How to prove the correctness of the binary tree inversion algorithm? Define the inversion of a binary tree as the tree whose left sub-tree is a mirror reflection of the original tree's right sub-tree around the center and right sub-tree a mirror reflection of the original tree's left sub-tree.
Examples:

   Inversion 1           Inversion 2

   C    |    C           C    |    C
  / \   |   / \           \   |   /
 A   B  |  B   A           B  |  B
                          /   |   \
                         A    |    A

Consider the following binary tree inversion algorithm (source: LeetCode):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

I sought to prove it inductively on the depth of tree but am stuck at the inductive step. How can I show that the mirror reflection of the left subtree (or right) around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself?

It might be surprising to you, but "the mirror reflection of the right subtree around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself" could be, in fact, part of the definition of "a mirror reflection of the right subtree around the center of the root tree"!
Note that the following definition of "the inversion of a binary tree", as given in the question, does not define what is the "mirror reflection of the original tree's right subtree". Although that mirroring is pretty intuitive for a human to understand accurately, given the accompanying illustrations, it is, in fact, not defined/specified clear enough to enable you to prove the correctness of the algorithm formally.

Define the inversion of a binary tree as the tree whose left subtree is a mirror reflection of the original tree's right subtree around the center and right subtree a mirror reflection of the original tree's left subtree.

So, here is the real question.
How do we define mirror reflection formally?
Here is a recursive definition. (This can be seen as taking the given algorithm as the definition basically.)
Given a binary tree $T$ or an empty graph, its mirror reflection $T'$ is another graph such that

$T'$ is empty if $T$ is empty.
$T'$ is a single node that is the same as $T$'s single node if $T$ is a single node.
Otherwise, $T'$ is also a binary tree such that

the root of $T'$ is the same as the root of $T$ and
the left subtree of $T'$ is a mirror reflection of the right subtree of $T$ and
the right subtree of $T'$ is a mirror reflection of the left subtree of $T$.

When $T'$ is a mirror reflection of $T$,  we also say $T'$ is a mirror reflection of $T$ along/around the center of $T$, or any imaginary line that goes from root to a leaf.

Here is a non-recursive definition, that is equivalent to the above.
Given a binary tree $T$ or an empty graph, its mirror reflection is any graph that is isomorphic to the graph $T'$ defined below.

If $T$ is empty, so is $T'$.
Otherwise, let $V$ be the nodes of $T$. Let $V'$ be a copy of $V$; that is, for each $v\in V$, there is unique node in $V'$ that corresponds to $v$. Call that unique node $v'$.

For any two nodes $p, c\in V$ such that $c$ is the left child of $p$, we let $c'$ be the right child of $p'$.
For any two nodes $p, c\in V$ such that $c$ is the right child of $p$, we let $c'$ be the left child of $p'$.

The OP also proposes the following geometric/graphical definition of "inversion of a tree".

Let $(a,b)$ be the coordinate of the node at depth $a$ that is the $b$-th node from the imaginary center line. If $b$ is negative then the node is to the left of the line. Then the inversion can be defined as the resulting tree if we map $(a,b)$ to $(a,-b)$ and keep the edges accordingly.

The definition above, although graphically clear to a human, might not be very friendly for rigorous reasoning. For example, "the b-th node from the imaginary center line" requires further non-trivial clarification.

With either of my definitions above, it will be rather easy to prove the correctness of the algorithm.
You might have noticed by now that inversion of a binary tree means exactly the same as its mirror reflection!


Is it decidable if a given TM accepts infinitely many words in a fixed number of moves? $L=\{\langle M \rangle \mid \text{There are infinitely many words accepted by M in less than 10 moves}\}$

I am having hard time understanding this language and I have several questions:

How is it possible to derive infinite amount of words in finite moves?
How can we determine if a word is or isn't in the language at all?
Why is this language decidable? I understand that it is because it halts on every input, but what are we looking for after 10 moves to decide if it will reject or accept?

Any further clarifications on this language will be highly appreciated.

I'm going to assume that you mean

$\qquad L = \{ \langle M \rangle \mid |L_{\leq 10}(M)| = \infty \}$

with $L_{\leq m}(M)$ the set of words that $M$ accepts after at most $m$ steps. In particular, it does not say a thing about all the other inputs.

  How is it possible to derive infinite amount of words in finite moves?

The Turing machine that does nothing but accept clearly accepts an infinite language. While it's true that machines that qualify for $L$ have to work with finite prefixes, but they can accept arbitrarily many inputs based on these prefixes!

  How can we determine if a word is or isn't in the language at all?

I don't know what "we" is here; but clearly, we can just run $M$ on the input. If it accepts after at most ten steps, fine; otherwise, it's not relevant for the criterion of $L$.

  Why is this language decidable?

Who says so?

Hint: How many symbols of the input can any TM examine in ten steps? Let's call this number $k$. What does it tell you if it accepts or rejects an input of length at most $k$? What does it tell you if it accepts or rejects an input of length greater than $k$?

  I understand that it is because it halts on every input.

How so? If you had an algorithm that decides $L$, then yes, it would halt on every input. But we can not assume that -- that's the claim we have to prove!

The inputs for this algorithm are all Turing machines, in particular also such that don't halt.

  but what are we looking for after 10 moves to decide if it will reject or accept?

You have one bit of information: did the machine accept or not? You can have some more, if that helps: did the machine visit a state twice? Did it move, and how?


Longest simple walk in a complete graph A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice.

A simple undirected graph is an undirected graph with no loops and multiple edges. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A path of length $n$ is a sequence of n edges $e_1$,$e_2,\ldots,e_n$ such that $e_1$ is associated with $\{x_0,x_1\}$, $e_2$ with $\{x_1,x_2\},\ldots,e_n$ with $\{x_{n-1},x_n\}$.

  What is the length of the longest simple walk in a complete graph with $n$ vertices?

What I tried: When $n$ is odd, every vertex has degree $n-1$ which is even. It follows that the graph has a euler circuit (every edge is included), therefore the longest walk length is $n(n-1)/2$, corresponding to the total number of edges.

But when $n$ is even, I try to follow similar reasoning and get stuck. I get a degree sequence, but I can't prove it is graphic. How could we handle the case where $n$ is even?

If $n$ is odd, the graph has an Euler trail, i.e., a simple walk on all $\tfrac12n(n-1)$ edges.  This is obviously optimal, since it uses every edge in the graph.

If $n$ is even, delete a matching of size $\tfrac12n-1$, i.e., delete a set of that many edges, no two of which share an endpoint. The resulting graph $G$ has two odd-degree vertices and $n-2$ even-degree vertices, so it has an Euler trail, which is a simple walk of length $$\tfrac12n(n-1) - (\tfrac12-1) = \tfrac12n(n-2)+1\,.$$ This is optimal. Any simple walk is an Euler trail of the graph formed from the vertices and edges of the walk. But any simple walk in $K_n$ longer than the one just described would have to contain at least four vertices of degree $n-1$, which is odd. And no graph with four odd-degree vertices has an Euler trail.


Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)? Suppose we have a function $f$,

$$
C = f(A,B),
$$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($\{0, 1\}$) and $f$ is the XOR operation, we have the following identity:

$$
H(C|A) = H(B),
$$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.

Note

\begin{align}
0&=H(C|A,B)\\
&=H(A,B,C)-H(A,B)\\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)\quad\text{(chain rule)}\\
&=H(B|A,C)+H(C|A)-H(B|A),
\end{align}

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)\ge 0$ and $H(B)\ge H(B|A)$, your condition is equivalently $H(B|A,C)=0\wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $\{b\mid \mathrm{Pr}\{A=a, B=b\}>0\}$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.


Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input) Is this problem decidable?

Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input?

My guess is not decidable. I am not sure, however, how to justify it.

I tried this: Lets enumarate all possible words from $\{0,1\}^*$ and run $M_1$ and $M_2$ simultaenously. If $M_1$ accepts/rejects and $M_2$ is still running, output NO. If $M_2$ stops and $M_1$ is still running, check next word. However, if neither $M_1$, nor $M_2$ do not halt on the word, I am stuck and cannot decide it (because I will get an instance of the halting problem for each combination of word and Turing machine).

Is this reasonable or is it a wrong assumption?

Hint: Let $M_2$ be a machine that on input $n$ runs for $n$ steps roughly, and only consider machines $M_1$ that don't depend on their input. If you could solve your task then you could determine whether a given input-less machine ever halts.


Given A to C, and B to C with known complexities, what can be said about A to B? Say I have two sets of values $A$ and $B$ and for each set I have a computable function from that set to a third set $C$. Now suppose that I want to construct a function from $A$ to $B$, such that if I compose that function with the $B$ to $C$ function mentioned above I get a function that produces the same results as the $A$ to $C$ function mentioned above.

If I know the time-complexity of the two functions that return elements of $C$, does that allow me to say anything about a function from $A$ to $B$ with the specified property? For example can any bounds be placed on the computational complexity of such a function? Can we even say whether such a function is computable or not?

We can have sets $A, B, C$ with linear-time computable maps $f : A \to C$ and $g : B \to C$ such that there exists a map $h : A \to B$ with $f = g \circ h$, but the needed time complexity/Turing degree for $h$ is as high as you want.

Proof: Pick a map $H : \Sigma^* \to \Sigma^*$ which is hard in whatever sense you have chosen. Now let $A = C = \Sigma^*$, and $B = \{\langle w, H(w)\rangle \mid w \in \Sigma^*\}$. Let $f = \mathrm{id}$ and $g = \pi_1$, i.e. $g(\langle w,u\rangle) = w$. Now $A,B,C$ and $f,g$ meet the criteria of the claim, and the only map $h$ that works is $h(w) = \langle w, H(w)\rangle$, which is essentially as hard as $H$.


Finding bicliques in a bipartite graph of minimum size Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V':  (u, v) \in E$.

