What mechanisms prevent a process from taking over the processor forever?

Various peripherals are connected to the main processor. When an event happens in a peripheral, the peripheral sets an electric signal which causes the processor to take some action. The act of setting this signal is called an interrupt request (IRQ for short), and the aftermath of the interrupt request on the processor is called an interrupt.

When a processor receives an interrupt, it typically does something like this:

Mask interrupts. This means that if other IRQs happen (coming from the same peripheral or a different one), they won't be noticed just yet: they will not have any effect on the processor until interrupts are unmasked.
Save the value of the program counter register to a register dedicated to that effect. Also save the value of a register that contains the processor mode (e.g. user mode, kernel mode, interrupt mode, …). Depending on the processor architecture, other registers may be saved as well (e.g. stack pointer).
Switch the processor mode to interrupt mode.
Read a value from a predefined address in memory, or from a register. This value is called the interrupt vector.
Jump to the address given by the interrupt vector.

The code at that address is typically kernel code. On computer architectures with memory access permissions, the kernel normally prevents unprivileged processes from setting interrupt vectors or from changing the code at that address. The kernel code typically begins by copying the saved register values into memory, so that they won't be forgotten if some other interrupt occurs.

One of the peripherals that can send interrupts is the clock. To avoid a process running forever, whenever the operating system kernel allows a process to execute (by branching to its code), it first programs the clock to send an interrupt at a certain time in the future, allowing the program to run uninterrupted only for a time slice.

If the process is still running at the end of the time slice, the clock interrupt occurs. The code at the interrupt vector is kernel code, so the process is no longer running: it has been preempted. The process's code and data are still around: the kernel can later decide to let the process execute some more by restoring the saved register values (finishing with the program counter).

After the kernel has finished its basic interrupt processing, and has performed whatever tasks it deems useful, it decides which process to execute next. This decision is called scheduling.

Some operating systems (mostly on tiny embedded systems) allow processes to run as long as they like. This is known as cooperative multitasking. (And some operating systems are even more basic: they only allow a single task at a time.)


Buchi automata in formal software verification

The fastest theoretical algorithm to solve Büchi Games in game graphs is presented in  [1]  and runs in $O(n^2)$: The algorithm uses a hierarchical decomposition approach. An easier folklore algorithm with $O(mn)$ running time using just the attractor concept is mentioned.

Büchi Games on graphs should be in linear time after computing the strongly connected components of the graph.

[1] Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition. J. ACM, (2014)


Complexity of two cycles which differ by $1$ in length

It belongs to NP obviously, and is NP-complete by a reduction from the Hamilton cycle problem on bipartite graph.

Given a bipartite graph with $2n$ vertices, add an isolated simple cycle of length $2n+1$. Since there is no odd cycle in a bipartite graph, the new graph has two cycles which differ by 1 in length if and only if there is a Hamilton cycle in the bipartite graph.


What are the tradeoffs in compiler development effort related to CISC vs. RISC?

CISC vs. RISC is just the wrong distinction.  There are some instruction set design decisions that matter to the compiler writer and others that don't, but this simply isn't one of them.

Variable instruction length vs. fixed instruction length pretty much doesn't matter.  Writing an assembler for variable instruction length requires you to do a little more bookkeeping, but once its done you never have to worry about it again.

You either want a lot of general-purpose registers or just one (e.g. an accumulator).  Register allocation is hard.  So hard it is difficult to even figure out the input parameters you are trying to optimize over (you'd like to minimize the number of spills at runtime, but you usually don't know how often any instruction is going to execute at runtime.)  If you have only one register then where you have to spill is pretty obvious, and if you have more registers than you need then a greedy heuristic will get you something pretty close to optimal.  When you have only half as many or a third as many registers as you need then good heuristics start to matter a lot.

Registers that are special-purpose (used implicitly in a few instructions) are fine, and registers that are general-purpose (can be used for different things in lots of different instructions) are fine, but trying to make a special-purpose register also general purpose is hard for the compiler.  For example the MIPS architecture's jump-and-link instruction uses R31 as the implicit place to store the return address.  R31 can also be used as a general purpose register, but the compiler has to "special case" it, so that's usually an optimization that takes a few years to get into the compiler.

Having more than one way to do the same thing is generally not helpful to the compiler writer.  The internal representation of the compiler is usually a graph where the nodes correspond to operations and the edges correspond to operands.  If there are multiple ways to do something (for example, lots of different addressing modes) then this becomes a graph tiling problem, which is hard.  The result is that most compiler writers just ignore any addressing modes beyond the simple ones.  Given the way modern microarchitectures work the main cost of not using the more complex addressing modes is that the instruction sequence takes up more space than it would in the optimal case.  There's a classic story from the 1980s about the VAX.  If I remember correctly, the VAX had a special call instruction that would also push arguments onto the stack.  It turned out that the longer instruction sequence that individually pushed the arguments and then did the call separately was faster.

Large constants are a pain, so this is a place where fixed-length instructions hurts rather than helps.  Sparc had something like 12 bits for constants, MIPS has 16, which is better (because then you can construct any 32-bit constant with at most two instructions.)  The larger the available constant fields are the less likely it is that you have to construct multi-instruction constant construction sequences.  (This is even more painful for PC-relative jumps and branches where usually you can fit a relative offset into the constant field, but sometimes not, in which case you need to save the PC in a register and manually add and subtract the appropriate constant.  Ick.)

