Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $n/2$ numbers left, then combine them so that $n/4$ numbers are left and so on until a single number, the result, is left which happens after $\lceil \log n \rceil$ steps.  With this is it obvious that we can compute the matrix product of two $n \times n$ matrices $A = (A_{ij}), B = (B_{ij})$ with $n^3$ processors in $\log n + 1$ steps, in a first step compute all the $n^3$ products of the entries $A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,\ldots, n\}$. Then with $n^2$ processors compute the $n^2$ sums of the $n$ numbers $A_{i1}\cdot B_{1j} + \ldots + A_{ik}\cdot B_{kj}$. Hence we get by with $1 + \log n$ parallel steps.

Now the following argument is from C. Papadimitriou, Computational Complexity, page 361, to show that we get time $2\log n$ using just $n^2 / \log n$ processors (the argument used is called Brent's principle according to the book).

  We compute the $n^3$ products not in a single step as before, but rather in $\log n$ ''shifts'' using $\lceil n^3 / \log \rceil$ processors at each shift. We use shifts of the same $\lceil n^3 / \log n \rceil$ processors to compute the first $\log \log n$ parallel addition steps, where more than $\frac{n^3}{\log n}$ processors would be ordinary needed. The total number of parallel steps is now no more than $2\log n$, with $\frac{n^3}{\log n}$ processors [...].

(those arguments could also be found on these slides).

But I get more parallel steps as $2\log n$.

1) First we compute the $n^3$ products $A_{ik}\cdot B_{kj}$ with $\log n$ shifts, hence we need $\log n$ parallel steps for this.

2) If we combine the results as written in the introduction, then in the $k$-th step we have $n/2^k$ numbers to combine. Hence if $2^k < \log n$ we do not have enough processors to do this in a single step, hence we have to ''shift'' again, this time $\lceil \log n / 2^k \rceil$ times. If $2^k \ge \log n$ we can use a single parallel step as we have enough processors at hand.

Combining the above reasoning we get the following equation (I omit the rounding)
for the number of parallel steps:
$$
 \log n + \sum_{k=1}^{\log \log n} \frac{\log n}{2^k} + \log n - \log \log n.
$$
The first summand commes from the shift over the $n^3$ numbers, the second summand for the shifts needed if in the combination/summation of the product we still have to many numbers for our processors, and the last for the number of steps if we do have enough processors.
This equals
\begin{align*}
 & \log n + \log n \left( 1 - \frac{1}{2^{\log \log n}} \right) + \log n - \log \log n \\
 & = \log n + \log n - 1 + \log n - \log \log n \\
 & = 3 \log n - \log \log n - 1
\end{align*}
The last is in general more than $2\log n$, so what am I missing. Why does they argue they get by with $2\log n$ steps. Do I miss anything here?

Yes, you are correct while all textbooks and lecture notes you and I have found so far are wrong in claiming "doing matrix multiplication with $\lceil n^3 / \log n \rceil$  processors in  at most $2\log n$ steps by Brent's principle"
There is hardly anything valuable to add to your meticulous calculation. Anyway, here is an example that specializes your calculation.
An example
Let $n=16$. We have two $16\times16$ matrices, $(A_{ij})$ and $(B_{ij})$ with $\left\lceil \dfrac{n^3}{\log_2n}\right\rceil=\left\lceil\dfrac{16^3}{\log_2 16}\right\rceil=1024$ processors.
It takes 4 parallel steps to compute all the $n^3=4096$ products of the entries $P_{ijk}=A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,2,\cdots,16\}$ with $1024$ processors.
How to compute $n^2=256$ sums of the $n=16$ numbers $P_{i1j}+ \ldots + P_{i16j}$ for $i,j\in\{1,2,\cdots,16\}$?
We first compute $256\times 8=2024$ sums of two neighbors $S_{ikj}=P_{i(2k-1)j}+P_{i(2k)j}$ for $i,j\in\{1,2,\cdots,16\}$, $k\in\{1,2,\cdots, 8\}$. It takes 2 parallel steps for 1024 processors, where $2$ is $\dfrac{\dfrac{n^3}2}{\dfrac{n^3}{\log_2n}}=\dfrac{\log_2n}2>1$.
There are $256 \times 4 = 1024$, $256 \times 2 = 512$, $256 \times 1 = 256$ sums of two numbers to calculate, respectively. Each of them will take one parallel step because of the serial dependency. We need $3 =\log_2n-1$ parallel steps.
So we need $4 + 2 + 3 = 9$ parallel steps in total, which is bigger than $\lceil 2\log_2 n\rceil = 8$.
Corrected statement
Multiplication of two $n\times n$ matrices can be done in no more than $3\log_2 n+1$ parallel steps with $\lceil n^3 / \log_2 n \rceil$ processors by Brent's principle.
Brent's principle
Here is one version of Brent's principle that applies to current situation.
(Brent’s principle): An algorithm involving $t$ time steps and performing a total of $m$ operations can be executed by $p$ processors in no more than $t + \lceil(m – t) / p\rceil$ time steps in PRAM.
In particular, we have $m=n^3+ n^2(n-1)$ operations and $t=1+\lceil \log_2n\rceil$ time steps for matrix multiplication. If we have $p=\lceil n^3 / \log_2 n \rceil$ processors, the upper limit of parallel steps given by Brent's principle,  $t + \lceil(m – t) / p\rceil$ is $3\lceil\log_2 n\rceil-1$ or $3\lceil\log_2 n\rceil$  or $3\lceil\log_2 n\rceil+1$.


Assign m agents to N points by minimizing the total distance Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?

My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.

It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.

There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)

Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?
How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently? Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.
How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?


Is there a binary search tree datastructure which can avoid becoming badly weight-balanced? This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$

  Definition: For a rooted tree $T$ and a vertex $v \in V(T)$, let $L_T(v)$ be the number of nodes in the left-subtree from $v$, and $N_T(v)$ be the number of nodes in the subtree rooted at $v$. We say that $T$ is $\mu$-balanced, with $0 \le \mu \le \frac{1}{2}$, if for every node $v \in V(T)$ the inequality
  $$ \mu \le \frac{L_T(v) + 1}{N_T(v) + 1} \le 1 - \mu$$
  holds, and if $\mu$ is minimal subject to this inequality holding.

(These are apparently also known as  weight-balanced trees in some of the literature.) A tree which is $\mu'$-balanced for some $\mu' < \mu$, we will say is μ-imbalanced.

The above-linked posts essentially show that neither AVL trees, nor Red-Black trees, can be guaranteed to be $\mu$-balanced for any $\mu > 0$: that is, for any such $\mu$, one can provide a sequence of inputs to be inserted so that the resulting tree is $\mu$-imbalanced.

Question. Is there any binary search tree structure, with the usual characteristics of $O(\log n)$ insertion and search time, and some $m > 0$, such that the tree will always be $\mu$-balanced for some $\mu > m$?