Given $\delta$, I'd like to identify bicliques $(U',V')$ such that $|V'| \ge \delta$.  Since the number of all bicliques in a bipartite graph w.r.t its size can be exponential, I'm looking for an approximate algorithm (desirably with guarantees), that can find bicliques such that $|V'| \ge \delta$. For example, find $k$ bicliques where $|V'| \geq \delta$, in time polynomial w.r.t. $k$ and $G$.  Can anyone suggest such an algorithm?

One naive solution is to enumerate bicliques using an enumeration-based algorithm and keep the bicliques that satisfy the last condition until the selection of "k" bicliques.

Here is an algorithm with $O(n^{2+\lg k})$ running time.  It's not polynomial in $k$ and $n$, but for fixed $n$ it is polynomial in $k$, and for fixed $k$ it is polynomial in $n$.  Here is the algorithm:

Let $\gamma = \lg k$.
Find all bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Output $k$ of them (stop early once you have found $k$ of them).

In step 2, it's easy to find all bicliques such that $|U'| \le \gamma$, $|V'| \ge \delta$ in $O(n^{2+\gamma})$ time: just enumerate all possibilities for $U'$.  By the definition of $\gamma$, this takes $O(n^{2+\lg k})$ time, since there are only ${|U| \choose 0 } + \dots + {|U| \choose \gamma} = O(|U|^{\gamma}) = O(n^{\gamma}) = O(n^{\lg k})$ possible subsets $U'$ of size $\le \gamma$.

But will step 2 find enough bicliques?  You might worry that it will find fewer than $k$ bicliques, even when there are at least $k$ in the graph.  Not to worry; that can't happen.  In particular, I'll show that if there is a biclique that is too large to be found in step 2, then there are at least $k$ bicliques that are small enough to be found in step 2, so step 2 will find enough to output $k$.  The only way that step 2 can fail to output $k$ bicliques is if the graph does not contain $k$ bicliques.

Let's prove that claim.  If step 2 outputs fewer than $k$ bicliques and there exists a biclique that the algorithm didn't output, that means there exists a biclique with $|U'| \ge \gamma+1$ and $|V'| \ge \delta$.  What are the consequences of this?  Well, there are two cases, depending on the size of $U'$:

Case 1. Suppose $\gamma+1 \le |U'| \le 2\gamma$.  Then you can find at least $2^{\gamma}$ more such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Why?  Well, take any subset of $U'$ of size at most $\gamma$, and keep $V'$ unchanged.  Then this will give a new biclique, and it will meet all the conditions of the original problem.  The number of such subsets is ${|U'| \choose 0} + {|U'| \choose 1} + \dots + {|U'| \choose \gamma}$, which is at least $2^{U'}/2$ (since $\gamma \ge |U'|/2$).  Now $2^{U'}/2 \ge 2^{\gamma+1}/2 \ge 2^{\gamma} \ge k$, so this gives us $k$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Thus in this case there exist enough bicliques that step 2 can find $k$ of them.
Case 2. Suppose $|U'| \ge 2\gamma$.  Then you can find at least $2^{\gamma}$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Why?  Again, take any subset of $U'$ of size at most $\gamma$; that will lead to another biclique that can be found in step 2.  How many such subsets are there?  There are at least ${|U'| \choose \gamma}$ of them, and  ${|U'| \choose \gamma} \ge (|U'|/\gamma)^{\gamma}$ more (see the first bound here).  By assumption, $|U'|/\gamma \ge 2$, so this means there are at least $2^{\gamma}$ more such subsets, i.e., at least $2^{\gamma}$ more bicliques that can be found in step 2.  Thus in this case there exist enough bicliques that step 2 can find $k$ of them.

In either case, if the graph has at least $k$ bicliques, this algorithm will output at least $k$ of them.


Context Free Grammer and PDA So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"L contains palindromes that don’t ever have the same character occur twice in a row."

Let Σ = {a, b, c}

Let L = {w ∈ Σ∗| w = {w1, w2, . . . , wn} is a palindrome, and wi 6= wi+1 ∀ 0 ≤ i < n}.

In other words, L contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea.

The grammar $S \to aSa \mid bSb \mid cSc \mid a \mid b \mid c \mid \epsilon$ would generate (normal) palindromes.

A simple way to extend this to generate palindromes with non-repeating would be to add for each letter $x$ a new non-terminal $S_{not\text{-}x}$, and adapt the grammar:

$S \to aS_{not\text{-}a}a \mid \dots$

$S_{not\text{-}a} \to bS_{not\text{-}b}b \mid \dots$

There are probably more efficient ways.


Rooted Binary Tree - Chain Nodes Algorithm The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that child is not a leaf.
I am stuck any help would be appreciated, so far I have done this:

Algorithm Chainnode(x) {
    if (not Leaf(x)) and (left[x] XOR right[x] == Null) {
        return True
    }
    else {
        return False
    }
}

Algorithm ChainnodeCount(x) {
    i = 0
    if (x == Null or Leaf[x]) then {
        return i
    }
    else if ChainNode(left[x]) == True {
        i = ChainNodeCount(left[x]) + 1
    }
    else if ChainNode(right[x]) == True {
        i = ChainNodeCount(right[x]) + 1
    }
    else {
        i = ChainNodeCount(left[x]) + ChainNodeCount(right[x])
    }
}

The number of chain nodes of a rooted binary tree with two non-empty sons is the sum of the chain nodes in its sons.

Also, the number of chain nodes of a rooted binary tree with only one non-empty son is the number of chain nodes of the son plus one.

If a rooted binary tree has no non-empty sons, its number of chain nodes is zero.

And finally, the number of chain nodes of an empty rooted binary tree is zero.

So, following this properties we have

int chainNodes(tree T) {
    if (T is empty)
        return 0;
    if (T has no nonempty sons)
        return 0;
    if (T has only one nonempty son)
        return chainNodes(son)+1;
    if (T has two nonempty sons)
        return chainNoodes(leftSon)+chainNodes(rightSon);
}

which is similar to your try.


Sorting when there are only O(log n) many different numbers We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list?

Any idea or hint or pseudo code? In fact I want to learn pseudo code.

Because you asked for minimum number of comparisons, so I assume the algorithm can only compare the numbers.

The idea is to extend the sorting lower bound argument.
Assume you want to sort $n$ elements knowing there exist at most $k$ distinct values. There are $n!$ ways to permute the elements, but many of them are equivalent. If there are $n_i$ element of the $i$th values. Each permutation is equivalent to $\prod_{i=1}^k n_i!$ other permutations. So the total number of distinct permutations is

$$\frac{n!}{\prod_{i=1}^k n_i!}$$

The number of required comparisons is bounded below by $$ \log_2 \left( n!/\min \{ \prod_{i=1}^k n_i! \big| \sum_{i=1}^k n_i = n, n_i\geq 0\text{ for all } i\} \right)$$

Good thing that minimization part can be easily shown by extend factorial to the continuous domain. $\min \{ \prod_{i=1}^k n_i! \big| \sum_{i=1}^k n_i = n, n_i\geq 0\text{ for all } i\}$ is attained when $n_i=n/k$. (note the $\log$ in the next computation is base $e$ for convenience)

$$ \log \left( n!/{(n/k)!^k} \right) = \log (n!) - k \log ((n/k)!) = n\log(n) - n\log(n/k) + O(\log n)=  n(\log(n)-\log(n)+\log(k)) + O(\log n) = \Omega(n\log k) $$

$\log(n!) = n\log n - n + O(\log n)$ is Ramanujan's approximation.

To get an upper bound. Just consider storing the unique values in a binary search tree, and each insert we either increase the number of occurrence of an element in the BST, or insert a new element into the BST. Finally, print the output from the BST. This would take $O(n\log k)$ time.

Since both the lower bound and upper bound works for all $k$, the algorithm would take $O(n\log \log n)$ time for your problem.

Addendum:

I just figured out from @Pseudonym's comment that this proof also proves that we need at least $nH$ comparisons where $H$ is the entropy of the alphabet, so I might as well add this to the answer.

Let $c = \log 2$ and $p_i = n_i/n$. The entropy of the alphabet where the $i$th letter appears $n_i$ time is $H=-\sum p_i \log_2 p_i$. $nH = -\sum n_i (\log_2(n_i)-\log_2(n)) = \sum n_i (\log_2(n) - \log_2(n_i)) = c \sum n_i (\log(n) - \log(n_i))$.

\begin{align*}
\log_2 \left( n!/\prod_{i=1}^k n_i! \right) &= \log_2(n!)-\sum_{i=1}^k \log_2(n_i!)  \\
&= \log_2(n!)-\sum_{i=1}^k \log_2(n_i!)  \\
&= c (\log(n!)-\sum_{i=1}^k \log(n_i!))  \\
&= c (n \log n-n + O(\log n) - \sum_{i=1}^k n_i \log(n_i)-n_i+O(\log n_i))  \\
&\geq c (n \log n-n -  \sum_{i=1}^k n_i \log(n_i)-n_i)  \\
&= c (-n + \sum_{i=1}^k n_i(\log(n) - \log(n_i))+n_i)  \\
&= c (\sum_{i=1}^k n_i(\log(n) - \log(n_i)))  \\
&= nH
\end{align*}


Proving the optimality of an algorithm I proposed an algorithm and I want to prove its optimality. It is not a greedy algorithm. I have the whole searching space $\mathcal{S}$ and I only search inside a subset of this searching space $\mathcal{C} \subset \mathcal{S}$ and exclude the remaining search space. I know the logic behind excluding this should not violate the optimality of my algorithm. What kind of proof technique I should use to formally prove the optimality of my algorithm ? like contradiction or so on. Note : the optimal solution that can be produced by my algorithm is not unique.

It's rarely possible to prove that an algorithm is optimal. You would have to show that your algorithm takes n steps, and for some reason solving the problem in less than n steps is impossible. Even for someone who is 100 times more intelligent than you and me together.

An example is finding the maximum of n random numbers, which can done in n steps, and n steps are required because if you read n-1 or fewer array elements, then you can't know whether the last one is greater than all other elements or not.


Maximum-weight set of cliques of size 3 with no common vertices in undirected graph I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 common vertices. The problem can be thought of as grouping the vertices into sets of 2 such that no vertex belongs to more than 1 group.
I'm looking to extend the problem such that the vertices can be split into groups of 3. For an undirected graph, this translates into looking for cliques/cycles of size 3 that do not contain common vertices. Any guidance on how to approach this problem either deterministically or with an approximation/heuristic algorithm?
Note: the graphs I'm working with are typically dense

This problem is NP-complete even when all edge weights are 1, since that restriction is equivalent to the problem Partition Into Triangles, which "Computers and Intractability" (Garey and Johnson, 1979) lists as NP-complete on p. 192, attributing the result to a personal communication from T. J. Schaefer in 1974, apparently based on a reduction from 3-Dimensional Matching.
So, no efficient algorithm can be expected. For an exponential-time exact algorithm, I would probably try branch and bound intertwined with maximum bipartite (2-)matching, as follows: At each stage, we have a vertex $v_i$, which we will take to be the lowest-numbered vertex of a triangle, and the decision is which of its neighbour vertices $v_j$ should become the highest-numbered vertex in the triangle. For each possible $v_j$, to test feasibility of the choice, create a new, bipartite graph with a vertex for each low+high vertex pair decided so far, as well as a vertex for each as-yet unprocessed vertex, and an edge between two vertices whenever the low+high pair represented by one would form a triangle in the original graph with the other and the latter vertex is numbered between the low and high vertices represented by the former. Run maximum bipartite matching on this new graph, and check that every low+high pair decided so far is saturated (adjacent to a matched edge) -- if this fails, then the current assignment of low+high vertices cannot be extended to a full triangle partition and the branch can be pruned. I think this algorithm, which chooses just 2 vertices within each triangle, will result in B&B tree depths of around 2/3rds the fully naive approach in which all 3 vertices of each triangle are chosen.


Running time of partial algorithms What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts?  Assume, if necessary, that the halting problem of the given algorithm is decidable (with unknown complexity).

How is this time function of $n$ called?  Is it studied in complexity theory, or does one only consider the running time of universally halting algorithms?

Given an algorithm $A$ (on inputs from some set $X$), we define the runtime function to be
$T_A(x) : X \to \mathbb{N} \cup \{\infty\}$ so that

$\qquad T_A(x) = \begin{cases}
    \text{number steps } A(x) \text{ takes},\ \ &A(x)\!\downarrow \\
    \infty, &A(x)\!\uparrow
  \end{cases}$

for all $x \in X$. I denote with $A(x)\!\downarrow$ that $A$ terminates on $A$,
and with $A(x)\!\uparrow$ the opposite.
Note that the number of steps an algorithm takes on an input depends on the
computational model you choose, but we can leave that abstract here.

Now, the common way to define worst-case runtime is

$\qquad\displaystyle T_A^{\mathrm{WC}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n\}$

which of course yields $\infty$ if there is any input of the given size for which $A$ loops.
You want

$\qquad\displaystyle T_A^{\mathrm{WC\downarrow}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n, A(x)\!\downarrow\}$.

I don't know an established name for that one, but if I were to need one I'd go with
terminating-worst-case runtime¹. That said, you probably use only one
notion of runtime most of the time, so you can do as most authors do and say something
along the lines of:

  From here on out, we always mean $T_A^{\mathrm{WC\downarrow}}$
    when we write "runtime" unless otherwise specified.

So yes, just use runtime but make very clear what you mean by that.

You notice that the definition of $T_A^{\mathrm{WC\downarrow}}$ assumes
that there is at least one input of every size for which $A$ terminates.
You should handle the case if that fails.


Printing values of psuedo random numbers in a range I wanted to write a program to print the values of pseudo random numbers in a range. So, i wrote the following:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
 int i=0,x;
 while(i!=10)
{
    srand(time(0));
    x=rand()%51;
    if(x>=30&&x<=45)
    {
    printf("%d\n",x);
    i++;
    }
}
return 0;
}

But this program is printing some random number between 30 and 45 10 times(the same value, say 33 ten times). Can someone please explain the flaw in this?

While this looks like a programming question, the real misunderstanding is in how to use pseudorandom number generators.

A pseudorandom number generator is initialized using a seed (we later expand on that). Once initialized, it can be called to output a (seemingly) infinite sequence of random bits or integers (the sequence will be periodic, but the period can be huge). The interface of a pseudorandom number generator thus consists of two functions:

Initialize with a seed – in your case, srand.
Output the next number in the sequence – in your case, rand.

For some reason, you are initializing the seed each time you want a random number. While this is not necessarily wrong (though in your case it is!), it ignores a fundamental feature of most pseudorandom number generators: initializing is slow, and generation is fast. We can effort initialization to be slow since it is only called once, whereas you could be generating many numbers. This is why it is not recommended to initialize your generator for each generated number.

What goes wrong with your code? The problem is that time returns a value which only changes once a second. Since your program executes in much less than a second, it is highly likely that each time you initialize your generator, you will initialize it using the very same value. Therefore you are getting the same number each time – this is by design.

Finally, a few words on how to initialize your generator. One option is to choose a seed at random once and for all. This guarantees that your results are reproducible – each time you run the program, it will be using the same pseudorandom sequence. Another popular option is to use the current time, as you're doing (though it's better to use something with higher resolution than seconds). A third option is to use some "entropy reservoir", such as the Unix /dev/random, which is supposed to pick up entropy from key presses, mouse moves, and so on. A fourth option would be to use thermal noise – that requires specialized hardware.


