Uniform sampling over non-standard simplex

According to Wikipedia the $n$-simplex is the set defined by:

$$S = \left \{ \mathbf{x} \in \mathbb{R}^n \; | \; \mathbf{x} = \sum_{i=0}^n \mathbf{u}_i\theta_i , \; \mathbf{u}_k \in \mathbb{R}^n , \;\; \theta_k > 0 \;\forall k, \;\;\sum_{i=0}^n \theta_i = 1\right \}$$

Note that the $\boldsymbol{\theta} = (\theta_0, \dots, \theta_n)^T$ is the standard $n$-simplex.

Hence in order to sample from $S$, compute a linear combination of the vertices $\mathbf{u}_k$ with the weights given by a sample of the standard simplex.

Which is the same as the following random process:

Consider the matrix of vertices $U = [\mathbf{u}_0 \; \dots \; \mathbf{u}_n]$, then a sample in $S$ is given by:

$$\boldsymbol{\theta} \sim \text{Standard-Simplex}$$
$$\mathbf{x} = U \boldsymbol{\theta}$$

Note that in your case the vertex $\mathbf{u}_k = s_k \mathbf{e}_k$.


Why is word-addressable the exception, not the rule?

Byte operations will always be important because a lot of a modern workload involves bytes. Text processing and bytecode interpretation (including emulation of other CPUs) are obvious examples, but also device drivers often need to be able to manipulate bytes efficiently.

Byte-addressed memory can be emulated with word-addressed memory and a reasonable assortment of bit manipulation instructions, however this means that you need more instructions to do the same thing, and those instructions have long chains of data dependencies between them.

RAM is reasonably cheap, but the instruction pipeline in a modern CPU is not.

Every so often, ISA designers reason that byte and short word load/store instructions aren't that important. Within two revisions, those instructions inevitably get added. This was the case with MIPS and Alpha, for example. Code density, it turns out, is quite important.

Note that this isn't true of arithmetic and logic operations. Given a sufficient number of registers (which, I might add, 32-bit x86 and earlier did not have), there doesn't seem to be any gain in implementing byte and short-word arithmetic and logic instructions. Well, for non-vectored instructions, anyway.


Let $T$ be a tree rooted at $r$ with $n > 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$.

Initially let $v=r$, then proceeds as follows:

If $\ell(v) \le \frac{2n}{3}$ then return $v$.
Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step.

Notice that, for every $v$ considered by the algorithm:

$v$ is not a leaf (hence step 2 is well-defined). If $v$ were a leaf, then the parent $w$ of $v$ (which always exists) would satisfy: $2 \le \frac{2n}{3} < \ell(w) = 2 \ell(v) = 2$, a contradiction.
$\ell(v) > \frac{n}{3}$. This is clearly true when $v=r$. For $v \neq r$, let $w$ be the parent of $v$. Since $\ell(w) > \frac{2n}{3}$, we must have $\ell(v) \ge \frac{\ell(w)}{2} > \frac{2n/3}{2} = \frac{n}{3}$.

The algorithm must terminate (at each iteration the depth of $v$ increases), therefore the returned vertex $v$ is not a leaf and satisfies both $\ell(v) > \frac{n}{3}$ (by the above property) and $\ell(v) \le \frac{2n}{3}$ (by the condition of step 1).

This proof is constructive and shows that $v$ can be found in $O(n)$ time (you can find all the values $\ell(v)$ with a postorder visit).


Single machine job scheduling to minimize weighted sum of completion time

Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w_k,w_{k+1},t_k,t_{k+1}$?


Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?

You are asking two different questions, I will answer only the first one.

  Is this language T-recognizable?

Designing first recognizer and then transforming it into a decider will not always work. A language may be undecidable but recursively enumerable.

Your approach is correct. This language is recognizable (recursively enumerable). Just systematically generate all possible sentences (for example by breadth first search algorithm) every time by checking if any derivation contains the nonterminal $A$ and the derived sentence is $x$. If the test passes then ACCEPT.

A hint for the second question: $x$ has some certain length $n$. Can derivation of all sentences of length $n$ help us decide?

Also, a decidable language is also recursively enumerable, but the converse is not always true.


What if traversal order of two of pre-order, in-order and post-order is same?

A proper proof uses the recursive definitions of the tree-orders. Here is a sketch.

For inorder the recursive definition is: in(left) - root - in(right).
For postorder we similarly have: post(left) - post(right) - root.

Look at the position of root in both orders. If we want this to be the same we need to have there are no nodes in in(right) which means the right subtree (at the root) is empty. Same for the root at other levels.


What does it mean if a generic structure is type-erased?

It means that at runtime you will not be able to see what object comes out of
the collection, as that information is removed from the lower-level code that is generated by the compiler.

In your specific instance, it would mean that at runtime an object of type AnyIterator<Element> will not be able to tell you what is the exact type of Element, unless ofcourse, you (implicitly/explicitly) cast it.


What is the relation between arithmetic circuits and straight line programs?

Straight-line programs and arithmetic circuits are two equivalent ways of describing the same computational model. A straight-line program typically has the following instructions:

Reading the input: $t_i \gets x_j$.
Initialization by constants: $t_i \gets r$ for all $r$ in the ambient field.
Addition, subtraction, multiplication, division: $t_t \gets t_j \pm t_k$ and so on.
Output: $o_i \gets t_j$.

The input and output instructions aren't really necessary. The inputs are $x_1,\ldots,x_n$ and the outputs are $o_1,\ldots,o_m$.

Exercise: show that (multiple-output) arithmetic circuits and straight-line programs are equivalent: they compute the same functions with the same size complexity (if you define size in the correct way, and allow the same sets of gates and lines).


Can we show a language is not computably enumerable by showing there is no verifier for it?

In practice, we don't usually prove just that a language is r.e. or not r.e.. If the language is r.e., we want to know whether it is recursive. If it is not r.e., we want to know what sort of Turing degree it has, not just that the Turing degree is not r.e..

For example, if $P$ is a problem with $P' \equiv_T 0'''$ then $P$ is not r.e., but that fact about the Turing jump is more informative than just knowing $P$ is not r.e.

So while, in principle, you could show that a language is not r.e. by proving there is no verifier, in practice it is more informative to prove that the language is not r.e. by showing that it computes something that no r.e. set can compute; the nature of that 'something" typically gives useful information about the problem being studied.


First Part: Let's first define the TR operator (Why do you use $TR$ and not $TC$?)
Given a formula $\phi$ with free variables $x_{i_1},\dots,x_{i_{2k}}$ than the string $\psi =TR(x_{i_1},\dots,x_{i_{2k}},\phi)(y_{i_1},\dots,x_{i_{yk}})$ is also a formula.
If you now consider an interpretation $\mathcal{I}$ than $\psi$ is true under  $\mathcal{I}$ iff $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}\in R^+$, where $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}$ is the tuple assigned to $(y_{i_1},\dots,y_{i_{2k}})$ by $\mathcal{I}$, $R$ is the binary Relation on $k$-tuples defined by $\phi$ and $^+$ the transitive closure.

As your input is (only) a structure, your Formula can't have free variables, but of course it can have constants, e.g. $\psi = TR(x_1,x_2,\phi,c_1,c_2)$ where $\phi$ is $x_1 P x_2$.

Let's assume your input ${\mathcal{G}}$ is a graph and two of it's vertices: $(V,E,v_1,v_2)$ ($E$ being a symmetric relation, not a set of pairs). Then $P^{\mathcal{G}} = E = R$ (the $R$ from above). Now $\psi^{\mathcal{G}}$ is true (i.e. your input accepted) iff $v_1$ and $v_2$ belong to the same connected component.

Second part: $t(n)$ is a function of the input size, so if your input has size $n$ the quantifier block is repeated as-is $t(n)$ times, using the same variables in each instance.

Again the example of checking whether there is a path:

$$QB(x,y) = (\forall z: \neg(x = y \vee  x E y))\\(\exists z )(\forall u)(\forall v (u = x \wedge v = z) \vee (u = z \wedge v = y)) \\(\forall x: x=u)(\forall y: y=v)$$

This block consists of three parts:

Check if there's a short path (length 0 or 1), then "quit".
Check if there is an intermediate z.
Rename the variables to recurse.

Since $(\forall z \phi)\psi$ is short for $\forall z (\phi\rightarrow\psi)$  the formula $QB(x,y)\exists x\neq x$ is only satisfiable if $\neg(x = y \vee  x E y)$ is false, i.e. there is a path of length $1$ or $0$ between $x$ and $y$.

If your input has size $n$, you only need $1+\log_2 n$ recursion levels, i.e.
$QB(x,y)^{1+\log_2 n}\exists x\neq x$ tests whether $x$ and $y$ are in the same connected component.

This example is taken from: Expressibility and parallel complexity (Immerman,1989)


When computing asymptotic time complexity, can a variable dominate over other?

First of all, if $k$ and $n$ are bounded then all complexities trivialize to $O(1)$. Hence a better assumption is something like $k = O(\log n)$. Under this assumption, you can, for example, say that $O(k + n) = O(n)$, and even $O(k + \log n) = O(\log n)$. However, you cannot say that $O(kn) = O(n)$, since it's not necessarily true! If $k = \log n$, then it's not true that $O(kn) = O(n)$. Instead, all you can say is that $O(kn) = O(n\log n)$.


Context-free grammar for"not-at-all" palindromes

Just use something like:

$
S \rightarrow a S b \mid a S c \mid b S a \mid b S c \mid c S a \mid c S b \mid a b \mid a c \mid b a \mid b c \mid c a \mid c b
$

This ensures the $i$-th symbol from the beginning is different from the $i$-th from the end.


Shortest path when allowed to reverse an edge

This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.

Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of whether or not you have already used the bonus ability. Therefore what should $V'$ be? And following on from that, what should $E'$ be?


Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

A partial answer to the second question:

In the book "Distributed Algorithms" by Nancy A. Lynch (1996) (Section 13.2  "Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables"), we have the following impossibility result:

  Theorem 13.11  There does not exist a shared memory system using read/write shared variables that implements a read-modify-write atomic object and guarantees 1-failure termination.


If $A$ is context-free then $A^*$ is regular

Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. Also we can see that $A^*\cap a^*b^*=A$. Since $a^*b^*$ is a regular expression, we do know that it is regular. Lets assume that A* is regular.
The regular languagues are closed unter intersection. Therefore $A^*\cap a^*b^*$ must be also regular(because we assume that $A^*$ is regular). This would implicate that A is regular because  $A^*\cap a^*b^*=A$. This is a contradiction because we know that A is not regular. Therefore A* cant be regular.
$q.e.d$


Given a network flow find if there's a min cut that only one of the given edges lay on it

