I believe you can solve it by:

first sorting the list that you have with some predictable ordering of the names. (maybe A -> Z)
Doing the final sort later, and to find the "previous" element thru name you just have to do a binary search on the ordered list.


Computational complexity of function $U^V$

One way to do this is by repeated squaring. First, express $V$ in binary,
$$
V = b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n
$$
where each  $b_i$ is either zero or one. Having done this, repeatedly square $U$ to get $U, U^2, (U^2)^2 = U^4, (U^4)^2=U^8, \dotsc, U^{2^n}$. Then
$$\begin{align}
U^V&=U^{b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n}\\
   &=(U^{b_0})((U^2)^{b_1})((U^4)^{b_2})\dotsm((U^{2^n}))^{b_n})
\end{align}$$
For example, to compute $3^{21}$ we would get the binary expansion of $21=16+4+1$ and then repeatedly square the $3$s:

$$\begin{align}
3^1 &=3\\
3^2 &=9\\
3^4 &=81\\
3^8 &=81^2=6561\\
3^{16} &= 6561^2=43046721
\end{align}$$
So we'll have
$$
3^{21}=3^{16+4=1}=(3^{16})(3^4)(3^1)=(43046721)(81)(3)=10460353203
$$
Consider the worst case, with $V=2^n-1$, and let $d$ be the number of bits in the representation of $U$. This will require $n-1$ squarings. Let's use the grade-school multiplication algorithm, for which the product of two $k$-bit numbers will take $O(k^2)$ primitive operations. We'll then have
$$\begin{array}{ccc}
\text{product}& \text{factor size} & \text{ops needed}\\
U^2 & d & d^2\\
U^4 & 2d & 4d^2\\
    & \dotsc & \\
U^{2^{n-1}} & 2^{n-2}d & 4^{n-2}d^2
\end{array}$$
So the total number of operations needed to precompute the squares will be
$$
(1+4+4^2+\dotsm+4^{n-2})d^2 = O((2^n)^2d^2) = O(V^2\log^2U)
$$

Now since we chose $V$ so that it involved all of the squares we computed, we'll have the final product $(U)(U^2)(U^4)\dotsm(U^{2^{n-1}})$. Mirroring the construction above, we find that the final product will also take $O(V^2\log^2U)$ operations, so to compute $U^V$ by repeated squaring will take time $(2^nd^2)$ where $n, d$ are the number of bits in $V$ and $U$, respectively. Unfortunately, this means that this construction is not polynomial in the size of $V$.

Notes.

In your original question, strictly speaking, the classes P, NP, Np-complete and NP-hard are generally applied to decision problems, which this isn't.
There are faster ways to compute the product of two integers, so you can actually do better than $O(V^2\log U)$.
While this (as it turns out) is actually less efficient than the naive algorithm of computing $U^V$ by successive multiplications, $U, U^2, U^3,\dotsc$, it works very well when computing modular powers, $U^V\pmod W$, since none of the intermediate products will ever be larger than $W$.


The exact relation between complexity classes and algorithm complexities

$P$ is defined as the class of (decision) problems that have an algorithm that solves them in polynomial time (in a TM, or a polynomially-equivalent model). Thus, $P$ contains exactly these problems, no more and no less.

As for $NP$- the situation is more delicate. A problem is in $NP$ if it has a nondeterministic algorithm that runs in polynomial time. An equivalent, more user-friendly definition, is that given a solution to the problem, you can verify it's correctness in time polynomial in the size of the problem. For example, given a graph and a path that claims to be a Hamiltonian, you can verify in polynomial time that it is indeed a Hamiltonian path. Thus, the problem of deciding if a graph has a Hamiltonian path is in $NP$.

Clarification: $NP$ is a class of problems, not of algorithms. An algorithm doesn't belong to $NP$.

Now, some problems are known not to have a polynomial time algorithm. This doesn't mean that they are in $NP$. In fact, some problems are known not to be in $NP$. For example, any $NEXP$-hard problem.

Regarding $NP$-hard problems - since we don't know whether $P=NP$ or not, we don't know if every problem outside $P$ is $NP$-hard. If $NP=P$, then every problem is $NP$-hard (except $\Sigma^*$ and $\emptyset$).

This answer (which is by far incomplete) covers about 3 weeks of material in a basic complexity course. Perhaps consider thoroughly reading a textbook, such as Sipser's "Theory of Computation".


What kinds of programming pitfalls modern languages are able to find?

