NP-Completeness of a Graph Coloring Problem

It is quite simple to show that the alternative formulation is NP-hard. The reduction is from the vertex coloring problem. Given a graph G with $n$ vertices, we create an instance of the above problem with $n$ output vertices and $n$ input vertices. Weights are set as follows: For all $i$, let $w_{ii}=1$. For $i \neq j$, if there is an edge between vertex $i$ and vertex $j$, let $w_{ij}=w_{ji}=1$, else let $w_{ij}=w_{ji}=0$. In addition, let $\beta=1$.

This is quite obvious but difficult to describe why the reduction is correct.
Let $\mathcal{C}$ show the instance of the graph coloring and $\mathcal{R}$ show the reduced instance of the problem.
To show the above reduction gives a correct solution we need to show that
(1) every valid coloring for $\mathcal{R}$ is valid for $\mathcal{C}$ as well.
(2) the answer given by $\mathcal{R}$ is minimal for $\mathcal{C}$.

If $i$ and $j$ are two adjacent vertices of $\mathcal{C}$,
then they must have different colors in $\mathcal{R}$.
That is because if $i$ and $j$ are adjacent and they have the same color,
the fraction $\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ would result in $\frac{1}{1+X}$,
where $X$ has a positive value.
Therefore, the condition does not hold.
In addition, every valid (but not necessarily minimal) coloring for $\mathcal{C}$,
is a valid coloring for $\mathcal{R}$ as well.
It follows the fact that in a valid coloring of $\mathcal{C}$,
every pair of adjacent nodes have different colors,
so the condition holds for all the colored edges of $\mathcal{R}$ in the solution.
Since every coloring of $\mathcal{C}$ is a valid coloring for $\mathcal{R}$,
the minimal solution to $\mathcal{R}$ must be a minimal solution to $\mathcal{C}$
as well.
Otherwise, it is not a minimal one because the solution to $\mathcal{C}$
gives a solution with a smaller number of colors.


Let $C$ be the collection of all c.e. sets.
One way to understand Rice's theorem is to say that every computable map $f : C \to \mathsf{bool}$ which preserves equality of sets is constant. (By "respects equality of sets" we mean that $f$ actually accepts codes of c.e. sets, but it maps any two codes for the same set to equal values).

Let's answer your question. Suppose we have a computable map $g : C \times C \to \mathsf{bool}$ which respects equality of sets. We want to prove it is constant. Then for every $y \in C$, the map $x \mapsto g(x,y)$ is constant by Rice's theorem. Likewise, for every $x \in C$, the map $y \mapsto g(x,y)$ is constant by Rice's theorem. But a map $g$ which is constant in each argument separately is constant.


Why injection into sum type apparently leads to ambiguity?

I think the key point here is $\sigma$, $\tau$ and $\phi$ are type variables, and not specific types. So, what the typing rule for $\operatorname{inl}$ says is that $\operatorname{inl} M$ is of type $\sigma + \tau$ for any $\tau$. The names of type variables don't matter, what matters is where else are you using the same type variable.


What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

If an $L$-complete problem (under first-order projection, or $NC^0$-reduction) has $NC^1$ circuit, then we have $L=NC^1$.

The $NC^1$ circuit for an arbitrary language $\mathbb{L}\in L$ is obtained by first projecting (in case of first-order projection) or doing a constant-depth transformation (in case of $NC^0$-reduction) to obtain an instance of the $L$-complete problem. Then, plugin the $NC^1$ circuit for the complete problem to solve the original problem overall.


Measuring difference between two sets of neural network weights?

One way to compare two neural networks is to compare how similar their predictions are, on typical instances.

Ideally, we'd like to compute the expected value of this similarity, taken over the distribution on instances.  However, as you say, the input space is high-dimensional, so the integral is hard to compute.  Also, the distribution on instances typically isn't known in any analytical or useful form.

Therefore, the standard trick is to estimate this expected value, using sampling.  We draw a sample of instances, compute the similarity of the predictions from the two networks on each instance, and take the average of those similarity values.  If the sample is large enough, this should be a good approximation to the expected value (to the integral).  So, you'll set aside a separate validation set, and then compute the average similarity between the two networks' predictions on this validation set.

I can formalize this more precisely.  Let $f,g$ be the two classifiers.  Suppose there are $k$ classes.  Assume you are using a softmax layer at the output of the neural network.  Then the output of a classifier $f$ on instance $x$ is a $k$-vector $f(x)$ whose $i$th component can be interpreted as the probability that $x$ has class $c$ (as predicted by the classifier).  So, we want some way to measure the similarity of the two $k$-vectors $f(x),g(x)$, i.e., the similarity of those two probability distributions on the $k$ classes.  You can use any distance metric or similarity measure on probability distributions.

Let $d(\cdot,\cdot)$ represent a distance measure on two distributions (or, more generally, a dissimilarity measure -- it need not be a metric).  Ideally, we'd like to compute $\mathbb{E}[d(f(X),g(X))]$ where the expectation is taken with respect to a random variable $X$ that is distributed according to the input distribution on instances.  To approximate this, we compute

$$D = {1 \over n} \sum_{j=1}^n d(f(x_j),g(x_j)),$$

where $x_1,\dots,x_n$ is a validation set that is held out and set aside for this purpose.  The validation set should be separate from the training set.

You can now instantiate $d$ with any distance measure on distributions of your choice.  Some reasonable choices include: KL divergence, or the Jensen-Shannon divergence (a symmetric version of the KL divergence);  total variation distance; earth mover's distance; or a very simple measure where $d(u,v) = 1$ if $\arg\max_i u_i \ne \arg\max_i v_i$, else $d(u,v)=0$ (i.e., compare whether both networks predicts the same class as the most likely class).

This approach is suitable if you want to measure how similar the predictions of the two neural networks are, without regard to their internal weights -- i.e., treating them as a black box.  I don't know how to compare how similar their internal structure is; there are probably many non-trivial transformations to networks that compute essentially the same thing, but with very different-looking weights.


Is my grammar correct for this context-free language?

In dealing with CFGs, it's often useful to work from the inside out. Clearly
$$
S\rightarrow aSa
$$
will generate all strings of the form $a^nSa^n$, for $n\ge 0$. Then all you have to do is allow the possibility that $S$ will also eventually generate $bb$, which we can do by the production $S\rightarrow bb$, giving the grammar
$$
S\rightarrow aSa\mid bb
$$
or, if you wanted to be explicit about the $bb$ central part, you could write
$$\begin{align}
S&\rightarrow aSa \mid T\\
T&\rightarrow bb
\end{align}$$
The problem with your grammar is that it can't guarantee that there will be the same number of $a$s on each end of a generated string.


A single finite machine is never Turing-complete.  (Such a machine with $n$ bits of internal memory has only $2^n$ states, so it can be modelled as a DFA with at most $2^n$ states.)  So, strictly speaking, it only makes sense to even ask about Turing-completeness when you have a machine model that is unbounded, or when you have an infinite family of machines $M_1,M_2,\dots$ of increasing size.

For similar reasons, strictly speaking, the computer sitting on my desk is not Turing-complete, either, because it is finite.  Nonetheless, it is useful to think of it as Turing-complete, in a looser sense: there is a natural abstraction of my machine where we disregard its finiteness (consider an abstract model where instead of being limited to 1TB of disk space, it has an unlimited amount of disk space).  For many purposes, the differences between my actual finite machine and the abstract, idealized machine with unlimited storage isn't very important.  But for your question, the difference can't be ignored, and to make your question well-specified, you'd have to think about how you plan to address this important distinction.

If you're interested in computing models that are somehow "simple"/"small" yet Turing-complete, you might be interested in rule 110, tag systems, and the lambda calculus.  See also
Universal binary rewriting system.  Do some searches on these terms on this site (and elsewhere) to learn more about these topics.


Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

Mikkel Thorup's paper Undirected Single-Source Shortest Paths with Positive
Integer Weights in Linear Time shows an $O(m)$ time algorithm for single-source shortest paths on undirected weighted graphs. That immediately implies an $O(mn)$ time algorithm for all pair shortest paths, which is the optimal $O(n^2)$ in your scenario.


It depends.  If it's a lot of data and a little bit of computation, yes, there is no net savings.  If it's a little bit of data and a lot of computation, no, there is a net savings.  It all depends.  Normally a GPU is used for situations where the amount of computation time saved greatly outweighs the time to transfer the data -- such as training machine learning models, or rendering complex graphics.


Time complexity is not god-given but is rather defined by the model of computation. To take a simple example, what is the time complexity needed for adding two numbers? In the RAM machine model, this operations takes constant time, as long as the numbers are not "too big". The rationale is that modern hardware implements addition as a fast machine instruction; if the numbers are not "too big" then they fit into single registers. The same reasoning holds for shifts. You have to be careful, however, that the size of the relevant quantities doesn't blow up.


Why are decision problems commonly used in complexity theory?

Oftentimes decision problems are used because they allow a precise and simple definition of the problem and, as stated, many other problems can be converted to an equivalent decision problem.

Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.


30 years ago research into cache-coherent shared memory was just beginning.  There were machines where you could send messages between processors.  By 1983 there were a few (room sized) machines where processors could communicate through a shared memory interface (for example, the Cray X-MP), but they didn't have cache coherence.  Most communication between processors in the early to mid '80s was done using message passing APIs.  Today almost everyone uses the MPI standard for message passing APIs.  The MPI standardization process started in 1992.

Cache-coherent shared memory multiprocessors and shared memory programming (for performance (as opposed to multi-threaded programming, which can be a convenient way to organize programs that need to interact asynchronously with the outside world)) started becoming somewhat common in the 1990s for systems with 10s of processors.  The OpenMP standard for specifying parallel computation in Fortran or C was first published in 1997.  Today (2013) you can buy a shared-memory machine with 8 hardware contexts for a few hundred dollars, and you can buy a shared-memory machine with 10s of hardware contexts for a few thousand dollars.

Hardware offload (to GPUs) started becoming popular when NVidia released the CUDA SDK for their GeForce GPUs in 2007.  The computing model with hardware offload is heterogeneous and in flux (currently some computing is done on the main processor, which tends to be shared-memory, then data gets copied back and forth between the processor and the GPU, some computing is done in the many vector lanes on the GPU, which can share some memory, but also have some private memories, and then the results are copied back to the main processor.) It appears as if most vendors are trying to come up with approaches to make the movement between cpu and gpu more streamlined.

