You can reduce to this from $CLIQUE$.

Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n
+2}\}$ and connecting them with all of $G$'s vertices but removing the edge $\{v_{n+1},v_{n+2}\}$, i.e. they are not neighbors in $G^*$. return $G^*$ and $t+2$.

If $G$ has a $t$ sized clique by adding it to the two vertices we get an $t+2$ almost clique in $G^*$ (by adding $\{v_{n+1},v_{n+2}\}$).

If $G^*$ has a $t+2$ almost clique we can look at three cases:

1) It contains the two vertices $\{v_{n+1},v_{n+2}\}$, then the missing edge must be $\{v_{n+1},v_{n+2}\}$ and this implies that the other $t$ vertices form a $t$ clique in $G$.

2) It contains one of the vertices $\{v_{n+1},v_{n+2}\}$, say w.l.o.g. $v_{n+1}$, then the missing edge must be inside $G$, say $e=\{u,v\}\in G$. If we remove $u$ and $v_{n+1}$ then the other $t$ vertices, which are in $G$ must form a clique of size $t$.

3) It does not contain any of the vertices $\{v_{n+1},v_{n+2}\}$, then it is clear that this group is in $G$ and must contain a clique of size $t$.

It is also clear that the reduction is in polynomial time, actually in linear time, log-space.


First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

What I tried was to do both DFS and BFS on a couple of graphs and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ.

Indeed, the spanning trees formed by the first-visited nodes might be different from DFS and BFS. For example, try a cycle graph of four vertices. When the spanning tree are different, the number of edges is still the same for both.

You might have noticed that the number of edges is always one less than the number of vertices of the graph, either by concentration or by luck, had you been playing with connected graphs long enough.

In fact, the number of edges in every spanning tree of a connected graph is always one less than the number of vertices in that graph. This comes from the following two facts.

The number of edges in a tree is one less than the number of vertice of that tree.
The vertices in a spanning tree of a connected graph are the vertices of that graph.

Exercise. What about disconnected graphs?


If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?

The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:

Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several reasons:

The real MST of the new graph differs in an edge that's not in the cycle. Then the original MST wasn't an MST to begin with, and we have a contradiction.
The real MST differs in an edge that's in the cycle, but then, as the rest of the tree is the same, we can't have removed the heaviest edge from the cycle, and we have a contradiction again.

Therefore the new tree is an MST of the new graph.


Analysis of updating vertex and one example?

In Dijkstra's algorithm there are $|E|$ update operations and $|V|$ remove_min operations.
To implement the algorithm, we can employ different types of data-structures. Since you are looking for the best update cost per vertex, you can employ the Fibonacci heap or Hash map implementation since they give you the minimum update cost (as per the table mentioned in your question). Now, suppose you employ Fibonacci heap. Then, the total amortized update cost for Dijkstra's algorithm would be $|E| \cdot O(1) = O(|E|)$. Therefore, the amortized update cost per vertex is: $O(|E|/|V|)$.

These are the three main implementations of Dijkstra's algorithm:

Array Implementation (a.k.a. Hash Map as per your table): Update $O(1)$ and Remove_Min $O(|V|)$

Binary Heap Implementation (a.k.a. Hybrid Binary Heap as per your table): Update $O(\log |V|)$ and Remove_Min $O(\log |V| )$

Fibonacci Heap Implementation: Update Cost $O(1)$ and Remove_Min Cost $O(\log |V|)$

Note that Fibonacci Heap provides the best update cost and the best remove_min cost among these three options. Therefore, it is the best of both worlds. Hence, it is best for Dijkstra's algorithm and you can remember this implementation only.


Semantics of Regex with boundary matchers

First of all, what we usually call Regex, for instance, in the context of programming languages, is not the same as pure regular expressions. That should not come as a surprise: all computational models have to be adapted to the real world to be made useful. In this case, besides being enriched by features that just enlarge the range of languages it can specify (such as numbered back references), Regex has other features that would require a completely different set of tools to be formalized properly.

What comes after ^ will not be matched to a prefix of the input string. What happens is that ^ is a reference to an event (as is $, they are called anchors). In abstract terms, you can think of the input of a Regex as continuous stream of symbols, unbounded, that is divided in units of limited size, separated from each other by a special symbol. Where should the matching process begin? This is where anchors come to the rescue.

In this context, ^ refers to the event of finding the special symbol, and forcing the Regex to match beginning with whatever comes right after, instead of $\unicode{x2013}$ for instance $\unicode{x2013}$ continuously trying to match a string starting with each symbol from the input, and backtracking to the next, in case of failure.

What the actual input unit is, pragmatically, depends on the context of application of the formalism. Usually we are talking about lines in a text file, separated by line break characters, or the successive contents of an input buffer.


Solving recurrence relation having square root

The solution is $T(n) = \Theta(n)$. It is easy to see that $T(n) = \Omega(n)$ (indeed, $T(n) \geq n$), and you can prove $T(n) = O(n)$ by induction: choose some constant $C>0$. Suppose that you have shown that all small enough $n$ satisfy $T(n) \leq Cn$. Then for larger $n$,
$$ T(n) \leq 2T(\sqrt{n}) + n \leq 2C\sqrt{n} + n = \left(\frac{2C}{\sqrt{n}} + 1\right)n. $$
This is at most $Cn$ if $2C/\sqrt{n}+1 \leq C$, and in particular if $n \geq 16$ and $C \geq 1$. Therefore if we define $C = \max(1,T(1)/1,\ldots,T(15)/15)$ then the argument above shows that $T(n) \leq Cn$.


Here's a big hint, and then I'll let you work out the rest for yourself. Because we want cs.SE to be a collection of questions and answers, please post your solution as an answer.

Edge-triggered D flip flops are generally done using the "two RS flip flop" design that you have. You got that right. Reading from left to right, I'm going to call these RS flip flops "stage 1" and "stage 2".

Before the transition "happens", stage 1 should load the data. The effect of the transition is to make stage 1 hold its data and make stage 2 load its data from the output of stage 1.

So to create a D flip flop that is triggered on the rising edge:

When the clock is low, stage 1 should load its data and stage 2 should hold its data.
When the the clock is high, and stage 2 should load its data and stage 1 should hold its data.

The effect of this is that the transition from low to high shifts the result from stage 1 to stage 2.

Conversely, to create a D flip flop that is triggered on the falling edge, stage 1 should load when the clock is high, and stage 2 should load when the clock is low.

Now can you implement that?

Incidentally, I don't understand your teacher's requirement "we couldn't use any gate on clock". When you realise digital circuits in CMOS or NMOS, clock fanout is a large practical issue. Besides, you only get inverting gates, so putting gates on clock lines is normal and expected.

Nonetheless, perhaps they meant you to use de Morgan's laws to reduce the gate count?


The expression
$$ \sum_{i=1}^n i^2 $$
is not an algorithm. It is just a number. In fact, what the book really means is the function
$$ n \mapsto \sum_{i=1}^n i^2. $$
Since
$$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6}, $$
we see that this sum is indeed $O(n^3)$, in fact, even $\Theta(n^3)$.

We often use big O notation in analyzing the running time of an algorithm. Quicksort runs in time $O(n\log n)$ (on average) since the function $T(n)$ measuring its average running time on inputs of length $n$ is $O(n\log n)$ — the function $T(n)$, not the algorithm itself.


Compute height of AVL tree as efficiently as possible

No.  There's a $\Omega(\lg n)$ lower bound.  You can't do better than $O(\lg n)$ time.  In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0.  In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T_1$ and $T_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T_1$ from $T_2$.  Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes.  To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T_1$ and on $T_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.


In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

In the paper they created gadget called a gate. This gadget has two entrances, from one entrance the player can open the gate, the other entrance can be traversed only if the gate its on the open state.

In the cell gadget, there are $2k + 2$ gates where $k$ is the number of states the turing machine has and the other two gates correspond to the symbols ($0$ or $1$) that the tape of the turing machine can have.

When the player enters the cell gadget, he accesses a chamber corresponding to the state the turing machine is at that moment. In the chamber, there are two gates that correspond to the two possible symbols that the turing machine can have. There, the player can open one of the gates, the opened door has to coincide with the symbol that the turing machine has in that cell.
He opens the gate by entering through one of the two entrances of the gate, he cannot access the other entrance from here. After opening the gate, he can traverse one of the two symbol gates, closing it.

After traversing the gate, the player reaches a different corridor, from that corridor he can access only the "state gates" that have the same symbol that the symbol gadget has (if they are opened), so he must have chosen to open the correct gate gadget in order to continue. Assuming that the player decided to open the correct state gadget, he can return to the same gate he opened before by entering through the second entrance of the gate (I thought that the player went to a different gate after that, the figure confused me).

After traversing the gate from this second entrance, the player closes the gate. From here he goes to a corridor that allows the player to open one of the symbols gadgets he visited previously (not a different one), and he will only be allowed to open the symbol gadget that the turing machine will write in that state and symbol configuration (if he decides not to open the symbol gate, he will be trapped if he decides to return to the gadget).


Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

You write in the comments:

  Since the address should be written in the tape by a $T(n)$-time Turing Machine, the size (i.e. string length) of the address can not exceed $O(T(n))$.

Can you use a similar argument to improve the bounds

  [The] tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.

you mention in the question? You may need to remember what operations are possible in constant time on the RAM, that is using the precise definition the authors use.


Conditions to apply Source Coding Theorem

It is an average in bits/symbol and does apply to all coding schemes.
You're correct, the number of bits/symbol needed is equal  or larger than the entropy rate (asymptotically, though) of the source for any lossless code.
If you allow for lossy coding, then a generalization called rate-distortion function is needed to lower bound the rate required.


Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?

Is an independent set a biclique?

After figuring out the first reduction from Vertex Cover (VC) described below, I realised that I had assumed that a biclique has at least one vertex in each part (and thus at least one edge).  But in many ways it makes more sense to consider an independent set (IS) to be a biclique too: it is a complete bipartite subgraph induced by two disjoint vertex subsets $A$ and $B$ -- it just happens that one of the subsets is empty -- so it (vacuously) meets the criteria.  (Similarly, a one-vertex graph is still considered a bipartite graph, and still considered a clique.)  I could not quickly find a "standard" definition to confirm either possibility, so I'll first give a reduction that considers only complete induced bipartite subgraphs with both vertex sets nonempty to be bicliques, and then describe how to modify the construction when independent sets are also considered to be bicliques (which turned out to be much trickier).

