Colour a binary tree to be a red-black tree A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).

I was wondering if we can do something similar with Red-Black trees.

  Given an arbitrary uncoloured binary tree (with NULL nodes), is there a "fast" algorithm which can determine if we can colour (and find a colouring) the
  nodes Red/Black so that they satisfy all the properties of a Red-Black
  tree (definition as in this question)?

An initial thought was that we can just remove the NULL nodes and try to recursively verify if the resulting tree can be a red-black tree, but that didn't seem to go anywhere.

I did (a brief) web search for papers, but could not seem to find any which seem to deal with this problem.

It is possible that I am missing something simple.

If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.

Here's an algorithm to figure out the color of any node n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Here n.black-quota is the number of black nodes you expect to see going to a leaf, from node n and n.min-height is the distance to the nearest leaf.

For brevity of notation, let $b(n) = $ n.black-quota, $h(n) = $ n.height and $m(n) = $ n.min-height.

Theorem: Fix a binary tree $T$. If for every node $n \in T$, $h(n) \leq 2m(n)$ and for node $r = \text{root}(T)$, $b(r) \in [\frac{1}{2}h(r), m(r)]$ then $T$ has a red-black coloring with exactly $b(r)$ black nodes on every path from root to leaf.

Proof: Induction over $b(n)$.

Verify that all four trees of height one or two satisfy the theorem with $b(n) = 1$.

By definition of red-black tree, root is black. Let $n$ be a node with a black parent $p$ such that $b(p) \in [\frac{1}{2}h(p), m(p)]$. Then $b(n) = b(p) -1$, $h(n) = h(p)-1$ and $h(n) \geq m(n) \geq m(p)-1$.

Assume the theorem holds for all trees with root $r$, $b(r) < b(q)$.

If $b(n) = m(n)$, then $n$ can be red-black colored by the inductive assumption.

If $b(p) = \frac{1}{2}h(p)$ then $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$. $n$ does not satisfy the inductive assumption and thus must be red. Let $c$ be a child of $n$. $h(c) = h(p)-2$ and  $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$. Then $c$ can be red-black colored by the inductive assumption.

Note that, by the same reasoning, if $b(n) \in (\frac{1}{2}h(r), m(r))$, then both $n$ and a child of $n$ satisfy the inductive assumption. Therefore $n$ could have any color.


Constructing a Pixel Image from Rectangles and Row or Column Rotations The most recent challenge on Advent of Code involves constructing an image in a binary pixel array from a sequence of instructions:

rect AxB, which sets all of the pixels in a rectangle A pixels wide by B tall at the top left corner of the array.
rotate row y=A by B, which performs a circular rotation of row A by B pixels.
rotate column x=A by B, which performs a circular rotation of column A.

As part of solving the problem, I produced the following image:

####..##...##..###...##..###..#..#.#...#.##...##..
#....#..#.#..#.#..#.#..#.#..#.#..#.#...##..#.#..#.
###..#..#.#..#.#..#.#....#..#.####..#.#.#..#.#..#.
#....#..#.####.###..#.##.###..#..#...#..####.#..#.
#....#..#.#..#.#.#..#..#.#....#..#...#..#..#.#..#.
####..##..#..#.#..#..###.#....#..#...#..#..#..##..

This got me wondering:

How is the inverse problem solved? i.e. given an image, what sequence of instructions generates that image?
Are there any images which cannot be created with this set of instructions?
Is there a polynomial-time algorithm to find a minimal sequence of instructions that generate a target image? That is, where there is no shorter set of instructions that generates the same image.  If not, is there a polynomial-time algorithm for deciding if a given sequence of instructions is minimal?

I've done some Google searches but turned up nothing. I would appreciate any links to materials describing this or similar problems.

Yes.  For every image, there exists some sequence of operations that generates that image.

I'll describe how to implement a set (x,y) operation, which sets the pixel in the xth row and yth column (and leaves all other pixels unchanged).  It should be clear that you can construct any image you want by repeatedly applying this primitive.

Here's how to implement the "set (x,y)" operation using the 3 operations you gave us:

Rotate column y upwards by x-1 positions, so that position (x,y) moves to position (x,1).
Rotate row 1 leftwards by y-1 positions, so that position (x,1) moves to position (1,1).
Set the pixel in the upper-left corner (the pixel at position (1,1)).
Rotate row 1 rightwards by y-1 positions, so that position (1,1) moves back to (x,1).
Rotate column y downwards by x-1 positions, so that position (x,1) moves to position (x,y).

It is easy to see that each of these 5 steps can be done using one of your three operations, and that afterwards, the pixel at (x,y) is set and all other pixels are left unchanged.

This shows that given a image with dimensions mxn, we can create it using at most 5mn operations.  Of course, this sequence of operations probably isn't the shortest possible.  I don't know whether there is an efficient algorithm to find the shortest sequence of operations to generate a target image.


Algorithm - Wine Bottle Filling You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 litres. Both A and B can perform these operations:
- completely fill a wine bottle with wine
- completely empty a wine bottle
- pour the wine of one bottle into the other bottle, making sure to stop only when either the bottle being filled is full or if when the bottle being emptied is completely empty. Assume the litres of wine are all positive ints.

Q: Determine if there exist a seq of operations that leaves exactly k_3 litres of wine in the bigger wine bottle. Try representing this as a graph problem.

My idea: define the vertices to be a pair of integers in a graph. I got this as a recent interview question. But couldn't solve the entire problem in time. Then they said you could have apparently applied some algo to this problem too, and that it had a complexity that was fast enough. Any ideas?

Here's an efficient method that doesn't involve constructing a graph of the states and searching for a path to each target value. Let the capacities of the bottles be integers $K_1<K_2$, respectively, and denote by $(a_1, a_2)$ the current amounts in the bottles. You have six basic operations you can perform, for $i=1, 2$:

$f_i$: fill bottle $i$.
$e_i$: empty bottle $i$.
$p_i$: pour as much of bottle $i$ as will fit into bottle $3-i$.

We'll show this

  Theorem. If $\gcd(K_1, K_2) = 1$ (i.e., $K_1$ and $K_2$ have no factors in common), then you can start in state $(0,0)$ and end in state $(0, t)$ for any target integer $0\le t\le K_2$.

Consider these two sequences of basic moves, starting in state $(0, b)$:

Sequence $S$: if $b>K_2-K_1$, perform $f_1, p_1, e_2, p_1$.
Sequence $T$: if $b\le K_2-K_1$, perform $f_1, p_1$.

The result of $S$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(K_1-(K_2-b),K_2)\stackrel{e_2}{\rightarrow}(K_1-K_2+b,0)\stackrel{p_1}{\rightarrow}(0,K_1-K_2+b)
$$
and the result of $T$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(0, K_1+b)
$$
It's not difficult to establish that if $b>K_2-K_1$, the $S$ sequence will satisfy that the first component of each state will be less than or equal to $K_1$ and the second will be less than or equal to $K_2$ at each step and we can show similarly that the basic moves in the $T$ sequence are likewise always legal at each step.

For example, with $K_1=3, K_2=5$ we will have the following sequence of states:
$$
(0,0)\stackrel{T}{\rightarrow}(0,3)\stackrel{S}{\rightarrow}(0,1)\stackrel{T}{\rightarrow}(0,4)\stackrel{S}{\rightarrow}(0,2)
$$
so the sequence $T,S,T,S$ will generate the target values $0, 3, 1, 4, 2$, and of course we can always generate $K_2$ by a single $f_2$ move. Notice that we have generated all the target values $0\le t\le K_2=5$, as the theorem above indicated we should.

To show that this behavior happens for all integer capacities $K_1<K_2$ where $\gcd(K_1, K_2) = 1$, consider the second component values at each stage modulo $K_2$: an $S$ sequence takes $(0,b)\rightarrow(0, K_1-K_2+b)$ and $K_1-K_2+b\equiv K_1+b\pmod{K_2}$. Similarly, a $T$ sequence takes $(0, b)\rightarrow(0, K_1+b)$, so any sequence of $S$-$T$ moves starting at $(0,0)$ will produce the target values $nK_1\pmod{K_2}$, for $n=0, 1, 2, \dotsc,K_2-1$.

For our example, with $K_1=3,K_2=5$, we'll have the sequence of target values
$$
\langle\,0, 3, 6, 9, 12\,\rangle \equiv\langle\,0, 3, 1, 4, 2\,\rangle\pmod{5}
$$
All that remains to establish our theorem is to show that the $K_2$ elements of the target sequence are distinct. Suppose that they weren't, namely that there exist $n, m$ with $0\le n < m < K_2$ such that $mK_1\equiv nK_1\pmod{K_2}$. Then we would have $(m-n)K_1\equiv0\pmod{K_2}$ which would mean that $K_2$ would have to divide $(m-n)K_1$. However, $K_1$ has no factors in common with $K_2$ since $\gcd(K_1, K_2)=1$, so $K_2$ would have to divide $m-n$. However, $m-n<K_2$ and so the only possibility would be that $m-n=0$, i.e., $m=n$, contrary to our assumption. Thus, all the $K_2$ values in our target sequence are distinct, establishing our theorem.

Notes

For completeness, we note that if $\gcd(K_1,K_2)=g>1$ then you can make all and only those target amounts $ng$ where $0\le n\le K_2/g$, since we can reduce this case to one with capacities $K_1'=K_1/g,K_2'=K_2/g$ and observe that $\gcd(K_1',K_2')=1$.
Instead of the $S$-$T$ sequences, these can also be used:
$$\begin{align}
Q: &\text{if }b < K_1, \text{ perform }p_2,f_2,p_2,e_1\\
R: &\text{if }b \ge K_1, \text{ perform }p_2,e_1
\end{align}$$
The $S$-$T$ sequences might not produce a given target in the fewest number of moves. It may be the case that the $Q$-$R$ sequences will get to a given target value faster and vice-versa. It's possible, using the extended Euclidean algorithm, to determine which sequence choice will reach a particular target value quicker.
To generate all the possible target values by this method will take $O(K_2)$ time.
If you only want an answer to the interviewer's question, "is there a sequence of operations that leaves an amount $k_3$ in the larger bottle?" here's an algorithm that runs in time $O(\log K_2)$: if $k_3 > K_2$ answer "no", otherwise compute $g=\gcd(K_1, K_2)$ (which you can do in time $O(\log K_2)$) and if $g$ divides $k_3$, answer "yes", else answer "no".