What is a 'subrecursive algorithm'? I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term subrecursive. Original context:

  Another possibility might be to assume subrecursive functions embedded in analogical processes rather than logical operations in FLB that can mimic recurssive operations for finite levels.

FLB is Noam Chomsky's faculty of language in a broad sense

I am have found the following definition from Campagnolo et al., but am having a hard time understanding it. Any help unpacking the following or an example would be greatly appreciated :)

  All functions in the Grzegorczyk hierarchy are subrecursive, meaning that they are computable in a number of steps which is a less computationally complex function of the input than the function itself

Bonus question

Are subrecursive algorithms the opposite of superrecursive algorithms? In either case can you help me understand the relationship between them?

There exist many interesting languages that do not have the full expressiveness of Turing Machines: these languages are traditionally called subrecursive.

The typical example is the language of primitive recursive algorithms, provably equivalent to the language of algorithms that can be written with "for-like" statements (fixed step, fixed bounds). Primitive recursive algorithms are total, hence they are not complete (that means that there are total functions not expressible in the formalism). A famous example of a total function not expressible in the primitive recursive setting is Ackermann function.

Other examples of subrecursive languages come from logic. It is well know that no logical system (rich enough to allow to reason about natural numbers) is complete. Hence you cannot expect to prove the totality of all algorithms in them. That is to say that any logical system characterizes a set of computable functions that are provably total in the given system. For instance, the set of computable functions provably total in Peano arithmetics is the so called Goedel's System T (a higher order generalization of primitive recursion); similarly, the set of computable functions provably total in second order arithmetics is Girard's System F, also know as polymorphic lambda calculus.

The interest of considering subrecursive languages consists in the fact of capturing statically , i.e. by the way the program is written, relevant dynamic aspects of the algorithm, such as totality, or complexity properties.

The problem of providing syntactical characterizations of subrecursive complexity classes such as P, Pspace, etc. has received much attention in the literature. The recent field of Implicit Complexity aims at studying the computational complexity of programs with no reference to a particular machine model and explicit bounds on time or memory, but instead relying on logical or computational principles that entail complexity properties, typically via a controlled use of the available resources. For an introduction to this topic, you may consult the special issue on Implicit Computational Complexity, ACM Trans. Comput. Log., Vol 10, n.4 2009.

Other interesting characterizations have been obtained restricting the interpretation of programming languages to finite domains. The seminal result in this area is an old work of Gurevich ("Algebras of feasible functions", FOCS 1983) where he proved that interpreting primitive recursive functions (resp. recursive functions) over finite structures one precisely get the log-space (resp. polynomial time) computable functions.

Please have a look at my article "Computational Complexity via Finite Types", ACM Trans. Comput. Log., Vol 16, n.15 2015, for more references in this area.


Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible? In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear constraints is quite simple:

$$z \geq x\\
z \geq y\\
x+y \geq z$$

However, if I want to replace $\vee$ with $\wedge$ in that statement, I'm unable to do this. Can this be done? It seems to me this might imply something about quadratic problems in general, but I'm not familiar with that problem, and I can't prove that it can't be done either. Assuming we could linearize this $\wedge$ relation, would this imply something like polynomial-time equivalence between LP and QP?

Thinking about it geometrically, the set $\{(x,y,z) \in [0,1]^3: (x > 0 \wedge y > 0) \Leftrightarrow z > 0\}$ is equivalent to the unit cube $[0,1]^3$ minus the three faces that intersect the origin, but plus the two edges that emanate from the origin that satisfy $z=0$. This is neither an open nor a closed set. I don't know whether that tells us anything about the applicability of linear programming, but considering I've never come across a linear program with strict inequalities, I suspect it might be a problem.

In fact, strict inequalities can't be allowed in linear programs since

$$\min x\\
x>0$$

has no solution.

@KlausDraeger pointed out that the above constraints and the logical statement with $\vee$ aren't equivalent, and for reasons similar to those that apply to the case with $\wedge$, I suspect we can't find equivalent constraints. The subset of $[0,1]^3$ defined by $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ is also neither open nor closed. I overlooked this because for the purposes I had in mind, it seemed to suffice that the linear constraints implied the truth of the logical statement - which isn't the case, I need equivalence between the set of linear constraints and the logical statement.