Substructural types ( http://en.wikipedia.org/wiki/Substructural_type_system ) can be used to provide some version of each of those. As a summary, while normal types control how something may be used, substructural types further control when or how often it may be used.

Affine types can be used to construct languages capable of expressing all, and only, polynomial-time functions. http://www.cs.cmu.edu/~fp/courses/15816-s12/misc/aehlig02tocl.pdf
Linear types can enforce that memory is accessible when variables go out of scope, enabling a kind of "static garbage collection." Similarly, ordered types can be used to require that variables are used in a LIFO order, allowing them to be stack-allocated. Regions ( http://en.wikipedia.org/wiki/Region-based_memory_management ) are also useful here. The first chapter of Advanced Topics in Types and Programming Languages provides a nice introduction to using linear and ordered types for this purpose.
Affine types also enable typestate-oriented programming ( http://www.cs.cmu.edu/~aldrich/papers/onward2009-state.pdf ). Typestate is used to enforce certain orderings in APIs (e.g.: can't read from a closed file), but can also be used to enforce safety properties. Requiring a block that handles some error can be encoded as requiring a function that transitions some object from an error state to a recovery state.


A "shortcut" to the solution; first calculate the NEEDED = MAX - ALLOCATEDresources:

    ALLOCATED MAX      NEEDED
    A B C     A B C    A B C
P1  0 1 0     7 5 3    7 4 3
P2  2 0 0     3 2 2    1 2 2
P3  3 0 2     9 0 2    6 0 0
P4  2 1 1     2 2 2    0 1 1
P5  0 0 2     4 3 3    4 3 1

AVAILABLE: x y 2

In order to complete P1 we need 4 Bs. But if you observe the column B of ALLOCATED, we see that we can only gain a single B if P4 is executed before P1. So whatever the execution order is, we need more than 3 new Bs (y >= 3).

Furthermore in order to complete P3 we need 6 As, but if you look at column A of ALLOCATED, we see that we can only gain 4 Bs if P2 and P4 are executed before P3. So whatever the execution order is, we need more than 2 new As (x >= 2).

So we have:

AVAILABLE: 2+x' 3+y' 2

and we can start completing processes that need less than (2 3 2) (P4 and P2)

P4: (2 3 2) - (0 1 1) + (2 2 2) = (4 4 3)
P2: (4 4 3) - (1 2 2) + (3 2 2) = (6 4 3)
now also P3 can be completed:
P3: (6 4 3) - (6 0 0) + (9 0 2) = (9 4 5) which are enough resources for
both P1 and P5

So the state is safe even with x'=0 and y'=0 and the solution is x=2, y=3


Algorithm for finding the limit of unkown function

This is some form of fixed point iteration (you are going $x_{n + 1} = f(x_n)$, and looking for $x^* = f(x^*)$). If you know that the convergence is linear (i.e., $e_{n + 1} \approx C e_n$, where $e_n$ is the $n$-th error), you can accelerate the convergence by Aitken's $\Delta^2$ method. Say you have $x_0$, $x_1$ and $x_2$. A (hopefully much better) approximation is given by:

$\begin{align*}
  x^+
    &= x_2 - \frac{(\Delta x_1)^2}{\Delta^2 x_0} \\
    &= x_2 - \frac{(x_2 - x_1)^2}{x_2 - 2 x_1 + x_0}
\end{align*}$

Start with $x_0 = x^+$ and compute new values for $x_1, x_2$. Repeat until satisfactory precision.


State-elimination on FSA, after epsilon-removal construction

Should I first follow the epsilon-removal construction, and then do state elimination?
  Or can I use state-elimination directly on this FSA?

If you would like to do more work to kill time, or if you would like to check the effect of epsilon-removal construction, or if someone higher on the command chain forces you to (for reasons I have no informed guess about), you should do the epsilon-removal construction before state elimination.

Otherwise, it is perfectly fine to start state-elimination directly and immediately.

By the way, the regular express I got is
$$\left(0+(0+02)(2+42)^*(4+\epsilon)\right)^*(0+02)(42+2)^*\,.$$


A question on instruction executing speed

There are a number of reasons for this.

Other processes were probably running at the same time.
Printing to the console takes many, many instructions per print, especially when the console starts to scroll.
You may have been using an interpreted language. In this case, the computer must  figure out what each line of your program means before running it. Some interpreters figure this out again every time they come to a line, even if they've run it before. Again, this takes many, many instructions per line.


Choosing $n$ points to get the closest sum

Round the $x_i$ into multiples of $(\epsilon/n) N$ (for a parameter $\epsilon > 0$ of your choice) which we will denote by $y_i$, and use dynamic programming to solve your problem for the $y_i$ in time $O(n^2N/\epsilon)$, coming up with a set $J$. Since $\sum_{j \in J} |x_j - y_j| \leq \epsilon N$, this will go you the correct answer up to an additive error of $\epsilon N$.

(Ricky Demer suggested the same solution in the comments to the post.)


Decomposing a closed walk in a directed graph into cycles

The problem stated in the question is also presented in the exercise of the book.

If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.


3-SAT and Systems of Nonlinear Modular Equations

The answer depends on whether we're talking about a single equation, or a system of equations; and whether the modulus $m$ is prime or composite.

A single equation

When the modulus $m$ is prime, then you can find a solution to a single equation

$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

in polynomial time (if one exists) by factoring the polynomial $a_n x^n + \dots + a_0$ over the finite field $\mathbb{F}_m$.  When $m$ is composite, finding a solution is (in general) at least as hard as factoring $m$.  See e.g.,Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?.

System of equations

That's the situation for a single equation.  In contrast, finding a solution to a system of (multiple of) these equations (in multiple unknowns) is NP-hard, regardless of whether $m$ is prime or composite.  There's a simple reduction, if $m$ is prime.  Each clause is translated to a nonlinear equation, e.g., $(x_i \lor x_j \lor x_k)$ translates to the equation

$$(1-x_i)(1-x_j)(1-x_k)=0 \pmod m.$$

As another example, $(\overline{x_i} \lor x_j \lor x_k)$ translates to

$$x_i (1-x_j)(1-x_k)=0 \pmod m.$$

Finally, for each variable $x_i$ we add the equation

$$x_i (1-x_i) = 0 \pmod m$$

to force $x_i$ to be 0 or 1 (this is unnecessary when $m=2$).

An extension of this idea works when $m$ is composite, too; if $m=pr$ where $p$ is prime, then multiply the left-hand-side of each equation above by the constant $r$.  This yields a system of nonlinear equations of degree 3.  If you want a system of nonlinear equations of degree 2, that is achievable too; translate the clause $(x_i \lor x_j \lor x_k)$ to the two equations

$$(1-x_i) (1-x_j) = 1-y_{i,j} \pmod m \qquad \qquad (1-y_{i,j})(1-x_k)=0 \pmod m$$

where $y_{i,j}$ is a new fresh variable (different for each clause).


Predicate Logic - Natural Deduction; Assumptions about exists-elimination

In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Exactly right. Your second move was illegal for the reason you said.

The problem is a bit tricky because of the annoying $S \to$ in front of the $\exists x Q(x)$, which means we can't eliminate the existential just yet. In order to get to $\exists x Q(x)$, we need to first have a proof of $S$, or know that $S$ is true. But we don't!

So how do we remove $S$ in front if we don't know it's true? Try first proving, as a lemma, that $S \lor \lnot S$: the law of the excluded middle. Next, your proof will have two cases: one if $S$ is true, and one if $S$ is not true. If $S$ is true, you should be able to eliminate the existential to get your $x$. If $S$ is not true, you should be able to prove $\exists x (S \to Q(x))$ by taking any $x$ at all.

By the way, in case you're interested: one reason this inference is difficult to solve is that not all logicians agree with it! There are logicians who proposed something called "Free Logic", with the main idea being that it is possible for no objects to exist at all. If no objects exist at all, then $S \to \exists x Q(x)$ might be true (it will be true if $S$ is false), but $\exists x (S \to Q(x))$ is definitely false no matter what, because there does not exist any $x$ period.


About the complexity of deciding whether no two elements of a collection are the same

I think there is something wrong with your claim that the complexity is $\Theta(n \lg n)$.  At least, it is not quite that simple.  You don't say where you got that claim from, but I don't think it is accurate, at least in general.

The problem can be solved faster, in some machine models.  For instance, there are sorting algorithms with running time faster than $\Theta(n \lg n)$, in some machine models, and there are other ways to solve this problem -- e.g., using a hash table using a 2-universal hash function should yield a solution whose expected running time is $\Theta(n)$, under a reasonable model of computation.

What is your machine model?  A RAM machine?  What notion of complexity are you OK with?  Worst-case running time of a deterministic algorithm?  Are you OK with a randomized algorithm?  The complexity of the problem will depend upon these fine details.


If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular

You can show that if $L_1 \subseteq L_2$ and $L_2$ is regular, then $L_2 \setminus L_1$ is regular iff $L_1$ is regular. This follows from the product construction, for example. Taking $L_2 = \Sigma^*$, we find that $\Sigma^* \setminus L_1$ is regular iff $L_1$ is regular. Hence if $L_1$ is any non-regular language, then it refutes your statement taken with $L_2 = \Sigma^*$.


How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$?

First of all, your question is not really well-defined, or put differently, the claim is incorrect in general. Consider for example $A = B = \emptyset$, in which there is only one set which you can get, namely $\emptyset$.

There are at least two ways in which we can address this problem. The first is to assume that the starting sets are "generic", that is, they don't enjoy any "special" properties. This is a vague description, but it can be formalized by saying that in the "Venn diagram" of the sets (which I describe below), all regions are non-empty.

The second way is to do everything formally. We think of $A$ or $A \setminus B$ not as a set but as a formal expression defined in an appropriate language. We then make two expressions equal if they are equal whenever you substitute actual sets. For example, $A = A \cap A$ and $A \setminus (A \setminus B) = A \cap B$. You can also define equality syntactically if you prefer.

Another problem with your claim is that it's not clear what you mean by "the sets have $2^n-1$ non-overlapping subsets". For example, $A \cap B$ and $A \setminus B$ are non-overlapping, and this is a maximal collection of non-overlapping subsets (in general). You mean something else, and again there are several possible interpretations. This time all interpretations I can think of only serve to complicate things and make them less intuitive, so I'll just explain what is meant by the claim, and you think of an appropriate interpretation.

The Venn diagram of the sets $A_1,\ldots,A_n$ consists of the $2^n$ regions which you can get by intersecting either $A_i$ or $\overline{A_i}$ for each $i$. That is, for each $i = 1,\ldots,n$ we choose $A_i$ or $\overline{A_i}$, and then compute the intersection of these $n$ sets. You can web-search "Venn diagram" to see pictorial representations.

You can prove by induction (exercise) that any set that you can obtain from (possibly multiple copies of) $A_1,\ldots,A_n$ using $\setminus$, $\cup$ and $\cap$ is a union of regions of the Venn diagram; indeed, a union which doesn't include the region $\overline{A_1} \cap \cdots \cap \overline{A_n}$. Moreover, you can easily get any of these $2^n-1$ regions individually (exercise), and these are your "$2^n-1$ non-overlapping subsets". In total, you can get any union of these $2^n-1$ regions (exercise), and so you can "reach" $2^{2^n-1}$ different expressions.

One possible formulation of your two claims are as follows. First, the maximal number of disjoint sets that can be formed from $A_1,\ldots,A_n$ is $2^n-1$ (under the caveats described in the second paragraph); this can be proved using the exercises mentioned above. Second, the number of different sets that can be formed (again, under the same caveats) is $2^{2^n-1}$, which again follows from these exercises.


How can you compute the expected edit distance in $O(2^{3n/2})$ time?

Heh…for the record, all I said was that the time seems to scale as approximately $\tilde O(2^{1.5n})$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific!

I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $d_{i,j} = d(a_{[0, i)}, b_{[0, j)})$ based on $a_{i-1}, b_{j-1}, d_{i-1,j-1}, d_{i-1,j}, d_{i,j-1}$.  From there, my algorithm is based on two observations.

Firstly, each column $d_{*,j}$ is a function of the previous column $d_{*,j-1}$, the string $a$, and the bit $b_{j-1}$.  We iterate over all strings $a$ (modulo symmetries), but instead of iterating over all strings $b$, we map each possible column $d_{*,j-1}$ to the two possible columns $d_{*,j}$, storing the collection of possible columns in a hash map with a counter for duplicates.  This allows us to deduplicate some work when many different prefixes $b_{[0, j)}$ lead to the same column $d_{*,j}$.

Secondly, using a separate dynamic programming algorithm, we can precompute an upper bound $w_{i,j}$ on $d(a_{[i, n)}, b_{[j, n)})$ based only on $a$.  Then, given a column $d_{*,j}$, the final distance $d_{n,n}$ can never be more than $m = \min_i (d_{i,j} + w_{i,j})$, so we can replace each $d_{i,j}$ with $\min \{d_{i,j}, m - |i - j|\}$ without affecting the final result.  This lets us recognize more columns as duplicates and deduplicate more work.


How to make a Neural network understand that multiple inputs are related to the same entity?

It is not necessary to indicate this to the neural network (and not possible).  This is not part of how neural networks are typically used -- or part of how other machine learning algorithms are used, either.

I confess I'm not clear on why you think it would make a difference, but it doesn't matter: there's no way (that I know of) to do that, and it's not something people normally do.


Note: please edit this answer and add to it, do not create new answers

Rigorous books:

The Art of Computer Programming by Knuth

A Discipline of Programming by Dijkstra

Introduction to Algorithms by  Cormen, Leiserson, Rivest, and Stein

Algorithms by Sedgewick and Wayne

Dr Dobb's Essential Books on Algorithms and Data Structures
This also includes introduction to algorithms

Algorithms + Data Structures = Programs by Wirth and its followup:
Algorithms and Data Structures

The Science of Programming by Gries and
A Logical Approach to Discrete Math by the same author

Algorithms on Strings, Trees and Sequences by Gusfield

Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik

The Theory of Parsing, Translation, and Compiling (part I and II) by  Aho and Ullman

The Design and Analysis of Computer Algorithms by  Aho, Hopcroft, and Ullman

Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman

Obviously the list can be extended quite a bit.
Note that as the field of computer science has expanded, books are unable to keep up and thus you'll have to turn to research papers.


Converting a Recurrence Relation to its Closed Form

It might be helpful if N is assigned a range of values from 1 to say 7 and evaluated till the recursion end is reached.
also summing together terms with 15 multiples separately and 40 multiple separately, because they are the building blocks from the base case and recursion.

T(1) = 40.

T(2) = 40.

....

T(6) = 2 * ( 2 * 40 - 15 ) - 15
           = 4 * 40 - 3 * 15

T(7) = 2 * ( 2 * ( 2 * 40 -  15 ) -15 ) - 15
           = 8 * 40 - 7 * 15

i think this can help to find the closed form. But i am not an expert in this area.


Yes there is, using algorithms such as Brent's cycle finding algorithm.

However, this is quite expensive and has fairly complicated code. What most implementations do is define some constant cycle/chain length, for example $\log n$ where $n$ is the number of elements in the hash table. If you find a chain (or cycle, but we never investigate whether it's actually a long chain or a cycle) larger than that constant we rehash or increase the hash table size.

But if your goal is merely the prove that you have a cycle, and you do not care about efficiency, the simplest method is to invoke the pigeonhole principle, and just loop $n + 1$ times where $n$ is the number of possible slots in the hash table. If you never find an empty slot you must have a cycle.


Are there NP COMPLETE problems that are "easy" in practice?

Honestly, SAT seems pretty easy in practice. SAT solvers are routinely used on instances with millions of variables that arise in model checking against formal specifications.


You may have a misunderstanding of OUTR. OUTR is not the R in the flowchart you posted. Here is what is exactly done in the Mano system:

OUTR is not flag! It's a register for sending AC's value to the output device.
FGO is a flag in system that shows whether the CPU is ready to send data to output device or not. So it is "1" by default. The CPU checks the flag:

If FGO="1" :  The device is ready to send output in an interrupt cycle! so R<--1 and the interrupt process will start:  AC's content will be moved to OUTR in parallel and FGO="0" (means OUTR is full and you cannot send anything to output device!).
If FGO="0": means that the device is busy reading data from OUTR so no more data can be send out.

At the end of the I/O process the R<--0 means get out of Interrupt cycle!


What is the intuition that 2-phase locking achieves serializability (also known as before-or-after atomicity)?

I'll try to phrase it from an intuitive perspective.

Anomalies occur when there are conflicts, i.e. when two different transactions write on the same object (clearly if they only read stuff nothing can go wrong).
For example, here:

r1(x), r2(x), w1(x) // at this point, r2 read garbage

2PL is a way to prevent this kind of stuff from happening by putting a lock on every object a transaction deals with, and removing the locks when it's done.
The lock can be a read lock (when T reads an object) or a write lock (when T writes an object) and the rules are simple:

refuse a read-lock if a write-lock (from a different T) already held
refuse a write-lock if any lock (from a different T) already held.

The idea behind these is that you don't want T2 to read something that T1 is going to overwrite (see the first example), and you don't want T2 to write onto something that was previously read or written by T1.

With 2PL, when T wants to read/write on an object it will ask permissions to put a lock on it, and this permission will be granted (or denied) based on the two rules above.

In the example I gave you, with 2PL T1 would have a write-lock on x so r2(x) would not happen before w1(x) because the read-lock would not be granted (rule 1).


Best-Case Running Time For Binary Search Tree Insertion

Both! That is, if you are lenient with what "best-case" means. The best-case is the input for respectively run¹ of an algorithm which minimises runtime (for a given size). I guess that some of your sources refer to (asymptotically) optimal BST implementations, either them or you mixing up the notions.

These are the facts:

For any (reasonable) binary search tree implementation, the best-case insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
An optimal binary search tree implemenentation has worst-case insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).

That's equivalent for deterministic algorithms; for nondeterministic ones you consider runs.


How could one prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ? Using induction

One way would be to show an isomorphism between strings and ordered sets, then the result is a direct consequence of properties of set cardinalities (namely that $|A \times B| = |A|\cdot|B|$ for any two sets $A$ and $B$).

Let's assume that you don't want to do that (for a start it's probably more work to do it properly - but very quick to do it in a hand-waving manner).

The first step is that we need to show that for a set of string $S$ and an alphabet $\Sigma$, $|S\circ \Sigma| = |S|\cdot|\Sigma|$, where $\circ$ is the concatenation operator (overloaded for sets as well as strings). This is not hard of course: each string $s \in S$ and each $\sigma \in \Sigma$, the string $s \circ \sigma$ is in $S \circ \Sigma$ and this string is different for every choice of $s$ and $\sigma$.

Next we can inductively show that $|\Sigma^{n}| = |\Sigma|^{n}$.

Base Case:

$\Sigma^{0}$ is the set of strings obtained by concatenating elements of $\Sigma$ $0$ times, i.e., just the empty string $\varepsilon$ (or $\lambda$ if you're that way inclined :D). So $|\Sigma^{0}| = 1$. Of course $\alpha^{0} = 1$ for any $\alpha \in \mathbb{N}$, so $|\Sigma^{0}| = 1 = |\Sigma|^{0}$.

Inductive Hypothesis

Assume that $|\Sigma^{k}| = |\Sigma|^{k}$.

Inductive Step

$\Sigma^{k+1} \ = \Sigma^{k}\circ\Sigma$, therefore $|\Sigma^{k+1}| = |\Sigma^{k}\circ\Sigma|$, which we have established is $|\Sigma^{k}|\cdot|\Sigma|$, by the inductive hypothesis (and power laws) $|\Sigma^{k}|\cdot|\Sigma| = |\Sigma|^{k}\cdot|\Sigma| = |\Sigma|^{k+1}$, which is what we wanted to show.


As given in your lecture notes, and an augmenting path is an s-t path in the residual graph such that all edges on the path have a positive residual capacity.
There could be many augmenting paths in the graph. But you just need to find one such path. Therefore, you can apply DFS or BFS which takes $O(m)$ time to find one such path from $s$ to $t$.


"problematic" non-halting inputs for Turing machines

So, let's start tackling those problems. As a side note, I have arranged the questions such that each question uses the answer of the one before it (and this way, they almost seem too trivial to begin with $:$P).

$A(1):$ is pretty trivial from definition. If $L$ is undecidable then there is no Turing machine that computes it and always halts, thus all Turing machines that compute $L$ have $P(M)\ne\emptyset$.
The other direction is also as simple as this one.

$A(2):$ let's assume $L$ is undecidable. If there was a Turing machine $M$ that computes $L$ and has a finite $P(M)$, then let us build a new machine $\hat M$ such that it will have $P(\hat M)=\emptyset$ as following (on input $w$):

reject if $w \in P(M)$ (this is possible since $P(M)$ is finite)
otherwise, return $M(w)$

this new machine, will halt for every $w\in P(M)$, but since for every $w\notin P(M)$ it will run $M$, and it's guaranteed that it will halt on it (since otherwise it would have been in $P(M)$), we have that the new $\hat M$ always halts, and accepts $L$ - thus contradicting the assumption. The other direction is simply derived from $A(1)$.

$A(3)$: for finite sets of Turing machines, $M_1,...M_n$ we will show that its impossible to have finite $\bigcap_{k\space=\space0}^nP(M_k)$ but undecidable $L$. lets assume towards contradiction this doesn't hold. Just at $A(2)$, we will build $\hat M$ - but now its enough to build it such that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k):$

Run $M_1(w), M_2(w), ...,M_n(w)$ in parallel
Accept if any one of them accepted.

Now, it's obvious why $\hat M$ accepts $L$. Let $w\notin P(\hat M)$, then there is some $1\le k\le n$ such that $M_k(w)$ halted, thus $w\notin\bigcap_{k\space=\space0}^nP(M_k)$. let $w\in P(\hat M)$, then it didn't halt on any $M_k$, thus $w\in P(M_k)$ for all $k$. Concluding that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k)$ is finite and therefore from $A(2)$ cannot exist.

Regarding infinite sets of Turing machines, this is definitely possible. Just define for each $w\in \Sigma^*$ the machine $M_w$ that accepts $L$ but also halts on $w$ (similarly to the build in $A(2)$). then $w\notin P(M_w)$ therefore $w\notin \bigcap_{\hat w} P(M_\hat w)$ and thus not only that $\bigcap_{\hat w} P(M_\hat w)$ is finite, its also empty.

$A(4):$ let $L$ is undecidable and $M_1,M_2...$ are Turing machines who accept $L$ and their intersection of the "problematic set" is finite. If we look at the function $f:\mathbb{N}\rightarrow\Sigma^*$ defined by $f(k)=\langle M_k\rangle$ , then it is not computable. This follows from $A(2)$ since if that function was computable, we would have been able to create a Turing machine $\hat M$ with $P(\hat M)=\bigcap_k P(M_k)$

Another idea i have started to think about is what happens when we talk about two languages or more, instead of one at a time. Let $M_1$ be a machine for $L_1$ and $M_2$ for $L_2$. then, we can define a machine $M$ for $L_1\bigcap L_2$ or $L_1\bigcup L_2$ with:

$P(M) = P(M_1)\bigcup P(M_2)$ (note this also can prove closure properties in $\mathcal R$)

or if $L_1\Delta L_2$ is finite, then we the problematic sets of machines for the languages are pretty much the same(for every machine $M$ in any one of them we can find machines $M'_1,M'_2$ for the other two languages with the same problematic set)

Although I have yet to write a formal proof of the above. (honestly, I don't have energy to write more proofs like that in this one big post) I still encourage you to try proving that at home!

Finally! I think (but still unsure) we can get similar results (but with more constraints) for time complexity analysis if we define $P(M, t)$ for time-constructible $t(n)\ge log(n)$ as the group of words $M$ doesn't halt on within $t(n)$ steps. In this definition there is the tricky problem of constants, so its harder to show theorems by defining new machines (as they might do just a little bit more constant work that will make some word enter the problematic set, and big-O notation here is somewhat meaningless for different constants)

If you think that something is incorrect, or just want to add more - I will be glad to make changes.


How is the data stored in AVL tree in a memory?

If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.

In most cases, however, the individual nodes of the tree are stored in one sequential chunk of memory that's allocated by whatever method your system/language provides (most common being malloc and/or new), each containing the key and the two pointers to child nodes, either of which can be a special value NULL, if a child is not present.

The individual nodes are usually scattered around the memory, with no clear relation between how/where they are located. We leave this for the memory allocator of the environment to handle. When we allocate a new node, we place its address (a pointer to it) in an existing node (or, as a special case, in the root pointer), so we can navigate to it.

Think of this as a linked list, where each item can have not only one, but two successors.


Determine if two grammars for the same language are ambiguous

Consider this a hint.  As I write in my comment, what is the syntax tree of ()()()?  Does the first two pairs belong to the leftmost of the <string><string>-part, or does the two latter pairs belong to the rightmost?

$$ \left(
 \overbrace{  \overbrace{ () }^\text{string} \quad
 \overbrace{ () }^\text{string}}^\text{string}
\quad \overbrace{ () }^\text{string} \right)
\text{ vs }
\left(
 \overbrace{ () }^\text{string}\quad
 \overbrace{  \overbrace{ () }^\text{string}\quad
 \overbrace{ () }^\text{string}}^\text{string} \right)
$$


Asymptotics of of $T(n) = n + T(n - \sqrt{n})$

You can get a lower bound of $\Omega(n^{3/2})$ as follows. Consider the number of steps it takes to get from $n$ to $n/2$. Since at each step, $n$ decreases by at most $\sqrt{n}$, this takes at least $\sqrt{n}/2$ steps. At each such step, we accumulate at least $n/2$, for a total of at least $n^{3/2}/4$.
You can prove a matching upper bound using a similar approach. While the input parameter is at least $n/2$, it decreases by at least $\sqrt{n/2}$, and so it takes at most $\sqrt{n/2}$ steps to get to $n/2$. During each such step, we accumulate at most $n$, for a total of at most $n^{3/2}/\sqrt{2}$. An identical argument shows that at most $(n/2)^{3/2}/\sqrt{2}$ is accumulated while going from $n/2$ to $n/4$, and so on. Hence
$$
T(n) \leq \frac{n^{3/2}}{\sqrt{2}} \left(1 + \frac{1}{2^{3/2}} + \frac{1}{4^{3/2}} + \cdots\right) = O(n^{3/2}),
$$
since the geometric series inside the parentheses converges.
Numerical experiments suggest that
$$
T(n) \sim \frac{2}{3} n^{3/2}.
$$
We can show this heuristically as follows. Let us imagine that $T$ is a recurrence in continuous time. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and so
$$
T'(n) \approx \sqrt{n}.
$$
Integrating, we get
$$
T(n) \approx \frac{n^{3/2}}{3/2} = \frac{2}{3} n^{3/2}.
$$
This can probably be showed by running the argument above more carefully (replacing $n/2$ with $(1-\epsilon)n$).


How to determine the size of training data using VC dimension?

Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can correct for the training error and repeat.

The bound obtained through usage of VC dimension could be very pessimistic, and I don't know how useful it is in practice. Perhaps your instructor will address this later on in the course (or perhaps the issue will be swept under the rug).


Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and  $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.

In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not just selection, which is known to be impossible.


There is no compelling reason that I'm aware of.  The hash algorithm would also work about as well with an initial value of 0, as far as I can see.


Finding A String Using A Suffix Array/Table

Sure: the longest stored suffix is the string itself.

In a suffix array, it's particularly easy to find: scan the array for starting index $1$ -- the suffix starting at the first character is, quite obviously, the string itself.


Describe a Turing machine that accepts a word iff there are twice as many 0's as 1's

Roughly speaking, the machine could act as follows:

Scan the input, looking for a 1 entry.
If no 1 entry is found, check that there are no 0 entries left, and halt at an accepting or rejecting state accordingly.
If a 1 entry is found, erase it.
Look for a 0 entry. if none is found, halt at a rejecting state. Otherwise, erase it.
Repeat step 4 one more time.
Go back to step 1.

When erasing an entry, you should change it to a symbol different from the blank symbol, so that you will be able in the future to scan through the entire breadth of the work.

If you have multiple tapes, you could try the following algorithm instead:

Scan the input. Whenever you see a 0, copy it to auxiliary tape 0. Whenever you see a 1, copy it to auxiliary tape 1.
As long as there are 1s in auxiliary tape 1: erase a 1, and erase two 0s from auxiliary tape 0; if there are not enough 0s, reject.
Accept iff there are no 0s in auxiliary tape 0.

This is a more efficient variant of the first algorithm.


Identifying useless vertices in a directed graph

Let $n$ and $m$ be the number of vertices and edges of your input graph $G = (V,E)$, respectively.
You can find all useless vertices in time $O(n+m)$.

You can discover the set $S$ all vertices reachable by at least one source in $O(n + m)$ overall time.

You do this by either:

running one visit from each of the input vertices, marking discovered vertices as visited, and taking care of not revisiting already visited vertices; or
adding a dummy "super-source" vertex $s$ with an outgoing edge towards every input vertex in $G$, and then running a visit from $s$.

By using the same technique on the reversed graph $G^R$, you can find the set $T$ of all vertices that are reachable from an output vertex in $G^R$. In other words a vertex $v$ can reach an output vertex in $G$ iff $v \in T$.

The set you are looking for is then $V \setminus (S \cap T)$.


Every complete subgraph $K_n$ contained in a graph $G$ can be considered as an induced subgraph of $G$. Note that, by definition, an induced subgraph is formed from a subset of the vertices of the original graph along with all of the edges connecting pairs of vertices in that subset.


Because in general $p(v_i \mid a_1 \dots a_n) \ne \prod_j p(v_i | a_j)$.  There is no reason to expect that equation to hold with equality.  You can't just write down an equation and hope that it is true; you have to be able to justify it from the axioms of probability, and you can't justify the equation you want to hold.

Remember that $p(A \mid B)$ is not the same as $p(B \mid A)$.  The two probabilities can be very different.  Be careful not to confuse them, or you will definitely get very mixed up.

In general, if $A,B,C$ are events, then $p(A \mid B,C)$ is not necessarily equal to $p(A \mid B) \times p(A \mid C)$.  It is easy to come up with a counter-example.  For instance, suppose I toss a fair die, and define the following events: $A$ = "the die came up 5", $B$ = "the die is showing an odd number", $C$ = "the die is showing a prime number".  Then $p(A \mid B,C) = 1/2$, $p(A \mid B) = 1/3$, $p(A \mid C) = 1/3$, and $1/2 \ne 1/3 \times 1/3$.

The reason why you can write $p(a_1 \dots a_n \mid v_i) = \prod_j p(a_j \mid v_i)$ is because $a_1,a_2,\dots,a_n$ conditionally independent on $v_i$: once $v_i$ is fixed, then $a_1,a_2,\dots,a_n$ become independent.  In general, if $A,B$ are conditionally independent on $C$, then $p(A,B \mid C) = p(A \mid C) \times p(B \mid C)$ -- this is in fact the definition of conditional independence.  That's why $p(a_1 \dots a_n \mid v_i) = \prod_j p(a_j \mid v_i)$ is justified.  (However, no such justification is available for $p(v_i \mid a_1 \dots a_n) \ne \prod_j p(v_i | a_j)$.)

If you are not familiar with the concepts of independence and conditional independence, I suggest reviewing a standard probability textbook, where you can find more on that subject to help you practice and become proficient with those concepts.


Relationship between Undecidable Problems and Recursively Enumerable languages

Are all undecidable problems recursively enumerable languages?

No. See my answer to your third question.

  If there is a problem which belongs to the class of non recursively enumerable
  languages, will it be always undecidable?

Yes. In particular, recursive (decidable) languages are a subset of the recursively enumerable languages, so anything that's not recursively enumerable isn't recursive (decidable).

  Also could any one suggest a problem which is not even recursively enumerable?

The complement of the halting problem is not recursively enumerable. Suppose that it were. Then you could begin recursively enumerating the set $H$ of halting programs at the same time that I'm recursively enumerating the set $H'$ of non-halting programs. Every program would eventually be listed by one of us; if you listed it, you'd shout "accept" and I'd stop enumerating, and if I listed it, I'd shout "reject" and you'd stop enumerating. We'd have an effective procedure for deciding the halting problem.

Note that this generalizes: the complement of any recursively-enumerable (but non-recursive) problem is non-recursively-enumerable, for the reason outlined above.


Data addresses with ADD instruction in various architectures?

First some terminology:

Let's consider the ADD operation that is a logically three operand operation: two sources and one target, so these 3 are the maximum that could be provided.

A (hardware) machine instruction is subdivided into fields, the main one of which is the opcode field.  The instructions can also be fixed-length or variable length.

An addressing mode is a way of specifying what memory address (i.e. data address) to use for reading or writing.  The architectures that you are asking about vary in the instructions that allow for addressing modes as fields in the instruction.  Typically, the fields associated with an addressing mode require a fair number of bits, such as 12, 16, 20 or more because they contain parts of memory addresses.

In a stack-based architecture, operations such as ADD implicitly target the stack, for both sources as well as for the target.  So, an ADD instruction has just one field, the opcode field, and will have no instruction set fields regarding source and target.  Initial operands are moved to the (expression) stack using PUSH instructions and popped of this stack using STORE (or POP) instructions.  It is the PUSH & STORE instructions that have the potential to indicate sources and targets that reference memory (e.g. data addresses).  The following accomplishes an ADD in a stack architecture.

PUSH  item1
PUSH  item2
ADD
STORE item3

item1, item2, and item3 would be considered addressing modes within those instructions, and might allow access to local variables and global variables.  Because the PUSH & STORE instructions have additional fields beyond the opcode whereas the ADD instruction does not, stack machine architectures typically use varying length instructions.  The hardware advances the PC by the right amount for each instruction so that it can execute the logically following instruction.  When several computations (multiple ADD or ADD & SUB, etc..) are combined the stack machine can use the stack to transfer intermediate computations without intervening PUSH & POP instructions.

In an accumulator-based architecture, you will typically have opcodes with one addressing mode.  The following sequence would be typical of them:

LOAD  item1
ADD   item2
STORE item3

You can see that a similar code sequence has one less instruction, and the instructions tend to be more regular.  As a result of this, accumulator machines might choose a fixed length instruction set (e.g. 16-bits).  The accumulator is implicitly sourced and targeted and does not require an instruction field.

A RISC register architecture, like MIPS will have a large number of registers (e.g. 32 or more), and support three operand instructions, though only between registers.  Memory operations will require separate LOAD and STORE instructions.

LOAD  r1, item1
LOAD  r2, item2
ADD   r3,r1,r2
STORE r3, item2

Here we have a longer sequence for the same operation; however, the RISC machine has so many registers that the idea is to use them instead of memory for local variables and such.  Thus, many of the loads and stores you might otherwise expect are eliminated.

x86, for the most part, is two operand machine.  It has more registers than your single accumulator machine, but fewer than a RISC machine.  Most instructions on x86 allow specifying a register number and an addressing mode, which might refer to another register or might refer to a memory addressing mode.

MOV AX, item1
ADD AX, item2
MOV item3, AX

Like the RISC machine, the 8 or so registers can be used for heavily used local variables, reducing the memory access.  However, will fewer registers the advantage isn't as good as with a RISC machine.

There are considerable trade-offs between these various architectural approaches to instruction set architecture.  Generally speaking, the stack machines result in smaller code space, because of their variable length instruction sets.  Code space has a huge impact on instruction cache performance, so the smaller the code, the better.  However, by comparison with RISC machines with their fixed-size instructions, the variable length instructions (and more of them) require substantially more complex decoding hardware, which either costs transistors or sacrifices performance.


Turing machine for unary encoded quadratic numbers


Find palindrome in directed Graph where edges are either blue or red

Here's a possible algorithm.
Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, b) \to (c, d)$ in $G'$ where two edges $c \to a$ (note the order) and $b \to d$ exist in $G$ with the same color.
Then to find an odd-length palindrome you simply check if $(s, t)$ is reachable from any $(x, x)$ in $G'$. To find an even-length palindrome check if $(s, t)$ is reachable from any $(a, b)$ in $G'$ under the condition that $a \to b$ exists (regardless of color) in $G$.

The idea is to extend the palindrome from the middle out. The vertices $(l, r)$ in $G'$ represent the leftmost and rightmost symbol in our palindrome, and the way we constructed the edges in $G'$ corresponds to all valid ways to extend the palindrome.


What is the difference between broadcast and gossip/epidemics?

While sometimes used as synonyms, to me, gossiping protocols are certain flavor of broadcast algorithms, where the message is flooded in a non-structural (commonly, random) way and spreads to the network.
In contrast, a non-gossiping broadcast algorithm may, for instance, deliver the message via a (predetermined) spanning tree, rather than let the message spread arbitrarily.
See, e.g., https://www.gsd.inesc-id.pt/~ler/reports/joaoleitaomsc.pdf


Answering your questions one by one:

The rules are part of an operational semantics, which defines how to evaluate expressions.
The notation with the horizontal line is an inference rule: if all the logical statements above the line are true, then you can conclude that the statement below the line is also true.
The arrow is a predicate that indicates that the left hand side can be evaluated (or reduced) to the right hand side.
The expressions separated by a comma form a tuple; for example, $A_p, cmd_1$ is a pair consisting of $A_p$ and $cmd_1$.
$\mathrm{dom}(f)$ returns the domain of the function $f$, that is, the set of values $x$ for which $f(x)$ is defined.

In these rules, $A_p$ is a state object: a function that maps variable names to values. (Think of it a bit like the heap on which you can allocate objects, and where the variable names are pointers.) The VAR rule performs variable lookup in that state:

If the statement above the line is true: $x \in \mathrm{dom}(A_p)$, that is, the function $A_p$ is defined for the argument $A_p(x)$,
Then the statement below the line is true: $A_p, x \Longrightarrow A_p(x)$, that is, the expression $x$ in the state $A_p$ can be evaluated to $A_p(x)$, which is just the value of the function $A_p$ when you pass in the variable name $x$ as argument.

Hope that helps. For more details, lecture notes on operational semantics (e.g. these from Cambridge) will further explain the notation.


Difference in Sorting 32- and 64-bit Integers

Yes.  For instance, sorting a million 5-bit integers is a lot easier: use counting sort.  And sorting a million long strings is a different question than sorting a million 32-bit integers.

In the case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an in-memory sorting algorithm (e.g., quicksort) rather than an external sorting algorithm.  If we didn't know the size of the items we were sorting, we wouldn't know whether they would fit in memory and thus wouldn't know whether it's more appropriate to use an in-memory sorting algorithm or an external sorting algorithm.


Is ROM primary memory or secondary memory?

The distinction between primary and secondary storage relies on several joint characteristics which the prototypical examples – RAM and hard drives – satisfy:

Primary storage can be accessed directly by the CPU. Access is fast. Data is volatile – it is lost when power is turned off.
Secondary storage cannot be accessed directly by the CPU. Access is slow. Data is non-volatile – it is retained even when power is turned off.
Tertiary storage is similar to secondary storage, but can only be accessed via a network device. Access is even slower.

Where does ROM fall into this classification? The typical usage of ROM in computing (according to Wikipedia, now falling out of use), is for booting. When the computer is started, the CPU is directed to start running from some address, which is memory mapped to read-only memory* containing instructions for booting the system. This kind of memory satisfies the first two properties of primary storage listed above, but not the third property.
(In reality, ROM can be writable – say it is really an EPROM – and sometimes it is really battery-backed RAM.)
Complicating the picture, some I/O devices are memory mapped, and so in this sense can be accessed directly by the CPU. This is (or at least, used to be) common for video. Does video memory count as primary storage or as secondary storage?
What these examples show is that the classification has its limits. The purpose of such classifications is to help us conceptualize how computers work. They shouldn't be taken too seriously – they don't apply in a clean way to all possible situations.


How can a TM M' have a property P if it only accepts a single string x from language of P?

I think I got it. Here is Rice's Theorem (Rice Theorem and Turing machine
b ehavior prop erties):

I looked it up here: Decidability for the definition of a problem in the context of Turing Machine (slides 9 and 11):

  Formally, a problem is a language.
  Each string encodes some instance.
  The string is in the language if and only if the answer to this instance of the problem is “yes.”

  A problem is decidable if there is an algorithm to answer it.

  Recall: An “algorithm,” formally, is a TM that halts on all inputs,    accepted or not.
  Put another way, “decidable problem” = “recursive    language.”

  Otherwise, the problem is undecidable

That answers why I only need one string w and reduced x from w to prove a language L with property P is undecidable.

According to Rice's Theorem, if language L with property P has Turing Machines that does not accept language of L, L is undecidable. Thus:

$$L_{p} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n})\}$$
$$L'_{NotInp} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n}) \}$$

