# Question
Title: Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?
# Intuition:

Suppose I have an array of nonzero integer values $A\[n\]$ and a partially constructed Fenwick tree of this array: $F\[k\], n\>k$. I can see why inserting the next element would be worst case $O(\lg n)$. The number of elements accessed from $F\[0:k\]$ to calculate $F\[k+1\]$ is equal to the number of trailing zeroes in $(k+1)\_2$ which is at most $\lfloor \lg(n) \rfloor$. There are $n$ elements, so this is $O(n\lg n)$. Wikipedia seems to agree as well.

# Thoughts:

**NOTE:** I am using this algorithm.

Consider the number of positive integers less than or equal to $n$ with exactly $j$ trailing zeroes in their binary representation, $j\<{\lfloor \lg(n) \rfloor}$. Since the leftmost ${\lfloor \lg(n) \rfloor}-(j+1)$ digits can be freely assigned so long as the resulting number is less than $n$ ($j+1$ because the $(j+1)th$ digit from the right must be a $1$), there are between $2^{\lfloor \lg(n) \rfloor-j-1}$ and $2^{\lfloor \lg(n) \rfloor-j)}$ such numbers for any $n$.

Let an operation be defined as the summation of two numbers, which is assumed to be a constant time operation. (The other operations, like insertion, are also in constant time and are performed a constant number of times, hence they are ignored) Thus, for $j$ trailing zeroes, $j$ operations must be performed.

As a result, the total number of operations to perform is at most $\sum\limits\_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}$. It must also be true that $2^{\lfloor \lg(n) \rfloor}≤n\<2^{\lfloor \lg(n) \rfloor + 1}$. Note that both maxima occur when $n\_2$ is filled with ones. If we take this case, the mean number of operations for any $j$ as $n \rightarrow \infty$ should be:

$\lim\_{n\to\infty}\frac{\sum\limits\_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}}{2^{\lfloor \lg(n) \rfloor +1}-1} =\lim\_{n\to\infty}{\sum\limits\_{j=0}^n \frac {j}{2^{j}}} =1$

Now, if we take the other extreme, where $\lg(n)\in\mathbb{Z}$ ($n\_2$ is a one trailed exclusively by zeroes) then there are exactly $\lg(n)+\sum\limits\_{j=0}^{\lg(n)-1} j2^{{\lg(n)-1}-j}$ operations to be performed over exactly $2^{\lg(n)}$ numbers, and the limit also approaches $1$. Testing seems to reveal that no other values of $n$ with the same $\lfloor \lg(n) \rfloor$ values have a higher mean number of operations per element than these.

**If the amortized cost of inserting each element is indeed constant, shouldn't constructing the tree be $\Theta(n)$ time?**

## Testing:

I've tested the ranges between admittedly small consecutive powers of two, both by applying the summation and by brute force, and the results seem to agree:

Code using summation: http://pastebin.com/T3EEM7qz

Code using brute force: http://pastebin.com/sxdAkgxn

# Answer
Technically it *is* $O(n\log n)$, since big-O is an upper bound only, but your tighter bound of $O(n)$ is also correct. (Without loss of generality, it suffices to restrict $n$ to powers of two; then the proof is easy.)
> 2 votes

# Answer
**\[EDIT: Everything down to the horizontal line was written under the assumption that the algorithm being used was the obvious naive one, in which we simply call update(i, A\[i\]) for every $1 \le i \le n$. But the OP had a cleverer algorithm in mind... which s/he has now actually described ;-)\]**

The main problem with your analysis is that the number of Fenwick tree operations (additions or writes to the array) required to **update** it with some value $i$ is not equal to the number of trailing zero bits in $i$. It's equal to the number of range sums that $i$ needs to be included in, which can all be found by repeatedly adding the least significant 1-bit present in $i$ to $i$ until it escapes past the maximum possible index, i.e., by using the update rule

```
void update(int idx ,int val){
    while (idx <= MaxVal){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

```

taken from this nice tutorial.

In the best case, which is when $n$ is 1 less than a power of 2, this works out to be $\lfloor \lg n \rfloor - y\_i - f\_i + 1$ operations, where $y\_i$ is the total number of 1-bits in $i$, and $f\_i$ is the number of trailing 0-bits in i. (Every *non-trailing* 0-bit position $0 \leq j \leq \lfloor \lg n \rfloor$ in $i$, including those $j$ for which $2^j \> i$, is the position of the lowest 1-bit of exactly 1 index that $i$ contributes to, and each of them can be reached in constant time due to the magic of ripple carries.) The worst case occurs when $n$ is a power of 2: this adds exactly 1 more operation to every update over the best case. (The worst-case value of $i$ is of course $i = 1$.)

None of this rules out the possibility that the naive construction algorithm actually is O(n) -- but it seems very unlikely. Using code similar to yours I find that empirically, the mean number of operations required by the naive construction algorithm seems to increase logarithmically with $n$:

```
NEW WORST: 1.000000 for n=1
NEW WORST: 1.500000 for n=2
NEW WORST: 2.000000 for n=4
NEW WORST: 2.500000 for n=8
NEW WORST: 3.000000 for n=16
NEW WORST: 3.500000 for n=32
NEW WORST: 4.000000 for n=64
NEW WORST: 4.500000 for n=128
NEW WORST: 5.000000 for n=256
NEW WORST: 5.500000 for n=512
NEW WORST: 6.000000 for n=1024
NEW WORST: 6.500000 for n=2048
NEW WORST: 7.000000 for n=4096
NEW WORST: 7.500000 for n=8192
NEW WORST: 8.000000 for n=16384
NEW WORST: 8.500000 for n=32768

```

Finally, in case you're interested, I came up with a simple in-place algorithm for this that uses exactly 1 addition operation per array index in response to a similar question on SO.

---

P.S.: Since I actually went through your question *before* realising that the thing you were counting wasn't quite right, let me just detail a couple of small further problems with it:

To get an upper bound on the mean you need to pick a *lower* bound on n to go in the denominator of the limit, e.g.:

$\lim\_{n\to\infty}\frac{\sum\limits\_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}}{2^{\lfloor \lg(n) \rfloor}} =\lim\_{n\to\infty}{\sum\limits\_{j=0}^n \frac {j}{2^{j}}}$,

and in any case,

$\lim\_{n\to\infty}{\sum\limits\_{j=0}^n \frac {j}{2^{j}}} =2$,

