"Process functions" in iterative and recursive depth-first search

Here is an iterative algorithm which preserves the behavior of the original recursive algorithm. The idea is to let each vertex to keep track of its next child to visit.

Iterative DFS on G starting at vertex v
    mark every vertex in G as "undiscovered"
    create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
    S.push([v,0])
    state[v] = "discovered"
    process_vertex_early(v)

    while S is not empty
        let [v, i] be the top element of S
        if i is less than the number of neighbours of v
            update that element to [v, i+1]
            let w be the i-th neighbour of v
            if w is marked "undiscovered"
                state[w] = "discovered"
                process_vertex_early(w)
                parent[w] = v
                S.push([w, 0])
                process_edge(v, w)
            else if state[w] is not "processed" or G is directed
                process_edge(v,w)
        else
            pop S
            process_vertex_late(v)
            state[v] = "processed"

There are general strategies that convert recursive algorithm/functions to iterative algorithm/functions. You can search "recursion and iteration" for more information if you have not done it yet.


So first Q1:
At first the definitions of universal language and the universal machine.
The universal language is defined as you mentioned in the question:
$$ U= \{(M,w)\:|\:\text( TM\:M\:accepts\:w)\} $$
The Universal Turing Machine on the other hand is defined as follows:
A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: It's a TM U, which you can give a random other TM M and an input w. The Universal TM then simulates the given TM M on that input w.
So the Universal Turing Machine accepts, if and only if the TM M accepts w (because it simulates M on w). It rejects, if and only if, the TM M rejects w. It halts, if and only if the TM M is halting on w (because it simulates M on w). So the Universal Turing Machine accepts the above defined Universal Language.
Now to the question: The definition of the link is a little bit misleading. The Universal TM doesn't accept HALT on default, but you can modify the Universal Turing Machine in a simple way to accept HALT: The reject states are replaced by accept states. The now modified UTM (let's call it U') is accepting HALT. Because now it always accepts, if the machine M is accepting or rejecting the input w, without getting stuck in a loop: U' is accepting, if M is halting on w.
Then Q2:
A "TM M is accepting a language L" means, that it definitely halts on w $\in$ L, but does not mean it halts on w $\notin$ L (it can loop forever). So that means, if the U' is accepting HALT, it holds for sure, only if $(M,w) \in HALT$. If $(M,w) \notin HALT$, the universal TM can halt or can loop forever. So it isn't deciding HALT, it's just accepting HALT.
(Actually it's the slightly modified Universal TM, which is accepting HALT as mentioned in answer Q1.)
Q3:
If you mean the Universal Language with L(UTM) and the halting language with L(HTM), then yes L(UTM) $\neq$ L(HTM).
Q4:
First three points you made are correct.
In the last point you have to be more exact: The (modified) UTM can accept the Halting Language, but cannot decide it. So you can check, whether M halts on w, but it may loop forever.


This reduction is the constructive proof technique to show that a subset (named safe) Tuple Relational Calculus (TRC) is less expressive than Relational Algebra (RA). The other way being true too, Safe-TRC and RA have equivalent expressive power. See Theorem 5.3.10 for instance.
The syntactic "safety" restriction ensures the domain independent property of the calculus and is needed.

In R-DBMS, SQL can be seen as the concrete (declarative) language for TRC. The RA counterpart is the procedural plan (a sequence of operations) in which an SQL expression is compiled to. So, the conversion is actually the formal description of the compilation process. Note that SQL introduces extensions like DISTINCT, ORDER BY, GROUP BY which are clearly outside the scope of TRC and RA theory.

I don't know the precise theoretical complexity of the conversion, but clearly it has to be "cheap". Photon Kolaitis states that it is linear.

I'm not aware of a proof-of-concept implementation of this algorithm.


DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }

Let $w=w_1\dots w_n$ be any word in $\{a,b\}^*$. For $i=0,\dots,n$ consider the values $d_i(w):=|w_1\dots w_i|_a - |w_{i+1}\dots w_n|_b$. We can prove

$d_0(w) = - |w|_b \le 0$,
$d_n(w) = |w|_a \ge 0$,
$d_{i+1}(w) = d_i(w) + 1$ for $i=0,\dots,n-1$.

This implies that there must be some $i$ with $d_i(w) = 0$, and therefore $w\in L$. So $L=\{a,b\}^*$.


There are many ways of accomplishing this. Consider SAT for example. Let SAT$_p$ denote a YES instance of SAT with $n$ clauses, where $p$ is the smallest prime factor of $n$. Clearly $\{ \mathrm{SAT}_p : p \text{ prime} \}$ is a partition of SAT. SAT$_p$ is clearly in NP. To show that it is NP-hard, we reduce from SAT. Given an instance of SAT having $n$ clauses, with add $m$ times the clause $x \lor y \lor z$ ($m$ to be chosen later so that $p$ is the smallest prime factor of $n+m$), where $x,y,z$ are new variables. The new instance is satisfiable iff the original one is, and by definition $p$ is the smallest prime factor of $n$. It remains to define $m$ and show that the reduction can be done in polynomial time (this depends only on the value of $m$ compared to the value of $n$).

Let $P$ be the product of all primes at most $p$. We will choose $m$ so that $n + m \equiv p \pmod{P}$. Clearly some $p < P$ fits the bill. I leave the reader to show that $p$ is the smallest prime factor of $n + m$.


Probabilities of duplicate mail detection by comparing notes among servers

If a given server receives $m \leq M$ copies, it does not receive $M-m$ copies. Also, there are many ways to pick $m$ messages out of $M$; you have to consider all of them. Furthermore, important assumptions are that

"randomly" means "uniformly at random", that is the probability that any given copy goes to any given server is $\frac{1}{N}$, and that
each copy is routed independently of its siblings, that is we have independent random events for the individual copies.

This is all you need to piece together the probability $\operatorname{Pr}(S_i = m)$ that server $i$ receives $m$ messages.

   If you put the above together, you get

 $\qquad \displaystyle \operatorname{Pr}(S_i = m) = \binom{M}{m} \left(\frac{1}{N}\right)^m \left(1 - \frac{1}{N}\right)^{M-m}$

 for $S_i$ being the number of copies the $i$-th server receives, $1\leq i \leq N$. You should recognize this kind of probability weight.

 If you have doubts that this is correct, run some simulations (not a proof!).

Now it is easy to compute $\operatorname{Pr}(S_i \geq 2) = 1 - \operatorname{Pr}(S_i = 1) - \operatorname{Pr}(S_i = 0)$.

   When using the derived weight in other calcuations, keep in mind that the $S_i$ are not independent because $\sum_{i=1}^N S_i = M$. The underlying probability distribution is the well-studied multinomial distribution.


Proof that dead code cannot be detected by compilers

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:

Run M on input x;
print "Finished running input";

If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run forever, then we need to keep the print statement. Thus, if we have a dead-code remover, it also lets us solve the Halting Problem, so we know there can be no such dead-code remover.

The way we get around this is by "conservative approximation." So, in my Turing Machine example above, we can assume that running M on x might finish, so we play it safe and don't remove the print statement. In your example, we know that no matter which functions do or don't halt, that there's no way we will reach that print statement.

Usually, this is done by constructing a "control-flow graph". We make simplifying assumptions, such as "the end of a while loop is connected to the beginning and the statement after", even if it runs forever or runs only once and doesn't visit both. Similarly, we assume that an if-statement can reach all of its branches, even if in reality some are never used. These kinds of simplifications allow us to remove "obviously dead code" like the example you give, while remaining decidable.

To clarify a few confusions from the comments:

  Nitpick: for fixed M, this is always decidable. M has to be the input

As Raphael says, in my example, we consider the Turing Machine as an input. The idea is that, if we had a perfect DCE algorithm, we would be able to construct the code snippet I give for any Turing Machine, and having a DCE would solve the halting problem.

  not convinced. return as a blunt statement in a no-branch straight forward execution is not hard to decide. (and my compiler tells me it is capable of figuring this out)

For the issue njzk2 raises: you are absolutely right, in this case you can determine that there is no way a statement after the return can be reached. This is because it's simple enough that we can describe its unreachability using control-flow graph constraints (i.e. there are no outgoing edges out of a return statement). But there is no perfect dead code eliminator, which eliminates all unused code.

  I don't take input-dependent proof for a proof. If there exists such kind of user input that can allow the code to be finite, it's correct for the compiler to assume that following branch is not dead. I can't see what are all these upvotes for, it's both obvious (eg. endless stdin) and wrong.

For TomášZato: it's not really an input dependent proof. Rather, interpret it as a "forall". It works as follows: assume we have a perfect DCE algorithm. If you give me an arbitrary Turing Machine M and input x, I can use my DCE algorithm to determine whether M halts, by constructing the code snippet above and seeing if the print-statement is removed. This technique, of leaving a parameter arbitrary to prove a forall-statement, is common in math and logic.

I don't fully understand TomášZato's point about code being finite. Surely the code is finite, but a perfect DCE algorithm must apply to all code, which is an infinte set. Likewise, while the code-itself is finite, the potential sets of input are infinte, as is the potential running-time of the code.

As for considering the final branch not-dead: it is safe in terms of the "conservative approximation" I talk about, but it's not enough to detect all instances of dead code as the OP asks for.

Consider code like this:

while (true)
  print "Hello"
print "goodbye"

Clearly we can remove print "goodbye" without changing the behavior of the program. Thus, it is dead code. But if there's a different function call instead of (true) in the while condition, then we don't know if we can remove it or not, leading to the undecidability.

Note that I am not coming up with this on my own. It is a well known result in the theory of compilers. It's discussed in The Tiger Book. (You might be able to see where they talk about in in Google books.


Learning the activation function in a neural network?

Monotonicity is necessary! A neuron (perceptron) is either activated or not activated given an input.  If you're trying to learn "red" and red should activate the neuron; the more red it's the most likely it should be activated (This monotonic gradient is what this activation function represents).  If at certain redness it activates but at more redness it deactivates it makes no sense e.g. it can't learn red (The case for non-monotonic functions).

That they're differentiable functions makes it practical for the back propagation algorithm.

What they explain in your linked article is that they're trying to better approximate other functions e.g. sinusoidal.  They're not trying sinuosoidal as an activation function.
They're combining several monotonic functions to create yet another monotonic function, that is also differentiable.


Alternative way of proving a language is $NP$

It depends on exactly what kind of reduction you're using.  Assuming that you mean a polynomial-time many-one reduction (also called "mapping reductions") then, yes, if $A$ reduces to $B$ and $B\in\mathrm{NP}$, then $A\in\mathrm{NP}$, also.  This was probably proven to you when you started to study reductions between $\mathrm{NP}$ problems.