$$M_{i}\mspace{8mu} \text{is}\mspace{8mu} \text{an}\mspace{8mu} i\text{th}\mspace{8mu} \text{Turing} \mspace{8mu} \text{machine},\mspace{8mu} i ≤ n. $$

If the language L' (which contains TMs not in P) is not an empty set, the above L sub P is undecidable. Recall that language with property P is decidable if and only if it is trivial, which means either it contains every RE languages or not at all. Since if a language L with property P is decidable, every Turing Machines accept every string in L, so we don't need to test the acceptance of input to a given TM.

Also, according to the definition of a problem in the context of Turing Machine, if we have the answer (an algorithm) to every instance of the language L sub P (obviously, since L sub P contains every TM), L sub P is decidable. Otherwise, it's not.

Let's be more concrete with an example from here: More Reduction Examples

Aside from the proof given on the page, let's look at it more intuitively. We may have Turing Machine M which accepts the three strings. Other than that, the input w can be anything which is not in M, but belong to other M'. Input w can be "Not UIUC", "Not Iowa", or "Not Michigan" or any other strings which do not belong to M. Since we do not have the answer to every instance of the problem with M (because if we do, M will accept every string since every string has property P. In this case, it's not). The language is not trivial, thus it is undecidable.

This is my reasoning. What do you think?


Prove { | TM M on input 3 at some point writes symbol "3" on the third cell of its tape} is recursively enumerable but not recursive

First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the third cell, we can do the simulation without looping. Thus, if TM $R$ exists, we can decide $A_{TM}$, but we know that $A_{TM}$ is undicidable, by contradiction, we can conclude that $R$ doesn't exist. Hence, $S_3$ is undecidable.

Let's assume $S_3$ is decidable so we can obtain contradiction by having TM $R$ decides $S_3$, and construct TM $M'$ to decide $A_{TM}$ as follows.

$M'$ = $``$On input $\big \langle M, 3 \big \rangle$:

Run TM $R$ on input $\big \langle M, 3 \big \rangle$.
If $R$ rejects, $reject$.
If $R$ accepts, simulate $M$ to write symbol $``3"$ on the third cell of its tape.
If $M$ has accepted, $accept$; if $M$ has rejected, $reject$."

Clearly, if $R$ decides $S_3$, then $M'$ decides $A_{TM}$. However, since $A_{TM}$ is undecidable, so we know $R$ doesn't exist and hence $S_3$ must be undecidable.


How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent of siblings.

Yes, it is. The parent of $A\to a$ is $S \to A_1 A_2$. $S$ has two children, both of which are instances of $A$. And the rule for  $S \to A_1 A_2$ assigns values to the inherited attributes of both children.
That's precisely what an inherited attribute is. Inherited attributes (which are inherited from the parents in the parse tree) can be used in the synthesized rules for those non-terminals, which is what is happening in the rule for $A$.


The notations $a(n) = O(b(n))$ and $O(a(n)) = O(b(n))$ have different meanings:

$a(n) = O(b(n))$ means that $a(n)$ belongs to the collection of functions $O(b(n))$. That is, $a(n) \in O(b(n))$.
$O(a(n)) = O(b(n))$ means (in this particular case) that the two collections of functions $O(a(n))$ and $O(b(n))$ are the same. That is, $c(n) = O(a(n))$ iff $c(n) = O(b(n))$.  (Usually $O(a(n)) = O(b(n))$ actually means $O(a(n)) \subseteq O(b(n))$.)

Big O notation is thus ambiguous, but in practice there is usually no confusion.


How an I prove if this language is decidable or not

Consider two cases:

$L_1$ is finite, and so there is a word of maximal length.
$L_1$ is infinite, and so there are words of arbitrarily large length.

Try to see if you can decide $L_2$ in these two cases.


is co-NP-hard contained in EXPTIME-hard or vice-versa?

It is known that co-NP $\subseteq$ PSPACE $\subseteq$ EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every $L\in$ EXPTIME to it, and therefore also from every $L\in$ co-NP)

