Ordering elements so that some elements don't come between others

Here's a naive algorithm. It relies ultimately on brute force, but may perform okay sometimes.

Each constraint
$(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ consists of two conjuncts; let's call them type-$A$, $i < k$, and type-$B$, $\neg(i < j < k)$. Each type-$B$ constraint can be equivalently written as a disjunction $i>j \vee j>k$, relying on the fact that $i\neq j,j\neq k$.

Collect all type-$A$ constraints. Call this $\Theta$. Check whether they are consistent, namely that this is a linearization of the ordering.  This takes $O(|S|)$-time in the number of constraints using topological sorting.
For each of the disjuncts in the type-$B$ constraint, check whether it is consistent with partial order $\Theta$. If it is not consistent, remove the disjunct. If both disjuncts are inconsistent with $\Theta$, then fail. Whenever just one type-$B$ constraint is removed, add the remaining one to $\Theta$. This step is $O(|S|^2)$.
Now there's an obvious algorithm for finding a solution, namely to consider all combinations of the type-$B$ disjunction pairs and test their consistency with $\Theta$, but this is clearly exponential in $|S|$.
One heuristic to improve performance  would be to treat the type-$B$ disjunction pairs as the branches of a tree---one pair forms the root, it's children are given by the second pair, their children by the third and so forth. Using this data structure, a solution is found by traversing the tree in a depth-first fashion. Each time a new constraint is added (using the label on a branch), consistency can be checked. Inconsistent subtrees can be pruned.
If a leaf of the tree is reached, then we have a consistent set of constraints consisting of all of the type-$A$ constraints and one disjunct of the type-$B$ constraints. Linearise the result to obtain the desired ordering.

My preferred approach would actually be to encode it into a set of constraints and use a constraint solver such as Choco. I would introduce $n$ integer variables $x_i$ in the range $[0,n-1]$ and require that they were all distinct. Then I would encode each of the constraints above directly as constraints and then let Choco do it's business.


Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

Take a binary tree with the following structure:

A traversal algorithm that considers every node in a tree must consider each node in some order. It might touch the nodes in this order: 2, 1, 3. Or this order: 1, 2, 3. And so on.

We can categorize these nodes into groups for convenience. Let us say that Node 1 is the Parent Node while Node 2 and Node 3 are Children of the Parent.

When we use terms like "pre-order", "in-order", or "post-order", we are really describing the order in which our implementation of an algorithm touches the parent node.

For example, an algorithm performs a pre-order traversal of the graph above if it touches the parent node before the child nodes. ( vis 1, 2, 3 )

An algorithm performs an in-order traversal of the graph above if it touches the parent node in between the child nodes. ( vis 2, 1, 3 )

An algorithm performs a post-order traversal of the graph above if it touches the parent node after the child nodes. ( vis 2, 3, 1 )

So, when we describe an algorithm as having a particular order, we aren't necessarily describing the algorithm--but rather we are describing the implementation of the algorithm.

For example, what if we want to implement Depth-First Search (DFS) of a more complicated graph?

Here's a larger graph traversed with a pre-order implementation of DFS:

Let us say that B and G are children of F, but none of the other nodes are considered children of F.

Notice that--given that definition--every parent node is processed before it's children. There might be several nodes processed in the course of doing that, but--no matter which parent node you check, it is guaranteed to be processed before its children.

The same goes for in-order traversal ( every parent is guaranteed to be processed in between its children ):

And post-order traversal ( every parent is guaranteed to be processed after each of its children ):

Note that all of the above are different implementations of the same algorithm, namely Depth-first Search. So, we have taken one algorithm and implemented it three different ways, each handling parents in a different order relative to their children.

In the same way, any graph traversal algorithm can be categorized as pre-order, in-order, post-order--or possibly none of the above. These terms merely describe the order in which parent nodes are processed relative to their children.

Note that the Wikipedia entry on tree traversal describes several implementations of several traversal algorithms, but is able to categorize all of these algorithms in terms of the order in which they process parents relative to their children.


Bridge theorems for group theory and formal languages

Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite nilpotent groups, soluble groups and supersoluble groups.

Finite groups also play an important role in the problem of finding a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. There is a finite number of "basic" identities, plus an identity for each finite simple group. See my answer to this question for references.

In the opposite direction, finite automata theory lead to an elementary proof of basic results on combinatorial group theory, like the Schreier formula. Based on Stallings's seminal paper Topology of Finite Graphs.

Also in the opposite direction, automatic groups are defined in terms of finite automata.

Profinite groups also play an important role in automata theory. An example is the characterization of the regular languages recognized by transition-reversible automata with
possibly several initial and final states.

For a very nice connection between context-free languages, groups and logic, see the article
by David E. Muller and Paul E. Schupp, Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems.


Are there more languages than functions?

It depends on the signature of the function.  In computability theory we typically deal with functions with the signature $f:\{0,1\}^* \to \{0,1\}$.  There is a one-to-one correspondence between functions $f:\{0,1\}^* \to \{0,1\}$ and languages $L \subseteq \{0,1\}^*$: in particular, the function $f$ corresponds to the language $L=\{x : f(x)=1\}$, and the language $L$ corresponds to the function $f(x) = 1$ if $x \in L$, $f(x) = 0$ if $x \notin L$.


Can I have a "dependent coproduct type"?

The dependent sum is a common generalization of both the cartesian product $A \times B$ and the coproduct $A + B$. It just so happens that the HoTT book introduces dependent sum by generalizing $A \times B$, because that does not require the boolean type to be defined first.

The coproduct is a special case of dependent sum. Given types $A$ and $B$, consider the type family $P : \mathtt{bool} \to \mathcal{U}$ defined by $P(\mathtt{false}) = A$ and $P(\mathtt{true}) = B$. The dependent sum $\sum_{b : \mathtt{bool}} P(b)$ is equivalent to $A + B$. By the way, you can also get $A \times B$ as a dependent product $\prod_{b : \mathtt{bool}} P(b)$.

You ask what is special about products and function types. There are many, many reasons why $\sum$ and $\prod$ are "necessary". In terms of logic, they are necessary because they correspond to $\exists$ and $\forall$ by the propositions-as-types correspondence (but that only shifts the question to "why are $\exists$ and $\forall$ necessary?"). In terms of category theory, $\sum$ and $\prod$ are necessary because they are the left and right adjoint to substitution. Ask a more secific question if you would like to know more.


Path cover with paths of bounded length, in the plane

This smells like a problem that might be NP-hard, so you'll probably have to
use one of the standard methods for dealing with intractability: e.g., devise
a heuristic, or formulate it so you can apply an existing solver.

I suggest that you try formulating it as a mixed integer linear programming
(ILP) problem, and if that's too slow, try simulated annealing.  I'll sketch
both approaches.

Integer programming

We'll think of our task as selecting a subset of the edges, so that they can
be pieced together into paths as required.  Introduce a zero-or-one variable
for each edge to indicate whether or not it is selected.  In other words, for
each pair of vertices $i,j$, introduce a zero-or-one variable $x_{i,j}$, with
the intended meaning that $x_{i,j}=1$ implies the edge $(i,j$) is included.

We'll add a bunch of inequalities that capture the requirement that the
selected edges form a bunch of paths of the desired form:

Each vertex (other than $r$) has exactly one edge out of it:
$\sum_j x_{i,j} = 1$ for each $i \ne r$.
Each vertex (other than $r$) has at most one edge into it:
$\sum_i x_{i,j} \le 1$ for each $j \ne r$.
$r$ has no edges coming out of it: $x_{r,j} = 0$ for all $j$.
For each vertex $i$ introduce a variable $y_i$ (not restricted to integer
values), with the intended meaning that $y_i$ captures the distance from
$r$ to $i$ along the harness that connects the two.  We'll require that
no harness is longer than the limit: $y_i \le b$ for all $i$.  Also
$y_r = 0$.
Finally, we'll ensure the consistency of the $x$'s and $y$'s by adding

$$y_i \ge y_j + \ell(i,j) - (b + \ell(i,j)) (1-x_{i,j})$$

for all $i,j$, where $\ell(i,j)$ is the length of the edge $(i,j)$.
(Notice how this works: if edge $(i,j)$ is not selected, i.e., $x_{i,j}=0$,
this inequality implies only $y_i \ge 0$; but if edge $(i,j)$ is
selected, this inequality ensures that $i$'s distance from $r$ is
$j$'s distance from $r$ plus the length of the edge between $i$ and $j$.)

Now ask an ILP solver to minimize the objective function
$\sum_{i,j} \ell(i,j) x_{i,j} $, subject to these inequalities.
The solution will correspond the optimal solution to the original problem.

You'll have to test to see whether existing off-the-shelf ILP solvers
(e.g., CPLEX) are able to solve this ILP instance efficiently.  You end
up with an ILP instance with about $|V|^2$ variables and inequalities.  If it takes too long, some solvers will have an option to specify a "timeout", so they give you the best solution they've found so far within the specified time, even if it isn't necessarily the globally optimal solution.

Some minor optimizations are possible.  For instance, we can omit any
edge $(i,j)$ whose length exceeds $b$ (eliminating the variable $x_{i,j}$
from the linear program, as it is forced to be zero).  Also, for any pair
of edges $(i,j),(k,l)$ that "cross" (i.e., their line segments intersect),
we know they can't both be simultaneously selected, i.e., we can add the
inequality $x_{i,j}+x_{k,l}\le 1$.  You probably don't want to add all
such inequalities, but you could try adding a small number (e.g., for
all pairs of short edges).  You can also add the inequality $y_i \ge \ell(r,i)$ for all $i$, in case that helps the solver.

This approach is also fairly flexible: for instance, we can limit the number of
paths that are allowed to be used (by adding an inequality to upper-bound
$\sum_i x_{i,r}$) or make other minor adjustments.  You can limit the number of edges allowed in each path by adding variables $z_i$ that count the number of hops between $i$ and $r$ along the harness connecting the two, and adding the inequality $z_i \ge z_j + 1 - K (1-x_{i,j})$ where $K$ is a suitably large constant (larger than the maximum number of edges per path) and then adding inequalities to upper-bound all of the $z_i$'s.

Simulated annealing

Another option is to use some form of local search, such as simulated
annealing.  The idea is that we start from a candidate solution and at
each step try making a small, randomly selected, local change and check
whether it is an improvement or not.

Part of the art of simulated annealing is to choose a set of allowable
changes; at each step, you'll randomly select from this set to obtain
your candidate change.  In this case, one reasonable class of "changes"
is: Pick a pair of vertices (probably ones that aren't too far apart),
and swap which paths they are in.  For example, suppose I've selected
vertex $b$ and vertex $e$, where the path containing $b$ looks like
$\cdots \to a \to b \to c \to \cdots$ and the path containing $e$ looks
like $\cdots \to d \to e \to f \to \cdots$.  Then after the swap operation
you'll end up with the two paths $\cdots \to a \to e \to c \to \cdots$
and $\cdots \to d \to b \to f \to \cdots$.  You can then evaluate whether
this increased or decreased the objective function.  You might want to
experiment with the distribution on pairs of vertices (do you try to
make nearby vertices more likely to be selected than far-apart ones?).

There may be other operations that would be useful to add and make
simulated annealing work better.  Selecting an appropriate set of
operations and choosing the parameters for simulated annealing is largely an art, and may require some experimentation.  It's hard to predict how well this will work without trying it.


Nobody can say what every computer will do, but there are some reasonable assumptions.

When you access data that is not in the cache, you want it to be in the cache afterwards. So the CPU will read the data from memory, and move it to the cache. That's one half of the job.

There is some part of the CPU that needs the data, and we want to get the data to that part of the CPU as fast and as cheap as possible. There is already a mechanism in place to provide the data if it is in the cache. So the CPU could just move the data to the cache, then use the existing mechanism. That's cheap and easy.

Or the CPU can move data from memory to the place where it is needed either simultaneously with the cache, or even before the data is moved to the cache. That has the advantage that the data may appear a little bit faster where it is needed. It has the disadvantage that now the two situations (in cache, not in cache) need to be handled by different hardware. That is likely more complicated and more expensive.

Which one is chosen depends on how much quicker the more complicated method is, how much it costs more, and how much the cost is compared to other possible improvements.


Permutation of words that have matched parentheses

When there are more than one type of parentheses (say [] and ()), the problem is NP-complete. The proof is the same as the proof for the palindrome problem except that in the reduction, 0s and 1s in $w$ are changed to [s and (s respectively, 0s in $v_i$ are changed to ]s and 1s in $r_k$ are changed to )s.

When there are only one type of parentheses (say ()), the problem can be solved in polynomial time.

For a character $c\in\{$($,$)$\}$, denote
$$
t(c)=\begin{cases}
1 & \text{if }c\text{ is '('},\\
-1 & \text{if }c\text{ is ')'}.
\end{cases}
$$
For a string $s=s_1s_2\ldots$ where $s_i\in\{$($,$)$\}$, denote $f(s)=\sum_{i=1}^{|s|}t(s_i)$ and $g(s)=\max_j\sum_{i=j}^{|s|}t(s_i)$. We have
$$
\begin{align}
f(s_1s_2)&=f(s_1)+f(s_2),\\
g(s_1s_2)&=\max\{g(s_1)+f(s_2), g(s_2)\}.
\end{align}
$$

We say a string $s$ is potentially accepted if for any prefix $p$ of $s$, $f(p)\ge 0$. Note $s$ is potentially accepted if and only if $f(s)\ge g(s)$. Also note $s\in L$ if and only if $f(s)=0$ and $s$ is potentially accepted.

Note if $\sigma$ is a valid permutation, and $f(x_{\sigma(i)})<0$ and $f(x_{\sigma(i+1)})\ge0$ for some $i$, we can swap the two elements to get another valid permutation. This suggests that we can arrange all $x_i$'s satisfying $f(x_i)\ge 0$ (say $x_{r_1},\ldots,x_{r_k}$) on the first $k$ positions, then arrange other $x_i$'s on the rest positions.

For the first $k$ positions, we process greedily. That is, say $\sigma(1),\ldots,\sigma(j)$ is determined, if there is some $i$ such that $x_{\sigma(1)}x_{\sigma(2)}\ldots x_{\sigma(j)}x_{r_i}$ is potentially accepted, we arrange $x_{r_i}$ on position $j+1$, i.e. $\sigma(j+1)=r_i$. Otherwise, we cannot arrange these $x_{r_i}$'s on positions $1,\ldots,j$ too, so we assert there is no valid permutation.

For the rest positions, we arrange them according to $g$ from big to small. That is, $g(x_{\sigma(k+1)})\ge g(x_{\sigma(k+2)})\ge\cdots\ge g(x_{\sigma(n)})$. If this arrangement is invalid, i.e. the final string does not belong to $L$, we assert there is no valid permutation. The correctness of this process comes from the following lemma:

  If for some valid $\sigma$ such that $f(x_{\sigma(k+1)}),\ldots,f(x_{\sigma(n)})<0$ and for some $i$, $g(x_{\sigma(k+i)})<g(x_{\sigma(k+i+1)})$, we can swap $x_{\sigma(k+i)}$ and $x_{\sigma(k+i+1)}$ to get another valid permutation.

Proof of the lemma. For convenience, denote $s_0=x_{\sigma(1)}\ldots x_{\sigma(k+i-1)}$ and $s=x_{\sigma(1)}\ldots x_{\sigma(n)}$. Note after swapping, $f(p)$ is not changed for prefix $p$ of $s$ such that $|p|\le |s_0|$ or $|p|\ge |s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}|$, we need only to show $s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}$ is potentially accepted. Note
$s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}$ is potentially accepted, we have
$$
\begin{align}
g(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)})\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)})
\end{align}
$$
or
$$
\begin{align}
g(s_0)+f(x_{\sigma(k+i)})+f(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),\\
g(x_{\sigma(k+i)})+f(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),\\
g(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),
\end{align}
$$
or
$$
\begin{align}
g(s_0)+f(x_{\sigma(k+i+1)})+f(x_{\sigma(k+i)})&\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),\\
g(x_{\sigma(k+i+1)})+f(x_{\sigma(k+i)})<g(x_{\sigma(k+i+1)}) &\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),\\
g(x_{\sigma(k+i)})\le g(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),
\end{align}
$$
which means
$$
\begin{align}
g(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)})\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}).
\end{align}
$$
Hence $s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}$ is potentially accepted.


