How do you prove these string/number radix encoding/decoding algorithms work?

First, you need to figure out what it is you want to prove. Here, I'd say we want to prove that
toString(parseInt(x, code),code) = x
and
parseInt(toString(x, code),code) = x
It's pretty obvious that trying to prove this is going to fail if:

we overflow the result in parseInt, because then parseInt isn't surjective
the input in parseInt contains characters that aren't in the code

So, our proof has to include the assumption that both are not the case.
The first proof is probably easier than the second. We can do induction on the length of `value':
toString(parseInt(x, code),code) = x
Given an arbitrary code which contains all characters in x
If x.length == 0:

x == ''
parseInt(x, code) returns 0
toString(0, code) returns ''  <- actually it returns 'a' so the proof breaks here, but you can do the same if you assume length 1

If x.length > 1

our induction hypothesis: for all prefixes y of x toString(parseInt(y, code),code) = y
parseInt(x, code) = parseInt(x[:-1], code) * code.length + code.indexOf(x[-1])   (I am using python syntax here to say everything but the last element, and the last element. This in and of itself would have to be proved I guess but it would be very easy if the algorithm was written recursively instead of iteratively)
toString(a * code.length + b, code) = code[b] + toString(a, code)  (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
that means toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = code[code.indexOf(x[-1])] + toString(parseInt(x[:-1], code), code) = (using induction hypothesis) x[-1] + x[:-1] which breaks our proof because toString has a bug and inverts the string, as far as I can tell.

Assuming the line result = code[digit] + result actually read result = result + code[digit] like I think it should:

toString(a * code.length + b, code) = toString(a, code) + code[b]  (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
that means toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = toString(parseInt(x[:-1], code), code) + code[code.indexOf(x[-1])] = (using induction hypothesis) x[:-1] + x[-1] = x

QED.
The other direction is similar, you can again use induction as long as you take care that your induction hypothesis is "for all y < x: parseInt(toString(y, code),code) = y".


A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable", i.e., all functions computable by TMs. This is just a hypothesis, and it is up to you to believe or not.

When we describe a procedure in order to show that some function is computable (or problem is solvable) we usually describe it at a high level, to avoid long and tedious rigorous formal details. So, you are right that "it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis". In other words, first we informally describe a procedure using English, and then since we believe in correctness of the the Church-Turing-Thesis we conclude that the function is computable.

Another example is computing $\pi(n)-$ the $n$th digit of the decimal expansion of $\pi$. Intuitively, we can draw a circle, measure its circumference and radius, and divide the circumference by two times the radius. But this method is not suitable to implement on a computer. The Turing-Church thesis says this function is indeed computable on a Turing machine. For example, $\pi(n)$ might be computed using Taylor series.

As for the wrong usage of the thesis, usually the error may lay in a wrong assumption. For example, the following wrong procedure may seem to decide the Halting problem:

Let L be the Halting Problem language
IsHalt(W,w)
  Recursively enumerate elements of L and complement of L
  and process one element from each set at a time
  If <W,w> is in one of them then depending in what set <W,w> is
  return true or false

Since we loop on both $L$ and $\overline{L}$, and we enumerate each element of these sets, the procedure eventually must halt with true or false. But the wrong part is that we assumed the $\overline{L}$ is r.e.


What is the difference between "use case" and "function"?

If by "function" you mean functionality then a single use case may require more than one function to achieve and a single function may serve multiple use cases.

Here's a concrete example:

Use case:

Allow user to withdraw money

Functions:

Check user balance
Prompt user to enter amount and check against balance
Check amount against money in machine
Output money

Depending on how you go about documenting your design you can argue that the 4 functions above can be written as a single function. Though doing this misses the important realization that Check user balance is a function that can be reused in another use case (Allow user to see his balance), even if we reduce them to one function the use case and function would be different ways to say the same thing:

Use case:

Allow user to withdraw money

Function:

Withdraw money

So, at its core level a functionality is an implementation of processes for a use case.

Why do we need two different names? Sometimes it makes it clearer to talk about a requirement and the solution to it. Similar to how in programming we have classes and objects.


$\mathrm{\oplus P^{BPP}\subseteq BPP^{\oplus P}}$

You get a smaller one, in words $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P}}$. Indeed, the stronger claim that $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P[1]}}$ also holds.

Consider a language $L\in \mathrm{{\oplus P}^{BPP}}$, by definition, there exists an oracular non-deterministic machine $N$ and a $\mathrm{BPP}$ machine $M$ such that: on a given input string $x\in \Sigma^*$, we have that $x\in L$ if and only if $N^M(x)$ has an odd number of accepting paths.

Now, we may assume that by repetition and taking majority, the probability of $M$ to produce wrong answer is exponentially small.

The following language $\mathcal{O}$ is in $\oplus P$: on an input string $x\in\Sigma^*$ and a polynomially long random bit string $r$ (i.e. input data is $(x,r)$), simulate $N^M(x)$ where the random coin tosses using inside the oracle calls to $M$ are taken from $r$ one by one from left to right; accept only when the number of accepting paths is odd.

So, on a given input string $x\in\Sigma^*$, we guess a polynomially long random bit string $r$, call the oracle $L\in\oplus\mathrm{P}$ on input $(x, r)$and return the same answer.

Clearly, the probability that the random bit string $r$ makes $M$ produce wrong answer to any oracle call is extremely small. So, w.h.p the answer returned by the only one call to $\mathcal{O}$ is identical to the answer of $N^M(x)$.

Thus, $L\in\mathrm{BPP^{\oplus P[1]}}$. The claim that we obtain a smaller class holds.


Complexity of pattern matching for modus ponens logical conclusions

This boils down to the question of whether there exists a polynomial-time algorithm for your matching operation.
If there exists such an algorithm, call it $A$, then the answer to your question is yes: given an augmented Turing machine that uses these operations, you can convert it to an ordinary Turing machine by simulating those operations using $A$.  This blows up the running time by at most a polynomial.  (Invoking a polynomial-time subroutine at most polynomially many times leaves with a running time that remains polynomial.)
If there is no such algorithm, then the answer to your question is no: the matching problem can be solved in polynomial time (indeed, constant time) on an augmented Turing machine, but cannot be solved in polynomial time on an ordinary Turing machine.
I'm not clear on the definition of your matching operation, and I'm not an expert in computational logic, so I don't know what is the computational complexity of the matching operation you have in mind.


Recursive complexity with change of variable


Clarification about conclusion of $Θ(nlogn)$?

In the first part where the summation $\sum_{i=1}^{\log n}i2^i$, you see that whole summation can be written as that chain of summations (if you sum them all up you'll end up getting the first form on the top). Then you use the summation of power two's formula, i.e. $\sum_{i=0}^{n}2^i= 2^{n+1}-1$.

In the first line $=2+2^2+...+2^{log n}$ the formula is missing a -1 so the result will be $2^{\log n +1}-2$, the second one is missing a 2 so it will be $2^{\log n+1}-2^2$ and so on.

You can write $2^{\log n +1}$ as $2*2^{\log n}$ which is equal to $2*n$. I think what confuses you is that you think they wrote $2^{\log (n+1)}$ where as it is $2^{\log n +1}$.

As for why the $2n*\log n - (2^{\log n +1} -2) \in \Theta(nlogn)$, since $2n\log n \in \Theta(nlogn)$ and $2^{\log n + 1} = 2*n$ thus it is $\Theta(n)$ and from the property of asyptotic notation we can conclude $\Theta(nlogn)-\Theta(n) \in \Theta(nlogn)$.


Data structures for general (non-tetrahedral) cell complexes

There is an extension of half-edge in any dimension, called darts in combinatorial maps.
There are two packages in CGAL allowing to use these combinatorial maps in any dimension (see here for combinatorialMaps and here for LinearCellComplex).

You can use this data structure to represent any Quasi manifold orientable subdivided 3D object. Quoting from CGAL webpage(section 2.4 Combinatorial Map Properties):

A quasi-manifold object is defined as:

  A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells.

and orientable as:

  It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object.


Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

If you solve a Problem that is NP-complete the solution to this problem can not be applied instantly to any other Problem that is NP-complete. However, the problem that you solved might be used to find a solution for other problems in NP.
For example:

If you can solve the TSP Problem your an adaption of your solution could also solve the problem of finding a hamiltonian circle in a graph
If you can solve the hamiltonian circle problem an adaption of your solution could also solve the long path problem
...

So your solution can not be directly used to solve other problems.
But if you found a solution for a problem that is NP-complete this implies that there are solutions in P for every problem that was believed to be NP-complete. This is because NP-completeness is defined as follows:

A problem P is NP-complete if it is NP-hard and the problem lies in NP
Beeing NP-hard means that every other problem P' that is NP-complete can be reduced to the problem P (meaning exactly that if you could find a solution for P you could also find oune for P')

The answer to your second question is simply "No".
The only reason for a cancidate to solve another problem that is NP-complete is that he could not find a solution for the given problem but for the other problem. And in addition he knows how to modify the problem he is abel to solve in such a way that he finds a solution for the given problem.


Can Euclidean TSP be exactly solved in time better than (sym)metric TSP?

One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in $O(n^{c \sqrt{n}})$ time, where $c$ is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis [1], Kann's PhD thesis [2], and Hwang et al. [3]. Each algorithm has a running time of $O^*(c^{\sqrt{n} \log n})$. This is much better than $O(n^2 2^n)$. As far as I know, it is still an open question whether the running time can be improved by say getting rid of the logarithmic term.

[1] W.D. Smith, Studies in computational geometry motivated by mesh generation. Ph.D. Thesis, Princeton University, Princeton.

[2] V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Kungliga Tekniska Högskolan, Stockholm, 1992.

[3] R.Z. Hwang, R.C. Chang, R.C.T. Lee, The searching over separators strategy to solve some NP-hard problems in subexponential time,
Algorithmica 9 (1993) 398–423.


Number of states in minimal Non Deterministic Finite Automata

But will not this NFA accept every string over the alphabet set?

It will not accept any strings except the empty one.
Since there are no transitions, the transition function $\delta(q_0,a) = \emptyset$ for all symbols $a$ of the input alphabet $\Sigma$, thus the extended transition function $\hat{\delta}(q_0,s) = \emptyset$ for all non-empty strings over $\Sigma$.

The set of accepting states $\{q_0\}$ and $\hat{\delta}(q_0,s)$ for all non-empty strings $s$ are disjoint, hence the NFA doesn't accept any non-empty strings.

As you already know this NFA accepts the empty string, and we just showed that it accepts only the empty string.

Remark: if it was a deterministic automaton you'd need 2 states to do the same thing. You could "cheat" and not show the 'dead state', but still it would be a 2 state DFA. With NFAs rules are a little bit different, since instead of states you use sets of states and having your NFA in no state at all (the empty set of states) is perfectly normal abstraction.


If a problem is PSPACE-complete what do we know about NL-completeness

A PSPACE-complete problem cannot be in NL, and in particular cannot be NL-complete (this is a consequence of the space hierarchy theorem). However, it is NL-hard. If $A$ can be transformed into a reachability problem, then probably the transformation is not polynomial-time.


Unprovable Post correspondence problem instance

The argument you outline doesn't actually work. In fact, for any specific PCP instance, there is an algorithm which produces the right answer; it is either "output 'yes'" or "output 'no'". It is only when you require the algorithm to work for all the infinitely many instances that undecidability enters the picture (since an algorithm needs to be finite, you cannot just cobble together all the individual solutions).

Now it is true that given any particular PCP instance, you could just enumerate the potential solutions. The problem with this is that while for solvable instances, you will eventually find the solution, for (non-trivial) unsolvable ones, you will never get an answer. That is, what you have here is a semi-decision procedure.


Is there a computer which can simulate all computers?

Your intuition sounds wrong to me.  It's not surprising you couldn't prove it, because it isn't true.  Roughly speaking, it is possible to find a computer that can simulate all other computers.

A universal Turing machine can simulate any other Turing machine, and can be used to simulate any other program in any Turing-complete language.  Thus, there is a reasonable sense in which it can simulate all other computers, if we make precise what we mean by "computers" in a particular way (e.g., if we accept the Church-Turing thesis).

If you want to know whether it is possible to simulate another computer and also do it faster, that's a different matter.  You'd have to formalize what you mean by "faster" to make that question well-defined.

Your question at the end of the post is not well-formed; computability is a property of languages, not of a single value (like $f(f,i_f)$).  Also, you defined $f$ to be a function of two arguments, so $f(i_f)$ doesn't type-check.


Why is the complement of a language that is not regular also not regular?

Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)

So, suppose that $L$ is non-regular.  If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.


Registers of Control Unit and Arithmetic Logic Unit

They are part of the memory interface between the CPU and the memory subsystem.

The MAR (Memory Address Register) is closely associated with the memory address bus, and the MBR (Memory Buffer Register) is closely associated with the memory data bus.

Some CPUs choose to connect their general purpose registers more or less directly to those busses, thus eliminating these specialized registers, but this is not usually the case in accumulator machines that you're describing in your question.

Some CPUs have a secondary ~ALU dedicated to addressing computation (so probably just add and some specific shifts, e.g. by 0, 1, 2, or 4); such a secondary ALU might also work in conjunction with the MAR or in replacement of an MAR.

On some processors, the CU will have to interleave requests for instructions from memory with requests by the program for data from memory. The instruction address (found in the PC) may first go through the MAR during fetch, or the PC value may be sent directly to the address bus during fetch, depending on the CPU design.

If the processor has a separate instruction cache and data cache, then it has two memory subsystem interfaces.  Typically the PC will then serve directly as the MAR for the instruction memory interface rather than creating a second MAR for that.

Note that the MAR, MBR, and the IR are internal registers that are generally not visible to the program or programmer, and so only visible if you're looking inside a particular processor's design.  The same instruction set architecture can be implemented in different ways, and in these alternative implementations, the discussions of the above considerations may vary; this happens in a processor family, like x86.


NP-complete problem with a polynomial number of yes-instances?

A language with only polynomially many yes-instances is called sparse.  Mahaney's theorem states that if any NP-complete language is sparse, then P = NP.  Since most people expect that P $\ne$ NP, it seems unlikely that there exists a NP-complete language with only polynomially many yes-instances.

It's a separate question whether the number of yes-instances is exponential.  (One could imagine that the number of yes-instances might be more than polynomial but less exponential.)  The Berman-Hartmanis conjecture is relevant here; it implies that all NP-complete problems have exponentially many yes-instances.  The conjecture remains an open problem.


What do we do instead of DFS on directed graphs?

DFS suffers from the same problem in undirected graphs: if your graph is not connected, then starting DFS with an initial vertex $v$ will only explore the connected component of $v$. In a similar fashion, if the graph is directed, then DFS will only explore the vertices reachable from $v$.

The solution is the same in both cases: loop over all vertices, and start DFS with each of the vertices functioning as the initial vertex. If you skip vertices which you have already discovered, then the resulting algorithm will still run in linear time.


Solving a variant of interval scheduling problem

It seems that you are looking for the minimum maximal independent set of an interval graph. A minimum maximal independent set in a graph is the same as a minimum weight independent dominating set, with all vertices weights equal to 1. Since interval graphs are a special case of chordal graphs, Martin Farber's paper Independent domination in chordal graphs (Operational Research Letters, 1(4):134–138, 1982; ACM Digital Library) contains the algorithm you are looking for.


Looking for a book that derives and constructs a model checking application

John Harrison's book is an exception in going all the way from theory to practice and making all the source code available. I think you will find it difficult to find an equivalent book for model checking, but there are a few that achieve a close approximation.

Principles of Model Checking by Baier and Katoen contains a lot of examples and pretty detailed algorithmic description.
The SPIN Model Checker by Gerard Holzmann is a very different treatment from the author of one of the earliest model checkers. He has maintained the tool for about thirty years and has a "programmatic" approach.

A better bet may be to follow the course notes and lab assignments of some courses available online. At least you will find the theory, practice and examples, even though they are not organised in a book.

Edmund Clarke's course in CMU has a reading list which includes tutorials for a few different model checkers.
Joost-Pieter Katoen's software verification course and the followup on Practical Model Checking and Advanced Model Checking cover a lot of ground.

Finally, this is not entirely what you asked for, but since you have been studying logic and now model checking, you will invariably run into references to abstract interpretation, which is the basis of static program analysis and is intimately connected to model checking (though this connection is not always explicit in the model checking literature).

Patrick Cousot's MIT Course is a tour de force covering everything from lattice theoretic foundations to the complete implementation of a static analyzer for a simple language. His course material includes all the code and exercises.


RP (randomized polynomial time) is a complexity class for algorithms that always run in polynomial time, while possibly make truly random choices, and always rejecting correctly while usually accepting correctly (i.e., with probability greater than $\frac{1}{2}$).

Expected polynomial time usually means that the complexity is polynomial time only in expectation, and the answer is always correct.

Suppose you have the following (silly) algorithm to check if the first element, in an array with length n, is the maximum:

Scan the array, check if the first element is maximum.
With probability $\left(\frac{1}{2}\right)^n$, uselessly scan the array an additional $\frac{2^n}{n}$ times, and recheck the result of step 1.
Return the answer from 1 in any case.

This algorithm has expected polynomial time. The cost of the first step is $\Theta(n)$. The expected cost of the second step is $\Theta\left( \left(\frac{1}{2}\right)^n n \frac{2^n}{n}\right) = O(1)$. The cost of the third step is constant. Conversely, it is not in RP because the second step can run in time $\Theta\left( 2^n \right)$ for an unfortunate randomized outcome.


Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

The only question is in the tile so I'm going to answer that.

A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$.
As a counter example look at the following graph:

If vertex $a$ is visited before vertex $b$ you will not necessarily discover the shortest path from $s$ to $b$.

Also, the same example shows that the order in which vertices are considered by a preorder DFS traversal is not necessarily a topological sort.
Indeed, if $b$ is visited before $a$ the order would be: $s, b, a$ but there is an edge from $a$ to $b$.


Articulation vertex in complementary graph

Hint: An equivalent characteristic of "an articulation vertex $v$" is as follows:

  $v$ is an articulation vertex in $G$ $\iff$ there exists two vertices $x,y$ such that $v$ is on all the paths between $x,y$.

So it suffices to check all the pairs $x,y$ in $G'$ to see whether there exists some path between them which does not pass $v$.

More hints:

Consider two cases:

In $G$, $v$ is on all the paths of $x,y$. Then is $e = (x,y) \in G'$?
In $G$, $v$ is not on all the paths of $x,y$. Where are $x$ and $y$ if $v$ is removed in $G$? Then,

2.1 What if $(x,y) \notin G$?
2.2 What if $(x,y) \in G$? Can you find a path $x \leadsto y$ in $G'$ which does not pass $v$?


NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

In parametrized complexity we solve the problem by fixing some parameter (say $k$).  If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is fixed parameter tractable in $k$.  Here $f(k)$ is just some computable function.  There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP.  We believe that XP is not equal to FPT (just as we believe P $\neq$ NP).  But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy.  In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction.  The class W[0] is the class FPT.

These are some samples in different classes of the W hierarchy:

Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
Independent set and Clique are both W[1]-complete
Dominating set is W[2]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at this paper.

And if you want even more is good to read Grohe and Fomine's book

And finally:

  Is this always the case for problems that admit an
  FPTAS/pseudo-polynomial time algorithm such as Knapsack

Not necessarily, it's known that if the problem has FPTAS then it's also FPT (which is obvious), but there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...


How to construct and write down a Turing machine for a given language?

What all strategies to devise a program for a Turing machine - or for any other machine, for that matter - boil down to is this: learn how to write programs for easy languages, and then use these programs and rules of composition to figure out more complicated ones. Programming languages - including Turing machine programs - expose an interface to the underlying computer, which allows you to perform some limited number of operations. Programming is the art and science of finding a sequence of such operations to solve your problem.

Can you write a Turing machine to recognize $a^+$?
Change the Turing machine in (1) to recognize $\#$ only. Hint: it's a different symbol and you only want one of them.
Change the Turing machine in (1) to recognize $(b + c)^*$. Hint: you'll now take either of two symbols instead of one symbol.
Take the machines from steps (3), (2) and (1). Create a new machine that does what (3) does, but instead of accepting, it does what (2) does, but instead of accepting, it does what (1) does.

In TM pseudocode, what you get is something along the following lines:

Move one cell to the right.
If the cell is $b$ or $c$, move to the right; else, halt reject.
If the cell is $b$ or $c$, move to the right, and repeat this step. Otherwise, if the cell is $\#$, move to the right and go to the next step. Halt reject in any other case.
If the cell is $a$, move to the right; else, halt reject.
If the cell is $a$, move to the right. Else, if the cell is blank, halt accept. Halt reject in any other case.

Those would serve as decent comments, but coming up with the TM and verifying that it works should also accompany any correct answer.


Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers

Suppose that the image of your mapping has size $k$. This implies a division of $\{1,\ldots,M\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus
$$
 \sum_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}.
$$
Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.


How would one simulate the law of conservation of energy?

I'm having a lot of trouble understanding the question as posed, but I think it's worth making a few general comments about conservation laws and how they are used in physical simulation.

Conservation laws happen because of Noether's theorem. When you are investigating how some physical system evolves over time, it's usually the case that the exact moment when $t=0$ is an arbitrary choice; you could start it 10 seconds later and the system would evolve the same. This is known as time translation symmetry. Any physical system which is time translation invariant is a system where energy is conserved.

Let's take as an example the problem of simulating a gas, where viscosity can be ignored, in one dimension.

We denote $\rho(x,t)$ as the density of the gas at a time and place, $v(x,t)$ is the velocity, $E(x,t)$ is the energy, and $p(x,t)$ is the pressure.

Then the equations we are solving are the Euler equations:

$$\frac{\partial}{\partial t}  \rho + \frac{\partial}{\partial x}  \rho v = 0$$
$$\frac{\partial}{\partial t}  \rho v + \frac{\partial}{\partial x}  \left( \rho v^2 + p \right) = 0$$
$$\frac{\partial}{\partial t}  E + \frac{\partial}{\partial x}  v\left(E + p\right) = 0$$

The pressure is defined in terms of the other variables, called the "equation of state". If we assume an ideal gas, $E = \frac{p}{\gamma - 1} + \frac{1}{2} \rho v^2$ where $\gamma$ is the heat capacity ratio, which is different for different gases.

The Euler equations are, respectively, conservation of mass, conservation of momentum (note that $\rho v$ is momentum), and conservation of energy. The equations state that a local change of (say) energy in time is balanced exactly by a change in space. So those three conservation laws are, in a deep sense, exactly the system that you are trying to simulate.

So I think that it's misleading to think of conservation of energy as something to exploit in simulating some physical system. Conservation of energy is a central part of the system that you're trying to simulate.

One last thing: Physical simulation, especially of thermodynamic systems, suffers from a phenomenon known as "numerical dissipation" or "numerical dispersion". The fact that you are using discrete time steps to simulate a continuous system means that something has to give, and depending on the numerical methods that you are using, this sometimes translates as unwanted diffusion of some quantity that should be locally conserved. Like energy.


The perfect shuffle alone has never been used as an interconnection network; it always included exchange links, in order to allow for a worst-case $O(\lg n)$ routing algorithm.
Algorithms for reduction, broadcast, parallel prefix, transpose etc are given in

Yosi Ben-Asher , David Egozi , Assaf Schuster, SIMD Algorithms for 2-D Arrays in Shuffle Networks.

Stone was the first researcher to provide algorithms for the perfect shuffle network, including algorithms for the FFT, matrix transpose etc.

This network has been used in several parallel machines, but mostly in multi-stage shuffle-exchange networks such as the Omega network (which uses the perfect shuffle between stages). An example is the IBM SP3 machine.

Note that these are message-passing algorithms, whilst you refer to a GPU, which is instead a shared-memory device.


Efficient membership check in multiple ranges

An interval tree can retrieve intervals containing a specified point in $O(\log n)$. If the set of intervals is fixed, it is very easy to implement.


What are the steps/tricks/tips to construct a Büchi automaton from a given language?

You can construct an NBA for an $\omega$-regular expression $r$ by induction on the generating sequence of $r$, using the constructive closure properties of NBAs.

You can see some examples here


In Amortized Analysis, can we chose how big $n$ is?

It depends a bit on what you mean with "choose an $n$". If you pick a fixed $n$, say a million, then no, that's not enough. Asymptotic notation already means "for sufficiently large inputs, the runtime is...". So a counterexample of any fixed size won't do.

If however you show a method that for an infinite number of sufficiently large $n$ produces a counterexample, then this is valid.


What algorithm to use, least waste when sawing wood planks

This problem can be reduced to the binpacking problem (which is a special instance of the cutting stock problem, see @fade2black's answer)
The bins can represent the fixed size wood pieces, which are 100cm long in your example.
The items to be binned can be the list of needed wood lengths.
Minimizing for the minimal number of bins equates minimizing waste;

Let $L_M$ be the size of a bin, $L_{all} = \sum_{i=1}^N L_i$
Suppose there is a distribution of $L_i$ over $M_{min}$ bins, but it is not the minimum amount of waste.

Then there is a distribution of $L_i$ over $M_{minwaste}$ bins where $M_{min} < M_{minwaste} $
And then the waste can be expressed as $[M_{minwaste} * L_M - L_{all}] < [M_{min}*L_M - L_{all}] $
which simplifies to: $M_{minwaste} < M_{min} $
This contradicts our premise and its derivative of $M_{min} < M_{minwaste}$ .

Hence, $M_{minwaste}$ cannot be greater than $M_{min}$ and have less waste.

Python example using the binpacking module, note that binpacking is indeed NP-hard, as such the binpacking module is most likely using heuristiscs which will most likely result in approximation answers.
import binpacking
needed = [60, 30, 50, 20]
print(binpacking.to_constant_volume(needed, 100))

Outputs the following:
[[60, 30], [50, 20]]


On graph isomorphism for weighted graphs

This on contrary appears to be a problem of greater difficulty than graph isomorphism. If you had a polynomial time solution to this problem,you can reduce graph isomorphism to it by keeping each edge weight say equal to some constant $c$. Also graph isomorphism is not known to have a polynomial time solution. It is a still an open question.


Relative succinctness of NFAs and regular expressions

DFAs can be exponentially more succinct than regular expressions. A simple example is the language of all words over $\{a,b\}$ in which the number of $a$s and the number of $b$s are each divisible by $n$. This is accepted by a DFA of size $n^2$, but requires a regular expression of length $2^{\Omega(n)}$. For proof, see Example 23 in the survey From finite automata to regular expressions and back by Gruber and Holzer.

Gruber and Holzer improved this in their paper Tight bounds on the descriptional complexity of regular expressions, also mentioned in their survey (Theorem 24 of the survey). In fact, they prove an even stronger result (Theorem 8 of the paper): there is a language described by a regular expression of length $O(n)$ whose complement requires a regular expression of length $2^{2^{\Omega(n)}}$. (A regular expression of length $O(n)$ corresponds to an NFA having $O(n)$ states and so to a DFA having $2^{O(n)}$ states, whose complement has the same number of states.) The regular expression with this wondrous properties, over the alphabet $\{0,1,\$\}$, is
$$
(0+1)^{\geq 1} + (\epsilon + \Sigma^*\$)\bigl((0+1)^{\leq 4n-1}\$ + (0+1)^{\geq 4n+1}\bigr)\Sigma^* \\
+ \Sigma^*\$(0+1)^{3n}(0+1)^*0\Sigma^{n+1}1\Sigma^* \\
+ \Sigma^*\$(0+1)^{3n}(0+1)^*1\Sigma^{n+1}0\Sigma^* \\
+ \Sigma^*\$(0+1)^*0\Sigma^{2n}1\Sigma^* \\
+ \Sigma^*\$(0+1)^*1\Sigma^{2n}0\Sigma^*
$$
We can even obtain an example over the binary alphabet $\{a,b\}$ using the homomorphism
$$
0 \mapsto abbb, \quad 1 \mapsto aabb, \quad \$ \mapsto aaab.
$$

The way all of these results are proved is via the concept of star height: a language of star height $h$ requires a regular expression of length $2^{\Omega(h)}$. Unfortunately lower bounds on the star height are rather difficult to establish, so instead one uses the more manageable cycle rank, a theorem of McNaughton identifying the two for a class of languages known as bideterministic. (For more details, consult either of the sources cited above.)


Reference request: Introduction to reinforcement learning with hand calculation examples

Poole and Mackworth's Artificial Intelligence: Foundations of Computational Agents, fully available online, has one such example for Q-learning.

Sutton & Barto's Reinforcement Learning: An Introduction, also online, has a few tiny iterative examples here and there.

Isbell & Littman's udacity course on RL has examples, quizzes, and programming exercises in Java.


Closure of Turing-recognizable languages under homomorphism

A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L_1, L_2 \in \mathcal{L}$ we also have $L_1 \cdot L_2 \in \mathcal{L}$.

Here, $A \cdot B = \{ v \cdot w \mid v \in A, w \in B \}$.

A class of languages $\mathcal{L}$ is closed against homomorphism if for every language $L \in \mathcal{L}$ and every (word) homomorphism $f$ we also have that $f(L) \in \mathcal{L}$.

Here, $f : \Sigma \to \Sigma^*$ is lifted to words and sets in the natural way, i.e.

$\qquad\displaystyle f(w) = f(w_1) \dots f(w_n)$ for $w = w_1 \dots w_n$,

and

$\qquad\displaystyle f(A) = \{ f(w) \mid w \in A\}$.

(Note that can make a difference if you require $f : \Sigma \to \Sigma^+$.)

It's easy to see that the two are not the same.

   Let $A = \{ w \in \{a, b\}^* \mid |w|_a \in 2\mathbb{N} \}$. Clearly, $\mathcal{A} = 2^A$ is closed against concatenation but not against homomorphism.

 Let $B = \{ ww \mid w \in \{a,b\}^* \}$. Then, $\mathcal{B} = 2^B$ is closed against homomorphism but not against concatenation.
 (mentioned by chi in a comment)

 For completeness, $2^{\Sigma^*}$ is closed against both, and $\mathcal{A}\cdot\mathcal{B}$ against neither.


Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

An $\mathsf{NC}^0$ circuit with single output of depth $\ell$ has $O(2^\ell)$ nodes, and in particular can depend on at most $O(2^\ell)$ many input bits.

$\mathsf{NC}^0$ circuits become more interesting when we allow them to have many outputs. Amazingly, there are some things you can actually do with some circuits. Check out the classic paper Crypography in $\mathsf{NC}^0$ by Applebaum, Ishai, and Kushilevitz.


Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

Your first approach doesn't quite work. If it is not the case that for any $k$ there is some language that requires exactly $k$ states, then all you know is that there exists a single $n$ such that every $n$-state DFA can be reduced to an equivalent DFA with fewer states.
The second approach does work, and requires a lower bound technique such as the pumping lemma (the pumping constant is the number of states) or Myhill–Nerode theory. Try the following language: all words whose length is a multiple of $k$.


What is the worst case time complexity for intersection tests with BVHs?

Worst time complexity is $O(n)$: If all triangles are identical the bounding boxes are the same as well and every triangle needs to be intersected.

Btw.: The triangles do not need to be identical for the bounding boxes to be the same. The result is still $O(n)$ in that case.


Propositional formula in DNF can be decided in polynomial time?

The conversion from CNF to DNF can come at an exponential cost. For example $(a_1 \lor b_1) \land \cdots \land (a_n \lor b_n)$ expands to $2^n$ many terms. As you comment, for DNF satisfiability is easy - it is falsifiability which is hard. If the problem is trivial, you don't input it to a SAT solver, and that's why SAT solvers accept CNFs instead of DNFs.

If you believe that P is different from NP, then this implies that there is no polynomial time way to convert CNF satisfiability to DNF satisfiability, since the former is NP-complete while the latter is in P.


Is there a way to compute time without system clock

You could try to measure time from RAM transfer rates. You'd need to know the precise clock ratio between the RAM and the CPU. There would have to be a precise clock ratio; I don't think this is the case on typical PC architectures as the RAM and the CPU have their own clock and I'm not sure the RAM peak transfer rate is a constant.

You'd need to block all other sources of interrupts, because if the CPU is responding to some other interrupt, it may notice too late that the RAM is ready, so it would tend to drift.

The nail in the coffin is that while the CPU is waiting for the RAM, it isn't doing anything else. The same objection goes for anything that requires the CPU to perform computations to obtain the time — a CPU that does nothing but measure the time has no time left to do useful things.


Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)

Consider an automaton with $n$ states, all final, and a transition between every pair of states for every symbol.

There are two variants of the subset construction.  A "formal" one where always $2^n$ subsets are considered, and a "practical" one, where you consider only states that are reachable. Of course only the latter interpretation of subset construction will work.


In a context-free grammar there are two sets of symbols (two alphabets, if you will). One is the set of symbols that can be replaced by others: these are the non-terminal symbols. The other is the set of terminal symbols, which (you may have guessed) cannot be replaced.

At some point, a derivation is expected to produce a string of symbols that is immutable, and because it is immutable we tend to think of these strings in the same way we think of numbers (as opposed to arithmetic expressions), as elements of a language that is being defined. This is one game that we play.

You can still think of those two sets of symbols as partitions of a bigger set, the "set of all symbols". This would allow you to play other interesting games.


Syntax directed translation , definition and actions

Syntax directed translation uses the hierarchical structure of the input to generate the output. In other words, you exploit the grammar structure to help you to translate the program.

Translating using semantic rules

Semantic actions allow to embed code into a cfg which helps you to translate the program/source code. The following Ruby code should help you to figure out how things work. The following simple translator translates a single line infix expression into postfix expression.

First of all note that I use grammar that is suitable for top-down recursive descent parser, namely without left recursion and unambiguous. Transformation of this grammar is given in your book. So, you have to be familiar at least with a top-down recursive descent parsing method which is simple if you understand and have no problems with direct/indirect recursive calls.

Also please pay attention to how I embedded prints into while loops in order to emit postfix notation. As an exercise try to move the print to another line to get infix notation.

I wrote deliberately in Ruby so that you could play with the code and see it in action and modify it easily. If you have Ruby installed just type ruby parser.rb and see output.

@source = "1*2-3*4"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  term()
  while(@token == '+' || @token == '-')
    op = @token #store the operator + or -
    get_token() #move to the next input symbol
    term()
    print op # <= semantic action (print operator + or -)
   end
end

def term()
  factor()
  while(@token == '*' || @token == '/')
    op = @token #store the operator
    get_token() #move to the next input symbol
    factor()
    print op # <= semantic action (print operator * or /)
  end
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    print tk # <= semantic action (print a digit)
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

Example outputs:

1*2-3*4 is translated into 12*34*-
1+2-3*7 is translated into 12+37*-

Computing expression value using node attributes

The following piece of code demonstrates node attributes in action to compute the value of an infix expression. Semantic actions this time around are lines which compute attribute of each tree node, that is, actual value of the expression.

@source = "9*3-3*7-2"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  exp_t = term()
  while(@token == '+' || @token == '-')
    op = @token
    get_token()
    term_t = term()
    # compute attribute of the tree node
    if op == '+'
      exp_t += term_t
    else
      exp_t -= term_t
    end
  end

  return exp_t #return attribute to one level up in the tree
end

def term()
  term_t = factor()
  while(@token == '*' || @token == '/')
    op = @token
    get_token()
    val = factor()
    # compute attribute of the tree node
    if op == '*'
      term_t *= val
    else
      term_t /= val
    end
  end

  return term_t #return attribute to one level up in the tree
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    return tk.to_i #to_i means convert to integer
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

Examples:
9*3-3*7-2 results in 4
9*3-3*7 results in 6
1-1+1*1 results in 1


Average case complexity of search data structures

One such notion is that of smoothed analysis, in which we compute the worst-case expected complexity of an algorithm on a randomly perturbed input. In more detail, let $N(x)$ be a randomly perturbed version of $x$, and let $T$ be the time complexity of the algorithm. Then we are interested in
$$
\sup_x \mathbb E[T(N(x))].
$$
The "worst case" aspect is with respect to the unperturbed input, and the "average case" aspect is with respect to the perturbation.

The simplex algorithm has been shown to be polynomial time in this sense, although its worst case complexity is exponential.


Deadlock and cycle in a resource allocation graph

I did some thinking and then searching and all RAG conditions of this example leads to conclusion that there is no deadlock (altho there is a cycle here).

Beside after searching I found this where you can find this:

Which clearly stands Graph With A Cycle But No Deadlock

Are you sure that you have your graph correct here?


What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable?

Here are several interpretations of your question:

  $L_1$ consists of all descriptions of Turing machines which are deciders (always halt) and the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which erased its input and transfers control to $T$. Then $\langle M \rangle \in L_1$ iff $T$ halts on the empty input.

Indeed, if $T$ halts then $L(M) = \Sigma^*$, while if $T$ doesn't halt, then $M$ is not a decider.

  $L_2$ consists of all descriptions of Turing machines which are either not deciders, or the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which simulates $T$ on the empty tape, and if $T$ halts, solves some NEXP-complete problem on the original input. Then $\langle M \rangle \in L_2$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then $M$ decides an NEXP-complete problem, which by the nondeterministic time hierarchy theorem doesn't belong to NP. In contrast, if $T$ doesn't halt on the empty input, then $M$ is not a decider.

  $L_3$ is the promise problem in which the input is a description of a Turing machine which is promised to be a decider, and the goal is to determine whether the language it decides is in NP.

Alternatively, you can ask whether there exists any decidable language $L_4$ such that

The description of any machine deciding a language in NP belongs to $L_4$.
The description of any machine deciding a language not in NP doesn't belong to $L_4$.

This is undecidable, in the sense that there is no Turing machine that halts and answers YES on all YES instances, and halts and answers NO on all NO instances.

Given a Turing machine $T$, construct a new Turing machine $M$ with two inputs $n,x$. The Turing machine simulates $T$ for $n$ steps. If $T$ halts within these $n$ steps, then it solves some NEXP-complete problem on $x$. Otherwise, it simply returns YES. The new machine $M$ is a YES instance of $L_3$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then there exists an NEXP-complete language $L$ and an integer $n$ such that $(n,x) \in L(M)$ iff $x \in L$, and so $L(M) \notin \mathsf{NP}$. In contrast, if $T$ doesn't halt on the empty input then $L(M)$ consists of all pairs $(n,x)$, and so $L(M) \in \mathsf{NP}$.


Reconstruct the minimal path cost from the delta-stepping algorithm?

The algorithm that you're implementing is based on the Dijkstra Algorithm, so we can use the same idea to get the path, that is, keep the predecesor data each time you relax the edges (see pred data structure below). Actually, in the same paper, they state where you have to look at in the following method.

However, we need the information of the vertex we are using in the relaxation method, as you know we are comparing these two values, $tent[w]$ vs $tent[v] + Cost[v,w]$. So if after all $tent[v] + Cost[v,w]$ is less than $tent[w]$, we need keep $v$ to say we are going to use the edge $(v,w)$.

Then I suggest you to introduce $v$ as follows:

Replace $Req$ for this definition, $$ Req = \{(w, tent(v) + c(v,w), v)\ :\ v\in B[i] \text{ and  } (v,w) \in light[v]\}. $$

Add a third argument to the method relax:

 relax(w,d,v)
    if d < tent[w]:
        pred[w] = v
        ...

And fix all for each with $(w,d,v)\in Req$ and the other.

To retrieve the path from $s$ to $w$, do something like:

for v in V: pred[v] = INF
...
def findpath(w):
  v = w
  path = []
  while pred[v] is not INF:
     path.append(v)
     v = pred[v]
  path.reverse()
  return path


What kind of language does the following DFA accept?

It accept all the words containing $i$ "a"s and $j$ "b"s for which $i \equiv j \pmod{4}$.


Median of distribution with memory constraint

Sure, you can definitely achieve this using a bit more running time.  Here is a conceptually simple approach, which might not be optimal, but will get you started and is probably pretty good:
Use binary search to find an approximate median $m$.  How do you know whether is candidate $m$ is too large or too small?  Sample $n'$ times from the distribution, count how many times the samples are $\ge m$, and compare that count to $n'/2$. This can be done with $O(1)$ space.
Then the key question becomes: how do we choose $n'$, to control the probability of error?  A simple approach is to choose $n'$ to be sufficiently bigger than $n$ that the probability of error in each iteration of binary search is $t$ smaller than the probability of error when using $n$ samples, where $t$ is the number of iterations of binary search needed to achieve the desired accuracy.  Then, a union bound ensures that this will meet your accuracy conditions.
Unfortunately, your accuracy condition is a bit hard to work with, when we don't know anything about the distribution of data, as the accuracy of the sample median can be arbitrarily bad.  For instance, consider a distribution that outputs $0$ with probability $(1-\epsilon)/2$ and $100$ with probability $(1+\epsilon)/2$.  Then the sample median is about equally likely to be 0 or 100, whereas the distribution median is 100,
so the average error of the sample median is about 50 (unless you're drawing $\gg 1/\epsilon^2$ samples).  That's a particularly nasty distribution, and it's going to be hard to work with.  But if you assume the distribution is approximately Gaussian (say) with standard deviation $\sigma$, then the error of the sample median, with $n$ samples, is roughly $1.25 \sigma/\sqrt{n}$.  Thus, the above algorithm can be used where we set $t \approx \lg (\sqrt{n}/1.25)$ and we set $n' \approx n t^2$.
That's one simple approach.  You can probably do better.  You might like to look up streaming algorithms for computing the median, as they tackle the problem you're working with: given an unlimited number of samples from the distribution, but only a limited amount of space, what's the best estimate we can get for the median?  For instance, here is one simple algorithm: the first layer repeatedly takes three samples and outputs the median of those three; the second layer repeatedly takes three numbers from the first layer and outputs the median of those three; and so on.  After logarithmically number of layers, you get a reasonable approximation to the median.  There's an entire literature on this subject, and you should be able to find lots more.


Convolution matrix are mean to change your image so you have to treat all the pixels.

For pixels without surrounding pixels there are different way to treat than dependently of the result you expect. You can ignore them and get a smaller image. Put an arbitrary value for their surrounding. Or consider the surrounding being symmetrical to the image.

Since the matrix apply on the image it doesn't mater if you apply it up to bottom, left to right or whatever. Each pixel of the result is computed as a local result of the convolution on the image.

For example  for an image
$$\begin{pmatrix}
a &b&c&d\\
e&f&g&h\\
i&j&k&l\\
m&n&o&p
\end{pmatrix}
$$
If we discard the surrounding pixels the result of the convolution with you matrix will be :

$$\begin{pmatrix}
f-e&g-f\\
j-i&k-j
\end{pmatrix}
$$

So for your convolution, a pixel $(i,j)$ is defined as $I_{(i,j)}-I_{(i,j-1)}$.
So this convolution stress the differences between pixels hence show the edges.

I hope its clear.


Where can I find the data of the computer experiments in the book "Neural Networks and Learning Machines"?

The MATLAB files for the book are accessible here.
I'm not familiar with the text, but there are .mat files in the zip named

c.mat
sig_lorenz_full.mat

which probably contain the data.  There are also a handful of TIFF files (images) from which he draws the other data.


How is the set of functions from ${\{a,b\}}$ to $N$ countable?

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite.

You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{N}$ using the injection $\alpha$ below:

$\alpha : \mathbb{N}^{\{a, b\}} \rightarrow \mathbb{N} : f \mapsto 2^{f(a)}(2f(b)+1)$


Chord protocol - How should I go about mapping nodes to placeholders on the ring?

Take the last m bits of the hash.  View it as a number in binary.  That's how you convert the hashed value into a number.  The position is a number.  That should answer your questions 1 & 3.

Now that you know how it works, you should be able to answer question 2 yourself.  If not, go back and read the original paper (especially Section IV.B), which should make this clear.


Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional?

For the standard enumeration $\varphi$ and some computable permutation $h$,
$$\forall e;~ \psi_e = h^{-1} \varphi_{h(e)}h ~~~~(*)$$

We want to prove that such $\psi$ is an acceptable enumeration. It suffices to find computable functions $f$ and $g$ such that for all $e$, $\psi_e = \varphi_{f(e)}$ and $\varphi_e = \psi_{g(e)}$.

$h^{-1} \varphi_{h(e)}h$ is partial computable. So by s-m-n theorem, there is a computable function $f$ such that for all $e$, $h^{-1} \varphi_{h(e)}h = \varphi_{f(e)}$, therefor by $*$ we have, $\psi_e = \varphi_{f(e)}$

$h \varphi_e h^{-1}$ is also partial computable. So again by s-m-n theorem, there is computable $g'$ such that for all $e$, $h \varphi_e h^{-1} = \varphi_{g'(e)}$. Define computable function $g$ as $g = h^{-1} g'$. In $*$ replace $e$ with $g(e)$ to get
$$\psi_{g(e)} = h^{-1} \varphi_{hg(e)}h ~.$$
By definition of $g$, we have $h g = h h^{-1} g' = g'$, so
$$\psi_{g(e)} = h^{-1} \varphi_{g'(e)}h ~.$$
By definition of $g'$
$$\psi_{g(e)} = h^{-1} h \varphi_e h^{-1} h ~,$$
and thus
$$\psi_{g(e)} = \varphi_e ~. ~~\Box$$


The simplest solution (in terms of saving you the time of understanding the literature) is probably going to be to use integer linear programming (ILP / MILP).  You can formulate it as an ILP instance, then apply an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_{i,j}$, with the goal that $x_{i,j}=1$ means that the $i$th person is assigned to $j$th time slot, and $x_{i,j}=0$ means that they're not assigned to that time slot.  Now you can write down some linear inequalities/equations constraining these, e.g.,

$\sum_{i} x_{i,j} = n$ for each $i$ (each time slot needs to be filled with $n$ people)

$\sum_j x_{i,j} = c_i$ for each $i$, where $c_i = $ the number of shifts the $i$th worker should be assigned

Also if the $i$th worker isn't available for the $j$th slot, then add a constraint that $x_{i,j}=0$.

Also, $0 \le x_{i,j} \le 1$ (to force each $x_{i,j}$ to be zero or one).

The combination of all of these constraints gives you an integer linear program.  Ask the ILP solver to find a feasible solution, and boom, you're done.  This might not be the most efficient possible algorithm, but it will be simple to implement and play around with, and I expect that it'll give high-quality solutions and be fast enough for the size of problem you're likely to encounter in practice.


How to prove that replacing a character in a string in both C and JavaScript is equivalent?

I would start by creating a formal definition of the function that you want and then proving for correctness each of the implementations.

Consider the following axiomatic definition:

$$replaceAt: string * \mathbb Z *char \to string$$

$$\forall c:char . ( \forall i \in \mathbb Z~.~replaceAt(``,i,c) = `` )$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~replaceAt(s,i,c)[i] = c ))$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~len(replaceAt(s,i,c)) = len(s) ))$$

$$\forall c:char .(\forall s:string . ( \forall i,j \in 0..len(s)-1 . i \neq j \implies replaceAt(s,i,c)[j] = s[j] ))$$

$$\forall c:char .(\forall s:string . ( \forall i \in \mathbb Z . i \geq len(s) \implies replaceAt(s,i,c) = s ))$$

If you can prove the correctness of each implementation to these axioms I'd say they're equivalent. At the moment your C implementation is not even a function.  Your Javascript function takes a string and not a char.  None of them are defined for indexes greater than your input.

I don't think comparing implementation to implementation makes sense as there are lot of differences in the implementation models of each language.


Making mathematical expressions as balanced trees as possible

Since these are mathematical expressions, you can bracket the second one as (4 (x-1)) ((y-2) (z-3)) to make it more balanced. In many programming languages this wouldn't be allowed, because with floating point arithmetic, the order of operations will often change the result.

Can't see any way to improve the first one.


All Huffman codes satisfy Kraft’s inequality with strict equality. We will give two proofs of this fact, one specific to Huffman codes, and the other applying to all minimum redundancy codes.

First proof. The first proof is inductive. Recall that Huffman’s algorithm proceeds as follows. We choose the two symbols with minimal probability, and merge them. We then run the algorithm on the new distribution. Finally, we split the merged symbol into two symbols by adding a suffix of 0 to one of them and of 1 to the other.

When there are only two symbols left, Huffman’s algorithm assigns them the codewords 0 and 1, and since $2^{-1} + 2^{-1} = 1$, we see that Kraft’s inequality is satisfied with equality.

Now suppose that there are more than two symbols. Huffman’s algorithm merges two of them, and then runs on the resulting code. The induction hypothesis shows that Kraft’s inequality is satisfied with equality on the new code. The final step is splitting one of the symbols. In this step, a codeword of length $\ell$ is replaced by two codewords of length $\ell+1$. Since $2^{-\ell} = 2 \cdot 2^{-\ell-1}$, we see that the final code also satisfies Kraft’s inequality with equality.

Second proof. The second proof applies to any minimum redundancy code. We start by associating with each prefix code a binary tree. This is done as follows. If the prefix code consists of just the empty word, then the binary tree is a leaf. Otherwise, we construct a binary tree for all codewords starting with 0, another one from all codewords starting with 1, and join the two at the root. If we think of the edges as labeled by 0 and 1, then we can recover the codewords by traversing the tree from root to leaves and concatenating the symbols written on the edges.

A simple induction shows that $\sum_f 2^{-\ell(f)} \leq 1$, where $f$ goes over all leaves, and $\ell(f)$ is the depth of $f$; this is just Kraft’s inequality. The same proof also shows that equality holds iff all internal nodes have exactly two children. In this case we call the code complete.

If the code is incomplete, there is an internal vertex with only a single child. We can replace this vertex by its child, thus obtaining a new code in which no codeword gets longer, and some get strictly shorter. The new code has less redundancy than the original one. This shows that if we start with a minimum redundancy code, then the code must be complete, and so Kraft’s inequality holds with equality.


Why Shannon's Entropy is said to be a measure of information?

Yes, of course. Shannon's work was on the transmission of information over discrete, noisy channels. It centred on the trade-off between bandwidth and signal-to-noise ratio, and, grossly over-simplifying it, in particular what the maximum transmission rates could be with and without the presence of noise induced error and how to construct suitable codes. This involves coding theory1 and probability theory, which is where some of things that have you confused come from.

It is also incorrect that you need 5 bits to encode letters. If we have a known frequency distribution of the letters, we can encode the more frequent ones with fewer bits, and less frequent ones with more, which will give much shorter messages that the simple 5-bits-for-everything coding. For example, the entropy given by the usual distribution of English is 4.219 bits per symbol, so we can encode common symbols like 'e' with perhaps 1 bit, and uncommon symbols like 'q' with 5 or 6 bits, an on average we use less than 5 bits per symbol. If we use more cunning coding schemes, for example ones that take into account digram and trigram frequencies, we can get this average down to a little over 2 bits per symbol by using short codes for common two and three symbol groups.

Also, notably, your title is backwards, Shannon's Entropy is a measure of information, not the other way around. It is not the only one possible, however Shannon argues that it is the most natural and intuitive.

The full extent of Shannon's (seminal) work on information theory is too large to encompass in this format, but there is plenty of further reading. The wikipedia entry on information theory is reasonably approachable, and the page on coding theory also adds something. For the real stuff of course, you can just read the paper in which Shannon invented information theory essentially out of whole cloth; "A Mathematical Theory of Communication"2.

Footnotes

This is not not suggest that Shannon was applying coding theory, he was inventing new ideas that would become large parts of coding theory.
Claude E. Shannon, "A Mathematical Theory of Communication", The Bell System Technical Journal, 27:379-423,623-656, 1948.


Efficient immutable data structure for small multi-sets of integer ranges?

I would suggest looking at interval trees and segment trees.  A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).


Difference between symbolic execution and reachability analysis

Generally, reachability analysis is a goal (determine which points in the code are reachable), whereas symbolic execution is a specific algorithmic technique (a tool for analyzing code).  You can use symbolic execution for reachability analysis, or for other goals.  Conversely, you can use other algorithms for reachability analysis.

Classically, symbolic execution was a static analysis.  However, recently it has been widely used in a hybrid static-dynamic analysis: see, e.g., concolic execution.  These hybrid methods seem to be very effective, but they are not purely static.


None of your examples holds up: each has queries that allow multiple answers, and each has queries that allow only singleton answers.

So you are really after a property of queries.
On the most abstract level, given a set $S$ the term you are looking for is function:

$\qquad f : Q \to S \\
\qquad f(q) = s \text{ s.t. } q(s) = 1$

where $Q$ is the set of queries (predicates), i.e. $Q \subseteq S \to \{0,1\}$. Note how $f$ is a (well-defined) function if and only if all $q \in Q$ have a support (set of values on which $q$ is $1$) of size $1$.

If queries end up being true for (i.e. returning) multiple values, we call $f$ a relation. Or, alternatively, a function that maps queries to (possibly empty) sequences of results, i.e.

$\qquad f : Q \to S^*$.


MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

Sorry for answering an old post
The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x_i}\oplus x_j)$)  instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.
To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)
For instance:
If we have an unsatisfiable formula that is $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4) $
We have a graph like this:

that is not bipartite
There are three clauses that are satisfiable and so we have just to eliminate an edge
Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex  to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut
To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals
For instance:
We have this graph,

We create the follwing formula $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5) $
So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.


Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms

Given two finite non-empty alphabets $\Sigma,\Delta$, a homomorphism is a mapping $h\colon \Sigma^* \to \Delta^*$ that satisfies the following two properties:

$h(\epsilon) = \epsilon$.
$h(xy) = h(x) h(y)$.

(Actually the first property follows from the second, since it implies that $h(\epsilon) = h(\epsilon \epsilon) = h(\epsilon) h(\epsilon)$, and so $h(\epsilon) = \epsilon$.)

It is not hard to show that $h$ is determined by its value on letters of $\Sigma$. Indeed, if $w = \sigma_1\ldots \sigma_n$, where $\sigma_1,\ldots,\sigma_n \in \Sigma$, then
$h(w) = h(\sigma_1) \ldots h(\sigma_n)$.
Conversely, if $h_0\colon \Sigma \to \Delta^*$, then the mapping $h(\sigma_1 \ldots \sigma_n) = h_0(\sigma_1) \ldots h_0(\sigma_n)$ defines a homomorphism. In formal language theory, one often identifies $h$ and $h_0$.


Algorithm to establish a global ranking given individual rankings

There is an entire area, rank aggregation (in your case, partial rank aggregation) which deals with these issues. You can take a look at Dwork et al., Rank aggregation revisited and Ailon, Aggregation of partial rankings, $p$-ratings and top-$m$ lists and the pointers therein. There are many other relevant papers online.


Problem with understanding Multi-party security circuit for secure stable matching

Stable matching involves finding a matching between two groups of people (group 1, say males, and group 2, say females).  Those are the groups that is referring to.


weight constrained shortest path problem variants

Check the definition of reduction again.  A reduction that works for general dags is a perfectly valid reduction.  It meets all of the conditions in the definition.  I suggest working through the definition -- that should help you see what is going on.

Or, to put it another way: The problem for "general DAG" is at least as hard as the problem for "a particular type of DAG", so if you've proved the problem is NP-hard for a particular type of DAG, you've also proven it is NP-hard for general DAGs, too.


Proving that language is regular or not regular

Here is a proof that the language $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ is regular. It can be modified to show that the first three on your list are regular. (Note that I changed $wu$ to $uw$.) Given a DFA for $L$, we build an NFA for $L_0$. The first thing that the NFA does is guess (take an $\epsilon$ move) a state $q$, whose intended semantics is the state that the DFA for $L$ ends up after reading $u$. It then simultaneously runs two copies of the DFA for $L$, one starting at the start state and the other starting at $q$. On reading a symbol $a$, it moves according to an arbitrary symbol on the first, and moves according to $a$ on the second. A state is accepting if the first copy is at state $q$ and the second is at an accepting state.

For the final one, consider the language $L= a^+ b^+ c^+$, and intersect $L_{+-+}$ with $a^+ c^+$.


Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"?

I do not recall having seen this precise problem before, but it does have a Cook reduction (polynomial-time Turing reduction) to $k$-Clique:

  Let $Y$ be an oracle for $k$-Clique. On input $(G,v)$:

  Determine the maximum clique size $\omega(G)$ via at most $log_{2}(n)$ calls to $Y$ using binary search.
  Create $G'$ by removing all vertices $u \neq v$ where $uv \notin E(G)$ (i.e. $V(G') = N[v]$).
  Determine $\omega(G')$ using $Y$ and binary search.
  If $\omega(G') = \omega(G)$ answer YES, otherwise answer NO.

This puts it in $\Delta_{2}^{P} = P^{NP} = P^{SAT}$, a refinement of your observation.

As there are $O(\log{}n)$ calls to the oracle, we can squash containment a little further; the problem is in $\Delta_{2}^{P}[O(\log{}n)] = P^{NP}[O(\log{}n)] = P^{SAT}[O(\log{}n)]$.

[Thanks here to Ricky Demer] If $P=NP$, then $P^{NP} = P^{P} = P$, so you are correct about the polynomial time solvability in this case (contrary to my original, now edited, musings).

So perhaps the problem is $P^{NP}[O(\log{}n)]$-complete, it shouldn't be (as Dominik observed in his answer) $P^{NP}$-complete. I have tried to use the results of Theorem 3.5 from Krentel's paper to construct a reduction, but unless $P^{NP}$ is low for itself (which I don't think it is, but don't know), this has been without luck. (If it is low for itself, then I have a marvellous proof, sadly there are no margins here to put it in.)


After you sort an array, the minimum can be found in the first position, and the maximum can be found in the last position. This reduces finding the minimum and maximum to sorting an array. However, sorting is actually more difficult than just finding the minimum or maximum, so it's not clear what this reduction is good for.


Direct conversion from regular expression to MSO

The direction from regular expressions to MSO is easy, as MSO is versatile. For a regular expressions $R$ let us construct formulae $\varphi_R$.

$\varphi_{\emptyset} := \bot$

$\varphi_{\varepsilon} := \forall x\bot$

$\varphi_a := \exists x(P_a x \wedge \forall y(x=y))$

$\varphi_{R_1 | R_2} := \varphi_{R_1} \vee \varphi_{R_2}$.

$\varphi_{R_1R_2} := \exists X(\forall y\forall z((Xy \wedge \neg Xz)\to y<z) \wedge [\varphi_{R_1}]_{Xx} \wedge [\varphi_{R_2}]_{\neg Xx})$

$\varphi_{R*} := \exists X(\forall y\forall z((\forall x((\neg x<y \wedge \neg z<x)\to(Xx\leftrightarrow Xy))) \wedge \forall x((x<y\wedge(Xx\leftrightarrow Xy))\to\exists x'(x<x'\wedge x'<y\wedge\neg(Xx'\leftrightarrow Xy))) \wedge \forall x((z<x\wedge(Xx\leftrightarrow Xy))\to\exists x'(z<x'\wedge x'<x\wedge\neg(Xx'\leftrightarrow Xy)))) \to [\varphi_R]_{\neg x<y \wedge \neg z<x})$

Here, $[\varphi]_{\psi(x)}$ denotes the relativization of the formula $\varphi$ to the formula $\psi$.

As you can see, the translation is linear.

In the other direction, I suggest to transform MSO to regular expressions in two steps, with NFAs in between. I know this is not what you are asking for. For complexity analysis it should suffice, however: The translation from MSO to NFAs is known not to have any elementary lower bound. And a direct translation to regular expressions cannot be any better, because of the linear translation from regular expressions to NFAs.


Semantic readings of the Lambek sequent calculus

What constitutes a proof in a system like this is a derivation which is a tree of rule applications. The above translation function is defined by (structural) recursion over that tree. Note, this is why it labels the premises in the rules with $\delta$. This is intended to be mnemonic for "derivation".

I'm guessing but $\mu$ and $\nu$ appear to need to be sequences of lambda terms, while $\phi$ is a specific lambda term (or, equivalently, a single element sequence of lambda terms). $\Gamma$ is a sequence of formulas, and $\mu$ has a lambda term for each element of that sequence. Constructs like $x,\mu$ correspond to sequence extension, extending the sequence $\mu$ with the (particular) lambda term $x$ on the left, symmetrically for $\mu,x$. The parenthesis notation, e.g. $\Gamma(C)$ and $\mu(\dots)$ correspond to (consistently) operating on an element at an arbitrary location in the sequence.

So, for example, an instance of the $\bullet R$ case would look like:
$$\left|\cfrac{\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}}{{X,A\bullet B,Y,Z\Rightarrow W}}\right|_{t_X,t_{AB},t_Y,t_Z} = \left|\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}\right|_{t_X,\pi_1(t_{AB}),\pi_2(t_{AB}),t_Y,t_Z}$$

A translation of a complete derivation would look like: $$\begin{align}
\left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{\cfrac{A\Rightarrow (A\bullet B)/B}{\Rightarrow ((A\bullet B)/B)/A}}\right|
& = \lambda a\left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{A\Rightarrow (A\bullet B)/B}\right|_a \\
& = \lambda a\lambda b\left|\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}\right|_{a,b} \\
& = \lambda a\lambda b(\left|A\Rightarrow A\right|_a, \left|B \Rightarrow B\right|_b) \\
& = \lambda a\lambda b(a, b)
\end{align}$$


Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

You have a fault in $f(n).g(n) = \Omega(n^2)$. Because, $g(n) = O(n)$ and you can't say $g(n)$ is $n$ or $\frac{1}{n^2}$ for example. Hence, we can't say nothing about $f(n).g(n)$. For more example:
$$g(n) = \frac{1}{n}, f(n) = n \Rightarrow f(n).g(n) = \Theta(1)$$
$$g(n) = 1, f(n) = n \Rightarrow f(n).g(n) = \Theta(n)$$
$$g(n) = \frac{1}{n^2}, f(n) = n \Rightarrow f(n).g(n) = o(1) (\text{little-o})$$
$$g(n) = n, f(n) = n \Rightarrow f(n).g(n) = \Theta(n^2)$$

As we don't know about $f(n).g(n)$. However, we can say $f(n).g(n) + h(n) = \Omega(n)$ as $h(n) = \Theta(n)$ and $f(n).g(n) \geq 0$.


Krentel gave two problems complete for $\Delta_2^P$ (see Theorem 3.4):

Input: Boolean formula $\phi(x_1,\dots,x_n)$.
Question: Is $x_n = 1$ in the lexicographically largest satisfying assignment of $\phi$?
Input: Weighted graph $G$, integer $k$.
Question: Is the length of the shortest TSP tour in $G$ divisible by $k$?

Krentel also states that the only previous example of a $\Delta_2^P$-complete problem up to 1988 was Uniquely Optimal TSP, given by Papadimitriou in 1984.
As sdcvvc pointed out, see also the MO discussion at https://mathoverflow.net/questions/2218/characterize-pnp for a nice discussion by Ryan Williams of a machine model that captures $\Delta_2^P$.

Mark W. Krentel, The Complexity of Optimization Problems, JCSS 36 490–509, 1988. doi:10.1016/0022-0000(88)90039-6


We have the following identity:

$$\sum_{i,j,k} a_i b_j c_k = (a_1+\dots+a_n) \times (b_1+\dots+b_n) \times (c_1 + \dots + c_n).$$

Therefore, one can compute the sum of all valid triples in $O(n)$ time by first computing the sum of the $a_i'$, the sum of the $b_i$'s, the sum of the $c_i$'s, and then multiplying these three sums.  This generalizes: you can find the sum of valid k-tuples in $O(kn)$ time.


We can show that $O(2^n\cdot n^{10}) \not\subset O(2^n)$:
As $2^n\cdot n^{10} \in O(2^n\cdot n^{10})$, then, if also holds $2^n\cdot n^{10} \in O(2^n)$ then we will have $2^n\cdot n^{10} \leqslant C 2^n$, which gives false $n^{10} \leqslant C$.


What is this fraction-like "discrete mathematics"–style notation used for formal rules?

This is a standard notation for an inference rule.  The premises are put above a horizontal line, and the conclusion is put below the line.  Thus, it ends up looking like a "fraction", but with one or more logical propositions above the line and a single proposition below the line.  If you see a label (e.g., "LET" or "VAR" in your example) next to it, that's just a human-readable name to identify the particular rule.

You might also see this referred to as natural deduction or Gentzen-style natural deduction.

This is a common notation in the programming languages literature.  You'll see it all over the place.  It's very convenient for the kinds of conclusions and recursive-structured proofs that arise in that field.

You'll see this notation used to express axioms/rules. You can think of each axiom as a template with "meta-variables" (e.g., expr); you can replace each meta-variable with some syntax from the programming language (e.g., any expression that is valid in the programming language), and you'll get an instance of the rule.  The inference rule promises that if all of the propositions are above the line are true (for some instance of the template, where you consistently replace each metavariable with the same value throughout the rule), then the proposition below the line will be true, too.


How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

Let arc $a1$ be $(u_1, v_1)$ and $a2$ be $(u_2, v_2)$. As you mentioned in your question, you want to find a simple shortest path that:

Goes from source $s$ to $u_1$
From $v_1$ to $u_2$
From $v_2$ to the sink $t$.

As you DAG has only positive weights, I think you should find the shortest paths for all three cases (using Dijkstra or any other algorithm) and join them together to get the shortest path from $s$ to $t$ satisfying the given constraints.

EDIT: As the question is for Simple Path, I will refer you to this: http://math.mit.edu/~goemans/18438S12/lec22.pdf.

I am quoting a few important points here:

  We first note that the arc-disjoint path problem, and the vertex-disjoint path problem in a directed graph are equivalent - i.e. we can give a polynomial-time reduction in either direction.
  Undirected Edge Disjoint Paths. In the case of fixed k (i.e. there are k source-sink pairs), there is a polynomial-time algorithm to decide if there are edge-disjoint paths connecting each $s_i$,$t_i$ pair. This result follows from the Graph Minor Project of Robertson and Seymour (1995), and is very involved.
  Yet for super-constant k, the undirected edge-disjoint paths problem is NP-complete. 22-1
  Directed Arc Disjoint Paths. Even for $k = 2$ it is NP-complete to determine if there are arc-disjoint paths P1, P2 connecting s1, t1 and s2, t2. In fact, we can even choose s1 = t2 and s2 = t1 and this problem still remains NP-complete.


Question about "Type checking a multithreaded functional language with session types" by Vasconcelos et al

I think

(Lambda [c→End, x:Int] . (close v))

is indeed what you need to write.  As you mention, it's "impossible" to write it because "c" is fresh.  From my reading of it, it does seem to be a problem in the paper.

I don't think this is a very serious problem, tho, since the same problem appears in other systems and has known solutions (look at the papers about "Calculus of Capabilities" or "Alias Types", for example).

if, as you do in your own syntax, you rely on type-inference, the problem disappears: the type inference can write the "c" since by that time it is known.
you can change accept and request to return two things: a type c and a value of type Chan C.  I.e. introduce "channel type parameters".  Indeed Chan c is a singleton type, so you need c to be able to parameterize over c in order to be able to do anything useful.


Language is non-empty is recursively enumerable (intuitive way)

A language $L$ is partially computable if there is a machine $M$ that on input $x$:

If $x \in L$ then $M$ halts.
If $x \notin L$ then $M$ doesn't halt.

This is equivalent to the other definitions.

To answer your question, what we do is to run the input machine $M$ on all inputs in parallel. If it never accepts on any input, then we never halt, but that's ok.

In order to run $M$ on all inputs in parallel, we use the technique of dovetailing:

We run $M$ for one step on the first input.
We run $M$ for one step on the first two inputs.
We run $M$ for one step on the first three inputs.
And so on.


Getting output of dynamic programming, (contiguous sub array, box stacking)

You are computing inductively an array maxWeight. The value of maxWeight at a certain point $i$ is the maximum over several possibilities. Currently you are remembering only the maximum itself. If you also store which possibility was maximum, then you will be able to use this additional information in order to construct an optimal solution.


How are the 1s and 0s derived by the minimax algorithm for the game called "nim"?

The graph contains all positions reachable from the initial position. The values are determined as follows:

A leaf (a node with no children) is labeled 0 if it is MAX's turn to play, and 1 if it is MIN's turn to play.
A non-leaf belonging to MAX gets the maximum of the labels of its children.
A non-leaf belonging to MIN gets the minimum of the labels of its children.

Hopefully you can now read the book and understand why we're doing the computation in this way.


Why is Clique NP-complete while k-Clique is in P for all k?

The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of
$$
 \sum_{k=1}^n n^k,
$$
which is no longer polynomial.


Bit representation of the hashing multiplication method

$(kA \bmod 1)$ is in the range $[0,1)$. So multiplying that by $2^p$ gives a number in the range $[0,2^p)$. That is:

$$\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor  \bmod 2^p$$

Once you've worked that out, it's not too hard to see:

$$\left\lfloor 2^p (kA \bmod 1) \right \rfloor  \bmod 2^p = \left\lfloor kA 2^p  \right\rfloor \bmod 2^p = \left\lfloor \frac{ks}{2^{w-p}}  \right\rfloor \bmod 2^p$$

So you can implement this by taking $ks$, shifting it $w-p$ bits to the right, then taking the lowest order $p$ bits. Which is exactly the same as taking the highest order $p$ bits of the low word.


SoP or PoS doesn't matter when building a truth table, you just list out the 8 possible inputs and then derive the possible outputs.

If A B and C are all false what is the value of Y?

If only C is true what is the value of Y?

And so on.


"strongly relational m-consistency when the domains contain at most m elements implies satisfiability" plain wrong?

Yes, the quoted statement is correct.  Wikipedia gives a proof in the next four sentences that immediately follow the quote you gave.

The constraints that arise from 3-colorability are not strongly relational 3-consistent, so the quoted statement implies nothing about 3-colorability.  Consequently, there is no contradiction.

(Why aren't the constraints from 3-colorability strongly relational 3-consistent?  Consider a star graph, with a vertex $v$ that is connected to three other vertices $w,x,y$.  There is one constraint per edge in the graph: e.g., one constraint that constrains the colors assigned to vertices $v,w$; one for $v,x$; and one for $v,y$.  Suppose we have a partial assignment that assigns $w$ the color red, $x$ blue, and $y$ green.  Then there is no way to assign a color to $v$ that makes the three constraints for $vw$, $vx$, and $vy$ all valid.  Thus, the constraints do not satisfy the definition of strongly relational 3-consistency.)


Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

There is no "why" here since 2 different edge minimum-cuts in an undirected multigraph can have one edge in common.

Here is an example. Edge set $\{AB,AC\}$ is a minimum cut.
Edge set $\{AB,BC\}$ is another minimum cut. They have edge AB in common.

  For the proof of a maximum of $\binom n2$ min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

I do not think we need that (non)-fact. The random contract algorithm will find each min-cut with a probability of no less than $\frac1{\binom n2}$. Since that algorithm only find one min-cut each time, there are at most $\binom n2$ min-cuts.

Here are several exercises to enhance our understanding of the intersection of two min-cuts.

(Exercise 1). Find an undirected multigraph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 2). Find an undirected simple graph in which 2 different edge minimum-cuts have 2 edges in common.

(Exercise 3). Given a positive integer $n$, find an undirected simple graph in which 2 different edge minimum-cuts have $n$ edges in common.


Is integer factorization reducible to subset sum?

Yes, such a reduction exists.  Subset Sum is NP-complete.  FACT is in NP.  Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.

To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction.  (Implicitly, we get a reduction from FACT to SAT by Cook's theorem, and from the proof of NP-completeness for Subset Sum you will be able to extract a reduction from SAT to Subset Sum.  Now compose those two reductions.)


If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?

why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?

Because it does not matter in the sense that $2^{O(f(n))} = b^{O(f(n))}$ for any positive $b > 1$.

Using the popular set-theoretic understanding of the big $O$-notation, we have
$$\begin{align}
2^{O(f(n))}&=\{2^{g(n)}\mid g(n)\in O(f(n))\} \\
&=\{\left(b^{\log_b2}\right)^{g(n)}\mid g(n)\in O(f(n))\} \\
&=\{b^{h(n)}\mid \exists g(n),\ h(n)= (\log_b2)g(n),\ g(n)\in O(f(n))\} \\
&=\{b^{h(n)}\mid h(n)\in O(f(n))\} \\
&=b^{O(f(n))}\end{align}$$

By the way, there is no need to assume $f(n)\ge n$. For example, all above hold when $f(n) = \lceil\sqrt n\rceil$ or $f(n) = \lceil\log_2n\rceil$.


What are the differences and relations between a type constructor and a type operator?

These sorts of terms in type theory are not always used completely consistently. However, type operators are generally type-level functions: that is, they take as arguments some number of types and return a single type. Type constructors are a specific kind of type operator for which the return type is free in the sense that it is a new type on its arguments.

Generally speaking, if you have a type operator $T: \star \to \star$ and for any type $A : \star$, you have a type $T(A) : \star$, which is not prima facie equal to anything else, then it is called a type constructor.

For example, $\times$, $+$ and $\to$ are all type constructors. Type-level application is not, because the application of $(\lambda X . X + X)\ Y$ is reducible to $Y$, i.e. the application of the type operator is equal to some other type.

In your example, $\mathrm{Ref} : \star \to \star$ would be considered a type constructor. If by "algebraic type" you mean "algebraic data type", then $\mathrm{Ref}(T)$ is not an algebraic data type, because it's part of the type system rather than formed as a composite type out of products and sums.


Does the 'difference' operation add expressiveness to a query language that already includes 'join'?

In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to construct left joins using differences, and then we'll show how to construct differences using left joins.

Let $R$ and $S$ have schemata $(R', T)$ and $(T, S')$, respectively, where $R'$ and $S'$ are the sets of attributes in one schema but not the other, and $T$ is the set of common attributes.

Let $w = (\epsilon, \epsilon, ..., \epsilon)$ be the null tuple for schema $S'$. That is, it is the tuple consisting of all null values for each attribute of $S'$. Then, we define left outer join as follows: R LEFT JOIN S is the set of all tuples $(r, t, s)$ belonging to schema $(R', T, S')$ where...

$(r, t)$  is a tuple in $R$;
(a) $(t, s)$ is a tuple of $S$ or (b) $s = w$;
If $(r, t, s)$ is in the set for $s \neq w$, then $(r, t, w)$ is not in the set.

Example: $R$'s schema is $(A_{1}, A_{2}, A_{3})$, $S$'s schema is $(A_{2}, A_{3}, A_{4})$, and we have that $R = \{(1, 2, 3), (4, 5, 6)\}$ and $S = \{(2, 3, 4), (2, 3, 6)\}$. By (1) and (2) we get the intermediate result $\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$. By (3) we must remove $(1, 2, 3, \epsilon)$, since we have (for instance) $(1, 2, 3, 4)$ and $s = 4 \neq \epsilon = w$. We are thus left with $\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$, the expected result for a left join.

Theorem: R LEFT JOIN S is equivalent to (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Proof: (R EQUIJOIN S) gives us everything required by (1) and (2a). We claim that ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) gives us everything of the form (r, t, w) required by (2b) and (3).

To see this, first notice that (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) is the set of all tuples in $R$ for which there is no corresponding tuple in $S$. To see that, it suffices to note that by projecting the common attributes out of $R$ and $S$ (the attribute set $T$) and taking the difference, one is left with all and only those tuples (with schema $T$) which are represented in $R$ but not $S$. By the EQUIJOIN with $R$, we recover all and only those tuples in $R$ which have values for attributes in $T$ which are present in $R$ but not in $S$; namely, precisely the set of tuples we have so far claimed.

Next, notice that the schema of (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) is the same as that of $R$ (namely, $(R', T)$), while the schema of $w$ is $S'$. The JOIN operation is therefore a Cartesian product, we we get all tuples of the form $(r, t, w)$ where there is no $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$.

To see that this is precisely the set of tuples we needed to add to R EQUIJOIN S in order to construct R LEFT JOIN S, consider the following: by construction, (3) is satisfied, since R EQUIJOIN S cannot contain $(r, t, s)$ if ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) contains $(r, t, w)$ (if it did, then the second part's containing $(r, t, w)$ would be a contradiction); if we were to add another $(r, t, w)$ not in ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), then there would be a $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$, and by the definition of EQUIJOIN, $(r, t, s)$ would also be in R LEFT JOIN S, a contradiction of (3). This completes the proof.

Now we show that left join can be used to construct difference:

Theorem: R DIFFERENCE S is equivalent to PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Proof: Notice that here, $R'$ and $S'$ are empty, since all attributes are shared for DIFFERENCE to make sense. First, we create a new relation from $S$ by duplicating the attribute set in $S$ (handled by RENAME and JOIN) so that it consists of tuples $(t, t')$ on attribute set $(T, T')$ where $t = t'$ (handled by the SELECT). The left join leaves us with tuples of the form $(t, t')$ where $t=t'$ or $t'=w$. Now, to get rid of entries which do also appear in $S$, we must keep only the tuples of the form $(t, w)$, which is handled by the outermost SELECT. The last PROJECT gets rid of the temporary attribute set $T'$ and leaves us with the difference in terms of the original schema.

Example: Let $R = \{(1, 2), (3, 4), (5, 6)\}$ and $S = \{(3, 4), (5, 6), (7, 8)\}$. We first get $S$ with the RENAMEd attribute set $T'$: $\{(3, 4), (5, 6), (7, 8)\}$. The JOIN operation gives us the Cartesian product with all nine possible pairings; this set is not written here for reasons of formatting. The SELECT then pares this down to $\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\}$. The LEFT JOIN with $R$ gives $\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$. The SELECT gives $\{(1, 2, \epsilon, \epsilon)\}$. The PROJECT gives $\{(1, 2)\}$, the desired answer.


About trap states when converting DFA to regular expression

Yes, since the automaton can never accept after reading a $b$.


Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal.  It can be implemented by a finite-state transducer: it needs only finite state.

However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be universal.  It might be that examining the proof of universality of Rule 110 could yield such a system, as apparently the proof involves a reduction that goes by way of cyclic tag systems -- though personally I've never read the proof, so this is only speculation.

A side note: From Rule 110, you can construct a particular queue automaton that is universal: the queue alphabet is $\{0,1,\$\}$ and contains the state of the cellular automaton (a binary string representing the contents of each cell, followed by $\$$).  I don't know whether it'd be possible to use this to construct a specific tag system that is universal (e.g., if you can find a way to use a tag system to emulate a queue automaton).


Proving equivalence of two Turing machines

The main idea behind your proof is correct.
Note that (assuming the tape is infinitely sized on the right only) in the operator algebra of tape movements on the right-infinite tape we have identy $xR^kyL^kz = xyz$.
Using that we can prove:
$$R = R^4L^3 = (R^2)^2L^3$$
$$L = R^2L^3 $$
And since the right hand side consists only of unit moves in your model, you can do the effective moves on the left hand side. And you already know how, you replace every transition $T(x, S_i) = (y, S_o, m)$ where $m \in \{L,R\}$ with series
\begin{align}
&&T(x, S_i) &= (y, s_1(m), m'_1(m))\\
&\forall z\in \Sigma :\quad &T(z, s_1(m)) &= (z, s_2(m), m'_2(m))\\
&&&\cdots\\
&\forall z\in \Sigma :\quad &T(z, s_{k-1}(m)) &= (z, S_o, m'_k(m))
\end{align}
where $s_i$ are new temporary states and $m'_i$ are the appropriate series of moves from $\{R^2, L^3\}$.