# Question
Title: Why do we use the number of compares to measure the time complexity when compare is quite cheap?
I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player correctly, assuming the tennis players are not a "rock paper scissors" situation (but has an "absolute 'combat' power").

If we have an array of size `n` being `1,000,000`, we don't usually mind comparing `2,000,000` times to find the second largest number. With the tennis tournament, having a Player A match with Player B can be costly as it can take a whole afternoon.

With sorting or selection algorithms, for example, what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? (Maybe it didn't happen yet, or else we would have a study case about this situation). So ultimately, shouldn't the number of atomic steps, instead of comparisons, measured by the order of growth as compared to `n` (O()) that determines the time complexity?

# Answer
> 22 votes
Sure. But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about. This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running time.

Also, there are some situations where we use sorting algorithms where each comparison is much slower than the other operations. A comparison may be slower than the other operations, because conditional branches can be very slow on modern processors (each comparison may have a significant chance to cause pipeline flushes). And if you are sorting complex objects with a custom comparison function, then each comparison might take many instructions. So, in at least some cases, the number of comparisons might well dominate the over time it takes to sort the input.

Finally, there are certainly some cases we *do* take into account the time to perform other operations. It's most common to only count the number of comparisons, but by no means universal. In situations where the time taken for other operations is important, people do analyze the total running time.

Ultimately, asymptotic running time analysis is only a theoretical model. It is a simplified model that omits many considerations. Any such simplification will necessarily ignore many factors. As long as those factors are unimportant, this can be useful, as it helps you simplify the problem enough to analyze it and gain insight. But, as always, if one of those factors turns out to have a significant effect and you didn't include it in your model, then the model will yield misleading results -- this is true of all models, and is not limited to sorting or algorithmic analysis. Part of the art of modelling is identifying which factors dominate and which factors are second-order, so that you can choose a model that's only as complex as needed -- it is as simple as possible, so you can understand it better, but no simpler than that, so it still yields predictions that are reasonably representative of the real world.

# Answer
> 9 votes
If moving an item were n times more expensive than comparing, selection sort would suddenly be the most efficient algorithm. But if moving an item were expensive, we could sort an array of array indices, and then sort the original array in place with at most 1.5n moves. (That would actually be n/2 swaps; if a swap is cheaper than 3 moves then worst case is 4/3 n).

The number of comparisons cannot be lower than log n! for comparison based sorting.

# Answer
> 6 votes
> what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons?

Um, yeah. That's why, in such cases, we **do** use those other operations for the analysis. For example:

> Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case, which is O(n log n). **The algorithm as a whole still has a running time of O(n2)** on average **because of the series of swaps** required for each insertion.

# Answer
> 2 votes
Big Oh analysis is looking at the asymptotic behavior of an algorithm. In these analyses, the thing which gets done "more" will always overshadow the thing which gets done less. As an example, consider an algorithm which does $O(n)$ disk operations at a cost of 1,000,000,000 units each, and $O(n^3)$ comparisons at a cost of 1 unit each. Obviously for small numbers of n, the disk operations will be the dominating part of the cost. However, as we get to large n, like 1,000,000,000, we see that we do 1,000,000,000 disk operations, for a total cost of 1,000,000,000,000,000,000 and we do 1,000,000,000,000,000,000,000,000,000 comparisons, meaning we spent literally a billion times more on the comparisons than on the disk reads, even though they are very light weight on their own.

This is not always the story we want. For many practical algorithms, we are not operating on such awful huge datasets where those small comparisons start to add up. In these cases we may do other things. In the case of "offline algorithms," which operate on databases on disks, we may measure the number of reads. Or we may even recognize that its cheaper to load a "page" of values all at once, so we try to measure how many pages have to get loaded.

This sort of study is useful, but it is not well captured in a simple Big Oh analysis. It typically has to account for what the hardware is good at, making the analysis more specialized. For example, there are cryptographic algorithms which are designed to be very inefficient on a GPU architeture, but very efficient on a CPU architecture.

My personal favorite of these is a particular disjoint set algorithm that came up when I was working on some fun threading problems. The complexity of it was one of those exotic things with O(log log N) terms showing up. But in the conclusion of the paper, they had to admit that their algorithm had some aspects which had such an ungodly large time constant that the less advanced algorithms were better for basically any dataset which fit onto a modern disk farm. Once your dataset started to move into the extabyte size scale, their algorithm started to earn its salt!

# Answer
> 2 votes
It seems like none of the other answers so far have mentioned a basic reason: There are many sorting algorithms whose total (asymptotic) time complexity **is** in fact bounded by the number of comparisons times the maximum time taken per comparison. Obviously that is why such sorting algorithms' cost should be measured by the number of comparisons, because they can be used to sort any input list from any set given a comparison function on that set.

Another more theoretical reason is that the information theoretic lower bound for sorting applies to the number of comparisons in the comparison model, so of course it makes most sense to measure the cost of a generic sorting algorithm in terms of the number of comparisons it takes.

# Answer
> 1 votes
### 1. Because you can avoid the other operations being expensive.

Comparing integers is cheap. Comparing arbitrary elements of type T is typically as expensive as reading sizeof(T) bytes. Now, you might think "ok, but copying type-T elements is also expensive" - but we don't need to do that. We can just copy or move their *indices* in the input around and use those to lookup the original elements when comparing. Yet, we can't avoid the comparisons the same way.

Caveat: You can use hashing to avoid, typically, most costly comparisons.

### 2. It doesn't matter (except when it does)

You asked:

> what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n)

Well, the first option is a poor sorting algorithm anyway, and as for the second option - see @HeapOverflow's answer.

# Answer
> 0 votes
The cost of comparison is more complex and depends on more than you imagine. Between each of the following is an order of magnitude cost increase.

* Register
* CPU Cache
* RAM
* Magnetic disk

Then there's the fact that your process does not run in isolation, but competes with other processes for system resources. Some of those processes will not be denied.

In the world of database engines, performance is all about mitigation of working set size. The smaller your working set, the less time you spend in the Slow Zone.

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


# Question
Title: Are there more languages than functions?
My gut says "no", but I don't know why.

For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(s)$, or the empty string if $f(s)$ is undefined. So there at least as many languages as functions. How can we define a function for every language? (Forgive my ignorance about languages, automata, etc. I have not studied in that area. Perhaps my question is poorly constrained.)

# Answer
It depends on the signature of the function. In computability theory we typically deal with functions with the signature $f:\\{0,1\\}^\* \to \\{0,1\\}$. There is a one-to-one correspondence between functions $f:\\{0,1\\}^\* \to \\{0,1\\}$ and languages $L \subseteq \\{0,1\\}^\*$: in particular, the function $f$ corresponds to the language $L=\\{x : f(x)=1\\}$, and the language $L$ corresponds to the function $f(x) = 1$ if $x \in L$, $f(x) = 0$ if $x \notin L$.
> 4 votes

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


title: maximum weighted path(s) in a DAG

text:
# Question
Title: maximum weighted path(s) in a DAG
Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current approach is doing the followings.

Add an extra node $S$ (source) and put directed edges to all starting nodes with zero weight. Similarly, add a sink node $T$ and put directed edges from all end nodes to $T$ with zero weight. Now, the problem is to find all maximum weighted paths between $S$ and $T$. Make the edge weights negative, i.e. weight $w$ becomes $-w$. Find the all single-source shortest path from $S$.

My question is, if there is any other efficient method to achieve this. The other thing is that, I need to find all maximum weighted paths if there exists more than one such paths. How can I find all maximum weighted paths efficiently?

Does maximum flow algorithm help?

# Answer
Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe:

In your case we could implement it similar to the following (transcribed mostly from CLRS 24.2) assuming input is an adjacency list:

```
0.  Max-Weight-Paths(Graph G(E, V)):
1.    add Super-Source S, and Super-Sink T // takes O(V + E)
2.    negate all edge weights              // takes O(V + E)
3.    topological sort G.V                 // takes O(V + E)
4.    for each vertex u in sorted order:
5.      for each vertex v in G.adj[u]:
6.        Relax(u, v)                      // 4-6 takes O(V + E)

```

Now for returning *all* max weight paths we can simply modify the relaxation step (6) a little bit. Instead of only containing a back pointer to one parent, we can maintain a linked list of back pointers to all parents of equal total distance like so:

```
0.  Relax(Vertex u, Vertex v):
1.    if distance(v) > distance(u) + w(u, v):
2.      distance(v) = distance(u) + w(u, v)
3.      parents(v) = {u}
4.    elif distance(v) == distance(u) + w(u, v):
5.      add u to parents(v)

```

Assuming `parents(v)` is maintained as a list, the `Relax` step still takes $O(1)$.

Then in the end you can return all max weight paths by starting at the sink `T` and traversing back up through `parents(T)` an so on. This traversal will return a DAG itself if multiple max weight paths exist. So just be smart about the traversal and the whole thing should take $O(V + E)$.

---

Edit, when I say be smart about the returning traversal, keep in mind a bad case scenario, something like this where all edge weights are equal:

There would technically be $6^2$ max weight paths, you could expand this example to get graphs with very large amounts of max weight paths due to combinatorics. So it might be more useful to return the DAG of max-weight paths rather than each individual. Although if you must return individual paths then you might be out of luck, because there are a lot of possibilities.
> 3 votes

# Answer
You should try to understand what topological sort does. It finds an order v1,v2,...vn of DAG such that there is never an edge (vx, vy) where x \> y.

Once you have top sort graph, then you can start in topological order of vertices, and then for each outgoing edge, start to RELAX the destination vertex.

Note that the RELAX function could either be max cost or min cost. The algo works in both the cases. To understand why it works, you'll need to understand why the algo works for Shortest Path solution first. You can check any algorithm book (Goodrich Tamassia / Cormen etc) to understand the proof
> 0 votes

---
Tags: weighted-graphs, dag
---


# Question
Title: MAX 2-SAT is polynomial time reducible to 2-SAT?
I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard.

I have issue about this statement: MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks like? I need the only intution about that, but not proof.

