It looks like you are on the wrong track.

While it is trivially true that $(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ where $\lambda$ is the language consisting of the empty word,    it is more often than not that $(L_1^*L_2^*)^{(1)}\neq (L_1\cup L_2)^{(1)}$. For example, if either $L_1$ or $L_2$ has a non-empty words, the left side $(L_1^*L_2^*)^{(1)}=(L_1^*L_2^*)^{(1)}\supseteq (L_1^*\cup L_2^*)$ has infinitely many word. However, if furthermore we let both $L_1$ and $L_2$ be finite languages, the right side $(L_1\cup L_2)^{(1)}$ is a finite language as well. A concrete counterexample can be given by $L_1=\{a\}$ and $L_2=\lambda$.

Here is an approach to move forward. Can you prove that for any language $L$, $(L^*)^*=L^*$? The use of that equality is that you can deduce that $(L_1\cup L_2)^{*}=\left((L_1\cup L_2)^{*}\right)^*$.

Here is another approach that I like. Intuitively, it is easy to "see" the equality $(L_1^*L_2^*)^* = (L_1\cup L_2)^*$. Note that A word in $L_1^*L_2^*$ is some number of words in $L_1$ followed by some number of words in $L_2$.

A word in $(L_1^*L_2^*)^*$ is some number of words in $L_1$ followed by some number of words in $L_2$, possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$, ..., possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$. Here "some number of" means zero or more.
A non-empty word in $(L_1\cup L_2)^*$ is a word in $L_1$ or $L_2$, possibly followed by a word in $L_1$ or $L_2$, ..., possibly followed by a word in $L_1$ or $L_2$.

Can you see how a word in the former language must be a word in the latter language? Can you see how a word in the latter language must be a word in the former language? If you can, try expressing those "how" in rigorous terms. That would be a proof.

Here is a related exercise.

  Let $L_1$ and $L_2$ be languages such that $L_1\subset L_2^*$ and $L_2\subset L_1^*$. Prove that $L_1^*=L_2^*$.


High dimensional Pareto dominance query data structure

Here is one approach you could consider.  If the number of non-missing coordinates is tightly concentrated around 10, it might help you partly avoid the curse of dimensionality.  I don't know whether it will be useful in practice.
Choose a random hash function $h:\{1,\dots,d\} \to \{1,\dots,10\}$.  If $x \in \mathbb{R}^d$ is a data point, let $f(x)$ be its signature, where $f:\mathbb{R}^d  \to \mathbb{R}^{10}$ is defined as
$$f(x) = (x^*_1,\dots,x^*_{10})$$
where $x^*_j = \max \{x_i \mid h(i)=j\}$.
Notice that the signature is dense, i.e., $f$ maps a sparse high-dimensional vector to a dense low-dimensional vector.
Also, notice that $f$ is monotonic: if $z \preceq x$ then $f(z) \preceq f(x)$.  The converse does not necessarily hold.
The approach will be to build a data structure that, given a query $z$, helps us enumerate all $z$ such that $f(z) \preceq f(x)$; then we will check each such $x$ to see whether $z \preceq x$, and count the number that do, or output the lowest-priced ones that do.  This reduces the problem from a 500-dimensional problem (on sparse data points) to a 10-dimensional problem (on dense data points).
How does the 10-dimensional data structure look?  We can use a simple trie, where the $i$th level branches on the value of $x^*_i$, and each leaf stores one data point.  In practice, I suggest organizing the list of children at the $i$th level using a binary search tree keyed on $x^*_i$, rather than as a list.
Now, the lookup algorithm simply traverses the trie recursively, but with the traversal pruned in the obvious way.  In other words, at each level we only explore the children $x^*_i$ where $z^*_i \le x^*_i$ (for query $z$).  Using the binary search tree data structure, at each level it is easy to enumerate only those children without having to enumerate the other children.
What is the running time of this algorithm?  The worst-case time could be bad, but I'll analyze the average-case running time, via an extremely crude heuristic.  If $z,x$ are two randomly chosen data vectors, then crudely $\Pr[z^*_i \le x^*_i] \approx 1/2$ for each $i$, as we have two randomly chosen numbers from $\mathbb{R}$ and it is roughly equally likely which one is larger.  Therefore, we can expect that only about a $1/2^{10}$ fraction of the data points $x$ will satisfy $f(z) \preceq f(x)$.  And, the running time of the recursive traversal of the trie will be approximately proportional to the number of such data points $x$.  Therefore, this heuristic predicts the average-case running time of this algorithm, on a random query $z$, to be something like $O(|X|/2^{10})$ time.  In other words, this is approximately a 1000-fold speedup over the naive algorithm of enumerating all data points in your dataset.  This crude analysis is overly optimistic and probably the true running time will be worse (e.g., due to collisions in the hash function, as this analysis implicitly assumed that both $z$ and $x$ have exactly 10 components and there are no collisions in the hash function, but in practice neither of those will always be true).

P.S. There are multiple variants possible.  We can also consider replacing 10 by an arbitrary $d'$ and optimizing over $d'$.  Also, we can alternatively define $f$ by
$$f(x) = (x^*_0,x^*_1,\dots,x^*_{d'})$$
where $x^*_0$ is the number of $x^*_1,\dots,x^*_{d'}$'s that are not $-\infty$.  I don't know whether either of those would be better, but they could be variants to try on your data set.
Another possible optimization is to precompute a dozen different copies of the data structure for a dozen different hash functions.  Then, when you want to answer a query for $z$, check which hash function maximizes the number of coordinates in $f(z)$ that are not $-\infty$, and use the corresponding data structure for the lookup.  If $x$ has exactly 10 non-missing coordinates, then it is very likely that one of these hash functions leads to a signature with only 0, 1, or 2 coordinates at $-\infty$.  Also you could consider an approach where $d'$ is large, say $d'=20$; then there is a good chance that there will be one hash function that does not introduce any collision... though I'm not sure what the effect of increasing the dimension like that might be on running time.


Why is the set of NFA that accept all words in co-NPSPACE?

Your question is really about the following statement: If an NFA with $n$ states does not accept every string, then it rejects some string of length at most $2^n$.  (The rest of the proof comes from the fact that REACH is in NL.)

To see why this is so, first let's look at a DFA with $k$ states that does not accept every string.  The transition function of the DFA corresponds to a directed graph $G$ on $k$ vertices. DFA computations bijectively correspond to walks in $G$ starting from the vertex $s$ representing the start state.

Since the DFA does not accept every string, there is a vertex representing a non-accepting state $j$ reachable by a walk from $s$.  In particular, there is a simple path $P$ from $s$ to $j$, which can have length at most $k$ (e.g., DFS will produce one).  $P$ corresponds to a string of length at most $k$ that is not accepted.

The NFA question reduces to the DFA one.  Using the powerset construction, convert the NFA with $n$ states to a DFA with $k = 2^n$ states and then use the above argument.


Showing that the class of regular languages are closed under merging / modified shuffle

Express the two languages as NFA.  Use a product construction.  Think carefully about what transitions should exist in the product automaton.


ε-NFA to DFA - initial state with only epsilon transitions

Here is an algorithm to convert an $\epsilon$-NFA to an equivalent DFA.

Let the $\epsilon$-NFA consist of a set of states $Q$, an initial state $q_0$, a set of accepting states $F$, and a transition function. We construct a DFA on the set of states $2^Q$ (the power set of $Q$). The initial state is the $\epsilon$-closure of $q_0$ (the set of all states in $Q$ reachable from $q_0$ by a path of $\epsilon$-transitions). A state is accepting if it intersects $F$. We define the transition function $\delta$ as follows: given a state $S \in 2^Q$ and a letter $a$, $\delta(S,a)$ consists of all states in $Q$ reachable from a state in $S$ by taking an $a$-transition followed by a path of $\epsilon$-transitions.


$\{a^n b^n\} \cap \{a^*b^*\}$ regular or not?

The complement of $\{a^nb^n \mid n \geq 0\}$ is not $\{a^nb^n \mid n < 0\}$. And the complement of the complement should always equal the original set. The rest of your argument falls apart here.

As an example, abb is a string that is not $a^n b^n$, thus it should be in the complement of L.

To hint at an answer, is there any string $a^nb^n$ that is not $a^*b^*$? What does this say about the intersection of the two?


What is the average-case complexity of trial division?

By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $[n/2,n]$ are prime.  We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \in [n/2,n]$, we have $x = \Theta(\sqrt{n})$).  Therefore,

$$\mathbb{E}[T(X_n)] = \Omega\left({\sqrt{n} \over \log n}\right).$$

This is enough to establish that trial division is inefficient.  Also, since we have the upper bound

$$\mathbb{E}[T(X_n)] = O(\sqrt{n}),$$

we get a pair of upper and lower bounds that are almost matching.

It turns out one can show that the correct running time is

$$\mathbb{E}[T(X_n)] = \Theta\left({\sqrt{n} \over \log n}\right).$$

I'll show the argument below.  It's a bit detailed, so brace yourself.

There's an error in your post.  You claim that

$$\mathbb{E}[T(X_n)] = {\sum_{i=2}^n \xi(i) \over n-1},$$

but that is not correct.  The running time on input $i$ is not $\xi(i)$; the running time is $\min(\xi(i),\sqrt{i})$, since trial division aborts early as soon as it has tried all divisors $\le \sqrt{i}$.  Therefore, your expression for the running time is not correct.

Yuval Filmus found that your expression was analyzed on Math.SE, and apparently

$${\sum_{i=2}^n \xi(i) \over n-1} \sim {n \over 2 \log n},$$

but unfortunately this doesn't really tell us much about the running time of your trial division, due to the error I mentioned.

If we correct the error, we find

$$\mathbb{E}[T(X_n)] = {\sum_{t<n} \xi(t) \over n-1} + \Theta\left(\sqrt{n} \over \log n\right),$$

where $t$ ranges over all composites less than $n$.  Now we can upper-bound the first term as follows:

$$\begin{align*}
\sum_{t < n} \xi(t)
&\le \sum_{p < \sqrt{n}} \left\lfloor {n \over p} \right\rfloor \times p\\
&\le \sum_{p < \sqrt{n}} n\\
&= n \times \#\{p : p < \sqrt{n}, p \text{ prime}\}\\
&= n \times O\left({\sqrt{n} \over \log n}\right).
\end{align*}$$

where the sum is over all primes $p$ that are at most $\sqrt{n}$, and using the prime number theorem in the last step to note that there are $O(\sqrt{n}/\log(\sqrt{n})) = O(\sqrt{n}/\log(n))$ many such primes $p$.

It follows that

$$\mathbb{E}[T(X_n)] = O\left(\sqrt{n} \over \log n\right),$$

so the simple bound given at the start of the answer was tight.


Finding top k which are the most different from each other

Your problem is NP-hard, when $k$ is part of the input.  Let $G=(V,E)$ be an undirected graph.  If we set all the scores to zero and $\text{var}(u,v)$ to 1 if $(u,v) \in E$ and 0 otherwise, your problem is equivalent to asking whether $G$ contains a clique of size $k$.  This is a NP-hard problem.

If we set all the scores to zero and allow the variety values to be arbitrary, your problem is equivalent to the maximum edge-weighted clique problem (MEWCP), which has been studied in the literature.  For instance, you can use quadratic programming or ILP to look for solutions; these can take exponential time in the worst case, but might be useful in practice if the number of items is not too large.

Obviously, when we take into account that scores can be non-zero, the problem only gets harder.  You might be able to adapt methods for MEWCP to your problem, or express your problem directly as an ILP or QP.


Complexity of $n \times \log n$ tiling problem

Hint: Use dynamic programming, going row by row. Use the fact that there are only $\log n$ many columns, and so only $|A|^{\log n} = n^{\log |A|}$ many different configurations of each column.

(The resulting algorithm will be polynomial in $n$ but not in the input size, which is only $O(\log n)$.)


The optimized numbers of variables and clauses to encode a graph coloring problem in CNF

The problem statement needs to be specified more precisely to be meaningful.

If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-colorable or not.  I suspect this isn't what you're looking for, so you probably need to define the problem statement more carefully to be able to answer the question in a useful way.  For instance, perhaps you need to specify exactly what properties you want $F$ to have.


Behavior of specific PDA for a certain input

This PDA is non deterministic. So just like in non-deterministic Finite State Machines you fork.

A string is only accepted by the PDA if one of the forks ends in an accepting state.


Alternative algorithm for minimum spanning tree construction

It is not immediate to see whether OP’s approach can be adapted easily to a full proof.

Here is an answer to the same question but phrased differently, a local minimum in the graph of spanning trees is a (global) minimum spanning tree.

I will present  another proof, which is more flexible and probably easier to understand.

Let $G$ be an undirected connected (finite) graph with distinct costs on its edges, as in the original question. Consider the delete-heaviest-edge algorithm on $G$, which removes the heaviest edge in a cycle until no cycle remains. Just to be clearer, let me call the remaining edges at the end of the algorithm $H$. Let us show that $H$ is the minimum cost spanning tree (MST) of $G$.

$H$ is a spanning tree of $G$ because of the following.

$H$ is connected,  since $G$ is connected and all we have done is breaking cycles.
$H$ is has no cycle since the algorithm ends only if there is no cycle.
$H$ has all vertices of $G$ since no vertex of $G$ has ever been deleted.

Because of the the cycle property, any edge in any minimal cost spanning tree (MST) of $G$ is never deleted. So all edges of any MST of $G$ remain in $H$. However, any spanning tree of $G$ has the same number of edges, so $H$ must be the unique MST of $G$. (Yes, we have also proved that there is only one MST of $G$, thanks to the distinctness of the costs).

So we have proved that the delete-heaviest-edge algorithm finds the MST. The flexibility of that algorithm is that in each step we can choose any particular cycle.

Following the OP, let $T$ be the spanning tree which we obtain at the end of OP's algorithm. Initialize $G'$ to be a copy of $G$ and $T'$ is the spanning tree of $G'$ that corresponds to $T$. Let $e'$ be an edge in $G'$ but not in $T'$. If we add $e'$ to $T'$, we will create a cycle since $T'$ is spanning. Note that $e'$ must be the unique heaviest edge in that cycle; otherwise, we can substitute $e'$ for that unique heaviest edge, which is in $T'$, to get a lighter spanning tree, which means the OP's algorithm must not end with $T$, a contradiction. Let us run the delete-heaviest-edge algorithm on $G'$ in the following way. We choose that cycle and delete $e'$ from $G'$. Repeat until all edges in $G'$ but not in $T'$ are deleted. What remains is exactly $T'$. Since $T'$ has no cycle, we have actually run the delete-heaviest-edge algorithm to the end. As we have proved, $T'$ is the MST of $G'$. That is, $T$ is the MST of $G$.


Find distinict elements in an array in $O(n)$ time

For the first task you can use a solution similar to yours.
Let the input array be $A[1, \dots n]$. Create an array $B$ indexed with the integers from $10$ to $10n$ where each entry is a boolean value initially set to false. Then, for each input element $A[i]$, set $B[A[i]]$ to true. At the end of the above loop, return the number of indices $y$ such that $B[y]$ is true. This runs in $O(n)$ worst-case time.
Notice that, depending on how the hashtable is implemented, a hashtable-based solution is not guaranteed to have a worst-case time complexity of $O(n)$. Usually the hash-tables provided by the common programming languages only provide you with expected constant time operations.
Also, if don't have any other information on the values the the input integers, you can't use linear-time sorting algorithms (since their complexity depends on the range of the input values).
Anyway, your solution already works for the general problem in $O(n)$ expected time.
I don't think the general problem can be solved in $O(n)$ worst-case time. According to Wikipedia, there is a lower bound of $\Omega(n \log n)$ on the algebraic decision tree model, and randomness doesn't help.


Help with understanding Hopcroft's algorithm

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function).

For incomplete DFA with partial state transition function $\delta$. You can always convert it to complete DFA $M'=\{Q',\Sigma,\delta',q_0,F\}$ where $$Q'=Q\cup\{q_{err}\}$$ and $\delta'$ extends $\delta$ by define $\delta_a(q)=q_{err}$ for all undefined $\delta_a(q), \delta_a\in\delta,q\in Q\cup\{q_{err}\}$.


Proof that a randomly built binary search tree has logarithmic height

Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced:

Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this case 3). With a little math, $n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$, which is to say it has $O(\log n)$ height. For the entirely unbalanced tree, the height of tree is simply $n-1\rightarrow O(n)$. So we have our bounds.

If we were constructing a balanced tree from an ordered list $\{ 1,2,\dots,n\}$, we'd choose the middle element to be our root node. If we are instead randomly constructing a tree, any of the $n$ nodes are equally likely to be picked and the height of our tree is: $$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$
We know that in a binary search tree, the left subtree must only contain keys less than the root node. Thus, if we randomly choose the $i^{th}$ element, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements, so more compactly: $h_n=1+\max (h_{i-1},h_{n-i})$. From there, it makes sense that if each element is equally likely to be picked, the expected value is just the average of all cases (rather than a weighted average). Hence: $\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

As I'm sure you've noticed, I've deviated slightly from how CLRS proves this, because CLRS uses two relatively common proof techniques that are disconcerting for the uninitiated. The first is to use exponents (or logarithms) of what we want to find (in this case height), which makes the math work out a little more cleanly; the second is to use indicator functions (which I'm just going to ignore here). CLRS defines the exponential height as $Y_n=2^{h_n}$, so the analogous recurrence is $Y_n=2\times\max (Y_{i-1},Y_{n-i})$.