Meanwhile in the last 30 years the advent of techniques to dramatically improve single-thread performance have also internally leveraged a great deal of parallelism.  Deep pipelining, superscalar and branch speculation techniques allow tens of instructions from a single thread to be in flight simultaneously.  Each CPU in the Cray X-MP in 1983 could complete a theoretical peak of 200MFLOPS with a 105MHz clock, whereas a single core today might be able to do 12 GFLOPS with a 3GHz clock.  So, many computations that would have needed to be hand-parallelized 30 years ago do not need to be explicitly parallelized today.


Constructing inequivalent binary matrices

I have made some progress towards answering this question. I am posting here in case anyone else is interested and also because this construction might have some usefulness for (directed) graphs.

Count the number of 1s in each row. Let $a_0$ be the number of rows with zero 1s, $a_1$ the number of rows with one 1 and so on up to $a_8$ which is the number of rows that have eight 1s. Obviously $\sum a_i=8$. The proposed parametrization that I have come to after trial and error is:
$$(a_1,\cdots, a_8; T, S)$$
where T is the trace of the matrix and S is $1$ if the matrix is symmetric and $0$ otherwise.
T runs from $0$ to $\sum_{i=1}^8 a_i=8-a_0$.

From my trials and errors it looks like that if two matrices are different in this parametrization then they belong to different equivalence classes, so to construct a representative in each class we just scan through the space of parameters as described above.

(Update) It turns out that this parametrization works fine for n=2 but not for n=3 as it can be seen by a brute force calculation. I still think it provides some insight on the structure of the answer and I invite people to try and modify/extend it to cover the most general case.


Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$

Here is what happens when you expand the recurrence:
$$
\begin{align*}
T(n) &= n^{5/2} + 4(n/2)^{5/2} + 4^2(n/2^2)^{5/2} + 4^3(n/2^3)^{5/2} + \cdots \\ &=
n^{5/2} \left(1 + \frac{4}{2^{5/2}} + \left(\frac{4}{2^{5/2}}\right)^2 + \left(\frac{4}{2^{5/2}}\right)^3 + \cdots \right).
\end{align*}
$$
Since $4/2^{5/2} = 1/\sqrt{2} < 1$, the large bracketed expression converges, and so the answer is $T(n) = \Theta(n^{5/2})$.


Any simple cycle satisfies the conditions, so you can use any standard algorithm for finding cycles in a directed graph.

For example: decompose into strongly connected components.  Pick one component.  Start following an arbitrary walk through vertices within that component.  As soon as you hit a vertex the second time, you can construct a cycle.


It's like magic, isn't it?

Here's a visual depiction for you, and hopefully it will make it easier for you to understand. This circuit is something called a half-adder; a half-adder is a special kind of adder -- the most base level kind of adder -- that takes two values, A and B which are the addend and auged respectively, and outputs them into the sum. If the addend and augend overflow, then the overflow is placed into a special output called $C_{out}$, which means "carry out."

Well, to chain these together, we need to take two half adders and put them together in order to construct something called a full-adder. What makes a full-adder special is that it takes another input, $C_{in}$ as well as the addend and augend, and performs an addition on all three of those bits.  Here, the half adder I described above has been put into a "black box" kind of configuration, where the visible details of the circuit are hidden, and the inputs and outputs are provided instead. Notice, just like the half-adder, we have a sum and a $C_{out}$ too.

Well, to construct bigger adders, such as four bit adders, we need to chain those full-adders together, and this is when the pattern becomes even more obvious:

And to construct an 8 bit adder, you put two four bit adders together. To construct a 16 bit adder, you put two eight bit adders together. To construct a ... well, you get the point.

So, what's all the 1 and 0 nonsense that I'm hearing about? (Read: how in the heck did someone come up with all of this).

Easy. We have things called "logic gates" which are represented by a couple of symbols to start with, but the simplest way to explain it is in the form of something called a truth table, but what these "True" and "False" values really represent is 1 for true and 0 for false -- but don't worry about that, yet. The first two columns: p|q are a set of truth values that are then evaluated for the other columns. Where $p\wedge q$  represent $p$ and $q$, $p\vee q$ represent $p$ or $q$, and the last column represents $p$ xor $q$

The last operator, xor is a special operator. It is the english equivalent of "I either __ or __" and the implication is that both cannot happen at the same time.

So when we're connecting these in relation to the individual circuit symbols, you can check those out here.

Putting these all together, with the special truth tables that I've shown you, you can clearly see that in the case of the half adder, walking through a set of logic values you can determine what these propositions mean in terms of those two binary truth values.

So, what's all this mean in terms of our base? Our system of counting? Well, as you may know, it is possible to convert a number of an arbitrary base (ours is 10) to another arbitrary base (in the case of the circuit, it is base two). There are many ways to do that, one of which is by using wolfram alpha; however, the manual way is fun too, if you want to learn how.

Let's count:

0        0000

1        0001

2        0010

3        0011

4        0100

5        0101

6        0110

7        0111

8        1000

9        1001

10       1010

11       1011

12       1100

13       1101

14       1110

15       1111

16      10000 <-- Rollover

The set of numbers on the right are binary numbers. The numbers on the left are numbers in our base, base 10. If you'll notice, the far right column, ex. 000[0], is the 'ones' column. This represents one one. The second column, ex. 00[0]0, is the 'twos' column. The third column, ex. 0[0]00, is the fours column. The fourth column [0]000 is the 'eights' column. Notice how the power values are, increasing in powers of two. Make more sense now?

