Can a Turing Machine decide if an NFA accepts a string of prime length?

The lengths of the strings accepted by a DFA form a semilinear set (like in Parikh's theorem for context free languages), the description of those isn't too hard to come by (essentially splice up all possible cycles of the automaton), and by Dirichlet's theorem any arithmetic progression of the form $a + b k$ with $\gcd(a, b) = 1$ contains an infinitude of primes.

Pulling the above together gives an algorithm to check if your regular (or even context free language) contains strings of prime length. Definitely not a simple question, IMVHO...


Set of vertex-disjoint cycles maximizing different colored vertices

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP.

Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature and can be solved in polynomial time with a reduction to the Assignment Problem.

With the introduction of colors to the problem, it is NP-hard (and the corresponding decision problem is NP-complete).  The problem that you described can be called TROPICAL MAX SIZE EXCHANGE (TROPMAX EXCHANGE).  CNFSAT reduces to TROPMAX EXCHANGE.

Create a graph with one vertex for each variable in the CNFSAT expression, with all of these "variable vertices" colored the same way.  Assign each clause in the expression its own color.  From each "variable vertex" create two cycles - label one cycle 'true' and one 'false'.  For each literal in the expression, create a vertex that is the color of its clause and put it on the appropriate 'true' or 'false' cycle of the corresponding variable vertex.  Finally, add additional vertices of some new color so that every 'true' and 'false' cycle has the same number of vertices.

Because we are choosing vertex-disjoint cycles, each 'variable vertex' can only be in its 'true' cycle or 'false' cycle, not both.  There are no cycles in the graph other than those true/false cycles.  Every cycle has the same number of vertices, so an algorithm that first maximizes the number of vertices in the cycles can choose any combination of cycles: either true or false for each variable vertex.  If the secondary criterion is to maximize the number of colors in the cycles, then if all colors can be included the CNFSAT expression can be satisfied.

Highley, Timothy and Le, Hoang. "Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent"
dmtcs:3186 - Discrete Mathematics & Theoretical Computer Science, July 31, 2018, vol. 20 no. 2
https://dmtcs.episciences.org/4690
https://arxiv.org/abs/1610.05115


Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

Any word $w$ in $L$ can be split into two words $w$ and $w'$ such that $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$, $w' \in \{c^r d^s \mid r+s > 0\}$ and if the last symbol of $w$ exists and is $d$, then the first symbol of $w$ is $d$.
On the other hand, every choice of $w$ and $w'$ that satisfies the above constrains induces a word $w w' \in L$.
In the following grammar the first two productions take care of generating $w'$, while the other productions generate $w$. In particular the nonterminal $X_\alpha^\beta$ with $\alpha \in \{a,b\}$ and $\beta \in \{cd\}$ will generate all the words in $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$ such that (i) if $\alpha=b$: then $n=0$ and (ii) if $\beta=c$ then $s=0$.
$$
\begin{align*}
S &\to Sd \mid X_a^dd \mid Yc \mid X_a^cc \\
Y &\to Yc \mid X_a^cc \\
X_a^d &\to aX_a^d d \mid X_a^c \mid X_b^d \\
X_a^c & \to aX_a^cc \mid X_b^c \\
X_b^d &\to b X_b^d d \mid X_b^c \\
X_b^c &\to bX_b^cc \mid \varepsilon
\end{align*}
$$


Shouldn't complexity theory consider the time taken for different operations?

All complexity theory is relative to some model of computation. Typically, we consider models of computation where all basic operations take unit time because that's usually precise enough and, frankly, it's already difficult enough to do that kind of analysis.

Typically, running time analyses are only quoted asymptotically anyway.  As long as there's a constant bound on the number of clock cycles required for any operation, saying that an algorithm takes $O(f(n))$ operations is exactly the same thing as saying that it takes $O(f(n))$ clock cycles: the difference is just in the constant hidden in the $O()$ notation.

Having said that, models of computation do vary in what operations they consider as being unit-cost. For example, ordinary Turing machines count moving the head one step as unit-cost; random access Turing machines can move the head farther at unit cost.  People who study the complexity of matrix multiplication are often interested in the number of times you need to multiply matrix elements, rather than the total number of arithmetic operations, precisely because of your observation that multiplies are significantly more expensive than additions on a real CPU.

But, again, many things are swept under the carpet by asymptotic analysis. Suppose you did produce a model in which branches are much more expensive than other operations. Fine but, if you have a loop that needs to be iterated $n$ times, where $n$ is an input, your compiler can only unroll a constant number of iterations of the loop.  So, instead of doing $n$ branches, you do, say, $n/8$ branches: that's still $O(n)$.


example for weakly fair v.s. strongly fair scheduling in concurrency

If you are familiar with temporal logic, the difference is quite easy to demonstrate:

Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually.

Strong fairness is $GFp\to Fq$ (or sometimes $GFp\to GFq$). That is, if $p$ holds infinitely often, then eventually $q$ will hold (or $q$ will hold infinitely often, in the second version).

Your description is slightly different from the above, in that your weak fairness has the "until" flavour, but it's the same idea.

To demonstrate the difference in the approaches, think of yourself as a process trying to gain access to some critical section. If you know that the system is weakly fair, then you need to raise a flag saying that you want access, and you have to keep this flag up all the time, until you get access. If the system has strong fairness, it is enough that you raise the flag every now and then, and you know that eventually you'll get access.

As an alternative example, children who want attention often go "mom" repeatedly until they are granted attention. This is similar to weak-fairness (of the mother), and as you can see, it prevents the child from doing anything else until granted attention. With a strongly-fair mother, it suffices for the child to say "mom" every few minutes, and go about doing other things in the mean time.

By the way, this question has an excellent answer by Cynthia Disenfeld at quora.


Languages having only one Myhill–Nerode equivalence class

Assuming that you mean the Myhill-Nerode relation, the Myhill-Nerode theorem states that the number of equivalence classes exactly equals the number of states in the minimal DFA accepting the language (if it's regular; otherwise there are infinitely many equivalence classes). So we have reduced the question to the following one:

  Which regular languages can be accepted using a DFA having only one state?

I'm sure you can answer this one yourself.


The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two nodes and two edges:

  ---- capacity 1 --->
A                      B
  <--- capacity 1 ----

If A is the source node and B is the sink, you can obviously see that if only positive flows are allowed, you get a max flow of 1 but if negative flows are allowed you'd get 2 (with the bottom edge flowing "backwards").

As I commented, the way to figure out the capacity of a graph that allows negative flows as well as positive ones is to restate the problem. Instead of allowing negative flows, add an additional reversed edge everywhere there's a normal edge in the original graph. Then solve the problem with only positive flows. In the trivial example above, you'd have two edges running each direction, and when you found the maximum using only positive flows, you'd get the right answer, 2.


How would you model Rust procedural macros?

I wouldn't consider it a higher-order function.  A higher-order function takes a function as input, or yields a function as its output.  In contrast, it sounds to me like your compiler extension is accepting data as input (the abstract syntax tree) and producing data on its output.
I suppose you could consider the AST a specification of a function, but that seems like a stretch to me.
I'm not sure that what name you attach to it matters much, from a computer science perspective.  A rose by any other name, and all that.


Which m numbers in the range [1, k] have sum equal to n

Hint:

What is the smallest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
What is the largest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
Can all numbers in between be so represented?


spanning tree implemented by a min priority queue

It would generate the MST for the component of the graph which the MST algorithm starts at, leaving the unconnected components untouched.


Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

Intuitively we cannot recognize $L$ using a pushdown automaton as the number of $b$'s has to be used twice, once in comparing against the number of $a$'s and once in comparing against the number of $c$'s. However, that is far from a proper proof.

We can just use the standard pumping lemma for context-free language for a rigorous proof.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

$vwx$ contains at least one letter other than $b$.
Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.
$vwx$ contains only $b$s.
Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}+1$. Then let $s=uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L\,.$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Here are two related exercises.

Exercise 1. Show the following language is not context-free.
$$ L = \{w  \in \{a,b,c\}^{*} : |w|_{a} > |w|_{b}\text{ and } |w|_{a} > |w|_{c} \}\,. $$

Exercise 2. Show the following language is not context-free. (Hint, Ogden's lemma.)
$$ L = \{w  \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{a} \not= |w|_{c} \}\,. $$


Worked out example of Slepian-Wolf Theorem

Here's a simpler example. Consider the binary erasure channel which erases its input with probability $1/2$. The channel capacity is $1/2$, so you should be able to send one bit of information by sending two bits on the channel. Or should you?

Shannon's theorem only guarantees that for every $\epsilon > 0$, you can send $(1/2-\epsilon) N$ bits of information by sending $N$ bits across the channel, with failure probability approaching zero as $N\to\infty$. There are two features of this theorem (shared by Slepian–Wolf) that you didn't take into account:

The theorem talks about asymptotic rates.
The theorem allows for some small failure probability.

The article you link to assumes you are already aware of all this. Since you appear not to be, I suggest reading a textbook on information theory, where all the relevant concepts are defined and explained.


Why does it seem as if I can apply the Pumping lemma to a language that is regular?

The pumping lemma says that, for every regular language there exists some pumping length $p$* such that blah blah blah.

You made two mistakes. First, you tried to choose $p$ based on a specific word, rather than based on the language as a whole. Second, you chose the wrong value of $p$. In particular, for the language you've given, $p=1$ has the property required of the pumping lemma: for every word $w$ in that language, you can write $w=\epsilon y z$ with $|y|=1$, and you'll find that $\epsilon y^n z$ is in the language for all $n\geq 0$.


The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.

It's undecidable* whether a given Turing machine even solves $P$, let alone whether it's optimal according to some criterion.  Since your problem isn't computable even without resource bounds, there isn't really any scope for complexity theory.

And how are you going to specify the problem $P$ anyway, except by giving some Turing machine?

* Off the top of my head, probably not even recursively enumerable.


Looking for non-entry level implementation of foundational algorithms and data structures in python. where to look?

David Eppstein has a bunch of algorithms implemented in Python in his PADS repository.


Find the minimum amount of swaps in fixed indices to sort an array

Your question appears to be about sorting networks. Sorting an array in the comparison model requires $\Omega(n\log n)$ comparisons, and so $\Omega(n\log n)$ of your swaps. Ajtai, Komlós and Szemerédi were the first to come up with a matching $O(n\log n)$ sorting network (the AKS sorting network), and their construction was simplified by Patterson. These networks also have the advantage that they can be divided into $O(\log n)$ layers of disjoint swaps. Very recently, Goodrich came up with Zigzag sort, another $O(n\log n)$ sorting network.

Since we know that there exist $O(n\log n)$ sorting networks, we can find an optimal sorting network in time $\binom{n}{2}^{O(n\log n)} = 2^{O(n\log^2 n)}$ (verifying that a network works takes time roughly $2^n$ using the zero-one principle). There is no reason to expect any subexponential algorithm.

You might be interested in Ian Parberry's page on sorting.

This part answers the following question: What is the maximal number of swaps needed to order an array of length $n$?

Suppose that your array contained numbers from $1$ to $n$. Then you can think of it as a permutation $\pi \in S_n$. Swapping two elements in the same as multiplying by a transposition, so the question is how many transpositions we need to multiply to get $\pi$. If the cycle structure of $\pi$ is $a_1,\ldots,a_k$ then this number is $(a_1-1) + \cdots + (a_k-1) = n - k$. Therefore $n-1$ is the most that is needed. An example of a permutation needing $n-1$ swaps is $(234\cdots n1)$, which corresponds to the array $2,3,4,\ldots,n,1$.


Non-existence of PSPACE-hard unary language

Suppose that $A$ is a unary PSPACE-hard language. We will show how to solve TQBF, a PSPACE-complete language, in polynomial time.

Recall that an instance of TQBF is a quantified formula of the form $\psi = \exists x_1 \forall x_2 \exists x_3 \forall x_4 \ldots \phi(x_1,\ldots,x_n)$, where $\phi$ is an arbitrary propositional formula. The instance is a Yes instance if the formula is valid.

We construct a binary tree which will represent the truth value of $\psi$. We do it level by level. Each vertex in the tree corresponds to a partial assignment of $x_1,\ldots,x_n$. At the root, we just write the empty assignment.

Suppose that we have constructed the $i$‘th level, where $0 \leq i < n$. We construct the $(i+1)$’th level as follows. For each vertex $\alpha$ on the $i$’th level, we add two children, $\alpha \cup \{x_{i+1} = 0\}$ and $\alpha \cup \{x_{i+1} = 1\}$. For each new vertex $\beta$, we consider the formula $\psi_\beta = Q x_{i+2} \ldots \phi(\beta,x_{i+2},\ldots,x_n)$. We apply the polytime reduction from TQBF to $A$ on $\psi_\beta$, obtaining a “truth value” $t_\beta$; note that there are only polynomial many possible values for $t_\beta$. These truth values may repeat; for each truth value $t$, we pick one vertex of that truth value (“live vertex”), and point all other vertices (“shadow vertices”) having the same truth value to that vertex; we won’t add new children to the shadow vertices in the next step.

After $n$ such steps, all the (polynomially many) leaves are labeled by complete truth assignments $\gamma$ to $x_1,\ldots,x_n$. We can evaluate $\psi_\gamma$ directly, and so obtain the real truth values of all live vertices on the $n$’th level, and deduce the real truth values of all shadow vertices on the $n$’th levels. From these we can deduce the real truth values of all live vertices on the $(n-1)$’th levels, and hence of all shadow vertices on that level; and so on. Eventually, we will find the truth value of $\psi$.

Since each level contains only polynomially many vertices, this algorithm runs in polynomial time. It follows that $\mathsf{P}=\mathsf{PSPACE}$.


Minimum capacity cut reduction from digraph with two edge weight sets

This problem is NP-hard.

Consider the $f=0$ case, then you are trying to minimize $-\Sigma_{e\in\delta^-(X)}g(e)$, i.e. maximize $\Sigma_{e\in\delta^-(X)}g(e)$. This is exactly the maximum cut problem, which is NP-hard.


Formally modelling and describing access rights

The Harrison-Ruzzo-Ullman model has this form.  It has principals (e.g., users) and objects (e.g., files), and a matrix that indicates which types of access each principal has for each object.  It also models how the sets of access rights can evolve over time.  It has no notion of hierarchy for principals or objects built into the model, but you could of course regard the set of principals and objects as hierarchical in the way you want -- that's compatible with the HRU model.

The HRU model concerns itself only with semantics: with who has access to what.  It is not concerned with efficiency.

You might also enjoy digging up a textbook that covers this.  The catchphrase you want is the foundations of computer security".  For instance, you might find Matt Bishop's book Computer Security: Art and Science very relevant.


How to minimize the average distance between pumps and cities?

Minimizing the average distance is equivalent to minimizing the sum of the distances, so let me work with that formulation of the problem.

Hint #1: When $k = 1$, the pump should be located at the median of the positions of the cities.

Hint #2: When $k > 1$, you can use a dynamic programming approach.
Let $f(i, j)$ be the optimal cost of serving cities $1,...,i$ with $j$ pumps. Your goal is to compute $f(n, k)$. Now observe that $$ f(n,k) = \min_{i=1,...,n} \left( \sum_{i': i < i' \le n} d(\text{city}_{i'}, \text{pump}_k) + f(i,k-1) \right), $$
because if the rightmost pump (pump number $k$) serves cities $i+1$ through $n$, then the total cost is the sum of distances of those cities to pump $k$, plus the optimal cost of serving cities $1$ through $i$ with $k-1$ pumps. Here $\text{pump}_k$ is the position at the median of cities $i+1,...,n$.


$$
\begin{align*}
x'y' + yz + x'yz' &=
x'y' (z+z') + (x+x')yz +x'yz' &\mbox{(identity)} \\&=
x' y' z  + x' y' z' + xyz + x'yz + x'yz' &\mbox{(distributivity)} \\&=
x' y' z  + x' y' z' + xyz + x'yz + x'yz  + x'yz' &\mbox{(idempotence)} \\&=
x'(y' z + y' z' + y z + y z') + (x+x')yz &\mbox{(distributivity)} \\&=
x'+yz. &\mbox{(identity)}
\end{align*}
$$


First, Wikipedia is wrong in classifying superscalar processors as SIMD (except as many modern superscalars also support short vector instructions). A superscalar has one instruction stream, i.e., there is conceptually only one current instruction address from which instructions are fetched. However, it also has only one data stream, i.e., it generally does not apply the same instruction to multiple data as a vector processor would. (from "Some Computer Organizations and Their Effectiveness" (Michael J. Flynn, 1972): "The single-instruction stream-multiple-data stream (SIMD), which includes most array processes, including Solomon [2] (Illiac IV).")

Pipelining does not increase the number of instruction streams being processed in parallel; the single stream simply flows through a longer channel as it were.

A single processing core can have multiple instruction streams by using multithreading. (Multithreading cores often present this as virtual cores, i.e., to software each thread appears to have a full core, as a convenience for operating systems, allowing any multiprocessor-capable OS to trivially support multithreading. However, this is not a necessary feature; the MIPS MultiThreading Application Specific Extension, e.g., differentiates between a Virtual Processing Element and a Thread Context.)

More interesting cases would included decoupled access/execute architectures, GPUs which provide some instruction stream divergence, and a traditional ISA that internally (microarchitecturally) uses speculative multithreading.

Decoupled access/execute architectures have two partially independent instruction streams, one performing memory accesses and address calculations, the other performing computation, e.g., see James E. Smith, "Decoupled Access/Execute Computer Architectures" (PDF, so they are not neatly classified as having a single instruction stream but they do not have the extent of independent instruction flow associated with Flynn's Multiple Instruction classifications.

Similarly, some GPUs support some control diverge (different instruction streams applied to different data), which is conceptually similar to applying eager execution (where multiple conditional paths are executed in parallel and only the results of the correct path are committed) to multiple data (where at least one of the data elements unconditionally does follow that execution path). This type of architecture is sometimes called Single Program Multiple Thread or Single Instruction stream Multiple Thread. (Note that GPUs also commonly support more traditional MIMD multithreading.)

Hardware speculative multithreading presents the interface of a single instruction stream, but such uses a microarchitecture that supports multiple partially independent instruction streams. For example, loops might have iterations distributed across multiple threads and function calls might spawn a separate thread while processing continues at the return point (possibly using a predicted return value). Like GPUs and decoupled access/execute, this provides limited independence among instruction streams, but even MIMD programs often have limited independence, synchronizing instruction streams at join points. However, unlike those architectures, hardware speculative multithreading provides a SISD interface to software, so from the programmer's perspective it is SISD while from the hardware perspective it is more like MIMD.


Generating all directed acyclic graphs with constraints

For small $n$, the easiest solution might be to download a list of all non-isomorphic graphs and then filter them according to your condition.

You might take a look at Brendan McKay's collection, constructed using geng as part of the Nauty graph isomorphism package.

See Enumerate all non-isomorphic graphs of a certain size for more details and citations.


The Ising Model and Computational Complexity

Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising formulations of many NP problems. The Ising model is also equivalent to unconstrained quadratic binary optimization which also can be used to model a large number of other NP-complete problems, see e.g. A unified modeling and solution framework for combinatorial optimization problems.


Optimize sorting matrix entries by row and column

Option 2: Compare full linear index
  #define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)

Instead of N, use the minimal power of 2 that is not less than N. For example, if N = 10000, use $2^{14}=16348$. So we can have #define COMPARE(ia,ja,ib,jb) ((ia << 14) + ja < (ib << 14) + jb ? -1 : (ia << 14) + ja > (ib << 14) + jb).

Instead of using #define, we can use a function to make sure that long expression is computed only once. forceinline is defined to be the cross-platform forceinline modifier.

#define TWO_EXPONENT 14
forceinline int compare(int ia, int ja, int ib, int jb) {
    int t1 = ((ia - ib) << TWO_EXPONENT) + (ja - jb);
    return (t1 > 0) - (t1 < 0);  //branchless computation
}

You have specified that you need to return 3 values, 1, 0, and -1. That sounds more than enough. You may want to double check if it is enough to use 1 for the case of "not smaller than". That is enough, for example, when we just want to sort an array of numbers.

Just in case you have not noticed, there are a wealth of information on how to store sparse matrix, Google search or Wikipedia entry.


Parikh's Theorem: CFL's "contain" regular languages?

The Parikh image $\Psi$ of a word is a vector counting the number of each of the letters in the alphabet: for example $\Psi( abbabaaca ) = (5,3,1)$ assuming the alphabet is $\{a,b,c\}$.

The Parikh image of a language is the set of Parikh images of the strings in the language: $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \{(n,n,n)\mid n\ge 0 \}$.

The theorem states that the Parikh images of context-free languages are in fact Parikh images of regular languages, as example   $\Psi( \{( ab)^n c^n\mid n\ge 0 \}) = \Psi( (abc)^*) $.

(In a previous edit I had the example  $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \Psi( (abc)^*) $. Technically correct, but the reader will note that language is not context-free.)


There is hardly a good reason to give a return expression a type.

In Benjamin Pierce's book, Types and Programming Languages, he mentions a similar situation: the type of throw expressions. Like return, a throw expression will not produce a value and instead changes the flow of control.

Pierce's comment is that if such expressions is to be given a type at all, a logical choice is ⊥, the "bottom" type. The bottom type is a type, but one which is impossible to instantiate. There are no objects of type ⊥.

This makes perfect sense for expressions that redirect flow in a program. They don't produce a value at all. So to denote this, we say their type is this "uninhabited" ⊥ type. If they did return a value, this would violate the one and only property of ⊥: that there are no values. We would have done the impossible.

If you come from an object oriented background, you might like to think about ⊥ as the "dual" of the Object type. (We sometimes call Object by the name ⊤ in computer science). In a subtype hierarchy, every type is a subtype of ⊤. Dually, ⊥ is a subtype of every other type. This means if I had a value of type ⊥, I can up-cast it


Can deep learning be applied to nonlinear parameter estimation problems?

No.  Deep learning is not useful or relevant here.  Deep learning is for classification.  You don't have a classification task.  Rather, you have an optimization task: find the parameter value $p$ that causes the best match between the given $x$-values and $y$-values.

Deep learning isn't magic sauce that you can apply to anything you might ever think of and expect it to solve your problem.  Your question is an instance of the XY problem.  There may be suitable methods to speed up optimization, but you'll probably need to ask a new question and tell us something about the structure/properties of $f$ and the typical range of values for $n_i$.


I don't know if my solution is correct, but after some searching, I eventually came up to this conclusion:

The algorithm that is used to build the graph is not compatible with a different choice other than $\theta_i = i^{-\alpha}$.

This is because the algo is derived from the  Barabási–Albert with some modifies. We start with N nodes, and we add a link between a couple of nodes every time step until we have added $mN$ edges. First we normalized the weights so they will be the probability that we choose the node $i, \;$  $\sum_{i=1}^{N} i^{-\alpha} \sim \frac{1-\alpha}{N^{1-\alpha}}$. We can easily compute the rate at which the node acquires links, since it will be proportional to its degree:
\begin{equation}
\frac{d\,k_i}{dt} = \frac{k_i}{2mN} =  \frac{1-\alpha}{N^{1-\alpha} i^\alpha},
\end{equation}
this means that we will select the node $i$ with probability $p(i) = k_i ^{-\frac{1}{\alpha}}$. This is equal to the probability that a node has a degree $k>k_i$, so it is related to the cumulative probability distribution:
\begin{equation}
P(k>\bar{k}) \sim k^{-\frac{1}{\alpha}} \rightarrow p(k) \sim k^{-\frac{1}{\alpha} -1} \equiv k^{-\gamma},
\end{equation}
where $\gamma = \frac{1+\alpha}{\alpha}$.
Is this a good answer?


DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion

DPDA for $\mathcal L=\{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

let's try to understand wich words the automata should accept:

$\{\varepsilon,03,13,23,0033,1133,2233,0133,0233,1233,000333,111333,\dots \}\in \mathcal L$

So we can see the "two parts" of the automata, the first part will contain the $0,1,2$ digits and the second part of the automata will contain the $3$ digits, so for the first part we will do a "push" for some $X$ and for the second part we will do a "pop" for $X$, we will accept the word if the stack is empty so in the end we will do a "pop" for some $Z$ that have been in the stack alaready

Try this one, if it is not $100\%$ at least it will lead you to bulid it by yourself

SPOILER:


Mathematical model on which current computers are built

The one closest to typical CPUs is probably the register machine or random access machine (RAM). A RAM has

an infinite number of registers, each of which stores an arbitrarily large number,
a set of operations on these registers (typically $\{+ 1, = 0\}$),
a programming language including these operations as well as control structures for looping/branching (until/if some register holds $0$) and
a program counter pointing to the next operation (in some program).

Real CPUs are quite similar, with some changes:

There are only finitely many registers (which may exist only virtually), and each stores only numbers of bounded size.
There are more operations.

Apart from that, it's very close indeed. It is common to extend the RAM model to account for memory hierarchy, which makes results a lot more applicable.


Maximum length path between any two nodes in a tree with possible negative edge weights

You can find this path in linear time:

If the tree is unrooted, pick an arbitrary node as root.
Traverse the tree in postorder and for each node:

2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.


Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b_j$ denote a cyclic shift of the $j$-th block.

When you need to access $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to insert something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:

Decrement all $b$ values starting from $j$.
Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
Then you fix $j$-th block by rebuilding it from scratch.

This gives you $O(\sqrt{n})$ insertion complexity.


Any proof of correctness of the Toom-Cook algorithm?

If you're only interested in the three-way splitting…

We know that any natural number is a linear combination of powers of ten, where the coefficients are in the range [0,9]. This is our writing system for numbers: the coefficients are simply the digits of the number.

Let's assume that our number has at least six digits (just for simplicity). If it has less than that, we don't need Toom-Cook: $n$ is bounded by a constant, so we can do the multiplication in $O(1)$.

So our number can now be written as $a_0 10^0 + a_1 10^1 + a_2 10^2 + \cdots + a_n 10^n$, where all $a_i$ are single-digit non-negative integers. And $n$ is at least 6.

We also know that we can find $p$ such that $|(n - 2p) - p| \leq 1$. (If $n$ is divisible by 3, then $p = \frac{n}{3}$. If $n-1$ is divisible by 3, then we let $(n-2p)$ be larger by 1. And if $n-2$ is divisible by 3, then we increase $p$ by 1.)

Now, through the laws of multiplication and exponents, it's clear that our number is equal to $(a_0 10^0 + a_1 10^1 + \cdots) + (a_p 10^0 + a_{p+1} 10^1 + \cdots) 10^p + (a_{2p} 10^0 + a_{2p+1} 10^1 + \cdots) 10^{2p}$.

Thus, the number can be divided into three generally-close-to-equal parts, as the paper says.


Yes, your algorithm is correct. The maximum number of edges that a graph can have without forming a cycle is when it is a tree. Lesser number of edges is only when the graph is disconnected. We will assume that the graph is connected, without loss of generality. In such a case, there would be $|V| - 1$ edges in the graph. Any other edge will create one cycle. So, any connected graph with exactly one cycle will have $|V|$ edges.

In such a case, you are right in doing a BFS to color alternatively the nodes alternatively. What you are doing is essentially starting from a root, and all nodes at odd depth have a different color than the root, and all nodes at an even depth have the same color as the root. If you encounter any node which has 2 colored neighbours (parent is always colored, but one of the children is also colored), then you have found a cycle. As you rightly note, if the second vertex is of a different colour than what you planned, it is an even cycle, and you can just go ahead - you will get a 2-coloring. Otherwise, just assign this vertex the third color, and go on with the alternating between two colors for the rest. This gives a 3-coloring.

As for the complexity, you are doing one BFS, checking for colored neighbors while putting them in the queue. Thus, complexity is $O(|V| + |E|)$, as you are visiting every edge and vertex once. However, since $|E| = |V|$, the overall complexity is $O(|V|)$. To color $|V|$ vertices, you need at least $\Omega(|V|)$ time, and so the algorithm is asymptotically optimal (no asymptotically faster algorithm is possible). This algorithm is $\Theta(|V|)$.


Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

MAYBE-MST-C does obtain the minimum spanning tree correctly.
Define a "local MST" as a spanning tree for which any cycle resulting from adding some edge $e$ would not have any edges on the cycle with weight $> w(e)$.
Lemma: The tree $T$ generated by MAYBE-MST-C is a local MST.
Proof:
any edge $e$ that is not already in $T$ at the end of the algorithm must have been removed, and thus it must have been a part of some cycle $c$, and was a maximal-weight edge on that cycle at the time $e$ was removed.
Note the rest of $c - {e}$ could have been deformed after $e$ was removed, but each deformation can only replace an edge $f$ with a longer path consisting of weights that are at most $w(f) \leq w(e)$. Hence, if $e$ were added back into $T$ at the very end and completed some cycle $c'$ that had the final result of all those deformations, $e$ is still guaranteed to be a maximal-weight edge on $c'$.
Main result: MAYBE-MST-C results in a minimal spanning tree.
proof: From the lemma, MAYBE-MST-C results in a local MST, and since local MSTs are minimum, the result immediately follows.


Functional dependencies on relational schema

I assume, by key, you mean the candidate key.

Let's check whether V is a candidate key:

closure(V) = {V, W, X, Y, Z}

Hence, V is a candidate key.

closure(W) = {W, V, X, Y, Z}

Hence, W is also a candidate key.

closure(X) = {X, Y, Z}

closure(Y) = {Y}

closure(Z) = {Z, X, Y}

By checking all the other possible keys, one can see that only V and W are candidate keys.

The lossless-join decomposition of R does not have to be unique.

One can be described as follows:

R = {R1(V, W, X), R2(X, Y, Z)}

Since R1 ⋂ R2 = {X} And X -> {X, Y, Z}.

Hence, X -> R2.

Hence, R1 ⋂ R2 -> R2. Hence, this decomposition is a lossless join decomposition.

R2 can be further divided as
R2 = {R3(X, Y), R4(X, Z)}

Similarly, R1 = {R5(V, W), R6(W, X)}

Hence R = {R5(V, W), R6(W, X), R3(X, Y), R4(X, Z)}


λ -calculus : What is the most efficient in memory representation of functions?

The thing is, there's really not much leeway in terms of function encoding. Here are the main options:

Term rewriting: you store functions as their abstract syntax trees (or some encoding thereof. When you call a function, you manually traverse the syntax tree to replace its parameters with the argument. This is easy, but terribly inefficient in terms of time and space.
Closures: you have some way of representing a function, maybe a syntax tree, more likely machine code. And in these functions, you refer to your arguments by reference in some way. It could be a pointer-offset, it could be an integer or De Bruijn index, it could be a name. Then you represent a function as a closure: the function "instructions" (tree, code, etc.) paired with a data structure containing all free variables of the function. When a function is actually applied, it somehow knows how to look up the free variables in its data structure, using environments, pointer arithmetic, etc.

I'm sure there are other options, but these are the basic ones, and I suspect almost every other option will be a variant of or optimization of the basic closure structure.

So, in terms of performance, closures almost universally perform better than term rewriting. Of the variations, which is better? That depends heavily on your language and architecture, but I suspect the "machine-code with a struct containing free vars" is the most efficient. It has everything the function needs (instructions and values) and nothing more, and calling doesn't end up doing large term traversals.

  I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use

I'm not an expert, but I'm 99% most ML flavours use some variation of the closures I describe, albeit with some optimizations likely. See this for a (possibly out of date) perspective.

Haskell does something a bit more complicated because of lazy evaluation: it uses Spineless Tagless Graph Rewriting.

  and also in the most efficient one that can be achieved.

What is most efficient? There is no implementation that will be most efficient across all inputs, so you get implementations that are efficient on average, but each will excel in different scenarios. So there's no definite ranking of most or least efficient.

There's no magic here. To store a function, you need to store its free values somehow, otherwise you're encoding less information than the function itself has.
Maybe you can optimize away some of the free values with partial evaluation but that's risky for performance, and you have to be careful to ensure that this always halts.

And, maybe you can use some sort of compression, or clever algorithm to gain space efficiency. But then you're either trading time for space, or you're in the situation where you've optimized for some cases and slowed down for others.

You can optimize for the common case, but what the common case is can change on the language, area of application, etc. The type of code that's fast for a video game (number crunching, tight loops with large input) is probably different than what's fast for a compiler (tree traversals, worklists, etc.).

  Bonus point : Is there such encoding that maps function encoded integers to native integers (short, int etc in C). Is it even possible?

No, this is not possible. The problem is that the lambda calculus does not let you introspect terms. When a function takes an argument with the same type as a Church-numeral, it needs to be able to call it, without examining the exact definition of that numeral. That's the thing with Church encodings: the only thing you can do with them is call them, and you can simulate everything useful with this, but not without a cost.

More importantly, the integers occupy every possible binary encoding. So if lambdas were represented as their integers, you'd have no way of representing non-church-numberal lambdas! Or, you'd introduce a flag to denote whether a lambda is a numeral or not, but then any efficiency you want is probably gone out the window.

EDIT: Since writing this, I've become aware of a third option for implementing higher-order functions: defunctionalization. Here, every function call turns into a big switch statement, depending on which lambda abstraction was given as the function. The tradeoff here is that it's a whole program transformation: you can't compile parts separately and then link together this way, since you need to have the complete set of lambda abstractions ahead of time.


Prove a network is a feedforward network if and only if the numbering of its cells satisfy these conditions

One direction (given such a numbering, there are no cycles) is elementary, and I encourage you to work it out on your own. The other direction is topological sorting.


Turing machine that converts decimal to binary

You can play around and try your ideas with this simulator.

Under examples, you can find decimal to binary converter. Furthermore, you can learn about TMs in tutorial section.


Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"

It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of minimum cardinality, not a minimal set.

A set $S$ is called minimal with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.

On the other hand, a set $S$ is said to have minimum size or cardinality with respect to some property if there exists no set $T$ of strictly smaller size (i.e. $|T|< |S|$) that also satisfies this property.

A minimum size set must be minimal (why?), but a minimal set need not be of minimum size (why?).

In the example in the book, the set $\{b,c,d\}$ is not a minimal hitting set, because its strict subset $\{c,d\}$ is also a hitting set. The subset $\{b,d,f\}$ is a minimal hitting set, because it has no strict subset that is a hitting set. It is not a minimum hitting set, because there is a hitting set of size $2$ ($\{c,d\}$).


I had never heard about it before, but taking a quick look at it I can understand why it is considered so important.

Basically, being able to prove that any program can be implemented via three basic operations (sequence, seletion, iteration) allows for simpler formalization when designing a new programming language.

It's basically a one-to-one correspondance to a Turing machine programme, therefore you can easily prove your programming language to be Turing complete.


Is the empty string ε in regular languages implicitly between any two characters in a string?

The empty string is not there between every two characters implicitly but quite explicitly. In fact, there are two empty strings between any two characters, and between those two empty strings there is another, third, empty string. However, since empty strings are empty, them being there is like them not being there at all.

Let's consider this situation from a slightly more general point of view, but without using fancy words. In a sum $1 + 2$ is there a zero in between? Yes, since obviously $1 + 0 + 2 = 1 + 2$, and in fact also $0 + 0 + 1 + 0 + 0 + 0 + 2 + 0 = 1 + 2$, so that's a whole lot of zeroes. Is this sort of thinking useful? Well, in certain situations it is, for instance when we perform algebraic manipulations of numbers.

It might help to write strings as finite lists, i.e., instead of aabab we write $[a, a, b, a, b]$. With this notation the empty string is just $[]$, which is probably less confusing than the Greek letter $\varepsilon$. Concatenation then is actually concatenation (link together in a chain or series, according to my dictionary):
$$[a, a, b][b, a] = [a, a, b, b, a].$$
And now, it makes perfect sense to say that there are empty strings everywhere, like ghosts:
$$[a, a, b][][b, a] = [a, a, b, b, a] = [a, a, b][b, a].$$
Finite automata with silent transitions do not "consume $\varepsilon$". A silent transition happens when no symbol is consumed. You might think that "to consume no symbol" is the same as "to consume the empty string" but that is not so! An automaton (at least of the ordinary kind) consumes one symbol when it makes a transition, or it does not consume anything at all. An empty string is not a symbol, and therefore it cannot be consumed during the transition of an automaton.

More formally, the transition function $\delta$ has the type $S \times \Sigma \to \Sigma$, where $S$ is the set of states and $\Sigma$ is the alphabet. The empty string has type $\Sigma^*$ and so it cannot be an argument to $\delta$. The types don't fit.


Vehicle Routing Problem with multiple deliveries?

It can be reduced to a TSP with an incomplete graph (i.e. with some missing edges). Each delivery "slot" is simply represented as a node in the graph, connected appropriately to the other nodes.


Algorithm to generate a token as survey summary

I think you should try converting your 24-digits (in base 10) number, in another base, which would reduce a lot the length of your token, while keeping the same information.
You should try experimenting with this website for example, which convert in base 36 (10 number + 26 letters):
http://www.unitconversion.org/numbers/base-10-to-base-36-conversion.html
Here, the number 986541236547896541258745 becomes 4GNE5T9XUQO08CKK
I'm sure you can devise an algorithm in base 62 (10 number, 26 lower cases letters, 26 upper cases letters), or event more if you use other characters, such as +-*&"# ... etc
EDIT:
found this website that allows you to convert from and to any bases between 2 and 62:
https://www.dcode.fr/base-n-convert
Here, the number 986541236547896541258745 becomes 4VMCgFPOG10DLH


The easiest way is to take the intersection of your language with $1^*+0=1^*$, which is
$$ \{ 1^n+0=1^n : n \geq 0 \}. $$
A similar option is to intersect with $1^*+1=10^*$, which gives
$$ \{ 1^n+1 = 10^n : n \geq 0 \}. $$
I'll let you finish the argument.


How to present ping data from ICMP timestamp

You ask:

  How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Well, the bottom line is: this data is blatantly wrong.  If your measurement method says that the latency on some link is negative 113 ms, there is something wrong with your measurement method.

Right now, you've got a "garbage in, garbage out" situation.  The data you've got does not survive simple cross-checks, which tells you that your measurement methods has problems.  What you need to do at this point is go back to the drawing board and devise a better measurement method.  For instance, maybe you can find some way to measure the offset between your clock and the remote machine's clock more precisely, and then adjust for that offset.

But in any case, it's pretty clear that the current measurement method isn't adequate on its own.


What does the language {a, b, c}* exactly mean? How will the automaton for this look like?

Any finite words composed of the characters $a,b$ & $c$ and the empty word are part of the language $\{a,b,c\}^*$. The automaton has one state which is the starting and ending state. That state has 3 recursive edges which are reading $a$,$b$ and $c$.


What is "Containment order"? Could I get a friendly explanation?

I'll try a down to earth definition \ example:

When speaking of a set $X$, lets say $X=\{1,...,100\}$,
denote the subset $X_i = \{1,...,i\}$

It holds that $X_1\subseteq X_2\subseteq...\subseteq X_{100}$

So you could say there is a containment order over these subsets, because each subset contains the other in an order that I stated. This order came from, and connected to (and isomorphic to) the partial order of $1 \leq 2 \leq ... \leq 100$ or if you prefer more fomally, that $(X,\leq )$ is a poset.


Finding the interior of a connected graph

If you are given the red pixels, try decomposing the pixels into strongly connected components (SCC), where two pixels are in the same SCC if they are adjacent and neither one is red.  Then each SCC represents a region.  This is a standard technique in computer vision.  Another way to think about this: try using flood fill from each possible starting point.

If you're not given the red pixels: you have a blob finding / segmentation kind of problem.  Try looking at existing methods for block detection.  You should also look at the watershed algorithm for image segmentation.  There are also methods based upon max flow (i.e., minimum graph cuts).

Doing some searches using these keywords will probably find you many more resources.


Maximizing the sum of selected elements in a matrix

The problem you want to solve is (a slight variation of) maximum weighted matching in general (i.e., not necessarily bipartite) graphs.  There are several algorithms with various worst-case bounds:

"Data structures for weighted matching and nearest common ancestors with linking" (Gabow 1990) is the best "in theory" with $O(nm + n^2\log n)$ time complexity.
"Faster scaling algorithms for general graph-matching problems" (Gabow and Tarjan 1991) has time complexity $O(m\log(nN)\sqrt{n\alpha(n, m)\log n})$, where $N$ is the largest cost value and $\alpha(n, m)$ is the very slow-growing "inverse Ackermann" function.
"Computing minimum-weight perfect matchings" (Cooke and Rohe 1999) describes the "Blossom IV" algorithm, which apparently performs well in practice despite a theoretical worst case $O(n^3)$ time.  The paper also gives a good overview of existing algorithms.
"Implementation of $O(nm\log n)$ weighted matchings in general graphs: the power of data structures" (Mehlhorn and Schäfer 2002) apparently performs even better in most cases, and also comes with a better worst-case guarantee.  There is an implementation in LEDA.
"Blossom V: A new implementation of a minimum cost perfect matching algorithm" (Kolmogorov 2009) claims to outperform the previous algorithm a majority of the time.

The above algorithms don't allow "self-edges" (choosing elements along the diagonal).  To accommodate these, for every vertex $v_i$, create an extra vertex $u_i$, and an edge $(v_i, u_i)$ with weight $a_{ii}$.

Note that while some of these papers talk about the maximum weight perfect matching problem, in which we have the additional constraint that every vertex must be incident on an edge in the matching, you can turn any instance of the plain maximum weight matching problem into an instance of the perfect kind by adding, for every existing vertex $v_i$, a new vertex $v'_i$, a zero-cost edge $(v_i, v'_i)$, and another zero-cost edge between every pair ($v'_i, v'_j)$ of new vertices.  (Perhaps another construction using fewer zero-weight edges is possible?)

I found most of the above information in https://people.mpi-inf.mpg.de/~mehlhorn/ftp/WeightedMatchings.pdf, which has a lot of useful information on implementation and theory.


In a Binary Tree, can two nodes have the same value?

If you say "binary tree", my answer is " yes", since binary tree to me only says: A tree of nodes that only have at most 3 edges, of which two (binary) are pointing in the same direction (to tree leafs).

If you mean a "binary search tree", my answer is "no", since a search tree does not have any advantage in allowing duplicates, since SEARCHING for ONE value in a BST can only result in ONE value, not in two or more. Since BST search is a deterministic algorithm, one of the two mentioned duplicates will never be found and hence is totally useless. Inserting a duplicate in a BST must be skipped since its position in tree is already occupied.


Asymptotic analysis with factorial and exponential

Stirling's approximation states that
$$
n! \sim \sqrt{2\pi n} (n/e)^n.
$$
It follows that
$$
n!/2^n \sim \sqrt{2\pi n}(n/2e)^n = \Theta(\sqrt{n}(n/2e)^n).
$$


See Chaitin's research into Omega that shows, as I understand it, that undecidable problems are [paraphrasing] quite numerous, rampant or dense among statements chosen at random. However you have to be careful how you define $U(N)$ and $D(N)$ because they may be actually uncomputable functions. There is also some connections to busy beaver research. Identifying decidable and undecidable statements seems quite analogous to proving that busy beavers halt or do not halt. (e.g. some of all statements are in the form, “busy beaver [x] halts”).


Let me start with the first question. Since $\lfloor x \rfloor \leq x$,
$$
\left\lfloor \frac{\mathit{high}+\mathit{low}}{2} \right\rfloor - \mathit{low} \leq
\frac{\mathit{high}+\mathit{low}}{2} - \mathit{low} \leq
\frac{\mathit{high}-\mathit{low}}{2}.
$$
To complete the proof, we use the inequality $\frac{x}{2} \leq \lfloor \frac{x+1}{2} \rfloor$, which holds for integer $x$. To see this, notice that for even $x = 2y$, the inequality reads $y \leq y$, and for odd $x = 2y+1$, it reads $y+1/2 \leq y+1$.
Now for the second question. We want to know what is the smallest integer $r$ such that $r > \log n$. Since $\lfloor x \rfloor > x-1$, we see that $\lfloor \log n \rfloor + 1 > (\log n - 1) + 1 = \log n$. On the other hand, since $\lfloor x \rfloor \leq x$, we see that $\lfloor \log n \rfloor \leq \log n$, and in particular, it is not the case that $\lfloor \log n \rfloor > \log n$. Therefore $\lfloor \log n \rfloor + 1$ is smallest integer $r$ such that $r > \log n$.


Doubt on Karger's Algorithm for Min-Cuts

The approach is right, however, you are missing a little detail. Karger's algorithm runs on multigraphs. Hence, two vertices can have more than one edge between them and hence, the probability of contracting them the disjoint sum of the probability of contracting any of the edges between them which is the number of edges between them over the total number of edges in the graph.


Why does 9 qubit Shor code have distance 3?

Distance 3 means that an error operator acting on 3 qubits maps a valid code-state to another valid code-state. For the Shor code, an example would be a simultaneous phase flip on the 1st, 4th and 7th qubits ($Z_1Z_4Z_7$).

You can easily check that $Z_1Z_4Z_7∉S$, but that it commute with $S$, hence is part of $N(S)$.


Let $a_i$ be the amortized costs of operation $i$, $c_i$ be the actual costs of operation $i$, and $D_i$ the data structure after operation $i$. The amortized costs of an operation  are defined as
$$a_i:=c_ i+ \Phi(D_i) -\Phi(D_{i-1}).$$
You usually assume the following

The potential is always positive, that is $\forall\colon i \Phi(D_i)\ge 0$,
In the beginning the potential is 0, that is $\Phi(D_0)=0$.

These two assumptions are not always necessary but they are commonly used and make the life easier. Now you can consider the potential at costs that have already been paid by previous operations.

To justify this definition consider the accumulated costs of all operations. We get the following telescoping sum
$$
\sum_{i=1}^n a_i = \sum_{i=1}^n (c_i +\Phi(D_i) -\Phi(D_{i-1})) = \Phi(D_n) -\Phi(D_{0}) + \sum_{i=1}^n c_i \ge \sum_{i=1}^n c_i.
$$
So you see that the sum of the amortized costs exceeds the total actual costs. Hence the amortized costs give an upper bound.

I have not seen the use of the $c$ in your formula. But the $c$ can be simply added to the potential function $\Phi$. So think of the $c$ as a factor that weights the potential, and be redefining the function $\Phi$ you can get rid of it.

So to answer your concrete questions. $a(i)$ denotes the amortized costs for the $i$th operation, that is the actual costs in a sequence of operation charged to operation $i$. The $c$ is some positive factor you can pick. And the $a(i)$s are not constant in general (they are in your example) - you don't have to show anything for the $a(i)$ costs, the values $a(i)$ are the result of your analysis.

Since you seem to speak German, you might also have a look at my German class notes to the potential function.


I wrote some code in Python to solve this problem. Python is designed to be very readable. There is a plaintext explanation of the algorithm below to help you understand what's going on. I am treating the database as an array indexable by its columns and rows.

def find_match(db, input_string):
    if input_string == '':
        return list()
    matches = list()
    length = 0
    for row in db:
        for col in [w1, w2, w3, w4]:
            if len(input_string) == length:
                return list(row[v]) # we found a match!
            if row[col] != input_string[length]:
                length = 0
                break
            length += 1
        if length == 0:
            continue
        if len(input_string) == length:
            return list(row[v]) # we found a match!
        matches.append((length, row[v]))
    matches.sort(reverse=True) # this puts longest matches first
    for length, match in matches:
        solution = find_match(db, input_string[length:])
# input_string[length:] means the input_string from index length till the end.
        if solution != []:
            return list(match) + solution
    return list()

Explanation:

This is a recursive algorithm to match the input. What it does is it loops over all rows in the database and finds all the ones that could be part of a match. If it finds anything that is a complete match, then it returns it immediately (there's no point going any further once you've found a solution.)

Then it sorts this list of potential matches so that the longest ones are evaluated first. It loops through these sorted matches and calls the find_match function using the portion of the input string that still needs to be matched, if that match is the one to be used. In this way, you are evaluating the longest matches first, as you requested.

A step-by-step example (Example 2 from your question):

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

input_string: [A, B, C, D, F]

input_string is not empty, so we construct matches as an empty list. This is the list of rows that could be part of the final solution (they must entirely match the input string from the beginning until they run out of characters)

We loop over the rows, and find the following potential matches:
X1 (A); Y0 (A, B); Y1 (A, B, C)

We add them to the list as a tuple containing their length and the v that corresponds to them. This way we will be able to make sure we check the longest matches first. matches looks like this once we finish iterating over the db:
[(1, X1), (2, Y0), (3, Y1)]

Next we sort the list using the length as the key so the longest matches are first:
[(3, Y1), (2, Y0), (1, X1)]

Now we iterate over the matches, and try to find a solution using each one. Because we are calling the function recursively, it could be a long time between checking each match, depending on the length of the input string that still needs to be matched.

The first row we try to find a solution with is the first element in matches: Y1 (A, B, C). We call find_match(db, [D, F]) using [D, F] as the input string because that is the portion that still needs to be matched if we use Y1 (A, B, C). We can easily find the input string because we have the length (3, in this case) and so we take input_string from its 3rd index on:

A, B, C, D, F
0, 1, 2, 3, 4
X  X  X  D, F

input_string: [D, F]

we loop over the rows and find only one match: X4 (D)

Our list of matches is [(1, X4)], so we call find_match(db, [F])

input_string: [F]

we loop over the rows and find 0 matches, so matches is [] and when we iterate over it, we immediately continue on to the next block of code which tells us to return []. This is our way of saying we didn't find any match.

Now we go back to when input_string was [D, F]. We set solution equal to [], because that's what we just returned. Our only potential match was (X4, D), which we just checked, so now we are done iterating over the potential matches. Because we couldn't find any match with [D, F] as the input string we return [] as well.

Now we go back to when [A, B, C, D, F] was the input string and we had just finished trying to match Y1. We continue iterating over matches ([(3, Y1), (2, Y0), (1, X1)]). We call find_match(db, [C, D, F]) using Y0 (A, B) as the match.

input_string: [C, D, F]

We loop over the rows and we would get X3 (C); Y3 (C, D, F); Y4 (C, D, G) as our matches, but once we find that Y3 (C, D, F) exactly matches the input string, we go ahead and return [Y3]

Now we go back to when [A, B, C, D, F] was the input string and we were just using Y1 (A, B, C) as the match. At this point we see that we did find a match (the function returned [Y3]) and we add Y1 to it so that we have the full match: [Y1, Y3]. We return that and the function is done executing.

In the part of the function that compares the row with the input string, there is a little bit of bounds checking to make sure we only take as many characters from the row as it has, and we don't try to match the input string with a row that is longer than it is, but I didn't bother elaborating on that because it never came up in this example.


Why does linear search have $\frac{n}{2}$ comparisons on average?

Let us assume that required element is equally likely to be in any position between $1$ and $n$. Let $x _i $ be a random variable. Random variable $x_i = 1$ means required element is in ith position and vice-versa. Now probability that required element is in position between $1$ and $n$ is $$ Pr[x_i = 1] = \frac{1}{n}$$ Now Expected value is given by $$\mathbb{E}(x) = 1 \times\frac{1}{n} + 2 \times \frac{1}{n} + 3 \times \frac{1}{n} +\cdots + n \times\frac{1}{n} $$ which can be written as
$$\mathbb{E}(x) =  \frac{n(n+1)}{2n} = \frac{(n+1)}{2}$$
which is a required answer

Reference : https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node56.html


Computing the longest common substring of two strings using suffix arrays

Your algorithm is incorrect. I assume you know how to compute the suffix array and the LCP array of a string, that is, their efficient implementation. As has been pointed out in the comments, you should try to understand what each component is, and why it works.

First of all, is the suffix array ($SA$) of a string. A suffix array is basically all the suffixes of the string $S$ arranged in ascending lexicographic order. More specifically, the value $SA[i]$ indicates that the suffix of $S$ starting from position $SA[i]$ is ranked $i$ in the lexicographic ordering of all suffixes of $S$.

Next is the $LCP$ array. $LCP[i]$ indicates the length of the longest common prefix between the suffixes starting from $SA[i-1]$ and $SA[i]$. That is, it keeps track of the length of the longest common prefix among two consecutive suffixes of $S$ when arranged in lexicographic order.

As an example, consider the string $S = abbabca$. The suffixes in lexicographic order would be $\{a, abbabca, abca, babca, bbabca, bca, ca\}$, so $SA = [7, 1, 4, 3, 2, 5, 6]$ for a 1-indexed array. The $LCP$ array would be $LCP = [-, 1, 2, 0, 1, 1, 0]$.

Now, given two strings $A$ and $B$, we concatenate them as $S = A\#B$, where $\#$ is a character not present in both $A$ and $B$. The reason for choosing such a character is so that when computing the LCP of two suffixes, say $ab\#dabd$ and $abd$, the comparison will break off at the end of the first string (since it only occurs once, two different suffixes will never have it in the same position), and won't "overflow" into the other string.

Now, it can be seen that you should be able to see why you only need to see consecutive values in the $LCP$ array (the argument is based on contradiction and the fact that the suffixes in $SA$ are in lexicographic order). Keep checking the $LCP$ array for the maximum value such that the two suffixes being compared do not belong to the same original string. If they don't belong to the same original string (one begins in $A$ and the other in $B$), then the largest such value is the length of the largest common substring.

As an example, consider $A = abcabc$ and $B = bc$. Then, $S = abcabc\#bc$. Sorted suffixes are $\{abc\#bc, abcabc\#bc, bc, bc\#bc, bcabc\#bc, c, c\#bc, cabc\#bc\}$.
$\begin{align*}
SA &= [4, 1, 8, 5, 2, 9, 6, 3, 7] \\
LCP &= [-, 3, 0, 2, 2, 0, 1, 1, 0]
\end{align*}$

Now, the greatest value is $LCP[2] = 3$, but it is for $SA[1]$ and $SA[2]$, both of which start in the string $A$. So, we ignore that. On the other hand, $LCP[4] = 2$ is for $SA[3]$ (corresponds to the suffix $bc$ of $B$) and $SA[4]$ (corresponding to suffix $bcabc\#bc$ of $A$). So, this is the longest common substring between the two strings. For getting the actual substring, you take a length $2$ (value of the greatest feasible $LCP$) substring starting from either $SA[3]$ or $SA[4]$, which is $bc$.


Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$

Take the log of your ratio to get
$$
c\log\log n - \frac{\log n}{\log\log n} = \frac{c\log^2 m - m}{\log m}, \quad \text{where } m = \log n.
$$
It is not hard to show that this tends to $-\infty$ as $m\to\infty$, and so as $n\to\infty$, which means that your ratio tends to zero as $n\to\infty$.

Indeed, since $c\log^2 m = o(m)$, for large enough $m$ we have $c \log^2 m - m \leq -m/2$. Since $2\log m = o(m)$, it follows that $\frac{m}{2\log m} \to \infty$ and so $\frac{-m}{2\log m} \to -\infty$.


Multi modal learning from separate modal datasets

Back in 2012, this was accomplished by Srivastava and Salakhutdinov in "Learning Representations for Multimodal Data with Deep Belief
Nets" where they mixed textual and visual features using the following Deep Belief network architecture:

Note the specially defined hidden layer that can be trained independently.

More recently in 2015, this was accomplished by Huang, Y.; Wang, W. and Wang, L. in "Unconstrained Multimodal Multi-Label Learning" where they use a conditional Restricted Boltzmann Machine applied to creating text labels for images:

Note that each observed variable, t for tags and m for images are connected to h, but there is the built in assumption that m is more frequently available than t.

One problem with both of these approaches is I'm unclear on how well they're going to scale.


Simulate NPDAs with DTMs using only polynomial overhead

We can combine two known techniques: CYK -which you mention- and the PDA to CFL construction.

Assume that the PDA is in "Chomsky Normal Form": it reads iff it pops, and pushes two symbols otherwise.
Formally, its instructions are of the form

$(p,\varepsilon,A) \mapsto (q,BC)$
$(p,a,A) \mapsto (q,\varepsilon)$

Recall that this can be transformed into CFL using non-terminals of the type $[p,A,r]$, and the productions

$[p,A,r] \to [q,B,s][s,C,r]$ for any "guessed" states $r,s$
$[p,A,q] \to a$

Note that $[p,A,r]$ is a non-terminal that derives all strings using certain computations (see below).

We do not have to explicitly perform the latter construction, but we can build it in the CYK itself, by introducing a table $P(i,j)$ that contains elements that are such triplets. So this would mean $[p,A,r] \in P(i,j)$ iff there is a computation on $w_i\dots w_j$ starting in state $p$ and ending in state $r$ that starts with $A$ on the stack and ends with an empty stack.


Look up Rice's teorem. Its proof is quite short and sweet. It says that any non-trivial property of a TM language (i.e., one that not all TM languages share) is undecidable, in the sense that it can't be decided by looking at the TM if the language it accepts has the property.

The property of being regular (or a context free language, or the empty language, or the language of all strings, or...) is non-trivial, so if a particular TM accepts a language with the property is undecidable, by Rice's theorem.


First, let's unpack this. We say that $O(\sqrt{n}) = \Omega(n^{\sin n})$ if any function $f(n)$ which satisfies $f(n) = O(\sqrt{n})$ also satisfies $f(n) = \Omega(n^{\sin n})$.
In particular, if $O(\sqrt{n}) = \Omega(n^{\sin n})$ then $\sqrt{n} = \Omega(n^{\sin n})$. If $\sqrt{n} = \Omega(n^{\sin n})$ then according to the definition, there exist $C,N>0$ such that $\sqrt{n} \geq Cn^{\sin n}$ for all $n \geq N$. Let us assume that this is the case.
In what follows, I assume that the argument in $\sin n$ is measured in radians.
Since $2\pi$ is irrational, the sequence $n \bmod 2\pi$ is equidistributed in $[0,2\pi)$. In particular, there are infinitely many $n$ such that $n \bmod 2\pi \in (0.4\pi,0.6\pi)$, and so $\sin n \geq 0.95$. For each such $n \geq N$, we have
$$ \sqrt{n} \geq Cn^{\sin n} \geq Cn^{0.95} \Longrightarrow n \leq C^{1/0.45}.$$
Since there are infinitely many $n$ such that $\sin n \geq 0.95$, we can find one such $n$ which exceeds both $N$ and $C^{1/0.45}$, and so reach a contradiction. This shows that $\sqrt{n}$ is not $\Omega(n^{\sin n})$.


What is the time complexity of the following algorithm on graphs

For every $v$, there are $\binom{n-1}{2}$ pairs in the worst case that need to be checked, since $v$ may be connected up to $n-1$ other vertices.

Since $\binom{n-1}{2} = \Theta(n^2)$, your algorithm performs $O(n^2)$ queries for every vertex. Since there are $n$ vertices, the time complexity is $O(n^3)$ and your analysis is correct.

Suppose we want to express the algorithm cost in terms of $m$.

For every $v_i$, we perform work equal to the number of neighbours over 2 of $v$, denoted by $N_i$. Or $\binom{N_i}{2}$

It is clear that the runtime would be $O(N_1(N_1-1) + N_2(N_2-1) +\dots +N_n(N_n-1))$ $$ = O(\sum_{i=1}^n (N_i)(N_i-1)$$

We know that $\sum_{i=1}^n (N_i) = 2m$, since every arc is counted exactly twice. What is left is to prove
$$\sum_{i=1}^n (N_i)(N_i-1) = O(nm)$$

Since $N_i \leq n-1$ it follows:
$$\sum_{i=1}^n (N_i)(N_i-1) \leq \sum_{i=1}^n (N_i)*n = n\sum_{i=1}^n (N_i) = n*2m=O(nm)$$


What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

If I understand the question, your problem is the following:

  Given a regular language $L$ over alphabet $\Sigma$ and a positive integer $n$, compute the probability that a word chosen uniformly at random from $\Sigma^n$ will be in $L$.

That's equivalent to computing $|L \cap \Sigma^n|$, i.e., the cardinality of the language $L \cap \Sigma^n$.  Note that $L \cap \Sigma^n$ is regular, so your problem is equivalent to the problem of counting the number of words in a finite regular language.  This is a standard problem that is well-studied; see https://cstheory.stackexchange.com/q/8200/5038, https://cstheory.stackexchange.com/q/32473/5038, Why isn't it simple to count the number of words in a regular language?, Counting the number of words accepted by an acyclic NFA.  Here are some results:

If the language $L$ is specified as a DFA or as an unambiguous regexp, then the problem can be solved in polynomial time.
If the language $L$ is specified as a NFA and $n$ is specified in unary, the problem is $\#P$-complete.  Thus, there is an exponential-time algorithm but you should not expect a polynomial-time algorithm.
If the language $L$ is specified as a NFA and $n$ is specified in binary, the problem is $PSPACE$-complete.  Thus, you should not expect a polynomial-time algorithm.

There are approximation algorithms that you might be able to use in practice to estimate the probability you're seeking (using a SAT solver as a subroutine).


Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $

It is regular since $a^*(bb)^* \setminus L$ is regular:
$a^*(bb)^*\setminus L = a^* \cup (bb)^* \cup \{a^mb^{2n}|1\leq mn < 3\}$
The last language of the union is finite thus regular.


Using the pumping lemma to prove that a language is context-free

I read How to prove that a language is not context-free? and it has a very detailed example of a demonstration using the pumping lemma. But you are looking for some general understanding of the method so I will tell you the steps I follow when I use pumping lemma to prove that $L$ is not CFL:

1) You suppose that $L$ is CFL. The idea is find a contradiction using the pumping lemma.

2) By pumping lemma exists a constant $N>0$ associated to $L$. Use a generic constant because if you use a fixed one like $N=1$ for example, and don't find a contradiction you have to try with $N=2,3,4,...$.

3) You have to choose a word $\sigma \in L$ such that $|\sigma|\geq N$. You have to use your creativity to choose a word that allows you to easily reach a contradiction in the next steps.

4) By the pumping lemma exists a factorization of your word $\sigma=uvwxy$ and the
following always complies:
$$|vwx|\leq N$$
$$|vx|\geq 1$$
$$\sigma_i=uv^iwx^iy \in L \forall i\in\mathbb{N}_0$$

5) So the next step is to prove that the factorization does not exists. Your job if to check that all possible factorizations in the form $uvwxy$ don't complies with the 3 points of the pumping lemma. This generate a contradiction in your initial assumption then $L$ can't be CFL.

6) If you find a factorization of your particular word this mean nothing! Remember that the pumping lemma says:

If $L$ is CFL $\Rightarrow$ exist a factorization$\dots$

So you have two options at this point. The first is suspect that maybe your language is CFL and try to write a context-free grammar or draw a push-down automaton that denotes $L$. In second option you can assume that the word $\sigma$ was bad pick and try with another word to find a contradiction.

This is the general mechanics of the pumping lemma. I recommend you to try to understand the theory behind it or you will probably make mistakes in your test.

You can't use the pumping lemma to show that a language $L$ is context-free.. If you want to prove that $L$ is CFL the standard way is to write a CFG or draw a PDA like I said before.


Complement of $0^n1^n | n \in \mathbb{N}$

Since $0 \in A$ and $1 \in A$, any word $w \in \Sigma^*$ can be written has a concatenation of $n=|w|$ words $w_1, \dots, w_n$ such that each $w_i \in A$ (showing that $w \in A^*$). In order to do so it suffices to pick $w_i$ as the $i$-th character of $w$, i.e., $w_i$ is either $0$ or $1$.


Copy on write is an interesting idea used on server systems. Does it make any sense on a smartphone?

Yes, copy-on-write makes sense on smartphones, too.  Smartphones are just computers, packaged to be small.  Smartphones run conventional operating systems, with multiple processes.  For instance, each app typically runs in its own process.  And yes, these processes do use shared memory, shared libraries, fork(), etc., so copy-on-write is useful (and is supported on typical smartphone operating systems).


How to show a function is primitive recursive by induction?

Wikipedia gives such an example. You haven't stated the definition of basic functions or basic operations, so I will assume the Wikipedia definition.
The successor function $S(x) = x+1$ is a basic function, and so is assigned 0. Projection functions such as $P_1^1(x) = x$, $P_2^3(x,y,z) = y$ and $P_3^3(x,y,z) = z$ are also assigned 0. The constant function $z(x) = 0$ is also assigned 0.
The function $g(x,y,z) = S(P_2^3(x,y,z)) = y + 1$ is a composition of two functions assigned 0, and so is assigned 1.
Using these functions, we can define a function $h(x,y)$ by primitive recursion: $h(0,y) = P_1^1(y) = y$, and $h(S(x),y) = g(x,h(x,y),y) = h(x,y) + 1$. This function is assigned 2, and you can check that $g(x,y) = x + y$.
The function $r(x,y,z) = h(P_2^3(x,y,z),P_3^3(x,y,z)) = g(y,z) = y + z$ is assigned 3.
We can define a function $k(x,y)$ by primitive recursion: $k(0,y) = z(y) = 0$, and $k(S(x),y) = r(x,k(x,y),y) = k(x,y)+y$. This function is assigned 4, and you can check that $k(x,y) = x\cdot y$.


Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem

You might be  looking for an enum.  See https://en.wikipedia.org/wiki/Enumerated_type.


Create an order from several incomplete orders

I will answer the following question:

  Given a list of partial orders, how can we find a total order compatible with all of them, if any?

Form a directed graph on the ground set by putting an edge $a \to b$ if $a$ immediately precedes $b$ in one of the partial orders. If this graph contains any directed cycles, then there is no solution. Otherwise, we can find a solution by performing a topological sort.


Simple (non-mathematical) definition of polynomial time?

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size.

Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.

For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.


How can we design an efficient divide-and-conquer algorithm for constructing a round-robin tournament?

Hint. Divide the teams into two sections. Every game that needs to be played is either between two teams in the same section, or between teams in different sections. What is the set of games that must be played between teams in the same section?


Do reductions form a total binary relation?

If $A \not \preceq B$ and $B \not \preceq A$ then we say that $A,B$ are incomparable with respect to the order $\preceq$.

As mentioned in the comments, the halting problem and its complement are incomparable with respect to many-one reductions; indeed, one of the reasons behind considering many-one reductions is that they make such distinctions possible.

One can also construct sets $A,B$ which are incomparable with respect to Turing reductions. These are known as incomparable Turing degrees. One way to do it is using diagonalization, as we explain below.

It will be somewhat less confusing to construct Boolean functions $\alpha,\beta$ instead of sets $A,B$. The construction will proceed in infinitely many steps. At step $i$ we will have finite partial functions $\alpha_i,\beta_i$, which extend the functions $\alpha_{i-1},\beta_{i-1}$ from the previous step. Initially, $\alpha_0 = \beta_0$.

At step $2i$, we make sure that the $i$th program cannot compute $\alpha$ given $\beta$. We start by picking the minimal input $x$ not in the support of $\alpha_i$. For each complete function $\beta'$ extending $\beta_i$, we run program $i$ on input $x$ with $\beta'$ as oracle. If none of these runs ever terminates, we set $\alpha_{i+1}(x)$ arbitrarily, and continue to the next step. Otherwise, suppose that program $i$ terminates on input $x$ with $\beta'$ as oracle. Since the program terminates, it only accesses the oracle at a finite number of places. We extend $\beta_i$ to $\beta_{i+1}$ so that it agrees with $\beta'$ on this finite number of places. Finally, we set $\alpha_{i+1}(x)$ to disagree with the output of program $i$ on input $x$ and oracle $\beta'$.

At step $2i+1$ we make sure that the $i$th program cannot compute $\beta$ given $\alpha$, in the same way. Our construction ensures that $\alpha = \bigcup_i \alpha_i$ and $\beta = \bigcup_i \beta_i$ are total functions that correspond to incomparable Turing degrees.


The space hierarchy theorem shows that your classes are different.


Trying to understand this Dynamic Programming solution

We are going to build up the matching with a top-bottom approach. Before proceed your intuition is correct. We need two indexes for our solution, that it would be a recursive function $f$ based on a index $i\in [n]$ and index $j\in[m]$.

This is the definition for $f$.
$$f(i,j):= \text{The optimal* matching between the elements from }\{a_1, a_2, \cdots, a_i \}\text{ with $i$ elements from } \{b_1, b_2, \cdots, b_j\}.$$

The first thing as with other recursive methods, is establish the well-defined bases cases of the recursion. These are the following.
$$
\begin{align}
f(i,1) &= |a_i - b_1|\ \ \ \forall i\in [n]\\
f(1,j) &= \min\ \{\ f(1, j-1),\ |a_1 - b_j|\ \} \ \ \ \forall j\in [m]\\
\end{align}
$$
These are when we have just one element from $B$ and just one element from $A$, respectively.

Thinking like $f$ is working yet as we expected, we can define it as follows with $i\in [n]$ and $j\in [m]$.

$$
f(i,j) = \min \ \begin{cases}
f(i-1, j-1) + |a_i - b_j| & \text{we match $a_i$ with $b_j$}\\
f(i, j-1)&\text{we won't pair $a_i$ with $b_j$}
\end{cases}.
$$

Be aware in the recursion for the corner cases, these are when $f$ is not defined. They are  when $i$ or $j$, or even both are less than or equal to zero, for these cases, we are gonna say, $f(i,j) = \infty$.

So, what is the answer (?). Because, we are using top-bottom approach and based on the definition of $f$, after compute $f(n, m)$, it should give us the answer. Notice, that this way is one of many methods using dynamic programming, and sincerely, it is almost the same as the solution your provided in the link, but here it is just more explicit.

Maybe like a pseudocode, we can do this in Python with the following implementation.

@memo
def f(n, m):
    global a, b
    if m <= 0 or n <= 0:
        return float('inf')
    if n == 1:
        return min(f(1, m - 1), abs(a[0] - b[m - 1]))
    if m == 1:
        return abs(a[n-1] - b[0])
    x = f(n - 1, m - 1) + abs(a[n - 1] - b[m - 1])  # take b_m
    y = f(n, m - 1)  # dont take b_m
    return min(x, y)

print f(len(a), len(b))

My @memo decorator is the following, and is the key of a technique that involved dynamic programing, caching o memoization.
    from functools import wraps
    def memo(func):  # memoization
        cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


Dividing 2 integers with some constraints

Here is a strategy (I will only consider positive numbers):
Let $d$ be the dividend and $x$ be the divisor. Generate all values $x_i = 2^i x$, up to some some $x_k$ such that $x_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x_{0} = x$ and, for $i \ge 1$, $x_i = x_{i-1} + x_{i-1}$.
Similarly, generate all values $b_i = 2^i$ for $i=0, \dots, k$.

Let $r$ be a variable that will hold the result. Initially $r=0$. For $i=k$ down to $0$ do the following:

Check whether $x_i$ is bigger than $d$;
If that is the case, then you know that, by subtracting $x_i$ from $d$, you are effectively subtracting $x$ from $d$ a total of $b_i = 2^i$ times. Update $d = d- x_i$, and $r = r + b_i$.

Finally, return $r$.

This strategy requires only a logarithmic number of operations w.r.t. $d/x$ (up to multiplicative and additive constants). Since this is at most $2^{31}$, the time needed is always upper bounded by a constant.

As an example, let's divide $62$ by $3$.
The sequences of values $x_i$ will be:
$x_0 = 3, x_1 = 6, x_2 = 12, x_3 = 24, x_4 = x_k = 48$, since $x_5 = 96 > 62$.
The corresponding values $b_i$ are: $b_0 = 1, b_1=2, b_2=4, b_3=8, b_4=16$.

Initially $d=62$, $x=3$, $r=0$.
In the fist iteration ($i=k=4$) we have  $62 = d \ge  48 = x_4 $, and we update: $d = 62 - x_4 = 62-48 = 14$, and $r = 0 + b_4 = 0 + 16 = 16$.
In the second iteration ($i=3$) we do nothing since $d = 14 \not\ge 24 = x_3$.
In the third iteration ($i=2$) we have $d = 14 \ge 12 = x_2$, and we update $d = 14 - x_2 = 14 - 12 = 2$, and $r = 16 + b_2 = 16 + 4 = 20$.
In the forth iteration ($i=1$) we do nothing since $d = 2 \not\ge 6 = x_1$.
In the fifth and final iteration ($i=0$) we do nothing since $d = 2 \not\ge 3 = x_0$.

In the end we have $r=20$ and $d=2$. Indeed: $62 = 3 \cdot 20 + 2$.


Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's

I am getting i=5. So is it correct answer?

I am afraid I could not understand your argument and conclusion clearly.

Anyway, can you check if you are able to pump $a^2, a^5, b^{10}, b^{22}$ using the pumping length of your choice?

Here are a few results stated in the form of exercises that you can prove and use to solve the problem in the question and beyond.

Assume $L$ is an arbitrary regular language.
Exercise 1. Show that there exists $p_0=p_0(L)\in \Bbb N^+$ such that $p\in\Bbb N$ is a pumping length for $L$ iff $p\ge p_0$.
We call $p_0$ the minimum pumping length of $L$.

Exercise 2. Let $L_{m,n}=\{a^m, a^{m+n}, a^{m+2n}, \cdots\}$ for $m,n\in\Bbb N$, $0<n$. Show that $p_0(L_{m,n})=m+1$.

Exercise 3. Let $L_1, L_2$ are two regular languages. Show that $p_0(L_1\cup L_2)\le\max(p_0(L_1), p_0(L_2))$

Exercise 4. Let $L_1, L_2$ are two regular languages over disjoint alphabets that do not contain the empty word. Show that $p_0(L_1\cup L_2)=\max(p_0(L_1), p_0(L_2))$

Exercise 5. Show that 11 is the minimum pumping length of $\{x\mid x=a^{2+3k} \text{ or } x=b^{10+12k},\ k\ge0\}$.


Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

$\mathsf{P/Poly} = \bigcup\limits_{k\in\mathbb{N}}\mathsf{SIZE}(n^k)$.

We don't know if every language in $\Sigma_2$ has a polynomial size circuit, but we do know that we cannot have polynomial circuits of bounded degree,i.e. $\mathsf{SIZE}(n^k)$ for some $k\in \mathbb{N}$, for all languages in $\Sigma_2$ (Kannan's theorem).


You can verify that the two expressions are equivalent by using some logical equivalences. Below I'm using 1 to represent true.
$$\begin{align}
a'bc'+a'bc + ab'c'+ab'c &= (a'bc'+a'bc) + (ab'c'+ab'c) &\text{associativity of } +\\
 &= a'b(c'+c) + ab'(c'+c) &\text{distributivity, twice}\\
 &= a'b(1) + ab'(1) &\text{inverse for }+\\
 &= a'b + ab' &\text{identity for }\cdot
