A recursive solution to the all-pairs shortest-paths problem I am learning All pair Shortest Path from CLRS book,but got stuck in the begining itself.I am writing my query.

According to one of the Lemma of shortest path -:

  All Subpaths of shortest path are shortest.

Using this lemma, we can write the Structure of shortest path given as-:

  Consider a shortest path $p$ from vertex $i$ to $j$ and suppose that $p$ contains atmost $m$ edges.We can decompose path $p$ into subpath  $p^{'}$ i.e
    $ik\,\,(\,\,i\rightarrow\,\rightarrow k )$ and one edge $(k\rightarrow j)$
  From the lemma it is clear that subpath $p^{'}$is also shortest and $p^{'}$
  contains atmost $m-1$ edges.
  so we can write as

    $\delta\,(i,j)=\delta\,(i,k)+w(k,j)\label{eqn:1}  $

where $\delta\,(i,j)$=shortest path weight from $i$ to $j$

Allright!!!! I am Ok till here.

Now the Author has wriiten the recursive solution to all pair shortest path which too makes sense to me .It is given by-:

  $L_{i,j}^{m}$=Minimum weight of any path from vertex $i$ to vertex$j$ that contains atmost $m$ edges.

    $L_{i,j}^{m}$=$min_{(1\,\leq k \leq n)}$$\,\,(L_{i,k}^{m-1}\,\,+w(k,j)\,\,)$ $\,\,\,(1)$

Here $k$ is used to find out all the predecessors of $j$.

I am still ok here,but i am stuck in the following point.

  If  the  graph  contains no  negative-weight  cycles,  then  for  every  pair  of  vertices  $i$  and  $j$  for  which $\delta(i,j)\leq \infty$(i.e connected)there is a shortest path from $i$ to $j$ that is simple and thus contains at most $n-1$ edges.A path from vertex $i$ to vertex $j$ with more than $n-1$ edge cannot have lower weight than a shortest path from $i$ to $j$ . The
  actual shortest path is given by

$\delta(i,j)=L_{i,j}^{n-1}=L_{i,j}^{n}=L_{i,j}^{n+1}....   (2)$

I am not getting relation between this statment$((1)\,\,and\,\,(2)\,)$   .Please help me out to derive this.

(1) tells you how to compute the shortest path.

Note that given that the graph has no negative-weight edge, the shortest path between two nodes is a simple path (with no cycles) which has at most $n-1$ edges. More than $n-1$ edges means a cycle which increases the path length. But we are interested in the shortest path.

(2) claims that after $n-1$ edges the shortest path length remains same:
$L_{i,j}^{n-1}=L_{i,j}^{n}$ is read as "the shortest path from $i$ to $j$ passing through $n-1$ edges is the same as the shortest path through $n$ edges".

In fact it means that there is no need to compute $L_{i,j}^{n},L_{i,j}^{n+1},\dots$ since it will not lower the path between $i$ and $j$.


is advice function and an oracle the same thing? In the context of P/poly complexity class, an advice function is mentioned.
How is the advice function different than an oracle(/certificate)?
https://en.wikipedia.org/wiki/Advice_(complexity)
https://en.wikipedia.org/wiki/P/poly

No, they are not the same.  An oracle is something that an algorithm can send inputs to, and get back outputs, possibly many times.  Advice is a single value that is provided to the algorithm, and depends only on the length of the input to the algorithm.


What does it mean to take a union of a transition function with a starting state? $$
\delta(q,a) = \begin{cases}
\delta_1(q,a) & q \notin F_1 \text{ or } a \neq \lambda \\
\delta_1(q,a) \cup \{q_1\} & q \in F_1 \text{ and } a = \lambda.
\end{cases}
$$

Look at the second line of the function definition. It's a transition function. $q_1$ is the starting state. What does that union mean here? Union of the function range with $\{q_1\}$?

The function $\delta_1$ is the transition function of an NFA. It outputs a set of states. So $\delta_1(q,a) \cup \{q_1\}$ is just the union of two sets of states.


Expression Problem – looking for a similar standard problem The Expression Problem, populated by Philip Wadler,  is a often used to standard problem to evaluate programming languages.

I think it is a very clear and popular example and I wonder if there are any similar standard problems that are possibly also as widely used and as clear.

So, are there any similar standard problems?

(In the case of Feature Oriented Programming (link link) I found some standard problems, like:
- implementation of a stack with different features
- implementation of linked lists
- implementation of a calculator
- the graph product line
- stock broker and bank account examples
- hierarchical display
)

I'm not sure that the problem is formulated quite as nicely, but the problem of implementing concurrency in an efficient manner has occupied at least as much effort as the expression problem, and prompted a number of solutions, including the use of semaphores and software transactional memory.

I'm certainly not an expert, but I believe the problem of concurrency can be formulated in a similar manner to the expression problem: create language constructs which allow us to simultaneously:

Have sufficient expressivity to create complex concurrent programs, say, a web server.
Be able to have a reasonable assurance that these complex programs will not incur deadlock.


Algorithm to place apples in boxes Suppose we have $x$ apples and $y$ boxes. Each box can fit at most 3 apples, and we say that a box is half full iff the box contains $\leq$ 1 apple. If each apple has a (non-empty) list of boxes that it can be placed in, what is a polynomial time algorithm that places apples in boxes such that the number of half full containers is maximized?

My attempt

Sort apples in ascending order of the number of boxes that they can be placed into. For each apple, if there is an empty box that it can be placed into, then place the apple there. Otherwise, if there is a box with 2 apples in it that the current apple can be placed into, place the apple in that box. Otherwise, place the apple in a half full box. This algorithm clearly runs in polynomial time, but I don't think it is optimal, especially since I haven't specified how to break ties between boxes.

The below isn't necessarily a very practical algorithm, but (if I didn't make any mistakes) it shows this problem is in fact polynomial time.

I believe you can pose your problem as a series of integral maximum flow problems. I will phrase the problem with lower bound edge demands. This is equivalent to a regular flow problem.

We construct a maximum flow problem as follows:

Make a node for each apple and construct an edge from the source $s$ with capacity $[1, 1]$.
Made two nodes for each box (one input and one output node). For each apple that can fit in that box construct an edge from that apple to that box's input node with capacity $[0, 1]$. Connect the input and output node of each box with capacity $[0, 3]$.
Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $[0, 1]$.
Connect each box's output node to the sink $t$ with capacity $[0, 1]$.
Connect  $A$ and $B$ to $t$ with respective capacities $[0, n]$ and $[0, n]$.

Now we will minimize the number of overfull boxes ($\geq 2$ apples), which is the same as maximizing the number of half full boxes.  The critical observation is that each box can lose at most one of its apples to the sink - if it is overfull it must start flowing its apples through either $A$ or $B$. In the case of 3 apples both $A$ and $B$ must be utilized to maintain the $\text{out} - \text{in} = 0$ property of the flow problem.

Now when there is a feasible solution for $n = 0$ you know that there are no overfull boxes. Vice versa, if there exists a solution where there are no overfull boxes, there will be a feasible solution for $n = 0$.

Similarly, if there exists a solution where there are $k$ overfull boxes, there will be a feasible solution for $k = n$. This means that if we try all $n$ in increasing order, the first time we find a feasible solution we know it's optimal in $k$.

By inspecting the flow graph you can then find which apple goes in which box.

Since solving this maximum flow problem is polynomial in $x, y$ and $n$ is bounded in $y$, this algorithm is polynomial in the worst case as well.


Analyze Speed Up in A Dispatcher-Woker Model In a Dispatcher-Worker model of parallel computation, we have $N$ worker machines simultaneously working on the task (for example, computing the checksum of network packets). There is no synchronization between these workers. A dispatcher distributes total amount of work $S$ to these workers.

Now consider the problem of analyzing the speed up of this model. To simplify the situation, assume the dispatcher evenly distributes work $\frac{S}{N}$ to each worker. And each worker finishes it within $X_i \sim \mathcal{N}(\frac{S}{N}, \sigma^2)$ time, where $\mathcal(\mu, \sigma^2)$ is the Gaussian distribution. Then I think the mathematical formula for the total amount of time needed is
\begin{equation}
Y = \max(X_1, X_2, ..., X_N)
\end{equation}

The question is how to compute the distribution of $Y$, so that analytically we could understand the parallel time needed, in terms of the number of workers $N$.

Here is how you can compute its distribution.  Let $F(t) = \Pr[X_i \le t]$ (the cumulative distribution function of $X_i$), and $G(t) = \Pr[Y \le t]$ (the cumulative distribution function of $Y$).  Then

$$G(t) = \Pr[Y \le t] = \Pr[X_1 \le t, \dots, X_N \le t] = \Pr[X_1 \le t] \times \dots \times \Pr[X_N \le t] = F(t)^N.$$

Now the probability density function of $Y$, $g(t)$, is the derivative of the cumulative distribution function, so

$$g(t) = G'(t) = N F(t)^{N-1} f(t),$$

where $f(t)$ is the probability density function of $X_i$.  This directly gives you the distribution of $Y$: namely, $g(\cdot)$ is the distribution of $Y$.

This calculation also gives you a good way to compute tail bounds.  For instance, if you want to compute the probability that the whole process needs more than $t$ time, i.e., that $Y > t$, you can compute this as $1-G(t) = 1 - F(t)^N$.