Big-O of iterating through nested structure While trying to understand complexity I run into an example of going through records organized in following way:
data = [
  {"name": "category1", "files": [{"name": "file1"}, {"name": "file2"}],
  {"name": "category2", "files": [{"name": "file3"}]
]

The task requires to go through all file records which is straight forward:
for category in data:
  for file in category["files"]:
    pass

It seems like complexity of this algorithm is O(n * m), where n is length of data and m is max length of files array in any of data records. But is O(n * m) only correct answer?
Because even there are two for-loops it still looks like iterating over a global array of file records organized in nested way. Is it legit to compare with iteration over different structure like that:
data = [
  ('category1', 'file1'),
  ('category1', 'file2'),
  ('category2', 'file3'),
]
for category, file in data:
  pass

...where complexity is obviously O(n), and n is a total number of records?

A better bound on the complexity is $O(k)$, where $k$ is the total number of files.
A similar situation is encountered in algorithms for sparse matrices. Sparse matrices are stored as a list of all non-zero entries. The running time is often analyzed in term of the number of non-zero entries rather than the dimensions of the matrix. The reason is that matrices encountered in practice are often sparse (or can be sparsified), and we are interested in algorithms taking advantage of this.


Finding paths from the result of max flow Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That is, each set of paths will make the max flow.
But I suspect there could be multiple set of such paths.

Give the edges some value of priority. Once you have run a given maxflox algorithm, reduce the priority of a given edge by the amount of flow which got through the last time. This way edges which have gotten flow through them the last time running the algorithm will not be chosen as the first flow first this time and another way, if any, will be produced.


Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints Show that any $S \in NP$ has 2 different polynomial-time verifiers $V_1, V_2$ such that, for all $x,y$, the following conditions hold:

If $V_1(x,y)=1$ then $V_2(x,y)=0$
If $V_2(x,y)=1$ then $V_1(x,y)=0$

I show a guideline that say to define $V_i(x,y)=1$ if $y=p(|x|)+i$ and there exists a prefix $y'$ of $y$ such that $V(x,y')=1$ but I'm confuse to find how it help to find the solution.

Since $S \in \mathsf{NP}$, there is a non-deterministic poly-time Turing machine $T^*$ that decides $S$.
Given $x \in S$, let $y^* = \langle y^*_1, y^*_2, \dots\rangle \in \{0,1\}^*$ be the list of non-deterministic choices of $T^*$ that lead to an accepting state in the execution of $T^*(x)$.
It is easy to see that $|y^*| = O(\mathrm{poly}(x))$ and that $y^*$ is a certificate for the the polynomial-time (deterministic) verifier $V^*$ that, with input $V^*(x,y^*)$, checks that the (unique) computation path of $T^*(x)$  when the non-deterministic choices are those in $y^*$ leads to an accepting state.
Define $y_1 =\langle 0, y^*_1, y^*_2, \dots \rangle$ and  $y_2 =\langle 1, y^*_1, y^*_2, \dots \rangle$.
When $y=\langle y_0, y_1, y_2, \dots \rangle$, the verifier $V_i(x, y)$  behaves as follows: if $y_0 \neq i-1$, it rejects. Otherwise $V_i(x, y)$ simulates $V^*(x, \langle y_1, y_2, \dots\rangle)$ and accepts iff $V^*$ accepts. It is clear that $V_1$ and $V_2$ are polynomial-time verifiers for $S$ for the certificates $y_1$ and $y_2$, respectively.
It remains to show that they satisfy the additional constraints from your question.
Notice that, if $V_1(x,y)$ accepts, then $y_0=0$, and hence $V_2(x,y)$ rejects since $y_0 = 0 \neq 1 = 2-1$.
Similarly, if $V_2(x,y)$ accepts, then $y_0=1$, and hence $V_1(x,y)$ rejects since $y_0 = 1 \neq 0 = 1-1$.


prove correctness of in-order tree traversal subroutine I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction.

Claim: For any n-node  subtree, the in-order-tree-walk subroutine prints the keys of the subtree rooted at node x in sorted order.

in-order-tree-walk(x)
  if(x!=NIL)
    in-order-tree-walk(x.left)
    print x.key
    in-order-tree-walk(x.right)

Above pseudo-code is taken from CLRS, and we're traversing the subtree rooted at node x.

Proof. By ordinary induction. Let our induction hypothesis $P(n)$ be the claim itself. We need show $P(n)$ holds for all positive integers.
Base case ($n=1$): in-order-tree-walk subroutine prints the single node's key and, since the both left and right pointers are NIL, terminates. Trivially, single key is already in sorted order.
Inductive step: Suppose $P(n)$ holds for some $n \geq 1$. Prove $P(n+1)$. Let $T$ be subtree consisting of $n+1$ nodes. Let $T'$ be subtree formed by removing the largest element from $T$. $T'$ has $n$ elements. By induction hypothesis $P(n)$, in-order-tree-walk(T') prints keys of subtree rooted at T'.root in sorted order. By binary-search-tree property, largest element in the tree is placed on the rightmost node and it's the last node visited during the in-order-tree traversal. So, that rightmost node's key is printed after the keys of $T'$ is printed. Since it's the largest element in $T$, and keys of $T'$ in printed in sorted order, we can conclude that in-order-tree-walk(T') prints keys of $T$ in sorted order.
By induction principle, we can conclude that $P(n)$ holds for all positive integers.

Can we show correctness using this induction proof? Is any parts of the proof need to be revised? I appreciate your efforts.
EDIT: trees/subtrees in this post refer to binary search trees. Binary search tree property is preassumed

In your proof the largest element of binary search tree $T$ can in fact be the root of the tree. I did not check whether you took care of that.
If you want to use induction by a number of elements in the tree, I would advise you to take strong induction, that is the hypothesis assumes the algorithm works for any number less or equal to $n$. Then the hypothesis can be applied to both subtrees which must have less elements than the full tree.
Finaly you could use structural induction, that is induction using the inductive definition of the structures you consider. Here that is the notion of a binary tree: which is either empty, or a root and two subtrees. In practise this gives the same proof as strong induction, but you did not need to quantify the number of nodes.


Maximum Enclosing Circle of a Given Radius I try to find an approach to the following problem:

  Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the set. The running time should be $O(n^2)$.

At first it seemed to be something similar to smallest enclosing  circle problem, that easily can be solved in $O(n^2)$. The idea was to set an arbitrary center and encircle all point of $S$. Next, step by step, replace the circle to touch the left/rightmost points and shrink the circle to the given radius, obviously, this is not going to work.

I don't know how to solve this problem in $O(n^2)$ time, but an $O(n^2\log n)$ algorithm does exist.

Let $C(s_i)$ be the circle whose center is $s_i$, the $i$-th point, with radius $r$. It's not hard to find that the point set $P = \{p_0, p_1, \ldots, p_m\}$ can be enclosed by a circle with radius $r$ iff the intersection $I(P)$ of $C(p_0), C(p_1), \ldots, C(p_m)$ is not empty. Moreover, if $I(P)$ is not empty, there must be some points in $I(P)$ lay on some $\textbf{bd}C(p_i)$ (the boundary of $C(p_i)$). So for each $C(s_i)$ and each point $p$ on its bondary, we try to find how many circles contain $p$. The max count among all $p$ will be the answer to this problem.

Let's examine points in $\textbf{bd}C(s_i)$. There is an one-to-one mapping between the points on $\textbf{bd}C(s_i)$ and the real number in $[0, 2\pi)$. For each circle $C(s_j)$, the intersection between $C(s_j)$ and $\textbf{bd}C(s_i)$ can be represented by an interval $[begin_j, end_j]$. So for all circles other than $C(s_i)$, there are at most $n-1$ intervals (some circles may not intersect with $C(s_i)$). The max count can be found easily by sorting all $2(n-1)$ end points of interval, scanning them in order and counting the current overlapping number. For each $C(s_i)$, this step can be done in $O(n\log n)$ time, and there are $n$ such circles, so the time complexity of this algorithm is $O(n^2\log n)$.


algorithm for connectivity by path of given length Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm will return a shortest path between them.
BFS has time complexity $O(|V|+|E|)=O(|V|^2)$.
Now let $k$ be some fixed integer (not part of the input).
Is there an algorithm that takes $G$, $v,$ $w$, and checks whether there is a path between $v$ and $w$ of length $k$? What would be its time complexity?

The problem is NP-complete and referred to as Longest Path.  It is FPT, though, so you can solve it in time polynomial in $n$ for fixed $k$.
If you want to solve it in FPT time, the easiest solution is to do color coding.  The trick is two-fold.

Suppose that vertices are colored with $k$ colors, and you are looking for a rainbow-path of length $k$, i.e. a path where every vertex has different color.  This problem can be solved by dynamic programming!

Repeat the following step: Randomly color the vertices of the graph with $k$ colors, and run the rainbow algorithm.

With probability depending only on $k$, if there exists a $k$-path, then you will output a rainbow path.


In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$? In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex format. can we use $a^n b^n c^n d^n$ format for our guesses?

You cannot force the guesses in any way.

That said, in your case you can emulate a witness of this form. Let’s first replace your $n$ with $m$, reserving $n$ for the input length. Suppose that your algorithm runs in time $t(n)$. Then you can only go through the first $t(n)$ guesses, so without loss of generality you can assume that $m \leq t(n)$. Since $t(n)$ is polynomial, $\log t(n) = O(\log n)$, and so you have enough space on the tape to store $m$. You therefore proceed as follows:

Guess $m$ (by guessing $\log t(n)$ bits).
Simulate the guesses $a^mb^mc^md^m$ using a counter that goes up to $m$ and another one that goes up to 4.


Proving the pigeonhole principle in Cutting Planes Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf

  Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i<j\leq n$.

  Find a derivation of $\sum_{i=1}^n x_i\leq 1$ in $O(n^2)$ length.

If it were just algebra I could just show by contradiction that at most one $x_i$ could be 1 and be done but how does it translate it into cutting planes PS? I guess a similar idea would be by obtaining $\sum_{i=1}^n x_i \leq n-1 -(n-2)x_i$ for all $i$ through addition of $x_i+x_j$ for all $1\leq j\leq n$ but I'm stuck there.

Thanks for your help.

The proof is by induction. Here is the inductive step.

Suppose that we know both of the following inequalities:
$$
x_1 + \cdots + x_m \leq 1 \\
x_2 + \cdots + x_{m+1} \leq 1
$$
Add them to get
$$
x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2
$$
Add the axiom $x_1 + x_{m+1} \leq 1$ to get
$$
2x_1 + \cdots + 2x_{m+1} \leq 3
$$
Divide by 2 and round down to get
$$
x_1 + \cdots + x_{m+1} \leq 1
$$
I'll let you fill in the remaining details.


Data Structure for Set Intersection? Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?

Init an empty set.
Add an element to a set.
Given two set, report whether they intersect.

If each set maintains a record of what other sets exist, and you have a total of $s > 0$ sets, you can easily turn any data structure for a collection (e.g. binary search trees, etc.) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.

Each set should have a unique identifier from some totally ordered set. If you explicitly name your sets $S_1, S_2, \ldots$ then the identifier could just be the index.
You should implement a "registry" of the sets; a data structure which maintains a collection of all of the sets which you have defined. The registry should be implemented as a search-tree data structure, to allow easy retrieval (e.g. if you wish to delete the set) and linear-time traversal of the sets.
Each set $S_j$ also maintains an "index" of each of the other sets — not a copy of them, but rather a data structure which is indexed by the labels of the other sets. This index will be used to maintain, for each set $S_k$, a binary search tree of all of the elements of $S_j \cap S_k$. (The two sets $S_j$ and $S_k$ share one copy of that search tree.)

Initialization

Initialization of a set $T = \varnothing$ consists of $O(1)$ operations to initialize the tree of its elements, $O(s)$ operations as you initialize (copying from the registry) the index for the set $T$, and $O(s \log s)$ operations as you traverse the registry to add $T$ into the indices of each of the other sets $S_j$. In the index of $T$, we create search trees representing $T \cap S_j = \varnothing$ for the other sets $S_j$; we copy the same pointer for the index of $S_j$.

Adding an element to a set $T$

Adding some $x \in V$ to the set $T$ takes time $O(\log n_T)$ as usual, where $n_T = |T|$. We also test for membership of $x$ in each of the other sets $S_1, S_2, \ldots$, which takes time $$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$$ where $n = |V|$ is the size of the universe (or of the largest set $S_j$) and $s$ is the number of sets in the registry.
For each set $S_j$ such that $x \in S_j$, also insert $x$ into the index for the set $S_j \cap T$.
For each such set $S_j$, this takes $O(\log s + \log n_T)$ time, to look up  $S_j$ in the index of $T$ and to insert $x$ in $S_j \cap T$; across all sets $S_1, S_2, \ldots$ this takes time $O(s \log s + s \log n_T)$. If we suppose that the number of sets $S_j$ is much less than the size of the universe $V$ (that is, if we suppose $s \ll n$), the total time for element insertion is then $O(s \log n)$.

If you do not allow duplicates in sets, we can save time in the case that $x \in S$ already by forgoing the membership test and insertions for the other sets $T$. "Insertion" in the case that $x$ is already present then takes time only $O(\log n_T)$.

Intersection testing

The index of each set is maintained precisely in order to allow quick evaluation of whether or not two sets $S_j$ and $S_k$ intersect.
For a set $S_j$, simply by checking its index for the set $S_k$, we can not only determine in time $O(\log s)$ whether or not $S_j$ intersects $S_k$, but we can also retrieve a binary tree containing the entire set $S_j \cap S_k$.

Element Removal

To delete an element $x$ from a set $T$, we remove it not only from the search tree for $T$ itself, but from each of the intersections $S_j \cap T$ for the sets $S_j$ in its index. This takes time $O(s \log n_T)$, where $n_T = |T|$.

Set Deletion

Because of the overhead of searching the registry, if you have many sets, it may be desirable to delete sets once they are no longer needed.
By traversing the entire registry, we may delete $S$ from the index of all other sets $S_j$ in time $O(sn_T)$, dominated by the cost of deleting the search tree representing $S_j \cap T$ for each of the other sets $S_j$, where $n_T = |T|$.

Remarks

If you expect only to implement a constant number of sets, then the above run-times reduce to:

initialization: $O(1)$
element insertion: $O(\log n)$
intersection testing (and retrieval of the intersection): $O(1)$
element removal: $O(\log n_T)$
set deletion: $O(n_S)$

where $n$ is the size of the largest set in the registry, and $n_T = |T|$ for the set $T$ which you are operating on.

If you expect to have $O(|V|)$ sets, where $V$ is your universe, you may need a different data structure if you want these operations to operate in sub-linear time. However, if you have pairs of sets whose intersection you know you will never test, you might be able to reduce the size of the index for the sets (by not including any sets whose intersection you will test) or use more than one registry (one for each collection of sets whose intersection you might test). In fact, a registry is only useful if you want centralized control of ensuring that each pair of sets has a record of each other in the index: it may be practical in some cases, at the initialization of a set $S$, simply to record ad hoc each new set into the indices of the other sets $T$ whose intersection with $S$ you are interested in.


Practical importance of Turing machines? I am an electrical engineer, and only had one CS course in college 26 years ago. However, I am also a devoted Mathematica user.

I have the sense that Turing Machines are very important in computer science. Is the importance only in the theory of computer science? If there are practical implications/applications what are some of them?

The importance of Turing machines is twofold. First, Turing machines were one of the first (if not the first) theoretical models for computers, dating from 1936. Second, a lot of theoretical computer science has been developed with Turing machines in mind, and so a lot of the basic results are in the language of Turing machines. One reason for this is that Turing machines are simple, and so amenable to analysis.

That said, Turing machines are not a practical model for computing. As an engineer and a Mathematica user, they shouldn't concern you at all. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures.

In fact, from the point of view of complexity theory, Turing machines are polynomially equivalent to many other machine models, and so complexity classes like P and NP can equivalently be defined in terms of these models. (Other complexity classes are more delicate.)


Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them Or in other words, find all $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ or $w \rightarrow  v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ algorithm for this.

I can see how to identify if a given vertex meets these traits (perform a BFS starting at that vertex, then do another BFS on the reverse of that graph and see if every vertex was visited in those BFSes). The obvious solution would be to run this on every vertex of the graph, but that will end up being $O(|E||V| + |V|^{2})$.

I've considered identifying strongly connected components, but that doesn't seem like the right approach, since a SCC requires that $v$ and $w$ are mutually reachable, whereas this homework question requires that $v$ and $w$ are only reachable one way.

Advice?

We can assume that the DAG is connected, since otherwise the solution is trivial. Consider some topological ordering of the vertices. A vertex $v$ satisfies your condition if (1) $v$ can be reached from all vertices preceding $v$ in the ordering and (2) all vertices following $v$ in the ordering are reachable from $v$. We can check conditions (1) and (2) separately.

To check condition (2), traverse the topological ordering in order, and for each vertex encountered, remove the vertex. Since this is a topological ordering, when a vertex is removed, it is a source, that is, it has no incoming edges. Condition (2) is satisfied for the vertex iff it is the unique source at that point. Condition (1) can be checked similarly by traversing the topological ordering in reverse.


Does there exist a undecidable infinite language with only a finite undecidable subset? I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an infinite set of decidable elements?
In order to formalize this, let's build a deciding machine that answers $\text{YES}$, $\text{NO}$, or $\text{MAYBE}$. A correct decider for a language may always answer $\text{MAYBE}$, but if it answers $\text{YES}$ or $\text{NO}$ its answer must be correct. Such a decider can always be constructed for any (undecidable) language - in the worst case it simply always returns $\text{MAYBE}$.
Does there exist an undecidable language $L$ for which a correct decider exists that only answers $\text{MAYBE}$ for a finite number of elements of $L$?

Let $S$ be the set of elements on which the decider $T$ answers MAYBE. We can construct a new decider $T'$ which correctly decides $L$ as follows:

If the input is in $S$, answer the hardwired correct answer.
Otherwise, run $T'$.

Hence $L$ is decidable.
This actually shows that if $L$ is undecidable, then every decider for $L$ must make infinitely many mistakes.


Both $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ are not turing-recognizable? if we define $A_{TM}$ and $\overline{ A_{TM}}$ as follows:
$$
\begin{align}
A_{TM}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ accepts $w$} \}\\
\overline {A_{TM}}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ do not accepts $w$} \}\end{align}
$$
$\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ both are not turing-recognizeable. right?(a bit confused by the way $\overline{ A_{TM}}$ is defined. noramly $\overline A = \Sigma^*\backslash A$).
My reasons :
1.$\overline{A_{TM}}$ is not reconizable because: if it was then we could run two recognizer for $\overline{A_{TM}}$  and $A_{TM}$ in parallel and decides $A_{TM}$.
2. $\Sigma^*\backslash A_{TM}$ is not recongnizeable by fallowing lemma :
lemma:  $L$ and $\overline L$ recognizeable iff $L$ is decideable.
in fact both reasones are quite the same but in second one we are considring inputs ($\langle M,w \rangle$) which are not properly formated.