If you mean polynomial-time Turing reduction, it's an open problem whether $A\in\mathrm{NP}$.  This corresponds to the question of whether $\mathrm{NP} = \mathrm{P^{NP}}$.

If you don't know what kind of reduction you mean, you should check with your teacher, but it's probably many-one reductions.  Those are the ones that are most commonly used with respect to problems in $\mathrm{NP}$.


4 Vertex Cover Problem is not NP Complete why?

If your graph has $n$ vertices, there are $O(n^4)$ possible subsets of $4$ vertices. Given one such subset, it is easy to check if it is a cover in $O(n^2)$ operations, by inspecting every edge and verifying whether it has an endpoint in the given subset.
Thus, in $O(n^6)$ operations we can check all possibilities.


When do structural hazards occur in pipelined architectures?

In a scalar implementation, a structural hazard can exist if specific execution hardware is not fully pipelined.  For some operations (e.g., multiplication and especially division) the cost of implementing full pipelining may not be considered worthwhile for the expected frequency of the operation.

In a superscalar implementation, a structural hazard may exist because not every execution unit can perform every operation.  E.g., supporting initiating execution of four memory operations or four multiplications every cycle would be relatively expensive when limited to four-wide issue given that a different type of operation is likely to be available.

Register file read and write port limits can also introduce structural hazards.  Although it is possible to provide enough read and write ports to support the worst case, the costs of register file ports to satisfy the worst case (even with the benefit in design complexity of not having to specially handle exceptional cases) can be considered not worth the benefits when the bad cases are sufficiently rare or non-critical.  E.g., some out-of-order implementations use operand capture (grabbing operands that become available between the time the operation enters the scheduler and the time it is scheduled for execution) and provide fewer register read ports than required for full width operation (whether operands available earlier are read when the operation enters the scheduler or when the operation is scheduled for execution).

(Even for an in-order implementation, result-forwarding and the use of operations with a single register source operand could make supporting four register read ports for two-way issue less necessary.)

Similarly, banking is often used for caches (and has been proposed for register files).  E.g., in the common case, two accesses are unlikely to map to the same bank out of 16 banks.
Banking storage is substantially less expensive than adding access ports.  The potential for bank conflicts represents a structural hazard.


The proposition states that if any of the four statements holds, then the other three also holds. This gives in total 12 different theorems. For the proof, you can use truth tables or the axioms of Boolean algebra.

What the comment is trying to explain is that, say, $xy=x$ isn't universally true (consider $x=0,y=1$). However, if $xy=x$ then also $x+y=y$, and vice versa. This is in contrast to identities such as $x+x=x$, which always hold (for all values of $x$).


simple but (seemingly?) tricky recurrence

Let us attempt to solve the easier recurrence $T(2n) = T(n) \log T(n)$. Define $S(m) = \log T(2^m)$. Then $S(m+1) = S(m) + \log S(m)$. Let us heuristically convert this into a differential equation: $S' = \log S$. The solution to this equation is $S = \mathrm{li}^{-1} + C$, where $\mathrm{li}$ is the logarithmic integral. Roughly speaking, $\mathrm{li}(x) \approx x/\log x$, and so $\mathrm{li}^{-1}(x) \approx x\log x$. This heuristic implies that $S(m) \approx m \log m$, and so $T(n) \approx \exp \Theta(\log n \log \log n)$. Of course, at this point this is just an educated guess.

As a sanity check, suppose that $T(n) = \exp (\log n \log \log n)$, where all logarithms are base 2. Then
$$
\begin{align*}
T(n) \log T(n) &= \exp (\log n \log \log n) \log n \log \log n \\ &=
\exp (\log n \log \log n + \log \log n + \log \log \log n) \\ &=
\exp (\log (2n) \log \log n + \log \log \log n).
\end{align*}
$$
This is quite similar to $T(2n) = \exp (\log (2n) \log \log (2n))$ (though not the same).


Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer?

You can look at how one of the existing DRAM simulators work. Consider, for example, Ramulator, which is a popular academic DRAM simulator. Ramulator Models main memory as a tree of nodes, where the root node represents a memory channel and lower nodes represent ranks, bank groups (supported in DDR4), banks, rows, and columns. For the DRR4 and DRR3 protocols, these levels are defined in the source code here and here, respectively. Therefore, the physical row buffer of each chip of the same bank are actually treated as a single row buffer whose state is maintained using a single value.


How to define an approximation algorithm when it fails?

The usual way out in such circumstances is bicriteria approximation algorithms. Suppose that given a set of possible solutions $S$, a constraint function $f$, and an objective function $g$, your goal is to find a solution $x \in S$ such that $f(x) \leq 1$ minimizing $g(x)$. A bicriteria approximation algorithm will find a solution $x \in S$ such that $f(x) \leq \alpha$ and $g(x) \leq \beta \mathrm{OPT}$, where OPT is the optimal solution to the original problem.

The quality of bicriteria approximation algorithms is thus measured by two parameters. The parameter $\beta$ corresponds to the approximation ratio, and $\alpha$ controls by how much the solution violates the constraints.


Beginner Question Concerning the Logic of a Very Simple Correctness Proof

Both of the assumptions you mention are "local" in the sense that they are a subclaim in the proof and are not part of the conditions of the theorem. You can also see them as the definition of a local variable $i$, an equivalent formulation of the two assumptions would be

Let $i$ be such that $A'[i]<A'[k]$ and $1\leq i \leq n$.

Let $i$ be such that $1\leq i \leq k$.

The proof counts the number of values of $i$ for which these statements hold, which shows that the postcondition is satisfied.

I think part of your confusion follows from some implicit language in these paragraphs, so I will rewrite one of them in full to be more explicit. The first paragraph from the book reads:

Suppose $A'[i] < A'[k]$ for some $i$, $1 \leq i \leq n$. Then $i < k$, for if $k < i$, $A'[k] > A'[i]$ violates the postcondition of Sort. Hence, there are fewer than $k$ elements of $A'$ , and hence of $A$, with value less than $A' [k]$.

A more explicit phrasing is as follows:
Let $i$ be such that $A'[i]<A'[k]$ and $1\leq i \leq n$. If $k<i$, then $A'[i]<A'[k]$ contradicts with the postcondition of Sort, so $i\leq k$. If $i=k$, then $A'[i]=A'[k]$, which contradicts with our definition of $i$.
So, we have shown that if $A'[i]<A'[k]$ and $1\leq i \leq n$, then $i<k$. This means that the number of elements of $A'$ with value strictly less than $A'[k]$ is strictly fewer than $k$. Since $A$ is a permutation of $A'$, there are fewer than $k$ elements of $A$ strictly less than $A'[k]$. Since $A'[k]$ is the return value of the algorithm, the first part of the postcondition of Select is satisfied.
The overall structure of the second paragraph is similar, so you should be able to grasp it if you can understand the first.


sequence of problems that take $\Theta(n^k)$ for increasing $k$?

You leave the computational model open. I will assume that the question refers to random access machines (RAMs), as that is customary when one asks for the actual exponent in polynomial time.

Let $P_k$ be the set of (encodings of) RAMs $M$, such that $M$ halts in at most $|M|^k$ steps using at most the initial $|M|^k$ memory cells. A universal RAM can solve $P_k$ in $O(n^k)$.

On the other hand, $P_k$ is the universal problem for $DTIME(n^k)$ (in the RAM model and under linear time reductions). As a special case of the RAM version of the time hierachy theorem, a simple diagonalization shows that all algorithms for $P_k$ have running time $\Omega(n^k)$. Thus the complexity of $P_k$ is $\Theta(n^k)$ as asked.

The tightness heavily relies on the computational model. The Turing machine version of the time hierarchy theorem has a $\log n$ gap. Let $P'_k$ be the set of (encodings of) Turing machines $M$, such that $M$ halts in at most $\frac{|M|^k}{\log n}$ steps. Then $P'_k$ can be solved in $n^k$ time by a universal Turing machine and all algorithms have running time $\Omega(\frac{n^k}{\log n})$. I suspect this is the best one can do.

[EDIT]

In a comment, you ask for more conventional problems, like graph problems or logic.

First, let me point out how $k$-Clique (as suggested in the answer) does not seem like a good candidate. If we could prove that $k$-Clique requires time $\Omega(n^k)$ (or $\Omega(n^{f(k)})$ for some unbounded $f$), we have implied that Clique is not in P. And thus that P is different from NP. That is not likely to be easy. The same holds for slices of any other problem that we know to be in NP, or in some other classes like PSPACE that are unknown to be different from P.

Every problem can be rephrased as a graph problem, by encoding the input as a graph. I don't know if you would call a graph version of $P_k$ conventional. I wouldn't call it natural.

As for logic, I can provide an example. It is not boolean logic however, and there is a gap between the lower and upper bound. The example is based on the Immerman-Vardi theorem. Let $\mathcal L$ be first-order logic extended by least-fixed-point operators. Let ${\mathcal L}^k$ denote the fragment where only $k$ first-order variables are allowed. It is permitted to re-use variables, so the restriction is that each subformula has at most $k$ free variables. The Problem $M_k$ is the model-checking problem for ${\mathcal L}^k$, that is on input of a formula $\varphi\in{\mathcal L}^k$ and a structure $\mathfrak A$ of matching vocabulary, the task is to decide whether $\mathfrak A\models\varphi$, that is whether $\varphi$ is true in $\mathfrak A$.