Yes, I believe there is (though I don't remember the details of the paper to confirm).

This is the original paper which dealt with that:

  Nievergelt J. and Reingold E.M., "Binary search trees of bounded
  balance", Proceedings of the fourth annual ACM symposium on Theory of
  computing, pp 137--142, 1972

Here is a page on weight-balanced trees which seems to have some more information and mentions their usage in functional languages.

This paper: On Average number of rebalanced operations in weight balanced trees, seems to be investigating the number of rebalancing operations in weight balanced trees.

I also seem to remember that one Knuth's Art of ... books had a reference to the above Reingold paper (perhaps in the exercises).


Is there a low degree vertex in planar graphs? A book I read states "Since $G$ is planar, $G$ has a vertex $v$ of degree at most 5".

Is this true?
Why?
Does this theorem have a name?

Yes, this is true.
It is a direct consequence of Euler's formula. The formula entails that the average degree is strictly less than 6, which implies the existence of a vertex of degree at most 5.
It doesn't have a name in itself, but Euler's formula is the overall subject.


The number of executions of the count statement; how many? How many times does the statement count in line 5 executes in terms of $n$?

1.  count=0;
2.  for (i=1; i<=n; i++) {
3.  for (j=1; j<=n; j*=2) {
4.  for (k=1; k<=j; k++) {
5.        count = count + 1;
6.      }
7.    }
8.  }

For the loop in line 3, we can list the numbers for $j$ as, $2^0,2^1,...,2^{\log n}$
Therefore, we can refer to the iterations of the exponents as $r$. Doing so would lead to the summations below for counting the number of executions.

$\sum_{i=1}^{n}\sum_{r=0}^{\log n}\sum_{k=1}^{j}1 =\sum_{i=1}^{n}\sum_{r=0}^{\log n}j $

I am stuck here, because $\sum_{r=0}^{\log n}$ depends on $j$ but I am not sure how to incorporate them.

Thanks in advance.

Hint: Substitute $j = 2^r$, and use the formula for summing a geometric series.

Make sure that you understand why the substitution $j = 2^r$ makes sense.


In complexity theory, does polynomial time refer to the big-O notation? When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases?

For example; algorithm X runs in polynomial time.

Very rarely we measure the exact running times, and when we do, it's specified quite clearly.

Then, there is the big-O notation and its friends, which give information about the asymptotic behavior of the algorithm.

But different big-O sets (being pedant here, O(n) is actually a set of functions) can be grouped into classes. There are linear algorithms, which run in O(n). Then, there are sublinear algorithms (faster than O(n), such as O(logn)). Polynomial algorithms are quite important, and represent the algorithms with running times bounded by a polynom (e.g. O(n^k)). There are expone ntial algorithms, such as O(k^n), nonpolynomial algorithms, which grow faster than polynomial and include exponential, and so on.

All of these are simply a coarse categorization of the running time, which can be made by looking at the asymptotic behavior of the algorithm.


Turing Machine to return all prime numbers My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.

So no matter what the input is, we should ignore it. I think it would be sufficient to add another tape with cells $1^*,2,\dots,n$. Now, I would use Sieve of Eratosthenes algorithm as follows:

Move a head to the right until the head encounters an unmarked symbol.
Mark the symbol with a star and write it down to another write-only tape representing the output, i.e. the symbol is a prime number.
Now, for $n$ being prime, I am supposed to mark every $n$-th symbol with a star. I am not sure how to do it.
Reset.

For the third step, I think I should utilize another marking mechanism to denote a gap between the beginning and the prime resolved in that round. Then, I would be moving that "window" and whenever the beginning of the "window" would reach the prime, I would mark the symbol at the end of the "window" with a star. Not sure how to express this formally.

Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.

The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:

Start with $n=2$ - this is prime.
Set $j$ equal to $n$.
Add $1$ to $n$
Set $k$ equal to $n$.
Subtract $j$ from $k$.
If $k$ is greater than $0$ go to step $5$.
If $k$ equals $0$ then $n$ is not prime; go to step $2$.
Subtract $1$ from $j$.
If $j$ equals $1$ then $n$ is prime; go to step $2$.
Go to step $4$.


Showing that an algorithm is 2-approximation I'm having trouble showing that this algorithm is 2-approx.

  We are given a set P of n points on the plane, and a positive integer k. We want to
  partition these points into k sets such that the largest distance between any two points which
  belong to the same part is minimized. Show that the following is a 2-factor approximation
  algorithm.

  Set S = ∅.

  For i = 1, . . . , k do

  Select the farthest point from S and add it to S.

  EndFor

  Put each point p ∈ P in the same part as the closest point in S to p.

I honestly don't know where to start. I can see that after each iteration, the distance between any point in P and the points in S become smaller. But after that I can't really see any good observations.

The place to start is at the simplest case: $k = 2$. Suppose that the points in $S$ are $x,y$. Consider some optimal solution of value $1$. We consider two cases.

$x,y$ belong to the same cluster. Thus $d(x,y) \leq 1$. Since $y$ is the farthest point from $x$, all other points are at distance at most $1$ from $x$, and in particular at distance at most $1$ from $\{x,y\}$. This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base (either $x$ or $y$), and so the diameter of each cluster is at most $2$.
$x,y$ belong to different clusters. In this case, since the optimal solution has value $1$, each point other than $x,y$ is within distance $1$ of either $x$ or $y$ (the one which shares cluster with it). This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base, and so again the diameter of each cluster is at most $2$.

See if you can generalize these ideas for $k > 2$.


Find lines segment portions close together I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A_1$, $B_1$ and $A_2$, $B_2$ (see left part in the below schema).

I would a like to find an algorithm to detect which portion of the line segment 1 has a distance less than or equal to $x$ to the line segment 2 (and the opposite). The expected result of the algorithm is represented by the red lines in the schema:

Could you please provide me some tips & tricks? I do not know where to start. Thank you.

Here is a derivation that shows how to solve this problem, using a bit of vector arithmetic.

You can project a point $P$ onto the line $A_1B_1$ using vector arithmetic; in particular, the projection of $P$ is $${(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1) + A_1,$$ where $v^\top$ denotes the transpose of vector $v$, so the vector measuring the orthogonal distance from $A_1B_1$ to $P$ is

$$D=P-{(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1)  - A_1.$$

Every point $P$ on the line segment $A_2B_2$ has the form $P=\alpha A_2 + (1-\alpha)B_2$, for some $\alpha \in [0,1]$.  So, we can write $D$ in the form

$$
\begin{align*}
D=\;&\alpha A_2 + (1-\alpha)B_2 - A_1\\
 &- {(B_1-A_1)^\top (\alpha A_2 + (1-\alpha)B_2-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1).
\end{align*}
$$

Notice that this is a linear function of $\alpha$, when $A_1,B_1,A_2,B_2$ are fixed.

Let the $x,y$-coordinates of $D$ be $x_D,y_D$, i.e., $D=(x_D,y_D)$.  The above equation implies that there are constants $a_0,a_1,a_2,a_3$ such that

$$x_D=a_0 \alpha + a_1, y_D = a_2 \alpha + a_3.$$

The $a_0,\dots,a_3$ depend only on $A_1,A_2,B_1,B_2$ (but not on $\alpha$) and can be readily computed using the formula above.

Now we want this vector $D$ to be of length at most $\tau$, i.e., $\|D\|_2 \le \tau$.  In other words, we want

$$x_D^2 + y_D^2 \le \tau.$$

This is equivalent to

$$(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 \le \tau.$$

That is a quadratic in the unknown $\alpha$, so we can readily find the range of $\alpha$ where this inequality holds by using the quadratic formula (basically, find the roots of the quadratic equation $(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 = \tau$, and these are the endpoints of that range, except that you should clamp to the range $[0,1]$).  Say that the inequality holds for $\alpha$ in the range $[\alpha_\ell,\alpha_u]$.  Then it follows that the points on the line segment $A_3B_3$ are all of distance at most $\tau$ to the line $A_1B_1$, where $A_3 = \alpha_\ell A_2 + (1-\alpha_\ell) B_2$ and $B_3 = \alpha_u A_2 + (1-\alpha_u) B_2$.

This would describe how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line connecting $A_1$ and $B_1$.  However, we really want to find all points that are distance at most $\tau$ from the line segment $A_1B_1$.  So, we want to constrain the projection of $P$ to be between $A_1$ and $B_1$, i.e., we want to constrain $D$ to be between $0$ and $B_1-A_1$.  By solving systems of linear equations, you can find $\alpha_0$ such that $(a_0 \alpha_0+a_1,b_0 \alpha_0+b_1)=(0,0)$ and $(a_0 \alpha_1+a_1,b_0 \alpha_1+b_1)=B_1-A_1$.  Then, we replace $[\alpha_\ell,\alpha_u]$ (obtained above by the quadratic formula) with the intersection of ranges $[\alpha_\ell,\alpha_u] \cap [\alpha_0,\alpha_1]$.  This gives us all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $A_1B_1$.

This solves your question of how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $A_1B_1$.  You can repeat the same procedure a second time to find all points on the line segment $A_1B_1$ that are distance at most $\tau$ from $A_2B_2$.


3xN tiling problem with blocks of size 3x1 or 2x2 I know there are a number of different tiling problems and some of them have been discussed here:
Number of ways of tiling a 3*N board with 2*1 dominoes problem
Domino and Tromino Combined Tiling
DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?.
My domain has different requirements which are as below:
https://www.codingame.com/ide/puzzle/3n-tiling

Height will be 3,
tile sizes are: 2x2, 3x1, 1x3

there are possible choices for 3x6:

┌─────┬─────┐  ┌───┬───┬───┐  ┌─────┬─────┐  ┌─┬─┬─────┬─┐
├─────┼─────┤  │   │   │   │  ├───┬─┴─┬───┤  │ │ ├─────┤ │
├─────┼─────┤  ├───┴─┬─┴───┤  │   │   │   │  │ │ ├─────┤ │
└─────┴─────┘  └─────┴─────┘  └───┴───┴───┘  └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐  ┌─┬─┬─┬─────┐  ┌─────┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
└─┴─────┴─┴─┘  └─┴─┴─┴─────┘  └─────┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┘

(illustration copied from Codingame problem section).

I have come up with the following DP relation:

dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))

dp[i-1] means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.

┌─┐
│ │
│ │
└─┘

dp[i-3] means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.

┌─────┐
├─────┤
├─────┤
└─────┘

dp[i-6] means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).

┌───┬───┬───┐  ┌─────┬─────┐
│   │   │   │  ├───┬─┴─┬───┤
├───┴─┬─┴───┤  │   │   │   │
└─────┴─────┘  └───┴───┴───┘

But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154.
Any help is appreciated.

Edit:

After a lot of thoughts and getting some ideas from answers, I came up with this solutions (Image represents a top down DP approach)

Basically, based on the image,

To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1[n] = dpHeight1[n-3]
To get to 2xN state, we can either take 1 time 2x2 so dpHeight2[n] = dpHeight2[n-2] or we can take 2 times 1x3: dpHeight2[n] += dpHeight2[n-3]
to get to 3xN, we can either take 1 time 3x1, so dpHeight3[n] = dpHeight3[n-1] or we can take 3 time 1x3, dpHeight3[n] += dpHeight3[n-3] or take 1 time 2x2 and 1 time 1x3, exception here is we can take 1x3 first or after we take 2x2, but they both have same count, so: dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2)

And this the code:

dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3

for (int width=1; width <= n; width++) {
    //take out one 1x3
    dpHeight3[width] = (dpHeight3[width-1])%mod

    if width >= 2 {
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
    }

    if width >= 3 {
        //put 1 time 3x1
        dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod

        //put 2 vertically stacked 3x1
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod

        //take out 3 vertically stacked times 3x1
        dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod

        //take out 1 time 2x2 and put it on top of 1 time 3x1
        // or take out 1 time 3x1 and put it on top of 1 time 2x2
        dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
    }
}

But still not getting the result.

Here is a systematic way to approach it.  I suggest you define three values:

$A_0(n)$ is the number of ways to tile a $3 \times n$ region.

$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.

$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.

Then you should be able to express each $A_i(n)$ in terms of $A_j(m)$ for $m < n$.  This gives you a mutual recurrence relation for these three values.  It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.

You can then compute these using dynamic programming, in order of increasing $m$.  Or, you can substitute into each other and get a single recurrence relation for $A_0(n)$ in terms of $A_0(m)$ for $m<n$, if you prefer.

Regarding your solution:

Yeah, you're missing something.  For instance, a solution could start

┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴
└─────┴─────┴──

and continue from there; that won't be counted in your case analysis.


Polynomial reduction from unbounded knapsack problem to general integer programming Given an oracle that can solve in polynomial time:

$$a^Tx=b$$
$$x \geq 0$$

So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)

With this oracle how can this be solved in polynomial time:
$$Ax=b$$
$$x \geq 0$$

where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.

My thoughts:

Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.

Hint: What do you know about the complexity class of the unbounded knapsack problem?  Is it in P?  Is it NP-hard?

Now what do you know about the complexity class of LP?  Is it in NP?

Think a bit about your answers to those two questions and see if that helps you see one path forward.  (There's a short proof of your desired result that doesn't require much detailed mathematics.)

Once you've figured that out:  if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...)

Once you've worked out that: you should now know there is a reduction. So look at the proofs of each of the steps of reasoning I walked you through. Review these proofs. Those proofs will construct a reduction for you. So, work out what reduction is implicit in the proofs. You should be able to take it from here!


Initializing non-deterministic variables in QBF I'm trying to translate the following pseudocode to QBF. The integers are encoded as simple fixed-width bitvectors, and the entire procedure runs in polynomial space ensuring QBF has enough representational power for a compact formula.

The following formula is nested to a linear depth in n, producing 2^n increments when unrolled. Using QBF allows for an exponentially more compact encoding than SAT. QBF solvers can typically handle thousands of variables, SAT solvers handle millions. For even modest values of n, such as n=30, unrolling to SAT would produce billions of variables (impractical), while a QBF encoding would be extremely practical with only tens of variables.

counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter > 0)

