The shortest path may indeed change. This is not because of some property of the uniform cost search, but rather, the property of the graph itself. Note that adding a constant positive cost to each edge affects more severely the paths with more edges. Here is an example, where the shortest path has cost $5$:

Adding a cost of $1$ to each edge changes the shortest path in the graph as:

The original shortest path has a new cost of $10$, whereas the other path has a cost of only $9$. Therefore, any optimal shortest path algorithm, such as Dijkstra's or uniform cost search, will find a different shortest path.

The shortest path will not change if it also has the least number of paths among all paths from source to destination. If the shortest distance is $d_{min}$ and $k_1$ edges, and there is some other path with distance $d_{min} + \Delta$ with $k_2$ edges ($k_2 < k_1$), it can be shown that adding any $c > \frac{\Delta}{k_1 - k_2}$ to all the edges will change the shortest path, and therefore your result.

Scaling the edges by a constant positive factor (multiplying all edges by $c>0$) will not change the shortest path.


Usage of stacks and heaps in object-oriented programming. Reasons?

I am not sure if choosing stacks/heap is related with object oriented programming. The stacks are adopted by many programming languages because they are perfect fit for scoped variables, e.g. create new stack frame at the beginning of a function, and discard it when leaving. They don't always store reference variables, but actual objects. In C++, you can allocate objects on stack and they will be destroyed when the control exits the scope.
While stacks are often used with scopes, which determines the variables lifetime, heaps are used for objects that live longer without predefined lifetime.


Tips for creating “Context Free Grammar”

Mmmm.

Let me note that in fact $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$ equals $\{ v  \mid v \in \{a,b\}^*\wedge|v| \text{ is even } \}$.

Al strings in $L$ are of even length, and conversely all strings of even length can be otained by taking $w=\varepsilon$.

That should help.


Finding C-convex holes in a planar point set

In "Counting Convex Polygons in Planar Point Sets" (link) Mitchell et al. show an algorithm which can do this in time $O(cn^3)$.

Note however that if you need to report those polygons then you can't do better than $O(n^c)$ as there might be $\Omega(n^c)$ such polygons to begin with (consider for example $n$ points in convex position).


Number of circuits with at most $m$ logic gates

I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly.

You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves $16(m+n)^2$ possibilities for the type of each gate. Since there are $m$ gates, at first glance there should be $(16(m+n)^2)^m$ different circuits we could construct from these gates.

However, we should also specifically select for the output gate, so we multiply the number of circuits by $m$ to account for this choice: thus we have a bound of $m\cdot(16(m+n)^2)^m$ different possible circuits of size $m$.

The crucial step that you are missing is that the labels we assigned to each of our gates were arbitrary, and thus we can divide our bound by $m!$ to compensate for our overcounting.

We thus have a tighter bound of
$$\frac{m \cdot (16 (m+n)^2)^m}{m!}$$ for the number of circuits of size $m$.

If we assume $m = (1-\epsilon)\frac{2^n}{n}$, for any $\epsilon>0$, one can (and Katz does) show that this is less than $2^{2^n}$.


If the decision problem can be solved in poly time, show the optimization problem also can

In the decision problem, $k$ is given, so the answer is yes, or no (a decision). In the optimization problem $k$ is unknown, and we have to find out how small can it be (the optimal solution). The bigger question asks if there is a logical connection between possible solutions to these two problems, such that the complexity of the respective algorithms is corelated.


How to approach DFA construction with substring constraints?

Use the state of the automaton to "remember" enough information about the string that you've seen so far to allow you to determine whether the string you've read is in the language. This is true essentially independently of the language you're trying to recognize.


Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

If edge weights are integers in $\{0,1,\ldots,K\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation.

At any time, the (finite) keys in the priority queue are in some range $\{D,D+1,\ldots,D+K\}$, where $D$ is the value of the last key removed from the priority queue. (Every key is at least $D$, because the sequence of keys removed by Dijkstra's algorithm is non-decreasing, and every key is at most $D+K$, because every key has value $d[u] + wt(u,w)$ for some edge $(u,w)$ where $d[u]$ is the distance from the source to some vertex $u$ that has already been removed, so $d[u]\le D$.)

Because of this, you can implement the priority queue with a circular array $A[0..K]$ of size $K+1$, with each cell containing a bucket.  Store each vertex with key $k$ in the bucket in cell $A[h(k)]$ where $h(k)=k \bmod (K+1)$. Keep track of $D$.  Do operations as follows:

delete-min: While $A[h(D)]$ is empty, increment $D$.  Then delete and return a vertex from $A[h(D)]$.
insert with key $k$: Add the vertex to the bucket of $A[h(k)]$.
decrease-key $k$ to $k'$: Move the vertex from $A[h(k)]$ to $A[h(k')]$.

Insert and decrease-key are constant-time operations, so the total time spent in those operations will be $O(|V|+|E|)$.  The total time spent in delete-min will be $O(|V|)$ plus the final value of $D$.  The final value of $D$ is the maximum (finite) distance from the source to any vertex (because a delete-min that takes $i$ iterations increases $D$ by $i$). The maximum distance is at most $K(|V|-1)$ because each path has at most $|V|-1$ edges.  Thus, the total time spent by the algorithm is $O(K|V|+|E|)$.


In this reduction of $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ to $L$, what matters in the construction of the Turing machine $M_1$ is  that the language accepted by
$M_1$ is $\{01\}$ iff $M$ accepts $w$, and is $\emptyset$
otherwise.

Whether $M$ does not halt on input $w$, or halts rejecting it, does not make any difference. In both cases, the language accepted by $M_1$ is  $\emptyset$, thus satisfyiing the definition for $L$. Hence $M_L$ will accept $\langle
M_1 \rangle$, so that $M_{ATM}$ will reject.


Here is a counterexample.
There are 6 drugs with intervals $$[1, 5],\ [2,8],\ [3,8]$$
and $$[6, 11], \ [6,12],\ [9, 13].$$
We can use containers of volume 4 to cover the first 3 drugs and containers of volume 10 to cover the last 3 drugs. So it is enough to use 2 kinds of containers.
If we use the greedy algorithm, we would first cover $$[2,8],\ [3,8],\ [6, 11], \ [6,12]$$
using, for example, containers of volume 7. And then the remaining two intervals $$[1,5],\ [9,13]$$
that are disjoint will need additional two containers of different volumes to cover.


Does the SIFT feature be calculated in the original image or the corresponding octave(s)?

The orientation of a keypoint should be computed on the original image, smoothed accordingly to the scale of that keypoint. Luckily we already have the Gaussian pyramid at our disposal, so we can simply select the closest level of this pyramid and compute the orientation there. In other words, if you detect a keypoint in the 3rd octave, then you compute its orientation in the 3rd octave of the Gaussian pyramid.
And the same for descriptors.


Numerical division of arbitrary numbers is $O(k^2)$, but division by 2 is a special case that is always $O(k)$, and a % 2 is $O(1)$, since it only requires examining a single bit. Since the loop requires $O(k)$ iterations, that makes the whole computation $O(k^2)$ in terms of bit operations.

In practice, however, you'd either

have a stored in a shift register to begin with, which means that the division (shift) operation is $O(1)$, making the overall implementation $O(k)$.
use a pointer to find the first nonzero bit of a (which takes $O(k)$) and then copy the bits to the result just once (which is also $O(k)$), making the overall implementation $O(k)$


Clock page replacement algorithm - Already existing pages


Difference between Turing machine and Universal Turing machine

A universal Turing machine is just a Turing machine whose programming simulates other Turing machines.  That is, the input to the UTM is a description of a Turing machine $T$ and an input for $T$, and the UTM simulates $T$ on that input.

It's universal in the sense that, for any problem that can be solved by Turing machines, you could either use a Turing machine that directly solves that problem, or you could use a UTM and give it the description of a TM that directly solves the problem.

If you like, a UTM is an interpreter for (all) Turing machines.


If set membership problem can be solved for a particular language does this imply that the language is regular?

Since any irregular, but decidable language answers the question with "no, there are irregular languages that are decidable", maybe some nuance for how this relates to the usual complexity classes.

For one thing, every regular language has at most linear time complexity (just use a DFA that recognizes the language and run the word on it and check whether you end up in an accepting state). Therefore, the deterministic time hierarchy theorem implies that there are languages that are decidable, but irregular, since it implies that the set of languages that, say, require at least quadratic but at most cubic time is nonempty; similarly for languages that require $\Theta(2^{2^{2^n}})$ time. On the other hand, there are irregular languages that have linear time complexity, as illustrated by the example $\{a^nb^n : n \in \mathbb{N}\}$ that David gave.

Another surprising thing I became aware of only recently is that SAT, the NP-complete problem of deciding whether a CNF formula is satisfiable, is context-sensitive. To see this, remember that the automata recognizing context-sensitive languages are the linear bounded automata, which are nondeterministic Turing machines that are only allowed to use the space used for the input (or alternatively, only use linearly much additional space - using a speedup theorem, those definitions should be equivalent); here are references on the matter.

And finally, a restricted version of the question ("does NP-completeness imply regularity?") can be answered by "no, there are irregular languages that are NP-complete". If P=NP, then all irregular languages that can be decided in polytime are NP-complete (since the reduction has all the power required for deciding any NP-problem, and so reductions always work), and if P$\neq$NP, then all NP-complete languages are irregular: if they weren't, then there would be a regular language that is NP-complete, but regular languages can be decided in linear time, contradicting P$\neq$NP.

So to sum up: decidability doesn't tell you much about where in the complexity zoo we are, and even knowing a language can be solved in linear time doesn't tell you anything about regularity. On the other hand, irregularity doesn't tell you much about time complexity either (maybe that implies that the language requires at least linear time - but I can't prove that off the cuff, not sure it's true!).


What is the difference between user-level threads and kernel-level threads?

One of the roles of a multitasking operating system kernel is scheduling: determining which thread of execution to execute when. So such a kernel has some notion of thread or process. A thread is a sequential piece of code that is executing, and has its own stack and sometimes other data. In an operating system context, people usually use process to mean a thread that has its own memory space, and thread to mean a thread that shares its memory space with other threads. A process can have one or more threads.

Some operating systems, for example older unix systems, only provide processes: every thread that the kernel manages has its own memory space. Other operating systems, for example most modern unix systems, allow processes to contain multiple threads of execution: they provide a kernel-level notion of threads.

