An SVM with a linear kernel has the same expressive power as a single perceptron in a neural net, since both are linear classifiers. If you think of the kernel function as mapping your input to a higher dimensional feature space then the SVM is still a linear decision boundary in that high dimensional kernel space. You could theoretically use the high dimensional kernel space features as input to a neural network as well as long as the kernel space is finite. Again the linear SVM behaves similarly to a single perceptron.

However, this only applies to linear SVMs.  In practice SVMs are typically used with a non-linear kernel, and then no such equivalence applies.  So this claimed equivalence might be a bit misleading, if you are comparing how SVMs tend to be used in practice to how neural nets tend to be used in practice.

Summary: Think of an linear SVM as being similar to a single perceptron instead of a neural network.


Why doesn't this quine-less language contradict Kleene's recursion theorem?

The recursion theorem only applies to admissible programming languages. A programming language $P$ is admissible if it satisfies the following three properties, with respect to some reference programming language $U$:

The problem of simulating a $P$-program on an input $x$ is r.e.
There is a computable transformation $f$ which, given a $P$-program, outputs an equivalent $U$-program.
There is a computable transformation $g$ which, given a $U$-program, outputs an equivalent $P$-program.

In your case the first two properties hold, so the third must fail. You can try to implement $g$ by "compiling" a $U$-program to a $P$-program, but this compilation would fail if the resulting program attempts to print its own source code. The recursion theorem shows that there is no way around this problem.


How should I choose the neighborhood structure for simulated annealing for my problem?

Simulated annealing can cope with neighborhood structures where you have to walk quite a bit to reach a distant point. Of course, the minimum distance between two points in the state space should at most be polynomial in the problem size, but any reasonable optimization heuristics will also require this restriction. The 5000 moves are completely reasonable for simulated annealing, especially since this is linear in $m$.

Don't implement any moves which would be very expensive to evaluate. The strength of simulated annealing is that it can work with moves which are cheap to evaluate, and hence evaluate a large number of candidate solutions. But if your state space is large, then you should also let simulated annealing evaluate a large number of candidate solutions. So your cool down schedule becomes important in this case. I could go into more detail here, but the question was about the neighborhood structure only, and the answer to this question is that your neighborhood structure is basically OK, and you should not use a neighborhood structure which would lead to expensive recomputations.


The circuit $C_n$ has $n+m$ inputs, $x_1,\ldots,x_n,r_1,\ldots,r_m$. Its size is polynomial in $n$, so without loss of generality, $m$ is polynomial in $n$. What we want is:

If $f_n(x) = 0$ then $\Pr_r[C_n(x,r) = 0] = 1$.
If $f_n(x) = 1$ then $\Pr_r[C_n(x,r) = 1] \ge 1/2$.

Here $x$ is shortcut for $x_1,\ldots,x_n$, and $r$ is shortcut for $r_1,\ldots,r_m$.


Building a tree with the heap property from an array and preserving its order

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675
As pointed out above by Raphael, there is a close relationship to treaps.
You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree


Why the name Recursively Enumerable and Recursive?

A recursive set is synonymous with computable set.  In the beginning of computer science, the notion of computer had not been completely fleshed out, and there were various ideas on the matter.  These ran from Turing's machines, Church's Lambda calculus, and Kleene-Gödels recursive function theory.  The idea is a set is computable if its elements can be decided by a (terminating) algorithm.

Recursively enumerable sets are more general.  It turns out that not every subset of the natural numbers is decidable by an algorithm.  However, for some sets, we can give a procedure (possibly non-terminating) that will enumerate the elements of the set (enumerate is used because each number appears exactly once thus a bijection from the natural numbers to the set in question is defined).  This is equivalent to saying that the set is semi-decidable in more modern terms.


Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$.  It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$.   Then, you add a constraint that the first bit of $Q$ is equal to $C1$ (that's a binary constraint), a constraint that the second bit of $Q$ is equal to $C2$ (another binary constraint), and so on.


Why aren't we researching more towards compile time guarantees?

I am not in a position to tell how much more research should be done on the topic, but I can tell you that there is research being done, for example the Verisoft XT program funded by the german government.

The concepts which I think you are looking for are called formal verification and contract based programming, where the latter is a programmer-friendly way of doing the first. In contract-based programming you first write your code as normal and then insert so called contracts into the code. A readily usable language which is based on this paradigm is Spec# by Microsoft Research, and the functionally similar but slightly less pretty Code Contracts extension for C# which you can both try out online (they also have similar tools for other languages, check out rise4fun). The "int with range type" you mentioned would by reflected by two contracts in a function:

Contract.Requires(-3 <= a && a <= 24);
Contract.Requires( 3 <= b && b <= 10);

If you want to call that function, you then have to use parameters which are ensured to meet these criteria, or you get a compile time error. The above are very simple contracts, you can insert almost any assumption or requirement about variables or exeptions and their relation which you might think of and the compiler will check if every requirement is covered by either an assumption or something that can be ensured, i.e. derived from the assumptions. That is why where the name stems from: The callee makes requirements, the caller ensures that these are met - like in a business contract.

Under the hood, code contracts are usually combined with knowledge about the inner workings (operational semantics) of the programming language into a list of verification conditions. This list represents basically one big logical proposition $P(x_1,x_2,...,x_n)$ with $n$ free variables - the inputs of your program. If the proposition $P$ is true for all possible variable assignments, then the program is considered correct. To check whether or not this is the case, an SMT Prover is used. From the CS side, those two are the critical parts of the process - the generation of verification conditions is tricky and SMT is an either NP-complete or undecidable problem, depending on the considered theories. There is even a competition for SMT solvers, so there certainly goes some research into this. Additionally, there are alternative approaches to using SMT for formal verification like state space enumeration, symbolic model checking, bounded model checking and many more which are also being researched, albeit SMT is, afaik, currently the most "modern" approach.

Regarding the limits of the general idea:

As previously stated, proving the correctness of the program is a computationally hard problem, so it might be possible that the compile time check of a program with contracts (or another form of specification) takes really long or might be even impossible. Applying heuristics which work well most of the time is the best one can do about it.
The more you specify about your program, the higher gets the probability of having bugs in the specification itself. This can lead to false positives (the compile time check fails even though everything is bug-free) or the false impression of being safe, even though your program still has bugs.
Writing contracts or specifications is really tedious work and most programmers are too lazy to do it. Try writing a C# program with code contracts everywhere, after a while you will think "come on, is this really necessary?". That is why formal verification is typically just used for hardware design and safety critical systems, like software controlling airplanes or automotives.

One last thing worth mentioning which does not quite fit the above explanation is a field called "Implicit Complexity Theory", for example this paper. It aims at characterizing programing languages in which each program you can write falls into a specific complexity class, for example P. In such a language, each program you write is automatically "ensured" to be of polynomial runtime, which can be "checked" at compile time by simply compiling the program. I do not know of any practically usable results of this research, however, but I am also far from being an expert.


Choosing Fitness function for float output in Genetic algorithm

The standard solution is: Use a softmax layer at the output of your neural network, and use the cross-entropy loss as your fitness function.


How to Add IEEE 754 Floating Point Numbers

It is difficult, and there are lots of special cases to handle.

Step 1: Determine if any of the operands is an Infinity or a Not-A-Number. In this case, look up the IEEE 754 standard and determine the result accordingly.

Step 2: Extract the sign, the biased exponent, and the mantissa. Add any implicit leading bit to the mantissa. Check whatever special rules there are: In the IEEE 754 32 and 64 bit format, a biased exponent of 0 means that there is no implicit leading bit in the mantissa, but the exponent should be treated as if it was 1. Add three extra bits containing zeroes to the mantissa.

Step 3: Make sure the exponents are the same. If one number has an exponent that is smaller by k, then shift that numbers mantissa to the right by k bit positions. If k is greater than 3, then set the last bit of the mantissa to 1 if any non-zero bits were shifted out. If k is so large that all mantissa bits would be shifted out then set the mantissa to zero, and don't try to shift by some huge amount.

Step 4: If the operands have different signs and the second mantissa is larger then exchange the operands. Add or subtract the mantissas, depending on the sign bits.

Step 5: If you added the mantissas and there was a carry, then increase the exponent, and shift the mantissa one bit position to the right. If the bit that is shifted out is non-zero, then set the last bit of the mantissa.

Step 6: If you subtracted the mantissas then count the number of leading zero bits in the mantissa. If all mantissa bits are zero then set the biased exponent to 1. Otherwise, shift the mantissa to the left and decrease the exponent, making sure that the biased exponent doesn't get smaller than 1.

Step 7: Perform rounding according to IEEE 754 rules. That's where the three extra mantissa bits are used. Remove the extra 3 mantissa bits. Due to the "round to even" rule, you round up (increase the mantissa by 1) if the last bit is 0 and the bits removed are 101 or larger, or the last bit is 1 and the bits removed are 100 or larger.

Step 8: If you rounded up and there is a carry then shift the mantissa one bit to the right and increase the exponent. If the biased exponent is too large then the result is infinity. If the biased exponent is 1 and the highest mantissa bit is zero then the biased exponent is changed to 0.

Step 9: Drop the highest bit of the mantissa, and pack sign, biased exponent, and mantissa together.


Kleene algebra - powerset class vs class of all regular subsets

The difference between the two is that $2^{\Sigma^*}$ contains all languages over $\Sigma$, whereas the class of all regular subsets of $\Sigma^*$ contains only the regular languages over $\Sigma^*$. So if $L$ is a non-regular language over $\Sigma$ then $L \in 2^{\Sigma^*}$ while $L$ doesn't belong to the set of all regular languages over $\Sigma$. For any $\sigma \in \Sigma$, you can take $L = \{ \sigma^{n^2} : n \geq 0 \}$, for example.


Compute how much memory is needed for a two level page table

This is a textbook exercise, maybe answering that exerise is part of your homework, so read your lessons, think about a possible answser, take a sheet of paper and draw rectangles and arrows representing memory, page tables, pointers...

First, an historical note, this arrangement 10 | 10 | 12 is the one used in 32bits x86 CPUs, which were fairly popular!

   4GB memory is divided into 1Million 4kB pages ( binary million = 2^20). Each "Page Table Entry" occupies 4 bytes. Total = 4MB. These entries are arranged in 1024 tables of 1024 entries. The indexes for the 1024 tables, "Page Directory Entries" each take 4 bytes (on x86, this is usually the same size as PTEs), so 4KB. Total size is therefore 4MB+4kB = 4100kB

A few remarks :

This size is only needed for mapping the whole 4GB address space. If there is less memory installed, the page tables can be smaller with "invalid" or "unmapped" entries in the first level page table.
A multitasking OS need to manage different memory maps for the different running applications, so there can be several copies of the page tables.


How to decide if a propositional formula is a well formed?

Perhaps this might help.

Well-formed: $(P \lor Q)$.

Not well-formed: $(P \lor Q$.

More generally, in class you must have been shown a definition of well-formed formulae. Use it.

Well-formed formulae are usually defined inductively. One possible definition is:

For every variable $v$, $v$ is a well-formed formula.
For every well-formed formula $\varphi$, $(\lnot \varphi)$ is well-formed.
For every binary symbol $\circ \in \{ \land, \lor, \rightarrow, \leftrightarrow \}$ and two well-formed formulae $\varphi,\psi$, $(\varphi \circ \psi)$ is well-formed.
"No other formula is well-formed."

The last "axiom" isn't quite formal. What we really mean is that a formula is well-formed only if it can be proved well-formed by using the first three axioms. (This is equivalent to the definition using least fixed points, which you might have seen in class.)

What all this means is that in order to show that a formula is well-formed, all you need to do is derive it from the axioms. Showing that a formula isn't well-formed could be more difficult. Since the set of well-formed formulae is context-free, there is an efficient algorithm which given a formula decides whether it is well-formed.


Merging Sorted lists using Heap Data Structure

Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m_1,m_2$ costs $O(m_1+m_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.

We can also get a matching lower bound. The number of possible answers is
$$
\begin{align*}
\frac{n!}{(n/\log n)!^{\log n}} &\sim
\frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &\sim
\frac{(\log n)^{\log n}}{\sqrt{2\pi n}^{\log n-1}}(\log n)^n.
\end{align*}
$$
The dominant term here is $(\log n)^n = \exp(n\log\log n)$, and we get an $\Omega(n\log\log n)$ lower bound in the decision tree model.


How to convert NFA with null moves to NFA without null moves?

If $q_j$ is a final state, you already said you would make $q_i$ into a final state. If there's no transitions from $q_j$ to another state in the FSM, then you are staying there forever- either as an accepting state or as a trap state. Either way, staying in $q_i$ is the same as staying in $q_j$ if you can't go anywhere from $q_j$.


The idea is to be able to modify the argument. FORTRAN used call-by-reference always, Algol-60 used the (mathematically clean, but hard to implement and with surprising corner cases) call-by-name; Pascal distinguishes between call-by-value and call-by-reference ("gets the variable"). But call-by-reference has its surprises, introducing aliasing between variables. Thus Ada offers call-by-value-return too.

If caller and callee reside on different machines, the performance gain of not copying arguments in and out, just using a pointer, is lost. Even worse, doing call-by-reference is quite inefficient (need to copy back and forth each time something changes). If you are defining what to do, I'd just ditch call-by-reference, and fight users tooth and nail to keep it out.


Output of well-known algorithms for the Subset sum problem

The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that when an algorithm answers YES, it can also naturally give you a certificate that proves it. Moreover, when this happens, you typically get a one valid solution. (This was just a clarification because your example outputs 2 valid solutions. Listing all solutions is a different thing).

Both algorithms you mention explicitly step through certain subsets, and so it is easy for them to also output the subset whose elements sum up to $t$. Whether you care about that extra information is up to you then.


Solving recurrence equation $T(n)=T(n^{2/3})+17$

This post answers the original version of the question, where the recurrence relation is

$$T(n)=T\left(\frac{n^2}{3}\right)+17$$

The recurrence relation is somewhat unconventional. Here is an outline to solve it.

Suppose $n\ge 6$. Let $n=3\cdot2^{2^{m}}$, where $m=\log_2(\log_2\frac n3)\ge0$.

$$\begin{align}
T(n)
&=T\left(3\cdot2^{2^{m}}\right)
 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m}}\right)}\right)-17\\