Here f is an arbitrary function that outputs 0 or 1.

This suggests a QBF implementation (although missing initialization) utilizing an adder circuit with its output fed back in as input:

∃ counter[n] ∀ loop_aux[n] ∃ f_output[1] (counter += f_output) & (f_output == f(loop_aux_0, loop_aux_1, .., loop_aux_n))

How can I add clauses or auxiliary variables to simulate sequential counter initialization?

It looks to me like there is some confusion here about what QBF is and when it is needed.  You don't need QBF for this problem; SAT is fine.

Here's how to solve this using a SAT solver. Notice that the condition counter > 0 is true at the end if and only if there was at least one loop iteration where f output 1.  In other words, the assertion will be true if and only if

$$\exists \mathtt{loop\_aux\_0},\dots,\mathtt{loop\_aux\_n} . \mathtt{f}(\mathtt{loop\_aux\_0},\dots,\mathtt{loop\_aux\_n})=1.$$

That can be expressed as a SAT instance.  There are no nested/alternating quantifiers; the formula has the form $\exists x. \varphi(x)$, so it can be solved by SAT.  Simply express the condition f(loop_aux_0, ..., loop_aux_n)=1 in CNF form, and then use a SAT solver to check whether that condition can ever be true (for any value of the loop variables).

QBF is useful when you have nested quantifiers, e.g., $\exists x . \forall y . \exists z . \varphi(x,y,z)$.  The result will be either true or false.

It's also worth knowing about #SAT.  #SAT is useful when you want to count the number of satisfying assignments to some formula $\varphi(x)$.  In other words, instead of checking whether $\exists x . \varphi(x)$ is true, suppose we want to know the number of values $x$ such that $\varphi(x)$ is true; then this is an instance of #SAT.

QBF and #SAT are not the same thing.  They're different problems.  And QBF isn't some kind of magic wand that lets you compress any SAT instance by some enormous factor; QBF is for a specific type of logical formula.


What is congruence in lambda-calculus I see a lot of lecture notes where they use the term "congruence" (ex: congruence relation) or deriving usages such as "the expression e is alpha-congruent to e2".
Could someone please explain what congurence means exactly in this context and give some examples to a noob without much knowledge about math/lambda-calculus.
Thanks in advance

Generally speaking, in algebra, a congruence relation is an equivalence relation such that operations on equivalent objects yield equivalent objects. In the lambda calculus, a congruence is an equivalence relation such that constructing terms from equivalent terms yields equivalent terms: if $M \equiv M'$ and $N \equiv N'$ then $M\,N \equiv M\,N'$, and if $M \equiv M'$ then $\lambda x.M \equiv \lambda x.M'$.
“Alpha congruence” is another name for alpha equivalence, which is the relation such that two terms are alpha-equivalent if they are, intuitively speaking, the same except for renaming internal variables. Since this is not only an equivalence but even a congruence, it's called both “alpha equivalence” and “alpha congruence”.


how can i find the Maximum Degree of Concurrency? i'm studying Parallel Processing ,

and i'm confused how can i calculate the max number of concurrency in a given dependency graph ?

i know that the maximum number of concurrency is the largest number of
concurrent tasks at any point of the execution , but i can't calculate it from the graph

can someone explain how can i find the solution from the following graph ?

thank you ALL

Graph a:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is the sum of the weights of those four nodes: 10+10+10+10 = 40.

Phase 2:  Task 6 and Task 5 can be executed parallelly (if you have more than 1 processor). So the degree of concurrency in this phase is: 9+6 = 15.

Phase 3: You can execute only Task 7, so the degree of concurrency here is 8.

The maximum number of concurrency is max(40, 15, 8) = 40.
The average degree of concurrency is (40+15+8)/(10+9+8) = 63/27.

Graph b:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is: 10+10+10+10 = 40.

Phase 2:  You can execute only Task 5, so the degree of concurrency here is 6.

Phase 3: You can execute only Task 6, so the degree of concurrency here is 11.

Phase 4: You can execute only Task 7, so the degree of concurrency here is 7.

The maximum number of concurrency is max(40, 6, 11, 7) = 40.
The average degree of concurrency is (40+6+11+7)/(10+6+11+7) = 64/34.


How much time would be needed to compute an algorithm with time complexity $O(n^k)$? How much time would be needed to compute a minimum k-cut, which has time complexity $O(n^k)$ on a graph with $n=5000$ and $k=30$? Consider using a basic 2GHz and 8GB RAM laptop.

Please explain also the process of how to compute the answer.

An algorithm has time complexity $O(n^k)$ if there exists a constant $C>0$ such that the number of operations that the algorithm performs in the RAM model on an input of length $n$ is at most $Cn^k$.

There are several reasons why this doesn't allow you to determine how much time the algorithm will take on a given machine for a given value of $n$:

$Cn^k$ is only an upper bound.
We don't know the value of $C$.
Your machine differs from the abstract model of computation used to analyze the algorithm.

Therefore the only way to really know how much time a certain algorithm would take is to code it and empirically measure its running time.

What good is asymptotic analysis, then? The abstract machine is a reasonable model of real computers, so it is likely that the running time will scale like $n^k$ (assuming $O(n^k)$ is a tight upper bound). If $k$ is large, then likely the algorithm isn't practical. So asymptotic analysis allows you to compare different algorithms on paper rather than in practice. Of course, sometimes this comparison will result in the wrong conclusion. This is the case for fast matrix multiplication, for instance.


Hoare logic - invariant of loop I am trying to prove partial corectness of following program:

{s = 0 and j = 0}
while j <= n do begin
  { s + j = (j - 1)j/2 and j <= n + 1}
    s := s + j;
  { s = (j-1)j/2 and j <= n + 1}
  { s = j(j+1)/2 and j + 1 <= n + 1}
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n}
{s = n*(n+1)/2}

And I am trying to find invariant.  It seems to me that good candidate is s = (j-1)j/2 and j <= n + 1.
Am I ok ?

There is an issue below:

{s = 0 and j = 0}
while j <= n do begin
  { s + j = (j - 1)j/2 and j <= n + 1}     (*)
    s := s + j;
  { s = (j-1)j/2 and j <= n + 1}           (**)
  { s = j(j+1)/2 and j + 1 <= n + 1}
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n}
{s = n*(n+1)/2}

The part marked with ** seems to use a weakening step (sometimes also called a pre- or post- step), moving from { s = (j-1)j/2 and j <= n + 1} to { s = j(j+1)/2 and j + 1 <= n + 1}. However, this is allowed only if the former implies the second, which is not the case! This step looks completely arbitrary.

You can simply avoid it, and backward propagate as usual.

Further, in * you can also assume that the while guard is true, beyond the invariant.

Here's a possible step towards a fix:

{ s = 0 and j = 0 }                           (1)
{ s = (j-1)j/2 and j <= n + 1 }
while j <= n do begin
  { s = (j-1)j/2 and j <= n + 1 and j <= n }  (2)
  { s + j = j(j+1)/2 and j + 1 <= n + 1 }
    s := s + j;
  { s = j(j+1)/2 and j + 1 <= n + 1 }
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n }     (3)
{ s = n*(n+1)/2 }

Now you need to prove the implications at points 1,2,3. 3 looks simple, and 2 requires a bit of arithmetic. Instead 1 looks false if n<-1. We need a stronger precondition ensuring that.

Indeed, if you manually run the program starting with n=-10, you do not get s=n(n+1)/2 at the end, so the Hoare triple is invalid, hence -- since the Hoare logic is correct -- we can not hope to prove it valid ;-)


Generate a uniform random numbers in $O(1)$ Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.)
How do we generate a uniform random number in $\{0,\cdots,m-1\}$ for $m\leq n$? We require that we can only call $G()$ $O(1)$ times in expectation.
My effort:
Suppose $n=km+r$, where $k$ and $r$ are integers. Call $G()$. If $G()\leq km$, return $G()\mod m$; otherwise, call $G()$ again.
But in expectation, this will call $G()$ $O(\frac{n}{n-r})$ times, and $r$ can be $1,\cdots,m-1$.

Since $r < m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m > r$. In particular, $r < n/2$ and so $n-r > n/2$. In total, we conclude that $n/(n-r) < 2$.


Algorithm to find what points are the nearest to other points I have two lists:

Location list, it contains point of interest
People list, it contains coordinates of every person. One single person could be in the list multiple times, depending from the log time. Someone who is out for a walk will result in two different locations in two different hours.

I would find out what people where near every point of interest.

I could approach the problem with brute force: external loop check for every point of interest the entire people list finding out who was there.

I would obviously avoid brute force. I thought about Nearest Neighbour, for sure multiple people will be in the same spot so I could look for a point of interest in the cluster.

Solutions?

Use a data structure designed for nearest neighbor search.


Number of submatrices with a particular sum- Answer Explantion I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix.

[1  2  3  2   5,
 2  4  6  4  10,
 3  6  9  6  15,
 2  4  6  4  10,
 5  10 15 10 25]

Now applying step 1 we get .

[ 1  2  3  2  5 ,
  3  6  9  6  15,
  6  12 18 12 30,
  8  16 24 16 40,
  13 26 39 26 65]

Now applying step 2 we get all the possible pair of row indices i.e.

(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)

Now comes the last part of applying two pointer algorithm. Which i am failing to understand.For ex.
Lets take (1,2)

B[2][1] - B[1][1]= 3-1 = 2
B[2][2] - B[1][2]= 6-2 = 4
B[2][3] - B[1][3]= 9-3 = 6
B[2][4] - B[1][4]= 6-2 = 4
B[2][5] - B[1][5]= 15-5 =10