Some Questions related to Linear programming

Let me answer your questions one by one:

The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum solution.
When adding slack variables, the optimum value remains unchanged. As an example, you change $x \geq y$ to the equivalent $x = y+z$, where $z \geq 0$.
You never minimize $3x+y=2$. What you minimize is a linear function, not an equation. Minimizing $3x+y$ and maximizing $-(3x+y)$ are the same.


Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths?

There is no comparison based sorting algorithm faster than O(n log n). So this is all theory.
There are plenty of situations where sorting an array takes O(n) time. These are special cases, but happen a lot. For example a sorted array. Or a sorted array with few elements changed. And there are cases where sorting the whole array isn’t needed. Like if I see my address book on the screen, apparently sorted - but only the bits that I’m looking up are sorted.
Log n isn’t very large, so O(n) doesn’t mean it’s faster than say Quicksort for anything that is small enough to sort.
Server farms rarely sort. Databases are indexed, and indexes are updated, no sorting needed.
The effect on society would be zero. Some people would be able to handle their computational needs for slightly less money, that’s all the difference.


Since $|x| = \max (x, -x)$ for any $x \in \mathbb{R}$, we have $|x_i - \mu| = \max(x_i - \mu, \, \mu - x_i)$. Therefore,
$$
\max_i |x_i - \mu| = \max \left(\max_i (x_i - \mu), \, \max_i (\mu - x_i) \right) = \max (g - \mu, \, \mu - l),
$$
where $g = \max_i x_i$ and $l = \min_i x_i$.
Finally, the function $\max(g - \mu, \mu - l)$ has minimum at $\mu = \frac{l + g}{2}$.


There is no such problem. All problems that can be solved (i.e., decided) by a non-deterministic Turing machine $T$ can also be solved by a deterministic Turing machine that simulates $T$.


You're wrong about $L^+$:

$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$


What is the Expected run time of an algorithm that randomly generates N unique strings of length D?

The usual way to approach your problem is as follows. When you select the $i$th string, there are $i-1$ previous strings that you have to avoid, so the probability that you generate a new string successfully is $\frac{2^D-(i-1)}{2^D}$. The expected number of strings generated before you generate a new string is thus $\frac{2^D}{2^D-(i-1)}$ – this is just the expectation of a geometrically distributed random variable. Considering all $N$ steps, the overall expectation is
$$
\sum_{i=1}^N \frac{2^D}{2^D-(i-1)} = 2^D \sum_{j=0}^{N-1} \frac{1}{2^D-j} \approx 2^D \log \frac{2^D}{2^D-N} \approx \frac{2^D}{2^D-N} N.
$$


Betweenness Centrality measurement in Undirected Graphs

Betweenness centrality is defined on connected graphs. Suppose a graph $G$ with two connected components, $G_1$ and $G_2$, and consider a node $v \in G_1$, then the betweenness centrality for $v$ is

$$C_B(u)=\sum_{s,t \in G}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=$$

$$\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{0}{0}}$$

But if you want to treat each connected component as a single graph, you can also calculate the betweenness centrality independently for each component.


My current research:

Initial attempt at some general rules

One can try to make some general rules for solving the rational comparison:

Assuming all positive $a,b,c,d$:

$$
a < b \wedge c \ge d
 \Longrightarrow
\frac a b < \frac c d\\
$$
This basically means, if the left side is less than one, and the right side is at least one, the left side is less than the right side. In the same vein:

$$
a \ge b \wedge c \le d
 \Longrightarrow
\frac a b \not\lt \frac c d\\
$$

Another rule:

$$
(b > d) \wedge (a \le c)
 \Rightarrow
\left[\frac a b < \frac c d\right]
$$
I think of this rule as logical, since the greater the denominator, the smaller the number, while the greater the numerator, the larger the number. Hence if the left side has a greater denominator and a smaller numerator, the left will be smaller.

From here on in, we will assume that $a<c \wedge b < d$, because otherwise we can either solve it with the rules above, or reverse the question to $\frac c d \overset ? < \frac a b$, and we end up with this condition anyhow.

Rules:
$$
\left.
\\
\frac {(b-a)} b < \frac {(d-c)} d
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$
This rule basically states that you can always subtract the numerators from the denominators, and set the results as the numerators, to obtain an equivalent problem. I'll leave out the proof.

$$
\left.
\\
\frac {a} b < \frac {c-a} {d-b}
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$

This rule allows you to subtract the left numerator and denominator from the right numerator and denominator for an equivalent problem.

And of course there is scaling:

$$
\left.
\\
\frac {ak} {bk} < \frac {c} {d}
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$
You can use scaling to make the subtraction rules above more significant.

Using these rules you can play around with things, apply them repeatedly, in smart combinations, but there are cases where numbers are close, and pathological.