First, compute the minimum cut value $c$ of the network.

Second, remove edge $e_1$ and increase the capacity of $e_2$ to infinity, then compute the minimum cut value $c_1$ of the new network.

Third, remove edge $e_2$ and increase the capacity of $e_1$ to infinity, then compute the minimum cut value $c_2$ of the new network.

Now you can check if $c-c_1\ge c(e_1)$ or $c-c_2\ge c(e_2)$ to see if there exists a min-cut in the initial network that contains exactly one of $e_1,e_2$.


Can the structure of a "Complete Binary Tree", be uniquely identified if only its pre-order or post-order or in-order traversals are given?

Given $n$, there is only one shape for a complete binary tree (CBT) with $n$ nodes.

For any deterministic traversal, the correspondence between a node's position in a CBT and its position during the traversal of that CBT is completely fixed. So if a deterministic traversal is given, we can reconstruct the CBT uniquely. This applies not only to any one of pre-order, post-order, or in-order traversals, it also applies to breath-first-traversal (with the left child visited before the right child), or any other deterministic traversal as mentioned by Hendrik Jan in his comment.

Here is an example. The shape above is the only shape for a CBT with 12 nodes, which are, 1 root (at depth 0), 2 nodes at depth 1, 4 nodes at depth 2 and 5 nodes at depth 3. A pre-order traversal of that CBT visits the nodes in the following order.

the root node.
the first node of depth 1.
the first node of depth 2.
the first node of depth 3.
the second node of depth 3.
the second node of depth 2.
the third node of depth 3.
the fourth node of depth 3.
the second node of depth 1.
the third node of depth 2.
the fifth node of depth 3.
the fourth node of depth 2.

Give the list above, we know the root node is the 1st-node visited, the first node of depth 1 is the 2nd-node visited, ..., the fourth node of depth 3 is the 8th-node visited and the fifth node of depth 3 is the 11th-node visited.


Deterministic construction for trapezoidal decomposition

I finally found recent paper titled "Optimal randomized incremental construction for guaranteed logarithmic planar point location" by several authors, where deterministic times are given for query and the seach structure, but expected time for preprocessing.


There are no known efficient algorithms for your problem. Consider the case where every edge has weight $1$ and there are $n$ vertices in the graph. A path from $A$ to $B$ with weight (approximately) $n-1$ is (approximately) a Hamiltonian path from $A$ to $B$ and finding Hamiltonian paths is NP-hard.


What is wrong with my LP exercise (longest path cost for a graph)

You are on a fool's errand: Longest Path is NP-hard, thus there is no LP for solving it.


Will a study of the mathematical proof of a problem [..], highlight peculiar properties of the problem which may help in designing an optimal algorithm?

Often they do. But not necessarily (unless you're a scholar of constructivism), for example when using the probabilistic method to show that a solution to said problem exists, then the proof will not help you designing any algorithm since it does not give you a construction.

  Since the program is expected to return a true response for every input, proof must be, in some way, built into the program.

That would be nice if it were the case, but often proving correctness (see formal methods) of an algorithm is rather difficult and/or a real pain. That said, there is such a thing as proof-carrying code which does exactly that, but the proofs are not given to you for free.


Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$).
To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\epsilon$ and target unitary $U$ there is some way to apply a finite number of your quantum gates to get a unitary $U'$ such that $||U - U'|| < \epsilon$.
Toffoli by itself is clearly not universal under this definition since it always takes basis states to  basis states, and thus, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.


Interpreting a proof of $2^\mathbb{N}$ being uncountable

There is no assumption in your proof that the functions involved are computable, so it would be quite stingy to interpret the proof that way merely because Agda allows you to compute with its terms.
Rather, yes how it should be interpreted depends on the model, and constructive (in the sense of just removing axioms) proofs like the one you've given enable an even wider range of models. So it applies to classical functions, because we can (I believe) interpret all the operations you used as operations on classical functions. It's just that when those operations are used to combine classical functions, they don't produce computable functions, even though the operations are in a sense computable.
When you do interpret the proof in a computable setting, what you get is actually a stronger result. The classical reading is, "the reals (or, Cantor space really for your example) are uncountable." The computable reading is, "the computable reals are computably uncountable." The latter means that we can actually compute a real that is left out of any alleged computable enumeration.
A good write up of this is here, although it applies equally well to types that aren't inductive, even though the title doesn't emphasize it. The first part of the author's thesis also gives a pretty good description of modest sets, which are a way of thinking about the 'computable operations on non-computable data' angle.
So, don't make the mistake of thinking that Agda and the like are only for reasoning about their own terms. It's an easy mistake to make coming from a computer programming background, but I think it's a mistake even there.
The reason why is your oracle example. One could imagine a model where there is an extra $^ℕ$ sequence added as a sort of brute fact (also all sequences computable from it, of course). When you ask about its bits, the computer accesses some sort of physical sensor and determines the answer based on that (and memoizes it). This bit sequence is not 'computable' in the sense of being described by some term, but as long as you haven't added axioms that depend on bit sequences being describable by terms, your proofs should hold for it. So this sort of 'open world' assumption seems to match aspects of actual computers.


How did 'Isabelle' (the theorem prover) get its name?

A little google-fu (and my own memory) tells me it was apparently named by Larry Paulson after Gerard Huet's daughter.

Gerard Huet happens to be one of the people behind the less poetically named Coq theorem prover.

Small world!


Does a proof using the well-ordering principle need a base case?

In the Wiki page,

  In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.

Pay attention to the word non-empty.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.


Can someone explain this formula for calculating Manhattan distance?

Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$.
Proof 1.
$|x|=\max(x, -x)$ for all real number $x$. So
$$\begin{aligned}
|a|+|b|
&=\max(a, -a) + \max(b, -b)\\
&=\max(a+b, a-b, -a+b, -a-b)\\
&=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\
&=\max(|a+b|, |a-b|)
\end{aligned}$$
Proof 2.
There are $2 \times 2 = 4$ cases.

$a\ge 0$

$b\gt 0$. LHS is $a+b$, RHS is $a+b$.
$b\le 0$. LHS is $a-b$, RHS is $a-b$.

$a\lt 0$

$b\gt 0$. LHS is $-a+b$, RHS is $-(a-b)$.
$b\le 0$. LHS is $-a-b$, RHS is $-(a+b)$.

One dimensionality of Manhattan-distance.
The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger. That is, $ d((x_1, y_1),(x_2, y_2))= \max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$
Proof: By definition,
$$d((x_1, y_1),(x_2, y_2))=|x_1-x_2| + |y_1-y_2|.$$
Now apply the lemma above. QED.
This answer also serves as a complement to another answer of mine.


For a given k-DNF formula, what is the size of the formula for the purpose of complexity?

The two standard conventions are number of clauses and number of literals (counted with repetition!).
The two measures are within a factor of $n$ of each other.


How to convert this recursive algorithm to an iterative form?

You have to perform a visit of the directory graph, such as a DFS. Since the graph you're dealing with is a tree, you can use a tree traversal instead, which is conceptually identical but should be easier to implement.

Just a pedantic note: you don't need the Church thesis to say that every recursive function is Turing-computable, it can be proven formally.


A loop invariant of regula falsi is that $f(a)f(b)<0$. Under the assumption that $f$ is continuous, this implies that there is a solution $x_0$ of $f(x0)=0$ inside $(a,b)$, since the eventual output $c$ is also in $(a,b)$, then for any output you have that $|c−x_0|≤|a−b|$. Therefore, you can add to the breaking condition, instead of it being abs(f(c))<tolerancia, to be abs(f(c))<tolerancia and abs(b-a)<.0001, or replace it completely by abs(b-a)<.0001.
It is true that the distance between $a$ and $b$ doesn't always go to zero. That's the price you pay for converging faster than bisection in some cases. Still, that is the only condition that you have to bound the error, if regula falsi is applied by itself, since $c$ could be approaching a root only from one side. What people do is not to apply regula falsi by itself, but to mix it, among other methods, with bisection. For example, what is done in Brent's method.


Understanding denormalized numbers in floating point representation

Although, the question is a bit old, but it may help people coming here for similar question.

A vital detail was missed out in the article that you referred to and it is that the standard chose to interpret an all 0s exponent to be equivalent to '-126' and not '-127'. One place, where I found a nice explanation (and an explicit statement about this truth) is this article. To quote from it:

  Subnormal Numbers: When all the exponent bits are 0 and the
  leading hidden bit of the siginificand is 0, then the floating point
  number is called a subnormal number. Thus, one logical representation of a subnormal number is

  (–1)s × 0.f × 2–127 (all 0s for the exponent) ,

  where f has at least one 1 (otherwise the number will be taken as
  0). However, the standard uses –126, i.e., bias +1 for the exponent
  rather than –127 which is the bias for some not so obvious reason,
  possibly because by using –126 instead of –127, the gap between
  the largest subnormal number and the smallest normalized number is smaller.

  The largest subnormal number is 0.999999988×2–126. It is close
  to the smallest normalized number 2–126.


Finding N most distinct values in set given distance metric

This problem generalizes maximum independent set and its relatives. Indeed, suppose that you could solve your problem. Then you could use the solution for deciding whether a graph contains an independent set of size $k$. Given a graph $G = (V,E)$, form a metric space by setting $d(u,v) = 1$ if $\{u,v\} \in E$ and $d(u,v) = 2$ if $\{u,v\} \notin E$. The graph contains an independent set of size $k$ iff there are $k$ points in the metric space in which the sum of distances is $k(k-1)$.


For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi_G$ such that $\chi_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have
$$
\begin{align*}
\chi_{G(1,1)} &= x \\
\chi_{G(1,2)} &= x^2 - x \\
\chi_{G(2,2)} &= x^4 - 4x^3 + 6x^2 - 3x \\
\chi_{G(1,3)} &= x^3 - 2x^2 + x \\
\chi_{G(2,3)} &= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\
\chi_{G(3,3)} &= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x
\end{align*}
$$


You must refer to the definition of a Binary Heap:

A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

It is by definition that it is never unbalanced. The maximum difference in balance of the two subtrees is 1, when the last level is partially filled with nodes only in the left subtree.


How to generate a context sensitive grammar for www

Intuitively you want to generate three intermediate symbols at a time, and allow the symbols to sort themselves. Let $S$ be the start symbol. The generation rules are:

$$S \rightarrow S A_1 A_2 A_3$$
$$S \rightarrow S B_1 B_2 B_3$$
The sorting rules are as follows: For symbols $X_i,Y_i \in \{A_1,A_2,A_3,B_1,B_2,B_3\}$ such that $j < i$ add the rule:
$$X_i Y_j \rightarrow Y_jX_i$$
In the end we have to turn the intermediate symbols into terminal symbols. Turn the start symbol into another symbol $S_1$ to end the generation phase.
$$S \rightarrow S_1$$
Push $S_1$ through the string converting symbols to terminal symbols on the way and increment the subscript when done with one word $w$.
For all $i \in \{1,2,3\}$ add the rules:
$$S_i A_i \rightarrow a S_i \; | \; a S_{i+1}$$
$$S_i B_i \rightarrow b S_i \; | \; b S_{i+1}$$
The subscript of $S$ ensures that the symbols are converted in the proper order as the subscript can not decrease. In the end remove $S_3$.
$$ S_3 \rightarrow \varepsilon $$


How to prove strict space lower bounds using crossing sequences in Turing machines?

A deterministic algorithm running in space $S$ runs in time $\exp S$. If you don't go over the entire array then you don't know the maximum number (formally speaking, consider two arrays differing in the last element, in only one of which it is the maximum). It takes time $n$ to go over the entire array. So $S = \Omega(\log n)$.


Here is a definition which describes the relationship between hard and complete:

  Given a set C of problems and a reduction R, it is natural to ask if there are problems Π ∈ C such that any problem Π′∈C,  R-reduces to Π. Such “maximal”
  problems are called in complexity theory complete problems. Let C be a class of
  problems and R be a reduction. A problem Π ∈ C is said to be C-complete (under R-reduction) if for any Π ∈′ C, Π′ ≤R Π. A C-complete problem (under reduction R) is
  then (in the sens of this reduction) a computationally hardest problem for class C. For instance, in the case of NP-completeness, NP-complete problems (under Karp-reduction) are the hardest problems of NP since if one could polynomially solve just one of them, then one would be able to solve in polynomial time any other problem in NP. Let C be a class of problems and R a reduction. A problem Π is said to be C-hard (under R-reduction)
  if for any Π ∈′ C, R Π≤ Π ′. In other words, a problem Π is C-complete if and only if Π ∈ C and Π is C-hard.

References

An Overview on Polynomial Approximation of
NP-Hard Problems
Computers and Intractability: A Guide to the Theory of NP-Completeness


How does the slow All-pairs-shortest-paths algorithm work?

Let me tell you what Bellman-Fords is actually doing because the sentence by relaxing all edges once for every vertex in the graph is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $n$ nodes it has at most $n-1$ edges.

Let's say the source node is $s$, then create a table $distance[\cdot]$ such that $distance[s] = 0$ and it is $\infty$ elsewhere. Let's solve the following dynamic programming problem, compute shortest path from $s$ to $u$ (for every $u$) that uses at at least $t$ edges.

The table we already filled is correct for the case of $t=0$. If you have this table already computed for some $t$ after relaxing all edges (in any order) it will be correct for $t+1$, since you extend all shortest path that uses $t$ edges with at least one more edge by relaxing the end of the path. Notice that you don't need to relax every edge $n$ times, but $n - 1$ times since largest path will have at most $n - 1$ edges.

The algorithm you showed is doing that for every pair of nodes in parallel. The first loop only runs $n - 2$ (instead of $n - 1$ times as I stated above) because you started with a matrix with all shortest path of length 1 already calculated (your base case is $t = 1$ instead of $t = 0$).

First loop of Extend-shortest-path is selecting the source node and following two loops are iterating through all edges (it assume the graph is complete) and relax the path that starts at $i$ ends in $j$ and use the edge $j-k$ next.

Old answer below (I miss-read the question and assumed it was asking  about Floyd-Warshall)

The key element that makes Floyd-Warshall (All-pairs-shortest-path) works is very different from Bellman-Fords key element.

Floyd-Warshall solves the following problem using dynamic programming. Calculate shortest path from every pair of vertex that use only first k vertex as intermediate hops. At the beginning it is the initial weight of existing edges and $\infty$ elsewhere (That is the base case).

Assume you have calculated such matrix for the first $k$ vertex and let's try to compute it for the first $k+1$ vertex. We should take into account paths that uses first $k$ vertex and goes through vertex $k+1$. Denote by $dp_k(u, v)$ the shortest path from $u$ to $v$ using first $k$ vertex, then it follows that the optimal path from $u$ to $v$ using $k+1$ vertex don't use this new vertex or indeed use it, so we get minimum from both values:

$$dp_{k+1}(u, v) = min(dp_k(u, v), dp(u, k) + dp(k, v))$$

In practice, the same table is reused on every step, so the algorithm only requires $O(n^2)$ spatial complexity. Temporal complexity is $O(n^3)$.


Term rewrite system for terms of lambda calculus?

I think that what you are looking for is called higher-order rewriting. There are systems in which you can define rewrite rules of the form $F\;(\lambda x.\lambda y.C\;X[x,y]) \longrightarrow X[X[t,u],v]$ for example, where $F$ and $C$ denote a function symbol and a constant symbols respectively. Note that here, $X$ denotes a higher-order variable (or meta-variable) of arity $2$. In the left-hand side (or pattern), it can be matched against any term containing only variables of $\{x,y\}$. The matched term is then used to replace the occurrences of $X$ in the right-hand side to apply the rewriting rule.

Note that the only terms that match the rewriting rule above are of the form $F\;(\lambda x.\lambda y.C\;A)$, with $FV(A) \subseteq \{x,y\}$. In this case, the variable $X$ is instantiated with $\hat{A}[-,-]$, which is a kind of context such that $A = \hat{A}[x,y]$.


Proving correctness of an exponentiation routine

A standard approach to proving correctness of a program involving a loop is to use a loop invariant. Loop invariant $P(j)$ is a statement indexed by the iteration number $j$ (or a parameter related to the iteration number) that asserts a certain mathematical relationship between some variables appearing in your code. Proving $P(j)$ is true for all $j$ is typically done by induction. You show that $P(0)$ is true, i.e., the loop invariant is true prior to the beginning of the loop. You show that $P(i)$ is true implies $P(i+1)$ is true. Then you can conclude that the statement $P(n)$ (or $P(n+1)$) must be true, which asserts the relationship between the variables of interest that is directly relevant to the correctness of the algorithm. Note that if $j$ is some parameter related to the iteration number (e.g., $j$ could be $n$ minus the iteration number), the starting point and the direction of the induction might be different. Finding the right loop invariant is usually the hardest part.