I'll call the problem in question "Maximal Biclique Hitting Set" (MBHS).  A biclique that contains at least one edge (i.e., is not an IS) is an "edgy" biclique.

Reduction from Vertex Cover for "edgy" bicliques

The following construction builds a MBHS instance $(G' = (V', E'), k')$ that replaces every edge in the input graph $G = (V, E)$ with a "rectangle" in which the two pairs of diagonally opposite vertices form a 4-vertex maximal biclique.

Add all vertices and edges in $G$ to $G'$.  For every edge $uv$ in $E$, create two new vertices $x_{uv}$ and $y_{uv}$ in $G'$, and the three edges $x_{uv}y_{uv}$, $uy_{uv}$ and $vx_{uv}$.  Set $A_{uv} = \{u, x_{uv}\}$ and $B_{uv} = \{v, y_{uv}\}$ and observe that $(A_{uv}, B_{uv})$ forms a biclique with 2 vertices in each part.

To see that this biclique is maximal, consider any other vertex $z \in V' \setminus \{u, v, x_{uv}, y_{uv}\}$.  To be able to add $z$ to $A_{uv}$ to form a larger biclique $(A_{uv}', B_{uv})$, $z$ must be adjacent to both $v$ and $y_{uv}$ -- but by construction, the only vertices adjacent to $y_{uv}$ are $x_{uv}$ and $u$, and $z$ is not either of those.  Similar reasoning shows that $z$ cannot be added to the other side ($B_{uv}$) either.  Since $z$ was arbitrary, $(A_{uv}, B_{uv})$ must be a maximal biclique.

Finally, set the threshold parameter $k'$ for the MBHS instance to $k$.  This concludes the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k'$.  The VC directly gives a solution to the MBHS instance, since every maximal biclique in $G'$ (both the rectangle bicliques that we created, and any bicliques already present in $G$) contains some edge of $G$, and every edge of $G$ contains at least one vertex in the VC solution.

If there is a solution to the constructed MBHS instance of size at most $k'$, then there is a solution to the original VC instance of size at most $k$.  Assume there is an edge $uv$ in $G$ whose corresponding edge in $G'$ is not covered (i.e., neither of its endpoint vertices is in the MBHS solution), since otherwise we are already done.  Let $(\{u, x_{uv}\}, \{v, y_{uv}\})$ be the unique rectangle maximal biclique that contains $uv$ in $G'$: then it must be that at least one of $x_{uv}$ or $y_{uv}$ is in the MBHS solution, since there is no other way to hit this biclique.  Replace whichever one of these two vertices is in the solution (choose arbitrarily if both are) with either $u$ or $v$ (again, choose arbitrarily) to create a new MBHS solution of the same size (at most $k$) with one more $G$-edge covered.  This can be repeated until every edge in $G$ is covered by a vertex in the MBHS solution, which remains of size at most $k$.  Finally, discard any remaining "rectangle vertices" (vertices not in $V$) from the solution, leaving a VC of size at most $k$.

When independent sets are considered bicliques too

If independent sets are also bicliques, the construction above can fail, most obviously on a graph containing vertices but no edges (which has a single maximal biclique, but an empty VC).

Create $|V|+1$ copies of $G'$ (that is, of the graph constructed for the reduction for edgy maximal bicliques).  Call this new graph $G''$.  The key observation is that in $G''$, there are $|V|+1$ copies of each maximal edgy biclique in $G'$ that all need to be hit separately, but a set of vertices that hits every maximal IS in a single copy of $G'$ suffices to hit every maximal IS in $G''$.  (There are actually vastly more maximal ISes in $G''$ than in $G'$, since to form a maximal IS in $G''$, we may independently choose a maximal IS from each copy of $G'$.  But an IS in $G''$ cannot be maximal unless it includes some $G''$-IS in each copy -- so it suffices to choose a particular copy and hit every maximal IS in that copy.)

Let $k''$ be the threshold parameter that together with $G''$ forms the constructed instance of MBHS.  Set $k'' = k(|V|+1) + |V|$.  Essentially this allows us to spend $k$ vertices hitting edgy maximal bicliques in each of the $|V|+1$ copies of $G'$, plus up to $|V|$ vertices to hit maximal ISes.

That ends the description of the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k''$.  To see this, first replicate the VC solution across all $|V|+1$ copies of $G'$ in $G''$: these vertices hit every edgy maximal biclique for a cost of $k(|V|+1)$.  Now add every remaining vertex from the first copy of $G'$ to the solution, ensuring that we hit every maximal IS in that copy of $G'$, and thus every maximal IS in $G''$ overall, for at most $|V|$ more vertices.  Every maximal biclique is now hit and we have used at most $k(|V|+1) + |V| = k''$ vertices.

If there is a solution to the constructed MBHS instance of size at most $k''$, then there is a solution to the original VC instance of size at most $k$.  By the pigeonhole principle, at least one of the $|V|+1$ copies of $G'$ has at most $k$ vertices in the solution.  These $k$ vertices necessarily hit all edgy maximal bicliques in that copy, since there is no other way to hit these bicliques, and so can be transformed into a solution to the original VC instance of size at most $k$ in the same way as described earlier for the "edgy bicliques" version of the reduction.