# Answer
> 3 votes
I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless P=NP.

Let $\phi$ be a 2-SAT formula with $m$ clauses. If you really want to reduce an instance $\phi$ of 2-SAT to (the decision version of) MAX-2-SAT, then this simply amounts to checking whether at least $m$ (i.e., all) clauses of $\phi$ are satisfiable.

---
Tags: satisfiability, 2-sat, maxsat
---


# Question
Title: Equivalence between MIN UNCUT and MIN-CSP_XOR
In this paper

> Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 2005.

Agarwal et al. claim that the following two problems are equivalent.

> Consider boolean variables $b\_1,\dots ,b\_n$ and a set of constraints of the form $b\_i \oplus b\_j = 0$ and $b\_i \oplus b\_j = 1$. The goal is to minimize the number of unsatisfied constraints.

and

> Given a graph $G=(V,E)$ find a cut that minimizes the number of uncut edges.

If constraints were only of the form $b\_i \oplus b\_j = 1$, the equivalence is straightforward. However, if we also consider constraints of the form $b\_i \oplus b\_j = 0$, the first formulation seems more general to me.

How are these equivalent?

# Answer
> 2 votes
Suppose we are given a set of constraints of the form $b\_i \oplus b\_j = c$. We construct a graph with one vertex corresponding to each $b\_i$. For each constraint of the form $b\_i \oplus b\_j = 1$, we add an edge $\\{i,j\\}$. For each constraint of the form $b\_i \oplus b\_j = 0$, we add a new vertex $x$, and two edges $\\{i,x\\},\\{j,x\\}$.

We can think of a cut as a partition of the vertices into two parts. For a constraint of the form $b\_i \oplus b\_j = 1$, the constraint is unsatisfied iff $i,j$ belong to the same part iff $\\{i,j\\}$ is uncut. For a constraint of the form $b\_i \oplus b\_j = 0$, there are two cases:

* If the constraint is unsatisfied, then $i,j$ belong to different parts, and so exactly one of the edges $\\{i,x\\},\\{j,x\\}$ is uncut.
* If the constraint is not unsatisfied, then $i,j$ belong to the same part, and so (depending on the location of $x$) either zero or two of the edges $\\{i,x\\},\\{j,x\\}$ are uncut. Since we are aiming to minimize the number of uncut edges, we can assume that zero are uncut.

In total, the number of unsatisfied constraints is the same as the number of uncut edges.

---
Tags: reductions, constraint-satisfaction, bipartite-graph
---


# Question
Title: An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence
Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly distributed infinitely long binary sequence.

Edit: I didn't consider my attempts at solving this to be relevant, they are as follows:

I've considered to use a Markov chain and the fact that $P(A\_j)$, the probability of absorbtion of the chain in the $j$-th absorbing state, $=(b^{(0)}NR)\_j$, where $b^{(0)}$ is the vector of probabilites of the starting state, $N$ is the fundamental matrix of the chain and $R$ is the matrix that describes the probability of transitioning from some transient state to some absorbing state.

I've indexed the chain states by $(i, j)$, where $i$ is the length of the longest prefix of the first string ($s\_1$) that matches in the current state, and $j$ is the same for $s\_2$.

Absorbing states are $(n, \*)$ and $(\*, m)$, where $\*$ denotes any number, therefore splitting $P$, the transition matrix of the chain, into $Q$ and $R$ is trivial.

The only thing left is to compute $P$ in polynomial time, which is where I'm stuck. I have written this algorithm, but it's not correct:

```
for i = 0...n
    for j = 0...m
        if i == n || j == m // absorbing state
            P[(i,j)][(i,j)] = 1
        else if s[i+1] == r[i+1] // bits are the same => either in both strings the next bit will match or it will in neither
            P[(i,j)][(i+1, j+1)] = 0.5
            P[(i,j)][(0,0)] = 0.5
        else // bits are not the same => in both cases only one of the bits will match
            P[(i,j)][(i+1,0)] = 0.5
            P[(i,j)][(0,j+1)] = 0.5

```

The problem with this algorithm is that in case a bit does not match, the matching prefix length may not be zero, for example on sequence $010...$ for the string $011$ the matching prefix length will be $1\rightarrow 2\rightarrow 1\rightarrow\ldots$, instead of $0$, as my algorithm implies.

# Answer
Here is the rough idea, for determining the probability that $x$ appears before $y$:

* Construct a DFA that accepts the language of all binary strings in which $x$ appears before $y$.
* Take the adjacency matrix of the DFA, replace the edges by $1/2$ entries.
* Relate the probability that you're after to this matrix, and using this, calculate the probability.

I'll let you sort out the remaining details.
> 1 votes

---
Tags: algorithms, probability-theory, polynomial-time
---


# Question
Title: Is there a random shuffle algorithm using only true /false?
Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals.

For this question, I'm specifically excluding an approach whereby the booleans are just arranged into an integer and then it's used in a Fisher-Yates shuffle. I'd be repeatedly shuffling approximately 30,000 items and have a ready source of random booleans. I'd need to build up a very large integer for Fischer-Yates to avoid any form of bias in the shuffle. Can this step be avoided and true /false used directly somehow? I have the sense that some soft of bubble sort might do it, with the comparison determined randomly, but I can't quite flesh it out.

I'd be interested in any algorithm than wasn't ridiculous i.e. with a stupid time complexity of something like 2^O(n). This question builds upon some of the concepts of Best random permutation employing only one random number but isn't identical.

# Answer
> 7 votes
No, there is no algorithm that shuffles an array of length $n \> 2$ using a *bounded* number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome has a probability of the form $A/2^m$, whereas we need each possible permutation to have probability $1/n!$.

When you're using Fisher–Yates shuffle in the form you describe you aren't getting a uniformly random permutation, though you are getting something very close. If you want to get a truly uniform random permutation then you need to use some form of rejection sampling.

Using bubble sort in the way you describe would likely be a disaster – it would likely result in a random permutation which is easy to distinguish from uniform. Don't do that. There are no tricks and shortcuts. If you want your random permutations to be faster at the cost of being slightly less uniform, you can reduce the precision involved in approximating random integers inside the Fisher–Yates shuffle. This will probably be much better than inventing your own algorithm.

# Answer
> 3 votes
Referring to a $b$-bit number as $b$ individual bits or vice-versa doesn't change the number of random bits you need. If you need a gazillion bits when you consider them as forming integers, you need a gazillion bits when you consider them as individual tosses of a fair coin.

# Answer
> 0 votes
**Why not converting booleans to integer, and using Fischer-Yates ?**

If you have n elements, you will have n! possible permutations.

Let us use FYK algorithm (supposing it is almost good).

Then you will need:

* choose among n : say n = 2^k\_n
* then choose among n-1 : says n=2^k\_n-1
* etc.

So you need sum(k\_n,k\_n-1, ...) = P, where 2^P=n! (approximately, because every n, n-1, ... is not a power of 2.

**1 So you need P booleans, where 2^P=n!**

**2 FYK needs almost minimal time**: you have to make n changes (difficult to do less). and cutting/converting bits is minimal. You even can struct your array in some of binary tree.

# Answer
> 0 votes
You actually can use `true` / `false` to simulate a Riffle Shuffle or Faro Shuffle:

1. Start with the deck of cards on the middle
2. Move half of the deck to the left, and half to the right
3. Get a boolean: if true, then move the top card from the left pile back to the middle, or if false, move that top card from the right pile back to the middle
4. Repeat step 3 until all cards are back to the middle

There can be a variation of step 3: if another boolean is true, move 1 card, otherwise, move 2 cards.

Another variation:

1. Start with the deck of cards on the middle
2. Get a boolean: if true, then move the top card to the left pile, or if false, move that top card to the right pile
3. Repeat step 2 until all cards in the middle are gone.
4. Now merge the left and right pile of cards by taking 1 card from each pile alternatively and putting them back into one pile

You can also use boolean to say, move 1 card vs 2 cards in step 2. Also a boolean for step 4: if true, move one card from the left pile card during merging, but if false, moving one card from the right pile card during merging instead.

But you probably have to do it 7, 8 times to get a pretty good shuffle.

---
Tags: algorithms, randomized-algorithms, sampling
---


# Question
Title: Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D that might compress C more and produce compressed file E.

Is this kind method of using more than one compression-method in each iteration of compression standard? if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.

**I mean, is there any study where 2 or 3 methods were apply to same file, if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.**

# Answer
> 1 votes
Here's a partial "yes" answer to your question.

Consider a file containing:

```
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

```

That is, it is all binary numbers that are $b$ bits long (in this case $b=10$, but in the exercise that follows, try something smaller), in order, with each number separated by (say) a newline character.

The standard BWT compression algorithm (e.g. the one that BZip is based on) performs a Burrows-Wheeler transform, followed by move-to-front coding, then followed by some kind of entropy coding (possibly using run-length encoding).

This file compresses "better" if you apply the BWT *twice*, applying the following stages to the BWT of the BWT instead of just the BWT. I encourage you to compute both BWTs on a small example to see why.

Now this is only one stage of the full compression algorithm, and so we haven't found a file that compresses better if you compress it twice. But this BWT "adversary" is certainly suggestive.

I don't know if there are any papers on this. I discovered this one a few years ago (but I'm sure I'm not the only person who has noticed it).

# Answer
> 2 votes
The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.

---
Tags: reference-request, information-theory, data-compression, coding-theory, encoding-scheme
---


# Question
Title: Amount of expected loop iterations when searching an array by random index
Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1\<=k\<=n

If we have a search algorithm like so:

```
while true:
  i := random(1, n)
  if A[i] == x
    break

```

random(a,b) picks a number uniformly from a to b

From this we know that the chances of finding x and terminating the program is k/n with each iteration. However what I would like to know is what would be the expected value for the number of iterations or more specifically the amount of times the array was accessed in this program given the array A as described above.

# Answer
> 1 votes
Let $N$ be the geometric R.V. that returns the number of times the array was accessed in order to search for the element, $A\[x\]$ until we successfully find it. We want to know $\mathbb{E}\[N\]$.

We can view the iterations of the while loop as a sequence of IID Bernoulli trials, each with a probability $p$ of succeeding, and $q = 1 - p$ of failure. Given the question, we want to know how many trials are needed to obtain a "success" which would be finding the element $A\[x\]$ thus the `while` loop terminates.

Since the $\Pr\\{N = k\\} = q^{k-1}p$, we have that $\mathbb{E}\[N\] = \sum\limits\_{k = 1}^\infty k \\: q^{k-1}p$.

Thus, $\mathbb{E}\[N\] = \dfrac 1p$ where $p = \dfrac kn$ so $\mathbb{E}\[N\] = \dfrac nk$.

So on average, it takes $\dfrac nk$ accesses before we find the element, $A\[x\]$.

---
Tags: algorithms, search-algorithms, probability-theory, randomized-algorithms, statistics
---


# Question
Title: Question about Circuit-SAT NP-Complete Proof
I have two questions about the proof that Circuit-SAT is NP-Complete from here (just the first 1.5 pages): https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture22.pdf

1. The THEOREM 1 states that the size of $C\_n$ is bounded by some polynomial in $n$. Where is this necessary in the proof? It seems like what really matters (coming from the reduction definition) is that we can find $C\_n$ in polynomial time. I am not sure where the size comes in.
2. How would one "hard-wire" $G$ into the circuit in the second paragraph? I understand why it is necessary. However, wouldn't one need to also show that this hard-wiring takes polynomial time as well?

# Answer
> 2 votes
1. You're right. All that matters is that the reduction runs in polynomial time. (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.)
2. Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1. If the circuit has polynomial size, this modification takes polynomial time, since you're only modifying at most polynomially much stuff.

---
Tags: complexity-theory
---


# Question
Title: lambda calculus beta reductions: ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))
My question is in continuation to lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (\* y y))) 12)

