Effiecient Repeat Evaluation of Large Multivariable Expressions

In symbolic computation, hash consing is a technique that consists of systematically remembering the result of function calls in a cache. The cache is indexed by functions and their parameters. Before performing an operation, you look up the call in the cache, and if you find it, you don't perform the function call. Function calls include data constructors, so there is only a single copy of any data structure in memory, and data structures can be compared by physical address. If the computation is highly repetitive, involving many identical parts, this can be a huge performance and memory benefit as it removes any redundancy in computation and memory. If the computation involves little repetition then it's just wasted time doing failed cache lookups and wasted memory for a cache that isn't used.

The same technique can be applied to numerical computations: store all intermediate results in a cache indexed by function calls. I don't know how effective it could be in practice.

As floating point is involved, you need to decide what it means for values to be equal. The most straightforward approach is to use floating point equality; assuming consistent compilation, the same mathematical operation on the same parameters always yields the same result, but you will miss equalities resulting from obtaining the same result in two different ways that are mathematically equivalent (e.g. you may not get the same result for f(x,y) and f(y,x) even if f is mathematically symmetric).


No, unfortunately that doesn't work.  The certificate needs to be a sequence of bits that is verifiable in polynomial time -- and thus the length of the certificate has to be at most a polynomial in the length of the input instance.  If your certificate is the value of some variables, and those values are real numbers, you might not be able to write down their binary representation in any reasonable amount of space (indeed, their binary representation might be infinite-length).

For instance, consider the sentence $\exists x . x^2 = 2$.  This sentence is valid, as $x= \sqrt{2}$ is an example that makes $x^2=2$ true.  However, when you try to write out $\sqrt{2}$ in binary, you get an infinite sequence, so it's not clear what the short certificate would be.  (Certificates need to be of finite length, certainly.)  In general, representing real numbers in binary is messy business; no matter what representation you choose, there will always be some real numbers you can't represent finitely.


What is the asymptotic running time of the following piece of code?

An easy way to intuit asymptotic notations goes like this. Say you have a number $n$ and a constant $c$. Now $n^2$ will always be greater than $n*c$ for any choice of $c$ where $c < n$. So no matter what the constant coefficient is, it will never exceed $n^2$.

Now your question. Asymptotic notations are calculated for sufficiently large values of n where sufficiently large is usually taken as infinity. So although your algorithm has $n^3$ and $n$ time complexities for smaller values of $n$, for large values ($n$ tends to infinity), the time complexity is $n^2$.


Is finding arbitrary length cycles in a graph NP-Hard?

The algorithms mentioned are all fixed-parameter tractable in the size of the cycle.  This means that if you fix the cycle size $k$, there's a polynomial time algorithm for finding the cycle as the number of vertices or edges increases, but the run time still increases exponentially as $k$ increases.  The big-O notation you're looking at only specifies asymptotic run times as the number of edge and vertices increase, but leaves out the possibly large but constant $k!$ factor.


Measures and probability in formal language theory

There is the concept of density of languages (see e.g. here). The density $\operatorname{den}_L : \mathbb{N} \to [0,1]$ of $L \subseteq \Sigma^*$ is defined by

$\qquad \operatorname{den}_L(n) = \frac{|L \cap \Sigma^n|}{|\Sigma^n|}$.

For any fixed length, the density corresponds to the probability of picking a word from the language, assuming we pick uniformly at random. Add a distribution over lengths and you may have what you need.

You may be able to express your concept of "volume" in terms of this notion, maybe by investigating $\lim_{n \to \infty} \operatorname{den}_L(n)$.

As for "randomly picking a language" -- how would you do that? There are uncountably many languages over any given alphabet so I'm not sure how you would define a (nice) probability distribution.


To what does typing correspond in a Turing Machine?

I can't give you a direct answer for automatons, but for functions on numbers.

The untyped lambda calculus corresponds to $\mu$-recursive functions.

For typed systems, it naturally varies for different systems.

An interesting one is System F, also known as the polymorphic lambda calculus. There is a theorem that says that

  A function (on natural numbers) is expressible in System F if and only if it can be proved in the second order Peano arithmetic that the function is total.

This means that in System F you can express basically all imaginable total functions.

There is a bit weaker system, Gödel's System T, for which there is a very similar theorem for first order Peano arithmetic. (However this system is not as nice as System F. In System F you can represent natural numbers, booleans etc. natively, while System T is constructed as the simply typed lambda calculus with externally added naturals and booleans. Also System F has type polymorphism, which makes it much more elegant in many cases.)

See also:

Girard, Lafont and Taylor, Proofs and Types. Cambridge University Press, 1989, ISBN 0-521-37181-3.
Is there an always-halting, limited model of computation accepting $R$ but not $RE$?


Complexity of a decision problem: system of linear equations over finite field with restricted solutions

You can reduce 1-IN-3 SAT to your problem (an instance is a 3CNF, and we want to find a satisfying assignment having exactly one satisfied literal per clause), assuming $p \geq 3$.
A clause $x \lor y \lor z$ is encoded as the constraint $x+y+z=1$.
A clause $\bar x \lor y \lor z$ is encoded as the constraint $1-x+y+z = 1$; and so on.
When $p = 2$, your problem becomes easy.


Proof that circuit design problem is NP-hard

If all clauses have the form $y_i \lor y_j \lor (y_k \oplus y_l)$, your problem is in P: simply setting all of the $y_i$ to 1 will satisfy all of the clauses, always.  Therefore, it's unlikely to be NP-complete, and you're unlikely to find a reduction from 3SAT (well, unless P=NP).

But if you additionally allow some clauses to take the form $y_i \oplus y_j$, then your problem becomes NP-complete.  This follows from Schaefer's dichotomy theorem plus a reduction to double the number of inputs (to enable one to express negated literals); or you can find a direct reduction.


The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows.

The absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a shortest path tree connecting $v$ to all vertices in $V$. It holds that $T(a)$ is a minimum diameter spanning tree of $G$, where $a$ is an absolute 1-center of $G$. Here, if the absolute 1-center is an edge, we subdivide it to obtain the vertex $a$ from which $T(a)$ is then computed from.

An absolute 1-center $a$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $T(a)$ is computed by any standard shortest path algorithm.


A repository for max flow and mincut datasets

To test correctness: the set of edges belonging to a min-cut is not unique in general, so a dataset like you ask would not really be helpful, apart from checking that the value of the cut is the right one. However, it is easy to check correctness yourself by using the output of your algorithm if you compute both the max-flow and the min-cut; just check that the first is a valid flow, the second is a valid cut, and that their value is the same. By the max-flow/min-cut theorem, they must then both be optimal.

To test speed: it's pretty old (1990-91), but you may want to have a look at the archive of the DIMACS implementation challenge on the Maximum Flow problem. It includes many generators and several other codes. For a more modern dataset (1998-2013), here is a collection of Maximum Flow problems arising in computer vision. Also, Andrew V. Goldberg has a page on network optimization software with several useful links (although the Min Cut one seems to be dead).


An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process.
Let's consider the set of sets $A$ as a list $A[i]$.
The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s_0$. And you keep a set $D$ of all indexes you already encoutered.
Then, we loop on other sets to add their information to the set tree. We consider the vertices of the tree starting from the root and adding new vertices when necessary.
let s define a function compare($s$, $v$) with $s$ a set and $v$, the set associated to a vertex of $G$.

if $s == v$ then return true

$c = s \cap v$

if $c == v$ then

for $v_s$ in sons(v) if compare(s-c, $v_s$) then return true
if $s-c \cap D$ is not empty then return false
create a new son to $v$, $v_s$ associated to set $s-c$ and return True

in $G$, develop vertex $v$ to $v_1$ and $v_2$ associated respectively to sets $c$ and $v-c$, return compare($s$, $v_1$)

Thus, the main loop is:

$root = A[0]$
$D = A[0]$
for $s$ in $A[1:]$

if compare(s, root) then $D = D \cup s$
else return false

return true

When reaching the $i^{th}$ set, $G$ contains at most $i-1$ vertices, and you will recursively call the compare function up to $i-1$ times. Thus for $N$ sets covering $L$ different indexes (thus the set operations are $O(L)$), this algorithm solves the problem in $O(L N^2)$
An exemple:
$A = [\{1, 3, 5\}, \{1, 2, 3, 4\}, \{ 1, 2, 3, 6\}, \{1, 2, 3, 5, 7\}]$
the initial tree $T$ has one vertex associated to the set $A[0] = \{1, 3, 5\}$
{1, 3, 5}

then you treat $A[1] = \{1, 2, 3, 4\}$, the root vertex has to be developed in
{1, 3} - {5}

to finally add a $\{2, 4\}$ son vertex to the root:
{1, 3} - {5}
|
{2, 4}

then comes $A[2] = \{ 1, 2, 3, 6\}$, after root, it remains $s = \{2, 6\}$. On $\{5\}$ child, there is no possibility as 2 is already in $D$. But on $\{2, 4\}$ child, it works after developing it.
{1, 3} - {5}
|
{2} - {4}
|
{6}

Finally comes $A[3] = \{1, 2, 3, 5, 7\}$, that will not work as 2 and 5 are both in $D$ and in different branches of $T$.


Is this finite graph problem decidable? What factors make a problem decidable?

Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.

The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly speaking, you need to look a bit further. The problem is a property on the paths in the graph, and there is sometimes an infinite number of paths, when the graph contains a cycle (you can loop around this cycle as many times as you like). However, it's easy to turn the problem to a finite problem: if there is any path beginning with $u$ and ending with $v$ that includes a cycle, then you can cut out all the cycles in that path, and you have a new solution which does not include a cycle. Since there is a finite number of paths that do not involve a cycle (if the graph has $k$ edges, there are at most $k!$ paths that do not use the same edge more than once), the problem of finding a path from $u$ to $v$ is finitary, hence decidable.

Incidentally, this property is called connectivity.

