Directed HAM Cycles with Additional Constraints to SAT

Encodings like this are notoriously slippery, so (of course) please carefully verify any outputs in case I've made a mistake somewhere.

Please assume that all unbound variables are universally quantified; i.e., I write $\bigvee_i\ p_{si}$ instead of $\forall s\ \bigvee_i\ p_{si}$.

Defining the partitions

First, define partition variables:

$p_{si} = \text{vertex $s$ is in partition $i$}$.

Basic partition constraints

Partitions are disjoint:

for $s \neq t$: $\lnot (p_{si} \land p_{ti})$.

Every string is part of one partition:

$\bigvee_i\ p_{si}$.

Coordinate matching within partitions

This is a little tricky.  First, we need to define which hypercube each partition corresponds to.  We specify this by defining which coordinates each partition matches on:

$m_{ij} = \text{partition $i$ requires coordinate $j$ to match}$.

Now we need to say that partition $i$ requires exactly $n-r$ coordinates to match (I'm going to use $r$ where OP uses $k$, because I need to use k as an index below):

$\sum_j m_{ij} = n - r$.

Computing the sum

Sums, of course, are not directly supported in the SAT model.  We can handle this by computing the sum with propositional logic:

$a_{ijk} = \text{for partition $i$, the sum over the first $j$ bits of $m$ is $k$}$.

The sum across the first $j$ bits for partition $i$ must be uniquely defined:

for $k_1 \neq k_2$, $\lnot (a_{ijk_1} \land a_{ijk_2})$.

We could require each sum to be defined at least once, but we don't need to; we take care of that for free when we define how addition works:

$a_{i1k} \iff m_{i1}$

$a_{ijk} \land m_{ij} \implies a_{i(j+1)(k+1)}$

$a_{ijk} \land \lnot m_{ij} \implies a_{i(j+1)k}$

Now we can set what the sum needs to be:

$a_{in(n-r)} = \texttt{true}$

(Again, I use $r$ where OP uses $k$ to avoid confusion with $k$ as an index.)

Constraining matches

Strings in the same partition match at the required coordinates:

$(m_{ij} \land p_{si} \land p_{ti}) \implies \text{strings $s$ and $t$ match at position $j$}$.

The RHS of that implication is just a set of constants that we can precompute as true or false.

Enforcing cycle direction within partitions

To encode direction, we can precompute constants for a neighbor relation between strings:

$d_{sti} = \text{$s$ and $t$ are identical, except at position $i$, where $s$ is 0 and $t$ is 1}$.

We'll also define a variable to encode which strings follow which strings:

$f_{st} = \text{$t$ immediately follows $s$ in the cycle}$.

$f_{st} \iff \bigvee_i x_{si} \land x_{t(i+1)}$.

Now we're ready to encode cycle direction:

$[\bigvee_i (p_{si} \land p_{ti})] \implies [\bigvee_{uvj}\ (f_{su} \land f_{tv} \land [(d_{suj} \land d_{tvj}) \lor (d_{usj} \land d_{vtj})]$.

If $s$ and $t$ are in the same partition, then there is one specific bit position $j$ where the strings $u$ and $v$ that follow $s$ and $t$ in the cycle differ (and specifically differ in the same direction: 0 to 1 or 1 to 0).

I don't know that much about SAT solvers, but it may be that the last line produces an unwieldy number of terms.  It may be possible to define further 'intermediate' variables like $f_{st}$ that break things up more and reduce the combinatorial explosion.


Are all partial functions partial computable?

The fact that we can encode Turing machines as strings means that there are only countably many Turing machines, so only countably many computable or partial-computable anythings.  Since there are uncountably many partial functions $\mathbb{N}\to\mathbb{N}$ (or even partial functions $\mathbb{N}\to\{0\})$, it follows that, in a very strong sense, "most" partial functions are not partial computable.

For a concrete example, use the fact that, if a set and its complement are both semi-decidable, they are both decidable (exercise: prove this), and the analogous result for partial functions. This means that, if you take any set $S$ that is semi-decidable but not decidable, then $\overline{S}$ is not semi-decidable.  So, for example, the function
$$f(x) = \begin{cases}
0 &\text{ if }x=\langle M\rangle \text{ for some TM $M$ that loops on every input}\\
{\perp} &\text{ otherwise}
\end{cases}$$
is not partial computable.


Why does this triple loop code have a running time of 1.5lnN * N^2

Let's consider the outer two loops first. For a fixed value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$.
Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the overall number of iterations of the middle loop is:
$$
\sum_{i=0}^{n-1} (n - i -1) =
\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}.
$$

For each of those iterations we execute the inner loop for a certain number $x \in \mathbb{N}$ of iterations. Notice that $x$ only depends on $n$ and not on $i$ or $j$.
Before the first iteration, the value of $k$ is $1$, and it doubles after every iteration (i.e., before the next iteration starts). This means that after a generic number $h \in \mathbb{N}$ of iterations (i.e., just before the $(h+1)$-th iteration starts) the value of $k$ is $2^h$. Since the loop continues as long as $k = 2^h < n$, we are interested in the minimum value of $h$ for which the above inequality is not true. This is $x = \lceil \log n \rceil $ if $n \ge 1$ (where we used the fact that $h$ must be a non-negative integer) and $x = 0$ otherwise. Since you are interested in the asymptotic behavior of the algorithm, I will ignore this latter case.

Finally, notice that for each iteration of the inner loop, exactly $3$ array accesses are performed.

To summarize:

We reach the inner loop $\frac{n(n-1)}{2}$ times;
Each time we perform $\lceil \log n \rceil$ iterations;
Each iteration causes $3$ array accesses.

The total number of array accesses is therefore:
$ \frac{3}{2}n(n-1) \lceil \log n \rceil  \sim \frac{3}{2}n^2 \log n$.


Which languages, decided by a turing machine are decidable?

Nice question.

Notations and terms

$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.

$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.

Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book introduction to the theory of computation by Michael Sipser. You could take a look at its definition at Wikipedia as well.

  We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.

  DEFINITION 3.6. Call a language Turing-decidable or simply decidable if some Turing machine decides it.

Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.

Application of Rice's theorem

Here is the Rice's theorem.

  Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.

  In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $\langle M_1\rangle \in P$ iff $\langle M_2\rangle \in P$. Here, $M_1$ and $M_2$ are any TMs. Then $P$ is an undecidable language.

a) $P=\{\langle M \rangle\mid L(M)\subseteq 0^*\}$.

WLOG, let 1 be an input alphabet symbol other than 0. $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{0\}$ but $P$ does not contain the description of a Turing machine whose language is $\{1\}$.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)\subseteq 0^*$ iff $L(M_2)\subseteq 0^*$

By Rice's theorem, $P$ is undecidable.

b) $P=\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\}$.

$P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{00\}$ but $P$ does not contain the description of a Turing machine whose language is $\{0\}$.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ contains at least one word of even length iff $L(M_2)$ contains at least one word of even length.

By Rice's theorem, $P$ is undecidable.

c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\}$ contains all TM descriptions, which is a decidable language.

d) $P=\{\langle M \rangle\mid L(M)\text{ is decidable}\}$.

Let $R=L(D)$ be a decidable language. For example, we can take $R=\{0\}$ and $D$ is a Turing machine that accepts 0 and rejects all other inputs. $\langle D\rangle\in P$. Let $H=L(N)$ be a semi-decidable but not decidable language. For example, we can take $H$ to be the language of the halting problem. Then $\langle N\rangle\not\in P$. Hence $P$ is nontrivial.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ is decidable iff $L(M_2)$ is decidable.

By Rice's theorem, $P$ is undecidable.

 For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\{0\}$, then, of course, for every $M$, $L(M)\subseteq 0^*$. Then $\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^*\}$ contains all TM descriptions. It is decidable.


Searching for the biggest area inside 2D matrix

A BFS combined with floodfill should be enough.

Basically, you do the following:

Iterate until you find the first X
Run a BFS on it and change all pixels to visisted = True. Also keep track if you happen to reach the boundary or fulfill any other criterion s.t. it is disqualified
If it is not disqualified, save its size as the current max-size
Iterate further until you find the next unvisited pixel and redo steps 2-4. Keep track of the largest size found.
If you need the original array, change back the visisted state of each pixel in a final iteration.

Overall runtime: Linear, because you change each element at most twice (once to visisted and once back), and also consider only a constant number of neighbors for each element (8).


How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

Let $N$ be the constant of the Pumping Lemma for CFL.

Let be $z=a^N b^{N+1} a^N b^{N+1}$.

let's analyze some of the possible decompositions of $z$ in $uvwxy$:

(note that $vx$ has always at least one symbol)

$u=\epsilon$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$.
just pumping once we get a string out of $L$.
$u=a^*$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. same as above.
$u=a^*$, $v=a^*$, $w=a^*$, $x=a^*b^*$, $y=b^* a^N b^{N+1}$. same.
$u=a^*$, $v=a^*$, $w=a^*$, $x=b^*$, $y=b^* a^N b^{N+1}$. same.
$u=a^*$, $v=a^*$, $w=a^*b^*$, $x=b^*a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$u=a^*$, $v=a^*$, $w=a^*b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$u=a^*$, $v=a^*$, $w=b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$...$

Anyway the problematic case is 7. because it could be $u=a^k$, $v=a^j$, $w=b^{N+1}$, $x=a^j$, $y=a^kb^{N+1}$ with $k+j=N$, so that pumping doesn't push $z$ out of $L$. But again, it can't happen otherwise we would have $\mid vwx\mid >N$, which is not possible and it is guaranteed by the lemma.


How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

Find all nullable variables. In this case only E' is nullable.
Let me illustrate the second step with an example:

Replace a production A -> BCD with a family of productions like this (assuming B, C & D are nullable):

A -> BCD | BC | BD | CD | B | C | D

Delete all the productions with the empty string as the right-hand side.

With all that in mind we get:

E  -> TE' | T
E' -> +TE'| -TE' | +T | -T
T  -> (E) |  id


Contradiction between best-case running time of insertion sort and $n\log n$ lower bound?