By applying the previous rules, you can reduce all these problems to:
$$
\left.
\frac a b < \frac {ap+q} {bp'+q'}
\iff
\frac a b < \frac {q} {q'}
\right|_{a>q,b>q'}
$$

Sometimes you can solve this directly now, sometimes not. The pathological cases are usually in the form:

$$
\left.
\frac a b < \frac {c} {d}
\right|_{a>c,b>d,c\in \mathcal O(a), d \in \mathcal O(b)}
$$

Then you flip it, and result in the same thing, just with one bit less. Each application of the rules + flip reduces it by a digit/bit. AFAICT, you cannot quickly solve it, unless you apply the rules $\mathcal O(n)$ times (once for each digit/bit) in the pathological case, negating their seeming advantage.

Open problem??

I realized that this problem seems to be harder than some current open problems.

An even weaker problem is to determine:

$$ad \overset ? = bc$$

And yet weaker:

$$ad \overset ? = c$$

This is the open problem of verifying multiplication. It is weaker, because if you had a way to determine $ad \overset ? < bc$, then you can easily determine $ad \overset ? = bc$, by testing using the algorithm twice, $ad \overset ? < bc$, $bc \overset ? < ad$. Iff either is true, you know that $ad \ne bc $.

Now, $ad \overset ? = c$ was an open problem, at least in 1986:

  The complexity of multiplication and division. Let us begin with the very
  simple equation ax = b. When considered over the integers, testing its solvability and finding a solution x is possible by integer division with remainder zero. For checking a given solution x, integer multiplication will suffice, but it is an interesting open problem whether there are faster methods of verification.

  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of
  Computational Complexity

Very interestingly, he also mentioned the question of verifying matrix multiplication:

  It is also an interesting question whether
  verification of matrix multiplication, i.e., checking whether AB = G for given C,
  could possibly be done faster.

  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of
  Computational Complexity

This has been since solved, and it is indeed possible to verify in $\mathcal O(n^2)$ time with a randomized algorithm (with $n\times n$ being the size of the input matrices, so it is basically linear-time in the size of the input). I wonder if it is possible to reduce integer multiplication to matrix multiplication, especially with their similarities, given Karatsuba integer multiplication's similarities to matrix multiplication algorithms that followed. Then perhaps in some way we can leverage the matrix multiplication verification algorithm for integer multiplication.

Anyway, since this is still, to my knowledge, an open problem, the stronger problem of $ad \overset ? < cd$ is surely open. I am curious if solving the equality verification problem would have any bearing on the comparison inequality verification problem.

A slight variation of our problem would be if the fractions are guaranteed to be reduced to lowest terms; in this case it is easy to tell if $\frac a b \overset ? = \frac c d$. Can this have any bearing on comparison verification for reduced fractions?

An even subtler question, what if we had a way to test $ad \overset ? < c$, would this extend to testing $ad \overset ? = c$? I don't see how you can use this "both ways" like we did for $ad \overset ? < cd$.

Related:

Approximate Recognition of Non-regular Languages by Finite Automata

They do some work on approximate multiplication, and randomized verification, which I do not fully understand.
math.SE: How to Compare two multiplications without multiplying?
Suppose we were allowed to preprocess $c$ as much as we wanted in polynomial time, can we solve $ab=c$ in linear time?
Is there a linear-time nondetermistic integer multiplication algorithm? See http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399

  There are well-known algorithms for multiplying n-bit numbers with
  something like O(n log(n) log(log(n))) complexity. And we can't do
  better than O(n) because at least we have to look at the entire
  inputs. My question is: can we actually reach O(n) for a suitable
  class of "nondeterministic" algorithms?

  More precisely, is there an algorithm that can accept two n-bit
  binary numbers "a" and "b" and a 2n-bit number "c" and tell you in
  O(n) time whether "a * b = c"? If not, is there some other form of
  certificate C(a,b,c) such that an algorithm can use it to test the
  product in linear time? If not linear time, is the problem of
  testing the product at least asymptotically easier than computing
  it? Any known results along these lines would be welcome.

  John.

  ―johnh4717


Uniform Hashing. Understanding space occupancy and choice of functions

Suppose that we sample a hash function $h$ at random from a collection $\mathcal{H}\subseteq [m]^U$ (we denote by $[m]$ the set $\{0,1,...,m-1\}$). The best possible thing we can require from this choice is that $\left(h(x_1),h(x_2),....,h(x_{|u|})\right)$ are jointly uniformly distributed over $[m]^U$, where $U=\{x_1,...,x_{|U|}\}$ (this in turn implies independence). Fix some $h_0\in [m]^U$, then under the previous requirement we have:
$\Pr\limits_{h\sim\mathcal{H}}[h=h_0]=\Pr\limits_{h\sim\mathcal{H}}\left[h(x_1)=h_0(x_1)\land...\land h(x_{|U|})=h_0(x_{|U|})\right]=\frac{1}{m^{|U|}}$.
It follows that $h$ is uniformly distributed over all possible functions in $[m]^U$ (in any other case we will fail either in uniformity or in independence). This is what is meant by "$h$ should be anyone of these functions".


Raft algorithm: What's the data format of `term`?

Note that we are focused on Raft algorithm.

What's the data format of term?
A term is just a positive integer.
Is it composed of Unix timestamp and length?
No, it is not. A term is just a positive integer. It is that pure and simple. In practice for reasons such as reporting or auditing, it might be helpful to record the time period when each term is valid. However, that is not an essential part of the algorithm at all.
How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).
Presumably, the question is seeking to confirm that terms can be maintained properly if term is based on time. However, as said above, this term can be considered as having nothing to do with time. So the best answer to this question should be that there is no need to be concerned with that kind of guarantee.

Here is a figure that shows how term is used in the logs in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable
Consensus Algorithm by the creators of Raft algorithm. Those numbers 1,1,1,2,3,3,3,3, etc in each log entry are the terms. Note that actual time is not mentioned anywhere in that figure, although a term does correspond to a limited continuous period of time.


Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

The Misra-Gries summary is a simple technique which will find, for a given $k$, all elements in a sequence of $n$ elements which occur more than $\lfloor n/k \rfloor$ times, introduced in the 1982 paper Finding Repeated Elements as a generalization of the more well-known Boyer-Moore majority vote algorithm, which is essentially the case where $k = 2$.

The Misra-Gries summary can be computed in $O(n\log k)$ time and $O(k)$ space with a single scan of the sequence. However, it always returns $k-1$ distinct values without any guarantee that any of them satisfy the criterion; it only guarantees that if a value satisfies the criterion, it will appear in the list. Reducing the summary to the required values requires a second scan of the sequence to count the occurrences of each candidate value. This scan can be performed in $O(n \log k)$ time by the simple expedient of putting the $k$ values into an associative array implemented with a balanced binary search tree, such as a red-black tree.

In fact, constructing the BST for the second scan is not really necessary because the $O(n \log k)$ Misra-Gries computation actually produces such a tree. The computation can be performed as follows:

Initialise an empty associative array $\mathit{C}$ which maps sequence elements onto non-negative integers. The array will have a fixed capacity of $k$ elements, but may contain empty slots.
For each element $a$ from the sequence in turn:

Precondition: $C$ contains at most $k-1$ pairs.
If $a\text{ is in }C$, increment its associated value.
Otherwise, add $\langle a, 1\rangle$ to $C$.
If $C$ now has $k$ pairs, decrement all of the associated values and remove all keys whose associated value is $0$. [Note 1]
Postcondition: $C$ contains at most $k-1$ pairs.

At the end of the scan, $C$ contains at most $k-1$ pairs with distinct keys, which include all elements which appear in the sequence more than $\lfloor n/k \rfloor$ times.

The proof of the postcondition is simple: If step 2 was performed, the size of $C$ was not changed, so it is still at most $k-1$ because of the precondition. Otherwise, step 3 is performed, after which $C$ contains at most $k$ because step 3 adds exactly one pair to $C$. If step 4 is performed, there must be at least one pair whose associated value is $0$ and will be deleted from $C$, because step 4 can only be performed if step 3 was performed and step 3 adds a pair with associated value $1$ to $C$.

The intuitive explanation of why any element repeated more than $\lfloor n/k \rfloor$ times must be in $C$ at the end of the scan is explained by @YuvalFilmus in this related question.

The fact that the scan takes $O(n \log k)$ time can be seen from a simple amortised time analysis of the iteration. Every element from the sequence will be added to $C$ exactly once, either in step 2 or step 3, each of which take $O(\log k)$ since $C$ has at most $k$ pairs. Furthermore, each element (except for the $k-1$ final candidates) will be decremented exactly once in some occurrence of step 4. (Step 4 decrements $k$ values, but each decrement pertains to a different element of the original sequence, so the total number of decrements is $O(n)$. Another way to look at this is to observe that step 4 can be performed no more than $\lfloor n / k\rfloor$ times.)

Each decrement in step 4 consumes $O(1)$ time, but at least one pair must be deleted from $C$, which requires $O(\log k)$ time. Again, we rely on amortised analysis to see that the total number of deletions is $O(n)$.

In practice, this algorthm will usually be implemented with a hash table rather than a balanced binary tree. The hash table implementation replaces the guaranteed $O(\log k)$ steps with expected $O(1)$ (but worst case $O(k)$). Since the worst case is extremely unlikely, the hash table algorithm is generally cited as linear-time, although strictly speaking it is linear expected time.

Notes

As an optimisation, it's possible (and, I believe, common) to avoid adding and removing $a$ in a single iteration. It is also unnecessary to remove pairs which have been decremented to 0 provided you can find such a pair in $O(1)$ for step 2. This can be done with a bit of bookkeeping. You can also implement "decrease all counts by one" by using a base value (so that the values are the stored value minus the base value) and incrementing it by one to effectively decrement all counts. All that will change the iteration step from amortized $O(1)$ to guaranteed $O(1)$ but the extra bookkeeping is likely to result in a slower total execution time.


I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as to why.

Conversion of a SAT Instance to a 3-SAT Instance:

For convenience, let us assume everything is in $\text{CNF}$, or conjunctive normal form. The $\text{SAT} \le_p \text{3SAT}$ proof works by introducing dummy variables to spread the actual variables over multiple clauses.

Illustration: Consider a single clause in boolean formula $(x_1 \lor x_2 \lor x_3 \lor x_4)$. The $\text{3SAT}$ reduction works by introducing a dummy variable to represent a disjunction of two literals in hopes that it reduces the clause's length by one. For example, $y = x_3\lor x_4$. The clause can be rewritten as:

$(x_1 \lor x_2 \lor y) \land (\bar y \lor x_3 \lor x_4)$

Notice that these clauses are now in a $\text{CNF}$ for $\text{3SAT}$. If this is repeated multiple times for each clause, the final $\text{CNF}$ formula will be at most polynomial in length of the original. This is why a polynomial time reduction would suffice.

Attempting to Apply the Method to Convert to 2-SAT:

If we tried to use the trick above with a clause of length 3, $(a\lor b\lor c)$, then we would not get the desired improvement. Let our dummy variable here be $y=b \lor c$.

The result: $(a \lor y) \land (\bar y \lor b \lor c)$

As you can see, it still has a clause of size 3. If we used the method again on the second clause, we would end up with the same problem while also adding an additional clause of length 2.

It could be said that the simplest reason for this is because $\land$ and $\lor$ are binary operators. You still need to apply these operators on pairs of variables, then include an additional dummy variable (resulting in a clause of length 3).

There have been attempts at getting around this that are successful, but the resulting sequence of clauses become exponential in length. Handling such a formula is outside the scope of $\text{P}$, which is why such a reduction would not be a polynomial time reduction.


Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case.  Suppose the tree is just a totally unbalanced path of right children; no node has a left child.  The only leaf in this tree is the tree with the maximum key.  If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting tree is still totally unbalanced.

Now suppose we repeatedly promote every node in the tree, one at a time, in decreasing key order, using the simpler algorithm.  After all the promotions are done, the tree has returned to its original state, and we have used roughly $n^2/2$ rotations.  Thus, on average, each promotion in this sequence requires $\Omega(n)$ rotations; moreover, I can repeat this pattern forever.  So the amortized cost for this promotion algorithm is $\Omega(n)$.

This bad example appears in Sleator and Tarjan's original splay tree paper.

The splay algorithm considers not just one node at a time, but two nodes at a time.  In particular, if the node $x$ being splayed is the right child of a right child, the splay algorithm first rotates $x$'s parent, and only then rotates $x$.

The advantage of this more complex algorithm is that it not only brings the accessed node to the root, but also moves every ancestor of the accessed node roughly halfway to the root, but never moves any node more than a constant number of levels away from the root.

Sleator and Tarjan prove that the amortized time per splay is only $O(\log n)$.  (The proof uses a tedious case analysis using a magic potential function; honestly, if you're curious, just read the original paper.)  Of course a single splay can take $\Omega(n)$ time, but starting with an empty tree, you have to perform a lot of insertions and splays to set up such a bad example.

More briefly: Splaying moves nodes upward quickly and downward slowly.


Proving a grammar only generates words whose alternating digit sums are multiples of three

Rough hint: play around with the many equivalent models you have for regular languages.

For 1), I find problematic that the contribution of an already generated digit changes as more symbols are added to the front. Things would be easier if the grammar was right-linear.

   Convert the given grammar to an NFA and convert that one to a grammar with the simple construction, which always yields right-linear grammars. (You should have proven algorithms for both.) Determinising/minimising the intermediate automaton might also help the proof.

Then, you have to figure out an induction hypothesis on sentences that works and implies the statement (for words), and perform induction over the whole set of sentences (by the length of the derivation).

   For example, if a non-terminal $C$ can only end the derivation by deriving a $1$, then for any sentence of the form $wC$, either $w$ has even length and its alternating digit sum plus one divides three, or it has odd length.

For 2), build an automaton that you can easily show generates all such words.

   For instance, use a counter construction, that is count the alternating digit sum modulo three in the states.

