# Question
Title: n log n = c. What are some good approximations of this?
I am currently looking into Big O notation and computational complexity.

Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic complexities grow with the size of the input.

The question asks:

*For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.*

The time periods are 1 second, 1 minute, 1 hour, 1 day, 1 month, 1 year, 1 century.

The functions $f(n)$ are seemingly common time complexities that arise in algorithms frequently, the list being:

$$ \log\_2n, \quad \sqrt{n}, \quad n, \quad n \log\_2 n, \quad n^2, \quad n^3, \quad 2^n \quad \text{and} \quad n!$$

Most are fairly straightforward algebraic manipulations. I am struggling with two of these, and both for the same reason:

If $c$ is the time in microseconds, the two I am struggling with are $$ n \log\_2 n = c$$ $$ n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$$

For $n!$ I thought of using Stirling's Approximation.

These both require the ability to solve $n \log\_2 n = c$, with Stirling require a little more manipulation.

**Questions**

1. As $n \log\_2 n$ is not solvable using elementary functions (only Lambert W), what are some good ways to approximate $n log\_2 n$? Or how do we implement Lambert W?
2. How do we solve n! = c, necessarily approximately as n grows large. Is Stirling the right way to go, and if so how to solve $\sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$

---

Here is some python code I put together to complete the table with my current output:

***EDIT: Based on a couple of answers, I have used a binary search method (except for lg n). I have edited the code below to reflect this:***

```
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| f(n)    |    1 sec    |    1 min    |    1 Hour   |    1 Day    |   1 Month   |    1 Year   |  1 Century  |
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| lg n    | 2^(1.0E+06) | 2^(6.0E+07) | 2^(3.6E+09) | 2^(8.6E+10) | 2^(2.6E+12) | 2^(3.2E+13) | 2^(3.2E+15) |
| sqrt(n) |   1.0E+12   |   3.6E+15   |   1.3E+19   |   7.5E+21   |   6.7E+24   |   9.9E+26   |   9.9E+30   |
| n       |   1.0E+06   |   6.0E+07   |   3.6E+09   |   8.6E+10   |   2.6E+12   |   3.2E+13   |   3.2E+15   |
| n log n |    62746    |   2.8E+06   |   1.3E+08   |   2.8E+09   |   7.2E+10   |   8.0E+11   |   6.9E+13   |
| n^2     |     1000    |     7745    |    60000    |    293938   |   1.6E+06   |   5.6E+06   |   5.6E+07   |
| n^3     |     100     |     391     |     1532    |     4420    |    13736    |    31593    |    146645   |
| 2^n     |      19     |      25     |      31     |      36     |      41     |      44     |      51     |
| n!      |      9      |      11     |      12     |      13     |      15     |      16     |      17     |
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+

```

Python code:

```
import math
import decimal
from prettytable import PrettyTable

def binary_search_guess(f, t, last=1000):
    for i in range(0, last):
        guess = pow(2,i)
        if f(guess) > t:
            return binary_search_function(f, pow(2,i-1), guess, t)

    return -1

def binary_search_function(f, first, last, target):
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
            if f(midpoint) <= target and f(midpoint+1) > target:
                found = True
            else:
                if target < f(midpoint):
                    last = midpoint-1
                else:
                    first = midpoint+1
    best_guess = midpoint

    return best_guess

def int_or_sci(x):
    if x >= math.pow(10,6):
        x = '%.1E' % decimal.Decimal(x)
    else:
        x = int(x)

    return x

def input_size_calc():
    #Create Pretty Table Header
    tbl = PrettyTable(["f(n)", "1 sec", "1 min", "1 Hour", "1 Day", "1 Month", "1 Year", "1 Century"])
    tbl.align["f(n)"] = "l" # Left align city names
    tbl.padding_width = 1 # One space between column edges and contents (default)

    #Each Time Interval in Microseconds
    tsec = pow(10,6)
    tmin = 60 * tsec
    thour = 3600 * tsec
    tday = 86400 * tsec
    tmonth = 30 * tday
    tyear = 365 * tday
    tcentury = 100 * tyear

    tlist = [tsec,tmin,thour,tday,tmonth,tyear,tcentury]
    #print tlist

    #Add rows
    #lg n
    f = lambda x : math.log(x,2)
    fn_list = []
    for t in tlist:
        #This would take too long for binary search method
        ans = int_or_sci(t)
        fn_list.append("2^(%s)" % ans)
    tbl.add_row(["lg n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #sqrt(n)
    f = lambda x : math.pow(x,1/2.0)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["sqrt(n)",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #n
    f = lambda x : x
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #n log n
    f = lambda x : x * math.log(x,2)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["n log n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #n^2
    f = lambda x : math.pow(x,2)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["n^2",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #n^3
    f = lambda x : math.pow(x,3)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["n^3",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #2^n
    f = lambda x : math.pow(2,x)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["2^n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    #n!
    f = lambda x : math.factorial(x)
    fn_list = []
    for t in tlist:
        fn_list.append(int_or_sci(binary_search_guess(f, t)))
    tbl.add_row(["n!",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])

    print tbl

#PROGRAM BEGIN
input_size_calc()

```

# Answer
> 9 votes
The approximate inverse of $c = n\log n$ is $n = c/\log c$. Indeed, for this value of $n$ we have $$ n\log n = \frac{c}{\log c} \log \frac{c}{\log c} = \frac{c}{\log c} (\log c - \log\log c) = c \left(1 - \frac{\log\log c}{\log c}\right). $$ This approximation is usually good enough.

# Answer
> 1 votes
You don't need to approximate anything to solve the exercise. All the functions you're given are monotone so you can just use binary search. That is, to solve $f(n)=c$ for $n$, just guess $n=1, 2, 4, 8, \dots$ until you find the first $k$ that $2^k \log 2^k \> c$. Then, do ordinary binary search between $2^{k-1}$ and $2^k$. If the solution is $x$, this takes roughly $2\log x$ evaluations of $f$.

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


# Question
Title: How do binary trees use memory to store its data?
So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no room, a new static array is created elsewhere in memory larger in size so more data can be stored.

My question is, how do binary trees use memory to store data? Is each node a memory location which points to two other memory locations elsewhere...not necessarily contiguous locations? Or are they stored in contiguous blocks of memory too like a static array or dynamic list?

# Answer
> 3 votes
We use implicit array representation to store Binary Heaps, where if a node has an index $i$, its children are found at indices $2i + 1$ (for the left child) and $2i +2$ (for the right), assuming indices start at 0.

Now this is not wasteful for Binary Heaps since nodes are added in Breadth First method. However for normal Binary Trees implicit array representation is very expensive to grow and wastes space in the order of $O(2^h)$ where $h$ is the height of the tree (Consider skewed binary trees).

For trees having a large number of nodes we use Succint Data Structures as pointed out by Raphael. A normal binary tree of $n$ nodes is stored using $O(nlogn)$ bits (pointer representation), but succinct representations require just $2n + o(n)$ bits and carry out many sophisticated operations in constant time. This link gives us a good overview of a simple representation of succint representations.

---
Tags: data-structures, binary-trees, memory-management
---


# Question
Title: Chomsky hierarchy type determined by language
I have some modified automata and the task is to give the type of Chomsky hierarchy to it. All task is between type 3 and 0 noninclusive. For regular languages there are lot of tools and I can check it without problems, Turing Machine equivalent is also easy task, and there will be no such examples.

Now the question: is it sufficient to show that automaton can accept specified language of given type? From what I checked it would be sufficient to show equivalence to for example to NPDA, so I assume that if machine handles language that at least NPDA accepts it would be sufficient.

For example if machine can accept $a^nb^n$, it is type 2. If machine can accept $a^nb^nc^nd^n$ it is type 1? If not are there better examples of such languages or what steps should I follow?

# Answer
No, a finite set of languages does not (usually) characterise infinite classes of languages. So any such specific tests are probably easy to fool.

For CFL in particular, there the Chomsky-Schützenberger characterisation. So if your model can deal with finitely many types of nested parentheses, it's *probably* at least as powerful as NPDA.

The generic proof technique for showing that one model is more powerful than another is *simulation*. You can find some examples via and, of course, in the literature.

Proof of the opposite is usually done by *counter-example*, i.e. a language that can be expressed in one but not the other model.
> 3 votes

---
Tags: automata, proof-techniques, computation-models
---


# Question
Title: About a step in the analysis of Quicksort by Sedgewick and Wayne
In the book *Algorithms*, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather\*} C\_N = N + 1 + (C\_0 + C\_1 + \dots + C\_{N-2} + C\_{N-1})/N + (C\_{N-1} + C\_{N-2} + \dots + C\_0)/N\\ NC\_N = N(N+1) + 2(C\_0 + C\_1 + \dots + C\_{N-2} + C\_{N-1})\\ NC\_N - (N-1)C\_{N-1} = 2N + 2C\_{N-1}\\ C\_N/(N+1) = C\_{N-1}/N + 2/(N+1)\\ C\_N\sim 2(N+1)(1/3 + 1/4 + \dots + 1/(N+1))\end{gather\*}$$

How did they get the last transformation?

It is also written that the parenthesized quantity in the last expression is the discrete estimate of the area under the curve $2/x$ from $3$ to $N$? How is it related to quicksort?

# Answer
Let $\rho\_N = C\_N/(N+1)$. The next to last equation shows that $$ \rho\_N = \rho\_{N-1} + \frac{2}{N+1}. $$ Therefore $$ \rho\_N = \frac{2}{N+1} + \cdots + \frac{2}{2+1} + \rho\_1. $$ Multiplying by $N+1$, $$ C\_N = (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1} + \rho\_1\right). $$ Since $\rho\_1$ is a constant whereas $2/3 + \cdots + 2/(N+1) \to \infty$, we deduce that $$ C\_N \sim (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1}\right). $$ We can estimate this expression in many ways, for example by approximating the series by an integral (this is what the authors suggest when they mention the area under the curve $2/x$). Or we can recognize that it is roughly equal to $2H\_{N+1}$, twice the $(N+1)$st harmonic number, and so using the well-known estimate $H\_N \sim \log N$, $$ C\_N \sim 2N\log N. $$

Finally, regarding the relevance to Quicksort, my guess is that $C\_N$ is the average number of comparisons performed on a random array of length $N$; but you should be able to tell by reading the book.
> 4 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recurrence-relation, quicksort
---


# Question
Title: Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs
Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with complexity $O(m)$, what is the most efficient ?