\end{align}$$


Proof Check: The class L is closed under concatenation

The idea is correct, but the proof is not finished. It lacks an implementation on the Turing Machine, and sometimes that can be quite tricky. Given a "slice" how are the halves "marked" as belonging to the first and second part, so we can run the two subroutines for $L_1$ and $L_2$? How are the consecutive slices generated?


How to determine if given “complex” time complexity is $O(n^2)$?

Sometimes, you can replace them by $n$. For example, in $F_1(n) = (n+\log(n))\times \sqrt{n+\log n}$, replace $\log(n)$ by $n$. So, $F_1(n) \leqslant 2n \sqrt{2n}$ and it means $F_1(n) = O(n\sqrt{n})$. Also, in multiplication or summation, you can ignore constants (not all the time in power functions). Hence, $F_2(n) = n \times (200 + \log^2(n)) = \Theta(n
\log^2(n))$. Or in $F_3(n) = (7 + n^3) \log(n^5) = 5 \times (7 + n^3) \log(n) = \Theta(n^3 \log(n))$ (as $\log(n^c) = c \log(n)$).


Reduction from a further constrained problem

Hint: An instance of densest $k$-subgraph can be viewed as an instance of your problem, in which sets are vertices and elements are edges.

More generally, to prove that a problem P is NP-hard given that a (seemingly) related problem Q is NP-hard, you need to come up with a polytime reduction from Q to P. If Q is strongly related to P, such a reduction could be easy to find.


