Proving closure under reversal of languages accepted by min-heap automata

Consider the language
$$L_{\times 2} = \big\{ x\bot y\bot z  \mid x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$$
(where $\#_0(x)$ denotes the number of zeros in $x$).

It is easy to decide $L_{\times 2}$ using a HAL machine — observe that the machine needs to keep track of two properties: the number of zeros in $x$ vs $y$ and the length of $x,y$ (vs $z$). It can push a 0 into the heap for every zero it sees in $x$ (and then later pop 0 for any zero seen in $y$); additionally it pushes 1 for any bit in $x,y$ (and later pops 1 for any bit of $z$). Since all the 1s are pushed down the heap, they don't interfere with the 0 count. The $\bot$ serves as a delimiter, and can be practically ignored.

Now, let $L = L_{\times 2}^R$, be the reverse language. That is,
$$ L = \big\{z\bot y \bot x \mid  x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$$
We will show that no HAL machine can decide $L$.

The intuition is the following. As above, the machine must keep track of both the length of $z$ and the number of zeros in $x,y$. However, in this case it need to track them simultaneously. This cannot be done via a heap. In more details, after reading $z$, the heap contains information about the length of $|x|+|y|$.
while reading $y$ the machine must also keep in the heap the number of zeros in $y$. However, this information cannot interfere with the information the heap already has on the length we expect $x$ to be. Very intuitively, either the information about the number of zeros will be "below"  the information about the length of $x$, and then we cannot access it while reading $x$, or it is "above" that information, rendering the latter inaccessible, or the two information will be "mixed" and become meaningless.

More formally, we are going use some kind of a "pumping" argument. That is, we will take a very long input, and show that the "state" of the machine must repeat itself during processing that input, which will allow us to "replace" the input once the machine repeats its "state".

For the formal proof, we require a simplification of the structure of the HAL machine, namely, that it doesn't contain a "loop" of $\varepsilon$-transitions$^1$. With this assumption we can see that for every input symbol the machine processes, the content of the heap can increase/decrease by at most $c$  (for some large enough constant $c$).

Proof.
Assume $H$ decides $L$, and consider a long enough input (say, of length $4n$, thus $|x|=|y|=n$, $|z|=2n$, ignoring the $\bot$s hereinafter). To be concrete, fix $z,y$ and assume that $\#_0(y) = n/2$. Observe that there are ${n \choose n/2}$ different $x$'s such that $z\bot y \bot x \in L$.

Consider the heap's content immediately after processing $z\bot y$. It contains at most $3nc$ symbols (where each symbol is from a fixed alphabet $\Gamma$), by our assumption. However, there are ${n \choose n/2}$ different $x's$ that should be accepted (which is substantially larger than the amount of possible different contents for the heap, as this increases exponentially, while the different number of heaps increases polynomially, see below).
Take two inputs $x_1,x_2$ that should be accepted, so that the following holds:

The prefix of length $n/2$ of $x_1$ has different number of zeros than the prefix of $x_2$ of the same length.
By the time the machine reads a prefix of  length $n/2$ of the $x$ part, the heap looks the same for both $x_1$ and $x_2$, and also, the machine is in the same state  (this must happen for some $x_1,x_2$, for large enough $n$, as there are more than $2^{0.8n}$ different options$^2$ for $x_1,x_2$, and at most $(3.5cn)^{|\Gamma|}|Q|$ different options for heap content and state$^3$).

It is clear that the machine must accept the word $z\bot y \bot x_1^px_2^s$, where $x_1^p$ is a prefix of $x$ of length $n/2$ and $x_2^s$ is a suffix of $x_2$ of the same length. Note that the number of zeros in $x_1^px_2^s$ differs from the number of zeros in $x_1$ and $x_2$ (that is, from $\#_0(y)$), due to the way we chose $x_1$ and $x_2$, thus we reached a contradiction.

$^1$  Does this assumption damages generality? I don't think so, but this indeed requires a proof. If someone sees how to get around this extra assumption, I'd love to know.
$^2$  Let's fix $x_1$ so that it's prefix (of length $n/2$ has exactly $n/4$ zeros). Recall that using Stirling's approximation we know that $\log {n \choose k} \approx nH(k/n)$ where $H()$ is the Binary entropy funciton. Since $H(1/4) \approx 0.81$ we have ${n \choose n/4} > 2^{0.8n}$ for large enough $n$.
$^3$  Assuming alphabet $\Gamma$, there are $|\Gamma|^n$ different strings of length $n$, so if this was a stack we were screwed. However, pushing "01" into a heap is equivalent to pushing "10" - the heap stores only the sorted version of the content. The number of different sorted strings of size $n$ is  ${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$, for a constant $|\Gamma|$.


Which sorting algorithm is most efficient to 'continuously' sort a vector again and again?

Look at what your problem actually is: Your problem is not sorting the list, but finding the largest ten items. That's a much easier problem, which can be solved without sorting the list again and again.

Start by finding the top ten items once. Let $X_{10}$ be the value of the tenth largest item.

If an item outside the top ten is changed to a value ≤ $X_{10}$, ignore it. If it is changed to a value > $X_{10}$, then drop the tenth item and insert the changed item in the array in the right position.

If an item in the top ten is changed then move it up or down according to the new value. If the new value is less than < $X_{10}$ then remove it from the top ten leaving you with the top nine, find the largest item that is currently not in the top nine, and put it into the tenth position.

So most of the time you do no work at all, a lot of the time very little work, and occasionally it takes linear time.


implementing permutation and combination recursively

The number of permutations of $n$ distinct objects is $n!$.
The number of $k$ selections out of $n$ distinct objects is $\binom{n}{k}$ known also as a binomial coefficient. Recursive definition of these numbers are trivial:
$$n! = n(n-1)!$$
$$\text{so if } f(n) = n! \text{ then } f(n) = n\times f(n-1), f(0) = 1$$
For binomial coefficients
$${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$
or
$$ b(n,k) = b(n-1, k-1)+b(n-1, k)$$
where
$$b(n,n)=1 = b(n,0)=1 \text{ and } b(n,k)=0 \text{ for } n < k$$

If you want approximate value without too much computation then you may check the Stirling's approximation.

Proof of $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$
You can prove it using a combinatorial argument or algebraic. The algebraic one is tedious (you need to manipulate factorials). So let's consider a combinatorial proof.

Assume we have $n$ people, numbered from $1$ to $n$, and want to create a team consisting of $k$ people. There are exactly ${\binom {n}{k}}$ ways to create a team, i.e, $k$ people out of total $n$. Consider the first member, number $1$. There are two possibilities: either include her or leave her out.

If we choose that member then we need to choose additional $k-1$
people out of remaining $n-1$ people which is equal to $\binom{n-1}{k-1}$.
If we leave that member out then we have to select $k$ out of $n-1$
people which equal to $\binom{n-1}{k}$.

Since these both options result in different teams the total number of teams is
$$\binom{n-1}{k-1} + \binom{n-1}{k} $$


No. Your proof of $A\iff B$ is to claim that

$$A\iff \text{something} \iff \text{something else} \iff A \iff B\,.$$

The first two stages are irrelevant, since you get back to $A$. The final stage just asserts as true the exact thing you're supposed to be proving.

Try instead to prove that every string in the first language is in the second.


Subgraph isomorphisms: does large out-expansion imply large in-expansion?

Yes: if each vertex maps to at least $k$ vertices by a set $S$ of bijections of a finite set, then there are at least $k$ vertices that map to each vertex by these bijections.

In fact, the in-spectrum (the sequence of in-expansions) is a permutation of the out-spectrum (the sequence of out-expansions).  Note that $f$ is a bijection iff $f^{-1}$ is a bijection.  Hence one can define a bijection between $S$ and $S^{-1} = \{f^{-1}\mid f\in S\}\ $ so the spectra are then permutations of each other.

An aside: this doesn't necessarily hold for bijections of infinite sets.  Let $f_i$ be the map $1\mapsto i, 2\mapsto 1, 3\mapsto 2, \dots, i \mapsto i-1, i+1\mapsto i+1,\dots$, and take the collection of all these maps.  Then the out-spectrum is $(\omega,2,2,\dots)$ while the in-spectrum is $(2,2,2,\dots)$.


Correctness of Strongly Connected Components algorithm for a directed graph

Transposing the adjecency matrix $A$ does

$\qquad A[i,j] = 1 \iff A^T[j,i] = 1$.

In terms of graphs, that means

$\qquad u \to_G v \iff v \to_{G^T} u$.

In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$.

The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion of "finishing time": it's not the time the node is visited, but when the search has traversed the subgraph reachable from it. Wikipedia proposes to use a stack to manage this, which I think is a good idea.

Why is it correct to use $G^T$, intuitively? Assume $x$ is the first node of its strong component visited by the DFS.

The DFS on $G$ traverses the whole strong component of $x$ after reaching $x$, plus some others via edges that leave the component.
Since we use a stack order for remembering the order of nodes, $x$ is also the first node of its strong component visited (as starting node, even) in the second phase.
Since $G$ and $G^T$ have the same strong components, all nodes in the strong component of $x$ are visited when searching $G^T$ from $x$. Those edges leaving the component in the first phase point in the wrong direction in $G^T$ and are thus not followed. All edges leaving the component of $x$ in $G^T$ have already been removed because of the stack order.


Show that term cons works by showing all beta reductions

$[3,2,1]$ is just syntactic sugar for $\mathsf{cons} \, 3 \, (\mathsf{cons} \, 2 \, (\mathsf{cons} \, 1 \, \mathsf{nil}))$. $[3,2,1]$ is $\mathsf{cons} \, 3 \, [2,1]$ by definition of the $[\ldots]$ notation.
Because $\mathsf{cons}$ is part of the definition of lists, it isn't meaningful to ask whether $\mathsf{cons}$ is correct on its own. The meaningful question is whether the definition of lists is correct as a whole. (More precisely, that's the definition of an encoding of lists in the lambda calculus.) Another way to look at it is that the goal isn't to prove that the definition of cons is correct, but that it's consistent with the rest of the definition of lists.
There are several, equivalent ways to define lists as an abstract type. Lists are an abstract type, defined by a number of functions and properties involving these functions. Lists are an abstract data type, so the functions can be classified into three groups: constructors (which build “bigger” lists from smaller lists and other stuff), destructors (which “break down” lists into smaller lists and other stuff) and other functions which can be built out of constructors and destructors. Any simple definition of lists uses two constructors: $\mathsf{nil}$ which is the empty list, and $\mathsf{cons}$ which takes two arguments, an element and a list, and returns a new list. The “most fundamental” (and easiest to reason with, but not easiest to understand) definition uses one destructor $\mathsf{case}$, and satisfies the following equations for any terms $f$, $g$, $h$, $t$ such that $t$ is a list:
$$
\begin{align}
\mathsf{case}\,\mathsf{nil}\,f\,g &= f \\
\mathsf{case}\,(\mathsf{cons}\,h\,t)\,f\,g &= g \, h \, t \\
\end{align}
$$
An encoding of this abstract type in the lambda calculus is the definition of three lambda terms $\mathsf{nil}$, $\mathsf{cons}$ and $\mathsf{case}$. Proving the correctness of this encoding means proving that the equation above holds.
Another, equivalent, definition of lists uses three destructors $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$ with the following equations (which presuppose the existence of booleans) for any terms $h$, $t$ such that $t$ is a list:
$$
\begin{align}
\mathsf{empty}\,\mathsf{nil} &= \mathsf{true} \\
\mathsf{empty}\,(\mathsf{cons}\,h\,t) &= \mathsf{false} \\
\mathsf{head}\,(\mathsf{cons}\,h\,t) &= h \\
\mathsf{tail}\,(\mathsf{cons}\,h\,t) &= t \\
\end{align}
$$
An encoding of this abstract type in the lambda calculus is the definition of five lambda terms $\mathsf{nil}$, $\mathsf{cons}$, $\mathsf{empty}$, $\mathsf{head}$ and $\mathsf{tail}$. Proving the correctness of this encoding means proving that the equation above holds.


Anti-symmetry of polynomial time reductions

$A\equiv_p B$ is by definition $A\le_p B$ and $B\le_p A$.

It means that they are in the "exact same level of complexity", but only with respect to polynomial time reductions! For example, if $A\in LOGSPACE$ and $B\in NLOGSPACE$, then trivially $A\equiv_p B$. But clearly $A$ and $B$ are not in the "same level of complexity".

This is part of a general observation about reductions: A reduction that is computable by a machine that works in $t(n)$ time (resp. $s(n)$ space) is only useful if you use it in classes that are provable at least as strong as $TIME[t(n)]$ (resp. $SPACE[s(n)]$), and are conjectured to be stronger.

So, polynomial time reduction are used in $NP$ and $PSPACE$, $LOGSPACE$ reductions are used in $NLOGSPACE$, etc.


The language of Logical Theory as Metalanguage

The concept of metalanguage is central to logic. Here is an example. The following statement is in the language of propositional logic:

  $$ a \lor b $$

The following is in the metalanguage:

  The formula $a \lor b$ is satisfiable.

In formal logic, we have some formalism for logical statements. This formalism specifies the syntax and semantics of logical statements. For example, in propositional logic we specify a set of logical connectives and how they are used to form logical statements (the syntax), and how a truth assignment to the variables yields a truth assignment of statements (the semantics). This constitutes the "object language". The metalanguage is just the usual English prose that we use, which might refer to the object language, as above.

In simple situations, we distinguish between the two by using logical symbolism for the object language, and natural language (like English) for the metalanguage. However, there are exceptions, the most interesting of which is the use of the metalanguage as a "shortcut" for a statement in the object language. For example, consider the following statement in the language of rings:

  $\exists b . ab=1$

This states that $a$ is invertible. We could also write it in this way:

  "$a$ is invertible"

What this means is that "$a$ is invertible" stands for some statement in the object language which states that $a$ is invertible. How is this different from stating in prose that $a$ is invertible? Well, suppose that we have some encoding function $\varphi$ which encodes formulas to integers. Then it is meaningful to consider $\varphi(\exists b.ab=1)$ or $\varphi(\text{"$a$ is invertible"})$ (the two might even be equal if you choose $\exists b.ab=1$ as the denotation of "$a$ is invertible"), but not $\varphi(\text{$a$ is invertible})$, the latter being as meaningless as $\varphi(\text{blue})$.

For further illustration of this difference, I recommend reading on Gödel's second incompleteness theorem.

Necessary and possible are logical concepts (concepts of the metalanguage) which can be thought of as properties of logical statements: a logical statement is necessary if it is always true (i.e., if it is a tautology), and it is possible if it could be true (i.e., if it is satisfiable). As such, you can think of them as predicates on the domain of logical statements. In the philosophical discipline of logic they have greater applicability, beyond propositional and predicate logic.

As an example, $a \lor \lnot a$ is possible and necessary, $a \lor b$ is possible but not necessary, and $a \land \lnot a$ is neither possible nor necessary. Every necessary statement is a fortiori possible.


Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

Let $f(n) = \Theta(n)$. Thus there are $N,a,b>0$ such that for $n \geq N$, we have $an \leq f(n) \leq bn$.

Now suppose that $T(n) = T(n-1) + f(n)$, with some base case $T(0) = C$. Unrolling the sum,
$$
T(n) = C + f(1) + \cdots + f(n).
$$
Let $D = C + f(1) + \cdots + f(N-1)$. For $n \geq N$,
$$
T(n) \leq D + b(N + \cdots + n) = D + b\frac{(n-N+1)(n+N)}{2} = O(n^2).
$$
Similarly,
$$
T(n) \geq D + a(N + \cdots + n) = D + a\frac{(n-N+1)(n+N)}{2} = \Omega(n^2).
$$


How are the web based compilers designed?

This question is asked on stackoverflow:

  How do sites like codepad.org and ideone.com sandbox your program

A short summary from the answers:

Using geordi (codepad does this)
Systrace
Virtualization (VM)
OS level jailing functionality

chroot
Permissions
ulimit
nice, ionice, cpulimit,
disk quotas

AppArmor, SELinux
Restrict compiler access to headers/libraries
Restrict interpreter access to libraries
Static analysis
libsandbox

A more theoretical answer would be that it is possible to restrict all calls out of the program, (syscalls, function calls etc.), in a manner similar to how native client works, if you have control of the compiler (and even moreso, if you control the CPU and OS). For time and memory consumption, you can simply have have cut-offs that would kill the compilation process/running program. This should only leave you vulnerable to bugs in the compiler, runtime libs, and the OS/hardware level; which a VM can mostly eliminate the danger of.


Algorithm for maximum independent set in trees

Lemma. Every tree $T$ with at least three vertices has a maximum-cardinality independent set which includes all its leaves.

Proof. Let $I$ be a maximum-cardinality independent set containing the greatest number of leaves of $T$ of all such independent sets. Suppose that $v\notin I$ for some leaf $v$ of $T$ and let $w$ be $v$'s unique neighbour. If $w\notin I$, then $I\cup\{v\}$ is independent, contradicting the supposed maximality of $I$. Otherwise, $w\in I$ but $I' = (I\setminus\{w\}) \cup \{v\}$ is an independent set of the same cardinality as $I$. Since $T$ has at least three vertices, $w$ has degree at least two, so is not a leaf. Therefore, $I'$ contains one more leaf than $I$, again contradicting the choice of $I$. $\square$

Now we can see that the algorithm proposed in the question produces a maximum-cardinality independent set because it actually mimics a particular set of choices by the dynamic programming algorithm. Let $v$ and $w$ be vertices in the tree at maximal distance (which must, of course, be leaves). By the lemma, there is a maximum-cardinality independent set that includes both of these vertices. Therefore, we can pick either one to add to our independent set.

Note that there is a slight wrinkle in the algorithm as presented in the question. Suppose $v$ and $w$ are at maximal distance in $T$ and we decide to add $v$ to our independent set.  We delete $v$ and its neighbour $v'$ from $T$. However, if $v'$ had degree at least three, we have disconnected the tree.  This is OK because, by maximality of the distance from $v$ to $w$, all but one of the neighbours of $v'$ must have been leaves, so all but one of the components of $T-\{v,v'\}$ are isolated vertices. But these isolated vertices must also be added to the independent set and deleted from $T$.  If they are not, then $d(v'',x)=\infty$ for any isolated vertex $v''$ and any other vertex $x$. Thus, the algorithm would be entitled to add any vertex $x$ to the independent set at the next step, which is not guaranteed to lead to a maximum-cardinality independent set (and, indeed, might disconnect the graph even more when we delete it and its neighbours).


What are elementary operations in time complexity definition?

The set of elementary operations and their cost constitute a model of computation. The most common model of computation used to analyze algorithms is the Random access machine. Briefly, memory is divided into words of size $O(\log n)$ bits, where $n$ is the size of the input to the algorithm. A program consists of a sequence of instructions. The exact set of instructions isn't really set in stone, but usually includes arithmetic instructions (addition, subtraction, multiplication, division with remainder), possibly bitwise instructions, memory dereferencing, control flow, and so on. In the unit cost RAM, the most common model, each instruction operations on a single word, and costs one unit of time.

Other relatively common models of computation include various models of Turing machine, the bit complexity model (in which words consist of a single bit), and logarithmic cost RAM.


Determine whether two languages are context free

For the first one, $$L_1 = \{a^i,b^{i+j}c^j \mid i,j \geq 0 \} $$

Here's an rough idea of the algorithm:

read off the all '$a$'s and push $a$ into the stack
upon seeing a '$b$', pop the '$a$'s till the stack is empty
then again as long as reading '$b$'s keep pushing $b$ into the stack
on seeing a $c$, start popping the stack until empty.

For the second one,

Please see my answer here, The other answer is equally good (perhaps even better and simpler) than mine.


Does "serializable" also mean that it's lockable

The definition of serializable schedule is pretty clear. Intuitively, it is a schedule which is equivalent to a serial schedule.

More formally, according to [1] :

  A serializable schedule over a set S of transactions is a schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed transactions in S.

In your example the schedule is definitely serializable, since it is equivalent to running Transaction 2 and then Transaction 1.

I don't know what do you mean by "lockable" and not sure that this term can be applied to a schedule.

[1] R.Ramakrishnan and J.Gehrke, Database Management Systems,  3rd edition


The way to use Dijkstra's algorithm to solve the $s$-to-$t$ widest-path problem (in a directed graph) is described well in the following lecture notes:

http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf

Make sure to read Sections 13.1, 13.2, and 13.3.  You will see that a single-line change to Dijkstra's algorithm suffices (we change the $+$ to $\min$, and change the $\min$ to $\max$, to represent the fact that we now have a different metric for the "goodness" of a path).

The section you quoted from Wikipedia is talking about a small optimization to this variant of Dijkstra's algorithm.  However, you can use the variant of Dijkstra's algorithm in Section 13.3 of those lecture notes directly, without the optimization mentioned in Wikipedia, if you like -- and that's easier to understand.


Solving linear system of nonhomogenous equations that are known to have natural solutions

You can represent the system as a matrix equation as $Ax = b$, where $k^{th}$ row of $A$ is the coefficients $[a_{k1},a_{k2}...,a_{kn}]$, $x = [x_1, x_2,...,x_n]$ and $b = [b_1,b_2,...,b_m]$.
Unique Solution:
If the system has a unique solution, you should be able to get $A$ into row-echelon form. Then, you'll find a row with only one non-zero coefficient, corresponding to an atomic expression like $x_j = b_k$. Plug this in by dropping the $j^{th}$ column and the $k^{th}$ row and updating all other rows as $b_l' = b_l - a_{lj}b_k$. Recursively keep doing this until all values are found.
I finally remembered that the name of this procedure: Gaussian Elimination. Here is a nice concise description with a solved example.
Underdetermined System:
If there are multiple solutions, then the number of linearly independent rows is less than the number of variables. Since you seem to have many more equations than variables, this is great news. Using the row-echelon form, you can weed out redundant equalities and end up with a much smaller system of equations.
Now, let $$z_k = \min_{\substack{1 \leq i \leq m \\ a_{ki} \neq 0}}\left\{\frac{b_i}{a_{ki}}\right\},$$
so we get $1 \leq x_k \leq z_k$ as the feasible set for each variable. One way to shrink the brute-force approach is to order the variables by their upper bounds. If $z_{k_1} \geq z_{k_2} \geq ... \geq z_{k_n}$, suppose variables satisfy $x_{k_1} \geq x_{k_2} \geq ... \geq x_{k_n}$. Then, you can enumerate the solutions under this constraint by enumerating.
For example, let's say $z_1 = 3, z_2 = 2, ...$. Then, you would have $(3,2,..),...,(3,1,..),...,(2,2,..),...,(2,1,...),...,(1,1,...),...$.
With this ordering assumption you are searching over a much smaller set. Once you have that, you can check the permutations of these solutions and if they are feasible for all variables, they are valid solutions.
For example, for $x_1 + x_2 + x_3 = 3$, let's say we break the tie as $x_1 \geq x_2 \geq x_3$. Then, the constrained solutions are $(3,0,0), (2,1,0), (1,1,1)$ and the permutations of these give you the whole set since they are all the feasible due to $z_1=z_2=z_3$.


Your problem may be a slight misunderstanding.

  Given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of 3SAT.

This is almost correct; check the claimed equivalence again:

$\qquad\displaystyle w \in \mathrm{3SAT} \iff f(w) \in \mathrm{KCLIQUE}\;. \tag{1}$

For the "backwards" direction, you only need to assume a yes-instance from the intersection of the image of $f$ and KCLIQUE, i.e. show that

$\qquad\displaystyle \forall w \in \operatorname{img}(f) \cap \mathrm{KCLIQUE}.\ f^{-1}(w) \in \mathrm{3SAT}$.

That means that you can assume some structure about the instances you need to prove the reverse direction for, namely that introduced by your reduction.

Another misunderstanding:

  the domain is the language 3SAT and the Codomain is the language KCLIQUE

That's not true; note that (1) is (maybe implicitly) supposed to hold for all $w \in \Sigma^*$, that is the domain of $f$ is $\Sigma^*$. All $w \not\in \mathrm{3SAT}$ must therefore map to $f(w) \not\in \mathrm{KCLIQUE}$ in order to fulfill (1), so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.


Is it possible for a network to have a negative cycle that is not found by the Bellman–Ford algorithm?

No, it is not possible. If there is a negative cycle in a network, it will be found by the step 3 of Bellman–Ford algorithm as described by Wikipedia.

Here is the reason given by Wikipedia.

  Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration $i$ that the edges are scanned, the algorithm finds all shortest paths of at most length $i$ edges (and possibly some paths longer than $i$ edges). Since the longest possible path without a cycle can be $|V|-1$ edges, the edges must be scanned $|V|-1$ times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length $|V|$ edges has been found which can only occur if at least one negative cycle exists in the graph.

For more detailed understanding, please read the proof of the correctness of Bellman-Ford as well as finding negative cycles by Bellman-Ford.

Here is one easy related exercise.

Exercise. Let $e_0, e_1, e_2, \cdots, e_{m-1}, e_m=e_0$ be a negative cycle whose number of vertices, $m$ is the smallest among all negative cycles. Show that it is a chordless cycle.


How are hash table's values stored physically in memory?

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table.  So, in your example, if you were storing the items in an array of size 6, the three items with hash values 0, 10 and 20 would be stored at locations 0, 4 and 2, respectively.  If you added a fourth element with hash value, say, 31, that would be stored at location 1, without needing to move any of the first three items.  If your hash table was becoming full and you wanted to move it into a bigger array, then you would need to recalculate the locations of all the items in the table and move them appropriately.


Are there any examples of programming synthesis in vulnerability research?

Yes, there's plenty of work on synthesizing exploits using program synthesis.  One of the seminal papers was:

Thanassis Avgerinos, Sang Kil Cha, Alexandre Rebert, Edward J. Schwartz, Maverick Woo, and David Brumley. Automatic Exploit Generation. Communications of the ACM, 57(2):74–84, 2014.

This is a cleaned-up and general-audience version of a paper published at NDSS in 2011.

You should be able to use Google Scholar to find lots of other related work and follow-on work, by finding papers that cite it.  Also, many of the research teams participating in the Cyber Grand Challenge have been publishing on this subject for the past several years; look up each of their web pages and go check out their papers, and you should be able to find more.

Generally speaking, the challenge typically lies more in finding inputs to a vulnerable program that will cause it to do something bad, rather than in finding programs that directly do something bad themselves.  Thus, the techniques tend to be slightly different from standard work on program synthesis, because the challenges are slightly different in this space: here it's often more about synthesizing data rather than code.

There is also plenty of work on automated patch creation.  There, the big challenge is usually identifying which part of the code is vulnerable and what the vulnerability is; once you know that, the patch synthesis is usually rather straightforward.  Consequently, the challenge typically seems to be more about program analysis than synthesis, though of course there are certainly aspects of both that do need to be solved, and different papers have a different focus.


Determine if two edges of a graph cross?

If you don't care about time complexity, the following algorithm would do. Go over all pairs of edges. For each pair, we have to find whether the two segments intersect. There are two cases: the two segments have the same slope, or they don't have the same slope.

If they have the same slope, then they could be two segments on the same line, or they could belong to different lines. In the second case, they don't intersect. In the first case, this is a one-dimensional problem which is easy to solve (you can reduce it to checking whether two intervals on the real line intersect).

If the two segments have different slope, then the corresponding lines intersect at a unique point. It remains to find whether this point also belongs to both segments.

There are probably more efficient solutions out there, but this shows how to solve your problem in a naive way.


Constructing Tree (forest) from Ancestor function

Assumptions

We have a finite set $\mathscr{D}$ of persons and a relation $\prec$: $x \prec y$ means that $x$ is an ancestor of $y$. This relation has the following properties:

Transitivity: if $x \prec y$ and $y \prec z$ then $x \prec z$ (the ancestor of my ancestor is my ancestor).
Antisymmetry: if $x \prec y$ then $y \nprec x$ (I am not my ancestor's ancestor).
Chain: if $x \prec z$ and $y \prec z$ then either $x \prec y$ or $x = y$ or $y \prec x$ (my ancestors form an ordered chain).

Data structures

Let it be given a set data structure on which the following operations are defined:

empty set
add an element to a set
splitting a set according to a property: iterate over the elements, compute a property on each element, and build two subsets, the set of elements for which the property is true and the set for which the property is false. This operation is assumed to be linear in the size of the set.

We will also use a tree data structure, in which each node contains a person and the set of its children. If $t$ is a tree, write $t_R$ for the person at the root node and $t_C$ for the set of children. A forest is a set of trees.

Algorithm

We start with an empty forest and add persons one by one. At each step, the parent-child relationship in the forest is the parent-child relationship for the ancestor relation. We define a recursive function graft that inserts a tree into a forest.

Input of graft: a forest $F$, and a tree $s$ such that none of the elements of the tree is related to any of the persons in $F$. Let $x = s_R$.

First, check whether $x$ is the ancestor of any of the existing persons: split the set $F$ according to the property $x \prec t_R$ for $t \in F$. Let $C$ be the subset of $F$ consisting of descendants of $x$ (if the root of a tree is a descendant of $x$ then all elements are also descendants by transitivity), and $F'$ be the remaining subset. By antisymmetry, none of the persons in $C$ is an ancestor of $x$. None of the elements of $s_C$ are related to any of the persons in $C$ by assumption. Let $u$ be the tree where the root person is $x$ and the set of children of the root is $C \cup s_C$.

By the chain assumption, $x$ can have ancestors in at most one of the trees in $F'$. Iterate over the trees $t \in F'$, and determine which one if any has an ancestor of $x$ at its root (this is a splitting operation where one of the sets is guaranteed to contain at most one element).

Output of graft:

If no tree in $F'$ has an ancestor of $F'$ at the root, then add the new node to the remaining forest: return $F' \cup \{u\}$.
If there is a tree $t$ in $F'$ such that $t_R \prec s$, then we need to insert the new element with its descendants into that tree. Let $G = \text{graft}(t_C, u)$. Return $(F' \setminus \{t\}) \cup \{t'\}$ where $t'$ has $t_R$ at the root and $G$ for children.

Main algorithm: Start from an empty forest, and iteratively graft the persons in $\mathscr{D}$ (grafting a person means grafting the tree with this person at the root and no children).

Correctness

From the remarks of this algorithm, it should be easy to prove that the recursive calls to graft are valid (all relatives of the nodes in the tree being inserted are inside that tree), and that $x$ is an ancestor of $y$ in the tree iff $x \prec y$.

Complexity

$\textrm{graft}(F,t)$ performs at most $2 n$ ancestor tests, where $n$ is the number of persons in $F$: one test per root of $F$, one test per root that is not a descendant of the new node, and tests performed by the recursive call if any which applies to a subset of $F$ not including any of its roots. The complexity of other operations is linear in the number of ancestor tests performed.

Therefore the forest construction algorithm performs at most $2 + 4 + 6 + \ldots + 2(n-1) = n (n-1)$ ancestor tests where $n$ is the total number of persons. In fact, it is easy to see that it never performs the same test twice. The overall complexity is therefore $O(n^2)$.

In the worst case, all possible $n (n-1)$ tests are performed. This happens when no two persons are related, and it is unavoidable in this case.


I suspect they probably mean
$$ub_d = \max_i x_i^d$$
where $x_i^d$ is the $d$h coordinate of $x_i$; and similarly for $lb_d$, but using $\min$ instead of $\max$.  But I don't know -- I am just speculating based on context.


Does a Hadamard Gate have uses outside of pure and evenly mixed states?

I don't know of any explicit use of the Hadamard gate in circuits other than to introduce or take away superposition, but here are some interesting applications:

The Hadamard gate is the single-qubit version of the Fourier Transform*, and the Fourier Transform is very useful.
Instead of using the Hadamard at the end of a computation to get back the original basis, you can measure the system in the Hadamard basis instead of the standard basis.
The set of $\{\text{CNOT}, \text{Hadamard}, \text{rotation by 45 degrees}, \frac{\pi}{8}\text{-gate} \}$ is a universal quantum gate set. That is to say, any quantum gate can be approximated arbitrarily well by repeated application of gates from this set.
If you prepend and append two Hadamard gates to a CNOT gate, you reverse the role of control bit and target bit.

*Demonstration: The quantum Fourier transform is defined as follows. Take a system of $n$ particles in the standard basis, and put it in state $|k\rangle, 0 \leq k \leq 2^n-1$. Then applying the Fourier Transform $F$ yields a big superposition:

$$ F|k\rangle = \sum_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot k}{2^n-1}}|u\rangle $$

Take $n=1$ and $k\in\{0,1\}$, and you see that $F|0\rangle = |+\rangle$ and $F|1\rangle=|-\rangle$. As you can see, it is performs exactly the same transformation as a Hadamard gate. Moreover, for any number of qubits $n$, the Fourier still behaves as the Hadamard only for the state $0$, on which it acts as follows:

$$ F|0\rangle_n = \sum_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot 0}{2^n-1}}|u\rangle_n = \sum_{u=0}^{2^n-1}e^{0}|u\rangle_n = \sum_{u=0}^{2^n-1}|u\rangle_n $$

I have not normalized my states in these examples, but you should definitely do so on an exam.


Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states

This isn't about induction, it's about proving that the correct DFA must have enough memory to remember everything about the last $n+1$ characters. The very number $2^{n+1}$ should have been a clue to this.
Imagine that the DFA has just now read some prefix that's longer than $n+1$, but it doesn't yet know if there are any more characters left. Ask the question: what must the DFA currently remember?

Well, clearly, it must remember what it read $n$ characters ago, to decide whether to accept or reject if the string just ends right now
It also must remember what was $n-1$ characters ago, just in case the string ends 1 character later
And it must remember what was $n-2$ characters ago, just in case the string ends 2 characters later
And it must remember what was $n-3$ ...

As you can see, by that kind of logic it must be absolutely sure about each of $2^{n+1}$ bits. To formalize this deduction, try to prove the following:
LEMMA: If $a$ and $b$ are two different strings of length $n+1$, then they should lead the DFA in question to two different states.
The method for proving this lemma is to append things to $a$ and $b$, such that, for example, string $ac$ must be accepted and string $bc$ must be rejected. If the automaton knows the difference between $ac$ and $bc$, then it must have known the difference between $a$ and $b$. Look up "right invariant equivalence" if you don't already know that concept.
Once you prove the lemma, the rest is obvious. There are $2^{n+1}$ different strings which all lead to different states. Therefore, there are at least $2^{n+1}$ different states.


Can we say anything about the complement of a regular language?

Complementing an NFA may involve an exponential blowup.
While there are concrete examples for this, it can also be deduced (in a way) by the fact that NFA universality is PSPACE complete. Indeed, if complementing an NFA could be done in polynomial time, then universality would also be possible in polynomial time.
This is not exact, since complemetation could also be only sub-exponential, but not polynomial.
As for a concrete example: Let $p_1,p_2,\dots$ be an enumeration of the prime numbers.
Consider the language: $L_k=\{1^n: \exists 1\le i\le k\ \text{ s.t. }\ p_i \not\mid n\}$. It is easy to construct an NFA for $L_k$ with $\sum_{i=1}^kp_i$ states.
However, it is also not hard to prove that a minimal NFA for $\overline{L_k}$ needs $\prod_{i=1}^k p_i$ states, which is exponential in $\sum_{i=1}^kp_i$.


Here's an argument to prove my speculation in comments that no such unique tilings exist for any non-square $n\gt 5$.  Firstly, as noted by Sasho in comments, $n$ must be restricted, because no such tilings exist if $n\equiv2$ or $3\pmod 4$.  If $n$ is a perfect square $n=k^2$ then obviously the $k\times k$ square is uniquely tileable, so $f(n)$ is clearly defined and non-zero in these cases.  To complete the argument, it just remains to show that no tiling involving $1$ or more $2\times 2$ tiles can be unique.

First, consider the case $n\equiv 0\pmod 4$, say $n=4k$.  If we have a tiling of an $m\times m$ square using $n\ 1\times 1$ tiles, obviously $m$ must be even, say $m=2j$; then we can construct tilings by building a $j\times j$ tiling of $2\times2$ tiles and then replacing $k$ of these by 'blocks' of four $1\times 1$ tiles.  It's clear that different replacements can always lead to distinct tilings except in the cases $m=4, n=12$ or $m=4, n=4$ where there's either a single $2\times 2$ tile or a single 'block of four' left over; in these cases, though, there's a different inequivalent tiling, one which puts a $2\times 2$ tile in the middle of an edge rather than in a corner.

Finally, suppose $n\equiv 1\pmod 4$, in particular presume $n=4t+1$ (and with $t\gt 1$ to prevent a slightly trivial case where there's simply 'not enough room' in the square for the following argument to go through).  Then no square of size $(2t+1)^2$ or smaller can be uniquely tileable: consider a tiling with $1\times 1$ tiles across the top of the square and down the right of the square (with any extra $1\times 1$ tiles just tucked onto the right side — they can't affect the argument).  Now the $2\times 3$ 'block' in the top-left of the square (consisting of the two $1\times 1$ tiles on the top and the $2\times 2$ tile beneath them) can be 'flipped' to produce a tiling that will necessarily be different from the tiling we've constructed.  Finally, no square of size larger than $(2t+1)^2$ can be tileable at all: suppose we're trying to tile a square of size $(2s+1)^2$ for $s\gt t$; then by the pigeonhole principle we can't fit any more than $s^2\ 2\times 2$ tiles onto the square, which means that there are $(2s+1)^2-4s^2 = 4s^2+4s+1-4s^2=4s+1$ squares left over - but since $s\gt t$, $4s+1\gt 4t+1=n$, the number of $1\times 1$ tiles we have available.

Thus, the only unique tilings that exist for $n\gt 5$ are those that use no $2\times 2$ tiles at all, and $f(n)$ is only non-zero when $n$ is a square (in which case it equals $\sqrt{n}$).


Lambda term satisfying two equations using Bohm Trees

This task can be solved very well by observation and inserting simple functions.

First, $\Delta$ should obviously be a function applying its argument to at least two terms (because it's $\lambda x y.$). So let's set $\Delta = \lambda f.fXY$, which gives $$X(Y(\lambda u.YuY)X)X=y_1
\\
X(Y(\lambda u.Yu(\lambda abc.cab))X)X = y_2$$
Now we see that $Y$ is mostly applied to other terms that seem complex enough to solve this task for themselves, so why not just set $Y=I(=\lambda t.t)$?
This leads us to $$X(XI)X=y_1
\\
X(X(\lambda abc.cab))X = y_2$$
$X$ is now an abstraction of at least two variables, but we see that the second one (it's always $X$ in the first application) can probably be ignored. Setting $X=\lambda p q.Mp$: $$M(\lambda q.MI)=y_1
\\
M(\lambda q.M(\lambda abc.cab)) = y_2$$
The same ways we did with $\Delta$, we see that M takes an argument with at most three abstractions, so we make $M=\lambda f.(f P Q R)$. Doing several beta reductions, this yields $$PQRQR=y_1
\\
RPQQR = y_2$$
with the obvious solutions $P=\lambda a b c d.y_1$ and $R=\lambda a b c d.y_2$ and the free parameter $Q$.
Now finally, we can insert these terms back into $M$, $X$ and $\Delta$ to yield the solution $$\Delta=\lambda f.f(\lambda p q.p(\lambda a b c d.y_1)I(\lambda a b c d.y_2))I$$ (setting $Q=I$ for brevity's sake).
There could very well be a smaller solution, but I think the derivation process is the simplest you can get with this one.


Is there any efficient way of calculating the n-th fibonacci number modulo another number?

Here are two suggestions:

The linear algebra approach. It is known that
$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n &F_{n-1} \end{bmatrix}. $$
You can compute the matrix power using repeated squaring, doing all the calculations modulo your modulus.

Closed form. If your modulus is odd and 5 is a quadratic residue (i.e., 5 has a modular square root) then you can use the explicit formula
$$
F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}.
$$
You can then use Carmichael's function to reduce $n$, and then repeated squaring. Care must be taken when the modulus isn't a prime power.

It is possible that a similar approach works more generally.


Reducing CLIQUE to Super Connector problem

The simplest NP-hardness reduction is as follows. Suppose we are given an instance $(G,k)$ of CLIQUE. If $k \leq c$ then we solve CLIQUE by brute force in time $O(n^c)$. Otherwise, $G$ has a $k$-clique iff it has a $k$-clique consisting of super-connectors. This is because any vertex in a $k$-clique must have degree at least $k-1 \geq c$, and so is a super-concentrator.


Logic, "and" operator between a set of formulas and a formula

A set $S$ of formulas (propositional logic) is consistent if there is a truth assignment under which all formulas in $S$ are true, in other words if there is a model of $S$. Alternatively, $\{\beta_1, \beta_2, ...,  \beta_n \}$ is consistent, iff $\beta_1 \wedge \beta_2 \wedge ... \wedge \beta_n$ is satisfiable.

You could just find a truth assignment such that $\alpha \wedge \beta_1 \wedge \beta_2 \wedge \beta_3$ is true. If the number of variables is small then you can check it by hand by creating a truth-table, or use Method of analytic tableaux. Also, note that the Satisfiability problem (SAT) is NP complete.

You can also use a resolution procedure to show that a formula is unsatisfiable (inconsistent).


What do you call a DAG with a single root/source?

In a directed graph we do not speak of roots and leaves, but of sources and sinks.

I'm not aware of any term that designates a DAG with only a single source, but you could just call it that: "a DAG with a single source".


How to verify a property about a certain order of events in TCTL / UPPAAL?

Under the assumption that your property can be interpreted in an intuitive way, as it is written, it seems that you can formulate it both in LTL, as:

a => F(b && F(c && F d))

and in CTL, which in the given example is equivalent to TCTL, due to lack of timing constraints (you may assume they are of form [0, inf) and consider a TCTL formula as a CTL formula), as:

a => AF(b && AF(c && AF d))

but not in the logic supported in UPPAAL. Your property requires nested quantifiers, which are not supported in UPPAAL (as you suggested).

In general, it is not possible to model properties like a => F b ("whenever a is true, b should be true eventually") directly in UPPAAL. A workaround that might work is to consider all states in which a holds as the initial states and then formulate and check AF b. Of course, since you have multiple of such nested formulas, this does not seem possible in your case.
Note that such properties require that for all reachable states X where a is true, there should be a state y (reachable from X), such that b is true in y (which does not fall into category of supported classes of properties in UPPAAL such as "liveness" and "safety").

Since you are trying to express a property that requires a nested CTL formula, UPPAAL is not suitable to formulate and model-check it. You should try SPIN or other tools that support full CTL.


Is this in-place merge algorithm efficient or not?

This algorithm has been previously published in literature; for a detailed worst-case runtime analysis, see [1], [2], and [3]. It is referred to as "Symmerge" or "merging by decomposition". When the two subarrays to be merged are both of length $n$, the algorithm runs in worst-case $O(n \log n)$-time and uses $O(\log n)$ space (due to recursion).

If we use this algorithm for mergesort, the overall mergesort recurrence becomes $T(n)=2T(n/2)+O(n\log n)$; using the Extended master theorem, we know $T(n)=O(n \log^2 n)$.

[1]: P.-S. Kim and A. Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.4612&rep=rep1&type=pdf

[2]: K. Dudzinski and A. Dydek, "On a stable storage merging algorithm". Information Processing Letters 12 (1981) 5–8.

[3]: S. Dvorak and B. Durian, "Merging by Decomposition Revisited."  The Computer Journal, Volume 31, Issue 6, 1988, Pages 553–556, https://doi.org/10.1093/comjnl/31.6.553


Why are recursive types needed as primitives for proofs in dependent type systems?

I'm not an expert, but I'll share what I understood so far with an example.

Let's consider the boolean type in CoC, using its standard encoding:
$$
\begin{array}{l}
\mathbb{B} = \Pi_{\tau:*} \tau \to \tau \to \tau
\\
\mathsf{tt} = \lambda \tau:*,x:\tau,y:\tau.\ x
\\
\mathsf{ff} = \lambda \tau:*,x:\tau,y:\tau.\ y
\end{array}
$$
We might expect to be able to prove
$$
\Pi_{b : \mathbb{B}} b={\sf tt} \lor b = {\sf ff} \qquad(*)
$$
Indeed, this quickly follows from the dependent elimination/induction principle we have e.g. in CiC
$$
\mathbb{B}_{ind} : \Pi_{P:\mathbb{B}\to*} P({\sf tt}) \rightarrow P({\sf ff}) \rightarrow \Pi_{b:\mathbb{B}} P(b)
$$

However, we can not really expect (*) to hold in all models of CoC!
Intuitively, a value in $\mathbb{B}$ should roughly be a family of functions
$\{f_\tau\}_{\tau}$ assigning to each type $\tau$ a value in the interpretation of $\tau\to\tau\to\tau$. But this does not force $f_\tau$ to be one between the values of $\sf tt,ff$. We could have e.g. (informally)
$$
f_{\mathbb{N}}(n)(m) = n+m
$$

To be sure that the values of $\sf tt,ff$ are the only possible values, we need to restrict ourselves to parametric models. Indeed (I think) the property $(*)$ can be proven from the free theorem associated to the polytype $\mathbb{B}$.

However, as far as I understand, CoC does not rule out ad-hoc models, where parametricity does not hold. In some of those, $(*)$ is simply false. By soundness, in the presence of a countermodel, we conclude that $(*)$ is not inhabited in CoC. Consequently, there's no $\mathbb{B}_{ind}$ term in CoC, either.


How can I compute logarithm when comparison is undecidable?

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range.
For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{2},\frac{3}{2}\right]$, or $C = \left[\frac{5}{4},\infty\right)$ with little difficulty. Use AGM if it's in $C$, the transformation if it's in $A$, and if it's in $B$, use this transformation:
$$\log (x) = \log (2x) - \log 2$$


What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

Let $r$ be the root of your circuit (without loss of generality, an OR gate), and let $V_i$ consist of those gates at distance $i$ from $r$. Assign (in your mind) a layer for each gate: layer 0 for the root, layer $2i-1$ for an AND gate in $V_i$, and layer $2i$ for an OR gate in $V_i$. The result is almost what you want – the only difference is that edges could span more than one layer.

In order to fix the problem, for each gate $g$, create gates in all layers above it (i.e., with smaller number) of the correct type, and connect them in a path (so all the new gates will have in-degree 1). Now you can arrange that each edge span exactly one layer.

Starting with a circuit of depth $D$ and $n$ gates, we have created a circuit of depth $2D$ and at most $nD$ gates. In particular, if the original circuit had polynomial size then so does the new one (with a different polynomial), and if the original circuit had constant depth (or logarithmic, or polylogarithmic) then so does the new one.


Least squares fit of a 1D lattice of points to a 2D dataset

Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are.  Then, use any standard black-box optimization algorithm (e.g., gradient descent) to find $m,c,d,i$ that minimize the objective function.  You might choose the initial values of $m,c$ based on a least-squares fit, and choose the initial values $d,i$ based on a best guess (maybe by projecting the points to the line $y=mx+c$ and then taking a FFT and looking for peaks, to try to find the periodicity), and then run gradient descent from there.

So, it all reduces to choosing an objective function $\Psi(m,c,d,i)$ that captures what you want.  We can't give that for you, since you haven't fully specified the problem.  For instance, you say you want "more or less the same number of data points" in each cluster, but you haven't specified how to trade off the errors: of course, we can't achieve this exactly, so we need some way to measure and compare different candidate solutions.

For instance, given a set $P$ of points, you might use an objective function like

$$\Psi(m,c,d,i) = \sum_{p \in P} d_{m,c,d,i}(p)^2$$

where $d_{m,c,d,i}(p)$ is the distance from $p$ to the nearest grid point on the line $y=mx+c$, i.e.,

$$d_{m,c,d,i}(p) = \min\{\sqrt{(p_x-x)^2 +(p_y-(mx+c))^2} : x=d + ij, j \in \mathbb{Z}\}$$

where $p=(p_x,p_y)$ in $(x,y)$-coordinates.

This doesn't do anything special about outliers; they incur a very large penalty.  That might be undesirable -- it might lead to poor results in the presence of outliers.  There are various methods for dealing with outliers.  One simple one is to fit a line using a robust least-squares fit, find outliers and remove them as part of a pre-processing step, and then run the procedure on the result.

Also, you mention fear of overfitting the data set. Another way to avoid overfitting is to add a regularization term that penalizes values of $d,i$ that are considered a priori unlikely.  For instance, you might add a penalty term that is proportional to $1/i$ or to $-i$.  The penalty term gets added to the objective function.  Then, when you minimize the objective function, this will exert some pressure to avoid choosing small values of $i$.


Finding median of three sorted array (the same length)

The recurrence relation can be solved as follows: for large $n$,

$$T(n) = T\left(\frac{2}{3}n\right) + 1 = T\left(\frac{2^{2}}{3^{2}}n\right) + 2 = \cdots = T\left(\left(\frac{2}{3}\right)^kn\right)+k$$

This iterative process ends when a $T(m)$ is called with $m \leq 1$. Now for what $k$ do we have $\frac{2^{k}}{3^{k}}n \leq 1$? It is $ ^{\frac{3}{2}}log(n)$. (verify this for yourself)

A good way to do this is using an insight from the $\texttt{MergeSort}$ algorithm. It sorts an algorithm by consequtively merging increasingly long sorted substrings. Here's how it goes: you keep three indices, say $i,j,k$, which start at $0$. You iterate them over the three arrays, each time incrementing the index which points to the highest value of its respective array, until you've encountered half of all elements, i.e. $i+j+k=\frac{3n}{2}$. When that has happened, you have encountered the median. Here's this algorithm as pseudocode:

$\texttt{TernaryMedian}(\texttt{array } A, \texttt{array } B, \texttt{array } C):$

int $i, j, k :=0$

while $i+j+k < \frac{3n}{2}$ do

$\quad$ if $A_i > B_j$ then

$\quad\quad$ if $A_i > C_k$ then $i := i + 1$

$\quad\quad$ else $k := k + 1$

$\quad$ else if $B_j > C_k$ then $j := j + 1$

$\quad$ else $k := k + 1$

end while

$median := max(A_i, B_j, C_k)$

This algorithm runs in time $O(n)$ and makes $3n$ comparisons in the best case and $\frac{9}{2}n$ comparisons in the worst; I'll leave the average case to you. This algorithm can be improved if you keep a pointer to the array containing the highest value of any of the pointers but which was not the subject of last iteration's increment. I'll leave it up to you to figure out why. Then you get $\frac{3}{2}n+1$ comparisons in the best case and $3n$ comparisons in the worst.

It may help to first look up $\texttt{MergeSort}$ on Wikipedia for merging two substrings, and then think about how you would merge three substrings. Hope this helps.


A state machine that is either DFA or NFA: is it possible?

Any piece of code can never be non-deterministic (a non-deterministic process can "multiply itself" by a constant factor every step, and obviously computers can't just multiply by their own free will).
Hence it is a DFA.

Also, your lexer will start always at the initial state $s_0$, and from it, depending on what it reads - it moves to different states.


It is the property "accepting by empty stack" what makes the DPDA weaker. If a language $L$ is accepted by a DPDA by empty stack, then $L$ has the prefix property. The following language $L = \{ b^n \mid n \geq 0\}$ clearly does not have prefix property since if $b^k \in L$ then $b^m \in L$ as well for $m < k$. So this language is not accepted by a DPDA by empty stack.

Assume that $w \in L$ and $wv \in L$ and $L$ does not have prefix property. Assume also that $L$ is accepted by some DPDA $M$ by empty stack. Since $w$ is accepted by $M$, there is a computation path from $(q_0, w, S_0)$ to $(q_k, \epsilon, \epsilon)$. Since $M$ is deterministic, the only possible computation for input $wv$ is $(q_0, w, S_0) \Rightarrow^* (q_k, v, \epsilon)$. But $M$ has already had empty stack and so it cannot move further from $(q_k, v, \epsilon)$ and hence does not accept $wv$.

Definition: A language $L$ has prefix property if $w \in L$ implies no proper prefix of $w$ is in $L$.


How can a set of N players be split into M teams, given certain rules?

Denote each person as a single vertex and connect them by an edge if they are not allowed to be in the same team. If several people have to be on the same team, use a single vertex to represent all of them. Then color the resulting graph by $k$ colors, where $k$ is the number of teams.This problem is the graph coloring problem. To complicate things you may require color certain vertices in the same color. Please follow this for other types of colorings.


Ignoring exceptions is unsound. Example:

let g = {
     raise E;
}
let f = {
     x := interesting_stuff();
     g();
     x := 0;
}

When analyzing f, you need to take into account the fact that g raises an exception, otherwise you would incorrectly conclude that x is always 0 on return from f.

I don't know that there is a “standard” technique for dealing with exceptions. There's some literature on the topic, I don't have any more idea of what papers are relevant than I can find by a Google search.

Formally, exceptions can be turned into conditional statements that propagate up the call chain, which of course blows up the control flow graph. In many concrete cases, the exception case is the less interesting case, where a lot of data gets killed, so it should be handled lazily in a forward approach (no need to analyze the liveness on the exception path if the handler kills the data).


Do we know something about this refutation method for SAT?

As far as I can tell the earliest mention of the procedure you outline, later described in the literature as variable elimination by clause distribution, was in the paper "ZRes: The old Davis-Putnam procedure meets ZBDD" by Philippe Chatalic and Laurent Simon.  The procedure was described again, along with other formula simplification techniques, in "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas Eén and Armin Biere.

The procedure was shown to be a workable way to improve SAT solver performance if care is taken to minimize clause growth as the implicants of removed terms are distributed, or to use data structures that efficiently manage large clause sets.


Coq cannot always know whether a program will terminate, because that would be a solution to the halting problem.

Coq is able to notice that a certain class of programs will terminate. The main heuristic it uses is that if one of the arguments to the function must get smaller on each recursive call, the program must terminate.

If you have a function that terminates, but Coq cannot tell that it terminates, you can add an extra argument that always get smaller on recursive calls. Doing this amounts to providing a proof that the function terminates.

So basically, Coq accepts any program that the user can prove the termination of.


Is string matching and replacement considered in formal languages?

Match & replace is a special case of rational transduction, a quite powerful class of string mappings with a number of nice properties.

The classes of regular, context-free and recursive enumerable languages are all closed against rational transduction (source), so this carries over to match & replace.

It does not seem as if the necessary elementary operations had a representation in formal language theory.


How do we determine whether a heuristic is better than another in A* search Algorithm?

A good heuristic should approximate the actual distance to the goal as closely as possible, without going over it.

If heuristic1 returns a greater or equal value than heuristic2 for every input (while still being valid), then heuristic1 is better. In your case, Manhattan distance is better than Euclidean distance because the value it returns is never smaller than Euclidean distance and is sometimes larger. (Unless you can move diagonally in the maze, in which case Manhattan distance is an invalid heuristic and Euclidean distance might be as well.)

If heuristic1 returns a larger value for some inputs, and heuristic2 returns a larger value for others (and both are valid), then heuristic3(x) = max(heuristic1(x), heuristic2(x)) is better than either of them.

If the heuristics are slow, it's more complicated. Since heuristic3 will be even slower than heuristic1 or heuristic2 alone, it could end up being worse overall if it doesn't improve the estimate by very much. There's no unambiguous way to choose the best heuristic in this case. You basically have to benchmark and decide how much cleverness you can afford.


What are the gates used to implement Shor's algorithm?

There are several correct answers to this question because there are several candidate sets available for use as a universal set of quantum operators and because there isn't an agreed upon best implementation for the primitives needed by Shor's algorithm. Different circuits will trade-off circuit-depth for ancillary qubits and vice versa.  Ultimately, the exact implementation is likely to depend on the architecture of the quantum computer.

What that in mind, you can probably find a version of the details you're looking for in Fast Modular Exponentiation Architecture for Shor's Factoring Algorithm by Pavlidis and Gizopoulos.  The exact circuit layout is lengthy and complex and probably too much for an answer here. The paper has lots of diagrams though and a quick scan should should provide you with a rough feel for the circuit construction. Unsurprisingly, the circuit makes heavy use of Hadamard gates and controlled phase-shift operators both to implement the inverse QFT and the modular exponentiation circuit.


For every undirected unweighted graph is every MST also a SPT

Counter example: V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}.
A MST of this graph, rooted at a, could be: {(a,b), (a,d), (b,c)}. But this is not a SPT because the path a->c is of length 2 instead of 1 (a and c are directly connected in the original graph).


Your understanding of reducing the given problem to a subproblem is flawed. Say you have to place the tiles, if you start from the centre and keep on placing the tiles, finally the arrangement  you have can also be obtained by placing tiles from the left hand side.  You don't want to double count. So the recurrence relation you mentioned is correct.


Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

You can use any balanced binary search tree data structure (doesn't have to be AVL tree).  Some such data structures are easier to implement (maybe a AA tree, left-leaning red-black tree, or splay tree?).  If you don't care about worst-case running time, it doesn't need to be balanced.  One pragmatic solution might be to use skip lists.

Are you sure the exam required students to implement their solution?  In my experience, exams in the algorithms and data structure courses I'm familiar with rarely require implementing the solution -- it is enough to describe the solution clearly.  A solution based on augmenting an AVL tree can be described in a fairly simple way: you say "take a AVL tree, and modify it in such-and-such a way", and that doesn't require re-describing all the details of how AVL trees work.  Only you know what the typical expectations are for the kind of exam you are looking at.


What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

The method you mention is based on the following theorem:

  If $f \geq 0$ is non-decreasing, $g \geq 0$ is non-increasing, and $f(t) = g(t) = y$, then
  $$ y \leq \min_x [f(x) + g(x)] \leq 2y. $$

Note that there is (at most) a unique point $t$ such that $f(t) = g(t)$.

In your case, $f(k) = k$ is increasing and $g(k) = n/k$ is decreasing, and $f(\sqrt{n}) = g(\sqrt{n}) = \sqrt{n}$, so $\sqrt{n} \leq \min_k [k + n/k] \leq 2\sqrt{n}$. In fact, calculus shows that the minimum is indeed $2\sqrt{n}$.

The proof of the theorem is very simple: if $x \geq t$ then $f(x) + g(x) \geq f(t) = y$, whereas if $x \leq t$ then $f(x) + g(x) \geq g(t) = y$.


The cached data might be needed again in the future and keeping it doesn't cause any particular performance problem, so you may as well keep it until you need the space for something else.


Sorting an array of length $n$ in $O(m+n)$ time

Use counting sort. In $O(n)$, count the number of elements of each value, and then in $O(m+n)$ go over the histogram and translate it to the sorted array.


Maximum weight perfect matching in general graphs

AB, CD, EF  is the unique perfect matching
Assigning $x_e = 0.5$ to all edges except CD gives the optimal LP solution.


Here's a different way to think about it. Every step, the Turing machine looks at the current cell of the tape, then does the following:

Optionally, move the head left or right
Select a new state, or accept, or reject

If it accepts or rejects, it halts and doesn't do anything further. But this won't necessarily happen: it's also possible for it to get stuck in a loop it can never get out of. Imagine the following machine:

  State 0: if you see a 0, don't move, go to state 0
  State 0: if you see a 1, don't move, go to state 0

It's never going to get out of state zero, it'll just stay in it forever.

It's possible for a single machine to do all three, depending on its input:

  State 0: if you see a 0, don't move, go to state 0
  State 0: if you see a 1, move right, go to state 1
  State 1: if you see a 0, don't move, reject
  State 1: if you see a 1, don't move, accept

Given the input 0 it'll loop, given the input 10 it'll reject, given the input 11 it'll accept.


Can a Turing machine decide if a LOOP program stops for the integer input 0

If all LOOP programs terminate that there is a Turing machine that decides whether a LOOP program stops on input 0: it just always accepts. For WHILE programs the picture is rather different - I'll let you find out yourself. (Perhaps your professor really meant WHILE programs.)


data structure admitting top items with prefix

You can achieve $O(\log n)$ time insert, $O(\log n)$ time delete, $O(n)$ space,  and $O(m \log m + \log n)$ time search by augmenting the trie.

Store in each leaf the weight of the corresponding item.  Also, at each internal node, add a field with a pointer to the leaf of maximum weight that's reachable from that node.

It's easy to see how to perform insertion in $O(\log n)$ time, and it's easy to see why this still uses only $O(n)$ space.

Search for the top $m$ items with a certain prefix can be done in $O(m \log m + \log n)$ time.  First, find the node $x$ corresponding to that prefix.  Use that node to identify the first item of the output (the highest-weight item with that prefix).  Next, look at the children $y_1,\dots,y_k$ of node $x$, and for each, look at the highest-weight item with that prefix.  Add these $k$ nodes to a priority queue, keyed on the weight of the corresponding item.  Extract the highest-weight item from the queue; that's the second item of the output.  Look at the children of the node you just extracted, and add them to the queue.  Repeat until you have output $m$ items; in each iteration, you extract the node of highest weight from the priority queue, output the corresponding item, and add the children of that node to the priority queue.  Remove duplicates as you go.  Stop once you've output $m$ items.  You do $O(\log n)$ time to find the first node corresponding to the prefix, and then each subsequent iteration takes $O(\log m)$ time (since operations on a priority queue of size $O(m)$ can be done in $O(\log m)$ time), and you do $m$ iterations, for a total running time of $O(\log n + m \log m)$.

Deletion can be done in $O(\log n)$ time.  To delete an item, traverse the trie to find that item.  Then, update each node that you visited during that traversal.  To update a node $x$, if the maximum-weight leaf under $x$ is the the item you're deleting, check the children of $x$ to find the next-highest-weight leaf under $x$, and update $x$.  This does $O(1)$ work per node you traverse, and the traversal visits $O(\log n)$ nodes, so the total time for deletion is $O(\log n)$ time.


Generate random weighted graphs representing a road network

One approach is to generate an arbitrary graph $G$ with arbitrary (positive) lengths on each edge.  Then, compute all-pairs shortest paths, and build a new fully-connected graph $G'$ where the length of the edge $u \to v$ in $G'$ is equal to the length of the shortest path from $u$ to $v$ in $G$.

The nice thing about this is that you're guaranteed by construction that $G'$ will satisfy the triangle inequality.

If you are happy with generating fully connected graphs, you can then output $G'$ as your random graph.  If you don't want the graphs to be fully connected, you could keep only some subset of the edges of $G'$ and delete the rest, then output the result.


An inductive definition takes some elementary objects of the structure to be defined and combines those to obtain new elements of said structure.

Example: Definition of the syntax of many logics.

On the contrary, a recursive definition is a rule how to obtain a specific object based on somehow "smaller" objects of the same structure.

To see the difference more clearly, consider the following:
To define the valid arithmetical expressions, you would state something like

Any real number is a valid arithmetical expression
When $\varphi$ and $\psi$ are valid arithmetical expressions, so are $(\varphi + \psi)$, $(\varphi - \psi)$, etc.

This is an inductive definition of arithmetic expressions, as you build up the class of valid expressions from the bottom (base cases) upwards.
Recursion, on the other hand, works from the top to the bottom. In this case, you would recursively check whether an arbitrary string is a valid expression or not.

When you define an object recursively, the object is determined by easier to compose objects of the same structure, like the Fibonacci numbers. You can only get the value of $\text{Fib}(n)$ by knowing $\text{Fib}(n-1)$ and $\text{Fib}(n-2)$.


Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.

First, show that $\phi(\phi(n)) < n/2$. This can be done as such:

Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$)

Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) < n/2$.
Suppose $n$ is odd and $n > 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) < n/2$.