$M_k$ can be solved in time $O(n^{2k+1})$. On the other hand, for some constant $c$, $M_{3k+c}$ is hard for $DTIME(n^k)$ (where we also require an $n^k$ bound on the contents of memory cells). I believe $c=2$ suffices. From diagonalization we obtain that $M_{3k+c}$ requires time $\Omega(n^k)$,
so $M_k$ requires time $\Omega(n^{\frac{k-c}3})$. The bound is not tight in the sense of $\Theta(n^{k'})$ for some $k'$, but at least we have $n^{\Theta(k)}$.


What is the polynomial time reduction between these two Hamiltonian cycle problems?

First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky.
Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2).
algorithm for P1 with input G = (V,E):
  E' = {} # edges of "Hamilton Cycle"
  run subroutine for P2 on G
  if there is no Ham. Cycle:
    report that there is no Ham. Cycle
  for e in E:
    run P2 on (V,E - {e})
    if (V,E - {e}) contains "Hamilton Cycle":
      E <- E - {e}   # remove e
    else:
      E' <- E' + {e} # add e to cycle
  return E'

It uses the procedure for P2 $O(|E|)$ times, thus we obtained a polynomial reduction.


Example of a superword w such that v^2 isn't its subword

There is a dedicated page on "square-free words" on wikipedia here, with references. As you can see, there is an exemple of a square-free word on a three lettre alphabet.


Minimum path between two vertices passing through a given set exactly once

The following answers the variant which requires passing through the set exactly once.

Make two copies of the graph. Remove all edges incident to two vertices of $A$. Orient all edges incident to $A$ in the first copy toward $A$, and all edges incident to $A$ in the second copy from $A$; other edges are bidirectional. Connect both copies of each vertex in $A$ with a zero-weight edge going from the first copy to the second copy. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

Using Dijkstra's algorithm, the complexity of this approach is $O(E+V\log V)$. In comparison, the trivial algorithm that tests all vertices in $|A|$ one at a time needs to run Dijkstra's algorithm $|A|$ times, unless the graph is unweighted, in which case one can use BFS instead in time $O(E|A|)$.

Here is an alternative solution, using only undirected graphs. Start by deleting all edges inside $A$. Add $M$ to the weight of all other edges incident to $A$, where $M$ is larger than the sum of all weights in the graph. Run Dijkstra's algorithm twice to find the shortest path between $S$ and any vertex in $A$, and between $T$ and any vertex in $A$; in both cases, the shortest path passes through no other vertex in $A$, due to our adjustment of the weights. Now go over all vertices $A$ and find the shortest path from $S$ to $T$ via a vertex in $A$.

This algorithm also runs in time $O(E+V\log V)$.

The following answers the variant which requires passing through the set at least once.

Make two copies of the graph. Connect both copies of each vertex in $A$ with an edge of zero weight. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

The complexity is $O(E+V\log V)$, or $O(E+V)$ if the original graph is unweighted (in this case, we modify the construction so that the parallel $A$-edges have unit weight; this is harmless in terms of computing the shortest path).


Does there exist a Turing complete typed lambda calculus?

Yes, sure. Many typed lambda calculi accept only strongly normalizing terms, by design, so they cannot express arbitrary computations. But a type system can be anything you like; make it broad enough, and you can express all deterministic computations.

A trivial type system that encompasses a Turing-complete fragment of the lambda calculus is the one that accepts every term as well-typed (with a top type).
$$\dfrac{}{\Gamma \vdash M : \top}$$

More practically, statically typed functional programming languages have at their core a typed lambda calculus which allows a fixpoint combinator as well-typed. For example, start with the simply typed lambda calculus (or the ML type system or system F or any other type system of your choice) and add a rule that makes some fixpoint combinator like $\mathbf{Y} = \lambda f. (\lambda x. f (x\,x)) (\lambda x. f (x\,x))$ well-typed.
$$
  \dfrac{\Gamma \vdash f : T \rightarrow T}
        {\Gamma \vdash \mathbf{Y}\,f : T}
  \qquad
  \dfrac{\Gamma \vdash f : T \rightarrow T}
        {\Gamma \vdash (\lambda x. f (x\,x)) (\lambda x. f (x\,x)) : T}
$$
The rules as presented above are rather clumsy, as they make terms like $\mathbf{Y}\,f$ well-typed even though their constituents are not well-typed — they are not fully compositional. A simple fix is to add a fixpoint combinator as a language constant and provide a delta rule for it; then it is a simple matter to have a type system and reduction semantics with type preservation. You do get away from the pure lambda calculus into the realm of lambda calculus with constants.
$$\begin{gather*}
  \dfrac{}{\Gamma \vdash \textbf{fix} : (T \rightarrow T) \rightarrow T} \\
  \textbf{fix}\,f \to f (\textbf{fix}\,f) \\
\end{gather*}$$

Sticking to the pure lambda calculus, an interesting type system is the lambda calculus with intersection types.

$$
\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \wedge T_2}
      (\wedge I)
\qquad\qquad
\dfrac{}
      {\Gamma \vdash M : \top}
      (\top I)
$$

Intersection types have interesting properties with respect to normalization:

A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
A lambda-term admits a type not containing $\top$ iff it has a normal form.

See Characterization of lambda-terms that have union types for an insight as to why intersection types have such a remarkable scope.

So you have a type system that defines a Turing-complete language (since every term is well-typed), and a simple characterization of terminating computations. Of course, since this type system characterizes normalization, it is not decidable.

A remark on the rule names $(\top I)$ and $(\wedge I)$: they have no formal meaning, but they are chosen deliberately. the $I$ stands for “introduction”, because these are introduction rules — they introduce the symbol ($\wedge$ or $\top$) into the type below the line. Dually, you'll find elimination rules, when a symbol appears above the line but not below. For example, the rule to typecheck a lambda expression in the simply-typed lambda calculus is the introduction rule for $\rightarrow$, and the rule to typecheck an application is the elimination rule for $\rightarrow$.


Suppose that a memory of size $M$ is divided into blocks of size $B$:

Block 0 consists of cells $0,\ldots,B-1$.
Block 1 consists of cells $B,\ldots,2B-1$.
Block 2 consists of cells $2B,\ldots,3B-1$.
Block $k$ consists of cells $kB,\ldots,(k+1)B-1$.

The "linear address" of a cell is its address in the memory.

Another way of addressing it is by giving which block it belongs to, and what is its offset inside the block. For example, linear address $B+2$ corresponds to block 1, offset 2.

Given a block and an offset, you can easily compute the corresponding linear address; and given the linear address, you can easily compute the block and the offset. Rather than spelling out the arithmetic, I challenge you to come up with the requisite formulas. Using these formulas, you can complete your exercise.


Why do we need the valid-invalid bit in a page table?

As David Richerby says, it’s not clear what you don't understand.
Most of my answer here has already been presented in answers (or comments)
to the questions you linked to.

I’ll admit, though, that the Operating System Concepts book
is probably not as clear as it should be.

The book (going back to Figure 8.6
(Hardware support for relocation and limit registers) on page 361)
suggests that the processor knows the maximum user virtual address
for a context (process),
so if the process tries to access an address above this limit,
the access fails with an addressing error.
This concept seems to erode over the following pages;
for example, Section 8.4.2 (Segmentation Hardware) (pages 365 and 366)
introduces a limit field in each segment table entry,
but waves its hands over the question
of specifying the maximum virtual address
(and, correspondingly, the length of the entire segment table).

I would argue that Figure 8.9 (Example of segmentation), on page 367:

            [images copied from this 944-page PDF of the book]
adds to the confusion:

It’s clearly not to scale.
It says that Segment 0 is 1000* bytes long — both explicitly,
in the segment table, and in the map of physical memory $(2400-1400=1000)$.
Likewise, it says that Segment 4 is 1000 bytes long — both explicitly,
in the segment table, and in the memory map $(5700-4700=1000)$.
But Segment 4 is clearly larger than Segment 0 in the memory map,
while Segment 0 is clearly larger than Segment 4
in the nebulous logical address space on the left.
Why are the segments colored inconsistently?
Segments 2 and 3 are gray on the left and white on the right.
Does this mean something?
How do we know which “segment” a given address is in?
How do we know the length of the segment table?

Wandering Logic addresses the fourth bullet with their statement,
“Typically the page table is a tree of fixed size pages.”
(emphasis added).
So, looking at Figure 8.15 (“Valid (v) or invalid (i) bit in a page table”),
excerpted here,

it might be that the system has no way of knowing
which pages are valid (0-5) and which ones are invalid (6 and 7)
other than marking the entries for the invalid pages with an invalid flag.

But also, while Figure 8.9 is somewhat confusing,
it also contains the kernel of part of the answer to your question:
The user virtual address space may be
segmented / fragmented / sparse / discontiguous.
In other words, just because the maximum virtual address is $N$,
that doesn’t mean that every $M$ such that $0 \le M \le N$
is a valid address.
Just as the segments are explicitly shown as being discontiguous
(and out of order) in the physical memory (on the right),
and are implicitly shown as disassociated in the logical address space
on the left, with order being irrelevant**,
they may actually be discontiguous in the logical address space.
In fact, the book (somewhat) explicitly (but not clearly) tells us
that they are discontiguous,
in the last paragraph of Section 8.4.2:

  A reference to byte 1222 of segment 0
  would result in a trap to the operating system,
  as this segment is only 1,000 bytes long.

So the 1222nd byte of the logical address space
is not the 222nd byte of segment 1,
but rather falls in the gap between segment 0 and segment 1.
If we assume that the segments occur in numeric order
in the logical address space with addresses at multiples of 2000,
starting at 0,
then the complete (logical and physical) segment map/table
might look something like this:

segment               logical                                  physical
   #    | base  limit          range       ...     base  limit          range
--------------------------------------     ...     ----------------------------
   0    |    0   1000           0-999              1400   1000        1400-2399
   1    | 2000    400        2000-2399             6300    400        6300-6699
   2    | 4000    400        4000-4399             4300    400        4300-4699
   3    | 6000   1100        6000-7099             3200   1100        3200-4299
   4    | 8000   1000        8000-8999             4700   1000        4700-5699

(I’m sorry, but I just don’t see any reason
to display the limit to the left of the base, as the authors do.)
So, pretending that the page size is 100 bytes,
using a format inspired by Figure 8.15,
we would get a page table that looks like this:

virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical
page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #
   0   |   14    ┃   18   | invalid ┃   36   | invalid ┃   54   | invalid ┃   72   | invalid
   1   |   15    ┃   19   | invalid ┃   37   | invalid ┃   55   | invalid ┃   73   | invalid
   2   |   16    ┃   20   |   63    ┃   38   | invalid ┃   56   | invalid ┃   74   | invalid
   3   |   17    ┃   21   |   64    ┃   39   | invalid ┃   57   | invalid ┃   75   | invalid
   4   |   18    ┃   22   |   65    ┃   40   |   43    ┃   58   | invalid ┃   76   | invalid
   5   |   19    ┃   23   |   66    ┃   41   |   44    ┃   59   | invalid ┃   77   | invalid
   6   |   20    ┃   24   | invalid ┃   42   |   45    ┃   60   |   32    ┃   78   | invalid
   7   |   21    ┃   25   | invalid ┃   43   |   46    ┃   61   |   33    ┃   79   | invalid
   8   |   22    ┃   26   | invalid ┃   44   | invalid ┃   62   |   34    ┃   80   |   47
   9   |   23    ┃   27   | invalid ┃   45   | invalid ┃   63   |   35    ┃   81   |   48
  10   | invalid ┃   28   | invalid ┃   46   | invalid ┃   64   |   36    ┃   82   |   49
  11   | invalid ┃   29   | invalid ┃   47   | invalid ┃   65   |   37    ┃   83   |   50
  12   | invalid ┃   30   | invalid ┃   48   | invalid ┃   66   |   38    ┃   84   |   51
  13   | invalid ┃   31   | invalid ┃   49   | invalid ┃   67   |   39    ┃   85   |   52
  14   | invalid ┃   32   | invalid ┃   50   | invalid ┃   68   |   40    ┃   86   |   53
  15   | invalid ┃   33   | invalid ┃   51   | invalid ┃   69   |   41    ┃   87   |   54
  16   | invalid ┃   34   | invalid ┃   52   | invalid ┃   70   |   42    ┃   88   |   55
  17   | invalid ┃   35   | invalid ┃   53   | invalid ┃   71   | invalid ┃   89   |   56
                                                                              90   | invalid
                                                                              91   |    ︙