Alignment can be an issue sometimes.  For example: some early SIMD instruction sets required that source memory operands be aligned at cache-line boundaries, which is almost impossible for the compiler to guarantee without inserting a bunch of extra code.  To be useful a SIMD instruction set needs to allow cache-line-unaligned loads, at least (aligning stores is easier when the loads can be unaligned, so that's less important.)


Construct Optimal Directory Trees Efficiently

One way is to use a Huffman code, over an alphabet of size $k$, whre $k$ is the number of letters you're willing to use on the keyboard.  Make the weight for an entry be the "probability" for that entry (how often that entry is selected).  Then a Huffman code will minimize the expected number of key presses.  There's a standard algorithm for constructing a Huffman code.

The potential drawback is that it doesn't use the keys of the keyboard in the way you suggest; rather than using up/down to move forward/backward in a directory, the $k=4$ keys are all treated as equal, and each keypress moves you one level down in the tree.  In other words, each directory has at most $k$ entries, and you select an entry with a single keypress.  You might or might not be happy with the user experience.  If you prefer, you can set $k=2$ and use only the up/down keys for selection (each directory has two entries; press 'up' to select the first or 'down' to select the second, and it will jump immediately to that entry).  This will require fewer key presses than the approach you are imagining, but does require you to find a way to name each of the resulting nodes in the tree with a human-understandable category (i.e., pick a name for that directory/entry).


Converting a recursive algorithm to a runtime function

The key is to use right - left as $n$ for the parameter of the runtime recursion. What is the size of the subparts?

Closer hint:

   Note that the algorithm separates the input part of the array in three approximately equal-sized parts; the first two are sorted recursively, the third with Mergesort. This should be reflected in your recurrence.

Almost finished:

   Assuming Merge3 runs in time $\Theta(n)$ und MergeSort in time $\Theta(n \log n)$, you get a recurrence of the form

 $\qquad\displaystyle T(n) \approx 2T(n/3) + \Theta(n) + \Theta(n/3 \log(n/3))$

 since all parts have size $\approx p \approx n/3$. Solve this with the Master theorem and flesh out the details.


Why is determining the size of a maximum independent set or a clique in P?

I would be interested to see what you read, but determining the size of the maximum independent set is $NP$-hard (of course clique is equivalent, so I'll just talk about independent set). Recall that the decision problem "Does the graph $G$ contain an indepedent set of size at least $k$?" is $NP$-complete. If we could determine the size of the maximum independent set ($\alpha(G)$) in polynomial time, we could answer this decision problem in polynomial time by taking $G$, getting $\alpha(G)$ from our polynomial time algorithm, then if $k \leq \alpha(G)$, we say $Yes$, if $k > \alpha(G)$ we say no. Hence a polynomial time algorithm for determining the maximum would immediately give us $P=NP$.

Perhaps you read that determining the size of a maximal independent set is poynomial time solvable. A maximal set is just one that cannot be made larger, so we can (typically, and certainly for independent sets) compute these greedily.


What specifically makes quantum computers useful?

Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. In a quantum computer, it can make the outcome less likely.

Quantum algorithms are carefully designed so that wrong answers tend to be destructively interfered, leaving only the desired solutions as measurement outcomes. This is tricky to do, and not every problem allows for it. Grover's Search Algorithm is an excellent example of this effect, so here's a beginner-level post about Grover's algorithm.

Other useful properties quantum computers have access to:

Entanglement for coordination and communication improvements (e.g. symmetry breaking, superdense coding, beating bell tests).
The uncertainty principle for cryptography (e.g. quantum key distribution, Einstein-certified random numbers).
Manipulating actual physical states to implement quantum sensors and other lab equipment (who wouldn't want a counterfactual bomb tester?).

(Scott Aaronson likes to say everything interesting about quantum is due to superpositions preserving the 2-norm instead of the 1-norm like probability distributions do. All the more specific useful effects I mentioned do derive from the underlying math.)


Finding the k-shortest path between two nodes

In the $k$ shortest path problem, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein [1] has an algorithm running in $O(m+n \log n + k)$ time to find the $k$ shortest paths (allowing cycles) between a pair of vertices in a digraph. With the techniques of the paper, one can also find all path shorter than some given threshold, within the same time bounds. There is a vast literature on the subject, the Eppstein paper includes many references and discussion.

If you disallow cycles, you might want to look at the algorithm of Hershberger et al. [2].

[1] Eppstein, David. "Finding the k shortest paths." SIAM Journal on computing 28.2 (1998): 652-673. [CiteSeerX]

[2] Hershberger, John, Matthew Maxel, and Subhash Suri. "Finding the k shortest simple paths: A new algorithm and its implementation." ACM Transactions on Algorithms (TALG) 3.4 (2007): 45. [CiteSeerX]


How to get enclosed spaces from a series of connected nodes

One approach is to use a data structure for representing a planar graph.  Each node corresponds to a vertex in the graph, and each walls corresponds to an edge in the graph.  Then, you are looking for the set of faces in this graph.  Standard data structures for representing planar graphs should make it easy to retrieve the set of faces.

For instance, one standard data structure is the DCEL data structure.  It explicitly contains one record for each face, so once you have converted this to a DCEL data structure, then it is straightforward to iterate over all faces.  There are standard algorithms for constructing a DCEL data structure from the set of vertices and edges.  Or, instead of a DCEL, it looks like you could alternatively use a quad-edge data structure or a winged-edge data structure.  The keyword is to look for data structures for polygon meshes.  This has been studied in great detail in the computer graphics and computational geometry fields.

Alternatively, you could solve your problem directly.  For each node, find all of the walls associated with it, sort them by their angle, and store that sorted list associated the node.  After doing that for all nodes, then you can iterate through all rooms.    Pick an wall, then you can find the room to the "right" of that wall by simulating the left-hand rule: stand to the right of that wall, put your left hand on the wall, and walk forward, going in a circle around the perimeter of the room.  To simulate that rule, as you walk forward, you'll walk to the endpoint of the current wall; at that node $d$, to find the next wall you proceed to, look in the sorted list of walls incident on $d$, and find the next one in sorted order, then follow that wall.  It might be a bit trickier to work out the details of this, than to use an existing implementation of a DCEL data structure.


Let's start with $n$ axis-aligned rectangles, since there is a kind of easy direct argument.  We'll sweep a vertical line.  The events are the endpoints of horizontal edges of the rectangles.  As we sweep we maintain a set of intervals on the sweep line that are "uncovered" by $R_i$, $i\ge 1$:

Add the vertical interval covered by the rectangle $R_i$ to the sweep line when we first encounter $R_i$
Remove the vertical interval covered by the rectangle $R_i$ from the sweep line when it moves past $R_i$

It's easy to do this with a binary tree so that updates take $O(\log n)$ time.  (The problem is, essentially, 1-dimensional.  You figure out if the endpoints are in an uncovered interval and extend/merge appropriately when adding and lengthen them when removing.)

Then you just check that, in the span of $R_0$, none of the uncovered intervals ever intersect the vertical span of $R_0$.  The whole thing is $O(n\log n)$ time an $O(n)$ space.

For the general case, the obvious trick is not quite so fast.  Use the standard sweep line algorithm to compute the whole planar subdivision induced by the rectangles.

Clearly some disk-like set $F'$ of the faces covers $R_0$.  By itself, this doesn't tell us enough, since what we are interested in is whether any of these faces is inside $R_0$ and outside the other rectangles.  To do this, we modify the construction a little bit, so that when we add an edge, we tag one side with the identity of the rectangle it's inside.  This adds $O(1)$ overhead, so the construction is $O(n^2\log n)$ time; with no assumptions on the rectangles, the output can be $\Omega(n^2)$ in size, so we are using that much space in the worst case, so the time is, "existentially optimal" though not "output sensitive".

Finally, $R_0$ is covered so long as none of the faces in $F'$ have only edges not tagged as being in one of the $R_i$.  The point is that if an edge of $f$ is in $R_i$, then the whole of $f$ is as well. Imagine sweeping a line over $f$ orthogonally along this edge: it can only leave $R_i$ either outside of $f$ or $f$ is bounded by more than one edge of $R_i$.

So the conclusion is that the special case is $O(n\log n)$ and the general one is $O(n^2\log n)$ at least, but I suspect it can be improved.


Is EXPTIME "solvable" or "checkable" in exponential time?

A language $L$ belongs to $\mathsf{EXPTIME}$ if there is an algorithm deciding it which runs in time $O(2^{n^k})$ for some $k$.

A language $L$ belongs to $\mathsf{NEXPTIME}$ if there is an algorithm verifying it which runs in time $O(2^{n^k})$ for some $k$. In other words, a language $L$ belongs to $\mathsf{NEXPTIME}$ if there is a constant $k$ and a machine $M$ running in time $O(2^{n^k})$ such that $x \in L$ iff there exists $y$ of size at most $O(2^{|x|^k})$ such that $M(x,y) = 1$. Alternatively, a language $L$ belongs to $\mathsf{NEXPTIME}$ if it can be decided in nondeterministic time $O(2^{n^k})$ for some $k$.

You observe correctly that every problem in $\mathsf{NP}$ has an $\mathsf{EXPTIME}$ algorithm, that just goes over all possible witnesses. This shows that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. It is conjectured that the two classes are distinct. In contrast, it is believed that $\mathsf{EXPTIME} \neq \mathsf{NEXPTIME}$, and this is stronger than (i.e., implies) the more famous conjecture $\mathsf{P} \neq \mathsf{NP}$, through a padding argument.

Note that nondeterministic computation can still be time-bounded. For example, $\mathsf{NP}$ is the class of languages computed by nondeterministic polytime algorithms. The nondeterministic time hierarchy theorem shows that $\mathsf{NP} \neq \mathsf{NEXPTIME}$; similarly, the deterministic time hierarchy theorem shows that $\mathsf{P} \neq \mathsf{EXPTIME}$.


What class of problems does this problem belong to

The algorithm that you have found is an example of a "greedy algorithm". When trying to find an algorithm for a problem there is a small bag of standard tricks that you can use but these are quite limited and for most problems, there's no easy solution: you have to "go down the long and winding route".

The trick here was to recognize that this problem has a property known as "optimal substructure": a solution to the problem consists of making some top-level choice, and then solving a smaller subproblem. The optimal substructure property states that any optimal solution consists of a top-level choice, and then an optimal solution to the subproblem (the way to solve the subproblem does not depend on previous choices).

If your problem has optimal substructure you can try solving it with dynamic programming (but that does not give a polynomial algorithm here because the problem does not have sufficient overlap between subproblems). Another option is using a greedy strategy, which happens to work here. The greedy strategy is (simply put): define some criterion by which to pick the locally "best" top-level choice and do not consider the possibility of making any choice.

In this case, the "right" criterion apparently is the expected cost of accomplishing that task by using that method. This intuitively makes sense (the option with highest success/cost ratio should be the one you try first) but to show that this choice indeed results in an optimal order, you have to show that the problem, coupled with this criterion, satisfies the "greedy choice property": any solution that does not use the "best" choice, can be modified to a solution that uses the "best" choice and whose objective value is at least as good or better as the objective of the solution that does not use the "best" choice. You can usually show this by some sort of exchange argument ("suppose the solution does not start with the best success/cost ratio, consider what happens if we swap the first step in the solution with the best success/cost ratio one, then the objective can only improve,...")


If you want to solve this in practice, I would suggest that you formulate it as an instance of integer linear programming (ILP).

You can have a variable $x_i$ for each article that is one if we buy the $i$th article, or $0$ otherwise.  Now you get some constraints.   For instance, if I want 2 of the Dreadlord card, and they're offered in the 3rd, 7th, and 8th articles, then I get the constraint that $x_3+x_7+x_8 \ge 2$.  The objective function is your total cost.  You want to minimize your total cost, subject to the requirements.

Here's how you can model the total cost.  The only tricky bit are the shipping costs.  For simplicity, assume that the shipping cost from a seller is fixed no matter how many items you buy from that seller.  To help with modeling the shipping costs, introduce a variable $y_j$ for each seller, where $y_j=1$ if you buy anything from the $j$th seller and $y_j=0$ otherwise.  Now use the "logical OR" construction from here to relate the $y_j$'s to the $x_i$'s.  For instance, suppose that articles 4, 5, and 9 are from seller 2.  Then you add the linear inequalities $y_2 \ge x_4$, $y_2 \ge x_5$, $y_2 \ge x_9$, $y_2 \le x_4 + x_5 + x_9$, $0 \le y_2 \le 1$.  Do this for each seller.  Now, the total cost is
$$\sum_i c_i x_i + \sum_j c'_j y_j,$$
where $c_i$ is the per-item cost of the card in the $i$th article and $c'_j$ is the shipping cost of the $j$th seller.  This is the objective function that you're going to try to minimize.

Then, throw an off-the-shelf ILP solver at the resulting set of constraints.

This problem is likely to be NP-hard, so in principle there might not be any efficient solution... but in practice ILP solvers are surprisingly good, so I bet they'll give you a pretty good solution to your problem.

Possible complications and details:  If the seller has multiple copies of a card available, we need to modify the above.  You can have $x_i$ count the number of them that you buy from that seller (instead of being 0 or 1).  Also, we need to modify the construction of the $y_j$'s, as follows.  For instance, if article 5 is from seller 2, and article 5 offers up to 17 copies of the Dreadlord card, then instead of $y_2 \ge x_5$, you should use $17 y_2 \ge x_5$ (this ensures that if $x_5 \ge 1$, then $y_2$ is forced to be $1$).

If the shipping cost is not constant per seller, then you might need a more complex model of the cost.  However, here's one simple case that you can handle without difficulty.  Suppose that the shipping cost for seller 2 is \$3 plus \$0.50 per card ordered.  Then you can treat this as a fixed shipping cost of \$3 (regardless of how many cards are ordered), and increase the per-item cost of each card offered by that seller by \$0.50.  If the shipping cost is a non-linear function of the number of cards bought, then you might need something fancier: in that case, you might want to ask a follow-up question about how to model that specific nonlinear function, and specify the nonlinear fucntion.  Or, you could approximate the shipping cost by a linear function and solve the ILP problem anyway, to get something that might be close to optimal, even if your model isn't perfect.


Order-preserving update of a sublist of a list of mutable objects in sublinear time

At the time of writing I was not absolutely sure what the problem
was. This lead to a more general second answer. See details in
discussion at the end of this answer.

Apparently, the "idea that does not work" does not work because you do
not know the index of an element $S_i$ in $F$ organized as a tree.

This is what is addressed here. The problem is restated for clarity, as your statement of it is a bit hard to follow.

Restatement of the problem:

Given a set $S$ with an order relation, maintain an ordered list $F$
where elements of $S$ can be inserted or removed, and such that the
index of an element in $F$ is returned when the element is inserted.

Actually, the solution will do more, as it is possible to access any
element of $F$ given its index, or to retrieve the index given an
element of $F$. All operations are in time $\log n$.

Solution:

You keep the ordered derived list $F$ in a self-balancing binary
tree. I checked with AVL trees, but other types (such as red-black
trees) should work as well. In each node $N$ of the tree you keep a
count $\text{weight}(N)$ of the number of elements of $F$ in the subtree
rooted in $N$, node $N$ included.

This can be done by updating weight counts as you walk down from the
root of the AVL tree for $F$ to reach the place for the insertion or deletion.
Then, during the retracing phase that rebalances the tree, when
needed, you also update the weight counts according to the
rebalancing.  That only add constant cost to each elementary step,
thus does not change the $\log n$ time complexity of the algorithm.

Hence it is easy to use this weight to compute in $\log n$ time the
index of an element of the list $F$ when accessing it, either on the
way down from the AVL tree root, or by walking up to the root when
accessing the element directly.

The index is computed on the fly by adding the weights of all the immediate
siblings on the left of the path from the AVL tree root to the
concerned element of $F$.

Conversely, it is easy to find in $\log n$ time an element of $F$ from
its (left to right) index by walking down from the root and leaving
enough elements on the left.

Computing the index of $S_i$ in $F$ using weights:

Recall that the weight of a node $N$ is the number of nodes in the subtree rooted at $N$, node $N$ included.

Computing the index of $S_i$ from the weights in the tree is precisely
done as follows: you simply do a search for $S_i$ in the standard way of
binary search trees, with a modification to compute the index. Below
is a pseudo-code recursive version, adapted from the searching algorithm in
wikipedia. It raises an exception if $S_i$ is not in the AVL tree, and
the index count start at 0 for the first element. To have the count start at 1, the first return statement should be return node.left.weight+1.

function Find-recursive(S_i, node):  // call initially with node = root
    if node = Null then
        raise Key_Not_Found
    else if node.key = S_i then
        if node.left = Null then return 0
        else return node.left.weight
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        if node.left = Null then return Find-recursive(key, node.right)+1
        else return Find-recursive(key, node.right)+node.left.weight+1

When the path from the root goes to the right daughter, that means
that all nodes in the left daugther subtree, plus the current node, precede
$S_i$, and have to be added to whatever other predecessors will be
found while searching in the right daughter subtree.

I do not give here the modifications of the insertion and deletion code necessary to update the weight count, as this is a bit too long for an answer here, and not so hard to do.

About the question, and the two proposed answers

The precise specification of the problem took some time to agree upon.

This first answer to the question was written on the basis of an
initial specification that did not mention explicitly that the source list $S$
could be modified dynamically, by insertion or deletion, thus possibly
inducing a similar modification in the filtered list $F$.

The elements of list $S$ are mutable objects and have a filter-property
$P_F$ that may be true or false depending on operations performed on
an element. The purpose of the question is to maintain a sublist $F$ of
elements $s\in S$ such that $P_F(s)$, similarly ordered, such that the
rank in $F$ of an element $s\in S$ is known when it in inserted in $F$ due to
a mutation.

I assume in this first answer here that the list $S$ is constant,
except for changes to its mutable elements. Thus on may see the list
$S$ as a set (of list elements), totally ordered by the order of the
list, and that relative order of two elements can be checked in
constant time $O(1)$, for example by attaching its $S$-list rank to
each element.

In a much later comment to this answer, the author of the question
made it clear that he also wanted to be able to modify the list $S$
with insertion or deletion of elements. This more complex question is
addressed  separately in a second answer.

Why keep both answers? The first algorithm here is slightly more
efficient as all operations can be performed in time $O(\log|F|)$,
while the more general algorithm (second answer) requires time
$O(\log|S|)$. With a constant ratio $|F|/|S|$, the difference is only
an additive constant $\log|S|-\log|F|$. However this constant is to be
compared to a logarithmic complexity $\log|F|$, which may not be very
large itself. And this complexity is that of elementary operations on
a data structure, to be repeated often in larger algorithms. So this
apparently negligible difference may have a measurable impact on
performance of a larger algorithm using the structure.

To see it numerically, assume that $|S|=256$ and $|F|=16$. Then
$\log|S|=8$ and $\log|F|=4$, which give a performance ratio of $2$,
to which one should add that the structure of the more general
algorithm may be more costly to maintain.


Primal-dual schema in approximation algorithms

You are asking many questions. I will only answer the first.

The answer to the first question is that in linear programming we cannot enforce the variables to be integers. Therefore the optimal solution could be fractional. Consider for example the vertex cover problem for a graph $G = (V,E)$:

$$
\begin{align*}
&\min \sum_{v \in V} x_v \\
s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\
& x_v \in \{0,1\}
\end{align*}
$$

This is an integer program whose LP relaxation is

$$
\begin{align*}
&\min \sum_{v \in V} x_v \\
s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\
& 0 \leq x_v \leq 1
\end{align*}
$$

Now take the case of the triangle. The smallest vertex cover has size 2, but the optimal solution for the LP is $(1/2,1/2,1/2)$. As you can see, it isn't integral.


How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra?

As to the question what benefits it would give you, the answer is simplicity.

Modern programming languages are large beasts with complicated semantics, starting with syntax, and not ending with the rules for integer and floating point arithmetic (real languages, as you know, don't work with 'mathematical' integers and reals, but rather with finite approximations). A calculus boils programming languages down to some essentials of interest, in the case of CSP to agents that synchronise on names. This makes thinking about, and proving things to do with synchronisation much easier than doing so using a fully blown programming language. If you are not primarily interested in looking at computation from the point of view communication patterns engendered by synchronisation, then, maybe, CSP is not the right calculus for you.


Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

If you allow sets to repeat, then you can show that this is still NP-hard by making all the weights equal. The idea is to reduce from unweighted maximum coverage to your version of maximum coverage. Given an instance of unweighted maximum coverage, where element $e_i$ appears $w_i$ times, let $W = \max_i w_i$, and for each element $e_i$ of non-zero weight, add $W-w_i$ sets of the form $\{e_i\}$. In the new instance, each element appears the same number of times, so all have the same weight; and one checks that the added sets cannot improve the optimal solution.

If you insist that the sets are disjoint, you repeat the same construction, but to each set in the construction (old and new) you add a unique dummy element. This increases the value of each feasible solution by exactly $k$.


What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating?

Maybe approach it from a "BTU's needed over time" standpoint. I don't know the exact maths off the top of my head, but consider:

What is the temperature differential?
What is the heating capacity (BTU's) of the radiant flooring system?
How long does it take to start rendering 68% of that heat to the room?
What is the heating load of the room in BTU's?
How efficient is the heat generated?

Then do some math on these numbers. Something like...

$t_{hours}=\dfrac{(T_{end}-T_{start})\cdot H_{demand}}{H_{supply}}\cdot \mathrm{eff}^{-1} + t_{delay}$

So for an end temperature of 22°C and a start of 18°C, heat of 50kBTU, demand of 20kBTU, 90% efficiency, and 15 minutee delay:

$\begin{align*}t_{hours} &= \dfrac{(22°C-18°C)\cdot 20k_{demand}}{50k_{heat}}\cdot 0.90_{\mathrm{eff}}^{-1} + 0.25h_{delay}\\
&= \dfrac{80\mathrm{k}}{50\mathrm{k}}\cdot 1.\bar{1}+ 0.25\mathrm{h}\\
&= 2.02\bar{7}\mathrm{h}
\end{align*}
$

Some analysis and experimentation will be needed to arrive at realistic values but hopefully this is a start.


Is it theoretically exist a computer that never affected by computer virus?

Do you mean "that cannot be affected" or "that was never affected"?
Then, under what conditions? Do you mean malware in general or a more
restrictive notion of virus? And then, what is virus or malware? Is
code for automatic update of your OS considered malware or not? Maybe
you do not want to update your OS. Maybe someone has taken control of
the updating service to introduce undesirable features in your system.

The main problem with your question is probably the word
"theoretically". What is a theoretical computer?  If it is a Turing
Machine, the answer is clearly yes: they do what their finite control
says they should do. Period.

Is there a fully precise theoretical model of a real computer. That is
doubtful, if only because it is a complex physical objet and there is
a limit to our ability to fully model such an object, since
our knowledge of physics is not complete ... though I doubt that is
the main issue.

Assuming we could completely model the physical computer with a formal
system, do we fare better? Now we have (or shall have) all these great tools for
proving theorems about computers and programs. But this has limitations too. Gödel
says that not all true facts are provable, especially in a theory that
can model that much computation. But even without falling in this
black hole, do we fare better?  No because before proving anything
about the computer we need to model precisely what a computer is, and
also what it means to be affected by a virus. Even if we have a
perfect and total proof system (which we do not), how do we prove that
our theoretical specification of the problem is accurate with respect
to the physical problem with real computers. Bugs are not the
exclusive privilege of programs and proofs, you can also have them in
specifications, and some may be hard to eradicate. If your child
specifies he wants a train as a gift when it is actually a car that he
wants, what are the formal tools that will identify the specification
error - short of implementing and observing that things do not behave
as expected.

Coming back to a more practical view. Some machines are harware
protected with encryption keys that allow only trusted software.
First, many people consider this as malware by itself, as it is often
used against the owner of the computer. Then encryption can be
broken by mathematical or social means. And the protection may possibly also be circumvented by other means.

A computer that stays off-line and does not access foreign data is
unlikely to be affected. Then, there are different ways of accessing
foreign data that may be more or less risky. Using foreign code is
likely to be more risky. So the question cannot be independent of
defining  the conditions in which the computer is used.

However, even off-line, there is always the risk that the computer was
born affected by malware (to avoid the restrictive concept of virus).

You should read Ken Thomson's 1984 Turing lecture: Reflections on
Trusting Trust.

Either you trust others to some extent, or you rebuild most of the
technology from scratch by yourself, with no interference from others. May be not starting at stone age, but far enough ... assuming you do not have bugs in your own code (but if not intentionally malicious, they are less likely to be as much a problem).


How $N$ qubits correspond to $2^N$ bits?

Despite what badly written pop-science explanations of quantum computation may tell you, a qubit is not two classical bits and $N$ qubits is not $2^N$ bits. Qubits are fundamentally different from bits, pairs of bits or anything else (except for a representation of $\alpha$ and $\beta$ in binary to precision sufficient to classically simulate the computation to whatever precision is required).

As for why people talk about $N$ qubits being equivalent to $N$ bits, it's hard to say. To paraphrase Tolstoy, all correct explanations are alike but all incorrect explanations are incorrect in their own particular way. Perhaps it comes from the widespread mistaken belief that quantum computers somehow try all the options in parallel; perhaps it's a mistranslation of the fact that quantum computers offer exponential speedup over some classical algorithms. Scott Aaronson has some thoughts along these lines.


Perfect random number generation using normal numbers

many easily-computable irrationals, like $ \sqrt{2} $ and $ \pi $

Therein lies your missing bit.  They are in no way easy to compute if you want many of them, as you would for a real world application.  A nuclear detonation simulation or Monte Carlo model of  stock market behaviour requires millions /billions of pseudo random numbers.  It's just that the formulae are simple to write down.  They are not simple to use for digits far  away from the decimal point.

12 trillion digits of $ \pi $ required the following not simple kit and about a week to compute using a BPP variant:-

Even more impressively (or uselessly depending on your point of view), the quadrillionth bit of $ \pi $ (which is a zero) took 1.2 million cpu hours to compute using >1000 computers.   I suppose computers have gotten faster since then, but it'll still be a while before you can do it on an iPhone.

Secondly, you'd be using the same sequence of numbers over and over, which isn't very random.  So a smart chap might then decide to pick random sub sequences of say irrational number $ \frac{1}{ \sqrt{2} } $ to use.  You'd then have to choose which digits /sequences to use, and how would you actually decide those?  Use a random number generator?

In short, it's unfeasible to use this technique for general pseudo random number generation. Which is why no one does.

Smallish caveat.  Very short sequences from irrationals like these are used as nothing up my sleeve numbers in cryptography for variable initialisation.


You can use any word in the language that lets you complete a proof. The pumping lemma says that, if a language $L$ is regular/context-free, then every long-enough string in the language can be partitioned in a way that generates an infinite set of strings that are also in $L$. So, if you can find any string in $L$ where the partition generates strings outside $L$, you're done.

Finding the right string to start with requires some thought and creativity; I'm not aware of any general method for doing it. I've not written anything out but I think that, if you start with $0^{n+1}1^n$, the proof won't work. However, you should try doing the proof with that string. Assuming that you don't make any mistakes, there are two possible outcomes:

you win by successfully proving that the language isn't regular;
you find that the proof doesn't work, and if the reason is the one I'm expecting, it should guide you straight to a better string to try to pump.


Are there algorithms for proving two finite state machines are equivalent?

Given two deterministic finite automata $A_1,A_2$, you can construct the product automaton $A_1 \times A_2$ using the product construction. Let a mixed state be one which is accepting in $A_1$ and rejecting in $A_2$, or vice versa. The two automata are equivalent iff no mixed stated is reachable from the initial state.


Algorithm to check the 2∀-connectness property of a graph

A simple algorithm is the following:

Let $G = (V,E)$ be the graph you want to check for 2-connectivity.

  For each edge $e = (x,y) \in E$, look if there is a path from $x$ to $y$
  in $(V, E \setminus \{e\})$. If for some $e$, there is not such a path, the graph is
  not 2-edge connected. If there is such a path for each $e$, $G$ is
  2-edge connected.

You should also note, that this algorithm is not the fastest, but very easy to understand. The path-finding part can be done using for example BFS or Dijkstra's Algorithm.

This article also shows a simple algorithm for testing 2-edge connectivity, which runs in linear time.


Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically.
Some examples:

Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable functions. The trick is that, to model computation, we need to represent functions, but for any set $S$, the function space $S \to S$ is always larger than $S$. So there's no simple set that captures all computations involving computations. Instead, Dana Scott introduced domains, which impose additional structure on sets to avoid countability problems.

SKI Combinators provide a "point-free" description of computation. Every computation can be expressed by composing and applying three base combinators $S$, $K$, and $I$. The equations for the combinators are:

$ S\ x\ y\ z = (x\ z)(y\ z)$
$ (K\ x) y = x$
$ I x = x$

So these equations, in some sense, give an algebraic account of all of computation.

Cartesian closed categories provide models for typed programming languages. They don't capture all of computation, but they do provide an abstract model of it.

Topos theory provides a generalization of logic using category theory. And logic corresponds to computation via the Curry-Howard correspondence

As for recursion, it turns out that you can eliminate it by instead using fixed-point combinators like the Y combinator. So recursion can always be eliminated from (untyped) languages, even without using iteration.


Best way for two players to visit a set of graph vertices in a given order

Here is the naive dynamic programming algorithm, which can probably be improved upon: For every $1 \leq i, j \leq |List|$, compute the minimal weight of a path in which Player 1 is at $List_i$, Player 2 is at $List_j$, and the players have covered all vertices up to $List_{\max(i,j)}$. This should run in $O(|List|^3)$.


The A* algorithm requires that its heuristic function $h(n)$ is admissible for all $n$, meaning that it should never overestimate the (unknown) true cost from a node to the goal. This assumption appears to be violated in your example for nodes $S$, $A$, and $B$. Only for $n = C$ and $n = G$ is the heuristic function $h(n)$ admissible, but it should be for all nodes.

This is why the algorithm seems to be resulting in suboptimal paths for you.

A good example of an admissible heuristic function in 2D environments is often the Euclidean distance (straight-line distance). Unless you start involving strange things such as teleportation, this heuristic is always admissible (you can never get anywhere faster than by following a straight line). Although in your drawing, it seems like this wouldn't work. It doesn't look like your drawing was drawn "correctly". Some short paths seem to have higher costs than longer paths (visually).


"Combinational" Decision Graph - Cheapest search algorithm

Your problem is $\mathcal{NP}$-hard, by reduction from $\mathcal{3SAT}$. Let $\Phi = \phi_1 \wedge \dots \wedge \phi_m$ be a CNF formula with variables $V = \{x_1, \dots x_n\}$. Let $\mathcal{L}(V)$ be the set of literals of $V$. Let joining nodes, decision nodes, cost nodes be defined as in your question.

For each $x_i$, we create four cost nodes $t_i$, $f_i$, both with cost $1$, representing an assignment of, respectively, true and false to $x_i$. Let $S$ be the set of all such nodes.

Let $\phi_i = \psi_{1i} \vee \psi_{2i} \vee \psi_{3i}$ be a clause with $\psi_{1i}, \psi_{2i}, \psi_{3i} \in \mathcal{L}(V)$. Without loss of generality, we may assume that $\psi_{1i}, \psi_{2i}, \psi_{3i}$ are literals obtained from different variables. Of the eight possible assignments of truth values to those variables, seven satisfy $\phi_i$. For each of those assignments, we create a joining node $c_{ki}$, which has as a successor every node $s \in S$ corresponding to the values relative to such assignment. For example, if the $k$-th assignment were "$x_\alpha$ true, $x_\beta$ false, $x_\gamma$ true", $c_{ki}$ would have $t_\alpha, f_\beta, t_\gamma$ as successors. Finally, we create a decision node $d_i$ with successors $c_{1i}, \dots, c_{7i}$ and let the starting node have as successors each of the $d_i$.

Now, observe that any solution path in the decision graph that we have built has weight at least $n$. In fact, whenever we encounter a fresh variable $x_i$, we are forced to take either $t_i$ or $f_i$, both of which have cost $1$. Furthermore, any path with cost not exactly $n$ has taken, by the pigeonhole principle, both $t_k$ and $f_k$ for some $k$, which means that it does not correspond to a consistent assignment of truth values to the variables of $V$.

On the other hand, an assignment of truth values to variables that satisfies $\Phi$ corresponds to a path of weight exactly $n$ (choose $t_i$ for every variable $x_i$ set to true, $f_i$ for every variable $x_i$ set to false, follow every arrow in the opposite direction).

We conclude that determining the optimal path is at least as hard as $\mathcal{3SAT}$, and consequently, as every problem in $\mathcal{NP}$.

As always with $\mathcal{NP}$-hard problems, your choice is to go with either heuristics or approximation schemes. If I may make a suggestion, problems like this are a good fit for logical programming tools, such as CSP/ASP.


Fastest possible way to check what of X is in a string

You can do that using Knuth/Moris/Pratt(kmp), the build table portion of algorithm is $O(m)$ and the search part is $O(n)$, being n the size of text and m the size of the pattern, to be more accurate, if you have 3 potential pattern, you'll do that in $3 * O(n+m)$, because you'll probably have to search it 3 times and build 3 tables.

As you problem is about having the pattern or not, once you find one, you can break the loop and that ofc counts as an optimization. If the pattern are static, by this I mean, they probably are always the same, you may store the prefix-table content of each pattern and that will make $O(m)$ one time, next time it'll just be $O(n)$.


Random function "returns a uniformly distributed int". Does this mean the probability of every number is the same?

Uniform distribution is when all values have the same probability. A random uniformly distributed integer in the range $0,\ldots,9$ will attain each of the values with probability $1/10$. In practice, you function is not truly random but only pseudorandom, so the probabilities won't be exactly $1/10$ but only very close to $1/10$.

Normal distribution is a probability distribution on real numbers. If we "bin" them then we get a normal distribution on the integers. If we "cap" it (there are several ways of doing this) then we get a probability distribution on a finite set of integers.


Minimum-area enclosing equilateral triangle for a point set

Let’s consider the following problem at first – given a convex polygon $H = (v_1,v_2,...,v_m)$ and a direction (unit vector) $\vec a$, find a farthest vertex $v \in H$ along this direction (it will be a vertex with maximum value of the dot product $\vec a \cdot \vec v$). Obviously, this problem can be solved by brute force in $O(m)$ time.
If the polygon is static and the query direction varies, then it makes sense to preprocess the polygon to answer this query faster. For each vertex $v \in H$ we can calculate a range of directions (a wedge), for which this vertex will be the farthest one - please see the picture below.

It’s easy to see, that wedges for two vertices, connected by an edge, have a common side – and this side is exactly the outward-pointing normal for this edge. These wedges together with corresponding vertices can be stored in a tree-like data structure. So, for any given direction we’ll be able to use this structure to find a wedge, containing this direction, and also the farthest vertex, corresponding to this wedge, in $O(\log m)$ time.
Returning to the main problem – we need at first to compute the convex hull $H$ for the set $P$, and then to preprocess the polygon $H$ as described above. After that we can scan edges of the polygon one by one, constructing the minimal enclosing equilateral triangle for each edge and recording its minimum area. For each edge the line, collinear with this edge, defines the direction of the first side of the triangle – and this side will contain two polygon vertices. As soon as the direction of the first side is known we can find directions (normal vectors) for other two sides by rotating it by $120^o$ and $240^o$. Then we use the tree, described above, to find farthest vertices for the second and third side of the triangle.
The convex hull computation plus the polygon preprocessing takes $O(n \log n)$ time. The loop over polygon edges takes $m \le n$ steps, and on each step we need to do two binary searches with depth $O(\log m)$, so the overall time will be $O(n \log n)$.


Objective function and constraint satisfaction over a set of multi-attributes elements

I don't see any problem with modeling this as an integer linear program, for example:

maximize V.x
st:
1) s.x < 80
2) 20 <= e.x <= 35
3) FR.x >= 5
4a) Wood.x + 2 - 2W >= 2
4b) Stone.x + 2W >= 2
5) Gold.x - Stone.x < 0
6) Size10p.x <= 5
x[i] ∈ {0, 1}
W ∈ {0, 1}