Assuming independence (that each draw of an element (out of the available elements) to be the root of a subtree is irrespective of all previous draws), we still have the relation: $$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$
for which I did two steps: (1) moving the $\frac{1}{n}$ outside because it is a constant and one of the properties of summations is that $\sum_i ci=c\sum_i i$, and (2) moving the 2 outside because it is also a constant and one of the properties of expected values is $\operatorname{E}[ax]=a\operatorname{E}[x]$. Now we're going to replace the $\max$ function with something larger because otherwise simplifying is difficult. If we argue for nonnegative $X$, $Y$: $\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$, then:
$$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$
such that the last step follows from the observation that for $i=1$, $Y_{i-1}=Y_{0}$ and $Y_{n-i}=Y_{n-1}$ and going all the way to $i=n$, $Y_{i-1}=Y_{n-1}$ and $Y_{n-i}=Y_{0}$, so every term $Y_0$ to $Y_{n-1}$ appears twice, so we can replace the entire summation with an analogous one. The good news is that we have a recurrence $\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$; the bad news, is that we're not much further than where we started.

At this point, CLRS pulls an induction proof $\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$ out of their ... repertoire of mathematical experience, one that includes an identity $\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$ they leave to the user to prove. What's important about their choice is that its largest term is $n^3$, and recall that we are using exponential height $Y_n=2^{h_n}$ such that $h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$. Perhaps someone will comment why this particular binomial was chosen. The general idea though is to bound from above our recurrence with an expression $n^k$ for some constant $k$.

To conclude with a one liner:
 $$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n) $$


Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

3-SAT is $NP$-complete, by the Cook-Levin theorem. This means that any problem in $NP$ (such as 3-coloring) can be solved in polynomial time given an oracle for 3-SAT.

  shouldn't we need to show $Q \leq_p P$ AND $P \leq_p Q$, where $Q$ is some known NP-complete problem, to prove that some problem $P$ is NP-complete?

Yes, but you essentially get the $P \leq_p Q$ for free because $P$ is in $NP$ and $Q$ is $NP$-complete.


Is there an algorithm that will fill any shape with points a given distance away from each other?

Are you looking for something like this?

Another way is to create equilateral triangle tiling like this, plot your polygon and check which points are inside. Of course it is not needed to actually plot it, just store it in memory.
If your resolution is e.g. one pixel big, you can check all possible starting points shifts from the starting point to find better solution.
To find optimal solution also rotation would be needed, or different approach.
If you decide that not rotated version is sufficient, the ray casting algorithm (also known as scanline test) for testing point inside polygon would be very effective, because all points in a row form line, so in one longer pass you can test whole row.


Select signals for memory mapped into common address space