(Consider all entries that have physical page numbers
(not flagged “invalid”) to be flagged “valid” —
I left that out to save space.)
See also What is stored in the first memory address? Why can’t I
print the contents?, where Scott provides an answer
that includes a hypothetical (example)
virtual (logical) → physical memory map

Maybe Silberschatz, et. al., should have used something like
that instead of their Figure 8.9.
(Their Figure 8.17 comes close, but, IMO,
it is too complex and confusing,
and not really the same thing in any case.)

Also, as Pseudonym points out,
pages that are valid addresses in the process's virtual address space
might not be OK for the CPU to access:

A page might be swapped/paged out to secondary storage (disk or SSD),
or it might be located in a memory-mapped file.
The operating system would need to trap the access
so it can fetch the page from secondary storage.

[Downvoter also commented:
“What about pages swapped out to disk?”]

A page might have been allocated to the process,
but not yet zero-filled.
The operating system would need to trap an access to such a page
so it can set it to all zeroes.
(Note: I’m not sure the OS would use an “invalid” flag for that;
it should be possible to flag the entry as “valid”,
but turn off read, write, and execute permissions,
so any access to any address in the page will cause a trap to the OS.)
The conventional wisdom is that fork() copies a process’s memory image.
In reality, it probably copies the page table,
so both parent and child are pointing to the same physical memory.
If/when the child process does an exec(),
it relinquishes its claim on the memory, and everything is cool.
But you don’t want it to appear (behave)
as though the processes are sharing memory,
so, as soon as either process makes any attempt to modify any memory,
the kernel wants to intercede and make a copy of the page
(so each process can have its own copy).
This is the “copy-on-write” paradigm that Pseudonym refers to.
(Although, again, I’m not sure the OS would use an “invalid” flag for that;
it should be possible to flag the entry as “valid”,
but turn off write permission,
so any write access to any address in the page will cause a trap to the OS.)

So, the answer to your question,

  Why do we need a validity bit
  when the process has no way of addressing memory outside its page table?

is that there can be addresses within the process’s page table
that are not valid addresses to access.

  Why do we [also] need a valid-invalid bit?

Good question.
As Silberschatz’s Figure 8.15 suggests,
it might be good enough just to set the physical page address
(or frame number) to 0.
But, notwithstanding the issue raised in the What is stored
in the first memory address? Why can’t I print the contents? question
(which Pseudonym also mentions: “The first few pages
of the address space of a process are deliberately left invalid
so that any attempt to access memory through a NULL pointer
is trapped by the operating system.”),
page 0 is a valid physical page address.
To say that “0” means “invalid”
would make page 0 of physical memory inaccessible — even to the OS.
Pretty much by definition, anything that can fit into a field
that is sized to a physical page number
will be a (theoretically) valid page number.
Sure, you could use an all-ones value (e.g., 0xFFFFFFFF),
but even that could result in a situation
where a machine that had 128 terabytes*** of physical memory
might be unable to access the last 512 or 1024 bytes; that would be silly.

Consider also what Daniel Jour points out:

  Because the [page number] entry isn't used by the MMU
  [if the entry is flagged as invalid,]
  the operating system can use it to store its own information,
  like for example a reference to the filesystem entity
  (for example inode number)
  where it stored the data to free the main memory for some other processes
  (it swapped that page out).

So that’s why a page table entry contains a physical page number
and a valid/invalid flag.

___________________
*  Apparently these numbers are decimal! —
see the last paragraph of Section 8.4.2 (Segmentation Hardware).
This is, of course, totally unrealistic, but I guess it doesn't matter
as long as the numbers are handled consistently.
**  which is nonsense — they are numbers, so they have an order.
*** I'm pulling a large number out of my hat here;
I haven’t checked that the math on this exactly makes sense.


It depends what you mean by "arithmetic".

It's a fairly well-known result that Peano arithmetic (PA) is powerful enough to model Turing machines.

There are other models of arithmetic, such as Presburger arithmetic (which is strictly weaker; it's essentially PA without multiplication) and real closed fields with a partial order, which are known to be decidable.


Design PDA or CFG for the following language

There is no such grammar: the language is not context-free.

$L\cap a^*b^*ca^*b^* = \{a^nb^{2m}ca^nb^m\mid m,n\ge 1\}$.


Is equivalence of a CFG and an RG undecidable?

It is undecidable whether for a given CFG $G$, $L(G)=\Delta^*$, the set of all strings (over the terminal alphabet of $G$). That answers your question, by chosing the most simple regular grammar.


The root colour of a red-black tree carries no significance. In fact, you can save memory by not encoding it. Didactically, it is meaningful to talk about a root's colour to illustrate what it means to be red or black, because it is a special case because it has no parent which is going to count it when it evaluates the sixth restriction in Wikipedia's list (that the path from a particular node to a leaf should contain the same number of black nodes).

As for your more general question about when changing a black node to a red one is allowed: a set of nodes can be repainted if afterwards, the black-height criterion is still satisfied. For example, if a row of the tree is saturated (if it is at depth $k$, there are $2^{k}$ nodes), then you can colour that row black. You may not colour only part of a (saturated or not) red row black. Another example: in the tree $1:red \rightarrow\{ 2:black, 3:black\rightarrow\{4:red, 5:red\}\}$, you can flip the colours of $\{3,4,5\}$ and still have a legal RB tree. This is true generally for subtrees of even height and alternating colours. Maybe you can think of more examples.


Given a propositional formula $\varphi(\vec{x}, \vec{y})$, consider $\psi = \exists \vec{y} \ \forall \vec{x} \ \varphi(\vec{x}, \vec{y})$.

Let
$\Delta =
\{ y_0 \leftrightarrow \top, y_0 \leftrightarrow \bot, \ldots,
y_m \leftrightarrow \top, y_m \leftrightarrow \bot \}$.
Then $\psi$ is true iff there exists $\Gamma \subseteq \Delta$ such that $\Gamma \nvDash \bot$ and $\Gamma \vDash \varphi(\vec{x}, \vec{y})$.

Therefore the problem is $\Sigma^\mathsf{P}_2$-hard.
$\mathsf{DP} \subseteq \Delta^\mathsf{P}_2$, so unless $\mathsf{PH}$ collapses the problem is not in $\mathsf{DP}$.


splitting of people betwen groups with group prioritiy list per person

If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching.
You might also be interested in stable marriage algorithms, which have a different notion of fairness.


Efficient Implementation of Boolean Lattice-Esque Operation

I believe the desired $A'$ is given by
$$A' = \{T : \forall T' . T \subseteq T' \implies T' \notin \cup_i f(A_i)\}.$$
Here is how to compute $A'$ in linear time from the $A_i$'s.  Basically, we want to include the set $T$ if: (1) for all $i$, there exists $T_i \in A_i$ such that $T_i \subseteq T$ and (2) there exists $j$ such that $T \in A_j$.  You can find those sets as follows:

For each $T \in A_1 \cup \cdots \cup A_k$:

Set flag := true.
For each $i := 1,2, \dots, k$:

If $\not\exists T_i \in A_i$ such that $T_i \subseteq T$, set flag := false.

If flag := true, output $T$.

Naively, this seems likely to take quadratic time or more.  However, since you're working in $Y_2$, there is a more efficient algorithm.  For each $i$, build a hashtable (an index) that, given $T$, lets you check whether $T \in A_i$.  Then, you can implement the algorithm above as:

For each $T \in A_1 \cup \cdots \cup A_k$:

Set flag := true.
For each $i := 1,2, \dots, k$:

If $|T|=2$: suppose $T=\{u,v\}$; if $T \notin A_i$ and $\{u\} \notin A_i$ and $\{v\} \notin A_i$, then set flag := false.
Otherwise if $|T|=1$: if $T \notin A_i$, then set flag := false.

If flag := true, output $T$.

This can now be implemented in time proportional to $k \sum_i |A_i|$.  I don't know whether this is efficient enough for you.
I think for this to work corretly in all cases, you might need to first convert each avoidance set $A_i$ into canonical form.  The canonical form of avoidance set $A$ is an avoidance set $A^*$ with the smallest number of sets such that $f(A^*)=f(A)$.  When working in $Y_2$ you can compute the canonical form with the following rules:

Rule 1: If $\{u,v\} \in A$ and $\{u\} \in A$ or $\{v\} \in A$, delete $\{u,v\}$ from $A$.

Rule 2: If $\{x,u\} \in A$ for each $x \in \{1,\dots,n\}\setminus\{u\}$, then add $\{x\}$ to $A$ and remove all $\{x,u\}$ from $A$.

You can enforce Rule 1 with a linear scan over $A$; and then you can enforce Rule 2 with a simple linear-time graph algorithm (build the undirected graph with an edge for each $\{u,v\} \in A$; check the degree of each vertex; apply Rule 2 to each vertex with degree $n-1$).  So, at least when working in $Y_2$, you can convert an avoidance set to canonical form in linear time.  I haven't tried to think about a generalization to arbitrary $Y_i$.


Finding vertices of a maximum clique in polynomial time

You first give it $(G,k)$, and if it says yes, you do the following.  You pick an arbitrary vertex $v$ and call your oracle with $(G-v,k)$.  If the oracle says yes, throw away $v$ and forget about it.  If it says no, then $v$ is in every clique of size at least $k$.  Output $v$ and decrease $k$ by one and lather, rinse, repeat.


How exactly is this equation for insertion sort time complexity solved so that it shows it is linear?

So you question is how to go from:

T(n)= c1(n)+c2(n−1)+c4(n−1)+c5(n−1)+c8(n−1)

to

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)

Step 1 (Expand the statement):

T(n)= c1(n)+c2(n)−c2+c4(n)−c4+c5(n)−c5+c8(n)−c8

Step 2 (Group similar elements):

T(n)= c1(n)+c2(n)+c4(n)+c5(n)+c8(n)−c2-c4-c5-c8

Step 3 (Find the factors):

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)


You can make any language homoiconic. Essentially you do this by 'mirroring' the language (meaning for any language constructor you add a corresponding representation of that constructor as data, think AST). You also need to add a couple of additional operations like quoting and unquoting. That's more or less it.

Lisp had that early on because of its easy syntax, but W. Taha's MetaML family of languages showed that it's possible to do for any language.

The whole process is outlined in Modelling homogeneous generative meta-programming. A more lightweight introduction to the same material is here.


Why is the node with the greatest DFS post-order number not necessarily a sink?

If your graph is strongly connected, there is no sink, so I guess that answers your question...


How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows:
$$
Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c.
$$

Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back:
$$
T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n).
$$


Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

Instead of simple numbering, you could spread the numbers out over a large  (constant sized) range, such as integer minimum and maximums of a CPU integer. Then you can keep putting numbers "in between" by averaging the two surrounding numbers. If the numbers become too crowded (for example you end up with two adjacent integers and there is no number in between), you can do a one-time renumbering of the entire ordering, redistributing the numbers evenly across the range.
Of course, you can run into the limitation that all the numbers within the range of the large constant are used. Firstly, this is not a usually an issue, since the integer-size on a machine is large enough so that if you had more elements it likely wouldn't fit into memory anyway. But if it is an issue, you can simply renumber them with a larger integer-range.
If the input order is not pathological, this method might amortize the renumberings.
Answering queries
A simple integer comparison can answer the query $\left(X \stackrel{?}{<}Y\right)$.
Query time would be very quick ( $\mathcal{O}\left(1\right)$ ) if using machine integers, as it is a simple integer comparison. Using a larger range would require larger integers, and comparison would take $\mathcal{O}\left(\log{|integer|}\right)$.
Insertion
Firstly, you  would maintain the linked list of the ordering, demonstrated in the question. Insertion here, given the nodes to place the new element in between, would be $\mathcal{O}\left(1\right)$.
Labeling the new element would usually be quick $\mathcal{O}\left(1\right)$ because you would calculate the new numeber easily by averaging the surrounding numbers. Occasionally you might run out of numbers "in between", which would trigger the $\mathcal{O}\left(n\right)$ time renumbering procedure.
Avoiding renumbering
You can use floats instead of integers, so when you get two "adjacent" integers, they can be averaged. Thus you can avoid renumbering when faced with two integer floats: just split them in half. However, eventually the floating point type will run out of accuracy, and two "adacent" floats will not be able to be averaged (the average of the surrounding numbers will probably be equal to one of the surrounding numbers).
You can similarly use a "decimal place" integer, where you maintain two integers for an element; one for the number and one for the decimal. This way, you can avoid renumbering. However, the decimal integer will eventually overflow.
Using a list of integers or bits for each label can entirely avoid the renumbering; this is basically equivalent to using decimal numbers with unlimited length. Comparison would be done lexicographically, and the comparison times will increase to the length of the lists involved. However, this can unbalance the labeling; some labels might require only one integer (no decimal), others might have a list of long length (long decimals). This is a problem, and renumbering can help here too, by redistributing the numbering (here lists of numbers) evenly over a chosen range (range here possibly meaning length of lists) so that after such a renumbering, the lists are all the same length.

This method actually is actually used in this algorithm (implementation,relevant data structure); in the course of the algorithm, an arbitrary ordering must be kept and the author uses integers and renumbering to accomplish this.

Trying to stick to numbers makes your key space somewhat limited. One could use variable length strings instead, using comparison logic "a" < "ab" < "b". Still two problems remain to be solved
A. Keys could become arbitrarily long
B. Long keys comparison could become costly


Is Rice's Theorem equivalent to the Halting problem?

Yes, you can prove Rice's theorem by reduction from the Halting problem.  See https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem.
The reverse direction is also provable and is trivial.
In some sense all statements that true and provable are equivalent, in the sense that you can prove any by starting from any other, but that probably isn't a useful observation.


Hough transform: difference in cartesian to polar equation

There's no fundamental difference.  The difference is merely one of convention, namely, where you consider the origin to be in your $(x,y)$ coordinates.  If you consider $(0,0)$ to be in the upper-left (with increasing $y$ values corresponding to going downwards), use one formula.  If you consider $(0,0)$ to be in the lower-left (with increasing $y$ values corresponding to going upwards), use the other.  Ultimately, the two are equivalent, up to a flip of the plane (reflection across the x axis).


NP-completeness: Reduce to or reduce from?

To show a new problem $X$ is hard, you reduce from a problem of known hardness to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$.

The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-SAT instance to an instance of $X$. Given an instance of 3-SAT, you transform it into an instance of $X$, apply the efficient algorithm for $X$, and thus have solved the 3-SAT instance.


