# Question
Title: Language comprising of Turing machine encodings
Let $A$ be the language $\\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\\}$

According to my understanding, if a Turing machine is able to decide if another Turing machine will accept only one string, then the halting problem could also be solved. Therefore, $A$ is non-recursively enumerable in my understanding. Is it correct ?

# Answer
As the question suggests, it is not too hard to show a reduction from the halting problem (HP) to the language $A$ stated in the question, $HP \le A$. This means that $A$ is undecidable, $A\notin R$ (also, it is not in co$RE$). But, is it in $RE$ or not?

Lets show that $\overline{HP} \le A$ and conclude that $A\notin RE$.

The reduction goes like that: on input $(\langle M\rangle,x)$ we generate the TM $M\_x$ that, on input $w$:

1. If $w$=$\varepsilon$, ACCEPT.
2. Run $M$ on $x$. If M halts, ACCEPT (otherwise, we're in a loop anyways)

The reduction is valid: if $(\langle M\rangle,x) \in \overline{HP}$, then $M$ does not halt on $x$. This means that $M\_x$ accepts *only* the empty string (and loops on any other input). Thus $\langle M\_x\rangle \in A$.
On the other hand, if $(\langle M\rangle,x) \notin \overline{HP}$, then $M$ halts on $x$, and $M\_x$ accepts *any* input, thus $\langle M\_x\rangle \notin A$.

It is easy to verify that the reduction is computable and complete.
> 6 votes

# Answer
I thought up a reduction on the train home, but Ran G. has beaten me to the punch ;). Nonetheless, as an exercise:

Let $E\_{TM} = \\{\langle M\rangle\mid L(M) = \emptyset\\}$ (as usual). This language in not recursively enumerable (in fact you have asked another question where this is demonstrated.

We can show that if $A$ is recursively enumerable, then $E\_{TM}$ is also. Let $R$ be a Turing Machine that recognises $A$ (if $A$ is recursively enumerable, then it is Turing recognisable and such a machine exists). Using it we can construct a machine $T$ that recognises $E\_{TM}$ as follows:

On input $\langle M\rangle$:

1. Pick two strings $w$ and $x$ where $w\neq x$.
2. Construct two machines $M\_{w}$ and $M\_{x}$ where each have a new branch from the start state that accepts $w$ and $x$ respectively.
3. Step for step run $R$ on inputs $\langle M\_{w} \rangle$ and $\langle M\_{x}\rangle$
    * If R accepts on both, halt and accept.

Now we argue that $T$ recognises $E\_{TM}$. If $L(M) = \emptyset$, then $M\_{w}$ and $M\_{x}$ accept only $w$ and $x$ respectively, thus $R$ will accept on both. If $R$ accepts on both $\langle M\_{w}\rangle$ and $\langle M\_{x}\rangle$, then $M$ cannot have accepted on any string:

* If $w \in L(M)$, then $\langle M\_{x}\rangle \notin A$, and hence $R$ would not accept.
* If $x \in L(M)$, then $\langle M\_{w}\rangle \notin A$, and hence $R$ would not accept.
* If $y \in L(M)$ where $y \neq w,x$, then $R$ would accept neither $\langle M\_{w}\rangle$ nor$\langle M\_{x}\rangle$.

Therefore $R$ cannot exist as it contradicts the non-recursive enumerability of $E\_{TM}$, and hence $A$ is also not recursively enumerable.
> 4 votes

---
Tags: computability, reductions, undecidability
---


# Question
Title: Recusively Enumerable or Recursive dependent on whether P=NP
If a language is defined such that
$L = (0+1)^{\ast}$ if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$ otherwise

Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the empty langauge. Therefore $\mathsf{P} = \mathsf{NP}$ , $L$ is recursive (being regular), but is $L$ still recursive if $\mathsf{P} \neq \mathsf{NP}$?

# Answer
The language $L = \emptyset$ is indeed a recursive set.
> 7 votes

---
Tags: computability, regular-languages, p-vs-np
---


title: What is tail recursion?

text:
# Question
Title: What is tail recursion?
I know the general concept of recursion. I came across the concept of **tail recursion** while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm. It is not clear to me what tail recursion really means.

Can someone explain the concept with a proper example?

*Some answers provided by the SO community here.*

# Answer
> 71 votes
Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function

```
int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

```

is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

```
int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

```

since it does some computation after the recursive call has returned.

Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.

# Answer
> 20 votes
Simply said, tail recursion is a recursion where the compiler could replace the recursive call with a "goto" command, so the compiled version will not have to increase the stack depth.

Sometimes designing a tail-recursive function requires you need to create a helper function with additional parameters.

For example, this is *not* a tail-recursive function:

```
int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

```

But this is a tail-recursive function:

```
int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

```

because the compiler could rewrite the recursive function to a non-recursive one, using something like this (a pseudocode):

```
int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

```

The rule for the compiler is very simple: When you find "`return thisfunction(newparameters);`", replace it with "`parameters = newparameters; goto start;`". But this can be done only if the value returned by the recursive call is returned directly.

If *all* recursive calls in a function can be replaced like this, then it is a tail-recursive function.

# Answer
> 18 votes
My answer is based on the explanation given in the book Structure and Interpretation of Computer Programs. I highly recommend this book to computer scientists.

## Approach A: Linear Recursive Process

```
(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

```

The shape of the process for **Approach A** looks like this:

```
(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

```

## Approach B: Linear Iterative Process

```
(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

```

Shape of the process for **Approach B** looks like this:

```
(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

```

The Linear Iterative Process (Approach B) runs in constant space even though the process is a recursive procedure. It should also be noted that in this approach a set variables define the state of the process at any point viz. `{product, counter, max-count}`. This is also a technique by which tail recursion allows compiler optimization.

In Approach A there is more hidden information which the interpreter maintains which is basically the chain of deferred operations.

# Answer
> 6 votes
Tail-recursion is a form of recursion in which the recursive calls are the last instructions in the function (that's where the tail part comes from). Moreover, the recursive call must not be composed with references to memory cells storing previous values (references other than the parameters of the function). In this way, we don't care about previous values and one stack frame suffices for all of the recursive calls; tail-recursion is one way of optimizing recursive algorithms. The other advantage/optimization is that there is an easy way to transform a tail-recursive algorithm to an equivalent one that uses iteration instead of recursion. So yes, the algorithm for quicksort is indeed tail-recursive.

```
QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

```

Here is the iterative version:

```
QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1

```

---
Tags: algorithms, reference-request, recursion
---


# Question
Title: Algorithm for determining minimal set of covering prefixes
I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set.

For instance, if my set is:

```
abracadabra
abracado
abramu
banana
bananasplit
bananaicecream
xylophone
zebra
zeitgeist
zello

```

I would want the output to be:

```
banana (len 6, matches 3)
abra (len 4, matches 3)
xylophone (len 9, matches 1)
ze (len 2, matches 3)

```

Now, this question isn't yet properly specified. That's because I'm ranking my results on two dimensions: maximum matches, and maximum length. My goal is to find prefixes that cover as much as of the set as possible, which are as long as possible and thus less likely to occur in strings that *aren't* in the set (all other things being equal, of course).

Ideally, I'd like to find a set of very long strings, ranked by how much of the set they cover.

That's my goal. Now I'll present my work, and where I need help.

**FIRST** Let's specify the problem better. We want a set of prefixes. For each prefix, we compute its length, and the number of matches it has in the set, and order the prefixes by their product. I'm then free to pick the top X prefixes.

I think that's a good specification.

**NOW** Comes an efficient implementation. Brute force is to check every possible prefix against every string, which is complexity n * n * m (n being number of strings, m being average length of strings).

An efficient algorithm?
Something like this:

1. Build a prefix tree of the set
2. Each leaf has value 1
3. Work up the tree, with each parent equal to sum of its children , plus 1 if it has an entry
4. Now we know each prefix and how many matches it has - I believe complexity is n log n
5. Walk through the tree, counting length of each string (complexity n * m)
6. And collect all the entries, sort them by length * value (complexity n log n)

That algorithm is roughly n log n, which is efficient enough. Will it work? How should it be improved? What's a simple way to implement it?

Finally: Since all the data is in a Postgres relational database, I believe it would be simplest to do the algorithm using relational algebra with aggregate functions. Comments on this?

# Answer
Your algorithm will work. The information you will be looking for can be found in the prefix tree (trie) will hold the information you are looking for.

Despite similarity in names, the set cover and this problem are not similar. The first is NP-Hard. This one is not.

However (in relation to Point 3 of your algorithm), a tree node that is not a leaf may be the end of a word $w$ contained in other words (e.g. "be" contained in "bee" "behavior" etc .. ). You should take into consideration when counting.

Point 4: Now we know each prefix and how many matches it has - I believe complexity is $n \log n$ .. why ? I dont think so. It is $O(n m)$.

Point 6: I dont know though why you want to sort. You can find the max (which is $O(n)$).

If you are going to present the tree in a relational database, then make sure you present it in a good way. For instance, try to make the whole tree in a single page, or close nodes in the tree in the same page. This is to minimize the I/O cost. How to do that ? I honestly don't know. For me, I would just put it the prefix tree in a single binary file. Or a seriazable data structure.
> 2 votes

---
Tags: algorithms, trees, data-compression, sets, coding-theory
---


title: Design the transition function

text:
# Question
Title: Design the transition function
I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\\{0^{n}1^{n+1}: n\ge1$}.

$$Q=\\{q\_0,q\_1,q\_2,q\_3,q\_4\\} ,Σ = \\{0,1\\}, Γ =\\{0,1,X,Y,B\\}, F=\\{q\_4\\}$$

X- processed 0
Y- processed 1
B- blank
P-move right
L-move left
So far I've succeeded to create a table for languages $\\{0^n1^n\\}$(without the red entry) and $\\{0^n1^k:k\ge n\\}$.

What should it look for case in which there is minimal superiority of "1's"?

@EDIT

Meanwhile I've finally hit on an idea for **L(M)**

Is it correct?

# Answer
> 3 votes
If you have managed to solve $0^n1^n$ then $q\_4$ should simply proceed to the rightmost bit you haven't processed yet and verify that it's a 1 and that there is nothing following it.

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


title: Broken stick problem

text:
# Question
Title: Broken stick problem
We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.

The amount of glue need to connect two parts equal the maximum from their sizes. We can only glue two parts at one time.Can we solve this problem in the time complexity smaller than $O(n^3)$? I know only the answer, using dynamic table in this complexity

# Answer
> 1 votes
You didn't define what 'connecting all parts' is. Do you need to arrange them in an array? Or just connect them?

The way I understood the problem, you can use Prim's algorithm to find the minimum spanning tree, and that's the result. O(n^2)

In case you want them arranged in an array, I think the sorted array is always optimal.

We will call a part "counted" if it is the bigger part in some connection. A part can be counted 0, 1, or 2 times. Let there be 3 elements in the array that are not sorted (A \> B \> C). Let L be the part placed left from this sequence, and R the part placer right. The ordering is L(permutation(A,B,C))R. You can observe all cases, and see that the permutation ABC is the best because it takes the parts max(L,A), A, B, max(C,R). This proves that all 3 element subsequences should be sorted, which means the sorted array is optimal.

# Answer
> 4 votes
Homework?

See the problem "Cutting Wood", which involves cutting rather than glueing, but is otherwise equivalent. Provided the orders matters (as noted by Marzio).

> Your favorite sawmill charges by length to cut each board of lumber. For example, to make one cut anywhere on an 8 ft. board of lumber costs \\$8. The cost of cutting a single board of wood into smaller boards will depend on the order of the cuts. As input, you are given a board of length $n$ marked with $k$ locations to cut

solution to exercise (pdf) Found in several places on the web, don't know the original.

---
Tags: complexity-theory, algorithms, dynamic-programming
---


# Question
Title: Bit complexity of O(1) time range query in a $k$-ary array
Consider the following problem:

Let $k$ be a constant. We are given a $k$-ary array $A\_{d\_1\times\ldots\times d\_k}$ of $0$ and $1$'s. Let $N = \prod\_{i=1}^k d\_i$.

We want to create a data structure by preprocessing $A$ to perform the following type of query operations:

1. Given the coordinates of a $k$-ary box $D$, is there a $1$ in the box?
2. Given the coordinates of a $k$-ary box $D$, return the position of a $1$ in the box (if there is one).

The operations must be performed in constant time $O(1)$. The time complexity is measured on a RAM machine. The preprocessing time and space for the data structure are not important for us.

The question is how much space (in bit complexity) do we need to store a datastructure allowing the above operations?

The trivial lower-bound is $N$ bits since the array can be reconstructed for these queries (so the data structure should have at least the same amount of information in it).

The trivial upper-bound is to store the answer to all of the queries. That would need $\prod\_{i=1}^k {d\_i \choose 2} = \Theta(N^2)$ bits. However we suspect that this can be done much more efficiently.

For example, consider the special case where $k=1$. In this case we can use a succinct RMQ data structure to solve the first problem, and the data structure takes $2N+o(N)$ bits to store.

> What is an efficient data-structure for this task?
> How low can the space complexity (the number of bits) go to support these operations (or just the first operation)?

**Update (1/15):** In the special case $k=1$, using $N +o(N)$ bits is sufficient (actually better, $\log {N\choose t}+O(t)$, where $t$ is the number of $1$'s in $A$) by reducing the problem to a predecessor problem and using the reduction from predecessor problem to fully indexable dictionary (FID). See "More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries" by Grossi, Orlandi, Raman and Rao (2009).

**Update (6/27):** Again by reduce the problem to RMQ. We use a $k$-dimensional RMQ by Yuan and Atallah to get a $O(n\log n)$ upper bound on the amount of space required when $k$ is fixed.

# Answer
> 1 votes
You can save a lot more on memory if you just allow logarithmic time complexity. You can implement a kD segment tree that will need N * 2^k bits memory, and runs in logarithmic time complexity for both subtasks, and linear time complexity for building the tree.

If you strictly want O(1), precompute everything.

---
Tags: reference-request, data-structures, space-complexity
---


# Question
Title: Algorithms computing if a number is a multiple of 3
When doing mental calculus one can do:

* Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3.

Do you know of any algorithm working similarily but operating on binary numbers digits (bits)?

* At first, I was thinking of using the ready made functions of my language converting integer to ascii to perform the convertion from base 2 to base 10, then apply the mental calculus trick. But of course then I could also encode the base convertion 2 to 10 myself. I have not done it yet, but I'll give it a try.
* Then I have thought of euclidian division in base 2...

However I wonder if there are other means, algorithms.

# Answer
Consider the following two observations (left as an exercise to the reader):

1. The even powers of two are 1 modulo 3.
2. The odd powers of two are -1 modulo 3.

We conclude that that a number (in binary) is divisible by three if and only if the sum of the bits in the even positions equals the sum of the bits in the odd positions modulo 3.
> 23 votes

# Answer
What about a finite state automaton for the job?

Of course the magic is just computation modulo 3. Adding symbol $a$ behind string $x$ means the "binary value" of the string goes from $val(x)$ for $x$ to $2\cdot val(x)+a$ for $xa$. Consequently from state $p$ and symbol $a$ we move to state $2p+a \bmod 3$, for $p\in \\{0,1,2\\}$ and $a\in \\{0,1\\}$. Note $x\in \\{0,1\\}^\*$ is a string, wheras $val(x)\in \Bbb{N}$ is its value as binary string.
> 38 votes

# Answer
In binary, numbers 1, 100, 10000 (=100×100), 1000000 (=100×100×100) etc. all give the same remainder after dividing by 11 (three). Therefore if we split a binary number to parts of *even length*, the sum of the parts gives the same remainder as the original number.

(When splitting the number, we add as many zeroes as necessary to the *beginning*. For example we would split 10111 to groups 01,01,11 or 0001,0111.)

Mathematically, just split the number into groups of *two* digits, then add the groups; and repeat this until your result becomes 00 or 11 = the original number was a multiple of three; or 01 or 10 = the original number was *not* a multiple of three.

For a computer program, using groups of eight or sixteens or thirty-two bits may be *faster* for your CPU. For example, if eight-bit addition is fastest, just make a sum of all bytes, and again, until the result fits into one byte. Then use one instruction to determine the remaininder after dividing by three.

(Note: We are assuming *unsigned* integers here. With a signed number, it needs a bit more of an attention. For example 129 is a multiple of 3, but -127 is not, although bits 10000001 mean for former as an unsigned byte and the latter as a signed byte.)
> 4 votes

# Answer
While not binary-specific, when in doubt, repeated subtraction is always a surefire way to compute division with remainder (and thus if a number is a multiple of 3).
> 0 votes

---
Tags: algorithms
---


# Question
Title: Potential function binary heap extract max O(1)
I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.

I know that the insert function should "pay" more in order to reduce the cost of the extraction, and this has to be in regards to the height of the heap (if $ \lfloor \log(n) \rfloor $ gives the height of the heap should the insert be $2\log(n)$ or $ \sum\_{k=1}^n 2\log(k) $)

# Answer
Try the following:

The weight $w\_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function

$$\Phi(H)=\sum\_{i\in H}2 w\_i.$$

Let us now analyze the heap operations. For **insert** you add a new element add depth $d$ at most $\log(n)$. This increases the potential by $2d$, and can be done in $O(1)$ time. Then you "bubble up" the new heap element to assure the heap-property. This takes $O(\log n)$ time and leaves $\Phi(H)$ unchanged. Thus the costs for insert are $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$.

Now consider the **extractMin**. You take out the root and replace it by the last element in the heap. This decreases the potential by $2\log(n)$, thus you can afford to repair the heap property, and therefore the amortized costs are now $O(1)$.

If you have a general question for the potential function you should pose this as a different question.
> 14 votes

---
Tags: data-structures, runtime-analysis, heaps, amortized-analysis
---


# Question
Title: Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?
I have a book that proves the halting problem with this simple statement:

$$ A\_\text{TM} \le\_m \text{HALTING} \le\_m \text{HALTING}^\varepsilon $$

It states that halting problem reduces to the language consisting of $\langle M, \omega \rangle$ for which a Turing machine $M$ accepts $\omega$ is undecidable.

What does this mean? What does the notation $\le\_m$ indicate?

# Answer
The symbol $\leq\_m$ means many-one reducible, contrast to reductions such as turing reducible (denoted by $\leq\_T$) and one-one reducible (denoted $\leq\_1$).

A many-one reduction from $L$ to $L′$ (given an alphabet $\Sigma$) is a (computable) function $f:\Sigma^\* \to \Sigma^\*$ such that for every $w \in \Sigma^\*$, we have that $w \in L$ if and only if $f(w) \in L′$. The "many-one" means that we allow $f(w) = f(w′)$ (it does not have to be injective). In your setting, it basically means that you can transform an input to $A\_{TM}$ to $HALTING$ such that $A\_{TM}$ accepts an input $w$ if and only if $HALTING$ accepts the transformed input $f(w)$.
> 3 votes

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


title: Showing bounds of a recurrence

text:
# Question
Title: Showing bounds of a recurrence
I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that:

The solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \lg n)$. Show that it's also $\Omega(n \lg n)$ and conclude that the solution is $\Theta(n \lg n)$.

For showing that it's $O(n \lg n)$, I've to show that $T(n) \leq cn \lg n$. This can be solved by choosing an $m \< n$, like $\lfloor n/2\rfloor$, and substituting.

But if we arrive at the conclusion that $T(n) \leq cn \lg n$ for any appropriate $c \> 0$ and $n \geq n\_0$, than how can we say that it is also $\Omega(n \lg n)$ which implies that $T(n) \geq cn \lg n$?

Some more clarification would be nice!

# Answer
> 3 votes
First, I would like to modify your statement slightly to remove any chance of confusion. When you say, "... $T(n) \le cn\log n$ for any appropriate $c \> 0$ and $n \ge n\_0$", it actually means $T(n) \le cn\log n$ for *some* appropriate $c \> 0$ for *all* $n \ge n\_0$.

Next, these constants for proving the lower bound can be (and generally are) different from these when proving the upper bound. I will demonstrate with your example:

**Upper bound:**
$T(n) = 2T(\frac{n}{2}) + n \le 2(c\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \le cn\log n - cn\log 2 + n = cn\log n - (c - 1)n$
$T(n) \le cn\log n$ for all $n$ for any $c \ge 1$
Therefore, $T(n) = O(n\log n)$

**Lower bound:**
I'll use a different constant $b$ for this, just to emphasize that the two constants are different.
$T(n) = 2T(\frac{n}{2}) + n \ge 2(b\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \ge bn\log n - bn\log 2 + n = bn\log n + (1 - b)n$
$T(n) \ge bn\log n$ for all $n$ for $0 \le b \le 1$
Therefore, $T(n) = \Omega(n\log n)$

So basically, you need to choose some constant such that the inequality holds for all sufficiently large $n$. These constants can (and generally are) different for different inequalities.

Note: I have assumed that $n$ is a perfect power of 2 in the above recursions to do away with the floor function. For asymptotic analysis, they do not really matter. These notes may help things become clearer.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: The difference between a sequence and a set
I am new to discrete mathematics and the theory of computation I am trying to learn and understand the terminology.

I am having a difficult time understanding the difference between a set and a sequence. I understand that unlike a set, in a sequence order and repetition does matter and sequences contain objects rather than elements or members. However, I don't see how sequences can be logically applied to the real world.

Can someone please give a clear and simple example of when a sequence would be used as opposed to a set and explain how is a sequence is different that a set?

I appreciate any clarification.

# Answer
Your question uses a number of words, such as "*logic*" that might require clarification. In order to answer I should start with some preliminary definitions.

Consider a universe of objects. The objects have different properties. We do not know yet if each object can be identified. We say that all objects that share a certain property form a *set* (this statement is related to the notion of *specification* in Set Theory).

For instance in order to have a set of all sand particles you do not need to be able to identify each particle of sand. You just need to be able to distinguish them from objects that are not sand particles.

So a set is either an empty set or a set of all objects in our universe that share some common property. Two sets $A$ and $B$ are considered equal if an element $x$ belongs to $A$ if and only if $x$ belongs to $B$. (this statement is known as *extensionality*). It follows that removal of duplicates does not change a set.

In order to define a sequence we need to introduce natural numbers into our universe. Now a *sequence* is a *mapping* from the set of natural numbers into a set of objects. That is each number is associated with a unique object. (You need to be able to identify individual objects in order to define a sequence).

A sequence can also be considered as a set where each element has a special form. For example a sequence `A, B, C, B, ...` can be represented as a set

```
   { {1,{A}}, {2,{B}}, {3,{C}}, {4,{B}}, ... }

```

### Example

Now here is an example where a sequence can be used as opposed to a set. Suppose our universe consists of colored grains of sand. Assume each grain is either green or red. Then we could have only four different sets in our universe:

```
  {}, {G}, {R}, {G, R}

```

and many higher order sets, such as

```
  {{G}}, {G,{R}}, ... etc.

```

However we could form many infinite sequences without using higher-order sets:

```
  R, G, G, R, G, R, R, G, ....

```

### Programming

In programming languages some basic data structures, such as arrays or lists are sequences, that is you can refer to an element by its sequence number. Using such structures to model sets requires additional processing: identifying duplicates and keeping them in a sorted state.

A natural data structure to model sets is a hash table. This model handles duplicates efficiently, however computing a hash table that represents a union of two hash tables may have complexity proportional to the size of the hash tables.

Hope this clarifies the difference between sequences and sets.
> 14 votes

# Answer
* Sequence - Order is important
* Set - Order is not important

Unlike set same element can appear multiple times in a sequence.

Wikipedia article gives more than enough information about this.
> 10 votes

---
Tags: computability, terminology, logic
---


# Question
Title: Proof by restriction: when is it valid to restrict to a special case?
I was reading a few notes on Proof by Restriction and I am confused:

A Valid Proof by Restriction is the following:

Directed Hamiltonian Cycle Problem is NP Complete because if we look only at *instances* of DHC where For $G=(V,E)\quad (u,v)\in E \leftrightarrow (v,u) \in E$ then it reduces to Hamiltonian Cycle which we know is NP complete.

A *wrong* proof is the following:

> **Subset Sum problem**
> INSTANCE: Integers $a\_1, a\_2,…,a\_n$ and integer B.
>
> QUESTION: Is there a sequence of 0’s and 1’s, $x\_1, x\_2,…,x\_n$ such that: $$\sum\_{i=1}^n a\_ix\_i \leq B$$

is a special case of

> **Real Subset Problem** INSTANCE: Integers $a\_1, a\_2,…,a\_n$ and integer B.
>
> QUESTION: Is there a sequence of real numbers $x\_1, x\_2,…,x\_n$ such that: $$\sum\_{i=1}^n a\_ix\_i \leq B$$

so it is NP Complete.

My notes say that the this proof is wrong since it restricts the question and not the instances but I don't seem to understand the difference.

Further, I can't really understand how Proof by Restriction works; for all I know I could be restricting an NP Complete problem to a trivial case which can be solved in Polynomial time.

# Answer
> 3 votes
Think about the set of all possible instances of DHC. A subset of these instances are those where, for every directed edge $(u, v)$, there is always a matching directed edge $(v, u)$. (In general, this doesn't have to be the case, but it CAN be the case, which is why this is a valid restriction.)

Now think about the set of all possible instances of SubsetSum. For each such instance, you're supposed to answer with a set of 0/1-valued $x\_i$. By your first definition, there are NO valid answers that include a real number in the $x\_i$. So, when you suddenly allow real-valued solutions in the second version of SubsetSum, you're **relaxing** the problem, not restricting it. (You're giving yourself more leeway by allowing more possible solutions.)

# Answer
> 1 votes
What you have in the case of DHC is really just a reduction: assuming you could solve DHC in polynomial time, you can solve HC in polynomial time, too, because it is a special case (use the same algorithm!). Therefore, HC $\in$ NPC implies DHC $\in$ NPC.

If you think of it in terms of the usual reduction HC $\leq\_p$ DHC, the polynomial transformation does *nothing*, so it's just a very simple reduction.

The subset sum thingy says "the special case is as hard as the general case", which is plain wrong. For example, HC is trivial on trees.

# Answer
> 0 votes
In the case of Directed Hamiltonian Cycle, when you have a solution to the restricted case (the graph with arcs going both ways), the solution is a valid solution for the original problem. In the case of subset sum, a solution to the Real Subset Sum is not a solution for the Subset Sum.

In the first case, you are showing Hamiltonian Cycle $\leq\_P$ Directed Hamiltonian Cycle. In the other case, you want to say Subset Sum $\leq\_P$ Real Subset Sum, and thus showing that since the latter is in $P$, the former is as well.

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


# Question
Title: In context of data mining, what does it mean for an association rule measure to be maximal?
In context of data mining, what does it mean for an association rule measure to be maximal?

I cannot understand the term maximal in this context.

I know of maximal independent sets in algorithms but cannot make out this term.

# Answer
> 1 votes
I believe that in the context of that paper (PS), you can read "maximal" as "maximized". That is to say, the conviction function $P(A)P(\neg B)/P(A, \neg B)$ attains its greatest value when $A \implies B$.

---
Tags: terminology, data-mining
---


# Question
Title: Introductory books on nature sciences behind bioinformatics
My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background in biology and chemistry to feel prepared for that cycle of lections (I was rather weak at these subjects at school).

Could you recommend any books that would provide a good introduction to the questions of natural sciences that bioinformatics focuses on?

# Answer
> 7 votes
As a previous response stated, it is not an absolute requirement that you study biology in order to do bioinformatics. However, if you wish to have a background understanding of the foundational concepts such as genes, RNA, DNA, etc. then a good introductory biology book should provide everything that you need.

Molecular biology is not the kind of topic that one can simply dive into the middle of, though. Therefore, in order to understand it, you need to do some introductory reading. The best book is one that has enough detail without assuming that you wish to become a biologist.

I suggest that you look at Collins Outline of College Biology. Reading chapters 2-5 and 12-15, should give you basic information you desire. Another choice is Schaum's Outline of Biology, Third Edition, chapters 2-4 and 7-10. Both books cost less than $20.00 and are easy to understand. Hope this helps.

# Answer
> 3 votes
As someone who came from a computer science background and led a team developing a product involving bioinformatics I can sympathize with the challenge of picking up the domain - but it is a fascinating area to work in.

As @JCEHR has pointed out, it is not an absolute requirement to study biology but it is helpful to start to pick up some of the principals. Bioinformatics is not just about molecular biology, genomic sequencing, protein expression and protein structure (don't worry if you don't understand these terms now) but I am fairly confident that this is the area that the vast majority of 'traditional bioinformatics' is applied and would be the core of any course on the subject. One of the most important measurable features of DNA, RNA and Protein is that they are a string of molecules that can be represented by a software string - the annotating, storage and (fuzzy) searching of those strings are key techniques.

As well as a general biology primer, you could also consider looking at a book that discusses genomics. The following looks good but it's kind of pricey:

*A Primer of Genome Science*, by Greg Gibson and Spencer V. Muse

# Answer
> 2 votes
As a Computer Scientist who did their minor in Biochemistry, my recommendation would be Larry Gonick's Cartoon guide to Genetics.

This is not a joke. I know of several respectable Bioinformaticians who learnt genetics this way. The book explains most of what, if not everything, you will need to know and supplies the most intuitive visuals to wrap your mind around the underlying concepts. And it's a fun read.

# Answer
> 1 votes
As others told you: it depends a little on the book that you will be using, as well as on the topics taught. Sometimes it will be rather self explanatory. However in order to be better prepared (and get used to the terminology) look at some primers on the web, like Preparata: A Biology Primer for Computer Scientists.

Do we have colleagues, or is the "biostar" site a friendly clone? See the question: "Best resources to learn molecular biology for a computer scientist".

---
Tags: algorithms, reference-request, education, bioinformatics
---


# Question
Title: Maximimal Independent Set on Ring and Path
Let's consider distributed version of algorithm for finding MIS of any graph $A$.

For details, MIS - Maximimal Independent Set.

Slow version of distributed algorithm for MIS, page 2 - Distributed algorithms. Maximal Independent Set

In worst case, time complexity of the algorithm is $\text{O}(n)$ and a message complexity is $\text{O}(m)$. If nodes of the network are not unique than it's not possible to find MIS.

I am interested in few special cases, when the graph is a **path** and **ring**.

**Exercise**: Consider a path graph $G$ with vertex UIDs to be a random permutation of $\\{1,…,n\\}$, time complexity of MTS\_Slow is $T \leq c\log n$ for a constant $c$ with probability $1-\frac{1}{n}$. What is a time complexity and it's probability on a ring $G$ with vertex UIDs to be a random permutation of $\\{1,…,n\\}$.

**Ideas:** Time complexity has $\log n$ factor, therefore on each phase number of candidates for MIS nodes from a path graph $G$ should be divided by constant factor. Lets consider the worst case, when only one node is choicen to join MIS on each phase, it occurs when the nodes' UID's are located in increasing or decreasing order, it happes with probability $P(B)=\frac{1}{2^n}$, $P(A)=\frac{1}{2}$, where B - nodes' UID is placed in increasing order, A - the next node's UID is bigger the the current one. But how to show that the number of candidates is getting lower by any arbitrary constant factor. The problem is I have a difficulties in defining probability for taking arbitrary constant factor of nodes on each phase.

Case with ring should be similar to a path graph case.

I will appreciate any help in solving this exercise.

# Answer
if a node terminates the algorithm after an iteration with probability $1/c$, then after $k$ iterations this probability is $c^{-k}$. and the number of iterations required is $\ln \_c n$. This is done by arguing that the expected number of nodes after $k$ iterations is $n c ^{-k}$, and we want to make this value less or equal to 1. We achieve this by setting $k$ to $\ln \_c n$.

Therefore, replacing $k = \ln \_c n$ leads to $c^{- \ln \_c n} = 1/n$, and whence the probability of correctness is $1 - 1/n$.

How to find $c$ ? As I said in my comment, I truly dont know the exact value. Here is *a* solution. Someone else may correct me.

We should calculate the probability that a node $v$ terminates the algorithm in any given iteration. This happens if $v$ is greater than its two neighbors OR if the left neighbor of $v$ is greater than all its neighbors OR if the right neighbor of $v$ is greater than all its neighbors. The probability of any of these events is 1/2\*1/2 = 1/4. The probability of any of these events is 1/4 + 1/4 + 1/4 = 3/4. Therefore $c = 3/4$.
> 1 votes

---
Tags: algorithms, graphs, distributed-systems
---


# Question
Title: Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points
I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull:

> Let $S= \\{p\_1, \dots , p\_n \\}$ a set of points and $CH(S)$ the convex hull of $S$.

---

The first problem and corresponding algorithm are as follows.

> Find the smallest subset $R \subset S$ for $CH(R) = CH(S)$. Since there are $2^n$ subsets, the complexity is $\mathcal{O}(2^n)$.

Pseudocode version:

```
foreach (s in S.subsets)
    if (CH(R) == CH(S))
        return R

```

Since we don't know $CH(S)$, and indeed it's our goal to compute $CH(S)$, how can we check if $CH(R) = CH(S)$?

---

The second problem is as follows.

> Let $p,q,r,s \in S$. $s \in CH(S)$, if $s \not\in triangle(p,q,r)$

And here is the algorithm:

Shouldn't the first part of the sentence (of the problem) be

> Let $p,q,r \in CH(S)$ and $s \in S$.

?

However, even in this case, we don't know what $CH(S)$ is.

My counterexample why this algorithm wouldn't work:

At the start, we check the $triangle(1, 2, 3)$, and see that $4$ is not in the triangle, and mark $4$ as not an element of the convex hull, but $4$ should be part of the CH!

# Answer
**A1)** You're right, the algorithm description sounds kind of weird. A naive algorithm that takes exponential time would rather be something like

```
foreach (R in S.subsets)
  if (R.isConvexHull(S))
    return R

```

However, the method for checking whether R is a convex hull needs $n$ time, so we obtain a runtime of $n2^n$.

**A2)** Your premise is missing some quantifiers. I think, what you wanted to say is

"$\forall s, $ if $\forall p,q,r \in S, s \not \in \triangle(p,q,r),$ then $s$ is on the convex hull."

Furthermore, go through your example again. You understood it wrong. If you check triangle (1,2,3), you see that 4 is **not** in the triangle. Hence, 4 *might* still be on the convex hull (but it doesn't have to). On the contrary, if you check the triangle (4,3,2), you see that 1 is on the interior. Therefore, 1 is *definitely not* on the convex hull.

This still does not give you a convex hull algorithm though, since the points still have to be sorted by the end. However, this is no problem, since the rest of the algorithm already needs $\mathcal{O}(n^4)$ time.
> 5 votes

---
Tags: algorithms, computational-geometry, convex-hull
---


title: Jamming signal useless in CSMA / CD?

text:
# Question
Title: Jamming signal useless in CSMA / CD?
I'm looking at collision detection in communication protocols, in particular Carrier sense multiple access with collision detection (CSMA/CD). According to what I've read on Wikipedia, a collision seems to cause the wave of the outgoing signal and the wave of the incoming signal to overlap. Thus, the signal has values with more amplitude than allowed for a "1-bit". This could be used as a working collision detection algorithm.

However, what's the use of the "Jam signal", as explained in the same Wikipedia article, then? It says that the CRC has to be faulted, but we already have a collision detection algorithm.

# Answer
> 2 votes
Wave overlaps need not cause just 1-bits with a too high amplitude. They could also flip bits around, or nullify each other. Thus error correction is not as easy as you describe and one actually has to use some kind of checksumming like CRC to detect errors reliably.

---
Tags: computer-networks, communication-protocols, encoding-scheme
---


# Question
Title: Can Real-Time Strategy games be ever solved?
With the advent of BWAPI, many AI enthusiasts have been making amazing AIs that can compete against top players in Starcraft. This led me to wonder if RTS (Real-Time Strategy) games can ever be solved theoretically.

One of my colleague argues no, because RTS games are non-deterministic and stochastic. What does this mean exactly? For instance, in Starcraft you have a set of defined and limited moves (I.E: Units, buildings, economy) you can make in the game, so I don't see what can be so stochastic about the game.

# Answer
> 1 votes
It looks like there are elements of (pseudo)randomness in StarCraft.

Of course, this does not seem like a major property and you can ask for solving the game without this feature. Then you end up with a very deep game tree that probably does not have any nice mathematical property or symmetry that would help you to effectively handle it. This is where it differs from the trees that arise from mathematical games.

You can use game theory to play StarCraft well (Monte Carlo, maybe?), but unless there is some strong form of rush that would quickly cut complexity of the tree, I am skeptical about solving it.

---
Tags: artificial-intelligence, computer-games
---


# Question
Title: Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?
I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?

# Answer
> 3 votes
This paper shows that for each priority queue implementation satisfying some technical condition (which holds for binomial heaps) there is a sequence of operations consisting of $n$ INSERTs, $n$ DELETEs and $n$ FIND-MINs that takes time $\Omega(n\log n)$. Since INSERTs are amortized $O(1)$ in binomial heaps, the DELETEs and FIND-MINs together must take time $\Omega(n\log n)$. Unfortunately, in the construction the INSERTs are interspersed between the other operations.

This is of course overkill for the case of binomial heaps.In the implementation in which FIND-MIN is implemented by comparing the roots of all trees. If we INSERT $2^m-1$ elements then we will have $m = \log(n+1)$ trees, and so FIND-MIN will take time $\Omega(\log n)$. In other implementations, it shouldn't be hard to concoct examples in which some MERGE operation (used inside all the others) takes time $\Omega(\log n)$.

You might be worried that even though these examples show that some operations could require logarithmic time, the amortized complexity is still better. You'll have to work harder, but after some though you should be able to come up with a sequence of $n$ INSERTs and DELETEs which takes amortized time $\Omega(\log n)$.

---
Tags: algorithms, data-structures, lower-bounds, heaps
---


# Question
Title: What are some good hints for proving non-regularity with the pumping lemma?
My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \\{a^{n} b^{n}\mid n \in\mathbb{N}\\}$. Although I know that these come with practice, I wondered if this community would have some input on the matter?

If you don't quite know what I am asking, think to calculus, when your professor used something that HE knew would get you from point a to point b that if YOU don't know, you cannot solve the problem.

# Answer
Always notice that you apply the *reverse direction* of the implication stated in the lemma when proving non-regularity. That is for any $k\in \mathbf{N}$ you pick a word $w\in L$ (depended on $k$) that has length at least $k$ and there is no way to split the word into three parts, such that pumping the middle parts in or out keeps the word in the language. Notice that you only consider partitions where the first two words together have length $k$ or less, and of course the middle part is not the empty word.

So here are a few general ideas.

1. Keep in mind that you pick the word dependent on $k$, so $k$ usually appears in the word $w$ as a parameter. For example in $\\{a^nb^n \mid n\ge 0\\}$ you pick $w=a^kb^k$.
2. It is crucial to pick the right word $w$. Pick a word that has an easy structure. Make it as easy as possible.
3. Notice that you are only allowed to pump at the beginning of the word. Use this restriction, by choosing a word in which the first $k$ letters have a simple structure.
4. For unary languages like $\\{a^{n^2}\mid n\ge 0\\}$ pick a very large word and hope that the distance to the next word in $L$ is larger than $k$. In the example pick $w=a^{k^2}$, the the next larger word in $L$ is $a^{(k+1)^2}$, but $(k+1)^2-k^2=2k+1$. Pumping the middle words once, gives a word that is too short. Another idea for unary languages is to pick $i$ in terms of $k$.
5. Don't forget to cover the case of pumping the middle word out.

You can see the (reverse direction) of pumping lemma as a two player game. Someone picks a $k$ then you pick the $w\in L$, then he splits the $w$ according to the rules, then you pick a repetition of the middle word. If the pumped word is not in the language then you win. If this game has a winning strategy for you, then $L$ is not regular.
> 5 votes

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


# Question
Title: What would be the classification of R according to paradigms?
I would like to know in which classification is the R programming language. It has elements of the imperative paradigm and object oriented paradigm (some things like that even a number is an object and they can be freely mixed). I am not quite sure if it has functional programming characteristics. So it can be considered a scripting language?

What would be its classification in one of the paradigms?

R can do tasks in batches so it can be considered also a scripting language, is that so?

# Answer
## Scripting language

I once heard the following definition of what a *scripting language* as at some conference. Namely, if its main purpose is to orchestrate components that exist in their own rights outside of the language. Consider a theatre script - it orchestrates actors who all exist independently of the script. Bash scripts and batch files (the latter article even has a section entitled "Other Windows scripting languages") are prototypical representatives of a scripting language according to the given definition, because they are completely useless if you couldn't invoke external tools or commands like `grep`, `ls` or `cd`.

The most important part of this definition is the "to orchestrate components that exist in their own rights outside of the language" bit. At the end of the day, all computer languages (no coined term AFAIK) allow you to orchestrate components, thereby creating more new and complex components. However, in a *programming language* you mainly orchestrate library functions that only exist because the programming language exist.

Having said that, I would consider R a multi-paradigm programming language, where multi-paradigm includes at least the *procedural paradigm* and *object-oriented paradigm*.

## Imperative paradigm

As a last remark: *imperative programming* includes both aforementioned paradigms and is different from *declarative programming*. An imperative language focuses on the "how to do things" and consists of more or less directly executable steps, whereas a declarative language focuses on the "what to achieve". As an example, consider sorting a list. An imperative program what consists of a procedure/method that moves elements around and thereby sorts the list, and each single instruction can be executed in a sort of obvious way. A declarative program would consist of a description of the property "sorted", but how to "execute" the property is not at all obvious. If you are interested in the differences, have a look at Quicksort implemented in Java and Prolog (among others).

## What Wikipedia says

Addressing a comment by @vonbrand and in support of my reply to that comment, here are a couple of quotes from Wikipedia:

The first line in the article on Perl describes Perl as a

> Perl is a high-level, general-purpose, interpreted, dynamic programming language.

but in the second paragraph you find

> Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier.

It is similar for Python, where the first paragraph is

> Python is a general-purpose, interpreted high-level programming language whose design philosophy emphasizes code readability. Its syntax is said to be clear and expressive. Python has a large and comprehensive standard library.

In the second paragraph you'll find

> Like other dynamic languages, Python is often used as a scripting language, but is also used in a wide range of non-scripting contexts.

which, I think, supports my comment given below quite nicely.

Furthermore, the article about scripting languages defines

> A scripting language or script language is a programming language that supports the writing of scripts, programs written for a software environment that automate the execution of tasks which could alternatively be executed one-by-one by a human operator.

and then goes on as follows, where the first sentence is, in my opinion, the most important one

> Scripting is usually a property of the primary implementations of a language, rather than a language per se, although many languages are not very suited to this kind of implementation. For example, C++ interpreters do exist, but C++ is generally not considered a scripting language for two reasons: these implementations are rarely used, and the time required to write program in C++ would be far greater than the time required to write an equivalent script in a language like Python.
> 5 votes

---
Tags: programming-languages, programming-paradigms
---


# Question
Title: Origins of the term "distributed hash table"
I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term *distributed hash table* came from. (I know it is not rocket science to just derive it from *distributing a hash table*, but somebody somewhere must have come up with it).

Most papers I read referred to the original paper on *consistent hashing* and one of the first algorithms making use of it (e.g Chord). I know that there was a lot of research on distributed databases in the 80s, so I figure that the term, or maybe the idea behind it, should be older than ~15 years.

The motivation behind this question is that knowing an earlier date and maybe another term for a similar idea would possibly widen the range of useful information I could gather for my research. For example, what have others done that is similar to what I want to do and where have they failed. Etc. etc.

I tried to find more on this subject using *Structured Overlay Networks* as a search keyword, but the resulting definitions/papers are also quite young, which leaves me with the impression that the research topic might not be so old after all.

Does anybody of you know of earlier research (maybe pre-90s?) in the topics of distributed hash tables and/or structured overlay networks? I'd be glad to hear some keywords which could lead me to more historic papers.

# Answer
The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda\[Lin86\]. The paper attributes the term to *Rob Bjornson* (which I believe to be this guy), but only cites personal communication as their mean of learning the term. \[Lin86\] also refers D. Gelernter: *Dynamic global name spaces on network computers.* (1984), which is said to propose an implementation. I didn't find the paper, so I can not say if this is true. Another report (which I didn't find as well) by Leichter is said to discuss the implementation further: *Implementing the Unimplementable -- Algorithms for Linda's Tuple Space*.

The source in Linda seems to be a dead end, but was the oldest source of the term that I could find. I think it could be attributed with the term, but I may be confuted. If we assume that Bjornson came up with the term, at least the time frame would be fitting. Bjornson started his work in 1984, so if he is attributed with the term, the term's origin would neatly fit into the time were the Linda papers above were written.
> 5 votes

---
Tags: data-structures, terminology, distributed-systems, hash-tables, history
---


# Question
Title: Complexity of testing if a number is a primorial
For the $n$-th prime number $p\_n$ the *primorial* $p\_n\\#$ is defined as the product of the first $n$ primes.

> What is the complexity of testing if a given number $n$ is a primorial?
> Is it related in some way to the FACTORING problem?

# Answer
> 4 votes
This is simpler than factoring. You can simply multiply all prime numbers up to the point where you (a) reach $p\_n$ or (b) get a product which is larger than $p\_n$. In the first case, you answer `yes` otherwise you answer `no`.

The reason it is simpler is that the prime factorization is trivial, whereas in the FACTORING problem, you don't know how many of each prime number you need.

---
Tags: complexity-theory, reference-request
---


# Question
Title: Clarifications on primitive recursive function definition
I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes $x+y$, then, in order to show that $f(x,y)=x+y$ is primitive recursive, my lecture notes give the following equations:

\begin{cases} f(x,0)=x \\ f(x,y+1) = f(x,y)+1 \end{cases} this first bunch makes perfect sense to me, on the other hand, looking at the equations down below, I don't get why a new function $g$ is used and also why does it have three parameters, when the sum clearly has only two? Is that $y$ the variable that supposedly holds (partial) results from computation?

\begin{cases} f(x,0)=u^1\_1(x) \\ f(x,y+1) = g(y, f(x,y),x) \end{cases}

where $g(x\_1, x\_2, x\_3) = s(u^3\_2(x\_1, x\_2, x\_3))$.

# Answer
The first equation is what you would normally write down as a mathematician if you were to define addition in terms of successor. The second equation is the same thing, except it is written in a precise manner so as to make it obvious that this indeed is a definition by primitive recursion. You have to pay close attention to details.

A function $f$ is said to be defined by primitive recursion if we can write its definition in the following form: $$f(x\_1, \ldots, x\_k, 0) = u(x\_1, \ldots, x\_k)\\ f(x\_1, \ldots, x\_k, n+1) = v(x\_1, \ldots, x\_k, n, f(x\_1, \ldots, x\_k, n)$$ where $u$ is a function of $k$ arguments and $v$ is a function of $k + 2$ arguments. Furthermore, $u$ and $v$ must be known to be primitive recursive alrady.

The first equation in your question is *not* of this form but the second one is. Concretely:

1. We cannot write $f(x,0) = x$ because "$x$" is not a primitive recursive function, whereas $u\_1^1$ is. Again, it does not matter that $u\_1^1(x)$ happens to be the same thing as $x$ because we are doing bureaucracy, and no shortcuts are allowed.
2. We cannot write $f(x, y+1) = f(x,y) + 1$ because the right-hand side is not in the correct form. For it to be in correct form we need to find a suitable $g$ so that $f(x, y+1) = g(x, y, f(x, y)$. Here $g$ *must* take $y$ as its second argument, even if it does not need it, otherwise we are not following the correct form. With this in mind it is easy to see that $g(a, b, c) = s(u^3\_2(a,b,c))$ does the job.

When you try to show that something satisfies a definition (in this case "is primitive recursive") you have to get it *exactly* in the correct form. Only later, when you already understand what is going on, can you start to make shortucts and wave your hands, and say "it's obvious". Your professor does not think you are at that stage (and you are not, since you asked this question).
> 5 votes

---
Tags: computability, terminology, recursion
---


# Question
Title: Are Turing machines more powerful than pushdown automata?
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.

Is this true?

# Answer
> 13 votes
If you only consider that 'Turing machines can always be made to behave like a stack' you can only conclude that they are at least as powerful as pushdown automata.

But in general, yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can describe Context Sensitive Languages.

# Answer
> 17 votes
You can't go to the bottom of the stack without "forgetting" the rest of the stack. With a Turing machine you can easily go back and forth on the tape.

This simple task cannot be done with a pushdown transducer (roughly the same thing as the pushdown automata, but that can write things at each step), but can easily be done with a tape:

> Read a string $w$ and then write the string twice: $ww$

If you don't want to hear about transducers, the similar problem is for you: this language is easily recognized by a Turing machine, but not with a pushdown automaton:

$$L = \\{ ww \mid w \in Σ^\* \\}$$

but I think with a transducer you get a grasp of the difference.

# Answer
> 12 votes
Turing machines are indeed more powerful than regular PDAs.

However in special case of a PDA with two stacks (TPDA or 2-PDA) the TPDA is equally powerful than a turing automata.

The basic idea is that you can simulate the TM's tape using two stacks: in the left stack everything is stored which is left from the head on the Turing-tape, while the symbol under the head and everything right from the head is stored in the other stack. And thus the TPDA can simulate the work of a Turing machine, and they are equivalent. A slightly more detailed description can be found here.

# Answer
> 5 votes
*One* Turing machine is more powerful than *one* pushdown automaton -- that is a fundamental theorem of automata theory and can be proved in a number of ways. For example, the halting problem for TMs is undecidable -- there is no program (or other TM) that will always give a correct yes-or-no answer to the question: will this TM on this input halt. But for PDAs, the halting problem is solvable. So the models have inherently different power, the TM model has more power than the PDA model, but also "suffers" for it.

But *two* pushdown automata "working together" can simulate a Turing machine. We just have to specify what we mean by two PDAs working together -- they are both connected to the input string and each can work with its stack independently of the other. Their finite state controls are also connected, or equivalently, merged into a single finite-state control.

The proof of that goes roughly that each of the PDAs can simulate half of the TM's tape, that is, the part of the TMs tape starting at the home square and going out indefinitely to the left or right. The details can get a bit messy, but the basic idea is simple. The top of the "left" pushdown store represents the current head square of the TM and the bottom represents the leftmost active square of the TM's tape; similarly for the "right" pushdown store. As for moves, for example, when the TM moves one square to the left, the simulating combo of PDAs pops a symbol from the right pushdown store and pushes it onto the top of the left pushdown store. When the TM rewrites the symbol under its head, the left pda pops its top symbol (the prior value) and pushes back another symbol (the new value).

So the combo of two PDAs working this way has exactly the same power as TMs, and the halting problem for the combo is also undecidable.

# Answer
> 3 votes
Just exhibit a TM accepting $0^n 1^n 2^n$, which isnt't context free (and thus there is no PDA accepting it).

# Answer
> 2 votes
The usual proof is one with detour.

1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
2. Note that Turing machines accept all recursive languages (by definition).
3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping Lemma -- which is easily proven on with context-free grammars -- and $\\{ww \mid w\in \\{a,b\\}^\*\\}$.

---
Tags: formal-languages, computability, automata, turing-machines, pushdown-automata
---


# Question
Title: Using transitive closure to determine acyclic property on directed graph
Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not?

I'm trying to achieve this but getting stuck on the reflexive property of the transitive closure!

# Answer
It is possible to use Warshall's algorithm for that also. If there is is a negative entry on the diagonal, then the graph contains a negative cycle. If both the shortest path from i to j and the shortest path from j to i is not infinite, then the graph contains a cycle. If there are no i and j with this property, then the graph is acyclic. (This takes only $O(|V|^2)$ steps to check, while Warshall's algorithm itself takes $O(|V|^3)$ steps.)

However, it's faster to use depth first search and check that there are no backward edges in the depth first search tree. Also note that there exists an algorithm for computing the transitive closure (including the transitive reduction) in $O(|V|\cdot|E|)$ steps. (I think it uses a topological order as a starting point.)
> 3 votes

# Answer
After running Warshall's algorithm (let's call the input graph $G$ and the resulting graph $G'$), we can reason that if there were a cycle $c\_1\rightarrow c\_2\rightarrow\ldots\rightarrow c\_n\rightarrow c\_1$ in $G$, then for every old edge of this cycle $c\_i\rightarrow c\_{i+1}$ there has to be a new, antisense edge $c\_{i+1}\rightarrow c\_i$, because it's a part of the closure of the path $c\_{i+1}\rightarrow c\_{i+2}\rightarrow\ldots\rightarrow c\_{i-1}\rightarrow c\_i$.

Also, for every 2-cycle ($c\_1\rightarrow c\_2\rightarrow c\_1$) in $G'$ we know from the semantics of the algorithm that any of the two edges stands for some oriented path in $G$: $c\_1=p\_{1\_1}\rightarrow p\_{1\_2} \rightarrow\ldots p\_{1\_n}=c\_2$ and $c\_2=p\_{2\_1}\rightarrow p\_{2\_2} \rightarrow\ldots p\_{2\_n}=c\_1$. It's easy to think about gluing these two together to get at least one original cycle.

So, we estabilished an equivalency between "there is a cycle in $G$" and "there is a 2-cycle in $G'$".
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Do self-loops in DFA cause infinite languages?
A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language.

The answer is "false". I've read this question, but I'm still wondering why $M$ does not necessarily accept an infinite language. Isn't the language $b^\*$ infinite? Don't all self-loops look like $b^\*$?

# Answer
> 11 votes
the answer is False:

consider a DFA that has no accepting states at all: any loop is not relevant, the language will always be the empty set.

Another option - a loop on a *dead* state, etc.

However, if it contains a loop on an "accepting path", then indeed the language must be infinite. (this is actually the key idea behind the pumping lemma..)

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: How to prove "The power set of a countable set must be uncountable"?
I'm not sure if this statement is correct, but my friend said so.

The problem arose from this T/F question: Let $F=\\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\\}$, then $2^F$ (Power set of $F$) is uncountable.

And its answer is True. The set of primitive recursive functions is countable, and I would like to know the proof to the statement above...I believe I've seen it somewhere in the book but can't find it now.

Thank you for your time.

# Answer
This is Cantor's diagonalization lemma:

Let $S$ be a countable set and suppose that there is a bijective function $\phi: S \to 2^S$. Let $U = \\{x \in S \mid x \notin \phi(x)\\}$. (Notice that our only assumption is the existence of the bijective function.)

Since $U \in 2^S$, and $\phi$ is bijective, there must be a $u \in S$ s.t. $\phi(u) = U$.

Now I ask you: Is $u \in U$?

If you answer that question, you have the answer: $\phi$ cannot exist! Hence $2^S$ cannot be countable. You should also show that there is an injective function $\psi: S \to 2^S$, but this is trivial: $\psi(x) = \\{x\\}$, so $|S| \leq |2^S|$.

To complete the argument you must also show that there cannot be a bijective function from $\mathbb{N}$ to $2^S$ but this is immediate since there is one from $\mathbb{N}$ to $S$.
> 5 votes

---
Tags: turing-machines, recursion, uncountability
---


# Question
Title: Difference between := and ← in pseudocode
This is a snippet from some pseudocode for a sorting algorithm. In it, the symbol ← is used to denote assignment, for example for the variable `done`. However, in the `while` loop the statement `done:= false` is written. I would assume it is also an assignment statement but I suspect it means somethings else, or perhaps extra, since if not, the ← would have simple be used again.

```
Algorithm MyAlgorithm(A, n)
    Input: Array of integer containing n elements
    Output: Possibly modified Array A

done ← true
j ← 0
while j ≤ n - 2 do
     if A[j] > A[j + 1] then
        swap(A[j], A[j + 1])
        done:= false
     j ← j + 1

```

# Answer
> 8 votes
The use of `:=` in this context appears to be a slip-up from whomever it is who wrote that pseudocode. The initial impression given is that they have different meanings (I thought at first that `:=` was perhaps "redefine", and that  was "declare and define"). However, with the use of `j ← j + 1` on the line following it, it seems clear that the `:=` was a mistake.

In general, `:=` and `=` are the most common assignment operators, seemingly in both pseudocode and real code. You may be interested in looking at notations of the assignment operator in various programming languages, which include `:=`, `=`, `<-`, , and many others.

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


# Question
Title: What sort of algorithm/communication model/data structure do collaborative real time editors use?
I am researching collaborative editing systems for some work, but so far my search is turning up blank.

Collaborative real-time editing systems almost all have features like:

* Many users can edit the document at the same time
* All changes are dated and saved in a linear revision history
* Edits are visible in semi-real time
* Who-wrote-what is tracked for all content

I cannot think of a data- and procedure model to encompass all of these without huge inefficiencies, for example:

* Take user input as a few typestrokes at a time, thus enabling real-time visibility but with horrible server loads.
* Take user input as element changes, thus disabling real-time visibility and complicating many-user-editing of one paragraph.
* Edit a XML Document Model Object in place responding to inputs, but making it difficult to version/revision track.
* Edit linear text stored in an appropriate editing structure responding to inputs, making it difficult to verify that correct markup is being generated.
* Store revision history accumulating, requiring computational resources but easing on space.
* Store revision history whole, requiring space but easing on computation.

Am I off track? Does there exist good solutions to these problems? What, if any, is the relevant litterature?

# Answer
The usual approach is operational transformation. The wikipedia page seems to be pretty good. Here are some other references:

Here's a paper on a different approach: Real time group editors without operational transformation. (Note: I haven't actually read it, so can't speak to how good it is)
> 4 votes

---
Tags: data-structures, efficiency
---


# Question
Title: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?
From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.

Can it be said then that every algorithm has a complexity of $O(\infty)$ since infinite complexity is the worst ever possible? By the same token, can it be said that every algorithm is $\Omega(1)$ since the absolute lowest complexity an algorithm can be is a constant?

# Answer
> 14 votes
To be clear, Big O and Big Omega are classes of functions. So if I have for example $\Omega(1)$, that's a set of a whole bunch of functions.

An algorithm's complexity is a function giving how many steps the algorithm takes on each input. This function may be in a class like $\Omega(1)$, or not.

$\Omega(1)$ is the class of functions $f(x)$ that are greater than some constant $c$ as $x$ goes to infinity. According to the technical definition, the function $f(x) = 0$ is not $\Omega(1)$, so an algorithm that never takes any steps (for instance) would not have complexity $\Omega(1)$. But virtually all algorithms would have complexity in $\Omega(1)$. (For example algorithms that always take at least one step.)

Since $\infty$ is not a number, $O(\infty)$ is not defined under any definition I've seen. It does not seem to be interesting to make this definition ( "all functions which are either finite or undefined"? but that is just all functions). So intuitively the answer to your question is yes, infinity is an upper bound on all algorithms' running times, but technically it's somewhat meaningless.

As a sidenote, we could extend little-o to include a domain of infinity by saying $f(x)$ is $o(\infty)$ if $f(x)$ is finite (i.e. well-defined) for all $x$. Under a definition like that, an algorithm that does not halt on some inputs would not have complexity $o(\infty)$. But every algorithm that does halt on all inputs would.

---

Edit/PS as pointed out by Yuval, we can give a slightly better answer for $O(\infty)$. Let's restrict attention to algorithms that halt on all inputs. Then we can define a function that grows like the maximum number of steps taken by *any* algorithm that halts. Call it $B(n)$. Then every algorithm's running time will be $O(B(n))$.

To define the function, let's take Yuval's suggestion and let $B(n) = $ the maximum number of steps taken by any halting TM of up to $n$ states on an input of up to $n$ bits. Now given any algorithm, it will be encoded as a Turing Machine, so it will have a certain number of states; say $N$ of them. Then the running time of the algorithm on inputs of size $m \geq N$ is at most $B(m)$. We can see this because $B(m)$ takes the maximum over all Turing Machines up to a certain size, including this one, so $B(m)$ will be at least as big as this TM's runtime.

See also: http://en.wikipedia.org/wiki/Busy\_beaver

---
Tags: complexity-theory, algorithm-analysis, asymptotics
---


# Question
Title: Homomorphisms and isomorphisms in an equational calculus
Suppose we have an algebraic specification in the form: $\\{S,F,w\\}$ where $S$ are the sorts, $F$ are the functions and $w$ are the set of equations. For example, the specification for natural numbers:

* $S = \\{\mathrm{int}\\}$
* $F = \\{ 0: \mathrm{int}, \\; \mathrm{succ} : \mathrm{int}\rightarrow\mathrm{int}, \\; \mathrm{pred}: \mathrm{int}\rightarrow\mathrm{int} \\}$
* $w = \\{ \mathrm{succ}(\mathrm{pred}(x)) = x, \\; \mathrm{pred}(\mathrm{succ}(x)) = x \\}$

My question is, why and where do we need homomorphisms and isomorphisms in this case? How do homomorphisms and isomorphisms look like between algebras ?

# Answer
> 6 votes
Can you come up with two different algebras, say, one where the domain is $\mathbb{N}$ and one where the domain is $\\{0,1\\}$ and in the former, `suc` and `pred` work as you would assume, and in the latter, they are modulo 2 operations? Then, try to come up with a homomorphism from one to another.

Then, try to make an algebra, where the domain is $\\{0, s0, ss0, sss0, \dots\\}$ and define `suc` and `pred` as you would guess. Make an isomorphism from this one to the one with $\mathbb{N}$ as domain.

Finally, you can make the "term algebra", which has as domain all strings that are valid "terms", i.e.: "0" is in the domain, and for every element $t$ in the domain, "suc($t$)" is in the domain, and "pred($t$)" is in the domain. Their interpretation is simply that the constant `0` maps to the string "0". The term `pred(suc(suc(suc(0))))` maps to the string "pred(suc(suc(suc(0))))". Now, you might have a hard time making an isomorphism from this to the standard algebra (the one with $\mathbb{N}$), since "0" and "pred(suc(0))" should both map to 0.

I'm not sure exactly what you ask for, but these two tasks should get you started, at least.

---
Tags: semantics, denotational-semantics
---


title: Collision resistant hash function

text:
# Question
Title: Collision resistant hash function
A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.

Let $h\_0:\\{0,1\\}^{2m}\rightarrow\\{0,1\\}^m$ be a $(\varepsilon, t)$-collision resistant hash function and $i\in\mathbb{N}\_{\geq 1}$.
Define a hash function $h\_i: \\{0,1\\}^{2^{i+1}\cdot m}\rightarrow \\{0,1\\}^m$ recursively using $h\_{i-1}$ in the following way:
Interpret the bit string $x\in \\{0,1\\}^{2^{i+1}\cdot m}$ as $x=x\_1 x\_2$, where both $x\_1,x\_2\in \\{0,1\\}^{2^i\cdot m}$.

Then the hash value $h\_i(x)$ is defined as

$$h\_i(x)=h\_0(h\_{i-1}(x\_1)h\_{i-1}(x\_2)).$$

For which $(\varepsilon\_i, t\_i)$ is $h\_i$ $(\varepsilon\_i, t\_i)$-collision resistant?
And can we successfully use the birthday attack on this hash function to find collisions?

# Answer
> 3 votes
The birthday attack applies to any hash-function, regardless of its structure, and also to $h\_i$.

For your first question, here is a possible hint. Note that

* if we can find a collision in $h\_i$ then we can find a collision in $h\_0$ (by considering the top-most $h\_0$, for instance).
* if we can find a collision in $h\_0$ then, we can find a collision for $h\_i$ (by replacing one of the inner-most $h\_0$ with it's collision).

# Answer
> 2 votes
There's a problem with the formal details of your definition of collision-resistance: if we take it seriously, then *no* function (whose output is shorter than its input) can ever be collision-resistant.

By the pigeonhole property, it is guaranteed that *there exists* some pair of messages $x,x' \in \\{0,1\\}^{2m}$ such that $h\_0(x)=h\_0(x')$ but $x\ne x'$. Therefore, *there exists* some circuit $C$ that outputs a collision in $h\_0$ (just take the circuit that has $x$ and $x'$ hardcoded in it and that outputs $x,x'$; it will do, and it is very small, with fewer than $t$ gates for any reasonable value of $t$). Consequently, no matter what function $h\_0$ you pick, it won't be collision-resistant.

Similarly, no matter what function you pick, $h\_i$ will never be collision-resistant.

Therefore, the question is framed poorly. I suspect you will want to go back to the drawing board and think more carefully about what exactly you want to know.

---
Tags: cryptography, hash
---


# Question
Title: Prove $\varphi(x)$ to be primitive recursive
Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation} f(x\_1,\ldots, x\_n) = \begin{cases} g(x\_1, \ldots, x\_n) \\;\\;\\;\\;\\;\text{ if } P(x\_1, \ldots, x\_n)\\ h(x\_1,\ldots,x\_n) \\;\\;\\;\\;\\;\text{ otherwise} \end{cases} \end{equation} Then $f$ belongs to $\mathcal C$ because $$f(x\_1, \ldots, x\_n) = g(x\_1, \ldots, x\_n) \cdot P(x\_1, \ldots, x\_n) + g(x\_1, \ldots, x\_n) \cdot \alpha(P(x\_1, \ldots, x\_n))$$ where

\begin{equation} \alpha(x) = \begin{cases} 1 \\;\\;\\;\\;\\;\text{ if } x = 0\\ 0 \\;\\;\\;\\;\\;\text{ if } x \neq 0 \end{cases} \end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation} \varphi(x) = \begin{cases} 2x \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{ if } x = t \cdot t \\ 2x+1 \\;\\;\\;\\;\\;\text{ otherwise} \end{cases} \end{equation} hence $$\varphi(x) = 2x \cdot P(x\_1, \ldots, x\_n) + (2x+1) \cdot \alpha(P(x\_1, \ldots, x\_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?

# Answer
> 1 votes
To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as *programming* asignments (in a rather cruel programming language).

---
Tags: computability, recursion, check-my-proof
---


title: Master theorem not applicable?

text:
# Question
Title: Master theorem not applicable?
Given the following recursive equation

$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that

$$ n^{\log\_2(2)} = n.$$

Now we check the first two cases for $\varepsilon \> 0$, that is whether

* $n\log n \in O(n^{1-\varepsilon})$ or
* $n\log n \in \Theta(n)$.

The two cases are not satisfied. So we have to check the third case, that is whether

* $n\log n \in \Omega(n^{1+\varepsilon})$ .

I think the third condition is not satisfied either. But why? And what would be a good explanation for why the Master theorem cannot be applied in this case?

# Answer
> 8 votes
The three cases of the Master Theorem that you refer to are proved in the *Introduction to Algorithms* by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).

It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\varepsilon}$ for any $\varepsilon \> 0$.

However the theorem can be generalized to cover this recurrence. Consider

**Case 2A:** Consider $f(n) = \Theta (n^{\log\_b a }\log\_b^k n)$ for some $k\geq 0$.

This case reduces to Case 2 when $k = 0$. It is intuitively clear that along each branch of the recurrence tree $f(x)$ is being added $\Theta (\log\_b n)$ times. A sketch of a more formal proof can be found below. The final result is that

$$T(n) = \Theta (n^{\log\_b a }\log\_b^{k+1} n).$$

In the *Introduction to algorithms* this statement is left as an exercise.

Applying this statement to the recurrence in question we finally get

$$ T(n) = \Theta(n \cdot \log^2 n). $$

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

$$ \lim\_{x\to c} \frac{f(x)}{g(x)} = \lim\_{x\to c} \frac{f^\prime(x)}{g^\prime(x)} $$

for any functions $f(x)$ and $g(x)$ differentiable in the vicinity of $c$. Applying this to $f(n) = n \log n$ and $g(n) = n^{1+\varepsilon}$ one can show that $\log n \not\in \Theta (n^{1+\varepsilon}).$

---

Sketch of the Proof of the Master Theorem for Case 2A.

This is a reproduction of parts of the proof from *Introduction to Algorithms with the necessary modifications*.

First we prove the following Lemma.

**Lemma A:**

Consider a function

$$ g(n) = \displaystyle \sum\_{j=0}^{\log\_b {n-1}} a^j h(n/b^j) $$

where $h(n) = n^{\log\_b a} \log\_b^k n.$ Then $g(n) = n^{\log\_b a} \log\_b^{k +1} n.$

**Proof:** Substituting the $h(n)$ into the expression for $g(n)$ one can get $$g(n) = \displaystyle n^{\log\_b a} \log\_b^k n \\; \sum\_{j=0}^{\log\_b{n-1}} \left(\frac{a}{b^{\log\_b a}}\right)^j = n^{\log\_b a} \log\_b^{k +1} n.$$

**QED**

If $n$ is an exact power of $b$ given a recurrence

$$ T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1) $$

one can rewrite it as

$$ T(n) = \Theta(n^{\log\_b a}) + \displaystyle \sum\_{j=0}^{\log\_b n - 1} a^j f(n/b^j). $$

Substituting $f(n)$ with $\Theta(n^{\log\_b a} \log\_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log\_b a }\log\_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.

# Answer
> 1 votes
The Akra-Bazzi theorem is a strict generalization of the master theorem. As a bonus its proof is a blizzard of integrals that will make your head spin ;-)