Let's call the memory address $x$. Thus $x$ is composed of bits $x_0,\ldots,x_{31}$, where $x_0$ is the LSB and $x_{31}$ is the MSB.
A memory address belongs to the EEPROM mapped area if it is in the range $0,\ldots,2^{20}-1$. You can check that this is equivalent to the condition $x_{20} = \cdots = x_{31} = 0$, which you can translate into a Boolean expression for "EEPROM Select".
The other signals can be handled similarly.


How does this recurrence relation fit the algorithm?

You should be careful about what is being counted. If you want to count "runtime" (as in, number of statements) the given recurrence is clearly wrong.

Reverse-engineering from the recurrence, it is probably supposed to count additions. In particular, note how the computation the parameters for recursive calls is ignored. I hope it is clear that the recurrence is correct for the worst-case then; your reasoning for $+1$ is spot-on.

Why does restricting your self to additions make sense here? Additions are one of the statements that are executed most often (in the worst case, that is ignoring line 4.). That means that the true runtime (in a theoretic model) is proportional to the number of additions. Since you are (most likely) after asymptotics in terms of $O$, counting additions is sufficient: the proportion-constant is lost in $O$, anyway.

You can, for the fun of it, set up a recurrence counting all statements. You'll see that the result has the same asymptotic growth as the one you were given.


In general, this is not possible unless P=NP. So, it is unlikely that such a method exists.

Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $C_i$ and variables $v$. For each clause, denote the variables that appear positive by $C_i^+$ and the variables that appear negative by $C_i^-$. Now, consider the following integer program $P$:

$\begin{align}
\max 1 \quad \text{s.t.} \quad & \sum_{v\in C_i^+} x_v + \sum_{v\in C_i^-} (1-x_v) \geq 1 \text{ for all } i\\
& x_v \in \{0,1\} \text{ for all } v
\end{align}$

Note that $P$ has a feasible solution if and only if our 3SAT instance is satisfiable. (a solution to $P$ corresponds to a satisfying assignment of the 3SAT instance) This solution is then 'optimal' as well, as all feasible solutions of $P$ have the same cost. This means that also the relaxation $P^*$ must have the same cost if $P$ is feasible. So, we will assume that the given 3SAT instance is satisfiable, so that the costs of $P$ and $P^*$ are equal.

Now, suppose we have some method to find a solution for $P$ from a solution $y\in [0,1]^d$ for $P^*$. As $P^*$ is a normal linear program, we can find such a solution $y$ in polynomial time, by using e.g. the ellipsoid method. Then, our method gives us a solution for $P$ in polynomial time. But this solution gives a satisfying assignment for our initial 3SAT problem, which means we can find a satisfying assignment to 3SAT problems in polynomial time. As finding a satisfying assignment for 3SAT is NP-hard (even if we know the instance has a satisfying assignment), this means that P=NP

I suppose that intuitively, what is going on here is that knowing the value of a solution to an integer program does not tell you a lot about the specific variable assignment. In a way, this is because the 'complexity' of a linear program lies mostly in its constraints, rather than the goal function.


The original definition of 3NF was "flawed".  Relvars such as yours could perfectly be in 3NF and still have undesirable redundancy.

And the flaw was exactly in cases when there was more than one candidate key.

Which was the very reason why BCNF was introduced, as a "fix" to the "flaw" that was discovered in [the definition of] 3NF.

The thing is, in cases of >1 candidate key, we wouldn't even want designs such as yours to even satisfy 2NF.  Both 2NF and 3NF can be violated only by nonprime attributes.  That is the flaw in their definition.  When the "fix" was applied to 3NF, superseding it with BCNF, the fix itself was flawed because actually what should have happened was to supersede the definition of 2NF with one that didn't limit itself to "nonprime" attributes".


The size of the cache in blocks is just the size of the cache in bytes divided by the size of a block in bytes.  However, both the figures you give are wrong: 64 kB is 2^16 bytes, and 16 bytes is 2^4 bytes.  Dividing we get 2^12.


Intuition behind recurrences with growth O(n log n) vs O(n²)

What you are missing is the big O constants. In the first case, at successive heights you are doing work of $$n, 2\frac{n}{2}, 4\frac{n}{4}, \ldots = n,n,n,\ldots. $$ In the second case, at successive heights you are doing work of $$n^2,2\frac{n^2}{4}, 4\frac{n^2}{16}, \ldots = n^2,\frac{n^2}{2},\frac{n^2}{4}.$$ Since the series $1,1/2,1/4,\ldots$ converges, the total work is only $O(n^2)$.


NP-completeness of a Generalized Version of Subset Sum

Without loss of generality consider an instance $\langle S, t \rangle$ of subset sum where $S$ contains only positive integers and $t \ge 1$ (zeros can be dropped from $S$, and the case $t=0$ is trivial).
Now build a new instance $\langle T, t' \rangle$  of your generalized version of subset sum by choosing $T = \{ (t+1)x : x \in S \}$ and $t'=t(t+1)$.
If the elements of a subset $S' \subseteq S$ sum to $t$, then the elements of $\{ (t+1)x : x \in S' \} \subseteq T$ sum to $\sum_{x \in S'} (t+1)x = (t+1)\sum_{x \in S'} x =(t+1)t = t'$.
If there is a subset $T' \subseteq T$ of elements that can be arranged in an expression $E$ (that uses only addition, multiplication, and parentheses) that evaluates to $t'$, then $E$ uses no multiplication.
Indeed, if $E$ used at least one multiplication, it would evaluate to at least $(t+1)^2 > (t+1)t = t'$ since each of the involved factors must be at least $(t+1)$.
As a consequence it must be that $t' = t(t+1) = \sum_{x \in T'} x$.
Let $S' = \{ \frac{x}{t+1} : x \in T' \} \subseteq S$. We have that $\sum_{x \in S'} x = \sum_{x \in T'} \frac{x}{t+1} = \frac{1}{t+1} \sum_{x \in T'} x = \frac{t'}{t+1} = t.$
This shows that your version of generalized subset sum is NP-complete (membership in NP is trivial).


The Lovász theta function is bounded between the independence number and the clique covering number (the chromatic number of the complementary graph). For even cycles, both numbers are $n/2$. For example, for the $6$-cycle with vertices $1,2,3,4,5,6$, there are independent sets of size $3$, e.g. $\{1,3,5\}$, and the graph can be covered with the $3$ cliques $\{1,2\},\{3,4\},\{5,6\}$.


What you are describing is unrelated to alpha-beta pruning.  The tendency of fixed-depth minimax searches to badly underestimate or overestimate positional scores in dynamic situations is known as the horizon effect.  The problem is due to static evaluation being used on positions unsuited to such evaluation.  Static evaluation scores a position based on things like material, pawn structure, and king mobility, properties that can be determined without extending the search tree.  But some positions are transitional, needing more search to identify their nature.

The standard way to deal with this problem is to recursively apply a quiescence function to all terminal nodes that extends the search an extra ply if there are checks, forced captures or promotions available at that node.  If no such moves are available, then the position is considered quiet and the usual static evaluation function is called.


Grammar for a language: odd length, middle character not repeated

Assume the middle character is $a$. Then a grammar is
$$A \rightarrow bAb | bAc | cAb | cAc | a$$
Similarly, we can define nonterminals $B$ and $C$ for the strings in our language where $b$ and $c$, respectively, are the middle symbols. Given those, you can get a grammar for your language by taking the union:
$$S \rightarrow A | B | C$$


Algorithm Complexity Analysis on functional programming language implementations

It depends on the semantics of your functional language. You can't do algorithm analysis on programming languages in isolation, because you don't know what the statements actually mean. The specification for your language needs to provide sufficiently detailed semantics. If your language specifies everything in terms of lambda calculus you need some cost measure for reductions (are they O(1) or do they depend on the size of the term you reduce?).

I think that most functional languages don't do it that way and instead provide more useful statements like "function calls are O(1), appending to the head of a list is O(1)", things like that.


What algorithm can solve the conversion engine problem?

In a union-find data structure, each item is either a root or points at a parent. For us, units will be items, and each pointer to a parent will be annotated with the appropriate conversion. You can maintain this annotation while running the usual operations on the union-find data structure.

Using this annotation union-find data structure, you can implement each add() using union and each lookup() using find, with only a constant factor overhead.


Knapsack problem with multiple constraints

I assume you can compare two recipes and say which would be preferable to the other. That is, you can define an order between them. Then:

You need to find appropriate recipe only once (or very few times). A simple scan through all the recipes is the only way possible. You need to look at every recipe at least once to be able to see if it is good enough or not. This will give linear complexity.
You have to find appropriate recipes repeatedly for a lot of different baskets. Then, it would make sense to order the recipes in a way that searching would be faster. You might want to sort the recipes first once, in $O(n\log n)$ time. Then, whenever you encounter a basket of ingredients for which you want to find the best recipe, you search the sorted list of ingredients using binary search in $O(\log n)$ time. Thus, the pre-processing phase (sorting) will be slow, but subsequent queries will be fast. This will be beneficial only when you have millions of recipes and want to search the best matched recipe for different baskets hundreds or thousands of times each second.

Admittedly, this is a little vague, but based on the given information, this is the best I can give.


What does it mean to say that there doesn't exist an algorithm from a TM point of view?

First, note that it is easy to write algorithms that not always halt:

algo(n) {
  while ( n % 2 != 0 ) {
    n += 2
  }
  return n
}

It seems that you are asking for a semi-decidable problem of practical relevance. Consider verification of hard- and software. Many interesting properties require logics of higher order for their formulation, and usually satisfiability and/or validity of such formulae is undecidable.

But these logics have proof system, sets of axioms and rules that make up every proof for valid formulae¹. Along these systems, all proofs can be (recursively) enumerated: thus, we can semi-decide many important properties. Using clever heuristics, lots of computational power and human intervention, e.g. by providing key lemmata, many problems can be solved in practice (i.e. for some useful instances) that are theoretically undecidable.

Beware incomplete proof systems.