Now you can show equivalence of this automaton and the one derived from the grammar in 1).


If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

Your grammar only contains rules of the form $A \to a$, for $A \in N$ and $a \in T$. Therefore $L(G) = \{ \sigma \in T : S \to \sigma \in P \}$. You take it from here.


Removing epsilon transition from the grammar. What's the difference between accepting languages?

There is no difference. Both grammars describe the same language $$L = \{ \epsilon \} \cup \{ a^nba^n  | \forall n > 0\}.$$


Why any problem can be reduced to SAT is NP-Complete?

Indeed that is incorrect. All problems in $\mathbf{P}$ are reducible to SAT. In fact, even trivial problems (e.g., finite languages) are reducible to SAT.

What is probably meant is that, if a problem in $\mathbf{NP}$ is such that SAT is reducible to it, then it is $\mathbf{NP}$-complete.


How can I debug my pseudocode algorithm?

This is an excellent question: how do we know that a complex piece of mathematics is correct? The (by now) traditional point of view is that if we succeed in proving something then it must be correct. Unfortunately, this point of view is a tad naive. Indeed, published papers often contain wrong results, and these can remain unnoticed for decades. Some high-brow examples can be found in Voevodsky's talk, and this is a notorious issue especially in cryptography and distributed computing, two fields with extremely complicated definitions and proofs.

The most stunning example, however, must be the gap in the proof of the classification of finite simple groups: the result was announced in 1983, but only in 2004 did Aschbacher and Smith publish two monographs (!) covering one of the cases. In 2008 a further gap was filled by Harada and Solomon who found, quoting Wikipedia, "a case that was accidentally omitted". Should we believe the proof now, then?

Another problem which has seen its share of wrong proofs is the four color theorem. The first two proofs, dating to 1879 (Kempe) and 1880 (Tait), were found wrong in 1890 and 1891, respectively. In 1977 Appel and Haken announced a solution, containing a very length case analysis. It was not surprising, then, that a small error was found around 1986. While the error was corrected, doubts remained. The matter was finally put to rest in in the computerized formal proof by Gonthier et al. (2005), formalizing the earlier "second generation" proof of Robertson, Sanders, Seymour and Thomas from 1996.

What is a computerized formal proof? The idea is that if you had a completely formal proof of each and every statement, then as long as we trust our proof system, then we can be sure that the result is correct. (Unfortunately, as Gödel showed there is no hope in showing that the proof system is consistent, so this is an article of faith.) As Russell and Whitehead exemplified in their Principia Mathematica, writing formal proofs is difficult. Instead, the idea is to use a proof assistant which gets hints and converts them, somehow, to a formal proof which can then be independently checked. There are several of these proof systems around, but the most popular nowadays seems to be Coq.

What if the reviewers don't believe your proof? This is the situation that Thomas Hales found himself in after proving (or so he claims) the Kepler conjecture on sphere packing. The reviewers gave up after spending a year of reviewing, saying that while they were unable to find any mistake, they are not completely certain that the proof is correct. In response, Hales decided to formalize his proof, starting up the Flyspeck project, now in its eleventh year. In a few more years the proof would probably be complete. Clearly this amount of effort is unreasonable for the everyday mathematician.

Can proof assistants be improved? Voevodsky has been developing Homotopy Type Theory, a Coq overlay for algebraic geometry, and claims that he is using it daily to verify his proofs. Last year Gonthier et al. formalized the proof of the Feit–Thompson theorem in group theory in Coq, thus laying the ground for formalized group theory results. Yet even these projects are missing a lot of background which will be needed to formalize research in theoretical computer science. Even after such a framework has been developed, it will still be rather time-consuming to turn the commonplace sloppy TCS proofs into formal attire.

So what are you to do? In your particular case, you are designing an algorithm, so you have the distinct advantage of being able to test your algorithm. (The Curry–Howard correspondence shows that every proof corresponds to an algorithm, but in your case the relation is clearer.) Perhaps there is a trivial algorithm which is very slow, and you could compare it to your algorithm. Or perhaps it is an NP-type problem, in which the solution is easy to verify but hard to find.

Do people actually verify their algorithms usually? I doubt it, unless they are in a field such as computational geometry in which their algorithms are actually being used. What people usually do is do their best to check their proofs, crossing all ts and dotting all is. That means avoiding phrases such as it is easy to see that. Having done that, they kindly ask a few other people to read through their proofs. Then they submit the paper to a journal, and if they're lucky then the referees will do another pass.

Even after all this, mistakes are occasionally found, but this is just part of life. Usually, these mistakes can be corrected easily, demonstrating that our formal sense of certainty is limited: true mathematics "works" even if not completely valid formally, as has been argued by a few philosophers, most of them coming from the ranks of practicing mathematicians. Wrong algorithms point the way to correct algorithms, as they bring new ideas. So don't worry too much, just do your best.


How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

Let $\sigma$ be the substitution $\sigma(a) = \sigma(b) = \sigma(c) = \{a,b,c\}$, and let $h$ be the homomorphism $h(\sigma) = \sigma\sigma$.

Your language is just
$$
h^{-1}(\sigma(G)) \cap L.
$$
In other words, your language is regular.

You can also see this using a product automaton. Given automata for $L,G$, consider an NFA on $Q_L \times Q_G$, with starting state $(q_{0L},q_{0G})$, accepting states $F_L \times F_G$, and transition function
$$
\delta((q_L,q_G),\sigma) = \{ (\delta_L(q_L,\sigma),\delta_G(q_G,\sigma \tau)) : \tau \in \Sigma \}.
$$


Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

One way to solve this problem is by showing there do not exist Turing machines that accept  $L_3$ or $\overline L$. But probably that is simply restating the question.

$L_u$, the universal language, is non-recursive but RE language. If we reduce $L_u \leq_M L$ then $L$ cannot be co-RE. If we reduce $L_u \leq_M \overline{L}$ then $L$ cannot be RE.

Let us  first do the reduction $L_u \leq_M L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows:
$M'$ rejects all inputs other than $w$. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M' = f(\langle M,w\rangle) \in L$.

Hence $L_u \leq_M L$. Therefore $L$ cannot be co-RE. Otherwise $L_u$ will become recursive.

Next we do the reduction $L_u \leq_M \overline L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M''$ as follows: Let $w'$ be a string other than $w$.
$M''$ rejects all inputs other than $w$ and $w'$. If the input in $w'$ then $M''$ accepts the input. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M''= f(\langle M,w\rangle) \not\in L$, that is, $\langle M,w\rangle \in L_u$ iff $M'' \in \overline L$.

Hence $L_u \leq_M \overline{L}$. Therefore $L$ cannot be RE. Otherwise $L_u$ will become recursive.

If we combine the results, $L$ is neither RE nor co-RE.


