# Tagged Questions

Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

151 views

### A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
48 views

### Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
4 views

### What is the difference between a MIMO and multiple MISO fuzzy logic classifiers?

If I have 10 independent inputs and 5 independent outputs, can I say that a multiple MISO fuzzy logic classifiers equal to the function of a MIMO fuzzy logic classifier?
28 views

### Finding integer solutions to quadratics in the form [duplicate]

In a set containing two different types of elements the probability of randomly choosing two elements of the same type can be expressed as: $$\ \frac nm * \frac {n-1}{m-1} = \frac 1x$$ Where n is ...
23 views

69 views

### Derangement combination calculation

For the traditional classic problem of derangement (https://en.wikipedia.org/wiki/Derangement), there is a formula $n! = (n-1)(!(n-1)+!(n-2))$, which calculates current results based on previous ...
114 views

50 views

### Algorithm for getting consecutive line segment edge points from midpoints

So I have a rectilinear grid that can be described with 2 vectors. 1 for the x-coordinates of the cell centres and one for the y-coordinates. These are just points with spacing like x spacing is 50 ...
46 views

19 views

### Enumerating (some) combinations of elements subject to a constraint

Consider this variant of the knapsack problem: I own an outdoor goods store, and hikers come from miles around because of my amazing variety of products for sale. There are 4 popular hikes in the ...
35 views

### algorithm problem: MxN matrix such that each element is from {0,1}

the question is the following: let $A$ be a matrix $m \times n$ such that each element is either $0$ or $1$ and each row has exactly $5x$ "$1$"s in it and each column has $5y$ $1$'s in it ...
54 views

### $L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
30 views

### calculating max n so that a has nth root over $\mathbb{Z}$

is there a nice (fast) way to find the maximal n so that for $a \in \mathbb{Z_+}$, $a^{1/n} \in \mathbb{Z}$ ? The only algorithmn which i know is brute Force. Greetings
16 views

### Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
51 views

### Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
47 views

### What is the required group theory knowledge needed to understand Verhoeff's algorithm?

The Wikipedia page tells me I need to understand permutation groups and dihedral groups. Can someone clearly outline what exactly the perquisites of understanding this is and how much time I'll take ...
I have a set of coupled tasks, let's say $M$ of them. The $ith$ coupled task is represented as the following 3-tuple $\{A_i,D_i,B_i\}$ where $A_i$ represents the time it takes to perform the first ...