In any case, Sedgewick in his "Introduction to the analysis of algorithms" argues convincingly that one should strive to prove $T(n) \sim g(n)$ type asymptotics.

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


# Question
Title: Big-O complexity when c is a tiny fraction
Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is

$$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$

The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them. And with $g(n) = 3n^4$ we say $f(n)$ is $O(n^4)$.

But what would Big-O be if instead of 3 we were given a really small constant, for example $$f(n) = 0.0000000001n^4 + 6n^3 + 10n^2 + 5n + 4$$

Would we still say $f(n)$ is $O(n^4)$?

# Answer
Medium answer - yes. As you said for the previous case, in the long run $n^4$ outpaces all of them. This is still true despite the constant in front.

Check it out: plot.

Also, remember that $n^3$ and $n^4$ are both $O(n^4)$, and in fact are both $O(n^{10})$ because big-O is an upper bound. So you might ask "is there any tighter big-O bound on this function than $O(n^4)$, like $O(n^3)$, and the answer would be no.
> 8 votes

# Answer
Remember, when we write $f(x) = O(g(x))$ we are saying that there are two positive constants, $c$ and $x\_0$ such that $|f(x)| \le c|g(x)|$ for all $x \ge x\_0$. Asymptotic analysis is concerned with how functions behave ***in the limit***.