So we get the desired result.

Now suppose $n\geq2$. You can write:
$$T(n) = T(\phi(n))+\log(\phi(n))^3 = T(\phi(\phi(n)))+\log(\phi(\phi(n)))^3 + \log(\phi(n))^3.$$
$$T(n) \leq T(n/2) + 2\log(n)^3.$$

Now you can apply the master theorem here to get:
$$T(n) = O(log(n)^4).$$


Is it possible to use a space-filling curve to index a 2D grid which is not $2^x$ by $2^y$?

What kind of indexing do you need? If it is just a lookup, your can interleave the bits of you coordinates to get a z-ordered Morton value. These could be stored in binary trie (critbit-tree) that uses prefix sharing. Traversing the tree gives you Morton-order, and the possible prefix sharing should reduce memory consumption.
I implemented one in Java: critbit

If you also need geometric queries (kNN, window queries, range queries), you could try the PH-Tree, it's like a bit like quadtree, but uses prefix sharing like a trie and some other things to be much more efficient (memory and speed) than a quadtree. The tree uses internally a Morton ordering so a full traversal or Window queries will always return Morton-ordered results.


Size of maximum clique given a fixed amount of edges?

The graph can have clique number 1 (if we allow the graph to be disconnected), or 2 (consider a long path).  The graph can have a clique of size at most
$$\frac{1}{2} (\sqrt{8m + 1} + 1),$$
where $m = |E|$, provided of course that $|V|$ is large enough.


