Reccurrence for the game of pile of stones

AS I asked for hints only, apart from the hints I have provided one can solve the question with grundy numbers.


Training a neural network by classifying its own output

No, that doesn't seem likely to be a very useful direction.

Neural networks are a form of statistical machine learning.  The premise behind all statistical machine learning schemes -- including neural networks -- is that the instances in the training set need to come from the same distribution as the instances that you will apply the classifer to (i.e., the instances in the test set).

If you artificially generate instances via some arbitrary procedure, they might not come from the right distribution.  That will invalidate the core assumption behind statistical machine learning and may make the classifier perform poorly.

Your approach would only work if we knew that the neural network was able to generate images that come from the right distribution (i.e., the distribution on natural images that you'll want to classify).  But there's no reason to believe that will be the case.  In particular, I suspect it most likely won't be the case.

Or, to put it another way, your approach would only work if we had a way to characterize the probability distribution on natural images and sample from this distribution.  However, this appears to be as hard as building a classifier, or even harder.  So, there is no free lunch.

You might interested in the distinction between discriminative vs generative models.  Standard neural networks are discriminative models, and thus don't provide any (direct) way to generate images.  It is also possible to build generative models, which can generate images.  However, building a generative model is believed to be at least as hard as building a discriminative model, and probably even harder.  So, your proposal amounts to saying: "if I had a generative model, I could use that to build a training set to train a discriminative model".  But if building a generative model is likely even harder than building a discriminative model, so this doesn't seem to help much.  There's no free lunch.

Separately: You don't say how you plan to use a neural network to generate images.  Neural networks are a classifier, so they can classify an existing image, but not generate a new image.  You have to do something special to generate images from a neural network.


The obvious (but perhaps not optimal) solution would be to give it as input to a LP solver.


How does continuous computer vision works?

It depends on what you're recognizing, but I'm familiar with two basic techniques:

Apply the recognition algorithm to each frame of the video.  Be fast enough that you can run on every frame of video.  This is probably the most common approach.
Recognize the object once, in one frame.  Then use motion tracking to keep track of the location of the object in subsequent frames.  In this way, you might be able to run the recognition algorithm (say) once every 10 frames and then use motion tracking to keep track of where it is in the remaining frames.  This has some tradeoffs (some latency to detect the object when it first occurs; fast motion or fast panning can cause loss of the object), but is another possible alternative.


Non-erasing Turing machines and loss of generality

Your definition of non-erasing Turing machine is "not the common one". Turlough Neary nicely summarizes early definitions and results for non-erasing Turing machines:

  Non-erasing Turing machines are a restriction of Turing machines that are permitted to overwrite blank symbols only. Moore [Moo52] mentions that Shannon had proved that non-erasing Turing machines simulate Turing machines, however this result was never published. Shortly after, Shannon proved 2-symbol Turing machines universal, Wang [Wan57] proved 2-symbol non- erasing Turing machines universal. Later, Minsky [Min61] proved the same result as Wang using a different technique. Minsky proved 2-tape non- writing Turing machines were universal and showed 2-symbol non-erasing Turing machines simulate these non-writing machines.

So here it says "overwrite blank symbols only", while you wrote "cannot replace a symbol with a blank unless the symbol under the read head is a blank".

In general, it seems that being non-erasing is not a serious restriction, but the answer here has one reference with results that point in the opposite direction:

  John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.


If you had only one tag, this would become a knapsack problem: in particular, determining whether you could sell all the impressions would be exactly the subset problem.  Therefore, the problem is NP-hard.

A plausible approach to solve it in practice would be to use integer linear programming.


Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?

tl;dr I wrote some solution but realized it is not perfect. Since I didn't want all this typing to go waste I figured I might post my observations here rather than splitting them in the comments.

I think that the problem can be solved for any arbitrary $s,t$ and $x$ in $\mathcal{O}(V+ E)$. In fact we can extend the problem to answer $Q$ queries of the form $(s,t,x)$ with $\mathcal{O}(V+E)$ pre processing and $\mathcal{O}(1)$ per query. I am having trouble completing step 6, but I am pretty sure that it can be done. Someone in the comments may know.

Find all strongly connected components (scc) of the graph using Kosarjau's or Tarjans algorithm. This step will take $\mathcal{O}(V+E)$ time.
Using a hash table, you can check if two nodes belong to the same stongly connected component in $\mathcal{O}(1)$ time.
If two nodes $u$ and $v$ belong to the same strongly connected component, then there exists paths both from $u$ to $v$ and $v$ to $u$.
Now what remains to be checked is if two nodes $u$ and $v$ do not belong to the same strongly connected component, does there still exist a path from $u$ to $v$.
We will modify the given graph $G$ to a new graph $G'$ which we shall call the strongly connected component graph or scc graph for short. In the scc graph, each node corresponds to one strongly connected component in the original graph i.e. we compress all nodes belonging to the same scc to a single node. It can be proven that the scc graph is a Directed Acyclic Graph (DAG for short).
Now our task reduces to check if there exists a directed path between $u$ and $v$ in the DAG. Topological sort can give an ordering such that for any path from $u$ to $v$, $u$ will appear before $v$ in the ordering. Thus we can check if index of $u$ in the topologically sorted sequence of vertices is less than that of $v$ in $\mathcal{O}(1)$ but this method also gives false positives and this is where I am stuck.
I feel that we can augment step 6 with some additional data to complete the algo. One method I was thinking of was to maintain some constant $K$ number of random topological sorts and if the inequality $index(u) < index(v)$ is true for all $K$ sequences then we can conclude with high probability that there is a path from $u$ to $v$.


Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

This is not a problem. You have an infinite tape, so you can store whatever you want on it.
Depending on how explicit your proof should be, consider a few edge cases for defining your transition function:

a.) How does your TM recognize, if all n 1s are gone? The complexity of this depends on the alphabet of the TM, if $|\Sigma| > 2$ it should be easy, else you have to work out a few details.

b.) After you've marked one of the 1s - how do you get back to the next step of your computation?


How many different max-heaps exist for a list of n integers?

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...

You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n_1,n_2$ (see the OEIS entry), clearly  $n_1+n_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose  n_1}$ ways how to distribute the elements. This gives the recurrence

$$ a(n)= {n-1 \choose  n_1} a(n_1)a(n_2).$$


Are all proof techniques which only look at black box behaviour of a TM relativizing?

A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is relativizing if it is of the form
$$\forall A \,.\, \phi(T^A)$$
We say that the statement $\phi$ relativizes. There is no requirement on how such a statement is proved, i.e., we do not assume that we only observe the "black box" behavior of $T$ or anything like that. In fact, it is clear that this cannot be the case, as one can easily prove a relativizing theorem about Turing machines which speaks about how the machine works.

Often we start with a theorem about an ordinary Turing machine, and later we ask whether the theorem relativizes. This just means that we first proved $\phi(T^\emptyset)$, and now we wonder whether the trivial oracle $\emptyset$ could be replaced with an arbitrary one $A$ so that we get $\forall A \,.\, \phi(T^A)$.


Why is DFS considered to have $O(bm)$ space complexity?

It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete $b$-ary tree of depth $m$. We can identify nodes in their tree with words over $[b]$ of length at most $m$. The algorithm operates as follows:

Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).
Pop $1$, and push $11,12,\ldots,1b$ to the stack.
Pop $11$, and push $111,112,\ldots,11b$ to the stack.
$\ldots$
Pop $1^{m-1}$, and push $1^m,1^{m-1}2,\ldots,1^{m-1}b$ to the stack.

At this point, the stack contains

$$ 1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b, $$

for a total of $(b-1)m + 1$ nodes. You can check that this is the pint in time in which the size of the stack is maximized.


Difference between intended interpretation and extended interpretation in first-order logic

You should only care about intended interpretation.  I don't like the concept of the extended interpretation.  The latter is only included to make precise the concept of quantification, but I think it makes things more confusing instead.

Before understanding what an intended interpretation is, you should really know what a model is, and what a language or signature is.  To follow their example:  A language can be consisting of the constants Richard and John, the predicates (the arity in backets) Brother (2), OnHead (2), Person (1), King (1) and Crown (1).  Finally you have the unary function LeftLeg (1).

That was the language, and though we use words as Brother, this should really impose no meaning, we could just as well have written it A.

A model, on the other hand, or what they call an intended interpretation is a domain, together with *interpretations of the above predicates, constants and functions.  Here's an example:

Domain = { Richard, John, Crown, Dog }
Brother = { (Richard, Crown), (Dog, John) }
OnHead = { (Dog, John), (Richard, Dog), (Crown, Richard) } (the crown' on Richard's head, Richard's on Dog's head, Dog's on John's head)
Person = {John, Dog}
Richard = Richard (oops, heavy overloading!)
John = Dog (oops, heavy overloading!)

I didn't complete the definition, but I hope you get the point.  If you put all those above together as a KB, (Domain, Richard, John, Brother, OnHead, Person, etc...), you get your inteded interpretation.

The extended interpretation you should ignore.  Completely.  At least if you understand what $\forall x P(x)$ means for some first order sentence $P$.  And $\exists x P(x)$.


I found this post on stack exchanges CS theory section:

https://cstheory.stackexchange.com/questions/20364/how-to-make-the-lambda-calculus-strong-normalizing-without-a-type-system

It is very similar to what I was looking for.


In a DAG, finding the path with the highest score

Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.


Is Dijkstra's algorithm just BFS with a priority queue?

You can implement Dijkstra's algorithm as BFS with a priority queue (though it's not the only implementation).

Dijkstra's algorithm relies on the property that the shortest path from $s$ to $t$ is also the shortest path to any of the vertices along the path. This is exactly what BFS does.

Or in another perspective: how would Dijkstra's algorithm behave if all the weights were 1? Exactly like BFS.


Considering following array
[5,4,3,2,1]

Now for ascending order, four elements are in incorrect position i.e. 5,4,2 and 1

So according to your logic,
No of swaps = No. of elements at incorrect position - 1 therefore No. of swaps = 4-1 i.e. 3

Now, according to Selection sort,

[5,4,3,2,1] Original Array

1st Pass: [1,4,3,2,5] i.e. 1 swap

2nd Pass: [1,2,3,4,5] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Similarly for Descending order,

Now, according to Selection sort,

[1,2,3,4,5] Original Array

1st Pass: [5,2,3,4,1] i.e. 1 swap

2nd Pass: [5,4,3,2,1] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Hope this helps !


You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets.

The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.

Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A_i$ is
$$ \sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$

Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$

Before we get our final polynomial, we need to count the size of our sets $A_{e}$, and the size of all intersecting subsets.

Observe that $|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$. This is  due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,

$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$