This approach is a common one, called reduction. Given a problem which is not straightforward, we reduced it to a problem we knew how to solve.

It is often difficult to prove that a problem is undecidable. To prove that a problem is decidable, all we need to do is exhibit an algorithm that decides it. To prove that a problem is undecidable, we need to prove that no algorithm can exist. There are a few well-known undecidable problems. In practice, most of the time, when we prove that a problem is undecidable, we show that there is a well-known undecidable problem that reduces to our problem. Since an algorithm for our problem would solve the well-known undecidable problem, our problem must also be undecidable.

You can't really say that “most” problems are decidable or “most” problems are undecidable. In some theoretical sense, almost all problems are undecidable, but we have a strong tendency to tackle “interesting” problems, and those are more likely to have a solution.


Is the following language regular; context-free but not regular; or not context-free?

Denote your language by $L$. Notice that
$$ L \cap 1^*\#0^*1 = \{ 1^n \# 0^n 1 : n \geq 0 \}, $$
which should suffice for showing that $L$ isn't regular.
On the other hand,
$$
L = \{ 0^a1^n \# 0^n 10^b : n,a,b \geq 0 \} \cup
\{ 0^ax01^n \# 0^n1x^R0^b : n,a,b \geq 0, x \in \{0,1\}^* \},
$$
which should suffice for showing that $L$ is context-free.


Textbook for understanding formal grammars

Probably the most-used textbook today is:

Hopcroft, Motwani, & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition).

A couple of other common ones are:

Sipser, Introduction to the Theory of Computation.
Linz, An Introduction to Formal Languages and Automata.

And a couple of older ones:

Michael Harrison, Introduction to Formal Language Theory. Many learned from this 1978 classic. Even though it's older, it has the advantage that you can pick up a very inexpensive used copy from online retailers.
Thomas Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science. It's up to the 3rd edition now, but the first edition was my textbook when I was an undergraduate. The exercises are excellent, but it's light on examples.


Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates

Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \land y)$.

The main observation is that if the function is monotone, you can remove all the negated literals (why?). Once you do that, you get a formula for the function which uses only AND and OR. Some clauses in this formula subsume others (for example, $x$ subsumes $x \land y$). If you drop all the subsumed clauses, you arrive at the minterm representation of the function. (A minterm is a minimal satisfying assignment.)

It's a bit more confusing, but you can also do everything using CNFs. This way you arrive at the maxterm representation.


The main difference between the pumping lemma and Myhill–Nerode theory is that the non-regularity criterion of Myhill–Nerode theory always holds for non-regular languages, whereas the same isn't true for the pumping lemma.

In other words, both the pumping lemma and Myhill–Nerode theory give you conditions which imply that a given language is not regular. If a language is not regular, then it is guaranteed that the Myhill–Nerode criterion will hold, but it is not guaranteed that the pumping lemma condition will hold. You can see an example in this question.

There are extensions of the pumping lemma which are guaranteed to work:

Jaffe's pumping lemma: a language $L$ is regular iff all long enough words $w \in L$ can be decomposed as $w = xyz$, with $y \neq \epsilon$, such that for all $i \geq 0$ and all words $v$,
$$xyzv \in L \text{ iff } xy^izv \in L.$$
Block pumping lemma: a language $L$ is regular iff there exists a constant $k$ such that for all words $u,v,w_1,\ldots,w_k$ there are $1 \leq i < j \leq k$ such that for all $\ell \geq 0$,
$$
uw_1\ldots w_k v \in L \text{ iff } u w_1 \ldots w_i (w_{i+1} \ldots w_j)^\ell w_{j+1} \ldots w_k v \in L.
$$

In both cases, it in fact suffices to allow only $i = 0$.

(This material is from Handbook of Formal Languages, Volume 1: Word, Language, Grammar, Chapter 4 by Sheng Yu, Section 4.1.)


Welcome to the Computer Science Stack Exchange.
We have two subjects in search algorithms: Exploration and Exploitation. Now, Random Restart increases Exploration in your search.
There is no guarantee that random restarts help you to find better solutions. But it will give you this chance to search the space solution better.
So, The answer to your question is that random restart doesn't necessarily help us get unstuck. According to the above facts, (a) is wrong. Between the other choices, I pick the last one (d). I think random restart doesn't belong to informed and uninformed search.


Designing context free grammar for a language with range restriction on repetition of alphabets

It has been a while, since I have done context-free grammars, but I think this should be the answer:

$\qquad \displaystyle A \to 0A11 \mid 0A111 \mid \varepsilon$

I am assuming that empty string is in $L$.

The idea behind is, that you are working your way from outside. Since you need at least 2 times more of $1$'s, than you need $0$'s, you need the first rule. The upper limit is handled with the second rule. All cases inbetween are also covered. $-$ is needed for termination.


Learning a small disjunction using an input distribution of our choice

$\Theta((k+1) \lg n)$ pairs are sufficient.  I think this is the best that's achievable.

Here's the distribution $D$ that achieves this result.  Let $p = 1/(k+1)$ and choose each bit of $x$ from Bernoulli(p) (i.i.d.), i.e., each bit of $x$ is $1$ with probability $p$ and $0$ otherwise.

Call $x$ good if $f(x)=0$.  Note that if $x$ is chosen according to $D$, it has probability $(1-p)^k$ of being good.  This is $(1-1/(k+1))^k$, which is approximately $e^{-1}$ (using the standard approximation $(1-y)^z = e^{-yz}$).  So, $\Pr[f(x)=0] \approx 1/e$, and about a constant fraction of pairs are good.

Now we can take all of the good pairs we have, and look for bit positions that are consistently zero in every good pair.  If we have enough good pairs, only correct positions $i_1,\dots,i_k$ should remain.  Fix a particular incorrect bit position; it has a probability $p$ of being eliminated by each good pair, so the probability that it survives all the good pairs is $(1-p)^g$, where $g$ is the number of good pairs.  Taking $g = -2\lg(n)/\lg(1-p) \approx 2 \lg(n)/p$, we find that the probability of survival for a single incorrect bit position after all $g$ good pairs is $1/n^2$.  By a union bound, this means the probability that any of the incorrect bit positions survive is about $1/n$.  In other words, if we have $2\lg(n)/p$ good pairs, with overwhelming probability this procedure will succeed in correctly inferring $i_1,\dots,i_k$.

Putting these two together, we need about $2e \lg(n)/p$ pairs.  Since $1/p=(k+1)$, this is $\Theta((k+1)\lg n)$.

It's possible to show that this is the best possible value of $p$.  Define $f(p) = p (1-p)^k$.  Then
$$f'(p) = (1-p)^{k-1} (1-(k+1)p),$$
since $f'$ is zero at $p=1/(k+1)$, and one can verify that the maximum value of $f(p)$ on the interval $[0,1]$ is attained at $p=1/(k+1)$.  Now the total number of pairs needed by the above procedure is $2 \lg(n)/f(p)$, which is minimal for $p=1/(k+1)$.  This justifies the choice of $p$ suggested above.

I'd conjecture that you can't do better than this class of distributions $D$ (where each bit of $x$ is chosen iid Bernoulli).  If that is right, then it follows that the result given above is the best possible: $\Theta((k+1)\lg n)$ pairs are necessary and sufficient to solve this problem.


Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?

If you already proved the binary case, a more formal answer is to observe that, for any i, the complement of $L_i$ is r.e. since it is a finite union of r.e. sets. Since the set and its complement are r.e., it is recursive.


Prove a lower bound of 7 vertices:

Since the tree is of height 3, it must have a path of length 3 from the root to a leaf, so we already have to have 4 vertices; $r-v_1-v_2-v_3$.  Now r has to have balance factor in $\{1,0,-1\}$ (i.e. $|\text{BF}(r)|\leq1$) so it must have a path of length at least two on it's other subtree, so we have $r-v_4-v_5$ (at least two more vertices).

For the same reasons (BF) $v_1$ has to have at least one child on it's other subtree, so we have $v_1-v_6$ (at least one more vertex).

So we have proved that an AVL tree of height 3 has to have at least 7 vertices, your example shows that there is an AVL tree with 7 vertices, so the minimum is 7.


Finding paths from the result of max flow

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


Find a 3-colouring using the 3-colourability decision problem

Let the vertices of the input graph $G$ be $\{v_1, \dots, v_n\}$.  First, check if $G$ is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and $b$ to $G$ and add the edges $rb$, $bg$ and $br$. Call this graph $G_0$.  Note that $G_0$ is 3-colourable and, in any 3-colouring of $G_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$ gets, red; call $g$&'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G_1, \dots, G_n$, each of which will be 3-colourable, creating $G_i$ from $G_{i-1}$ as follows.

Set $G_i = G_{i-1} + \{rv_i, gv_i\}$ (i.e., the graph made by adding edges $rv_i$ and $gv_i$ to $G_{i-1}$) if this graph is is 3-colourable. Since $v_i$ is adjacent to both $r$, which is red, and $g$, which is green, $v_i$ must be blue.
Otherwise, set $G_i = G_{i-1} + \{gv_i, bv_i\}$, if this graph is 3-colourable. In this case, $v_i$ must be red.
Otherwise, set $G_i = G_{i-1} + \{bv_i, rv_i\}$.  Since $G_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v_i$ blue or red, $v_i$ must be green.

The above procedure produces a 3-colouring of the $n$-vertex graph $G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.


Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

The three languages you ask about are not very interesting:

$L_1$ is famously not context-free; it's usually written as $\{ ww \mid w \in \Sigma^* \}$. Note that the condition $|w_1| = |w_2|$ is obsolete. Standard entry-level proof techniques work.
$L_2 = \Sigma^+$ since every word $w$ (except $\varepsilon$) can be split into $w_1 = \varepsilon$ and $w_2 = w$; hence it's regular.
$L_3 = \emptyset$ since the two conditions are contradictory; hence it's regular.

As you see, neither gives you any inside into $L$. The languages discussed here are more helpful in this regard.

