What roadblocks are there to HSA becoming standard, similar to floating point units becoming standard?

A couple issues come to mind:
Synchronization/Communication overhead
In order to seamlessly transition from CPU to GPU code you need to communicate with the GPU. The GPU additionally has to be available(aka not rendering the screen), and all instructions on the CPU side of things need to retire/finish executing. Additionally you need to make sure that any pending writes have reached L3 cache/main memory, so that the GPU sees writes. As a result a transition to GPU code is quiet expensive, especially if the GPU is doing something latency sensitive(like rendering the next frame of something), and you need to wait for that process/task/thread/whatever to finish. Similarly returning back to the CPU is also expensive.
In addition you have to handle what happens if multiple CPU cores start fighting over the GPU.
Differing Memory Performance Needs
GPUs typically require high bandwith memory, but low latency is not as important, while CPUs are typically more sensitive to low latency.
Low performance GPUs can and do use main memory, but if you wanted a high performance GPU built into the CPU you would potentially need two different types of memory. At which point there isn't much advantage to having everything on one chip, since all that does is make cooling harder.
Inertia/Dev Infrastructure
SIMD has compiler support right now and lots of work put into it. Simple GPU style workloads like dot products are already memory bound anyway on a CPU, so existing CPU+GPU combos would not benefit.
Could just have lots of SIMD
Not much more to say beyond heading. SIMD+Many cores+lots of execution units would give you a more GPU like CPU. Add better SMT for a bonus. See Xeon Phi for a real world implementation of this concept. Though one thing worth mentioning is silicon spent on more GPU style features is silicon not spent on branch prediction etc.
Edit:
Another thing that comes to mind is there are broadly speaking three reasons to have a GPU.

Just want to browse the web, display Netflix etc. For this use case existing CPU and GPU performance/architecture is more than sufficient.
Want to play high end videogames etc. Existing architecture has a lot of momentum behind it, and I'm not convinced gaming CPU workloads really need better SIMD performance, and instead need better cache/branch etc, though I don't really know. However the GPU is likely already busy so it might not be the best idea to shift even more work to the CPU
HPC applications. Custom hardware like Xeon Phi is available for people who need a more GPU like CPU.


Be careful. Even mastering the tools for compiler construction, handling a very complex preexisting language (which LaTeX certainly is) is an arduous task. Add that there is no firm syntax for LaTeX (there are certain overall conventions, but lots of special cases) makes it worse.

But to really be of any guidance, we'd need a whole lot further detail: What kind of documents? Can you define the format, or is it a corpus of preexisting texts? Do they use the same packages? Are they written to some rigid format or "anything goes? What do you want to extract? (If it is e.g. all the "exercise" environments it is very simple ---but the contents will depend on all sorts of external definitions, finding/including that isn't simple. Solution is to require manual fixups, but that negates the "automation" aspect).

Go also to TeX.SE for LaTeX related questions.

Good luck!


How does the computation scale?

Keep reading!  The paper describes how this scales for $n$, in the very next line after the excerpt you show.  In particular, the next line is Proposition 1, which states the running time of computing the subproduct tree, as a function of $n$.  That tells you how the running time scales for large $n$.

How do you compute the coefficients?

Follow the algorithm described in the paper!  You already described the algorithm.  Use exactly what you described.

Don't the coefficients become large, when $n$ is large?

Yes, potentially.  This is inherent to the task: if you want to compute some polynomial (the product) whose coefficients are large, then yes, the coefficients produced by such an algorithm will be large.  This is pretty much a tautological statement.


How unallocated memory space is represented?

Each page of RAM is typically a 4k block, with a set of privileges on it such as read, write, or execute. Broadly speaking, the memory manager for the operating system will allocate a bunch of pages for OS related storage, and when a program launches, it will allocate initial RAM, and as more items are allocated, the program will ask the operating system for more RAM.

From the program's point of view, the RAM is all contiguous. However, under the hood, the operating system is mapping the various blocks of system RAM, and each program's RAM.

Physically, the RAM is broken up into blocks, which are essentially unorganized, but the operating system itself has a table mapping what block belongs to each program.


Role of computational power in recent AI developments

This is a broad question, but from the presentations I've seen, there have been three major factors that all have come together over the past decade or two:

More data.  Machine learning algorithms rely upon having many instances, so we can train them.  The more data we have (the more labelled instances we have), the better the algorithms do.  On some of the harder problems people are tackling today, machine learning algorithms only start to do well once you give them millions or billions of examples.  For example, speech recognition is a prime example of this: researchers in the field have told me that progress in speech recognition was closely related to the size of the data sets available for training.  Over the past decade or two, large data sets have become available: it's become possible to train algorithms using every image on Flickr, or every video on Youtube, or every call ever made to Google Voice.  That wasn't possible two decades ago.
More computational power. Processing that much data requires efficient algorithms.  One significant advance was that researchers found out how to use GPU's (graphic cards) as specialized processors: implementing the machine learning algorithm on a GPU could speed up the training process by 10x - 100x.
Better algorithms. Deep learning has been having some significant successes over the past five years or so.  This is a result of decades of hard work.  There's a small subcommunity of researchers who have been working on neural networks for decades, and who have slowly been making progress, finding what kinds of neural networks work well.  They've invented many new algorithmic ideas: autoencoders, stochastic gradient descent with mini-batches, ReLU activation functions, drop-out for regularization, convolutational neural network structures.

It has taken the combination of all of these new algorithmic ideas, plus larger data sets, plus new ways of implementing the algorithms efficiently so we can make effective use of the large data sets, to achieve these gains.  This is a real success story for the field.

Sometimes you hear the stereotype of a lone inventor sitting in their garage, who one day has a "Eureka!" moment and comes up with a brilliant invention fully-formed in a flash of insight.  However, that's typically not how research progresses.  Deep learning is a good example of that.  It has taken decades of work and gradual improvement, exploring many ideas that ultimately didn't pan out, with researchers building on incremental advances and new ideas from other researchers, to reach where we are today.  An inspiring example for the impact of long-term fundamental research.


Is the time reversal symmetry of non-deterministic computations important?

The time reversal symmetry is already important for decision problems. It translates into reversal of the accepted language. The trick is to replace total functions by partial functions, and don't consider "yes"/"no" as output of the problem. Instead, the "yes"/"no" is derived from the existence of a path between start and end state. This is explained for finite automata in my answer to the question "Why is non-determinism useful concept?", and elaborated for more powerful machines like pushdown automata, Turing machines and probabilistic machines in my answer to the question "What is the difference between non-determinism and randomness?".

This raises the question whether deterministic context-free languages are closed under the reversal of $L$, because this is the only one of the examples where the deterministic and the non-deterministic languages are not identical.

The importance of the time reversal symmetry is not necessarily limited to the decision problem. It might be possible to also work out its consequences for the counting problem and the function problem.


Regarding Backus' Commentary on von Neumann-style Programming

Reading the quote literally without the interpolated interpretation, I think what Backus is saying is that a powerful language is one which makes no distinction between expressions and statements.
That is, where all statements are also expressions, like a functional language.
I don't think Backus was claiming that an "all statement" language - the meaning of which is not entirely clear in this context - would be powerful or even feasible. Rather, he is claiming that the existence of certain statements that cannot be analysed as expressions, is a defect in language design.


ANN - Backpropagation with multiple output neurons

Backpropagation works for feed-forward ANNs with multiple output neurons.

For an output neuron $z_r$ in an ANN, the delta function is

$$
\delta_r = \frac{\partial f_r(a_r)}{\partial a_r} e_r\qquad,
$$
where $f_r(a_r)$ is the activation function of $z_r$, $a_r$ is the sum of weighted inputs of $z_r$ and $e_r$ is the error of $z_r$, $e_r$ = $z_r$ - $y_r$ ($y_r$ is the target value).

for a hidden neuron $z_k$ the delta function is the sum of weighted deltas of the neurons in the next layer (in forward direction) of $z_k$. So, for a neuron in the layer next to the output layer, the delta function is:

$$
\delta_k = \frac{\partial f_k(a_k)}{\partial a_k} \sum_{r\in post(k)}\delta_r w_{kr}\qquad,
$$

where $w_{kr}$ is the weight between neurons $z_k$ and $z_r$. I suggest to have a look at the Wikipedia article about Backpropagation, especially the subsection 'finding the derivative of the error'. Following the link at the end of this section (https://www4.rgu.ac.uk/files/chapter3%20-%20bp.pdf), the first five pages or so might be helpful for a better understanding.


Given a TM $T$ does $T$ ever leave the initial state when start tape is blank?

I would say it is decidable.

If I understood correctly, here's what I think.

First of all a TM starts from some initial state $s_0$. How can it change the state? In your transition function you have something like $(s_0, x) \to (s_i, y, m)$ where $s_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s_0, \_)$ to some state not $s_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.


Lower bound for comparison algorithm - checking whether permutation is odd or even

Hint: Show that if you know the parity of the input permutation then you know the entire permutation, and so you can sort the list.

In more detail, the information that you have at any leaf of the decision tree can be represented as a partial order on the elements. Show that if this partial order is not linear then it has a linear completion which is an odd permutation and another linear completion which is an even permutation.


How I can find all equivalence classes by Myhill-Nerode?

$\Bbb N$ denotes the set of natural numbers, that is, the set $\{0,1,2, \cdots\}$. If $\Bbb N$ is the set of positive integers, the treatment will be roughly the same.

  So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

Since the above paragraph in the question, $z=z(C)$ is understood/redefined to be the set of words such that Cz is a subset of $B$, given a set of words $C$. That is, $cw\in b$ for any $c\in C$ and $w\in z$.

With the above understanding, yes, $z([\lambda]_{\equiv_{B}})=z(\{\lambda\})=B.$

  $3: \left[73 a^{k}\right]_{\equiv_{B}}=\left\{73 a^{k}\right\}  $ for $  k \in \mathbb{N} $

Case 3 gives one equivalent class for each $k\in\Bbb N$. It lists infinitely many equivalent classes as the following, each with different $z$.

Letting $k=0$, we have $\left[73\right]_{\equiv_{B}}=\left\{73\right\}\,.$
Letting $k=1$, we have $\left[73 a^1\right]_{\equiv_{B}}=\left\{73 a^1\right\}\,.$
Letting $k=2$, we have $\left[73 a^2\right]_{\equiv_{B}}=\left\{73 a^2\right\}\,.$
Letting $k=3$, we have $\left[73 a^3\right]_{\equiv_{B}}=\left\{73 a^3\right\}\,.$
$\vdots$