I'm not going to list each 3-set, but they all have the same count. $|A_e \cap A_{e'} \cap A_{e''}| = \lambda$. And Finally, $|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$. Now lets collect our terms and add up.

$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$

Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.


Your answer to B is perfectly fine.

To show that something is LR(1) you should generate the automaton and show it has no conflicts.

Don't forget you have to show that G and G' generate the same language. Luckily this is simple because your removal of rules only involved a finite sub language thus you can exhaustively show equivalence.


NP-Complete is not closed under kleene star

$L$ is $\mathrm{NP}$-complete, so, for any $X\in\mathrm{NP}$, there is a many-one reduction $f_X$ from $X$ to $L$.  Just modify $f_X$ so that it's a reduction to $L'$ instead. Note that $f_X$ already does the right thing unless you have some $w$ such that $f_X(w)\in\{0,1\}$.

Note that the same technique shows that $L\cup S$ is still $\mathrm{NP}$-complete for any finite $S\subseteq \Sigma^*$.


Short answer is yes, you can parallelize $k$-means, essentially as you described.

First, on each processor, you assign points to the centroids closest to them. This part is trivial as long as each processor knows the locations of the centroids.

Next, you compute the new location of the centroids on each processor, and then combine them.
But as Raphael pointed out in his comment, you have to weight the centroids from machine 1 and machine 2.

Let's consider a simple example, and only look at 5 points assigned to one of the centroids $C$. Suppose that machine 1 has points $x_1$ and $x_2$ and machine 2 has points $x_3, x_4$ and $x_5$. If we were dealing with the standard (single processor) version of $k$-means, then the new location of $C$ would be
$$
C' = \frac{1}{5} \sum_{i=1}^5 x_i
$$

The contribution from machine 1 is
$$C_1 = \frac{1}{2} \sum_{i=1}^2 x_i$$

and the contribution from machine 2 is
$$
C_2 = \frac{1}{3} \sum_{i=3}^5 x_i
$$

In order to properly combine the results from the two machines, you just do the algebra:
$$
C' = \frac{1}{5}(2C_1 + 3C_2)
$$

Your stopping condition should be the same as in the standard version of $k$-means.


Prove the halting problem is undecidable using Rice's theorem

Your question contains a few hints at misunderstandings of the fundamentals that would take several pages to address. So let's focus on your final question:

  Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

No. Rice's theorem can only be used to show undecidability of index sets and the (usual) Halting problem can not be expressed as such. For details, see here and here.


You haven't actually augmented the grammar. The augmented grammar has the production $$start\to SL\;\$$$

With that change, state 1 is not a reduction state and there is no conflict.

If you did not intend to augment the grammar, then it is not $LR(0)$, because the language does not have the prefix property. But that's not very useful, so normally we augment grammars, turning the language $L$ into $L\$$, where $\$$ is a symbol not in the the alphabet for $L$. Clearly the augmented language has the prefix property.

There's a reasonable explanation with references on Wikipedia.


Are there deterministic and/or non-interactive zero-knowledge proofs?

Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.

Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies.  See Wikipedia for many references.


Your term is the application $3\ 2\ succ\ 0$, where $succ$ is the successor function.

If you task is to reduce this term to a beta normal form:

First we can observe that for terms $M$ and $N$, the application $MN$ beta-reduces to the $M$-fold application of $N$, which is

in the case of $N$ an operation: the $M$-fold application of the operation $N$ to whatever term $P$ the term $MN$ is applied to; i.e., $MNP$ is $\underbrace{N(N(...N(}_{M\text{ times}} P)))$,
in the case of $N$ a church number: the (church number representation of the) exponentiation of $N$ with $M$; i.e, $MN$ with $M,N$ numbers is $N^M$.

as you can easily verify with simple numbers like $2$ and $3$.

So $3\ 2$ is $2^3$, which beta-reduces to $8$, and $3\ 2\ succ$ creates an 8-fold application of $succ$, which is then applied to $0$.
So your term is the $2^3$-fold = $8$-fold application of the $succ$-function to the number $0$, that is, $\underbrace{succ(succ(...succ(}_{8 \text{ times}} 0)))$, which eventually beta-reduces to the church number $8$, $\lambda fx.f(f(f(f(f(f(f(f(x))))))))$.


There's lots of work in the computer vision community on "shape descriptors".  This might or might not be useful.  See e.g., https://en.wikipedia.org/wiki/Shape_analysis_(digital_geometry), https://en.wikipedia.org/wiki/Shape_context, https://en.wikipedia.org/wiki/Image_moment, https://en.wikipedia.org/wiki/Spectral_shape_analysis.


Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order

The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute.

A real brute force takes exponential time, the number of binary trees, which is equal to the number of nested expressions. See Catalan numbers.


Number of ways to bicolor a graph with some constriants

If you only care about graphs with at most $32$ vertices then just list all possible colorings. They are only a constant number ($2^{32}$). For each of them you can decide in constant time whether it is valid according to your constraints.
If you care about graphs with any number of vertices, then the problem is a generalization of the problem of counting the number of dominating sets in a graph, which is #P-complete even for special classes of graphs.


Space complexity of Travelling Salesman Problem

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space requirements are $O(n\log n)$.

The dynamic programming solution, as mentioned in the comments, uses a table of size $O^*(2^n)$. This is much more memory than the brute force solution, but the complexity is exponential instead of factorial, which is much better.

(The notation $O^*$ means that we ignore polynomial factors.)

In fact, every problem in NP can be solved using polynomial space, using a brute force approach that simply goes over all possible witnesses, and for each of them, verifying (in polynomial time per witness) whether it is a valid witness. This extends the brute force algorithm for TSP.


Is L={0,1}* without strings that start with 00 decidable?

so turns out its decidable because its the regular expression $L = 01(0|1)$*


There's a linear-time algorithm for this problem.  Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$.  This $r_j$ is the maximum possible value of the ratio of sums.

Proof: The ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum_{j \in S} a_{1j} - c a_{2j} \ge 0$.  That's possible iff there exists $j$ such that $a_{1j} - c a_{2j} \ge 0$, i.e., such that $a_{1j}/a_{2j} \ge c$.

As a tip for how you could discover this on your own: play with some examples.  If you try many examples and work out by hand the optimal solution, you might happen to notice the pattern (that the best ratio for the sums matches the largest ratio of columns), and that would give you a hypothesis that you could then try to prove.


Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid

"Schnyder's algorithm" computes an embedding on an $O(n)\times O(n)$ grid. See here for a reference, and see here for a more general treatment that is not behind a paywall. Note that if your initial (topological) embedding is not unique, you can just add edges (while preserving planarity) until the graph becomes 3-connected (or even a triangulation) and then apply some drawing algorithm. Once the layout is computed you simply remove the augmentation.

I want to point out that there is also a different drawing algorithm for the $O(n)\times O(n)$ grid by De Fraysseix, Pach and Pollack. It is based on the canonical order of the planar graph. See here for the reference if the graph is a triangulation, and here for 3-connected planar graphs.enter link description here. These articles are behind paywalls, but the algorithms are standard and you will find lecture notes if you google the keywords. You might also try to check out the handbook of graph drawing for more information.


Partitions of a directed graph - common prey and common enemy partitions

Let $p = p_1,\ldots,p_n$ be a sequence of vertices. We say that this is a +path from $p_1$ to $p_n$ if $n$ is even and $(p_1,p_2),(p_3,p_2),(p_3,p_4),(p_5,p_4),\ldots,(p_{n-1},p_{n-2}),(p_{n-1},p_n)$ are all directed edges. In other words, a +path is one that alternates taking the edges in the "correct" and "wrong" ways, starting with a "correct" and ending with a "wrong". A -path is defined analogously with the directions reversed.

Say that two vertices $p,q$ are +equivalent if there is a +-path from $p$ to $q$. I claim that this is an equivalence relation. Indeed:

The empty +path connects a vertex with itself.
The reverse of a +path from $p$ to $q$ is a +path from $q$ to $p$.
The concatenation of a +path from $p$ to $q$ and a +path from $q$ to $r$ is a +path from $p$ to $r$.

The equivalence classes of this relation are $B_1,\ldots,B_p$. If $x \in B_i$ and $y \in B_j$ have a common out-neighbor $z$ then $x,z,y$ is a +path from $x$ to $z$, so $i = j$. This shows that the $B_i^+$ are distinct, and because every vertex has an incoming edge, they form a partition of the vertex set.

We can similarly define -equivalence, whose equivalence classes are $A_1,\ldots,A_k$, and show that the $A_j^-$ partition the vertex set (since every vertex has an outgoing edge).

Take any $x,y \in B_i^+$, say $(z,x),(w,y)$ are edges for $z,w \in B_i$ (possibly $z = w$) and there is a +path $\alpha$ from $z$ to $w$. It's not hard to check that $x,\alpha,y$ is a -path from $x$ to $y$. Conversely, suppose that $x \in B_i^+$ and $y \in B_j^+$, say $(z,x),(w,y)$ are edges for $z \in B_i, w \in B_j$. If there is a -path $\beta$ from $x$ to $y$ then $z,\beta,w$ is a +path from $z$ to $w$, so that $i = j$. We conclude that $\{B_1^+,\ldots,B_p^+\} = \{A_1,\ldots,A_k\}$, so $p = k$. Similarly $\{A_1^-,\ldots,A_k^-\} = \{B_1,\ldots,B_p\}$.


Is this data structure a hypertree or they are just isomorphic trees?

You can describe what's going on here with the notion of a functor, extending things which you would do naturally with three different types (ints, chars, and floats) to trees over these types.

What you have is in effect only a single tree, e.g.
$$
T = \left\{\mspace{45mu}\begin{array}{c@{}c@{}c}
& (4,a\mspace{-18mu}&,3.5) \\
&/&\backslash \\
&\mspace{-60mu}(3,f,1.0) & (1,y\mspace{-36mu}&,3.1) \\
& &  /&\backslash \\
& &\mspace{-60mu}(4,e,2.3) & (7,f,7.7)\mspace{-60mu}
\end{array}\mspace{50mu}\right\}
$$
and mappings from this tree over tuples, to the trees which are visible by the classes,
$$
A = \left\{\mspace{-10mu}\begin{array}{c}
4 \\
\;/ \;\;\backslash &  \\
\;3 \quad 1 \\
\;~ \quad\; / \;\; \backslash \\
\;~ \quad\;4 \quad7
\end{array}\mspace{-10mu}\right\},
\qquad
B = \left\{\mspace{-10mu}\begin{array}{c}
a \\
\;/ \;\backslash &  \\
\,f \quad y \\
\,~ \quad\; / \;\; \backslash \\
\,~ \quad\;e \quad f
\end{array}\mspace{-10mu}\right\},
\qquad
C = \left\{\mspace{-20mu}\begin{array}{c}
3.5 \\
\,/ \;\;\backslash &  \\
\;1.0 \quad 3.1 \\
\;~ \quad\;\;\;\; / \;\; \backslash \\
\;~ \quad\;\;\;\; 2.3 \quad 7.7
\end{array}\mspace{-10mu}\right\}.
$$
The mappings which carry $T \mapsto A$, $T \mapsto B$, and $T \mapsto C$ can be desribed in terms of the projectors
$$\begin{align*}
\pi_1 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{int} \;, \\
\pi_2 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{char} \;, \\
\pi_3 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{float}
 \;.