(Just in case someone is interested, there is a simpler constraint that also implies the truth of $(x > 0 \vee y > 0) \Leftrightarrow z > 0$, and that's $0.5(x+y) = z$; I could not find a set of constraints equivalent to the logical statement, though.)

A linear program consists of a finite collection of inequalities of the form $\sum_i a_ix_i \leq b_i$. Each such inequality defines a closed convex set, and so their intersection defines a closed convex set. Any domain which is not closed and convex thus cannot be represented using linear programming constraints.


Generalizing the Comparison Sorting Lower Bound Proof Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:

For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of the $n$ numbers.
We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
So $\log_2(n!)$ comparisons are required.

Now consider the following generalization of the argument above:

Define a space of possibilities and its size (in the case of sorting, $n!$ orderings)
Define the goal state and its size (in this case, only one correctly sorted answer)
Define the amount of information that is gained at each step of the computation (in this case, one bit since there are only two possible outcomes per comparison)
Calculate the information difference between the space of possibilities (step 1) and the goal space (step 2) and divide by the information gain per step (step 3) to yield the lower bound on the number of steps (in this case, $(\log_2(n!)$ - $\log_2(1))$ / 1 = $\log_2(n!)$).

Please answer all the following questions. I'm less concerned with the correctness of the particulars of step 4 than I am with the correctness of steps 1 - 3.

Are there any problems with the generalized argument?
If the problems can be fixed, what are the fixes?
If the problems can't be fixed, please point out the fatal ones and provide directions to sources which describe these lower-bounds proofs and their pitfalls.

The decision tree method for proving lower-bounds (like the $\Omega(n \lg n)$ lower-bound for comparison based sorting you mentioned) are often called information theory methods.

Here is a short video by Faith Ellen about this method:

Lower-bounds, Part 2/4: Information Theory

The first part is here:

Lower-bounds, Part 1/4: Introduction, Decision Trees


Show that if A is regular, then the subset containing only even language strings, is also regular A language A, even(A) is the subset of A consisting of those strings in A of even length:

even(A) = { x∈A | |x| is even}

I need to use closure properties show that if A is regular, then even(A) is also regular.

Isn't that a definition called "A language is called a regular language if some finite automaton recognizes it", could prove even(A) is regular? How to use closure properties to prove this question?

Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?


How do binary trees use memory to store its data? So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no room, a new static array is created elsewhere in memory larger in size so more data can be stored.

My question is, how do binary trees use memory to store data? Is each node a memory location which points to two other memory locations elsewhere...not necessarily contiguous locations? Or are they stored in contiguous blocks of memory too like a static array or dynamic list?

We use implicit array representation to store Binary Heaps, where if a node has an index $i$, its children are found at indices $2i + 1$ (for the left child) and $2i +2$ (for the right), assuming indices start at 0.

Now this is not wasteful for Binary Heaps since nodes are added in Breadth First method. However for normal Binary Trees implicit array representation is very expensive to grow and wastes space in the order of $O(2^h)$ where $h$ is the height of the tree (Consider skewed binary trees).

For trees having a large number of nodes we use Succint Data Structures as pointed out by Raphael. A normal binary tree of $n$ nodes is stored using $O(nlogn)$ bits (pointer representation), but succinct representations require just $2n + o(n)$ bits and carry out many sophisticated operations in constant time. This link gives us a good overview of a simple representation of succint representations.


What were the research outcomes of the Univalent Foundations Program year (Homotopy Type Theory) The Institute for Advanced Study has had a year-long special program devoted to the Univalent Foundations Program.

At the end of this they have produced a book and a code repository.

At the end of this we see a blog entry in Scientific American claiming:

...it could provide a new, self-contained foundation for all of mathematics.

Now this is a bold claim. By contrast I can see humbler claims such as a simple proof in Agda that the sum of two odds is always an even.

My question is: What novel research did these guys actually produce at the end of the year? All the article indicates is that they wrote some code in Agda. Is it just that we have a new view of Martin-Löf type theory with some applications?

Assumptions

I understand the broader ideas of Martin-Löf type theory as it relates to the isomorphism between Types and Proofs.

The book is itself representative of the research product of the program. The code that they wrote actually is mostly in Coq, to my knowledge, and certainly the development that accompanies the book was written in Coq.

Homotopy Type Theory itself essentially constitutes Martin-Löf, together with the univalence axiom, which essentially states that equivalent types are equal. The notion of equivalence comes from a view that establishes a connection between a synthetic homotopy theory and Martin-Löf type theory, hence the name. This axiom gives way to a powerful type theory that the book shows is capable of reasoning about a lot of important existing foundational mathematics.

In fact, part 2 of the book comprises developments of a more traditional, topologically-motivated version of homotopy theory, set theory, category theory, and a nice constructive presentation of the real numbers. I have not explored the Coq code that much yet, but my understanding is that all of these presentations are accompanied by corresponding Coq source. Since we can formulate all of these important foundations entirely within homotopy type theory, the hypothesis that it might be an important foundation for mathematics going forward makes sense. The idea is that mathematicians will be able to extend these seminal developments towards more results in fields like algebra, topology, and analysis.

Inasmuch as homotopy type theory pertains to being able to do mathematics in Coq via the Curry-Howard correspondence, you can think of homotopy type theory as corresponding to a more powerful instance of Curry-Howard. The most exciting contribution of this work is really that it gives mathematicians language for speaking about mathematics in terms of type theory, and the idea is that this should enable on the one hand, more mathematics being accompanied by mechanized proofs in provers like Coq, as well as computer proofs that correspond more closely to their plain English equivalents. Anyone who has used Coq will tell you that the proofs that you produce often don't end up looking much like equivalent plain-English proofs at all.


Context free languages invariant by "shuffling" right hand side Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.:
$A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; CBD \; | CDB \; | \; DBC \; | \; DCB$
It may happen that the resulting language $L'$ generated by the expanded $G'$ is equal to $L$
For example:
Source               Shuffled
S -> XA | YB         S -> XA | AX | YB | BY
A -> YS | SY         A -> YS | SY
B -> XS | SX         B -> XS | SX
X -> 1               X -> 1
Y -> 0               Y -> 0

Is there a name for such class of grammars ($L(G) = L(G_{\text{shuffled}}))$?

Furthermore, does this theorem hold?

Theorem [it doesn't hold, see Yuval's answer and comments]: If exists a grammar $G$ such that, $L(G) = L(G_{\text{shuffled}})$, then for all $G'$ such that $L(G) = L(G')$ we have $L(G') = L(G'_{\text{shuffled}})$
In other words the "shuffle invariance" of grammars also corresponds to a class of languages.

Your theorem doesn't hold.
Consider the grammar
$$
\begin{align}
&S \to 1T \mid T1 \\
&T \to 23 \mid 32 \\
\end{align}
$$
Shuffling the grammar results in the same language.
Now consider instead the grammar
$$
S \to 123 \mid 132 \mid 231 \mid 321
$$
which generates the same language.
Shuffling this grammar results in a larger language.


Complexity of finding these original parameters I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple solutions, I want the minimal (if possible).

It is clear that $c$ has to be odd, so if $c$ given to me is not, then I can immediately stop the computation. However, I'm not sure what other cases there can be.

Also, I'm not sure if there is a better alternative than the following (or even brute-force): let $d = \min(a, b, c)$, and have $m, s$ be roughly $\sqrt{d}-m$, and try brute-force starting from there.

You can compute $m,s$ from the equations: $s = (c-1)/2$ and $m = (b-1)/s$; both must be integral. You can then check that indeed $m(s+1) = a$. If this holds, then you have found the unique solution $m,s$, otherwise there is no solution.
More generally, this method allows you to find the unique real solution to your system of equations, if any exists.

Note that $m = (b-1)/s = 2(b-1)/(c-1)$. Hence $s,m$ are integers if $s$ is odd and $c-1$ divides $2(b-1)$. If they are integers, the final equation is satisfied if
$$
a = ms + m = b-1 + \frac{2(b-1)}{c-1} = (b-1) \frac{c+1}{c-1}.
$$
Another way to state this condition is
$$
a(c-1) = (b-1)(c+1).
$$


Planar graphs of bounded degree: mixing time = cover time? For many planar graphs of bounded degree (binary tree, lattice, cycle) the (1/4)-mixing time and the cover time are equal, up to log-factors. Is this always the case?

The answer turns out to be no. A counterexample, kindly suggested to me by Balász Gerencsér, is a $\sqrt{N}$ by $\sqrt{N}$ grid, with a path of length $\sqrt{N}$ glued to it. One can show that

the mixing time of a simple random walk on this graph is $O(N\log N)$ (by combining Cheeger's inequality and the Spielman-Teng [1] bound on the spectral gap)
the cover time of a simple random walk on this graph is $\Omega(N^{3/2})$ (by combining Matthews method with an expression of the hitting time using effective resistance)

[1] Spielman, Daniel A., and Shang-Hua Teng. "Spectral partitioning works: Planar graphs and finite element meshes." Linear Algebra and its Applications 421.2-3 (2007): 284-305.


How do we determine whether a heuristic is better than another in A* search Algorithm? I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics.

Currently, I explored Manhattan and Euclidean distances. Which other heuristics are available? How do we compare them? How do we know whether a heuristic is better than another?

A good heuristic should approximate the actual distance to the goal as closely as possible, without going over it.

If heuristic1 returns a greater or equal value than heuristic2 for every input (while still being valid), then heuristic1 is better. In your case, Manhattan distance is better than Euclidean distance because the value it returns is never smaller than Euclidean distance and is sometimes larger. (Unless you can move diagonally in the maze, in which case Manhattan distance is an invalid heuristic and Euclidean distance might be as well.)

If heuristic1 returns a larger value for some inputs, and heuristic2 returns a larger value for others (and both are valid), then heuristic3(x) = max(heuristic1(x), heuristic2(x)) is better than either of them.

If the heuristics are slow, it's more complicated. Since heuristic3 will be even slower than heuristic1 or heuristic2 alone, it could end up being worse overall if it doesn't improve the estimate by very much. There's no unambiguous way to choose the best heuristic in this case. You basically have to benchmark and decide how much cleverness you can afford.


NFA-$\epsilon$ extended transition function for inverted strings It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows:
\begin{align*}
\hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\
\hat\delta(q,\epsilon) &= ECLOSURE(q) \\
\hat\delta(q,\alpha x) &= \bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(p_i,x))
\text{ for } \alpha \in \Sigma^* \text{ and } x \in \Sigma
\end{align*}