See also https://math.stackexchange.com/q/89030/14578 for other useful facts about the distribution of $Y$.


Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will be the start state while the other will be the final state (they cannot be the same since otherwise the empty string will be accepted). My initial idea was to take a grammar for $L$ in GNF (Greibach Normal Form) (refer to Ran's answer below for details on how a CFG in GNF can be converted to a PDA having 1 state and no $\epsilon$-transitions that accepts by empty store) and then give a PDA for this that meets the specification. But the problem is that I cannot find a way to do this without having an $\epsilon$-move at the final step when I have to move to the final state after the stack is empty. Any help would be greatly appreciated.

The PDA can be specified as $M = (K, \Sigma,\delta, q_0, Z_0, \{q_f\} )$ where
$q_0$ is the initial state, $Z_0$ is the initial stack symbol and $q_f$ is the final state. The exact question is

  Show that if $L$ is a CFL and $\epsilon$ does not belong to $L$, then there is a PDA $M$ accepting $L$ by final state such that $M$ has at most 2 states and makes no $\epsilon$-moves.

Thus, the PDA should

accept by final state
have at most 2 states
make no $\epsilon$-moves

Indeed, as you say, a PDA can accept by final state or by empty stack. The two acceptance criteria can be effectively translated into one another. Main ingredient of that translation is to clearly mark the bottom symbol of the stack, so the PDA knows when the stack will be empty. In that way it will not accidently block or accept when not planned.

True, given a CF grammar you can construct a single state PDA, accepting by empty stack. In that simulation the contents of the stack correspond to the part of the string not rewritten in a leftmost derivation. If the CFG you start with is in Greibach Normal form, then the PDA can be constructed to be "real-time" i.e., it has no $\epsilon$-moves.

The point is to combine both ideas. Thus mark the last nonterminal. When it is removed (not replaced by another nonterminal), then move to the second state, the final accepting state (at the same time emptying the stack).

For the CFG from your example $S\to aSB, S\to aB, B\to b$ this can be obtained by changing the grammar a little and making a "marked" copy $\bar X$ of each nonterminal $X$ to indicate bottom of stack: $\bar S\to aS\bar B, \bar S\to a\bar B, \bar B\to b, S\to aSB, S\to aB, B\to b$. Production $\bar B\to b$ is the final one. $\bar S$ is the new start symbol.


Applying algorithms on large data Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how to efficiently apply those algorithms considering the cost of block transfer from external memory ? For example, almost all algorithm textbooks say that B and B+-trees can be used to store data on disk. However, actually how this can be done, especially handling the pointers where the data is present on disk is not explained. Similarly, though many books teach searching techniques, they do not consider data present in secondary memory.

I have checked Knuth's book. Although it discusses these ideas, I still did not understand how to actually apply them in a high-level language. Is there any reference that discusses these details?

Database books are good example. However, have a look at the field I/O efficient data structures (and algorithms). To my knowledge, there are some  courses about this topic, but very few books.

Check this book: U. Meyer, P. Sanders, and J. Sibeyn (eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Check these courses:
http://www.win.tue.nl/~hermanh/teaching/2IL35/
http://www.daimi.au.dk/~large/ioS12/

and these slides:
algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf


Find the maximizing row-column matches in a matrix I have a set of R x C matrices similar to the following (can be much longer):

    C1      C2      C3      C4      C5      C6
R1  0.32    0.81    NA      NA      NA      NA
R2  0.90    -0.44   0.95    NA      NA      NA
R3  NA      0.93    0.86    0.24    NA      NA
R4  NA      NA      0.70    0.74    0.15    0.05
R5  NA      NA      NA      NA      NA      NA

I need to find the sequence of row-columns matchings that provides the overall maximum values (when summed). Each row can be associated to one and only one column, and "cross" matchings are not allowed, i.e. if R2 was matched with C4, a following row R>2 cannot be matched with a previous column C<4.

Given the limit on crossed matching, and as the number of rows and column can be unequal, obviously not all rows and/or columns will be matched

The solution in this example would be:

[R2:C1 = 0.90] + [R3:C2 = 0.93] + [R4:C4 = 0.74] = 2.57

which is higher than alternative solutions that may contain the highest values in the matrix, such as:

[R2:C2 = 0.81] + [R2:C3 = 0.95] + [R4:C4 = 0.74] = 2.50

The only solution I came up with is to create all possible RxC matrices populated by 1 and 0 where the marginal of each row and each column is not greater than 1, and where the no-crossing rule is respected.
Then by multiplying such matrices with the original ones, I obtain new matrices containing ONLY the values in the solution, which can be easily summed.

Example of the solution above:

    C1  C2  C3  C4  C5  C6  |   row
R1  0   0   0   0   0   0   |   0
R2  1   0   0   0   0   0   |   1
R3  0   1   0   0   0   0   |   1
R4  0   0   0   1   0   0   |   1
R5  0   0   0   0   0   0   |   0
_______________________________
col 1   1   0   1   0   0

This is a valid matrix as all the marginals are <= 1 and the positioning is ordered by column = 1,2,4 and by row = 2,3,4

The problem with this solution is that as R or C grows the number of possible permutations becomes extreme.

I need to implement a general and fast solution in a software, and I can't compute millions of table each time.

Any hint will be useful, thanks!!!!

EDIT: This is my implementation of D.W.'s answer in pseudo code

result = matrix(R, C, 0) //allocate response matrix RxC with all elements = 0
for (i from 1 to R){
  for (j from 1 to C){
    part1 = A[i-1,j]
    part2 = array[j] //allocates array of length j
    for(jPrime in 1:j){
      part2[jPrime] = M[i,jPrime] + A[i-1,jPrime-1]
    }
    A[i,j] = max(part1, max(part2))
 }
}

This returns the following A matrix:

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,] 0.32 0.81 0.81 0.81 0.81 0.81
[2,] 0.90 0.90 1.76 1.76 1.76 1.76
[3,] 0.90 1.83 1.83 2.00 2.00 2.00
[4,] 0.90 1.83 2.53 2.57 2.57 2.57
[5,] 0.90 1.83 2.53 2.57 2.57 2.57

The problem can be solved with dynamic programming in $O(RC)$ time.

I'll start by showing how to solve it in $O(RC^2)$ time.  Let $M[\cdot,\cdot]$ denote the input matrix.  Let $A[i,j]$ denote the total value of the best matching using only rows $1..i$ and columns $1..j$.  We will compute the entries of $A[\cdot,\cdot]$.  There is a recursive relation for $A[\cdot,\cdot]$:

$$A[i,j] = \max(A[i-1,j],\max\{M[i,j'] + A[i-1,j'-1] : 1 \le j' \le j\}).$$

Here the $A[i-1,j]$ term corresponds to not including any match for row $i$, and the $\max\{M[i,j'] + A[i-1,j'-1] : 1 \le j' \le j\}$ corresponds to matching row $i$ to column $j'$.

You can fill in the entries of the $A$ array in a straightforward way in $O(RC^2)$ time, and the value of the best matching is given by $A[R,C]$.  So, this gives an $O(RC^2)$ time algorithm.

You can speed this up to $O(RC)$ time by simultaneously computing another array $B[\cdot,\cdot]$, with entries defined as

$$B[i,j] = \max(A[i,1],A[i,2],\dots,A[i,j]).$$

Then all of the entries of $A$ and $B$ can be filled in, if you do it in the right order, in a total of $O(RC)$ time.  This is linear in the size of the matrix, i.e., proportional to the number of entries in the input matrix. Since any algorithm will presumably have to examine all entries in the matrix, I think that means this algorithm is asymptotically optimal: no algorithm can run faster by more than a constant factor.


Combine $k$ sorted lists into one Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time.

The solution I came up with is to recursively halve the lists until you have sections of two lists. Then you combine them by setting a pointer at the start of each one, and placing the smaller element into a new array and incrementing its pointer until you've gone through every element, then return that sorted array.

The combine part does at most $2n$ comparisons, so it's $O(n)$. The recursion depth is $\log_2 k$, since you're halving the remaining lists at each combination. This would give a total of $n\log_2 k$.

Is this a correct implementation and time analysis?

What you describe is a sort of recursive merge which generalizes merge sort, and indeed results in the advertised complexity. The pointer procedure which you are trying to describe is usually just called merge.

Another approach is using a min-heap of size $k$, which stores the current "contenders" for the $k$ smallest elements. It is initialized with the smallest elements of each of the lists, and at each step you pop the smallest element and add it to the merged array, replacing it with the next smallest element in the corresponding list.


Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S ) Prove that the following grammar is ambiguous; S → a | S + S | S S | S* | ( S )
checking ambiguity in grammar. the subject of this question is compiler construction and automation. would you please help me find the answer we only have to figure out whether its ambiguous or not

To show the grammar is ambiguous, you must find a string derived by the grammar which has two or more distinct parse trees. I think we have a few options here. One that should work is S + S*:
                   S
                  /
                 /
   S            S--+
  /            / \
 /            /   \
S--+         S     S
 \            \
  \            \
   S--S         *
    \
     \
      *

These derivations are fundamentally different (not just different orderings of the same derivation) and so the string S + S* is fundamentally ambiguous. Does it mean (S + S)* or does it mean S + (S*)?


How to properly solve T(n) = T(n-1) + O(2^n)? I've been trying to solve this recurrence: T(n) = T(n-1) + O(2^n)

My approach when writing everything out and solving the geometric series was: T(n) = O(2^n).

T(n) = c2^n * (1 + 1/2 + 1/4 + ...)

= c2^n * (1/2)^i for i from 0 to infinity

T(n) <= d*2^n for some constant d.

What you did is fine for most purposes. If you want a really rigorous proof without "dot dot dots," then you need to use induction. For that you need to make the constant in big-Oh explicit, and use your "back of the envelope calculation" to come up with the induction hypothesis.


Difference between capacity miss and conflict miss Premise:

Two types of cache miss:  capacity miss, conflict miss\
Cache contains only 2 sets, SET 1 and SET 2

Problem:

If data A maps to SET 1 and it doesn't exist in SET 1 while SET 1 is fully occupied and SET 2 is not fully occupied, I know this case is called conflict miss. But what should it be called if the same case but entire cache is fully occupied? Is it capacity miss or conflict miss? Once the cache is fully occupied, conflict miss will never happen?

It will be capacity miss because capacity miss means that your cache is full and there is no way to accommodate the data A.
Yes it means Once the cache is fully occupied, conflict miss will never happen.


Can PTAS $\epsilon$ parameter be dependent on the algorithm input? Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$.
Let $n$ be the input of the algorithm A.
From Wikipedia:

The running time of a PTAS is required to be polynomial in $n$ for every fixed $\epsilon$, but can be different for different $\epsilon$.

Can we define $\epsilon$ to be equal to $\frac{1}{n}$?
Thus, the time complexity of A would be $O(n)$, which is polynomial in $n$, but, can $\epsilon$ be dependent on $n$?

If $A$ is an algorithm whose running time is $O(1/\epsilon)$, then if you substitute $\epsilon = 1/n$, its running time will be $O(n)$. This is a property of the particular algorithm $A$ rather than of polynomial time approximation schemes. We have absolutely no guarantee on the running time of a PTAS when $\epsilon$ is subconstant (i.e., when $\epsilon = o(1)$).
The running time of algorithms tends to depend on the input length (though it's not always the case), so I'm not convinced that $A$ really has running time $O(1/\epsilon)$.


experimental analysis of running times in extendable table I was given the following homework question:

  Implement an extendable table using arrays that can increase in size
  as elements are added. Perform an experimental analysis of each of the
  running times for performing a sequence of n add methods, assuming the
  array size is increased from N to the following possible values:

  2N
  N + ceiling(√N)
  N + ceiling(log N)
  N + 100

I'm just a little confused about what this question is asking, and was hoping for some help/clarification. The way I understand it, you could implement something like this in Python with a two-dimensional array (the "extendable table"), and then append varying numbers of values for each scenario. Am I understanding the implementation correctly?

Then, I'm also a bit unclear on what number of values you'd be appending. Would you literally first test it with say, 16 values, then 32 (2N), then 20 (ceiling(√N)), etc? Or is it more complex than that?
Any help is appreciated!

An extendable array isn't a two-dimensional array (I don't know what's an extendible table). The idea is that you start with an array of a fixed size, and each time you are trying to insert an element into the array but it's full, you increase the size from $N$ (its current size) to $f(N)$ (its subsequent size, until it needs to be enlarged again). That means that you allocate new memory ($f(N)$ items), copy the old array into the new place, and then free the old memory. When you have added $f(N)-N-1$ more elements, a subsequent insertion would require enlarging the array to size $f(f(N))$, and so on. The question is what is the best choice for the function $f$.

Experimentally, you can try different functions $f$. For each such suggestion $f$ (and the same initial size of the array, say something like 20 or 100, you decide), plot $n$ against the time it takes to add $n$ elements (what elements you add isn't important; you could just add zeroes), averaged over several trials. I'll let you decide how exactly to do that, but you probably want several different values of $n$, and $n$ as large as roughly a million or so (you decide exactly how large). You can then find which function is better than others. I suggest you use C rather than python in your experiments.


Counting Number of arrays where sum of ith row is greater or equal to (i-1)th row I am working on a problem where I am supposed to count the number of arrays of size $N\times M$ where the sum of elements in the $i$-th row is greater than or equal to the the sum of elements in the $(i-1)$-th row. And the the sum of elements in $N$-th row (the last row) is less than or equal to $M$. All the elements are non negative integers.

For example, $N=2, M=2$ there are 25 solutions.

The solution that I have worked out so far is that for a row to have sum less than $M$, the number of possible ways is $C(2M,M)$. But I am unable to implement the remaining constraint.

The case where $N=2$ is fairly easy. For $M\ge N$ we'll have an array
$$\begin{array}{ccccc}
a_{1,1} & a_{1,2} & a_{1,3} &\dotsm & a_{1,M}\\
a_{2,1} & a_{2,2} & a_{2,3} &\dotsm & a_{2,M}\\
a_{3,1} & a_{3,2} & a_{3,3} &\dotsm & a_{3,M}\\
        &\dotsm   &         &       &        \\
a_{N,1} & a_{N,2} & a_{N,3} &\dotsm & a_{N,M}\\
\end{array}$$
Define $t(k,M)$ to be the number of integer solutions of $x_1+x_2+\dotsm+x_m=k$ with all $x_i\ge 0$. The stars and bars theorem tells us that
$$
t(k,M)=\binom{M-1+k}{M-1}
$$
Then if we let $C(N,M)$ denote the number of solutions to the original problem, it's not hard to see that for $N=2$,
$$\begin{align}
C(2,M) &= \sum_{i=0}^M\left[t(i,M)\sum_{j=0}^it(j,M)\right]\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\sum_{j=0}^i\binom{M-1+j}{M-1}\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\left[\binom{M-1}{M-1}+\binom{M}{M-1}+\dotsm+\binom{M-1+i}{M-1}\right]\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\binom{M+i}{M}
\end{align}$$
The last step above uses a fairly well-known result on the sum of a column of Pascal's triangle. So finally we'll have
$$
C(2,M) =\binom{M-1}{M-1}\binom{M}{M}+\binom{M}{M-1}\binom{M+1}{M}+\dotsm+\binom{2M-1}{M-1}\binom{2M}{M}
$$
For $N=M=2$ we have $C(2,2)=1+6+18=25$, which agrees with your example.

Added yet again. For a (not particularly useful) general form, it's not hard to see that
$$
C(N,M)=\sum_{0\le i_1\le i_2\le\dotsm i_N\le M} t(i_1,M)t(i_2,M)\dotsm t(i_N,M)
$$
In this expression, each of the $i_k$ represents the possible sum of the $k$-th row.

I asked on Math.SE whether the expression for $C(2,M)$ had a closed form and the consensus was that it didn't (although it can be expressed as a hypergeometric series, for what that's worth).


Stable Marriage Problem unique match I'm having some thoughts and I'd like to have your opinion about it.
Given a basic, normal instance of SMP (men-women, men choose), we define $\mu$ to be the set of all stable matches.

Each member of $\mu$ consists of men-rank, which describes the satisfaction index of the men - which in this case the member with the highest rank is the male-optimal match.

So if we run the stable-match known algorithm, the output would be the match with the highest rank, because the algorithm always returns the men-optimal and female-pessimal match - lets denote this match by $A$.

Now, lets replace the roles, and run the algorithm again.
We denote the output match by $B$ - which is the female-optimal and male-pessimal match.

Assuming $A=B$:

Can we say that this instance has a unique stable match?
What else can we say about this instance?

I will answer your first question.

By definition, a matching $A$ is male-optimal if for any male $m$ and stable matching $C$, $A(m) \succeq_m C(m)$, that is, $m$ prefers $A(m)$ at least as much as $C(m)$, where $A(m)$ is the female assigned to $m$ by $A$.

Similarly, by definition, a matching $B$ is male-pessimal if for any male $m$ and stable matching $C$, $B(m) \preceq_m C(m)$.

Now suppose that $A$ is male-optimal, $B$ is male-pessimal, and $A = B$. Take any male $m$ and any stable matching $C$. By definition, $A(m) \succeq_m C(m) \succeq_m B(m) = A(m)$, and so $C(m) = A(m)$. In other words, $C = A$, and so the stable matching is unique.


Definition of “K-fairness” with respect to concurrency? There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that satisfy a 1-fairness or 3-fairness property). Does this actually exist or is this something that was made up to describe a phenomenon that I am not recognizing?

Perhaps you should look for "bounded fairness", the property that something happens within the next $k$ times, where $k$ is the bound.


Can 2-philosophers problem be analogous to dining philosophers problem? Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B.

Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A needs all come from B. However, the DP problem usually gives an example of 5 philosophers, in which case, for example, philosophers A requests 2 forks from two different neighbors.

Short answer: yes, though it could be considered a "degenerate case" (that is, a case that ends up being somewhat different from most others).

Long answer: the Dining Philosophers problem is really about having $n$ philosophers, and coming up with an algorithm that works for any $n$. A good algorithm should work for even "degenerate cases" like zero philosophers or one philosopher—by hard-coding them if necessary ("if there's only one philosopher, eat whenever you feel like"). So $n=2$ is a perfectly valid Dining Philosophers problem.


Selection problem on the union of two ordered dictionaries Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the kth smallest key in the union of keys from S and T. (assuming no duplicates)

I am confused on what the question is asking. I am assuming the keys are not ordered, otherwise all you would have to do is compare the first key in each dictionary, or is that what array-based ordered sequence means? Also are we creating a larger dictionary that holds both S and T inside? Would this add to the complexity if so? For the search algorithm, would we use a binary search since its complexity is O(log n)?

The following algorithm uses the divide-and-conquer technique. In the course of divide-and-conquer, the lengths of both sorted arrays $S$ and $T$ will change. We denote the length of $S$ (or, $T$) by $len(S)$ (or $len(T)$) at any time. Notice that I only summarize the algorithm and have intentionally omitted the tricky things about indexes (e.g., taking floor or ceiling).

Notations and Basic Idea:

At any iteration, denote the median index of $S$ by $s_m \triangleq len(S) /2$ and the median of $S$ by $S[s_m]$.
Similarly, denote the median index of $T$ by $t_m \triangleq len(T) / 2$ and the median of $T$ by $T[t_m]$.

  The basic idea is as follows: we compare $s_m + t_m$ with $k$ and $S[s_m]$ with $T[t_m]$ to determine which (left or right) half part of which array ($S$ or $T$) can be discarded and then we can leave the smaller sub-problem to recursion.

Algorithm:

Case 1 ($s_m + t_m \geq k$):

1.1 Case 1.1 $S[s_m] \geq T[t_m]$.

We can discard the right bigger half of array $S$ (i.e., from $S[s_m]$ to its end). Then recursively find the $k$-th smallest element in $T$ and the left smaller half of $S$.

1.2 Case 1.2 $T[t_m] > S[s_m]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.
Case 2 ($s_m + t_m < k$):

2.1 Case 2.1 $S[s_m] \geq T[t_m]$.

We can discard the left smaller half of array $T$. Then recursively find the $(k - t_m)$-th smallest element in $S$ and the right larger half of $S$.

2.2 Case 2.2 $T[t_m] > S[s_m]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.

Time Complexity:

At each iteration, we discard a half of some array. So the time complexity is $O(\lg (len(S)) + \lg (len(T)))$, which is $O(\lg n)$ for input arrays $S$ and $T$ of size $n$.

References:

How to find the kth smallest element in the union of two sorted arrays?
Finding kth smallest number from n sorted arrays A generalization to multiple sorted arrays.


Is it true that $ 2^{O(3k)} = 2^{O(k)} $? Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
But It should be different from  $ O(2^{k}) = 2^{O(k)} $ ?
I will be happy for simple explanation.
Thanks.

$\mathcal{O} (3k) = \mathcal{O} (k)$ because $\mathcal{O} (k)$ can be defined like this:
$$
\tag{1}
d = \mathcal{O} (k) \implies d \le Ck ,
$$
for some constant $C>0$ and for all $k$ larger than some threshold, and similarly $\mathcal{O}(3k)$ would be defined as:
$$\tag{2}
d_3 = \mathcal{O}(3k) \implies d_3 \le C_3 (3 k),
$$
for $C_3 > 0$ and for all $k$ larger than some threshold.
Now remember that $C$ and $C_3$ are positive, so $3C_3 > C$, which means that if $d_3 = \mathcal{O}(3k)$ then it must also be $\mathcal{O}(k)$.
Then since $2^k$ is a monotonic function, we also have that $2^{\mathcal{O}(3k)} = 2^{\mathcal{O}(k)}$.
Some will argue that specifying the extra constant of "3" is redundant and formally improper, but you might still find that constant explicitly written in some papers, especially by people that don't know the above definition and tend to use big-O notation with (some would say regrettable) looseness.
The bottom line: If you know the constant hiding under the Big-O is 3, you might as well just say $d \le 3k$ instead of $d=\mathcal{O}(3k)$.

You've added a new question to your post after two of us already answered the first one. For the second question:
$2^{\mathcal{O}(k)}$ gives us everything of the form $2^l$ where $l \le Ck$ under the conditions of Eq. 1.
By monotonicity of the function $2^l$ we have everything smaller than $2^{Ck} = (2^C)^k$ under similar conditions.
Let's consider the example where $C=2$.

Your question becomes whether or not $\mathcal{O}(2^k) = \mathcal{O}(4^k)$, but since there is no constant $C$ such that $4^n \le C  2^n$, it is not true that $\mathcal{O}(2^k) = \mathcal{O}(4^k)$.
Therefore it is also not true that $\mathcal{O}(2^k) = \mathcal{O}(2^{Ck})$ and:
it's also not true that  $\mathcal{O}(2^k) = 2^{\mathcal{O}(k)}$.

Conclusion: $\mathcal{O}(2^k) \ne 2^{\mathcal{O}(k)}$ in general.


Why is compression ratio using bzip2 for a sequence of "a"s so jumpy? library(ggplot2)

compress <- function(str) {
  length(memCompress(paste(rep("a", str), collapse=""), type="bzip2"))
  / nchar(paste(rep("a", str), collapse=""))
}

cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress))

ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) + geom_line()