The lower bound of $\Omega(n \log(n))$ is a lower bound for the worst-case behavior of a sorting method. Both insertion sort and bubble sort have $O(n^2)$ worst-case complexity.


Union of a regular and a non-regular language

I assume you can already prove that the union, intersection, and complement of regular languages is regular.

Let $L_1$ be regular and $L_2$ be non-regular. Then you should also be able to prove:

At most one of $L_1 \cup L_2$ and $L_1 \cap L_2$ is regular.
If $L_1 \subset L_2$ then their union is irregular. (You should also be able to construct an example).
If $L_2 \subset L_1$ then their union is regular. (You should also be able to construct an example).
If the complement of $L_1$ contains at least two words, there is a regular language $L_3$ such that $L_1 \cap L_3 = \emptyset$ and $L_1 \cup L_3 \subsetneq \Sigma^*$. Then either $L_3 \cup L_2$ is regular or $L_1$, $L_3 \cup L_2$ are an example of a regular and an irregular language whose union is regular but where neither is a subset of the other and their union is not $\Sigma^*$.


Aspvall, Plass and Tarjan describe a linear time algorithm determining the truth value of quantified 2CNFs in their paper A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Their algorithm is an extension of the well-known algorithm for solving 2SAT using directed reachability; their initial step is computing the strongly connected components of the implication graph.


What is the difference between finite automata and Büchi automata?

There is no difference in the specification (syntax). The only difference is in the interpretation (semantics). The language accepted by a DFA consists of finite strings defined in a certain way given the DFA, and the language accepted by the corresponding Büchi automaton consists of infinite strings defined in a certain way.

Indeed, you can leverage this connection to prove results such as:

  An $\omega$-language is recognizable by a deterministic Büchi automaton iff it is the limit language of some regular language.

For a proof, see Wikipedia.


Should we assume both processes are getting same CPU clock while we solve SYNCHRONIZATION problems in uniprocessor system?

It is very common to run processes on an operating system with a preemptive scheduler. The scheduler can switch between processes at any time: it is unpredictable when the operating system will switch from one process to another.

Unless otherwise specified, this is the model we use when discussing synchronization problems: there may be a switch between processes at any time. This means that in many cases there is no difference between the uniprocessor case and the multiprocessor case: the same execution sequences are possible in both. The operating system effectively pretends that there's one CPU per process.

The switches can even happen in the middle of a high-level instruction. For example, if you write a simple assignment in a high-level language

x := y;

this could translate to multiple machine instructions such as

copy top half from x to y
[possible switch]
copy bottom half from x to y

or

load x to register r1
[possible switch]
store y from register r1

This is why it's important to know which operations are atomic even in the uniprocessor case.

When you consider synchronization between kernel threads, and you get down to the level of machine instructions, there are things that are not possible in a uniprocessor case, because the kernel decides when a context switch is possible. But to exclude these impossible sequences, you need to know both how the machine instructions work and how the kernel works. If you don't know that then you can't exclude any interleaving of the execution.


Double hashing - probe count probabilities

As Wandering Logic noted, there are approximate expressions for probabilities of probe count in unsuccessful search  case in TAoCP, a few pages later expressions for expected probe count:

$1-\alpha$, $\alpha(1-\alpha)$, $\alpha^2(1-\alpha)$, ... - probabilities of making 1, 2, 3, ... probes respectively.

In successful search case I derived approx. expressions myself, relying on explanation of expected probe count formula in the book:

$1 - {\alpha\over2}$, ${\alpha\over2} - {\alpha^2\over3}$, ${\alpha^2\over3} - {\alpha^3\over4}$, ...


External fragmentation in fixed size partitioning

You seem to feel external fragmentation should not be possible with a fixed size algorithm – I wonder why?

Summary: A fixed size algorithm probably only helps if all requests are for the size it provides.

External fragmentation has, in general, more to do with the order of de-/allocation and the strategy for placement of allocation blocks in the available space than with the size of space allocated for a given request. However, if all requests are for the same single fixed size as the algorithm allows for the caller (i.e. minus any internal overhead), then fragmentation will no longer be a functional problem: although allocated and unallocated blocks may be interspersed, this will not reduce the total number of allocation requests that can be satisfied. There could however be consequences for performance, especially if the algorithm does not maintain a chain of free blocks.


Recognizing interval graphs--"equivalent intervals"

Imagine scanning the real line from left to right. Whenever an interval starts or ends, you make notice of it. For example, perhaps at some representation, at the point $3$ the intervals for $x_2,x_7$ start and the interval for $x_{15}$ ends, and at the point $4$ the interval for $x_2$ ends, and no points occur in between.

Suppose we "remove" the portion $(3.25,3.75)$ of the real line, thus pushing the point $4$ back to $3.5$. This only affects the value of some ordinates, so we would like to say that these two interval representations are "the same". Indeed, they are equivalent under the definition you give, since if we make a list of which intervals start and end at what point, then the lists would be identical, the only difference being the value of the ordinates.

Another operation we can do is reflecting the real line, say around zero. Now the interval for $x_2$ is $(-4,-3)$ instead of $(3,4)$, so that at the point $-4$ the interval $x_2$ starts, and at the point $-3$ the intervals for $x_2,x_7$ end and the interval for $x_{15}$ starts. Again, we would like both of these representation to count as "the same". This transformation is captured by the reversal clause in the definition you quote.


Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$?

It's a more or less standard result that the language in question isn't  context-free, so the answer to your question is no. The same holds for a number of similar languages, like
$$
L_1= \{a^{n^2} \mid n\ge 0\}\quad\text{and}\quad L_2=\{a^p\mid p\text{ is prime}\}
$$
There's a nice property that can be useful in cases like this: any context-free language over a one-symbol alphabet is regular. This, combined with a characterization of regular languages over a unary alphabet implies that languages like the ones above cannot be context-free since they're too "sparse".


How many recursive calls does it take to compute binomial probability weights?

If we let $T(n,k)$ represent the number of times that binomial1 is called when computing binomial1(n, k, p) we'll have $T(n,k) = T(n-1, k) + T(n-1, k-1)+1$ and $T(-1, k) = T(k, -1) = T(0,0)=1$. The closed form expression for $T(n,k)$ is a bit messy, but fortunately we don't need it.

Note that the binomial coefficients $\binom{n}{k}$ are defined by the nearly similar recurrence $\binom{n-1}{k} + \binom{n-1}{k-1}$ so we'll have $T(n,k)\ge \binom{n}{k}$ and in particular $T(100, 50)\ge \binom{100}{50}$ and by Stirling's approximation we'll have $T(100,50)\approx 2^{100}/\sqrt{50\pi}$, which is pretty much what you guessed.

[In fact, it turns out that $T(n,k)$ is quite a bit larger than $\binom{n}{k}$.]


Language of balanced parentheses; Biconditional proof about parentheses

You are given two different definitions of the language of balanced parentheses:

$w \in L$ iff $w$ contains an equal number of "(" and ")", and every prefix of $w$ contains at least as many "("s as ")"s.
$L$ is generated by the grammar $S \to SS | (S) | \epsilon$.

You need to show that both definitions are the same. The easy direction is showing that each word generated by the grammar satisfies property (1). You do this by induction - either induction on the length or "structural" induction, which in this case is induction on the number of derivation step (base case: $S \to \epsilon$, steps: $S \to SS$, $S \to (S)$). The other direction is more complicated. You need to use complete induction; given a word $w$ satisfying (1), figure out which production needs to be applied first, and which parts of the word it generates, and then appeal to the induction hypothesis.


Logarithmic run time for calculating prime numbers?

Let's use a different parameter for your input, $m$. The number of instructions that your algorithm executes in the worst case is $O(m)$.

We often measure the running time of algorithms in terms of the length of their input (measured either in bits or in words), often denoted by $n$. The length of your input is $n \approx \log_2 m$, since this is how long it takes to encode the integer $m$ in binary. Therefore your algorithm actually performs an exponential number of instructions $O(2^n)$.

A different issue is the cost of arithmetic operations, such as the modulo operation on line 3. In most models of computation (and in real life), the cost of such an operation depends on the length of the numbers being operated on. Therefore your algorithm runs in time which is worse than $2^n$ by a polynomial factor $n^{O(1)}$ (the exact polynomial factor depends on the algorithm you use to perform the division). Such a running time is usually denoted $\tilde{O}(2^n)$.


Are the words "expression" and "term" interchangeable in programming language theory?

The two words expression and term have largely the same sets of possible meaning, but in a specific presentation, they may not be synonyms.

In rewriting theory, a term is something that conforms to a certain syntax, and for which a notion of computation (rewriting) is defined. In programming language theory, term can mean specifically one of the two aspects. And so can expression. Which means which depends on the author, and not all authors use both words in this way.

One possible meaning of the word is “something that can be computed”. In this sense, if the computation terminates, you end up with a value.
Another possible meaning of the word is “something that conforms to a certain syntax”. There is often a computation mechanism defined over this syntax, but not always.

In the theory of a programming language, there are often multiple syntactic objects: the core language, types, kinds, objects, classes, modules, interfaces, … Something like function x : int => x + 1 may be a core term which contains the type term int, or a core expression which contains the type expression int. It's common but not universal to use one of the two nouns to mean “core” (and “core” is my choice of terminology), e.g. “function x : int => x + 1 is an expression” or “function x : int => x + 1 is a term”. Different authors use different words; communities of a specific language tend to align on terminology, but that isn't systematic.

For example, in the world of ML, “expression” with no qualifier is normally reserved for the core language, and there are additionally “module expressions” in the module language, as well as “type expressions” and “signature expressions”. A “term” can be anything conforming to one of the syntactic forms, although many authors (e.g. the SML definition) don't use “term” at all.

But in Coq, a “term” is the most important syntactic form. Due to the nature of the language, the syntax of types is the same as terms. The Coq manual uses “expression” to designate any family of syntactic form.

If you're reading a text on programming languages, the meaning of the words should be explained or (in less formal texts) clear from context. If you're writing a text, try to use the terminology that's common in your community, and always make sure that the definitions you use are clear.


What is the point of traversing a binary tree in preoder, inorder or postorder?