Given a precision $ε>0$ you want to compute $f(n,λ)$. When $n≤m$, let $g$ be the error function, that is the difference, between the sum of the $m-1$ first terms and the actual value $f(n,λ)$.

$$g(n,λ,m)=e^{-λ}\sum_{k=m}^n\frac{λ^k}{k!}$$

You want to find a $m$ big enough to have $g(n,λ,m)≤ε$. Then you just have to remark that the following terms are not very big so you can go a little bit further:

$$g(n,λ,m)<e^{-λ}\sum_{k=m}^∞\frac{λ^k}{k!}=h_λ(m)$$

Since the well-known corresponding series converges, $\lim h_λ = 0$. So for all $ε$ and $λ$ you can find a $m_{ε,λ}$ such that $m_{ε,λ}$ steps are enough to compute $f(n,λ)$ with precision $ε$.

Given $ε$ and $λ$ your problem is in $O(1)$.


Is a supercomputer more powerful than the total of all the world's computers in 2004?

No, and not by a long way.

Take 25,000,000 ordinary desktop PCs from 2004.  To exceed the supercomputer you're talking about, each would need an 88megaflop CPU, 40Mb of memory and a 940Mb hard disk. In 2004, CPU clock frequencies were already in the GHz range, RAM in the hundreds of megabytes and hard drives in the gigabyte range. And there were many more than 25,000,000 computers in the USA, let alone the world.


Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices.  So, here is one plausible algorithm you could use:

We are given an existing coloring $C$.  Pick two vertices $v,w$ randomly.  We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph.  If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use).  If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick).  Then extend this to a coloring for the new graph.

If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one.  Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure.  In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$.  Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.

So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once.  On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.


Is there a task that is solvable in polynomial time but not verifiable in polynomial time?

This is only possible if there are many admissible outputs for a given input. I.e., when the relation $R$ is not a function because it violates uniqueness.

For instance, consider this problem:

  Given $n \in \mathbb{N}$ (represented in unary) and a TM $M$, produce another TM $N$ such that $L(M)=L(N)$ and $\# N > n$ (where $\# N$ stands for the encoding (Gödel number) of $N$ into a natural number)

Solving this is trivial: keep adding a few redundant states to the TM $M$, possibly with some dummy transitions between them, until its encoding exceeds $n$. This is a basic repeated application of the Padding Lemma on TMs. This will require $n$ paddings, each of which can add one state, hence it can be done in polynomial time.

On the other hand, given $n,M,N$ it is undecidable to check if $N$ is a correct output for the inputs $n,M$. Indeed, checking $L(M)=L(N)$ is undecidable (apply the Rice theorem), and the constraint $\#N > n$ only discards finitely many $N$s from those. Since we remove a finite amount of elements from an undecidable problem, we still get an undecidable problem.