So what makes these circuits work? Consider the half-adder. Those inputs a and b represent some arbitrary value coming from the outside. The first portion of the half adder is a xor gate. Look in the table for what happens when two true values are applied (1's), the output is 0. Therefore the sum is zero. Now consider the and gate, what happens when two true values are applied to the and gate? the output is one. So, we derive the sum from the output of the xor gate (which is 0), and we derive the $C_{out}$ from the and gate which is (1) if A and B are both (1).

Edit: More Circuits

I've added these and I've also made YouTube video of them working, just as I promised.

Videos:

If I get another request, I'll make another video and upload it, showing the internals of what it REALLY looks like as the circuit is going through its cycles.

Here are some adders

Here is a demonstration of the gates

Make more sense now?


Contrasting Peterson’s and Dekker’s algorithms

Your informal descriptions of the algorithms is wonderful.

I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom.  Neither algorithm is starvation free or fair.[ed: as pointed out in the comments, both algorithms are starvation free, and Peterson's algorithm is also fair].  Dekker's solution was the first mutual exclusion algorithm using just load and store instructions.  It was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968.  If you read through the paper you see Dijkstra work through a number of attempts, recognizing the problem with each, and then adding a little bit more for the next version.  Part of the inefficiency of his algorithm comes from the fact that he starts with a turn-taking algorithm and then tries to modify it to allow the processes to progress in any order.  (Not just 0,1,0,1,...)

Peterson's algorithm was published in 1981, after more than a decade of experience and hindsight about Dekker's algorithm.  Peterson wanted a much simpler algorithm than Dekker so that the proof of correctness is much easier. You can see that he was feeling some frustration with the community from the title of his paper.  Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981. Very quick read and very well written. (And the snide remarks about formal methods are priceless.)  Peterson's paper also discusses the process by which he built his solution from simpler attempts.  (Since his solution is simpler, it required fewer intermediate steps.)  Note that the main difference (what you call "dominance" rather than "submissiveness") is that because Peterson started out fresh (not from the turn-taking algorithm Dijkstra started with) his wait loop is simpler and more efficient.  He realizes that he can just get away with simple looped testing while Dijkstra had to backoff and retry each time.

I feel I must also mention Lamport's classic Bakery algorithm paper: Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974.  The Bakery algorithm is arguably simpler than Dekker's algorithm (and certainly simpler in the case of more than 2 processors), and is specifically designed to be fault tolerant.  I specifically mention it for two reasons.  First, because it gives a little bit of history about the definition of the mutual exclusion problem and attempts to solve it up to 1974.  Second because the Bakery algorithm demonstrates that no hardware atomicity is required to solve the mutual exclusion problem.  Reads that overlap writes to the same location can return any value and the algorithm still works.

Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987.  In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section.  Again, it guarantees mutual exclusion and deadlock freedom, but not fairness.  It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention.  (When there is contention, it falls back on an O(N) test.)  He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses.  (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

In all: I'd say Dekker's algorithm itself is interesting mainly from a historical perspective.  Dijkstra's paper explained the importance of the mutual exclusion problem, and demonstrated that it could be solved.  But with many years of hindsight simpler (and more efficient) solutions than Dekker's have been found.


How to find the reverse of a binary string with simple binary operators?

Yes, absolutely.  Every boolean function can be implemented by a circuit.  In this case, it suffices to XOR bits 1 and $n$; bits 2 and $n-1$; and so on; and then take the NOR of all of the outputs of these XOR gates.


Undecidability of two Turing machines acting the same way on an input

You were very close to the answer. The special case you mentioned can be handled by hand. Modify the machines resulting from the reduction such that, for each transition, where the machine halts and rejects, let the resulting machine go into an endless loop instead.

Now each machine either accepts or goes into an endless loop. That means, checking if both machines are equivalent on an input $x$ is checking whether both accept the input $x$.


Survivors classes in the extremely unlikely scenario of P = PSPACE

The time hierarchy theorem still tells us that
$$\mathrm{P}\subsetneq \mathrm{EXP}\subsetneq\mathrm{2\text{-}EXP} \subsetneq \dots\,,$$
and likewise for the analogous space classes and nondeterministic time and space classes.


What is the earliest use of the "this" keyword in any programming language?

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years.

It also used the this keyword for the same concept, which can be seen in this book chapter extract:

  class Linker;
  begin
     ref(Linker) Next, Sex, Employment;
     text ID;

     procedure Add_to_List(LHead); name LHead; ref(Linker) LHead;
     begin
        Next :- LHead;
        LHead :- this Linker
     end..of..Add..to..List;

     procedure Onto_Lists(Gender,Occupation);
         name Gender,Occupation;
         ref(Linker) Gender,Occupation;
     begin
        Sex :- Gender;
        Employment :- Occupation;
        Gender :- Occupation :- this Linker
     end..of..Onto..Lists;

     InImage;
     ID :- Copy(SysIn.Image);
     InImage;
  end--of--Linker;


Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

This problem can be solved in polynomial time.

For such a graph $G=(V,A)$, turn it into a new weighted undirected graph $G'$ as follows, where we denote respectively by $d^{\mathrm{in}}(v)$ and $d^{\mathrm{out}}(v)$ the in-degree and out-degree of $v$.

For every $v$, we have that $d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v)$ is even. Otherwise, the graph cannot be changed to an Eulerian graph.

For each edge $(u,v)\in A$, construct two vertices $u_{\rightarrow v}, v_{u\rightarrow}$ and an edge with weight $1$ between them.
For each vertex $v\in V$, add an edge with weight $1+\epsilon$ (where $\epsilon$ is a small positive number that depends on the size of the graph) between $v_{u_1\rightarrow}$ and $v_{\rightarrow u_2}$ for all $u_1,u_2\in V$ such that $(u_1,v),(v,u_2)\in A$.
For each vertex $v\in V$, construct $\left|d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v) \right|/2$ vertices $v_1,v_2,\ldots$. If $d^{\mathrm{in}}(v)\ge d^{\mathrm{out}}(v)$, add an edge with weight $1$ between $v_i$ and $v_{u\rightarrow}$ for all $i$ and $u\in V$ such that $(u,v)\in A$. Otherwise, add an edge with weight $1$ between $v_i$ and $v_{\rightarrow u}$ for all $i$ and $u\in V$ such that $(v,u)\in A$.

Recall that a directed graph is Eulerian iff each vertex has equal in-degree and out-degree, assuming the underlying undirected graph is connected. Now we can see finding a minimum number of edges to reverse in $G$ is equivalent to finding a maximum weight matching in $G'$, by reversing all edges $(u,v)$ such that $u_{\rightarrow v}$ is matched with $v_{u\rightarrow }$ in the maximum matching.


How could I prove that $B$ reduces to $A$ in polynomial time in this case?

Take $a\in A$ and  $b \notin A$.

the reduction defined as follows:
$$f(x)=\begin{cases}
a & x\in B\\
b & x\notin B
\end{cases}$$

It is easy to see that $f \in \text{POLY}$ since $B\in\text{P}$, and the correctness is trivial.


The C standard does not bother to distinguish between different kinds of errors encountered during parsing, but it is possible to categorise errors according to which clause of the standard applies.

The second line in your query (int /* n; -- assuming that there is no */ in the remaining program text) is covered by a requirement in the description of phases of translation, §5.1.1.2/1; in particular, in phase 3: (emphasis added)

  The source file is decomposed into preprocessing tokens and sequences of
  white-space characters (including comments). A source file shall not end in a
  partial preprocessing token or in a partial comment. Each comment is replaced by
  one space character. New-line characters are retained. Whether each nonempty
  sequence of white-space characters other than new-line is retained or replaced by
  one space character is implementation-defined.

The other two errors are also produced in phase 3, because the unmatched quote cannot be decomposed into a preprocessing token. The error is mentioned specifically in §6.4/3:

  A token is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. If a ' or a " character matches the last category, the behavior is undefined.

That probably justifies the use of the phrase "lexical error", at least as an informal description.


What advanced math topics are recommended for computer science?

If you want to do theoretical computer science, more math the better. Ultimately, learning math is not so much about learning specific topics, though that is of course important, it is also about gaining mathematical maturity, which means being able to think mathematically, being able to formalise and prove things, being able to abstract away inessential details and capture the essence of a problem. Of course, actually knowing lots of useful theorems is important too.

For crypto you'll need (at least) algebra (group theory etc), number theory, and discrete mathematics. Some logic wouldn't hurt either.

Linear algebra will help with machine learning and computer graphics.

Logic, topology and category theory will help for many Theory B topics (programming language semantics etc).

The list goes on ...


Notice that it's not unreasonable to slightly extend this problem to an arbitrary number of triples. For example, the single triplet [123] is a reasonable candidate to be in your language, since $1+2=3$. Similarly, [280][135] is another reasonable candidate, since $12+38=50$. With that in mind, I'll extend the language to all strings of an arbitrary number (including zero) of triples that satisfy the summation requirement. I'll also decide that we'll accept a sequence of triplets only if they represent a sum without a final carry, so we wouldn't accept the string [000][000][190] since $100+900=1000$ and there's a final carry out (though [000][000][190][001] would be accepted).

The fundamental idea is a very common one: "remember" the current state of the problem by using one state in the DFA for each possible configuration. Here's what we might do:

Label the start state $start$. We haven't read any input yet. This will also be the unique final state.
Let state $t$ remember that we've seen the first [, so we have the move $\delta(start, [)=t$.
Next, construct ten states $p_0, p_1, \dotsc,p_9$ to remember the first digit. We'll have the moves $\delta(t,i)=p_i$, i.e., from $t$ we'll be in state $p_i$ after having seen input $i$.
Now make twenty more states, $q_0, \dotsc,q_9$ and $c_0,\dotsc,c_9$. The $q$'s will record the sum of the first two inputs if there's no carry and the $c$'s will record the sum if there is a carry. In other words
$$
\delta(p_i,j) =\begin{cases}
                  q_{i+j} &\text{if } i+j\le 9\\
                  c_{(i+j)\bmod{10}} &\text{if } i+j\ge 10
               \end{cases}
$$
Then make two states, $a,b$ to note whether the third input is the sum of the first two and wehther or not we've generated a carry. From state $q_k$ (sum is $k$ with no carry) we'll pass to state $a$ if the third input is the digit $k$. Similarly, we'll have $\delta(c_k,k)=b$ meaning that we've just seen the appropriate third digit and we had a carry.
Now we've read the first triplet and we're expecting to see a ]. In state $a$ we know we've completed the first triplet and don't have to adjust any subsequent triplet, so $\delta(a,]) = start$, i.e., we loop back to the start and accept if there's no further input. On the other hand, if we're in state $b$ then we have a correct digit sum, but we also have a carry, so we can't yet accept when we see a ], instead we need to read another triplet. We'll process the ], read a [ and duplicate the whole process again, this time adjusting for the carry. We'll then have $\delta(b, ])=u$ and $\delta(u,[)=v$.
Starting anew from state $v$, we construct 34 new states exactly as we did in steps (1) - (6). The only difference is that the transitions from the new states corresponding to the original $p$ states (call them $p'_i$) in step (4) we'll compensate for the previous carry in and have
$$
\delta(p_i,j) =\begin{cases}
                  q_{i+j+1} &\text{if } i+j+1\le 9\\
                  c_{(i+j+1)\bmod{10}} &\text{if } i+j+1\ge 10
               \end{cases}
$$
The final difference with these new states is that if we get to the new state, $b'$ corresponding to the original $b$, then on seeing ], we go back to state $start'$ and start again.

In high-level terms, we have two nearly-identical functions to check whether a triplet $t$ is valid:

$N(t)$ which checks whether $t$ is valid, assuming no carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.
$C(t)$ which checks whether $t$ is valid, assuming a carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.

Then, we would have the following pseudocode

c = 0
while there's a triplet t to process
   get t
   if c = 0
      c = N(t)
   else
      c = C(t)
end loop
if c = 0
   accept
else
   reject


Why does a software video encoder create higher quality output than a hardware video encoder

There is no reason in principle why hardware would have to produce worse results than software. But there are two problems:

Better quality requires better algorithms, and better algorithms in hardware usually take more circuits and cost more money, while higher quality in software can be almost free.
Real-time encoding must finish in given time. If you run a video conference you have one second to encode one second of video. Even if you knew how to produce better quality in more time, you are not allowed to. But if you use an offline encoder, that can give you an option to encode an hour of video in six hours with low quality, in twelve hours with medium quality, or in 36 hours with highest quality.

And of course you can have the latest and best quality software encoder at any time. If your hardware is three years old and not very good, replacing it with much better new hardware is inconvenient and costly.


Showing that Independent set of size $k$ can be decided using logarithmic space

You can use the following algorithm.

I assume that the vertices are labeled $1,\ldots,m$. You enumerate all $k$-tuples $\{1,\ldots , m\}^k$. This can be done by reserving $k$ counters on the TM tape. Since $k$ is not part of your input this needs only $O(\log m )\subseteq O(\log n)$ space. However for every $k$-tuple you can test if it is an independent set. Simpy test all pair of selected vertices if there are not connected by an edge. Again, since $k$ is fixed the edges you have to test (depending on the current tuple) are known. Thus this test can be hard-wired into the TM program, and therefore needs no extra-space.


What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.


What is the relation between a web server and a local file serve in distributed systems?

Often the content is stored on a local filesystem (or file server); the web server accesses the content by reading it from the local filesystem (or file server), then provides it to the web client on demand.  So the web server is making use of a local file server -- in that sense the web server is a client of the local file server.


Can one get Turing-completeness without nontermination?

Many total languages, including Agda and Coq, allow you to define coinductive data types. These model infinite objects, like infinite lists.

Obviously, a function producing an infinite list cannot terminate. However, it must, in a total language, be productive. This means that any finite prefix of the produced infinite list can be computed in finite time. Coq and Agda have productivity checkers to ensure this, like they have termination checkers for functions which consume inductive data types.

Using these coinductive data types, you can model infinite executions. In the example you linked, 'running' a brainfuck program produces a trace, which is a potentially-infinite list of machine states.

Whether this is enough to declare the language 'Turing-complete' is, I guess, a question for philosophers. Agda only ever allows you to inspect a finite prefix of the generated trace, so you can't 'run' a program for an infinite amount of time. Then again, no physical machine can run a program for an infinite amount of time. And in practice, you can just disable Agda's termination checker for the one function that prints out your potentially-infinite trace.


How to calculate time complexity of this problem?

Given any reasonable computational model, we can provide an algorithm to solve your problem that reads the input (stopping at $10$ symbols should it be longer), stores the length, and while such length is less than $10$, appends the needed symbols and updates the total length.

This algorithm performs a constant amount of work at most $10$ times, which means that there exists a constant $c$ that bounds the running time for any size of input. By definition, such an algorithm has complexity $\Theta(1)$.

Observe that if you require the output to be a copy of the input for strings longer than $10$, then, depending on your computational model, you might need to physically copy the string, which takes time $\Theta(n)$.


Sipser exercise : variant of CNF is NL-complete

Let's assume for simplicity that each negated literal appears exactly once. Let $C_i$ be the clause containing $\lnot x_i$. Consider the graph whose vertices are the variables, and $x_i$ is connected to $x_j$ if $x_j \in C_i$. This is a kind of implication graph: in order to deduce that $x_i$ is false from $C_i$, we must have first deduced that $x_j$ was false from $C_j$.

Show that $x_i$ is forced to be false (i.e., unit propagation shows that $x_i$ has to be false) iff the set of vertices reachable from $x_i$ contains no directed cycle, something which can be checked in NL (using coNL=NL). The formula is unsatisfiable iff there exists a positive clause in which all variables are forced to be false (and so unit propagation gets stuck at this clause).

This shows that your problem is in NL. To show that it is NL-complete, reduce from directed reachability. Encode all edges incoming to $x_i$ by a clause of the form $\lnot x_i \lor \cdots$.


The objective function you describe satisfies two properties:

It is maximized at a solution.
It is non-negative.

One can think of many other functions satisfying these two properties, for example $\binom{N}{2} - L + C$ for every $C \geq 0$. The exact choice is not so important – indeed, they chose $N^2/2$ whereas they could have chosen $\binom{N}{2} = N(N-1)/2$.


A flawed theorem about regular languages

The concatenation of $L_1$ and $L_1^{\mathrm{R}}$ is not $\{awwa\mid w\in\{a,b\}^*\}$.


Shortest path given correct order of colours?

Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that sequence).  Then, find the shortest path in this new graph using any standard shortest-path algorithm.  If all weights are non-negative, you can use Dijkstra's algorithm on this graph; otherwise you can use Bellman-Ford on this graph.
See How hard is finding the shortest path in a graph matching a given regular language?.  Your problem is a special case of the problem solved there.  (Possibly also useful: Product construction for given two finite automata .)
Specifically, here is how the product construction works in your setting.  Let $(c_1,c_2,\dots,c_q)$ be the desired sequence of colors.  Then, for each $k=1,2,\dots,q-1$, you'll have an edge $(x,y,z,k) \to (x,y,z,k+1)$ in the new graph if there is an edge $(x,y,z,c_k) \to (x,y,z,c_{k+1})$ in the original graph; the weight of the edge is copied over from the corresponding edge in the original graph.  Now, find the shortest path from $(x_0,y_0,z_0,1)$ to $(x_1,y_1,z_1,q)$ in the new graph, where $(x_0,y_0,z_0,c_1)$ is the starting vertex in the original graph and $(x_1,y_1,z_1,c_q)$ is the ending vertex in the original graph.


An NFA with multiple starting states makes a non-deterministic choice of the starting state, in the same way that it makes non-deterministic choices throughout its operation. It is equivalent to an NFA with a single new starting state connected to the former starting states with $\epsilon$ transitions.

For example, here is an NFA which accepts the language of all words not containing all letters in the alphabet $\Sigma$. For each $\sigma \in \Sigma$ there is a state $s_\sigma$. For each $\tau \neq \sigma$, there is a self-loop labelled $\tau$ around $s_\sigma$. All $s_\sigma$ are starting states as well as accepting states. The state $s_\sigma$ is supposed to represent all words not containing $\sigma$.

In order to convert this to an NFA with a single starting state, add a new state $s$ which is the new starting state, and connect $s$ to all $s_\sigma$ with $\epsilon$ transitions. The semantics of both NFAs are exactly the same.


why is discrete maths needed to understand algorithms?

There are several angles to this question.

First, most algorithms work on discrete abstractions like graphs, trees, matrices, sequences. To understand what the algorithm does, you need some acquaintance with those. They are staple of discrete mathematics. To prove the algorithm works as claimed relies on said properties, and the proof is essentially doing discrete mathematics.

Second, to use algorithms successfully, you need to know how to map your real work problem to the above abstractions, that again means knowing their particularities.

Third, you usually will want to derive performance numbers, either to verify the algorithm works within given constraints (time, space), or to compare alternative approaches and evaluate tradeoffs. Again, a job for discrete mathematics.

Sure, you certainly can do a lot without going deeply into discrete mathematics (at least not openly), but it is a valuable toolbox.


Proving that a set of grammars for a given finite language is decidable

Hint: Combine the following two properties of context-free grammars:

Given a context-free grammar $G$ and a regular language $L$ (given by a DFA, say), there is an algorithm that constructs a context-free grammar $G'$ satisfying $L(G') = L(G) \cap L$.
Given a context-free grammar $G$, there is an algorithm deciding whether $L(G) = \emptyset$.