Obviously all steps can be carried out in polynomial time, so the MBHS problem is NP-hard.  (It's not clear to me that it is in NP though -- there could be exponentially many maximal ISes (consider a $3n$-vertex graph consisting of $n$ vertex-disjoint triangles), so checking that each one is hit takes too long.  Does anyone have thoughts on a certificate that can be checked in poly-time?)

Bonus material: A failed reduction attempt

My first attempt at dealing with non-edgy bicliques was to add one new vertex $p$ to $G'$, and connect it to every other vertex in $G'$: Now every maximal independent set originally in $G'$ becomes a maximal biclique with $p$ on one side, and intuitively it seems that it would be a good idea to include $p$ in the MBHS solution, as it would hit every such biclique for the cost of just 1 vertex.  The problem is that it could be that every maximal IS in $G'$ is already hit by some vertex in the VC, meaning that it is not actually necessary to include $p$, and that doing so would therefore yield a suboptimal solution.  (This can happen when the given threshold $k$ is loose; in particular, it will always happen for $k=|V|$.  If OTOH $k$ is the minimal threshold for which the answer to the VC problem is YES, then at least one maximal IS misses every vertex in the VC solution, and we would be justified in forcing $p$ into the solution -- but we don't know whether this is the case at the point when we are mapping the VC instance to the MBHS instance, and it is NP-hard to find out!)  The general approach here, of trying to design a gadget that will cause all ISes in $G'$ to become edgy bicliques, can be expressed precisely as: Find a small graph that has an optimal MBHS solution with the additional property that every maximal IS in the graph is hit by some vertex in the solution.  But after trying several examples with 2, 3 or 4 vertices, I wasn't able to come up with such a gadget.


Is It possible to change the side of 0 and 1 in Huffman tree?

You can assign the $1$ and $0$ as you like, but be consistent. Only your code change, i.e. a 1011 becomes a 0100.


Computing all possible partial sum-function of a given set of numbers

There are ${N \choose K}$ subsequences of length $K$, so outputting $\mathcal{S}(\cdot)$ for all of them will certainly require an output of length at least ${N \choose K}$.  Thus, the running time has to be at least ${N \choose K}$.  Beware that this is potentially exponential in $N$, depending on the value of $K$, so for some choices of $N,K$ there is no hope for an efficient algorithm to compute all those values.

You can list all those values in approximately ${N \choose K}$ time.  Take any algorithm for enumerating all $K$-size subsets of $\{1,2,\dots,N\}$; then it is easy to turn it into an algorithm to do what you want, by keeping track of the product associated with each subset.  Note that when you add an element to a subset, with a single multiplication you can update the product (compute the product of the new subset, based on the product of the old subset multiplied by the new element that was added).


$Sat(EG^2\alpha)$ as a fixpoint of an operator

Let us prove that $EG^2\alpha$ is the greatest fixpoint of $\tau(Z):=\alpha\wedge EXEXZ$.
Suppose $s_0\in Sat(\tau(EG^2\alpha))$, then $s_0\in Sat(\alpha)$ and for some path starting at $s_0$, we have $s_2\in Sat(EG^2\alpha)$ where $s_2$ is a successor of $s_1$ and $s_1$ is a successor of $s_0$. That is, $s_0\in Sat(\alpha)$ and for some $\pi\in Paths(s_2)$, we have $\pi[2i]\in Sat(\alpha)$, $i\in \mathbb{N}$. Hence, $s_0\in Sat(EG^2\alpha)$.
Now, assume that $s_0\in Sat(EG^2\alpha)$, then for every $\pi\in Paths(s_0)$, $\pi[2i]\in Sat(\alpha)$, $i\in\mathbb{N}$. Therefore, $s_0\in Sat(\tau(EG^2\alpha))$.
We have seen that $EG^2\alpha$ is a fixpoint of $\tau(Z)$. Suppose, now, that $Y$ is a fixpoint of $\tau(Z)$, that is $Y=\tau(Y)$. Let us see that $Sat(Y)\subseteq Sat(EG^2\alpha)$. Let $s_0\in Sat(Y)$, then $s_0\in Sat(\alpha)$ and $s_2\in Sat(Y)$ for some $s_1\in suc(s_0)$ and $s_2\in suc(s_1)$. But then again $Sat(Y)=Sat(\tau(Y))$, so we have $s_0\in \alpha$, $s_2\in Sat(\alpha)$ and $s_4\in Sat(\alpha)$ for some $s_3\in suc(s_2)$ and $s_4\in suc(s_3)$. In the limit case, we get a path starting at $s_0$ that satisfies $EG^2\alpha$. Hence, $s_0\in Sat(EG^2\alpha)$.
To extend the CTL algorithm
$Sat(EG^2\alpha)$ is the largest $C\subseteq S$ ($S$ is the set of states) such that:

$C\subseteq Sat(\alpha)$;
$s\in C\Rightarrow\text{ for each }s'\in suc(s),\text{we have } suc(s')=C$.


Efficient method for generating the smoothing function

Suppose that we are substituting variable $x$.

You will have a lot of zeroes and ones in the circuit, so a simple simplification function should help a lot. Additionally a potentially large part of your circuit unrelated to $x$ might be duplicated, so I would suggest preventing its duplication in the first place.

First I would mark any inputs (including the constants $0$ and $1$) to the circuit that aren't $x$ as unrelated. Second, any gate that only has unrelated inputs is marked as unrelated itself. This is done repeatedly until the result is stable. Then, any unrelated subcircuit which has a related gate as parent is removed and replaced with a temporary variable (e.g. $t_1, t_2,$ etc) and it is for each temporary variable what circuit it corresponded to.

Then you should apply your smoothing function definition and minimize recursively using $S$, applying matching with priority from top to bottom:

$$\begin{align}
S(0) &= 0\\
S(1) &= 1\\
S(\neg 0) &= 1\\
S(\neg 1) &= 0\\
S(a + b) &= \begin{cases}
    1 & S(a) = 1 \vee S(b) = 1\\
    0 & S(a) = 0 \wedge S(b) = 0\\
    S(a) & S(b) = 0\\
    S(b) & S(a) = 0\\
    S(a) & S(a) = S(b)\\
    S(a) + S(b)&S(a) < S(b)\\
    S(b) + S(a)&\text{otherwise}
\end{cases}\\
S(a \cdot b) &=\begin{cases}
    1 & S(a) = 1 \wedge S(b) = 1\\
    0 & S(a) = 0 \vee S(b) = 0\\
    S(a) & S(b) = 1\\
    S(b) & S(a) = 1\\
    S(a) & S(a) = S(b)\\
    S(a) \cdot S(b)& S(a) < S(b)\\
    S(b) \cdot S(a)& \text{otherwise}\\
\end{cases}\\
S(\neg \neg a) &= S(a)\\
S(\neg a) &= \neg S(a)\\
S(a) &= a\end{align}$$

Note that all comparisons here are done simply on the symbolic formulas, with comparison done in any consistent order (such as an arbitrary lexicographic order). This minimization isn't very advanced, but runs very fast and fully eliminates any constants unless the entire circuit is constant. If your primitive gates aren't conjunction and disjunction you'll need a different minimization function, but I think the concept is clear.

After minimization is done you can add back the $t_1, t_2,$etc circuits and connect wherever they occur.

Practical algorithms aside, I don't believe that your intuition of the circuit becoming simpler is correct when truth tables are too large to be enumerated.

Let's do a napkin math calculation. Suppose you have 64 inputs and consider a 'reasonable' useful circuit any circuit with $\leq 10000$ binary gates, then there are $4\sum_{g=0}^{10000}\sum_{k=0}^{g} (64+k)^2$ possible circuits, assuming $4$ different gate types. That's approximately $2^{52}$ possible reasonably sized circuits.

There are $2^{2^{64}}$ possible truth tables. We haven't even scratched the surface of the surface of all possible circuits. There is plenty of space for combinations of reasonable circuits to blow up exponentially in size and I don't see reason to believe why they wouldn't - there's plenty of domain left to blow up into.


Breadth First Search Path Finding - Store Paths in Queue or Track Predecessors?

There's no set answer, as it depends on the number of nodes in the graph, the average number of nodes in the queue at any point in time, and the average length of paths.

"Considered better" is a matter of opinion, and on this site, we focus on technical questions rather than opinion.

If it were me, I would use predecessor pointers as my default, unless I had careful measurements showing that on my workload the other was better.


This is called the offline dynamic storage allocation problem. Check out the papers cited by https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 for a good review of the literature.


How to uniformly sample a sorted simplex

Yes, all you have to do is to uniformly sample a simplex, and then sort the elements, under the assumption that the given distribution on the simplex is invariant under the permutation of the coordinates and the probability of a 0-measure set is 0.

That assumption holds often by default. Hopefully it holds in your situation. otherwise, a different sampling method or some preprocessing/postprocessing may be needed.

Here is a simple argument that should convince you that uniformly sampling and then sorting results in uniform sampling, given that assumption. Suppose we get a sample $x<y<z$ in the end. It may come from any one of the six kinds of original sampling, $(x,y,z)$, $(x,z,y)$, $(y,z,x)$, $(y,x,z)$, $(z,x,y)$ and $(z,y,x)$. The original sampling is uniform everywhere, and hence uniform on a neighborhood of these six points. Combining six identical (small) disjoint neighborhoods of them and dividing by 6, we see that sampling and sorting is also uniform on a neighborhood of $(x,y,z)$. Since $(x,y,z)$ can be any given point with distinct coordinates and the set of all points with at least two equal coordinates has measure 0, the sampling and sorting is uniform on the whole sorted simplex.

A rigorous proof along the same line of reasoning can be written if we want to be more formal.


Explaining SAT to high school science teachers

The permanent is #P-complete, even when restricted to $\{0,1\}$-valued matrices. The permanent can be used to compute certain parameters in statistical mechanics, see for example this paper on the dimer covering problem. Since I'm not a physicist, I cannot comment on whether these theoretical statistical mechanics problems are really useful; I suspect that they are not directly useful, but the area itself could lead to useful insights. It could also be the case that some of these parameters are useful on their own, but you'll have to consult with an expert.
Your 5 minute pitch could go something like this:

Statistical mechanics is a beautiful and deep part of physics and chemistry which studies how the emergent behavior of large systems results from microscopic physical laws operating on individual elements. It explains phenomena such as the laws of gasses, magnetization, and transitions between different phases of matter. Statistical mechanics is intimately connected to probability theory, computer science, operations research, and data science.
Many important quantities in statistical mechanics can be formulated as instances of #SAT. An algorithm for solving #SAT exactly or approximately can thus be used to predict physical and chemical phenomena.

This might somewhat overstate the case, but that's how sales pitches go.


Meaning of the notation Typ := TVar | (Typ → Typ)

Intuitively, a type variable is like a variable in an expression, except that it stands in for a type rather than standing in for a number/bitstring/etc.

Formally, we choose a countably infinite set $\mathsf{TVar}$, and then define a type variable to be a member of $\mathsf{TVar}$.

The notation $\mathsf{Typ}:=\mathsf{TVar}|(\mathsf{Typ}\to \mathsf{Typ})$ is an instance of Backus normal form.  It is an inductive definition of $\mathsf{Typ}$.  It says that if $\alpha$ is a type variable (i.e., if $\alpha \in \mathsf{TVar}$), then $\alpha$ is an element of $\mathsf{Typ}$; and if $\alpha,\beta$ are type variables (i.e., $\alpha,\beta \in \mathsf{TVar}$), then the term $\alpha \to \beta$ is an element of $\mathsf{Typ}$.  $\mathsf{Typ}$ is the set of terms that can be constructed in this way.  We call a term a type if it is an element of $\mathsf{Typ}$.


Have block edit distances been computed on large code bases?

I do not know about publicly available tools to do it, but I did fair amount of diff related algorithms and one tool to check similarities between codes.

There are some basics to start with:

0) diff operates well on similar changed texts and falls into worst case when they are different.

1) Tools to check similarities on codes that I have seen, used and written were all operating on AST trees, disregarding formatting, variable and function names. Even though when codes exhibited packaging into functions it gave really hard time. So after that technique like SSA and strip code of functions was applied.

2) Languages that allow same thing to be done in several ways are to be treated as same expressions.

3) Sometimes code is translated into another language. So perfectly working transpilers should exist in first place. Every transpiler I have used was not fully functional, maybe I am not aware of new achievements, but as I checked there is no tool "write in any language you want and get source in any other".

4) There are situations like using well known algorithms, or copying from one book. Also there is probability that two codes are the same, or almost the same (same AST, same language), and are not copied.

5) There might be a lot of false positives, and even if we overcome above problems, what would be the outcome of such search?

There is no tool to produce comparable and working solution to JS. And nowadays many projects are getting JS spin off. Also with tools like emscripten (to operate on LLVM code) makes it virtually impossible to keep track of code.

If you take Levenshtein distance as a measure, you should probably consider above points. This seems convincing to me that it is really not sufficient to start tracking such changes in open source code, as there are tons of them.


What's a real life usage for detecting communities in complex systems?

Suppose you have a bunch of friends, regularly meeting together. Occasionally, you also visit your sibling, and they have their own friends. Can we extract these groups of friends just from knowing who's friends with whom on a social network? This is community detection, which is a form of intelligence gathering.


A private IP is not necessarily assigned by an ISP. It is actually a much more general concept: Any node (or cluster of nodes) realizing NAT separates two networks, a public and a private one. Most routers in home networks separate your internal network (private) from your ISP's or the wider internet (public). In the case of an ISP, it might be so that the ISP uses NAT to separate its own network of subscribers (private) from the wider internet (public), though not all ISPs have such a policy; actually some ISPs may even provide you with a reserved public IP (i.e., an IP which is accessible from the wider internet and which is statically assigned to you).

A private IP is only valid within its own network. In fact, the values for private IPs are standardized and are not routed in the wider internet. Thus, even if a node (e.g., a webserver) in the internet came to know the IP of your device in its private network—which, up to exploits, is unfeasible because of NAT—, it cannot really do anything with that IP unless it is also part of the device's private network: any packets sent to that IP will be immediately dropped (i.e., not routed) by the next node. Rather, what is logged in webservers and the like is the public IP of the NAT node through which you are accessing it.


How to prove that if the set and its complement are recursively enumerable, then both are recursive?

Roughly, yes, that's the right idea.

I think there are a few small issues though.

First, you can not compute the characteristic function $\chi_A$, since this is computable only when the set is recursive. What you can compute is the semi-characteristic function, whose domain is $A$, and is constantly $1$ there.

If we wanted to be more pedantic, "computing a function step by step" is not completely precise. One usually takes a "program" implementing the semi-characteristic (e.g. a Turing machine accepting each element of $A$, and diverging elsewhere) and executes that program step-by-step.

So, given two TMs $M$ and $N$ implementing both semi-characteristics, you can craft a new TM $O$ which runs them "in parallel, step by step" on the same input $w$. Eventually, one (and only one) of them will halt, and $O$ can accept or reject "w" consequently.

A completely computational-model-agnostic way to state "computing step by step" could be to exploit the Kleene's normal form theorem, where a number $x$ plays an equivalent role to the number of steps. While this is arguably the "true mathematical" way to do it, in computer science we often prefer to work with "programs" (TMs,...) since we find those more familiar.


