# Question
Title: Three Partition-Function Algorithms Comparison
I have implemented three algorithms codes, in Swift:

1- Polynomial coefficient:

```
 // create polynomial
func arrangePoly(ofTerms term: Int, toLength len: Int) -> [Int] {
    var a = Array(repeating: 0, count: len+1)

    for i in stride(from: 0, to: a.count, by: term) {
        a[i] = 1
    }
    return a
}
// polynomial product
func productToN(array1 a: [Int], arrayb b: [Int], toPower n: Int) -> [Int] {
    var res = Array(repeating: 0, count: n+1)

    for (pa, ca) in a.enumerated() {
        for (pb, cb) in b.enumerated() {
            if pa+pb <= n {
                res[pa+pb] += ca*cb
            }
        }
    }
    return res
}
// test code: partition of N
var p1 = arrangePoly(ofTerms: 1, toLength: N)
var res = p1

for i in 2...N {
    res = productToN(array1: res, arrayb: arrangePoly(ofTerms: i, toLength: N), toPower: N)
}
print(res[N])   // coefficient of x^N

```

2- Euler recurrence relations:

```
func eulerPartition(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            let sign = power(-1, k-1)
            sum += sign * (eulerPartition(n-(k*((3*k)-1)/2)) + eulerPartition(n-(k*((3*k)+1)/2)))
            k += 1
        }
        return sum
    }
}

```

3- Divisor sum formula:

```
// sigma(k) is the well-known sum of divisors of k
func part(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            sum += sigma(k) * part(n-k)
            k += 1
        }
        return sum / n
    }
}

```

All the three versions gives the same results for each n \>= 1, but with different efficiency. While the Euler recurrence algorithm is assumed, theoretically, to be the fastest of the three, the polynomial coefficient algorithm works the best on my core2duo laptop in spite of it is not recursively coded like the others. I am sure I have done something wrong, but I can not figure what or where.

Any idea?

# Answer
> 1 votes
Your implementation of the Euler method doesn't use memoization, so you keep computing and recomputing the same values. This is like computing the Fibonacci numbers along the following lines:

```
Fibonacci(n)
  if n = 0 or n = 1, return n
  otherwise, return Fibonacci(n-1) + Fibonacci(n-2)

```

You should modify the implementation so that after calculating `eulerPartition` for a certain $n$, if you are given the same $n$ again then you immediately return the previously calculated value.

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


# Question
Title: Question about NP problem certificates and P=NP
From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate.

My question is whether or not creating an algorithm to determine values accepted by a certificate for an NP problem can itself be considered an NP problem.

This problem is an example of what I had in mind (it's more or less a variation of SAT).

Imagine a padlock with N switches and each switch has a configuration 'UP' or 'DOWN'. The padlock can have anywhere between 1 and $2^N$ solutions (i.e. it may only accept one combination or any number of combinations up to and including all possible combinations) and both the total number of solutions and the solutions themselves are selected at random.

If there are $2^N$ solutions a solution takes $O(1)$ time to find since all inputs are valid.

However, if there is only 1 solution $O(2^N)$ time is required to find it.

If it is accepted that trying all combinations on the padlock requires $2^N$ combinations and that because the solution is random there is no way to guarantee a solution unless $2^N - 1$ combinations are tested by process of elimination.

Because the total number of acceptable solutions is not known until different candidates are tested against the certificate, the problem requires $O(2^N)$ time to solve.

To prove that the problem is solvable in NP, use an NTM to solve the problem by non-deterministically testing all valid combinations and accepting any valid solution. Takes $O(N)$ time to solve since every differing possible bit to test will branch into a new non-deterministic chain.

The certificate for the problem contains acceptable values for each 'swicth' (bit) at each location either 1 for 'UP', 0 for 'DOWN' or 'X' to accept any value at that location and takes $O(N)$ time to verify.

Is this valid?

If I'm correct and the problem above does fit in the class of NP it seems sufficient to prove that $P \neq NP$ but I'm fairly confident I made an error I'm not aware of and I'm not sure if my example can be properly classed as an NP problem.

# Answer
Your problem is in the *black box* or *oracle* setting, that is, you are given access to the input as a black box rather than explicitly. You can contrast your problem with 3SAT, in which the input is a formula. One way to solve 3SAT is to try plugging in solutions at random (or systematically) and checking whether they satisfy the formula. However, better approaches are known, and these approaches use the explicit description of the formula.

The P vs NP question is in the white box setting – concretely, $\mathsf{P} \neq \mathsf{NP}$ is equivalent to the conjecture that no polynomial time algorithm solves 3SAT. Results in black box settings are irrelevant (at least directly) to the P vs NP question.

In the black box model we can also separate P from BPP (at least for promise problems), by considering the problem of finding a zero input for a balanced Boolean function. However, for explicit inputs, it is considered likely that P=BPP. This shows that the black box setting exhibits different behavior than the white box setting.

Black box settings are common in optimization, where often we are looking for algorithms which do not rely on the exact form of the input function. For example, in submodular optimization we are given a submodular function as a black box. One method for proving lower bounds in this area is the *indistinguishability method*, in which we construct two black boxes which are identical on most inputs but have a very different optimal solution. This method is technically much easier than similar results in the white box setting (for example, in the special case of set coverage functions or cut functions), which rely on PCP theory.
> 3 votes

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


# Question
Title: Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise
> Prove that following problem is complete in NP in sense of Karp.
>
> Given: context free grammar $G$
>
> Check if $G$ generates word containing all symbols from alphabet
>
> **Remark** Above problem should be encoded as langauge over finite alphabet, although alphabet of $G$ can be arbitrarily big. You can assume that symbols of this alphabet are encoded as binary strings.

My main problem at this moment is that I don't understand **Remark**. For me, it should be attached also alphabet of grammar. Can you explain me in human language what this Remark try to say ?
To be more clear I can say that in other task with the same question, but with given regex **and alphabet of regex** I did deal with it. However, in mentioned task there was no this awkward Remark.

# Answer
> 1 votes
The remark addresses the following problem:

> How to encode context-free grammars over an arbitrary alphabet using a fixed alphabet?

Besides the alphabet, you encounter a similar problem when trying to represent non-terminals. The solution suggested by the remark is to use binary encoding. For example, the grammar

$$ S\to SA | \epsilon \\ A \to a | b | c $$

could be encoded as follows:

$$ N0; \to N0;N1; | \epsilon \\ N1; \to T0; | T1; | T10; $$

Another potential encoding is unary encoding:

$$ N0 \to N0N00|\epsilon \\ N1 \to T0|T00|T000 $$

Which encoding is used can affect the complexity of the problem. For example, problems like Knapsack and Subset-Sum are NP-hard for binary encoding, but become easy when unary encoding is used (such problems are known as *weakly polynomial*).

# Answer
> 2 votes
What the remark is trying to tell you, I think, is that the alphabet of each different grammar $G$ can grow and is not fixed.

For instance. say that you have a language $L$ that you want to reduce to your language, let´s call it $L'$, then, you are allowed to make the alphabet of the different context free grammars inside $L'$ grow as the instances inside $L$ grow. For a bigger instance a bigger alphabet

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


title: Disproving using the definition of O

text:
# Question
Title: Disproving using the definition of O
Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only.

I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some contradiction by trying to prove it is $O(\sqrt{n})$? Any help on how to answer this would be appreciated.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).

# Answer
Here is one possible definition of big O (your definition might vary in details):

> Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) \> 0$ for all $n$. We say that $f(n) = O(g(n))$ if there exists an integer $N$ and a real $C \> 0$ such that for all $n \geq N$, $f(n) \leq Cg(n)$.

Using the rules of logic, we get a definition of the *negation* of big O:

> Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) \> 0$ for all $n$. We say that $f(n)$ is not big $O(g(n))$ if for every integer $N$ and real $C \> 0$ there exists $n \geq N$ such that $f(n) \> Cg(n)$.

This is what you should prove. For each integer $N$ and real $C \> 0$ you should find $n \geq N$ such that $0.1n + 10\sqrt{n} \> C\sqrt{n}$.
> 2 votes

# Answer
You could use the limit definition of *Big-O*. Provided that the limit for both $f(x)$ and $g(x)$ exists and $g(x) \gt 0$ for all $x$, the following equivalence holds: $$ f(n) \text{ is }O(g(n)) \text{ if on only if } \exists~ c\in\mathbb{R}: \lim\_{n \to \infty}\frac{f(n)}{g(n)} = c, \text{ where } 0 \leq c \< \infty $$ (If either limit does not exist or $g$ is not positive, then $f(n)$ may or may not be $O(g(n))$, you need to use more precise criteria to find out.)

So, if $0.1n + 10\sqrt{n}$ is $O(\sqrt{n})$ then $$ \lim\_{n \to \infty}\frac{0.1n + 10\sqrt{n}}{\sqrt{n}} = \lim\_{n \to \infty}{0.1\sqrt{n} + 10} = \infty$$ which is not a constant.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Why do we use dynamic memory allocation in general and why did we use it in this particular example?
Dynamic Programming C/C++ implementation of LIS(Longest Increasing Subsequence) problem

```
/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */

int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );

/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++ )
    lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++ )
    for (j = 0; j < i; j++ )
        if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */
for (i = 0; i < n; i++ )
    if (max < lis[i])
        max = lis[i];

/* Free memory to avoid memory leak */
free(lis);
return max;
}

```

It is a code from www.geeksforgeeks.org . I have seen explanations that memory is allocated(when done dynamically) on heap, which is a free store of (very large) memory, so it makes sense to only use dynamic allocation when memory required exceeds memory of stack used for storing variables and data locally allocated in functions.

Would it make a difference if I declared array as int arr\[n\] (as n is given by user in input) and then in main function use lis(arr, n) ? If so, why? If not, what else does dynamic allocation benefit from in this case and in general?

# Answer
If you declared array as `int arr[n]` then the memory **might** be allocated on the Stack and `arr` would exist as long as the function `lis` exists, i.e., it would be allocated locally in the `lis`. `malloc` on the other hand, would allocate the memory on the Heap and the array would exist until you **explicitly** **free** it using `free`. Nevertheless, as Yuval Filmus noted, memory allocation for the variable length arrays depends on compiler implementation and environment (for example underlying environment may have no distinction between heap and stack). In addition, the GNU C Compiler allocates memory for variable length arrays on the stack.

However, regarding the time or space complexity of the algorithm, it would not make any difference. In particular, the time complexity of an algorithm has nothing to do with its implementation in a particular language.
> 1 votes

---
Tags: dynamic-programming, memory-allocation
---


title: What does $n^{O(1)}$ mean?

text:
# Question
Title: What does $n^{O(1)}$ mean?
I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.

I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.

# Answer
It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$". In other words, the function is at most $n^c$ for some constant $c$.

You can see this by directly substituting the definition of $O(1)$ in the expression. $g(n)=n^{O(1)}$ if there's constant $c$ such that, for all large enough $n$, $f(n)\leq n^{c\cdot 1} = n^c$.

