What is difference between Buffering and Spooling with respect to Operating System

There's not really a significant difference.  Spooling uses buffering.  Buffering can be used for other purposes, too.

The second quote you include in your question (I/O overlap, etc.) looks to me like it's not very helpful.  The key question is whether you have one buffer per process (job) or a shared buffer that is common to all jobs.  If you have one buffer per job, obviously they can overlap.  If you have a single buffer for all the jobs, then if one job starts writing to it, other jobs might need to be locked out (depending upon how you implement the buffer).

Don't worry about these words.  Memorizing the names and the terms "buffering" and "spooling" is not important.  What's important is the concept: the idea of storing some data in a temporary space in memory, so that when the recipient is finally ready to use it, it's all there for them in one spot.


Assuming the original instance is not easy in NP-hardness reduction

A polynomial time reduction from PARTITION to a language $L$ is a polynomial time function $f$ such that if $x$ is a Yes instance of PARTITION then $f(x) \in L$, and if $x$ is a No instance of PARTITION then $f(x) \notin L$.
If $x$ is an "easy" instance — belongs to some polynomially solvable class of instances — then $f$ can just solve it, outputting a fixed Yes or No instance of $L$. Therefore you can assume that $x$ is a "hard" instance.


Is this context-free grammar correct for this regular expression?

One way to check whether you have got correct grammar is to use plain English or regular expression to characterize each non-terminals, starting from the more basic blocks.

$$S_4 \to aS_4 \mid bS_4 \mid \epsilon$$
This rule says $S_4$ is the words any words made up by zero or more $a$'s and $b$'s or, what is equivalent, $(a\cup b)^*$.

$$S_3 \to aS_3 \mid \epsilon$$
This rule says $S_3$ is the words any words made up by zero or more $a$'s or what is equivalent, $a^*$.

$$S_2 \to bS_4$$
This rule says $S_2$ is all words that are $b$ followed by zero or more $a$'s or $b$'s or what is equivalent $a(a\cup b)^*$.

$$S_1 \to aS_3bS_4 \mid \epsilon$$
These two rules says $S_1$ is $aa^*b(a\cup b)^*$ or the empty string.

$$S \to S_1 \mid S_2$$
This rule says $S$ is $aa^*b(a\cup b)^*$ or the empty string or $a(a\cup b)^*$.

The given regular expression for $S$ is
$$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*). $$
Can you see the difference between the given regular expression and the above description of $S$? Yes, the extra empty string. That is the single difference.

If the given regular expression is more complex, we might need to design some algorithm and implement it in some programming language. For the simple ones like this, the above step by step analysis should be enough. Be careful, of course.


Limited number of calls to a black box for finding longest path in graph given an access to oracle

Since you can find the actual length of the longest path using binary search, in $\log |V|$ steps, I'll assume you have access to an oracle which tells you the length of the longest path. Given a graph $G$ lets denote the length of the longest path in $G$ by $L(G)$.

If you remove an edge after finding out that it does not affect the length of the longest path in $G$, then you avoid the issue of having to commit to some specific longest path. Suppose you keep iterating over the remaining edges, and for each remainning edge $(u,v)$ you check if
$L(G)=L\left(G\setminus\left\{(u,v)\right\}\right)$. If they are equal, remove $(u,v)$ from $E$ and return to the main loop. When there are no more edges to delete, $E$ consists of a longest path in $G$.

To prove this, let $\mathcal{P}$ be the set of longest paths in $G$. Note that in any iteration $i$ (each iteration consists of removing an edge which does not affect the longest path length), there exists some $P\in\mathcal{P}$ such that $P$ is a path in $G_i$. Using this observation, you can show that when there are no more edges to delete, your graph is a longest path.


Theorem 3 in this paper gives you the algorithm for your case (projection onto a plane). For general dimension the problem is NP-hard.


Express boolean logic operations in zero-one integer linear programming (ILP)

Logical AND: Use the linear constraints $y_1 \ge x_1 + x_2 - 1$, $y_1 \le x_1$, $y_1 \le x_2$, $0 \le y_1 \le 1$, where $y_1$ is constrained to be an integer.  This enforces the desired relationship.  (Pretty neat that you can do it with just linear inequalities, huh?)

Logical OR: Use the linear constraints $y_2 \le x_1 + x_2$, $y_2 \ge x_1$, $y_2 \ge x_2$, $0 \le y_2 \le 1$, where $y_2$ is constrained to be an integer.

Logical NOT: Use $y_3 = 1-x_1$.

Logical implication: To express $y_4 = (x_1 \Rightarrow x_2)$ (i.e., $y_4 = \neg x_1 \lor x_2$), we can adapt the construction for logical OR.  In particular, use the linear constraints $y_4 \le 1-x_1 + x_2$, $y_4 \ge 1-x_1$, $y_4 \ge x_2$, $0 \le y_4 \le 1$, where $y_4$ is constrained to be an integer.

Forced logical implication: To express that $x_1 \Rightarrow x_2$ must hold, simply use the linear constraint $x_1 \le x_2$ (assuming that $x_1$ and $x_2$ are already constrained to boolean values).

XOR: To express $y_5 = x_1 \oplus x_2$ (the exclusive-or of $x_1$ and $x_2$), use linear inequalities $y_5 \le x_1 + x_2$, $y_5 \ge x_1-x_2$, $y_5 \ge x_2-x_1$, $y_5 \le 2-x_1-x_2$, $0 \le y_5 \le 1$, where $y_5$ is constrained to be an integer.

And, as a bonus, one more technique that often helps when formulating problems that contain a mixture of zero-one (boolean) variables and integer variables:

Cast to boolean (version 1): Suppose you have an integer variable $x$, and you want to define $y$ so that $y=1$ if $x \ne 0$ and $y=0$ if $x=0$.  If you additionally know that $0 \le x \le U$, then you can use the linear inequalities $0 \le y \le 1$, $y \le x$, $x \le Uy$; however, this only works if you know an upper and lower bound on $x$.

Alternatively, if you know that $|x| \le U$ (that is, $-U \le x \le U$) for some constant $U$, then you can use the method described here.  This is only applicable if you know an upper bound on $|x|$.

Cast to boolean (version 2): Let's consider the same goal, but now we don't know an upper bound on $x$.  However, assume we do know that $x \ge 0$.  Here's how you might be able to express that constraint in a linear system.  First, introduce a new integer variable $t$.  Add inequalities $0 \le y \le 1$, $y \le x$, $t=x-y$.  Then, choose the objective function so that you minimize $t$.  This only works if you didn't already have an objective function.  If you have $n$ non-negative integer variables $x_1,\dots,x_n$ and you want to cast all of them to booleans, so that $y_i=1$ if $x_i\ge 1$ and $y_i=0$ if $x_i=0$, then you can introduce $n$ variables $t_1,\dots,t_n$ with inequalities $0 \le y_i \le 1$, $y_i \le x_i$, $t_i=x_i-y_i$ and define the objective function to minimize $t_1+\dots + t_n$.  Again, this only works nothing else needs to define an objective function (if, apart from the casts to boolean, you were planning to just check the feasibility of the resulting ILP, not try to minimize/maximize some function of the variables).

For some excellent practice problems and worked examples, I recommend Formulating Integer Linear Programs:
A Rogues' Gallery.


New Idea for accessing memory across an inter-network connected system

This would be an instance of a distributed shared memory architecture.  There's been lots of research on such systems.  I would recommend spending some quality time on Google Scholar to read relevant research papers on those kinds of systems, to learn about what's been tried so far.

You might also be interested in the literature on distributed in-memory databases, caches, and data stores.


All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.


Is $a^n b^n$ an artificial language or does it occur in the real world?

The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.


According to the hint, the number of elements in the levels beyond the first is expected to be
$$
n \cdot (1/2 + 1/4 + \cdots + 1/2^k).
$$
Presumably, $k \approx \log n$, though as we will see, this doesn't really matter.

Let's plug in some numbers to see how this behaves. When $n = 100$ and $k = 10$, we get
$$
100 \cdot (1/2 + 1/4 + \cdots + 1/2^{10}) \approx 99.9.
$$
When $n = 1000$ and $k = 15$, we get
$$
1000 \cdot (1/2 + 1/4 + \cdots + 1/2^{15}) \approx 999.97.
$$
When $n = 10000$ and $k = 20$, we get
$$
10000 \cdot (1/2 + 1/4 + \cdots + 1/2^{20}) \approx 9999.99.
$$
What is happening here? Massaging the formula for the sum of the geometric series, we get
$$
n (1/2 + 1/4 + \cdots + 1/2^k) = n (1 - 1/2^k).
$$
So as $k$ gets larger, the value of this formula gets closer and closer to $n$. Moreover, if $k \geq 1$ (say), then
$$
\frac{n}{2} \leq n (1/2 + 1/4 + \cdots + 1/2^k) \leq n.
$$
So from the point of view of asymptotic analysis, this expression is $\Theta(n)$ rather than $\Theta(n^2)$.


Curry-howard isomorphism in object oriented programming languages

If you only consider terminating functions, then your axiomatisation works :-) Indeed, terminating functions have a resonable notion of equality:
If their return type has decidable equality then the functions have decidable equality.

Regarding your code, it could be rendered in an OOP-like fashion this way

record TopologicalSpace : Set₁ where

  field
     BaseSet  : Set
     Topology : (BaseSet → Boolean) → Boolean

  Empty    = λ (x : BaseSet) → false
  Universe = λ (x : BaseSet) → true

  field
    axiom1   :       Topology Empty    ≡ true
                AND  Topology Universe ≡ true

This is a real programming language whose functions must always terminate: It is Agda; http://learnyouanagda.liamoc.net/

The source for the code can be found here: https://github.com/alhassy/RandomProgramming/blob/master/Agda/TopologicalSpaces.agda


Is this the correct way to use the pumping lemma?