You can also replace the undecidable property $L(M)=L(N)$ to obtain variations which are still computable but NP hard/complete. E.g. given $n$ (in unary) it is trivial to compute a graph $G$ having a $n$-clique inside. But given $n,G$ it is hard to check whether a $n$-clique exists.


Neighbourhood in local search metaheuristic

I think the property of being able to reach all the successor states from a current state is crucial and needed in order for the problem to be well-defined. If this was not the case, you might miss out on good solutions. Moreover, you might never reach a goal state and hence run forever.

The classic AI book by Russell & Norvig, 3rd edition, page 67 gives a formal definition for a problem. One of the components is a successor function which returns all the successor states for a current state. Together the formal components create a search space, that is the set of all states reachable from the initial state. If one uses a different successor function, namely such that it leaves out some successors, the resulting search space is a different one: goal state(s) might be missing and optimal solutions might very well differ. Perhaps the reason you are unable find it from the literature is that the requirement is obvious.


Consider an adaptive algorithm making $q$ queries. Fixing the randomness, we can describe the positions queried by the algorithm using a function $A$ which gets as input the answers of the preceding queries, and outputs the next position to be queried. If the bits are read from an array $x$, then the adaptive algorithm works as follows:

Read $b_1 = x_{A(\lambda)}$.
Read $b_2 = x_{A(b_1)}$.
Read $b_3 = x_{A(b_1b_2)}$.
...
Read $b_q = x_{A(b_1 b_2 \ldots b_{q-1})}$.