How is an OS page stored in a k-way set-associative cache?

There are few things to be cleared first.

Lets assume a away set associative cache with bwide cache-lines and c number of cache lines. In this configuration, size of the cache is a X b X c. Number of bits needed to represent the number of cachelines, is called index bits. (ex: 1024 cachelines will need 10 bits). When we need to load data, the index bits of the memory address tells us in which cache line this data will be stored. Since our cache is away, there are a number of cachelines, all indexed by this index bits, this data can be stored. If there are empty lines, we will use them, otherwise we have to replace and entry and store the newly fetched data.

Now coming back to your original question,

Think of "loading the page to cache" as reading the entire page in cacheline quantities. Assuming all the cache entries are invalid, first n reads will be stored in the first entry in each block of cachelines, the second n reads will be stored in the second entry in each block.

In a 2-way set assoc cache with 4 cachelines, this is how it would look like.

cacheline 1 set0 - addr 0
cacheline 1 set1 - addr 4
cacheline 2 set0 - addr 1
cacheline 2 set1 - addr 5
cacheline 3 set0 - addr 2
cacheline 3 set1 - addr 5
cacheline 4 set0 - addr 3
cacheline 4 set1 - addr 7


Is every subset of a decidable set, also decidable?

This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder.
Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.

Similarly, the converse is not true - that is, smaller languages are not "harder" as well. For example, the language "nothing" is also easily decidable.