As for an NPDA for $L$, the answer you link already mentions that there are algorithms to get you from a grammar to an automaton; check a proof that NPDAs and CFGs are equally powerful.

That said, an idea for constructing an automaton from scratch is the same as for the grammar, even though it's a little messier to implement. Let $w$ be the whole input word, and rename $(w_1,w_2)$ to $(u,v)$ to avoid syntax overload. Then:

Note that if $u \neq v$ with $|u| = |v|$, there must be $i$ so that $u_i \neq v_i$. And, importantly, if there is no such $i$ if $u=v$.
Non-deterministically guess two input indices $j, l$  to compare.
Non-deterministicaly guess the middle index $k$ of the input.
Use states to verify that $w_j \neq w_l$.
Use states to verify that $|w|$ is even.
Use the stack to verify that $k = |w|/2$.
Use the stack to verify that $j = l - k$.
Reject if any of the verifications fail.

The main trick left is how to use the stack for the two checks at once; I'll leave that as an exercise.
Proving that the resulting automaton is instructive about the nature of non-determinism.


How to do supervised learning without knowing the target

It's hard to know what to recommend, without more context.

One possible approach is to use hill-climbing, simulated annealing, or some other form of local search.  A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further improvement is possible.  You can combine with random restarts, or use a more powerful method like simulated annealing.

Alternatively, you could try using something like gradient descent.  Suppose you learn not only whether increasing the parameter will improve the model, but how much it improves it.  If you have this information, you can estimate the gradient at a point, then move in the direction of the gradient, and repeat.  Based on experience with stochastic gradient descent, rather than repeating this many times at a single point and averaging, it's likely to be more effective to do this only once at each point and instead repeat for more iterations of gradient descent (perhaps with a smaller step size).  Basically, because your information is noisy, each step is mostly random and is only loosely correlated with the correct direction, so this does a random walk that is slightly more likely to go in a good direction than a bad direction; after sufficiently many iterations, this should converge to a good solution.  The analysis of stochastic gradient descent shows that in many settings this performs better than trying to compute many votes at a single point, average them to get a very good estimate of the direction to go, and repeat for many fewer iterations.  So, the theory says: take only one vote.  There's no theory to tell you how much to change the parameters (the step size).  Usual practice in the machine learning literature is to treat this as a hyperparameter, try multiple different values (e.g., 0.0001, 0.001, 0.01, 0.1), and see which works best.  Sometimes it may be helpful to start with a large step size and then reduce it after some number of iterations.  There are also heuristic optimizers that try to adaptively adjust the step size, such as the Adam optimizer, but it's unclear whether they help or not.

Another approach is to use Bayesian optimization, which uses machine learning to construct a surrogate model that can predicts how well any set of parameters will perform, and then uses optimization methods on the surrogate model.  See, e.g., Google Vizier for one representative of this approach.

I can't predict which approach is likely to be most suitable to your setting.  That may depend on the number of dimensions (how many parameters you have), the dependence of the metric you care about as a function of the parameters (how nonlinear it is), and what kind of information you receive about any set of parameters.

Related: What solution to apply for finding the optimal parameters?, What is an appropriate global optimization technique for a noisy and expensive function?, Mathematical optimization on a noisy function.


Are these two regular expressions equivalent?

First, an alternative notation (what I usually use, and it is my personal preference) to join two regular expressions is to use '+' instead of $\cup$ which is used to denote a union of two sets. So your regular expression can be written as
$$ u^*v(w + xu^*w)^* $$
or sometimes
$$ u^*v(w \mid xu^*w)^* $$
instead of
$$ u^*v(w \cup xu^*w)^* $$
That pair of parentheses around the second $u$ is redundant and so not needed since the Kleene star operator applies to only $u$ in $xu^*w$, i.e., $xu^*w$ and $x(u)^*w$ denote the same set.


What is the difference between the fundamental matrix and the essential matrix?

Both matrices relate corresponding points in two images. The difference is that in the case of the Fundamental matrix, the points are in pixel coordinates, while in the case of the Essential matrix, the points are in "normalized image coordinates". Normalized image coordinates have the origin at the optical center of the image, and the x and y coordinates are normalized by Fx and Fy respectively, so that they are dimensionless.

The two matrices are related as follows:
E = K' * F * K, where K is the intrinsic matrix of the camera.

F has 7 degrees of freedom, while E has 5 degrees of freedom, because it takes the camera parameters into account. That's why there is an 8-point algorithm for computing the fundamental matrix and a 5-point algorithm for computing the essential matrix.

One way to get a 3D position from a pair of matching points from two images is to take the fundamental matrix, compute the essential matrix, and then to get the rotation and translation between the cameras from the essential matrix. This, of course, assumes that you know the intrinsics of your camera. Also, this would give you up-to-scale reconstruction, with the translation being a unit vector.


Number of nodes at given depth in binary tree

Intuitively, the maximum number of leaves at distance at most $d$ from the root is obtained when all of these leaves are at distance exactly $d$ from the root. Since there are at most $2^d$ nodes at distance exactly $d$ from the root, this suggests that the maximum number of leaves at distance at most $d$ from the root is $2^d$.
We can easily prove this bound formally using Kraft's inequality, which states that
$$ \sum_{\ell} 2^{-d(\ell)} \leq 1, $$
where $\ell$ goes over all leaves, and $d(\ell)$ is the distance of $\ell$ from the root. Kraft's inequality implies that
$$ 1 \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d(\ell)} \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d},$$
from which it immediately follows that there are at most $2^d$ leaves at distance at most $d$ from the root.

The text you quote is less sophisticated. It is bounding the number of leaves at distance at most $d$ from the root by the number of nodes at distance at most $d$ from the root. Since there are at most $2^e$ nodes at distance exactly $e$ from the root, it follows that the number of nodes at distance at most $d$ from the root is bounded by
$$ \sum_{e=0}^d 2^e = 2^{d+1} - 1. $$


Confused about how to exactly determine the complexity of an Algorithm

To prove that an algorithm is in $P$ you basically have two options:

Show how to solve it using a number of operations that is polynomial in the size of the input. This means you have to specify a Turing machine to do it, and prove that each of the operations takes a polynomial amount of time. Alternatively, you would prove that the turing machine spends a polynomial amount of steps in any non-accept/reject state.
Show that your problem can be reformulated as a already-known problem previously proven to be in $P$. Here you have to prove that the reformulation is correct and that it takes polynomial time.


Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

Here are some ideas on how to reduce checking bipartiteness to undirected non-connectivity:

A graph is bipartite iff it has no odd cycles.
Suppose we guess that vertex $v$ participates in a cycle of length $2k+1$. Using a layered graph, we can check whether it is the case using undirected connectivity.
We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

Every graph can be made bipartite by splitting every edge into a path of length $2$.
What happens when we join $s$ and $t$, after splitting the edges?


Confusion with the Running Time of an algorithm that finds duplicate character

When we sum all numbers we get $n(n-1)/2$, which is in the class of functions $O(n^2)$. Make sure that you understand what big O notation is about.

Another way of seeing that this sum is $O(n^2)$ since each summand is at most $n$ and there are at most $n$ summands, so the sum is at most $n^2$.


A survey on ranking keyword search results

There is a research literature on this subject that uses machine learning for ranking; it is often known under the term learning to rank.  I recommend reading the papers on that subject.


Doing induction on recurrences correctly

The error is that $c(n-1)^2 + n^2 = cn^2 - 2cn + c +n^2 \leq (c+1)n^2$, so the constant $c$ is in fact no constant, since it grows with every step.
So you get that when $n$ increases by 1, $c$ also does, so you have $O(n) \cdot n^2$, so $O(n^3)$.


Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

Use the space hierarchy theorem, which is a finite form of the undecidability of the halting problem.


Computer Programs and lambda terms without normal form

A troublesome one unfortunately. When one goes to examine programs there are two main ways to do it

Operationally

This is the sort of obvious approach to analysing a program in the lambda calculus. We give a set of rules for what it means for one program to step to another and then go on to prove things about programs stepping. Here a step is one small tweak to the program. We continue to step until we end up at a value at which point no more steps are applicable. A value in the lambda calculus is just a lambda term.

Now the obvious impact of nontermination is that for any term there is no guarantee that there is a finite number of steps leading it to a value. We can prove useful theorems like "Either a term is a value or there is an applicable step" (a form of type safety) and "A term can only step to at most one unique value" (a corollary of the Church Rosser Theorem). These are all still useful results that justify statements like "there are unequal lambda terms".

Denotationally

Here we're trying to understand the lambda calculus by mapping each term to a particular mathematical object so that the mapping is coherent in some way. Mostly we want it so that $denote(e) = denote(e')$ if and only if $e = e'$. With this theorem in hand we can go on and prove things in the denotation equal and actually generate useful theorems about the lambda calculus.

Here nontermination causes some real pain. We can't just treat lambdas as "normal" math functions because normal math functions terminate. Instead we explicitly model nontermination by dedicating a specific element in our mathematical collection as what nonterminating programs denote to. Then we go on and prove a theorem along the lines that if $denote(e)$ gives that nonterminating object, then $e$ doesn't run to a value (runs to in the sense of operational semantics).

However the lambda calculus is a pain to denote for a much more fundamental reason though: recursion. The nontermination in the lambda calculus emanates from the fact that the lambda calculus is built on top of this sort of cyclical definition: a lambda term is a function from $A \to A$ where $A = A \to A$. This recursive definition gives us self-application eg $\lambda x. x\ x$ which gives us nontermination.

Building a denotation involves building a collection where $$A \cong A \to A$$ which is just absurd if $A$ is a set and $A \to A$ is the normal collection of set-theoretic functions!

Indeed proving that such an $A$ exists was the impetus for a large field in programming language semantics called "domain theory". Dana Scott constructed such an $A$ by cleverly defining $A$ with an ordering relation on it and restricting functions to be continuous with respect to that ordering operation. Even with this the proof is very technical (and cool).


What's the theory behind the operator precedences of common operators?