Where . is the dot product, x is a binary vector indicating which items to take, e is the vector of all-ones, FR is a boolean vector where an element is 1 iff the corresponding item is from France, Wood is a boolean vector that indicates that the material wood, etc. Size10p indicates that the item has a size higher than 10.

I've made all the left-hand sides of dot products the constant vector, so you can easily see that there are no sneaky quadratic constraints.

Most of the constraints are obvious, but constraint 4 is a bit trickier. It involves a disjunction, and uses an extra binary variable to choose which "side" of the disjunction to take. The other half is then trivially satisfied, by either adding 2 and not also subtracting 2 (W = 0, not taking the wood-side of the disjunction) or by just adding 2 (W = 1, taking the wood-side).

  here we're not dealing with the full space of Integers, but instead only with the values found in the bag

This is usually not a problem, since you can binarize constraints of the form v ∈ some enum to v1 = [v == item1], v2 = [v == item2] etc combined with v1 + v2 + ... = 1. But I did not even need that here, the decision is just "do I take this item or not", and things such as "item has property 'Gold'" are just constant booleans.

More tricks are available in other answers, for example Express boolean logic operations in zero-one integer linear programming (ILP).


Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P?

This problem is NP-hard.

Consider the following variants:

Variant 1: given a graph where each vertex has degree at most three, determine if there is a Hamiltonian path.