The compression ratio starts out at 37 for "a" and hits the break-even at 39 "a"s (compression ratio = 1). The chart starts out pretty smooth and gets edgy suddenly for 98 "a"s and from there at increasingly small intervals.

The local lows and smooth sections seem also quite erratic and random. Can somebody explain to me why bzip2 shows this behaviour in this example?

Suppose a simple compression algorithm that represents a run of a by storing $(\text{header}, \mathtt{\text{"a"}}, n)$, i.e. some fixed header, the string a, and the number of repetitions $n$. This is a run-length encoding. Then the length of the compressed text would be close to $a + \lg n$ bits for some constants $a$. The corresponding compression ratio would be $\dfrac{a + \lg(n)}{n}$. This is roughly the shape of the curve as seen from a distance, if you neglect the local ups and downs. Asymptotically, the compression ratio is $\Theta(\lg(n)^p/n)$ with $p \ge 1$ (I haven't worked it out but I suspect there are other factors at play which make the size of the output superlinear in the length of the input string).

$\lg n$ bits aren't an integer number of bits, let alone bytes: the size of $n$ has to be at a minimum rounded up to an integer number of bytes. This explains a first threshold effect: for this simple compression algorithm, you would observe that the length of the output is $a$ when $n$ is sufficiently small, then $a+1$, then $a+2$, etc. The compression ratio therefore isn't a smooth curve but jumps from $\dfrac{a}{n}$ to $\dfrac{a+1}{n}$, then $\dfrac{a+2}{n}$, etc. This effect is barely visible in the realignment after jumps (but there are other effects at play which make the jumps different).

Since the compression ratio is too close to the inverse ratio of the length for visual observation, here is the data for small length in my implementation (this may be dependent on the version of the bzip2 library, as there are multiple ways to compress some inputs). The first column indicates the number of a's, the second column is the length of the compressed output.

1–3       37
4–99      39
100–115   37
116–258   39
259–354   45
355       43
356       40
357–370   41
371–498   43
499–513   41
514–609   45
610       43
611       41
613–625   42
626–753   44
754–764   42
765       40
766–767   41
768       42
769–864   45
…

Bzip2 is far more complex that a simple run-length encoding. It works in a series of steps, and the first step is a run-length encoding step, but with a fixed size limit. The first step works as follows: if a byte is repeated at least 4 times, then replace the bytes after the 4th by a byte indicating the repeat count of the erased bytes. For example, aaaaaaa is transformed to aaaa\d{3} (where \d{003} is the character with byte value 3); aaaa is transformed to aaaa\d{0}, and so on. Since there are only 256 distinct byte values, only sequences where the byte is repeated up to 259 times can be encoded this way; if there are more, a fresh sequence starts. Furthermore, the reference implementation stops at a repeat count of 252, which encodes a string of 256 bytes.

This step explains the first threshold and the threshold at 258: $\mathtt{a}^n$ compresses to 37 bytes for $1 \le n \le 3$ and to up to 39 bytes for $4 \le n \le 258$. The introduction of the repeat count results in 2 more bytes in the output of the subsequent steps, and that extra byte is able to represent all repeat counts up to 258. After 258 bytes, there is a second RLE string. There is a third one at 514 bytes, a fourth at 769 bytes, and so on. Extra RLE strings after the second one don't cost much if at all because that sequence aaaa\d{252} (assuming that \d{252} is the repeat count, I haven't checked) is itself repeated and therefore compressed by subsequent steps.