# Answer
Since $m \in \Theta(n^2)$ in the worst case, $O$-bounds don't tell you much. That is to say, just from these bounds alone, you can't say that $O(m)$ is better than $O(n^2)$ (and the reverse never holds for simple graphs).

However, if you have $\Theta$-bounds then $\Theta(m)$ is properly better than $\Theta(n^2)$ if $m \in o(n^2)$, i.e. you have *sparse* graphs.

Also, the usual limitations of $O$-worst-case analysis apply: you may actually be interested in typical-case behaviour, constant factors may matter to you, and you need efficiency for finite (small?) $n$.
> 5 votes

# Answer
A bound of the form $O(m)$ is always better than a bound of the form $O(n^2)$ since $m \leq n^2$. As Raphael mentions, since this is only an upper bound, a priori we don't know which algorithm is better. However, if you are interested in sparse graphs (say, $m = O(n)$) then the promise $O(m)$ is better than the promise $O(n^2)$.

Often algorithms are analyzed so that their big O complexity does equal their worst-case complexity. That is, usually an $O(n^2)$ algorithm has time complexity $\Theta(n^2)$ on some inputs, and an $O(m)$ algorithm has time complexity $\Theta(m)$ on some inputs. This doesn't offer any help, since the worst-case instances for the $O(n^2)$ algorithm could be dense.

However, by the same token, *graph* algorithms are analyzed so that their big O complexity is the best upper bound that can be given in the worst case, where *best* here roughly means out of all bounds of the form $O(n^\alpha m^\beta)$. This means that usually, if the complexity of an algorithm is quoted as $O(n^2)$, then its complexity is *not* $O(m)$. However, this is just a convention, and you should check the individual algorithms to make sure.

Don't forget also that asymptotic notation ignores constants – a $\Theta(n^2)$ might be better than a $\Theta(m)$ algorithm for all graphs containing less than $10^{30}$ edges.
> 2 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, efficiency
---


# Question
Title: How can I convert a list with duplicates into a set for a reduction to the set cover problem?
I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here.

Here's a condensed version of the problem:
You're given a collection of refrigerator magnet letters that may contain duplicates. You have a limited vocabulary of words made of combinations of those letters (again, a word may contain the same letter twice). Can you choose words from the vocabulary to build with the magnets such that all of the magnets are used and each magnet is used in only one word?

It's suspiciously similar to the set cover problem, so I've been trying to come up with a way to convert (in polynomial time) a collection of symbols that potentially contains duplicates into a set. This would allow the collection of symbols to be used as *U* and the child's vocabulary to be used as *S* for set cover.

I've had no luck so far, so a hint or even a suggestion for a more appropriate NP-complete problem to reduce to would be greatly appreciated.

# Answer
There are several possible interpretations of the problem:

1. The alphabet size could be fixed or unbounded.
2. Words could be repeated or not.
3. The input histogram (how many letters of each type) could be encoded in unary (e.g., the letters are "aabcccccc") or in binary (e.g. $a\times 2, b\times 1, c \times 4$).

Here is the complexity of some of these variants.

**Fixed alphabet, words may not be repeated, histogram is encoded in unary.** Use dynamic programming. Given the list of words $w\_1,\ldots,w\_n$, compute inductively all possible histograms of all possible subsets of $w\_1,\ldots,w\_i$ which are "within budget". If the budget is $b\_1,\ldots,b\_m$ (so the alphabet size is $m$), then the number of such histograms is at most $(b\_1+1)\cdots(b\_m+1) \leq (2\max b\_j)^m$, which is polynomial in the input size. Check whether the budget is one of these possible histograms.

**Fixed alphabet, words may be repeated, histogram is encoded in unary.** A similar strategy works, using a fixpoint iteration. Maintain a list of reachable histogram. At each round, add all words to all reachable histograms under budget, and update the list. Stop when the list stabilizes. Check whether the input histogram is one of them.

**Unbounded alphabet.** NP-complete, by reduction from 1-in-3 SAT. There is one letter per variable and clause, and one word per variable truth assignment. The word contains the variable symbol as well as the clauses satisfied by the assignment. All budgets are $1$.
> 1 votes

---
Tags: reductions, set-cover
---


# Question
Title: Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$
I'm having a lot of trouble constructing a PDA for the language: \begin{equation\*} \\{a^m b^n : m \< 2n \< 3m \\} \end{equation\*}

I know if I push a symbol for each $a$ I see, then pop 2 symbols for each $b$ I see, then I should run out to satisfy the $m \< 2n$ part of the inequality. But I really don't understand how to include the requirement $2n \< 3m$. I'm assuming it has something to do with clever branching based on non-determinism, but I can't wrap my head around it. Any help would really appreciated.

# Answer
To handle the inequality $m \lt 2n$, you arrange to push a marker for each $a$, and pop two markers for each following $b$. This way the number of markers on the stack indicates the number of $a$'s. When the stack is empty, the equality is reached.

To handle the inequality $2n \lt 3m$, you could to arrange to push three markers for each $a$ and pop two markers for each following $b$. However, a stack won't let you push different numbers of markers.

There is no general way of “merging” two automata in this way. If the two automata use the stack at different rates, it may not be possible to merge them without having two stacks. This is reflected in the properties of languages recognized by pushdown automata: the intersection of two context-free languages is not always context-free.

To get an idea of what to do here, I think it helps to write a context-free grammar for this language. A grammar needs to break down the language into some recursive structure, which leads us to expressing elements of the language as expansions of shorter elements. I'll look at what happens when $b$s are added; you could obtain a different grammar by similar means by looking at what happens when $a$s are added.

If you add $1$ to $n$, what happens to the possible values of $m$? For the maximum value, it's easy: it increases by $2$, because $m \lt 2n \iff m+2 \lt 2(n+1)$. For the minimum value, it's more difficult: we need to find the threshold for $\frac{2}{3}n$, so it depends on whether $n$ is a multiple of $3$, which we cannot express in a grammar rule. However, if we add three $b$s at a time, it's easy: the minimum number of $a$s increases by $2$, because $2n \lt 3m \iff 2(n+3) \lt 3(m+2)$.

Let $L$ be the desired language. The rule above tells us how words in $L$ can be constructed from shorter words; we still need to check the base cases. $$ \begin{align} L \cap a^\* &= \varnothing \\ L \cap a^\* b &= \\{ab\\} \\ L \cap a^\* b^2 &= \\{a^2b^2, a^3b^2\\} \\ L \cap a^\* b^3 &= \\{a^3b^3, a^4b^3, a^5b^3\\} \\ \end{align} $$ We have all the information needed to construct a grammar for $L$. $$ \begin{array}{rl} S &\to a b \\ S &\to a^2 b^2 \\ S &\to a^3 b^2 \\ S &\to a^3 b^3 \\ S &\to a^4 b^3 \\ S &\to a^5 b^3 \\ \end{array} \qquad \begin{array}{rl} S &\to a^2 S b^3 \\ S &\to a^3 S b^3 \\ S &\to a^4 S b^3 \\ S &\to a^5 S b^3 \\ S &\to a^6 S b^3 \\ \end{array} $$ If you're unsure about the correction of this construction, prove that all words in $L$ are recognized by this grammar (construct a derivation) and prove that all the words recognized by this grammar are in $L$ (by induction over the rules).

Now you can apply a systematic method for constructing a non-deterministic pushdown automaton from a grammar. Since the right-hand part of every rule is the same, it is enough to have a single element in the stack alphabet. Push this symbol for each batch of 2 to 6 $a$'s (this is non-deterministic); pop it for 3 $b$'s.
> 5 votes

# Answer
Hint: For each $a$, push either $1$, $2$ or $3$ symbols. (But not always $1$ and not always $3$!)
> 3 votes

# Answer
yes, we can create PDA for the given language.

first i find the relation between n & m.

given that m \< 2n \< 3m

i break this in two equation

1. 2n \> m i.e \[ n \> m/2 \] -----------eqn-1
2. 2n \< 3m i.e \[ n \< 1.5m \] -------------eqn-2

from eqn 1 & 2 i found that \[ m \>= n+1 \]for n,m \>= 2 i.e if n=2 then m=3 n=3 then m=4 etc

now it is simple to construct PDA for the above language a^m b^n where m\>=n+1 & m,n\>=2

push all a into stack and when see 1st b leave it and when see 2nd b then start popping a from stack.
> -4 votes

---
Tags: formal-languages, automata, pushdown-automata
---


# Question
Title: Which matrix of Q values is being used here?
This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task

In section 2.1, equations (5) and (6), I am wondering which Q values are being used to adjust the weights of the restricted boltzmann machine:

Option 1: the Q values generated by the original MDP

Option 2: the approximate Q values obtained by calculating the (negative of the) free energy of the RBM

