$L$ is CFL because there is a CFG generating it:

$$
\begin{align}
S&\rightarrow aAc\\
A&\rightarrow aAc \mid BC\\
B&\rightarrow aDb\\
C&\rightarrow bEc\\
D&\rightarrow aDb \mid \epsilon\\
E&\rightarrow bEc \mid \epsilon
\end{align}
$$

$L$ is not DCFL. To prove this, we give some lemmas firstly:

  Lemma 1.
  $$
\begin{align}
L &=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}\\
&=\{a^x b^y c^{|x-y|+2+z}\mid x,y\ge 2, z\text{ is even},0\le z\le x+y-|x-y|-4\}.
\end{align}
$$

Proof. Let $L'=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}$. Easy to see $L\subseteq L'$. Now let $a^xb^yc^z\in L'$, then we can choose $m=(x+y-z)/2, n=(x-y+z)/2, k=(y-x+z)/2$. Because $x+y+z$ is even, $m,n,k$ are all integers. Because $|x-y|+2\le z\le x+y-2$, we have $m,n,k\ge 1$, so $a^xb^yc^z\in L$. As a result, $L=L'$.

  Lemma 2. $M =\{a^x b^y c^{|x-y|+2}d^z\mid x,y\ge 2, z\text{ is even},z\le x+y-|x-y|-4\}$ is not context-free.

Proof. Suppose it is context-free, according to Odgen's lemma, there exists some $p\ge 1$ such that $s=a^{p+2}b^{p+2}c^2d^{2p}\in M$ can be written as $s=uvwrt$, such that

the number of $d$s in $vwr$ is at most $p$ (i.e. we mark all $d$s),
there is at least one $d$ in $vr$, and
for all $q\ge 0$, $uv^qwr^qt\in M$.

From condition 3, $v$ and $r$ each contains at most one character. Together with condition 2, as $q$ grows, the number of $d$s in $uv^qwr^qt$ grows infinitely. To satisfy the condition $z\le x+y-|x-y|-4=2\min\{x,y\}-4$, the number of $a$ and $b$ must both grow, i.e. $a$ and $b$ must both in $vr$. However, $vr$ contains at most two characters, while $d$ is already in it, $vr$ cannot contain both $a$ and $b$, a contradiction.

Now let's come back to $L$. Suppose there is a DPDA $D$ accepting $L$, we create two copies $D_1$ and $D_2$ of $D$ and change the input character $c$ in $D_2$ to $d$. We then construct a new PDA $P$ as follows:

The states of $P$ are the union of states of $D_1$ and $D_2$. The start state of $P$ is the start state of $D_1$. The accepting states of $P$ are the accepting states of $D_2$.
For a transition in $D_1$, if the destination is an accepting state in $D_1$, change the destination to the corresponding state in $D_2$. Other transitions keep unchanged.

Now run $P$ on a string $a^xb^yc^{|x-y|+2}d^z\in M$. According to lemma 1, after reading $a^xb^yc^{|x-y|+2}$, it enters a state in $D_2$ for the first time. Since $a^xb^yc^{|x-y|+2+z}\in L$ according to lemma 1, $P$ will finally accept.

On the other hand, if a string $s$ is accepted by $P$, let $s=s_1s_2$ where after reading $s_1$, $P$ enters a state in $D_2$ for the first time. According to lemma 1, $s_1$ must have the form $a^xb^yc^{|x-y|+2}$ ($x,y\ge 2$). Also, $s_2$ does not contain $c$, and after changing all $d$s in $s_2$ to $c$s, $s_1s_2$ belongs to $L$. This means $s$ must have the form $a^xb^yc^{|x-y|+2}d^z$ where $x+y+|x-y|+2+z$ is even (i.e. $z$ is even) and $|x-y|+2+z\le x+y-2$ (i.e. $z\le x+y-|x-y|-4$). Hence $s\in M$.

As a result, $P$ recognizes $M$, which contradicts to lemma 2.


Is square numbers written in binary a regular language?

Here is a high-tech solution. Denote your language by $L$. Szalay showed that
$$
L \cap 10^*10^*1 = \{ 10^n10^{n+2}1 : n \geq 0 \} \cup \{110001, 1000010001\}.
$$
From here it's pretty easy to show that $L$ is not regular, by reduction to $\{a^nb^n : n \geq 0\}$.


Nearest neighbor search in latitude/longitude coordinates

First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate.
You've already worked out that if all you need is nearest neighbour on points, then using 3D distance as a proxy for great circle distance is probably the most efficient approach. To be honest, this is probably the best solution for your specific problem, but not if you had to do distance queries involving non-point geometry (e.g. "find me all lines within 200km of this point").
The usual practice for spatial indexing in GIS is to use some variant on a bounding volume hierarchy.
In Cartesian space, that would mean an R-tree, and in geographic space, you would use circles of a sphere or ellipsoid as the bounding volume shape. In the case of a binary tree index, you can use a great circle as the splitting criteria for each node.


Number of substrings with exactly k distinct characters

atMost(A, K) computes the number of substrings with at most K distinct characters.
A substring with at most K distinct characters has either exactly K, or at most K-1, distinct characters. So, atMost(A, K) - atMost(A, K-1) is the number of substrings with exactly K distinct characters.


You have $(\neg A \wedge \neg C) \vee \text{some_big_expression} $ and you want to show that it's equivalent to $\text{some_big_expression} $.

Simplification rules won't necessarily lead you from the first expression to the second expression. There are systematic ways to test whether two expressions are equivalent, by applying De Morgan's laws in a certain way and other simplification rules (such as $\neg (\neg P) \longrightarrow P$) to transform a formula into equivalent formulas until you reach a disjunctive normal form (or other normal forms, if you apply the laws in a different way). But this doesn't directly get you from one expression to the other.

Another way to prove that two formulas are equivalent is to show that the first implies the second and the second implies the first. Here, it's obvious that
$\text{some_big_expression}$ implies $(\neg A \wedge \neg C) \vee \text{some_big_expression}$, so the difficulty is to prove the opposite implication: $(\neg A \wedge \neg C) \vee \text{some_big_expression}$ implies $\text{some_big_expression}$. Think about what this means: you want to prove that if $P$ or $Q$ holds then $Q$ holds — in other words, if you already know $Q$, then you don't need to prove $P$, it's already implied by $Q$. This is a consequence of two properties of disjunction, idempotency and monotonicity: if $Q \Rightarrow P$ then $(P \vee Q) \Rightarrow (P \vee P) \Rightarrow P$.

So what's left is to prove that $\neg A \wedge \neg C$ implies $(\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C)$. I'll let you finish. Hint: the right-hand side has both $B$ and $\neg B$, what can you say about these?

Second exercise: use De Morgan's laws to grind the first formula into the second one.


It is actually $LL(3)$. Try to prove it yourself.


How can, e.g., Dijkstra find all shortest paths in linear time?

As you (almost) observe, there can be $2^{\Theta(n)}$ shortest paths between a pair of vertices:

       *   *           *
      / \ / \ /     \ / \
    s*   *   *  ...  *   *t
      \ / \ /       / \ /
       *   *           *

With $k$ cycles, this graph has $3k+1$ vertices and there are $2^k = 2^{n/3-1}$ shortest $s$–$t$ paths: you can go clockwise or anticlockwise around each cycle, independently of the others.

The simple answer to your question is that you are mistaken.  It is impossible for any algorithm to output all shortest paths in linear time (time $O(n)$), just because it is impossible to output an exponential amount of data in a polynomial number of steps: a Turing machine can only write one character of output per step.

Outputting all shortest paths is an example of an enumeration problem. Typically, we use different measures for these problems because it seems "unfair" to say that an algorithm is slow just because it has a lot of work to do.  The usual standard for enumeration algorithms is to look at the number of steps between each successive output. Using modified Dijkstra will (I assume) have polynomial delay: there's a constant $c$ such that, for any large enough graph on $n$ vertices, the algorithm will output some shortest path after at most $n^c$ steps and, after each output, there will be at most $n^c$ more steps before the algorithm outputs another shortest path or terminates.


Round Robin, confused about how to processes are handled related to arrival order

In round-robin scheduling, every process is put into a big queue as soon as they arrive. When a process gets to the front of the queue, it is treated for some fixed number of time-steps (in your case 3 steps, as I suppose is also what's meant by the text "Quantum = 3"). If the process is not finished when its time is up, it gets stowed in the back of the queue. So when Process 5 is done at step 12, it gets stowed in the back of the queue, behind all the processes that arrived at step 11.


Show that the Halting problem is reducible to its complement

Suppose $HALT$ was many one reducible to $\overline{HALT}$. Let the mapping function be $f$. We construct a machine $D$. It takes input $\langle M,w \rangle$ obtains the string $f(\langle M,w \rangle)=\langle M^{'},w^{'} \rangle$. $D$ simulates $ M$ on $w$ and  $M^{'}$ on $w^{'}$. If the first simulation ends  $D$ accepts if second simulation ends/halts it rejects. $D$ is a decider for $HALT$ which is not possible.


Efficient way to find matching date ranges?

Your question is not clear.

I am assuming you have 1000 date intervals in some set $A$ and another 1000 in set $B$ and you wish to find which intervals in $B$ lie completely inside some interval in $A$.

For an interval [x,y] in $B$, search points $x$ and $y$ in the segment tree built on $A$ and find sets that overlap.

Look up Segment tree.

Its stores line segments with starting point and end point.
You can modify it to store start date and end date.

https://en.wikipedia.org/wiki/Segment_tree


Floating point bitwise comparator. If f1 and f2 are floating point numbers with the following properties can we always say f1 > f2?

If we study the expression for a floating point number, $$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}),$$
and pay attention to the sum $\sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}$, we note that
$$0 \leq \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k} \leq \sum\limits_{k=1}^{23} 2^{-k} < \sum\limits_{k=1}^\infty 2^{-k} = 1,$$
where the last equality is formed by evaluating the geometric series. Thus we find that
$$2^{e-127} \leq2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}) < 2^{e-127}\cdot 2$$
Thus if $s = 0$ and $e_1 > e_2$ we find that $f_2 < 2^{e_2 - 127} \cdot 2 \leq 2^{e_1 - 127} \leq f_1$.
Note that if $s = 1$ and $e_1 > e_2$, the signs are reversed and we actually have $f_2 > f_1$. But always $|f_1| > |f_2|$.

The extended result of the above is that if we ignore the effects of denormal numbers, NaNs, infinities and say that $-0 < 0$, we have
$$f_1 < f_2 \iff n_1 < n_2,$$
where $n_1, n_2$ are the bit patterns of $f_1, f_2$ interpreted as $w$-bit two's complement integers.