given the input:

```
((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

```

I want to understand the order of reductions that I should take. in the above mentioned question it was suggested to me to apply left most reduction.

I want to check if this is a valid 1st step towards leftmost reduction:

Or should f= λy.λg.g(\*y y) instead ? What it might boil down to is: am I allowed to solve the sub-trees up before applying the solution from the right subtree on the left sub-tree?

# Answer
$$ (\lambda f. \lambda x .f x f) (\lambda y.\lambda g. g (\* y y)) 2 (\lambda a. a) $$

The leftmost redex $(\lambda a.b)c$ is

$$(\lambda f. \lambda x .f x f)(\lambda y.\lambda g. g (\* y y))$$

with

* $a = f$
* $b = \lambda x .f x f$
* $c = (\lambda y.\lambda g. g (\* y y))$

Don't forget to make sure that $x$ doesn't exist in $c$, because if so then doing an immediate beta reduction would change the meaning of the expression. So the redex reduces to:

$$(\lambda x .(\lambda y.\lambda g. g (\* y y)) x (\lambda y.\lambda g. g (\* y y)))$$

Overall giving

$$ (\lambda x . (\lambda y.\lambda g. g (\* y y)) x (\lambda y.\lambda g. g (\* y y))) 2 (\lambda a. a) $$

The next redex is $(\lambda y. \cdots)x$
> 2 votes

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Why does the substitution {x/f(y), y/z} work this way?
There is an example of applying a substitution to an expression, and I am having a problem with it. Let $\theta = \\{ x/f(y), y/z \\}$, and $E=p(x,y,g(z))$, then $E\theta = p( f(y),z,g(z) )$.

Why is $y/z$ not applied to $E$ after using $x/f(y)$, so that the answer would be $E\theta = p( f(z),z,g(z) )$?

# Answer
Because that's not how substitution is defined.

Seriously, there isn't much more to it than that. In some situations (such as applying a single step of a collection of rewriting rules), having the ability to substitute "each variable once, all at once" like this is important for the correctness of the definition. So substitution is defined so that there is a way to write these definitions correctly.

In other situations (such as the output of a unification algorithm), authors require that substitutions be *idempotent*, i.e. applying the substitution a second time does not change the result. This prohibits substitutions such as the one in the question, thereby avoiding the issue.
> 2 votes

---
Tags: logic, unification
---


# Question
Title: What is an asymptotically tight upper bound?
From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation. But what does asymptotically tight upper bound mean for Big-O notation?

# Answer
> 23 votes
Saying that a big-O bound is "asymptotically tight" basically means that the author should have written $\Theta(-)$. For example, $O(x^2)$ means that it's no more than some constant times $x^2$ for all large enough $x$; "asymptotically tight" means it really is some constant times $x^2$ for large enough $x$ and not, say, some constant times $x^{1.999}$.

# Answer
> 16 votes
Here's an example explaining it (and a concrete example for David's fine answer).

Suppose you have an algorithm that is given as input an array of integers $A$. The algorithm scans through the array, and increments a counter initially set to zero everytime it sees an element that is an even integer. We can prove the algorithm runs in say $O(n^3)$ time, where $n$ is the number of elements in $A$. But we can also give a *tighter* bound, and say it runs in time $O(n)$. This bound is asymptotically tight: in fact, since reading the input already takes $\Omega(n)$ time, we could be more precise and say the algorithm takes $\Theta(n)$ time.

# Answer
> 1 votes
$\Theta$ means we have both a lower bound and an upper bound. For example if $f(n) = \Theta(n^2)$ then $c\_1 n^2 \<= f(n) \<= c\_2 n^2$ for large n.

However, we have functions that are not always close to the upper bound. For example, $\sin n \cdot n^2 = O(n^2)$, but it is not $\Theta (n^2)$. Still, we cannot reduce the $n^2$. $\sin n \cdot n^2 ≠ o(n^2)$. That makes $n^2$ an asymptotic tight upper bound.

---
Tags: asymptotics
---


title: MSD vs LSD Radix sort

text:
# Question
Title: MSD vs LSD Radix sort
I read the following in CRLS:

I don't understand the text in yellow. Why would `radix sort` not work so well if we sort by their most significant digit? What extra "piles of cards" is it referring to?

Perhaps I'm not able to follow the example with cards, and an example with actual numbers would be best.

---

In case it helps, sorting **naively** by MSD doe not seem to work, even if all values are d-digit numbers:

```
Input   (1)   (2)   (3)
        *      *      *
 321    132   321   321
 522    321   426   522
 132    426   522   132
 426    522   132   426

```

where `(i)` is the result of sorting the previous column by the ith-highest digit.

# Answer
It would work, the only problem is that it will generate a lot of extra piles for the intermediate results that are difficult to track.

if the sorting algorithm sorts the $d$-digit numbers starting from their most significant digit it would create 10 piles at first (one pile for the numbers starting with 0, another one for those starting with 1 and so on) and then sort each pile recursively as explained in the book.

The problem is that to sort the pile of numbers starting with 0 the algorithm needs to create ten more piles (one for the numbers starting with 00, the second for the numbers starting with 01 and so on, the last pile is for the numbers starting with 09).

Thus we have created 19 piles until now. To sort the pile of the numbers starting with 00 we need to create 10 more piles. If this process continues until the $d$ digit are sorted you can imagine that a huge number of piles are created (how many?).

This are the extra piles that the book was referring to.

If you use LSD radix sort you don't have to split the numbers in piles at all. You can just sort the input pile by last digit, then the same pile by the penultimate digit and so on, after $d$ steps you will end up with the expected result.

The intuition is the following: let $d$ be $2$ and let $83$, $19$ and $17$ be the input. The first step on MSD radix sort will place $17$ and $19$ before $83$. Then if you sort the same whole pile by the second digit you will end up with $83$ before $17$ which is wrong. You need to split the pile because you have to "remember" the previous sorting made by the algorithm, which is more "important". Conversely, the first step of LSD radix sort will place $83$ before $17$, then $19$. If you take the whole pile and sort it by the first digit you get $17$, $19$, $83$ which is correct. You don't need to split the pile because the current step of the algorithm is more "important" of the previous ones and it is allowed to "mess up" the previous ordering in any way (for example by placing $83$ after $17$ and $19$). This would work as long as the sorting algorithm used for each digit is stable.
> 1 votes

---
Tags: algorithms, sorting, radix-sort
---


title: Solving equation with $n\log n$

text:
# Question
Title: Solving equation with $n\log n$
Given a computer that takes 1 microsecond for an operation, I'm trying to find the amount of operations this computer can perform in one second, given an algorithm with complexity $O(n\log n)$. I've tried to solve it by the following ways but always get stuck. Note that one second equals $10^6$ microseconds.

##

I've found this post where it's stated that *"there is no simple way"* to solve that but I still want to ask here if there is any different approach to the question from a "computer science perspective".

# Answer
If $n\log n = x$ then $x = e^{\log n} \log n$ and so $\log n = W(x)$, where $W$ is the Lambert $W$ function.

The Lambert W functions is implemented in any popular mathematical software. It can be evaluated using standard techniques such as Newton's method or its second derivative generalization, Halley's method; see the Wikipedia article (under Numerical Evaluation).

Roughly speaking, $n = e^{W(x)} \approx e^{\log x - \log\log x} = x/\log x$. The Wikipedia article contains concrete bounds (under Asymptotic expansions).
> 3 votes

# Answer
No way to say. $T(n) = O(n \log n)$ means there exist constants $c \> 0, N\_0$ so that for all $n \ge N\_0$ it is $T(n) \le c n \log n$. They are *anything*, i.e., it might be valid only for ridiculously large $n$ (large $N\_0$), or even for small $N\_0$, like $N\_0 = 10$, the constant $c$ could be such that all you know is that $T(100) \le \text{one milisecond}$ or $T(100) \le \text{one week}$.
> 3 votes

---
Tags: time-complexity
---


# Question
Title: Injectivity not required for unification algorithms?
When learning about a general unification algorithm, we learned the rule *decompose*, which states unifying