This includes all polynomially-bounded functions. For example, for $n\>0$, $$n^2+3n = n^2(1+\tfrac3n) = n^{2+\log(1+3/n)/\log n} = n^{O(1)}\\,,$$ since, for $n\geq 3$, we have $1\<1+\tfrac3n\leq 2$ and $\log n\>1$, so the exponent is between $2+\log 2$ and $2$.
> 8 votes

---
Tags: asymptotics, landau-notation, notation
---


# Question
Title: Counting frequencies of Element in an array
Given an array of size $N$. I need to find the count of values in range $\[L, R\]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).

For eg- \begin{align\*} A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\ L&=0,\ R=3\\,, \end{align\*} the answer would be 1 (1,1,1) and 2 (2,2,2).

I tried it by doing the following:

```
  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

```

But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.

How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?

**Update** :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.

```
add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR <= R:
    add(currentR)
    currentR++
  while currentR >R+1 :
    remove(currentR)
    currentR--
  output answer

```

I need to calculate for many pairs of L,R .So I need an efficient algorithm. The above algorithm seems to do so.

But How do I differentiate the contiguous triplets here ?

# Answer
> 1 votes
Maybe this:

```
answer = 0
lastVal = -1    //some value not inside [L,R]
count = 0
for i in {l..r}:
  if (array[i] != lastVal)
     count = 1
     lastVal = array[i]
  else
     count++
     if (count == 3)
        count = 0
        answer++

```

Edit: This code assumes that the set (1,1,1,*1*) is counted as one triplet not two. i.e.: (1,1,1) and (*1*), not (1,1,1) and (1,1,*1*)

# Answer
> 0 votes
In a language with good sequence facilities, such as Clojure, we can answer such questions directly:

```
(defn triples-in-range [low high coll]
  (->> coll
       (partition 3 1)
       (filter #(apply = %))
       (map first)
       (filter (set (range low (inc high))))))

```

For example,

```
(def data [1,1,1,2,2,1,5,1,1,2,2,2,5,5])

(triples-in-range 0 3 data)
;=> (1 2)

```

There are faster ways to do this. It's an example of a search that would benefit from something like the Knuth-Morris-Pratt algorithm.

The above is working code. You don't have to get the details to understand that the accurate and concise expression of an algorithm in terms of telling abstractions blows away oceans of speculation.

# Answer
> 0 votes
Here is a solution in sudo code.

set count =0;

get current element in array: x move to next element: y check if next element is equal to previous element: is x=y if true do count ++ if false reset count to 0. when count = 2: save that element in your result.

You can format your output the way you want. Here i put the output in a string result.

This is in Java

```
    int[] data  = new int[]{1,1,1,2,2,1,5,1,1,2,2,2,5,5,4,7,7,7};
    int count   = 0;
    int L       = 0;
    int R       = 3;

    String result="";

    for (int i = 0; i < data.length-1; i++)
    {
        if((data[i] == data[i+1]) && (data[i]>L && data[i]<R) )
        {
            count = count+1;
        }
        else
        {
            count =0;
        }

        if(count >= 2) //AT LEAST 3 times in successive positions
        {
            result = result +","+data[i]   ;
        }
    }

    if(result.length()>0)
    {
        result = result.substring(1);
    }
    else
    {
       result = "No values in the range are repeated!";
    }
    System.out.println(result);

```

# Answer
> 0 votes
If you need to execute multiple queries on this, you could do a mixture of what Nathaniel and David Richerby suggested. First preprocess the array and determine which elements are the last element of a triple. You could return a new array which if index $i$ is true, means element $i$ is the third element of a triple. This takes $O(n)$.

```
find-third-elements-in-triples(arr):

  thirds = new boolean array same length as arr, initialized all to false

  c = 1
  for i in {1 ... length(arr)}:
    if arr[i] != arr[i - 1]:
      c = 1
    else:
      c += 1
      if c >= 3:
        thirds[i] = true

  return thirds

```

A side note, for input `[1,1,1,1]`, it would return `[f,f,t,t]`, meaning this includes overlapping triples. It also can satisfy the "repeated at least three times" stipulation.

Now from their, each query is relatively simple to handle. Iterate from $l+2$ (the third element) to $r$ and see how many elements are the third element of a triple and this will tell you how many triples are in the segment $\[l, r\]$. This will take $O(r-l) = O(n)$ time.

```
query(arr, l, r):

  // You could keep the 'third-element' array as a single instance array of some sort
  if thirds == null:
    thirds = find-third-elements-in-triples(arr)

  count = 0
  // start at the third element
  for i in {l+2 ... r}:
    if thirds[i] and !thirds[i+1]:
      count += 1

  return count

```

Note: you can remove the `and !thirds[i+1]` code if you're treating overlapping triples as separate triples. Otherwise that check basically says, "we're not at the end of our contiguous sequence yet, so we're not ready to increase the count".

To get faster than $O(r-l)$ for each query, you could look into creating a Fenwick Tree out of the `thirds` array to make queries in $O(\log n)$. You would treat `false` as 0 and `true` as 1, then calculate interval sums to find out how many `thirds` are in your interval.

# Answer
> 0 votes
If you want to stick to array data-structure then following is a java code that I wrote using `data`array from TimeTrax's answer.I have provided comments for understanding and I hope you can implement it in your preferred programming language.

```
int[] data  = new int[]{1,1,1,1,1,1,1,2,2,1,5,5,5,3,1,1,2,2,2,5,5,4,7,7,7};  //creating an array
String result="";                         //creating a string for printing final output
for (int i=2;i<data.length;i++){          // loop over the array, start from the third element

    if(data[i-2]==data[i]){               //if the first element matches the third element
        if(data[i-1]==data[i]){           //and if the second element matches the third element
            result=result+data[i]+",";    //then append the third to the list of triplets which is the result string
            i=i+2;                        //and move the pointer to the sixth element for checking fourth,fifth and sixth element for possibility of next triplet and so on
        }
    }
}

System.out.print(result);                 // printing out result string

```

**The Output is as follows**

`1,1,5,2,7,`

Each number is a representation of a its triplet

The complexity of the above code however remains in **O(n)**. I have made a little optimization so that the more triplets you have in comparison to the size of the array the lesser will be the running time of the loop.The best it can give is when you have all triplets in your array(i.e. The loop will run 1/3 rd times the size of your array).

If you think you want more optimization then consider @ryan's suggestion about Fenwick Tree

# Answer
> -1 votes
```
answer = 0
last = null
count = 0
foreach value in array
   if (last != null)
       if (value == last)
          count++
       else
          if count >= 3 then answer++
          count = 0
   last = value
if count >= 3 then answer++

```

---
Tags: algorithms, arrays
---


# Question
Title: Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm?
If the complexity of an arbitrary algorithm to solve any NP problem after analysis is $\Theta(2^\sqrt{n})$ then is this algorithm considered as "good" and practical algorithm?

I know that in algorithm analysis and computational complexity theory every algorithm with any polynomial complexity is considered as "good" and practical algorithm, although in mathematics and calculus $2^\sqrt{n}$ is**n't** polynomial by definition, but so $n\log n$, but $\Theta(n\log n)$ counts as "good" and practical algorithm to solve any NP problem.

I have already graphed the functions: $x, x\log\_2x, x^2, 2^\sqrt{x}$ and $x^3$ by using some online function plotter, and for some **large** $x$, it appears that $ x^3\>2^\sqrt{x}\>x^2\>x\log\_2x\>x$

So I think that $\Theta(2^\sqrt{n})$ is practical and "good" as $\Theta(n\log n)$ is, although both of them are not polynomial by definition.

Am I right?

# Answer
Complexity is how an algorithm increases its number of steps in comparison to $n$ when we scale $n$ to a large value.

For very small $n$ , an algorithm with complexity $\Theta(2^\sqrt{n})$ can behave nearly as good as an algorithm running in polynomial time.But if we increase the $n$ , then certainly the algorithm with polynomial time will give much faster results.That's how algorithms are compared.One important thing to remember is that your $n$ is a variable related to input size and if this occurs as a power of something in time complexity then you can be sure that the algorithm is going to take a lot of time for large values of $n$.

**$\Theta(2^\sqrt{n})$ is not as good as $\Theta(n\log n)$**
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Why do we need Gibbs sampling (and MCMC)?
I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.

Maybe my alternative suggestion would sound somewhat naive (even stupid) but why can't we just draw a number in random from $\[0,M\]$ for some sufficiently large enough $M$. Then, we divide the range to buckets with appropriate sizes according to the distribution.

This will be a true sampling of $\pi$.

One could argue that my suggestion demands a PRNG, but Gibbs Sampling uses randomness too when deciding the next state from the neighbors of the current state.

So for a reasonable distribution, wouldn't my suggestion work way better? It's essentially $O(1)$ and accurate.

# Answer
> 3 votes
The approach you described sounds like the common algorithms for sampling. If by reasonable distribution, you mean a smallish finite discrete distribution, then see the following references for how to do that. You would be right that Gibbs sampling would be a worse choice, probably, when these methods apply.

https://stats.stackexchange.com/questions/26858/how-to-generate-numbers-based-on-an-arbitrary-discrete-distribution

https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/

For many problems it is computationally infeasible (or impossible in the case of infinite state spaces) to enumerate all possibilities, nor even choose a sufficiently large M. (The M you describe is actually the partition function, i.e., the sum of all the un-normalized probabilities of all events). For instance, imagine sampling from an Ising model, which has 2^N states, where N is the number of binary variables.

# Answer
> 3 votes
It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time.

Further, sampling from a Markov chain allows you to sample without having to construct the probability distribution explicitly or even the state space, explicitly. For example, how do you propose to randomly sample matchings in a graph by your method, even uniformly? You'd need to first construct the set of all matchings (of which there can be exponentially many), then select one. And note that constructing the set of matchings implies being able to count them, which is **#P**-hard, so very unlikely to be doable efficiently. With a Gibbs sampler, you just run a Markov chain for polynomially many steps and you have yourself a matching chosen uniformly at random.