There is really no theory behind it: operator precedence is a purely human construct.

The reason is that expressions are not linear blocks of text. They are trees. For example, you can represent any arithmetic in Reverse Polish Notation. In a tree, there is no ambiguity. An operator acts on its children, end of story.

Humans are good at reading things linearly, and bad at reading trees hierarchically. So, we write equations and expressions as linear sequences of characters, with rules for parsing, parentheses to imply the tree structure, and operator precedence rules to remove some of the "obvious" parentheses.

One could imagine a system in which 2+3*4 was (2+3)*4. Math works just as well in such a system, and the choice is totally arbitrary. It is simply not the arbitrary choice we happen to use.


This is a classical result of Assouad (Densité et dimension) about dual VC dimension.
Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are shattered, that is, all possible rows appear when we restrict $A$ to the columns in $S$. The dual VC dimension of $A$ is the VC dimension of $A^T$, the transpose of $A$.
Suppose that $A^T$ has VC dimension $2^{d+1}$. Then there is a set $S$ of $2^{d+1}$ rows of $A$ such that when we restrict $A$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $d+1$, then in particular we see the following columns: for each $i$, there is a column which contains the $i$'th bit of the row index. For example, if $d=1$ then we see the following columns:
$$
\begin{matrix}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1
\end{matrix}
$$
Therefore the VC dimension of $A$ is at least $d+1$.
If we take $d = \mathrm{VC}(A)$, then we deduce $\mathrm{VC}(A^T) < 2^{\mathrm{VC}(A)+1}$.


Complexity of 4-coloring a map with constraints

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.


Term for programming languages that read like sentences?

I know of no standard term for that aspect of PL. Maybe you can use "human-readable syntax" or "human-friendly syntax".

In PL theory, we (unapologetically) tend to disregard syntactic issues (e.g., look at LISP), and focus more on language features / semantics / types and more math-y stuff.

I mean: if you asked me what are the main differences between C++ and Python, I would probably spend a long time before mentioning some syntactic difference.

For practical applications, of course, having a more human-centric design that the one offered by pure theory is important. A clean and easy syntax is certainly quite convenient to read and write.

Note that, if a PL pushes this principle to extremes, and employs a syntax which is very close to natural language, it could possibly harm productivity. This is because, natural languages can be quite ambiguous, and when programming you really need to be rigorous. Trying to oversimplify a PL by completely removing the math-y aspects of PL is probably not a good idea.

COBOL is arguably more human-readable than Python, but it's hardly better. x = y+z is simpler than ADD Y to Z GIVING X.


BFS for transforming one word to another

The maximum degree of a vertex is $25n$, since this is the number of words which can be obtained by changing a single character. I'm not sure how you get to $26^n$.

You are writing "$4$ is more than $O(n)$" (where $n=2$). This is completely meaningless, since $O(n)$ stands for a function bounded by $Cn$ for some unknown constant $C$. If you don't know the value of $C$ (in this case, $C=25$) then you cannot possibly determine that $4 > Cn$.


Construct an equivalent NFA for the given regular grammar

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

EDIT : As @rici said, if we apply subset construction to the last automaton, we get this one : (without dead states)

So this is an automaton that matches with $G$.


Type-checking function calls with functional subtyping

Presumably, what Scala does (since you mentioned it) is relax your step 2. It is incorrect to check that the type of $f$ is merely 'of the form' $T → U$ because it is applied. Rather, one should check that the type of $f$ is known to be a subtype of some $T → U$.
In Scala, such subtyping 'facts' can be added by declaration when defining a type. So, arrays are declared to be subtypes of function types. You gave this as:
$$[U] <: \mathsf{Int} → U$$
This is just an axiom that needs to be part of the subtyping check. Scala is actually even more complex than this, but this at least covers the subtyping part.
As Andrej mentioned in the comments, these sorts of arbitrary 'declared' subtyping axioms don't necessarily lead to the nicest behavior (principal types, decidability, etc.). There might be multiple particular strategies that you could replace your steps with to incorporate the change to step 2, and they might have different limitations on what types they can check/infer for various examples.


Finding constants C and k for big-O of fraction of polynomials

It works if the denominator doesn't have negative coefficients. Consider, however,
$$ \frac{x}{x-1}. $$
As $x$ tends to infinity, this is $O(1)$. However, your method would give
$$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$
which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case it is zero, but for an example like
$$ \frac{x}{x-2} = \frac{1}{1-\tfrac{2}{x}} \leq \frac{1}{-1} = -1, $$
the inequality is in fact wrong.

Often when considering $O(f(x))$, we assume that $f(x)$ is always positive. But sometimes it isn't, and then the assumption that we're making is that $f(x)$ is eventually positive. This is not usually explained when big O notation is defined, but it's the reason behind the extra quantifier "for large enough $x$" which appears in the full definition of big O; this quantifier is only needed when $f(x)$ is not always positive but only eventually positive.

The way to fix the argument is now clear. If $f(x)$ is eventually positive, then take some $y$ such that $f(x) > 0$ for all $y \geq x$, and now apply the method. For example, if $f(x) = x/(x-1)$ then any $y > 1$ would do, say $y = 2$. In that case we have
$$ f(x) = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-\frac{1}{2}} = 2 $$
for $x \geq 2$.

More generally, suppose that $f(x) = C p(x)/q(x)$, where $p,q$ are monic polynomials (leading coefficient is $1$) and are eventually positive, and $C > 0$. Then for all $\epsilon > 0$ there is $y$ such that for all $x \geq y$,
$$ (C-\epsilon) x^{\deg p - \deg q} < f(x) < (C+\epsilon) x^{\deg p - \deg q}. $$
(Exercise.)


Does the circuit value problem require only log space in alternating Turing machines

It is a classical result that ALOGTIME=P. You can find a proof in lecture notes of Madhu Sudan. Both the circuit value problem and the monotone circuit value problem are P-complete, and in particular in P, and so can be solved in alternating logarithmic space.

One thing which might be confusing you is that we only measure space on work tapes. Space on the input tape is for free, though this comes at a price: you are not allowed to modify it.


Runtime complexity of a brute force factoring algorithm? (in terms of bits)

It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits.

(When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ repeated divisions, for a total complexity of $O(n^3) = o(2^{\frac{n}{2}} n^2)$.)

Notice that this is the best bound we can get for your question under reasonable hypotheses.
Indeed, if the complexity of dividing two n-bit numbers is also $\Omega(n^2)$ and you apply the brute-force algorithm on a prime $N$:

$$
\sum_{i=2}^{\lfloor \sqrt{N} \rfloor} T(\log N, \log i)
\ge \sum_{i=\lceil \sqrt{N}/2 \rceil}^{\lfloor \sqrt{N} \rfloor} T\left(\frac{1}{2}\log N - 1, \frac{1}{2}\log N - 1\right) = \Omega(\sqrt N) \cdot \Omega(\log^2 N) = \Omega(\sqrt{N} \log^2 N),
$$

where $T(i,j)$ is the time it takes to divide a $i$-bit integer by a $j$-bit integer and I am assuming that $T(i,j)$ is non-decreasing w.r.t. $i$ and $j$.


Estimating the run time of a program according to a given CPU performance

If you determined that the runtime of your code, on a certain computer, is T(N) = N log N + 9N + 55 microseconds, then that equation determines the runtime. Just substitute N into that equation.


How broken is LCG in the case of partial output?

Yes, there are techniques based on lattice reduction that are faster than brute force.  See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to $O(2^{(n - k)/2})$ if $k \ge n/2$: see https://crypto.stackexchange.com/a/10609/351.


Confused about Telescoping/Domain Transformation Question


Relational algebra statement for a query

Hint: A product has the same names in all countries if for every two countries, it has the same name in both countries.


Recurrence formula for a known sequence?

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=00010101$. Then the sequence is
$$ 0111, 11, 1, $$
and so $N = 6$ and the cost is $13$.


Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?

Should I include this algorithm in $\mathbb{P}$?

Yes. Since the algorithm is asymptotically bounded above by $O(n)$ the algorithm is in $\mathbb{P}$.

  If zero $\in O(1)$, . . .

Zero is in $O(1)$.

  . . . so often material I study from doesn't distinguish between Big-O and Big-Theta

big-O pertains to an asymptotic upper bound, where big-Theta pertains to an asymptotic tight bound.

The formal definition: $$f(n) \in O(g(n)) \iff \exists N_0,c\in\mathbb{R}^+ \text{ such that } n>N_0 \implies 0 \leq f(n) \leq cg(n)$$ Also, $$f(n) \in \Theta(g(n)) \iff \exists N_0, c_1, c_2 \in \mathbb{R}^+ \text{ such that } n>N_0 \implies c_1g(n)\leq f(n)\leq c_2g(n)$$

For example, $f(n) = n^2 + 3n \in O(n^3)$ and $f(n) \in O(n^2)$. But, $f(n) \not\in \Theta(n^3)$, yet $f(n) \in \Theta(n^2)$.

We can't use $\Theta(n^{O(1)})$ to describe $\mathbb{P}$, as $O(lg(n))$ isn't in $\Theta(n^{O(1)})$, but is in $O(n^{O(1)})$ (and is in $\mathbb{P}$).


Find a sequence of $n$ integers with $\Omega(n^2)$ inversions

Sorta answered my own question in the comments, so I decided to put this here:

If we take any sequence of $n$ integers, in reverse order like $\{n,n-1,\dots, 2, 1\}$. Then each digit $S[i]$ will have $(i-1)$ inversions, and there are $n$ digits.

Thus $I(n) = \displaystyle\sum_{0}^{n-1} n = 0 + 1 + 2 + \dots + (n-1)$. So the total number of inversions will be $I(n) = \dfrac{n(n-1)}{2}$.

Then see, since $n^2 = O\left(\dfrac{n(n-1)}{2}\right)$, $\dfrac{n(n-1)}{2} = \Omega(n^2) $.