You can always satisfy at least half of clauses: for each variable $x$, find the number of clauses that contain $x$ and the number of clauses that contain $\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing $x$ and $\lnot x$. Repeat for other variables.
Since for each $x$ we satisfy at least half of removed clauses, we satisfy half of the clauses overall.
On the other hand, it's also tight: let $\alpha > \frac 12$ be the fraction of clauses for which we can give an answer. Let $\beta > \frac 12$ be the maximum fraction of clauses we can satisfy in a specific clause. Then we can add clauses so that $\beta$ (for the new clause) becomes arbitrary clause to $\alpha$:

If $\beta < \alpha$, then we can add clauses $(x_i \lor \lnot x_i)$, until $\beta > \alpha$ (since these clauses are always true, $\beta$ increases).
If $\beta > \alpha$, we can add clauses $(x_i)$ and $(\lnot x_i)$, until $\beta < \alpha$ (since exactly half of clauses is true, $\beta$ decreases).

I didn't check, but to get $O(\frac 1m)$ difference (i.e. to find the exact number of clauses), I think it suffices to add $O(m)$ clauses. In other words, if we can solve for some $\alpha > \frac 12$, we can check for any $\beta$ whether $\beta$ fraction of clauses can be satisfied, and therefore we can solve MAX2SAT in polynomial time.


Why is the opcode 0 for all r-type instructions? Please explain your answer

In designing an ISA, there are many tradeoffs that can/need to be taken.
This makes it slightly challenging to answer why questions but I will do my best.

In mips I am sure you are aware of the three instruction classes: I, J, and R.

For this explenation I belive only I and R are relevant.

    Type    [31-26] [25-21] [20-16] [15-11] [10-06] [05-00]
    R-Type  [opcode] [$rs]   [$rt]  [ $rd ] [shamt] [funct]
    I-Type  [opcode] [$rs]   [$rt]  [         imm         ]

First lets examine the implications of using [31-26] for R-Type [funct] information.

This would limit the total number of R + I + J instructions to 64. To increase this field for all instructions would limit the size of immediate values.

Additonaly, [5-0] of R instructions would be freed up but not used, not very efficient. By moving R-type opcodes to [funct] the total possible instructions jumps to ~127, while keeping 16 bit immediates.

Finally, if you notice in the data path below there is almost no cost to moving R instruction opcodes to the [funct] field, and it makes room for future instructions to be added to the ISA.

I hope this helps


What is the correct FSA representation of the following string sequence?

I think none of your finite automata accepts the third string ABDDEFGHI.The following is what I think a correct finite automaton for accepting all three strings

In case where your language has the third string ABDDDFGHI.The first is wrong since it accepts another string.The third also seems incorrect since there are multiple labels of same letter exiting from one node.Your second automaton is correct but you may want something like this


Minimum Path cover in a Directed Acyclic Graph

This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard.

Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there exist 2 vertex-disjoint paths satisfying your conditions if and only if the weights can be partitioned into two subsets both with sum $k$, which is exactly the partition problem. Hence, your problem is NP-hard.


Calculating the information density of an encoding system

When people talk about information density in this context, they probably mean that the information density is

$$\text{density} = {n \over m}$$

where $m$ is the number of nucleotides needed to encode $n$ bits.  Here the assumption is that the $n$ bits come from the uniform random distribution (i.e., all $2^n$ possibilities are equally likely).  Implicitly, we are taking $n$ to be very large, or taking the limiting value of the density as $n \to \infty$.

So, think of it this way.  Imagine we had $n = $ 1 million bits.  How many nucleotides would the encoding scheme need, to encode those 1 million bits, on average?  Call that $m$.  Now divide $n$ by $m$; that's your information density.

The way to figure out the average number of nucleotides needed to encode a one-million-bit input will depend on the particular encoding scheme.


Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

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


Algorithm for estimating function maximizing parameters

You have a function $f:\mathbb{R}^3 \to \mathbb{R}$, which accepts three real numbers as input and produces a real number as output.  You want to find values $\omega, \alpha, \beta$ that maximize $f(\omega, \alpha, \beta)$.

This is a standard problem in mathematical optimization, and there are a variety of techniques for solving this problem.

Black-box methods. The methods that are easiest to use treat $f$ as a complete black box: all we need is  a way to evaluate $f$ at any input of our choice.  Example methods include hill climbing, coordinate descent, (well, in this case it will be coordinate ascent, since you want to maximize $f$), gradient descent (well, in this case it will be gradient ascent, since you want to maximize $f$), Newton's method, conjugate gradient methods, and more.
Black-box, plus derivatives. Some of these methods can be sped up significantly if we have an efficient way to evaluate each of the partial derivatives of $f$ at any input of our choice.  Sometimes, if $f$ has a simple representation, we can compute the partial derivatives of $f$ algebraically, which then gives us a way to evaluate these functions at any desired input.  The reason this speed things up is that some of the black-box methods effectively end up approximating the partial derivatives or 2nd partial derivatives (e.g., the gradient or Hessian matrix) as part of the process; if you have a faster way to compute them directly, then those methods become more efficient and more effective.
Dedicated methods. There are other methods available if the function $f$ has a particular algebraic form, e.g., linear programming, convex optimization, and more.  These probably won't apply to you, so they can be safely ignored in your situation.

Many tools, like MathLib, include built-in libraries to apply these methods for you.

In your case, the function $f$ is given by $f(\omega, \alpha, \beta) = \sum_{i=1}^m{\left\{ -\ln(v_i) - \frac{r_i^2}{v_i} \right\}}$ where $v_i = \omega + \alpha r_{i-1}^2 + \beta v_{i-1}^2$.  But those details aren't important; what's important is that, given $\omega, \alpha, \beta$, you can evaluate $f$ to learn the value of $f(\omega, \alpha, \beta)$.  That allows you to apply black-box optimization methods.

One generic issue to be aware of is that many of these methods may only produce a local optimum, not a global optimum.  There are a variety of heuristics for dealing with this, but generally none that are guaranteed to work in all cases.  Often, the methods are fairly sensitive to the choice of starting point, so if you have a good guess at a value of $\omega, \alpha, \beta$ that is likely to be near the optimal value, then starting the methods from there can be helpful.  Also, it can be helpful to apply the methods multiple times, from different (random) starting points and take the best observed over all iterations.


An important argument for learning one is that operations in a purely functional language does not have side effects.

In this case that means one operation cannot change the state of another parallel operation. That makes it much easier to reason about the behaviour of your program, since you don't need to account for all the possible combinations of states, but rather the input and output of each function.

Some functional languages have both purely functional operations and destructive operations (like Lisp and Scheme) and some have only the former (like Haskell). Which one you choose is dependent on what you are trying to solve.


Why we write "Ignore the input " when describing an Enumerator?(Sipser Chapter 3)

It's just an explicit statement that the behaviour of the machine doesn't depend on its input in any way. This could be inferred from the rest of the machine's description, but explicitly saying it makes it clear that it's not a mistake.


No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power.

With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of uncountable sets like the real numbers couldn't be represented in one symbol). And likewise for the output.

So you can make a two-state (one initial, one accept) infinite-alphabet-TM with a single transition that moves to the accept state and changes the symbol under the tape head in accordance with the function you're trying to compute. This recipe would allow you to compute any mapping between sets that can be put in a one-to-one correspondence with the alphabet.

So to avoid that degenerate sort of machine being the answer to everything, you'd need to restrict what the transition function can do. An obvious one would be to require the transition function itself to be computable (ordinary TM's transition functions are trivially computable after all, since they're finite). But then you'd be trying to use computable functions to define your model of computable functions.


Why do OS locks require hardware support?

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

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


How to prove the following language is not in R

Hint: This language is actually computable for every $c$. If $M$ terminates within $c$ steps, then it only gets to see at most $c$ symbols of its input, so in some sense its domain is finite.

There are some subtleties here. For example, it might be that there are also infinitely many inputs on which $M$ doesn't stop within $c$ steps. Perhaps it's better to first prove that the following language is computable for every $c$:
$$
L'_c = \{ \langle M \rangle \mid \text{$M$ stops within $c$ steps on all inputs}\}.
$$


How to prove the following: Every set is Turing reducible to itself

Informally, $A$ is Turing reducible to $B$ if you can figure out what $A$ is by asking questions to $B$.

A bit more formally, $A$ is Turing reducible to $B$ if there's some algorithm you can use to figure out whether a number is in $A$ by asking questions about whether or not various numbers are in $B$. For example, an instance of a Turing reduction between $A$ and $B$ might look like the following:

I want to figure out whether $3$ is in $A$.
I ask $B$, "Is $17$ in you?"
$B$ says yes.
I now say, "Okay, based on that answer I now want to ask: is $42$ in you?"
$B$ says no.
I say, "Great! Now I know that $3$ is in $A$.

So, you're trying to do the following: given some arbitrary set $A$ and an arbitrary number $n$, find a way to figure out whether $n$ is in $A$ by "querying" $A$. (HINT: don't overthink this ...)

Incidentally, Turing reductions don't have to be efficient, or non-stupid, or anything else nice; they just have to work. For example, in the problem you're trying to solve, there is a "best" Turing reduction; but we could also modify that reduction to pointlessly ask "Is $17$ in $A$?" at the end for absolutely no reason, and simply ignore that extra information.


How can a problem be undecidable yet enumerable?

For me, the easiest way to think of it is this:

You're asking yourself "out of a bunch of candidates in a set $X$, do any of them fulfill the property $P$"?

Decidable/recursive means that you only need to look at a finite number of elements of $X$ before you hit some point where you know nothing that's left has the property.

A problem that's recursively enumerable, but not recursive, is one where you can look at each $x$ in $X$ one at a time. If you find one, then you're done, you know there exists on that fulfills your property. But there's no way of knowing when you're done, and $X$ is infinite, so if one doesn't exist, you will end up searching forever.

This contains some simplifications over the theoretical definitions, so be careful.

As an example: The halting problem is, you're looking at all $x_1, x_2, \ldots$ where each $x_i$ is a configuration of the turing machine $M$ after $i$ steps. The property is, is $x_i$ in a halting state. If you find one, you're done, but if you don't find one, there's no way to know when you're done.

Compare this to the SAT problem. You've got a Boolean formula, and you want to give each variable a True or False value to make the whole thing true. Even though it's really slow, you can try all true/false combinations. There's an exponential number of them, but it's finite. When you're done, you're done, and if none of them satisfied, you can halt, confident that there's no answer.