It's also possible for a process to manage its own threading. In cooperative multithreading, the code of each thread contains instructions to switch to another thread. In preemptive multithreading, the process requests periodic asynchronous notifications from the kernel, and reacts to these notifications by switching to a different thread. This way, multithreading is implemented with no kernel cooperation, at the user level, in a library.

A system can offer both kernel-level and user-level threads; this is known as hybrid threading.

User- and kernel-level threads each have their benefits and downsides. Switching between user-level threads is often faster, because it doesn't require resetting memory protections to switch to the in-kernel scheduler and again to switch back to the process. This mostly matters for massively concurrent systems that use a large number of very short-lived threads, such as some high-level languages (Erlang in particular) and their green threads. User-level threads require less kernel support, which can make the kernel simpler. Kernel-level threads allow a thread to run while another thread in the same process is blocked in a system call; processes with user-level threads must take care not to make blocking system calls, as these block all the threads of the process. Kernel-level threads can run simultaneously on multiprocessor machines, which purely user-level threads cannot achieve.


How do I prove that Context Free languages have more memory than FSM

There's a small mistake in your question.

The FSM (DFA or NFA) are machines that accept regular languages.

the CFL is also a language.

They are accepted by a machine called PDA (PushDown Automata) which you can think of as a generalization of the a DFA/NFA.

A PDA is like a NFA but in addition, it also has a stack. So it can accept (context free) languages like $L = \{0^p1^p | p \geq 0\}$

Its fairly easy to show that the PDA is more powerful than DFA.. (see it accepts $L$ that the DFA cannot)

We will show something stronger, i.e. formally define the construction of the PDA that will show that any language accepted by some DFA is also accepted by some PDA .

a PDA is 6 tuple $(Q, \Sigma, \Gamma, \delta, q_0, F )$, where,

$Q$ is the set of states
$\Sigma$ is the input alphabet,
$\Gamma$ is the stack alphabet,
$\delta$ is the transition func. $\delta:(Q \times \Sigma_\epsilon \times \Gamma_\epsilon) \rightarrow \mathcal{P}(Q\times \Gamma_\epsilon)$ ,
$q_0 \in Q$,
$F \subseteq Q$

now observe that a DFA/NFA is just the same thing where $\Gamma$ is always 'empty'.


Given a prime power, is it possible to efficiently compute the prime

Yes, here is a simple approach (there are likely more efficient ones).

Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the range $\{1, \ldots, \log_2(n)\}$, you can do a binary search for a $p$ in the range $\{2, \ldots, n\}$ such that $p^{i} = n$.


Can a Turing machine determine if a set is accepted by a another Turing machine?

Is the language of all machines that accept $W$ recognizable?

$$L_W = \{\langle M\rangle : L(M) = W\}$$

The answer is unfortunately no, except in trivial cases. If $W$ is unrecognizable, then $L_W$ is empty (no machine recognizes $W$) and hence decidable (The machine that rejects all inputs decides $L_W$).  In all other cases, $L_W$ is unrecognizable. We can show this using reductions from the unrecognizable rejection problem— the problem of determining whether a machine rejects a word.

If $W=\Sigma^*$, the set of all strings, then $L_W$ is unrecognizable (a standard result: "$M_x(w)$ simulates $M$ on $x$ for $|w|$ steps and accepts if the simulation doesn't accept by then." provides a reduction from the problem of deciding whether $M$ rejects $x$).
If $W\neq \Sigma^*$ is decidable, then $L_W$ is unrecognizable. Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine decides whether $w\in W$ and accepts if so. Otherwise, it simulates $N$ on $x$ and does what it does. The machine $N_x$ therefore accepts $W$ (if $N$ rejects $x$) or all strings (if $N$ accepts $x$).

If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.
If $W$ is recognizable but undecidable, then $L_W$ is unrecognizable:  Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine simulates $N$ on $x$ for $|w|$ steps. If the simulation accepts in that time, the machine accepts. Otherwise, the machine tests whether $w\in W$ and does what it does.

Hence $N_x$ accepts the union of $W$ and the set of all strings longer than the number of steps it takes for $N$ to accept $x$. If $N$ rejects $x$, $N_x$ recognizes $W$. If $N$ accepts $x$, $N_x$ recognizes additional words. (Note that because $W$ is undecidable, there must be arbitrarily long strings not in $W$. Otherwise, a DFA could decide $W$ by memorizing the short strings and using a length requirement for the long ones. Hence $N_x$ recognizes a strict superset of $W$ if $N$ accepts $x$.)

If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.


I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free

Sketch of an answer:

As you suggested, use the states of the PDA to check when a $11$ or a $010$ has been found. Then, instead of keeping track of the number of $11$s and $010$s separately, keep track of the difference in their numbers.

You could have some symbol in the stack initially, say, $\$$, to mark that the stack is empty. Then, use a symbol $x$ to denote $+1$ in the difference, and $y$ to denote $-1$ in the difference.

Whenever a $11$ is encountered, and the top of the stack is not a $y$, push an $x$. Else, pop a $y$.

When a $010$ is encountered, if the top of the stack is not an $x$, push a $y$. Else, pop an $x$.

Thus, at any given point, the stack consists entirely of $x$s or entirely of $y$s, or only the $\$$. The number of $x$s denotes how many more $11$s have been encountered as compared to the number of $010$s, and vice-versa.

At the end of the input, accept if the top symbol is an $x$, as this would mean that the number of $11$s were more than the number of $010$s.


How can a fully encrypted homomorphic program resist copying?