A subset of a regular language could be non-regular, so the entire line of reasoning is flawed. As an example, every non-regular language over $\{0,1\}$ is a subset of the regular language $(0+1)^*$.

Regarding the language $H$, you'd do better writing your proof in paragraph-style rather than as a cryptic list. In addition, you made the following mistakes:

You never mention which $h$ you take.
You don't get to choose the decomposition $h = xyz$. The proof has to work for every such decomposition satisfying the properties given in the lemma ($|xy| \leq n$, where $n$ is the "pumping constant").

Several ways of showing that your original language is not regular are given in this answer.


Your second intuition is correct, the $poly$ refers to the bound on the advice. The first definition of this class (that I can find) is in Karp & Lipton's "Turing Machines that Take Advice" (pdf), and in particular:

  We are mainly interested in $poly$, the collection of all polynomially-bounded functions... (p. 192)

Of course they don't give the reasons for choosing that name, so on the speculative part!

Firstly, it should be clear that $P$ and $poly$, although both derived most immediately from the word polynomial, have rather distinct meanings. $P$ as a name refers to deterministic polynomial time, and as a class is the set of all problems solvable in such. $poly$ however is a bound on the advice function, not a time-complexity statement.

This is where I speculate that the difference in names stems from; $P$ and $poly$ are quite separate concepts and it would only serve to confuse if we were to write $P/P$ - this notation would suggest some idea of $\bigcup_{k} DTIME[n^{k}]/\bigcup_{k} DTIME[n^{k}]$, which is certainly an incorrect impression to gives, whereas $P/poly$ immediately suggest $P$ which has something polynomial attached to it but is different to $P$.


Turing machine with a finite tape after the input word ends

Given the length of the input $n$, you can come up with a bound $N(n)$ on the number of configurations that the Turing machine can have. If the machine hasn't stopped on an input within $N(n)$ time steps, then it will never stop (why?), and you can use this to complete the proof. Details left to you.


Finding maximum clique in a distance matrix created by certain pattern

Although the question lacks some details, I propose my solution to the general version of your problem.

Yes. It really depends on the "pattern" based on which you create the graph. There is an infinite number of patterns. For example, one can propose a simple pattern that makes it easy to find the cliques in linear time:

Pattern 1: There is a link between two vertices if the labels of the vertices are two consecutive numbers.
Clique detection algorithm? Simply list the cliques "{1,2}, {2,3}, ..., {n-1, n}".

Pattern 2: There is a link between two vertices if their distance in the original graph is at most two.
Clique detection algorithm? Np-hard problem.


Are registers stack, per core or per application based?

Each processor has it's own registers. each process has it's own values to the registers which getting stored/reload during context-switch.


Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

Don't make this more complicated than it is. Instead of giving you a full solutions, I will give you a partial solution, which should allow you to work out the details by yourself:

Every TM be turned into a TM that visits its initial state exactly once. To do so, introduce a new state $q^'_0$, which will be the new start state. Then add a $\varepsilon$-transition from $q^'_0$ to $q_0$. This is the only way to "leave" the state $q'_0$.

For this modified machine, a accepting run visits the initial state once, and ends in the accepting state. What is left to do is to modify the machine further, such that it jumps back to $q^'_0$, after the machine was in the accepting state. But you have to assure that when $q^'_0$ is visited the second time, you will jump to a new accepting state. But it's not difficult to record how often you visited a state.

If you want that another state is visited twice, then you can always made a detour in the beginning that visits this state (you record that the machine is in "detour" mode be writing a flag on a special tape). Than you reroute the normal computation, such that if it should visit the requested state it visits a copy of this state. Finally, when accepting, you jump back to the requested state. Conceptually, this is not very different to relabeling the states.


Is there always a Big Oh complexity strictly between any two others?

Yes: take a function in the middle, for some suitable definition of middle. You have a wide choice.

If $O(f) \subset O(g)$ (where the inclusion is strict), then $g \in O(g) \setminus O(f)$ (because if $g \in O(f)$ and $f \in O(g)$ then $\Theta(f) = \Theta(g)$). Take the geometric mean: let $h = \sqrt{f \cdot g}$ (since we're talking about complexity here, I assume the functions are positive).

Then $f \in O(h)$ and $h \in O(g)$ (if this is not immediately obvious, prove it using the definition of $O$), i.e. $O(f) \subseteq O(h) \subseteq O(g)$. If $O(f) = O(h)$ then $g = f \in O(f)$, which is not the case since we assumed $g \notin O(f)$. It remains to prove that $O(h) \ne O(g)$, and we'll have $O(f) \subset O(h) \subset (g)$.

If $O(h) = O(g)$ then $g \in O(h)$, i.e. there exists $A$ and $C \gt 0$ such that $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. Then $g(x) \le C^2 f(x)$ (take the square and divide by $g(x)$; again, I assume positive functions), thus $g \in O(f)$, which goes against our initial assumption. The hypothesis $O(h) = O(g)$ leads to a contradiction, which concludes the proof.


I will answer your first question.

By definition, a matching $A$ is male-optimal if for any male $m$ and stable matching $C$, $A(m) \succeq_m C(m)$, that is, $m$ prefers $A(m)$ at least as much as $C(m)$, where $A(m)$ is the female assigned to $m$ by $A$.

Similarly, by definition, a matching $B$ is male-pessimal if for any male $m$ and stable matching $C$, $B(m) \preceq_m C(m)$.

Now suppose that $A$ is male-optimal, $B$ is male-pessimal, and $A = B$. Take any male $m$ and any stable matching $C$. By definition, $A(m) \succeq_m C(m) \succeq_m B(m) = A(m)$, and so $C(m) = A(m)$. In other words, $C = A$, and so the stable matching is unique.


Myhill-Nerode style characterization of CFL?

David S. Wise provides in his paper A strong pumping lemma for context-free languages a strong pumping lemma which is equivalent to being context-free. He also provides an additional equivalent condition (property 3 on page 362) which he claims could be viewed as an analog of the Myhill-Nerode theorem. As an application of the latter, he shows that $\{ a^nba^{mn} : m,n > 0 \}$ cannot be expressed as a finite intersection of context-free languages.

More information on the strong pumping lemma appears in one of my answers.


Space complexity of boolean circuit evaluation

This general question is captured by the concept of graph pebbling. Orient the edges of the circuit so that they point away from the leaves and toward the root. A pebbling of the graph is a series of moves, in the course of which pebbles are added to and removed from vertices (at most one pebble per vertex!), according to the following rules:

A pebble can always be removed.
A node $v$ can be pebbled (we can add a pebble to it) if all nodes $w$ such that there is an edge $w \to v$ are pebbled.

The goal is to pebble the root, and what we want to minimize is the maximum number of pebbles on the board. This minimum is called the pebbling number of the circuit.

If a circuit has pebbling number $p$, then it can be evaluated using roughly $p$ bits of memory. The idea is that pebbling a node corresponds to computing the its value, which is possible since all of its children are pebbled as well.

All of the above concerns the case in which the circuit is given ahead of time, and the goal is to construct a strategy to evaluate it on an unknown input. However, the same general approach can also be used to solve your problem, using the fact that the pebbling number of the complete binary tree of depth $D$ is $O(D)$. For more on pebbling, see Nordström's survey.

Finally, let me mention that the circuit evaluation problem is $\mathsf{P}$-complete. This means that assuming $\mathsf{L} \neq \mathsf{P}$, it is not possible to evaluate arbitrary circuit in logarithmic space. In contrast, the formula evaluation problem is in $\mathsf{ALOGTIME}$ (i.e., uniform $\mathsf{NC^1}$), and so in $\mathsf{L}$. This is due to important work of Buss.


Understanding simulated annealing information theoretically

Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state.  You want to find order within the disorder.  Now, Metropolis and Simulated Annealing are slightly different things.  Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode.  What simulated annealing does is focus the Metropolis to find the absolute minimum.
So in annealing you start at a high temperature, which means basically that anything is possible.  Think of quantum tunneling.  The most improbable thing can happen when temperatures are very high.  So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise.  As you cool you focus on just what makes sense so that jumps are made only when they are better.
At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only.  In the end you should have a good idea of the optimal solution.


Union-Find with link-by-rank to represent a binary field with simple operations

In each node store an additional field named "value". The value of a root $r$ represents $\text{FIND}(r)$ (so the root itself is not necessarily $\text{FIND}(r)$). For $\text{SET_TO_1}(i)$, let $r$ be the root of the tree $i+1$ belongs to, we in addition change the value of the new root to the value of $r$. Now which root becomes the new root does not matter at all.


Here is an $O(VE)$ algorithm, which is substantially better than $O(V^3)$ if the graph is sparse. First do a topological sort, in time $O(V+E)$. Now work your way backwards, storing which vertices are reachable. At a vertex of outdegree $d$, this requires $O(dV)$ work, so in total you get $O(VE)$.


The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

EDIT: There are countably many recursive languages, and uncountably many non-recursive languages, so there are way more non-recursive languages.

There are countably infinitely many halting programs and non-halting programs alike.  I can't think of an interesting structure you can put on the set of programs that includes a concept of "proportion" where you end up being able to say anything interesting about the proportion of halting programs, unfortunately.

For instance, one natural structure to put on the set of programs is to give them a computable well-ordering.  One can make sense of questions about how big an infinite co-infinite subset of a countable set is if that countable set is well-ordered.  For example, the notion of asymptotic density can give credence to the intuition that there are more non-square integers than there are integers.  It basically says that the percentage of numbers that are not square tends towards 100% as you consider larger and larger finite initial segments of the naturals.  Asymptotic density makes sense for subsets of the naturals which have a canonical (computable) well-ordering.  The same cannot be said, however, for subsets of the set of all programs.  Since there is no canonical enumeration of the programs, there's no canonical answer to the question of proportion of halting programs in terms of asymptotic density.

Proposition: If $0 \leq \alpha \leq \beta \leq 1$ where $\alpha, \beta$ are computable real numbers, then there is an effective enumeration of the set of all programs such that the lower asymptotic density of the halting programs is $\alpha$, and the upper asymptotic density is $\beta$.

Proof Sketch: Let $\pi_1, \pi_2, \dots$ be a computable enumeration of all programs.  Let $\eta_n$ be the program:

print n
exit

Let $\nu_n$ be the program:

print n
loop {}

Note that $\eta_1, \eta_2, \dots$ is an effective enumeration of (some, obviously not all) programs that halt, and $\nu_1, \nu_2, \dots$ is an effective enumeration of programs that don't halt.

Let $0.a_1a_2\dots$ be the decimal expansion of $\alpha$, and $0.b_1b_2\dots$ the expansion of $\beta$.  Note that since $\alpha, \beta$ are computable, the sequences $a_1, a_2, \dots$ and $b_1, b_2, \dots$ are also computable.

Our goal is to build an effective enumeration of all the programs such that the lower and upper asymptotic densities of the halting programs are $\alpha$ and $\beta$ respectively.  We're going to build this enumeration in stages.  Each stage is going to have 3 parts:

At stage $n$:

(Sketch) Select programs from the front of the $\eta$ and $\nu$ lists that aren't already in our partially-constructed enumeration so far, and append them to the partial enumeration.  In this selection of programs, the proportion of $\eta$ (halting) programs chosen should be $0.a_1a_2\dots a_n$.  Select a lot of programs so that the proportion in the overall list (what had already been construct plus what has just been appended) is pretty close to $0.a_1a_2\dots a_n$ as well.  If we do this carefully at each stage $n$, we can assure ourselves that the lower density of the halting programs will be $\alpha$.
(Sketch) Do the same thing, this time so that the proportion of halting programs in the selection is $0.b_1b_2\dots b_n$.  Again, select a lot so that after appending these programs to the list so far, the overall proportion is close to $0.b_1b_2\dots b_n$.  If we do this carefully, we assure ourselves that the upper density of the halting programs will be $\beta$.
If $\pi_n$ isn't already in the list, append it to the end.  This ensures us that the enumeration we're building really does enumerate all the programs.


The number of the iterations of the while loop is

$$n/2+(n-2)/2 + (n-4)/2 + \dots +1$$

which is $O(n^2)$.


Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?

Yes. Transform both into DFAs $M_1$ and $M_2$; from them construct DFAs for $L_1 \cap \overline{L_2}$ and $\overline{L_1} \cap L_2$, and check that neither accepts anything.

As noted in the comments, the NFA to DFA construction can give an exponential increase in number of states, same for regular expression to DFA, so this doesn't prove the problem is in NP. Luckily you weren't asked about that ;-)