$$G \cup \\{f(a\_0,...a\_k)=f(b\_0,...,b\_k)\\} \Rightarrow G \cup \\{a\_0=b\_0,...a\_k=b\_k\\}.$$

The question of, "What if $f$ is not injective?" stood out to me. Say $f$ is not injective, and we traverse that branch of computation where $f(a\_0,...a\_k)=f(b\_0,...,b\_k) \Rightarrow \\{a\_0=b\_0,...,a\_k=b\_k\\}$ and lead to failure. Is it possible that there's another way to assign $a\_0,...,a\_k$ to $b\_0,...b\_k$ such that it's unifiable?

I was thinking maybe of an example to demonstrate what I mean. This may not be a good example, but say we consider $f(x,y) = x+y$, and we want to unify $f(h(a),g(b)) = f(g(c),h(d))$ then we would fail by assigning $\\{h(a) = g(c), g(b)=h(d)\\}$ by decompose, but succeed in unification if instead we first switch the arguments of $f$ (valid since $f(a,b)=f(b,a)$), which will yield $\\{a \mapsto d, b \mapsto c\\}$.

I was reading a bit about it in this paper on page 6 where they discuss the idea of strictness in terms of decompose, but I don't quite understand it, and more generally how we can perform this unification step of decompose on a general $f$ without somehow backtracking on failure.

# Answer
> 2 votes
Here $f$ is not a mathematical function. Rather, it is a function symbol. Don't think of $f(a,b)$ as the result of evaluating the function at parameters $a,b$. Rather, think of it as a term in a symbolic expression -- it is a syntactic object that is not intended to be interpreted in the way you are interpreting it.

If you like, you can think of it as though every function symbol in a symbolic expression is an injective function; but that's not really accurate, that's just a crude way to think about symbolic expressions.

You can't define $f(x)=x+y$. $f$ is an uninterpreted function symbol. You're not allowed to define a particular function. Rather, $f$ is a stand-in for a function that is not yet defined. One way to think about it is that any conclusions that you draw from unification, are conclusions that should hold for all functions $f$ (not just a single one).

---
Tags: logic, term-rewriting, unification
---


title: Usefulness of consensus number

text:
# Question
Title: Usefulness of consensus number
What information and usefulness does knowing the *consensus number* of a shared object give me?

# Answer
> 1 votes
You probably cannot do much better than quote the abstract of Herlihy's original paper:

> A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a consensus protocol, for proving statements of the form, “there is no wait-free implementation of X by Y.” We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: they cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.

---
Tags: consensus, shared-memory
---


title: Set notation of a grammar

text:
# Question
Title: Set notation of a grammar
Say I have a grammar e.g,

$$\begin{align}S&\to AB\mid abc\\ A&\to aAb \mid \lambda\\ B&\to bBa \mid ba \end{align}$$

Now it is obvious the notation for this would be something like, $$L(G) = \\{a^{i}b^{i}b^{k}a^{k} | i \ge 0, k \> 0\\}$$

My question is how do I account for the starting state going to abc. How can I represent this in set notation? My only thought would be to append $(abc)^{m}$ to the statement and then say something like if i,k == 0 then m = 1. Though I'm not sure if that is allowed?

# Answer
> 1 votes
In contrast to popular thought, the description of a language doesn't have to be of the exact form $$ L = \\{a^i b^j c^k \mid \text{conditions on $i,j,k$}\\}. $$ A language is a set, and you can describe it in exactly the same variety of ways as you describe sets. For example, we can write $$ L = \\{a,b\\}^\* \setminus \\{a^nb^n \mid n \geq 0\\}. $$ In your case, as rici mentions in the comments, you might as well just take a union with $\\{abc\\}$ to account for the additional case.

---
Tags: formal-grammars
---


# Question
Title: Why postfix is used more often than prefix expression?
i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) .But i am not getting any enough information about the popularity reason of postifx expression over prefix expression.

**Why are we not using prefix expression than the postfix expression more often?**

**I am guessing that** ,

1. it's related to the easiness of converting the infix to postfix
2. or the evaulation process of postifx is easy than prefix.

*If so, Please someone elaborate on it.*

thanks.

# Answer
The evaluation is easier for postfix-notation expressions.

The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time:

* operand -\> put it on the stack;
* operator -\> get from the stack the number of values it needs (two for `+`, three for `?:`, one for unary `-` and so on), combine the values using the operator and put the result on the stack.
* when the entire expression is processed, the stack contains only one value; it is the value of the entire expression.

The prefix-notation expressions can be evaluated using a similar algorithm that uses the operands (instead of the operators) to trigger computations. However, it is not that straight-forward; it involves lookups on the top of the stack to find the operator and to decide if enough operands were read for it.

The prefix-notation expressions can also be evaluated from right to left using the same algorithm as for postfix-notation expressions.
> 3 votes

---
Tags: algorithms, algorithm-analysis, mathematical-analysis, stacks
---


title: Sampling of subsets with repeat

text:
# Question
Title: Sampling of subsets with repeat
Given a string S of length n and a positive integer k \<= n, we want to randomly, and with equal probability, choose a string from the set of all strings of length k that may be formed with a subset of the letters of S. For example, if S = daddy and k = 2, we want to choose each of the strings da, dd, dy, ad, ay, yd and ya with equal probability 1/7.

Obviously, one could do this by calculating all possible permutations. However, is there a more efficient way?

# Answer
> 1 votes
Let $l$ be the number of *distinct* characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$.

Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map: $$ M = \\{a \mapsto 1, d \mapsto 3, y \mapsto 1\\}. $$ The idea of our algorithm is to first calculate the *number* of possible permutations of $k$ elements from $M$, and then to use this to generate one randomly.

## Step 1: calculating the number of possible permutations

We use dynamic programming. We actually calculate, more generally, the quantity $$ p\[i,j\] \qquad \text{ for } 0 \le i \le k \text{ and } 0 \le j \le l, $$ which represent the \*number of permutations of length $i$, which use only the first $j$ elements of the map. For example, in the example problem (input "daddy", $k = 2$), we have \begin{align\*} p\[0, 0\] &= p\[0, 1\] = p\[0, 2\] = p\[0, 3\] = 1 \quad \text{(empty string)} \\ p\[1, 1\] &= 1 \quad \text{(strings of length 1 using only a -- so just "a")} \\ p\[1, 2\] &= 2 \quad \text{(strings of length 1 using a and d -- so "a" and "d")} \\ p\[1, 3\] &= 3 \quad \text{("a", "d", and "y")} \\ p\[2, 1\] &= 0 \quad \text{(no strings of length two using only a since only one a is allowed)} \\ p\[2, 2\] &= 3 \quad \text{("ad", "da", and "dd")} \\ p\[2, 3\] &= 7 \quad \text{("ad", "da", "dd", "ay", "ya", "dy", "yd")} \end{align\*}

Now how do we calculate $p$? We can use a recursive algorithm. Let $M\[j\]$ denote the value of $M$ on the $j$th character (so in our example, $M\[1\] = 1, M\[2\] = 3, M\[3\] = 1$). Then $$ p\[i, j\] = \sum\_{i' = 0}^{M\[j\]} \binom{i}{i'} p\[i - i', j-1\]. $$

What this formula says is: pick $i'$ places to put character $j$. For example, in our running example for $p\[2, 3\]$, it says pick $i'$ places to put the character $y$ in a string of length $2$. Then for the remaining $i- i'$ places, we fill them in with a string only using the first $j-1$ characters (which can be done in $p\[i-i', j-1\]$ ways). The variable $i'$ ranges from $0$ to $M\[j\]$ because we can only use character $j$ at most $M\[j\]$ times.

This recurrence allows us to calculate the entire table of $p\[i,j\]$ in approximately $O(nk)$ time.

## Step 2: Picking a permutation at random

The total number of permutations is $p\[k, l\]$. So pick a random number $r$ from $1$ to $p\[k, l\]$.