Why are the thresholds at 258, 516, 769, (none at 1024), 1279 rather than exact multiples of 256? I suspect it's because the Burrows-Wheeler transform followed by a move-to-front can transform something like aaaa\374aa (output of step 1 for $n=258$) by moving the a's together so that they can be encoded together, but I haven't checked.

The reduction in length at $n=100$ is interesting. For the input $\mathtt{a}^{101}$, the first RLE step produces aaaa\d{97} — but the byte value of a is 97, so this is aaaaa which has better potential for compression by subsequent steps. I suspect that the shrinking effect not only for $n=101$ but also for surrounding values is due to the delta encoding step which makes it easier to store bytes with nearby values. If you change a to A (65), you'll notice that the shorter output happens for $68 \le n \le 83$.

My analysis of this example is far from exhaustive. To understand other effects, you would have to study the other steps of the transformation: I mostly stopped after step 1 of 9. I hope this gives you an idea of why compression ratios get a little choppy and don't vary monotonically. If you really want to figure out every detail, I recommend taking an existing implementation and observing it with a debugger.

For the most part, such minute variations aren't the main focus when designing a compression algorithm: in many common scenarios, such as general-purpose or media compression algorithms, a difference of a few bytes is irrelevant. Compression tries to squeeze out every bit at the local level, and tries to chain transformations in such a way as to gain often while rarely losing and then not by much. There are nonetheless situations such as special-purpose communication protocols designed for low-bandwidth communication where every bit matters. Another situation where exact output length matters is when the compressed text is encrypted: when an adversary can submit part of the text to be compressed and encrypted, variations on the length of the ciphertext can reveal the part of the compressed-and-encrypted text to the adversary; this was recently publicized in the CRIME exploit on HTTPS.


Why does the principle of locality of computation not relativize? Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS).  However, one of the techniques I've read about that does not relativize is using the fact that all of a Turing machine's computation is local and I'm wondering why this is a valid approach.

After all, the oracle tape has to be read somehow and if it is not locally then how?  As I learned through this post regarding the Time Hierarchy Theory and relativization, the oracle of a polytime OTM must be accessed via a polytime reduction so it cannot just act arbitrarily.  Is it just that the oracle tape is read only?  Or is that even if computation is local for an OTM, we just regard this aspect as irrelevant since a call to the oracle is seen as taking one step? Thanks.

When you go into a special "oracle" step, the oracle reads the entire contents of the oracle tape and determines its output based on the entire tape. This is the non-local aspect of oracle computation.


Injectivity not required for unification algorithms? When learning about a general unification algorithm, we learned the rule decompose, which states unifying

$$G \cup \{f(a_0,...a_k)=f(b_0,...,b_k)\} \Rightarrow G \cup \{a_0=b_0,...a_k=b_k\}.$$

The question of, "What if $f$ is not injective?" stood out to me. Say $f$ is not injective, and we traverse that branch of computation where $f(a_0,...a_k)=f(b_0,...,b_k) \Rightarrow \{a_0=b_0,...,a_k=b_k\}$ and lead to failure. Is it possible that there's another way to assign $a_0,...,a_k$ to $b_0,...b_k$ such that it's unifiable?

I was thinking maybe of an example to demonstrate what I mean. This may not be a good example, but say we consider $f(x,y) = x+y$, and we want to unify $f(h(a),g(b)) = f(g(c),h(d))$ then we would fail by assigning $\{h(a) = g(c), g(b)=h(d)\}$ by decompose, but succeed in unification if instead we first switch the arguments of $f$ (valid since $f(a,b)=f(b,a)$), which will yield $\{a \mapsto d, b \mapsto c\}$.

I was reading a bit about it in this paper on page 6 where they discuss the idea of strictness in terms of decompose, but I don't quite understand it, and more generally how we can perform this unification step of decompose on a general $f$ without somehow backtracking on failure.

Here $f$ is not a mathematical function.  Rather, it is a function symbol.  Don't think of $f(a,b)$ as the result of evaluating the function at parameters $a,b$.  Rather, think of it as a term in a symbolic expression -- it is a syntactic object that is not intended to be interpreted in the way you are interpreting it.

If you like, you can think of it as though every function symbol in a symbolic expression is an injective function; but that's not really accurate, that's just a crude way to think about symbolic expressions.

You can't define $f(x)=x+y$.  $f$ is an uninterpreted function symbol.  You're not allowed to define a particular function.  Rather, $f$ is a stand-in for a function that is not yet defined. One way to think about it is that any conclusions that you draw from unification, are conclusions that should hold for all functions $f$ (not just a single one).


Error in pivot selection algorithm for merge phase [Sorting] In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart on the other GPU-partition). That pivot element is crucial for being able to merge the two partitions, given that we have already sorted them on each GPU locally.
However, the pseudo-code for that pivot-selection, as shown in the paper, doesn't seem to reflect the whole truth since when implementing it 1:1, the selected pivot element is off by some elements in some cases, depending on the input - the amount of elements to sort and therefore the amount of elements per partition (the chunk of data that each GPU gets).
To get more specific, the problem is - to my understanding - that the while loop is exited too early due to the stride being reduced down to zero before the correct pivot element has been found. In general, the approach is binary search-like, where the range of where the pivot can fall, is halved each iteration.
Can anyone spot what needs to be done here?
Here is a C++ implementation of the pivot selection:
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b)
{
  size_t pivot = a.size() / 2;
  size_t stride = pivot / 2;
  while (stride > 0)
  {
    if (a[a.size() - pivot - 1] < b[pivot])
    {
      if (a[a.size() - pivot - 2] < b[pivot + 1] &&
          a[a.size() - pivot] > b[pivot - 1])
      {
        return pivot;
      }
      else
      {
        pivot = pivot - stride;
      }
    }
    else
    {
      pivot = pivot + stride;
    }
    stride = stride / 2;
  }
  return pivot;
}