Homomorphic program encryption, assuming you want it fully operational, is not possible. At some point of time actual operations are executed (directly or in obfuscated form).
Encryption of any kind does not prevent copying, because with physical access to hard drive you can make verbatim copy at any moment.
There is also a huge slowdown with program obfuscation (like in Gentry's garbled scheme)/communication that drastically reduces realistic use.


What is a disequality path in the context of equality graphs?

Suppose we have a bunch of variables $v_i$ and a bunch of equations $v_i = v_j$ and disequalities $v_i \neq v_j$. We can describe out knowledge as a graph whose vertices are the variables and whose edges are the equations (equality edges) and disequalities (disequality edges).
An equality path is a proof that $v_i = v_j$. Such a proof consists of a path from $v_i$ to $v_j$ using only equality edges. A disequality path is a proof that $v_i \neq v_j$. Such a proof consists of a path from $v_i$ to $v_j$ in which exactly one edge is a disequality edge.
When the domain of the variables is larger than 2, then equality paths are the only way to deduce equality from the givens, and disequality paths are the only way to deduce disequality from the givens. This is a nice exercise. In the binary case, however, a path with an even number of disequality edges is a proof of equality, and a path with an odd number of disequality edges is a proof of disequality.


What is a good method for modelling combinatorial tree (sport competition results)?

I can't follow how you get 30 combinations, you have 2 matches per journey each of the 2 matches can result in 5 different attributions, so you get 5*5 = 25 different attribution per match. At each journey there are 3 possibilities to make 2 matches. So the result would be 25/3 + 25/3 + 25/3 = 25 different point attributions.
Did I got something wrong?

You want to calculate how many different point attributions there are after n journeys and the probabilities to make a match are the same for every combination at every journey?


They actually start by proving that $[[E(\varphi U\psi)]]=\bigcup\limits_{k\ge 1}G^k(\emptyset)$.

You can see (or prove by induction for the general case) that repeated applications of $G$ starting with the empty set yields:

$G(\emptyset)=[[\psi]]$,

$G^2(\emptyset)=[[\psi]]\cup ([[\varphi]]\cap pre_\exists([[\psi]]))=[[\psi]]\cup\left\{s\in S | s\in[[\varphi]] \land \exists s' \left(s\rightarrow s' \land s'\in[[\psi]]\right)\right\}$

$\vdots$

$G^{i+1}(\emptyset)=G^i(\emptyset)\cup \left\{s\in S| s\in[[\varphi]]\land\exists s' \left( s\rightarrow s'\land s'\in G^i(\emptyset)\right)\right\}$

The union of the above sets exactly coincides with the definition of $[[E(\varphi U \psi)]]$. To conclude the proof, they use the fact that $G$ is montone and that $G^{n+1}(\emptyset)$ is a fixed point of $G$, thus $\bigcup\limits_{k\ge 1}G^k(\emptyset)=G^{n+1}(\emptyset)$, which is the least fixed point of $G$.


Applications of Depth-First Spanning Tree

You can find bridges, i.e. edges whose removal causes the graph to separate into disconnected components.

Assuming connected, undirected graphs, the key insight is that a tree edge $e = (v,w)$ ($v$ being the father of $w$ in the tree) is a bridge if and only if there is no backwards edge¹ connecting $w$ or a successor of $w$ with an ancestor of $w$ (in the search tree). If there were such an edge, $e$ could not be a bridge as it's part of a cycle.

By augmenting the depth-first search algorithm in a suitable way, we can do these checks along the road and thus get an $O(n + m)$ algorithm.

There can be no forward and cross edges!


Can someone clarify landau symbols definition please?

In the case of $O(f(n))$ and $\Omega(f(n))$ you are correct in that they can be wildly inaccurate and still be correct, for instance, $n$ is $O(2^n)$ - this just does not provide good information.

For $\Theta$ yes you can drop the lower orders of magnitude. What "$f(n)$ is $\Theta(g(n))$" means is that there are two constants, $C_1$ and $C_2$, and two values $n_1$, $n_2$ such that $C_1g(n)>f(n)$ for all $n$ greater then $n_1$, and likewise $C_2g(n)Nf(n)$ for all $n$ greater then $n_2$. In your case we can see that multiplying $n^2$ even by 2 will dwarf the remaining values of $f(n)$ for sufficiently large $n$, likewise multiplying by 1 will make it always smaller.

Little $o$ and $\omega$ notation is used to describe a function as being orders of magnitude less then another. When we were in big $o$ notation, as long as one constant $C$ existed such that $Cg(n)>f(n)$ then $f(n)$ is $O(g(n))$, with little $o$, every possible $c$ must cause this to happen. The easiest way to find this is to take the limit of $\lim_{x \to \infty} \frac{f(n)}{g(n)}$: if it is zero then $f(n)$ is $o(g(n))$; if it is $\infty$ then $f(n)$ is $\omega(g(n))$


Does $\#W$[1]-hardness imply approximation hardness?

$\mathrm{W}[1]$-hardness implies that a problem has no eptas unless (at least) $\mathrm{W}[1] = \mathrm{FPT}$ (having an eptas implies parameterized tractability for the standard solution size parameterization), but there are problems with a ptas that are $\mathrm{W}[1]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$).

Transferring this to $\#\mathrm{W}[1]$-hardness, you can at least say that a $\#\mathrm{W}[1]$-hard problem still has no eptas, but I don't think a stronger statement can be made a priori. Turning to speculation, I suspect it's also not true that $\mathrm{APX}$-hardness immediately follows from $\#\mathrm{W}[1]$-hardness in general, though perhaps something may be said for higher classes, such as the counting version of $\mathrm{para}\text{-}\mathrm{NP}$.


Is the SK2 calculus a complete basis, where K2 is the flipped K combinator?

Consider the terms of the $S,K_2,I$ calculus as trees (with binary nodes representing applications, and $S, K_2$ leaves representing the combinators.

For example, the term $S(SS)K_2$ would be represented by the tree

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

To each tree $T$ associate its rightmost leaf, the one you get by taking the right branch at each @. For example, the rightmost leaf of the tree above is $K_2$.

As can be seen from the ASCII art below, all reduction rules in the $S, K_2, I$ calculus preserve the rightmost leaf.

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f
  / \
 /   \
S     e

      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

From there on, it's easy to see that if some term $T$ reduces to $T'$, then $T$ and $T'$ have the same rightmost leaf. Hence, there is no term $T$ in the $S, K_2, I$ calculus such that $TK_2S$ reduces to $K_2$. However, $KK_2S$ reduces to $K_2$, hence $K$ cannot be expressed in the $S,K_2, I$ calculus.


Is there a solution set for Knuth's The Art of Computer Programming series?

The books contain worked solutions to some exercises and hints to some others. Others are open questions: this is indicated by their difficulty rating, and you shouldn't expect to find worked solutions to them except maybe, for a few, as papers in journals.


Compute lebesgue measure of set of intervals

You can solve this in $O(n \log n)$ time.  Here is an algorithm.  Sort the intervals by their left endpoint ($x$-value), in increasing value.  At each stage, if the first interval is disjoint from the second interval, remove the first interval and add its width to the running total so far.  If they're not disjoint, replace the first two intervals by their union.


Pi approximation with Montecarlo: Why not just evenly distributed points?

Let us compare the efficiency of both methods. The first method generates random points on the unit square $[-1,1]^2$, and checks how many of them lie inside the unit circle – the fraction should be $\pi/4$. If we sample $N$ points, our estimate has roughly normal distribution with mean $\pi/4$ and variance $\pi/4(1-\pi/4)/N$, and so we expect an error of order $1/\sqrt{N}$.

The second method generates an $M \times M$ grid inside $[-1,1]^2$ (we can take $M = \sqrt{N}$ for later comparison), and checks how many of the $M^2$ points lie inside the unit circle. If we think of each point as standing in for a grid square, then we can estimate the number of problematic squares (those intersecting the circle) as $\Theta(M)$ out of the $M^2$, leading to an overall error of order $1/M = 1/\sqrt{N}$, just as before.

We can speed up the second method, however: for a given value of $x$, we can use binary search to locate the $y$ coordinates at which the circle crosses the grid. This gives an $O(M\log M)$ algorithm, an almost quadratic speedup over the two algorithms mentioned above. This is very similar to evaluating the integral $2\int_{-1}^1 \sqrt{1-x^2} \, dx$, implementing the square root using a binary search.


Can DFA with output (definition?) match expressiveness of NFA with unique output?

An interesting definition can be found in an old survey article by J. Berstel and J. Sakarovitch

  A plurisubsequential function is a finite union of subsequential functions having pairwise disjoint domains. A subsequential function is a function realized by a gsm equipped with an additional partial output function $\rho$ defined on the states of the gsm. ...1

The finite union with pairwise disjoint domains covers cases like above, where more than one output makes sense, but we know only later which. An reasonable implementation could first scan the input once, determine the relevant subsequential function, and then compute that function by a second scan over the input.

The survey proves that addition of one is a plurisequential functions if the digits of the number are given in low-ending order, but not if the digits are given in big-endian order. So the observation from the question about the reverse direction is correct.

Interesting, J. Berstel also wrote a book which contains an answer to the question whether it is possible to relax the restrictions for DFA with output such that it matches expressiveness of NFA with unique output. From
J. Berstel, Transductions and context-free languages Chapter IV, 5 Bimachines

  Definition A bimachine $\mathfrak B = \langle Q, q_-, P, p_−, \gamma\rangle$ over $A$ and $B$ is composed of two finite sets of states $Q,P$, two initial states $q_− \in Q$, $p_− \in P$, of two partial next state functions $Q \times A \to Q$ and $A \times P \to P$ denoted by dots, and a partial output function $\gamma : Q \times A \times P \to B^∗$.

The output of such a machine is naturally partitioned into as many parts as the input has symbols, some of these parts can be empty. To compute the $i$-th part, $Q$ processes the first $i-1$ input symbols forward, $P$ processes the last $n-i-1$ input symbols backward, and $\gamma$ computes the output from the $i$-th input symbol $a$ and the current states $q$ and $p$ of $Q$ and $P$ as $\gamma(q,a,p)$.

A partial function is rational if and only if it is realized by a bimachine. Bimachines were introduced by Schützenberger in 1961. In 2006, J. Rhodes organized a P vs NP Workshop, and where Pedro V. Silva gave an introduction to bimachines.

A bimachine has only a finite number of states and is deterministic, but in general it needs $O(n)$ forward and backward scans over the input. The plurisubsequential functions (or slight extensions of this idea) are attractive, because they only need two forward scans over the input.

  1 ... If a computation in the gsm ends in some state, then the word associated with that state by the function $\rho$ is concatenated at the end of the output, provided p is defined for this state. Otherwise, it indicates that the computation is unsuccessful, and therefore that the function realized by this transducer is undefined for the given input.


Proof via induction for small-step semantics

The induction should be on the derivation of $t \to^* t'$:

If $t \to t'$ in one step, then we get the desired result by the E-IF rule.
Suppose $t \to^* t'$ because $t \to t'' \to^* t'$. By the E-IF rule we have
$$(\mathtt{if}\;t\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to
    (\mathtt{if}\;t''\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)$$
and by the induction hypothesis
$$(\mathtt{if}\;t''\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to^*
    (\mathtt{if}\;t'\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3).$$
These two together give us the desired
$$(\mathtt{if}\;t\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to^*
    (\mathtt{if}\;t'\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3).$$


directed graph data structure with fast in/out neighbor query

If you care about constant factors, then big-Oh notation is not a useful tool to help you compare or measure possible data structures.  If you want to minimize storage as much as possible, you need to think about the layout of the bits -- and then it would help to know concrete parameters and information, like roughly how big $n$ is, a rough estimate of the average degree (averaged over all vertices), a rough estimate of the largest degree and the distribution of degrees, etc.

For instance, one scheme is to represent the list of out-neighbors using something more efficient than a plain linked list (e.g., a linked list of buckets, where each bucket contains $c$ elements, and where you choose an optimal value of $c$ to minimize expected space usage).  Or, you can pack these lists of out-neighbors and in-neighbors into a single big array, with each vertex having a pointer to the first index in that array where the sequence of out-neighbors or in-neighbors exist.  You can also arrange that each entry needs only $\lceil \lg n \rceil$ bits, where $n$ is the number of vertices.

Another scheme is to use a multi-linked list as Patrick suggests, but with a slight twist.  Instead of storing a pair of vertices $(a,b)$ in each linked-list node, store $a \oplus b$ (the xor of the identifier for vertex $a$ and the identifier for vertex $b$).  This will be present in two linked lists: the out-neighbors of $a$, and the in-neighbors of $b$.  Each linked-list node will have two next pointers.  Notice that, when traversing the list of out-neighbors of $a$, all of the nodes will have $a$ as one of the two vertices, so if the value $x$ is stored in the node, we know it represents an edge to $a \oplus x$ (since $a \oplus (a \oplus b) = b$).  Similarly, when traversing the list of in-neighbors of $b$, the value $x$ in a node represents an edge from the vertex $x \oplus b$.  This doesn't reduce the number of pointers compared to a naive scheme, but it halves the amount of space for storing the data (the vertex identifiers) in each linked-list.

There are many more such bit-packing tricks and considerations that can be tried when you care about constant factors.


Can you insert into sorted list with time O(1)?

Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.


The operation $\operatorname{Inv}(\operatorname{Pol}(\cdot))$ is a closure operation. This means that

$\Gamma \subseteq \operatorname{Inv}(\operatorname{Pol}(\Gamma))$.
$\operatorname{Inv}(\operatorname{Pol}(\Gamma)) = \operatorname{Inv}(\operatorname{Pol}(\operatorname{Inv}(\operatorname{Pol}(\Gamma))))$.

See for example lecture notes of Jin-Yi Cai.


programs compatible with different processors

The intel line of processors (8086, x86) have backwards compatible instruction sets (i.e., unless you tell an x86 otherwise, it will behave like a 8086, and the 8086 instructions (and registers, etc) are just a subset of the x86 ones. Ditto for AMD64 (i.e., x86_64), they are able to run x86 software as is. This for pragmatic compatibility reasons: buying the shiny, new machine with the latest processor, and having it run your extant software in a slow emulator is not a way to make new buyers. So the 80286 could run 8086 software (operating system and all), and so on up. You can install an 32 bit (x86) operating system on x86_64 (64 bits) too.

ARM is a completely different kettle of fish, but also compatible (to an extent) along the line.

Besides, running software on some sort of virtual machine (Java Virtual Machine, .NET, ...) has advantages as the same "binary" runs on more platforms (simplifying the logistics of getting "the right version" to the user), today's processors are so ridiculously overpowered it doesn't make much of a difference for interactive applications. Besides, the Just In Time compilation technology has become the tool of choice, even rivaling native compiled binaries for some uses.


Does Ford-Fulkerson always produce the left-most min-cut

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source.  See this question for a formalization of what is meant by "closest".

A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case.

Based on what I've read, there are output-sensitive algorithms to enumerate all min $(s,t)$-cuts.  After a single maximum flow computation, the running time is $O(n)$ per min-cut that is output.  Details can be found in the following paper:

Jean-Claude Picard, Maurice Queyranne.  On the structure of all minimum cuts in a network and applications.  Combinatorial Optimization II: Mathematical Programming Studies, volume 13, 1980, pp.8--16.
Unfortunately, there does not seem to be a non-paywalled online version of the paper.

(See also here for a related question.)

In contrast, if you want to find all min-cuts of an undirected graph, rather than all min $(s,t)$-cuts, you can use Karger's algorithm to do that efficiently (in polynomial time).


Do closure properties for languages go the other way?

No, it doesn't tell us much. Intuitively, union erases information; it's not normally a reversible operation.

So, for example, the union of a language with its complement is clearly decidable and recognizable, regardless of any category in which the language might or might not belong.


Please explain this formal definition of computation

We are missing some context so I have no idea what point Knuth is trying to make, but here's how to interpret a Turing machine this way. Perhaps it will help you understand what's going on. In general, a good way of getting a grip on a concept is playing with it. In the case of programming paradigms, that means writing a program. In this case, I will show how to write any program.

Suppose the tape of the Turing machine has symbols $\{0,1,\epsilon\}$ (where $\epsilon$ stands for "empty"), and add one more symbol which represents the location of the head $H$. Your states are going to be pairs of the form $(q,\alpha)$, where $q$ is a state of the Turing machine, and $\alpha \in \{0,\ldots,14\}$. We also identify $(F,0)$ with $N$ for any final state.

On (non-empty) input $x$, your starting point will be $(Hx,(s,0))$, where $s$ is the starting state. The difficult part is to encode states. Suppose that at state $q$, upon reading input $x$, you replace it with $a(q,x)$, move in direction $D(q,x) \in \{L,R\}$, and switch to state $\sigma(q,x)$. For the $\theta$s, we have
$$
\begin{align*}
\theta_{q,0} &= 0H0, & \theta_{q,1} &= 0H1, & \theta_{q,2} &= 0H\epsilon, \\
\theta_{q,3} &= 1H0, & \theta_{q,4} &= 1H1, & \theta_{q,5} &= 1H\epsilon, \\
\theta_{q,6} &= \epsilon H0 & \theta_{q,7} &= \epsilon H1, & \theta_{q,8} &= \epsilon H\epsilon, \\
\theta_{q,9} &= H0, & \theta_{q,10} &= H1, & \theta_{q,11} &= H\epsilon, \\
\theta_{q,12} &= 0H, & \theta_{q,13} &= 1H, & \theta_{q,14} &= \epsilon H.
\end{align*}
$$
For the $a$s, we have $a_{q,i} = (q,i+1)$ for $i < 14$, and $a_{q,14} = (q,14)$, though we should never really get that far. For the $b$s, we have
$$
\begin{align*}
&b_{q,0} = b_{q,3} = b_{q,6} = b_{q,9} = (\sigma(q,0),0), \\
&b_{q,1} = b_{q,4} = b_{q,7} = b_{q,10} = (\sigma(q,1),0), \\
&b_{q,2} = b_{q,5} = b_{q,8} = b_{q,11} = b_{q,12} = b_{q,13} = b_{q,14} = (\sigma(q,\epsilon),0).
\end{align*}
$$
Now it remains to determine the $\psi$s. Let $a_0 = a(q,0)$. If $D(q,0) = L$ then
$$
\begin{align*}
\psi_{q,0} &= H0a_0, & \psi_{q,3} &= H1a_0, & \psi_{q,6} &= \psi_{q,9} = H\epsilon a_0.
\end{align*}
$$
If $D(q,0) = R$ then
$$
\begin{align*}
\psi_{q,0} &= 0a_0H, & \psi_{q,3} &= 1a_0H, & \psi_{q,6} &= \epsilon a_0 H, & \psi_{q,9} &= a_0H\epsilon.
\end{align*}
$$
Next, let $a_1 = a(q,1)$. If $D(q,1) = L$ then
$$
\begin{align*}
\psi_{q,1} &= H0a_1, & \psi_{q,4} &= H1a_1, & \psi_{q,7} &= \psi_{q,10} = H\epsilon a_1.
\end{align*}
$$
If $D(q,1) = R$ then
$$
\begin{align*}
\psi_{q,1} &= 0a_1H, & \psi_{q,4} &= 1a_1H, & \psi_{q,7} &= \epsilon a_1 H, & \psi_{q,10} &= a_1 H\epsilon.
\end{align*}
$$
Finally, let $a_\epsilon = a(q,\epsilon)$. If $D(q,\epsilon) = L$ then
$$
\begin{align*}
\psi_{q,2} &= H0a_\epsilon, & \psi_{q,5} &= H1a_\epsilon, & \psi_{q,8} &= \psi_{q,11} = H\epsilon a_\epsilon, \\
\psi_{q,12} &= H0a_\epsilon, & \psi_{q,13} &= H1a_\epsilon, &\psi_{q,14} &= H\epsilon a_\epsilon.
\end{align*}
$$
If $D(q,\epsilon) = R$ then
$$
\begin{align*}
\psi_{q,2} &= 0a_\epsilon H, & \psi_{q,5} &= 1a_\epsilon H, & \psi_{q,8} &= \epsilon a_\epsilon H, & \psi_{q,11} &= a_\epsilon H\epsilon, \\
\psi_{q,12} &= 0a_\epsilon H, & \psi_{q,13} &= 1a_\epsilon H, & \psi_{q,14} &= \epsilon a_\epsilon H.
\end{align*}
$$

Now apply $f$ repeatedly until you get stuck. If you follow the construction, you will see that we have simulated the running of the Turing machine.


Why should leaf nodes in a red-black tree be black?

Take a uncolored leaf node, now you can color it as either red or black. If you colored it as red then you may have chance that your immediate ancestor is also red which is contradicting(according to basic principle). If you color it as black then no problem even though the immediate ancestor is red. And also no change in the number of black nodes from root to leaf paths(i.e every path get +1). This may be the possible reason behind that.


Is it possible to go from code to circuit?

Yes, it is certainly possible.
There are compilers that will compile from code to circuits.  Classic examples would be VHDL or AHDL compilers, but you can certainly do this for any other language, to the extent that you have an upper bound on the running time of the program or that you have an upper bound on the memory use of the program and are willing to have a circuit that contains stateful elements.
In fact, you can walk down to Fry's and buy something that basically has the form you asked for: it's called a computer.  That's more or less what a computer does: it takes code written in a programming language and executes it efficiently, using an optimized circuit.  The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer).  However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits.  The mapping is implemented by a compiler.


What is the difference between decidability and computability?

A function over finite strings is called computable if it can be computed by a program (more formally, a Turing machine).

A set of finite strings is computable if it membership problem in that set (given $x$, is $x \in L$?) can be decided algorithmicaly (more formally using a Turing machine).

They are used for different kind of objects.

The word "computable" can be used for a set. When we say that a set is computable we mean that the set is decidable (which is equivalent to saying that the characteristic function of the set is computable).

It makes no sense to say a function is decidable.


Questions about an answer to a pumping lemma question for CFLs

The essential idea is that pumping lemma tells you about string $uv^lwx^ly$ with $l \geq 0$. That is, you can "pump" to $uwy$, if $l = 0$, that way shortening the initial string.

The answer considers the string $a^n b^{n+1} c^{n+1} d^n$. Removing a single $b$ or inserting a single $a$ would move the string out of the language. Removal and insertion correspond to $l = 0$ and $l = 2$.

The answer only considers $vx$, because $w$ does not matter - it will not be pumped.

If $v$ or $x$ contains any $a$s, double them to get more $a$s then $c$s. If $v$ or $x$ contains any $b$s, remove them to get fewer $b$s than $d$s. $v$ and $x$ will never contain both $a$s and $c$s, because $|vwx| \leq n$. Same is true about the other pair of symbols.


How to understand the storing mechanism used in external merge sort

How do you load that entire list into memory?  You don't.  You have a bit of a misunderstanding about how Merge works, in this setting.

It's tempting to think that Merge should work as follows: load both input lists into memory, in their entirety; merge them; then write the result back out to storage.  But that wouldn't work -- we won't have enough memory to load the entire lists into memory.

Instead, Merge works without loading either input list into memory all at once.  Take a look at the pseudocode for Merge, and you'll see that it only needs to have two list items in memory at a time: one list node from somewhere in the first list, and one from somewhere in the second node.  Merge finds which one of those two items is smaller, outputs it, and then loads the next item from the input list it came from.  You can see that Merge only needs $O(1)$ memory to merge two sorted lists, even if the sorted lists are stored in external storage -- it never needs to load the input lists into memory in their entirety.


Is "sparse subtree" an appropriate term for what I describe in this question?

2021 update: "embedded subtree"
In a discussion elsewhere8, I just encountered a term of interest with its own Wikipedia page: induced subgraph. This was roughly the sort of term I was after when I asked my original question, though it doesn't nail it.
It led me to google for "induced subtree". That has 80 matches and looked more appropriate for what I was after. But it still wasn't right because it disallows ancestor-descendant pairings that aren't parent-child.
That led me to "embedded subtree" in this paper which notes:

[In contrast to "induced subtrees"] Embedded subtrees ... allow not only direct parent-child edges, but also ancestor-descendant edges.

So maybe that's the right term.
On the other hand it still doesn't cover what I'm calling "annotation" -- the key notion that the nodes in the "subtree" are paired up with a subset of nodes in the original tree but are not actually the same nodes.
So due to that technical aspect, and for aesthetic reasons, I currently feel my original answer, which follows, remains as acceptable as it ever was. ;)
AST
This self answer defines the terms and acronyms I've made up to refer to what I asked about.1
The terms I've made up are general definitions of two kinds of tree data structure. I define them more precisely in later sections but in summary they are:

A Sparse Tree aka AST. A sparse subset of a tree.

Annotated Subset Tree aka AST. A sparse tree formed via "annotation".

Why define terms to distinguish the concepts when their acronyms eliminate the distinction? Because the mental modelling utility of eliminating the distinction is what I wanted to emphasize first and foremost, while still defining the distinction to make it clear what's going on behind the scenes.
AST typically refers to Abstract Syntax Tree
One existing typical meaning of AST in the CS world is the specific context I had in mind when I posed my question.2
So now we have not two but three ASTs. In the section Why three ASTs?!? below I'll return to why I'm defining three distinct tree concepts that all share the same acronym.
A Sparse Tree
By A Sparse Tree3 I mean a node of a tree data structure that serves as a root, plus any "well formed"4 potentially sparse subset tree formed of branch and leaf nodes relative to that root.
My example will be A Sparse Tree formed from a parse tree.5
If source code is like this:
foo = bar # Assign bar to identifier foo

And the parse tree is like this:
TOP
  statement                   foo = bar # Assign bar to identifier foo
    assignment                foo = bar
      identifier              foo
      assignment operator     =
      identifier              bar
    end-of-line-comment       # Assign bar to identifier foo

then the following represents two of many possible sparse trees based on that single parse tree:
# A Sparse Tree:
    assignment                foo = bar
      identifier              foo
      identifier              bar

# Another Sparse Tree:
    end-of-line-comment       # Assign bar to identifier foo

Annotated Subset Tree
By Annotated Subset Tree6 I mean A Sparse Tree represented/stored by annotating a subset of the nodes of a tree.
By "annotating" I mean hanging an additional node of data off selected nodes.
Why three ASTs?!?
One abstract use case for sparse trees is forming an Abstract Syntax Tree that consists of annotations of the Parse Tree generated by a parser.
When the distinction between A Sparse Tree, an Annotated Subset Tree, and an Abstract Syntax Tree is moot -- which is most of the time -- just use the acronym AST without worrying about the ambiguity, because, by my definitions, it doesn't matter.7
That's why the terms I've coined share the same acronym: AST -- so they can be understood as theoretically distinct things but, for some parser implementations, the same thing in practice.
Footnotes
1 My question was originally an attempt to find out if there was already an accepted term for what I described, generically in regard to trees, without regard for Abstract Syntax Trees. Then it became documentation of that attempt and the CS exchange community's response:

I'm not sure there is a standard term. Feel free to make up your own.
Just be sure to explain at least once in some detail what the term means.

2 I deliberately didn't state this context for my question because my original goal was to find out if there was a generic CS term about such trees.
3 A google for "sparse tree" suggests a few things, most notably a new christmas tree aesthetic and an aspect of a software feature (Emacs Org mode), as well as some genuinely CSish notions, but I didn't find any matching what I've described in this answer.
4 By "well formed" I mean that each node in the sparse/subset tree contains content from, and/or pointers to, the content of other nodes along branches proceeding in the direction of the tree's leaves from the sparse/subset tree's root node.
5 The word "sparse" is onomatopoeically reminiscent of "parse". This is a "happy mnemonic accident" given that the context for me naming these things is a sparse tree formed from a parse tree. It also reminds me of "A partridge in a pear tree" and I have fantasized that I will one day come up with and publish a worthy pun along those lines.
6 A google for "annotated subset tree" suggests a variety of CSish notions, but I didn't find any matching what I've described in this answer.
7 Of course, the usual use of the term "AST" in a CS context is an Abstract Syntax Tree. The whole point of this SO was to pick abstract terms describing a concrete approach that may be taken by parsers storing an AST. The fact that the terms all initialize to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.
8 A reddit.com/r/ProgrammingLanguages discussion


Yes, this can be solved in polynomial time, for arbitrary $N$.  This is an instance of the assignment problem, for which polynomial-time algorithms are known.

You want to assign a color of glass to each bin, such that each bin gets exactly one color, and each color is assigned to exactly one bin.  The cost of assigning bin $b$ to color $c$ is the number of bottle moves needed to move all bottles of color $c$ that aren't currently in bin $b$, into bin $b$.  Therefore, this is an assignment problem.

(You can compute this cost function more efficiently as follows: the cost of assigning bin $b$ to color $c$ is the number of moves needed to move all bottles that aren't colour $c$ out of bin $b$.  Thanks to @David Richerby for this insight.)

The assignment problem can be solved using standard methods, e.g., the Hungarian algorithm or algorithms for min cost max flow.


Complete explanation of state elimination methods

I'm not an expert, but I try to answer your question with an order, and if I will say something wrong, the people can improve my answer.
In general, is possible to use the State elimination method to convert a "Deterministic state automata" (DFA) to a regular expression (RE).
From the theory, we know the information below

If a language is regular, then it is described by a regular expression.

We also, know that if a language is regular is accepted by a DFA.
well now to convert a DFA that describes our regular language to the RE, we need to convert the DFA into a "Generalized Nondeterministic automata" (GNFA).
Definition of GNFA

A GNFA is simple nondeterministic finite automata (NFA) wherein the transition (arrows of the graph) can contain a regular expression.

We also need the rules about this GNFA, we need the rules below:

The start state must behave only outgoing state and must hasn't incoming edge.
The final/accepting state must have only incoming transition and it just hasn't outgoing edge.

Structure example

We can convert easily DFA to a GNFA with a special form, with the following step:

If a DFA has an incoming edge to the start state A, we move the start state to new state B and we can connect the state B->A with an empty string (ϵ).

In addition: The start state must have only outgoing transitions. (if there is an incoming arrow/edge, it must not carry a (non-empty) label).

if the final/accepting state A has an outgoing transition, we can move the final state to a new state B and connect the node A->B with an empty string (ϵ).

In addition: The final/accepting state must have only incoming transitions.
PS. The additional informations are coming from the first comment below this answer.
Now the last step is to convert the GNFA to a RE.
After the conversion of DFA to a GNFA with a special form, we know that each arrow of GNFA can contain a regular expression, and at this point, the last step consists of the following passages:

Remove the intermediate step with an intermedia regular expression, until to remove all intermediate state.
The result that we can have is (InitState)--- RE---->(FinalState), and the regular expression of the transition from InitState to FinalState is the regular expression accepted from the previous DFA.

The passages can be express with the Figure below:

A complete example, that can help you to understand the process described inside this answer.


Algorithm to translate a deterministic Büchi automaton to LTL (when possible)

You may find the algorithm in Diekert and Gastin's paper, Section 12. It works for both NBW and DBW (provided that you have the $\omega$-expression), and this can be decided in polynomial time.


None of the above.  First, block sizes are rounded up to the nearest power of 2.  If you try to allocate an object of length 5K, it will first round that up to 8K.  Next, it will try to find a free block of size 8K.  In your example, you'll need to look at larger blocks -- the 1K, 2K, and 4K blocks are too small.  You'd better hope there is another 8K block (not shown) that is free, or an even larger block that is free and can be split up to create a 8K block.


Generating Combinations from a set of pairs without repetition of elements

One direct way is a recursive procedure that does the following on each invocation. The input to the procedure is a list of pairs that have already been chosen and a list of all the pairs.

Compute the smallest number not already covered by the input list. For the first invocation, this will be 0 of course, because no pairs have been chosen.
If all the numbers are covered, you have a correct combination, print it out and return the the previous step. Otherwise, the smallest number that is uncovered is the target we will aim for.
Search through the pairs looking for a way to cover the target number. If there is none, then just return to the previous level of recursion.
If there is a way to cover the target number, pick the first way and recursively call the entire procedure again, with the pair just picked add to the list of chosen pairs.
When that returns, look for the next way to cover the target number with a pair, without overlapping a previously chosen pair. If you find one, pick it and again recursively call the next procedure.
Continue steps 4 and 5 until there are no more ways to cover the target number. Go through the entire list of pairs. When there are no more correct choices, return to the previous level of the recursion.

The way to visualize this algorithm is with a tree whose paths are sequences of non-overlapping pairs. The first level of the tree contains all the pairs that contain 0. For the example above, the tree is

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

In this example all the paths through the tree actually give correct collections, but for example if we left out the pair (1,2) then the rightmost path would have only one node and would correspond to the search in step 3 failing.

Search algorithms of this type can be developed for many similar problems of enumerating all objects of a particular type.

It was suggested that perhaps the OP meant that all pairs are in the input, not just a set of them as the question says. In that case the algorithm is much easier because it's no longer necessary to check which pairs are allowed. It's not even necessary to generate the set of all pairs; the following pseudocode will do what the OP asked. Here $n$ is the input number, "list" starts out as an empty list, and "covered" is an array of length $n$ initialized to 0.  It could be made somewhat more efficient but that's not my immediate goal.

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}


Lower bound on the covering radius of a code

The idea is to use a sphere packing argument, only for covering. Let $V_q(\rho)$ be the volume of a Hamming ball of radius $\rho$. The Hamming balls around all codewords cover the entire space, so $V_q(\rho) q^k \geq q^n$, or $V_q(\rho) \geq q^{n-k}$. To deduce the bound, use an approximation for $V_q(\rho)$.


The average codeword length of your professor's code is $2.577$.

The average codeword length of your code is $2.662$.

Huffman's algorithm produces a code minimizing the average codeword length.

You draw the conclusions.


Here is a more general statement:

  A language $L$ has an undecidable subset iff $L$ is infinite.

For the proof, note first that if $L$ is finite then all its subsets are finite and so decidable. Conversely, if $L$ is infinite then it has uncountably many subsets. Since there are only countably many decidable languages, some subset of $L$ (indeed, most subsets of $L$) must be undecidable.


I will make slightly stronger assumptions than that are provided in the question: we have a data structure, representing a tree, that consists of an array of vertices of the tree (allowing random access) and given a vertex, we have access to an array containing that vertex' children (again allowing random access). Furthermore we can check vertices for equality, and given a vertex we can (in $O(1)$ time) locate it in the main array.

On a tree of $n$ nodes, any strategy must take at least $\Omega(n)$ time in the worst case.

Consider a path of $n$ vertices. Define a vertex to be "examined" if it is accessed via the main array, via a children array or is reported as the root. Every non-leaf vertex must be examined by the algorithm: if some non-leaf vertex $v$ is not examined, we can make $v$ the root, making $v$'s child a child of $v$'s predecessor. This is not seen by the algorithm and it will incorrectly report the old root: making $v$ changes its children array (which is not seen by the algorithm as $v$ is not accessed at all) and changes the child array of $v$'s parent (which by the assumption of $v$ not being examined is not seen by the algorithm either).

Thus every non-leaf vertex in a path must be examined and any algorithm thus takes $\Omega(n)$ time.


Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%.  This assumes, among other things, that good hash functions are used.  The formula is:

$(1 - (1 - [1/m])^{kn})^k$

where $m$ is the number of bits in the filter, $k$ is the number of hash functions and $n$ is the number of entries in the filter.

Because items cannot be removed from a typical Bloom filter, if generation of the filter is too expensive, you might consider a counting Bloom filter to allow deletions.

(Although I have not read of it being used and do not know if it would be effective, one might use ORed signatures in each field instead of a set bit, where each signature has half or fewer of the bits set.  A possible match is found when ((entry_signature ^ test_signature) & test_signature) == 0 for each entry selected by a hash function.  If every signature has the same number of set bits, this would be like nesting a Bloom filter with a size equal to the signature size and the number of hash functions equal to the number of set bits.)


In the worst case you will store 1 record per node, so you will need 1000 nodes.

In the best case you will store 4 record per node, so you only need 1000/4 = 250 nodes.

In the worst case you will have 3 children per node, so your tree will only grow by multiples of 3 for each level.  So we can say that $3^h \geq 1000$, where $h$ is the height.  So $h=\lceil\log_3 1000\rceil=7$

In the best case you will have 5 children per node, so your tree will be $h=\lceil\log_5 250\rceil=4$


Understand the time complexity for this LCS (longest common subsequence) solution

I assume you are interested in worst-case complexity.

A dynamic programming approach (recursively) breaks a problem into "smaller" problems,
and records the solution of these subproblems to make sure
that subproblems are not computed several times. So when the time required to combine subproblems is constant (it is the case for LCS), you only have to find an upper bound for the number of possible subproblems that will be solved along the program.

Here the subproblems are of the form
findLCS(s1,s2) where s1 is a prefix of str1, and s2 a prefix of str2.
There are (1+str1.length()) possible prefixes for str1, and
(1+str2.length()) for str2.
The number of possible subproblems is therefore (1+str1.length()) * (1+str2.length()).
Furthermore, a solution is obtained in constant time from its subproblems.
Hence complexity O( str1.length()*str2.length() ).

N.B. on some sequences all subproblems will be indeed computed, e.g., when letters in str1 and str2 are distinct.
Consequently, the quadratic bound is "tight".

N.B.2 you may find (short) explanations on the wikipedia page for LCS


Proving complexity of computing product of matrices

I'm afraid you can't.  As I mentioned in my response to your previous question:

  The complexity of a problem is the running time of the fastest algorithm for that problem.

There exist algorithms for this problem whose running time is much less than $N^3$.  As I described in my previous answer, there are much more efficient algorithms for matrix inversion (and for matrix multiplication).  I linked to algorithms for both.

Therefore, you cannot prove that the complexity is $\frac83 N^3 + \dots$ flops -- because that isn't true.

Given your pair of questions, and since you said you're not sure where to start, I would suggest you start by reviewing the following material here on this site:

What is the difference between an algorithm, a language and a problem?
How to come up with the runtime of algorithms?
How does one know which notation of time complexity analysis to use?
Is there a system behind the magic of algorithm analysis?

Then, read some material on fast algorithms for matrix multiplication and other matrix operations.  That'll be a starting point, at least.

If what you want is to understand the running time of LU-factorization of a matrix, that's a different question.  If that's your question, you should probably research that, and then post a new question, showing what research you've done.


The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of.  Just keep reading for a few more sentences, and you'll immediately find the justification.  As it says,

  "First of all, we notice that each type 1 comparison definitively eliminates one edge ...  Since the numbers of edges of A and B are at most $(3p-6)$ and $(3q-6)$, respectively, the number of type 1 comparisons is bounded by ..."

and so on.  So to find the explanation for that statement, just continue reading a few sentences onward.

And, as the paper says in the introduction,

  "[our algorithm]" is based on the property that the number of edges of the convex hull of $n$ points is at most linear in $n$."

Therefore, your examples are not possible.

See also the 3rd paragraph of Section 4 for more elaboration ("It is a crucial observation that...").


Nice question. It is not regular.

Notice that this language consists of words where some nonempty prefix is an even palindrome.

Intersect $L$ with $(01)^{+} (10)^{+}$. If a word of this form has a palindromic prefix: $(01)^n (10)^m = u u^R v$ and $u \neq \varepsilon$, then the center of palindrome must be between the group of $01$ and the group of $10$. For example, take the word $0101011010101010$. The only possibility of breaking a prefix into a palindrome is $(010101\cdot 101010)\cdot1010$. (I leave the proof of this statement to you.)

Therefore, $L \cap (01)^{+} (10)^{+}=\{(01)^n (10)^m : m > n \geq 1\}$. However, this language is not regular - for example, each prefix $(01)^n$ is in a different Myhill-Nerode class.


Here is your suggested automaton, if I understand your transitions correctly (initial state is 1)

This automaton will only accept $\epsilon$, and words consisting of a number of $b$'s

Hints to make one that accepts your language:

Make sure that it accepts $\epsilon, a, b$ and make sure that you "move away" from accepting states when seeing a $b$ after an $a$ (keep in mind that $aabb$ is also a string in the language, i.e the second $b$ should make the machine go to an accepting state).


Computation Complexity of stream algorithm

One standard way to measure the running time of streaming algorithms is to count the amount of time taken per item that the algorithm processes.  For instance, one algorithm might take $O(1)$ time per item.

Also it is common to analyze the memory usage (space complexity) of these algorithms, as in many practical situations memory can be a limiting factor.  That is straightforward to measure.  Usually the space complexity is measured not as a function of the number of elements seen, but rather as a function of something else -- e.g., the accuracy of the answer, or the number of distinct items in the input stream, or something else that is appropriate to the application and that makes it possible to do analysis.

I suggest you read about streaming algorithms.  There's lots of work on those topics and those fields certainly measure the running time of their algorithms. See, e.g., https://en.wikipedia.org/wiki/Streaming_algorithm and textbooks on the subject.


Do we include Transmission delay in Round trip time?

Suppose you have two computers (A and B) both connected to a switch with cut-through forwarding. When you are interested about RTT between computer A and computer B, you'll omit transmission delay, because the switch transmits the frame to B as it arrives from A, so transmission delay is not significant. Now, suppose that our switch uses store-forward, in this case, when the frame arrives, the switch will first store it completely, and then sends it to B, so we have to deal with transmission delay.


How to solve the following left recursion?

Rewriting (A|B) a as Aa | Ba allows you to apply the solution you already have (with Ba instead of B).


Is a language containing set of binary numbers which are divisible by number N Regular?

You can produce a finite automaton to recognize binary strings divisible by $N$ for any $N>0$. Use $N+1$ states, $s$ (the start state) and $q_i$, where being in state $q_i$ corresponds to having seen input $B$ which is congruent to $i\bmod N$.

The transitions are then easy enough: in state $q_i$ and seeing a $0$ input the machine would pass to state $q_k$, where $k\equiv 2i\bmod N$, since appending a zero to a binary string doubles the number represented. Similarly $\delta(q_i, 1)=q_k$, where $k\equiv 2i+1\bmod N$.

The start state is there solely to avoid the question of what number the empty string represents, and obviously $q_0$ is the final state.


Minimum number of swaps in sorting sequence

This problem is known as "sorting strings by interchanges". Amir et al [1] proved that the problem is NP-complete and admits a 1.5-approximation. They also obtain other results for transforming two strings into one another (which is not equivalent to the sorting problem) and using several other cost functions for each transformation.

[1]: Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
On the Cost of Interchange Rearrangement in Strings. SIAM J. Comput. 39(4): 1444-1461 (2009) -- https://epubs.siam.org/doi/10.1137/080712969


Are hash functions really quantum resistant for commitment schemes?

No.  I can see how that sounds like it could work, but it doesn't actually work.  You're missing an important detail about how we implement classical functions on a quantum computer.  The usual way to implement non-reversible functions with reversible logic is to use ancilla bits (i.e., constant inputs, and junk outputs that are discarded).

For instance, suppose you want to implement the function $f(x,y) = x \land y$ (it computes the boolean AND of its two inputs).  You can make this invertible by instead implementing $g(x,y,z) = ((x \land y) \oplus z, x, y)$ (here $\oplus$ denotes XOR).  Here $g$ is called a Toffoli gate.  Note that $g$ is invertible, even though $f$ is not.  Moreover, we can compute $f$ by noting that $g(x,y,0) = (f(x,y,0),x,y)$, so if you want to compute $f$ in a reversible way, you feed in $x$, $y$, and a constant $0$ to $g$, then discard all but the first bit of output.  Just because you can invert $g$ doesn't mean you can invert $f$.  First, given only $f(x,y)$, we don't know what value to place into the other output bits of $g$.  Second, if we made random guesses at those outputs and then inverted $g$, that won't necessarily give us an inverse of $f$ (try it!).

The same is true for SHA2.  We know how to implement SHA2 on a quantum computer.  It uses ancilla bits.  Those ancilla bits prevent you from inverting SHA2 by trying to reverse the quantum computation.


How can I solve this deadlock related problem mathematically?

As per the question, all the even processes request only even resources(i.e. Ri & Ri+2)
Where as odd processes request:
either,
odd resources(i.e. Rn-1 & Rn-1-2) when 'n' is even.
or,
even resources (i.e. Rn-1 & Rn-1-2) when 'n' is odd.

Deadlock can only happen when even and odd processes request overlaps i.e. odd processes have to request even resources which means 'n' must should be odd.

Mathematically,

Let Pn-i be an odd process then,

n-i<=k

or,ceil(n-i)=k   here ceil() is ceiling function since the value at max can be equal to k.

i=ceil(n-k)---eqn(i)

For deadlock to happen,

i=n-i-2

substituting value of i from eqn(i), we have,

ceil(n-k)=n-i-2

solving further we get,

k=ceil((n+2)/2)  where 'n' is odd

since, 'n' must should be odd option A and C can be ignored now coming to option B substituting n=21 we get k=12
In option D substituting n=41 we get k=22.

so option B is correct.For option D to be in deadlock k should be equal to 22.


How to compare algorithms having the same complexity

By "having the same complexity" I assume you mean having the same time complexity.

If you have done fine analysis of time complexity of these algorithms then there may be hidden constants or factors of lower degree polynomials which are ignored when you compare using big-O notation but have effect in practice. For example, if one algorithm always takes $n^2 + 100n + 10000$ steps and the second one takes $0.3n^2$ then the second one would be a better  choice, though both run in $O(n^2)$.

You could also consider their space complexity and choose one which consumes less memory if the memory consumption matters and more important than the time complexity.

If you aim to implement these algorithms yourself and use it in your commercial application (or something like that) then you could think about how easy they are implemented and how easy these algorithms scale.


What is the complexity of a bracketed search using mediants?

The relation between the Stern–Brocot tree and Farey sequences shows that if $0 < p/q < 1$ and $(p,q) = 1$ (i.e., $p/q$ is a reduced fraction) then $p/q$ is at the $q$th level of the tree. Since the running term of your algorithm is linear at the level in which you terminate, your algorithm takes time $O(q)$, where $p/q$ is the answer; but this is not so helpful.

You haven't specified what your stopping criterion is, but presumably you have some error threshold $\epsilon$. The question therefore is for which Farey sequence is it the case that adjacent terms are at distance at most $2\epsilon$ (and so every point is at distance $\epsilon$ from some point). Using the fact that the distance between adjacent fractions $p_1/q_1,p_2/q_2$ in a Farey sequence is $1/(q_1q_2)$, it is not hard to show that the maximal distance at the $q$th Farey sequence is $1/q$. Therefore if you are aiming at a distance of $\epsilon$, then your algorithm will run in time $O(1/\epsilon)$ in the worst case.

However, "most" adjacent fractions at the $q$th Farey sequence are at distance $O(1/q^2)$, and so on average you would probably expect a running time of $O(\sqrt{1/\epsilon})$ (unfortunately, this average is with respect to the input rather than the algorithm).


MIPS with one read port in the register file?

For your MIPS CPU with 1read + 1write register file :

ALU instructions will last two cycles as you describe.
Load instructions can be executed in 1 cycle (with data in cache, etc...)
Store instructions must be split in two cycles to get the two source registers.

Another example, in SPARCs, STORE R1,[R2+R3] require two cycles with a 2R1W register bank, whereas LOAD [R1+R2],R3 can be executed in 1 cycle.


Knapsack-like problem with profit formula

One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).

To implement this algorithm efficiently, start by sorting the dumbbells according to weight and according to rep (separately), and find the $M$ dumbbells with maximal rep. Now go over the dumbbells in order of weight, each time removing the dumbbell with lowest weight and updating the set of $M$ best dumbbells. If you're careful you might be able to implement this in $O(N)$, so together with the initial sorting, the algorithm might run in time $O(N\log N)$.


Strictness Strictness ($\textsf{ST}$) is related to recoverability. Serializability ($\textsf{SR}$) is one of many consistency conditions of transactions, which is somewhat orthogonal to recoverability. 2PL is a protocol usually used to ensure serializability.

First, I don't think the term "strict transaction" is proper. Strictness, just like serializability, is defined over executions (also called histories or schedules) of transactions.

Secondly, strictness is incomparable to serializability (there are various versions of serializability. I suppose you are referring to CSR --- conflict serializability).

Finally, your question "Can there be a strict transaction that is not 2Phase?" should be

  "Is there any execution which is strict but not serializable?"

The answer is "Yes". For example, $e = r_1(x) \; w_2(x) \; w_2(y) \; c_2 \; r_1(y) \; c_1$. You can check that $e \in \textsf{ST} \land e \notin \textsf{SR}$.


Are these special (one production) Context-Free Grammars always unambiguous?

Here is a simple counter example:
$S \rightarrow aSbSaSbS \space |\space  \epsilon$

and string $w: abababab.$
In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$.

Why I was able to get this grammar?

Let's rewrite above grammar with numbers assigned to each $S$'s.

$S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$

Now We can virtually eliminate $S_1$ and $S_3$. (For this whenever we have to derive something from $S_1$ or $S_3$ we will only derive $\epsilon$ from both of this type of $S$'s.)

So we get $S \rightarrow abS_2abS_4|\epsilon$.  (At this time we already have got rid of rule 3.)

Which we were looking for.


Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

I think we can prove that $O(n)$ time is not attainable for the special case $k=2$, using an adversary argument.

Fix a constant $c>0$.  Let's take two lists of $n$ items, where the resulting $2n$ items are all different.  Consider an algorithm that has done $cn$ comparisons between the $2n$ items in the two lists.  This defines a partial order $\preceq$ on the $2n$ items, where if the algorithm has compared $x,y$, we have either $x \prec y$ or $y \prec x$, and where we let $\preceq$ be the reflexive, antisymmetric, transitive closure of $\prec$.

I'm pretty sure that, with high probability over the choice of the lists, there exists some item $x$ in the first list and some item $y$ in the second list such that $x,y$ are incomparable under $\preceq$.  (This needs proof; I'll let you fill this part in.)

Now we can consider a parallel universe where everything is exactly the same as before, except that in the alternate universe, $y=x$.  This alternate universe is also compatible with all of the comparisons that have been made by the algorithm.  Thus, the algorithm cannot distinguish these two universes, so it must produce the same output in both cases.

However, the correct output for the two universes differs.  The correct output in the first universe is the empty set, while the correct output in the second universe is the element $\{x\}$.  Consequently, the algorithm must be incorrect in at least one of these two universes.  In other words, for at least one of these two inputs, the algorithm produces the wrong output.

It follows that, when $k=2$, any $O(n)$-time algorithm must produce an incorrect answer on at least one input.  In other words, any correct algorithm must take $\omega(n)$ time.


Intersection of Turing-recognizable language and regular language

A recognizable language is not necessarily decidable. If you intersect such a language with $\Sigma^*$ it doesn't suddenly become decidable.


If $L_1,L_2\in \mathrm{NP}$ and $w\in L_1$ or $w\in L_2$ then can $L_1\cup L_2=L$'s verifier use the same certificate $c$ for $w$?

Assume that $c_1$ and and $c_2$ are polynomial size certificates for $x \in V_1$ and $x \in V_2$. Then define $c=c_1\#c_2$, a new certificate formed by concatenation of $c_1$ and $c_2$ which is clearly polynomial size. Then $V_1$ and $V_2$ still can use $c$ as a certificate to verify $x\in V_1$ and $x\in V_2$. $V_1$ will use the left part of $c$ and the $V_2$ will use the right part of $c$.

  Is a verifier by definition is deterministic TM?

Yes, the verifier is a deterministic TM, by definition.

  In the above answer, does $V_3$ runs $x,c$ on both $V_1$ and $V_2$ in the worst case?

You can treat $V_3$ as a TM which invokes (as subroutines) $V_1(x,c)$ and $V_2(x,c)$, so if $V_1$'s worst case is $O(f)$ and $V_2$'s worst case is $O(g)$ then $V_3$'s worst case is either $O(f)$ or $O(g)$ which is polynomial.


Explanation of the knowledge representation hypothesis (Brian Smith)

This is a philosophical statement which uses sophisticated language per convention. Here is another version (according to this page):

Any process capable of reasoning intelligently about the world must consist in part of a field of structures, of a roughly linguistic sort, which in some fashion represent whatever knowledge and beliefs the process may be said to possess.

You can visit the page I linked from some critique of both statements. For another critique, here is an example taken from these lecture notes. Consider the following two procedures for translating the colors red and blue into French:
function translate1(color):
  if color is "red" return "rouge"
  if color is "blue" return "bleu"

function translate2(color):
  dictionary = [ "red" -> "rouge", "blue" -> "bleu" ]
  return dictionary[color]

According to the lecture notes, only the second function translate2 conforms to the hypothesis.

Now for some positive example. Consider an automated translation service such as Google translate. As a vast simplification, Google has a dictionary that it uses to translate words from (say) English to French. This dictionary is a "propositional account" of the knowledge of the process. Here by "propositional account", Smith means a set of logical statements, for example:

The translation of red is rouge.
The translation of blue is bleu.

(Technically, he means first-order logic, so you would put these statements in concise logical form, or as Prolog statements.)
The translation program uses its dictionary in its efforts. Thus the dictionary plays a "causal ... role" in the "behavior" of the system. That is, since rouge is the counterpart of red, if you give the program red it outputs rouge. We don't claim any 'real' intelligence for the program, so this role is only "formal", and moreover our understanding of the dictionary as a list of matching words in two different languages is only an "external semantic attribution" that is irrelevant for explaining the behavior of the program. After all, the program doesn't really 'speak' English or French, it only gives the impression of being able to.

Let me try to put the hypothesis in simpler words:

Programs use databases that represent knowledge.

(See Surely you're joking, Mr Feynman!, page 281.)
Now we can come up with many more examples. JPEG compression programs use knowledge about the human visual system in the form of the quantization matrix, which explains which Fourier coefficients are more important for image representation. Recommendation systems use a database of products that can be recommended, and another database that keeps track of what other users liked. OCR systems use implicit representations of symbols (letters, digits, and punctuation) in the form of a machine learning recognizer for them.
Does modern machine learning conform to the hypothesis? Considering the last example, optical character recognition, the "catalog of characters" isn't stored as such, but only implicitly as (say) a set of weights in some neural network. This is certainly not a "field of structures, of a roughly linguistic sort", as per the other version of the hypothesis.
Modern artificial intelligence has largely moved away from the naive and romantic view of classical artificial intelligence, as exemplified by the KR hypothesis. Instead, now we often use statistical methods of machine learning which are much more successful in practice but much less satisfying from a human perspective.
Are knowledge representation techniques used in the real world? This is a question left for the experts to answer.


Known bounds on space complexity of multiplication decision problem

You can do it in $O(\lg N)$ space, if you're willing to accept a randomized algorithm with an exponentially small probability of error.  In practice, this algorithm is practical and every bit as good as a deterministic algorithm with no possibility of error.

The idea is to choose a random $\ell$-bit prime $\alpha$, reduce $m,n,p$ modulo $\alpha$, and then check whether the congruence $m\times n \equiv p \pmod{\alpha}$ holds modulo $\alpha$.  This test can be done with $O(\ell)$ bits of space (about $3\ell$ bits).  Moreover, it suffices to take $\ell = O(\lg N)$.  In particular, if you want the probability of error to be at most $1/2^t$, it suffices to take $\ell=O(t + \lg N)$.  The constants hidden by the big-O notation are small (something like 3 or so).

Now take $t=100$, and you get a practical algorithm.  The probability of error is $1/2^{100}$, which is so small as to be negligible.  It's more likely that you have a cosmic ray bit flip that causes your computation to give the wrong answer than that you get a wrong answer due to bad luck.  (And cosmic ray bit flips affect deterministic algorithms, too, so the notion of an algorithm with zero error is not something that can be implemented in the real world; the best we can hope for is for the probability of error to be negligible.)

The analysis of this relies upon the prime number theorem.  I don't have time to write out the full analysis right now, but the basic idea is that the algorithm gives the wrong answer only if $\alpha$ divides $mn-p$.  Since $|mn-p|$ is (at most) $2N$ bits long, there can be at most $2N/\ell$ distinct $\ell$-bit prime divisors of $mn-p$.  Also, by the Prime Number Theorem, there are about $2^{\ell}/\ell$ possible $\ell$-bit primes.  Therefore, the probability that the randomly chosen $\alpha$ happens to divide $mn-p$ is at most $(2N)/2^{\ell}$.  Now solve for $\ell$, and you get the result I claimed above.

Importantly, the probability of error is taken only over the internal coin flips of the algorithm, not over the possible values of $m,n,p$.  In other words, even if an adversary chooses the values of $m,n,p$, the probability of error will still be at most $1/2^t$.


Why does this pumping lemma application "prove" that 0*1* is not regular?

The idea is that there is some partition that fulfills the condition of the pumping lemma - you do not have the choice of the x, y, and z - you have to show that there exists no x, y, and z that satisfies the conditions.


Repeated fingerprinting after array updates

Any of the first three options you list are likely to be fine for what you want.

The CRC provides a good fingerprint (indeed, there's some theory to back that up, based on the theory of Carter-Wegman hashing, 2-universal hashes, etc.).

The Rabin fingerprint is also fine, and is essentially equivalent to the CRC (modulo small technical details that are unimportant).  $f^i(m_i) = m_i x^i \bmod p(x)$, which can be readily computed even for very large values of $i$ using fast modular exponentiation.

The Rabin-Karp hash is also fine, as long as you choose a good modulus $m$.  Don't pick a power of two; use a prime number.  Exponentiation is again fast if you use standard algorithms for fast modular exponentiation.  If possible, use a constant $a$ that is larger than the largest possible value of any single array element (single byte), i.e., larger than 256.  (Alternatively, it might be possible to pick $m$ to be a power of two if you also choose the constant $a$ to be a large random number modulo $m$; I haven't thought about that too carefully, so if that sounds attractive, please post a  separate question asking about that specific scenario.)

Buzhash is a little weaker than the other hash functions, though I suppose it's possible it might be good enough in practice.  Yes, Buzhash is susceptible to swapping of two values that are a multiple of 32 positions apart.  There might be ways to fix this, but given the large lookup tables required, that seems moot.  As you say, Buzhash requires a lookup table that maps from 8-bit values to 32-bit values (i.e., 256 entries, where each entry is a 32-bit word), so it sounds like Buzhash is not going to be feasible in your situation.


How is the traveling salesman problem verifiable in polynomial time?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.

The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you describe, "Is there no TSP path with length at most $C$?" is also in co-NP: if you unpick the double-negation, a "no" instance to that problem is a "yes" instance to TSP and we can verify those in polynomial time.

There are some problems, such as integer factorization and any problem in P, that we know to be in both NP and co-NP. (Thanks to user21820 for pointing this out.)

It's not known whether NP and co-NP are the same set of problems. If they're the same, then we can verify both "yes" and "no" instances of TSP. If they're different, then P$\,\neq\,$NP, since we know that P$\,=\,$co-P (because we can just negate the answer of a deterministic machine, giving the answer to the complement problem).


Batch regularization & L2 regularization

No. They are not equivalent.  They are two different techniques, that each provide some kind of regularization, but using one doesn't necessarily make the other redundant.  For instance, in the paper you cite, the authors are using both (see Section 4.2.1 for mention of L2 regularization).

Specifically: whether or not it is more effective to use just batch regularization or to use both will probably depend on the specific learning task you have in mind.  But there is no theory that implies the two are equivalent.

Batch normalization still has a bias term that is added after the normalization step (the $\beta$); it does not eliminate it.  L2 regularization penalizes large weights and large biases.  As far as I can tell, batch regularization doesn't try to do either (at least not explicitly).

When using L2 regularization with batch regularization, I imagine you could either L2-penalize just the weights; or L2-penalize the weights, the $\gamma$ terms (scaling), and the $\beta$ terms (shift).  I don't know which will produce better results.  My intuition says the latter might be preferable, but experiments and data beat intuition any day.


is reducing to normal form simply applying beta-reduction?

Using only $\beta$-reductions is sufficient to get to a normal form if variables are named “correctly”.

What do we mean by that?

Let’s take as an example the term $\lambda x y. x\ y$.
Informally, it is a function that takes two arguments - variables $x,y$ and gives us the application of first argument to the second - $x\ y$. Now we want to apply something to this term, say $$(\lambda x y. x\ y)\ a$$

After we perform the $\beta$-reduction, substituting $a$ for $x$ in our term, we get $\lambda y. a\ y$ and we realize that whatever we substitute for $x$, we should be left with a function that applies it to the input variable $y$.

What if we want to substitute a variable named $y$ for $x$? We would be left with $\lambda y. y\ y$ which is a function that takes a variable and applies it to itself! Not at all the function we thought we would have for any $a$.

This example demonstrates that sometimes $\alpha$-conversion is necessary as a helper tool, and I emphasize the word “conversion” because it is not per se reduction.

You could also check my answer on this question that has computation similar in nature to yours and maybe try pLam interpreter to see all the reduction steps with colored terms that go into reductions.


Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

To apply the pumping lemma for regular languages:

You assume some pumping length $p > 0$: Suppose a pumping length $p$.
You pick a string $s$ such that $|s| \geq n$: Indeed, $a^pb^p$ is a good one since $|a^pb^p| = 2p \geq p$.
Now, you have to consider all the partitions of $s$ as $xyz$, such that

$|y|>0$ and
$|xy| \leq p$.

In this case, the 2nd inequality restricts $y$ to contain only $a$'s. Therefore, all the possible partitions are of the form $y = a^k$, $x = a^{p-k-r}$ and $z = a^rb^p$ for $k$ and $r$ such that $k > 0$ and $p \geq k + r$.

For every possible partition of the previous step, you have to show that there is some $i\in\mathbb{N}$ such that $xy^iz$ is not in the language.

Here, consider $i = 0$. Then $xy^0z = xz = a^{p-k-r}a^rb^p = a^{p-k}b^p$.
It is now a matter of showing that $p-k\neq p$, or, equivalently, that $k > 0$ which is already true.


Why is linear programming in P but integer programming NP-hard?

The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no longer carries any meaning in terms of whatever SAT instance you were trying to simulate.

The tough answer to this is that we don't know that they aren't in the same complexity class. Nobody has a proof that $P \neq NP$. If we understood the deeper reasons why the problems were so different, that would require that we understood why the complexity classes were different, which we don't.


Regularity of the exact middle of words from a regular language

Hint: Consider some DFA for $L$. For every $n \geq 0$, let $A_n$ be the set of states $s$ such that there is some word of length $n$ which leads the DFA from the initial state to $s$. Let $B_n$ be the set of states $t$ such that there is some word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s,t$, let $R_{s,t}$ be the (regular) set of words leading the DFA from $s$ to $t$. We have
$$ L_2 = \bigcup_{n \geq 0} \bigcup_{\substack{s \in A_n \\ t \in B_n}} R_{s,t}. $$
Since there are only finitely many possibilities for $s,t$, the union is in fact finite, and so regular.


Application of set theory subjects as ordinals, forcing, generic filters in software engineering

Generally speaking, if you want to present some applications of the theory, it's more effective to start with applications first and teach the theory that's needed for that application, rather than select a collection of theory and then search around for some application of it.

So, one way to approach your question is to ask why the department wants software engineers to know set theory. How will set theory help software engineers?  Then once you know the answer to that question, you could devise a curriculum based upon the elements of set theory that will be relevant to software engineers.  Most likely the set of topics that should be taught to software engineers is quite different from the set of topics that we would teach to mathematicians.

If you've followed this approach to course design, you should able to answer very clearly what the applications are and why you are teaching them this material.  This approach can also potentially lead to better student engagement, depending on student's motivations.  However, this approach likely requires re-thinking the entire course and starting over from scratch on the syllabus and topics you plan to teach, which might or might not be attractive in this case.


Generalization of Functors to other datatypes?

I guess no one else is going to answer this, so I'll take a crack.

First, there's nothing inherently 'functional' about categories, necessarily. For instance, you can make any monoid into a category, where you have one object, and then the arrows from that one object to itself are the elements of the monoid. The identity element is the identity arrow, and composition is monoid multiplication. Then functors between two monoids in this sense are homomorphisms between the monoids; they are functions that preserve identity and multiplication.

Categories are then generalizations of this to situations where the monoid values have types, and can only be multiplied together when the types correspond. The specifics of this work for functions, but it could be a lot of other things, too. You could try to devise a category where $Hom(X,Y) = X×Y$, and then functors from/to that category would be obligated to map from/to products.

However, it is also common to define additional structure beyond just being a category. For instance, even for 'functional programming,' you are usually talking about (at least) Cartesian closed categories. These are categories $C$ that have additional structure:

$$-×- : C × C → C$$
$$1 : C$$
$$[-,-] : C^{op} × C → C$$

Where $×$ forms binary products, $1$ is a terminal object, and $[-,-]$ forms exponentials, so:

$$C(X×Y,Z) \cong C(X, [Y,Z])$$

And when you have categories with additional structure like this, you also want to talk about functors that preserve that extra structure. So there are Cartesian closed functors between Cartesian closed categories that map products to products, terminal objects to terminal objects, and exponentials to exponentials.

So, yes, you can describe plenty of structure besides just $Hom$, and talk about maps that preserve all that structure (in various senses), not just functors.


Using the pumping theorem to show that this language is not context-free

Suppose that $L$ is context-free. Then the pumping lemma for context-free languages tells us that $L$ has a pumping length $p \ge 1$. We want to show that this leads to a contradiction, by exhibiting a string that is in $L$ but cannot be pumped in the manner specified in the lemma.

Consider the string $s = a^pb^pc^{(p^2)}$. Clearly, $s \in L$.

Now, see if you can show that all the possible ways of breaking down this string into the chunks specified in the lemma lead to a pumped string that is not in $L$.


Find string patterns preferably in regex for string streams

The general approach is likely to be:

Identify a set of candidate patterns that might appear.
For each candidate pattern, check for all instances of that pattern.

I'm not aware of any simple procedure that avoids the need for step 1.  The problem is that there are many possible patterns that might appear (e.g., "consists solely of Latin-8 characters"; "length is always at most 100") but most of them won't be meaningful or useful in your domain.  Only you know what will be meaningful/useful.  So, you'll have to use your domain knowledge to identify which potential patterns are useful -- I don't know of any algorithm that can do that for you.