Now recall the recurrence relation $$ p\[i, j\] = \sum\_{i' = 0}^{M\[j\]} \binom{i}{i'} p\[i - i', j-1\]. $$

Very roughly, we can use this recurrence relation to enumerate the $r$th permutation. To evaluate the $r$th permutation of $p\[i,j\]$ total, evaluate the above sum and locate the term where the $r$th permutation would fall. For example if $r = 4$ and there are $7$ total permutations, and the sum gives you $3 + 4$, then $4$ falls fourth out of $7$, so it falls in the second group. Then, we are looking for the first out of $4$ permutations in the second group, which we can recursively find by picking a random permutation from $p\[i - i', j-1\]$.

---
Tags: algorithms, sampling
---


title: Find CFG for the following language

text:
# Question
Title: Find CFG for the following language
I need to show that the following language is context free:

$$L = \\{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\\}$$

# Answer
> 1 votes
Hint 1: $L = L\_1 \cup L\_2$ for some $L\_1$ and $L\_2$ which are obviously context-free.

Hint 2:

> $L\_1 = \\{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge (\ell \ge n)\\}$

---
Tags: context-free, pushdown-automata
---


# Question
Title: Checking if sequence is almost strictly in ascending order
This was part of my interview questions.

> Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
>
> For instance,
>
> For `sequence = [1, 3, 2, 1]`, the output should be
>
> `almostIncreasingSequence(sequence) = false`
>
> There is no one element in this array that can be removed in order to get a \>strictly increasing sequence.
>
> For sequence = `[1, 3, 2]` the output should be
>
> `almostIncreasingSequence(sequence) = true`
>
> We can remove 3 from the array to get the strictly increasing sequence `[1, 2]`. Alternately, we can remove 2 to get the strictly increasing sequence `[1, 3]`.
>
> The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return `false`.

The conceptual algorithm that the interviewer wanted was below with **Java**:

```
boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

```

but I didn't get the part comparing `sequence[i]` with `sequence[i+1]` and`sequence[i+2]` to increment the counter which are `seq1` and `seq2`. How does this cover all the cases?

# Answer
**It does not** cover all cases! Consider the sequence **\[2, 6, 4, 8, 7\]**. Before the return statement, the values of `seq1` and `seq2` are: $seq\_1 = 2$, $seq\_2 = 0$. So the function would return $True$. However, the sequence is **not** almost strictly increasing, because you need to remove at least two elements from it to obtain an increasing sequence.

So, either the Java implementation is not faithful to the conceptual algorithm, or the conceptual algorithm is **wrong**.

The problem can be solved by finding the length of the longest increasing subsequence (LIS) of the given sequence. Call $n$ the length of the original sequence. If the LIS has length $\ge n-1$, the sequence is almost increasing according to your definition. If the LIS has length $\le n-2$, the sequence is not almost increasing.
> 2 votes

# Answer
Indeed the method almostIncreasingSequence does not cover all the cases. So there must be something wrong about the interview.

Here is **the simplest counterexample, \[2,1,4,3\]**. Because 2,1 and 4,3 are two disjoint decreasing pairs, we need to remove at least two elements to change it into a strictly increasing sequence. That array is not an almost strictly increasing sequence. However, almostIncreasingSequence will return true.

The answer by Vincenzo suggests that longest increasing subsequence can be used to solve this problem. While that algorithm can do the job, it is not easy to implement and it runs in $O(n\log n)$ time-complexity, where $n$ is the length of the given sequence.

Here is **a simple correct method that runs in $O(n)$**. The idea is simple. Once we find an adjacent pair of elements that is not strictly increasing, we check if we can remove one of them so that nearby elements become strictly increasing. If not, then we return false. If yes, then we will check the remaining elements. A standard padding trick is used so that we can check the boundary cases and the ordinary cases uniformly.

```
boolean isAlmostIncreasingSequence(int[] sequence) {
    // Pad the sequence so that we can reason with less cases.
    int[] padded = new int[sequence.length + 2];
    padded[0] = Integer.MIN_VALUE;
    padded[padded.length - 1] = Integer.MAX_VALUE;
    System.arraycopy(sequence, 0, padded, 1, sequence.length);

    int bad = -1;

    // find the first not strictly increasing pair
    for (int i = 1; i < padded.length - 1; i++) {
        if (padded[i] >= padded[i + 1]) {
            bad = i;
            break;
        }
    }

    if (bad != -1) {
        // Can we succeed if we remove the element at bad or bad+1?
        if (padded[bad - 1] < padded[bad + 1] && padded[bad + 1] < padded[bad + 2]
                || padded[bad] < padded[bad + 2]) {
            // all the rest of the padded sequence
            for (int i = bad + 2; i < padded.length - 1; i++) {
                if (padded[i] >= padded[i + 1]) {
                    return false;
                }
            }
        } else {
            return false;
        }
    }

    return true;
}

```
> 0 votes

# Answer
You scan until you find the first two elements that are not in strictly ascending order (in your example 3 is not less than 2). One of them must be removed.

Assume a \[i\] ≥ a \[i+1\]. If i \> 0 and a \[i+1\] ≤ a \[i-1\] then you cannot remove a \[i\], so you have to remove a\[i+1\]. In all other cases you would remove a\[i\].

Then you check that with this item removed, the rest is in strictly ascending order. If you find another item in the wrong order, you return "false".
> 0 votes

# Answer
Strictly ascending requires not to have repeated values after removing one element from the array. Hence there should never be more than one repeated element.

In Python3, `def almostIncreasingSequence(sequence):
 # To check if there are more than one repeated numbers, set() can be used to eliminate repetitions
 # len(x) to find the count of array x
 # len(set(x)) - remove repetition and find count
 if len(sequence) - len(set(sequence)) > 1:
 return False
 # popping each element and checking whether the remaining array is same
 # as the original after sorting one of the copy
 for i, n in enumerate(sequence):
 # list.copy() to make a copy of the array
 temp = sequence.copy()
 temp2 = sequence.copy()
 #list.pop(i) to delete the element at index i
 temp.pop(i)
 temp2.pop(i)
 # list.sort() to sort array in ascending order
 temp.sort()
 if temp == temp2 and (len(temp) - len(set(temp))) == 0:
 return True
 return False`
> -1 votes

---
Tags: algorithms
---


# Question
Title: Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?
A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as in this question.

I've noticed that when solving such tasks, any algorithm for *calculating the number of such* combinatorial objects via a recurrence relation can be transformed into an algorithm to *generate* such combinatorial objects. My question is, is there a name for this technique? Is there a theorem which says when this is true?

**For example,** suppose I want to generate a random sequence of $n$ $1$s and $0$s, where there are no two adjacent $1$s. I can begin by letting $a\[n\]$ be the number of such sequences, and observe that $$ a\[n\] = a\[n-1\] + a\[n-2\]. $$

(This is the Fibonacci relation.) This allows me to efficiently calculate a table of $a\[i\]$ for $i = 1$ to $i = n$. Now if I want to generate a random such sequence, all I have to do is:

**Step 1:** Generate a random value $r$ from $1$ to $a\[n\]$.

**Step 2:** Use the recurrence relation to locate a sub-term which corresponds to the $r$th sequence:

* If $r \le a\[n-1\]$, recursively find the $r$th sequence counted by $a\[n-1\]$, and append a $0$.
* Otherwise, if $a\[n-1\] \< r \le a\[n-1\] + a\[n-2\]$, set $r' = r - a\[n-1\]$, and recursively find the $r'$th sequence counted by $a\[n-2\]$, and append a $01$.

What seems to be going on here is that, given any recurrence relation for $a\[n\]$, I can transform this into a recursive algorithm which returns the $r$th object counted by $a\[n\]$. I'm assuming this is well-known, so I would be interested in any references or classic results about this. In particular, this isn't just specific to the example $a\[n\]$, but should be true for *any* recurrence relation satisfying certain properties.

Also, I think this may be related to some research on random testing.

# Answer
> 1 votes
These are known as ranking and unranking functions. You are right about the correspondence between recurrence relations for counting and unranking algorithms.

---
Tags: reference-request, combinatorics, recurrence-relation, randomness
---


# Question
Title: Context-free grammar for language involving multiplication
I'm struggling to find the context-free grammar for the following language: $$ L = \\{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\\} $$ Any help would be appreciated.

# Answer
Write $L$ in the following way: $$ L = \\{ a^sbc^s : s \in \mathbb{N}^+ \\} \cup \\{ a^sb^2c^{2s} : s \in \mathbb{N}^+ \\} \cup \\{ a^sb^3c^{3s} : s \in \mathbb{N}^+ \\}. $$
> 3 votes

---
Tags: automata, context-free
---


# Question
Title: Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset
### Problem Description

I have a *data state space*: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a parent data set, forming a tree (not a lattice; data sets branch but do not merge.) The root of the tree is an empty data set.

I'm not looking at/exploring the entirety of this data state space. Rather, I have a listing of all the leaf-node data sets which exist in use in the real world. I only care about these leaf-node data sets, and (sometimes) their ancestors.

I wish to find (or create!) a persistent (on-disk, distributed/sharded if necessary) data-structure for storing and querying of these in-use data sets. I would also accept a database management system that happens to have such a data-structure (or assemblage of features to simulate such a data structure) as a feature. I just have a practical need to store and query this data!

### Requirements

This data structure would need the following operations:

* **define** a new data set in the store, in terms of a **parent data-set identifier/handle**; and a **set of key-value "writes"** which would create this data set if applied to the referenced parent;
* **open** the store with respect to a particular data-set identifier, returning a data-set handle;
* **query** the store + data-set handle for a **particular key's value**;
* **query** the store + data-set handle for the key-value pairs in a given **key range**;
* **query** the store + data-set handle for a **dump** of all key-value pairs in the data set.
* (optionally) obtain a **cursor** against a store + data-set handle + initial key, and use it to **iterate** forward/backward through key-value pairs, with each iteration returning a key-value pair.

Constraints imposed by the data:

* Many leaf-node data sets in the state space will contain **billions** of key-value pairs.
* Many leaf-node data sets are more than **10 million levels** "deep" or "high" away from the root.
* Many data sets are trivial changes from their parent, consisting of **one** update or even **zero** updates (but will retain a distinct identity in the zero-update case.)
* Many data sets are non-trivial, consisting of **hundreds of thousands** of updates to their parent.
* Each branch node in the tree has, on average, **1.5 children** (most have only one; some have two; very few have more than two.) The tree mostly consists of long linear segments of nodes, with branch nodes forking between a new "main branch" on one side; and a short, terminal "side branch" on the other.

Operational constraints:

* The **read** operations must be **time-efficient** (i.e. soft real-time/bounded latency), as the point of this data store is to serve read-heavy analytical queries.
* **Insertion** of new data sets into the store must **scale** into the millions without going exponential; but otherwise inserts can be fairly slow, taking on the order of seconds to commit a new data-set definition into the store.
* **Opening** a data set within the store can be time-costly (again ~seconds), though again, this overhead must grow slowly-enough to allow one to open a data-set buried "deeply" in the store. This "free" time can be used to unpack the data set from any compression/delta-encoding format, to cache data or required intermediate data-structures from disk into memory, etc.
* The store must be as **space-efficient on disk** as possible (allowing whatever disk-space overhead is required to satisfy the other constraints.) I don't have petabytes laying around to spread this store onto!

### Discussion

The disk-space usage consideration is where things get interesting, IMHO.

Without a requirement of disk-space efficiency, the naive solution is to just have full copies of every distinct data-set stored separately in their own read-indexed storage files, possibly then distributing distinct data-sets onto their own network shards so read queries can be separately routed to them.

But this naive solution would throw the storage requirements for this state-space (recall, ~billions of KV pairs each, ~millions of nodes) into multi-petabyte territory, and I don't have that kind of space.

Intuitively, from experience tuning analytical database systems, I would expect a *good* on-disk data structure for OLAP backing-storage (including all required indices) to introduce no more than a 10x overhead on top of a change-data-capture representation of the source data. The change-data-capture representation of all these data sets (i.e. the representations that would be fed to the **define** operation above) currently sums to ~50GB; so I'd intuitively expect this data structure would demand no more than ~500GB of disk. Am I crazy to expect that?

I know I can get some easy wins in terms of storage overhead for general "deduplication" of data sets, by just relying on a filesystem with block-level copy-on-write, where each data-set in the state space becomes its own copy-on-write snapshot, and the snapshots form a tree. But this seems like it *wouldn't* scale operationally, because either I'd be using a sorted flat-file data set format (in which case inserts "in the middle" of data cause storage-overhead explosion in descendant snapshots) or I'd be using something like an on-disk LSM tree \[e.g. LevelDB\] or B+-tree \[e.g. LMDB\] (in which case each snapshot would add another "level" to the tree, causing either an explosion of file inodes in the case of LevelDB, or a fragmentation of each file into tiny per-layer extents in the LMDB case), in the end meaning that reads to a million-branch-deep data set in such a store would have quite a lot of overhead at the filesystem bookkeeping level.

I would guess that a *good* data-structure for this would involve, at some level:

* tries (HAMTs?)
* a notion of "keyframes" vs "interstitial frames", for representing the trivial change sets
* a notion of "highly-connected routes" through the tree, where "major branches" are repacked (defragmented?) and "minor branches" are re-stored in terms of their difference from a "major branch"

I'm aware of **Datomic**, which seems to have an architecture and set of operations similar to what I'm looking for; but which supports only a linear timeline, rather than a tree of timeline-branches. I'm unclear on whether its architectural design could be extended to support branching time without fundamental changes.

I'm also aware of what **blockchain** systems (e.g. Ethereum) are doing with *merkle patricia trie*-based storage. I've evaluated doing exactly this, but—at least as blockchains themselves implement this approach—the read performance *doesn't* scale for analytical workloads. (It works for these systems, because their evolution-steps are OLTP workloads, computing almost always against a "main branch" state—the outcome of the previous most-recent computation—which is therefore cached almost-entirely into memory. Everything other than the most-recent "main branch" state is able to be considered "cold." None of this is true for an OLAP use-case; OLAP queries look at arbitrary branches of a state-space at arbitrary times, with no branch or node being "hot.") I would expect that some modification (relaxation?) of this approach might be suitable, though, since the *merkle* aspect of the *merkle patricia tries* used here is only relevant for trustless multi-party state sharing, which doesn't come up in this design.

# Answer
> 1 votes
I recommend you use a persistent map data structure. A reasonable choice would be a persistent binary balanced tree or a persistent hash array mapped trie; with these choices, every operation can be done in $O(\log n)$ time or $O(1)$ time. You can store these data structures on disk and the disk overhead should be not too large: $O(n+\log m)$ or $O(n+m)$, where $n$ is the total number of items stored and $m$ is the number of "define" operations used to construct all of the datasets.

Since you have a read-mostly workload, as an optimization you can use your "opening" to load all of the key values in the data structure into memory and construct an in-memory hashmap that serves as a faster index into the data structure, and throw away this hashmap whenever memory gets tight or when you are done with that data structure; or you can build up such an index on the fly as a cache of where certain keys are located. Or, the data structure might perform adequately for your needs even without this.

---
Tags: data-structures, database-theory, data-compression
---


# Question
Title: Query: Given a graph, is edge x in an optimal TSP tour?
Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.

It may be argued that the complexity of this problem is strictly greater than any co-NP problem. The idea is that it's perhaps impossible to come up with a counter-example, since we need e.g. an optimal tour candidate before we can consider a counterexample (but no optimal tour candidate is given in this problem statement).

On the other hand, it may be argued that the complexity of this problem is strictly smaller than any P-space-complete problem, as our problem may be seen as

$\exists$"a tour A containing x" $\forall$"tours B": (some formula stating that A \<= B)

whereas some probably "minimal" P-space-complete problem has O(n) alternations of $\exists$ and $\forall$: the quantified boolean formula problem (QBF).

Based on this argument, is it reasonable to expect that there's a complexity class between co-NP and PSPACE? Does this particular class have a name? Can we expect to find arbitrarily more such classes by adding another one alternation of $\forall$ or $\exists$ to the previously found such class?

# Answer
The complexity class $\Sigma\_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that $$ x \in L \Longleftrightarrow \exists y \forall z \\, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|). $$ This is the natural location for your problem:

* $x$ is a pair $(G,e)$, where $G$ is a graph and $e$ is an edge of $G$.
* $y$ is a TSP tour.
* $z$ is a TSP tour.
* $f(x,y,z)$ holds if (i) $y,z$ are TSP tours of $G$; (ii) $e \in y$; and (iii) $w(y) \leq w(z)$.

More generally, $\Sigma\_k^P$ is defined similarly with $k$ quantifier alternations, and $\Pi\_k^P$ is defined the same but starting with a universal rather than an existential quantifier. For example, $\Sigma\_1^P$ is NP and $\Pi\_1^P$ is coNP. We also define $\Delta\_k^P = \Sigma\_k^p \cap \Pi\_k^P$, generalizing the class NP∩coNP.

We define $\Sigma\_k^P$-hard and $\Sigma\_k^P$-complete in analog to NP-hard and NP-complete, using polynomial time reductions. The obvious question to ask in your case is whether your language is $\Sigma\_2^P$-complete.
> 5 votes

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


title: Distribution Optimization Algorithm

text:
# Question
Title: Distribution Optimization Algorithm
I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem).