Variant 2: given a graph, determine if there is a trail (a path without repeated edges) that visits every vertex at least once.

Variant 1 is NP-hard [1].

Variant 1 can be reduced to variant 2 by mapping to the same graph.

If there is a Hamiltonian path on the graph, the Hamiltonian path is certainly a trail that visits every vertex at least once.

On the other hand, if there is a trail from $u$ to $v$ that visits every vertex at least once, since every vertex in the graph has degree at most three, every vertex except $u$ and $v$ must appear exactly once on the trail. If every vertex appears exactly once, the trail itself is a Hamiltonian path. If $u$ and/or $v$ appear twice, remove the first and/or the last edges on the trail respectively, then the trail becomes a Hamiltonian path. Anyway there is a Hamiltonian path in the graph.

So variant 2 is NP-hard.

Suppose the problem in OP is in P. Given an instance of variant 2, construct a new graph for every pair of vertexes $(u,v)$ by adding a new vertex $s$ and new edges $(s,u)$ and $(v,s)$. Now there is a trail that visits every vertex at least once in the original graph if and only if the answer to the problem in OP on at least one of these new graphs is "yes". So one can solve variant 2 in polynomial time by solving the problem in OP on these new graphs. So the problem in OP is NP-hard.

[1] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.


Are there more Turing-unrecognizable languages than recognizable?

