# Question
Title: Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?
An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.)

However, there are different kind of algorithms, such as deterministic, non-deterministic, and randomized algorithms, and possibly others.

Are these algorithms running on deterministic Turing Machines, or do they have to be run on specific machines? For example:

1. Are nondeterministic algorithm algorithms on a deterministic Turing machine? I heard that they are not, but are on nondeterminisitic Turing machines, but I forget where I heard it. Or I might be wrong.
2. Are randomized algorithms algorithms on a deterministic Turing machine?

# Answer
Broadly speaking, you can normally trade the word "algorithm" for the words "Turing Machine", in the sense that a Turing Machine is not a programmable computer like the one you have in front of you, it is a mathematical embodiment of an algorithm. So for the two cases you mention:

1. A nondeterministic algorithm *is* a nondeterministic Turing Machine.
2. A randomized algorithm *is* a probabilistic Turing Machine.
> 1 votes

# Answer
**In a nutshell**: *A Turing Machine is an algorithm by itself, not a programmable device. However, deterministics, non-deterministic, or randomized algorithms can be interpreted on **universal** deterministic TM. However, this does raise some problems in the case of randomized algorithms.*

I can see the intent of your question, that could be a good one but is not quite well stated. But then it is an opportunity to look at things more precisely. This answer is in agreement with Luke Mathieson's answer, and trying to understand further what motivates the question.

The problem is that you do not program Turing Machines (TM). TMs are not programmable machines, they are just the transition function described by their definition. A TM will do the computation it is intended for an no other.

So, a TM is not a programmable machine. It can at best be considered as belonging to an abstract machine model. This is actually generally true in automata theory. A PushDown Automaton (PDA) is a specific PDA that recognizes only one context-free language.

You may want to see them an abstract machine models with a program running them, but that is not the way theory does it. So, for all purpose and intent, **the program is the machine in the theoretical framework**, i.e. the algorithm is the machine. This is essentially the answer given by Luke Mathieson.

This seems to remain an unsaid misunderstanding, though. People should talk of running an algorithm **as** a Turing Machine, and not **on** a Turing Machine. But a check with a search engine (Google) gives only one answer for the former ("run as a Turing Machine"), but gives 13000 answers for the latter ("run on a Turing Machine").

Now, you may have various kinds of simulations in this context. For example, you can show that for each machine of type A there is a machine of type B that computes exactly the same result.

You can also have so called **Universal Machines**. A universal machine U can take as input the description (encoding) of another machine A together with a description of its inputs I, and mimics the computation on A on the input I. The better known ones are the Universal Turing Machines, and also the classical computer. A more common name for it is an *interpreter*.

**An interpreter is the kind of machine on which you run a program, an algorithm description. I would say it is the only kind for which you question makes sense.**

The difficulty then is to understand what sense the question can make. The problem is that an algorithm may be seen with various intended meanings. For example, the meaning can just be the language it defines, or enumerate. It can also be how it does it. The computational cost of the algorithm may or may not be part of what you are interested in, of what you want to see preserved by the simulation. So the issue is whether the interpreter you are using is or is not capable of simulating the algorithm in a way that gives you a precise account of what you consider of interest in the algorithm computation.

Non deterministic algorithms can be interpreted in various ways on deterministic interpreter. For practical uses, on of the early attempts to do that is due to Robert Floyd's "Non-deterministic algorithms" in 1966.

General context-free parsers can also be viewed as interpretation of non-deterministic PDA on deterministic machines.

Randomized algorithms are also usually interpreted on deterministic machines, using (pseudo) random number generators.

However, *Traduttore, traditore*, running these algorithms on a deterministic interpreter may give only a specific vision, an approximation, of what these algorithms do. But the situation is not quite the same for non-deterministic and for randomized algorithms.

In the case of a non deterministic algorithm, the deterministic simulation, for example with breadth first search of an answer, may lose the spirit of non-determinism, of the computational model, but it gives something that is computationally equivalent. If you choose to view non-deterministic choice as being oracle based, it gives you an implementation of the oracle.

Of course, without going into details, another possibility is to interpret a non deterministic algorithm on a non-deterministic universal machine. I do not know how useful that can be.

In the case of randomized algorithm, things are different. Simulation on a deterministic machine require the use of a random number generator. But, all a deterministic machine can provide is a pseudo random number generator, which is actually a deterministic algorithm. So **deterministic simulation is intrinsically different from a true probabilistic Turing Machine**, and may raise issues regarding the "real" randomness of the generator. My guess, but this would require double checking with experts, is that a true probabilistic TM can produce a non-computable number, while a deterministic simulation cannot do that. But does it matter much?

It is however possible to consider abstractedly that the interpreter has a true random number generator, which is equivalent to **using a probabilistic universal machine as interpreter**. Concretely, on a real interpreting machine such as a computer, that amounts to assuming the random number generator can be trusted, or to using as a random number generator a physical phenomenon considered "truly" random.
> 1 votes

---
Tags: algorithms, turing-machines, randomized-algorithms, nondeterminism, computation-models
---


# Question
Title: Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time
There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.

# Answer
> 9 votes
The 2007 paper Linear-time ranking of permutations gives a linear time ranking algorithm for the lexicographic order, assuming arithmetic on numbers of length $O(n\log n)$ takes constant time.

---

The 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for the lexicographic order. Regarding the latter, it states

> The whole problem of ranking permutations in lexicographic order seems inextricably intertwined with the problem of computing the number of inversions in a permutation, and it seems that a major breakthrough will be required to do that computation in linear time, if indeed it it possible at all.

On the other hand, it does mention an $O(n\log n/\log\log n)$ algorithm for ranking permutations in lexicographic order due to Dietz.

# Answer
> 0 votes
Already given answer being good i wil add another (more recent) reference here:

A New Method for Generating Permutations in Lexicographic Order, by TING KUO (2009)

proposes a method to generate, rank and unrank permutations in lexicographic order, plus a few new features like generate a permutation which is a given distance away from another permutation.

Complexity is again of the $O(nlgn)$ order

---
Tags: permutations
---


title: Similarity of two monochromatic shapes

text:
# Question
Title: Similarity of two monochromatic shapes
I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. Of course this has to work regardless of what the angle shift is and regardless of their scale (only aspect ratio matters).

I know there is SIFT method but this seems too complicated for this simple use case. Is there more suitable method?

**Updated question**

The problem is I don't know the optimal measure too. I mean I have to check if the two shapes are similar not in terms of size or angle but shape. So in terms of those triangles what matters is angle. Of course these shapes not need to be so trivial - they can consist of curves where no angles are present. So far I have found that I can use Procrustes algorithm to eliminate the offset, size and angle but what then? There is Fréchet distance but it seems it won't work for any composite shapes - a square with both diagonals is a good example. I mean this isn't going to work when there are several ways of drawing a figure, is it?

I was also wondering if those shapes can be represented by graphs (so finite number of points) and then I could see what is the length of minimal path going through both points (hamiltonian cycle?) - but I'm not sure if it would work in all scenarios.

While Procrutes algorithm will work with any shape I can think of, Frechet distance is more problematic.

It works well for any shape which can be drawn in one stroke so there are no two ways of doing this. A good example is a triangle

the problem is visible here

as there are more than 1 way of ordering the pixels to get the desired shape. Is there a way to handle this as well with Frechet algorithm? If not, what algorithm should be used?

# Answer
One approach is to apply Procrustes analysis to superimpose the shapes, then use the sum of the squares distances between each pair of corresponding points (i.e., a L2 norm). This is apparently sometimes called Procrustes distance. Here you will use the set of "corners" of the shape as your set of points.

One disadvantage of this approach is that it is not robust in case one or a few points are deleted: maybe shape $S\_2$ is the same as shape $S\_1$ except that it is missing a single point. If you want to be robust to this kind of situation, you could combine RANSAC with Procrustes distance. Pick a random sample of 3 consecutive points from $S\_1$, and 3 consecutive points from $S\_2$; use Procrustes analysis to find the best map $M$ to superimpose those points; apply $M$ to $S\_1$ to get $M(S\_1)$, and use some kind of edit distance to measure the similarity between the vector of points of $M(S\_1)$ and vector of points of $S\_2$ (you might assign a large cost $c\_\text{del}$ to deleting a point, a large cost $c\_\text{ins}$ to inserting a point, and make the cost of matching a point $p$ to a point $q$ be the squared distance $||p-q||^2$ between the two points, then apply standard dynamic programming algorithms to compute the edit distance). Now repeatedly apply this sampling procedure. Keep the best map $M$ you find, where you can determine what you consider best (e.g., the lowest edit distance; or some other metric).

There are probably many other possible distances. For instance, instead of the sum of squared distances, another possibility is to compute $\theta\_i$ (the angle between $p\_i,p\_{i+1},p\_{i+2}$ from the first shape) and $\theta'\_i$ (the angle between $q\_i,q\_{i+1},q\_{i+2}$ from the second shape), then some norm on these angles: e.g., $\sum\_i (\theta\_i - \theta'\_i)^2$. This too could be made robust to a few mismatched points using RANSAC. There isn't enough information in the question to select between these, so without more knowledge, the best I can suggest is to simply try these on a set of examples and see which one seems to give results that most closely match what you are looking for.

None of this will work if your shapes $S\_1$ and $S\_2$ look "similar" but they have a very different number of points. For instance, you mention the case where $S\_1$ is a perfect square (with crisp edges where the angle between all 4 pairs of 3 points is exactly 90 degrees) made out of 20 points total and $S\_2$ is a user-drawn square consisting of 300 points without crisp corners and no 3 consecutive points which align at 90 degree angle. The methods above will not work at all for that kind of situation.

