Longest path in an undirected tree with only one traversal

We perform a depth-first search in post order and aggregate results on the way,
that is we solve the problem recursively.

For every node $v$ with children $u_1,\dots,u_k$ (in the search tree) there are
two cases:

The longest path in $T_v$ lies in one of the subtrees $T_{u_1},\dots,T_{u_k}$.
The longest path in $T_v$ contains $v$.

In the second case, we have to combine the one or two longest paths from $v$ into
one of the subtrees; these are certainly those to the deepest leaves. The length
of the path is then $H_{(k)} + H_{(k-1)} + 2$ if $k>1$, or $H_{(k)}+1$ if $k=1$,
with $H = \{ h(T_{u_i}) \mid i=1,\dots,k\}$ the multi set of subtree heights¹.

In pseudo code, the algorithm looks like this:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

$A_{(k)}$ is the $k$-smallest value in $A$ (order statistic).


Cache memory temporal locality and spatial locality principles

It loads data in "blocks". Hence, data close together will be loaded together - space locality
It gets rid only of the most unused data - temporal locality


Let's start with an integer program for vertex cover:
\begin{align}
&\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\
& x_v \in \{0,1\} &&\text{for every } v \in V
\end{align}
Here $V$ is the set of vertices and $E$ is the set of edges.
The optimal solution for this integer program is the minimum vertex cover in the graph. We denote its value by OPT.
Unfortunately integer programming is NP-hard to solve exactly, so we consider a linear programming relaxation, replacing the constraint $x_v \in \{0,1\}$ by the constraint $x_v \in [0,1]$:
\begin{align}
&\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\
& 0 \leq x_v \leq 1 &&\text{for every } v \in V
\end{align}
Every feasible solution of the original integer program is also a feasible solution of the linear programming relaxation. In other words, the linear program is minimizing over a set of solutions which contains the set of solutions to the integer program. Therefore the optimal value of the linear program is bounded from above by OPT.
More abstractly, if $A \subseteq B$ then
$$
\min_{x \in B} \phi(x) \leq \min_{x \in A} \phi(x).
$$
In our case, $A$ is the set of solutions to the integer program, $B$ is the set of solutions of the linear program, and $\phi$ is the objective function $\sum_{v \in V} x_v$.


What is a list of "reasonable but undecidable" theorems?

Godel's First Incompleteness Theorem: "Any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete."
"A certain amount of elementary arithmetic" can be considered as reasonable properties of... well all math.
Incompleteness can also be seen as a form of undecidability.


State of the art time complexity for getting (tree) descendants by type/attribute

For the static case, if you have a solution with $O(1)$ running time, I can't see any opportunity for improvement in the running time, as you can't do better than $O(1)$.  So I'll focus on the dynamic case, i.e., where we want to support insertions and deletions.

One strategy is to augment the tree, so that for each type $T$ each node $x$ contains:

A count of the number of descendants of type $T$
A pointer to each immediate type-$T$ descendant of $x$ (i.e., a link to each $z$ such that $z$ has type $T$, $z$ is a descendant of $x$, and there is no descendant $y$ of $x$ such that $y$ has type $T$ and $z$ is a descendant of $y$)
A pointer to the immediate type-$T$ parent of $x$ (i.e., the lowest ancestor of $x$ that has type $T$)