Thus $I(n) \in \Omega(n^2)$, and we have a sequence of $n$ digits with $\Omega(n^2)$ inversions.


What does "higher order address bits" and "lower order address bits" mean?

According to the problem, the address itself is 32 bits long. Some of those bits (the higher order ones, i.e. closer to the msb) are used to identify a page, and some of those bits (the lower order ones, i.e. farther from the msb) are used to identify a word within that page. The question here is, how many bits should be allocated for each part, to ensure you can address as much of your memory as possible.

(The msb is the "most significant bit": the one that has the highest place value. We can't just talk about the "first bit" or the "last bit" because nobody can agree on whether the msb comes first or last. It's a headache for anyone doing network programming.)


Can this language be defined by a Context Free Grammer?

You'll need to "wrap" the Bs in the Cs:

S -> aaC
C -> aCc | B
B -> aBb | ɛ

With that, we have

$L(B) = a^m b^m$,

$L(C) = a^p \cdot L(B) \cdot c^p = a^p a^m b^m c^p$ and

$L(S) = a^2 \cdot L(C) = a^2 a^p a^m b^m c^p = a^{m+p+2} b^m c^p$.


Note that
$$\frac{n!}{(n-100)!100!}<\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)< n^{100}.$$

Thus, your algorithm runs in polynomial time


How does hardware interrupt work on a physical layer

The CPU has specific pins on the outside to detect hardware interrupts.

Take for instance the 6502 used in the Apple II and c64 it has two interrupt pins:
IRQ on pin 4 and  (can be ignored)
NMI on pin 6  (cannot be ignored)

If the signal on pin 6 falls from high voltage to low voltage the CPU will perform a call to the non-maskable-interrupt handler.
It will read the contents of address $FFFE and jump to the 16-bit location contained in that address.
After it's done it will return to where execution was before and resume operation as if nothing happened.

In the interrupt handler the CPU will query its peripherals to find out which one generated the interrupt.
Usually a specific chip is connected to the interrupt pin and that chip can be queried using an INput/OUTput instruction to get the relevant info quickly. On the c64 the CIA 6526 was used.

  Are there specific areas of the CPU that contain addresses for handlers registered by the OS?

You set up the CPU so that it calls a predetermined address when it receives an interrupt.
In early CPU's this address has hardcoded in the chip. In newer chips the system kernel can change the interrupt address using a privileged instruction.

On modern processors this works the same but things are complicated because everything is virtualised.


For 1, suppose that $n = 2^{m+\delta}$, where $m$ is an integer and $\delta \in [0,1)$, and compute how many iterations the loop has.

For 2, it's easy to see that it's $\Theta(n^3)$.

For 3, the "inner" loop is $\Theta(n^2)$. Now suppose that $n = 2^{m+\delta}$ and follow the same procedure as in 1. (For starters, you might want to assume that $\delta = 0$.) You will get $\Theta$ of
$$ n^2 + \frac{n^2}{4} + \frac{n^2}{16} + \cdots = \Theta(n^2). $$


Complexity of solving LP with a non-linear growth in variables/constraints

The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then any generic algorithms must take exponential time, since it has to consider all the constraints.

In some cases it is possible to solve linear programs with exponentially many constraints efficiently. This is the case if there is a separation oracle which, given a variable assignment, outputs a violated constraint (if any). If this can be done efficiently, then the ellipsoid algorithm can solve the linear program efficiently (at least approximately). If your problem is NP-hard then there is (probably) no efficient separation oracle for the dual LP. (Another possible reason for your problem to be hard is that rounding a solution could be hard or, perhaps, impossible.)


Is this a proof that SET COVER is not an NP-hard problem?

Weighting of elements from set $P$ of SET COVER problem can be obtained by solving a system of linear inequalities for a given $\varepsilon$ that involves $\{0,1\}$-matrix $I=[x_i\in P_j]:$ $Iw\geq\varepsilon\sum\limits_{i=1}^mw_i.$ If it is not feasible then $\varepsilon$-DENSE SET COVER is void. Found weighting can be easily removed by repeating elements of $P$ with respect to the weighting but the resulting problem will be the same. Feasible SET COVER could be reduced to dense one for $\varepsilon=\frac{1}{m}$ but generally aforementioned reduction could lead to void dense problem for constant $\varepsilon.$

In the geometric case when VC-dimension is finite the dense problem with constant $\varepsilon$ could be solved in polynomial time due to result of Haussler and Welzl "epsilon-nets and simplex range queries" claiming existence of feasible solution to $\varepsilon$-dense problem of length $$\frac{8d}{\varepsilon}\log\frac{d}{\varepsilon}.$$
Having upper bound on the problem optimum we could solve te problem by brute-force search. Here $d$ denotes VC-dimension.


Interpretation of Backtracking Algorithm Problem - weighted matching

Suppose man $i$ is paired with woman $w(i)$, for $1\le i\le n$.

"The sum of the products of the preferences" is the following number.

$$ P_{1,w(1)}Q_{w(1), 1} + P_{2,w(2)}Q_{w(2), 2} + \cdots + P_{n,w(n)}Q_{w(n), n} $$

One can imagine that each individual product $P_{i,w(i)}Q_{w(i),i}$ quantifies how preferred is the pairing between man $i$ and woman $w(i)$.


How to connect the math of recurrence relations to daily programming concepts

In computer science, recurrence relations are often useful for analyzing the running time of algorithms.  For instance, we might define a function $T(\cdot)$, so that $T(n)$ is the running time when running the algorithm on an input of size $n$.  Often, for many kinds of algorithms, we can write a recurrence relation that expresses $T(n)$ in terms of smaller values, such as

$$T(n) = 2T(n/2) + O(n).$$

This would be saying that the running time to solve a problem of size $n$, is twice the time to solve a problem of half that size (perhaps because we recursively solve the first half and the second half using the same algorithm), plus $O(n)$ more (perhaps to combine/merge their two solutions).

So, the numbers represent running times -- the number of operations the algorithm takes to solve the problem.  You might like to take a look at Reference answers to frequently asked questions and How to come up with the runtime of algorithms?.  Also take a look at algorithms textbooks, especially their chapters on running time analysis and divide-and-conquer algorithms.

The initial condition of a recurrence (e.g., the value of $T(1)$) depicts the running time of the algorithm on a small instance.  Often, for a recursive algorithm, this is the running time of the base case.

In computer science, the sequence we are considering is

$$T(1),T(2),T(3),T(4),T(5),\dots,$$

i.e., the sequence of running times as the input size increases.  If you were to write down the sequence of running times for some algorithm, you might spot a pattern, where each term can be computed by a simple formula of a few previous terms (namely, the pattern indicated by the recurrence relation).  That said, honestly, thinking about this as a sequence might not be the most helpful or intuitive viewpoint (at least, I don't find it to be so); I find it more intuitive to think of $T(\cdot)$ as a function rather than a sequence.  The same mathematics still applies.

Another way to get some intuition is to work through a few examples where recurrences are used to analyze the running time of some simple algorithms.  I think that will also help you get a better intuition of what the mathematical expressions mean and how they relate to the algorithm.


Growth of exponential functions according to the big O notation

You swapped two functions. Notice that:
$$n^{\sqrt{n}} = 2^{\sqrt{n} \log n } = o(2^{\frac{n}{2}})$$.

Once this is fixed, the factorial is in the correct order since very rough inequalities show that
$$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \ge \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n-1 \text{ times}} = 2^{n-1} = \omega(2^{\frac{n}{2}}),$$
and
$$n =  n \cdot (n-1) \cdot \ldots \cdot 2 \le \underbrace{n \cdot n \cdot \ldots \cdot n}_{n-1 \text{ times}} = n^{n-1} = o(n^n).$$

In general, from Stirling's approximation you know that $n! = \Theta( \sqrt{n} \cdot (n/e)^n )$.


How to group thousand of data points for each user

The solution was to use run-length encoding.
Let's say that I have:

The first 10 questions true
The next 24 false
The next 34 unknown

I'd transform it in 10T24F34U.
You can find more info on Wikipedia's Run-length encoding as provided by D.W. in the comments.
The main reason for this solution is to send data via an API. I'm not sure if I'm going to use this algorithm or just rely on the typical compression when sending data to a browser. So that is another possible solution.


Find max flow in a network with all capcities of $\sqrt 2$ and one with 2

First, you can divide all capacities by $\sqrt{2}$ so that all capacities are now $1$ except for a single edge $e'$ which has capacity $\sqrt{2}$.

Call this instance $G$. Create $G_1$ which is a copy of $G$ where the capacity of $e'$ has been replaced with $1$, and find the max flow of this graph, with a value $F_1$.

Now, consider $G_2$ which is also a copy of $G$ where the capacity of $e'$ has been replaced with $2$ and has a max flow of $F_2$.

If $F_2 > F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is an augmenting path in $G_2$ along which you can push $1$ additional unit of flow. This augmenting path necessarily corresponds to an augmenting path in $G$ where you can push $\sqrt{2}-1$ additional units of flow. Thus, the max flow for $G$ is $F=F_1 + \sqrt{2}-1$.

If $F_2 = F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is no augmenting path in $G_2$ along which you can push any amount of flow. This also means that this holds for $F$, as the capacity increase of $e'$ between $F_1$ and $F$ is lower than between $F_1$ and $F_2$. Thus, the max flow for $G$ is $F=F_1$.

(You just need a single search of augmenting path to determine if $F_2 > F_1$ or $F_2 = F_1$ once you have computed the flow for $F_1$)

Then, to get the answer to your original problem, just scale the flow back by multiplying $F$ by $\sqrt{2}$.


Are Turing-recognizable languages closed under intersection?

Indeed, the recursively enumerable languages are closed under union and intersection, but not complement. This is not a contradiction: the formula $A \cap B = \overline{\overline{A} \cup \overline{B}}$ tells that a class closed under union and complement is closed under intersection, but does not tell anything otherwise.

A similar example: the set of finite subsets of $\mathbb N$ is clearly closed under union and intersection, but not complement.


Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$