Their $z$'s are the following, which are more or less listed in the question.

$z\left(\left[73\right]_{\equiv_{B}}\right)=z\left(\left\{73 \right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+2\right\} \,.$
$z\left(\left[73 a^1\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^1\right\}\right)= \left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+1\right\} \,.$
$z\left(\left[73 a^2\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^2\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m\right\} \,.$
$z\left(\left[73 a^3\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^3\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m-1\right\} \,.$
$\vdots$

Once you have understood the above, it should be easy to figure out case 4 and the rest of the given solution. You did have a pretty good understanding of the  Myhill-Nerode equivalence classes.

Here is another way to write the same solution in the question.

$1: [\lambda]_{\equiv_{B}}=\{\lambda\}  $

$2: [7]_{\equiv_{B}}=\{7\}  $

$3: \left[73\right]_{\equiv_{B}}=\left\{73\right\}$

$4: \left[73a\right]_{\equiv_{B}}=\left\{73a\right\}$

$5: \left[73a^2\right]_{\equiv_{B}}=\left\{73a^2\right\}$

$6: \left[73a^3\right]_{\equiv_{B}}=\left\{73a^3\right\}$

$\vdots$

$\infty+1: \left[73 a^2 7\right]_{\equiv_{B}} =\left\{73 a^{2+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+2: \left[73 a^3 7\right]_{\equiv_{B}} =\left\{73 a^{3+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+3: \left[73 a^4 7\right]_{\equiv_{B}} =\left\{73 a^{4+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+4: \left[73 a^5 7\right]_{\equiv_{B}} =\left\{73 a^{5+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\vdots$

$2\infty+1: [3]_{{\equiv B}}=\Sigma^{*} \setminus\left([\lambda]_{\equiv B} \cup[7]_{\equiv B}  \cup\left(\bigcup_{k \in \Bbb{N}}\left[73 a^{k}\right]_ {\equiv_{B}}\right) \cup \left(\bigcup_{k \in \Bbb{N}}\left[73a^{k+ 2} 7\right]_{\equiv_B}\right)\right)\,. $

Exercise. Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
give all equivalence classes of the Myhill-Nerode relation. (Check here for an answer.)


The formula is wrong. The notation $f = O(g)$ is asymmetric, and has the meaning $f \in O(g)$. For more, check our reference question on Landau notation. Other relevant reference questions are this one and this one.


You are right!

The work $W$ at each node (of level $i$), splits into $Wa_1, Wa_2, \dots, Wa_k$ at level $i+1$.

If you add them up, you get that the total work at level $i+1$ is $a_1 + a_2 + \dots + a_k$ times the total work at level $i$.

Of course, this assumes that your $\Theta(n)$ is some exact $cn$, but this argument is good enough to prove that $T(n) = O(n)$. Proving $T(n) = \Omega(n)$ is trivial.

btw, I recommend you look at Akra-Bazzi as a useful tool, if you are interested in such questions.


Algorithm to assign producers to consumers with respect to connections

I'm not sure I understand the problem statement, but it looks like this can be modelled as a network flow problem.  Here's how.  First, create a new source vertex $s_0$.  Then, for each producer $p$, if its capacity is $c_p$,  and add an edge $s_0 \to p$ with capacity $c_p$.  Do that for every producer, then look for a max flow in the resulting flow graph.


What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory?

Maybe currying is the syntax you refer, and passing arguments as functions:

const sum = (a, b, c) => a + b + c;
const partial = a => b => c => sum(a, b, c);

console.log(partial(1)(2)(3));          // 6


Regular expression of a language over {a,b,c} which does not contain substring bbb

The following regular expression (where $\cdot$ stands for $a|b|c$) will match all strings with lengths divisible by 3 not containing the string $bbb$ and not starting with a b.

$((a|c)\cdot\cdot)^*$

Can you modify this to get the expression you want?


Weakest precondition (WPC) can be computed with a procedure that takes your program, as well as the given postcondition (in this case, x=y), as inputs, and applies certain rules on how the precondition is computed for each part of the program (e.g. how to compute WPC for an if statement), until it reaches the point of computing the precondition for the whole program. Now, since the program you've given is a sequence of statements, this procedure will compute WPC for each of these statements and effectively start with computing WPC for the last statement and "propagate" WPC back to the first statement in the sequence.

In order to understand computation of WPC, it's good to be aware of some relevant notions like the semantics of the programming language your program is given in, i.e. what each statement means, (for your example the semantics is quite straitghforward), the way the WPC is computed according to rules that depend on the given part of the program and its semantics, and then specific rules on how WPC is computed for the given language. (Some links to useful materials are given at the end.)

Specifically for your program, which we will label for more convenient notation of P[x..y], which designates the program part consisting of lines from x to y

1. x := y + 1;
2. if (y > 0) then
3. x := x + y
4. else x := y + 100;
5. x := x + y;

the procedure for computing WPC would be given as

wpc(P, x==y) === wpc(P[1..5], x==y) === wpc(P[1], wpc(P[2..5], x==y))

where we use === for equivalence on the top-level (not be confused with assignments = and equality == in the language), and in turn

wpc(P[2..5], x==y) === wpc(P[2..4], wpc(P[5], x==y))

as P[2..4] represents the if statement. Now,

wpc(P[5], x==y) === wpc(x := x + y, x==y) === x + y == y === x = 0

given the rule for handling assignments, wp(x:=E,R) = R[x ← E],
which says that, intuitively, in order for some condition to hold after the assignment of x is executed, same condition should hold before that assignment, where instead of x we have the right-hand side of the assignment, since that will exactly be the value of x after assignment is done.

The next step is computing wpc(P[2..4], wpc(P[5], x==y)), i.e. wpc(P[2..4], x=0), since based on the WPC computation we discussed above, wpc(P[5], x==y) === x==0.

Now, there is again one statement (the if-condition) and one postcondition. (Note that you've written this postcondition two times, once for each branch of the if statement).  Without going into all the details, the WPC computation would follow the rule for conditionals, i.e. wp( E  S_1  S_2 ,R) = (E ∧ wp(S_1,R)) ∨ (¬E ∧ wp(S_2,R)), which guarantees the postcondition is satisfied if either branch is taken, thus the WPC becomes a logical OR between WPCs for each branch computed separately, i.e.

wpc(P[2..4], x==0) === (y > 0) & wpc(x := x + y, x==0) | !(y>0) & wpc(x := y + 100, x==0)

which is the same as the condition you wrote

(y > 0 & x + y = 0) | (y =< 0 & y=-100) === (y > 0 & x + y = 0) | (y = -100)

where WPCs for both branches are computed similarly as given before, as both of them represent assignments.

There are many good resources that cover program semantics and generation of verification conditions (including the computation of weakest precondition): some of them are mentioned on Wikipedia, while some courses like the "Program Analysis" course provide good views on the material and might represent a good step to start.


Deciding on decidability of a problem and reducing it to halting problem if not decidable

The first language is semidecidable while the second one is not semidecidable.

Claim 1: $L_1 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$ is semidecidable.
Proof: On input $w\#x$ Simply simulate $M_w$ on $x$ and count the number of visited states. If the counter reaches $|Q|$ then ACCEPT. This shows $L_1$ is semidecidable/RE.

Claim 2: $L_2 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$ is not semidecidable.
Proof: Let $L_2$ be semidecidable. Then since $\overline{L}_1 = L_2$, i.e., $L_1$ and $L_2$ are complement of each other, $L_1$ (and so $L_2$) is decidable. In this case we can reduce the Halting problem to $L_1$ as following. Let $M$ be a Turing machine deciding $L_1$. We construct a Turing machine that decides the Halting problem. On input $w\#x$ we modify $M_w$ so that when $M$ halts, it first traverses all other states and then halts. We could do it by changing the ACCEPT state to a normal state, introducing a new ACCEPT state, and adding the following new transitions $$\delta(q_1, a) = q_2, \dots, \delta(q_n, a) = q_{new-accept}$$ where $a$ is a new alphabet symbol and when the modified $M_w$ is at the state $q_{old-accept}$ it first writes $a$ on the tape and enters the state $q_1$ (without moving the head, i.e, the head always reads $a$). Similarly for the the REJECT state. Thus $M_w(x)$ halts if and only if $M_w$ visits all states, which is decidable by $M$.


How to statically type polymorphic lambdas using hindley milner style type inference

You should use a polymorphic lambda calculus, e.g. System F for representing typed terms. Then, when you generalize a let binding, you also insert lambdas which abstract over types, and when you check a function application, you also insert type applications as needed. This is precisely what GHC Haskell does, and is the standard solution.

Now, your concrete example does not fit into pure H-M inference, because you seem to be using an overloaded + operation. Unless + is implemented for every type or fails at runtime for some types, (T1, T1) -> T1 is not a valid polymorphic type for add.

For a pure H-M example program, elaborating to System F would look something like the following, with input:

id := func a begin a end
a  := id 'hello'
b  := id 100

And output:

id := Func A (func (a : A) begin a end)
a  := id [String] 'hello'
b  := id [Int] 100

Where I use Func A to mean a lambda binding a type (corresponding to big lambda in System F), and id [String] to mean applying the polymorphic id to a String type. The point of type lambdas and applications is to have an explicit internal representation of polymorphic functions.


Is a language that sits between two regular languages also regular?

Any time you're asked questions like "Is a subset of a regular language always regular?" or "Is a superset of a regular language always regular?", you have the best chance if you pick the biggest possible language to take subsets of, and the smallest possible language to take supersets of. Thankfully, the biggest possible and smallest possible languages are both regular.


How to solve a DP problem that minimizes a sum of cubic powers?

The essence of the dynamic programming is to recognize the appropriate subproblems.
Here is a way to formulate the subproblems. Let us compute $dp[i]$, the minimum total waste for weight sequence $w_{i}, w_{i+}, \cdots, w_N$, where $1\le i\lt N$. The wanted minimum total waste of the entire sequence shall be $dp[1]$.
The base cases are $dp[N]=dp[N-1]=\cdots=0$, where $dp[i]=0$ as long as $w_{i} + w_{i+1}+ \cdots+w_{N}\le M$ since the last trip does not produce waste. Let $j$ be the smallest such index.
What about $dp[j-1]$, $dp[j-2]$ and beyond? We note that $dp[k]$ is the minimum of
$$\begin{align}
  dp[k+1] &+ (M-w_k)^3,\\
  dp[k+2] &+ (M-(w_k+w_{k+1}))^3,\\
  \cdots\\
  dp[k+t] &+ (M-(w_k+w_{k+1}+\cdots+w_{k+t-1}))^3\\
  \cdots,\\
  \end{align}$$
where the list goes on as long as $w_k+w_{k+1}+\cdots+w_{k+t-1}\le M$.
This recurrence relation enables us to compute $dp[k-1]$ if $dp[k], dp[k-1], \cdots, dp[N]$ are known.
The time complexity of algorithm is about $O(N*N)$.
Java code

The above is an implementation in Java that takes file "elevate.in" as input. Just click "run" to see the result.
Exercises
Here are two exercises based on the same situation to think about.
Exercise 1. (One minute or two.) Suppose the total waste is defined as $$TW=\sum_{t=2}^{S}(WF[t])^3$$ instead. Note that the WF of the first strip instead of the last strip is excluded.
Exercise 2. Suppose the total waste is defined as $$TW=\sum_{t=2}^{S-1}(WF[t])^3$$ instead. Note both the WF of the first strip and the last strip are excluded.


Searching for the value in the tree is a $O(\log n)$ task.

Then, we can visit the path leading to the value, from the leaf (the value), to the root. At every intermediate node, we know how many other values there are further on the left: none, if we moved up from the left subtree, and left.size (which is assumed to be stored in each node) otherwise.

So, we can add all the relevant size values, counting up how many other values we have on the left of our value, so retrieving the order of the value in $O(\log n)$.


Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all unaffected pairs, using $D'_j = D_j - TV_j$. The affect this has on the ratios is
$$
 \frac{D'_j - D'_{j+1}}{V_j - V_{j+1}} = \frac{D_j - TV_j - D_{j+1} + TV_{j+1}}{V_j - V_{j+1}} = \frac{D_j - D_{j+1}}{V_j - V_{j+1}} - T.
$$
In other words, their relative order does not change. However, the removed ball $i$ does affect one of the other ratios: instead of $\frac{D_{i-1}-D_i}{V_{i-1}-V_i}$ we now have $\frac{D_{i-1}-D_{i+1}}{V_{i-1}-V_{i+1}}$. So we remove the former and insert the latter instead.

Constructing the min-heap in the beginning takes time $O(n\log n)$.
Afterwards, we perform $O(n)$ operations on the min-heap, each of which runs in $O(\log n)$, and so the total running time is $O(n\log n)$.


Consequences of a language that hides his lower level rappresentations

There's plenty of precedent for this in real programming languages. One obvious example is pointers/references, which are internally just an address (probably). The language/runtime must know this, but in managed languages you don't have access to that.

One of my favourite examples of "useful information that must be there but is hidden" is in C++. You can allocate an array of objects using the new[] operator and deallocate them with delete[]:

Object* objs = new Object[25];
// do stuff to objs
delete[] objs;

C++ does not provide a way to obtain the number of elements in array. However, the delete[] operator must have access to this information, because it needs to execute the destructors of those elements.


building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

Your DFA has states $S_0$ to $S_m$ and E. You start at state $S_0$.
Any state transitions to E if the next input symbol is not a. States $S_m$ and E transition to state E on any input; state $S_i$ for 0 ≤ i < m goes to state $S_{i+1}$ on input a.
$S_i$ is an accepting state if and only if i is a prime. All other states are non-accepting.


CFG - Left factoring in recursive nested productions

You can solve this with regular expressions:

S -> a b S | T

is equivalent to

S -> (a b)* T

and

T -> a c T | d T | ϵ

is equivalent to

T -> (a c | d)*

Subtitute T into the rule for S:

S -> (a b)* (a c | d)*

Now, you can use a standard method to derive a right regular grammar.


Name of a sequence that is unknown to stop on a given input

It has many names, I first heard about it as the Syracuse problem, but the most prominent name is maybe Collatz Conjecture.


Let $f(n) = \begin{cases}
1 & \mbox{if $n$ is odd}\\
n & \mbox{if $n$ even}
\end{cases}$, and $g(n) = \begin{cases}
n & \mbox{if $n$ is odd}\\
1 & \mbox{if $n$ even}
\end{cases}$.
Then, $h(n)=f(n)+g(n) = n+1 \not\in O(f(n))$.
Indeed, for any $n_0$ and $c>0$, there is some $n \ge n_0$ such that $h(n) > c f(n)$.
Simply pick $n$ as an odd integer greater than $\max\{c, n_0\}$, e.g., $n=2\max\{c, n_0\}+1$. Then $h(n) = n+1 = 2\max\{c, n_0\} + 2 > c = c \cdot 1 = c f(n)$.
A similar argument shows that $h(n) \not\in O(g(n))$.


My answer was the following:

 Algorithm Sort(A, n)
   Input: an array A of n integers, the element of A belong to the set {0,1,2}
   Output: A is sorted
   int zero ← 0, one ← 0
    for i = 0 to n-1
    // we count the number of occurrences of each element in the array
    switch(A[i])
      case 0:
        zero ← zero + 1
      case 1:
        one ← one + 1
    // 2 would be be n - ( zero + one)
    // now we populate the array
    for i = 0 to n – 1{
      if i < zero then A[i]  = 0
      else if i < zero + 1 then A[i] = 1
      else A[i] = 2

The algorithm traverses the array twice, so its execution time is at least 2n.
I was thinking of a way to get rid of the second for loop, but I doubt it can be avoided, unless the input array is already sorted or it contains element of the same type.
In any case 2n is O(n).


Understanding sequential solution for the TAOCP 3 Million Men problem

With a for loop that steps through the array and creates a new pair from the $i$th and $(i+2)$th elements, for each $i$.
The same as the merge step in merge sort.
There are no "otherwise"s in the statement in English, so there should be no else statements.


It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$.
And the probability of success in $m$ tries is the probability of not to be failed in every try, which is $1-(1-\frac{k}{n})^m$.


Unfortunately you will always need space $\Omega(nk)$ to support your operations.

Consider all possible contents of your stream, i.e. all subsets of $[n]\times [k]$. There are $2^{nk}$ such subsets. Take two different subsets out of this, lets say $M$ and $M'$. Since the sets are different, there is an element $(a,b)$ which is contained in $M$ but not in $M'$ or the other way around. Now we perform the operation $\mathrm{Search}(a,b)$, for which the answer should be "Yes" for $M$ and "No" for $M'$ (or vice versa). It follows that both sets need a different storage content.

Moreover, this shows that each data structure needs a different storage content for each of the subsets. It follows that each data structure needs $\Omega(nk)$ bits of space to perform your operations (even without the delete operation and without constant time querying).


primitive recursion in the lambda calculus

As you mention, $1$ is primitive recursive according to the following proof:

$0$ is primitive recursive (axiom)
$\operatorname{suc}$ is primitive recursive (axiom)
$1=\operatorname{suc}(0)$ is primitive recursive (composition)

Using this you can show that $1$ is admissible, that is if you add $1$ as an axiom, the resulting set of functions is still the primitive recursive functions.

Note that lambda calculus has absolutely nothing to do with the answer.


Algorithm: turining a fraction into a decimal expansion string

All we need is a function $f$ that gives the whole part of a fraction. One can define this one using integer division:

$$f(a, b) = \lfloor a / b\rfloor$$

Finally let's assume we have routine $g(a, b)$ that reduces a fraction to its simplest form. This can be done with the Euclidean algorithm.

Let's first take the integer part of a fraction out using $f$, and reduce our fraction using $g$, giving us $\frac{a}{b} < 1$. Then we can repeatedly ask for the next decimal $d$ and continue with $10\cdot \frac{a}{b} - d$:

$d := f(10a, b)$
$a, b := g(10a - b\cdot d, b)$

This algorithm will perfectly give you all digits ad infinitum, and $g$ makes sure the numbers stay small and manageable.


Bounds on "well dispersed" sparse matrices

The answer to the main question is yes, and the key to the construction is the notion of an expander graph.

  A (bipartite $d$-left-regular) expander graph between vertices $\mathcal{I}$ and $\mathcal{O}$ (the bipartition), where $|\mathcal{I}|=|\mathcal{O}|=n$, with expansion factor $c>0$, is a graph which is $d$-left-regular, meaning that each $x\in \mathcal{I}$ has degree $d$, such that for all subsets $A\subseteq I$ such that $|A|\le n/2$, the set $B\subseteq\mathcal{O}$ of neighbors of elements of $A$ has $|B|\ge (1+c)|A|$.

There are many proofs of existence of expander graphs like this by the probabilistic method and some deterministic methods as well; for the present purpose we only need that expander graphs as defined above exist for some constant $c>0$ independent of $n$.

Given such a graph, we can construct a $n\times n$ matrix from the adjacency matrix of the graph, with $\mathcal{I}$ for the rows and $\mathcal{O}$ for the columns. This matrix has exactly $k=dn=O(n)$ ones, because of the $d$ left regular property, and the expander property is unaffected by any permutations performed by the adversary.

Now for $\alpha>0$, let $A$ be the last $\alpha n$ elements of $\mathcal{I}$ and let $C$ be the last $\alpha n$ elements of $\mathcal{O}$, after the adversary has chosen an ordering of the rows and columns. If there is no one in this square in the matrix, then there must correspondingly be no edge between $A$ and $C$, and hence the neighbors $B$ of elements of $A$ must satisfy $B\subseteq C^c$, so by the expander graph property this implies
$$(1+c)|A|=(1+c)\alpha n\le |B|\le |C^c|=(1-\alpha)n\implies \alpha\le\frac{1}{2+c}.$$

Thus any empty bottom right square must be smaller than $n/(2+c)\times n/(2+c)$, so in the language of the OP, $$f(n,k)\ge 2n\left(1-\frac{1}{2+c}\right)=(1+\epsilon)n$$
where $\epsilon=\dfrac{c}{2+c}>0$.


I believe I have found the answer: The proof is wrong. BPP_PATH is not in P_CTC because P_CTC is required to give a single definite answer, while BPP_PATH is a probabilistic algorithm, so the second reduction does not work. For it to work, one would have to use the time-travel information to count the number of successes of the probabilistic algorithm vs the number of its failures. I have no idea how to do this, or if it even can be done (probably not).


With regards too your first question I would take a different easier to understand route.
Firstly you should note that most programming languages are (theoretically) Turing-Complete (which implied that for a program written in some programming language like C or Python you could transform it into a TM or vice versa).
I'm sure that you heard of the concept "interpreter". It's a program that takes a script as input and runs it (e.g. the python interpreter). You can probably write a simple interpreter yourself (great tutorial).
Now notice that your interpreter could be converted to a TM which takes programs as inputs and runs them, thus you could construct a UTM, and the input would be e.g. a python script.
With regards to your second question: as I mentioned most programming languages used today are (theoretically) Turing-Complete meaning that you could transform any Turing-Machine too a program in this language. The straight forward approach, which works in most object oriented languages is just to model a Turing-Machine (using e.g. a string as tape and an int to remember where on the tape your head is and so on...simple example).
Algorithms that convert one program from one language to another are called transpilers.
I think I don't fully understand your last question. Of course you could plug a UTM into itself. It's like writing a python interpreter in python. The "problem" is that simulation comes at a cost. Generally if you simulate a UTM on a UTM the complexity of some operations increases.


Is Loop Invariant Proof a form of Induction?

Good question. I think yes, a loop invariant proof implies induction. However, it also deals with the termination step which is outside of the scope of induction. So a loop invariant contains an induction proof, but goes beyond that, and so an induction proof does not do all that a loop invariant proof does.

  (1) Here, showing that the invariant holds before the first iteration is like the
  base case, and showing that the invariant holds from iteration to iteration
  is like the inductive step.


Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that paper, means strict partial order.  (Yes, "strict" means "irreflexive".) (Yes, "order" can be used interchangeably with "ordering" sometimes. I prefer "order" in a mathematics environment and "ordering" in non-mathematics environment, since "order" is such a common English word.)

Informally, that "partial" means it is possible a "<" relation thereof is missing for some pairs of elements. Here is an example. Let $S=\{a,b,c\}$. We can define a relation $<_1$ on $S$ by $a<_1 b$ and $a<_1 c$. That is all. Note we did not say anything about the relationship between $a$ and $c$. In fact, we have specified that there should not be a relationship between $a$ and $c$. These two elements are incomparable. That is why we say $<_1$ is a "partial" relation on $S$.

In that paper, for example, $p_3$ and $q_3$ are two incomparable events. We cannot say $p_3\to q_3$ nor $q_3\to p_3$. The order relationship between $p_3$ and $q_3$ is missing. It is not defined. That is why it is referred as a "partial" ordering. "It can't handle concurrent events, so it's named as Partial ordering." That understanding is pretty good. However, I would phrase it as "It does not order concurrent events, ...". I mean, it does handle concurrent events, resulting in that concurrent events should be treated as incomparable.

In contrast, "a total ordering" or, a total order is a partial ordering under which every pair of elements are comparable. If you find these two math terms sound contradictory, think of them as square are also rectangles. In fact, the "total ordering" in the paper is the strict total order. Yes, you can understand that "total ordering" means "it can handle all the events in a distributed system", or "it can order every pair of events in a distributed system (as defined in the paper)".

You may find lots of terminologies in the theory of partially ordered set and order theory. It looks like overwhelming initially. However, most of the concepts are very easy to understand intuitively.

In your case, all you need to understand is how is $\to$ defined on the set of events of a system and that a total ordering is such a special $\to$ that for any two events $e_1$ and $e_2$, either $e_1\to e_2$ or $e_2\to e_1$ must hold. You could ignore all those formal concepts in math theory even though they might help understand more things later more clearly.

As mentioned by Gokul, here is a pretty good explanation about Lamports's logical clocks.


Origins of the term "distributed hash table"

The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda[Lin86]. The paper attributes the term to Rob Bjornson (which I believe to be this guy), but only cites personal communication as their mean of learning the term. [Lin86] also refers D. Gelernter: Dynamic global name spaces on network computers. (1984), which is said to propose an implementation. I didn't find the paper, so I can not say if this is true. Another report (which I didn't find as well) by Leichter is said to discuss the implementation further: Implementing the Unimplementable -- Algorithms for Linda's Tuple Space.

The source in Linda seems to be a dead end, but was the oldest source of the term that I could find. I think it could be attributed with the term, but I may be confuted. If we assume that Bjornson came up with the term, at least the time frame would be fitting. Bjornson started his work in 1984, so if he is attributed with the term, the term's origin would neatly fit into the time were the Linda papers above were written.


Lack of time hierarchy theorem for probabilistic machines

The deterministic time hierarchy theorem is based on our ability to simulate "weaker machines" (namely, those which run in time $T$ whereas the simulator is allowed to run in time $T\log T$), and know their response on a given input. This way, we can construct a machine running in time $T\log T$ which differs from every machine running in time $T$ on at least one input (simple diagonalization).

In the context of BPP however, the response on a given input (i.e. whether or not it belongs to the language accociated with the given probabilistic machine) is determined by the probability of accepting that input, namely if it exceeds some agreed upon threshold. You can of course compute this probability in a naive manner, and diagonlize just like in the deterministic case. This is similar to what you suggested, but calling this a time hierarchy theorem for probabilistic time is hardly fair, since the jumps are big enough to allow you to simply apply the deterministic time hierarchy theorem, avoiding any probabilistic issues. This does not answer for example whether or not $BPTime(n)\subsetneq BPTime(n^2)$.


Connection between NAND gates and Turing completeness

There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.

A program (or algorithm, or machine) is a mechanism for computing a function. For definiteness, let us assume that the input is a binary string $x$, and the output is a Boolean output $b$. The size of the input is potentially unbounded. One example is a program that determines whether the input is the binary encoding of a prime number.

A (Boolean) circuit is a collection of instructions for computing some finite function. We can picture the circuit as an electrical circuit, or think of it as a sequence of instructions (this view is called confusingly a straight-line program). Concretely, we can assume that the input is a binary string $x$ of length $n$, and the output is Boolean. One example is a circuit that determines whether the input encodes a prime number (just as before, only now the input has to be of length $n$).

We can convert a program $P$ into a circuit $P_n$ that simulates $P$ on inputs of length $n$. The corresponding sequence of circuits $P_0,P_1,P_2,\ldots$ is not arbitrary – they can all be constructed by a program that given $n$ outputs $P_n$. We call such a sequence of circuits a uniform circuit (confusingly, we often think of the sequence as a "single" circuit $P_n$ for an indefinite $n$).

Not every sequence of circuits is uniform. Indeed, a sequence of circuits can compute every function from strings to Boolean, computable or uncomputable! Nevertheless, in complexity theory we are interested in such non-uniform models in which the circuits are restricted. For example, the question P=NP states that NP-complete problems cannot be solved by polynomial time algorithms. This implies that NP-complete problems cannot be solved by polynomial size uniform circuits. It is moreover conjectured that NP-complete problems cannot be solved by polynomial size circuits without the requirement of uniformity.

Turing-complete computation models are models which realize all computable functions (and no more). In contrast, complete systems of gates (such as AND,OR,NOT or NAND) allow computing arbitrary finite functions using circuits made of these gates. Such complete systems can compute completely arbitrary functions using (unrestricted) sequences of circuits.


Smallest number with in a larger number with a certain length

This problem is very similar to subsequence problem that is solved using dynamic programming. So, there are several ways to solve this problem, but the algorithm that you choose really depends on the input size ($n$, $m$ and base of numbers).

I here explain the simplest algorithm. I assume that the number is given in base 10, which means that your digits are all between 0 and 9. You just need to iterate over the smallest digits first and construct the smallest possible subnumber from the digits after that.

Algorithm SmallestSubNumber(number[1:n], m)
Smallest = \inf;
For i=0:9
   For j=1:n-m
      If (number[j] == i):
          Smallest = min(Smallest, i*10^(m-1) + SmallestSubNumber(number[j+1:n], m-1));
   If (Smallest != \inf) return Smallest;


Generating the exact uniform distribution of all sudoku puzzles can be done that way: you can just randomly generate a 9x9 grid and then only keep it if it is a correct sudoku grid, otherwise retry.

This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct by $9^{17}$ only by generating a random 8x8 grid and then fill the remaining two lines. This is still a random distribution, but still way too inefficient.

You can also force the first line to be $[1, 2, .. 9]$, then randomly generate the remaining of the grid and then randomly pick a permutation of all digits. You will still pick all the grids with the same probability but $9!$ faster.

Maybe you see where I am going: answering this problem in a clever way will probably lead you to wonder about the underlying symmetries of sudoku grids. A lot of work was done in this direction to prove the fact that 17 is the minimal number of clues to a sudoku (see this article) and you can go here to see this precise enumeration of 5,472,730,538 classes of 3,359,232 similar grids, which uses these symmetries:

Permutations of digits
Permutations of rows (the bands and the rows inside each band)
Same thing for columns
Transposition

With this framework you can pick randomly one of the 5,472,730,538 classes (they can actually be compressed into 6 GB) and then pick one of the representative for each symmetry, respectively one in $9!, 6^4, 6^4, 2$.

EDIT: to adapt this to incomplete puzzles, you can choose randomly a subset of your grid, check if the solution is unique with a sudoku solver and retry if not. This is not a uniform distribution since the number of incomplete puzzles with a unique solution may be different for two grids. (I would be very surprised otherwise)


Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode

Unicode is a suitable encoding for most scripts because it includes characters from all the scripts. The analog would be an instruction set architecture that includes instructions from all processors. This would be huge and impractical to implement whether in hardware or in software. It would even be contradictory: how do you reconcile an architecture with 16-bit words with an architecture with 64-bit words? an architecture that allows unaligned word accesses with one that doesn't? an architecture that guarantees the presence of an MMU with one that guarantees that addresses used by software map directly to addresses in physical memory? an architecture that guarantees that all memory accesses take exactly the same amount of time with one that has memory caches?

A realistic ISA can't combine what all the ISA do. You have to make choices, and these choices depend on your objectives. If you're building a processor for real-time processing, a guarantee that memory accesses take the same amount of time is crucial. If you're building a processor for fast numerical or symbolic computation, caching memory accesses is essential for performance. A good instruction set for general-purpose computing is not the same as for graphical rendering, and machine learning calls for yet another approach. There is no one-size-fits-all.

Why isn't there a standard model of vehicle? Why are there so many different models of cars and airplanes and bicycles and motorcycles and helicopters and submarines and so on?


Capacity of binary not symmetrical channel

You need to compute $H(Y)$ by its definition:

$$ H(Y) \triangleq \Pr(Y=0) \log \frac{1}{\Pr(Y=0)} + \Pr(Y=1)\log\frac{1}{\Pr(Y=1)}$$

To be able to compute this formula, you need to figure out what is $\Pr(Y=1)$ and $\Pr(Y=0)$. These two measures actually depend on the distribution of $X$.

To compute $H(X|Y)$ again, use the definition.
$$H(Y|X) \triangleq \Pr(X=0) H(Y| X=0) + \Pr(X=1)H(Y|X=1)$$

where $H(Y | X=0)$ is easy to compute from the original entropy definition $H(Z)$, for a random variable $Z$ that is distributed same as $(Y|X=0)$. This is immediately given by your $P(Y|X)$.

In order to compute the channel's capacity, you will need to find the distribution $p(x)$ that maximizes $H(Y)-H(Y|X)$.

Maybe you should also check a textbook about information and entropy. For instance, try Cover & Thomas, "Elements of Information Theory", Chapter 7 (Channel Capacity).


Turing Completeness of System Which Randomly Fails to Complete Calculations

I've gone around and around on this one.  It would seem that we've landed on "No, it would not be Turing Complete, although we might be able to approximate it with a bounded probability of error on either accuracy or returning in finite time."

In your post, you said "just not reliably"... that is, in fact, a crucial part of the definition.  To be Turing-complete, we have to be able to exactly simulate a single taped Turing machine -- getting it right "sometimes" isn't any better than flipping a coin to determine if it's raining outside with "50% accuracy".

In the given example, you seem to suggest that the random failures only occur on assignment, not for other operations in the computer.  Does this affect assignments performed by the programmer alone, or internal assignments performed as intermediate steps by the compiler?  If it only affects assignments performed by the programmer, many programs could be written (in horrendously terrifying complexity and near impossible to debug) without creating and assigning any variables at all.  In this case, I suppose it would be similar to a Turing tarpit.

If the programmer HAD to assign variables, they should be able to use something in the vein of the old Heinlein "Tell me 3 times", assigning the variable in an array repeatedly (say 100 times, or until 3 distinct values have been saved) and then use the median value (since all values are x, x-1, or x+1, the median value, not median result, must be the correct one).  This would cut into performance HORRIBLY, but should, typically, arrive at correct values.  (In fairness to @DavidRicherby, I concede that we cannot ensure both that we arrive at an answer and that it is correct with 100% certainty; for a look at how we could arrive at 3 distinct values without additional assignments, consider the following approach:

# function sum : x,y $\rightarrow$ z
var a = x + y;   // first assignment, may be x, x-1, or x+1
var b = x + y;
while (a == b)
  b = x + y;     // if this loop finishes, b is now distinct from a
var c = x + y;
while ((a == c) || (b == c))
  c = x + y;     // if this loop finishes, c is now distinct from a and b
if ((a < b) && (b < c))
  return b;
if ((b < a) && (a < c))
  return a;
// repeat for the other combinations; there should be 6 total if statements.

)

If the compiler can introduce intermediate assignment operations that the programmer did not that also suffer from this drawback (say, at the end of every elementary computation), or if there are other operations affected by this glitch (the killer one in my above example being the comparison operators), then we cannot simulate a Turing-complete language (or machine) at any speed -- we will only be right 1 out of every $3^n$ times on average, where $n$ is the number of operations we can't correct for.

The Short Version of My Answer:

I can try to check for errors internally myself in the midst of computation, which may or may not work depending on the details of your system.  If I can't have or emulate a verifying system, then I cannot be Turing complete -- I'm just guessing at solutions.

Given that popular consensus is that such a verifying system implemented could not guarantee both returning in finite time AND returning an accurate answer, it would appear no, although we might be able to approximate it a reasonable percentage of the time.


Build Automatic Speech Recognition (ASR) from scratch

I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

Start with trying existing open source speech recognition system, learn how they work, play with them. Check http://cmusphinx.sourceforge.net.

  I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

HMM which provide time variance is still a reasonable model for speech, most of the system use it in one form or another. Limitations of HMM exist, but you do not need to care about them on that level.

You can implement a basic speech recognition system without HMM. For example check

http://de.mathworks.com/company/newsletters/articles/developing-an-isolated-word-recognition-system-in-matlab.html

That would be enough for "yes" and "no" discrimination. For any more serious use you will need HMM.

  Can someone recommend me books on topics from which I can start?

There are two good books on topic:

A basic guide to start:

http://www.amazon.com/Spoken-Language-Processing-Algorithm-Development/dp/0130226165

A modern state of the art

http://www.amazon.com/Automatic-Speech-Recognition-Communication-Technology/dp/1447157788/


Understanding non-faulting and faulting software prefetches

A faulting prefetch is one which (as gnasher729's answer notes) generates any translation (e.g., invalid page table entry), permission, or other fault (e.g., ECC failure, data watchpoint match) associated with the access. Such a prefetch acts as if the memory location was accessed normally. For data accesses such a prefetch can be provided by software on architectures that lack prefetch instructions. (For instruction accesses, a return operation would need to be placed in the cache block reducing the amount of useful code that would fit in the block.)

By acting as a normal access, a faulting prefetch effectively guarantees that the chunk of memory will be cached (a non-faulting prefetch may be dropped under high memory use or even a TLB miss) and that its address translation will be cached. This behavior may be preferred if the address is known to be accessed in the near future, especially if a timing critical section is about to be entered.

In some RISC ISAs, a faulting data read prefetch could be provided by a simple load to the zero register. Other ISAs could preform a normal load at the cost of temporary use of a register.

Non-faulting prefetches are purely hints to hardware, allowing hardware to drop the access if it is perceived as too expensive. By avoiding faults, such prefetches can be used without concern about whether the address is valid; prefetching from a null pointer or past the end of an array is safe.
A non-faulting prefetch is purely speculative. (Some ISAs provide support for speculative, non-faulting loads. In such an ISA, non-faulting prefetches could be implemented using such a load. Since the speculative load value may be used, hardware will typically treat such as an actual access and merely suppress any exceptions.)


Use max operation in a constraint in Linear Programming

Introduce variables $m_1,m_2,m_3$ to represent the three maxes.

Add the linear inequality $m_1 + m_2 + m_3 \ge q$.

Then, add the following extra inequalities for $m_1$:

$0 \le m_1 \le 1$
$m_1 \le x_1 + x_2 + \dots + x_n$
$x_1 \le m_1$, $x_2 \le m_1$, $\dots$, $x_n \le m_1$

and similarly for $m_2$ and $m_3$.


Calculate the average Big O from a function?

Strictly speaking, there are no such things as "Big O complexity" or "average Big O complexity". Look at the definition of Big Oh and you can stop guessing.

The right mindset is that you can analyze whatever aspect (say, the number of steps taken by an algorithm) in some case you care about (say, in the worst case, however you define it). You write a function $f$ of the input size $n$ that captures this. You do not need to know anything at all about asymptotic analysis up to this point. Now you can look at the definition of Big Oh again, and express $f(n)$ as the Big Oh of something.

With that being said, I think the questioner should clarify the meaning of "average Big O complexity". Concepts should not be intuitive and come out of thin air, but have precise definitions.


Context Free Grammar $L = \{a^i(b+c)^jd^k | i0\}$

Whenever you see a condition $i<j+k$, you can translate that to the condition $i+\ell=j+k$ where $\ell>0$, then use the methods you know for handling $=$ instead of $<$.

See our reference question on this subject for more systematic answers.


Binary Search Tree Traversal output validity and unique BST construction

I believe you are correct. The hard part is convincing yourself why this is true, I guess.

The key to the riddle is the root. preorder, postorder and levelorder all have the root at first or last position. Once the root is known all elements smaller go in the left subtree and those larger go right. Thus reconstructing the tree from its order is a recursive process.

Inorder always yields the elements from small to large, so there the situation is completely different. There is no unique tree, and any tree that is built by adding the elements as a BST will do.


Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

Let $M$ be a Turing machine and consider the Turing machine $M'$ that simulates $M$ on an empty input (regardless of the input to $M'$).

If $M$ halts on empty input then $M'$ eventually halts too. This means that there is a word $w$ of sufficiently large length $|w|$ such that $M'$ halts after at most $|w|$ steps (actually, there are infinitely many such words).

If $M$ does not halt, then also $M'$ doesn't halt (regardless of the its input).

Therefore your problem cannot be decidable as otherwise there would be a Turing machine capable of solving the halting problem.


Can User Level Thread read/write Kernel thread?

No.  In most operating systems, kernel memory is protected using virtual memory mechanisms, so a user process cannot read or write to kernel memory.
A user thread is part of a user process, and has the same permissions as the process.  So, a user thread will not be able to write to kernel memory.


Does the concept of subtype require dynamic method binding?

No. It doesn't even require a notion of "method" at all. Even if you have objects and methods, it doesn't necessarily require a notion of dynamic dispatch. Indeed, dynamic dispatch is only relevant if you can "override" methods (where, here, I'm [atypically] including implementing an interface as "overriding" [abstract] methods).

All subtyping states is if $t$ is a term of type $S$ then $t$ is also a term of type $T$ if $S\operatorname{\mathtt{<:}}T$. There are a variety of ways to implement this. For structural subtyping, usually the idea is that the sub-type is representationally compatible with the super-type so that their common interface literally refers to the same code. For example, if the 3-tuple $(A,B,C)$ is represented by contiguously storing a representation of $A$, $B$, and $C$, and similarly for a 2-tuple, then a 3-tuple literally is a 2-tuple that just happens to have a representation of $C$ following it. This is represented by $(A,B,C)\operatorname{\mathtt{<:}}(A,B)$. As another example, a sum/variant type $A+B+C$ could be represented as a tag indicating the variant and a representation of $A$, $B$, or $C$ as appropriate. If the tags are compatible, then a value of type $A+B$ literally is a value of $A+B+C$ leading to $A+B\operatorname{\mathtt{<:}}A+B+C$. Something like dynamic dispatch could be used internally to avoid relying on representational compatibility if desired by the language implementer.

Another approach would be to have subtyping imply the implicit insertion of coercions from sub-types to super-types. Dynamic dispatch is just completely irrelevant to subtyping in this context.

Common object oriented languages tend to conflate subtyping and subclassing, but they are fairly different concepts. Many (most?) programming languages that have some degree of "subtyping" fail to satisfy various notions of "substitutability", so the baseline is usually just that using a sub-type as a super-type typechecks and (usually) doesn't crash. (Even that low bar fails to be met by e.g. Java and C# and certainly C++.)

You could have a language that supports dynamic dispatch which doesn't have a notion of subtyping. For example, conversions to "super-types" could be explicit.


Find the maximum (longest) delay to last user in a multicast T. NP complete proof

Refer to Shorted Path Tree (SPT)- https://en.wikipedia.org/wiki/Shortest-path_tree
It ensures that the delay from source node is always minimum for all the nodes including the maximal ones.

Based on your problem description I think it is SPT. If that's the case, it is not a $\text{NP}$-hard problem.


How exactly do you calculate the hidden layer gradients in the backpropagation algorithm?

You've transposed the sizes of both $w^L$ and $\delta^{x,L}$.  $w^L$ should be 2x4 and $\delta^{x,L}$ should be 2x1.  $(w^L)^T$ is a 4x2 matrix that will be multipled by a 2x1 matrix yielding a 4x1 matrix suitable for the next step of backpropagation.
In general for neural nets the activation units are represented as column vectors and the weights are matrices of dimension |L+1| x |L|, where L is the current layer and L+1 is the next layer (in the forward direction).


Proving NP is a subset of the union of exponential DTIME

You are on the right track. To finish the proof you need to show that

$\qquad \displaystyle \mathsf{DTIME}(2^{n^k} n^k) \subseteq \mathsf{DTIME}(2^{n^c})$

for some constant $c$.


When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?

One issue is that the way you're using the English language is appropriate for talking about DFAs but not appropriate for NFAs.
With a DFA, we can say "the DFA is in state $q$ after reading the input".  That is well-defined for a DFA.
That is not well-defined for NFAs.  There may be multiple possible runs, each of which ends in a different state.  So it doesn't make sense to say "the NFA is in an accepting state after reading the whole input", because there may be multiple possible runs, some of which are in an accepting state and some of which are not.
The formal definition of a NFA gives a precise definition of under what conditions a string is considered to be accepted.  Please consult any good textbook.  The short answer to your last question is yes, the input string is accepted in that situation, as there exists a run of the NFA that ends in an accepting state and where the whole input has been consumed.  But there's little point in us repeating material that's already covered in standard textbooks, and if you work through the definitions, you should be able to figure this out for yourself.


Halting problem for fixed Turing machine and fixed input

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always halts, we can easily decide $\text{HALT}_M$ just by outputting "yes".

What you probably meant to say is the following facts, which are true:

There exists a Turing machine $M$ such that the problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable.
For all words $w$, the problem $\text{HALT}_w$ (deciding on input $M$ if $M$ halts on $w$) is undecidable.

In particular for fact 1, we can take $M$ to be the universal Turing machine.

  What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?

Yes, the problem becomes trivially decidable. Define the language
$\text{HALT}_{M_0, w_0}$ to be the problem of deciding whether $M_0$ halts on $w_0$. But notice that this problem no longer has any input that the answer depends on, as both things that the answer might depend on ($M_0$ and $w_0$) are now fixed, i.e. part of the language definition, not part of the input. That means the answer is just "yes" or "no". So we can trivially decide this problem either by using a program which always says "yes", or a program which always says "no".

This is a common pitfall about decidability: it is only useful to ask whether a problem is decidable or not when the number of possible inputs is infinite. If there are only finitely many possible inputs, then all problems become decidable.
You have asked whether a problem with only 1 possible input (the empty input) is decidable, and the answer to that is always yes.


How is the computational power of a human brain comparing to a turing machine?

Given that Alan Turing devised the Turing Machine model of computation by abstracting what humans actually do when they compute by hand, I think one would be very hard-pressed to prove that a Turing Machine is more powerful than a human.

[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course).  Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states]


Graphs with chromatic number $(\chi(G) \ge 3 )$ other than odd cycle (Triangle free)

If a graph contains no odd cycle then it is bipartite and so 2-colorable.


Algorithm to find the intersection of non-convex polyhedra

I propose the following approach.

Decompose each polyhedron into a union of convex polyhedra, say $A = A_1 \cup \cdots \cup A_m$ and $B = B_1 \cup \cdots \cup B_n$.
Convert each convex polyhedron from V-representation (its list of vertices) to H-representation (intersection of half-spaces, given by linear inequalities).
Compute the intersection as $A \cap B = \bigcup_{i,j} A_i \cap B_j$, where you can compute $A_i \cap B_j$ trivially once they are in H-representation: you just concatenate the list of linear inequalities.  (If you want, you can convert $A_i \cap B_j$ back to V-representation.)

There are standard algorithms for doing step 2.  In fact, given a face, it is easy to construct the corresponding linear inequality (form the plane that goes through all of the vertices on the face, then create the corresponding linear equality, then change the equality to an inequality).

I'm not sure how to do step 1; perhaps that is worth asking as a separate question, if you can't figure it out after some research.


The running time is $O(n+nk) = O(nk)$, where we are making the implicit assumption that $n,k \geq 1$. This is usually a reasonable assumption.

If we do allow $n$ and $k$ to be zero then the running time becomes $O(nk + n + 1)$.

Let me comment that there are several different definitions of big O, which are usually but not always equivalent. Here I am using the following definition: $f(x_1,\ldots,x_m) = O(g(x_1,\ldots,x_m))$ if there exists a constant $C>0$ such that for all integers $x_1,\ldots,x_m \geq 0$, it holds that $0 \leq f(x_1,\ldots,x_m) \leq C g(x_1,\ldots,x_m)$.


Nomenclature for deterministic algorithms that might fail

I do not have an authorative answer but two proposals.

Such algorithms compute partial functions, so you could call them partial or partially correct algorithms.

Working off your literature, the class of algorithms you defined is that of Las Vegas algorithms. Even though the implication  is that the algorithm is randomised it certainly need not be; even though you have access to random bits you don't have to use them.
If you want to stress determinism, you can use deterministic Las Vegas algorithm.


In your case, the simplest solution may be to use SAT.
Your first clause includes $x \le 0.25$ and $x > 0.91$. This means that there are five regions of interest for the variable $x$, which we identify with boolean variables: $X_1 \equiv x \in(-\infty, 0.25)$, $X_2 \equiv x = 0.25$, $X_3 \equiv x \in (0.25, 0.91)$, $X_4 \equiv x = 0.91$, $X_5 \equiv x \in (0.91,\infty)$.
Create a boolean variable for each of these ranges, and convert the clause to use them. So, for example, $x \le 0.25$ would convert to $X_1 \vee X_2$, and $x < 0.91$ would convert to $X_1 \vee X_2 \vee X_3$.
More clauses would mean more constants, and hence more ranges of interest for a primitive variable.


undirected graph without weights and DFS

The time complexity of DFS is O(|V|+|E|), therefore if one can solve these problems with DFS, it follows their time complexity is also O(|V|+|E|), remains only to proof that complexity, for which I should recommend a reading on Cormen.

1) To check if G is bipartite, tag each visited vertex with a color. Initially, all vertex are, say, WHITE. When you start the DFS with a vertex, tag it with RED. Everytime a RED vertex visits a WHITE vertex, tag that WHITE vertex with BLUE, and when a BLUE vertex visits a WHITE vertex, tag it with RED. If a vertex visits another vertex of the same color, then that graph is not bipartite. This is because a graph is bipartite if and only if it is 2-colorable, that is, its chromatic number is 2. In short, every pair of adjacent vertices of that graph can be colored with 2 different colors, and only 2 colors are needed to color the entire graph.

2) Here, a similar approach, but with only WHITE and BLACK. All vertices are initially WHITE. Start the DFS in a vertex and tag it with BLACK. Everytime a BLACK vertex visits a WHITE vertex, tag it with BLACK. If a BLACK vertex visits another BLACK vertex, then there is a cycle in the graph.

3) Start with a counter=1 and start the DFS. If at any point the vertices stack is empty, that is, you have backtracked all the reacheble vertices from the origin and need to access the vertex list once again, then increment the counter variable. That variable indicates the number of connected components of your graph.

4) It is NOT possible to solve this problem with DFS. It is probably a trick.
Why can't DFS be used to find shortest paths in unweighted graphs?


Not quite-infinitely expandable human-friendly naming system?

As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme x_N_M where N and M are numbers. Think of this as indexing a point with the fraction N/M. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point x_N_M, name the new point x_N_2M. To insert on the right of the rightmost point x_U_V name the new point x_2U_V. And to insert between adjacent points x_A_B and x_C_D, name the new point x_E_F where E/F is the average of A/B and C/D.


Can we somehow get functoriality from purely type-theoretic reasoning?

There are two senses in which type formation operations are 'functorial,' but neither matches functoriality on the category of types.
First, you can interpret the collection of types as a groupoid, and consider isomorphisms between types to be 'arrows.' These compose, but also always have inverses, so are in some sense undirected. However, this is also why all constructions are able to be functorial, because type formation operations have both covariant and contravariant positions, and thus may not preserve the direction of arrows.
Anyhow, functoriality here says that if you have $P : A \cong B$ then there is always $F P : F A \cong F B$, and: $$F\ \mathsf{Refl}_A = \mathsf{Refl}_{F A} \\ F (P \cdot Q) = F P \cdot F Q$$ This is essentially the direction of homotopy type theory, where these properties are internalized (and the 'dimension' is not limited to just groupoids).
The second functoriality property is already in the other answer. The "identity extension lemma" is a functoriality property where categories are relaxed to reflextive graphs (rather than tightened to groupoids). Again, type formation operations are able to be functorial because reflexive graphs do not have operations where 'direction' matters. However, this time it is because edges are not assumed to be composible.
So, the identity extension lemma says that every relation $R : A \Leftrightarrow B$ induces a relation $FR : FA \Leftrightarrow FB$ where:
$$F\ \mathsf{Refl}_A = \mathsf{Refl}_{F A}$$
And that's all there is to being a "relator" of reflexive graphs. There are also type systems that can talk about this sort of thing internally, possibly even with homotopy type theory features, like here.
Now, The first approach doesn't give you 'normal' functoriality for all type formations because not every map $f : A → B$ is an isomorphism. And of course, if we do $F A = A → A$, that's not going to extend to $(A → A) → (B → B)$ nor the other direction, without also having some map in the other direction. However, given an isomorphism, it induces $(A → A) \cong (B → B)$
In the second approach, a map $f : A → B$ induces a relation $\mathsf{gr} f : A \Leftrightarrow B$ given by $(x, f\ x)$. However, although we could compose the maps, there is no notion of composition of relations to talk about, and relate back to the composed functions. Considering the same type construction:
$$FR(m,n)\quad \Longleftrightarrow \quad R(x,y) ⇒ R(m\ x, n\ y)$$
So:
$$F(\mathsf{gr}\ f)(m,n)\quad \Longleftrightarrow\quad f \circ m = n \circ f$$
If you try to apply this to composed maps, then you know:
$$f \circ m = n \circ f \\ g \circ m = n \circ g$$
so $$f \circ g \circ m = f \circ n \circ g$$
but then there's nothing to do further.
You can read more about this angle in this paper, which tries to apply parametricity to a wider mathematical scope. A counter-question that the paper kind of motivates is: why do you care specifically about category functoriality? The original intuitive specification of "naturality" sounds very much like the intuitive specification of "parametricity," but the former was eventually formalized in terms of directed maps, rather than undirected relations. However, there is nothing inherently more legitimate about directed maps vs. relations or isomorphisms, and some things work out more appropriately for the latter than the former. Sometimes even in category theory it it necessary to shift into the 'undirected' perspective to make easier sense of something. See for instance here.
On a final note, you can have a type theory that keeps track of category theoretic functoriality of things. Here is early work, and here is something closer to homotopy type theory. The former tracks functoriality of everything explicitly, and is of course significantly more complicated for it. The latter allows functoriality to be an internally definable property, similar to the 'dimension' in homotopy type theory. But in neither would every type expression be necessarily functorial with respect to directed maps, because that would require limiting what one is able to write.


Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching

I would do this iteratively going through buyers ready to pay the highest price. I assume you can have partial fills if buyer and seller quantity don't match?

Step 1. Sort the buyers with MAX price at the top.
Step 2. Sort the sellers with LEAST price at the top.
Step 3. Take the topmost buyer from step 1 and try to fill its order, taking into consideration any restrictions, with a matching seller from the top. This will be your reference price. To match the seller you would need to traverse from top, comparing one by one to see which seller matches.
Step 4. Update the seller and buyer quantities based on the match in step 3.
Step 5. Repeat from step 1.

Hope that helps. Have a wonderful day!


Calculating direct sum of 2 binary numbers

The operation $\oplus$ is the same as bitwise XOR. The same symbol is used for direct sum, but there is otherwise absolutely no relation.


AFAIK, the page table entry doesn't contain the page itself. Rather, it contains the address of the physical memory chunk that the particular page in the table is mapped to. This address will be 32-bits (4 bytes).

In this example, the page table entry contains the address of the physical memory chunk (frame). Knowing the offset, we can find the actual address in the physical memory.

Hope it helps.


How does one program crashing not crash the entire system?

Probably you should read something about OS memory management.

If the program is running it has memory which is readable, memory which is writable and both. If it tries to go beyond its permissions, OS kills it and reports to you in a way you call "crash".

That's all was very roughly speaking.


how to bound the probability that quicksort takes greater than n lg n time?

The exercise is extremely poorly worded. The problem is that Randomized-Quicksort is a randomized algorithm, and so it doesn't have a "running time", or rather, its running time is a random variable. I suspect that this is a typo, and that the intension was to analyze the deterministic Quicksort algorithm. Assuming this correction, here is a more formal version of the exercise:

  Show that for all $k > 0$ there exist constants $a_k,b_k$ such that for all $n$, there exists a subset $S \subseteq S_n$ (where $S_n$ is the set of all permutations of $1,\ldots,n$) of size at most $(a_k/n^k) n!$ such that for all $\pi \in S_n \setminus S$, the running time of Quicksort on $\pi$ is at most $b_k n \log n$.

In order to prove the exercise, presumably you need to use material from Theorem 12.4, which states that the expected height of a randomly built binary search tree of size $n$ (formed by choosing a random permutation in $S_n$ and adding the elements to a binary search tree in that order) is $O(\log n)$. You then argue roughly as follows:

When running Quicksort on a permutation in $S_n$, the running time is $O(nh)$, where $h$ is the height of the binary search tree formed from the permutation.
The argument of Theorem 12.4 can be strengthened to show that for each $k>0$ there exist $a_k,b_k$ such that when constructing a random binary search tree, the probability that the height exceeds $b_k \log n$ is at most $a_k/n^k$.
Putting the two ingredients together yields the problem.


Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \{0w \mid w \in A\} \cup \{1w \mid w \in B\}$ satisfies that $A \leq A + B$, hence $A + B \in \mathfrak{L}$. Since $A + B = A + C$ iff $B = C$, we see that $B \mapsto A + B$ provides an injection from the all languages into $\mathfrak{L}$.


Proof-sketch on the language accepted by a Turing machine

In order to prove that any machine, automaton or grammar satisfies $L(T) \subseteq X$ you have to translate your intuition of how it was designed into hard facts. What is the intended meaning of a certain configuration, how where the states chosen? So you have to divide the operation of the machine into phases. Like, "if the TM is in state $q$ on the left of the tape, it will move right, marking half of the symbols $A$ ending in state $q$ on the leftmost cell used". If the design of the machine is done right, such explanations usually suffice, if they can be easily understood. Otherwise one has to apply induction, on whatever seems interesting (like the remaining symbols $A$).

Let me try to add an example, what I would consider sufficient "proof". A Turing machine deciding the language $\{ a^{2^n} \mid n\ge 1\}$. States used $p_0,p_1,p_O,p_E,\ell,p_A,p_R$, accepting state $p_A$, rejecting $p_R$. Tape alphabet $\{a,X,B\}$, with $B$ for blank. Instructions in the order (state, symbol, new state, new symbol, direction).

We scan the tape from left to right. In each scan we halve the number of $a$'s. When the number of $a$'s on the tape is $1$ we accept, otherwise when the number is odd we reject (and halt), finally when the number is even, we return to the leftmost symbol on the tape.

Start in state $p_0$, indicating $0$ $a$'s read. Other states $p_1,p_E,p_O$ for single, even, odd number of $a$'s read.

$(p_0,a,p_1,a,R)$, $(p_1,a,p_e,X,R)$, $(p_E,a,p_O,a,R)$, $(p_O,a,p_E,X,R)$, move right, crossing out every second $a$.
$(p,X,p,X,R)$, for $p = p_0,p_1,p_E,p_O$, ignore symbol $X$.
$(p_0,B,p_R,B,L)$, $(p_1,B,p_A,B,L)$, $(p_E,B,\ell,B,L)$, $(p_O,B,p_R,B,R)$, make decision on reaching the right end of the tape, as explained above.
$(\ell,\sigma,\ell,\sigma,L)$, $\sigma = a,X$
$(r,B,p_0,B,R)$ in state $\ell$ move left to first symbol on tape, ending there in state $p_0$.

Finally, note we reject on empty tape.


How the concept of computer change over time?

The Online Etymology Dictionary gives the first attested use of
  "computer" in the "1640s, [meaning] "one who calculates,"; this is an
  "... agent noun from compute (v.)". The Online Etymology Dictionary
  states that the use of the term to mean "calculating machine" (of any
  type) is from 1897." The Online Etymology Dictionary indicates that
  the "modern use" of the term, to mean "programmable digital electronic
  computer" dates from "... 1945 under this name; [in a] theoretical
  [sense] from 1937, as Turing machine".

It seems the word computer was given a new definition in 1945 to the more familiar programmable computer we think about today. Words change meanings all the time, it's the evolution of language and as machine computer became more popular than human computers the term computer changed as well.

Technically anything which can simulate a turning machine can be considered a computer so humans naturally can also be considered computers, but that just seems more confusing than it is helpful.


Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

The question you're asking deals with the topic of derandomization, and you're proposing a specific technique for derandomization, namely using pseudorandom number generators. There are other techniques suck as using k-wise independent distributions and the method of conditional expectations. The holy grail in the field is proving the conjecture P=BPP, which states (informally) that we can always get rid of randomness, though the resulting algorithm could be slower; more precisely, it states that if you have a randomized polytime algorithm for something, then there exists a deterministic polytime algorithm for the same problem.

In your particular case, you don't need random bits at all, since you can use the linear time median algorithm to guarantee a running time of $O(n\log n)$ for quicksort. The AKS deterministic primality test is likewise a specific derandomization of randomized primality testing. P=BPP, in contrast, gives a general derandomization technique that works for every (polytime) algorithm; ad hoc derandomizations are still meaningful, since they could be more efficient (like in the quicksort example).


The Chomsky–Schützenberger representation theorem

If you start with a pushdown automaton, then its instruction diagram can be interpreted as a finite state automaton. The instruction $(p,a,A,q,\alpha)$ — in state $p$ reading $a$ we pop $A$ go to state $q$ and push $\alpha$ — has an edge from $p$ to $q$ with label $(a,A,\alpha)$. This defines a regular language of possible instruction sequences (ignoring popping and pushing).

Now recode $(a,A,\alpha)$ by bracket symbols. $A$ is popped and is coded with the closing bracket $\bar A$, the symbols $\alpha$ are pushed and coded as opening brackets. If we code the instruction by the string $\bar A\alpha$ the (regular) language of instructions is a perfect matched bracket sequence (Dyck) if it is a legal sequence of popping and pushing. (Add $Z$ the initial stack symbol as first letter)

Now we forgot about the input letter $a$. This has to be inserted to the instruction, without losing the bracket structure. This is done by adding a virtual closing bracket $\bar a$ for each $a$. Thus, the finite state edge is now as follows: $(p,a\bar a \bar A\alpha,q)$.

Chomsky-Schutzerberger intersects with Dyck for the popping and pushing as I said, and retrieves the symbol $a$ using an homomorphism that deletes all other symbols.

It is also possible to start with a CF grammar in Greibach NF. Then the states totally disappear, the coding is similar, and the regular language is very simple: $S \{\; a\bar a \bar A \alpha^R \mid A\to \alpha \;\}^*$


p constant in pumping lemma for regular languages

The key here is that $L$ is a finite language.  Therefore it can be recognized by a DFA which has no cycles - in this case, a chain of 122 states, numbered 1 through 122, with transitions on $a$ from each state $i$ to state $i+1$ [except for a loop on $a$ from state 122 to itself], with states 1, 4, 9, ..., 121 being final.  For P=122, this automaton satisfies the Pumping Lemma - i.e all strings in $L$ of length at least P can be pumped - in a purely vacuous sense, because there are no strings in $L$ of length at least P.


How difficult is this matching-like problem?

Observing that there exists an optimal solution such that for any $i_1<i_2$ , $f(i_1)\le f(i_2)$ (otherwise, we can swap $f(i_1)$ and $f(i_2)$), there is a dynamic programming algorithm solving your problem.
We sort $A$ and $B$ firstly. Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, where $a_1<\cdots<a_n$ and $b_1<\cdots <b_m$. Let $D(i,j)=\min_{f:\{a_1,\ldots,a_i\}\to\{b_1,\ldots,b_j\}}\sum_{j'\le j}(\text{number of nodes matched to }j')^2$, then $$D(i,j)=\min_k D(i-k,j-1)+k^2,$$
where the minimum is taken over all $k$ such that $a_{i-k}$ is able to be matched to $b_j$. The original objective is to compute $D(n,m)$. It can be done by this recurrence in $O(n^2m)$ time.


I have not watched the video, so I'll go by your description. There is an array of items which contain pointers to other items. These pointers form a linked list structure.

This sort of data structure tends to arise when a collection of items needs to be easy to traverse in multiple different orders. For example, a priority queue may need to be traversed both according to the elements' age and according to the elements' priority. This can be implemented with an array of elements, with new elements added at the end so that they're in age order, and a linked list or a search tree for priorities.

One common case for linked lists of array items is in a memory allocator. You ask, “Why use these free nodes, when you can dynamically allocate storage?” Well, what about the cases when you can't dynamically allocate storage, because you're implementing the dynamic storage allocator? The concept of “free list” is common to most memory allocators. A block of memory that isn't in use is an element of the free list. With fixed-size blocks, to free a block, you write a pointer to the current head of the free list at the beginning of the block, and you set the head of the free list to the address of this block. To allocate a block, you take the current head of the free list as the block to use, and set the head of the free list to the block that
was second in the list. In pseudocode:

allocate() :=
    block := free_list_head
    if free_list_head is null: raise out_of_memory
    free_list_head := free_list_head.next
    return block
free(block) :=
    block.next := free_list_head
    free_list_head := block

Allocators for variable-sized blocks typically use fancier data structures so as to be able to merge adjacent blocks and find blocks of an appropriate size.


You just need to check if $|a-b|$ is divisible by a some integer $k$. You can reduce it to the integer factorization problem if you are not interested in the trivial divisors 1 and $|a-b|$.


How would I write a single expression involving count, x and y that has exactly the same effect as shown (below)?

I'm assuming that you're interested in the following more general situation:

Input: $x,y$.
Initialize $count$ to $0$.
While $y < x$: Increment both $y$ and $count$.

You want to know the values of $x,y,count$ at the end.

If $y \geq x$ to start with, then the while loop never runs, so nothing happens. If $y < x$ (and both are integers), then the loop runs $x - y$ times (why?). At this point you should be able to tell what are the values of $x,y,count$ at the end of the code.


Why should we study all the three forms of representation of finite automata?

Add regular grammars for a fourth. There are others...

Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a crucial idea for more elaborate models). To prove DFA and NFA accept the same set of languages is also exploring a very important phenomenon in a simple, understandable setting.

Regular expressions (and also regular grammars) are completely different formalisms, that happen to describe the same set of languages. Again, the proof of this fact explores important cross-relations, and are an example that formalisms might look very diffent, be based on radically dissimilar concepts, but describe the same languages. Again, in a rather simple setting.

For "real world" use, you can start with a regular expression and get a minimal DFA for high-performance searching. Digital circuits are essentially DFAs, understanding them is central in computer engineering. Last but not least, often systems can be modelled as "being in a state" and "moving to another one" on external stimuli, even if the system is very far from a real DFA viewing it this way might help understanding it.

Added later: As noted by Raphael, it may be more efficient to interpret an NFA directly for searching, because creating a DFA can be expensive, and an NFA may be much smaller.


Is the complement of every non Turing recognizable language a Turing recognizable language?

Your proof is fine. There are also explicit languages which are neither r.e. nor co-r.e., for example the language of all total Turing machines (Turing machines halting on every input).

In fact, the language of all total Turing machines is $\Pi_2$-complete, which means, in a sense, that there is no better way to "solve" it than to run all on inputs and see whether the given machine halts on each of them (of course, you can't do this with a Turing machine, but perhaps with a more powerful device...). Take a look at the arithmetical hierarchy for more on this.


How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

I don't know what search engines actually do, but one approach would be sort by decreasing pagerank, resolving ties using the document ID.  (In other words, the primary sorting key is the page rank, and the secondary sorting key is the document ID.)

This still allows the merge operation.  It also ensures that results are generated in decreasing pagerank order, i.e., the top-ranked results are generated first.  Note that if two documents have the same document ID, then they'll definitely have the same pagerank, too, which is why this approach works.


Variant of interval scheduling with varying task durations

The deterministic version of your problem (i.e. to determine whether there is a valid arrangement) is strongly NP-complete by a reduction from 3-Partition, as suggested in [1].

Given an instance $x_1,x_2,\ldots,x_{3m}$ of 3-Partition, let the duration in your problem be $[0, mB+m]$ where $B=\sum_{i=1}^{3m} x_i/m$. For each element $x_i$, there is a task with duration $x_i$. The intervals for these tasks are all $[0, mB+m]$. In addition, there are additionally $m$ tasks with duration $1$, and their intervals are respectively $[B, B+1], [2B+1, 2B+2],\ldots,[mB+m-1,mB+m]$. Note the positions of these additional tasks are fixed.

Since we can assume $B/4<x_i<B/2$ for all $i$ in 3-Partition, we can see there is a valid partition if and only if there is a valid arrangement in your problem.

[1] Garey, M. R., & Johnson, D. S. (1977). Two-processor scheduling with start-times and deadlines. SIAM Journal on Computing, 6(3), 416-426.


How to construct Context Free Grammar of words with equal number of 0's and 1's

The question defining a context-free grammar for $\{\in\{0,1\}^*:\#_0(w)=\#_1(w)\}$ restricts its answers to one particular grammar and the proof for its correctness is somewhat involved. Here I would like to show a different grammar that is easier to figure out.

Since the requirement is the same number of 0's and 1's, we can grow the start non-terminal $S$ by a pair of 0 and 1 in all sorts of way. (This is more or less what your idea of "counting" should be). We will have the following production rules, $S\to S01\mid S10\mid 01S\mid 10S\mid 01S\mid 10S\mid \epsilon.$

However, if we check closely, the above grammar does not generate 00111100. What happens is that the above grammar will generate the first part 0011 as a whole, missing the second part 1100. That suggests us to add another rule $S\to SS$. Once we have added that rule, rules $S\to S01\mid S10\mid 01S\mid 10S$  become redundant. The final grammar is
$$S\to SS\mid 0S1\mid 1S0\mid \epsilon.$$

It is clear that the word generated by that grammar has the same number of 0's and 1's.

Are all such words generated by that grammar?

The rule $S\to\epsilon$ show that unique word of length 0 can be generated.

As the induction hypothesis, suppose all words of length less than $2n\le2$ can be generated.

Let $w$ be such a word of length $2n$.

Let $d(k)$ be the difference of the number of 0's and the number of 1's in the first $k$ letter of $w$. In particular, $d(2n)=0$. Since the situation is symmetric with respect to 0 and 1, WLOG assume $w$ starts with a 0, i.e., $d(1)=1$.

If $w$ ends with a 1, then $w=0w'1$ for some word $w'$. $S$ generates $w$ since $w'$ have the same number of 0's and 1's and $w'$ is shorter than $w$. So $S\Rightarrow0S1\Rightarrow0w'1=w$.
If $w$ ends with a 0, then $d(2n-1)=-1$. Since $d(x)$ changes 1 by 1, $d(k)=0$ for some $1\lt k\lt 2n-1$. Let $w_1$ be the first $k$ letters of $w$ and $w_2$ the rest of $w$. By induction hypothesis, $S\Rightarrow w_1$ and $S\Rightarrow w_2$. Hence $S\Rightarrow SS\Rightarrow w_1w_2=w$.

We have completed mathematical induction. All such words can be generated.


Steps to convert regular expressions directly to regular grammars and vice versa

As (briefly) indicated by Raphael in a comment, the only difference between an NFA and a linear grammar is formatting. You can use any algorithm which converts a regular expression to an NFA, and produce a right or left linear grammar instead of the NFA, simply by changing the way you produce output.

Specifically, when you are producing an NFA (with any algorithm) you will perform a series of steps of the form "Add a transition labeled $a$ between $P$ and $Q$", where $a$ is either a terminal or $\varepsilon$, and $P$ and $Q$ are states. To "directly" produce a right linear grammar, implement the above step by producing the production $P\to a Q$ if $a$ is a terminal, or
$P\to Q$ if $a$ is ε. Also, implement the step "Mark $Q$ as a final (accepting) state" by outputting the production $Q\to\varepsilon$. (Alternatively, don't put $Q$ in the productions produced for transitions, if you know in advance that $Q$ is a final state.)

If you want to produce a left linear grammar, you need to work with incoming transitions instead of outgoing transitions; for the $a$-transition from $P$ to $Q$, write $Q\to P a$ unless $P$ is the start state, in which case you just use $Q\to a$. (Again, ε transitions are handled by omitting $a$.)

If the unit productions bother you, use an algorithm which produce an ε-free NFA, or produce the NFA and then do an ε closure to eliminate the ε transitions before printing out the grammar.

Any correct regular expression to linear grammar algorithm will be some version of the above procedure (since you could produce the transition table instead of the grammar by once again changing the print format).


Is there an undecidable language that is mapping reducible to its complement?

Yes, it is possible. Enumerate the set of all possible Turing machines and let $H$ (resp. $\overline{H}$) be the set of indices of the Turing machines that halt (resp. do not halt) on empty input.
Let $L = \{ \langle T, 1 \rangle \, : T \in H \} \cup \{ \langle T, 0 \rangle \, : T \in \overline{H} \}$.
Clearly $L$ is not decidable but it is possible to reduce $L$ to $\overline{L}$ since $\langle T, r \rangle \in L \iff \langle T, 1-r \rangle \in \overline{L}$.


How can I reduce Subset Sum to Partition?

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$. Let $L'$ be the list formed by adding $S+B,2S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ 2S-B \}$ and $L\setminus M \cup \{ S+B \}$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. Indeed, since $(S+B)+(2S-B) = 3S$ and each part sums to $2S$, the two elements belong to different parts. Without loss of generality, $2S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$.