Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

I checked an older edition of Sudkamp, and it had the same example. Actually the expression is $c^*(b\cup ac^*)^*$, which has a different bracketing.
Your $(ac)^*$ specifies strings of the form $acac\dots ac$, whereas Sudkamp has $ac^*$ which means strings like $acc\dots c$.

It follows the arguments of the answer by Raphael, but backwards. Any sequence of $c$'s is either at the beginning of the string, or else it cannot be preceeded by $b$ because there is an explicit $a$ in the expressing.


Color coding to get an FPT algoirthm for $k$ disjoint triangles

No, this is not correct.

As a counterexample, suppose we have a graph consisting of a central triangle, together with 3 outer triangles, such that each outer triangle is joined to the central triangle by one shared vertex (i.e., each vertex of the central triangle is identified with one vertex of one of the outer triangles).

Clearly, a solution for $k=3$ would take the three outer triangles and not take the inner triangle.

Assume the random coloring assigns a distinct color to every vertex (otherwise there is no colorful solution).

If your greedy algorithm considers the central triangle first it will always take it, but this is incorrect.


How to find an array of probabilities that give equal products

Let the array be $a_1,\ldots,a_n$, which we assume are positive. The condition $a_i x_i = a_j x_j$ implies that
$$ x_i = \frac{a_n}{a_i} x_n. $$
Since the $x_i$ must sum to $1$,
$$
1 = \sum_{i=1}^n \frac{a_n}{a_i} x_n \Longrightarrow x_n = \frac{\frac{1}{a_n}}{\sum_{i=1}^n \frac{1}{a_i}}.
$$
The formula for $x_i$ shows that
$$
x_j = \frac{\frac{1}{a_j}}{\sum_{i=i}^n \frac{1}{a_i}}.
$$


PDA for a language where the second part is not the reverse of the first part

This answer is for the original version of the question, in which "$k$" was missing.
Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.


Regular expression for containing 010 as a subword

In the first one, L1 = (a+b)*(aa+bb)(a+b)* not (a+b)(aa+bb)(a+b)* because in the second one, it is possible only to have one character of a or b and then we have to find the occurrence we need. Your L1 denies any word that does start with (aa+bb). It also forces all the words to start with a or b.

By the way, I use + for | and ∪.

So for the second one, it is in the same manner:

L1 = (0+1)*(010)(0+1)*

010 might occurs in the beginning, the middle or the end of the word.


Standard dynamic programming approaches are likely not going to work for this problem, because the extra "this or that but not both" constraints destroy the overlapping subproblems property. So let's break out the sledgehammer.
You can easily encode this as a 0-1 integer linear programming problem and use an off-the-shelf solver. For the given example (and some maximum weight limit $W$), a suitable 0-1 ILP problem is:
maximize $20A + 80B + 30C + 70D + 50E$
subject to
$A, B, C, D, E \in \{0, 1\}$
$10A + 50B + 20C + 30D + 50E \le W$
$A + B \le 1$
$C + E \le 1$
$A + D \le 1$
Although, it is not obvious to me that an integer linear programming solver will take full advantage of the structure of the problem. So perhaps a more specialized solution may perform better in practice.


Fastest way to find natural solutions to Linear equation

We can write $N$ as a linear combination of $a$ and $b$ if and only if $N$ is a multiple of $d=\gcd(a,b)$. Using the extended Euclidean algorithm we can find integers $x,y$ such that $ax+by=d$ and this in turn yields a solution of the form $\frac{N}{d}(ax+by)=N$. Now $\frac{Nx}{d}$ and $\frac{Ny}{d}$ will not necessarily be positive.

However, for all integer $k$, $a\frac{Nx+bk}{d}+b\frac{Ny-ak}{d}=N$ will also be a solution. To determine whether the equation has any natural solutions, we must simply determine the range of $k$ for which $Nx+bk$ is positive and the range for which $Nx-ak$ is positive and determine whether the ranges overlap.

In the case with 3 unknowns, $ax_1+bx_2+cx_3=N$, note that $bx_2+cx_3$ will always be a multiple of $\gcd(b,c)$. The problem thus comes down to solving $ax+y\gcd(b,c)=N$, picking an appropriate solution to that problem, and then solving $bx_2+cx_3=y\gcd(b,c)$. However it is not clear to me how to pick $y$ so that the second problem can be solved.


Efficient algorithm to find vertex with paths to every other vertex

You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.


When scheduling intervals across multiple resources, why sort?

Why sorting? One reason is efficiency: the algorithm can easily be improved to run in time $O(nd + n \log n)$ instead of $O(n^2)$. The other reason is that it is not immediately clear (at least not to me) what label to assign to intervals when processing them out of order: you may get yourself stuck later on.

Here is why it's faster: By iterating over the intervals in order of increasing start time, we can limit the inner for-loop to d iterations. Since all intervals that precede I_j have already been considered in an iteration of the outer for-loop before the current iteration, we know these intervals are already 'scheduled': they have a label assigned to them. Since there are only d labels, there are only d intervals (namely the latest for each label) that can possibly overlap with I_j. The inner for-loop only needs to look at these d intervals for each iteration of the outer for-loop, resulting in a total running time of $O(nd)$ after sorting ($O(n \log n)$ time).

The line For each interval I_i that precedes I_j in sorted order and overlaps it does not clearly capture this. Instead the algorithm should keep track of the set of intervals containing for each label the most recently encountered interval labelled as such. The inner for-loop should iterate over this set, containing only $d$ intervals.
Your second algorithm in it's current form is not correct, in that it does not always find an optimal solution. Consider the three intervals $\{(1,2),(3,4),(1,4)\}$ which can be partitioned in two sets of pairwise disjoint intervals: $\{(1,2),(3,4)\}$ and $\{(1,4)\}$, i.e. the algorithm should find a label for all intervals when $d=2$. When your second algorithm takes these intervals in order $\langle(1,2),(3,4),(1,4)\rangle$ it may do the following:

For interval $(1,2)$ labels 1 and 2 are available (none of the preceding intervals overlap, because there are no preceding intervals). We choose label 1.
For interval $(3,4)$ labels 1 and 2 are available (none of the preceding intervals ($\{(1,2)\}$) overlap). We choose label 2.
For interval $(1,4)$ all preceding intervals overlap, no labels are available. The algorithm fails to label this interval.


Prove that there is a path of lenght k+1 in a graph with minimum degree k

Hint. Build up the path, using the minimum degree condition to show that you can extend it as much as you need to.


Does an array count as a primitive operation when it is used as an argument in a function call?

As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...

  Simple operations (+, -, call, return, etc.) take one time step.
  Loops and subroutines are not simple operations: they may involve many of them.
  Memory accesses (e.g., indexing into an array) take one time step.

... you counted correctly operations [1-4] and 7. As for operation 5, it depends: the subroutine call does count as one single-step operation (according to assumption 1), but the subroutine itself doesn't: it is a composite operation (according to assumption 2). Finally, I would not consider passing A as a parameter to be an operation: A affects running time when it is accessed within the Sum subroutine, not in the subroutine call.


How to reduce Untyped λ-Calculus to Normal Form?

EDIT: Thanks to @ljedrz Comment.

  Before doing the reduction is worth noting that:
  $$ (\lambda n f x . n ~ f (f ~ x)) = (\lambda n f x .((n f) (f ~ x))) $$
  This is a convention, the parenthesis always associate to the left

It can be reduced further, but I advise you to change the second expression to an $\alpha$-equivalent one.

$$ \Big(\big(\lambda n f x . (n ~ f) (f ~ x) \big) ~ (\lambda h y . y) \Big) $$

This might not be necessary in this specific problem, but might also save you some headache later trying to keep track if some free variables got captured.

\begin{align*}
\Big(\big(\lambda \color{red}{n} f x . \color{red}{n} ~ f (f ~ x)\big) ~ \color{red}{(\lambda h y . y)} \Big) &\rightarrow_\beta \big[n ~ / ~(\lambda h y . y)\big] \big(\lambda f x . n ~ f (f ~ x)\big)\\
 &\rightarrow_{\alpha} \big( \lambda f x. (\lambda h y. y) ~ f ~ (f~x) \big)\\
\Big( \lambda f x. \big((\lambda \color{red}{h} y. y) ~ \color{red}{f}\big) ~ (f~x) \Big) &\rightarrow_{\beta} \Big(\lambda f x.\big[h ~ / ~ f \big]\big(\lambda y.y\big) ~ (f ~ x) \Big)\\
\Big( \lambda f x. ((\lambda y. y)) ~ (f~x) \Big) &\rightarrow_{\beta} \Big(\lambda f x.\big[y ~ / ~ (f ~ x)\big]y\Big)\\
 &\rightarrow_{\alpha} \Big(\lambda f x. (f ~ x) \Big)
\end{align*}

Which cannot be reduced further.


There is no induction needed. There is only one transition reaching the final state $q_2$, namely $q_1 \xrightarrow{b} q_2$. Furthermore, every transition reaching $q_1$ is labelled by $a$. It follows that every word accepted by the automaton has to end by $ab$. It remains to prove that, conversely, any word of the form $uab$ is accepted. After reading $u$ from the initial state $q_0$, you reach one of the three states $q_0$, $q_1$ or $q_2$. It suffices now to observe that $q_0 \xrightarrow{ab} q_2$, $q_1 \xrightarrow{ab} q_2$ and $q_2 \xrightarrow{ab} q_2$. Thus $q_0 \xrightarrow{uab} q_2$ in all cases, which means that $uab$ is accepted.


Finding the Shortest Path that connects k nodes in a graph

The state of a traversal at any point will be (a) the node you're currently at, and (b) the subset of the $k$ selected nodes you've already passed through.  Thus, you can solve this problem by constructing a new graph $G'$ that is $2^k$ times as large as the original graph $G$, and then finding the shortest path in $G'$.

In particular, each vertex of $G'$ has the form $(v,S)$ where $v \in V$ and $S$ is a subset of the $k$ selected nodes; for each edge $v \to w$ in the original graph, $G$' has the edge $(v,S) \to (w,S)$ (if $w$ is not one of the selected $k$) or $(v,S) \to (w,S\cup \{w\})$ (if $w$ is one of the selected $k$).

Unfortunately the running time of this algorithm is exponential in $k$.  I don't expect there to be a polynomial-time solution; David Richerby explains why not.


Comparing the big-$O$ of these four functions

One useful technique for comparing functions asymptotically is to take their logs since doing that turns exponentials into polynomials. So, if you are comfortable with comparing polynomials, then taking logs is always something you should be thinking about.
There is one thing that you have to be careful of when you do that, however. After taking logs, you can not throw away constant factors anymore.
If you take the logs of your functions, you get $\log(f_1(n))=\sqrt{n}\log(n)$, $\log(f_2(n))=n\log(2)$ and $\log(f_3(n))= 100\log(n)+\frac{n}{2}\log(2)$. So, $f_2$ is asymptotically larger than $f_3$ which, in turn is asymptotically larger than $f_1$. You already know where $f_4$ goes.