How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points?

You might try using the spring model: https://en.wikipedia.org/wiki/Force-directed_graph_drawing.  Or, you could use optimization methods.  Build an objective function $\Psi$ that is a sum of penalty terms.  For each pair of mapped points $a^*,b^*$ that you are hoping will be at distance $c_{a^*,b^*}$, you have a penalty term $(d(a^*,b^*) - c_{a^*,b^*})^2$.  Also, for each point $a^*$, add a penalty term that is zero throughout most of the interior of $A$, but increases when you get close to the boundary of $A$ and rises to $+\infty$ for all points outside $A$.  Finally, find an arrangement of points that minimizes this objective function.  You could then apply any of a number of optimization methods to do this, such as gradient descent or others.  Stress majorization may be useful.


How to judge the searching precision of Particle Swarm Optimization?

If by "precision" you mean the error in the result of PSO (i.e., the difference between the value that PSO outputs and the true global optimum), the error can be arbitrarily large.  PSO is a heuristic.  There are no guarantees that it finds the global optimum, or even that it gets close -- and there is no formula in terms of parameters (like velocity) for how large the error will be.  The error depends on the optimization problem you're solving and on the shape of the loss surface.


No.  There seem to be multiple misconceptions here.

First, linear regression.  Linear regression assumes that the errors are normally distributed.  It doesn't require that the inputs be normally distributed, and normally they won't be.

Second, neural networks.  Neural networks certainly don't require that the inputs are normally distributed.  I'm not sure where your colleague is getting that from, but it's just not true.

Yes, neural networks work fine in higher dimensions.


Recommended readings for Probability theory applied to algorithms

I highly recommend Mitzenmacher and Upfal, Probability and Computing.

It has almost all the background needed for a beginning graduate student to start in probabilistic algorithms and analysis, and is clearly written, nice examples, etc.


Dove tailing questions about accepting language

Showing some machine $R$ that recognizes $L$ is enough to prove that $L$ is recognizable, however, you have yet shown $R$ recognizes $L$.

Formally, you must show:

$M \in L \Rightarrow  R $ accepts $M$
$M \notin L \Rightarrow  R $ does not accept $M$, but not necessarily halts.

Let $S_i$ be all strings in $\Sigma ^*$ of length exactly $i$. It is clear, for any $i$ that is finite, $S_i$ is also finite.

Let $S_i^*$ be a subset of $S_i$, where every $s \in S_i ^*$ contains exactly five $1$'s.

$R$ is a machine that given input $M$:

for $i=5...\infty$
for $s$ in $S_5^* \cup S_6^* \cup \dots \cup S_i^*$

simulate $s$ on $M$ for $i$ steps. If $M$ halts in $i$ steps or less, finish and accept. Otherwise continue.

Suppose $M \in L $ (and we will show $R$ accepts $M$):
 There exists $w^*$ of length $k$ that contains five $1's$ and $M$ halts on $w^*$ in $r$ steps.

Since $S_i^*$ is finite, $S_5^* \cup S_6^* \cup \dots \cup S_k^*$ is also finite (finite union of finite subsets), so $R$ simulates $w^*$ on $M$. Now if $r \leq k$ then $M$ halts and $R$ accepts $M$.

If $r > k$ then surely $w^* \in S_5^* \cup S_6^* \cup \dots \cup S_r^*$, hence at $i=r$ $M$ will halt on $w^*$ and $R$ will accept.

The second step is very simple; if $M \notin L$ then no such $w$ with five $1's$ exists such that $M$ halts on it, and $R$ will run indefinitely.


Is there a repository for the hierarchy of proofs?

The Mizar system is a huge repository of math proofs. See the wikipedia page and the official website.

  of all of the known mathematical proofs that can be expressed using English statements

From wikipedia/Mizar_system#Mizar_language:

  The distinctive feature of the Mizar language is its readability

Proofs are written as articles, of which there are more than a thousand articles, and more than 50,000 proven theorems. The wikipedia page mentions some interesting ideas of the "QED manifesto", and how Mizar might be on its way to accomplishing this.

A huge graph of the Mizar library.

This paper might also be helpful: Combining Mizar and TPTP Semantic Presentation Tools


Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I don't know of a simple proof, but there is a proof where the underlying idea is simple to understand.