&=T\left(3\cdot2^{2^{m-1}}\right)-17
 =T\left(\sqrt{3\cdot3\left(\cdot2^{2^{m-1}}\right)}\right)-2\cdot17\\
&=T\left(3\cdot2^{2^{m-2}}\right)-2\cdot17
 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m-2}}\right)}\right)-3\cdot17\\
&=\cdots\\
&=T\left(3\cdot2^{2^{m-\lceil m\rceil}}\ \right)-\lceil m \rceil\cdot 17
\end{align}$$

Since $-1\lt m-\lceil m\rceil\le0$, $3\sqrt2\lt3\cdot2^{2^{m-\lceil m\rceil}}\le6.$ So
$T(n)\sim -17\log_2(\log_2 n)$ when $n$ goes to $\infty$.

Here are two related exercises.

Exercise 1. What is the recurrence relation for function $S$ such that $S(n)=T(3n)$?

Exercise 2. What is the asymptotic behavior of $T(n)$ if $n$ goes to 3 from above, assuming $T$ is continuous?


Finding number of smaller elements for each element in an array efficiently

The naive algorithm for determining $B$ from $A$:

  For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for
  $i=1,\dots,k$ and counting those that satisfy $A(i)<A(k)$.

This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the first $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is:

  For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for
  $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by
  setting it initially to $A(n)-1$ and then subtracting $1$ for each
  entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.

This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example:
$$\begin{vmatrix}
  A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\
  S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\
  B & 0 & 0 & 0 & 0 & 3 & 1 & 6 &  &  \\
\end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.


Hint: Start with a problem in $\mathrm{DTIME}(e^{2t}) \setminus \mathrm{DTIME}(e^t)$.


Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe?

Yes, it is still NP-complete. If you have an instance with $n < m$, then you can pad $U$ with $m - n + 1$ new elements and add new subset containing only the new elements. The original instance has a solution of size $s$ if and only the padded instance has a solution of size $s + 1$. The reduction is obviously polynomial time.


Applying Brewer's theorem (CAP) to a single node

In my opinion, the CAP theorem is applicable intentionally to distributed systems. To quote the article "Perspectives on the CAP Theorem @ IEEE Computer'2012 by Gilbert and Lynch":

  Brewer first presented CAP in the context of a Web service implemented by a set of servers distributed over a set of geographically diverse datacenters. Clients issue requests to the service, which sends back responses.

In this context, the "network" in CAP theorem refers to communications among servers (instead of communications among clients or between clients and servers). This can be justified by the following two arguments.

To quote the above article again (with emphasis added):

  Unlike the other two requirements, partition tolerance is really a statement about the underlying system rather than the service itself: communication among the servers is unreliable, and the servers can be partitioned into multiple groups that cannot communicate with one another.

In the proof of the CAP theorem in the above article, it says,

  Consider an execution in which the servers are partitioned into two disjoint sets: $\{p_1\}$ and $\{ p_2, \ldots, p_n\}$. Some client send a read request to server $p_2$.

The proof followed is based on the communication among the two disjoint sets of servers.

To summarize, CAP theorem (again, it is my own opinion) does not consider the situation in which client nodes and server nodes are partitioned. After all, we can do almost nothing in this bad situation. In other words, CAP theorem assumes that the communications between clients and servers behave well and focuses on the theory and implementation of the distributed service itself.


Maintaining search indices with binary trees

if I change a single index the whole file will need to be rewritten

So don't change indices. When you add data, remember what words already existed, and store subsequent words afterward. For each word, instead of storing one index in the index file, store several.

There is a lot to optimize on top of that. But I don't think this is a productive use of your time. There are existing programs that can do this (and far more complex use cases, too) very efficiently and without raising a sweat: databases. Use a database engine (Berkeley DB, SQlite, NoSQL, MySQL, TSQL, …).

If you want to understand how to store this kind of data efficiently, read about implementations of database engines. B-trees will be involved at some point.


What is the difference between deterministic and confluent?

If a binary relation is confluent and terminating, then the map from initial state to final state is total and deterministic.  The converse also holds.
If a binary relation is confluent, the binary relation need not be a function.
You'll have to decide what you mean by "deterministic" and whether you refer to what the original state ultimately leads to (then the answer to your question is yes, as mentioned in the first paragraph of this answer) or whether you refer to the behavior in a single step of the system (then the answer is no, as mentioned in the second paragraph of this answer).


I'm not sure what's the simplest way, but you can use diagonalization. We will construct an oracle for the following problem:
$$
L = \{ x : O(y) = 0 \text{ for all } |y|=|x| \},
$$
where $O$ is some oracle that we construct by diagonalization. The same oracle will also be used to solve $L$ in randomized polynomial time, but we will ensure that it doesn't suffice to solve $L$ in deterministic polynomial time.

Let $M_i$ be an enumeration of timed oracle Turing machines running in polytime (that is, $M_i$ runs some other machine $M'_i$ for $p_i$ time steps, where $M'_j,p_k$ go over all oracle machines and polynomials).

We construct $O$ in stages. Initially, $O$ is empty (none of its values are decided).

In stage $i$, we handle $M_i$. We pick some length $n$ on which $O$ is completely empty, and furthermore the running time of $M_i$ on $0^n$ is at most $2^{n-1}$ (this will hold for all large enough $n$), and run $M_i$ on $0^n$. Whenever $M_i$ queries an undecided value of $O$, we set the value to $0$. If the machine $M_i$ says that $0^n \notin L$, then we set all other values of $O$ of length $n$ to $0$. If it says that $0^n \in L$, then we set the other values of $O$ of length $n$ so that exactly half of them are $0$ and half of them are $1$.

Finally, we set all undecided value of $O$ (after going through the entire enumeration) to $0$.

Our construction guarantees the following properties:

$M_i^O$ fails to compute $L$. Consequently, $L \notin \mathsf{P}^O$.
For each length $n$, if we choose a random $y$ of length $n$ then $\Pr[O(y) = 0] \in \{1/2,1\}$. This gives a trivial random sampling algorithm for $L$, showing that $L \in \mathsf{BPP}^O$. (In fact, the algorithm has one-sided error, so $L \in \mathsf{RP}^O$.)


What are witnesses C and k for an O-bound?

I am going to guess what $C$ and $k$ mean in your context:

$f(x) = O(g(x))$ if and only if $\exists C, k \;\; \forall x \ge k \;\; (f(x) \le C|g(x)|)$.

You are asked to find constants $C$ and $k$ and prove that for all $x \ge k$ you have $8x+9 \le C x^2$.