Follow up question: When considering states $(s^t, a^t)$ and $(s^{t+1}, a^{t+1})$, how do we determine which values of $a^t$ and $a^{t+1}$ to use? Are these the optimal actions from the original MDP, or are these to be obtained through the alternating Gibbs sampling mentioned later on...(which doesn't make sense, since we would not have weights required for this CD)

Thanks for your help

# Answer
1. Reinforcement learning works by bootstrapping, which means that Q values are updated based on previous *estimates*. Also, MDP's don't generate Q values, just rewards (Q values are long-term estimates of accumulated future rewards). So the answer is option 2: the Q values are obtained by calculating the (negative of the) free energy of the RBM. You use the RBM to calculate the current Q value and use it together with the value from the previous step to update your estimate.
2. The paper uses the Sarsa algorithm, which means it is on-policy. In other words, it uses only actual performed actions. It means that the values are updated only on the next step $t+1$, where you chose your action $a^{t+1}$. In summary, you use Gibbs sampling to select actions and, on time $t+1$ you update the weights using $s^t, a^t, s^{t+1}$ and $a^{t+1}$.
> 2 votes

---
Tags: dynamic-programming, approximation, neural-networks
---


# Question
Title: How to choose proper activation functions for hidden and output layers of a perceptron neural network?
As far as I know choosing an activation function for the input layer is relatively straightforward: I use Sigmoid if the input data domain is (0,1) and TANH if it is (-1,1).

But what activation functions to set for hidden and output layers? Is there any conventional logic for making thish choice reasonably? How do I know/set the domain of a neuron layer output?

# Answer
* Input: it is not common to use activation functions in the input layer. Just rescale your data to the \[-1;1\] interval;
* Hidden: the $tanh$ activation used to be the most popular. Now, this role has been taken by the $relu$ (rectified linear unit) activation, which produce sparse activations and better preserve the gradients;
* Output: here is where you need to chose the activation function according to your problem type. For classification use the softmax activation (the multivariate version of the logistic sigmoid). For regression problems you may use linear outputs (identity activation function).
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Is $\epsilon$ always contained in $\Sigma^*$?
Please correct me on any terminology. For some reason I'm a bit confused.

$\Sigma = \\{\epsilon, 0, 1\\}$

This means my alphabet, $\Sigma$, contains three symbols ($\epsilon, 0, 1$).

$\Sigma^\*$ is the language over $\Sigma$, and it equals $\\{\epsilon, 0, 1, 01, 10\\}$.

My regular expression for $\Sigma^\*$: $\epsilon+0+1+(01)+(10)$.

First question: Does every $\Sigma^\*$ include $\epsilon$? I see some with, and some without. I feel like this is a big difference because your regular expression and DFSA will be different.

Second question: At this point, I would have five accepting states in a DFSA? Since the first state is the empty string, is it $\epsilon$? Or is the first state just nothing, which transitions to a second state via $\epsilon$ which contains the empty string?

# Answer
Normally, $\epsilon$ stands for the empty string: the string with no characters, which would be `""` is most programming languages. It's too confusing to have $\epsilon$ be a symbol in the alphabet, so I'm going to rename it and write your alphabet as $\Sigma=\\{e,0,1\\}$. (The alternative would be to use some other symbol to denote the empty string.)

Now, *by definition*, $\Sigma^\*$ is the set of all finite strings that can be written using the characters of $\Sigma$. This always includes the empty string $\epsilon$ and, as long as $\Sigma\neq\emptyset$, it also contains strings of all finite lengths. So the claim in the question that $\Sigma^\*=\\{e, 0, 1, 01, 10\\}$ is incorrect: $\Sigma^\*$ is an infinite set.

The regular expression for $\Sigma^\*$ is $(e+0+1)^\*$; the automaton consists of a single state, which is accepting and has transitions to itself for each symbol in $\Sigma$.
> 5 votes

# Answer
This is not the easy answer. It attempts to explain in detail the source of the confusion. With apologies as it makes also for a very long answer.

Your confusion is related to an issue that is both essential and often glossed over, the **distinction between syntax and semantics**. It is often the source of confusion in some formal issues.

In any discourse, these two aspects are always both present, but often not cerefully distinguished, though there are notations to do so in writing, but not so much in speech.

Typically, to make the distinction clear, a dog may bite you (not mine), but the word "dog" does not bite and is the syntactic representation of the concept of dog, or possibly of a specific dog.

You always have a syntactic discourse (what gets spoken or written), but it is always intended to stand for semantics concepts, to represent them. When you say: "I am hungry", you utter three words meaning to convey the idea that you feel like eating something. Alternatively you could say it in German: "Ich bin hungrig" , or in French: "j'ai faim", with a different syntactic representation, but with the same meaning, i.e. the same semantics. Note that, in writteh form at least, the syntactic representation is always a sequence of characters, all belonging to the Latin Alphabet in this case, which is a collections of representation symbols.

Similarly, the same number can be represented syntactically by "7" in decimal notation, by "VII" in Roman numerals, by "111"in binary positional nottion, by "lllllll" in unary notation, by "seven"in English, etc. An important remark is that the choice of notation can make you life and your communication easier or harder, exactly like the proper choice of representing data structure in algorithm design (these are closely related problems).

The difficulty of formal languages is that they are used to study syntax. Thus formal syntax becomes the semantic part of the discourse, and you need a syntax to represent it. And this can become very confusing.

To discuss about syntax, as the semantic topic of the discussion, you first define an alphabet. To remain abstract, we give it a mathematical name which could be anything, but we often choose the name $\Sigma$. Of course, we have to know the symbols in that alphabet (like letters in the Latin alphabet), so we define the set of symbols that compose it, by writing: $\Sigma=\\{a,b,4,5,\eta,+\\}$ if these are the 6 symbols we want to use.

Note that this notation is probably an abuse. If you really want to talk about these symbols, they should be written between quotes, for example as '$a$', '$b$', '$4$', etc. to distinguish the symbol as semantic object from the syntactic representation used to talk about it, exactly as I did above to explain that the word "dog" never bites.

But this would be tedious and awkward to write and read, so that there is an unsaid convention that, unless it is necessary for better understanding, the symbols are allowed not to be quoted and to stand for themselves as semantic objects.

Now symbols can be concatenated into strings. The word "dog" is typically a string of 3 letters (letteres being symbols). Strings can have any finite length, i.e. any number of symbols, including zero. They are often represented by the sequence of symbols composing the string, surrounded by double quotes. An English written word is a string of letter, and that is why I wrote "dog" thus to mean the string that represent a dog. Of course, the string of length 0, containing no symbol, is then represented by "", with nothing between te quotes.

Note that, in strict mathematical sense, a string of length 1 may have to be distinguished from the character that composes that string. Hence the notation differ, with single or double quotes. But that is not always respected, assuming for example that context will tell which is intended.

When talking of syntax, the convention of having symbols stand for themselves is often extended to strings, which get written without quotes, though othen with a different font (italics), which is similar to quoting. It is usually easy to read, except for the empty string which becomes invisible if it is to stand for itself, without external markers.

Hence, the solution is to use a special syntactic representation for the empty string, to give it a name. This name is often, in mathematical text, the Greek letter $\epsilon$, or sometimes the Greek letter $\lambda$.

If the alphabet is noted $\Sigma$, then $\Sigma^\*$ represents (is the syntactic representation for) the set of all finite strings composed of symbols of $\Sigma$, including the empty string, however represented. There is no upper limit to the length of these string (but they are all finite), so that their number is infinite. In the case of your example, it is any finite sequence of $0$ and $1$ in any order.

In your question, you represent strings as standing for themselves, without quotes, so the representation for the empty string is naturally $\epsilon$. Hence, you *always* have $\epsilon\in\Sigma^\*$, independently of the symbols that $\Sigma$ contains.

But if you write $\Sigma=\\{\epsilon,0,1\\}$, you are saying that you have an alphabet with three symbols, '$\epsilon$', '$0$', and '$1$', precisely as you say in your question. But then, of course, the symbol $\epsilon$ stands for itself, and can no longer be used to represent the empty string.

This creates a lot of confusion for readers, since they are used to see it as standing for the empty string. So it should be avoided.

When $\Sigma=\\{0,1\\}$, the regular expression for $\Sigma^\*$ is $\Sigma^\*=(0+1)^\*$. Basically, it is the Kleene star closure operator applied to the set of all strings of length 1 on alphabet $\Sigma$.

The corresponding minimal deterministic finite state automaton (DFA) has only one state $q$, and a transition from that state to itself for any symbol in $\Sigma$. The state $q$ is bot initial state and final accepting state. Since the initial state is an accepting state, it does not need to read any symbol to recognize the input. Thus it can recongnize an empty input, i.e. $\epsilon$. Any DFA that recognizes a language containing the empty string $\epsilon$ must have an initial state that is also an accepting state.
> 2 votes

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


# Question
Title: What is the relation between a regular language, $L$, and $\Sigma^*$?
Let's say I have $\Sigma = \\{0\\}$.

Can a language $L$ be as large as $\Sigma^\*$? So $L = \Sigma^\*$.

Can a language $L$ be as small as just $\\{0\\}$? A subset of $\Sigma^\*$.

Can multiple languages, $L\_1, L\_2$, come from the same $\Sigma$, i.e. be subsets of the same $\Sigma^\*$?

# Answer
> 1 votes
A language is any set of finite strings on a given alphabet. $\Sigma^\*$ is the set of all finite strings on the alphabet $\Sigma$. Hence ...

> Hence $\Sigma^\*$ is a language on the alphabet $\Sigma$.

The set $\\{0\\}$ contain only strings on the alphabet $\Sigma$. Hence ...

> Hence $\\{0\\}$ is a language on the alphabet $\Sigma$.

But it is not the smallest language on the alphabet $\Sigma$.

For example $\\{000000000000\\}$ and $\\{\epsilon\\}$ are other languages on the alphabet $\Sigma$ that contain a single string.

And there is a smaller one: the empty language $\emptyset$ is the smallest language on the alphabet $\Sigma$, and contans no string.

But the union of two languages on the alphabet $\Sigma$ is a language on this alphabet, so taking for example the union of the above: $\\{000000000000,\epsilon,0\\}$.

So, if my count is right, we have 6 different languages from alphabet $\Sigma$, thus all subsets of $\Sigma^\*$, which should answer your last question.

---
Tags: formal-languages
---


# Question
Title: Can I couple non-terminals in context-free grammars?
If I had productions like so...

$S \rightarrow A1B$

$A \rightarrow \epsilon$

$A \rightarrow 0$

$B \rightarrow \epsilon$

$B \rightarrow 1$

If I only want strings $\\{\epsilon1\epsilon, 011\\}$, am I allowed to choose when both $A$ and $B$ become $\epsilon$? Or will I get resulting strings such as $\epsilon11$ and $01\epsilon$? (I know the $\epsilon$'s disappear, but I just left them in to avoid confusion.)

If I get the unwanted strings, then how would you force both $A$ and $B$ to be $\epsilon$ only when you need them to be, while still having $A$ and $B$ result in different *terminals*?

# Answer
> 2 votes
In your case, the desired language is *finite*, so you can just go

$\qquad\displaystyle S \to 1 \mid 011$.

If you had recursion, say

$\qquad\displaystyle S \to ASB \mid 1$

as starting rule, you can *not* force "matching" $A$ and $B$ to behave in sync. There are more powerful types of grammars that can do that, but that's beyond the power of context-free.

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


# Question
Title: What's wrong with my pumping lemma proof?
The language $L = \\{0^{2n} \space |\space n \ge 0 \\}$ is obviously regular – for example, it matches the regular expression $(00)^\*$. But the following pumping lemma argument seems to show it's not regular. What's gone wrong?

I've found a way of splitting an input $s$ as $xyz$ satisfying the requirements of the pumping lemma but it's not true that $xy^iz\in L$ for all $i$. Doesn't that mean the language isn't regular?

In more detail, the pumping lemma for regular languages says that, if a language $L$ is regular, there exists pumping length $p \ge 1$ such that any string $s\in L$ with $|s|\> p$ can be written as $s = xyz$ such that:

1. $\lvert y \rvert \ge 1$
2. $\lvert xy \rvert \le p$
3. $xy^iz\in L$ for all $i \ge 0$.

So, let's take $s = 0^{2p}$ and write it as $s=\epsilon\\, 0 \\, 0^{2p-1}$ (i.e., $x = \epsilon$, $y = 0$, $z = 0^{2p-1}$). This satisfies 1. and 2. But, taking $i=0$, we get $xy^iz = \epsilon\\, 0^0\\,0^{2p-1} = 0^{2p-1}$, which isn't in $L$ because its length is odd. So it looks like the language isn't regular after all.

---

This is intended as a reference question illustrating a common mistake in the use of the pumping lemma for regular langauges. Thanks to Ariel for spotting the issue in the original version of the question.

# Answer
The problem is in the quantifiers. The pumping lemma says that any string $s$ with $|s|\geq p$ *can* be written as $xyz$ such that the three properties hold. It doesn't say that *every* way of writing it as $xyz$ that makes the first two properties hold also makes the third one hold.

For the language $\\{0^{2n}\mid n\geq 0\\}$, we proceed as follows. First, note that we must have $p\geq 2$, since if $p=1$, we're forced to take $x=\epsilon$, $y=0$, $z=0^{2p-1}$ and you already showed in the question that this doesn't work. So, with $p\geq 2$, we can write $s = 0^{2p}$ as $s=\epsilon\\,00\\,0^{2(p-1)}$ ($x=\epsilon$, $y=00$, $z=0^{2(p-1)}$). We have $|\epsilon00| \leq p$, $|00|\>1$ and $(00)^i\\,0^{2(p-1)}\in L$ for all $i\geq 0$. Thus, there exists *some* way of decomposing the string as $xyz$ that satisfies all the properties, even though the first decomposition you thought of didn't work.

To show that a language isn't regular, you need to show that *every* decomposition into $xyz$ that satisfies the first two properties fails to satisfy the third one. It's not enough to just show that one decomposition doesn't work.

To understand why the pumping lemma is the way it is, it helps to think about the proof. If a language is regular, it is accepted by some DFA. That DFA has some number of states: call it $p$. By the pigeonhole principle, whenever that DFA reads a string longer than $p$, it must visit some state twice: say state $q$. Now, $x$ is the part of the input read upto (and including) the first visit to $q$, $y$ is the part read after the first visit and upto and including the second (which must be at least one character) and $z$ is the rest. But now you can see that $xz$ must be accepted: $x$ takes you from the start state to $q$ and $z$ takes you from $q$ to an accepting state. Likewise, $xy^iz$ must be accepted for any positive $i$, since each repetition of $y$ takes you from $q$ back to $q$. Note that the decomposition of the input into $x$, $y$ and $z$ is entirely determined by the automaton which is, in turn, determined (but not uniquely) by the language. So you don't get to choose the decomposition: if the langauge is regular, *some* decomposition exists; to show that a language is not regular, you must show that *every* decomposition fails.
> 8 votes

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


# Question
Title: Finding similar high dimensional real vectors
I have a collection of vectors $v\_1,v\_2\in \[0,1\]^n$ and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric $L: \[0,1\]^n \times \[0,1\]^n \longrightarrow R$. $n$ will be around $200$.

I've implemented Locality Similar Hashing (LSH) for word based documents, and I'm curious if there's an adaptation of it which will work for real based vectors.

I read here on Computer Science Stackoverflow that universal hashing will work.

If I have the vector $s=(0.55, 0.34, 0.90, 0.99)$ I can break it up into two sub vectors $s\_1=(0.55, 0.34)$ and $s\_2=(0.90, 0.99)$ and apply a universal hash to each:

$h\_n= a\cdot s\_n \space mod \space p$

Where $a$ is a random vector and $p$ is prime. I can now define a space of bins, where each $h\_n$ defines a bin in this space. Each vector with a subvector in $h\_n$ is mapped to the bin $h\_n$

The problem is that this method is too precise. The vectors $(0.57, 0.34)$ and $(0.55, 0.34)$ are very similar but will get mapped to different bins.

I'm wondering if it's there's any theoretical and practical issues with either truncating the last digit or rounding up/down such that both vectors are now mapped to a bin representing the vector $(0.5, 0.3)$

This I believe is equivalent to multiplying all the vector elements by 10 and truncating the decimals, leading back to normal LSH.

I'm quite new at all this, so please forgive the slight errors in notation or understanding.

# Answer
## One approach: Quantization

One approach is to quantize the values, then apply an existing LSH that works on discrete values. In other words, you split up the space $\[0,1\]$ into several ranges, map each real number to its containing range, and then apply an existing LSH that works with discrete values. This is essentially equivalent to first truncating each coordinate of the vector, then applying some discrete LSH.

For example, suppose you split the interval $\[0,1\]$ up into ten ranges, $\[0,0.1)$, $\[0.1,0.2)$, ..., $\[0.8,0.9)$, and $\[0.9,1.0\]$. Now you can map any value in $\[0,1\]$ to its corresponding range -- this is basically just truncating to keep only the first digit in the decimal representation. Map each interval to a digit from 0 to 9: e..g, $\[0,0.1) \mapsto 0$, etc. In this way, given any vector $v \in \[0,1\]^n$, you can get a new vector $w \in \\{0,1,\dots,9\\}^n$. For instance, the vector $v=(0.55,0.34,0.90,0.99) \in \[0,1\]^4$ maps to the new vector $w=(5,3,9,9) \in \\{0,\dots,9\\}^n$.

The new vector $w$ is in a discrete space, rather than in a continuous space. Now if you have a LSH that works on this discrete space, you can apply it to $w$. For instance, suppose $h\_1:\\{0,\dots,9\\}^n \to \mathbb{R}$ is a locality-sensitive hash (LSH) on this discrete space. Let $f:\[0,1\]^n \to \\{0,\dots,9\\}^n$ be the mapping that sends each real number to its corresponding range, i.e., $f(v)=(g(v\_1),\dots,g(v\_n))$ where $g(x)= \lfloor 10x \rfloor$ is the truncation map $g:\[0,1\] \to \\{0,\dots,9\\}$. Define $h\_0 : \[0,1\]^n \to \mathbb{R}$ by $$h\_0(v) = h\_1(f(v)).$$ Then $h\_0$ is a LSH on continuous values.

If you plan to generate multiple different LSHs, it's probably slightly better to apply the following tweak. Pick a random $n$-vector number $r \in \[0,0.1)^n$. Now the LSH for $\[0,1\]^n$ is defined to be $h\_0(v) = h\_1(f(v+r))$ as above, where $f:\[0,1\]^n \to \\{0,1,\dots,10\\}^n$ is the truncation map defined as above and $h\_1:\\{0,1,\dots,10\\}^n\to\mathbb{R}$ is a LSH on discrete values. This tweak lets you generate multiple independent LSH's for $\[0,1\]^n$. If you are only picking a single hash function, you can skip this step.

There's nothing special about base-10. Instead of using base-10, you can also use base-2 or any other base. The performance will depend upon the base you use as well as the specific discrete LSH you choose, so you might need to play with the options to see which is best overall. I suspect you will find that the optimal choice of base is base $b=2$ or $b=3$ (and, if your discrete LSH is based upon hashing a random subset of the coordinates, choosing a subset of size proportional to $\sqrt{n}/b$), but it's not possible to give a hard-and-fast rule: the optimum depends to some extent on the distribution of your data. That's why I suggest trying a few different parameter choices to see which seems to work best on your data.

This is basically the "truncation" idea in your original post (truncate all real values, then apply a discrete LSH), but now we apply it to the entire vector, rather than trying to split the vector in half. Of course, the discrete LSH might itself work by picking a few randomly chosen coordinates and hashing only those coordinates (e.g., using a universal hash).

## Another approach: Use a LSH designed for continuous values

There are also some LSH's that are designed specifically for continuous real numbers. I don't know if there are any for the Euclidean distance.

## A totally different approach: nearest-neighbor data structures

Finally, it's worth mentioning that there are also other approaches to this problem that don't involve LSH's at all. There are some data structures that are designed to support nearest-neighbor search (or approximate nearest-neighbor search). You might look at metric trees, k-d trees, and nearest-neighbor search.

However, beware of the curse of dimensionality. If the dimension $n$ is large, none of these approaches are likely to work well: high dimensions are just plain hard. For instance, one rule of thumb I've seen is that k-d trees tend not to work well when $n \ge 30$. I'm not sure any of these techniques will be terribly effective when $n$ is large: nearest-neighbor search in high dimensions is hard.
> 2 votes

---
Tags: hash, cluster
---


# Question
Title: How can I take advantage of the capabilities of a cluster
I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that there are different "nodes" ? My program is not designed to take advantage of this individually - it can't event take advantage of multiple processors, because the calculations have to be done in sequence. But I have to run multiple instances of the program, and I was hoping there'd be a way to run them on separate "nodes" (?) to avoid them having to share CPU time too much.

What I know : the cluster runs Red Hat Enterprise Linux for Servers 5.3.

Can anyone help?

# Answer
> 2 votes
According to my experience, clusters usually work like this: you submit a job to it (a program), and it allocates a node to run your job. You don't worry about allocating the nodes yourself.

So in your case, simply submit multiple jobs (usually they provide some method to submit batch jobs), and the cluster will allocate different nodes to each of them.

---
Tags: distributed-systems, parallel-computing
---


# Question
Title: Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?
Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le\_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, $\mathrm{L} \in \mathrm{NTIME}(n)$. Thus, $\mathrm{NTIME}(n^3)\subseteq \mathrm{NTIME}(n)$ which implies the non-deterministic time-hierarchy is false.

But we all know that time hierarchy is true. Where am I going wrong? The statement seems to be correct but I know it's wrong. How?

# Answer
> 9 votes
The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $L\in\mathrm{NTIME}(n^3)$.

---
Tags: complexity-theory, reductions, complexity-classes
---


title: Do sparse graphs have to be large?

text:
# Question
Title: Do sparse graphs have to be large?
I'm looking for a good definition of sparse graphs. Is a sparse graph effectively a big one, with millions/billions of nodes? An example from real world is the Facebook graph. Or can sparse graphs be in small networks as well?

# Answer
The common definition is that a *family* of graphs $G = (V, E)$ is sparse if $m \in o(n^2)$, with $n = |V|$ and $m = |E|$. Formally, that requires the family to be infinite, and we only know something *in the limit*.

The definition does not apply to graphs of a fixed size per se. One would certainly want $m \ll n^2$ in some sense. For instance, if $m \leq 5n$ or $m \approx \log n$ you would probably say that your graph is "sparse".

You can bridge this gap by requiring a bit more on the asymptotic side. Say we call a family of graphs sparse if

$\qquad\displaystyle m \leq f(n) + O(1)$ with $f \in o(n^2)$;

then we may want to call every graph with $m \leq f(n)$ sparse. The implicit assumption is that the error term hidden in $O(1)$ is well-behaved.
> 5 votes

# Answer
Sparsity is a fuzzy notion, and its meaning will depend on the context. It can be argued a graph is not sparse "by itself", but rather it is sparse relative to other graphs. Indeed, there are several ways to define or measure sparseness.

We can say a connected graph is maximally sparse if it is a tree. Intuitively, a tree-like graph is sparse. But what could be a "tree-like graph"? Perhaps the number of cycles is bounded, or by removing a constant number of vertices we get a tree. One very popular definition of sparseness rises from these considerations. Informally, the *treewidth* of a graph is a measure of how close a graph is to being a tree.

To address your question, a graph of low treewidth can be either small or large. For instance, forests, trees, and outerplanar graphs all have constant treewidth. In contrast, a complete graph on $n$ vertices has treewidth $n-1$. This corresponds to our intuition that complete graphs are *not* sparse.

Treewidth is just one measure of sparseness. You can dig deeper into the literature and explore other measures as well.
> 3 votes

# Answer
A graph is dense if the number of edges is closer to the maximum number of edges there could be. Formally, a graph is dense if $e=\cal \Omega(v^2)$ where $v,e$ are the number of vertices and edges. A graph is sparse if the above is not true.
> 2 votes

---
Tags: graphs, terminology
---


# Question
Title: Partitioning planar graphs without minimizing edge cuts
I am looking for an algorithm that, given an undirected, *planar* graph $G = (V,E)$ with node weights, meets the following conditions:

1. Creates balanced (within some margin) $k$ partitions of $V$ according to node weight.
2. All partitions have to be connected.
3. It cannot minimize communication volume, or edge cuts.

My graphs are planar, all vertex weights are positive integers, and the reason that I want #3 is that I need to be able to generate $n$ distinct partitions from the graph that I have. I have found that if I use GPMetis, no matter what options and seed I pass it (currently using `-seed=40 -ctype=rm -iptype=random -ptype=kway`). The options have an impact only if I scale up the number of vertexes (on my graphs that have less than 100 nodes, it always gives the same answer).

Are there algorithms that exist to create balanced partitions by vertex weight that meet these conditions? It doesn't need to ignore edge counts/weight entirely, so long as I can still make the result different via some seed. Willing to take either a research paper, or fully functional code.

As background:

* I know that a vertex separator can be found in polynomial time for planar graphs, but I need all my vertices.
* There are several edge cut algorithms that also run in near polynomial time, but these have the problem listed above of not being able to inject sufficient randomness.

# Answer
One general method is to perturb the node weights slightly, find a good partition, and repeat that $n$ times with $n$ different perturbations.

The basic algorithm is something like this:

* Repeat until you have $n$ distinct balanced partitions of $G$:

1. Copy $G$ to $G'$. Randomly perturb the weight of each node in $G'$ by a tiny amount (a different random change for each node).
    2. Find a balanced partition of $G'$. This corresponds to a partition of $G$.
    3. If this is a legal, balanced partition of $G$ and you haven't seen this partition of $G$ before, add it to your list of distinct partitions.

If you choose the amount of the perturbation correctly, then you can expect this will need only $O(n)$ iterations of the loop to find $n$ distinct partitions.

Let's see in a little more detail how to make this work in your setting and why it works. The basic idea is to add a tiny, tiny random perturbation to each node's weight. This won't affect the total weight of any group in your partition by very much: the sum of a bunch of of tiny numbers is still quite small, and in particular, we can ensure it will be much smaller than 1. Since the total weight of any group of vertices in $G$ has to be an integer, the change in its total weight can't be enough to make it jump up to the next integer. Consequently, this won't change the relative order of vertex-groups (if one vertex-group has a smaller weight than another vertex-group, after perturbation its weight cannot become larger); all it can do is break ties.

However, this basic idea has a problem: after perturbation, the vertex weights in $G'$ are no longer integers. It's possible that your underlying algorithm (e.g., Metis) requires the vertex weights to be integers. If so, here is how we can fix things up and preserve the integrality of node weights. The idea is to first scale up all of the weights by a large integer constant $c\_1$, then add a small integer perturbation to each node weight. Formally, let $w\_v$ be the weight on node $v$. We're going to pick integer constants $c\_1,c\_2$ and for each node $v$ set

$$w'\_v = c\_1 w\_v + r\_v,$$

where $r\_v$ is a random integer chosen from $\\{0,1,\dots,c\_2\\}$ (chosen independently for each node). We'll use $w'\_v$ as the weight of node $v$ in $G'$.

How do we choose $c\_1,c\_2$? Basically, we need $c\_2$ to be large enough so that each iteration is likely to give you a new partition, and we need $c\_1/c\_2$ large enough so that a balanced partition of $G'$ is likely to also be a balanced partition of $G$. One reasonable setting is to use $c\_2=100n$ and $c\_1 = 100 |V| c\_2$. Alternatively, if your underlying algorithm is OK with non-integer vertex weights, you could instead pick $r\_v$ randomly from the range $\[0,1/(100|V|)\]$ and just leave $c\_1=1$.

Why does this work? Well, first note if we divide all the weights in a graph by a constant, that has no effect on the set of balanced partitions -- so we might as well consider the weights to be $w''\_v = w\_v + r\_v/c\_1$. Now I claim that a balanced partition of $G'$ is almost certainly a balanced partition of $G$. Any single group in the partition has at most $|V|$ vertices, and the weight of each node in the group has been randomly increased by at most $c\_2/c\_1$, so the total increase in the weight of that group is at most $|V|c\_2/c\_1=0.01$. Originally the total weight of a vertex-group has to be integer, so this perturbation is not enough to make it jump up to the next integer. Now, depending upon your definition of balanced, most likely the following will be true: any balanced partition in $G'$ has a high probability of being a balanced partition in $G$.

Also, the random perturbations ensure that, if you look at two perturbed graphs $G'\_1,G'\_2$, it is unlikely that the optimum partition of $G'\_1$ is the same as the optimum partition of $G'\_2$.

So, I suggest you give this a try.

---

Important caveats: There are no guarantees this will work. From a theoretical perspective, it's not guaranteed to work. Indeed, I suspect your problem might be NP-hard, so it would be too much to expect this to always work. But in practice, this often works, if you are in a situation where your underlying algorithm (e.g., Metis) is able to find the optimum partition in a reasonable amount of time. As a pragmatic guideline, it's more likely to work if the underlying algorithm can find an exact optimum rather than an approximate-optimum (e.g., maximally balanced rather than close-to-maximally-balanced). However, as I said, there are no guarantees, so the best way to find out whether it will work in your particular situation is to try it out and see.
> 2 votes

---
Tags: algorithms, graphs, optimization, partition-problem, planar-graphs
---


# Question
Title: Is the language of Turing Machines that halt on every input recognizable?
I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is not recognizable. Does anyone know how to do this reduction, what I come up with is:

Using python-like syntax:

```
def R(<M>,w):
    def F(x):
        if M(w)loops: //Run M on w
            return True on every x
        else
            loop on every x
return F

```

Of course the problem here is that we can't really know when M loops on w

Does anyone know how to do this reduction, or if it is possible to prove that the language of TMs that accept every input string is unrecognizable using a reduction from a different unrecognizable language?

# Answer
> 10 votes
**Preliminary**

Let $H$ be the usual halting language: $$ H=\\{(\langle M\rangle, w)\mid M(w) \text{ halts}\\} $$ Its complement is $$ \overline{H}=\\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\\} $$ We know that $H$ is recognizable (just run $M$ on $w$ and do what it does), so $\overline{H}$ must be unrecognizable (otherwise $H$ would be decidable, which we know isn't true).

**The Reduction**

As you suggested, we'll produce a reduction from $\overline{H}$ to $$ AH = \\{\langle N\rangle\mid N \text{ halts on all }x\\} $$ thus showing that $AH$ is unrecognizable. As you suggested, what we want is to map $(\langle M\rangle, w)$ to a description of a TM $M\_w$ where

```
Mw(x) =
   run M on w
   if M(W) halts
      loop
   if M(w) doesn't halt
      halt

```

That would do it, except for the fact that if $M$ didn't halt on $w$, we'd never get to the $\texttt{halt}$ instruction. What we need is a *finite* way of testing for non-halting. A standard way to deal with this kind of difficulty is to limit the number of steps our simulation will perform, like this:

```
N(x) =
   run M on w for |x| steps
   if M has halted
      loop
   if M(w) hasn't halted yet
      halt

```

How does this modification help us?

* If $(\langle M\rangle, w)\in\overline{H}$, then $M(w)$ will never halt, so $N(x)$ will halt after $|\\,x\\,|$ steps and thus $\langle N\rangle\in AH$
* If $(\langle M\rangle, w)\notin\overline{H}$ then $M(w)$ will eventually halt, say after $s$ steps. This means that $N$ will halt on all inputs, $x$ of length less than $s$, and will loop on all longer inputs, so $\langle N\rangle\notin AH$.

This establishes the reduction we needed, and so we can conclude that $AH$ is non-recognizable.

---
Tags: computability, turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points?
Is there a known/existing algorithm for taking a 2D canvas covered in arbitrarily/randomly distributed points and dividing it entirely into a set of non-overlapping polygons? An example of the kind of result I'm looking for:

# Answer
You might be looking for a Voronoi diagram. Given a set $S$ of points, it creates one cell per point, where the cell for point $p$ contains everything that is closer to $p$ than to any other point in $S$. There are algorithms to compute a Voronoi diagram in $O(n \lg n)$ time, where $n$ is the number of points in your set.
> 12 votes

# Answer
Yes, there are even algorithms which are able to satisfy additional constraints. It can occur as a subtask during mesh generation. The vanilla algorithm is the Delaunay triangulation, which is closely related to the Voronoi diagram (in case you wonder why D.W. thinks that the Voronoi diagram answers your question).
> 13 votes

---
Tags: algorithms, graphs
---


# Question
Title: Algorithm to check the distance between integers
I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case.

I have a sorted array of pairwise distinct integers, say $\[1,2,4,5,7,8\]$ I need to know if there is a gap of at least two between two consecutive integers, i.e., if there are successive integers $a$ and $b$ in the list with $b\>a+2$.

For example in the array given, the algorithm should return false, but for $\[2,3,6,7\]$, it should return true. Is it possible to solve it by mathematics instead of iterate and compare the integers one by one?

I will add some inputs and the desired output:

* \[1,2,4\] -\> false
* \[1,**2,5**\] -\> **true**
* \[1,2,4,6,8\] -\> false
* \[1,3,4,6,8\] -\> false
* \[**1,4**,6,8\] -\> **true**
* \[1,3,5\] -\> false

# Answer
If you allow no missing elements, there is indeed an algorithm that does not need to check all values:

Since the numbers are distinct and sorted, the algorithm

$\qquad\displaystyle \[a\_1, \dots, a\_n\] \mapsto \begin{cases} \mathrm{true}, &a\_n = a\_1 + n - 1,\\ \mathrm{false}, &\text{else} \end{cases}$

solves the problem.

If $a\_n \geq a\_1 + n$ there has to be a step larger than one. On the other hand, $a\_n \< a\_1 + n - 1$ can not happen without duplicates (pigeon-hole principle).

---

If you allow some missing elements but not too many in a row, this no longer works. We will show this by an adversary argument.

Assume there was a deterministic, correct algorithm $A$ that reads $\<n$ of the input values. Then, $A$ answers `false` for inputs with $n$ elements of the form

$\qquad\displaystyle I\_1 = \[1,3,\dots,2n-1\]$.

By assumption, $A$ does not read at least one value; let's call that one $i$. Without loss of generality, let $i \not\in \\{1, 2n-1\\}$; these cases can be dealt with similarly. Then, $A$ *also* answers `false` on

$\qquad\displaystyle I\_2 = \[1,\dots,i-2,\mathbf{i+1},i+2,\dots,2n-1\]$

because it is deterministic; if it does not read $i$ on $I\_1$ it will also not read $i+1$ on $I\_2$ since the other elements are all the same.

But this result is wrong since there is a gap of $(i+1) - (i-2) = 3$ in $I\_2$. This contradicts our assumption that $A$ is correct; therefore, there can be no such algorithm.
> 3 votes

# Answer
Please have patience with a programmer's view.

For a range (initially the full range) consider the difference between last and first element.

* There is a known minimum up to which **no overflow** is possible.
* There is a known maximum from which **an overflow** is always present.
* Between it is **unknown**, and one may split the range in two lesser and recurse the algorithm.

By recursively splitting the full range in sub-ranges, one should eventually find a violating range, be it an adjacent pair.

Also without recursion, one has a (very) **partial** function yielding `{false, true, unknown}`.

The worst case would still be a full iteration.

```
boolean overflowsDistance(int[] data, int maxDistance) {
    return overflowsDist(data, maxDistance, 0, data.length);
}

// i: start index, j: index after last index.
private boolean overflowsDist(int[] data, int maxDistance, int i, int j) {
    if (i >= j + 1) { // Empty or singleton range
        return false;
    }

    // Heuristic short-cut we hope for:
    int maxAllowable = (j - i) * maxDistance;
    int actual = data[j - 1] - data{[i];
    if (actual > maxAllowable) {
        return false; // There must be an overflow
    }
    // Case monotone integers like [1, 1, 1, 3, 3, 4]:
    if (actual <= maxDistance) { // There cannot be an overflow
        return true;
    }
    // Case distinct integers like [1, 2, 4, 6]:
    if (actual <= maxDistance +  j - i) { // There cannot be an overflow
        return true;
    }

    // Split range:
    int mid = (i + j) / 2;

    return overflowsDist(data, maxDistance, i, mid + 1)
        orelse overflowsDist(data, maxDistance, mid, j);
}

```

I would not even call the normal behavior O(log N) as an individual overflow is camouflaged by the possibility of having many small increments. *Which makes this an interesting programmer's puzzle.*
> 0 votes

---
Tags: algorithms, arrays
---


# Question
Title: Is the superset and subset of a semi-decidable language also semi-decidable?
Given three languages $L\_1, L\_2, L\_3$ with $L\_1$ and $L\_3$ being semi-decidable and $L\_1 \subseteq L\_2, L\_2 \subseteq L\_3$. Can I deduce from these properties, that $L\_2$ is also semi-decidable and how would I proof this?

Intuitionally it seems obvious that $L\_2$ is also semi-decidable, but I didn't find a way to prove (or falsify) it.

So far I only found information about the closure of semi-decidability under $\cup$ and $\cap$. Can I use these properties in any way?

# Answer
> 0 votes
No, because every language $L$ satisfies $$ \emptyset \subseteq L \subseteq \Sigma^\* $$ and $\emptyset$ and $\Sigma^\*$ are both semi-decidable.

---
Tags: semi-decidability
---


# Question
Title: Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?
The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time.

$$LIN \subseteq P$$

Since HORN-SAT is solvable in $O(n)$ (as indicated in Linear-time algorithms for testing the satisfiability of propositional horn formulae (1984))

> New algorithms for deciding whether a (propositional) Horn formula is satisfiable are presented. If the Horn formula $A$ contains $K$ distinct propositional letters and if it is assumed that they are exactly $P\_1,…, P\_K$, the two algorithms presented in this paper run in time $O(N)$, where $N$ is the total number of occurrences of literals in $A$.

I am wondering why we can't conclude that

$$LIN = P$$

given that HORN-SAT has also been proven to be $P$-complete under log-space reduction? I must be missing something. Or is that a well-known fact?

(I have yet thoroughly gone through the 1984 paper so I don't quite understand the algorithms for solving HORN-SAT in linear time, and thus I may have misunderstood the implication.)

# Answer
> 11 votes
Because log-space reductions don't necessarily run in linear time. If you take a problem in P and try to reduce it to HORN-SAT, there will be a log-space reduction, but that reduction might take more than linear time. Thus even though HORN-SAT can be solved in linear time, the other problem might not be solvable in linear time: you can convert it into a HORN-SAT instance and then solve the HORN-SAT instance, but the conversion process might itself take more than linear time.

A log-space reduction is one where the amount of space used is $O(\lg n)$, where $n$ is the input size. In particular, it might use $c \cdot \lg n$ bits of space, for some constant $c$. Now it's known that any deterministic algorithm which uses at most $b$ bits of space runs in time at most $O(2^b)$ \[if it's guaranteed to terminate\], as there are only $2^b$ possible different states, and if the algorithm visits any state more than once, it will loop forever. Consequently, a reduction that uses $c \cdot \lg n$ bits of space will have running time at most $O(2^{c \lg n})$. However, $2^{c \lg n} = (2^{\lg n})^c = n^c$, so the only conclusion we can draw is that the reduction runs in $O(n^c)$ time, i.e., in polynomial time.

In other words: a log-space reduction can take more than linear time to execute. Its running time can be any polynomial in $n$.

# Answer
> 11 votes
The deterministic time hierarchy theorem precludes all problems in P being decided in linear time. If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll find that the reduction itself requires more than linear time.

---
Tags: complexity-theory, time-complexity, reductions
---


# Question
Title: Converting final state PDA to empty stack PDA
I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n \> m } $

A final state acceptance PDA for this language would push $A$ symbols in the stack for every 'a' input, and pop them for every 'b' input. If the stack has no more $A$s while we still have 'b' inputs to process, the automaton goes in a non-accepting state, and the string is not accepted.

---

To convert this to an empty stack acceptance PDA, I add the two states, one before the previous start state, and another state after the last to empty the stack. Whenever the inner automaton goes to the accepting state, it also moves to the empty-stack state with an $\epsilon$ transition.

If I test the string $aabbb$, after we process the first 3 characters, we still have an $A$ symbol in the stack, but the automaton moves to the empty-stack state with an $\epsilon$, it empties the whole stack, therefore the string is accepted.

Where is my mistake in this reasoning?

# Answer
Your description of the construction is wrong. The new automaton has a new initial stack symbol, from the new start state it places the original PDA's initial stack on top of it and moves to the original's start state. The new initial stack can only be removed in a new state that is entered via $\epsilon$ from final states, and in this new state all that is done is to slurp down the stack's contents.

This is activated from any final state, and the automaton can end up with empty input and empty stack only if the original reached the final state at the end of the input.
> 3 votes

---
Tags: automata, pushdown-automata, simulation
---


# Question
Title: Push Down Automatons "guess" - what does that mean?
I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown.

Still, I do not understand *how* exactly they "choose". For palindormes for example every source I found just says the automaton "guesses" the middle of the word. What does that mean?

I can think of several possible meanings:

1. It goes into one state randomly and therefore might not accept a word, which actually is in the language
2. It somehow goes "every possible way", so if the first one is wrong it tests if any of the other might be right
3. There is some mechanism I am not aware of, that chooses the middle of the word and is therefore not random, but the automaton always finds the right middle.

This is just an example; what I want to know is how it works for any automaton that has several following states for one and the same state before it.

# Answer
> 9 votes
Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them.

Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a theoretical device, which can be used to simplify the presentation of certain concepts.

For the palindrome, you can think about it in two ways. Either there's a magical power that lets your machine say "this is the middle of the word, time to switch from pushing to popping", or after reading each letter, it says "I'm going to fork a new process which that this letter is the middle of the word, and see if it finds it's a palindrome. Then in this other thread, I'll keep trying, assuming this isn't the middle of the word".

Another way to think of it is as infinite parallelism. So an equivalent model would be that, instead of choosing a new path, it simultaneously tries both paths, branching off new "processes," succeeding if any are in a final state after reading the whole word. Again, this can't be built using real hardware, but can be modelled with non-determinism.

The interesting thing about nondeterminism is that for finite-automata and Turing machines, it doesn't increase their computational power at all, just their efficiency.

# Answer
> 5 votes
The main difference (in my opinion) between a deterministic automaton and a non-deterministic automaton is that for a deterministic automaton a given input word has only one path through the machine. In a non-deterministic automaton a given input word may have multiple paths through the machine (because there may be choice at some points).

In light of this, the condition for acceptance of an input word also needs changing to accommodate the fact that a word may induce several paths through the machine. The usual definition of acceptance for a non-deterministic automaton is as follows: For a word to be accepted by the automaton there must be at least one accepting path induced by that word.

This then leads to the idea of an automaton "guessing," if a word is accepted by a non-deterministic automaton then we tend to think of the automaton as automatically making the right choices so that (one of) the accepting path(s) is followed when that word is presented as input.

What this means for palindromes is that the pda will essentially have two modes: a pushing mode where it pushes the current letters on the stack and a popping mode where it pops those letters off and matches them against the input. This machine will have an empty transition from the pushing state to the popping state which it will be able to follow at any point in the word. However the machine will only empty its stack and move to an accept state if it has read a palindrome and followed the empty transition at the middle of the palindrome. Since we only require the existence of an accepting path we can say that the automaton "guesses" where the middle of the word is.

# Answer
> 5 votes
The idea of nondeterminism is quite simple: the automaton might have several next steps in certain situations. The automaton accepts if there is *some* (there might be several!) sequence of steps leading from the initial configuration to an accepting one, it rejects only if there is *no* such sequence.

This means it "decides" which step to take next in those ambiguous situations. One way to talk about this is to say it *magically* selects the "right" next step always (or one, if there are several "right" steps). Another way to see it is that in such situations the automaton's computation splits into several copies, each one pursuing one path.

In practice, this can be implemented by backtracking, placing some form of tag on places where decision was taken, and go back and try the next alternative if the current path doesn't work out. This is usually handled by recursion. Or supplementing the information the automaton has "legally" with extra information (that is what you do when you show how a nondeterministic automaton works on the blackboard, looking ahead and figuring out which of the steps leads to success).

# Answer
> 2 votes
# "Guessing" is directly related to our existential interpretation of non-determinism

**In a nutshell:** *This idea that a non-deterministic automaton can guess (or be helped by an oracle) is directly related to our existential interpretation of non-determinism. Another interpretation is possible (maybe others) where "guessing" would not make sense.*

Non determinism is strange. We do have one way of interpreting it in automata theory, but it is not a priori obvious how we should do that.

It may seem surprising, but non-determinism is a very common situation. When one has to prove a theorem, given the axioms of some mathematical theory, the process is naturally a non deterministic one. That is why we often do not know what to do to solve a problem, for example to find the solutions of a third degree equation, or prove some theorem.

There are many ways to combine what is already known with inference rules to get new results. And the situation is usually the same if we try to reconstruct a proof backward from the result.

When attempting to solve such a problem, we try to "*guess*" a path in some transition system.

Actually, we do not guess, but build in our mind some structure that organizes and/or simplifies the maze of possibility so that we can see our path through it. In some cases, the question follows an identified pattern for which we have a standard way to (sometimes? usually? always?) find a solution, and we call that an algorithm.

One (usually expensive) technique we can use is simply to fully explore the maze: to follow all paths, doing it breadth first to avoid being caught in an infinite subgraph. This is pretty much what is being done by dovetailing all possible computations of a non-deterministic automaton. This derived dovetailed computation is itself a deterministic one.

**This dovetailed computation $DC$ mimics all possible computations of the original automaton $A$, but does not tell us how it should be interpreted.** It can just tell us whether A might sometime halt, with acceptance or rejection, and possibly that it will always halt. But it cannot, any more than $A$ itself, tell us that $A$ never halts, or never halt with acceptance.

Actually, **there could be different ways of interpreting a non-deterministic computation**. Afaik they are all consistent, but not with each other.

In the case of a language recognizer $R$, such as a NPDA, that can either not halt, or halt with acceptance or rejection, **the recognizer is said to accept an input $w$ iff there is one computation that halts and accept**. This is consistent with our own view of the non-deterministic proof process that is considered successful iff it can identify one proof tree for the theorem to be proved.

The idea of guessing for the recognizer is just an image taken from our own way of "guessing" how to find that proof tree. But the big difference is that our brains are not PDAs. They are much more complex devices with the ability to explore and map approximately transition structures so that we can find our way through them, which we sometimes perceive as guessing.

This interpretation of non-deterministic computation is what I would call **existential acceptance**, in reference to the fact that it requires only the existence of a single accepting computation. It corresponds to **existential halting** that I introduced in another answer.

However, one could also interpret non-determinism in a universal way as: **a recognizer is said to (universally) accept an input "w" iff all possible computations halt and accept the input.** This universal acceptance corresponds to the concept of universal halting introduced in the same answer.

Universal acceptance, and universal halting seem to lead to a self-consistent understanding of non-determinism. Hence one could do theoretical work with that definition. But it is not consistent with our usual practice in many non-deterministic situations such a theorem proving, or in everyday life situation. When confronted with a problem, we only want one way of solving it, and then do not care whether other ways are successful or not (well this is a bit over simplified).

If we have to recognize a palindrome, we can guess by measuring the length and looking for the middle. The PDA cannot. But, as we are only interested in existence of one solution, we can always pretend that it can ... if that will help it. Or we can consider that it has oracles provided by more intelligent machines (us?) to help it. Or you may even call it magic, and think it is (after all, the existential quantifier is a kind of magic wand). If it can help, it will. If there is no accepting computation, no help whatsoever will be any use.

Note that this idea of guessing would be meaningless in the universal acceptance interpretation.

---
Tags: automata, pushdown-automata, nondeterminism
---


title: How to prove $0\neq1$ using the J rule?

text:
# Question
Title: How to prove $0\neq1$ using the J rule?
Suppose I have a simple dependent type theory with bottom, unit, sums, dependent pairs, dependent functions, natural numbers and homogeneous identity with J-elimination.

Is there a way to prove $(0 = 1) \rightarrow \bot$? Or do I need K for that?

# Answer
First define a type family $P : \mathtt{Nat} \to \mathtt{Type}$ such that $P\\,0 \equiv \top$ and $P\\,1 \equiv \bot.$ For instance, we could define it by induction as \begin{align} P\\, 0 &\equiv \bot \\ P\\, (\mathtt{succ}(n)) &\equiv \top. \end{align} Let $\mathtt{tt}$ be the inhabitant of $\top$.

Suppose $e : 0 = 1$. Then, using $J$ we can formulate the transport map $\mathtt{transport}^P\_e : P\\,0 \to P\\,1$, and use that to transport $\mathtt{tt} : P \\, 0$ to $$\mathtt{transport}^P\_e(\mathtt{tt}) : P \\, 1.$$ We are done because $P\\,1 \equiv \bot$.
> 7 votes

---
Tags: proof-techniques, type-theory, dependent-types
---


# Question
Title: Is there a research name for "systems that steadily grow in complexity as they are computed"?
I have an intuitive concept of systems that **grows in complexity steadily as it computes**. I can think in some examples:

1. Nature. Given the physical laws, some initial conditions (say, the Earth planet at the beginning of life) and enough time, the system eventually evolves in complexity, all the way from dinosaurs fighting over territory to humans building castles.
2. Cellular automatas. Given a set of automata rules, some initial conditions (a grid with specific cells set) and enough time, some automatas eventually evolve complex structures.
3. AI applications such as genetic programming (to some extent). The issue is that most of those evolve towards a specific goal and often reach a tipping point and stop.

The kind of system I'm talking about is supposed to grow in complexity indefinitely. That is, one can expect that, given enough time, such system will eventually develop complex structures such as "lifeforms" that defend their own existence. It is also not goal oriented, it is supposed to grow in complexity because their own internal structures are more stable when they are more complex. We know nature/physical laws satisfy that criteria, but I'm not sure about cellular automatas and genetic programming. That is a very vague concept and hard to define (there is no accepted definition of complexity, after all). Yet, is there any name/formalization for this kind of system? Do we know any examples of systems/specific automatas that, as far as our observation goes, never reach a "tipping point" where they stop becoming more complex?

# Answer
> 5 votes
Hypothesis could be :

1. The **time is discrete**, let $s\_i$ be the state of your system at $t=i$.
2. Your system is deterministic and its transition function **$f$ is computable**.
3. Its complexity $c : \mathbb{N} \to \mathbb{N}$ is the Kolmogorov complexity, $c(i)$ is the **length of the shortest C++ program** which prints $s\_i$.

Then you have a bound : $$c(i) \leq O^+(1) + c\_0 + |f| + |i| = O^+(1) + |i| $$

($O^+(1)$ is a notation for a positive constant, |x| is the Kolmogorov complexity of x)

And more generally for any computable function $g$ : $$c(g(i)) \leq O^+(1) + c\_0 + |f| +|g| + |i| = O^+(1) + |i| $$

The system complexity grows more slowly that any computable function !

Conclusion :

* You should look at systems which are not deterministic or whose transition function is not computable. Or use an other definition for complexity (like this one : Chaos Theory).
* With Kolmogorov complexity, chaotic states are more complex than states with lifeforms defending themselves, but may be one can define a physical macroscopic Kolmogorov Complexity where the unbreakable basic components for describe the world are quite big and their internal features are negligible. Then it becomes more complex to describe tangle of life and vacuum than homogeneous chaos.

# Answer
> 1 votes
there is some scientific study of systems that roughly fit your criteria. you might examine the following to determine which are fitting or not based on their properties. there is a wide range of examples with different phenomena in each category.

---
Tags: terminology, reference-request, evolutionary-computing
---


title: Definition and properties of support

text:
# Question
Title: Definition and properties of support
From Xiong, Hui, Shashi Shekhar, Pang-Ning Tan, and Vipin Kumar. “TAPER: A Two-Step Approach for All-Strong-Pairs Correlation Query in Large Databases.” Knowledge and Data Engineering, IEEE Transactions on 18, no. 4 (2006): 493–508. :

> Support measures the fraction of transactions that contain a particular subset of items. The notions of support and correlation may not necessarily agree with each other. This is because item pairs with high support may be poorly correlated while those that are highly correlated may have very low support. For instance, suppose we have an item pair {A, B}, where supp(A) = supp(B) = 0.8 and supp(A, B) = 0.64. Both items are uncorrelated because supp(A, B) = supp(A)supp(B). In contrast, an item pair {A, B} with supp(A) = supp(B) = supp(A, B) = 0.001 is perfectly correlated despite its low support.

I don't quite follow the example about support. Could anyone give a proof of $supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$ ? I don't even quite understand what $supp(A, B)$ means. Is there a book or paper on support vs correlation?

# Answer
> 3 votes
First, the definition is clear: support is exactly "the fraction of transactions that contain a particular subset of items." This is a data-mining term, not a statistics term.

$supp(A)$ is the fraction of transactions that contain item $A$. $supp(B)$ is the fraction of transactions that contain item $B$. $supp(A,B)$ is the fraction of transactions that contain the subset $\\{A,B\\}$.

Now, your question really seems to be more about how the authors expound on this, which does seem to be a little unclear. As a statistic, support can basically mean, "What is the probability that this subset of items is contained in a random transaction?" That is, you can consider that $supp(A)=\mathbf{P}(A)$.

Then you can see that $$supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$$ comes from the definition of statistical independence, $$\mathbf{P}(A\cap B) = \mathbf{P}(A)\mathbf{P}(B) \iff A \perp B.$$

---
Tags: data-mining, statistics
---


# Question
Title: Approximate Bayesian Computation VS Monte Carlo Simulation
I am a little confused about the differences between Approximation Bayesian Computation (ABC) and Monte Carlo Methods (MCM). Citing from wikipedia:

> **Approximate Bayesian computation** (ABC) constitutes a class of computational methods rooted in Bayesian statistics. In all model-based statistical inference, the likelihood function is of central importance, since it expresses the probability of the observed data under a particular statistical model, and thus quantifies the support data lend to particular values of parameters and to choices among different models. For simple models, an analytical formula for the likelihood function can typically be derived. However, for more complex models, an analytical formula might be elusive or the likelihood function might be computationally very costly to evaluate.
>
> **Monte Carlo methods** (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. \[..\] Monte Carlo methods are mainly used in three distinct problem classes: optimization, numerical integration, and generating draws from a probability distribution.

In both cases, we run many simulation starting with constant or varying parameters and get the posterior probability (although I am not sure we call that a posterior probability in MCM). I would tend to think that ABC is MCM, where we use the posterior probability to define a confidence interval. Or maybe, by definition MCM are deterministic and therefore the resulting distribution is a function of the parameter values only and therefore it does not make any sense to make any statistical inference (such as calculating an confidence interval). I'd tend to think that ABC is a type of MCM, where we make statistical inference (or whenever the simulation takes a random seed in input). Is that right?

* Is ABC a specific case of MCM?
* Is ABC just like an MCM except that a random seed is taken in input?

# Answer
Yes, ABC is a specific application of Monte Carlo method. That application is approximating likelihood functions.

Anything that happens in a computer is actually deterministic. However, ABC, like any other MCM, must have a good pseudo-random generator. There is no difference in the amount of randomness required by the methods.

Examples of Monte Carlo methods which are not ABCs include genetic algorithms and Monte Carlo integration.
> 6 votes

---
Tags: statistics, monte-carlo, bayesian-statistics
---


title: Pruned FFT runtime

text:
# Question
Title: Pruned FFT runtime
Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). They can also exploit sparsity in the input vector to further accelerate computation.

On http://www.fftw.org/pruned.html, the runtime is reported to be $\in O(n\log k)$, where $n$ is the length of the input vector and $k$ is the number of desired indices to compute in the result (of course, the standard FFT could always be used to compute the full result in $O(n\log n)$ steps); however, I cannot figure out where the benefit of sparsity in the input vector is measured in this bound.

Does anyone know the runtime / how to get the runtime of a pruned FFT on $n$ inputs, $m$ of which are nonzero, and where $k$ outputs are computed? I have an algorithm that depends on a step very similar to a pruned FFT calculation, and I have a lot of sparsity.

Thanks a lot for any advice you can lend.

# Answer
> 3 votes
If you want to do a normal FFT, and just try to exploit the fact that many of the input coefficient are zero because of padding, or that you are only interested in part of the output coefficients because you intentionally oversampled the input, then this isn't really worth the trouble, especially in 1D.

If you are thinking about 2D or 3D, want to avoid the coupling between pitch and resolution (i.e. that the pitch has to be a multiple of the resolution), and implement the data reduction for pruned FFT explained in the linked FFTW documentation, then an implementation based on Bluestein FFT/Chirp Z-transform can provide real practical benefits. It is still an exact transform without any resolution based error. This is the variant I most often ended up with in the past, but sometimes variants with resolution dependent error were more appropriate, see below for more details.

The Bluestein FFT can be implemented once (with appropriate case districtions for optimal speed) using FFTW (or your prefered FFT library) as a backend, and then forgotten and used as a black box. Don't know whether there exists a good free implementation, but it wouldn't be difficult to provide one.

The runtime of such an implementation is best measured in term of the needed intermediate memory. A single 1D Bluestein FFT needs $O((n+m)\log(n+m))$ time and $O((n+m))$ space. For a 2D implementation, the intermediate storage after the FFT has been performed in one direction will be $n\_x m\_y$ or $m\_x n\_y$, depending on whether the x- or y-direction was chosen. The corresponding runtime will be $O(n\_x(n\_y+m\_y)\log(n\_y+m\_y)+(n\_x+m\_x)\log(n\_x+m\_x)m\_y)$ or $O((n\_x+m\_x)\log(n\_x+m\_x)n\_y+m\_x(n\_y+m\_y)\log(n\_y+m\_y))$.

---

The story doesn't end here. In the past, I sometimes also had to use a non-uniform FFT. This transform has a well controllable resolution based error, but it can transform much more than just sums of delta distributions, it can also compute transforms of polygonal domains and more.

But the story doesn't end here either. I hope I will never have to use those, but in a recent breakthrough development, researchers at MIT came up with ingenious randomized algorithms, and presented several new results for sparse Fourier transform:

* An $O(k \log n)$-time algorithm for the exactly k-sparse case.
* An $O(k \log n \log(n/k))$-time algorithm for the general case.
* An $\Omega(k \log(n/k) /\log\log n)$ lower bound for sample complexity.

---
Tags: algorithm-analysis, runtime-analysis, fourier-transform
---


# Question
Title: Lower bound on distinct element heapsort
I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS:

**Exercise 6.4-5**
Show that when all elements are distinct, the best-case running time of heapsort is $\Omega(n\text{log}(n))$.

I've been thinking over this for about a day or so, and so far I've tried working with finding the time it takes run heapsort through just the leaves of a heap (I've been focusing on full heaps with $n = 2^h - 1$ elements), but couldn't draw any conclusions except for the minimum and 2nd-minimum elements, so that hasn't really gotten anywhere.

Does anyone have any hints as to how to proceed? Please **don't** post solutions to the problem, just hints/potential directions to proceed.

Any help is much appreciated!

# Answer
> 3 votes
keep in mind, that a heap has a height of $O(\log n)$ and its root contains the minimal element. how long does it take to restore the heap if you remove the root element (the minimum!) and how often you have to do this in order to achieve a sorted list?

after that, think of the time you need for building a heap out of $n$ elements in abitrary order

---
Tags: algorithm-analysis, sorting, heaps, heap-sort
---


# Question
Title: "Compressing" rationals given error bounds
I'm working on implementing some exact real arithmetic operations for fun. I've got the rough outline of how I want to do things as well and have figured out how to write most of the important algorithms (though I have not properly implemented them just yet).

Going against the "pre-mature optimization is bad, m'kay" philosophy I am wondering about a few things. So reducing fractions is one way to reduce the size of rationals, sure, but it isn't perfect. If you knew you only had to be within a certain range you could do better by changing the value. For instance say I need to add $1$ and $\frac{1}{8}$ to with in $\frac{1}{2}$. I don't need to full precision, I can just return 0 in fact. More beneficially say I had something like $\frac{2^{16}+1}{2^{32}}$, if I only need say something like $\frac{1}{2^{15}}$ precision, I can approximate this rational as $\frac{2^{16}}{2^{32}}$ and then reduce that to $\frac{1}{2^{16}}$.

This are some contrived cases but I think there is a generally useful optimization to be done here. Are there algorithms which, given an error bound, can find the smallest (in bits) rational number within the specified bounds of another given rational number?

Most of my algorithms tend to produce rationals with power of two denominators so I am particularly interested in that case.

# Answer
> 3 votes
A brute force solution is to trace the line ay=bx in integer coordinates from the origin to (a,b). Any pair with a smaller number of bits will be along that line segment. This method allows finding either the minimum distance or the smallest (x,y) within the error bounds. It requires o(a+b) steps, and there's plenty of redundancy possible, since eg both (x,y) and (kx,ky) might be found for k \>1.

Tracing the line refers to iteratively moving either up or right according to which move minimizes distance to the line; it's a common method for graphics.

# Answer
> 4 votes
Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number $x$. In particular, given a real number $x$, you can generate a sequence of truncated continued fractions $a\_i/b\_i$, where each rational number $a\_i/b\_i$ is a better approximation to $x$ than any other fraction whose denominator is $\le b\_i$. So, a reasonably good algorithm for your problem is to compute the sequence of truncated continued fractions, and keep the last one whose denominator is smaller than your bound. This doesn't find the best rational approximation for a given number of bits, but it does give you a best rational approximation for a given upper bound on the size of the denominator.

To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits). Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator. KWillets' method seems better if $a,b$ are not too large. However, if they are very large, then a continued fractions-based method might become more attractive.

---
Tags: numerical-analysis, number-formats
---


# Question
Title: Assigning one variable to another in 3 address code?
3 address code is a very common topic in many of the CS theories. I encountered it while studying Compiler Design. According to the Wikipedia article, it says -

> Each TAC instruction has at most three operands and is typically a combination of assignment and a binary operator.

Now my query, does that mean I can assign a variable to another variable(operand) even if it doesn't changes any thing, as this action doesn't violates the exact meaning of TAC(at most three operands). Example for clarity:

```
a = b*c - d*4

```

**TAC**

```
t1 = b
t2 = c
t3 = d
t4 = t1*t2
t5 = t3*4
t6 = t4 - t5
a = t6

```

In all the above lines, I haven't violated the TAC rule of at most 3 operands, but in the first 3 lines, I have assigned three variables to three different operands even if it isn't required.

Now technically will that be considered wrong? I know it's inefficient but is it wrong in technical terms? What I think is it's not wrong because the code optimization stage which comes after this will do the filtration if required. Still I want to know the opinions.

# Answer
Three address code is an intermediate language used internally by (some) compilers. What is "right" depends on the specific rules that that compiler expects/enforces. Efficiency, as you state, is normally not an issue, as the intermediate language is designed for easy massaging and ultimately traslating into efficient target code.
> 2 votes

---
Tags: compilers, code-generation
---