\end{align*}$$
Each of these "projector" maps $\pi_j$ can be extended to a mapping on trees, using the tree functor which carries all functions $f: A \to B$ to functions on trees, $\text{Tree}(f) : \text{Tree}(A) \to \text{Tree}(B)$ in the obvious way, preserving the tree structure for any given tree, and applying the function $f$ to each node in the tree. Thus
$$\begin{align*}
A &= \Bigl[\text{Tree}(\pi_1)\Bigr](T), \\
B &= \Bigl[\text{Tree}(\pi_2)\Bigr](T), \\
C &= \Bigl[\text{Tree}(\pi_3)\Bigr](T).
\end{align*}$$
So these trees are just the images of $T$ under projection maps in the natural way; they aren't meaningfully independent of one another, and what the classes do which can only access one of these trees is that they can only access information about $T$ through these projections.


log(n) complexity. Difficulty understanding example

Do you know the Harmonic series (wiki)?

$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = 1 + \sum_{i=2}^{n} \frac{1}{i} \le 1 + \int_{1}^{n} \frac{1}{x} \text{d}x = 1 + \ln n = \Theta(\log n).$$

Similarly, we also have
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum_{i=1}^{n} \frac{1}{i} \ge \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Theta(\log n).$$

The formula above follows from

$$\int_{a}^{b+1} f(x) \text{d}x \le \sum_{i=a}^{b} f(i) \le \int_{a-1}^{b} f(x) \text{d}x$$

when $f(x)$ is non-increasing.


Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?

You're expecting too much to expect there to be a single web page that is somehow always updated with the latest in the research literature on the subject.

Let me teach you how to figure out this information for yourself, instead of relying on someone else to have done it for you.  The general approach is to find one paper on the approximability of your problem; then use Google Scholar to track down related papers.

How do you find one paper on the problem?  Perhaps that web page will show you one, even if it's not the latest on the topic.  Perhaps you can search using Google Scholar to find such a paper.  Perhaps you'll have to try other methods.

Then, how do you find other papers on the subject, to find what is the latest and greatest state of the art?  Read the introduction and related work section of that paper, and it should give you an entryway into previous results.  Also, search for that paper on Google Scholar and find what papers cite it; that should give you an entryway into newer results, and you can scan the title and abstracts of those papers to see if they are relevant.  Then, proceed recursively from each paper you've determined to be relevant.


Finding the point nearest to the x-axis over some segment

The $\log^2(n)$ implies that at each node in the search you probably have to do another search. This gave me an idea. Let's construct a tree from the input data:
$$\text{LeafNode} = \{ x, y \}$$
$$\text{NonLeafNode} = \{ \text{Min}_x, \text{Max}_x, \text{MinYPoint} \}$$

Each node will partition the input space into two non-overlapping ranges. The root node will thus be the complete range of $x$ in the input data with the minimum $y$ value.

Then we define a recursive search function that takes a node and the horizontal line segment and returns either the minimum $y$ or $\text{NotFound}$ condition (for simplicity say the value of $\infty$ represents $\text{NotFound}$).

GlobalMinY = Infinity

search( Node, segment ) -> MinY
    if Node does not overlap segment
        return Inf
    if Node.MinY >= GlobalMinY
        return Inf
    if Node is sub-segment
            GlobalMinY = Node.MinY
        return Node.MinYPoint

    return Min( search(Node.Left), search(Node.Right) )

It's easy enough to construct these tree using a modified merge-sort, so construction time is within the bounds. What I'm having a hard time showing is that the search time is within the required bounds.

Search time: Other than the root node, at each node one of the Left or Right nodes will either be included completely or excluded completely. Only one of them can have a partial overlap. If this is correct the time is $2 \log(n)$ -- from root we do two searchs and each follows only a single path through the tree. I'm not even sure the GlobalMinY optimization is needed.


Algorithm to organize a tournament where the team componentes change each round

Sorry, but there is no solution. (Assuming that all games are 2 vs 2.)

How many matches does each player play?

They play with each other player exactly once, one such player per match, for a total of $n-1$ matches.
They play against each other player exactly once, two such players per match, for a total of $\frac{n-1}{2}$ matches.

This implies $n-1=\frac{n-1}{2}$ and thus $n=1$. But you said $n$ is even. And besides, a single-player tournament would not be interesting.

[EDIT]

The question was now changed to omit the requirement that every other player is a partner at least once. However, it is still not possible.

How many rounds should there be? For every player there are $n-1$ potential opponents. In every round there are $2$ opponents without repetition. Hence the number of rounds is $\frac{n-1}2$. This is not an integer number, because $n$ is even.


Why would this Semidefinite Program be Dual Infeasible?

The original poster seems to misunderstand the distinction between "primal infeasible" and "dual infeasible."

The output from CSDP shows that the problem is primal feasible ($X=0$ is a primal feasible solution) but that the primal problem is unbounded. By weak duality, the corresponding dual problem is infeasible.

If you just want a primal feasible solution and don't care about the primal objective value, then you can get this in a couple of ways:

You can use the "certificate" returned by CSDP.  This is a matrix $X$ such that $X$ is positive semidefinite and $A(X)=0$.  Any positive multiple of this matrix is a primal feasible solution to your SDP.
You can add an additional constraint that causes the objective function to be bounded.  A simple choice would be trace(X)=100.

By the way, it's easy to confirm this using another SDP solver such as SeDuMi or SDPT3 or SDPA.


Is this big O notation format correct? $3^n = 2^{(O(n))}$

Sure, that is a correct notation. It is also a correct statement.
Essentially it is a compact way to say the following:

$\exists c>0, \exists n_0 \ge 0 : \forall n>n_0, 3^n \le 2^{c n} $.

You can pick any $c  \ge \log_2 3$ and $n_0 = 0$.


Is there a faster than O(n^2) solution for Box stacking problem?

This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question:

As in the link, for a box in the input with dimensions $(w_i, d_i, h_i)$, consider all rotations of the box, but maintain the property that the first dimension is always $\ge$ the second dimension. So each input box corresponds to three boxes, and consider all these $3n$ boxes, and sort them in decreasing area of the base (ie. the product of the first two dimensions).

Let this sorted sequence be $(a_1, b_1, c_1), (a_2, b_2, c_2), \ldots, (a_{3n}, b_{3n}, c_{3n})$.

Let $DP[i]$ be the maximum height that you can achieve using the first $i$ boxes in this sequence, such that the topmost box is the $i^{th}$ box. Initially $DP[i] = 0$ for all $i$. The recurrence is

$DP[i] = c_i + \max_{\substack{j < i \\ a_j > a_i \\ b_j > b_i}} DP[j]$

Now, instead of spending $\mathcal{O}(n)$ time to find this optimal $j$, we will do it faster using some data structures. Think of each box $(a_j, b_j, c_j)$ as a point $(a_j, b_j)$ in a 2D plane, which has a value $DP[j]$. Now what we want to find is the point in the rectangle $[a_i + 1, INF] \times [b_i + 1, INF]$ which has the maximum value. Note that we can ignore the constraint $j < i$ because it will be implicitly satisfied from the dimensional constraints.

For this, construct a 2D Segment Tree aka Fenwick Tree (look at the section 'Compression of 2D Segment Tree'), using $a_i$ as the values in the outer Segment Tree, and $b_i$ as the values in the inner Segment Trees. You can also use most other 2D Range Query data structures for this.

You can query for the maximum value in that rectangle in $\mathcal{O}(\log^2{}n)$ time, and once you have computed $DP[i]$, you will have to update that value in all the $\mathcal{O}(\log{}n)$ inner Segment Trees, which would take a total of $\mathcal{O}(\log^2{}n)$ time.

Hence, the problem can be solved in $\mathcal{O}(n\log^2{}n)$ time, and $\mathcal{O}(n\log{}n)$ space.


Your operations correspond to applying a 3-cycle on the input permutation. You can reach the identity by applying 3-cycles iff the input permutation is even. Given the cycle decomposition of the input permutation, it shouldn't be hard to answer your question (though the answer is not immediate).


Thorup : What is the meaning of super distance?

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

"Super" refers to the "$\ge$" relation between $D$ and $d$. In other words, since $D(v)\ge d(v)$ where $d(v)$ is the distance from $v$ to $s$, $D(v)$ is called super distance.

  Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

Correct. It is just a distance that approximates the shortest distance from the source from above, which will become that shortest distance at the time $v$ is moved to $S$, the set of vertices whose distances have been settled.


Consider $G_1$. Strings generated by this grammar could be derived by repeated use of the production $S\rightarrow abS$ followed by one use of $S\rightarrow a$ to eliminate the variable $S$. Consequently, we can generate strings in the language by repeatedly adding $ab$ to the right and ultimately stopping by adding an $a$ to the right:
$$
S\Rightarrow ab\color{red}S\Rightarrow ab\color{red}{abS}\Rightarrow abababS\Rightarrow\dotsm (ab)(ab)(ab)\dotsm a
$$
so we generate strings of the form
$$
\underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ a
$$
which corresponds to the regular expression $(ab)^*a$, so $L(G_1)$ is regular. Note that $G_1$ is a regular grammar, since it's a right-linear grammar, namely one for which all the productions are of the form $A\rightarrow xB$ or $A\rightarrow x$ where $A, B$ are variables and $x$ is a string of terminals.

Grammar $G_2$ is only slightly more complicated. We now have four productions

$S\rightarrow S_1ab$
$S_1\rightarrow S_1ab$
$S_1\rightarrow S_2$
$S_2\rightarrow a$

Now a string of terminals can only be generated by production (1) adding $ab$ to the left (since the grammar is left-linear), followed by zero or more productions (2) adding another $ab$ to the left, followed by production (3) and then production (4) adding $a$ to the left. We then can generate strings
$$
a\ \underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ ab
$$
In a way similar to the above, a regular expression denoting $L(G_2)$ could be $aab(ab)^*$.

Your $G_3$ is not a regular grammar, since in such a grammar, all productions must either be right-linear or left-linear. In $G_3$ the production $A\rightarrow aB$ is right-linear but the production $B\rightarrow Ba$ is left-linear. A regular grammar cannot, by definition, have both right- and left-linear productions.