Multi-processing cpu utilization estimate

$P^n$ is the probability that all "cores" are idle simultaneously, hence $1-P^n$ is the probability that at least one core is in use.


Is it possible to form a PDA for this language?

Yes, the language is context-free.  I recommend that you ignore that article on geeks for geeks; its so-called "analysis" is stated in a way that is highly ambiguous, and appears to be faulty in some cases.
Hint: The language has the form $L = \{a^j a^k b^k b^{2j}\}$.  Build a PDA that non-deterministically guesses $j$.  (I assume you know how to build a PDA for $\{a^n b^n\}$ and $\{a^n b^{2n}\}$.)


For your first question, here is a hint:
$$
\Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1}] = \\
\sum_{i_k} \Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1} \land h(x_k) = i_k].
$$

Regarding the connection between universal and $k$-universal: Consider the family consisting of all constant functions. This family is 1-universal but not universal (for $|U|>1$).

However, it turns out that every 2-universal family is universal (exercise). The converse isn't true: for example, the family of all functions $h$ such that $h(x_1) = 0$ is universal but not 2-universal (for $m>1$).


Algorithmic Composition: generative vs transformative algorith

A generative algorithm tries to generate a new song out of nothing.

A transformative algorithm takes one song $s$ as input, and tries to produce a new song $s'$ by making some changes to $s$.


Why does decreasing the gap size in Shell sort never undo previous sorts?

Here is an argument that I find a bit easier to understand than the ones I've seen online. It's not super rigorous, but I think it could be made so. To start with, the claim that you ask about can actually be made stronger and still be true. From Sedgewick and Wayne's Algorithms:

  when an h-sorted array is k-sorted, it remains h-sorted

That is, we don't even need to assume that $k$ is less than $h$. Now, what does it mean that the array is $h$-sorted? Let us first define:

An $h$-inversion of two elements $x_i$ and $x_j$, where $i < j$, is an inversion $inv(x_i,x_j)$ for which $j-i=h$.

Here, $i$ and $j$ are indices. Simply put, an $h$-inversion is an inversion between elements that are $h$ indices apart in the array. Then we can define:

An $h$-sorted array is an array with no $h$-inversions.

If we accept these definitions, we only need to show that $k$-sorting the array does not increase the number of $h$-inversions. We will do so by looking at what might happen when we swap two elements $x_i$ and $x_{i+k}$ during a $k$-sort. But first, let's adopt the following notation:

Let $x_i|$ and $x_{i+k}|$ denote the elements with index $i$ and $i+k$ before the swap, while $|x_i$ and $|x_{i+k}$ denotes the elements with index $i$ and $i+k$ after the swap.

Then, because we only swap the elements $x_i$ and $x_{i+k}$ if $x_i > x_{i+k}$, we have

$ |x_{i+k} = x_i| > x_{i+k}| = |x_i$.

The equalities are obvious because the left hand and right hand sides really refer to the same element, before and after the swap. The notable thing is the inequality, which we will be using soon.

To keep things easy to visualize, let us look at two elements that are to the right of both $x_i$ and $x_{i+k}$. More specifically, the elements $x_{i+h}$ and $x_{i+k+h}$, with $h>k$.

$$
\left\{\ldots, x_i, \ldots, x_{i+k}, \ldots, x_{i+h}, \ldots, x_{i+k+h}, \ldots\right\}
$$

Since the array starts out $h$-sorted, we have

$x_i| < x_{i+h}$ , and
$x_{i+k}| < x_{i+k+h}$.

After the swap we have,

$|x_i < x_{i+h}$, because $|x_i < x_i|$, as established previously. Thus, no new inversion has been introduced involving indexes $i$ and $i+h$.

And for $x_{i+k}$ and $x_{i+k+h}$ we have either

$|x_{i+k} < x_{i+k+h}$, in which case no new inversion is introduced involving indexes $i+k$ and $i+k+h$,

or, and this is key,

$|x_{i+k} > x_{i+k+h}$, in which case a new $h$-inversion $inv(x_{i+k},x_{i+k+h})$ has been introduced. However, since $x_{i+k+h} < |x_{i+k} = x_i| < x_{i+h}$ and $x_{i+k+h}$ is $k$ positions to the right of $x_{i+h}$, we know that $x_{i+h}$ and $x_{i+k+h}$ will be swapped later in the $k$-sort, eliminating the $h$-inversion.

Thus, after the full $k$-sort, any such $h$-inversions introduced by the sort will have also been resolved by the sort.

We have only specifically looked at elements to the right of both $x_i$ and $x_{i+k}$, but very similar arguments can be made for elements to the left of both, or even with one element sitting in between (when $h<k$). I won't go into those cases here however, because this is already a long post.


How to solve recurrence of a binary tree