Now how is that helping? I mean on these values if we apply two pointer algorithm what will we achieve? For example i am looking for all occurrences of 36. How do i get close to it. ?

Can anybody carry this forward and explain the solution?

The two-pointer algorithm is described in this post. Given a non-negative sequence $\alpha_1,\ldots,\alpha_n$ and a target sum $S$, we want to find the number of pairs $(i,j)$ such that $\alpha_i + \cdots + \alpha_j = S$. Let's make life a little easier by requiring the sequence to be strictly positive. For each $i$ there is therefore at most one $j$ such that $\alpha_i + \cdots + \alpha_j = S$, and we could find it by enumerating over all $j$ (resulting in an $O(n^2)$ algorithm) or using binary search (this requires $O(n)$ preprocessing, and leads to an $O(n\log n)$ algorithm).

The two-pointer algorithm is very similar but uses data from the $i$th iteration to make the $(i+1)$th iteration faster. Here is one variant For each $i$, we calculate the minimal index $j(i)$ such that $\alpha_i + \cdots + \alpha_{j(i)} \geq S$. The main observation is that $j(i)$ is a non-decreasing sequence, that is, $j(1) \leq \cdots \leq j(n)$. This suggests the following algorithm:

Initialize $j(0) = 0$.
For each $i$ in turn, calculate $j(i)$ by going over $j = j(i-1),j(i-1)+1,\cdots$ until $\alpha_i + \cdots + \alpha_j \geq S$. We then set $j(i) = j$. If $\alpha_i + \cdots + \alpha_{j(i)} = S$, we have found a subsequence summing to $S$.

This algorithm runs in linear time (basically since the index $j(i)$ keeps increasing) and finds all contiguous subsequences summing to $S$. I'll also let you figure out yourself what to do when some entries could be $0$.


Do correlated inputs imply existence of efficient communication protocols? Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such as disjointness of $X$ and $Y$ requires $\Omega(n)$ bits assuming the input distributions of $X$ and $Y$ are chosen to be "hard".

Now suppose that we know that $H(X | Y) = k$ and $H(Y | X) = k$, for $k << n$. Is it always possible to derive an efficient deterministic communication complexity protocol (that computes a given function $f$) and has communication complexity at most $O( H(X | Y) \cdot H(Y | X) )$ ?

If the answer to the above question is no, is there an easy counterexample, i.e., a function that requires a high amount of communication despite correlated inputs?

One approach I was thinking about is that, since Alice knows $X$ and $H(Y | X)=k$, we could in advance fix an enumeration $E_X$ of the possible choices of Bob's input $Y$, given $X$.
Clearly, the choice of a specific $Y=y$ from $E$ can be described using $k$ bits.
But this doesn't seem to help at all: Bob doesn't know $X$, so he doesn't know which enumeration $E_X$ is used by Alice (and vice versa).

Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) < 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.


Non-regular Languages? Possible Duplicate:
  How to prove that a language is not regular?

Why $L_a$ and  $L_b$  are not reguluar?

$L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$.

$L_b= \{nm^{i_1} nm^{i_2}...bn^{i_z}: z \in N, (i_1,...,i_n) \in N^z, 1 \leq j \leq z, i_j ≠ j \}$.

Hints...

$L_a$ can be transformed into an well-known non-regular language by a very simple homomorphism that basically "loses" information.

For $L_b$ you might try transforming it into its "opposite" (that is, equality in place of inequality) by operations known to preserve regular languages.  The "opposite" language might then be amenable to a pumping argument. Also, try "testing" your argument on a much simpler version of $L_b$ which, although it is regular, will let you see the patterns to use for the full $L_b$.

PS -- these are both techniques that might be added to the reference post that Dave Clarke points to. I will do so when this question has settled down.

Thinking a bit more about $L_b$, the idea I had in mind to derive the "opposite" language may not lead directly to an easy solution. So here's a hint in a different direction.  There are a lot of $m^{i_j}$ in each string of that language. If you could "isolate" those strings of $m's$ by an appropriate regularity-preserving operation, you might get a simpler language that is amenable to a proof, perhaps by pumping or perhaps by the "opposite" idea.  Also, think about what each $i_j \neq j$ means in terms of other symbols in the string.


Proving existence results I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:

(i) For all x ∈ A, |x| ≤ 5.

(ii) Every DFA that decides A has more than 8 states.

To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}* that holds both of these properties?

You can prove the existence of an object satisfying properties in many ways. The simplest is to exhibit such an object explicitly, which is what you can do in your case. But there are also other possibilities:

Use a probabilistic argument. If you choose a uniformly random graph on $n$ vertices, then it will have no large clique or independent set. We don't know how to construct such graphs explicitly.  Sometimes it is not enough to just choose a random graph. The well-known construction of graphs with high girth and high chromatic numbers modify a random graph so that it satisfies the requirements. A more sophisticated version is the recent interlacing polynomials method, used to construct Ramanujan graphs.
Use a non-constructive argument. The is an algorithm that given $n$, determines whether the decimal expansion of $\pi$ contains a block of $n$ zeroes. Indeed, such a program either always returns YES, or it returns whether $n \leq N$, where $N$ is the longest such stretch of zeroes. While we do not at the moment know which of the two options is correct, one of them must be correct, and so the algorithm exists.
Use a proof by compactness. Consider the problem of determining whether a graph can be embedded into a torus (without edge crossings). This is a minor-closed family of graphs, and we can consider the set of forbidden minors, i.e., minimal graphs (with respect to the minor relation) not embeddable into a torus. This is an antichain of graphs (with respect to the minor relation), so according to the graph minor theorem, it must be finite. Since we can test whether a graph on $n$ vertices has a given graph as a minor in time $O(n^2)$, it follows that we can determine whether a graph is embeddable in a torus in time $O(n^2)$. But we can't actually construct the algorithm, so we don't know the complete list of forbidden minors.


Linear time labeling algorithm for a tree? I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in the obvious way until all vertices have a label. The reason I do this is I want to store the vertices in a queue, and go through them "leaves first". Is there an easy way to do this $O(n+m)$ time?

I can solve the problem by doing a BFS on every step. But in the worst case, on every step I go through every vertex, remove exactly two leaves and enqueue them. I believe this takes quadratic time.

Another idea was to first find all the leaves, and then do a BFS from every leaf. This doesn't give me the desired solution. For example, consider a kind of "crown graph" as in the figure below. The desired solution is shown, but launching a BFS from each leaf would result in only two labels used.

Ideally, the linear time algorithm would also be easy to explain and implement.

Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:

Put all vertices in a priority queue, with their priority being their degree.
While the queue is non-empty:

Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).

In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:

Initialize an array of length $V$ with the degrees of all vertices.
Initialize another array of length $V$ with "alive".
Go once through the first array, and push all vertices of degree $1$ to a queue.
While the queue is non-empty:

Pop a vertex $v$.
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Mark $v$ as "dead".
If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
If the new degree of $u$ is $1$, push $u$ to the queue.

Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.

Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.

You run this algorithm on the root.


What is the proper runtime for visiting all outgoing edges in an adjacency list? Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list.  Suppose that we want to list all of the edges incident to some node $v \in V$.  We can do this by iterating over all the elements in the adjacency list.

My question concerns the runtime of this operation.  Is it proper to say that the runtime is $\Theta(deg^+(v))$ (since the runtime is a linear function of the outdegree of $v$)?  Or should it be $\Theta(1 + deg^+(v))$, since even if $deg^+(v)$ is zero, there is some amount of work that's still done?  Or are both of these terminologies incorrect because there is no underlying variable $n$ for which we could apply the formal definition of $\Theta$?

Thanks!

You're right that $\Theta(\deg^+ v)$ is a bit sloppy, but it is usually understood that $\Theta(\deg^+ v)$ is actually $\Theta(1 + \deg^+ v)$. Perhaps it's better to use the more accurate $\Theta(1 + \deg^+ v)$.

You're also right that more formally a $\Theta(\cdot)$ notation should state the underlying variable, but here there is only one variable and so no confusion can arise. Also, since $\deg^+ v$ is always non-negative, the simpler definition of $\Theta(\deg^+ v)$ - there exists $C > 0$ such that the running time is at most $C \deg^+ v$ - is unambiguous. That's also how we should understand expressions like $\Theta(n + m)$, where the two variables $n,m$ are independent.


Single Source Shortest Paths using Product Construction I am trying to solve a bounded SSSP problem as follows:

  Given a connected weighted graph with non-negative edges (might have
  cycles), find the shortest path from a vertex s to a vertex t with
  at most k edges.

I have done some research on this problem. All proposed solutions point to using Bellman-Ford's algorithm by modifying its outer loop to perform k iterations. This will yield a worst case time complexity of O(VE).

I wish to know if it is possible to solve this in O(k * (V+E)LogV) or better using Dijkstra's algorithm?

I have seen this post that discusses the same problem. Dijkstra's algorithm to compute shortest paths using k edges?

However, I don't know how to prove the correctness of the solution that uses product construction.

Could someone please advise me?

The product construction means that you don't just store the shortest distance to a given node, but store the shortest distance to reach a node on a shortest path with $k$ nodes. You certainly don't need to explicitly construct the edges of the product graph. But since the algorithm will produce $k\cdot|V|$ shortest distances of this form, it seems as if you must at least construct an array of this size to hold those distances.
However, this is not exactly true, because only the distances different from $\infty$ must be stored.

So you could either generate the nodes of the product graph on the fly and store them in a map (i.e. something like a red black tree), or first determine the reachable part of the product graph by a suitable algorithm. If you only care about the complexity and not about the practical efficiency, then the solution with the map is simpler and still good enough. That map can then also be used for Dijkstra's algorithm itself to determine the next node on which the algorithm continues.

The disadvantage compared to Bellman-Ford's algorithm is that you can't reuse the memory from the previous iteration for the current iteration, because Dijkstra's algorithm will not produce all distance $j-1$ paths before producing distance $j$ paths. But maybe it is possible to modify Dijkstra's algorithm to do exactly this, and this might indeed yield the most efficient algorithm for your problem.


Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable? I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$.
My idea:
It is co-semi-decidable since as soon as i find an $x\in T(M_v)$ with $|x|\geq |w|$ I have shown that this sepcific w is not in the set. I think it aint semi-decidable, since there can always be an $x\in T(M_v)$ which is longer than w. Therefor i also think the problem ist undecidable.
Do i oversee something ?