Incidentally, you mention the issue of shapes that can be drawn in one vs those that cannot. I think your representation of a shape as a vector of points implicitly assumes that the shape can be drawn in one stroke (since the points appear in the vector in the order that they're visited by the stroke, and each point is assumed to be connected to the one after it), so if you want to deal with shapes that cannot be drawn in a single stroke, you'll probably need to find a different representation of the shape.
> 0 votes

---
Tags: matching
---


# Question
Title: Description and semantics of program graphs
I'm working on a question which gives me a program graph and tells me to give a mathematical description of it. I'm aware that a program graph PG is a tuple

$(Loc, Act, Effect, \rightarrow, Loc\_0, g\_0)$

This is the question I'm trying to answer:

So far for $PG\_1$ (one of the 2 transition systems) I have:

$Loc = \\{k\_1, k\_2, k\_3\\},$ with $Loc\_0 = \\{k\_1\\}$

$Act = \\{\alpha\_1, \beta\_1, \gamma\_1\\}$

$Effects = \\{Effect(\alpha\_1, \eta) = \eta\[x := x + 1\]$, $Effect(\beta\_1, \eta) = \eta\[y := y - 1\]$, $Effect(\gamma\_1, \eta = \eta\[y := y + 2\]\\}$

$\rightarrow = \\{(k\_1, \alpha\_1, k\_2), (k\_2, \beta\_1, k\_3), (k\_3, \gamma\_1, k\_1)\\}$

$g\_0 = $ ?

I'm aware that $g\_0$ is the starting condition, but I'm not sure what it is in this case? Also for $\rightarrow$ I assumed this was done the same was it is in Transition Systems, if somebody could clarify whether or not this is the correct way to do it I would be really grateful.

Thanks in advance for any help.

# Answer
> 3 votes
## Definitions

From "Principle of Model Checking" By Joost-Pieter Katoen and Christel baier:

> A program graph over a set Var of typed variables is a tuple $(Loc, Act, \>Effect, \rightarrow, Loc\_0, g\_0)$ where:
>
> * $Loc$ is a set of locations
> * $Effect: Act \times Eval(Var) \to Eval(Var)$ is the effect function
> * $\rightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the condition transition relation
> * $Loc\_0 \subseteq Loc$ is a set of initial locations
> * $g\_0 \in Cond(Var)$ is the initial condition

It is further noted that:

> $Eval(Var)$ denote the set of (variable) evaluations that assign values to variables
>
> $Cond(Var)$ is the set of Boolean conditions over Var

Given these definitions, your definitions of $Loc$, $Act$ and $Effect$ are **correct**

## Transitions

So, according to these definition the conditional transition relation must be:

$\rightarrow =\\{(k1,α1, ? ,k2),(k2,β1, ?, k3),(k3,γ1, ?, k1)\\}$

where each questionmark is a tautology, ie something always true (as there are no conditions in the figure). As the authors note,

> If the guard is a tautology ... we simply write $(l, \alpha, l') \in \rightarrow$.

So in conclusion your definition of $\rightarrow$ is **correct**

Furthermore, $Cond(Var)$ must consist of tautologies.

## Initial Condition

To me it seems that there are no given initial conditions on the variables $x,y$ so $g\_0$ must simply be a tautology as $g\_0 \in Cond(Var)$. It seems undefined what specific tautology $g\_0$ must be, but any tautology will do, if you apply the Structural Operational Semantics given in the book, as any location satisfies any tautology.

## Execution and Traces

Both concepts are defined in the context of Transition Systems.

Executions:

> Executions are alternating sequences consisting of states and actions

And traces:

> Thus, rather than having an execution of the form $s\_0 \rightarrow^{a\_0} s\_1 \rightarrow^{a\_1} s2$ . . . we consider sequences of the form $L(s\_0)L(s\_1)L(s\_2)$ . . . that register the (set of) atomic propositions that are valid along the execution. Such sequences are called traces.

For reasoning about executions and traces you thus need to look at the transition system induced from the program graph (by the structural operational semantics given in the book).

---
Tags: semantics, model-checking, software-verification
---


# Question
Title: Can a probabilistic Turing Machine compute an uncomputable number?
Can a probabilistic Turing Machine compute an uncomputable number?

My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should add that I am pretty much ignorant of probabilistic TM and randomized algorithms. I looked at wikipedia, but may even have misunderstood what I read.

The reason I am asking that is that only the computable numbers can have their digits enumerated by a Turing Machine.

But with a probabilistic Turing Machine, I can enumerate any infinite sequence of digits, hence also sequences corresponding to non computable numbers.

Actually, since there are only countably many computable numbers, while there are uncountably many reals that can have their digit enumerated, I could say that my probabilistic Turing Machine can be made to enumerate the digits of a non computable number with probability 1.

I believe this can only be fallacious, but why? Is there a specific provision in the definition of probabilistic TM that prevents that?

Actually, I run into this by thinking whether various computation models can be simulated by a deterministic TM, in question "Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?". Another p\[ossibly related question is "Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?".

# Answer
Consider the following reasonable definition for a Turing machine computing an irrational number in $\[0,1\]$.

> A Turing machine computes an irrational $r \in \[0,1\]$ if, on input $n$, it outputs the first $n$ digits (after the decimal) of the binary representation of $r$.

One can think of many extensions of this definition for probabilistic Turing machines. Here is a very permissive one.

> A probabilistic Turing machine computes an irrational $r \in \[0,1\]$ if, on input $n$, (1) it outputs the first $n$ digits of $r$ with probability $p$; (2) it outputs any other string with probability less than $p$; (3) it never halts with probability less than $p$.

Under this definition, it is not immediately clear whether everything that you can compute is indeed computable (under the sense of the first definition).

However, there are some modifications that do allow us to conclude that the resulting number is computable, for example:

1. We can insist that the machine always halt.
2. We can insist that $p \> 1/2$.

Other modifications are not necessarily enough. For example, does it help if we assume that the non-halting probability tend to $0$ with $n$?

Summarizing, it might depend on the model.
> 4 votes

---
Tags: computability, turing-machines, randomness, probabilistic-algorithms, real-numbers
---


title: Is Weighted Vertex Cover NP-Complete?

text:
# Question
Title: Is Weighted Vertex Cover NP-Complete?
I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's NP-Complete and maybe the knapsack problem can be reduced to it but I'm not sure.

> WEIGHTED VERTEX COVER:
> **Input:** A weighted graph $G$ with integer weight $Wv\>1$ on each vertex $v$ and an integer $T$.
> **Question:** Does $G$ have a vertex cover with total weight at most $T$?

# Answer
Expanding on Pål GD's hint, you can reduced from the normal, unweighted version of VERTEX COVER.

> VERTEX COVER
> **Input:** A graph $G$ and an integer $k$.
> **Question:** Does $G$ have a vertex cover of *size* at most $k$?

So in this case, you're just counting the number of vertices in the cover. Now to transform this to the weighted version, we just need to add weights to all the vertices such that we can recover the size of the vertex cover from the weight of the vertex cover.

Bigger hint under the spoiler tag, don't mouse over unless you're really stuck.

> What happens if we assign each vertex the same weight (doesn't really matter what it is, as long as they're all the same)? If each vertex has weight $c\>1$, what's the weight of a vertex cover of size $k$? What's the size of a vertex cover of weight $T$?
> 2 votes

---
Tags: complexity-theory, np-complete
---


# Question
Title: A language is Turing recognizable iff it is a projection of a decidable language
I was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \\{x \mid \exists y \\;(\langle x, y\rangle \in D)\\}$.

I do not know how to prove this kind of questions, is there any help to solve this problem or any problem as this kind?

# Answer
> 5 votes
There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., here, or search in this site).

The other direction is less obvious, but also not too difficult: Assume that $C$ is recognizable. Then, there exists a machine that halts and accepts any $x\in C$. Thus, you can write the sequence of configurations of $M$ on input $x$, and this sequence is *finite*! This sequence will be the $y$ that exists if $x$ is in the language. You should be able to complete the details from here.

---
Tags: turing-machines, computability, semi-decidability, decidability
---


# Question
Title: Does $\#W$[1]-hardness imply approximation hardness?
Let $\Pi$ be a *parametrized counting problem*, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$.

Assume that $\Pi$ is $\\#W$\[1\]-complete (a known problem for example would be counting the number of simple paths of length $k$ in a graph).

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

---

Note that when discussing a parameter which is the cost of solution it makes sense to discuss the approximation hardness (e.g. see this question), as opposed to other popular parametrizations.

# Answer
$\mathrm{W}\[1\]$-hardness implies that a problem has no *eptas* unless (at least) $\mathrm{W}\[1\] = \mathrm{FPT}$ (having an *eptas* implies parameterized tractability for the standard solution size parameterization), but there are problems with a *ptas* that are $\mathrm{W}\[1\]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$).

Transferring this to $\\#\mathrm{W}\[1\]$-hardness, you can at least say that a $\\#\mathrm{W}\[1\]$-hard problem still has no *eptas*, but I don't think a stronger statement can be made *a priori*. Turning to speculation, I suspect it's also not true that $\mathrm{APX}$-hardness immediately follows from $\\#\mathrm{W}\[1\]$-hardness in general, though perhaps something may be said for higher classes, such as the counting version of $\mathrm{para}\text{-}\mathrm{NP}$.
> 3 votes

---
Tags: complexity-theory, approximation, counting, parameterized-complexity
---


# Question
Title: Question about spanning trees and creating them through BFS and/or DFS algorithms
The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the root v.

What about if instead of DFS I used BFS?

I have no clue where to begin with this one. I feel like I'm overlooking some basic characteristic of the algorithm or the tree that it produces. Any help would be appreciated!

# Answer
If you get to pick, each time, an ordering of the vertices, then statement is trivially true - just choose the ordering that gives that tree, but this is not interesting.

Assuming the vertices do have some fixed order (so the DFS/BFS can't arbitrarily pick which vertex it has to choose next), then statement is false. We can see this via a simple counting argument. As the ordering is fixed, the DFS/BFS produces a unique spanning tree for each starting vertex, i.e. we can produce at most $n$ spanning trees (per algorithm), where $n$ is the number of vertices in the graph.

However if our input graph is $K\_{n}$ with $n \> 3$ (the complete graph on $n$ vertices), the graph has $n^{n-2}$ spanning trees, clearly far more than what we can produce from the DFS/BFS.
> 2 votes

---
Tags: algorithms, graphs, spanning-trees
---


title: Borůvka cleanup in linear time?

text:
# Question
Title: Borůvka cleanup in linear time?
Given boruvka's algorithm:

```
MST T <- empty tree
Begin with each vertex v as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

```

In each phase I'd like to reduce the graph's size, by saying that after each phase - there is actually no need to remember edges that are within each component (because some were inserted to the MST T already and others are not needed). So instead of each component I'd like to put only a single vertex. The only problem comes when I try to construct my edges - an edge between two new vertices (which were two components before) is the one with the smallest weight among all the edges between a vertex in the first component and a vertex in the second. I wanted to implement this in linear time, but I don't see how I can reduce the edges as well, all in linear time?

# Answer
> 4 votes
This depends on what you mean by linear time. If you want $O(n)$, then you're out of luck, there's too many edges to consider in the worst case.

If you mean $O(n+m)$, then it is possible, and it is reasonable to consider this as linear time, as the input needs to represent the edges as well as the vertices, which takes at least $O(n+m)$ symbols.

After each round of selecting which new edges to add, we keep track of which pairs of components are being merged, then we look at these in order (any order is fine) and look at all edges from the new component to each other new component, and record the smallest we have seen. (Note that this is symmetric, so we when we find the smallest edge from new component $A$ to new component $B$, it is also the smallest from $B$ to $A$, so we only need to consider edges going to new components later in the ordering, but this doesn't affect the complexity). To achieve this we can simply look at all edges in order and update the appropriate information.

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: What's the difference between a binary search tree and a binary heap?
These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?

# Answer
> 94 votes
> Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.

Source: https://stackoverflow.com/a/6147264/781723

> Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.

Source: https://stackoverflow.com/a/17476698/781723

# Answer
> 55 votes
**Summary**

```
          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

```

All average times on this table are the same as their worst times except for Insert.

* `*`: everywhere in this answer, BST == Balanced BST, since unbalanced sucks asymptotically
* `**`: using a trivial modification explained in this answer
* `***`: `log(n)` for pointer tree heap, `n` for dynamic array heap

**Advantages of binary heap over a BST**

**Advantage of BST over binary heap**

* search for arbitrary elements is `O(log(n))`. **This** is the killer feature of BSTs.

For heap, it is `O(n)` in general, except for the largest element which is `O(1)`.

**"False" advantage of heap over BST**

**Average binary heap insert is `O(1)`**

Sources:

Intuitive argument:

* bottom tree levels have exponentially more elements than top levels, so new elements are almost certain to go at the bottom
* heap insertion starts from the bottom, BST must start from the top

In a binary heap, increasing the value at a given index is also `O(1)` for the same reason. But if you want to do that, it is likely that you will want to keep an extra index up-to-date on heap operations https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu e.g. for Dijkstra. Possible at no extra time cost.

**GCC C++ standard library insert benchmark on real hardware**

I benchmarked the C++ `std::set` (Red-black tree BST) and `std::priority_queue` (dynamic array heap) insert to see if I was right about the insert times, and this is what I got:

* benchmark code
* plot script
* plot data
* tested on Ubuntu 19.04, GCC 8.3.0 in a Lenovo ThinkPad P51 laptop with CPU: Intel Core i7-7820HQ CPU (4 cores / 8 threads, 2.90 GHz base, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3,000 MB/s)

So clearly:

**GCC C++ standard library insert benchmark on gem5**

gem5 is a full system simulator, and therefore provides an infinitely accurate clock with with `m5 dumpstats`. So I tried to use it to estimate timings for individual inserts.

Interpretation:

* heap is still constant, but now we see in more detail that there are a few lines, and each higher line is more sparse.

This must correspond to memory access latencies are done for higher and higher inserts.
* TODO I can't really interpret the BST fully one as it does not look so logarithmic and somewhat more constant.

With this greater detail however we can see can also see a few distinct lines, but I'm not sure what they represent: I would expect the bottom line to be thinner, since we insert top bottom?

Benchmarked with this Buildroot setup on an aarch64 HPI CPU.

**BST cannot be efficiently implemented on an array**

Heap operations only need to bubble up or down a single tree branch, so `O(log(n))` worst case swaps, `O(1)` average.

Keeping a BST balanced requires tree rotations, which can change the top element for another one, and would require moving the entire array around (`O(n)`).

**Heaps can be efficiently implemented on an array**

Parent and children indexes can be computed from the current index as shown here.

There are no balancing operations like BST.

Delete min is the most worrying operation as it has to be top down. But it can always be done by "percolating down" a single branch of the heap as explained here. This leads to an O(log(n)) worst case, since the heap is always well balanced.

If you are inserting a single node for every one you remove, then you lose the advantage of the asymptotic O(1) average insert that heaps provide as the delete would dominate, and you might as well use a BST. Dijkstra however updates nodes several times for each removal, so we are fine.

**Dynamic array heaps vs pointer tree heaps**

Heaps can be efficiently implemented on top of pointer heaps: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

The dynamic array implementation is more space efficient. Suppose that each heap element contains just a pointer to a `struct`:

* the tree implementation must store three pointers for each element: parent, left child and right child. So the memory usage is always `4n` (3 tree pointers + 1 `struct` pointer).

Tree BSTs would also need further balancing information, e.g. black-red-ness.
* the dynamic array implementation can be of size `2n` just after a doubling. So on average it is going to be `1.5n`.

On the other hand, the tree heap has better worst case insert, because copying the backing dynamic array to double its size takes `O(n)` worst case, while the tree heap just does new small allocations for each node.

Still, the backing array doubling is `O(1)` amortized, so it comes down to a maximum latency consideration. Mentioned here.

**Philosophy**

* BSTs maintain a global property between a parent and all descendants (left smaller, right bigger).

The top node of a BST is the middle element, which requires global knowledge to maintain (knowing how many smaller and larger elements are there).

This global property is more expensive to maintain (log n insert), but gives more powerful searches (log n search).
* Heaps maintain a local property between parent and direct children (parent \> children).

The top note of a heap is the big element, which only requires local knowledge to maintain (knowing your parent).

Comparing BST vs Heap vs Hashmap:

* BST: can either be either a reasonable:

+ unordered set (a structure that determines if an element was previously inserted or not). But hashmap tends to be better due to O(1) amortized insert.
    + sorting machine. But heap is generally better at that, which is why heapsort is much more widely known than tree sort
* heap: is just a sorting machine. Cannot be an efficient unordered set, because you can only check for the smallest/largest element fast.
* hash map: can only be an unordered set, not an efficient sorting machine, because the hashing mixes up any ordering.

**Doubly-linked list**

A doubly linked list can be seen as subset of the heap where first item has greatest priority, so let's compare them here as well:

* insertion:
    + position:
        - doubly linked list: the inserted item must be either the first or last, as we only have pointers to those elements.
        - binary heap: the inserted item can end up in any position. Less restrictive than linked list.
    + time:
        - doubly linked list: `O(1)` worst case since we have pointers to the items, and the update is really simple
        - binary heap: `O(1)` average, thus worse than linked list. Tradeoff for having more general insertion position.
* search: `O(n)` for both

An use case for this is when the key of the heap is the current timestamp: in that case, new entries will always go to the beginning of the list. So we can even forget the exact timestamp altogether, and just keep the position in the list as the priority.

This can be used to implement an LRU cache. Just like for heap applications like Dijkstra, you will want to keep an additional hashmap from the key to the corresponding node of the list, to find which node to update quickly.

**Comparison of different Balanced BST**

Although the asymptotic insert and find times for all data structures that are commonly classified as "Balanced BSTs" that I've seen so far is the same, different BBSTs do have different trade-offs. I haven't fully studied this yet, but it would be good to summarize these trade-offs here:

* Red-black tree. Appears to be the most commonly used BBST as of 2019, e.g. it is the one used by the GCC 8.3.0 C++ implementation
* AVL tree. Appears to be a bit more balanced than BST, so it could be better for find latency, at the cost of slightly more expensive finds. Wiki summarizes: "AVL trees are often compared with red–black trees because both support the same set of operations and take \[the same\] time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither weight-balanced nor mu-balanced for any mu \< 1/2; that is, sibling nodes can have hugely differing numbers of descendants."
* WAVL. The original paper mentions advantages of that version in terms of bounds on rebalancing and rotation operations.

**See also**

Similar question: https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst

# Answer
> 37 votes
Both binary search trees and binary heaps are tree-based data structures.

Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap.

Max Heap:

>

Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree **must** be sorted, unlike heaps.

Binary Search Tree:

>

BST have average of $O(\log n)$ for insertion, deletion, and search.
Binary Heaps have average $O(1)$ for findMin/findMax and $O(\log n)$ for insertion and deletion.

# Answer
> 13 votes
With data structure one has to distinguish levels of concern.

1. The *abstract data structures* (objects stored, their operations) in this question are different. One implements a priority queue, the other a set. A priority queue is not interested in finding an arbitrary element, only the one with largest priority.
2. The *concrete implementation* of the structures. Here on first sight both are (binary) trees, with different structural properties though. Both the relative ordering of the keys and the possible global structures differ. (Somewhat imprecise, in a `BST` keys are ordered left-to-right, in a heap they are ordered top-down.) As IPlant correctly remarks an heap should also be "complete".
3. There is a final difference in the *low level implementation*. A (unbalanced) binary search-tree has a standard implementation using pointers. A binary heap to the contrary has an efficient implementation using an array (precisely because of the restricted structure).

# Answer
> 3 votes
On top of the previous answers, the heap must have the heap structure property; the tree must be full, and the bottom most layer, which cannot always be full, must be filled leftmost to rightmost with no gaps.

---
Tags: data-structures, binary-trees, heaps
---


# Question
Title: Common subgraph isomorphism with K vertex
I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is:

* Compute all combination of vertices with length K of Graph A.
* Run subgraph isomorphism test for every combination vertices against Graph B, probably using VF2 algorithm.

Upon researching I found Maximum Common Subgraph. On one paragraph, there is

> The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k vertices isomorphic to a subgraph of G2 is NP-complete.

This "associated decision problem" is exactly what I'm looking for. But I can't look further than this Wikipedia article to learn about it. Can anybody point me to related paper or text about this problem? Or even better, slightly explain to me how solution of the problem might works compared to my dumb algorithm.

My sincerest thank to you all.

# Answer
> 3 votes
The fact that the Maximum Common Subgraph is NP-complete suggests that your "dumb" algorithm is about as good as it gets. You certainly cannot expect a polynomial time solution.

There are a few approaches you could try, depending on the exact context you are working in, the details of which are more than can reasonably be reproduced here, but a good starting point would be Abu-Khzam *et al.*'s paper "The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover" (In Proceedings of AICCSA 2007, pp. 367-373). This describes a variety of exact approaches which exploit different properties of the input.

---
Tags: algorithms, graphs, graph-isomorphism
---


# Question
Title: Route planning for a car driver picking up people using public transport
We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation:

Person 1 is driving with his car from the south of city A to city B far in the north. He is picking up person 2 who is starting in the west of city A and person 3 who is starting in the east of city A. Person 2 and 3 only use public transport. Most likely, the optimal solution will be that they meet somewhere in the center or north part of city A and then drive on from there.

Any hints on an algorithm to find that solution?

# Answer
> 1 votes
A generalized version of this problem is likely $NP$-complete, however given that very few people are sharing the same car, you can probably get away with an exact, exponential time algorithm.

Assuming your road network is given as a graph, for every node you will want to store:

* The earliest time each person using public transport can get to that node
* For every subset of people sharing the car, what is the earliest time the car can get to that point with that subset of people in it

Basically, if you have $n$ persons and one car, you would get a graph with $2^n+n$ "layers" (one layer for each subset and one layer for each person using public transport).

You can use a Dijkstra-like algorithm to compute these values. You do a multi-start search, starting from the homes of all the people involved. Whenever the car gets to a new node you check whether any people are ready to join the car, if so, you branch (the car continues without picking them up, but also moves to any layers in the graph that can be reached by picking people up). Whenever a person gets to a new node, you check whether the car has already reached that node (and also branch).

Note it is not really branching, but rather pushing more nodes on to the priority queue.

---
Tags: algorithms, graphs, routing
---


# Question
Title: Time Complexity of k-clique problem with fixed k
My question expands on a related question on the link, Why is the clique problem NP-complete? In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-clique problem is polynomial time solvable. The question "Prove that the presence of 3-clique in a graph can be decided in polynomial time" also appears in the book, `S. K. Basu, "Design Method and Analysis of Algorithms, PHI, 2005, pg159.`

To avoid any confusion, I felt it important to clarify that this would only be possible if the graph $G=(V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) is fixed. In such a case a polynomial number of steps $R^m,$ (where $R=f(V,E)$, i.e. $R$ is a constant given by some function of vertices and edges) can be used to find the solution of 3-clique for example. So the conclusion that finding 3-clique for a fixed graph has polynomial time complexity works perfectly fine until this point.

But such a polynomial time algorithm with time complexity less than or equal to linear time complexity can not be designed to find 3-clique, i.e. $m\>1$. Assuming that $k$ is fixed but $G$ is not fixed, in that case the complexity of finding 3-clique will then be exponential, unless someone can provide a polynomial time algorithm with complexity $R^m$, where $m\leq 1$ to find 3-clique for a fixed arbitrary graph. Since we are unable to prove that a polynomial time algorithm does not exist for 3-clique problem on an arbitrary graph, the computational complexity of the problem will hence be treated as being NP-complete based on the relationship $3SAT\leq\_p k$-clique, a proof of which can be found in many standard books on algorithms.

# Answer
> 2 votes
A polynomial algorithm does exist for finding whether a graph contains a triangle. For one, you can go over all triplets $x,y,z$ of vertices, and check if the graph contains the triangle $\\{x,y\\},\\{y,z\\},\\{x,z\\}$. This algorithm takes $O(n^3)$. Surprisingly, there is a faster algorithm: take the adjacency matrix $A$ of the graph, and compute the trace of the matrix $A^3$. The graph contains a triangle iff the trace is positive. This algorithm takes $O(n^\omega)$, where $\omega \< 2.373$ is the exponent of matrix multiplication.

# Answer
> 1 votes
I'll try to explain how I understand this. May be after that I'll understand it better :)

"k-Clique problem" is NP-complete, and "k-Clique problem for a fixed k" is easily solvable in polynomial time, and there is no contradiction here.

Let F be a function "size of the problem" -\> "time required to solve it".

"size of the problem" here is a length of an input string, which describes the problem. I guess it's not an obvious thing. It depends on "encoding". If we have a graph with $n$ vertices, we will need at least $log(n)$ characters to encode a single node id, there may be about $n\*n$ edges, so we need ~ $n\*n\*log(n)$ characters to describe all the edges. To fully describe the problem we also need to include the "k" in the input string, so that the machine would know what kind of clique it is looking for. Probably some additional "formatting" characters would be necessary to delimit.

May be there are a little more compact ways to construct an input string. But looks like "size of the problem" is $O(n^l)$ for some $l$. I am not ready to prove it.

If $k$ is fixed, it's easy to construct a Turing machine which checks if k-Clique exists in a given graph. This machine would require polynomial time to solve the problem. Either $O(n^m)$ or $O($"size of the problem"$^m)$ - it does not really matter since "size of the problem" is $O(n^l)$.

But if $k$ is not fixed, there is no way to construct a Turing machine which would solve the problem in $O($"size of the problem"$^m)$ time. Size of the problem "is there a $n$-Clique in $2\*n$ nodes graph" is polynomial of $n$, but all the techniques we used to solve the problem for a fixed $k$ would not help us to solve this problem fast (in polynomial of $n$ or polynomial of "size of the problem" time).

---
Tags: complexity-theory, np-complete, polynomial-time
---


# Question
Title: MST with half the edges the maximum weight
I have been cracking my head over the following question -

> You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with repetitions), and the other half of edges all have weight C. Is it true that every MST of the graph includes the same number of edges of weight C?
>
> If Yes, describe an efficient algorithm for finding the number of edges of weight C in every MST of the graph. The output is between 0 and |E| / 2, no need to return the MST.
>
> If No, show a counterexample.

My work so far -

I've managed to prove to myself that the number of C weighing edges included in a spanning tree (not minimum) can be anywhere between 0 and |E| / 2 (using a cycle with C edges crossing it).

Obviously, I couldn't find a counterexample yet. It feels like what's preventing me from creating two different MST's with a different number of C edges is that for creating a graph that has more than one MST you need to have cycles, and if a C edge is contained in the cycle it won't be chosen (Kruskal). That is the direction I'm leaning towards for a proof, proving a more general claim obviously.

Assuming the above is in fact true, I need to show an efficient algorithm for finding the number of C edges in every MST. The question states there is no need to return an MST, so it seems like there should be a better algorithm than finding the MST and counting the number of C edges in it, meaning this algorithm should be more efficient than sorting. From what I showed above, it could be anywhere between 0 and |E| / 2 so I'm kinda lost here too.

# Answer
> 3 votes
All spanning trees have the same number of edges of each weight, as shown by Raphael as an answer to a question in that direction (thanks hengxin).

How to we count the number of heavy edges, of weight $C$, without computing the MST explicitly? First ignore the heavy edges. Also ignore the weights of the remaining edges. Determine the number $k$ of connected components in the resulting graph of light edges. The number of heavy edges then equals $k-1$. Here I assume all nodes in the graph are reachable.

# Answer
> 3 votes
If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$. If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer.

So now you want to know whether the answer is yes. To see that it is, observe that each MST is constructed by running the greedy algorithm on a specific linear extension of the partial order induced by the weights. In your case, the edges $E$ partitioned into sets $E\_{\<C}$ and $E\_C$, and every edge in $E\_{\<C}$ comes before any edge in $E\_C$ for all of these linear extensions. That tells you that every MST is made of a spanning forest $F$ on the subgraph induced by $E\_{\<C}$ and some edges from $E\_C$; since all the choices for $F$ have the same size, we are done.

---
Tags: algorithms, trees, minimum-spanning-tree
---


# Question
Title: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
If a weighted graph $G$ has two different minimum spanning trees $T\_1 = (V\_1, E\_1)$ and $T\_2 = (V\_2, E\_2)$, then is it true that for any edge $e$ in $E\_1$, the number of edges in $E\_1$ with the same weight as $e$ (including $e$ itself) is the same as the number of edges in $E\_2$ with the same weight as $e$? If the statement is true, then how can we prove it?

# Answer
**Claim:** Yes, that statement is true.

**Proof Sketch:** Let $T\_1,T\_2$ be two minimal spanning trees with edge-weight multisets $W\_1,W\_2$. Assume $W\_1 \neq W\_2$ and denote their symmetric difference with $W = W\_1 \mathop{\Delta} W\_2$.

Choose edge $e \in T\_1 \mathop{\Delta} T\_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T\_1 \mathop{\Delta} T\_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T\_1$ and assume $T\_1$ has more edges of weight $\min W$ than $T\_2$.

Now consider all edges in $T\_2$ that are also in the cut $C\_{T\_1}(e)$ that is induced by $e$ in $T\_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T\_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T\_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T\_2 \cap C\_{T\_1}(e)$ (where $T\_1$ is the updated version) have weights other than $w(e)$.

Now we can always choose $e' \in C\_{T\_1}(e) \cap T\_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

$\qquad \displaystyle T\_3 = \begin{cases} (T\_1 \setminus \\{e\\}) \cup \\{e'\\}, &w(e') \lt w(e) \\\\[.5em\] (T\_2 \setminus \\{e'\\}) \cup \\{e\\}, &w(e') \gt w(e) \end{cases}$

which has smaller weight than $T\_1$ and $T\_2$; this contradicts the choice of $T\_1,T\_2$ as minimal spanning trees. Therefore, $W\_1 = W\_2$.

---

1. The nodes incident of $e$ are in $T\_2$ connected by a path $P$; $e'$ is the unique edge in $P \cap C\_{T\_1}(e)$.
> 19 votes

# Answer
Here is a slightly simpler argument that also works for other matroids. (I saw this question from another one.)

Suppose that $G$ has $m$ edges. Without loss of generality, assume that the weight function $w$ takes on values in $\[m\]$, so we have a partition of $E$ into sets $E\_i := w^{-1}(i)$ for $i\in \[m\]$. We can do induction on the number $j$ of non-empty $E\_i$ and number of vertices $n$ in $G$; for $j=1$ and any $n$, the statement is obvious.

A standard fact about matroids is that for every MST $T$ there is a linear extension of the ordering induced by $w$ so that the greedy algorithm produces $T$.

To close the induction, take $t$ to be the largest number so that $E\_t$ is not empty. Set $E' = E\_1 \cup \cdots \cup E\_{t-1}$. Observe that any linear extension of $w$ puts every edge in $E'$ before any edge in $E\_t$. According to the fact, any MST consists of a spanning forest $F$ of the subgraph induced by $E'$ and some edges from $E\_t$. By the inductive hypothesis, each connected component of $F$ has the same number of edges from each $E\_i$ for $i \< t$. Since all the choices of $F$ have the same size, the number of edges from $E\_t$ required to complete $F$ to a spanning tree is independent of the choice of $F$ and we are done.
> 6 votes

---
Tags: graphs, spanning-trees, weighted-graphs
---


# Question
Title: Polynomial time algorithm for finding two or more vertex-disjoint cycles
The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a graph.

The difficulty however comes when we are required to find in polynomial time whether 2 vertex disjoint cycles exist in an arbitrary graph. Is there such a polynomial time algorithm which finds whether 2 vertex disjoint cycles exist in an arbitrary graph?

By vertex disjoint cycles, I mean cycles which do not share a common vertex.

# Answer
> 6 votes
The structure of graphs without two vertex-disjoint cycles is well understood (see for example Bollobás, Extremal graph theory), having been researched in 1965 by Dirac and the 17-year old Lovász (separately).

**Theorem 1.** Suppose that $G$ has minimum degree at least $3$. Then $G$ has no two vertex-disjoint cycles if and only if one of the following holds:

1. $G \setminus \\{v\\}$ is a forest for some vertex $v$.
2. $G$ is a wheel (a cycle plus a vertex connected to all vertices in the cycle).
3. $G$ is $K\_5$, the clique on 5 vertices.
4. $G \setminus \\{v,u,w\\}$ is an independent set for some three vertices $v,u,w$.

**Theorem 2.** A graph $G$ has no two vertex-disjoint cycles if and only if either $G \setminus \\{v\\}$ is a forest for some $v$, or $G$ is obtained from one of the graphs $H$ in Theorem 1 by subdividing edges, adding a forest, and possibly connecting each tree in the forest by a unique path to $H$.

Theorem 1 can clearly be implemented algorithmically in polynomial time. In order to implement Theorem 2, we need to undo the subdivision and remove the forest and its attaching paths. We can identify the forest by removing isolated trees and identifying paths leading to trees. We can then undo the subdivision by compressing paths, reducing to the case of Theorem 1. It seems that everything can be implemented in polynomial time.

---
Tags: algorithms, graphs, polynomial-time
---


# Question
Title: Why does this mergesort variant not do Θ(n) comparisons on average?
A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:

```
sort(array):
    if length(array) < 2:
        return array
    unsorted ← empty_array
    i ← 0
    while i < length(array) - 1:
        if array[i] > array[i + 1]:
            push(unsorted, pop(array, i + 1))
        else:
            i ← i + 1
    return merge(array, sort(unsorted))

```

(`push(array, element)` puts the new element at the end of the array and increases the array’s length by 1. `pop(array, index)` removes the element at that index from the array, moving all the elements at greater indices and decrementing the array’s length, and returns the removed element. `merge` is the same as in mergesort.)

Instead of simply splitting the array in the middle like mergesort, it splits it so that one resulting array doesn’t need to be recursively sorted. Let $n$ be the length of the array to be sorted. Applying the Master Theorem gives us

$$\begin{align\*} T(n) &= T(n / b) + \mathrm{splitComparisons}(n) + \mathrm{mergeComparisons}(n) \\ &= T(n / b) + (n - 1) + n \\ &= T(n / b) + 2n - 1\\,, \end{align\*}$$

so $f(n) = 2n - 1$ and $a = c = 1$ in the statement of the Master Theorem.

$b$ is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that `array[i] > array[i + 1]` (for all `i`), $b = 4$. $b$ is clearly greater than $1$, since the length of unsorted array grows smaller with every recursive call, so taking the logarithm with base $b$ of $1$ will always give us $0$, which is less than $c$. Then $T(n) = \Theta(f(n)) = \Theta(n)$.

But that can’t be true, so the Master Theorem isn't applicable for some reason; I suspect because $b$ isn't constant, but I don’t know how to prove that. The worst case of the sorting algorithm obviously requires a quadratic number of comparisons and the best case linear, so by analogy with bubblesort, insertion sort, etc, I’m guessing this algorithm also makes a quadratic number of comparisons on average.

# Answer
Since you don't do any reordering while splitting, the length of `array` after the `while` loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in `unsorted`.

In particular, there is no $b$ so that your ansatz describes the actual number of comparisions.

Assuming that the probability distribution of the length of the longest increasing subsequence survives your splitting, a proper ansatz would be of the form

$\qquad\displaystyle C(n) = C(n - 2\sqrt{n}) + \Theta(n)$

which does not seem to solve² to $C \in O(n)$.

In fact, it's even worse since you keep the "first" increasing subsequence, not the longest (in general); consider for instance $\[1,n,2,3,4,\dots,n-1\]$; you keep $\[1,n\]$ and recurse on $\[2,3,\dots,n-1\]$.

---

1. On the distribution of the length of the longest increasing subsequence of random permutations by J. Baik, P. Deift and K. Johansson (1999) \[via Wikipedia\]
2. I have not solved it explicitly, but plots suggest as much.
> 4 votes

# Answer
You seem to be assuming that `pop` takes $O(1)$ time. That assumption is wrong.

You can't implement `pop` in $O(1)$ time, since `pop` requires shifting all elements after `index` one to the left, which is $O(n)$ time using the obvious implementation. (There are modestly better methods, but nothing that achieves $O(1)$ time like you are implicitly assuming. If you want to claim a particular running time, it's your job to specify how you plan to implement `push` and `pop` and justify their running time carefully.)

Consequently, the time complexity of your algorithm is not $O(n)$.
> 0 votes

# Answer
Assuming input `array` is in decreasing order, then `array[i] > array[i+1]` is always satisfied, your algorithm would move all but the first item from `array` to `unsorted`. The running time is at least $\Omega(n^2)$.

Let `array` `array'` denote the same variable before and after the while loop. Then `array[i]` is left in `array'` if and only `array[i]` is (one of) the biggest among `array[0], ..., array[i]`. In expectation, there would be only $O(\log n)$ items left in `array'`, assuming the input `array` is random.
> -1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, average-case
---


# Question
Title: Decidability of "Is this regular expression prefix-free?"
Say that string $x$ is a *prefix* of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it doesn’t contain a proper prefix of any of its members. $$ \text{Prefix-FreeREX} = \\{(R) \mid R \text{ is a regular expression and $L(R)$ is prefix-free}\\} $$ I was wondering about how to prove that Prefix-FreeREX is decidable. Also why does a similar approach fail to show that Prefix-FreeCFG is decidable?

# Answer
> 9 votes
Let $L$ be a language on the alphabet $A$. Then $L$ is prefix-free if $L \cap LA^+$ is empty. If $L$ is regular and given by a regular expression, then $L \cap LA^+$ is also regular (and one can effectively compute a regular expression for it). Now testing whether a given regular language is empty is decidable.

For context-free languages, the situation is different. Above proof does not work because the context-free languages are not closed against intersection. In fact, there *is no algorithm* to decide whether a given context-free grammar generates a prefix-free language.

Here is a proof of this claim \[Luc Boasson, personal communication\].

Let $(u\_1, v\_1), \dotsm, (u\_n,v\_n)$ be two finite lists of words of $A^\*$ defining an instance of the Post Correspondence Problem (PCP) and let $X = \\{x\_1, \ldots, x\_n\\}$ be an alphabet of $n$ letters. Assume that $A$ and $X$ are disjoint and consider the homomorphims $u, v: X^\* \to A^\*$ defined by $u(x\_i) = u\_i$ and $v(x\_i) = v\_i$. Consider the languages \begin{align} U &= \\{x^Ru(x) \mid x \in X^+ \\} \\ V &= \\{x^Rv(x) \mid x \in X^+ \\} \end{align} Let $\sharp$ be a new letter. Then $U \cup V\sharp$ is a context-free language. It is prefix-free if and only if $U$ and $V$ are disjoint if and only if the Post Correspondence Problem has no solution. Thus deciding whether a given context-free language is prefix-free is undecidable.

# Answer
> 7 votes
A deterministic finite automaton $A$ accepts a prefix-free language if and only if there is no accepting run which contains more than one final state. That, in turn, is the case if and only if $A$ has no final state that is reachable from a final state which, in turn, is reachable from the initial state. This can be checked by simple graph traversals.

So you can decide your problem by converting the regular expression to an equivalent automaton, determinising and then performing above mentioned checks.

Intuitively, this won't work for CFL (that is PDA) because

* there is a one-state PDA for every CFL, so there's little to see, and
* not every CFL has a *deterministic* PDA.

---
Tags: computability, regular-expressions
---


# Question
Title: Number and probability of random allocations of n processes to n servers
I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space of allocations is n^n, and each has equal probability.

Intuitively this seems unlikely to me: if you imagine each server having a number and that number being the number of processes assigned, you wouldn't have the case of two servers being assigned n processes; yet the n^n -- as far as I can see -- assumes that such allocations are possible.

Am I missing something?

# Answer
The number $n^n$ can be easily obtained if you think the problem in the other direction: each process has $n$ choices and therefore $n$ processes has $n^n$ possible choices in total. Of course it is impossible that two servers have $n$ processes. If a process can be assigned to more than one server, the number of possible assignments is far more than $n^n$.
> 3 votes

# Answer
> "you wouldn't have the case of two servers being assigned n processes"

No, you certainly cannot have two servers, each being assigned $n$ processes, as that would require a total of $2n$ processes -- whereas there are in fact only $n$ processes.

> "yet the n^n -- as far as I can see -- assumes that such allocations are possible."

There's the source of your misconception. I'm not sure why you think this is true. (In the future, if you spell out your reasoning in the question, it's more likely someone can give you a helpful explanation.) No, the $n^n$ answer does not assume that such an allocation is possible.

One way to help you think about this is try thinking about the case $n=2$. Write down the sample space: try writing down all possible outcomes, and the probability of each. I think that will help you see what's going on.

Here's the other way to think about it: for each process, there are $n$ places it can go (independent of all other processes). For two processes, that means $n^2$ ways where to assign them. For $n$ processes, there are $n^n$ ways to assign them.

But try the example with $n=2$ and see what happens. If that's not enough, next try the example with $n=3$ and see what happens. In general, if you are confused, working through special cases and small examples is often extremely helpful.
> 0 votes

---
Tags: combinatorics
---


# Question
Title: Allocating n processes to n servers, counting from the server perspective
In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from the perspective of the choice when allocating each process.

I'd like to know -- to expand my understanding of counting -- how we might count in a different way, from the server perspective: assigning each server to some number of processes.

The obvious problem I see is if I have already allocated one process to a server, I then can't allocate it to another, and so the analysis becomes complicated -- each server-based count is dependent on all other server-based counts.

Is this a common problem, and there's actually a heuristic to know which way to count things?

# Answer
The heuristic is: "try both ways, and see which works". As you get more practice you might start to develop a sixth sense about which one to try first, but that's the most useful principle I can suggest.

The general mathematical principle is the bijection principle. If you have two finite sets $S,T$ and you can find a bijection between $S$ and $T$, then they must have the same size. So, if you can count the number of elements in either of them, you can infer the number of elements in the other one.
> 1 votes

---
Tags: combinatorics
---


# Question
Title: Shortest paths in weighted graphs, and minimum spanning trees
I stuck in one challenging question, I read on my notes.

> An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this graph, the shortest path between any two vertices is on the minimum spanning tree (MST). Verify the following:
>
> 1) shortest path between any two vertices $u$, $v$ is unique.

My question is, is this statement (1) is false or True?

Other details is not mentioned in the old exam question, But I think:

1) if this means that for any pair of vertices and for any shortest path between them, it lies on MST So this statement is False. for example Let's assume that we have a graph with two vertices $\\{1, 2\\}$ and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex ($\[1, 2\]$, $\[1, 2, 1, 2\]$, ...)

2) if this means For each $a,b\in V$, for each shortest path $P$ from $a$ to $b$ in $G$ there exists a minimum spanning tree $T$ of $G$ such that $p$ is contained in $T$. this statement is True.