There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees.
Your recursive procedure actually computes two different functions: the first output is a Boolean function $b$ which measures whether the tree is balanced, and the second is an integer-valued function $h$ which computes the height of the tree.
The height function $h$ is defined as follows: if $T$ is a leaf then $h(T) = 0$, and if $T = (T_\ell,T_r)$ then $h(T) = 1 + \max(h(T_\ell),h(T_r))$. This function computes the height of the tree.
The balancedness function $b$ is defined as follows: if $T$ is a leaf then $b(T) = \mathsf{true}$, and if $T = (T_\ell,T_r)$ then $b(T) = b(T_\ell) \land b(T_r) \land |h(T_\ell) - h(T_r)| \leq 1$. In words, a tree is balanced if in every internal note $v$, the heights of the left and right subtrees differ by at most one.
As you can see, the argument of both functions is a tree.
Your recurrence describes the worst-case running time of the procedure as a function of the number of nodes. The base case is $T(1) = O(1)$ (when the tree is a leaf), and when $n > 1$,
$$ T(n) = \max_{\substack{n_\ell,n_r \geq 1 \\ n_\ell+n_r+1=n}} T(n_\ell) + T(n_r) + O(1). $$
The solution is $T(n) = \Theta(n)$. You can prove this by induction. In particular, if you replace $O(1)$ by $1$, a simple induction shows that $T(n) = n$.
In fact, it is not hard to check that your procedure has running time $\Theta(n)$ on any tree having $n$ nodes, since the recursive calls "visit" every node in the tree, and do $O(1)$ processing per node.


Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small.

Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$.  Let $H$ be a secure cryptographic hash function producing (at least) $n+k$ bits of output.

Let $a$ be an array of $2^k$ $n$-bit bitstrings.  This array stores the state of the filter, using a total of $n2^k$ bits.  (It does not particularly matter how this array is initialized; we can just fill it with zeros, or with random bits.)

To add a new value $x$ to the filter, calculate $i \,\|\, j = H(x)$, where $i$ denotes the first $k$ bits and $j$ denotes the following $n$ bits of $H(x)$.  Let $a_{i} = j$.
To test whether a value $x'$ has been added to the filter, calculate $i' \,\|\, j' = H(x')$, as above, and check whether $a_{i'} = j'$.  If yes, return true; otherwise return false.

Claim 1: The probability of a false positive (= new value falsely claimed to have been seen) is $1/2^{n+k}$.  This can be made arbitrarily small, at a modest cost in storage space, by increasing $n$; in particular, for $n \ge 128$, this probability is essentially negligible, being, in practice, much smaller than the probability of a false positive due to a hardware malfunction.

In particular, after $N$ distinct values have been checked and added to the filter, the probability of at least one false positive having occurred is $(N^2-N) / 2^{n+k+1}$.  For example, with $n=128$ and $k=16$, the number of distinct values needed to get a false positive with 50% probability is about $2^{(n+k)/2} = 2^{72}$.

Claim 2: The probability of a false negative (= previously added value falsely claimed to be new) is no greater than $1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$, where $N$ is the number of distinct values added to the filter (or, more specifically, the number of distinct values added after the specific value being tested was most recently added to the filter).

Ps. To put "negligibly small" into perspective, 128-bit encryption is generally considered unbreakable with currently known technology.  Getting a false positive from this scheme with $n+k=128$ is as likely as someone correctly guessing your secret 128-bit encryption key on their first attempt.  (With $n=128$ and $k=16$, it's actually about 65,000 times less likely than that.)

But if that still leaves you feeling irrationally nervous, you can always switch to $n=256$; it'll double your storage requirements, but I can safely bet you any sum you'd care to name that nobody will ever see a false positive with $n=256$ — assuming that the hash function isn't broken, anyway.


Necessary and sufficient condition for unique minimum spanning tree

Answer my own question by simply copying the comment made by @JeffE, the author of the lecture note：

  Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) – JeffE


Your channel is known as the Z-channel. Take a look at Marco Mondelli, S. Hamed Hassani, and Rüdiger Urbanke, How to Achieve the Capacity of Asymmetric Channels.


Concrete and simple applications for bipartite graphs

Assignment Problem would be one such example:

  There are a number of agents and a number of tasks. Any agent can be
  assigned to perform any task, incurring some cost that may vary
  depending on the agent-task assignment. It is required to perform all
  tasks by assigning exactly one agent to each task and exactly one task
  to each agent in such a way that the total cost of the assignment is
  minimized.

Hall's Marriage Theorem would be another:

  Imagine two groups; one of n men, and one of n women. For each woman,
  there is a subset of the men, any one of which she would happily
  marry; and any man would be happy to marry a woman who wants to marry
  him. Consider whether it is possible to pair up (in marriage) the men
  and women so that every person is happy.

The Mutilated Chessboard Problem can be solved using The Hall's Theorem:

  Suppose a standard 8x8 chessboard has two diagonally opposite corners
  removed, leaving 62 squares. Is it possible to place 31 dominoes of
  size 2x1 so as to cover all of these squares?


Common subgraph isomorphism with K vertex

The fact that the Maximum Common Subgraph is NP-complete suggests that your "dumb" algorithm is about as good as it gets. You certainly cannot expect a polynomial time solution.

There are a few approaches you could try, depending on the exact context you are working in, the details of which are more than can reasonably be reproduced here, but a good starting point would be Abu-Khzam et al.'s paper "The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover" (In Proceedings of AICCSA 2007, pp. 367-373). This describes a variety of exact approaches which exploit different properties of the input.


End-Of-The-Line Augmented Problem of PPAD

This question is answered in the original paper by Papadimitriou 1994 original paper (pdf). It turns out that the problem is not only NP-hard but also PSPACE-hard, this is theorem 2 on page 506.


Help in understanding 'reasonable' encoding of inputs

Unary encoding for values 0 <= k <= N takes O(N) space. Unary encoding of an n-bit number takes $\Theta(2^n)$ space. See the difference?


For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges?

If edges have real valued capacities, there may not exist a maximum flow which assigns an integer value to every edge. For example consider a single edged $s-t$ network with $c(s,t)=0.1$ where $c$ is capacity function. However if edges have integer valued capacity, there exists a maximum flow which assigns integer value to every edge because in each iteration of ford-fulkerson algorithm, each edge in residual graph is assigned an integer value. So the result is an integer.


Why is the satisfiability of ESO formulas not equal to the satisfiability of FO formulas?

You're right: an ESO sentence is satisfiable iff its first-order "matrix" - with relation/function variables replaced with corresponding relation/function symbols - is satisfiable.

TI'm not an expert here, but I think what's going on is "linguistic convenience." There are other related questions where we don't get coincision. For example, checking whether a first-order sentence is true in a given finite structure is usually harder than checking whether one of its "second-orderizations" is true in that same structure${}$('s reduct). Similarly, as you say validity for ESO sentences is strictly more complicated than validity for FO sentences. In this way it may feel more consistent to talk about ESO satisfiability rather than FO satisfiability if we're also talking about ESO validity, ESO truth in a given structure, etc.


Here is the transition table for your NFA:

q    s    q'
S0   b    { S1 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }

There are a few problems that prevent this from being a DFA:

Two valid transitions from state $S_1$ on $b$;
No valid transition from $S_0$ on $a$;
No valid transition from $S_2$ on $a$.

Problems (1) and (3) can be solved by introducing a new, "dead", state, $S_3$; the transition table becomes:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

To solve problem (2), we can simply note that the transition $S_1 \rightarrow bS_2$ doesn't buy us anything in terms of strings accepted; the only way to get to an accepting state after doing that is to take the transition $S_2 \rightarrow bS_1$, and we could simply have applied the transition $S_1 \rightarrow bS_1$ twice to do the same thing. We can simply remove this transition and the resulting NFA accepts the same language. Here's the transition table:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

We have no $\lambda$-transitions and each transition maps to a singleton set of states; this defines the following DFA:

q    s    q'
S0   b    S1
S0   a    S3
S1   b    S1
S1   a    S2
S2   b    S1
S2   a    S3
S3   b    S3
S3   a    S3

Now, we may argue using the Myhill-Nerode theorem to see whether we have redundant states. Consider the ways to get to a string in the language from state $S_0$. We can see any string in the language (by definition) and end up in an accepting state. This state constitutes an equivalence class we have not yet observed.

Consider $S_1$. Our first observation is that any string in the language, if encountered starting at this state, will also lead to an accepting state, hence another string in the language. However, we can also see the string $ab$, among others, so this constitutes a new equivalence class, and the state is required.

Consider $S_2$. Any string in the language, except $\lambda$, leads to an accepting state of the DFA. This is a new equivalence class and the state is not redundant.

Consider $S_3$. No strings lead from here to an accepting state, so this is yet another equivalence class under the indistinguishability relation, and the state must be kept.

Therefore, the DFA whose transition table is given above is minimal for the language it accepts. Furthermore, it accepts the language of the NFA originally proposed.

To prove the DFA accepts the target language, there are a variety of approaches. The easiest one is actually by stating three facts about the syntax of your DFA, which prevents the excluded condition from occurring in any accepted strings:

The transition from $S_0$ on $a$ leads to a dead state (no string begins with $a$);
There is no transition to an accepting state on $a$ (no string ends with $a$);
Applying $q \rightarrow aq'$ and $q' \rightarrow aq''$ consecutively always leads to the dead state, where these transitions are any of those in the DFA (no string contains $aa$).

I suppose this is a proof by cases, if knowing what to call the proof is important :D


Project to nearest point in convex polytope

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can solve this problem in polynomial time using several methods, one being the ellipsoid method (originally due to Kozlov, Tarasov and Khachiyan [1]).

We can write $\|y - x\|_2^2$ as $y^Ty - 2x^Ty + x^Tx$. Thus an equivalent problem is
$$
\min_y\ (y^Ty - 2x^Ty) \text{ such that } A y\leq b.
$$
This is a convex quadratic program, since in this case $Q$ is the identity matrix, which is positive definite.

[1] The polynomial solvability of quadratic programming, USSR Computational Mathematics and Mathematical Physics, 20(5):223–228, 1980; Science Direct


How many bits representation of data on tape of Turing machine consumes

Note that the usual representation of signed integers in binary is not the one you propose.

In general, though, being super-efficient about coding in Turing machines isn't really important. We mainly use Turing machines for:

computability, where we don't care about efficiency at all;
complexity, where we only care about efficiency up to constant or even polynomial factors.

We don't use Turing machines for real computation where we care about the "real" efficiency, where making your program twice as fast makes it twice as good.

So, from the point of view of Turing machines, it's completely adequate to code vectors and so on by something like the following. Pick any sensible format for the individual data items and write those out with each bit doubled (i.e., $1011$ becomes $11001111$). Then separate each item with $01$. This means that storing the vector/matrix/whatever takes "twice as many bits as it should" but that constant factor just isn't important for the things we use Turing machines for.