By the way, $L(G_3)=\{a^nb^n\mid n\ge 0\}$ which you'll soon learn is not a regular language.


How to define a language for an independent set problem of a graph?

A language $L$ describes decision problem $p$ means that $\forall x \in L $ the instance $x$ is a Yes/Accept instance of $p$.

For the independent set problem, we have to define language $L$ such that every $x\in L$ be an independent set of graph $G=(V, E)$.

So one possible way to define decision language for independent set problem is
$$L=\{I\,|\, I\subseteq V ,\,\forall u,v\in I \, (u,v)\notin E\}.$$

If you wish to define the language generally you can write it as
$$L=\{(G=(V,E),I)\,|\, I\subseteq V ,\,\forall u,v\in I \, (u,v)\notin E\}.$$


Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

If you assume that $\mathsf{NP}\neq\mathsf{coNP}$ then any coNP-complete problem gives a counterexample. I would guess that one can refute your conjecture unconditionally.


MIPS Architecture : PC-relative addressing

Branch instructions in MIPS have a 16-bit offset value which is sign-extended to provide offsets between -32768 and 32767 words (-131072 and 131068 bytes). This offset is added to the Next PC value rather than the PC of the branch itself.

Why the NPC is used rather than the PC of the branch is not obvious (to me). This may have been related to the use in the Stanford MIPS project of an assembler which performed the limited instruction reordering for filling the delayed branch slot with a previous instruction. With such a design, the offset for forward branches (i.e., branches with positive offsets, commonly used to implement if-then, conditionally branching over the then clause) would never be changed during the conversion and the offset for backward branches (i.e., branches with negative offsets, commonly used for loops) would only be changed when the delay slot had to be filled with an extra no-op instruction. This might simplify compiler development.

An alternative speculation would be that such slightly simplified the initial implementation where the branch was evaluated in the second pipeline stage when the current PC is the NPC relative to the branch instruction.

A third speculation is that such was considered conceptually cleaner given the use of a delayed branch slot. The offset then becomes relative to the instruction in which the branch is "activated".


How to prove that $n^2$ is not $o(n^2+10^{10}n)$?

One definition $f(n)=o(g(n))$ is that $\lim_{n\to\infty} f(n)/g(n)=0$. If this is the definition you're using, then showing that the limit is $1$ already shows that $f(n)\neq o(g(n))$.

The other definition is that, for every $c>0$, there is an $n_0$ such that $f(n)\leq cg(n)$ for all $n\geq n_0$.  The fact that $\lim_{n\to\infty} f(n)/g(n)=1$ means that, for all $\varepsilon>0$, there is some $n_0$ such that $f(n)/g(n)>1-\varepsilon$ for all $n\geq n_0$ (this is part of the definition of "limit").  So, for all $\varepsilon>0$, we have $f(n)>(1-\varepsilon)g(n)$ for all large enough $n$. This means that, in particular, we do not have $f(n)\leq cg(n)$ for $c=1-\epsilon$, so $f(n)\neq o(g(n))$ by the alternative definition.


Copied from here.
The mathematics
Consider the group  $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices.
Each matrix is a function $f:X\to S$, and element $f\in S^X$.
So, the problem consists of computing the cardinality
$$\left|S^X/G\right|$$
Cycle index polynomial of a group of permutations
For a permutation group $G$ acting on a set $X=\{1,2,3,\ldots,n\}$ define the polynomial
$$Z(G,s_1,s_2,s_3,\ldots,s_n)=|G|^{-1}\sum_{g\in G}\prod_{k=1}^{n}s_k^{c_k(g)}$$
where $c_k(g)$ is the number of cycles of length $k$ in the cycle decomposition of the permutation $g$.
Polya's enumeration theorem tell us that
$$\left|S^X/G\right|=Z(G,s,s,\ldots,s)=|G|^{-1}\sum_{g\in G}s^{c_k(g)}$$
Cycle index of the Cartesian product
In our case, $G$ is the Cartesian product $S_w\times S_h$. In this paper they prove the following formula
$$Z(G_1\times G_2,s_1,s_2,\ldots,s_{n_1\cdot n_2}) = Z(G_1,s_1,\ldots,s_{n_1})\otimes Z(G_1,s_1,s_2,\ldots,s_{n_2})$$
where the product $\otimes$ (In the paper they use the symbol text reference mark) of polynomials is defined by:
If
$$f(x_1,x_2,...,x_m)=\sum a_{i_1i_2\ldots i_m}x_1^{i_1}x_2^{i_2}\dotsm x_m^{i_m}\text{ and }g(x_1,x_2,...,x_n)=\sum b_{j_1j_2\ldots j_n}x_1^{j_1}x_2^{j_2}\dotsm x_n^{j_n}$$
then
$$f(x_1,x_2,\ldots,x_m)\otimes g(x_1,x_2,\ldots,x_n)=\sum a_{i_1i_2\ldots i_m}b_{j_1j_2\ldots j_n}\times\prod_{\substack{1\leq r\leq m\\1\leq s\leq n}}(x_{r}^{i_l}\otimes x_{s}^{j_s})$$
where
$$x_{r}^{i_l}\otimes x_{s}^{j_s} = x_{\operatorname{lcm}(r,s)}^{\gcd(r,s)i_rj_s}$$
Cycle index of the symmetric group
For the case of the symmetric group $S_n$ acting on $\\{1,2,3,\ldots,n\\}$ we have
$$Z(S_n)=\frac{1}{n}\sum_{k=1}^{n}s_kZ(S_{n-k})$$
or explicitly
$$Z(S_n,s_1,s_2,\ldots,s_n)=\sum_{r_1+2r_2+3r_3+\ldots nr_n=n}\frac{s_1^{r_1}s_2^{r_2}\dotsm s_n^{r_n}}{1^{r_1}r_1!2^{r_2}r_2!\dotsm n^{r_n}r_n!}$$
Solution of the problem
Combining the results above we obtain that the number of classes of $w\times h$ matrices on $s$ symbols up to permutations of the rows and columns is
$$N=\frac{1}{w!h!}\sum_{\substack{i\in P(W)\\j\in P(H)}}\frac{w!}{1^{i_1}i_1!2^{i_2}i_2!\dotsm w^{i_w}i_w!}\frac{h!}{1^{j_1}j_1!2^{j_2}j_2!\dotsm h^{j_h}j_h!}s^{\sum_{\substack{a\in i\\b\in j}}\gcd(a,b)}$$
where the outer sums runs over the partitions $i=(i_1,i_2,\ldots,i_w)$ and $j=(j_1,j_2,\ldots,j_h)$ of $w$ and $h$, respectively. This is, $i_1+2i_2+\ldots+wi_w=w$ and $j_1+2j_2+\ldots+hj_h=h$. The inner sums run over the elements $a$ and $b$ of the partitions $i$ and $j$. This is, $a$ takes the value $1$, $i_1$ times, the value $2$ $i_2$ times, and so on and likewise $b$ takes the value $1$ $j_1$ times, the value $2$ $j_2$ times, etc.
Implementation
As seen in the final formula, we need to compute:

Partitions of a number
Greatest common divisors (gcd) of many numbers.
Factorials of many numbers.

For these, we can do:

To compute all partitions one can use the iterative algorithms here.
An efficient way to compute gcd one could use Euclidean algorithm. However, since we are going to need the gcd of all pairs of numbers in a range and each one many times. It is better to pre-compute the full table of gcd all at once by dynamic programming. If a>b, then gcd(a,b)=gcd(a-b,b). This recurrence equation allows to compute gcd of larger pairs in terms of that of smaller pairs. In the table, one has the initial values gcd(1,a)=gcd(a,1)=1 and gcd(a,a)=a, for all a.
The same happens for factorials. The formula will require the factorials of all numbers in a range many times each. So, it is better to compute them all from the bottom up using that n! = n(n-1)! and 0!=1!=1.
The powers of $s$, which are also needed repeatedly in the sum could also be pre-computed.

An implementation in Python could look like this. Feel free to improve it.


Right, except that the constants are actually $1/c_2$ and $1/c_1$.  That is, $$c_1 g(x) \leq f(x) \leq c_2g(x) \Rightarrow \frac{1}{c_2}f(x) \leq g(x) \leq \frac{1}{c_1}f(x)\,.$$
Also, remember that the inequalities only apply for large enough $x$.


Choose an arbitrary language $L$ that is not RE. Denote $L_w=\{w\}$ the language containing a single word $w$. Clearly, $L=\bigcup_{w\in L} L_w$ is a union of infinitely many regular and recursive languages.


Given an input and a program when can you derive the output faster than just running the program?

Here's an example:

for i from 1 to 10000000000
  do nothing
end for
output 1

In general, however, you can't save much. Indeed, the time hierarchy theorem states, roughly speaking, that you cannot simulate a $T(n)$-time Turing machine running in time $o(T(n)/\log T(n))$.


Why can we not read and write to the same address at the same time?

In other models (a distributed architecture, for example, with several processors) you can often do concurrent reads, where two or more processors are able to read a word from memory simultaneously. The problem with concurrent writes is more complicated since you have the possibility of a race condition: if one processor wants to write 31 to a memory location and at the same time another processor wants to write 0 to that location, the behavior of the system might not be predictable so running a program twice might result in two different results. Dealing with this problem can be tricky, as you might imagine. That's not to say it can't be handled, only that it's more complicated.


For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

One way to do it is to construct the tree containing those values:

Explore the BST until you find the root of a subtree that is between the bounds;
Explore the left part of the subtree, and trim branches on the left that have a root $\leqslant node_x$;
Do the same thing on the right for roots $\geqslant node_y$

Each of those steps are done in $O(\log n)$ since the BST is balanced. Once you have constructed the tree, just do a tree traversal (in-order for example) of it. This last step is indeed done in $O(k)$.


Sorting an array of length $n$ with $k$ distinct elements

Consider quicksort with $w$ unique values, where the pivot is taken arbitrarily from the list. In the worst case the pivot will be an extrema (either the minimum or maximum of the list), and so the algorithm will recurse for $w-1$ and 1, and a list of 1 unique value is already sorted.

As the time complexity is linear, $O(n)$, for each pass, and the number of passes is in worst case the number of unique values, $O(w)$, then the time complexity is $O(nw)$, which for constant $w=50$, is $O(n)$


Number of inversions in an array of pairs of integers

You can visualize the problem like so (using a = [1,4,8], b = [5,7,2]):

As you can see, I have sorted a, with each element pointing to a position in b sorted in reverse. All we need to do now is iterate over a, counting how many previous indices were lower than us. We can can compute that with a Fenwick tree, all in $O(nlog(n))$. Here is a python implementation:
import bisect