Yes, you are missing something.
The first argument that this language is co-semi-decidable is correct. However, the second one is wrong (and not formally written. A formal proof could not consist of such arguments, they are only for intuition usually).
Now to show why it is fully decidable:
We know that $|T(M_v)|=c<\infty$. Now, since this is a constant smaller than infinity, there must be an $x_0\in T(M_v)$ for which $|x_0|$ is the longest from the words in $T(M_v).$
Now, build the turing machine that accepts $w$ iff $|w|>|x_0|$.
Since $x_0$ is the longest, then if $|w|>|x_0|$ we will have that $\forall x\in T(M_v):|w|>|x_0|\ge|x|$ and thus $w$ is in your language. Now, if $|w| \le |x_0|$, then obviously $w$ is not in your language.
Thus $w$ is in your language iff $w$ is accepted by the turing machine we built.


Mixed Integer Linear Programming application problem I have a Mixed-Integer Linear Programming question.

There's this game called Islanders. Pretty graphics, it's about maximizing your score building a small city in a confined island.

Here's a quick rundown of the rules:

There are various building types
Every building type has a different size
Every building type has a different range (explained later)
Every building may give a non-zero base score when placed
Every building may have give a positive, zero or negative score based on what buildings are within its range when placed
Buildings already placed are not affected by newer buildings (their score contribution is not updated)

I thought it would be a fun exercise to formulate these rules into an MILP and see what comes out of it.

I have written the attached Python 3 program, using the PuLP library (link).
I have used the default solver (CBC), provided with the installation of PuLP.

There are currently 4 building types encoded, with their base score declared at line 61, the 4x4 cross-score matrix at line 64 and their dimension and range in lines 72 and 75.

In line 82 there is currently stated that there is 1 building of the first type and 3 buildings of the 2nd type to be placed optimally (N=5)

There are several decision variables:

px and py are each building coordinates
t is the build order (integer)
placed_before is a NxN array saying if building i is to be placed before building j (binary)
east_of, north_of have similar logic (binary)
covers states whether building j is in range of building i (binary)
x_overlaps and y_overlaps check whether two buildings are built on top of each other, which is restricted (binary)
gives_score is a NxN array saying if building i contributes to the score of building j (is whthin range is is placed before it, binary)

The constraints are as follows:

Lines 140-147 state the building order constraints, which form variable t
149-161 decide if buildings are east-west and north-east, used for later
163-183 establish whether buildings overlaps each other, in the east-west (x) direction and the north-south (y) direction
185-219 establish if building i covers building j, filling in the covers variable
222-237 enforces the separation of two buildings, if they overlap in both x and y directions
239-250 finds out if a building i contributes to the score of building j

Currently, the cost function under optimization is gives_score, to maximize the number of buildings which give score to another.

The issue:

Currently with 1 of the first building and 4 of the second, the optimization does not finish in reasonable time. 380 constraints are generated.
If instead you go for 3 of the second building type, the problem becomes tractable again, finishing in approx. 10s. 228 constraints are generated.
Also, if you disable the constraints of lines 222-237, the optimization manages to run, but the buildings overlap.

Any suggestions on the problem formulation or explanations on why this is such a hard problem?

Thank you in advance.

Bonus:
Here is an example optimal result for 1 of type-1 building and 3 of type-2:

While I can't answer if your model is okay or if it has some subtle flaw, I think I can confirm that general approach works and the issue is with CBC solver.
I reimplemented the game on my own: https://gist.github.com/afish/56d710cf440bf652fa2ea51f356f7378
CPLEX finds solution for city center and 4 houses in 3 seconds. CBC can't do it (I killed it after couple minutes). I imagine the same situation might be with your code.
I don't know what solvers you can use but seems like CBC is not a good choice here. Just for the record, I also tried MIPCL, SCIP, and GLPK - none of them could solve the problem in a reasonable (~seconds) time.


Need hint for bipartiteness proof I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(u_1, v_2), (u_2, v_1) \in E^\prime$.
I need to prove:
$$G^\prime \textrm{ has 2N connected components} \Leftrightarrow G \textrm{ is bipartite}$$
I don't know what technique or approach I need to use to prove this in either direction. I have a feeling I can use a direct proof for both directions. I have tried to come up with something but after an hour nothing has come up.

Let's do the case $N = 1$.
Suppose that $G$ is a connected graph, and assume first that $G$ is bipartite, with bipartition $X,Y$. Let $X_1,X_2,Y_1,Y_2$ be the two copies of the two parts in $G'$. Note first that the edges in $G'$ either connect $X_1$ to $Y_2$ or $X_2$ to $Y_1$, and so $G'$ has at least two connected components.
Conversely, any path from $X$ to $Y$ in $G$ gives rise to a similar path in $G'$ from $X_1$ to $Y_2$, implying (after a short argument) that $X_1 \cup Y_2$ form a connected component; and similarly for $X_2 \cup Y_1$. Thus $G'$ has exactly two connected components.
Now suppose that $G$ is a connected non-bipartite graph. As before, the vertices in $X_1 \cup Y_2$ are all in the same connected component of $G'$, as are the vertices in $X_2 \cup Y_1$. We will show that $X_1$ is connected by a path to $X_2$, implying that $G'$ is connected.
Since $G$ is not bipartite, there is some odd cycle in $G$. Let $x$ be a vertex on this odd cycle. Lifting this cycle to $G'$, we obtain a path from $x_1$ to $x_2$.


Given a total recursive function, can you always compute its fixed-point? We know from Kleene's recursion theorem that if $f$ is total recursive, there must be an integer $n$ for which $\varphi_n=\varphi_{f(n)}$. My question is: for every $f$ total recursive, is there a computable (total) procedure that computes such a point?

ie: $\exists g.\forall f.\varphi_{g(n)}=\varphi_{f(g(n))}$.

The proof of the recursion theorem is constructive: it gives you an algorithm to compute $n$ from $f$. See for example these notes of Rebecca Weber.


How do I mathematically express a set generated using two loop variables within a single for loop? I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration.

For example, assuming n is previously defined and holds some positive integer, how I would I represent the set printed by this for-loop in mathematical notation?

// prints a set of multiples (n previously defined)
for (int j=n, k=n; k>=0; j++, k--) {
  cout << (n-j)*(n-k) << endl;
}

Forgive my crudeness, but I'm thinking something along the lines of:

$\left \{ \left ( n-j \right ) \cdot \left ( n-k \right )\forall j \left \{ n, n+1, ..., 2n \right \}  \forall k  \left \{ n, n-1, ..., 0 \right \}\right \}$

I'm lost. Should I even be using $\forall$ in this context? Any guidance is greatly appreciated!

You attempt is basically correct, assuming that the for-loop is short for nested loops. You'd usually write it like

$\qquad\displaystyle\{ (n-j)(n-k) \mid j \in \{n, \dots, 2n\}, k \in \{n, \dots, 0\}\}$.

Now we note that we can write

$k$ instead of $n-k$ (in the code, reverse the direction of the for-loop) and
$-j$ with $j \in \{0, \dots, n\}$ instead of $n-j$ with $j \in \{n, \dots, 2n\}$ (do you see why?).

So we get

$\qquad \displaystyle \{ -jk \mid j, k \in \{0, \dots, n\}\}$.

If, on the other hand, the for-loop is supposed to step j and k simultaneously, building all combinations is not what happens. Then, you'd have

$\qquad\displaystyle \{ (n-j)(n-k) \mid (j,k) \in \{ (n,n), \dots, (2n,0) \} \} $

which we can rewrite by noting that

$j \in \{n, \dots, 2n\} \iff (n-j) \in \{0, -n\}$ and
$k \in \{n, \dots, 0\} \iff (n-k) \in \{0, n\}$ and

to

$\qquad\displaystyle \{ -jk \mid (j,k) \in \{(0,0), \dots, (n,-n)\} \}$.

But now $j$ and $k$ only differ by the sign, so we can rewrite using only one variable:

$\qquad\displaystyle \{ -x^2 \mid x \in \{0, \dots, n\}\}$.


How can I fill bookcases with shelves of books using the least number of bookcases? Sorry for layman's term question, my background in computer science is weak.

What I have is a list of shelves with books of varying height.  Each shelf stores a value that describes how many shelves (of that height) can fit on a bookcase.  The bookcases have adjustable shelves so that we can maximize the usage of each one.

What I have been trying so far is sorting the shelves from shortest to tallest and filling in each bookcase, but what happens is that there are remainders which could be filled in with the small shelves.

I should mention that an additional complexity is that we want to place the tallest shelf on the top of the bookcase (because it would be more efficient).

I am not expecting a full on answer for how to do this... but I would very much appreciate a book or article on the topic.  I just need a little direction and I think I would be able to pick it up.

Thanks for your help!

I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below.

Multiple bookcases

If you have multiple bookcases, and you need to put each shelf into exactly one of the bookcases, then you have an instance of the bin packing problem.

Each shelf corresponds to an item, and each bookcase corresponds to a bin. Now you want to find a way to put each item into one bin, i.e., put each shelf into one bookcase, so that every shelf is in some bookcase, and each bookcase has room for all the shelves that will go into it.

This can be modelled in a straightforward way as a bin packing problem:

The "size" of a shelf (an item) is the height of the shelf.
The "size" of a bookcase (i.e., of a bin) is the height of the bookcase.

Now you want to find a way to assign each shelf to one of the bookcases, so that the sum of the sizes (heights) of the shelves in each bookcase does not exceed the size (height) of the bookcase.  That is exactly the bin packing problem.

You should be able to use any standard algorithm for bin packing to solve your problem.  Given the number of bookcases and shelves you're likely to have in practice, any of them should be efficient enough for practical use.  For instance, one approach is to formulate this as an instance of ILP (integer linear programming), as described in the Wikipedia article on bin packing, and then solve the problem using an off-the-shelf ILP solver, such as lp_solve or CPLEX.  This will likely be very effective in practice.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into each bookcase, and then for each bookcase, find the tallest of the shelves that are going into that bookcase and put it at the top of the bookcase.