Why do we need full-fledged workstations running massive OSes with massive software?

You are conflating a number of issues here.

Why does my software have all these features to begin with?

Because other computers' software has those features, and network effects punish any software developer who doesn't follow the herd.

Let's take an example from your question: Why does my web browser need to do anything other than basic HTML and CSS? Well, have you ever tried browsing the modern internet with all JavaScript disabled? It's functionally unusable. The problem is that, once JavaScript existed in a widely used browser (Netscape), people started using it in their webpages. That meant that other browsers had to add support for it to prevent their users from complaining that webpages are broken. And once more users had support for it in their browsers, more webpage authors started assuming that users had it. Round and round the positive feedback loop goes.

Software developers have strong incentives for adding features to software, and strong disincentives for removing them or even changing them.

It's taking 25 years to kill Flash Player, despite it being an incredibly complicated, bug-ridden, security nightmare black box that Adobe themselves no longer wants anything to do with. You know that all hell is going to break loose on December 31, 2020 when the plug finally gets pulled and people can no longer play their beloved Flash games from 2001.

Why do employees of a company need to have full PCs rather than dumb terminals that can only view intranet pages?

Because intranet pages work great until an employee needs to do anything other than the specific tasks that the programmer has predetermined are that person's job.

What happens when someone else (either inside or outside the company—let's call her "Alice") wants to send you a presentation to review and edit? Every person at every job role at my company has had to do that at some point—managers, engineers, administration, facilities, you name it.

You can receive Alice's presentation file on your internal webmail, but you need some way to edit it. And that means your computer needs to be able to edit PowerPoint files, because that's what everyone uses. And PowerPoint files are ludicrously flexible in what sort of content can be contained in them. So we're back to the network effects problem. If Alice sends me a PowerPoint file and I can't edit on my computer because it uses features that my software doesn't support, that's my problem as far as Alice is concerned.

It's functionally impossible to forsee all the things that someone might need to do for most modern jobs, for the simple reason that if it were possible, that job would probably already be fully automated. And that's not even accounting for the fact that many companies allow their employees to use company computers for all sorts of things that are not strictly part of their job description, such as streaming music.

There's also a more general principle here. As you correctly point out, most PCs are "fundamentally overpowered and overcomplicated for the vast majority of tasks that any person employed by a normal, non-highly specialized IT company, or government entity, would logically need." The problem is that a computer that does all the tasks you need 95% of the time but is useless the remaining 5% of the time when you need to do something weird and specialized—is useless as a computer.

I've heard it said that in software design, 10% of the features cover 90% of what any user needs, but that the remaining 10% of what any user needs is different for each user. If you take the set of features used by each user and intersect all of these sets, the result is not sufficient for any user.

"This interface would have a simple username/password system, with no demands to reset passwords or 'two-factor auth' or any of that nonsense"

This gets its own subheading, because this is a totally separate class of issues from everything else you mention. Go over to Security.SE and read about why these things exist. There are very specific reasons for these security practices, that are totally orthogonal to any discussion about complexity of software.


A one-way function is a function $f$ such that $f(x)$ is easy to compute, but given $y$ in the range of $f$, it is hard to computer a preimage of $f$. Notice that there is no black-box involved. The idea is that $f$ "looks like" a black box that applies $f$ in the sense that you can apply $f$ but cannot do much more, and in particular cannot invert $f$ (or even learn anything about the inverse).

The goal of cryptography is to come up with cryptographically secure algorithms. There is no place for a black box there. That said, when constructing protocols from primitives, we often treat the primitives as black boxes with certain properties. In some cases we can actually show that this point of view isn't general enough - we show that given one primitive as a black box, another primitive cannot be constructed, though perhaps such a construction is possible given access to the code of the first primitive.


Complexity

Your problem is NP-hard.  Therefore, you should not expect any efficient algorithm that will always find the optimal solution.

In particular, your problem is a generalization of the knapsack problem.  Suppose we insist that $f_i(5)=f_i(6)=\cdots=f_i(4999)=0$ for all $i$ (but $f_i(5000)$ can be any positive integer), and the same for the $g_i$.  Then the problem becomes exactly the knapsack problem.  In particular, the knapsack problem is a special case of your problem, which means your problem is at least as hard as the knapsack problem, as any algorithm for your problem could also be used to solve the knapsack problem.  Moreover, the knapsack problem is NP-hard, so your problem is too.

Therefore, you're going to have to make some compromises.  You could look for heuristics that produce the optimal solution and sometimes run fast, but in the worst case might take exponential time.  Or, you could look for heuristics that produce an approximate solution (not optimal, but hopefully close to it).  I'll outline several approaches.

Exact solutions

Suppose you want the exact optimum solution.  Then I know of two reasonable approaches, depending on how large $B$ is.

If $B$ is small, you can adapt the standard dynamic programming algorithm for the knapsack problem to this situation.  The running time will be roughly proportional to $B$, so if $B$ is not too large, this is reasonable, but if $B$ is a 100-bit integer, this is completely infeasible.

Alternatively, you can use integer linear programming.  Introduce zero-or-one variables $v_{i,k}$, with the intended meaning that $v_{i,k}=1$ means that you've set $x_i$ to $k$.  Add constraints to ensure that $x_i$ is set to  a single value ($v_{i,5} + \dots + v_{i,5000}=1$) and that $g_1(x_1)+\dots+g_n(x_n)\le B$ (namely, $\sum_{i,k} v_{i,k} g_i(k) \le B$), and then maximize the objective function $\sum_{i,k} v_{i,k} f_i(k)$.  Feed this to an off-the-shelf ILP solver, and it might find a solution for you, if you are lucky and the size of the problem is not too large.

Approximate solutions

If you're willing to accept an approximate solution that isn't necessarily optimal but should be close to optimal, there are several possible approaches.

One approach is to create the ILP problem above, run the ILP solver for a limited amount of time, then stop the solver and ask it to give you the best solution it has found so far.  Many ILP solvers have the ability to do that.

Another approach is to round to a limited precision.  Pick a constant $c>1$, and replace each $g_i(x)$ with $\lfloor g_i(x)/c \rfloor$ and replace $B$ with $\lfloor B/c \rfloor$.  In other words, divide all the $g$'s and $B$ by $c$, and then round to an integer.  Now solve the resulting problem.  This is an instance of your problem, but with smaller numbers and a smaller $B$, so you can now try to find an exact solution to this smaller problem -- for instance, using dynamic programming.  The optimal solution to this smaller problem will correspond to a close-to-optimal solution to the original problem.  You can tune the value of $c$: the larger $c$ is, the more efficient this will be, but the worse the quality of the solution.

There may be other methods.  You could study the literature on the knapsack problem to see what techniques have been considered there and see  how to adapt them to your situation.  But the above is probably a pretty good starting point.


Is the Syntax of C Language completely defined by CFGs?

The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase to phase. For example, even though the grammar of C doesn't care about names of variables, this information is passed, and that's how the attributed grammar can verify the typing rules. So there are additional mechanisms working on top of the grammar.

For an even simpler example, take the one given by Aho and Ullman. At the parsing phase, all variable names look "the same", yet you cannot use a variable unless it had been declared. This information is hidden from the context-free parser, but is retained as an attribute for the lexical phase, and is checked during parsing. The context-free grammar of C represents only some aspects of what legal C code is, which are useful for implementing a fast parser. On top of that parser, the other rules are checked, semantics are given to the C code, and machine code is generated.


is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$

This is a classical example of a context-free language whose complement is not context-free. It is context-free since every word in $w$ has the form
$$ \Sigma^i a \Sigma^j \Sigma^i b \Sigma^j = \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j $$
or the similar form with the locations of $a$ and $b$ switched.


Automata for languages derived from an automaton by number of state visits

Starting with an automaton for $L$ with state set $Q$, starting state $s_0$, transition function $\delta$, and accepting states $F$, here is how to construct automata $M_1,M_0$ for $L_1$ and $L_0$. The state set of both is $Q \times \{0,1\}$. The starting state is $(s_0,0)$. The transition function is given by
$$
\delta'((s,x),a) = \begin{cases} (\delta(s,a),x) & \text{ if } \delta(s,a) \neq q, \\ (\delta(s,a),1-x) & \text{ if } \delta(s,a) = q. \end{cases}
$$
The accepting states of $M_1$ are $F \times \{1\}$, and of $M_0$ are $F \times \{0\}$.

In words, in addition to remember the original state, the new automaton also remembers the parity of the number of times that $q$ has been visited. Acceptance is determined accordingly.


Wrapping the complexities of alternative algorithms: What is the proper "term" for it?

Hybrid algorithms.

In sorting algorithms it's rather common, Start with quicksort and if the size of the array is small enough switch to insertion sort (much faster for small $n$). Additionally when the recursion depth becomes too large (threatens to become $O(n^2)$) fall back to heapsort (guaranteed $O(n\log n)$).


Calculating complexity for recursive algorithm with codependent relations

Let us note that $F(n) = G(n+1) - G(n-1)$. Therefore
$$
G(n+1)-G(n-1) = G(n-1) - G(n-3) + 2G(n-1),
$$
implying that
$$
G(n+1) = 4G(n-1) - G(n-3).
$$

Similarly, $G(n) = (F(n+1)-F(n-1))/2$, and so
$$
(F(n+1)-F(n-1))/2 = (F(n-1)-F(n-3))/2 + F(n-1),
$$
implying that
$$
F(n+1) = 4F(n-1) - F(n-3).
$$
These are exactly the same recurrences, though with different initial values.

A simple induction shows that $F(n) = 0$ for odd $n$ while $G(n) = 0$ for even $n$ (this also follows from their semantic meaning).

Using the recurrence, we easily get that for even $n$,
$$
F(n) = (1/2 + 1/2\sqrt{3})(2 + \sqrt{3})^{n/2} + (1/2 - 1/2\sqrt{3})(2 - \sqrt{3})^{n/2}.
$$
Let us comment that this sequence is A001835.

Similarly, for odd $n$,
$$
G(n) = (1/2 + 1/\sqrt{3})(2 + \sqrt{3})^{(n-1)/2} + (1/2 - 1/\sqrt{3})(2 - \sqrt{3})^{(n-1)/2}.
$$
This sequence is A001353.

Alternatively, we can notice that
$$
\begin{pmatrix}
F(n) \\
G(n+1)
\end{pmatrix} =
\begin{pmatrix}
1 & 2 \\
1 & 3
\end{pmatrix}
\begin{pmatrix}
F(n-2) \\
G(n-1)
\end{pmatrix}
$$
It follows that
$$
\begin{pmatrix}
F(2m) \\
G(2m+1)
\end{pmatrix} =
\begin{pmatrix}
1 & 2 \\
1 & 3
\end{pmatrix}^m
\begin{pmatrix}
1 \\
1
\end{pmatrix}
$$
The eigenvalues of the matrix are $2 \pm \sqrt{3}$, and so we are led to formulas as stated above.


Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language and no others.

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.
All finite languages are decidable which means that there is a corresponding Turing machine which is a decider


Proving that a spanning tree of graph is not a minimum

If you remove that edge you mentioned with weight $\geq w_i$ from $T$, then the new $T$ has two components (because it's a tree). But one of the edges on the cheap path connecting $u$ and $v$ in $T'$ would reconnect these two components in $T$. And the substitution saved you a bit in terms of weight.


Modification of dynamic programming for a knapsack problem

Apply the golden rule of DP (that is how I name it), namely, adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. This rule is simple and powerful, yet it can be overlooked by DP beginners and sometimes experienced guys.

In this particular question, instead of $V(i,w)$, define $V(i,w,c)$, where $V(i,w,0)$ means no item 1 and no item 2,  $V(i,w,1)$ means one item, and  $V(i,w,2)$ means one item 2. Rewrite the recurrence relation accordingly. Compute the values either recursively or iteratively with memoization. Select the desired result among possible candidates.

This answer can be seen as a formalization of @fade2black's answer, although I had/have been calling/using the golden rules too many times in my DP adventure.


When do the gradients exist in a Reinforcement Learning setting?

The gradient doesn't exist / isn't well-defined for non-differentiable functions.  What they mean by that statement is that there is an analogous version of gradients that can be used, instead of the gradient.

Discrete functions

In the discrete case, finite differences are the discrete version of derivatives.  The derivative of a single-variable continuous function $f:\mathbb{R} \to \mathbb{R}$ is $df/dx$; the partial difference (a discrete derivative) of a single-variable discrete function $g:\mathbb{Z} \to \mathbb{Z}$ is $\Delta f : \mathbb{Z} \to \mathbb{Z}$ given by

$$\Delta f(x) = f(x+1)-f(x).$$

There's a similar thing that's analogous to a gradient.  If we have a function $f(x,y)$ of two variables, the gradient consists of partial derivatives $\partial f / \partial x$ and $\partial f / \partial y$.  In the discrete case $g(x,y)$, we have partial differences $\Delta_x f$ and $\Delta_y f$, where

$$\Delta_x f(x,y) = f(x+1,y) - f(x)$$

and similarly for $\Delta_y f$.

Continuous functions

If you have a continuous function that is not differentiable at some points (so the gradient does not exist), sometimes you can use the subgradient in lieu of the gradient.


Why does existence of predecessor imply adequacy of a numeral system?

Recall that the set of partial recursive functions $\mathcal{R}$ is defined inductively by the following rules:

(zero) $\dfrac{}{\zeta : n \mapsto 0 \in \mathcal{R}}$
(successor) $\dfrac{}{\sigma : n \mapsto n + 1 \in \mathcal{R}}$
(projection) $\dfrac{}{\Pi_m^i : (n_1, \cdots n_m) \mapsto n_i \in \mathcal{R}}$
(composition) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi_i : \mathbb{N}^k \to \mathbb{N} \in \mathcal{R} }{\phi : (n_1, \cdots n_k) \mapsto \chi(\psi_1(n_1, \cdots, n_k), \cdots \psi_m(n_1, \cdots, n_k)) \in \mathcal{R}}$
(primitive recursion) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi : \mathbb{N}^{n+2} \to \mathbb{N} \in \mathcal{R} }{\phi : (k,n_1, \cdots n_m) \mapsto \begin{cases}
      \chi(n_1, \cdots n_m) & \text{ if } k=0 \\
       \psi(\phi(k-1, n_1, \cdots, n_m),k-1, n_1 \cdots n_m ) & \text{ if } k > 0\\
   \end{cases}  \in \mathcal{R}}$