Let's rewrite your function:

$$ f(n)=an^4+6n^3+10n^2+5n+4 $$

This function is $O(n^4)$. Your question is "Can we change the value of the constant $a$, in such a way that $f(n)$ is no longer $O(n^4)$?" The answer is no. For any $a$, we can choose $c$ and $n\_0$ such that $|f(n)| \le c|n^4|$ for all $n \ge n\_0$. In fact, you have already stated this:

> The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them.

This holds true regardless of the value of $a$ in the function. It may take "longer" for $an^4$ to outpace the other terms, but it eventually will.
> 7 votes

---
Tags: complexity-theory, algorithm-analysis
---


# Question
Title: Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading `0`). Let $a$ and $b$ be integers, with $a \> 0$. Consider the language of the decimal expansions of the multiples of $a$ plus a constant:

$$M = \\{ \overline{a\\,x+b} \mid x\in\mathbb{N} \\}$$

Is $M$ regular? context-free?

(Contrast with Language of the graph of an affine function)

<sub> I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated. </sub>

# Answer
The language is regular.

**Hint:** cast out nines

---

### Proof idea

For $a=9$ and $b \< 9$,

> build an automaton with $9$ states labeled $0$ through $8$. $0$ is the initial state, and the one final state is $b$. From state $s$, on digit $d$, transition to state $(s + d) \\;\mathrm{mod}\\; 9$.