This allows 'count' queries to run in essentially $O(1)$ time: given a node $x$, you can count the number of type-$T$ descendants of $x$ in $O(1)$ time.  (Simply find $x$'s immediate type-$T$ parent, then use the field in the parent that stores the count of number of type-$T$ descendants.)

Also, 'enumerate' queries run in $O(k)$ time: given a node $x$, you can enumerate all type-$T$ descendants of $x$ in $O(k)$ time, where $k$ is the number of type-$T$ descendants of $x$.  (Simply find $x$'s immediate type-$T$ parent, then traverse the fields that list the immediate type-$T$ descendants, recursively.)

The running time to insert a new leaf at depth $d$ in $O(d)$ time, since you only need to update the fields in the nodes along the path from that leaf to the root.  If the tree is balanced, this is $O(\log n)$ time.

The running time to delete a leaf at depth $d$ is the same, for the same reasons.

This is the best I know how to do.  I don't know if it is possible to do better.


The concepts of asymptotic running time analysis and Landau notation already provide a way to compare the asymptotic running time of two algorithms, as long as (a) you are happy to ignore constant factors, (b) only care about asymptotics (limiting behavior as problem size gets large), and (c) you want to evaluate them according to their worst-case running time.  It sounds like you are happy with (a), (b), and (c), so you should be happy with existing tools.  They do tell you how much more efficient one algorithm is than the other.  You just might not have appreciated yet how to fully use these mathematical tools and concepts, which is understandable.

In particular, if we can express the running time of algorithm A as $\Theta(f(n))$ and the running time of algorithm B as $\Theta(g(n))$, we already know how to compare them.  We know that the ratio of their running time is $\Theta(f(n)/g(n))$.  In particular:

If $f(n)/g(n) = \Theta(1)$, we know that their asymptotic worst-case running times are equivalent.
If $f(n)/g(n) = o(1)$ (i.e., $f(n) = o(g(n))$), we know that A is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(f(n)/g(n))$.
If $f(n)/g(n) = \Omega(1)$ (i.e., $f(n) = \Omega(g(n))$, or equivalently, $g(n) = o(f(n))$), we know that B is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(g(n)/f(n))$.

You might want to read How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?,  Sorting functions by asymptotic growth,  How do O and Ω relate to worst and best case?, and Justification for neglecting constants in Big O.  That will give you some essential background to help you understand how these concepts fit in.

(I'm simplifying a bit, and casting this at the level that it sounds like you're ready to absorb.  Once you understand the basics, read Are the functions always asymptotically comparable? if you want to read some more precise statements -- but beware that right now this might just cause more confusion than it's worth.)


Do the two huffman trees have the same corpus?

Your inequalities are based on the assumption that the left child of an inner node is not bigger than the right child. However, this does not hold. (Note that the condition is violated for the root of the right tree.)

Instead we do know that whenever the algorith chose to unite two nodes, there were no nodes with smaller weight present. For the left tree we find:

$a_1$ ad $a_2$ were joined before $a_5$ was joined to another node, so
$$a_1 \leq a_5\text{ and }a_2\leq a_5.$$
We do not know, if $a_1$ and $a_2$ were joined before or after $a_3$ and $a_4$, but in case the latter pair was joined first, we find $a_1 \leq a_3+a_4$ and $a_2\leq a_3+a_4$. If the former pair was joined first, we find $a_1\leq a_3$, $a_2\leq a_3$, $a_1\leq a_4$, and $a_2 \leq a_4$. These inequalities imply those of the first case, so we can conclude that $$a_1 \leq a_3+a_4 \text{ and } a_2\leq a_3+a_4.$$

Can you go on from here?


L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?

Try to implement it in constant space to see what goes wrong. You need to be able to count up to $k$, which takes $O(\log k)$ space.

More formally, consider the language
$$L = \{a\ast b : a,b \in \{0,1\}^k, b=a+1\}.$$
This is not a regular language, and so cannot be decided in constant space.


Single tape TM that converts numbers from binary notation to unary

As you have said, there are $2^n-1$ total "decrements". Notice that at the $k$'th decrement, you "waste" $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$:
$\sum_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$


Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former.  In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other variant of FF in preference to EK).

The above does not imply that EK is faster than a particular (say, DFS-based) variant of FF on any particular instance.

BFS and DFS have the same runtime, but DFS only promises to find a path from source to sink in the residual graph -- not necessarily a shortest possible such path, which BFS does promise.  It's possible to show that no modification to the residual graph ever reduces the distance from the source to any vertex; with this, and the fact that BFS always finds a shortest path, it's possible to show that after finding at most $|V||E|$ augmenting paths, no source-to-sink path remains in the residual graph.  This page gives a full proof -- I've only skimmed it, but note that when it says that "That is, [the distance from the source to all other nodes] is always increasing", it in fact means (or should mean) that this never decreases -- that is, the distance from the source to a particular node can stay the same after an augmentation, or it can be larger, but it can never be smaller.


Combine the following IP Addresses into a single block

An ip address has two parts: the address and the netmask.

The address is just a 32-bit binary number. E.g. yours:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000

However, these addresses are very precise, and without any further information point to exactly one address. But we want to be more general, and be able to talk about a whole group of addresses. That is a block, and what the netmask is for.

When I use a netmask of /n, it means 'only look at the first n bits of this address, those are meaningful, the rest can be anything'. Think of it like this, the address we give is full, but then we strike out the most specific parts that can be anything:

  United States,  Middleberge, Otter Lane 5322

In your case, the first 26 or 25 bits matter, so we strike through the last 6 or 7 bits:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000

But we still need to combine the blocks. Note that the top two lines have the exact same start, but then one ends in a 0 followed by anything, and the other in a 1 followed by anything. But since that exhaustively covers everything, we can just extend the 'anything' part one up to combine them:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.10000000

Here we can do the exact same:

00010000.00011011.00011000.00000000

We can now convert our IP address back to decimal, giving 16.27.24.0. The netmask is 32 - 8 = 24 (because we strike out 8 binary digits). So the full IP address + netmask is 16.27.24.0/24.


In what sense a type of parser is less power than the other?

Assuming that by "CLR" you mean "canonical LR", then you have the order wrong; the correct containment order is

$LR(0) < SLR(1) < LALR(1) < CLR(1)$

A possibly more meaningful way of saying that is that if we define $G_X$ to be the set of context-free grammars which can be parsed with algorithm $X$, then

$G_{LR(0)} \subset G_{SLR(1)} \subset G_{LALR(1)} \subset G_{CLR(1)}$

That containment sequence does not apply to languages. If we say that $L_X$ is the set of languages for which there is a grammar in $G_X$, then we will find that

$L_{LR(0)} \subset L_{SLR(1)} \subseteq L_{LALR(1)} \subseteq L_{CLR(1)}$

For all of these parsing algorithms, the fact that the algorithm cannot produce a conflict-free parsing table for a particular grammar means that that grammar cannot be parsed with that algorithm. The word "accept" is quite confusing here: an algorithm produces a parser from a grammar (or fails to do so); the parser then accepts those sentences which are in the grammar's language. If an algorithm produces a parser for a grammar, then that parser will be 100% precise: it will accept all sentences in that grammar's language and reject all other sentences.

Furthermore, all these LR parsers have linear time and space complexity (in the size of the sentence to be recognised), and all of them reject invalid inputs at the earliest possible point, which is as soon as the prefix of the input cannot be the prefix of any sentence in the language. It is true that some of the parsers may perform extra reduce actions before reporting failure, but that is not considered in the definition of a grammar's "power".


How are Operating systems involved in execution of programs?

At one level you have hardware: A computer with a CPU, RAM, hard drive, graphics card, monitor, keyboard and so on.

Then on the lowest level of the operating system you have code that can talk to these devices. That code allows the operating system to read or write data from the hard drive, determine the location of the mouse, and so on.

At a higher level of the operating system, the OS has code to assign address space to processes, start processes and kill them, allow these processes indirect access to the hardware.

Above that, it is just code. You have a mouse reporting it's location, you have graphics hardware that can display a cursor, so someone wrote code that keeps track of the mouse location and displays the cursor at the point corresponding to the mouse location. And then someone wrote code to display icons. And more and more and more code on top of that. And that's all, really.


Is the exact cover problem NP-hard when there is a restriction on the size?

Yes, it is still NP-hard.  In fact, it remains hard even if you replace $\log_2 n$ with the constant 3.  This follows by reduction from 3-dimensional perfect matching.

3-dimensional perfect matching is the following problem:

Input: disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$

Question: does there exist a perfect matching?  In other words, does there exist $S \subseteq T$ such that $|S|=|X|$ and the union of elements of $S$ is an exact cover for $X \cup Y \cup Z$?

From this statement of the problem, it is clear that 3-dimensional perfect matching is a special case of your problem: take $U=X \cup Y \cup Z$ and $C = \{\{x,y,z\} : (x,y,z) \in T\}$.

In contrast, if the size of every set is at most 2, then it can be solved in polynomial time, using algorithms for finding a perfect matching in an undirected graph.


Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation.  Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.


Average number of full nodes in a binary search tree

As the both the formula itself is given $f(n) = \frac{n-2}{3}$ as well as the inductive structure $f(n) = \frac{n-2}{n} + \frac1n \sum_{i=0}^{n-1}{\dots}$, it seems you are requested to show the formula by (mathematical) induction. Hint (2) only explains the formula.

Inductively you apply the formula for $f(k), k<n$ in the recursive expression and conclude that it also holds for $f(n)$. I can do that, but run into trouble. The formulas do not match.

Summing $f(i) + f(n-i-1)$ is easy, as it is equal to $\frac{i-2}3 + \frac{n-i-1-2}3 = \frac{n-5}3$, so the $i$'s cancel. Plugging it into the recursion yields $\frac{n-2}{n} + \frac nn \frac{n-5}3$ which is not the expected $\frac{n-2}{3}$.

edit: The first values of $f$ however are special. $f(0) = f(1) = 0$, where the formule $\frac {n-2}3$ predicts $\frac {-2}3$ and $\frac {-1}3$ respectively.  Thus we have to correct this within the summation, twice as it occurs in both $i=0,1$ and $i=n-1,n$, and add $\frac 2n$. Amazingly, that works.

Part (3) just expects you to know what is the relation between the numbers of full nodes and leaves in a binary tree.


Why is SAT so important in theoretical computer science?

SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of SAT.
SAT is also amenable to surprisingly successful heuristic algorithms, implemented by software known as SAT solvers. As a result, there is a lot of practical interest into formulating problems efficiently as instances of SAT.
SAT also shows up in fine-grained complexity, one of whose main assumptions is the strong exponential time hypothesis, which is a conjecture on the computational complexity of SAT.


Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$, which is why we use the $O(1)$ notation.

You don't get to choose the constant – rather you are only given that such a constant exists.


Your statement for directed graphs is not true. Your graph in the OP is a counterexample. However, for undirected graphs it is true since if $(a,b)$ is a cross edge then the depth-difference between the vertices is at most 1, i.e. $depth(a) = depth(b)$ or $depth(a)+1 = depth(b)$. Using this fact, which is proved below, you can prove your statement.

Assume that at some point you have the following queue configuration:
$$v_1, v_2,\dots, v_k,a,\dots, u_1,\dots u_m \text{ (leftmost leaves first)}$$
where $v_i$s and $a$ have the depth $d$ and $u_i$s have the depth greater than $d$. Since $(a,b)$ is a cross edge, $a$ and $b$ belong to different ancestral trees, i.e., one of the $v_i$s is an ancestor of $b$ i.e, $b$ must be discovered before we reach $a$. If their depth values are equal then $b$ has already been reached (discovered) and so they must be at the same time in the queue. Otherwise, their depth values differ by 1 and so $b$'s ancestor (parent) must be one of the $v_i$, say $v'$. This $v'$ is popped and extended before we reach $a$ and since $b$ is a descendant of $v'$, $b$ is pushed into the queue before $a$ is removed.

Thus in both cases $a$ and $b$ appear in the queue for some time during the execution of BFS.

Claim: In a breadth-first search of an undirected graph for each cross edge $(a,b)$ $$0 \leq depth(b)-depth(a) \leq 1$$
Proof: Assume that $depth(b)-depth(a) > 1$. Then $depth(b)$ is at least $depth(a) + 2$. But $(a,b) \in E$ (a cross-edge) and hence $depth(b) = depth(a)+1$, a contradiction (see the following figure).


Would a sparse NP-Complete language imply L = NP?

Your claim [4] is wrong - the issue is with the term "$X$-complete" for a complexity class $X$.

Stricly speaking, barring specific convention the phrase "$X$-completeness" doesn't pin down a single notion: we also need to specify the reducibility notion involved. For example, Cai/Sivakumar look at P-completeness with respect to logspace and NC many-one reductions, while "NP-complete" refers to polynomial-time many-one reductions. Changing the reducibility notion changes the completeness (and hardness) notion - for a silly example, everything in P is NP-complete with respect to exponential-time Turing reductions.

So the implication "P=NP implies P-complete=NP-complete" is a non-sequitur, since the implicit reducibility notions are different. P=NP does imply (say) "P-complete w/r/t logspace reductions = NP-complete w/r/t logspace reductions," but that's a completely different thing.


How to find nearest number in a sequence that is strictly smaller than given number

Converting my comment into an answer.

Here is an algorithm for the interpretation that you are looking for $l_j$ such that $l_j \lt l_i$ and $|i-j|$ is the smallest.

  Traverse left to right, push stuff on stack. If new element to be pushed >= top
  element. If new element < top element keep popping the stack till top
  < new element. For the elements popped, the new element is the $l_j$


Proof that $(L_{all})^C$ is not recursively enumerable

Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input.

Here is a computable reduction from HALT to $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in L_{all}$. This shows that $L_{all}$ cannot be co-r.e. Indeed, if $L_{all}$ were co-r.e. then HALT would be co-r.e. Since HALT is also known to be r.e., it would be recursive; but we know that HALT is not recursive.

Here is a computable reduction from HALT to the complement of $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which on input $n$ runs $T$ on the empty input for $n$ steps; if $T$ halted, $T'$ enters an infinite loop, and otherwise $T'$ halts. You can check that $T \in \mathrm{HALT}$ iff $T' \notin L_{all}$. This shows that $L_{all}$ cannot be r.e. Indeed, if $L_{all}$ were r.e. then HALT would be co-r.e., and we get a contradiction like in the preceding paragraph.

In fact, $L_{all}$ is $\Pi_2$-complete; it is sometimes known as TOT or TOTAL. Thus $L_{all}$ is stronger than HALT, which is only $\Sigma_1$-complete.


Self-balancing binary search tree optimized for insertion

I realized, considering that memory and processing constraints are negligible in my situation, that it is trivial to produce a new, perfectly balanced tree from an in-order traversal of the unbalanced tree, where perfectly balanced means that the max depth of a leaf node is at most one more than the minimum depth of a leaf node.

For that matter, a tree isn't even necessary.  Using a binary search over an ordered array to determine where to insert each new element is more efficient than using a binary search tree at all.  Given that my input set is a fixed 58 items, using JavaScript's Array.prototype.splice() function is more than performant enough, and makes the code trivial, as well.


Quicksort is for sorting, the algorithm you refer to is a selection algorithm known as Quick Select.

Since you can only pick as pivot a number that is in the list case #1 never happens.
Worst case is that you continually pick a number that partitions the list into 2 lists: A list with just one element and a list with $n-1$ elements, if this is the case in each iteration you only rule out a single element.

So first iteration you do $n$ operations, second iteration $n-1$ operations, third one
 $n-2$ operations, ... last iteration 1 operation.

Which its the sum of the first $n$ natural numbers:

$1+2+3+... +(n-2)+(n-1)+ n = n(n-1)/2$ operations = $O(n^2)$


Data structure with init $O(n)$ and interval max $O(\log n)$

Assume for simplicity that $n$ is a power of 2. Construct a complete binary tree in which the vertices at depth $k$ correspond to subarrays of length $n/2^k$, and contain as auxiliary information the maximum element of the subarray.

This data structure can be initialized in $O(n)$, and it supports your type of range queries in $O(\log n)$. You can also update the data structure by modifying arbitrarily a single element of the array in $O(\log n)$.

Details left to you.


When a trained RNN is tested, is the number of time-steps same for
  every input?

Typically, yes. If an input is too short, it can be padded. If an input is too long, it can encoded in some way to reduce length. A good discussion of these methods can be found here.

The reason I said typically is because an RNN is producing an output after each time step t. That is for each time step t there is an input t and output t. In classification tasks, we usually only want the last output. But in generative tasks we would want the output at each time t. It is certainly possible for the length to differ between inputs.

So like most things in machine learning the answer is, it depends.


Minimum weighted arithmetic mean partion?

Suppose first that we fix the sizes of the sets $|A_i| = n_i$ in non-decreasing order $n_1 \leq \cdots \leq n_k$. In that case, if we arrange the numbers $a_i$ in non-decreasing order, then an optimal choice is
$$ A_1 = \{a_n,\ldots,a_{n-n_1+1}\}, A_2 = \{a_{n-n_1},\ldots,a_{n-n_1-n_2+1}\}, \ldots, A_k = \{a_{n_k},\ldots,a_1\}. $$
The reason is that given any solution where $a_i \in A_I$ and $a_j \in A_J$, switching $a_i$ and $a_j$ will result in a total change of
$$ -n_Ia_i-n_Ja_j + n_Ja_i+n_Ia_j = (n_I-n_J) (a_j-a_i),$$
so the switch is beneficial (or harmless) as long as $n_I \leq n_J$ and $a_j \geq a_i$.

In view of this, there is always an optimal solution in which $A_1,\ldots,A_k$ is a partition of $a_1,\ldots,a_n$ into intervals. This suggests a dynamic programming algorithm. For each $\ell \leq k$ and $t \leq m \leq n$, we compute
$$ \min_{A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t} \sum_{i=1}^\ell |A_i| c(A_i), \quad \text{where $A_\ell = \{a_{t+1},\ldots,a_m\}$}. $$
Here $A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t$ means that the left-hand side is a partition of the right-hand side into intervals. I am assuming that sets could be empty; the algorithm can be modified to ensure that sets are not empty (just make sure $\ell \leq t < m$).


graph isomorphism completeness of class X and not-X

Apparently, with graphs of class $X$ and not-$X$ you mean graphs that fulfill a property $X$ and those that don't. It is common that say a graph problem has a different complexity when the input graph is restricted to a certain class of graphs. In this sense, graph isomorphism is no different. As for your question, it is easy to come up with plenty of (even large) classes of graphs. For example, consider graphs that have an even number of vertices, and those that don't. Both are GI-complete, so at least in general, there are no implications.

If this is not satisfying, you need to address what you mean by "non-trivial graphs", but I don't think this would turn out to be too fruitful.


Reductions among two problems related to walks of length $k$

Since $k$ is a constant you can solve $B$ in polynomial-time by exploring all $O(n^{k-1})$ paths of length $k$ starting from $s$ and ending in $t$, as you point out.
At this point the reduction is trivial:
If the answer to an instance $\langle G, s, t\rangle$ of $B$ is "yes" then the corresponding instance of $A$ is $G$.
If the answer to the instance  $\langle G, s, t \rangle$  is "no", then the instance of $A$ is the empty graph.


Machine learning - PCA and KNN on rgb images are too slow

One possible approach is to train a classifier that, given a table, outputs its shape; train a classifier that, given a table, outputs its texture; train a classifier that, given a table, outputs its colour; and so on for each of the feature values you care about.  Thus, given a table, you can compute a feature vector that has the value of each of these attributes.  You can then define a distance metric on these feature vectors (e.g., some kind of weighted L2 distance), which will let you measure how similar two tables are by comparing their feature vectors.

Once you've done this, there's a straightforward way to find the most similar tables.  Use the classifiers to find the feature vectors for all the tables.  Then, use k-nearest neighbors to find the k most similar images to each given image.  If the number of features is not too large, this should be efficient, as you are now doing k-NN in a low-dimensional space.  For instance, you can use k-d trees or other data structures for nearest neighbor search to speed up the search.  These data structures are a lot more efficient when the number of dimensions is small.

I expect this should be plenty efficient for your needs.  Handling 4000 table images should be no problem.

There are other possible approaches as well, but the above is the first thing I'd try.


How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?

We can write the constraints on the $d_{uv}$ as follows:
$$ d_{uv} \geq z_u - z_v, z_v - z_u $$
$$ d_{sv} \geq 1 - z_v $$
$$ d_{ut} \geq z_u $$
Since we are minimizing $\sum d_{uv} c_{uv}$ and $c_{uv} > 0$, this means that we want to minimize each individual $d_{uv}$, and so in fact
$$ d_{uv} = |z_u - z_v| $$
$$ d_{sv} = 1 - z_v $$
$$ d_{ut} = z_u $$
If we put $z_s = 1$ and $z_t = 0$, then the formula
$$ d_{uv} = |z_u - z_v| $$
holds for all $u,v$.
We can think of $z_v$ as specifying the position of the vertices on the real line. We are penalized $c_{uv} |z_u - z_v|$ for each edge $(u,v)$. Furthermore, $z_s = 1$ and $z_t = 0$. From this description, it is evident that there is no reason to put any vertex beyond the interval $[0,1]$.
If $z_v \in \{0,1\}$ for all $v$, then we can think of the $z_v$ as specifying a cut: one side (which includes $s$) consists of all $v$ such that $z_v = 1$, and the other side (which includes $t$) consists of all $v$ such that $z_v = 0$. If we allow general $z_v \in [0,1]$, then we can think of it as a "fractional cut".
It is natural to ask whether fractional cuts are better than cuts. It turns out that they aren't. The simplest way to see this (same proof as in Luca Trevisan's lecture notes) is to construct the cut randomly: choose a threshold uniformly at random in $[0,1]$, and use it to partition the vertices into those left of the threshold and those right of the threshold. The probability that two vertices $u,v$ are in different sides of the cut is exactly $|z_u - z_v|$, and so the expected weight of the cut is $\sum_{uv} c_{uv} |z_u - z_v|$.
This is a very simple example of the metric method in the design of algorithms.


Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?

Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think):
$$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$
Now  $f(n) = c\cdot g(n) + O(g(n))$ means, that  $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have
$$f(n) = c\cdot g(n) + \phi (n) \leqslant c\cdot g(n) + C\cdot g (n)=(c+C)g (n)$$
so $f \in O(g)$ and your claim is correct.
The general rule can be worded as follows:
If $f \in O(g)$, then $f+O(g)=O(g)$