I would like to give an equivalent definition for the function but now considering an string $w \in \Sigma^* $ such that $w = x\alpha$ with the same definitions for $x$ and $\alpha$ given above. But what I've only got is the base case (i.e. $w = \epsilon$) which is pretty the same. Any hints to define the function like that?

First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p_i},x))$ (green for highlighting the difference).

The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^*$, is
$$
\hat\delta(q,x\alpha) = \bigcup_{p_i \in ECLOSURE(\delta(q,x))} \hat\delta(p_i,\alpha)
$$


Group adjacent sections to create groups with biggest value, value is changing in groups I have sections 1,2,3...44. We can group only adjacent ones and create groups of maximum size S = 4.
There are two possible variations of this problem:

can not overlap at all (preferred)
can overlap only in outer sections (numbers) /i.e. 1+2+3, 3+4+5+6, 6+7+8 ...

Each section (or group) has it's own value, which is calculated in database query. To simplify, let's assume that it is something like:
SELECT COUNT(*) FROM table WHERE section IN (:sectionNumbers)

Where sectionNumbers parameter is array of sections in group (1,2,3 i.e.)
The value is always greater or equal to value of group with less elements. For example group 1+2+3+4 has value of 100 but the same group without element 4 has value of 70(but it could be 100 as well).
Is there an algorithm which can group those sections (numbers) to maximize sum of group values and in same time try to make those groups as small as possible? If there's not such an algorithm, which is the most similar problem to this one? Maybe I can figure out how to solve this with some similar problem solution.
Not every section has to be in group, but if it is possible, merge them.
Correct result for example could be:
Group: [1], [2+3+4+5], [5+6+7+8], [9+10+11+12], [13+14+15+16], [16+17+18], [19+20+21] ...
Value: (11)   (965)      (146)       (242)         (600)         (611)       (94)

In this example is section 1 alone, because value of group 2+3+4+5 (965) is higher then if we group 1+2+3+4 (i.e. 300)

Your problem can be solved with dynamic programming using a straightforward algorithm.  Let $V[i..i+j]$ denote the value of a single group with numbers $i,i+1,\dots,i+j$.  You say you know all of those values.  Let $A[i]$ denote the value of the best way to group all of the numbers $1,2,\dots,i$.  Then $A[i]$ satisfies the recursive equation
$$A[i] = \max(A[i-4] + V[i-3..i], A[i-3] + V[i-2..i], A[i-2] + V[i-1..i], A[i-1] + V[i..i]).$$
Set $A[-3]=A[-2]=A[-1]=A[0] = 0$.  You can evaluate $A[1]$, $A[2]$, $A[3]$, etc. in that order, using a linear scan.  This takes 44 iterations of the loop, and each iteration of the loop uses a few simple lookups and operations, so the total running time will be extremely fast.  Finally, $A[44]$ holds the solution to your answer, i.e., the value of the best way to group the numbers 1,..,44.  If you want to retrieve the grouping itself, you can do that via standard techniques with prev pointers (each time you take a max, remember which one was the largest; or go back and re-compute it).


Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2) In The Algorithm Design Manual section 5.9.2, covering graphs and articulation vertices, Steven Skiena writes

  Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v,
  meaning the oldest ancestor of v that we can reach by a combination of tree edges
  and back edges.

This phrasing is ambiguous.  On the errata page of his website, he clarifies:

  it is clearer to say:
  "denote the earliest reachable ancestor of vertex v, meaning the
  oldest ancestor of v that we can reach from a descendant of $v$
  by using a back edge."

But to me, this phrasing is still somewhat ambiguous.  Consider the following four-vertex graph G:

    A
    |
+ - B
|   |
|   C
|   |
+ - D

We conduct an alphabetical depth-first search (DB is a back edge).  According to Skiena's revised definition, it would seem that A is a reachable ancestor of C as follows:  D is a descendent of C, and we can reach A from D using a back edge by following the path DBA.  However, execution of Skiena's code for finding articulation vertices via depth-first search on G results in reachable_ancestor[C] = B, not A; therefore I don't think he intends for A to count as a reachable ancestor of C.

Might it be more accurate to say that reachable_ancestor is the
oldest ancestor of v that we can reach from a descendant of v
by using a back edge but without passing through any other ancestors of v?

A small modification makes the definition agree with Skiena's algorithm.
"Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of v by using at most one back edge."

If we view undirected edges as "two-way" directed edges, then to reach A from C would require two back edges: DB and BA.  Thus the earliest ancestor that can be reached from C by using at most one back edge is B.


The length of the smallest co-prime chain between any two integers Consider the following statement:

for any $a < b \in \mathbb{N}$, one of the following holds:

$\gcd(a,b) = 1$.
there is a $a < x < b$ such that
$\gcd(a,x) = \gcd(x,b) = 1$.
there are $a < x < y < b$ such that
$\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$.

Is this statement true?

Motivation:
I found a variant of this problem in one of the recent algorithms competitions.
Consider the following problem:
Input: two integers $a$ and $b$ where $a \lt b$.
Output: smallest number $l$ such that there are integers
$a = x_0 < x_1 < x_2 < \ldots < x_l < x_{l+1} = b$ such that
all consecutive integers in the list are co-prime:
$\gcd(x_i, x_{i+1}) = 1$ for $i=0,\ldots, l$.
Examples:

$a = 7, b = 13$:
$\gcd(a,b) = 1$, therefore $l = 0$.

$a = 10, b = 12$:
$\gcd(a,b) = 2 \neq 1$, therefore $l \geq 1$.
Let the sequence be $10, 11, 12$. $\gcd(10, 11) = 1, \gcd(11, 12) = 1$.

$a = 2184, b = 2200$:
There is no $a< x < b$ such that $\gcd(a,x)=\gcd(x,b)=1$.
However, we can find $2$ integers that satisfy this problem.

There is a reference algorithm that algorithms are evaluated against.
That algorithm assumes that

There is always an $l$ that satisfies the condition.

$l\leq 2$.

I don't see why they are true.
I have a polynomial time algorithm that does not assume either of them.
I am not losing out on the asymptotic performance
compared to the reference algorithm,
but I could get the performance constants much lower
if I can understand and prove the validity of the assumptions.

The conjecture $\ell \leq 2$ seems to be open. It is stated as Conjecture 3 in a paper of Dowe. Dowe does show that the Goldbach conjecture implies that $\ell \leq 3$, and mentions that Alan Woods showed in his PhD thesis that $\ell$ is bounded. Perhaps the recent proof of the odd Goldbach conjecture also implies a definite and small bound.

If $\ell > 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell > 2$ then both $b-a$ and $b-a-1$ have to be Erdős-Woods numbers. A059756 lists the first few Erdős-Woods numbers. While all numbers on that list are even, there are also odd Erdős-Woods numbers, some of which are listed in A111042. The smallest values of $a$ corresponding to given differences are listed in A059757. While this list is not increasing, it does seem as if the numbers are growing pretty fast. Any counterexample to $\ell \leq 2$ would to be such that both $b-a$ and $b-a-1$ are Erdős-Woods numbers, and in particular $b-a > 430$ (per A059756). This suggests (but does not prove) that any such counterexample will be huge, and so for all practical purposes we can assume that $\ell \leq 2$.


Number of balanced binary trees (The Art of Computer Programming) In the section 6.2.3 (Volume 3) Donald Knuth says:

... we can ask about the number $B_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the generating function $B_h(z) = \sum_{n\ge0} B_{nh}z^n$ for small $h$, from the relations
$$B_0(z) = 1,$$ $$B_1(z) = z,$$ $$B_{h+1}(z) = zB_h(z)(B_h(z) + 2B_{h-1}(z)).$$

I would understand this formulas if they were like this:
$$B_0 = 1$$ $$B_1 = 1$$ $$B_{h+1} = B_hB_h + B_hB_{h-1}+B_{h-1}B_h = B_h(B_h + 2B_{h-1})$$
Which means that there is only one empty tree ($h=0$), only one tree with a single node ($h = 1$) and number of other trees (of $h+1$, where $h\ge1$) can be calculated as the number of all combinations of shorter trees - having trees shorter by one on as both sub-trees ($B_hB_h$), having shorter by one on the left and shorter by two on the right ($B_hB_{h-1}$) and the wise versa ($B_{h-1}B_h$).
These formulas are actually the same as the ones from the book if $z=1$. This makes me think that it is correct.
Is my reasoning correct? And if it is, can anyone explain what this $z$ actually stands for?

The way I tend to interpret these parameters is to think of them as stand-ins for some type of basic structure in your enumeration problem. This might sound a bit too abstract, so let's look at a (simpler) concrete example.

Let's consider the task of enumerating linked lists. The question I'm interested in is, given a list of unit types (those whose only element is the unit $\circ$), how many lists over unit are there such that their length is $n$? Now, this question was chosen for a very simple purpose: it's easy to see what the answer is. If each element of your list can only be a single element $\circ$, then obviously there's exactly one list of size $n$.

