the book is describing low level machine language architecture associated with the CPU & what is also known as "microcode". it would be possible to design opcodes that use multiple registers (that does occur in some mostly uncommon cases) but most opcodes generally refer to one register or a memory location, unless its a transfer between two registers. the register number is usually encoded into the opcode in binary. that is, registers serve as a sort of small intermediate "hub" or even a small "cache" between memory and the CPU.

if one had opcodes that refer to multiple registers it quickly leads to a combinatorial explosion where the opcodes become very numerous. even a 2-way register opcode scheme takes roughly $c \cdot r^2$ encodings where $r$ is the number of registers. a 3-way register operation would require $c \cdot r^3$ etc... another scheme is to limit multiway register operations to just a few "privileged" registers, not the full set.

a good case study or example might be the 6502 CPU that has an accumulator, an auxiliary X and Y register, and some limited operations to move between them. a full/general level of register interchange is then supported by stringing several/multiple register manipulation opcodes together.


Data structure that allows accessing elements by index and delete them in O(logn)

Take any self-balancing binary tree (e.g. AVL) and replace every node's key with the number of left descendants it has. This is easy to keep up-to-date for tree insertions/deletions (in $O(log n)$ time), and rotations (in $O(1)$ time).
Then to find the node with index $i$ you start at the root and repeatedly compare $i$ with the value of the current node $v$. If $i < v$ you go to the left child, $i = v$ you found the correct node and $i > v$ you subtract $i := i - v$ and go to the right child.


If your transpositions form a permutation $\pi$ then (using the appropriate convention for multiplication) $A\pi = B$ and so $\pi = A^{-1} B$. This shows that we can assume without loss of generality that $A$ is the identity, and the question now becomes: how many transpositions do we need to multiply in the worst case to get any particular permutation? This might be a question you already know how to answer.


Why does the reduction from 3SAT to IS work?

The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS.

So assume that the formula is satisfiable.

Since the formula is satisfiable each clause has at least one literal (it may be $x_1$ or $\overline{x}_1$ for instance). Now I claim that according to the structure of the graph the maximum IS must have $k$ nodes where $k$ is the number of clauses.

Why?

Because each clause corresponds to a single triangle $K_3$, and hence you can choose only one node from each triangle, where you have exactly $k$ triangles (any two nodes in the $K_3$ are not independent - they are connected by an edge).

But which node do we choose from each gadget/triangle?

You choose those literals which are true. These literals form independent set. Indeed, if two true literals belong to different triangles then they are not connected by an edge since only $x_i$ and $\overline{x}_i$ may be connected by an edge. But $x_i$ and $\overline{x}_i$ cannot be true at the same time (remember that our IS $S$ contains only true literals).

So we have exactly $k$ nodes/true literals which indeed forms a maximum IS. Therefore if the formula is satisfiable then the graph has a maximum IS.

You also need to prove the opposite, namely, if the graph has a maximum IS then the formula is satisfiable. I think you could prove it yourself.


Average time to solve maze through backtracking

Your question on the exam is asking for average case analysis -- visiting all the cells to solve the maze is the worst case.