Therefore EXPTIME-hard $\subseteq$ co-NP-hard.

Note that this argument does not hold for co-NP-complete and EXPTIME-complete. This is still an open problem (i believe).


What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

There is no such thing as a "correct" name. There is the name that is commonly used, which might depend on the community. This is what you would use unless you want to make a point. If you think that the common name doesn't give credit to the right people, you can use a different name, though you should also mention the common name so that others know what theorem you refer to.

Mathematical theorems and concepts are often named not after the first people who proved or defined them (if you're interested, you should be able to find several lists of such theorems and concepts online). Yet once a name has stuck, it is different to change it. That is because the most important goal of a name is not to give credit but rather to give a short name for a common concept. Indeed, sometimes results are not named after anybody, even though many of them were first proved by somebody.


How does it possible that $ZPP=RP\cap coRP$?

The complexity class P is obviously contained in their intersection (since the probability to err on either side is zero), so the intersection isn't empty.

(The complement of a complexity class isn't the same as the complement of a specific language.)


A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"

Recall the padding lemma: given $\langle M \rangle$ we can compute $\langle N \rangle$ where $N$ is equivalent to $M$, but has a longer representation. (Essentially, we can always add more irrelevant states to a TM, effectively.)

Then, define $E_0$ to do the following:

Run $E$ until $M_1$ is produced.
Let $N_1 = M_1$
Output $N_1$
Continue running $E$ until $M_2$ is produced.
Let $N_2$ be $M_2$, after as many paddings as needed to make its representation larger than $N_1$.
Output $N_2$
Continue running $E$ until $M_3$ is produced.
Let $N_3$ be $M_3$, after as many paddings as needed to make its representation larger than $N_2$.
Output $N_3$
And so on.

By construction, $E_0$ prints larger and larger strings, hence its enumerated language is decidable: this is the wanted language C.

We now need to check the quivalence. For any $N_i$ in the language enumerated by $E_0$, we find an equivalent $M_i$ enumerated by $E$. Vice versa, for any $M_i$ in the language enumerated by $E$, we find an equivalent $N_i$ enumerated by $E_0$.


What does $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$ in this paper mean?

You're over-thinking it. It just says that, if $t_0$, ..., $t_{n-1}$ are in $T^0_\Sigma$ and $\sigma$ is a symbol in the alphabet $\Sigma_n$, then the string consisting of $\sigma$, followed by $($, followed by... is in $T^0_\Sigma$


Combinations and Permutations of M sets of distinct items?

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to

for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2.
for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of size 2.
for each element in $B$, pair it with each element in $C$. This gives us $|N_B||N_C|$ combinations of size 2.

In total, this gives us as $ |N_A||N_B|+|N_A||N_C|+|N_B||N_C| = 3\times2 + 3\times4 + 2\times4 = 26$

What we have done above is to take all possible combinations of the sets in $M$ (set combinations of size 2 are $AB, AC, BC$), taken the product of all their sizes, and finally added them up.

In general, given $n$ sets in $M$, and we want to know the number of $k$ sized combinations. The high-level algorithm would be as follows

for each k-sized set combination of sets in M
  multiply the sizes of all the sets in the k-size set combination
  add this product to the final result

This can be written briefly as
$$ \sum_{\substack{S \subseteq M\\|S|=k}}\prod_{X\in S}{|X|}$$

Now, to generate all unordered combinations of size $k$, we follow the same steps as the above algorithm, but instead of taking the product of set sizes, we perform a cross product on all the sets in each $k$-size set combination.

Combinations(M,k):
  if |M| == 1
    return { {e} | e in any set of M }

  M[1] = first set in M

  if |M| > k
    Result = Combinations(M\{M[1]} ,k)
  else
    Result = {}

  Temp = Combination(M\{M[1]},k-1)

  for each element e in M1:
    make a copy of Temp called Dummy
    to each set in Dummy, add e
    add all the elements in Dummy to Result

  return Result


How to find a perfect matching with this constraint?

We consider three different cases: $\alpha < 1$, $\alpha = 1$, and $\alpha > 1$.

Suppose first that $\alpha < 1$. Arrange the $n^2$ elements in the matrix in non-increasing order: $x_1,x_2,\ldots$. Note that $x_1,\ldots,x_n$ must belong to the diagonal, and moreover $\alpha x_n \geq x_{n+1}$. Hence the instance is solvable iff $\alpha x_n \geq x_{n+1}$ and $x_1,\ldots,x_n$ belong to different rows and columns.

The case $\alpha = 1$ is very similar. Let $x_1 = x_2 = \cdots = x_m > x_{m+1}$. If $m = n$ then we are back to the previous case. If $m < n$, then $x_1,\ldots,x_m$ must belong to the diagonal. We find out whether it is possible, fix this part of the permutation, and iterate (details left to you). The most interesting case is when $m > n$. In that case, we use a bipartite perfect matching algorithm to find out whether $n$ of these $m$ elements can be put on the diagonal.

The case $\alpha > 1$ is slightly more complicated. Let $A$ be the list of elements larger than $\alpha x_n$. All of these elements (if any) must belong to the diagonal in any solution, since the diagonal always contains an element at least as small as $x_n$. If $A \neq \emptyset$, we first check that they can be put in the diagonal, fix this part of the permutation, and iterate. If $A = \emptyset$, then we check whether the first $n$ elements can be put on the diagonal. If so, we have found a solution. Otherwise, we know that the solution must contain an element at least as small as $x_{n+1}$ on the diagonal, and we let $A$ be the list of these elements. If $A \neq \emptyset$, we do what we did before. Otherwise, we use a bipartite perfect matching algorithm to try and fit $x_1,\ldots,x_{n+1}$ on the diagonal (deleting first elements conflicting with the current partial permutation). If so, we have found a solution. Otherwise, we continue with $x_{n+2}$. Eventually we will have made a conclusion, since when reaching $x_{n^2}$ the answer is positive.


Just some general observations.

O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
A Θ(n log n) running time can have many different components, for instance

$\qquad\displaystyle a \cdot n\log n + b \cdot n \log \log n + c \cdot \sqrt n + d \cdot n + e \cdot \log n + d$

While technically the linearithmic term dominates, if $a$ is small compared to the other coefficients you will have a hard time detecting it.
Measuring wall-clock running time is noisy without end, inparticular because the coefficients mentioned above get skewed by platform details. Try investigating counts, for instance of a dominant operation or block.
Linear regresssion always works. Since the "difference" between $n \log n$ and $n$ is rather small (also considering above point), it's not susprising you'd get a high confidence. Run linearithmic regression and compare!


Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

There are two standard kinds of approaches to this sort of problem.

Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
Explore a sweep line algorithm.  In this sort of algorithm, we envision $p$ increasing from 0 upward as time progresses, and at each point in time, we keep track of the set of all intervals that contain $p$.  Thus, when $p$ hits the left endpoint of an interval, we add it to the set; when it reaches the right endpoint, we remove it from the set.  You can store the set as a balanced binary tree data structure, and then make it persistent using standard path copying techniques.  Now that you have this persistent data structure that captures all points in time, often you can find a way to solve your problem fairly rapidly.  Crucially, the tree will be of size $O(n \lg n)$ and depth $O(\lg n)$, so accesses are fast.

I haven't explored either of those approaches in the context of your particular problem, but these are two general techniques that are often useful for problems of this sort.


Proving complexity by reduction using strongly NP-hard problem

I will assume that your definition is the one on Wikipedia.

We wish to prove that $X$ is strongly NP-Complete. Here's how you do that. First, show that $X$ is strongly NP$^1$. Next, find a strongly NP-Complete problem $Y$ and reduce $Y$ to $X$. That is, provide an algorithm which takes an instance $y$ of $Y$ and produces $f(y)$ such that if $y\in Y$ then $f(y)\in X$ and otherwise, if $y\not\in Y$ then $f(y)\not\in X$.

I remember in which way to reduce a problem (was it $X$ to $Y$ or $Y$ to $X$?) by framing it as a conversation which I've laid out here in this other answer(link): someone challenges me by saying $X$ is easy. Then I say, nonsense, if $X$ were easy, then I could solve very hard problem $Y$. And then I show how to do that: I take an instance of $Y$, rewrite it into an instance of $X$, and then you're done. You've shown that $X$ is at least as hard as $Y$, so we write $Y\leq X$.

$^1$ best I can figure, strongly NP means it has logarithmically-sized certificates


Given NFA to recognize a language, construct a new NFA for that language without the empty string

Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.

Define a DFA $M_{\epsilon}^{-1}$ for the language $\Sigma^* \setminus \{\epsilon\}$. Hint: it has two states for any $\Sigma$.
Say how to construct $M'$ such that $L(M') = L(M) \cap L(M_{\epsilon}^{-1})$. Hint: use the Cartesian Product Machine construction.


Creating all possible subsets and complexity calculation

Your code doesn't really generate all subsets, but it does go over all subsets. The complexity of your code depends on the complexity of the data structures you use, which you'll have to figure out yourself. The proverbial "innermost loop" in your case is the if (i >= M), and this part runs $2^M$ times (once for each subset). If the complexity of the innermost loop is $C$, then the overall complexity of the code would be $O(2^M C)$, since the complexity of all other parts pales in comparison.


The Entropy of the phrase "Eile Mit Weile"

The two answers agree, with the following change: it's 1.63263 nats, not bits. That is, the value 1.63263 is calculated using the natural logarithm.


I would use the term I/O interface to refer to the set of CPU instructions that one uses to read and write data from or to an I/O device.  There are generally two parts to this.

One is the interrupt mechanism, by which I/O devices can communicate asynchronous information to the CPU.  Generally there is a pin, or several pins, on the CPU chip package that can be used to trigger an interrupt.  Triggering an external interrupt on most CPU architectures will cause the processor to save some (or all) of its register state and jump to a predetermined location to run the interrupt service routine.  (On some architectures there is a way of triggering different interrupt routines for different purposes, while on others there is a single external interrupt routine and there needs to be additional communication done in the interrupt service routine to figure out which device needed service.)

The second part is the way that data gets communicated back and forth between the CPU and the I/O device.  This is generally done one of two different ways: memory mapped or "port mapped".  In memory mapped I/O the registers on the I/O device are mapped to particular locations in the CPU's memory space, and the CPU uses normal load and store instructions to read and write those registers.  In port mapped I/O the registers on the I/O device are mapped to particular locations in something called "port space."  The instructions you use to access the I/O device's registers are often called something like in and out, but they are pretty similar to load and store instructions.  There are other possibilities that get more complicated, but I've probably already given you more detail than you want.

For every specific device there is then some set of device registers that need to be read and/or written with specific values in some specific order. The protocols for what you need to read/write in which registers can get exceedingly complex.

To make this clearer let me give you an example.  Let's take the PC keyboard (from the old days before we had USB).  Here is the first thing that came up when I googled: http://www.oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_20/CH20-2.html#HEADING2-1.  The keyboard controller has two 8-bit registers mapped to port addresses 60h and 64h (hexadecmial).  You read these registers using inb and outb instructions which moves data between the ports and the CPU registers.

The keyboard will additionally cause an interrupt to interrupt number 9 (out of 255) every time a key is pressed or released.  So the interrupt service routine associated with interrupt 9 reads port 64h and looks at bit 1 to see if there is a data byte ready. If there is it reads the byte out of port 60h and copies it into some memory buffer for software to read later.  (The reason you do the test is that several different hardware devices may be sharing the interrupt.)


Please provide me a solution of Max-Heapify using Recursion Tree

Try to solve the recurrent by expanding equality case:

$$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$

Now you can see $T(n) = \Theta(\log_{\frac{3}{2}}(n))$. Because each time $\Theta(1)$ is added up to reach to the leaf of the expnasion tree.
Also, you can reach this result using the master theorem.


Optimizing hash table for common subset of keys?

Yes, it's sometimes possible to optimize hash tables based on expected key values (i.e. make certain classes of keys at the expense of other classes). But I don't see how there could be one in your case.

There are two ways to potentially make hash tables faster: use a hash function with fewer collisions, and use a hash functions that's faster to calculate. But they pull in opposite directions: you can either make the hash function faster or better, not both.

Hash functions are designed to spread out likely key values in the first place. So if you have “typical” input, there's nothing to be gained here.

For example, if you're making exact string comparisons, then the fact that the strings are encoded in UTF-8 doesn't affect the way the hashes are calculated. The hash function looks at all the bytes of the string anyway, and has a low probability of collisions except for specially-crafted data. A hash function specialized to pure-ASCII strings won't be faster to calculate (operations are on bytes anyway, even on words, not on individual bits) nor have more collisions (repeated bit patterns like “all upper bits are 0” is something typical hash functions are designed to cope with).

An example where you can gain performance for typical cases is when the key for the hash table is a large data structure, such that there's a gain to be made by hashing only part of the data structure. Say the key consists of both a name and some large extra data, and most keys have different names, but occasionally there are distinct keys with the same name. Then you might use a two-level table: first hash on the key, and then, only in buckets where there is more than one entry, calculate the hash of the extra data.

In the case of a string, the closest thing would be to hash only a prefix. But that typically gives bad results in practice; for example, in a compiler, it's very common to have large sets of identifiers with a common prefix.

Another case where a simpler, partial hash function can be useful is when equality between keys is hard to test. This may be the case with Unicode strings if you need to treat different representations of the same text as equal, e.g. treat combining characters as equivalent to non-canonical forms. In this case, you may want to avoid doing the work of normalizing each string. However that wouldn't help for the pure-ASCII case, since normalizing a pure-ASCII string is easy. It might help with typical “tame” uses of Unicode (sticking to characters that are common in one language).

A hash table is not necessarily the best structure to represent a mapping from keys to values. Search trees or tries have many advantages. Balanced search trees have guaranteed $O(\lg(n))$ behavior, whereas hash tables are harder to protect against deliberately-crafted key sets (not so much an issue in compilers, but it can be an issue when interpreting code from an untrusted source, e.g. a web browser running Javascript code from some random website). Hash tables are pretty much impossible to share intelligently — you have to copy the whole table. With trees, on the other hand, sharing comes naturally. Sharing is very often useful in compilers, between scopes that differ only on a few identifiers.


Three Partition-Function Algorithms Comparison

Your implementation of the Euler method doesn't use memoization, so you keep computing and recomputing the same values. This is like computing the Fibonacci numbers along the following lines:

Fibonacci(n)
  if n = 0 or n = 1, return n
  otherwise, return Fibonacci(n-1) + Fibonacci(n-2)

You should modify the implementation so that after calculating eulerPartition for a certain $n$, if you are given the same $n$ again then you immediately return the previously calculated value.


How to check if a list of XY coordinate meet the safety distance to each others?

The problem you are solving has many well-known efficient algorithms.

The problem is to find closest pair of points in the plane.
If the closest pair have distance less than the safety distance, you already have a pair.
If not, no other pair can have a less distance, and hence all pairs are safe.

One efficient way to solve this problem is using divide and conquer. The algorithm is practical and easy to implement. It has run-time $O(n \log n)$ (check the notes at the end).

It might be an over-kill, but as efficient from the theoretical point of view, to build Delaunay-Triangulation over the set of points and compare each point to its neighbors in the triangulation, which is also achievable in $O(n \log n)$.

There are many libraries that offer a ready-to-use Delaunay-Triangulation (you can check CGAL-Boost library for C++), which makes it an easier way to implement that the previous method.

ps. Another very well-known approach, used in many different problems is line-sweep. There is also a line-sweep $O(n \log n)$ algorithm for Closest pair of points problem. (please check the link).


What are differences between Static Scope and Dynamic Scope?

In static scope the $fun2$ takes the globally scoped $c$ which comes from scope where function is defined (opposite to dynamic, where it traverses scopes of execution), so $c = 3$.
With dynamic scope traverses up the chain of scopes until it finds variable it needs, which reflects the fact that scopes are:
Global($a=1, b=2, c=3$) -> main($c=4$) -> fun1 ($a=2, b=3$) -> fun2.
fun2 in the way up finds $a=2, b=3$ in fun1 and $c=4$ in main.
By the way: C has static scope rules.


Language of CFG: $S \to aS | aSbS | \varepsilon$

Let $w \in L$ be a word of length $n$. If $n = 0$ then clearly $w \in L(G)$, so suppose that $n > 0$. For $0 \leq i \leq n$, let $\delta_i$ be the difference between the number of $a$s and $b$s in the first $i$ characters of $w$; thus $\delta_i \geq 0$ for all $i$. We now consider two cases:

Case 1: $\delta_i > 0$ for all $i > 0$. In that case $w = ax$ for some $x \in L$. Induction tells us that $x \in L(G)$, and so $w \in L(G)$.

Case 2: $\delta_i = 0$ for some $i > 0$. In that case $w=axby$, where $|axb| = i$ and $x,y \in L$. Induction tells us that $x,y \in L(G)$, and so $w \in L(G)$.


Gate/transistor number and program length measures of computational complexity?

Two well-known books in this research area are:

  Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984

and

  F. Tom Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, 1991.

The connection between space and time complexity is due to the finite speed of communicating across distance.  Thus, a lot of the interesting results are about how various communication networks can (or cannot) be embedded in 3-dimensional space.


What is the relation between an algorithm and its implementation at the level of code?

An algorithm is a method for performing some task; an implementation is an expression of that method in a particular language.


social network analysis - relations between people with weights

First a few comments/questions about your approach:

Why do you think your problem has anything to do with minimum spanning trees? I fail to see the connection.
Why is your graph directed when the original problem seems to state that the "know eachother" relation is symmetric? (if A knows B then B knows A)
For your "greedy post-processing" can you do better than looking at all possible  subsets of D? In other words, how does your MST help you compute the correct subset?

Then to answer your question:
If I understood you correctly, the problem you want to solve is a weighted version of dominating set. It is NP-Hard and thus unlikely to be solvable efficiently in the worst case when the number of people increases.
By googling "minimum weight dominating set" you will however find approximation algorithms, heuristics or "practically efficient" algorithms which might do the trick if the number of people in S is not too large (or the specific instance happens to be nice enough). I'm not sure how well they would perform for your considered graph size.
Alternatively, if the number of people in S is really not large (say fewer than 25) then you might consider simply brute-forcing through every possible subset of S.


Generating a set of minimal-length strings that, together, invoke every production of a context free language

In a nutshell

Not knowing enough the literature, I worked out a solution which is
presented in the next section, together with a proof for the hardest
part. Once I knew what was needed, I could search the literature for
the right ideas. Here is a quick presentation
of the algorithm, based on the literature, which is essentially the
same I developed.

The first thing to do is to find a size-minimal terminal string
$\sigma(U)$ for every non-terminal $U$ of the grammar. This can be
done by using Knuth's extension to conc-or graphs (also known as CF
grammars) and and-or graphs of Dijkstra's shortest path algorithm.
Example B in Knuth's paper does what is needed, almost.