# Answer
> 2 votes
It's because we're not sampling integers. If we were sampling integers, and the distribution were given explicitly, you are right, there would be simpler methods. But instead we often want to sample from a set of objects, where each object is some more complicated thing (it's not just an integer), and there's no clear way to do that.

---
Tags: algorithms, randomness, sampling, markov-chains
---


# Question
Title: Show that (2,3)-satisfability is np-complete
First of all, I introduce *(2,3)-satisfability*:
Formulas are in CNF form, the special property is that each clause has $2$ or $3$ literals. Formula is satisfied iff only and only if there exists valuation such that:

* clauses with two literals are treated normally - it sufficient to satisfy one literal (also $2$ literals can be satisfied).
* clauses with three literals are treated specially - there are must be satisfied exactly $2/3$ of literals (no more, no less)

Show that checking if such formula is *(2,3)-satisfable* is np-complete.
I have no idea how to do it. Obviously, it is easy to show that it is in np, but hardness doesn't seem that easy to show.

# Answer
1-in-3-SAT is NP Complete: given a set of clauses, find a value assignment such that exactly 1 literal in each clause is made true (http://cs.nyu.edu/courses/fall14/CSCI-UA.0310-001/1in3sat.pdf).

Reduction from 1-in-3-SAT: negate every literal in every clause of the 1-in-3-sat instance. Now exactly two literals need to be made true in each clause instead of one to have an equivalent solution set. This is your (2,3)-satisfiabililty instance. We don't even need the clauses with two literals.

Example

```
1-in-3-SAT instance: (a,-b,c), (a, b, -c), (d, e, f)
equivalent (2,3)-satisfiability instance: (-a,b,-c), (-a, -b, c), (-d, -e, -f)

```
> 4 votes

# Answer
Please note that $$(x\_1 \vee x\_2 \vee x\_3) \text{ is satisfable in 'normal sense' iff } \\ (x\_1 \vee x\_4 \vee x\_5) \wedge (x\_2 \vee x\_6 \vee x\_7) \wedge (x\_3 \vee x\_8 \vee x\_9)\\ \wedge (x\_5 \vee x\_7 \vee x\_9) \\ \text{is 2-satisfable} $$ where are $x\_4, x\_5, x\_6, x\_6, x\_8, x\_9$ are variables that doesn't occur in a formula (they are just new variables).
> 2 votes

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


title: Hyperexponentiation modulo a prime

text:
# Question
Title: Hyperexponentiation modulo a prime
Let $a\uparrow^{n} b $ denote the indexed version of Knuth's up-arrow notation ($a \uparrow\uparrow \dots \uparrow b$ with $n$ arrows), with $a, b, n$ positive integers.

Is there a generalized algorithm to compute $a\uparrow^{n} b$ modulo a prime efficiently? How does the complexity of such an algorithm depend on $n$? What if we restrict $a$ and $b$ to also be prime, or if we remove the requirement for $p$ to be prime?

# Answer
Maybe.

Consider the problem of calculating $a^{a^b} \bmod p$. What we do here is calculate $x = a^b \bmod (p-1)$, which is the exponent we need to do $a^x \bmod p$, which is our answer. This is due to Fermat's Little Theorem, which states that for prime $p$:

$a^{p-1} \equiv 1 \bmod p$

You may notice that this intermediate exponential is smaller. Also, given a composite modulus, we can break it into factors, calculate for each of the those factors separately and combine with the Chinese Remainder Theorem. So the modulus can shrink pretty fast.

This means that a power tower can only grow to a certain size, beyond which the modulus used to calculate the upper parts of the tower is zero, so the part of the tower above that threshold has no effect on the result.

So tetration at least may be easier than it would at first appear. That said, there is also the requirement that you can swiftly factorize p, which makes large p difficult to work with.
> 2 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Is a finite Solomonoff learner worse than human learning?
An elegant program for a bitstring is the shortest program on a universal Turing machine that outputs this bitstring. According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.

Solomonoff induction uses the elegant program for a bitstring to predict the next digit. This is a universal prior given the minimal assumption the output is generated by a Turing machine.

We can use this insight to build a machine learning algorithm called a finite Solmonoff learner. The difference between a finite Solomonoff learner and the original Solmonoff induction algorithm is the finite learner does not have access to all elegant programs. There is no algorithm that can generate all the elegant programs, so the elegant programs the finite learner can use must be stored in memory. With a finite amount of memory, there is a limit to the elegant programs that can be stored and consequently used by the finite learner for prediction.

The limit exists because there are a finite number of elegant programs of a certain length L. When the bitstring of 1s becomes long enough, it is not possible for there to be an elegant program representing the bitstring to be of length L or shorter. If L is the amount of memory available, then eventually the elegant programs will all be longer than L, and none will fit in memory.

Now let's assume we have a very long string of 1s, and we remove one digit to make a prediction problem.

As a concrete example, our bitstring is:

11111111111111111111

We remove a 1 at random:

111111111111111\_1111

The learner must figure out the most likely digit to go in the empty spot.

For a given amount of memory we can make the bitstring of 1s long enough that its elegant program cannot fit in memory. In this case, the finite Solomonoff learner will not be able to access the elegant program for the bitstring, and will thus be incapable of predicting the digit that goes in the empty slot.

To continue the example, assume the elegant program that generates the 1s is:

10001011

Furthermore, the amount of memory available is 7 bits. Consequently, the 8 bit elegant program cannot be stored in memory, and the finite learner cannot figure out what goes in the empty slot.

On the other hand, regardless of how long the bitstring of 1s becomes, a human will have no problem identifying the missing digit. A human has finite memory and cannot access all elegant programs to make predictions. Despite having the same handicap as a finite learner, the human can outperform the finite learner infinitely often.

Does this demonstrate Solomonoff learning is less powerful than human learning?

# Answer
> 3 votes
Your suppositions are wrong. A finite Solomonoff learner *can* learn the all-1's string. There does exist a learning algorithm that can output a program for the all-1's string.

Consequently, this example does not demonstrate that Solomonoff learners are necessarily worse than a human being. They might be; but this example doesn't prove that.

For instance, consider the following learning algorithm: if the inputs is all-1's, then output a program that only outputs 1's (e.g., 10001011 in your example), otherwise do something arbitrary. This is a trivial algorithm, but it demonstrates that there does exist a learning algorithm that can learn that sequence. In other words, you've given an example of an input sequence that both a human can learn and a finite Solomonoff learner can learn.

What you *might* have shown is that if we restrict the learner to a very limited amount of memory, then the learner might not be able to learn some things that a human can. But that's a rather uninteresting conclusion. Of course we know that if you severely restrict the memory of the computer, that limits what it can compute. For instance, if we limit the memory of the algorithm to only 7 bits, then the algorithm must act like a finite-state machine with at most 128 states, which severely limits the patterns it can find. A human can learn sequences that can't be recognized by a finite-state machine with 128 states. That's not surprising, and doesn't really have any interesting implications for whether finite Solomonoff learners are worse than human learning.

There's no point in comparing a human to a computer algorithm that has been massively handicapped. To make the comparison interesting, you must allow the computer algorithm to have reasonable access to the resources that any computer would have; otherwise you have trivialized the question. This means allowing the computer learner a non-trivial amount of memory. And once you do that, the learner no longer has any difficulties with your sequence.

---

There are other issues in your post. If you are assuming that the only possible approach is to try all possible algorithms until you find one that works, that's not the case. More seriously, the problem of "given a sequence, find the elegant program for it" is not computable, so if you require the learner to find the shortest possible program, you've created an impossible problem. Finally, where you say that "According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.", but that's not correct. What *is* true is that changing the universal Turing machine will change the length by only a constant... but if you care about constants, that might be important.

---
Tags: machine-learning, computer-vs-human
---


# Question
Title: Is this a correct approch of finding expected runtime of an algorithm?
Consider two algorithms; we analysis their run time only by counting the number of comparisons

```
TwoMax1(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > L:
             S = L
             L = A[i]
         else
            if A[i] > S
                S = A[i]
    return (L,S)

 TwoMax2(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > S:
            if A[i] > L:
             S = L
             L = A[i]
            else
                S = A[i]
    return (L,S)

```

Here is my approach for the first algorithm:

(1) define our sample space. Since the returned output is a pair, maximum and second maximum could be anywhere in the array. For each maximum, there are $(n-1)$ possible index for second maximum, and we have $n$ possible index for the maximum value; So sample space: $S = \\{(A\[0\],A\[1\]),(A\[0\], A\[2\]),(A\[0\],A\[3\]),\dots\\}$ and so on.

Define an indicator $I\_i = 1$ iff $A\[i\] \> \max \\{A\[0\], A\[1\], \dots, A\[i-1\]\\}$.

The total expected comparison of comparing to maximum would be $$\mathbb{E} (\sum\_{i=0}^n I\_i) = \sum\_{i=0}^n \mathbb{E}(I\_i) = \mathrm{Prob}(A\[i\] \> \max \\{A\[0\], A\[1\],\dots, A\[i-1\]\\}) = \frac{n+1}{2}.$$

where $$\mathrm{Prob}(A\[i\] \> \max \\{A\[0\], A\[1\], \dots, A\[i-1\]\\}) = \frac{i}{n}$$ because under the sorted array, we have $\frac{i}{n}$ chance of choosing a integer that greater than $A\[0\], A\[1\],\dots,A\[i-1\]$.

Now similar, the total expected comparison of comparing to second maximum would be same; and we sum two parts together up is $n+1$.

Is this a good way of approaching? If so, I also want to know some other ways of doing it, for example, define a different random variable to solve the second function.

# Answer
First of all, notice that in `TwoMax1`, $A\[i\]$ is *always* compared to $L$. This already gives you $n$ comparisons. If $A\[i\]$ is not the current maximum, then it is compared to $S$. This happens with probability $1-1/i$ (see below). Therefore the total expected number of comparisons is $$ n + \sum\_{i=1}^n \left(1 - \frac{1}{i}\right) = 2n - H\_n = 2n - \log n - \gamma + O\left(\frac{1}{n}\right). $$

In `TwoMax2`, $A\[i\]$ is *always* compared to $S$. Again, this gives you $n$ comparisons. If $A\[i\] \> S$, which happens when $A\[i\]$ is one of the two maximal elements, then $A\[i\]$ is compared to $L$. When $i = 1$, it is always the case that $A\[i\] \> S$, and otherwise it happens with probability $2/i$. Therefore the expected number of comparisons is $$ n + 1 + \sum\_{i=2}^n \frac{2}{n} = n + 2H\_n - 1 = n + 2\log n + \gamma - 1 + O\left(\frac{1}{n}\right). $$

The second algorithm thus makes roughly half as many comparisons than the first algorithm.

---

You mention that the sample space consists of all *outcomes*. But in fact, the sample space consists of all *inputs*, or in your case, all input permutations. You are analyzing the algorithm with respect to the uniform distribution over this sample space.

Also, the probability that $A\[i\] \> A\[1\],\ldots,A\[i-1\]$ (numbering elements from zero) is not $i/n$ (consider for example the case $i=1$!) but rather $1/i$. The reason is that if $A\[1\],\ldots,A\[n\]$ is a random permutation then $A\[1\],\ldots,A\[i\]$ is a random permutation of $\\{A\[1\],\ldots,A\[i\]\\}$. In particular, $A\[i\]$ is a random element of $\\{A\[1\],\ldots,A\[i\]\\}$, and so it equals the maximum with probability $1/i$.
> 1 votes

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


# Question
Title: Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT
A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:

1. There exists a clause where all variables are unsatisfied.
2. Unfixing any variable makes every clause contain at least one free variable.

Particularly for 2-SAT and 3-SAT is their number bounded by polynomial?

If yes, then how can the number of such assignments in SAT be reduced from $2^m$ to polynomial, when applying Tseytin transform? $m$ is number of variables.

# Answer
> 3 votes
Yes, the number of minimal unsatisfiable partial assignments is upper-bounded by a polynomial.

Suppose there are $n$ clauses. There are $n$ ways to choose which clause is unsatisfied, call it $C$. Suppose clause $C$ mentions variables $x\_i,x\_j,x\_k$. Then the partial assignment must assign values to $x\_i,x\_j,x\_k$ but not to any other variable. (If it assigned a value to $x\_\ell$, then unfixing $x\_\ell$ would leave clause $C$ without a free variable, which violates the second requirement.) There is only one way to assign values to $x\_i,x\_j,x\_k$ to make clause $C$ unsatisfied. So, there are at most $n$ minimal unsatisfiable partial assignments.

---
Tags: satisfiability, counting
---


# Question
Title: Proof for "It is my contention that these operations include all those which are used in the computation of a number"
In his famous paper, Turing briefly describes his machine and then states (p. 232) (emphasis mine):

> **It is my contention that these operations include all those which are used in the computation of a number.** The defence of this contention will be easier when the theory of the machines is familiar to the reader.

Does this mean that all numbers that could ever be computed by a machine or a human being can be computed by a Turing Machine?

If yes, what proof has Turing, beside "It is my contention"?
Does Turing defend this contention later on, in the same paper or elsewhere?

# Answer
A contention is something that one asserts to be true. Turing's contention here is essentially the Church–Turing thesis: that Turing machines can compute everything that can be reasonably computed. This isn't something that can be proven without a definition of "reasonably computed". But, even if one were to define that term, it would be arguable that the definition wasn't a good one and that, again, isn't something that can be proven.

Turing's paper includes a lot of material about computable sequences of numbers and also a sketch proof that Turing machines and the lambda calculus are equally powerful. That constitutes quite a lot of evidence for the original contention, though I didn't notice Turing explicitly mentioning this when I skimmed the paper just now.

In particular, one might choose to define "reasonably computable" as meaning "computable by any possible physical system." Well, Turing machines can simulate every physical process we're aware of, including quantum mechanics. But, of course, we can't prove that there are no physical processes we don't know about yet that can't be simulated by Turing machines.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Why is it so difficult to eliminate dead loops?
I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the code revealed that it would obviously terminate.

Investigating this further, I found it was *extremely easy* to write very short programs for which basically every major compiler will emit a bunch of dead code. (Side note - it's worse when using a C++ compiler - AFAIU 'forward progress' is guaranteed so even infinite loops should be able to be removed!)

```
// when m <= 0 this will never enter the loop, so will terminate
// when n >= m, j will be incremented each time through the loop until
// j == m, so the loop will terminate
void naught(int n, int m) {
    int i = 0, j = 0;
    while(j < m) {
        if (i < n) {
            i++;
            j++;
        }
    }
}

// each two loop iterations the value of i gets incremented by 3, and
// then decremented by 1. eventually it will be greater than or equal
// to the value of n and so the loop will terminate. We can ignore
// overflow since it is undefined; a language with unbounded integer
// types would also terminate.
void zip(int n) {
    int i=0;
    while (i < n) {
        if (i % 2 == 0)
            i += 3;
        else
            i--;
    }
}

// each time through the loop the value of i is increased; so it will
// terminate. same comments about undefined behaviour / unbounded types
// apply here
void nothing(int n) {
    int i=2;
    while (i < n) {
        i *= i;
    }
}

// on the first iteration through the loop i becomes equal to n + 1,
// so it will terminate. ditto on undef / unbounded
void zilch(int n) {
    int i=0;
    while (i < n) {
        i += (n / (i + 1)) + 1;
    }
}

// if i <= 0 we never enter the loop. otherwise, on the first iteration,
// i gets divided by i + 1 which equals zero from rounding.
// ditto on undef / unbounded
void nada(int n) {
    int i=n;
    while (i > 0) {
        i /= i + 1;
    }
}

```

Is there some fundamental reason that compilers fail in these simple cases? This lack of optimization does not seem to be compiler-specific, or language specific, so I thought it might be because of lack of research (hence posting here). Has there been much research in this area? When a compiler sees the snippets above, what are the obstacles in its way that prevent it from removing the code?

To my human brain, the "obvious" thing to do would be to work out where the loops terminate and where not, and replace the entire thing with a simple if statement. If optimizing for C++, I would immediately remove all the loops since forward progress is guaranteed. Why can't the compiler do the same?

Edit:

Maybe I should have been more clear in my question; I am aware that the problem is undecidable in *general*, but to me these seem like relatively "easy" examples (especially in a C++ compiler, where AFAIU they should all be able to be removed). Optimization in general is an undecidable problem but it has not stopped optimizers from being written. I am interested whether there has been any research in this area.

# Answer
The conceptual problem here is that dead code elimination is not computable. That is, we know that there is no algorithm that can remove all instances of dead code.

Of course, tools can be created that recognize some instances of dead code and remove them. Which patterns to look for is a matter of taste and skill of the tool creator; it's better to be conservative and err on the site of not breaking things. Language semantics play a huge role as well. I don't think there are overarching conceptual issues there, but I could be wrong.

There may be language-specific subtleties at work that prevent elimination of apparently dead code. For instance, a Java compiler can never remove a private method that is never called from within the class -- it can be executed using reflection. Such special cases are beyond the scope of this site, and best discussed one by one on Stack Overflow.

In the end, I expect there to be trade-offs (as there always are): how much time do you spend on developing the optimizer, how much time do you spend during compilation, for what gain? Maybe an optimization that often creates more efficient code occasionally creates some dead code, which you are willing to accept.
> 5 votes

---
Tags: compilers, program-optimization
---


title: Big Oh notation and selection

text:
# Question
Title: Big Oh notation and selection
I wanted to know something about selection and Time complexity,

for example if I had the f.f.g java code:

```
public List<String> sort(int n, List<String> ob){
 if(n == 1){
    return binarySort(ob)
 else{
    return selectionSort(ob)
}

```

I know this is a weird example but I feel it should help me understand what to do when you have selection at the extreme.

How does one go about finding the big oh of the algorithm above? Please note you don't have to go into detail of explaining how big oh found for binary and selection sort.

# Answer
> 2 votes
The complexity is defined for $n$ growing to infinity, and the behavior for small $n$ does not matter. (Just like the limit of a sequence does not depend on the first terms).

So the complexity of your snippet is that of `selectionSort(ob)`. And this would still hold with a condition like $n\<10^{20}$.

# Answer
> 0 votes
First, note that we measure things in terms of the length of the input, and we traditionally call that quantity $n$. So let's not have an input called $n$. Also, sorting strings is awkward, since you need to take into account the complexity of determining the order of two strings, which can't be done in constant time. So, let's get rid of those issues by rewriting the code as

```
function sort (int p, int A[])
  if p == 1
      return binarySort (A);
  else
      return selectionSort (A);

```

Also, note that there's no such thing as "the big-O of an algorithm". Big-O is a notation for comparing the growth rate of mathematical functions: it's a way of writing that one mathematical function (e.g., $f(n)=n$) grows slower than another mathematical function (e.g., $g(n)=4n^2+n\log n$), along with a definition of what "grows slower" means. But it doesn't even make sense to ask "What is the big-O of this mathematical function?" For any function $f$, there are infinitely many functions $g$ such that $f=O(g)$. For example, if $f(n)=3n+6$, all of the following statements are true: $f=O(n)$, $f=O(2n)$, $f=O(n/\pi)$, $f=O(n^6)$, $f=O(2^{4n-6}+\log\log n)$, ... If all of this seems needlessly pedantic, suppose somebody asked you "Hey, what's your less than?" and it turned out they actually wanted your height rounded up to the next centimetre.

So what are you actually looking for? You're probably looking for the asymptotic worst-case running time of your algorithm. Aha, but now the clue is in the name. You just need to consider what is the worst-case running time of the algorithm, for each $n$, and look at how that behaves as $n$ gets large. Well, I don't know what you mean by "binarySort" but the answer is that the worst case for your function `sort` is whichever is the larger of the asymptotic worst-case running time of `binarySort` and of `selectionSort`.

# Answer
> 0 votes
Since there can be a case where almost all of the times `n!=1` condition is true $-$ which would be a worst case scenario (considering that **Selection sort** has a complexity $O(n^2)$ as compared to **Binary sort** which has complexity $O(n \log n)$). We can generalize the complexity to be $O(n^2)$ for **worst case**.

If you think that the chance of `n!=1` being true has very little probability then in an **average case**, complexity of your code will be that of **Binary sort** i.e. $O(n \log n)$

Time complexity is mostly considered for **worst case**, however there are popular algorithms like **quicksort** which are preferred because of very less likely-hood of a **worst case** to happen and their good **average case** complexity.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Why is the inapproximability $2^{n^\epsilon}$?
Many inapproximability factors are $2^{n^\epsilon}$. I don't know why this is **2** instead of 3, 4, ..., etc.

To be precise, given a problem,

theorem 1 says: It's NP-hard to approximate the problem to $2^{n^\epsilon}$ for any $0 \leq \epsilon \< 1$;

theorem 2 says: It's NP-hard to approximate the problem to $3^{n^\delta}$ for any $0 \leq \delta \< 1$.

Can we say theorem 2 is tighter?

I know that given $\delta \< 1$, we can find $\epsilon \< 1$ such that $3^{n^\delta} \in \mathcal O(2^{n^\epsilon})$. However, the definition of approximation factor is not in asymptotics. We should get $3^{n^\delta} \leq 2^{n^\epsilon}$ if we want to say the two theorems are actually same.

# Answer
> 4 votes
The two theorems are equivalent. You can write $$ 3^{n^\delta} = 2^{\log\_2 3 \cdot n^\delta} = 2^{n^{\delta + \frac{\log \log\_2 3}{\log n}}} = 2^{n^{\delta + o(1)}}. $$ In particular, for any $\delta' \> \delta$ there exists $N$ such that $3^{n^\delta} \leq 2^{n^{\delta'}}$ for all $n \geq N$. Conversely, $3^{n^\delta} \geq 2^{n^\delta}$.

Hardness of approximation results are only about "large enough $n$". Every problem can be solved exactly in polynomial time (even *constant* time) for all inputs of size at most $N$, for any *fixed* $N$.

---
Tags: complexity-theory, asymptotics, np-hard, approximation
---


# Question
Title: Does the transitivity of big-O notation hold for asymptotically nonnegative functions?
I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then

$$ f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(n) = O(h(n)) $$

However, I don't see why this wouldn't also be valid if you just required $f(n)$ and $g(n)$ to be asymptotically nonnegative.

Edit: Here is the definition of $O$ used in the book:

$$ \begin{aligned} O(g(n)) = \\{f(n):&\text{ there exist positive constants $c$ and $n\_0$ such that}\\ &0 \le f(n) \le cg(n) \text{ for all } n \ge n\_0 \\} \end{aligned} $$

# Answer
Suppose $f(n)$, $g(n)$ and $h(n)$ are asymptotically non-negative functions such that $f(n) = O(g(n))$ and $g(n) = O(h(n))$.

Then, by definition, there exist positive constants $c\_1, c\_2, m\_1, m\_2$ such that

$$ 0 \le f(n) \le c\_1 g(n) $$

whenever $n \ge m\_1$ and

$$ 0 \le g(n) \le c\_2 h(n) $$

whenever $n \ge m\_2$.

Choose $c = c\_1 c\_2$ and $n\_0 = \max\\{m\_1, m\_2\\}$. Note that both $c$ and $n\_0$ are positive. Then, whenever $n \ge n\_0$, we have

$$ 0 \le f(n) \le c\_1 g(n) \le c\_1 c\_2 h(n) = c h(n) $$

which implies that $f(n) = O(h(n))$.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
Classical computer **always** requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, **but** can quantum computer do that in $\Theta(\log n)$ time?

Given that $a$ is an infinite sequence of natural numbers defined either iteratively or recursively by some math formula and $a\_i$ is an arbitrary natural number, an element of the infinite sequence $a$, for any arbitrary index $i \in \mathbb{N}.$

Then to compute the sum of the first $n$ natural numbers of the infinite sequence $a$ or in other words to compute $\displaystyle \sum\_{i=1}^{n} a\_i$

Classical computer **always** requires $\Theta(n)$ time to do that, but what about quantum computer? How much time does quantum computer requires? Can quantum computer do this computation in $\Theta(\log n)$ time?

Please assume that computation of $a\_i$ for any index $i \in \mathbb{N}$ requires no longer than $\Theta(1)$ time.

# Answer
> 5 votes
No, a quantum computer can't sum $n$ outputs from a black box function in $O(\lg n)$ queries.

For example, you could use magic summing power to easily do asymptotically better than Grover's algorithm at searching for solutions to a predicate. Except Grover's algorithm is proven to be asymptotically optimal. Contradiction.

Also, magic summing would trivially prove that $NP \subseteq BQP$. To determine if problem X has a solution or not, you'd simply sum up the outputs of the black box "if input is a solution for problem X then output 1 else output 0".

---
Tags: complexity-theory, time-complexity, runtime-analysis, quantum-computing
---


title: A d-ary heap problem from CLRS

text:
# Question
Title: A d-ary heap problem from CLRS
I got confused while solving the following problem (questions 1–3).

### Question

> A *d*-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have *d* children instead of 2 children.
>
> 1. How would you represent a *d*-ary heap in an array?
> 2. What is the height of a *d*-ary heap of *n* elements in terms of *n* and *d*?
> 3. Give an efficient implementation of EXTRACT-MAX in a *d*-ary max-heap. Analyze its running time in terms of *d* and *n*.
> 4.  Give an efficient implementation of INSERT in a *d*-ary max-heap. Analyze its running time in terms of *d* and *n*.
> 5.  Give an efficient implementation of INCREASE-KEY(*A*, *i*, *k*), which flags an error if *k* \< A\[i\] = k and then updates the *d*-ary matrix heap structure appropriately. Analyze its running time in terms of *d* and *n*.

### My Solution

1. Give an array $A\[a\_1 .. a\_n\]$

$\qquad \begin{align} \text{root} &: a\_1\\ \text{level 1} &: a\_{2} \dots a\_{2+d-1}\\ \text{level 2} &: a\_{2+d} \dots a\_{2+d+d^2-1}\\ &\vdots\\ \text{level k} &: a\_{2+\sum\limits\_{i=1}^{k-1}d^i} \dots a\_{2+\sum\limits\_{i=1}^{k}d^i-1} \end{align}$

**My notation seems a bit sophisticated. Is there any other simpler one?**
2. Let *h* denotes the height of the *d*-ary heap.

Suppose that the heap is a complete *d*-ary tree $$ 1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log\_d\[n{d-1}+1\] - 1 $$
3. This is my implementation:

```
EXTRACT-MAX(A)
1  if A.heapsize < 1
2      error "heap underflow"
3  max = A[1]
4  A[1] = A[A.heapsize]
5  A.heap-size = A.heap-size - 1
6  MAX-HEAPIFY(A, 1)
7  return max

MAX-HEAPIFY(A, i)
1  assign depthk-children to AUX[1..d]
2  for k=1 to d
3      compare A[i] with AUX[k]
4      if A[i] <= AUX[k]
5          exchange A[i] with AUX[k]
6          k = largest
7  assign AUX[1..d] back to A[depthk-children]
8  if largest != i
9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )

```

* The running time of MAX-HEAPIFY:

    $$T\_M = d(c\_8\*d + (c\_9+..+c\_13)\*d +c\_14\*d)$$ where $c\_i$ denotes the cost of *i*-th line above.
    * EXTRACT-MAX: $$ T\_E = (c\_1+..+c\_7) + T\_M \leq C\*d\*h\\ = C\*d\*(log\_d\[n(d-1)+1\] - 1)\\ = O(dlog\_d\[n(d-1)\]) $$

**Is this an efficient solution? Or there is something wrong within my solution?**

# Answer
> 10 votes
1. Your solution is valid and follows definition of *d*-ary heap. But as you pointed out your notation is a bit sophisticated.

You might use those two following functions to retrieve parent of *i*-th element and *j*-th child of *i*-th element.

$\text{d-ary-parent}({\it i}) \\ \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\ \ \ \ \ {\bf return}\ d(i-1)+j+1$

Obviously $1 \le j \le d$. You can verify those functions checking that $\text{d-ary-parent}(\text{d-ary-child}(i,j)) = i$

Also easy to see is that binary heap is special type of $d$-ary heap where $d=2$, if you substitute $d$ with $2$, then you will see that they match functions PARENT, LEFT and RIGHT mentioned in book.
2. If I understand your answer correctly you use a geometric progression. In your case you get go $h = log\_d(n\\,d-1+1) - 1$, which is obviously $\log\_d(n\\,d) - 1 = \log\_d(n) + \log\_d(d) - 1 = \log\_d(n) + 1 - 1 = \log\_d(n)$, which in fact is a valid and correct solution. But just for sake of handling constant fluctuations you might wanna write $\Theta(\log\_d(n))$.

The reason for this is that some heaps might not be balanced, so their longest path and shorthest path migt vary by some constant $c$, by using $\Theta$ notation you eliminate this problem.
3. You don't need to re-implement procedure given in textbook, but you must alter it a bit, eg assigning all children to $AUX$ table using given $\text{d-ary-parent}$ and $\text{d-ary-child}$ functions.

Because $\text{EXTRACT-MAX}$ was not altered, it depends on running time of $\text{MAX-HEAPIFY}$. In your analysis you now you must use worst-case time proportional to hight and number of children which each node must examine (which is at most *d*). Once again your analysis is very precise, in the end you got $O(d\ \log\_d(n(d-1)))$, which can be transformed to:

$O(d\ \log\_d(n(d-1))) = O(d(\log\_d(n) + \log(d-1))) = O(d\ log\_d(n) + d\ \log\_d(d-1))$

For practical reasons we can always assume that $d \ll n$, so we can lose the $d \log\_d(d-1)$ part of *O* notation, then we will get $O(d\log\_d(n))$. Which is also valid solution. But not surprisingly you can also analyse function run time using Master theorem, which will show that $\text{MAX-HEAPIFY}$ is not only $O$ but even $\Theta$.
4. CLRS book already provides INSERT procedure. Which looks like this:

$\text{INSERT}(A, key)\\ \ \ \ \ A.heap\\\_size = A.heap\\\_size + 1 \\ \ \ \ \ A\[A.heap\\\_size\] = -\infty\\ \ \ \ \ \text{INCREASE-KEY}(A, A.heap\\\_size, key)$

It can be easy proven but common sense dictates that it's time complexity is $O(\log\_d(n))$. It's because heap might be traversed all the way to the root.
5. Just like INSERT, INCREASE-KEY is also defined in textbook as:

$\text{INCREASE-KEY}(A, i, key)\\ \ \ \ \ {\bf if}\ key \ 1\ and\ A\[i\] \> A\[\text{d-ary-parent}(i)\]\\ \ \ \ \ \ \ \ \ A\[i\] \leftrightarrow A\[\text{d-ary-parent(i)}\]\\ \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

Complexity is obviously $O(\log\_d(n))$ (see previous point).

# Answer
> 1 votes
This is not complete answer. part b) solution is not $$h=log\_d\[n{d-1}+1\] - 1$$ Its $$ 1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log\_d\[n(d-1)+1\] - 1$$ as pointed out by user 55463(because he cant comment,but answer),but downvoted because of lack of explanation. Upvoted answer has also mistakenly solved it. Answer will still be $$h=\Theta(\log\_d(n))$$ Source:Problem 2-2. Analysis of d -ary heaps ,part b)