Yes, in fact one can show that there are uncountably many languages (say by representing a language as a sequence of the form $\{0, 1\}^\mathbb N$ which can be interpreted as the binary form of some real number in $[0, 1]$) while there are only countably many TMs (as any TM can be represented by a finite string), so almost all languages are undecidable, i.e. assuming we draw a language from an uniform distribution the probability of it being decidable would be 0.


Find Number of elements X in the Tree that lie between a and b

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.


Confusion about assignment axiom in Hoare logic

The assignment axiom in standard Hoare logic says:

|- {P[e/x]}x:=e{P}

If you choose P[e/x] to be x+1=44 (that is e is x+1) you get:

|- {x+1=44} x:=x+1 {x=44}

By the consequence rule, since:
|= x=43 --> x+1=44, and
|= x+1=44 --> x+1=44, and
|- {x+1=44} x:=x+1 {x=44}

you know that |- {x=43} x:=x+1 {x=44} .

By soundness:
|={x=43} x:=x+1 {x=44}


Greedy and backtracking solutions to an arrangement problem with constraints

Overview of the problem

If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
information. Much is said in wikipedia about the Hamiltonian path
problem, which is a NP complete problem. I will only try to discuss
some apects, with my limited competence on the topic, taking into
account the way your question is stated.

Backtracking is just a way of implementing a non-deterministic
algorithm. It is usually simpler to describe the non-deterministic
algorithm, and just say that it is implemented by backtracking, and
possibly explain separately what that is (as I do below)

The non-deterministic algorithm

In the case of the Hamiltoniam path problem (which you can translate
back into your teenagers problem), the non-deterministic algorithm is
as follow:

Choose a starting node for the path, and mark it used.
While there are unmarked nodes do:

Choose a new unmarked node connected to the last node added to the path,
add it at the end of the path, and mark it used.

At the end of the loop you have a Hamiltonian path. The choose
statement is non deterministic, as you have to take one of many
possibilities,  many (or all) of which may not succeed.

Backtracking interpretation

Failure may in general occur in different ways. Here you have failure
when none of the unmarked nodes is connected to the last node added to
the path (i.e. none of the remaining teenagers is compatible with the
last one chosen).

The backtracking implementation consist in keeping track, at each
occurrence of a choose statement, of all the possible choices that
have not yet been tried. If you fail, you go back to the previous
choose, undoing what was done (i.e. node addition to the path and
node marking), discard the choice made and make a new choice from
those that have not yet been tried at that choose statement.

One way of implementing this is to associate a list of remaining
alternative choices to each node of the constructed path. Another
possibility is to rely on the exception mechanism of the programming
language.

Pruning

I am not sure what is (or should be) considered pruning in this case.

Checking that a node chosen is connected to the previously chosen one
is a very trivial form of pruning. No pruning at all would be
exploring the complete set of remaining nodes at each choose
statement, to discover soon after that some fail because the node is
not connected to the end of the path.

Greedy algorithm

The greedy algorithm as described by Yuval Filmus' answer is just the
non-deterministic algorithm, except for the fact that you do not
backtrack. You just fail.  I do not know whether there is more to be
said.

He is much more expert than I am on these issues. However, my own
feeling is that the very concept of greedy algorithm makes less or little
sense in this case.  The reason is that I understand greedy algorithms
as a way of finding good solutions to quantitative optimization
problems, which may not be optimal in some cases.

A greedy algorithm also has to make choices, and does so on the basis
of local optimizations that may not be optimal globally. But it is
expected to succeed anyway and does not have to backtrack: the price
of greediness is that the "cost" (however defined) of the result obtained
by the algorithm may be higher than the cost of the optimal solution.

I do not think that is really very meaningful in an all or nothing
situation, were you are supposed to succeed or to fail, without any
measure of intermediate situations, like placing the largest possible
number of teenagers, or placing them all with the smallest number of
conflictual sittings. These examples may be seen as optimization
variants of the problem where greediness makes sense.

However, we can use heuristics that could possibly increase the
chances of success. In the case of our optimization variants, they
could e seen as greedy techniques that improve the chances of having
near otpimal solution (Though I did not prove anything). But the
greedy algorithm remains basically the non-deterministic description.
The heuritic comes as a way to choose that improves chances of
success, or of approaching the least cost.

One such heuristic, is to always choose one of the unmarked nodes that
has the least number of edges connecting to other unmarked nodes. The
purpose is to keep in your bag nodes that will be easier to connect to
the path, while removing those that are getting hard to use. And if one
of these node is disconnected from all others, or has only one
connection but cannot be added to the path immediately, you know you
have failed and can start backtracking earlier.

We could say that we try to optimize the cost of the search reather
than the cost of the solution obtained, and that this "greedy"
algorithm does increase the chances of success if there is no
backtrack, or reduce the number of search steps if we use backtrack,
or improve the solution obtained if we consider one of the two
optimization variants I described above (maximum number of
non-conflicting teenagers, or minimum number of conflicts).

A global improvement

A global way to improve the algorithm is to decompose the graph into a
a block tree of the graph, where each node is a biconnected
components. This can be done in linear time.

A Hamiltonian path for the whole graph is composed of subpaths in each
of the biconnected components, connected by the edges of the block
tree.

In practice, you solve the given problem at the level of the block
tree, and then you solve it independently for each block, i.e. for
each biconnected component.

Since the algorithm is exponential anyway (NO complete), there is much
to be gained whenever it can be decomposed, thus reducing the size of
the sub-problems.

Actually, if the block tree is not composed of a simple path without
branching, there is no solution to the problem. So that may be a way
of getting much faster negative answers.

This may also be seen as a form of global pruning of the search space.


Obtain all possible Turing Machines from a Universal Turing Machine

Enumerating all the possible TMs is a boring programming exercise. We do not need to use the UTM at all here -- we only have to generate the representation of all TMs and output it, using the chosen encoding of TMs as words.

The UTM does not accept your language $L$ since it accepts another language, namely $\{\langle M,w\rangle \ |\ \mbox{$M$ accepts $w$}\}$.


Is this language regular or non-regular: {ww : w ∈ {a,b}* }

Your explanation is correct. To make it more rigorous, assume that L can be recognized by a finite automaton $D$ with $N$ states.

Consider feeding a string $w$ longer than $N$ characters to $D$. Since $D$ has only $N$ states, that means it will go through some state twice. Suppose $w$ can be represented as $w = pqr$, where the state of the DFA is the same before and after $q$.

Then the strings $ww = pqrpqr$ and $pqqq...rpqr$ must be both accepted by $D$, but probably only the first one is in $L$ (some more rigor may be needed to prove that there exists such a string $w$ such that the second string really cannot be in $L$, for some number of repetitions of $q$).

P.S. looks like I unknowingly used the Pumping Lemma.


When directed graph is linear, return the nodes in order. Otherwise fail

Here is a quite non-optimal algorithm, to get you started.

Go over all edges $(a,b)$. For each edge, go again over all edges, and check how many times $a$ appears. Stop once you discover $a$ that appears only once (if this never happens, reject). We will take $n_1 = a$.

Go over all edges again, looking for the unique edge $(n_1,b)$ in which $n_1$ appears. Take $n_2 = b$.