def query(bit, i):
    ret = 0
    while i > 0:
        ret += bit[i]
        i -= i & -i
    return ret

def update(bit, i, delta):
    while i < len(bit):
        bit[i] += delta
        i += i & -i

def csFindInversions2(a, b):
    assert len(a) == len(b)

    def solve(a, b):
        tmp = sorted(b)
        lut = [
            len(b) - bisect.bisect(tmp, b[i])
            for i in sorted(range(len(a)), key=lambda i: a[i])
        ]
        bit = [0]*(len(a) + 1)
        ret = 0
        for i in lut:
            ret += query(bit, i)
            update(bit, i+1, 1)
        return ret
    return solve(a, b) + solve(b, a)

Note that this solution does not account for duplicates.


So this result pertains to the online mistake bound framework. I found a proof here in Shai Shalev-Shwartz's lecture notes. I'll give a rough sketch of it here for the sake of keeping things self contained.

One way to think of online learning is a game between the learner and an adversarial environment. The environment produces an example $x_t$ at time $t$. The learner then outputs a label $\hat{y}_t \in \{-1,1\}$. Finally the environment outputs the true label of $y_t$ and the learner suffers a mistake if $\hat{y}_t \neq y_t$.

The thing to note for the above bound is that it doesn't matter if the environment switches the true hypothesis mid-game, provided the new hypothesis is consistent with all previous labelings. This is because it would be the same as selecting the new hypothesis in the first place.

Assume the learner is trying to learn some some finite hypothesis class $C$ over an instance space $\mathcal{X}$ with $\text{VCdim}(C) = d$. Let $X = \{x_1, \cdots, x_d\} \subseteq \mathcal{X}$ be a shattered set. At any time $1 \le t \le d$ the environment reveals $x_t$ and the learner outputs $\hat{y}_t$. The environment then selects a new hypothesis $c \in C$ such that $c(x_t) = -\hat{y}_t$ and $c(x_i) = y_i$ for $1 \le i \le t$. There will always exist such a hypothesis $c \in C$ since $X$ is shattered by $C$. So the learner makes at least $d$ mistakes. Since this argument was independent of the learning algorithm it follows that
$$
\begin{align*}
\text{VCdim}(C) &\le \text{Opt}(C).
\end{align*}
$$


Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

You had several questions in there, let's just look at a couple of them, the way I understood you.

  Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard?

Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the statement is not entirely correct).  ("Hardness" means that it is at least as hard as all the problems in the class.  "Completeness" means that it is "hard" and is contained in the class in question., see the reference question [1].)

We do believe that $\textsf{NP} \cap \textsf{coNP}$ is strictly contained in $\textsf{NP}$, and that therefore $L$ cannot be $\textsf{NP}$-hard.

  Could it be that the optimal algorithm for $L$ is exponential?

That could very well be.  Factoring is in $\textsf{NP} \cap \textsf{coNP}$ [2], and we don't believe there exists a polynomial time algorithm for Factoring.

What is the definition of P, NP, NP-complete and NP-hard?
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp


Finding all rows of 2 variables using Gaussian Elimination

If I understand you correctly, you have a matrix $M$ over $GF(2)$ (the field with two elements), and want to find all linear combinations of rows which have weight exactly $2$.

Using Gaussian elimination, you can bring your matrix into echelon form. This makes it easy to determine, for any particular row, whether it is in the span of the rows of $M$. Since there are only $\binom{n}{2}$ many rows of weight $2$, the entire algorithm will run in polynomial time. (It is likely that this can be optimized further.)


Construction of the complement of universal Turing machine - where is the catch?

Let V be a Turing Machine constructed the same way as U but with the final states switched

This construction won't work. This is a pattern in automata theory, by the way: for deterministic deciders, flipping final states provides a new proof for closure against complement. For all others, it usually fails.

Here, observe that your semi-decider $U$ of L is, by definition, of the form:

  Accept after finite time if $w \in L$; loop otherwise.

With your construction for $V$, you get:

  Reject after finite time if $w \in L$; loop otherwise.

This is not a semi-decider for $\overline{L}$!

Intuitively, you can not flip a non-termination; you don't get the result you would flip!


Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything at a problem you want to solve. (The reason a book might talk very specifically about say "probabilistic algorithms" instead of "here's how you solve problem X by using a probabilistic algorithm in combination with this trick, that heuristic and this data structure" is that it wants to keep focus on a specific algorithmic idea and its analysis).

The key point here is that a SAT solver is intended to be used in practice, and this is why it makes sense to combine several algorithmic techniques, data structures, etc. to achieve practical efficiency. Still, in general, no matter what the solver does, it cannot be fast and correct on every possible instance (due to NP-completeness).

To understand why having a fast algorithm for an NP-complete problem allows you to solve other such problems, look up polynomial-time reductions, and read up on NP-completeness. Here, again, it is useful to notice that all of this is perfectly fine in theory, but in practice things might be different (it is not true that "polynomial time" necessarily means "efficient in practice").


Name for value which may only be -1, 0 or 1?

There is no standard name, but the value can be seen as value in the balanced ternary numeral system or as the sign (sgn) function. IMHO, the name Sign() is more appropriate when working with calculations or ordering, the 'balanced ternary' is more appropriate when working with logic. For my purposes, I created a Tri enum in the C# language and, besides others, a generic mapping function with this code:

    // https://en.wikipedia.org/wiki/Sign_function
    public static Tri Sgn<T>( this T value ) where T : IComparable<T> {
        var t = value.CompareTo( default( T ) );
        return t < 0 ? Tri.Negative : t > 0 ? Tri.Positive : Tri.Zero;
    }

And, last but not least, there is the three-valued logic: https://en.wikipedia.org/wiki/three-valued_logic. Values of the 'Tri' type can be used to implement functions for three-valued logic.


Are there any implementations of computability logic?

There doesn't seem to be any implementations of it in any current programming languages. It is rather new (introduced in 2003), so that may be a factor.

The author does define some "systems" that implement it, which are listed in the Wikipedia references. For example, Introduction to clarithmetic I, and a few related articles.

  “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic.

GitHub doesn't reveal anything either.


Please explain linear programming as seen for this load balancing problem

How do you physically characterize the load of a processor, is it equivalent to CPU utilization?

The program is modelling load like this. Whether you feel it's a good way to model load, and whether you can think of any real version of load that works like this is a separate issue.

You are running a storage facility for water. The key "facts" about water are:

It's just water and all water is the same. If I ask you to store a litre of water for me and I come back for it a week later, I don't care if you give me back exactly the same molecules of water: I just want you to give me a litre of water. (Economists call a substance with this property "fungible".)
Water is infinitely subdivisible. If I give you a litre of water, you can split it into any number of smaller quantities, without restriction. (Atoms? Shmatoms!)

OK. In your water storage facility, you have $n$ tanks, each of which can hold an unbounded amount of water (you were sure you only needed one such tank, but the TankCorp salesman was very persuasive). At any particular time, the $i$th tank contains $p_i$ litres of water.  A new customer has just arrived with $L$ litres and you need to decide if you can store that and, if so, what is the best way of doing that.

You'll put $x_i$ litres of water in each of your tanks.  You can choose the value of each $x_i$ however you want but, if you accept the customer, you must store all of his water, which means you must have $\sum_i x_i = L$. Also, TankCorp tanks do occasionally burst so you want to fill the tanks as evenly as possible so that, if a tank does burst, you know it won't be a super-full one: you want the loads in the tanks to be balanced.  This is achieved by making the emptiest tank as full as possible.  Why? Because the total amount of water in all the tanks is fixed so, if one tank has less water in it, you can always make the quantities more equal by taking water from a very full tank and transfering it to the emptiest one.

Your job is to pick values for the $x_i$ to satisfy these constraints. Note that if, at the start of the day, each of your tanks is empty, then the solution is trivial: you just set $x_i = L/n$ for each $i$ and each tank contains the same amount of water.

OK, that's the model.  You can use it to represent any kind of load that resembles the idealized water I described: it must be arbitrarily subdivisible (you can split it between your servers however you want) and fungible (your client don't care which server does any fraction of the work). Literally speaking, that's nothing at all, but we can get a good approximation if we replace "infinitely subdivisible" by "subdivisible a lot".  For example, suppose you're running a web server cluster.  You can't literally divide a burst of a thousand requests between the machines in your cluster in any fraction ("I'll do 4.7 requests on server 1, ...") you want but you can divide it into any number of thousandths, which is close enough.

  i.e. what can I do to find out what the load of my processor is currently having?

I'm not sure what you mean.  This isn't a system for measuring load, it's a system for assigning fractions of jobs to servers so that each server will have about the same load.

  How is the fraction of load $L$ to be distributed determined?

By solving the program!  (I.e., choosing values for the $x_i$ that satisfy the constraints.)

  If $\gamma$ is the minimum final load after $L$, then why do we maximize it? Wouldn't that be equivalent to maximize the left over work to be done?

No, because the total work to be done is fixed. Maximizing the least-busy server means that there's less work for the busiest server to do, so you finish as soon as possible.


Let $b$ be the base of the logarithm. If $T > \max(b^2, 2)$, then $\log T =\log_b T> 2$. So
$$T\log T - (T+\log T) = (T-1)(\log T -1) -1 > 1\times 1 -1 =0$$
i.e., $T+\log T< T\log T$.

So, any function that grows asymptotically slower than $T+\log T$ modulo a constant factor also grows asymptotically slower than $T\log T$ modulo the same constant factor. According to the definition of multiple usages of big O-notation,
$$O(T+\log T)= O(T\log T)$$

Yes, it is true that $O((T+\log T)^{1/n})= O((T\log T)^{1/n})$, where we consider $n$ as a constant.


Let's try to show the contrapositive. Since $\mathsf{NP} \cup \mathsf{coNP} \subseteq \mathsf{P}^{\mathsf{SAT},1}$, the contrapositive states that if $\mathsf{P}^{\mathsf{SAT},1} \subseteq \mathsf{NP} \cup \mathsf{coNP}$ then $\mathsf{NP} = \mathsf{coNP}$. Let us assume, therefore, that every problem in $\mathsf{P}^{\mathsf{SAT},1}$ is both in $\mathsf{NP}$ and in $\mathsf{coNP}$. We would like to show that this implies that $\mathsf{NP} = \mathsf{coNP}$.
We can imagine that the argument will have the following structure:

Come up with some language $L \in \mathsf{P}^{\mathsf{SAT},1}$.
The assumption implies that $L \in \mathsf{NP}$ or $L \in \mathsf{coNP}$.
Use these facts to say something about the relation between $\mathsf{NP}$ and $\mathsf{coNP}$.