P.S.: I tried ceiling the stride in order to not skip iterations when the stride is odd, but this introduced the issue of moving out of bounds of the array and even after handling those cases by clipping to the array bounds, the pivot was not always correct.

The "Algorithm 1 Pivot selection" of that paper is rather sloppy. The critical mistake is, as you have noted, "the while loop in the algorithm is exited too early due to the stride being reduced down to zero before the correct pivot element has been found".
There are two other drawbacks.

The condition, a[len(a) − pivot − 2] < b[pivot + 1] is superfluous since it is implied by a[len(a) − pivot − 1] < b[pivot].
It does not handle the situation where there are equal elements in the array.

To address that critical mistake, make sure that the stride is always greater than 0. To prevent out-of-bounds exceptions, extreme boundary cases should be specially handled beforehand. To handle equal elements, equal signs can be included at some comparisons.
Here is a correct algorithm in C++ that selects the desired pivot, following the pseudocode in the paper with the aforementioned modifications.
// Return a pivot so that a[size-pivot:size] and b[0:pivot] should
// be swapped. If 0 is returned, no elements should be swapped.
// It is assumed that vector a and b are sorted of the same size.
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b) {
  size_t size = a.size();

  if (b[0] >= a[size - 1]) return 0;
  if (a[0] >= b[size - 1]) return size;

  size_t pivot = size / 2;
  size_t stride = std::max(1, pivot / 2);
  while (true) {
      if (a[size - pivot - 1] <= b[pivot]) {
          if (a[size - pivot] > b[pivot - 1]) return pivot;
          else pivot = pivot - stride;
      } else {
          pivot = pivot + stride;
      }

      stride = (stride + 1) / 2;
  }

  return pivot;
}

Note that the method above requires the size of a is equal to that of b. Otherwise, a few more lines of code are needed.
If you are not required to stick to the pseudocode in that paper, which is not very good anyway, please check another version of my answer, where I use my preferred version of binary search to select the desired pivot.


Big O notation space/time I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read examples in books because authors don't always give precision about whether the given result is a time or space complexity.

So, when you see that an algorithm has a O(n) complexity, you don't know much. You have to say: this algorithm has a O(n) time complexity.

IHMO I think it would be much more useful to use two separated letters like O(n) and T(1) for instance.

Is there such convention when talking about algorithm complexity?

Big O notation comes from number theory.

It's not about time or space at all. It's about the rate of growth of functions.

Even in computer science, we use it measure many other quantities, for example the number of rounds in a protocol, the depth of a circuit, the error probability of an algorithm, and so on.


Exploration in reinforcement learning when state space is huge When the state-action space is huge I know I can use function approximators to generalize but how can I explore? Doing an exhaustive search seems very naive. What DeepMind for example did to explore the state-action space in Atari games?

In the Atari paper, an $\epsilon$-greedy strategy is used for state-space exploration. This means that the algorithm makes the deep network learn a greedy strategy to pick an action that maximises the $Q$-value of the current state ($a = max_a Q(s, a; \theta)$. At each time-step in a game, the agent picks an action as per this greedy strategy with probability $1-\epsilon$ and it picks a random action to explore the state-space with probability $\epsilon$.
The value of $\epsilon$ can be varied depending on whether we want the agent to explore more ($\epsilon$ value high) or learn from its past behaviour more ($\epsilon$ value low).
In the paper, the authors mention that $\epsilon$ is annealed linearly from 1 to 0.1 over the first million frames, and fixed at 0.1 thereafter.


Expected number of random interval flips needed for sorting a random array This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort.
Assume that $A$ is an array initialized by a random permutation on the set $I_n=\{1,2,\ldots, n\}$.
Consider the next algorithm:

While $A$ is not sorted:

Pick two random numbers $i\leq j\in\{1,2,\ldots, n\}$ uniformly and reverse $A[i\ldots j]$.

For example, if the initial array was $A=1,4,2,3,5,6$ and the algorithm  picks $i=2,j=5$ then the value of $A$ after the reversal would be $1,5,3,2,4,6$.
Notice that this algorithm halts after finite number of iterations with probability 1.

What is the expected number of iterations for the algorithm?

$\Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $\Omega(n!)$ iterations on average.  Obviously, you need to try at least $\Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation).

Also, one can show that $O(n! \cdot n \lg n)$ is an upper bound on the number of iterations needed.  Here's why.  It's known that there is a constant $c$ such that composing $k=c n \lg n + o(n \lg n)$ randomly chosen transpositions gives you something that is close to a random permutation.  So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant.  Each one is approximately a random permutation (independent of all others).  After checking $\Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order.  Therefore, your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.  Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort -- thus your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.

So we know that the answer is at least $\Omega(n!)$ and at most $O(n! \cdot n \lg n)$.  Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn't leave much of a gap -- it almost totally resolves the question.  If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap -- but lacking clear motivation for studying this problem, it's not clear it's worthwhile to spend that level of energy on it.

How do we know that composing $O(n \lg n)$ random transpositions gives you something close to a random permutation?  That was proven in the following paper:

Generating a Random Permutation with Random Transpositions.  Persi Diaconis, Mehrdad Shahshahani.  1981.

See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.


Algorithm to find shortest path between two nodes I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint.

The additional constraint is that there are $N$ sets of special edges with weight $0$ such that a path is not considered valid if it traverses one edge in a set but not the remaining edges in that set.

Note that these $N$ sets of edges are disjoint such that no edge belongs to more than one of the $N$ sets. The number of edges in each set is around 3 to 6. And there are a large number of these sets. About $50\%$ of edges belong to a set, the rest don't belong to a set and can be traversed normally.

Does such an algorithm exist? Can such an algorithm exist that is better than brute force?

It is $NP$-complete, and thus it is unlikely that a polynomial algorithm ("better than brute force") exists. Proof is by reduction from Hamiltonian $s-t$-Path:

Every edge in the input graph $G=(V,E)$ is given weight $1$. The graph is then duplicated, and special (weight 0) edges are added between corresponding vertices in the two graphs. We thus get two copies of the original graph, and the copies are linked by $|V|$ special edges between the two copies of the same vertex.  Call these new edges the 'copy' edges.

$|V|$ vertices are added to the graph and connect in a chain with $|V|-1$ new special (weight) 0 edges. Another special (weight 0) edge is added to connect the end vertex to $s$.  Call these new edges the 'chain' edges.

Partition the $2|V|$ new edges into $|V|$ edge sets that each consist of one copy edge and one chain edge.

We now try to find a shortest path between the start of the chain and vertex $t$ that satisfies your requirement of traversing either all or none of the edges from each edge set.
Such a path must start by traversing the full chain, so it must contain all chain edges, so it must contain all copy edges, so it must visit every vertex of the original graph; therefore, omitting all special edges from it will produce a Hamiltonian path from $s$ to $t$, if one exists.

Deciding whether a Hamiltonian path between arbitrary edges $s$ and $t$ exists is known to be $NP$-complete, so your problem is $NP$-hard: if you can find a polynomial algorithm for it (such as Dijkstra's), you will have proved $P=NP$.


Performant algorithm to find edges without cross overs I have a series of graphs with points plotted like this:

Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don't know the starting position sometimes this can result in crossed paths.

I could resolve this with more costly algorithms like 2-opt, but because this is being used in real time graphics it isn't quite performant enough.

It might help to know all of these graphs are mapping slightly deformed ovals and so they will have no intrusions. I basically need something that would act as if a rubber band was placed over the points on a graph.

I feel there's probably a better way to do this rather than relying on generic path optimisation algorithms?

As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).


Literature on network-flow (optimization) approximation algorithms I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.

However, I have been looking in several well-known algorithm books but, I haven't yet found something. Most books don't go beyond Ford-Fulkerson and/or Edmond-Karp in respect to network-flow problems, and the sections explaining approximation algorithms discuss some algorithms not relating to network-flow optimization.

Could someone point me towards appropriate literature? I prefer books instead of papers.

In his FOCS2013 (Best Paper award) work, Aleksander Mądry gives a $\widetilde O(m^{\frac{10}{7}})$-time for exact max-flow and gives a nice survey on the existing techniques (including near-linear time for $(1+\epsilon)$-approximation in undirected graphs).


LL(1) parsing table construction i have the following CFG

E -> ABC
A-> a|Cb|epsilon
B-> c|xA|epsilon
C-> y|z

and the First of the Non-Terminal :

First(E) = {a,y,z,epsilon}
Frist(A) = { a,y,z,epsilon}
First(B) = { c,x,epsilon }
First(C) = {y,z}

the follow of Non-Terminal :

follow(E)={$}
follow(A)={c,x,y,z}
follow(B)={y,z}
follow(C)={b,$}

my problem is how to construct the parsing table , i constructed the table and i got the following , but i think there is something missing/mistake in the table

    x    a    b    c    y    z    $
------------------------------------
E       ABC            ABC  ABC  epsilon
A eps.   a        eps. Cb   Cb
B  xA              c   eps.  eps.
C                       y     z

i hope the table is clear ,

Note : in the row A i got epsilon with both Cb in y And Cb in z , but i did not write it in the table , is that mean the grammer is not LL(1) ??

thank you!

Let's start with the general case.
Given a production of a grammar, let's say A -> α where α is a general string, to compute the LL(1) parsing table T the algorithm says:

foreach(A -> α in the grammar):
  write A -> α in T[A,b], ∀  b ∈ first(α);
  if ( ℇ ∈ first(α) ):
     write A -> α in T[A,x], ∀ x ∈ follow(A);

If at the end of the algorithm you have any cell in the table T with more than one entry then the grammar is not LL(1), as in your case.
To run this algorithm you need to compute the set of firsts and follow of a symbol. I see you did right the follows sets, but you mistake in the firsts set of E. So here is the algorithm to compute the firsts set of a symbol X:

if(X is a terminal symbol):
  first(X) = X;
  break;
if (X -> ℇ ∈ productions of the grammar):
  first(X).add({ ℇ });
foreach(X -> Y1....Yn ∈ productions of the grammar):
  j = 1;
  while (j <= n):
    first(X).add({ b }), ∀ b ∈ first(Yj) ;
    if ( ℇ ∈ first(Yj)):
       j ++;
    else:
       break;
if(j = n+1):
  first(X).add({ ℇ });

So going back to your example:

First(E) = {a,y,z,c,x}

and in the table:

T[E,$] = E -> ABC


What is a naive method? I was researching dynamic programming and read the following:

  Often when using a more naive method, many of the subproblems are
  generated and solved many times.

What is a naive method?

It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact".

For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$, then a "naive" implementation would be

def Fib(n):
  if n <= 1:
    return 1
  else:
    return Fib(n-1) + Fib(n-2)

What's the problem? That if we call, say, Fib(7), then we end up making many of the same calls over and over, such as Fib(4) (because Fib(7) calls Fib(6) and Fib(5), and Fib(6) calls Fib(5) and Fib(4), and both times we call Fib(5) it calls Fib(4) and Fib(3), and so on).

So here a more a more "sophisticated", as opposed to naive, solution would be like dynamic programming and avoid all the extras computations.


Closure properties of Alternating Circuit 1 level Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.
Is this class closed under Kleene star?
I thought it would be simple since it is easy to check every subword (using a polynomial number of gates), but the part where I have to check every partition makes the circuit linear in depth.

Denote your language by $L$. Let the input be $x_1,\ldots,x_n$. Let $f(i,j,\ell)$ be true if $x_1,\ldots,x_j \in L^\ell$. The output will be
$$
\bigvee_{\ell=1}^n f(1,n,\ell).
$$
When $\ell = 1$, there is an $\mathsf{AC^1}$ circuits for $f(i,j,\ell)$. When $\ell > 1$, we use the formula
$$
f(i,j,\ell) = \bigvee_{k=i}^{j-1} (f(i,k,\lfloor \ell/2 \rfloor) \land f(k+1,j,\lceil\ell/2\rceil)).
$$
The resulting circuit is still $\mathsf{AC^1}$, since there are only $O(\log n)$ levels of recursion.
A different way of looking at this construction is to notice that for inputs of length $L$, we can replace $L^*$ with $L \cup \cdots \cup L^n$; and that $L^m$ can be computed in $O(\log m)$ steps using repeated squaring.


Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree I have homework from recursion tree and despite my search for hours I could not find the answer to this problem.

I appreciate if you can help.

  Draw a recursion tree and give a tight asymptotic bound on the solution of the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$. You need not prove your answer.

I don't know what a recursion tree is, but I know how to expand a formula:
$$
\begin{align*}
T(n) &= 2^{n/2} T(n/2) + 2^n \\ &=
2^{n/2} (2^{n/4}T(n/4) + 2^{n/2}) + 2^n \\ &=
2^{(3/4)n} T(n/4) + 2^n + 2^n \\ &=
2^{(3/4)n} (2^{n/8} T(n/8) + 2^{n/4}) + 2^n + 2^n \\ &=
2^{(7/8)n} T(n/8) + 2^n + 2^n + 2^n \\ &= \cdots
\end{align*}
$$
You take it from here, along the following lines:

Assume that $n$ is a power of $2$. How many times do we need to apply the recurrence identity until we get to $T(1)$? (Above I applied it three times and got down to $T(n/8)$.)
When we do get to $T(1)$, what are we left with? (When we get down to $T(n/8)$, we are left with $2^{(7/8)n} T(n/8) + 3\cdot 2^n$.)
Suppose that $T(1) = C$. Can you come up with a formula for $T(n)$? Can you deduce a tight asymptotic bound?


Can a dynamic language like Ruby/Python reach C/C++ like performance? I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, compiling Ruby code can't ever be efficient because the way Ruby handles reflection, features such as automatic type conversion from integer to big integer, and lack of static typing makes building an efficient compiler for Ruby extremely difficult.

Is it possible to build a compiler that can compile Ruby or any other dynamic languages to a binary that performs very closely to C/C++? Is there a fundamental reason why JIT compilers, such as PyPy/Rubinius will eventually or will never match C/C++ in performance?

Note: I do understand that “performance” can be vague, so to clear that up, I meant, if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y? Where X is everything from device drivers and OS code, to web applications.

To all those who said “yes” I’ll offer a counter-point that the answer is “no”, by design. Those languages will never be able to match the performance of statically compiled languages.

Kos offered the (very valid) point that dynamic languages have more information about the system at runtime which can be used to optimise code.

However, there‘s another side of the coin: this additional information needs to be kept track of. On modern architectures, this is a performance killer.

William Edwards offers a nice overview of the argument.

In particular, the optimisations mentioned by Kos can’t be applied beyond a very limited scope unless you limit the expressive power of your languages quite drastically, as mentioned by Devin. This is of course a viable trade-off but for the sake of the discussion, you then end up with a static language, not a dynamic one. Those languages differ fundamentally from Python or Ruby as most people would understand them.

William cites some interesting IBM slides:

  Every variable can be dynamically-typed: Need type checks
  Every statement can potentially throw exceptions due to type mismatch and so on: Need exception checks
  Every field and symbol can be added, deleted, and changed at runtime: Need access checks
  The type of every object and its class hierarchy can be changed at runtime: Need class hierarchy checks

Some of those checks can be eliminated after analysis (N.B.: this analysis also takes time – at runtime).

Furthermore, Kos argues that dynamic languages could even surpass C++ performance. The JIT can indeed analyse the program’s behaviour and apply suitable optimisations.

But C++ compilers can do the same! Modern compilers offer so-called profile-guided optimisation which, if they are given suitable input, can model program runtime behaviour and apply the same optimisations that a JIT would apply.

Of course, this all hinges on the existence of realistic training data and furthermore the program cannot adapt its runtime characteristics if the usage pattern changes mid-run. JITs can theoretically handle this. I’d be interested to see how this fares in practice, since, in order to switch optimisations, the JIT would continually have to collect usage data which once again slows down execution.

In summary, I’m not convinced that runtime hot-spot optimisations outweigh the overhead of tracking runtime information in the long run, compared to static analysis and optimisation.


Randomly built binary search trees In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:

  The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.

We define "randomly built binary search tree on $n$ keys" as:

  a binary search tree that arises from inserting the keys in random order into an initially empty tree, where each of the $n!$ permutations of the input keys is equally likely.

In the proof, we defined some random variables:

Let $X_n$ denotes the height of a randomly built binary search tree on $n$ keys and the exponential height $Y_n = 2^{X_n}$. Of the $n$ keys, we choose one key as the root of the tree, and we let $R_n$ denotes the random variable that holds the position that this key would occupy if the set of keys were sorted (also know as 'rank' in the text). If we know that $R_n=i$, it follows that $Y_n=2\cdot max(Y_{i-1},Y_{n-1})$.

We also define indicator random variables $Z_{n,1}, Z_{n,2}, ..., Z_{n,n}$, $Z_{n,i} = I\{R_n=i\}$.

  \begin{equation}
\begin{split}
E[Y_n] & = E\Big[\sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))\Big] \\
& = \sum_{i=1}^{n} E[Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by linearity of expectation)}\\
& = \sum_{i=1}^{n} E[Z_{n,i}] E[(2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by independence)}\\
\end{split}
\end{equation}

I would like to ask why is the last equality correct? In other words, why can we assume independence of $Z_{n,i}$ and $max(Y_{i-1},Y_{n-i})$?

In the proof, there was a brief explanation:

  Having chosen $R_n = i$, the left subtree (whose ranks are less than $i$. This subtree is just like any other randomly built binary search tree on $i-1$ keys. Other than the number of keys it contains, this subtree's structure is not affected at all by the choice of $R_n=i$, and hence the random variables $Y_{i-1}$ and $Z_{n,i}$ are independent. Likewise, the right subtree, whose exponential height is $Y_{n-i}$, is randomly built on the $n-i$ keys whose ranks are greater than $i$.

However, since $R_n$ does affect the number of keys $Y_{i-1}$ and $Y_{n-i}$ contain (as acknowledged by the explanation above), wouldn't it mean that  $Y_{i-1}$ and $Y_{n-i}$ are dependent on $Z_{n,i}$?

A note regarding similar questions posted on CS stackexchange

I have read the answers for the following questions which are very similar to mine:

Proof that a randomly built binary search tree has logarithmic height
Average height of a BST with n Nodes.
Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

For 1 & 2, the question was a more general one which asked for an explanation for the entire proof. Also, the answer for both questions did not attempt to justify the independence and simply used the result.

For 3, the question was based on a MIT lecture, https://www.youtube.com/watch?v=vgELyZ9LXX4 and it lacked some of the details which I have included above. Also, the answer was also not clear.

Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$.

Here is what I got wrong:

From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$,  I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes the indicator random variable for the event that the rank of the root node is $i$.  $Y_{i-1}, Y_{i-1}$ denotes the exponential height of a randomly built binary search tree with $i$ elements and $i-1$ elements respectively. In this case, since $Z_{n,i}, Y_{i-1}, Y_{i-1}$ all dependent on this random variable $i$, I assumed that they must be dependent (through $i$).

Here is how I should have seen the equation above. By expanding out the summation:
$$Y_n = Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1})) + Z_{n,2} (2\cdot max(Y_{2-1}, Y_{n-2})) + ... + Z_{n,n} (2\cdot max(Y_{n-1}, Y_{n-n}))$$

Thus, $i$ is just a variable and should not affect the independence between the pair $Y_{i-1},Y_{n-i}$ and $Z_{n,i}$. For instance in the first term $Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1}))$, $Z_{n,1}$ denotes the indicator random variable for the event that the rank of the root node is 1. On the other hand, $Y_{1-1}, Y_{n-1}$ denotes the exponential height of a randomly built binary search tree with $0$ elements and $n-1$ elements respectively. Thus, from the definition alone, it should be clear that the pair $Y_{i-1},Y_{n-i}$ should not depend on $Z_{n,i}$.


Is there an algorithm that can solve chess within the span of a human lifetime? According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree:

  A machine... would require over $10^{90}$ years to calculate the first move!