To handle other values of $a$ that are coprime with $10$,

> group digits in packets to find some $k$ such that $a$ divides $10^k-1$ (e.g. take $k=3$ if $a=37$ because $999 = 27 \times 37$).

To handle values of $a$ whose only prime factors are $2$ and $5$,

> note that it's all about a finite number of digits at the end.

To generalize to all values of $a$ and $b$,

> use the fact that union and intersection of regular languages are regular, that finite languages are regular, and that the multiples of $a\_1 \cdot a\_2$ are exactly the multiples of both when $a\_1$ and $a\_2$ are coprime.

Note that we use whichever technique is convenient; the three main elementary techniques (regular expressions, finite automata, set-theoretic properties) are all represented in this proof.

---

### Detailed proof

Let $a = 2^p 5^q a'$ with $a'$ coprime with $10$. Let $M' = \\{\overline{a'\\,x+b} \mid x\in\mathbb{Z} \wedge a'\\,x+b \ge 0\\}$ and $M'' = \\{\overline{2^p 5^q\\,x+b} \mid x\in\mathbb{Z} \wedge 2^p 5^q\\,x+b \ge 0\\}$. By elementary arithmetic, the numbers equal to $b$ modulo $a$ are exactly the numbers equal to $b$ modulo $a'$ and to $b$ modulo $2^p5^q$, so $M \cap \\{\overline{x} \mid x \ge b\\} = M' \cap M'' \cap \\{\overline{x} \mid x \ge b\\}$. Since the intersection of regular languages is regular, and $\\{\overline{x} \mid x \ge b\\}$ is regular because it is the complement of a finite (hence regular) language, if $M'$ and $M''$ are also regular, then $M \cap \\{\overline{x} \mid x \ge b\\}$ is regular; and $M$ is therefore regular since it is the union of that language with a finite set. So to conclude the proof it suffices to prove that $M'$ and $M''$ are regular.