Our goal is to show that $\mathsf{NP} = \mathsf{coNP}$, or equivalently $\mathsf{NP} \subseteq \mathsf{coNP}$. This, in turn, is equivalent to showing that $\mathsf{SAT} \in \mathsf{coNP}$. Considering the plan above, what we need is to find a language $L \in \mathsf{P}^{\mathsf{SAT},1}$ such that both $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$ imply $\mathsf{SAT} \in \mathsf{coNP}$.
We can take as $L$ the following language:
$$
L = \{(x,0) : x \in \mathsf{SAT}\} \cup \{(x,1) : x \notin \mathsf{SAT}\}.
$$
Details left to you.


Claimed problems with Lisp dynamic scoping

With fact, the primary problem is with f.  If n is 0, then it works fine.  However, for any other value of n, fact is called with an f of () => n * f().  So when the base case (n = 0) is finally encountered, f is () => n * f().  When f is invoked, f is still () => n * f().  So the call to f results in unbounded recursion with itself.

With incrementer, x will be not be defined when y => x + y is called in your example.  This is because y => x + y does not close over x (because of dynamic, as opposed to lexical, binding), there is no call on the stack that binds x to a value when the closure is invoked, and there is no global / top-level binding for x.


How do I get the solution for a recursion with n! using Master Theorem?

Suppose for simplicity that we only consider $n = 4^k$, and that $T(1) = 1$.

Let us guess that $T(n) \leq Cn!$ (where $C>0$), and try to prove it by induction. For the inductive step we need
$$
16C(n/4)! + n! \leq Cn!,
$$
that is,
$$
16C(n/4)! \leq (C-1)n!.
$$
For the base case we need $C \geq 1$.

Let us write the inductive constraint for $n = 4$:
$$
16C \leq 24(C-1) \Longrightarrow C \geq 3.
$$
This prompts us to choose $C = 3$. For $n \geq 4$ we then need
$$
48 (n/4)! \leq 2n! \Longleftrightarrow \frac{n!}{(n/4)!} \geq 24.
$$
It is easy to check that this always holds – for $n = 16$ it's a simple computation, and for $n \geq 64$ we have $n!/(n/4)! \geq n > 24$.

Intuitively, what is happening here is that $(n/4)!$ is much much smaller than $n!$, and so $T(n) \approx n!$, since all other summands (which you see if you unroll the recursion) are so much smaller.


Can you prevent a man in the middle from reading the message?

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

Yes, they can.

A key exchange protocol like (the "textbook" version of) DH is secure against eavesdropping (i.e., simply observing what is being transmitted on the channel), but completely breaks down against man-in-the-middle (MITM) attacks, as you have stated.

Certificates are an attempt remedy this, but another problem arises: How can you ensure both parties receive the correct certificate? Obviously you cannot just send the certificates over the insecure channel since this is again susceptible to a MITM attack.

The solution is the existence of an alternative, (completely) secure channel. This would be either the two parties meeting in person and exchanging their certificates physically or over some alternative, trusted channel (e.g., over telephone, if it can be trusted).

In computer networks, the alternative channel is usually a public-key infrastructure (PKI). This means your operating system or browser has a set of preconfigured root certificates from which other certificates are signed (and possibly even further certificates using these as intermediate certificates). Hence, when you visit some website, it presents a signed certificate, which is signed using (a chain of) certificates which you already trust. Then, by using this certificate, an authenticated key exchange is possible (e.g., to agree on an ephemeral key to use with ordinary symmetric encryption).


How to calculate combination from given n,r and rank?

I assume that your rank starts at $0$, as this simplifies the code (for me).

The core question you must be able to answer is how many elements there are in a substructure of yours.
So in your example, we're ordering combinations lexicographically so we can use the binomial coeffecient to find how many elements there are of our substructures. We'll first try to find the first element of our combination.

Suppose our first element is $x$, then there are $\binom {n-x}{r-1}$ ways the rest of the elements can be chosen. So how do we find $x$? We repeatedly compare our rank to $\binom {n-x}{r-1}$. Is our rank smaller than this, then we must be in this range of sets. Otherwise we subtract this from our rank to skip these sets and try the next $x$.

Once we have found our $x$, we move on to the second element, etc until we are done. Initially we search with $x = 1$, but we increment $x$ after each element found because we want a strictly increasing lexicographically ordered set.

def binom(n, k):
    if k > n: return 0
    if n - k < k: k = n - k
    r = 1
    for d in range(1, k+1):
        r = r*n//d
        n -= 1
    return r

def derank_one(n, r, rank, x):
    while True:
        size = binom(n - x, r - 1)
        if rank < size:
            return x, rank
        if size <= 0:
            raise ValueError("rank is out of range for this set")
        rank -= size
        x += 1

def derank(n, r, rank):
    x = 1
    result = []
    while r > 0:
        x, rank = derank_one(n, r, rank, x)
        result.append(x)
        r -= 1
        x += 1
    return result

And indeed we find that derank(10, 5, 71) == [1, 3, 5, 6, 7] ($71$ because we count starting from $0$).


Complexity of Solving a System of Polynomial Equations

Solving systems of polynomial equations over the reals is $\exists \mathbb R$-complete by definition, and it is a major open problem whether this complexity class equals PSPACE. See this.


How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments.
Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as
$$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log_3{2})^2.(\log_3n)^2$$
However, this modification will only bring a change of constant in your final solution. So we can safely assume that the original equation had the base of the logarithm as 3.
You have that $k = \log_2(\log_3n+2)$, and you can substitute this at the end to find your answer.


Are NP proofs limited to polynomial length?

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time.

While you could define proofs to exceed a polynomial length, only a polynomial prefix of the proof could be read in polynomial time, assuming the head starts at cell 0 and can move at max one cell to the right in one time unit.


Is there an efficient method to store large DAGs?

Try constructing a reduced ordered binary decision diagram (ROBDD) as described here.
The reducing algorithm removes redundant nodes, and reuses equal subtrees in the decision tree, such that every node is unique.
The memory complexity of a ROBDD is $\mathcal O({2^n \over n})$ as proved here.


Why is heap insert O(logN) instead O(n) when you use an array?

Given your link, you seem to be interested in data structures supporting the following operations:

Create(m): create a new instance with room for m elements.
Size(): return the number of elements currently stored in the instance.
Insert(k): insert an element with priority k.
ExtractMax(): return the maximal priority currently stored, and remove it.

Since Size() is easy to implement in constant time as part of the other operations, I will not discuss it below.

Here are three sample implementations:

Unsorted array:

Create() simply allocates memory.
Insert() simply inserts the element at position i+1, where i is the current number of elements.
ExtractMax() goes over the entire array, finding the maximum; and then "compacts" the array by moving all elements to the right of the maximum one entry to the left.

Sorted array: (your implementation)

Create() simply allocates memory.
Insert() first scans the array to find the proper location for the element, then moves all elements to the right of the intended location one entry to the right, and finally stores the element.
ExtractMax() returns and removes the ith element, where i is the number of elements currently in the instance.

Binary heap:

Create() simply allocates memory.
Insert() and ExtractMax() are described on Wikipedia.

Binary heaps are implemented using "partially sorted" arrays. That is, the order of elements in the array is not arbitrary, but it is also not completely determined. Rather, we are only guaranteed that A[i] ≥ A[2i],A[2i+1]. This freedom allows us to trade-off the running time of the two operations Insert() and ExtractMax().

In all of these implementations, Create() is roughly the same, so to compare the various implementations it suffices to consider the two operations Insert() and ExtractMax():

$$
\begin{array}{c|c|c}
\text{Implementation} & \text{Insert()} & \text{ExtractMax()} \\\hline
\text{Unsorted array} & O(1) & O(n) \\
\text{Sorted array} & O(n) & O(1) \\
\text{Binary heap} & O(\log n) & O(\log n)
\end{array}
$$

Here $n$ is the number of elements currently in the array.

If you perform many Insert() and ExtractMax() operations, a binary heap is likely to be more efficient.

Another operation which you mentioned is

Initialize(A): add to an empty instance the elements in A

You can add support to this operation to all different implementations mentioned above:

Unsorted array: simply copy A to the array. Running time: $O(|A|)$.
Sorted array: copy A and sort the resulting array. Running time: $O(|A|\log|A|)$.
Binary heap: run Insert() for each element of A. Running time: $O(|A|\log|A|)$.

Considering this operation doesn't strengthen the case of your implementation.


Is there any theoretically proven optimal compression algorithm?

Huffman coding is optimal for a symbol-to-symbol coding where the probabilities of every symbol are independent and known before-hand. However, when these conditions are not satisfied (as in image, video), other coding techniques such as LZW, JPEG, etc. are used. For more details, you can go through the book "Introduction to Data Compression" by Khalid Sayood.


Why is there more frequent overflow in normalised Floating Point

In a nutshell: Normalized binary floating point requires the
  mantissa to start with digit $1$. When there is an underflow on the
  exponent, the computation may be saved, at the expense of precision,
  by allowing the mantissa to start with some leading $0$ in what is
  called subnormal or denormalized numbers.

It is always a bit chancy to guess the intended meaning of a statement
without enough context.

I am not sure either of what you means by

  when we adopt a normalised representation, our range is smaller than
    in a unnormalised representation.

With these disclaimers, here is my understanding.

A first point to note is that the meaning of qualifier normalized
depends on context. In scientific notation, wich is close to floating
point, it means that the mantissa is represented with a single
non-zero digit before the decimal point, for example $2.718\times
10^{24}$.

The definition is different in the IEEE standards for floating points.
They specify the number of digits used for the mantissa, with no
leading $0$, and with no decimal point (implying it is immediately
right of the last digit which can be $0$).