# Answer
> 0 votes
Let's consider the hypothesis of the question to try clarify every aspect:

Our Graph G should:

1. be undirected
2. be weighted
3. be connected
4. with no negative weights
5. with all weights distinct
6. in this graph, **the** shortest path between any two vertices is on the minimum spanning tree (MST)

I believe the key point here is the article used in point 6, as pointed out by David Richerby comment

From the wikipedia page: Article (grammar):

Definite Article

> A **definite article** indicates that its noun is a particular one (or ones) identifiable to the listener. **It may be something that the speaker has already mentioned, or it may be something uniquely specified**. The definite article in English, for both singular and plural nouns, is **the**.

Indefinite article

> An **indefinite article** indicates that its noun is not a particular one (or ones) identifiable to the listener. **It may be something that the speaker is mentioning for the first time, or its precise identity may be irrelevant or hypothetical, or the speaker may be making a general statement about any such thing.**

So point 6 lends to some ambiguity:

1. It could be that **the shortest path** is implied to be unique. (In this case I must say the hypothesis and the question are sort of misleading)
2. Or it could be that **the shortest path** is only one of the possible shortest paths between any two vertices

So if we interpret the hypothesis as per point 1 (i.e. the shortest path means there is a unique shortest path) then the hypothesis is also the answer.