## Problem

Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags.

For example, you might be interested in running an ad with 50000 impressions on the following tags: `javascipt, typescript, react, nextjs, nodejs, webpack`.

StackOverflow "promises" you will get 50000 impressions, but they are free to distribute them across the above tags however they desire (could even be 100% to one tag).

**How should StackOverflow optimize the distribution so that they can sell/deliver the maximum number of impressions?**

For simplicity, assume:

* we know the number of impressions each tag receives per month ahead of time and it doesn't change
* each impressions only belongs to a single tag

## **My Research**

I believe this might be similar to the Knapsack or Bin packing problems.

The simplest way to approach this is with a "first-fit" (or maybe better described as "first come, first-serve") algorithm:

1. Get all active "subscriptions" (impressions & tags), ordered by Created Date ASC
2. For each "subscription", grab the first tag and "consume" as many impressions as we can. If the subscription still has remaining impressions, move to the next tag.
3. Repeat with next subscription

That might play out something like this:

```
==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000

== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme:
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark:
 - javacript:  0
 - typescript: 0

```

The optimization for this solution is clearly horrible. In the example above, while we had more than enough impressions to go around, we allocated the only ones that "Stark" could purchase before we got around to them.

**Is there an official name to this problem and what does the optimal solution look like?**

# Answer
> 2 votes
I think this is actually "just" maximum cardinality bipartite matching, which can be solved optimally in $O(|E|\sqrt{|V|})$ time using the Hopcroft-Karp algorithm.

On one side, you have a vertex for each demanded impression (say, customer A demands 50000 of either "javascript" or "typescript", and customer B demands 10000 "javascript", so 60000 vertices in all), and on the other side you have a vertex for each supplied impression (say, 30000 labelled "javascript" and 15000 labelled "typescript", so 45000 vertices in all). Draw an edge from each demanded impression to every supplied impression of a type that satisfies its impression type constraints (so there would be 45000 edges leaving each of customer A's vertices, and 15000 edges leaving each of customer B's), and solve.

If you have thousands of impressions, you may wind up with millions of edges, which might take too long. If an approximate answer suffices, I would suggest dividing all numbers through by some constant, e.g. 1000, and then multiplying them back up again afterwards. (If this constant divides all input numbers, the solution will remain optimal.)

# Answer
> 2 votes
If you had only one tag, this would become a knapsack problem: in particular, determining whether you could sell all the impressions would be exactly the subset problem. Therefore, the problem is NP-hard.

A plausible approach to solve it in practice would be to use integer linear programming.

---
Tags: algorithms, optimization, knapsack-problems
---


# Question
Title: Applying SVD compression to integral point images
Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular values to construct the the best rank-$k$ approximation of $A$ to accomplish compression for data storage.

I understand that for a floating-point image, the compression rate for SVD is

$$\frac{mn}{k(m+n+1)},\tag{1}$$

as mentioned in a lot of places including some textbooks. For example, a quick internet search gives us this article and this convenient demo link.

Coming back to our case, the entries of $A$ are 8-bit unsigned integers, while we still need to use floating points (32 bits or 64 bits) for the storage of the singular values and vectors (because 8-bits do not seem enough for the precision), it would seem that the compression rate for this case should become

$$\frac{mn}{4k(m+n+1)}, \quad\text {or} \quad \frac{mn}{8k(m+n+1)}.\tag{2}$$

This would render this compression scheme not practical in most cases. For example, using the demo link above, for that default image there, we need at least the first 100 singular values for a less-than-satisfactory compressed image. Using Formula $(1)$, that is assuming the original image is using the floating point data type, the compression rate is $2.40$; but assuming the original image is using the 8-bit unsigned integer data type, using Formula $(2)$, the compressed image becomes at least $0.6$ times bigger than the original one.

Does SVD compression only work for floating point images? What am I missing here?

# Answer
> 1 votes
> Does SVD compression only work for floating point images?

It seems quite obvious that it works for arbitrary images. Whether you are satisfied with the amount of compression or not doesn't really change the fact that it works.

I think looking at the compression ratio is going to lead to misleading results. Suppose you take two images: $I\_1$ uses 8-bit RGB, and $I\_2$ is the same image but captured using 24-bit RGB. Note that it is often fairly challenging to distinguish between two such images, and the differences are often perceptually minor. Now suppose you compress both with lossy compression. Suppose that both compressed images happen the same size. Then the compression ratio of $I\_1$ is 3x worse than the compression ratio of $I\_2$. Does that mean that compression doesn't work for 8-bit RGB images? No, it means that $I\_2$ has a bunch of extra information that isn't semantically relevant. Thus, a compression algorithm that throws away this irrelevant information will achieve a higher compression ratio. That's not because the compression algorithm is better; it's just a reflection of the fact that $I\_2$ has more irrelevant information (or information with low relevance).