Because it's common for programs to access data sequentially.

This arrangement of the cache will make sequential data access more efficient.  In particular, when the program accesses the first word, that word and subsequent words in the same cache line are all loaded into the cache, so when the program accesses the next word, it will already be cached and access will be very fast.

Any other arrangement would make sequential access slower.


How can Machine Learning be used to find attributes/characteristics of graphs?

ML is not likely to be a good approach for these kinds of problems.  It will probably perform far worse than a hand-designed algorithm.  Current ML is not magic; it is just a form of pattern-matching.


is it always true that the depth of BFS is $\leq$ DFS?

A result about BFS is that what you call the depth of the BFS of a node $v$ is the length of a shortest path from the source to $v$.

Assume the exists an instance where the depth of the DFS $<$ BFS. Then we have a path from the source to $v$ that has length strictly smaller (the path taken by the DFS to reach $v$) than the length of a shortest path from the source to $v$ (the path taken by the BFS), which is impossible.

This argument by contradiction shows that depth BFS $\leq$ DFS, for any graph.


Solving recurrence relation when cost of all combining steps is constrained

Form a recursion tree. The root represents $T(n)$, and has weight $f(n)$. It has $k$ children, the edges are labelled $f(d_1),\ldots,f(d_k)$, and the children itself have weights $f(d_1)f(n),\ldots,f(d_k)f(n)$; they correspond to $T(d_1n),\ldots,T(d_kn)$. Each child has its own $k$ children, and so on, only we delete nodes corresponding to $T(m)$ for $m < 1$. Note that the weight of each node is $f(n)$ times the weights of all edges from the node to the root. The total running time, assuming a base case around $1$, is the sum of all weights in the tree.

When $\sum_{i=1}^k f(d_i) < 1$, we can compute the total weight of the infinite tree (without the pruning described above) as
$$
f(n) \sum_{t=0}^\infty (f(d_1) + \cdots + f(d_k))^t = \Theta(f(n));
$$
here $(f(d_1) + \cdots + f(d_k))^t f(n)$ is the total weight at level $t$. Thus in this case we have $T(n) = \Theta(f(n))$.

When $\sum_{i=1}^k f(d_i) = 1$, each full level contributes $f(n)$, and each partial level (where some nodes were pruned) contributes at most $f(n)$. There are $\Omega(\log n)$ full levels and $O(f(n))$ full or partial levels, and we conclude that $T(n) = \Theta(f(n)\log n)$.


Maximum Schedulable Set Zero-Lateness Deadline Scheduling

Use a dynamic programming algorithm to compute an $n \times n$ table $T$, where the entry $T(j,k)$ answers the question: suppose you wish to schedule $j$ out of the first $k$ jobs. What is the earliest time you can complete processing these?

How do we compute $T(j,k+1)$? Either the job $k+1$ is included in the best set of $j$ out of $k+1$ jobs, so $$T(j,k+1) = T(j-1,k) + t_{k+1},$$ or job $k$ is not included in this set, so $$T(j,k+1) = T(j,k).$$ We also have to worry about the deadline. We can do this by making the entries of $T$ where the task is impossible equal to $\infty$, and checking whether we have exceeded the deadline at every step. So the pseudocode for computing the $T(j,k+1)$ entry of the table is

if T[j-1,k] + t[k+1] > d[k+1]
    then T[j,k+1] = T[j,k]
    else T[j,k+1] = min ( T[j,k-1]+t[k+1], T[j,k] )

We initialize by setting $T(j,k) = \infty$ if $j > k$, and $T(1,1) = \infty$ if $t_1 > d_1$, and $T(1,1) = t_1$ otherwise.


Two regular languages over the same alphabet, regular or not regular?

I see several problems.

In your first part you say that, given a regular language $L$, $\overline{L}$ is regular since  $\Sigma^*- L$ is also regular. This is true, but it is implicitly using the fact that regular languages are closed under difference. It is not clear if you're allowed to use that fact as a black box (since it is a more general statement than the one you're trying to prove).

In your second part you are not giving a proof. You are just showing that $L_1 \cup L_2$ is regular when $\Sigma=\{a,b\}$, $L_1 = \{a\}$ and $L_2 = \{ b \}$. What if $\Sigma \neq \{a,b\}$? What if $L_1 \neq \{a \}$?
Your proof needs to work for all possible choices of $\Sigma, L_1,$
 and $L_2$.

Moreover, $L_1 \cup L_2 \neq \{ab\}$ contrarily to what you claim.

Finally, you say that since $\{a\}$ is regular then so is $\{a\}^*$. This is true but it is unclear why you need this.


What is the simplification of AB + BC + (~B)C?

Imo there is a problem in the proposed options. Indeed,

$AB+BC+(\neg B)C=AB+(B+\neg B)C=AB+C$

You can check that also comparing the truth-tables of
$AB+BC+(\neg B)C$ and $AB+C$.


Suppose you have created another array $S$ and stored sum from start to $i$ at $S[i]$. The sum of elements from index $l$ to $r$ inclusive is  $S[r]-S[l-1]$ for $l\ge1$, which takes two lookups and one subtraction, or $S[r]$ for $l=0$, which takes one lookup. So it takes $O(1)$ time.

Suppose you set $arr[k]$ to a new value, where $k=n/3$. Then you have to update $S[k], S[k+1], \cdots, S[n-1]$, which are roughly $n-n/3=2n/3$ numbers. That is, it takes $O(n)$ time. You can figure out all other cases of $k$.

"You can even explain the whole concept of segment trees here." That is exactly the purpose of that article and its follow-ups. Try reading them. Follow the recommendations thereof.


Show that the collection of Turing-recognizable languages is closed under homomorphism

The proof is posted by Anwar Saiah on this post. I quote it here (with its formatting improved).

Given a language $L$ that is Turing recognizable and a TM $M$ that recognizes it and a homomorphism $f$, we build a NTM $M'$ that recognizes $f(L)$.
$M'$ looks like this:
On input $w$ :

Non-deterministicly feed words from $\Sigma^∗$ to $f$ until you obtain $w$.

Run $M$ on $f^{−1}(w)$, if $M$ accepts accept, otherwise reject.

This works because $M'$ is a non-deterministic Turing machine.  A NTM accepts $w$ if there is at least one branch accepting $w$, so if there is any word $x$ such that $f(x)=w$ and $M(x)$ accepts, this will find it and accept.


Ensure a vertex has the highest flow in max-flow algorithm

Add auxiliary nodes 8a, 9a, 10a between nodes 8, 9, 10 and node 11, so that for example we have 8 -> 8a -> 11. Set all the capacities on the (8 -> 8a, 9 -> 9a, and 10 -> 10a) edges to $c = 0$, and run max flow. If there is a solution (if the maximum flow through the graph is equal to the number $n$ of packages to be shipped) then congratulations - we are done. Otherwise, set the capacities to $c = 1$, and go again. And so on until you find the smallest capacity $c^*$ such that the maximum flow is $n$. If the flow through vertex 7 is larger than this capacity $c^*$ then we have a solution, but if not there is no solution. If you continue to increase up to $c = n$ and there is no solution, then the original problem has no solution.

As requested by D.W. I will elaborate on the correctness and efficiency of this solution. The simple method of increasing $c$ by $1$ each time to find $c^*$ can be improved by binary searching instead: as $c$ increases the maximum flow will also increase up to $n$, and therefore we can binary search on the possible values of $c$ in order to find the smallest $c^*$ such that the maximum flow is $n$. This improves the number of calls to a max-flow subroutine from $n$ to $\log n$.
In order to show correctness I will set up some more notation. In any allocation of flow to the graph, let $f_0$ be the flow through the special warehouse, and $f_1, \ldots, f_k$ the flow through the other warehouses. We will call an allocation of flow "feasible" if $f_0 + f_1 + \cdots + f_k = n$ and $f_0 > f_i$ for all $i = 1, \ldots, k$ and "infeasible" otherwise.
Suppose there is no feasible flow. Then no matter how we set $c$ in our algorithm, it will never find a feasible flow either (introducing capacities to vertices only limits the set of solutions). Therefore the algorithm gets the correct answer in this case.
Suppose there is a feasible flow. Out of all possible feasible flows, choose one which minimises $c' = \max_{i = 1, \ldots, k} f_i$. Then there is no feasible flow where $f_i < c'$ for all $i$, and there is a feasible flow where $f_i \leq c'$ for all $i$, and hence our algorithm will arrive at $c^* = c'$. However, the algorithm may not arrive at the same flows: in particular if $g_0, g_1, \ldots, g_k$ are the flows found by the algorithm, we are guaranteed that $g_i \leq c'$ for all $i = 1, \ldots, k$, but we may not have $g_0 > g_i$ for all $i$.
I think this is a problem with the algorithm actually: it finds $c^* = c'$ correctly, but needs some help in order to figure out whether flow through the special node can be made strictly larger. There are some things you could do with the residual graph here, or you could use a reduction to a circulation problem with lower bounds on capacities: use the algorithm above, but as a final step introduce the constraint that the flow through the special node must be at least $c^* + 1$, and check for a solution.


Mapping reducibility vs. Turing reducibility

You can define a notion of reducibility which will ensure that if $A$ reduces to $B$ and $B$ is recognizable then so is $A$. The definition allows an oracle call to $B$, but the semantics are different: if the contents of the oracle tape are in $B$ then the machine continues, and otherwise it gets stuck (never halts).

The problem with this definition is that it is pretty weak. While the other property (with recognizability replaced by decidability) still holds, it never helps you that $B$ is decidable. Compare this with mapping reducibility: there you are using the full power of decidability.

Still, the definition could be useful. Assuming you aren't the first to come up with this idea, the only conclusion is that this definition doesn't lead to a nice enough theory. It's also possible that you came up with a nice concept which you could develop to a nice theory. A third possibility is that a theory has been developed, but I am unaware of it.


How hard is finding the discrete logarithm?

Short answer.
If we formulate an appropriate decision problem version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes NP, coNP, and BQP.

A decision problem version of Discrete Log.
The discrete logarithm problem is most often formulated as a function problem, mapping tuples of integers to another integer. That formulation of the problem is incompatible with the complexity classes P, BPP, NP, and so forth which people prefer to consider, which concern only decision (yes/no) problems. We may consider a decision problem version of the discrete log problem which is effectively equivalent:

  Discrete Log (Decision Problem). Given a prime $N$, a generator $a \in \mathbb Z_N^\times$ of the multiplicative units modulo $N$, an integer $0 < c < N$, and an upper bound $b \in \mathbb N$, determine whether there exists $1 \leqslant L \leqslant b$ such that $a^L \equiv c \pmod{N}$.