But his paper ends with a section entitled "Another Type of Strategy" and provides vague guidance on other options to solve chess.

Can it be proven whether chess can or cannot be solved with some algorithm (other than brute force) within some defined amount of time (for example, 100 years)?

You can't prove that chess can't be solved with less than 100 years time because you don't know what computers will be developed during that time. The only limits on computational speed we know are pretty ridiculous compared to what we can do today.

You might be able to prove that solving chess needs at least X many operations, but I don't know of any such results.


Group values up to a threshold and minimize groups Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$
Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups.

Example: $N={20,19,18,17,14,12,9,5,4}$ and $t = 40$

Possible Grouping: ${(20,19),(18,17,4),(14,12,9,5)}$ (Greedy)

Is greedy a strategy/algorithm, that will lead to the optimal solution? If not, are there other algorithms to solve this problem?

I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.


What Is The Complexity of Implementing a Particle Filter? In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations.  Is this correct?  Could someone explain this?

It appears that the speaker feels that there isn't a definitive complexity analysis yet for the technique. This could be due to a couple of factors.

The analysis is hard, and no one has figured it out yet.
The technique has multiple different appropriate implementations, based on the problem context.

I'd bet on the second option, particularly in light of the speaker's comment that the technique may not be appropriate for higher dimension parameter spaces. Keep in mind that the video did not present an algorithm, it presented a very high-level discussion of a technique.


NOT satisfiable 3SAT instance certificate Given a NOT satisfiable 3SAT instance, that we say $S$. Suppose that $M$ is a minimal subset of clauses of $S$ such that $M$ is NOT satisfiable. Say $X$ the subset of variables of $S$ that belong to the clause of $M$. For each Boolean values combination of the variables of $X$, we have a clause of $M$ that is false, because $M$ is NOT satisfiable.
The question is: is $M$ a polynomial certificate that $S$ is NOT satisfiable? I mean: if we have $M$, we can check that, for each possible Boolean value of the variables that are in $X$, there is a false clause in $M$. This means that $M$ is a certificate that $S$ is NOT satisfiable. Because each clause is false for only one Boolean value of the variables that are in the clause and becasue $M$ is minimal, the number of cases, that we have to check to verify that $M$ is NOT satisfiable, is the cardinality of $M$ (i.e. the number of clauses in $M$). Threfore the complexity of the certificate is linear on the number of clauses of $M$ (therefore linear on the number of clauses of $S$).
Here an example.
If $X=\left\{a,b,c\right\}$, $M$ contains all possibile combinations, three by three, of $\left\{a,b,c,\bar{a},\bar{b},\bar{c}\right\}$ ($9$ literals in all), without that a variable and its negation appear in the same clause (it would be a tautology). Therefore the number of clauses of $M$ is exponential on the number of the variables of $X$, but the number of clauses of $M$ is at most the number of clauses of $S$. In other word we have $cardinality(X)=O(\log(numberClauses(S)))$.

A CNF which is not satisfiable is usually called unsatisfiable. A CNF which is unsatisfiable but becomes satisfiable if we drop any clause is minimally unsatisfiable.
Papadimitrious and Wolfe constructed, in their paper The complexity of facets resolved (Lemma 1), a polynomial time reduction $f$ from CNFs to CNFs such that:

If $\varphi$ is satisfiable then $f(\varphi)$ is satisfiable.
If $\varphi$ is unsatisfiable then $f(\varphi)$ is minimally unsatisfiable.

It is likely that this can be extended to a reduction from 3CNFs to 3CNFs.
This reduction shows that the minimally unsatisfiable case is the "hardest". In particular, if there is an efficient way to check that a minimally unsatisfiable CNF is unsatisfiable, then P=NP.


Is there an algorithm that given a PDA $M$ decides if there exists a string in $L(M)$ with a suitable decomposition? I am looking for an algorithm that given a PDA $M$ decides whether there exists $w \in L(M)$ for which there exists a decomposition $w = uvxyz$ that satisfies $|vy| \geq 1$ and $uv^ixy^iz \in L(M)$ for every $i \geq 0$.

In a context-free language $L$, by the Pumping Lemma, there exists a $p > 0$ such that every $w \in L$ such that $|w| \ge p$ admits a decomposition $w = uvxyz$ such that $uv^ixy^iz \in L$ for all $i \geq 0$.

If $L$ is infinite, it has words of length $\ge p$, and you can pick any of them. If $L$ is finite then no word satisfies the condition (this is not a contradiction with the pumping lemma, because the pumping lemma gives a length $p$ which is more than the length of any of the words in $L$).

It is decidable if a context-free grammar generates an infinite language (see e.g. Is it decidable whether a given context free grammar generates an infinite number of strings?).

Therefore the algorithm is

  On input $\langle M \rangle$, where $M$ is a PDA

  Convert $\langle M \rangle$ to the description of an equivalent CFG $\langle G \rangle $
  Check if $L(G)$ is infinite
  If yes, then answer yes else answer no


Single-source shortest path problem with diameter Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and design an algorithm runs in O(V+E+D) time.

As we know, in a single-source shortest path problem, we could use the Dijkstra Algorithm and it's running time is $O((V+E)log V)$ using a min-heap. So we can explore the minimum known distance. But the bottleneck is to insert and delete a min-heap structure.
With the information, how to reduce the running time to $O(V+E+D)$?
**Update **
From https://stackoverflow.com/questions/66570124/single-source-shortest-path-in-a-graph-with-positive-weights-and-diameter-d

We continually increment i until we find some i such that Arr[i] is not empty.

This tells where does the $O(D)$ come from. But what I don't understand is why inserting and deleting take a constant amount of time if min-heap is still using. Or is it another data structure? Many thanks

Instead of a min-heap use an array of $D +2$ lists indexed from 0 to $D+1$. The $i$th list contain vertices whose distance to the source equals $i$ except for the last one which contains vertices with unbounded distance.
Iterate over this array from $0$ to $D$ and for each list, while not empty choose the head of the list as the vertex whose incident edges are to be relaxed in this iteration (the vertex with min distance to the source) and remove this element from this list.
To ensure updates add an array of $n$ pointers such that each vertex points to its occurance in the lists .
It is easy to see that updates run in constant time, hence we get $O(m)$ for updates over all edges. Since we iterate over empty lists and each vertex only once in the array we have amortized running time $O(n+m)$ for iterations.


Complexity of domino tiling with dominoes placed in a line Let's say I have a bunch of cards or dominoes with one color on the left side of the
card and another color on the right. (The two colors could be the same.)
Dominoes can't be rotated so the color on each side is fixed. There is no
limit on the number of colors and colors can be repeated on cards.

Dominoes are placed in a line, one after another.

The rule is, the color on the right hand side of a domino must match the
color on the left hand side of the domino placed next to it.

The problem is, given a pool of dominoes, is it possible to put all of the
dominoes in a line while following the rule? (I believe this is the same
problem as given a group of matrices is it possible to multiply them all
together.)

So for example given these dominoes: R-R, R-B, G-Y, GG-Y, Y-GG, R-R, R-B,
..., R-B, B-R, P-G is it possible to form a straight line with all
adjoining sides having the same color.

My real question is this: Is the complexity of this problem (determining
if it is possible to put all N dominoes in a line) NP?

This is just the Eulerian path problem on a multigraph. The colors are the vertices, and the dominos are the edges. You want to know whether there is a path that goes passes through each edge exactly once. It's polynomial time, and you should be able to find the algorithm by googling "Eulerian path".


How do you describe a language that is generated by Context Free Grammer I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ?

this is the CFG I am trying to describe

S -> SS
S -> XXX
X -> aX| Xa| b

I was thinking something like this

S-> SS
  ->XXXS
  ->aXXXs
  ->abXXS
  ->abXXS
  ->abXAXS
  ->abbaXS
  ->abbabS
  ->abbabS
  ->abbabXXX
  ->abbabbXX
  ->abbabbbX
  ->abbabbbb
  ->abbabbbb

Hint: How many $b$s are there in each word generated by this grammar?

Guidance: What is the language generated by $X$? What is the language generated by $XXX$? What is the language generated by $S$?


How to create a subset with a given length and mean? I have a set of numbers $P=\{p_1,\dotsc,p_{|P|}\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\mu_s$ .
$$\sum_{x \in S} x \approx \mu_s * |S|$$
My problem:

$|P|$ = 5000
$|S|$ = 1500
$\mu_s$ $\approx$ 90 $(target$ $mean)$
$\mu_p$ = 95
$min(P)$ = 0
$max(P)$ = 300

I am looking for algorithm suggestions so I can implement this in Python. I would also like $S$ to include a range of values, rather than just the naive approach of sorting from smallest to largest first, then applying a greedy algorithm.
Additional question is whether dynamic programming could be used for this type of problem (i.e. we have to select a certain number of items from a list such that the sum is as close as possible to the capacity limit)?

For every $i \in \{0,\ldots,|P|\}$, $j \in \{0,\ldots,|S|\}$, and $T \in \{0,\ldots,\mathcal{T}\}$ (I discuss $\mathcal{T}$ below), compute whether there is a subset of size $j$ of $p_1,\ldots,p_i$ which sums to $T$. You should take $\mathcal{T}$ to be your maximum allowable answer – $\max(P) \cdot |S|$ would definitely do, but you can probably pick something which is closer to $\mu_S |S|$, say $\mu_P |S|$. The running time is $O(|P| |S| \mathcal{T})$. In your case, assuming you choose $\mathcal{T} \approx \mu_p |S|$, then $|P| |S| \mathcal{T} \approx 2^{40}$, so this is barely feasible.
This is a naive dynamic programming algorithm, which probably can be improved, especially since you're only looking for an approximation.
For example, you could only look for solutions such that $S \cap \{0,\ldots,i\} \approx \frac{|S|}{|P|} i$ and $\sum(S \cap \{0,\ldots,i\}) \approx \frac{|S|}{|P|} \mu_S$, which will reduce the running time significantly. While this is only a heuristic, it might be possible to show that you get a decent approximation on average, if you randomize the order of $P$.
Another possible optimization is to quantize the partial sums, quantizing more aggressively as $i$ gets larger. If done carefully, you won't lose much in accuracy but will have a significant gain in running time.


How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method The guess solution to the

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

is $\Theta(n \log{\log n})$. This is my solution:
$$
T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} + \frac{n}{\log n} \\
\leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
\leq cn \log{\log {n}} + \frac{n}{\log n}
$$