So the containment relation does not preserve hardness. Indeed - that's why we use the relatively complicated notion of reductions between languages, rather than showing containment.

So the simple answer to your question is that it's false, and an example, as in the comments, is $\Sigma^*$, which is decidable, but contains an undecidable language (indeed, every undecidable language).


Why is the sequence "3,3,4,5,2" considered a bitonic sequence?

The words "increasing" and "decreasing" are used in inconsistent ways. Probably, you're assuming one definition while the author of the text that's confusing you is using the other.  Say that the sequence $a_1, \dots, a_n$ is

type A if $a_1\leq a_2\leq \dots\leq a_n$;
type B if $a_1<a_2<\dots<a_n$.

The problem is that

some people refer to type A sequences as "nondecreasing" and type B sequences as "strictly increasing", which is unambiguous;
some people call type A "nondecreasing" and type B "increasing";
some people call type A "increasing" and type B "strictly increasing".

This means that the term "increasing" is ambiguous because some people use it for type A and some people use it for type B. (And ditto for variants of "decreasing".)

The same problem occurs, though to a much smaller extent; with the terms "nonnegative", "positive" and "strictly positive": the first definitely means $\geq 0$, the last definitely means $>0$; the majority of people use "positive" to mean $>0$ but a few use it for $\geq 0$. (And ditto for variants of "negative".)


Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?