(minimalization) $\dfrac{\chi : \mathbb{N}^{m+1} \to \mathbb{N} \in \mathcal{R} }{\phi : (n_1, \cdots n_m) \mapsto k \text{, the least integer with } \chi(k,n_1, \cdots n_m) =0
   \in \mathcal{R}}$

So we will prove the result by structural induction on $\mathcal{R}$.

Initial functions.

It is clear that $\zeta$ is defined by $\lambda x. d_0$, $\sigma$ by $S$, and $\Pi_m^i$ by $\lambda x_1 \cdots x_m . x_i$.

Composition

Suppose $\chi$ is defined by $f$ and $\psi_i$ by $g_i$.

Let $h$ be the term $\lambda x_1 \cdots x_k.f (g_1x_1 \cdots x_k) \cdots (g_mx_1 \cdots x_k)$. Then $h$ defines the function $\phi : (n_1, \cdots n_k) \mapsto \chi(\psi_1(\vec{n}), \cdots \psi_m(\vec{n}))$

Primitive recursion.

Suppose $\chi$ is defined by $f$ and $\psi$ by $g$.

Let's define the combinator $\textbf{r} = \lambda nfg.isZ\:n\:f\:(g \:(P\:n))$, with the property that:

$$
\textbf{r} \: d_n \:f \: g = \begin{cases} f & \text{ if } n = 0 \\
g \: (d_{n-1}) & \text{ if } n > 0
\end{cases}
$$

Now let $h$ be the term $\textbf{y} \: (\lambda s y x_1 \cdots x_m . \textbf{r} \: y(f x_1\cdots x_m)(\lambda z.g (s z x_1 \cdots x_m)z x_1 \cdots x_m )$. Then $h$ defines $\phi: (k,n_1, \cdots n_m) \mapsto \begin{cases}
      \chi(n_1, \cdots n_m) & \text{ if } k=0 \\
       \psi(\phi(k-1, n_1, \cdots, n_m),k-1, n_1 \cdots n_m ) & \text{ if } k > 0\\
   \end{cases}$.

Minimalization

Suppose $\chi$ is defined by $f.

Let $g$ be the term $\textbf{y} (\lambda syx_1 \cdots x_m.isZ \: (f\: y\: x_1\cdots x_m) \: y\:  (s\: (S \: y)\:  x_1 \cdots x_m))$. Then take $h$ to be the term $g \: d_0$, and $h$ defines the function $\phi : (n_1, \cdots n_m) \mapsto k \text{, the least integer with } \chi(k,n_1, \cdots n_m) =0$.

By induction, every function in $\mathcal{R}$ is definable.

(I leave the proving the fact that the terms $h$ define the stated functions as an exercise!)


You said:

If I understand correctly, $x$ and $z$ are basically anything on the 2
sides of the string $y^p$ that we're pumping and thus can be anything
in .

This is not true. The pumping lemma suggests that for every long enough word $w$  such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma hold. You only know that such $x, y$ and $z$ exist, you do not know whether this is true for all $x, y, $ and $z$ that partition $w$. Thus, you cannot force $x$ or $z$ to be empty. In fact, this is far from being true. For example, consider the language of the regex $a b^*$. Here $y$ cannot contain the letter $a$, thus you cannot force $x$ to be the empty word.
You also said:

If $x$ is necessary, why is there no $|yz|\leq p$?

This condition is too strong as, along with the condition on $|xy|$, it suggests that every long enough word $w$ in the language, has to be of length at most $2p$, which is not correct.
Also, once you have the condition $|xy|\leq p$, there is no need to have a condition on $|yz|$. The pumping lemma conditions come up naturally from how a run of length at least $|Q|+1$ looks. In such long runs, two states have to repeat in the first $|Q|+1$ states of the run, and thus the condition on $|xy|$ arises. You can think about considering the last $|Q|+1$ states in a long run, and that might give you another variant of the pumping lemma (where $x$ and $z$ replace rules) but I don't see how this may be more useful or more appealing than the standard pumping lemma.


Is "backward substitution" and "backtracking" the same thing?

Backward substitution is a specific method to solve a particular problem: a linear system of equations;
Backtracking is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial solution to a complete solution.

This should answer your "can the terms be used interchangeably?" questions: no, they can't.
Imagine you are solving a crosswords puzzle. One algorithm would be: for each definition, find the list of possible words; then try every combination of those words and check if that combination solves the puzzle. This is a bruteforce approach and pretty inefficient. A much better approach is to use backtracking: for each definition, find the list of possible words; choose a word for the first definition; choose a word for the second definition; check immediately for any inconsistency between the two chosen words. If they are inconsistent, "backtrack" by choosing a different word for the second definition. If you run out of words for the second definition, "backtrack" even further by choosing a different word for the first definition. Only if they are consistent, move on to the third definition. This is a backtracking algorithm. Backtracking algorithms are often very straightforward to implement using recursion.
Backward substitution is a method to solve a system of linear equations. A system of linear equations is something that looks like:
a x + b y = c
d x + e y = f

As you can see it is a very specific problem. There is no notion of recursion here. Linear equations are often written in matrix form: A X = B; in my example, A = ((a b)(d e)), X = (x y) and B = (c f).
The article you linked mentioned "recurrence" because they had a problem with cascading linear equations; the linear equations are called a "recurrence relation" because they define a sequence, where X1 = A X0, X2 = A X1, X3 = A X2, etc.


Trilinear interpolation for distorted cubes?

Imagine a cube with each corner a different RGB color value - as you know you could interpolate the colors inside the cube using trilinear interpolation.

You can reuse this same logic for coordinates as well -- set the RGB values of the corners to be the XYZ coords of your distorted cube's corners.

Now the RGB "color" you sample in this cube is the distorted coordinate -- eg, it is the coordinate of your sampling point after that point has been "remapped" to the now-distorted cube, using the normal trilinear algorithm.

Hope this helps.


Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

Hint: You need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things $x$, $y$ and $z$ can be given that $xyz=(01)^p2^p$. Then you pump each one and see whether you get a contradiction, which will be a word not in your language. Each case needs to lead to a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

Of course, you need to work through the details and consider all the possible splittings.


Using function composition to turn a function into point free one

Going from the point-free version to the lambda version is mechanical. Remember that composition is defined by (f . g) = (.) f g = \x. f (g x), so (f . g) x = f (g x). Remember also that (f . g) is syntactic sugar for (.) f g and f x y is shorthand for (f x) y. It's easier to follow what's going on if you apply one argument at a time.

p = ((.) f) . g
p x = (((.) f) . g) x = ((.) f) (g x) = (.) f (g x)
p x y = (p x) y = ((.) f (g x)) y = (.) f (g x) y = (f . g x) y = f (g x y)
p x y z = (p x y) z = (f (g x y)) z = f (g x y) z

To go in the other direction, arrange the function calls so that there is a single occurrence of the function's parameter in the function body, and arrange it to be at the end of the call. In addition to . for composition, this may require the use of auxiliary functions such as flip to change the order of arguments.

p x y z = f (g x y) z
p x y = f (g x y)
p x = \y. f (g x y) = \y. f ((g x) y) = \y. (f . g x) y = (f . g x) = ((.) f) (g x)
p = \x. ((.) f) (g x) = \x. ((.) f . g) x = ((.) f . g)


What is the difference in 'logical array blocked' and array list B, and what do they represent?

In the pseudocode, T array means an array where each element has type T.  Logical is the type of a boolean (i.e., it can hold the value true or false).  Integer list is the type of a list of integers.

Thus, in the pseudocode, logical array blocked(n) is the declaration of an array called blocked containing n elements, where each element is a boolean.  integer list array B(n) is the declaration of an array called B containing n elements, where each element is a list of integers.

$V_K$ isn't clearly defined, but from context, I'd guess it is the set of vertices in $A_K$.


This should be NP-hard, here's a way you could try to do a reduction:

Take any graph $G$ embedded in the $\mathbb{R}^2$ plane. Let $c_{min} = \min_{e \in E}\{c(e)\}$  be the minimum edge weight in the graph ($c$ is the weight function of the edges of $G$, i.e. the euclidean distance). To build $G'$, split every vertex $v = (x,y)$ into $v_1 = v$ and $v_2 = (x+\epsilon,y)$ where $\epsilon = \frac{c_{min}}{2^n}$, connect $v_1$ and $v_2$ with an edge weighted by their euclidean distance. Obviously, no vertex in $G'$ is incident with more than two edges, and there are no vertices that are incident with no edges.

What you now would have to prove is something like "there's a TSP route of weight $\le w$ in $G$ iff there's a TSP route of weight $\le w + n \cdot \epsilon$ in $G'$. I don't know how to prove that, but some geometry and use of the triangle inequality might help. I expect the choice of $\epsilon$ as vanishingly small will be enough to give the reduction.

EDIT: The reduction will remain valid after your edit.


Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights.

A simple example which requires exponential weights is the function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.


Which of the following sequences could not be the sequences of nodes examined in a binary search tree?

Actually the test is quite easy. If you consider the subsequence of numbers greater than the final number $363$, this sequence is supposed to decrease.

Thus, in the case of $e: 925, 202, 911, 240, 912, 245, 363$, the subsequence is $925, 911, 912, 363$ and we see the problem.

Why is that so? If we see a number $x$ larger than the target $363$, we are supposed to move to the left subtree of $x$ where all numbers will be smaller than $x$. Thus also all numbers we will see from there will be smaller. As a consequence the numbers larger than $363$ will decrease.

Similarly, the numbers smaller than $363$ will increase. That is why $d$ fails: $278,347,299,358,363$.


Transforming an arbitrary cover into a vertex cover

If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction).