This would allow us to actually compute loga(c) modulo N by binary search, if we could efficiently solve it. We may then ask to which complexity classes this problem belongs. Note that we've phrased it as a promise problem: we can extend it to a decision problem by suspending the requirements that $N$ be prime and $a \in \mathbb Z_N^\times$ a generator, but adding the condition that these restrictions hold for any 'YES' instance of the problem.

Discrete Log is in  BQP.
Using Shor's algorithm for computing the discrete logarithm (Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer), we may easily contain Discrete Log in BQP. (To test whether or not $a \in \mathbb Z_N^\times$ actually is a generator, we may use Shor's order-finding algorithm in the same paper, which is the basis for the discrete logarithm algorithm, to find the order of $a$ and compare it against $N-1$.)

Discrete Log is in  NP ∩ coNP.
If it is actually the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, a sufficient certificate either for a 'YES' or a 'NO' instance of the decision problem is the unique integer $0 \leqslant L < N-1$ such that $a^L \equiv c \pmod{N}$. So it suffices to show that we can certify whether or not the conditions on $a$ and $N$ hold. Following Brassard's A note on the complexity of cryptography, if it is both the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, then it is the case that
$$ r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$} $$
by definition (using the fact that $\mathbb Z_N^\times$ has order $N-1$).

A certificate that the constraints on $N$ and $a$ both hold would be a list of the prime factors $q_1, q_2, \ldots$ dividing $N-1$, which will allow us to test the above congruence constraints. (We can test whether each $q_j$ is prime using AKS test if we wish, and test that these are all of the prime factors of $N-1$ by attempting to  find the prime-power factorization of $N-1$ with only those primes.)
A certificate that one of the constraints on $N$ or $a$ fail would be an integer $q$ which divides $N-1$, such that $a^{(N-1)/q} \equiv 1 \pmod{N}$. It isn't necessary to test $q$ for primeness in this case; it immediately implies that the order of $a$ is less than $N-1$, and so it is a generator of the multiplicative group only if $N$ fails to be prime.


Hint 1: For a SAT problem instance with $n$ variables construct a planning problem with $n$ lectures

Hint 2: Each $L_i$ will have $2$ elements

Hint 3: Clauses will be $P_j$, as you have already guessed.


What is the complexity of depth first traversal that don't label nodes as discovered?

For general DAGs, the runtime could indeed be exponential in the depth. Here's an example of a family of such graphs. Let $G_d$ be a digraph comprised of a vertex stacked on a collection of 4-cycles as below, where I've illustrated $G_3$:

In this figure, the edges are directed from top to bottom and every vertex has two children. The number of function calls your algorithm makes (and hence the run time) for a digraph $G_d$ of depth $d$ will satisfy $T(0)=1, T(d)=2T(d-1)+1$, since every $G_d$ is comprised of a root vertex at the top with two overlapping copies of $G_{d-1}$ below it. This recurrence has solution $T(d) = 2^{d+1}-1$, exponential in the depth.


What is a dominator node and a dominator tree?

The reason you give is not exactly right; the definition of a dominator node works from a starting node ($1$ in the example). The only way to reach $3$ from $1$ is to go through $2$ as it is the sole successor node of $1$ in the given graph. Hence $2$ dominates $3$. For the same reason, the nodes $4$ through $6$ are also dominated by $2$ and further, $2$ is the immediate dominator of these nodes (as $1$ dominates $2$) and these nodes are also not dominated by any other nodes than $1$ and $2$:

$3, 4$ and $6$ can be immediately reached from $1$ via $2$.
$5$ can be reached from $2$ either via $3$ or $4$ and thus the only common nodes in these paths to $5$ are $1$ and $2$.

As for applying these concepts to compilers, consider a block-level control flow graph (or CFG for brevity) of a program.
If some block $B$ dominates a block $B'$ in the CFG, then $B$ must have been executed by the time the program reaches $B'$.
This knowledge can be used to remove redundant pieces of code:
Consider the program
a = (something)
b = True

if a == True:
   b = True
else:
   b = False

Here, the block consisting of the first two lines dominates the if-block as well as the else-block.
Hence we know that by the time we jump to the if-block where we would set b to True, it is already set to True by the fist block and thus the compiler could optimize the code by deleting the assignment in the if-block.
You can also detect loops in the code by analyzing if the CFG has edges of the form $B' \to B$ where again $B$ dominates $B'$. Such a path indicates the existence of a loop where $B$ would then represent the loop header while $B'$ is (the last) part of the loop body.


Metaprogramming taken to an unnecessarily high level- how can a program write not just other programs, but a programming language?

Of course we could in principle auto-generate a full programming language. First we'd have to say what being a full programming language actually entails. Here is my attempt:

Syntax of programs.
A notion of value (programs that have no further reductions, but are not stuck).
A reduction relation giving the operational semantic.
A notion of program equality.

All of this can be specified syntactically and generated by a computer. There are tools for part of this purpose, e.g. Ott, but specifying the whole operational semantics of a realistic PL is extremely hard work. One could argue that for example the C used in programming the Linux kernel is only specified by the official GCC version used for compilation of the kernel.

As specifying all of this is such a pain, nobody has so far produced a full-spectrum meta-programming tool. At this point it is not clear how it would look like and how it would help.


I would suggest using bipartite matching.  Have one vertex on the left side for each hidden value you observed.  Have one vertex on the right side for each value in your approximate distribution (your model for the underlying distribution).  Draw an edge between each pair of vertices $(u,v)$, with a weight based on how similar their counts (frequencies) are.  Look for a matching of maximal weight.

This will work if you have no other information about the hidden values, other than their frequencies.  If you also have some information about their order or other side information, I don't know how to use bipartite matching for that.


Preserving connectivity from a vertex by edges deletion

Construct a DFS traversal tree, starting from $v$.

You can remove all edges of v that are not part of the tree.

The tree construction costs $O(|V|+|E|)$.

The identification of the edges that can be removed is $O(deg(v))$.


I am not completely sure about what is causing your confusion, but perhaps this can help:

$a.\bar{b}.0$ can only perform $a$.

$(a.\bar{b}.0)\setminus\{b\}$ can only perform $a$.

$((a.\bar{b}.0)\setminus\{b\})[a\to b]$ can only perform $b$ (i.e. $a$ after substitution).

The full process $((a.\bar{b}.0)\setminus\{b\})[a\to b]\mid(\bar{b}.b.0)+\bar{b}.c.0$ can perform $b$, $\bar b$ (two distinct ways), and $\tau$ (two distinct ways).

Also note that the unrelated process $((a.\bar{b}.0)[a\to b])\setminus\{b\}$ would instead be stuck.


When you get a question about a DAG, the first thing to do is a topological sort.

Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.


What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications

The node of the BST would have  the following structure. $Node \space := (Key,Value)$.
Insert a key-value pair by performing comparisons on the keys of two different pairs.
Avoids nodes with redundant keys  i.e. before insertion, if a node in the BST with the same key value exists, do not insert it. Else if no node with the same key exists, insert the key-value pair.
No change in delete function.
Search returns $null$ if no node's key matches, else return the value associated with the key which was searched.

Then use these  functions assuming that these perform the corresponding operations on a HashTable.
Using a self-balancing BST would give $O(log\space n)$  time complexity for all the three functions defined above. And iterating through all the key-value pairs would simply mean doing an in-order traversal of the BST.


If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered
finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different
count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been
analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as
powerful as Turing machines (TM), up to proper initial encoding of the
problem ... which is a significant constraint. Read the proof in
Wikipedia. But this constraint is apparently only when the input of the
TM is to be encoded in the counters. This result appears in a 1967
book by Minsky, Computation. For off-line TM, taking their input on
a separate tape, there is no such problem.

So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.

The PushDown Automaton is an off-line machine since the
input is from a normal read-only tape. The encoding suggested in the proof (step 2 of
the proof) TM allows it to simulate a PDA with only two bowl
symbols. The gist of the construction is to consider the PDA stack as
representing a number in base $n$, where $n$ is the cardinality of the
stack alphabet. Instead, you use one bowl symbol to represent the
stack number in unary notation (just use a very big bowl). Actually,
you simplify by first using a stack with only two symbols, to use
binary notation before making it unary in the bowl.  The remaining
bowl symbol is used for book-keeping while simulating the binary stack with unary notation.  Read it from wikipedia, it is
quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.


In "real mode" on the x86, an address is 32 bits long. The higher 16 bits can be considered the segment address, while the lower 16 bits are the address within the segment. But it's a bit more complicated than having $2^{16}$ segments of $2^{16}$ addresses each.

If you have a 16-bit address, then you're able to address $2^{16} = 65,536$ different locations. If each of those is a byte, you have 65,536 bytes, or 64KB, of addressable memory. So a segment is at most 64KB long.

To get the actual address, the segment address is effectively shifted left by four bits, then added to the address within the segment. This does, as you've noted, mean that the addresses are not unique! The address 0x0000.00FF is the same as the address 0x000F.000F in this system. Segments can, and frequently do, overlap. And this isn't considered a problem, because in "real mode", there's no protection whatsoever. Segments are just a convenience; the CPU doesn't care if you want to write to opposite ends of memory in completely different segments.

This also limits the total amount of addressable memory to $2^{20}$ bytes, rather than the $2^{32}$ you would expect with an address of that length. But this is also by design: the 8086 has only 20 address pins. So despite the apparent clumsiness of this system, it ended up working out well.


Classes of outer totalistic cellular automata

Here is a fairly old link, which only lists a few classes specifically, but it might be a place to start.

I'd agree with David Eppstein that a longer list might not be all that useful.  There's no quick way to tell for sure whether a given CA rule is Class 4, except in the really simple cases.  In many cases, with enough work you may be able to design persistent structures that could support universal computation.


What are some applications of computing the permanent of a matrix?

Valiant proved that the permanent is $\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete problems.


How to find partition set of a Partition Problem using its decision problem

Here is what you would do if instead of PARTITION you had SUBSET-SUM. Given a set $S$ and a target $T$, repeat the following process:

Pick some $x \in S$.
If $S \setminus \{x\}$ has a subset summing to $T$, remove $x$ from $S$ and go back to 1.
Otherwise, remove $x$ from $S$ and replace $T$ with $T - x$. Mark $x$ and go back to 1.