Actually, Knuth computes only the length of these terminal strings,
but it is quite easy to modify his algorithm to actually compute one
such terminal string $\sigma(U)$ for each non-terminal $U$ (as I do it
in my own version below). We also define $\sigma(a)=a$ for every
terminal $a$, and we extend $\sigma$ as usual into a string
homomorphism.

Then we consider a directed graph where non-terminals are the nodes,
and there is an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha
V\beta$. If several such rules can produce the same arc $(U,V)$, we
keep one such that the length $|\sigma(\alpha\beta)|$ is minimal.
The arc is labeled with that rule, and that minimal length
$|\sigma(\alpha\beta)|$ becomes the weight of the arc.

Finally, using Dijkstra's shortest path algorithm, we compute the
shortest path from the initial non-terminal $S$ to each non-terminal
of the grammar. Given the shortest path for a non-terminal $U$, the
rule labels on the arcs may be used to get a derivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then, to every rule of
the form $U\rightarrow\gamma$ in the grammar, we associate the
size-minimal terminal string $\sigma(\alpha\gamma\beta)$ which can be
derived using that rule.

To achieve low complexity, both Dijkstra's algorithm and Knuth's
extension are implemented with heaps, AKA priority queues. This gives
for Dijkstra's algorithm a complexity of $O(n\log n +t)$, and for
Knuth's algorithm a complexity $O(m \log n +t)$, where there are $m$
grammar rules and $n$ non-terminals, and $t$ is the total length of
all rules. The whole is dominated by the complexity of Knuth's algorithm since $m\geq n$.