Now, one way to solve this is to look at the inductive definition of a list.
$$
\textrm{List}_{\circ} = \circ :: \textrm{List}_{\circ} ~\textrm{or}~ []
$$

This says that a list over $\circ$ is either a $\circ$ prepended to another list, or it is an empty list. Flattening out the fancy operators into tuple form, and turning the word $\rm or$ into a $+$, we have

$$
\textrm{List}_{\circ} = (\circ * \textrm{List}_{\circ}) + []
$$

Since an empty list [] can be thought of as a tuple with zero $\circ$s inside, let's rewrite it as $\circ^0 = 1$. This then gives an equation

$$
L = \circ * L + 1
$$

Suppose that we're working over the complex field, then this is equivalent to (assuming that $\circ \ne 1$)
$$
L = \frac{1}{1 - \circ} = \circ^0 + \circ^1 + \circ^2 + \circ^3 + \dots
$$

Now, notice that the formal power series of $L$ with respect to $\circ$ exactly specifies all of the possible lists over the unit $\circ$. That's kind of cool, but is it just a coincidence?

To find out, we turn our attention to a related problem, that of counting lists over the booleans $(\bot, \top)$. Once again, we start with the inductive definition

$$
\textrm{List}_{2} = (\bot ~\textrm{or}~ \top) :: \textrm{List}_{2} ~\textrm{or}~ []
$$

Doing the same transformation as before, we find that

$$
L_2(\bot, \top) = \frac{1}{1 - (\bot + \top)} = 1 + \bot + \top + \bot^2 + \bot\top + \top\bot + \top^2 + \bot^3 + \bot^2\top + \dots
$$

Interesting, it seems like for certain enumeration problems, the inductive definition we use to specify/construct a type can be translated into this functional over the complex numbers. What's more, this functional's formal power series seems to generate a series of constructions that are isomorphic to the objects from your inductive specification. This is more or less the idea behind these generating functions: their series representation "generates" the combinatorial structures that you are studying.

Now, let's come back to the counting problem. So what if we know that $\frac{1}{1 - \top - \bot}$ represents our combinatorial class? How does this help us with the enumeration problem? Well, the counting problem asks for the number of lists that contains a certain number. This tells us that even if $\top$ and $\bot$ are distinct, they still each contribute the same number of elements (namely, 1) to the list. We can specify this "blindness" with the equality $z = \bot = \top$, so that

$$
L_2(z) = L_2(z, z) = \frac{1}{1 - 2z} = 1 + z + z + z^2 + z^2 + z^2 + z^2 + z^3 + z^3 + \dots
$$

simplifying, this series yields

$$
L_2(z) = 1 + 2z + 4z^2 + 8z^3 + \dots + 2^k z^k + \dots
$$

Since each of the lists under $z^3$ are lists of length 3, this series then tells us that there are $2^3$ distinct boolean lists of length 3.

Herein lies the power of these generating functions. By "erasing" properties that you don't care about (like the distinctness of true and false in a counting problem), you end up with this formal series whose coefficient gives the total count of a subclass of interest. Therefore, the question du jour of these "analytic" enumeration problems is not how one interprets giving $z$ a specific value, but rather how one can show that the function is analytic/differentiable around the origin and what its coefficients are.

This glosses over a lot of the details, but the intuition should hopefully remain. For your particular problem, we can follow the same recipe to eventually derive Knuth's tower of balanced tree construction.

Now, a height-balanced tree is a binary tree such that the height of each child of a tree is always within one unit of any other child of a tree. This gives a simple case-analysis to consider.

A balanced tree of height $h$ is a root node together with children such that they are:

Balanced, so that the height of both children are the same, aka $h - 1$.
Unbalanced but left-skewed, so that the height of the left children is larger, aka $h - 1$ and $h - 2$.
Unbalanced but right-skewed, so that the height of the right children is larger, aka $h - 2$ and $h - 1$.

This then yields an inductive specification

$$
BBT_h = (BBT_{h-1}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-2}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-1}, \circ, BBT_{h-2})
$$

Where the tuple $(L, \circ, R)$ denotes the balanced tree rooted at $\circ$ with the left branching to $L$ and the right branching to $R$. Transferring to the complex field, this gives
$$
B_h = \circ B_{h-1}^2 + \circ B_{h_2} B_{h-1} + \circ B_{h-1} B_{h-2}
$$
taking advantage of the newly found freedom of commutativity, and reassociating, we have
$$
B_h(\circ) = \circ B_{h-1}(B_{h-1} + 2 B_{h-2})
$$
Since this is a two-step recurrence, we need to specify their initial conditions. $B_0$ is the class of balanced trees with zero nodes, so we have $B_0(\circ) = \circ^0 = 1$. $B_1$ is the class of balanced trees with one node, so we have $B_1(\circ) = \circ^1$. Finally, substituting $z = \circ$ gives Knuth's generating functions.

Of course, we've skipped over one bit: we haven't shown that there's some neighborhood around the origin such that $B_k(z)$'s formal series actually converges. Fortunately for us, these forms of inductive constructions are all generally admissible, so we need not worry about them here.

Finally, the last step is to characterize the coefficient of $z^k$. To be fair, the full problem is to find the coefficients of $\sum_h B_h(z)$, but it suffices to just find the coefficient for some $B_h(z)$, since we can then sum over the rest independently. There's two general strategies we can pursue:

Find an explicit characterization of $B_h(z)$.
Use the implicit recurrence directly and see if we can find the coefficients directly.

Here, I imagine that Knuth's approach is probably the second approach. In particular, given two functions $A(z) = a_0 + a_1 z + a_2 z^2 + \dots$ and $B(z) = b_0 + \dots$, we have
$$
A(z) * B(z) = \sum_n \sum_{k \le n} a_k b_{n-k} z^n
$$
and in particular
$$
zA(z) = a_0z + a_1z^2 + \dots
$$

Letting $[z^n]f(z) = f_n$ be the coefficient of $z^n$ in $f(z)$, then we have
\begin{align*}
[z^{n+1}]B_h(z) &= [z^n](B_{h-1}(z)^2 + 2B_{h_1}(z)B_{h-2}(z)) \\
&= \sum_{k \le n} ([z^k]B_{h-1}(z) + [z^k]B_{h-2}(z)) \times [z^{n-k}]B_{h-1}(z)
\end{align*}

This then gives a rather mundane dynamic programming algorithm to compute these coefficients. You can also probably appeal to some analytic techniques to solve for asymptotic properties, but that's for another time.


Strassen's algorithm on unit vectors? I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum.

public Double dotProduct(List<Double> v, List<Double> u) {
    Double dotProduct = 0;
    for (int i = 0; i < 128; i++) {
        dotProduct += v.get(i) * u.get(i);
    }
    return dotProduct;
}

Will strassen's algorithm perform better?

Strassen's algorithm is for multiplying square matrices, not vectors. Your algorithm already runs in (asymptotically) optimal time $O(n)$ (where $n$ is the dimension of the vector), and also uses the optimal number of multiplications.


A basic question about predicate logic Suppose we have a statement: "Tom has a car" and we have an auxiliary clause that is
has(x, y): x has y then to write the statement in logic I am guessing the following ones:
$\exists$y has(Tom,y)
or
has(Tom,car)
The reason I am not sure which to select is I don't know whether or not "car" is a specific constant similar to Tom?

There is no universal answer. It depends on how you choose to model the universe of discourse you've been assigned to model.
We'd normally expect there to be multiple cars that appear as distinct individuals in the model, and we expect the predicate has to be the relationship that expresses which individual owns which individual object, i.e. between individual persons and individual cars.  In that case, if car is a constant, it must denote a particular car, so you'd need other constants, for instance, car2, car3, etcetera, to denote other cars. It's awkward, but it can be done.
So it is valid, but very impractical. In practice, we usually see a predicate is_car(x), as Yuval Filmus suggests, and a couple of individuals for which that predicate holds that stand for the individual cars that exist in the universe of discourse being modelled.
Tom can be a constant representing a particular person, and we can use other constants such as Dick and Harry to represent other persons. Courses in logic tend to do this because they are proper names and they use sentences such as Tom has a car which imply that there is, indeed, exactly one Tom in the universe of discourse, so you can do this.
Once again: this is valid, and probably what your professor wants you to do, but it is highly impractical.
In practical applications of logic, e.g. when designing a relational database, we can't usually assume that names such as Tom uniquely identify a person, so we model names not as constants, but as predicates.
For instance, we may use a predicate has_first_name(x,y), and the statement Tom has a car can then be expressed as
$\exists! x: \mbox{has_first_name}(x,\mbox{"Tom"}) \\ \wedge \\ \exists x: \mbox{has_first_name}(x,\mbox{"Tom"}) \wedge \exists y: \mbox{is_car}(y) \wedge \mbox{has}(x,y)$
PS: Mars points out a more serious issue with using constants for cars: they always refer to a particular car, and Tom has a car doesn't - you could only express it by a statement that lists every individual car, like this: $\mbox{has}(\mbox{Tom},\mbox{car}) \vee \mbox{has}(\mbox{Tom},\mbox{car2}) \vee \ldots$.


Optimal Algorithm for checking if a number is a multiple of three I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.

I currently have an assignment to work on:

  An algorithm reads in the binary digits of a positive integer $N$ and determines whether $N$ is a multiple of 3. Show that the algorithm takes time at least of order $n$, where $n$ is the number of binary digits of $N$.