The set of all marked elements at the end of the algorithm is an answer.

This approach doesn't work for PARTITION (why?), but perhaps it helps figuring out how reductions of this sort work. One idea to try for PARTITION is merging elements (replacing $x,y$ with $x+y$). I'll let you work out the details.


What do we know about NP ∩ co-NP and its relation to NPI?

The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI strictly contains (NP ∩ co-NP) - P (note that every language in NP ∩ co-NP is in P ∪ NPI). This is your option (4).

In summary, assuming P ≠ NP and NP ≠ co-NP, we get this:

[source]


Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?

The two languages aren't equal. However both $K$ and $K'$ are undecidable.

Proof:

We know that:
$K = \{ \langle M , v \rangle | M$ halts on $v$ }. Let us construct another language: $K'' = \{ \langle M , \langle M\rangle \rangle | M$ halts on $\langle M \rangle \}$. Note that $K'' \subset K$ because we replaced $v$ by $\langle M \rangle$ (encoding of $M$). Also note the similarity of $K'$ and  $K''$.

If you prove that $K'$ is undecidable, we can conclude that $K$ is undecidable.

You might have proved that $K'$ is undecidable.


How to construct the found path in bidirectional search

Let me give this question a try. I am not sure I do fully understand it so I was considering to post a comment but in the end, I preferred to try an explanation. Hope it helps!

Raphael already suggested a solution (so I voted up his comment) which works even if you only store states instead of nodes. To make it clear:

states: those in the original problem. These are unique
nodes: those enumerated by your search algorithm (bidirectional breadth-first search in your case). As stated in your book "two different nodes can contain the same world state, if that state is generated via two different search paths" so that it is very likely to have more nodes than states (since the former distinguish states by the different paths ---which can be exponentially large--- that lead to the same state).

Obviously, the path from the start state $s$ to the target $t$ is computed by concatenating the paths from $s$ to $n$ and from $n$ to $t$ where $n$ is the node that was found in the hash table of the opposite search.

Now, assuming you are using a consistent-heuristic function (a heuristic function $h (n)$ is said to be consistent if and only if it satisfies the triangular inequality $h(n) \leq c(n,m) + h(m)$ where $c(n,m)$ is the cost of the operator from node $n$ to one of its offsprings $m$) or no heuristic function at all (so that your BFS is a blind search) let me suggest the following procedure:

Let me assume wlg that $n$ was generated by the forward search (i.e., from the start state $s$) and that it was found in the hash table of the backward search (i.e., the one issued from the goal node). In this case it suffices to expand the node $n$ and to select any descendant that appears also in the hash table of the backward search. You can do this since you are storing all states (instead of nodes) in both hash tables. No matter of the difference between nodes and states, if you generated $n$ in the backward search (which results from the fact that it is stored in the hash table) it had to be done via one of its parents which can be recovered now as one of its descendants (assuming you are traversing undirected graphs, otherwise just apply the inverse operators to recover the parents). Acting like this you will eventually get to the target node.

The same mechanism applies to the forward search ---i.e., no need to store with each node its path to the start node, just use the closed list implemented as a hash table. Reverse the path obtained in the previous paragraph, concatenate them and there you are a solution path.

If you are not using a consistent heuristic function, then you should store along each node in the hash table its value $g(n)$ ---i.e., the cost of the path from its corresponding root node, either $s$ or $t$. Doing so, the previous procedure is just slightly modified by selecting the parent (now generated as a successor) whose $g$ value is $g(n)-1$. However, this is not even necessary in case you are seeking (as it seems) any path from $s$ to $t$.

Bidirectional search is one of the most intriguing "paradigms" in heuristic search. Noone has already found a simple way that makes it as efficient as in the case of blind search (where it is clearly a winner).

Hope this helps,


How does machine learning relate to artificial intelligence?

Machine Learning is a subset of (the scientific field of) Artificial Intelligence.

What is ML?

Machine Learning is defined by Tom Mitchel:

  A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

Hence: When you write an algorithm that gets better the more data you give it, then you can call it ML.

What is AI but not ML?

SLAM
Path finding: Bellman–Ford algorithm, A* search algorithm, Dijkstra's algorithm
Markov chains
cellular automata
Logic: Although a lot of people (e.g. Pedro Domingos) include logic approaches (e.g. with inverse deduction) in Machine Learning, I would rather say it is AI.

Fuzzy logic (see Fuzzy logic vs AI vs Machine learning vs Deep learning)
Knowledge representation / Formal systems

See also

Difference between machine learning and artificial intelligence


There is a legitimate mathematical question here: find an encoding or $X_1\times X_2\times\cdots\times X_d$. The idea is to use mixed base. As you note, if all sets have cardinality $b$, then you can use base $d$ encoding. If the sets have different cardinalities, then you use a mixed base approach. Suppose $|X_i| = b_i$. The choice of elements $c_i \in X_i$ (say $0 \leq c_i < b_i$) can be encoded as follows:
$$ c_1 + b_1 c_2 + b_1 b_2 c_3 + \cdots + b_1 b_2 \cdots b_{d-1} c_d. $$
Every number in the range $0$ to $b_1 b_2 \cdots b_d - 1$ encodes a unique choice of element from $X_1\times X_2\times\cdots\times X_d$.

There is also a programming question here: how to generate the list. The idea is to use a generalization of a binary counter, familiar for students of amortized complexity. There is an array $c$ of length $d$, where $c_i$ is going to encode a choice of element in $X_i$. At each step, we update this "counter" by increasing it by 1. We start by increasing $c_1$ by 1. If $c_1 < b_1$, everything is fine. Otherwise, there is carry: we set $c_1 = 0$, and increase $c_2$ by 1. And so on. The resulting sequence is a lexicographically ordered list of elements in $X_1\times X_2\times\cdots\times X_d$. The amortized complexity per step (assuming $b_i > 1$ for all $i$) is $O(1)$.

Notice the similarity between the encoding in the first half and the algorithm in the second half.


Are there competitions for integer programming?

There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or the XCSP competition.


Incorrect Answer Trying to Find Hamming Distance

A 010101
D 000111

There are two bits different (namely the bold ones). So the hamming distance is 2.


Computational complexity of counting symbols

Turing machines are a nice model with several advantages, mostly their simplicity, but they are not the first choice when analyzing algorithms. Algorithms are typically implicitly analyzed on the RAM machine model, and in some cases, on the BSS model.

Here are some comments on the computational complexity of counting in various models:

Single-tape Turing machine: These are only considered since it is relatively easy to prove lower bounds on them. They are even less realistic a computation model than multi-tape Turing machines.

Multi-tape Turing machine: It is a standard example in amortized complexity that an increasing counter can be implemented using $O(1)$ amortized bit operations. This is because half the time, only one bit changes, one quarter of the time, only two bits, and so on, for a total number of changed bits which is $1/2 + 2/4 + 3/8 + \cdots = 2$. The Turing machine complexity is linear in that, and so counting can be implemented in $O(n)$.

RAM machine: A RAM machine consists of finitely many registers and a random-access memory. The registers are $O(\log n)$-bits long, where $n$ is the size of the input. Reasonable operations on registers take constant time. In particular, increasing a counter that can count up to $\mathit{poly}(n)$ takes $O(1)$ worst-case time. In particular, your function will run in $O(n)$.