Let's find a loop invariant for your code. Note that you overwrite the variable $a$ inside the loop. This means that I cannot use $a$ in the loop invariant to refer to the original input, but I'd like to. Therefore I introduce a new letter $\alpha$ to refer to the value of $a$ that is passed to the function, i.e., the first input. The rest of the variables are exactly as in your code. Our loop invariant $P(i)$ will be indexed by the variable $i$, which is related to the iteration number, but starts with $n$ and decreases to $0$ similar to what I wrote about above. Define the following loop invariant:
$$P(i) \text{ is true if and only if } x*a^i == \alpha^n$$
Clearly, at the beginning you have $x=1$,  $a=\alpha$, and $i = n$, so $P(n)$ is true. I leave proving the inductive step to you (note you will be proving $P(n)$ is true implies $P(\lfloor n/2 \rfloor)$ is true, so this induction skips over lots of values, but it's okay - why?). When the algorithm terminates you have $P(0)$, which asserts $x*a^0 = \alpha^n$, i.e., $x = \alpha^n$, which is what you needed to prove.


Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion?

Given your very strict interpretation of limited memory size, limiting
also the size of integers, one consequence is that it is not possible
to play encoding games with integers (such as Gödel enumerations or
encodings).

Another consequence is that you cannot have a way of retrieving the
address of a memory location in order to make pointers. The reason is
that unbounded recursion implies that memory addresses will have
unbounded size (which is a bit inconsistent on the implementation
side, but I guess I have to ignore it). If there was an instruction to
retrieve the address of a variable, the space needed to store this
address could well exceed all of the memory available for a given
recursive call. Hence there is no hope of manipulating addresses.

Hence, each recursive call can only access a finite amount of
information, say $n$ bits, which may be seen also a one of $2^n$
symbols. There is as much information, i.e. one of those symbols,
memorized for each of the previous calls, but not accessible on the
recursion stack.

Of course a little bit of information is passed as parameter at each
recursive call, and some is returned when it terminates.

So all this pretty well describes a pushdown automaton.

Hence all you can do is recognize or generate context-free languages,
or some equivalent computation. You are pretty far from Turing
completeness.

But if your model allowed storing pointers to local variables, then,
even without Gödel encodings in integers, you could have Turing
completeness.


Your third question provides a hint as to why $s(n) \neq n$,
where $n$ is a node and $s(n)$ is the state of $n$.
Different nodes may contain the same state
but different parents,
and the path of a node may contain the same state multiple times
if it contains a cycle.
Theoretically,
you could define $path(n) = n$.
Practically,
it is useful to define $n$ as a record or class
containing useful data about $n$,
which brings us to:

You can store $parent(n)$ in your data structure for $n$
to find the parent of node $w$ in $\mathcal{O}(1)$.
There is no guarantee that $parent(n) \in O$ if $n \in O$.
We remove a node from $O$
and add its children
when it is expanded
in Algorithm 1.
In Algorithm 2,
we add $parent(w)$ to $O$
if it is not already there,
while removing $w$.

In terms of correctness,
you typically don't have to worry about cycles.
As long as the step cost from one state to another is always greater than $0$,
which is almost always the case in practice,
each cycle increases $f(n)$,
making nodes without cycles more favorable.
In terms of performance,
exploring cycles is a waste of time.
In regular A* search
you can detect and remove nodes with cycles
by either looking in the path of a node
or maintaining a set of explored states.
It has been a while since I worked on SMA*+,
but I think I tried to add cycle detection to SMA*+
but ran into an issue.
That could be a good area for future research .

The SMA*+ code is part of a search library I was working on.
It needs cleaning up
before I would consider publishing it,
but I'll post the node code here:
class _SMAStarPlusNode(Node):
    """Implements comparison for heapq."""
    def __init__(self, node, f_cost):
        # Copy attributes from node
        self.__dict__ = node.__dict__

        # Add SMA*+ attributes
        self.f_cost = f_cost
        self.num_successors = 0
        self.child_fs = {}
        self.open = True # Track whether in open list, to avoid scanning entire list

    def __lt__(self, other):
        return (self.f_cost, -self.depth) < (other.f_cost, -other.depth)
    def __le__(self, other):
        return (self.f_cost, -self.depth) <= (other.f_cost, -other.depth)
    def __gt__(self, other):
        return (self.f_cost, -self.depth) > (other.f_cost, -other.depth)
    def __ge__(self, other):
        return (self.f_cost, -self.depth) >= (other.f_cost, -other.depth)

class Node(object):
    """A node in a search tree.

    This class is very minimal, utilizing lazy evaluation for most attributes.
    Since thousands of instances of this class may exist at a time, every attribute
    adds greatly to the memory requirements of the program.
    """

    def __init__(self, parent, state):
        self.parent = parent
        self.state = state

        # Lazily evaluated attributes (added when needed):
        # _path_cost - added in Problem.path_cost
        # _depth
        # _path

    @property
    def depth(self):
        """Return the depth of this node."""

        # Lazily evaluate depth
        try:
            return self._depth
        except AttributeError:
            return self._make_depth()

    def _make_depth(self):
        try:
            # Non root have 1 more depth than their parent
            _depth = self.parent.depth + 1
        except AttributeError:
            # Root node has depth of 0
            _depth = 0

        # Cache and return
        self._depth = _depth
        return _depth

    @property
    def path(self):
        """Return the path to this node.

        Returns:
            tuple; a tuple of states.
        """

        # Lazy evaluation
        try:
            return self._path
        except AttributeError:
            return self._make_path()

    def _make_path(self):
        try:
            # Add current node to path to parent node
            _path = self.parent.path + (self.state,)
        except AttributeError:
            _path = (self.state,)

        # Add to cache
        self._path = _path
        return _path

class Problem(object):
    ...

    def path_cost(self, node):
        """Return the path cost to a given node.

        This method belongs to Problem instead of Node because Node does
        not store Problem (to minimize memory usage).
        """

        # Lazily evalute path cost
        try:
            return node._path_cost
        except AttributeError:
            if node.parent is None:
                _path_cost = 0.0
            else:
                _path_cost = (self.path_cost(node.parent) +
                              self.step_cost(node.parent.state, node.state))

            # Cache
            node._path_cost = _path_cost
            return _path_cost

I removed some code that only existed
to work around Python recursion limitations
while evaluating lazy attributes.
It was big and messy
and hopefully isn't an issue with the latest Python,
but be aware if you copy this code verbatim.


To answer your first question: SLDNF resolution employs negation as failure to deal with negation.

So from ←$\neg$off_ground(a) we derive ⧠ by trying to derive ←off_ground(a) and failing (i.e. deriving FF).
This is done in the upper tree on the right hand side.


Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

Hint for showing 2-wise independence: Given $x_1,x_2$ and $v_1,v_2$, write the desired equations in a different way:
$$
b = v_1 - Ax_1, \\
A(x_2-x_1) = v_2 - v_1.
$$

Regarding 3-wise independence: I could be missing something, but it seems that the family is 3-wise independent.

Hint for refuting 4-wise independence: Take $x_3 = x_1 + x_2$ and $x_4 = 0$.


How likely is for a pseudorandom number generator to generate a long sequence of similar numbers?

Given the same internal state, a pseudorandom number generator (PRNG) must produce the same output.  PRNGs have a period: if you run one long enough, it will start repeating the same sequence.  (For good PRNGs, the period is long enough that you don't have to worry about it.)  For very simple PRNGs such as a simple linear congruent generator of the form

new number = old number $\times$ constant $+$ another constant

the state is just the previous value.  In that case, it's impossible to generate the same number twice in a row unless the constants are poorly chosen and the PRNG gets stuck in a short loop.  (This has been known to happen, and you don't want to use such a PRNG!)  However, you will sometimes generate numbers that are similar (not the same) in various respects.  The tests that vonbrand's answer mentioned are designed to verify that such similarities occur with relative frequencies that are close to what should be found if each number had equal probability.

The most common version of a Mersenne Twister (MT) has a 624$\times$32-bit internal state.  If the MT is being used to generate 32-bit numbers, it uses up 32 bits of its state each time it outputs a number, and when all 624 internal state words have been used, the MT generates a new 624-word state from its old state.  (The number that is output is not the same as the state word that's used; it's a function of the state word, though.)  I suppose an MT could theoretically sometimes output the same number in two successive calls on the MT, although I am not certain that that is possible.  I think that would require that two successive words in the generated 624-word state were identical (unless it happened because you seeded the MT with a bad state that included the same number multiple times).  I don't know whether this is possible; I suspect that it is.  But it should be very, very, very rare in the sense that the relative frequency of successive duplicates across the entire period of MT should be small.

For 32-bit numbers, ideally, the relative frequency of choosing the same number twice in a row should be $1/2^{32} \times 1/2^{32} = 2^{-64}$.  That would be very rare.  On the other hand, the period of the widely-used version of MT, versions of MT19937, is $2^{19937}-1$. This is the number of successive pairs that could, theoretically, contain duplicates, and $2^{-64} \times 2^{19937}-1 = 2^{19873}$ is a large number.  However, any use of MT will only make use of a small fraction of the period.  At this point, if I wanted to know how common or rare duplicates are, I would look at the test in TestU01 or another test suite that checks the frequency of duplicates.  I wouldn't test the entire period, though, unless I had a lot of computing power and was patient.  I don't know whether it's possible to assess the frequency of duplicates analytically from the design of MT19937.

I listed some other relevant resources in this answer and said more about Mersenne Twisters in this answer.


Can Reduction for Undecidability/Decidability Problems Go Both Ways?

When proving decidability of a new problem, you reduce the new problem
(i.e. a problem with unknown solution) to an old one (used as
subroutine) with a known solution, so that the techniques used to
solve the old one can be used to solve the new one.

But, when proving undecidability, you have to do the opposite. You
reduce the old problem, known to be undecidable, to the new problem
(used as subroutine), in such a way that, if the new problem has a
decision procedure, its use as a subroutine provides a decision procedure to the old
problem, known not to have any. Hence the new problem cannot have a
solution, and is undecidable.

In your example, you should have tried to show that if you have a
decision for your new problem, that you can use as subroutine, then
you ave a decision for the halting problem, which is not possible.

So proofs go both ways only in the sense that the contrapositive of a statement goes the other way. Decidability goes one way, and undecidability goes the other way.

However, it you can do the reduction both ways at the same time (either both for decidability or both for undecidability), then you have proved that the two problems are strictly equivalent, and that any solution for one is a solution for the other. When it goes only one way, this establishes that one problem is harder than the other (letting you work out which is which).

I guess that is about all I can say about the "direction"of the proof.


If there's algorithm which returns true if Hamiltonian cycle exists in polynomial time then an algorithm to find the cycle in such time also exists?

Input: A graph G = (V, E) for which the checker algorithm is true.

if you remove an edge $e\in E$ from The graph and run the algorithm then if it returns false the removed edge must be part of every hamiltonian cycle in the graph.

If the result is true then we can remove the edge and remove another edge we haven't checked yet and run the algorithm again.

Eventually the graph will only contain a hamiltonian cycle. in O(e) applications of the algorithm.


Streaming algorithm for counting triangles in a graph

Let $(u,v,w)$ be a particular triangle in the stream, and suppose that the edge $(u,v)$ appears first. The probability that we chose $(u,v)$ in the first step is $1/m$. The probability that we chose $w$ in the second step is $1/(n-2)$. Hence the probability that we chose the triangle $(u,v,w)$ is $1/[m(n-2)]$. Let us denote this event by $E_{u,v,w}$.
If $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$ are two different triangles that the events $E_{u_1,v_1,w_1}$ and $E_{u_2,v_2,w_2}$ are disjoint (note that the triangles don't have to be disjoint). Therefore if there are $T$ triangles, then the probability that we chose one of them is exactly $T/[m(n-2)]$. Therefore the expected output of the algorithm is exactly $T$.


By symmetry, we can assume that $\Pr[X=0] = \Pr[X=1] = p$, and so $\Pr[X=?] = 1-2p$. We can then express $I(X;Y)$ as a function of $p,\lambda,\mu$. The capacity of the channel is the maximum of $I(X;Y)$ over all $p \in [0,1/2]$. You can find this maximum using calculus.
In more detail, let us first note that $\Pr[Y = 0] = \Pr[Y = 1] = (1-\mu)p$ and $\Pr[Y=?] = 1-2(1-\mu)p$. Furthermore, $H(Y|X=?) = 0$ and $H(Y|X=0) = H(Y|X=1) = H(1-\lambda-\mu,\lambda,\mu)$. Therefore
$$
I(X;Y) = H((1-\mu)p,(1-\mu)p,1-2(1-\mu)p) - 2pH(1-\lambda-\mu,\lambda,\mu).
$$
The derivative of this with respect to $p$ is
$$
-2(1-\mu)\log((1-\mu)p)+2(1-\mu)\log(1-2(1-\mu)p) - 2H(1-\lambda-\mu,\lambda,\mu) = \\
2(1-\mu) \log \frac{1-2(1-\mu)p}{(1-\mu)p} - 2H(1-\lambda-\mu,\lambda,\mu).
$$
Equating this to zero, we get
$$
\log \frac{1-2(1-\mu)p}{(1-\mu)p} = \frac{H(1-\lambda-\mu,\lambda,\mu)}{1-\mu}
$$
and so
$$
\frac{1-2(1-\mu)p}{(1-\mu)p} = e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)}.
$$
Massaging this, we finally get
$$
p = \frac{1}{(1-\mu)(2 + e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)})}.
$$


Can you suggest a topic for a Bachelor Thesis in Mathematics that is related to Machine Learning?

I would like to make two points clear as a researcher:

Mathematics is a very broad discipline. When you're on bachelor level it is still appropriate to call it "Mathematics" but already in Masters, you'll need to specialize! Youll have to choose a branch and then you won't be "a mathematician" you'll be Statistician, a topologist, graph theorist, category theorist etc. This being said you need to ask yourself which branch you're most interested in? This leads to the next point:

The fact that you're interested in Machine Learning already narrows it down to  Probability & Statistics, Linear Algebra, Multivariate Calculus. And here I would say that any topic that falls within these categories will help you later along the road.

Bachelor Thesis is a piece of scientific work that's why it is called "Bachelor". You are supposed to do research and produce new knowledge regardless of how small or significant it will be. This forum cant do it for you.
Pick something YOU are interested in from Probability & Statistics, Linear Algebra or Multivariate Calculus and explore the topic. Once you start you'll inevitably get questions that need addressing. If you get stuck pick a classic problem (for example Knight's tour) and systematically break it down.


How to score a given arrangement of windows on a screen to produce good layouts

I will expand on my comment on the other question and propose a target function that ensures that no very small windows occur and that windows are not unnecessarily far away from screen edges. Let $\mathcal{W} = \{1,\dots,n\}$ a set of windows and $T = \mathcal{W} \to \mathbb{N}^4$ a tiling; if $T(W) = (x,y,w,h)$ window $W$'s top-left corner is positioned at $(x,y)$ and $W$ has width $w$ and height $h$. Now let $c : (\mathbb{N}^4)^\mathcal{W} \to \mathbb{R}$ a cost function from the space of all tilings to the reals:

$\qquad \displaystyle c(T) = \left[ \min_{W \in \mathcal{W}} T(W)_3\cdot T(W)_4 \right] - \sum\limits_{W \in \mathcal{W}} \operatorname{empty}(W)$

where $\operatorname{emtpy}(W)$ the maximum number of empty tiles between one of $W$'s edges and the respective nearest screen edges. The objective is maximisation.

Note that this is a (non-equivalent) simplification of the multicriteria optimisation goal of maximising

$\qquad \displaystyle c(T) = \left( \min_{W \in \mathcal{W}} T(W)_3\cdot T(W)_4 \ ,\ -\sum\limits_{W \in \mathcal{W}} \operatorname{empty}(W)\right)$.

Of course you need appropriate restrictions in place that ensure that now window is placed outside of the screen and windows do not overlap.


Find longest subsequence in array with given condition

In the following answer, I show how to solve in $O(n\log n)$ the following similar question:

  Given an array $A$ and a number $k$, find the longest contiguous subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Using this, it is easy to solve in $O(n \log n)$ the following question, closer to yours:

  Given an array $A$ and a number $k$, find the longest subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Indeed, sort $A$ and then find the longest contiguous subsequence satisfying the condition.

Finally, to solve your actual question, filter $A$ by removing all elements at distance more than $k$ from the first element. The longest subsequence is now guaranteed to contain the first element (since it can always be added), so we can run the preceding algorithm to solve your question in $O(n\log n)$.


How to use Artificial Intelligence in Computer Chess

The whole state space for chess is enormous - it can be roughly estimated as 1043 (Shannon number (Shannon, 1950), (Wikipedia)).

The idea you present - Reinforcement Learning agents playing with each other to learn the game - was successfully applied to Backgammon - TD-Gammon (Tesauro, 1995), (Chapter in Reinforcement Learning by Sutton&Barto). It also used Neural Networks to estimate game's value function. This problem is however much simpler, as number of states in Backgammon is significantly smaller than in chess, namely: 18,528,584,051,601,162,496 (Backgammon Forum Archive thread).

If you, however, would end the game after few initial moves and aim only to learn "good openings" you could succeed with analogous approach. The main problem would be to evaluate the game after the opening game, which seems hard. Just a similarity measure to the established positions after well known openings is not enough, because position can be far from them if opponent would make a stupid move (so it wouldn't be because of learning agent's mistake, so the position even if "incorrect" should be evaluated as a good outcome).

References:

SHANNON, Claude E. "Programming a computer for playing chess." In Philosophical Magazine, 7th series, 41, no. 314 (March 1950): 256-75.
Gerald Tesauro. 1995. Temporal difference learning and TD-Gammon. Commun. ACM 38, 3 (March 1995), 58-68


What is a protocol for determining which of two numbers is larger, without sharing those numbers?

As pointed out by Luke Mathieson in the comments, this problem is called Yao's Millionaire Problem, for which protocols can easily be found by Googling.


What is the best terminology for lower bound

If you want to talk about the complexity of a problem, just use "the complexity of the problem" and don't bring lower bounds into it.

GOOD: "The complexity of SLL(k) testing is exponential."

GOOD: "The complexity of SLL(k) testing is at least exponential."

GOOD: "There is an exponential lower bound on the complexity of SLL(k) testing."

GOOD: "The complexity of SLL(k) testing is in $\Omega(2^n)$."

BAD: "The lower bound of SLL(k) is exponential."  <--- Don't say this!  There's more than one valid lower bound.

BAD: ""The complexity is at least $O(2^n)$."  <--- Don't say this!  Big-O is an upper bound; it doesn't go with "at least".


b0a has two subtly different productions (Note: I always expand the leftmost non-terminal):

EXP --> bEXP --> bEXPa --> b0a and
EXP --> EXPa --> bEXPa --> b0a,

so that's an example of an ambiguous string.

To give a priority over b means that if you have b0a it will always be parsed as b(0a)  (i.e. the first production I showed).

For the bit involving b and m, can you find two different productions for b0m0?

1m1m0 also has two subtly different productions:

EXP -> EXPmEXP --> 1mEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0 and
EXP -> EXPmEXP --> EXPmEXPmEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0.