One characteristic of normalized binary representation is that the
mantissa (called "significand"or "coefficient" in the IEEE standard).
always start with a digit $1$.  This gives optimal precision with the
mantissa (though the ending $0$'s may not be significant), and can
save one bit, since a leading $1$ that is always present does not need
to be represented.

However the is a provision for representing subnormal numbers
(also called denormal or denormalized) which, as the names
indicates, are not normalized.

When there is a need to represent a number such that it requires an
exponent smaller than the possible minimum, the normalized computation
will cause an underflow exception, which is one of several possible
exceptions.

However, this can be recovered, as smaller values (subnormal numbers)
can be represented in denormalized format. This requires various
tricks as the leading digits of the mantissa can now be $0$ rather
than an implicit $1$. Skipping the details, what this amounts to
is that underflow can be overcome, to some extent, by using subnormal
numbers that have less precision than the normal ones.

Thus if the computation has provision for using subnormal numbers, it
is less likely to be aborted by an underflow. But then one should
watch for the precision which may not be as good as normally expected.


Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$

The description of the PDA is easy:

  Read the input string. if read $b$ and the stack is empty, reject the string. If see $a$, push two $a$ to the stack. If read $b$, pop a value from the stack. Finally, if read the end of the string, it will be accepted.


compressing a set of binary strings with fixed length

Suppose $S$ consists of $m$ strings in $\{0,1\}^n$ and we don't allow query arrows. Any two different sets $S_1,S_2 \subseteq \{0,1\}^n$ of size $m$ respond differently to some lookup query: there must be some $x \in S_1\setminus S_2$, for example, and the lookup of $x$ should succeed in $S_1$ and fail in $S_2$. For this reason, the contents of your data structure should be different for $S_1,S_2$. Since there are $\binom{2^n}{m}$ different choices for $S$, any data structure supporting all of them should have at least $\binom{2^n}{m}$ different settings. In particular, if you use $M$ bits to store it then $2^M \geq \binom{2^n}{m}$. When $m = 2^n/2$, for example, this forces $M \geq 2^n - O(n) = 2m - O(\log m)$.


What can be learned from the weights in a neural network?

It depends. Weights of neural networks can be graphed or visualized for some insight. This is especially useful if the neural network works with visual processing. It is possible to "derive" what low-level inputs to the neural network create particular neurons in higher levels to "fire" by working backwards through the neural network weights— in other words, the problem of finding/deriving the low-level input patterns that maximally excite particular neurons, and graphing the results. A great example of this is the recent breakthrough result by Google in a self-trained visual network that self-organized to find higher-level patterns like cats and human faces, etc. [1],[2],[3]

This is also known as "feature detection" and there is Nobel-prize winning research (1981 Hubel/Weisel) that demonstrates that real brain neurons function in a similar way, to varying degrees. Active research is ongoing/continuing in this area in both biological and artificial systems.

Another way of analyzing neural net weights is to conclude what factors (inputs) affect the neural network and which don't. For example, suppose the neural net is used to predict stock prices and it has various inputs relating to different economic variables such as say GDP, gold prices, DJIA (an index), and interest rates. After the network is trained (successfully!) to predict something (say future prices), one can determine how much effect each one of the input variables has on the final prediction.

Also a determination can be made of basic negative or positive correlation between input and output. In this way neural networks can be used in a manner very similar to statistical techniques like factor analysis.

So the answer is "yes absolutely," but only in the sense that there are different ways to reveal "algorithms" in neural networks via graphical or other "human-readable" representations other than with the typical representation of algorithms, i.e. code. But representing neural network weights in a human-readable way and finding new useful representations is an active area of research.

[1] Google Puts Its Virtual Brain Technology to Work Technology Review

[2] Google’s Artificial Brain Learns to Find Cat Videos
 Wired

[3] How Many Computers to Identify a Cat? 16,000 NYT


What would a language look like in which precise GC was implementable as a library?

I think it is possible to implement a garbage collector in C++ without changing the language itself. But in order to use the garbage collector, one must restrict the programmer from using arbitrary language constructs. In particular, all memory allocation requests must be done through the allocation APIs given by the garbage collector, and all the access must be done through references that is managed by the garbage collector.


DFA for strings with number of 0's odd only in substring longer than 1

I believe your language is not regular and if I'm not mistaken, the pumping lemma suffices:
Let us assume by contradiction your language is regular, thus it should hold all 3 conditions of the pumping lemma.

Let $w=0^{2p+1}111$, notice $w\in L$ because $2n$ is always even, thus by adding $1$ we have an odd number of $0$s.

Now let us take a simple example where $p=1$, but this should work for any $p$.

In this case, $p=1$, notice $|w|>p$, since $|w|=5$, essentially $w=000111$. In our case this means $y=0$ and because $|xy|\le 1$ and because $|y|>0$  where 1 is our pumping length this means $x=\epsilon$.

This leaves $z=0011$. However, for $i=2$, we receive: 000011 which is $y^2z \equiv 000011 $.

Then the number of 0s in your substring is now even, meaning $000011 \notin L$.
Again, we can do this for any pumping length $p$ by simply pumping up or pumping down.

Thus there won't be a DFA/NFA for that. You can try using a TM.

For more information: pumping lemma.


How to prove Q1 and Q2 are equal using state equivalence algorithm

The algorithm is working fine on this DFA. At step 2 you'll get the table as:

  1 2
1 G G
2   G

G is green.

If there is an unmarked pair (Qi, Qj), mark it if the pair {δ(Qi, A), δ (Qj, A)} is marked for some input alphabet. Where A is set of all inputs.

{δ(1, 'a'), δ(2, 'a')} = {2,1} = {1,2}
{δ(1, 'b'), δ(2, 'b')} = {1,2}

{1,2} or {2,1} is not marked. Hence move to step 4, Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

I prefer the method of partitioning for minimizing the DFA. Consider the following DFA
State transition table for the DFA will be:

   0  1
a  b  c
b  a  d
c  e  f
d  e  f
e  e  f
f  f  f

Draw 0 equivalent partitions, by separating final and non-final states in different sets.
[a b f] [c d e]
Draw 1 equivalent partitions, by taking every possible pair from each set and checking whether their transitions on an input symbol belongs to a single set or not. For example {a,b} on 0 goes to {a,b} and it belongs to a single set [a b f], {a,b} on 1 goes to {c,d} which belongs to 1 single set [c d e], hence {a,b} are 1 equivalent. But {a,f} on 1 goes to {c,f} and it doesn't belong to a single set, hence they are not equivalent. So separate them. (you can check for {b,f},{c,d},{c,e},{d,e} as well, result will be the same)
[a b] [f] [c d e]
Draw 2 equivalent partitions, by repeating the procedure and you'll find nothing is changed. Hence final configuration is reached.
Merge [a b] and [c d e]

In your example: 0 equivalent partitions: [q1 q2] 1 equivalent partitions: [q1 q2]

Hence they are combined.


Actually the regular expressions from $q_0$ to $q_2$ and from $q_2$ to $q_0$ seem to be correct, but the loops around $q_0$ and $q_2$ are more questionable. Although they will lead to a correct answer, they could be simpler and I am not sure you applied the algorithm correctly.

If you want to be sure of your answer, I would recommend to use linear equations. This is exactly the same method, but it might be safer. In your case, you have the system
\begin{align}
X_0 &= (a+b)X_0 + (aa + b)X_1 + ab^*X_2 \\
X_1 &= X_0 + ba X_1 + bX_2 \\
X_2 &= (bb + a) X_0 + aX_1 + 1
\end{align}
where $1$ denotes the empty word. You want to eleminate $X_1$. To do this, rewrite the second equation as $X_1 = baX_1 + (X_0 + bX_2)$ and apply the general result that if $1 \notin K$, the unique solution to the equation $X = KX + L$ is $K^*L$. In your case, you get $X_1 = (ba)^*(X_0 + bX_2)$. You now copy-paste this value of $X_1$ in the two other equations (and I really did it this way!) to get
\begin{align}
X_0 &= (a+b)X_0 + (aa + b)(ba)^*(X_0 + bX_2) + ab^*X_2 \\
X_2 &= (bb + a) X_0 + a(ba)^*(X_0 + bX_2) + 1
\end{align}
which leads to
\begin{align}
X_0 &= (a+b+ (aa + b)(ba)^*)X_0 + ((aa + b)(ba)^*b + ab^*)X_2 \\
X_2 &= (bb + a + a(ba)^*)X_0 + a(ba)^*bX_2 + 1
\end{align}
You can now recover the regular expressions if you wish: $q_0 \xrightarrow{a+b+ (aa + b)(ba)^*} q_0$, $q_0 \xrightarrow{(aa + b)(ba)^*b + ab^*} q_2$, $q_2 \xrightarrow{bb + a + a(ba)^*} q_0$, and $q_2 \xrightarrow{a(ba)^*b} q_2$.

A further simplification. You may observe that in your original automaton, you have $q_0 \xrightarrow{a+b} q_0$. This implies that for any word $u$, there is a path $q_0 \xrightarrow{u} q_0$. It means that the transition $q_0 \xrightarrow{a+b+ (aa + b)(ba)^*} q_0$ in the second automaton is redundant and could have been replaced by $q_0 \xrightarrow{a+b} q_0$.


Derivation of implicational propositional axioms

The natural way to define your addition operation is as set intersection. The value of a single axiom is the set of all models satisfying the axiom. The sum of several axioms is then the set of all models satisfying all the axioms.

A similar definition is $\mathbf{A} + \mathbf{B} = \mathbf{A} \land \mathbf{B}$, but then you need to interpret equality as logical equivalence. The definitions then become completely equivalent.

However, you can't "cancel" axioms. If you know that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ then all you can conclude is that in the presence of $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are equivalent. As an example, let $\mathbf{A}$ be $x=0$, let $\mathbf{B}$ be $y=1$, and let $\mathbf{C}$ be $x+y=1$. In the presence of $\mathbf{A}$, the axioms $\mathbf{B}$ and $\mathbf{C}$ are equivalent, but in general they aren't.

If are are really keen on the cancellation law, you can always take formal sums. It is then true that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ implies $\mathbf{B}=\mathbf{C}$, but at the cost of $\mathbf{A}+\mathbf{B}$ having no other meaning than the formal sum of $\mathbf{A}$ and $\mathbf{B}$.


Hamiltonian circuit for a family of graphs

This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).


Minimum cost of wood for woodworking project problem

As D.W. rightly pointed out, it is a generalisation of the knapsack problem. Its closest relative is probably the cutting stock problem, where the goal is to minimise waste.
The cutting stock problem is typically solved using a (quite natural!) translation to integer linear programming. That seems like the best bet for your problem, too.


Polysize bounded depth circuit for modified MAJORITY problem

This task is known as approximate counting or approximate majority. The first to construct such a circuit was Ajtai in his celebrated 1983 paper $\Sigma_1^1$-formulae on finite structures, which also proves the first switching lemma. You can check out Section 3 for the construction. For a more modern account, see Section 2 of Viola's Randomness buys depth for approximate counting.


how do I simplify this particular boolean expression?

We can do it by brute force, expanding all 108 product terms and combining like terms carefully. Many of the terms can be eliminated immediately.

In hindsight or by luck or by sharp observation that D and E appear most frequently, we can proceed as follows.

  $(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)$

Let $D=1$ and $E = 1$. The formula becomes 11111 = 1
Let $D=1$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})1 1 1 A = \overline{B}A$
Let $D=0$ and $E =1$. The formula becomes $1(\overline{A}+\overline{C}) C \overline{B} 1 = \overline{A}C\overline{B}$
Let $D=0$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})(\overline{A}+\overline{C})1 \overline{B} A = \overline{C}\overline{B}A$