that fails to for the $T(n) \leq cn \log{\log {n}}$

Now I try to solve the $T(n) \leq c(\log \log n - \frac{n}{\log n})$, we have
$$
T(n) \leq 2c\left(\left(\frac{n}{2}\right) \log \log {\frac{n}{2}} - \frac{\frac{n}{2}}{\log {\frac{n}{2}}}\right) + \frac{n}{\log n}\\
\leq cn \log \log {\frac{n}{2}} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\
\leq cn \log \log {n} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\
$$
and it will never be $\leq cn \log \log {n} - \dfrac{n}{\log n}$

How can I solve the recurrence?

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):

$$
\begin{align}
T(n) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\
& = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\
& = n \left[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right]\\
& = n \sum_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\
& = n \cdot H_{\log n}\\
\end{align}
$$

Where $H_n$ is the $n$th Harmonic number. It's known that $H_n = \Theta(\log n)$.

We can thus conclude
$$T(n) = \Theta( n \log \log n )$$

Now with this being said; I believe this issue in your logic is the following steps:
$$
\begin{align}
T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
& \leq cn \log{\log {n}} + \frac{n}{\log n}
\end{align}
$$
The jump from step 1 to step 2, while not incorrect, is not tight. Which is why you're not meeting the necessary conclusion. It should be something like:
$$
\begin{align}
T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
& \leq cn \left[\log \log \frac{n}{2} + \frac{1}{\log n}\right]
\end{align}
$$
It can then be proven by induction that:

$$\log_2 \log_2 \frac{n}{2} + \frac{1}{\log_2 n} < \log_2 \log_2 n$$

For $n > 2$. The proof is pretty straightforward and I'll leave it as an exercise for the reader, but it then follows that:

$$
T(n)  \leq cn \log\log n
$$


Algorithm to count the number of subsets of size k with sum of all its elements minimum possible An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:-
122
122
122
222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < \cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + \cdots + n_{d-1} < k$ but $n_1 + \cdots + n_d \geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,\ldots,a_{d-1}$, and any $k-(n_1+\cdots+n_{d-1})$ elements of value $a_d$. You take it from here.


Nim Games: Is it possible to reduce following using Grundy Number? Following is the problem from a finished programming contest.

  Two players try to create a number, DesiredTotal, by adding numbers
  from 1 to N. The first to cross the number is the winner. The number to be
  added cannot be repeated. For example, if one player used 4 to increase the sum from
  20 to 24, the neither player can use 4 again in the game.

Now I understand how the above problem could be solved using dynamic programming by exploring all the possible paths and memoizing the solution, but the game being impartial still qualifies to be a Nim game.

Am I correct that, it is a Nim game? If yes, could somebody help me to reduce into a Nim game?

Below is the source but it requires signing in.

Theory: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Source: https://leetcode.com/contest/leetcode-weekly-contest-10/problems/can-i-win/

Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the sum as well as the current set of allowed addends. You can compute the Grundy function, which gives the equivalence to Nim, using dynamic programming.


Decidablity of Languages of Grammars and Automata Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.
Here are the two questions I'm looking at from a past exam.  They seem to be related, the first:

Let
$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \} $
Prove that $\mathrm{FINITE}_{\mathrm{CFG}}$ is a decidable language.

and...

Let
$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$
Prove that $\mathrm{FINITE}_{\mathrm{TM}}$ is an undecidable language.

I am a bit lost on how to tackle these problems, but I have a few insights which I think may be in the right direction.  The first thing is that I am aware of is that the language $A_{\mathrm{REX}}$, where

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

is a decidable language (proof is in Michael Sipser's Theory of Computation, pg. 168).  The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.  Thus $A_{\mathrm{CFG}}$, must also be decidable as it can be converted to a regular expression.  This, and the fact that $A_{\mathrm{TM}}$ is un-decidable, seems to be related to this problem.
The only thing I can think of is passing G to Turing machines for $A_{\mathrm{REX}}$ (after converting G to a regular expression) and $A_{\mathrm{TM}}$.  Then accepting if G does and rejecting if G doesn't.  As $A_{\mathrm{TM}}$ is undecidable, this will never happen.  Somehow I feel like I'm making a mistake here, but I'm not sure of what it is.  Could someone please lend me a hand here?

Convert G to Chomsky Normal form. This way, the only empty derivation would be the start symbol that does not appears anywhere else and thus if there is some production that may able to eventually generate itself, then the grammar is infinite. If no such production exists, each symbol will only be able to generate a finite set of strings, and then the grammar is finite. So, build a directed graph where each production is a node and each symbol inside a production is an edge targeting that symbol. If the graph has some cycle, the CFG is infinite, otherwise it is not. Hence a Turing machine for $FINITE_{CFG}$ could be construct doing exactly that, and then $FINITE_{CFG}$ is decidable.
Suppose that $FINITE_{TM}$ is decidable. Lets say that $H$ is a Turing machine that has some string as input and uses itself as an input to $FINITE_{TM}$. If $FINITE_{TM}$ returns true (i.e, $H$ accepts only a finite language), then $H$ accepts the input, which leads to a contradiction since the input set is infinite (the input's length is unbounded, so accept any possible string as input means accepting an infinite set of strings). If $FINITE_{TM}$ returns false (i.e $H$'s language is infinite), then $H$ rejects the input, meaning that $H$'s language is finite because it does not accepts any input (i.e. its language is empty), which leads to a contradiction too. This way, the supposition that $H$ exists leads to contradiction, and this supposition is based in the supposition that $FINITE_{TM}$ is decidable. So, by contradiction, we have that $FINITE_{TM}$ is not decidable.

  The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.

I really doubt that Sipser would state that, you probably misread or misunderstood. This would mean that context-free grammars generate exactly the same langauges as right-linear grammars. This is false; the right-linear grammars generate are a proper subset of the languages context-free grammars dp. That said, the way you tried to use regular languages to answer the questions just leads you to nowhere.

As you can see above in my proofs, the two questions are indeed two very distinct, unrelated questions. It just happens that they were worded similarly.


Is modulus capable of universal computation? I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers?

It was a long while ago though and don't remember where I heard it.

Is this true or does it ring any bells?

You have to distinguish between two meanings of computation:

Computation of functions on a finite domain (e.g. circuits).
Computation of functions on an infinite domain (e.g. Turing machines).

A single division operation cannot be universal in terms of the second meaning, since division is total: it always halts (even division by zero halts). However, it could possibly be universal in terms of the first meaning. For example, if we encode the input using different primes, then the Chinese Remainder Theorem shows that $x \mapsto n \pmod{x}$ is universal, that is, for every Boolean function $f$ on some set $S$ of finite primes there is a number $n$ such that for every $x \in S$, $n \mod{x} = f(x)$.


What algorithm would compute the maximum choices from two sets? Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two vectors with extra zeros inserted into the shorter vector to make up for the size difference?

For example, consider the following two vectors as inputs:

[8 1 4 5]
[7 3 6]

The choices for inserting the zero and the resulting sum are:

[0 7 3 6]  => Maximums: [8 7 4 6]  =>  Sum is: 25
[7 0 3 6]  => Maximums: [8 1 4 6]  =>  Sum is: 19
[7 3 0 6]  => Maximums: [8 3 4 6]  =>  Sum is: 21
[7 3 6 0]  => Maximums: [8 3 6 5]  =>  Sum is: 22

Therefore, in this case, the algorithm should return 25.

I could do this by brute force by calculating for all permutations of placing zeros into the smaller vector (as just done above) but this would be computationally expensive, and worst in the case when one vector is exactly half the size of the other.

Is there a way to compute the answer in linear time proportional to the length of the longer vector even when the vectors differ in length?  If not, can we do better than the number of factorial permutations being chosen?

Hint: Use dynamic programming. For each $z,l$, compute the optimal way to insert $z$ zeroes to the prefix of length $l$ of the smaller array.


What kind of language does the following DFA accept? can anyone please describe the language this FA accepts? thank you

It accept all the words containing $i$ "a"s and $j$ "b"s for which $i \equiv j \pmod{4}$.


What algorithm may be used to solve the re-assembly of shredded papers? I was once given this question in an interview:

  Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so each piece can show a series of alphabets going down vertically), and there are 300 pages of such paper shredded total. Assume they are just English words with no proper names (for people / places). Find a method to reassemble all the papers and give the O() complexity time and space.

I proposed a solution where we take one piece of stripe, and go down the row to match for consecutive occurring alphabets, for a proper stripe. So we would build up a dictionary of all English words, for example, for the word Apple, that will mean ap, pp, pl, and le are all valid. And if we go down both stripes, we should expect most (or all) of them match with each other if they were adjacent.

But doing this way, it looks like it would be (180 * 300)! = 24000! (factorial) steps, before we can finish the task? I can only find a complicated paper about re-constructing non-fixed size font paper (and it seemed way too complicated for a 20 minute interview question), and another paper that is not public.  Is there a good solution to this problem?

(Actually, it seems that if it is not fixed size font, it is a easier problem?  Because we can just look at the left and right edge: along the left edge, for example, if there is ink, we call it as 1, and no ink, we call it a 0. Or we can just scan and collect data: from top edge, go down 3.232cm of blank space, and then 0.012cm of ink, and then 0.027cm of blank space, all the way down to the end of paper, and then we can create a signature.  If we do the signature for all 80 x 300 stripes, now we have 48000 signatures. Now we can actually just match the signatures up to tell which strips is adjacent to which stripe. So that would be a linear O(n) solution?)

If the cuts are in the middle of letters, then I think your solution in the last paragraph is a good one.

If the cuts go between letters, then I think your approach of finding pairs of strips of papers is a good one.  I would start by finding all pairs of strips that could have been adjacent, based on which digraphs (pairs of characters) can appear in some word.  Then, I would try to extend to find all triples of strips that could have been adjacent: for each possible pair of adjacent strips $s_1,s_2$, find all $s_3$ such that $s_2,s_3$ is a pair of possible adjacent strips; then test whether if you past together $s_1,s_2,s_3$ that all trigraphs (triples of characters) can appear in some word.  Then, I would extend to 4-tuples of strips, filtering them based on 4-graphs of characters, and so on.  The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good.

For fun, you might enjoy reading about the DARPA shredding challenge (summary on Wikipedia).