Suppose you have a PDA $N$ (deterministic or nondeterministic; doesn't matter) which accepts the language $L_M$, and whose set of states is $S$. And further suppose you have a DFA $M$ with $T$ as its set of states which accepts the language $L_M$.

Conceptually, you can construct a new PDA, whose set of states is the Cartesian product $S \times T$, and awhich "runs" both the PDA and the DFA in parallel. A transition from state $(s_i,t_j)$ to state $(s_p,t_q)$ does whatever the PDA does when transitioning from state $s_i$ to $s_p$, but also takes the appropriate transition from $t_j$ to $t_q$.

An accept state in this new PDA is any state which corresponds to an accept state in both $M$ and $N$. Then this PDA should, assuming we get the details right, accept the language $L_M \cap L_N$.

There are a lot of details that you need to get right, which makes the proof fairly technical. So it's not a short proof. But it's simple to understand the idea behind it.

If you want to understand how this works, I would suggest trying to write a reasonably formal proof that the intersection of two regular languages is regular using a similar construction.

And as an additional exercise: Why can't you use this technique to prove that the intersection of two context-free languages is context-free?


Context-free grammar for $a^ib^ic^id^{3i}$

You can use the pumping lemma to show that this language is not context-free.
Suppose it is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = a^nb^nc^nd^{3n}$. $u$ can be written $u = vwxyz$ with:

$|wxy| \leq n$
$|wy| > 0$
$\forall k \in \mathbb{N}, vw^kxy^kz\in L$.

Now using the first condition, $wxy$ can be written with at most two letters from the initial four. You can take it from here to find a contradiction.


What is the difference between caching, buffering and paging? Expecting a detailed answer on the OS level

Paging, caching, and buffering are too broad topics to cover in a single post. Briefly, they serve different purposes:

Operating systems use paging as a memory management scheme. A computer stores and retrieves data from secondary storage (usually HDD) for use in main memory (RAM). For example, virtual memory implementations use paging.

Page caching, on the other hand, is a part of the main memory (say RAM) where you store frequently accesses pages since retrieving from HDD slower than retrieving from the main memory. Please note, I am talking about only page caches. There is for example HDD caches, CPU caches, Web server caches. But all of them have the same goal: to speed up data access.

Buffering typically used for data transfer between OS or program and external devices, Input/Output (keyboard, printer, etc).

In some sense caches and buffers are somewhat similar, both for storing temporary data for read/write speedup. However, buffers are usually associated with a certain device (printer, keyboard, or even a particular file). Two different buffers are used for two different files, while raw data from both files may be stored in a single cache. Unlike caches buffers contain metainformation about files or devices. Buffers usually short-lived but caches may live as long as OS or program runs.

This is just very brief information. For further details you may Google and find tons of information on this subject. Or just get a good book on OS.


Find one-variable recursive formula for running time of Karatsuba multiplication

The recurrence with two variables $n,m$ is as what you have obtained:

$$T(n, m) = 3T(n/2, m/2) + O(\max(n,m))$$

Assume $n = \Omega(m)$. We have

$$T(n, m) = 3T(n/2, m/2) + O(n)$$

Although the master theorem cannot be applied directly, if you expand this recurrence, then you will eventually identify the patterns and the result:

$$T(n, m) = 3T(n/2, m/2) + O(n) = \cdots = \sum_{k=?}^{k=?} (3/2)^{k} \cdot O(n) + c \cdot T(n/m,1) = \cdots$$
Please find out $c$ and the range of $k$, and fill the gaps.

There is a method to reduce the two variables $n,m$ recurrence to a single one:

  Assume $n = \max(n,m)$ and pre-append $n-m$ $0$'s to the integer with less bits.

The problem is this will yield a different time complexity from that given above. This can be seen from an extreme example: $1$-bit $\times$ $O(n)$-bit.


How can I tell who is a truth teller and who is a liar?

Here are some hints to get you started. Admittedly, this question isn't that easy.

Part (a): Suppose that there are exactly $n/2$ truth-tellers and $n/2$ deceivers. Show that the deceivers have a strategy in which what a goblin A says about a goblin B depends only on whether they both have the same nature. Draw the conclusions.

Part (b): Pair the goblins up. Show that for some pairwise responses, it is safe to get rid of both goblins. Explain why it is useful to have a majority of truth-tellers.

Part (c): This part should be clear enough.


Find hamming codewords in r=2^k dimensions

I completely misunderstood Misha's answer. Here is my updated understanding of the equivalent problem. All quotes are from his answer.

Let $S = \{0,1\}^{r-1}$, $|S| = 2^{r-1}$ bit arrays, each bit array has length $r-1$.
Let $S_i = \{x\ |\ x \in S\ and\ x_i = 1\}$, where $x_i$ is the $i^{th}$ bit of bit array $x$. We set the $i^{th}$ bit of array $x$ to $1$.

An even number of bit arrays is always chosen from $S_i$. If initially an odd number of bit arrays is chosen, then choose the bit array corresponding to the parity bit as well, so finally an even number of bit arrays are chosen.

This corroborates with Misha's answer, as the coordinates numbered off exactly match the parity bit coverage.

  Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.

Repeat step 2 for all $i \in [1,\ r-1]$.

Let $A$ be the set of chosen bit arrays from $S_i$ for all $i$, where chosen bit arrays are hamming codewords.

The hamming code is an even parity bit, single error correction code for arrays of length $r - 1$.

The following describes single error correction, where "vertex" means "bit arrays", and "picked vertices" means "bit array in $A$" or "hamming codeword".

  If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.

This solves the equivalent problem of finding set $A$.

Now, to solve the original problem.

(I originally thought the $00\dots00^{\text{th}}$ coordinate was for double error detection, and was wondering why I needed that in a single error correction code. I was completely wrong.)

  Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex.

This is equivalent to prepending a new bit, $b$, for each bit array within the set $A$ that we derived earlier, thus making all bit arrays have length $r$.

Arbitrarily let bit $b = 0$. Define $A_{new} = \{b\ x_1\dots x_{r-1}\ |\ x \in A\}$.

Let $B = \{\neg b\ x_1\dots x_{r-1}\ |\ x \in A\}$, so all bit arrays are same as $A_{new}$, except for every array, the $b$ bit is flipped.

This fits well with Misha's explanation that bit arrays from $A_{new}$ and $B$ are nearly-identical, because the only difference is the flipped bit $b$.

  the $00\dots00^{\text{th}}$ coordinate of a vertex [...] is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.

This solves the original problem, such that the $2^r/r$ bit arrays are in sets $A_{new}$ and $B$.


In a linear code, the minimum distance is the same as the minimum weight of a non-zero codeword. It's a nice exercise to prove this, and reduces the computation time quadratically.

Computing the minimum distance of a code given the generator matrix (or the parity check matrix) is NP-hard, that is, given a generator matrix (or a parity check matrix) and an integer $w$, it is NP-complete to determine whether the minimum distance of the code generated by the matrix is at most $w$. The task could become easier if the code has some structure, but for arbitrary codes it is quite difficult.


A PDA to recognize the Intersection of two regular languages?

If the intersection is empty then you have to show that some PDA accepts the empty language. That doesn't sound too difficult.

More generally, every NFA is secretly a PDA (showing that every regular language is context-free), and so if you can construct an NFA for your language then you can easily convert it to a PDA.


We can build it up from smaller pieces:

How can you describe sequences made up of only a's? Just $a^*$

How about sequences made up of only a's and b's? $(a|b)^*$
These can be thought of as turning the knob from A to B, then going back to A, etc..

Similarly for b's and c's:  $(b|c)^*$

Say we stay in positions A-B for a while, and then we want to go to C; this can be expressed as:
$(a|b)^*  (bb^*)  c$

Now let's say we stay in positions A-B for a while, and then we switch to C, and stay in B-C for a while. Then the rule means we must pass through b at least once:
${(a|b)^*  (bb^*)  (b|c)^*}$

Now what if we want to stay in A-B, then switch to C, stay in B-C, then switch back to A, and stay in A-B again? ${(a|b)^*  (bb^*)  (b|c)^* (bb^*) (a|b)^*}$

The pattern starts to appear. You can see that whenever we want to transition we need to stick a $bb^*$ in between.

To get full sequences, we could try:

$(\,  (a|b)^*(bb^*) \, | \, (c|b)^*(bb^*) \, )^*$
which you can check, obeys the transition rule. The only problem is that this assumes the sequence ends with b.  To fix that, we just include options to end at a or c; naming the above as
$$
L=(\,  (a|b)^*(bb^*) \, | \, (c|b)^*(bb^*) \, )^*,
$$
we arrive at an answer:  $L\, | \,La^* \,| \,Lc^*$


Calculating modulus of large non-factored numbers

The map from natural numbers to the ring of remainders is a homomorphism, which is a way to say that it has all sorts of nice properties with respect to operations + and *. In particular, a+b has the same remainder as mod_p(a) + mod_p(b) and a*b, the same as mod_p(a)*mod_p(b).

So, mod_p(a_0 + a_1*2^8 + a_2*2^16 + ...) = mod_p(mod_p(a_0) + mod_p(a_1)*mod_p(2^8) + mod_p(a_2)*mod_p(2^16) + ...).


For fixed $c$ (i.e., we consider $c$ as a constant) this is trivially solvable in time $n^cm$ which is polynomial in $n$, however, if $k$ is part of the input, then $n^k$ would be considered exponential in $k$.

Vertex cover is solvable in $2^k \cdot n^{O(1)}$.


What is the real advantage of Google's new Fuchsia operating system kernel?

From what I understand you are asking what are the technical benefits of zircon over linux?

First of all zircon is a micro kernel as opposed to the linux monolithic kernel. So lets look at some of the advantages of an microkernel over a monolith:

Segmentation, a micro kernel has a very segmented model and drivers live outside of the kernel. That means you have more control over what those pesky vendors put into your kernel to slow it down. Security is increased because you can protect the core of the kernels functions from god knows what monster code the vendors wanna chuck in there as drivers.
Size, a micro can be way way smaller in size and together with the modularity of the micro kernel can help so you have the same kernel on everything from your phone, laptop to a IoT thermometer.
Speed, although in practice you have a lot of microkernels that are slower than monoliths because all the communication between the pieces of the kernel create a lot of overhead, you could have speedier communication with things like File I/O, network traffic and other components by the lack of context switching between kernel space and user space (think >10Gbps networks).
Control over updates. One of the biggest problem with Android is fragmentation, if you wanna build an app you have 839274326 versions of Android out there, for which version do you build your app? Also you have vendors not applying patches because they need to build their version with all the modifications they put in. If you had a really segmented core that you could update without affecting the vendor modifications that would be a big win for Google.
Real-time operation, they probably want a pure real time implementation because it goes well with their data collection needs.


Minimax algorithm when all the options are the same

Shaull's answer is absolutely correct, and by referring Zermelo's theorem it is pointing in the right direction.

However, beyond the observations done on the rationality of your opponent, the point here is that Minimax is pretty good for strategical games where a single mistake could lead to a disaster, e.g., chess ---where just overlooking a single move can lead to checkmate. On the other hand, if no such strategical flaws are likely (e.g., Omweso and I think Quoridor also to some extent) then Monte-Carlo sampling is a much better option.

For a thorough study on the topic, see:

Raghuram Ramanujan and Bart Selman. Trade-Offs in Sampling-Based Adversarial Planning. Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling. Freiburg, Germany, 2011.

(which was actually awarded a honorable mention for best student paper). In this case, the purpose of such algorithm is to follow good lines of action instead of preventing a loss. Monte-Carlo sampling is also the best option to use in case your branching factor is too large (so that minimax and any of its variants such as alpha-beta become infeasible), e.g., Go.

Be aware however, that one of the options used much often in Monte-Carlo sampling, UCT, does not seem to be so good in the end. For a good discussion on the topic, see:

Carmel Domshlak, Zohar Feldman. To UCT, or not to UCT?. Proceedings of the Sixth Annual Symposium on Combinatorial Search. Leavenworth, Washington, USA, 2013.

Hope this helps,


Did Wheeler really believe that physics was undecidable?

The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid.

In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable).

To give you an idea how this happens: equality of reals is a map $\mathbb{R} \times \mathbb{R} \to \Sigma$ which is implemented by a Turing machine that takes (Turing machines that compute) reals $x$ and $y$ and returns a non-boolean truth value represented by a Turing machine which terminates if, and only if, $x \neq y$.

In contrast, equality of natural numbers is decidable. It is a map $\mathbb{N} \times \mathbb{N} \to \{0,1\}$ which takes two natural numbers and outputs either $0$ or $1$, depending on whether they are equal.

As far as physcists are concerned, I would be careful about learning computability theory from them. I wouldn't want anyone to learn physics from me.


Bellman-Ford - is number of interations greater than diameter?

In the Bellman–Ford algorithm, after $t$ iterations the array contains, for any two nodes, the minimal walk of length at most $t$ connecting them. Assuming your graph doesn't have negative weights, the shortest walk between any two vertices will be a path, and so its length would be at most the diameter. Therefore there is no need to run the algorithm beyond $d$ iterations.


What is the knowledge required to understand the formal definition of a Turing Machine?

All you need is some basic discrete mathematics.

The states, tape alphabet and states are finite sets; the blank symbol, starting state, accepting state and rejecting state are elements of one of those sets.

The transition function is a function on finite sets, defined using a Cartesian product of finite sets.

The tape is a sequence of elements of one of the sets.


Regularization term moving the hyperbolic plane

The point of the regularization term is usually to keep the network from overfitting by keeping the weights vector with low absolute values or sparse. Therefore I would say a sum of all weights is not a good regularization term, because even extreme positive and negative weights can sum to zero. In the regularization term, the $L_2$, $L_1$, $L_0$ norms are commonly used (read about it here).

In a side note, if I understood you correctly, I would suggest to avoid imagining the target function (or loss function) as a hyperbolic plane, since usually DNNs contain non linear activation functions like ReLU.


Why is this verifier for primality wrong?

Here are the semantics of a verifier for primality. The verifier gets two inputs, an integer $n$ and a witness $w$. The following two properties must hold"

Soundness: if the verifier accepts $n$ and $w$, then $n$ is prime.
Completeness: if $n$ is prime, then there is a witness $w$ such that the verifier accepts $n$ and $w$.

We also usually ask that the verifier run in polynomial time in $n$.

Your verifier isn't sound (take any odd composite $n$ and $d = 2$) but is complete.

However, if you flip the return value, you do get a verifier for compositeness:

If $d \mid n$ and $1 < d < n$ then $n$ is composite.
If $n$ is composite then there exists $d$ such that $d \mid n$ and $1 < d < n$.

The notion of a verifier is asymmetric. Your verifier works for compositeness, but not for its complement, which is primality.


Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?

Your argument shows that
$$
\sum_{i=1}^{\lg n} 2^{i-1} = O(n\lg n).
$$
It doesn't show the matching lower bound, which is actually false.


To show that a grammar is unambiguous, it is enough to show that for any expression E, there is only one "last step" possible in any derivation of E. It is the case here : the last rule is given by the last symbol of the expression (either +, *, or a terminal a), and the parentheses will prevent any ambiguity.
Of course you can not write "$abc+$" in your grammar, it has to be $(ab)c+$ or $a(bc)+$, but this is implicit when you define a grammar.

For instance, $a(bc+)*(bc)*+$ is not ambiguous : the last rule is given by the last symbol +, and so on... the expression it represents is $(a*(b+c))+(b*c)$


It depends on the definition. Some definitions of a deterministic finite automaton (DFA) are a quadruplet $(Q, \delta, q_0, F)$ where $Q$ is the set of states and $q_0 \in Q$ is the initial state. Therefore, it must be defined.
However, the definition of non-deterministic finite automaton (NFA) is sometimes seen as a quadruplet $(Q, \Delta, I, F)$ where $Q$ is the set of states and $I\subset Q$ is the set of initial states. Here, you can chose $I = \emptyset$ and get an automaton without initial state.
Since a DFA can be seen as a special case of a NFA, it is not necessary for an automaton to have an initial state. In both cases (DFA and NFA), the language recognized by an automaton without initial state is $\emptyset$.


Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard

Let A be the empty language. It is trivially reducible to, say 3SAT: transform any input into the formula $a \land \lnot a$. But only the empty language is reducible to the empty language, thus A is not NP-hard.

If P = NP, then any nontrivial language is NP-hard, thus it will be really hard to find counterexamples where both A and its complement are nonempty.


Tackling overlearning neural network issue

Yes, it is alright to repeat training data, as long as each one is repeated an equal number of times: this does not violate assumptions.  That said, it smells to me like a kludge.  If you have no theoretical understanding of why the approach was failing without that adjustment, then just randomly tweaking things (like repeating points) in hopes that it will happen to succeed does not seem like the right approach.

Be careful that you don't do cross-validation on the result after repeating samples.  You need to separate the test set from the training set before repeating.  If you repeat samples, then do cross-validation, there is a high likelihood that most or all samples in the test set will also appear in the training set (due to the repetition) and thus you'll be over-fitting -- the cross-validation results won't be meaningful in that case.


Pattern matching on function application

If you are given that $g(f(x))=x$ for all $x$ and $f,g$ are pure functions, then your proposed transformation works.  However, the condition $f(g(x))=x$ is not sufficient: consider $f,g:\mathbb{N} \to \mathbb{N}$ given by $g(x)=2x$, $f(x)=\lfloor x/2 \rfloor$.  (I'm not sure which your g . f notation was intended to capture.)


Yes, it's correct that you can convert between base-2 and base-3 representation (in either direction) in polynomial time.  Thus, that would be a good example of two encodings that are polynomially related.

You can't convert from binary (base-2) to unary representation in polynomial time; it causes an exponential increase in the size of the instance.  That's probably what is meant by "expensive".


Characterize the Equivalence Classes of a Language

The notion of equivalence is that of indistinguishability. Given a language $L \subseteq \Sigma^{\ast}$, we say that strings $x$ and $y$ are indistinguishable wrt. $L$, written $x \, I_L \, y$, if we have that for every $z \in \Sigma^{\ast}$ that $xz \in L \iff yz \in L$.

The Myhill-Nerode theorem tells us that a language $L$ is a regular language iff the set of equivalence classes of $I_L$ is finite.

To show that $L = \{ w \in \{ a,b\}^{\ast} \mid \exists n \geq 0. w = a^n b^n \}$ is not regular, we simply have to show that the set of equivalence classes of $I_L$ is infinite.

So consider a string $w \in \{ a,b\}^{\ast}$. The set of all strings $w$ not of the form $a^i b^j$ where $i \geq j$ forms an equivalence class, since for no $z$ we have that $w_1 z \in L$ if $w$ is not of the form $a^i b^j$.

Moreover, every string of the form $a^i b^j$ where $i \geq j$ can only be indistinguishable from itself. So every such string forms an equivalence class containing only this single string.

Consequently, $I_L$ has infinitely many equivalence classes.


Find k maximum numbers from a heap of size n in O(klog(k)) time

Hint: Each time you perform one iteration of your loop, how much does the size of $B$ increase?  Each time you perform one iteration of your loop, how many numbers are added to $A$?

You terminate once $k$ integers have been added to $A$... so how many times will the loop iterate?  What does this tell you about how large $B$ can get?  What does that say about the running time of your algorithm?

(I am giving only a hint, so you can have the pleasure of working out the answer on your own.)


Let $G = (V,E)$ be an infinite digraph: $E \subset \mathbb{N}\times \mathbb{N}$ is decidable. Does it imply that $\delta (i,j)$ is a total function?

This function is not necessarily total, even when the set of edges is decidable. Note that you haven't proved it, but simply showed why we can't directly use some classic algorithm for finite graphs, though perhaps some smarter algorithm exists?

Imagine $G$ is a "universal configuration graph". To explain what i mean, lets first discuss what is the configuration graph of a Turing machine $M$. Given a Turing machine $M$, let $G_{M}$ denote the graph whose vertices are configurations of the form $C=(q,s_1,s_2)$ where $q$ is the machine state, and $s_1,s_2$ are the strings to the right and left of the read/write head correspondingly (the first symbol of $s_2$ is the current symbol under examination). $(C_1,C_2)\in E$ if you can go from $C_1$ to $C_2$ in a single step. The number of vertices in $G_M$ is countable (since we go over all possible contents of the tape).

Now I want to define $G$ as $\bigcup\limits_{M} G_{M}$. The graph $G$ is the disjoint union of all possible configuration graphs (so we go over all Turing machines, note that the number of vertices remains countable). To identify each vertex (configuration) in $G$ to the graph $G_{M}$ it's belonging to, we can add the encoding of the machine to the description of each vertex. The set of edges of $G$ is clearly decidable, since given two vertices
$v_1=\left(\langle M\rangle , C_1\right)$ and $v_2=\left(\langle M'\rangle , C_2\right)$, we check if $\langle M\rangle=\langle M' \rangle$, and if so, we check if $M$'s transition function allows us to move from $C_1$ to $C_2$ in a single step.

If reachability in $G$ is decidable, then you can decide the halting problem. Given a Turing machine $M$ and input $x$, check if the accepting configuration of $M$ is reachable from the initial configuration of $M$ on input $x$ (for simplicity, you can assume there is a unique accepting configuration).


Is every language over any alphabets is accepted by automata?

Suppose that $\mathcal{M}$ is any kind of machine model in which every machine has a finite description, say as a binary string. The model can be more powerful than mere Turing machines – for example, it could be Turing machines with access to an oracle for the halting problem.

Since every machine has a finite description as a binary string, there are only countably many machines, and so countably many languages they accept. Since there are uncountably many languages, there must be some language not accepted by any $\mathcal{M}$-machine. In fact, most languages aren't, in the sense that a random language would not be accepted by any $\mathcal{M}$-machine.

The only way out is if machines do not have a finite description. But this is not what we usually understand by machine. An example of such a "machine" is one in which an arbitrary language is hardwired. Such machines can, by definition, accept all languages, but they are not so interesting mathematically.


The Hamming codes are perfect codes. This means that balls of radius $(d-1)/2$ (where $d$ is the minimal distance) centered around the codewords partition the space. In particular, the covering radius is $(d-1)/2$.


Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S )

To show the grammar is ambiguous, you must find a string derived by the grammar which has two or more distinct parse trees. I think we have a few options here. One that should work is S + S*:
                   S
                  /
                 /
   S            S--+
  /            / \
 /            /   \
S--+         S     S
 \            \
  \            \
   S--S         *
    \
     \
      *

These derivations are fundamentally different (not just different orderings of the same derivation) and so the string S + S* is fundamentally ambiguous. Does it mean (S + S)* or does it mean S + (S*)?


Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

There is a grammar of size $O(\log n)$ using repeated squaring.

Let's start with the simpler case $n = 2^m$:
$$
\begin{align*}
&S \to a B_0 B_1 \dots B_{m-1} \\
&B_i \to A_i | \epsilon && (0 \leq i \leq m-1) \\
&A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq m-1) \\
&A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$ and $B_i \to a^{2^i}|\epsilon$.

More generally, suppose $n-1 = 2^{d_0} + 2^{d_1} + \cdots + 2^{d_\ell}$, where $d_0 > d_1 > \cdots > d_\ell$. The corresponding grammar is:
$$
\begin{align*}
&S \to a B_{d_0} | a C_0 B_{d_1} | a C_1 B_{d_2} | \cdots | a C_{\ell-1} B_{d_\ell} | aC_\ell  \\
&C_j \to C_{j-1} A_{d_j} && (1 \leq j \leq \ell) \\
&C_0 \to A_{d_0} \\
&B_i \to B_{i-1} A_{i-1} | B_{i-1} && (1 \leq i \leq d_0) \\
&B_0 \to \epsilon \\
&A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq d_0) \\
&A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$, $B_i \to \{a^k : 0 \leq k < 2^i\}$ and $C_j \to a^{2^{d_0} + \cdots + 2^{d_j}}$.

As an extra property, both grammars are unambiguous.


Replacement of a substring with another substring in a string

There is no proper, rigorous definition.  Or, rather, you can make multiple definitions.  All are valid.  You could provide a rigorous definition for replacing the first match, or a rigorous definition for replacing all matches.  Mathematics doesn't tell you which definition is "proper" or "best" or "most useful".
A meta-comment: You might to be expecting more from mathematics than it can bear.  Mathematics doesn't tell you what is "proper" or "right" or "best".  It gives us a model for a world: if the structure satisfies such-and-such conditions, then it has such-and-such properties.  You'll have to decide what conditions are appropriate, or what properties you want to have.


Consensus protocols in multiplayer video games

Section IX of the following paper proposes a variant of your idea:

OpenConflict: preventing real time map hacks in online games.  Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh.  IEEE Security & Privacy 2011.

The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a client's status messages for consistency.  Your scheme differs only by having other clients do the same analysis.  (Their proposal also has some extra hashing and signatures and cryptography, which can probably be ignored for your purposes.)

Their scheme is basically a more sophisticated version of what you propose: rather than requiring everything to be broadcast, it only has to be uploaded to the server at the end of the game.  This has two advantages: (a) it significantly reduces network traffic, because they upload to the server rather than broadcasting to everyone; (b) by using commitments and hashes, they don't have to broadcast the full status messages to all other players on-the-fly; instead, it's enough to batch up all of those messages and upload them at the end (all that they need to broadcast at each step is just a commitment/signed hash, which will be much smaller and thus much more efficient to broadcast).  I wouldn't be surprised if they were already familiar with your proposal, but considered it too trivial and too inefficient, and so wrote only about a more sophisticated version that is less obvious and more efficient.

I recommend you take a look at the following book:

Exploiting Online Games: Cheating Massively Distributed Systems.  Greg Hoglund and Gary McGraw.  Addison-Wesley.


A certain submatrix of the correlation polytope