Calculating eigenvalue gap of a torus graph

Suppose that the torus is $n\times n$. Let $\omega = e^{2\pi i/n}$ be a primitive $n$th root of unity, and let $v_{\alpha,\beta}$ be the $n\times n$ vector given by $v_{\alpha,\beta}(i,j) = \omega^{i\alpha+j\beta}$. Using $A$ for the adjacency matrix of the torus (indexed by pairs $(i,j) \in \mathbb{Z}_n$),
$$
\begin{align*}
(Av_{\alpha,\beta})(i,j) &= v_{\alpha,\beta}(i+1,j) + v_{\alpha,\beta}(i-1,j) + v_{\alpha,\beta}(i,j+1) + v_{\alpha,\beta}(i,j-1) \\ &= v_{\alpha,\beta}(i,j) (\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}).
\end{align*}
$$
In other words, $v_{\alpha,\beta}$ is an eigenvector with eigenvalue $\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}$. It is not hard to check that the $n^2$ vectors $v_{\alpha,\beta}$ are linearly independent, and so they form a basis of eigenvectors for $A$. The eigenvalues are
$$
\lambda_{\alpha,\beta} = \omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta} = 2\left(\cos \frac{\alpha2\pi}{n} + \cos \frac{\beta2\pi}{n}\right).
$$
For $\alpha \in \{0,\ldots,n-1\}$, the function $\cos \frac{\alpha2\pi}{n}$ reaches its maximum $1$ at $\alpha = 0$, and otherwise its second largest value is attained at $\alpha=1$ and $\alpha=n-1$. Therefore the second-largest eigenvalue is $2 + 2\cos \frac{2\pi}{n}$. More generally, for a $d$-dimensional grid, the second-largest eigenvalue is $2(d-1) + 2\cos \frac{2\pi}{n}$, and the eigenvalue gap is $2-2\cos \frac{2\pi}{n} = \Theta(\frac{1}{n^2})$.

More generally, the $n\times n$ torus is the cartesian product of the $n$-cycle with itself. It is well-known that if $G$ has eigenvalues $\lambda_i$ and $H$ has eigenvalues $\mu_j$ then the eigenvalues of the cartesian product of $G$ and $H$ are $\lambda_i + \mu_j$ (the proof follows the computation above, replacing $\omega^{i\alpha}$ with an arbitrary eigenvector of $G$, and $\omega^{j\beta}$ with an arbitrary eigenvector of $H$). It follows that the eigenvalue gap of the product is the minimum between the eigenvalue gaps of $G$ and $H$.


Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

Do you mean a grammar with left and right recursive rules, or a single production rule with left and right recursive alternatives?

If a single production rule is both left and right recursive, the grammar is ambiguous. For example, the following rule

$A \to \alpha A \mid A \alpha$

has the following two (left-most) derivations:

$A \Rightarrow \alpha A \Rightarrow \alpha A \alpha $ corresponding to the grouping $(\alpha (A\alpha)$

$A \Rightarrow A \alpha \Rightarrow \alpha A \alpha $ corresponding to the grouping
$((\alpha A) \alpha)$

But a grammar can have left recursive and right recursive rules in different production rules and that can be unambiguous. For example, the following grammar:

$\begin{align*}
  S &\to X \mid Y \\
  X &\to X b \\
  Y &\to a Y \\
 \end{align*}$

In this grammar, $X$ and $Y$ are left and right recursive, respectively, but the grammar is unambiguous.


Just follow the rules of $\beta$-reduction and remember that function application associates to the left, i.e. $f g h$ is just syntactic sugar for $(f g) h$.

I'll show the steps for $(\lambda x.x y)(\lambda y.y z)$.

Strip off $\lambda$ from $(\lambda x.x y)$. You get the abstraction body $x\ y$, where $x$ is free now.
Substitute the argument $(\lambda y.y z)$ for $x$ into $x\ y$: $(\lambda y.y z)$ y. Notice that I didn't do anything with $y$ during this step.
Observe that the current $\lambda$-term is an application that can be reduced further. Again stripping off $\lambda$ we get $y\ z$ and substituting $y$ for $y$ results in the same term $y\ z$.

Here is the sequence of $\beta$-reductions without the intermediate steps:
$$(\lambda x.x\ y)(\lambda y.y\ z) \rightarrow_\beta (\lambda y.y\ z) y \rightarrow_\beta y\ z.$$

The second problem can be dealt with in the same way.


In my opinion you are not quite right...

During the loop, when you return from foo(i), the spaces used by the call foo(i) is released (I mean, the stack pointer is back to the previous position).

So actually foo(i) only uses 1 more AR than foo(i - 1). The space cost should be O(n).

This can be verified by running the code with foo(25) and specify a stack of size 1 MB (disable all optimizations, of course). It will return normally within several seconds, without "stackoverflow". This is a proof that it's not using O(2^n) space.


Example on Referential transparency (wikipedia)

If Source refers to the keyboard, and the user types a the first time but b the second time, then GetInput(Source) will not return the same value both times.
It's impossible to replace GetInput(Source) by its value without changing the meaning of the program, because there are many possible values, depending on the actions of the user. To replace GetInput(Source) with a would be wrong if the user decides to press b.
An example of a consequence of the fact that GetInput(Source) is not referentially transparent is that if the program calls this twice, which call returns a and which calls return b depends on the order in which the calls are evaluated (or more precisely, on the order in which the calls get their input from the keyboard: you have to get down to this level of detail to be sure).


Why do we use the log in gradient-based reinforcement algorithms?

We often take the logarithm because:

Maximizing $\log \Phi(x)$ is equivalent to maximizing $\Phi(x)$, so in maximum-likelihood problems, we can maximize the log of the likelihood instead of maximizing the likelihood directly and the result will be equivalent.
The logarithm converts multiplication to addition, and the derivative of a sum is "nicer" than the derivative of a product.  Products often arise when maximizing likelihoods, because the probability of something can often be written as the product of other probabilities   (e.g., when we are calculating the probability of that multiple independent events all happen).  The derivative of the product is ugly, but the derivative of the log of the product is nice and simple.
Gradient descent often involves maximizing a likelihood, so we'll need to take derivatives.  The expressions get simpler/cleaner if we can take the derivative of the log likelihood instead.


What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Why should we even expect that there is such a polynomial-time algorithm? The comment

  Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24

has an upvote, but it only hints implicitly that there is a (simple?) solution. Let me try to guess the (simple?) solution that is expected here. The AHU algorithm by Aho, Hopcroft and Ullman produces a canonical labeling of trees. Let's interpret the AHU algorithm as an efficient implementation of color refinement for rooted trees, and ask whether color refinement for "labeled trees" (isomorphism of "colored trees" would not allow to swap colors) would always be able to decide isomorphism. The answer is "no", because isomorphism of labeled trees is GI complete:

  From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge.

The link above also makes it clear that this is well known by citing

    Theorem: Marked tree isomorphism is isomorphism complete

  from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”


Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most

Hint: Show that at a given value of $i$, the probability of failure of the $l$th attempt is at most $i/m \leq 1/2$ (perhaps using a union bound), and the events are independent for different attempts.


Relationship between circuit size and formula size in Sipser text

Yes, that's correct.  See the Tseitin transform, which describes how.  It doesn't matter how the circuit $C$ was constructed.


Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous

First, figure out what the language is.
Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous?
Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect the resulting word?


Do the classes $P$ and $NP$ include problems faster then polynomial?

We have $$\mathsf{P} = \bigcup_{k \in \mathbb{N}} DTIME(n^k)$$
And e.g. $\log n \in \mathcal{O}(n)$. Thus, problems which are solvable in deterministic logarithmic time are in $\mathsf{P}$ since they are in $DTIME(n)$.


For each cell $(i,j)$, store the set of possible pairs $(x,y)$'s.

Now, DP by scanning row-major from top row to bottom row, for each cell $(i,j)$, only needs to consider $(i,j-1)$ and $(i-1,j)$ (if any), either choose or not to choose $(i,j)$. So from the stored set in $(i,j-1)$ and $(i-1,j)$, compute $(i,j)$'s set easily.

Try to finish the above idea in details. And then code it in your favorite programming language will quickly improve your DPing skill.


Personally, I would not call it a greedy algorithm. I'm not sure that's a useful way to think about it.

A greedy algorithm optimizes some global objective function by making small choices, where at each step we make a locally optimal choice (among all the choices at each step, we choose the one that best improves our objective function).  In a greedy algorithm, the objective function monotonically increases at each step of the algorithm.  I don't see any sense in which radix sort has this form.

This becomes clearest if we look at the version of radix sort that starts by sorting on the least significant digit, then the next-least significant digit, etc.  Here the objective function does not monotonically increase.  The first step can take you further away from being sorted, but then later steps bring you back.

For instance, consider the list $[0101, 0010, 0001]$.  Let's look at what happens if we apply radix sort to this list.  The first pass will transform this to $[0010, 0101, 0001]$: it got further away from being sorted.  After the second pass, we get $[0101, 0001, 0010]$, then after the third pass we get $[0001, 0010, 0101]$: it is finally sorted.  So, we started out being close to sorted, then we got farther away from being sorted, then we got closer -- not exactly the characteristic of a greedy algorithm.

For an even better example, consider the list $[0001, 0010, 0101]$.  Let's look at what happens if we apply radix sort to this list, even though it happens to already be sorted.  The first pass will transform this to $[0010, 0001, 0101]$.  I don't care what your global objective function is; this has certainly made the global objective function worse, because it changed the list from being completely-sorted to being not-sorted.  So, this shows that radix sort doesn't seem to be a greedy algorithm (at least if you start by sorting on the least significant bit).

There's an alternative version of radix sort where we sort first by sorting on the most significant digit, then the next-most significant digit, etc.  This does feel closer to a greedy algorithm, though I'm not sure that viewpoint is really useful in any practical way.

It is definitely not a dynamic programming algorithm.

I'm not sure that trying to classify it in this way is useful or helpful.  I don't think it'll help you, e.g., understand how greedy algorithms work, or help you design better greedy algorithms in the future in other settings.  I'd suggest you think about radix sort on its own terms: it just is what it is.


What is meant by "give pattern of a regular expression"

A pattern (in the context of languages and automata) is a way of defining a set of strings. A string matches a pattern if it belongs in the set defined by that pattern. So, your regular expression is actually a pattern. The question, I think, would be to find the pattern given a set of strings!


Does co-inductive and co-recursive types also have their recursors?

To understand coinduction, it helps to understand the categorical presentation of induction (since, as far as I know, coinduction comes from dualizing it there).

The idea behind induction is that we have a functor $F : C → C$, and we consider algebras $(A,\ α : F A → A)$. The operation $α$ specifies how to interpret the structure given by $F$ into $A$. Then, an inductively defined type is an initial algebra $(μF, \mathsf{in} : F μF → μF)$, which mean there is a unique homomorphism $\mathsf{fold}_A : μF → A$ to any other algebra. This homomorphism is the recursor, and the uniqueness allows us to define the induction principle in various ways, depending on the setting.

Coinduction flips most of these arrows around. Instead of algebras, we have coalgebras, $(A, α : A → F A)$. And instead of being initial, the coinductively defined type is final, so we get a unique $unfold_A : A → νF$ from any other coalgebra. So, instead of a recursive way of "eliminating", we get a recursive way of "introducing," and the eliminators are non-recursive.

However this flipping around makes some thing not work quite as nicely with coinductive types. I have an Agda development here that tries to explain the stuff about induction above in more detail, with the idea of finding something similar for coinduction. But I never got around to figuring that part out. And as far as I know, there is no known 'nice' interpretation of the coinductive case similar to the inductive one. The one thing to note is that 'just do the same thing with slices as induction' turns out to be uninteresting for coinduction.

One promising thing I have seen is that in cubical type theory, definition by coinduction gives a natural way of showing that two values of a coinductive type are equal, because it automatically corresponds to bisimulation, which is the usual notion of equality for coinductive things. The idea is that an identity from $x : A$ to $y : A$ is a function $eq : \mathbb{I} \to A$ (where $\mathbb{I}$ is an 'interval' type with distinguished values $0$ and $1$) such that $eq\; 0$ evaluates to $x$ and $eq \; 1$ evaluates to $y$. Then $unfold_\mathbb{I}$ gives us a principle for proving $x = y : νF$ by breaking things down to individual pieces like $\mathsf{step} : \mathbb{I} \to F\ \mathbb{I}$. You can see an example of this here.

I don't know if that completely answers your question or not. Hopefully it helps some.


Decidability of equivalence of two context free grammars

Let me prove that the problem of determining whether $x = 0$ is undecidable.

Let $A$ be a Turing machine that accepts only $x$, and let $B$ be a Turing machine that accepts only $0$. Then $x = 0$ iff $L(A) = L(B)$, so according to your argument, determining whether $x = 0$ should be undecidable.

I hope that this example helps you understand why your reasoning doesn't work. Instead, try to to use the fact that CFG universality (given a grammar $G$ over $\Sigma$, does $L(G)$ equal $\Sigma^*$?) is undecidable.


What is the min # of moves to sort an array from 1 to n?

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted.
This shows $n-k$ moves is necessary.


What is the complexity class of this variant of Subset sum?

This is NP-hard. The associated decision problem is NP-complete.

There are various ways to prove that.  For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard.

Your problem is an instance of multi-dimensional subset sum (or multi-dimensional knapsack), for which you can find algorithms and approximation algorithms in the literature.

Related: https://cstheory.stackexchange.com/q/19976/5038, How to find subset of vectors whose sum has certain characteristics, https://cstheory.stackexchange.com/q/21865/5038, https://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints


How shall I resolve a nonlocal name in a language with deep binding?

Roughly put, every time you define a function, as in def B(): ... you define B to be a closure. This is a pair contains a representation of the body of the function (possibly compiled to a simpler language), and a reference to the current environment (possibly restricted to what B actually needs). The current environment is the one we are in when we run def B(): ....

In the example you provide, B is defined inside A, so its associated closure gets a reference the the current call frame of A. This is why, if you pass P=B in the recursive call, after the call running P prints the value of I in the previous call frame.

Note that, in many languages, closures can be returned, which makes the current call frame to be not freed after the return. For example,

def A(I):
  def B():
    print(I)
  def C():
    nonlocal I  # Python for "use A's I, don't create a fresh local I"
    I += 1
  return (B,C)

# main
(b,c) = A(10)
b() # 10
c()
b() # 11
c()
b() # 12

Above, we can see that, even if A returned, its local variable I is still live! It can be accessed through the two returned closures, which contain a reference to the A's call frame, even if A is now finished.


Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

In grassfire the distances are constant. All of your neighbors have equal length. In a weighted graph, grassfire will fail.

Graphfire is actually based on a small modification of BFS.

The Dijsktra works on weighted graphs, too.

Note: If all costs are equal, Dijkstra = BFS

Know the difference, and use them according to your need.


Removing left-recursion in grammar while maintaining left-association of operator

Compatibility of left associativity and LL(1) parsing

You just hit one of the major inconsistencies in the use of
context-free (CF) syntax. People want to choose grammars so that the
parse-tree will reflect the intended structure of the sentence,  close to its semantics, especially in the case
of non associative operators, such as application. This was pretty much the original intent of CF grammars in linguistics. But at the same
time they are constraining themselves to parsing technology that will
tolerate only some types of grammars.

Indeed, if the parse-tree is to reflect the left associativity of an
operator, then the grammar is necessarily left-recursive, since the
top application node in the parse-tree is necessarily adding the
rightmost term of non-parethesized successive applications.. So LL
parsing is out of the question. You are right.

There are two ways out of this. One is not to rely on the parser to
give the rigth "parse-tree" to be used for later stages of processing
(such as reducing the lambda expression, here). This lead to the
concept of Abstract Syntax Trees (AST) that can be built from the
parse-tree, but with a different structure.

The other solution is to use more general parsing Techniques that will
accept any CF grammar, and parse in accordance with it. General CF
parsers is a well developed technology  (and I do not cease to wonder
why LL remains so popular).

I have no idea what could be considered a proper answer to these
contradicting requirements.

What I would do is show they are contradicting requirements. Give a
first grammar that meets the associativity and priority constraints,
then transform the grammar into and LL(1) grammar for the parsing.

The fact that something appeared in a journal or on an exam is not a
total garantee that it is correct.  And I might be wrong too ... but I
did some checking, in addition to my own knowledge of the issue.

About this specific example

This being said, the first grammar you are suggesting does not seem
quite correct. It does not have a way of producing λu.λv.v .

One trick to know is to start with operators (here abstraction or
application) with the lowest priority (abstraction). It is the same for arithmetic
expressions.


Google's Deep Dream project is research being done to visualize neural networks' learning to understand more about them.

First, you have to understand a Deep Belief Network on a high level. In short, it's a way for machines to 'learn' about data (images, in this case). That works, essentially, by transforming an input by several matrices (layers) through the network to get an output. Deep Belief Networks are trained to reconstruct their original image. All of the images are generally of some type, like animals. After some training, they begin to recognize basic features that are common between members of the training set, such as edges or colors.

The images published for the Deep Dream project are different ways of visualizing the data from trained networks. For some of the images, they observe the state of the image in layers between the input and output, resulting in artistic looking sketches of the original. For other images, they start with one image that is not related to the training set, send it through the network, then send the output through the network repeatedly to accentuate features that the network found in the image.


No, theorem 2 does not imply theorem 1 unless you also prove for that instance that every optimal DTSP visit order creates a crossing ETSP trajectory.  There might be another optimal DTSP $|T'| = |T|$ visit order that does not result in a crossing ETSP so that we have $T* = T'$.


A data hazard occurs whenever you access a register after updating it. Due to the pipeline structure updating the register happens after it is being accessed by the successive instruction. That is, when accessed, the register holds the old value rather than the updated value.

For instance:

1. R2 = R1 + 1    // update R2
2. R3 = R2 + X    // access R2

Instruction 1 updates R2 at S4 (see the table). Instruction 2 reads R2 at S2. But at this time the new value of R2 is not stored yet -- it will be stored only on the next clock. This problem is the hazard.


No Naive Set Theoretic Models of Polymorphic Lambda Calculus?

The standard reference you are looking for is indeed Reynold's Polymorphism is not Set Theoretic. While it is quite obvious that you cannot form, e.g. the product $\Pi_{S\in\mathrm{Set}}S$ over all sets using the usual set theoretic product, it's a legitimate, and non-trivial question whether there is some weaker notion of product that would work, while preserving the usual binary product $\times$ and function space $\rightarrow$.

This turns out to not be possible either, since on one hand, it is rather easy to build a type $\bf 2$ such that the interpretation has at least 2 elements, and show that the interpretation of $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ is isomorphic to $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$, which is not possible for the usual interpretation of $\rightarrow$ by the usual cantor paradox. In this sense it is somewhat similar to the proof for the untyped calculus.

Note that a further paper, by Andrew Pitts, Polymorphism is Set Theoretic, Constructively, overturns this conclusion somewhat by showing that the above contradiction is only possible to construct in classical set theory, and that there are several constructive theories of sets in which polymorphism can be interpreted with the usual interpretations of functions spaces and products. Most notably these "large products" exists in the Effective Topos, the most comprehensive of introductions being given by Phoa.


On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$

Suppose that $$ T(n) = T(n/a) + T(n/b) + n^c. $$
Let's try to prove by induction that $T(n) \leq Mn^C$:
$$
T(n) \leq M(n/a)^c + M(n/b)^c + n^c = \left((a^{-c} + b^{-c})M + 1 \right) n^C.
$$
Therefore we need $(a^{-c} + b^{-c})M + 1 \leq M$, which we can satisfy as long as $a^{-c} + b^{-c} < 1$.
When $a^{-c} + b^{-c} = 1$, the answer is likely $T(n) = \Theta(n^c\log n)$.


Linear Regression. Why do we take sum of errors to compute the cost?

You can usually view the cost function as the average squared error over some dataset with $N$ pairs of data, thus being defined as:

\begin{align}
J &= \frac{1}{N} \sum_{i=1}^{N} \left(f(x_i,\beta) - y_i \right)^2
\end{align}

We want the average error of our model (for all data we have) to decrease as we fine tune values for $\beta$, the vector parametrically defining how our model $f(\cdot,\cdot)$ works. So we like to look at all the data at once since it can be used to make changes to $\beta$ that should actually make the model improve as a whole.

If we instead made the cost function based on a subset of the dataset, you would end up with a cost function that may sub-optimally modify the value for $\beta$. This sub-optimal behavior may make us take longer to get to a local minimum of the cost function or even diverge from a good solution if you aren't careful with your hyper parameters.

Stochastic gradient descent or mini-batch gradient descent are methods that use a single piece of data or a subset of data from the dataset to make adjustments. These methods have actually found use for really large datasets where the longer convergence time is more worthwhile than the time it takes to do a whole pass on the data to compute necessary gradients and costs.


In general each thread has its own registers (including its own program counter), its own stack pointer, and its own stack.  Everything else is shared between the threads sharing a process.

In particular a process is generally considered to consist of a set of threads sharing an address space, heap, static data, and code segments, and file descriptors*.

An address space is simply the mapping of logical addresses to specific pieces of physical memory. So when we say that all the threads in a process share the same address space we mean that when accessing a variable foo in global scope all the threads will see the same variable.  Similarly, the threads may all be running a different point in the code at any particular time, but they are all permitted to call the global function bar(), which will correspond to the same function for every thread in the process.

Most modern operating systems have added a notion of thread local storage, which are variables of global scope that are not shared.  The usual example of the use of this is for the variable errno.  That's a single variable of global scope, but in most modern operating systems each thread is given its own local copy, so that an error in a library call on one thread won't impact the behavior of other threads.

* There is some additional process state shared by all the threads in a process, things like the process id, the signal handling, and file locks.  For a complete list of process state shared by threads you need to look at the documentation for the specific threading implementation.  For example, the pthreads man page.


Need help analyzing the runtime analysis of this algorithm/algorithms in general

I figured out why the runtime is O(N^2).

Yes, the while loop does run N/2 times. However, that is equivalent to -

"for(int i = 0; i < N; i+=2)" which has a runtime of O(N) still.

I confused it with -

"for(int i = 0; i < N; i *= 2)" which has a runtime of O(logN).

The summation also results in the correct answer in this instance.


check if a binary tree is a binary search tree

abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft); should likely be comparing with maxLeft and minRight, not maxLeft and minLeft