Is there a complexity class “BQP without error”?

Yes, it's called EQP (exact quantum polynomial) and is listed in the complexity zoo:

  The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQP_K. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.


Are Epsilon-NFAs a way to make designing NFAs easier?

An epsilon-NFA is a mathematical formalization.  Mathematics doesn't have a purpose, per se.

Why do we use this formalization?  Sometimes, because it is convenient.  Yes, it sometimes makes designing certain NFAs less onerous, and that's useful.  So, yes, your suggested rationale/motivation is reasonable.  It also makes some algorithms (e.g., Thompson's construction) simpler and easier to understand.  It's also intellectually interesting to know what power epsilon-transitions add.  There are multiple reasons why one might study this concept; different people might have different reasons for studying it at any point in time.  See also Why is non-determinism useful concept?.

What is "happening" when we execute an epsilon-transition?  Well, a NFA is not a physically implementable machine; it is an abstract concept.  So it is hard to map it to physical, real-world intuitions.  See also Why NFA is called Non-deterministic?.


Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations

A good way to think about these equations is to imagine them as sets over valid words. Say I have an alphabet $\Sigma = \{a, b\}$, then the rule
$$
A \leftarrow A a \mid b
$$

says that there's some set $A$ that is isomorphic to the set $(A * \{a\}) \cup \{b\}$. Here the $*$ operation is the product/concatenation operation lifted over sets, that is
$$
\{a, b, c\} * \{d, e, f\} = \{ad, ae, af, bd, be, bf, cd, ce, cf\}
$$

Going back to our grammar rule, it is basically declaring the existence of a set $A$ of words that satisfies the equation
$$
A = (A * \{a\}) \cup \{b\}.
$$

Now, there's a huge class of sets of words that satisfies this equation. For example, the set $A_\bot = \{b, ba, baa, baaa, baaaa, \dots\}$ is a valid solution since a $b$ or appending any element of $A_\bot$ with another $a$ will result in a word that is already in $A_\bot$. However, you should check that
$$
A_{bb} = \{b, bb, ba, bba, baa, bbaa, baaa, bbaaa, \dots\}
$$
is also a valid solution to this equation. In particular, $b$ is already in $A_{bb}$, and for any element $ba^k$ or $bba^k$ in $A_{bb}$, its concatenation with $a$ results in $ba^{k+1}$ and $bba^{k+1}$, which are also already in $A_{bb}$. Therefore, $A_{bb}$ is also a valid fixed point.

In fact, for any given ground set of words $S = \{w_1, w_2, w_3, \dots\}$, we can construct a closure $A_S$ which contains every word in $S$ and similarly satisfies the above equation. In particular, the closure operator is the same isomorphism:

\begin{align*}
A_S^{k + 1} &= (A_S^k * \{a\}) \cup \{b\} \\
A_S &= \bigcup_k^\infty A_S^k
\end{align*}

So now we get to the real question. If there are an infinite supply of solutions for this equation, then what good is it as a characterization of some grammar? Well, intuitively, we hope to just characterize those words that are generated from this rule "from scratch". In effect, we wish to treat these rules as free objects. That is, we care about the case where the underlying generator $S = \{\}$. Let
$$
A(S) = (S * \{a\}) \cup \{b\}
$$
then we want
$$
A_* = \bigcup_k A^{(k)}(\{\})
$$
to be the set generated by our grammar rule, where $A^{(k)} = A(A(\stackrel{k}{\dots} A(\cdot)))$.

This then gives some intuition of what we mean by the "least solution." $A(S)$ is monotone in the sense that $S \subseteq S' \implies A(S) \subseteq A(S')$; in fact, this holds over all grammar rules. Since the least element over the class of possible sets that $S$ can take (ordered on set inclusion) is the empty set, then effectively the "freely generated" language that we desire also turns out to be the smallest (ordered on set inclusion) fixed point, that is, $A(\{\}) \subseteq A(S')$ for any set $S'$.

In general, you'll see a lot of these "smallest solution" clauses all around the landscape of computer science. For example, any recursive program is the smallest solution to some program equation; any constructable inductive datatype is the smallest solution to some inductive datatype equation; any valid program semantic is the smallest solution to some logical equation; etc. It turns out that these classes of topological closures corresponds elegantly to a notion of finiteness. For example, the set of all finitary words $\Sigma^*$ is itself a least fixed-point. Since computations themselves can be seen as some enumeration process of finite objects, the analogy holds quite naturally; least fixed-points typically gives some assurance of some form of computability.

In conclusion, if you see the phrase "least solution" or "the least fix-point," it often means that the problem concerns finite objects that are freely-generated in the sense that only things that can be derived "from scratch" are considered.


Why are weights of Neural Networks initialized with random numbers?

The basic intuition behind initializing weight layers into small (and different) values is just so that the bias of the system is broken and weight values can move along and away and apart to different values.

More concretely, you'ld probably want your initial weights to be distinct and have "a small gap" between them, this 'gap' expands out as you go along and forces the weights to be a bit larger at every iteration, and this helps the network to converge faster, i.e. the learning process speeds up.

If you would instead have all your weights to some constant, each weight will be updated at a very slow (~fixed) rate, and this won't help much, specially if the initial values are 'very far' from the final values.

Hope that helps,
Have fun learning :)


Hint: Take a SAT instance $C$ with $k$ clauses and introduce $3k$ new variables $\top^i_1, \top^i_2, \top^i_3$ for $i \leq k$ and construct $k$ new clauses $c^\top_i = \{ \top^i_1,\top^i_1,\top^i_3 \}$.  Let $C' = C \cup \bigcup_{i=1}^k c^\top_i$ be the input to 3SAT-WITH-MAJORITY.


Can the following O(...) expression be simplified?