BSS machine: One has to be careful when performing arithmetic on large numbers. On the RAM machine, arithmetic takes constant time only if the magnitude of the operands is $\mathit{poly}(n)$. A BSS machine allows access to special registers which store values in some field, say the real numbers. You can perform constant-time arithmetic and comparisons, but not functions like floor. You are also not allowed to use such values for indexing. (If you don't limit yourself enough, you will soon be solving SAT in polynomial time.) You can think of a BSS machine as accommodating floating-point operations, which in practice take constant time, while ignoring the finite precision involved in them.


First, not all processor architectures stopped at 32 registers. Almost all the RISC architectures that have 32 registers exposed in the instruction set actually have 32 integer registers and 32 more floating point registers (so 64).  (Floating point "add" uses different registers than integer "add".)  The SPARC architecture has register windows.  On the SPARC you can only access 32 integer registers at a time, but the registers act like a stack and you can push and pop new registers 16 at a time.  The Itanium architecture from HP/Intel had 128 integer and 128 floating point registers exposed in the instruction set.  Modern GPUs from NVidia, AMD, Intel, ARM and Imagination Technologies, all expose massive numbers of registers in their register files.  (I know this to be true of the NVidia and Intel architectures, I am not very familiar with the AMD, ARM and Imagination instruction sets, but I think the register files are large there too.)

Second, most modern microprocessors implement register renaming to eliminate unnecessary serialization caused by needing to reuse resources, so the underlying physical register files can be larger (96, 128 or 192 registers on some machines.)  This (and dynamic scheduling) eliminates some of the need for the compiler to generate so many unique register names, while still providing a larger register file to the scheduler.

There are two reasons why it might be difficult to further increase the number of registers exposed in the instruction set.  First, you need to be able to specify the register identifiers in each instruction.  32 registers require a 5 bit register specifier, so 3-address instructions (common on RISC architectures) spend 15 of the 32 instruction bits just to specify the registers.  If you increased that to 6 or 7 bits, then you would have less space to specify opcodes and constants.  GPUs and Itanium have much larger instructions.  Larger instructions come at a cost: you need to use more instruction memory, so your instruction cache behavior is less ideal.

The second reason is access time.  The larger you make a memory the slower it is to access data from it.  (Just in terms of basic physics: the data is stored in 2-dimensional space, so if you are storing $n$ bits, the average distance to a specific bit is $O(\sqrt{n})$.)  A register file is just a small multi-ported memory, and one of the constraints on making it larger is that eventually you would need to start clocking your machine slower to accommodate the larger register file.  Usually in terms of total performance this is a lose.


3-SAT problem with number of clauses equal to number of variables

Let the variant of the 3-SAT problem you describe be called EQUAL-3-SAT, where (following your definition) each clause has at most 3 literals. We prove EQUAL-3-SAT is NP-complete by a reduction from 3-SAT as follows.

Let $\phi$ be an instance of 3-SAT with $n$ variables and $m$ clauses. If $\phi$ is balanced already in the beginning (the case $n=m$), we do nothing. If $n > m$, we introduce a fresh variable $x$ that does not appear anywhere in $\phi$ and add to $\phi$ exactly $n-m+1$ clauses of the form $(x)$, so we have $n=m$, and we are done.

Then, if $n < m$, we can do similar balancing: each addition of a 3-literal clause $(a \vee b \vee c)$, where $a$, $b$ and $c$ are fresh variables, increases $n$ by $3$, and $m$ by $1$. Keep adding this clause to $\phi$ until $n=m$, or the difference between $n$ and $m$ is exactly one or three (if the difference was two, repeating the process once more would balance $\phi$). If the difference is one, adding one more 3-literal clause causes $n=m+1$ thus we use the balancing process of the first step (case $n > m$). If the difference is three, we simply add an 2-clause of the form $(a \vee b)$, increasing $n$ by two and $m$ by one, again giving us $n=m$.

Finally, we observe the new formula is satisfiable if and only if $\phi$ was.


A hash function is a pseudorandom function with a constant range. Ideally, one would like two central properties:

The hash function should be easy (fast) to compute.
The probability that two inputs $x,y$ hash to the same value is roughly $2^{-n}$, where $n$ is the output length.

The second property isn't stated rigorously. There are several ways to state it rigorously:

We can consider an ensemble (collection) of hash functions, and then the probability is over the choice of the hash function.
We can consider some distribution on pairs $x,y$.

The main difference between hash functions and pseudorandom number generators is that a hash function gives a unique value for each input. This is important for applications such as hash tables and message verification:

In hash tables, a hash function is used to choose the location at which an input is put. When you search for the same input, it is important that the hash function puts you in the same location. The pseudorandom property ensures that none of the cells gets to keep too many elements.
In message verification, you are sent separately a message and its hash, and you verify the integrity of the message by comparing its hash to the one given to you. Here the pseudorandom property ensures that it is hard to cheat.

Now to address your specific questions:

Why use a hash function and not an RNG with a set seed and array size?

A hash function has the property that each input is hashed to the same value, which is important in some applications (see above).

One way to guarantee the pseudorandom property is to have an ensemble of pseudorandom functions, and choose one at random; this is like choosing a seed at random. In practice, the seed is chosen at random once and for all, since this simplifies things.

Choosing the random seed ahead of time is OK for many applications. The main drawback is that the adversary gets to see the seed ahead of time, and can use this knowledge to try to cheat. When the hash function is easy to "break", this can actually cause problems. For example, it can allow Denial of Service attacks by sending some server some data which is all hashed to the same index, thus slowing things.

In settings when there is no adversary (say, a hash table used in your own program), a hash function with a fixed seed doesn't suffer from this drawback.

Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?

Collisions are unavoidable, unless you know the input ahead of time. Indeed, if you have more potential inputs than possible outputs (which is usually the case for hash functions), then collisions are bound to occur.

Consider the idealized hash function in which the hash of any given input is chosen completely randomly (but is fixed); such a function is not efficiently computable, but otherwise is an excellent hash function. Even such a function will have collisions. The goal in constructing a hash function is to imitate this behavior while keeping the function easily computable.

Why do we mod with array size at the end? Can't we just restrict the range of the hash function?

You don't want to construct a specialized hash function for each array size. Rather, you obtain such a hash function by taking a canonical hash function and then modding with the array size.

Another way to look at it is that you are restricting the range of the hash function. You constructed your hash function with restricted range by taking a canonical hash function and reducing its output modulo the array size.

What is the difference between a hash table and a pointer?

A hash table is a data structure for storing entries (whatever they are), supporting operations such as insertion, deletion, and lookup. This is rather different from a pointer.

If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?

Even if you know the number of unique keys in advance, you don't necessarily know what they are, and without this information you can't use direct addressing.

Even if you did have a list of unique keys in advance, it is not always easy to construct an efficient direct addressing scheme. Imagine that the input is the set of all binary trees on at most 20 vertices. How do you map such a binary tree to an integer? While such schemes are definitely possible, often it is faster to use a hash function; the overhead due to collisions is negligible compared to the cost of computing a direct addressing scheme.

In the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?

If you don't know ahead of time how many unique keys you have, then you use a dynamic hash table instead of a static one. A dynamic hash table can grow in size, though this is an expensive operation. The hash table is initialized at some fixed size, and once it gets too full, it grows in size; if it gets too empty, it shrinks. For an example, look up the Python implementation of dictionaries (dictionaries are the python name for hash tables).


proof of convergence in arbitrary precision PRNGs

You ask us for a proof this program will always halt for all initial seeds, but no such proof is possible in general.  For instance, if the PRNG always outputs the number 66, then this will never halt (assuming you use big integers).  Obviously that would be a really lousy PRNG, but if you aren't willing to assume that the PRNG is good, then no proof is possible.

On the other hand, if you assume that the PRNG is good (i.e., computationally indistinguishable from truly random values), then this is not really a question about PRNGs.  Indeed, it's not even a question about computer science.  It is a question about whether a particular random walk will eventually return to its starting point.  (As such, this question really belongs on a mathematics site, not CS.SE.)

You ask for a proof that the random walk will never return to its starting point (that the probability of return to the initial point is exactly zero).  I do not think any such proof is possible, because I do not think the statement is actually true.


What are potential pitfalls with having a minimal kernel that runs managed code?

Depending on the language, there can be many development challenges:

Pointers: If a language doesn't have pointers, it will be a challenge to do relatively-easy tasks. For example, you can use pointers to write to VGA memory for printing to the screen. However, in a managed language, you will need some kind of "plug" (from C/C++) to do the same.
Assembly: An OS always needs some assembly. Languages like C#, Java, etc. don't work so well with it, unlike C/C++. In C or C++ you can also have inline assembly which is very, very useful for many tasks. There are MANY cases where this is needed (examples in x86): loading a GDT, loading an IDT, enabling paging, setting up IRQs, etc.
Control: If you are using something like Cosmos, you aren't having full control. Cosmos is a micro-kernel and essentially "bootstraps" your "kernel". You can implement something like Cosmos from scratch if you really wanted to, however, that can take a long, long time.
Overhead: With managed languages, there is A LOT of overhead compared to C or even C++. Things like Cosmos need to implement a lot of things before even a C# hello world kernel can be run. In C, you are ready to go, no real setup needed. In C++, there are just a few things that need to be implemented to use some of C++'s features.
Structures: In C/C++ there are structs which many managed languages do not have, and so, you would need to implement some way of having something like a struct. For example, if you want to load a IDT (Interrupt Descriptor Table), in C/C++, you can create a struct (with a packed attribute), and load it using the x86 ASM instruction lidt. In a managed language, this is much harder to do...

Managed languages, syntax-wise, are easier, however, for many OS related things are many times not very-well suited. That doesn't mean they can't be used, however, something like C/C++ are often recommended.


The following survey states that the result is proved by Ibarra, Jiang, Ravikumar in Information Processing Letters (1988).

Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits. Niedermeier R., Rossmanith, P.,  Information and Computation 118(2), 227-245, 1995.


The number of balanced trees with N node and L leaves

Suppose $BTC[H][N][L]$ shows the number of balanced trees with the height $H$, with $N$ nodes and $L$ leaves. Using the following formula, a dynamic programming algorithm can be developed for the problem:

The recursive part:
$\begin{align*}
BTC[H][N][L] = \sum_{h=0}^H\sum_{n=0}^N\sum_{l=0}^L \qquad&(BTC[h-1][n][l]\times BTC[h-1][N-n][L-l])\\
 +&(BTC[h-1][n][l]\times BTC[h-2][N-n][L-l])\\
 +&(BTC[h-2][n][l]\times BTC[h-1][N-n][L-l])
\end{align*}$

The base cases:
$BTC[h][n][l]=\begin{cases}0 & \text{if $h>\log_2n$ or $l>\frac{n}{2}$ or $n=0$ or $l=0$}\\ 1 & \text{if $h=0$}\end{cases}$


How realistic is the i.i.d assumption in the definition of Shannon's entropy?

No.  Shannon's definition is perfectly general.

There is a special case when the symbols are iid random variables, and you might have seen a formula for that special case (which is indeed simpler), but the definition is fully general.  Note that when we write the entropy $H(X)$, you should take the random variable $X$ to be the entire sequence of symbols.  Then the standard definition applies directly, and doesn't assume that each individual symbol in $X$ is iid.


Featurizing images of different dimensions

Option 1: You can crop the images to the smallest sizes in all dimensions. However, blindly cropping images will cause you to lose important information, if you don't have a region of interest. For example, if you are focusing on faces, it is fine to define a ROI and crop around the face. On the other hand, for example if you are doing pure color-wise comparison of images, you will not know if you are cropping all red pixels from an image, that actually contain valuable information.

Option 2: You can scale them to the largest sizes in all dimensions. However, blindly resizing images might cause you to lose important structural information. For example, if you are doing color-wise comparison, you can upsample the images and the mean of the pixels will not change much. On the other hand, for example  if you are looking for faces in an image, your faces will not be circular but elliptical.

Option 3: You can extend the images to the largest sizes in all dimensions. This introduces additional information if you don't filter it in the following steps. For example, for color comparison, you can fill with value nan and later neglect features which has value nan. You can fill with nan, or -1, or mean, etc.

Option 4: You can define a window to process the images. Imagine that you have an n*n window (say 3*3), and you slide that window on the image and extract features from each window (F1 is from [1:3,1:3] of the image, F2 is from [2:4,1:3] of the image, ...). Thus, the features are independent of the image size. However in this case you need to have a clever way to combine those features, because you will have different number of features from each image.


What formal representation is commonly used to describe compiler optimizations?

There are many compilers, which compile widely different kinds of languages which serve widely different purposes. For example, a database language will have very different optimizations than an array-based language like APL.

Compilers themselves use several intermediate languages, from the input language, to a de-sugared version of the input language, all the way down to "fancy" assembly-like versions. You might check here to get an idea of the intermediate languages involved.

Optimizations happen at each of these stages. In general it only makes sense to state optimizations in terms of a formal execution semantics of the language in question: an optimization must preserve the observational semantics, aka the result of the computation. Ideally you would use the semantics to say something about the execution time as well: typically the number of abstract reduction steps would get lower (in certain cases) after application of the optimization.

Pragmatically, many optimizations of imperative-style languages happen on an intermediate language that looks a lot like LLVM IR. Characteristics include SSA form (no variable repeated in the left-hand-side of an assignment) and three address code (at most one assignment, and one operation per statement).

The function calls, thunks, memory layout and semantics of things like pointers are going to tend to be specific to your language.


The master theorem isn't the appropriate theorem for every recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the well-known identity
$$ \sum_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2). $$
You should think of the master theorem as a tool, not a liability. It is supposed to help you – use it if you need it, but feel free to use any other approach as you see fit. The only cases you absolutely have to apply the master theorem is when answering questions on a homework or a test that say you must use it; in the real world one tends not to limit oneself.


Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)}