How are logical addresses of instruction operands mapped to physical addresses?

Usually instructions are moved from RAM or from external memory to the processor’s instruction cache. Then the only address mapping is mapping a logical address to a cache line containing the instructions.

Most instructions are completely contained within one cache line, on processors with fixed instruction size each instruction is contained within one cache line. On processors with variable instruction length like intel processors the instruction decoder will read two cache lines if needed.


How to minimize this DFA using given algorithm?

The difficulty with the problem is, as Dean Gurvitz hinted and as you have experienced, not all transitions are specified explicitly. For example, given input 3 at state 0, what is the transition? According to the definition of DFA, every transition for any input symbol at any state must be specified.

You will ask then, why do I see such a graph for a DFA? What you see is a DFA specified as an incomplete DFA.

  some authors use deterministic finite automaton for a slightly different notion: an automaton that defines at most one transition for each state and each input symbol; the transition function is allowed to be partial. When no transition is defined, such an automaton halts.

To apply your procedure to minimize a DFA, you have to convert an incomplete DFA to a (complete) DFA. Add another state $R$, the rejected state. Whenever a transition from some state given some symbol is not specified, add a transition from that state given that symbol that goes to $R$. In particular, all transitions that start from $R$ go to $R$. Now that a (complete) DFA if formed, you can compute merrily with your procedure, treating $R$ just as any other non-final state. Once you are done with your procedure, you will have a (complete) DFA with minimal states. If preferred or necessary, you can convert the minimal (complete) DFA to an incomplete DFA by removing the (new) rejected state, i.e., the state that comes from $R$, and all transitions from or to that state.


Finding optimal sequence of questions to minimize total student time

I suspect the problem $\mathsf{TUT}$ to be NP-hard. I will show how to transform the problem such that it is strongly related to a problem which is NP-hard. (Yes, this is all rather vague. I basically think my general approach is correct, but I am currently unable to proceed.)

First, note that the problem $\mathsf{TUT}$ can be reformulated as follows:

Given a set of questions $Q$ of size $k$, a set of $n$ subsets $\mathcal{F}_Q\subseteq \mathcal{P}(Q)$ and an integer $C$, does there exists a sequence $\Sigma : \langle S_1,\ldots, S_k\rangle$ such that, for all $i \in\{1,\ldots,k\}$:

$S_i\subseteq Q$ and $|S_i|=i$; and
$S_i \subset S_j$ for all $j>i$; and
$\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$ ?

Note that the set $S_i$ represent the first $i$ questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.

Now, we restrict the size of the subsets in $\mathcal{F}_Q$ to $2$, so we can represent these subsets as edges on a graph where the vertices are the elements from $Q$. (A hardness result for this special case is sufficient for hardness of the general problem)

Now, the problem of minimizing $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ for a single $i$ (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub '$\mathsf{\text{Double max $k$-vertex-cover}}$':

  Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

This problem is NP-hard, since $k$-clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove $\mathsf{TUT}$ to be NP-hard, since we need to find the maximum for every $i$, while respecting condition 2. This conditions are not satisfied by every sequence $\Sigma$ that satisfies only condition 1 and 3: consider the graph on $7$ vertices with two disjoint cycles, one of size $4$, the other size $3$. For $i=3$, selecting all vertices in the $3$-cycle gives the maximum, while selecting all vertices of the $4$-cycle is optimal for $i=4$.

It seems that condition 2 makes the problem even harder and most certainly not easier, which means $\mathsf{TUT}$ should be NP-hard, but I haven't seen a method to formally prove this.

So, to summarize, I have reduced the question to the following:

Is it possible to include condition 2 to complete the hardness proof for $\mathsf{TUT}$?

Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ under condition 2 from $i=1\ldots k$, by finding all maximum 'extenstions' of all found maximum sets for $i-1$. This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in $k$. Additionally, I have not seen a method to determine whether a subset for some $i$ would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.


Estimating the range of $1$'s in an array of $0$'s and $1$'s

If c < 0.5 then this can't be done faster than O(n). Assume the array is all zeroes, with a single 1 somewhere in the middle. You have to examine array elements at least until you find the 1, or until you are left with an unexamined subarray of size 2cn. Since you have no clue where the 1 is, it might take n attempts to find a 1, and n - 2cn attempts until you can give a result with an error less than cn in i and j. (If you are left with an interval of size 2cn you just let i = j = middle of the interval).

Obviously if c >= 0.5 then you can let i = j = n/2, and the error is less than cn whatever the correct values are.


The way to view the lattice is by taking the two pieces one at a time. Firstly, you have the lattice:
$$
\begin{array}{c}
Clean \\
| \\
Dirty
\end{array}
$$
to capture that Clean data has higher integrity than Dirty data.

Similarly,
$$
\begin{array}{c}
DataEntry \\
| \\
Website
\end{array}
$$
captures that DataEntry data has higher integrity than Website data.

These can be combined (using the product of two lattices) into the following,
which captures all combinations and the relationship between them:
$$
\begin{array}{ccccc}
&& (Clean, DataEntry)  \\
& / && \backslash~~~~~~~~~~~~~~~~~~~~~~~~~ \\
 (Dirty, DataEntry)  &&&  (Clean,Website)  \\
&\backslash &&/~~~~~~~~~~~~~~~~~~~~~~~~~~ \\
&&     (Dirty,Website)
\end{array}
$$
The two middle elements are incomparable.

The paper Lattice-based Access Control Models by Ravi Sandhu gives a good overview of the application of lattices in access control models, including the Biba model.

If you want to learn the general theory about lattices, then Introduction to Lattices and Order by B. A. Davey and H. A. Priestley is a very good starting point.


How to extend a hash function to manipulate longer integers?

I believe Schrage's method is exactly what you are looking for.

But for a general method of computing $ax + b \bmod m$ where $a, b, x, m$ all fit in a single CPU word and all are unsigned values I can quickly explain a method. I assume a CPU word has size $2^w$ and overflow is just modulo $2^w$.

First, computing $x + y \mod m$. Reduce $x, y \mod p$ (not necessary if you already know $x, y < p$). Then, if $y \geq m - x$, overflow would occur. So in that case we compute $x + y - m$, otherwise simply $x+y$. In C++:

// Compute (x + y) % m, assumes x, y < m.
uint64_t addmodu64(uint64_t x, uint64_t y, uint64_t m) {
    return x + y - m * (y >= m - x);
}

Then, computing $xy \bmod m$ can be done by multiplication through repeated addition in $O(\log x)$ additions. We can repeatedly apply the following identity:

$xy \equiv (2\lfloor{x\over2}\rfloor + (x\bmod 2))y \equiv 2y\lfloor{x\over2}\rfloor + y(x\bmod 2) \mod m$

This gives a recursive function:

// Compute (x * y) % m, assumes x, y < m.
uint64_t mulmodu64(uint64_t x, uint64_t y, uint64_t m) {
    if (x == 0) return 0;
    uint64_t y2 = addmodu64(y, y, m);
    uint64_t r = mulmodu64(y2, x/2, m);
    if (x % 2) r = addmodu64(r, y, m);
    return r;
}

This is just for demonstration purposes, for a fast implementation you want to convert this to a loop without any calls.

Finally, computing $(ax + b \bmod p) \mod m$ then is as simple as addmodu64(mulmodu64(a, x, p), b, p) % m.


Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

Wikipedia has an extensive list of languages that use the off-side rule1:

  ABC
  Boo
  BuddyScript
  Cobra
  CoffeeScript
  Converge
  Curry
  Elixir (, do: blocks)
  Elm
  F# (if #light "off" is not specified)
  Genie
  Haskell (only for where, let, do, or case ... of clauses when braces are omitted)
  Inform 7
  ISWIM, the abstract language that introduced the rule
  LiveScript
  Miranda
  Nemerle
  Nim
  occam
  PROMAL
  Python
  Scheme, when using e.g. SRFI 119
  Spin
  XL

1: I've never heard this term before myself.


Hence, taking into account that FOL captures LOGSPACE, it should be possible to:

Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
It should be possible to define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)")