Hint: let $n={k \choose k/2}$.  Consider the state of the algorithm after reading $n/2$ of the sequences.  How many possible states are there, that it could be in at that point?


The HAMPATH complement ("G does not contain an Hamiltonian path from s to t") is in co-NP; to be more precise it is  co-NP complete (it is easy to prove that $L$ is NP-complete if and only if its complement $\bar{L}$ is co-NP-complete).

The question if it is in NP is open.

But since HAMPATH is NP-complete, if its complement is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\mbox{-}NP}$


Is it possible to simulate a CPU with software?

Yes, its possible to simulate a CPU with software.  A CPU is just an electronic implementation of a large, but finite, number of rules of the form "If this condition is true, modify the state like this" and software can certainly do that. Wouldn't it be surprising if it couldn't? CPUs are designed to support the sorts of things we want to do with software, so it would be very strange if they were radically different.

Indeed any system that has a finite state (i.e., can be described with a finite amount of data) and is manipulated by a finite set of rules can be simulated in software. Going further, I don't think there is any known physical process that can't, at least in principle, be simulated in software.


Number of Configurations of LBA(Linear Bounded Automaton)

If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options for the first three symbols and so on. If you are not convinced, try it with for example a $3$-symbol alphabet.

Since your tape has length $n$ there are $n$ possible head positions, so you multiply the number of strings on the tape with $n$.