not 1 as you claimed. (Obviously this wouldn't change the asymptotic complexity; also, although this constant appears to be loose from looking at your graphs, I find that it actually agrees with the numbers output by your brute-force code snippet, which hover just below 2 -- are the graphs "right", or the code?)
> 2 votes

---
Tags: algorithm-analysis, data-structures, binary-trees, amortized-analysis
---


# Question
Title: Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?
Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that might happen in case of robbery, one problem came into my mind and it can be described as follows.

Suppose that you and your family decided to go on a trip abroad, that would last for around 7 days. After spending some nice time with your family, you return back only to realize that your home had been robbed. You call the police and the police asks for the data stored in the camera.

Now, you know for sure that the robbery happened during those 7 days that you were gone, and you definitely know that the camera will show the people doing the robbery at some specific point of time, problem is, you do not know when.

Now, assuming that no one had seen anything at all and that the only source of information would be the data stored by the camera, how would the police find the time during which the robbery happened? Can they do something better than watching every single second of the footage available?

In computer science terms, assume that you are given an array of size $N$, where all the elements are white, except for one which is black. Now you can imagine that the white elements are just images stored by the camera and the indexes of the array represent seconds. If no robbers are depicted in the image, then this image is `white`, otherwise it is `black`.

So now you want to find that second where the robbers are depicted in the image, so you are looking for the index of the black element in your array. Can you do better than actually scanning the entire array to find that index?

# Answer
> 10 votes
For your problem with the array: No, there is no better algorithm. That's the best you can do. Any deterministic algorithm will in the worst case have to look at every array element (technically: at least $n-1$ of the $n$ elements).

This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at $n-2$ elements and hasn't found the black element yet. Then I claim a correct algorithm has to examine at least one more array element. If it doesn't, then look at what output it produces, and see which of those two elements it blames; you can now construct an array that puts the black element at the other element (the one it didn't blame and hasn't looked at yet). That array will be entirely consistent with everything the algorithm has seen so far, so the algorithm will produce the wrong output on that array.

---

For your problem with the camera video: In real life, there are much better techniques available. For instance, you can do "change detection" to find the frames in the video that are different (show a change from the previous frame) and look only at those. There are more sophisticated things you can do, but this illustrates that in practice you can often do much better, by taking advantage of domain-specific information about video surveillance.

---
Tags: algorithms, search-algorithms
---


title: Is weighted XOR-SAT NP-hard?

text:
# Question
Title: Is weighted XOR-SAT NP-hard?
Given $n$ boolean variables $x\_1,\ldots,x\_n$ each of which is assigned a positive cost $c\_1,\ldots,c\_n\in\mathbb{Z}\_{\>0}$ and a boolean function $f$ on these variables given in the form $$f(x\_1,\ldots,x\_n)=\bigwedge\_{i=1}^k\bigoplus\_{j=1}^{l\_i}x\_{r\_{ij}}$$ ($\oplus$ denoting XOR) with $k\in\mathbb{Z}\_{\>0}$, integers $1\leq l\_i\leq n$ and $1\leq r\_{i1}\<\cdots\<r\_{il\_i}\leq n$ for all $i=1,\ldots,k$, $j=1,\ldots,l\_i$, the problem is to find an assignment of minimum cost for $x\_1,\ldots,x\_n$ that satisfies $f$, if such an assignment exists. The cost of an assignment is simply given by $$\sum\_{\substack{i\in\\{1,\ldots,n\\}\\x\_i\\,\text{true}}}c\_i.$$ Is this problem NP-hard, that is to say, is the accompanying decision problem "Is there a satisfying assignment of cost at most some value $K$" NP-hard?

Now, the standard XOR-SAT problem is in P, for it maps directly to the question of solvability of a system of linear equations over $\mathbb{F}\_2$ (see, e. g., https://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem#XOR-satisfiability). The result of this solution (if it exists) is an affine subspace of $\mathbb{F}\_2^n$. The problem is thus reduced to pick the element corresponding with minimal cost from that subspace. Alas, that subspace may be quite large, and indeed, rewriting $f$ in binary $k\times n$-matrix form, with a $1$ for each $x\_{r\_{ij}}$ at the $i$-th row and the $r\_{ij}$-th column, and zero otherwise, we get a cost minimization problem subject to $$Ax=1,$$ where $A$ is said matrix, $x$ is the column vector consisting of the $x\_1,\ldots,x\_n$ and $1$ is the all-1-vector. This is an instance of a binary linear programming problem, which are known to be NP-hard in general. So the question is, is it NP-hard in this particular instance as well?

# Answer
> 13 votes
A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}\_2$, and an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$.

You can reduce this problem to your problem. The system $Ax = b$ is equivalent to the conjunction of equations of the form $x\_{i\_1} \oplus \cdots \oplus x\_{i\_m} = \beta$. If $\beta = 1$, this equation is already of the correct form. If $\beta = 0$ then we XOR an extra variable $y$ to the right-hand side, and then we force this variable to be $1$ by adding an extra equation $y = 1$. We define the weights as follows: $y$ has weight $0$, and the $x\_1$ have weight $1$. We have now reached an equivalent formulation of maximum likelihood decoding which is an instance of your problem.

---
Tags: optimization, np-hard, satisfiability, integer-programming, xor
---


title: Standard definition of Turing machine

text:
# Question
Title: Standard definition of Turing machine
I have followed two famous book on "Automata and Formal Language Theory":

1. Micheal Sipser's book
2. Jeffrey Ullman and John Hopcroft's book

in both books, tuple level definition of Turing machine differs with each other. Although abstract level working are same but details are different. **Why there is not any standard definition?** Even some other books have explained the Turing machine in different way.

When we try to measure time complexity of same algorithm on these machines, exact time also differs. Why the authors/scientist have not agreed upon one standard definition?

# Answer
There is no standard definition since it is uncommon to use the details of the definition of Turing machine. In contrast to other definitions in mathematics, Turing machines are complicated objects whose definition is unwieldy to use directly. Instead, we invoke the Church–Turing hypothesis and describe Turing machines by giving algorithms rather than listing tuples. At this point, the exact definition of Turing machine is unimportant.

A similar situation occurs in other cases, of which I will describe two: *number systems* and *forcing*.

**Number systems**, especially the real numbers, have several different constructions. If you look at books containing a construction of the real numbers, you are likely to see different constructions, in some cases vastly different ones (for example, Dedekind cuts versus Cauchy sequences). However, from the point of view of the user, all we care about is that the real numbers we construct satisfy the field axioms as well as being complete and Archimedean (the exact meaning of these terms is unimportant). We almost never get to use the actual underlying definitions.

**Forcing** is an important proof technique in set theory. Forcing can be defined in several different ways, the most popular being forcing relations and Boolean-valued models. (A less popular one is modal logic.) These methods are all equivalent, but the formal development can be somewhat different. All of these methods lead to the same proofs in set theory, but there is no "official" one. Which one you choose to present in a set theory textbook or course depends on your personal taste.

The exact definition of Turing machine does matter if you're interested in exact resource consumption, say, how many steps does it take to solve a certain problem. Since all reasonable definitions of Turing machines result in the same running times *up to constant factors*, and since we don't usually care about constant factors per se, the exact definition doesn't matter and yields the same results.

The same situation occurs when proving other theorems in which the Church–Turing hypothesis cannot be used. For example, when proving Cook's theorem that SAT is NP-complete, we really need to refer to the definition of Turing machine; but the construction will work for many different definitions, in much the same way. We pick one definition arbitrarily and stick to it, knowing that using any other variant will result in a slightly different yet still valid proof.
> 12 votes

# Answer
This happens often; for instance, there are several definitions of finite automata around.

There are two things we are usually interested in in models of computation (and in TCS):

1. computational power and
2. cost measures.

If 1. is the same and 2. only differs insignificantly (complexity theorists would say, by a polynomial/polylogarithmic/constant/... factor), we may switch between (approximately) equivalent definitions.

The conditions can be proven formally, provided the models are formally defined. It may be an illustrative exercise for you to do this.

*Why* have different definitions then? Because one or the other proof may be easier, or one or the other concept more neatly described. Therefore, the goal of a course/book, the selection of topics, the author's didactic approach and taste may cause one definition to work better than another.
> 5 votes

# Answer
I will try to take a slightly different approach than the other answers, and examine in particular the standardisation issue.

It is a bit surprising that you wonder about this situation. The Hopcroft-Ullman book (I use the 1979 edition) gives two definitions of PushDown Automaton (PDA): acceptance by final state or by empty stack.

If you read the section on Turing Machines (TM) construction techniques (section 7.4 in 1979 edition), they explicitly state:

> Designing Turing machines by writing out a complete set of states and a next-move function is a noticeably unrewarding task. In order to describe complicated Turing machine constructions, we need some "higher-level" conceptual tools.

The rest of the section, and the following sections, show all sorts of variations on the definition of a TM, extending or limiting the definition, that are all equivalent.

The point is that, for each problem at hand, we will choose the one definition that is best adapted too solving that problem. Of course, each of these definition could do in principle. But depending on the issue, some definitions will give you more perspicuity on a specific problem, and thus make the proofs easier.

Considering the case of Context-Free (CF) languages and grammars, there are many normal forms that have been defined: Chomsky Normal Form, Greibach Normal Form, Binary form. All can generate any CF language, and they could be seen as variations of CF grammar definition. It is good to have them coexist, because each as a role to play in some context. They are intertranslatable, but at cost.

If you try to analyze the cost/complexity of CF parsing they are not equivalent, and this is to be taken into account. This complexity issue is much more critical in the CF case than it is for TM, because CF parsers are used a lot in engineering situations, while TM are a purely theoretical tool. This does not prevent engineers using CF parsing from using various grammar forms for the same language, in some coordinated way, in order to take various issues into account.

In the case of CF languages, it can be a critical **engineering issue**, and it was thus to be expected that CF gramars, and their different forms would be normalized/**standardized** about as much as the size of wrenches or the diameter of electric wires. Actually it went as far as defining a precise syntax for writing CF grammars, the Backus Naur Form (BNF).

TM have few engineering applications that would justify normalization, and they have much greater potential variability (which is however partially taken into account by considering majors variations such as multi-tape, multi-head, ...). This explain that there was little pressure to adopt a standard form, given that mathematicians who use them are supposed to be technically mature enough to be careful when it can make a difference, such a counting precisely the number of moves. Even for complexity, the small variations in definitions often do not matter, because we consider only asymptotic complexity, and often asymptotic complexity up to a polynomial function.

It is quite common in mathematics (among other sciences) that different authors will choose different definitions, that are know to be equivalent (or equivalent in most context), depending on their taste, their view of applications, their vision of the problem structure, their pedagogical purposes, etc. Definitions also evolve with time as more gets known about a problem, and as perspectives change. The same goes for notations. This variability is an important source of progress and understanding. The Greeks were doing excellent mathematics, but it is a lot easier with modern concepts (e.g. variables), definitions and notations.

Standards are often seen as extremely convenient (cf wrenches and wire diameters). But they can also a factor of rigidity that prevent progress. Standardization is a double edged sword, so we must blunt it a little bit for safety. The various definitions are usually not quite identical, but close enough so that theories can develop more or less in the same way.
> 5 votes

---
Tags: terminology, turing-machines
---


title: Cases of Master Theorem

text:
# Question
Title: Cases of Master Theorem
Suppose that we have $ \\ T(n)=\left\\{\begin{matrix} c, & \ \text{if } n\<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$

The Master theorem is the following:

1. If $f(n)=O(n^{\log\_b a- \epsilon})$, then $T(n)= \Theta(n^{\log\_ba})$
2. If $f(n)= \Theta(n^{\log\_b a} \log^k n)$, then $T(n)=\Theta(n^{\log\_ba}\log^{k+1}n)$
3. If $f(n)=\Omega(n^{\log\_b a+ \epsilon})$, then $T(n)= \Theta(f(n))$, provides $af\left(\frac{n}{b} \right) \leq \delta f(n)$ for some $\delta\<1$ for all $n \geq d$.

**Proof**:

Using iterative substitution, let us see if we can find a pattern:

$$T(n)=aT\left( \frac{n}{b}\right)+f(n)=a \left(aT \left(\frac{n}{b^2} \right) +f\left( \frac{n}{b}\right)\right)+f(n)= \dots\\\= a^{\log\_bn}T(1)+ \sum\_{i=0}^{(\log\_bn)-1} a^i f\left( \frac{n}{b^i} \right)=n^{\log\_b a} T(1)+ \sum\_{i=0}^{(\log\_b n)-1} a^i f\left(\frac{n}{b^i} \right)$$

We then distinguish the three cases as

* The first term is dominant
* Each part of the summation is equally dominant
* The summation is a geometric series

Don't we have to explain further which case correponds to which of the following cases

* The first term is dominant.
* Each part of the summation is equally dominant.
* The summation is a geometric series

and justify why it is like that? How could we justify it?

# Answer
The three cases correspond exactly to the three cases in the statement of the theorem. Let's consider them one by one. Suppose for simplicity that $T(1) = 1$.

**Case 1.** Suppose that $f(n) = n^\delta$, where $\delta \< \log\_b a$. Then $$ T(n) = n^{\log\_b a} + \sum\_{i=0}^{\log\_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta \< \log\_b a$, we have $b^\delta \< a$ and so $a/b^\delta \> 1$. Therefore $$ \sum\_{i=0}^{\log\_b n-1} \left(\frac{a}{b^\delta}\right)^i = \left(\frac{a}{b^\delta}\right)^{\log\_b n} \sum\_{j=1}^{\log\_b n} \left(\frac{b^\delta}{a}\right)^j = \Theta(n^{\log\_b a - \delta}), $$ since the geometric series $\sum\_j (b^\delta/a)^j$ converges, and $\log\_b (a/b^\delta) = \log\_b a - \delta$. We conclude that $$ T(n) = n^{\log\_b a} + \Theta(n^{\log\_b a - \delta} n^\delta) = \Theta(n^{\log\_b a}). $$ (So it is not quite true that the first term is dominant.)

**Case 2.** Suppose that $f(n) = n^{\log\_b a}$ (this is the case $k = 0$; the case $k \> 0$ is similar though slightly more complicated). Then $$ T(n) = n^{\log\_b a} + \sum\_{i=0}^{\log\_b n-1} \left(\frac{a}{b^\delta}\right)^i n^{\log\_b a}. $$ This time $a = b^\delta$, and so each summand is equally dominant, leading to $$ T(n) = n^{\log\_b a} + (\log\_b n) n^{\log\_b a} = \Theta(n^{\log\_b a} \log n). $$

**Case 3.** Suppose that $f(n) = n^\delta$, where $\delta \> \log\_b a$. Then $$ T(n) = n^{\log\_b a} + \sum\_{i=0}^{\log\_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta \> \log\_b a$, we have $b^\delta \> a$, and so $a/b^\delta \< 1$. Therefore the geometric series $\sum\_i (a/b^\delta)^i$ converges, implying that $$ T(n) = n^{\log\_b a} + \Theta(n^\delta) = \Theta(n^\delta). $$

---

These proof sketches serve to explain that proof hints. However, they're not a complete proof, for two reasons. First, I assumed that $f$ has a specified form rather than a specified order of magnitude. Second, there is a tacit assumption that $n$ is a power of $b$. With more work we can take these points into account and prove the complete theorem. (A third and more minor point is the base case – you have assumed a base case of $1$, whereas the theorem calls for an arbitrary base case.)
> 3 votes

---
Tags: proof-techniques, recurrence-relation, master-theorem
---


# Question
Title: Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?
Suppose $\Pi$ is a decidable decision problem.

> Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?

Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?

# Answer
If you assume that $\mathsf{NP}\neq\mathsf{coNP}$ then any coNP-complete problem gives a counterexample. I would guess that one can refute your conjecture unconditionally.
> 5 votes

# Answer
If $P=NP$ then

$\Pi \not\in NP$
$\implies$
$P=NP$ and $\Pi$ is neither the empty language nor the full language
$\implies$
$\Pi$ is $NP$-hard.

Let $\operatorname{int}(s)$ denote the result of putting a leading 1 on the most significant end of $s$ and then parsing the result as an integer in binary.

If $P\neq NP$ then for each subset $S$ of $\\{0,1\\}^\*$ that is not in $\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$,
$\\{111 \ldots \[2^{\operatorname{int}(n)} \text{ of them}\] \ldots 111 : n\in S\\}$ is not in NP since $S$ is too hard, is decidable if and only if $S$ is, and is not NP-hard even with respect to Turing reductions since for any polynomial bound, there are only polynomially many possibilities for the subset of that language consisting of the elements that fit within the length bound, so one could try the search-to-decision reduction with each of them.
> 3 votes

# Answer
Completeness for a class means it is universal for the class, i.e. other problems in the class can be solved using it. If there is a difficult problem in a class then all universal problems for the class will also be difficult. But the reverse does not hold: difficulty does not imply universality. E.g. the fact that a problem cannot be solved in polynomial nondeterministic time does not imply that it is NP-complete (i.e. universal for NP).

For NP: if P=NP all problems except trivial ones will be complete for NP (under Karp reductions). So assume P is a proper subset of NP (or alternatively use a weaker notion of reduction like AC0).

Consider a unary language which is outside NP. (It is an easy exercise to show there are unary languages of arbitrary difficulty.) The language cannot be complete for NP by Mahoney's theorem.
> 2 votes

---
Tags: complexity-theory, np-hard, complexity-classes, np
---


# Question
Title: Prove L and {0,1}*-L are recursively enumerable
Exercise ask : Prove which a binary language L is recursive if and only if both ***L*** and {0, 1}\* - L are recursively enumerable.

Now I try to give a solution: Suppose that L is recursively enumerable.Then, would exist two machines M and M' such that simulate M and M' at alternate steps on two copies of the input x. For all the x that belong to A\*({0-1}*), at least one of the two machines M and M' would stop given that x € L xor x € A* \- L. If M' would stop then M" decide as M' while if M would stop then M" contradict M. It would follow that M" decide A\*-L in contradiction with hypothesis.

Help me, I don't understand almost nothing on this part,I have a prof. incompetent, he has teach much bad with little theory and zero exercises.

# Answer
> 2 votes
In one direction (the one you don't mention) this is easy. If $L$ is recursive then $L$ is recursively enumerable since we can go over all possible strings $x$, for each of them check whether $x \in L$, and output those which satisfy $x \in L$. A similar approach enumerates $\overline{L}$.

For the other direction, suppose you have a machine $A$ enumerating $L$ and another machine $B$ enumerating $\overline{L}$, and we want to construct a machine deciding $L$. Here is what we do. On input $x$, we run the machines $A$ and $B$ "in parallel", and observe the strings that they output. Eventually one of them outputs $x$. If $A$ output $x$, then $x \in L$; if it was $B$, then $x \notin L$.

The Turing machine model is sequential, so how do we run $A$ and $B$ in parallel? We simulate one step of $A$. Then we simulate one step of $B$. Then we simulate one step of $A$. Then we simulate one step of $B$. And so on. The result is as if we ran $A$ and $B$ in parallel. (This is very similar to how parallel threads are simulated on a single core; the main difference is that to improve efficiency, we run each of the threads many steps at a time.)

---
Tags: computability, turing-machines
---


# Question
Title: Algorithm(s) for creating balanced 5-a-side teams?
I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than others.

The best matches are the ones where the score stays even throughout the game because they are the most competitive. Our rules are as following: first team to score 5 goals gets 1 point then the goals count resets.

The problem is figuring out how to pick balanced teams. I am going to program a script to log teams and scores over time and I am wondering what algorithm(s) can I use to generate the teams based on this history keeping in mind that we wont always have the same 10 players but we might have the same 8 players, etc?

# Answer
This is a modelling question. One plausible model might be as follows. Each player as a strength, which is a real number. The strength of a team is the sum of the strengths of the players on the team. If team A plays team B, then team A will win with probability $f(s\_A - s\_B)$, where $f$ is the logistic function, $s\_A$ is the strength of team A, and $s\_B$ is the strength of team B.

This is an example of a possible model. It might or might not be a good model. But if we assume this model is correct, then it is possible to infer the approximate strength of each player, given the outcomes of a bunch of matches. If $s$ is a vector that describes the strengths of all players, define $L(s)$ to be the likelihood of this vector. In particular, $L(s)$ is formed by computing the product of the likelihood for each match that was played. To compute the likelihood of a match between $A$ and $B$, you use $s$ to calculate the probability $p$ that A wins (assuming $s$ is the correct strength); if A actually won, the likelihood of that outcome is $p$, otherwise it is $1-p$. (I assume there are no ties.) For any particular $s$, you can calculate the likelihood of each match outcome like this, multiply them together, and get $L(s)$. Now, to find the "best fit", you find the vector $s$ that maximizes $L(s)$. This is known as a maximum-likelihood method.

How do you find the vector $s$ that maximizes $L(s)$? Basically, you use some mathematical optimization method, like gradient descent.

If you assume this model is correct, another procedure to find the strengths of the players would be to use logistic regression. However, ultimately this will end up being equivalent to what I articulated above.

Of course, you might find that the model I outlined is not a good model. In that case, your task is to find a better probabilistic model that describes the probability that team A will beat team B, as a function of the strengths of the players. Then, you can use the techniques sketched above to infer the strengths of each player.

Finally, once you have the strength of each player, the probabilistic model will let you evaluate different ways of assigning people to teams and figure out which one is most balanced (where the probability of winning for team A is as close to one-half as possible).

This approach assumes you only take into account who won, but not the score. It would be possible to consider more sophisticated probabilistic models that also try to describe the distribution of scores as a function of the strengths of the players, but this will be more complex. I suggest you stay simple for now.

---

You could also look at the Elo rating system and research whether there's any way to generalize it to apply to your setting, where each team has multiple players and you want to rate the strength of each individual player.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Notation for asymptotic bounds on both sides
I am writing my first paper, and one of the results can be written as follows:

> For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and $\epsilon=\omega\left(\frac{\log\log W}{W}\right)$, we obtain a $o(\min \\{W, \frac{1}{\epsilon}{\log^2 W}\\})$ space algorithm, improving the state of the art.

Is there some standard notation, say $\Gamma$, so I could write:

> For any $W$ and $\epsilon=\Gamma\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)$, ...

?

Will appreciate any help !

# Answer
I'm also not aware of any specific notation for the concept you want. In the example theorem statement in the question, there's nothing wrong with what you already have ("$\epsilon$ such that $\epsilon=o(\cdots)$ and $\epsilon=\omega(\cdots)$"). In other situations, it might be more convenient to say something like, "For any $\epsilon\in o(\cdots)\cap\omega(\cdots)$".
> 3 votes

# Answer
I have seen a "$o$-relation" (asymptotic dominance), namely

$\qquad\displaystyle f \prec g \iff f \in o(g)$.

This allows you to write

$\qquad\displaystyle \frac{\log\log W}{W} \prec \epsilon \prec \frac{\log^4 W}{W\log\log W}$,

which reads more in line with $\leq$-bounds while denoting the asymptotic flavor of the bound.

Note that $\epsilon$ is usually used for constants while you use it as a function in the input $W$. This may be confusing for some readers, at least if it is not standard in your particular subfield.
> 3 votes

# Answer
No, I'm not familiar with any such notation. I suggest you stick with what you have: it should be understandable to your audience. And isn't that what we care most about -- communicating clearly?
> 2 votes

---
Tags: asymptotics, notation
---


title: A metaphor for recursive enumerability

text:
# Question
Title: A metaphor for recursive enumerability
In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said **"I know it when I see it."** It struck me that this was a pretty good description of recursive enumerability (recognizability): he was asserting that he was a recognizer for the set of all creative events, broadly construed, that were pornographic. By saying that he wouldn't, and perhaps couldn't, define pornography, he was saying that as far as he was concerned, pornography was not recursive, in that while he could answer "yes" to the question "is this work pornographic?" he couldn't correctly answer "no" in all cases, saying, in effect, that the set of pornographic events wasn't recursive (decidable). In short, he claimed, metaphorically, the set *PORN* was in $RE\setminus R$.

Pedagogically, this metaphor might work well as an aside when I introduce $RE$ and $R$ to my students, but I'm not entirely happy with it, since it seems feasible that another jurist might very well assert that s/he could indeed determine, for all possible creative events, $e$, whether $e$ was not pornographic. The question is, is there a "tighter" real-world metaphor, where we could agree that determining whether $e$ is a member of $P$ is obviously possible, but determining that $e\notin P$ for all $e$ is obviously impossible?

# Answer
I was first taken by your metaphore, but I do not think it works. Actually he is saying that he is himself a decision procedure, though he cannot describe his own internal program. Hence Justice Stewart decisions are recursive, not recursively enumerable, at least where pornography is concerned. I would indeed expect anyone capable of such an arrogant statement to be computationally limited.

Now for other examples taken from the real world, the first that comes to mind is actually co-RE, though that amounts to the complement being RE. It is the buggy program problem. If a program has a bug, it will show some day, provided we use it long enough. But we cannot be sure thre are no bugs, even when none has been found. Well, that was before we could prove program correct (not that we are really there yet).

A close problem is falsifiability of scientific theories, as defined by Karl Popper. The idea is that science is primarily co-RE:

A theory in the empirical sciences can never be proven, but it nust be falsifiable, meaning that it can and should be scrutinised by decisive experiments that could prove it wrong.

In other words, all we can know for certain, is that some empirical science theories are false, because some consequences have been experimentally proved false.
Whatever remain might be good theories, unless later proved false.

False theories form a RE set. Good theories are the co-RE complement.

But I am not sure this last example will make things clearer for your students.

And the relations between scientific theories, or their correctness status are a bit more subtle than that.

**P.S.** I think mortal people form an RE set.
> 5 votes

# Answer
I find that the simple computer program analogy works very well:

Let's say you enter a command or start some program (with some particular input) on your computer, and suddenly the screen freezes.

You know very well that it might start running soon and give you the answer, but on the other hand, it might simply be in an infinite loop (or appear to be in one) or have crashed, or simply not return the answer in a very long while ... Should you force stop it?

This also reminds me of a blog post Thore Husfeldt wrote, *The Freeze App Does Not Exist*.
> 3 votes

# Answer
I find that the concept occurs frequently in every day life. Some examples:

* Choosing a partner. You'll never know if you have found the "best" potential partner, but it's often easy to decide "not this one".
* When to buy a new car (or mobile, PC, ...). If you buy *now*, the next generation may be slighlty better, or cheaper.
* "Turn left at the second to last crossing" -- you only know which one after you've driven to the end.

In more abstract terms, we usually act as *online algorithms* in the real world. An algorithm that wants to decide something about a function has to work similarly: it can only walk over the domain for a finite time until it has to make a decision (marry somebody, buy a car). A semi-decider can keep walking but may not decide at all (stay single, travel by bus).
> 2 votes

# Answer
> The question is, is there a "tighter" real-world metaphor...?

here is a simple straightforward analogy that has "nearly" actually been used in the literature in different places/ ways. depending on reception will come up with others less direct. it has the advantage that it also extends to all languages even the decidable ones.

imagine a guru on a mountain who answers your questions. you ask him a question and he will have an answer. but the time between you asking and when he answers is variable. there are different classes of questions expressed as symbol/ word statements from "languages" in computer science.

some languages can be "recognized" quickly by the guru, in other words he *always* answers questions in those languages. some can even be "efficiently recognized". these are called P. others are thought to be not recognizable efficiently but nobody has a proof of that. those are called NP.

there are languages that take a "long time" to recognize by the guru (questions in the language take long or unpredictable amounts of time) but are still recognizable, and the guru still *eventually* comes up with answers. these are called decidable. there is a timing/ space hierarchy of such languages but thats another metaphor.

then there are languages that exist where the guru answers some of the questions, but not others. but the timing is impossible to determine on the unanswerable questions. the unanswered questions have no time limit. that is to say, if the guru answers, it may take him days, months, years, or very long stretches of time to answer. there is absolutely no time limit "rule" that one can use to say definitively "if the guru has not answered in *x* time then he will never answer". there is no way to know, waiting, whether a nonanswer will ever eventually turn into an answer or not. these languages are called "undecidable".

exercise for reader: now describe coNP. :)
> 0 votes

---
Tags: computability, didactics
---


# Question
Title: Why the given lexical specification will not process the following strings?
I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question.

Here is the question:

> Given the following lexical specification:
>
> $(00)^\*$
> $01^+$
> $10^+$
>
> Which strings are NOT successfully processed by this specification?
>
> 1. $0111110$
> 2. $01100110$
> 3. $0001101$
> 4. $01100100$

The correct answers are 1 and 2. But I can't figure out why. How do I interpret this lexical specification? Can someone help me out with this.

# Answer
**The strings not processed successfully are 1, 2, and 3.** Only string 4 is processed successfully.

I think your problem is not with interpreting the meaning of regular expressions, but in understanding the process of lexical analysis, at least as intended in your course.

Normally, a regular expression is supposed to match a string from beginning to end. But when doing lexical analysis of a program, you are supposed to cut the program text in small chunks coresponding to the lexical elements of the language, which in turn can be taken (up to some details not relevant here) as the terminal alphabet of the (usually Context-Free) grammar used to define the language you are parsing.

So, during lexical analysis, you have nothing to indicate the end of a lexical element, as the program text goes on to give the next lexical element. For example, if you are scanning the string $foobar$, is it the identifier $f$ followed by $oobar$, or $foo$ followed by $bar$, or $fo$ followed by $oba$ and $r$. For a strict lexical point of view, all these possibilities would be correct ... though the grammatical parser that will use the lexical element can be unhappy with some choices.

To simplify matters, a simple rule is often followed by scanners performing lexical analysis, called maximal munch rule, or longest match rule. It works as follows:

While recognizing a lexical element, the lexical analyzer will keep reading the input string as long as it is reading a prefix of a lexical element, according to the lexical specification, and will halt when the next symbol to be read would no longer constitute such a prefix if added to the part of the input already scanned. At that point, if the scanned string corresponds to a complete lexical element (i.e. the scanning automaton is in an accepting state), this lexical element has been recognized. If it is only a prefix of a lexical element that cannot be completed with what follows into a proper lexical element, you have a lexical analysis error.

Thus with your example 1, $0111110$, the lexical analyser will start recognizing the second regular expression $01^+$, and will scan $011111$ as one lexical element. Then it is left with only $0$ which is the prefix of a word in the first two regular expression $(00)^\*$ and $01^+$. But then the string stops, so that it cannot be part of a complete lexical element. hence the lexical analysis fails with an error at that point.

You could say that if you had stopped the first lexical element one symbol earlier, thus recognizing $01111$. Then you would be left with $10$ which is recognizable by the third regular expression $10^+$. But that is not how things work. There is no backtracking (actually, some scanners have more complex rules allowing for some backtrack, for example for the programming language C). Allowing this would also make thigs a lot more ambiguous as I explained in the $foobar$ example.

In the second example $01100110$, you get $011$, then $00$, and you are left with $110$. The first $1$ is a prefix for the regex $10^+$, but it should then be followed by at least one $0$, which is not there. Hence lexical analysis fails.

However, the third example $0001101$ should fail too. The reason is that symbols are read one by one. The first $0$ is a prefix for both regex $(00)^\*$ and $01^+$. But, on scanning the second $0$, we know we are looking for a lexical element defined by the forst regex $(00)^\*$. Then the third $0$ is ok too, since $000$ is a prefix of $0000$ which is recognized by the first regex. So it is scanned. But now we need a $0$, and we find a $1$. So the lexical analysis fails.

My guess is that the designer of the exercise recognize too quickly that it could work, by stopping one $0$ early (and I did too the first time I read this). But the computer does not have this global perception, and proceeds one symbol at a time.

The fourth example $01100100$ works fine, yielding $011$, $00$, and $100$.

**If backtracking were allowed**, all four strings could be scanned into lexical elements.

But the fourth string could then be scanned as:

* $011$, $00$, $100$, or
* $01$, $10$, $01$, $00$

Though you can use a rule that you backtrack only in case of failure, to avoid such an ambiguous situation.

*Of course, there is the possibility that your instructor defined things differently, but this is the best I can do with the information I have.*
> 2 votes

---
Tags: regular-expressions, compilers, lexical-analysis
---


# Question
Title: Can this language be defined by a Context Free Grammer?
I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt:

Question: $L = \\{a^n b^m c^p \mid n = m + p + 2\\}$

```
My Attempt:

S -> aaBC

B -> aBb | ^

C -> ?  (Now how can i increase length of `a` Terminal by C as i increased from B)

```

Is this language not context free / impossible ?

# Answer
You'll need to "wrap" the Bs in the Cs:

```
S -> aaC
C -> aCc | B
B -> aBb | ɛ

```

With that, we have

$L(B) = a^m b^m$,

$L(C) = a^p \cdot L(B) \cdot c^p = a^p a^m b^m c^p$ and

$L(S) = a^2 \cdot L(C) = a^2 a^p a^m b^m c^p = a^{m+p+2} b^m c^p$.
> 5 votes

# Answer
As noted by Raphael in one of the comments an appraoch to this question is given in one of the reference questions: "How to prove that a language is context-free?".

Try to write the language in such a way that the nesting structure can be handled by a CFG.

$L=\\{a^nb^mc^p\mid n=m+p+2 \\} = \\{a^{m+p+2}b^mc^p\mid m,p\ge 0 \\}$

This does not work, so reorder:

$L=\\{a^{p+m+2}b^mc^p\mid m,p\ge 0 \\} = \\{a^pa^ma^2 b^mc^p\mid m,p\ge 0 \\} $.

Then apply nesting, peeling the layers of the string like an onion.

$S\to aSc$, $S\to T$, $T\to aTb$, $T\to a^2$.
> 2 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Do functional algorithms require more memory than imperative algorithms?
Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example.

The imperative approach would as follows:

```
wordcount = {}
for word in words:
    wordcount[word] += 1

```

The functional would be:

```
uniquewords = set(words)
wordcount = [words.count(w) for w in words]

```

For each word w we are doing a full scan on the words array, while the imperative approach goes over each word just once. Am I right to suppose that the functional way of doing it will consume a lot more resources than the imperative one?

# Answer
Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in `words` and behind the scenes `set(words)` is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses imperative features dressed up as functional programming. Have a look at Ocaml or Haskell.

As for your question, people have thought about just how efficiently one can implement functional programs on standard hardware (which I think is what you're asking). At LICS 2015 the following paper has been accepted:

> B. Accattoli, C. Sacerdoti Coen. On the Relative Usefulness of Fireballs. LICS 2015.

In it the authors show that a RAM machine (standard hardware) can simulate $\lambda$-calculus (functional programming) with a linear-time overhead with respect to the number of computation steps ($\beta$-reductions) of the functional program. This shows that functional programs can be efficiently implemented on existing hardware and will *not* in general consume a lot more resources.

Let me also point out that you cannot make the comparison you're trying to make in a sensible way. You are comparing two *different* algorithms that compute the same function. Instead, you should be comparing two *implementations* of the same algorithm in an imperative and a functional style. For instance sorting algorithms would do. And you should use a language that supports both imperative and functional programming. For instance, we could take merge sort and use the rosettacode.org functional implementation of merge srot in OCaml. Perhaps someone has the time to play with this and post some comparisons.
> 7 votes

---
Tags: functional-programming, performance, programming-paradigms, imperative-programming
---


title: Computing FIRST and FOLLOW sets

text:
# Question
Title: Computing FIRST and FOLLOW sets
Suppose we have the following grammar:

```
S -> A ( S ) B | ε
A -> S | S B | x | ε
B -> S B | y

```

where `S` is the start symbol, `S, A, B` are non-terminal symbols, `x, y, (, )` are terminal symbols, and `ε` is the empty string.

I'm trying to compute the `FIRST()` and `FOLLOW()` sets of `S`, `A`, and `B`.

```
FIRST(S) = FIRST(A ( S ) B) ∪ {ε}
FIRST(A) = FIRST(S) ∪ FIRST(SB) ∪ {x} ∪ {ε}
FIRST(B) = FIRST(S B) ∪ {y}

```

How can I compute `FIRST(S)`, since I don't know what the `FIRST(A)` is? How should I attack the problem? Any ideas?

# Answer
If you just keep applying FIRST, it not hard to understand where to stop.

FIRST($\mathtt{S}$) = FIRST($\mathtt {A(S)B}$) ∪ {ε}

In your example, FIRST($\mathtt{A}$) includes ε, so

FIRST($\mathtt{S}$) = FIRST($\mathtt {A}$)\\{ε} ∪ FIRST($\mathtt {(S)B}$) ∪ {ε} = FIRST($\mathtt {A}$)\\{ε} ∪ {$\mathtt{(}$} ∪ {ε}

Now, as FIRST($\mathtt{A}$)\\{ε} = FIRST($\mathtt{S}$)\\{ε} ∪ FIRST($\mathtt{SB}$)\\{ε} ∪ {$\mathtt{x}$}, then

FIRST($\mathtt{S}$) = FIRST($\mathtt{S}$)\\{ε} $\cup$ FIRST($\mathtt{SB}$)\\{ε} ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

Notice that the appearances of $\mathtt{S}$ on the left side are redundant here, so we get (again, because FIRST($\mathtt{S}$) includes ε):

FIRST($\mathtt{S}$) = FIRST($\mathtt{B}$)\FIRST($\mathtt{S}$) ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

The end result is FIRST($\mathtt{S}$) = {$\mathtt{y}$, $\mathtt{x}$, $\mathtt{(}$, ε}
> 1 votes

---
Tags: formal-grammars, compilers
---


title: What exactly is computation?

text:
# Question
Title: What exactly is computation?
I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition.

`Dictionary.com`'s definitions of computation, computing, calculate, and compute are circular, so it doesn't help.

`Wikipedia` defines computation to be "any type of calculation that follows a well-defined model." It defines calculation as "the deliberate process that transforms one or more inputs into one or more results, with variable change." But it seems this definition includes many actions as computations even though they aren't typically thought of as computation.

For example, wouldn't this entail that, say, a bomb exploding is a computation, with the input being the fuse being lighted and the output being the explosion?

So, what exactly is computation?

# Answer
Perhaps the problem here is looking a for a highly specific definition of a very general concept. I don't see the problem of viewing virtually everything as a computation. Although we don't think about it, everything we do is expressible in terms of the Physics of the component parts, down to at least quarks buzzing about. We have the same situation with computation. There's inputs, outputs and a process (all of which could be trivial). Whether they're *interesting* or *useful* as computations or models of computation is a very different question.

The strongest working definition we have comes via the (strong) Church-Turing Thesis, which states that every possible *physically realizable* model of computation is no more powerful than a Turing Machine. If you believe that this is true, then although we may have lots of way to express things, ultimately we can reduce every computation to a Turing Machine, hence giving a *definition* of computation as "anything we can reduce to a Turing Machine".

In this model, the exploding bomb is a computation. It's not a widely applicable one (we hope ;) ), but we can model in some fashion with a Turing Machine (though there is an argument here about the nature of the output and the equivalence with the TM's output). It's also not a good model of computation in general, in that it seems unlikely that the exploding bomb model is Turing complete.
> 6 votes

# Answer
This is the question that Turing set out to solve in his famous 1936 paper, On computable numbers, with an application to the Entscheidungsproblem, a paper in which he comes up with (what came to be known as) the Turing machine model. See in particular Section 9.

Turing's work is in the context of computable *numbers*. There are other notions of computation appropriate for computing other kinds of structures, and their study forms part of computation theory (also known as recursion theory).

The main difference between the common notion of computation and your example (an exploding bomb) is the thing being computed. What is being computed by your exploding bomb? Another difference is the computational means, but one can envision a mechanical contraption which uses bombs to compute something more legitimate.

Another point is whether the classical notions of computation apply to what we perceive today as computation – namely, two-way interaction between the computer and the user. This is a common criticism levelled against the classical notional of computability, though interaction can be modelled using the tools of computation theory (it's just not what you learn in class).
> 6 votes

# Answer
On it's most basic level, a computation is just a **mapping** between some set $A$ to some set $B$. every $x\in A$ is called *an input* and the computation maps this input to some output $y\in B$. The mapping needs to be defined on its entire domain: if some input $x\in A$ is not mapped by the computation, then the computation on $x$ is not defined.(1)

The other great answers in this thread try to plot the connection between this mapping and the method of achieving it. That is, they explain that to "compute" the output of some input $x$, we need a systematic, well defined method that takes us from an input $x$ to its output $y$. While true, this is not necessary to define computation. Indeed, if you encounter a Genie, and every time you give them a number $x$ they answer with $y$, then they compute something (even if this mapping is not recursive, and no computer can produce it).

In this very broad way to see computation, any physical device is a computer: it transfers the physical system at time $t=0$ (its input) to a different system at time $t=1$ (the output). Moreover, this computation is well defined (i.e., can be specified in a compact way, e.g., by unitary matrices). If you design the device properly, it can perform almost any (recursive) computation you desire. (Scott Aaronson talks quite a bit about "Can Nature compute problems", although his focus is mainly on NP-complete problems, this is very relevant to this discussion).

Bottom line: any mapping defines a computation. Any "device" that transforms an input to the corresponding output, performs ("computes") that specific computation.

---

(1) we can extend the discussion to these types of computations, which will make sense when you think on funcitons which are not recursive, but I prefer not to go there.
> 3 votes

# Answer
I will not attempt to define what a computation is, which was done rather well by Luke Mathieson and Yuval Filmus.

However, thinking about an exploding device as a computation lead me to an important side issue: if the explosion is a computation, then what does it compute? Other than a representation of the device after it has exploded.

What I am aiming at is that we can define fairly precisely what we consider to be a computation, and even what can be seen (contrived?) as one. **We can describe a computation. But can we tell what it is computing?**

Computation, as commonly defined, is a purely syntactic game. It is a game of physical structures that are being transformed according to precise rules. Since our only tool (up to standard transformations) for representing physical structures is ultimately the string of symbols, computation ends up being defined as some kind of formal transformations on strings of symbols. This is true of Turing Machines, lambda-calculus, partial recursive functions, and other less popular models. The word calculus (as in lambda-calculus) actually reflects this view as, in Latin, calculi are small stones used for representation.

But what this does not tell is what meaning is to be attached to this syntax, what it represents. Here is what little I think I understand, as I am not a specialist of such issues (so double check me). The problem is covered by model theory.

Given a formal system of representations, possibly associated with a logic (axioms and inference rules) or a computation system (transformation rules), a model of the formal theory is a mathematical stucture with components that follow these rules.

The same computation, or more precisely the same description of a computation can actually have many models corresponding to very different entities.

For example, a GCD algorithm describe a computation. But it may be interpreted on natural numbers, or on polynomials.

This is remindful of Bertrand Russell'quote:

> Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true.

The situation is pretty much the same for computation. It is a formal game, where the moves can be understood in many different ways. But there are actually deep ties between Mathematics formally defined by axiomatic systems and Computation Theory.

Computation, algorithmics, was defined to solve mathematical problems, and many of the modern concepts were thought of by logicians who were trying to understand the mechanisms that allow us to prove theorems, starting from axioms and applying inference rules.

Hence, to come back to the exploding device, it can certainly be construed as a manipulation of a representation, i.e. as a calculation. But it is generally pretty hard to associate to it any meaning other than itself.

However, this is not always true, or was not. The principle of analog computation relies on the idea that different representation system can be used for calculations that are related in some precise way. Then we can calculate with one system to have an idea of what the other sytem (too unwieldy to actually use, for example a universe :) would calculate in the corresponding setting.
> 1 votes

---
Tags: terminology, computability
---


# Question
Title: Since we need space for recursive calls, is the space complexity of the recursive factorial is n?
As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:

* In-place partitioning is used. This unstable partition requires O(1) space.
* After partitioning, **the partition with the fewest elements is (recursively) sorted first, requiring at most O(log n) space**. Then the other partition is sorted using **tail recursion or iteration, which doesn't add to the call stack**. This idea, as discussed above, was described by R. Sedgewick, and keeps the stack depth bounded by O(log n).

Now please consider the following method computing the factorial of `n` recursively:

```
private static int fact(int n) {
    if (n == 1) {
        return n;
    }
    return n * fact(n - 1);
}

```

There is no tail recursion. Does it mean that we need O(n) extra space for the call stack?

# Answer
> 5 votes
Yes, you need up to $n$ stack frames for the recursion. Therefore, you'll need $\Theta(n)$ space for these stack frames.

---
Tags: algorithms, recursion, space-analysis
---


# Question
Title: Why would a function be tabulated in advance and then retrieved?
Given some function and assuming no concern for the time to compute the co-domain for its domain, when might it be preferable to compute and tabulate in advance the co-domain results of the function, and then retrieve it from the table rather than compute it?

For example, if the domain for $f(x)=x^2$ were sufficiently small, why, if ever, would one wish to compute the co-domain and then, for a given x, retrieve the stored value of $f(x)$?

# Answer
> 3 votes
This sort of computation can be used for optimization purposes.

A classic simple example is computing the Fibonacci sequence. Apart from the base cases, $f(n) = f(n - 1) + f(n - 2)$, but then $f(n+1) = f(n) + f(n-1)$ and $f(n+2) = f(n+1) + f(n)$, and so on. So the value of $f(n)$ for each $n$ is used repeatedly. The effect is more dramatic if you use the naïve recursive algorithm.

This computation can be significantly optimized if we keep the values of $f$ that we have already computed and simply access the result as we need it.

If all we want to do is compute $f(n)$ for some $n$ once, this is already an observable improvement in the asymptotic running time of the algorithm (and it shows up very quickly in practice too). If we need to repeatedly use values of $f$ in a larger program, the improvement is even more effective.

Doing things like this form part of a technique called memoization, which is closely related with dynamic programming.

# Answer
> 3 votes
If your domain $X$ is ordered and small, the values in $f(X)$ are small as well and $f$ is expensive to compute, then there's a simple reason: efficiency.

For instance, if $X$ is a range of natural numbers, you can store the image of $f$ in an array and obtain $O(1)$-time "comptutation" of $f$ at the cost of $\Theta(|X|)$ memory (assuming that the size of $f(x)$ is bounded by some constant).

Of course, this only pays off if you need values of $f$ *often*, $f$ is particularly expensive, and/or you can access the values quickly¹. A compromise can sometimes be to compute the values lazily, but you'd still have to pay with memory up-front.

Note how the scenario parameters that enable you to resolve the trade-off can change over time.

1. In times without (universal) computers at every workstation, pre-computed tables for often used functions were indispensible. Logarithm tables, for example, were used in engineering disciplines.
2. With ever-faster computers in most offices, storage (both analogue and digital) was more sensitive. Efficient algorithms allow to re-compute values quickly enough.
3. Today, fast storage is cheaper than time and energy. Big players keep their data (which they concurrently update, all the time) in memory at all times in order to fulfill client queries as fast as possible. On the other end of the spectrum, mobile devices have to use their limited amount of energy conservatively, so storing (or pre-computing in times of energy abundance) beats re-computing.

So it's the same as ... all the time: inspect your situation, define your priorities, and pick the job for the tool.

---

1. Consider memory hierarchy. If you traverse the values and they lie unordered on the heap, you are in for a hellpit of cache misses which potentially nullifies the advantage (or turns it around on you).

# Answer
> 1 votes
**This is actually a centuries-old technique that was largely killed by computers**, but could possibly revive or still exist in some technical niche. It is even known to have been used by ancient Greek mathematicians and physicists.

The question asks why one would prefer to tabulate the results of a function, in a table indexed by its parameters, so as to replace computation by table lookup.

Of course, the minimum to expect is that table lookup is cheaper than computation of the result, but that is often the case with properly chosen data-structures.

The answer given by Luke Mathieson describes the best known case of function tabulation, which is memoisation, i.e. simply the preservation in a table of results that had to be computed previously, in case they are needed again.

Raphael argues that a systematic precomputing for a small domain can bring more efficiency to computations when the values are needed often, though, as he proposes lazy computation of the table, the difference with the previous answer is not too clear.

In a comment, I also suggested filling the table in advance, even with values not yet needed, when there is free/cheap computer time available for it.

But all this seems somehow restricted to a single program, which limits the usefulness of the effort.

However, the problem should probably be considered in a more general context, and has been in the past, before computers existed.

Complex calculations are an ancient problem in mathematics, sciences and engineering, and for a long time it was done by hand. These computations were used for all kinds of purposes, including astronomical (and astrological) predictions (including discovery of planets), computing tides, cartography and triangulation, compounded interest rates. In particular, logarithms were used to replace multiplication by addition, which implied using exponentiation on the results.

All these computations made use of hard to compute functions, such as trigonometric functions, logarithm, and others. So it became a business (and a very tedious job) to create precise tables for these functions, that were printed as books and sold to engineers and all people who needed them to conduct calculations. These were functions on the reals, and the tables were designed to reach a given precision, with some improvements using interpolation techniques. The tables were also designed so that they could be used reversibly: the same table could be used for logarithm and for exponential. These books were extremely valuable tools that one would keep around all the time. And they survived until the 1980's, when the microcomputers and especially sophisticated hand-held calculators became available, i.e. not much more than twenty to thirty years ago.

Using efficiently these tabulated functions was part of standard engineering curricula in universities and engineering schools.

Another way of tabulating functions was using a graphical form, called nomogram, nomograph, chart or abaque. They were tabulating a variety of complex functions used in exact sciences, either computed or obtained experimentally.

The formerly ubiquitous slide rule of engineers was yet another way of tabulating functions.

It could be that there are still useful functions that are too costly to compute with good precision, even with a standard computer. Then it can make sense to have them computed with powerful machines, then tabulated and made accessible, either on some memory device, or through the Internet. But I would not be enough in that kind of scientific work to know, and my search on the Internet was not fruitful.

---
Tags: algorithms, memoization
---


title: Divide-and-Conquer Exercise

text:
# Question
Title: Divide-and-Conquer Exercise
I need help on this question: Given a sorted array of distinct integers A\[1, . . . , n\], you want to find out whether there is an index i for which A\[i\] = i. Give a divide-and-conquer algorithm that runs in time O(log n).

How I can proceed? Thanks a lot!

# Answer
> 2 votes
Hint: Define $B\[i\] = A\[i\] - i$. What can you say about the array $B$? Use the fact that $A$ contains *distinct* integers.

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: Rewriting gates such as XOR into three basic gates?
How would I rewrite an XOR gate into the three basic logic gates (AND, OR, NOT). To be more specific, I have to write it in such a way with 2 NOT gates, 2 OR gates, and 1 AND gate. I also have to do it with 1 OR gate, 2 AND gates, and 1 NOT gate.

I'm not looking for just the answer, I'm looking for a way to come up with the answer.

Thanks!

# Answer
Hint: $a \oplus b = \neg \big( (a \land b) \lor (\neg a \land \neg b)\big)$ (you can't have both true and you can't have both false). Using De Morgan's, you should be able to break up the negation and the main $\lor$.
> 0 votes

---
Tags: logic, xor
---


# Question
Title: Understanding the definition of endless sets
In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise:

* I don't understand exactly, what an endless set is (I find it very hard to understand, maybe because of the "endless")
* I don't know, how I can prove that the given sets are endless

The definition given is this:

> A set $X$ is called endless set, if there is a endless family of sets $\\{X\_n\\}\_{n=0}^{\infty}$ with $... \in X\_3 \in X\_2 \in X\_1 \in X\_0 \in X$.

Can someone explain in simple words what an endless set is?

# Answer
Defining endless sets, you probably assume that you don't have the Axiom of regularity.

A set is endless when it doesn't contain only simple elements, it has to contain an other set among his elements, and this other set has again to contain an other set and this third set has to contain an other set, etc..

For example, a set verifying $M = \\{M\\}$ is endless because it contains an other set ($M$) which contains an other set (still $M$) which contains an other set ($M$), etc.. You can take $X=X\_0= X\_1= ... = M$ as infinite family.

A counter example is $M = \\{42\\}$; $M$ doesn't contain any set. $M= \\{42, \\{12\\}\\}$ is also a counter example because $M$ contains a set ($\\{12\\}$) but this set doesn't contain any set.
> 1 votes

---
Tags: terminology, sets
---


# Question
Title: Boat riddle as a combinatorial optimization problem?
I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: person $x\_m$ and $x\_n$ cannot sail together and cannot even stay on the same bank of the river or $x\_m$ and $x\_n$ always have to be together.

When I remembered this riddle, I thought whether it could be represented as an optimization problem. The criterial function would be $\min(\text{numberOfSails})$ and the conditions will be my limitations, but I am not sure whether I can model my problem like this (and I am not sure how to model all my conditions).

Could you tell me or give me a hint, how such an approach for modelling this program would look like?

At first I thought it could look something like this:

```
min i // i = number of sails
x_i1 + ... + x_i2 <= 2 // i-th sail can contain max 2 people
x_im + x_in <= 1 // x_m and x_n cant sail together
etc.

```

But there is so much wrong with this model (like considering the people left on the first bank or the people already transported) and so on, so I am not sure how to tackle this problem.

# Answer
> 3 votes
The river crossing problem using integer programming is solved by Börndorfer et al. in \[1\].

---

\[1\] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.

---
Tags: optimization, linear-programming, modelling
---


# Question
Title: How to express the predice c > 0 in linear programming constraints?
I want a constraint that: if c=0 become x=0 if c \> 0 become x=1 for example: C \< = M.X or
C\> = M.X or X=exp(-M\*C) that X is binary variable and M is huge value. This constraint is very important for me. Please help me.

# Answer
Such a constraint is impossible to express in a linear program. The set of feasible solutions of a linear program is *convex*: if $a,b$ are feasible solutions (assignments to all variables satisfying all constraints), then so is $pa+(1-p)b$ for all $p \in \[0,1\]$.

In your case, let us look at the values of variables $c,x$. One feasible solution is $(c,x) = (0,0)$, and another is $(c,x) = (1,1)$ (say). Therefore $(c,x) = (1/2,1/2)$ should also be feasible, contrary to your specification.
> 2 votes

---
Tags: integer-programming
---


title: The control in the Turing Machine

text:
# Question
Title: The control in the Turing Machine
My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the tape.

The following is an excerpt from Michael Sipser's Theory of Computation, the passage is about how a Turing Machine can find the leftmost Cell. What is written is pretty straight forward. But what I don't understand is the part written in bold.

> "A trickier method of finding the left-hand end of the tape takes advantage of the way that we defined the Turing machine model. Recall that if the machine tries to move its head beyond the left-hand end of the tape, it stays in the same place. We can use this feature to make a left-hand end detector. To detect whether the head is sitting on the left-hand end, the machine can write a special symbol over the current position **while recording the symbol that it replaced in the control.** Then it can attempt to move the head to the left. If it is still over the special symbol, the leftward move didn’t succeed, and thus the head must have been at the left-hand end."

What does he mean by this exactly? What does recording a symbol in the control mean? Isn't the only (and infinite) memory of the TM the tape?

# Answer
The state of the machine can be used as a finite memory. You can use the state to remember (or, if you prefer, "encode") what the last character you saw was, since there are only finitely many possibilities. If necessary, you can remember the last two characters, or ten or a million, as long as you fix the number at the time when the machine is designed.

What you can't do is remember an unbounded amount of information in the state. So you can't remember, for example, all the characters you've passed over since you last saw an '$a$', or even the number of characters since then.
> 8 votes

---
Tags: turing-machines, automata
---


title: How do I detect and rotate a square?

text:
# Question
Title: How do I detect and rotate a square?
I have recently written code for detecting path colors in a 2D grid and printing the corresponding path costs and it works fine for me. Here's my code; I am currently new to OpenCV and know only C++ (no python).

The image that I had for the project was:

Now I may get an image like this for the same task:

I need an algorithm to detect the square in the middle of the arena, rotate it to the angle by which it becomes like the image above, and then crop the rest of the image off.

I am currently at a fix about doing this.

# Answer
Since you asked for algorithms, I suggest you look at the Hough transform and other techniques for finding lines in an image. I suspect this will help you determine where the lines are, where the intersections are, and how much to rotate to recover the original image.
> 3 votes

---
Tags: image-processing, computer-vision, pattern-recognition
---


title: Data structure for ordered counted set

text:
# Question
Title: Data structure for ordered counted set
Is there a name for a counted set (multiset) that is ordered?

For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the items were added to the cart unless an item of the same type was already added in which case a number associated with item is incremented.

Is this a well studied data structure or just a specialized multiset? I imagine it could be represented with an internal data structure of a dictionary and an array.

# Answer
> 2 votes
Just use a regular dictionary (also dynamic set) and attach a counter to each entry. The `insert` operation then finds already existing entries and can increase the counter; similarly for `delete`.

If you want to search the literature, some sources (e.g. Algorithms by R. Sedgewick and K. Wayne (2011, 4th ed)) call the abstract data structure for multi sets a *bag*. This notion seems to be used in practice as well.

Note that some implementations will assume that you assign data to keys, and that the same key can occur multiple times with different data. In this case, using a counter is not enough, so these may not directly do what you want (since they may not even bother to detect duplicate keys).

---
Tags: data-structures, reference-request, sets
---


# Question
Title: Minimize cost and maximize quality of function in four variables
Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory.

I have an indexing scheme used to search for the K-nearest neighbors of a point in many dimensions. This indexing scheme has four adjustable parameters. For each given fixed problem size (total number of points, number of nearest neighbors to find, number of dimensions, desired accuracy) I plan to run a solver to find the optimal values for these four parameters. Here are the constraints:

1) If the accuracy is below desired accuracy (say 95%), prefer parameter values that maximize the accuracy.

2) Once the accuracy equals or exceeds the desired accuracy, prefer parameters that minimize the execution time.

3) Do not exhaust all system memory.

I handle #3 by restricting the one parameter that is directly proportional to memory usage based on numerous manual tests.

One of the parameters is discrete: it may only take on integer values. (This is the one that affects memory size).

Three of the parameters always move in the same direction as accuracy: as they increase, accuracy always remains the same or increases, up to a maximum of 100%. Each of these three parameters also moves in the same direction as cost: as they increase, the cost always increases (without bound).

The fourth parameter has the smallest (and least predictable) influence on cost. The accuracy will always decrease as you move farther away from the optimal value, either up or down.

Because of the 100% accuracy cutoff, the function has places with no derivative (is not smooth).

I have hundreds of combinations to optimize, varying # of dimensions versus # of points. My current approach runs all night without completing all the cases and produces erratic results (poor solver algorithm that gravitates toward high accuracy and horrible time cost). Given the nature of the constraints I have described and the number of parameters, **which class of algorithms should I investigate?** I understand the gradient method, but worry that it will perform poorly (too many steps) or not work with the non-smoothness of the function.

It might be possible to seed each successively larger case with the best results from the next smaller case; the parameter values should vary smoothly as the case sizes increase. the cost of evaluating the execution time and accuracy increases with the number of points and with the number of dimensions.

**Current algorithm:**

1) Start with seed values for each parameter, as determined after days of manual testing.

2) Holding all parameters fixed but one and varying that one, find its best value. Test values in increasing order, stopping when the accuracy is acceptable.

3) Repeat for all parameters.

4) Make five passes over all parameters. At each pass, use a finer grid for the search.

My approach is basically using an inefficient gradient search in one dimension at a time. It is slow and produces good results for the smaller cases but soon yields poor results for the medium sized cases.

**The Four adjustable parameters**

In thinking about them, I have decided that three of the parameters can be represented as discrete integer values, and only one is continuous.

a) Perms = Number of permutations of the index to create. Each index takes up memory. This parameter has the dominant influence on memory usage. This ranges from 3 to 20. Depending on the number of points indexed, somewhere between 20 and 32 indices will use up all memory.

b) Margin = Number of points to select in each index probe. If K is the number of neighbors sought, Margin typically varies from 3\*K to 20\*K.

c) Box-Points = Number of random faces of a hypercube surrounding the search point to probe. This ranges from 1 to 2\*dimensions.

d) Box-Size = A fraction to multiply by the characteristic hypercube size to define the volume of hyperspace to search. Typically ranges from 0.3 to 1.5.

# Answer
> 1 votes
So, simplifying a bit, you want to maximize an objective function $\Phi(w,x,y,z)$, where $\Phi$ has the following properties:

* $\Phi(w,x,y,z)$ is monotonically increasing in $w$, in $x$, and in $y$
* for any fixed $w,x,y$, $\Phi(w,x,y,z)$ is monotonically increasing-then-decreasing in $z$, i.e., there exists some $z\_0$ such that $\Phi(w,x,y,z)$ is monotonically increasing in $z$ for $z \le z\_0$ and is monotonically decreasing in $z$ for $z \ge z\_0$.

Here $\Phi(w,x,y,z)$ represents the accuracy.

There are efficient algorithms to maximize this objective function, if $\Phi$ has some additional nice properties. I'll describe how to do so, in several steps.

Given $w,x,y$, it is possible to efficiently find the $z$ that maximizes $\Phi(w,x,y,z)$ using ternary search (see also here). Let $\Phi\_3(w,x,y)$ denote the value of $\Phi(w,x,y,z)$ for the value of $z$ that maximizes $\Phi(w,x,y,z)$, i.e.,

$$\Phi\_3(w,x,y) = \max\_z \Phi(w,x,y,z).$$

The comment above indicates that you can efficiently compute $\Phi\_3(w,x,y)$ using ternary search. If $z$ comes from a discrete space with $N$ possible values, the running time to compute $\Phi\_3(w,x,y)$ will be $\Theta(N)$; if it comes from a continuous space, you can find the approximate value of $\Phi\_3(w,x,y)$, and for typical functions, it the convergence rate will often be very fast (the number of iterations will be proportional to the number of digits of accuracy you want in the answer).

Now, if we are lucky, $\Phi\_3$ will be monotonically increasing in $w,x,y$. If this happens, we can continue to apply a similar idea, as follows.

Under this condition, given $w,x$, it is possible to efficiently find the $y$ that maximizes $\Phi\_3(w,x,y)$. How? Use binary search on $y$, and use the fact that we know how to efficiently compute $\Phi\_3(w,x,y)$. So, define

$$\Phi\_2(w,x) = \max\_y \Phi\_3(w,x,y),$$

and note that this gives us an efficient way to compute $\Phi\_2(w,x)$. The running time will again be efficient, i.e., $\Theta(\lg N)$ evaluations of $\Phi\_3$ if $y$ comes from a discrete space with $N$ possible values, otherwise we can get an approximate optimal value efficiently (typically, the number of evaluations of $\Phi\_3$ needed is proportional to the number of digits of accuracy we want in the answer).

Suppose that $\Phi\_2(w,x)$ is monotonically increasing in $w,x$ and $\Phi\_1(w) = \max\_x \Phi\_2(w,x)$ is monotonically increasing in $w$. Then Applying the same techniques, we can see that given $w$ it is possible to efficiently find the $x$ that maximizes $\Phi\_2(w,x)$ (using binary search), and thus that it is possible to find the $w$ that maximizes $\Phi\_1(w)$. Finally, the maximum value of $\Phi\_1(w)$ is exactly the maximum value of $\Phi(w,x,y,z)$ over all $w,x,y,z$.

So if $\Phi$ has some additional nice properties, there are efficient algorithms. The resulting algorithm will have running time $O(k^4)$, where $k = \lg N$ if each parameter comes from a discrete space; or where $k$ is typically proportional to the number of bits of accuracy desired if the parameter comes from a continuous space.

Therefore I suggest you try this and see if your $\Phi$ has the required nice properties. If it does, you are in good shape and you can try a technique based on this.

---

What do you do if $\Phi$ doesn't have these nice properties? Probably your best next bet is to try some standard black-box mathematical optimization routine, e.g., hill-climbing, gradient descent, or convex optimization. If $\Phi$ is a relatively smooth function, I suspect they might work pretty well.

---
Tags: algorithms, optimization
---


# Question
Title: Delaunay Triangulation on Convex Polytopes — Uniform Sampling
My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts:

Uniform sampling from a simplex

Random vectors uniformely distributed into convex n-polytope

Therefore, I'm very interested in this approach. But I don't really know how to use Delaunay Triangulation here. What I have is a linear equation Ax = b and a non-negativity constraint that $x \geq \vec{0}$, and I want to sample x uniformly. Can someone tell me how to do the Delaunay Triangulation here? Thanks in advance!

# Answer
> 3 votes
This is an active area of research. Fortunately, recently there has been a breakthrough due to Vempala and Cousins \[1\]. They provide a MATLAB implementation of their algorithm. If you're interested in the technical details, you can check out some slides from a recent workshop.

This algorithm only samples points *approximately* uniformly. Exact uniform sampling, or rather the related volume estimation problem, is known to be hard (under reasonable assumptions) in general. Your convex body isn't general, however – it's a polytope. Nevertheless, the answers to this question suggest that there is no better algorithm for this special case (they suggest employing general algorithms which are older than Cousins–Vempala).

---

1. Bypassing KLS: Gaussian Cooling and an $O^\*(n^3)$ Volume Algorithm by B. Cousins and S. Vempala (2014, preprint)

---
Tags: computational-geometry, sampling
---


title: Graph Families that are easy to color

text:
# Question
Title: Graph Families that are easy to color
What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter.

Examples would be:

* Kneser graphs
* Chordal graphs

Do you know any other families?

**Motivation:**

We are looking for interesting classes on which we can test a proper coloring heuristic. This is why we wanted some graphs that are not so easy to color but in the same time have a known chromatic number so we can evaluate the quality of the heuristic.

# Answer
> 8 votes
Whenever you are interested in a (well-known) graph invariant, it's a good idea to check out ISGCI first. Have a look at graphs that have bounded chromatic number, or graphs for which computing the number is doable in polynomial time.

To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded treewidth.

---
Tags: graphs, reference-request, colorings
---


title: Exercise on Divide&Conquer's technique

text:
# Question
Title: Exercise on Divide&Conquer's technique
I need help on this exercise: You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(n log n).

I find a solution but in O(n^2)... How can I apply D&C?

# Answer
Given an array of elements $a\[i\], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b\[\\;\]$:

```
declare b to be of size n
old = a[0]
b[0] = a[0]
j = 1
for i = 1, ... , n
   if a[i] =/= old    // found a new value
      old = a[i]      // save it
      b[j] = a[i]     // store it in b[j]
      j = j + 1       // and increment the b index

```

It's clear that, first, this can be done in one pass through the $a$ array, so this part will take time $O(n)$ (along with $O(n)$ time to allocate $b$), and, second, after this part the $b$ array will contain all of the values of the original array, with no duplicate values.

**Note**. This may or may not be what you want. Starting with an initial array $\langle\\,7, 3, 7, 4, 1, 3, 1, 7\\,\rangle$, this will result in a $b$ array $\langle\\,1, 3, 4, 7\\,\rangle$, which has all the values without duplicates, but the original place order of the elements isn't preserved. There are at least two possibilities for the result, depending on whether you want to eliminate all the duplicate values after the first occurrence, (giving you $\langle\\,7, 3, 4, 1\\,\rangle$) or if you want to eliminate all the duplicate values before the last occurrence, giving you $\langle\\,4, 3, 1, 7\\,\rangle$.

For the first option, a fairly simple modification is to do a preprocessing step on the $a$ array, changing it to an array of pairs, $(value, index)$, where $index$ is the position of the element with that value. In the example above, this will give you a new array $$ \langle\\,(7, 0), (3, 1), (7, 2), (4, 3), (1, 4), (3, 5), (1, 6), (7, 7)\\,\rangle $$ Now, as we did originally, sort this array by the first element of the pairs, giving $$ \langle\\,(1, 4), (1, 6), (3, 1), (3, 5), (4, 3), (7, 0), (7, 2), (7, 7)\\,\rangle $$ (here we need to use a stable sort, like mergesort, to maintain the original place order). Eliminating duplicates, as above, we will have $$ \langle\\,(1, 4), (3, 1), (4, 3), (7, 0)\\,\rangle $$ and if we sort the result by the second index, we'll have $$ \langle\\,(7, 0), (3, 1), (4, 3), (1, 4)\\,\rangle $$ and looking at the first element, we'll have $\langle\\,7, 3, 4, 1\\,\rangle$, which is what we wanted.

This algorithm will take $O(n)$ steps to preprocess the array, $O(n\log n)$ steps to sort the result, $O(n)$ steps to eliminate the duplicate values, and $O(n\log n)$ steps to do the final sort, giving us an algorithnm that runs in time $O(n+n\log n+n+n\log n)=O(n\log n)$.
> 4 votes

# Answer
This is my solution (pseudocode):

```
Duplicate(A: array):
  Array B = Merge-sort(A)
  Array Vect // New Vector
  int p=2
  Vect[1] = B[1]
  for i=2 to B.lenght{
    if (B[i]<>B[i-1]) then
        Vect[p] = B[i]
        p = p+1
   }
 return Vect

```

is correct?
> -1 votes

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


title: Algorithm - Wine Bottle Filling

text:
# Question
Title: Algorithm - Wine Bottle Filling
You have two friends, call them A and B. They each are given two wine bottles: one bottle holds `k_1` litres and the other `k_2` litres. Both A and B can perform these operations: \- completely fill a wine bottle with wine \- completely empty a wine bottle \- pour the wine of one bottle into the other bottle, making sure to stop only when either the bottle being filled is full or if when the bottle being emptied is completely empty. Assume the litres of wine are all positive ints.

Q: Determine if there exist a seq of operations that leaves exactly `k_3` litres of wine in the bigger wine bottle. Try representing this as a graph problem.

My idea: define the vertices to be a pair of integers in a graph. I got this as a recent interview question. But couldn't solve the entire problem in time. Then they said you could have apparently applied some algo to this problem too, and that it had a complexity that was fast enough. Any ideas?

# Answer
> 5 votes
Here's an efficient method that doesn't involve constructing a graph of the states and searching for a path to each target value. Let the capacities of the bottles be integers $K\_1\<K\_2$, respectively, and denote by $(a\_1, a\_2)$ the current amounts in the bottles. You have six basic operations you can perform, for $i=1, 2$:

* $f\_i$: fill bottle $i$.
* $e\_i$: empty bottle $i$.
* $p\_i$: pour as much of bottle $i$ as will fit into bottle $3-i$.

We'll show this

> **Theorem**. If $\gcd(K\_1, K\_2) = 1$ (i.e., $K\_1$ and $K\_2$ have no factors in common), then you can start in state $(0,0)$ and end in state $(0, t)$ for any target integer $0\le t\le K\_2$.

Consider these two sequences of basic moves, starting in state $(0, b)$:

* Sequence $S$: if $b\>K\_2-K\_1$, perform $f\_1, p\_1, e\_2, p\_1$.
* Sequence $T$: if $b\le K\_2-K\_1$, perform $f\_1, p\_1$.

The result of $S$ will be $$ (0, b)\stackrel{f\_1}{\rightarrow}(K\_1,b)\stackrel{p\_1}{\rightarrow}(K\_1-(K\_2-b),K\_2)\stackrel{e\_2}{\rightarrow}(K\_1-K\_2+b,0)\stackrel{p\_1}{\rightarrow}(0,K\_1-K\_2+b) $$ and the result of $T$ will be $$ (0, b)\stackrel{f\_1}{\rightarrow}(K\_1,b)\stackrel{p\_1}{\rightarrow}(0, K\_1+b) $$ It's not difficult to establish that if $b\>K\_2-K\_1$, the $S$ sequence will satisfy that the first component of each state will be less than or equal to $K\_1$ and the second will be less than or equal to $K\_2$ at each step and we can show similarly that the basic moves in the $T$ sequence are likewise always legal at each step.

For example, with $K\_1=3, K\_2=5$ we will have the following sequence of states: $$ (0,0)\stackrel{T}{\rightarrow}(0,3)\stackrel{S}{\rightarrow}(0,1)\stackrel{T}{\rightarrow}(0,4)\stackrel{S}{\rightarrow}(0,2) $$ so the sequence $T,S,T,S$ will generate the target values $0, 3, 1, 4, 2$, and of course we can always generate $K\_2$ by a single $f\_2$ move. Notice that we have generated all the target values $0\le t\le K\_2=5$, as the theorem above indicated we should.

To show that this behavior happens for all integer capacities $K\_1\<K\_2$ where $\gcd(K\_1, K\_2) = 1$, consider the second component values at each stage modulo $K\_2$: an $S$ sequence takes $(0,b)\rightarrow(0, K\_1-K\_2+b)$ and $K\_1-K\_2+b\equiv K\_1+b\pmod{K\_2}$. Similarly, a $T$ sequence takes $(0, b)\rightarrow(0, K\_1+b)$, so any sequence of $S$-$T$ moves starting at $(0,0)$ will produce the target values $nK\_1\pmod{K\_2}$, for $n=0, 1, 2, \dotsc,K\_2-1$.

For our example, with $K\_1=3,K\_2=5$, we'll have the sequence of target values $$ \langle\\,0, 3, 6, 9, 12\\,\rangle \equiv\langle\\,0, 3, 1, 4, 2\\,\rangle\pmod{5} $$ All that remains to establish our theorem is to show that the $K\_2$ elements of the target sequence are distinct. Suppose that they weren't, namely that there exist $n, m$ with $0\le n \< m \< K\_2$ such that $mK\_1\equiv nK\_1\pmod{K\_2}$. Then we would have $(m-n)K\_1\equiv0\pmod{K\_2}$ which would mean that $K\_2$ would have to divide $(m-n)K\_1$. However, $K\_1$ has no factors in common with $K\_2$ since $\gcd(K\_1, K\_2)=1$, so $K\_2$ would have to divide $m-n$. However, $m-n\<K\_2$ and so the only possibility would be that $m-n=0$, i.e., $m=n$, contrary to our assumption. Thus, all the $K\_2$ values in our target sequence are distinct, establishing our theorem.

---

**Notes**

1. For completeness, we note that if $\gcd(K\_1,K\_2)=g\>1$ then you can make all and only those target amounts $ng$ where $0\le n\le K\_2/g$, since we can reduce this case to one with capacities $K\_1'=K\_1/g,K\_2'=K\_2/g$ and observe that $\gcd(K\_1',K\_2')=1$.
2. Instead of the $S$-$T$ sequences, these can also be used: $$\begin{align} Q: &\text{if }b \< K\_1, \text{ perform }p\_2,f\_2,p\_2,e\_1\\ R: &\text{if }b \ge K\_1, \text{ perform }p\_2,e\_1 \end{align}$$
3. The $S$-$T$ sequences might not produce a given target in the fewest number of moves. It may be the case that the $Q$-$R$ sequences will get to a given target value faster and *vice-versa*. It's possible, using the extended Euclidean algorithm, to determine which sequence choice will reach a particular target value quicker.
4. To generate all the possible target values by this method will take $O(K\_2)$ time.
5. If you only want an answer to the interviewer's question, "is there a sequence of operations that leaves an amount $k\_3$ in the larger bottle?" here's an algorithm that runs in time $O(\log K\_2)$: if $k\_3 \> K\_2$ answer "no", otherwise compute $g=\gcd(K\_1, K\_2)$ (which you can do in time $O(\log K\_2)$) and if $g$ divides $k\_3$, answer "yes", else answer "no".

# Answer
> 3 votes
The idea is to construct a directed graph whose vertices are labelled by pairs of integers $(a\_1,a\_2)$, where $0 \leq a\_i \leq k\_i$ (I'm assuming that $k\_1,k\_2$ are integers). There is also an additional vertex $t$. The vertex $(a\_1,a\_2)$ represents the fact that bottle $i$ holds $a\_i$ litres. Connect $(a\_1,a\_2)$ to $(b\_1,b\_2)$ if a single operation can take you from state $(a\_1,a\_2)$ to state $(b\_1,b\_2)$. Connect $(a\_1,a\_2)$ to $t$ if $a\_1 = k\_3$ (assuming $k\_1 \geq k\_2$). Now check using your favorite graph search algorithm whether $t$ is reachable from $(0,0)$.

This algorithm runs in time $O(k\_1k\_2)$. One wonders whether there is a faster algorithm running in time polynomial in the input size $\log (k\_1 k\_2)$.

---
Tags: algorithms, decision-problem
---