if(x == NULL)
    return <true, -∞, +∞>;

I'm guessing the point of returning infinities here is to make a NULL vertex NEVER fail the > and < comparisons above, in which case in makes more sense to return <true, +∞, -∞>;


What's this type of semantic analysis called in NLP?

Given your example, Lexical Semantics may be what you are looking for. Things like WordNet provide hypernym (breakfast -> meal), hyponym (meal -> lunch), meronym (course -> meal), holonym (water -> oxygen) relationships. See chapter 19 of Speech and Language Processing by Jurafsky and Martin for more thorough set of details.


Find an MST in a graph with edge weights from {1,2}

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices that have a connection of weight 1 (because they have priority to those of weight 2). I would say that a single list can handle this.

I also think that there might be another approach. Start building spanning trees for the components when we only use edges of weight 1, just ignoring edges of weight 2. Then the components are "big vertices" that can be connected by a tree using the remaining edges of weight 2. Keeping components here is easy: all vertices reached in a new component are labelled with the same number. That number identifies the "big vertex".


Help with problem 4.1-1 from CLRS 2nd edition

As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.

In the comment you mention that the text states that they omit floors and ceilings. This is always wrong. You cannot "omit" stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)
Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence
$$ T(n) = 2T(n/2) + O(n). $$
This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n).
$$
When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for all positive values of $n$.
You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.

How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n_0 = n$, $n_{i+1} = \lceil n_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n_i = 1$.
Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n_1 \leq (n+1)/2$, and so $n_2 \leq (n+3)/4$, and $n_3 \leq (n+7)/8$, and so on. More generally, $n_i \leq (n+2^i-1)/2^i < n/2^i + 1$. Hence if $i = \lceil \log_2 n \rceil$ then $n_i < n/n + 1 = 2$, implying that $n_i \leq 1$.
In the other direction, clearly $n_i \geq n/2^i$, and so if $i = \lceil \log_2 n \rceil - 1 < \log_2 n$ then $n_i > 1$, implying that $T(n) > \lceil \log_2 n \rceil - 1 + C$.
We conclude that the minimal $i$ such that $n_i = 1$ is exactly $\lceil \log_2 n \rceil$. Hence $T(n) = C + \lceil \log_2 n \rceil$.


One approach: Use a meet-in-the-middle algorithm.  Build a precomputed table that stores $T_i = x^i \bmod P(x)$ for all $i$ up to the maximum message length.  Now, given $S$, you are looking for $i,j$ such that $S = T_i + T_j$.  This can be found by enumerating all $i$, and for each $i$, computing $S-T_i$ and checking whether it is present in the precomputed table.

The running time is proportional to the maximum length of the message.  I'd imagine that in a real deployment, two-bit errors will be rare enough that this running time is affordable.  (If two-bit errors are common, then three-bit errors will have non-negligible probability, which is a problem of its own.)

If you want to reduce space complexity, instead of storing the entire precomputed table and looking up $S-T_i$ in the table, compute the discrete log of $S-T_i$ for each $i$ using whatever method you prefer (such as the one you listed in your question).

I don't know if there are smarter methods that exploit the structure of $\mathbb{F}_2^{32}$ in a more intelligent manner.


Synchronisation and ordering in distributed systems