Let $P$ be the set of people and $\mathcal{S}$ be the modified multi-set of subsets. By checking if an $\mathcal{S}$-saturated matching into $P$ exists (i.e. Hall's condition) you are indeed finding a diverse group. If you are checking that some group $P$ is a putative solution the procedure is the exactly the same.

This can be done quickly via the Hopcraft-Karp algorithm (as you don't have weights over edges) or by implementing this as a Max-flow LP and using a solver. I'm willing to bet the solvers will work much faster in practice.


Let S be the set of all traces in which "11" does not appear (a safety property) and L be the liveness property defined such that if 1 appears then eventually 2 will appear after (in temporal logic: $\square( 1 \rightarrow \lozenge 2)$).
Then trace(P)=trace(S)$\cap$trace(L).


Is the number of inequivalent elementary cellular automata rules really 88?

OK! Peter de Rivaz has confirmed the number $88$ by careful analysis of the two equivalence rules, and a clever script.

Here I will try to repeat the analysis (for my own understanding) and then apply some mathematical magic.

A binary cellular automaton is denoted by a bit string $ABCDEFGH$ where the consecutive letters denote each a bit (next state) for the three bits that encode the configuration at position with its two neighbours, $xyz = 111, 110, 101, \dots, 001, 000$.

The mirror operation is the automaton in left-right reverse, meaning that the bit for $xyz$ is now at $zyx$. Thus $A$ at $111$ stays in place, but $B$ at $110$ is swapped with position $E$ at $011$. The new rule is then $AECGBFDH$. There are $64$ rules that stay unchanged under this operation. Says Wikipedia.

The complement operation is the automaton with bits swapped, meaning that the bit for $xyz$ is now the negation of bit $\bar x\bar y\bar z$, which looks rather DeMorgan to me. In words, the bits are reversed and inverted. The new rule is then $\bar H\bar G\bar F\bar E\bar D\bar C\bar B\bar A$. There are $16$ rules that stay unchanged under this operation. Says Wikipedia.

We can also combine the two rules. Mirror complement gives $\bar H\bar D\bar F\bar B\bar G\bar C\bar E\bar A$. Again there are $16$ rules unchanged under this rule. The math is easy, unchanged means $A=\bar H$,  $B=\bar D$ etc, finally leaving $4$ free variables.

Applying no operation identity keeps all $256$ bit strings unchanged. Also any combination of mirror and complement will again be one of the four above operations (but you have to convince yourself on that).

The magic is Burnside's Lemma: the number of orbits under a group $G$ of permutations of a set $S$ equals $\frac1{|G|}\sum_{\psi\in G}|\text{fix}(\psi)|$.

The number of orbits here is the number of inequivalent cellular automata. Let's check the math: $\frac14(256+64+16+16) = 352/4 = 88$. This (again) confirms the number on Wikipedia.


Solving recurrence $T(n) = T(n - 1) + n$ with substitution method


What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?

Stirling's formula shows that $\log m! = \Theta(m\log m)$. In terms of the length $n = |m|$, we get $|m!| = \Theta(n2^n)$, and so $m!$ cannot be bounded by a polynomial in $m$. A reasonable algorithm for calculating $m!$ exactly is using the formula $m! = m \cdot (m-1) \cdots 1$. This algorithm uses quasilinear time and linear space (in the output size). For estimating $m!$, you can use the asymptotic series extending Stirling's formula.

Since $m!$ grows very large, there is no real need to calculate $m!$, you can just store all relevant values in a table (a value is relevant if it can be stored as a machine integer, though if you use bignums then more values become relevant). You can find the values in such a table on the web.

Things become more interesting when you're after $\log m!$, since now a table would be too big. Fortunately, MATLAB can compute the $\Gamma$ function which satisfies $\Gamma(m+1) = m!$ (it is the unique log concave function with this property) and its logarithm $\ln \Gamma$ — use the functions gamma and gammaln.


What algorithm will tell us how to divide-up a round robin tournament into rounds?

You want the algorithm for constructing a Graeco-Latin square, or any of the algorithms described in https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm


A spanning tree, by definition, has the same vertices as the graph it spans. Since such a tree is an induced subgraph and, since trees are (by definition) connected, the graph itself must be connected.

Note this applies to any spanning tree, not just a minimal one (i.e., an MST).


CFG to CFL conversion (production rule with both left and right recursion)

Is there a general rule to convert a context-free grammar to a context-free language?

The answer depends on what you mean by "context-free language". A context-free grammar is one way to describe context-free languages, so in some sense the answer is a trivial "yes" – a context-free grammar is already a description of a context-free language.
Presumably you are interested in a more explicit description. In this case, the answer is probably "no", though it's impossible to tell unless you define your problem formally. The reason for the negative answer is the following undecidability result: given a context-free grammar over an alphabet $\Sigma$, determining whether it generates $\Sigma^*$ is undecidable.

How do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?

In mathematics, the way to know things for sure is to prove them.

Is there a way to make it either in left or right recursion so that it is easier to understand the structure?

If a grammar contains only left-recursion or only right-recursion, then it is a left-regular grammar or a right-regular grammar, respectively (actually, whether this is true depends on what you mean by left-recursion and right-recursion, so I am making a guess). (Another common term is left-linear/right-linear grammar.) Such a grammar generates a regular language. Given that it is undecidable whether a given context-free grammar generates a regular language, there is no simple transformation that can change an arbitrary context-free grammar into one with only left-recursion or only right-recursion.
A grammar mixing left-linear and right-linear rules is known as linear; such grammars describe linear languages, a sub-class of all context-free languages which contains non-regular languages such as $\{a^nb^n \mid n \geq 0\}$, generated by $S \to aT \mid \epsilon, \, T \to Sb$.
It seems that even determining whether a given linear grammar describes a regular language is undecidable, see the comments to this answer by J.-E. Pin.


In your specific case, what other constraints do you have on $M$ and $N$? For example, if it is possible that $M=N=1$, then each of your clauses will have 2 literals, and your SAT problem actually seems to become the 2-SAT problem which is in P.

So if $P_1$ depends on $M$ and $N$, maybe you should consider an NP-complete SAT variant that somehow takes them into account. In general, if you want to add some additional constraints on SAT (or any other problem you reduce from), make sure the problem still remains NP-complete.


Rice Theorem - What is non-trivial property?

A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property.

To see why, note that such a property can be decided by a very simple Turing machine, which accepts/rejects every Turing machine representation.


A tree is not restricted to a certain branching factor. A n-ary tree may only have a branching factor of n (or less), but in an unrestricted tree, each node may contain an arbitrary number of subnodes.

A tree is a connected graph without cycles, so your datastructure still satisfies that definition.

Alternatively you could call your structure something like "nested lists".


Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node)

The answer has to do with tracking the precise assumptions that are made in these different results. In short, while both results assume asynchrony, the "impossibility of distributed consensus with one faulty process" requires a stronger form of liveness and determinism, and that makes consensus impossible.

1. Impossibility of Distributed Consensus with One Faulty Process

This seminal result (of Michael Fischer, Nancy Lynch, and Michael Paterson) is about distributed consensus where the system is not just asynchronous, but also satisfies:

Determinism.  The consensus algorithm does not use any randomness.
Liveness under message delays. Not only may messages be delayed arbitrarily, but we also must guarantee liveness even in the presence of such continued delays.

Let us see why tehse properties are too strong, and make distributed consensus impossible.

Consider an example: Alice, Bob, and Charlie are friends and want to decide on where to meet for dinner. It is possible that one of them unexpectedly goes AWOL (or decides they are not interested in being friends anymore) and stops responding to messages. In this case, the other two can still decide on a place to meet. Now what should they do?

The obvious approach would be that:

  Alice just decides where to go, and tells Bob and Charlie.

But this does not work because Alice may be the one who goes AWOL.
So to fix this, the next most obvious approach might be:

  Both Alice and Bob tell everyone else where to go. If everyone hears from Alice, then they will go where Alice says; otherwise, they will go where Bob says.

But this has a new problem. Suppose you are Charlie. If you hear from Alice, you know where to go. If you hear from neither of them, you wait to hear. The problem is when you have heard from Bob, but not Alice. Because there are arbitrary message delays, you cannot commit to go where Bob said: Alice might have said where to go, and you just have not received it yet!
So you are completely stuck, and if it happens that Alice has gone AWOL, you will just keep waiting forever.

The problem here is that we have no way to abort the transaction; no way to say, "OK, this isn't working, it's been too long and I haven't received a delay -- let's try again." Real-world consensus algorithms (the best known being Paxos) have the possibility that rounds fail due to network delays, and in this case they just try again, hoping for shorter network delays. Additionally, it is possible to get around the problem by using randomized protocols which usually work, and only go on forever with small (or even zero) probability.

2. Asynchronous Byzantine Agreement where less than $1/3$ of the nodes fail

The bitcoinSE post you link glosses over the issue of liveness, saying only that it is "the ability to continue to make forward progress". In fact, the above result shows that the strongest form of this is impossible, so we have to relax our requirements / assumptions.

Let's consider two examples. In Miguel Castro and Barbara Liskov's "Practical Byzantine Fault Tolerance", they achieve practical liveness with less than a third of nodes being faulty by assuming that message delays do not continue to grow indefinitely. As the authors state:

  We guarantee liveness, i.e., clients
  eventually receive replies to their requests, provided at most
  $\frac{n-1}{3}$ replicas are faulty and $delay(t)$ does not
  grow faster than $t$ indefinitely...This is a rather weak synchrony
  assumption that is likely to be true in any real system
  provided network faults are eventually repaired, yet it
  enables us to circumvent the impossibility result in [9].

Here [9] is the impossibility result discussed above. In plain terms for our example, they avoid the above problem with Charlie by requiring a weak form of synchrony: Charlie does not simply have to keep waiting forever, as we know that message delays can only grow termporarily, and not indefinitely. (Of course the actual algorithm gets a lot more complex, but that is partly the conceptual idea of why liveness is possible.)

In Ran Canetti and Tal Rabin's "Fast Asynchronous Byzantine Agreement with Optimal Resilience", they use randomness to get liveness with less than $n/3$ Byzantine node failures. From their paper:

  In this setting, we describe an $(\lceil\frac{n}{3}\rceil- 1)$-resilient Byzantine Agreement protocol. With
  overwhelming probability all the non-faulty players complete the execution of the protocol. Conditioned on the
  event that all the non-faulty players have completed the
  execution of the protocol, they do so in constant expected
  time.

Here $(\lceil\frac{n}{3}\rceil- 1)$-resilient just means less than a third of nodes are Byzantine.
Note the key words with overwhelming probability. So they have a probabilistic algorithm which has many possible "runs", and overwhelmingly most of them work. Note that the above impossibility result implies that there must always be some runs where liveness does not occur, i.e. there is no consensus:

  Fischer, Lynch and Paterson’s [FLP] seminal impossibility result for deterministic protocols implies that any (randomized) protocol reaching BA must have nonterminating runs.


Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

Your regular expression is correct, however, your grammar isn't. Assuming $E = \varepsilon$, you can derive words like $S \to \mathtt{1}\,X \to \mathtt{1}\,\varepsilon = \mathtt{1}$.

A right regular grammar might look like this:
\begin{align}
S &::= \mathtt{1}\,A\\
A &::= \mathtt{0}\,A \mid \mathtt{1}\,A \mid \mathtt{2}\,A \mid \mathtt{9}\,A \mid B\\
B &::= \mathtt{.}\,C\\
C &::= \mathtt{0}\,C \mid \mathtt{1}\,C \mid \mathtt{2}\,C \mid \mathtt{9}\,C \mid D\\
D &::= \mathtt{9}
\end{align}


Formal way to model or describe distributed systems architecture

I am not sure what you mean by "formal approach" but have you looked at Petri Nets? Many consider Petri Nets to be a "formal approach".

Personally, I use Petri's net elements (Place, Transition, Input, Output) to organize my computer program (logic annotations to net elements). I also use it to organize requirements (annotations meant for human interpretation). I find it useful to begin with a diagram (technically, graphical annotations to net elements but if each graphic represents one and only one net element then the diagram may be used to generate the net elements). Then to aid my memory I use forms to create the annotations. Based on the diagrams and the forms, I create my computer programs.  For more information about this check out "Net Elements and Annotations for Computer Programming: Computations and Interactions in PDF".

Sometimes, I create a "high-level" diagram based on a Petri Net diagram to create a view of the system. [A high-level (Petri Net) diagram is a Petri Net diagram where one or more than one graphic object represented more than one net element]. Sometimes, I begin with a high-level diagram and break it down to a Petri Net diagram. In the "high-level" case, the form views are also applicable.


Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?

Look at Elias delta or gamma coding as an example.


How is algorithm complexity modeled for functional languages?

If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a
seemingly simple notion of
time-complexity: just count
the number of $\beta$-reduction
steps $(\lambda x.M)N \rightarrow M[N/x]$.

But is this a good complexity measure?

To answer this
question, we should clarify what we mean by complexity measure in the
first place. One good answer is given by the Slot and van Emde
Boas thesis: any good complexity measure should have
a polynomial
relationship to the canonical notion of time-complexity defined using
Turing machines. In other words, there should be a 'reasonable'
encoding $tr(.)$ from $\lambda$-calculus terms to Turing machines, such for some polynomial $p$, it is the case that for
each term $M$ of size $|M|$: $M$ reduces to a value in $p(|M|)$ $\beta$-reduction steps exactly
when $tr(M)$ reduces to a value in $p(|tr(M)|)$ steps of a Turing machine.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

There are terms that produce normal forms (in a polynomial number of steps) that are of exponential size. Even writing down the normal forms takes exponential time.
The chosen reduction strategy plays an important role. For example there exists a family of terms which reduces in a polynomial number of parallel β-steps (in the sense of optimal λ-reduction), but whose complexity is non-elementary (meaning worse then exponential).

The paper "Beta Reduction is Invariant, Indeed" by B. Accattoli and  U. Dal Lago clarifies the issue by showing a 'reasonable' encoding that preserves the complexity class P of polynomial time functions,  assuming leftmost-outermost call-by-name reductions. The key insight is the exponential blow-up can only happen for 'uninteresting' reasons which can be defeated by proper sharing. In other words, the class P is the same whether you define it counting Turing machine steps or (leftmost-outermost) $\beta$-reductions.

I'm not sure what the situation is for other evaluation strategies.
I'm not aware that a similar programme has been carried out for space complexity.


Why is fail[1] in KMP Algorithm always 0?

This is by definition, since:

  For each position i in pattern P, spi is defined as the length of longest proper suffix of P[1...i] that matches a prefix of P.

So, we can conclude that for i=1 the length of longest proper suffix that matches the prefix is 0 since longest prefix = suffix = EMPTY_STRING.

Visit this page for details.


Does exploiting a spatial Locality in Cache always leads to a lower miss rate?

Spatial (and temporal) locality are both heuristics. Many (in fact, most) algorithms run on data structures in some sequential manner, which many times means that the memory used is consecutive.

However, there are examples where spatial locality may actually be very bad. Perhaps the most common example is scanning a 2-dimensional array: consider an $n\times n$ array, then in the memory, it is represented as an $n^2$ length array, where the entry $i,j$ is in cell $i+n*j$.

If you scan the array row by row, then spatial locality is excellent, your cache will always prepare the next row.
However, if you scan by column, then not only will you always get a miss, but using spatial locality, you will actually retrieve the same rows over and over.


When to add and when to multiply to find time complexity

You add time complexities when you have something of the form: do operation $A$, then do operation $B$. This would be (time complexity of $A$) + (time complexity of $B$).

You multiply time complexities when you have something of the form: do operation $A$, $X$ times (eg. in a for loop). This would be $X \cdot $(time complexity of $A$).

If you perform two binary searches, each of which has time complexity $\log n$, the total runtime is $\log n + \log n$. You might see a runtime of $(\log n)^2$ if you had to perform $\log n$ binary searches.


Why Don't We Use Non-ML Artificial Evolution?

Because we don't know how to make it work well to solve practical problems we care about.

If your'e asking about evolutionary algorithms in general: As a rough rule of thumb, evolutionary algorithms haven't turned out to be all that wonderful.  As a starting heuristic, they're... usually OK.  But, practical experience is that other methods often seem to perform better.

If you're asking about Tierra specifically: Tierra was a demo applied to a very specific, artificial situation.  It doesn't seem to have generalized to allow us to solve many practical problems we care about.  Also, I'm not sure, but it looks like Tierra might have been intended more to try to understand evolution, more than to apply evolution to solving practical computing problems.


Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm.

Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time proportional to $\sqrt{10^d} \approx 3.16^d$, i.e. exponential in $d$, the number of digits. That is by no means "fast" and grows very quickly as the numbers get larger.

It is polynomial with respect to the value of $n$, but not with respect to the size of $n$. This behavior is called pseudopolynomiality.

The "fast" prime testing algorithms use much more sophisticated approaches which can not be modified (easily) to also give a factorization. They just report yes/no whether the number is prime. The AKS primality test uses time proportional to $d^6$.


Prove that L = { wu; wu in {a,b}* and |w| = |u| } is not regular

As Rick Decker said $L$ is a regular language. For example:
$$L= \mathscr{L}(\,(aa | ab | ba | bb)^*\,)$$

If your teacher asked you to prove that $L$ is not regular in an exam then he is a big troll. Otherwise remember that the pumping lemma is only usefull to prove that a language is not regular and if you fail to find the contradiction in the lemma then that doesn't prove anything. $L$ can be regular or irregular at that point.

In this answer I covered some common mistakes when students use the pumping lemma: Common Mistakes


Shuffling a file on disk using $O(\log n)$ memory

The algorithm you suggest doesn't result in a uniform permutation. An in-place algorithm which works for every file size is the Fisher–Yates shuffle.


complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$

Purely for clarity I'll lay out the definitions first, then give a reduction for your problem, so skipping a little ahead shouldn't cause a problem (if it does, start a bit earlier ;) ).
The two problems:

Hamiltonian Path (HP)
Input: A graph $G$.
Question: Does $G$ contain a path with $|V(G)|$ vertices?
Not Quite Longest Path (NQLP)
Input: A graph $G$ and an integer $k < |V(G)|$.
Question: Does $G$ contain a path on $k$ vertices?

Now, what we want to prove:

Lemma 1: NQLP is $\mathcal{NP}$-complete.

Of course this has two parts, membership and hardness.

Proposition 2: NQLP $\in \mathcal{NP}$

Proof: Given an order set of vertices we can easily check that it is of length $k$ and forms a path in $G$. $\Box$

Proposition 3: HP $\leq_{m}$ NQLP

Proof: Let $G$ be an instance of HP and for convenience let $n = |V(G)|$. We construct an instance $(G', k)$ of NQLP by taking $G'$ as $G$ with an additional, disconnected vertex $v$, i.e. $V(G') = V(G)\cup \{v\}$ and $E(G') = E(G)$. Thus $|V(G')| = n' = n+1$. We choose $k = n < n'$. This construction is clearly computable in polynomial time.
Claim: If $G$ has a Hamiltonian path, $G'$ has a path of length $k$.
By definition, the Hamilton path includes all vertices of $G$, as $G'$ has $G$ as an (induced) subgraph, this path exists in $G'$. Moreover it is of length $n = k$.
Claim: If $G'$ has a path of length $k$, $G$ is has a Hamiltonian path.
If $G'$ contains a path of length $k$, it cannot include the added vertex $v$, as it has no incident edges (except the trivial case where $G$ was one vertex, but then we have a symmetry which does our work for us). Therefore it must include every other vertex in $G'$ (as $k = n' -1 = n$), as $G' - v$ is simply $G$, $G$ must be Hamiltonian. $\Box$
Proof of Lemma 1: As HP is $\mathcal{NP}$-complete, Prop. 3 proves that NQLP is $\mathcal{NP}$-hard. Then combining Propositions 2 & 3, we have proved Lemma 1. $\Box$


Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$

Your guess is wrong. In fact, it is not hard to show that assuming $T(n) > 0$ for all $n > 0$, then $T(n) = \Omega(\log^k n)$ for all $k$. Indeed, for this to hold we need that for large enough $n$ we would have
$$
(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),
$$
or $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$,
which holds as long as $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, and in particular for large enough $n$.

What is the correct order of growth of $T(n)$? To try and find out, write $S(n) = T(2^n)$. The recurrence now becomes
$$ S(n+1) = S(n) + S(an). $$
For large $n$, we would expect $S(n+1) - S(n)$ to be very close to $S'(n)$, and so heuristically we would expect that $S$ satisfy $S'(n) = S(an)$. This equation seems a bit hard to solve, but an approximate solution is $S(n) = n^{\Theta(\log n)}$. Substituting back, we deduce that the order of growth of $T(n)$ should be something like $(\log n)^{\Theta(\log \log n)}$.


Is $(aaaaa)^n aa (aaaaa)^n$ a regular language?

The language consists of those strings that contain $5 n + 2 + 5 n = 10 n + 2$ symbols $a$ for some $n \in \mathbb{N}$, i.e.,
$$\lbrace(aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N}\rbrace =
\lbrace (aaaaaaaaaa)^n aa \mid n \in \mathbb{N} \rbrace.$$
It is regular because it is accepted by the automaton which has twelve states $s_0, \ldots, s_{11}$ with a starting state $s_0$, accepting state $s_2$, and transitions $s_i \stackrel{a}{\longrightarrow} s_{i+1}$ for each $i = 0, \ldots, 10$, and one more transition $s_{11} \stackrel{a}{\longrightarrow} s_0$. In essence, this automaton counts the number of letters modulo 10 and accepts if the answer is 2.


Analyzing the Runtime of Shuffling Algorithm

You are right about the running time of the second algorithm, i.e., Shuffle1$(A)$. Its running time is indeed $O(n^{3} \cdot m^2)$.
To analyze the running time of the first algorithm, i.e., Shuffle$(A)$, you can formulate the recurrence relation as follows:
$$T(n) = 4 \cdot T(n/2) + O(n^2)$$
Note that, Random(10) takes time $O(10^2) = O(1)$.
You can indeed solve this recurrence using the Master Theorem. The theorem gives $T(n) = O(n^{2} \log n)$ by applying Case $2$ of the theorem.

You can also solve the recurrence by the expansion method as described below:
$$
\begin{align}
T(n) &= 4 \cdot T(n/2) + O(n^{2}) \\
&= 4 \cdot (4 \cdot T(n/4) + O(n^{2}/4)) + O(n^{2}) \\
&= 4^{3} \cdot T(n/8) + 4^{2} \cdot O(n/4^{2}) + 4 \cdot O(n^{2}/4) + O(n^{2}) \\
& \quad \, \textrm{... on further expansion we get the following relation} \\
&= 4^{t} \cdot T(n/2^{t}) + \sum_{i = 0}^{t} 4^{i} \cdot O(n^{2}/4^{i}) \\
\end{align}
$$
When $t = \log n$, the value $T(n/2^{t})$ becomes $T(1)$. I am assuming that $T(1) = 1$ for the base case of your algorithm. (ttnick is asking the same question in the comment section also). Based on this assumption, we get the following relation:
$$T(n) = (4)^{\log n} \cdot 1 + \sum_{i = 1}^{\log n} O(n^{2}) = n^{2} + \sum_{i = 1}^{\log n} O(n^{2}) = O(n^2 \log n)$$.


In fact, you're talking about Memetic Algorithms. In the case of a neural network, supposing you have training samples, the individual learning may be done through an iteration of backpropagation. If you don't have training examples, you may apply some noise to the weights and keep the modification only if it performs better (hill climbing). Actually, any local search algorithm could be used.
Regarding the frequency of individual adaptation, this is currently a research topic, but you can find works that suggest applying the adaptation to all individuals at every generation as well as other works suggesting to increase this frequency gradually, since the last generations are the ones which need more fine tuning. Genetic algorithms are very good to find some good global solution, while local search is very good to find the optimal local solution. So the trick is to find the optimal solution region with GA and fine tune with local search.


Here is what you need to prove:

  If $a > 7$, $b \geq 0$ and $n = a-b$ then $n < a$ and $a+b \geq 0$.

By the way, this is actually false, since if $b = 0$ then $n = a$. Perhaps you miscopied?


Option 1: Use least squares fit to find the closest plane.  Then, measure the average squared error (the sum of the squared residuals).

Option 2: Use robust regression instead of least squares.  Or, use RANSAC.  These will handle outliers better.

All of these run in polynomial time.


Difference between virtual memory and job pool

The concept of “job pool” refers to a batch processing system, where jobs are queued to be executed when resources are available. The job pool contains both jobs that are currently executing and jobs that have been scheduled but are not yet being executed. Ancient computers (and some mainframes that are still in operation) worked this way. When a job is executing, it is fully present in memory.

Modern systems don't work that way. Computers that are big enough to run multiple tasks — even many embedded systems — have a memory management unit which translates virtual memory addresses to physical addresses, and the operating system uses that to move each page between memory and disk (this is called swapping or paging). This is an evolution from earlier multiprocessing systems: at first (before the MMU era) processes were swapped as a whole, but nowadays, if there isn't enough memory to fit all currently running processes, the operating system can swap out the parts of processes that aren't currently being used.

Systems designed for large non-interactive computations generally use job management even today. Swapping takes time; if the active processes require more memory than is available to run comfortably, this causes thrashing. To avoid this, job schedulers do use job pools, and arrange to start jobs, and possibly pause them, based on available resources. The system works on top of an operating system based on virtual memory, so once a job is paused it will naturally be swapped out as its pages in RAM are replaced by pages of active jobs.

(Note that job-based management is only marginally relevant to today's computing environment. I wouldn't set much store by a textbook that focuses on that in the 21st century. Virtual memory, on the other hand, is relevant to all but low-end embedded systems.)


Dempster-Shafer theory initial belief values

If the 95% (initial) belief corresponds to the probability of a true positive according to the performance statistics, then that seems appropriate to me.


Since you have both lists, even if not both at the same time, your
space cost is at least that of the longest, thus at least $n/2$.
This corresponds to a $O(n)$ space complexity.

So, unless you exclude it for some reason, it makes sense to use a bit
array $M[1:n]$ to represent the set A by its characteristic function,
i.e. $M[i]=0$ iff $i\notin A$, and $1$ otherwise. The space complexity
is unchanged, and the array $M$ is actually much smaller than one of
the two lists (initial or final).

Initializing the array $M$ from the initial list is linear.

Then you can take the logical complement of the array $M$ in linear
time.

Then you scan the array in linear time to get all the element of the
complement of your initial list in linear time $O(n)$

Of course, by now you have noticed your mistake: sorting is in time
$O(n \log n)$ (or better according to comment) when $n$ is the number
of element to be sorted.  But it is trivially linear if $n$ is the size of the
finite ordered set they come from.

Using an array, as I just did is one way of sorting in linear time with respect to the size of the referance set.

Your own answer was good because of that. Only your complexity assessment was wrong.


Definition of Turing Machine as a language acceptor

Immediately after the definition, the text (fifth edition) continues

  This definition indicates that the input $w$ is written on the tape with blanks on either side. The reason for excluding blanks from the input now becomes clear: It assures us that all the input is restricted to a well-defined region of the tape, bracketed by blanks on the right and left. Without this convention, the machine could not limit the region in which it must look for the input; no matter how many blanks it saw, it could never be sure that there was not some nonblank input somewhere else on the tape.

This differs from the approach some other authors take, using a tape that's bounded on the left and unbounded in the other direction, and stipulating that the input string begins at the leftmost cell and continues to the first blank. I don't find Linz's definition to be better, if for no other reason than it eliminates any language containing the empty string from being the language of a TM.


Minimum Spanning Tree over Vertices Proof

It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$,
$$
\begin{align*}
\sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) \\ &=
\sum_i \sum_{(i,j) \in T} w(v_i) + \sum_j \sum_{(i,j) \in T} w(v_j) \\ &=
2 \sum_i d_T(i) w(v_i).
\end{align*}
$$
You take it from here.


Fastest known complexity for combinatorial ILP algorithm?

From what I can tell by searching, the definite survey seems to be:

Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied Mathematics 123.1 (2002): 5-74.

In particular, Section 2.1 discusses integer programming in bounded dimension, and presents algorithms due to different authors. Indeed, the survey lists many references, and discusses some practical implementations.

For a fixed number of variables, integer linear programming is polynomial time solvable by Lenstra's algorithm.


Single Source Shortest Paths using Product Construction

The product construction means that you don't just store the shortest distance to a given node, but store the shortest distance to reach a node on a shortest path with $k$ nodes. You certainly don't need to explicitly construct the edges of the product graph. But since the algorithm will produce $k\cdot|V|$ shortest distances of this form, it seems as if you must at least construct an array of this size to hold those distances.
However, this is not exactly true, because only the distances different from $\infty$ must be stored.

So you could either generate the nodes of the product graph on the fly and store them in a map (i.e. something like a red black tree), or first determine the reachable part of the product graph by a suitable algorithm. If you only care about the complexity and not about the practical efficiency, then the solution with the map is simpler and still good enough. That map can then also be used for Dijkstra's algorithm itself to determine the next node on which the algorithm continues.

The disadvantage compared to Bellman-Ford's algorithm is that you can't reuse the memory from the previous iteration for the current iteration, because Dijkstra's algorithm will not produce all distance $j-1$ paths before producing distance $j$ paths. But maybe it is possible to modify Dijkstra's algorithm to do exactly this, and this might indeed yield the most efficient algorithm for your problem.


Technically, a transition has to be an atomic event (in the context of formal languages, the reading of a symbol). That said, there are two situations in which you could imagine something different:

1) You could use a set of symbols as an abbreviation of multiple alternative transitions from one state to the other, or a string of symbols as an abbreviation of a sequence of transitions that happen one after the other. In fact, a number of different abbreviations are commonly used when dealing with finite automata on practical situations.

2) You could have a language whose symbols have an internal structure (for instance, they are encodings of sets). Of course, this internal structure should be transparent to the formal treatment of the language.