What follows is my own work, before I produced the short answer above.

Deriving the solution from the useless symbols elimination algorithm.

There are several aspects to this algorithm. For better intuition I
chose to present it in three successive versions that introduce
progressively more features. The first version does not answer the
question, but is a standard algorithm for useless symbols elimination that suggests a solution. The second version answers the question without the minimality constraint, The third version gives an answer to the question, satisfying thye minimality constraint.
This third solution is then improved by using an adaptation to
and-or graphs of Dijkstra's shortest path algorithm.

The end result is a very simple algorithm, that avoids reconsidering computations already done. But it is less intuitive and does require a proof.

This answer only tries to answer the question as made precise by the OP's
comment: "for each production rule, I want to generate a minimal
string that takes the parser from the start state, through the
production being tested, to a set of terminals." Hence I only try to
get a set of strings such that for each rule, there is a string in the
set that is one of the size-minimal strings of the language having a
derivation using the rule.

It must be however noted that the fact that a string "invokes" a rule,
that is has a derivation using that rule, does not necessarily means
that the rule will be considered by a parser that work with ambiguous
grammars and resolves ambiguities arbitrarily. Handling such a
situation would probably require more precise knowledge of the parser, and
might well be a more complex question.

The basic algorithm

To solve this question, one can start with the classical algorithm for useless
symbols removal in context-free grammars. It is in section 4.4, pp
88-89, of Hopcroft & Ullman, 1979 edition. But the presentation here may be a bit different.