Go over all edges again, looking for an edge $(n_2,c)$ in which $n_2$ appears on the left (if there is no such edge, reject). Take $n_3 = c$.

Continue in this way, finding $n_4,\ldots,n_n$.

This algorithm runs in $O(n^2)$. Using hashing, you should be able to improve it to $O(n)$.


Yes, it can be done in polynomial time, but the proof is quite subtle.  It's not simply $O(n^3)$ time, because Gaussian elimination involves multiplying and adding numbers, and the time to perform each of those arithmetic operations is dependent on how large they.  For some matrices, the intermediate values can become extremely large, so Gaussian elimination doesn't necessarily run in polynomial time.

Fortunately, there are algorithms that do run in polynomial time.  They require quite a bit more care in the design of the algorithm and the analysis of the algorithm to prove that the running time is polynomial, but it can be done.  For instance, the running time of Bareiss's algorithm is something like $O(n^5 (\log n)^2)$ [actually it is more complex than that, but take that as a simplification for now].

For lots more details, see Dick Lipton's blog entry Forgetting Results and What is the actual time complexity of Gaussian elimination? and Wikipedia's summary.

Finally, a word of caution.  The precise running time depends upon exactly what field you are working over.  The above discussion applies if you are working with rational numbers.  On the other hand, if, for instance, you are working over the finite field $GF(2)$ (the integers modulo 2), then naive Gaussian elimination does run in $O(n^3)$ time.  If you don't understand what this means, you can likely ignore this last paragraph.


Optimizing estimator of composed functions when function is known

Is there any literature about creating an estimator when you know the exact function you are estimating?

I think streaming algorithms may be of interest to you. A streaming algorithm is an algorithm that operates on some model of a massive 'stream' of data that is simply impossible to completely store, but it is possible to traverse it and do some computations with bounded memory. Often, it is impossible to solve even simple computations with bounded memory, but answers that are correct with high probability can be found efficiently, with techniques as random sampling, aggregating medians or probabilistic data structures.


Is random access allowed in the Bit Complexity model, or is it just expensive?

According to Fürer's paper, the underlying complexity model is a Turing machine without random access, or equivalently, Boolean circuits. So no random access is allowed. Check also Diem's writeup on the subject.


Use the definition of $L(A)$.

There are several different ones, so let me illustrate with the definition I know. We define a function $\hat\delta$ inductively so that $\hat\delta(q_0,w)$ is the set of all states reachable from $q_0$ by reading the word $w$. We then define $L(A)$ as the set of words $w$ such that $\hat\delta(q_0,w)$ intersects $F$.