Usually the second language is denoted by $A_{\overline{TM}}$, exactly to avoid the confusion with the complement.
This is actually a common question, and it has to do with the encoding of TMs and words.
When we write $\langle M,w\rangle$, we mean that we give some agreed-upon encoding of a Turing machine and a word over its alphabet. We usually don't go to much into it, but it is agreed that the encoding is simple enough so that another Turing machine can easily parse it (where easily usually means either in logarithmic space, or polynomial time, or something of the sort).
Now, intuitively, in an agreed encoding, some words represent $M,w$ such that $M$ accepts $w$, some represent $M,w$ such that $M$ does not accept $w$, and some are meaningless gibberish.
When the encoding is easy to parse, we can kind of ignore this gibberish. However, it does pose a small problem when we start complementing languages.
Indeed, $\Sigma^*\setminus A_{TM}$ should, formally, also contain all strings that are not legal encodings.
However, since determining whether an encoding is legal is easy, then it doesn't effect the recognizability or decidability of the language. You can always start by checking the legality of the encoding, and accept if the encoding is illegal.
There is another way around it, which I like: you can define the encoding such that every string is a legal encoding. You do that by using some encoding of your liking, and adding to it the statement that any string that is not a legal encoding is now interpreted as some fixed TM $T$ and the empty word. Then, you actually get that $A_{\overline{TM}}=\overline{A_{TM}}$, and the problem goes away.