Is $\Omega^\infty (g(n)$ a more general version of $\Omega(g(n))$?

The phrase "for infinitely many integers" means "for an infinite set of integers". This strange definition is what you get when you negate little $o$. That is, for any two functions $f,g \geq 0$, either $f = o(g)$ or $f = \Omega^\infty(g)$. In some cases $f = \Omega^\infty(g)$ is enough to derive certain consequences, and so is a useful property.


How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?

For pumping lemma proofs, we have to remember that only strings longer than the pumping length are guaranteed to be "pumpable" (if the language is regular). Unfortunately we don't (typically) know what the pumping length is, so we have to work a little more abstractly than picking a fixed length string.

In this case, given pumping length $p$, we can take the string $s=0^{3p}1^{p}\in L$ (i.e. we choose the string where $n=p$ and $m=3n=3p$). Now if $L$ were regular, we'd be able to divide $s$ up into three parts $s=xyz$ where:

$|xy|\leq p$
$|y| > 0$
$xyz \in L \Leftrightarrow xy^{i}z\in L $ for all $i\in\mathbb{N}$

So with our $s$, we know that $y$ must be a string of $0$'s, as $y$ is non-empty and is a subtring of the first $p$ characters.

Then if we pump up (never forget that pumping down is also a possibility - consider $0^{2p}1^{p}$) we get the string $s'=0^{3p+|y|}1^{p}$. As $|y|>0$, clearly $s' \notin L$, which contradicts the pumping lemma, therefore $L$ cannot be regular.


Is binary-search really required in Chan's convex hull algorithm?

I think this is correct... see 2. Chan’s Algorithm p4, Remark.

  Remark. Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, this is irrelevant as far as the asymptotic runtime is concerned, given that already the divide step takes $O(n \log H)$ time.

Anyway, the complexity is bounded by the divide phase.


Program interpretation for static analysis

It's been hinted at in the comments, but in general, the task of giving non trivial explanations of an arbitrary piece of code by some automated analysis is impossible.

The first issue is giving a well-defined meaning to the term "program intent". The field of operational semantics can give us a precise definition of what a piece of code actually does when run on a concrete computer, under the hypothesis that the compiler or interpreter is free of programing errors, but the intent of the person who wrote the code can obviously not be divined from the code itself, e.g. a piece of code may be intended to say, crash if given a negative number as input, or that outcome may be the result of programmer oversight.

However it might be desirable to, say, infer various mathematical properties of an arbitrary piece of code, in your example you might want to infer

forall x, if x > 0 then SQRT(x)*SQRT(x) == x

This also is impossible to do in general. This somewhat surprising fact can be demonstrated using Rice's theorem, which essentially says that any property like the above statement can not be proven or refuted automatically for arbitrary programs.

That being said, there has been a substantial body of work which aims at identifying and proving properties such as the above for concrete program implementations. Because of Rice's theorem, such attempts must be incomplete, but in practice much can be done for "real world" programs. This field is usually designated under the term formal methods, and even a short summary would be significantly more effort than I'm ready to put forward right now. A good overview can be found here.


Learning a specific functional form with machine learning

Yup.  You define two neural nets (or other models) $f,g$ with weights $\theta,\psi$, define

$$o_{\theta,\psi}(x,y,z) = f_\theta(x) g_\psi(y) g_\psi(z),$$

define a loss function (which compares the predicted output $o_{\theta,\psi}(x,y,z)$ to the desired output), and then use stochastic gradient descent to find weights $\theta,\psi$ that minimize the aggregate loss on the training set.


Recursive algorithm to compute a sum of product like function

Assuming we are given the $x_{ij}$'s and $i,j,m$, your formula already is a recursive algorithm to compute $F_{i,j}(m)$.  If you use dynamic programming (memoization) to avoid re-computing $F_{i',j'}(m')$ more than once for any given tuple $(i',j',m')$, the running time will be $O(m^3)$, since you only evaluate $F_{i',j'}(m')$ for tuples $(i',j',m')$ where $0 \le i',j',m' \le m$.

If the $x_{ij}$'s are not given, your question is not well-defined.  If that's what you meant, it's possible you might be asking for us to compute the distribution of $F_{i,j}(m)$, but if so, the question needs to be edited accordingly.

Either way, I suspect that there must be some additional base cases you have not provided.  As it currently stands, the solution $F_{i,j}(m)=0$ for all $i,j,m$ satisfies your equation.  I suggest you edit your question to specify the missing base cases.


How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages

Just to clear something up that may not have been obvious, $\chi$ is a set and the notation $B[\chi, x]$ is meant to be ABTs under free variables that are either $x$ or are in $\chi$. In this notation I believe it is implied that $x \notin \chi$ when you write $B[\chi, x]$, which is important.

Using the definition of ABT above, you cannot prove for any $\chi$ that let(z, x.x) is in $B[\chi,x]$, but i claim that this is necessary to prove if you want to use it as the inner formula $a_1$ in let(y, x.$a_1$).

The reason you cannot prove let(z, x.x) is in $B[\chi,x]$ is because using the rule#1 stated above, the free variable $x$ is only an ABT in $B[\chi]$ when $x \in \chi$ (or alternatively: $x$ is only an ABT in $B[\chi',x]$ for some $\chi'$), but then using rule#2, we deduce $z \in B[\chi] \wedge x \in B[\chi, x] \rightarrow let[z,x.x] \in B[\chi]$. As I had mentioned in the first paragraph, this implies $x \notin \chi$, which means that the formula let(z, x.x) is ONLY in ABTs where $x$ is not a free variable.

The reason why $x$ needs to be free in this inner formula is because otherwise we cant apply rule#2 again on the outer formula let(y, x.$a_1$).


Basic question about branches and pipelines

The classic RISC pipeline resolves branches in the decode stage, which means the branch resolution recurrence is two cycles long. More information can be found in the Wikipedia article on the Classic RISC pipeline.


What is the algorithm for a decider to get the language accepted by a DFA?

Suppose that $A,B$ are two DFAs on a common alphabet $\Sigma$ with states $Q_A,Q_B$, initial states $q_{0A},q_{0B}$, final states $F_A,F_B$, and transition functions $\delta_A,\delta_B$. We define a product DFA as follows:

$Q = Q_A \times Q_B$.
$q_0 = \langle q_{0A}, q_{0B} \rangle$.
$F$ consists of all pairs $(q_A,q_B)$ such that either $q_A \in F_A$ and $q_B \notin F_B$ or $q_A \notin F_A$ and $q_B \in F_B$.
$\delta(\langle q_A,q_B \rangle, \sigma) = \langle \delta_A(q_A, \sigma), \delta_B(q_B, \sigma) \rangle$.

You can prove by induction that $\delta(q_0, w) = \langle \delta_A(q_{0A}, w), \delta_B(q_{0B}, w) \rangle$, and so our definition of $F$ guarantees that the language of this DFA is the symmetric difference of $L(A)$ and $L(B)$.

In order to know whether $L(A) = L(B)$, we have to check whether their symmetric difference is empty. This happens exactly when no accepting state is reachable from the initial state in the product DFA, a condition which we can check using BFS/DFS.


Lower the frechet distance between two curves

Raichel and Har-Peled wrote a paper, The Frechet Distance Revisited and Extended, which explains how to compute various curves.
This might implicitly give you the answer.


Deleting useless (dead) states from a finite automaton

Reverse all edges in the graph, and add a new state pointing at all accepting states. Find the set of states reachable from the new state in linear time (using BFS/DFS). These are the useful states (according to your definition).

The running time of this algorithm is linear in the number of states plus number of transitions.  This is about the best you can hope for (in terms of asymptotic worst-case running time).


In your construction you correctly computed the closures of the original states and then made the $a$- and $b$-transitions, but you omitted step (3) of the algorithm: compute the closures of the results again. For example, from $q_0$ on input of $a$ the first step is
$$
q_0\stackrel{CL}{\longrightarrow} \{q_0, q_1, q_2\}
$$
then, on seeing an $a$ we make the transitions, as you did:
$$
\{q_0, q_1, q_2\}\stackrel{a}{\longrightarrow} \{\delta(q_0, a), \delta(q_1, a), \delta(q_2, a)\}=\{q_3, q_4\}
$$
then (here's the step you omitted), you take the closure again:
$$
\{q_3, q_4\}\stackrel{CL}{\longrightarrow} \{q_2, q_3, q_4\}
$$
and thus you'll have the new transition $\delta'(q_0, a) = \{q_2, q_3, q_4\}$.

If you do this for all the state-symbol pairs, you'll find that the transitions of your new NFA are
$$\begin{array}{c|cc}
 & a & b\\ \hline
q_0 & \{q_2, q_3, q_4\} & \{q_2, q_3\} \\
q_1 & \{q_2, q_3, q_4\} & \varnothing \\
q_2 & \{q_4\} & \varnothing \\
q_3 & \{q_4\} & \{q_5\} \\
q_4 & \{q_5\} & \{q_2, q_3\} \\
q_5 & \varnothing & \varnothing \\
\end{array}$$
Since $q_1$ is an unreachable state, it can be eliminated without changing the langauge of the resulting NFA.


For full detail, you should consult a textbook on operating systems.

The brief answer is that the operating system doesn't need to be executing all the time. It suffices for it to periodically regain control of the machine, and this happens through so-called "interrupts".  Interrupts can happen for a number of reasons:

a process that wants the operating system to do something for it (e.g., to perform I/O) can raise an interrupt (known as a "system call");
a hardware device that needs attention (e.g., because some I/O that was requested has now completed) alerts the OS by raising an interrupt;
the system clock will raise interrupts at some frequency (typically multiple times per second).


Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations

I suggest taking a look at the edit distance algorithm.  Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.


Contradiction proof for inequality of P and NP?

Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$.

Sure.

  As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the  exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L \in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.


How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

The probability that a specific set of size $k$ is a stable set is $2^{-\binom{k}{2}}$. Hence the probability that some set of size $k \leq n/2$ is stable is at most
$$
\binom{n}{k} 2^{-\binom{k}{2}} \leq 2\left(\frac{en}{k}\right)^k 2^{-k^2/2}.
$$
When $k = c\log n$ (logarithm to the base 2), this upper bound is
$$
2\left(\frac{en}{C\log n}\right)^{C\log n} 2^{-C^2\log^2 n/2}=
\frac{2^{(C-C^2/2)\log^2n}}{\Omega(\log n)^{\Omega(\log n)}} = o(2^{(C-C^2/2)\log^2n}).
$$
For $C \geq 2$, this is $o(1)$.


Relation between type-checking decidability, typability decidability and strong normalization

I'll give a more focused and technical answer to Martin's. If we're interested in dependent type theories, then neither direction is obvious, but both are generally assumed to hold. However the direction Decidable $\Rightarrow$ Normalizing is open, I believe, even for relatively well understood systems, though we do have partial results. This question explores some of the same issues.

More technically: a good technical framework for these questions is the setting of Pure Type Systems in which normalization does imply decidability of type checking. The result is folklore, but non-trivial, since a strategy for when to apply the conversion rule needs to be found. The obvious strategy is to normalize inferred types before all applications of the application rule. There are some subtleties even here, where the correctness of a natural (more efficient) strategy called expansion postponment was open for a while, but has been settled since.

There are type systems which are normalizing but undecidable, most notably the system with intersection types which types exactly the normalizing terms, and so must be undecidable (since otherwise it could be used to identify normalizing terms). It would be tempting to say here that the system is defective in the sense that it is not type directed, i.e. the terms do not contain enough information to figure out the type.

Now the converse, which would suggest non-normalizing systems are undecidable, is far from obvious: it was even open for a while for the famous $Type:Type$ system of Martin-Löf! This case was solved by giving an example of a looping combinator, which allows writing arbitrary computations.

However the general problem is still open for general pure type systems, though it is widely believed to be true, and some partial results have been shown in this direction, e.g. here.


Using Limits to Determine Asymptotic Relationship

Knowing $3^4=81$ and $4^3=64$, we have $f(n)=81^n$ and $g(n)=64^n$. Using this we obtain:
$$\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=\lim\limits_{n \to \infty}\left(\frac{81}{64}\right)^n=+\infty$$
so you have your "Note 2". By definition last limit mean $\forall C>0$ we have  $\exists N \in \mathbb{N}$, such that $\forall n>N$ holds $\frac{f(n)}{g(n)} \geqslant C$ so we have $f\in \Omega(g)$.
For further let's assume, that we have positive functions and $g$ have not $0$s subsequence.
Following question. Your "note 1" means that $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}$ is not $0$ and is not $\infty$, but equals to some number between them.
And last. Suppose $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=A>0$. This means, that $A-\varepsilon<\frac{f(n)}{g(n)} < A+\varepsilon$, for appropriate $n$, and so we can conclude $f \in \Theta(g)$.


You can prove by induction that for all $n\in\mathbb{N}$, $A$ and $B$ agree on all the strings in $\{0,1\}^{\le n}$, i.e. $A\cap\{0,1\}^{\le n}=B\cap\{0,1\}^{\le n}$.

The case of $n=0$ follows from the fact that $M$ does not query its oracle on the input $\epsilon$, which means $M^A$ accepts $\epsilon$ iff $M^B$ accepts it. For $n>0$, let $x\in\{0,1\}^{n+1}$ be some length $n+1$ string. We need to prove (under the inductive hypothesis) that $x\in A\iff x\in B$. Suppose $x\in A$, then $M^A$ accepts $x$. Note that on input $x$, $M^A$ queries strings in $\{0,1\}^{\le n}$ alone, where $A$ and $B$ agree. This means that replacing the oracle from $A$ to $B$ won't change $M$'s outcome on $x$, hence $M^B$ accepts $x$ and therefore $x\in B$, since $B=L(M^B)$. The same arguments apply in the $x\notin A$ case, which concludes the proof.


Shifting and adding to get multiplication values?

Shifting left is the same as multiply by two.
Take number, say in your example 33, convert to binary, 100001, here 1<< 6 is the leftmost bit and 1 is rightmost bit. As you have noticed it is $2^0$.

Second example is handled manually, it is 10000000000111111, so at first you set leftmost bit, then notice that consecutive ones could be converted to 1000000 - 1.

Standard usage is to speed up multiplication by constant, so you precompute it and use in your code. It makes sense until additions, subtractions and bit shifts are cheaper on target machine than one vanilla multiplication.
Some bit twidlings are already present in compilers, other may break compilers ability to optimise more.

Such operation is good in static, compiled languages, like C. It may work on managed ones (with platform independent emulation of arithmetic operations), but makes little sense on interpreted languages like Python (unless you compile it).


This is actually kind of complicated. Basically you can:

Decompose a huge multi-qubit operation into many single-qubit gates, but with lots of controls allowed on each single-qubit gate. Think of it as doing Gaussian elimination: you're factoring the matrix into a bunch of simple row operations.
Gradually reduce the number of controls to at-most-one-per-gate, by repeatedly using a construction based on the fact that every operation has a square root and an inverse.
Factor each single-qubit operation $U$ into $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$. Use that to replace controlled-$U$ gates with uncontrolled single-qubit operations separated by $CNOT$ gates.
Approximate each uncontrolled single-qubit operation with a sequence of $H$ and $T$ gates (which is possible because they correspond to rotations that can approximate any other rotation).

What you're left with is a circuit containing only $CNOT$, $H$, and $T$ gates that approximates the original operation. You need more gates to get a better approximation, but you can get as close as desired. Also the overhead isn't too terrible.

For details of the constructions, and proofs that the errors don't compound in a way that destroys the efficiency of the approximation, you'll probably have to get a textbook or read papers. There's a lot of details.


Since your heap contains $d$ elements, every operation takes take $O(\log d)$, for a total running time of $O(n\log d)$.
When $d$ is constant, this is $O(n)$, and when $d = O(\log n)$, this is $O(n\log\log n)$.
For a matching $\Omega(n\log d)$ lower bound, see this question.


Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

For $i \ge 0$ define $w_i = b^i aa$.
For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed, $w_i b^i \not\in L_2$ but $w_jb^i \in L_2$.
Then the number of equivalence classes of the set $\{ w_i \mid i \ge 0\}$ with respect to the equivalence relation "having a distinguishing extension" is not finite and, by the Myhill-Nerode theorem, $L_2$ is not regular.

Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.
Suppose that $L_2$ is regular. Then so is $L' = \overline{L}_2 \cap \{b^i aa b^j\} = \{b^i aa b^i\}$, which is easily shown to be non-regular using the pumping lemma.
Indeed, suppose that $L'$ was regular, and let $p$ be its pumping length. For some $k \in \{1, \dots, p\}$, the word $b^p aa b^p \in L'$ can be written as $b^k b^{p-k} aa b^p$ such that $b^{ki} b^{p-k} aa b^p \in L'$ for every $i \ge 0$. Nevertheless, for $i=0$ we have $b^{p-k} aa b^p \not\in L'$, yielding a contradiction.


Algorithms for two and three dimensional Knapsack

Knapsack can be solved by dynamic programming in pseudo-polynomial time $O(nW)$ with $n$ the number of objects and $W$ the size of the knapsack. So, as long as your container is small (numerically), you can solve the problem efficiently. Note that you can adjust $W$ by changing resolution; no need to measure a shipping container to the µm, but meters are probably to coarse (depending on your objects).

Knapsack can also be approximated arbitrarily well in polynomial time (see polynomial-time approximation schemes).

However, Knapsack only considers fitting numbers into another number; it does not care about geometrics. If you need to "puzzle", you need another problem; considering Tetris, this is probably much harder than Knapsack.


Since you have a 1-1 relationship between DisasterEvent and People now, you can not distinguish any relation between People and Place. If several Places are related to a single DisasterEvent, all those places are related to the same instance of People.

If you want to map the People affected by the Event at a Place, you should relate People to Place instead of to DisasterEvent.

As long as an event always occurs at at least one place, you can always relate your People to your DisasterEvent via the Place where it occurred.

On a sidenote, I would use Location instead of Place, and maybe the more precise Victims for People, as well as maybe Damage for Home.


What is the difference between cyber security ontologies and scenario ontologies in this system?

Some more detail can be found p97. Here "ontologies" are basically encodings of database contents (which represent cyber attacks, incidents, and malicious/ impacted software programs) parseable by external sources, e.g. ACT-R. The event data management system keeps track of (real) attacks/ incidents, or possibly simulated ones. TENA is a Testing and Training Enabling Architecture. In a sense the Cyber Security Ontologies are all the "Nouns", and the Scenario Ontologies are "Verbs" that operate on the Nouns. ACT-R takes these inputs and attempts to create a conceptual linking or model. In a sense the ACT-R is a machine learning system for cyber-attack-related events and entities. It is a framework for outputting a (maybe statistical) analysis that could be used to predict future attacks from the structure of past ones.

  The need for controlled vocabularies, taxonomies, and
  ontologies to make progress toward a science of cyber security
  is recognized in [26] and [27] as well. In the domain of cyber
  security, the ontologies would include, among other things,
  the classification of cyber attacks, cyber incidents, and
  malicious and impacted software programs. From our point of
  view, which seeks to accurately represent the human-side of
  cyber security, we also expand our analysis to: (i) the different
  roles that system users, defenders and policy makers play in
  the context of cyber security; (ii) the different jobs and
  functions that the members of cyber defender team play and
  the knowledge, skills and abilities needed to fulfill these
  functions. In order to reduce the level of effort, we will reuse
  existing ontologies when possible6 and only create new
  ontologies that support the use cases we select.


Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?

Yes, I believe there is (though I don't remember the details of the paper to confirm).

This is the original paper which dealt with that:

  Nievergelt J. and Reingold E.M., "Binary search trees of bounded
  balance", Proceedings of the fourth annual ACM symposium on Theory of
  computing, pp 137--142, 1972

Here is a page on weight-balanced trees which seems to have some more information and mentions their usage in functional languages.

This paper: On Average number of rebalanced operations in weight balanced trees, seems to be investigating the number of rebalancing operations in weight balanced trees.

I also seem to remember that one Knuth's Art of ... books had a reference to the above Reingold paper (perhaps in the exercises).


What are the criticisms regarding the performance of HTM?

Criticisms against Jeff Hawkins are well summarized in the following essay taken from
http://www.theregister.co.uk/2014/03/29/hawkins_ai_feature/

I myself believe that the HTM theory has a huge potential and will be a foundation of true machine intelligence. IBM recently announced to back up the HTM theory and started the Cortical Learning Center including some hundred members.

http://www.technologyreview.com/news/536326/ibm-tests-mobile-computing-pioneers-controversial-brain-algorithms/

As is pointed out in the essay, Dillep George, a cofounder of Numenta, made the startup Vicarious, which attracted a huge amount of fund, of which fact suggests a potential of the HTM theory.

  Source: Criticisms against Jeff Hawkins, The Register

  His media-savvy, confident approach appears to have stirred up some
  ill feeling among other academics who point out, correctly, that
  Hawkins hasn't published widely, nor has he invented many ideas on his
  own.

  Numenta has also had troubles, partly due to Hawkins' idiosyncratic
  view on how the brain works.

  In 2010, for example, Numenta cofounder Dileep George left to found
  his own company, Vicarious, to pick some of the more low-hanging fruit
  in the promising field of AI. From what we understand, this amicable
  separation stemmed from a difference of opinion between George and
  Hawkins, as George tended towards a more mathematical approach, and
  Hawkins to a more biological one.

  Hawkins has also come in for a bit of a drubbing from the
  intelligentsia, with NYU psychology professor Gary Marcus dismissing
  Numenta's approach in a New Yorker article headlined Steamrolled by
  Big Data.

  Other academics El Reg interviewed for this article did not want to be
  quoted, as they felt Hawkins' lack of peer-reviewed papers combined
  with his entrepreneurial persona reduced the credibility of his entire
  approach.

  Hawkins brushes off these criticisms and believes they come down to a
  difference of opinion between him and the AI intelligentsia.

  "These are complex biological systems that were not designed by
  mathematical principles [that are] very difficult to formalize
  completely," he told us.


Real-valued genetic algorithm offspring out-of-bounds

Anything is acceptable.  These are all heuristics; all that matters is results (i.e., whether it helps you find a good solution to the problem, and how quickly it does so).

One standard method is to "clip" all values to be within the bounds.  In other words, if the value is smaller than 0, you replace it with 0; if it is larger than 10, you replace it with 10.  This ensures that the value will be within bounds.

There are other methods as well.  For instance, you could let $y = 10 \sigma(x)$ where $\sigma(x) = 1/(1+e^{-x})$.  You apply genetic programming to the values $x$ (so you do mutation and crossover operations on the $x$ values), but then you calculate $y$ and use that as the actual output.  Note that $x$ can be any real number ($-\infty < x < \infty$) and the definition of $y$ will ensure that $0 \le y \le 10$.


Creating a list of minimum-distance pairs from two lists

This seems to be a classical example of bipartite weighted maximum matching, for which there are efficient algorithms (you'll have to convert your minimization objective to a maximization one).


The purpose of grey node in graph depth-first search

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to explicitly make these distinctions for better understanding.

Of course, there are actual uses of these colors. Consider a directed graph $G$. Suppose you want to check $G$ for the existence of cycles. In an undirected graph, if the node under consideration has a black or grey neighbor, it indicates a cycle (and the DFS does not visit it as you mention). However, in case of a directed graph, a black neighbor does not mean a cycle. For example, consider a graph with 3 vertices - $A, B,$ and $C$, with directed edges as $A \to B$, $B \to C$, $A \to C$. Suppose the DFS starts at $A$, then visits $B$, then $C$. When it has returned to $A$, it then checks that $C$ has already been visited and is black. But there is no cycle in the graph.

In a directed graph, a cycle is present if and only if a node is seen again before all its descendants have been visited. In other words, if a node has a neighbor which is grey, then there is a cycle (and not when the neighbor is black). A grey node means we are currently exploring its descendants - and if one such descendant has an edge to this grey node, then there is a cycle. So, for cycle detection in directed graphs, you need to have 3 colors. There could be other examples too, but you should get the idea.


Scheduling N variable-time interdependent tasks across M workers

This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation of the assignment problem (find the optimal pairing of workers to jobs that minimizes cost). The variation in both cases is an added dependency between jobs (Job A must complete before Job C) etc. This collection of combinatorial optimization problems is NP-Hard. Most of what you'd find in the literature is approximation heuristics to find a near optimal policy (sequence of tasks per worker).

This paper is one such approach: "Approximation Algorithms for Multiprocessor Scheduling under Uncertainty"

A quick way to solve your problem (quick as in prototype a solution, not necessarily runtime, or necessarily near optimal), is to construct a topological sort of your job dependency graph, use breadth first search to batch all jobs of a given height and put that batch on a stack (assumes directed edge represents a depends on relationship, with zero out degree nodes having no dependencies). Afterwards, Until the stack is empty, pop a batch and treat it as a traditional assignment problem and solve using the Hungarian algorithm, then enqueue the tasks to each assigned worker's task queue. Afterwards you'd have a policy. (When you go to execute the policy, you'd have to have some signalling mechanism that a task completed so that workers don't start on a task whose dependencies haven't finished yet.)


Is every decidable language a deterministic context free language?

You are asking several disparate questions:

Is every decidable language a deterministic context-free language? No. There are even context-free languages which are not deterministic context-free. Furthermore, membership in a context-free language (deterministic or not) can be decided in polynomial time, whereas the time hierarchy theorem shows that there are languages decidable in time $O(n^{\log n})$ (say) but not in time $O(n^{\log\log n})$, and in particular not in polynomial time.
Are there any decidable languages that are not recognizable? A language is decidable iff both the language and its complement are recognizable.
Is the question "Does a given PDA accept a given input?" decidable? Yes, though the algorithm isn't obvious. One way is to convert the PDA to an equivalent context-free grammar in Chomsky normal form, and then use the CYK algorithm.
Under what operations are decidable languages not closed? Decidable languages are not closed under taking prefixes. The language of pairs $M,n$ such that $M$ halts within $n$ steps is decidable. But the language of all prefixes ending with $,$ is the halting problem, which is not decidable. (I'm skipping a few steps here.)


What is "potential speedup" in parallel computing?

Potential speedup $\equiv$ number of processors.  I agree that it is poorly chosen wording.  A better term would be efficiency (the average amount of time that the processors are doing useful work.)


Is the inverse of MST cut property true? Why?

This is not the case.
If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ must be included (there is some other cut in which $e$ is the only - and therefore the lighest - edge).


Arbitrary Turing machine run time analysis on the empty word

The $\log T(n)$ factor in the analysis stems from the need to keep (and update) a step counter, in binary, that goes up to $T(n)$. This requires $\log(T(n))$ cells, and the need to update it (or rather, to drag it along on the tape) costs $\log(T(n))$ in every iteration.

Now, if you could avoid this for $\epsilon$, then you could avoid it for an arbitrary input word $w$, by modifying the given TM $M$ to a new TM $M'$ that first writes $w$ on the tape, and then simulates $M'$ for $T(n)+|w|$ steps on $\epsilon$.

Since $T(n)$ is super-linear, this would contradict the best known lower bounds.

Note that this does not prove that a better simulation is not possible, only that the word $\epsilon$ plays no special role.

In fact, however, you could prove that $o(T(n))$ is not achievable, by tweaking slightly the Time Hierarchy Theorem


What purpose was the Von Neumann machine intended for? And what hardware limitations existed when von Neumann invented it?

The von Neumann architecture was built for sequential computing. It was groundbreaking because it combined the instructions in memory along with the data for the instructions in the same space. Before this, programming required rewiring because each machine was built with a specific purpose in mind.

The essential idea is abstraction on some level. The people who design the actual machines don't need to concern themselves with what software will be written for the machine. Rather, they make a few basic commands extremely efficient. The software teams then efficiently use these commands, allowing a generalizable/abstractable computer model.


The +1 is for the newline character.

The byte count equals the number of characters, in this case, because each character takes exactly one byte.  That need not be true in general (see, e.g., UTF-8), but it is for the example you listed.

You didn't write an integer to the file.  You wrote a string -- a sequence of characters, namely the character 1, then the character 2, then 3, then 4, then a newline.  Files don't store integers or other types.  They store a sequence of bytes.  Each character is converted to one or more bytes using an encoding, and then the sequence of bytes is written.


Is there a name for this traversal-optimized representation of a binary tree data structure?

This representation is known as a "zipper" and is described by Gérard Huet in his paper "The Zipper":

  The basic idea is simple: the tree is turned inside-out like a returned glove,
  pointers from the root to the current position being reversed in a path structure. The current location holds both the downward current subtree and the upward path. All navigation and modification primitives operate on the location structure. Going up and down in the structure is analogous to closing and opening a zipper in a piece of clothing, whence the name.


What does "Kan" mean in "Kan operations"?

Kan operations are likely named after Daniel M. Kan, in analogy to concepts such as Kan extensions, Kan complexes, Kan fibrations, Kan condition, and many more. Kan also introduced adjoint functors.


Recursive language subtracted from recursively enumerable language

The language that contains all input strings is recursive. Just create a Turing machine that always outputs true. So take that to be $L_2$. $L_1 - L_2$ would be the empty no matter what $L_1$ is. The empty language is also recursive. So now we have an example of a recursive language arising from $L_1 - L_2$.

The language that contains no input strings (the empty language) is recursive. Just create a Turing machine that always outputs false. So take that to be $L_2$. Now $L_1 - L_2 = L_1$ which is not recursive.

So $L_1 - L_2$ may or may not be recursive.

Now we are left with b) and c). To decide between these we can note that the language is always recursively enumerable.
Proof:

Iterate outputs from $L_1$ but only output them if they are not contained in $L_2$ (check by a Turing machine which always terminates). We now have a Turing machine that outputs all elements of $L_1 - L_2$.

So $L_1 - L_2$ is always recursively enumerable.


Shortest travelling cost if we have bunch of points in 2D plane

This is the Traveling Salesman Problem with the $L_1$ metric (also known as the Manhattan distance).

Unfortunately, this version of the TSP is also NP-hard.  Therefore, there is no algorithm that always produces the optimal solution, is efficient, and works for all inputs.  Instead, you'll have to use a heuristic or approximation, or accept a solution that can take exponential time in the worst case.  Dijkstra's algorithm won't suffice.

Strictly speaking, the standard formulation of the TSP doesn't allow you to visit any point more than once.  However, in this situation allowing you to visit a point more than once doesn't make the problem any easier, since visiting a point more than once will never help you find a shorter solution.

Perhaps the following paper will be useful:

The L1 Traveling Salesman Problem.  Donald C.S. Allison, M.T. Noga, Information Processing Letters, vol 18, 1984, pp.195-199.


Yes, any constant is a polynomial of degree zero.


Can the difference of a non-regular and a regular language be regular?

When $L_2 = \Sigma^*$, then $L_3 = \emptyset$ no matter what $L_1$ is.

Let us say that a language $L$ is subset-regular if $L \cap L'$ is regular for all languages $L'$. In other words, $L$ is subset-regular if all of its subsets (including $L$ itself) are regular.

Theorem. A language is subset-regular iff it is finite.

Proof. Clearly every finite language is subset-regular. In the other direction, an infinite language has uncountably many subsets, so not all of them can be regular. $\quad\square$

We can replace $\Sigma^*$ above with the complement of any subset-regular language, that is, with any cofinite language. Moreover, due to the theorem above, only cofinite languages work: if $L$ has a non-regular (proper) subset $L'$, then $\overline{L'} \setminus \overline{L} = \overline{L'}$ isn't regular.


Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1?

Refer the following paper; https://www.researchgate.net/publication/2241064_A_New_Weight_Balanced_Binary_Search_Tree.
It has both bottom-up and top-down restructuring.


The easiest way to remember asymptotic notation is to memorize the following table:
$$
\begin{array}{cc}
o & < \\
O & \leq \\
\Theta & = \\
\Omega & \geq \\
\omega & >
\end{array}
$$
For example, if $f(n) = O(g(n))$ then asymptotically and up to a constant multiple, $f(n) \leq g(n)$; formally, there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for large enough $n$. In your case, clearly the average case is at most the worst case, and so $A(n) = O(W(n))$.


Cantor's diagonal method in simple terms?

Here's the standard application explained in the simplest terms I can:

Theorem: There are more real numbers than there are integers.

Lemma: A real number has a decimal representation (that might not terminate), and all decimal representations create real numbers.

Proof of Theorem: Suppose there are as many integers as reals. Then we can list the reals in some order,

$r_1 = 3.141592...$

$r_2 = 2.718281...$

$r_3 = 1.000000...$

and so on for each $r_i$ where $i$ is an integer

There is a contradiction because I can construct a real that is not in the above list. Let $r' = 0.d_1d_2d_3d_4\ldots$ where $d_1$ is not equal to the 1st digit after the decimal of $r_1$, $d_2$ is not equal to the 2nd digit after the decimal of $r_2$, and so forth. For example, I could add 5 and take it mod 10. In the example this gives $r' = 0.665\ldots$. The contradiction is that $r'$ is not in the list, because for any $i$ I know that $r'$ and $r_i$ differ by at least $4*10^{-i}$ (since they differ in $d_i$).

The fact that the reals cannot be enumerated as such shows that they are larger than the integers. But, the important result of Cantor is simply that they cannot be enumerated.


Expanding on reinierpost's comment, here is how to do it in linear time. Every word $w$ can be decomposed as $w = a_1^{k_1} a_2^{k_2} \cdots a_l^{k_l}$, where $a_i \neq a_{i+1}$ and $k_i \geq 0$. This is just decomposition into runs. The LCP of $w$ and its shift is simply $a_1^{k_1-1}$.

In view of this, here is how to compute the answer for all suffixes of a word $w$ in linear time. We go over the array backwards, populating an array $K$ using the following algorithm:

$K_n = 1$.
For $i = n-1,\ldots,0$:

If $w_i = w_{i+1}$, $K_i = K_{i+1} + 1$, otherwise $K_i = 1$.

The answer for the suffix starting at $w_i$ is $w_i^{K_i-1}$.


Since you indicate that the parameter of the near operator can be an arbitrary expression, it should be handled at the parser rather than at the lexer. Otherwise how would you handle things like near(x+y)?


Find Number of even subarrays $O(n)$ [explanation needed]

Let $S_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x_i, x_{i+1}, ..., x_{j}$ using the expression $S_j - S_{i-1}$. This subarray will have even sum only if  $S_{i-1}$ and $S_j$ are both even or both odd.

With this in mind, we can count how many even and odd $S_i$ we have and then calculate the number of possible pairs of $S_i$ and $S_j$ that yield an even number. So if we have $e$ even $S_i$ then there are $e \choose 2$ possible pairs. Each pair, corresponds to a different contiguous subarray.

$$
{e \choose 2} = \frac{e!}{(e-2)!2!} = \frac{e * (e-1)}{2}
$$

Same holds for the pair of odds.


Can application DNS requests bypass a firewall on Windows and Linux

It depends on the policy enforced by the firewall.  If it blocks outbound DNS requests, then the request wouldn't go through; if it doesn't, the request would go through.  A firewall is a mechanism; it has to be configured with a policy that determines which packets or connections are allowed and which are blocked.  Just saying you have a firewall does not tell us what policy you have chosen to have it enforce.
The details of how gethostbyname() behaves are beyond the scope of this site.
You certainly could have a situation where the firewall blocks an application from making DNS requests to the outside world but allows them to a local DNS server; and where the local DNS server acts as a resolver or a proxy and itself makes requests to the outside world.  That will depend on the firewall and how it is configured as well as the DNS server and how it is configured.


Explain auto continue passing style transformations

The code you posted takes a few shortcuts. The mismatch with the rules of the CPS transform comes form your code being in Haskell, which features integers (0,1,2), arithmetics (+,-), definitions by cases, and recursion, while the CPS transform only covers the pure lambda calculus, without all the bells and whistles that come with a "usual" programming language.

Anyway the idea of a CPS function is that you never return the result of the function in a direct way. Rather, you pass that result to a continuation function, usually named k, which is an additional parameter to the function. Often, it is convenient to take k as the last parameter -- this is only a convention, though, and we could choose otherwise.

For instance, the constant-zero function becomes

zero n = 0

zero_cps n k = k 0

Squaring:

square n = n*n

square_cps n k = k (n*n)

Now, in the last line I cheated a bit, since there I am using * as the regular multiplication function, instead of using a CPS variant of multiplication. Your fib_cps code does the same for + and -, which are not translated into CPS.
Let's continue with this.

Now, what if we want to CPS transform this composition?

f n = square (square n)

f_cps n k = ???

Intuitively, in f_cps we want to call square_cps, take its result, and pass that to another square_cps. But we can't do that directly, since square_cps does not return its result, it passes it to the continuation. So, we need to write something like

f_cps n k = square_cps n (\m -> ...???...)

where m is the "result" of square_cps, hence m=n*n. What do we do with m? We want to square it again.

f_cps n k = square_cps n (\m -> square_cps m (\o -> ???))

here o will be the square of the square of n, hence n*n*n*n. That is the final result, so we can pass it to k, which expects the result of f.

f_cps n k = square_cps n (\m -> square_cps m (\o -> k o))

So, in CPS style, we use this "idiom":

function_cps arg1 arg2 ... arg2 (\x -> ...)

meaning "call function with the args, let x be the result, and then proceed with ...".

Code like f1 (f2 (f3 (f4 n))) becomes

f4 n  (\x4 ->
f3 x4 (\x3 ->
f2 x3 (\x2 ->
f1 x2 (\x1 ->
... use x1 here ...))))

(If you happen to be familiar with monads in Haskell, you'll see that this is very similar to a monadic do block. This is not a coincidence since CPS is strictly related to the Cont monad.)

In your fib_cps code, we need to do

fib (n-1) + fib (n-2)

This is transformed into a program which evaluates fib (n-1) first (let x be its result), then fib (n-2) second (let y be its result), and finally returns x+y.
In code

fib (n-1) (\x ->
fib (n-2) (\y ->
k (x+y)))

where the last line combines the results and passes their sum to k, the continuation of the call fib_cps n k.

You might have noticed that we needed to fix an evaluation order: first fib (n-1), then fib (n-2). This order was not present in the original code. Indeed, to transform some code to CPS, we need to be more explicit about what we want to evaluate first.

In your CPS rules, application $MN$ is transformed into

$$
[[M]](\lambda m.\ [[N]](\lambda n.\ \ldots)
$$

which forces $M$ to be evaluated first, then $N$, giving an evaluation order, similarly to what happened above.

Further, the CPS term above always evaluates $N$. This is done according to the call-by-value (CBV) semantics, where function arguments are always evaluated. So, the CBV CPS transform matches such semantics, which is used by languages like Ocaml.

Note that Haskell, instead, uses a call-by-name (CBN) semantics instead, where e.g. zero (non terminating expression) returns 0 immediately without evaluating its argument. If we wanted to use CPS completely preserving Haskell's semantics, we should use another form of CPS called the CBN CPS transform, which is subtly different.

In your posted fib_cps code, CBV CPS is used, even in Haskell, since

+ always evaluates its arguments
we are not using a CPS version of +
CBV CPS is arguably a bit simpler to understand

I hope this does not sound too confusing. Continuations are quite tricky to understand.


Derivation of product type eliminator in type theory

What is meant here, is that you can construct an identification $x=(\mathsf{pr}_1(x),\mathsf{pr}_2(x))$ for any $x:A\times B$. In other words, you can show $$\Pi_{(x:A\times B)}x=(\mathsf{pr}_1(x),\mathsf{pr}_2(x)).$$
In order to do this, we use the induction principle of $A\times B$. By the induction principle it suffices to show that $$\Pi_{(a:A)}\Pi_{(b:B)}(a,b)=(\mathsf{pr}_1(a,b),\mathsf{pr}_2(a,b)).$$
Now you simply observe that by the definition of the projection maps, there are judgmental equalities $\mathsf{pr}_1(a,b)\equiv a$ and $\mathsf{pr}_2(a,b)\equiv b$. Therefore, the above type reduces to $$\Pi_{(a:A)}\Pi_{(b:B)}(a,b)=(a,b),$$
which can be proved by reflexivity.

We conclude that every element of $A\times B$ can be identified with a pair, namely the pair of its own projections. The same is true for $\Sigma_{(x:A)}B(x)$.


Is this a valid induction proof example ?

This is a perfect example of a sloppily written induction proof. Of course the induction hypothesis is not only repeating the proof's statement; otherwise, it would not qualify as a proof at all since it would be assuming the statement is true regardless of the ensuing argument. What is meant, instead, is that $k$ is then fixed and the induction step is conducted for this particular choice of $k$.

The following proof structure is more elegant and IMO much easier to follow (esp. for beginners):

Induction basis: [...]
Induction step: let $k$ be given.
Induction hypothesis (IH): let [statement you are trying to prove] be true for $k$.
Then [ensuing reasoning which shows the statement is true for $k + 1$ by making use of IH].

This makes it explicit for which $k$ the hypothesis should hold as well as what statement it is exactly that we are trying to prove in the induction step.


Why can't exhaustive search parsing stop after |w| + 1 derivations?

You increase the length of the sequential form with each derivation, but you also need to convert non-terminals to terminals.

Think of a grammar in Chomsky normal form. For each word symbol, you need to create a non-terminal first (and you create only one per derivation!) and then convert it into a terminal. That's $2|w| \pm 1$ derivations right there.

Yes, CNF is a little wasteful this way, but finding short derivations isn't its purpose, isn't it?


Sorting an unordered pile of items into drawers with minimal drawer movements

How about the following:

Go through your bag; fold and stack items for drawers $D_i$ and
$D_{i+1}$, $i \in 2\mathbb{N}$, in/on drawer $D_i$
(which you open on demand).

Make sure you have the items for $D_{i+1}$ on top; that may require quite
some reordering pancake-style,
but you don't seem concerned about such operations.

Note that there is always enough room (two drawer heights) to do this,
assuming the drawers are roughly equal and your clothes fit into them as it is.
For each open drawer $D_i$,

pick up the stack for $D_{i+1}$ (and put in the bag, if necessary),
close $D_i$,
open $D_{i+1}$,
put the stack in there, and
close $D_{i+1}$.

This algorithm requires $2M$ drawer movements if all drawers get clothing, so it is worst-case optimal.

It will waste some movements if there are items for $D_{i+1}$ but not $D_i$; if only odd drawers get items, we execute twice the drawer movements necessary. Since this is the worst that can happen, we still have a $2$-approximation.