Sum of divisors summatory function with Erathosthenes' sieve

This isn't really computer science...

You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a table s where you store the sum of divisors for all 1 ≤ j ≤ k, for k = 1 to M. That's easy, $s_0 = 0$, $s_{k+1} = s_k + d_{k+1}$. And then f (L, R) = $s_R - s_{L-1}$.

The first table is the problem. You handle this in $O (n \log n)$. And you only need a factor two, you say...

You will have an array d with 5 million entries, likely 4 byte per entry = 20 Megabyte. On a typical processor that you would have in your home computer, 20 Megabyte doesn't fit into any cache. And your code does lots of accesses to elements of that array in quasi random order. For each potential divisor k, you visit all numbers that are divisible by k, and increase the sum of divisors by k.

Let's do that with fewer visits: When you visit j which is divisible by k, add the two divisors k and j/k. But when you do that, start with $j = k^2$, adding only k (because k = j / k, and you don't want to count the divisor twice), and then add k and j / k for further j. You don't need to divide, because j / k will equal k+1, k+2, k+3 etc. We initialise the array for the case k = 1, that is setting A [j] = 1 + j / 1 for j ≥ 2.

A [1] = 1
for (j = 2; j ≤ M; j += 1)
    A [j] = 1 + j

for (k = 2; k*k ≤ M; k += 1)
    j = k*k
    A [j] += k
    j += k
    s = k + (k + 1)
    while j ≤ M
        A [j] += s
        j += k
        s += 1 // s equals k + j / k

You don't save operations. However, you are now accessing the array A in a much more regular pattern, so this will save you time because access to the items will be faster. j will be smaller, making the number of iterations for each j larger, which will make branch prediction work better.

For more improvement, you would find out how many array items fit into the processor cache in your computer, then perform the whole code for subranges of the array only (for example changing only A [0] to A [99999], then changing A [100000] to A [199999], and so on). That way, most memory accesses will only access cache memory, which might be substantially faster.

You are doing N lookups in a table of size M. If M is substantially larger than N, then you should probably think about approaches that don't build this table, and that may be a lot slower per lookup, but faster overall due to the small number of lookups. Even in the case here where N ≤ 100,000 and M = 5,000,000, you might for example not count divisors 1, 2, 3, 4, j/1, j/2, j/3, j/4 in the table (which makes it a bit faster to build), and handle that during the lookup.

Or you could add the sum of the divisors for odd numbers only, then calculate the sum of divisors for even numbers (if the sum of the divisors of an odd k is s, then the sum for 2k is 3s, for 4k it is 7s, for 8k it is 15s etc), which would save almost a factor 2.

PS. I measured it... making the algorithm for counting all sums of divisors more cache friendly by adding both j and k/j doubled the speed. Calculating the sum of divisors for odd k first, then calculating even k from the odd values, makes it a total of 7 times faster. Obviously all just constant factors.


Why do we use the number of compares to measure the time complexity when compare is quite cheap?

Sure.  But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about.  This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running time.

Also, there are some situations where we use sorting algorithms where each comparison is much slower than the other operations.  A comparison may be slower than the other operations, because conditional branches can be very slow on modern processors (each comparison may have a significant chance to cause pipeline flushes).  And if you are sorting complex objects with a custom comparison function, then each comparison might take many instructions.  So, in at least some cases, the number of comparisons might well dominate the over time it takes to sort the input.

Finally, there are certainly some cases we do take into account the time to perform other operations.  It's most common to only count the number of comparisons, but by no means universal.  In situations where the time taken for other operations is important, people do analyze the total running time.

Ultimately, asymptotic running time analysis is only a theoretical model.  It is a simplified model that omits many considerations.  Any such simplification will necessarily ignore many factors.  As long as those factors are unimportant, this can be useful, as it helps you simplify the problem enough to analyze it and gain insight.  But, as always, if one of those factors turns out to have a significant effect and you didn't include it in your model, then the model will yield misleading results -- this is true of all models, and is not limited to sorting or algorithmic analysis.  Part of the art of modelling is identifying which factors dominate and which factors are second-order, so that you can choose a model that's only as complex as needed -- it is as simple as possible, so you can understand it better, but no simpler than that, so it still yields predictions that are reasonably representative of the real world.


Proving this language is not context free using the pumping lemma

Here in the notation of the language superscript $R$ is not a number; you cannot choose it to be a length $m$.

Instead $R$ usually denotes the operation of "mirror image" which inverts a string: $(abbaa)^R = aabba$.

Now start rereading your notes on the Pumping Lemma.


Is there a polynomial time algorithm for this decision problem?

This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$).  Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.


Yes, this is called the Product Constuction - given DFAs $M_1$ and $M_2$, we can construct $M=M_1\times M_2$:

$M$ consists of pairs of states from its constituent DFAs, so if the original DFAs
have states $A,B,C$ and $x,y,z$, the product would be $\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\}$.
The transition function is updated such that if on a particular step, a string would cause $M_1$ to transition from state $A$ to $B$ and $M_2$ to transition from $x$ to $y$, then the product would transition from $Ax$ to $By$
The initial state is the pair consisting of the initial states of the constituent DFAs (i.e. $Ax$).
If we are constructing the DFA that determines whether both of
the two constituent DFAs would accept the string, then the accept
states of $M$ is the intersection (those pairs made up of accept states from both).
If we are constructing the DFA that determines whether either of the two
constituent DFAs would accept the string, then the accept states of
$M$ is the union  (those pairs made up of accept states from either).
In your example, $x_1$ and $y_0$ are the accept states of $M_1$ and $M_2$; the intersection would be $\{x_1y_0\}$ while the union would be $\{x_1y_0,x_1y_1,x_0y_0\}$.

I’ve included some other DFAs regarding restrictions on length for reference.


You have 8 options:

T F F

T T F

T T T

F T T

F F T

F F F

T F T

F T F

When the first column is x1 the second is x2 and the third x3

Lets try each one:
(T or T or T)and(T or F)and(F or T)=T and T and T=T

(T or F or T)and(T or T)and(F or F)=F
And so on...

You can continue from here and you will get the right answer


How many possible ways to go right and up in an array

You can treat this problem as a combinatorics problem: How many ways are there to reach from $(0,0)$ to $(m,n)$?.

Your steps are either $\mathit{up}$ denoted by $1$ for clarity, or $\mathit{right}$, denoted by $0$

No matter what path you take, you must move exactly $n$ times $up$ and exactly $m$ times $right$.

it means you would, in total, perform $m+n$ moves

Since any move is essentially either $1$ or $0$, it can be reduced to the following questions: Given a sequence of moves $P$ of length $m+n$, how many such options are there for such a $P$ in which #$1=n$, #$0=m$ ?

Solution:

  $$\binom{n+m}{n} = \binom{n+m}{m} $$


An upper bound on the first question is $k\leq 15$: Take a set of $5$ $a$s $A=\{a_1,\dots,a_5\}$, $5$ $b$s $B_1=\{b_1,\dots,b_5\}$ and $5$ $c$s $C_1=\{c_1,\dots,c_5\}$. We know that at most 2 of the $a$s don't have a neighbor among the $B$s, otherwise we found a complement of a $K_{3,3}$, which is forbidden. The same holds for $a$s and $c$s. Thus there must be one $a_1'$ that has a neighbor among both sets. We call these neighbors $b_1'$ and $c_1'$ respectively.