minimum and maximum nodes of MultiWay tree of height h I know that it doesn’t have to be balanced so in theory given that the height of
the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first level "doesn’t count" in the height, I should have $h+1$ nodes.

The maximal number of nodes in a $M-way- tree$ should be $\Sigma^h_{i=0}  M^i$, when $i$ is the tree level.

Is this correct ? Thank you!

This looks correct.

Note that the sum of the geometric series can be expressed more concisely:

$$\sum\limits_{i = 0}^{h} M^{i} = \frac{M^{h + 1} - 1}{M - 1}$$


Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.

The professor hasn't given the correction.

I have seen similar questions but the condition is different, I can't find the grammar. Is it possible to prove that it is not context free?

EDIT: taking inspiration from other slightly similar solved question, here's my solution, but I think it could be factorized/improved

S -> S1 | S2
// S1 is the case where I will try to pair a with c (i.e when there more c than d), S2 is the case where I will try to pair d with b (i.e when there are more b than a)
S1 -> XY
X -> aXc | Z // for each a generate a c
Z -> aZb | epsilon // for each a generate a b
Y -> cYd | epsilon // for each d generate c
// since all the b's have been generated along with a's, i did not find a way to pair d's with b's
S2 -> UV
U -> aUb | epsilon
V -> bVd | W
W -> cWd | epislon

Note if $n<m$, we can write $a^nb^mc^qd^p$ as $a^nb^nb^xc^qd^{x+q}$ where $n,x,q$ are independent of each other. Otherwise, we can write $a^nb^mc^qd^p$ as $a^{m+y}b^mc^yc^pd^p$ where $m,y,p$ are independent of each other.

So the grammar can be $S\rightarrow S_1S_2\mid S_3S_4$, where $S_1$ generates $a^nb^n$, $S_2$ generates $b^xc^qd^{x+q}$, $S_3$ generates $a^{m+y}b^mc^y$, and $S_4$ generates $c^pd^p$. They are all easy to construct.


Graph partitioning with parts of equal size Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.
Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.

I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.

Your problem is a special case of graph partitioning. When $k=2$, the problem is known as minimum bisection, and is NP-complete.


Mathematics topics or fields that increase computer programming proficiency? Generally computer programmers who are mathematicians or have mathematics background are very good in terms of algorithms and computer programming in general.

What I am not saying:

Mathematics is needed to be a good computer programmer.
Mathematics is necessary for programming.
Good mathematicians are good programmers and vice versa

What I am saying

I would like to learn some mathematics because I believe it will make me a better programmer. What areas/topics of mathematics will help me to become a better programmer? Answers of the form math topic - corresponding cs area will be appreciated.

NB: I asked this on StackOverflow where it was declared off-topic. I want to learn it during my spare time just the way I have been doing with computer programming. Thanks in advance.

So, there are many fields of math that are relevant to the Science of CS, but for programming specifically:

Graph theory: this is the big one. Graphs and trees are everywhere. Networks, maps, paths in video games. Even things like solving a Rubiks cube can be modelled as a graph algorithm and solved with A*.
Discrete math: aside from graph theory, knowing this area in general is helpful. It's full of proofs by induction, which are very useful for understanding recursion, which is very useful in programming, particularly with data structures. Knowing about sets, counting, inclusion-exclusion, boolean logic, etc. can come in handy once in a while.
Type theory: unsurprisingly, knowing type theory helps with understanding programming in typed languages, and more broadly, with using types as a way of ensuring certain correctness properties. Knowing about the theory of subtyping helps you to understand covariance and contravariance in Java-like languages. Knowing about things like parametric polymorphism is obviously helpful when learning a type-heavy language like Haskell or Purescript, but langauges like Scala, TypeScript, and Rust are becoming more prevalent in industry, and types are at their cores.

If you take this one to its extreme, you get things like Coq and Agda and Idris, which can be used to prove extremely precise correctness properties about programs.
Computability and Complexity Theory: knowing when a problem is either unsolvable, or NP-hard, is useful, because you won't waste hours racking your brain for a fast way to do it. Likewise, knowing some of the theory behind approximation algorithms, fixed-parameter tractability, or low-base exponential algorithms, can help when you really need to solve an NP-hard problem.
Automata theory: many problems can be modelled with various state machines, so understanding their properties is useful.

There are also some field-specific areas:

Statistics: If you're doing machine learning or big-data, this is a must.
Linear algebra/vector calc: both of these are important for machine learning, graphics, simulations, or image/audio processing.
Lattice theory: if you're doing any work with compilers or program optimization, this one comes up all the time. Fixed points everywhere!
Category theory: not needed to code, but useful for anything deeply drenched in type theory.

Edit: can't believe I forgot:

Cryptography: if you're interested in security, hashing, digital signatures and such, then make sure to learn some number theory, Group Theory, Field theory, elliptical curve Theory, etc.


Is it possible to construct a finite state automata for a decimal adder? Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is accepted, but 2#97#104 is not. Is it possible to find a finite automata for such a language ?  I cannot fathom how decimal addition could be carried out using a DFA .

Interestingly, the question in the body has a negative answer, but the question of the title has a positive answer, if you choose the appropriate representation for the data.
Let me explain this for a binary adder (I let you generalize the argument for a decimal adder). First represent the numbers $x$ and $y$ to be added in reverse binary, with a final $0$ and make sure they have the same length by adding further $0$'s at the end if needed.
For instance, $22 = 2 + 4 + 16$ would be represented by $011010$ and $13 = 1+4+8$ by $101100$. Their sum $35 = 1 + 2 + 32$ is represented by $110001$. Now, just read this data column by column
\begin{matrix}
22 \to &0&1&1&0&1&0\\
13 \to &1&0&1&1&0&0\\
35 \to &1&1&0&0&0&1
\end{matrix}
to get
$(0,1,1)(1,0,1)(1,1,0)(0,1,0)(1,0,0)(0,0,1)$. Taking all representations of the triples $x, y, z$ such that $x + y = z$, you get a regular language on the alphabet $\{0,1\}^3$, recognised by the following automaton

The trick behind this representation is that addition can be obtained by a sequential transducer.


Finding a partition with minimum "maximal length" We're given $n^2$ different points in $(0,1)$ : $x_1<  x_2 < \dots < x_{n^2}$.

We are required to choose $n$ points $x_{i_1}<\dots<x_{i_n}$ such that the value of $\max\,\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n} - x_{i_{n-1}}, 1-x_{i_n}\} $ is minimal.

It feels a lot like a dynamic programming problem, but I didn't manage to divide it into appropriate subproblems.

Any ideas?

This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:

   How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question.