# Answer
> -1 votes
Answer to the second question is h = logd(n(d-1) + 1) - 1 So, h = logd(nd - n + 1) - 1

---
Tags: data-structures, time-complexity, runtime-analysis
---


# Question
Title: How many bytes of memory is used just to "acknowledge" that a certain file is a .jpg?
I'm rather new to computers and how they work in the microscopic scale, but here's the little bit that I know.

> Computers have lots of transistors in them, both in memory and processor, and each transistor has two states, on and off. They are translated to binary equivalents 0 and 1. All data is stored in computers as combinations of 0s and 1s. Each 0 or a 1 is called a **bit**, and 8 bits make up a **byte**. A single byte is too small so units like kilobytes, megabytes, and gigabytes are more common.

I know that .jpg images occupy some memory in the computer, usually in the orders of kilobytes. However, the computer must know that the 0s and 1s that make up the image are for the image, and the computer must acknowledge this. In order to inform the computer that these 0s and 1s are assigned for a .jpg image, there must be a few bytes of data to **inform** that the rest of the bytes are a part of the image file. **How many bytes would just *acknowledging* the file type take?**

# Answer
Zero. A file type doesn't need to be “acknowledged”.

Imagine a photo of a tree. How much surface on the photo is needed to acknowledge where the photo was taken? Zero. The photo doesn't need to include an indication of where it was taken. It *may* do so, of course (for example, someone could have held a GPS's display in front of the tree), but equally it may not. There may be a legend below the photo, or here may not. And even if there's an indication, it could be false.

