# Question
Title: Ordering elements so that some elements don't come between others
Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \\{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\\},$$ find an algorithm which either finds a permutation $\pi$ of the set $\\{1, 2, \dots, n\\}$ such that $$(i,j,k) \in S \implies (\pi(j)\<\pi(i)\<\pi(k)) ~\lor~ (\pi(i)\<\pi(k)\<\pi(j))$$ or correctly determines that no such permutation exists. Less formally, we want to reorder the numbers 1 through $n$; each triple $(i,j,k)$ in $S$ indicates that $i$ must appear before $k$ in the new order, but $j$ must not appear between $i$ and $k$.

**Example 1**

Suppose $n=5$ and $S = \\{(1,2,3), (2,3,4)\\}$. Then

* $\pi = (5, 4, 3, 2, 1)$ is *not* a valid permutation, because $(1, 2, 3)\in S$, but $\pi(1) \> \pi(3)$.
* $\pi = (1, 2, 4, 5, 3)$ is *not* a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1) \< \pi(3) \< \pi(5)$.
* $(2, 4, 1, 3, 5)$ is a valid permutation.

**Example 2**

If $n=5$ and $S = \\{(1, 2, 3), (2, 1, 3)\\}$, there is no valid permutation. Similarly, there is no valid permutation if $n=5$ and $S = \\{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\\}$ (I think; may have made a mistake here).

*Bonus: What properties of $S$ determine whether a feasible solution exists?*

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

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

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

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

# Answer
Here is a partial answer:

If you remove the constraint $ i \lt k$ on each triple then your problem becomes the Non-Betweeness problem which is $NP$-complete and there are no known efficient algorithms for such problems. But with $i \lt k$ constraint, it may force some nice structure which can be exploited to find a polynomial time algorithm for your problem.
> 1 votes

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: What is a good reference to learn about state transition systems?
I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but failed to do so.

Does anybody know a modern introduction to the topic? Of particular interest would be something dealing with computability.

# Answer
One of the key uses of state transition systems, also known as labelled transition systems, is for modelling concurrent systems.

One very nice, delightful even, book that uses labelled transition systems to give semantics to concurrent formalisms CCS and the $\pi$-calculus is *Communicating and Mobile Systems: the Pi-Calculus* by Robin Milner. Definitely worth reading.

*Principles of Model Checking* by Christel Baier and Joost-Pieter Katoen is about model checking concurrent systems, so early in the book labelled transition systems are introduced to give semantics to such systems. This book also talks about probabilistic labelled transitions too.

Another possibility is *Concurrency: State Models & Java Programs* by Jeff Magee & Jeff Kramer. This book takes a more practical approach, but comes with an analyzer for systems described using labelled transition systems.

I don't know much about continuous dynamic systems. Perhaps you want to look at hybrid systems?
> 6 votes

---
Tags: computability, automata, reference-request, computation-models
---


title: Modified Djikstra's algorithm

text:
# Question
Title: Modified Djikstra's algorithm
So, I'm trying to conceptualize something:

Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:

1. movements on the graph are regulated by a circular cycle of length 48, in such a manner that:

> cycle{
>
> ```
>      0 <= L <= 24  movement IS possible
>
>     25 <= L <= 48 movement IS NOT possible
>
> ```
>
> }

For simplicity's sake, we will call this cycle 'time'.
2. The distance between nodes A and B is equal to:

> shortest\_distance(A to B) - 1 OR shortest\_distance(A to B) + 1

Depending on their orientation
3. the weight of the edges represents the 'time' it takes to travel between nodes.

I'd like to create an algorithm that will give me the shortest path with these constraints in mind, assuming one is leaving from node A at time(cycle) = 12, traveling towards node B. The shortest path would be defined as the path which takes the least 'time'.

Step one would obviously be to take into account the orientation affecting the shortest distance (i.e. which way are they oriented by above), which would be a simple addition or substraction to the result of djikstra's algorithm

What I'm having trouble figuring out is how to account for the cycle in the algorithm... could it be as simple as just an if statement checking to see if the current cycle time is within the constraints that allow movement?

Would my idea be viable? If not, does anyone h ave any suggestions at different ways I should look at this problem?

I know this question seems really basic, but I just can't wrap my head around it.

# Answer
> 3 votes
I didn't really understand your problem description, but if you go by the timezone analogy, the only thing stopping you from using Djikstra's algorithm are the negative costs on some edges (ie.: some edges go back in time). If this is the problem, you can get around it by using an alternate algorithm that can handle negative edges, like Bellman-Ford

---
Tags: algorithms, graphs, shortest-path
---


title: $\log^*(n)$ runtime analysis

text:
# Question
Title: $\log^*(n)$ runtime analysis
So I know that $\log^\*$ means iterated logarithm, so $\log^\*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$.

I'm trying to solve the following:

is

> $\log^\*(2^{2^n})$

little $o$, little $\omega$, or $\Theta$ of

> ${\log^\*(n)}^2$

In terms of the interior functions, $\log^\*(2^{2^n})$ is much bigger than $\log^\*(n)$, but squaring the $\log^\*(n)$ is throwing me off.

I know that $\log(n)^2$ is $O(n)$, but I don't think that property holds for the iterative logarithm.

I tried applying the master method, but I'm having trouble with the properties of a $\log^\*(n)$ function. I tried setting n to be max (i.e. $n = 5$), but this didn't really simplify the problem.

Does anyone have any tips as to how I should approach this?

# Answer
> 14 votes
Recall that for $k \> 1$, by definition we have $\log^\*k = \log^\*(\log{k}) + 1$.

By applying the definition twice, we see that $\log^\*(2^{2^n}) = \log^\*n + 2$. Now we can compare $\log^\*n + 2$ and $(\log^\*n)^2$.

# Answer
> 2 votes
Let's write it out and see what we get. To track the number of logs, I'll subscript them; I know that's usually base, if anyone has a better idea let me know or edit it in:

$$ \log^\*(2^{2^n}) \\ = \log\_1(\log\_2(...\log\_k(2^{2^n})...)) \\ = \log\_1...\log\_{k-1}(2^n\log\_{k}(2)) \\ = \log\_1...\log\_{k-2}(\log\_{k-1}(2^n)+\log\_{k-1}\log\_{k}(2))) \\ = \log\_1...\log\_{k-2}(n\log\_{k-1}(2)+\log\_{k-1}\log\_{k}(2))) \\ \approx \log\_1...\log\_{k-2}(n\log\_{k-1}(2)) \\ = \log\_1...\log\_{k-2}(n+\log\_{k-1}(2)) \\ \approx \log\_1...\log\_{k-2}(n) \\ $$ Since we're looking for large $n$, I've dropped the additive terms $\log(\log(2))\approx-0.3665$ and $\log(2)\approx0.693$.

This shows that if $\log^\*(2^{2^n}) = k$, then $log^\*(n) \approx k-2$, or combining these, $$ \log^\*(2^{2^n}) \approx \log^\*(n)+2 $$

The big-$\Theta$s are identical, and as pointed out in the comments, if the base of the logarithm and the power are the same, the equations are identically equal.

---
Tags: asymptotics, landau-notation, mathematical-analysis
---


title: Randomized Selection

text:
# Question
Title: Randomized Selection
The randomized selection algorithm is the following:

Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in \[n\]$

Output: The the "rank $k$ element" of $A$ (i.e., the one in position $k$ if $A$ was sorted)

Method:

* If there is one element in $A$, return it
* Select an element $p$ (the "pivot") uniformly at random
* Compute the sets $L = \\{a\in A : a \< p\\}$ and $R = \\{a\in A : a \> p\\}$
* If $|L| \ge k$, return the rank $k$ element of $L$.
* Otherwise, return the rank $k - |L|$ element of $R$

I was asked the following question:

> Suppose that $k=n/2$, so you are looking for the median, and let $\alpha\in (1/2,1)$ be a constant. What is the probability that, at the first recursive call, the set containing the median has size at most $\alpha n$?

I was told that the answer is $2\alpha - 1$, with the justification "The pivot selected should lie between $1−\alpha$ and $\alpha$ times the original array"

Why? As $\alpha \in (0.5, 1)$, whatever element is chosen as pivot is either larger or smaller than more than half the original elements. The median always lies in the larger subarray, because the elements in the partitioned subarray are always less than the pivot.

If the pivot lies in the first half of the original array (less than half of them), the median will surely be in the second larger half, because once the median is found, it must be in the middle position of the array, and everything before the pivot is smaller as stated above.

If the pivot lies in the second half of the original array (more than half of the elements), the median will surely first larger half, for the same reason, everything before the pivot is considered smaller.

Example:

3 4 5 8 7 9 2 1 6 10

The median is 5.

Supposed the chosen pivot is 2. So after the first iteration, it becomes:

1 2 ....bigger part....

Only `1` and `2` are swapped after the first iteration. Number 5 (the median) is still in the first greater half (accroding to the pivot 2). The point is, median always lies on greater half, how can it have a chance to stay in a smaller subarray?

# Answer
Suppose your array has $n$ elements. As you have noted, the median is always in the bigger part after the first partition. The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$. This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements. Because $\alpha \> 1/2$, you know these are disjoint sets, so the probability of hitting one of the bad pivots is just $2 - 2\alpha$, and $1- 2 + 2\alpha=2\alpha - 1$.
> 12 votes

---
Tags: algorithms, algorithm-analysis, probability-theory, randomized-algorithms
---


# Question
Title: What is a formula for the number of strings with no repeats?
I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1\< |t| \< |s|$, there is no disjoint copy of $t$ in $s$. For exapmle, let $A=\\{a,b\\}$. Then $aaa$ *is* one of the strings I want to count, since for the substring $aa$, there are no disjoint copies. However, $abab$ contains such a repeat.

If someone's already figured out a useful formula, please link. Otherwise, I will refer back to this post in any article I write, if I use someone's answer.

Here is another example. Let's try to construct a long string over $\\{a,b\\}$, that contains no repeats:

aaa (can't be a)
aaab (a or b)
aaabbb (can't be b)
aaabbba (can't be b or a)
aaaba (can't be a or b)

If we built a tree, we could count the number of nodes, but I want a formula.

**Edit:** Well, it's not as daunting as I first thought if we convert this to a bin-choosing problem. A set of strings of length k with at least one repeat is equal to the set that is the union of all permutations of the cartesian product: $A \times A \times \cdots\times A \text{(k-4 times)} \times R \times R$ where $R$ is the required repeat. I don't know if that's helpful, but it sounded pro :) Anyway, let their be |A| bins, choose any two (even if the same one) to be the repeat, then choose $k-4$ more and multiply (the first 4 are already chosen, see?). Now I just need to find that formula from discrete math.

# Answer
*This answers the question after the number of repeat-free words per size, implying that the desired quantity even exists.*

**Definition:** Call $w \in \Sigma$ *repeat-free* if and only if it does not contain a factor $xyx$ with $x \in \Sigma^{\geq 2}$ and $y \in \Sigma^\*$.

**Claim:** For given finite alphabet $\Sigma$ with $|\Sigma| = k$, there are no repeat-free words of length greater than $2k^2 + 1$.

**Proof Idea:** By pigeon-hole principle. Take a word $w$ of length $2k^2 + 2$ (or a longer word and consider its prefix of this length), i.e. $w = a\_0a\_0' \dots a\_{k^2}a\_{k^2}'$. Assume $w$ is repeat-free; that means that $a\_ia\_i' \neq a\_ja\_j'$ for all $i \neq j$ (otherwise we had a repeat). Therefore, there are $k^2 + 1$ many pairs of symbols; this contradicts $|\Sigma^2| = k^2$. So $w$ is not repeat-free. $\square$

Note that this is a rough proof: factors $a\_i'a\_{i+1}$ might create a repeat even sooner.

---

*Notation:*

* $\Sigma^{\geq k} = \bigcup\_{i=k}^\infty \Sigma^i = \Sigma^\* \setminus \bigcup\_{i=0}^{k-1} \Sigma^i$
* "factor" = "subword" = "substring"
> 1 votes

---
Tags: formal-languages, combinatorics, strings, word-combinatorics
---


title: Complexity of 3SAT variants

text:
# Question
Title: Complexity of 3SAT variants
This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order such that the betweeness constraint of each triple is enforced while in the later problem there is a total order such that the betweeness constraint of each triple is violated.

What is the complexity of the following 3SAT variants?:

3SAT\_1={($\phi$): $\phi$ has an assignment that makes every clause false}

3SAT\_2={($\phi$): $\phi$ has an assignment such that exactly half of the clauses are true and the other half is false}

# Answer
3SAT\_1 is easy, and a variant of 3SAT\_2 is NP-complete. My guess is that 3SAT\_2 is also NP-complete. Update: my guess is proved below.

Let $C = x\lor y\lor z$ be a clause. Then $\lnot C = \lnot x \land \lnot y \land \lnot z$. An assignment makes every clause of $\phi$ false if it makes all their negations true. The conjunction of the negation of all clauses is just a big conjunction. A conjunction is satisfiable if and only if it does not contain a variable and its negation. So 3SAT\_1 is in P (in fact it's in AC$^0$).

The variant of 3SAT\_2 asks whether $\phi$ has an assignment that makes exactly $8/9$ of the clauses true. This is clearly in NP. To reduce 3SAT to this variant, take the formula $\phi$, and for each clause $C$ in $\phi$ add the eight clauses $$(x\_C \lor y\_C \lor z\_C) \land \cdots \land (\lnot x\_C \lor \lnot y\_C \lor \lnot z\_C).$$ In any assignment, exactly seven of these are correct. In total we have $9|\phi|$ clauses. Of the $8|\phi|$ that we added, exactly $7|\phi|$ are always correct. Hence $\phi$ is satisfiable if and only if in the new formula one can satisfy exactly $8|\phi|$ constraints, which are $8/9$ of its clauses.

Update: Here is a reduction from 3SAT to 3SAT\_2 itself. Given a formula $\phi$, consider two cases. The first case is when we can falsify all clauses in $\phi$ at once. As shown above, in this case each variable appears only positively or only negatively, and so setting it appropriately, the formula is satisfiable. Otherwise, add $|\phi|$ clauses of the form $x \lor y \lor z$, where $x,y,z$ are new variables. In any assignment either all of these are satisfied, or all are not satisfied. Since the original clauses cannot be all falsified at once (by assumption), the new formula can be half-satisfied if and only if the original one is satisfiable.
> 10 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Sharp concentration for selection via random partitioning?
The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:

* Sample $n^{3/4}$ elements from $A$ with replacement into $B$
* Sort $B$ and find the rank $|B|\pm \sqrt{n}$ elements $l$ and $r$ of $B$
* Check that $l$ and $r$ are on opposite sides of the median of $A$ and that there are at most $C\sqrt{n}$ elements in $A$ between $l$ and $r$ for some appropriate constant $C \> 0$. Fail if this doesn't happen.
* Otherwise, find the median by sorting the elements of $A$ between $l$ and $r$

It's not hard to see that this runs in linear time and that it succeeds with high probability. (All the bad events are large deviations away from the expectation of a binomial.)

An alternate algorithm for the same problem, which is more natural to teach to students who have seen quick sort is the one described here: Randomized Selection

It is also easy to see that this one has linear expected running time: say that a "round" is a sequence of recursive calls that ends when one gives a 1/4-3/4 split, and then observe that the expected length of a round is at most 2. (In the first draw of a round, the probability of getting a good split is 1/2 and then after actually increases, as the algorithm was described so round length is dominated by a geometric random variable.)

So now the question:

> Is it possible to show that randomized selection runs in linear time with high probability?

We have $O(\log n)$ rounds, and each round has length at least $k$ with probability at most $2^{-k+1}$, so a union bound gives that the running time is $O(n\log\log n)$ with probability $1-1/O(\log n)$.

This is kind of unsatisfying, but is it actually the truth?

# Answer
> 5 votes
It's not true that the algorithm runs in linear time with high probability. Considering only the first round, the running time is at least $\Theta(n)$ times a $G(1/2)$ random variable. Let $p(n) \longrightarrow 0$ be the allowed failure probability. Since $\Pr\[G(1/2) \geq \log\_2 p(n)^{-1}\] = p(n)$, the running time is at least $\Omega(n \log\_2 p(n)^{-1}) = \omega(n)$.

(There is some cheating involved, since the length of the first round isn't really $G(1/2)$. More careful analysis might or might not validate this answer.)

Edit: Grübel and Rosler proved that the expected number of comparisons divided by $n$ tends (in some sense) to some limit distribution, which is unbounded. See for example Grübel's paper "Hoare's selection algorithm: a Markov chain approach", which references their original paper.

---
Tags: algorithms, algorithm-analysis, randomized-algorithms
---


# Question
Title: Constraint-based Type Inference with Algebraic Data
I am working on an expression based language of ML genealogy, so it naturally needs type inference \>:)

Now, I am trying to extend a constraint-based solution to the problem of inferring types, based on a simple implementation in EOPL (Friedman and Wand), but they elegantly side-step algebraic datatypes.

What I have so far works smoothly; if an expression `e` is `a + b`, `e : Int`, `a : Int` and `b : Int`. If `e` is a match,

```
match n with
  | 0 -> 1
  | n' -> n' * fac(n - 1)`,

```

I can rightly infer that the `t(e) = t(the whole match expression)`, `t(n) = t(0) = t(n')`, `t(match) = t(1) = t(n' * fac(n - 1)` and so on...

But I am very unsure when it comes to algebraic datatypes. Suppose a function like filter:

```
let filter pred list =
  match list with
    | Empty -> Empty
    | Cons(e, ls') when pred e -> Cons (e, filter ls')
    | Cons(_, ls') -> filter

```

For the list type to remain polymorphic, Cons needs to be of type `a * a list -> a list`. So, in establishing these constraints, I obviously need to look up these types of my algebraic constructors - the problem I now have is the 'context-sensitivity' of multiple uses of algebraic constructors - how do I express in my constraint equations that the `a` in each case needs to be the same?

I am having trouble finding a general solution to this, and I am unable to find much literature on this. Whenever I find something similar - expression based language with constraint-based type inference - they stop just short of algebraic datatypes and polymorphism.

Any input is much appreciated!

# Answer
> 2 votes
See: Mini ML Specifically the Type Inference section.

This contains sample code in F# for a complete parser of a simple functional language. More importantly the Type Inference section implements the Hindley-Milner algorithm which is what is found in most type inference system. The author also provides links to two other important documents to help in understanding Hindley-Milner; one being a kind of high level introduction and the other being a paper that describes the implementation of the algorithm in code.

---
Tags: programming-languages, type-theory, functional-programming, inductive-datatypes, typing
---


# Question
Title: Lower bound for finding kth smallest element using adversary arguments
In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument?

Wikipedia says that tournament algorithm runs in $O(n+k\log n)$, and $n - k + \sum\_{j = n+2-k}^{n} \lceil{\operatorname{lg}\\, j}\rceil$ is given as lower bound.

# Answer
I am going to briefly outline a sketch of an adversary argument.

Consider your selection algorithm playing against an opponent that we will call the adversary.The aim of the adversary is to provide an input $X$ for your algorithm that maximizes the number of comparison operations done by your algorithm. Indeed, your algorithm can be seen as a comparison tree, in which a path corresponds to a partial order. When the algorithm asks the adversary about a pair $(x, y)$ of elements, the adversary returns either $x \< y$ or $y \< x$. The adversary answers can never contradict previous outcomes.

Assume that the $k$-th largest element is $x^\*$: considering the partial order associated to any leaf of the comparison tree, then $x^\*$ must be comparable with every other element in order for the algorithm to be correct, so that the algorithm must have made at least one comparison $(y, z)$ $\forall y \neq x^\*$ whose outcome is either $y \< z \leq x^\*$ or $x^\* \leq z \< y$. Call such a comparison *crucial* for an element $y$. Obviously, the adversary wants to maximize the number of non crucial comparisons done by your algorithm.

Let $L$ be the set of $k−1$ largest elements; your algorithm needs to correctly identify all of the elements in $L$ and also the largest element in $X \setminus L$, i.e. $x^\*$. Observe that each element in $X \setminus L$ has lost at least one crucial comparison. Now, the adversary has a strategy that forces each of the $k - 1$ elements in $L$ to win at least $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$ comparisons, none of which is crucial for $X \setminus L$. Adding the remaining $n - k$ crucial comparisons for $X \setminus L$ you obtain the lower bound. For details, please read the following, excellent, Jeff Erikson notes.
> 8 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Showing that a problem in X is not X-Complete
The Existential Theory of the Reals is in **PSPACE**, but I don't know whether it is **PSPACE-Complete**. If I believe that it is not the case, how could I prove it?

More generally, given a problem in some complexity class **X**, how can I show that it is *not* **X-Complete**? For example, **X** could be **NP**, **PSPACE**, **EXPTIME**.

# Answer
Actually proving $X$ is not $PSPACE$-complete (under, say, polynomial-time reductions) would be extremely hard to do.

If $P=PSPACE$, then all non-trivial (i.e., not $\varnothing$ and not $\Sigma^{\star}$) and infinite problems in $PSPACE$ are $PSPACE$-complete under polynomial-time reductions. Since the existential theory of the reals has this non-trivial and infinite property, proving that it *isn't* $PSPACE$-complete would imply $P \neq PSPACE$. (See the answer to this question on CSTheory.SE for a sketch of the proof.)
> 16 votes

# Answer
A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.
> 11 votes

# Answer
Look at the accepted answer for this question on MathOverflow, What techniques exist to show that a problem is not NP-complete?. It answers the case when X=NP.
> 3 votes

# Answer
As Ryan wrote, proving that a problem is not hard is not easy.

Let $Q$ be a problem in a complexity class $X$ and $S$ is closed w.r.t. $\leq$ reductions. Proving that $Q$ is not $X$-hard w.r.t. $\leq$ is equivalent to separating the complexity class obtained by taking closure of $Q$ w.r.t. $\leq$. Now, if $Q$ is hard for another class $Y$ w.r.t. $\leq$, then it means separating $Y$ from $X$. As you know, there aren't many separation results.

In your case, $X = \mathsf{PSpace}$, $\leq = \leq^\mathsf{P}\_m$, and $Y=\mathsf{P}$.

Because we can't prove such results at the moment (with the possible exception of Ryan :), in place of proving that $Q$ is not $X$-hard, we show that it is in a complexity class that is *believed* to be smaller than $X$. For example, if you show that $\mathrm{Th}\_\exists(\mathbb{R,+,\times,0,1})$ is in $\mathsf{PH}$, then it will be taken as a strong evidence for $Q$ not being $X$-hard. (In logicians' language, if you can't prove an unconditional result, try proving a conditional one assuming a hard to prove but widely believed statement like $\mathsf{P}\neq\mathsf{PSpace}$).
> 3 votes

---
Tags: complexity-theory, proof-techniques
---


title: What is co-something?

text:
# Question
Title: What is co-something?
What does the notation `co-` mean when prefixing `co-NP`, `co-RE` (recursively enumerable), or `co-CE` (computably enumerable) ?

# Answer
> 11 votes
Often, in mathematical terminology, the prefix *co-* refers to a dual in some sense. For complexity and computability classes, the prefix *co-* has a fixed meaning: if *X* is a class of decision problems, then *co-X* is the class of problems whose complement is in *X*. That is, if the problem “does this object have the property $P$” is in *X*, then the problem “does this object have the property $\neg P$?” is in *co-X*.

For example, RE is the class of semi-decidable problems, that is, problems for which there is a Turing machine that can verify a positive answer. Co-RE is the class of problems for which there is a Turing machine that can verify a negative answer. A well-known problem that is in RE but not in co-RE is the halting problem (intuitively, you can verify that a Turing machine halts by running it to completion, but if the machine runs forever, you'll never be sure).

NP is the class of problems for which a solution can be verified in polynomial time; equivalently, NP is the class of problems that can be solved by a non-deterministic Turing machine in polynomial time. Co-NP is the class of problems for which the absence of a solution can be proved in polynomial time. It is not known whether $\text{NP} = \text{co-NP}$.

# Answer
> 5 votes
In the more algebraic side of theoretical computer science, co- means dual, as in Gilles' answer, but it has a very precise interpretation. If the concept of interest (let's say *a product*) is formalised in Category Theory, then the dual (a *coproduct*) is the same concepts with the arrows going in the opposite direction.

A simple example (yet abstract) is the idea of an *algebra*, which, for a functor $F$, is a pair $\langle S,\alpha:FS\to S\rangle$. Algebras are important in computer science for modelling data types. The dual of an algebra is a *coalgebra*, which is a pair $\langle S,\alpha:S\to FS\rangle$. Coalgebras are important for modelling systems.

What happened when we dualized? Well, the arrow $FS\to S$ was reversed, obtaining $S\to FS$.

One of the cool things about this idea is that all of the theory that works for one concept works for the dual concept, where all of the arrows are reversed.

---
Tags: complexity-theory, computability, terminology
---


title: Quicksort explained to kids

text:
# Question
Title: Quicksort explained to kids
Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper.

Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or at least handwave) that the average complexity is $O(n \log n)$, and what the best and the worst cases are, to a kindergarden class? Or at least in primary school?

# Answer
At its core, Quicksort is this:

1. Take the first item.
2. Move everything less than that first item to the left of it, everything greater to the right (assuming ascending order).
3. Recurse on each side.

I think every 4-year-old on the planet could do 1 and 2. The recursion might take a little bit more explanation, but shouldn't be that hard for them.

1. Repeat on the left side, ignoring the right for now (but remember where the middle was)
2. Keep repeating with the left sides until you get to nothing. Now go back to the last right side you ignored, and repeat the process there.
3. Once you run out of right and left sides, you're done.

As for the complexity, worst-case should be fairly easy. Just consider an already-sorted array:

```
1 2 3 4
  2 3 4
    3 4
      4

```

Fairly easy to see (and prove) that it's $\frac{1}{2}n^2$.

I'm not familiar with the average-case proof, so I can't really make a suggestion for that. You could say that in an unsorted array of length $l$ the probability of picking the smallest or largest item is $\frac{2}{n}$, so...?
> 14 votes

# Answer
Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2. Make a bunch of X flash cards, number them 1--X, and shuffle it. Then here's the explanation:

> OK, we've got this deck of (let's say 20) cards here. We want to put them in order, so 1 is first, then 2, then 3, and so on. Here's a very quick way to do it.
>
> First, let's go through this deck and make two piles out of it. Half of 20 is 10, so anything bigger than 10 goes in this pile on the right, and anything smaller goes in this pile on the left. (Make sure to demonstrate as you go.)
>
> Now, let's do the same thing with the smaller piles. What's half of 10? (Someone says "five!") That's right! So anything bigger than 5 goes in this pile on the right, and anything smaller goes in this pile on the left.
>
> And over here, we've got the group that's bigger than 10. So half of 10 is 5, and what's 10 plus 5? (Someone says "fifteen!") That's right! So anything bigger than 15 goes in this pile on the right, and anything smaller than 15 goes in this pile on the left.
>
> And now the piles are getting small enough that you can easily look at them and put them in order. Look, here we've got `2, 4, 5, 3, 1`. So we just switch them around like this, and you can see `1, 2, 3, 4, 5`. So let's do the same thing with the other piles, and then we just put the piles in order, and look! They're in order from 1 to 20!

Congratulations. You've just taught a bunch of children the basic principles of an adaptive quicksort algorithm! You can go a bit deeper than that depending on mental maturity, but going much further beyond this point requires some understanding of formal logic.

As for proving its complexity, that's trickier. It's one of the things that requires formal logic, and they'll have to understand the basic principles of big-O notation in the first place. You might want to hold off on that part at first.
> 16 votes

# Answer
How about this?

Computer Science Unplugged - Sorting Algorithms

It doesn't quite cover all your questions, but it's a good start.

More resources on this topic are linked here.

They also made a video available that explains sorting algorithms (quicksort included) here. This video really helps understand the difference between the different sorting algorithms for young kids.
> 2 votes

# Answer
See the graphical loveliness of this little demo.

.
> 1 votes

---
Tags: algorithms, education, algorithm-analysis, didactics, sorting
---


# Question
Title: How to represent the interests of a Facebook user
I'm trying to figure out a way I could represent a Facebook user as a vector. I decided to go with stacking the different attributes/parameters of the user into one big vector (i.e. age is a vector of size 100, where 100 is the maximum age you can have, if you are lets say 50, the first 50 values of the vector would be 1 just like a thermometer).

Now I want to represent the Facebook interests as a vector too, and I just can't figure out a way. They are a collection of words and the space that represents all the words is huge, I can't go for a model like a bag of words or something similar. How should I proceed? I'm still new to this, any reference would be highly appreciated.

# Answer
> 4 votes
The interests are categorical data and may be modeled as binary variables (a user either likes them or he does not). You can subsume little-used categories under broader categories. For example, a user who likes a little-known horror movie can simply be marked as liking horror movies. You can even subsume such items under multiple categories if it belongs to several.

For what you can do with the data see A Review on Data Clustering Algorithms for Mixed Data

---
Tags: machine-learning, modelling, social-networks, knowledge-representation
---


title: Rectangle Coverage by Sweep Line

text:
# Question
Title: Rectangle Coverage by Sweep Line
I am given an exercise unfortunately I didn't succeed by myself.

> There is a set of rectangles $R\_{1}..R\_{n}$ and a rectangle $R\_{0}$. Using plane sweeping algorithm determine if $R\_{0}$ is completely covered by the set of $R\_{1}..R\_{n}$.

For more details about the principle of sweep line algorithms see here.

Let's start from the beginning. Initially we know sweep line algorithm as the algorithm for finding line segment intersectionswhich requires two data structures:

* a set $Q$ of event points (it stores endpoints of segments and intersections points)
* a status $T$ (dynamic structure for the set of segments the sweep line intersecting)

**The General Idea:** assume that sweep line $l$ is a vertical line that starts approaching the set of rectangles from the left. Sort all $x$ coordinates of rectangles and store them in $Q$ in increasing order - should take $O(n\log n)$. Start from the first event point, for every point determine the set of rectangles that intersect at given $x$ coordinate, identify continuous segments of intersection rectangles and check if they cover $R\_{0}$ completely at current $x$ coordinate. With $T$ as a binary tree it's gonna take $O(\log n)$. If any part of $R\_{0}$ remains uncovered that $R\_{0}$ is not completely covered.

**Details:** The idea of segment intersection algorithm was that only adjacent segments intersect. Based on this fact we built status $T$ and maintained it throughout the algorithm. I tried to find a similar idea in this case and so far with no success, the only thing I can say is two rectangles intersect if their corresponding $x$ and $y$ coordinates overlap.

The problem is how to build and maintain $T$, and what the complexity of building and maintain $T$ is. I assume that R trees can be very useful in this case, but as I found it's very difficult to determine the minimum bounding rectangle using R trees.

Do you have any idea about how to solve this problem, and particularly how to build $T$?

# Answer
> 6 votes
Let's start with $n$ axis-aligned rectangles, since there is a kind of easy direct argument. We'll sweep a vertical line. The events are the endpoints of horizontal edges of the rectangles. As we sweep we maintain a set of intervals on the sweep line that are "uncovered" by $R\_i$, $i\ge 1$:

* Add the vertical interval covered by the rectangle $R\_i$ to the sweep line when we first encounter $R\_i$
* Remove the vertical interval covered by the rectangle $R\_i$ from the sweep line when it moves past $R\_i$

It's easy to do this with a binary tree so that updates take $O(\log n)$ time. (The problem is, essentially, 1-dimensional. You figure out if the endpoints are in an uncovered interval and extend/merge appropriately when adding and lengthen them when removing.)

Then you just check that, in the span of $R\_0$, none of the uncovered intervals ever intersect the vertical span of $R\_0$. The whole thing is $O(n\log n)$ time an $O(n)$ space.

For the general case, the obvious trick is not quite so fast. Use the standard sweep line algorithm to compute the whole planar subdivision induced by the rectangles.

Clearly some disk-like set $F'$ of the faces covers $R\_0$. By itself, this doesn't tell us enough, since what we are interested in is whether any of these faces is inside $R\_0$ and outside the other rectangles. To do this, we modify the construction a little bit, so that when we add an edge, we tag one side with the identity of the rectangle it's inside. This adds $O(1)$ overhead, so the construction is $O(n^2\log n)$ time; with no assumptions on the rectangles, the output can be $\Omega(n^2)$ in size, so we are using that much space in the worst case, so the time is, "existentially optimal" though not "output sensitive".

Finally, $R\_0$ is covered so long as none of the faces in $F'$ have only edges not tagged as being in one of the $R\_i$. The point is that if an edge of $f$ is in $R\_i$, then the whole of $f$ is as well. Imagine sweeping a line over $f$ orthogonally along this edge: it can only leave $R\_i$ either outside of $f$ or $f$ is bounded by more than one edge of $R\_i$.

So the conclusion is that the special case is $O(n\log n)$ and the general one is $O(n^2\log n)$ at least, but I suspect it can be improved.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Complexity of an optimisation problem in 3D
I have a collection $P \subseteq \mathbb{R}^3$ of $N$ particles and there is a function $f : P^2 \to \mathbb{R}$. I want to find which configuration of the system minimizes the value of $f$.

Can this problem (or similar ones) be reduced to TSP? Could you point me to literature on the topic?

In my application, $f$ is the atomic van der waals force, which for each pair of particles of atoms is attractive or repulsive depending on some predefined thresholds.

In addition, it would be great to have a list of concrete examples of problems that can be reduced to TSP.

# Answer
> 8 votes
Since TSP is NP-complete, most problems you'll encounter in practice can be. (NP is a pretty general class.) A classic paper of Karp gives a large number of other NP-complete problems that, by definition, can be reduced to TSP.

# Answer
> 6 votes
A decision variant of the problem might be:

> Does there exist a configuration of the system such that the objective function assumes a value less than or equal to $y\_0$?

It depends entirely upon the form of the objective function. Suppose that the objective function is constant, i.e., $f(x) = c$. Then a constant-time algorithm which solves the decision problem is to return $yes$ iff $c \le y\_0$.

Suppose instead that $f(x)$ returns 0 if the Turing machine encoded by $x$ (according to some encoding scheme) halts on itself as input, and 1 otherwise. Then the decision problem is undecidable, since it would allow you to solve the Halting problem; in particular, it is not reducible to TSP.

(*Note: in order for the above to create a Halting-Problem scenario, there would need to be some restrictions on the allowed configurations, so that - for instance - only one configuration were possible. This could easily be encoded by the $f$; make all but exactly one configuration result in $f(x) = +\infty$*)

---
Tags: complexity-theory, optimization, search-problem
---


# Question
Title: Maintaining search indices with binary trees
There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.

For each word initially I am creating a separate file. Consider 2 documents:

* document 1: “The Problem of Programming Communication with”
* document 2: “Programming of Arithmetic Operations”

Here, there are 10 words, 8 unique. So I create 8 files (`the`, `problem`, `of`, `programming`, `communications`, `with`, `arithmetic`, `operations`).

In each file, I will store at which document they appear and at what position. The actual structure I am implementing has lot more information but this basic structure will serve the purpose.

```
file name        file content
the              1 1
problem          1 2
of               1 3 2 2
programming      1 4 2 1
communications   1 5
with             1 6
arithmetic       2 3
operations       2 4

```

Meaning. the word is located at document 1, position 3 and at document 2, position 2.

After the initial index is done I will concatenate all the files into a single index file and in another file I store the offset where a particular word will be found.

index file: `1 1 1 2 1 3 2 2 1 4 2 1 1 5 1 6 2 3 2 4`
offset file: `the 1 problem 3 of 5 programming 9 communications 13 with 15 arithmetic 17 operations 19`

So if I need the index information for `communications`, I will go to position 13 of the file and read up to position 15 excluded, in other words the offset of the next word.

This is all fine for static indexing. But if I change a single index the whole file will need to be rewritten. Can I use a binary tree as the index file's structure, so that I can dynamically change the file content and update the offset somehow ?

# Answer
> if I change a single index the whole file will need to be rewritten

So don't change indices. When you add data, remember what words already existed, and store subsequent words afterward. For each word, instead of storing one index in the index file, store several.

There is a lot to optimize on top of that. But I don't think this is a productive use of your time. There are existing programs that can do this (and far more complex use cases, too) very efficiently and without raising a sweat: databases. Use a database engine (Berkeley DB, SQlite, NoSQL, MySQL, TSQL, …).

If you want to understand how to store this kind of data efficiently, read about implementations of database engines. B-trees will be involved at some point.
> 5 votes

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


# Question
Title: Extending the implementation of a Queue using a circular array
I'm doing some exam (Java-based algorithmics) revision and have been given the question:

> Describe how you might extend your implementation \[of a queue using a circular array\] to support the expansion of the Queue to allow it to store more data items.

The Queue started off implemented as an array with a fixed maximum size. I've got two current answers to this, but I'm not sure either are correct:

1. Implement the Queue using the Java Vector class as the underlying array structure. The Vector class is similar to arrays, but a Vector can be resized at any time whereas an array's size is fixed when the array is created.
2. Copy all entries into a larger array.

Is there anything obvious I'm missing?

# Answer
> 3 votes
Using the `Vector` class is certainly a possibility, as a practical matter. Other solutions will amount to implementing functionality that is similar to what the `Vector` class provides (possibly in a way that is more efficient given that the data structure stores a queue).

Some languages offer inherently resizable arrays. For example, in C, to allocate an array, you allocate a block of memory of the required size with the `malloc` function, and you can later resize this block without affecting the data in the remaining part (when shrinking) or the initial part (when extending). Under the hood, `realloc` may allocate a new region (at a different address in memory) then copy the data, but it'll try to extend or shrink the region in place for efficiency, in which case no copying is necessary.

Most high-level languages do not support resizing existing memory regions. This is because resizing might change the address of the object, which requires modifying all references to that object — C gets away with it by shifting the burden of updating references to the programmer. If you want a resizable array, you can achieve that manually: access the array through an indirect reference, and when you want to resize the array, allocate a new array, copy the data and assign the indirect reference to the new array.

As a simple optimization, if the array size shrinks by a small amount (say, because you take an element from the queue), do not shrink the array: you'll waste a bit of space, but avoid incessantly reallocating the array and moving the data around if successive elements are removed. And if the array size increases by a small amount (say, because you push an element onto the queue), increase the array size by a margin over the requested amount, so that the array will still be good for the next few increases. The `Vector` class in Java does this: it maintains an `elementCount` for the array that contains the data; array elements beyond this position are not used.

Asymptotically, you get good behavior by varying the array size exponentially, for example sticking to powers of 2: if you add an element to a 128-element queue, resize the array to 256; if you remove an element from a 65-element queue (in a 128-element array), resize the array down to 64. With array sizes of the form $a^n$, the wasted space is at most $(a-1)$ times the array size. The cost of reallocations, dominated by moving elements when crossing a size boundary is $\Theta(a^n)$. Amortized over a sequence of additions from an empty array or a sequence of removals until the array is empty, the cost of reallocations is $\Theta(a^n/a^n) = \Theta(1)$. In general the amortized cost of reallocations is $O(1)$.

There are other implementations of resizable arrays that avoid reallocation altogether, at the cost of having slower access time to elements. Avoiding reallocations is especially good to avoid long pauses when a reallocation happens and a lot of data needs to be moved around. A simple one is to maintain a list or array of arrays of exponentially increasing size. The element number $2^i + j$ with $j \< 2^i$ is stored at position $j$ in array number $i$. No data ever needs to be copied when the array grows or shrinks (except for the bookkeeping data to maintain the collection of array, which grows logarithmically over the total size).

# Answer
> 1 votes
As explained by Guillaume13, Vector is deprecated and therefore the usage should be discouraged. There is the ArrayList class though, which basically does the same but is more up to date in the Java world.

Considering your the actual question, I think both answers are more or less equally good, as the term "extend" can be interpreted quite vast. Both design ideas would work and do their job, but not perfect (as already pointed out by Gilles), therefore they are, interpreting the task, as to program a flexible queue, not perfect.

Depending if you have to keep an "true" array (which is by design not flexible) the second might be the more fitting choice, though.

In my opinion a lisp-like list, where you just work with cells storing a value and a pointer to the next cell, would be the best answer if you are allowed to discard the old implementation. But I am not sure if such a revolutionizing design, considering your starting point, would still be within the reach of of the question.

# Answer
> 0 votes
In java, Response 2 because : in the Memory management logic : an array is an array and to expends it you have to copy it. The fact is in most of high level language the array\_copy is a native fast function so it's extremly efficient. Java Vector is deprecated and strongly discouraged since many year.

# Answer
> -1 votes
Ummmm... isn't the point of a circular array to wrap around and store some of the data at the beginning? Isn't it just to simply overlap data to fill in bits not already filled, but can be filtered out by using the % operator? Or am I completely wrong?

---
Tags: algorithms, data-structures
---


# Question
Title: How to output all longest decreasing sequences
Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for example $(3,2,1)$ is a decreasing subsequence of $(7,3,5,2,0,1)$.) I know how to calculate the length of longest decreasing sequences, but don't know how to report all longest decreasing sequences.

Pseudocode will be helpful.

# Answer
> 4 votes
Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a \> b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.

# Answer
> 1 votes
-a recursive helper function

```
    list form_longest_sublist_from(list array,list buffer,from)
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i]
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc

```
* The algorithm to use the function

```
list of lists arrayoflongestlist
    list buffer;
    from i = length array - 1 to -1 step -1
        clear buffer
        add array[i] to buffer
        from x = i - 1 to -1 step -1
            if(array[x] < last buffer
                list sbuffer;
                sbuffer = form_longest_sublist_from(array,buffer,x);
                if length sbuffer > length buffer)
                    buffer = sbuffer;
                            endif
            endif
        endfor
            if length arrayoflongestlist > 0
                   if length (last arrayoflongestlist) < length buffer
                            clear arrayoflongestlist
                            add buffer to arrayoflongestlist
                   endif
                   else if length (last arrayoflongestlist) == length buffer
                add buffer to arrayoflongestlist
            endif

                   if length (last arrayoflongestlist) > i)
                break;
        else
            add buffer to arrayoflongestlist
        endif
    endfor

```

I basically redid the whole algorithm to be a fit for the problem.

The basic idea is to start from each possible point (each element) in the array and form all possible decreasing sublists by going thorugh the rest of the array and see which elements are smaller and use those elements to start a recursion which does the same mentioned before starting from that point and then filtering the recursions for the longest list given back.

My possible worst/bestcase scenarios mentioned before are of cause not correct considering this algorithm.

# Answer
> -3 votes
For every decreasing sequence, store the initial positions in another array.

```
for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

```

Now the array temp will contain initial and final positions of all the decreasing sequences consecutively. Then print them

---
Tags: algorithms, arrays, subsequences
---


# Question
Title: Distribute objects in a cube so that they have maximum distance between each other
I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure that each color assigned to an object is as different from any color on any other object as possible.

In RGB space, we have three planes, all with values between 0 and 255. In this cube $(0,0,0) / (255,255,255)$, I would like to distribute the $n$ colors so that there is as much distance between themselves and others as possible. An additional restriction is that $(0, 0, 0)$ and $(255, 255, 255)$ (or as close to them as possible) should be included in the $n$ colors, because I want to make sure that none of my $(n-2)$ objects takes either color because the background will probably be one of these colors.

Probably, $n$ (including black and while) will not be more than around 14.

Thanks in advance for any pointers on how to get these colors.

# Answer
> 4 votes
All colors will be on the surface of the RGB cube, unless I'm mistaken, for the same reason that all electrical charge appears on the surface of electrical conductors. This suggests the following method to determine colors:

* interpret the RGB color space as an XYZ Cartesian space;
* interpret candidate colors as charged particles, e.g., electrons;
* find the low-energy state of the system through e.g. simulated annealing;

For $n \sim 15$, a highly accurate simulation should be fairly quick; you could use a Runge Kutta technique, or even Euler's method with a small time step could probably do it (much easier to implement/understand). I might suggest the series "Numerical Recipes" for numerical integration/quadrature techniques of interest.

Once particles converge, you have the arrangement of colors by interpreting points as colors. Initially, particles can be arranged randomly on the cube's surface, with a little spacing (helps convergence and stability issues). Putting small groups on faces of the cube should work.

To avoid getting stuck in a local (rather than global) minimum, you can "pulse" some small random electric field after convergence and see whether the system goes back to the same configuration, or a different one. It's somewhat unlikely that randomly placed particles will do that in this scenario, but possible.

EDIT:

As pointed out in the comments, the assumption that optimal solutions should lie only on the surface probably doesn't hold for all geometries in the discrete case.

Fortunately, this has little bearing on the rest of the technique described above. Particles can be initially placed anywhere; just leave some room between pairs of particles for stability and covergence, and then iterate the system to convergence, then pulse a few times (possibly with increasing intensity) to see if you can get the system to converge to some different (possibly better) configuration.

Also note that I believe this method will maximize something like "(harmonic?) average distance between pairs of particles". If you want to maximize the minimum distance between pairs of particles, or some other average (geometric?) between pairs of particles, this may not give you the best solution.

In any event, I feel like this technique will give you an easy way to come up with good approximately-optimal sets of colors... getting actual "optimal" solutions is probably not required for your use-case. Naturally, if an exact and provably optimal solution is desired, numerical simulation is probably not the best way to go.

---
Tags: algorithms, optimization, computational-geometry
---


title: Proving a specific language is regular

text:
# Question
Title: Proving a specific language is regular
In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it.

> Prove the following statement:
>
> If $L\_1$ is a regular language, then so is
>
> $L\_2 = \\{ uv |$ $u$ is in $L\_1$ or $v$ is in $L\_1 \\}$.

You can't use the pumping lemma for regular languages (I think), so how would you go about this? I'm inclined to believe that it's false because if $u$ is in $L\_1$, what if $v$ is non-regular? Then it would be impossible to write a regular expression for it. The question is out of 5 marks though and that doesn't seem like enough of an answer for it.

# Answer
You can use the pumping lemma to show that a language is *not* regular. Here, you're trying to prove that if $L\_1$ is regular then $L\_2$ is regular. The pumping lemma can't be used to prove this implication. It could be used to prove the contraposite (i.e. you might be able to prove that if $L\_2$ is not regular, then $L\_1$ is not regular by the pumping lemma). However, even assuming this can work (I haven't checked), it would be a lot more complicated than necessary for this result.

You write “what if $v$ is non-regular?” But this doesn't make sense: the concept of regularity applies to a language, not a word. For a given $u$, what language does $v$ have to belong to, in order for $uv$ to be in $L\_2$?

If that's not enough of a hint, try reasoning with regular expressions. If $L\_1$ is regular, then there is a regular expression that characterizes it. How can you use this regular expression to characterize $L\_2$?
> 7 votes

# Answer
Write $L\_2$ as $$\\{uv \mid u \in L\_1, v\in \Sigma^\*\\} \cup \\{uv \mid u\in \Sigma^\*, v\in L\_1\\}$$ (convince yourself it is OK to do so)

Then check about right/left quotient. With that, the proof is trivial.

EDIT: actually, quotient is not needed. Only concatenation.
> 6 votes

# Answer
There is another question about proving that languages are not regular. My personal favorite way to do it is, essentially, equivalent to the Myhill-Nerode Theorem.

For proving that a language is regular, you can either show it is expressible by a DFA, NFA, Regular Expression, etc. or you can use the fact that regular languages are closed under:

* Intersection (easiest to show with DFAs)
* Union (easy with regular expressions)
* Reversal (easy with NFAs)
* Taking prefixes, as in $L\_3$ from @sdvvc's comment (easy with DFAs)
* Suffixes (can be obtained from reversal and prefixes)

Some combinations of these should deal with the language in the question.
> 5 votes

---
Tags: formal-languages, regular-languages
---


title: Overflow safe summation

text:
# Question
Title: Overflow safe summation
Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a\_1, a\_2, \dots a\_n$ such that their sum $a\_1 + a\_2 + \dots + a\_n = S$ also fits in a register of width $w$.

It seems to me that we can always permute the numbers to $b\_1, b\_2, \dots b\_n$ such that each prefix sum $S\_i = b\_1 + b\_2 + \dots + b\_i$ also fits in a register of width $w$.

Basically, the motivation is to compute the sum $S = S\_n$ on fixed width register machines without having to worry about integer overflows at any intermediate stage.

Is there a fast (preferably linear time) algorithm to find such a permutation (assuming the $a\_i$ are given as an input array)? (or say if such a permutation does not exist).

# Answer
**Strategy**
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input *on-the-fly*, while performing the addition.

**Algorithm**

1. Partition $a\_1, \ldots, a\_n$ into a two lists, the positive elements $P$ and the negative elements $M$. Zeros can be filtered out.
2. Let $Sum=0$.
3. While both lists are non-empty
4. $~~~~~~$If $Sum\>0$ { $Sum:=Sum+\text{head}(M)$; $M:=\text{tail}(M)$; }
5. $~~~~~~$else { $Sum:=Sum+\text{head}(P)$; $P:=\text{tail}(P)$; }
6. When one of the two lists becomes empty, add the rest of the remaining list to $S$.

**Correctness**
Correctness can be established using a straightforward inductive argument on the length of the list of numbers.

First, prove that if $a\_1, \ldots, a\_n$ are all positive (or all negative), and their sum does not cause overflow, then nor do the prefix sums. This is straightforward.

Second, prove that $Sum$ is within bounds is an invariant of the loop of the algorithm. Clearly, this is true upon entry into the loop, as $Sum=0$. Now, if $Sum\>0$, adding a negative number that is within bounds to $Sum$ does not cause $Sum$ to go out of bounds. Similarly, when $Sum\le0$ adding a positive number that is within bounds to sum does not cause $Sum$ to go out of bounds. Thus upon exiting the loop, $Sum$ is within bounds.

Now, the first result can be applied, and together these are sufficient to prove that the sum never goes out of bounds.
> 10 votes

---
Tags: algorithms, arrays, integers, numerical-analysis
---


title: Lambda Calculus beta reduction

text:
# Question
Title: Lambda Calculus beta reduction
I am trying to learn Lambda calculus from here

and while trying to solve some problems, I got stuck. I was trying to solve the following problem (page 14, excercise 2.6 part (i):

Simplify $M \equiv (\lambda xyz.zyx) aa (\lambda pq. q)$.

My evaluation using the beta rule reduces it to $(\lambda z. z)$ as follows: First I replace occurences of $x$ in $M$ by $aa (\lambda pq. q)$, and then since there are no occurences of $y$ in the resulting $\lambda$ term, the expression simply evaluates to $(\lambda z. z)$.

Is my reasoning correct? (Since there were no solutions to these notes, I want to ensure my understanding is correct. Any corrections, will be much appreciated! Thanks in advance.

# Answer
No, your reduction is wrong. The function $(\lambda x y z. z y x)$ is applied to three arguments: $a$, $a$ and $(\lambda p q. q)$. It is not, as you wrote, a the function $(\lambda x y z. z y x)$ applied to the term $a a (\lambda p q. q)$; that second term does not appear in $M$. Strictly speaking, functions in the lambda-calculus take three arguments, they are effectively curried, so if you add optional parentheses $M$ can be written $$ (((\lambda x. (\lambda y. (\lambda z. (z y) x))) a) a) (\lambda p. (\lambda q. q)) $$ This reduces by substituting $a$ for $x$ in $(\lambda y. (\lambda z. (z y) x)))$, then $a$ for $y$ in the result of this: $$ M \to (\lambda y z. z y a) a (\lambda p q.q) \to (\lambda z. z a a) (\lambda p q. q) $$ then substitute $(\lambda p q. q)$ for $z$, after which a new redex appears: $$ \ldots \to (\lambda p. (\lambda q. q)) a a \to (\lambda q. q) a \to a $$
> 8 votes

---
Tags: logic, lambda-calculus
---


# Question
Title: Why are blocking artifacts serious when there is fast motion in MPEG?
Why are blocking artifacts serious when there is fast motion in MPEG?

Here is the guess I made:

In MPEG, each block in an encoding frame is matched with a block in the reference frame. If the difference of two blocks is small, only the difference is encoded using DCT. Is the reason blocking artifacts are serious that the difference of two blocks is too large and DCT cut the AC component?

# Answer
> 8 votes
DCT is both discrete and finite, it has a limited range in both the space and frequency domains. If the change in a certain location is large or the location changes a lot, the results of the transform will be beyond the sampling range in the frequency domain.

Since as you mentioned MPEG is based on blocks, the result of a block with with missing high frequencies, after transform back to the spacial domain, will result in the loss of detail in that block - making the block look flat.

For a more accurate result try Signal Processing Stack Exchange.

---
Tags: information-theory, data-compression, video
---


title: How many possible ways are there?

text:
# Question
Title: How many possible ways are there?
Suppose I have the given data set of length 11 of scores:

```
p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1]

```

I want to select scores 6, 5, 5, 4, 2, 2 from the data set. How many ways are there?

For the above example answer is: 6 ways

```
{p[1], p[2], p[4], p[5], p[7], p[8]}
{p[10], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[10], p[5], p[7], p[8]}
{p[9], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[9], p[5], p[7], p[8]}
{p[10], p[2], p[9], p[5], p[7], p[8]}

```

How can I count the ways in general?

# Answer
> 3 votes
Say you want to pick, out of a multiset $S$, the numbers $x\_1$, $x\_2$, ..., $x\_n$ with multiplicity $m\_1$, $m\_2$, ..., $m\_n$ (i.e., you want to pick $x\_1$ exactly $m\_1$ times). Furthermore, assume that in $S$ the numbers $x\_1$, $x\_2$, ..., $x\_n$ have multiplicity $s\_1$, $s\_2$,..., $s\_n$. (we assume for every $i$, $s\_i \ge m\_i$, otherwise no solution exists).

Consider the first element $x\_1$: you have exactly $s\_1 \choose m\_1$ different ways to pick $m\_1$ occurrences of $x\_1$ from the $s\_1$ times it appears in $S$.

In a similar way for all the other elements, the answer would be $${s\_1 \choose m\_1} {s\_2 \choose m\_2} \cdots {s\_n \choose m\_n} = \prod\_{i=1}^n {s\_i \choose m\_i}$$

---

For your example, set $x\_1=6$, $x\_2=5$, $x\_3=4$, $x\_4=2$. In the data set they appear with multiplicity $s\_1=1$, $s\_2=2$, $s\_3=1$, $s\_4=4$ and you want to have $m\_1=1$ sixes, $m\_2=2$ fivess, $m\_3=1$ fours and $m\_3=2$ twos, so the number of different options is $$ {1 \choose 1} {2 \choose 2} {1 \choose 1}{4 \choose 2} = 1 \cdot 1 \cdot 1 \cdot 6$$

---
Tags: combinatorics
---


title: When to use recursion?

text:
# Question
Title: When to use recursion?
When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?

# Answer
> 19 votes
I have taught C++ to undergraduates for about two years and covered recursion. From my experience, your question and feelings are *very* common. At an extreme, some students see recursion as difficult to understand while others want to use it for pretty much everything.

I think Dave sums it up well: use it where it is appropriate. That is, use it when it feels natural. When you face a problem where it fits nicely, you will most likely recognize it: it will seem like you cannot even come up with a iterative solution. Also, clarity is an important aspect of programming. Other people (and you also!) should be able to read and understand the code you produce. I think it is safe to say iterative loops are easier to understand at first sight than recursion.

I don't know how well you know programming or computer science in general, but I strongly feel that it does not make sense to talk about virtual functions, inheritance or about any advanced concepts here. I have often started with the classic example of computing Fibonacci numbers. It fits here nicely, since Fibonacci numbers are defined recursively. This is easy to understand and does not require *any* fancy features of the language. After the students have gained some basic understanding of recursion, we have taken another look at some simple functions we have built earlier. Here's an example:

> Does a string contain a character $x$?

This is how we did it before: iterate the string, and see if any index contains $x$.

```
bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

```

The question is then, *can* we do it recursively? Sure we can, here's one way:

```
bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

```

The next natural question is then, should we do it like this? Probably not. Why? It's harder to understand and it's harder to come up with. Hence it is more prone to error, too.

# Answer
> 24 votes
The solutions to some problems are more naturally expressed using recursion.

For example, assume that you have a tree data structure with two kinds of nodes: leaves, which store an integer value; and branches, which have a left and right subtree in their fields. Assume that the leaves are ordered, so that the lowest value is in the leftmost leaf.

Suppose the task is to print out the values of the tree in order. A recursive algorithm for doing this is quite natural:

```
class Node { abstract void traverse(); }
class Leaf extends Node {
  int val;
  void traverse() { print(val); }
}
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

```

Writing equivalent code without recursion would be much more difficult. *Try it!*

More generally, recursion works well for algorithms on recursive data structures like trees, or for problems that can naturally be broken into sub-problems. Check out, for instance, divide and conquer algorithms.

If you really want to see recursion in its most natural environment, then you should look at a functional programming language like Haskell. In such a language, there is no looping construct, so everything is expressed using recursion (or higher-order functions, but that's another story, one worth knowing about too).

Note also that functional programming languages perform optimized tail recursion. This means that they do not lay down a stack frame unless they do not need to --- essentially, recursion can be converted to a loop. From a practical perspective, you can write code in a natural fashion, but get the performance of iterative code. For the record, it seems that C++ compilers also optimize tail calls, so there is no additional overhead of using recursion in C++.

# Answer
> 11 votes
From someone who practically lives in recursion I will try and shed some light on the subject.

When first introduced to recursion you learn that it is a function that calls itself and is basically demonstrated with algorithms such as tree traversal. Later you find that it is used a lot in functional programming for languages such as LISP and F#. With the F# I write, most of what I write is recursive and pattern matching.

If you learn more about functional programming such as F# you will learn F# Lists are implemented as singly linked lists, which means that operations that access only the head of the list are O(1), and element access is O(n). Once you learn this you tend to traverse data as list, building new list in reverse order and then reversing the list before returning from the function which is very effective.

Now if you start to think about this you soon realize that recursive functions will push a stack frame every time a function call is made and can cause a stack overflow. However, if you construct your recursive function so that it can perform a tail call and the compiler supports the ability to optimize the code for the tail call. i.e. .NET OpCodes.Tailcall Field you will not cause a stack overflow. At this point you start writing any looping as a recursive function, and any decision as a match; the days of `if` and `while` are now history.

Once you move to AI using backtracking in languages such as PROLOG, then everything is recursive. While this requires thinking in a manner quite different from imperative code, if PROLOG is the right tool for the problem it frees you of the burden of having to write lots of lines of code, and can reduce number of errors dramatically. See: Amzi customer eoTek

To get back to your question of when to use recursion; one way I look at programming is with hardware at one end and abstract concepts at the other end. The closer to the hardware the problem the more I think in imperative languages with `if` and `while`, the more abstract the problem, the more I think in high level languages with recursion. However, if you start writing low level system code and such, and you want to verify that its valid, you then find solutions like theorem provers come in handy, which rely heavily on recursion.

If you look at Jane Street you will see they use the functional language OCaml. While I have not seen any of their code, from reading about what they mention about their code, they are surly thinking recursively.

EDIT

Since you are looking for a list of uses, I will give you a basic idea of what to look for in the code and a list of basic uses which are mostly based on the concept of Catamorphism which is beyond the basics.

For C++: If you define a structure or a class that has a pointer to the same structure or class then recursion should be considered for traversal methods that use the pointers.

The simple case is a one way linked list. You would process the list starting at the head or tail and then recursively traverse the list using the pointers.

A tree is another case where recursion is often used; so much so that if you see tree traversal without recursion you should start asking why? It is not wrong, but something that should be noted in the comments.

Common uses of recursion are:

# Answer
> 8 votes
To give you a use case that is less arcane than those given in the other answers: recursion mixes very well with tree-like (Object Oriented) class structures deriving from a common source. A C++ example:

```
class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

```

The above example uses recursion: ComputeValue is implemented recursively. To make the example work, you use virtual functions and inheritance. You don't know what the left and right parts of the Plus class are exactly, but you don't care: it something that can compute its own value, which is all you need to know.

The crucial advantage of the above approach is that *every class takes care of its own computations*. You separate the different implementations of every possible subexpressions completely: they have no knowledge of each other's workings. This makes reasoning about the program easier and therefore makes the program easier to comprehend, maintain and extend.

# Answer
> 3 votes
The first example used to teach recursion in my beginning programming class was a function to list all the digits in a number separately in reverse order.

```
void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

```

Or something like that (I'm going from memory here and not testing). Also, when you get into higher level classes, you'll use recursion a LOT especially in search algorithms, sorting algorithms, etc.

So it may seem like a useless function in the language now, but it is very very useful in the long run.

---
Tags: algorithms, recursion
---


title: Logic gates from everyday materials

text:
# Question
Title: Logic gates from everyday materials
Logic gates are an abstract device which can be implemented with electromagnetic relays, vacuum tubes, or transistors. These implemenations have been successful in computing in part because of various properties of chainability, durability, and size beyond their basic binary stability. They also work well because electricity is the energy source which can rather easily be shipped around.

I've seen adders built out of wood, marbles, and gravity. I've seen "lab on a chip" capilary-action-driven prototypes. I've seen all kinds of specialty mechanical calculators (Curta, slide rule). I've seen domino trails as single-use logic gates.

I'm interested in other illustrative computing devices that aren't *necessarily* convenient, durable, or fast, but which exploit properties of everyday materials to perform computation and which are directly visible. The dominoes trails are close, but are a little too complicated to reset.

Magneto-mechanical arrangements? Water in pipes/troughs? More general marble contraptions?

PS. Here's a new one. Mechanical CPU Clock

# Answer
Some more options:

If you're into Billiard, you can create logic gates from Billiard balls

If you prefer the wild life, Crab-based logic gates should fit.
> 5 votes

# Answer
It is possible to build a Turing machine with "Lego" elements without any electric components, only with pneumatic transmission of energy. The guys who did this used some logic gates with pneumatic but this was the very easy part. The underlying automaton was way harder to build. (webpage in French. The other Turing machines in Legos use electronic devices which is very much like cheating)

Moreover I know you can build logic gates using only Lego elements and that may be more relevant.

So mechanics as well as pneumatics are enough to build logic gates.
> 8 votes

# Answer
Believe it or not, here's a guy who built logic gates using streams of water...

http://www.blikstein.com/paulo/projects/project\_water.html

Apparently, he worked up to a 4-bit adder, though I believe this picture shows only a single half-adder...

<sub>(source: blikstein.com)</sub>
> 7 votes

---
Tags: computer-architecture, didactics
---


# Question
Title: Encoding the sequence 0110 and determining parity, data bit and value
I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense.

eg.1

eg.2

I don't really understand the above two examples and the calculations taking place.

How were the conclusions reached concerning the categories of **bin position (dec/bin), parity/data bit and value** in **e.g 1**?

Secondly I don't understand the process taking place in **e.g. 2** at all. Does it follow that:

> General rule: For any code C,
>
> * errors of less than $d(C)$ bits can be detected,
> * errors of less than $d(C)/2$ bits can be corrected.
>
> Definition: A code C with $d(C) \geq 3$ is called error-correcting.

If this is correct then how would I put it into practice. Would really appreciate some assistance!

# Answer
> 5 votes
Well, these examples are not easy to read, by they are indeed correct.

**e.g.1**:

The word to code has 4 bits, and lets call them $b\_1 b\_2 b\_3 b\_4$. To this "data" word add 3 parity bits (adding is over $GF(2)$):

* $p\_1 = b\_1 \oplus b\_2 \oplus b\_3$,
* $p\_2 = b\_1 \oplus b\_2 \oplus b\_4$, and
* $p\_3 = b\_1 \oplus b\_3 \oplus b\_4$.

<sub>\[remark: for **odd** parity, add "1" to each equation, e.g., $p\_1 = b\_1 \oplus b\_2 \oplus b\_3 \oplus 1$\]</sub>

Then we transmit the code word

$$C= b\_1 b\_2 b\_3 p\_1 b\_4 p\_2 p\_3$$

Why this particular order? They want the "position" of the parity bits to be "1" "2" and "4" (starting to count from the right side) which corresponds to bit positions "001" "010" and "100". This is meaningful in order for the decoding to work as they demonstrate.

You can see by the colors which parity bit belongs to which data-bits.

(Awful explanation in my eye, but, oh well.)

as for the decoding: **e.g. 2**

the procedure to decode is the following:

1. recompute $p\_1, p\_2, p\_3$ from the received $b\_1b\_2b\_3b\_4$
2. if you got the **same** values as the received codeword (the $p\_1,..$ you received) - then everything is fine
3. Otherwise - the error is located in position $x$ where $x$ is the sum of locations of the parity bits $\\{1,2,4\\}$. For instance, if only $p\_3$ is incorrect, than the error is in bit no "1" - $p\_1$ itself is the only one got flipped. If $p\_3$ and $p\_1$ mismatch, than you need to flip the bit in location $1+4=5$, that is, $b\_3$.

Note that this code fixes only a single error.

---
Tags: coding-theory
---


# Question
Title: Magic Square Check for NxN Matrix - with Minimum Complexity?
Is there any algorithm that works better than $\Theta(n^2)$ to verify whether a square matrix is a magic one? (E.g. such as sum of all the rows, cols and diagonally are equal to each other). I did see someone mention a $O(n)$ time on a website a few days ago but could not figure out how.

# Answer
If you have an $N \times N$ matrix, then it has $N^2$ entries, and as you need to check all entries at least once to see if the square is a magic square, any algorithm must have a running time of $\Omega(N^2)$.

For a square to be a magic square, all rows, columns and both diagonals must sum to the same number. There are $N$ rows, $N$ columns and 2 diagonals, each of which have $N$ entries, so you can check this property in $O((2N+2)N) = O(N^2)$ time.

Combining the above: verifying the magicness of a square is in $\Theta(N^2)$.
> 4 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: What is the name of this logistic variant of TSP?
I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the problem.

I have $P$ warehouses on the Cartesian plane. There's a path from a warehouse to every other warehouse and the distance metric used is the Euclidean distance. In addition, there are $n$ different items. Each item $1 \leq i \leq n$ can be present in any number of warehouses. We have a collector and we are given a starting point $s$ for it, say the origin $(0,0)$. The collector is given an order, so a list of items. Here, we can assume that the list only contains distinct items and only one of each. We must determine the shortest tour starting at $s$ visiting some number of warehouses so that the we pick up every item on the order.

Here's a visualization of a randomly generated instance with $P = 35$. Warehouses are represented with circles. Red ones contain item $1$, blue ones item $2$ and green ones item $3$. Given some starting point $s$ and the order ($1,2,3$), we must pick one red, one blue and one green warehouse so the order can be completed. By accident, there are no multi-colored warehouses in this example so they all contain exactly one item. This particular instance is a case of set-TSP.

I can show that the problem is indeed $\mathcal{NP}$-hard. Consider an instance where each item $i$ is located in a different warehouse $P\_i$. The order is such that it contains every item. Now we must visit every warehouse $P\_i$ and find the shortest tour doing so. This is equivalent of solving an instance of $\text{TSP}$.

Being so obviously useful at least in the context of logistic, routing and planning, I'm sure this has been studied before. I have two questions:

1. What is the name of the problem?
2. How well can one hope to approximate the problem (assuming $\mathcal{P} \neq \mathcal{NP}$)?

I'm quite happy with the name and/or reference(s) to the problem. Maybe the answer to the second point follows easily or I can find out that myself.

# Answer
> 5 votes
Among others, this problem can be seen as an instance of the Traveling Purchaser Problem. $\text{TPP}$ is a generalization of $\text{TSP}$ and was first proposed by T. Ramesh, Traveling purchaser problem, 1981. The problem is as follows:

> We are given a set $M = \\{ 1, ..., m \\}$ of markets and a set of $N = \\{ 1, ..., n \\}$ of products. Also we are given $c\_{ij}$, the cost of traveling from city $i$ to city $j$, and non-negative $d\_{ij}$, the cost of a product $i$ at market $j$. The purchaser starts from his home city (for example city $1$), and travels to a subset of the $m$ cities and purchases each of the $n$ products in of the cities he visits, and return back to his home city. The objective is to find a tour for the purchaser that such that the sum of the travel and purchase costs are minimized.

So, put in the terms of the original question, warehouses are markets. Each available item at a market has equal price. If item $i$ is not available at a market $j$, its price $d\_{ij}$ is set to a high value.

In addition to containing $\text{TSP}$, $\text{TPP}$ contains prize collecting $\text{TSP}$, uncapacited facility location problem, group Steiner tree problem and the set cover problem as its immediate special cases. For the hardness, following from current hardness results for set cover, it follows that there is no PTAS for $\text{TPP}$ even with metric travel costs whose performance ratio is better than $(1-o(1))\ln n$ unless $\mathcal{P} = \mathcal{NP}$. For additional discussion and formulation as an IP, see for example R. Ravi and F. S. Salman, Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design, 1999. The Wikipedia entry for TPP also gives links to some heuristic approaches.

# Answer
> 6 votes
The problem is in $\mathrm{P}$ if the number of items is constant.

Let $K$ be the number of items (independent of $n$). For every ordering of items, use backtracking to try all allowed routes: you first go through some warehouse for the first item (trying all warehouses), then one for the second item and so on.

There are $O(K!)$ orderings of the items. Let $W\_i$ be the number of warehouses for item $i$. The number of routes is $\prod\_{i=1}^K W\_i \leq \prod\_{i=1}^K n = n^K$. Therefore, the running time of the above algorithm is $O(K! n^K)$, which is polynomial for fixed $K$.

If the number of items can be linear in $n$, the problem is at least as hard to approximate as $TSP$: you can take an instance of $TSP$, make an item for every vertex as you noted, and then add extra vertices very far away from all other vertices to inflate $n$ (and therefore allow for enough items that every vertex of the $TSP$ instance has a different item), without destroying the hardness of approxability of $TSP$. Note that if your points are in the Euclidian plane, then this doesn't really help you as there is a $PTAS$ for planar $TSP$.

# Answer
> 2 votes
What you described sounds more like a planning problem in AI. It sounds like what might be modeled with a planning language, such as STRIPS, ADL, PDDL, etc. Once modeled, the plan can then be solved by one of many planning algorithms/heuristics, which are typically state space search algorithms. The Wiki links should get you started. A planning chapter in any AI textbook can also help. An example of PDDL planner is the GraphPlanner software.

Granted some rather degenerate instances of this problem may be equivalent to TSP, this problem is not in general the same as TSP, nor is it Set TSP. In both TSP and Set TSP, the set of cities (warehouses) to be visited is predefined. Here, we don't really care about what warehouses are visited, but rather we only care about fulfilling an order as cheaply and efficiently as possible. You could have orders that cannot be fulfilled. A planner will come back with an empty plan or a partial one in such a case -- a non-satisfiability report. The plan satifiability problem is known in general to be PSPACE-complete. In TSP or Set TSP, an optimal tour always exists -- it might not be unique though.

---
Tags: algorithms, optimization, reference-request, approximation
---


# Question
Title: How to use adversary arguments for selection and insertion sort?
I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.

I have some doubts regarding this. I understand that adversary arguments are usually used for finding lower bounds for certain "problems" rather than "algorithms".

I understand the merging problem. But how could I write one for selection and insertion sort?

# Answer
> 9 votes
From your comment, it seems you are confusing the meaning of lower bounds, upper bounds and asymptotic notation. For instance, take Insertion Sort. Its best-case running time is $\Theta(n)$ (this happens when the input is already sorted). Its worst-case running time is $\Theta(n^2)$ (this happens when the input is in reverse sorted order). So, since the running time falls between a linear function of $n$ and a quadratic function of $n$, you can say that the running time of Insertion Sort is both $\Omega(n)$ and $O(n^2)$. It's important to understand in this case that you *cannot* say that the running time is $\Omega(n^2)$. Why? Because there exists an input that causes the algorithm to run in $O(n)$. However, you may say that the worst-case running time is $\Omega(n^2)$, again because there exists an input that causes the algorithm to run in $\Omega(n^2)$. We usually use the $O$ notation for the worst-case though, since we are interested in an upper bound on the number of operations done by the algorithm.

Now, let's think about an adversary argument for Insertion Sort (you may try to derive one for Selection Sort by applying the same ideas).

Consider the Insertion Sort algorithm playing against an opponent that we will call the adversary. The aim of the adversary is to provide an input X for the algorithm that maximizes the number of comparisons done by the algorithm. This is usually analyzed in the context of *decision trees*. A decision tree shows all possible sequences of comparisons that the algorithm could make. Each interior node of a decision tree represents a single comparison. The two children of a node represent the two outcomes of the comparison (yes/no or true/false). Each leaf represents a possible output. For sorting algorithms, the leaves are *permutations* of the keys. The algorithm starts at the root and follows a path down to a leaf. At each internal node, the answer for the comparison done tells the algorithm which node must be visited next. When the algorithm reaches a leaf, it outputs its corresponding permutation. The running time of an algorithm (seen as a decision tree) for a given input is the number of comparisons done in the path from the root to the output leaf. Now, the adversary has a simple strategy that will work against any comparison-based sorting algorithm, including Insertion Sort: whenever the algorithm makes a comparison, the adversary chooses the answer that will eliminate the fewest possible permutations.

In general, owing to the fact that with $n$ elements there are $n!$ possible permutations, any decision tree for sorting must have at least $n!$ leaves, and so must have depth $\Omega(\log(n!)) = \Omega(n\log n)$ (by Stirling’s approximation). For Insertion Sort, the adversary may craft a particular input that causes the corresponding decision tree to have depth of at least $\Omega(n^2)$.

The algorithm uses an array $A\[1 .. n\]$ to store the input elements and is based on the following invariant:

At the start of each iteration of the for loop, the subarray $A\[1 .. j-1\]$ consists of the elements originally in $A\[1 .. j-1\]$, but in sorted order.

In each iteration, the elements in $A\[1 .. j-1\]$ are therefore already in sorted order, and the algorithm examines $A\[j\]$ and inserts it in its final proper place, by comparing the value of $A\[j\]$ against the value of the elements in $A\[1 .. j-1\]$, starting from $A\[j-1\]$ and proceeding back to $A\[j-2\]$ and so on until $A\[j\]$ is no longer the greatest one in the comparison. The elements in $A\[j+1 .. n\]$ are in an unknown state (with regard to the sort order) and will be processed in later iterations.

Here is the strategy of the adversary. Knowing that the algorithm works by inserting $A\[j\]$ in its proper place by moving the elements in $A\[1 .. j-1\]$, then the obvious strategy is to maximize in the $j$-th iteration the number of elements that must be moved in order to accommodate $A\[j\]$. This is easily accomplished by carefully choosing the input so that it is in *reverse* sorted order. Indeed, in this case, the number of elements that must be moved in each iteration is $j-1$. This leads to the $\Omega(n^2)$ worst-case running time (determined by the corresponding arithmetic series).

---
Tags: algorithms, algorithm-analysis, proof-techniques, lower-bounds
---


# Question
Title: Null Characters and Splitting the String in the Pumping Lemma
So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take the problem prove that $L = \\{w | w$ contains more $0$'s than $1$'s over the language $\\{0,1\\} \\}$ is not regular via the pumping lemma.

So I choose the string $01^{p}0^{p}$. Since this is a regular language pumping lemma problem I know that:

1. for each $i \> 0, xy^{i}z \in A$,
2. $|y^{i}| \> 0$, and
3. $|xy| \< p$

I am little uncertain about other possibilites though, such as if $x$, or $z$ can be null (obviously $y$ can't by condition 2). I assume that this isn't possible since I don't think the preceding or trailing whitespace is considered part of the string, but I'm not sure. **Is it possible for $x$ or $z$ to be null?**

# Answer
Yes, it is possible for $x$ or $z$ to be 'null', if by 'null' you mean the empty string. The empty string, $\epsilon$, is the string of length zero.

If the loop in the automaton (which is ultimately what the pumping lemma refers to) starts at the initial state and the initial state is also an accepting state, then strings of the form $y^i$ will be accepted, where $y$ is some string that will take you around the loop.

Whitespace plays no role in this theorem. Formal languages are defined over a given alphabet, in your case $\\{0,1\\}$. This is the only alphabet relevant for the question. There is no preceding or trailing whitespace when talking about the pumping lemma. Spaces, tabs, return characters play absolutely no role.
> 6 votes

---
Tags: formal-languages, regular-languages, proof-techniques, pumping-lemma
---


# Question
Title: Looking for a ranking algorithm that favors newer entries
I'm working on a ranking system that will rank entries based on votes that have been cast over a period of time. I'm looking for an algorithm that will calculate a score which is kinda like an average, however I would like it to favor newer scores over older ones. I was thinking of something along the line of:

$$\frac{\mathrm{score}\_1 +\ 2\cdot \mathrm{score}\_2\ +\ \dots +\ n\cdot \mathrm{score}\_n}{1 + 2 + \dots + n}$$

I was wondering if there were other algorithms which are usually used for situations like this and if so, could you please explain them?

# Answer
You could use any function that gives a lower weight to older entries. For example, if data consists of scores, $s\_1,\ldots,s\_n$, where the index corresponds to the 'time of arrival' of the entry, that is, newer entries have larger indices, then you could use a weight function that increase as $i$ increases. So any 'increasing' function will do. Examples include:

* $f(x)=e^x$
* $f(x)=\log x$
* $f(x)=x$
* $f(x)=x^2$

etc.

Then your function will be

$\dfrac{\sum\_{i=1}^n s\_i\cdot f(i)}{\sum\_{i=1}^n f(i)}$.

Actually, it makes more sense to give the newest entry the lowest index and make the weight function decreasing. This way you can tune it by setting the weighting that you want to give to the first element.

Wikipedia has an entry on weight functions, some examples can be found on the page about weighted means.
> 8 votes

---
Tags: algorithms, data-mining
---