What I tend to do when it comes to counting with a tape is to go back and forth on the tape, marking the relevant portions of the tape as I'm reading new input.

Example
To recognize the language $0^n1^n$ with a Turing machine (not that you'd need the power of a Turing machine, but for illustrative purposes), you can read the first $n$ $0$s, and then when you read the first $1$, mark that $1$ (write $1'$ in that cell), then go back all the way to the first $0$ and mark that, too (writing $0'$). Then go back to the next $1$ (the one to the right of the cell with the $1'$) and write $1'$, go back to the next $0$ that is not marked, and mark that. When you run out of $1$s to read/mark, you have to go back and make sure that all $0$s have been marked. If this is the case, accept the language. If not, or if any other deviation has occurred during the operation of the machine (e.g. encountered some input symbol other than a $0$ or a $1$, read and marked a $1$ but there were no $0$s left to mark; these are treated like undefined transitions), you must reject the language.

Say you are given the string $0000111$ as input.
After counting two $1$s:

  $0' 0' 0 \,0 \,1' 1' 1\,$

After counting three $1$s:

  $0' 0' 0'0 \,1' 1' 1'$

Now there is one $0$ left that is not marked; reject the language.

For your language, it is simple (but, like the above, pretty tedious) to use this strategy to recognize the language. The variation comes in keeping track of what parts of the previous input to mark, and how to get back to the next input cell to read.

Aside: This can be generalized to multiplication, for example to recognizing the language $0^n1^m0^{n \cdot m}$.


Find the minimum cost of adding the elements of a set (greedy algorithm)

I think the following algorithm can work (and is greedy):

Put all elements in a priority queue
While the priority queue has at least 2 elements, extract the two lowest elements, sum them, then add the sum to the priority queue

It gives a correct order for summing elements to get the minimal overall cost.


A new definition of recursively enumerable set?

Your definition makes no sense because according to it every language is recursively enumerable. Given any $C \subseteq \Sigma^*$, take $B = C$ and $f(x) = x$, the identity function, which is computable. Then $f^{-1}(C) = C$, therefore $C$ is recursively enumerable.

We can fix your definition by observing that the following theorem holds:

  Theorem: A language $A$ is recursively enumerable if, and only if, there is a partial computable $f$ and a recursive set $B$ such that $A = f^{-1}(B)$.

You are close to reinventing the notion of many-one reduction, by the way.


What is it called when you classify words into categories, but not by part of speech?

The name of the classification you are looking for is called Semantic field classification (https://en.wikipedia.org/wiki/Semantic_field). The sort of algorithm you are looking for falls under the category of Statistical Semantic.


A 2-coloring of a cubic graph in which all vertices are good is known as an unfriendly partition. Such a coloring always exists, and the following algorithm finds it:

Start with an arbitrary coloring, say everything is colored blue.
While there exists a bad vertex: pick some bad vertex, and flip its color.

Why does the algorithm terminate? Consider the number of monochromatic edges. Flipping the color of a bad vertex decreases the number of monochromatic edges. Since there are $1.5n$ edges, the algorithm terminates after at most $1.5n$ steps.

In fact, the entire algorithm can be implemented in $O(n)$ time, essentially since every step only affects $O(1)$ vertices. The basic idea is to maintain a stack or queue of bad vertices.


How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?

$L$ is semi-decidable (or, synonymously, recursively enumerable). This can be proven (arguably) more easily by using an NTM which non-deterministically picks an input $w \in \{ 0, 1 \}^\ast$, simulates $M$ on it for at most $|w|^3$ steps, and accepts if and only if $M$ does. The NTM accepts exactly the language $L$ because, if there is no accepting branch of the NTM, then there is also no input $w$ for which $M$ halts in at most $|w|^3$ steps. For a properly written proof, it should also be said the semi-decidability of $L$ follows from the equivalence of DTM and NTM acceptors (remember (semi-)decidability is defined in terms of DTMs, not NTMs!).

Because of the equivalence of DTM and NTM acceptors, the above reasoning indirectly gives you a DTM which accepts $L$. The explicit construction could be picking an enumeration of inputs (e.g., lexicographical order), simulating $M$ on each input $w$ for at most $|w|^3$ steps, and accepting if and only if $M$ does. (Having to argue about the enumeration of inputs might be perceived as "hard" by some, hence why proving with an NTM could be considered "easier".)

A warning, however: $L$ is not decidable. This is because its complement is $\{ \langle M \rangle \mid \forall w: \text{$M$ does not halt for $w$ in at most $|w|^3$ steps} \}$ and, thus, a variant of the complement of the halting problem, which is notorious for not being semi-decidable.


assuming you have a pump length $p$ then there is a string $1^{2x}0^y$ with $p \lt x \le y$ as part part of the language

thus the partition $uvw$ with $\text{length}(uv)<p$ must have $uv$ as all $1$s

this means that your pump string $v$ contains all $1$ which if pumped can create twice as many $1$ than $0$s which is not part of the language. QED


The question "Does it terminate?" isn't well-formed.  You need to define more precisely what you mean by that question before it can be answered.

Is it guaranteed to terminate on all possible execution traces?  No.  There exists an execution trace where it never terminates.
Does it terminate with probability one?  Yes.  If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.
Is the expected number of repetitions until termination finite?  Yes.  If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).

So, the answer to the question depends upon precisely which of those questions you meant to ask.  Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely.  For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness).  Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.


How Does Dynamic Heap Storage Have Something to Do with Heap?

Heap memory and the heap data structure are two different and unrelated things. This really bothered me when I was learning about memory, especially since stack memory was actually a stack. The original use of the word heap in computer science referred to the data structure. However, in the 1970s some authors began to use the word heap to refer to the pool of available memory. This use actually more closely matches the English definition of heap - an untidy collection of things - since heap memory is a messy place to allocate and deallocate memory. The name stuck and now we have multiple meanings for the word heap.


Is there another common name for dominating set in graphs?

No, dominating set is a common name, and I've never seen another name for the definition. You might get luckier if you search for domination number though, that's the size of a minimum dominating set.


Consider the following code snippet:

  for(int i=0;i<n;i++)

  The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

This loop executes $n$ times, not $n+1$ times. The first iteration of the loop has $i = 0$; the second has $i = 1$, and so on, up to the last iteration of the loop $i = (n-1)$. Then let us see what happens after that:

We get to the bottom of the loop  when $i = (n-1)$.
At this point, we jump up to the top and execute i++. So now $i = n$.
Next, we check the loop condition. We see that i < n is false, so the loop condition is false. That means we exit the loop.

So in total, we executed the loop for $i = 0$, $i = 1$, $i = 2$, up to $i = n-1$. That is in total $n$ times.

Your misconception was that the loop is terminated once $i$ gets to $n + 1$; but actually it is terminated when $i = n$, because $n$ is already not less than $n$.

  I know this would not make any difference to the complexity since $O(n+1)=O(n)$, linear time.

That is correct!


Criteria for selecting language for first programming course

I'll throw in my own two cents although I believe this subject is a bottomless pit. Don't get me wrong, I think it's a fascinating question, but probably not one we will solve here to everybody's satisfaction.

In a nutshell, I'd say that the language should do what you want it to do, in a simple and unambiguous a way as possible, and not more.

My own experience comes from tutoring several generations of first and second year students with the Oberon programming language. People who know this language will recognize its influence in my opinions. Note that this language was used to teach "Algorithms and Data Structures". At the time (back then), functional programming and object-oriented design were taught in separate courses as of second year.

Important: Before going into the specifics of any language, however, I would like to emphasize that the most important thing is to be absolutely clear, to yourself and to your students, about what the goals of your course are. Are you teaching programming per se? Or algorithms and data structures? Or software engineering? Before choosing a language, it's worth it to think a moment about where you're going with it. Differences at this level (goals) is what probably, in my opinion, leads to most disagreements on this topic.

The points I consider important may overlap with several things that have already been said, but I believe most end up being subsets of one of the following four:

Simplicity: The students are usually there to be taught programming, algorithms and data structures, and not the features and intricacies of any specific programming language. Wirth used the Einstein quote "Make it as simple as possible, but not simpler" as a guiding principle in the design of Oberon, and there are several other languages out there that do it just as well. Your programming language of choice should be able to implement all the concepts required in your lecture, but should do this with the smallest possible set of features/details. The programming language is usually just the tool, not the goal.
Unambiguity: A close sibling of simplicity, there should be one construct for each concept, with as little overlap as possible. Think of it as there being only one "right" way of implementing every concept. Three different types of loops that semantically all do the same thing? Or fifteen different ways to increment a variable? Not good. This also makes correcting homework or generally just understanding your students' code a lot easier. Your teaching assistants will appreciate it.
Portability: Students will go to class with Linux, Windows and OSX machines, and the programming environment should be as similar (identical) as possible under all three. The results of any program should also be identical. This is another point that the teaching assistants, responsible for marking homework and dealing with questions/problems, will greatly appreciate.
Industry preference: Seriously, we should start worrying about this only if "Industry" itself ever decides what programming language it likes best. Since the invention of computers this has been a constantly-moving target. For the moment, if your students really learn how to program, then it won't be language-dependent. There are, however, some areas where industry manages to agree on a standard, e.g. VHDL for circuit design or SQL for database queries, so this is still a valid point.

Again, how a language fits this list is strongly dependent on what it is you're trying to teach!


Trivial solution to the Continuous Knapsack problem

Briefly, the supply of each material is finite: there is only $w_i$ of material $i$. If $w_i < W$, then you cannot fill the knapsack just with material $i$.

In the continuous (or fractional) knapsack problem, we are given a bunch of materials $1,\ldots,n$. Material $i$ has weight $w_i$ and total value $v_i$. The goal is to pick $\alpha_1,\ldots,\alpha_n \in [0,1]$ such that $\sum_i \alpha_i w_i \leq W$ in a way which maximizes $\sum_i \alpha_i v_i$. Your suggestion of taking $\alpha_i = W/w_i$ (for the best material $i$) is only feasible and optimal if $W = w_i$. If $W > w_i$ then the choice isn't feasible – there is not enough of material $i$. If $W < w_i$, then the choice (probably) isn't optimal, since the knapsack will still have room left.