To simulate this non-adaptively, we simply read $x_{A(w)}$ for all words $w$ of length at most $q-1$. Given these $q' = 2^q-1$ non-adaptive queries, we can simulate the adaptive algorithm.


Aggregate Rate and Poisson Process in Aloha

The dictionary definition of aggregate might be helpful: https://www.wordnik.com/words/aggregate

You have $N$ senders.  Each sender sends packets on a network at some rate, say, $\lambda/N$.  Now think about all the packets that are sent over that network, without regard to who sent it.  What's the rate at which such packets appear on the network?  That's a total over all packets.  The aggregate rate will be something like $\lambda$.

It might also be helpful to refresh your understanding of what a rate is.  A rate is an amount divided by a time period: e.g., the number of packets sent by Alice per unit time interval.  The aggregate rate is also a count divided by a time period, but in this case, the count is of a different quantity: it's a count of all packets, not a count of the packets sent by Alice.  So, the number of packets sent (in total, from anyone) per unit time interval is a rate.  That is what your book is calling the aggregate rate.


You run your NTM, and at any point where it could decide between n > 1 actions, it picks an action k and writes k to a tape.
Now you build a TM. It’s identical to the NTM, except at every point where the NTM made a decision, your TM reads a number k from the NTMs successful run, and takes action #k. That’s it.