At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.
There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize broadcast service. Not surprisingly, there are various broadcast service with different ordering (what you are probably interested in) and reliability (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?
Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

As for your comment:

I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such consistency models issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.
I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...


Show that (2,3)-satisfability is np-complete

1-in-3-SAT is NP Complete: given a set of clauses, find a value assignment such that exactly 1 literal in each clause is made true (http://cs.nyu.edu/courses/fall14/CSCI-UA.0310-001/1in3sat.pdf).

Reduction from 1-in-3-SAT: negate every literal in every clause of the 1-in-3-sat instance. Now exactly two literals need to be made true in each clause instead of one to have an equivalent solution set. This is your (2,3)-satisfiabililty instance. We don't even need the clauses with two literals.

Example

1-in-3-SAT instance: (a,-b,c), (a, b, -c), (d, e, f)
equivalent (2,3)-satisfiability instance: (-a,b,-c), (-a, -b, c), (-d, -e, -f)


Solve T(n)=T(√n)+ n using substitution method

As you mention,
$$
T(n) = n + \sqrt{n} + \sqrt[4]{n} + \cdots,
$$
and the number of terms is at most $\log \log n$. Hence
$$
n \leq T(n) \leq n + \sqrt{n} \log\log n.
$$
This implies that $T(n) \sim n$.


How to solve recursion with two separate converges rates

If you take the initial conditions $T(0) = 0$ and $T(1) = 1$ then you get A018819 (up to shift), which is essentially A000123. The asymptotics are known to be $T(n) = n^{\Theta(\log n)}$. The references under the second entry contain more accurate asymptotic information.
More explicitly, A018819 satisfies the recurrence $a(2m+1) = a(2m) = a(2m-1) + a(m)$, with $a(0) = a(1) = 1$. You can show inductively that $a(n) = T(n+1)$. Indeed:

If $n = 2m+1$ then $$T(n+1) = T(2m+2) = T(m+1) + T(2m) = a(m) + a(2m-1) = a(2m) = a(2m+1) = a(n).$$
If $n = 2m$ then $$T(n+1) = T(2m+1) = T(m+1) + T(2m-1) = a(m) + a(2m-2) = a(m) + a(2m-1) = a(2m) = a(n).$$


Your problem is not in P, for two different reasons:

P is a class of decision problems, but your problem is a function problem.  Instead of P, you should consider its functional equivalent FP.
The output could be exponentially large in the input length: encoding $b$ takes about $\log b$ bits, but encoding $a^b$ takes about $b \log a$ bits.

This still leaves open the possibility that the following problem is in P:

  Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.

While I don't know what the answer to this question is, here is a related problem in FP:

  Given natural numbers $a,b,c$, determine $a^b \bmod c$.

This can be shown using the important technique of repeated squaring.


Your machine outputs the character it just received; Feynman's outputs the previous one.

More specifically, when Feynman's automaton receives the sequence of stimuli $s_1, s_2, \dots$, its output is $x, s_1, s_2, \dots$, where $x=0$ if the automaton starts in state $1$ and $x=1$, otherwise.  Your automaton outputs $s_1, s_2, \dots$ given the same sequence of stimuli.


Difference between edges in Depth First Trees

You could find a nicely description in CLRS 3ed Chapter 22.3. I extracted the next description from there. There are just four types of edge in a graph.

Tree edges are edges in the depth-first forest $G_\pi$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
Back Edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges.
Forward Edges: are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or the can go between vertices in different depth-first trees.

For that, because you're interested in depth-first forest ( graph contains all depth-first search trees) only two types of edges remain:

Tree Edges: edges with a first node without parents in the forest of depth first search trees $G_\pi$
Cross Edges: edges inside depth-first trees with the description above, and those edges connecting those dfs-trees.


How can an algorithm have exponential space complexity but polynomial time complexity?

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:

  Observe that the number of minimal, and even minimum solutions, can be
  exponential in the size of the graph; Fig. 1 gives an example.
  Therefore, the total running time of any enumeration algorithm cannot
  be expected to be polynomial in the size of the graph.

The paper goes onto explain the concept of polynomial delay,

  However, certain enumeration algorithms for other combinatorial
  problems work with polynomial delay, i.e., the algorithm performs at
  most a polynomial number of steps before the first and between
  successive outputs.

What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.

When it comes to memory, the paper states:

  Note that memory requirements are polynomial for graphs with a
  polynomial number of MFVS, but potentially exponential for the general
  case.

Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.

Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.


Puzzle/game of NP class for a high school student

There is a list of a bunch of games that are NP-hard here: https://www.ics.uci.edu/~eppstein/cgt/hard.html  You might also enjoy this list of Nintendo games that are NP-hard: https://jeremykun.com/2012/03/22/nintendo-np-hard/.

Some well-known games that can be proven to be NP-hard (in some form or other) include Tetris, Minesweeper, Checkers, Chess, Dots and boxes.

I think Dots and Boxes might be a particularly surprising and accessible one -- it's rather mind-blowing that such a simple-seeming game hides such complexity.

Caveat: do understand that in many of these cases, we're actually considering a variant of the game.  Many games are finite, so there are only finitely many positions, and thus can't literally be NP-complete -- so instead we consider variants.  For instance, instead of chess on a 8x8 board we consider a variant with a $n \times n$ board, or something like that.  The general point still applies but there are technical details that you should make sure you understand before using this in a classroom.


Master Method to solve recurrences is 'a' related to 'b'?

No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you break into two sub-problems of the same size ($b=2$), but only recurse on one of them ($a=1$). In this case, the recurrence would look like: $$T(n) = T(n/2) + O(1)\,.$$

For an algorithm like merge-sort however, not only is the problem broken into two sub-problems of equal size, but you recurse on both sub-problems before merging the results. In this case, you have that $a = b = 2$, and so, the recurrence looks  like: $$T(n) = 2T(n/2) + O(n)\,.$$


Are there any examples of projects running a program that will take many years to finish its job?

There have been several programs running for very long times, like the Great Internet Mersenne Prime Search, which has been going for some 25 years now.


Language equivalent states in a deterministic parity automaton

Two states in the automaton have different languages if and only if there exists a word that is accepted from one state, but not from the other. Checking if this is the case boils down to building a product of the automaton with itself, i.e., starting form the automaton $\mathcal{A'} = (Q, \Sigma, \delta, q_0, \mathcal{F})$, you build an automaton $\mathcal{A'} = (Q \times Q, \Sigma, \delta', (q_0,q_0), \mathcal{F}')$ such that for all $q,q' \in Q$, you have $\delta'((q,q'),a) = (\delta(q,a),\delta(q',a))$.

In this product automaton, you want to cycles along which the parity of the highest color visited infinitely often in the first factor of $Q \times Q$ is not the same as in the second copy. Whenever this is the case, then for every state $(q,q')$, we know that $q$ and $q'$ have different languages.
 Otherwise, if from state $(q,q')$, there is no way to reach a cycle along which one copy of the automaton accepts, but the other one does not, you know that the states have the same languages.

The technique is applied in the paper "SAT-Based Minimization of Deterministic ω-Automata" by Souheib Baarir and Alexandre Duret-Lutz, which bases on a similar construction for deterministic Buchi automata from earlier work. They use a SAT solver to guess an automaton that is equivalent to a given one and add SAT clauses that enforce that in a product between the two automata, you do not have reachable cycles along which the acceptance of the cycle differs between the copies. After an equivalent automaton is fixed, their clauses become Horn clauses, so you can check this in polynomial time. In your case, you would just use the same automaton again.


How precise is the statement "STLC is the internal language of CCCs"?

Cartesian closed categories correspond to the simply typed lambda calculus with products.  Your silly function is just $\lambda x.\lambda y.y$. If you want something that directly corresponds to the simply typed lambda calculus without implying products check out this paper by Bart Jacobs: Simply Typed and Untyped Lambda Calculus Revisited.

Let's instantiate your silly term and spell out what it looks like in type theoretic notation.

First, we're using _[_] at type $(\sigma \vdash \tau \Rightarrow \tau) \to (\Gamma\times\sigma\vdash\sigma) \to (\Gamma\times\sigma\vdash\tau\Rightarrow\tau)$.  As a rule and placing in the terms, we get:
$$\frac{z : \sigma \vdash \lambda y:\tau.y : \tau\Rightarrow\tau \qquad \Gamma, x:\sigma\vdash x:\sigma}{\Gamma,x:\sigma\vdash (\lambda y:\tau.y)[z\mapsto x]:\tau\Rightarrow\tau}$$
where $M[z\mapsto N]$ means "substitute $N$ for $z$ in term $M$".  Of course,  substituting for a variable that doesn't occur does nothing.  So, in type theory, the above is (often by definition of substitution) equivalent to just $\Gamma,x:\sigma\vdash(\lambda y:\tau.y):\tau\Rightarrow\tau$.  (Closely relatedly, weakening is also often transparent in type theory.)  We then lambda abstract to get silly.

As a potential further insight, structural rules like $(\lambda y:\tau.M)[x\mapsto N] \equiv (\lambda y:\tau.M[x\mapsto N])$ with $y$ not free in $N$ come from naturality.  This particular case comes from naturality of currying (if you spell it out, you'll see how the "$y$ not free in $N$" part is handled).

However, in this case it was a bit of a fluke that this worked out.  In general, the second argument to _[_] should be a substitution, i.e. an arrow from contexts to contexts.  In this code, a context is effectively represented by a left nested tuple (ending in an empty tuple).  So if the second argument to _[_] does not return a left nested tuple, then _[_] will not behave like substitution.  For example, the expression var 0 [ var 1 ] does not correspond to $$x:\sigma, y:\sigma \vdash x[x\mapsto y] : \sigma$$ like we might think, but rather to $$x:\sigma\times\sigma, y:\sigma \vdash \mathtt{snd}(x) : \sigma$$
This second interpretation is an artifact of this particular implementation that was exposed by failing to meet the precondition of _[_].  We would get the intended behavior had we written something like var 0 [pair unit (var 1)].  It would be cleaner and closer to typical STLC syntax to have _[_] take a vector of arrows that get tupled together in a left nested manner.

That this confusion between types and contexts is so easy is particular to CCCs.  Most categorical semantics have a strict distinction between types and contexts; they live in separate categories.  This is true of the semantics in the above mentioned Bart Jacobs paper.  However, this conflation of types and contexts in CCCs makes it possible to discuss the categorical semantics without needing to introduce notions like indexed categories or fibrations.


Why does Coq include let-expressions in its core language

It is a common misconception that we can translate let-expresions to applications. The difference between let x : t := b in v and (fun x : t => v) b is that in the let-expression, during type-checking of v we know that x is equal to b, but in the application we do not (the subexpression fun x : t => v has to make sense on its own).

Here is an example:

(* Dependent type of vectors. *)
Inductive Vector {A : Type} : nat -> Type :=
  | nil : Vector 0
  | cons : forall n, A -> Vector n -> Vector (S n).

(* This works. *)
Check (let n := 0 in cons n 42 nil).

(* This fails. *)
Check ((fun (n : nat) => cons n 42 nil) 0).

Your suggestion to make application (fun x : t => v) b a special case does not really work. Let us think about it more carefully.

For example, how would you deal with this, continuing the above example?

Definition a := (fun (n : nat) => cons n 42 nil).
Check a 0.

Presumably this will not work because a cannot be typed, but if we unfold its definition, we get a well-typed expression. Do you think the users will love us, or hate us for our design decision?

You need to think carefully what it means to have the "special case". If I have an application e₁ e₂, should I normalize e₁ before I decide whether it is a $\lambda$-abstraction? If yes, this means I will be normalizing ill-typed expressions, and those might cycle. If no, the usability of your proposal seems questionable.

You would also break the fundamental theorem which says that every sub-expression of a well-typed expression is well-typed. That's as sensible as introducing null into Java.


Efficiently compute parallel matrix-vector product for block vectors with FFTs?

Let's look at the case where $P=2$, for starters.  The FFT can be computed in a divide-and-conquer fashion, where first we compute the FFT of the even-numbered indices, then the FFT of the odd-numbered indices, and then combine them in a simple step (with a single layer of butterfly operations).

So, if the even-numbered indices are stored on one processor and the odd-numbered indices are stored on a second processor, then you could do this in parallel in a natural way, with the first processor doing the FFT on its own data, and the second processor doing the FFT on its own data; the final butterfly step requires only $\Theta(NP)$ data sent over the network.

If the data isn't partitioned that way, then the first step could be to send all the values at even-numbered indices to the first processor and the values at odd-numbered indices to the second processor, then do the above process.  In total it will require $\Theta(NP)$ data sent over the network and $\Theta(N \lg N)$ computation ($\Theta(N \lg N)$ computation at each processor to compute the FFT locally).

More generally, if $P$ is a power of 2, you can generalize these ideas in a similar fashion.  You send the data to the appropriate processor   ($\Theta(NP)$ data sent over the network), then compute the FFT locally at each processor ($\Theta(N \lg N)$ steps of computation at each processor), then combine them with $\lg P$ butterfly layers (requires $\Theta(NP \lg P)$ data sent over the network).

If $P$ isn't a power of two, you can pick the largest power of two that is smaller than $P$, and use that many processor (the remainder are left idle).


How hard is counting the number of simple paths between two nodes in a directed graph?

The most common complexity class associated to counting problems is #P. Deciding if there a simple path from a given node to another is clearly in NP. Counting them is then in #P.

About the NP-completeness: even if that's not a decision problem, it would hardly fit in NP: there may be $n!$ paths, and non-determinism does not help you about that (you'd still need to check them all)

The answer to your two first two question is: yes, it is hard, it is #P-complete (ref).

The Wikipedia article gives pertinent facts: 1) probabilistic algorithms are useful to approximate #P-complete functions, and that's the kind of algorithm used for the approximation in the previous article. 2) There are other easy problems with hard (#P-complete) counting versions:

finding (linear) vs. counting all assignments satisfying a DNF formula or an instance of 2-SAT
finding (linear) vs. counting topological sortings
finding (O(VE)) vs. counting perfect matching in bipartite graphs

You already know that if you remove the constraint "simple path" the problem falls into P (well you have to bound the length of the paths by a polynomial of the size of the graph or give the bound in unary)


What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

You say that your implementation of Bellman-Ford loops forever.
This leads me to believe that you are only stopping when no computed distance changes in one iteration.

You can always stop at the $(n-1)$-th iteration since, in the $i$-th iteration, all finite distances towards the vertices at hop-distance at most $i+1$ from the source must have correctly been computed.

Then, you can perform a single additional iteration. If a distance to a vertex $v$  changes during this iteration, then $v$ must be part of negative weight cycle (and you will find at least one such vertex $v$ per cycle).
If $V$ is the set of these vertices $v$, you can mark all vertices reachable by those in $V$ has having "negative infinity" distance (you can do this in linear time w.r.t. the size of the graph by performing any graph visit).


Here is a partial answer, to put you on the right track. Try to complete it to a full answer.
Let's try to show that $L^*\subseteq L^* L^*$.
Let $x\in L^*$, so we know that we can write $x=y_1\cdots y_k$ where $y_i\in L$ for all $i$.
Now, let's assume for a moment that $k\ge 2$, then we can look at two words: $x_1=y_1$ and $x_2=y_2\cdots y_k$. We then have that $x=x_1x_2$ and $x_1\in L^*$ and $x_2\in L^*$, so $x\in L^*L^*$.
If $k<2$, then we can take $x_2=\epsilon$, and possible $x_1=\epsilon$, and the proof still works. So we have $L^*\subseteq L^* L^*$.
Can you now follow a similar scheme for the other containment?


Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)

As the proof (sketch) itself notes:

  Note that on a given input $x$ of length $n$ there are $2^{f(n)}$ possible configurations.

This means there is only a finite space of configurations for a machine that operates in less than $f(n)$ amount of space!

Intuitively, if you have an array [0,1,0,...,] of length $n$, then all possible combinations of configurations of that array is $2^n$, and so a machine which could only modify an array of bits of size at most $n$ will either halt in that time, or end up in a loop with exactly the same state as previously, and this is easy to decide.

If you allow arbitrary amounts of space then as you note, it is undecidable whether or not a state is reachable or not.

It's hard to say whether a given piece of work is "too high level" for someone or not. To paraphrase Euclid, there is no "royal road" to theoretical computer science, so you should expect to have at least some difficulty working through technical material.

As Paul Halmos suggests: "Don't just read it, fight it!". This suggests that difficulty in mathematical reading is rather widespread (I certainly experience it sharply as well).


When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?

I decided to go with option B, as it seems like the more practical thing to do.


For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected

Compute a minimum bottleneck spanning tree of the graph. (Actually just compute a minimum spanning tree, as a minimum spanning tree is a minimum bottleneck tree.)
Determine the maximum edge weight from MBST, this will be your $t$.
Remove all edges whose weight is higher.

This can be done in linear time in the sum of the number of nodes and edges (see wiki).


"Practical forms" of Chernoff bound for inequality in expectation

It is more practical just because it has

  the advantage of being easier to state and compute with in many situations (quoted from [1]).

I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation:

$$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$

[1] Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.


Find the centre of a circle given two points lying on it and its radius


Kolmogorov Complexity, struggle with equation

The statement is equivalent to \begin{align}n+1=\log_2\left(\frac{|(01)^{2^n}|}2\right)&\impliedby |(01)^{2^n}|=2^{n+2}.\end{align} If $(01)^{2^n}$ means $\underbrace{(01)(01)(01)\cdots(01)}_{2^n\,\text{times}}$ then the statement is incorrect as $|(01)^{2^n}|=2^{n+1}$ as you have correctly obtained.


Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

The quadratic sum-of-squares relaxation of Max-Cut should indeed work out to be equivalent to the SDP that Goemans and Williamson solve. I encourage you to work this out yourself. This means that the Goemans-Williamson analysis indeed shows the inequality you mention.

You ask whether degree-2 SoS is a rewriting of the Goemans-Williamson rounding. It isn't. Rounding is a completely separate issue. Degree-2 SoS is a rewriting of the SDP that Goemans and Williamson solve. Rounding is how we bound the integrality gap.

Assuming the Unique Games Conjecture, $\alpha_{GW}$ is the optimal approximation ratio achievable in polynomial time. Since optimizing degree $d$ sum-of-squares can be done in time $O(n^{O(d)})$, this implies (assuming UGC) that every constant degree $d$ has the same integrality gap $\alpha_{GW}$ in the worst case.


Terminology: words with only terminals vs. words which can contain nonterminals

A standard term would indeed be sentential form. I think it can be used on its own, not only bound to a grammar.

It makes more sense when you know that words are also called sentences, probably harking back to the beginnings of formal grammars in the study of natural languages.

That said, there is precedence for pattern in the study of pattern languages. While they work nothing like grammars, mixed strings of alphabet symbols and variables have this name there.


Is there a largest class of halting programs?

There is no largest class of programs which have a decidable halting problem. If $L$ is such a class and $P \notin L$, then the class $L \cup \{P\}$ also has a decidable halting problem (why?). (This works since the class of all programs does not have a decidable halting problem.)

Responding to Raphael's comment, there is also no largest class of programs, up to finitely many exceptions, with a decidable halting problem. For each program $P$, let $L(P)$ be some infinite decidable set of programs equivalent to $P$ (for Turing machines, we can add dummy unreachable states, for example). Let $L$ be a class with decidable halting problem. I claim that there must be some $P$ such that $L(P) \cap L = \emptyset$. Otherwise, we could decide the halting problem for an arbitrary program $P$ by enumerating $L(P)$. Given a program $P$ such that $L(P) \cap L = \emptyset$, we can obtain a decider for $L \cup L(P)$, so that $L$ has infinitely many exceptions.


An example of a code that is neither p-code or s-code but is uniquely decodable?

An easy way to get new codes of any size is to compose a prefix non-suffix code and a suffix non-prefix code. For instance, start with the prefix non-suffix code $X_5 = \{0, 10, 110, 1110, 1111\}$ and compose it with the suffix non-prefix code $\{0,01\}$, which consists to replace $1$ by $01$ in $X_5$ to get
$$
S_5=  \{0, 010, 01010, 0101010, 01010101\}.
$$
The resulting set is a code that is neither prefix nor suffix.

N.B. The advantage of this method is that you always get codes, no verification needed.


Polynomial time algorithm to find an induced cycle in non-chordal graph

Since I found a solution myself, I'm gonna post the idea. It suffices to find chordless paths. For a vertex $v$ and $u$ its neighbour, we can delete the edge $\{u,v\}$ from $G$ and find a chordless $u$-$v$ paths. Connecting these will result in a chordless cycle.
A very simple algorithm finding such paths is described here. Naive algorithm runs in time $O(n(n+m))$ per $u$-$v$ path, they further give more efficient algorithm with running time $O(n+m)$ per $u$-$v$ path.


Rounding errors when converting floats to integers

It depends on :

the range of your input numbers
the FP type, typically IEEE single (32bits, 23bits precision) our double (64bits, 52bits precision)
The rounding mode, which is almost always "round to nearest even"

0.01 ≈ 7bits, add 3 bits for correct rounding, so around 13 bits remains with single precision, which give a range around ≈ ±10000.

[Well, I'm too lazy to give precise answers. The problem with FP is that every operation can slightly affect the precision, as well as the way the program is compiled and the target architecture, with or without FMA (fused multiply-add), for example.]


Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and calculus are used in specific areas of computer science, and there are various places you will see probability.
Probability is usually used to describe randomness in your algorithms, and therefore is used quite a lot. Basic knowledge of probability and expected value of random variables is usually enough.
Calculus is used mainly in optimization and machine learning problems (but you can still see it elsewhere).
Linear algebra, and specifically matrices from it are especially useful. You might not need the entire course for every application of it in computer science, but it will be very useful in machine learning.
I know there are other mathematical topics that can be useful for computer science, like  group theory, but I don't have experience with them to tell you what they are used for.
Also, there is no need to learn everything at once! You will start the math topics appear only in more advanced courses.


Difference between present - absent bit and valid - invalid bit in a page table?

Many people confuse these two bits. I'll try to explain the concept to best of my knowledge.
Let's say we have 32 bit architecture. so process virtual address space(VAS) will have size of 2^32. VAS space of a process has kernel code and data part and user code and data part.Page table of process contains entries for both user/kernel part. kernel page table entries are same for all processes that is these virtual addresses are mapped to same physical memory frame for all processes.because memory has just one copy of OS code.
process when initialized doesn't use the full VAS.virtual addresses which are not in use as of now have valid bit zero(Invalid). It can make use of more addresses by calling sbrk(), brk() system call.These system calls are used internally by malloc in C(if no holes are present already). which will add more virtual address to process page table that means it will make those pages valid.
Now there is a catch, page table entries which had valid bit set recently are not yet mapped to physical frames, that is where present/absent bit comes into picture. or if they are swapped out due to lack of physical memory.
Now when process will try to access these newly validated virtual address/swapped out address, as present bit is not set it will generate a page fault. Now we'll switch to kernel mode to service the page fault.OS has the disk address of the page to be loaded, once page fault service routine is finished it will make present bit set in the process page table. Meanwhile this page fault routine is being serviced,current process is contexted out and new process is given the cpu as per scheduling algorithm so that CPU cycles are not wasted.
I hope this answer helps.


How to generate (Java) source code in academically acceptable way - using abstract syntax tree?

It highly depends on what is the domain you are working on, i.e. why do you need to generate Java Source code anyway?.

Can you explain better what knowledge do you have stored in your knowledge base?.

The most "formal" method I can think of is by using the Java grammar and generate and abstract syntax tree as you mentioned. But it may or may not be appropriate, it depends on what are the task you want to solve.

If you want to use the grammar approach you may want to check antlr, I've used it to compare AST in plagiarism detection. Here is a repository with the grammars of many languages, including Java: https://github.com/antlr/grammars-v4


One question we could ask is "Can we reduce this back to the subset sum problem?" In this case, the answer is yes: for each duplicate $z$ we replace it with two numbers $x$ and $y$ such that $x+y=z$.
$$[-1,-1,2,3]\to [-7,-1,2,3,6]$$

However, we need to be careful that we don't introduce additional solutions (those using just $x$ without $y$), which we can do by making $x>\lvert \Sigma(a_i)\rvert$ for $a_i<0\in A$, and $y<-\lvert\Sigma(a_i)\rvert$ for $a_i>0 \in A$. Specifically, this precludes the use of $x$ without $y$ (and vice versa) by making the sum of $x$ and all negative numbers strictly above zero (and thus doesn't satisfy the traditional subset sum problem).


What complexity class does this variation of traveling salesman problem belong to?

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city.  Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$.  Then your problem asks whether
$$
minTSP(c + v) \ge min TSP(c) + x.
$$
But then the special case $c=0$ is equivalent to asking whether $minTSP(v) \ge x$, which is coNP-hard.


Time complexity of $L=\{a^nb^n | n \ge 1\}$

If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, assuming that you have in input a string $w$ of lenght $n$ that belongs to the language $L$, you have $\frac{n}{2}$ $a$'s that have to match with the same number of $b$, each $a$ is paired to a $b$ that is $\frac{n}{2}$ cells away, so to perform a complete matching you need $\frac{n}{2}$ transitions from an $a$ to reach the $b$ to be coupled with it, and again $\frac{n}{2}$ transitions to reach the next $a$, so in total $n\cdot \frac{n}{2}$ transitions (actually, you have to perform an extra transition for each letter to put the head in the right place, so the exact amount of transitions is $\frac{n^2}{2}+n+1=O(n^2)$).
Now, let us consider a word $w$ of lenght $n$ that does not belong to the language $L$. If it start with $b$, it is immediately rejected, so suppose $w=a^hb^kv$, where $v\in a\Sigma^*$ has lenght $j>0$ and $h+k+j=n$. If $k\leq h$, then the TM will performs $\frac{k^2}{2}+k+1$ transitions before stopping (and rejecting $w$), while if $k>h$, then it will make $\frac{h^2}{2}+h+1$ transitions. So, the worst case correspond to the maximum of the function
$$
f(h,k,j)=\cases{\frac{k^2}{2}+k+1, \quad k\leq h\\ \frac{h^2}{2}+h+1,\quad k> h}
$$
on the constraint $h+k+j=n$, $j>0$, and it is not difficult to see that it is reached for $|h-k|=1$ and $j=1$.
Summing up: the worst case is reached when $w$ belongs to the language $L$, and the TM must carry out $O(|w|^2)$ transitions.

If you want to play with your TM and see the exact number of transitions, go here, compile and load a word, enjoy!


I suspect the biggest problem is going to be the gap between role 3's.  So, one possible approach would be to schedule 8 rounds at a time, and for each block of 8 rounds, make sure that every player gets assigned role 3 exactly once.

This can be done as follows.  For the first round, randomly pick N/8 people to be role 3 in the first round.  Then, randomly pick N/8 people who haven't been picked yet to be role 3 in the second round.  Continue until you have scheduled all of the role 3's for all 8 rounds.   This will ensure that each player is role 3 exactly once in those 8 rounds; and that in each round, exactly N/8 people have role 3.

You could then complete the schedule by randomly scheduling role 2's and role  1's among the remaining people (with the right probabilities).  This would be pretty simple to implement and might be good enough.

What if people start complaining about the role 2's?  Well, you could schedule them nearly-equally, too, with a modest modification.  As before, schedule 8 rounds at a time.  We'll try to ensure each player is assigned role 3 exactly once in those 8 rounds; and that most players are assigned role 2 twice, once in the first 4 rounds and once in the last 4 rounds (but we won't be completely perfect about that).  We'll start by assigning the role 3's as described above and fix their assignment.

Next, we'll assign  role 2's to the first 4 rounds.  In the first round, randomly pick a subset of N/4 people who don't have any assignment in that round, and assign them role 2.  In the second round, out of the people who  don't have any assignment in that round and who haven't been assigned role 2 yet, randomly pick a subset of N/8 of them and assign them role 2.  Continue.  In each round, we find the set of people who don't have a role assigned to them in that round yet and who haven't been assigned role 2 yet, and randomly pick a subset of size N/4  from that set; everyone in that subset is assigned role 2.  In rounds 1-3, it is nearly guaranteed that this set is larger than N/4, so we can pick a subset  of the appropriate size.  In round 4,  this set might be smaller than N/4; if so, assign everyone in that set role 2, and then randomly pick other people who don't have an assignment in that round to be role 2 until you have N/4 role 2a's in that round.  In this way, most people are assigned role 2 exactly once in the 4 rounds, with a few people who get assigned role 2 zero or two times (due to round 4 being imperfect).

Then, do the same for role 2 in rounds 5-8.


Runtime difference bewteen Union by Rank and Union by Size for union-find

If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same [$O(m\alpha(m,n))$]. But notice that Wikipedia uses union by rank in order to prove the upper bound $O(m\log^*(n))$ because for proof purposes the union by rank algorithm is simpler to handle. On the other hand if you are implementing such a data structure you usually want to allow the user to access the sizes of the sets in the structure and thus use union by size method in order to keep track of the sizes and don't waste space for an extra array.

Its worth mentioning if we don't combine them with e.g. path compression both work in amortized $O(log(n))$.

This is a good lecture on this topic. It contains references to all the papers proving bounds for the problem. It also contains explanation of what $O(m\log^*(n))$ and $O(m\alpha(m,n))$ mean.


Break keyword outside a loop is syntax error or semantic error?

Both work, so how you do it is up to you. But there are a couple of reasons to consider doing it during a post-parse analysis:

While it is certainly possible to define two different types of block, one in which break is legal and the other one in which it isn't, the result is a lot of duplication in the grammar, and a certain complication because you have to allow break inside blocks which are themselves contained inside a looping construct. If you allow compound statements without explicit blocks, like if (condition) break;, then you also need to define different if statements, etc. This rapidly gets out of hand unless you have a tagged formalism like that used in ECMAScript.

Detecting the error in a post-parse scan will allow you to produce better error messages. Rather than just presenting the user with some kind of syntax error message (which might be "unexpected token 'break'"), you can actually provide a meaningful error message like "'break' statement cannot be used outside of a loop."