And this is exactly the situation you're in. There is no way that the low 8 bits of those 32-bit floating point numbers are perceptually meaningful; no human is going to be able to perceive those. So, if you're capturing an image with 32-bit floats, then some of the bits of those floats are pure noise that are perceptually completely irrelevant. So, of course a compression algorithm that throws away that irrelevant information is going to achieve a higher compression ratio. Does that mean that compression on 8-bit images doesn't work? No, it just means there was less irrelevant information to throw away. This phenomenom is not specific to SVD-based compression; it will likely be true for any form of good lossy compression.

I can always make the compression ratio arbitrarily good by appending a bunch of irrelevant useless information to the input, and then modifying my compression algorithm to throw away the irrelevant information. That doesn't mean I have a better compression algorithm, or that the compression algorithm doesn't work or is unacceptable on the original images.

For all of these reasons, I think a better way to compare the two schemes is by the size of the compressed image, not by the compression ratio. And both variants you describe achieve the same size compressed image, so the apparent difference evaporates.

Second, when you're doing your comparison, there is no reason why you need to hold $k$ fixed. Usually we think of lossy compression as a tradeoff between the size of the compressed image vs the perceptual quality. You have two tunable parameters: $k$, and the number of bits of precision that use for the entries of the outputs of the compression. You are free to choose those arbitrarily to maximize the perceptual quality of the image, for a given image. For instance, instead of using one value of $k$ and 32-bit floats, you might do better to double $k$ and use 16-bit floats. Probably only empirical experiments can help you set those parameters in the optimal way... but you shouldn't assume what the optimal setting will be, or that it will necessarily be the same for both settings (both 8-bit inputs vs 32-bit inputs).

---
Tags: image-processing, data-compression, linear-algebra, matrix, decomposition
---


# Question
Title: Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?
This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an algorithm like DFS that runs in time polynomial in the number of inputs. In this case your input is a graph with $n$ vertices and $m$ edges, and your algorithm runs in time $O(m + n)$.

But we know that in reality we must always consider the lengths of binary encodings when calculating runtime. This is why something like the dynamic programming algorithm for Knapsack isn't actually polynomial.

DFS takes in $n + m$ "objects" as input. If we say that each object takes a fixed number of bits (e.g., each vertex takes 1 bit to encode and each edge takes 3 bits), then it makes sense to me that the algorithm is indeed polynomial in the input. But is there any reason that we need a fixed number of bits for each object? Might there exist a more powerful encoding of the input that takes $\log (m+n)$ bits, suddenly making the algorithm exponential?

One thought I had was just that there is an assumption that any practical encoding in the real world is going to require a fixed number of bits for every extra "object" given as input, whether the objects be vertices, letters in a string, etc.; thus it is most useful to think about runtimes this way. But I want to make sure since I think this is fundamental to my understanding. Thanks in advance!

# Answer
There are $2^{n^2}$ labelled directed graphs on $n$ vertices. Therefore, any such graph requires at least $n^2$ bits to represent it. So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs.

If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ of them, which for $m \ll n^2$ is approximately $(e n^2/m)^m / \sqrt{2\pi m}$, and thus you'll need at least $m \lg (n^2/m) + O(m)$ bits to represent all of them. Notice that this is $\Omega(m)$, so there is no hope for an encoding scheme that uses only $O(\log m)$ bits (or $O(\log(m+n))$ bits) and can represent all such graphs.

Of course, you can consider encodings that are logarithmically short, but they can only express a tiny fraction of all possible graphs. Yes, if you wanted to represent the input in that way and solve a reachability problem on such a graph, then ordinary DFS would take time exponential in the size of the input.

Related: You might be interested in succinct data structures.
> 3 votes

---
Tags: runtime-analysis
---


title: Minimizing DFA built on set of words

text:
# Question
Title: Minimizing DFA built on set of words
A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and then minimizing such automata. So it is very interesting for me is there some algo using it to solve my problem.

P. S. The problem must be quite common because of DFA connection with regexps, and at the same time its statement seems like special case, so I think I am missing some simple idea.

# Answer
There is clearly no sublinear-time algorithm; any algorithm needs to look at all words in the input to have a hope of being correct.

There is a straightforward algorithm to construct a trie that recognizes these words in linear time. The trie is a DFA, but not a minimal DFA.

The trie is acyclic, and apparently there are algorithms for minimizing an acyclic DFA in linear time, so this yields a linear-time algorithm to construct such a minimal DFA. See for example

Johannes Bubenzer. Minimization of Acyclic DFAs. Proceedings of PSC 2011.
> 4 votes

---
Tags: algorithms, finite-automata, formal-grammars
---


# Question
Title: Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm
I have a collection of $n$ vectors $x\_1, ..., x\_n \in \mathbb{R}\_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to the uniform norm. That is, find the (possibly not unique) set $W^\* \subset \\{x\_1, ..., x\_n\\}$ such that $\left| W^\* \right| = k$ and

$$W^\* = \arg\min\limits\_{W \subset \\{x\_1, ..., x\_n\\} \land \left| W \right| = k} \left\lVert \sum\limits\_{v \in W} v \right\rVert\_{\infty}$$

The brute-force solution to this problem takes $O(dkn^k)$ operations - there are ${n \choose k} = O(n^k)$ subsets to test, and each one takes $O(dk)$ operations to compute the sum of the vectors and then find the uniform norm (in this case, just the maximum coordinate, since all vectors are non-negative).

My questions:

1. Is there are a better algorithm than brute force? Approximation algorithms are okay.

One idea I had was to consider a convex relaxation where we assign each vector a fractional weight in $\[0, 1\]$ and require that the weights sum to $k$. The resulting subset of $\mathbb{R}^d$ spanned by all such weighted combinations is indeed convex. However, even if I we can find the optimum weight vector, I am not sure how to use this set of weights to choose a subset of $k$ vectors. In other words, what integral rounding scheme to use?

I have also thought abut dynamic programming but I'm not sure if this would end up being faster in the worst-case.

2. Consider a variation where we want to find the optimal subset for every $k$ in $\[n\]$. Again, is there a better approach than solving the problem naively for each $k$? I think there ought to be a way to use the information from runs on subsets of size $k$ to those of size $(k + 1)$ and so on.
3. Consider the variation where instead of a subset size $k$, one is given some target norm $r \in \mathbb{R}$. The task is to find the largest subset of $\\{x\_1, ..., x\_n\\}$ whose sum has uniform norm $\leq r$. In principle one would have to search over $O(2^n)$ subsets of the vectors. Do the algorithms change? Further, is the decision version (for example, we could ask if there exists a subset of size $\geq k$ whose sum has uniform norm $\leq r$) of the problem NP-hard?
4. Suppose we now know that our vectors $x\_i$ all come from $\\{0, 1\\}^d$. Does anything change?

# Answer
> 1 votes
The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent\_set\_(graph\_theory) or set packing.

One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v\_1,\dots,v\_n$, and then minimize $t$ subject to the constraints $\\|\sum\_i v\_i x\_i \\|\_\infty \le t$ and $\sum\_i v\_i = k$. Note that $\\|\sum\_i v\_i x\_i \\|\_\infty \le t$ iff $-t \le \sum\_i v\_i x\_{ij} \le t$ for all $j$, so this can be expressed using linear constraints. Then, apply an off-the-shelf ILP solver and hope it terminates in a reasonable amount of time.

(The ILP solver will probably apply methods such as solving the associating linear program and then applying randomized rounding, so you don't need to implement it yourself.)

If $d$ is very small, it might be possible to solve the problem in something like $\tilde{O}(dkn^{k/2})$ time using meet-in-the-middle search combined with a nearest-neighbor data structure, but I haven't worked out the details, and I expect it won't scale to large $d$.

---
Tags: time-complexity, optimization
---


title: Complexity class of an algorithm

text:
# Question
Title: Complexity class of an algorithm
What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time?

As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm has the same complexity as $n^{\mathcal{O}(1)}$, which would be in $P$?

# Answer
> 2 votes
No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$. No, it certainly does not have the same runtime. See Sorting functions by asymptotic growth.

There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably not much more to say.

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


# Question
Title: How can an existential type be defined in terms of universal type?
In *Types and Programming Languages* by Pierce, how does the following achieve the definition of an existential type in terms of universal type, by polymorphic version of Church encoding of pairs?

> **24.3 Encoding Existentials**
>
> **The encoding of pairs as a polymorphic type in §23.4** suggests a similar **encoding for existential types in terms of universal types**, using the intuition that an element of an existential type is a pair of a type and a value:
>
> ```
> {∃X,T} := ∀Y. (∀X. T→Y) → Y.
>
> ```
>
> That is, an existential package is thought of as a data value that, given a result type and a continuation, calls the continuation to yield a ﬁnal result. The continuation takes two arguments—a type X and a value of type T—and uses them in computing the ﬁnal result.

To complete the quote, the polymorphic version of Church encoding of pairs of numbers is given in Exercise 23.4.8 (p349 p546):

```
pairNat = λn1:CNat. λn2:CNat.
λX. λf:CNat→CNat→X. f n1 n2;
fstNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n1);
sndNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n2);

```

which is further generalized to pairs of elements of any types, on p352

> we use the abbreviation Pair X Y (generalizing the PairNat type from Exercise 23.4.8) for the Church encoding of pairs with ﬁrst component of type X and second component of type Y:
>
> ```
> Pair X Y = ∀R. (X→Y→R) → R;
>
> ```
>
> The operations on pairs are simple generalizations of the operations on the type PairNat above:
>
> ```
> > pair : ∀X. ∀Y. X → Y → Pair X Y
> fst : ∀X. ∀Y. Pair X Y → X
> snd : ∀X. ∀Y. Pair X Y → Y
>
> ```

Thanks.

# Answer
> 5 votes
As a general recipe, to figure out how to encode a type `A`, write down

```
∀Z . (A → Z) → Z

```

and massage it to something that does not involve `A`, using basic isomorphisms, such as currying and uncurrying. For example, if we plug in `A := X + Y` we get:

```
∀ Z . (X + Y → Z) → Z           ≅
∀ Z . (X → Z) × (Y → Z) → Z     ≅
∀ Z . (X → Z) → (Y → Z) → Z

```

You can also read the above lines as a sequence of logical equivalences. So this gives us the encoding of `X + Y` in terms of the universal quantifier.

I do not understand why in your question you speak about existential types, but since you do, it is worth explaining the encoding of `∃ X . B(X)` in terms of  this way:

```
∀ Z . ((∃ X . B(X)) → Z) → Z    ≅
∀ Z . (∀ X . (B(X) → Z)) → Z

```

Again, you can read the equivalence either as a type isomorphism or a logical equivalence in logic, using the fact that $(\exists x . \phi(x)) \Rightarrow \psi$ is equivalent to $\forall x . (\phi(x) \Rightarrow \psi))$.