There is a dichotomy theorem that covers this. For a graph $H$, let $P_H$ be the following problem: On input of graph $G$, decide whether there is a homomorphism from $G$ to $H$. A homomorphism is a function that maps vertices of $G$ to vertices of $H$ in such a way that edges of $G$ are mapped to edges of $H$.

Observe how $5$-colouring is $P_{K_5}$, where $K_5$ is the complete graph with $5$ vertices: The only constraint for a homomorphism to $K_5$ is that the endpoints of edges are mapped to different vertices. Furthermore, careful $5$-colouring is $P_{C_5}$, where $C_5$ is a cycle of length $5$. (To see how that works out, let the vertices of said cycle be in the order $0,2,4,1,3$.)

Now the theorem states that:

If $H$ is bipartite, then $P_H$ is in PTIME.
If $H$ is not bipartite, then $P_H$ is NP-complete.

If you still want a reduction from $5$-colouring, I suggest to look for a suitable gadget. The gadget should be a graph $I$ with two special vertices $v$ and $w$, such that

There is no careful $5$-colouring of $I$ that assigns the same colour to $v$ and $w$.
For all colours $c$ and $d$ such that $c\not=d$, there is a careful $5$-colouring of $I$ that assigns $c$ to $v$ and $d$ to $w$.

Then, for a reduction you would replace every edge with a copy of $I$.

[EDIT]

Wikipedia has the following reference for the dichotomy theorem:

Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110


NP-hard proof with reduction from two known NP-hard problems

If you can reduce one NP-hard problem to a problem $L$, then $L$ is NP-hard. If you can reduce a second NP-hard problem to $L$, then so what? You already know that $L$ is NP-hard. How could reducing more problems to $L$ make $L$ easier (e.g., not NP-hard)?

It's like saying, "If I have one million dollars, I'm rich. If I have two million dollars, am I still rich?"


Yes, the grammar you noww have is still illegal. For CFG you can only have two types of productions $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables) and $a$ terminal.

It is best to add additional variables that introduce the brackets $A\to ($ and $B\to )$.
Now you can use $S\to AB$ instead of your production $S\to ()$.

Finally, try to get rid of $S\to (S)$. It is too long and contains both terminals and nonterminals on the right side.