Suppose $i=1$ then inner loop get executed $n-2$ times because of $2\leq j\leq n-1$ and $j $increment each step by one, As a result $n-1-2+1=n-2$ times inner loop executed.
If $i=2$ then inner loop executed $n-4$ times ... until $i=\frac{n}{2}$ inner loop executed 1 time.

Value of $i$
#inner loop executed

$i=1$
$n-2$

$i=2$
$n-4$

$i=3$
$ n-6$

...
...

$i=\frac{n}{2}$
$n-(n-1)$

It's equal to following summation:
$\frac{n}{2}\times n-2\sum_{i=1}^{\frac{n}{2}}i=\frac{n^2}{2}-\frac{n\times(\frac{n}{2}+1)}{2}=O(n^2)$


The easiest solution is to use one bit per state for a total of 8 bits:

state1 = 0000 0001
state2 = 0000 0010
...
state8 = 1000 0000

Then you can just bitwise or (or add) them together. Many programming languages have a datastructure for "bitsets" that can help with this, especially if you have more bits than fit in a simple integer. Your example with just 8 states fits in a typical int, so you don't really need such a data structure.


Algorithm for calculating regular divisions of lengths in easy-to-read form

I would shoot for having about the same number of ticks each time, given that the tick values are acceptable. I am interpreting tick values as the constant difference between two tick values. Say you wanted to have about $n$ ticks and you are given a distance $d$. Then your tick values would be about $\frac{d}{n}$. Round this up or down to the nearest acceptable tick value.


Can a type system serve as a proof assistant for foreign functions?

Long story short: no you can't. A foreign function is like a black box and the type you ascribe to it is a promise you make: in the Curry-Howard correspondence that would correspond to adding an axiom to your theory.

That being said, there are ways. In Coq for instance, there are various formalisations of the C standard (e.g. Robbert Krebbers' work). Because you have an explicit representation of C programs and their semantics, you can write your code directly in the proof assistant and it is then possible to prove some of its properties.


Removing edges from a fully connected weighted graph

This is NP-hard by reduction from Set Cover.  The problem remains NP-hard even if edge weights are restricted to $\{1, 3\}$.

In the Set Cover problem, we are given a ground set $U$ containing $m$ elements $x_1, \dots, x_m$, a collection $\mathbf S$ of $n$ subsets $S_1, \dots, S_n$ of $U$, and an integer $k$, and our task is to determine whether there exists some set of at most $k$ of the $n$ sets in $\mathbf S$ whose union contains all $m$ elements in $U$.

First let's frame your problem as a decision problem: Given an edge-weighted undirected graph $G = (V, E)$, a set of $r$ constraints $d(v_{s(i)}, v_{f(i)}) \le M_i$ for $1 \le i \le r$ and an integer $q$, does there exist a subgraph $G'$ of $G$ such that each constraint is satisfied by some path in $G'$ and $G'$ contains at most $q$ edges?

To convert a given Set Cover instance into an instance of this problem:

Create a vertex $t$.
For each element $x_i$, create a vertex $u_i$ and the constraint $d(u_i, t) \le 2$.
For each set $S_j$, create a vertex $v_j$ and the unit-weight edge $v_jt$.
For each $x_i$ that belongs to a set $S_j$, create the unit-weight edge $u_iv_j$.
Add in all possible remaining edges, giving each weight 3.
Set $q$ to $m+k$.

First, suppose the solution to the Set Cover problem is YES.  It is easy to construct a solution to the constructed instance of your problem: For each set $S_j$ not selected by the Set Cover solution, delete the corresponding edge $v_jt$.  For each element $x_i$, choose some set $S_j$ such that $x_i \in S_j$ and $S_j$ was selected by the Set Cover solution (since the solution was YES, such an $S_j$ must exist) and keep the corresponding edge $u_iv_j$; delete all other edges incident on $u_i$.  Finally, delete all weight-3 edges.  Clearly this leaves exactly $m$ edges incident on $u$-vertices, plus at most $k$ edges connecting $v$-vertices to $t$, for a total of at most $q = m+k$ edges.  Each $u_i$ is connected to $t$ by a length-2 path via the vertex $v_j$ corresponding to its chosen containing set $v_j$, so all distance constraints are satisfied.  Thus the solution to the constructed instance of your problem is also YES.

Second, suppose that the solution to the constructed instance of your problem is YES.  Let $G'$ be any such satisfying subgraph.

Since $G'$ satisfies all distance constraints, and no weight-3 edge can participate in any such path, removing any remaining weight-3 edges in $G'$ must produce another valid solution $G''$.

Every $u$-vertex in $G''$ is adjacent to some $v$-vertex that is adjacent to $t$, since the answer to the problem was YES and there are no other paths from $u$-vertices to $t$ of distance $\le 2$.  Suppose some $u_i$ in $G''$ is incident on 2 or more outgoing edges.  All but one of these edges can be removed without violating the $d(u_i, t) \le 2$ constraint.  Let $G'''$ be the graph that results from performing these edge deletions on $G''$: $G'''$ is a valid solution.

Each of the $m$ $u$-vertices in $G'''$ is incident on exactly 1 edge, and since the answer to the problem was YES, the total number of edges in $G'''$ is $\le q = m+k$, so there are at most $k$ other edges in $G'''$.  These can only be edges between $v$-vertices and $t$.  Construct a solution to the original Set Cover problem by selecting the at most $k$ sets corresponding to the $v$-vertices that are adjacent to $t$ in $G'''$: clearly the union of these sets contains all $m$ vertices, so the answer to the original Set Cover problem is also YES.

We have established that a YES answer to each problem implies a YES answer to the other problem, so a NO answer to either problem implies a NO answer to the other one, so the problems are equivalent.  The constructed instance of your problem is easily constructed in polynomial time, so it follows that your problem is NP-hard.


You can use the category of sets as your model of how functional programming works as long as you do not allow general recursive definitions.

To see why general recursion is not valid in the category of sets, consider the following program (written in Haskell):

fix :: (Bool -> Bool) -> Bool
fix f = f (fix f)

If we interpret Bool as any set $B$ with at least two elements (for instance $B = \{0, 1, \bot\}$) then there will be a map $f : B \to B$ which does not have a fixed point (for instance $f(0) = 1$, $f(1) = \bot$, $f(\bot) = 0$). However, fix always computes fixed points.

You can use sets as long as all the recursive definitions are well-founded, i.e., the recursive calls always happen on strictly smaller arguments. Typical fold and map operations on lists and other inductively defined structures are like that.

To model recursion one has to change something. One possibility is to use domains which were invented precisely for this purpose.


If declarative programming is possible at the instruction/action level?

Machine code is imperative, not declarative, so if you want your code to execute on a conventional CPU, at some point there needs to be some code that converts the declarative program to imperative style (e.g., a compiler), and at least some of that code needs to be written imperatively (because at least some of it needs to be written in machine code).  It can't be turtles all the way down.


Proving that it's decidable whether a TM ever moves on the blank input

In order to understand what $M$ does on a blank input, one needs only examine its transition function $\delta$. As mentioned in the question, assume the starting state is $q_0$, then there are two options: either $\delta(q_0,\text{blank})$ moves the head (and then we can reject) or it doesn't move the head, which brings us to two other options: either it remains in state $q_0$ (then we can accept, right?) or it moves to another state, say $q_1$.

But, with $q_1$ the same reasoning applies, and as Raphael suggested, we can't go on with this logic forever since the number of states is bounded by $|Q|$. So after $|Q|$ "steps" of the above reasoning we will have a conclusive answer to the question of whether the head moves or not, and we can accept or reject accordingly. Since we were successful at constructing a decider, this question (and hence the induced language $Aright$) is decidable.


Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

Note if $n<m$, we can write $a^nb^mc^qd^p$ as $a^nb^nb^xc^qd^{x+q}$ where $n,x,q$ are independent of each other. Otherwise, we can write $a^nb^mc^qd^p$ as $a^{m+y}b^mc^yc^pd^p$ where $m,y,p$ are independent of each other.

So the grammar can be $S\rightarrow S_1S_2\mid S_3S_4$, where $S_1$ generates $a^nb^n$, $S_2$ generates $b^xc^qd^{x+q}$, $S_3$ generates $a^{m+y}b^mc^y$, and $S_4$ generates $c^pd^p$. They are all easy to construct.


How do incompressible strings and random strings share the same properties?

The theorem says, in effect, that incompressible strings are a deterministic model of random strings. If you have some property that you can prove using random strings, you can also prove it using incompressible strings instead. If you have some construction involving a random string, you can make it somewhat more explicit using an incompressible string.

Another deterministic model of randomness, which is very useful in theoretical computer science, is expanders. These are models of random graphs with respect to a lot of properties. In many cases, instead of using a random graph you can use an expander. Since we can construct expanders explicitly, this allows us to derandomize many randomized constructions.

While the same cannot be said for incompressible strings, they are useful in some circumstances. Their use in lower bounds is known as the incompressibility method, which I encourage you to look up.


Is there a more efficient encoding, preferably without a database of each valid sudoku setup?

Yes. I can think of an encoding improving your 149-bit encoding of a minimal $9\times 9$ puzzle in 6 or 9 bits, depending on a condition. This is without a database or any register of other solutions or partial boards. Here it goes:

First, you use $4$ bits to encode a number $m$ with a minimal number of appearances in the board. The next $4$ bits encode the actual number $\ell$ of times $m$ appears. The next $7\ell$ bits encode each of the positions in which $m$ appears.

The following $81-\ell$ bits are flags indicating whether the remaining positions have a number or not (you just skip the positions in which $m$ is). Whenever one of these bits is 1, then the next 3 bits indicate which number it is (in the ordered set $\{1,\ldots,9\}$ without $m$). For example, if $m=4$ and the 3 bits are 101, then the number in the corresponding position on the board is the the 5th (counting from 0) in the set $\{1,2,3,5,6,7,8,9\}$, so it is $6$. Numbers $j<m$ will be encoded in binary as $j-1$, while numbers $j>m$ will be encoded as $j-2$. Since we had already written $\ell$ positions, only $3(n-\ell)$ bits will be added to encode the rest of the board in this step.

Thus, the total number of bits required to encode a board using this procedure is $$B=4+4+7\ell+(81-\ell)+3(n-\ell)=89+3\ell+3n.$$

For $n=17$, we note that $\ell$ can be 0 or 1 (in general, $\ell\leq\lfloor n/9\rfloor$). Thus, $B$ can be 140 or 143 depending on whether there's a number not appearing on the board.

It's worth pointing out that Kevin's solution is way better in the general case. This encoding uses at most 149 bits only for $n\in\{17,18,19\}$, or for $n=20$ provided that $\ell=0$. At least it shows a general idea on how to take advantage of the fact that $N=9$ is very close to $2^{\lfloor\log_2N\rfloor}$ (which means we tend to "lose memory" by using 4 bits per value, since 4 bits allow us to express $N=16$ numbers as well.

Example. Consider the following board with $n=17$ clues.

.  .  .   .  .  .   .  1  .
4  .  .   .  .  .   .  .  .
.  2  .   .  .  .   .  .  .

.  .  .   .  5  .   4  .  7
.  .  8   .  .  .   3  .  .
.  .  1   .  9  .   .  .  .

3  .  .   4  .  .   2  .  .
.  5  .   1  .  .   .  .  .
.  .  .   8  .  6   .  .  .

Here, no number does not appear on the board, and numbers 6, 7 and 9 appear only once. We take $m=7$ (0111) and $\ell=1$ (0001). Reading the positions from left to right and then from top to bottom, $m$ appears in the position $36$ (0100100). Thus, our encoding begins with 011100010100100.

Next, we need seven 0s, one 1 and the 3-bit encoding of the number $1$, then a 0 followed by a 1 and the 3-bit encoding of $4$, etc. (0000000100101100). Eventually, we will skip the position where $m=7$ is, and we will encode 8 as 110 (the 6th number counting from 0 on the list ${1,2,3,4,5,6,8,9}$) and 9 as 111. The full encoding goes as follows:

// m=7, l=1 and its position on the board.
011100010100100
// Numbers 1 and 4 at the beginning. Note that 1 is encoded 000, and 4 is 011.
0000000100001011
// Numbers 2 and 5.
0000000001001000000000001100
// Numbers 4 and 8. We skip the appearance of 7 and encode 8 as 110.
010110001110
// 3, 1 and 9. 9 is encoded as 111.
00010100000100001111
// 3, 4, 2, 5, 1, 8, 6 and the last empty cells.
0000101000101100100100011000100000000000111001101000

The complete encoding is 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, and the reader can check the length of that string is indeed 143 :-)


Question about labeling in Dijkstra's Proof of Correctness

Since the algorithm at each step adds to $S$ the vertex with the lowest "d" value, and $y$ is not in $S$, $d[u] \leq d[y]$.


Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part

I suggest using dynamic programming.  Because your graph forms a path, we can use dynamic programming (considering all prefixes of the path), solving once for each candidate for the maximum total weight of the parts.  Details below.
Let $S$ denote the sum of the weights of the cut edges (i.e., the first part of your objective function) and $M$ the maximum total weight of the parts (i.e., the second part of your objective function), so that your goal is to minimize $\lambda S + (1-\lambda) M$.  Define $f(m)$ to be the minimum possible value of $S$, for all covers with $M \le m$.  I'll show below how to  calculate $f(m)$ for any desired $m$.  This  then is sufficient to compute the minimum possible value of $\lambda S + (1-\lambda) M$,  by enumerating all $m$ and  checking  which gives the lowest value  of $\lambda   f(m) + (1-\lambda) m$.
So, let's fix $m$ from here on.  For any $k$ that ends a consecutive interval in $C$, i.e., where $\iota(k) \ne \iota(k+1)$, define $S_*$ by
$$S_* = \sum_{i\le k, \iota(i)\ne \iota(i+1)}   w_e(i,i+1).$$
We will let $A[k]$ denote the minimum possible value of $S_*$, taken over all exact covers that contain an interval that ends at $k$ (i.e., where $\iota(k)\ne \iota(k+1)$) and such that $M\le m$ for this cover.  Note that this depends on only how vertices $0,1,2,\dots,k$ are partitioned by $C$, and doesn't depend on what is done with vertices $k+1,\dots,n-1$.
Now we can write a recurrence relation for $A[k]$:
$$A[k] = \min_t A[t] + w_e(k,k+1),$$
where $t$ ranges over $0 \le t < k$ such that $\sum_{i=t+1}^k w_v(i) \le m$.  Thus, for each $m$, you can fill in the array $A[\cdot]$ in $O(n^2)$ time using dynamic programming.  It's possible to get this down to $O(n \log n)$ time by pre-computing prefix sums for $w_v(\cdot)$ and binary search to find the range of allowable $t$'s, and storing $A[\cdot]$ in a balanced binary tree augmented with minimums stored in each tree node to quickly find the minimum of $A[\cdot]$ over a range of indices.   To get the total running time, we must multiply this by the number of values of $m$ we iterate through.  A trivial upper bound on $M$ is the sum of all vertex weights.
In this way, we obtain an algorithm whose running time is $O(Tn \log n)$ where $T=\sum_v w_v(v)$ is the total of all vertex weights.  In practice, often the running time will be less, as we can iterate through $m$ in increasing order, and once we find a solution whose objective function has value $v$, then there is no need to consider values of $m$ larger than $v/(1-\lambda)$.  As @j_random_hacker points out, we can replace $T$ with $O(n^2)$, if that helps: we only need to consider values of $m$ that are equal to the sum of vertex weights along some interval, and there are only $O(n^2)$ such intervals.
If you want an approximation algorithm, scale all of the vertex weights down by a factor of $c$, and then round to the nearest integer.  This will speed up the algorithm by a factor of $c$, and should approximate the optimal solution to within $\pm (1-\lambda)cn$ (probably better than that in practice).


The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) = 0$ if $\{u,v\} \notin E$.
Two graphs $G,H$ are edge-disjoint if there doesn't exist an edge $\{u,v\}$ which belongs to both of them. That is, $G,H$ are edges-disjoint if there do no exist $u,v$ such that $A_G(u,v) = A_H(u,v) = 1$.
You take it from here.