This metaphor works for a file's format.

Data in memory is just a bunch of bits. The semantics of this bunch of bits is defined by the code that manipulates it, not by the values of the bits alone. See How does a computer determine the data type of a byte?

If a location in memory may contains $n$ different file types, and the program needs to store an indication of the file type, then storing the type requires at least $\lceil \log\_2(n)\rceil$ bits. This is because $k$ bits of memory can store $2^k$ different values; $\lceil \log\_2(n)\rceil$ is the minimum value of $k$ such that $2^k \ge n$. In practice, it is common to use more bits (e.g. a whole word), because manipulating arbitrary groups of bits is not easy in a typical programming environment.

This is assuming that the type indication uses a constant amount of memory. If the type indication uses a variable amount of memory (e.g. a string), then the minimum is again 0 (but you then have the problem of how to store the length of the string). When data is stored in files, it's common to indicate the file format via the filename extension. But this is purely a convention; there is no mathematical relationship between a file's name and a file's content.

The JPEG format, like many other file formats, starts with a magic number. It's a 2-byte magic number. If a file begins with the two bytes (0xff,0xd8), then there's a good chance that it's a JPEG file. But this too is purely an engineering consideration — a convention that most programmers follow. It's a social observation, not a scientific observation.
> 3 votes

# Answer
Depends on how accurately you want it to be.

If you trust the extension then all you need is the 4 last characters in the file name (32 bits)

If you trust the magic header number then you need to check the file starts with 3 bytes `ff d8 ff` (24 bits). Though other file types have different sizes of magic number. There is a (non-exhaustive) list of them on wikipedia.

If you want to make sure the file is an actual image then you need to actually decode it. Here the size depends on the file size.
> 3 votes

---
Tags: memory-hardware
---