# Answer
> 0 votes
At chapter 5 of TaPL, we saw that in untyped lambda calculus.

```
pair f s = \b . b f s
fst p = p tru
snd p = p fls

where
tru = \t. \f. t
fls = \t. \f. f

```

This definition of pair is to be typed now. Here, `b` takes two arguments `f:F` and `s:S` and we assume the resulting type is `R`. so,

```
b : F -> S -> R
b f s : R

```

now we apply quantification to this `R` which can be any type. so we will get the typed version ;

```
pair f s : ∀R. (F -> S -> R) -> R

```

which should result in

```
Pair F S = ∀R. (F -> S -> R) -> R

```

Then assigning `F = ∃X`, `S = T` , and `R = Y`, we get;

```
Pair (∃X) T = ∀R. ((∃X) -> T -> Y ) -> Y

```

, and uncurrying can reach the following result;

```
Pair (∃X) T = ∀R. (((∃X) x T )-> Y ) -> Y

```

which is the same with

```
Pair (∃X) T = ∀R. ((∃X. T )-> Y ) -> Y

```

and it is equivalent to

```
Pair (∃X) T = ∀R. (∀X. T -> Y ) -> Y

```

---
Tags: programming-languages, type-theory, polymorphisms, types-and-programming-languages
---


# Question
Title: Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?
I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being negative results about decidability and established by diagonal arguments (and in the 1930's), so they must somehow be two ways to view the same matters. And I thought that Turing used a universal Turing machine to show that the halting problem is unsolvable. (See also this math.SE question.)

But now that (teaching a course in computability) I look closer into these matters, I am rather bewildered by what I find. So I would like some help with straightening out my thoughts. I realise that on one hand Gödel's diagonal argument is very subtle: it needs a lot of work to construct an arithmetic statement that can be interpreted as saying something about it's own derivability. On the other hand the proof of the undecidability of the halting problem I found here is extremely simple, and doesn't even explicitly mention Turing machines, let alone the existence of universal Turing machines.

A practical question about universal Turing machines is whether it is of any importance that the alphabet of a universal Turing machine be the same as that of the Turing machines that it simulates. I thought that would be necessary in order to concoct a proper diagonal argument (having the machine simulate itself), but I haven't found any attention to this question in the bewildering collection of descriptions of universal machines that I found on the net. If not for the halting problem, are universal Turing machines useful in any diagonal argument?

Finally I am confused by this further section of the same WP article, which says that a weaker form of Gödel's incompleteness follows from the halting problem: "a complete, consistent and sound axiomatisation of all statements about natural numbers is unachievable" where "sound" is supposed to be the weakening. I know a theory is consistent if one cannot derive a contradiction, and a complete theory about natural numbers would seem to mean that all true statements about natural numbers can be derived in it; I know Gödel says such a theory does not exist, but I fail to see how such a hypothetical beast could possibly fail to be sound, i.e., also derive statements which are false for the natural numbers: the negation of such a statement would be true, and therefore by completeness also derivable, which would contradict consistency.

I would appreciate any clarification on one of these points.

# Answer
I recommend you to check Scott Aaronson's blog post on a proof of the Incompleteness Theorem via Turing machines and Rosser's Theorem. His proof of the incompleteness theorem is extremely simple and easy to follow.
> 38 votes

# Answer
Neel Krishnaswami's answer to *Halting problem, uncomputable sets: common mathematical proof?* on CSTheory points to references connecting the above results under the umbrella of category theory.
> 21 votes

# Answer
(This is supposed to be a comment to Suresh's answer, but it's simply too long to fit there. So I apologize in advance that it doesn't really answer Marc's question.)

I find Neel's answer *Halting problem, uncomputable sets: common mathematical proof?* on CSTheory and Andrej Bauer's blog post unsatisfactory for two reasons.

First, we don't usually need all the category-theoretic jargon to explain the connection. The existence of an undecidable language is implied by Cantor's Theorem, which has a very elementary diagonal proof. The reason is that the set of programs is equinumerous to $\mathbb{N}$. On the other hand, since each language can be seen as a subset of $\mathbb{N}$, and thus the set of all languages is equinumerous to $\mathcal{P}(\mathbb{N})$. By Cantor's Theorem, there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, and thus we know there must exist an undecidable language.

Second, the above proof is unsatisfactory since we also want to "see" example of a reasonable undecidable language. The above proof can be seen as a counting argument and thus not really "constructive" in that sense. Turing discovered the halting problem as such an example.
> 17 votes

# Answer
Universal Turing machines are useful for some diagonal arguments, e.g in the separation of some classes in the hierarchies of time or space complexity: the universal machine is used to prove there is a decision problem in $\mbox{DTIME}(f(n)^3)$ but not in $\mbox{DTIME}(f(n/2))$. (Better bounds can be found in the WP article)

However, to be perfectly honest, if you look closely, the universal machine is not used in the \`negative' part: the proof supposes there is a machine $K$ that would solve a time-limited version of the halting problem and then proceeds to build $¬KK$. (No universal machine here) The universal machine is used to solve the time-limited version of the halting problem in a larger amount of time.
> 6 votes

# Answer
A slightly weaker form of Gödel's first incompleteness theorem can be derived from the undecidability of the Halting problem with a short proof. The full incompleteness theorems also have a short proof which is similar to the one for undecidability of the Halting problem. I highly recommend the whole series (or at least the previous part) for context. The proofs are based on Ryan O’Donnell's brilliant course slides.)
> 3 votes

# Answer
"If not for the halting problem, are universal Turing machines useful in any diagonal argument?"

Rice's theorem is essentially the generalization of diagonalization against Turing machines. It shows that there is absolutely no property about Turing machines that you can decide for all Turing machines with a single algorithm unless that property holds for all Turing machines or no Turing machines. Note the fact that the property holding for all Turing machines or no Turing machines prevents the diagonalization object from being a Turing machine, therefore it can't be on the list in the first place to contradict the decision about the property. Indeed this is the *only* thing that prevent the diagonalization object from being on the list and contradicting the decision about the property, which is all properties of Turing machines are undecidable. This pattern of the diagonalization object needing to be a member of the list of things that you're trying to make a decision about, and yet negate the decision, is the critical abstraction that Lawvere's theorem (referenced in the link in Suresh's answer) captures in order to fully generalize the notion of diagonalization. Now, since we know by experience that nearly every diagonalization seems to have the common property of leading to some extremely important result in mathematical logic, that makes Lawvere's theorem quite the interesting tool.
> 0 votes

---
Tags: computability, logic, halting-problem, incompleteness
---


# Question
Title: an algorithm for detecting if noisy univariate data is constant or is sum of step functions
In an explicit algorithm I'm writing, there is a certain stage where I need to determine whether or not a certain noisy univariate data is constant or is sum of step functions.

For example, defining foo as the algorithm I'm after (writing in Python):

```
assert foo([0]*20) == False
assert foo([0]*20 + [1]*20) == True
assert foo([0]*20 + [5]*30 + [1]*70) == True

```

\- The data in the examples is not noisy, but assume the real one is (just a bit, one can pinpoint where a step might take place by observing the plot of the data.)

I'd be happy to hear any ideas.

# Answer
> 1 votes
Every possible observation is consistent with a sum of step functions: one can use one step function per data point and fit any possible sequence of observations. So, the question is not well-posed. You'll probably need to impose some kind of restriction or prior on the set of sum-of-step functions you're willing to accept (e.g., a sum of at most 3 step functions).

If you make the question well-defined, it might be answerable in a principled way using maximum likelihood. Let $\mathcal{H}\_0$ denote the set of constant functions, and $\mathcal{H}\_1$ the set of sum-of-step functions you are willing to accept (e.g., with a limit on the number of step functions you're summing). Let $\vec{x}$ denote the observed data. Fix a probabilistic noise model. Let $L(f)$ denote the likelihood of function $f$, i.e., the probability of observing $\vec{x}$ given that the true underlying function is $f$. Let $L(\mathcal{H}\_0) = \max \\{L(f) \mid f \in \mathcal{H}\_0\\}$ and $L(\mathcal{H}\_1) = \max \\{L(f) \mid f \in \mathcal{H}\_1\\}$. Then a maximum-likelihood decision rule would be: infer that the underlying data is constant if $L(\mathcal{H}\_0) \ge L(\mathcal{H}\_1)$, otherwise infer that the underlying data is a sum of step functions.

To implement this, you'll need an algorithm to compute $L(\mathcal{H}\_0)$ and $L(\mathcal{H}\_1)$, which will in turn depend on the noise model. Computing $L(\mathcal{H}\_0)$ is likely to be straightforward for reasonable noise models; e.g., if you assume iid Gaussian noise, then $L(\mathcal{H}\_0)$ amounts to computing the average of the data points, choosing a constant function that is always equal to that average, and computing its likelihood. Computing $L(\mathcal{H}\_1)$ (assuming you have a restriction on the number of step functions you'll accept) is a little trickier but is doable using dynamic programming.

From a pragmatic perspective, you might also be interested in changepoint detection.

---
Tags: algorithms, time-series-analysis
---