We now fix the set $A$ and consider $10$ additional pairs of sets of $b$s and $c$s $(B_i,C_i)_{i\in\{2,\dots,11\}}$ with
$$B_i=\{b_{i+4}\}\cup(B_{i-1}\setminus \{b_{i-1}'\})$$ and
$$C_i=\{c_{i+4}\}\cup(C_{i-1}\setminus \{c_{i-1}'\})$$
and choose $b_i'$ and $c_i'$ such that they're both neighbors of the same $a_i' \in A$ (which all exist by the observation above).

Now at least $3$  pairs of sets agree on the same $a$ by the pigeonhole principle, i.e. there is an $a_l\in A$ and pairwise different $m_1,m_2,m_3 \in \{1,\dots,11\}$ such that $a_l = a_{m_1}' = a_{m_2}' = a_{m_3}'$.
Now $b_{m_p}'$ and $c_{m_p}'$ are neighbors of $a_l$ for $p\in\{1,\dots,3\}$. Thus for some $p,p'\in \{1,2,3\}$ the set $\{a_l,b_{m_p}',c_{m_{p'}}'\}$ induces a triangle of friends.


Starting with a vague definition of algorithm, you won't get a clear-cut answer. Here are two possible ways to look at it.

Algorithms are high-level constructs, that is we distinguish idea from implementation. In that sense,

for ( i=1; i<n; i++ ) {
  print i
}

and

i = 1
while ( i < n ) {
  print i
  i++
}

are implementations of the same algorithm, but clearly not the same program. And while this simple example may actually translate to the same machine code for many real languages, it's clear that they don't have to. So whether the programs create the same sequence of states depends on your machine model.

This is a hint that tying your notion of algorithm to a specific machine model is probably not useful.
Algorithms are specific sequences of instructions for fixed machine models. Then, the answer depends on your machine model.

If there is exactly one statement for every possible state change, then
a sequence of states induces a unique sequence of statements. Hence, if
all inputs cause identical state sequences, the algorithms/programs are
the same.
If multiple statements can cause the same state change, then the opposite is true.


Efficiently count frequency of n-grams at start of words

There is a 11.881.376 times faster method. Instead of for every 5-gram looping over the entire dictionary, loop over the dictionary once, and for every word determine with what 5-gram it starts and then increment the counter for that particular 5-gram.


In Coq, what does it mean to have an inductive type where the right-hand side of ":" is Prop?

Inductive types are similar to Haskell's data, but they are more general.

An inductive definition in Set describes a way to build a piece of data from smaller pieces. For example, the following definition defines a type called prod which allows taking two pieces of data and bundling them together.

Inductive prod (A B : Set) : Set :=  pair : A -> B -> prod A B.

(This definition exists in the standard library — with Type rather than Set, but I won't get into that distinction in my answer.) In English, given two data types A and B, and given a value a of type A and a value b of type B, I can build the value pair a b which has the type prod A B. (In the standard library, there's syntactic sugar for this: (a, b) : A * B.) And this is the only way to build a value of the type prod A B: given a value of this type, I can extract the two values that make it up (the primitive syntax for that is pattern matching, both in Haskell and in Coq).

You could take the same definition, but with A and B in Prop, and construct a type in Prop.

Inductive pprod (A B : Prop) : Prop :=  ppair : A -> B -> pprod A B.

What does this mean? Let's go through the English explanation above, applying the Curry-Howard correspondence: types become propositions, and values become proofs. So, given two propositions A and B, and given a proof a of the proposition A and a proof b of the proposition B, I can build a proof ppair a b which has the type pprod A B. And this is the only way to build a proof of pprod A B.

To build a proof of pprod A B, I need a proof of A and a proof of B. In other words, pprod A B is true if A and B are both true. There's a name for that: it's the conjunction of the two propositions — pprod A B is “A and B”.

Well, in the standard library, there's syntactic sugar for this: pprod is called and — the definition is

Inductive and (A B : Prop) : Prop :=  conj : A -> B -> and A B.

and there's syntactic sugar for and A B which is A /\ B.

This is pretty typical of how Coq works. In Coq, to say that something is true is to hold a proof of it. Coq implements a constructive logic, and makes that logic apparent. Every time you prove something, Coq builds the proof object and verifies that it's well-formed. It's rare to write down constructions in Prop, you'd usually let a tactic do it for you, but the objects always exist under the hood. (End a proof with Defined. instead of Qed. and run Print mytheorem to see the proof object for mytheorem. It can get big, but it's sometimes instructive to look at that for small proofs.)

I think it's instructive to look at how basic logical operators such as and, or, not and exists are defined (forall is a primitive concept). They're in the Logic library. It might not all make sense at first read, so revisit it again after you've practiced a bit.

To say that “P is true” in Coq, you build a proof of X. To show that “(A and B) is true”, you build a proof of (A and B), and you do this by building a proof of A and a proof of B. Likewise, to show that “(A or B) is true”, you build a proof of (A or B) by either building a proof of A or a proof of B (your choice, and if the proof depends on some variable, then you can pick a different side to prove depending on the value of that variable). This illustrates the relationship between constructivity and intuitionistic logic: the only way to prove A \/ B (syntactic sugar for or A B) is to either prove A or prove B, and this goes even when B is not A. If you can't manage to prove A and you can't manage to prove not A either, then you can't prove A \/ not A. The law of excluded middle does not hold. (It can be added as an axiom, but at a cost — you lose some of the advantage of constructivity.)

I don't think your definitions of Knight and Knave are particularly useful. You can prove Knight p and Knave p for any person p. The point of defining things in Prop is that they're not always true. Parametrized types in Set are often non-empty for every value of the parameters, but parametrized types in Prop are usually empty for some parameters — the parameters that make the proposition false.


Expectation for the number of leaf nodes in a randomized tree construction

I tried to define a random variable $x_i$ for a node $i$, which is $1$ if it is a leaf node and $0$ otherwise.

Then, I must find $$E(X) = \sum_i E(x_i)$$.

If $A_{ij}$ shows the event that the node $j$ is connected to the node $i$, then I must have $\bar A_{ij}$, and then $Pr[x_i = 1] = Pr[\bar A_{ii+1}].Pr[\bar A_{ii+2} | \bar A_{ii+1}]....$

$j$ must be bigger than $i$, pointing to the nodes that arrive after the node $i$. Let $j$ be $i+1$.

$$Pr[A_{ij}] = \frac{1}{j-1}$$ so $$Pr[\bar A_{ij}] = 1- \frac{1}{j-1} = \frac{j-2}{j-1}$$

The reason is that when the node $j$ arrives there are $j-1$ nodes to be attached to. Similarly:

$$Pr[\bar A_{ij+1} | \bar A_{ij}] = 1 - \frac{1}{j} = \frac{j-1}{j}$$

so

$$Pr[\bar A_{in} | \bar A_{ij} \cap \bar A_{ij+1} ... \cap \bar A_{in-1} ] = 1- \frac{1}{n-1} = \frac{n-2}{n-1}$$

So, let's multiply them to each other:

$$ Pr[x_i = 1] = \frac{j-2}{j-1} . \frac{j-1}{j} .. \frac{n-2}{n-1} $$

Since the product is telescopic, we have:

$$ Pr[x_i = 1] = \frac{j-2}{n-1} $$

By replacing $j$ with $i+1$:

$$  E(x_i) = Pr[x_i = 1] = \frac{i-1}{n-1}$$

So
$$ E(X) = \sum_{i=1}^{n}E(x_i) = \sum_{i=1}^{n}\frac{i-1}{n-1} = \frac{1}{n-1}\frac{n(n-1)}{2} = \frac{n}{2}$$


Finding missing edge weights in the context of minimum spanning tree

Firstly, to make the nice answer given by OP to Problem 1 the only valid answer, we should change its question "what are $x$ and $z$?" to "what are the maximal weights of $x$ and $z$?". Otherwise, we can have many valid answers such as "$x=3, z = 5".
Secondly, to make the nice answer given by OP to Problem 2 the only valid answer, we should change its question "What are the weights of other edges?" to "What are the minimal weights of other edges?". Otherwise, we can have many valid answers such as "$w(ED)=16, w(CD)=115$ and $w(AB)=19$".
Lastly and most importantly, let us answer the central question, "Is there some standard well defined steps for both problems? Or its more sort of trial and error work?". A standard way to rephrase the question is, "Is there an effective algorithm for both kinds of problems?"
Let $G$ be an edge-weighted connected undirected graph with some unknown weights. Let us state the questions clearly in more detail. We will assume there are graphs that satisfy the given conditions in the problems. (Otherwise, we can add extra steps to the algorithms below to detect those impossible situations).
The first kind of problem: unknown weights in an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all edges of unknown weights belong to that MST. What are the maximal values of those unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.
Pick any edge $e$ that is not that MST. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$x\leq a$" where $x$ is the unknown weight of some edge in that MST and $a$ is a known number. Repeat until we have gone through all edges that are not in that MST.
Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$x\leq a$" with the smallest number $a$ where $x$ is an unknown. Let $x=a$  be part of the answer. Repeat this process until we have no more inequalities.
The second kind of problem: unknown weights outside an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all weights of edges of the MST are known. What are the minimal values of the  unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.
Pick any edge $e$ of unknown weight. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$a\leq x$" where $x$ is the unknown weight of $e$ and $a$ is a known number. Repeat until we have gone through all such edge $e$ of unknown weight.
Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$a\leq x$" with the largest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.
More general problems?
If you have read this far, it will be obvious that we could create more general problems of similar kinds. We will have a general approach towards producing an algorithm as well. So much for my answer that is already long.


The definition of a graph's transitive reduction

If we order the vertices alphabetically, then the adjacency matrix is
$$A=\begin{pmatrix}
0&1&1&1&0\\
0&0&0&1&0\\
0&0&0&1&1\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
The adjacency matrix of the transitive closure would be
$$B=\begin{pmatrix}
0&1&1&1&1\\
0&0&0&1&1\\
0&0&0&1&1\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
To get the this one you get each row by navigate the graph starting at the node corresponding to that row and mark with a $1$ the columns of the nodes that you manage to visit and with $0$ the rest.
Now,
$$AB=\begin{pmatrix}
0&0&0&2&3\\
0&0&0&0&1\\
0&0&0&0&1\\
0&0&0&0&0\\
0&0&0&0&0
\end{pmatrix}$$
To build the adjacency matrix $C$ of the transitive reduction put a $1$ in position $(i,j)$ if the $(i,j)$ entry of $A$ is non-zero and the $(i,j)$ entry of $AB$ is zero.
So, the adjacency matrix of the transitive reduction should be
$$C=\begin{pmatrix}
0&1&1&0&0\\
0&0&0&1&0\\
0&0&0&1&0\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
So, the transitive reduction looks like this


I suggest you use a data structure for nearest neighbor search to speed up the process of finding all points in the polyline that are closer than the defined radius.  That should lead to a significant speedup.


Derandomization of an approximation algorithm for solving a linear system

In your case the method of conditional expectations devolves to a greedy algorithm. At each stage, you choose the value for the variable under consideration that satisfies the most equations (if any; otherwise choose an arbitrary value), and substitute this value.

Why does this work? Suppose that at the beginning of stage $i$, you have $N_i$ remaining equations (i.e., ones in which there is at least one remaining variable with non-zero coefficient). The greedy choice satisfies at least $(N_i-N_{i+1})/p$ equations. In total, the number of equations you satisfy is at least
$$
\sum_{i=1}^n \frac{N_i-N_{i+1}}{p} = \frac{N_1 - N_{n+1}}{p} = \frac{N}{p},
$$
where $N$ is the total number of equations, and $N_{n+1} = 0$ is the number of remaining equations at the end of the algorithm.


How to prove that Bellman-Ford algorithm detects a negative cycle?

Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists).
To prove this, we can use induction:
Clearly this holds after the first step as a path of length $1$ is just an edge connecting two vertices.
Now suppose we found minimal weight paths from $s$ to any other vertex of length $\leq k$ after the $k$-th step and we execute the $(k + 1)$-th step.
Note that any path $p_{sv}$ of length $k + 1$ from $s$ to some vertex $v$ can be formed by taking some path $p_{sw}$ of length $k$ from $s$ to a neighbor $w$ of $v$ and then appending the edge $wv$ and in particular we find that if $p_{sv}$ is of minimal weight w.r.t. all $s$-$v$-paths of length $k + 1$ then $p_{sw}$ must already be weight-minimal w.r.t. all $s$-$w$-paths of length $k$ (otherwise one could use a better path from $s$ to $w$ and adjoin $wv$ to get a path with less weight than $p_{sv}$) and the claim follows.
Now let us address your first question.
Note that any simple path (i.e. one that does not self-intersect) between any two vertices in $G$ is of length at most $|V(G)| - 1$ and conversely, any path of length $\geq |V(G)|$ must contain a cycle.
Hence, a path from $s$ to $v$ of length $|V(G)|$ (or greater) can be decomposed into three parts: some initial path segment starting at $s$ and ending at some vertex $w$, a cycle (of positive length) starting and ending at $w$ and some final path segment from $w$ to $v$ (note that the path segments need not be cycle-free themselves).
If $G$ contained no negative cycles, then the path obtained from appending the final path segment to the initial one is cannot be of larger weight than the one also containing the cycle and thus, the weight of any path containing a cycle can never be shorter than the cycle-free path obtained from cutting said cycle out in the manner I outlined and in particular, this means that the algorithm cannot improve on the paths it found in $|V(G)| - 1$ steps.
However, if at least one negative cycle exists in $G$ we can use the lemma we proved in the beginning we get that the Bellman-Ford-algorithm will find an improved path in the $|V(G)|$-th step which could not exist in a graph with no negative cycles, showing that the graph contains a negative cycle if and only if we detect such an improvement in the $|V(G)|$-th step.
The answer to your second question is negative and it is easy to construct counterexamples where arbitrarily many iterations are needed to find all vertices reachable via paths including negative cycles:
Consider the butterfly graph $B$ on the five vertices $v_1, ..., v_5$ such that both $C_1 = \{v_1, v_2, v_3\}$ and $C_3 = \{v_3, v_4, v_5\}$ are the triangles of $B$ (i.e. $v_3$ is the "center vertex" of degree 4) and set the weights such that $C_2$ forms a negative cycle of weight $-1$ while $v_1 v_2$ and $v_1 v_3$ have both weight $0$ and $v_2 v_3$ has weight $n$.
Now consider the paths from $v_1$ to $v_2$ -- using the negative cycle $n + 1$ times we are able to find a path better than the one consisting only of the edge $v_1 v_2$ but such a path has length $2 + 3 \cdot (n + 1)$ and hence by choosing $n$ to be some large enough value (really $n > 1$ suffices) and recalling our initial result we can see that the Bellman-Ford algorithm will not find that $v_2$ can be reached via a negative cycle until step $2 + 3 \cdot (n + 1)$.
Since of course every vertex in such a negative weight cycle is also one reachable via one, this also negatively answers the second part of this question.
However, note that if some vertex $v$ cannot be reached via a negative cycle from the starting vertex $s$ then the distance (in the algorithm's table) between $s$ and $v$ can only decrease at most $|V(G)| - 1$ times while for any vertex that can be reached via a negative cycle said distance can decrease arbitrarily often, so it is possible to find all such vertices eventually with some additional bookkeeping.


"Dense" regular expressions generate $\Sigma^*$?

Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is.

In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, not counting $\epsilon$ or $\emptyset$. However, $\emptyset$ can be eliminated from every expression not generating the empty language, and the expression can be "cleaned up" so that the number of $\epsilon$ it contains is at most $|\mathrm{alph}(R)|$ (Lemma on page 10 of the talk).

In page 51, for every $n \geq 3$ they construct a regular expression of size $O(n)$ over $\{0,1\}$ which generates all strings of size at most $\Omega(2^n n)$, but doesn't generate all strings. Note that "size" here is both in your sense and theirs, since we're using big-O notation. They also pose an open question to find the best dependence between the two parameters.


Traveling Salesman: how to use a lower bound?

You want a bound that depends upon the partial choices made so far.  So, I suggest you compute a bound that is based upon (1) the sum of the edges in the part you've chosen already, plus (2) a greedy bound for the remaining unvisited nodes (for each node, sum of the two least cost edges, divided by two); or something like this.  This will be different from the greedy bound applied to the entire graph, because of part (1).


Reversing topo-order of the original graph instead of the topo-order of the transposed graph?

It may work for the graph you give, but not for all graphs.  Consider a graph with 3 vertices, A, B, and C.

$A \rightarrow B, C$

$B \rightarrow A$

Search on A, exploring B before C, B finishes first but is not in a sink.

Also, note that for the Wikipedia article, the search is on incoming edges, not outgoing, which is why it doesn't need to explicitly transpose the graph.


If each pixel contains the channels for the 3 primary colours, why can a 1-bit picture only be presented in white and black?

Please read the Wikipedia article 8-bit color.

8-bit color graphics are a method of storing image information in a computer's memory or in an image file, so that each pixel is represented by one 8-bit byte. The maximum number of colors that can be displayed at any one time is 256 or 2⁸.

In other words, the problem is that 8 bits mean that all three primary colors red, green, and blue, are encoded in 8 bits in total.  From Wikipedia:

The simplest form of quantization frequently called 8-bit truecolor is to simply assign 3 bits to red, 3 to green and 2 to blue (the human eye is less sensitive to blue light) to create a 3-3-2
Bit    7  6  5  4  3  2  1  0
Data   R  R  R  G  G  G  B  B

8-bit color image, but this process is sub optimal. There could be different groupings of colors that make evenly spreading the colors out inefficient and likely to misrepresent the actual image. Because the color map doesn't need to have every color in it and just needs to accurately represent the more color dense image, an arbitrary color can be assigned to each of the 256 available color 'slots' on the map. [...]

Concluding, 1 bit means that you can have only two states, e.g. black/white.


M1 and M2 together will eventually enumerate every possible string. So the trick is to alternate between them. Then you get an enumerator that enumerates all strings. Every time you compare the output string of the enumerator to your input string. At some point they will be equal. Then you just have to look whether you have used M1 or M2 in the last step.

You compute for input string w:

M1(0)=w?, M2(0)=w?, M1(1)=w?, M2(1)=w?, M1(2)=w?, M2(2)=w?,...


In order to prove an algorithm correctness a loop invariant should include:

Initialization:It is true prior to the first iteration of the
loop.
Maintenance: If it is true before an iteration of the loop, it
remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Let's look at your invariant:
Initialization then is before entering the loop, so choose any number for $y$ or $z$ such that $y,z \in N$ (I'll use $n_1$ and $n_2$ respectively) then you will have that your property is satisfied since at this point: $d=1$, $c=0$ and $x=0$.
So your invariant will be: $(n_1 + n_2 + 0)*1 + 0 = n_1 + n_2$.
Maintenance: This one you can prove it with induction. Here a complete example with induction. Is slightly more complicated, but you can see in your case that it holds, since at every iteration you "divide" $y$ and $z$ by 2, but $d$ duplicates every time, therefore balancing the division. The $c$ is there in case of odd numbers.
Loop termination: at this point according to the while, nor $y$ nor $z$ nor $c$ can be higher than $0$, but at the same time they are all natural numbers, therefore they are all $0$. Now we have that $x = y+z$ and if you plug it into the invariant you have: $(0 + 0 + 0)*d + x = y_0 +z_0 \Rightarrow y + z = y_0 + z_0$


From my understanding, you are asking about computing the derivative, at some pixel $(x,y)$, with respect to the $x$ direction. We can approximate a derivative of some function $f(x,y)$ along the $x$ direction using the following Finite Difference formula:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+h,y) - f(x,y)}{h} $$

for some $h \neq 0$, usually using $h \ll 1$ if possible. For an image, the best you can do with this formula is the following:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+1,y) - f(x,y)}{1} = f(x+1,y) - f(x,y) $$

This is because $f(x,y)$, the pixel color values at $(x,y)$, is a value of $1$ away from the nearest neighboring pixels in both the $x$ and $y$ direction.


How can blank be written on the tape if it is not part of input alphabet?

The formal definition of a turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$, where:

$Q$ is a finite set of states.
$\Sigma$ is a finite set of input symbols (input alphabet).

$\Sigma$ does not contain the blank symbol ($\sqcup$).

$\Gamma$ is a finite set of tape symbols (tape alphabet).
$\sqcup \in \Gamma$ and $ \Sigma \subseteq \Gamma$.
$\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $ is the transition function.

$Q^\prime = Q - \{q_{\text{accept}}, q_{\text{reject}}\}$

$q_0 \in Q$ is the start state.
$q_{\text{accept}} \in Q$  is the accept state.
$q_{\text{reject}} \in Q$ is the reject state.

The part you want to pay attention to is the definition of the transition function:

  $\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $

Note that the transition function accepts inputs that are of the tape alphabet, and writes output that is also of the tape alphabet.

The turing machine is decidable only if it recognizes some language L and and halts for every input.


Shortest paths between given red vertices and arbitrary blue vertices

I assume no negative weights in this solution (since you stated Dijkstra). My solution also uses Dijkstra. Let $G'$ be the graph resulting from $G$ by contracting all the blue vertices into one vertex - which means, remove all blue vertices in the graph and add one blue vertex $b$, and for each edge between a red vertex $u$ and a blue vertex $v$, add an edge between $u$ and $b$.

Claim. A shortest path from a red vertex $u$ to a blue vertex in $G$ has the same length as a short $u$ to $b$ in $G'$.

Proof. Since the graph does not have negative weights, a shortest path can always be replaced with another shortest path with only the last vertex blue (every thing after this vertex are edges with weight 0). Now there is a one-to-one correspondence between shortest paths in both graphs, since inner-vertices on the path can be translated without change and the last edge of the path in $G$ corresponds to an artificial edge to $b$ in $G'$ with the same weight.

Now since the graph is undirected, a shortest path from $u$ to $v$ is a shortest path from $v$ to $u$ (in case of directed graphs we can do this by inverting the graph) and hence, instead of running Dijkstra for each query from a red vertex $v$, run one Dijkstra as preprocessing from $b$ and for each query vertex $v$ answer $d_{G'}(b, v)$.


Is in-place run length encoding possible in O(1) space given that the output is shorter than the input?

An $O(1)$ space algorithm that uses one extra symbol not found in $L$, which I will call $B$ for blank space.
I define an operation, a "shift right" at position $k$. It finds the next blank symbol $B$ after position $k$ , shifts all symbols one to the right, and sets position $k$ to $B$. For example a right shift at the third symbol:
abcdeBfjgB    becomes    abBcdefjgB
  ^                        ^

Similarly a "shift left" at position $k$ assumes there is a $B$ symbol there, and moves it all the way to the end of the string, shifting all other symbols left.
abBdeBfjgB    becomes    abdeBfjgBB
  ^                        ^

Note that you can perform both shifts in $O(1)$ memory.
Now, first we replace all runs of any symbol $x$  with length $l \geq  3$ or greater with $xlB^{l-2}$. This can be done in-place, and leaves such runs identifiable. Also note that these are all the runs that shortens the output compared to the input.
Then, move a single pointer $p$ from left to right:

If the string at the pointer starts with $B$, shift left.

If the string at the pointer starts with $xlB^+$, this is the start of a run with length at least 3. Increment $p$ by $2$.

If the string at the pointer starts with $xx$ replace it with $x 2$ and increment $p$ by 2. Note that $xx$ can never be the start of a run of length 3 or higher, since we already replaced those.

If the string at the pointer has form $xy$, increment $p$ by 1, shift right, and replace the resulting $B$ at $p$ with $1$. Increment $p$ by 1 again. Note that the shift right must succeed due to the guarantee the output is shorter than the input, and we already created all space possible when replacing all runs of length $3$.

If any space is left over at the end, the algorithm will eventually get stuck performing step 1. Detect this, strip the remaining space, and you are done.


What is the name of the variant of ICP where the correspondence of the points are known?

This problem is called "rigid registration", the correspondences being the "rigid" part.

As D.W. pointed out, you can do a least squares fit (or use something like RANSAC to find the correspondences and then do a least squares fit). In the absence of noise, the least squares fit has a particularly nice formulation which has been known for a long time.

If $\mathbf{x}_i$ and $\mathbf{y}_i$ are the two corresponding sets of coordinates (there are $n$ points), we want to find the rotation matrix $R$ and translation vector $\mathbf{t}$ which minimises:

$$\hbox{arg min} \frac{1}{n}\sum_i \left\Vert \mathbf{y}_i - R \mathbf{x}_i - \mathbf{t}\right\Vert^2 $$

Calculate the covariance matrix:

$$\mathbf{\mu}_x = \frac{1}{n} \sum_i \mathbf{x}_i$$
$$\mathbf{\mu}_y = \frac{1}{n} \sum_i \mathbf{y}_i$$
$$\Sigma_{xy} = \frac{1}{n} \sum_i (\mathbf{y}_i - \mathbf{\mu}_y) (\mathbf{x}_i - \mathbf{\mu}_x)^\intercal$$

Compute the singular value decomposition of the covariance matrix:

$$\Sigma_{xy} = U S V^\intercal$$

Then:

$$R = V U^\intercal$$

This algorithm can be made more robust in the presence of noise. There are also more recent algorithms which are competitive.


What, if any, is the term for a node whose children are all leaf nodes?

They are classified as nodes of height 1 by convention in the case of a rooted tree.

The height of a node $N$ is the number of edges on the longest downward simple path from $N$ to a leaf, according to Introduction to Algorithms by CLRS as well as the Wikipedia entry.

You might want to use penultimate nodes as suggested by Orlp. Please note some papers define a penultimate node slight differently on general graphs as a nonleaf node that is adjacent to a leaf node. For example, Patrolling Games.


You will reduce $P_1$ to $P_2$ if you know something "bad" about $P_1$, and you want to see if this extends to $P_2$.

It should read "If $P_1$ is non-RE, $P_2$ cannot be RE". If it is in the book, it's a typo.


Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same?

I think you're confusing two things: dependently typed languages are convenient for specifying properties and giving proofs about functional programs. The techniques you mention are possible decision procedures for certain properties of functional programs.

The ability to specify program properties usually takes place within a logic. Dependent types are a kind of logic, when viewed through the propositions-as-types lens. The nice thing about this logic is that it is naturally suited to talk about functional programs, which also can be used as a proof language. But there are other logics as well capable of doing this, and some are not based on dependent types.

Supercompilation type proofs are essentially a way to prove that two functions are observationally equal i.e. send identical inputs to outputs. But the fact that a supercompiled function $\mathrm{S}(f)$ is observationally equal to $f$ is not obvious: it has to be proven. Usually this is done with pen and paper, but of course Agda could be used for such a purpose.

Some things to note:

Agda is sufficiently powerful to prove (almost) all the program equivalences you could be interested in. The drawback is that you have to supply the proof yourself.
The things that can be proven automatically using SC or transducers are nice, but they only cover a tiny percent of what people want to prove about their functional programs. In particular, these techniques will fail with any slightly complex property (say, always returning a prime number) and even expressing the desired property may be hard (e.g. always returning a prime number).
There are a number of decision procedures for functional programs which are well-studied and offer similar or additional power as the techniques you mention. In particular ACL2 has been around for quite some time and is (I hear) quite powerful for these kinds of things.
In theory, we could integrate these kinds of procedures to help the user produce a proof in a system like Agda or Coq. There are a number of technical and social reasons for which this hasn't happened yet. There's still hope though! Note also that Coq has a fair number of automated techniques already.


What you have written (i.e., $\{ \varepsilon, 01, 0011, 000111, \ldots \}$) is simply $A$ itself.

(Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because it is not correct.

The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \{ \varepsilon \}$ and $A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \in A^i, w' \in A \}$. An inductive argument easily shows:
$$A^i = \{ w_1 \cdots w_i \mid w_1, \ldots, w_i \in A \}
= \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid n_1, \ldots, n_i \ge 0 \}$$

Since $A^\ast$ is the union over all such $A^i$, we obtain
$$A^\ast
= \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid i, n_1, \ldots, n_i \ge 0 \},$$
which is obviously not equal to $A$.


At risk of sounding like I'm avoiding the question, I claim that every reduction is a direct proof of NP-completeness, just avoiding a lot of tedious, unnecessary work.

First, let me talk a little about the proof of the Cook-Levin theorem (SAT np-completeness).

At a very high level, the cook-levin theorem proof does this:

Assume R is some problem in NP. Then, by definition, there is a nondeterministic TM $T$ that runs in $p(n)$ time and decides $R$, for $p(n)$ a polynomial.

Then, it is sufficient to show that for any $x$, we can construct in polytime a boolean formula $B$ such that $B$ is satisfiable if and only if $T$ accepts $x$ (within $p(|x|)$ steps, by assumption of $T$).

Finally, by taking the formal definition of a nondeterministic turing machine and translating it into the language of a SAT instance, we construct a formula that is true only if $T$ accepts $x$ within $p(|x|)$ steps. This is a tedious and difficult process, which you can read about here http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem#Proof

Anyways, the point of this explanation is the last paragraph: notably, that the only nontrivial part of this proof is taking the parts of a NTM and putting it in the language of a SAT instance. But, this is essentially what a reduction is!

For example, when you write a reduction from SAT to 3-coloring, what you are showing is that a SAT instance can be translated into a 3-coloring instance -- and this gives you a direct proof of np-completeness, because we already have a translation from a p(n) time NTM into a SAT instance.

So, cook-levin tells us how to make boolean formulas from an NTM, and a 3-coloring reduction tells us how to make vertices and edges from boolean formulas. Put these together, and you get a direct translation from an NTM into vertices and edges, which is exactly what you're looking for. It just happens to be tedious to deal with all the annoying little pieces of the NTM formalism, so no one likes to deal with that. It's much easier to do a reduction from SAT than a 'reduction' from NTM.


Given family of grammars, determine if LR(k)

No, of course not.  If you want to prove that some formula is true for all $n$, it is in general not enough to show that it is true for $n=2$ and $n=3$.  That's just wishful thinking.

Consider, for instance, the claim that $n^2+n+41$ is prime for all $n$.  You can check it for $n=2$ (sure enough, $2^2+2+41=47$ is prime) and $n=3$ (yup, $3^2+3+41=53$ is prime), and it'll be true for both $n=2$ and $n=3$, but that doesn't mean it's true for all $n$.  In fact, it's not true for all $n$: at $n=41$, the corresponding value is not prime (it is divisible by 41).


If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

Given $x$, define $p_1(x,y) = \Pr[O_1(x) = y]$ and $p_2(x,y) = \Pr[O_2(x) = y]$. Let
$$
\begin{align*}
\delta_x &= \sum_y [\max(p_1(x,y),p_2(x,y)) - \min(p_1(x,y),p_2(x,y))] \\
&= \sum_y |p_1(x,y) - p_2(x,y)| \\ &\leq \epsilon_1(n).
\end{align*}
$$
On the other hand,
$$
\sum_y [\max(p_1(x,y),p_2(x,y)) + \min(p_1(x,y),p_2(x,y))] = \sum_y [p_1(x,y) + p_2(x,y)] = 2.
$$
Therefore
$$
\sum_y \min(p_1(x,y),p_2(x,y)) = 1 - \frac{\delta_x}{2}.
$$
Consider now the following random process that generates two random variables $R_1,R_2$:

For every $y$, with probability $\min(p_1(x,y),p_2(x,y))$, generate $R_1=R_2=y$.
Otherwise (this happens with probability $\delta_x/2$):

For every $y$, with probability $\frac{p_1(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_1=y$.
For every $y$, with probability $\frac{p_2(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_2=y$.

This process is a coupling that generates two random variables $R_1,R_2$ with the following properties:

$R_1 \sim O_1(x)$.
$R_2 \sim O_2(x)$.
$\Pr[R_1 \neq R_2] = \delta_x \leq \epsilon_1(n)$.

Let us go back to your algorithm $A$, and suppose that it runs in time $T(n)$. Use the coupling above to generate two random variables $B_1,B_2$ with the following properties:

$B_1 \sim A^{O_1}(x)$.
$B_2 \sim A^{O_2}(x)$.
$\Pr[B_1 \neq B_2] \leq T(n) \epsilon_1(n) =: \epsilon_2(n)$.

Note that $\epsilon_2(n)$ is negligible. We have

$$
\begin{align*}
&\sum_y |\Pr[A^{O_1}(x) = y] - \Pr[A^{O_2}(x) = y]| \\ =
&\sum_y |\Pr[B_1 = y] - \Pr[B_2 = y]| \\ =
&\Pr[B_1 \neq B_2] \sum_y |\Pr[B_1=y|B_1 \neq B_2] - \Pr[B_2=y|B_1 \neq B_2]| \\ \leq
&\Pr[B_1 \neq B_2] \sum_y (\Pr[B_1=y|B_1 \neq B_2] + \Pr[B_2=y|B_1 \neq B_2]) \\ \leq &2\epsilon_2(n),
\end{align*}
$$
since given $\Pr[B_1=y|B_1=B_2] = \Pr[B_2=y|B_1=B_2]$.


Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

In this context, lexicographic order means:

First order by length.
Within each length, order lexicographically.

You're saying that the proof is incorrect, but in fact it is only inaccurate in that the order is not quite the lexicographic order. I would say that the proof has a small mistake, but is otherwise correct.

One often encounters such small issues in intricate mathematical arguments. Instead of immediately declaring failure when you run upon such a difficulty, you should try to see if the argument can be fixed by making small adjustments. You're not in a trial, acting as a prosecutor. Rather, you should believe the author that she had some valid proof in mind, but perhaps was a bit sloppy when trying to express her thoughts on paper. It's a cooperative game, in which you are trying to make the proof work rather than try to break it.


Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?

The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate.  I'm not sure where you got it from, but it's not correct.

Recursively enumerable languages are closed under union and intersection.  However, they're not closed under complement.  And, there's no way to express complement using just union and intersection.  So, the fact that they're closed under union and intersection does not imply that they're closed under complete.  There's no paradox/contradiction here.


Algorithm: How to find the number of independent sets in a tree?

Let $T$ be the tree. For every $n\in T$, we indicate the number of independent sets in the subtree of $T$ rooted in $n$ that contain $n$ with $A(n)$, and the number of independent sets that do not contain $n$ with $B(n)$.

The following recursive relations hold:

$$
\left \{
\begin{array}{r c l}
A(n) & = & \prod_{m \in Adj[n]}B(m) \\
B(n) & = & \prod_{m \in Adj[n]}A(m) +B(m)
\end{array}
\right .
$$

Notice that we are using a constant number of memoization cells for each node of $T$. Interestingly enough, if $T$ is a line tree of $k$ nodes, the answer is exactly the $k$-th Fibonacci number.


Does hiding variables work in terms of blocks or line-by-line?

It depends on the programming language.  It's up to each language to specify whether this is legal or not, and what it means.

In many languages this would be legal.  It is called variable shadowing.


Turing machine that can tell if it ends in standard position?

In most of the models of Turing Machines there is a separate blank symbol $B$. Sometimes we may even have a start symbol $\rhd$. This makes it easy to check if $M$ halts in standard position.

If $0$ is also treated as the blank symbol, and the tape is initialized with 0's on both side of inputs (with no separate blank symbol) then the analysis of computation becomes a little bit difficult (Where is the boundary?).

In your case, it is doable without much hassle as 0's in the input always occur singly. First rewrite the whole input as 2-bit alphabet, converting 0 to 10 and 1 to 11, B will be 00 and start symbol $\rhd$ will be 01. Now we are happy to go. We just need to modify the Turing Machine to consider 2 bits at a time.


Most common approach to such problems is some form of sub-sampling: randomly draw equal numbers of examples for each class. For model tuning you can use Stratified Cross-validation which in essence uses exactly this approach.

Other possibility is to weight the examples according to the ratio of class sizes. However, since on of your class has infinite number of samples this is impossible, unless you'll first employ sub-sampling anyway, at least for this infinite class. One example for decision tree context is modified information gain: "A Robust Decision Tree Algorithm for Imbalanced Data Sets" by Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla (PDF)


How are the control signals derived in the MIPS pipeline?

You are correct. The above data path doesn't have the parts that support jump instruction. Yet, those are easy to add.

The pipelined datapath in your question is based on a single-cycle MIPS that doesn't support jumps (Figure 5.21 in Patterson and Hennessy). In order to add jump support, consider the single-cycle MIPS datapath of Figure 5.24; then add the jump parts to the pipelined architecture.

However, note that jumps and branches must be treated correctly in order to avoid control hazards - specifically, new instructions that entered the pipe after the jump should not be executed. The complete datapath that takes care of control hazards (again, for branches only) appears in Figure 6.41.


How to calculate the dimension of a convex polyhedron?

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.
Implicit inequalities
The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$.
Let $a^i x \leq b_i$ for $i\in M$ be the linear inequalities that compose the system $A x\leq b$ defining $P$. An inequality $a^i x \leq b_i$ is called an implicit inequality of this system if $a^i x = b_i$ for all $x$ such that $A x\leq b$. Let $A^= x\leq b^=$ denote the subsystem of $Ax\leq b$ that consists only of the implicit inequalities in $Ax\leq b$. Now, we have the folllowing theorem:

Let $P = \{x\in \mathbb{R}^n \mid Ax\leq b\}$ be a nonempty1 polyhedron. Then, $\mathrm{aff}(P) = \{x \mid A^= x= b^=\} = \{x \mid A^= x\leq b^=\}$. Additionally, $\dim P = n - \mathrm{rank}\ A^=$.

(see Theorem 3.17 from Integer Programming by Conforti, Cornuéjols, and Zambelli. Chapter 3.8 contains additional examples for computing the dimension by hand)
So, to compute the dimension of $P$, we first find all implicit inequalities to obtain $A^=$, and then compute the rank of $A^=$. The latter is easy to do, but the first can be rather complicated to do in general (although it is often doable 'by hand' for well structured cases).
Finding implicit inequalities via linear programming
Note that an inequality $a^i x \leq b_i$ is implicit if and only if the hyperplane $a^i x = b_i$ (i.e. the 'border' of the halfspace defined by the inequality) contains $P$. We can determine whether this is the case by solving a pair of linear programs (thanks to @plop for pointing this out). The inequality $a^i x \leq b_i$ is implicit if and only if
$$\max \{a^i x \mid Ax\leq b\} = \min \{a^i x \mid Ax\leq b\} = b_i,$$
or in other words when optimizing within $P$ in the directions of $a^i$ and $-a^i$ both yields the value $b_i$.
To see why this is true, first note that if either of the results of these programs give a value other than $b_i$, we have found some $x\in P$ with $a^i x \neq b^i$, so the inequality is not implicit2.
For the other implication, any point $x'\in P$ that lies outside the hyperplane $a^i x =b_i$ lies inside the hyperplane $a^i x = b'_i$ for some $b'_i\neq b_i$. If $b'_i < b_i$, then $\min \{a^i x \mid Ax\leq b\} \leq a^i x' = b'_i < b_i$, and if $b'_i > b_i$, then $\max \{a^i x \mid Ax\leq b\} > b_i$. So at least one of the linear programs gives a value unequal to $b_i$  if $a^i x \leq b$ is not implicit.
The algorithm
So, a possible algorithm for finding the dimension of $P$ in $\mathbb{R}^n$ when given by a system of $m$ inequalities is

Solve $2m$ linear programs to find the implicit inequalities and $A^=$.
Compute the rank $r$ of $A^=$, and return $n-r$.

Linear programs can be solved in polynomial time via e.g. the interior point method (although the simplex method is much faster in practice), and the rank of a matrix can be computed in polynomial time via Gaussian elimination. So, the dimension of a polyhedron can be computed in polynomial time.
As I mentioned earlier, there are probably much better approaches than what I suggest here. The suggestions offered by @plop in the comments look promising and I recommend anyone looking for something better than what I'm suggesting here to follow them through, but I will end my answer here, it is already long enough.

(The first part of this answer is taken from these slides by Rudi Pendavingh , page 8)

1: If $P$ is empty, then its dimension is $0$. Additionally, we can test whether $P$ is empty via linear programming. So, we can and I will assume that $P$ is non-empty for the remainder of this answer.
2: It may happen that the minimization and maximization program give the same value, but a different one than $b_i$. (Try to think of an example!) In this case, the inequality must be redundant: it can be removed from the system without changing $P$.


That is called secret sharing.

The usual method for the 2-shares case is the method you thought of with the one-time pad.

Note that usual secret-sharing schemes provide no protection against fake shares.


Can we get a better time hierarchy theorem?

IMHO, there cannot be better, stricter Time Hierarchy Theorem everywhere.

To improve this theorem, you need faster Universal Turing Machine. The $log(n)$ overhead of the currently fastest simulation technique seems to be unavoidable, especially for large enough time bounds, since with more time resource the simulated TM can do crazy things that the UTM cannot assume some regular property to do the simulation faster.

With small time bounds, there may be some improvements. But, its consequences are negligible.


Amortised analysis is a tool to get more useful results than "naive" worst-case analysis. Especially in the realm of advanced data structures, operations can be cheap most of the time but expensive in rare cases; worst-cases analysis yields only the latter case as characteristic of the data structure. Dynamic arrays, splay trees and some flavors of hash tables are among the more popular examples.

For many purposes, that is too pessimistic. We don't actually need that every operation is fast¹; we execute lots and lots of operations (e.g. during an algorithm) and we want the total runtime to be small. That is what amortised analysis looks at.

Be careful not to confuse amortised analysis with average-case analysis. The former is still considering the worst case; it only sums over time and spreads the cost evenly; you get for one operation its share of the worst-case total cost. On the other hand, average-case assumes a probability distribution over inputs and/or the sequence of operations, and yields the expected time per operation, which is (by definition) its share of the expected total cost.

Real-time applications are a notable exception.


Term for an approximation that becomes better as the problem grows

You can say your algorithm is asymptotically optimal. One example is universal codes, which are a certain type of codes for the natural numbers. They satisfy the following property. Let $D$ be a monotone probability distribution over the natural numbers, that is $\Pr[D=n] > \Pr[D=n+1]$. The average codeword length under a universal code is $H(D)(1 + o(1))$. Since $H(D)$ is the optimal length, universal codes are asymptotically optimal, in exactly the same sense as the one you're after.


Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

In the example, we can assume the start cell $s$ is the origin in a plane consisting of square cells with Descarte coordinates.  That is, $s$ is $(0,0)$. The coordinate of destination cell, $t$ is $(m,n)$. The distance of any two cells is given by the taxicab geometry. That is, the distance between cells $(p_1,p_2)$ and $(q_1,q_2)$ is
$$d((p_1,q_2),(q_1,q_2))=|p_1-p_2|+|q_1-q_1|$$
In particular, $d(s,t)=|m|+|n|$.

At the last step of running Dijkstra's algorithm with source cell $s$ when we visit cell $t$, all cells whose distance to $s$ is smaller than $d(s,t)$ must have been visited. Some of the cells whose distance to $s$ is $d(s,t)$ may have also been visited. If you color all cells that are no more than $d(s,t)$ away from $s$, you will get a diamond shape whose boundary cells $(p,q)$ are given by the following equations.

$$ \begin{align}
p+q = d(s,t)  &\text{ where }p\ge0, q\ge0. \text{ This is the top right segment.}\\
p-q = d(s,t)  &\text{ where }p\ge0, q\le0. \text{ This is the bottom right segment.}\\
-p+q = d(s,t) &\text{ where }p\le0, q\ge0. \text{ This is the top left  segment.}\\
-p-q = d(s,t) &\text{ where }p\le0, q\le0. \text{ This is the bottom left segment.}\\
\end{align}$$

That diameter shape is, in fact, a circular disk with center $(0,0)$ and radius $|m|+|n|$ in the taxicab geometry. Yes, as you pointed out, "radios" should be "radius".

How many cells are there in the diamond shape? The diamond shape is actually a square the length of whose diagonals is $2(|m|+|n|)$. So its area is $(2(|m|+|n|))^2/2=2(|m|+|n|)^2$, which is about the number of cells in the it asymptotically.

Exercise. The exact number of cells in a disk with radius $r$ in the taxicab geometry is $2r^2+2r+1$. In particular, there are 13 cells in a disk with radius 2.


O(·) is not a function, so how can a function be equal to it?

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some caveats of the $O$ notation.
For example, we write that $(1/2) n^2 + n = O(n^2)$, but we never write that $O(n^2)=(1/2)n^2 + n$. To quote Donald Knuth (The Art of Computer Programming, 1.2.11.1):

  The most important consideration is the idea of one-way equalities. [...] If $\alpha(n)$ and $\beta(n)$ are formulas that involve the $O$-notation, then the notation $\alpha(n)=\beta(n)$ means that the set of functions denoted by $\alpha(n)$ is contained in the set denoted by $\beta(n)$.


Stirling's approximation states that
$$
n! \sim \sqrt{2\pi n} (n/e)^n = \Theta(\sqrt{n} (n/e)^n).
$$
Therefore $\sqrt{n}! = \Theta(n^{1/4} (\sqrt{n}/e)^{\sqrt{n}})$. In particular, $\sqrt{n}! = o(\sqrt{n}^{\sqrt{n}})$.

Note also that if all you want is to express $\sqrt{n}!$ in big Theta notation, you can just write $\sqrt{n}! = \Theta(\sqrt{n}!)$.

If $\log f(n) = \Theta(\log g(n))$ then it doesn't follow that $f(n) = \Theta(g(n))$. For example, $\log (a^n) = \Theta(\log (b^n))$ for all $a,b > 1$, but $a^n$ is not $\Theta(b^n)$ (unless $a = b$).


Stablishing termination of the construction of infinite stream with ranking functions

I think Turing's method is probably fine, but you are mistaken about why exactly the code you wrote, "terminates."

First, note that this is not really (written as) a function at all. It is a self-referential value. And the reason the program terminates even though it's defined in it is that the program does not attempt to evaluate it fully. In this case, perhaps it would be all right, because a sufficiently smart evaluator would notice that there is a loop in the pointer structure, but there are other examples where that would not be sufficient.

So, these infinite structures are not something that you prove 'terminate' by showing they can be labelled by some finite size. Instead, they are not evaluated at all until something else demands to see the structure, and then they are unfolded as needed. This sort of structure is sometimes called, "coinductive," whereas the Turing methodology you're talking about is related to induction.

However, there is a property related to termination for coinductive things. For termination of inductive definitions, we label inputs with natural numbers (say), and ensure that this number decreases for recursive calls, which ensures termination. For coinductive definitions, we consider things like #:: to increase size, and we want to ensure that the size of the result is bigger than the size of any recursive references. This ensures that we are incrementally producing more of the value after a finite amount of work, and this is referred to as the definition being, "productive."

The reason we care about this property is that we assume the parts of the program that cause the unfolding of the infinite values can only demand finite portions of them. If you can only look at a finite portion of a potentially infinite value, and the pieces each take a finite amount of time to produce, the overall computation terminates.

But, there is also a way to apply a more Turing-like methodology to this, and it is to recognize that streams could be implemented as functions. Stream[Int] is the same, in a way, as Natural => Int, where you ask for the value of the stream at a particular index, and it returns the value. And in this representation, productivity corresponds to the termination of the function for every natural number. In this case it's easy, because the function is x => 0, but other examples could require more sophisticated arguments.


What is the point of delimiters and whitespace handling

Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?

If by "right" you mean it is the case in every programming language, then no, it is not right, and probably no non-trivial lexical statement would be either.
In many languages, integer literals do not have to be separated from a following identifier; in other languages, they do. In most languages, <= is different from < =, so identifiers and numbers are not the only classes of tokens which require explicit separation. (If you don't consider < and = to be "delimiters", then you cannot say that identifiers need to be separated by whitespace or delimiters, either, since a<b is normally valid.)
Maximal munch is a very common lexical algorithm. This views the input to be a sequence of lexemes where each lexeme starts precisely following the previous lexeme and continues as far as possible (so that if two lexemes are possible at a given point in the source code, the longest one is chosen regardless of whether the rest of the input would be valid or not). Not all lexemes are tokens; the set of lexemes includes ignorable whitespace, for example, which is recognized by the tokeniser but does not otherwise participate in syntactic analysis.
However, most languages have idiosyncratic exceptions. Consider the handling of <:: in C++ or 1..2 in D; both of these require an explicit exception to the maximal-munch rule. A different issue is the handling of regular-expression literals in ECMAscript (and other languages), in which / and /= could be tokenised as a simple operator token, or they could be the first part of a regular expression literal. Which option is chosen depends on the immediate syntactic context. Yet another deviation from the above model is found in languages like Python and Haskell where layout (whitespace used as indententation) is sometimes syntactic.
To the extent that a language specification uses the maximal munch algorithm, whitespace is mandatory precisely in those contexts where maximal-munch would produce a different tokenisation. In such languages, whitespace is always discarded (after tokenisation) and there is no need to ensure it is supplied.
There is no global institution which regulates computer language designers. Each language community develops according to its own philosophy, customs, eccentricities and equivocations, and there is no higher truth to which one can appeal.

Particular languages may be based on a different tokenisation model, so you cannot make general language-independent statements based on the behaviour of a single language. In the comments streams, it has been suggested that this question actually applies to VHDL and that VHDL does not conform to the maximal munch model. The text cited in the OP apparently comes from section 13.2 of the VHDL Reference Manual. However, it seems clear (even from the text quoted in the OP), that the design is not much different from maximal-munch. I repeat, with emphasis added:

The text of each design unit is a sequence of separate lexical elements. Each lexical element is either a delimiter, an identifier (which may be a reserved word), an abstract literal, a character literal, a string literal, a bit string literal, or a comment.
In some cases an explicit separator is required to separate adjacent lexical elements (namely when, without separation, interpretation as a single lexical element is possible). A separator is either a space character (SPACE or NBSP), a format effector, or the end of a line. A space character (SPACE or NBSP) is a separator except within a comment, a string literal, or a space character literal.

So that makes it clear that the only case in which separation is obligatory is where the concatenated tokens could be tokenised as a (longer) combined token, which is essentially the maximal-munch rule.


Why are $L$-reductions defined the way they are?

L-reductions were defined by Papadimitriou and Yannakakis in their paper Optimization, approximation, and complexity classes. From the abstract:

Furthermore, we show that a number of common optimization problems are complete for MAXSNP under a kind of careful transformation (called L-reduction) that preserves
approximability.

A survey of various related notions of reducibility is Ausiello and Paschos, Approximability preserving reduction. Each of the notions of reductions appearing there was invented to serve some purpose. Definitions are typically not arbitrary. They are supposed to model some intuitive notion. Some definitions are more successful than others. When unsure about a definition, it's always a good idea to check out the original paper(s) introducing the definition.


How to find unambiguous grammar for palindromes

First, I believe you are looking for a different word than 'unambiguous'.  A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must have only one derivation in this grammar.

I suspect the word you really mean is 'deterministic'.  YACC must declare that this grammar has 'shift-reduce' conflicts - e.g if the next letter is 'a' one cannot decide if the first, third, or fourth rule is to be applied.  This is an inherent problem with palindromic languages; the core problem is that there is no way to know, during a left-to-right scan of the input string, exactly where the midpoint of the string is.

If you are permitted to change the language, you could add a new letter 'c' and use it to always (and ONLY) mark the center of each string.


Sorting a list of strings in lexicographic order of sorted strings

You can also solve this in $O(n \log n)$ time and $O(n)$ space:

First, sort each word using mergesort.  The running time of this will be at most $O(n \log n)$, and the space usage is $O(n)$.
Then, store all the words in a word trie.  The time and space for this will be $O(n)$, if you implement the word trie properly.  In particular, at each node of the trie, you should store the set of children as a hashtable (not as an array).  In this way, the storage at a node is proportional to the number of children it has, and lookup to find a child can be done in $O(1)$ time.  Thus, the running time of this stage is $O(n)$ time and $O(n)$ space.
Finally, read out all the words from the trie.  This involves taking each hashtable and sorting its contents, say using mergesort.  All of those sorting steps will take at most $O(n \log n)$ time.

The resulting data structure seems quite simple.  It's especially simple if you implement in a language that has built-in support for hashmaps (e.g., Javascript, Python).

Alternatively, you can replace the hashmap with a balanced binary tree data structure and get a similar running time.

As a general note about "smart arrays":

You can replace your use of "smart arrays" with a hashtable.  That way you will preserve the ability to do $O(1)$ (expected) time reads and writes.  In particular, instead of setting $A[i] := v$, you store value $v$ at the key $k$ (i.e., add the mapping $k \mapsto v$ to the hashtable).  When you want to read the value of $A[i]$, you instead lookup $i$ in the hashtable and return whatever you find there.  In this way, the space usage is proportional to the number of initialized entries in the "smart array", and each access takes $O(1)$ (expected) time.


Show that every definite language is accepted by a finite automaton

This is true as a consequence of the Myhill Nerode theorem. For any fixed $k\gt 0$, the number of possible combinations of the last $k$ symbols of any string $w\in L$ is $|\Sigma|^k$, where $\Sigma$ is the alphabet.

Any two strings that have the last $k$ symbols identical will always be both accepted or both rejected by $L$, for any string appended to them, i.e., no string in $\Sigma^*$ will distinguish such strings. Thus, such strings lie in the same equivalence class of $L$.

Strings with differences in their last $k$ symbols will either lie in different equivalence classes or will cause the classes demarcated in the previous step to collapse together into a single class.

Thus, the equivalence classes of $L$ are determined by the last $k$ symbols of $L$.

As the possible combinations of the last $k$ symbols is finite, the number of equivalence classes is finite. Thus, by the Myhill Nerode theorem, the language $L$ is regular. Hence, there exists a DFA that accepts $L$.


Relationship between graph expansion and conductance

There are several different definitions for the expansion of a graph, but all of them are spatial. One common definition defined the expansion $h(G)$ of a graph $G$ as $$ h(G) = \min_{|S| \leq |G|/2} \frac{|\partial S|}{|S|}, $$
where $S$ is a set of vertices containing at most half of the vertices, and $\partial S$ is the (edge) boundary of $S$, the number of edges connecting $S$ to $\overline{S}$. For a $d$-regular connected graph, there is a strong connection between $h(G)$ and a spectral parameter, the eigenvalue gap $\lambda(G)$, which is the smallest non-zero eigenvalue of the Laplacian. For a $d$-regular connected graph, Cheeger's inequality states that
$$ \frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}.  $$
This is often put in terms of the second largest eigenvalue $\lambda_2(G)$ of the adjacency matrix of $G$, which satisfies $\lambda_2(G) = d - \lambda(G)$. There must be versions of Cheeger's inequality for non-regular graphs, and I'll let you look them up.

A lot of information on expander graphs can be found in the survey (based on course notes) Expander graphs and their applications by Hoori, Linial and Wigderson. Other information is scattered among lecture notes and even recent papers.


Avoiding underflow when identifying neighbours of a cell in a grid by using modulo

Using modular arithmetic here is equivalent to playing the game of life on a torus. Suppose you start with a $100\times 100$ grid with rows and columns numbered $0, \dots, 99$. The modular arithmetic says that $0-1\equiv 99$, which means that row $99$ is above row $0$ as well as below row $98$ and, similarly, column $99$ is to the left of column $0$ as well as to the right of column $98$.

This isn't equivalent to saying that there is nothing above row $0$ and nothing below row $99$.


Does the following operation makes the language regular?

Interesting question. As Orlp pointed out, $L$ does not contain 01. So it cannot be $(0+1)^*$.

In fact $L$ is not regular. Consider $M=L\cap L(0^+110^+1)$.

Claim. $M=\{0^i110^i1\mid i\gt0\}$.
Proof. Since $(0^i1)1(0^i1)\in M$ for $i>0$, we have the "$\supseteq$". Now suppose $wxw=00^i110^j1$, $w\in\{0,1\}^+$, $x\in\{ 0,1\}^*$, $i,j\ge0$. then $w$ must starts with 0 and ends with 1. Since there only three 1's in $wxw$, $w=00^i1$ and $x=1$. So $wxw=00^i1100^i1$, $i\ge0$. We have the "$\subseteq$".

There is a counting requirement for words in $M$. So, intuitively, $M$ cannot be regular. I will let you prove it rigorously using, for example, the pumping lemma for regular language.

Since $M$ is not regular and $0^+110^+1$ is regular, $L$ cannot be regular.


Why don't we use simple binary values to compress data?

Suppose we code, as you suggest, $a=0$, $b=1$, $c=10$, $d=01$, $e=11$, etc., and I send you the message $1001$. You can't tell if I said $10\,0\,1=cab$, $1\,0\,01=bad$. The point of the Huffman scheme is that it's a prefix code, so it's uniquely decodable (and, further, you can always decode the start of the message based on the bits you've already seen, without having to look into the future).


Call an array $C$-sorted if each element is at-most $C$ places away from its place had the array been sorted (this is the same as "almost"-sorted array in the question, but in plain English).
Assume we will use comparison sort.
Claim One: Given an array of $n$ elements that is $C$-sorted,  we can sort it with at most $n\lceil\log_2 (C+1)\rceil$ comparisons.
Proof: Here is how we can sort the given array.

Create a buffer that is an array of size $C+1$.

One by one move the first $\min(n, C+1)$ elements to the buffer, keeping the buffer sorted using binary search to find the right place for each new element.

One by one move the min element from the buffer array to the result array, and, if the given array is not empty yet, add the next element to the buffer, keeping the buffer sorted using binary search to find the right place for that next element.

For each element in the array, at most $\lceil\log_2 (C+1)\rceil$ comparisons is used to find its right place in the buffer. The number of total comparisons used is at most $n\lceil\log_2 (C+1)\rceil$.  $\quad\checkmark$

Claim Two: At least $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons are needed to $C$-sort an array of size $n$ in the worst case.
Proof: Otherwise, suppose there is an algorithm that can $C$-sort any given array of size $n$ with less than $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons. Extending that algorithm with the algorithm shown in the proof of claim one, we obtain an algorithm that can sort any given array of size $n$ with less than $\log_2(n!)$ comparisons. That is well-known to be impossible. $\quad\checkmark$

Claim Three: There is no algorithm that can $C$-sort an array of size $n$ with $O(\frac{n\log_2 n}{C})$ comparisons.
Proof: We have, if $n\ge C^{1+\epsilon}$ for some fixed $\epsilon\gt0$,
$$\begin{aligned}\lim_{C\to\infty} \frac{\log_2 (n!) - n\lceil\log_2 (C+1)\rceil}{\frac{n\log_2 n}{C}} &= \lim_{C\to\infty} C\left(\frac{\log_2 (n!)}{n\log_2 n}-\frac{\lceil\log_2 (C+1)\rceil}{\log_2 n}\right)\\&\ge \lim_{C\to\infty} C\left(1-\frac1{1+\epsilon}\right)=\infty.
\end{aligned}\quad\checkmark$$

Indeed, $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ given a pretty strong lower bound for the number of comparison needed in the worst case since
$\log_2 (n!)$ is the lower bound to ordinarily sort an array, and, as $\log_2(n!)\approx n\log n$, for any fixed $C$,
$$n\lceil\log_2 (C+1)\rceil = o(\log_2 (n!)).  \ \ \color{#d0d0d0}{\text{(small o, not big O!)}}$$
That is, at least $(1-\epsilon)\log_2(n!)$ comparison is needed to $C$-sort array when $n$ is sufficiently large, for all fixed $\epsilon\gt0$ and $C$.

We also note that

on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A comparison sort cannot use less than $\log_2(n!)$ comparisons on average to sort $n$ items (as explained in the article Comparison sort) and in case of large $n$, Stirling's approximation yields $log_2(n!) \approx n(\log_2 n − log_2 e)$, so quicksort is not much worse than an ideal comparison sort.

Now let us have an array of $n=1000$ elements and $C=10$.

Quicksort will perform about $2n\log n\approx 19931$ comparisons on average to sort the array, as shown on Wikipedia.
Claim Two says $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil\approx4529$ are needed to $10$-sort the array in the worse case, which is sort of information-theoretical the best.
Note that $\frac{n\log_2 n}{C}\approx997$, which is much less than
of 4529.

So I believe, (some more argument are omitted here), an algorithm that performs about $n\log_2(n/C)\approx6643$ comparisons to $10$-sort the array is pretty much about the best we can get.


Are these production rules for a formal grammar?

The use of notation in that statement might be confusing.  A grammar is a rule of the form "something $\to$ something", where the something on the left is a string of symbols containing at least one non-terminal symbol, and the something on the right is a string of symbols.
For instance, $A \to BcD$ would be a valid rule, as would $AB \to BDeeF$, or $aAcE \to b$.
If you read the very next sentence after the one you quoted, it explains the meaning of the part you didn't understand, in different words.  It says "That is, [...]" (you can read the rest yourself).  If you don't understand one sentence, in the future I suggest you keep reading a little further to see if you can work it out from context.


How did the Logic Theorist prove the Pons Asinorum?

If you google "logic theorist source code" you find this which is clearly not the original source code, but presumably is a modernization of the ideas in the code. You can also find this 1963 RAND memorandum which is a more contemporary description of the system. It seems to include a complete code listing as well as descriptions in terms of flowcharts.

As far as I can tell, it proved basic statements in essentially classical propositional logic.  The main idea is backward chaining.

Page 52 of Perspectives on the History of Mathematical Logic shows the (erroneous) proof of Theorem 2.85 in Principia Mathematica and the proof Logic Theorist produced.  Theorem 2.85 (using more common notation) is $$((P\lor Q)\Rightarrow(P\lor R))\Rightarrow(P\lor(Q\Rightarrow R))$$ which (ironically) is actually easier to read in Logic Theorist's notation, (((PVQ)I(PVR))I(PV(QIR))), than it is in the aforementioned page. As you should be able to tell, this has no particular connection to any geometrical theorem, let alone the isosceles triangle theorem.  I have no idea why it's linked that way on Wikipedia.  You could, however, take e.g. Tarski's axioms for planar geometry and apply the same proof search techniques to questions in Euclidean geometry as done in Automated Development of Tarski's Geometry by Art Quaife. I can't find a good reference, but I'm fairly certain novel and elegant proofs have been found when automated theorem proving (in this style) has been applied to planar geometry. This isn't surprising as these systems tend to search the proof space starting from the shortest proof candidates.


How to prove $L \notin \texttt{DSPACE}(f)$

Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the halting problem is proven undecidable.

You're not going to prove that a completely generic language $L$ is not in $\mathrm{DSPACE}(f(n))$ for a completely generic function $f$.  Any such proof is going to have to rely on some properties of $L$ and $f$: quite apart from anything else, if you fix a decidable language $L$, then there are infinitely many functions $f$ such that $L$ is in $\mathrm{DSPACE}(f)$ and, conversely, if you fix any "reasonable" function $f$, there are infinitely many languages in $\mathrm{DSPACE}(f)$. So you can't hope to prove $L\notin\mathrm{DSPACE}(f)$ as a generic result.

Second, saying "I don't know any languages in $\mathrm{DSPACE}$" is like saying I don't know any people who weigh kilograms (or pounds, if you prefer). It doesn't really mean anything until you specify how many kilograms or, correspondingly, what space bound you're talking about.


What is the name of the data structure that is a tree on the backend but has a list like API?

In "Optimal  Algorithms for List Indexing and Subset Rank" by Paul F. Dietz this data structure is called an "indexed list" and an algorithm is given that has complexity $O(\log n / \log\log n)$ for all operations. Unfortunately this term has little value as a search term.

While that is complex data structure note that you can transform any self-balanced tree into the data structure you want. Just replace the key field of each node with a field that keeps track of the number of elements to the left of it, and update this on inserts/deletes (takes $O(\log n)$ time). Then use that field as your key when searching for element $i$ in the tree.

Also check out "tiered vectors".


Find a pushdown automaton for { x#y ∣ x ≠ y }

Since you have a marker $\#$ separating $x$ and $y$, the solution is
rather easy. The PDA must first decide non-deterministically whether
it will attempt to check that $|x|\neq|y|$ or whether $x$ and $y$
differ for their $i$-th symbol, i.e. whether $x_i\neq y_i$. This
corresponds to two distinct sets of states.

The first case can be dealt with as you suggest.

In the second case, the automaton scans the input, and stores a symbol
$a$ in its stack to keep count. At the $i$-th symbol, chosen
non-deterministically, it decides to check whether that is the symbol
rank for which $x_i\neq y_i$. So it memorizes the synbol $x_i$ in its
finite control (meaning that the states now used have a component
indicating whether a $0$ or a $1$ was found). Then, the PDA scans the
input without memorizing anything until it scans the symbol $\#$. Then
it start scanning the $y$ part, popping the stack for each symbol
read. When the stack is empty, it is reading the symbol $y_i$, and it
can check whether it is different from $x_i$ memorized in the finite
control. If it is different, the PDA can accept the string, and does
not even need to scan the rest.

If the end of the string is reached before the stack is empty, the
automaton can accept too, though this can also be handled by the first
case.


Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

The proof seems correct to me.

1) The base case proves the claim when the height of the subtree rooted at $x$ is $0$. The inductive step proves the claim for every subtree rooted at $x$ of positive height $h$ assuming that the claim is true for all subtrees of heights from $0$ to $h-1$. So the inductive step for $h=1$ is able to prove the claim for all subtrees of height $1$ using the fact that the claim is true for the base case, i.e., for all subtrees of height $0$. This is a standard proof by structural induction.

2) Each subtree $T_u$ rooted in a child $u$ of $x$ has a black-height $bh(u)$ of either $bh(x)$ or $bh(x)-1$ but, in any case, the height of $T_u$ is smaller than the height of the subtree $T_x$ rooted in $x$. This means that the induction hypothesis can be applied, showing that the number of internal nodes is at least:

$2^{bh(x)}-1$ if $bh(u)=bh(x)$; or
$2^{bh(x)-1}-1$ if $bh(u)=bh(x)-1$.

In any case the number of internal nodes of $T_u$ is at least the smaller of the above two quantities, i.e., $\min\{ 2^{bh(x)}-1, 2^{bh(x)-1}-1 \} = 2^{bh(x)-1}-1$.
This means that the number of internal nodes in $T_x$ is at least:

$$
2 \cdot ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)}-1.
$$


Do compression tables exist and where are they used?

The big advantage of Lempel-Ziv-style compression is that

it creates its own dictionary on the fly and
tailors it to the data. Therefore, they are
general-purpose compression algorithms which
can be used without having to keep dictionaries in sync; all you need for
decoding is the encoded file and the algorithm.

If you fix a dictionary, this is going to perform well for some inputs. For instance, you can order all English words by frequency in some corpus, number them and store a sequence of these numbers instead of the words themselves. This will then work very well for English texts similar to your corpus, worse for other texts, and not well at all for weather data or images.

Note that LZ-style compression is used in popular formats such as (g)zip, PNG and GIF.

FLAC is one noteable format that uses something different, namely linear predictors. In a certain sense, you can view this as a fixed (though conceptually infinite) dictionary; the method estimates parameters of a certain model and represents bits of data by these parameters (plus some error information). This works well because the model fits the kind of data (apparently) very well, and the representatives are significantly smaller than the data itself. However, the decoder only knows the model; there is no fixed set of parameters everybody uses. So I don't think this fits your idea, either.