Every quadratic multilinear polynomial can be written as
$$
a_0 + \sum_i a_{ii} x_i + \sum_{i \neq j} a_{ij} x_i x_j =
a_0 + \sum_i a_{ii} x_i^2 + \sum_{i \neq j} a_{ij} x_i x_j,
$$
using the fact that $x_i^2 = x_i$ for every $x_i \in \{0,1\}$. This clearly equals $a_0 + \sum_{ij} A_{ij} x_i x_j$, which in turn is the same as what you wrote.

Regarding the matrix $M_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.


Why this Nondeterministic Finite accept this string?

When a transition doesn't exist for current (state, input) pair, the NFA halts and the computation path rejects the input string. Or if an empty string transition is defined, it can be used to go into a garbage state for undefined transitions and the computation path rejects the string. See What does an NFA do if there's no transition with the correct symbol? for really good information.

In addition, this source that says the string is not accepted: http://people.cs.nctu.edu.tw/~wgtzeng/courses/FL2013SpringUnder/2.%20Finite%20automata.pdf slide 15.


Lossless data compression must make some messages longer?

You are missing an important nuance. How would you know if the message is only 2 bits, or if it's part of a bigger message? For that, you must also encode a bit that says that the message starts, and a bit that says it ends. This bit should be a new symbol, because 1 and 0 are already used. If you introduce such a symbol and then re-encode everything to binary, you will end up with an even longer code.


Is there a correlation of zip compression ratio and density of information provided by a text?

Shannon's noisless coding theorem is the formal statement that the size of an optimally compressed data stream is equivalent to the amount of information in that data stream.

But you are also right that the definition of "amount of information" depends on your probability model for the data stream.  If you have a correct table of letter probabilities before you start the compression then Huffman coding gets within a constant factor of optimal, Arithmetic coding gets even closer to optimal.  But if there are correlations between neighboring symbols (which there are in real human produced text) you can do better by choosing codes for pairs of letters.  And you can do even better if you look at triples, and so on.  Additionally, you typically don't have a very good probabilistic model of your data stream when you start, so you need to adaptively construct the probability table and then assign variable length symbols depending on the probabilities as you learn more.

The kinds of compression used in zip/gzip,  compress, and 7-zip are all variants of Lempel-Ziv coding.  Lempel-Ziv coding is adaptive, builds probability tables over varying length chunks of letters, and is optimal in the sense that given an infinite random stream that is ergodic (the probabilities are stable over time) it will, in the limit, adaptively find a table that takes into account correlations over arbitrary distances, and then use that table to produce a stream that approaches optimally coded.

Of course, neither children's books nor novels for adults are infinitely long ergodic random processes (although some of them may seem like they are) so the conditions of the theorems don't hold.

Here's an interesting interview with Jacob Ziv where he talks a little about the universality of Lempel-Ziv coding:
http://www.ieeeghn.org/wiki/index.php/Oral-History:Jacob_Ziv#Lempel-Ziv_algorithm.2C_Viterbi_algorithm.2C_and_Ziv-Zakai_bound.


Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

It's not possible.

A reversible computation always corresponds to a permutation of the state space. When working on three bits, a Toffoli corresponds to a single swap in the state space (it swaps 111 for 110). When working on four or more bits, a Toffoli gate always corresponds to an even number of swaps in the state space. This is because it performs a swap for each possible state of the uninvolved bits, and there are an even number of such states. For example, a Toffoli applied to the first three bits of a four bit system swaps 111_0 for 110_0 and swaps 111_1 for 110_1. Even number of swaps.

Permutations have a parity. A permutation that can be implemented with an even number of swaps has even parity. Permutations that can be implemented with an odd number of swaps have odd parity. The composition of two even parity permutations will also be an even parity permutation. Odd parity permutations can't be reached by composing even parity permutations.

This means the Toffoli gate can't perform a CCCNOT without workspace, because the action of the CCCNOT on the state space is an odd parity permutation but the action of the Toffoli is an even parity permutation. The single CNOT and NOT gates have the same problem. You need an extra work bit (or quantum gates like $X^{1/8}$) to break the parity barrier.


maximum matching in a bipartite graph for solving a chess rook maximization problem

This is a well known problem in competitive programming. When you put a rook in a row and a column, you can no longer have any other rooks in that row and in that column. That is, you are matching rows to column, such that each row gets at most one column and each column gets at most one row. Sounds like bipartite matching?

What do the holes represent? Positions where you cannot place rooks. These are row-column pairs that cannot be matched. I will leave it as an exercise for you to figure out what that means in the bipartite graph of rows and columns.


Is the set of CFGs that contain all odd and even length words Turing-decidable?

The problem is that you interpret e.g. "grammars that generate all even length strings" as "grammars that generate only all even length strings", which is wrong. If you look at it this way, the intersection you are looking for is grammars that generate all even length strings and all odd length strings, i.e., grammars that generate all of $\Sigma^*$


Both $\emptyset$ and $\{0,1\}^*$ are in $P$, and therefore they are also in $NP \supseteq P$ and $co-NP \supseteq P$.


Interval tree: find all intervals containing a given interval

Hint: A (non-root) interval can only contain I if its parent contains I.

For the algorithm in the pseudo-code below, TestInterval is not called for the same vertex twice, so the complexity is $O(n)$.

Consider the subtree S consisting of all nodes which TestInterval is called on. At every node in S which is not a leaf node, an interval must have been added to intervalContainingI (and k incremented). A binary tree with k non-leaf nodes can have at most $k+1$ leaf nodes. Therefore the complexity is in fact $O(k)$.

vector<int> intervalsContainingI;

void TestInterval(interval x)
{
    if (x.start <= I.start && x.end >= I.end)
    {
        intervalsContainingI.push_back(x);
        if (Exists(x.leftChild))
        {
            TestInterval(x.leftChild);
        }
        if (Exists(x.rightChild)
        {
             TestInterval(x.rightChild);
        }
    }
}

TestInterval(root_node);


Reason for differences between ways of specifying trees

You're right. You need less space to save a tree with an adjacency list. But (like Dave Clarke's comment already says) there are more interesting fields, not only the space-complexity. Sometimes it is useful to spend more space to reduce for example the time-complexity of a problem. An easy example makes that point clear: If you represent your tree by saving the children of each node, you can compute the children of a given point in constant time (just looking which children are saved for the particular node). If you otherwise save the parent of each node, then you have to check every node in your tree (except the given point) to compute the children of a given node. In the first case you need more space and less time. In the second case you need less space, but more time.


DCFL with prefix property have LR(0) grammar?

Your grammar is $\mathrm{LR}(0)$ by adding a $\mathrm{\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\$$ when constructing the $\mathrm{LR}(0)$ automaton (and it is a standard construction).

Omitting syntactical purposes, every DCFL $\mathrm{L}$ can be parsed by an $\mathrm{LR}(0)$ grammar for $\mathrm{L}\$$. What makes $\mathrm{LR}(k)$ ($k>0$) more practical is that it may include more syntactical information which is very important in compiler design. Otherwise, all these techniques would never be used in practice. In that case, $\mathrm{LL}(k)$ with local manipulation for expressions would be used instead, even with prohibitive cost of time and space.


Usually it's stored as an adjacency list. Which is basically a linked list for every single node. So the linked list of a node u contains every node v such that (u,v) is a valid edge of the tree.

The adjacency list of this tree would be:

 1 ->
 3 -> 1, 4
 4 ->
 5 -> 3, 8
 7 ->
 8 -> 7, 10
10 ->

It can also be stored using an adjacency matrix. But that's used when the nodes of the tree are less (since it requires more memory). Adjacency list is better for sparse graphs.


Guessing the smallest unique positive integer

There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability

$$ 0.839286 \cdot (0.543689)^{\textstyle i}$$

where 0.543689 is the solution of $x^3 + x^2 + x = 1$.

For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.


Interview question (constant-time algorithm, ILP)

After glancing at http://www.lume.ufrgs.br/bitstream/handle/10183/66091/000870881.pdf;sequence=1,

I think I figured it out.

Something along the lines of, wlog, let (a,d) have ratio a/d >= b/e >= c/f.

Then y is capped at d/gcf(e,d) and z is capped at d/gcf(f,d). brute force all possible (y,z) possibilities in constant time, fill in the corresponding x=floor[(G-ey-fz)/d] (constant time), and select the maximum ax+by+cz (constant time). QED.

This solution seems a bit inefficient and although there may be a better constant-time solution out there (particularly, for d>100), it scales well for large G which is all that really matters for this question.


A $\mathrm{No}$ answer means that there is no solution, not that there is a non-solution.

So for Subset-Sum this means there is no subset of the input integers that sum to zero, or to put it another way, every possible (non-trivial) subset has a non-zero sum. Not that there is a subset which doesn't sum to zero.


Your question surprisingly has an answer on stackoverflow, no doubt dating before this site. The question gives an algorithm of time complexity $O(\max(H_1,H_2))$, and claims that it can be improved to $O(\min(H_1,H_2))$.

By the way, oftentimes $O(H_1 + H_2)$ is used for $O(\max(H_1,H_2))$.


Proving there is no polynomial algorithm for independent set

Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies
$$
 |A(G) - \alpha(G)| \leq K,
$$
where $\alpha(G)$ is the maximum size of an independent set in $G$.

We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the assumption $\mathsf{P} \neq \mathsf{NP}$.

Given a graph $G$, let $H$ consist of $2K+1$ disjoint copies of $G$; note that $\alpha(H) = (2K+1) \alpha(G)$. Run $A$ on $H$ to get a value $A(H)$ which satisfies
$$
 |A(H) - \alpha(H)| \leq K \Longrightarrow |A(H) - (2K+1) \alpha(G)| \leq K \Longrightarrow \\
 (2K+1)\alpha(G) \in \{A(H)-K,\ldots,A(H)+K\}.
$$
The set on the right contains $2K+1$ values, exactly one of which is a multiple of $2K+1$, hence we can determine $\alpha(G)$ given $A(H)$.


Does RAM take the copy of the program or does it load programs from the hard disk?

Ram used to load a program because ram is a volatile memory i.e. after. Power cut or after the task is over the data in ram is lost so all the data is saved in. Our hard disk
Here. Copying and loading are equivalent in this case