One bookcase

If you have one bookcase, and you can select some subset of the shelves to fill the bookcase, your problem is an instance of the knapsack problem.

Treat each shelf as an item that can be placed into the knapsack.  Then:

the "weight" of a shelf is its height,
the "value" of a shelf is the value of including that shelf in the bookcase (e.g., the number of books it'll enable you to store, or maybe just a fixed value that's the same for all shelves), and
the "capacity" of the knapsack is the total height of the bookcase.

The optimal solution to the knapsack problem will select a subset of items whose total weight doesn't exceed the knapsack's capacity, and that maximizes the sum of the values of the selected items.

In your context, that amounts to selecting a subset of the shelves whose total height doesn't exceed the height of the bookcase (and thus it'll be possible to fit all of the selected shelves into your bookcase), and that maximizes the sum of the values of the shelves (e.g., maximizes the total number of shelves that you fit into the bookcase, or the total number of books you can store in the bookcase, etc.).

There are many algorithms for the knapsack problem, such as the dynamic programming algorithm.  In your situation, I suspect the number of candidate shelves is small enough that any of these algorithms is likely to be efficient enough for real-world use.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into the bookcase, and then choose the one that is tallest and put it at the top of the bookcase.


Extracting features for texture classification I'm a beginner in the field of pattern recognition and computer vision. I'm working on a project right now to classify t-shirt patterns into three categories i.e. solids, stripes and checks. I have close up training images of the t-shirt images. A sample shirt image looks like this

I have looked at a bank of gabor filter features, but they are computationally expensive. It would of great help if someone could point me out in the general direction for working forward. Any help is appreciated.

EDIT - I found the solution in D.W.'s answer below, though my solution is not very good. I'm classifying solid patterns by counting the number of line segments in the image. If they fall below a certain number, I'm classifying them as solid. If not, I further classify them into stripes or checkered using HoG features and a linear SVM. The accuracy achieved was around 91%. It was a little low due to some misclassified samples in the training set.

If it is important for you to get a high accuracy, then use a convolutional neural network (ConvNet). These ConvNets hold the state of the art for most visual recognition tasks. If your training set size is small, you should use a pretrained ConvNet as a feature extractor and then apply a support vector machine (SVM) on top of the extracted features.

I can recommend Keras as a good toolbox for ConvNets that is simple to use. You should be able to find a pretrained ConvNet for Keras by searching Google. VGG or ImageNet are names of well-performing ConvNets (particularly the former) so that is worth searching for.


Probability that all indices divisible by 100 in a hash table with linear probing are occupied I am trying to solve this question on Sedgewick's and Wayne's Algorithms book:

  Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the probability that all positions with indices divisible by 100 are occupied.

So we had 500.000 inserts on the hash table and need to check the probability of positions 0, 100, 200, ..., 99900 being occupied. So far I thought about calculating the events one by one:
On the first insert there are 10^4 / 10^6 probability of inserting in an index divisible by 100. On the second, we have to consider that the first index divisible by 100 was chosen, so there is a 9.999 / 10^6 probability.

And since we have more inserts (500.000) than indices divisible by 100, I thought about computing the probability of 10.000 inserts occupying the indices divisible by 100 and then multiplying this probability by 50, since we could "try" this insert pattern 50 times.

P = (10.000 / 10^6 * 9.999 / 10^6 * ... * 1 / 10^6) * 50

Is this line of thought correct?
Also, the tricky part here is that we are talking about a linear-probing hash table. So if we insert an element on index 99 twice, the second element will occupy index 100. This also means that inserting an element on index 1 100 times will mean that index 100 is occupied.
I am not sure how to deal with this extra requirement. Any ideas?

This problem may be reduced to the following simple probability problem with concrete numbers.

Assume you have an urn with 8 black and 12 white balls, total 20 balls. You randomly draw 15 balls from the urn one by one without replacement. What is the probability that all black balls are selected?

How does it relate to the original problem? Occupying slots one by one is equivalent to drawing balls without replacement. Both number of slots and balls decrease. "Drawing a ball" corresponds to "eventually occupying a slot" after linear probing (searching).

We have address space of $10^6$ slots equivalent to having $10^6$ balls in an urn. Then you have positions with indices divisible by 100 equivalent to having $10000$ $(=10^6/100)$ black balls. $500000$ positions are occupied means that you draw $500000$ balls. Finally, the requirement "all positions with indices divisible by 100 $(=10^6/100)$ are occupied" means "all $10000$ black balls must be selected".

Thus it is the hypergeometric distribution that describes the probability of $k$ successes in $n$ draws, without replacement, from a finite population of size $N$ that contains exactly $K$ successes, wherein each draw is either a success or a failure (black or white).
The probability is equal to

$$ P(k \text{ successes})= \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$

So, if we take urn-balls model then we have
$$ P(8 \text{ black balls})= \frac{\binom{8}{8}\binom{20-8}{15-8}}{\binom{20}{15}}$$

As for the original problem then we have
$$ P(10000 \text{ occupied slots})= \frac{\binom{10000}{10000}\binom{10^6-10000}{500000-10000}}{\binom{10^6}{500000}}$$

Now, our numbers in the original problem is too large to compute the binomial coefficients. You could get around the problem using Stirling's approximation.


Chomsky hierarchy type determined by language I have some modified automata and the task is to give the type of Chomsky hierarchy to it.
All task is between type 3 and 0 noninclusive.
For regular languages there are lot of tools and I can check it without problems, Turing Machine equivalent is also easy task, and there will be no such examples.

Now the question: is it sufficient to show that automaton can accept specified language of given type?
From what I checked it would be sufficient to show equivalence to for example to NPDA, so I assume that if machine handles language that at least NPDA accepts it would be sufficient.

For example if machine can accept $a^nb^n$, it is type 2.
If machine can accept $a^nb^nc^nd^n$ it is type 1?
If not are there better examples of such languages or what steps should I follow?

No, a finite set of languages does not (usually) characterise infinite classes of languages. So any such specific tests are probably easy to fool.

For CFL in particular, there the Chomsky-Schützenberger characterisation. So if your model can deal with finitely many types of nested parentheses, it's probably at least as powerful as NPDA.

The generic proof technique for showing that one model is more powerful than another is simulation. You can find some examples via simulation and, of course, in the literature.

Proof of the opposite is usually done by counter-example, i.e. a language that can be expressed in one but not the other model.


Probability of hash collision in the case of two parallel hashes I understand how to calculate the probability of a hash collision.
I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I could potentially query two hashes to determine probable record matches.
If I have 1 billion records, a 64-bit hash will have $\sim 1:32.5$ collisions. If I have two by 64-bit hashes, how many effective bits will I have?
65-bits seems pessimistic, 128-bits seems optimistic. $\sim 32.5^2$ results in a fraction over 69 bits hash resolution.
How do I calculate this?
ILLUSTRATION
Parent Table
parent id, $\{$ field $1$, field $2$, ... field $n \}\implies$  parent hash
Child Table
child id, parent id, parent hash, $\{$ field $1$, field $2$, ... field $n \}\implies$ child hash
As illustrated, the child table has both parent hash and child hash. Two by 64-bit hashes.

You can think of concatenating the two hash values and treating the result as a single hash.  Then you have $n$ records, each of which has a single hash.  The probability of a collision among $n$ hashes is roughly $n^2/2^{b+1}$, if the hash outputs a $b$-bit value.  In your case if each of the two individual hashes is 64 bits long, after concatenation you have a 128-bit hash for the record, so $b=128$.

How did I obtain the formula $n^2/2^{b+1}$?  It's an application of the birthday paradox, with $n$ people born on a planet that has $2^b$ days in the year (instead of 365 days).  Or, if you prefer an intuitive argument: think of all ways to pick a pair of $b$-bit hashes.  There are about $n^2/2$ pairs of hashes. For each one, there's a $1/2^b$ probability that those pair of hashes are equal (that they collide).  So the total probability that at least one of these collide is about $n^2/2$ times $1/2^b$.  This is a crude estimate that isn't totally accurate, but it turns out to be a reasonable approximation as long as $n^2/2$ is fairly small compared to $2^b$.


Regex for divisibility by 123 in binary strings Is there a regex that checks for divisibility by 123 in binary strings?
This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative Exercises section).
Creating a regex to check if a binary string is divisible by 3 is simple: (0|1(01*0)*1) *
A regex to check if a binary string is divisible by 2 is also simple: (0|1)*0
And there are many questions on the Internet asking for a regex for divisibility by 7.
However, I could not find any resources related to a regex for checking if a binary string is divisible by 123.
These are the representations of some multiples of 123 in binary:

0 = 0
123 = 1111011
246 = 11110110
369 = 101110001
492 = 111101100
615 = 1001100111
738 = 1011100010
861 = 1101011101
984 = 1111011000
1107 = 10001010011
1230 = 10011001110

There doesn’t seem to be a pattern that stands out (even though there is probably one, since the question to check 123-divisibility with a regex exists).
There are, however, some similarities in some strings:
123, 246, 492 and 984 in binary are basically the same, but 246 has an extra 0 in the end, 492 has two extra 0s in the end and 984 has three extra 0s in the end.
369 and 738 in binary are basically the same, but 738 has an extra 0 in the end.
615 and 1230 in binary are basically the same, but 1230 has an extra 0 in the end.
Any ideas for a regular expression for such strings? Thanks!

Here is a way that succeeds, albeit with a lot of work.

First, construct a DFA for the language. That is actually quite simple: It has states $0$ through $122$ (for the remainders), start state and only accepting state is $0$, the transitions from state $n$ go to $(2n \mod 123)$ for label $0$ and to $(2n+1 \mod 123)$ for label $1$.

Now, convert that DFA to a regular expression. The result is not likely to be simple, small or nice.

If you use an extension to regular expressions that allows intersection, you can also do the above with $41$ instead of $123$ and then intersect with the expression you have for divisibility by $3$.


Linear Search Algorithm - Why allow a user to input a start and end index to LS? Here is the linear search algorithm provided in class:

bool LinearSearch(int [] a, int l, int u, int e) {
      for(int i:=l; i ≤ u ; i := i + 1) {
          if (a[i] = e) return true;
      }
      return false;
}