Let us start with $M''$, i.e. numbers modulo $2^p 5^q$. The integers whose decimal expansion is in $M''$ are characterized by their last $\mathrm{max}(p,q)$ digits, since changing digits further left means adding a multiple of $10^{\mathrm{max}(p,q)}$ which is a multiple of $2^p 5^q$. Hence $0^\* M'' = \aleph^\* F$ where $\aleph$ is the alphabet of all digits and $F$ is a finite set of words of length $\mathrm{max}(p,q)$, and $M'' = (\aleph^\* F) \cap ((\aleph \setminus \\{0\\}) \aleph^\*)$ is a regular language.

We now turn to $M'$, i.e. numbers modulo $a'$ where $a'$ is coprime with $10$. If $a' = 1$ then $M'$ is the set of decimal expansions of all naturals, i.e. $M' = \\{0\\} \cup ((\aleph \setminus \\{0\\}) \aleph^\*)$, which is a regular language. We now assume $a' \> 1$. Let $k = a'-1$. By Fermat's little theorem, $10^{a'-1} \equiv 1 \mod a'$, which is to say that $a'$ divides $10^k-1$. We build a deterministic finite automaton that will recognize $0^\* M'$ as follows:

* The states are $\[0,k-1\] \times \[0,10^k-2\]$. The first part represents a digit position and the second part represents a number modulo $10^k-1$.
* The initial state is $(0,0)$.
* There is a transition labeled $d$ from $(i,u)$ to $(j,v)$ iff $v \equiv d 10^i + u \mod 10^k-1$ and $j \equiv i + 1 \mod k$.
* A state $(i,u)$ is final iff $u \equiv b \mod a'$ (note that $a'$ divides $10^k-1$).