I am going to take $C = 1$ and $k = 9$. We have $x \ge 9$ so $C g(x) = C x^2 = x^2 \ge 9 x = 8x + x \ge 8x + 9 = f(x)$.


I'm not sure I completely understand your questions. Still:

  who deals with the size of the block?

If the compiler does not know the size, it can write the size at the very beginning the block, after (or before) the tag. Some convention must be established -- this is something that must be decided when designing the runtime system.

  who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it.

If the type is known by the compiler, the compiler can emit code to put the right tag. Otherwise, the compiler must emit code which will compute the tag at runtime, e.g. fetching it from some other block, and store it at the start of the block.

  But then what is done in compile time? How does a compiler represent objects at compile time?

It does not have to. A compiler must emit target code which, at runtime, will deal with the tags.

Further, note that tags are not always needed. If the language is (statically) typed, the compiler might know the size and type of everything, hence there would be no need to store tags at runtime.


Here is an algorithm which satisfies your conditions:

for i in 0,...,n-1:
   A'[i] = 0

Clearly your conditions are lacking.

Correction of a sorting program, like any other program, is a combination of two condition: termination and partial correction. Termination just states that if the preconditions are satisfied then the program always terminates (in your course the phrase used is evidently "outputs after finite time", but halts or terminates is shorter). Partial correctness means that if the preconditions are satisfied and the program halts, then the postconditions are satisfied. What is left here is to come up with preconditions and postconditions. Since you're not working within a formal model, it is not clear how exactly to state the precondition, but it's probably something like that:

Precondition: The input $A$ is an array of length $N \geq 1$ of numbers.

(More generally, it is an array of some linearly ordered set, but we can think of "numbers" (whatever that means) as an important special case.)

Stating the postcondition is harder. It is not enough to ask that the output be sorted, as my example above shows. The semantics are subtler. Here is one way of stating the postcondition:

Postcondition:
(1) The output array $A'$ is an array of length $N$ of numbers.

(2) The output array $A'$ is nondecreasing, i.e., $A'[0] \leq \dots \leq A'[n-1]$.

(3) The multisets $\{A[0],\ldots,A[n-1]\}$ and $\{A'[0],\ldots,A'[n-1]\}$ are equal, i.e., for each number $x$, the number of elements in $A$ equal to $x$ is the same as the number of elements in $A'$ equal to $x$.

The way that you prove postcondition (3) for bubble sort (and, more generally, for comparison sorts) is by showing that the swapping operation preserves the multiset of elements (the fast implementation of quicksort might need more care). So it might seem that you can replace (3) with the following postcondition:

(3') The array $A'$ is obtained from $A$ by a sequence of swaps.

There are two problems with this postcondition. First, it is not semantic — it doesn't describe what sorting accomplishes, only how sorting is done. Second, it is too restrictive. There are sorting algorithms which use operations beyond swapping. A particularly useful example is counting sort. Suppose the sorted numbers come from a very small domain, say $\{0,\dots,m-1\}$. We compute a histogram of the input array (using an integer array of length $m$), and then go over the histogram, producing a sorted version of the input.


Operation on a regular language and context free language

There is no guarantee that your resulting language will be context free.

Here is a hint for creating a more formal proof.  Try the languages $L_1 = c^*$ and $L_2 = a^nb^n$.  The resulting language, given your additional requirement of $|u| = |v|$ would be $c^{2n}a^nb^n$.

Using the pumping lemma for context free languages, are there two substrings that you can pump indefinitely that will match this language?


Proving inherent ambiguity of a language is difficult, but proving ambiguity of a grammar is relatively quite easy.

The definition of ambiguity of a grammar does not say that every string has to have different parse trees. It says there need to exist only one string which has different parse tree to make a grammar ambiguous.

The trick to achieve two different parse tree for an ambiguous grammar is to look for a string where you can apply two different rules for the same string or the same rule in two different ways. Since one rule derives $0S1S$ and the other rule derive $1S0S$ you cannot have both rules deriving same strings, so you have to look for a rule that can be applied in two different ways. There you are in luck. Both rules can be applied in different ways.

Take first rule for example: $S \rightarrow 0S1S$. Can you have a string starting with 0 but matches 1 at two (or multiple) different places? It turns out you can $\underline 0$-$10$-$\underline 1$-$\epsilon$ and $\underline 0$-$\epsilon$-$\underline 1$-$01$ i.e. string $0101$. $0101$ and $1010$ are the smallest length strings of the grammar which will have different parse trees.

String $010110$ also has two parse trees $\underline 0$-$\epsilon$-$\underline 1$-$0110$ and $\underline 0$-$10$-$\underline 1$-$10$.


Given two identical DOM trees find same node in tree B

You are right, the complexity of the second algorithm is $O(P)$ where $P$ is the depth of the given vertex in the second tree. Notice that, without additional assumptions, it might very well be $P=\Omega(N)$ (think, e.g., of a path rooted in one endpoint where the given vertex is the other endpoint).
If the second tree is somehow "balanced", for some reasonable definition of balanced* then its height will be at most $O(\log n)$, hence $P=O(\log n)$.
*Since your tree is not necessarily binary you'd have to provide a suitable definition of balanced. A sufficient condition for $P=O(N)$ would be for the heights of the two tallest subtrees rooted in two children of each node of the second tree to differ by at most an additive constant.


How much does C# gain from its value types

Swift does the same thing (having both value types and reference types). I'm sure there are efficiency studies, performed by the people implementing the Swift compiler.

But the difference between reference types and value types goes a lot deeper. What you need to look at is things like mutability, semantics when passing parameters, and so on. I don't choose reference vs. value types for micro efficiencies, but for the semantics.

So your assumption "the design decision is mainly to make small objects more cache friendly", is firstly wrong, and secondly I strongly doubt it makes things more cache friendly.


Higher-ranked polymorphism without explicit application or subtyping?

The Dunfield & Krishnaswami paper's introduction refers to Practical type inference for arbitrary-rank types

  As can be seen, it scales well to advanced type systems; moreover,
  it is easy to implement, and yields relatively high-quality error messages
  (Peyton Jones et al. 2007)

In System F-ish approach there is also a "subtyping" relation. See section 3.3 Subsumption.

I'd also emphasize that Haskell doesn't have impredicative types (or inference for them). See: https://mail.haskell.org/pipermail/ghc-devs/2016-September/012940.html for pointers.

  You can write a polytype in a visible type argument; eg.  f @(forall a. a->a)
  You can write a polytype as an argument of a type in a signature  e.g.  f :: [forall a. a->a] -> Int

  And that’s all.  A unification variable STILL CANNOT be unified with a polytype.  The only way you can call a polymorphic function at a polytype is to use Visible Type Application.

  In short, if you call a function at a polytype, you must use VTA.  Simple, easy, predictable; and doubtless annoying.  But possible.

I.e. id id will always be elaborated as

forall a. id @(a -> a) (id @a)

not

id @(forall a. a -> a) id

Yet, you can write the latter explictly, if you enable ImpredicativeTypes.


Determining cycle time and and hold time in logic circuits

Well if someone is interested I have solved the question myself.

First of all, it indeed is possible that $t_{hold} = t_{setup} + t_{pd-min}$.

And about the input time, it has to satisfy: $$t_{hold} \le t_{pd-min}(logic) + t_{input-valid-min}$$

since $t_{hold} = 8ns$ and $t_{pd-min}(Logic) = 10ns$ , even $t_{input-valid-min} = 0$ satisfies this.


Is there a program to solve a metric TSP for 80 edges at optimum?

It should be no problem to solve this instance with an integer linear programming based approach. You could try the online interface to the Concorde TSP solver.


How to determine the set of real numbers corresponding to a given floating point number?

The powers of two are more interesting than most other numbers.
Assume you are using double precision IEEE 754 format floating point numbers. Let $u = 2^{-52}$, Then the next floating point number larger than 1 is $1+u$, and the next floating point number smaller than 1 is $1 - u/2$.
A real number x is rounded to 1 if $1-u/4 ≤ x ≤ 1+u/2$. For any floating-point number f with $1 < f < 2$, x is rounded to f if $f - u/2 ≤ x ≤ f + u/2$ if the last bit of f is even, and if $f - u/2 < x < f + u/2$ if the last bit of f is odd.
Numbers x with $f - u/2 < x < f + u/2$ are always rounded to f, because f is the nearest floating point number. For the numbers $x = f ± u/2$, $f$ and $f ± u$ are equally far away, so the round-to-even rule decides.


Algorithm to maximize function of subsets

The algorithm that iterates through every $2^{1000}$ subsets.  Sorry, but stated like this, the answer is that there is no solution.

For every algorithm you come up with, I can come up with a subset $T \subseteq S$ such that $T$ is the last of all sets to be tested, and be the max of $f$.


Examples of sophisticated recursive algorithms

My favorite recurrence shows up in output-sensitive algorithms for computing convex hulls, first by Kirkpatrick and Seidel, but later repeated by others.  Let $T(n,h)$ denote the time to compute the convex hull of $n$ points in the plane, when the convex hull has $h$ vertices.  (The value of $h$ is not known in advance, aside from the trivial bound $h\le n$.)  Kirkpatrick and Seidel's algorithm yields the recurrence
$$
  T(n,h) = \begin{cases}
       O(n) & \text{if }n \le 3 \text{ or } h \le 3 \\
       T(n_1, h_1) + T(n_2, h_2) + O(n) & \text{otherwise}
  \end{cases}
$$
where $n_1, n_2 \le 3n/4$ and $n_1 + n_2 = n$ and $h_1 + h_2 = h$.

The solution is $T(n,h) = O(n\log h)$.  This is a little surprising, since $h$ is not the parameter being split evenly.  But in fact, the worst case of the recurrence happens when $h_1$ and $h_2$ are both about $h/2$; if somehow magically $h_1$ is always constant, the solution would be $T(n,h) = O(n)$.

I used a variant of this recurrence in one of my first computational topology papers:
$$
  T(n,g) = \begin{cases}
       O(n) & \text{if }n \le 3 \text{ or } g = 0\\
       T(n_1, g_1) + T(n_2, g_2) + O(\min\{n_1, n_2\}) & \text{otherwise}
  \end{cases}
$$
where $n_1 + n_2 = n$ and $g_1 + g_2 = g$.  Again, the solution is $O(n\log g)$, and the worst case occurs when both $n$ and $g$ are always split evenly.


Karp hardness of a vector system allocation

Omitting the second requirement (allowing vectors to share initial points):

This becomes $\mathrm{NP}$-complete since it is exactly $\mathrm{MAX}$-$\mathrm{CUT}$.

Consider the set of all terminal points of the vector system. Exclude all the edges between any two vertices of this set. All the edges inwards constitute the cut.

Putting back the second requirement (vectors required not to share inital points)

This is $\mathrm{NP}$-complete by a reduction from $\mathrm{DOMINATING\ SET}$.

Reverse the direction of the vector system.

We see that now the set of initial points (originally terminal points) are dominating the set of terminal points (originally initial points). Note that these two sets are disjoint.

So, given an instance $(G,k)$ of $\mathrm{DOMINATING\ SET}$. Our reduction just produces $(G,n-k)$ where $n=|V(G)|$ as an instance of the vector allocation system.

If there is a dominating set of size $k$, then for each of the dominated $n-k$ vertices, we can assign for it a dominating vertex among $k$ dominating vertices. The direction is from the dominating vertex to the dominated vertex (this is the reversed direction). We have formed a (reversed) vector system of size $n-k$.

Conversely, if there exists a vector system of size $n-k$. The set of terminal points (originally initial points) are of size exactly $n-k$. Take the remaining $k$ vertices as a dominating set. This shows that the original instance of $\mathrm{DOMINATING\ SET}$ is a YES instance.


Can a unnormalized floating point number be recognized also when exponent is not zero?

I had to re-read your question a few times to have an opinion. The question states that there exists a sign, an excess 64 exponent, and a 16-bit mantissa. It then asks you to normalize a given bit pattern. It's my opinion that you are supposed to make some inferences.

First off, an excess 64 suggests that you have a 7-bit mantissa. (It's not certain as one technically could have an excess 64 applied to an 8-bit or even a 9-bit mantissa, but those are all highly unlikely in normal circumstances.) This appears to be confirmed in the sense that they supply what appears to be one bit, followed by 7 bits, followed by 16 bits.

Second, you are being asked to normalize a value. This is commonly asked by providing you with the signed number and a positioned radix, leaving you to figure out the sign, exponent, and mantissa. But in this case, their question must be taken to imply that they are giving you a denormalized value. So I believe they want you to accept the last 16 bits just as it is given to you and to do the necessary shifting to put it back into a properly normalized form. And I therefore think they want you to accept the given exponent as a starting point that you assume is correct for the given value.

This leads to the third problem. You inserted a hidden bit on your own, on the assumption that the denormalized value carries a hidden bit. But denormalized values, even in FP formats supporting hidden bits (and not all do that) do not have an implied hidden bit. So I wonder why you inserted one on your own, writing "$1.0001010100000001\times 2^0$." If you were right about that, then why in the world would they now ask you to normalize it?? It doesn't make any sense, neither in the format of the question nor in actual experience with common cases. So I think here you must assume the opposite... that the 16 bit mantissa they gave you is instead just a pure 16-bit integer that has not been normalized and doesn't imply a hidden bit. Otherwise, what could they possibly be asking you to do?

That said, I haven't worked from your book. So I don't know the context here. You will have to use your own judgment about what I write here and see if you think I might be right about it.

If I am right, then you are being told $sign=0$, $exponent=0$ as it is in excess 64, and $value=5377$ (decimal.) And you are then asked to normalize it and create a proper 24-bit FP formatted value. Since you mentioned IEEE754, which uses hidden bit notation, I'd assume that this novel 24-bit FP format also uses hidden bit notation. I wish I had your book, as that would help to gain context, but I get something like the following: $0 \,\, 1001100 \,\,\, 0101000000010000$


Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs

Indeed, if states and inputs are finite (and the tape is finite, which is quite reasonable), then you can easily reduce the Turing machine to a Finite State Machine. However, this is completely impractical, since it doesn't yield any reasonably effective algorithms. I.e. your solution for the halting problem will be to explode the states of the TM with all possible input combinations of size N, and then find a path that reaches a stop state, right? Probably don't want to implement such a check in your compiler.


Chromatic polynomial of a cycle - Interpreting its terms

There is a theorem of Whitney answering your question. Let
$$ P(G,\lambda) = \sum_{k=0}^n (-1)^k a_k \lambda^{n-k}. $$
Then $a_k$ is the number of $k$-subsets of the edges of $G$ not containing any broken cycle. A broken cycle of $G$ is obtained from a cycle of $G$ by removing its maximum edge according to some fixed ordering of the edges.

For example, if $G = C_n$ then for $k < n-1$, $a_k = \binom{n}{k}$, and $a_{n-1} = \binom{n}{n-1} - 1$, since we miss one broken cycle.

For a proof and references to other proofs, see this paper.


In general, the answer is usually "no". Equality of languages is, most of the time, undecidable; regular languages are a special case here, at least when they are given in certain representations.

What you can do is to break down those languages in terms of closure properties of REG, e.g. reversal, homomorphism, complement, etc.

Since your task here is to prove such closure properties, you'll have to take the long and creative route: come up with a construction and prove it correct. The purpose of the exercise is to train doing exactly that, so taking a shortcut would be unwise.


Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

This characterization of words not in $A4$ is nice. However, what we want is to produce words in $A$. Let us classify the words in $A4$ as the disjoint union of the following 3 pieces.

the words where the number of $a$'s is even and the number of $b$'s is even.
the words where the number of $a$'s is odd and the number of $b$'s is even.
the words where the number of $a$'s is odd and the number of $b$'s is odd.

Now use a distinct nonterminal to represent each piece.

The above hint should be enough to set you moving.

Once you have got your own solution, or you run into another bottleneck, you could mouseover the following to reveal the spoiler.

   To facilitate writing the grammar, we will add a non-terminal to represent the 4-th piece.

 $\quad$4. the words where the number of $a$'s is even and the number of $b$'s is odd.

 Here is the grammar, where non-terminal $S_{i,j}$ represents the words whose number of $a$'s is $i$ modulo 2 and whose number of $b$'s is $j$ modulo 2.

 $S\to S_{0,0}\mid S_{1,0}\mid S_{1,1}$
 $S_{0,0}\to cS_{0,0}\mid aS_{1,0}\mid bS_{0,1}\mid\epsilon $
 $S_{0,1}\to cS_{0,1}\mid aS_{1,1}\mid bS_{0,0}$
 $S_{1,0}\to cS_{1,0}\mid aS_{0,0}\mid bS_{1,1}$
 $S_{1,1}\to cS_{1,1}\mid aS_{0,1}\mid bS_{1,0}$


Why is the counting variant of a hard decision problem not automatically hard?

The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard".

A decision problem is hard if it's NP-complete under polynomial-time many-one reductions (a.k.a. Karp reductions, a.k.a. polynomial-time mapping reductions).
A counting problem is hard if it's #P-complete under polynomial-time Turing reductions (a.k.a. Cook reductions).

As such, if a decision problem is NP-complete, we know that the corresponding counting problem is NP-hard but that's not the definition of what a hard counting problem is.  Being #P-complete seems to be a much stronger statement than just being NP-hard – Toda has shown that #P-complete problems are hard for the entire polynomial hierarchy under randomized reductions so, as a complexity class, #P feels much closer to PSPACE than to NP.

Going in the opposite direction, it's clearly true that, if the counting problem is easy in the sense of being in FP, then the decision problem is in P. After all, if you can efficiently count, you can certainly tell if the answer is nonzero.  However, just because the counting version is "not hard" (i.e., not #P-complete) doesn't imply that it's "easy" (i.e., in FP).  Ladner's theorem extends to #P so, if FP$\,\neq\,$**#P** then there's an infinite hierarchy of distinct complexity classes between them so our "not-hard" counting problem could be complete for any one of those classes and, therefore, not be "easy" (in FP).

Having said that, I don't think we have any counterexamples to the conjecture that a decision problem being NP-complete means that the counting version is #P-complete.  So, it's not a theorem but it is empirically true.


Order Notation - Why can't $c$ be in terms of $n$?

Suppose we define $f(x) = O'(g(x))$ to mean that there is a function $c(x)$ such that $f(x)\leq c(x)g(x)$ for all sufficiently large $x$. Then $f(x) = O'(g(x))$ for almost every pair of functions $f$ and $g$, just by taking $c(x)=f(x)$. So, this definition just isn't a useful way to compare functions.

(I say "almost every pair" because there are issues if we have infinitely many values of $x$ for which $g(x)=0$ and $f(x)\neq 0$ but I don't think it's worth pinning down exactly what functions work and what don't.)


Approximating the set of witnesses of a BPP algorithm

The idea suggested to you was helpful.  It basically amounts to suggesting a candidate algorithm $\mathcal{A}'$.

Your next step is to try bounding $|W(\mathcal{A}',x)|$  and $|\{0,1\}^n - W(\mathcal{A}',x)|$ for that choice of $\mathcal{A}'$.  See what you can come up with.  See if you can relate $|W(\mathcal{A}',x)|$ to $|W(\mathcal{A},x)|$ etc.


In a CSP, what is an extensional constraint?

Let $X$ be a finite set of variables, where each variable $x \in X$ has a domain of values. Let $D(x)$ denote the domain of the variable $x$. Let $C$ be a finite set of constraints on the variables.

Each constraint $c \in C$ has a scope, which is a subset of the Cartesian product $D(x_i) \times \cdots \times D(x_j)$. In other words, the scope of the constraints gives the set of legal combinations of values.

An extensional constraint is the relational view of the constraint. It is an explicit listing of the subset of the Cartesian product. You could also have something called an intensional constraint, where the idea is that the values are instead computed by an algorithm.


Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?

Yes.  You can replace the oracle with subroutine calls to the polynomial-time implementation of the oracle.  Or, to put it another way: $P$ is closed under composition.
The running time remains polynomial: if the original Turing machine used $p(n)$ steps, and the subroutine takes $q(n)$ steps, then the resulting machine will use at most $p(n) + q(p(n))$ steps, which is upper-bounded by a polynomial.


P vs NP is settled as soon as we find a $O(n^k)$ algorithm for an NP-complete problem (for any constant $k$) or show that no NP-complete problem has such an algorithm.

Whether or not $k$ is too big to yield a tractable algorithm is a different problem. Having a practical algorithm for, say, SAT, would indeed be very useful, many problems we currently solve heuristically (e.g. in chip design) could then be solved to optimality.


Can context-free grammar generate $a^{2^n}$?

It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\{a\}$ is regular.

Thus, your question is essentially, "is $\{a^{2^n}:n\in \mathbb N\}$ regular?"
And the answer to that is no (easy to prove using the pumping lemma).


Reducing a non-RE language to its complement

Such a undecidable language $L$ can not be in $RE$, since if there was a computable reduction from $L$ to $\overline{L}$, then $L$ would be in $R$.

Let $x'$ be the value to which $x$ reduces. $x' \in L$ if and only if $x\not \in L$. We could then decide $x\in L$ by enumerating $L$, and stopping to report that $x\in L$ as soon as we encounter $x$, and report that $x\not \in L$ when we encounter $x'$. That would make $L$ decidable, which is a contradiction. So there can be no reduction from a language in $RE$ to its complement.

By a similar argument, such a language can not be in $co-RE$ either.

There does exist an undecidable language $L$ that can be reduced to its complement. To find one, we must consider a language that is neither in $RE$ nor in $co-RE$. Let $L\in RE$ be an undecidable language. Then

$L'=\{0w|w\in L\} \cup \{1w|w\in \overline{L}\}$

is not recursive enumerable nor is its complement (see here).

But there clearly is a reduction from $L'$ to $\overline{L'}$.


How long will selection sort and merge sort take to sort a certain number of items?

They want you to apply rule of three under ridiculous assumptions.

  If an O(n²) algorithm takes 1ms for 1000 elements, then from 1ms = c * 1000² and the ansatz Xms = c * 100000² we get that X = 10000.

In essence, they want you to assume that the running time function equals $cn^2$, in which case you could compute the constant $c$ from the given information.

The problem is that

$O(\_)$ is only an upper bound and does not tell you anything about the true behaviour of the described function,
there are unknown lower-order terms hidden in that $O(\_)$ (and also $\Theta(n^2)$, if you had that) and
asymptotics tell us nothing for any finite $n$.
They also ignore that the algorithms take different amounts of time for different inputs of the same size and
that "time" is a famously fickly cost measure as it depends a lot on effects like caching and process scheduling.

Therefore, the problem is senseless.


Formula for finding number of colors to color a map such that no two adjacent counties have the same color

No.

The famous four-colour theorem says that four colours are always enough (assuming that counties are contiguous areas of land).
It's easy to tell if one colour is enough: this is the case only if every county is an island, so has no border with any other county.
It's easy to tell if two colours is enough: this corresponds to the adjacency graph being bipartite. You can determine this by colouring an arbitrary county red, then colouring all its neighbours blue, then colouring all their neighbours red, and so on. If this process produces a legal colouring, you have your colouring; if it fails, it turns out that there is no colouring with two colours.
If two colours isn't enough, then it's NP-complete to tell whether three is enough or you have to use four.  This means that, as far as we know, there's no efficent algorithm to determine whether an arbitrary map can be coloured with three colours. This is a result due to Garey, Johnson and Stockmeyer (Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3):237--267, 1976; Science Direct).

There are efficient algorithms to find four-colourings of planar graphs: the two computer-assisted proofs that four colours is enough both gave algorithms. But, as noted above, there's no known efficient algorithm to tell whether four colours is optimal for a given map.


Let $\mathsf{BWT}^{-1}$ be the inverse Burrows-Wheeler transform, that is, $\mathsf{BWT}^{-1}(\mathsf{BWT}(w)) = w$.

If $\mathsf{BWT}(x) = \mathsf{BWT}(y)$ then
$$
x = \mathsf{BWT}^{-1}(\mathsf{BWT}(x)) = \mathsf{BWT}^{-1}(\mathsf{BWT}(y)) = y.
$$


Since all intervals are non-overlapping, the use of an interval tree is unnecessary. We will store our intervals in an AVL tree $T$ sorted by start points and use the fact that bulk deletion of a set of contiguous keys $q_i,...q_{i+k-1}$ can be done in $O(\log n + \log k)$ amortized time (see non-open access and open access).

Let $x=[a,b)$ be an interval and  $begin(x)=a$, $end(x)=b$. We define $pred(x)$ and $succ(x)$ to be the previous and next intervals. Both functions have $O(\log n)$ complexity, where $n$ is the number of intervals in the tree. The number of disjoint intervals is the number of leaves in $T$.

Insertion

Let us first examine what happens when we insert an interval $x$ into the tree. When inserting $x$, we can determine the range of intervals it overlaps with in $O(\log n)$ time by performing predecessor and successor queries. When inserting $x$, we need to perform one of the following three operations on $T$

Add a new disjoint interval.
Extend an existing interval.
Combine and potentially extend $k$ existing intervals.

(1a) The first case happens if the inserted query $q$ doesn't overlap with any of the intervals in our set i.e. $
end(pred(x)) \leq start(x) \land begin(succ(x)) \geq end(x)$ Since no intervals need to be updated, we simply insert $x$ into $T$.

(2a) The second case happens if $x$ overlaps with or contains one other interval $q$. In order to update the interval, delete $q$ and reinsert $q'$ where $$q'=[\min(start(x), start(q)), \max(end(x), end(q)))$$

(3a) In the third case, let $Q=\{q_i, q_{i+1}, ... q_{i+k-1}\}$ be all $k$ of the intervals that $x$ intersects. $Q$ can be obtained by finding the predecessor and successor of $x$. We can again update the tree by deleting all of $Q$ from $T$ and reinserting an interval $$q'=[\min(start(x), start(q_i)), \max(end(x), end(q_{i+k-1})))$$

The first and second cases have $O(\log n)$ time complexity. The third case at first looks like $O(k\log n)$ time which is undesirable as $k=O(n)$. However, it has been shown that bulk deletion of a set of keys in the range $[L, R]=\{q_i, q_{i+1}, ... ,q_{i+k-1}\}$ can be done in amortized $O(\log n + \log k)$ time. Therefore, for insert we have amortized $O(\log n)$ complexity. Note that the number of leaves (disjoint intervals) in the tree can be updated after each insertion in constant time.

Deletion

By deleting an interval $x$, we either

Split an interval into two
Shorten 1 or 2 intervals and delete those in between (if any).

(1b) The first case happens if $x$ is nested within an interval $q$ i.e.
$$start(q) \leq start(x) \land end(x) \leq end(q) $$ Therefore, we delete $q$ and insert the two resulting intervals $[start(q), start(x))$ and $[end(x), end(q))$

(2b) In the second case, let $Q=\{q_i, q_{i+1}, ... q_{i+k-1}\}$ be the intervals that $x$ overlaps with. We can delete all of $Q$ from the tree and update and reinsert the the trimmed versions of $q_i$ and $q_{i+k-1}$ if they were not completely nested in $x$. As in case (3a), this is a bulk deletion that can be done in amortized $O(\log n + \log k)$ time.

Similar to insertions, we can keep track of the number of leaves after each deletion in constant time.

Amortized Complexity of Bulk Updates in AVL-Trees

Bulk Updates and Cache Sensitivity in Search Trees


Recover boolean vector from dot products

Here is an variant of the idea 1 in the question, where a factor of 2 is used to replace the original factor of 9.

Let $v=[2^0, 2^1, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the first 64 entries of $b$.
Let $v=[0, 0, 0, \cdots, (64 \text { zeros}),  1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 64 entries of $b$.
Let $v=[0, 0, 0, \cdots, (128 \text { zeros}),  1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 128 entries of $b$.
And so on, until we have determined all entries of $b$. There may be less than 64 positive numbers in $v$ in the last round.

The above scheme is the best possible if the number of effective bits in $b^Tv$ is 64 and we have no prior knowledge about $v$ except the number of its entries. This can be seen easily from information theory, as each query against the black box can provide at most 64 bits of information.


Behaviour of Dijkstra in Case of Negative Edge Weight

The article on Dijkstra's algorithm at GeekForGeeks say "Dijkstra’s algorithm doesn’t work for graphs with negative weight edges in general."

Introduction to Algorithms by Corman et al. says "Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph for the case in which all edge weights are nonnegative."

As explained in the linked question and answer and as OP has found, the general proof of the correctness of Dijkstra's algorithm will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense.

I would advise you to stay away from Dijkstra’s algorithm when a graph that has negative weights appears. It might work in some cases, but it may lead you into troubles that will be avoided if you apply Bellman–Ford algorithm or Floyd–Warshall algorithm.

By the way, the shortest distance from $A$ to $G$ is 2.


Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

A large part of what is known goes unpublished, when it is considered trivial. What counts as trivial is, of course, different in different times and for different communities. For instance, we do not consider particularly interesting about binary numbers that they are as expressive as decimals, but that the machines that operate on binary representations are simpler.

In his famous 1936 article, Turing is satisfied with the premise that the alphabet of the machine is finite, which leads me to believe that differences beyond that are considered trivial by him, for general purposes.

He discusses the difference between machines with infinite and finite sets of symbols, and reaches the conclusion that using an infinite set of symbols would, at some point, make it impossible to concretely differentiate them from each other (which could be another way of illustrating the fact that real numbers can't be listed). He then states that the effect of this restriction is not very serious, because you can, at least to some extent, conveniently represent bigger alphabets by groups of symbols of smaller ones, considering that any effective computation can only use, in practice, what amounts to a finite number of symbols.

I suggest that you try to imagine how to simulate an $n$-symbol TM (I would start with $n=8$) on a two-symbol one. It is a good exercise.


Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$

The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: divide $m$ by $c$, and increment $c$. The algorithm terminates when one of the following happens: $m = 1$, in which case you can declare success; or $m$ is not divisible by $c$, in which case you can declare failure.


Are disjoint edges the same as matchings?

Two disjoint edges $(a,b)$ and $(c,d)$ are edges that do not share any endpoint, i.e., $\{a,b\} \cap \{c,d\} = \emptyset$. A matching is a set of pairwise disjoint edges.


What are the most used statements in programming (ranked)?

I don't know about statement types, but there's been a lot of research over the decades about CPU instruction frequency and how it impacts ISA design, IR design, and VM design... but it's all for languages like C. See, for example, loads/stores/branch frequencies for the SPEC2017 benchmarks.
If your language is C-like, there are basically only two reasons to compile to a virtual machine:

The goal is portability and/or optimisation convenience, in which case it is an intermediate representation on the way to generating code for a real machine.
The goal is some unusual performance constraint, such as extremely fast compilation, or for the generated code to be as tiny as possible.

In managed/interpreted languages, the main considerations are:

If the VM code is also a distribution format (e.g. JVM or DotNET), size may be a factor.
When interpreting, maximising the amount of "actual computation" (as opposed to interpreter overhead) performed for each interpreted instruction.
When compiling (whether AoT or JIT), preserve as much of the relevant semantics of the source language as is needed for efficient optimisation, and discard (as far as possible) as much of the irrelevant semantics as possible.

Examples of that last point: Preserving basic types (integers, floats) is much more important than preserving non-basic types (structs, objects). Preserving the distinction between static calls and dynamic calls in OO languages is also extremely important.
I suspect that a reason why there isn't as much general research on object-oriented, managed, non-C-like languages (calling them "modern" is arguably misleading!) is because specific libraries and frameworks tend to dictate the style of programming that programmers do.
For C# specifically, if such information has been collected, it seems unlikely that Microsoft is telling anyone.


Are combinatory logic terms always larger?

not an expert on this but here are two historical papers that seem to be closely relevant to the question and it is possibly a semi active area of research. Turner proposed a set of combinators that can be reduced to SK combinators. this next paper argues that Turner combinators even not reduced to SK combinators leads to exponential blowup (and that presumably the reduction would to SK terms be even larger). but then the 2nd paper says there is an efficient O(n log n) space algorithm based on Turner combinators. (it appears maybe that claims have been made about polynomial efficiency that are regarded as not fully demonstrated/ unproved & are therefore regarded as conjectures...?) anyway apparently real functional evaluation in applied languages typically does not use combinator method so implementors are not too concerned with issues of theoretical efficiency of evaluation of functional expressions by combinator translation.

What is an Efficient Implementation of the λ-calculus? / Frandsen, Sturtivant (1991) (see p.18)

Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities $2^{Ω(ν)}$, i.e. an exponential lower bound.
It is open whether any implementation of polynomial complexity, $ν^{O(1)}$, exists, although some implementations have been implicitly claimed to have this complexity.

Translation of Turner Combinators in O(n log n) space / Noshita (1985)

A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n.


Answering questions about the recurrence of certain aspects of an algorithm

Firstly, there is one minor typo in the question. The "$T(n) =\frac 32 * T(n-1) + 1$" should be "$T(n) =\frac 32 * (T(n-1) + 1)$" since this equality is said to be obtained by simple algebra from the equality above it. However, this typo does not affect either the question or this answer.

The answer to all of your questions are so simple that I can hardly imagine that you missed it. Well, on the other hand, it is indeed very easy to miss it.

Let me give you a simple example to illustrate the answer. Suppose we have the following function, which computes the factorial.

function FACTORIAL(n)
    if n = 1 then
        return 1
    else
        return  n * FACTORIAL(n-1)
    end-if

Suppose we have made a call, FACTORIAL(4). That means we must have called FACTORIAL(3), FACTORIAL(2) and finally FACTORIAL(1). So we have made four calls to this function in total, the last three of which are called recursively. In fact, we have the following recurrence relations for $U(n)$, the number of recursive calls made in FACTORIAL(n).
$$U(1) = 0$$
$$U(n) = 1 + U(n-1), \text { for } n\gt 1$$
Notice the first "1" in the last equality, which stands for the call to FACTORIAL with parameter $n-1$ in the code, n * FACTORIAL(n-1) while $U(n-1)$ comes from the number of recursive calls made by FACTORIAL(n-1). In other words, the recursive calls made by FACTORIAL(n-1) does not include that call itself, which is, though of course, counted towards the recursive calls made by FACTORIAL(n). We can also check by contradiction. Let us suppose we did not have that "1". Then we would get $U(4)=U(3)=U(2)=U(1)=0$, which said that we had made no recursive calls to FACTORIAL when we had computed FACTORIAL(4), which is not true at all.

In the same way as in this simple example, all those constant 1's and one 2 in the question come from right where the calls are made. For example, when x = 2, the function will return (3*RANDOM(n-1) + RANDOM(n-1) + 1), which incurs $(1+R(n-1)) + (1+ R(n-1)) = 2 + 2*R(n-1)$ recursive calls.


Program Counter Incrementation When instruction Is More Than One Word

Who says incrementing the program counter would have to happen before decoding the instruction? Modern decoders will actually decode several instructions simultaneously (if the first instructions are simple enough so that the decoder can find the start of the next instructions with negligible delay).

That's what Intel processors with their fabulously complex instruction set do. The decoder is given a large range of bytes. For some instructions it's easy to determine the length, for some it's difficult.

So the decoder tries to find the length of the instruction starting at the first byte, and very quickly finds that it is a simple instruction say of 3 bytes, or something more complicated. The decoder does the same thing simultaneously assuming an instruction starting at byte 1, at byte 2, at byte 3 and so on. (Duplicating hardware is cheap when a chip can have billions of transistors).

Once the decoder has these numbers (instruction at #0 is 3 bytes, instruction at #1 is difficult, instruction at #2 is 6 bytes, instruction at #3 is 2 bytes, instruction at #4 is difficult, instruction at #5 is difficult etc. ) it combines these results and knows there is a 3 byte instruction at #0, followed by a 2 byte instruction at #3, followed by a difficult instruction at #5. The information about the instruction starting at #1, #2, #4, #6 etc. is thrown away.

And then the decoder gets really going: It can decode several simple and one complex instruction. So the processor decodes the simple instruction at #0, the simple instruction at #3, and the complex instruction at #5. And when it has the length of that complex instruction at #5, then it increases to program counter.


A Question relating to a Turing Machine with a useless state

This is clearly reducible from the Halting Problem. If a machine $M$ does not stop on input $x$ then any final state is "useless". Given an input $M,x$ for the Halting problem, it is easy to construct $M_x$ that halts on every input (thus its final state is not useless) if and only if $M$ halts on $x$. That way you can decide Halting Problem if you can decide $\mathrm{USELESS}_{\mathrm{TM}}$, which yields a contradiction.


To me, the way the cutting cost analogy is unnatural. I'm going to work with an equivalent problem instead. Additionally, I'll think about the task in reverse, combining pieces instead of cutting.

An equivalent problem:

  Given a sequence of integers $s_0,s_1,\ldots,s_k$. We want to find the order of adding up all the integers such that the cost of this process is minimize. The add operation only works on each adjacent pair in the sequence and will replace the pair with its sum. The cost of each add operation is the resulting sum.

I'll think about the problem of finding lowest cost first. The order of adding can be traced back if you have the algorithm to find the lowest cost.

Define $M(i,j)$ to be the lowest cost of this process on the subsequence

  $s_i,s_{i+1},s_{i+2}\ldots,s_{j-2},s_{j-1},s_j$

where $0 \le i \le j \le k$

We can then formulate $M(i,j)$ in terms of smaller problems as follows:

  $M(i,j) = \Sigma_{y=i}^{j} s_y + \min\limits_{x \ldotp i \leq x < j} \{M(i,x) + M(x+1,j) \}$

for the case that $j-i>2$

I'll leave the base case of $j-i \le 2$ and the order of which $M(i,j)$ to calculate first for reader to work out.

The algorithm has to calculate $M(i,j)$ for every $0 \le i \le j \le k$ and each time it does that, it has to iterate over $x$. Thus, the time complexity is $O(k^3)$


NFA with exponential number of states when determinized

The standard example is the language $L$ of all words over an alphabet $A$ of size $n$ that don't contain all the different letters. There is an NFA accepting $L$ with $n+1$ states (or $n$ states if you allow multiple starting states): first guess a letter $a$ which is missing, then go (with an $\epsilon$-move) to an accepting state with self-loops for all letters other than $A$.

Any DFA for $L$ requires at least $2^n$ states. This can be seen using the Myhill-Nerode theorem. Let $S_1,S_2$ be two different subsets of $A$, and $w(S_1),w(S_2)$ words which contain all and only the letters in $S_1,S_2$, respectively. Without loss of generality, suppose $a \in S_1 \setminus S_2$, and let $w = w(A-a)$. Then $w(S_1)w \notin L$ while $w(S_2)w \in L$.


Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

No, it is not a context-free language. From my original SO answer: consider the string $0^n1^n0^n1^n \in L$, where $n$ is the pumping length from the pumping lemma for context-free languages. This fails the pumping lemma for context-free languages; in particular, we have seven cases for $vxy$:

$vxy$ consists entirely of 0s from the first part of the string. Pumping this up or down will cause the numbers of 0s in the first and third parts of the strings to be different, so we're no longer in $L$.
$vxy$ consists entirely of 1s from the second part of the string. Same problem between the second and fourth parts as between the first and third parts mentioned in case 1.
$vxy$ consists entirely of 0s from the third part of the string. Same but opposite problem as in case 1.
$vxy$ consists entirely of 0s from the fourth part of the string. Same but opposite problem as in case 2.
$vxy$ straddles the first and second parts of the string, beginning with 0s and ending with 1s. Pumping will change the the numbers of 0s and 1s in the first and second parts of the string, and they won't match the third and fourth parts of the string anymore, so we're not in $L$ anymore.
$vxy$ straddles the second and third parts of the string, beginning with 1s and ending with 0s. We have the same problem as in case 5.
$vxy$ straddles the third and fourth parts of the string, beginning with 0s and ending with 1s. We have the same but opposite problem as in case 5.


Deciding on Sub-Problems for Dynamic Programming

The principle of dynamic programming is to think top-down (i.e recursively) but solve bottom up. So a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way.


Select a subset of the columns in $2\times n$ matrix, is it easy?

Hint: Show that it is NP-hard by reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes (see a question on math.se).

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$), consider an instance of your problem with $b = n/2$, $c = \sum_i (M+x_i)/2 - 1$ for large enough $M$ (I think that $M = \max_i x_i$ should suffice), and the matrix
$$
\begin{bmatrix}
M+x_1 & \cdots & M+x_n \\
M+\frac{\sum_i x_i}{n/2}-x_1 & \cdots & M+\frac{\sum_i x_i}{n/2}-x_n
\end{bmatrix}.
$$


A deterministic FA for $0^*1^*$ is required

To construct a DFA, note the following:

An empty string or any string containing only $0$s is accepted, so
any $0^*$ is accepted.
Zero or more $0$s followed by one or more $1$s is accepted, so any
$0^*11^*$ is accepted.
Zero or more $0$s followed by one or more $1$s followed by $0$ is
rejected, so any $0^*11^*0$ is rejected.
Any extension to a rejected string is also rejected (i.e. there is no
route back from a rejecting state to an accepting state), so any
$0^*11^*0(0+1)^*$ is rejected.

This suggests a three state DFA with two accepting states and one rejecting state ...


Find ellipsoid that contains intersection of an ellipsoid and a hyperplane

Your are describing the basic step in the ellipsoid algorithm. Your question might be answered in lecture notes on the algorithm, such as these ones by Goemans.

More generally, given a convex body $K$, the minimum volume ellipsoid containing it is called the Löwner–John ellipsoid. The same name is also given to the maximum volume ellipsoid contained in $K$. See for example these lecture notes of Boyd and Vandenberghe.


What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language?

Reiterating my comment, for each $A$ we can construct a language $A'$ (read: $A$ jump) which cannot be reduced to $A$ by taking all halting TMs with oracle access to $A$. The classical proof of the undecidability of the halting problem applies, showing that $A'$ cannot be (Turing-)reduced to $A$.


Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

It is perhaps more illuminating to reformulate this proof by contradiction as a proof by induction. We prove that $d[v] = \delta(s,v)$ by induction on the latter (the case $\delta(s,v) = \infty$ should be taken care of separately). If $\delta(s,v) = 0$ then $v = s$, and indeed $d[s] = 0$. Now suppose that the result holds for all vertices at distance $i$ from $s$, and consider a vertex $v$ at distance $i+1$ from $s$. Let $u$ be a neighbor of $v$ at distance $i$ from $s$. By induction, $d[u] = \delta(s,u)$, and so once $u$ is processed, $d[v] \leq \delta(s,u) + 1 = \delta(s,v)$. Since $d[v] \geq \delta(s,v)$, it follows that $d[v] = \delta(s,v)$, as needed.
How do the two proofs relate? Let $U$ be the set of vertices such that $d[v] = \delta(s,v)$; clearly $s \in U$. Let $v \neq s$ be an arbitrary vertex reachable from $s$, and let $u$ be a predecessor of $v$, that is, a neighbor of $v$ such that $\delta(s,v) = \delta(s,u) + 1$. The proof shows that if $u \in U$ then also $v \in U$. You can now proceed in two different ways:

Proof by contradiction: choose $v \in U$ minimizing $\delta(s,v)$. By definition, the predecessor of $v$ does lie in $U$, and so we reach a contradiction.
Proof by induction: we show that all vertices reachable from $s$ are in $U$, by induction on their distance from $s$.

The two proofs are equivalent. I prefer the second.


How to generate all possible test cases of length $n$ for comparison sorts

Yes, there is an algorithm to generate all the possible test cases with length equal to $n$ and only them, significantly faster than the naive brute force algorithm would do.

Firstly, let's sort the numbers of each testcase you provided with length equal to 3 in ascending order and list only the different testcases that we get as result.

[0, 0, 0]
[0, 0, 1]
[0, 1, 1]
[0, 1, 2]

There are $4 = 2^2 = 2^{3 - 1}$ results. Note that the first value always has to be zero and while we move to the left within a specific testcase we can keep the previous value or increase it by one. So the number of different sorted testcases of length $n$ is $2^{n - 1}$. You can produce these sorted testcases by using a binary array whose value is initially zero and it's increased by one after each step.

After creating the sorted testcases you would like to have all the permutations of each one of them. Note that the number of permutations of a testcase is lower than $n!$ for all testcases except one (the $[1, 2, 3, \dots, n]$). Also note that the permutations of the different sorted testcases do not overlap. There is a built-in function in C++ which can create these permutations efficiently, named "next_permutation". The algorithm used for its implementation is nicely described on a Stack Exchange accepted answer which you can read here: std::next_permutation Implementation Explanation. I encourage you to read this description of the algorithm.

Bellow I provide you with a C++ implementation of the full algorithm that takes $n$ as input and produces all the different testcases that you want efficiently.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 105  // Assumed maximum value of n

int A[MAXN];  // The binary array used to create the sorted testcases
// Initially A is 0 (every number in it is zero)

vector<int> C;
// A vector that stores current sorted testcase and is used to obtain its permutations

int main()
{
    int n;
    cin >> n;  // Read n
    do
    {
        C.clear();  // Clear the vector C to create a new sorted testcase
        int cnt = 0;
        // cnt counts how many times we have increased the number to be inserted in the testcase
        for (int i = 0; i < n; i++)  // Create the sorted testcase of length n number by number
        {
            if (A[i]) cnt++;  // Binary array at current index shows if we should increase the number
            C.push_back(cnt);  // Put the current number in the end of the current sorted testcase
        }

        // Output all permutations of the current testcase
        do
        {
            for (int i = 0; i < n; i++) cout << C[i] << ' ';
            cout << '\n';
        } while (next_permutation(C.begin(), C.begin() + n));  // Continue while there are unprinted permutations

        // Increase binary array by one
        A[n - 1]++;  // We add one at the position n - 1 (least significant bit)
        int p = n - 1;
        while (p && A[p] == 2)  // We move the carry from right to left
        {
            A[p] = 0;
            A[--p]++;
        }
    } while (!A[0]);  // First number of sorted testcase must be 0, so when it becomes 1 we have finished
    return(0);
}


For the "all the processes agree about the one elected leader" part:

It is a combination (conjunction) of

No more than one process can ever be declared to be the leader: $\Box (\textrm{nr} \_ \textrm{leaders} \le 1).$
Eventually a leader is elected: $\Diamond (\textrm{nr} \_ \textrm{leaders} = 1).$


How does a nondeterministic Turing machine work?

Here are several ways of thinking about non-determinism (copied from this answer).

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using configurations. A configuration is an instantaneous description of the entire state of the machine. We can define a relation $\sigma \vdash \sigma'$, where $\sigma,\sigma'$ are configurations, which holds when $\sigma$ can lead to $\sigma'$ in one step. In a deterministic machine, there is at most one $\sigma'$ per each $\sigma$, whereas in a nondeterministic machine, there could be more than one. An accepting computation for a word $w$ is one which starts at the initial configuration (the tape contains $w$, the head points at the start of $w$, the state is the initial state) and ends at an accepting configuration.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are configurations and there is an edge from $\sigma$ to $\sigma'$ if $\sigma \vdash \sigma'$. An accepting computation is a path from the initial configuration to an accepting configuration.


Prove that the number of edges is at least twice the number of vertices

Hint: if you add up the degrees of all the vertices, you've counted each edge twice.


What changes do I need to make to my algorithm to make this scene from a different angle?

Can you try replacing the original condition i % j == 0 with the following conditions? They work for me.

For a perspective coming from the top right, (w-i) %j == 0
For a perspective coming from the bottom left, i %(h-j) == 0
For a perspective coming from the bottom right, (w-i) % (h-j) == 0
For a perspective coming from the the top centre, (w/2-i) % j == 0


The ratio should be bounded below by a positive constant. Equivalently, its infimum should be positive.


Can a weaker version of the Halting Problem be solved?

If you define $H$ to take a 50-or-fewer state Turing machine (TM) and an arbitrarily large input, then if you can build a universal Turing machine (UTM) in 50-states, then you can simulate $H$ by encoding its description as well as its input into the input of the 50-state UTM.

If $H$ merely needs to tell whether any 50-or-fewer state TM halts with an empty tape as input, then, since there are finitely many such TMs, it can simply have a table hard-coded into it. Producing this table may be difficult, but it "exists" in the usual mathematical sense.1 Given values of the Busy Beaver function, we can actually easily describe one potential implementation. Simply simulate the input TM up to the appropriate Busy Beaver number of steps, and if it hasn't halted by that point, then it never halts.

To give an idea of how difficult it is to produce the aforementioned table, just note that we can write a program that terminates only if ZFC set theory is inconsistent. Gödel's incompleteness theorem then implies that if ZFC is consistent, then it is not possible to prove that that program doesn't halt. The upshot of this is after a certain number of states (and not a very large number) even if you were outright given the (correct) TM to do what you describe, you could not prove that it was correct in ZFC. (This isn't particular to ZFC. ZFC is just the formal system that is usually considered the "foundation" of mathematics. Other formal systems will merely have different cut-offs.) In other words, even if you were given the answer, you could not convince yourself that it was correct.

1 Actually, it exists in a stronger sense than many mathematical objects in that we can actually enumerate all the Turing machines and at some point the correct one will come up. We just won't realize it when it happens, in general.


What is the difference between ∀ and Π in the Calculus of Constructions?

I had only a quick and cursory look at the paper — so take this with great care.

It appears that $\Pi X$ is used to express dependent products as in the calculus of constructions. Instead, $\forall X$ looks more like polymorphic types in ML.

The main difference is that, if $t : \Pi x. P(x)$ then $t T : P(T)$, while if $t : \forall x. P(x)$ then $t : P(T)$. Note that the former requires an additional argument, the second does not: the polytype gets instantiated automatically. Rules $\mathit{App}$ and $\mathit{Inst}$ at page 7 cause this difference.

Of course, this also means that introducing $\Pi$ requires a lambda, while introducing $\forall$ does not.

There also is some type / kind distinction related to this, but I can't comment on that precisely.


Sampling from a set of numbers with a fixed sum

You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have
$$
\mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\sqrt{n}},
\quad
\mathbb{E}[b_ix_i\cdot b_jx_j] = \frac{\sqrt{n}(\sqrt{n}-1)}{n(n-1)}x_ix_j = (1-O(1/\sqrt{n}))\frac{x_ix_j}{n}.
$$
Therefore
$$
\mathbb{E}[y^2]=\sum_i \frac{x_i^2}{\sqrt{n}}+\frac{1-O(1/\sqrt{n})}{n}\sum_{i \neq j} x_ix_j \leq \frac{(x_1+\cdots+x_n)^2}{n} + \frac{\sum_i x_i^2}{\sqrt{n}}.
$$
This shows that
$$
\mathbb{V}[y] \leq n + \frac{\sum_i x_i^2}{\sqrt{n}} - (\sqrt{n})^2 = \frac{\sum_i x_i^2}{\sqrt{n}}.
$$
The error in this estimate is quite small. The quantity $\sum_i x_i^2$ is maximized when $x_i = n$ for some $i$, and we conclude that $\mathbb{V}[y] \leq n^{3/2}$. This is of course not very helpful, if you are trying to use Chebyshev's inequality!

A cheap way out is to "filter out" all elements which are at least, say, $n^{1/2+\epsilon}$. There are at most $n^{1/2-\epsilon}$ of these, and so it is very likely that the sample contains none of them. This allows us to essentially assume that all $x_i$ are at most $n^{1/2+\epsilon}$, and so
$$\sum_i x_i^2 \leq \left(\sum_i x_i\right) \max_i x_i \leq n^{3/2+\epsilon}.$$
This shows that the "effective" variance is at most $n^{1+\epsilon}$, and so with high probability the deviation from the mean is at most, say, $n^{1/2+2\epsilon}$.

You can probably get better bounds with improved technology, but this bound is already pretty reasonable. When $x_1 = n$, you are always within distance at least $\sqrt{n}$ from the mean.


CFG for palindromes containing atleast 3 c's

You have a symbol S that needs to generate a palindrome with at least 3 c's.
Create a symbol X that needs to generate a palindrome with at least 1 c, and a symbol Y that needs to generate a palindrome with no requirement for c's.

S -> aSa | bSb | cXc
X -> aXa | bXb | cYc | c
Y -> aYa | bYb | cYc | a | b | c | eps

I think the essential step was not to start writing down productions, but to write down which different symbols you need to produce which kinds of output. The productions are then trivial.


Is SAT sparse? Is this an understood problem?

SAT is not sparse. For example, we have exponentially many monotone formulas per input length, and they are all satisfiable.

Regarding your second question, since most people conjecture that P≠NP, according to Mahaney's theorem those people don't expect NP-complete problems to be reducible to sparse languages.


A linear time algorithm to find the array of indices of bigger numbers

Let $A$ be an array with indizes $1$ to $n$.
We first build the array $B$ where $B[i] = j$ indicates that index $j$ has the highest value $A[j]$ in the first $i$ entries of $A$.
Then we build a list $L$ which has the numbers from $B$ in the same order but without duplicates in it.
Then we define the function $f$ as $f(i) = L[i+1]$ or none if $L[i+1]$ does not exist.
The final result is applying $f$ to $B$.

Let's look again at your example $A = [4,6,2,3,1,7,5]$.
Then $B = [1,2,2,2,2,6,6]$ and $L = [1,2,6]$.
Hence the function $f$ is $1 \mapsto 2, 2 \mapsto 6, 6\mapsto \textrm{none}$.
Applying $f$ to $B$ gives us $[2,6,6,6,6,\textrm{none},\textrm{none}]$.

Computing $B$ and $L$ runs clearly in linear time (for $L$ we only need to append values to a list at its end).
Applying $f$ takes linear time too, if done correctly:
Either you have an look up table as array of length $n$ (or hash map if you're ok with expected worst-case analysis).
Or you use the monotonicity of $B$ and use the list $L$ which you traverse in lock-step when traversing $B$.
This approach has the benefit that it uses less space in some instances and cache efficiency may be better since the relevant information is stored next to each other in consecutive order (worst case is still $n$).


Are all languages generate by Turing machines countable?

Yes. All languages, not only those generated by Turing machines, are countable. This is because they are all subsets of $\Sigma^*$, and $\Sigma^*$ itself is countable. However, there are uncountably many languages.


Do there exist "O(1)-complete" problems?

Since reading the input is necessary for almost all problems, we need at least $\Omega(n)$ time for nearly all problems, where $n$ is the size of the input.
Therefore, you may think of the class of linear time problems, which is already defined.

However, we still do not know any $O(n)$-complete or $O(n^2)$-complete problem. The field of fine-grained complexity has some new results in this area, but the classes are problem-based (for example, APSP is equivalent to Radius, Negative Triangle, ...).


Operator-precedence grammar`s symmetrical rule

It's not the symmetry of rule 2 which is the problem (whatever you mean by symmetry). The problem is (more or less) inherent to the operator precedence algorithm.

O-P parsing was dropped from the Dragon book between the first and second editions, presumably because the authors no longer believed to be a useful parsing technique [Note 1]. So I'm quoting from the first edition, which I still have on my bookshelf for odd sentimental reasons [Note 2]. And what it says is: (p. 203)

  As a general parsing technique, operator-precedence has a number of disadvantages… since the relationship between a grammar for the language being parsed and the operator-precedence parser itself is tenuous, one cannot always be sure the parser accepts exactly the desired language.

And that's the case. Operator-precedence grammars tend to accept a superset of the desired language, and you need to augment them with a number of checks to ensure that invalid sentences like the one you threw at your parser don't actually get recognized.

The classic O-P construction -- the one I think you are referring to with your use of $First$ and $Last$ -- has two problems, one inherent to O-P parsing and the other which can be (mostly) avoided. The first problem is that all non-terminals look the same to an operator-precedence grammar. That's the essence of the O-P parsing technique, so there's not much that can be done about it. The other problem is that $First$ (and $Last$) don't even distinguish between the presence and absence of a non-terminal. For this reason, $First(O)$ (not to be confused the the $LL$ algorithm's $FIRST_k$ function) includes $\fbox{+}$, and $First(C)$ includes $\fbox{<}$. In both cases, the terminal would not be in the $LL$ $FIRST$ set, because it does not appear exactly at the beginning of the right-hand side, but rather  immediately following the non-terminal at the beginning.

Given that the $First$ function can't distinguish between terminals which follow non-terminals and terminals which just start a production, it is hardly surprising that the parser doesn't really care whether or not $\fbox{<}$ has an argument. Regardless of whether there is an expression before the $\fbox{<}$ or not, the grammar simply sees that $\fbox{if} \lessdot \fbox{<}$. And consequently, it doesn't complain when the two tokens are consecutive.

Now, in theory, the O-P parser uses precedence relations only to find a possible handle. Once it does so, the parser should find the grammar rule for which the handle is the right-hand side, if any, or throw an error. But I've rarely seen a description of O-P parsing which actually does that. Instead, the simplifying assumption is made that you can figure out which rule to reduce with by just looking at the last terminal on the stack, and that the input is correct [Note 3].

It's actually pretty easy to extend O-P to get around this problem. The basic idea is to divide the relations into two classes: those which apply to adjacent terminals, and those which apply to terminals separated by a single-non-terminal. (Since the grammar is an operator grammar, those are the only two possibilities.) I refer to these as 0- and 1-superscripted relations, where the number refers to the number of intervening non-terminals.

To compute these relations, we start by compute two groups of $First$ and $Last$ sets, using the same subscript notation. So $First^0(N)$ is the set of terminals which immediately start a right-hand side of $N$, and $First^1(N)$ is the set of terminals which immediately follow a non-terminal which immediately starts a right-hand side.These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix, but their union is the classic $First(N)$ set.

More precisely, using the standard convention that lower-case letters $a$, $b$, $c$… represent terminals, upper-case letters $A$, $B$, $C$… represent non-terminals while $P$, $Q$… represent productions, and greek letters $\alpha$, $\beta$, $\gamma$… represent possibly-empty sequences of grammar symbols, either terminals or non-terminals, we define:

$$First^0(N) = \{ a : N \Rightarrow^*  a\beta \}$$
$$First^1(N) = \{ a : N \Rightarrow^*  B a\beta \}$$
$$Last^0(N) = \{ a : N \Rightarrow^*  \beta a\}$$
$$Last^1(N) = \{ a : N \Rightarrow^*  a\beta aB\}$$
Correspondingly, we define two of each precedence relationship.

$$a \lessdot^0 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^0(B)$$
$$a \lessdot^1 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^1(B)$$
$$a \gtrdot^0 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^0(A)$$
$$a \gtrdot^1 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^1(A)$$
$$a \doteq^0 b \iff \exists N : N \to \alpha a b \beta$$
$$a \doteq^1 b \iff \exists N,X : N \to \alpha a X b \beta$$
For each production $N \to \alpha A x \beta$, add $Last_0(A) \gtrdot_0 x$ and $Last_1(A) \gtrdot_1 x$

To parse, we use essentially the standard algorithm taking account of the presence or absence of non-terminals. Conceptually, we store both terminals and non-terminals on the stack. (In practice, I would keep separate stacks and use a flag on the terminal to indicate whether it has a non-terminal on top of it or not -- there can only be one, because it is an operator grammar.) At each step, we compare the incoming terminal with the topmost terminal on the stack. If the actual top of the stack is a non-terminal, we use the 1-superscripted relations; otherwise, we use the 0-superscripted relations. As before, if no relation exists between the two terminals an error is signalled (and that will catch your error).

Now, to assist with the identification of the production corresponding to the handle, we can store a little bit more information on the stack. When we push a terminal onto the stack, it is either because there was a $\lessdot$ relation with the previous stacked terminal, in which case we are starting a right-hand side, or there was a $\doteq$ relation with the previous terminal, which must be part of the same right-hand side. In either case, we can record the prefix of the appropriate RHS (up to the curren point) instead of the terminal. That has two advantages.

it lets us distinguish between prefix and infix operators in a natural way; and
it really lets us assign them different precedences, because we can actually define the precedence relations as relations between RHS location and incoming terminal, instead of terminal and incoming terminal, thereby allowing a bit more discrimination. (That's needed to give unary minus tighter binding.)

Now before you rush out and start coding a parser generator based on this idea, please re-read [Note 1], because at this point we are 90% of the way to rediscovering $LR$ parsing. I really believe that if you follow this algorithm closely, you will gain some useful intuitions for understanding $LR$ parsing. And it should be obvious that it is only a small step between "extended" O-P parsing and a table-driven $LALR(1)$ parser, at which point you might as well haul out bison or some other yacc-derivative and let it build your parser for you. [Note 4]

Notes

Personally, I would have dropped LL-parsing, but who am I to judge :) It's not that O-P parsing is at all useful once the LALR(1) construction algorithm is known. It isn't, and the problem you're having is a case in point. Any language parseable by O-P can be parsed correctly and unambiguously with LALR(1), and with the same computational complexity. (Indeed, with essentially the same amount of time and space.) The only reason to keep O-P hanging around at all is that (again, in my opinion), thinking about O-P parsing will (if you think about it the right way) lead you to the key insights which lead to LR parsing.
I like the cover.
In practice, there is another classic problem with O-P parsing, which was mentioned in the text I replaced with an … in the Dragon book quote: the algorithm as described can't distinguish between prefix and infix uses of $\fbox{-}$. The usual hack used to fix that problem is to use a small state machine (two states, typically) which is sufficient to reveal whether or not an operator was preceded by an operand. That's also sufficient to throw an error if an operator cannot be used as a prefix operator, so practical O-P parsers don't really have a problem. A while back, I described such an algorithm in a StackOverflow answer
I'm sure I'm not the first person to have thought up this idea, in several decades of very clever people thinking about parsing algorithms, but I haven't ever seen it described anywhere. As I said, I worked it out while I was trying to grasp the mechanics of bottom-up parsing, and afterwards it seemed a bit redundant. But if anyone passing by happens to know a literature reference, I'd appreciate a pointer.