Do we have to calculate time for declaring statement in RAM model?

There is no standard answer, so you'll have to go by whatever convention is used in your course.


What does it mean for a problem to be both NP hard and coNP hard

A language $L$ is NP-hard if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

A language $L$ is coNP-hard if for every language $R$ in coNP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

If a language is both NP-hard and coNP-hard then its exact complexity lies above both NP and coNP. Indeed, it is conjectured that NP$\neq$coNP, and this implies that a problem which is both NP-hard and coNP-hard belongs to neither NP nor coNP.

Problems which are both NP-hard and coNP-hard do exist. For example, any PSPACE-complete problem is both NP-hard and coNP-hard.


Search algorithm that returns the lowest cost path to one, of many possible goal nodes?

Yes, any of the standard search algorithms will do that.

You seem to be under the misapprehension that search algorithms stop "when they reach node $x$." They don't: they stop when they reach a node with any property you tell them to use. That property could be "node $x$", or "any node in $x_1, \dots, x_k$", or "any node with score more than $10$" or any other condition you choose.


You can use a Sparse-Table for these type of queries.

Most implementations/tutorials on Sparse-Tables don't actually cover/support the usecase of adding new values (actually I've never seen one before), however it shouldn't be too hard to modify a typical implementation. You basically only need to invert what each entry stores.

Normally a sparse table stores the following things for each element at position $i$. It stores the minimum of the range $[i, i+1)$, the minimum of the interval $[i, i+2)$, the minimum of of the range $[i, i+4)$, the minimum of the interval $[i, i+8)$, and so forth.

This is a problem when you want to append a new value, because it will affect at least one range for each element, so adding a new element is $O(n)$.

However if you point the ranges in the opposite direction, you do better. So for each element at position $i$, you store the minimum of the ranges $(i-1, i]$, $(i-2, i]$, $(i-4, i]$, and so forth. You can still do the answer minimum queries in $O(1)$, but now if you add a new element at the end, you only need to recompute $O(\log n)$ ranges, namely the new ones for the new element. You don't need to modify the other entries.

One thing that you additionally should take into care. Whenever your array gets gets bigger than a power of 2, you need to compute a new range for each element (in $O(n)$ time). But that's still amortized $O(\log n)$.

edit: Actually, now that I think about it more, this $O(n)$ recomputation can be avoided. Notice, that a those new ranges $(i-2^{\log n + 1}, i]$ will contain exactly the same values as the previous ranges $(i-2^{\log n}, i]$. Therefore you can always just lookup the largest range $(i-2^j, i]$ if you want to want to know the range $(i-2^k, i]$ with $k \ge j$. Then adding a new element works in true $O(\log n)$ time, and not just in amortized time.


What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions

I believe this can be solved in $O(nm)$ time using dynamic programming:
$$\begin{align*}
B[i,k] &= A[i,k] + \dots + A[i,k+r-1] + C[i,r]\\
C[i,k] &= \max(A[i,k] + C[i,k+1], \max_{i'} B[i',k])
\end{align*}$$
Note that you can compute $A[i,k] + \dots + A[i,k+r-1]$ in $O(1)$ time as the difference of two prefix sums (assuming you have done a one-time precomputation to compute all prefix-sums).
The answer is then $\max_i B[i,1]$.  Computing it takes $O(nm)$ time, as there are $O(nm)$ entries to fill in, and each one takes $O(1)$ time to fill in, using the equations above.
Interpretation:

$B[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k=i$ and $i_k,\dots,i_m$ satisfy the repetition rule

$C[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k,\dots,i_m$ satisfy the repetition rule except that if $i_k=i$, the run starting at $i_k$ can be of any length (but all subsequent runs must be at least $r$ long).  In other words,
$$C[i,k] = \max_\ell A[i,k] + \dots + A[i,k+\ell-1] + \max_{i'} B[i',k+\ell]$$

Generally, this is not the kind of thing I would expect to find papers about.  I would expect to see a one-sentence "can be solved by dynamic programming", possibly with an explanation of the max-trick above to reduce the running time from $O(nmr)$ to $O(nm)$, but not an entire paper about it.  So I would not bet on such a paper existing.  But I could be wrong.  It's certainly possible there could be such a paper.  I would not know how to go about looking for it.


I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular

You should notice that if the conditions hold, the language can be regular (necessary, but not sufficient). However, you proved the third condition is not held in your case, hence it is not regular which this is not true. Therefore, your proof is not correct.

On the other hand, if we suppose $x = a$ and $y = a^{3}$ and $z = 3n-4$ we can say $xy^nz$ is in $L$ for all $n\geq1$ ($p = 4$). Hence, we can't proof $L$ is not regular by pumping lemma.


Tree decomposition - Fastest algorithm in practise

The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.


Does the Halting Problem prove that true Artificial Intelligence is impossible?

If we cannot determine from program description whether it halts we also cannot write algorithm to do so (otherwise we could have determined it from description).
The ability to think and reason like humans is not connected to the halting problem, and the separate problem here is that we do not fully know how people think, so we cannot copy this idea, we are prone to emotions and logic just fails. If you want to create "true Artificial Intelligence" you would have to unlock any restrictions, constraints, let it evolve and think differently otherwise your AI is at the best case clone of you and it will not be self-concious or thinking just ultra advanced processing unit.

If tou like to think about the true AI - human limits are not applicable because if we proved something cannot be done - it is not doable under any circumstances, but if we do not know how to do something (yet) - there is no constraint neither for human nor for the true AI.


Is the existence of an oracle such that $P^O = NP^O$ nontrivial?

The existence of an oracle with respect to which $\mathsf{P} = \mathsf{NP}$ shows that $\mathsf{P} \neq \mathsf{NP}$ cannot be proved using techniques that relativize such as diagonalization. In contrast, the time and space hierarchy theorems do relativize, disproving your claim that any two complexity classes are equal relative to some oracle.

The easy observation that $\mathsf{P}^\mathsf{R} = \mathsf{EXP}^\mathsf{R}$ seems to contradict the fact that the time hierarchy theorem relativizes. Tthe definition of $\mathsf{X}^\mathsf{R}$ that you use is $$ \mathsf{X}^\mathsf{R} = \bigcup_{A \in \mathsf{R}} \mathsf{X}^A.$$
The time hierarchy theorem shows that $\mathsf{P}^A \neq \mathsf{EXP}^A$ for every language $A$, but not for every family of languages.

The oracle with respect to which $\mathsf{P} = \mathsf{NP}$ is a single language. One possible choice is any $\mathsf{PSPACE}$-complete language. This is very similar to using an arbitrary recursive language, with a crucial difference – there are languages in $\mathsf{PSPACE}$ which are complete with respect to polynomial time reductions.


Terminology: Difference between decision variables, features and attributes?

Feature and attribute have both the same meaning.

Decision variable is the variable which is used to make a split in a decision tree in tree based algorithms, i.e. the variable on which the decision is made.


How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I think I found a good way to prove $p(n) = \Omega(n^k)$:

We want to show that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

We know $\lim_{n\to\infty} p(n)/n^k = a_{k}$

This gives us some intuition to choose $c \leq a_{k}$.

Let $c = a_{k}/2$

Now choose $n_{0}$ such that $cn^k = (a_{k}/2)n^k \leq p(n)\ \forall{n \geq n_{0}}$.

or rearranging, $(a_{k}/2)n^k \geq -\sum\limits_{i=0}^{k-1} a_{i}n^i\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n^k \geq \sum\limits_{i=0}^{k-1} |a_{i}|n^i\ \forall{n \geq n_{0}}$

or $(a_{k}/2)n^k \geq n^{k-1}\sum\limits_{i=0}^{k-1} |a_{i}|n^{i-(k-1)}\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n \geq \sum\limits_{i=0}^{k-1} |a_{i}|\ \forall{n \geq n_{0}}$ since $n^{i-(k-1)} \leq 1$

Hence pick $n_{0} = 2/a_{k}\sum\limits_{i=0}^{k-1} |a_{i}|$

We now have a $c$ and $n_{0}$ such that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

Hence proved.


Counting number of states from a regular expression

The rule for the $\sigma\in \Sigma$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $a$ in $ab$ for the circuit that recognizes $a$ in $a + \epsilon$.

So you have five letters that appear in $r$, that's $5*2$ states. Then you have 2 concatenations, two unions and two stars. That's $2 * 0 + 2*2+2*2 = 4*2$ states.


Can there exist more than one optimal solution in a dynamic programming problem?

Yes, but it's implicit in the dynamic programming table.

The dynamic programming table starts by filling out objective values for trivial sub-solutions, then combining them to obtain the optimum objective value by the time the final entry is reached. The central part to emphasise here is that the dynamic programming table has objective values as its entries, rather than the sub-solutions themselves (although you may hang on to all sorts of information to help the computation of course). So the way you obtain the actual solution from a dynamic programming table is to trace back from the final entry reconstructing the steps taken to get there.

Then if there's multiple ways to get there, in the tracing you just run into situations where you can go more than one way. If you were only interested in obtaining some solution, you just pick a route. If you want all of them, you exhaustively explored all routes back through the table.


How on-chip multithreading prevents cache misses from stalling a processor pipeline?

It's called "out of order execution".

When one instruction stalls, that doesn't mean the whole pipeline stalls. All instructions that don't depend on this one instruction can continue. Sometimes there is enough work to do even with a single thread to keep all the execution units busy even if one instruction stalls for 40 cycles. But with hyperthreading, you have a whole thread whose instructions are all independent of the stalling instruction, and which can all continue executing.


Motivation for Inverse Reinforcement Learning

Often the transition model is not known in advance.  For instance, consider a complex system like flying a helicopter or surfing a surfboard.  It's not easy to characterize in advance what the behavior of the system will be, in response to certain control inputs; the relationship may be highly nonlinear and complex.


Given a set of numbers, get the maximum 10 number average below a certain threshold

Looking for a maximum average $m$ below a threshold $m_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s_{max}$. If you have to select $k = 10$ numbers among $N$, you have:

$s_{max} = k \times m_{max}$

now the question looks like a Knapsack problem with a forced number of selected items $k$. You can use a DP solution closed to the one solving Knapsack. I also assume $s_{max} > 0$ and all available numbers are strictly positives. Note, that you may apply a simple offset on all numbers and $m_{max}$ if any is negative.

Let's build a $k\times s_{max}$ array $A$ with $A[i, j]$, the index of the last number selected to have $i$ selected values for a total of $j$. $A$ is initially filled with an "null" value.

Then the pseudo algorithm is:

for n from 1 to N:
    v = n-th available value
    for i from k-1 to 1:
        for j from smax-v to 1:
            if A[i, j] is not null and A[i+1, j+v] is null then:
                A[i+1, j+v] = n
    if A[1, v] is null:
        A[1, v] = n

The best sum you can obtain is the last $A[k, j]$ which is not null. Using the index in $A$, you can backtrack the subset. Note that $i$ and $j$ loops go backward, to be sure the same value is not used twice.

Complexity is $O(Nks_{max})$ in time and $O(ks_{max})$ in space.

If $s_{max}$ is large and $N$ quite small, a (key, value) structure (in fact $k$ of these structures) instead of $A$ may be much more efficient as you won't have to loop on all empty values.


Is there a "natural" undecidable language?

Since you wanted "strings", I mention the classic one: Post Correspondence Problem.


Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{p!+p}$ (Ogden's lemma allows us to pump some $b^q c^q$ for $q\leq p$, and $q|p!$ since $q \leq p$.) Similarly, we can get the same word by pumping $a^p b^p c^{p!+p}$. The two parse trees are different since in the first one most of the $b$s are "closely related" (in terms of least common ancestor) to $c$s, and in the second one it is the other way around.


Does applying a homomorphism to the intersection of two CSLs yield RE languages?

This follows from closure properties of CSL: it's closed against intersection and $\epsilon$-free homomorphism, but not against (general) homomorphism.

Thus, $h(L_1 \cap L_2)$ is always context-sensitive if $h$ is $\epsilon$-free.

If $h$ is not, $h(L_1 \cap L_2)$ may not be. As an example, take $L_1$ and $h$ from the proof that CSL is not closed against general homomorphism, and $L_2 = \Sigma^*$.

Since CSL $\subseteq$ RE and RE is closed against intersection as well as (general) homomorphism, $h(L_1 \cap L_2)$ is indeed always in RE.


What are some problems in the class P which we used to think were in the class of NP?

Consider the following problem $A$: given $n$, is $n$ a composite integer (i.e., not a prime)?

It is easy to prove that $A$ is in NP: any nontrivial divisor acts as a certificate.

Proving that $A$ is also in P is much harder, and it is equivalent to proving that its complement, i.e. primality, is in P as well. Still, this has now been proved.


Understanding the geometrical interpretation of word2vec

If two words tend to appear in the same context, then they will tend to receive a similar word vector.

For instance, a large corpus might contain sentences like "I really love Fuji apples" and "I really love Gala apples".  From this we can see that "Fuji" and "Gala" have appeared with the same context (in this case the context is "love _ apples", if by context we look one word to the left and one word to the right).  This will tend to cause the optimization algorithm to assign Fuji and Gala vectors that are similar.

As you can see, words that tend to be associated with the same surrounding context will often have a similar semantic content.  Not always, but it's a good heuristic.


Efficiently finding the intersections of sets that yield a desired set

Your problem is equivalent to enumerating all inclusion-minimal set covers, a problem addressed here.

Suppose that you're looking for all collections of sets whose intersection is some set $T$. All the relevant sets must contain $T$, so you can just consider all sets containing $T$, and remove $T$ from all of them. This reduces to the case $T = \emptyset$.

Now let $U$ be the union of all sets. The intersection of a collection of sets is empty iff the union of their complements is $U$. In other words, if you complement all sets, then you're interested in inclusion-minimal set covers.


The problem is $NP$-complete by reduction from $3$-SAT. In the reduction, the goal will be to have at least one vertex of each labeled class left.

For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this gadget, which is not connected to anything else but allows us to conserve one vertex of the opposite color class.

For every clause with $3$ literals, we create a clique on $3$ vertices (corresponding to the $3$ literals), each with unique colors. We must delete all but one of the vertices from this gadget, and the vertex which is not deleted signifies which literal causes the clause to be satisfied. We create two further copies of this gadget, which are not connected to anything else but (similarly to the variable gadgets) allow us to conserve vertices of the unused color classes.

We now connect every vertex whose preservation denotes making a true (resp. false) assignment to a variable to the literals which are incompatible with that assignment.

For a clause with $2$ literals we do the same, except with $2$ (instead of $3$) cliques on $2$ (instead of $3$) vertices.


Is Mersenne primality testing necessarily EXPTIME?

Nothing is impossible. But the problem is that you might want to check whether a 10 million digit number is a prime, but that number is just 2 raised to an 8 digit power, minus 1, so the problem size would be just 8.

For random 10 million digit numbers, the problem size is 10 million. For 10 million digit Mersenne numbers, the problem size is just 8. You can't even write down that number in polynomial time in the problem size. You can't even write it in base 2 in polynomial time, where the number is just a huge string of 1's.


Can quantum computing help solve NP-Complete problems?

BQP (the quantum analog of BPP) is closed under polynomial time reductions, so if some NP-complete problem is in BQP, then all NP-complete problems are in BQP. For more arguments, check this Quora question or that Quora question.


Proving satisfiability using resolution and variable elimination

If $x_7$ is a pure literal, then this means that you can satisfy all clauses containing $x_7$ by setting it to true. Accordingly, we set $x_7,x_5,x_6,x_8$ to true, satisfying all clauses apart from $\lnot x_2 \lor \lnot x_3 \lor x_4$, which we can satisfy by setting $x_4$ to true (for example).
If you set $x_4,x_5,x_6,x_7,x_8$ to true, then the left-hand side of your original formula is satisfied (once you correct $x_1 \lor x_2$ to $x_1 \lor x_2 \lor x_6$ and $\lnot x_5 \lor \lnot x_6$ to $x_5 \lor \lnot x_6$), while the right-hand side is falsified, and so the entailment is false. (In contrast to your post, there is no "formula" there which can be satisfied or not.)


How can I check constraints on my state machine behaviour?

Use a model checker.  This is exactly what they're good for.  You might look at SPIN and NuSMV as a starting point, but there are many others as well.


Find candidate keys given functional dependencies

Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the following one:

{ A B C → D
  A B C → F
  D E F → A
  D E F → C
  D → B }

From these dependencies we can see that E must belong to all the candidate keys, since it does not appear in any right part.

We can start now from the left hand parts of the dependencies to see if their closure contains all the attributes:

ABC+ = ABCDF

by adding E (that must be present in every candidate key) we discover the first candidate key, since ABCE+ = ABCDEF.

Then from DEF:

DEF+ = ACBDEF

so this is already a candidate key.

Finally, starting from  D we found that:

D+ = DB

trying again to add E, we find:

DE+ = BDE

we can now try to add A:

ADE+ = ABDE

which is still not a candidate key, and finally adding C we find the last candidate key:

ACDE+ = ABCDEF


Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

If $n\lt k$, we have $T_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$.
One of the recurrence relations is,
$$\quad  T_k(n) =6+T_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$
where $6$ comes from $2T_k(2)$, since $T_k(2)=3$.
Applying the recurrence relation above repeatedly, we have
$$\begin{align}
T_k(n)&=6\cdot 1+T_{k-1}(n-2\cdot1)\\
&=6\cdot 2+T_{k-1}(n-2\cdot2)\\
&=\cdots\\
&=6\cdot (p-1)+T_{k-(p-1)}(n-2\cdot (p-1))\\
&=6\cdot p+T_{k-p}(n-2\cdot p)\\
(\text{let us apply } T_k(n)=2n-1)\quad&=6\cdot p+2(n-2\cdot p)-1\\
\end{align}$$
if we can choose $p$ such that

$n-2(p-1)\ge k-(p-1)\ge\dfrac{n-2(p-1)+3}2$,
which ensures all equalities except the last one hold, and
$n-2p<k-p$,
which ensures the last equality holds.

Solving $p$ for those inequalities, we find that $p= n-k+1$.
$$T_k(n)=6\cdot p+2(n-2\cdot p)-1=4n-2k+1$$

So, we have
$$T_k(n) =\begin{cases}
  2n-1, & n<k \\
  4n-2k+1, & n \geq k
\end{cases}$$
It is easy to check that $n\le T_k(n)<4n$, so $T_k(n)=\Theta(n)$.

"How can I show that the boundary case of $k=3$ can be within $\Theta(n)$?"
What is the situation when $k=3$ under the assumption $k\ge\dfrac{n+3}2$? That means $n\le3$. So that situation is rather irrelevant since we are interested in the asymptotic behavior of $T_k(n)$.


What is the worst-case big-O time complexity for this code?

You need to be aware that the complexity of insert and pop can be $O(n)$ in python ($n = \text{length($L$)}$). Hence, the time complexity can be $O(n^2)$.


How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?

I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. Lomuto divides the array into three parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into two parts; elements smaller than the pivot, elements equal to or greater than the pivot. One of the traps that I fell into was that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition returns the position just before the final position of the pivot. This is why Lomuto then quick sorts from lo to p-1, whereas Hoare quick sorts from lo to p. Another inference that can be drawn is that if Hoare's partition returned i instead of j, we'd then divide the array into two parts- from lo to i-1 and from i+1 to hi, just like Lomuto did. And it only took me 4 hours to understand that.


This "kind" of computer is known as a Zeno Machine. Its computational model falls into a category called Hypercomputation. Hypercomputational models are mathematical abstractions, and because of the ways in which they are defined to work, they aren't physically possible.

Take your Zeno Machine for example. If we imagine the Zeno Machine to be a calculating machine of any kind, whether it uses an abacus or integrated circuit doesn't matter. Say the program data used by the machine is fed to it by an infinitely long tape of symbols (just like a Turing Machine).

Of course, we know from mathematics that:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n $

which we say is equal to $1$. Thus the computation should complete in 1 second because the sum absolutely converges.

But this convergence is, of course,  dependent on $n$ going to (and reaching) infinity. In the physical sense, this means that as the time required for each calculation gets smaller, the "read head" of the calculating machine will have to zip along the symbols in the tape faster and faster. At some point, this speed will exceed the speed of light.

So answering your second question, the absolute lowest-possible bound on a calculation would probably be on the order of the Planck time, given the speed of light as the primary limiting factor in theoretical, but physically-plausible models of computation.


Why is a set of attributes X not a key if X → Y holds but there exists a strict subset V of X where V → Y?

Generally, you want to define a key as a superkey that is minimal with respect to inclusion; if $X$ is a superkey, $V$ is a superkey and $V \subset X$, then $X$ can't be minimal.

The intuitive idea behind the definition is that we don't want keys to contain "useless" attributes. For instance, imagine a table that contains a list of people, each of which has a unique number $K$, a name $N$ and a surname $S$. $K$ would be a key to that table, because it functionally determines all other attributes in the relation. The pair of attributes $\{K, S\}$ also functionally determines the entire relation, but attribute $S$ is "useless" in that respect, because it is itself determined by $K$.


An obvious approach to NP = coNP, is there a counterexample?

It is not known whether NP=coNP or NP≠coNP, but the latter is strongly suspected. It is not even known whether P≠NP implies NP≠coNP.

It is known that NP≠coNP implies P≠NP, and this approach for proving P≠NP is known as "Cook's program".

Now to your particular proof system. As far as I understand, your proof system maintains a collection of DNFs, which are initially the clauses of the original CNF (so they are trivial DNFs in the sense that all terms have width 1). At each step, you take two DNFs and combine them to a new DNF.

This system is similar to "depth-2 Frege", which is the following system. You start with "axioms" which are the clauses of the original CNF that you are trying to refute. The proof consists of a sequence of "lines" (propositions), each one either an axiom or following from previous lines via one or more derivation rules. In addition, all the lines are constrained to be formulas of depth 2 (CNFs or DNFs). The exact choice of derivation rules doesn't matter - fix any finite set of derivation rules of your choice.

It seems that one can simulate your proof system using depth-2 Frege in such a way that the number of lines in the Frege proof is comparable to the size of your proof. To know for sure, one needs to examine the exact simplification rules that you use, and show how to simulate them using depth-2 Frege. I believe that this should work out.

The pigeonhole principle is hard not only for Resolution, but also for bounded depth Frege. In particular, refuting the pigeonhole principle using depth-2 Frege takes $2^{n^{\Omega(1)}}$ lines, where $n$ can be taken as the size of the formula. See for example Fu and Urquhart.


If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences

Assuming a monolithic kernel like Linux, there just are no "kernel programs", every in-kernel thread is just a function running in the kernel's address space. If you copy that and place it in a userland program (given the correct environment in terms of available data structures and functions to call) it will work fine as long as it doesn't invoke any privileged operations. Any of those will give some sort of exception.
Placing a userland program into the kernel would mean to add a lot of infrastructure provided by the operating system: in C's terms, standard input and output, the contents of the standard C library and any others in use. Using a snippet of userland code in the kernel will work just fine, as long as any infrastructure/environment called upon is provided.
Kernel code and userland code are the exact same instructions (but the kernel has access to some privileged operations and registers that userland can't use).


Indistinguishability of exponentially close distributions

Here is the key. Let $A \otimes B$ be the distribution corresponding to a sample from $A$ and an independent sample from $B$, and denote total variation distance by $d_{TV}$. Then
$$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$
We can see this using the $L_1$ formula for $d_{TV}$:
\begin{align}
d_{TV}(A_1\otimes A_2,B_1\otimes B_2) &=
\frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &\leq
\frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[A_2=x_2]| \\ &+
\frac{1}{2} \sum_{x_1,x_2} |\Pr[B_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &=
\frac{1}{2} \sum_{x_2} \Pr[A_2=x_2] \sum_{x_1} |\Pr[A_1=x_1] - \Pr[B_1=x_1]| \\ &+
\frac{1}{2} \sum_{x_1} \Pr[B_1=x_1] \sum_{x_2} |\Pr[A_2=x_2] - \Pr[B_2=x_2]| \\ &=
\sum_{x_2} \Pr[A_2=x_2] d_{TV}(A_1,B_1) + \sum_{x_1} \Pr[B_1=x_1] d_{TV}(A_2,B_2) \\ &=
d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2).
\end{align}
Now let $D^{\otimes n}$ denote $n$ independent samples from $D$. The above inequality shows that
$$
d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).
$$
Let $E$ be the event that your algorithm outputs "$D_1$". The definition of $d_{TV}$ guarantees that
$$
|\Pr_{D_1^{\otimes m}}[E] - \Pr_{D_2^{\otimes m}}[E]| \leq d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).
$$
Here $\Pr_D$ denotes that the samples in the algorithm are generated from the distribution $D$.
We deduce that an algorithm with advantage $\delta$ must use at least $\delta/d_{TV}(D_1,D_2)$ samples.


Is there such thing as "sequential types"?

The seminal paper on this topic is Linear Types Can Change the World! by Phil Wadler.
Of course, with a title like that, you know it has to be a Wadler paper. It's a pun, the implication being that linear/uniqueness type system allows you to represent operations which mutate the world state.
You can use linear types today in languages such as Clean. See, for example, Aachen et al, High Level Specification of I/O in Functional Languages.
In logic languages, you can do the same thing with strong modes rather than strong types, such as in Mercury. (Full disclosure: I'm one of the original Mercury developers.) See Fergus Henderson's honours thesis, Strong Modes can Change the World!
EDIT
I think I may have misinterpreted the question, which I thought was about types for imperative code.
The answer to your question is "yes, absolutely". There is a tradeoff between types and programs. At one end of the spectrum, you have a completely dynamic type system, where every program has the same type. At the other end, you have a hyper-static type system, where every type only has one program that is of that type, with the type essentially encoding the program.
In the middle ground, there are many programming languages whose type systems are Turing-complete, including Haskell, Java, TypeScript, and Rust.


Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

Proof:
Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma.
So let p the pumping number.
Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$.
Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},0<=k<p$ and because $ a^{2p-k}\neq b^p$ it follows that the pumped $w$ is not  in $L$. Which is a contradiction. Therefore $L$ is not regular.
$\tag*{$\blacksquare$}$


Edit distance of list with unique elements

TL;DR: A slightly more restrictive kind of edit distance, in which we can only insert and delete individual characters, can be computed in linearithmic time when both (or even just one) of the strings have unique characters.  This gives useful upper and lower bounds on the Levenshtein edit distance.

Insert/delete edit distance, and longest common subsequences

Levenshtein edit distance allows single-character insertions, deletions and substitutions, assigning each a cost of 1.  If we restrict to just insertions and deletions, we get a similar distance measure that now causes substitutions to have a cost of 2 (since any substitution can be mimicked using an insertion and a deletion).  I don't know a standard name for this more restrictive kind of edit distance, so I'll call it "insert/delete edit distance".  It corresponds closely to the longest common subsequence (LCS) problem, in which we are given two strings, of length $m$ and $n$, respectively, and want to know the length of the longest subsequence that appears in both.  If two strings have LCS $L$, then they have insert/delete edit distance $n+m-2L$: the easiest way to see this is to align the strings so that characters in the LCS appear stacked on top of each other, while characters not in the LCS appear opposite a - gap character.  It will then be apparent that we can edit the first string into the second by making an insertion wherever there is a - in the top row, and a deletion wherever there is a - in the bottom row.  For example:

-C-IRC-LE
T-RI-CKLE

Here the LCS of CIRCLE and TRICKLE, ICLE, has length 4, and the edit distance is indeed $6+7-2*4=5$.

Longest increasing subsequences

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$.  Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters.  We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table.  Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.).  Finally, we look for a longest increasing subsequence in B.  This corresponds to a LCS between A and B, and from there we can immediately calculate the insert/delete edit distance.  The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

Bounds on Levenshtein edit distance

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the insert/delete distance is also a valid sequence of Levenshtein edit operations).  Dividing the insert/delete edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 insert/delete edit operations.