If the intention of this function was to linear search through the function why allow a parameter of l and u? A user could test this function in ways to breach the intention of linear search. For example let l and u be numbers such that it only searches through a subsequence of the list and not the entire list. I asked my professor if the intention of this code was to have the possibility of it being used in ways that do not search the entire list. She didn't quite understand me, because she replied "No, it should be possible to search through the entire list." Well I know it's possible but why have the l and u if you can just write the code better and remove l and u. Now I know in other languages you might need to know the bounds, but this isn't a programming class whatsoever.

Surely, it is not about correctness. It is only a slightly general version of linear search. This technique is not uncommon. Obviously the more general the procedure is, the more applicable it is.

Linear search is a little bit simple for an illustration. Let's look at quicksort@wiki that is declared as quicksort(A, lo, hi). This is because quicksort is a recursive procedure that needs to call itself over a sub-range of the array. Notice that quicksort also needs a partition procedure, which is declared as partition(A, lo, hi) instead of partition(A).

Another kind of examples is dynamic programming. Suppose that you want to compute the edit distance@wiki between two strings of $a$ and $b$, with lengths $m$ and $n$ respectively. What you are actually computing is $\text{Dist}(i,j)$ for $0 \le i \le m, 0 \le j \le n$.


S/Kademlia dynamic crypto puzzle In S/Kademlia two crypto puzzles is used, one static and dynamic. The static is used to generate a key pair that makes an eclipse attack difficult to achieve, the dynamic to make Sybil attacks harder.

In the dynamic, I am very confused about the x which is found, since I can’t find any evidence for this ever being used again in the system, is it send along in a signature or what is it used to?

I do not think the paper mentions any use of it, I at least have not been able to find it, why I ask here for the use of x.

It's part of the solution to the cryptopuzzle.  The goal is to find $x$ that makes $P$ satisfy the criterion; once you've found such an $x$, you can verify that it is a valid solution (and so can anyone else).


Proof of APSPACE = EXP I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book.

Please give a semi-detailed proof of this. I have found a paper which has this proof(by Chandra, Kozen et al.) but found it too hard to understand.

I Asked this once and my post was closed. I remember saying i have no idea, and i'm in need of some enlightenment. Eventually i found the solution somewhere and i think that my problem was that i was not as comfortable as i thought with the ideas appearing in the proof of the Cook-Levin theorem.

The interesting direction is $EXP\subseteq APSPACE$. Let $L\in EXP$ be some language decidable in $2^{n^c}$ time, i.e. there exists a Turing machine $M_L$ which runs in $2^{n^c}$ time deciding $L$.

For any input $x$, we can look at the $2^{|x|^c}\times 2^{|x|^c}$ computation table of $M_L$ on x. The i'th row describes the $i'th$ configuration during the computation: $\sigma_1\sigma_2...\sigma_i q\sigma_{i+1}...\sigma_{2^{|x|^c}}$, where $\sigma_i\in \Sigma\cup \Gamma, q\in Q$. This means that at the $i'th$ step $\sigma_1...\sigma_{2^{|x|^c}}$ is the content of the working tape, we are at state $q$, and the head is at the symbol appearing after $q$ (we should also include the input somewhere, but specifics don't really matter here).

We denote by $C_{ij}$ the content of the cell in the $i'th$ row and $j'th$ column in the computation table of $M_L(x)$.

Our APSPACE machine will be able to decide whether or not $C_{ij}=\sigma$ (then you can go over the last row and check if $q_{acc}$ is written somewhere). Note that the index $i$ can be written in polynomial number of bits.

As in the Cook-Levin theorem, the important fact is that computation is local. The value of $C_{ij}$ is determined by the values $C_{i-1,j-1},C_{i-1,j},C_{i-1,j+1},C_{i-1,j+2}$, say by some known function $g$ ($g$ of course depends on the transition function of $M_L$), meaning:

$\forall \sigma\in\Sigma\cup \Gamma\cup Q: \hspace{1mm} C_{ij}=\sigma \iff \exists \sigma_1,\sigma_2,\sigma_3,\sigma_4: \hspace{1mm} C_{i-1,j-1}=\sigma_1 \land
C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4 \land \sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right).$

To decide whether $C_{ij}=\sigma$, under existential quantifiers, nondeterministically guess $\sigma_1,\sigma_2,\sigma_3,\sigma_4$. Verify that
$\sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right)$, if not reject.

The next step is to verify recursively that $C_{i-1,j-1}=\sigma_1 \land
C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4$. Let us denote by $S_i$ the space used by our machine, when it begins with the i'th configuration (i.e. verifying $C_{ij}=\sigma$ for some $j,\sigma$). Even if we use the same space for all four calls, you get $S_i=S_{i-1}+poly(|x|)=...=2^{|x|^c}poly(|x|)$. This happens because we keep a call stack (we dont overwrite the current frame), to overcome this:

under universal quantifiers, write nondeterministically $\left(J,\sigma_J\right)\in \left\{\left(j-1,\sigma_1 \right),\left(j,\sigma_2 \right),\left(j+1,\sigma_3 \right),\left(j+2,\sigma_4 \right)\right\}$ (suppose for simplicity that your machine has four transition functions), and output "yes" if $C_{i-1,J}=\sigma_J$.

The universal quantifiers allowed us to compute the conjunction of four recursive calls simultaneously, thus we dont need to keep a call stack. In that case, in all times we need only remember $i,j,\sigma$, which requires polynomial space (in the recursive call for $C_{i-1,J}$, we use the same space that was used to store $i$).


Proof: There exists an irregular language L such that LLLL is regular As title.

I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.

A senior gave me a hint that Lagrange's four square theorem might help, but I don't see how I can utilize it.

Thanks.

Let us prove a more general result:

  For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular.

The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is
$$
S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}.
$$
Let $1 \leq p \leq m-1$, and consider $p \cdot S$, i.e., the set of all sums of $p$ elements from $S$. Since all elements in $S$ are equivalent to either $0$ or $1$ modulo $m$, if $a \in S$ is equivalent to $p$ modulo $m$ then it must have the form
$$a = m^{k_1} + 1 + \cdots + m^{k_p} + 1. $$
The base $m$ representation of $a$ thus has at most $p+1$ non-zero digits (it could have fewer if some of the $k_i$ are equal). It is easy to check that a vanishing fraction of numbers have this property.

Let $L_{m,p} = \{ a^{km+p} : k \geq 0\}$. It follows that $L' = L^p \cap L_{m,p}$ is an infinite language with vanishing density, and so it cannot be regular (since regular unary languages are eventually periodic, and so if they have vanishing density they must be finite). Since $L_{m,p}$ is regular, it follows that $L^p$ isn't regular.

In contrast, $m \cdot S$ is cofinite — it contains all integers which are at least $m^2-1$ — and so $L^m$ is regular.

The language constructed above has the "regularity profile" $\{k : k \geq m\}$. This is the set of powers $k \geq 1$ such that $L^k$ is regular ($L^0$ is always regular). This prompts the following question:

  What regularity profiles are possible?

Any regularity profile is closed under addition, but are there any other constraints?


Karloff's algorithm applied to sparse graphs I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph.

Karloff [1, p.6] has given a map-reduce algorithm called "Finding  an  MST  of  a  Dense  Graph  Using Map-Reduce" which finds an MST of $G$ by randomly partitioning the vertices into $k$ different equally sized sets $V_i$ and then finding a MST for $V_i \cup V_j$ for all $i,j$.

will it provide correct output if we will apply this algorithm to a sparse graph, i.e., a graph for which $|E| < N$, instead of a $c$-dense graph? Will it work correctly?  If it will, why is the paper making the assumption  here $|E| = m \ge N^{1+c}$, if their algorithm works for sparse graphs too?

A Model of Computation for MapReduce. Howard Karloff, Siddharth Suri, Sergei Vassilvitskii.  ACM-SIAM Symposium on Discrete Algorithms, 2010.

I would suggest reading Theorem 5.1 and Lemma 5.1 on the same page in the paper. They answer both your questions.

The proof of Theorem 5.1 in the paper does not use the density of $G$. It will therefore also work for sparse graphs.

You are asking about the motivation behind the assumption of $G$ being dense. In this context the assumption is that a dense graph does not fit into the memory of a single machine. Lemma 5.1 and the conclusions after it show that the input size to the reducers is small enough to fit into the memory.


What is the name of this sorting algorithm? I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays.

Basically, it marches through the input array and for each new array component it inserts it into a sorted doubly-linked list. It has two optimizations:

each list node has a count; instead of adding a new node with the same key, existing node is reused by incrementing its counter,
the sort maintains a reference to the most recently accessed list node. This allows faster search for the next list node in case the two relevant keys are "close" to each other.

My question is: what is the name of that sort? (I believe I am not the first one to conceive it.)

What is the name of that sort?

There is no existing name for it, I would believe.

If I had to name it, its name could be "caching and counting insertion sort". Here are the considerations.

It is a kind of insertion sort since it maintains a single ordered linked-list all the way by inserting elements one by one into that ordered linked-list.
"Caching" and "counting" are the basic two features of that insertion sort. Caching tries to make it faster to find the right location to insert by taking advantage of possible locality coherence. Counting is a common strategy to deal with the situation when duplicates happen often. Both caching and counting are standard terms that are easily recognizable.
It happens that both words start with "c", which is helpful for reading and memorizing.
"caching" is put before "counting" since "caching" is a more distinguishing feature of the algorithm. It is better to make the name less similar to the existing counting sort.
This is not a very cohesive name, since there is no strong coupling between the two techniques used in that sort. The technique of caching could be applied to almost all kinds of sort. The technique of counting could be applied to almost all kinds of sort as well independently. The only meaningful connection between them is that if this caching technique improves the speed a lot, it is more likely that there are lots of duplicates, then the counting technique might be even more useful.
"Caching and counting insertion sort" or "caching-counting insertion sort" is, in fact, more like a description instead of a proper name.

I would not recommend a name like "curve sort" unless you can show me some direct or obvious connection between "curve" and that sort.

Should we name that sort?

Is that sort distinctive and cohesive enough to deserve a distinctive short name?