If we interpret the hypothesis as per point 2 then we could consider the following undirected graph:

```
A--5--B
|   /
2  3
| /
 C

```

There is no unique shortest path between A and B
Since we could have both:
AB (cost 5)
AC + CB (cost 2+3 = 5)

So if we interpret the hypothesis not meaning the shortest path is unique and asks you to verify this, then we have demonstrated that there is such graph with no unique shortest path that satisfies all other conditions.

---
Tags: graphs, trees, shortest-path, minimum-spanning-tree
---


title: Suffix Tree algorithm complexity

text:
# Question
Title: Suffix Tree algorithm complexity
I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident with it to say so. Well on average we go $\log n$ deep and need at max $|\Sigma|$ steps to find a corresponding node that matches (or not). Thus I would come up with $O(n \cdot |\Sigma| \cdot \log n)$.

> Repeat the following for all suffixes of the given string, right to left.
>
> 1. Scan if its in tree
>     * Not in tree -\> add it as new node
>     * Is partly in tree -\> fork here, such that the matching part remains
> 2. Go back to step 1 until the sequence that was observed equals the source

# Answer
There is no one complexity for all suffix tree algorithms. There are multiple algorithms, with different running times. It is not helpful to talk about this as though there was only one complexity that applies to all algorithms for computing a suffix tree. If you want to ask what is the running time of an algorithm for this task, you need to specify which algorithm you are asking about.

