Is there an algorithm that can solve any two-player game?

(Note that you're excluding games with randomness, such as backgammon.)

Yes. In particular, endgame tablebases use most of such an algorithm.

Wbool,Wfull,Bbool,Bfull = set(),set(),set(),set()
keep_going = False
for v in nondraw_endstates:
 keep_going = True
 if is_a_victory_for_white_(v):
  Wbool.insert(v)
  Wfull.insert([v,0])
 else:
  Bbool.insert(v)
  Bfull.insert([v,0])
n = 1
while keep_going:
 keep_going = False
 for v in Wbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Wbool:
    continue
   if white's_turn_(u):
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Wbool:
     avoidable = True
     break
   if not avoidable:
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
 for v in Bbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Bbool:
    continue
   if not white's_turn(u):
    Bbool.insert(u)
    Bfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Bbool:
     avoidable = True
     break
    if not avoidable:
     Bbool.insert(u)
     Bfull.insert([u,n,v])
     keep_going = True
     continue
 if (initial_node in Wbool) or (inital_node in Bbool):
  keep_going = False
 else:
  n = n+1

Suppose the game is locally finite. If white has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Wfull's triples to all non-endstate white nodes is a winning strategy for white.  If black has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Bfull's triples to all non-endstate black nodes is a winning strategy for black. If only finitely many nodes can reach the non-draw endstates and neither side has a winning strategy then the while loop will terminate and white can always stay out of Bbool and white doing so guarantees that white won't lose. Bblack can always stay out of Wbool and black doing so guarantees that black won't lose.

If the while loop terminates, then it does so in an amount of time that's bounded above by a polynomial in (the number of nodes that can reach the non-draw endstates). Furthermore, by reduction from the circuit value problem, deciding who has a winning strategy is P-complete even when $G$ is (finite and) acyclic and there are no draw states.


Why does the given solution to this problem works? How can it's correctness be proven?

There's a simple $O(n\log n)$ solution. It also sounds plausible that there is a linear time solution, but it seems to require a bit of case analysis.

First of all, instead of either decreasing by $k$ or increasing by $k$, we can first decrease all values by $k$, and then either not change the value or increase it by $\Delta := 2k$.

Suppose now that the sorted list is $x_1 < \cdots < x_n$. We first show that without loss of generality, an optimal solution increases a prefix of the sorted list. Indeed, consider a solution $y$ which increases $x_{i+1}$ but not $x_i$. Let us consider an alternate solution $z$ which doesn't increase $x_{i+1}$. Denote by $s(y),s(z)$ the span of the solution, which is the objective we're trying to minimize. If $s(y) \neq s(z)$ then $s(z)$ involves $z_{i+1}$, and so $z_{i+1}$ is an extreme point of $z$. Since $z_i < z_{i+1}$, necessarily $z_{i+1}$ is a maximum. Let $z_j$ be the other extreme point of $z$. Since $y_j = z_j$, we see that $s(y) \geq y_{i+1} - y_j = z_{i+1} + \Delta - z_j = s(z) + \Delta$, and so $z$ improves over $y$. We conclude that any optimal solution which increases $x_{i+1}$ must also increase $x_i$, and so also $x_{i-1},\ldots,x_1$, and generally increases a prefix of $x$.

The $O(n\log n)$ algorithm first sorts the list, and then considers all possible increases of prefixes. The idea is to consider what happens when not changing the list, when increasing $x_1$, then $x_1,x_2$, then $x_1,x_2,x_3$, and so on. At each point of this process, we need to know the span of the solution under consideration. When increasing $x_1,\ldots,x_i$, the minimum is always $x_{i+1}$ (there is no need to consider the case $i=n$). We can determine the maximum in an online fashion: if the maximum is $M$ before increasing $x_i$, then after increasing $x_i$ it is $\max(M,x_i+\Delta)$.

Here is the resulting algorithm, which assumes that we have already sorted the list.

Set $M \gets x_n$ (current maximum).
Set $O \gets x_n - x_1$ (smallest span currently known).
For $i=1,\ldots,n-1$:

Set $M \gets \max(x_i+\Delta,M)$.
Set $S \gets M-x_{i+1}$ (current span).
Set $O \gets \min(O,S)$.

Return $O$.


kd-tree stores points in inner nodes? If yes, how to search for NN?

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

Procedure NN(node), given query q
  if(node is leaf)
    Search all points, in node, update current best
  else {internal node}
    if( cut_coord(q) <= node's cut-value )
        NN(left-child)
        if( cut-coor(q) + current best distance > node's cut-value )
            NN(right-child)
        end if
    else {cut-coor(q) > node's cut value}
        NN(right-child)
        if(cut-coor(q) - current best distance <= node's cut-value)
            NN(left-child)
        end if
    end if(left/right)
  end if(node)

In order to perform ANN search, see the answer here.


Are there connections between the theory of computation and machine learning?

Yes, check out Computational learning theory (Algorithmic learning theory) and conferences COLT and ALT although the connection with machine learning is arguably limited.


Trouble understanding this proof about the minimum number of states of a deterministic finite automaton

Let $L$ be an arbitrary language. We say that two words $x,y$ are equivalent modulo $L$, written $x \stackrel{L}{\sim} y$, if for all words $z$, either both $xz,yz$ are in $L$, or both are not in $L$.

Lemma 1. Suppose that $x_1,\ldots,x_n$ are pairwise inequivalent modulo $L$. Then any DFA for $L$ must contain at least $n$ states.

Proof. Consider a DFA accepting $L$. Let $q_i$ be the state that the DFA reaches after reading $x_i$. I claim that $q_1,\ldots,q_n$ are all distinct. Indeed, consider any two states $q_i,q_j$. Since $x_i,x_j$ are inequivalent modulo $L$, there exists a word $z$ such that $x_iz \in L$ and $x_jz \notin L$, or vice versa; without loss of generality, assume the former. Since $x_iz \in L$, $\delta(q_i,z)$ must be an accepting state, whereas since $x_jz \notin L$, $\delta(q_j,z)$ must not be an accepting state. This shows that $q_i \neq q_j$. $\quad\square$

This is the method which is used in Proposition 5 that you mention.

What is the best lower bound that Lemma 1 can give us? Once you notice that $\stackrel L \sim$ is an equivalent relation, it is not hard to check that the maximum $n$ that you can choose is the number of equivalence classes of $\stackrel L \sim$:

Corollary 2. Any DFA for $L$ must contain at least $n$ states, where $n$ is the number of equivalence classes of $\stackrel L \sim$. In particular, if $\stackrel L \sim$ has infinitely many equivalence classes, then $L$ is not regular.

It is natural to ask whether this method is optimal:

If $L$ is not regular, can we always prove this using Corollary 2?
If $L$ is regular, is there always a DFA having $n$ states?

The positive answer to both questions is the main result of Myhill–Nerode theory, which you might learn about in the future.


How many time and space units does this algorithm take?

My thoughts about the question
Honestly speaking, this question is really weird. Usually when you ask about the time and space complexity, you mean it in big-O or other asymptotical notation. Not the actual literal number of steps the algorithm takes, since this can change depending on the hardware you are using and a lot of other factors.
So the fact that most answers are with the same asymptotics, it makes absolutely no sense!

My answer to the question
The answer depends on what you define a "time unit" and "space unit". Under normal circumstances, you would say this algorithm takes $\Omega(N\log(N))$ time, and would need $\Theta(N\log(N))$ space as well.
The explanation for that comes from the fact that $y$ at the $k$'th iteration is computed to be $k!$ ($k$ factorial). Saving in memory the value $N!$ needs $\log(N!)=\Theta(N\log(N))$ space, and thus also the running time must be at least $\Omega(N\log(N))$.
An upper bound for the running time depends on the algorithm used for multiplication.

Your answer to the question
Assuming multiplication takes $O(1)$ time, and a single unit of space is defined as a single variable, your solution is correct. This also demonstrates the problem of not using big-O notation, since your answer is correct however it is not one of the listed answers.


VC dimension of monotone disjunctions of length k over n variables?

Yes.  This bound follows by a little bit of straightforward manipulation:

$${n \choose k} = {n \times (n-1) \times \dots \times (n-k+1) \over k!} \le {n \times n \times \dots \times n \over 1} = n^k.$$

Now taking the logarithm of both sides, we see that

$$ \lg {n \choose k} \le \lg(n^k) = k \lg n.$$

The bound can also be derived from bounds listed in Wikipedia: it follows from the fact that ${n \choose k} \le n^k/k!$.  Check out Wikipedia in the future -- it's often helpful!


Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

The general $n \times m$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $t_j = 0$ for each column.

A slightly more complicated reduction from subset sum shows that this is NP-hard even for $m = 2$. Suppose we are given a subset sum problem instance where we have a set $B$ of integers and the goal is to find a subset of $B$ that sums to exactly $k$. We reduce this to your problem as follows: for each integer $b \in B$, add $[b, -b]$ as a row to $A$; then set $t_1 = k - 1$ and $t_2 = -k - 1$. This enforces that the sum of the chosen subset must be greater than or equal to $k$ and also less than or equal to $k$, and therefore exactly equal to $k$.

For solving this problem in practice, I would recommend an integer linear programming solver. Most such solvers have direct support for 0-1 variables, so the linear optimization version you describe in the question can be presented to the solver exactly as written.


What are the differences between propositional logic and temporal logic?

An interpretation in propositional logic consists of assigning a truth value to every variable. In contrast an interpretation of, say, LTL consists of assigning a truth value to every variable at each point in time. So the domain of discourse is different. Propositional logic is about variables having a definite truth value, whereas LTL is about variables having a truth value depending on time.

Everything that can be expressed in propositional logic can also be expressed in LTL, by just always referring to the truth value at time zero. We say that propositional logic is interpretable in LTL. The converse isn't true – you can't express temporal concepts in propositional logic. You use temporal logic when you need to express temporal concepts. In situations where you don't need to express temporal concepts, you use propositional logic.

The language of set theory is rich enough to encompass both propositional logic (and its extension, predicate logic) and temporal logic. However, the language of set theory might be too expressive for your comfort at times (for example, it may be hard to process algorithmically), which is why we are interested in propositional logic and temporal logic.


Analogue of the topology-computability correspondence for computational complexity

The answer to your literal question is neither. The reasoning in your question makes perfect sense, and there are several researchers working on the details on what exactly is analogous to complexity theory in the same way topology is analagous to computability. However, I don't think I am unfair in claiming that this is nowhere near completed.
In a compact metric context, notions such as metric entropy seem to be important, and the counterpart to "continuous" seems to be "having a modulus of continuity of particular growth". Beyond compact metric, the picture quickly gets very unclear.
I don't know of a comprehensive written treatment, but Martin Ziegler just gave a tutorial on this at the conference "Computability in Europe". The talks are up on this Youtube channel, specifically "Quantitative Coding and Complexity theory...".


Prove whether this problem is decidable or undecidable

I believe that you ask whether the following language is decidable:

$$L_{\text{visit all}} = \{ \langle M,w\rangle \mid \text{  $M$ run on $w$ visits all its non-halting states}\}$$

I believe this language is undecidable. The reason is similar to the reason why the following language is undecidable:
$$L =\{ \langle M,w\rangle \mid \text{$M$ visit the state $q_1$ when running $w$}\}$$
Very iformally: You can see it by "designating" one state to be special, so if we reach it, it means acceptance. Then reaching all states is equivalent to halting problem.


Theoretical machines which are more powerful than Turing machines

Yes, there are theoretical machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is hypercomputation.


Show that a language belongs to the polynomial hierarchy

Let me assume your are familiar with the oracle-version of the polynomial hierarchy. Thus, if $L\in \Sigma_k$, then there exists a (non-deterministic polytime) Turing machine $M$ with oracle $\Sigma_{k-1}$.

To show that $L^*$ is also in $\Sigma_k$ we explain how one could build a new non-deterministic polytime Turing machine $M^*$ with oracle $\Sigma_{k-1}$ that accepts $L^*$. The key idea is, that we use the (simulation) of $M$ as a sub-module for $M^*$.

The machine $M^*$ works as follows. It guesses a partition of the input $w$ into some words $u_1u_2\cdots u_k$. Then it runs the simulation for $M$ for every $u_i$. If the simulation verifies that all $u_i\in L$ then $M^*$ accepts, otherwise it rejects. Clearly $M^*$ accepts $L^*$ and uses only the oracle $\Sigma_{k-1}$. What is left to check is if $M^*$ runs in polytime. The running time of $M^*$ is dominated by
$$t_M(|u_1|)+t_M(|u_2|)+\cdots+ t_M(|u_k|)\le t_M(n)+t_M(n)+\cdots+ t_M(n)\le n \cdot t_M(n),$$
for $n=|w|$. Since $t_M(n)$ is a polynomial, we have that $n\cdot  t_M(n)$ is a polynomial as well.


Techniques (tools) to convert temporal logic (CTL,CTL* or LTL) to μ-calculus formulae

You may find an answer or at least relevant references in the article
A linear translation from LTL to the first-order modal $\mu$-calculus.


special case of best first search algorithms

Consider a node $u$ such that $depth(u)=l$.

In Best first Search when you evaluate $u$ with the evaluation function you defined, you have $f(u)=−l$.

queue

╔═══╤═══╤═════╤═══╗
║ r │ a │ ... │ u ║
╚═══╧═══╧═════╧═══╝

When you expand $u$ and you evaluate the first child of $u$ (suppose it is Node $v$) you have $f(v)=−(l+1)<−l=f(u)$ so now you expand $v$ (that means that you put $v$ in the front of the queue) and you continue.

queue

╔═══╤═══╤═════╤═══╤═══╗
║ r │ a │ ... │ u │ v ║
╚═══╧═══╧═════╧═══╧═══╝

This corresponds to what you do when you use Depth First Search.


What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically?

In most CS contexts, including this one, $X^*$ means any number of $X$'s, including zero, and $X^+$ means one or more $X$'s.

So $A\Rightarrow^* B$ just means that $A$ gets to $B$ by some number of steps and, if that number is zero, then $A=B$. More formally, it means that there is some number $\ell\geq 1$ and objects $C_1, \dots, C_\ell$ such that $A=C_1$, $B=C_\ell$ and $C_i\Rightarrow C_{i+1}$ for each $i\in\{1, \dots, \ell-1\}$.  $A\Rightarrow^+ B$ means the same thing except with $\ell\geq 2$.

So, for example, given the grammar
$$S\to aS\mid b\,,$$
we have
$$S\Rightarrow aS\Rightarrow aaS\Rightarrow aab\,,$$
so we can write $S\Rightarrow^*aab$. In this case, $\ell=4$, $C_1=S$, $C_2=aS$, $C_3=aaS$ and $C_4=aab$.  Since $\ell\geq 2$, we can also say $S\Rightarrow^+ aab$. We can also write $S\Rightarrow^*S$, which is $\ell=1$, $C_1=S$; but we can't write $S\Rightarrow^+S$, because any positive number of productions from $S$ will give a string with at least one terminal symbol in it.


Is paradox recognition paradoxical or not paradoxical?

Russel's paradox does not apply to the lambda calculus. Intuitively speaking, Russel's paradox comes up when there is a level system (e.g. sets that are members of “bigger” sets one level up), and there is a form of negation. The lambda calculus has neither: all lambda terms are at the same level and there is no negation.

I don't know what you think you mean by “The lambda-expressions that may not be applied to themselves”. Any lambda term can be applied to any lambda term.

An analog of Russel's paradox (or rather the similar Burali-Forti paradox) arises in the higher-order typed lambda calculus, where terms have types that themselves have types. If $\mathsf{Type} : \mathsf{Type}$, it's possible to construct a well-typed term that of type $\mathsf{Type}$ that does not terminate. See Example of a false proposition when assuming Type : Type. As can be done in set theory, type theory can solve the problem by adding a universe stratification: base types have the sort $\mathsf{Type}_0$ and higher-order types obey $\mathsf{Type}_n : \mathsf{Type}_{n+1}$.


Is the language of words with as many a's in the first as b's in the second part context-free?

Yes, the language is context-free.

Let $w$ be a word in $\{a,b\}^*$. Decompose it as $w = u v$ where $|u| = N_b(w)$.
$$ \begin{align}
  N_a(u) &= N_a(w) - N_a(v) && \text{because \(w = u v\)} \\
         &= N_a(w) - (|v| - N_b(v)) && \text{because \(v \in \{a,b\}^*\)} \\
         &= N_a(w) - |w| + |u| + N_b(v) && \text{because \(|v| = |w| - |u|\)} \\
         &= |u| - N_b(w) + N_b(v) = N_b(v) \\
\end{align} $$
Thus we can decompose any word in the desired form: $L = \{a,b\}^*$. Constructing a PDA is left as an exercise to the reader.

This still works if the language contains other letters, by the way, but you have to take a prefix of $w$ that contains $N_b(w)$ letters in $\{a,b\}$ and arbitrarily many other letters.

Another way to see this is to notice that if there is an $a$ in $u$ and a $b$ in $v$, then you can swap the two letters, which results in a word that has the same balance $N_a(u) - N_b(v)$. $L$ is the set of words whose balance is zero for some split position. Iterate this decomposition until it becomes impossible: either $u$ contains no $a$ or $v$ contains no $b$. If we choose the split position so that $|u| = N_b(w)$ and $|v| = N_a(w)$, then now $u$ contains all the $b$'s and $v$ contains all the $a$'s: $N_a(u) = 0$ and $N_b(v) = 0$, and in particular the balance is 0.


Operating Systems TestAndSet instruction

You are right, TestAndSet doesn't test the value of the flag, it merely sets it, but returns the previous value, which must be tested elsewhere.

The trick is that as the assignment is atomic, only one process can cause a transition from 0 to 1 (others only cause a "transition" from 1 to 1), and only it can pass the while.


There are many ways this kind of situation be handled.

Clever compilers

If you are are writing the contents of, lets say register 5 to the memory location 0x12345, and the next instruction is reading from the memory location 0x12345 and the variable allocated at memory location 0x12345 is not "volatile", compiler will optimize your code so that the next instruction will use the contents of register 5, instead of reading data from the memory.

Instruction reordering

Ordering of the instructions are changed so that the next instruction is pushed down, as far as required without compromising the outcome of the program. This way, more non-dependent instruction can be executed until the memory write is complete.

Multiple threads

When the scheduler detects that there is a read after write dependency, it can pick another thread for thread for the IF stage. That way, the current thread will stay inactive until the memory write is complete. Once completed it becomes active again, and will get picked up by the scheduler when a similar situation arises for the current thread.

Bubbles

And of course, you can have many bubbles in the pipeline, until the write is complete :-). BTW, this is a bad idea.


Can a turing machine calculate word's length?

Replace every character in the input string with a $1$; you then have the length of the string in unary notation. Then convert the unary representation to your favorite base $b$ by successive division by $b$.


How do computers really communicate with hard-drives on x86_64?

The processor has a control bus which allows it to tell the motherboard it wants to write somewhere else than RAM. When the processor sets a certain line on the control bus, it can write data to a port instead of RAM.
The processor can send data to certain ports which, by convention, are used to talk to hardware. The Hard-Drives have controllers which will answer to certain values on their respective conventional ports. These will be called commands. SATA drives which are the most common types today use certain ports for bilateral communication between processor and hard-drive.
An example is PIO mode that all SATA compliant drives must respect. In PIO mode (https://wiki.osdev.org/ATA_PIO_Mode), the port 0x1f7 is used to send commands to the drive. It will then output its data onto a certain port that the processor will read to fetch the data.
As to USB, it is similar. The USB controller (xhci today see https://wiki.osdev.org/XHCI and https://wiki.osdev.org/Universal_Serial_Bus#USB_2.0_Host_Controllers) is actually polling its own USB port to determine if a device is plugged in at some point. This provides the plug and play functionalities.
When you do a read/write operation you use IO ports again just like before but these ports are mapped to RAM addresses creating RAM holes known as the PCI hole. To determine the memory mapped ports locations you need to parse the ACPI tables which are built by the BIOS during initialisation of the system. The ACPI tables have conventional locations in RAM that the OS can look for. Once the OS finds these tables it needs to interpret language known as AML to determine what devices are connected on the computer and where (at what RAM address) to find the ports/registers to communicate with these devices.
Other hardware then hard-drives (keyboard/mouse) work with interrupts and ports which is another complex subject.
PS: Developping your own x86-64 operating system is not that unrealistic. Osdev.org can help on that path. If you have some time and go step by step you will learn a lot.


Is this language is Context-free language or not?

You can't use the pumping lemma to prove that a language is context-free (see, e.g., here).  The pumping lemma is only useful to prove that the language is not context-free.  See our reference questions for details on how to prove that a language is or isn't context-free: How to prove that a language is context-free?, How to prove that a language is not context-free?.

So, one thing wrong with your proof is where you say "if... the word stays inside language the language is context-free" -- that's not correct.


Is it possible to use an adjacency matrix for Bellman-Ford algorithm?

It is possible to use an adjacency matrix, but you will increase the runtime in most cases.
The main core of the algorithm is, that you iterate over all edges and try to relax the distance approximations.
If you have an adjacency list, you can efficiently iterate over all edges in $O(|E|)$ time, and get the the worst case complexity $O(|V| \cdot |E|)$ in total.
If you however use an adjacency matrix, in most cases you cannot iterate over all edges as efficiently. You could iterate over all entries in the matrix, and check for each one if the edge exists (e.g. check if the distance stored is infinity), however that will require $O(|V|^2)$ time and therefore lead to a total complexity of $O(|V|^3)$.
If you have a dense matrix $|E| \approx |V|^2$, then this will result in the same time complexity $O(|V| \cdot |E|) = O(|V|^3)$, but if you have a sparse graph, $|E| \approx |V|$, then iterating over all edges will take significant slower and you get the complexity $O(|V|^3)$ even though with a with an adjacency list you would have the complexity $O(|V| \cdot |E|) = O(|V|^2)$.
So it would be better, to simply convert the adjacency matrix into an adjacency list, or just a simple list of all edges.


To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question

  For some kinds of binary search trees, including red-black trees but
  not AVL trees, the "fixes" to the tree can fairly easily be predicted
  on the way down and performed during a single top-down pass, making
  the second pass unnecessary. Such insertion algorithms are typically
  implemented with a loop rather than recursion, and often run slightly
  faster in practice than their two-pass counterparts.

So a RedBlack tree insert can be implemented without recursion, on some CPUs recursion is very expensive if you overrun the function call cache  (e.g SPARC due to is use of Register window)

(I have seen software run over 10 times as fast on the Sparc by removing one function call, that resulted in a often called code path being too deep for the register window.   As you don't know how deep the register window will be on your customer's system, and you don't know how far down the call stack you are in the "hot code path", not using recursion make like more predictable.)

Also not risking running out of stack is a benefit.


What was Robert Floyd's algorithm for inserting brackets?

The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today.
The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm used to parse Algol-60, commonly referred to as the "Shunting Yard Algorithm". Floyd's contribution was to formalise and extend the idea, making it into a practical general-purpose parsing technique.
Floyd's approach to parsing was highly influential on another young parsing investigator of the time, Donald Knuth, whose 1965 paper "On the Translation of Languages from Left to Right" introduced the LR(k) parsing algorithm, capable of parsing a much larger set of languages than operator precedence parsing. However, it was not until 1969 when Frank deRemer invented the computationally manageable LALR(1) algorithm described in "Practical Translators for LR(k) languages" that Knuth's discovery moved out of the theoretical realm and into practical compiler construction.
Floyd's 1961 paper "An algorithm for coding efficient arithmetic operations", cited in the OP, was not about parsing ("inserting brackets properly") but rather about efficiently ordering the computation of the parsed expression so as to maximize the use of scarce CPU resources, based on the very limited CPU architectures common at the time. Modern CPU architectures demand different algorithms, but parts of Floyd's 1961 algorithm can be found in simple optimizations for minimising the stack size in stack-based virtual machines (or, equivalently, the number of temporaries required in three-address-code).

For reference, a quick summary of Floyd's operator precedence algorithm. The algorithm takes as input a precedence grammar $G$, which is a context-free grammar with the property that no right-hand side contains two consecutive non-terminals. (This definition allows unit productions and null productions; in practice, these would usually be removed before proceeding since they do not participate in the parsing algorithm.)
As usual, we will write $G = \langle N, T, P, S\rangle$, where $N$ is the set of nonterminal symbols, $T$ the set of terminal symbols, $P \subset N \times (N \cup T)^*$ the set of productions and $S \in N$ the target (start) symbol. We will use uppercase letters to represent symbols in $N$, lowercase letters to represent symbols in $T$ and Greek letters to represent sentences which are elements of $(N\cup T)^*$. We write $\alpha \Rightarrow \beta$ if $\alpha$ derives $\beta$ (that is, $\alpha = \alpha_1 A \alpha_3$ and $\beta = \alpha_1\alpha_2\alpha_3$, where $A\rightarrow\alpha_2 \in P$). Also, we write $\Rightarrow^+$ and $\Rightarrow^*$ for the transitive closure and reflexive transitive closure of $\Rightarrow$.
Then we define three precedence relations over $T$: $\lessdot$, $\doteq$ and $\gtrdot$ , defined as follows:
$a \lessdot b \text{ if } A\rightarrow\alpha a B \beta \in P \text{ and either } B\Rightarrow^+b\gamma \text{ or } B\Rightarrow^+Cb\gamma$
$a \gtrdot b \text{ if } A\rightarrow\alpha B b \beta \in P \text{ and either } B\Rightarrow^+\gamma a \text{ or } B\Rightarrow^+\gamma aC$
$a \doteq b \text{ if either } A\rightarrow\alpha a b \beta \in P \text{ or } A\rightarrow\alpha a C b \beta \in P $
For an intuition about these symbols, think of a derivation being written with $\langle$ and $\rangle$ surrounding the strings replacing each nonterminal. Then $a\lessdot b$ holds if there is such a derivation where $b$ follows $a$ after a sequence of $\langle$s possibly followed by a single nonterminal. (Note that the operator property guarantees that there could not be two consecutive nonterminals.) In other words, ignoring nonterminals, $b$ is the first terminal in a reduction following $a$. $\gtrdot$ is analogous: $b$ is the first terminal following a reduction whose last terminal was $a$. (Again, the operator property guarantees that $b$ is not preceded by a nonterminal, since a nonterminal cannot follow a reduction.) $a\doteq b$ holds if $a$ and $b$ are consecutive terminals in a production, possibly separated by a (single) nonterminal.
Now, if the three precedence relations $\lessdot$, $\gtrdot$ and $\doteq$ are disjoint, we call $G$ an operator precedence grammar.
For simplicity, we will parse the augmented grammar
$$G' = \langle N\cup\{S'\}, T\cup\{\#\},P\cup S'\rightarrow S\#, S'\rangle$$
where $\#$ is some symbol not in $T$. It's easy to verify that $a\lessdot \#$ for every $a \in T$ and that there is no other precedence relation involving $\#$. We also add a $\#$ to the end of the input. Then we can parse the input as follows:

Create a parser stack $S$ consisting only of the symbol $\#$.

For each input symbol $b$ in turn, from left to right:

While $TOP(S) \gtrdot b: \;POP(S)$
If $b = \#$ and $top(S) = \#$, $ACCEPT$ the input
If $TOP(S) \lessdot b \text{ or } TOP(S) \doteq b: \;PUSH(S, b)$. Otherwise, $REJECT$ the input.

In practice, we'll actually want to record the derivations discovered by this algorithm. If we $POP$ the stack in step 2.1, the popped symbols (both terminals and nonterminals) are accumulated into $X$, and just before we continue with step 2.2, we find the production in $P$ whose right-hand side is $X$, and output that production as a derivation step. If there is more than one such production, then we need some auxiliary algorithm to decide which one to use; usually, we sidestep the problem by requiring that the right-hand sides be unique. (This is also why it's common to eliminate unit and null productions, because the Floyd algorithm provides no clue whatsoever about when to insert their derivation steps.)

Like many others, I think Floyd's contribution to parsing theory was fundamental. But it is important not to be seduced by the beautiful simplicity of his algorithm. As Floyd himself noted, it suffers from two important issues:

It is not sufficient to parse many programming languages, whose grammars cannot conveniently be written as operator grammars with unique right-hand sides or do not yield disjoint precedence relations.

The fact that a string is accepted by the algorithm does not guarantee that the string is accepted by the grammar. Many syntactically invalid strings are accepted and must be filtered out using other algorithms.

Floyd's later work, including his investigation into bounded-context grammars, sought to overcome these shortcomings.


There is a $O(|X|)$ algorithm for this problem using a stack.

Algorithmic details:

For a building $i\in \{1, ..., n\}$, we will be pushing $i$ onto the stack $S$. For building $i$, let $X_i$ be its coordinate, $H_i$ be its height and $R_i$ be its range.
While iterating over the data (i.e. $i = 1 ... n$), we maintain the loop invariant that $S$ will only contain indices $j$ such that $R_j \ge X_i$ at the end of $i$-th iteration.
The loop invariant implies that for buildings $k$ and $k'$, where $k<k'$, which are next to each other in $S$, we have $R_k=\max(X[k]+H[k], R_{k'})$.
At the start of $i$-th iteration, to maintain the loop-invariant, we must pop all indices $j$ from top of $S$ such that $R_j \lt X[i]$.
The loop invariant also forces us to push $i$ on top of $S$ at the end of $i$-th iteration.
(Edit) Running time will be $O(|X|)$ because each $X_i$ gets pushed on to the stack $S$ (and subsequently popped off) only once for each $i \in \{1,...,n\}$. And we need not do more than $O(1)$ work with each operation on $S$.
(Edit) Space complexity will be $O(|X|)$. Observe the case where $X=\{1,2,3,...,n\}$ and $H=\{n,n-1,n-2,...,1\}$ for some $n\in \mathbb{N}$. That is, pushes onto the stack will happen before any pops.

Insight:

Think about maximal sets of buildings (not necessarily contiguous) where if one falls, then all the ones on its right within the same set will fall too. Now if we look at lowest and highest indices of buildings in such a set as endpoints of an interval, then intervals are either contained within one another or they don't overlap at all. That is, there is always at least one set of contiguous buildings. If this set is removed from the list of buildings, another set will now have contiguous buildings.

Code (Python 3.x):

import random

MAX_RANGE = 2**32

#implementation of the explained O(|X|) algorithm
def building_dominoes(X, H):
    ''' For building i, we store (i, X[i] + H[i]) on the stack
        to simplify some aspects of the implementation. Same is
        the reason for using MAX_RANGE. These can be done away
        with easily.
    '''

    s, result, rang = [], [0]*len(X), 0

    for i in range(len(X)):
        clear_stack(s, X[i], result)
        s.append((i, X[i] + H[i]))

    clear_stack(s, MAX_RANGE + 1, result)

    return result

def clear_stack(s, x, result):
    range_max = 0
    while s and s[-1][1] < x:
        j, new_range = s.pop()
        result[j] = range_max = max(range_max, new_range)

# brute-force version
def brute_force(X, H):
    n = len(X)
    res = [0] * n
    for i in range(n-1, -1, -1):
        res[i] = max([X[i] + H[i]] + [res[j] for j in range(i+1, n) if X[j] <= X[i] + H[i]])
    return res

# small set of tests
META_X = [
    [5, 6, 9, 11],
    [0, 1],
    [1, 2, 3, 4, 5],
    [1, 2, 3, 4, 5],
    [1, 2, 3, 6, 8, 10],
]
META_H = [
    [2, 3, 1, 5],
    [9, 1],
    [2, 4, 6, 8, 10],
    [10, 8, 6, 4, 2],
    [8, 3, 1, 2, 1, 1],
]

success = 0
for i in range(len(META_X)):
    if building_dominoes(META_X[i], META_H[i]) == brute_force(META_X[i], META_H[i]):
        success += 1
print(f"Passed {success} tests from the specified set of {len(META_X)} tests.")

# randomized tests
VALS = list(range(100000))
MIN_N, MAX_N = 10, 500
NUM_TESTS = 500
success = 0
for i in range(NUM_TESTS):
    size = random.randint(MIN_N, MAX_N + 1)
    X = sorted([random.choice(VALS) for _ in range(size)])
    H = [random.choice(VALS) for _ in range(size)]
    if building_dominoes(X, H) == brute_force(X, H):
        success += 1
print(f"Passed {success} tests from the set of {NUM_TESTS} randomized tests.")


$\mathcal{INDSET}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $x_v$.

For each edge $uv\in E$, create a clause $\lnot x_u \lor \lnot x_v$

Now, to assure that there exist exactly (or more than) $k$ variables assigned to $\mathrm{TRUE}$, we need to sum over all the assigned value ($\mathrm{FALSE}$ as $0$, $\mathrm{TRUE}$ as $1$):

We use half-adder and full-adder. Note that each circuit gate using some Boolean operation like $C = A \oplus B$ can be transformed into $\mathcal{3SAT}$ clauses easily.

To compare the obtained sum and $k$, it is straightforward from their binary representations (as two arrays of Boolean variables), just scan from left to right (in big-endianness fashion).

$\mathcal{MAX-CUT}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $s_v$. A cut is then described by a partition of the vertex set $V=S\cup (V\setminus S)$, where $v\in S$ iff. $s_v=\mathrm{TRUE}$.

For each edge $e=uv\in E$, create a Boolean variable $c_e$ and some clauses to force that $c_e=(s_u\neq s_v)$. So, $c_e=\mathrm{TRUE}$ iff. $e$ is crossing $(S, V\setminus S)$.

Then, we use half-adder and full-adder as before to count the number of crossing edges. Lastly, compare as before.


Full circularity vs strong circularity for attribute grammars

You are using the terms in a weird way. A grammar can be circular or non-circular. Since FULLY testing this property is EXPTIME, one wants a simpler (easier to test) property.
This is where strong NON-circularity comes in. In strong non-circularity, you basically combine the dependencies of all possible sub-trees, even for combinations that can't appear together. So if a grammar is strong non-circular, it particularly rules out the combinations that CAN happen together. I.e. the grammar is non-circular.

So this means that strong NON-circularity implies NON-circularity. Sure you can invert implications by negating both sides of it. I think this is what you did when you say that "Full circularity implies strong circularity".
But I don't think it makes sense to call a grammar that is NOT strongly NON-circular "strong circular". IMHO that would be a confusing term, because it sounds like such a grammar was "even more circular" than other grammars, but it is the opposite - it only fails the strong-non-circularity test which isn't a necessary condition. So such a grammar would rather be "less circular" than other grammars, because it "looks circular" without necessarily being circular.
But that doesn't sound right either (because in the end, it is either circular or not). If anything, I would call it "weakly circular", because that property doesn't guarantee anything - to be certain, you still need to apply the full circularity test.

To adress the question: in practice you usually only work with S-Attribute Grammars, which don't even need to be tested for circularity, because they can't be circular.

I dug out this example (attributes starting with i are inherit attributes, attributes starting with s are synthetic ones):

S -> A
    ix.1 = 1        (1)
    iy.1 = 2        (2)
    sx.0 = sz.1     (3)
A -> A a
    ix.1 = sy.1     (4)
    iy.1 = ix.0     (5)
    sy.0 = sz.1     (6)
    sz.0 = 0        (7)
A -> a
    sy.0 = 0        (8)
    sz.0 = ix.0     (9)
A -> b
    sy.0 = iy.0     (10)
    sz.0 = 0        (11)

this grammar is non-circular, but it fails the strong-non-circularity test, because in the strong-non-circularity test, you take the union of the dependency-sets for the productions of the same nonterminal. So you have the edges for both A->a and A->b together, although they can't appear together (because you can't apply both productions at the same time).

The production of A -> A a then yields the following dependency-graph:
let Q and R be the prefixes for the two A's in the production, then you have the nodes

{ Qia, Qib, Qsb, Qsc, Ria, Rib, Rsb, Rsc }

and the edges

{ (Qsb, Qia),     from (4)
  (Qia, Rib),     from (5)
  (Rib, Rsb),     from (10)
  (Rsb, Ria),     from (4)
  (Ria, Rsc),     from (9)
  (Rsc, Qsb)      from (6)
}

this is a cycle and therefore the strong-non-circularity test fails. The point why the strong-non-circularity test is wrong here, is because the edges (Rib, Rsb) and (Ria, Rsc) come from different productions.


If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

Here is a hint.

You need your machine to initially accept part of a word from $L$, consuming the tape as it goes. Then, without consuming anything, you need to find some word from $R$ that will push the machine into a final state. The chosen word from $R$ plays the role of the input word for the second half of the computation.

Clearly, non-determinism will have a role, as will the product between the two machines. The trick in formalising this is adjusting the product to deal with the fact that the input comes from $R$ not from the input.


Is $2^n$ steps enough to tell if DTM will run forever?

More precisely, if a deterministic Turing machine has an alphabet $\Sigma$, and a set of states $|Q|$ and consumes at most $f(|x|)$ space then the maximum number of configurations the machine can have is $$|Q|\times f(|x|) \times|\Sigma|^{f(|x|)}$$
This is because the maximum length of the tape portion (cells in fact used by the machine) is $f(|x|)$, the head of Turing machine at any time can be located on one of the $f(|x|)$ cells, the machine may be in $|Q|$ different states, and this portion of the tape can be filled in $|\Sigma|^{f(|x|)}$ different ways (using alphabet symbols).

If $q=|Q|$ and $|\Sigma| = 2$ (binary alphabet) then we have
$$qf(|x|)2^{f(|x|)}$$
different configurations.

Each step of a Turing machine may change machine's state, tape content, or the position of the head. So after $qf(|x|)2^{f(|x|)}$ steps if the machine hasn't yet halted it must repeat the configuration: $\langle$ state, tape content, head position $\rangle$ meaning the machine will loop forever. So I would say it needs $O(f(|x|)2^{f(|x|)})$ steps rather than $O(2^{f(|x|)})$.


Both CRC and the Hamming code are binary linear codes. One significant difference is that the Hamming code only works on data of some fixed size (depending on the Hamming code used), whereas CRC is a convolutional code which works for data of any size.

So, are CRC and the Hamming code fundamentally different ideas? This is a philosophical rather than a technical question, and so has no definite answer. It could also depend on your point of view. From far away, both are binary linear codes. From up close, there are some crucial differences.


Minimize sum of squares of rows in matrix when sum of columns have some constraint

Summary

Solve iteratively by pseudo-inverse, set negative $x_{ij}$ to 0, and remove negative $x_{ij}$ from equations.

Warning: seems to always work only if number of rows equal to the number of columns. Don't know if it is because of ill-conditioning of matrix or the initial guess is too far off or bug.

Lagrange Multipliers

I will write in math's ordering of index.

$x_{ij}$ is the element of matrix $X$ at row $i$ and column $j$.

The square of column sum of the $j^{th}$ column is:

$$\left(\sum_{i} x_{ij} \right)^{2}$$

The row sum constraint for the $i^{th}$ row is:

$$0 = s_i - \sum_{j} x_{ij} $$

Optimize sum of square of column sums by Lagrange multipliers:

$$
  L = \left [ \sum_{j} \left(\sum_{i} x_{ij}\right)^2 \right ] - \sum_{i} \lambda_i\left(s_i - \sum_{j} x_{ij}\right)
$$

Set derivatives to zero:

$$\forall i, j: 0 = \frac{\partial L}{\partial x_{ij}} = 2\left (\sum_{k} x_{kj}\right) + \lambda_{i}$$

$$\forall i: 0 = \frac{\partial L}{\partial \lambda_{i}} = s_i - \sum_{j}x_{ij} $$

Pseudo-inverse

Matrix equation:

$$A\vec{y} = \vec{b}$$

"Solve" by Moore-Penrose inverse (pseudo-inverse)

$$\vec{y} = A^{+}\vec{b}$$

This gives a solution that is as good as possible, even when some of the equations conflicts with each other.

Karush–Kuhn–Tucker conditions

What if the solution says some of the $x_{ij}$ is negative?

We set all negative $x_{ij}$ to zero, remove these variables from the matrix equation, and solve by Moore-Penrose inverse again. Repeat until no more negative $x_{ij}$.

(This is a simplified version of KKT because I don't understand everything in KKT yet.)

See: https://math.stackexchange.com/questions/1747435/correct-formulation-of-equality-and-non-negativity-constrained-non-linear-minimi

https://optimization.mccormick.northwestern.edu/index.php/Quadratic_programming

Example

I will explain with the 1-4-1 problem as an example.

Let $\vec{y}$ be the coefficients in row-major ordering and the $\lambda_i$

$$\vec{b} = \begin{bmatrix}
x_{1,1}&x_{1,2}&x_{1,3}&x_{2,1}&x_{2,2}&x_{2,3}&x_{3,1}&x_{3,2}&x_{3,3}&\lambda_{1}/2&\lambda_{2}/2&\lambda_{3}/2\\
\end{bmatrix}^{T}$$

where $[\cdot]^{T}$ denotes transpose of a matrix/vector.

I define a geometry matrix $G$. If $g_{ij} = 0$, $x_{ij}$ should be zero.
$$G = \begin{bmatrix}
{\color{red}1}&{\color{red}1}&{\color{red}0}\\
{\color{green}0}&{\color{green}1}&{\color{green}0}\\
{\color{blue}0}&{\color{blue}1}&{\color{blue}1}\\
\end{bmatrix}$$

Matrix $A$ is:

$$A = \begin{bmatrix}
{\color{red}1}&{\color{red}1}&{\color{red}0}&0&0&0&0&0&0&0&0&0\\
0&0&0&{\color{green}0}&{\color{green}1}&{\color{green}0}&0&0&0&0&0&0\\
0&0&0&0&0&0&{\color{blue}0}&{\color{blue}1}&{\color{blue}1}&0&0&0\\ \hdashline
{\color{red}1}&0&0&{\color{green}0}&0&0&{\color{blue}0}&0&0&{\color{magenta}1}&0&0\\
0&{\color{red}1}&0&0&{\color{green}1}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}&0\\
0&0&{\color{red}0}&0&0&{\color{green}0}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}\\
\end{bmatrix}$$

Upper half is for constraints.
Bottom half is for $0 = {\partial L}/{\partial x_{ij}}$.
The magenta numbers are for $\lambda_1$, $\lambda_2$, and $\lambda_3$.

The $\vec{b}$ is just the row sum padded by zeros:

$$\vec{b} = \begin{bmatrix}1&4&1&0&0&0\\\end{bmatrix}^{T}$$

Result

--- cycle 0 ---
    Matrix A:
        [[1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.4 -0.4  0.   0.   4.   0.   0.  -0.4  1.4 -1.4 -3.2 -1.4]]
    X:
        [[ 1.4 -0.4  0. ]
         [ 0.   4.   0. ]
         [ 0.  -0.4  1.4]]
    lambda^{T} / 2:
        [[-1.4 -3.2 -1.4]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1.4 3.2 1.4]
--- cycle 1 ---
    Matrix A:
        [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.  0.  0.  0.  4.  0.  0.  0.  1. -1. -4. -1.]]
    X:
        [[1. 0. 0.]
         [0. 4. 0.]
         [0. 0. 1.]]
    lambda^{T} / 2:
        [[-1. -4. -1.]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1. 4. 1.]

Program

import numpy as np
from numpy.linalg import pinv, lstsq

def vec_y_split(vec_y, geometry):
    """Reshape vec_y into reshaped vec_y matrix and lambda
    """
    n_rows, n_cols = geometry.shape
    return vec_y[:-n_cols].reshape(geometry.shape), vec_y[-n_cols:]

def array_to_indent_str(x, indent=1):
    s = " " * indent * 4
    return s + str(x).replace("\n", "\n" + s)

def print_vec_y(vec_y, geometry, row_sum, indent=0):
    c, lam = vec_y_split(vec_y, geometry)
    s = " " * indent * 4
    print(s + "X:")
    print(array_to_indent_str(np.around(c, 3), indent + 1))
    print(s + "lambda^{T} / 2:")
    print(array_to_indent_str(np.around(lam.T, 3), indent + 1))
    print(s + "row sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=1), 3), indent + 1))
    print(s + "column sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=0), 3), indent + 1))
    print(s + "Error (Not considering zero requirement):")
    err = np.sum((c.sum(axis=1) - row_sum) ** 2) ** 0.5
    print(s + str(err))

def make_mat_A(geometry):
    n_rows, n_cols = geometry.shape
    mat_A = np.zeros((n_cols + n_rows, geometry.size + n_cols))
    # row equations
    for i in range(n_rows):
        for j in range(n_cols):
            mat_A[i, i * n_cols + j] = geometry[i, j]
    # col equations
    for j in range(n_cols):
        mat_A[n_rows + j, geometry.size + j] = 1
        for i in range(n_rows):
            mat_A[n_rows + j, i * n_cols + j] = geometry[i, j]
    return mat_A

def make_vec_b(geometry, row_sum):
    n_rows, n_cols = geometry.shape
    vec_b = np.empty((n_cols + n_rows, 1))
    vec_b[:n_rows, 0] = row_sum
    return vec_b

def remove_var(geometry, mat_A, coeff, epsilon):
    n_rows, n_cols = geometry.shape
    for i in range(n_rows):
        for j in range(n_cols):
            ix = i * n_cols + j
            if coeff[ix] < -epsilon:
                mat_A[:, ix] = 0

def iterate(geometry, mat_A, vec_b, vec_y, row_sum):
    i = 0
    epsilon = 1e-7
    n_rows, n_cols = geometry.shape

    while i == 0 or np.any(vec_y[:-n_cols] < -epsilon):
        print("--- cycle %d ---" % i)
        print("    Matrix A:")
        print(array_to_indent_str(np.around(mat_A, 3), 2))
        print("    Vector b^{T}:")
        print(array_to_indent_str(np.around(vec_b.T, 3), 2))

        vec_y = lstsq(mat_A, vec_b, rcond="warn")[0]

        if i > 0:
            remove_var(geometry, mat_A, vec_y, epsilon)

        print("    Vector y^{T}:")
        print(array_to_indent_str(np.around(vec_y.T, 3), 2))
        print_vec_y(vec_y, geometry, row_sum, indent=1)

        i += 1

def search(geometry, row_sum):
    print("=== Start ===")
    print("row_sum^{T}:")
    print(row_sum.T)
    print("geometry:")
    print(geometry)
    n_rows, n_cols = geometry.shape
    vec_y = np.empty(geometry.size + n_cols)
    # Set initial guess to solution with no zero
    vec_y[:-n_cols].reshape(n_rows, n_cols)[:] = \
        row_sum[:, np.newaxis] / n_cols
    vec_y[-n_cols:] = 0
    print("Intial Guess:")
    print_vec_y(vec_y, geometry, row_sum, indent=1)

    mat_A = make_mat_A(geometry)
    vec_b = make_vec_b(geometry, row_sum)
    iterate(geometry, mat_A, vec_b, vec_y, row_sum)

def problem_1_4_1():
    # For the 1-4-1 problem, use
    row_sum = np.array([1, 4, 1])
    geometry = np.array(
        [[1, 1, 0],
         [0, 1, 0],
         [0, 1, 1], ]
    )
    search(geometry, row_sum)

def problem_random():
    np.set_printoptions(precision=3)
    N = 100 * 2
    n_rows = N
    n_cols = N
    # row_sum is integers between 1 and 100 inclusive.
    row_sum = np.random.randint(1, 1000, size=n_rows)
    # geometry is a random array of zeros and ones.
    geometry = np.random.choice(2, size=(n_rows, n_cols))

    search(geometry, row_sum)

problem_1_4_1()
problem_random()

Random Implementation Ideas

No need to calculate pseudo inverse. Some solvers solves for a linear least square system. That is equivalent to solve by Moore-Penrose inverse, but possibly faster. https://eigen.tuxfamily.org/dox/group__LeastSquares.html
Use sparse solvers if there are many zeros.
Maybe rewrite the equations in block triangular form. For each overall iteration, perform one newton iteration on each block. That means no need for sparse matrix and two much smaller dense matrices. Don't know if that is possible though.
Use old solution as initial value for finding new solution.

Alternative and Questions

Use/Derive Simplex/criss-cross algorithm for the derivative of the lagrange multiplier equations. Don't know speed.

Or Use/Derive Simplex algorithm for quadratic programming.

https://www.me.utexas.edu/~jensen/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf

https://math.stackexchange.com/questions/246808/analog-of-simplex-method-for-quadratic-programming

What algorithm does the solver use?

How big is the matrix $X$?

How many zeros in matrix $X$?


How is the formula for calculation in row/column major obtained?

Row-major order stores the rows of the array one after another in memory. That is, the array

a d g j
b e h k
c f i l

is stored as

a d g j b e h k c f i l

To determine the address of an element in this list, we need to know how many elements come before it. For element $[I,J]$, this is the number of complete rows above row $I$ times the length of a row, which is $(I-L_r)\times n$, plus the number of elements before it in the current row, which is $J-L_c$.

Since the first element is at address $B$ and each element takes $W$ bytes, the addresses of the elements are $B$, $B+W$, $B+2W$, ... and, in general, if there are $k$ elements before you, your address is $B+kW$. For element $[I,J]$, we have calculated that $k=n(I-L_r)+(J-L_c)$.

For column-major, the argument is basically the same. If you understand the above, it should be easy to adapt it.


When can we assuredly say that a function is little o of some other function?

Your example doesn't work, since in fact $\log x = o(x)$. However, the function $\phi$ below is $O(x)$ but not $o(x)$ or $\Omega(x)$:
$$
\phi(x) = \begin{cases} x & \text{if $\lfloor x \rfloor$ is even}, \\ 1 & \text{if $\lfloor x \rfloor$ is odd}. \end{cases}
$$


How can an existential type be defined in terms of universal type?

As a general recipe, to figure out how to encode a type A, write down

∀Z . (A → Z) → Z

and massage it to something that does not involve A, using basic isomorphisms, such as currying and uncurrying. For example, if we plug in A := X + Y we get:

∀ Z . (X + Y → Z) → Z           ≅
∀ Z . (X → Z) × (Y → Z) → Z     ≅
∀ Z . (X → Z) → (Y → Z) → Z

You can also read the above lines as a sequence of logical equivalences. So this gives us the encoding of X + Y in terms of the universal quantifier.

I do not understand why in your question you speak about existential types, but since you do, it is worth explaining the encoding of ∃ X . B(X) in terms of ∀ this way:

∀ Z . ((∃ X . B(X)) → Z) → Z    ≅
∀ Z . (∀ X . (B(X) → Z)) → Z

Again, you can read the equivalence either as a type isomorphism or a logical equivalence in logic, using the fact that $(\exists x . \phi(x)) \Rightarrow \psi$ is equivalent to $\forall x . (\phi(x) \Rightarrow \psi))$.


Yes, this is correct.

The easiest way to get to the result is to look at a graph with $v$ vertices and $0$ edges. It obviously has $v$ components. Adding an edge between two vertices $a$ and $b$ reduces the number of components if $a$ was not reachable from $b$ before adding the new edge.

Concerning  "best" solution: Your approach yields an optimal solution, though it is only one way to do it - there are other ways (e.g. 26 components with either 2 or 3 vertices) that work equally well.


First a quick note, the flow entering a vertex is equal to the flow leaving. I'll just refer to it as the amount of flow through a vertex.

Second, note that we can say $a \leq b \wedge b \leq a$, thus we can add the constraint $a = b$ for two vertices.

Then we can re-use the NP-hard result from the paper that you quoted:

  "A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"

The reduction is done by putting two proxy vertices in the middle of the respective arcs, let's call them $a$ and $b$.

We then also add two vertices $a'$ and $b'$, directly connecting to the source, and add the constraints $a = a'$ and $b = b'$. Finally we add vertex $c$, and connect it to $a'$, $b'$  and the sink. Note that the flow through $c = a' + b' = a + b$.

We finish the reduction by adding constraints $c \leq a$ and $c \leq b$. Now $a+b \leq a$ and $a+b \leq b$ implies that either $a=0$ or $b=0$ (or both).


Characterisation of Turing completeness?

It seems very unlikely that there is any useful characterization other than the definition. Any such characterization would have to deal with all kinds of programming languages (imperative, functional, declarative and everything else) along with, assuming the claims from the Wikipedia article you link are correct, Minesweeper, Conway's game of Life and Magic the Gathering.

If you did have a characterization, it would probably be no easier to apply that characterization than to just apply the definition.


This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question about how we interpret the given conditions in the original problems.

(By the way, in general, it is the responsibility of the original problem/exercise to make it clear the exact meaning of each given condition. A notable exception is an interview question, where you are supposed to dig out various assumptions.)

Let us take the definitions given at Cache Performance by gshute at UMD as referenced in the question, which is consistent with the Wikipedia entry on average memory access time.

  Cache Access Time

  The fraction or percentage of accesses that result in a hit is called the hit rate.
  The fraction or percentage of accesses that result in a miss is called the miss rate.
  It follows that hit rate + miss rate = 1.0 (100%).
  The difference between lower level access time and cache access time is called the miss penalty.
  Effective access time is a standard effective average.

effective-access-time = hit-rate * cache-access-time
                      + miss-rate * lower-level-access-time

  Miss penalty is defined as the difference between lower level access time and cache access time. Then the above equation becomes

effective-access-time = cache-access-time + miss-rate * miss-penalty

Since "t1 means the time to access the L1 while t2 and t3 mean the (miss) penalty to access L2 and main memory, respectively", we should apply the second formula above, twice. That is,

Teff = t1 + (1-h1)[t2 + (1-h2)t3] = 32

For the sake of discussion, if we assume that t2 and t3 mean the time to access L2 and main memory including the time spent on checking and missing the faster caches, respectively, then we should apply the first formula above, twice. That is,

Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 = 24.

For the sake of discussion again, if we assume that t2 and t3 mean the time to access L2 and main memory directly assuming there is no caches at all, respectively, then we should claim there is not enough information to compute a reasonable answer. Or if we can assume it takes relatively ignorable time to find it is a miss in $L1$ and $L2$ (which may or may not true), then we might be able to apply the first formula above, twice.

You could say that there is nothing new in this answer besides what is given in the question. I would actually agree readily. All I have done is basically to clarify something you have known as well as showing how to select the right definition or formula to apply.

Now that the question have been answered, a deeper or "real" question arises. Are those two formulas correct/accurate/make sense?

The picture of memory access by CPU is much more complicated than what is embodied in those two formulas. The actual average access time are affected by other factors [1]. However, we could use those formulas to obtain a basic understanding of the situation.


How to find optimal token set for compression?

Are there existing algorithms for it? Are there any algorithms related to the problem?

Theoretical one: https://en.wikipedia.org/wiki/Sequitur_algorithm
Practical one: https://encode.ru/threads/1909-Tree-alpha-v0-1-download


Can given grammar be parsed using recursive descent?

You will be able to.
Consider what happens when you try parsing a string as an Expr: you will need to read a term. If your term is starts with an english alphabet character, then its an Ident and once you stop seeing letters a-z, then you have finished reading Term. If it does not start with an alphabet character, then you need to see a '(' and you will retry reading an expression from there (by induction this will work), and finally read a ')'.
So we can successfully read the first Term, and after that we just need to see a '(', another Term (and again by induction we can do that) and finally a ')'
This language has no ambiguity so its pretty easy to parse.


Context free grammar where number of a's is larger than number of b's in any prefix of the string

In short, take your grammar for  the language having a greater or equal number of $a$'s in every prefix, but rename the startsymbol to $P$, i.e.
$$
 P \to aP \mid aPbP \mid \varepsilon.
$$
Then simply note that your condition requires a word to start with an $a$, hence the following will do the job:
$$
 S \to aP.
$$
For if $S \to w$ then $w = auv$ with $|u|_a \le |u|_b$, where $|u|_a$ denotes the number of $a$'s in $u$ (and analog for $|u|_b$), hence for the prefixes of $w$ the assertion follows. And conversely it works the same.

For your given grammar, this is correct (but I leave my answer as it seems to be simpler). For a proof note that if the produced word contains at least one $b$, then it must have at least two $a$'s before it, and this is what your production $aSAbA$ takes care of, where from $A$ we can just derive words having at most as many $a$'s as $b$'s in every prefix.

Let me give another approach to think about this. Might be a little bit to much theory, but just for education and reasoning. Note that the famous Dyck language is defined as
$$
 D := \{ w \in \{a,b\}^{\ast} :  |u|_a \le |u|_b \mbox{for each prefix $u$ of $w$ and } |w|_a = |w|_b \}.
$$
It is quite simple to give a grammar for this language, for example
$$
 S \to \varepsilon \mid SS \mid aSb.
$$
Now if we denote by $\mbox{pref}(L)$ the set of prefixes of some language $L$ then your initial language of words having at most as many $a$'s as $b$'s in any prefix is $\mbox{pref}(D)$. And it is quite easy to derive a grammar from it, just make sure every production could be finished any time on the right (for a general argument see this post), hence we could give the grammar
$$
 S \to \varepsilon \mid SS \mid aSb \mid aS \mid a
$$
where the production $S \to aS$ could also be leaved out. Now simply note that words fulfilling your restriction have to start with an $a$ and proceed as above.


A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.

The conjecture $\mathsf{L} \neq \mathsf{NL}$ is considered (by some) to be more approachable than the conjecture $\mathsf{P} \neq \mathsf{NP}$. I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$.

The bigger picture here is whether Savitch's theorem, which states that $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$ for reasonable $t(n) \geq \log n$, is tight. While $\mathsf{NPSPACE} = \mathsf{PSPACE}$, I think that most people believe that $\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$. On the other hand, I'm not sure that people believe that $t(n)^2$ is the optimal blowup; perhaps a smaller exponent also works, at least in some cases. See for example a recent arXiv paper, The parameterized space complexity of model-checking bounded variable first-order logic, by Yijia Chen, Michael Elberfeld, and Moritz Müller.


Is deciding if there is a set that is intersected with some given sets and that has at most one common element with other given sets NP-complete?

You can reduce 3SAT to this problem by converting each variable $v_i$ to two elements $e_{i1}$ and $e_{i2}$ (one for its positive literal and one for its negative literal) and a set $B_i$ containing $e_{i1}$ and $e_{i2}$, and converting each clause $c_j=l_{j1}\vee l_{j2}\vee l_{j3}$ to a set $A_j$ containing elements representing $l_{j1},l_{j2},l_{j2}$.

Now it's not hard to prove this problem is NP-complete using the reduction above.


What is the complexity of finding a regular expression equivalent to a given DFA?

"Find an equivalent regular expression" is not a decision problem, so it can not be in any of these classes. See also our reference questions on complexity theory.

There are polynomial-time algorithms that solve your computational problem, though, so it is in some flavor of P.


Applications of the LU factorization in computer science

LU decomposition is a basic technique in numerical linear algebra, which is "numerical analysis for linear algebra", or (roughly speaking) the study of numerical algorithms for matrices. Numerical linear algebra has many applications, since many numerical algorithms reduce to linear algebra, which is at the heart of multivariate calculus. You can find a list of areas of application on the Wikipedia article.


Complete the following table by specifying the scope of each declaration

Your first answer is good (assuming the scope to assign is in order as declarations go).
Each declaration is in the scope, where it is declared. In inner scope (say B2) variable $b$ is declared shadowing previous declaration. Now you cannot use outer scope variable (read, write) as is by name without scope resolution operator.

Your second table suggests that variables are available in given scopes (say B1, B2, B4), and you have taken into account shadowing, so it still looks good, but technically it is accessible and not shadowed in that scope, not declared in that scope.


Origins of the Segment tree data structure

It seems to me that the Segment tree in the Wikipedia article is exactly the same as the segment tree you're used to hear about.

Segment trees as used in programming competitions can be generalized as working over any data type which forms a Semigroup (that is, any data type over which some binary associative operation can be defined on). As a reference, I've been implementing them in Haskell, the source code can be found here.

In this particular case, you'd have to notice that the power set of a set forms a commutative monoid with union, and monoids are, in particular, semigroups. Hence, the particular case described in Wikipedia is a segment tree where the data type is an Interval, and the associative operation is the union operation!.


Before proving a lower bound you have to formalize your computational model. This can be done in several ways for dynamic programming. The pioneer here is Allan Borodin, who came up with priority branching trees. Buresh-Oppenheim et al. extended this to the strong model of priority branching programs. Jukna considered incremental dynamic programming algorithms,tropical circuits and tropical switching networks. The last model is particularly simple, and Jukna proves some tight results for it, so you may be able to prove that your algorithm is optimal for that model.


Characterizing a CFG equivalent to a special type of PDA

In other words, you are constructing a linear grammar for a one-turn pushdown automaton.

So the standard construction from the link (which is Sipser style, afaik) gives productions $A_{ik}\to a A_{\ell j} b$ for each pop-push pair in the computation. That is ok, the productions are of the right form.

Now there are two problems. One is what to do with the zillions of $A_{ij}\to A_{ik}A_{kj}$ productions (which are obviously not allowed!) ? The answer is in the intuitive meaning of the symbols $A_{ij}$.

The second problem is hidden, and not clear in your question (and also not in the example you link). Is it allowed to replace to topmost stack symbol by another (this will not change the stack size) or are those considered two consecutive operations? (Here the Sipser model deviates from the standard one). Also: can we make a computational step. not changing the stack?


Is Dual Graph of a Triangulation of a Polygon Tree?

Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree.

However, is this thing I've drawn here really a polygon? That depends on which definition of "polygon" you use. A polygon is often defined as an area bounded by a single polygonal chain that does not intersect itself. This type of polygon is also known as a simple polygon. Sometimes, we want to talk about generalizations of this simple polygon. A polygon with holes is a connected area bounded by several polygonal chains that do not intersect themselves or with each-other.
So, for this answer, I will define a polygon to be either a simple polygon or a polygon with holes. This means that above, I've shown an example of a polygon with a triangulation of which the dual graph is not a tree. This particular polygon is actually an example of something that holds more generally: the dual of a triangulation of a polygon is a tree if and only if the polygon is simple. (Proof idea: since a polygon is connected, the dual graph of the triangulation is also connected. Observe that the boundary of the polygon is disconnected if and only if the dual graph of the triangulation contains a cycle. Since a tree is defined as a connected acyclic graph, the claim follows.)


Higher order empirical entropy is not the entropy of the empirical distribution?

No, as your counterexample shows, it is not true.  I don't understand why you previously thought it was true, either, so it's hard to say what might have gone wrong with your previous intuition.

We can say that

$$H(X) = H(X_1) + H(X_2 | X_1) + H(X_3 | X_1,X_2) + H(X_4 | X_1,X_2,X_3),$$

where $X_i$ denotes the $i$th character in $X$.  that much is true.

In the example you gave, $H(X_1) = 0$, $H(X_2|X_1) = 1$, $H(X_3|X_1,X_2) = 0.5$, $H(X_4 | X_1,X_2,X_3) = 0.75$ (see footnote * for explanation).  Thus $H(X) = 1 + 0.5 + 0.75 = 2.25$.

Do notice that $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ both depend on $i$.  This might be important.

Also, notice that $H(X_{i+1}|X_1,\dots,X_i)$ is unrelated to $H_1(x)$.

Perhaps you were expecting $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ to be the same for all $i$?  If that were true, there might be a relationship between $H_1(x)$ and $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ (or something similar to them)... but it's not.

Footnote *: How did I calculate those?  I used the formula

$$H(X_{i+1}|X_1,\dots,X_i) = \sum_v \Pr[(X_1,\dots,X_i) = v] \times H(X_{i+1}|(X_1,\dots,X_i) = v).$$

For $i=1,2$, we only need to consider two values of $v$; for $i=3$, we only need to consider three values of $v$.


Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

I know of no compendium that is completely satisfactory in any regard. It seems to be too much of a thankless task maintaining these things, thus I suspect that broad answer to your question is, unfortunately, no.

However, there are several resources which, together, are at least a good start for any search.

In this case, Wikipedia is a fairly decent resource (I guess the contribution model helps overcome some of the problems with a single-curator approach, but you lose the consistency).

If you're interested in Parameterized Complexity, Marco Cesati began a compendium of problems, but like Kann, has (understandably) not kept up with the updates. There's also an online compendium, but it is less comprehensive.

A similar question was also asked on cstheory, attracting a couple of answers, one that caught my eye was the Encyclopedia of Algorithms. I cannot personally vouch for it, but it at least looks useful, or at least useful enough to convince a university library to buy.


The resulting zero-one representation is the $|A|\times |A|$ matrix $M$ with $M_{ij} = 1$ if $(i,j) \in R$, and $M_{ij} = 0$ if $(i,j) \notin R$. In our case, the matrix is
$$ M = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}. $$
Take it as an exercise to prove the following properties:

$R$ is reflexive iff the diagonal of $M$ is all 1s.
$R$ is symmetric iff $M$ is symmetric.
$R$ is antisymmetric iff the off-diagonal entries of $M+M^T$ are 0/1 (but not 2).
$R$ is transitive iff the support of $M^2$ is a subset of the support of $M$, where the support is the set of non-zero entries.


Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output

One simple approach is repeated halving.
Remove a single 1 from the input (if you fail, output N).
Then go over the tape in passes. Each pass deletes every other 1 encountered (starting with the first). The number of passes required to delete all 1s is $\lceil \log_2 n \rceil$. You can count the number of passes as you go.
For example, suppose that $n=6$:
111111       Delete the first 1
b11111       Delete every other 1
2b1b1b       Delete every other 1
22bb1b       Delete every other 1
222bbb       Convert back to 1
111bbb       Done

The number of passes is $3 = \lceil \log_2 n \rceil$.


Draw a graph of DFA for a regular language

$T$ is a 'trap state' $q_3$ is final accepting state. From state $T$ all inputs $a$, $b$, $1$ will direct to $T$ itself. There's a self loop over state $q_4$ for inputs $1$ and $b$.


Why is big omega of peak finding Omega(lg n)?

I think you got a bit confused with the definition of Big-Omega ($\Omega$).
The $\Omega(f(n))$ is a lower bound for an algorithm. It means that your algorithm's running time can not be less than $kf(n)$ where $k$ is a constant. And it applies to worst case not the best case.

edit
If you calculate your algorithm running time as $c\log{n}$, it's asymptotic analysis says that it is $\Omega(\log{n})$.

big omega notation


As mentioned in the comments, it depends on whether you care about partial correctness or total correctness.

Partial correctness requires that, if the program starts from any state satisfying the preconditions, and if the program terminates in a final state, then such final state satisfies the postcondition.

Total correctness requires that, if the program starts from any state satisfying the preconditions, then the program terminates in a final state, which satisfies the postcondition.

Only total correctness requires termination, partial correctness does not.

The Hoare logic rules for program statements are roughly the same, except for while loops. In partial correctness, the while rule requires to find a suitable invariant property. In total correctness, the rule requires both the invariant property and the variant: this is a strictly decreasing, natural valued function of the state (roughly, providing an upper bound on the number of loops).

If your rules have no variant, but only deal with the invariant, they are meant to be used to prove partial correctness, only.


If P = NP, would dynamic programming be obsolete?

Absolutely not. P = NP doesn't imply that problems that can be solved with dynamic programming can be solved easier or quicker with another algorithm.


If $V$, $E$ and $F$ is respectively the number of vertices, edges and faces in a maximally triangulated graph, then why do we have $3F = 2E$?

Every face is a triangle (hence, the name, "maximally triangulated graph"). Every face is thus composed of three edges (or sides). So, if we have $F$ faces, then we may be tempted to say that there are $3F$ edges. This is not the case because an edge contributes to exactly $2$ faces. So, in $3F$ we are counting every edge twice. So, $\frac{3F}{2} = E \iff 3F = 2E$.


Is a Karp–Levin reduction a Levin reduction?

A Karp reduction from a language $A$ to a language $B$ is a function $f$ such that $x \in A$ iff $f(x) \in B$. This is the common meaning of the term.

David Richerby mentions in a comment below that Levin reductions are a more elaborate type of reductions: see this question.

In the present instance, Karp–Levin reduction seems to mean the same as Levin reduction. Indeed, since the common term for the usual notion of many-one reduction is Karp reduction, adding Levin's name might signify something different. The way the term is used in the paper should make it clear which meaning is being used. The paper might also include a definition of this somewhat non-standard term, and I suggest you include such a definition in future papers you may write.


Searching for a string of numbers in a large digit sequence

Use your web browser. You can get the first 2 million or so digits in this link, and then use your browser's searching facilities. I was able to locate 351814 within the first 2 million digits (though not within the first 1 million digits, available in a separate link). By the way, I found both links on Wikipedia.


Can I say is lossy compression to discard data having a way to recover it?

However, in punctual cases, it will infer similar data that works just as well as the original.

From this I would conclude it is lossy because it is similar data, rather than lossless, which would be a perfect reconstruction.

That being said, I'm not entirely what you mean by "data that works just as well", but if the data works exactly how the original data would work, for your use case it might be considered lossless because the information you need and compress is not lost. You must be careful to specify that the compression of the information you wish to recover is lossless, but the compression of the data as a whole is lossy.

As example, if my goal is to save (using compression) simple arithmetic equations to later determine if they are odd or even. I might compress $f = 4 + 3 + 8 +1$ into the number of even ($e$) and odd ($o$) terms it has: $ C(f) = 2e2o$. This is clearly lossy, I can't perfectly reconstruct which terms created $f$, but for my purposes I can clearly determine whether it is odd or even after compression. Even further I could reconstruct similar data (as you stated) that works just as well as the original, for my purposes.


Is $A\odot B\odot C = A\oplus B\oplus C$?

Yes, $x\odot y\odot x = x\oplus y\oplus z$, where $\oplus$ is the XOR operator and $\odot$ is the XNOR operator.

In fact, it is easy to see that both sides of the equation are always equal. Note that $a\odot b$ tests whether $a$ is the same as $b$ while $a\oplus b$ tests whether $a$ is different from $b$. So we know $a\odot b= \overline{a\oplus b} = \overline a\oplus b$. So, $x\odot y\odot z = (x\odot y)\odot z =\overline{x\oplus y}\odot z = \overline{\overline{x\oplus y}}\oplus z = x\oplus y\oplus z$. (We do not even use the associativity of $\odot$ nor that of $\oplus$.)

Let $n\geq 1$. We can show the following easily by induction on $n$.
$$x_1\oplus x_2\oplus\cdots\oplus x_n = (\text{ number of true's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is odd }) $$
$$x_1\odot x_2\odot\cdots\odot x_n\, = (\text{ number of false's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is even }) $$

So in general, we have the following, which can be shown directly by induction on $n$ as well.
$$\begin{align}
\text{for odd } n,\ \
&x_1\oplus x_2\oplus\cdots\oplus x_n = x_1\odot x_2\odot\cdots\odot x_n\\ \text{for even } n,\ \
&x_1\oplus x_2\oplus\cdots\oplus x_n = \overline{x_1\odot x_2\odot\cdots\odot x_n} \end{align}$$

Now let us come to the real question. Why does wolfram alpha give a completely different output for $x\odot y\odot z$ at http://www.wolframalpha.com/input/?i=x+xnor+y+xnor+z?

As Peter Taylor has noticed on that web page, Wolfram parses "x xnor y xnor z" very differently from what we might have expected, "(x xnor y) xnor z". Wolfram parses it as "Not(x Xor y Xor z)" in text notation or, what is the same, "¬($x \underline\vee y\underline\vee z)$" in symbolic notation. This is not mentioned in its documentation for Xnor operator at http://mathworld.wolfram.com/XNOR.html nor at http://www.wolframalpha.com/input/?i=xnor. One might suspect this is an implementation bug of Wolfram.

However, it turns out this is a feature by design (or possibly an unintentional side-effect) of Wolfram. Its documentation for Operator Input Forms shows the following lines, where the small wedges at the end of each line means "built-in meaning exist".  So after all Wolfram has decided to treat "x xnor y xnor z" as "not(xor(x,y,z))" instead of the more common "(x xnor y) xnor z" as a surprise to unsuspecting users such as OP and me! (Of course, "more common" is only in the eyes of some people. It is quite possible Wolfram's interpretation is more common in other situations.)

One might wonder why Wolfram has made such a strange and uncommon choice. Here is my speculation, my pure shallow speculation.

Wolfram defines Xor for multiple argument as "true if an odd number of its arguments are true and false otherwise", probably along the approach of a BooleanCountingFunction. It also parses and evaluates expressions such as "x1 xor x2 xor x3 xor x4 xor x5" (which everyone agree must be "((((x1 xor x2) xor x3) xor x4) xor x5)") as "Xor(x1, x2, x3, x4, x5)", which is easier to define and faster to compute especially when the number of arguments becomes larger. All is going well without inconsistency for Xnor. Xnor looks very similar to Xor. So, (again just my speculation), Wolfram chooses to define Xnor in a similar way to Xor ( and in fact, in a similar way to Or, And, too). Since BooleanCountingFunction only deals with the number of true values, it choose to to define and compute both Xnor(x1,x2,...,xn) and "x1 xnor x2 xnor ... xnor xn" as whether the number of the true values are even, which is also the negation of Xor and which is, at least indeed, the same as x1$\odot$x2 in the case when $n=2$. However, the resulting value of, for example, "x1 xnor x2 xnor x3" as computed by the negation of Xor(x1,x2,x3) is exactly the opposite of the value of "(x1 xnor x2) xnor x3"! In fact, Wolfram's value of "x1 xnor ... xnor xn" and our value of x1$\odot\cdots\odot$xn are the same when n is even and different when n is odd, for any truthy value of x1, ... and xn.

Moreover, there exists a somewhat similar problem for the NAND operator, but to a much less extent since NAND is not associative. Wolfram treats "x nand y nand z" as "x nand (y nand z)" instead of "(x nand y) nand z" (probably for another good reason). You can check the outputs by Wolfram, http://www.wolframalpha.com/input/?i=x+nand+y+nand+z, http://www.wolframalpha.com/input/?i=(x+nand+y)+nand+z and
http://www.wolframalpha.com/input/?i=x+nand+(y+nand+z)

In conclusion, be careful when you use Wolfram to compute logic formula involving XNOR and NAND, especially if you have more than one such operator or more than three arguments. You will want to double check.


Efficient Algorithms for Complex Networks

There are currently serious efforts devoted to algorithms taking into account usual properties of complex networks, either in their design (use these properties to be efficient) or in their analysis (show that, if the input graph has these properties, then the algorithm has low complexity).
Since most complex networks met in practice are sparse, let me first say that any complexity expressed in terms of the number of edges (instead of the squared number of vertices) is of interest in this context. But I do understand that you actually have more advanced complex network properties and complexity analysis in mind.
My 2006 paper about triangle counting and listing provides a good illustration, I think. There, I used the fact that most complex networks met in practice have very heterogeneous degrees. I proposed a very simple algorithm makes a distinction between low- and high-degree vertices, and proved its algorithmic complexity as a function of the graph degree distribution.
Many such examples exist in the literature. For instance, the arboricity and core value have been used to enumerate $k$-cliques. However I am not aware on any survey devoted to them.


Knuth's proof of O(1) for linear probing

Let $p_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p_i = p_j$ for all $i,j$, and so $Mp_0 = p_0 + \cdots + p_{M-1}$. Now let $X_i$ be the indicator for the event "$i$ is empty". Then $$p_0 + \cdots + p_{M-1} = \mathbb{E}[X_0] + \cdots + \mathbb{E}[X_{M-1}] = \mathbb{E}[X_0 + \cdots + X_{M-1}], $$
using linearity of expectation. But $X_0 + \cdots + X_{M-1} = M-N$, since exactly $N$ positions are full and $M-N$ are empty. Altogether, we get
$$
p_0 = \frac{p_0 + \cdots + p_{M-1}}{M} = \frac{M-N}{M} = 1 - \frac{N}{M}.
$$

Now for the coupling argument. Let $A = a_0,\ldots,a_{N-1} \in \{0,\ldots,M-1\}^N$ be a uniformly random insertion sequence, and let $B = b_0,\ldots,b_{N-1}$, where $b_t = a_t + j-i \pmod{M}$. Denote the final resulting hashtables by $H_A,H_B$. You can prove by induction that $H_A(p) = H_B(p+j-i\bmod{m})$ for every $p \in \{0,\ldots,m-1\}$ (the induction is on the number of insertions), and so $H_B(j) = H_A(i)$. In particular, cell $i$ is empty in $H_A$ iff cell $j$ is empty in $H_B$. Now $H_A$ and $H_B$, when considered individually, are generated by a uniformly random insertion sequence, and so the probability that $H_A(i)$ is empty is $p_i$, and the probability that $H_B(j)$ is empty is $p_j$. This shows that $p_i = p_j$.


Deleting nodes from graph so that they can be separated by a straight line

Try the following (inefficient) approach. Assume there are $N$ points in total. Now with each of the $N$ points try to find a line segment that passes through it with the least number of mis-classifications (number of points that were not correctly separated) by the line segment. The important point to note here is that, you would not have more than $N-1$ such line segments to check for. At the end of the procedure simply choose the point and its best corresponding line segment. The overall complexity is $O(N^3)$ under ideal conditions. Some perturbation of point may be required in the process, if not ideal.

A slightly more efficient procedure is as follows, let the convex hull of the points in type 1 be $P_1$ and those of type 2 be $P_2$. Then I suspect, in the previous procedure, instead of computing the best line segment for every point, just do the procedure for those in $P_1 \cap P_2$.


Evolutionary algorithm for the Physical Travelling Salesman Problem

Have a look at this survey on crossover operators for TSP

It gives you the history of development on this area as well.

List of operators covered:

Partially Mapped Crossover (PMX) [Goldberg, 1985]
Order Crossover (OX) [Davis, 1985]
Edge Crossover (EX) [Whitley, 1989]
Subtour Exchange Crossover (SXX) [Yamamura, 1992]
Edge Exchange Crossover (EXX) [Maekawa, 1996]
Edge Assembly Crossover (EAX) [Nagata, 1997]
Partition Crossover (PX) [Whitley, 2009]


Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular

If $L_6$ were regular, then so would the following language be:
$$ (L_6 \cap a^* b^*) \cup \{ \epsilon, ab, a^2b^2, a^3b^3, a^4b^4, a^5b^5 \}. $$
However, this language is none other than $L_5$.

You can also use the pumping lemma. Try to pump the word $c^qa^qb^{2q}$ for large enough $q$.


I am slightly confused. If $k$ is a constant, then you can try all $O(n^k)$ possible tours. Hence the problem is in ${\sf P}$.

However, if $k$ is part of the input, the decision problem is ${\sf NP}$-complete. This can be shown by reducing $\text{HAM-CIRCUIT}$ to the problem, by the following reduction.

Assume that we want to determine if a $n$-vertex graph $G$ has a Hamiltonian circuit. Then we take the complete graph $K_n$ with the following distance function
$$
w_{ij}:=\begin{cases}
1 & \text{if $(v_i,v_j)$ is an edge in $G$} \\
2 & \text{otherwise}
\end{cases}.
$$
Furthermore we pick $k=n$ and $m=n-1$.

Let me tell you why this is a reduction. If $G$ has a Hamiltonian circuit, then there is a tour in $K_n$ with length $n$. In other words a circular route of length $\le n$ that serves $> (n-1)$ nodes. On the other hand, if there is a Santa-tour that visits $>(n-1)$ nodes is has to visit all nodes. Since the Santa-tour can only have length $\le n$ and every edge length is at least 1, all $n$ edges in this tour have length 1. Hence this tour corresponds to a Hamiltonian circuit in $G$.


Merging and Unmerging Sets of Trees Efficiently

One solution

Make trees immutable, using path copying.  Give each tree a name.  Whenever you create a new tree T3 by merging two trees T1,T2, remember in T3 that it was created by merger of T1,T2 (i.e., include pointers to T1,T2 as part of the auxiliary information in the root node of T3).  Also keep track in the auxiliary information for each tree all of the original trees it was transitively created from.

Now, when you want to unmerge a tree, you can look at the auxiliary information to work out what you need to do.  When you call unmerge(T, U), look at the auxiliary information for T to find the two trees T1,T2 it was merged from; if U was used to create T1, then

unmerge(T, U) = merge(unmerge(T1, U), T2)

so you can proceed recursively.  Similarly, if U was used to create T2, then

unmerge(T, U) = merge(T1, unmerge(T2, U))

The running time of this will be proportional to the maximum "depth" of the merge operations, times the time to merge two trees.

A more efficient solution

With more sophisticated data structures, you can speed up the unmerge operation so it performs at most $O(\log n)$ merges.

Call a tree "atomic" if it wasn't created by a merge/unmerge.  The auxiliary information for each tree T will be an ordered list of the atomic trees T1,..,Tk it was created from, so that T = merge(T1,..,Tk).  This list will be stored as a persistent self-balancing binary tree with k leaves, one per atomic tree in the list, ordered in the same way they are in the list.  Each node in that self-balancing tree corresponds to an interval Ti,..,Tj of the list (namely, Ti,..,Tj are the set of leaves under that node); add metadata so that node points to the tree produced by merge(Ti,..,Tj).  Also, as auxiliary information for tree T, we'll have a map that given the name of a tree U lets you look up where in the list T1,..,Tk that U appears; this can be done with a second persistent self-balancing binary tree with k leaves, ordered by lexicographic order on the names of the atomic trees.

The merge(T1, T2) operation merges the two trees, and constructs its auxiliary information by concatenating the associated lists.  Those operations on the self-balancing binary trees can be done in $O(\log n)$ time, so this adds little overhead to the merge operation.

Finally, unmerge(T, U) can be implement as follows.  First, we look up where U appears in the associated list for T; suppose U is the ith item in the list T1,..,Tk, i.e., U = Ti.  Then we need to compute merge(T1,..,Ti-1,Ti+1,..,Tk).  It turns out that this can be done in $O(\log n)$ merges.  Why?  Well, we look at the path from Ti to the root in the self-balancing tree for T; if we take all of the siblings of the nodes on that path, and merge their associated trees in the correct order, we get merge(T1,..,Ti-1,Ti+1,..,Tk).  Since it is a self-balancing tree, its depth is at most $O(\log n)$, so there are at most $O(\log n)$ nodes along that path, so we need to do at most $O(\log n)$ merge operations.  Thus, unmerge(T, U) is about $O(\log n)$ times as slow as a merge operation.

A final note: there's nothing special here about the fact that the T1,..,Tk are trees.  They could have been any value, such as simple integers or anything else.  So, you might find it easier to think about this with simple values first.  On the other hand, this also means that my algorithm isn't taking into account the fact that the T1,..,Tk are trees; it's possible that data structures that take that into account might be able to be even more efficient.


How to answer the following queries on a tree?

Without any precomputation, a depth-limited version of depth-first search would be a natural approach to this problem: then it's like finding the minimum of an array, you could find the minimum weight during the search. But a time-efficient way (if you have multiple queries for different nodes and $K$) is to indeed precompute the answer for all the nodes: a linear algorithm seems achievable, starting from the bottom level up to the root, level by level. You have to store for each node an array $a$ such as $a(K)$ gives the desired value. And if you modify the value of a node later, I think a backpropagation scheme could be also considered.


Perhaps the problem here is looking a for a highly specific definition of a very general concept. I don't see the problem of viewing virtually everything as a computation. Although we don't think about it, everything we do is expressible in terms of the Physics of the component parts, down to at least quarks buzzing about. We have the same situation with computation. There's inputs, outputs and a process (all of which could be trivial). Whether they're interesting or useful as computations or models of computation is a very different question.

The strongest working definition we have comes via the (strong) Church-Turing Thesis, which states that every possible physically realizable model of computation is no more powerful than a Turing Machine. If you believe that this is true, then although we may have lots of way to express things, ultimately we can reduce every computation to a Turing Machine, hence giving a definition of computation as "anything we can reduce to a Turing Machine".

In this model, the exploding bomb is a computation. It's not a widely applicable one (we hope ;) ), but we can model in some fashion with a Turing Machine (though there is an argument here about the nature of the output and the equivalence with the TM's output). It's also not a good model of computation in general, in that it seems unlikely that the exploding bomb model is Turing complete.


Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula:
$$
(x-c) \sum_{i=0}^d b_i x^i = (-cb_0) x^0 + \sum_{i=1}^d (b_{i-1}-cb_i)x^i + b_dx^d.
$$
If you compute $(x-a_1)\cdots(x-a_n)$ by successively multiplying the terms, i.e. by computing $P_1 = x-a_1$ and $P_{d+1} = P_d(x-a_{d+1})$ for $1 \leq d \leq n-1$, then you need this many multiplications:
$$
1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = \Theta(n^2).
$$


Number of vertices of a graph in vertex cover of size $m$

Consider the graph $G=(V, E)$, where each vertex in $G$ has at most $k$ neighbours. Let $C\subseteq V$ be a vertex cover of size at most $m$. For a vertex $v\in C$, let $c(v) = \{v\} \cup \{ u\in V: \{u, v \}\in E\}$, that is, $c(v)$ is the set of vertices that are covered by the vertex $v$ (including $v$ itself).
A side note: the subgraph induced by the vertices in $c(v)$, for any $v$, is a "star" graph (similar to the one you attached, yet the number of vertices that are neighbours of $v$ in this subgraph can be strictly less than $k$). The idea is to consider star graphs corresponding to the vertices in $C$, and then use the union bound for sets.
Now $C$ being a vertex cover implies that $\bigcup\limits_{v\in C} c(v) = V$. This is easy, yet we prove it for completentss:  the $\subseteq$-containment is trivial. The other direction follows as for every vertex $v\in V$, one of the following holds:

$v\in C$: in this case, as $v\in c(v)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.
there is $u\in C$ such that $\{u, v\}\in E$: in this case, as $v\in c(u)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.

Finally, the following holds $$ |V| = |\bigcup\limits_{v\in C} c(v)| \leq \sum\limits_{v\in C} |c(v)| \leq |C|\cdot max_{v\in C} (|c(v)|) \\\leq |C|\cdot max_{v\in C}(degree(v) + 1) \leq |C|\cdot (k + 1) \leq m\cdot(k+1)$$


Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1

(This is an attempt to an answer, I hope the details are right.)
Your language consists of all strings in $(aa+bb)^*$ with an even number of $bb$.
We are allowed to use complementation, so we start by looking at the complement of the language. I think we can split the complement into two (overlapping) parts

strings not of the form $(aa+bb)^*$, that language has starheight one.
strings of the form $w_0\cdot bb\cdot w_1\cdot bb\cdot w_2 \dots bb\cdot w_n$, where (1) the number of $bb$ is odd, and (2) the $w_i$ do not contain any $bb$ (but I will have to be more precise on that)

Now we will try to find an expression for the language $W$ of the $w_i$ without using star. That means we can use the star to count the odd number of $bb$, as in $(W\cdot bb\cdot W\cdot bb)^*\cdot W\cdot bb\cdot W$.
This is the tricky part. Strings from $W$ are either

the empty string $\varepsilon$
just one single $a$
of the form $axa$, where $a$ does not contain $bb$. Not "containing $bb$" is the complement of $(a+b)^*bb(a+b)^*$, and as you know $(a+b)^*$ is again star-free.

The strings we now have specified can have longer stretches of $b$'s, but whenever that happens the $b$'s come in pairs.


For every two decidable languages There is a turing machine that decides if they are equal

Many problems that are decidable for regular languages become undecidable for context-free languages.

Even the intuitively simple problem $L = \Sigma^*$ is undecidable for context-free $L$, where $\Sigma$ is the alphabet of the language. That of course means that equality for context-free language $L=K$ is undecidable too.


Naming facts exported from blocks in Isabelle/HOL

From section 1.1.2 in the document isar-ref: you can reference facts via explicit name, implicit name and literal position. In this case, the explicit name has not been provided. I believe that the canonical method to provide an explicit name is to reference the fact of interest by its implicit name immediately after the end of the block. For example,

lemma mylemma: "i = i"
proof -
  {
    fix j :: nat
    have "j = j" by auto
  }
  note name = this
  show ?thesis using name by auto
qed

As a side remark, I would like to mention that general questions about Isabelle or the syntax of Isar are best posed on Stack Overflow. I believe that this would drastically increase the chances of your questions being answered promptly.