Regularity of language obtained by interleaving $a,b$

There are several issues here. Let's first see what happens if you need to insert only $a$-s. We will construct an operator $A[r]$ which generates a regular expression for $$\{\sigma_1 a \sigma_2 a \ldots a \sigma_n : \sigma_1 \ldots \sigma_n \in L[r], n \geq 1\}.$$ If $\epsilon \in L[r]$ (which can be determined inductively), then it would need to be added explicitly as an additional final step. The construction is inductive:

$A[\epsilon] = A[\emptyset] = \emptyset$, $A[\sigma] = \sigma$.
$A[r_1 + r_2] = A[r_1] + A[r_2]$.
$A[r_1r_2] = A[r_1] a A[r_2] \stackrel?+ A[r_1] \stackrel?+ A[r_2]$, where the first additional term is present if $\epsilon \in L[r_2]$, and the second if $\epsilon \in L[r_1]$.
$A[r^*] = (A[r]a)^*A[r]$.

When you have both $a$-s and $b$-s the general idea is the same, but you have to keep track of the parity of the generated words. We construct operators $E[r],O[r]$ for extracting only the words of even length and odd length (respectively) in $L[r]$. The construction is inductive:

$E[\epsilon] = \epsilon$, $O[\epsilon] = \emptyset$.
$E[\sigma] = \emptyset$, $O[\sigma] = \sigma$.
$E[\emptyset] = O[\emptyset] = \emptyset$.
$E[r_1 + r_2] = E[r_1] + E[r_2]$, $O[r_1 + r_2] = O[r_1] + O[r_2]$.
$E[r_1r_2] = E[r_1]E[r_2] + O[r_1]O[r_2]$, $O[r_1r_2] = O[r_1]E[r_2] + E[r_1]O[r_2]$.
$E[r^*] = E[r]^*(O[r]E[r]^*O[r])^*E[r]^*$, $O[r^*] = E[r^*] O[r] E[r^*]$.

At this point we have all the ideas required to solve your actual exercise. That's a task for you.


On clarification of intersection of classes definition

Complexity classes are sets of languages. Intersection of sets is intersection of sets.


Is Category Theory useful for learning functional programming?

In a previous answer in the Theoretical Computer Science site, I said that category theory is the "foundation" for type theory.  Here, I would like to say something stronger.  Category theory is type theory.  Conversely, type theory is category theory.  Let me expand on these points.

Category theory is type theory

In any typed formal language, and even in normal mathematics using informal notation, we end up declaring functions with types $f : A \to B$.  Implicit in writing that is the idea that $A$ and $B$ are some things called "types" and $f$ is a "function" from one type to another.  Category theory is the algebraic theory of such "types" and "functions".  (Officially, category theory calls them "objects" and "morphisms" so as to avoid treading on the set-theoretic toes of the traditionalists, but increasingly I see category theorists throwing such caution to the wind and using the more intuitive terms: "type" and "function".  But, be prepared for protests from the traditionalists when you do so.)

We have all been brought up on set theory from high school onwards.  So, we are used to thinking of types such as $A$ and $B$ as sets, and functions such as $f$ as set-theoretic mappings.  If you never thought of them that way, you are in good shape.  You have escaped set-theoretic brain-washing.  Category theory says that there are many kinds of types and many kinds of functions.  So, the idea of types as sets is limiting.  Instead, category theory axiomatizes types and functions in an algebraic way.  Basically, that is what category theory is.  A theory of types and functions.  It does get quite sophisticated, involving high levels of abstraction.  But, if you can learn it, you will acquire a deep understanding of types and functions.

Type theory is category theory

By "type theory," I mean any kind of typed formal language, based on rigid rules of term-formation which make sure that everything type checks.  It turns out that, whenever we work in such a language, we are working in a category-theoretic structure.  Even if we use set-theoretic notations and think set-theoretically, still we end up writing stuff that makes sense categorically.  That is an amazing fact.

Historically, Dana Scott may have been the first to realize this.  He worked on producing semantic models of programming languages based on typed (and untyped) lambda calculus.  The traditional set-theoretic models were inadequate for this purpose, because programming languages involve unrestricted recursion which set theory lacks.  Scott invented a series of semantic models that captured programming phenomena, and came to the realization that typed lambda calculus exactly represented a class of categories called cartesian closed categories.  There are plenty of cartesian closed categories that are not "set-theoretic".  But typed lambda calculus applies to all of them equally.  Scott wrote a nice essay called "Relating theories of lambda calculus" explaining what is going on, parts of which seem to be available on the web.  The original article was published in a volume called "To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism", Academic Press, 1980.  Berry and Curien came to the same realization, probably independently.  They defined a categorical abstract machine (CAM) to use these ideas in implementing functional languages, and the language they implemented was called "CAML" which is the underlying framework of Microsoft's F#.