The state $(i,u)$ reached from a word $\overline{x}$ satisfies $i \equiv |\overline{x}| \mod k$ and $u \equiv x \mod 10^k-1$. This can be proved by induction over the word, following the transitions on the automaton; the transitions are calculated for this, using the fact that $10^k \equiv 1 \mod 10^k-1$. Thus the automaton recognizes the decimal expansions (allowing initial zeroes) of the numbers of the form $u + y 10^k$ with $u \equiv b \mod a'$; since $10^k \equiv 1 \mod a'$, the automaton recognizes the decimal expansions of the numbers equal to $b$ modulo $a'$ allowing initial zeroes, which is $0^\* M'$. This language is thus proved regular. Finally, $M' = (0^\* M') \cap ((\aleph \setminus \\{0\\}) \aleph^\*)$ is a regular language.

To generalize to bases other than $10$, replace $2$ and $5$ above by all the prime factors of the base.

### Formal proof

Left as an exercise for the reader, in your favorite theorem prover.
> 3 votes

# Answer
Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with $a$ states 0, 1, ..., $a - 1$. Start state is 0, and from state $q$ on input the digit $d$ go to state $(10 q + d) \bmod a$. Accepting state is $b \bmod a$ (might need a tweak if $b \> a$).
> 9 votes

# Answer
**Hint #1**: first solve the more popular problem "write a automaton that recognizes the decimal/binary representations of numbers divisible by 3" **when the least signigicant bit** appears first.