The algorithm aims precisely at proving the existence of such a covering as
requested by the OP, and consists in two parts:

lemma 4.1 of H&U, page 88: removal of all unproductive non-terminals. This
is done by trying find for each terminal a terminal string it can
derive on. A simple way to explain it is as follow: You create a
set $Prod$ od productive symbols, which you initialize with all
terminals. Then for each rule, not yet processed, that has all its
right-hand-side (RHS) symbols in $Prod$, you add the left-hand-side
(LHS) non-terminal to the set $Prod$, and you remove all rules with the
same LHS  non-terminal from the set of rules to be processed. You iterate the process until there is no rule left with
all its RHS symbols in $Prod$. The remaining non-terminals, not in $Prod$ at the end of this process,
are non-productive: they cannot be derived into a terminal string,
and can thus be removed from the grammar.
lemma 4.2 of H&U, page 89: removal of all unreachable
symbols. This is done by the classical node reachability in
directed graphs, by considering non-terminals as nodes and having
an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha$ such that
$V$ occurs in $\alpha$. You create a set $Reach$ of reachable
symbols which is initialized with only the initial symbol $S$. Then,
for every non-terminal symbol $U$ in $Reach$ or later added to it,
and for every rule $U\rightarrow \alpha$, you add to $Reach$ all
the symbols in $\alpha$. When all non-terminals in $Reach$ have
been thus processed, all symbols (terminal or non-terminals) that
are not included in $Reach$ cannot appear in a string derived from
the initial symbol, and are therefore useless. Thus they can be
removed from the grammar.

These two basic algorithms are useful to simplify the raw results of
some grammar construction techniques, such as used for the
intersection of a context-free language and a regular set. In
particular, this is useful in cleaning up the results of general CF
parsers.

Useless non-terminal symbols removal is necessary in the context of
solving the question asked, as the rules using them cannot be
"invoked" (i.e. used in its derivation) by any string of the language.

Building a set of string that invoke every rule

(We are not looking yet for minimal strings.)

Now answering specifically the question, one must indeed remove all
useless symbols, whether unreachable symbols or unproductive
non-terminal symbols, a well as useless rules having such useless
non-terminals as LHS. They have no chance of being ever invoked
usefully while parsing a terminal string (though some may well waste
the processing time of a parser when they are not removed; which ones
may waste time depends on the parser technology).

We now consider, for each (useful) rule, the production of a terminal string that
invokes it, i.e. that may be generated by using this rule. This is
essentially what is done by these two algorithms above, though they do
not keep the information, as they are satisfied with proving the
existence of these strings to ensure that non-terminals are both
reachable and productive.

We modify the first algorithm (lemma 4.1) by keeping with each
non-terminal $U$ in the set $Prod$ a terminal string $\sigma(U)$ it
derives on: $U\overset{*}{\Longrightarrow}\sigma(U)$. For every terminal we define the $\sigma$ as the
identity mapping. When $U$ is added to the set $Prod$ because a rule
$U\rightarrow\gamma$ has all its RHS symbols in $Prod$, then we define
$\sigma(U)=\sigma(\gamma)$, extending $\sigma$ as a homomorphism on strings, and we remove all $U$-rules, that is all rules with $U$ as LHS.

We modify the second algorithm (lemma 4.2) by keeping with each
non-terminal symbol $U$ added to $Reach$ the path used to reach it
from the intial symbol $S$, which gives the successive rules to get a
derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$.