Basically, I have thought up of an algorithm which I'm pretty sure is correct:
(I don't know what's the best/correct way to write an algorithm but here's my attempt)

Start with a binary number $x=a_na_{n-1}\dots a_1a_0$.
Then compute $x'=\sum^{i=n}_{i=0} (\frac{3}{2}+\frac{1}{2}(-1)^{i+1})a_i$.
Then $x'=0 \mod3 \iff 3|x$

This works because $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$

I can guess that my algorithm takes time at least of order $n$ because I need order $n$ steps to compute $x'$.

However, I have my doubts:

How do I know my algorithm is the optimal algorithm?
Am I 'cheating' by saying $x'=0 \mod3 \iff 3|x$?
Am I even answering the question correctly by providing such an algorithm or is there some other sort of analysis to show lower bounds for algorithm time?

If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you have to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)


Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the math, specifically the optimization part (for selecting weights), I ran into a problem: I couldn’t understand the Broyden–Fletcher–Goldfarb–Shanno algorithm.
I understand that it (basically) uses newton's method, expect that it finds the zeroes of the derivative of the original function (to find the local minima of the original function).

However I was having trouble following the notation and math that is written on Wikipedia about it:

First of, I do understand that Bk is a Hessian matrix that holds the partial second derivatives and f(x) is the original function that we are finding the local minima of. Moving on to step 1, I do not understand why the search direction needs to be solved. (Is it because we need to figure out whether the zero of the derivative is a local maximum or minimum of f(x) aka perform the first derivative test). In step 2, I do not understand why line search needs to be performed. In step 3, I do not understand what the product of ak and pk means. In step four, (correct me if I am wrong), yk equals the change in y or f(x). Finally, I know step 5 is trying to approximate Bk+1, which is what newton's method does, but I do not understand why its trying to estimate another Hessian matrix, shouldn't it be estimating a point? Or is it estimating a matrix because the algorithm is supposed to work with a multidimensional space, but then how does the partial second derivative matrix lead to finding the local minima of the original function? Also, what does the right side of the equation mean with all the vector/matrix multiplication and division. (I know this is a quasi-netown method but do not really understand it).

I tried to search the internet for my answers, but I couldn't really find anything. I am only in high school and don't have anyone who can explain me this math. So I really appreciate your help. Thank you so much in advance.

The purpose of the "search direction" is that we want to move closer to a minimum of $f(x)$.  The gradient tells us the direction of steepest descent (as in gradient descent).

The reason we do the line search is to figure out how far to travel in that direction.  The gradient tells us the direction; but it doesn't tell us how far to go in that direction.

The product $\alpha_k \mathbf{p}_k$ is an ordinary product of a scalar and a vector; i.e., component-wise product.  You probably need to study a bit of linear algebra and multivariate calculus to get familiar with this sort of thing -- that's a vitally important foundation.

Step 5 is the heart of BFGS.  A full Newton method would calculate the Hessian (matrix of second partial derivatives) at each point; i.e., it would re-calculate the Hessian in step 5.  BFGS doesn't re-calculate it from scratch, as re-calculating it is expensive.  Instead, it tries to make an estimate/guess of how the Hessian has changed.  That's what step 5 is doing.  This estimate is less accurate than simply recomputing the full Hessian matrix, but it's faster.

You're not going to be able to understand what's going on in BFGS from Wikipedia.  Wikipedia's description is not very good, and there is no explanation of where the method came from.  Look for a better, more detailed explanation that explains where these steps came from, the intuition of what's going on, and how these particular formulas were derived.  Wikipedia is a great resource, but it's not a very good source for learning BFGS.


What is meant by Category theory doesn't yet know how to deal with higher-order functions? In reading Uday Reddy's answer to What is the relation between functors in SML and Category theory? Uday states

  Category theory doesn't yet know how to deal with higher-order
  functions. Some day, it will.

As I thought Category theory was able to serve as a foundation for math, then it should be possible to derive all of math and higher-order functions.

So, what is meant by Category theory doesn't yet know how to deal with higher-order functions? Is it valid to consider Category theory as a foundation for math?

The issue with higher-order functions is simple enough to state.

A type-constructor like $T(X) = [X \to X]$ is not a functor.  It should have been.
A polymorphic function like ${\it twice}_X : T(X) \to T(X) = \lambda f.\, f \circ f$ is not a natural transformation.  It should have been.

If you read Eilenberg and MacLane's original category theory paper, (PDF) the intuitions they present cover those cases.  But their theory doesn't.  Theirs was a great paper for 1945!  But, today, we need more.

The reaction of category theorists to these issues is a bit perplexing.  They act as if higher-order operations form a Computer Science idea; they are of no consequence to mathematics.  If that is so, then a foundation of mathematics would not be good enough for a foundation of computer science.

But I don't seriously believe that.  I believe that higher-order functions would be quite important for mathematics as well.  But they have not been seriously explored.  I am hopeful that, some day, they will be explored and the limitations of category theory will be realized.


Primitive word and cyclic rotations Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$.

Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?

Yes, this is true. The direct implication ($\Rightarrow$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J.
9 (1962) 289-298.  Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.


Worst Case Scenario in MaxHeapify First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most give a mathematical answer, but can't give a real example.

In CLRS 3ed pg 155 we have "The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the $\Theta(1)$ time to fix up the relationships among the elements $A[i]$, $A[LEFT(i)]$ , and $A[RIGHT(i)]$, plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i (assuming that the recursive call occurs). The children’s subtrees each have size at most $2n/3$ - $\textbf{the worst case occurs when the bottom level of the tree is exactly half full}$ — and therefore we can describe the running time of MAX-HEAPIFY by the recurrence $T(n) \leq T(2n/3) + \Theta(1)$.

I understand why the maximum nodes a subtree can have is around $2n/3$. I have two questions:

1) We're dealing with a heap - a  "binary tree that is completely
filled on all levels except possibly the lowest, which is filled from the
left up to a point" (CLRS pg 151). For a given n, there's only one legal tree structure - we can't "make" its bottom level exactly half full. So what does it mean to say the worst run-time for n is when the bottom level is exactly full? If you mean that the worst-case happens when n is such that the bottom-level is half-filled, then it's worse in comparison to what? trees of other sizes? obviously different sizes have different run-times!

2) I understand why when there's a height difference it'll take another MaxHeapify call, but why does the bottom level have to be full? Can you give me an example of two trees of height larger than 1, where in one its bottom level is half-full, and in the other it's almost half-full (missing just one leaf from being half-full) and there's a worse run-time in the first one?

1) This is the worst case in regards to all the possible recurrences and their respective sub-problem sizes.

Let's take some small sample $n$'s for a tree of height $3$. This is to show how the varying worst-case sub-tree size ranges from 1/2 to 2/3.

$$
\begin{align}
n &\quad \text{bottom half-full?} & \text{size of worst case sub-tree} \\
8 &\quad no & 4/8 \\
9 &\quad no & 5/9 \\
10 &\quad no & 6/10 \\
11 &\quad yes & 7/11 \\
12 &\quad no & 7/12 \\
13 &\quad no & 7/13 \\
14 &\quad no & 7/14 \\
15 &\quad no & 7/15 \\
\end{align}
$$

We deal in worst case scenarios when defining running times. This is why we must look for the worst case sub-problem (sub-tree) to define the recurrence relation. Clearly with varying $n$ values, the recurrence would vary, so we must take the worst of them. This is clearly the result of the deepest level being half-full, resulting in the upper bound recurrence:

$$T(n) \leq T\left(\frac{2n}{3}\right) + \Theta(1)$$

Alternatively if we were looking for a lower bound, we should look for the best case of all those worst case sub problems. We could then achieve:

$$T(n) \geq T\left(\frac{n}{2}\right) + \Theta(1)$$

2) The heap with the bottom level half full will always have the worse running time no matter how trivial the difference is. Minor differences like the one you described are not important. We're not comparing for one instance, time complexity is used to compare on a larger scale. On a large scale you can see the size of the sub problem ranges from n/2 to 2n/3.


How to find all topological sortings of a special DAG in O(N^2) I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
Problem description:

Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.
Since the required answer can be quite large, print it modulo $10^9+7$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.
Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at  position. Assume that there are $X$ outgoing edges to the children from  and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.
Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X_1, X_2, \cdots X_i$ such that  $X_1, X_2, \cdots X_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.
$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$
Note that this $\sum_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.
Now, for $X$ nodes basically you have computed $dp_j$, number of filling up $j$ spaces using subtrees of $X$ nodes such that $X_1, X_2, \cdots X_x$ is included. Lets call this $dp$ as $left[]$ and similary call the $dp$ for $Y$ nodes as $right[]$.
$$DP(i, j) = \sum_{1\le k < j} nCr(j-1, k) \times {left}_k \times nCr(a, b) \times {right}_{a-b}$$
Where $a = SZ_i - j$, $b = SZ_x - k$ and $SZ_i$ denotes the size of subtree rooted at $i^{th}$ node & $SZ_x$ denotes the sum of sizes of all subtrees rooted at all those $X$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $O(N^2)$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.
I believe that the added constraint that the number of edges is equal to $N-1$ simplifies the solution, and I couldn't think of any other possibility.
Could anyone kindly validate the solution?

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.


Why do OS locks require hardware support? I just read the chapter on locks in the book Operating Systems: Three Easy Pieces, and it discusses an implementation of locks (see in Figure 28.9) that involves a test-and-set hardware instruction.
The textbook emphasizes that both hardware support and OS support are necessary to build an efficient locking mechanism. Wikipedia echoes this sentiment:

Locks typically require hardware support for efficient implementation. This support usually takes the form of one or more atomic instructions such as "test-and-set", "fetch-and-add" or "compare-and-swap". These instructions allow a single process to test if the lock is free, and if free, acquire the lock in a single atomic operation.

I think I've come up with an alternative lock implementation that doesn't require hardware support. It seems to have relatively similar performance overhead, while guaranteeing mutual exclusion, so making this post to find out if I'm missing something.
Textbook Lock Implementation
I'll first summarize the textbook implementation. For setup, we need to:

Maintain a single flag (set to 0 or 1) and a queue (of thread IDs).
Maintain a separate flag for a "guard" lock, which will be a simple spin lock. Because the guard lock is meant to protect a relatively small critical section, the performance overhead of a spin lock won't be as pronounced.