Generalisations

Already in 1977, Hunt and Szymanski came up with an algorithm that can be viewed as a generalisation of the longest increasing subsequence algorithm.  It is efficient whenever the number of pairs of matching character positions between the two strings is small.  If there are $r$ such pairs, their algorithm takes $O((r + n)\log n)$ time.  (Notice that $r \le n$ if all characters in one string are distinct.)  This algorithm was the basis of the original diff program, which treated entire lines of text as individual characters.  diff later switched to using Myers's $O(nd)$-time algorithm, where $d$ is the insert/delete edit distance, as this performs better when overall differences are small but some "characters" (text lines) appear frequently (such as a line containing just an opening brace in C program code).

  Hunt, J.; Szymanski, T. (1977), "A fast algorithm for computing longest common subsequences", Communications of the ACM, 20 (5): 350–353, doi:10.1145/359581.359603


Join of recursively enumerable set and its complement

The operation you described in actually the join operator in the semilattice of Turing degrees, defined as $A\sqcup B=\{0x | x\in A\}\cup \{1x | x\in B\}$. It is not hard to show that $A,B\le_T A\sqcup B$, thus if $A\in RE\setminus R$ then $\overline{A}\notin RE$ and thus $A\sqcup\overline{A}\notin RE$.


Why must uncommitted transactions be undone in backwards order?