Languages of cardinality higher than $\aleph_0$

In traditional Formal Language theory, all languages are countable. This is because they're defined as a subset of $\Sigma^*$, so they always contain strings of finite length, meaning we can map them to integers.

We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.

There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$,
can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?

You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.

Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.

For more info, see http://en.wikipedia.org/wiki/Computable_number.

Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.


Computer Security versions of the Halting Problem

What you're looking for is Rice's Theorem, which is a generalized version of Halting Undecidability.

It basically says that any property of a Turing Machine (i.e. any computer program) is undecidable, if it's a property of the behavior of the program (i.e. a property of the language it accepts/produces), as opposed to a particular syntactic feature of the implementation. This holds unless it's a trivial property (always true or always false).

For example, deciding "Does instruction X ever get executed" or "Is a high security value stored in low security memory" are all questions about program behavior.

But things like "does this program contain a for-loop" or "is this program type-correct" aren't behaviors, because there might be equivalent programs which don't have the same values for those properties.
You can phrase a program with a for-loop as using while-loops without changing the behaviour, or you can make a version of a program which behaves correctly but doesn't check under your typing discipline. So these aren't properties of the behavior, they're properties of the particular implementation.


The fastest way to check if a move is a winning move in Tic Tac Toe

Yes, you can do this more efficiently.  If you have a board position and the last move made to get to that position, you can check whether the board position is an end state using the following insight:

The previous board position wasn't an end state.  Thus, if the board is an end state, that can only happen because there's a 5-in-a-row that includes the square where the last move occurred.

So, if the last move was in square $s$, check whether there's a 5-in-a-row that includes square $s$.  There are only 4 directions to check (horizontal, vertical, and both diagonals), and you can check each direction efficiently.


Is the runtime for the general number sieve given in base 10, e or 2?

Wikipedia gives the running time as
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},
$$
where $n$ is the integer being factored. Here $\ln n$ is the natural logarithm (logarithm to base $e$).


For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases

First of all, there are two notions of Kolmogorov complexity, that Li and Vitanyi (in their classic monograph) call algorithmic complexity and algorithmic prefix complexity. Each of them is defined with respect to a universal computer which has a certain property.

Algorithmic complexity $C(x)$ has the property that for every computer $P$, if we denote by $C_P(x)$ the complexity of $x$ with respect to $P$, then $|C(x) - C_P(x)| \leq \gamma_P$, where $\gamma_P$ depends only on $P$. This property is known as universality.

Algorithmic prefix complexity $K(x)$ uses a computer in which the valid programs form a prefix code (a prefix computer), and we only require the universality property for prefix computers.

The actual definitions are slightly more complicated, since we also need to define, at the same time, the notion $C(x|y)$ or $K(x|y)$.

If you want to use some encoding of Turing machines as your definition of Kolmogorov complexity (of either kind), you need to use an encoding which is universal. But the point of Kolmogorov complexity is that which computer you use doesn't matter, since the resulting notions of Kolmogorov complexity only differ by an additive constant.

Finally, the Kolmogorov complexity analog of your "substitution" rule is
$$
K(x) \leq K(x|y) + K(y) + O(1).
$$
In fact, more is true:
$$|K(x|y) + K(y) - K(x,y)| = O(1). $$
This holds for prefix complexity.


This depends on both the processor architecture and the kernel architecture.

Generally speaking, interrupt handlers start with interrupts disabled. This is necessary so that the interrupt handler has room for storage — at a minimum, the interrupt handler needs the exclusive use of a few registers, including the program counter, which the processor must save somewhere (in a set of banked registers).

On some processors, it's possible for an interrupt to be interrupted by another higher-priority interrupt. To give one example that I'm familiar with, on ARM processors, there are two interrupt levels: IRQ (normal interrupts) and FIQ (fast interrupts). Each has their own register bank for the program counter and stack pointer, and their own interrupt vector. An IRQ handler starts with IRQ disabled but FIQ enabled; an FIQ handler starts with both IRQ and FIQ disabled. Thus an FIQ can be triggered in the middle of handling an IRQ.

It's up to the operating system to decide when an interrupt handler will reenable interrupts of the same priority, or interrupts of a different type with the same priority. The longer interrupts are blocked, the longer the latency to handle an interrupt that comes soon after another. In particular, a real-time OS typically needs to reenable interrupts very fast. To give a couple of examples:

FreeBSD's interrupt handlers can be preempted when they are performing a blocking operation (waiting for a lock).
Linux encourages splitting the task of an interrupt handler into two parts: the top half is the actual interrupt handler, and runs with interrupts disabled; the bottom half runs with normal preemption for as long as it needs. Typically the top half exchanges data between hardware peripherals and a preallocated memory buffer, then the bottom half handles all the rest such as communicating with other kernel and userland threads, initiating new hardware I/O, etc.

At the point where an interrupt handler unmasks interrupts, it must be ready to cope: it must not be using any resource that another interrupt handler would thrash. Furthermore, since the interrupt handler hasn't finished its job, there must be some mechanism for the program counter to be saved somewhere; the mechanics of this depends a lot on both the processor and the kernel architecture.


Convert a polygon mesh into a b-spline surface

Without any assumptions on the input mesh, you cannot in general get a single b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also need some fairly significant assumptions about the mesh topology. At the very least, you would want the input mesh to be manifold. (It might be possible to contrive a method for creating a single b-spline that exactly matches an arbitrary polygon mesh except on a set of measure zero, but in many cases the spline would have to be extremely degenerate and overlap with itself in strange ways.)

On the other hand, if you are allowed to use multiple disconnected b-spline surfaces in the output, then the problem is easy.

A degree-1 b-spline surface with a 2x2 control point matrix and no internal knots is just a quadrilateral with bilinear interpolation in the interior. In particular, if you set two adjacent control points to the same location in 3D space, you get a triangle. (c.f. Bézier triangle)

Any polygon mesh can be subdivided into a triangle mesh through well-known methods. Once you have done that, you can just separately convert each triangle into a 2x2 b-spline surface.


Efficient way to check if a graph node's children were visited during traversal

If you can afford more memory, add a field to each node's data containing a count of already visited children. Assuming that you know the number of children, if you update this field each time you visit a child, you will know when all children have been visited.


Which matrix of Q values is being used here?

Reinforcement learning works by bootstrapping, which means that Q values are updated based on previous estimates. Also, MDP's don't generate Q values, just rewards (Q values are long-term estimates of accumulated future rewards). So the answer is option 2: the Q values are obtained by calculating the (negative of the) free energy of the RBM. You use the RBM to calculate the current Q value and use it together with the value from the previous step to update your estimate.
The paper uses the Sarsa algorithm, which means it is on-policy. In other words, it uses only actual performed actions. It means that the values are updated only on the next step $t+1$, where you chose your action $a^{t+1}$. In summary, you use Gibbs sampling to select actions and, on time $t+1$ you update the weights using $s^t, a^t, s^{t+1}$ and $a^{t+1}$.


First of all it seems that google has exaggerated a little bit by shooting the $10000$ years results. It seems that IBM, on his current and most powerful classic super computer, is able to perform the same task in $2.5$ days, saving the entire search space (Hilbert space) on a $250$ petabytes hard drive. This does not mean that google's result is not to be taken into consideration: it is definitely a milestone but it will not change the world as many claim, it will not provide us with stable and multipurpose quantum computers  within a year or two (
to tell the truth, with current technologies it is not even practically possible to get computers with enough qbits and keep them in a consistent state).

Having made this premise, we come to the experiment:

Essentially (and in simple terms, very simple terms)
what they did was to correctly sample from the possible outputs of a $53$ qbits random quantum circuit using a statistical test called linear cross-entropy benchmark and sampling about $5000000$ results in about $200$ seconds. The test was a stochastic triumph.

Some notes:

people (outside the discipline) are going crazy blathering of a proof of $P = NP$ or $BQP = BPP$ and then some...
All these things are false, none of these important open problems have been solved by the experiment.
The real importance of having scalable quantum computers lies in being able to perform simulations of physical systems efficiently, which entails dramatic results in the industrial field: desig of new medicines, design of new materials, etc.
Quantum computers will not spell  the end of cryptography: not all cryptographic methods can be efficiently cracked by a quantum computation and, in addition, we already know post-quantum cryptographic techniques: for example lattice cryptography.


Closure properties of linear context-free languages

For our readers. Linear grammars are close to regular grammars, a single nonterminal at the time, but they may generate letters at both sides $A \to aBb$ with $A,B$ nonterminal, and $a,b$ terminal (or empty). $REG \subset LIN \subset CF$, strict.
Some closure proofs may benefit from another way to define linear languages: as single turn pushdown languages.

Linear languages are closed under union, construction as for context-free grammars $S\to S_1, S\to S_2$. Likewise they are closed under intersection with regular languages.

They are not closed under intersection: $\{ a^n b^n c^m \mid m,n \ge 0 \} \cap \{ a^n b^m c^m \mid m,n \ge 0 \}$.

Hence they cannot be closed under complement, but I would be nice to have a concrete example.

Neither are they closed under concatenation, intuitively because $S\to S_1S_2$ is not a linear structure. Same for Kleene star.

Linear languages have a pumping property which is similar to that of the context-free languages, except that the composition $z = uvwxy$ may additionally be required to have $|uvxy|\le m$, where $m$ is the pumping constant. This is similar to the requirement for regular languages, where pumping may be assumed to be at the beginning. Linear languages also have a linear structure (like finite state computations) but the symbols that are generated first are at both ends of the string. WIth this property it can be easily shown that $K =\{a^nb^n \mid n\ge 1\}^2$ is not linear.