The combination of caching and counting might be distinctive enough. However, those two optimizations are not cohesive. In fact, it is reasonable to see the two as independent. Caching deals with locality while counting deals with duplicates. Each one of them can be removed or applied without affecting the other's usefulness or functionality. It is preferable to study either one of them separately. It is not preferred to give a name to a simple combination of two abstract features.

As said by Bulat, there could be dozens of variations we can make to each of the algorithms listed on this page or this Wikipedia article. In particular, the counting technique can be applied to most if not all of them. In most cases the variations don't get individual names. To be clear, not every variation get individual names that have become established or standardized. Of course, if you write an article to expound that sort, you can certainly give it a fancy cool name such as "curve sort" or "Rodionsort".

What else could be done?

In fact, it looks like more interesting to name a simplified version of your algorithm that does not use the counting technique "caching insertion sort" or simply "caching sort", since caching makes sense mostly with insertion sort.

There have been many discussions/articles about whether or how much certain sorting algorithms are cache-friendly. However, I have not seen a simple sorting algorithm that takes an explicit separate step in order to take advantage of the "smoothness" of the data, although it might be a simple step. The most similar step I have seen is the checking whether the given data have been sorted before or during sorting. Some complex sorting algorithms such as Timsort search for ascending or descending subarrays during sorting, which also use many other techniques. A simple algorithm called "caching sort" sounds attractive and pedagogical to me.

A slight generalization could be caching two elements instead of just one element. When a new element comes along, we could start searching the position for the new element from the cached element that is nearer to the new element. Then the sorting would be efficient for data stream that comes from two "smooth" sources that are mixed irregularly.

A further generalization could be caching even more elements with more involved caching policy. Or even layers of caches. Let me stop my brainstorming here.


Why bound of linear function is same as that of quadratic equation I am learning algorithms. So, I came along with something very interesting.

The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$.

This is same as for $an^2 + bn + c$. But shouldn't it be different?

$O$ only gives an upper bound; see also here. Clearly, $n^2$ is -- up to a constant factor -- an uppper bound for linear functions.

In fact, you can prove that

  $n^{k_1} \in O(n^{k_2})$ for all $k_1 \leq k_2$.

Together with

  $n^{k_1} + n^{k_2} \in O(n^{\max \{k_1,k_2\}})$ for all $k_1,k_2$

and the obvious

  $cn^k \in O(n^k)$ for all $c,k$,

you get a general version of your statement.


Prove not context free How can we prove that:

$$
L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\}
$$

is not context-free?

The language defines $w_1$ as a sub-string of $w_2$, and they are separated by a $\#$. This is easy with the CFG pumping-lemma for a slightly different language with $|w_2| \ge |w_1|$ by using the special case of $|w_2| = |w_1|$ (i.e. $w_1 = w_2$).

But here, $w_1$ is a proper sub-string of $w_2$ so I can't do the same. I fail to push the string out since we can always pump, for example the first symbol of $w_2$.

For large enough $p$, consider the word $w = 0^{p+1}1^{p+1}\#0^{p+1}1^{p+2} \in L$. Mark the part $1^{p+1}\#0^{p+1}$. According to Ogden's lemma, we can write $w = uxyzv$ such that $xyz$ contains at least $1$ and at most $p$ marked symbols, and $ux^iyz^iv \in L$ for all $i \geq 0$. The pumped part $xyz$ cannot lie all to the right of $\#$ since then pumping it down would result in a word not in the language (here we crucially use the fact that only the $0^{p+1}$ part to the right of $\#$ is marked). It also cannot lie all to the left of $\#$ since then pumping it up would result in a word not in the language. It follows that the part of $xyz$ to the right of $\#$ is of the form $0^k$, and the part of $xyz$ to the left of $\#$ is of the form $1^\ell$ (otherwise, there would be more than $p$ marked symbols). However, pumping up, the resulting word is not in the language. This contradiction shows that $L$ is not context-free.


Limit repetitions in randomized list with each unique element occurring n times I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.

So with elements [0,1,2] n = 4 and m = 3:
[1, 2, 0, 0, 0, 1, 1, 2, 2, 2, 0, 1] valid
[1, 2, 0, 0, 0, 0, 1, 2, 2, 2, 1, 1] invalid

The only solutions I found were to add all elements n times to a list and then shuffle until the condition is satisfied or generate the whole search space and then randomly sample from the correct solutions. Both seem possibly slow and memory intensive.
Could just be looking for the wrong terms, this has to be documented somewhere.

I came up with this approach, but am not sure about correctness.

E: set of elements e
n: of each element in sequence
m: maximum repetitions of one element
S = [] # empty sequence
while |S| < |E| * n:
    R = shuffled list containing each e m times
    for m:
        if s+r satisfies condition:
            S <- s+r # Extend s with r
        else:
            rotate r by one element
return the first |E| * n elements of S

It seems to produce correct results, but is it ok to sample and then rotate the subsequences R like that?
Would the time complexity be just O(|E| * n * m)?

Here is my python implementation:

def generate_sequence(e, n, m):
# Final sequence
s = []
# Extend s by n * len(elements) each iteration
for _ in range(n//m+1):
    r = list(e) * m
    random.shuffle(r)
    for _ in range(len(r)):
        # List of all windows of size m+1 where at least one element is from s or r.
        windows = filter(lambda x: len(x) == m + 1,
                         [s[-i:] + r[:(m + 1 - i)] for i in range(1, m + 1)])
        # check if any window contains an invalid sequence
        if not all(len(set(window)) > 1 for window in windows):
            # rotate r one to right
            r = [r[-1]] + r[:-1]
        else:
            # Valid s+r
            s.extend(r)
            break
return s[:len(list(e)) * n]

I will assume that by "random" you mean you want the output will be uniformly distributed on the set of all valid arrangements, or in other words, that all valid arrangements are equally likely to be output by the algorithm.

Simple method: rejection sampling

A simple approach is to use rejection sampling: generate a random arrangement, then check if it contains any element $m$ times in a row, and if so throw that away and repeat.

You can generate a random arrangement by starting with the list $[0,1,2,0,1,2,0,1,2,\dots]$ and then applying a random permutation to it, i.e., randomly shuffling it.

This will ensure the output is uniformly distributed.  It will be efficient if $m$ is large and inefficient if $m$ is too small.  In particular, if $m \ge \log_3 n$, then this should be pretty efficient; the expected number of times you repeat is $O(1)$.  On the other hand, if $m \ll \log_3 m$, then this becomes highly inefficient, because you have to repeat many times.

Sophisticated method: ranking/unranking

Here is a more sophisticated technique that will be more efficient if $m$ is small.  It works by counting the number of valid arrangements using dynamic programming, and using ranking/unranking techniques.

Let's start by looking at how to count the number of valid arrangements.  In particular, let $f(n)$ denote the number of valid arrangements of length $n$.  I'll show how to compute $f(n)$ using dynamic programming.

To aid with that, let $g(n,x,r,a_1,a_2,a_3)$ denote the number of valid arrangements of length $n$ that use exactly $a_1$ 1's, $a_2$ 2's, $a_3$ 3's, without repeating any number $m$ times in a row, and assuming that before these $n$ you have a sequence of $r$ $x$'s in a row (e.g., if $x=3$ and $r=2$, then a valid sequence is allowed to start with up to $m-r-1$ 3's, but no more than that).  Notice that

$$f(n) = g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3) + g(n-1,3,1,n/3,n/3,n/3-1),$$

so if we can compute the $g$'s, we can compute $f$.  Also there is a recursive relation among the $g$'s:

$$g(n,1,r,a_1,a_2,a_3) = g(n-1,1,r+1,a_1-1,a_2,a_3) + g(n-1,2,1,a_1,a_2-1,a_3) + g(n-1,3,1,a_1,a_2,a_3-1),$$

which is obtained by a case analysis on the first digit of the sequence, and symmetrically for other values of $x$.  (Here I assume we agree on boundary conditions like $g(\cdot,\cdot,m,\cdot,\cdot,\cdot)=0$.)

Now this gives a dynamic programming algorithm for computing $g$, by memoizing, and thus an algorithm for computing $f$.  What is the running time?  Well, there are at most $3m(n/3)^3 = O(n^3m)$ different subproblems, and solving each one can be done in $O(1)$ time using memoization, so the total running time is $O(n^3m)$.

Now that we know how to count, how do we use that to generate a random valid arrangement?  We'll use unranking.  Since there are $f(n)$ valid arrangements, we can think of each integer in the range $1..f(n)$ as corresponding to a valid arrangement.  We will construct an algorithm that can find the arrangement corresponding to a particular integer $i$; then all we need do is pick a random integer in that range, find the corresponding arrangement, and we have a random valid arrangement.

It's easy to use the recursive formula above to build an unranking procedure.  Given an integer $i$, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3)$; if yes, then the first number in the sequence is 1; if not, we test whether $i \le  g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3)$; if yes, then the first number in the sequence is 2, else it is 3.  We continue from there to iteratively fill in each element of the sequence.

This lets us pick a valid sequence uniformly at random.  The running time is $O(n^3 m)$, so it is efficient for all values of $m$.  You can even precompute all of the $g$ values in advance, in which case the running time becomes $O(n)$ per random sequence you want to generate.


Performance speedup with Amdahl's law Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is obtained?

I have two solutions for that:

1- Using Amdahl's law, We have

              1
 S= --------------------
      (1-alpha) + alpha
                  -----
                    n

So, we have 1/(0.7+(0.3/4)) where 0.7 is the fraction that is not affected. and 4 is the speedup of reducing CPI of SQRT from 8 to 2. That speedup will be 1.29.

2- We can calculate

CPI_avg = sigma( I * CPI_class )

and we know SQRT instructions are 300K and the rest are 700K. So

CPI_old = (300000*8 + 700000*3) / 1000000 = 4.5
CPI_new = (300000*2 + 700000*3) / 1000000 = 2.7

So, the speedup will be 4.5/2.7 which is 1.66

The question is, which one is correct? 1.29 or 1.66?

Amdahl’s formula assumes that you know the percentage of execution time, but you only know the percentage of instruction. The percentage of execution time is 53.33%, not 30%.

The approach “total time before, divided by total time after” also works in more complicated cases.