Given this definition, we argue as follows. First, the definition of $\hat\delta$ (which I haven't specified) easily implies that $q_0 \in \hat\delta(q_0,\epsilon)$. Since $q_0 \in F$, it follows that $\hat\delta(q_0,\epsilon)$ intersects $F$, and so $\epsilon \in L(A)$.


How a swapper manipulates entire processes in the operating system?

One processor can only execute one process at a time. Today processors have several cores/threads in the same chip. Even if you have one core in your processor, the OS needs to swap the entire execution context (the entire process) in order to execute something else and it needs to do it efficiently to prevent latency in rendering.
What is called a swapper here is the part of the OS which does this execution context swap.
For example, on Linux the task_struct is a structure containing the process information. When Linux calls schedule(), the function will determine what process should run next and on what core based on priority. This priority is probably stored in the task_struct.
Paging swapping and process swapping is quite different. Every process has its own page tables.
For example, on x86-32 systems (32 bits systems) you are going to have 2 levels of page table: PDT (page directory table) and PT (page table). The CR3 register contains the address of the bottom of the PDT and the PDT contains addresses of the PTs. Since on most systems pages are 4KB, one PDT, which has itself a size of 4KB, can map up to 4MB. If your PDT is full, it will thus map the whole address space available (4GB) (https://wiki.osdev.org/Paging). A virtual address is separated in chunks representing the offset in respective tables. For virtual address 0xABCDEF12, on x86-32 you have 0xF12 as the offset in the physical page, ten bits as the offset in the PT and the most significant 10 bits as the offset in PDT.
When a process swap occurs, all page tables are kept in memory (RAM) and the actual physical pages are kept where they are. The only thing which changes is the CR3 register which will point to a new address. At this address is another PDT for the new process taking place. The TLB (page cache) needs to be flushed as well.
Page swapping is completely different. It involves taking pages that are on a swap partition on the hard-disk and loading it to RAM. Linux for example works with interrupts to manage page swapping. The CPU was made to throw an exception (or interrupt) and launch a certain interrupt handler when a page fault occurs (when the CPU tried to execute or read data that isn't in RAM). For x86-32, the interrupt number of a page fault is 0xE (https://wiki.osdev.org/Exceptions). When a page fault occurs, the CPU will look in its IDT for the address of the handler (code present in RAM that will run to manage the page fault). The address of the IDT is stored in a special register called the LIDT.
A page fault can occur when the PT contains a page which has the present bit not set. This means that the page is mapped but not present in RAM at the moment. The page fault handler registered by the OS will thus take the page on the hard-disk and load the page to memory and return.
With virtual addressing, each process is considered to have a full 4GB of virtual address space. One core has only one process running and this process has access to the whole 4GB of virtual address space. The same virtual address can point to 2 different addresses in physical RAM. The OS uses this to map the process space to different positions in RAM so that processes don't interlace each other. If physical RAM is full (which is rare nowadays), the OS will place some pages not currently in use onto the hard-disk. I often installed Linux on computers without swap space. I simply considered that RAM would never be full and thus I would not need it.
As an example, Linux uses ELF files as executable files. Very often, the ELF file's code will be mapped to virtual address 0x400000. Every process' code is mapped to the same virtual address. Thus the OS needs to setup its page tables accordingly and needs to determine what process is going to get what part of the available RAM. It is done so that all processes don't interfere with each other or the kernel.
Processes are swapped according to a timer which raises an interrupt after some time. The timer is programmed to a certain time, counts down to 0, then raises a certain interrupt number. The OS will register a handler to that interrupt number which will call a scheduler which will determine what process goes next and reschedule the timer etc. When processes are swapped all registers are stored onto the process' stack and a pointer to the stack is kept in a structure somewhere (https://en.wikipedia.org/wiki/Context_switch).


How does one find out whether $N = a^b$ for some $b$?

Yes, your approach is a good one.  The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why?  It's easier to see why if you state more carefully the problem  you are trying to solve.  You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$.  Taking logs of both sides, we get $b \lg a = \lg N$.  From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:

For $b=2,3,\dots,\lg N$:

Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.

Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate.  You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt[b]{N}$; for instance, you could use Newton's method.  But the basic method above is already very efficient.

You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$.  Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$.  This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$.  This is much slower.  Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.


If we sort a table column-wise and then row-wise why the table is still sorted column-wise?

Consider some column $i$ and some rows $j < k$. Let $x$ be the element at row $j$ column $i$ after the final sorting, and let $y$ be the element at row $k$ column $i$. We want to prove that $x \leq y$.

Since $x$ ended up in column $i$, there must have been $n-i$ elements in row $j$ larger than $x$. Together with $x$ itself, these are $n-i+1$ elements in row $j$ that were at least as large as $x$. The corresponding elements in row $k$ were also at least as large as $x$, since the columns were sorted. Summarizing, row $k$ contains at least $n-i+1$ elements which are at least as large as $x$. That means that after sorting, the element at position $i$ on row $k$ (that is, $y$) is at least as large as $x$


There is an $n^k$ prover if and only if $P = NP$

An $n^k$ prover implies that the set $\{\left(\varphi,1^n\right)|\text{$\varphi$ has a proof of length $\le n$}\}$ is in $P$, since we can simply run the prover for $n^k$ steps and check whether it yields a valid proof.
It remains to show that this language is NP complete. This follows from a straightforward reduction from SAT. Given a CNF $\varphi$ over the variables $x_1,...,x_n$ return the pair $\left(\exists x_1,...,x_n: \varphi, 1^k\right)$ where $k=k(|\varphi|)$ is some upper bound on the length of the satisfiability proof for satisfiable formulas of length $|\varphi|$.


What does it mean to isolate a field in a word?

Consider an 8-bit word whose contents can be described as follows:

Bits 0–2 encode some value $x$.
Bits 3–4 encode some value $y$.
Bits 5–7 encode some value $z$.

Each of these different values is known, in this context, as a field. You can think of it as a field in some form.

Isolating a field out of a word means extracting just the value of the field. For example, denoting the entire word $w$, here is how we can isolate each of the fields:

$x$: AND $w$ with the mask $7$ (which is $111$ in binary).
$y$: Right-shift $w$ by 3 positions, and AND the result with the mask $3$.
$z$: Right-shift $w$ by 5 positions.

In C, you could implement these as follows:

x = w & 7;
y = (w >> 3) & 3;
z = w >> 5;


Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$

The solution is to delete the sub-tree $x$ ($O(\lg n)$),
then replace sub-tree $z$ instead of sub-tree $y$ ($O(1)$),
then turn $z$ to black ($O(1)$),
and finally insert $y$ as usual ($O(\lg n)$).


Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

First, let us note that for monotone $f$, the statement holds for some $c > 1$ iff it holds for all $c > 1$. Indeed, let $1 < c_1 < c_2$. If the statement holds for $c_2$ then $f(c_1n) \leq f(c_2n) = O(f(n))$ due to monotonicity. In the other direction, let $M$ be an integer so that $c_2 \geq c_1^M$. Then induction shows that $f(c_1^Mn) = O(f(n))$, and so $f(c_2n) = O(f(n))$ due to monotonicity.

If $f$ is a polynomial then $f(n) = \Theta(n^A)$ and so $f(cn) = \Theta((cn)^A) = \Theta(n^A) = \Theta(f(n))$. A similar argument works when $\Omega(n^{A-o(1)}) \leq f(n) \leq O(n^{A+o(1)})$.

In the other direction, suppose that $f(n) = n^{g(n)}$, and suppose that $g(n)$ is nondecreasing. Then $f(cn) \geq c^{g(n)} f(n)$, and so $f(cn) = O(f(n))$ iff $g(n)$ is bounded. So in some sense, if $f(cn) = O(f(n))$ then $f$ must have polynomial growth.


Randomized algorithms

If you'll accept a randomized algorithm, yes, it can be done in linear time.  There's a randomized algorithm whose expected running time is $O(n)$, and where the probability that it takes longer than $c \cdot n$ time is exponentially small in $c$.

Here's the idea.  Randomly permute the entries of $S$, then split it into three equal-sized pieces, each of length $n/3$: let $X$ be the first one-third, $Y$ the second one-third, and $Z$ the third one-third.  Now call 3SUMx1(X, Y, Z).  If this finds a solution, you have a solution to the 3SUMx3 problem.  Moreover, I claim that if there is a solution to the 3SUMx3 problem, then with probability at least $6/27$, this procedure finds a solution.  Therefore, the expected number of times you have to repeat it (before finding the first solution) is constant.

The running time of each iteration is $O(n)$, and you do a constant number of iterations (on average), so the total expected running time is $O(n)$.  The probability that you fail to find a solution after $k$ iterations is $(21/27)^k$, which is exponentially small in $k$.

Where does $6/27$ come from?  Suppose there's a solution to the 3SUMx3 problem, say, $S[i]+S[j]+S[k]=0$.  What is the probability that $i,j,k$ all come from different thirds of the array?  This probability is $3!/3^3 = 6/27$.  So, if a solution to the 3SUMx3 problem exists, then each iteration of the above procedure has at least a probability $6/27$ of finding it.

Deterministic algorithms

What about a deterministic algorithm?  I don't have a specific proposal in mind, but I feel like it's plausible that this construction could be derandomized.

For instance, to give you an idea of the sort of thing I'm talking about, suppose we split the array into thirds once (deterministically).  Suppose there exists a solution $S[i]+S[j]+S[k]=0$. Then there are $3^3=27$ cases for which third each $i,j,k$ falls into.  After you remove symmetries, there are only $1+6+3$ cases:

Type A (1 case): All three indices fall in different thirds.
Type B (6 cases): Two of the indices fall into the same third, and the other index falls a different third.
Type C (3 cases): All three indices fall into the same third.

You can test for a type-A solution in $O(n)$ time, with a single invocation of the oracle:  3SUMx1(X, Y, Z).  Also, you can test for a type-C solution by making three recursive calls to the same solution (one on X, one on Y, one on Z).  This leaves only the question of how to test for a type-B solution.  It seems like you might also be able to test for a type-B solution using a similar recursive algorithm, though I haven't tried to work out the detailed case analysis.  It seems not impossible that perhaps some ideas along these lines could lead to a deterministic algorithm -- though I haven't worked out the details and I'm just speculating at this point.


Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

Let $S$ be a maximal set of vertices in which any two vertices are at distance at least 3. (Note maximal just means that $S$ cannot be enlarged by adding new vertices.) By design, any other vertex is at distance at most 2 from some vertex in $S$, and therefore $S$ is a 2-dominating set. On the other hand, if we define the $B_1(v)$ to consist of all vertices at distance at most 1 from $v$, then the sets $B_1(v)$ for $v \in S$ are disjoint. Since the minimum degree is  $\delta$, the size of each set $B_1(v)$ is at least $\delta+1$, hence $|S| \leq n/(\delta+1)$.


Why number of possible cuts in a graph differ from maximum number of minimum cuts?

In a specific graph, not any cut is a minimum cut. What Wikipedia claims is that out of the $2^{n-1}-1$ potential cuts, at most $\binom{n}{2}$ can be minimum cuts in any given graph. Some graphs contain even fewer minimum cuts. For example, if you connect two cycles by a single edge then there is a unique minimum cut.

The upper bound on the number of minimum cuts follows by analyzing Karger's algorithm (linked to in the question): you can show that the probability that the algorithm produces any specific minimum cut is at least $1/\binom{n}{2}$, and so there can be at most $\binom{n}{2}$ of them.


To show that $L$ is not recognizable, you can reduce the complement of the halting problem to it. $\overline{\mathrm{HALT}}$ is not recognizable because, if a language and its complement are both recognizable, then they're both decidable, and we know that $\mathrm{HALT}$ isn't recursive.

Given a Turing machine $M$ and input $w$, you want to accept iff $M(w)$ loops. So construct the machine $M'$ which halts if its input is $1100$ and simulates $M(w)$, otherwise. If $M'\in L$, then $M'$ cannot halt on $0011$ or $1000$,* which means that $M(w)$ doesn't halt.

* It seems there's a typo in the question, which mentions $0011$ twice. Obviously, this doesn't make any real difference.


Metrics on which Clock Cycles Per Instruction(CPI) depends

In part a same processor is assumed, and 2 compilers are used. In part b, 2 processors with different clock frequency is used, since the execution times for both processors are equal but the CPIs and dynamic instruction counts are unequal. The CPI for both processors is the same as the CPI from part a because the same compilers were used and the same compiled program is run.
So the dynamic instruction count and CPI is the same from part a.
$\frac{f_A}{f_B}=\frac{CC_B}{CC_A}=\frac{T_B}{CPI_B*I_B}*\frac{CPI_A*I_A}{T_A}$.
Since $T_A=T_B$,
we get
$\frac{f_A}{f_B}=\frac{CPI_A*I_A}{CPI_B*I_B} = \frac{1.1*1*10^9}{1.25*1.2*10^9} =0.7333 $
or $\frac{f_B}{f_A} = 1.37$
For part c, use CPIs obtained in part a.
Speedup
$\frac{T_A}{T_C}=1.67$
$\frac{T_B}{T_C}=2.27$
CPI depends on the processor's hardware architecture, processor clock frequency, compiler and the number of instructions.


What are GEN and KILL statements in dataflow analysis?

Dataflow analysis works on sets of facts.  GEN points are points in the graph where one of the facts you care about becomes true, and KILL points are points in the graph where one of the facts you care about becomes false.

The GEN and KILL points thus depend on the facts you care about.

For example: if you were doing a constant propagation analysis you might care about the fact that variable x has the constant value 3.  Any point in the graph where x is assigned the value 3 is a GEN point.  Any point in the graph where x is assigned a constant value other than 3 is a KILL point.

If you were doing reaching definitions, and x is defined in two different places then the facts you are interested in are (1) "x from the first definition may be available here" and (2) "x from the second definition may be available here."  In this case the point where x is first defined is a GEN point for fact (1) and a KILL point for fact (2).  The point where x is second defined is a GEN point for fact (2) and a KILL point for fact (1).

As a third example, suppose you were doing a liveness analysis.  This is a backwards analysis.  In this case the places where x is used are GEN points, because x is live at the statement where it is used, and at some of the statements above the statement where it is used.  The definitions of x are KILL points, because the previous definitions of x are no longer needed after this node (as well as at along all the nodes along the reverse path until you reach a GEN statement higher in the graph.)


Show that an NP-Complete problem exists that is contained in SPACE(n)

First, let me show how to prove that some NP-complete problem using linear space just given the existence of some NP-complete problem.

Suppose that $L$ is NP-complete. In particular, $L$ runs in nondeterministic time $O(n^k)$ for some $k$, and so uses $O(n^k)$ space. Construct a new language $L’ = \{(x,1^{|x|^k}) : x \in L\}$. Given an input to $L’$, we can first verify that it is of the form $(x,1^{|x|^k})$, and then run the nondeterministic algorithm for $L$, which now runs in linear time and space (since the length of the input is $|x| + |x|^k$). Conversely, $L’$ is still NP-hard, since you can easily reduce $L$ to $L’$.

The technique illustrated above is known as padding, and is very useful in computational complexity.

Second, why does this not show that all of NP can be solved in linear space? The fact that $L’$ is NP-hard means that every language $A$ in NP can be reduced to it in polynomial time. If the reduction works in time $O(n^k)$, we can use the linear space algorithms for $L’$ to solve $A$ in space $O(n^k)$, since this is the size of the input to $L’$.

It is expected that NP is not contained in $\mathsf{SPACE}(n)$, but we don’t know how to prove it. Indeed, since L is contained in $\mathsf{SPACE}(n)$, if we could prove that NP is not, then we would separate L from NP, a separation which isn’t known at the moment. See this answer. It is known, however, that NP is different from $\mathsf{SPACE}(n)$; see this answer.


Proving a language comprised of 2 languages is regular

Proof using closure properties

Let $add\colon \Sigma \to \Sigma^*$ be a regular substitution that maps $\mu \in \Sigma$ to $\{ \sigma \mu \xi : \sigma, \xi \in \Sigma \}$ (the image is regular since it is finite). Then your language is $L_1 \cap add(L_2)$.

Proof using product automaton

Let $(\Sigma, Q^i, q_0^i, F^i, \delta^i)$ be automata accepting $L_i$ (for $i = 1,2$). We construct a new automaton $(\Sigma, Q, q_0, F, \delta)$ where:

$Q = Q^1 \times Q^2 \times \{1,2,3\}$.
$q_0 = (q_0^1,q_0^2,1)$.
$F = F_1 \times F_2 \times \{1\}$.
$\delta((q^1,q^2,1),\sigma) = (\delta^1(q^1,\sigma),q^2,2)$.
$\delta((q^1,q^2,2),\sigma) = (\delta^1(q^1,\sigma),\delta^2(q^2,\sigma),3)$.
$\delta((q^1,q^2,3),\sigma) = (\delta^1(q^1,\sigma),q^2,1)$.

The product automaton keeps track of the state in both automata, as well as the location within the triple $\sigma_i \mu_i \xi_i$ (this is the purpose of the third argument).


Intersection/Union of Language of PDA, CFG and NFA

$L(P)$ and $L(G)$ are context-free; $L(N)$ is regular.  By standard closure properties, the intersection of a context-free language with a regular language is context-free, and the union of two context-free languages is context-free. Therefore, $L(P)\cap L(N)$ is some context-free language $C$ and $C\cup L(G)$ is context free.

The closure properties can be proven without reference to the specific language by using the fact that every context-free language is accepted by a PDA or defined by a context-free grammar.  For example, to show that the union of two context-free languages is context free, let those languages be defined by grammars $G_1$ and $G_2$ with start symbols $S_1$ and $S_2$. We can rename the non-terminals in $G_1$ and $G_2$ so that no non-terminal appears in both grammars. Now form the a grammar $G$ with start symbol $S$ consisting of the rule $S\to S_1|S_2$, all the rules of $G_1$ and all the rules of&nbsp:$G_2$.  You should be able to convince yourself that $L(G) = L(G_1)\cup L(G_2)$. But proving this didn't require us to know anything about what rules are contained in the grammars.


Problems with the proof of Huffman Optimality in Cover's book

To answer your first question, the index $i$ goes over the range $1,\ldots,m$. The assumption is that there are finitely many symbols. While some theoretical papers consider encodings of countably infinite domains (such as universal codes), usually the set of symbols is assumed to be finite.

To answer your second question, the claim is that a Huffman code has minimum redundancy among the class of uniquely decodable codes. The proof of Theorem 10 in your notes, however, only directly proves that a Huffman code has minimum redundancy among the class of instantaneously decodable codes. It does so when it takes an optimal encoding for $p_1,\ldots,p_{n-2},p_{n-1}+p_n$ and produces an optimal encoding for $p_1,\ldots,p_n$ by adding a disambiguating bit to the codeword corresponding to $p_{n-1}+p_n$; it's not clear how to carry out a similar construction for an arbitrary uniquely decodable code.


What you want to prove is false.

$T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$.

To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$.

Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem to conclude that $T(n) = \Theta(n^{ \log_b a } \cdot \log^{k+1} n)$.


The running time of quicksort satisfies the recurrence
$$
T(n) \leq \max_{n_1+n_2+1=n} T(n_1) + T(n_2) + Cn,
$$
with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step,
\begin{align}
T(n) &\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &=
\max_{0 \leq m \leq n-1} C(m^2 + (n-1-m)^2) + Cn \\ &=
C(n-1)^2 + Cn + \max_{0 \leq m \leq n-1} 2Cm(m-(n-1)) \\ &\leq
C(n-1)^2 + Cn \\ &\leq Cn^2.
\end{align}

Why is the worst case when $n_1 \in \{0,n-1\}$? This is because the function $n^2$ is convex, that is, the maximum of $x^2+(n-x)^2$ over $x \in [0,n]$ is attained at one of the endpoints. In more complicated situations, we could trying showing this directly, by inductively showing that $T(n+2)-T(n+1) \geq T(n+1)-T(n)$, which should imply (I think) that the maximum of $T(n_1)+T(n_2)$ is attained at one of the endpoints.


Does the product of two functions equal the product of their Big-O's?

By definition, $f(n) \leq c_1 \cdot g(n)$ and $l(n) \leq c_2 \cdot m(n)$, for some $c_1$ and $n \geq n_0$, and for some $c_2$ and $n \geq n_0'$ respectively. Suppose we set $n_0^* = \max (n_0, n_0')$, then both inequalities are satisfied for $n \geq n_0^*$. Then obviously $f(n) \cdot l(n) \leq c_1 \cdot g(n) \cdot c_2 \cdot m(n)$ for $n \geq n_0^*$. So indeed the claim holds. We can go take one additional step, however. Note that we can replace $c_1 \cdot c_2$ by a new constant, and thus we conclude that $f(n) \cdot l(n) = O(g(n) \cdot m(n))$.


set of Kolmogorov-random strings is co-re

We want to show $\overline{R_c}\in RE$.

$\overline{R_c}=\left\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|<|x| \right\}$, i.e. $x$ is not a Kolmogorov-random string if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$.

Given $x$, run all the Turing machines $M$ with description $|\langle M\rangle|<|x|$ with empty input $\epsilon$, simultaneously (i.e. dont execute any machine for $i+1$ steps before executing all of them for $i$ steps). This is possible since the set of all Turing machines of length $\le |x|$ is finite. If one of the machines halts and outputs $x$, accept, otherwise keep running. If all the machines halted with output different then $x$, reject.

Clearly if $x\in \overline{R_c}$ then our machine accepts, otherwise it either rejects or doesn't halt (which is the case if none of the machines outputs $x$ after some finite number of steps, and at least one of them doesn't halt).