Finally, there are $q$ states, so for every possible string on tape and every possible head position, we can be in either of the $q$ states, making $qng^n$ configurations of the Turing machine.


We can reduce 3SAT to ExactOneSAT (3SAT $\leq_P$ ExactOneSAT) as follows. Replace each clause $C_m$ by $(z_{m,1} \lor z_{m,2} \lor z_{m,3})$ and ensure that if $C_m$ is, say, $(v_i \lor \overline{v_j} \lor v_k)$ then  $(\neg v_i \Rightarrow \neg z_{m,1})$, $(\neg \overline{v_j} \Rightarrow \neg z_{m,2})$ and $(\neg v_k \Rightarrow \neg z_{m,3})$. Thus, for example, if $v_i$ is true then $z_{m,1}$ can be true or false, but if $v_i$ is false then $z_{m,1}$ must be false.

Thus replace  $(X_{m}^1 \lor X_{m}^2 \lor X_{m}^3)$  in clause $C_m$ by
$$(z_{m,1} \lor z_{m,2} \lor z_{m,3}) \land (\neg X_{m}^1 \lor y_{m,1} \lor z_{m,1}) \land ( \neg X_{m}^2 \lor y_{m,2} \lor z_{m,2}) \land ( \neg X_{m}^3 \lor  y_{m,3} \lor z_{m,3})$$
where $X^1_m, X^2_m, X^3_m$ are the three literals in the clause $C_m$. Note that $X$'s are literals in the clauses and can have negations, whereas $y$'s and $z$'s are variables.