Actually this is not correct: first-order logic does not capture logspace. As you said earlier in your question, FOL plus deterministic transitive closure captures logspace, that is
$$
\text{FO(DTC)} = \text{L}
$$
but
$$
\text{FO} \ne \text{FO(DTC)},
$$
i.e. deterministic transitive closure is not definable in first-order logic.
More generally, FOL is quite limited. FOL captures a class called uniform $\text{AC0}$ (see the complexity zoo and Immerman's diagram); it is the class of queries computable in "constant parallel time". And transitive closure, even deterministic transitive closure, cannot be done in $\text{AC0}$ (with a circuit of constant depth). Even something very simple, calculating the parity of the number of input bits, can't be done in $\text{AC0}$.

How to describe Deterministic Transitive Closure in FOL?

To reiterate: it is impossible.


Numerical issues in solving linear systems

The $2\times 2$ matrix has determinant close to zero, and so its condition number is very large, causing numerical instability.

The explicit solution of your system is
$$
x=\frac{a}{a^2-b^2}, y=-\frac{b}{a^2-b^2}.
$$
Therefore
$$
x+y = \frac{a-b}{a^2-b^2} = \frac{1}{a+b},
$$
thus avoiding the numerical issues.


How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

The Arden's rule, as it is usually stated, is easier to use if you consider equations on $(L_q)_{q\in Q}$ depicting the language $L_q$ the automaton accepts from state $q$. Doing this, you obtain the following equations. Check that you understand this properly :

$L_0 = 0L_0 + 1L_0 + 0L_1$
$L_1 = 0L_3 + 1L_3$
$L_3 = \varepsilon$

(I use $L$ instead of $q$ as it looks less misleading to me)

Once you have those equations, you can solve this as follows

$L_1 = 0 + 1$ (I replaced $L_3$ with its value)
$L_0 = (0+1)L_0 + 0(0+1)$ (Replaced $L_1$ and factorized. This is ready for Arden's rule)
Since $\epsilon\not\in L_0$, from Arden's rule : $L_0 = (0+1)^*0(0+1)$

The language accepted by the automaton is always the union of the $L_{q_i}$, where the $q_i$ are the initial states. So here, $L = L_0 = (0+1)^*0(0+1)$


Which in-memory data structure can accommodate billions of md5 value?

Maybe you can use a binary trie (critbit tree?) that splits in two on each node instead of 256? Of course you get many more nodes, but they are a LOT smaller.
An example implementation in Java is here: critbit


This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up.

Encoding Numbers

The basic motivation is to compute things, as in doing arithmetics¹. The first thing to look at is how to represent numbers. There have been many approaches, using decimal or ternary and I think even octal systems, but in the end, binary won out. Now we know we have to build devices that deal with two values -- let's call them $0$ and $1$.

Note that there are also multiple ways to encode numbers in binary. After you build up your first processor, you realise advantages of doing things in certain ways. Popular examples are the two-complement and IEEE floats. For starters, restrict yourself to plain natural numbers.

Gates

Assume we use binary encoding. Think of how you learned adding in primary school and write down the same for binary numbers. As it turns out, the building blocks of Boolean algebra are already there for you; it is easy to build a basic adder (and other arithmetic functions) using logic gates.

How to build such gates is outside of the scope of computer science; eletrical engineering has provided multiple solution using e.g. tubes or transistors. Head over to Electrical Engineering Stack Exchange for questions on this.

Clock and State

Not all gates are equally fast and not all parts of a computation have the same number of gates. Therefore, we have to take extra care that individual operations do not overtake each other. It has proven useful to use a global clock; the result of a given network of gates is the state of the output wires at the end of the cycle (which may change wildly while the gates cascade towards their individual final states).

That means that results of one cycle may have to be stored until the next cycle starts, e.g. if you wire up loops. There are a number of basic elements you can use to varying effect, all build up from gates; some are called flip-flops. Those are also used to build registers, elements that store numbers for as many clock cycles as needed.

Architecture and Commands

Now you have a myriad of design choices to make. What arithmetic operations does your processor provide? What do your commands look like? It may be educational to look at the MIPS architecture whose early forms are easy compared to other designs. Have a look at the plans:

Original from http://ube.ege.edu.tr/~erciyes/CENG311

Essentially, it's fetching and and disassembling commands, a set of registers, an ALU and control. Commands encode which ALU operation to perform on which operands (by the number of the register they are held in), how to manipulate the program counter² or which register to load/store from/to memory³.

Further Considerations

By now you have a working processor in the modern sense, assuming you figured out how to build a memory and a way to feed it commands. On its way to a modern machine, many choices have to be made. Here are some:

Do you want a von Neumann architecture or would you rather keep commands and data separate?
Do you want regularity and simplicity or abstraction and space economy in your instructions?
Depending on your memory implementation, you might want to have caches.
Do you want your processor to handle multiple operations at the same time using a pipeline?
Are all operations (and memory addresses) available to all programs, or do you have an operating system?
How do you implement I/O?

Alternatives

The above is heavily influenced by how history turned out. In a different world with different minds, computers may work differently. In fact, there is a plenty of models of computation, some of which have advantages that make them useful as abstraction for real machines in many cases. There are also attempts to imitate the way our brains work, that is to enable neural computing, or more generally to exploit problem-solving and information-storing strategies observed in nature, most prominently DNA and quantum computing.

So maybe (hopefully?) the information above is all ancient history another 50 or 100 years from now.

All the fancy things we do with computers today are broken down into many small arithmetic tasks which the processor executes one by one.
If your model allows the program to manipulate control flow, this would be the memory address the processor gets the next instruction from. You can also conceive machines that only read a fixed set of instructions from, say, a tape. In fact, early implementations did that. No jumps meant no loops; a program was a completely unrolled/unfolded series of instructions depending on the data. Obviously, being able to use the same program for multiple input data is more powerful.
Assuming you have memory; your processor works fine without but can then only deal with so many values at once. Early computers did read in all their data from tapes and kept them in registers. There was no memory, let alone writable, persistent storage as we know it today.


Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT

Schaefer's dichotomy theorem gives you the answer. Apply it and see what you get, and let us know.

Looking at the modern formulation, in your case $\Gamma$ contains the three relations $\lnot x \lor \lnot y \lor \lnot z, x \lor \lnot y \lor \lnot z, x \lor y \lor \lnot z$. For each of these relations $R$, you have to go over the list of polymorphisms, and check whether one of them is a polymorphism of $R$. For example, to check whether the binary AND function is a polymorphism of $\lnot x \lor \lnot y \lor \lnot z$, you have to check whether
$$
(\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2) \\ \Longrightarrow \lnot (x_1 \land x_2) \lor \lnot (y_1 \land y_2) \lor \lnot (z_1 \land z_2).
$$
If every $R \in \Gamma$ has one of the six polymorphisms, then your problem is in P. Otherwise, it's NP-complete.


Determining whether a digital circuit is optimal

Use one of the standard techniques for circuit minimization.  As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place).

Circuit minimzation is NP-hard (in fact it's even harder than that, in some sense), so you shouldn't expect an efficient algorithm for it that handles all functions efficiently.


Difference between spanning tree and a tree?

Given a graph $G$,
a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$.

There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree.

Regular (sub)tree is just subgraph which is a tree - it doesn't have all the nodes in $G$: it satisfies property (i) above, but not necessarily property (ii).


Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?

To prove that it's false you just need a counter-example.

The two MST can be

Noticed that the only two common edge is not the lowest cost edge. Hence the statement is FALSE.

However, if all the edges have unique weights, the answer is TRUE.

  Any MST of a size larger than 1 contains the smallest and the second
  smallest edge.

The smallest edge must be in any MST. Suppose not, we can always include it and form a cycle, and remove the largest edge in the cycle to form a smaller tree.

The second smallest edge must also be in any MST (of the size larger than 1). Suppose not; we can include it and form a cycle. Noticed that a cycle must have at least 3 edges. Hence, the largest edge that is removed must be larger than the second smallest edge. Hence we also form a smaller tree.

Since any MST must contain the 2 smallest edge, when they only have 2 edges in common, it must be both of them, which are also the lowest costs edge in the graph.


Does every turing machine have an equivalent, single-state, n-tape turing machine?

Yes, there always exists a machine, and we really only need 2 tapes.

Your standard TM transition might be written:

$\delta(S_n, a) = (S_m, b, r)$

This would mean that, from $S_n$, if we read $a$, we would write $b$, move in direction $r$, and transition to state $S_m$.  We will allow our machine to move left, right, or stay in place ($<$, $>$, or $-$).

Now for the 2-tape machine, we'll go to our infinite shelf of Turing Machines and grab a standard two-tape model where both heads have independent left/right/stay capabilities.

As it turns out (just our luck!), on this machine, one of the motors actually broke a few years ago, so the second head can still read and write, but it can't move left or right any more.  Not to fear, we won't be needing that motor.  This machine will serve our needs just fine.

This model happens to be called the TwoTapey. On the TwoTapey, we could write a transition this way:

$\delta(S_n, a_1, a_2) = (S_m, b_1, b_2, d_1)$

This transition would mean that, from $S_n$, if the TwoTapey reads $a_1$ on tape 1 and $a_2$ on tape 2, it would transition to $S_m$, write $b_1$ on tape 1, $b_2$ on tape 2, and move head 1 $d_1$.  On a normal two-tape TM, we'd need a $d_2$ for the second head, but there's no need for that here, because that darned motor is still busted.

So, to translate our standard TM to the TwoTapey, we need to add each of our original state names as strings into the tape alphabet of the 2-tape machine.  Then, take each transition, and translate it this way:

$\delta(S_n, a) = (S_m, b, r)$

becomes

$\delta(S_0, a, ``S_n") = (S_0, b, ``S_m", r)$

The key is that busted motor.  Since we never move left or right on the second tape, this allows us to imitate our original states by simply using the second tape to hold our old state information.  This allows us to transition from $S_0$ back to $S_0$, but still utilize just as many transitions as we used to have in the original machine.

As CandiedOrange pointed out to me, this is actually a really good way to show that the hardware/software divide is artificial.  All state is just data, and all data is just state.


Is multiprocessing possible on a turing machine?

You can consider two variants of this question.

Can a Turing machine simulate parallelism?
Can a Turing machine simulate parallelism efficiently?

The answer for the first question is a resounding affirmative. Just like your own OS simulates threads on a single-core CPU, so a Turing machine can simulate parallelism.

Regarding the more refined second question, it depends on your definition of efficiency. You can probably simulate parallelism with at most a polynomial blow-up in resources (mainly time).

Turing machines are not a good model if you care about concrete efficiency. The more appropriate model is the RAM machine. RAM machines can probably simulate parallelism pretty efficiently, though you should not accept a running time any less that the combined running times of the individual threads in your parallel solution.


Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes)

Your attempt is wrong for several reasons:

If $L$ isn't regular then it doesn't mean that $L^p$ isn't regular. For example, let $L = \{ a^{n^2} : n \geq 0 \}$. Then $L$ isn't regular but $L^4$ is regular.
The language $L^p$ (the concatenation of $p$ copies of $L$) is not the same as the language $\{ w^p : w \in L \}$. For example, $\{a,aa\}^2 = \{a,aa,aaa,aaa\}$ whereas $\{ w^2 : w \in \{a,aa\} \} = \{aa,aaaa\}$.
To obtain your language from $L' = \{ a^{2^n} : n \geq 0 \}$ you will need to take the union of infinitely many powers of $L'$. There is usually very little you can say about infinite unions, since every language can be written as an infinite union of words.

One way to show that your language isn't regular is using the following criterion:

  Suppose that $L = \{ a^i : i \in S \}$ is an infinite regular language. Then $|S \cap \{1,\ldots,n\}|/n$ tends to a positive rational limit.

This criterion follows from the fact that $L$ is regular iff $S$ is eventually periodic.

The Erdős–Kac theorem implies that the fraction of numbers in $\{1,\ldots,n\}$ with at most two distinct prime factors tends to 0. In particular, if $S = \{ 2^k p : k \geq 0, p \text{ prime} \}$ then $|S \cap \{1,\ldots,n\}|/n \longrightarrow 0$. Since $L$ is infinite, the criterion shows that it is not regular.


First of all, let me recommend then you use parentheses. So $\Phi = \{P(a,f(a))\}$, and you're trying to derive $\exists y P(b,y)$ from this.

If it were $\exists y P(a,y)$ instead, the proof would be very simple. You start by using the $\Phi$-rule to deduce $\vdash P(a,f(a))$, and then using the $\exists R$ rule you deduce $\vdash \exists y P(a,y)$.

As it stands, you cannot deduce $\exists y P(b,y)$ from $\Phi$ since $\exists y P(b,y)$ is not logically entailed from $\Phi$. For example, consider the interpretation in which $f$ is the identity and $P(x,y)$ is true only if $x=y=a$. Then $\Phi$ holds but $\exists y P(b,y)$ is false. Since LK-$\Phi$ is sound, you cannot deduce $\exists y P(b,y)$ from $\Phi$.


Why doesn't the recursion theorem prove there is an undecidable finite set?

Your argument "goes backwards."

Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that no machine decides $A_R$, merely that $D$ specifically doesn't.

Basically, what you've written looks like this:

CLAIM: there is some $x$ such that no $y$ does [task involving $x$].
PROOF: picking some $y$, we build an $x$ such that $y$ does not do [task involving $x$].

And this isn't valid.

It may help to consider an argument of the same "shape" but about a more concrete topic.

CLAIM: there is a natural number $n>1$ which isn't divisible by any prime $p$.
PROOF: fixing a prime $p$, let $n=p+1$. Then $n$ isn't divisible by $p$.

The subtle nature of decidability often makes questions about it appear more complicated than they are, and I think this is such a situation.

It's worth noting that the recursion theorem can be applied here to show something - specifically, that the $A_R$s are not uniformly decidable.

Specifically, suppose I have some total computable function $f$. By the recursion theorem I can whip up a machine $R$ such that $R$ behaves as you describe for $D=f(R)$, and so $f(R)$ cannot decide $A_R$. This means:

  While for each $R$ there is some $D$ which decides $A_R$, there is no computable way to find such a $D$ given $R$.

This isn't surprising - the same result follows more simply from the unsolvability of the halting problem - but it is an important example of how the recursion theorem can be used to prove non-uniform decidability results even when each of the languages in question is decidable.


Lower bound on size of proof that a list of integers is sorted

When talking about proofs, you need to explain three things: (1) formal proof system, (2) what you want to prove, (3) what you want to prove it from.

You seem to imply that item 3 should be $n$ different axioms, listing the contents of the array. In that case, you're right that you will need to invoke all axioms to prove that the list is sorted, in any consistent formal system.

Another reason why the proof will need to be of linear length is that item 2, what you want to prove, might be stated as $A[1] \leq A[2] \land A[2] \leq A[3] \land \cdots \land A[n-1] \leq A[n]$.

However, perhaps it is the case that item 3 is a description of the algorithm, and item 2 is something similar to Gilles's formulation, $\forall i \in [n-1], A[i] \leq A[i+1]$. In that case, if the proof system is strong enough (say ZFC), then you should be able to prove item 2 in $O(\log n)$ by starting with a general correctness proof for your algorithm, and then invoking it for your particular $n$. If your proof system is too weak to prove something like that, you might still be able to prove that the array is sorted in $O(\log^{O(1)})$; the relevant subject is known as bounded arithmetic.


Big O vs Big $\Theta$ during coding interview

I think its fine. It just shows the interviewer you actually know what the real meaning of big-O and theta are. Just make sure its actually true (the $\Omega$ part) when you have a complicated algorithm and you have used some inequality for big-O complexity proof.


Partition points on a 2d plane with arbitrary line segment

Hint: Instead of storing them as cartesian points, store them as polar coordinates (with a tiny drop of preprocessing).


Detailed explanation about Damerau Levenshtein Distance algorithm?

The algorithm is based on dynamic programming. It computes a table $d[i,j]$ which stores the edit distance between $a_1\ldots a_i$ and $b_1\ldots b_j$. Although you only really need $i$ to range from $0$ to $\mathrm{length}(a)$ and $j$ to range from $0$ to $\mathrm{length}(b)$, some corner cases are handled by allowing $i=-1$ or $j=-1$ and letting the corresponding cells in the table have infinite cost (a large enough number is used instead of infinity).

The formula used to compute $d[i,j]$ given earlier parts of the table is explicitly found in the code, so I'll let you figure it out on your own.


Maximum amount of memory that can be allocated to a process

The main point I think is here the usage of paging without implementation of virtual memory(VM) techniques.

Nowadays it's rare, but once upon a time when the concept of VM was a dream paging was used for a different purpose. At that time the memory allocated to a process needed to be contiguous which usually lead to fragmentation (external) and hence bad utilization of memory. Then the concept of paging brought a revolution. Memory can be allocated to a process non-contiguously. The process memory space is divided into pages of same size. The Main Memory is also divided into same size frames and page size is equal to frame size. Page table of a process keeps track of the addresses of the frames. To be precise if the page table has $k$ entries it can have at most $k$ frames. For each frame, page table stores the starting memory address of that frame. Unlike the concept of VM all the frames need to be stored in main memory. Note that this might lead to another type of fragmentation (internal) as a process memory space size might not be multiplicative of page size. But, this is not that severe like the external one.

So, here in your question I think they try to mean this kind of scenario, paging without VM. Thus here also it is possible to limit the size of a process by using the page table in the similar manner you mentioned in your question for the case where we use VM.

But, my main concern is to convey the idea that we can indeed use paging without VM.


It's a valid proof in the sense that it convinces an appropriately skeptical reader that $\neg 0 = 1$. The argument is as follows.

By an axiom $0\vee \neg 0 = 1$.
We know that either $\neg0=0$ or $\neg0=1$.
We can't have $\neg0=0$ because $0\vee0=0$.
So it must be the case that $\neg0=1$.
Actually, let's check that: $0\vee 1=1$. Good.

However, that's not a proof from the axioms. Of the steps that you've used, only 1 is actually an axiom.

Step 2 is the law of excluded middle, which isn't actually one of the axioms. If you think about it, it's not actually obvious that every formula evaluates to exactly one of 0 and 1 (in particular, there are no formulae that evaluate to both 0 and 1, and none that evaluate to either).  The law of excluded middle can be proven from the axioms but it's not an axiom.

Step 3 uses an axiom ($a\vee0=a$ instantiated with $a=0$) to deduce that $0\vee 0=0$ but there's no axiom that says you can use this to conclude that $b\neq 0$ if $a\vee b\neq a$.

Step 4 is restating the law of excluded middle.

In step 5, you could use some axioms to deduce that $0\vee 1=1$ ($0\vee 1 = 1\vee 0 = 1$) but, again, there's no axiom allowing you to draw the ultimate conclusion.

Students often get confused about axiomatic proofs: the usual complaint is "I don't know what I'm allowed to use."  Confusion about that is very understandable: you've spent your whole life "knowing" that $\neg0=1$ and treating that as (half of) the definition of negation. If you're not allowed to "know" something as basic as how negation works, what on earth are you allowed to know?  (Students have exactly the same problems with elementary group theory.)

For an axiomatic proof, it's actually quite simple: you're allowed to use the axioms, instantiated however you please.1 If you can prove something from the axioms, you're allowed to use that repeatedly, as a lemma: for example, I proved above that $0\vee 1=1$ so you could use that as many times as you want, after proving it once. But that's all.

Alexey Romanov included a proof in his comment to the question.  I'll write it out a little more fully.

$$\begin{align*}
    \neg0
        &= \neg0 \vee 0 &\text{($0$ is the identity for $\vee$)}\\
        &= 0 \vee \neg0 &\text{(commutativity of $\vee$)}\\
        &= 1            &\text{(instantiate $a\vee\neg a=1$ with $a=0$).}
\end{align*}$$

Because of the limited resources available to you, axiomatic proofs tend to be rather fiddly and tedious, which is why we don't do them after the first week of the course. Pedagogically, I think it's actually a mistake to start with axiomatic proofs because they confuse the students more than they help. I think it would be better to introduce them later in a course, after the students are already used to proving things.

OK, and transitivity of equality and probably modus ponens. But I'm just putting this here for the experts to think about; for the beginner, this footnote is more likely to confuse than clarify.


Suppose that $f(x) = 0$. Then $g(f(x))$ is computable for any function $g$, computable or not. This explains 1.
As for 2, the composition of two computable functions is computable, so if both $f$ and $h$ are computable, so is $g$. Since $f$ is computable and $g$ isn't, the only conclusion is that $h$ is not computable.


I understood the problem as that we can select any $S_i$ satisfying these conditions. Then the answer is $\{0, 1, 2, 3, 4, 5\}$. The construction is unique in a certain sense.
Wlog we can assume that $S=A$ (otherwise, just remove redundant elements from $S$). I'll use $A, B, C, D, E$ instead of $S_i$. One way to arrive at a solution is to draw a Venn diagram for $A, B, C$ and to think about it:

What can we say about it:

$A \setminus (B \cup C) \ne \emptyset$. Otherwise $B \cup C = A \cup B \cup C = S$. Similarly for $B$ and $C$.

For $D$ we must have $A \setminus (B \cup C) \subseteq D$. Otherwise, $B \cup C \cup D \ne B \cup C \cup A = S$. Similarly for $B$ and $C$.

For $D$ we must have $A \cap C \setminus B \not \subseteq D$. Otherwise (just look at the diagram),
$$B \cup D = B \cup (A \setminus (B \cup C)) \cup (C \setminus (A \cup B)) \cup (A \cap C \setminus B) = S$$

What we said for $D$ also holds for $E$. I.e. it must contain the symmetric difference but must not contain $A \cap C \setminus B$ and similar.

We must have $D \cup E \cup X = S$ for $X = A,B,C$. Therefore, $D \cup E \cup (A \cap B \cap C) = S$. In particular, it means that $A \cap B \cap C \not \subseteq D \cup E$, since otherwise $D \cup E = S$.
Also, $S \setminus (A \cap B \cap C) \subseteq D \cup E$. Therefore, forgetting about symmetric difference:
$$((A \cap C) \cup (A \cap B) \cup (B \cup C)) \setminus (A \cap B \cap C) \subseteq D \cup E$$
Therefore, while $A \cap C \setminus B$ doesn't belong to either $D$ or $E$, it belongs to their union.

Note that conditions above are necessary and sufficient. Putting this together:

$A \setminus (B \cup C)$ must have at least one element, which also belongs to both $D$ and $E$. The same for $B, C$.
$A \cap C \setminus B$ must have at least two elements: one belongs to $D$, another belongs to $E$. The same for other pairwise intersections.
$A \cap B \cap C$ has at least one element, which doesn't belong to either $D$ and $E$.

Note that we've used all $10$ elements from $S$. All sets $A,..,E$ have $6$ elements, so we just select one of them to be $S_1$, and arrange elements in the sets so that $S_1 = \{0,..,5\}$


Running time for Testing Polygonal Neighbours for Intersection or Inclusion

In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons.

The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper.

However, even though I do not know why you are reading this paper, I'd advise against it. This paper is pretty old and the main result (the $n\log n$ segment intersection algorithm) has been both improved upon and better explained by other sources. If you did not have an introductory course on computational geometry or something similar, I advise you to look at a computational geometry /algorithmic geometry textbook or lecture notes first.


Is it possible to prevent arithmetic errors with a dependent type system?

In theory, you can do anything of this sort with dependent types! Typically you would define your own (dependent) type, say

b_int = {z : Z | MIN_INT <= z <= MAX_INT}

Depending on the "flavor" of your dependent types, you might need a bunch of functions for going from b_int to Z and vice-versa (for well-defined values).

and then your function f would have to be of type:

 f : b_int * ... * b_int -> b_int

Now the tricky part. First you have to specify all the arithmetic operators, say b_add : b_int * b_int -> b_int in terms of the "ordinary" add function add. Ah except this isn't quite right. b_add MAX_INT 1 shouldn't be allowed! So you would have to give it a stricter specification, along the lines of

 b_add : { (n, m) : b_int * b_int | MIN_INT <= n + m <= MAX_INT } -> b_int

Then you want to prove something along the lines of:

b_add_correct : forall n m, n + m = b_add(n,m)

where the pair (n,m) needs to be in the domain of definition of b_add. Here, again, there may be a lot of pain if you need to translate to and from the Z type of unbounded integers, depending on how explicit the sub-types are.

Similarly for division:

b_div : { (n, m) | MIN_INT <= n / m <= MAX_INT, m =/= 0 }

So, if your program only uses the bounded operations, then there should be no way of writing a type correct program that has overflow or NaN operations.

However, I hope to convince you as well that there may be a significant amount of pain if there are no natural inclusions of types into sub-types, b_nat -> Z and if proofs of the inequalities have to be carried around explicitly.

One example is if the coercion box : Z -> b_nat explicitly carries the proof of inequality, i.e. box actually has the type:

 box : (x : Z) -> (p : x <= MAX_INT) -> b_nat

(I'm omitting the lower bound for simplicity). Then the correctness for b_add might be something more like:

 b_add_correct : forall n m : Z, (p : n <= MAX_INT) ->
                                 (q : m <= MAX_INT) ->
                                 (r : n + m <= MAX_INT) ->
    n + m = unbox (b_add (box n p) (box m q) r)

Whew! It gets even worse if just applying a bop operation requires explicitly building a proof that some bound holds (for example if you know $n < m$, then you might want to use the fact that $m - n \neq 0$ to do division). That can make your program look quite messy, and be hard to write, since your proof obligations and program writing become inextricably linked.


What is the difference between a "meta model" and "design patterns"?

Design Pattern: It is a "good practice". It can be considered as a possible solution for a problem that may ofter occur. The solution usually comes from the experience.  Examples are MVC and Identify Field.

Metamodel: It can be considered as a set of rules, constraints and constructs that allow to model a problem.
As an example you can consider a map.

A map allows to model the reality, so a map can be considered the model. The metamodel of a map is the legend: the constructs that you need to use in order to represent borders, rivers, lakes,...

In your case Identify Field is just a good practice that you can decide to follow or not. It's not a constraint/rule.


You could use the digits $\{0,\dots,9\} =: \Sigma$ as alphabet and consider infinite words. A word corresponds then to a real number. Those are known as $\omega$ languages link. There are omega-regular languages too.

Edit: The set of all real numbers, $\Sigma^\omega$, forms an $\omega$-regular language of course.


System restarted before transaction is committed

The correct answer is (b) under the assumption that the recovery algorithm used is the undo-redo algorithm, which is one of the most commonly used, and which can be used if the DBMS adopts both the immediate update policy and the immediate commit policy (instead of the deferred update and the deferred commit policies).

The immediate update policy allows that updated pages can be written to the database before the transaction has committed; The immediate commit policy allows the commit record to be written to the log before all updated pages have been written to the database. Those policies require the use of Write Ahead Log (WAL) rule (write the updates to the log file before writing to disk) and of Commit rule (the after-images of the updates are written to the log file before the commit of the transaction).

Under this hypothesis, when a failure occurs, the recovery algorithm must undo all the transactions non committed, and redo all the transaction committed, going back in the log file until a checkpoint record is found or until the beginning of the log file.

So, the correct answer is (b) since also T1 must be redone. In fact, we do not know if its updates to the database have been written or not (as I said, assuming that we are in the case of immediate commit policy).


Longest Common Subsequence Via Dynamic Programming

Your question is clear and you are performing the method correctly, as far as see.

But it seems to be a misunderstanding about what the problem solves about strings.
The longest common subsequence problem is about find out a  subsequence of characters in the case of string, not necessary consecutive like substrings.

By example, some subsequences of AAGCT are: AG, AT, ACT, AGT


Do unconditional branches cause control hazards?

YES, unconditional jumps can cause a control hazard in a pipelined machine.

  we know with 100% certainly that B will be executed since an unconditional jump instruction A preceded it.

Well, we know, but the CPU does not know.
I mean, the CPU does know that we need to jump to B, but only after the CPU decodes the jump instruction and realizes that the instruction is a jump (to B). Until that point thee CPU did not know it is about to jump and during that period it continued inserting other instructions to the pipe (not necessarily from B).

When the CPU finds out it has a jump it is "too late": the pipe is already contaminated with other instructions.

In your example, the "contamination" is in fact the correct code, but in the general case it may a different code segment.


Find a strategy to evade hungry lions on the real line for the longest time

Assume you start at zero. Lion #i is at $d_i$ and wakes up at $w_i$. If there is no lion with $d_i > 0$ and $w_i < d_i$ then you walk to the right and are safe. If there is no lion with $d_i < 0$ and $w_i < |d_i|$ then you walk to the left and are safe.

Otherwise, you die. There is always an optimal strategy of the form "move to some point X and stop, then wait until lions force you to move, and die when two lions from either side meet" - the point X is obviously not known. The point X is limited; if for example $d_i > 0$ and $w_i < d_i$ then you can walk only $(d_i + w_i)/2$ before you are forced back.

Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.

(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).


Is this an example of a type-0 grammar that is not context-sensitive?

The language you state in the question, $L=\{ a^+b^+\} \cup \{a^* \}$ is is regular (even though expressed via a context-sensitive grammar) and thus it is not undecidable.

To generate an undecidable language, you can think of a Turing machine for that language, and try to simulate the behaviour of the TM by the grammar. For instance, the nonterminals can be the TM's state (and their position in the sentinel clause will be the head's position). Now a move of the head can be described by grammar transitions of the form $aQb \to Qab$ or $aQb \to abQ$, etc.


What is the name for a function's "return arity"?

The term "arity" would have been introduced to programming via formal logic and related fields (e.g. universal algebra). In the context of formal logic, there is little reason to allow function symbols to return multiple values even in the form of a tuple, and good reasons to disallow it.  Mathematically, a function $X\to Y\times Z$ is equivalent to a pair of functions $X\to Y$ and $X\to Z$. So we don't lose anything by disallowing functions into cartesian products. What we gain, though, is a uniform syntax, especially in the context of single-sorted logic which is the typical one in formal logic.

In a single-sorted logic, there is only one sort (base type), call it $S$, so all functions are of the form $S\times\cdots\times S\to S$, or more compactly $S^n\to S$. By disallowing functions into products, if we have a term $f(x,y)$ and a function symobl $g$ of arity 2, say, then $g(f(x, y), z)$ is always a valid term. If we allowed functions into products, we'd need to at least introduce the projections $\pi_i : X_1\times X_2 \to X_i$. This would require us to assume the products were associated in some particular way or we would need to allow a whole family of projections or we would need some syntax to "spread" the results into multiple parameters. Basically, the syntax of terms would become significantly more complicated for no real gain. These syntactic complexities are reflected in programming languages that have real multi-valued returns (as opposed to just a single-valued return of a tuple).

Single-sortedness is what allows us to reduce the arity to a number. Combined with the restriction that function symbols can only return into the single sort, everything you need to know about a function symbol for the purposes of syntax can be reduced to a single number. In multi-sorted logics, it makes more sense to view the arity as a list of sorts, but since the return type is no longer fixed something more like a type annotation, e.g. $(X, Y)\to Z$, makes more sense. These type annotations are more relevant than arity. They are what you need to tell if a term is well-formed.

Most programming languages don't support a true notion of multi-valued return, and many don't even have a good notion of tuple. Occasionally in more theoretical work, the term "coarity" is used for a return sort. In a single-sorted context, the coarity could be represented by a number, but in a multi-sorted, i.e. statically typed, context it would be more natural for it to be a list of sorts. Really, computational models where operations can produce multiple outputs are usually thought of with a circuit metaphor. In such cases, we'd talk about things like fan-in and fan-out, or in-degree and out-degree.


Minimal number of changes to make string into concatenation of $k$ palindromes

Let $s=s_1 s_2 \dots s_n$.
Suppose that you already know, for each substring $s[i:j]=s_is_{i+1}\dots s_k$ of $s$, the minimum number $D(i,j) $ of character substitutions needed to make $s[i:j]$ palindrome. These values can be found in $O(n^2)$ time using dynamic programming since $D(i,j) = 0$ if $i>j$ and $D(i,j) = D(i+1,j-1) + \mathbb{1}_{s_i \neq s_j}$ if $i \le j$.

Your problem exhibits the optimal substructure property. Suppose that you already known the beginning position $i$ of the last substring $s[i:n]$ of $s$ in an optimal partition: clearly you will need to make $D(i,n)$ changes in order to transform $s[i:n]$ into a palindrome. You are then left with the prefix $s[1:i-1]$ of $s$. This prefix still needs to be partitioned into $k-1$ nonempty substrings that are palyndromes. Fortunately this is exactly an instance of the problem you were trying to solve in the first place. You can exploit this property as follows:

Define $OPT[j,h]$ as the minimum number of character substitutions needed in order to partition $s[1:j]$ into $h$ substrings, each of which is non-empty and palindrome. If no such partition can exist, regardless of the number of character substitutions, let $OPT[j,h]=+\infty$.

By definition $OPT[0,0]=0$  (since $s[1:0]$ is the empty string) and, for $h=1,\dots,k$, $D[0,h] = +\infty$.

Moreover, for $i=1,\dots,n$ and $h=1, \dots, k$:
$$
OPT[j,h] = \min_{i=1,\dots,j} \left\{ OPT[i-1,h-1]  + D(i, j) \right\}.
$$

This gives you a dynamic programming algorithm with time complexity $O(k n^2)$.
The optimal solution to your original problem is $OPT[n,k]$.


Theoretical foundations of robust and distributed services

You might be interested in these papers:

The LOCKSS system
Publius: A robust, tamper-evident, censorship-resistant web publishing system
The Eternity Service
The Free Haven Project: Distributed Anonymous Storage Service
Freenet: A Distributed Anonymous Information Storage and Retrieval System
Tarzan: A Peer-to-Peer Anonymizing Network
Anonymizing Censorship Resistant Systems
Tangler: A Censorship Resistant Publishing System Based on Document Entanglement
The Economics of Censorship Resistance


Why does Skiena reserve space for n+1 adjacency lists?

Note that the author uses 1 instead of 0 as the starting point of an array $A$. In other words, $A[0]$ is wasted. For example, to initialize a graph:

for (i=1; i<=MAXV; i++) g->degree[i] = 0;

By the way, in the second edition of this book, it is (Section 5.2):

#define MAXV 1000            /* maximum number of vertices*/

typedef struct {
  int y;                    /* adjacency info */
  int weight;               /* edge weight, if any */
  struct edgenode *next;    /* next edge in list */
} edgenode;

typedef struct {
  edgenode *edges[MAXV+1]; /* adjacency info */
  int degree[MAXV+1];      /* outdegree of each vertex */
  int nvertices;           /* number of vertices in graph */
  int nedges;              /* number of edges in graph */
  bool directed;           /* is the graph directed? */
} graph;


How to iterate the Hardy-Ramanujan integers quickly

I'm very happy that the site linked me to How can I generate first n elements of the sequence 3^i * 5^j * 7^k?. It was a critical stepping stone, which enabled me to solve my own question after lots of thinking.

First I want to elaborate on that answer a bit, as it took me a while to understand and code it.
We want to iterate $3^i 5^j 7^k$.
The next element must be one of $3 x, 5 y, 7 z$, where $x, y, z$ is a previous number in the sequence. This is because $x < 3 x, y < 5 y, z < 7 z$, and $3 x, 5 y, 7 z$ satisfy the constraints.
For $x$, we start with the first element in the sequence. We increment it's position whenever $3 x$ is the smallest out of $3 x, 5 y, 7 z$. To see why, we've already included $3 x$ in the sequence, for all $x$s in the sequence so far. So the only possible $3 x$ that can be inserted in the sequence, is if $x$ is the new element we just inserted.
Similarly for $y$ and $z$.
The following code iterates this sequence:
def main():
    x = 1
    y = 1
    z = 1
    S = []
    x_iter = iter(S)
    y_iter = iter(S)
    z_iter = iter(S)
    for _ in range(20):
        m = min(3 * x, 5 * y, 7 * z)
        S.append(m)
        if m == 3 * x:
            x = next(x_iter)
        if m == 5 * y:
            y = next(y_iter)
        if m == 7 * z:
            z = next(z_iter)
    print(S)

The Hardy-Ramanujan Integers can be defined as the integers $2^{e_1} 3^{e_2} 5^{e_3} \cdots$, s.t. $e_1 \geqslant e_2 \geqslant e_3 \geqslant \cdots \geqslant 0$.
It seems that these two problems are related, and indeed they are the same, if we re-write the Hardy-Ramanujan Integers by removing the decreasing exponents constraint, as $2^{e_1'} (2^{e_2'} 3^{e_2'}) (2^{e_3'} 3^{e_3'} 5^{e_3'}) \cdots$.
Now the only issue is that compared to the previous problem, our list of bases is infinite. But note that a new prime $p$ can only be included in the sequence, if it's smallest form, $2^1 3^1 \cdots p^1$, is less than the next sequence element, produced with primes $< p$. So we only need to introduce a new prime when this occurs.
Before this occurs, The exponent of $p$ is 0. Any prime $> p$ will give a sequence element bigger than $2^1 3^1 \cdots p^1$, so does not yet need to be considered.
This gives the following code:
import math