When a thread wants to acquire a lock, it will do the following:

First, spin with the test-and-set instruction until you acquire the guard lock.
Once acquired, check if the flag (of the main lock) is set to 0. If it is, simply set it to 1, and the lock has been acquired! If the flag is set to 1, proceed to step 3.
Push the current thread ID onto the queue.
"Park" the current thread. This is an instruction in Solaris that basically puts a thread to sleep.

On the other hand, when a thread wants to release a lock, it will do the following:

Spin until you acquire the guard lock.
If the queue is empty, set the flag to 0, and you're done. If the queue is nonempty, proceed to step 3.
Pop a thread ID from the queue, and "unpark" the corresponding thread (wake it up).

My Implementation (without hardware support)
First, some setup:

Every lock must be initialized with some unique lock ID.
Inside the OS, maintain a "lock table." For each lock ID, the lock table will maintain a flag (0 or 1) and a queue (of thread IDs).

Then, when you want to acquire the lock:

Make a system call (which might be called something like lock) and pass in the lock ID as an argument.
Enter the OS. Since the OS manages scheduling, we guarantee mutual exclusion for the following steps.
Search the lock table for the specified lock ID. If the flag is 0, set it to 1. Then return; the lock has been acquired! If the flag is 1, proceed to step 4.
Push the calling thread to a queue.
Block the calling thread, so for now, it cannot be scheduled.

To release a lock:

Again, make a system call with the lock ID as an argument.
Entering the OS (again guaranteeing mutual exclusion), search the lock table for the specified lock ID. If the queue is empty, set the flag to 0, you're done. If not, proceed to step 3.
Pop a thread from the queue, and unblock it. It should be scheduled soon.

Note that when we are acquiring a lock, a context switch is not necessary if the lock is available, so the performance overhead should be minimal.
It's likely that I'm missing a small detail that will make me look stupid, but that's why I'm asking this question in the first place.

Since the OS manages scheduling, we guarantee mutual exclusion for the following steps.

But how do you guarantee mutual exclusion inside the OS?
On a single-processor machine¹, you know that only the kernel code that serves the lock system call is executing. All other threads are in a known state. However the kernel code can be interrupted at any time by a hardware interrupt. This could be the timer interrupt that tells the kernel that it's supposed to schedule a different thread. You can implement locks just by manipulating the bits in the lock table, but only if interrupt code won't manipulate the lock table. So it's possible to implement a lock this way, but it imposes some design constraints in the kernel.
On a multi-processor machine, all you know is that this processor is serving the lock system call. The other processors could be manipulating the lock table at the same time. At step 3, you read an entry from the lock table and then possibly write to that entry. Another processor could have read or written the entry between your read and your write². Avoiding this race condition is precisely why processors have instructions such as compare-and-swap that combine a read and a write.
Even on a single-processor machine, making a system call is a heavyweight operation compared to a single instruction such as compare-and-swap. It's no good for high-speed concurrency.
¹  By single-processor, I mean a machine that executes a single thread at a time. In this context, a machine with a single piece of silicon that contains multiple logical cores is a multi-processor machine.
²  And in the real world, it can get worse, because processors don't always have a consistent view of memory, so two processors could for example take the same lock independently even if their read/write sequences don't overlap. But even with consistent memory, interlacing read/write sequences spells doom for a naive lock implementation.


Is there a way to hash a turing machine? If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which can later be decoded to give us back the deltas) ? It doesn't matter if all the natural numbers map one-to-one to all the Turing machines.

Sure.  Any Turing machine can be represented as a bit string (print out the description of the Turing machine).  Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).


Automata for empty language I am trying to understand how many states should be there in a Finite Automata which does not accept anything.

I thought it to be containing only one non-final state, the starting state, with all transitions going to itself.

But one of my teachers mentioned that the set of final states cannot be empty. Does that mean there will be two states states, one start state and one final state, with no transition between the two?

The standard definition of DFA (as well as NFA) allows the set of accepting states to be empty. Indeed, otherwise the Myhill–Nerode theorem would be false. The theorem states that the number of states in a minimal DFA for $L$ equals the number of equivalence classes in the Myhill–Nerode relation for $L$. When $L = \emptyset$, this relation contains one equivalence class (consisting of all strings), and so there should be a DFA for $L$ having a single state.

Of course, you can define DFAs in any way you like, and in particular, your teacher's definition still results in the same class of regular languages. Nevertheless, the standard definition is better, for the reason stated above.


Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$ So far we have learned Recursion Tree, Substitution Method, and Master's Theorem.
I'm not sure how we can find lower AND upper bounds.
I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, but how can I find both upper and loewr?

It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".


Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang) I am learning about quantum error correction which is for a part based on classical linear error correcting code.

There is a very basic answer on an exercice I do not understand. Here is the problem (From Nielsen & Chuang, page 450, exercice 10.25)

  Let $C$ be a linear code.
  Show that if $x \in C^{\perp} $, then: $\sum_{y \in C} (-1)^{x.y} = |C|$
  Show that if $x \notin  C^{\perp}$, then: $\sum_{y \in C} (-1)^{x.y}=0$

I can show the first one using the definition, basically if $x \in C^{\perp}$ by definition $\forall y \in C$ I have $x.y=0$

Thus: $\sum_{y \in C} (-1)^{x.y} = \sum_{y \in C} (-1)^0 = |C|$ (where I assume that what is called $|C|$ is the number of element in the linear code which is $2^k$ if we want to encode $k$ bits an information right ?

However I don't understand the second one. Indeed, if $x \notin C^{\perp}$ then $x.y=1$ (We work with modulo 2 scalar product). And we have:

$$\sum_{y \in C} (-1)^{x.y}=\sum_{y \in C} (-1)=-|C|$$

Where is my mistake ?

In summary my questions are:

Do you agree with me that if we want to encode $k$ bits of info, then $|C|=2^k$
Why for $x \notin C^{\perp}$ $\sum_{y \in C} (-1)^{x.y}=0$

Suppose that $e_1, \ldots, e_k$ are (linearly independent) rows of the generator matrix of $C$. We can find vectors $e_{k+1}, \ldots, e_{n}$ s.t. $\{e_i\}_{i=1}^n$ is a basis in $\mathbb{F}_2^n$ (not necessarily orthogonal).

$\textbf{Claim 1.}$ $\exists i \in [k],$ s.t. $\langle x, e_i \rangle = 1$. Otherwise, for $\forall y \in C$ the inner product $\langle x, y \rangle = \sum_{i=1}^k \beta_i \langle x, e_i \rangle = 0,$ where $y = \sum_{i=1}^k\beta_ie_i$ is the basis decomposition of $y$ (all operations are modulo 2). Hence, the assumption that $x \notin C^{\perp}$ is incorrect.

Without loss of generality, $\langle x, e_1\rangle = \ldots = \langle x, e_s\rangle = 1$, $\langle x, e_{s+1}\rangle = \ldots = \langle x, e_k\rangle = 0$ for some $s \in [k]$.

Then $\langle x, y\rangle = \sum_{i=1}^s\beta_i$. The number of sequences $\{\beta_i\}_{i=1}^s$ of an even weight is the same as the number of odd-weight sequences, and it's equal to $2^{s-1}$, which concludes the proof.


Reduction of 3-SAT to Vertex Cover? Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$?

I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of having two "gadgets": the 2-node variable gadgets and 3-node clause gadgets.

I also understand the formula $k = variables + 2\:clauses$ as the minimum number of nodes required to cover all the edges. What I don't understand is how this setup proves that if there exists a $k\text-covering$, then the boolean expression in CNF is satisfiable.

Examples with expressions that are satisfiable and not satisfiable would be helpful. Also, once the $3SAT$ problem is converted to a $k\text-covering$, does it provide a means to identify which value (true or false) should be assigned to each variable so as to satisfy the boolean expression?

To show that Vertex Cover and 3SAT is "equivalent", you have to show
that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step.

Assuming you are familiar with how the reduction is done, (if not ,refer to the document).

Since you only asked about
how this setup proves that if there exists a k-covering, then the boolean expression in CNF is satisfiable.

This is effectively the "only if" part to the proof that the two are "equivalent". So all you need to do is to show that as long as there is a k Vertex Cover for the graph constructed in the reduction, you have a satisfying solution to 3SAT.

The proof:

Since there is a k Vertex Cover, then one and only one node of each of the variable gadgets must be in the Vertex Cover. (This is because k = variables+2clauses,if you don't choose one of the variable in the variable gadget then the middle connection in the gadget is not incident, and if you choose in one gadget, you will end up with variables + 1 + 2 clauses, we'll show that you must choose 2 nodes in each clause gadget in the next sentence.)

We must have 2 nodes in each clause gadget because if we don't, then one of the connection in the clause gadget is not incident.

So set the variable corresponding to the one node that is selected in each of the variable gadgets to TRUE.

Now we have two scenarios for each of the clause gadgets:

One: A gadget can have a connection with a variable Node that is set to TRUE. In this case the gadget has a variable which is TRUE, the gadget is therefore satisfied.

Two: A gadget does not have a connection with a variable Node set to True. Then it must select all 3 of its Nodes to make the edges all incident. And that is not possible when we have a k Vertex Cover.

Hope this answers your question :))


Louvain algorithm: self-loop weight is double? In the 2nd phase of the Louvain algorithm, self-loops are given by the sum of all the intra-community weights. I'm wondering from their own figure, why all of the self-loops seem to have 2w weights, rather than w. Note in the blue community for instance: 2 intra-community edges, self loop has weight 4.

Every edge has the same weight, which it contributes to each endpoint. When both endpoints are in the same cluster, the edge counts twice towards that cluster. Then they are in different clusters, the edge counts once towards each of the two clusters. So each edge has the same overall contribution.