There are also multiple different models. Some algorithms are designed for the regime where $\Sigma=\\{0,1\\}$ or where you have a small finite-sized alphabet (e.g., $|\Sigma|=256$), where it is reasonable to consider $|\Sigma| \in O(1)$. Consequently, the running time for those algorithms might not include any dependence on $|\Sigma|$ -- which is reasonable if you assume that $|\Sigma| \in O(1)$. Other algorithms are designed to work even when the size of the alphabet is large. For those, the dependence on $|\Sigma|$ is at the heart of the problem. Therefore, you'll also find some algorithms designed for the large-alphabet regime, and typically the running times that are quoted for those algorithms *do* show the dependence on $|\Sigma|$. Therefore, when you read a paper on a suffix tree algorithm, if you want to use the algorithm on a situation where the alphabet size is large, you need to carefully examine the assumptions that were made during the running time analysis. Does the quoted running time include the dependence on $|\Sigma|$? Does the paper assume $|\Sigma| \in O(1)$?

Finally, the dependence on $|\Sigma|$ can depend on subtle aspects of how the data structures are instantiated. Therefore, a high-level description of the algorithm is often not enough -- you often need to know how the tree is represented and how the individual steps are instantiated to tell what the dependence on $|\Sigma|$ will be.

I suggest you read What are the effects of the alphabet size on construct algorithms for suffix trees?