Standard type constructors like $\times$, $\to$, $List$ etc. are functors.  That means that they not only map types to types, but also functions between types to functions between types.  Polymorphic functions preserve all such functions resulting from functor actions.  Category theory was invented in 1950's by Eilenberg and MacLane precisely to formalize the concept of polymorphic functions.  They called them "natural transformations", "natural" because they are the only ones that you can write in a type-correct way using type variables.  So, one might say that category theory was invented precisely to formalize polymorphic programming languages, even before programming languages came into being!

A set-theoretic traditionalist has no knowledge of the functors and natural transformations that are going on under the surface when he uses set-theoretic notations.  But, as long as he is using the type system faithfully, he is really doing categorical constructions without being aware of them.

All said and done, category theory is the quintessential mathematical theory of types and functions.  So, all programmers can benefit from learning a bit of category theory, especially functional programmers.  Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically.  The "category theory for computer science" books are typically targeted at theoretical computer science students/researchers.  The book by Benjamin Pierce, Basic category theory for computer scientists is perhaps the most readable of them.

However, there are plenty of resources on the web, which are targeted at programmers.  The Haskellwiki page can be a good starting point.  At the Midlands Graduate School, we have lectures on category theory (among others).  Graham Hutton's course was pegged as a "beginner" course, and mine was pegged as an "advanced" course.  But both of them cover essentially the same content, going to different depths.  University of Chalmers has a nice resource page on books and lecture notes from around the world.    The enthusiastic blog site of "sigfpe" also provides a lot of good intuitions from a programmer's point of view.

The basic topics you would want to learn are:

definition of categories, and some examples of categories
functors, and examples of them
natural transformations, and examples of them
definitions of products, coproducts and exponents (function spaces), initial and terminal objects.
adjunctions
monads, algebras and Kleisli categories

My own lecture notes in the Midlands Graduate School covers all these topics except for the last one (monads).  There are plenty of other resources available for monads these days.  So that is not a big loss.

The more mathematics you know, the easier it would be to learn category theory.  Because category theory is a general theory of mathematical structures, it is helpful to know some examples to appreciate what the definitions mean.  (When I learnt category theory, I had to make up my own examples using my knowledge of programming language semantics, because the standard text books only had mathematical examples, which I didn't know anything about.)  Then came the brilliant book by Lambek and Scott called "Introduction to categorical logic" which related category theory to type systems (what they call "logic").  It is now possible to understand category theory just by relating it to type systems even without knowing a lot of examples.  A lot of the resources I mentioned above use this approach to explain category theory.


What does the exact $\mu$-recursive program for minimization look like?

I think you're confused about definitions. What you represented above is bounded minimization where we look for the least number $z$ below a given bound $k$ such that $f(n,z) = 0$. Such bounded minimization can be defined without any extra gadgets, using only primitive recursion.

The so-called $\mu$ operation performs unbounded search. It is not something we can define using primitive recursion. It is a new primitive operation which we add to primitive recursive functions to obtain recursive functions.

That is, if $f$ is a function of several arguments then $\mu(f)$ is a partial function which satisfies
$$
\mu(f)(\vec{n}) = k \iff f(\vec{n},k) = 0 \land \forall j < k, f(n,k) \neq 0.
$$
If there is no such $k$ then $\mu(f)(\vec{n})$ is undefined.

Every primitive recursive function is total. However, $\mu$ allows us to create non-total functions, for instance $\mu(f)(1)$, where $f(n,k) = 1$, is everywhere undefined. Therefore, $\mu$ is not something that can be defined using primitive recursion.

There are various mechanisms that exceed the power of primitive recursion which allow us to define $\mu$. One such is a general recursion, and another is a fixed-point operator.


Why are lambda-abstractions the only terms that are values in the untyped lambda calculus?

There are a number of things going on here:

The language you are talking about has no additional data types, otherwise there would be other kinds of values.
The reduction strategy of the language does not reduce inside lambda abstractions. Both call-by-value and call-by-name conform to this. Otherwise, not every lambda abstraction would be a normal.
One generally considers closed expressions as programs, so there are no free variables, hence the example you present is not considered.

Other terms are not values because they can be reduced or they do not appear in closed programs.

That a lambda abstraction is a value means that it cannot be reduced any further (depending on the reduction strategy).

For open terms, variables are also values.


What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

I believe that the correct formula is
$$
I(A) = \log \frac{1}{\Pr[A]}.
$$

In this case, we have
$$
I(A_i) = \log \frac{4}{\Pr[A]} = \log \frac{1}{\Pr[A]} + \log 4 = I(A) + \log 4.
$$


Is the union of NP Complete language and a finite language (in P) NP Complete?

The answer is yes, and this is a special case of the following statement:

Let $X$, $Y$ be non-trivial languages (ie either empty nor everything) such that the symmetric difference $(X \setminus Y) \cup (X \setminus Y)$ is finite. Then $X \leq Y$ (linear time, constant space manyone reduction).

The reduction just tests whether the input is any of the finitely many values in $(X \setminus Y) \cup (X \setminus Y)$ and proceeds in a hard-coded way there. This takes constant time+space. Otherwise, it copies the input, since $X$ and $Y$ will agree there.

How to use this: For NP-hardness of $A \cup B$, set $X := A$ and $Y := A \cup B$. For NP-membership of $A \cup B$, set $X := A \cup B$ and $Y := A$. Note that the symmetric difference of $A$ and $A \cup B$ is included in $B$, hence if $B$ is finite, so is the symmetric difference.


What is the most efficient way to find bSmooth values in QS?

The most efficient method is to use a sieve; this is why the method is called the quadratic sieve. It should be mentioned, though, that the sieve is just an optimization over Dixon's method, and doesn't affect the asymptotic running time apart from some (multiplicative) lower order terms. For a description of the sieve, you can start with Wikipedia.


Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$

If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align*}
T(\beta) &= 2T(\beta/2) + M(\beta)&\text{given}\\
T(\beta) &= 2T(\beta/2) + \log \beta&\text{given (1)}\\
T(\beta) &= 2\beta - \log (\beta) - 2&\text{inductive hypothesis (2)}\\
T(\beta) &= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&\text{substitute (2) into (1)}\\
T(\beta) &= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&\text{algebra}\\
T(\beta) &= 2\beta - \log (\beta) -2&\text{QED}\\
\end{align*}

So we've proven that if $M(\beta) = \log \beta$ then $T(\beta) = O(\beta)$. However the assignment claims $O(T(\beta)) = M(\beta)\log \beta = \log^2 \beta$. This cannot be true.

If we read between the lines it seems implied that $M = Ω(\beta)$.


As the comments indicated, if the goal is to invent fictional cities, and you allow more three or more conjuncts in a condition, then any SAT problem is reducible to your problem.

Depending on the type of constraints, this is probably a more general problem, called "SAT Modulo Theories" or SMT for short. It's the boolean satisfiability problem, plus the theory of whatever your constraints are.

For example, if you allow inequalities:

Elevation < 200

You now need to decide what kinds of constraints those are. If elevation is an integer, and you allow constraints between properties (e.g. number of subway stations is less than the number of suburbs), then solving the problem is, in general, an integer programming feasibility problem.

But chances are that you don't need to worry about that for your scale. If we allow the closed-world assumption, in the sense that the set of city names and locations etc is fixed, then backtracking search is probably good enough. A small Prolog program will do the job.

Here, I used GNU Prolog, and attached the finite domain solver for elevation:

city(new_york).
city(moscow).
city(london).
city(paris).

location(museum).
location(store).
location(subway).
location(grand_bazaar).

% The lowest city in the world is Jericho, and the highest city
% is La Paz.
elevation(Elevation) :- fd_domain(Elevation, -846, 11975).

satisfying_cities(City, Location, Elevation) :-
    city(City),
    location(Location),
    elevation(Elevation),
    (City = new_york ; \+ Location = museum),
    (\+ City = new_york ; \+ Location = store),
    (City = new_york ; Location = subway),
    (Elevation #\= 100).

And running the query:

?- satisfying_cities(City, Location, Elevation).

gives some answers, the first of which is:

City = new_york
Elevation = _#0(0..99:101..127@)
Location = museum

The FD constraint on elevation is a little hard to read, but it's essentially saying that any elevation between 0 and 99 or 101 and 127 will do.


Random generator considerations in the design of randomized algorithms

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. I have to disagree. What a good pseudurandom sequence ensemble gives you is a guarantee on the performance of the algorithm run a random sequence from the ensemble, compared to a trully random sequence. If you don't have such a guarantee, you can't conclude that the algorithm will work poorly - you just don't know.

Is there any justification of this common practice? It works.

Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Complexity theory suffers from two shortcomings. The first one is that it is very hard to prove anything (for example, P vs. NP is open). The second one is that it is mostly concerned with worst-case analysis. Put together, these two limitations rule out complexity theory as a good model for the behavior of algorithms in practice.


Counting and finding all perfect/maximum matchings in general graphs

Counting the number of perfect matchings in bipartite graphs amounts to computing the permanent of 0–1 matrices, which is $\# P$-complete. It follows that there is a reduction from all the other counting problems you mention (which are all in $\# P$) to this problem. You can compute the number of perfect matchings in planar bipartite graphs, and you can approximate the number of perfect matchings in general bipartite graphs. See for example this survey. Approximating the number of perfect matchings in general graphs is apparently more difficult, see for example this paper or that paper. Both papers mention that their algorithms seem to perform well on random graphs, but not necessarily that well in the worst case.

The problems of counting and of enumerating matchings in graphs are of different kinds, so it's hard to say whether they are "equivalent". Note, however, that if you could enumerate matchings then you could count them. This shows that, in some sense, enumerating is harder than counting. For the case of perfect matchings in bipartite graphs, there appears to be a difference, since you can approximate the number of perfect matchings, but computing them exactly is $\# P$-hard.


Theoretical minimum number of registers for a modern computer?

If you allow direct memory access by memory address, then you do not need any "registers" because you can use memory locations instead. For example, memory at location 0 can be the program counter, at location 1 we have the stack pointer, etc. But that is cheating.

So to prevent ourselves from cheating, let us assume there is no direct memory access, because we could use fixed memory locations as registers. Then we can get away with two registers, a program counter and a stack pointer, as explained in the Wikipedia article on stack machines. The stack is only accessible through the stack pointer, and the program is only accessible through the program counter.

Another possibility is to use counter machines. A two-counter machine is Turing complete, i.e., it can compute whatever Turing machine can. This again is nicely explained in the Wikipedia article on counter machines.