Suppose that there exists a strictly positive constant $c > 0$ such that $k,n,L \geq c$; this happens for example if $k,n,L$ are all positive integers. In this case, a function is in $O(kn + k^2L + k^2nL + knL)$ iff it is in $O(k^2nL)$, where for our purposes $f(k,n,L) = O(g(k,n,L))$ (read: $f(k,n,L)$ is in $O(g(k,n,L))$) if there exists a constant $C>0$ such that for all $k,n,L$ "in range" we have $f(k,n,L) \leq C g(k,n,L)$. Here "in range" is the common domain of the functions $f,g$, such as all positive integers or all positive reals which are at least $c$, for some positive $c>0$.


Reflexive transitive closure = (zero or more) Kleene star?

(Note: I'm not 100% sure about the Alloy syntax since I never used it -- what follows is accurate on the general principles but the syntax could be slightly different)

Basically, S.*bar means starting from S and using .bar any number $n\geq 0$ of times.

Instead, S.^bar means starting from S and using .bar any positive number $n > 0$ of times.

It is immediate to see that S.^bar is equivalent to S.bar.*bar since the latter denotes zero or more steps after a first step, hence one or more steps.

If the language allows S.iden to mean "zero steps from S", and + to denote union, then we can also write S.^bar as S.(iden + ^bar) which can be read as "zero steps or (one step or more)" which is the same thing as "zero or more steps".

In the underlying theory, one can define the reflexive and transitive closure of a relation $R \in \mathcal{P}(A\times A)$ as the smallest relation $R^* \in \mathcal{P}(A\times A)$ satisfying

$$
R^* = I_A \cup R \circ R^*
$$

where $I_A$ stands for the identity relation. The existence of the smallest $R^*$ is guaranteed by the Tarski fixed point theorem (on the complete lattice of the relations). According to the Kleene fixed point theorem (and a few minor simplifications) one can also write it as
$$
R^* = \bigcup_{n\geq 0} R^n
$$
where $R^n$ denoted the self-composition of $R$ for $n$ times.


Delivery Algorithm - Find shortest paths

A max of 10-15 orders is small enough that you might be able to brute force it.  While this would exceed your execution time limit, it might be worth doing so on a small number of problems in order to compare algorithms absolutely rather than relatively.  Alternatively, you might be able to find precomputed benchmarks for this problem.

In general, I'm personally found of restricting routing problems to a Deluaney triangulation.  It's fast to calculate and has a Euclidean minimum spanning tree  (MSP) as a subset.  It won't have any route crossings (like those removed by a 2-opt).

However, the SLA constraint may work against that.  E.G. Say that the you have found an optimal TSP solution (a locally optimal solution) for W1, but it can only service k out of n orders in time.  In that case the globally optimal solution may require delaying the last (n-k) orders in W1 and going to the clostest order in W2.  There's no reason to expect this W1 to W2 switch-over arch to be in a DT over all the sites.  Furthermore, if your time windows don't overlap, there's no reason to visit W2 site during the W1 phase.

So then, I'd find a MSP for each subset of order sites (W1 & W2).  On W1, apply Christofide's algorithm to get a Hamiltonian cycle.  Find the start node, call it S1, & remove its longest arc in the cycle to get a Hamiltonian path through all of W1 - call this P1.

Next, compute the travel time & check for broken SLAs on P1.  Eject the site that yeilds the biggest time savings until all remaining SLAs on P1 are valid.

Find the clostest point in W2 to the last site in P1 - call this S2.

On W2, apply Christofide's.  Find S2 & remove its longest arc in the cycle to get a path through all of W2.

Recompute the travel time for P1 + P2 & check for broken SLAs on P2.  Eject the site that yeilds the biggest time savings until all remaining SLAs on P2 are valid.

Finally, let W3 be all the previously ejected sites. Find the clostest point in W3 to the last site in P2 - call this S3.  Find a MSP on W3, apply christofides, find the S3 & remove its longest arc in the cycle to get a path.

Solution is concatenation of P1, P2, P3, S1.  Clearly, there are cases where this won't give the optimal answer, but it should scale well & has known bounds on the sub-problems which might help in determining its overall bounds.


Is there any way that I, a CLI PHP developer, could "hook into" some kind of AI blackbox?

something which would be unbearably slow to calculate in PHP but goes super fast with the ai-blackbox.exe

I think you are massively overestimating the state-of-the-art of AI.

Any AI blackbox is implemented in some programming language. PHP is not the fastest language, but its slowness is likely to be a constant factor in any computation. So the difference between you calculating it in PHP and the black-box calculating it is mostly whether you wrote the code yourself or someone else wrote it.

A general purpose question-and-answer system is actually likely to be slower than something you write yourself, because you probably have some idea of the kinds of questions you are going to be feeding the system, and could optimize based on this.

You seem to want to phrase your questions using natural language i.e. English or another human language. Natural Language Processing is a huge open area of research, and is far from solved. There are some existing techniques for this, but they are far from perfect. Anyone who has spent a day with a Siri, Google Home or Amazon Echo sees that we are a long way from being able to properly process human language.

What kinds of questions do you want to answer? Even assuming you could fully process the input to your question, you're going to have a hard time if the range of possible solutions includes "all of human knowledge." Representing such knowledge, collecting the information, and searching it, are all areas of current research.
Most modern AI techniques are for specialized AI i.e. you train a Neural Network to perform a single task very well. So they don't really apply to what you're talking about.

They either agree with me that it's just nonsense and doesn't actually exist, or they link me to some massive manual which I'm utterly unable to comprehend.

This is because AI is hard. Even with specialized AI, it takes a lot of expert knowledge to train a neural network. Generalized AI is even harder.

Can I actually use this, today, for anything meaningful, in a simple way?

I think the closest you will get to this is the Wolfram Alpha API. This is a system that lets you put in a question, and sometimes returns an answer. It's best with math-style things, or with facts it can guess from i.e. Wikipedia. It is far from perfect, and far from the kind of generalized AI you're talking about. It's also proprietary software i.e. you can only run it on their servers and make requests to them. And it is not free after a certain number of requests.
You can test it out at https://www.wolframalpha.com/.

Or is this exclusively useful for a handful of scientists doing some very specific work and who need to "train" the AI in all kinds of ways before it can answer anything?

There is a reason there is currently a huge demand for data science and AI specialists. Currently, it takes a lot of specific work to train an AI even to perform a single task. A Neural Network is basically a graph with weighted edges, and you can automatically optimize the edge weights, but you have to figure out the graph structure yourself. There is some work into "Automated Machine Learning", which tries to guess these structures automatically, but it's very much an open problem.
Essentially, it currently takes an expert to train an algorithm to perform a single task. General question and answering is mostly out of reach, even for experts.


How does a program execute with respect to the operating system?

A initialized file means that you have comprobe that exist, or open it in some mode (write, read, r&w, etc) and create it if is not already.


Easy reduction from 3SAT to Hamiltonian path problem

The number of vertices in the well-known reduction from 3SAT to directed Hamiltonian Path(dHAMPATH) can be easily reduced to $O(n+k)$, where $n$ is the number of variables and $k$ is the number of clauses, therefore the size of the constructed graph instance is linear to the size of the original 3SAT instance.

In the original reduction, we have start vertex and end vertex, $k$ vertices for clauses, $n$ lists of length $4k$ for variables. The idea is that we don't have to construct list of length $4k$ for each variable, we can construct list according to the number that the variable appears in all the clauses. Since the total number of appearances of variables in clauses is $3k$, it is $O(n+k)$.


Weights must be initialized to random, distinct, small values.

If all the weights are initialized to zero, our optimization function (eg. gradient descent) will not work. According to a later video, it's a problem of symmetry that will happen when you initialize weights to the same value. So if you used 0.4 instead of zero, the same problem would happen.

From course material:

  When training neural networks, it is important to randomly initialize the parameters for symmetry breaking. One effective strategy for random initialization is to randomly select values for weights uniformly in the range [-x, x]. One effective strategy for choosing x is to base it on the number of units in the network. A good choice of x is x = sqrt(6) / sqrt(in + out) where in and out are the number of units in the layers adjacent to [the weights]. This range of values ensures that the parameters are kept small and makes the learning more efficient.


Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

$X_m$ and $Y_m$ are not shaded, because each of them is potentially the median of $X \cup Y$.

Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array of size $n$):

(1) $X = \{ 2, 4, 6 \}$ and $Y = \{ 3, 5, 7 \}$.

(2) $X = \{ 2, 4, 6 , 8 \}$ and $Y = \{ 3, 5, 7, 9 \}$.

I think the caption of Figure 1 is wrong: median of two sorted lists lies in the unshaded region.


How can recursion tree split a problem into smaller pieces that do not add up?

Here is a very simple example: binary search.
We are looking for an element $x$ inside a sorted array $A$. We compare $x$ to the element at the middle $m$ of $A$. If $m = x$, we're done. If $m > x$, we recurse on the left half, and if $m > x$, we recurse on the right half. The recurrence for the worst-case running time is
$$ T(n) = T(n/2) + O(1), $$
whose solution is $T(n) = O(\log n)$.


Difference between beta reduction and substitution

The $\beta$ reduction is defined by using capture-avoidng substitution. That is,

$$
  (\lambda x. M)N \longrightarrow_\beta M[x \mapsto N]
$$

So it's the definition. Under the $\beta$-equivalence, $(\lambda x. M)N \equiv_\beta M[x \mapsto N]$, but syntactically, $(\lambda x. M)N \neq M[x \mapsto N]$.