Original transactions:

Insert record $r$.
Update some field $f$ of $r$.

Forward undo:

Delete record $r$.
Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.


How is the environment designed for testing a reinforcement learning algorithm?

In reinforcement learning, the "environment" is typically a set of states the "agent" is attempting to influence via its choice of "actions".

For example, in "Reinforcement learning design for cancer clinical trials" by Zhao, Kosorok, and Zeng (2009),

  ..."states" may represent individual patient covariates and "actions" can
  be denoted by various treatments or dose levels.

More abstractly, in "A brief introduction to reinforcement learning" by Murphy (1998),

  The environment is a modeled as a stochastic finite state machine with inputs (actions sent from the agent) and outputs (observations and rewards sent to the agent).

So, the "structure of the environment," what signals are relevant, and how they interact is highly specific to the problem you're trying to solve, as is the choice of where to draw the boundary between the agent and the environment.

In "Reinforcement Learning: an Overview", Sutton and Barto (1998), give an overview of the Agent-Environment interface and note:

  The agent-environment boundary can be located at different places for
  different purposes. ... In practice, the agent-environment boundary is
  determined once one has selected particular states, actions, and
  rewards, and thus has identified a specific decision-making task of
  interest.

"Reinforcement Learning: A Survey" by Kaelbling, Littman, and Moore (1996) also provides an overview of the problem.


Why the Smallest Operable Data Type in Most Programming Languages Is One-Byte Sized?

Most instruction sets contain instructions that modify a single byte, but not instruction that modify a single bit and so higher level languages tend to reflect that.

Though modern high level languages include what is effectively a bit type, called boolean. Usually, it can only take two value (true or false), but a boolean requires a whole byte for storage.

If you need to store many bits, what you can do is to use a specialized data structure, which internally uses bytes or integers for storage (and so it stores 8 or more bits in a single underlying element). Such data structures include std::vector<bool> in C++ and BitArray in .Net.


@tonny,
     I am also found this example from a book, I think the number 6 is missed after the number 40 in the example. The correct order is 10, 22, 20, 2, 40, 6 and 38.
So if it starts from cylinder 20,
You can write it as, -> (20), 10, 22, 2, 40, 6, 38
                     -> (20-10)+(10-22)+(22-2)+(2-40)+(40-6)+(6-38)
                     ->  10+12+20+38+34+32
                     -> 146.
So seek time is = 146*6
                  876 ms.


Thanks to j_random_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem:

We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered as columns $\{v_1,\dots,v_{N_1}\}$ and edges ordered as rows $\{e_1,\dots,e_{N_2}\}$.
We'll construct rectangles on this grid (the drawing below will help a lot understanding the different rectangles used)

For each vertex, we create a rectangle of type 1, which covers the central column of the column of blocks corresponding to that vertex, so we have $|V|$ rectangles of type 1.

Each block correspond to a unique couple $(e_i,v_j)$, with $e_i=(v_a,v_b)$ for each block we add a rectangle of type 2 :

if $j<a$ or $b<j$, this is a 3-by-3 rectangle covering the entire block.
if $j=a$ (resp. $j=b$), this is a 3-by-1 rectangle covering of the left (resp. right) column of the block.
if $a<j<b$, this is a 1-by-3 rectangle covering the top row of the block.

So we have $|E||V|$ rectangles of type 2, those rectangles will be obligatory to choose, as each will be the only cover for the top-left (or top-right) corner of the block it's in.