As with any alternative representation of a formal expression, these variations should be used when their understanding is clear, from definition, or context.


What information needs to be saved in a Lamport clock system to deduce message causality?

Lamport clocks are not designed to allow you to infer all causality.  No one ever claimed that knowing the Lamport timestamp is enough to read out the causality of all messages.

Rather, Lamport clocks provide a partial ordering that is consistent with causality: if event $a$ happens before event $b$ (causally), then $a$'s timestamp will be smaller than event $b$.  The converse does not necessarily hold.

See https://en.wikipedia.org/wiki/Lamport_timestamps and https://en.wikipedia.org/wiki/Lamport_timestamps#Implications.

If you want to read out the full causality, use vector clocks or other methods that are designed for that.


Is ambiguity in Programming Language always bad?

There are computer languages with ambiguous grammars. They decide how to compile ambiguous code by applying rules outside the grammar (there’s no law saying that a language has to be defined by a grammar only). The problem is if your language is ambiguous - if you have code and cannot tell how it should be compiled, that’s quite useless.


Are these sets of indices also index sets?

We start with a bit of notation:

$\phi_x$ is the partial function computed by program $x$.
$W_x = \operatorname{dom} \phi_x$, that is, the set of inputs on which program $x$ halts.
An index set is a set of programs $I$ such that if $\phi_x = \phi_y$ then $x \in I \Leftrightarrow y \in I$. (That is, $I$ is a union of equivalence classes of the equivalence relation $x \equiv y \Leftrightarrow \phi_x = \phi_y$.)

Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.

We can now go over the four sets in the question:

$\emptyset$ is trivially an index set.
$K = \{ e : e \in W_e \}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W_e = \{e\}$. There are infinitely many programs which halt only on input $e$ and output $\phi_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi_e = \phi_{e'}$. (This proof is taken from S. Barry Cooper, Computability Theory, mention by Pål GD in the comments.)
$E = \{2,4,6,8,\ldots\}$ is computable and so not an index set by Rice's theorem.
$\{ x : \phi_x = \phi_{x^2} \}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi_x = \phi_{x^2} = \phi_y$ then also $\phi_y = \phi_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi_x = \phi_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi_x = \phi_y$. It would be a major coincidence if for all $x,y$ we would have $\phi_y = \phi_{y^2}$.)

In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \{ x : \phi_x = \phi_{x^2} \}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.

For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:

$I$ can be an index set: Fix some admissible numbering $\phi_x$. Let $p_i$ be the $i$th prime. Define a new admissible numbering $\psi_x$ by $\psi_{p_i^k} = \phi_i$ for all $k \geq 1$, and $\psi_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi_x = \psi_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.
$I$ can be not an index set: Fix some admissible numbering $\phi_x$. Define a new admissible numbering $\psi_x$ by
$$ \psi_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi_{x-5} & x \geq 5 \end{cases} $$
In this case $\psi_1 = \psi_{1^2} = \psi_2$ but $\psi_2 \neq \psi_{2^2}$, showing that $I$ is not an index set.

I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.


Counting the nodes of a unidirectional graph

You can build a graph $G'=(V,E')$ that comprises the same set of vertices $V$ from the input graph $G=(V,E)$ and whose set of edges $E'$ includes an edge $(v,u)$ for every edge $(u,v) \in E$. That is, $G'$ is the same graph as $G$, but with the edges reversed; therefore, $G'$ is also topologically sorted (in the same way as $G$, but in the opposite direction). You are looking for the number of successors (+1) of every vertex in $G'$. This can be found using depth-first search, starting a new traversal from every vertex and counting the nodes that you find. The running time of this algorithm is $O(mn)$, where $n$ is the number of vertices of the graph and $m$ is the number of edges. D.W.'s answer provides some useful links with approaches with slightly better running times.


Searching for efficient method to compute $a^n \bmod p$ for large numbers

The algorithm you are looking for is quick modular exponentiation.

It is based on the exponentiation property of modulus operator
:

A^B mod C = ( (A mod C)^B ) mod C

for example we need to calculate 4^8 mod 7 (let us assume for the time being 4^8 is a large number and cannot be computed by available machines.)

we can then write

=(4^ 4 * 4 ^ 4) mod 7

=(4^4 mod 7 * 4^4 mod 7 )mod 7

= (256 mod 7 * 256 mod 7) mod 7

= 2

This algorithm doesn't only work for powers of 2 it works generally . We just need to write the power in its binary representation .

example :

3^31 mod 4

can be written as

3^(16+8+4+2+1) mod 4

you can see once we apply the exponentiation property to same the computations will be quite efficient.


Can every context free grammar be transformed into equivalent grammar of this form?

Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals that represent sequences of old nonterminals, for instance $[A_1A_2\dots A_k]$ is a single symbol that represents the sequence $A_1A_2\dots A_k$ when $k\ge 2$.

Then any production $A\to aA_1A_2\dots A_n$ with $n\ge3$ is replaced by $ A\to a A_1[A_2\dots A_n]$, leaving two nonterminals at the rhs of the production.

Remaining question: what are the productions for terminals $[A_1A_2\dots A_k]$, in such a way that we get only a bounded number of those nonterminals?
Well, if $A_1 \to bB_1\dots B_m$ in the original grammar in GNF, then we add the production $[A_1A_2\dots A_k] \to b[B_1\dots B_m][A_2\dots A_k]$ in the new grammar. This can be done for all sequences of nonterminals that are suffixes of the sequences introduced by the original grammar.

Note that we have to take care of short sequences in the obvious way. If in the construction above we find an empty sequence $[\ ]$ it should be omitted, and we write $A$ for the sequence $[A]$ of length one. These special cases occur if $m\le 1$ or $k\le 2$.


Once you have $S(m) = 2 S(m-1) + 2^{3m}$, you can divide by $2^m$ and obtain :
$$\frac{S(m)}{2^m} = \frac{S(m-1)}{2^{m-1}} + 2^{2m}$$
Thus, setting $P(m) = \frac{S(m)}{2^m}$, you should be able to find $P(m)$, then $S(m)$.


Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A_1,A_2$ with no edges between them. It is consistent that all elements in $A_1$ are smaller than all elements in $A_2$, in which case the maximum is in $A_2$. Similarly, the maximum could be in $A_1$. The algorithm cannot tell which is which, hence will be wrong on at least one of these scenarios.

The exercise was probably aiming at the following simpler argument: if less than $\lceil n/2 \rceil$ comparisons are made, then there is at least one element which is not compared at all. Hence for all we know, it could be the maximum, or the minimum (if these are different!); indeed, it could be at any position at all. This argument works as long as $n > 1$.


Does a Non-Deterministic Turing Machine solve all problems in P in constant time?

A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.