To make m associative is to remove this ambiguity, so that only one of these parses is possible (from the question, it doesn't seem to matter which one exactly, as long as you choose one and stick to it!)


Finding the language of a context-free grammar?

Your grammar generates the language of all palindromes. It can be described in the following ways:

$L(G)$ is the language of all palindromes over $\{0,1\}$.
$L(G) = \{ x \in \{0,1\}^* : x \text{ is a palindrome} \}$.
$L(G) = \{ x \in \{0,1\}^* : x^R = x \}$.

The first option is really the best, but unfortunately your TAs are expecting the third option.


How to handle missing attribute's value with ID3 algorithm?

One approach is to use imputation to estimate a value for the missing attribute, based on other attributes.

See also https://en.wikipedia.org/wiki/Missing_data#Techniques_of_dealing_with_missing_data and https://stats.stackexchange.com/questions/tagged/data-imputation and https://stats.stackexchange.com/questions/tagged/missing-data
and https://stats.stackexchange.com/q/208845/2921.


Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$

Here is a proof sketch. We use the fact that any function on $O(\log n)$ bits can be computed in depth 2 and polynomial size.

The input is $\log n$ integers of length $n$, which we can think of as an $n\times \log n$ matrix.
Sum the columns of the matrix to get a vector of length $n$ in which each entry has length $\log\log n$. We can also think of this as a staggered sum of $n$ numbers of length $\log \log n$, which is equivalent to the original sum.
Divide the staggering sum into blocks of length $\log n/\log\log n$, by possibly dividing each summand into two parts. Each block contains $\log n/\log\log n$ summands of length $\log\log n$. Sum each block to obtain a result of length at most $2\log\log n \leq \log n/\log\log n$ (for large enough $n$). We can think of this as a new staggering sum.
Repeat the previous construction. Now each block contains two summands, so the result is of length $\log n/\log\log n + 1$.
Again divide into blocks. This time each block contains the sum of a full length ($\log n/\log\log n$) integer $x$ and one extra bit (a least significant bit) $y$. The actual sum also includes an extra carry bit $z$ which depends on the less significant blocks. If we could determine $z$ then we could determine the value of the sum in that block.
It remains to show how to calculate the carry bit coming from the addition of blocks $B_k,\ldots,B_0$ (most significant to least significant). Suppose that in block $B_i$ we are adding $x_i$ to the bit $y_i$. Let $M$ be a block full of 1s. There is carry iff for some $i$, $x_k + y_k = x_{k-1} + y_{k-1} = x_{i+1} + y_{i+1} = M$ and $x_i + y_i = M + 1$.

If you have trouble with the proof sketch (which I haven't described very clearly), try using diagrams. The idea is to start with the initial sum and replace it with progressively simpler but equivalent sums, until the final sum can be computed in one go.


If $L_1$ is semidecidable, there's a TM $M_1$ that takes a string $x$ and always reliably halts and answers "yes" if $x\in L_1$. If $L_2$ is decidable, there's a TM $M_2$ that always halts and reliably answers "yes" if $x\in L_2$ and "no" if $x\notin L_2$.

Make a new machine $M$  that when given an input string $x$ first runs $M_2(x)$. If the answer is "yes" then you know $x\notin L_1\setminus L_2$ so have $M$ halt and answer "no". If, on the other hand, $M_2(x) = "no"$ then $x$ may or may not be in $L_1\setminus L_2$, so then run $M_1(x)$ and do whatever $M_1$ does. It may never halt or it may answer "no", but if $x\in L_1\setminus L_2$ your $M$ will correctly answer "yes", proving that $L_1\setminus L_2$ is indeed semidecidable.


Reverse cartesian product matching all given rows

Unfortunately the problem is NP-hard when the number of columns ($n$) is unlimited.  In particular, consider the case with $n$ columns and where every number in every row is either 0 or 1.  Then your problem is equivalent to: given a truth table for a boolean function, find a minimal DNF formula (with the minimum number of clauses) for that function.  This is NP-hard.

I know you said you'll have at most 8 columns, so this theoretical result doesn't necessarily imply there is no hope for your specific situation, but it does suggest that you shouldn't expect an efficient algorithm that will generalize to a large number of columns.

One approach you could use that might work well enough in your situation is to use a SAT solver.  Encode each of the sets $A_{i,j}$ with a one-hot encoding; i.e., you have variables $x_{i,j,t}$, which is true if $t \in A_{i,j}$ or false otherwise.  Then it is easy to write down a bunch of constraints (clauses) that enforce that these $A_{i,j}$ form a solution to your problem.  For instance, for each row $r$ that isn't in the input (each $r \notin S$), you get a constraint that $r_1 \notin A_{i,1} \lor r_2 \notin A_{i,2} \lor \dots$ for each $i$, i.e., $(\neg x_{i,1,r_1}\lor \neg x_{i,2,r_2} \lor \dots)$.  And so on.  In this way, for any $k$, you can set up a SAT instance that will be satisfiable iff it is possible to express your input using $k$ reverse cartesian products.  Then you can use binary search on $k$ to find the minimal $k$ such that this is possible.

Because SAT is NP-hard, this won't scale to very large inputs, but it's possible it might work well enough on the problem sizes you mention.  The only way to know for sure is to try it and see.


Implementing wait-free consensus with queues

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question.

We study how initialization of shared objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus
between two processes, we prove that an initially empty queue or stack cannot.
However, with a tiny extra resource such as a 1-bit safe register, an empty queue or stack suffices to solve consensus.

Please check Section 5 for impossibility proof and algorithm.

Please also check the paper "On the Importance of Registers for Computability" by Rati Gelashvili, Mohsen Ghaffari, Jerry Li, and Nir Shavit, 2014.
In the second paragraph of Introduction, the authors claim that:

(1) We show that $\ldots$ two queues in arbitrary initial states are sufficient for solving two process consensus.
(2) On the other hand, we prove that it is impossible to solve two process consensus using a single empty queue.

A little conclusion is:

In other words, unless you have multiple queues or multiple registers, a queue’s ability to solve consensus is completely dependent on its initialization.

There are many propositions/lemmas/theorems in this paper. And they are not limited to the queue object. I think it may contain what you want to know (I will read it carefully when I have time).


Efficient algorithms for finding a region in $\mathbf R^2$

Here's an idea that might be quick in practice. Judging from the OP's comments, this is idea is implementable.

The idea is that we start scanning from a corner and approach the center of the rectangle. Once the scan finds a vertex $v$ with label $1$, it halts. Start a DFS from $v$. Keep a stack $F$ that represents the frontier into which you can expand the search. A vertex is put into the stack if and only if it has at least one neighbor whose label is $0$. The idea is to complete a cycle, while staying on the boundary.

The figure above is a rough representation of the initial region of the green vertices labeled $1$. Say we start scanning from the upper right corner. The vertex $29$ is the one we hit, and the one from which we start a DFS.

The DFS was started from the purple vertex $29$. In the figure, $F$ would contain $9$ and $28$, because they are the only neighbors we can visit next that have at least one neighbor with the label $0$. The cycle is completed when we come back to $29$ or when the frontier meets.


The DPLL algorithm doesn't try to satisfy as many clauses as possible.  If there is a satisfying assignment, DPLL will find it.  Otherwise DPLL will try a series of partial assignments until it runs out of possibilities, and then it will declare the formula unsatisfiable.  But in the case of an unsatisfiable formula, there is no guarantee that DPLL will discover the maximum number of satisfiable clauses on the way to proving unsatisfiability.
The MAXSAT problem is related to finding the minimally unsatisfiable subformulas (MUSes) of an instance.  Determining whether a set of clauses is a MUS is a DP-complete problem.  This is expected to be harder than mere NP-completeness, so it is unlikely that modifying DPLL to return partial solutions is going to be fruitful.  Given that the class DP is contained in $\Delta^P_2$ you might devise a scheme that calls DPLL (or related algorithms) a polynomial number of times to produce a MAXSAT result.


Why are random numbers important to the study and application of computer science?

There are a lot of applications of Random numbers in Computer science, there are full books about it, check Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan, for instance. There you will find many arguments for the case of random numbers.

Here is a not exhaustive list of applications in sub-fields of CS:

Algorithms (As Yuval pointed, there are many problems where only randomized algorithms are known and you will find that many times randomized algorithms are simpler and more efficient than their deterministic counterpart)
Machine Learning ( Generative algorithms, variational autoencoders, GANS, Bayesian inference, Monte-Carlo algorithms, ...)
Cryptography(randomized prime number testing, ...)
Computer graphics and simulation (Path Tracing, Procedural stuff, games, ...)
Big Data (search for sketching algorithms, probabilistic counting, Bloom filters, ...)
Optimization (stochastic gradient descend, meta-heuristics)
Simulation (random processes, multi-agent, stochastic differential equations,...)

I am sure there are plenty more.


How to enumerate combinations in parallel

Since you just need to select $k$ rows, this becomes the same as choosing $k$ elements of a given set of $n$ elements, say $\{1,2,\dots,n\}$.

You can generate $n \choose k$ combinations in lexicographic order (i.e. starting with $\{1,2,3, \dots, k\}$ and ending with $\{n-k+1, ..., n-1,n\}$), with the next one depending only on the previous one.

The fact that the order is predictable, and that you only need the previous state, allows you to split the output space, and apply independent parallel computations to each.

There are plenty of algorithms available on the web for lexicographic generation, for instance Frank Ruskey's book: Combinatorial Generation has a chapter (4) on lexicographic algorithms, and for your purposes, you can use Algorithm 4.4 which appears on page 58.


Problems for which there is no algorithm with smallest time complexity

The existence of such problems follows from the Blum speedup theorem. The theorem shows, for example, that there exists a problem such that for any algorithm solving it in time $T(n)$, there is another one solving it in time at most $\log T(n)$.


How would a CPU know if a piece of data is in cache or RAM or on disk?

How does the CPU know if a piece of data is in L1 cache?  The L1 cache is part of the CPU (it's on the same chip) so the CPU just asks the L1 cache "do you have the data for address X?"; if it gets the answer "yes", it is good; if it gets the answer "no", then the CPU tries to read from RAM.

How does the CPU know if a piece of data is in physical memory or on disk?  The operating system keeps track of what data has been paged out to disk.  See https://en.wikipedia.org/wiki/Virtual_memory for details on that.


recognize strings of 1's and 0's which are multiples of 3

If the question intends anything other than your option 2 (binary representations of natural numbers that are divisible by 3), then it is a badly written question.

If the qeustion meant strings in which the number of 0s and the number of 1s are both divisible by 3, it would have said that. It would be bizarre to have numbers whose digits are all 0s and 1s and intend some base other than binary without mentioning that.


Boolean Functions Implemented by Multiplexers

I think there is no specific name for it, just several methods, c.p. this website
Note that it's quite simple to e.g. implement all 2-input logic functions with a 4 input
 1 output mux, by connecting the inputs to the address/select lines, and applying the constants 0/1 to the data inputs. (This actually transforms the MUX into a Lookup table (LUT))


What is the concept of "encoding" in NP-completeness

Everything is in binary in your electronic computer. However:

We don't want to have to throw away all of the theory of computation if somebody builds a really fast ternary computer.
More importantly, the stuff we wish to compute upon isn't binary. It's strings and graphs and numbers and things like that. So the very first thing you need to do is to encode your string/graph/number into a form that fits into your model of computation. And, since we are forced to encode, we'd better consider whether our encoding is a good one.


As I understand your question, the double-sided machine has a tape indexed by $\mathbb{Z}$ and the one-sided has a tape indexed by $\mathbb{N}$.

The question then boils down to finding a bijection f between the two sets st. $\forall z \in \mathbb{Z}: |f(z) - f(z+1)| < k$ for some constant k. Can you find such a bijection:

Hint: k = 3 is sufficient.


Remapping values to bias a uniform set towards a certain curvature

For continuous distributions, you can use the inverse transform sampling method.  See also https://stats.stackexchange.com/q/176955/2921 and https://en.wikipedia.org/wiki/Ziggurat_algorithm.

For discrete distributions, you just generate a random floating point number in the range [0,1], and then figure out which of the buckets $[0,p_1)$, $[p_1,p_1+p_2)$, $[p_1+p_2,p_1+p_2+p_3)$, ..., $[..,1]$ it falls into, where $p_1,p_2,p_3,\ldots$ are the desired probabilities of the possible values.  See also https://stats.stackexchange.com/q/26858/2921 and http://www.keithschwarz.com/darts-dice-coins/.


Can a Turing Machine decide only non-regular languages?

@Karolis Juodele already gave the answer, and your answer is also correct.

Another thing to keep in mind is although infinite languages can be undecidable, some of them are regular.. ex. $\{0\}^* \subset \{0,1\}^*$ is an infinite language but is regular (you can construct a FSM, with a single state, that accepts it).

Basically any undecidable language is infinite, but any infinite language is not necessarily undecidable.

Also, for a language like $L = \{w \mid m \text{ halts on the input } w\}$, there exists a Turing Machine for which $L$ is undecidable.


substitution method on T(n) = T(floor(n/2)) + n recurrence

As Yuval has mentioned in the comment that the proof is based on the complete induction.
However, an important thing is missing in the screenshot that you have shared. The "base case" is missing. Without the base case, the induction hypothesis and proof make no sense.
Here, the base case is when $n = 1$. You might want to verify that $T[1] = O(1)$. And, if that is the case, then $T[1]$ satisfies the induction hypothesis, i.e., $T[n] \leq c \cdot n \log n$ for $n = 1$ and sufficiently large $c$. Now, you would like to prove that the hypothesis also holds for other values of $n$.
For this, you assume that $T[m] \leq c \cdot m \log m$ for any $m<n$. And, suppose using this you could prove that $T[n] \leq c \cdot n \log n$. Then, it will imply that the hypothesis is indeed the correct hypothesis for every $n$. This is because you can apply this proof step to the base case. And, it will give you the correctness of the hypothesis on $T[2]$. Then, you apply the proof step on $T[2]$ and it will give you the correctness on $T[3]$, and so on... Therefore, it proves that the hypothesis is indeed the correct hypothesis for all value of $n$, for sufficiently large $c$.


Your idea of stopping when there are $r$ vertices remaining is the correct approach. Now let us see how to bound the success probability of contracting one arbitrary edge not in a fixed $r$ way cut-sets.

Denote the graph by $(V,E)$ with $n=|V|$ and $m=|E|$.

Lemma: Let $C$ be an $r$-way minimum cut. The probability that a randomly selected edge is not in $C$ is at least
$$\frac{(n-r+1)(n-r)}{n(n-1)}.$$

Proof:
Let us count the number of elements in the following sets.

$$\begin{align}
V^{r-1}&=\{Q: Q \subseteq V\text{ such that } |Q| = r-1\}\\
S&=\{(e, Q):  Q\in V^{r-1}, e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{e}&=\{\phantom{(e,\,} Q\phantom{)}: Q\in V^{r-1}\phantom{, e\in E } \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{Q}&=\{\phantom{(}e\phantom{,Q)}: \phantom{Q\in V^{r-1},\,} e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
\end{align}$$

$|V^{r-1}|=\binom{n}{r-1}.$
$|S_e|=\binom{n-2}{r-1}$ for all $e\in V$.

Fix an arbitrary $Q\in V^{r-1}$. If we removes all edges not in $S_Q$, i.e., all edges whose endpoints are in $Q$ and all edges between a vertex in $Q$ and a vertex not in $Q$, there will be $r-1$ connected components of single vertex and one or more connected components in the remaining vertices. That means the set of all edges not in $S_Q$ is an $r$-way cut. Since the minimize size of an $r$-way cut is $k$, the number of edges not in $S_Q$ is no less than $k$, i.e, $|S_Q|\le m-k.$

Since $S$ is the disjoint union of all $S_e$, $e\in E$ as well as the disjoint union of all $S_Q$, $Q\in V^{r-1}$,
$$\binom{n-2}{r-1}m \le (m-k)\binom n{r-1},$$
which means,
$$1-\frac k{m} \ge\frac{\binom{n-2}{r-1}}{\binom n{r-1}}=\frac{(n-r+1)(n-r)}{n(n-1)},$$
where the left side is exactly the probability that a randomly selected edge from $E$ is not in $C$, a set of $k$ edges. QED.

Now that we have the lemma above, we can proceed just as in the book to compute the probability that any given minimum $r$-way cut $C$ survives all $n − r$ random successive edge contractions.

Exercise. (One minute or less) Check that the lemma and its proof above  specialize to the arguments given in the book in the case of $r=2$.


Finding the $k$th largest element in an evolving query data structure

Have a look at the Wikipedia page for segment trees:

  It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

So it does not seem to be a good data structure for your scenario at all.

Note that the kind of query you want to perform is called selection (unimaginative, I know). Check the linked article for loads of algorithms. One simple way to solve your problem is this:

Store elements in a sorted list. That means, updates (that is insertions) take linear time.
For the queries, run a selection algorithm on the specified interval.

This approach can be improved by extending the list to a skip list.

Another approach is using binary search trees. If you use a self-balancing variant, that makes updates possible in $O(\log n)$ time. The queries you want can be implemented by storing in every node how many descendants it has, so we can find the $k$-th largest element in $O(\log n)$ time.


Exact runtime of median of median algorithm

"since $T(n)=O(n)$ then $T(n)=an+b$" it's wrong assumption, because big-$O$ gives only upper bound. For example $n^\alpha \in O(n)$ for $\alpha \in (0,1))$, $\log n \in O(n)$ etc., so you cannot reduce situation for only linear functions.
For exact estimation you need to elaborate $O(n)$ in recurrence relation.


Proving a language is not regular with pumping lemma

To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be all $a$s, so pumping up leaves us with a string $s'=a^{p+k}b^{p} \notin A$.


What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$?

$$\newcommand{\expr}{\mathsf{expr}}
\newcommand{\int}{\mathbf{Int}}
\newcommand{\List}{\mathbf{List}}
\newcommand{\let}{\mathbf{let}}
\newcommand{\id}{\mathsf{id}}
\newcommand{\in}{\mathbf{in}}
\newcommand{\map}{\mathsf{map}}
\newcommand{\string}{\mathbf{String}}
$$

It's not really possible to answer this without being a little more precise about the status of some things. To this end, let's be clear about distinguishing 'meta' variables from variables that may be part of the syntax of the language. I'll use Greek letters for meta variables and English letters for object variables. Term names will be sans-serif, like $\expr$, keywords/constants will be bold, like $\int$.

So, the two things you ask about actually become at least three things:
$$
\begin{align}
\expr &: α → β \\
\expr &: a → b \\
\expr &: ∀ a\ b. a → b
\end{align}
$$

The first is something you might see when discussing the simply typed lambda calculus. It does not have type variables in its object language at all, but it would be inconvenient to talk about particular concrete types all the time. So instead, people tend to talk about things in a schematic way, where meta variables stand in for arbitrary particular simple types. So, something like:

$$\frac{}{λx. x : α → α}$$

is actually a schematic statement, saying that $λx.x$ could be shown to have any type of the form $α → α$. But in a concrete derivation, each occurrence of $λx.x$ can only have a particular concrete type, like $\int → \int$. There is no universal identity function in the language, each occurrence of $λx.x$ stands for an identity function that only works on one type. Perhaps it might help to require annotating the lambda bound variable in this scenario, like so:

$$λ(x : \int). x$$

since now the notations for different identity functions are actually syntactically distinct.

Now, the obvious problem with this is that the concrete system is awful to work in. You can tell, because people are routinely writing schemas rather than concrete stuff. It is basically the type system of C, and schemas are like macros that automatically copy and paste your code, which is one way that people work around this awfulness in actual C (the other way being unsafe casting, which prevents the types from guaranteeing that your code actually makes sense).

To remedy this, we can move to #2, which is to make type schemas a well-defined part of the language. This is the approach of things like Hindley-Milner (HM), and the many languages based on it (ML, Haskell, ...). One way of looking at HM is that you add named definitions to the language itself, and these definitions are allowed to have internalized type schemas, rather than particular simple types. Then, when those named definitions are referenced, the schema can be instantiated to any concrete type necessary, and the fact that the schematic definitions are uniform in the choice of type ensures that they will work. So for instance:

$$
\begin{align}
\let\ &\id : a → a \\
      &\id = λ x. x \\
\in\ &(\id\ 5, \id\ \texttt{"hello"})
\end{align}
$$

This sort of system is a pretty strong sweet spot, because it is easy to implement and these sort of named schematic definitions cover a wide range of things that people want to write.

However, one deficiency is that these schematic objects are not first class. Expressions cannot be given a schematic type, only named definitions can, even though we somehow figure out that expressions are valid ways of implementing them. And we cannot take something with a schematic type as an argument to a function to be used at multiple instantiations. Even though:

$$λi. (i\ 5, i\ \texttt{"hello"})$$

seems similar to our term with $\let$ above, it is invalid, because $i$ is a lambda-bound variable, not a definition name.

So, the step to eliminating this discrepancy is to pass from type schemas: $$a → b$$ to quantified types: $$∀ a\ b. a → b$$.

The idea is that the quantifier can bind variables and produce something that is a type in its own right. Then we can ascribe these types to expressions (and variables), rather than only to named definitions. If we do keep named definitions around (which really we probably should, although many type theories aren't presented that way), they no longer have a special status with respect to typing.

All our previous schematic definitions can be translated to this new system by putting all the quantifiers at the beginning of the schema:

$$
\begin{align}
\let\ &\id : ∀ a. a → a \\
      &\id = λ x. x \\
 \in\ &(\id\ 5, \id\ \texttt{"hello"})
\end{align}
$$

But now we can write a corresponding lambda expressions and make sense of their types:

$$
\begin{align}
(λi. (i\ 5, i\ \texttt{"hello"})) &: (∀ a. a → a) → (\int, \string) \\
λx. x &: ∀ a. a → a \\
(λi. (i\ 5, i\ \texttt{"hello"}))\ (λx.x) &: (\int, \string)
\end{align}
$$

There are subtleties/consequences to these steps that I haven't mentioned, but this is sort of the core idea. You might also make slightly different choices for notation. For instance, you might require writing the prefix $∀$ syntax for the schemas because it is clearer that it means the named definition works for every choice of instantiation of the variables, not for some unknown choice.


Correctness of algorithm to find maximum in array

Tip: It's usually easy to proof by contradiction. Ignore the rest if you liked the suggestion.

Suppose you found some ans using your algorithm and ans is not the biggest.

If it's not the biggest, it means at some point, your ans was compared to a value X that's bigger than ans and max(ans, X) returned you ans.

Since max returns only the maximum value and X is bigger than ans, it's a contradiction.

By induction in the size n of the array, it's quite easy:

Base case: n = 1

the algorithm will run and return the only element who is also the biggest [OK]

Hypohtesis: The algorithm works for any n

Inductive Step: It works for n+1

Let's say you runned the first n elements of the array and you have your ans.
Now you will just compare ans with the last element and you will return the biggest.
As ans was the biggest from the first n elements (by hypothesis, we can find the biggest between n elements) and ans will be the maximum between ans and the last element, ans will be the maximum of the full array. [OK]

hope it helps.


Finding the path of a negative weight cycle using Bellman-Ford

Per Kleinberg–Tardos, you want to run Bellman–Ford for n iterations and find a cycle in the predecessor array.

To find a cycle in the predecessor array, start by coloring every node white. For each node u in an arbitrary order, set v := u, and, while v is white and has a predecessor, recolor v gray and set v := predecessor[v]. Upon exiting the loop, if v is gray, we found a cycle; loop through again to read it off. Otherwise, none of the gray nodes are involved in a cycle; loop through again to recolor them black.


Bits needed to send parameters of perfect hash functions

If I understand you correctly, the following is the case:

The server has $n$ files in some order $f_1, f_2, \dots, f_n$.
The user also has exactly one of those files, $f_u$, but does not know $u$.
The user and server agree on some protocol beforehand, which does not depend on any of the $f$.
The server gets to communicate some bits of information to the user once, and only in this direction.
From this information the user must be able to find integer $k$ such that $f_k = f_u$.

Based on the above I would choose some strong cryptographic hashing function $H$, and use it to hash all files on the server. Take the $k$-bit prefix of this hash such that all prefixes are unique. Send these in the correct order for $O(kn)$ total complexity.
How big does $k$ need to be in practice? The chance that the first hash is not a duplicate is $1$, the second $1- \frac{1}{2^k}$ chance, the third $1- \frac{2}{2^k}$, etc. We find that none are duplicates as $\prod_{i=0}^{n-1} (1 - i/2^k) \approx e^{-n^2/2^{k+1}}$ by the Birthday paradox. Let's say we're okay with constant chance of failure $\epsilon$, and thus we want $e^{-n^2/2^{k+1}} > 1-\epsilon$, which gives $k \in O(\log(n))$.
Thus our solution uses $O(n \log n)$ bits. You can't beat this (asymptotically) either, because a full permutation worth of information needs to be transferred, which takes $O(\log n!) = O(n \log n)$ bits.


Algorithm - we will accept the request that finishes first. This is also quite a natural idea, we ensure
that our resource becomes free as soon as possible.In this way we can maximize the time left to satisfy other requests.

let O is the set of optimal intervals and A is the set of intervals produced by our algorithm

formally:
   Initially let R be the set of all requests, and let A be empty
     While R is not yet empty
        Choose a request i ∈ R that has the smallest finishing time
        Add request i to A
        Delete all requests from R that are not compatible with request i
     EndWhile
   Return the set A as the set of accepted requests

Let i1,..., ik be the set
of requests in A in the order they were added to A

similarly let j1,......jm be the set of requests in O in the order they were added to O

we have to show that k $=$ m , that is both the set have same number of intervals

we want to show that our greedy rule “stays ahead” which means that each of its intervals
finishes at least as soon as the corresponding interval in the set O.

which means f(ik) $\leq$ f(jK)

here f(ik) denotes the finishing time of a interval i

this statement can easily be proved using induction.
base case here is the very first interval
 which is f(i1) $\leq$ f(j1)

Optimality -
Now let's assume that k < m which means there is a interval in O which is not selected by our algorithm

let the index of that interval is k+1

we know that f(ik$+$1) $\leq$ f(jk$+$1)        -   based on the statement we just proved

also f(ik) $\leq$ f(ik$+$1)  and  f(jk) $\leq$ f(jk$+$1)      -   As the intervals are ordered by their finishing time

clearly jk$+$1 interval was available after jk finished but we know that ik finished before jk,
so this means that an interval was available for selection after ik finished but our algorithm did not select it, but this can not happen
as our algorithm will only stop when there are no intervals left.

so our assumption was wrong which means k = m

PS - I suggest reading the greedy algorithm section from the "Algorithm & Design" by Kleinberg and tardos

here is a link to a soft copy -
http://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf


Are there NP languages whose verification is P-complete?

Every language in NP has a logspace verifier.

Indeed, let $L$ be any language in NP. Therefore, there is a polynomial time machine $T$ and a polynomial $p$ such that $x \in L$ iff some string $y$ of size at most $p(|x|)$ makes $T(x,y)$ accept.

While the witness $y$ may be hard to check, we can make help a logspace machine verify it by including the transcript of the accepting computation. We construct another machine $T'$ which accepts a new witness $z$. The witness $z$ consists of a sequence of configurations of the machine $T$, starting with an initial configuration encoding $x$ and $y$, and ending at an accepting configuration. Since each configuration has polynomial length, a logspace machine can verify that $z$ indeed consists of a valid sequence of configurations.


Subtracting lower-order term to prove subtitution method works

If you're using the same book I have (Introduction to Algorithms 3rd edition), then you mis-wrote the question. The relation in question should be: $T(n)=4T(n/2) + n.$

That said, substitution here won't work, as you know.  Assuming $T(n) \le cn^2,$
you get:

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}) + n$

$T(n)\le cn^2 + n$

Which doesn't imply  $T(n) < cn^2.$ Instead, you can make the assumption: $T(n) \le cn^2 - bn.$

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}-b\frac{n}{2}) + n$

$T(n)\le cn^2 + n(-2b + 1)$

Letting $b=1,$ you get an equation consistent with the initial asumption. Namely:

$T(n)\le cn^2 - n$

As a side note, the relation you initially wrote, $T(n)=4T(n/2) + n^2,$ can be solved using case 2 of Master's Theorem, and has an answer of $\Theta(n^2lg(n))$


Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?

My initial thought was the following framework for an algorithm:

let c = empty array of size n
let G = ({}, {})
for i in [0, n):
    while there's not an independent set of size k_i in G:
        add a new vertex to G
    let S = an independent set of size k_i in G:
    connect every vertex in S to every other vertex in S in G
    let c[i] = S

The glaring issue is that I'm relying on a algorithm for independent set here, and there's no general polynomial-time algorithm for it. What I'm trying to figure out is if there is some structure inherent to this problem that makes independent set feasible to compute.

There's a polynomial time algorithm for finding an independent set on a chordal graph (though I can't find a straightforward presentation of the algorithm anywhere yet), so if I can prove that $G$ is always a chordal graph I've solved the problem.

A graph is chordal iff it has a perfect elimination ordering, an ordering of the vertices such that for any vertex v, v and the neighbors of v that occur later in the ordering form a clique. I'll prove this using induction.

Base case:
Our starting graph has a trivial empty ordering, so our base case holds.

Inductive step:
We need to show that adding some number of vertices, then filling out an independent set they are part of into a clique, creates a new graph with an ordering if the original graph already had one.

Let $s$ be the previous ordering (for example, $1342$). Let $t$ be an arbitrary ordering on the new vertices. Let our new ordering be $ts$, the concatenation of the two orderings. Since the only edges these new vertices have are within the new clique, and removing any of the vertices in a clique leaves the remaining vertices in a clique as well, as we move across $t$ and check if it forms a clique with the following neighbors in $ts$, it always will. Since we already know the vertices in $s$ satisfy the ordering criteria by the induction hypothesis, all the vertices in $ts$ satisfy the induction hypothesis and our new graph has a perfect elimination ordering. So the inductive step holds

So by our base case and inductive step, on every step of the algorithm, finding the independent set will take only polynomial time in the total number of nodes and edges, and since adding a $k_i$-clique can always be done in $k_i$ or fewer new vertices, the number of vertices is at most $\sum_{i=0}^{n-1} k_i$, the number of edges is at most the square of that, and therefore the whole algorithm is polynomial in the sum of the inputs, as desired.

I haven't proved that the result has the minimal number of vertices yet. That's going to have to wait for another day though. Might have to explain the previous parts a bit better too.


What makes it so difficult to prove P =/≠ NP? — The subset sum issue

Many simple-seeming problems turn out to have solutions that are extremely complicated and deep. That's not a bad thing, in fact it's what keeps mathematics interesting. One of the best known examples is Fermat's Last Theorem, which states that the equation $x^n+y^n=z^n$ has no solution in positive integers $x, y, z$ whenever $n\ge 3$. One could hardly ask for a simpler problem, but despite the efforts of some of the brightest mathematicians it remained unsolved for 358 years! On the plus side, three centuries of trying (and failing) to prove Fermat's Last Theorem led to the development of a lot of what's known as algebraic number theory.

Indeed, the subset sum problem is easy to state. Finding a poly-time solution, though, has turned out to be really hard, to the extent that no one has yet been able to demonstrate one. One could say, "Okay, I'll turn the problem around and show that there is no poly-time algorithm possible." Ugh! That sounds even worse: how could one establish that among the infinitely many algorithms to solve subset sum, there are none that run in time polynomial in the length of the instance to be solved?

I don't necessarily recommend this, but you could just try inventing an algorithm of your own that always finds the correct answer to subset sum. You'll almost certainly find, as others have, that no matter how much cleverness you throw at the problem, you'll fail to come up with a "fast enough" algorithm. That, at least, should disabuse you of the notion that simple questions should have simple solutions.


The notation $|V|$ here means the number of vertices in your graph. Likewise, $|E|$ is used to denote the number of edges. We typically say that a graph is sparse whenever $|E| \in O(|V|)$ - i.e there are few enough edges. Similarly, we say that a graph is dense whenever $|E| \in \Theta(|V|^2)$ - i.e there are many edges in your graph. These are not really rules, but rather just the terminology one often uses in textbooks.

An adjacency matrix requires $\Theta(|V|^2)$ space to store, while an adjacency list requires $\Theta(|V| + |E|)$ space to store. So when the graph is sparse, using an adjacency matrix is wasteful in terms of space usage, even though answering queries may be faster. On the other hand, is the graph is dense, then both representations require a quadratic amount of space to store, and so you are better off using the adjacency matrix for $O(1)$ edge queries. There are other trade-offs that one can consider as well depending on the queries you anticipate using often, such as vertex insertion/deletion, neighborhood queries, among others... but this is the general rule of thumb.

It may also make a difference when implementing certain algorithms, like Dijkstra's. Using an adjacency matrix, the algorithm takes $O(|V|^2)$ time, but using an adjacency list, it can be implemented in $O(|V| + |E| \log |E|)$ time. This type of trade-off is common when implementing different graph algorithms.


Integer programming to MAX-SAT translation

The decision versions of both MaxSAT and integer programming are in fact NP-complete, so there is polynomial reduction from integer programming to MaxSAT.

In the context of solvers, modern MaxSAT solvers support "weighted partial MaxSAT"-encodings (weighted clauses with possibly infinite weights), so you can add any SAT encoded hard constraints by encoding them as clauses with infinite weight.

For comparing MaxSAT and IP solvers, I would strongly suggest looking at modern literature on "implicit hitting set" algorithms for MaxSAT. The solvers using this algorithm use both IP solvers and SAT solvers as subroutines for solving MaxSAT. It might even be that if you use some direct translation from IP to MaxSAT and give the resulting instance for these solvers, the solver will under the hood just directly solve the original IP instance with the IP solver. Also, there is a lot of recent research comparing IP and MaxSAT solvers for solving specific problems (just search "integer programming maxsat" in Google Scholar).


A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives.  A join (specifically, an equi-join) which is expected to have some non-matching keys can be sped up by pre-processing the valid keys from one table into a Bloom filter.  The join operator tests each key from the other table against the Bloom filter first and only does a full lookup for each positive ("maybe in the set") result.

For instance if you are joining on B_id above, you might first preprocess all of the B_id's in table B into a Bloom filter, and use it to test each B_id in table A for a possible match.  If a B_id from A tests negative in the filter, you can discard it, so you only consult table B for B_id's which are either in B or are false positives.

The benefit of using a pre-filter is basically in the number of negatives it can eliminate at a lower per-key cost than a full lookup.  The filter may also be a smaller size than the set of keys it represents, so it can be broadcast to all threads or nodes that are processing the join in a distributed environment.

Ives and Taylor summarize a number of techniques like this in Sideways Information Passing for Push-Style Query Processing.


The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-hardness of HALT), which contradicts the time hierarchy theorem. We conclude that HALT is not in P.

Consider now a different problem, REGEXP-INT, in which given a list of regular expressions, we have to decide whether their intersection is empty. This problem is coPSPACE-hard, and so if it were in P, then P=PSPACE. While we don't know for sure that P is different from PSPACE, this is widely conjectured (and follows from P$\neq$NP), and assuming that, we conclude that REGEXP-INT is not in P. We call this a conditional result. Similarly, SAT is NP-hard, and so unless P=NP, SAT is not in P.

The unconditional results invariably use one of the hierarchy theorems, and so eventually, diagonalization. This technique itself cannot separate P from NP, due to the so-called "relativization" barrier (though non-black-box diagonalization still stands a chance).


Are Huffman trees and optimal binary search trees for solving the same problems?

Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected number of questions. The difference lies in which questions are allowed:

In the case of Huffman trees, you can ask any Yes/No questions of your choice.
In the case of BSTs, you can ask a 3-way question of the form "$x < t$, $x = t$, or $x > t$?".

Neither Huffman trees nor binary search trees are described in this way usually. Instead:

Huffman trees can be viewed as a way of coding elements drawn from $\pi$ in a prefix-free way (no codeword is the prefix of another). The code of an element consists of the path that takes you from the root to the appropriate leaf ($0$ for taking a No edge, $1$ for taking a Yes edge).
Binary search trees allow searching $x$ inside a list $y_1,\ldots,y_n$. The answer is either $y_i$ (this corresponds to items stored in internal nodes), or $y_i < x < y_{i+1}$ (this corresponds to items stored in leaves; this includes the cases $x < y_1$ and $y_n < x$).

This should answer most of your questions.


Normalized measure from dynamic time warping

Sure.  There's a straightforward way to convert an unnormalized distance metric into a normalized similarity measure.  Basically, use

$$S(x,y) = \frac{M - D(x,y)}{M},$$

where $D(x,y)$ is the distance between $x$ and $y$, $S$ is the normalized similarity measure between $x$ and $y$, and $M$ is the maximum value that $D(x,y)$ could be.

In the case of dynamic time warping, given a template $x$, one can compute the maximum possible value of $D(x,y)$.  This will depend on the template, so $M$ becomes $M(x)$, and the formula becomes

$$S(x,y) = \frac{M(x) - D(x,y)}{M(x)}.$$

So how do you compute $M(x)$?  Basically, multiply the length of the template (the number of samples in the time series), times the maximum value of each sample.  If each sample is in the range $[0,1]$, then the maximum value of each sample is 1, so $M(x)$ becomes just the length of $x$.  This gives a simple upper bound on $D(x,y)$.  [Trivia: in fact one could compute a slightly tighter upper bound, but in practice that's probably not necessary.]

It is easy to verify that the similarity measure is always in the range $[0,1]$ and thus is normalized as you were hoping for.


Computing order statistics $1,2,4,8,\ldots,n$

You can find all of these order statistics in $O(n)$. First, find the maximum (order statistic $2^k$) in time $O(n)$. Then, find the median (order statistic $2^{k-1}$) in time $O(n)$, and remove all larger elements. Find order statistic $2^{k-2}$ in time $O(n/2)$, and remove all larger elements. And so on. The total running time is $$O(n + n/2 + n/4 + \cdots) = O(n).$$