If $\phi'$ is the modified boolean CNF, then this will give us $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT. This along with the fact that above transformation is polynomial-time gives us a proof of NP-completeness.

Let us see how $\phi \in 3SAT \Rightarrow \phi' \in$ ExactOneSAT.

Assume we have a satisfying assignment for $\phi$.

For example, say $X_m^1$ is true and $X_m^2$  and $X_m^3$ are  false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = False, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say $X_m^1$ and $X_m^2$ are true and $X_m^3$ is false. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = False, $z_{m,3}$ = False

For example, say all $X_m^1$, $X_m^2$ and $X_m^3$ are true. Then we can make following assignments:

$y_{m,1}$ = False, $z_{m,1}$ = True
$y_{m,2}$ = True, $z_{m,2}$ = False
$y_{m,3}$ = True, $z_{m,3}$ = False

So we can see that we can find a satisfying assignment for $\phi'$ where only one literal is true in every clause.

Let us now see how $\phi' \in$ ExactOneSAT $\Rightarrow \phi \in $ 3SAT

Assume we have a satisfying assignment for $\phi'$ where exactly one literal is true in every clause.

Let us say $z_{m,1}$ is true and $z_{m,2}$ and $z_{m,3}$ are false. Then definitely $X_m^1$ in the second clause should be true, implying that same assignment satisfies $C_m$.

Thus we have $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT.

We have actually prove ExactOne3SAT is NP-complete by this because every clause has 3 literals.


Efficient way to choose set from including conditions on sets

I think it should be straightforward to reduce One-in-3SAT to this problem: For example, you can create a size-2 set $X_i$ for each variable $x_i$ from the One-in-3SAT instance, and set $a_i=1$ to force that either the variable or its negation is chosen.  $n$ will be the number of variables, and you will need additional sets $X_j$ for each clause, with $a_j=1$ (reflecting the constraint that exactly 1 literal in each clause be positive).

Showing this reduction would show that the problem is NP-hard, indicating that a polynomial-time solution is very unlikely.


Basis
    $$ |X| = 0 $$
    $$|P(X)| = 2^{|X|} = 2^0 = 1$$
    True. Any set with zero elements takes the form $\{\}$, and thus its power set will be $\{\{\}\}$. One element.

Inductive Step

We must show:
    $$|P(X+1)| = 2^{|X+1|}$$
    Thus:
    $$|P(X+1)| = 2^{|X+1|} = 2*2^{|X|} = 2*|P(X)|$$
    This is true because, if $X$ as a set grows by one, the power set, for every member in its set now has a new binary choice: include the new element or not. Thus the power set doubles.


Proving or disproving a set of total functions is countable

Hint: Let $M_1,M_2$ be an arbitrary pair of inequivalent Turing machines. Your set $S$ contains all functions satisfying $f(1) = M_1$ and $f(2) = M_2$.


Design a DFA which accepts words with sorted letters

Your suggestion is to use two states and stay in the first one until the machine reads a character that is strictly before the last one it read. This can't be right because a DFA can't test the current character against previous ones. A DFA knows exactly two things: which state it's in now and what the next character of the input is. Its decision about which state to move to is based only on those two pieces of information and everything from the past is forgotten.

When designing automata, it's a good idea to think about what each state means. For example, consider the following automaton, with states that I'll unhelpfully call $A$ and $B$. $A$ is the start state and is accepting; $B$ is non-accepting. Whenever the automaton reads a character, it moves to the other state. What does it do?  Well, it accepts the empty string because the start state is accepting. If it reads a character, it moves to the non-accepting state $B$; if it reads another one, it moves back to $A$. So, whenever the machine has read an even number of characters, it's in $A$ and, whenever it's read an odd number of characters, it's in $B$. It would, therefore, make much more sense to call the states "even" and "odd" because that's what they represent.  Knowing that, you could easily write an automaton that accepts exactly words whose length is, say, equal to  2, mod 3.  Or exactly the words equal to 3, 5 or 11, mod 12.  Being a bit more clever, you could write an automaton that accepts exactly the strings whose length is equal to 3 mod 5 and also equal to 0 mod 4 (hint: 20 states).

That doesn't directly answer your question but I think you've figured out the answer, from your comments. Yes, it's going to need about 28 states so it'll have about 28x27=756 arcs so you'll have to describe it instead of drawing it in full.


The complexity of the reachability-coreachability analysis of a finite state machine

Let $m\ge1$ be the size of the alphabet $\Sigma$.

Let us restrict our attention to the two most common models of finite state machines (FSM), deterministic finite automatons (DFA) and non-deterministic finite automatons (NFA). We know that FSM corresponds naturally to the directed multi-graph as explained by Wikipedia entry on state diagram.

A $n$-state $DFA$ $D=(Q,\Sigma,\delta,q_0,F)$ corresponds a directed multi-graph $G$, whose nodes are also $Q$ and all of whose nodes have outdegree $m$. Whenever we mention some $q\in Q$, it will be clear whether we mean the state $q$ in $D$ or the node $q$ in $G$. It takes $O(mn)$ time to convert $D$ to $G$.