As we have said, each edge correspond to a row, with two blocks (let's call them endblocks) corresponding to the endpoints of the vertices $(e_i,v_a)$ and $(e_i,v_b)$, now we have rectangles of type 3:

for endblock $(e_i,v_a)$ (resp. $(e_i,v_b)$), we have a 1-by-2 rectangle covering the top-right (resp. top-left) corner of the endblock.

We have $2|E|$ rectangles of type 3, and again, they're obligatory as each will be the only cover for the top-right corner (if it's the first endblock) or the top-left corner (if it's the second endblock) it's in.

Now, for each edge we construct rectangles of type 4, between the endblocks, we have two rectangles for the second row :

One going from the central square of the first block to the central-left square of the second block.
One going from the central-right square of the first block to the central square of the second block.
And the same two rectangles for the third row.

We have $4|E|$ rectangles of type 4, those are not all obligatory however.

So now, to cover the grid:

$|E|(|V|+2)$ rectangles (type 2 and 3) are obligatory and $|V|+4|E|$ (type 1 and 4) are optionnal.

To cover, for a given edge, the part between the edge endblocks not yet covered (second and third rows of the row of blocks), we can either use:

the four rectangle of type 4.
one rectangle of type 1 and two rectangles of type 4.

Note that in any case, we need at least two rectangles of type 4.

So here the cost function will be : $|E|(|V|+4) + k$

If their is a valid vertex cover with less than k vertex:  we use the $|E|(|V|+2)$ obligatory rectangles, then for the optionnal rectangles, we can use the rectangles of type 1 corresponding of the vertex cover, and for every row, we need only 2 rectangles of type 4 (we already have a rectangle of type 1). So if the graph has a valid vertex cover, the grid has a valid set cover.
If we have a valid set cover for the grid (with less than $|E|(|V|+4) + k$) rectangles, then for each edge, either we already have a rectangle of type 1 (and the edge is "covered") or four rectangle of type 4, in which case, we can replace two of them by one rectangle of type 1, and we still have a valid cover with $|E|(|V|+4) + k$ rectangles. By iterating this process, we reach a valid solution with no row using four rectangle of type 4, from which we can obtain a valid vertex cover.

So the vertex cover can be reduced to the grid cover. And the grid problem instance can be encoded by $|E|(|V|+6) + |V|$ covers on a grid with $9|V||E|$ elements, so the reduction is polynomial and the grid problem is NPC.

PS :
I noticed after writing this answer that a lot of rectangles are actually useless and much simpler reduction can be made using a $|E|$-by-$3|V|$ grid with $|V|+4|E|$ covers, using cost function $3|E|+k$


Show that if Automata $A$ recognize language $L$, there also exists an automata $A′$ that recognize $Double(L)$

You said you showed this result using regular expressions. Take the idea you used then and apply it to automata. You assume you're given an automaton $A$ for the language $L$. You need to construct an automaton $A'$ which accepts all and only the strings in $D(L)$.

Here's a hint to get you started: if you have a rule in $A$ of the form $\delta(p, a) = q$, meaning that in state $p$, seeing input $a$, you go to state $q$, how would you modify that rule so that from state $p$, seeing $a$ and $a$ again, will go to state $q$? Perhaps you might introduce another state along the way from $p$ to $q$?


Algorithm to get maximal selection set of a collection of sets with a binary relation

Your problem generalizes MAX-CLIQUE, and as such its decision version is NP-complete. To see this, given a graph $G=(V,E)$, take $I=V$, $A_i=V$, and $R=E$.


Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.

This problem is actually #P-hard wich is believed to be strictly harder than NP.

The version of the problem where you only look for the existence of such a path is called the longest path problem. A well-known problem in theory. It is fixed-parameter tractable when parameterized by the length of the path (check Parameterized Algorithms book by Cygan et al for description and methods).


Find sets of weighted objects to maximize number of sets with weight >= X

This problem is NP-hard as it can be seen by a reduction from $3$-partition.
In the $3$-partition problem we are given a (multi-)set $\mathcal{S}$ containing $3n$ positive integers $x_1, \dots, x_{3n}$ and the goal is that of deciding whether there exists a partition of $\mathcal{S}$ into $n$ sets $S_1, \dots, S_n$ of $3$ elements each, such that, for each $i$, $\sum_{x \in S_i} x = T$, where $T = \frac{1}{n} \sum_{i=1}^{3n} x_i$.
It is known that this problem remains NP-hard even when each $x_i$ is strictly between $T/4$ and $T/2$. We will therefore restrict to such instances.
To obtain an instance of your problem, it suffices to use the same set of integers $\{ x_1, \dots, x_{3n} \}$ (i.e., $N=3n$) with $X = T$.
Clearly, since the sum of any two input elements can be at most $2 \cdot (\frac{T}{2}-1) < T = X$, we have that, in any partition $\mathcal{P}$ of $\{ x_1, \dots, x_{3n} \}$, the number of sets $S \in \mathcal{P}$  such that $\sum_{x \in S} x \ge X$ can be at most $N/3 = n$.
If the answer to the 3-partition instance is "yes", then the same partition $S_1, \dots, S_n$ exactly matches this upper bound in the instance of your problem.
On the other hand, if the answer to the 3-partition instance is "no", then in any partition of $\{ x_1, \dots, x_{3n} \}$ there is at most one set with sum smaller than $T$, i.e., there are at most $n-1$ sets with sum at least $T$.
To summarize: the answer to the instance of $3$-partition is yes if and only if the optimal solution to the corresponding instance of your problem has measure at least $n$.
Your problem is not NP-complete since it does not belong to NP (since it is not a decision problem). Unless P=NP there is no efficient (polynomial-time) algorithm for your problem.


Why is a program with only atomics in SC-DRF but not in HRF-direct?

Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF."  That's incorrect.

They do say that "[in] scoped synchronization ... it is possible to write a racey program that is composed entirely of atomics if those atomics do not use scopes correctly," [top of page 2], which is slightly different (and uses the word "racey" ambiguously, perhaps leading you to believe they meant the incorrect statement.)  They perhaps should have instead said said that in scoped synchronization it is possible to write a non sequentially consistent program that is composed entirely of atomics if those atomics do not use scopes correctly.

SC-DRF (roughly: the memory semantics for C++ and Java) divide memory locations into two classes, synchronization objects, (sometimes called atomics), and data objects.  For the most part  all operations on synchronization objects are guaranteed to be sequentially consistent.[1]  (Not race free.)  This is a constraint on the compiler, not the programmer.  It says that if the programmer says that one thread writes atomic object a then writes atomic object b, all the threads will see the writes occur in this order.  (The compiler is not allowed to reorder the accesses, and is required to insert the appropriate memory barriers and fences on machines that aren't sequentially consistent.)

Sequentially consistent means that all threads on all processors agree on a total order of all memory operations.  If one thread thinks that operation $x$ happened before operation $y$, all the threads think that operation $x$ happened before operation $y$.
Sequentially consistent does not mean not racey and it does not mean deterministic.  For example, two different threads could try to write the same synchronization variable at approximately the same time.  These accesses will be racey.  A sequentially consistent system will just guarantee that if one thread thinks that write $x$ happened before write $y$, all the threads will agree that write $x$ happened before write $y$.  Sequential consistency is useful because you can use it to construct and reason about useful non-deterministic synchronization objects like mutexes and condition variables.

SC-DRF then says that if your program is data race free, the operations on data objects will appear to be sequentially consistent.  The compiler is permitted to reorder (or even sometimes eliminate) operations on data objects, and if the underlying machine is not sequentially consistent, the compiler is not required to insert memory barriers or fences.  But the compiler is not allowed to reorder operations on data objects with respect to operations on synchronization objects.

Data race free is not the same as race free.  And sequentially consistent is not the same as race free.  A particular program execution schedule is data race free if for any pair of data object accesses, $x$ and $y$, by two different threads (at least one of which is a write operation) we can use the (sequentially consistent) order of atomic object accesses to prove that either $x$ happened before $y$ or $y$ happened before $x$.  If we can not do the proof then that execution schedule is data racey.

A program is data race free if all possible execution schedules are data race free.  A program is data racey if there is an execution schedule that is data racey.

Being data race free is a constraint on the programmer, not the compiler.  It says that if your program is data racey, then your program has no semantics.  The compiler is allowed to do anything it wants, including halting the program, going into an infinite loop, or blowing up the computer.

Oh dear.  TL; DR!  I haven't even mentioned SC-for-HRC yet!

In SC-for-HRC the atomics need to specify what scope they belong to.  Atomic accesses are guaranteed (by the compiler) to be sequentially consistent only within their own scope.  All threads within the scope will agree about the order in which the atomic accesses occur, but threads in a different scope may not agree (and may not even be able to see the accesses at all, let alone their order.)

For example it might be the case that all the GPU threads agree that thread 19 acquired mutex A then acquired mutex B, but all the CPU threads do not agree (or know) that thread 19 acquired mutex A or mutex B at all.  SC-DRF does not have "scopes" so doesn't suffer this problem.

[1] The exceptions to the sequentially consistent atomics have to do with explicitly using std::memory_order_relaxed.  So don't do that.  (And I'll ignore the exceptions in the rest of what I'm saying.)


Solving recurrences by substitution method: why can I introduce new constants?

I am guessing that the book wants you to proof the stronger hypothesis $T(n) \leq c\log( n -d)$ which implies $T(n) \leq c log(n)$ is also true ( because $n \geq n -d$ for $d\geq 0$. )


Show that kleene plus language is a regular language by describing how you build a DFA or NFA for it

You can use Thompson's construction. It constructs NFA with $\epsilon$ moves. But remove the forward $\epsilon$-transition from the new start state into the new final state since you are interested in $L^+$ and not in $L^*$.

NFA with $\epsilon$ moves is a generalization of NFA and DFA. But you can systematically transform any NFA with $\epsilon$ moves into equivalent NFA without $\epsilon$ moves and DFA. Look here for more.


How to get the upper, lower and average bound of a given algorithm?

When we talk of best case, worst case, and average case, it is in the context of algorithms whose running time depends on the input and not just on its length. If the algorithm always runs in time $n\log n + 2$, then the best case, worst case, and average case are all the same.

For a non-trivial example, consider quicksort. Quicksort always runs in time $O(n^2)$, and there is a sequence of arrays, one of each length, on which quicksort runs in time $\Theta(n^2)$. Therefore the worst case running time of quicksort is $\Theta(n^2)$. The best case running time varies according to the implementation – it can be $\Theta(n\log n)$ or $\Theta(n)$.

What about average case? Whenever we talk about average case, we need to introduce a distribution, according to which the average is taken. For sorting, the standard distribution is a random permutation of $1,\ldots,n$. The average case running time of quicksort, with respect to this distribution, is $\Theta(n\log n)$.

In other words, even though there are some arrays which are "difficult" or "bad" for quicksort, causing it to have quadratic running time, on "most" arrays it behaves much better, having a linearithmic running time. The running time depends not only on the length of the input array, but also on its order. This causes the discrepancy between worst case and average case for quicksort, and for many other (though not all) sorting algorithms.


Is busy beaver the fastest growing function known to man?

The busy beaver function grows faster than any computable function. However, it can be computed by a Turing machine which has been given access to an oracle for solving the halting problem. You can then define a "second order" busy beaver function, that grows faster than any function that can be computed even by any Turing machine with an oracle for the halting problem. You can keep doing this forever, building up a hierarchy of ever faster growing busy beaver functions.

See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.


Lower bound for number of nonterminals in a CFG

You need at least two non-terminals here. For suppose not. A rule of the form $S \to \alpha$ cannot include two copies of $S$, since otherwise it would generate a word of the form $\cdots b \cdots a \cdots$ (since $S$ generates $b,a$). A rule of the form $S \to x S y$ (where $x,y$ are words) cannot mention the letter $b$ for similar reasons. The only rules mentioning $b$ are thus of the form $S \to w$ (where $w$ is a word). It follows that every word generated by the grammar has a bounded number of $b$s (since at most one rule of the form $S \to w$ can be applied when generating a given word), so it doesn't generate all of $a^*b^*c^*$.

In contrast, you can generate the language using two non-terminals: $S \to aS|Sc|B$, $B \to Bb|\epsilon$. Therefore the minimum number of non-terminals needed to generate this language is two.


Weighted graph clustering with maximum size constraint

I can't think of an exact algorithm and don't know if an efficient one exists. But if you're ok with heuristics and approximate solutions you could try the following:
Find an initial solution:
Repeat the following until every vertex is assigned to a cluster:
Pick a vertex u belonging to no cluster and create a new cluster C = {u0}. Grow a minimum weight tree from {u0} using Prim's algorithm (using only vertices assigned to no cluster) with a cost function corresponding to:
C[v] = minimum over (u=neighbour of v in C) of -value((u,v))/weight(v)

(you just have to adapt the cost update function of any efficient Prim implementation)
Stop when the weight of your Tree starts getting too big.
That's just an idea. You could also try to start with any random assignment of clusters which agrees with the weight constraint.
Perform local optimizations:
Pick a vertex v and see if you can gain value by moving it to another cluster by computing the sum of values of the edges you gain minus the sum of the edges you loose. Pick the cluster which maximizes this sum, among the ones which are possible (i.e, weight(C) + weight(v) <= n). You can repeat that as long as you like or as long as the solution is improving, choosing the vertices in some order or randomly.
If this doesn't work well enough, you can allow to sometimes perform swaps which make your solution momentarily worse in order to get out of a local minimum, using something like Simulated annealing or Tabu Search.


Is complexity of $GI_{di}$ same as $GI_{un}$?

The Wikipedia page mentions that digraph isomorphism is GI-complete, and gives a reference. For the proof, something along the following lines should work. Replace each $u\to v$ edges with a path $u\to x\to y\to v$, and attack a clique of size $A$ to $x$, and a clique of size $B \neq A$ to $y$. Choose $A,B > n$ to ensure to these are the only cliques of that size. Instead of a clique you can have a long path or a large star.


Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$

First, let me mention that $O(n)$ and $O(cn)$ are exactly the same thing. What you are really after is showing that $T(n) \leq cn$ for all $n$.

Let us aim at a slightly more relaxed goal: showing that $T(n) \leq An$ for some possibly larger constant $A$. For the base case, we need $A \geq c$. For the inductive step, we know that
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \leq A(n/2+n/4+n/8)+1 = (\tfrac{7}{8}A+1)n.
$$
Recall that our goal is to deduce that $T(n) \leq An$. This would follow if $\tfrac{7}{8}A + 1 \leq A$, that is, if $A \geq 8$.

In total, if we take $A = \max(c,8)$ then both the base case and the inductive step go through.

As an aside, you can also use the Akra-Bazzi theorem to directly conclude that $T(n) = O(n)$.

Now let us try to obtain more insight on the recurrence. Let $S(n) = 8n - T(n)$. Then
$$
S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + 8n - 8\lfloor n/2 \rfloor - 8\lfloor n/4 \rfloor - 8\lfloor n/8 \rfloor - n.
$$
Since $8(n/a-1) < 8\lfloor n/a \rfloor \leq 8(n/a)$, we see that
$$
S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + r(n),
$$
where $0 \leq r(n) < 24$. Applying the Akra-Bazzi theorem, we get $S(n) = O(n^p)$ for some $p < 1$ (the solution to $(1/2)^p + (1/4)^p + (1/8)^p = 1$), and so $T(n) = 8n + O(n^p)$.


Are syntax and semantic just 2 structures such that one is a model of the other?

I am afraid the phrasing of the question misled me (though I did know
better) in first seeing model theory as applying to any two arbitrary
mathematical structures, and being the study of homomorphisms of
mathematical structures.

Actually this is wrong. Model Theory already contains the idea of
syntax and semantics, more or less as I define it below. It studies
theories, which are sets of sentences in a formal language, and
models which are interpretation of these sentences in abstract
mathematical structures. This is close to what I call language
below, and I guess this is also close to what the author of the question calls
language.

So the proper answer to the question is that even model theory has a
concept of syntax and semantics, where syntax is a theory, i.e. a
formal representation structure such as a universal algebra, and
semantics is an interpretation (i.e. a morphism) in some abstract
mathematical domain.

Hence the "duality syntax/semantic" is already present in model
theory. There is nothing new on that side.

However, what may make a difference is the understanding of the word
language, as it could be interpreted as going beyond what is usually
concerned by the syntactic algebras usually addressed by model theory.

Actually, the question does not define the word language, and it could
be formal languages, programming languages, natural languages, with
some unsaid understanding of what is intended.

So two possible answers could be:

model theory is the study of languages with their syntax and
semantics, and there is nothing to add, or
a language can be defined by an arbitrary syntactic definition
(meaning a computable structure) and a homomorphic(?) mapping in
some abstract mathematical structure. The question mark is because
I fear that the definition of the mapping may raise some issues.

The second view is possibly less formal, or less constrained. Whatever
the case, I am leaving below my initial answer (which corresponds to
the second view), since several of the issues it is addressing may
still be relevant and of interest to computer scientist, even though
the presentation may be debatable from the point of view of model
theory.

It does not bring anything new from a formal point of view, since the study of formal system that are considered in syntax already had to go all the way to Turing computability, in order to address the Entscheidungsproblem, and that is as far as we may hope to go in terms of syntax.
I may however help understanding some more practical issues.

Your comments are welcome, including suggestions to erase my former, more naive, though possibly more intuitive, answer.

The first section is the direct answer to the question. The other two
sections may be skipped. They are attempts to explore some examples or consequences, or some practical
aspects encountered by computer scientists, in particular in the
design of programming languages.

Syntax, semantics and languages

The view of the issue as expressed in the question is mainly "OK". My
main criticism though is that the reference to the concept of
language is critical, because directly related to the concept of
syntax, not separable from the concept of syntax.

As a consequence, there is something circular, kind of tautological,
about your statement. The question is why do we use this specific
terminology of "syntax and semantics" for some models, for some
homomorphically related pairs of structures, and not for others. Where
is the difference? And a correlated question is: what is a language?

Clearly there is no restriction on semantics: any topic/structure can
be the object/content of a discourse. Hence, the fundamental
distinction is to be looked for on the syntax side. My own
understanding is that what distinguishes such a homomorphic pair is
the domain of the homomorphism: the syntax structure has to be concrete and
concretely manipulatable. Basically a syntactic structure is a
finite collection of concrete objects, usually idealized as symbols,
and a finitely defined collection of rules to compose in diverse ways any unboundedly
finite number of copies of these symbols, and to transform such
compositions into others compositions. The word syntax comes from
'Ancient Greek: σύνταξις "coordination" from σύν syn, "together,"
and τάξις táxis, "an ordering"'.

Fundamentally, syntax is physical. The concept of symbol is only a
mean to abstract away the choice of physical instanciation of the
symbols as objects such as sounds, gestures, glyphs, objects, stones
(which gave us the word calculus), electric or magnetic state,
presence and absence of a signal, etc., or composition of other
symbols.

Hence, the theory of syntax is essentially what is better known as the
theory of computation, which is the study of rule based manipulation
of symbols. Whatever we express, transmit, receive, compute, memorize,
analyze, is processed through some syntactic symbolic representation.

But what we are interested in is not the symbolic representations, but
some semantic concepts or objects (possibly themselves physical) that are
intended to be represented by the symbolic compositions at hand. And
the correspondence is defined by the semantic homomorphism into its
semantic codomain.

Then, in the most general acceptation of the word, a language is the
association of a syntax structure and a semantic structure through a
homomorphic mapping. Or to state it in the terms of the question, it
is a pair of structures such that one is a model of the other, with
the additional requirement that the latter be a syntactic structure.
But, in order to give such a definition, you must first define what
is a syntactic structure. And that definition stands on its own,
independently of the concepts of language or semantics: Syntax
is the study of finitely defined manipulations (including transmission
and memorization) of unboundedly finite compositions of copies of a
finite set of symbols. Ot in simpler terms, syntax concerns the
definition, analysis and manipulation of representations.  You may
read computation theory and information theory.

This is in agreement with the concept of homomorphism: the meaning of
the whole is derived from the meaning of the parts. But this is a
meta-remark. I insist less on defining semantics since it seems that
any structure (that makes sense?) can play that role.

Further remarks

I do not know if the view of linguists on natural language is exactly
the same, or as precise regarding the homomorphic relation, but it
should not be too far from it. The concepts of syntax and semantics
arose from language analysis and logic, which I assume were the same
topic at some point in history (actually diverging pretty late, in the
19th century according to Wikipedia page on syntax). Still, it seems
that some modern linguists follow somewhat similar views "since they regard syntax to be the study of an abstract formal system".

The point is that most mathematical domains, abstract concepts, and
other objects of discourse generally elude us, and can only be
contemplated and dealt with through mechanisms to represent them and
(some of) theirs values, i.e. through syntactic representation. In its
simplest form, it can be a pointing finger to represent a direction.

The main characteristic of a syntactic domain is that it is a concrete
representation, finitely defined through some formal system such as
the formal languages dear to computer scientists. But these syntactic
domains, which are very precisely the domain of computation, i.e. of
syntactic transformations, are very limited, as we learn from the
study of computability. For example, they are denumerable, while many
abstract domains we are interested in are not denumerable.

As a consequence, it is often the case that syntax can only represent
a small part of the mathematical domains we study. This is typically
the case for real numbers, almost all of which do not have a (finite)
syntactic representation, the others being the computable reals.

Choosing a data structure to represent the values of some abstract
domain we wish to compute with is just finding an appropriate syntax,
for your semantic problem, whether to express some conceptual semantic
derivation (computation) or to have simpler relation with semantics (semantic morphism),
or to optimize some aspect of communication and memorization
(space. speed, reliability).

For users who want an example, computing the sum of XXVII and XCII, I
mean 11011 and 1011100, is just a manipulation of the digits to get the
representation of a number (119) that is the sum of the numbers
represented by the initial two representations. The positional
notation happens to be easier to manipulate, to be more economical in
space (number and variety of symbols), and to have a simpler way to
express the homomorphism. The syntax changes, the semantics is the
same, and in both correspond to languages to express natural numbers
(well, not quite for Roman numerals).

IMHO (but some of this may be a matter of individual perspective), if
syntax should be only what can be represented and manipulated,
semantics can be any mathematical domain, or more generally any
abstract domain of discourse, including the domains used for
syntax. Hence you can have a theory of syntax where you study
syntactic representation systems. Formal language theory is nothing
else.

Note that the the idea of a syntac-semantic duality should not
induce the idea that there is some sort of symmetry between syntax and
semantics.

Syntax and semantics in computer science practice

It is true that we often pretend to address semantic issues, for
example when defining formally the semantics of a programming language
$L$. But that may be seen as an abuse. What we really do is use a standard
language $S$ that is supposed to have an accepted semantics and define
the semantics of $L$ in terms of the semantics of $S$. The difficulty
is that we can never access semantics directly, but only through some
syntactic proxy, even when the semantics is itself syntactic in
nature. This is why we use metalanguages such as Backus-Naur Form (BNF).

There are however various mathematical techniques to define semantic
domains. Among these techniques, you have the definition of syntactic
models where the syntax (possibly up to quotient by some equivalence
relation) is its own model. Actually, one of the major contribution of
Dana Scott to computer science was to conceive non-syntactic models of
lambda-calculus which is (initially at least) a purely syntactic theory (see for example
Continuation Models for the Lambda Calculus With Constructors,
B. Petit (2012).

A characteristic of most mathematical theories is that they may have
many models, including non-standard models. "A non-standard model is a
model of a theory that is not isomorphic to the intended model (or
standard model)". That also applies to syntactic theories. Actually,
non-standard interpretation of languages is a very fruitful area of
research in computer science, related to abstract interpretation, type
analysis, flow analysis, partial evaluation and many other approaches
to program analysis.  To take a very trivial, purely syntactic
example, a non-standard interpretation of a program can be a
pretty-printed version of that program. A type checker is usually an
abstract interpretation of the program.

As a consequence, it is clear that the chosen syntax may not capture,
express, all the properties of the intended semantic domain. However,
anything that is considered as syntactically correct must have some
associated semantics through the semantic morphism, even if it is some
special error value. But it is improper, though often done, to state
that the syntax is defined by a context-free grammars, and then
consider programs with undeclared variables as being incorrect. It
cannot be syntactically incorrect for such a reason, because CF
grammars cannot check variable declarations. And I would not know what
it means to be semantically incorrect, other than being possibly a
special error value of the semantic structure.

The dream of programming language designers or implementor is that any
program that can only fail, or that can fail in some specific way,
should be syntactically incorrect. Hence, they have been increasing
the descriptive power of syntax to include as much checking as
possible, limited only by computability constraints. This did lead to
the use of Turing complete formalisms, of which van Wijngaarden's
W-grammars are an example. But this is a pipe dream. Computability
theory tells us that semantic properties of syntactically expressed
functions cannot be checked syntactically, as soon as the language has
Turing power, which we usually expected in programming languages.

In practice, this checking for intrinsic correctness (i.e. independent
of problem specification), or for properties to be used, is often
performed in compilers (or in formal semantic definitions) by what is
called static semantics. Being purely computational, static semantics can be as well considered as part of the syntax.

In the case of programming languages, the semantic domain is a
computation domain.  Given that we allow Turing complete formalisms to
express the syntax, it becomes possible for the syntax to express
completely the semantics. But developing this angle is getting far away
from the original question. Still, this is the main reason why the distinction between syntax and semantics is so difficult to make precise in programming languages.  This may also be the reason why universal Turing machines are possible.

A last point is that defining the semantics as a structure that is a
model of the syntax may not be enough. It could be a model in several
different ways. So it is essential to include the morphism in the
description of the semantics. That is typically what is done with
denotational semantics of programming languages, and a lot of other
formal systems.

Note: This was rather complex and hard to write. If you are to
criticize it, I would appreciate explicit and precise comments. It
would also be useful to other users. Thank you.


Upper bound on register machine contents

Hint: Your computation model is Turing-complete. If you could compute an upper bound, that would enable you to solve the halting problem.


Reverse the input and output of a Mealy machine

That's not possible in general. The classical Mealy machine definition requires the Mealy machine to accept infinite-length input strings and produce infinite-length output strings while reading the input. You can't reverse an infinite-length input string and can't reverse an infinite-length output stream, since there is no last letter in the unreversed string that you could put as first letter in the reversed string.

So for your question to make sense, you would first need to change the definition to allow the Mealy machine to have missing successors for some state/input combination, so that an input word ends at a well-defined position. Then, you would need to assume that the automaton eventually has a missing transition for every possible input word. This excludes all cycles in the automaton.

If we have this, then there is only a finite number of different input strings. If $M'$ is actually well-defined, then it is possible to build such a Mealy machine. But $M'$ may not be well-defined. For example if $M(\textit{abcd}) = \textit{efgh}$ and $M(\textit{cd}) = \textit{he}$, then we have $M'(\textit{dcba})=\textit{hgfe}$ and $M'(\textit{dc}) = \textit{eh}$. By the definition of Mealy machine, this also means however that $M'(\textit{d})=\textit{h}$ and $M'(\textit{d}) = \textit{e}$, which is a contradiction.


Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1

A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \epsilon})$-algorithm is known.

For this we'll use the result that MAXCONV can be solved in $\mathcal{O}(n^{2 - \epsilon})$ iff MAXCONV UPPERBOUND can be solved in $\mathcal{O}(n^{2 - \epsilon})$ (reference: "On Problems Equivalent to (min,+)-Convolution", ICALP 2017)

To show this, first note that we may drop the requirement that the arrays are sorted. To show this, take arbitrary values $b_{i}[j]$, set $V = 2 \max_{i, j} |b_{i}[j]|$, and set $a_{i}[j] = b_{i}[j] + Vj$. Now $a_{i}[j+1] - a_{i}[j] = b_{i}[j+1] - b_{i}[j] + V \geq 0 \geq 0$, and the answer for $a$s is exactly $(k+1)V$ more than the answer for $b$s.

In a MAXCONV UPPERBOUND instance $(a[i])_{i = 0}^{n-1}, (b[i])_{i = 0}^{n-1}, (c[i])_{i = 0}^{n-1}$ we are asked if for all $k$ we have $\max_{i+j = k} a[i] + b[j] \leq c[k]$. To reduce it to our problem, set $a_{1}[j+1] = a[j]$, $a_{2}[j+1] = b[j]$ and $a_{3}[j] = -c[n-j]$. Further set $a_{1}[n+1] = a_{2}[n+1] = a_{3}[n+1] = -\infty$. Now the answer is positive if and only if at least one of the upper bounds doesn't hold: if the answer is positive, then $a_{1}[x] + a_{2}[y] + a_{3}[z] > 0$ for some $x + y + z = n+2$, hence $a[x-1] + b[y-1] > c[(x-1)+(y-1)]$ and the upper bound for $k = x+y-2$ doesn't hold. Similarly if $a[i] + b[j] > c[i+j]$, we have $a_{1}[i+1] + a_{2}[j+1] + a_{3}[n+2 - (i+1) - (j+1)] = a[i] + b[j] - c[i+j] > 0$.


Is there a formal CS definition of VCS and file versions?

You're thinking of a tweet by Isaac Wolkerstorfer (@agnoster):

git gets easier once you get the basic idea that branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space.

Unfortunately, it's a joke. As the author wrote on Quora:

It was intended as firmly tongue-in-cheek. I actually love git, and I think its complexity is greatly overblown. At the same time, I'm sympathetic to the fact that advice from git gurus to novices can end up sounding like inscrutable gibberish.
It's not intended to have any deeper meaning. Attempts to analyze it in this fashion should be futile, but due to a bug in reality, you can actually make any sufficiently hand-wavy statement fit if you try hard enough.

This has been discussed on Programmers Stack Exchange and on Mathematics Stack Exchange.

Joke aside, there has been work of formalizing version control. One effort that allies theory and practice is the work on patch theory by David Roundy on Darcs. The main objective of the theory is to model merging and, in particular, conflict resolution. The Darcs wiki has an introduction to the theory and a few pointers as well as a bibliography (unmaintained so outdated if you want a recent view on the subject, but it does list a 2009 survey paper by Petr Baudiš) and a list of talks (which includes more recent material). There's also a wikibook. One seminal paper is A Principled Approach to Version Control by Andres Löh, Wouter Swierstra and Daan Leijen3.
Patch theory does lead to a categorical model, which has been more recently explored in A Categorical Theory of Patches by Samuel Mimram and Cinzia Di Giusto and Homotopical Patch Theory by Carlo Angiuli, Ed Morehouse, Daniel R. Licata and Robert Harper. In Mimram and Di Giusto's work, the model has files as objects and patches as morphisms. I think that makes merging a branch a functor — an endofunctor if you're working in a single repository. “Homeomorphic endofunctor” doesn't make sense to me. With homotopy theory involved, submanifolds of a Hilbert space might not be so far out...


Does this argument prove CFLs are not closed under union?

Your first proof is valid. You are assuming by contradiction that CFLs are closed under complement and arriving at the absurd conclusion that they must be closed under intersection. Notice that this works for any intersection operation between two CFL languages.

Your second proof is wrong. You would need to assume that CFLs are closed under union and arrive at a contradiction. In your case your are not showing that, under the assumption, CFLs are closed under complement and intersection (hence the absurd). You are just showing that CFLs must be closed w.r.t. a particular operation in which you perform complements and intersections in some particular order.

Using the same logic I could prove the following erroneous claim.

Claim: CFLs are not closed under the identity operation $\textrm{Id}(L) = L$.

"Proof": CFLs are not closed under complement and, given a CFL $L$, $\textrm{Id}(L)$ can be written as $\textrm{Id}(L) = L = \overline{\overline{L}}$.


Architecture of a chatbot - how to organize and fetch possibilities?

When Building AI and ML for you Chatbot, you basically have 2 options:

You can use a 3rd party tool which will take care of the
AI/Conversational part of the Chatbot.
You can make your own using Machine Learning.Overwhelming, but quite
a few developers are choosing to go this route and many companies
are trying to democratize Machine Learning.

You can build your own NLP(Natural Language Processing) by using Machine Learning. One of the first things to consider will be the type of model you want to build.

Using an NLP/NLU Platforms: Natural Language Processing (NLP) and Natural Language Understanding (NLU) platforms attempt to solve the problem by parsing language into entities, intents and a few other categories. Different NLP platforms may have different names however the essence is moreso the same.

Categories:

Agents correspond to applications. Once you train and test an agent,
you can integrate it with your app or device.
Entities: represent concepts that are often specific to a domain as a
way of mapping natural language phrases to canonical phrases that
capture their meaning.
Intents represent a mapping between what a user says and what action
should be taken by your software.
Actions correspond to the steps your application will take when
specific intents are triggered by user inputs. An action may have
parameters for specifying detailed information about it.
Contexts are strings that represent the current context of the user
expression. This is useful for differentiating phrases which might be
vague and have different meaning depending on what was spoken
previously.

NLP Platforms:

API
WIT
LUIS
Microsoft Bot Connector

Reference :

NLP & Machine Learning Tutorial
Chatbot AI Tutorials
Machine Learning in a Year
Neural Networks for Machine Learning
You Too Can Become a Machine Learning Rock Star!


Push down automata what to do when there is no suitable transition

Starting with empty stack is not allowed.

A PDA is usually defined as (Q, Σ, Γ, δ, q0, Z0, F), where the symbols have their usual meanings. One of these is Z0, the stack start symbol. It is on the stack when the PDA starts.

So by definition you have Z0 on the stack at start.
You need to find Z0 in your case and start with that.


Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size?

Beam size, or beam width, is a parameter in the beam search algorithm which determines how many of the best partial solutions to evaluate. In an LSTM model of melody generation, for example, beam size limits the number of candidates to take as input for the decoder. A beam size of 1 is a best-first search - only the most probable candidate is chosen as input for the decoder. A beam size of $k$ will decode and evaluate the top $k$ candidates. A large beam size means a more extensive search - not only the single best candidate is evaluated.

Beam search is a heuristic search algorithm that uses breadth-first search to build its search tree and reduces the search space by eliminating candidates to reduce the memory and time requirements.1 Without the beam search, the worst time and space complexity for the best-search would be $\mathcal{O}(b^m)$ where $b$ is the branching factor and $m$ is the maximum depth. With beam search, the worst time complexity is $\mathcal{O}(kb)$ and the worst case space complexity is $\mathcal{O}(k)$2.

In the case of melody creation with Magenta, a beam size larger than the default of 1 will build a search tree for each candidate evaluation, as visible in this incomplete sketch of the graph ('h' represents an arbitrary heuristic cost):

A larger beam generally means a more accurate prediction at the expense of memory and time. In one trial using attention_rnn, for example, modifying the beam width from 1 to 4 decreased the average negative log-likelihood of sequence (melody) generation from 84.2 to 38.6.

1 - Beam search (Wikipedia)

2 - Notes on the Complexity of Search
 (MIT)


If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.


Can I couple non-terminals in context-free grammars?

In your case, the desired language is finite, so you can just go

$\qquad\displaystyle S \to 1 \mid 011$.

If you had recursion, say

$\qquad\displaystyle S \to ASB \mid 1$

as starting rule, you can not force "matching" $A$ and $B$ to behave in sync.
There are more powerful types of grammars that can do that, but that's beyond
the power of context-free.


In Hindley-Milner system, how can I prove that let id=\x.x in id id is well-typed?

If I understand you question correctly, you are wondering how the typing judgment $f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \beta$ can be proved, where $\beta$ is some (yet unknown) type.

As we are dealing with an application, the only rule that applies is T-App, so we end up with the following (partial) typing derivation, where $\gamma$ is yet another (unknown) type.
$$ \dfrac{\dfrac{\dfrac{}{x : \alpha \vdash x : \alpha}}
{\vdash \lambda x.x : \alpha \to \alpha} \quad\quad
\dfrac{f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma \to \beta \quad\quad f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma}
{f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \beta}}
{\vdash let \; f = \lambda x.x \;\; in \;\; f\;f : \beta} $$

Now, to complete the two open branches of the derivation, the only possibility is to use the T-Var rule, which has two preconditions. Applying it in the left branch, you can easily see that $\gamma$ must actually be $\beta$. And similarly, applying the T-Var rule in the right branch, you learn that $\gamma$ (or rather $\beta$) must be an arrow type of the form $\delta \to \delta$. So in the end, you obtain the following derivation (omitting the "$f : \forall \alpha.\alpha\to\alpha \in f : \forall \alpha. \alpha \to \alpha$") for the second premise of the T-Let rule.
$$ \dfrac{\dfrac{\forall \alpha.\alpha\to\alpha \subseteq (\delta \to \delta) \to (\delta \to \delta)}{f : \forall \alpha.\alpha \to \alpha \vdash f : (\delta \to \delta) \to (\delta \to \delta)} \quad\quad \dfrac{\forall \alpha.\alpha\to\alpha \subseteq \delta \to \delta}{f : \forall \alpha.\alpha \to \alpha \vdash f : \delta \to \delta}}
{f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \delta \to \delta}$$

Note that the conclusion of the full derivation then becomes $\vdash let \; f = \lambda x.x \;\; in \;\; f\;f : \delta \to \delta$.


Binary integer programming problem without exponential memory

There is in general not likely to be any algorithm for this problem that will take polynomial time (and polynomial space); the problem is NP-hard, and thus not believed to allow an efficient algorithm.  If you just want polynomial space, then exhaustive search works.  You're not likely to find any algorithm that uses polynomial space and is guaranteed to be faster than exhaustive search; that would contradict the strong exponential-time hypothesis.  All existing methods are heuristics that might work well on some instances but not others.


How does matrix chain multiplication problem has an optimal substructure?

First of all, it is correct and important to know that optimal solutions need not necessarily be unique!
However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such decisions repeatedly (usually via divide and rule)

Note that again, the 'optimal' decision need not be unique! So, by making different locally optimal decisions, it is possible to end up with multiple globally optimal results. So, the seeming contradiction of multiple optima and optimal substructure doesn't exist.


Finding the most efficient paths to cover an area from multiple starting locations

If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete [1]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").

In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.

You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.

[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.


Basic requirements for Integrality gap examples

No, there is absolutely no need for the gap instances to be efficiently constructible. It is perfectly fine even to give some pure existence proof, say using diagonalization or probabilistic techniques.

The reason is that the integrality gap examples rule out certain kinds of algorithms. Specifically, suppose that an algorithm solves the LP and then rounds it, and suppose that the way you prove the approximation guarantee is by showing (for a minimization problem) that rounding increases the value of the solution by at most a factor $C$. If there is an integrality gap of $\alpha$ then you know that $C \geq \alpha$. So no algorithm with this kind of analysis can result in an approximation ratio better than $\alpha$.

If I remember correctly there are some rare cases in which the way you analyze your algorithm is a bit different, and then you can go beyond the integrality gap, but unfortunately I can't think of any; if you're interested ask a separate question.

It is meaningful to consider an integrality gap even for different relaxations, for example for the semidefinite relaxation or for some LP or SDP hierarchy. The requirements are the same only you're comparing the integral optimum to the value of some more complicated program. The consequence is that an algorithm which proceeds by solving that program and then rounding can't given an approximation ratio better than the integrality gap (unless it does some rare hocus pocus as mentioned above).

Chlamtac and Tulsiani have written a nice survey on integrality gaps, which you might want to browse. It describes many complicated methods for constructing integrality gaps.


Necessities for two undirected graphs being isomorphic

For two graphs $G$ and $H$ it is necessary for literally every property that holds of $G$ to also hold of $H$ and vice-versa.  There's no point making a list because everything is in that list.


Call the center point $(c_x, c_y)$. The function $d(p_x,p_y) = \sqrt{(p_x-c_x)^2+(p_y-c_y)^2}$ computes the distance from the point $(p_x,p_y)$ to the center of the circle.

For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve for, $x$ and $y$ and plug this into the distance equation above, $d(x,y)$. Find the critical points by setting the partial derivatives equal to zero. Check that the critical points are further than the radius of the circle from the center of the circle.

If all critical points for all edges are more than the radius away from the center then the circle fits.


Does computational complexity theory take into account problems with subjectivity in the verification of a solution?

No.  Computational complexity doesn't deal with subjectivity.  In computational complexity, we consider formal languages that are precisely defined, so there is no subjectivity.


Regular expression for the language containing neither aa nor bb

$((ab)^∗∪(ab)^∗a)∪((ba)^∗∪(ba)^∗b)$  will work.

The possibilities are: $a,ab,aba,ababa,...$ or $b,ba,bab,baba,...$ or empty string


Linear programming IFF with equality constrain

Yes, this is possible. The main idea is that a binary variable can be used to enable/disable a inequality constraint as follows: given an inequality $a\cdot x\leq b$ and a binary variable $v$, pick a constant $L$ such that $a\cdot x - b\leq L$ is true for all variable assignments. Then the inequality $a\cdot x \leq b+ (1-v)L$ will be equal to $a\cdot x\leq b$ if $v=1$ and will always be true if $v=0$.

So, the constraint $y=1\Rightarrow v=k$ part can be modeled by the two inequalities $v\leq k+(1-y)L$ and $v\geq k - (1-y)L$. For the other part, $v=k\Rightarrow y=1$, we first transform this into $y\neq 1\Rightarrow v\neq k$. We can model the $v\neq k$ condition as $v < k \vee v > k$ and to model the 'or' we introduce a new binary variable $q$. In particular, we want $v<k$ if $q=1$ and $y=0$ and $v>k$ if $q=0$ and $y=0$, so we get $v < k + (1-q+y)L$ and $v > k-(q+y)L$.

In summary, the inequalities $$\begin{align} v&\leq k+(1-y)L\\ v&\geq k - (1-y)L\\ v &< k + (1-q+y)L\\  v &> k-(q+y)L\end{align}$$ model the constraint $y=1 \Leftrightarrow v=k$.


If it is implemented in hardware, prefetching is typically done asynchronously.

It's also possible for a compiler to insert extra prefetch instructions into the code.  Thus, the initiation of the fetch is done synchronously, but then the memory access continues asynchronously.

See https://en.wikipedia.org/wiki/Cache_prefetching.


Prove that the following language is regular

The idea is like the production of two DFAs. Let two DFAs be $M_1 = (Q_1, \Sigma , \delta_1, q_{01}, F_1)$ and $M_2 = (Q_2, \Sigma , \delta_2, q_{02}, F_2)$. Define NFA $M = (Q, \Sigma , \delta, q_0, F)$ to have:

$ Q = Q_1 \times Q_2 \times \{0,1\}$

$ \delta((q_1,q_2,0), a) = (\delta(q_1,a),q_2,1) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ \delta((q_1,q_2,1), a) = (q_1,\delta(q_2,a),0) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ q_0 = (q_1,q_2,0)$

$ (q_1,q_2,0) \in F \ \text{iff} \ q_1 \in F_1 \ \text{and} \ q_2 \in F_2$

Note that the 0 or 1 is just indicating moving turn! In a final state, the turn has to be 0 meaning $M1$'s turn!


How do you marginalize in graphical model elimination?

I'm realizing now that it's just regular matrix multiplication.

For the case above, let $p(x_5|x_3)$ and $p(\bar{x_6}|x_2,x_5)$ be represented by $r\!\times\!s$ and $s\!\times\! t$ matrices, respectively, where $x_5$ can take on $s$ different values. Then, for each element $m_{ij}$ of $m_5$, we have that

$$m_{ij}=\sum_{k=1}^s p_{ik}(x_5|x_3)p_{kj}(\bar{x_6}|x_2,x_5)$$

where $1\leq i \leq r$ and $1 \leq j \leq t$.

This is matrix multiplication. Also, intuitively, the dimensions will always work out, since each factor in the product will always be a function of the variable we're summing over.

I think the notation is what was tripping me up. I usually don't see matrix multiplication written explicitly as a sum of products.


NFA designing for strings starting with $01$

Since this is an NFA, the solutions are equivalent. When you are in a state without any transition for the current input you receive, you terminate (equivalent to getting stuck in a non-accepting state without going out of it).