In Meek STV, there is the concept of the quota or threshold that a candidate must exceed to be considered elected. This threshold is changed from round to round in the Meek STV system. The threshold changes based on how many votes are thrown away.

Let's say that your code is 4 5 6 and the rest blank, then once all those candidates are either elected or eliminated, the remaining part of your vote is considered "thrown away". Based on this, the threshold is changed for what candidates need to be elected in the next round.

In the STV system, the vote 0 2 4 0 1 6 is considered the same as 2 4 1 6 0 0, i.e. the zeros are automatically put at the end.

In the Stack Exchange moderator elections, it is possible to choose only a second candidate and a third candidate, but not a first. That is the same thing as choosing a first candidate and a second candidate.

Related on Meta Stack Exchange: How are moderator election votes counted, in pure English?


In information theory, why is the entropy measured in units of bits?

The entropy of a random variable $X$ can be described in terms of prefix-free binary encodings. Let $T(X)$ be the minimal average codeword length of a binary prefix code for $X$, and let $X^{\otimes n}$ be the random variable corresponding to $n$ independent samples of $X$. Then
$$ \lim_{n\to\infty} \frac{T(X^{\otimes n})}{n}. $$

Shannon's source coding theorem allows a similar description. An encoding scheme for a variable $X$ over an alphabet $\Sigma$ is a pair of mappings $E\colon \Sigma^n \to \{0,1\}^{\ell(n)}$ and $D\colon \{0,1\}^{\ell(n)} \to \Sigma^n$. The entropy is the infimum of $H$ such that there are encoding schemes with $\ell(n) = Hn$ such that as $n\to\infty$,
$$ \Pr_{x \sim X^{\otimes n}}[D(E(x))=x] \to 1. $$
In words, there is an encoding at rate $H$ if we can encoded $n$-tuples of samples of $\Sigma$ using $Hn$ bits in such a way that most of the time, we can decode the original sample from its encoding.

Both of these characterizations show that when encoding a large number of samples of $X$, each sample of $X$ takes $H(X)$ bits to encode.

Another characterization is the asymptotic equipartition (AEP) theorem, which states that $X^{\otimes n}$ consists, up to some small error, of roughly $2^{nH(x)}$ points whose probability is roughly $2^{-nH(x)}$.


You are unsure how to answer the question.

When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come.

A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls.

Now try f (10, 64) -> f (64, 9) -> f (9, 63) -> ... -> f (3, 57) -> f (57, 2) -> f (2, 56) -> f (56, 1). It should be easy to figure out the exact number of multiplications.

But then you need to check for the cases where the recursion doesn't end, and that is when we miss the test "n = 1" altogether because n < 1. If n < 1 then we call f (n, x-1). If x-1 < 1 as well then the recursion never ends. So that is the case when n < 1 and x ≤ 1.

PS. This function does not calculate x^n.


Conversion of ambiguous left recursive grammar to LL(1)

I don't want to do your homework, but the two insights that appear to solve it for me are:

What the first rules

$S \rightarrow SoS$

$S \rightarrow SlSr$

say is that whatever else $S$ can be rewritten to (which, in this case, is just $i$) can be followed by any number of occurrences of $oS$ and $lSr$ arbitrarily often.

If we introduce a nonterminal for that (the part that follows the $i$), left-factorized rules for it follow immediately.


Minimum number of swaps to make two arrays strictly increasing

$dp[b][i]$ denotes the minimum number of swaps needed to make the first $i$ elements of both arrays strictly increasing where $b$ is a boolean flag denoting whether we've swapped $A[i]$ and $B[i]$ (or $\infty$ if this minimum doesn't exist).
The key observation is that we only care about what $A[i-1]$ and $B[i-1]$ are when calculating $dp[0/1][i]$. This means that we can calculate $dp[0/1][i]$ using only $A[i-1]$, $B[i-1]$, $A[i]$, $B[i]$ and $dp[0/1][i-1]$ in $\mathcal O(1)$ time. (The recurrences are shown in the code you posted).
The answer is clearly $\min(dp[0/1][N])$, and this solution runs in $\mathcal O(N)$ time.


The categorization in that list is certainly still current.

Perhaps one new category has emerged, namely, dependently-typed programming languages. These are essentially automated theorem provers where the primary goal is not proving theorems, but programming. Due to the Curry-Howard correspondence, these two concepts are strongly intertwined. The ultimate goal of such programming languages is to write programs that have much stronger guarantees than regular typed programming languages. People also use these for theorem proving. Some new systems falling into this category include Agda and Epigram. One of the key characteristics of such languages is that they put a lot of effort into making it easier for programmers to define inductive families of datatypes. A simple example is a vector, which depends upon natural numbers (defined inductively).

Regarding which ones are still very active, I think they all are. Coq, Isabelle, Twelf, and PVS are used a lot in the programming languages community. Maude is used extensively in modelling systems. (Personally, I've used Coq and Maude.)

I'd never heard of a few of them. In the pdf you link to, there are links to the theorem provers. Some links are current, some are broken. Gandalf now seems to be some sort of bearded wizard.

The theorem provers mentioned in “A Review of Theorem Provers” are:

ALF: subsumbed by ALFA, Coq, and Agda.
ALFA: seems to no longer unsupported.
COQ: actively supported.
MetaPRL: seems to be no longer supported.
NuPRL: actively supported.
HOL: actively supported.
PVS: actively supported.
Isabelle: actively supported.
TWELF: actively supported.
ACL2: actively supported.
INKA: seems to be no longer supported.
GANDALF: seems to be no longer supported.
TPS: may still be active, but has only a small following.
OTTER: may no longer be supported.
SETHEO: replaced by E-SETHEO, which seems to no longer be supported.
SPASS: seems to be still active.
EQP: seems to be no longer supported.
MAUDE: very actively supported.
OMEGA: seems to be no longer supported.
Mizar: actively supported.

There are undoubtedly many new automated theorem provers that have not been mentioned in this list.

For completeness, as suggested by Raphael, there are site archiving proofs made using various tools. For example:

The Archive of Formal Proofs for Isabelle
Formalized Mathematics for Mizar
The Constructive Coq Repository
The ACL2 Books Directory
Selections from the PRL Math Library
NASA Langley PVS Libraries


What are the examples of trivial and non-trivial properties of language recognized by a Turing machine?

In the context of Rice's theorem, a trivial property has a very specific meaning.

Here, we define a property to be a set of Turing-recognizable languages. A property is non-trivial unless it contains no languages, or contains all Turing-recognizable languages.

We can clearly recognize these with a Turing Machine, since we can just make a machine that always says "YES" for the first case, or make a machine that always says "NO" for the second.

So both the properties you have identified are non-trivial properties, and are thus undecidable by Rice's theorem.