The problem of determining all reachable states from state $q_0$ in $D$ corresponds to the problem of determining all reachable nodes from node $q_0$ in $G$. If we use the classic breadth first traversal starting from node $q_0$ to solve the later problem, the worst case happens when we have to go through all arcs in $G$, which is $\Theta(mn)$ time-complexity.  In fact, for any algorithm to determine the set of all reachable nodes, all edges must be checked.
The problem of determining all co-reachable states in $D$ corresponds to the problem of determining all reachable nodes from $q'$ in graph $G'$, where $G'$ is $G$ with all edges reversed and with one extra node $q'$ that is connected to all node $q_i\in F$. The conversion from $G$ to $G'$ takes $O(mn+n) = O(mn)$ time. If we use the classic breadth first traversal starting from node $q'$ to solve the later problem of all reachable nodes, the worst case happens when we have to go through all arcs in $G'$, which is $\Theta(m(n+1)=\Theta(mn)$ time-complexity. In fact, it is easy to see that asymptotically, solving the problem of co-reachability has the same worst-case time-complexity as solving the problem of reachability.

To summarize, the worse case to determine the reachability or co-reachability of a $n$-state DFA takes $\Theta(mn)$ time.

In this section, we will explain the exact meaning of the statement "all edges must be checked" for the case of reachable states.

(All edges by adversary) Let $G$ be a multi-graph $G$ of $n$ nodes and a start node $q_0$. Each node $q$ has exactly $m$ outgoing edges $\{q_\sigma\mid \sigma\in\Sigma \}$. The only way for us to know the other endpoint of $q_\sigma$ is to inquire from a truthful smart adversary $A$, who can config the other endpoint on the fly. Each inquiry must be "which node is the endpoint of $q_\sigma$ other than $q$?" for some $v$ and $\sigma$. The minimal number of inquiries needed to determine the set of reachable nodes from $q_0$ is $mn$.

Proof. Let $Q=\{q_0, q_1, \cdots, q_{n-1}\}$.

Here is $A$'s strategy to reply to the inquiry. Initialize $n$ empty set $S_q$, $q\in Q$. For an inquiry about $q_\sigma$ with $q=q_i$, there are five cases.

if $i\lt n-2$ and $\#S_q\lt m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
if $i\lt n-2$ and $\#S_q= m-1$, reply that $q_\sigma= (q,q_{i+1})$. Add $\sigma$ to $S_q$.
if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}\lt 2m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}= 2m-1$, reply $q_\sigma=(q_{n-2}, q_{n-1})$ when $q=q_{n-2}$ and reply $q_\sigma=(q_{n-1}, q_0)$ when $q=q_{n-1}$. Add $\sigma$ to $S_q$.
if $\#S_\sigma= m$, the inquiry must have been done before and, hence, reply the same as before.

I will leave the rest of the proof as an exercise.

Exercise 1. Finish the proof of "all edges by adversary". Show that $A$'s strategy is consistent in the sense that there is one such $G$ that all replies of $A$ are true. Furthermore, after $mn-1$ inquires, we cannot determine whether $q_{n-1}$ is reachable from $q_0$ or not.

Interested readers can do the following exercise that deals with NFA.

Exercise 2. the worse case to determine the reachability or co-reachability of a $n$-state NFA takes $\Theta(mn^2)$ time.


Determine time given algorithmic complexity as input grows?

The standard method is to heuristically assume that a bound of the form $\Theta(g(n))$ can be approximated by $Cg(n)$ for some constant $C$, though in some cases this approximation is not justified, and the "constant" $C$ fluctuates (but is bounded on both sides).

Considering your first example, if $f(n) \approx Cn^3$ then $f(k^2) \approx Ck^6 = (Ck^3)^2/C \approx f(k)^2/C$. Unfortunately, the dependence on $C$ cannot be eliminated, but $C$ can be approximated empirically, though you should take such results with a grain of salt.


How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming.

Let $m_i$ be the maximum viable elements of the sub-problem on $s[1..i]$. Consider the sub-problem on $s[1..i]$. An optimal solution has two choices.

It excludes $s[i]$, then it must choose an optimal solution of the sub-problem on $s[1..(i-1)]$.
It includes $s[i]$, then it cannot include $s[i-1],\ldots,s[i-k+1]$, and must choose an optimal solution of the sub-problem on $s[1..(i-k)]$.

Now you can write a recursion formula for $m_i$, and compute $m_1,\ldots,m_n$ in order in $O(n)$ time.


Your proof is incomplete, there are many cases you don't cover. You are not ruling out, for example, $u = 0^{m/2-3}$, $v=0$, $x=00$, $y=00$, $z=0^{m/2-2}$.

A good hint that your proof is wrong is that all you're using about prime numbers is that they're odd¹. Odd numbers do form a context-free language.

The pumping lemma gives you $uvxyz=0^p \in L$ and for all $n\in\mathbb{N}$, $uv^nxy^nz = 0^{p+(n-1)k} \in L$, with $k = |vy| \ge 1$. Now you need to prove that the numbers $\{p + (n-1)k \mid n\in\mathbb{N}\}$ cannot all be prime.

   Look at the values of $p + (n-1)k$ modulo $k+1$ when $n$ varies from $1$ to $k+1$. Since $k$ and $k+1$ are co-prime, one of them has to be $0$ modulo $k+1$, meaning that it is a multiple of $k+1$ (and not $k+1$ itself because it's larger), so it is not prime. Depending on your mathematics background, you may formulate this argument using the Chinese remainder theorem or any other equivalent theorem.

¹  And you didn't account for $2$ being prime, but that's ok, it's enough to consider sufficiently long words, because the status of a finite number of words doesn't affect the context-freedom of the language.


Which neural network topology is the most efficient to generate randomly shaped letters?

I think it's unlikely you're going to get good results.  Neural networks typically require a large training set.  With only a few dozen or so examples, I doubt you'll have a large enough training set for this to work well.

So, what could possibly go wrong?  I suspect the most likely outcome is that you'll get useless results.

That said, if you really insist on trying neural networks, you could try using a variational autoencoder.  An autoencoder consists of two halves: the first half maps the input $x$ to a value $z$ in the "latent space", and the second half maps $z$ to an output $x'$.  You train the autoencoder to ensure that (hopefully) $x$ and $x'$ are very similar, for all the instances $x$ in your training set.  The idea is that you make the latent space much smaller than the space of inputs/outputs, and you hope this forces it to generalize.

For instance, the input might be a 40-vector $x \in \mathbb{R}^{40}$, encoded by a one-hot encoding ($x_i=1$ means that you include a black line in the $i$th position; $x_i=-1$ means you don't include it).  The latent space might be $\mathbb{R}^2$ or $\mathbb{R}^3$ or so.  You might include a few layers of a convolutional network to map from $x$ to $z$, and then the inverse architecture to map from $z$ to $x'$.  Then, you could train the network using a standard loss function for variational autoencoders, along with some regularization term.


This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$.

As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$, it can be concluded that $f(i)$ is a decreasing function, which tells us that the array is sorted in decreasing order.

Here, we are looking for the smallest index $i$ such that $f(i)\lt 0$. We need to find a particular value of $i$ such that $f(i-1)\ge 0$ and $f(i)\lt 0$. Such an $i$ must be unique because for all indices greater than $i$, $f$ must be negative and for all indices less than $i-1$, $f$ must be non negative. Such an $i$ must exist as it is given that for at least one value each, $f$ takes positive and negative values. The index $i$ can be found by binary search as you suggested.


How does the undecidability of Extensional Martin-Löf Type Theory apply to real type-checking compilers?

You can't expect to find a ready-to-use proof of Id(a,b) when you need one. For instance, you have proofs of Id(a,c) and Id(c,b), but not of Id(a,b). You would need some intelligence to find automatically new proofs of equality, and avoid always having to ask the user to do the job manually. But there is no perfect algorithm to implement such an intelligence: whatever you implement, it will always have limitations.
There are however solutions to this difficulty, see for instance the Andromeda project.


Can a safe state in Banker's Algorithm cause deadlock eventually?

No deadlock as long as you keep running the Banker's algorithm.

By definition, a state is considered safe if it is possible for all processes to finish executing, which means there is no deadlock.

In order to avoid triviality, the question should be asking whether a safe state might change into deadlock. Assume the system is in a safe state (or the system is safe in short) initially. If you are able to run the Banker's algorithm, then

each time a request for resources is raised, the system will

either reject the request so the state  will not change, meaning the system is still safe of course.
or it will grant the request after it have been verified that after the requesting process has obtained those resources the system will still be safe, meaning the system is still safe.

each time some resources is returned, the system will obviously still be safe.

So, you can see that almost by definition and design, a safe state never goes into deadlock under the Banker's algorithm.

A more interesting question might be whether the system guarantees to make progress. The answer is yes, too. For any process, it is assumed that maximum number of instances of each resource type may not exceed the total number of resources in the system. It is also assumed that when a process gets all its requested resources it must return them in a finite amount of time. Suppose at some point of time, no process is able to run yet because of its lack of resources. Since the system is safe, resources will be allocated upon requests continuously until one of process is able to get all the resources it needs, meaning that process will start to run and progress will be made. After some finite amount of time, that process, having made some progress, must return all its requested resources to the system. Now the system is sort of back to square one but with progress made.

For a more rigorous analysis, you can check Selected Writings on Computing: A Personal Perspective
, Springer-Verlag, 1982, by the algorithm's designer Edsger W. Dijkstra.


Approximation algorithm for the partition problem

Consider what happens if you have 1000 items of size 1, and 1 of size 1000.  Optimally, you would have 2 sets of size 1000, but if you followed the heuristic with items in ascending order, you will have one set of 500, and one of 1500, for a 3/2 approximation, worse than 7/6.


Why do the following algorithms for Quadratic Primes perform so differently?

Well, I finally find out I'm just writing bad code that results in too many computations.
The condition in slow() should be P[i*i+a*i+b] != 1 instead of P[..] == 0 because there are cases when the index is smaller than 0.


A question about the polynomial hierarchy

Hint: $L \in \Sigma_i^p$ iff $\overline{L} \in \Pi_i^p$. (Here $\overline{L}$ is the complement of $L$.)


Efficiently finding "unfounded edges" in a strongly connected graph

I believe that computing graph dominators will solve your problem. This can be done in $O(|E|\log |V|)$ time (or even faster, though they describe the faster algorithm as "sophisticated") using a 1979 algorithm by Lengauer and Tarjan, which is (at least currently) described here (21 pages -- I have only read the first few pages myself).

Add a new "start" node with an out-edge to every source node, run the dominator algorithm to determine dominators for every node, and then check each edge $uv$: $uv$ is unfounded if and only if $v$ dominates $u$. (Each of these checks can be done in constant time using a lowest common ancestor (LCA) algorithm, although that may be overkill here -- for an edge $uv$, we only care about whether or not $LCA(u, v) = v$.)