from sympy import nextprime

def main():
    S = [1]
    primes = [2]
    next_prime = nextprime(primes[0])
    # The smallest Hardy-Ramanujan integer that includes `next_prime`
    next_prime_product = primes[0] * next_prime
    candidates = [1]
    candidate_S_indexes = [0]
    for _ in range(20):
        m_options = [
            math.prod(primes[:i + 1]) * candidate
            for i, candidate in enumerate(candidates)
        ]
        m = min(m_options)
        if next_prime_product < m:
            # Add a new prime & candidate
            m = next_prime_product
            primes.append(next_prime)
            next_prime = nextprime(next_prime)
            next_prime_product *= next_prime
            candidates.append(m)
            candidate_S_indexes.append(len(S))
        S.append(m)
        for i, m_option in enumerate(m_options):
            if m_option == m:
                candidates[i] = S[candidate_S_indexes[i] + 1]
                candidate_S_indexes[i] += 1
    print(S)

P.S. I saw some answer in Haskell in German before at:

A good algorithm for A094348?
A025487Haskell - seqcomp

but could not understand the German at all, nor the Google-translated version, nor the Haskell code. But I'm quite satisfied with my algorithm here. It feels pretty optimal.


Closure of regular languages under "inverse second half"

The white token is a placeholder, which just remembers the original state of the red token (of course, the roles of these two tokens can be switched); this is the state at which $M$ would be after reading $\alpha$. The red token corresponds to the $w$ part of the word, and the blue token to its $\alpha$ part.