On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide a counter-example:

The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph


Finidng edges of convexhull from rectangles

If you have $n$ rectangles, take the convex hull of the $4n$ points given by the corners of those rectangles.  This gives you exactly what you want, and you can use any standard algorithm for computing the convex hull.  There is no need to explicitly deselect individual corners -- let the algorithm for computing a convex hull take care of that.


Emulation, interpreters and parallel execution

Your understanding of the complexity of a switch or case statement is not correct.  In most languages these statements make a decision based on the value of a single integer variable.  If those integers are densely packed together (as they typically are when an interpreter is decoding an instruction opcode) then the compiler turns this into an $O(1)$ lookup table.

The table is simply an array of addresses.  The control variable for the switch statement is used to determine the offset into the array.  Then the code simply jumps to the address given at that offset in the array.

In the case where the integers are not densely packed together then the compiler builds a logarithmic-height tree of branches each of which divides the remaining range in half, like in the children's "number guessing game."  So, for example, if you have a switch statement over 1000 different cases spread over the numbers 0-1000000000, then you'll be able to determine whether any given input is one of the cases, and which case, in less than 10 comparisons.  (Because $\log_2 1000 < 10$.)


Should O(1) necessarily stand for a non-zero constant?

$O(1)$ does not represent time. It represents a class of functions, which could be used to measure time, space or literally anything else.

$f(x)\in O(1)$ if, and only if, there is a constant $c$ such that $f(x)<c$ for all large enough $x$. There's no requirement that $f$ must be eventually non-zero. $f(x)\in o(1)$ if, and only if, $\lim_{x\to\infty} f(x) = 0$ so, in particular, for all large enough $x$, $f(x)<1$. Therefore, $f(x)\in O(1)$.


Turing Recursive Definition vs General Perception

A function is recursive if it can be defined using certain constructs, one of which is recursive calls.

A function is computable if it can be implemented by a Turing machine.

Theorem: A function is computable if, and only if, it is recursive.

Because of the above theorem people are sometimes a bit imprecise about using the correct words and definitions, and they conflate recursive and computable functions. They should not. It confuses students.


Do all Regular Expressions describe Regular Languages?

It's a standard part of any automata theory course that regular expressions, deterministic finite automata and nondeterministic automata all define the same class of languages. Any individual exposition will take one of those three things as defining the class of regular languages.

So, yes, all regular expressions define regular languages, and every regular language is the set of strings that match some regular expression.

At least, the above is true for regular expressions as used in computer science. Perhaps the confusion in the question arises from the fact that many computer systems such as text editors, programming languages/libraries and command shells have pattern-matching features that they call "regular expressions" but which are more powerful than CS regular expressions. @reinierpost provides the example that egrep '^(.*)\1 matches the non-regular language $\{ww\mid w\in\Sigma^*\}$.


Are LR(k) languages and DCFLs equivalent?

According to Wikipedia:

For every fixed $k \geq 1$: A language has an LR($k$) grammar iff it is DCFL.
A language has an LR(0) grammar iff it is DCFL and has the prefix property (no word is a prefix of another word).

The first property is proved in Knuth's original paper, in Section V on page 628.


Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$

Here is a Turing machine on the online simulator I found here.

name: Recongnize 0^2n 1^n
init: s0
accept: acc

s0, 0
s1, _, >

s1, 0
s2, _, >

s2, 0
s2, 0, >

s2, 1
s2, 1, >

s2, _
s3, _, <

s3, 1
s4, _, <

s4, 0
s4, 0, <

s4, 1
s4, 1, <

s4, _
s0, _, >

s0, _
acc, _, -

The idea is to delete the two zeroes on the left, got to the end on the right, delete one, go to the way to the left, repeat. Accept only when after deleting 1 on the right the tape is empty.


Minimizing the maximum Manhattan distance

Manhattan-distance balls are square and aligned with the diagonals, which makes this problem much simpler than the Euclidean equivalent.

Find an input point P with maximum x+y, an input point Q with minimum x+y, an input point R with maximum x-y, and an input point S with minimum x-y. The minimum maximum distance d is the maximum of ceiling(((P.x+P.y) - (Q.x+Q.y))/2) and ceiling(((R.x-R.y) - (S.x-S.y))/2) or sometimes that quantity plus one. Accordingly, for each center C, we can compute the bounds on C.x+C.y and C.x-C.y so that (P.x+P.y) - (C.x+C.y) <= d and similarly for Q, R, S. Then there's some simple formula to count the points in that rotated rectangle. If the count is zero, increase d and try again.

The overall running time is O(N).


How to recursively infer a word/string from a context-free grammar?

You are correct to realize that this is just like deriving words, but backwards. The authors admit this when they say "However, it is often more natural to think of grammars as used in derivations, . . ."

Labeling the productions as $A\rightarrow aAd$ (1), $A\rightarrow B$ (2), $B\rightarrow bBd$ (3), $B\rightarrow C$ (4)m $C\rightarrow cC$ (5), $C\rightarrow cD$ (6), $D\rightarrow Dd$ (6), and $D\rightarrow\epsilon$ (8) we can produce this derivation
$$
A\stackrel{(1)}{\Longrightarrow}aAd\stackrel{(2)}{\Longrightarrow}aBd\stackrel{(3)}{\Longrightarrow}abBdd\stackrel{(4)}{\Longrightarrow}abCdd\stackrel{(6)}{\Longrightarrow}abcDdd\stackrel{(7)}{\Longrightarrow}abcDddd\stackrel{(8)}{\Longrightarrow}abcddd
$$
and reading this from right to left gives exactly the table you had.

Frankly, it's not a topic I cover when I'm teaching this material.


Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

If there is a finite number of exceptions to the Goldbach conjecture then it is still solvable in linear time.
Note that there is a non-zero probability that the Goldbach conjecture is false. Heuristically, the probability for an infinite number of exceptions is zero.


The formula states that for all $n$, if $a$ holds at time $n+1$ then $b$ holds at time $n$. If $a$ never holds then the formula is trivially true.


No.  Every function can be implemented with a polynomial-depth circuit, but not all function families can be implemented with a polynomial-time algorithm.

In particular, if we're allowed unbounded fan-in/fan-out, you can implement every function in depth 2 using a CNF or DNF formula for the function (but the size of the circuit is exponential).  If we're only allowed constant fan-in/fan-out, you can simulate that with linear depth (use a $n$-layer tree to make exponentially many copies of each input; then 1 layer to evaluate the CNF clauses; then a $n$-layer AND tree).