Then, for each rule $U\rightarrow\gamma$ in the grammar, we produce a
terminal string that "invokes" this rule as follows. We take from the
result of the second algorithm the derivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then we apply the rule
to get the string $\alpha \gamma \beta$. A terminal string
"invoking" the rule $U\rightarrow\gamma$ is $\sigma(\alpha \gamma \beta)$

Building a set of minimal strings that "invoke" every rule

We ignore the issue of eliminating useless symbols, which can be a
by-product of these modified algorithms.

Building a set of minimal strings relies on first getting a minimal
derived string for each non-terminal. This is done by further
modifying the first algorithm (lemma 4.1). First we remove from the
set of rules to be processed all recursive rules (i.e. with a LHS
symbol occurring in the RHS string). It is obvious that none of these
rules can derive to a shorter terminal string than the non-recursive
rules with the same LHS. And there must be at least one non-recursive
rule if the LHS is not a useless non-terminal (because
non-productive).

Then we procede as before to build the set $Prod$ of productive
symbols, associating with each synbol $U$ a terminal string, which we
note $\sigma(U)$. The string $\sigma(U)$ is produced as before by
application of the rule $U\rightarrow\gamma$, substituting each
non-terminal $V$ occurring in $\gamma$ with $\sigma(V)$. So far, it
was necessary to apply this to only one rule with a given non-terminal $U$
as its LHS, the first that would have all its RHS non-terminals in
$Prod$, and then ignore the others, because any such derived string
would do. But we are now looking for a minimal derived string. Hence,
for a non-terminal $U$, this has to be done for all rules with $U$ as
LHS. But we keep only one terminal string $\sigma(U)$, replacing the
current one by the newly found one, whenever the new one is smaller.

Furthermore, whenever the string $\sigma(U)$ is replaced by a smaller
one, all rules with an occurrence of $U$ in the RHS that had been
already processed have to be put back in the set of rules to be
processed, since change allows deriving their RHS on a shorter string.
So doing this will call for more iterations, but will eventually end
since none of these strings ever gets much shorter than the empty
string.

At the end of this first algorithm, the string $\sigma(U)$ is one of
the smallest strings that can be derived from $U$. There may be
others.

Now we also have to modify the second algorithm to get, for every
non-terminal $U$, (one of) the shortest string containing U as the
only non-terminal. To do this, we keep the same directed graph with
non-terminals as nodes, and having an arc $(U,V)$ iff there is a rule
$U\rightarrow \alpha V \beta$. But now we put weights on the arcs, to
compute the minimum length of the terminal context that has to be
associated with reachable non-terminals. The weight associated with
the arc $(U,V)$ above is the length $|\sigma(\alpha\beta)|$, where the
mapping $\sigma$ is extended to terminals as the identity, and then
extended again as a string homomorphism. It is the length of (one of)
the shortest terminal strings that can be derived from the string
$\alpha\beta$. Note that $V$ is removed in this calculation. HOwever,
when there are several occurences of $V$ in the RHS, only one must be
removed.  There may be several possible $(U,V)$ arcs, with different
weights, if there are several rules with $U$ as LHS and $V$ in the
RHS. In such a case, only (one of) the lighter such arc is kept.

In this graph, we no longer look just for reachability of nodes from
$S$, but for the shortest weighted path that reaches every node from
the initial symbol $S$. This can be done with Dijkstra's algorithm.

Given the shortest path for a non-terminal $U$, we read it as before
as a sequence of rules, from which we get a dérivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then to every rule of
the form $U\rightarrow\gamma$ in the grammar, we produce a minimal
terminal string that "invokes" this rule as
$\sigma(\alpha\gamma\beta)$

Remark: The same minimal string may probably be used for several rules. But the fact
that one of the strings uses a rule $\rho$ in its derivation does not
necessarily mean it is a minimal string for that rule $\rho$, as it may have
been found for another rule, while a shorter one can be found for $\rho$.
It may be possible to increase the likelyhood that the same minimal
string will be found for several rules by using some priority policy
whenever there is flexibility. But is it worth the trouble?

A faster algorithm for minimal terminal string deriving from a non-terminal

Building the function $\sigma$ such that $\sigma(U)$ is a minimal
terminal string deriving from $U$ is done above with a rather naive
technique that requires iteratively reconsidering work already done
when a new smaller derived string is found for some non-terminal. This is wasteful, even if
the process will clearly terminate.

We propose here a more efficient algorithm, that is, in essence, an
adaptation to the CF grammar graph of an extension of Dijkstra's
shortest path algorithm to and-or graphs, with a proper definition of
the path-concept for an and-or graph. This variant of the
algorithm probably exists in the literature (assuming it is correct),
but I have been unable to find it in the resources I can access.
Hence I am describing it in more details, together with a proof.

As previously, we first remove from the set of rules to be processed
all recursive rules (i.e. rules with a LHS symbol occurring in the RHS
string). It is obvious that none of these recursive rules can derive
to a shorter terminal string than the non-recursive rules with the
same LHS. And, for a LHS $U$ there must be at least one non-recursive
$U$-rule if the symbol $U$ is not a useless non-terminal (because
non-productive). This is not strictly necessary, but reduces the
number of rules to be considered later.

Then we procede as before to build the set $Prod$ of productive
symbols, associating with each synbol $X$ a terminal string, which we
note $\sigma(X)$, which is a size-minimal terminal string derivable from
$X$ (in the previous algorithm, that was true only after
termination).The set $Prod$ is initialized with all terminal symbols,
and for each terminal symbol $a$, we define $\sigma(a)=a$.

Then we consider every rule $U\rightarrow\gamma$ such that all RHS
symbols are in $Prod$, and we choose one such that $\sigma(\gamma)$ is
size-minimal. Then we add $U$ to $Prod$, with $\sigma(U)=\sigma(\gamma)$,
and remove all $U$-rules. We iterate until all productives
terminals have been entered in $Prod$. Any non-terminal $U$, once entered in
$Prod$, never has to be considered again to change $\sigma(U)$ for a
smaller string.

Proof:

The previous algorithms were more or less intuitively obvious.
This one is a bit trickier, because of the and-or character of the
graph, and a proof seems more necessary. All we need is actually the
following lemma, which establishes the correctness of the algorithm
when applied to the last iteration.

Lemma: After each iteration of the algorithm, $\sigma(X)$ is a size-minimal
terminal string derivable from $X$, for all $X$ in $Prod$.

The base step is obvious, since this is true by definition for all
terminals in $Prod$  when it is initialized.

Then, assuming it is true after some non-terminals have been added to
$Prod$, let $U\rightarrow\gamma$ be the rule chosen to add a new
non-terminal to $Prod$. We know that this rule is chosen because
$\gamma\in{Prod}^*$ and $\sigma(\gamma)$ is size-minimal over all RHS of all
rules with a RHS in ${Prod}^*$. Then $U$ is added to $Prod$, and we have only
to prove that $\sigma(\gamma)$ is a size-minimal terminal string
derivable from $U$.

This is obviously the case for all derivations beginning with the rule
$U\rightarrow\gamma$, since by induction hypothesis, application of mapping $\sigma$ is such that all
non-terminals in $\sigma$ are substituted with size-minimal terminal strings
deriving from them. Hence no other derivation can produce a shorter terminal string.

We thus consider only derivations starting with another $U$-rule
$U\rightarrow\beta$, such that
$\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$,
where $\Sigma$ is the set of terminal symbols.

If $\beta\in{Prod}^*$, then a minimal string it can derive on is
$\sigma(\beta)$. But, since we chose the rule $U\rightarrow\gamma$, it
must be that $|\sigma(\beta)|\geq|\sigma(\gamma)|$. So the rule
$U\rightarrow\beta$ does not derive on a smaller terminal substring.

The last case to consider is when $\beta\notin{Prod}^*$, and we then
consider a derivation $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$.
If that derivation involves only non-trminals in $Prod$, then
$\beta\in{Prod}^*$, which is a case we have already seen. Hence we consider only
derivations that have steps using a rule with its LHS not in $Prod$.
Let $V\rightarrow\alpha$ be such a rule, such that
$\alpha\in{Prod}^*$.There must be at least one such rule since they
are partially ordered by derivation order, and $w\in{Prod}^*$.

Thus we have $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu
V\nu$. We know that $\mu$ and $\nu$ derive on a string of
size at least 0, and since no $V$-rule with a RHS in ${Prod}^*$ was chosen, they
derive on terminal strings of length at least equal to
$|\sigma(\gamma)|$. Hence, with the rule $U\rightarrow\beta$, $U$
derives on a terminal string of length at least equal to
$|\sigma(\gamma)|$.   $\blacksquare$


Can we define the Functor Category in Haskell (or any other language with a more expressive type system)?

Ed Kmett has actually defined this in his Hask library. The trick is to define a natural transformation as a data type and encoding the functors that this natural transformations map, in the type level like this:

class (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f
instance (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f

data Nat (p :: i -> i -> *) (q :: j -> j -> *) (f :: i -> j) (g :: i -> j) where
  Nat :: ( FunctorOf p q f
         , FunctorOf p q g
         ) => {
           runNat :: forall a. Ob p a => q (f a) (g a)
         } -> Nat p q f g

Now he defines the Natural transformation as instances of a Category like this:

instance (Category' p, Category' q) => Category' (Nat p q) where
   type Ob (Nat p q) = FunctorOf p q
   id = Nat id1 where
     id1 :: forall f x. (Functor f, Dom f ~ p, Cod f ~ q, Ob p x) => q (f x) (f x)
     id1 = id \\ (ob :: Ob p x :- Ob q (f x))
   observe Nat{} = Dict
   Nat f . Nat g = Nat (f . g)
   unop = getOp

All of this can be found here: https://github.com/ekmett/hask/blob/master/src/Hask/Category.hs


What is Harrison hashing, its applications in web search engines?

I think you are looking for Implementation of the Substring Test by Hashing by Malcolm C. Harrison. It describes a fast implementation, which determines if one string contains a specified substring. This technique is appropriate in searching of large static text files.

Also you can find in String Searching Algorithms By Graham A. Stephen.


How to test if my implementation of tree/graph data structures are correct?

Identify the representation invariants.  Add assert statements to check that the representation invariant holds (sometimes called a repOK function).  Use random testing to generate millions of test cases, and check that no assert ever fires.

Build a reference implementation of the abstract data type that implements all of the methods, but instead of using your data structure, implements the same semantics using some known-good data structure (e.g., a simple list or something).  Use random testing to generate millions of test cases, and check that in every case your implementation produces the same results as the reference implementation.

This isn't perfect but it'll probably be pretty good.