When reading a symbol, the red token advances according to the rules of $M$, the white token stays put, and the blue token guesses a symbol and advances according to the rules of $M$ (in effect, it guesses one symbol of $\alpha$).

The machine accepts if the blue and white tokens are at the same state (so we guessed correctly the state at which $M$ is after reading $\alpha$), and the red token is at an accepting state of $M$ (so $\alpha w \in L$).


Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

There are two cases:

$P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.
$P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).

By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.

We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate any algorithm running in Polynomial time with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.

Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.

As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.


Algorithm favours CPU bound or I/O bound processes

First of all, let me clarify that the CPU Burst Time of a process has no relation with being a CPU or I/O bound process. A CPU bound process is one that spends most of its execution time at CPU and an I/O bound process is one that spends most of its execution time at an I/O device. Therefore, a process having small CPU burst time can also be a CPU bound process. Similarly, a process having very large CPU burst time can still be I/O bound.
For example, consider a process A having CPU burst time of 1ms and I/O burst time of 5 ms. It is clearly an I/O bound process. And a process B having CPU burst time of 10ms and I/O burst time of 5 ms is clearly a CPU bound process. But if we consider SJF or SRTF algorithms, they will definitely prefer the process A over B inspite of A being I/O bound and B being CPU bound because A has lower CPU burst time than that of B. Thus, it is incorrect to think that SJF favours I/O bound processes.
But, as I/O bound processes spend more time doing I/O than CPU, they will be sent to the waiting state more often.
(It has nothing to do with CPU scheduling as CPU scheduling is handled by Short Term Scheduler and waiting state is handle by Medium Term Scheduler). Once a process in waiting finishes its I/O, it now depends on the CPU Scheduler. Now, if any preemptive algorithm is being used, there are chances that this process will get execution (depending on the criteria). But if any non-preemptive algorithm is being used, this process won't get execution until currently executing process is finished. So, we can say that non-preemptive algorithms (kind of) favour CPU bound processes (as they spend more time at the CPU, so they have to face lower chances of waiting).