Informally think this way: Whenever you move to a new cell, you can move to at maximum 3 directions, which one direction is to go back to your previous cell (this choice is discarded since it's of course not what you want to do to explorer the maze.) In the two other options left, one of the direction will lead you to the target, the other one does not. What's the expectation of find the target in each move? Does it hint something $O(n \log n)$?

Also try to picture this as you are exploring a tree structure. What's the average height of a tree?


There's a line of research that studies how to store sensitive data in the CPU's registers instead of RAM.  Here's a seminal paper:

TRESOR Runs Encryption Securely Outside RAM.  Tilo Müller, Felix C. Freiling, Andreas Dewald.  Usenix Security 2011.

There's also work in storing sensitive data in the cache.  Here are two of the seminal papers:

CARMA: A hardware tamper-resistant isolated execution environment on commodity x86 platforms.  Amit Vasudevan, Jonathan McCune, James Newsome, Adrian Perrig, Leendert van Doorn.  ASIACCS 2012.
Copker: Computing with Private Keys without RAM.  Le Guan, Jingqiang Lin, Bo Luo, Jiwu Jing.  NDSS 2014.

There's lots more work on these subjects, but this will get you started.  You can find follow-up papers in the standard ways (Google Scholar, etc.).

You might also be interested in Intel SGX, TrustZone, TPMs, or related schemes for hardware support for secure computation.


Show that for every language there exists a harder language

There are a few ways to approach this.
You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq_T A$. Let $L_A=\{B| B\le_T A\}$ denote the set of all languages reducible to $A$. Show that $f:L_A\rightarrow \mathbb{N}$ that maps languages $B\in L_A$ to $n$ such that $M_n$ is a reduction from $B$ to $A$ is an injection, and conclude that there exists a language outside of $L_A$. Next, you want to make it comparable to $A$. We can get such a language with the join operator:
$A\sqcup B=\{0w|w\in A\}\cup\{1w|w\in B\}$.
I leave it to you to show that $A\sqcup B$ is the least upper bound for $A,B$, i.e. $A,B\le_T A\sqcup B$ and additionally for every $L$ such that $A,B\le_T L$ we have $A\sqcup B\le L$ (you only care about the former). Show that if $B\nleq_T A$ then $A\sqcup B\nleq_T A$.
Another way to prove this is to use the jump operator. We need to introduce the notion of oracle machines, and then show that $B=\left\{\left(M^A,w\right)| \text{$M^A$ halts on $w$}\right\}$ is a strictly harder language. The proof is identical to the undecidability of the standard halting problem, only that now we show the stronger property that no machine with oracle access to $A$ can decide $B$.
You can also directly construct such a language via diagonalization. define $B=\left\{n | M_n(n)\notin A\right\}$. We constructed $B$ such that any computable function $M_n$ fails to be a reduction from $B$ to $A$ on at least one input (specifically, the encoding of the reduction). You can now use the join operator to make them comparable.


In 2-4(a) each stage processes one instruction at a time using one unit for every stage. In 2-5 the instruction fetch unit remains the same but fetches two instructions that are then processed parallelly, each with its own unit. So we have two pipelines of cause. They are logically and physically seperated.
But as far as I understand, the main difference between 2-5 and 2-6 is that in 2-6 the CPU decides dynamically what the order of execution of the instructions will be (out-of-order-execution) so that it can eliminate dependencies and hazards. The multipipeline approach executes parallel but in-order. But a superscalar CPU will as well need all stages twice. I personally think it would be wrong to say a superscalar has one single pipeline.


How to convert 2 or gates (x1 V x2 V x3) to NAND

(x1 or x2 or x3) = (not x1 NAND not x2 NAND True NAND not x3)


Probability of arising of simple graph in configuration model

Consider a simple $d$-regular graph. For each vertex, assign numbers from $1$ to $d$ to the edges adjacent to it. There are $(d!)^n$ ways to do so. Each such assignment corresponds to a particular perfect matching in the configuration model, and vice versa.


Usage of master theorem for solving recursions

You may solve this recurrence by using the Akra-Bazzi method, which generalizes the master theorem and allows solving recurrences of the form

$T(n)= \sum\limits_{i = 1}^k {a_i T(n/b_i) + f(n)}$

You need to solve for $p$ the equation

$\sum\limits_{i = 1}^k {a_i b_i^{-p} = 1}$

and the solution to the recurrence can be obtained exactly as in the master theorem, but you must compare $f(n)$ with $n^p$ instead of $n^{\lg_b a}$.

For your recurrence, $p = 0.954101 \quad$ so that $f(n) = n \quad $ dominates $n^p = n^{0.954101}$ and therefore, $T(n) = O(n) \quad$ (you may want to verify that the master theorem regularity condition also holds).

Akra and Bazzi also proved a more general result.


Suppose that you have a CNF formula $x$ with input size $n$, and that you can solve $\text{SAT}$ in $O(n^c)$ time for some constant $c$.

We construct a new formula $y$. For each clause $l_i$ in $x$, with terms $v_{i,k}$, add a new variable $t_i$ and the CNF clauses $\bigwedge_i(\neg t_i \vee l_i)$ and $ \bigwedge_{i,k} (t_i \vee \neg v_{i,k})$.

Now this formula is only satisfiable if $t_i$ is assigned a truth value equal to $l_i$, and our input size is bounded by linear function of the original size. We then add a "at least $k$ out of $n$" constraint to this formula on the $t$ variables. This also adds a polynomial number of clauses. Now the formula is only satisfiable if at least $k$ clauses of the original formula are satisfiable.

Now we can simply solve $\log_2(n)$ instances of the above formula, doing a binary search with $k$ to find the maximal number of clauses that are satisfiable simultaneously.


Object recognition - given an image, does it contain a particular 3D object of interest?

If you have one or several images of a particular "sink" or object, then you can possibly use SIFT or SURF or other feature extraction/matching algorithms to match the objects up. You can investigate the OpenCV project (wikipedia, project); it includes many of these (possibly patented) algorithms. You can get an idea of how they work and what they can do by searching youtube for "opencv". If you specialize in matching previously known instances of a particular object, this might be appropriate. Additionally, there is much research specializing in facial recognition, so you can possibly find work on that.

Another project of interest: Sketch2Photo: Internet Image Montage. I don't know how they do it though, or if it can reliably identify anything; it seems to rely on some sort of recognition, and semantics search as well (you must name the objects in the sketch). You can read their paper (PDF)

If you want to recognize a generic "sink" concept or many multiple generic concepts, then it is bordering on strong(er) AI. There are lots of machine learning projects, and I am not sure which are useful for this or practical, but to demonstrate how cutting edge this is (and possibly not practical unless you spend a lot of time and research), Google (paper (PDF)) has made a giant GPU neural network that it successfully trained to recognize cats, presumably learning some sort of ability to conceptualize a more abstract "idea" of what a cat looks like. Related work by Yoshua Bengio; wired article; open source project.

This is "cutting edge", so again not practical, but just pointing out that you are trying to recognize generic things, and Google is working so hard just to recognize generic cats, you are in for a lot of work, or a restriction/trick/shortcut.


Can pseudo random number generator generate all possible sequences?

If you are considering a pseudorandom generator that can work with seeds of any length, then the answer is "It depends". It depends on the pseudorandom generator. There are pseudorandom generators for which the answer is yes (e.g., $G(x)=x$, or any bijective $G$), and pseudorandom generators for which the answer is no (e.g., $G(x) = G'(\text{SHA256}(x))$, where $G'$ is a pseudorandom generator that accepts fixed-length seeds, is almost certainly such an example).

In practice, pseudorandom generators usually have a fixed-length seed.  In that case, if the length of the output is longer than the length of the seed, then there exists an output that isn't produced by any seed (of that length).  This follows from the pigeonhole principle.

In practice this almost certainly doesn't matter.  Usually what matters is whether the output of the pseudorandom generator passes statistical tests, or whether it is indistinguishable from true-random bits.


What is the complement of the language with all ucv with u ≠ v?

The complement of a language $L$ over an alphabet $\Sigma$ consists, by definition, of all words over $\Sigma$ that are not in $L$. If you use this definition, you find out that $\overline{L}$ consists of all words of the form $wcw$ for $w \in \{a,b\}^*$ (like your friend said), as well as all words which contain either no $c$ or at least two $c$s.

The complement operation for languages, like the complement operation for sets, assumes an underlying universe. In the case of languages, the underlying universe is $\Sigma^*$, where $\Sigma$ is the alphabet that the language is defined over. You an think of languages in at least two ways:

A language is a pair consisting of an alphabet $\Sigma$ and a subset of $\Sigma^*$. We usually only explicitly mention the second part.
A language is a collection of "words" over some universal alphabet. We can think of the language as being over any alphabet which includes all the symbols appearing in the language.

While the more correct view is the first, the more practical view is the second. Therefore, whenever you take the complement of a language, you must make sure with respect to which alphabet the complement is taken. This can be done in at least two ways:

When you define the language, you also mention the underlying alphabet.
When you take the complement, you state with respect to which alphabet you are complementing it.

For example, you could say:

  Let $L$ be the language over $\{a,b,c\}$ given by $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$?

Or you could say

  Let $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$ (as a language over $\{a,b,c\}$)?


In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree?

This one is a bit tricky! Here is the idea. We would like to use the pigeonhole principle. However, there are $n$ vertices and $n$ possible degrees $0,\ldots,n-1$, so the pigeonhole principle allows the situation in which each degree appears exactly once. We can flatly rule it out for values of $n$ which are of the form $4m+2$ or $4m+3$ using the handshake lemma, which states that the sum of the degrees is even, but what about the general case?

It turns out that to solve the general case we don't even need the handshake lemma. The following observation suffices (and explains why we need $n>1$):

   If $n > 1$ then a graph cannot contain both a node of degree $0$ and a node of degree $n-1$.


Is detecting easy instances of NP-hard problems easy?

The problem isn't really well-posed.  For any particular instance, there is a single solution, say $S$.  Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what input you give it, all it does is just print $S$.  This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$.

Therefore, the answer to your question is "Yes", but for uninteresting reasons.  It's possible you might need to think more about how to formulate your question to match what you really want to know.

The final part of your question is actually a bit different.  It doesn't ask about a single instance $I$.  Rather, it asks about a special case of the problem, i.e., an infinite family of instances that is a proper subset of all possible instances for $\Pi$.  In that case, the answer is "it depends"; some special cases might remain NP-hard, and others might be in P.

Finally, I don't know what it means to say "The adversary knows X but you don't".  I'm free to write an algorithm that assumes X is true and only works when X is true.  "Knowledge" is a funny thing and not well modelled by the kinds of tools you seem to be talking about; complexity theory is more about "existence" than "knowledge".


If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

The second question is the easier one, we can just pick any string $\varsigma$ in the infinite Turing recognizable language $S$, and let $S' = S\setminus\{\varsigma\}$. Then you should be able to construct a TM that recognizes $S'$ from the recognizer $R$ for $S$.

The normal proof for the first question is trickier, relying on two facts:

Every Turing recognizable language has an enumerator (a TM that prints out the strings in the language one by one).
If a language has a lexicographic enumerator (a TM that enumerates the strings in the language in lexicographic order), then it is decidable.

So you start with $S$, which must have an enumerator $E$ that prints out, one by one, the strings in $S$ in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using $E$ as a subroutine. It doesn't have to print out everything in $S$, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.


Matrix chain multiplication recurrence and its solution

We get the recurrence by considering all possible ways of breaking up $A_i \times \cdots \times A_j$.
Specifically, we consider $(A_i \times \cdots \times A_k) \times (A_{k+1} \times \cdots \times A_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.


Using Subset Sum algorithm $O(n)$ times to find the subset

Suppose that $\mathit{sum}$ is the sum of some subset of $A[2],\ldots,A[n]$. Then you can just remove $A[1]$.

Conversely, if $\mathit{sum}$ is not the some of any subset of $A[2],\ldots,A[n]$, then any subset summing to $\mathit{sum}$ must contain $A[1]$. Therefore it consists of $A[1]$ together with a subset of $A[2],\ldots,A[n]$ summing to $\mathit{sum}-A[1]$.

Either way, we have eliminated $A[1]$. We can then go on and eliminate $A[2],\ldots,A[n]$ in sequence.


The average-case lower bound for uniformly distributed data is $\Omega(\frac{n^2}{2^p})$, $p$ here denotes the number of increments, not actual gaps.

The number of passes is given as the input with gaps, which are in form of list, say $\{k_1, k_2,\dots,k_p\}$ where given $k$ is single increment value. There are $p$ increments to go, this $p$ is in the equation.

To avoid explicit list one may use shrink factor, which behaves similarly to shellsort and use the gap divided by consecutive powers of this factor.


Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

Hint: If $A$ reduces to $\overline{A}$ then $\overline{A}$ reduces to $A$ (using the same reduction).


Why does a graph traversal algorithm is initialised with visited[s]←true

Suppose you don't mark the start vertex as visited. As you explore the graph, you might come back to the start and begin to explore from there again. Since the first thing you do is visit the start, it's marked as visited at the start of the algorithm.

However, the given algorithm clearly doesn't perform a graph traversal. It adds the start node to the list, then marks all its neighbours as visited, one at a time, then deletes the start node from the list, then terminates. The line

visited[j]←true;

should be

visited[j]←true; LIST←LIST+{j};


Differences and relationships between randomized and nondeterministic algorithms?

Non-deterministic algorithms are very different from probabilistic algorithms.

Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. Probabilistic algorithms are practical, and are used for example by your computer when generating RSA keys (to test that the two factors of your secret key are prime). Probabilistic algorithm which don't use any coin tosses are sometimes called "deterministic".

Non-deterministic algorithms are ones which "need a hint" but are always correct: they cannot be fooled by being given the wrong hint. As an example, here is a non-deterministic algorithm that factors an integer $n$: guess a factorization of $n$, and verify that all the factors are prime (there is a "fast-in-theory" deterministic algorithm for doing that). This algorithm is very fast, and rejects false hints. Most people think that randomized algorithms can't factor integers that quickly. Clearly this model of computation isn't realistic.

Why do we care about non-deterministic algorithms? There is a class of problems, known as NP, which consists of decision problems which have efficient non-deterministic algorithms. Most people think that the hardest problems in that class, the so-called NP-complete problems, do not have efficient deterministic (or even randomized) algorithms; this is known as the P vs NP question. Since many natural problems are NP-complete, it is interesting to know whether in fact they are not solvable efficiently, in the worst case (oftentimes, the instances which arise in practice are in fact solvable in reasonable time).


Understanding terms related to 2SAT algorithm

The terms universal vertex and existential vertex are not universal, but rather specific to this specific theorem. The context is a graph on the set of literals (variables and their complements). Presumably for every clause $\ell_1 \lor \ell_2$ in $C$, there is an arrow from $\bar{\ell}_1$ to $\ell_2$.

A vertex is called universal if its corresponding variable is universally quantified, that is, quantified as $\forall x_i$. In other words, if $Q_i x_i = \forall x_i$ then the vertices $x_i$ and $\bar{x}_i$ are universal.

Similarly, a vertex is called existential if its corresponding variable is existentially quantified, that is, quantified as $\exists x_i$.


Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

Suppose you have a polynomial-time algorithm $\mathcal{A}$ to solve this problem, then consider a graph $G$ and arbitrary two vertices $s$ and $t$. We construct a new graph $G'$ by add a new vertex $t'$ into $G$, as well as an edge $(t,t')$. Now we have

\begin{align}
\text{#(paths from $s$ to $t$ in $G$)} =&\ \text{#(paths from $s$ to all other vertices in $G'$)}\\
&-\text{#(paths from $s$ to all other vertices in $G$)}.
\end{align}

That means, we can use $\mathcal{A}$ to count the number of paths between two vertices in polynomial time. However, the latter problem is #P-hard. So such an algorithm $\mathcal{A}$ does not exist unless $\mathbf{P}=\mathbf{NP}$.


Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

What you draw is an NFA, because you do not have both transition for $a$ and $b$ in two accept states.
Indeed, you need 4 states at least. Because you have 4 different states:

Initial state
Detect $a^*$ strings
Detect $b^*$ string
None of them

You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state with the others. Definitely you can't merge the 4th state with second and third state. Hence. the only possibility is merging the 4th state with the first state. But, we have some transitions from the initial state to other states, and if we merge the 4th and the first state, we will accept some strings that are not totally $a$ or $b$. And that is the contradiction to the definition of the language. Therefore, we need a state to go there if we found any $b$ in the middle of some $a$s or vice versa.


Examples of processes / problems that cannot be tackled by Turing Machines

I'll address as answer only part of the question (see my comments for why not all of it). The interesting phylosophical part of the question is basically asking if the Church-Turing thesis (CTT) describes all that happens in the universe. This is much more a physics question than it really is a CS question. CTT has been extended to the Church–Turing–Deutsch principle to account for quatum computers; it basically states that a quantum computer can simulate any physical process in the universe.

So what about continuous processes that we normally model over $\mathbb{R}$? Well, there are two aspects of this:

Models of computation with infinite-precision real-numbers have been devised. Whether you think such a model is the "right" one for physical processes, depends on physics and...
There are tough issues like the Bekenstein bound, which limit the amount of information that can exist in a finite region of space as we currently understand it. For details on this latter issue, it's much better to ask on our physics sister site.

A bit more info with pointer to additional readings is found at https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis


$\sum_{i=1}^k\frac{1}{i}$ is the $k$th harmonic number, which is $\Theta(\log k)$.


Equivalence between two definitions of Tree width

First, let me note that the claim, as stated in the question, is false:
Consider the following graph:

  $\begin{matrix}  & & 2& - & 3\\
& \diagup\\
1 & & | & & |\\
& \diagdown \\
 & &4 &-& 5
\end{matrix}
$

The complete graph on $5$ vertices is a chordal completion of this graph. However, this graph has treewidth $2$. (A decomposition is $\{1,2,4\}$, $\{2,3,4\}$, $\{3,4,5\}$ )

The correct claim is

  The treewidth of $G$ of is the size of the largest clique $\omega(G) - 1$ in a chordal completion with the minimum largest clique of the graph $G$.

Now, a proof is as follows: if the treewidth of $G$ by tree decomposition is $k$, then every tree decomposition has a bag of size at least $k$. We use the concept of a separator graph from a paper by Parra and Scheffler, in particular the fact that every maximal clique in the separator graph of $G$ is a tree decomposition of $G$ (This can be seen by comparing the definition of tree decompositions with those in the paper)

Then, by Theorem 4.7$^*$ from the same paper, every minimal chordal completion of $G$ has all the bags of some tree decomposition as a clique. This means every minimal chordal completion of $G$ has a clique of size $k$, so the chordal completion method also gives a tree-width of $k$. $\square$

*: Paraphrased in our notation, Theorem 4.7 states:

  A graph $H$ is a minimal chordal completion of $G$ if and only if $H$ is the graph $G$ with exactly the edges added such that all vertex sets in $\mathcal{S}$ are cliques. Here $\mathcal{S}$ is a maximal clique in the separator graph, which consists of minimal separators of $G$.

I attempted to find a proof using only elementary techniques, but I don't think an easy proof without any deeper theory would be easy to find.


Notation Conventions for Tree Data Structures

You can use functions.

Let $node$ be an arbitrary node of the tree.

Then $data(node)$ is data associated with $node$, $children(node)$ is set of child nodes of $node$ and $parent(node)$ is parent of $node$.

For data associated with $i^{th}$ child of $node$ you can use $data(children(node)_i)$ etc.


Shortest path with nodes containing collectibles of negative cost

This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP.  Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish.  Now running a solver for your problem will give the solution to the TSP.

I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier.  If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.


To your first question, suppose your non deterministic machine has two transition functions $\delta_0,\delta_1$ (if you allow arbitrary number of transitions, then you can construct an equivalent Turing machine with only two transitions by adding more states). In that case, it is intuitive how to use the one time read witness. Read $w\in \{0,1\}^{p(|x|)}$ as a computation sequence, i.e. the $i'th$ bit is $0$ if $\delta_0$ is used and $1$ otherwise. Follow the computation described by $w$, and accept iff the original non deterministic machine accepted in this computation. I leave it to you to complete the details.

As for your second question, the class generated is indeed $NP$. Obviously $VNL\subseteq NP$, so it remains to see why $NP\subseteq VNL$. Let $L$ be some language in $NP$, so we have $L\le_p SAT$, where the reduction can be computed in logarithmic space (verify that the reduction used in the proof of Cook-Levin's theorem can indeed be computed in logspace). Let $f$ be the reduction from $L$ to $SAT$ computable in logarithmic space. Given $x\in \Sigma^*$, we would like our witness $w$ to be a satisfying assignment for $f(x)$, since we can verfiy an assignment in logarithmic space. The problem is that $|f(x)|$ is polynomial in $|x|$, so we cant write it in our work tape. You can solve this by having $f(x)$ provided in the witness (along with an assignment), and your machine could verify for all $1\le i\le |f(x)|$ that $w_i = {f(x)}_i$. Luckily, since $f$ is computable in logspace, you can verify that the witness provided the correct $f(x)$, and check if the assignment satisfies $f(x)$.


Can the foundation of computer science be implemented to include new rules of inference so that computer can do causal reasoning?

This is a hot topic at the moment. Read this recent paper by Judea Pearl for example. In general, ML and AI are not very good at causal inference at the moment, because it requires a symbolic representation to build causal graphs. Attempts are being made, however, see e.g. https://arxiv.org/abs/1711.08936 or https://arxiv.org/abs/1709.05321.


It’s a trick question. There must be four letters or more. Let the last letter be a, where a is 0 or 1. If any other letter other than the first or second to last is a, then the string is in L. (Pick x = a, w = everything before the first a, y = everything between first and last a). If you can’t find a in these places, the string cannot be in the language because you can’t match the last x with another one.

So you don’t have to check for two equal strings of identical length at all, the language is much simpler. And it is regular.


Find subgraphs that can only be reached by two nodes

I don't know if there's a name for such subgraphs, but here's something to get you started.
If you require the subgraphs to be connected
A polytime algorithm for $G=(V,E)$ would be: for every possible unordered pair $(A,F)\in \binom{V}{2}$ consider the connected components of the graph induced by $V\smallsetminus\{A,F\}$. Then consider the classes which contain at least a neighbour of $A$ and one of $F$ (this step is required if the original graph was not connected). Then for each subgraph you found you can "add $A$ and $F$ back in" and look for their distance in the graph.
Let's sketch correctness (only the step about the subgraphs we are looking for being the connected components needs to be verified).

All components are solutions: by construction they only share links with themselves and A and F, and are connected.
All solutions are components: they are connected and only connect to the rest of the graph through A and F.

I am guessing you can do much better in runtime, but your problem seems to be in $P$ at least.
If you don't
You need to also consider combinations of the subgraphs found above, but in terms of the minimum distance it doesn't change much.


How to prove if an algorithm is reentrant?

One approach is to design your code so it is "safe by construction", so re-entrant calls cannot happen.  For instance, one way to do this is to use mutual exclusion to ensure that your method can't be invoked again while it is in the middle of running, to ensure you'll never have two instances running at the same time.  For instance, this kind of approach is often used to ensure that interrupt handlers are correct: they often clear interrupts at the beginning and re-enable them at the end.

Another method is to take whatever code you already have and try to prove it will continue to function correctly even in the presence of re-entrant invocations.  Here you can pick your favorite formal logic for reasoning about program correctness.  For instance, you can use Hoare-style logic to specify the intended functionality and prove it correct.  Then, you consider a tweaked version of your code, where before and after each statement, there is a (non-deterministic) possibility of a recursive invocation of the method being externally invoked; now you prove that the tweaked version continues to meet the spec.  You can replace Hoare logic with any other method for program verification.


Efficient data structure for matching 3D lines

Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line.  Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$).  Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we can take $p$ to be a point whose $z$-component is zero.

So, let's represent any line by the pair $p,v$, where $v$ is chosen to have norm 1 and where $p$ is chosen to have its $z$-component be zero.  Then this is a canonical representation of the line: each line has a unique representation, and two lines coincide iff their $p,v$-representations are identical.

This means that you can store each line in a hash table, where you store the pair $p,v$.  Thus, it is a hash table where each key is a 6-tuple.  You could compress it so each key is a 4-tuple (you can represent $v$ with 2 dimensions, and you only need to store the $x$- and $y$-components of $p$), but this probably doesn't gain you much.

To deal with floating-point errors, you could round $p,v$ to the nearest multiple of $\epsilon$ before storing it in the hashtable.  Or, you could store it in a data structure that supports nearest neighbor queries, such as a k-d tree.


The appropriate technique is machine learning. Some keywords you could search for are "music speech discrimination", and you could look at this survey. (These pointers came from Vor's comment.)


Why does many to one reduction imply Turing reducibility?

To put it informally, $A\leq_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further calculation."

If you can solve a problem using a subroutine such that blah blah blah, you can solve that problem using the subroutine.


How to do compare-and-increment different locations with in memory MVCC?

I asked the question directly from paper authors, and they replied to me:

  txn-id and read-cnt are 4-bytes each (not 8 bytes as I thought before), thus it is possible to compare-and-swap in one step.


Count paths of length $n$ that a player can take

This is a question in combinatorics, and can be calculated in a closed formula.

The key settings are:

"Down" is not allowed
Visiting previously visited square is not allowed

From the two requirements, we can draw the following conclusions:

Up is always a valid move (since we never went down, going up is essentially revealing a new square)
Left is not valid after Right, but is valid after Up (revealing new row) or after Left (which is essentially unvisited)
Right is not valid after Left, but is valid after Up (revealing new row) or after Right (which is essentially unvisited)

Denote $U$, $L$ and $R$ for Up, Left and Right respectively. We can now represent a path in a string like so: $P = (U,U,U,U,L)$

The question is now: How many valid paths strings of length $n$ are there?

Let $T(n)$ be the number of valid strings of length $n$

If the first move is $U$ then the remaining strings are $T(n-1)$
If the first move is $L$ then the remaining strings are those starting with $L$ or $U$
If the first move is $R$ then the remaining strings are those starting with $R$ or $U$

Looking at strings where the first move is either $L$ or $R$: the remaining strings are: strings starting with $U$ (twice), starting with $L$, or starting with $R$. (simple summation of all the options in 2nd and 3rd bullet).

Note that all the strings starting with $U$ + all the strings starting with $L$ + all the strings starting with $R$ is exactly $T(n-1)$ since the first move is already set.

We are left with one more instance of "all the strings starting with $U$" = $T(n-2)$ (again, first move is set)

Which results the following recursive formula: $$T(n) = 2T(n-1)+T(n-2)$$
where:

$$T(1) = 3, \space
T(2) = 7 $$

Calculations omitted, the closed formula for the relation above is:

$$T(n)= \frac{(1+\sqrt{2})^{n+1}}{2} + \frac{(1-\sqrt{2})^{n+1}}{2} $$


Is an oracle ever useful if you can't control the input instances?

As Xodarap pointed out, if you require your algorithm with the “random oracle” to always output the correct answer, then the random oracle is useless.  The problem becomes more interesting if we allow small probability of error (where the probability is with respect to the random instance chosen by the oracle).

In addition, as Vor pointed out in comments on the question, it is meaningless to say “random instance” without specifying a probability distribution.  One of the reasonable assumptions to make here is that this random instance is chosen uniformly at random from the set of all strings of length p(n), where n is the input length and p is some fixed polynomial.  We could make other, weaker, assumptions on the probability distribution.

Here we will make the assumption quite general, and will show that existence of a randomized polynomial-time algorithm with a “random oracle” for NP-complete problems has a surprising consequence even under this weak assumption.

Let’s drop the requirement that the “random oracle” will solve a problem in NP (on a randomly chosen instance).  Now the “random oracle” can be any predetermined probability distribution over polynomial-length strings, and every time it is asked, it emits a string according to this probability distribution.  The only requirement is that this probability distribution depends only on the input length.  Note that your model is indeed a special case of this model.  In your model, the probability distribution is required to have the following form: it first chooses a uniformly random instance y from a set depending on the input length, and then returns a pair (y, g(y)), where g: {0, 1}*→{0, 1} is the characteristic function of some decision problem in NP.  Now we allow any probability distribution, as long as the distribution is determined by the input length alone.

An “oracle” of this general form is called a randomized advice.  The class of decision problems which can be decided by a randomized polynomial-time algorithm with a randomized advice (with bounded two-sided error) is called BPP/rpoly, and it is known that this class is equal to P/poly.  (The inclusion BPP/rpoly⊆P/poly can be proved in the same way as a well-known inclusion BPP⊆P/poly.  For a proof of the latter, see e.g. Theorem 6.3 of Goldreich [Gol08].)

This means that if an NP-complete problem can be solved in your model, then NP⊆P/poly.  However, it is known that NP⊆P/poly implies that the polynomial hierarchy collapses to the second level [KW98, Cai07].  Most complexity theorists consider a collapse of the polynomial hierarchy as a big surprise.  If we believe that the polynomial hierarchy does not collapse, then NP-complete problems cannot be solved efficiently with the “random oracle” in your sense.

References

[Cai07] Jin-Yi Cai.  S2p ⊆ ZPPNP.  Journal of Computer and System Sciences, 73(1):25–35, Feb. 2007.  DOI: 10.1016/j.jcss.2003.07.015.

[Gol08] Oded Goldreich.  Computational Complexity: A Conceptual Perspective.  Cambridge University Press, 2008.

[KW98] Johannes Köbler and Osamu Watanabe.  New collapse consequences of NP having small circuits.  SIAM Journal on Computing, 28(1):311–324, 1998.  DOI: 10.1137/S0097539795296206.


Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

Minimizing regular expressions is very hard, see for example a paper of Gramlich and Schnitger, who show that no $o(n)$ approximation algorithm exists unless P=PSPACE. Another type of answer to your question is the formal systems mentioned in my answer to your related question.


Why does Feistel encryption algorithm encode half block every time?

You can't.  Some of the block is used as the input to the F function, and the rest is modified. Those can't overlap.  If you wanted to modify all of the block, there wouldn't be any input to the F function.

You might be interested in https://en.wikipedia.org/wiki/Feistel_cipher#Unbalanced_Feistel_cipher


Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

Your algorithm goes over all pairs $(\ell,h)$ of indices such that $1 \leq \ell \leq h \leq n$, and for each of them, runs $\Theta(1)$ operations (the rest of the steps are insignificant from an asymptotic point of view). If there are $M$ such pairs, then the best case, worst case, average case complexity are all equal to $\Theta(M)$.


How to learn computer science the right way

Firstly, most of the things you are talking about fall under the category of programming, rather than computer science. Programming is a useful tool for computer scientists, and indeed some computer scientists study programming, but it programming barely scratches the surface of what computer science is about.

Why not try a free online course, such as one offered by coursera? There are many many courses, from programming to theory to machine learning to software engineering. All are free and typically the standard of quality is extremely high.


Operating System - CPU scheduling Decisions

The only way that a process can go from "ready" to "running" is if the scheduler just scheduled it. Running the scheduler as soon as the process started running would mean that you'd actually be running the scheduler the whole time.


The outer most while loop ends when $\text{sq} = n$ and by definition $\text{sq} = i^2$ and thus it will run $i^2 = n \Rightarrow i = \sqrt{n}$ times ( as we increment $i$ by one each iteration).
Note that -
The for loop runs at $\log(j)$ from $1$ to $\text{sq} = i^2$ and $1 \leq i \leq \sqrt{n}$  so we have this sum:
$$\sum_{k=1}^{i^2}\log(k) ~~ \forall i \in\{1,2, \dots,\sqrt{n}\}$$
Recall: $\log(a) + \log(b) = \log(a \cdot b)$
Some examples:
$i=1 \Rightarrow \sum_{k=1}^{1}\log(k) \Rightarrow \log(1!)$
$i=2 \Rightarrow \log(4!)$
$i=3 \Rightarrow \log(9!)$
$i=4 \Rightarrow \sum_{k=1}^{16}\log(k) = \log(1)+\log(2) + \dots + \log(16) \Rightarrow \log(16!) ~~~~~~ \\
\text{etc... until } i=\sqrt{n}$
And thus this whole system of loops runs at:
$$\sum_{k=1}^{ \sqrt{n}}\log[(k^2)!] = \log{( \prod_{k=1}^{\sqrt{n}}k^2! )}$$
This can be bounded by $O(\sqrt{n} \log(n!))$ or $O(n^{1.5} \log(n))$ by taking the largest element in that sum ( $\log(n!)$ ) and multiplying it by the number of elements ( $ \sqrt{n}$ )


Shortest sub-sequence of one string, that's not a sub-sequence of another string

A dynamic programming algorithm seems to work.

Given a prefix $X_k = x_1 x_2\dots x_k$ of string $X$ ($X$ is of length $s$, so $X = X_s$), a prefix $Y_m = y_1 y_2 \dots y_m$ of string $Y$ ($Y$ is of length $t$, so $Y_t = Y$), and a length $L$, we determine if there is a subsequence of $X_k$ which is also a subsequence of $Y_m$, such that the sub-sequence is of length exactly $L$ and ends at $x_k$. Call that (boolean) value: $\text{is_there}[k,m,L]$.

We will also need to know if there is a subsequence of $X_k$ which is also a subsequence of $Y_m$ such that the subsequence is of length exactly $L$ and ends at or before $x_k$.  Call that boolean value $\text{is_there_any}[k,m,L]$.

These satisfy the recurrences:

$$\text{is_there}[k,m,L] = \text{is_there}[k, m-1, L] \vee (x_k = y_m \wedge \text{is_there_any}[k-1,m-1,L-1])$$

and

$$\text{is_there_any}[k, m, L] = \text{is_there}[k, m, L] \vee \text{is_there_any}[k, m-1, L]$$

The smallest $L$ such that $\text{is_there}[k, t, L] = false$ for all $k$ gives you the result. (Note that $t$ is the length of $Y$).

If the length of the shortest such subsequence is $S$, This can be implemented in $O(stS)$ time and $O(stS)$ space by a triply nested for-loop with $L$ on the outside, then $k$, then $m$.

Something like:

Compute isThere for L = 1.
foreach L in (2 ... s)
    foreach k in (1 ... s)
       foreach m in (1 ... t)
         is_there[k,m,L] = blah
         is_there_any[k,m,L] = blah


Generate a dataset for binarization of text in images

Start with the following paper, and use it to seed a literature search using the usual methods.

Detecting Text in Natural Scenes with Stroke Width Transform.    Boris Epshtein, Eyal Ofek, Yonatan Wexler.  CVPR 2010.


graphs - finding a shortest path length not achievable by breadth first search

BFS doesn't work well on graphs with weighted edges, or in other words, graphs where the cost to travel each edge isn't equal. The reason for this is that BFS implicitly assumes equal path lengths. At each step, all nodes adjacent to the current node get pushed into the queue, regardless of the edge weights. This results in a situation where the number of edges traveled, rather than any actual edge weights, reflects the "path length".

For example, consider a graph with 3 nodes A, B, and C; the edge from A to B AB's weight is 2, BC's weight is 3, and AC's weight is 100. Since A is 2 edges (AB, BC) away from C by taking the path through B, but only 1 edge away from C by taking edge AC, BFS would choose AC as the "shortest path" even though it's weight is significantly higher than the sum of AB and BC.

Instead, try algorithms such as Dijkstra's and Bellman-Ford that explicitly take into account the edge weights (e.g. with a priority queue in Dijkstra's). They tend to have a greater time complexity, but will return the correct answer.


Annotated type system problem about conditional branch

With the above expression, two branches (if and else) have the same analysis information at their respective entry and exit points i.e. In simple terms we can say that then-branch gives rise to the same set of reaching definitions as the else-branch does.
So, this is dubious, depending on the condition of if-block it is decided control will go to then or else block which will become the exit of if-block. To follow this idea we can modify the equation like below.

We assume that if if-block gets executed as true then final(S1) is executed i.e. RD2 and for false statement final(S2) i.e. RD3 is executed. The exit of the if-block is the subset of the union of then-block and the else-block.


Conversion of nfa with self-loop to one without self-loop

Add a new state and make the self loop point to the new state and add a empty transition from the new state back to the original state.

It is straightforward to prove that this NFA is equivalent to the original.


Seeking popular science book on bioinformatics or computational genomics

this is a very broad question so am going to answer it with decent lists found across the internet most of which are sorted by some criteria (eg bestsellers, top review counts, etc). also there are so many bioinformatics books now and one strategy might be to simply go with your favorite publisher. there are some that come up often in CS areas eg O'Reilly. also, even the "x for Dummies" book series has a bioinformatics title which might be of interest to those who like that publisher. another option is to narrow it down by your algorithmic angle eg there is one based on Python and there are others that emphasize other statistical packages, etc.;

as for your tricky criteria of "inspirational" it may make sense to look for biographies of scientists in the field or stories about successful startups, and if the student is into CS, then programming exercises might verge on "inspirational".

goodreads bioinformatics books ranked by review count & ratings listed
O'Reilly bioinformatics top sellers
Amazon best sellers Bioinformatics
best book on bioinformatics for a computer scientist stackoverflow
suitable book on bioinformatics for cs student biology.se
recommend your favorite bioinformatics books biostars thread


Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions

The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.

   That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition.
 You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).

Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.


Measure two qubits, one from entangled pair, in Bell basis?

I figured out that as we are operating on 3 qubits ($|v\rangle$ and $\beta_{00}\rangle$ pair) and we want to perform CNOT on the first two (if we enumerate like 1- $|v\rangle$, 2- first from pair, 3 - second from pair) it is just like we want to perform $CNOT \otimes I$ on $|v\rangle \otimes |\beta_{00}\rangle$.

After performing the CNOT described above we need to perform H on the $|v\rangle$ qubit, which is now entangled (as CNOT is an entangling operation), so it is like we want to perform $H \otimes I$ on the three (where $I$ is 3 x 3 identity matrix).

Beaing able to perform both steps described above we are able to perform a measurement of qubit $|v\rangle$ and the first qubit from the entangled pair $|\beta_{00}\rangle$ in the Bell basis.


Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$

Note that any amount of ones at the start or zeroes at the end has no influence on the number of $01$ pairs. Then in the middle you want any multiple of three of $01$ pairs, giving:

$$1^*(0^+1^+0^+1^+0^+1^+)^*0^*$$


Hint: What is the time complexity of the fastest nondeterministic Turing machine that is a decider for $SAT$?


Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

You can't semi-decide a non decidable problem in an efficient way.

Suppose that you have an algorithm $A$ which semidecides such a problem in, say, $T(n)$. I.e. every word in the problem is accepted within $T(n)$ steps. Assume that $T(n)$ is bounded from above by any computable total function $g(n)$ (say $2^{2^n}$, which allows $A$ to range over any efficient algorithm).

Then, the problem is decidable: run $A$ for at most $g(n)$ steps, and accept if $A$ accepts, otherwise reject.

Contradiction. QED

Asymptotically, a semidecider of a non recursive problem can never be efficient. (Unless we choose another definition of "efficient" than "low worst-case complexity", I guess)


Why is the Shannon entropy 0.94 in this example?

Back to the definitions:
$$H(L\mid A) = \sum_a p(A=a) H(L \mid A=a).$$

As you compute, $P(A=true)=6/8$ and $P(A=false)=2/8$.

However, you don't compute $H(L\mid A=true)$ but instead compute $P(L=positive\mid A=true)$.  [and the same for $A=false$.].

With standard definition of $H()$ we get,

$$H(L\mid A=true) = - 4/6\log_2(4/6) - 2/6\log_2(2/6) = 0.9182958$$
$$H(L\mid A=false) = H(1/2) = 1$$

And thus, $H(L\mid A) = 6/8 \times 0.918 + 2/8\times 1 = 0.938 \approx 0.94$.


We can't say without knowing number of stages used in pipeline. If stages are not more than $3$, it's not RAW.

First of all, this statement of mine is incorrect if we talk about data dependency. Dependency is a matter of instructions itself, architecture doesn't come into play directly. Architecture can only ensure that stall not to happens even with dependencies but it doesn't change the fact of dependencies among instructions. But in a pipeline if any data dependency results into stall then it is called data hazard.

  and even if it fetches it ,it still be a wrong value as per the instruction sequence as I2 is modifying it.

Again, as I have explained above, the modification is irrelevant here if we are just talking about dependencies. To check data hazard What we need to do is to see whether dependencies result into stall in pipelining or not. If yes, it results, then it is data hazard.


Is the superset and subset of a semi-decidable language also semi-decidable?

No, because every language $L$ satisfies $$ \emptyset \subseteq L \subseteq \Sigma^* $$ and $\emptyset$ and $\Sigma^*$ are both semi-decidable.


Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

There is no such algorithm. Start by googling undecidability. The problem itself is called "language intersection/disjointness".


PLT Redex has support for term rewriting. You'll find that most of the examples are focused on small-step operational semantics for programming languages, but in general the system allows for arbitrary rewriting, including non-determinism. It also has a bunch of nice features, like randomized testing of properties, alpha-equivalence, steppers for visualising/debugging, and excellent graphical output.
If you want higher-order syntax, you might be interested in something like ELPI.
For a super-lightweight prolog-style programming, you might be interested in miniKanren.


If you think it's false, the easiest way to disprove it would be to find a counterexample. That is, find a graph where $E \leq \frac{1}{2}(V-1)(V-2)$. Try some easy connected graphs (e.g. a straight-line path graph) and see if you can find a suitable graph.


The ID3 algorithm is one standard way to construct a decision tree.  You can also look at successors like C4.5 and others.  These aren't guaranteed to give the smallest possible decision tree (that is known to be NP-hard) but the decision tree it outputs is often fairly reasonable.


Book recommendations on the analysis of randomized algorithms

Randomized Algorithms by Motwani, Rajeev, and Raghavan contains a lot of excellent material on the design and analysis of algorithms.  They show many proofs of correctness for different randomized algorithms.


I will guide you through it, giving you the most important ideas. Yet, I will leave the details for you, many details actually. For two languages $A, B$, it holds that $A\subseteq B$ iff $A\cap\overline{B} = \emptyset$. This is an easy exercise and I leave it to you. Now given two automata $C_1$ and $C_2$, we can check whether $L(C_1)\subseteq L(C_2)$ by checking the emptiness of $L(C_1)\cap \overline{L(C_2)}$. In general, constructing an automaton for the intersection of two automata is easy, regardless of whether the automata are DFAs or NFAs (by easy I mean it can be done in time polynomial in the two automata): indeed, one can show that the product construction of automata can be generalised to NFAs. So, given two NFAs, one can build an NFA over their product to recognise their intersection. Then, to check whether the product automaton is empty, we can simply check if there is a path from an initial state to an accepting state in the product - which can be done in time polynomial in the size of the product automaton (polynomial in the size of the automata that we're intersecting). So, to solve the above problem, one can do the following.
Given automata $C_1$ and $C_2$, construct an automaton for $D = \overline{L(C_2)}$, then construct a product automaton $E$ for $L(C_1)\cap L(D)$, and finally check whether $L(E)$ is empty - which takes time polynomial in $|E| = |C_1|\cdot |D|$. So the complexity depends on the size of $C_1$, and on the size of $D$ which recognizes $\overline{L(C_2)}$. So $|E|$ is polynomial in the sizes of $C_1$ and $C_2$ iff $|D|$ is polynomial in them. To sum up:

If $C_1$ is an NFA and $C_2$ is a DFA, then $D$ is obtained from $C_2$ by flipping accepting and rejecting states. So $|D| = |C_2|$, and thus solving the problem takes time polynomial in $|C_1|\cdot |C_2|$. Hence, the problem in this case is in P.

If $C_1$ is a DFA and $C_2$ is an NFA, then $D$ is obtained from $C_2$ by applying the subset construction. So $|D| = 2^{|C_2|}$, and thus solving the problem takes time polynomial in $|C_1|\cdot 2^{|C_2|}$, which is exponential. Hence, the problem in this case is in EXPTIME. In fact, it can be shown that the problem is in PSPACE. Idea: we do not need to construct the whole product automaton, and then find a path in it. Instead, we can find this path nondeterministically on the fly in polynomial space (use the fact that PSPACE = NPSPACE, and the fact that given a state in the product, you can compute its successor states if you have the description of $C_1$, and $C_2$. Once you guess a successor state, you can remove the current state. This way, you do not need to construct the whole product, you only store the current state in the guessed path). I left out some important small details to you. Also, you can show that the problem in this case is PSPACE-hard by reducing the NFA-universality problem to it. Indeed, given an NFA $A$, a reduction outputs $C_1, C_2$, where $C_1$ is a DFA that accepts all words, and $C_2 = A$. Clearly, $L(A) = \Sigma^*$ iff $L(C_1)\subseteq L(C_2) = L(A)$. Thus, PSPACE-hardness follows.


In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?

This is over a year later, but I also found this question really frustrating, but after reading other explanations, I've finally figured it out. So, I want to share with everyone my findings!

In this problem we're guaranteed that the amount of gas is enough to go around the road once. We then have this equality
$Amount_{gas}$ = $Amount_{distance}$
$$\sum_{i=1}^{n} x_{i} = 0$$
where $x_{i}$ is the Amount of gas at station i - the cost:
$$G[i] - D[i]$$

If we reach a point $j$ such that:

$$\sum_{i=1}^{j} x_{i} < 0$$

This must mean
$$\sum_{i=j + 1}^{n} x_{i} > 0$$

Why!?!??! Because the problem promises us enough gas to cover the distance!
$$\sum_{i=1}^{j} x_{i}  + \sum_{i=j + 1}^{n} x_{i} = 0$$

If we start at point $j + 1$, which is right after we don't have enough gas,
the equation becomes
$$\sum_{i=j + 1}^{n} x_{i} + \sum_{i=1}^{j} x_{i} = 0$$

Starting at $j + 1$ means we have $\sum_{i=j + 1}^{n} x_{i}$ gas before j, so we won't have a negative number.

This agrees with the solution in EPI because we are in fact doing a vertical shift on our piecewise function $\sum_{i=1}^{n} G_{i} - D_{i} $
The pictoral graph in EPI helps us see that it's not good enough to merely spit out the first j that gives us a negative value. If instead, we find the minimum, we will have more than enough gas before we reach j (first point that gives us negative amount of gas left) and cover subsequent negative gas stations until the aforementioned minimum.


What are the closure properties of LL(k) languages?

All of these (except possibly Kleene closure) are answered (in the negative) in Rosenkrantz & Stearns, Properties of Deterministic Top-Down Grammars, 1970.
For an example of a language whose Kleene closure is non-deterministic, see this answer by Hendrik Jan.


Is there an intuitive proof for the existence of hard functions?

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. We then compute the maximal $S$ such that $C_S < 2^{2^n}$, and conclude that there must be a function that cannot be computed by a circuit of size at most $S$. The answer is $S = O(2^n/n)$, and we usually really don't care about the hidden constant; we tend to abstract away constants in complexity theory.

The same argument shows, with very small modifications, that a random function has circuit complexity $\Omega(2^n/n)$ in expectation and with high probability.

How about an explicit function with complexity $\Omega(2^n/n)$? This is a difficult open problem. The best lower bounds we have for explicit functions are $\Omega(n^3)$ for Andreev's function (see Komargodski–Raz–Tal for the best result in this direction). I am told that obtaining anything better than $\Omega(n^3)$ would be difficult due to the natural proof barrier.


Relations between statements involving universal quantifier, conditional and biconditional

Reasoning based on examples is fine for disproving implications, as you have done. In order to prove that an implication holds, however, you need something more elaborate. One possibility, as mentioned in the comments, is to use resolution to prove the implications. For example, suppose you want to show that (a) implies (b), i.e. that

$\varphi:=(\forall x.(b(c)\to c(x)))\to((\forall x.b(x))\to(\forall x.c(x)))$

is valid. We will do this by deriving a contradiction from $\neg\varphi$, which (using standard equivalences) is equivalent to

$\forall x.(\neg b(x)\vee c(x)))\wedge\forall x.b(x)\wedge\exists x.\neg c(x)$.

Skolemization results in

$(\neg b(x)\vee c(x))\wedge b(x)\wedge\neg c(a)$,

from which resolution derives first $\neg b(a)$ and then an empty clause, i.e. false. Therefore the original implication is valid.

As for your table, note that the example I gave also shows that (d) does not imply (a); the remaining 5 implications look ok.


Has there been any more progress on P vs. PSPACE compared to P vs. NP?

This doesn't really answer your question, but there is a result that under a restricted form of time travel (yes, time travel), it holds that $P=PSPACE$. I'll remark that the result is nontrivial, given the restrictions on the model.
See this explanation by Scott Aaronson.


Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?

Yes, it can be done in $O(n \log k)$ time, using exactly the approach you hinted at.

You're going to do a linear scan over the array, from left to right.  At each step, you check whether the max of the last $k$ elements is more than twice the min of the last $k$ elements.

To compute the max and min efficiently, you'll maintain a max-heap of the last $k$ elements, and a min-heap of the last $k$ elements.  Each time you move one element to the right, you add an element to each heap (insert $A[i]$ into the heap) and remove an element from each heap (delete $A[i-k]$ from the heap).

To remove elements from the heap, have two auxiliary arrays, $B$ and $C$.  $B[i]$ maintains a pointer to where $A[i]$ is stored in the max-heap, and $C[i]$ maintains a pointer to where $A[i]$ is stored in the min-heap.  To reduce space consumption, you can arrange that these two auxiliary arrays are of length $k$ rather than length $n$, if that is important.


Complexity of inserting an integer to an empty hashtable

The answer depends on your model of computation.    In other words, it depends on how you count the number of basic operations, or on what you consider to be a "basic operation".

In the transdichotomous model or Word RAM model, you can do computation on an entire word in $O(1)$ time, and the word size is guaranteed to be large enough to hold the integer (and, in particular, at least $\log n)$.  An operation on a single word counts as a single operation, even though you're operating on a bunch of bits.  Consequently, there exist hash functions that can hash the number $n$ in $O(1)$ time, in these models of computation.

In the bit complexity model, it takes at least $\log n$ time to read an integer with $\log n$ bits, so you're right that hashing $n$ will take $\Omega(\log n)$ time.

You might find it useful to read https://en.wikipedia.org/wiki/Transdichotomous_model and https://cstheory.stackexchange.com/q/2656/5038.

Ultimately, the time to compute a hash will depend on the hash function (some hashes might be even slower than the above), but this might be enough to clear up your particular question.


How does an automaton model a computer or something else?

The impetus behind all of this comes from trying to define a mathematically rigorous model of what "computation" means. Alan Turing did this in 1936 by defining a definition of a simple abstract machine that seemed to be sufficient to describe everything that we'd call computation, a device we now call a Turing Machine.

Over the years, people have investigated other models of computation that were restricted in what they could do and discovered that these simpler models were also interesting in themselves. This eventually lead to what we might call the standard introduction to computability theory, as follows.

Finite Automata. Starting with this model, we have a finite collection of states and define transitions from one state to another depending on the current character being read in an input string. Some of these states are designated as final states and the convention is that if the automaton is in a final state after reading all the characters of the input, we say that the automaton accepts the input string.

(Important Digression): Languages and problems. Starting with a machine that can determine whether a string is or is not in a particular language, we can transform this task into a task of solving a problem. For instance, we might want to solve the problem "given nonnegative integers $n$ and $m$ are they both even or both odd?" It's not hard to see that this is equivalent to "can we make a finite automaton that accepts all and only strings in the language $L_1=\{a^nb^m \mid a\equiv b\pmod 2\}$, where $a^nb^m$ is the string of $n$ copies of $a$ followed by $m$ copies of $b$. It turns out that a finite automaton can be built to do this. The point here is that any computational problem can be turned into a language recognition problem, where the language is effectively an encoding of the possible solutions. In other words, the language
$$
\{(0, 0), (0, 2), (0, 4),\dots, (2, 0), (2, 4), \dots, (1, 1), (1, 3), \dots,\}
$$
can, suitably coded, be recognized by a FA

Other Automata. It happens that finite automata can't recognize solutions to all problems. For example, a FA (finite automaton) can't recognize the language $L_2=\{a^nb^n\mid n\ge 0\}$, in other words, it isn't powerful enough to determine whether two nonnegative integers $n, m$ are equal. If we modify our FA model by including a stack where we can push or pop symbols depending on the input string (as well as change to another state), then this new model (a pushdown automaton or PDA, as it's known) can recognize the language $L_2$ and also the language $L_3=\{a^nb^mc^{n+m}\}$, so a PDA can determine whether two numbers sum to another. It happens, though, that PDAs aren't powerful enough to do the same for products. We can continue this process, adding enhancements to each abstract model of computation, and get a hierarchy of increasingly more powerful machines. The exciting part is that this hierarchy quickly comes to an end.

Turing Machines. If we take a FA and add to it an arbitrary long list (called a tape) initially containing the input and allow moves where the current state and the current contents of an element in the list determine the next state, what we write in the current list element, and whether we move one position forward or backward in the list, we have Turing's 1936 abstract machine, a Turing Machine, or TM. This simple device is extremely powerful: it can add, subtract, multiply, divide, move data to a different location on the tape, compare two chunks of data and base its actions on the results of the comparison, and do things like compute prime numbers and give the $n$-th digit of $\pi$. In fact, it can do everything that modern computers can do and more, since, being an abstract machine, it has an arbitrarily large amount of "memory" on its tape, potentially vastly larger than the number of elementary particles in the universe.

Things to do With TMs. With this model, we can perform all the tasks we're used to:

Implement Functions. We can build a TM that, say, computes square roots: given two numbers on its tape, like "3.1416#7", we can define the moves of a TM to produce the square root of the input, 3.1416, to seven digits of precision, so at the end of its calculations, the tape would contain "1.7724559". This is just an algorithm: a finite sequence of steps in some model that produces a result according to our specifications.
Language recognizers (and problem solvers). We could design a TM that recognizes the language of primes: $L_4=\{2,3,5,7,11,13,17,19, \dots\}$: given an input tape initially containing an integer $P$, this machine could determine if $P\in L_4$, namely if $P$ is the decimal representation of a prime number.
Programmable Computers. It's even possible to design a universal TM which takes a suitably coded description of a TM, $\langle M\rangle$ (perhaps by a listing of its move rules), and an input $X$ and simulate the action of $M$ on input $x$, which of course exactly what a real-world computer plus compiler does.

Remarks and Consequences

Fully fleshed out, this narrative has a flow, from simple machines to, ultimately, a machine that's more powerful than any modern physical computer. The narrative doesn't stop there, though. The Church-Turing Thesis says that anything that we would agree falls under our definition of "computation" can be accomplished by a TM. In other words, the Church-Turing Thesis is a confident bet that not only are TMs more powerful than any modern computer, but that they can accomplish anything we'd call computation on any future computer.

It gets even better, though. Since the (uncountable) infinity of possible functions from the integers to themselves is vastly larger than the (countable) infinity of possible Turing Machines, it means that there are lots of tasks that TMs (and hence computers) cannot do. That might not be a real-world problem, since the functions that TMs can't compute are in a very real sense undescribable, but there are also plenty of seemingly programmable tasks that TMs (and hence computers) cannot do. For example, "given a listing of a program and an input for that program, can we always determine whether that program will eventually halt when given that input?" Professional programmers would love such a tool, but it is provably impossible to construct a program to determine, for all program listings and inputs, whether that program will perhaps enter an infinite loop or not. Similarly, there is no hope of determining, in all cases, whether a given program will behave according to some set of specifications. So our fascinating narrative has a sad ending: there are (infinitely many) tasks computers will never be able to do.


Give a grammar to show whether a language is regular or context-free

Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\{w : |w| \equiv 0 \pmod{2}\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.


Is there a solution for this maze problem in polynomial time?

If the number of keys is unlimited, the problem is NP-hard, by a straightforward reduction from the traveling salesman problem: simply put a different key in each vertex,  and have a single chest that requires all the keys.


Can bar codes theoretically be considered a type of digital memory?

There is no god-given definition of (read-only) digital memory. We can think of several reasons for a writing system to be considered digital:

Can be read by a computer.
Cannot be read by a human.
Has high density.
Designed for use by computers.

Barcodes satisfy the first two properties, but not the third one: their density is rather low. Nevertheless, both traditional barcodes and modern QR codes were designed to be read by machines, and this gives credence to your claim.


What does an NFA do if there's no transition with the correct symbol?

In a DFA, if you are in state $p$ and see an input character $c$, one of three things may happen:

You can consume that character (i.e., read it) and change to state $q$ ($q$ may be $p$ or not).
There may not be a move defined for the pair $(p, c)$ in which case the DFA halts and rejects the input string.
If the DFA is in a final state after having read all the input, it accepts the input, otherwise it rejects the input.

For an NFA, you have more possibilities:

In state $p$ with input $c$ you can consume the input and change to several states $q_1, q_2, \dotsc$ .
In state $p$ you can elect not to consume the input and change to several states $q_1, q_2, \dotsc$. This is called an epsilon move. In essence, your machine may change state without reading any input.
As with a DFA, there may not be any move defined for the pair $(p, c)$ or $(p, \epsilon)$ in which case the NFA halts that branch of execution.
If the NFA is in a final state in any particular branch of its execution and has consumed all the input, it accepts the input. If it hasn't reached any accept state after having read all the input, it rejects.

In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.

Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.


How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?

$f(n)$ is the well-known Fibonacci sequence.

Let $\alpha=\frac{1+\sqrt5}2$ be the golden ratio and $\phi=\frac{1-\sqrt5}2$. It is shown here that
$$f(n)=(\alpha^n-\phi^{n})/\sqrt5$$

Gnasher729 conjectured that $F(n) \approx 0.72 * n * f(n)$. Following that clue, we can find the following identity holds for all cases we tested by trial and error.
$$F(n)= nf(n) - (n-2)f(n-2) + (n-4)f(n-4) - (n-6)f(n-6) + \cdots$$
where the sequence of summands goes on as long as the summand makes sense.

How to prove that long formula? We can observe it implies for $n\ge2$,
$$ F(n) = nf(n) - F(n-2).$$

Let us prove that simple recurrence relation of $F(n)$ by induction on $n$.

The base cases when $n=2$ and when $n=3$ is easy since f(2)=1, f(3)=2, F(2)=1+0+1=2 and F(3)=2+1+2=5.

Suppose it is true for $n\le k$, where $k\ge3$.
$$\begin{aligned}
F(k+1) =& F(k) + F(k-1) + f(k+1)\\
=& (kf(k) - F(k-2)) + ((k-1)f(k-1) - F(k-3)) + f(k+1)\\
=& k(f(k)+f(k-1))-f(k-1) - (F(k-2)+F(k-3)) + f(k+1)\\
=& kf(k+1)-f(k-1) - (F(k-1)-f(k-1)) + f(k+1)\\
=& (k+1)f(k+1)- F(k-1)\\
\end{aligned}$$

Now that we have proved that simple recurrence relation of $F(n)$, it is immediate to prove that long formula, which can also be stated succinctly as

$$F(n)=\sum_{0\le i\lt n, i\text{ even}}(-1)^{i/2}f(n-i)$$

Interested readers may enjoy the following exercises, roughly in the order of increasing difficulty.

Exercise 1. Given the above formulas for $f(n)$ and $F(n)$, show that $F(n)=\Theta(n\alpha^n)$.

Exercise 2. Given the above formulas for $f(n)$ and $F(n)$, show that $$\lim_{n\to\infty}\frac{F(n)}{n\alpha^n}= \frac1{1+\alpha^{-2}}\approx 0.7236$$

Exercise 3. Find a close formula for $F(n)$.


Is There a Complete Problem for the Class of Turing Decidable Problems?

Generally a class having a complete problem under a nice class of reductions
implies that the class can be enumerated.
$\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.

Here is the argument:

Assume that there is a complete problem $A$ for $\mathsf{R}$.
Therefore for any problem in $\mathsf{R}$ can be obtained from
a reduction (let's say polynomial time many-one reductions) combined with $A$.
We can computably enumerate the reductions,
therefore we can computably enumerate $\mathsf{R}$.
But $\mathsf{R}$ is not computably enumerable
(otherwise we could diagonalize).

In the literature look for the set of total recursive/computable functions.


Number of FLOPs (floating point operations) for exponentiation

Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...

There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.

Convert the non-negative integer power to base 2.
Count the number of ones in this representation.
Add the power of two corresponding to the most significant non-zero bit in this representation.
Subtract one.

This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.

  ... and how does it work if $n$ isn't an integer?

There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $\exp(n\ln(x))$.)


Master theorem and constants independent of $n$

Use a recursion tree (otherwise known as the proof of the Master Theorem).  I'll assume here that $r>1$, since otherwise the recurrence never bottoms out.

The root of the recursion tree for $T(n)$ has value $nr^2$.
The root has $r^2$ children, each with value $(n/r)r^2 = nr$.  Thus, the total value of all children is $nr^3$.
Each child has $r^2$ children of its own, each with value $(n/r^2)r^2 = n$.  Thus, the total value of all grandchildren of the root is $nr^4$.
An easy induction argument implies that for any integer $\ell\ge 0$, the root has $r^{2\ell}$ descendants at level $\ell$, each with value $(n/r^\ell)r^2 = nr^{2-\ell}$.  Thus, the total value of all nodes at level $\ell$ is $r^{2\ell} \cdot nr^{2-\ell} = nr^{2+\ell}$.
The level sums $T(n) = nr^2 + nr^3 + \cdots + nr^{2+\ell} + \cdots$ form an increasing geometric series, so (for big-Oh purposes) only the deepest level matters.
The recursion reaches its base case when $n/r^\ell = 1$, or equivalently, when $\ell = \log_r n$.
The total value of all nodes at that level is $nr^{2+\ell} = nr^{2+\log_r n} = n^2r^2$.
We conclude that $T(n) = O(r^2 n^2)$.

These notes describe the recursion tree method in more detail, with lots of examples.

Equivalently, define $S(n) = T(n)/r^2$, so that $S(n) = r^2 T(n/r) + n$, and then use the Master theorem to solve for $S(n)$.  But that would require remembering the Master theorem, which I don't.


How was $T(N)$ derived for this function?

Here, $C_1$ and $C_2$ are constants that concern several instructions:

$C_2$ corresponds to instructions executed only once l <- 0, the last executed test of while(A[l]!=NULL) and return l
$C_1$ corresponds to instructions executed several times: each test of while(A[l]!=NULL) but the last, and l<-l+1. Those are executed a total of $N$ times.

We indeed get $T(N) = C_1\times N + C_2$.


Some questions about the Computability of Turing Machines

The answer is "we don't know without more information" for all 4.

Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable.

On the other hand, suppose $g$ is a total non-computable function (which is a special case of $g$ being a partial non-computable function), and suppose $f$ is the constant zero function $f(x) = 0$. In this case:

$f \circ g$ is the constant zero function, which is obviously computable.
$g \circ f$ is also a constant function. We don't necessarily know what the constant is, but that doesn't matter; every constant function is computable. See How can it be decidable whether $\pi$ has some sequence of digits?

Deterministic vs. non-deterministic Turing machine doesn't affect the answer, because a deterministic Turing machine can simulate the execution of a non-deterministic Turing machine (potentially with an exponential slowdown) by dovetailing.


Sum of distances between points on one-dimensional axis

Let us start with the formula for the sum of distances:
$$
\begin{align*}
D(\ell,r) := \sum_{i=\ell}^r [A_r - A_i] &= (r-\ell+1) A_r - \sum_{i=\ell}^r A_i \\ &= (r-\ell+1) A_r - \sum_{i=1}^r A_i + \sum_{i=1}^{\ell-1} A_i.
\end{align*}
$$
In time $O(n)$ we can compute an array $B_i = \sum_{j=1}^i A_j$: indeed, $B_0 = 0$, and $B_j = B_{j-1} + A_j$. The formula above then translates to
$$
D(\ell,r) = (r-\ell+1)A_r - B_r + B_{\ell-1},
$$
which can be computed in $O(1)$.


Macro expansion is done in which phase of a compiler?

It's completely dependent on the language. Different languages have wildly different notions of macros. I'll just give a few examples; other situations are possible.

The original C language (K&R C)

Macros are expanded by the preprocessor, which is a separate program that runs before the compiler proper. Macros perform a simple text substitution. This program prints 1, because PLUS()PLUS() expands to ++ which is the increment operator.

#include <stdio.h>
#define PLUS() +
int main()
{
    int x = 0;
    PLUS()PLUS()x;
    printf("%d\n", x);
    return 0;
}

The modern C language (ANSI C)

Macros are expanded by the preprocessor, which acts on tokens, after lexical analysis. Thus, a macro only expands to whole tokens, but can contain things like unbalanced parentheses. The program above prints 0, because each PLUS() expands to a + token, so the instruction is equivalent to + + x;.

Lisp

Macros act on the program's representation as an abstract syntax tree, i.e. after parsing. Thus a macro expands to a sexp (Lisp's term for an abstract syntax tree), and its arguments are themselves sexps. Macros are expanded before variable resolution. Such macros are said to be unhygienic. Care must be taken not to mix up variables introduced by a macro from the variables of the program fragments.

(defmacro repeat (count func)
  `(loop for i from 1 to ,count
      do (apply ,func nil)))
(repeat 3 (lambda () (print "hello")))
(let ((i 5))
  (repeat 3 (lambda () (print i))))

The first call to repeat prints hello three times as expected. The second call to repeat does not print 5 three times, it prints 1 then 2 then 3, because the variable i from the macro shadows the variable i from the context of the macro call.

Scheme

Scheme is similar to Lisp, but with a few differences. One of the differences is that Scheme macros are hygienic. The Scheme equivalent of the program above prints hello three times then 5 three times.

(define-syntax repeat
  (syntax-rules ()
    ((repeat count func)
     (do ((i 1 (+ 1 i)))
         ((> i count))
       (func)))))
(repeat 3 (lambda () (display "hello") (newline)))
(let ((i 5))
  (repeat 3 (lambda () (display i) (newline))))

TeX

TeX expands macros in its mouth but defines them in its stomach. But don't set too much store by this: from a language design perspective, TeX is weird.


Is Pattern Matching as expressive as Case Expression in Haskell?

The expression

case e of
  p1 -> e1
  p2 -> e2
  ...

can be rewritten as

let k p1 = e1
    k p2 = e2
    ...
 in k e

where k is a fresh identifier.

This translation assumes that the language has some way to define a local function by pattern matching (e.g. let).

If local functions can not be defined, there's always the possibility of lifting the definition to the top level. Indeed, any local definition

let f x1 ... xk = e in e'

having free variables v1 .. vn can be rewritten written as

(\f -> e') (globalF v1 ... vn)

provided that we also define a global function

globalF v1 ... vn x1 ... xk = e

Note that globalF has no free variables, by construction. I believe it is sometimes called a "supercombinator".

This naturally extends to the case where x1 ... xk are patterns, and we have multiple defining equations for f / globalF.

For example,

case x of True  -> False
          False -> True

cab be rewritten as

let f True  = False
    f False = True
 in f x


Search string excluding longer string containing substring that contains string, not exclusively longer string

Finite automata to the rescue!

Let

$\mathcal{A} = \Sigma^* \cdot \{A\} \cdot \Sigma^*$ and
$\mathcal{B} = \Sigma^* \cdot \{B\} \cdot \Sigma^*$

be the regular languages that contain all strings with substring $A$ resp. $B$.

Note then that

$\qquad\displaystyle L = \overline{\mathcal{B}} \cdot \{A\} \cdot \overline{\mathcal{B}}
\ \cup\
\mathcal{A} \cdot \mathcal{B}
\ \cup\
\mathcal{B} \cdot \mathcal{A}$

is the set of all strings you are looking for, and from basic closure properties of REG we know that it is regular as well.

Constructing a (minimal) DFA from the above description using standard constructions yields an effective method that may or may not be efficient.


Representation of the concatenation at the type level

A major idea of concatenative languages is that the syntax and semantic domain form monoids and the semantics is a monoid homomorphism. The syntax is the free monoid generated by the basic operations, better known as a list. It's operation is list concatenation, i.e. (++) in Haskell. In the untyped context, the semantic domain is just the monoid of endofunctions (on stacks) with composition as the operation. In other words, an interpreter should look like the following:

data Op = PushInt Int| Call Name | Quote Code | Add | ... -- etc.
type Code = [Op]

-- Run-time values
data Value = Q (Endo Stack) | I Int | ... -- etc.
type Stack = [Value]

-- You'd probably add an environment of type Map Name (Endo Stack)
interpretOp :: Op -> Endo Stack
interpretOp (PushInt n) = Endo (I n:)
interpretOp (Quote c) = Endo (Q (interpetCode c):)
interpretOp op = ... -- etc.

interpretCode :: Code -> Endo Stack
interpretCode = foldMap interpretOp

runCode :: Code -> Stack
runCode code = case interpretCode code of Endo f -> f []

Making a (very naive) compiler is just as simple. The only thing that changes is the target monoid which will now be a syntactic monoid built out of a fragment of the syntax of the target language thus interpretOp will become compileOp. This target monoid may be sequences of statements with the operation of sequential composition, i.e. ;. You can be quite a lot more sophisticated though.

Type systems for concatenative languages are not as obvious, and there are almost no typed concatenative languages. Cat is the most significant example I'm aware of. One way to start to approach it and experience some of the issues that come up is to embed a concatenative language in Haskell. You quickly discover that you don't want add :: (Int, Int) -> Int as this won't compose. Instead, you have add :: (Int, (Int, s)) -> (Int, s). This works extremely well for simple things. This is also relatively clearly poor man's row types. One of the first and most significant hurdles you'll hit is dealing with quotations. The problem is that [add] should correspond to something with a type like s -> ((forall s'. (Int, (Int, s')) -> (Int, s')), s) which requires higher-rank types and impredicative instantiation. Cat appears to have both. It certainly has higher ranked types, and it will substitute a polytype for a type variable. It may be doing things in a way that can be understood without impredicativity. Accomplishing this with an embedding in Haskell might be doable using type-level lists, (closed) type families, and local universal quantification. At this point though, making a custom type system likely makes more sense.

Operations with non-uniform stack effects are also likely to be problematic, but, in most cases, it makes sense to just omit them and provide alternative means of doing things that guarantee a consistent stack.


Let's consider the following grammar:

  1: $S \to A b$
  2: $S \to B b$
  3: $A \to a a$
  4: $B \to a a a$

Obviously, this language is totally uninteresting: the only words in it are $aab$ and $aaab$. However, the grammar is not $LL(1)$ or $LL(2)$ (not sure if you know what that is, if you don't, then that's not a problem).

Let's try parsing the input $aaab$ by going through it one character at a time, while pretending we know absolutely nothing about the rest of the string, except the next token (essentially, we use 1 token of lookahead). We are allowed to use our knowledge of everything we've seen so far though.

Initially, we only know that the string starts with an $a$. This tells us absolutely nothing about whether we are in 'case 1' (production 1) or 'case 2' (production 2) of our grammar. Luckily, we don't really care at this point.

Let's skip over the $a$ and go to the next point. We remember the $a$ and look at the next token. This is another $a$. Note that by now, we've seen $aa$, which means that we might be in case 1: it might be the case that these first two $a$s constitute an instance of $A$! We'll just leave it at this for the moment, and first 'read' the $a$ officially.

We now look at our third token and find it is again an $a$. We now want to decide whether those two $a$s we saw earlier really constitute an $A$ ($LR(k)$ algorithms never delay this decision). As an $A$ is always followed by a $b$, we decide this is not the case: our next token is an $a$.

Reading the $a$, we know we're definitely in case 1 (assuming our input is correct). Our lookahead becomes a $b$, which is precisely what we expect. We therefore decide that the three $a$s we've seen so far are in fact a $B$. Note that at this point, we no longer need to 'remember' that we've seen three $a$s: all we need to know is that we've seen a $B$. This is effectively the same situation we'd be in if we would have had $Bb$ as input, and we'd have read $B$, and as this makes everything easier to remember, we'll do precisely that (this corresponds to a reduce action of an $LR(k)$ parser).

Finishing up, we read the $b$, find that we are at the end of the input, decide that the left part must be an $S$ and decide that the input was correct.

The $LR(k)$ algorithm works pretty much as described above. It remembers what it has seen so far and decides based on this information and the next token whether the last bit of what it has seen so far is 'actually' a nonterminal. It then replaces this by the nonterminal, shuffles some information around and continues as if the replacement had taken place in the input.

The crucial bit is finding out when what we've seen so far, or to be more precise the last bit of what we've seen so far, is actually an instance of a nonterminal, so an expansion of a production. In our example, if we had transformed the two $a$s at the start into an $A$, then everything would have went wrong. We say that $aa$ is not a handle at this point. However, $aaa$ was a handle, as we correctly replaced it by a $B$. A grammar is $LR(k)$ if we can always make correct decisions about what is a handle using $k$ tokens of lookahead and everything we've seen so far.


Integer Knapsack Problem - No duplicates Allowed

You are right about "independence" between subproblems. Therefore, you use the new subproblems (wiki) by introducing another variable $i$, meaning using the items up to $i$:

  Define $V[i,s]$ to be the maximum value ($V$) that can be attained with size less than or equal to $s$ using items up to $i$ (the first $i$ items).


Context-free Languages closed under Reversal

Your sources are right, and I am afraid there is only little to add, except formalism. I denote the reverse (mirror) of string $w$ by $w^R$.

If $G$ is a grammar, let $H$ be its reversed, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.

Then by induction we show that $A\Rightarrow_G^*w$ iff $A\Rightarrow_H^*w^R$.

(basis) In zero steps we have  $A\Rightarrow_G^0 A$ iff $A\Rightarrow_H^0 A$.
(induction) Assuming
$A\Rightarrow_G^*w_1Bw_2$ iff $A\Rightarrow_H^*w_2^RBw_1^R$ we can apply any production $B\to u$ in $G$ (and in $H$ in reverse) and obtain $A\Rightarrow_G^*w_1uw_2$ and $A\Rightarrow_H^*w_2^Ru^Rw_1^R$ respectively, where indeed $w_2^Ru^Rw_1^R$ is the reverse of $w_1uw_2$.

This is a very condensed proof, but contains all necessary ingredients. Again, a derivation of the reverse grammar is the reverse of the original one. This is especially clear when looking at the two derivation trees.


Difference Between Residual Neural Net and Recurrent Neural Net?

The answer is YES, they basically are the same according to this paper

The figure above shows how they compared both and how a ResNet can be reformulated into a recurrent form tat is almost identical to a RNN.
For more info you can read the paper and get deeper.


Yes the language is regular.

Productions 2 and 3 are like transitions in a finite state automaton: $B \to aC$ is like moving from state $B$ to state $C$ while reading $a$; $B\to \varepsilon$ indicates that $B$ is like a final state where we can stop the computation (i.e., end the dirivation in grammar terminology).

The production $A\to B$ is like an $\varepsilon$-transition in finite state automata. This may be practical, but does not change the language generating capabilities of the grammars.


Choosing heuristic for A* algorithm where cost is less than absolute distance

The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path.

The more complicated option is to look at the graph and estimate the chance that you will end up going through the low cost area. This requires some precalculation of the low cost areas and their influence on paths.

For example a low cost highway, any heuristic that is close to it will need to get a bonus to account for taking the highway. But heuristics that are not going to take the highway can use the larger estimation.


How to solve this recurrence using recursion tree method

Break it up into parts you can handle.

$\max\,\{\sqrt{n},2\} = \sqrt{n}$ if, and only if, $n>3$, so rewrite the recurrence as

$$\begin{align*}
T(n) &= T(\lceil\sqrt{n}\,\rceil) + n && \text{for } n>3\\
T(n) &= T(\lceil n/2\rceil) + n &&\text{for } n\leq 3\,.
\end{align*}$$

At that point, I think it's reasonable to solve the $n\leq 3$ part by direct substitution and then use required method for the $n>3$ case.

By the way, you also need a case for $T(1)$, since the general equation gives $T(1) = T(\lceil\tfrac12\rceil)+1 = T(1)+1$, which is impossible.


$L$ is decidable. Prove that "similar" language is also decidable

Let's consider for simplicity the language
$$
L'' = \{ w : \text{there exists $u \in L$ such that $u,w$ disagree on all positions} \}
$$
instead of your more complicated one.

Consider the language
$$
L = \{ 0^n10^m : \text{the $n$th Turing machine halts on the empty input after exactly $m$ steps} \},
$$
which is computable. You can check that $1^n0 \in L''$ iff the $n$th Turing machine halts, hence $L''$ is not computable.

In order to answer your original question, just repeat each bit 3 times.


There is a similar problem, where you're looking for pairs with a given sum $S$.

For that problem, you initialize an empty set and then iterate once through your numbers. For each number $x$ you do:

Check, if the number $S-x$ is in the set. If it is, you can form the pair $(x,S-x)$.
Add $x$ to the set.

If its allowed to use a number twice, you would only have to switch step (1) and (2).

To check for ranges instead of exact sums you would have to adapt your data structure. You would exchange the set with a range tree and do the following:

Query your range tree for the range $(low-x,high-x)$ (where low and high are 20 and 27 in your example). This query will return a set $P$ of numbers and you can form a pair  $(x,p) \forall p \in P$.
Add $x$ to the range tree.

Obviously, this approach only works for pairs. If you want to get all tuples with 4 elements you could first generate all distinct pairs and then try to combine them with the approach I've outlined above. This would result in an $\mathcal O (n^2 \log n)^*$ algorithm (same for tuples with 3 elements, though you would add the pair-sums to the DS and query with the elements from your initial array and not with other pair-sums).

*: This runtime is only correct if the size of tuples in a range is bounded with $\mathcal O(1)$. The worst case without this assumption is of course $\mathcal (N^4)$, when e.g. you have $N$ positive numbers and your allowed range is from $0$ to $\infty$ (result = all possible 4-tuples, without constraints).

PS: I think it's highly likely, that there cannot be a better algorithm, as this problem is an adaptation of 3SUM.


Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p

Suppose $p=\sum\limits_{n=1}^\infty \frac{1}{2^n}p_n$, where $p_n\in\{0,1\}$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i \neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^{-(k-1)}\frac{p_k}{2}$, thus the probability of generating heads is $\sum\limits_{k=1}^{\infty}2^{-k}p_k =p$. The expected number of iterations is $2$.

Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.