Both regular and context-free are closed under rotation, but linear languages are not: $K$ is the rotation of linear $\{  b^m a^n b^n a^m \mid m,n\ge 1 \}$ (and a suitable regular intersection).

Regular languages are closed under quotient, but linear (and context-free) languages are not. In fact the operation is very powerful: the RE languages are quotients of two linear languages.

On the other hand, they are closed under quotient with regular languages. That follows as they form a full trio (i.e., they are closed under homomorphisms, and inverse morphisms and intersection with regular languages). Consequently/equivalently they are closed under finite state transductions.

Of course, they are closed under reversal.


How to prove T Z = Z for binary representation of natural numbers in Coq

to show that bin_to_nat is the inverse of nat_to_bin I need to prove that T Z = Z

No, you can't prove that T Z = Z because it is false:

Lemma TZ_neq_Z : T Z <> Z.
Proof.
  discriminate.
Qed.

Indeed, distinct constructors of an inductive type always lead to distinct terms.

That doesn't mean you can't prove that bin_to_nat is the inverse of nat_to_bin though.


What's the advantage of "value restriction" over its alternatives?

I'm sure that this isn't the only advantage, but I think the primary advantage is simplicity. This is even identified in the original paper introducing the value restriction: previous solutions all existed, but the complexity of annotations made them undesirable.

The majority of value that people want to give polymorphic types are functions, which are values, and you can "fake it" with thunks for anything that isn't a value.
The language of types is unchanged, so it's easier for the programmer to use. There is no need for extra annotations or types. The users

In "real world" languages, the solutions falls into two categories. ML-style languages use the value restriction, and Haskell-style language use purity and monadic effects. Rust even uses a more restrictive version of the value restriction, where only top-level functions can be polymorphic.

As is common with PL research, there may be many theoretically sound solutions which don't gain traction in popular languages because of their difficulty or awkwardness of use.


Proving non-regularity via syntactic congruence classes?

You want to prove that if $\equiv_S$ has infinite index, then $L$ is not a regular language, or, equivalently that if $L$ is regular, then $\equiv_S$ has finite index. This is an immediate consequence of the following result.
Theorem. Let ${\cal A} = (Q, \Sigma, \cdot, i, F)$ be the minimal complete deterministic automaton of $L$. Then $u \equiv_S v$ if and only if, for every state $q \in Q$, $q \cdot u = q \cdot v$.
Proof. Suppose that $u \equiv_S v$ and let $q \in Q$. Since $\cal A$ is minimal, it is accessible, and there exists a word $x$ such that $i \cdot x = q$. Now, for every word $y$,
$$
xuy \in L \iff xvy \in L,
$$
or, equivalently,
$$
1 \cdot xuy \in F \iff 1 \cdot xvy \in F
$$
that is,
$$
(q \cdot u) \cdot y \in F \iff (q \cdot v) \cdot y \in F
$$
It follows that the states $q \cdot u$ and $q \cdot v$ are equivalent, and hence equal, since $\cal A$ is minimal.
Suppose now that for every state $q \in Q$, $q \cdot u = q \cdot v$. Let $x$ and $y$ be words. Then the following equivalences hold:
\begin{align}
xuy \in L &\iff 1 \cdot xuy \in F \iff ((1 \cdot x) \cdot u) \cdot y \in F \\
&\iff ((1 \cdot x) \cdot v) \cdot y \in F \iff 1 \cdot xvy \in F \\
&\iff xvy \in L
\end{align}
and thus $u \equiv_S v$.


The author of the list that you mention has written a thorough report on the problem of selecting a CRC polynomial, which probably contains the answers to all your questions. See page C-19:

Important to select CRC polynomial based on:

Data Word length
Desired HD
Desired CRC size

Safety-critical applications commonly select HD=6 at max message length

For example, HD-6 detects between 1-6 error bits in the Data Word, so the bigger the HD the better (for the given Data Word length).


Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

This sounds to me like the Knapsack problem where

$z$ is the weight of each item,
$Z$ is the capacity of the knapsack,
$g$ the value of the item, and
$G$ the value to be achieved.

The problem is NP-complete but solvable, using dynamic programming, in pseudo-polynomial time $O(n \cdot W)$ where $W = \max_{(z,g) \in R}(g)$.
You can prove that the Knapsack Problem is NP-complete by reducing from the Subset sum problem.  Indeed, Subset Sum is a special case of Knapsack where $z = g$; The "weight" of each problem is the same as its "value".


How should $\lambda x. \lambda y. f z x y \stackrel{\eta}{=} \lambda x. f z x$ be read?

Applications in Lambda calculus are assumed to be left associative, this means that $f~z~x~y$ is the same as $((f~(z))~(x))~(y)$.

With this is mind eta-conversion makes more sense. Wikipedia says:

  Eta-conversion expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments. Eta-conversion converts between λx.(f x) and f whenever x does not appear free in f.

This means that $\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$ is assumed to be true because $y$ does not change the result of the application $f~z~x$, its value is applied after $f~z~x$ is already evaluated.

You can find out more about eta-conversion by playing with it in the Haskell REPL:

Prelude> let z = 1
Prelude> let f x y = (+) ((+) z x) y
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3
Prelude> let f x = (+) ((+) z x)
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3

As you can se, it is easily possible to leave out a the parameter y without changing the meaning of your program.


Hi there CoderInNetwork,

That ain't an easy question and any advances regarding a good heuristic function would be very welcome. Indeed, I will refer in my answer to Andreas Junghanns' PhD written in 1999 (yeap, 16 years ago and still the current state of the art in the field). You can find it in citeseer:

Andreas Junghanns' PhD

Go to Section 4 and you will see a discussion about a heuristic function. The easiest one comes from a simple observation: every stone has to go to one and only one target location so you have to solve a minimum cost perfect matching in a bipartite graph where one set of vertices is made of the stones and the other one is made of the target locations ---so that there are obviously edges going only from the first set to the second and the goal is to find the minimum assignment of stones to goals. The cost of every edge would be equal to the estimated distance to get to the goal assigned from every stone.

This can be done in $O(n^3\log_{2+\frac{n}{4}}n)$ using minimum cost augmentation ---again refer to Andreass Junghanns' PhD, Section 4.3.3 in page 52.

Even considering that this heuristic can be computed in an acceptable time (after making a good number of code optimizations) note that it does not account for dead locks. This is, it will naively move the stones without considering that either the walls or other stones can lead to unsolvable configurations.

From this observation, Andreas Junghanns introduced the idea of using Pattern Databases (PDBs) for improving this lower bound (see a discussion of their implementation in Chapter 5). At the time of writing his PhD, PDBs were not very well known but they are quite well known nowadays and a lot of progress has been made.

Finally, regarding your question: even if there are only 3 stones, problems can be really difficult to solve (or, at least, to solve optimally if that's what you are aiming for). See Appendix B, page 158, The 61 Kids Problems and you'll see lots of challenging problems. Many of those contain only 3 stones.

Hope this helps,


Data structure to use for a consumable message queue where it's safe for messages to overwrite one another

Sorry, you have to tell us more.  We can't tell you what you should do in case of a failure; that will depend upon the application semantics and the type of a failure.

In general, in the event of a failure of an attempted operation, there are several options:

Retry the operation later.
Treat the failure as permanent.

If you decide you want to retry it later, then the implications of this for other operations depends on the dependencies between operations and the desired semantics.  If operations A and B commute (performing A first then B has the same effect as B then A), and if you try A and it fails, then often you can perform B immediately and then retry A.  If operations A and B don't commute, and you try A first and it fails, then performing B immediately and then retrying A will have different semantics, which might or might not be acceptable depending upon what guarantees you are trying to provide.

Related topics: ACID, database transactions.

Example: Suppose you have a one-level filesystem (with no directories), and the intended semantics are that operations on one file can be performed in an arbitrary order compared to operations on another file (but operations on a single file are performed in the order they were requested).

Then operations A and B commute if they are performed on different files, and they don't commute if they're performed on the same file.  Thus, conceptually you can maintain one queue per file.  When you receive a request to perform operation $O$ on file $F$, append $O$ to the queue for $F$.  Whenever you are free to perform an operation, pick an arbitrary file whose queue is non-empty and try the operation at the head of the queue.  If the operation succeeds, then you can pop it from the queue.  If it fails and you want to retry it later, then you have to leave it at the head of the queue to be retried later.

Such a data structure can be implemented with a hash table of queues. The hash table is keyed on the filename; it yields a queue.  It's easy to implement all the necessary behaviors using this data structure.

I am assuming that there are only two possible outcomes of an attempted operation: success (the operation is performed in full), or failure (and there is no effect: this is the same as a no-op).  If it is possible that an operation can fail partway through without rolling back its effects, so it has a partial effect, then you've got much bigger problems.


Remove range of keys from Binary Search Tree in O(s+h)

It sounds like you almost have an algorithm.
Find the vertex $u$ where the successor of $m$ is stored. Similarly, find the vertex $v$ where $n$ is stored (or its predecessor if $n$ is not in the BST).

Suppose that the range of vertices to delete is not empty (that is, the key of $u$ is smaller than, or equal to, the key of $v$) and let $w$ be the lowest common ancestor of $u$ and $v$.

Proceed as follows:

Walk from $u$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=u$) and whenever $z$ is reached from its left child, delete $z$ and its right subtree. The left subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in red in the left figure. This takes time $O(h + d_u)$, where $d_u$ is the number of deleted vertices.
Walk from $v$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=v$) and whenever $z$ is reached from its right child, delete $z$ and its left subtree. The right subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in blue in the left figure. This takes time $O(h + d_v)$, where $d_v$ is the number of deleted vertices.
You are now left with the task of deleting $w$ (see the figure on the right), which can be done in $O(h)$ time using the standard deletion algorithm (if $w$ is a leaf, delete it immediately, otherwise swap $w$ with its predecessor/successor and then delete it).

The overall time required is then $O(h + d_u + d_v) = O(h + s)$.