This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are the subproblems stated explicitly.

   Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$?
 $$ m(w,k) := \min_{i_0 = 0,\,i_k = w,\,i_1\lt\cdots<i_k} \max\{x_{i_1} - x_{i_0},\,x_{i_2}-x_{i_1},\,\cdots,\,x_{i_k} - x_{i_{k-1}}\} $$
 What is the technique? We replace the last item $1-x_{i_n}$ with $x_k - x_{i_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'<w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x_{n^2+1} = 1$.


Algorithm for Dynamic Client Side Throttling Problem

I am trying to come up with an algorithm that will dynamically throttle a client's number of outstanding requests based on the response times of completed requests. Response times are unpredictable and can be between 7 and 90 seconds. The response times are greatly affected by the total of outstanding requests, if the server is flooded it bogs down and times increase to very long times.

My specific scenario

My client application has several http requests it needs to send to a server (actually 3 servers that are load balanced and use a round robin distribution, the number of servers and the code running there are out of my control). Each request is a flat object containing 25 parameters. The server uses the parameters to do several look ups which may or may not trigger other look ups and calculations, this is where the server processing time is variable. The server returns a list of corresponding results which can be 0 to approximately 25 in length for most results.

What I have tried

I created a rolling average class that keeps the response times of the last X number of responses and can give the average at any point. Then when each response is received I compare its response time to the average. If the response time is equal or less than the average I increase the number of allowed outstanding requests. If the current response time is greater than the average I decrease allowed outstanding requests.

This approach worked somewhat in scaling up but I had cases where the average just grew over time and allowed more and more outstanding requests which brought everything to a crawl.

I have an implementation question on stackoverflow if you want more details on how I am doing this in code minus the rolling average part.

https://stackoverflow.com/q/30263716/1168353

I have been using a mocked out version of the server that just sleeps a thread before returning a response. I pick a "bestWaitSeconds" that is the fastest time it can return and a "MaxRequestsBeforeDegradation" that determines the maximum number of requests before times increase, anything below that returns bestWaitSeconds. The degradation formula looks like the below and only applies when "currentRequests" is more than MaxRequestsBeforeDegradation.

secondsToWait = (currentRequests - MaxRequestsBeforeDegradation) * (r.NextDouble() + .5) * bestWaitSeconds;

The random is just a way to apply the unknown return time stated in the problem. Times do go well above 90 seconds when the server is overloaded. This formula isn't exactly what the server does but it conveys the idea I think.

So basically the algorithm needs to get as close to MaxRequestsBeforeDegradation as possible. In the real case that MaxRequestsBeforeDegradation would change over long amounts of time so the algorithm also needs to adapt and explore up and down to continually know where the best number of outstanding requests is. Hope this helps.

Summary

How can I dynamically find the optimal number of outstanding requests allowed at a given moment to get the greatest throughput, given only a history of response times?

this is a fairly basic problem in control theory and there are "design patterns" in this area to handle this type of system, and think there is probably an example right out of a control theory book very close to your question. basically the theory involves a concept somewhat like the way a thermostat regulates temperature in a house. if the house is too hot, the heater shuts off, if is too cool, it turns on. you want something like the opposite where more delay ("throttling") is applied when there is greater load, however the principle is the same.

a basic solution is something like this. keep track of the minimum response time, this is a "baseline". now measure the current instantaneous difference between the minimum response time and current response time, this is roughly proportional to "load". now one does not one long-past load to influence current load readings. but neither does one want a large current spike in load to effect the throttling too much. the immediate idea here is to use a exponential running/ moving average of the load measurements to determine the throttling (this metric is used a lot in stock trading algorithms). exponential averages have a tunable continuous parameter (0..1) that basically weights between current and past values, at one end the past values are weighted lighter, at the other end the current value is weighted heavier.

my suggestion is to try this algorithm for different weighting values and then graph the results. notice a lot of web load problems vary over daily rates where midday or midweek have highest load. in that case a changing weight value might be more optimal. a basic strategy to figure out the general trend of cycles in input load would be to have no throttling and then just look at daily or weekly loads.

note that some round-robin routers are automatically doing something like basic load balancing because they do not route to already busy connections.


Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered? Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions?
It is something which I have been unclear with for a while (from a Computability Theory POV).

No - even within (say) the class of $\Sigma_1$ (= c.e., r.e., semidecidable, ...) sets, there is lots of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions).
The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing degree is strictly between ${\bf 0}$ (= computable) and ${\bf 0'}$ (= halting problem)? This was answered about a decade later by the Friedberg-Muchnik theorem, which showed that there are Turing-incomparable (so a fortiori many-one-incomparable) c.e. sets. Their argument generalizes immediately to get a countably infinite sequence of Turing-incomparable c.e. sets. Later, Sacks proved that whenever we have c.e. sets $A<_TB$ we can in fact find a sequence $(C_i)_{i\in\mathbb{N}}$ of c.e. sets which are Turing-incomparable to each other and which all lie strictly between $A$ and $B$ in terms of Turing reducibility (this is basically his density theorem + a bit of elaboration). Note that Sacks' theorem also shows that there are infinite increasing and infinite decreasing sequences of Turing degrees as well as infinite antichains.
So there is extremely rich non-linearity there. In fact, though, that's only the beginning of the story. The structure of $\mathcal{R}$ (= the Turing degrees of c.e. sets, ordered by Turing reducibility) turns out to be extremely complicated, and there are still many major open questions about it. Soare's old book Recursively enumerable sets and degrees contains a lot of information on the topic, which really picks up in earnest at chapter $7$ (where priority arguments, the method developed by Friedberg and Muchnik and later elaborated by Sacks and others, are first introduced); Soare also wrote a medium-length survey paper on the topic.

EDIT: Even though it's not directly related to the OP let me address a common related question: namely, how the c.e. degrees (= Turing degrees of c.e. sets) sit inside the poset of all Turing degrees.
We know that every c.e. set is Turing reducible to the halting problem, so every c.e. degree is $\le_T{\bf 0'}$. The converse however is false: there are degrees below ${\bf 0'}$ which are not c.e. degrees. There is a "syntactic" characterization of $\{{\bf d}: {\bf d}\le_T{\bf 0'}\}$ but it's more complicated; see here.
(Incidentally, the easiest way I know to prove the existence of a non-c.e. degree below ${\bf 0'}$ is to $(i)$ prove Sacks' density theorem and $(ii)$ construct a minimal noncomputable degree below ${\bf 0'}$. This is rather a lot of work, but as far as I know there's no easier way of doing this!)
There is however a sense in which the degrees below ${\bf 0'}$ are "c.e. in flavor." Specifically, say that a set $X\subseteq\mathbb{N}$ is $2$-c.e. if $X=A\setminus B$ for c.e. sets $A,B$. We can similarly define $3$-c.e. and $n$-c.e. sets for all finite $n$, and even continue this into the transfinite in a precise sense. The resulting "hierarchy" (scarequotes since it's not linear!) is called the Ershov hierarchy, and with help from the limit lemma we can show that every set computable from ${\bf 0'}$ is $\alpha$-c.e. for some ordinal (or rather, ordinal notation) $\alpha$. The fact that $\le_T{\bf 0'}$ doesn't imply c.e. is extended by a general, if somewhat technical, non-collapsing result for the Ershov hierarchy; for example, there is a $2$-c.e. set not Turing-equivalent to any c.e. set (which I believe is due to Cooper).


Difficulty understanding the faster multiplication hardware This is a picture of faster multiplication hardware taken from Computer Organization and Design (5th Edition). I'm having some difficulty understanding it. I was trying to simulate this for a test multiplication of : 1011 x 101. Firstly, P0 is simply the LSB of the (Mplier0 * Mcand) which gives P0 = 1 The two operands of the upper rightmost adder would be then, 1011 (Mplier0 * Mcand) and 0000 (Mplier1 * Mcand) which would produce the result 1011 with P1 = 1. This 1011 would then be one of the inputs of the second stage adder. The other input of the second stage/level adder would come from the upper 2nd rightmost adder. Which gives 1011 (Mplier2 * Mcand) + 0000 (Mplier3 * Mcand) = 1011. So the two inputs of the second stage adder are both 1011. Finally the output of this second stage adder will be 1011 + 1011 = 10110. The penultimate result is 1011011. But the correct answer is 110111. What am I doing wrong here?

You want to multiply x by y, where both are 32 bit numbers.

The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 bits. The second number is x if bit #30 of y is 1, and 0 if bit #30 of y is 0. This number is shifted by 30 bits. And so on. The last number is x if bit #0 of y is 1, and 0 if bit #0 of y is 0. This number is shifted by 0 bits.

So you have 32 numbers to add. You use 16 adders in parallel to add the first and second, the third and fourth, the fifth and sixth number and so on. You get sixteen 34 bit results. Next you use 8 adders in parallel to each add two of these sums. Then 4 adders in parallel, then 2 adders in parallel, then one adder to get the final result.

Obviously you figure out how big each result can be, and where you would be adding zeroes (which obviously don't need adding). In total you need 31 adders, five levels deep, so the delay for the multiplier is about five times that of a 32 bit adder.

(BTW. There are methods that can get the result faster and I think with less hardware).


How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:

How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as well?

Suppose you have an algorithm that decides membership in $L$ in polynomial time (by assumption since it's in $P$). You can easily write an algorithm that uses the previous one for deciding membership in $\bar L$ and prove that it takes polynomial time.


Polynomial time algorithm to find an induced cycle in non-chordal graph Let $G=(V,E),n=|V|,m=|E|$ be a graph. There exists an algorithm with time complexity $O(n+m)$ to test if given graph $G$ is chordal. If I know the graph is NOT chordal, is there a algorithm to find any of the cycles without a chord of length $k\geq 4$ (running in polynomial time of course)?

Since I found a solution myself, I'm gonna post the idea. It suffices to find chordless paths. For a vertex $v$ and $u$ its neighbour, we can delete the edge $\{u,v\}$ from $G$ and find a chordless $u$-$v$ paths. Connecting these will result in a chordless cycle.
A very simple algorithm finding such paths is described here. Naive algorithm runs in time $O(n(n+m))$ per $u$-$v$ path, they further give more efficient algorithm with running time $O(n+m)$ per $u$-$v$ path.


How do we analyze Algorithms with parallelism features As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, while most of cases in the area that I am working on is optimized.
The second though is, I am using "Python-Maps" (and other parallelism features, but let's take just "map no python as an example" to simplify the question) to implement the first algorithm, while I don't use parallelism features in the second algorithm.

What is the approach to compare, abstractly, the both algorithms ?. Can you please give any hint ?

The conceptual/abstract model I use when developing a parallel algorithm is (loosely) Leslie Valiant's Bulk Synchronous Parallel model.

You have $P$ processors (where $P$ is typically some small number like 4, 8, 16, maybe 128, but certainly $P \ll N$).  You are trying to design an algorithm where you spend most of your time computing in parallel, then you use a barrier to synchronize the processors, then do some communication between processors, synchronize again, and then go on to the next parallel computation step.  It is called bulk synchronous because you can think of the algorithm as a series of steps where the work inside each step is completely asynchronous, but the steps happen one at a time and in order.

There are a handful of different things you need to worry about that all interact and have inescapable tradeoffs.

Algorithm efficiency.  You should have a best sequential algorithm you are using as a baseline.  Often the best sequential algorithm won't parallelize well (because of all the rest of this list) so your parallel algorithm may require substantially more work.  For example: There are often clever sequential algorithms that are $O(N \log N)$ where the only realistic parallel algorithms are $O(N^2)$.  Alpha-Beta pruning tree search algorithms are another case where you may need to do (significantly) more work to avoid synchronization/communication overheads.
Work independence. You need to choose an algorithm where, in each bulk step, there are approximately $O(N)$ (or more) independent pieces of work to do.
Load imbalance.  During each step of the algorithm you want to break the work into $P$ nearly-equal chunks.  If the chunks are unequal then each bulk synchronous step will take the amount of time for the largest chunk and many of your processors will spend a significant portion of their time idle.  Examples of load imbalance problems happen with:

divide and conquer algorithms (the first step has to happen on one processor, then you get two (perhaps unequal chunks) so the second step happens on two processors.  It takes $O(\log P)$ steps to get all $P$ processors working, and the amount of work they are doing may not be similar, let alone the same.)
hashing algorithms (it depends on whether your hash function is distributing the data evenly among hash buckets or whether there is some bias.  The bias ends up as load imbalance.)
sparse graphs and sparse matrices.  (Similar to the hashing problem.  It may be easy to divide up the number of nodes in your graph evenly, but the number of edges per node determines the amount of work so two chunks with similar numbers of nodes may have very different amounts of work involved.)

Synchronization overhead.  Synchronization is "pure overhead". It is added cost for parallelization that simply isn't required in the sequential algorithm.
Data communication overhead.  This one is quite tricky because it interacts with a problem (cache locality) that is quite difficult in the sequential case as well.
Reductions.  Often some of your work looks unavoidably sequential, but involves associative operators that can be mostly parallelized (with some cleverness, and assuming that your hardware supports it.)  Similarly you sometimes have operators that are (a) associative, (b) commutative and (c) applied sparsely, in which case it may be possible to parallelize a chunk of code using fine-grained mutual-exclusion (locks).
SIMD hardware limitations.  The Bulk Synchronous Parallel model is single-program-multiple-data (SPMD).  In each chunk of work between barrier synchronizations each processor has something like $O(N/P)$ work to do, and that work may require a substantial amount of data-dependent branching.  But most modern parallel hardware exposes a substantial fraction of its parallelism only with single-instruction-multiple-data (SIMD) short-vector units.  This means that you have to go beyond the work independence in step (2) above.  You have to find work to do that is not just independent but where there are few (hopefully none) data-dependent branches for each chunk of work.
Accelerator data marshalling.  This is starting to get better, but for the moment many parallel accelerators (GPGPUs) require you to move data back and forth between the accelerator and the processor at each barrier synchronization point.  This means that you need to find more work independence to make the cost of using the accelerator break even.

That's a lot to keep in mind, but you can often think about it a little more simply.

Rewrite the sequential code using the least clever algorithm you can think of.
Look for the loop nest where you are spending most of your time (use a profiler.)
Choose the outer-most loop where the iterations are independent of one another.
Turn that loop into a parallel-for (using whatever method your programming language and/or libraries provide.)
Hope that everything else works out.


Maximum integer in a sorted list which also is in an unsorted list If I have a sorted list $A=[a_1, \dots, a_n]$ such that the integers $a_1\leq a_2\leq\dots\leq a_n$, and an unsorted list $B=[b_1, \dots, b_k]$, which includes at least one integer also in $A$, can I then find the maximum integer in $A$ which also is in $B$ in $O(k\log n)$ time? If so, how?

Are you familiar with binary search? If not, look that up. It has complexity $O(\log n)$ and will find you the index $i$ where you would insert $x$ into $A$ to maintain sorted order. From this you can instantly see whether $x$ already exists in $A$ by checking whether $A[i] = x$.
Then, do this for $b_1, b_2, \dots$, checking for each whether it is in $A$ in $O(\log n)$ time, and if yes, whether it is bigger than the current best found.
You do this $k$ times to find the biggest element that is in both $A$ and $B$ in $O(k \log n)$ time.

You can even be a bit smarter, like such:
lo = 1
best = A[1] - 1
for b in B:
    if b > best:
        i = binary_search(A, lo, n, b)
        if A[i] == b:
            best = b
            lo = i + 1

This doesn't change the worst case complexity but will avoid needless binary searches, and make the bounds on the binary searches that you do tighter.


Question on interpreting logical notation, relating to alphabets, theoretical comp sci $\exists x \in \Sigma^* (t=sx)$

Have I interpreted the above into words correctly?:

"There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, where sigma contains string 't', which is a concatenation of string x and string s."

I'm not clear on how/whether t=xs is an alphabet.

Note: an earlier version of this question, with some errors, was posted at Math.SE.

Since $t$ and $s$ aren't quantified, the expression $\exists x\in\Sigma^*\;(t=sx)$ is a predicate $P(s, t)$ in inputs $t$, and $s$. In other words, we could write
$$
P(s, t)\stackrel{\text{def}}{\equiv}\exists x\in\Sigma^*\;(t=sx)
$$
meaning "$P(s, t)$ is true if and only if there is a string $x$ over $\Sigma$ for which $t$ is the concatenation of $s$ and $x$". In answer to your question, $t=sx$ isn't an alphabet, but is a condition, namely that $t$ (a string) can be expressed as the string $s$ followed by the string $x$.

Look at some examples, with $\Sigma = \{a,b\}$,

Is $P(a, abb)$ true? It is if we can find a string $x$ such that $abb=ax$. Obviously $x=bb$ works here, so $P(a, abb)$ is true.
Is $P(ba, abb)$ true? It is if we can find a string $x$ such that $abb=bax$. There's no $x$ we can use here, so $P(ba, abb)$ is false.

In general, it's not hard to see that $P(s,t)$ can be interpreted as "$s$ is a prefix of $t$".

In a different universe of discourse, if $s, t, x$ were integers, can you see that $\exists x\in\mathbb{N}\;(t=sx)$ would mean that $s$ divides $t$?


Difference between $NP\cap coNP$ and $NEXP\cap coNEXP$ $NP\cap coNP$ is low for itself: $NP^{NP\cap coNP}\cap coNP^{NP\cap coNP}=NP\cap coNP$.

Going up to exponential realm, we are considering similarities of $NP\cap coNP$ to its exponential version $NEXP\cap coNEXP$.

By padding, we already have $$NEXP^{NP\cap coNP}\cap coNEXP^{NP\cap coNP}=NEXP\cap coNEXP$$

Two questions:

Though it is unlikely, I do not know for sure whether $NEXP\cap coNEXP$ is low for itself: $$NEXP^{NEXP\cap coNEXP}\cap coNEXP^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$
Being more moderate in using oracle machine, we may ask whether $$P^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$

NO. Assume to the contrary that we have that equality, the LHS contains $EXP^{EXP}=EEXP$. So, we deduce that $NEXP=EEXP$.But then the LHS can even contain $EXP^{EEXP}=EEEXP$. That is way too much over $NEXP$.
YES. By the same proof for $P^{NP\cap coNP}=NP\cap coNP$, the NEXP machine simulates the oracle machine by guessing the oracle answer and the corresponding certificate of membership (non-membership) and verify by the verifier (refuter, resp.) of the NEXP (coNEXP, resp.) machine for the language of the oracle. Then, if at any time the certuficate does not prove the guess, refute and halt. Otherwise, return the same answer as the oracle machine.

Similarly for the coNEXP machine, but you have to accept if a guess is not proven by the certificate guessed after it.


Software code generation from the (operational) semantics - reference request for automatic programming Are there research trends that try to research code generation directly from the (operational or some other kind of) semantics? One can imagine cognitive architecture that discovers and reasons about the tasks that the software should do and constructs the operational semantics of some program. And later there should be only one additional small system that generates software code from the semantics for the execution on well established platforms.

In such a way one can avoid the uncertain and rigorous path that goes through discovery and generation of formal specification that requires rigorous reasoning (sometimes undecidable, sometimes exponentially hard). Use of cognitive architecture and generation of the operational semantics (or some other semantics) allow one to do approximate, uncertain reasoning which cancels undecidability or exponentiality by discovery of additional axioms or shortcuts.

This is reference request question. Of course, I can use Google, but my experience is that computer science often names the research themes and terms differently than I have them imagined firstly and there is no reliable semantic search. So - reference request is necessary.

I haven't seen anything on this but the closest I could find is Evolving Algebras:

Evolving Algebras: An Attempt to Discover Semantics
Evolving Algebras: Mini-Course
Communicating Evolving Algebras

In that mini course there are several papers outlining different aspects and applications of the Evolving Algebra. From one of them:

  In 1988 Yuri Gurevich has discovered the notion of evolving algebra in an attempt
  to sharpen Turing's thesis by complexity theoretic considerations (see
  [22]). Through numerous case studies (see [4] for an annotated list which is
  complete up to 1994) it has become clear since then that using the notion of
  evolving algebras one can develop a powerful and elegant specication methodology
  which has a huge yet unexplored potential for industrial applications. In
  this report we are going to explain the basic concepts of this approach to the design
  and analysis of complex systems and illustrate its salient features through
  a challenging example from real life.

They also talk about successive refinement and hierarchical modeling.

Maybe if you could describe more on what you're trying to accomplish with the code generation part that would be helpful. It sounds like you are wondering about generating/forming a verified program from cognitive reasoning somehow, automatically generating the operational semantics. I haven't seen anything on that.


On $UP$, $NP$, $\oplus P$ and $PP$? We know $UP\subseteq NP\subseteq PP$.

  Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$?

I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever queries an $UP$ machine can do we know an $NP$ machine can do.

  How to show second $NP^{\oplus P}\subseteq PP^{\oplus P}$?

Consider the oracle machine $N$ that decides $L \in NP^{\oplus P}$. For each computational branch of $N$, if it ends with $\textsf{YES}$, do nothing. If it ends with $\textsf{NO}$, branch and output once $\textsf{YES}$ and once $\textsf{NO}$. Therefore, $L\in  PP^{\oplus P}$.


Minimum number of comparision to find the third largest element in an array of distinct integers? For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $

Is there any formula for the third largest element? and if so, what is the derivation?

For the problem of computing the $k$-th rank element, a lower bound of $n-k+\log \binom{n}{k-1}$ can be proven with decision trees.
For simplicity this proof assumes that the element set $X$ is of size $n$ and its elements are distinct (which makes the problem harder). Moreover, the algorithm may only compare any two elements, and conclude one is either smaller or greater than the other.

First, let us claim the following:

For computing the $k$-th rank element (denoted $x_k$) (using comparisons only), every other element $x_i$ must be involved in a comparison that sets it lesser or greater than the $k$-th rank element.
Formally: for any $x_i$ lesser than $x_k$, $x_i$ must be involved in a comparison of the sort $x_i < x_j \leq x_k$. For any $x_i$ greater than $x_k$, it must be involved in the comparison $x_i > x_j \geq x_k$

The proof by contradiction: Suppose $x$ was not involved in either those comparisons. Then $x$ can be either greater or smaller than $x_k$, which means the $k$-th rank element can change depending on $x$.

Let $\mathcal{T}$ be a decision tree that finds the $k$-th rank element. We will show $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves.
Now, suppose $T_1$ is another decision tree, that knows the set of elements greater than $x_k$, denoted by $K_1$. It means $T_1$ does not need to compare any elements of $K_1$, and thus performs $n-k$ comparisons, or has $2^{n-k}$ leaves.
Because of the claim we made earlier, we know $\mathcal{T}$ must have performed the comparisons in $T_1$, hence for each leaf in $T_1$ there is a corresponding leaf in $\mathcal{T}$. Moreover, in each of these leaves, the element $x_k$ defines the set $K_1$, which are all the elements greater than $x_k$.
How many trees like $T_1$ are there? As many as the different choices you can make for the set $K_1$, which is selecting $k-1$ elements out of $n$, which is exactly $\binom{n}{k-1}$. And for each of these trees, there are at least $2^{n-k}$ leaves in $\mathcal{T}$, which are essentially distinct, since they define distinct sets $K_i$.
It follows that $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves, therefore the lower bound is $\log$ of the same:
$$n-k+\log \binom{n}{k-1}$$


Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free? I know that the Context-free languages are not closed under compliment.

Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here

Why are palindrome and not-palindrome both context-free?

that palindromes are closed under complement.

Can someone please guide over this?

Generally speaking, the way to figure out whether a given language is context-free is twofold:

Try proving that it is not context-free, say using the pumping lemma.
Try proving that it is context-free, say by constructing a grammar or a PDA.

If any of these methods succeed, you will have found whether the language is context-free.

In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:

$y$ has even length.
$y$ has length one.
$y$ has odd length, and when written as $y = z \sigma w^R$, with $|z| = |w|$, the two words are different.

In the third case, let us suppose that $z_i = \alpha \neq \beta = (w^R)_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that
$$
\overline{L} = (\Sigma\Sigma)^* \cup \Sigma \cup \bigcup_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j.
$$
It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.


Algorithm for splitting an array into k sub-arrays We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized sub-arrays (+-1), that each value in the i'th sub-array will be larger than any value in the (i-1)'th sub-array, and smaller than any value in the (i+1)'th sub-array. This method need to be applied in complexity of O(n log k).

Insert(x)- Gets a value x which isn't in our data structure, and adds it. This method need to be applied in complexity of O(k logn).

I did the init method using Medians- ofMedians QuickSelect, by dividing the array into k' sub arrays when k' equals to the closest power of 2 for k, and then I adjusted my pointers to the dividers by using Select on the smaller arrays which added me only O(n).

With the Insert part I'm having some trouble and would appreciate any help, Thanks:)

Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably.

Let $n$ be the number of elements in the data structure before the insert operation. We will maintain this invariant: each subarray contains either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ elements. The elements of each subarray are stored in a min-heap and in a max-heap that support element deletion.

Insert $x$ into the unique group $i$ whose minimum element is smaller than $x$ and such that the minimum element of the next group (if any) is larger than $x$.

Notice that if, before the insert operation, $i$ contained $\lfloor n/k \rfloor$ elements then the operation cannot possibly violate the invariant.
This means that if the invariant is violated then $\lfloor n/k \rfloor < \lceil n/k \rceil$, $i$ contained $\lceil n/k \rceil$ elements, and there is a group $j \neq i$ that contained $\lfloor n/k \rfloor$ elements.
Let $j^*$ be the value of $j$ that satisfies the above conditions and minimizes $|j^*-i|$.

We can restore the invariant as follows:

If $j^* < i$ then all groups $h \in \{j^*+1, \dots, i-1\}$ have $\lceil n/k \rceil$ elements. For each $h= j^*+1, \dots, i$ do the following: pick the minimum element $m$ from group $h$ (this can be done in $O(\log n/k)$ time by a pop() operation on the min-heap of $h$ and a delete($m$) operation on the max-heap of $h$) and add $m$ to group $h-1$ (this amounts to adding $m$ to both the min-heap and the max-heap of group $h-1$).
If $j^* > i$ then all groups $h \in \{i+1, \dots, j^*-1\}$ have $\lceil n/k \rceil$ elements. For each $h= i, \dots, j^*-1$ do the following: pick the maximum element $M$ from group $h$ and add it to group $h+1$.


Characterizing a CFG equivalent to a special type of PDA Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which starts with an empty stack and ends with an empty stack and which has the additional property that during this computation, the stack size can increase, but once the stack size decreases it cannot subsequently increase. I want to show that there is a CFG equivalent to $P$ with the property that for each production in this grammar, there is at most one variable on its right-hand side.

My initial idea to approach this problem was to convert $P$ into an equivalent PDA $P'$ which either pops or pushes on every transition, but never both, which empties the stack before accepting, and which has a single final state. Then I would convert $P'$ into a CFG $G'$ using the standard method, as seen here. Finally, I could show that for every $\sigma \in L(P') = L(P)$, there exists  a derivation of $\sigma$ in $G$ such that every production applied in this derivation is of the form $A_{pq} \rightarrow aA_{rs}b$, where $p,q,r,s$ are states in $P'$ with the property that a transition exists from $p$ to $r$ which reads input symbol $a$ and pushes a symbol $u$ onto the stack and a transition exists from $s$ to $q$ which reads input symbol $b$ and pops $u$. However, I don't know how to show this to be the case.

In other words, you are constructing a linear grammar for a one-turn pushdown automaton.

So the standard construction from the link (which is Sipser style, afaik) gives productions $A_{ik}\to a A_{\ell j} b$ for each pop-push pair in the computation. That is ok, the productions are of the right form.

Now there are two problems. One is what to do with the zillions of $A_{ij}\to A_{ik}A_{kj}$ productions (which are obviously not allowed!) ? The answer is in the intuitive meaning of the symbols $A_{ij}$.

The second problem is hidden, and not clear in your question (and also not in the example you link). Is it allowed to replace to topmost stack symbol by another (this will not change the stack size) or are those considered two consecutive operations? (Here the Sipser model deviates from the standard one). Also: can we make a computational step. not changing the stack?


Language of the values of an affine function Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions of the multiples of $a$ plus a constant:

$$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$$

Is $M$ regular? context-free?

(Contrast with Language of the graph of an affine function)

 I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.

Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with $a$ states 0, 1, ..., $a - 1$. Start state is 0, and from state $q$ on input the digit $d$ go to state $(10 q + d) \bmod a$. Accepting state is $b \bmod a$ (might need a tweak if $b > a$).


Does forcing TMs to change all symbols they read change their power? If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power?

For example: $( State, A, State, Z, DIRECTION)$

$A$ cannot be the same symbol as $Z$.

If you give me a standard Turing Machine, I can build a must-write-different Turing Machine that does the same thing.

I'll take the original alphabet and double it -- so for symbol $a$, I create two symbols $a_1$ and $a_2$, and for symbol $b$, I create $b_1$ and $b_2$.

Now I treat both $a_1$ and $a_2$ in the exact same way as the old TM treated $a$, except when I'm supposed to write an $a$ back onto an $a$, I check if the current symbol is $a_1$ or $a_2$ and write the other one.

We could verify that this construction will indeed mimic the behavior of the original TM (no matter what it was), so must-write-different TMs are equally powerful.

(If this is not clear, please let me know so I can explain further!)


Average number of collisions before successful insertion into hash table I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.

I was thinking that since it is a linear probing and we do not know where the free slots in the hash table are, the probability that first slot is free is $(m-n)/m$ where $n$ denotes the amount of 'bad' slots, i.e. there are $n$ items stored in our hash table.
If the second slot is free then $(m-n)/(m-1) > (m-n)/n$ and so on.

So the expected number of collisions is $1/p = 1/ (1-\alpha)$ where $\alpha := n/m$ is our load factor.

But my friends got totally different numbers. Am I going into the right direction?

1 / (1 - alpha) is about right, if you ignore that for the second slot the chance is (m - 1 - n) / (m - 1) and so on. But when that difference becomes relevant, you should have increased the size of your hash table :-)

What also will happen if you visit consecutive slots on collisions is that once your table is reasonably full then you might have large ranges of occupied slots, which could very much change the situation. Say you have 1,000,000 slots and 999,500 used entries: It's quite likely that the 500,000 slots from 0 to 499,999 are all used.

But all this depends on having a good hash function. Your hash function needs to rarely map different items to the same hash code. And if your hash table visits consecutive slots for collisions, then your hash function mustn't map similar items to consecutive hash codes. Otherwise the average number of slots might be a lot larger.

On the other hand, the cost of visiting a few or a dozen used slots is usually very low to the cost of computing a hash code, if the hash table stores hash codes. It gets really expensive when you have a collision not in slot numbers, but in hash codes. That's when you actually have to compare values. So the most important thing would be a good hash function.

Added: Assume that you have a hash table with 1,000,000 slots, and that 999,500 slots are used. Which is obviously a much higher load factor than a hash table should ever be allowed to have. If the used slots were perfectly random, then inserting a new element would require visiting 2,000 slots on average.

But if you had a range of 500,000 consecutive used slots (which would be quite likely if inserting always visited the next available slot), and you inserted the next item: There would be a 50% chance that the next item gets inserted into that range, visiting from 500,000 to 0 slots, or 250,000 on average. And a 50% chance that the next item gets inserted into the other range which has 0.1% empty slots, or 1,000 on average. So the total average is 125,500 slots visited.


Generating random words by grammar A bit of context

I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this question I presented "minimal working example" for simplicity. And of course, I am able to avoid the issue I faced using a bunch of trivial heuristics, but the question really makes me wonder.

The problem

Suppose we have a typical context-free grammar for arithmetic expressions of $+,*$, brackets, and integer literals:

$$E \longrightarrow F(“+”F)^*$$
$$F \longrightarrow T(“*”T)^*$$
$$T \longrightarrow int|“(”E“)”$$

It is easy to implement a staighforward algorithm for generating random words by this grammar: we implement a separate procedure for each nonterminal. If a nonterminal has multiple production rules (as $T$ does), we choose a production rule by tossing a coin. If rule contains kleene star (e.g. $(“+”F)^*$), we also toss a coin and generate zero or one repetition (sure we could pick any random integer $k\geq0$ and generate $k$ repetitions, but for simplicity we will focus on the simplest version of this procedure). Here is what we get:

generate_E():
    if coin_toss():
        return generate_F() + "+" + generate_F()
    else:
        return generate_F()

generate_F():
    if coin_toss():
        return generate_T() + "*" + generate_T()
    else:
        return generate_F()

def generate_T():
    if coin_toss():
        return "(" + generate_E() + ")"
    else:
        return random_integer()

An invocation of generate_E() yields a random expression.

What could go wrong? It turns out that execution of this procedure on the real machine terminates with stack overflow quite often. Of course, technically here we have a possibility of endless recursion, but my intuition was telling me that probability of reaching recursion depth $k$ decays exponentially with increasing $k$, therefore getting deep levels (let's say, 1000) is almost impossible. Apparently, a few consecutive runs reveals that procedure can easily reach depth of many thousands (by depth I mean maximum number of procedure calls the stack contains simultaneously).

I am curios how to formalize this empirical fact. I want either a formula for $P(depth = k)$, or an asymptotic approximation of it, or an inequality bounding right tail of CDF below (something like $P(depth > 1000) > 0.05$)

My attempt

I tried to come up with a formula for $P(depth = k)$:

Let's denote $P(depth = k)$ as $P_E(k)$. Also, we define similar values for generate_F() and generate_T() - $P_F(k)$ and $P_T(k)$ respectivetely.

Clearly (else branch of generate_T), $$P_T(1) = \frac{1}{2}$$ and for $k > 1$ (then branch)$$P_T(k) = \frac{1}{2}P_E(k - 1)$$

Regarding $P_F(k)$, we can either execute else branch, and it gives term $$\frac{1}{2}P_T(k - 1)$$, or then branch, what gives a bit more complicated one $$\frac{1}{2}\sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T(y)}$$ i.e. $$P_F(k)= \frac{1}{2}(P_F(k - 1) + \sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T(y)})$$

Finally, the formula for $P_E(k)$ is almost the same as for $P_F(f)$, we only have to replace $P_T(x)$ with $P_F(x)$.

Now, we can calculate some values of $P_e(k)$

\begin{array} {|r|r|}\hline k & P_E(k) & P_E(k)\text{ in decimal}& P_E(k)\text{ by Monte-Carlo} \\ \hline 3 & \frac{33}{128} & \approx0.257812 & \approx0.2527 \\ \hline 6 & \frac{4448787585}{34359738368} & \approx0.129477 & \approx0.1282 \\ \hline 9 & \frac{14080391757747154038821618051813151497122305}{178405961588244985132285746181186892047843328} & \approx0.078923 & \approx0.0761 \\ \hline 12 & \text{ the fraction is too long} & \approx0.053213 & \approx0.0530 \\ \hline  \end{array}

As we can see, the recurrent formulas seem to be true, but neither they give me an insight on asymptotical behaviour of $P_E(k)$, nor the first values give a clue on formula in closed form.

Any help would be appreciated.

Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > 1$, it is not surprising that your process often failed to terminate.

To gain more information, we need to know the exact distribution of the number of $E$-offsprings, which is given by the following generating function (see the Wikipedia article linked to above):
$$
h(z) = \frac{33}{128} + \frac{7}{16}z+ \frac{15}{64}z^2 + \frac{1}{16}z^3 + \frac{1}{128}z^4.
$$
This implies that the extinction probability is $d \approx 0.717778143742483$ (by solving $h(z) = z$). This is an upper bound on the probability that your procedure terminates.

We can easily recover your numbers by considering iterates of $h$. The probability that the process terminates in $3k$ steps is $h^{(k)}(0)$. So computing $h(0),h(h(0))-h(0),h(h(h(0)))-h(h(0))$ and so on, we recover the figures in your table.

When $k$ is large, $h^{(k)}(0) \approx d$. We can compute $h'(d) \approx 0.882115879977412$. We have
$$
\frac{d - h^{(k)}(0)}{d - h^{(k-1)}(0)} =
\frac{h(d) - h(h^{(k-1)}(0))}{d - h^{(k-1)}(0)} \approx h'(d).
$$
It follows that
$$
d - h^{(k)}(0) \propto h'(d)^k.
$$
Therefore the probability that the process terminates in exactly $3k$ steps is
$$
h^{(k)}(0) - h^{(k-1)}(0) =
[d - h^{(k-1)}(0)] - [d - h^{(k)}(0)] \propto h'(d)^{k-1} - h'(d)^k \propto h'(d)^k.
$$
Empirically, we can check that the constant of proportionality is roughly $0.0248011196615094$.


Find common min in logarithmic time I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(\log n)$ time. Is this possible to achieve, either for worst-case or amortized complexity?
Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.

Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.

You can't.  There is no such data structure.  Assuming you have a separate instance per set, and each instance is initialized separately (using only information about the set it represents and not any information about any of the other sets), these running times are not achievable.

In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time.  Indeed, testing disjointness requires $\Omega(n)$ time, as explained here.  Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$.  Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$.  Now $T_1,T_2$ are guaranteed to have a common element.  So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another.  Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible.  It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.

This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.


Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$ Given an array $A$ of positive integers with size $m$ and an array index $c$ (indexing starts at $1$). Prove using mathematical induction over $m$ that there always exists a contiguous subarray $S$ in $A$ such that the (sum of the elements of $S$) $\pmod {i} = 0.$

I'm unable to find the correct approach to solve this. I'm sure the Pigeonhole Principle will be useful here, but I don't know how to correctly apply it within the proof. Can someone point me in the right direction?

Let's try to do it, no induction involved.

Suppose you augment your initial list $A = [a_1, a_2, ..., a_m]$ with a new element at the beginning $a_0 = 0$, $A' = [a_0, a_1, ..., a_m]$.

Now build partial sums of $A'$, such that $P_i = \sum_0^i a_j$. Notice that the sums of elements in the initial list from positions $b$ to position $e$ is $\sum_b^e a_i = P_e - P_{b - 1}$. Notice $P_0 = 0$ is defined since we added $a_0$. This is a very common trick when you care about the sums of intervals.

Back to the problem, you need to proof there exist two index $i < j$ such that $c | (P_j - P_i)$. This is equivalent to say that there exist two index $i < j$ such that $P_i \equiv P_j \mod c$. We only care about remainder of each element in $P$ if they are divided by $c$, and moreover we should only show that at least two elements have the same remainder.

Now notice the number of different remainders given $c$ is at most $c$ and the length of the list $P$ is $|P| = m + 1$. Since $c \le m < |P|$ by the Pigeonhole principle you can guarantee at least two elements in $P$ have the same remainder.


How to fill cell-network partition matrix of a function? I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 1), but I can't make it past the first paragraph:

Consider the $x_l … x_{k - 1} | x_k$ partition matrix of a function $f(
x_1, x_2, …, x_k)$, as shown in Fig. 1, where $C_0$ and $C_1$
represent the $x_k = 0$ and $x_k = 1$ columns, respectively. Let $0$
and $1$ represent the columns of all 0's and all 1's, respectively.
Let $X$ denote a column with at least one 0 and at least one 1,
and $\overline{X}$ its complement. The concatenation of two columns
will represent a complete partition matrix. Thus, for example,
$01$ represents $f(x_1, x_2, …, x_k) = x_k$ and $XX$ represents a
function independent of $x_k$, but dependent on at least one of
the remaining variables.

I'm trying to build something like a Karnaugh map, but the result I'm getting doesn't make sense.

For example, here's what I made from $f = x_1 \times x_2 \times x_3$ (with digital logic "&" for boolean times):

The first column ($C_0$) I would call $0$, from the author's definition, but the second column ($C_1$) doesn't seem to be a $0$, $1$, or $X$. What am I doing wrong?

You're pretty close.

I don't think that's what they intended as the partition matrix.  Instead, I think they intended the following matrix:

         x3
x1 x2 \  0 1
       -----
 0  0  | 0 0
 0  1  | 0 0
 1  0  | 0 0
 1  1  | 0 1

That's slightly different from what you have written.  In particular, the partition matrix will have $2^{k-1}$ rows and 2 columns.

It's best to think of the first sentence as one paragraph, and the remaining sentences as a second disconnected paragraph that is trying to explain a taxonomy for classifying a column of this matrix.  The author is proposing to classify every column into one of three types: all-zeros, all-ones, or contains both a 0 and a 1.  The paper represents an all-zeros column by 0, an all-ones column by 1, and the third case by X.  Thus, X is used to represent any column that contains at least one 0 and at least 1, i.e., any column that is not all-zeros and not all-ones.

By this classification, the partition matrix above would be of the form 0X: the first column is all-zeros (type 0), and the second column is type X.


Minimum number of clues to fully specify any sudoku? We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all valid sudoku puzzles be specified in 17 clues? If not, what is the minimum number of clues that can completely specify every valid puzzle? More formally, does there exist a valid sudoku puzzle (or, I guess it would be a set of puzzles) that cannot be uniquely solved from only 17 clues? If so, then what is the minimum number of clues, $C$, such that every valid sudoku puzzle can be uniquely specified in $C$ or fewer clues?

Since permuting two rows within a single block of a valid, completed sudoku produces another valid, completed sudoku, you can take any completed board (81 clues) and remove the first two rows (81-18=63 clues), which will give you an incomplete sudoku with two solutions. Note that even if you remove all but one of the 18 numbers there, the solution is immediately uniquely determined (since there can be no number repeated in the same column).

Another operation that produces another completed sudoku is applying a permutation of $\{1,\ldots,9\}$. If you take a permutation that is a transposition (permutes two elements, keeping the other fixed), again, as before, you can remove all appearances of those two elements and you have an incomplete sudoku with two possible solutions and 63 clues. Again, if you don't remove all 18 numbers, the solution will be unique.

Of the six elemental operations that produce a completed sudoku (see here), these two are the ones that can involve the least number of elements, so I'd say $C=63$ is an upper bound for what you're looking for. I know this does not exactly answers your question, but the general idea of removing sets of positions which produce two different solutions might be a good starting point.


Why is this example a regular language? Consider this example (taken from this document: Showing that language is not regular):

$$L = \{1^n \mid n\text{ is even}\} $$

According to the Pumping Lemma, a language $L$ is regular if :

$y \ne ε$
$|xy| \lt n$
$\forall k \in N, xy^kz \in L$

In the above example, $n$ must be even. Suppose we have $n = 4$, we can express: $$xy^kz$$ such that: $x = 1$, $z = 1$, and with $k = 2$, we have $y^k = y^2 = 11$, so we get the string $1111$. However, since all $k$ must be satisfied, if $k = 1$, the string is $111$, it does not belong to $L$. Yet, I was told that the above example is a regular language. How can it be?

Pumping lemma is not a sufficient condition for being regular, it is only a necessarily condition. Satisfying it does not imply that the language is regular.
In the pumping lemma, some parameters are chosen adversarily, i.e. you don't have control over them. If a language is regular then pumping lemma says that "for a long enough string in the language there is a partition s.t. ...". To show that a language is not regular you should show that for all ways of partitioning the conditions will not hold. Your argument does rule out $y=11$ for example, you are only talking about a particular way of partitioning and that does not imply anything.
The language is indeed regular, it is (11)*.