Different traversals of a binary tree exist to suffice different data dependencies between the nodes.

Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.

In case of Postorder, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n_i$ the weight of the subtree rooted at $n_i$, which is the sum of the weights of all descendants of $n_i$ including $n_i$.

In case of Preorder, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.

In case of Inorder you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).

Finally, in case of BFS, we consider the tree as levels, level $l_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n_i, n_j$ if $i < j$, $n_j$ is not closer to the root than $n_i$.

Note that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.

Note In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).

Note One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.


Given a truth table, force a contradiction

It appears the question that you are asking is:

  What is the set of formula for which a witness attempting to prove the formula false will always fail?

That is, you are asking whether a formula is valid: whether it is true for every interpretation. A formula is valid if and only if its negation is unsatisfiable, which according to this resource is Co-NP complete.


Schedule tasks from a weighted list with time frame constraints

I'd be inclined to punt the problem to an integer linear programming problem solver. (Note that many solvers will take a timeout argument that'll return the best solution they've found so far if/when the timeout triggers)

Encode each task as a rational (or potentially integer, depending) for the time of the start of the task and a boolean for if the task is going to be done, with appropriate bounds constraints predicated on if the task is going to be done (note that when you have multiple possible time slots for a task you'll need to encode the bounds as "at least one of these time slots are valid").

Then for each pair of distinct tasks add a constraint that either the first task starts after the second one finishes or vice versa.


Basic mapping reductions without using Turing machines

The identity function is a reduction from a language to itself. One reduction from $\{0,1\}$ to $\{0,1\}$ is given by $\lfloor x/2 \rfloor$, which maps $0,1$ to $0$, and all other integers to non-zero values.


What is a "slice" of a parameterized problem $(Q, \kappa)$?

The way you state it, a slice of an parameterized problem is the problem where we use some fixed constant for our problem parameter, instead of a 'free' variable. In a sense, we are only considering the subfamily of the problem for this particular constant, which is probably the logic behind the name 'slice'.

Indeed, if a problem $(Q,\kappa)$ is fixed parameter tractable, there is an algorithm that solves this problem with running time $O(f(n)\cdot g(\kappa))$, where $f$ is (sub)polynomial and $g$ can be superpolynomial. So, if we take a slice of this problem, then there is an algorithm that solves the problem '$(Q,l)$' ($=(Q,\kappa)_l$) in time $O(f(n)\cdot g(l)) = O(f(n))$, as $l$ and therefore $g(l)$ is constant. So $(Q,\kappa)_l$ is indeed solvable in PTIME.


Search in a partial ordering defined by tuples of numbers

I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

global: visited, front

function proceed(arrival)
    visited := array of bool for each node initialized to false
    for each x &isin; front
        proceed(arrival, x)
    return front

function proceed(arrival, node):
    if(visited[node]): return
    visited[node] := true
    if(node.departure > arrival):
       remove node from front
       for each node x:
           append x to the end of front

function calculate_outgoing:
    outgoing := array of lists for each arrival at A, each list contains feasible and relevant A->B connections for that arrival.
    front   := [(-&infin;, -&infin;)]
    for each arrival at A in increasing order:
        outgoing[arrival] := proceed(arrival)
    return outgoing

Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.


Traveling Salesman Problem: Big O Complexity of Algorithm

You've almost got it! Remember, you're going to visit each city exactly once in a tour. Which means you have to look up $n-1$ distances for each one. This is $O(n)$, since the problem specifies that matrix lookup is assumed to be $O(1)$.


FSM + state data is Turing complete abstraction?

Maybe your questions should be more self-contained, but let's assume that your description together with the documentation from Akka amounts to the following description:

The input consists of events, and the output consists of actions.
Even so output actions may trigger further input events, this relation is neither fully deterministic, nor part of the machine model itself.
There are a finite number of states that determine which rules will be applied to the input event and the internally stored data, for determining the output action, the new state, and the modification of the internal data.
After an output action is performed, the machine transitions into a new state, and waits for further input events.

Under these conditions, the machine model is only Turing complete if already the rules for determining the output action, the new state, and the modification of the internal data were Turing complete.

What you have in mind is probably some mechanism for triggering input events as part of the output action. So the FSM is supposed to have some sort of first-in, first-out event queue, and the output action can post input events to this queue. In this case, this machine model would be more powerful than a queue automation, which is known to be Turing complete.


What you call "equational dynamics" is not actually an operational semantics, it's an equational theory. As you note, equations by themselves do not tell us how to run programs. However, they are needed because we want to express the idea of program equivalence. For instance, an optimizer replaces a piece of code with an equivalent piece of code (which is hopefully more efficient). But what does "equivalent" mean here?

We can use observational equivalence: two programs are equivalent if we can make exactly the same observations about them. In other words, they behave the same way. This kind of equivalence is defined using operational semantics.

An alternative is to start by prescribing equivalences. We want certain programs to be equivalent, usually because we have some mathematical understanding of how things are supposed to work. For instance $\beta$-reduction $(\lambda x . e_1) e_2 = e_1[e_2/x]$ is an equation which expresses the mathematical meaning of $\lambda$-abstraction. In practice is is often easier to come up with equations than with an operational semantics. (For instance, when Matija Pretnar and I worked on Eff, we knew exactly what the equations were because we were actullay trying to turn equational theories into a programming language. Also, when Alonzo Church came up with the $\lambda$-calculus he wrote down equations that expressed the mathematical properties of functions and function application.) The problem then is to find an operational semantics which respects the equations, but at the same time does not introduce (too many) observational equivalences that are not implied by the equations.


This answer assumes that $T(M)$ is the set of inputs on which $M$ halts.

Given an instance $u\#v$ of $\texttt{EQU}$, we construct a new Turing machine $w$ with the following input:

A string $x$.
An integer $t$.

The machine acts as follows.

Run $u$ on $x$ for $t$ steps. If $u$ halted, then run $v$ on $x$.
Run $v$ on $x$ for $t$ steps. If $v$ halted, then run $u$ on $x$.
Halt.

I claim that $w \in \texttt{UNI}$ iff $u\#v \in \texttt{EQU}$. To see this, consider some input $x$. We distinguish four different cases:

Both $u$ and $v$ halt on $x$. In this case $w$ will halt on $x,t$ for all $t$ (since "run $v$ on $x$" and "run $u$ on $x$" will always terminate).
Both $u$ and $v$ don't halt on $x$. In this case the test in steps 1–2 will always fail, and so $w$ will always reach step 3 and halt on $x,t$, for any $t$.
$u$ halts on $x$ after $t$ steps, and $v$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 1.
$v$ halts on $x$ after $t$ steps, and $u$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 2.

How did I construct this machine? First of all, let us note that $\texttt{UNI}$ is $\Pi_2$-complete. This means that we can reduce to it any language $L$ such that
$$
x \in L \leftrightarrow \forall y \exists z \, \Pi(x,y,z),
$$
where $\Pi$ is any computable predicate. Next, using $H(u,x,t)$ for "$M_u$ halts on $x$ within $t$ steps", we see that
$$
u\#v \in \texttt{EQU} \leftrightarrow \forall x (\exists s \, H(u,x,s) \land H(v,x,s)) \lor (\forall t \, \lnot H(u,x,t) \land \lnot H(v,x,t)).
$$
Rearranging, this is the same as
$$
u\#v \in \texttt{EQU} \leftrightarrow \forall x \forall t \exists s \, (H(u,x,s) \land H(v,x,s)) \lor (\lnot H(u,x,t) \land \lnot H(v,x,t)).
$$
Therefore $\texttt{EQU}$ should reduce to $\texttt{UNI}$. Taking a look at the $\Pi_2$-completeness proof, we reach the machine outlined above.

It is easy to see that $\texttt{UNI}$ reduces to $\texttt{EQU}$, by mapping $w$ to $w\#h$, where $M_h$ is a machine that always halts. We conclude that $\texttt{UNI}$ is also $\Pi_2$-complete.


how to deduce a function subtype rule from a given function type definition

The intersection rule should be derivable, but it isn't purely a subtyping rule. Basically we reason as follows (I've translated into a notation that's a bit more familiar to me):

I'm presuming that subtyping says $A \cap B \subseteq A \subseteq A \cup B$
Subtyping means that $f : (A \to Y) \cap (B \to X)$ leads to both $f : A \to Y$ and $f : B \to X$
If $f : A \to Y$, it is then the case that $x : A ⊢ f \; x : Y$. But subtyping $A \cap B \subseteq A$ means that $x : A \cap B ⊢ f \; x : Y$ follows.
The same argument means that $f : B \to X$ leads to $x : A \cap B ⊢ f \; x : X$
These two judgments together lead to $x : A \cap B ⊢ f \; x : X \cap Y$
This leads back to $f : A \cap B \to X \cap Y$

Another way to specify this is that $f : (A \to X) \cap (A \to Y)$ leads to $f : A \to X \cap Y$. Subtyping allows us to broaden the original $A$ and $B$ to the common $A \cap B$, and then apply this intersection rule. But the intersection rule isn't subtyping, it is the rule for deducing that something has an intersection type via two separate deductions.

Pure subtyping can allow you to go from $f : A \to Y$ to $f : A \cap B \to X \cup Y$. Note that this is refining the input and broadening the output, and we could do each individually.

For union types, there is an opposite sort of rule. $f : (A \to Y) \cap (B \to Y)$ leads to $f : A \cup B \to Y$. So, if you can map both $A$ values and $B$ values to $Y$ values, you can map their union to $Y$ values. However, note that this doesn't allow us to deduce your rule with a union. Instead, we can only get from $f : (A \to Y) \cap (B \to X)$ to $f : A \cup B \to X \cup Y$, because this time we can broaden the result type of both functions and apply the union rule.

But, there is no way (I think) to get to $f : A \cup B \to X \cap Y$, which makes sense if you think about it. Just because we know that $f$ takes $A$ values to $Y$ values and $B$ values to $X$ values doesn't imply that it takes all $B$ values to $Y$ values and $A$ values to $X$ values, which is what that specification says.

So, to sum up:

The rule is derivable (with some standard assumptions, I think).
The rule is not a contradiction.
We can derive a union rule, but not the one you wrote. And I'm unsure what 'complement' rule you're talking about.
Subtyping works as usual, but it is not the only basis for the intersection/union rules.

Edit: Here's a summary of the rules that I believe hold, as I think it might lead you less astray than the long stuff above:

$$(A \to Y) \cap (B \to X) \subseteq (A \cap B) \to (X \cap Y)$$
$$(A \to Y) \cap (B \to Y) \cong A \cup B \to Y$$
$$(A \to X) \cap (A \to Y) \cong A \to X \cap Y$$

In particular, note that the first relationship is subtyping, not equivalence. The intersection of the function types carries more information than the function between intersection types. If the lisp documentation you're looking at says those are the same, it's wrong. Consider, just because we know that a function takes $A \cap B$ to $X \cap Y$ doesn't tell us anything about what it takes $A - B$ to. However, if it's merely saying that knowing $f$ has the first two types, we can conclude it also has the third type, that is correct.


Monad in Haskell programming vs. Monad in category theory

A monad in Haskell is intended to be a monad on the category of types, when the category theory is done internally to the type theory. The capabilities of Haskell and similar languages are somewhat limited, so there are a lot of basic constructions in category theory that cannot be done, but there are plenty of structures that can be encoded reasonably.

M :: * → * is the object mapping of the functor, which you have instead named $T$ later.
The arrow mapping part of the functor is given by fmap
$η$ is the unit function, which Haskell calls return (or pure, which is a little more general)
$μ$ is given by join.

The requirements expected of Monad instances are equivalent to the ones to be a monad in category theory.
Essentially, this is not much different than speaking specifically about monads on the category $\mathsf{Set}$, aside from the earlier mention of Haskell/etc. missing some constructions that set theory has (there are things that act enough like (co)products, but not like pullbacks/pushouts). You could do a lot only thinking about monads on $\mathsf{Set}$, because many structures in abstract/universal algebra give rise to one, and are presentable that way.
One might quibble that types in various programming languages do not technically form a category with good properties/structure, but you could instead imagine that you are using them as a means to talk about something better behaved, like System $F_ω$, and it wouldn't really change the answer in an interesting way.


How to determine the maximum RAM capacity for an operating system?

The calculation is in bytes since the memory is addressed in units of bytes. If a machine word is $N$ bits and an addressed is stored in a register whose size is a single machine word, then you can address $2^N$ different locations, each of which is a byte (in principle, that could depend on the CPU, but I'm not aware of any CPU which addresses its memory in larger words). However, more complicated addressing mechanisms can be used to address more memory. For example, pointers could take up more than a machine word, or segments could be applied (as in 80386 and its successors).


Origins of misconception about using equality signs with Landau notation

$O$ is not only used in simple statements like $f(n)=O(g(n))$. It is also used to give error terms as in $f(n) = 14\, n\log n + O(n)$. The interpretation is still the same as @usul has described in his answer: There is a function $h \in O(n)$ so that $f(n) = 14\, n\log n + h(n)$.

Here, writing $f(n) \in 14\, n\log n + O(n)$ would emphasize the fact that there is a set involved in the equation, while the important point is that the leading term(s) are exactly as stated, while the $O$-term simply bounds the error. So in this context using $=$ is a sensible choice and I'd assume that it has been carried over to the case with zero leading terms in order to keep notation consistent.


It will be difficult with your idea as you don't initially know which table to put a person in.  For example will different 1 2 and different 3 4 have two solutions, namely $A = \{1, 3\}$ and $B = \{2, 4\}$, and also $A = \{1, 4\}$ and $B = \{2, 3\}$ (and symmetrically).  When you get the information that different 2 3, you have now lost some crucial information that you need.
The answer is graphs.
A graph is bipartite if and only if it is two-colorable (if and only if it has no odd cycles).
You are creating a bipartite graph such that when there is an edge between two people then they attend different parties.
When the graph is connected, it is easy to say whether two people are in the same party or not: Given $u$ and $v$, if the shortest path from $u$ to $v$ has an even number of edges, they are in the same party, if it has an odd number of edges, they are in different parties.
The command different u v simply adds the edge between $u$ and $v$.
However, the command same u v is slightly worse since you need to record the fact that they don't have an edge.
I would do the following.

If $u$ or $v$ have neighbors, add edges from $u$ to $N(v)$ and/or $v$ to $N(u)$.  One is enough, but you can also make it complete.  This is a space/time tradeoff.
If neither $u$ nor $v$ have neighbors, construct an artifical vertex $x_{uv}$ and connect both $v$ and $u$ to $x_{uv}$.  If $u$ or $v$ later get a different command, say different v w, you can remove $x_{uv}$, or identify $x_{uv}$ and $w$ (merge the vertices and their neighborhoods).

Complexity:

different a b → $O(1)$.  Add edge in constant time.  Check if $a$ or $b$ has an $x$-neighbor takes $O(1)$ time, delete that vertex takes time $O(1)$.  Add at most two edges after $x$ deleted.
same a b → $O(1)$.  Check existence of neighborhood, if so, add two edges in constant time.  Otherwise, create $x$ vertex and add two edges in constant time.
tell a b → $O(n + m) = O(m)$ with a single BFS search.  When you get the path $P$ you can add edge from $P_i$ to $P_{i+2}$ for all $i$; that could lower the future searching time.


Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?

Fortunately you gave us some context in the comments (always a good idea to include it in your question). Rather than doing what you're trying to do, I believe quantitative type theory is what you're looking for.


[...] an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

Be careful with this! In the context of NP-completeness we work with many-one reductions, not Turing reductions. This means you are not allowed to assume the existence of an efficient algorithm for $X$; this is too strong an assumption since it would allow you arbitrary access to the algorithm deciding $X$. Rather, you must reduce SAT to an instance of $X$. In fact, it is irrelevant whether $X$ can be solved efficiently or not (or even solved at all!). This establishes NP-hardness; for NP-completeness you also need to show $X \in \textbf{NP}$.

Note it is only once you have established NP-hardness of $X$ that you can say the existence of an efficient algorithm for $X$ implies the existence of an efficient algorithm for SAT (or any problem in NP). However, this is only an implication of the NP-hardness of $X$, not the actual requirement for $X$ being NP-hard.


are regular languages closed under division

If $L_1$ is regular and $L_2$ is any language, then $L_1 / L_2$ is regular. In fact, the construction of a DFA for $L_1 / L_2$ is almost trivial (with one caveat): It's the same as the DFA for $L_1$, except that the "final" states are the the states which can reach the original accepting states given a string from $L_2$.

Suppose that $M_1 = (Q, \Sigma, \delta, q_0, F_1)$ is the DFA which accepts $L_1$. Then a DFA which accepts $L_2$ is $M_2 = (Q, \Sigma, \delta, q_0, F_2)$, where:

$$F_2 = \left\{ q \in Q : \exists x \in L_2. \delta(q,x) \in F_1 \right\}$$

Now here's the caveat: this proof sketch is not constructive! To turn this into an algorithm requires some way to enumerate or recognise strings in $L_2$, and remember, $L_2$ can be any language.

If $L_1$ is context free and $L_2$ is regular, $L_1 / L_2$ is always context-free (proof left as an exercise), but it is not necessarily regular. (To see why, consider $L_2 = \{ \epsilon \}$.)

EDIT I've just noticed that the definition in the question is different from the usual definition of "right quotient". The usual definition is:

$$A/B = \left\{x\in \Sigma^{*} : \exists y \in B. xy \in A\right\}$$

The definition in the question is:

$$A\div B = \left\{x\in \Sigma^{*} : \forall y \in B. xy \in A\right\}$$

My answer us for the usual definition, because these are standard results. The answers are similar for the definition in the question, except that the construction is slightly different. (See David Smith's comment.)

I suspect there is a typo in the original question.


Language of the graph of an affine function

Hint:

$53 \cdot 100000010000000000 + 4 = 5300000530000000004$.

Sketch:

   Assume $a$ has $n$ digits and $b$ has $m$ digits.

 If $\overline{x}=10^k \underbrace{00\dots01}_{n}0^l\underbrace{00\dots0}_{m}$ for some $k,l$ then

 $\overline{ax+b}=\overline{a}0^k \overline{a} 0^l \overline{b}$.

 If $L$ was context-free, then

 $$L'=L \cap 10^{\ast}0^{n-1}10^{\ast}0^m \mathtt: (0+1+2+...+9)^{\ast} = \{10^{k+n-1}10^{l+m} \mathtt: \overline{a}0^k\overline{a}0^l\overline{b}:k,l \in \mathbb N\}$$
 would be context-free as well.

 Given a PDA $M$ for $L'$ we could construct a PDA $N$ for $\{a^n b^m c^n d^m\}$ , a well-known non-context-free language. $N$ simulates $M$, but it is "feeding" different letters; it is a composition of $M$ with a transducer. Initially, $N$ behaves as if $M$ read $1$. Then, consecutive $a$'s are interpreted as $0$'s. Next, $N$ behaves as if $M$ read $0^{n-1}1$, and treats consecutive $b$'s as $0$'s, then as if it read $0^m \mathtt: \overline{a}$ etc.


Problem with solving the recurrence $T(n) = 2T(\sqrt n) + \log n$

Regarding your 1st problem:
You don't need to change $m$ to $\log m$. Let's suppose $f(x)=g(y)$.Then you do not need substitute $y$ anywhere. Because $y$ if substituted would again produce $y$. If you  substitute $y$, you must substitute  it by $g^{-1}f(x)$=$g^{-1}g(y)=y$. You can see you are again getting $y$.

Regarding your second problem:
$S(m)=T(2^m)$

Let $y=m/2$

$$S(y)=T(2^y)$$

$$S(m/2)=T(2^{m/2})$$

You must substitute $m$ by $m/2$. What you are doing is dividing $2^m$ by $2$ which is completely wrong.


What is a Huffman tree for a Block-Code?

In your context, a block code of length $\ell$ encodes $\ell$ letters at a time. The domain thus consists of all words over the alphabet of length $\ell$. Unless you're told otherwise, the assumption is that the individual letters are independent - the probability of a word $\sigma_1 \dots \sigma_\ell$ is the product of the probabilities of the individual letters.


Is a String with no parantheses considered having balanced parantheses?

This is what formal definitions are for...

That said, it makes the most sense to allow no parentheses. Roughly speaking, a string has balanced parentheses if every left parenthesis is "matched" by a right parenthesis (of course this is far from being a formal definition). If there is no left parenthesis, then everything is OK.

Once you accept that, there is absolutely nothing wrong about the empty string – it is a string like any other. In particular, it is a string over your alphabet with balanced parentheses.

One way to formally define your language is using a context-free grammar. While there are many possible grammars, here is one that tried to capture the "matching" aspect when scanning the string from left to right:

$$
\begin{align*}
&S \to \epsilon \\
&S \to xS \\
&S \to yS \\
&S \to (S)S
\end{align*}
$$


The problem is NP-complete and is thus not likely to admit a polynomial time algorithm.   Below is a proof of the NP-completeness of the problem, shown by a reduction from 1-in-3-SAT.

Let $\phi$ be an instance of 1-IN-3-SAT, where we are given a 3-CNF-SAT formula
asked to find a satisfying assignment where each clause is satisfied by exactly
one literal.  Let $V(\phi)$ be the set of $n$ variables, and $C(\phi)$ be the
set of $m$ clauses.

We construct an instance $G = (A,B,E)$ with a budget of $b = n + m$ (the allowed
number of blue vertices).

For each variable $x \in V(\phi)$, construct two red vertices $v_x$ and
$v_{\overline{x}}$ in $A$ together with $b+1$ blue vertices in $B$ adjacent to
both of them.  This forces exactly one of $v_x$ or $v_{\overline{x}}$ to be
flipped.  We also end up with $n$ flipped "variable vertices", thus using the
first part of the budget.

Remark: $\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$ are the only vertices in
$A$.

For each clause, say $c = x \lor \overline{y} \lor z$, we create $b+1$ blue
vertices and three extra red vertices $v_{x \in c},v_{\overline{y} \in c},v_{z
\in c}$, all in $B$.  Let $v_x,v_{\overline{y}},v_z$ all be fully adjacent to
the $b+1$ blue vertices and connect $v_x$ to $v_{x \in c}$, $v_y$ to
$v_{\overline{y} \in c}$, and $v_z$ to $v_{z \in c}$.

Now, since each clause gadget has $b+1$ blue vertices, we know that either one
or three literals in that clause have been flipped.  Suppose that three have
been flipped for one of the clauses.  But then we use at least budget $n + m +
2$.

Suppose that $\phi$ is a yes instance with a 1-in-3 assignment $\alpha: V(\phi)
\to \{\top,\bot\}$.  Flip every vertex which corresponds to $\alpha$.  Since
every clause is satisfied by exactly one variable, for each clause there is now
one blue vertex, and for each variable, exactly one of them is blue, hence we
have $n + m = b$ blue vertices.


Why are FPGA's less efficient than fully hard-coded ASIC's?

Functionality of FPGAs in very coarse lines:
At the core functionality of FPGAs are small memories called Look Up Tables (LUTs). An FPGA instead of actually compute in hardware the output of a function, say f(x), what it does is store in these small memories all possible outputs of f. So next time an input x is given fpga passes x as address in a small memory and "looks up" the answer. As it happens with all kind of memories the larger the memory the bigger the delay. So FPGAs are consisted of "a lot" of very small LUTs distributed all over their surface. Every LUT "solves" a tiny subproblem and passes the answer to subsequent LUTs for further processing (answers). Loading the LUTs with different answers and connecting them in a programmable way gives FPGAs the ability to solve any kind of problem.

LUTs are interconnected each other in an hierarchical manner. That is, as it happens with computer networks, or with buildings, it would be infeasible to connect via road each building with every other, buildings are interconnected in an hierachical manner where you have small streets, bigger streets, highways etc. So to route a package from A to B you don't have a direct-short/fast-link between A and B, but instead you may use a lengthier route which is consisted of various kinds of roads.
According to the previous analogy LUTs are the buildings and roads are the signal interconnections between LUTs. In FPGAs LUTs which are a kind of processing units are fixed in specific places, so in order to pass a signal from one LUT to another you have to follow the specific route hierarchy of FPGA. Instead in an ASIC you can place processing units in more efficient manner, and also make direct interconnection where is critical to do so, in order to minimize the delay.
Even the simplest form of processing in an FPGA (consisting only of programmable logic) has to be in the form of a LUT. For example to compute the output of a 2 input AND gate you would need a LUT. In an ASIC you would need just an AND gate. The total circuitry of the LUT certainly has greater delay that just an AND gate of the same technology.
To sum it up the sources of inefficiency of an FPGA are the

routing delay you might have due to fixed routing hierarchy and
circuitry overhead of LUTs themselves

Have in mind also that an FPGA is actually an ASIC, in which the "specific application" is to be programmable!


Question on interpreting logical notation, relating to alphabets, theoretical comp sci

Since $t$ and $s$ aren't quantified, the expression $\exists x\in\Sigma^*\;(t=sx)$ is a predicate $P(s, t)$ in inputs $t$, and $s$. In other words, we could write
$$
P(s, t)\stackrel{\text{def}}{\equiv}\exists x\in\Sigma^*\;(t=sx)
$$
meaning "$P(s, t)$ is true if and only if there is a string $x$ over $\Sigma$ for which $t$ is the concatenation of $s$ and $x$". In answer to your question, $t=sx$ isn't an alphabet, but is a condition, namely that $t$ (a string) can be expressed as the string $s$ followed by the string $x$.

Look at some examples, with $\Sigma = \{a,b\}$,

Is $P(a, abb)$ true? It is if we can find a string $x$ such that $abb=ax$. Obviously $x=bb$ works here, so $P(a, abb)$ is true.
Is $P(ba, abb)$ true? It is if we can find a string $x$ such that $abb=bax$. There's no $x$ we can use here, so $P(ba, abb)$ is false.

In general, it's not hard to see that $P(s,t)$ can be interpreted as "$s$ is a prefix of $t$".

In a different universe of discourse, if $s, t, x$ were integers, can you see that $\exists x\in\mathbb{N}\;(t=sx)$ would mean that $s$ divides $t$?


criterion for two line segments intersecting

You need to know about the orientation test.

For any three points, compute the determinant

$$\Delta_{123}=\left| \begin{array}{ccc}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
x_3 & y_3 & 1 \end{array} \right|.$$

This is twice the signed area of the triangle $123$. When it is $0$, it tells you that the three points are aligned. Otherwise, it tells you on what side of the line joining two points the third lies.

In your case, there is an intersection if $1$ and $2$ are on either sides of $34$, while $3$ and $4$ are on either sides of $12$:
$$(\Delta_{134}>0)\ne(\Delta_{234}>0)\land(\Delta_{123}>0)\ne(\Delta_{124}>0).$$

It is up to you to decide what to do in cases of perfect alignments.

As an extra goodie, the $\Delta$'s can be used to compute the coordinates of the intersection. (Let $P$ be the intersection point, interpolated along the segment $P_1P_2$: $P=(1-t).P_1+t.P_2$; it is easy to show that $(1-t)\Delta_{134}+t\Delta_{234}=0$ and to find the value of $t$.)


Best random permutation employing only one random number

Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to predict which permutations they are, but you have nonetheless determined that fact.) [1]

$log_2{52!}$ is about 225.6, so with a single 64-bit random number, you can only generate one out of every 4372488437452686306097090522819848184377442426979 permutations. With four 64-bit random numbers, you'd have no trouble generating all of them. $log_2{64!}$ is just under 296, so it would require five 64-bit numbers.

Since your permutation-generator is deterministic, you cannot invent more possibilities by manipulating the algorithm. The best you can do is to ensure that it is a homomorphism; that every random number is mapped onto a different permutation. Beyond that, you could investigate whether the one-in-4372488437452686306097090522819848184377442426979 sample of the universe of permutations exhibits any biases. For example, is each individual permutation position in the same evenly distributed? Is there a correlation between two (or more) positions? I sincerely doubt that trying to emulate a physical shuffle will improve these statistics more than the simple mathematical approach outlined below.

As xkcd reminds us, there is no such thing as an intrinsically random value. The only meaningful question we can answer is whether a sequence of pseudorandomly generated values is "random-like".

So let's first figure out how to transform the $i$ bits of randomness into $2^i$ distinct permutations. The following generic procedure should work:

Predefine some function $f$ which maps $[0, 2^i)$ onto $[0, n!)$.
For each permutation, given a random number $x$, compute ${q_0,...,q_{n-1}}$ and
${r_0,...,r_{n-1}}$ as follows:

$q_0 = f(x)$
$r_i = q_i \mod (n-i)$
$q_{i+1} = {{q_i - r_i}\over{n - i}}$

Perform a Fisher-Yates shuffle using ${r_0,...,r_{n-1}}$ as the "random numbers".

(Aside from expanding the initial seed into the range $[0,n!)$, this is precisely the solution proposed by Yuval, just written out in more detail.)

Then you could start to measure the "randomness" of a proposed function $f$ by measuring the distribution of the values of each $r_i$ over the range of $f$. The next step might be to look at the distribution of $<r_i, r_j>$ for each pair $0 <= i < j < n$

One really simple definition of $f$ is:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor$$

Assuming you calculate this with precise rational arithmetic, this gives a surprisingly reasonable set of individual $r_i$ distributions for a 52-shuffle given a 64-bit random number. [2] You'll have to decide whether that's good enough for you. If it turns out to not be, there are other possible transformations which might do better. Another simple one would be replacing the above with:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor + p \mod n!$$

where $p$ is some large prime.

[1] This information-theoretic argument is based on the permutation-generation algorithm being stateless. If each random number is in some way combined with all previously generated random numbers without losing (too much) information, then the universe of possible permutations could be much larger. (This condition is not satisfied by simply combining the two random numbers with some arithmetic or bitwise operation whose value has the same number of bits as each of the arguments.) I think that's a reasonable assumption because the original question was cast in the context of a client-server architecture; in such systems maintaining co-ordinated state between the disconnect components is generally more complicated than exchanging a few more bits in each transaction.

[2] I didn't do much more than look at some histograms and a couple of correlations and a chi-square or two, but it was all really simple python, so I'm sure you could reproduce my limited research in a few minutes.


Efficiently deciding whether TM accepts all inputs in at most $k$ steps

Given a 3CNF formula on $n$ variables, we can construct in polynomial time a Turing machine with polynomially many states $a(n)$ that accepts a truth assignment and in polynomial time $b(n)$ checks whether it satisfies the formula, and if so, enters an infinite loop. If you believe ETH, then checking whether this machine halts on all inputs in $b(n)$ steps should take time $2^{\Omega(n)}$, indicating some kind of exponential blow-up.


Indeed.

Let the fragment at a particular stage be :
{1,2},{5,6},{3},{4}.

Now the fragment {1,2} will connect with the least weight outgoing edge which is 1-3 and fragment {5,6} will connect with the least weight outgoing edge which is 1-5 to create the fragment {1,2,3,5,6} and {4} and finally it connects to {4} with edge {2-4}.

Hope this helped.


NP-hardness of maximum set cover with even/odd coverage requirement

One can rephrase your question as follows:

  Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.

A very similar problem was shown to be NP-complete by Stadnicki on cstheory:

  Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?

This implies that your problem is intractable as well.


Homework? I start with hints. Integer values assumed.

Reduction. Make two copies of the vertices in the graph (odd and even) and rewire the graph such that each odd length edge of the graph is between the even and odd copies.

Direct. The algorithm keeps two values (for each pair of vertices): the length of the even length and odd length shortest paths. You can adapt Floyd if you realize that odd+odd = even (etc).


Building heaps and heapsort using linked list

doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list.
merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.


Run time of product of polynomially bounded numbers

Computing the product sequentially, we need to perform $n-1$ multiplications of numbers of size $O(C^n n^{cn})$, for some constant $C$ corresponding to the constant in $O(n^c)$. Using algorithms for fast integer multiplication, each of these requires $\tilde{O}(C\log n + cn \log n) = \tilde{O}_c(n)$, so in total the time is $\tilde{O}_c(n^2)$ (the $\tilde{O}$ hides logarithmic factors).


Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode

count = new int[C] (array of integers)
for every a[i] in a
   count[a[i]]++
for i = 1, i < C, i++
   count[i] += count[i-1]

To Answer a query for a given k you just return count[k - 1]


Undecidability of checking whether all words can be generated from a context-free grammar?

Let $T$ be a one-tape Turing machine. A snapshot of a Turing machine is the contents of its tape, where the location of the head is preceded by the current state of the machine (encoded using a disjoint set of symbols).

We can encode a halting computation of $T$ on the empty string as a string $s_0 \# s_1^R s_2 \# s_3^R \# \ldots \# s_n$ (or $s_n^R$, according to the parity of $n$), where $s_0,\ldots,s_n$ is the sequence of snapshots encountered during the run of $T$.

We can check that a string does not code a halting computation as follows:

It is of the form $\Sigma^*\# s \# \Sigma^*$, where $s$ doesn't contain $\#$ but doesn't correspond to a valid snapshot. (More accurately, we have two corner cases corresponding to the first and last snapshot, and we might have to count the number of $\#$ in the prefix to determine whether it should be a snapshot or its reverse.)
It is of the form $s_0 \# \Sigma^*$, where $s_0$ doesn't contain $\#$ but doesn't correspond to an initial snapshot.
It is of the form $\Sigma^* \# s_n$ (or $s_n^R$), where $s_n$ doesn't contain $\#$ but doesn't correspond to a final snapshot (i.e., the Turing machine is not in a final state).
It is of the form $\Sigma^* \# s_i \# s_{i+1}^R \# \Sigma^*$ (or $s_i^R \# s_{i+1}$, according to the parity of $\#$ in the prefix), where $s_i,s_{i+1}$ do not contain $\#$ but $s_{i+1}$ is not the snapshot following $s_i$.

With some care, we can express all of these conditions as a context-free grammar. Here it is important that we encode the computation by reversing any other snapshot, since this enables us to ascertain that $s_{i+1}$ doesn't follow $s_i$ in a context-free manner (roughly speaking, this is just the language $w\#w^R$ with small modifications).

This context-free grammar generates $\Sigma^*$ if and only if $T$ doesn't halt on the empty string. It follows that universality of context-free grammars is co-r.e.-hard. It is also co-r.e.: if the context-free grammar is not universal, then there is a witness for it, namely a string not generated by the grammar (recall that the word problem for context-free grammars is decidable). Hence universality of context-free grammars is co-r.e.-complete.


By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively.
Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,y iterations, where x <= i and y <= j. This will probably result into something like O(xy), if no further calculations are made per iteration.

Finally, are you sure about this problem? It is rather a combinatorial problem that does not involve any algorithm. The problem can rephrased as: how many different permutations one can get from the following string:

RRRRDDD

Where R appears x times, and D y times? This is merely a permutation with repetition: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm


Big O notation for Average case in Linear search

Let us recall the definition of big-O notation.
If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n > n0, 0 ≤ g(n) ≤ c f(n)
Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 2.


Finding sequence of pairs with second element of previous pair matching first element of next pair

The integers of your problem form nodes, the pairs form directed edges. Then you can use Tarjan's strongly connected components algorithm to find the groups of nodes that form a cycle.


Can we add dependent type into an existing imperative programming language?

So, it's possible, but there are certainly some barriers:

What kinds of expressions are allowed in types? What does it mean for a type to have a side-effect? Can typrchecking my program perform IO?
Just because dependent types are in the system doesn't mean they provide a type safe language. It may be possible to produce proofs of False if the underlying type system is not consistent.
Many imperative languages don't have type systems complex enough to make dependent types useful. For example, Go has no higher kinded types, so if you can't index types by types, indexing types by values probably won't work.
Depending on the language, some additional type annotations might be necessary to make type checking decidable.
It may be hard to interpret dependent types in the context of side effects. What does a value of type $x=y$ even mean if $x,y$ can change their values at runtime? Does this mean a term can be well typed at one point, and dynamically become ill typed? Or can you only use dependent types for immutable values?

I'm sure that imperative dependent types are possible. In particular, I'd keep my eyes on Rust for adding these in a limited way.

But doing dependent types in a pure functional language is just so much easier.


How does the cpu know which process to wake?

TL;DR
The CPU doesn't know anything. The operating system (OS) knows it all.

The CPU is rather a stupid machine that activates one instruction at a time, without knowing what that instruction "means" nor to which program it "belongs". To the CPU eyes there is only a single program that runs (maybe, up to interrupts that "jump" to the interrupt service routine and then goes back to THE PROGRAM.

The program that does the magic and allows us running multiple programs "at the same time" over a single CPU is the OS.
The OS keeps a list of processes that are ready to run, with all the information needed -- their priorities, their memory regions, the point in the code where they stopped, etc.

Every now and then a timer interrupt is received causing the scheduler (which is part of the OS) to run. The scheduler registers the process that was currently running as "stopped" and chooses one of the waiting processes, restoring its meta-date (stack, etc.), and jumps to the point where that process stopped last time.

This gives you the illusion of running multiple processes simultaneously. But at the bottom of it, there is only one program that runs -- the OS -- and it gives priority to (or, calls) user loaded programs.

Regarding your question about inra-process communication. Again, this is usually done via methods provided by the OS. When a process waits for a signal it calls an OS method that registers this process awaits a signal and blocks the processes, allowing other processes to run. When the other process  needs to send data to the first processes it uses a OS method that records the data and its destination, and (eventually) awakes the destination process. From the point of view of the first process it got blocked on a OS function which returns only when new information arrives.


$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.


Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete

Let $\langle G=(V,E), k \rangle$ be an instance of CLIQUE with $k \ge 1$, and let $n=|V|$.
Let $S$ be a new set of $n$ additional vertices.
Construct a new graph $G'=(V', E')$ with $V' = V \cup S$ and $E=E' \cup (S \times (E \cup S))$.
Now consider an instance $\langle G', n+k \rangle$ of your problem.
If $G$ has a clique of size $k$ containing the vertices in $C \subseteq V$ then $G'$ has at least one clique of size at least $n+k$. Pick, e.g., the clique induced by $C \cup S$.
If $G'$ has a clique or an independent set of size $n+k$ then let $C$ be the set of vertices that induce such a clique or independent set set.
Since $C \cap S \neq \emptyset$ and $|C| \ge 2$, $C$ cannot be an independent set and therefore it is a clique. Then $C' = C \setminus S$ is a clique of size at least $n+k-n=k$ that is also a subgraph of $G$.


I believe you have misunderstood the question. You are given a black box that can answer queries of the form "does $X$ have a subset summing to $Q$", and you need to construct an algorithm that given $X$ and $Q$, finds a subset summing to $Q$ if one exists.

Here is a hint:

  Choose an arbitrary $x \in X$. Ask the black box whether there is a subset of $X - x$ summing to $Q - x$.


Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $

The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $A_{TM}$, in order to show undecidability.

Perhaps you meant to ask about the other direction?

At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed:

Given $M_1,M_2$ as input for $L_c$, construct a new machine $N$ that works as follows: given input $x$, $N$ ignores it (i.e., erases $x$ from it's tape), and then starts simulating $M_1$ and $M_2$ on every word $w\in \Sigma^*$, in canonical order. Note, however, that in order to simulate $M_1$ and $M_2$ on all words, we cannot simply run them on each word arbitrarily, as we might get stuck (we do not use an oracle to $A_{TM}$). Instead, we run them in parallel: run $M_1$ and $M_2$ on each of the first $k$ words in $\Sigma^*$ for $k$ steps, and then increase $k$ by 1. This is a fairly common trick, but it's quite clever.

Now, if at any point both $M_1$ and $M_2$ accept, then $N$ accepts. Otherwise, it keeps running and increasing $k$ forever.

The reduction is completed by sending $<N,\epsilon>$ to the $A_{TM}$ oracle (or, alternatively, it's complete if you treat it as a mapping-reduction).

Note that $N$ accepts $\epsilon$ (and any other word) iff there is a word that is accepted by both $M_1$ and $M_2$.


Is a subgraph either a spanning subgraph or a full subgraph?

On your question "isn't a full subgraph actually a spanning subgraph?". The answer is no, a full subgraph doesn't need to be a spanning subgraph. By your definition, a full subgraph can have lesser number of vertices than in the original graph. However, a spanning subgraph must have exactly the same set of vertices in the original graph.

On your second question "how to calculate the number of spanning subgraphs of $G$ as a function of number of nodes in $N$." Since it is a fact that graph $G = (N,A)$ with differing $A$ will have differing number of possible spanning subgraphs, I suspect you might have misunderstood the question. For example, does the question actually only ask for an upper bound of the number of possible spanning subgraphs as function of $|N|$?


Information capacity of Ternary-based system over Binary-based

Binary (two states)

1 Megabyte = 1,048,576 bytes = 8,388,608 bits = 8,388,608 cells.  See https://en.wikipedia.org/wiki/Megabyte and https://en.wikipedia.org/wiki/Byte.  1 byte = 8 bits.

There are $2^{8,388,608}$ different possible values that can be stored in this much memory.

Ternary (three states)

Now a cell can have 3 possible values.  If we have 8,388,608 cells, each of which can have 3 possible values, then the entire memory can hold $3^{8,388,608}$ possible values.  This is the equivalent of $\lg 3^{8,388,608} = 8,388,608 \times \lg 3 \approx 8,388,608 \times 1.58 \approx 13,295,629$ bits.  This corresponds to $13,295,629/8 = 1,661,953$ bytes.

Therefore, this many ternary cells can store the same  amount of data as 1,661,953 of ordinary binary cells (as 1,661,953 MB of memory).


How to solve the recurrence: T(n) = n*T(n-1) + n?

Looks like
$$
T(n) = n! + \left(\frac{n!}{0!} +\frac{n!}{1!} +\frac{n!}{2!} +\frac{n!}{3!} + \dots + \frac{n!}{(n-2)!} + \frac{n!}{(n-1)!}\right)
$$
satisfies the recurrent relation (here $T(0) = 1$).

From this for example $T(n) \leq n!(1+e)$.


Finding a trapdoor function for the 3-partition problem

As Yuval says, it's an open question whether one can build a public-key cryptosystem whose security is based on the assumption that $\textsf{P} \ne \textsf{NP}$.  There is no known public-key cryptosystem with that property, though many cryptographers have tried to find one.  So, you're trying to solve a problem that is likely to be extremely hard to solve.

Part of the challenge is that NP-complete problems are generally hard, but that's not enough for cryptography.  Public-key cryptography also requires that there be a "trapdoor" that makes them easy.  So, you'll need to find a way to encode a secret trapdoor in the 3-partition instance that makes it easy to solve the 3-partition problem if you know the trapdoor -- but where you can prove that the existence of the trapdoor doesn't make the problem any easier for people who don't know the trapdoor.  It's not clear how to do that.  There are ways to embed a trapdoor, but then they require choosing 3-partition instances with a particular structure/format, and then solving those special instances might be easy (might be doable in polynomial time).

You might be interested in knapsack cryptography (see the knapsack tag on Crypto.SE), Impagliazzo's five worlds, this question on Crypto.SE, and Impagliazzo and Rudich's black-box separation between one-way functions and key exchange, which provides some kind of evidence that it's likely not going to be easy to do what you want (e.g., there's no black-box way to convert a NP-complete problem to a public-key encryption algorithm).


Do problems in P only reduce to NP and coNP problems?

One short answer, take $B$ be to be any problem in $\mathsf{P}$. The reduction is then powerful enough to simply solve the problem as part of the reduction, and consequently produce a trivial yes or no instance at the other end as appropriate. Then we can take $C$ and $D$ to be anything, they don't even have to be computable.

A more interesting, but conditional answer, is to take $B$, $C$ and $D$ to be any three $\mathsf{NP}$-complete problems (they don't even need to be different ones). Every $\mathsf{NP}$-complete problem is polynomial-time many-one reducible to every other $\mathsf{NP}$-complete problem, so the two reducibility conditions hold trivially. If $\mathsf{P} \neq \mathsf{NP}$, then $B$ can't be in $\mathsf{P}$, and if $\mathsf{NP} \neq co\mathsf{NP}$, then $C$ can't be in $co\mathsf{NP}$. You can do essentially the same thing by taking them all to be $co\mathsf{NP}$-complete. Taking it further, you can do this for any class in the polynomial hierarchy, and the statement being true would imply a collapse to whatever level you chose, another thing that is viewed as unlikely to happen. You could also choose a selection of $\mathsf{PSPACE}$-complete problems, and the statement would imply $\mathsf{P} = \mathsf{PSPACE}$, which also seems unlikely to be true.


Why do we use persistent data structures in functional programming?

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs.  This makes it easier to conceptualize computations and get them right.  It also makes them easier to test.

That is just a start.  Since mathematics has long worked with functions, there are plenty of reasoning techniques that we can borrow from mathematics, and use them for rigorous reasoning about programs.  The most important advantage from my point of view is that the type systems for functional programs are well-developed.  So, if you make a mistake somewhere, the chances are very high that it will show up as a type mismatch.  So, typed functional programs tend to be a lot more reliable than imperative programs.

When you work with mutable data objects, in contrast, you first have the cognitive load of remembering and managing the multiple states that the object goes through during a computation.  You have to take care to do things in the right order, making sure that all the properties you need for a particular step are satisfied at that point.  It is easy to make mistakes, and the type systems are not powerful enough to catch those mistakes.

Mathematics never worked with mutable data objects.  So, there are no reasoning techniques we can borrow from them.  There are plenty of our own techniques developed in Computer Science, especially Floyd-Hoare Logic.  However, these are more challenging to master than standard mathematical techniques, most students can't handle them, and so they rarely get taught.

For a quick overview of how the two paradigms differ, you might consult the first few handouts of my lecture notes on Principles of Programming Languages.


You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller.

Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order.

Start by sorting the input sequence, $A$, of $n$ objects
Find the largest index $k$ such that $A[k] < A[k+1]$.  If no such $k$ is found, terminate. The sequence $A$ contains the last lexicographic permutation.
Find the largest index $l$ such that $A[k] < A[l]$
Swap $A[k]$ and $A[l]$
Reverse the sub-sequence starting from $A[k+1]$ to the final element, $A[n-1]$

Note that this algorithm generates the next lexicographic permutation of $A$ in-place. To generate all permutations, you can repeat this until no more permutations are found.


When is the minimum spanning tree for a graph not unique

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.

Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.

If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest edge-weight from $F\cap C$, then we can create a second MST by swapping an edge from $F\cap C$ with edge-weight $m$ with $e$. Thus we do not have uniqueness.


Time complexity of subset sum problem with reals instead?

What model of real numbers are you using?  If it's something like floating point, where everything is really rational, just multiply through by a common denominator and you're back in the world of integers. The bit-length is only polynomially larger than the ones you started with (the common denominator is at most the product of $n$ $n$-bit numbers, so it has at most $n^2$ bits), so nothing has changed, complexity-wise.

Beyond that, things will get more complicated – can you even tell in polynomial time what numbers are represented by the input?

However, the real-number version is definitely still NP-hard, since it has the integer version as a sub-problem.


0/1 Knapsack problem with real-valued weights

Sort the items by density such that $p_1/w_1\geq p_2/w_2\geq\cdots\geq p_n/w_n$ for profits $p$ and weights $w$. Let $W(k)=\sum_{1\leq i\leq k} w_i$ be the total weight of the first $k$ items in this order. Then for capacity $c$ an optimal fractional solution is to choose items $1,\ldots,i^*$ where $i^*$ is the largest number s.t. $W(i^*)\leq c$ , and additionally a fraction of $(c-W(i^*))/w_{i+1}$ of item $i^*+1$.

Update: I misread your question. For solving the $0$/$1$ version with real-valued weights you can either round them, or apply branch-and-bound algorithms that were designed for real values, e.g. Martello and Toth's MT1R.


Is there a theory of exception hierarchies?

There's a large number of publications on exceptions, with quite a few theoretical investigations. Here is an unstructured and far from complete list with some examples. Sorry, I don't have
time at the moment for a more focussed reply.

B. Randell, System Structure for Software Fault Tolerance.
J. B. Goodenough. Exception handling: Issues and a proposed notation.
J. B. Goodenough. Structured exception handling.
B. G. Ryder, M. L. Soffa, Influences on the Design of Exception Handling.
D. Teller, A. Spiwack, T. Varoquaux, Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml.
X. Leroy, F. Pessaux, Type-based analysis of uncaught exceptions.
R. Miller, A. Tripathi, Issues with Exception Handling in Object-Oriented Systems.
S. Drew, K. J. Gough, J. Ledermann, Implementing Zero-Overhead Exception Handling.
B. Stroustrup, Exception Safety: Concepts and Techniques.
D. Malayeri, J. Aldrich, Practical Exception Specifications.
H. Nakano, A Constructive Formalization of the Catch and Throw Mechanism.
A. Nanevski, A Modal Calculus for Exception Handling.
P. de Groote, A Simple Calculus of Exception Handling.
H. Thielecke, On Exceptions and Continuations in Presence of State.
J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.
M. van Dooren, E. Steegmans, Combining the Robustness of Checked Exceptions with the Flexibility of Unchecked Exceptions using Anchored Exception Declarations.
J. A. Vaughan, A logical interpretation of Java-style exceptions.
S. Marlow, S. Peyton Jones, A. Moran, Asynchronous Exceptions in Haskell.
B. Jacobs, F. Piessens, Failboxes: Provably Safe Exception Handling.


Definition of Turing machines and rejection states

A deterministic Turing machine accepts if, and only if, it terminates in an accepting state. Any state that is not accepting is rejecting by default.  There are various equivalent ways of defining Turing machines: for example, instead of having a HALT instruction and accepting and rejecting states, you could have explicit ACCEPT and REJECT instructions.


Sensitivity and block sensitivity of specific problem, is there an errata? Arora-Barak exercise 12.4

The definition of $g$ should be: $g(x_1,\ldots,x_k) = 1$ if there exists $i \in [k-1]$ such that $x_i=x_{i+1}=1$ and $x_j = 0$ for $j \neq i,i+1$.

As for your question, whether $g=1$ iff the condition holds, or whether it is just a sufficient condition: in mathematics, when we define something, we use the word "if" to mean "iff". Check your favorite textbook, monograph or paper for many examples.


Algorithm for finding connected components checking as few edges as possible

You are looking for the minimum spanning tree for each connected component.


Abstracting away the details of their argument, what they're saying is basically:

  Suppose we have a Turing machine DoesItZork(P) that takes a program P and decides whether it zorks or not. Now we can build a Turing machine RunThenZork(P) = P() then Zork() which first runs its input, then zorks. Now, if DoesItZork(RunThenZork(P)) returns True (and P itself does not zork), then P must halt on the empty input. On the other hand, if it returns False, then P must not halt on the empty input. So we just invert the output: DoesItHalt(P) = not DoesItZork(RunThenZork(P)). So if we have a way to ensure that P never zorks on its own (which we do), then having DoesItZork gives us a solution to the Halting Problem. We know that there is no solution to the Halting Problem, therefore, there can be no DoesItZork.

As a matter of fact, this proof skips over some important details. For one, Turing machines have no concept of files, so there needs to be some mapping between Turing machines and actual computer programs. (Fortunately, such a thing does exist.)

In addition, there's an easier way to prove this, once you allow for the idea that a Turing machine can be a virus. Rice's Theorem effectively says that all non-trivial semantic properties of a program are undecidable, where a property is trivial if all Turing machines have it or no Turing machines have it, and a property is semantic if it has to do with the program's behavior rather than its encoding. Since there exist programs that are viruses, and programs that are not viruses, and viruses are defined by their behavior, it's undecidable which are which.


$k$-SAT completeness proof when $k$ is linear in number of variables

Your problem is actually in P. First of all, you can assume that no clause contains both a variable and its negation, since such clauses are always satisfied. Suppose that the instance contains $m$ clauses. Then a random assignment will falsify your formula with probability $m/2^{n/2}$. If $m < 2^{n/2}$, then this means that your formula is satisfiable. Otherwise, the input is of size at least $2^{n/2}$, and so you can go over all $2^n$ truth assignments in polynomial time.


We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N>0$ such that $f(n) \leq Cn^2$ for all $n \geq N$. We usually denote "$f(n)$ is $O(n^2)$" by "$f(n) = O(n^2)$".
An algorithm has running time $O(n^2)$ if its worst-case running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the algorithm on inputs of length $n$, then the algorithm has running time $O(n^2)$ if $T(n) = O(n^2)$.
Equivalently (and this is the point of the CLRS formulation), an algorithm has running time $O(n^2)$ if there exists some function $f(n) = O(n^2)$ such that the running time of the algorithm on an input of length $n$ is always at most $f(n)$.
If we denote the running time of the algorithm on the input $x$ by $T(x)$, and the length of $x$ by $|x|$, then we can see the difference between these two equivalent definitions by writing them out formally.
The first definition is
$$
\max_{|x| = n} T(x) = O(n^2),
$$
where the left-hand side defines a function of $n$, which we denoted above by $T(n)$.
The second definition states that for some $f(n) = O(n^2)$,
$$
T(x) \leq f(|x|).
$$
If the second definition holds, then in particular
$$
\max_{|x|=n} T(x) \leq f(n),
$$
and so
$$
\max_{|x|=n} T(x) = O(n^2),
$$
which is the first definition.
If the first definition holds, then we can take $f(n) = \max_{|x|=n} T(x)$ to obtain a function satisfying the second definition:
$$
T(x) \leq \max_{|y|=|x|} T(y) = f(|x|),
$$
where the first definition guarantees that $f(n) = O(n^2)$.


How to prove polynomial time equivalence?

The problems you mention here are variations of a problem called SUBSET-SUM, FYI if you want to read some literature on it.

What is $S_i$ in your algorithm? If it's the $i$-th element, then you assume that the minimal set will use the smaller elements, which is not necessarily true - there could be a large element that is equal to $t$, in which case there is a subset of size $1$. So the algorithm doesn't seem correct.

However, as with many optimization problems that correspond to NP-complete problems, you can solve the optimization problem given an oracle to the decision problem.

First, observe that by iterating over $k$ and calling the decision oracle, you can find what is the minimal size $k_0$ of a subset whose sum equals $k$ (but not the actual subset).

After finding the size, you can remove the first element in $S$, and check whether there is still a subset of size $k_0$ - if not, then $s_1$ is surely in a minimal subset, so compute $t-s_1$, and repeat the process with the rest of $S$.

If $s_1$ does not effect the size $k_0$, then repeat the process with $S\setminus \{s_1\}$.

It is not hard to verify that this process takes polynomial time.


Practice of setting parallelism as the default behaviour

Have fun. If you use multiple threads you need to make sure that the overhead doesn’t outweigh the savings. The number of processors to use depends on the number of available processors, their properties (hyperthreading, performance vs. power saving), and the usage of the machine including the OS. And making one task fast may have negative side effects on the machine as a whole. Summary: It’s difficult.
Set your priorities: First make it work. Second make it maintainable. Third if required measure to find performance problems and fix them by using code that is not stupid (in the last ten years 99% of my performance problems were caused by stupid code and fixed by using code that isn’t stupid), then by using good code, then by using optimised vector code. Using multiple threads should be your very last resort.


How could you "solve" the halting problem if, hypothetically, the busy beaver numbers were "small"?

To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.

Since the halting problem isn't computable, this means that no such $f$ is computable; this is a "global" phenomenon. No particular value of $BB$ is too large to be used, but rather the growth rate of $BB(n)$ prevents us from having a whole sequence of upper bounds, one for each $n$. As a low-level analogy:

  There is no polynomial function which is always above $exp(n)=2^n$. Of course, this isn't because individual values of $exp$ are too big, but rather because of the overall behavior of the function across all inputs
  .


A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights.  An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix.  The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or constant entries in the matrix).  Implicit means implied by.  Mathematicians use it as a euphemism meaning, "you should prove it yourself."

But the first paper defines a notation consistent with a Continuous-time Markov Chain, sometimes called a Markov Process, while the second paper defines a notation consistent with a Discrete-time Markov Chain.  They say

  $P$ is the transition probability matrix indicating the probability of getting from one state to another, and $\pi$ is the initial probability distribution representing the likelihood for the system to start in a certain state. [emphasis added]

They are assuming that the matrix is constant over time (thus implying the Markov property).  Implicit in the term probability is the fact that each constant is in range $[0,1]$, that the entries in every column of $P$ sum to $1$, and that the sum of the entries in $\pi$ sum to $1$.

I can't read the third paper, it is paywalled.  If the entries in every column of the matrix are required to sum to 1 then they are probabilities and they are talking about Discrete-time Markov Chains.  If the entries in every column can sum to an arbitrary number then the entries represent rates not probabilities and they are talking about Continuous-time Markov Chains.

Continuous-time Markov Chains are not the same as Discrete-time Markov Chains.  In a Continuous-time Markov Chain the edge weights do not represent probabilities, but rather transition rates.  The edge weights must be non-negative, but can be arbitrarily large, and the weights of the out-edges can sum to any non-negative number.  The sum is not required to be $1$.

With both Continous-time and Discrete-time Markov Chains the Markov property is implied by the constant edge weights (or equivalently the constant entries in the transition matrix.)


How can we find a palindrome within a string?

Of course, every letter is a one letter palindrome - so let's assume you are looking for a palindrome that is at least two letters long.

If your goal is just to find any palindrome in a string $\{a_i\}$(rather than finding all palindromes or finding the longest palindrome, for example) then you only need to consider two cases:

1) If $a_n=a_{n+1}$ for any $n$ then you have found a two letter palindrome.

2) If $a_n=a_{n+2}$ for any $n$ then you have found a three letter palindrome.

Any longer palindrome must contain a two or a three letter palindrome as a substring.


How many times an empty 4-cycle can be counted in an undirected graph?

For each set $\{a,b,c,d\}$ of four vertices, there are three possible squares: $a-b-c-d$, $a-b-d-c$ and $a-c-b-d$. This is $|S_4|/|D_4|$, where $S_4$ is the symmetric group on four points, and $D_4$ is the dihedral group, the group of symmetries of a square.

Hear a square is a set of edges forming a square. So the squares are really $\{\{a,b\},\{b,c\},\{c,d\},\{a,d\}\}$, $\{\{a,b\},\{b,d\},\{c,d\},\{a,c\}\}$ and $\{\{a,c\},\{b,c\},\{b,d\},\{a,d\}\}$. You can check that all are distinct. Every square on $a,b,c,d$ is one of these — try finding any other one. We know that this list is exhaustive because of the computation $|S_4|/|D_4| = 3$.


The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.

The idea is to randomly guess a witness for the input being a YES-instance. If you find one, your answer "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the input is a NO-instance we can never find such a witness, so we always output NO correctly.

One well-known example is the Solovay–Strassen primality test.


Proving that vertex labeling is NP-complete

Given a graph $G$, consider its complement $G'$. The graph $G'$ is a yes instance of your problem if its vertices can be ordered so that adjacent vertices are not connected by an edge in $G'$. In other words, $G'$ is a yes instance of your problem if the vertices of $G$ can be ordered so that adjacent vertices are connected. So $G'$ is a yes instance of your problem if and only if $G$ has a Hamiltonian path.


There's lots of research on this subject.  I've sometimes seen it called "time-travel debugging" in the literature, sometimes "reverse debugging".  A few minutes on Google Scholar should turn up a bunch of research publications on the subject.

See also https://softwareengineering.stackexchange.com/q/181527/34181 and https://stackoverflow.com/q/1470434/781723.