Intermediate question: prove that $\\{ \overline{a\\,x+b}\mid a\\,x+b≥0 \quad x\in\mathbb{Z}\\}$ is regular.

**Hint #2**: The graph of the function $(n \mapsto 10n+d)$ "modulo $a$" is finite. You can compute it for each $d$ in $\\{0, \dots, 9\\}$ which is both the set of digits and the language of your automaton.

**Hint #3**: now, replace $x∈\mathbb Z$ with $x∈\mathbb N$. What does this change? Try to use the fact that regular languages are stable by intersection instead of building an *ad-hoc* automaton.

**Hint #4**: now assume that $a$ is a prime number (so that $\mathbb Z/a\mathbb Z$ is a field) and that we are still in the case where $x∈\mathbb Z$. We now use a representation where the first bit is the **most significant** bit. Can you build the automaton the same way?

**Hint #5**: you don't always have to build an automaton to prove a language is regular. How can you use previous results to prove that $M$ is regular? (with the most significant bit first)
> 8 votes

# Answer
It is regular. Let's first work in binary, which will generalize to any base \> 1. Let $M\_{a,b}$ be the language in question. For a = 1, b = 0 we get

$M\_{1,0} = \\{1, 10, 11, 100, 101, ...\\}$

which is all strings over $\\{0,1\\}$ without leading zeroes, which is regular (construct a regular expression for it).

Now for any $a$, with b still 0 we get $M\_{a,0}$ from $M\_{1,0}$ by multiplying numerically by a, that is, performing the transformation $\bar x \rightarrow \overline {ax}$ on each string of $M\_{a,0}$. That can be done bitwise by a sequence of shifts and additions of $x$ that depend on the bits of fixed string $\bar a$. The two transformations we need are:

$\bar x \rightarrow \overline {2x}$ which is $\bar x \rightarrow \bar x0$

and

$\bar x \rightarrow \overline {2x+x}$

Concatenating a 0 on the right clearly preserves regularity. We thus have only to prove that the second operation preserves regularity. The way to do that is with a finite-state transducer working on $\bar x$ from right to left. That's the hardest step. I suggest doing it with a pseudo-code program and some finite auxilliary memory (like some bit variables) rather than using states. As long as the memory is of a fixed size over all inputs and you scan strictly right to left, it's a finite state transduction and preserves regularity.

Finally, to get $M\_{a,b}$ from $M\_{a,0}$ we need to numerically add $b$ to each string, but that's done with a similar transducer $T\_b$ which depends on the fixed number b.

To do the same in any base, show additionally how to perform multiplication by a single digit $d$ in that base, using a transducer $S\_d$ that depends on d. With that, we can multiply by multi-digit numbers and still remain in the regular languages. Or, we can finesse this by saying that multiplication by $d$ is just repeated addition.

You wanted only hints. Each of those steps depends on a fairly complex theorem/technique, so proving those to get a complete proof will be the extra work.
> 8 votes

# Answer
I am following the idea of @vonbrand:

**Hint 1:**

Solve first for $b=0$. You might use the Myhill-Nerode Theorem.

> We define the following relation $\bar x\approx \bar y :\iff x\equiv y \mod a$. This is obviously an equivalence relation. Furthermore it is right-congruent, since if we append a digit $d$ we get $\bar x \approx \bar y \iff 10x+d \equiv 10y+d \mod a \iff \bar x d \approx \bar y d$. Finally it saturates $L$, since $L$ is the equivalence class $\[0\]$. Since $\approx$ has a finite number of classes we have by the Myhill-Nerode Theorem that it is regular. The associated FSA is minimal and has $a$ states.

**Hint 2:**

Solve the general case, reuse the automaton induced by the $b=0$ case.

> We know that the language is regular for $b=0$. Hence simply take the $a$ state FSA $M$ for the $b=0$ language. Now we construct a FSA for $L$. Assume that $b$ has $k$ digits. Then the FSA branches like a 10-ary tree of depth $k$ and contains all paths to numbers with $k$ digits. All states that can be reached with a number not in the form $ax+b$ are rejecting otherwise accepting. Finally we connect the tree-part of the FSA with the automaton $M$, according to the remainder by the division by $a$.
> 5 votes

---
Tags: formal-languages, context-free, regular-languages, integers
---