# Question
Title: Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$
> For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$, $$\\#f = |\\{v : f(v) \neq v\\}|$$ For graph $G$ we denote: $$\\#G = \max\\{\\#f : \text{$f$ is isomorphism $G$} \\}$$
>
> Prove that if $P = NP$ then function $G\to\\#G$ is polynomially computable.

My problem is that I can't think about isomorphisms. I know that thanks to assumption in polynomial time I can check if two graphs are isomorphic. The problem is however that I can't generate candidate for checking it.

# Answer
Consider the decision version of computing $\\#G$:

$L=\\{(G,k) | \text{$G$ has an automorphism $f$ with $\\#f\ge k$}\\}$

$L$ is obviously in NP (an automorphism $f$ with $\\#f\ge k$ is a witness). If $\mathsf{P=NP}$ then $L\in P$, and you can compute $\\#G$ in polynomial time using binary search.
> 1 votes

---
Tags: complexity-theory, graphs, time-complexity, np, graph-isomorphism
---


# Question
Title: How do I calculate the speedup properly?
I am trying to calculate the speedup of this, but I am getting the wrong answer:

> Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can only execute sequentially. The other phase takes 3 times units to execute sequentially but can be perfectly parallelized. What is the maximum speedup you can achieve?

This is how I have tried to calculate it; I've used the parallelization formula, which states:

$1/((1-P)+P/n))$

Where:

```
S(n) is the theoretical speedup
P is the fraction of the algorithm that can be made parallel
n is the number of CPU threads

```

So using the formula in my case:

P is 75% as 3/4 is the total time

I assume n is 1 as nothing is mentioned about it

$1/((1-0,75)+0,75))=1$

What am I doing wrong?

# Answer
If the phase can be perfectly parallelized then $n$ can be arbitrarily large.

$\lim\_{n\to\infty}\frac{1}{(1-0.75)+0.75/n} = \frac{1}{0.25} = 4$
> 1 votes

---
Tags: parallel-computing, performance, program-optimization
---


# Question
Title: Minimum Spanning Tree with Kruskal - bounds on size
I am using Kruskal's algorithm to build minimum-spanning-trees. I would like to know, given that my total set of edges has size `N`, if there is a bounding number of edges in the resulting MST, i.e. a size `M` smaller than `N` that determines the maximum number of edges in the MST. Or otherwise, if in general no such bounds exists. (Background: I want to allocate an array for the resulting MST in advance, and would like to avoid having to resize it.)

A second, related question: If I have a graph G and a corresponding MST (via Kruskal) from this, and I remove edges from G and rebuild the MST (with the same algorithm), is it safe to assume that the new MST can never have more edges than the old one, i.e. it can only ever shrink?

**Edit:** If these assumptions do not hold, would any of them hold if an additional property is that the graph G is fully connected?

# Answer
By definition a spanning tree must have $n-1$ edges.

If you remove edges and the graph remains connected, then again, a spanning tree must have $n-1$ edges.

If you remove edges and the graph is disconnected then you will not be able to make a spanning tree for the whole graph but rather you will be able to get a Spanning Forest.
> 3 votes

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


title: Proving if a function is an upper bound

text:
# Question
Title: Proving if a function is an upper bound
Let $f(n) = (\log n)^n$ and $g(n) = n^2$

By taking a large value, I could make out that $f(n) \> g(n)$ .

I want to know if $f(n) \in \Theta(n^2)$ . For proving this, I need to find out the value of $c$ such that $f(n) \le c \cdot g(n)$ .

How do I find the value of $c$ ? By seeing the function it seems like no $c$ exists. But I am not able to prove or disprove it.

Please help.

# Answer
> 3 votes
Just looking at the plot we can easily see, that these two complexities are completely different.

To prove it, we have to show that there doesn't exist a $c \in \mathbb{R}$ such that

$$(\log n)^n \le c \cdot n^2$$

We can take the $\log$ $$n\cdot \log\log n \le \log c + 2\log n$$ Because $3 \le \log\log n$ and $\log n \le n$ for big $n$, also the following inequalities have to hold:

$$3n \le n\cdot \log\log n \le \log c + 2\log n \le \log c + 2n$$

And therefore also the following inequaltiy has to hold:

$$3n \le \log c + 2n$$

This implies $n \le \log c$ or $e^n \le c$. And there is no $c \in \mathbb{R}^+$ with $c \ge e^n$ for all $n$

---

The proof is probably way too complicated, but it was the first thing that came to my mind.

---
Tags: algorithms, time-complexity
---


title: Boolean Logic Equation

text:
# Question
Title: Boolean Logic Equation
How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1.

```
x + x * y = x
x + x * y = (x * 1) + (x * y)
          = x * (1 + y)
          = x * 1 [THIS LINE]
          = x

```

thanks

# Answer
> 1 votes
In Boolean Algebra we have:

\begin{align\*} a \cdot b &= \min{(a,b)}\\ a + b &= \max{(a,b)} \end{align\*}

---

So, by the first definition it's obvious that:

$$ x \cdot 1 = \min{(x,1)} = x$$

Since $x \leq 1$.

By the same reasoning:

$$1 + y = \max{(1,y)} = 1$$ since $y \leq 1$.

So you have:

\begin{align\*} x + x \cdot y &= (x \cdot 1) + (x \cdot y)\\ &= x \cdot \color{red}{(1 + y)}\\ &= x \cdot \color{red}{1}\\ &= x \cdot 1 = x \end{align\*}

---
Tags: logic, boolean-algebra
---


# Question
Title: Practical application of Finite State Machines
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...

It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in string matching like KMP algorithm.

What is the significance of NFA, Moore and Mealy machines?

# Answer
Each time you do a search (particularly a "pattern search") in your favorite editor/tool, the pattern is translated into some form of finite state machine, which does the matching.

The lexical analysis part of your compiler/interpreter (yes, even your shell) is again a finite automaton which matches keywords and other tokens recognized by the language.

Any vending machine is a finite automaton which takes in coins of different denominations and recognizes when the correct amount has been entered (OK, today's vending machines probably have a small CPU inside doing the adding, but the end result is the same).
> 8 votes

# Answer
(the concepts of) DFA/NFA have some applications in the field of compilers and in construction of parsers. They are also use to identify strings according to regular-expressions (i.e. searching "patterns" over the web or over databases)

Moore/Mealy machines, are DFAs that have also output at any tick of the clock. Those have **PLENTY** of applications. In fact, any CPU, computer, cell phone, digital clock and even your washing machine have some kind of finite state machine in it, that controls it.

Maybe I should make it clear: **any "computer" is basically a finite state machine.**
> 7 votes

# Answer
One major application is modelling of systems. Essentially, simple software systems can be modeled as Finite State Machines. (By simple software, I mean languages that can be represented using regular expressions). There are many of such "simple" systems, vending machines are examples (as vzn indicated).

By finding the intersection of two Finite state machines, you can design in a very simple manner concurrent systems that exchange messages for instance. As an example, traffic light is a system that consists of mutliple subsytems (the different traffic lights) that works concurrently.

Have a look at these examples: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/

You will need to have LTSA analyzer to run these examples. http://www.doc.ic.ac.uk/ltsa/
> 4 votes

# Answer
heres a very good online reference on FSMs & related theory, 75p, with many diagrams. has many applications after the middle theory section, and also in many exercises with sample applications eg p485:

ch12. Finite-State Machines by Keller, Harvey Mudd college, CS60 textbook/ CS, intro to abstraction

applications are extremely diverse. eg from the book:

* number classification
* watch with timer
* vending machine
* traffic light
* bar code scanner
* gas pump

sec 12.4 EE constructions eg

* logic elements
* clock quantization
* combination lock
* flip flops
* adders
* registers
* buses/multiplexing

FSMs are also used in speech detection to find phonemes, one of the major points of application of this excellent online library which has some more detail in man pages and documentation: AT&T online FSM library. see section "FSM Library and Speech Processing Applications" (which also lists some more abstract/theoretical "applications")

etc!
> 3 votes

# Answer
I use state machines when writing device drivers. Beware that large state machines can become unwieldy. Consider using this set of macros (https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at) … that way the transitions become so simple that you don’t even need a state diagram. This is because the macros let you write your state machine code as if it is structured code. I wrote Cisco's Transceiver Library for the Nexus 7000 using these macros.
> 1 votes

# Answer
In practice, you will see it explicitly as an integer state variable (usually called 'state') that represents a very coarse state machine representing what actions are callable by the user of an object. It's usually an enumeration with values like: {uninitialized,initialized,...,stopped}. State machines are often explicit when parsing data, and will be signified by a switch statement in a while loop where at the top of the loop, the next character is gotten. In particular, if parsing has a regular grammar, an exact FSM with no other features is often used. If you are in a language that supports tail calls, FSMs are generally exhibited by mutual recursion (which can make the code read like a very clear pseudocode specification). A really useful feature of an FSM is the ability to operate concurrently because you only need to remember current state, rather than an entire execution stack. (ie: context switching between millions of state machine instances).
> 0 votes

---
Tags: reference-request, automata, finite-automata
---


# Question
Title: The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail
According to this description of Python's method resolution order (mro), a.k.a. C3 linearization, the algorithm can be described recursively as follows:

```
L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

```

where

* `O` is the class from which every class inherits.
* `C` is a class that inherits directly from `B1`, ..., `Bn`, in this order.
* `<` and `>` are list delimiters.
* `+` is the list-concatenation operator.
* `merge` merges its list arguments into a single list, in a manner to be described below.

The above can be rephrased in words (quoted from the above Python document):

> the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

The `merge` algorithm is described as follows (essentially quoted from the Python document, but slightly reworded):

> Consider the head of the first list, i.e L(B1)\[0\]: if it is a *good* head, i.e. if it is not in the proper tail of any of the other lists, add it to the linearization of C, and remove it from all the lists in the merge. Otherwise, consider the head of the next list, etc. Repeat until no more classes, or no good heads. In the latter case, it is impossible to construct the merge.

The following example is given as an illustration. Suppose `A` inherits directly from `B` and `C`, in this order, and suppose that the linearizations of `B` and `C` are

```
L(B) = <B, D, E, O>
L(C) = <C, D, F, O>

```

Then `A`'s linearization is

```
L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
     = <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
     = <A, B, C> + merge(<D,E,O>, <D,F,O>)
     = <A, B, C, D> + merge(<E,O>, <F,O>)
     = <A, B, C, D, E> + merge(<O>, <F,O>)
     = <A, B, C, D, E, F> + merge(<O>, <O>)
     = <A, B, C, D, E, F, O>

```

My question is: in terms of the original description of the algorithm, what purpose does it serve to give the list `<B1,...,Bn>` of direct parents as an argument to `merge`? Will the algorithm produce different results if this argument is omitted?

# Answer
Without the last list:

```
merge(<B,D,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

```

With the last list:

```
merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
  <B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
  <B,C,D,F,O>

```

---

Without the last list:

```
merge(<B,D,C,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

```

With the last list:

```
merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
  no-merge

```

---

Intuitively, the last list forces the final result to be compatible with the ordering `<B1,...,Bn>`. That might change the order, or make the merge fail.
> 5 votes

---
Tags: algorithms, programming-languages, type-theory, object-oriented
---


# Question
Title: Shuffling a list while keeping order relative to related elements
I'm looking to shuffle a list of the elements $a\_1,\dots, a\_6, \dots, e\_1, \dots, e\_6$

while keeping two rules:

if I loop though the list and filter out a specific letter or number it should be in order:

$a\_1, a\_2, a\_3 \dots$ or $a\_1, b\_1, c\_1 \dots$

How can I shuffle the list keeping these rules? I'm using python, so if there's a library that'd be great. Otherwise, just a generic way I could tackle this problem.

Here's an example of a shuffle that would fit the criteria:

$a\_1, b\_1, a\_2, b\_2, c\_1, a\_3, d\_1, c\_2, d\_2, e\_1, a\_4, b\_3,$ $c\_3, d\_3, b\_4, d\_4, c\_4, a\_5, e\_2, d\_5, e\_3, c\_5, a\_6, b\_5, e\_4, a\_7, $ $b\_6, c\_6, b\_7, d\_6, e\_5, e\_6, c\_7, d\_7, e\_7$

# Answer
Something like this perhaps?

```
from random import randint
letter_count = [0] * 5

for _ in range(35):
    while True:
        letter = randint(0,4)
        if letter == 0 or letter_count[letter-1] > letter_count[letter]:
            if letter_count[letter] < 7:
                break

    letter_count[letter] += 1
    print(chr(97+letter),letter_count[letter])

```

It works, in a quick and dirty fashion, but it does not have a uniform distribution. You would calculate the probability of a sequence occurring by dividing by the number of possible elements at each step. At some point in the example you might have 5 possible elements and the probability of the sequence occurring would be 1/(some multiple of 5). For other sequences there would never be 5 possible elements and the probabilty of that sequence would be 1/(not a multiple of 5).
> 1 votes

# Answer
Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews described in his paper Generating a random linear extension of a partial order. This might even be implemented in some library.

Your particular case is generating a random lattice word of certain content (for the reduction, delete all letters or all numbers). This is a concept occurring in representation theory of the symmetric groups, generalizing the classical ballot sequences. If you're lucky you might find an algorithm for generating a random lattice word (in Mupad, for example, somebody implemented an algorithm for *generating* all lattice words).
> 8 votes

---
Tags: algorithms, randomness
---


# Question
Title: Why are unbalanced partitions worse than balanced partitions in Quicksort?
I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.

After reading this document it shows that worse case partitions are of the type $(0,(n-1)), (0,(n-2)), (0,(n-3))$ and so on. So the work on every step is $Cn, C(n-1), C(n-2)$ , it actually decreases since $C(n) \> C(n-1)$. Correct me if I am wrong.

While in best case the partitions on every step can be assumed as $n/2$ on each side or $n/2$ or $n/2 - 1$ on each side. So the work done on each step, is $Cn$ always.

**So how is that better than unbalanced partitions ?** The work actually decreases in every step for unbalanced partitions, while for balanced partitions the work actually remains constant on all the steps and depending on the partition algo it may even include the pivot which is already sorted.

# Answer
> for balanced partitions the work actually remains constant on all the steps

That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the current one.

You also seem to be missing that, for the total cost, you need to *add up* all the steps. Just saying, "the inputs get smaller", doesn't tell you anything besides that the algorithm terminates.

In the worst case, you get the solution of a recurrence similar to

$\qquad\begin{align\*} T(1) &= 0 \\ T(i) &= T(i-1) + i \end{align\*}$

which solves to some $T \in \Theta(n^2)$.

In the average case, you get the solution of a recurrence similar to

$\qquad\begin{align\*} T(1) &= 0 \\ T(i) &= 2T(i/2) + i \end{align\*}$

which solves to some $T \in \Theta(n \log n)$.

---

To stress my point from above, consider

$\qquad\begin{align\*} T(1) &= 0 \\ T(i) &= T(i/2) + i \end{align\*}$

which solves to some $T \in \Theta(n)$.

Or

$\qquad\begin{align\*} T(1) &= 0 \\ T(i) &= T(i/2) + 1 \end{align\*}$

which solves to some $T \in \Theta(\log n)$.

You see that the specifics of the recurrence matter.
> 4 votes

# Answer
Raphael's answer gives you a formal proof: the recurrence from using a balanced partition solves to $\Theta(n \log n)$ and the (arbitrarily) unbalanced one to $\Theta(n^2)$.

Quicksort's recursive structure is nice enough that we can get a lot of intuition from looking at the recursion tree. Every level of recursive calls is just a partition (into a growing number of parts) of the $n$ elements of the original input. Every element not in a cell of size one is compared as a non-pivot at each level.

This tells us that as long as there are $\delta n$ elements in a non-trivial sub-problem (in total, there may be many non-trivial problems left) at some level, Quicksort makes about $\delta n$ comparisons.

It's then easier to see that the best partitioning scheme will minimise the total number of levels. Balanced partitioning gives you $\Theta(\log n)$ of them, and so a total running time of $\Theta(n\log n)$.

This kind of accounting is the idea underlying a very useful lemma by Timothy Chan for analysing recursive algorithms.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion, quicksort
---


# Question
Title: Equivalence of machine $M$ in $BPP$ and $EXP$
Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists **equivalent** machine in $EXP$. I cannot see how the $EXP$-machine is equivalent.

1. If we run machine $A$ on $x$ it can accept a word $x$ with probability $0.5$. Now we can run our $EXP$-machine. It try **every** possible toin-cosses-result so it compute an **average** probability of accepting of $x$.
2. I don't see why it works equivalently- even if the $EXP$-machine has coin-toesses as input, it should be random in any way.

# Answer
You are confused about the definition of when a language is in a class. You show that a language $L\subseteq \\{0,1\\}^\ast$ is in $P$, for example, by describing a Turing Machine with the following properties:

1. It is deterministic
2. It runs in polynomial time
3. It solves $L$

The classes $BPP$ and $EXP$ have similar definitions. The Complexity Zoo has a (very long) list of all the complexity classes.

The proof you cite works by following the definition of $EXP$ very closely: to show that $L\in EXP$, it describes a Turing Machine which (1) is deterministic, (2) runs in exponential time and (3) solves $L$. Showing this is relatively straightforward: it simulates the random machine for all possible random seeds, counts how many of those computations accept and how many reject, and then acts accordingly. This new algorithm satisfies the three properties above: we now know that there is a Turing Machine which is deterministic, runs in exponential time, and solves $L$. Now the proof is done. $\square$

The confusion may be that you do not need an equivalent machine (one that is also random, or that also sometimes errs, etc.), you only need to look closely at the definition of $EXP$ (which again, you can find in The Zoo), and then show that $L$ satisfies all the requirements. Also, $BPP$ is a class of *languages*, not of *machines*. Consider for example the complexity class $Sparse$, which consists of all languages that have a certain density, but which are not necessarily computable by any Turing Machine; the definition is not at all tied to the notion of computation.
> 3 votes

---
Tags: complexity-theory, complexity-classes, probability-theory
---


# Question
Title: Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?
I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 .

$n$ : number of nodes in the tree

$Z\_{n,k}$ : Indicator random variable that activates when rank of the root is k

$X\_n$ : random variable denoting height of BST

$Y\_n$ : random variable denoting $2^{X\_n}$

In the video, it is said that $Z\_{n,k}$ and $max(Y\_{k-1} , Y\_{n-k})$ are independent events.

But how they are independent? If we have $k=1$, then the max height can go till n. And when we have $k=n/2$ , max can go till $n/2$ only. Therefore the choice made by $Z\_{n,i}$ affects the possibilities for $Y\_{k-1}$ and $Y\_{n-k}$

# Answer
I haven't watched the video, but presumably it uses the following model of random BST. You start with one element. Then you insert an element which is smaller than the existing element w.p. 1/2, and larger w.p. 1/2. Then you insert an element which is smaller than both existing elements w.p. 1/3, is between them w.p. 1/3, and larger than both w.p. 1/3. In the $n$th step, you similarly insert the new element in one of the $n$ positions, with equal probability for all.

This means that $Z\_{n,k}$, which indicates whether the $n$th element got inserted in the $k$th position, is independent of anything that went on before, and in particular of $Y\_1,\ldots,Y\_{n-1}$.
> 1 votes

---
Tags: algorithm-analysis, data-structures, proof-techniques, probability-theory, binary-search-trees
---


title: Christmas Light Route Efficiency

text:
# Question
Title: Christmas Light Route Efficiency
This is a real situation *(I hope it's ok that I post this here. If not, please suggest a better home)*. I have little knowledge of algorithms, but I know I can use one to solve this problem.

I'm looking for an answer, or an online resource that can help, or an algorithm I should research to help me find the route with the least overlap.

---

I have an enclosed structure with rafters. I want to hang christmas lights inside it, and I'm trying to figure out how to cover all the ceiling beams with lights while minimizing overlap.

Here's a rudimentary schematic of the structure:

* The pink circles are places I can hang the lights from
* The yellow dots are where the lights should be
* "Start" is the only available electrical outlet
* Each strand of lights is aprox 234 inches (droop and empty sections have been accounted for)

## What is the most efficient path(s) to minimize overlap?

Here's some things to keep in mind:

* Assume I have an infinite number of lights
* The beginning of a strand of lights has a male electric connector. The end has a female.
* The start (male) of one strand must intersect with the end (female) of another strand (for electricity).
* Multiple strands can start from the same point

Here's the XML of the diagram (you can use this in draw.io):

```
<?xml version="1.0" encoding="UTF-8"?>
<mxfile userAgent="Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.90 Safari/537.36" version="7.1.3" editor="www.draw.io" type="device"><diagram id="d7d79c46-3ad7-dd0f-4011-e37531a3d72a" name="Page-1">7V1Lk6M4Ev4tc3DE9KEckngf29Xd24fZiImtjdjpo8rINtsYebHq4fn1KwHiIYGLcoNM2XYdClKyBF9+SqVSCZ5Z99vXf6R4t/knDUk8QyB8nVlfZghB2/L4PyE5FBLgglyyTqOwkFWCh+hvIisW0qcoJPtGRUZpzKJdU7ikSUKWrCHDaUpfmtVWNG72usNrogkeljjWpf+JQrbJpb4DKvl3Eq03smcIipJHvPy5TulTUvQ3Q9Yq++TFWyzbKurvNzikLzWR9XVm3aeUsvxo+3pPYgGuhC3/3reO0vK6U5KwPl9w8i884/iJyCvOrosdJBbZ3RBRH8ysxcsmYuRhh5ei9IWrn8s2bBvzM8gPi+ZIyshr5yXB8kY5gwjdEpYeeJXiC34BzaF5+lLpAUo2beo6kEJc6H5dtlzdPz8oIGiHw50eHMg+Ix7e9PCwwRnx8KeHh+OeEY9gengo5qMcPkbwkPPXhAEpx48ZQOD0AIGoiUg5guqIoNEQQdNHxENGEbGmj4jfZlbHQ8SeHiKqH2LYsE7QUVU9EcOITNBXVX0Rs4igCU6+6qgxO/uiCc6+6qgxjMgEZ1911BhGZIKzrzpqWj208RCZ4OyrjhrDiExw9lVHjWFEJjj7qqOm1YsfD5EPECsyjMgHiBYZRmSC8SItvmo0gGZN0GfVIqxmEZmgz6rFWM0iovusnjOXc3INFn6DrHnve5bSn+SexjTlkoQmvOZiFcWxIsJxtE746ZIDQrh8IeCKljj+XBRsozAU3bSCPQDCUPP4NIDtFnzREPDqDnBfeFOyj/7Gj1kFwcQdjRKWXYqzmDlfBLBPjO7z7U1YwzkmK9aCMqMCzj1HN0rW/xYnX+7sgcxc4DQAbvGWnLEA1v1pDrAFLw1i2wFvQdxmIwaBuM1Bd2MBQBg9NzB2//ckNpcXAuq7AqzPvEYx9MtyfrQu/mftcMgSKfM8KeUXVi+oibN+pfSS1Oyi5khqMVXWWGrWVx2+d1noelYTXehAc/DqSxjfnfsXZ6g8aZEP0sFA5iyVvijyvfkFQuw3ILY9z9x8q6+yOMSWd3EQN1nsWuZcGltftnGI3ctjcRNiLzAIsb4O9IOLc8tVhIOW6W40hPV1pdxUvBR4A3VVqVvhsZwJuy0eWnelW3zyZb4qF+54un78nV8F7wbIf58yTMCKJuxuhbdRfMirfifxMxGI1spz9EUpRLvXekHeqShJaLrFca3sGacR5v+5XjB7SkUC7tF6S7zrqvJSoKkWxoTxVcZdoWy9nKa7DU6KVlEu61ipVGVREmZ8EIVA3m1WwlLe2Iq3L3vKoh2CACKMkV1GCUYZzBDsyDKIa9fwQtOwedVlR/xeH39GvC/RYR5wuSv41ahXpQbfKXrOlm9CxfWDT7XbCMmSpphFNKnrL0oiFkng1Hq1Lhr1wmi/i/FBlsQRRwSB36LtjqYMJ6zQYUwxUzBTF4ZObo071oFvWpEBRjfUtoBsbXi3RY2sAYa307YBlGMhBkDr8FZGJhIjU4MVZl/lvA3FcFiJMSOufM8PssZAFk+pfUvin3fbgT+/+Gi3F4rcb/BOCJcxfeL38lb0NMT7TRZpFSf1yGGV2W4tYvxI4kXJ77YqzUgkLwm+ir+yRKbZo4HCXbDpf7dlolijRWydHjs/lUbe0ADe7/JHHFbRq9BEW/xWQ/fbNx8txCS6TnEYcdBqZaHjWUE4FvLum0GwtiFpD4F6j92lS0UdobPB7uproauB3fLPB3uPfbJLhd1Rdotcyxzs+qLpamD3wPnY3iNL7VJhh+p+vEnce+TCXSru6pwKAdKDM6MB3yPl7lKBtzxfAV568yaA75HZd6nAO5YKvEnG90ggvFTg3eCcjL/i1ao6t3LGG5xcr3jBqgLvtTz0MBbu3qgr1o5gWHfy3YS0ogZULX2/ZDSlXPF6Vn1szqAN8q54PavAbrVk9Y4G+xWvZ9UwglG6X/F6VsXdKN+veFWl4u7IBC0DuPvXPKsqiyqTLqZ/xdOqyneT8Uq/xc7co9lnYAGUZ/JmZ7oukvCzeG/cTGyM4/0+Wmbo4JTp4uaWOE1Y8f46sUHfkdwkatXwB9mne62QqU98ZmVe1CzPtcovnITa6+veVM4bCWVSlpIYs+i52XybRooe/hTJX5Xulf0wNdNiT5/SJSm+U2lVa8ZDx9vhilkTprWTsaO8536bxi0DNaNImfr964RppLaBSvBHlg9XlywoY3TblP2rUFI3uxqELKAhacRRIOlDSR9PNJnjrxe6R8lYZnF08bhJ0tqYgK5mZeAHoLH6+h8IvIGYrLc0HJch1B8GERg/FKfFVNF8erKYZ8QheY3YX+J47hRnPyQV5WsqgUq3HqT5L2HsUPBBZIZyEU3Zhq5pguM/aDYq9IcVG/TSpqk6xewjxOxLNI5ZplCpJNDOvl+kVRDMg9pHPhMg/UK7Wez34gk3N/hQq1Zk43ZTW3lKzSneWVfRLm/xZBLK2b9mUR+EXTzd/+lDuC43yEePlqsbITTTstlCh/ih3eQWQke41eJYBV4IPG+gCClUFOXrwTivzY2yft2NgqBPfKKaAgv036kzPT9Qqid4hxpET39ikVacZN0hYOvKXflLsly2+8lf3S51Euw+ZuTh4vQgTOMdmAPgSckPKbGkpJxaVcMpYHg8ikB/U5VbgoIV55wmlX1ax3FOmyRVqkPgjzdJgj4hoOuh9jsYKv0DyBkPax5CNQS4QB0Bp83A/jlp7Su0du1j83Jfkne813oMhvfJHbkx/AjDuQfccIGr02Honec6nM1sqy5gMNDiZkxO9wkgXw+np+SQnG2RDgPFa7DBEIaatzu3HBTYfD3t2h6QW6TldODMa6XyqYMxON8nI+ojcX61Qu/n/GoVBqfb8SCwGoYcwGEtef7E7PmGgOKqBGO4KlpkfkiO90k+u3HcMMfP5plAr2l6Gzy0gmDu+6is4J7otfjHonBWz7jbSWTvk/B3I/uN7JmbAccnu6M+7TrkZkSfLMsb2T+g460u+zz4C572EXaKAfL+DZGTuNonTebG1Y/IVcVD9tUYRX+uese46nunbN6dxFV04+p1cFUENEYhKwSWMbbquy3I5V5c2+vohkjCyrIBrjwJq+MXI99Loq4f4RiDJfqOBXLttre93TgyCkc05Z5IEt1kDckSfQ/AQc4c+jdbMhpP/I6fW31/SNEkUdriLOd49559e/fe1N+958hX7tUOpv/uPXD6i/felzo56K862D2fODrhBX38tPrV9NxmVL9Nb339Pw==</diagram></mxfile>

```

# Answer
> 2 votes
The problem you're trying to solve is called the route inspection problem (a.k.a. Chinese postman problem, from back in the days when it seemed normal to call something "Chinese" because the first person to study it was Chinese). Good news – there's an efficient algorithm, described in the Wikipedia article.

---
Tags: algorithms, efficiency
---


# Question
Title: Prove that $L$ is closed under Kleene star iff $L=NL$
> Prove that $L$ is closed under Kleene star iff $L=NL$

Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$. Lets consider language $A\in L$. We show that also $A^\*\in L$. It is easy because we can guess partition of word $w=w\_1w\_2..w\_k$ and launch algorithm for each part. It is possible because $L=NL$ so being in class $L$ we can use guessing.

However, when we assume that $L$ is closed under Kleene star I am hopeless. Obviously, from assumption we know that $A\in L$ then also $A^\*\in L$. Of course, we know that $L\subseteq NL$. However I must now show that $NL\subseteq L$ using assumption. This is hard for me.

# Answer
> 3 votes
Let $A$ be the language consisting of the following words: $$ (u,v)|\Sigma^\*|(v,w), $$ where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.

Given a directed graph $G$, we can encode it as a list of edges in the following way: $$ (x\_1,y\_1)(x\_1,y\_1)|(x\_2,y\_2)(x\_2,y\_2)|\cdots|(x\_m,y\_m)(x\_m,y\_m) $$ where $x\_i,y\_i$ are vertex numbers encoded in binary. Furthermore, this string, which we denote by $\langle G \rangle$, can be output by a logspace machine.

Suppose now that we are given two vertices $s,t$, and that there is an $s$-$t$ path of length $\ell$ of the form $(s,x),\ldots,(y,t)$ in $G$. Then I claim that for all $L \geq \ell$, $$ (s,x)|\langle G \rangle^L|(y,t) \in A^\*. $$ Conversely, if such a string belongs to $A^\*$ then there is an $s$-$t$ path in $G$. In other words, $$ \exists \text{$s$-$t$ path in $G$} \longleftrightarrow (s,t) \in G \lor \exists x,y \text{ s.t. } (s,x)|\langle G \rangle^n|(y,t) \in A^\*. $$

If we assume that $\mathsf{L}$ is closed under Kleene star then $A^\* \in \mathsf{L}$, and so we can evaluate the right-hand side formula in logspace. Since $s$-$t$ reachability is $\mathsf{NL}$-complete, we deduce that $\mathsf{L}=\mathsf{NL}$.

---
Tags: complexity-theory, space-complexity, nondeterminism, kleene-star
---


title: Best way to fusion two list of clusters

text:
# Question
Title: Best way to fusion two list of clusters
Imagine the following sets :

```
A = Set( sortedSet(1,2,3), sortedSet(4,8))
B = Set( sortedSet(3,4), sortedSet(5,6,7) )

```

Where each inner list represent a cluster composed by indexed dots (1,2,3...).

I want to gather cluster sharing the dots sharing the same index into one to get :

```
Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )

```

My first attempt was to merge two Sets

```
Set( sortedSet(1,2,3) ), sortedSet(3,4), sortedSet(4,8), sortedSet(5,6,7) )

```

and then merge each subset with subset of the same set where they share a common element. And repeat this process $k$ times with the result set until it doesn't change.

```
0 : Set( sortedSet(1,2,3,4), sortedSet(3,4,8), sortedSet(5,6,7) )
1 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
2 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
1 = 2 then Stop

```

Unfortunately i think this method is upperbounded in a bit less than $O(k.n^2)$ where n is the total number of elements in every subsets.

My second attempt was to get links which connected subsets of A and B. Add to each A's subsets every sub sets of B which are connected to them from the link A -\> B to get A'. Then use link B -\> A to gathered A' subsets to get A''. Finally i apply my first attempt on A'' to get A''' and add it the lonely clusters in A and B.

So my final result is A''' + A\_lonely + B\_lonely

I use optimization that i know like using SortedSet and exist method (rather than go through each subset to know if they share a common element).

The second method works way faster (5min VS 45min) for a precise test. But i know that i can still encounter the same issue due to the step A'' -\> A''' which remains quadratic.

Any optimizations i could use or proper solution is welcome !

# Answer
You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number of edges and vertices of the graph. The clusters from each connected components are then fusioned to create the resulting clusters.
> 1 votes

# Answer
Thank's to @D.W insights, the right way to do this is to use Disjoint-set Data Structures which have a $O(\alpha(n))$ costs to merge where $\alpha$ is the inverse Ackermann function.

Then use them to find connected components in a graph.
> 0 votes

---
Tags: algorithms, data-structures, sets, union-find
---


# Question
Title: What is responsible for the 1-1 correspondence between characters and binary?
Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and their binary equivalents, which is then loaded into ROM during manufacturing?

# Answer
> 1 votes
Internally, everything is binary and only binary. The only places that characters exist are places where you can literally see them with your eyes. For your benefit, and your benefit only, the system contains code that associates pictures such as `a` or `6` with those binary values and displays those pictures on the screen or on printer paper.

---
Tags: computer-architecture, encoding-scheme
---