I also suggest you take a look at What is the difference between an algorithm, a language and a problem?, to help you think clearly about the difference between a problem vs an algorithm.
> 4 votes

---
Tags: algorithms, algorithm-analysis, data-structures, runtime-analysis, suffix-trees
---


# Question
Title: Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph
I have been scratching my head to find good counter examples to the following problem:

> Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A directed graph is acyclic if it has no directed cycle. Suppose that we want to compute the maximum-weight acyclic subgraph of G (where the weight of a subgraph is the sum of its edges' weights). Assume that G is weakly connected, meaning that there is no cut with no edges crossing it in either direction.
>
> Here is an analog of Prim's algorithm for directed graphs:
> Start from an arbitrary vertex **s**, initialize **S={s}** and **F=∅**.
> While **S≠V**, find the maximum-weight edge **(u,v)** with one endpoint in **S** and one endpoint in **V−S**. Add this edge to F, and add the appropriate endpoint to **S**.
>
> Here is an analog of Kruskal's algorithm. Sort the edges from highest to lowest weight. Initialize **F=∅**. Scan through the edges; at each iteration, add the current edge **i** to **F** if and only if it does not create a directed cycle.

Both algorithm fail.
There should be a 4 vertices graph with 2 cycles that demonstrate this.

So far I played with different weights for this:

```
A<----B
^⟍    ^
|  ⟍  |
|    ➘|
C<--- D

```

However I am not yet able to prove that both algorithms fail. I would love any suggestioin

# Answer
This is a nice exercise. You should probably do it yourself, to get the learning benefit. I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example. Basically, keep trying what you've been doing, but be more systematic and exhaustive about it. You're on the right direction -- keep at it.
> 3 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree
---


title: Does spanning tree make sense for DAG?

text:
# Question
Title: Does spanning tree make sense for DAG?
Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.

# Answer
> 9 votes
Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem, also known as the arborescence problem (PDF). The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.

# Answer
> 8 votes
One generalization of a tree in a directed graph is an arborescence. It is a directed tree with all edges directed from parent to child.

# Answer
> 1 votes
The case for DAGs is trivial, which might be the reason you cannot find any dedicated information about them.

First, there must be a unique vertex $r$ of zero incoming degree, which is the root of the directed spanning tree (arborescence). (Otherwise no spanning tree can exist.)

Next, for each vertex $v \neq r$ choose a parent vertex $P(v)$ such that the $w(v, P(v))$ is minimal.

We chose $|V| - 1$ edges in a graph of $|V|$ vertices with no cycles, so thus chosen subset of edges forms a spanning tree $T$. Any other spanning tree, for each vertex $v \neq r$, must have a unique incoming edge $(v, Q(v))$. By our construction $w(v, P(v)) \leq w(v, Q(v))$. Summing over all $v \neq r$ we get that $T$ is minimal.

---
Tags: graphs, spanning-trees
---


# Question
Title: Recommendations for machine learning book?
I am a microbiologist and I am currently self-studying machine learning from some open lecture videos. I am finding it pretty difficult to understand proofs that are somewhat "obvious", my poor mathematical knowledge is to blame for that. Can you please recommend a text-book that deals with the mathematical proofs of the theorems? Or approaches machine learning from the mathematical side?

# Answer
> 2 votes
MOOC Course on Machine Learning: https://www.coursera.org/course/ml

Guide to Mathematical Proofs from berkeley: https://math.berkeley.edu/~hutching/teach/proofs.pdf

Enjoy!

# Answer
> 1 votes
This might be helpful:

Machine Learning by Tom Mitchell

According to the Centre for Computational Statistics and Machine Learning:

"*A good introduction book for machine learning in general. It is **easy to read and goes at a low pace**. Some topics are a bit dated and not very popular currently and some of the recent progress as kernel methods and graphical models are missing. But it includes an overview to genetic algorithms and reinforcement learning. I suggest to read chapters 1, 4-9 and 13.*"

---
Tags: machine-learning, proof-techniques
---


# Question
Title: Is the time reversal symmetry of non-deterministic computations important?
A deterministic computation can only be run backward in time, if all transitions are one-to-one. This restriction is absent for non-deterministic computations. Hence it seems to me that non-deterministic computations be can run both forward and backward in time. But because the output becomes the input for the reversed computation, and the only output for a decision problem is "yes"/"no", this time reversal symmetry seems pretty useless for decision problems.

Now I wonder whether there is some class of computational problems for which this fact would translate into a corresponding useful property. Something like the fact that "P = co-P", which is a useful property of decision problems for deterministic computations.

> Is there a computational problem type for which the time reversal symmetry of non-deterministic computations turns into a useful property for certain problem classes?

The computational problem types I have in mind here are the different types of requested output like

* decision problem
* optimization problem
* search problem
* counting problem
* function problem

because the different types of expected input (that come to my mind) like

* offline/online problem
* (non-)promise problem

seem to be closely tied to the computational problem itself, so that they are probably not helpful for general symmetry considerations.

# Answer
The time reversal symmetry is already important for decision problems. It translates into reversal of the accepted language. The trick is to replace total functions by partial functions, and don't consider "yes"/"no" as output of the problem. Instead, the "yes"/"no" is derived from the existence of a path between start and end state. This is explained for finite automata in my answer to the question "Why is non-determinism useful concept?", and elaborated for more powerful machines like pushdown automata, Turing machines and probabilistic machines in my answer to the question "What is the difference between non-determinism and randomness?".

This raises the question whether deterministic context-free languages are closed under the reversal of $L$, because this is the only one of the examples where the deterministic and the non-deterministic languages are not identical.

The importance of the time reversal symmetry is not necessarily limited to the decision problem. It might be possible to also work out its consequences for the counting problem and the function problem.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs
A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-*expander* if the graph has $n$ vertices, maximum degree $d$, and satisfies the following *expansion property*:

* for every subset $W\subset V$ such that $|W|\leq n/2$, $|W\cup N(W)|\ge (1+\varepsilon)|W|$

where $N(W)$ is the neighborhood of $W$ in $G$. The expansion property means, informally, that the neighborhood of $W$ is "large" when $W$ is "small". That expanders exist can be shown with the probabilistic method (see, e.g., this writeup from Ellis).

I'm trying to show that expanders can be used to amplify the success probability of one-sided Monte Carlo algorithms. In particular, given a polynomial time algorithm $A$ for a problem in RP that uses $n$ random bits and gives false negatives with probability at most $1/2$ we want to show there is a polynomial time algorithm that uses $n$ random bits and gives false negatives with probability at most $n^{-c}$ for a fixed constant $c$.

Here is the method I've been asked to analyze. We regard $A$ as a function $A(x,r)$ where $x$ is the input and $r$ is a string representing the random bits. On the input $x$ we then:

* Fix a $(2^n,d,\varepsilon)$-expander $G$ and identify its vertices with $\\{0,1\\}^n$
* Select a vertex $r$ of $G$ uniformly at random
* Compute the set $y\_1,y\_2,\ldots, y\_t$ of vertices at distance at most $\delta$ from $r$ in $G$
* Say "no" if and only if $A(x,r),A(x,y\_1), \ldots, A(x,y\_t)$ are all "no"

What I need to show is that for $\delta = O(\log n)$ the probability of a false negative is at most $n^{-c}$.

As a side note, this is actually enough to accomplish the original goal. A result of Gabber and Galil is that there is a family of $(2^n, 5,(2 - \sqrt{3})/4)$-expanders with the additional property that the neighbors of any vertex can be enumerated in polynomial time. This means that $d$ and $\varepsilon$ can be taken uniformly in $n$, and that we can implement BFS from $r$ in polynomial time per vertex considered. Since $t\le d^{\delta + 1}$, the new algorithm runs $A$ a number of times polynomial in $n$ for $\delta = O(\log n)$ and $n$ is polynomial in the input size. Since $G$ is deterministic and does not depend on $A$, there is also clearly no new randomness.

---

Here is how I approached the problem thus far.

Let $G$ be given. Since $|V| = 2^n$, we have an identification $V \cong \\{0,1\\}^n$. Let $r \in \\{0,1\\}^n$ be chosen at random so that $r$ corresponds to a random starting point in $G$. Define a ball $B(v,\delta) = \\{u \in V: d(u,v) \leq \delta\\}$ where $d(u,v)$ is the length of the shortest $uv$-path. We are only interested in the number of *bad balls*, namely balls such that all $u\in B(v,\delta)$ result in false negatives, that is, our $\mathsf{RP}$ algorithm should accept but reject nonetheless. If we can bound above the number of bad balls by $2^n/n^c$ for some constant $c$, then we are done since an error occur if and only if the chosen vertex $y\_i$ is such that $B(y\_i,\delta)$ is bad.

I tried bounding the number of vertices in a bad ball using the expansion property of $G$, but I am not sure how this could help considering balls are certainly not disjoint. We also know that at most $1/2$ of the vertices will result in a false negative.

Any help would be greatly appreciated.

# Answer
> 5 votes
Since nobody else answered, here is what I had in mind when I made my comment. The basic idea behind the proposed amplification algorithm is that expanders are "negatively curved" in the sense that small sets in degree-bounded expanders should have a lot of their volume near the boundary. This then suggests that a ball centered in a small set should quickly "escape" with reasonable probability.

To answer a question from your comment, since the ball around a random vertex isn't a uniformly random set, we wouldn't expect a bound like $2^{-s}$ for the probability of being bad. Instead we get something that depends on $\epsilon$ and $d$ (with bigger $\epsilon$ and smaller $d$ being better if the other parameter is held fixed).

As in my comment, set $X\subset \\{0,1\\}^n$ to be the random strings where our RP algorithm $A(x,r)$ gives false negatives and $Y$ be the complement. Since $G$ is a $(N,d,\epsilon)$-expander with $N = 2^n$, and $|X|\le N/2$ by hypothesis, we know that:

* at least $\epsilon |X| / d$ different vertices in $X$ have a neighbor in $Y$

Notice that this already gives us something, since if we took $\delta = 1$, the improved algorithm now gives a false negative with probability only $1/2 - \epsilon/d$. The question just asks us to be a bit more ambitious.

To this end, define $$ X\_i := \\{r : d(r,Y) \ge i\\} $$ What we just argued was that $|X\_2| \le (1-\epsilon/d)|X|\le (1-\epsilon/d)N/2$. From the way we've defined $X\_i$, we the neighborhood of $X\_i$ is contained in $X\_{i-1}$ for $i\ge 3$. This lets us replay the same argument to show that, for $i\ge 3$ we get $|X\_i|\le (1-\epsilon/d)|X\_{i-1}|$. By induction we then get that $|X\_s|\le (1-\epsilon/d)^{s-1}N/2$.

Finally, observe that the improved algorithm fails when the chosen $r$ is in $X\_{s+1}$. For $s=\Theta\_{\epsilon,d}(\log n)$ this probability is $n^{-c}$.

---
Tags: algorithms, graphs, randomized-algorithms, expanders
---


title: Feynman finite state machine

text:
# Question
Title: Feynman finite state machine
In his lectures on computer science, Feynman talks about finite state machines:

he present a simple delay finite state machine

> Let me now give a specific example of an FSM that actually does something, albeit something pretty trivial - a delay machine. You feed it a stimulus and, after a pause, it responds with the same stimulus. That's all it does. Figure 3.4 shows the "state diagram" of such a delay machine.

I just don't see the utility of using two states here, why not just use a machine with one state?

# Answer
> 7 votes
Your machine outputs the character it just received; Feynman's outputs the previous one.

More specifically, when Feynman's automaton receives the sequence of stimuli $s\_1, s\_2, \dots$, its output is $x, s\_1, s\_2, \dots$, where $x=0$ if the automaton starts in state $1$ and $x=1$, otherwise. Your automaton outputs $s\_1, s\_2, \dots$ given the same sequence of stimuli.

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: Language is recursive, hence recursively enumerable
I was going through a book of proof and I read:

> If L is recursive, L is r.e.

And the proof goes:

* Let L be recursive, hence there is a TM that decides it
* Convert an halt state to a normal state
* Add to program that when it enters this state it goes to infinite loop

How can this be a proof for it?

# Answer
> 5 votes
One possible definition of recursively enumerable (most likely the one used by your instructor) is that it is the domain of a partial function. In Turing Machine terms, that means the following definition:

> A language $L$ is recursively enumerable iff there is a turing machine that halts on input $x$ exactly whenever $x\in L$.

Note that there is no longer any notion of accepting an rejecting state.

Now, assuming that you have a recursive language $L$, you know there is a TM $M$ that always halt on any input $x$ (on the alphabet of $L$), being in an accepting state iff $x\in L$.

To prove that L is RE, you can build a machine $M'$, that will halt exactly on the words $x\in L$. This implies the following step, if you want to be fully formal:

* define the TM $M'$;
* prove that $M'$ halts on all words $x\in L$;
* prove that $M'$ halts only on words $x$ that are in $L$, i.e. does not halt on words $x\notin L$.

Actually, in most proofs of this type, the difficulty is to define (construct) the machine $M'$, while the two other steps are often long and tedious, but not difficult. So it is common to consider that giving the definition is enough of a proof (as long as the definition is correct).

However, that may be unwise, because sometimes the other two steps will uncover errors in the definition provided in the first step. So you are quite correct in asking for a full proof. The definition of $M'$ is not enough for a formal proof, even though it is pretty trivial in the example of your question.

Actually, the construction you give, possibly badly recorded, does contain two error:

* accepting states are not made to loop infinitely;
* accepting states must remain halting states.

Given the TM $M$ that can decide whether a string $x$ belongs to $L$, you define the TM $M'$ as follows:

* convert all non-accepting halting states into states that loop for ever;
* convert all accepting halting states into simple halting states (not really important, but acceptance will be irrelevant, only halting will matter);

Everything remains otherwise the same: same states, same transitions, and you have only added transitions to make the non-accepting halting states go into a loop.

Then, you can prove by induction on the length of a computation (number of transitions), that if $M$ reaches an instantaneous description $d$ on input $x$ in $n$ steps, then $M'$ reaches the same $d$ in input $x$ also in $n$ steps. Whenever $x\in L$, there is a computation of $M$ such that $M$ reaches an instantaneous description with some halting accepting state $q$. Hence, the same computation for $M'$ must reach the same instantaneous description with state $q$, which by construction of $M'$ is still a halting state. Therefore $M'$ is in a halting state.

When $x\notin L$, there is a computation of $M$ such that $M$ reaches an instantaneous description with some halting non-accepting state $q$. Hence, the same computation for $M'$ must reach the same instantaneous description with state $q$, which by construction of $M'$ is a looping state, so that $M'$ will not terminate.

So the TM $M'$ is a machine that does recognize $L$ as an RE set, according to the definition above.

QED

# Answer
> 6 votes
Depending on what definitions you use, the proof can be trivial. We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $S$ and rejects the non-members of $S$. Such a Turing machine is called a *decider* of the set.

One definition of the recursively enumerable sets is that $S$ is RE if there is a Turing machine that accepts every member of $S$ and does not accept any non-member. That is, if $x\notin S$, the machine either rejects it or loops forever. By this definition, it is trivial that every recursive language is RE: the machine that decides the language has the property that it accepts everything in the set and nothing outside it.

The other definition is that a set $S$ is RE if there is a Turing machine that accepts every member of the set and loops forever for every non-member. This appears to be the definition your book is using. Now, suppose you have a machine that decides a set $S$. Modify it so that, instead of rejecting non-members of the set, it loops forever. This gives a machine that accepts every member of $S$ and loops forever for every non-member. This is exactly what you need to conclude that $S$ is RE.

The same idea proves that the two definitions of RE are the same. Any machine that obeys the second definition also obeys the first one (the first says it can either loop or reject for non-members: it happens to loop for all of them but that's a valid choice). Any machine that obeys the first definition can be converted to obey the second by the same trick: replace rejection with looping.

# Answer
> -1 votes
The class R is a proper subset of the class RE and this is just a trivial consequence of the definition of these classes. Basically a Language L is in R iff both L and (not)L are in RE. So if something is in R it must be in RE.In the proof you have presented this idea is illustrated by sort of handicapping the TM by enabling it to satisfy only one of the 'anded' conditions.

---
Tags: computability, turing-machines, semi-decidability
---


title: Searching the space of permutations

text:
# Question
Title: Searching the space of permutations
I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I don't know which one. An oracle however knows the true permutation. To find the true permutation, I'm allowed to query the oracle for pairwise comparison between 2 objects (is a before b in the true permutation?).

A naive strategy would be to do a binary search (ask the "right" pairwise comparison question that eliminates half the permutations at every stage), to find the true permutation in log n steps. My question is, can this always be done? Or can I find an adversarial set of permutations such that O(log n) queries aren't enough.

Edit:
Example: Say my objects are 1,2,3,4. The set of permutations is {1243, 2341, 1342, 3412}. I don't know the true permutation. I ask "Is 2 before 4 in the true permutation?". The oracle returns yes. So I know its among the first two permutations. I then ask "Is 1 before 3 in the true permutation?" to find the true permutation.

# Answer
> 8 votes
Consider the following set of $n$ orders, which I give for $n = 6$: $$ 123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465 $$ Hopefully the generalization to arbitrary $n$ is clear.

If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an argument, but it can be converted to one); this is tight (for this example).

Let me also mention two well-known papers in the area:

1. Fredman showed that if there are $\Gamma$ many possible orderings, then you can find the correct one using $\log\_2 \Gamma + 2n$ queries.
2. Kahn and Kim showed that if the potential orderings constitute all possible orderings extending some partial order, then $O(\log \Gamma)$ queries suffice.

---
Tags: complexity-theory, lower-bounds, search-problem, permutations
---


# Question
Title: Algorithmic type checking for Calculus of Inductive Constructions
So from reading "Advanced Topics in Types and Programming Languages" (ATTPL) I know of the calculus of constructions (CoC). It also presents the "algorithmic" type checking rules. Reading Coq's documentation on the Calculus of Inductive Constructions (CioC) you can get a sense of things but it is far from algorithmic. Is there any reference on algorithmic type checking for CioC?

# Answer
The problem of giving an algorithmic reading to the typing rules in CIC, and dependent type systems in general, is quite subtle.

One recommendation is Randy Pollack's Typechecking in Pure Type Systems, Gille Barthe's Type Checking \*Injective Pure Type Systems and McKinna and Pollack's Pure Type Systems formalized.

The first basic idea is to "push" the conversion rule $$ \frac{\Gamma \vdash t: A\quad A\simeq B}{\Gamma\vdash t : B}$$

into the application rule $$ \frac{\Gamma \vdash t:A\quad \Gamma\vdash u:A' \quad A\simeq \Pi x: A'.B}{\Gamma\vdash t\ u:B\\{x\mapsto u\\}}$$

And similarly for "application-like" rules. The theorem is that these modified rules suffice for type-checking (without conversion), with the exception of a possible single application of conversion at the end.

This makes the rules type-directed, which allows a straightforward implementation. There are additional shortcuts which allow skipping verification of $\mathrm{WF}$, for example, if it is known that it is going to be derived later, or it is admissible.

As Luke notes, there is no complete treatment of such shortcuts, and the validity of these is sometimes quite complicated to prove (e.g. the "expansion postponement" rule).

Checking conversion of terms with $\delta$-reductions (defined functions) is a whole bag of worms: when checking

$$ f\ t\_1\ldots t\_n\simeq f\ u\_1\ldots u\_n$$

should you just check $t\_i\simeq u\_i$ for each $i$, or unfold $f$? The answer is, unsurprisingly, it depends. In general clever heuristics are used, e.g. "unfold $f$ if it is a projection, otherwise try checking equivalence of the arguments, and unfold $f$ if that fails".
> 4 votes

# Answer
The page you link has a series of references just before Section 4.1, and you can't really get better than these.

The inference rules are also given in section 4.2, but for me the formatting seems to have gone haywire, so they're a bit hard to read. Assuming you're comfortable with CoC or $\lambda$-calculus, it should be clear that these give the algorithm (if you're not, then jumping into CoIC or pCoIC may be a bit of an uphill struggle).

Maria João Frade has made some lecture slides available which goes through it with a bit more explanation (the CoIC part is the second section of the slides).

Ultimately though, Bertot and Castéran's book is probably the best reference for understanding CoIC, unless you want to slog through the research papers (having partially done the latter, it's not impossible).
> 3 votes

---
Tags: reference-request, lambda-calculus, type-theory, type-checking, coq
---


# Question
Title: Computer science fields that deal with peer-to-peer systems
I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P technologies have really caught my interest. I have the impression that I need to choose one of the computer science fields to perform my PhD studies in, so now I'm wondering how to do that, given my interest in P2P technologies. Would P2P fall under the area of distributed systems and such? Which fields of computer science are most relevant to P2P systems?

# Answer
> 3 votes
Distributed systems, algorithms and even graph theory are fields that are likely to be relevant.

But, in a sense, "fields" aren't particularly relevant. You don't get a PhD "in a field" but, rather, by finding an advisor who wants to do a research project with you. That person would probably be in one of the fields I've suggested but being in a field isn't a formal status.

# Answer
> 2 votes
Not repeating previous answer.

Security, cryptography, zero knowledge techniques are probably also very relevant. Essentially you should analyze what properties you expect from your P2P system, and that include two kinds:

* properties that you would expect from any implementation of the same service.
* properties that only P2P can provide.

Typically, many services can be fully centralized, but that gives too much power to whomever can access all the data. Possibly P2P can avoid that. At what cost?

Identifying the questions you might have, and the way they were so far addressed may help you identify relevant fields. Look at all existing P2P systems.

For example, the first one may have been Internet TCP/IP. What did it rely on? I would guess that probability theory has some part in it. What else?

And if you manage to produce a working P2P search engine that is competitive, I hope they give you two PhDs for the price of one.

---
Tags: distributed-systems, research
---