Note that substitution is a meta-operation on $\lambda$-calculus terms (normally).
A $\lambda$-calculus term $M$ is whether a variable $x$,
a lambda abstraction $(\lambda x. M')$, or an application $M_1 M_2$.
That's it.
There is no substitution.
Substitution is a map on $\lambda$-calculus terms.
Therefore, for example, a term $({+}~x~y)[x \mapsto z]$ is syntactically equal to $({+}~z~y)$.
There is no reduction.
In contrast to this, $(\lambda x. {+}~x~y)~z$ is not syntactically equal to $({+}~z~y)$, although it can be reduced to $({+}~x~y)$.

Also, $(\lambda x. {+}~x~1)~2$ is different from $(\lambda x. {+}~x~1)[x \mapsto 2]$. The latter is equal to $(\lambda x. {+}~x~1)$.


Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?

The accepted answer is incorrect. I've taken the same course, and option 1 is correct. They didn't say why, but I have the following argument.
Quoting Wikipedia:

polynomial time: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $ T(n) = O(n^k) $ for some positive constant $ k $.
exponential time: An algorithm is said to be exponential time, if $ T(n) $ is upper bounded by $ 2^{poly(n)} $, where $ poly(n) $ is some polynomial in $ n $. More formally, an algorithm is exponential time if $ T(n) $ is bounded by $ O(2^{n^k}) $ for some constant $ k $.

We don't know $ P \neq NP $, so option 2 can't be ruled out.
For all we know, the running time required to solve NP-complete problems could be anywhere between polynomial and exponential (note that $ n^{\log n} $ is more than polynomial but less than exponential). Thus, options 3 and 4 can't be ruled out.
That only leaves option 1. The claim in option 1 is incorrect because if there's a polynomial-time algorithm for any NP-complete problem X, then every other NP problem has a polynomial-time algorithm by reduction to X.


With $n = |w|$ the length of $w$, step 2 is repeated exactly $n+1$ times.

But they assume implicitly that $n$ is the length of the input (which is canonical in complexity theory), i.e. $|\langle w \rangle|$ with an unspecified encoding $\langle.\rangle$ of strings.
(Why they insist to introduce that encoding here, I don't know.)

The $O$ (which should be a $\Theta$) comes from that encoding as well. While there are exactly $|w| + 1$ ways to cut $w$ in two parts, we don't know the exact figure in terms of $|\langle w \rangle|$.

They forget to mention their assumption that that encoding is reasonable in a certain way, i.e. $|\langle w \rangle| \in \Theta(|w|)$ for all $w$.


optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

Algorithm in the question
Although it is correct, it is rather slow. In the function Omega(k), b goes from 1 to the largest prime divisor of $k$, which is of order $\dfrac {\pi^2n} {12\,\log n}$ on average for $1 \le k \le n$ as mentioned by the On-Line Encyclopedia of Integer Sequences. So, the running time of computing $g(n)$ is $O(\dfrac {n^2}{\log n})$. It takes more than an hour to compute $g(10^6)$ on my computer.
A Faster Algorithm
Instead of computing directly the number of prime factors of each number $k$, we can add 1 to $\Omega(k)$ whenever $k$ is a multiple of a power of $p$ for all primes $p$. For example, since 72 is a multiple of 2, 4, 8, 3 and 9 but no other powers of primes, we will get
$$\Omega(72)=(1+1+1)+(1+1)=5.$$
Here is the improved algorithm.
def g(n):
    # Omega[k], for k >= 1, is the total number of prime factors
    # of k, honoring their multiplicity. Omega[0]=0 is ignored.
    Omega = [0] * (n+1)
    for k in range(2, n+1):
        if Omega[k] == 0:  # i is a prime.
            power = k
            while power <= n:
                m = power
                while m <= n:
                    Omega[m] += 1
                    m += power
                power *= k

    return sum(map(lambda x: (x % 2 * 2 - 1) * x, Omega))

On average, each $O(1)$ number of operations will yield 1 prime factor. Thus, the running time of the algorithm above is
$$O(1)\cdot O\left(\sum_{k=1}^n\Omega(k)\right)=O(n\log\log n),$$
where $\log\log n$ is the average of $\Omega(i)$ for $1\le i\le n$, as mentioned in Wikipedia. Since $\log\log n$ grows very slowly, this algorithm can be considered as an almost linear algorithm.
It took less than 1 second to run g(10^6) on my computer.


Visual programming tools, why don’t they work with the AST directly?

Many of these tools do work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages and editors like it (Scratch, Pencil Code/Droplet, Snap!, GP, Tiled Grace, and so on).

Those systems don't show a traditional vertex-and-edge graph representation, for reasons explained elsewhere (space, and also interaction difficulty), but they are directly representing a tree. One node, or block, is a child of another if it is directly, physically inside the parent.

I built one of these systems (Tiled Grace, paper, paper). I can assure you, it is very much working with the AST directly: what you see on the screen is an exact representation of the syntax tree, as nested DOM elements (so, a tree!).

This is the AST of some code. The root is a method call node "for ... do". That node has some children, starting with "_ .. _", which itself has two children, a "1" node and a "10" node. What comes up on screen is exactly what the compiler backend spits out in the middle of the process - that's fundamentally how the system works.

If you like, you can think of it as a standard tree layout with the edges pointing out of the screen towards you (and occluded by the block in front of them), but nesting is as valid a way of showing a tree as a vertex diagram.

It will also "do the round trip from source to node-graph and then back again to source when needed". In fact, you can see that happen when you click "Code View" at the bottom. If you modify the text, it'll be re-parsed and the resulting tree rendered for you to edit again, and if you modify the blocks, the same thing happens with the source.

Pencil Code does essentially the same thing with, at this point, a better interface. The blocks it uses are a graphical view of the CoffeeScript AST. So do the other block- or tile-based systems, by and large, although some of them don't make the nesting aspect quite as clear in the visual representation, and many don't have an actual textual language behind them so the "syntax tree" can be a bit illusive, but the principle is there.

What you're missing, then, is that these systems really are working directly with the abstract syntax tree. What you see and manipulate is a space-efficient rendering of a tree, in many cases literally the AST a compiler or parser produces.


Finding a class of graphs for which vertex coloring is NP-hard

This PDF defines a graph for which solving a 3-SAT formula is equivalent to determining if the graph is 3-colorable. Finding the vertex coloring of these graphs would solve the 3-SAT problem, so the vertex coloring problem on these graphs is at least as hard as an NP-complete problem. Therefore, solving the vertex coloring problem on these graphs is NP-hard.


Empirical Risk and True Risk - Generalization Error Proof

This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David.
Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such that the difference between the empirical error $L_S(A(S))$ of the hypothesis $A(S)$ produced by $A$ given the finite sample set $S$ and the true error $L_P(A(S))$ is large, i.e. the hypothesis $A(S)$ performs well on the training data but does not generalize.
So to prove the statement, let $m \geq 0$ and $\varepsilon > 0$ and consider a binary classification scenario over the domain set $\mathbb N$.
We define a learner $A$ as follows: Given a set $S \subset \mathbb N \times \{0, 1\}$ of $m$ samples, $A$ outputs the hypothesis
$$ h_S(x) =
\begin{cases}
y, & \text{if } (x, y) \in S \\
0, & \text{otherwise}.
\end{cases} $$
Clearly, the empirical error of the hypothesis produced by $A$ will be $0$ for any training set $S$ as we defined the output of $A$ specifically to be correct for all samples in $S$.
It remains to construct a probability distribution over $\mathbb N$ such that the true error of the hypothesis $A(S)$ is at least $1 - \varepsilon$ for any choice of $S$.
Recall that the true error of a hypothesis $h$ w.r.t. a distribution $P$ is defined as
$$L_P(h) = \Pr_{(x, y) \sim P}[h(x) \neq y].$$
We now fix the labels in our distribution to always be 1 to ensure that $A(S)$ errs on all inputs not contained in the sample set $S$.
Hence the task now reduces to assigning probabilities to each $n \in \mathbb N$ such that the combined probability of any $m$ points forming such a sample set is bounded by $\varepsilon$.
To achieve this, consider the distribution $P \colon \mathbb N \to [0, 1]$ with
$$
P(n) =
\begin{cases}
\varepsilon / m, & \text{if } n \leq m - 1 \\
\varepsilon / (m \cdot 2^{n - m + 1}), & \text{otherwise}.
\end{cases}
$$
If we consider any sample set $S \subset \mathbb N$ of size $m$, we find that
$$ \Pr_{x \sim P}[x \in S] =  \sum_{n \in S} P(n) \leq \sum_{n \in S} \frac{\varepsilon}{m} = \varepsilon.$$
Hence, using the learner $A$ on a sample set $S$ of size $m$ drawn using the distribution $P$ yields a hypothesis $h_S$ with
$$
\begin{align}
L_P(A(S))
&= \Pr_{x \sim P}[h_S(x) \neq 1] \\
&= \Pr_{x \sim P}[x \notin S] \\
&= 1 - \Pr_{x \sim P}[x \in S] \\
&\geq 1 - \varepsilon.
\end{align}
$$
To finish everything off, recall that we defined $A$ such that $L_S(A(S) = 0$, yielding
$$|L_S(A(S) - L_P(A(S))| \geq 1 - \varepsilon.$$


Nth number in a infinite sequence of numbers

The idea here is as follows:

The first 9 digits are 123456789.
The next 90 pairs of digits are (10)(11)...(99).
The following 900 triplets of digits are (100)(101)...(999).
And so on.

Given an index $n$, you calculate which group you are (singles, pairs, triplets, ...), then which tuple you belong to and which digit inside the tuple. For example, if $n=28$ then this is digit no. 19 in the second group, which is the first digit of the 10th tuple 19, that is, 1.


Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

You can find a $k$-th order statistic of an array using a selection algorithm in $\Theta(n)$ time. It means that you can also find the $k$ least (and the $k$ greatest) elements of an array in $\Theta(n)$ time by first finding the $k$-th ordering statistic and then comparing it with each element of an array.
So in your case we can find $n / 2$ (median) and $n/2 + n / \log(n)$ order statistics and then find all suitable elements by scanning an array and comparing its elements with both statistics.


Could an NP-hard problem have a mechanical or physical solution method?

No.

Unless $P=NP$, it's unlikely that any mechanical process can solve an $NP$-hard problem efficiently. Given a mechanical approach to solving a problem, we could run a physics simulation on a computer to get the same result.

Of course this depends on being able to simulate what happens in the real world efficiently. In order for "mechanical polynomial time" to be stronger than "polynomial time" you'd need to find some physical process that can not be simulated efficiently. One possible candidate would be quantum mechanics but that doesn't seem to be what you're asking about (and it is speculated that even quantum computing doesn't allow one to solve $NP$-hard problems efficiently).


The algorithm you described isn't polynomial time because it has to consider every possible subset of customers (they are $2^m$ of these).

Solution

This problem is NP-hard because the vertex cover problem can be reduced to it.

https://en.wikipedia.org/wiki/Vertex_cover#Computational_problem

HINT: To do the reduction, consider how you would model $A$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.


Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

I suppose you are looking for an asymptotic bound. Notice that the recursion depth is $\log^* n$, that is how often do I have to apply the logarithm recursively to get below 2. Also, the function is increasing. Using these two facts, you can plug in the recursion once and then you  see that you have at most $\log^*$ summands, each of them at most $\log^2 n$ and then the additional $n$. This sum is dominated by $n$.

$$
\begin{align}
T(n)&=\log(n) T(\log n)+n=\log n \log\log n \;T(\log\log n)+\log^2(n)+n \\
&\le \log^*n\log^2n+n=O(n)
\end{align}
$$

Clearly $T(n)\ge n$ and thus $T(n)=\Theta(n)$.


Whats the point of caching if the minimum single clock cycle time is the prorogation delay of the slowest component (fetching from DRAM)?

You are right that the clock speed is determined by the slowest stage. But on most architectures it is not true that fetching(or any kind of memory access in fact) takes one cycle. This is an illusion provided by the CPU to makes things manageable. In practice if your CPU tries to fetch and the operation cannot be completed in one cycle then it will stall(on pipelined processor it will introduce a "bubble") until it gets the memory content. Thus if your memory takes 100 cycles to read, then the CPU will stall 100 times in the fetching stage. The same applies to read(and to some extent write) stages.

This is why caching is so important: by caching the processor can reduce the fetch/read/write delay and maintain this illusion that it takes one cycle when really it does not. Example latencies for memory read are:

L1 cache: 1 cycle
L2 cache: 10 cycles
DRAM: 100 cycles

Do not take those figures literally, it is very architecture dependent. But you can see that without caching, your CPU would take 100 cycles to fetch each instruction, this is obviously unacceptable.


The minimal DFA for $L$ contains 25 states, as can easily be shown using Myhill–Nerode theory.

Indeed, consider the 25 words $\{a^ib^j : 0 \leq i,j < 5\}$. I will show that when a DFA reads any two different words from this list, it cannot end up in the same state. To show this, for any two different words $x,y$ from the list, I will give a word $z$ such that $xz \in L$ but $yz \notin L$.

Let $x = a^i b^j$ and $y = a^k b^\ell$ be two different words from the list. Since $x \neq y$, either $i \neq k$ or $j \neq \ell$ (or both). Assume without loss of generality that $i \neq k$. Take $z = a^{5-i} b^{5-j}$. Then $|xz|_a = |xz|_b = 5$, and so $xz \in L$. In contrast, $|yz|_a = 5-i+k \not\equiv 0 \pmod{5}$, since $i \not\equiv k \pmod{5}$ by assumption, showing that $yz \notin L$.


If P=NP, which two languages are NOT NP-complete?

For $L$ to be $NP$-complete, every problem in $NP$ must be reducible to an instance of $L$ in polynomial time. If $P=NP$, you can solve any potential problem in $NP$ directly within polynomial time, and then just branch and output an instance known to be either in or not in $L$ (in constant time), to prove that $L$ is $NP$-complete. However, two languages lack the required pair of instances - the empty language fails to have an instance that accepts, and its complement fails to have an instance that rejects. If at least one problem in $NP$ has some instances that accept and some instances that reject, then you can't reduce it to either of these two languages, and therefore they are not $NP$-complete. To wrap up the proof, you'd need to give an example of such a problem and the instances, which should be fairly trivial.


Approximation Algorithm for Independet Set Problem: Any Explanation Please?

In general, the maximal degree in a graph can be as large as $n-1$. Therefore on general graphs, the greedy algorithm is only guaranteed to give a $1/n$ approximation, which you can also obtain by returning an arbitrary vertex.

What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.


Why is addition as fast as bit-wise operations in modern processors?

Addition is fast because CPU designers have put in the circuitry needed to make it fast.  It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it.  See https://en.wikipedia.org/wiki/Adder_(electronics).

Both can be made fast enough to execute within a single CPU cycle.  They're not equally fast -- addition requires more gates and more latency than a bitwise operation -- but it's fast enough that a processor can do it in one clock cycle.  There is a per-instruction latency overhead for the instruction decoding and control logic, and the latency for that is significantly larger than the latency to do a bitwise operation, so the difference between the two gets swamped by that overhead.  AProgrammer's answer and Paul92's answer explain those effects well.


If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints:
$x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$
which is $n$ constraints.

Let $m=\lceil \log_2 k\rceil$ and $x_i = b_{im}, b_{i(m-1)}, \dots, b_{i1}$, where $m$ is the high bit and $1$ is the low bit.
Define $d_{ij} = b_{ij}\textrm{ XOR }b_{(i+1)j}$.
Then, the constraint $x_1 < x_2$ is representable as:
$$
\bigvee_{i=1}^{m} \left[\left(\bigwedge_{j=i+1}^m d_{1j}'\right)\left(b_{2i}b_{1i}'\right)\right] = 1
$$
basically the i-th clause encodes that the top $m-i$ bits are identical and the $i$-th bit is $1$ in $x_2$ and $0$ in $x_1$.

Abusing notation slightly (taking the constants in the representation of $k$ for $x_{n+1}$), a similar technique can be used for $x_n \leq k$, where one would add an extra clause $\bigwedge_i d_{ni}'$ for handling the equality.

The above formula is a DNF. To get to CNF, one would simple encode $\textrm{NOT}(x_2 \leq x_1)$.

Finally, if it's needed to represent $x_1 \geq 1$ one can do this by adding a CNF clause $\bigvee_i b_{1i}$.

Note that the complexity here is really good. $O(nm)$ clauses, and $O(nm^2)$ literals. In particular if $n$ and $k$ are large this is much better than for other techniques (but it isn't applicable in other settings where other constraints could change the ordering).


Computing MOD_4 function using MOD_2, OR, AND, NOT gates

Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we would be able to solve our problem.

How do we "halve" the number of ones? The idea is to consider the running sums
$$ y_i = x_1 \oplus \cdots \oplus x_i. $$
Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.


Check if a given polynomial is primitive

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{P(x)}$.

You can also just use a CAS (computer algebra software). For example, using the free software Sage you can do

F.<x> = GF(2)[]
(x^8+x^6+x^5+x+1).is_primitive()

For more on the relevant mathematics, see the Wikipedia article.


How to prove the language of contractible strings is context-free but not regular?

For $i \ge 0$ consider the word $x_i = (ab)^i$.
For $0 \le i < j$, $(ba)^i$  is a distinguishing extension for $x_i$ and $x_j$. Indeed $x_i(ba)^i \in L$ but $x_j(ba)^i \not\in L$. By the Myhill–Nerode theorem $L$ is not regular.
Given a non-empty word $w \in L$,
$w$ can be written as $\alpha_1 \alpha_2 \dots ... \alpha_k$ where (i) each $\alpha_i$ is a non-empty contractible string that starts and ends with the same symbol, and (ii) the first symbol of $\alpha_{i+1}$ differs from the last symbol of $\alpha_i$.
Each $\alpha_i$ starting with some symbol $x$ can be written, in turn, as
$x \beta_1 x \beta_2  \dots \beta_h x$, where $h \ge 1$, all $x$ are exactly the characters removed in a single contraction step, and all $\beta_i$ are (possibly empty) substrings that are contracted before contracting $x$. It follows that each non-empty $\beta_i$ must start and end with the unique symbol in $\{a,b\} \setminus \{x\}$.
Consider hen the following context-free grammar $G$, in which $A$ (resp $B$):
generates a contractible string starting and ending with $a$ (resp. $b$):$$
S \to \varepsilon \mid S' \mid S''\\
S' \to A \mid AB \mid ABS' \\
S'' \to B \mid BA \mid BAS'' \\
A \to aa \mid aBa \mid aA \mid aBA \\
B \to bb \mid bAb \mid bB \mid bAB
$$
The above observations imply that $L(G) \supseteq L$, while
a parse tree for $w$ (according to $G$) provides a sequence of contraction for $w$, showing that $L(G) \subseteq L$.


Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?

Using formal notations rather than words would make your life easier. Since you have a
binary encoding of  Turing Machines (TM), you should use a formal
notation for it.

For example you can give it a name, say $g$. Then an encoding $x$ of a
TM $M$ can be written $x=g(M)$, or if you want to use the common angle
bracket notation: $x=\langle_g M\rangle_g$. Note that I keep $g$ as a
subscript of the angle brackets, so that I can distinguish different
binary encodings of Turing Machines.

Now, if $g$ is a binary encoding scheme for TMs, then its composition
$h=f\circ g$ with a bijective and computable function $f$ (from binary
numbers to binary numbers) is also a binary encoding scheme for TMs,
such that (using the various possible notations) $h(M)=f(g(M))=\langle_h M\rangle_h=f(\langle_g M\rangle_g)$.

Now you can rewrite the definition of $L$ using this new binary
encoding scheme:
.$$\begin{align}
L&=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}\\
&=\{f(x)\mid \mbox{$x=\langle_g M\rangle_g$ and $M$ accepts $f(\langle_g M\rangle_g)$}\} \\
&=\{f(\langle_g M\rangle_g)\mid \mbox{$M$ accepts $f(\langle_g M\rangle_g)$}\}\\
&=\{\langle_h M\rangle_h\mid \mbox{$M$ accepts $\langle_h M\rangle_h$}\}
\end{align}$$

It is now easy to see that L is recursively enumerable, since for any
value $x$, we can test whether it is in $L$ by running the machine $M$
such that $x=\langle_h M\rangle_h$ with input $x$, which does
terminate when $x\in L$.

However, $L$ is not decidable. The proof goes by contradiction.
We first suppose that $L$ is decidable. Thus its complement $\overline
L$ is also decidable, and is recognized by a Turing machine $\overline
M$

If $\overline M$ accepts $\langle_h \overline M\rangle_h$, then
$\langle_h \overline M\rangle_h$ is in $\overline L$, the language
that $\overline M$ recognizes by definition. But this implies, by definition of
$\overline L$ that $\overline M$ does not accept $\langle_h \overline
M\rangle_h$.

But if $\overline M$ does not accept $\langle_h \overline M\rangle_h$,
then $\langle_h\overline M\rangle_h\notin L$ by definition of $L$. Thus $\langle_h\overline
M\rangle_h\in\overline L$. Hence since $\overline M$ recognizes
$\overline L$,  $\overline M$ must accept $\langle_h \overline
M\rangle_h$.

In both cases we have a contradiction. So the hypothesis that $L$ is
decidable cannot hold.


How do I follow the text of this Longest Common Sequence proof?

The two red-underlined parts of the proof is to standardize an LCS solution, that is called $T_{opt}$ therein.

The idea is to push all the $0$'s farthest possible to the right (without passing through its nearest $1$ to the right).

Consider the following two strings:

$s_1=0001000100010001$ (i.e. $n=4$ vertices)

$s_2=0001000\ 00010001000$ (where the space is for visualizing purpose only) (i.e. $u=2$, $v=4$)

A common subsequence (not necessarily longest) can be: $s=0001000 00010001$ (i.e. $u$ is omitted)

The standardization process in the proof is to actually align $s$ against $s_1$, $s_2$.

And, this MUST be standardized to be as follows:

s1= 0001 0001 0001 0001

s2= 0001 000  0001 0001000

s = 0001 000  0001 0001

Similarly, if we omit $v$, then $s=000100010001000$

And, this should be standardized as follows:

s1= 0001      0001 0001 0001

s2= 0001 000  0001 0001 000

s = 0001      0001 0001 000

Finally, we will be able to construct an $n^2+k$-long common subsequence if there exists an independent set of size $n-k$, where for each edge $\{u,v\}$, we omit at least one of them (the ones that are in the independent set) so that it is possible to align like we do above (note that each edge-string $e_j$ contains only $n-1$ symbol $1$'s). And lastly, by complementing a $k$-VC, we have an $(n-k)$-IS.


Efficiently enumerate all subsets of an ordered set

One possibility is to generate separately all subsets of size $k$ using the following recursive approach:

  A $k$-subset of $a_1,\ldots,a_n$ is either a $k$-subset of $a_2,\ldots,a_n$ or $a_1$ adjoined to a $(k-1)$-subset of $a_2,\ldots,a_n$.

Run this recursive algorithm for $k=0,\ldots,n$. If you're careful, you will get a lexicographically ordered output.


Whatever you do, your specification will turn out to have internal state reflecting the accumulator inside your object. For a class this simple, the specification won't be any simpler than the implementation. The point is that for much more complex cases the specification is simpler. Consider a dictionary, where you add data under a key and must be able to retrieve it later. Your specification can very well be the equivalent of a linear array of key/value pairs, and the search a simple linear search. Your implementation would perhaps be a scheme based on hashing or balanced binary trees. The specification is easy to reason with, you prove your implementation behaves the same as the specification, and you are set. Tomorrow you rip out the implementation, and replace it by some fancier structure, prove again that it complies with the specification. No changes elsewhere.

Specifications are essentially writing the same program again in another (hopefully easier to handle) programming language, probably foregoing any performance considerations, and reasoning that both programs do the same. The specification languages up to date have turned out much harder to use than the regular programming languages (and specifications can have bugs too...), and the proof that they behave the same isn't for the faint of heart. And if I come up with an idea of how my program should behave, and program that, it stands to reason that the specification and the final program will share the same misconceptions and missed corner cases. There have been spectacular failures of the "program verification" movement. Look at Berry's "Academic Legitimacy of the Software Engineering Discipline" (CMU/SEI-92-TR-34) for an example of a program of a couple dozen lines, written and "proved correct", then fixed and again verified for publication in academic journals by some of the maximal experts in the area several times, and which was wrong each round.


Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation >

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:
$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$
i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I think there is a small mistake here, since $n_j$ should be considered as the number of symbols of degree $j$ and not of degree $d_j$ in $\alpha$.

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

In this formula, the left side can be interpreted as "the total number of symbols", and the right side can be interpreted as "the first operator symbol plus the total number of arguments". Intuitively, those quantities are indeed equals.
If we correct the mistake, then it is somewhat easy to prove by induction:

if $\alpha$ does not contain any operator of degree $\geq 1$, then we have $\alpha = f()$, where $f$ is an operator of degree $0$ (that could be considered as a constant). We have then $n_0 = 1$, and $n_i = 0$ for any $i \geq 1$. The property $n_0 = 1 + n_2 + 2n_3 + ...$ holds;

if $\alpha = f(\alpha_1, …, \alpha_d)$ where $f$ is an operator of degree $d \geq 1$ and the $\alpha_i$ are pure words that verify the property we want to prove, then we get:

$n_k(\alpha) = \sum\limits_{i=1}^d n_k(\alpha_i)$ if $k \neq d$;
$n_d(\alpha) = 1 + \sum\limits_{i=1}^d n_d(\alpha_i)$.

Therefore we get:
$\begin{array}{rcl}
 n_0(\alpha)& = &\sum\limits_{i=1}^d n_0(\alpha_i) \\ & =& \sum\limits_{i=1}^d\left(1+\sum\limits_{k=2}^{\infty}(k-1)n_k(\alpha_i)\right)\\ & = & d + \sum\limits_{k=2}^{\infty}(k-1)\sum\limits_{i=1}^dn_k(\alpha_i) \\ & =  &d + (d-1)(n_d(\alpha) - 1) + \sum\limits_{k = 2,k\neq d}^{\infty}(k-1)n_k(\alpha)\\ & = & 1 + \sum\limits_{k = 2}^{\infty}(k-1)n_k(\alpha)\end{array}$
And that proves the formula by structural induction on pure words. Please note that the previous sums can be interverted because the infinite sum is, in fact, finite (since $n_k(\alpha_i) = 0$ for $k$ big enough).

The fact that $n_j$ is the number of symbols of degree $j$ and not of degree $d_j$ is somewhat confirmed after the statement: "since each nullary operator has positive    weight, we have $w \geq n_0$". Why? Because $\alpha$ contains $n_0$ occurrences of nullary operators, which are supposed to be of positive weights. The statement would make no sense if $n_0$ was the number of symbols of degree $d_j$ (since $w_j$ could be zero).


Emulating equal operator using multiplication

Suppose that $f,g$ were functions satisfying $f(A) g(A) = 1$ and $f(A) g(B) = 0$ if $A \neq B$. Take any $A \neq B$. Then $f(A) g(B) = 0$, and so either $f(A) = 0$ or $g(B) = 0$. If $f(A) = 0$ then $f(A) g(A) = 0$, and if $g(B) = 0$ then $f(B) g(B) = 0$. So no such functions exist.


CFG with regular expression terminals on RHS

The general answer is pretty straightforward: if you have a grammar rule of the form $S \rightarrow {\alpha}r{\beta}$, where $r$ is a regular expression over the set of nonterminals, change this production to $S \rightarrow {\alpha}S'{\beta}$, find a right-regular grammar with start symbols $S'$ generating $L(r)$ (there is an algorithm for this); and then your grammar will include all those productions as well. Repeat for every production containing a regular expression on the right-hand side.


Apparently, you are expecting the reduction between any two $\mathsf{NP}$-complete problems $X$ and $Y$ to be a one-to-one map (e.g., a bijection). The idea of a reduction, however, is irrelevant to having instances "correspond" to others. What reductions do give us is a hardness relation between problems (and not between individual instances). If $A$ and $B$ are problems and $A$ is reducible to $B$, then we expect $B$ to be harder than $A$; the idea is that, if there is an efficient algorithm which solves $B$, then we can also solve $A$ by reducing it to $B$ and running said algorithm. Completeness, then, corresponds to the notion of hardness equivalence: $A$ is reducible to $B$ and $B$ is reducible to $A$; that is, if $A$ is hard (resp., easy), then so is $B$, and vice-versa.

To give an example why we cannot generally expect reductions to be injective, surjective, or even bijective, let again $X$ to be $\mathsf{NP}$-complete and consider the problem $Z = \{ (0, x) \mid x \in X \} \cup \{ (1, y) \mid y \in \{ 0,1 \}^\ast \}$. Naturally, we can reduce $X$ to $Z$ by mapping each instance $x$ of $X$ to $(0,x)$; this does not give us a surjective map. Further, note $Z$ is also reducible to $X$: map $(0,x)$ to $x$ and $(1,y)$ to $x'$ where $x' \in X$ is a fixed (i.e., hard-coded) instance. This reduction is surjective, though not injective. As you can see, there is really no relation between what we expect from a reduction and injectivity or surjectivity.


Given a Noisy Curve, Write a Function to Output Likely Slopes

A moving window (with some reasonable window size) is probably hard to beat.  I don't know of any parameter-less solution.

Another possible approach could be to estimate the slope of the last 10% of the data, and compare this to some threshold.  (So, the 1000th data point uses the average of points 900-1000.  The 2000th data point uses the average of points 1800-2000.  And so on.)  This way, if it does flatten out, then if you continue for another 10% longer, you'll reach a point where the last 10% is all flat and the procedure will likely terminate.  This may do 10% more iterations than "necessary", but that might be acceptable given that in return you get a procedure that doesn't require a fixed window size.

However, choosing a threshold might be a bit tricky.  I'm not sure how to do that in a reasonable way.

Given a bunch of data points, you can compute a least-squares fit for the regression line through those points, and find an estimate of the slope of that line.  You can also compute a confidence interval for that slope.  This will give you a range of plausible slopes.


What to do when the information gain on decision trees is 0 for all possible splits?

You should process ALL of the possible splits and hope for information gain somewhere down the line.


What would dynamically-typed languages actually do if type enforcement was removed?

A language in which automatic type checking is not available, an operation would make assumptions about the types of its operands. On the event that these assumptions are false, the operation, not knowing anything about this, may produce nonsense results.

Assembly is such language. It has, for instance, separate addition operations for integers and floats. If you perform integer addition on floating point values you will get a result which is correct as neither integer nor float. Depending on your definition of correct.


Is the image of a total, non-decreasing function decidable?

I am assuming in my answer that $g$ is to be taken as computable, given the comments in the question. For non-computable $g$ see David's answer.

There are two answers:

There is no uniform decision procedure for membership in the image of a non-decreasing function. For suppose we had a decision procedure $P$ which would decide whether $n \in I_g$ on input $\langle\ulcorner g \urcorner, n\rangle$. (Here $\langle\ulcorner g \urcorner$ is a suitable encoding of the Turing machine that computes $g$.) Then we could implement the Halting oracle as follows. Given a Turing machine $T$ let $g$ be
$$g(n) = \begin{cases}
1 & \text{if $T$ halts in $\leq n$ steps}\\
0 & \text{if $T$ does not halt in $\leq n$ steps}\\
\end{cases}
$$
Clearly, $g$ is a monotone map and so we would have
$$\text{$T$ halts} \iff P(\langle\ulcorner g \urcorner, 1\rangle).$$
For each such $g$ its image is decidable, but non-uniformly in $g$. (This means my proof will somewhere make a non-computable step.) Consider any non-decreasing $g$. Then either $I_g$ is finite or $I_g$ is infinite (that was the non-computable step):

if $I_g$ is finite then it is recursive
if $I_g$ is infinite then we can use the usual trick: given and $n$, enumerate the values $g(0), g(1), g(2), \ldots$ and wait until they get larger than $n$, which they will as $I_g$ is infinite. Once they do, see whether $n$ has been enumerated.


Assigning one variable to another in 3 address code?

Three address code is an intermediate language used internally by (some) compilers. What is "right" depends on the specific rules that that compiler expects/enforces. Efficiency, as you state, is normally not an issue, as the intermediate language is designed for easy massaging and ultimately traslating into efficient target code.


If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?

This is a common question regarding pumping lemmas, and it is completely answered by carefully understanding the quantifiers in the lemma.
The lemma itself says the following:

For every CFL $L$, there exists a constant $p$ such that for every word $w\in L$, if $|w|>p$, then there exist words $u,v,x,y,z$ such that $w=uvxyz$, and (1) $|vxy|\le p$, (2) $|vy|\ge 1$, (3) for every $i\ge 0$, $uv^ixy^iz\in L$.

Now, the typical usage of the lemma is by contradiction, so we have a language $L$ which we suspect to be not a CFL, and we show the negation of the lemma (read this carefully, and see how we negate the formulation of the lemma):

For every constant $p$, there exists a word $w\in L$ with $|w|>p$, such that for every decomposition $w=uvxyz$, if (1) and (2) hold, then there exists $i\ge 0$ such that $uv^ixy^iz\notin L$.

As you can see, in order to apply the lemma, we can choose the word $w$, but we are given $u,v,x,y,z$. Then, we assume that cases (1) and (2) hold, and deduce that (3) doesn't hold.
It is really important to understand which elements we can choose, and which we need to be given without choice. These correspond to existential/universal quantification.


Why is universal turing machine considered with only one head?

There are two (related) answers to your question. The first answer is that the time complexity classes are traditionally defined using one-head Turing machines. For the diagonalization argument to work, we need the simulating machine to be of the same kind as the simulated machines.

The second answer is that even if you consider time complexity classes defined using $N>1$ heads, then you are going to encounter a similar problem with the universal Turing machine who only has $N$ heads but has to simulate both the original $N$ heads and to read the program. (It could be that the performance hit is not as bad for more than one head.) Making the number of heads finite but unbounded will make things even worse, since the universal Turing machine has a fixed number of heads.


Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?

Sorting is all about removing inversions.

Combsort is much faster than cock-tail sort because it does more "long range" comparisons and exchanges; exchanging two out-of-order elements that are far apart will (on average) remove (a lot more) more inversions than exchanging two that are close together.

As for the formula you quote... well, Wikipedia's wrong.  Combsort isn't that much faster.  The formula you quote is a (very) weak lower bound on the average number of comparisons (try substituting p=2.log2(n) into the formula. Combsort can't possibly require only O(1) comparisons to perform the whole sort because... it's obviously had to do about pn, before the insertion sort phase, at the end of the sort, even begins).

[I think that formula has been (mis)quoted on the Wikipedia Combsort page since something like 2008, and I don't think anyone bothered to point out, even on Wikipedia's Combsort talk page, that the paper being referenced gave it as a formula, only for a lower bound, before June 2013.]

In practice, unless you are sorting billions of records, if you use increments that are relatively prime and have a growth ratio of 1.25 or so, Combsort will require (on average) about 3*log2(n)*n comparisons (and will generally run somewhere between 2 and 3 times slower than a quicksort or a mergesort, if you are sorting, say, integers).

You are unlikely to run into Combsort's (quadratic) worst case unless you deliberately engineer an input that will cause it.


time complexity when power is involved in iteration

You are interested in several different variants. I'll show you how to estimate the running time in the first one, you do the rest. In fact, I will only estimate the number of times that the inner loop is run, which is
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil.
$$
To obtain this, you need to figure out the number of iterations in loops of the form for (x = a; x < b; x += c) (assuming $a \leq b$ and $c \geq 1$), which is a nice exercise.

Using $x \leq \lceil x \rceil < x+1$, we see that the sum above can be bounded by
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} \leq
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil <
\lfloor \sqrt{n+1} \rfloor-2 + \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i}
.
$$
Using $m = \lfloor \sqrt{n+1} \rfloor - 1$, we can evaluate the left sum as follows:
$$
\sum_{i=2}^m \frac{n-i^2}{i} = n \sum_{i=2}^m \frac{1}{i} - \sum_{i=2}^m i =
n (H_m-1) - \frac{m(m+1)}{2} + 1,
$$
where $H_m$ is the $m$th harmonic number. It is well-known that $H_m = \log m + O(1)$, and so we can estimate the sum by $\frac{1}{2}n \log n - \Theta(n)$, skipping a few steps. A similar bound holds for the right sum, since the additional term is only $\Theta(\sqrt{n})$. Altogether, we deduce that the inner loop runs $\frac{1}{2}n\log n - \Theta(n)$ many times.


Generate algorithmically all grid points inside a hypercube

Here's another way of looking at the problem: You have a lattice generated by the columns of $M$. Use the Lenstra–Lenstra–Lovász (LLL) algorithm to obtain a reduced basis of this lattice. If you replace $M$ by a new matrix formed by the output of LLL, then the columns of $M$ will still generate the same lattice, but the basis vectors will be closer to being orthogonal to one another, and the entries of $M^{-1}$ should have smaller magnitude.

From there, it would also help to bound each component of $v$ separately: i.e., you can bound the $i$th component $|v_i|$ by $\sum_{j=1}^d |(M^{-1})_{ij}|$. (By the way, the bound $\|v\|_\infty \leq \|M^{-1}\|$ is not correct; we need to use the sum of the elements on each row, not the maximum.)

For values of $d$ up to about 30, the LLL algorithm will finish practically instantly. Asymptotically, it takes $O(d^6)$, so it will slow down for very large $d$, but at the same time the number of points we need to check grows exponentially in $d$, so the run-time of the LLL is not really the bottleneck. On the other hand, the savings in the number of points needing to be checked can be enormous. I wrote some GAP code to generate a random regular (stochastic) matrix $M$ and compare the bounds on the components of $v$ that we obtain using the original basis, compared to the LLL-reduced basis (By the way, we do not need to assume that the matrix is regular; I made this restriction only because this was the case in your application):

d:=8;
M:=IdentityMat(d);
for i in [1..d] do
  for j in [1..d] do
    M[i][j]:=Random([-10^8..10^8]);
  od;
  M[i]:=M[i]/Sum(M[i]);
od;
L:=LLLReducedBasis(M).basis;
MM:=M^-1*1.0;
LL:=L^-1*1.0;
for i in [1..d] do
  for j in [1..d] do
    MM[i][j] := MM[i][j]*SignFloat(MM[i][j]);
    LL[i][j] := LL[i][j]*SignFloat(LL[i][j]);
  od;
od;

Print("Bounds for original basis: ");
ones:=[1..d]*0+1;
v:=MM*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

Print("Bounds for LLL basis: ");
v:=LL*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

The following output (based on the default random seed, with $d=8$) is not atypical:

Bounds for original basis: 9 23 24 4 23 16 23 4
(258370076349 points to check)
Bounds for LLL basis: 3 3 2 2 3 4 2 3
(2701125 points to check)

Edit: This problem is a special case of the general problem of enumerating lattice points in convex polytopes, which it turns out is a well-studied problem, and there are more efficient algorithms than the one described above. See this this paper for a survey.


If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?

The reduction does indeed work for any non-trivial language $B$. And that's what the claim you've quoted says: "Let... $B$ be another language not equal to $\emptyset$ or $\Sigma^*$", not "... another NP language..."

So, yes, it could be arbitrarily difficult to compute $x$ and $y$. It might even be impossible to compute them. But that doesn't affect the running time of the reduction because the reduction doesn't have to compute $x$ and $y$. Rather, the person who designs the reduction has to figure out those strings once. If you think in terms of computer programs, the reduction is a program that could be arbitrarily difficult to write but, once it's been written, it runs very quickly.  In complexity theory, we don't care how difficult it is to write the program; we only care about how efficiently it runs. If the program exists, we're happy, and these programs certainly exist.

Note that it can still be possible to concretely and explictly write down the reduction, even if $B$ is uncomputable.  For example, let $B$ be the language of descriptions of Turing machines that halt on every input. This is highly uncomputable: neither it nor its complement is recursively enumerable, for example, which means that there's no algorithm that can generate all the strings in $B$, or all the strings that are not in $B$. However, we don't need all the strings: we just need two strings.  Let $M_1$ be the Turing machine that immediately enters the halt state, regardless of its input, and let $M_2$ be the Turing machine that moves its head to the right forever, regardless of its input. We have $\langle M_1\rangle\in B$ and $\rangle M_2\rangle\notin B$ so, if you cared to figure out the values of $\langle M_1\rangle$ and $\langle M_2\rangle$ as binary strings, you could explicitly write down the reduction from an polynomial-time language to $B$.


Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Hint: Use FFT to multiply the polynomials
$$ \sum_a x^{a^2 \pmod{n}}, \qquad \sum_b x^{b^3 \pmod{n}}. $$


Why selection sort is a stable sort algorithm?

Just run an example. I will use colors to distinguish multiple elements with the same value and a $\mid$ to separate the unsorted part from the sorted part.
With the input
$\mid\color{blue}{2},3,\color{red}{2},1$
the first step will swap $\color{blue}{2}$ with $1$.
$1,\mid3,\color{red}{2},\color{blue}{2}$
The order of the $2$s changed. It continues
$1,\color{red}{2},\mid3,\color{blue}{2}$
$1,\color{red}{2},\color{blue}{2},\mid3$
So, the $2$s ended in a different order as they started.
To avoid this you can insert the smallest element of the unsorted part at the beginning of the unsorted part, instead of swapping it.
So, the first step would be
$1,\mid\color{blue}{2},3,\color{red}{2}$
The next step leaves it as it is.
$1,\color{blue}{2},\mid3,\color{red}{2}$
It continues with
$1,\color{blue}{2},\color{red}{2},\mid3$
To prove that this happens in general, observe that if an element with multiplicity is about to be moved, it must be the first element (from left to right) of that value appearing in the unsorted part. So, when it gets moved to the beginning of the unsorted part it continues appearing before all the elements of the same value appearing in the unsorted part and after all the elements of the same value that could already be in the sorted part.


Ski design usaco problem alternative solution

I know, this question is really old, but I will answer it anyway. You can just pick wether you higher the lowest distance or lower the highest one. Then greedy pick the cheaper one until you have your maximum height equal or smaller than 13. In this case, you only need O(max-min-13) steps.  Hope it helps.

Just keep in mind that you need to track the former changes because of the quadratic equation.


The term 'extension' could generally be interpreted in mathematical sense1 as an enlargement of the domain of a pre-existing function.

In your case, assume Density-reachability could be described as a process $d\colon A \rightarrow B$ mapping inputs from domain $A$ to output in domain $B$. An enlargement of domain could be viewed as another map $e\colon A \rightarrow A'$ which maps where the old inputs in $A$ could be thought of as special cases in subset of $A'$ that is the image of map $e$.

An extension then could be described as any map $x\colon A' \rightarrow B$ which statisfy
$$x \circ e = d$$
There could be many such $x$, so picking extension is a choice. The above equation basically expresses that

  If I pick $a \in A$ from the old domain, translate it to the new domain as $e(a)$, then use this new tool $x$ which could be thought of as an extension of old tool $d$ along the translation $e$, then the final result must agree with just using the old tool $d$ to begin with.

or
$$x \circ e(a) = d(a)\qquad; \forall a \in A$$

The term 'canonical' simply implies that the choice of extension is the obvious, natural one of the situation.

1 At least from the perspective of category theory.


You are correct.

3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard.

So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.