Need help understanding a derivation of "witnesses" for a Landau bound

They want to end up with  constant * n2  on the very-right.

They applied "make each term a constant times n2".


A processor that can only support one memory access per cycle can still be pipelined. Such a memory interface would represents a structural hazard for load and store operations. In addition, store operations would introduce the equivalent of a control hazard since they might change instructions that have already been fetched.

The structural hazard can be detected when the instruction is decoded and the pipeline stalled at instruction fetch at the appropriate point. This allows a load or store to execute at the cost of a pipeline bubble. For stores, the processor can speculate that a store does not address memory that holds instructions which will be in the pipeline (or at least that the store not change the semantics of any such instructions). This is comparable to predicting a branch. As branch prediction requires checking the condition and target, store conflict prediction requires a comparison of the store address with the addresses of all instructions that will have been fetched by the time the store data becomes visible to the instruction fetch stage. As a branch misprediction requires flushing the pipeline so would a store conflict misprediction.

If one allows a wider front end and buffering, the impact of the structural hazard can be reduced. Such buffering, even if it is after instruction decode, might be considered a cache.

A processor that breaks some instructions into multiple micro-ops and executes one micro-op per cycle could benefit from such a buffer even if only one instruction is fetched per cycle. Variable length instructions would naturally benefit from a buffer of fetched instructions since a fixed width fetch would often either fetch more than one instruction or fetch only part of an instruction.

If the data access width is greater than the typical instruction length, it also becomes natural to use this greater width for fetching instructions, buffering any excess.

The structural hazard related to loads and stores can avoided by multiporting (or accessing the cache twice within a single cycle) or pseudo-multiporting (banking) the memory. The processor would still have the quasi-control hazard for stores. The main benefits of such an implementation over having separate caches would be somewhat simpler handling of stores and faster operation when running self-modifying code. The processor could still handle the store issue with separate coherent caches, but implementing coherence and handling the delay in realization of stores in the instruction cache would add complexity.

I would argue that a modified Harvard architecture that implements a Von Neumann interface (i.e., is indistinguishable to software except with respect to performance) is Von Neumann. (Recent ISAs generally avoid such guarantees. The benefit of a simpler interface is generally not considered worth the complexity/performance tradeoffs.)