So the original formula is
$$DE + (D\overline{E}A + \overline{D}(E\overline{A}C + \overline{E}\overline{C}A))\overline{B}$$

(Computationally, it is debatable which formula is simpler.)


Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

If you consider a grammar $(N, \Sigma, P, S)$ you could actually give a regular expression for the production rules $P$, which pretty much determine the whole grammar:
$$r = S \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast (, \bar{N} \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast)^\ast$$
over the alphabet $N \cup \Sigma \cup \{,, |, \to\}$, where we use the $\bar{N}, \bar{\Sigma}$ as shortcut for $\sum_{A \in N} A$ and $\sum_{a \in \Sigma} a$.

So you could pass the grammar (the "code" of the cfl) to a finite automaton to check whether it is a context-free-grammar.

Basically, you just have to check whether there is only one single non-terminal in front of a $\to$. There is no nesting in contex-free grammars in contrast to regular expressions.


Is the language of TMs that halt on some string recognizable?

You can construct a recognizer following the same principle used for the recognizer for HALT. The only extra bit is how you check "all" inputs without getting stuck in a non-terminating computation.

An important technique you can use here is called dovetailing (expressed with inputs from $\mathbb{N}$):

Simulate one step of $M$ on $1$.
Simulate two steps of $M$ on $1$ and $2$ each.
Simulate three steps on $1$, $2$ and $3$ each.

$\quad\vdots$

Terminate and accept once any of the simulated computations terminates and accepts.

If there is a halting input of $M$, this dovetailed simulation certainly finds it after finite time. If there is none, it loops and is correct in doing so.

This is, in essence, your $N$ (with an explanation why it's actually a computable function). You don't need the rest of the reduction in order to show that $L$ is semi-decidable.


How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)

A simple way is as follows: do a symmetric visit of the BST (in time $O(n)$) and write down the elements in increasing order to an array $A$. Then reconstruct the BST from $A$.

If you're fine with a recursive algorithm, and the positions of $A$ are indexed form $0$ to $n-1$, then the root $r$ of the new BST will be exactly the element $A[\frac{n-1}{2}]$. The elements in $A[0], \dots, A[\frac{n-1}{2}-1]$ will be those of the subtree $L$ rooted in the left child of $r$, and the elements in $A[\frac{n-1}{2}+1], \dots, A[n-1]$ will be in the subtree $R$ rooted in the right child of $r$.

Notice that $|L| = 1 + \frac{n-1}{2}-1 = \frac{2^i - 2}{2} = 2^{i-1}-1$ and
$|R| = 1 + (n - 1) - (\frac{n-1}{2} + 1 ) =  (n - 1) - \frac{n-1}{2} = \frac{n-1}{2} = 2^{i-1}-1$, so you can apply this algorithm recursively.

The time required is $T(n) = T(2^i - 1) = 2 T(2^{i-1} - 1) + \Theta(1)$, with $T(1)=\Theta(1)$, which has solution $T(n)=\Theta(n)$.


Average number of full nodes in rooted m-ary tree

Every $m$-ary tree is a node together with up to $m$ children, which are also $m$-ary trees. Let $T(x,y)$ be the generating function in which the coefficient of $x^ny^k$ is the number of $m$-ary trees with $n$ nodes and $k$ full nodes. Then
$$
T(x,y) = x(1 + T(x,y) + \cdots + T(x,y)^{m-1} + yT(x,y)^m).
$$
The generating function of the total number of $m$-ary trees is $A(x) = T(x,1)$, and the generating function of the total number of full nodes in $m$-ary trees is $B(x) = \frac{\partial}{\partial y} T(x,y)|_{y=1}$.

The generating function $A(x)$ satisfies the equation
$$
A(x) = x(1 + A(x) + \cdots + A(x)^m).
$$
The generating function $B(x)$ satisfies the equation
$$
B(x) = x(B(x) + 2A(x)B(x) + 3A(x)^2B(x) + \cdots + mA(x)^{m-1}B(x) + A(x)^m),
$$
and so
$$
B(x) = \frac{xA(x)^m}{1-x(1+2A(x)+3A(x)^2+\cdots+mA(x)^{m-1})}.
$$

You can try solving these equations.

For example, in the trivial case $m=1$, we have $A(x) = x(1 + A(x))$, and so
$$ A(x) = \frac{x}{1-x} = \sum_{n \geq 1} x^n. $$
It follows that
$$
B(x) = \frac{x\cdot \frac{x}{1-x}}{1-x} = \frac{x^2}{(1-x)^2} = \sum_{n \geq 1} (n-1)x^n.
$$
Therefore the average number of full nodes in $1$-ary trees with $n$ nodes is $\frac{n-1}{1} = n-1$.


The short answer is that for any finite language $p$ is greater than the length of every string in the language - i.e. finite languages are a trivial case as it's true that every string longer than $p$ can be pumped.

Beyond the question you asked, understanding what the pumping length is can help with stuff that you might do later. A very brief sketch of the proof of the lemma is that given a regular language, there's some DFA that accepts it. We can can take $p$ to be the number of states in that DFA.

Then if there are no loops in the DFA, we have a finite language an every string has length strictly less than $p$ (it can't have passed through the same state twice), this is the case in the question.

If there are loops (i.e. the language is infinite) then there can be strings of length greater than $p$, but this means that they have to have repeated some states (by going around the loop), and that it has to have done this loop in the first $p$ characters (otherwise we have too many characters for the number of states). This loop is the $y$ section of the string, obviously we can go around the loop as much as we want (even zero times), and this is the pumping part.

Obviously this is quite informal, but you should be able to glean the essential parts that give the conditions of the pumping lemma.


One time pad, get plaintext using ciphers encoded with the same key

So I've passed coursera Scala course and deciced to apply my fresh knowledge.
Here is my algo:

Xor ciphers with each other and collect xor result for each position.
As a result I got a Map[Int, List[String]] where Int is a position of char in chiper and List[String] are all xor results for current position.
I have an assumption that if xor in List[String] equals to UPPER ASCII alpha, it means that  source of this computation was: *space xor lower_alpha = UPPER_alpha*.
I can try to guess key value: c1 (char from 1st cipher), c2(char from 2nd cipher), xorRes (c1 xor c2 = xorRes) => c2 xor(c1 xor xorRes) or c1 xor(c2 xor xorRes) = *lower_alpha*.

Here is a part of code:

  /**
   * hex1 is a hex from 1st cipher
   * hex2 is a hex from second cipher
   * xor is ahex1 xor hex2
   * @return List with pos of possible key and possible key value else return empty list
   * */
  def getPossibleKey(hex1: String, hex2: String, xor: String, pos: Int): List[(Int, String)] = {
      if(isUpperAphpa(xor)){
          if( isLowerAphpa(xorHexStrings(xorWithSpace(hex1), hex2)) ){
            List( (pos, xorWithSpace(hex1)) )
          }else if( isLowerAphpa(xorHexStrings(xorWithSpace(hex2), hex1)) ){
            List( (pos, xorWithSpace(hex2)) )
      }else{
        List.empty
      }
  }else{
    List.empty
  }

}

As a result i got: List[Int, String] where String is the most popular lower_alpha got from getPossibleKey function.

Then i just applied collected key to each cipher and started to fix the key. I know that c1 xor m1 = k1 where c1 is a cipher fragment, k1 is a key fragment and m1 is a plain text.


Concretely speaking, the Backus-Naur form is a notation for context-free grammars, applied to the (formal) description of languages at the syntactical level.

While there are extended versions of BNF that have been standardized, the BNF itself hasn't, so there is no way of determining if the empty grammar is "legal" BNF.

As a mathematical object, the possibility of an empty grammar will depend on the definition (of grammar) used. A grammar that has no productions is usually said to define the empty language, but any grammar whose set of possible terminal derivations is empty is also a candidate definition of the empty language.


Remove contiguous subsequence so the remaining numbers will created a sorted sequence

Let the original sequence be $a_1,\ldots,a_n$. After removing a contiguous subsequence $a_{i+1},\ldots,a_{j-1}$, we are left with $a_1,\ldots,a_i,a_j,\ldots,a_n$ (possibly $i = 0$ or $j = n+1$). In particular, if $a_1 \leq a_2 \leq \cdots \leq a_I > a_{I+1}$ then $i \leq I$, and if $a_{J-1} > a_J \leq a_{J+1} \leq \cdots \leq a_n$ then $j \geq J$. In other words, we can remove all elements $a_{J+1},\ldots,a_{I-1}$. Renaming elements, we are left with two non-decreasing sequences
$$a_1,\ldots,a_s,b_1,\ldots,b_t.$$
Merge both sequences, and consider all places in the merged sequence in which a $b$-element follows an $a$-element, say $a_i,b_j$. This corresponds to the sorted sequence $a_1,\ldots,a_i,b_j,\ldots,b_t$ of length $i+t-j+1$. Go over all such places and choose the one maximizing the length of the corresponding sequence. (You also need to consider some corner cases, which I leave to you.)

This algorithm runs in linear time, and so is asymptotically optimal.


Hint: If you have all-pairs shortest-paths information, and if you are considering placing a store at city X, can you compute the max distance from any city to a store?  You could now enumerate all possibilities for city X.  What's the running time of this algorithm?

An alternative approach:

Hint: If you add a new source vertex and add edges from it to _______, and then use Dijkstra's algorithm to compute single-source shortest-paths starting from that source, does that give you any useful information that will help you?  (You'll have to fill in the blank somehow.)


Why can useless states in TMs not be found by traversing the state graph?

Your proposed algorithm finds some useless state, but not all of them.

Remember that you have tape content to deal with. Say, for instance, a state is reachable when there's a symbol 2 on the tape. It is reachable in the state graph, but if the TM gets only binary input (and never write a 2 itself) it will never be attained by the machine.

The proof you have tells you that there is no way to fix this.

Note that this problem is similar to detecting dead code; maybe this metaphor works better for you.


Single-source shortest path problem with diameter

Instead of a min-heap use an array of $D +2$ lists indexed from 0 to $D+1$. The $i$th list contain vertices whose distance to the source equals $i$ except for the last one which contains vertices with unbounded distance.
Iterate over this array from $0$ to $D$ and for each list, while not empty choose the head of the list as the vertex whose incident edges are to be relaxed in this iteration (the vertex with min distance to the source) and remove this element from this list.
To ensure updates add an array of $n$ pointers such that each vertex points to its occurance in the lists .
It is easy to see that updates run in constant time, hence we get $O(m)$ for updates over all edges. Since we iterate over empty lists and each vertex only once in the array we have amortized running time $O(n+m)$ for iterations.