# Question
Title: Succinct bounded-sum array with $O(1)$ access
Assume we have a $n$ sized integer array $A$, and that we know that $\sum\_{i\in\[n\]}A\[i\] \le M$.

Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written in $O(1)$ time), and that $M=n^{O(1)}$.

A standard implementation could allocate $\lceil \log\_2 M\rceil$ bits per cell, resulting in a $n\cdot \lceil \log\_2 M\rceil$ bits array.

Arithmetic encoding allows us to encode the array using $$\left\lceil\log\_2{n + M \choose M}\right\rceil\approx n\log\left(\frac{M}{n}\right)$$

bits, but does not allow $O(1)$ time operations.

> **Is there a succinct encoding (say, of size $n\log\left(\frac{M}{n}\right)+O(n)$) that allows $O(1)$ time operations?**

The required operations are standard array operations -- retrieving and setting the value of $A\[i\]$ for any $i\in\[n\]$.

# Answer
"Improved Address-Calculation Coding of Integer Arrays" by Elmasry et al. may be state of the art: they store such an array in $n \lg(1 + M/n) + O(n)$ bits, perform point reads in $O(\lg \lg M)$ time, and perform point updates in $O(\lg^2 M)$ time.
> 2 votes

# Answer
Raman, Raman, and Rao is a standard reference for rank/select in O(1) time. This solves your problem for the special case of a static array, i.e., you can retrieve $A\[i\]$ in $O(1)$ time, but not update $A$: see the third bullet item in their abstract. The rank operation can be used to determine membership, and the select operation retrieves the $i$th element of the array. Their data structure requires $o(n)+O(\lg \lg m)$ extra space beyond the minimum.

The conclusion of their paper also mentions a lower bound if you want to support insert, delete, rank, and select. I don't know if that's applicable here.
> 2 votes

---
Tags: algorithms, data-structures, arrays, encoding-scheme
---


# Question
Title: Efficiently finding duplicates in lists of numbers
I decided to try my hand at solving the knapsack problem.

My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the objects to fit into the knapsack. The $i$ tables will then be sorted. Then for each of the $k$ numbers to be tested, I'll run a binary search on the sorted arrays.

I realised that there may be sums which repeat. I feel like recording them will be unnecessary waste of space.

So I want to determine if for any new number $k$ to be added to the list, if $k$ is a duplicate of any number in the list. It is trivial to just search the list, but this is too inefficient, and takes $O(n^2)$ operations, making the trade off with space complexity a bad deal.

I wanted a linear time algorithm for solving this problem. I thought of a function, which takes in inputs, and the function is such that if any new input is the same as a previous input, the function will provide a certain known output. This function should work in constant time or at worst, logarithmic time.

I have tried several means of constructing the function but they failed.

# Answer
Use any efficient set data structure, based e.g. on hashtables or balanced search trees.

Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will come up with.

That said, you may want to check out *pseudo-polynomial* algorithms for Knapsack, and problem variants that have polynomial-time algorithms.
> 4 votes

---
Tags: algorithms, data-structures, search-algorithms, lists
---


# Question
Title: Why use maximum likelihood for word prediction?
According to https://www.tensorflow.org/tutorials/word2vec/, the standard approach for predicting the next word in a word sequence is maximum likelihood. The predicted next word is the word that maximizes

$$P(w\_t|h)=\frac{\exp(\text{score}(w\_t,h))}{\sum\_{w'}\exp(\text{score}(w',h))}.$$

To me, it seems that the word predicted from this model is always the word with the maximum score, in which case we could just use the score function for prediction.

What does maximum likelihood provide that a simple score function does not?

# Answer
That approach *is* using a score function (in a particular way). It is also using maximum likelihood. Both ways of describing the approach are valid.

Why is it useful to think about this in terms of maximum likelihood? Because it gives a more systematic way to think about this problem and others like it.

If we just want to think about maximizing a score function, the question that raises is -- what score function should we use? How do we choose one? It sounds arbitrary.

In contrast, the maximum-likelihood approach gives us a principled way to choose the function. Here is how to derive that formula, given the maximum-likelihood principle. First, they have apparently decided to use the following approximation for the probability of seeing $w\_t$ as the next word, given history $h$:

$$P(w\_t,h) = \exp(\text{score}(w\_t,h)).$$

Once you've decided to do that, then by the definition of conditional probability it follows that

$$\begin{align\*} P(w\_t|h) &= \frac{P(w\_t,h)}{P(h)}\\ &= \frac{P(w\_t,h)}{\sum\_{w'} P(w',h)}\\ &= \frac{\exp(\text{score}(w\_t,h))}{\sum\_{w'}\exp(\text{score}(w',h))}. \end{align\*}$$
> 1 votes

---
Tags: natural-language-processing
---


# Question
Title: Closest arithmetic progression to an array
Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers: $1, 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to $10^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N)$, where $M$ is the maximum integer value of an array?

# Answer
> 3 votes
Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a\_i-(ix+k)|$ is minimized. Fix $x$ and replace $a\_i$ by $b\_i=a\_i-ix$. Now the goal is to minimize $\sum|b\_i-k|$, so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x$, it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum\_{b\_i\in upper\\,half}b\_i-\sum\_{b\_i\in lower\\,half} b\_i$. Substitute $b\_i$ by $a\_i-ix$ and we'll get a formula like $c-(\sum\_{b\_i\in upper}i-\sum\_{b\_i\in lower}i)x$, which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes.

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b\_i\<b\_j$ but after this point $b\_i\>b\_j$. This only happens when $i\<j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by $2(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M)$, the total complexity is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)

# Answer
> 2 votes
The continuous case is that of finding the Least absolute deviation. Not easily tractable, but you may find libraries that are more efficient that the LP formulation.

Iteratively reweighted least-squares is not too hard to implement yourself. If you are not looking for the optimum, a simple least-square could do.

# Answer
> 0 votes
Why not compute the mean value of the consecutive differences in the array and use it as a progression value? The mean will naturally be a real value, however you could always round it or ceil it. This gives you 2 progression values. You could try both and use the one with less distance. This way the algorithm might run in $O(N)$ time. Correct me if I misunderstood.

---
Tags: algorithms, dynamic-programming, arithmetic, linear-programming
---


# Question
Title: Are problems in NP decidable in polynomial time by NDTMs, or just recognisable?
So if we have a problem in NP, does that mean that we can create, by definition, a NDTM that always accepts or rejects in polynomial time? The alternative I'm thinking of would be if the NDTM could only be guaranteed to accept in polynomial time. Rejecting could take longer or forever.

# Answer
The decision problems studied in computational complexity theory are all *decidable*. One cannot define the worst-case time complexity for Turing machines that may fail to halt.
> 5 votes

# Answer
First of all, you need to understand how a nondeterministic algorithm works. There are several different ways of conceptualizing nondeterminism, one of which is by allowing the machine to "guess" bits. We can formalize this as follows: the machine has access to an additional "witness" tape, whose semantics we discuss below.

A polynomial time nondeterministic machine is a machine that terminates in polynomial time (and in particular, always halts), has access to a witness tape, and when halting, either *accepts* or *rejects*. Such a machine accepts a language $L$ if:

1. For every $x \in L$, there is a way to initialize the witness tape so that the machine accepts on input $x$. Other initializations of the witness tape can cause the machine to accept or reject; but we are promised that there is at least one initialization that does cause the machine to accept.
2. For every $x \notin L$, the machine always rejects, no matter how we initialize the witness tape.

So the machine always runs in polynomial time, and it may accept or reject, depending on both the input and the contents of the witness tape. The language that such a machine accepts consists of all inputs for which *some* setting of the witness tape causes the machine to accept.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?
Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia):

```
BronKerbosch1(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

```

I have read that the time complexity of some modified versions of this algorithm is $O(3^{n/3})$, but I can't seem to find the running time complexity of the simple version anywhere.

# Answer
> 4 votes
The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of *ordered cliques*, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is $$ \sum\_{k=0}^n n(n-1)\cdots(n-k+1) = \sum\_{k=0}^n \frac{n!}{(n-k)!} = n! \sum\_{k=0}^n \frac{1}{k!} \approx e \cdot n!. $$ When the maximum clique has size $k$, the number of recursive calls is at most $$ 1 + n + n(n-1) + \cdots + n(n-1)\cdots(n-k+1) \leq 2n^k. $$ Conversely, if you run the algorithm on a complete $k$-partite graph, then the number of recursive calls will be $\Omega(n^k)$.

---
Tags: graphs, time-complexity, clique
---


title: Intersection with a finite set

text:
# Question
Title: Intersection with a finite set
If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular?

This question arises from another question which says

Show that if $L$ is not a CFL and $F$ is finite then $L - F$ is not a CFL.

Now $L = (L - F) ∪ ( L ∩ F)$.

Now if I am able to prove that $L ∩ F$ is finite or regular than I can arrive at a contradiction as follows:

If $L ∩ F$ is finite or regular then union with $L-F$ will be a CFL, therefore $L$ will be a CFL, which is a contradiction.

But my problem is assuming anything about $L ∩ F$.

What will be the properties of this intersection?

# Answer
There is no need to consider the intersection $L \cap F$. If $F$ is finite, then so is $L \cap F$, but that is not a useful fact here.

Insteed, one should proceed by contradiction. Suppose $L \setminus F$ were a context-free language. Then there exists a context-free grammar $G\_1 = (V\_1,\Sigma,R\_1,S\_1)$ such that $L(G\_1) = L \setminus F$. But since $F$ is finite, then $F$ is trivially a context-free language. Let $G\_2 = (V\_2,\Sigma,R\_2,S\_2)$ be a context-free grammar such that $L(G\_2) = F$.

But then $G = (V,\Sigma,R,S)$ where $S \notin V\_1 \cup V\_2$ and

$$V = V\_1 \cup V\_2 \cup \\{ S \\}$$ $$R = R\_1 \cup R\_2 \cup \\{ S \rightarrow S\_1, S \rightarrow S\_2 \\}$$

is a context-free grammar such that $L(G) = L$. This is a contradiction.
> 3 votes

# Answer
Any subset of a finite set is finite.

The intersection of two sets is a subset of each.
> 0 votes

---
Tags: regular-languages, context-free, automata, finite-sets
---


title: Dijkstra's Algorithm

text:
# Question
Title: Dijkstra's Algorithm
I have recently implemented Dijkstra's Algorithm to the shortest path between all pairs of nodes in the graph. I have implemented this code in Java. As instructed I am using a linked list to represent the adjacency matrix. As instructed, I am running my algorithm for a complete graph. The running time for a 1000 node complete graph is about 361 minutes. For 2000 nodes, my program has been running for close to a day, and it is still running.

I would like to run this for a complete graph of 6000 nodes but the running time is going to be too long. I am wondering, if this is too be expected.

Bob

# Answer
> 2 votes
Dijkstra has running time $\mathcal{T}(G) \in \Theta(|E| + |V| \log |V|)$. If the graph is dense then $|E| \in \Theta(|V|^2)$, which means that $\mathcal{T}(G) \in \Theta(|V|^2)$.

A quadratic running time means that a graph with twice as much nodes will take four times as much time to be processed. If $1000$ nodes required $6$ hours, then it is not surprising that $2000$ nodes will take about one day.

As you know, constants depend on the machine you're running your code on, it is therefore impossible to judge the speed of your code having the clock running time as the only datum; however your times strike me as particularly high for a reasonably modern personal computer, I would expect them to be a couple of orders of magnitude lower.

---
Tags: algorithms, graphs
---


title: Why are directed graphs important?

text:
# Question
Title: Why are directed graphs important?
We have been reading about algorithms for MST, strong-connectivity, routing, etc. in directed graphs.

Also recently people have been doing research for dynamic and fault tolerant algorithms for directed graphs.

But I was wondering if there are any practical applications where the underlining graph network is "Directed". Other than social-networks all problems that I could think of like rail/road network, Internet network, etc. deal with undirected graphs only.

Edit 1: I understand that these can be used to model some scenarios where links are directed but I was wondering how often these scenarios occur in real-world, and how important is study of fault tolerance for directed graphs.

# Answer
> 38 votes
Recalling that a *directed graph* is a graph where the edges have an associated direction with them.

Using a directed graph you can represent *asymmetrical* relationships between nodes, while in undirected graph we can represent only *symmetrical* relationships.

Practically, using a directed graph you can represent:

* **Road networks** (using a directed graph you can represent streets' direction);
* **hyperlinks connecting web pages**;
* **dependencies in software modules**;
* **prey-predator relationships**;
* **deterministic finite automaton**.

Besides these classical examples, you can depict many other real-world scenarios (financial trade, scheduling, infectious disease, citation, control flow, etc) that needs an ordered relationship \[1\].

# Answer
> 5 votes
Directed graphs do exist. As mentioned in the comments, Directed Acyclic Graphs (DAGs), in particular, are *tremendously* useful in many computational tasks such as the compiling of code.

Also, its worth noting that most directed graph algorithms can be used in the undirected case simply by replacing each undirected edge with two directed edges. The dual of this, trying to make a directed graph out of an undirected graph, cannot be done for most algorithms.

# Answer
> 3 votes
The beginnings of topological sorting (a fundamental operation on directed acyclic graphs) lie in networks of dependencies in project management, specifically the PERT method. Kahn and Lasser both cite PERT in their papers and base their examples on it, eg

> A PERT network of 30,000 activities can be ordered in less than one hour of machine time.

Online job scheduling is still done with this type of network; for instance an ETL system schedules jobs to run only after the jobs that provide their input data have run.

# Answer
> 2 votes
Answer: From the OP I deduce that the question is actually related to SDGs (Signed Directed Graphs). So here is my answer which addresses basic directed graphs then leads on to SDGs.

Directed graphs are widely utilized in fault-tree analysis in industrial systems. As you eliminate causes of a fault you follow the directed graph to explore other possibilities.

Directed graphs are utilized to prevent counterproductive revisiting of nodes which have been effectively eliminated. In fault diagnosis, often time to restoration of service is critical. In complex industrial systems there is always a parallel tree based on time which can lead to total system shutdown if the fault is not corrected within various time limitations. Going back and forth would be more likely to lead to total failure, which can cause restoration operations which are much more time-consuming (like draining tanks and pipelines in order to restart a refinery).

It is like trimming a tree branch - no need to go back to the trunk when you are trying to find a single twig.

SDGs have the additional property of giving guidance based on probabilities or thresholds in order to help make decisions as the tree is traversed.

Here is a link to a good book on the subject, called Fault Detection and Diagnosis in Industrial Systems (page 224), where it describes the benefits of SDG-based diagnosis:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

---
Tags: graphs, fault-tolerance
---


# Question
Title: Running time of algorithms that sometimes loop forever
Consider the following algorithm that computes the sum of two integers (toy example):

```
INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

```

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!

# Answer
The textbook *Computational Complexity: A Modern Approach* by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class *cannot* capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.
> 5 votes

# Answer
I doubt this idea has been studied because, to me, it doesn't seem at all useful. The only thing that would allow you to use your example algorithm is the fact that you have an exact running time bound on the terminating option, which means that you can detect that you were in the non-halting case, abort and restart. In general, of course, you can't detect that you're in a non-halting case, so you can't use this trick. Also, the trick relies on the algorithm being probabilistic. In a deterministic algorithm, even if you could detect the infinite loop, you'd only be able to return "I don't know", which isn't a correct answer to whatever problem you're trying to solve.

The closest concept I'm aware of is Las Vegas algorithms. These are randomized algorithms that always produce the correct answer on termination, and that terminate in expected finite time. Indeed, the abort-and-restart version of your example algorithm is an example of a Las Vegas algorithm – in expectation, you need one abort (assuming the coin is unbiased).
> 2 votes

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


title: Contained optimal combination of inputs

text:
# Question
Title: Contained optimal combination of inputs
I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to **select the optimal combination of players** with the **highest combined score** (i.e. a fantasy football formation) **within a $50,000 budget**, where a lineup must consist of the following formation:

* Goalkeeper x1
* Defender x2
* Midfielder x2
* Forward x2
* Utility x1 (can be any position apart from GK)

Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one *not already used* non-goalkeeper as a "utility" (from the 100 - 18 = 82).

Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.

**What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment** (i.e. there are trillions of possible combinations)?

# Answer
> 3 votes
It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.

# Answer
> 1 votes
This problem can be formulated as a mixed integer linear problem very easily.

Sets:

$P$ of all players. Each player costs $c$ and has a score of $w$

$GK,D,M,F$ Form a partition of $P$ (no player can play more than one position)

$NGK=D\cup M\cup F$

Variables:

$x \in \lbrace0,1\rbrace^{P}$ for each candidate player, indicating being chosen for its position.

$u \in \lbrace0,1\rbrace^{NGK}$ for each candidate non-goalkeeper, indicating being chosen as *utility*.

Constraints: Sums over each position must equal amount allowed for each position: $$\sum\_{i\in GK} x\_{i} = 1 $$ $$\sum\_{i\in D} x\_{i} = 2 $$ $$\sum\_{i\in M} x\_{i} = 2 $$ $$\sum\_{i\in F} x\_{i} = 2 $$ $$\sum\_{u\in NGK} u\_{i} = 1 $$

For each non goalkeeper, being chosen as utility implies not being chosen for its other position:

$$ x\_i + u\_i \leq 1 \quad \forall i \in NGK $$

Total cost must be less than budget:

$$\sum\_{i \in P} x\_i.c\_i + \sum\_{i \in NGK} u\_i.c\_i \leq 50000$$

Objective function: Maximize sum of all scores: $$max \quad \sum\_{i \in P} x\_i.w\_i + \sum\_{i \in NGK} u\_i.w\_i $$

# Answer
> -1 votes
**Short Cut - not perfect but if draft is tomorrow**

Create a property productivity = goals / price
Rather than use decimal I would just go 100000 * goals / price

Take the top goalie by productivity
Top 2 defenders by productivity
Top 2 midfielders by productivity Top 2 forwards by productivity
Substitute the least productive defender, midfielder, or forward with top performing utility player if the utility player is a better performer
(assuming max one utility is a substitute)
This is not going to be perfect

If you are over the cap
Drop the highest salary and run again
This is not going to be prefect as some times dropping number 2 salary will be best
Back to if you are over the cap

If you are under the cap it gets trickier
Drop the lowest performer
From that position drop all player with \<= goals
Run again
If under the cap back to step one

**Brute Force / Random**

Look at actual combinations

```
gk    18     18
df    22    231
mf    32    496
fd    28    378
ut    76     76

```

Total number of combinations
59,247,707,904

I you take a random 1,000,000 (random) you are only looking a small fraction
The first short cut would be better than that

**Dynamic programming**

You can eliminate any player that cost more and produces less goals.

Could also eliminate any two player combos that cost more and produce less goals.

Quickly eliminate over the cap.

Keep the best score and skip if you don't have a chance of making the best score.

Looking at the dynamic programming I am not convinced that you would get the options down sufficiently. Even if every individual combination was dropped in 1/2 with dynamic programming that is 1.8 billion total combinations. At 1 per millisecond that is 59 years.

Would need to get the individual combinations down by a factor of 10x eacj to get it down to 7 days.

---
Tags: algorithms, combinatorics, knapsack-problems, permutations
---


title: Is this language in $PSPACE^{L'}$?

text:
# Question
Title: Is this language in $PSPACE^{L'}$?
Let's assume we have an arbitrary language $L'$ and let's define the language $L = \\{1^n | \text{The number of strings in } L' \text{ of length } n \text{ is odd }\\}$.

Is $L\in PSPACE^{L'}$?

I tried saying that I can define a determinstic machine that holds a counter and that goes over all possible strings of length $n$, which is $2^n$, and for each such string it asks the oracle whether it is in $L'$. If yes it increases the counter, and if not, it does not. Then, at the end, checks if the counter is odd, and accepts if so. Else, it rejects.

The problem is that even in $PSPACE$ I can not go over all strings since that would not be a polynomial amount of space, except if I am allowed to override the previous string I checked and that would count only as $n$ space, but I am not sure..

Another part of the question asks if $L \in NP^{L'}$, but that clearly is not the case.

# Answer
Yes it is, by exactly the argument you give. Looping over all possible strings of length $n$ requires only $n$ tape cells – you can do it by treating the length-$n$ strings as numbers in base $|\Sigma|$, so looping through those is essentially a counter, too. You can reuse the space since you don't care about strings that you've already tested. Testing if the string you just made is in $L'$ takes space $n$ on your oracle tape. Implementing the counter requires only $O(n)$ bits, since you only need to store a number in the range $0, \dots, |\Sigma|^n$. So the total amount of space required is linear in $n$.

In fact, you can do slightly better, though the total will still be $O(n)$ because of the need to loop through the length-$n$ strings. You don't need to *count* how many strings in $L'$ you've seen so far; you just need to know if that number is odd or even.
> 1 votes

---
Tags: complexity-theory, turing-machines, oracle-machines
---


# Question
Title: Counting substrings with a given number of different characters in O(N)
Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters.

The obvious solution takes $O(n^2)$ time (fix substring start point, and move its end point while keeping track of the set of seen characters).

Is there a way to do that in $O(n)$ time? Or at least in $O(n c)$ time, where $c$ is the number of unique characters in the string $S$?

I tried to keep track of two pointers (start and end) and move only one of them forward at each step, while updating the hash table with character counts. But counting substrings became really messy.

# Answer
You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward.

Let $S$ be the string. We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to count the number of substrings that start at position $i$.

For each $i$, find the smallest $j\_\text{min} \ge i$ such that $S\[i..j\_\text{min}\]$ has exactly $k$ unique characters as well as the largest $j\_\text{max} \ge i$ such that $S\[i..j\_\text{max}\]$ has exactly $k$ unique characters. You can do this efficiently, by keeping an array (or hashtable) with character counts for $S\[i..j\_\text{min}\]$ and one with character counts for $S\[i..j\_\text{max}\]$; you'll update these each time you decrement $i$, $j\_\text{min}$, or $j\_\text{max}$. (In addition to the array/hashtable, also keep track of the number of of characters with non-zero count, and update this each time you update the array or hashtable.) When you decrement $i$, you can update the array/hashtable with character counts for $S\[i..j\_\text{min}\]$, then use that to see whether you need to decrease $j\_\text{min}$ and by how much (updating the array/hashtable each time you decrement $j\_\text{min}$). Same for $j\_\text{max}$.

Finally, sum up the counts you get for each value of $i$.

Note that $j\_\text{min}$ starts out at $n$ and only ever decreases: when you decrement $i$, $j\_\text{min}$ can only ever get smaller (but not bigger). So, you'll only need to decrement $j\_\text{min}$ (and update the array/hashtable) at most $n$ times: it starts out at $n$, and only ever decreases, and never gets smaller than $1$, so it can only be decreased at most $n$ times. The same is true for $j\_\text{max}$. Consequently, we do at most $O(n)$ updates to the array/hashtable (summed up over all the steps of the algorithm), so the total running time of this algorithm is $O(n)$.

Credit: Thanks to @aaaaajack for a major improvement to my algorithm, and to @Raphael for further improvements.
> 5 votes

# Answer
As is often the case with substring problems, *suffix trees* provide an answer.

1. Construct the suffix tree of your string.
2. In one traversal, annotate every node with the set of characters on the path from it to the root.
3. Check all nodes and output those whose associated set has $k$ members.

All steps take time in $O(n)$ (under the usual assumptions).

You can make this faster by aborting a branch in step 2 if the set reaches size $k+1$ (they never shrink) and checking/returning nodes when you visit them. Also, you don't need to actually store the sets; carrying one representation you can efficiently update (e.g. bit vectors) around is quite enough.

*Disclaimer:* in order to achieve the running-time bounds it may be necessary to maintain character sets of compound edges during step 1.
> 2 votes

---
Tags: algorithms, strings, counting
---


# Question
Title: Sum of two elements in set evenly divisible by k
I have gone through this particular problem in hackerrank.

> You are given an array of $n$ integers, $a\_0, a\_1, a\_2 , \ldots, a\_n$, and a positive integer $k$. Find and print the number of pairs $(i, j)$ such that $i \< j$ and $a\_i + a\_j$ is evenly divisible by $k$.

I wanted to make this work in $O(n)$ time. After lots of searching I found a solution online.

```
a = [1, 3, 2, 6, 1, 2]
k = 3
m = [0]* k
count = 0
for i in a:
    rem = i % k
    com = (k - rem) % k
    count += m[rem]
    m[com] += 1
    print(rem, com, count, m)
print(count)

```

This particular snippet works in $O(n)$ time. But I am having a hard time understanding whats going on mathematically, especially with rem and com variables.

Can anyone please explain me the aspect(mathematical) behind it.

# Answer
> 2 votes
This solution actually works in time $O(n+k)$. The idea is to maintain an array $m\_0,\ldots,m\_{k-1}$, where $m\_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m\_{k-r}$ new pairs (where $m\_k = m\_0$), and then update the array $m$.

A simpler solution is to first compute a histogram $m\_0,\ldots,m\_{k-1}$, where $m\_r$ is the number of inputs *in total* which leave a remainder of $r$ after division by $k$. For each pair $s+t = k$, we count $m\_sm\_t/2$ pairs, and for $s=t=0$, we count $m\_0(m\_0-1)/2$ pairs (exercise), for a total of $$ \frac{m\_0(m\_0-1)}{2} + \sum\_{s=1}^{\lfloor k/2 \rfloor} \frac{m\_sm\_t}{2}. $$

---
Tags: algorithms, arrays, modular-arithmetic
---


# Question
Title: Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)
Please bear with my unhelpful typesetting.

My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson

While discussing Lemma 3, in 4th paragraph, authors make an assumption I am unable to understand.

The assumptions are -

1) **There exist two neighbour configurations $C\_0$ and $C\_1$ both from set $\mathscr{C}$** (which contains configurations on which event $e$ was never applied). So far so good. Till this part we never discuss about valency of $C\_0$ and $C\_1$.

2) Next assumption is - **From $C\_0$ taking $e$ causes to go to $D\_0$ while from $C\_1$ taking an $e$ causes to go to $D\_1$**.

3) **$D\_0$ and $D\_1$ do not have same valency**. (Both are not 0-valent/1-valent simultaneously)

The proof of lemma goes on and uses commutative property to prove that set $\mathscr{D}$ is bivalent.

While I have no problem with rest of proof, I am failing to understand why all three parts of the assumptions should be considered consistent to each other. It is these assumptions (especially 2 and 3) that lead to contradiction.

Here is clarification regarding points 2 and 3.

To me it seems that from the assumption, $e(C\_i) = D\_i$, we introduced the contradiction by saying that $D\_0$ and $D\_1$ are of different valencies. How can one justify that this choice is valid? Why should not I think that both $D\_0$ and $D\_1$ should be of same valency? How do I prove that set $\mathscr{D}$ will still remain bivalent even if $D\_0$ and $D\_1$ are of same valency?

In other way, question would be, how to prove that all three points mentioned above can actually arise in some consensus protocol with assumptions given in lemma.

The fact that $e(C)$ followed by $e'(e(C))$ or vice-versa; $e'(C)$ followed by $e(e'(C))$ should result in same configuration is achieved due to commutativity, and we knew this before hand. My point is, we specifically chose a scenario which was contradicting in itself and does not does anything more in the bigger picture to draw a contradiction of the statement, that $\mathscr{D}$ is univalent.

# Answer
> 7 votes
The paper says

> By an easy induction, there exist neighbors $C\_0, C\_1 \in \mathscr{C}$ such that $D\_i = e(C\_i)$ is $i$-valent, $i = 0, 1$

Here is a proof:

The set of configurations forms the nodes of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following any edges labelled $e$. $\mathscr{D}$ is the set of nodes reachable from $\mathscr{C}$ by paths labelled $e$.

Let $i$ be the valence of $e(C)$: $e$ applies to $C$ by assumption; it is in $\mathscr{D}$ by definition; it is univalent by the assumption from paragraph 2. Let $D$ be a $(1-i)$-valent node in $\mathscr{D}$, which exists because paragraph 3 shows that $\mathscr{D}$ has both 0-valent and 1-valent configurations. By the definition of $\mathscr{D}$, there must be some node $P \in \mathscr{C}$ such that $D = e(P)$. By the definition of $\mathscr{C}$, there is a path from $C$ to $P$ consisting of nodes in $\mathscr{C}$.

The valences of $e(C)$ and $e(P)$ are unequal. For every node $V$ along the path from $C$ to $P$, $e(V) \in \mathscr{D}$, so every one is univalent. Thus, there must be two adjacent nodes along the path with different valences under $e$. These constitute $\\{C\_0, C\_1\\}$.

---
Tags: distributed-systems, concurrency, synchronization, mutual-exclusion, consensus
---


# Question
Title: Finding the spots furthest away from bad data
The real-world problem I'm trying to solve is to create an algorithm which finds the ideal channels where I can transmit radio traffic, inside a radio frequency band that could contain various disturbances. These *n* ideal channels are those who are furthest away from any of the disturbances, but also the furthest away from each other. Where *n* is a constant picked by me, depending on how many channels the radio can support.

---

In abstract terms, I have a chunk of generic data where each item could either be labelled "good" or "bad". It can be considered to be an array of booleans, or illustrated as a series of 1=good and 0=bad, for example `0010111100`.

In this data, consecutive sequences of good data form good segments:

```
0010111100   data size=10
  ^ ^
  | +------- good segment 2, size 4
  +--------- good segment 1, size 1

```

In the best case, there only exists one good segment covering all of the data:

```
1111111111   data size=10, 1 good segment with size 10

```

No matter the nature of the data, I need to find the *n* "best places" that are furthest away from any bad data, but also from each other. It is considered equally bad to be near a "bad" item as it is to be near another "best place".

The ideal solution is where the minimum distance between all "best places" and bad data/other best places is as long as possible, for all best places.

For example, in the case of `1111111111` where n=3 places, they could be located as follows (simply divide the data size by 3):

```
1111111111   data size=10, n=3
  ^  ^  ^

```

Or in case of `0110111110` n=3, the following would be fine:

```
0110111110   data size=10, n=3
 ^   ^ ^

or

0110111110   data size=10, n=3
  ^  ^ ^

```

In case there is too much bad data, the problem has no solution. The sum of all good segment sizes must be at least *n* or there exists no solution. Example:

```
0000010001   data size=10, n=3, no solution possible.

```

---

I suppose one solution is to find the *n* best segments out of all the good segments - then simply find the *n* best places at the center of those segments.

But one problem then is that there aren't necessarily *n* good segments. In that case, the best places have to be divided across what good segments there are.

Are there any similar existing algorithms that could be used or modified to suit the above scenario?

I'm also wondering if there is a particular data structure that would beneficial to use in this case, other than a raw array? A heap binary tree consisting of good segments?

# Answer
I am going to assume you want to maximize the "separation". In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.

Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m = $ the data size. I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.

To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan. Select the left-most place you can. Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place). Keep iterating. When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.

Now you can use binary search from here. If the number of places that could be selected was less than $n$, decrease $s$ and try again. If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again. There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate. If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.
> 3 votes

---
Tags: algorithms, data-structures, sorting, search-algorithms
---


# Question
Title: What's really meant by context-free in the term context-free grammar?
I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.

So can anyone help with this ?

# Answer
The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy.

If you consider context-free grammars, their production rules have the following form:

$$ A \rightarrow \alpha$$

So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the substitution of the non-terminal symbol takes place without considering its "context", that is the other symbols it is surrounded by.

On the other hand, if you consider production rules of context-sensitive grammars, they have the following form:

$$ \beta A \gamma \rightarrow \beta \alpha \gamma$$

where $A$ is a non-terminal and $\alpha$, $\beta$, $\gamma$ are sequences of non-terminals and terminals.

In this case the "context" (i.e., $\beta$ and $\gamma$) of the non-terminal symbol to be substituted influences the effect of the substitution and it is part of the rule itself.

You can find more details in this answer on mathematics and in this answer on software engineering.
> 31 votes

# Answer
"Context" is surrounding text. Context-free grammars are context-free in the sense that the rules look like $A\to\text{things}$, rather than $\text{stuff}\\,A\\,\text{more-stuff}\to\text{things}$. The left-hand side of a rule is always a single non-terminal symbol. That is, the rules for expanding a non-terminal symbol don't depend on what text appears around that symbol (its context), but only depend on the symbol itself. For example, in the grammar for a programming language, the term $\mathrm{Expr}$ expands to the same kind of expression whether you're writing an assignment (e.g., `x:=y+z`), passing arguments to a function (e.g., `f(y+z)`) or returning a value from a function (e.g., `return y+z`).
> 17 votes

# Answer
Generically speaking, even regular languages may have context dependencies, meaning that you can determine - to some extent - in what ways symbols can appear in the vicinity of other symbols in a string that belongs to that language.

What is specific to context-free grammars is that when there are multiple ways of substituting a non-terminal symbol, by applying different rules with the same non-terminal on the right side, the choice of which rule to apply is never dependent on what is happening around this symbol during the derivation process.

You can think of them as context-free **derivation** languages, context-free languages for short.
> 4 votes

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


title: Help with recursive algorithm analysis

text:
# Question
Title: Help with recursive algorithm analysis
Given this algorithm:

```
int foo(int num) {
    if (num == 0){
        return 0;
    } else {
        return 1 + foo(num/10);
    }
}

```

Me and my friend are debating how you should treat "N" as the size of the input.

If I'm considering N to be the number of digits: then my analysis will say O(n)

However, if I'm considering N to be the actual value of the input to the function I will get a different runtime representation and different analysis with the conclusion of O(log n) (base 10)

Me and my friend cannot understand why the second approach is wrong, so far we got explanations like : "The algorithm is cutting the number digit by digit so your N is the number of decimal digits of the number"

However, log (base 10) of the actual value will give me pretty much the same result.

Why is the second approach is wrong ?

# Answer
> 2 votes
There is nothing inherently wrong about either approach, however the first one is overwhelmingly more common. The reason is that complexity analysis takes place in an asymptotic setting with respect to the *size of input*.

Computers are machines that perform meaningless operations on meaningless symbols, it is your job to find meaning in the computation. Therefore, determining what the size is depends on some agreed upon definition of what constitutes a reasonable symbolic representation of the input. Formally, you would have to define how the machine that executes your algorithm works in order to be able to talk about complexity at all, but in this context it is sufficient to assume that any representation that uses a finite set of symbols is acceptable.

There are many ways - all in principle equally valid - to represent the natural numbers. For instance, you might say that $0$ is represented by the string `x`, $1$ by `xx`, $2$ by `xxx` and so on. In this case the size of input would be proportional to the numerical value.

However most of us would agree that representing numbers in some base $b$ - which is certainly acceptable as it requires at most $b$ symbols - is more reasonable; in this case the size of the input is proportional to the number of digits required to write the representation of the number, which is itself proportional to the logarithm of the numerical value.

Taking numbers to have size proportional to their logarithm is also more consistent with the way we treat other objects. If the input of an algorithm is an array, the size of the array is the number of cells (and not the number of different arrays of that length), similarly for graphs, matrices and other mathematical objects.

# Answer
> 1 votes
When encoded in base $b$, the input $n$ has size roughly $\log\_b n$. Sometimes we instead encode whole numbers in *unary*: the number $n$ is encoded as $n$ times some fixed character. Under that encoding, the input $n$ has size $n$.

How you encode the input depends on you, though usually a base $b$ encoding is used. In particular, the model we use for analyzing algorithms (the random access machine) implicitly assumes that the inputs are encoded in base $b$. Therefore your first running time is the correct one, and the other one is wrong.

---
Tags: algorithm-analysis, recursion
---


# Question
Title: in refutation (resolution) can we use a clause that have been resolved
In resolution if we have a set S composed of three clause C1, C2 and C3 and we want to proof that C4 is derivable from S using refutation:

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C3 or C4 or C2 cause even it has been resolved?

and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from or initial set I= {S, ¬C4} and add the resolvent instead?

and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

thank you for claryfing things.

# Answer
> suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C2?

No, not really. If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies. And if C1 can be resolved with C5, then it can also be resolved with C2 in a second way (assuming C1 is not a tautology, and hence cannot be resolved with itself).

> can we resolve C1 with C3 or C4 cause even it has been resolved?

We can (and often must) resolve C1 with C3, even so it has already been resolved with C2. We don't need to resolve any clause with C4 itself, rather the negation of C4 must be brought into a conjunctive normal form. The clauses of that normal for have to be added to our set S.

> and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from our initial set I= {S, ¬C4} and add the resolvent instead?

No, that would be too simple. What you actually do is to select a variable that you want to eliminate from the clauses in the set S, and then:

* for every clause C containing the variable and every clause N containing the negation of the variable
    + resolve C and N and add the resolvent to the set S
* remove all original clauses containing the variable or its negation from the set S

Of course, you could also eliminate a variable by considering both possible assignments separately. It is said that those two approaches are equivalent in a certain sense, yet the approach to consider the assignments separately allows for backtracking, which keeps the memory consumption low by removing the need for explicit representation of the resolvents.

> and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

We stop once we find ⊥.

---

> thank you for claryfing things.

The question is tagged , but none of your questions even touched unification. Your questions also indicate that the resolution rule somehow seems to feel like magic to you. But the resolution rule itself is basically just the cut rule, which is an inference rule of sequent calculus:
$\cfrac{\Gamma \vdash \Delta, A \qquad A, \Gamma' \vdash \Delta'} {\Gamma, \Gamma' \vdash \Delta, \Delta'}$

The cut rule itself is just the appropriate formulation of transitivity of implication
$\cfrac{A \vdash B \qquad B \vdash C} {A \vdash C}$
in the context of sequent calculus (where you can have both a left ($\Gamma$) and a right ($\Delta$) *context*). A sequent $A\_1,\dots,A\_r \vdash B\_1,\dots,B\_s$ can be read as $(A\_1\land\dots\land A\_r) \to (B\_1\lor\dots\lor B\_s)$, which is equivalent to the clause $\lnot A\_1\lor\dots\lor \lnot A\_r \lor B\_1\lor\dots\lor B\_s$.

Whether this is helpful or not is of course a matter of taste. By getting rid of negation, one can write down deductions more symmetrically (and the sequent calculus has established conventions avoiding all those dots when writing things down). You could verify the assertion that "If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies." for example by checking that the deductions
$\cfrac{\Gamma \vdash B, \Delta, A \qquad A, \Gamma', B \vdash \Delta'} {\Gamma, \Gamma', B \vdash B, \Delta, \Delta'}$ and $\cfrac{\Gamma, B \vdash \Delta, A \qquad A, \Gamma' \vdash B, \Delta'} {\Gamma, B, \Gamma' \vdash \Delta, B, \Delta'}$
cover all relevant cases.
> 4 votes

---
Tags: logic, proof-techniques, first-order-logic
---


# Question
Title: Reduction: Vertex Cover to Binary Integer Program (Decision Problem)
I am stuck with the following task: Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming".

I have the feeling that there must be a very easy way.

My approach until now:

1. We can convert any decision problem to an optimization problem in polynomial time.
2. We can reduce the optimization problem of vertex cover to a linear program in polynomial time. (https://en.wikipedia.org/wiki/Integer\_programming#Proof\_of\_NP-hardness)
3. We can convert any optimization problem to a decision problem in polynomial time.

Is this approach ok? And/Or is there a better/easier way?

kind regards James

**EDIT: I think the following solution should work**

Let $a\_{i,j}$ be 1 if vertex $j$ is connected with edge $i$ and otherwise 0. Let $r=|E|$ and $n=|V|$.

A= \begin{bmatrix} a\_{1,1} & a\_{1,2} & \dots & a\_{1,n} \\ a\_{2,1} & a\_{2,2} & \dots & a\_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a\_{r,1} & a\_{r,2} & \dots & a\_{r,n} \\ -1 & -1 & \dots & -1 \\ \end{bmatrix}

Let $b\_i = 1$ $\forall i \in 1..r$

b= \begin{bmatrix} b\_1 \\ b\_2 \\ \vdots \\ b\_r \\ -k \\ \end{bmatrix}

# Answer
> 3 votes
Vertex Cover (Decision Version):

* Given a graph $G=(V,E)$ and a positive integer $K$. The decision vertex cover problem asks: Does $G$ contains a vertex cover of size $K$ or less?

Binary Program (Decision Version):

* Given a matrix $\mathbf{A}$ of size $m\times n$, a vector $\mathbf{b}$ of size $m$ and a positive integer $L$. Define the decision version of Binary Program as: Is there a vector $\mathbf{x}\in\\{0,1\\}^n$ of $L$ nonzeros or less such that $\mathbf{A}\mathbf{x}\geqslant\mathbf{b}.$

You could write the optimization version of vertex cover as a Binary Program as follows: Let $x\_v$ be a binary variable that is equal $1$ if vertex $v$ is selected, and, $0$, otherwise.

\begin{align} & \text{minimize} & & \sum\_{v \in V} x\_v\\ & \text{subject to} & & x\_u+x\_v\geq 1 \text{ for all } \\{u,v\\} \in E\\ & & & x\_{ v }\in\\{0, 1\\}, \forall v\in V. \end{align}

You can easily check that this Binary Program indeed finds a vertex cover of minimum size.

Now, just set $L=K$, $m=|E|$, $n=|V|$, the vector $\mathbf{b}=\[1,1,\ldots,1\]^\top$ and the matrix $\mathbf{A}=\[a\_{ev}\]\_{\forall\\,e\in E,v\in V}$ as

$$a\_{ev}=\begin{cases}1,\text{ if } v\in e\\0, \text{ otherwise}\end{cases}$$

This is, cearly, a polynomial-reduction from Vertex Cover to Binary Program.

---
Tags: reductions, decision-problem
---


# Question
Title: Numerical example of theoretical diff file size using Kullback Leibler?
I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia. Can anyone point me to a numerical example of this calculation? I can only find general theory and formulae. I'd like to check my work. So this is what I have so far...

This is a graph of the individual divergences for each byte probability between two files, say P and Q. They are calculated according to the standard log formula for divergence. The byte values (0-255) are along the bottom. You can see that the divergences are both positive and negative.

I am unsure as to what the units of the y axis are, but following on from Shannon entropy, they must be bits per byte. And they're small values. The sum of all the divergences, keeping sign, is 0.019 bits /byte. Both file sizes are approximately 20KByte, so can I say that the theoretical patch size going from P to Q is 20,000 * 0.019 = 380 bits or 48 bytes?

This feels wrong. If the graph represents the patch size somehow, then I cannot see how the information contained in this complex shaped graph can be encoded in just 48 bytes. There are no examples anywhere on the Interweb that I can find.

One further thing. The above is for two similar files. If P or Q should be totally random (from a random number generator), the KL divergence calculation = approx. 0.5. This at least makes some semblance of sense if you think about all of the bits from P to Q being on average 50% different due to the randomness. Perhaps 48 bytes is correct. Err, um...

# Answer
> I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL)

That's not quite right. I suspect you've taken an imprecise, non-technical, handwavy statement from Wikipedia and interpreted too much into it. They're trying to summarize some underlying theory in an informal way, but such summaries are inevitably incomplete. Instead, you'd be better off reading and understanding the underlying theory.

There is a sense in which that statement is correct if we make certain assumptions -- e.g., that the source is memoryless (each character is independent of all past ones, with no history), and that we interpret it in an asymptotic, average-case kind of way -- but for many real-world sources of data, those assumptions don't apply.
> -1 votes

---
Tags: data-compression, entropy
---


# Question
Title: Is there an isomorphism between (subset of) category theory and relational algebra?
It comes from big data perspective. Basically, many frameworks (like Apache Spark) "compensate" lack of relational operations by providing Functor/Monad-like interfaces and there is a similar movement towards cats-to-SQL conversions (Slick in Scala). For instance, we need natural join (assuming no repetitions on indexes) for element-wise multiplication of vectors from SQL-perspective, which could be considered as `zip + map(multiply)` *(Spark's MLib, however, already has `ElementwiseProduct`)* in Category Theory's applications.

Simply saying (following examples are in Scala):

* the referenced subcase of join can be thought as applicative functor (over sorted collection), which in its turn gives us `zip`: `List(1,2,3).ap(List(2,4,8).map(a => (b: Int) => a * b))` --\> `(List(1,2,3) zip List(2,4,8)).map(x => x._1 * x._2)`. Moreover, we can induce it to some other joins, assuming some preprocessing (`groupBy` operator or just surjection, or generally - an epimorphism).
* other joins and selection can be thought as monad. For instance, `WHERE` is just: `List(1,2,2,4).flatMap(x => if (x < 3) List(x) else List.empty)` --\> `List(1,2,2,4).filter(_ < 3)`
* data itself is just ADT (GADT too?), which in its turn looks like a simple Set-category (or more generally speaking - Cartesian-closed), so it should (I suppose) cover Set-based operations (due to Curry-Howard-Lambek itself) and also operations like `RENAME` (at least in practice).
* aggregation corresponds to `fold/reduce` (catamorphism)

So, what I'm asking is can we build an isomorphism between (maybe subset of) category theory and (the whole) relational algebra or is there something uncovered? If it works, what exact "subset" of categories is isomorphic to relalgebra?

You can see that my own assumptions are quite broad while formal solutions like Curry-Howard-Lambek correspondence for logic-cats-lambda are more precise - so actually, I'm asking for a reference to an accomplished study (that shows a direct relationship) with more examples in Scala/Haskell.

**Edit**: the accepted answer made me think that I went too far representing joins and conditions as a monad (especially using an empty value that effectively instantiates FALSE), I think pullbacks should suffice at least for relalgebra subset of SQL. Monads are better for higher order (nesting) stuff like GROUP BY, which isn’t part of relalgebra.

# Answer
Let me articulate the Curry-Howard-Lambek correspondence with a bit of jargon which I'll explain. Lambek showed that the simply typed lambda calculus with products was the internal language of a cartesian closed category. I'm not going to spell out what a cartesian closed category is, though it isn't difficult, instead what the above statement says is you don't need to know! (Or that you already know, if you know what the simply typed lambda calculus with products is.) For some type theory/logic to be the internal language/logic of a category means 1) that we can interpret the language into the structure on the category in a way that preserves the structure of the language (in effect a soundness condition), *and* 2) and "essentially" all the structure arising from cartesian closure can be talked about in terms of this language (a completeness condition).

The relational algebra is equivalent to the tuple or domain relational calculus which is essentially first order logic. This statement is roughly Codd's theorem, though a similar theorem was proved decades earlier by Tarski for FOL and cylindrical algebras. There is a bit of a subtlety though. We want the queries in the relational calculus to be domain independent, which is to say that expanding the domain of *possible* values doesn't change the results of a query. An example of a relational calculus query that is *not* domain independent is $\\{ x\mid x = x\\}$. Every relational algebra expression is logically equivalent to a *domain independent* query in relational calculus.

Putting that aside, the categories whose internal logic (which is essentially a decategorified or proof-irrelevant form of an internal language) are Heyting categories for intuitionistic FOL and Boolean categories for classical FOL. (The categorified/proof relevant versions are described by hyperdoctrines. Also very relevant are pretoposes of various sorts.) Note, that FOL, the relational calculus, and the relational algebra do *not* support aggregation. (They also don't support the recursion necessary to represent a Datalog query.) One approach to `GROUP BY` and aggregation is to allow relation-valued columns which leads to higher-order logic (HOL) and the *nested* relational calculus (NRC). Once we have relation-valued columns, aggregation can be formalized as just another "scalar" operator.

Your examples point to the fact that a monadic meta-language is a decent language for queries. The paper Monad Comprehensions: A Versatile Representation of Queries (PDF) spells this out well. A more comprehensive and modern look is Ryan Wisnesky's PhD thesis, A Functional Query Language with Categorical Types (PDF), which is related to David Spivak's work which itself seems rather relevant to any interpretation of your question. (If you want to go more historical, there was the Kleisli, A Functional Query System.) In fact, the monadic meta-language is a decent language for queries in the *nested* relational calculus. Wisnesky formulates NRC in terms of an elementary topos whose internal language is the Mitchell–Bénabou language which basically looks like an intuitionistic set theory with bounded quantifiers. For Wisnesky's purpose, he uses a Boolean topos which will instead have a classical logic. This language is quite a lot more powerful than (core) SQL or Datalog though. It is worth noting that the category of *finite* sets forms a (Boolean) topos.
> 15 votes

---
Tags: relational-algebra, category-theory, curry-howard
---


# Question
Title: Time complexity of the fastest algorithm for this case
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $2≤i≤n−1$, either $A\[i\] \> max \\{A \[i-1\], A\[i+1\]\\}$, or$A\[i\] \< min \\{A\[i-1\], A\[i+1\]\\}$. What is the time-complexity of the fastest algorithm that takes as input a sorted array $A$ with $n$ distinct elements, and un-sorts $A$?

A.$O(nlogn)$ but not $O(n)$
B.$O(n)$ but not $O(\sqrt{n})$
C.$O(\sqrt{n})$ but not $O(logn)$
D.$O(logn)$ but not $O(1)$
E.$ O(1)$

My approach:
1.Pair wise swapping can be done which will result in $O(n)$
2.Starting from the left every even position from the start will be swapped with the even position from the right
1 2 3 4 5 6 7 8 -- 2 will be swapped with 7 similarly 4 and 5
odd length can be also listed which is taking $n/4$ steps
So i want to confirm whether only $O(n)$ is the max can best algorithm can be achieved or better can be achieved.

# Answer
I think it's not optimal but here's a lower bound: you have to move at least $\lfloor\frac{n}{3}\rfloor$ elements.

Split $A$ into blocks of $3$: {$A\[1\],A\[2\],A\[3\]$}, {$A\[4\],A\[5\],A\[6\]$}, ...

The claim is you have to move at least one element from each block. Otherwise, assume the block {$A\[k\],A\[k+1\],A\[k+2\]$} is kept unchanged. Since $A$ is sorted, $\min(A\[k\],A\[k+2\])\<A\[k+1\]\<\max(A\[k\],A\[k+2\])$, which violates your constraint. So the problem takes $\Omega(n)$. Combine this with your $O(n)$ approach we get $\Theta(n)$.
> 2 votes

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, polynomial-time
---


title: Combining merge sort and insertion sort

text:
# Question
Title: Combining merge sort and insertion sort
A cache-aware sorting algorithm sorts an array of size $ 2^{k} $ with each key of size 4 bytes. The size of the cache memory is 128 bytes and algorithm is the combinations of merge sort and insertion sort to exploit the locality of reference for the cache memory (i.e. will use insertion sort when problem size equals cache memory).

> What are the best case and worst case running time of the algorithm?

# Answer
> 4 votes
**Basic Idea**

* For small values of n insertion sort runs faster than merge sort . Hence insertion sort can be used to Optimize merge sort
* Basic idea is apply insertion sort on sublists obtained in merge sort and merge the sorted (using insertion sort) lists

**Coming to Question**

Base Condition

If each word is 4-byte long, then a 128-byte cache contains 32 words. Therefore, if the problem size is 32 or less, the instance will be immediately solved by Insertion Sort, otherwise it will be split in two sub-problems with the same size, which will then have to be merged

Time Complexity

> Total Complexity = Complexity Insertion Sort + Complexity of Merge Sort

We have $n$ elements . We are dividing it to $\frac{n}{x}$ sublist each contain x elements each

Complexity Of Merge Sort

* Total work done by merge sort in copying $n$ elements from each level to upper level is $O(n)$
* Number of levels = number of sublists or small problem = $O(\log \frac{n}{x})$
* Complexity of Merge sort : $O( n \log \frac{n}{x} )$

Complexity Of Insertion Sort

* We are sorting $ \frac{n}{x} $ lists each of $x$ elements using insertion sort so complexity contributed by insertion sort is $\frac{n}{x} $ INSERTION ${x}$

> Total Complexity = $\Theta ( \frac{n}{x} \ \text{INSERTION} \ (x) + n \log \frac{n}{x} )$

Best Case

* is when Insertion sort perform in best case with $O(n)$ ie $\text{INSERTION} \ (x) = x$
* Best Case Complexity=Total Complexity = $\Theta ( n + n \log \frac{n}{x} )$

Worst Case

* is when Insertion sort perform in best case with $O(n^{2})$ ie $\text{INSERTION} \ (x) = x^{2}$
* Best Case Complexity=Total Complexity = $\Theta ( nx + n \log \frac{n}{x} )$

More Information : Gate Overflow - Sorting Algorithm

# Answer
> 3 votes
If each word is 4-byte long, then a 128-byte cache contains 32 words. Therefore, if the problem size is 32 or less, the instance will be immediately solved by Insertion Sort, otherwise it will be split in two sub-problems with the same size, which will then have to be merged.

Try drawing the recursion tree. What does each leaf do? How much does that contribute to the overall complexity? What do internal nodes do? I'll let you work out the details.

# Answer
> 2 votes
I will only consider worst case, leaving best case to you. The running time $T(n)$ of merge sort on an instance of length $n$ (words) satisfies the recurrence relation $$ T(n) = 2T(n/2) + O(n), $$ with a base case of $T(1) = O(1)$. In your case, the base case is different: $T(32)$ is the running time of insertion sort on an array of length $32$. Since 32 is constant, we can write $T(32) = O(1)$, and then solve the recurrence relation as in pure merge sort. The result will be exactly the same - the difference between the algorithms (pure merge sort and modified merge sort as in your question) is hidden in the big O constant.

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


# Question
Title: Does it make sense to have both the concept of 'null' and 'Maybe'?
While creating a client for a web API in C#, I ran into a problem regarding `null` as a value where it would represent two different things:

* *nothing*, e.g. a `foo` may or may not have a `bar`
* *unknown*: by default the API response only includes a subset of properties, you have to indicate which additional properties you want. So *unknown* means that the property was not requested from the API.

After some searching I found out about the Maybe (or Option) type, how it's used in functional languages and how it "solves" null dereferencing problems by forcing the user to think about the possible absence of a value. However, all of the resources I encountered talked about replacing *null* with *Maybe*. I did find some mentions of *three-valued logic*, but I don't fully understand it and most of the times its mentioning was in the context of "it's a bad thing".

I'm now wondering if it makes sense to have both the concept of *null* and *Maybe*, to represent *unknown* and *nothing* respectively. Is this the three-valued logic I read about, or does it have another name? Or is the intended way to nest a Maybe in a Maybe?

# Answer
> 14 votes
The `null` value as a default present everywhere is just a really broken idea, so forget about that.

You should always have exactly the concept that best describes your actual data. If you need a type which indicates "unkown", "nothing", and "value", you should have precisely that. But if it does not fit your actual needs then you should not do it. It is a good idea to see what other people use and what they have proposed, but you do not have to follow them blindly.

People who design standard libraries try to guess common usage patterns, and they usually do it well, but if there's a specific thing you need, you should define it yourself. For instance, in Haskell, you could define:

```
data UnknownNothing a =
     Unknown
   | Nothing
   | Value a

```

It may even be the case that you should be using something more descriptive that is easier to remember:

```
data UserInput a =
     Unknown
   | NotGiven
   | Answer a

```

You could define 10 such types to be used for different scenarios. The drawback is that you won't have available pre-existing library functions (such as those of `Maybe`), but this usually turns out to be a detail. It's not that hard to add your own functionality.

# Answer
> 4 votes
As far as I know, the value `null` in C# is a possible value for *some* variables, depending on its type (am I right?). For example, instances of some class. For the rest of the types (like `int`, `bool`, etc) you can add this exception value by declaring variables with `int?` or `bool?` instead (this is exactly what the `Maybe` constructor does, as I will describe next).

The `Maybe` type constructor from functional programming adds this new exception value for a given datatype. So if `Int` is the type of integers or `Game` is the type of the state of a game, then `Maybe Int` has all the integers plus a *null* (sometimes called *nothing*) value. The same for `Maybe Game`. Here, there are no types that come with the `null` value. You add it when you need it.

IMO, this last approach is the better one for any programming language.

# Answer
> 3 votes
If you can define type unions, like `X or Y`, and if you have a type named `Null` which represents only the `null` value (and nothing else), then for any type `T`, `T or Null` is actually not so different from `Maybe T`. The only problem with `null` is when the language treats a type `T` as `T or Null` implicitly, making `null` a valid value for every type (except primitive types in languages that have them). This is what happens for example in Java where a function which takes a `String` also accepts `null`.

If you treat types as set of values and `or` as union of sets, then `(T or Null) or Null` represents the set of values `T ∪ {null} ∪ {null}`, which is the same as `T or Null`. There are compilers which perform this kind of analyses (SBCL). As said in comments, you cannot easily distinguish between `Maybe T` and `Maybe Maybe T` when you view types as domains (on the other hand, that view is quite useful for dynamically typed programs). But you could also keep types as algebraic expressions, where `(T or Null) or Null` represents multiple levels of Maybes.

# Answer
> 1 votes
You need to find out what you wish to express, and then find a way how to express it.

First, you have values in your problem domain (like numbers, strings, customer records, booleans, etc). Second, you have some additional, generic values on top of your problem domain values: For example "nothing" (the known absence of a value), "unknown" (no knowledge about presence or absence of a value), not mentioned was "something" (there is definitely a value, but we don't know which one). Maybe you can think of other situations.

If you wanted to be able to represent all the values plus these three additional values, you would create an enum with cases "nothing", "unknown", "something", and "value" and go from there.

In some languages some cases are simpler. For example, in Swift you have for every type T the type "optional T" which has as its possible values nil plus all the values of T. This lets you handle *many* situations easily, and is perfect if you have "nothing" and "value". You could use it if you have "unknown" and "value". You could *not* use it if you need to handle "nothing", "unknown" and "value". Other languages may use "null" or "maybe", but that's just another word.

In JSON, you have dictionaries with key/value pairs. Here, a key may just be missing from a dictionary, or it may have a value of null. So by carefully describing how things are stored, you can represent generic values plus two additional values.

---
Tags: programming-languages, language-design
---


# Question
Title: Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?
I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\\{a^ib^jc^k : i\leq j\leq k\\}$. I can easily build a linear turing machine, that would delete a, b and c for each a and then b and c for each b and if the only thing left, will be c, then the word belongs to the language. So I know the language is context-sensitive. What I can't figure out is if the language is context-free.

I tried to build a pushdown automata but I couldn't find any. I also tried to use the pumping lemma but wasn't able to find a good word to prove it's not context-free. Could you help me?

# Answer
> 1 votes
A word like $a^nb^nc^n$ should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments.

Also, each splitting $z=uvxyz$ can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different $i$ for each splitting. That is very natural here as $a$ has the minimal number of occurrences, and contradiction is reached by adding occurrences, whereas for $c$ deletion (choosing $i=0$) will get you into trouble.

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


# Question
Title: Arithmetic coding and "the optimal compression ratio"
Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be inefficient, the author refers to an 'optimal compression ratio' that seems to be a function of the probabilities of a given symbol being represented at any given position in the dataset. Am I correct in understanding this to mean:

***Given*** *a set of data and a set of probabilities describing the likelihood of any given member of the dataset being a given symbol, **then** there is no way to represent that data encoded in that manner in fewer bits than the calculated optimal compression ratio*?

In other words: there's no way to encode something in few than 'optimal' bits so don't try?

# Answer
The optimal compression ratio is the entropy, which is the optimal compression ratio due to the source coding theorem.
> 3 votes

# Answer
Beware: The phrase "optimal compression ratio" is perhaps a bit misleading. It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it comes with -- you should really think of it as "the best compression ratio that is achievable, under a certain set of assumptions" (or "the best compression ratio that is achievable by a certain type of compression algorithm"). Since those assumptions often aren't literally true, there's no real guarantee that this is truly the smallest something can be compressed to.

In particular, one key assumption is that the symbols come from a memoryless iid source: i.e., there is a distribution on characters, and each character is sampled randomly from this distribution, independent of all previous characters. For a source that satisfies this assumption, we can calculate the best achievable compression ratio; it is the entropy.

Of course we know this isn't true in practice; in English text, if the previous letter was 'q', the next one is much more likely to be a 'u' than otherwise. So really you should think of the entropy as telling you "if you didn't take advantage of that type of knowledge, what is the best compression ratio you could achieve?".
> 6 votes

# Answer
Let's say your calculation showed that optimal arithmetic coding would need 3.71 bits per character on average. That means that if you compress multiple different strings of characters, you will on average use 3.71 bits per character or more.

Any single string may be coincidence consist of many characters that are much more common than the average character, and that particular string may be encoded in a lot fewer than 3.71 bits per character. Another string may consist entirely of very rare and unusual characters and use more than 3.71 bits per character.

The number also assumes that any correlation between characters has already been handled earlier, so you have purely independent characters. If there are dependencies between characters, you can usually have much better compression.
> 2 votes

---
Tags: information-theory, data-compression, huffman-coding
---


title: Does a verifier means decidability

text:
# Question
Title: Does a verifier means decidability
If, for example, there is a problem B which have exponential time verifier - a verifier that verify on exponential time - Does it 100% means that B decidable?

On one hand I thought - If there is a verifier - why can't I just decide for each input - using the verifier? On the other hand - from what I know - if it doesn't halt we wouldn't know it...

Thanks.

# Answer
I'll start with an intuitive explanation as to why $B$ is decidable. Given input $x$, we can start trying every possible witness $y$ and check whether the verifier $V$ accepts $(x,y)$. This is a semi-algorithm, since it doesn't necessarily halt.

However, we note that since $V$ has exponential running time, then considering witnesses that are "too long", i.e. so long that $V$ won't be able to read all the witness, is irrelevant. So we can in fact stop after a bounded number of witnesses, which makes our procedure a halting algorithm.

Now let's formalize this.

Let's assume that the language $B$ has a verifier $V$ that runs in time $f(n)$ for some function $f$ (in your question, $f$ is an exponential function, but this is not important). A crucial property of $f$ is that it's computable. That is, given $n$ we can compute $f(n)$. It is easy to see that functions such as polynomials and exponentials are computable.

Since $V$ is a verifier for $B$, then we have can write the following: $$B=\\{x: \exists y \text{ such that } (x,y)\in L(V)\\}$$ where $V$ has the property that given input $(x,y)$, $V$ halts in time at most $f(|x|)$.

We now make the following key observation: if $V$ accepts $(x,y)$ for some $y$, then there exists $y'$ such that $|y'|\le f(|x|)$ such that $V$ accepts $(x,y')$. That is, if there is a witness, then there is also a "short" witness.

This observation is correct since if $y\>f(|x|)$ then $V$ cannot read more than $f(|x|)$ letters of $y$, so it's enough to consider a prefix of $y$.

From this it is easy to see why the procedure we described above works.
> 5 votes

---
Tags: complexity-theory, turing-machines, time-complexity, undecidability
---


# Question
Title: Complexity of k-way merge with log n arrays of size n / log n
I'm designing an in-place sorting algorithm to sort a collection of size $n$. Near the end of the sorting, it may end up with with $\log{n}$ sorted sub-sequences of size $\frac{n}{\log{n}}$. At this point, I use a very simple $k$-way merge algorithm that merges the sub-sequences pairwise until everything has been merged. This very case apparently represents the complexity bottleneck of the algorithm.

I'm repeatedly using the C++ function `std::inplace_merge` to perform the merging operations, which performs $Θ(N \log{N})$ comparisons most of the time, but may perform up to $O(N \log^2{N})$ comparisons if there isn't enough extra memory available, where $N$ corresponds to the sum of the sizes of the sequences to merge (in our case $2\frac{n}{\log{n}}$).

Taking all of that information into account, I can tell that repeatedly merging the sub-sequences pairwise until everything has been merged takes the following number of comparisons, step by step:

* Step 1: $O(\frac{\log{n}}{2} * \frac{2n}{\log{n}} * \log^2{\frac{2n}{\log{n}}}) = O(n * \log^2{\frac{2n}{\log{n}}})$
* Step 2: $O(\frac{\log{n}}{4} * \frac{4n}{\log{n}} * \log^2{\frac{4n}{\log{n}}}) = O(n * \log^2{\frac{4n}{\log{n}}})$
* Step 3: $O(\frac{\log{n}}{8} * \frac{8n}{\log{n}} * \log^2{\frac{8n}{\log{n}}}) = O(n * \log^2{\frac{8n}{\log{n}}})$
* $\ldots$

If I'm not mistaken, there will be $\log{k}$ steps where $k$ is number of sorted sub-sequences in the original collection, which is is $\log{n}$, hence there will be $\log{\log{n}}$ steps. This should yield an overall complexity along the lines of $O(\log{\log{n}} * n * \log^2{\frac{?n}{\log{n}}})$.

Now, to be perfectly honest, I've got no idea how to simplify this expression further, and since I'm describing a sorting algorithm, I would like to know whether it is more along the lines of $O(n \log{n})$ or $O(n \log^2{n})$.

Having computed the complexity of the other two steps of the algorithm, it appears that none of them performs more than $O(n \log{\frac{n}{\log{n}}})$ comparisons¹, which is intuitively smaller than $O(n \log{n})$, the lower bound for comparison sorting, so the k-way merge surely dominates the overall complexity and thus performs at least $O(n \log{n})$ comparisons.

Can you help me solve this complexity problem?

---

¹ Among the other steps, the bigger one is sorting $\log{n}$ sub-sequences of size $\frac{n}{\log{n}}$ with an $O(N \log{N})$ sorting algorithm, which has the complexity $O(\log{n} * \frac{n}{\log{n}} \log{\frac{n}{\log{n}}}) = O(n \log{\frac{n}{\log{n}}})$.

# Answer
First of all, notice that whatever you were doing, the complexity up to this point *can not possibly* be $o(n \log n)$. If that were true, we could merge each sorted subsequence in time $O(n \log \log n)$, violating the well known bound of $\Omega(n \log n)$ for the worst case of a general sorting algorithm. In fact, $$\Theta\left(n \log \frac{n}{\log n} \right) = \Theta(n \log n - n \log \log n) = \Theta (n \log n)$$

Now, let's analyze the complexity of what you are proposing. In order to visualize all the merging that's going on, imagine inserting each sorted subsequence into a FIFO queue. At each step, we take the first two sequences of the queue, merge them, and put the result at the back of the queue. We take note of the sequence that is initially in front of the queue, and define a *round* as the set of all merging operations that happen between two subsequent appearances of the initial sequence at the front of the queue.

Observe that each round splits in half the queue size: let's say there are $r$ rounds, with $r \in \Theta(\log \log n)$. Let $\alpha = \frac{n}{\log n}$. Before the $h-$th round begins, the queue contains $\frac{n}{2^h \alpha}$ subsequences, each of which has length $2^h \alpha$. Therefore, the complexity of round $h$ is:

$$ \Theta\left( \frac{n}{2^{h+1} \alpha} \left( 2^{h+1} \alpha \log (2^{h+1} \alpha) \right) \right) = \Theta \left( n \log (2^{h+1} \alpha) \right) $$

This yields an overall complexity of:

$$ \Theta\left( \sum\_{h=0}^{r-1} n \log (2^{h+1} \alpha) \right) = \Theta\left( nr \log \alpha + n\sum\_{h=0}^{r-1} \log 2^{h+1} \right ) = \Theta\left( nr \log \alpha + nr^2 \right ) $$

Now, remembering that:

$$ \Theta \left( \log \alpha \right) = \Theta \left( \log n - \log \log n \right) = \Theta(\log n) $$

We conclude:

$$ \Theta\left( nr \log \alpha + nr^2 \right ) = \Theta(n \log n \log \log n) $$
> 3 votes

---
Tags: algorithm-analysis, asymptotics, sorting
---


# Question
Title: Simulate NPDAs with DTMs using only polynomial overhead
We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$.

Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \subseteq \mathrm{P}$ and $\mathrm{CFL} \subseteq \mathrm{NP}$, respectively. We simply use the TM tape as stack, readig and writing only at one end of the used area. The only element we can not immediately translate is transitions which push more than one symbol on the stack; for such we add intermediate states. We get a TM that stays within a constant factor both in terms of size and runtime of the original PDA.

As a follow-up to my overly optimistic answer here (thanks @A.Schulz for exposing my mistake) I wonder: can we combine the two? That is, is there a (more or less) direct simulation from NPDA to DTM?

Naive translations as the above do not work because of the blow-up needed to resolve the nondeterminism. We may be able to make use of some normal forms such as absence of $\varepsilon$-transitions (are there others?), though.

# Answer
> 2 votes
We can combine two known techniques: CYK -which you mention- and the PDA to CFL construction.

Assume that the PDA is in "Chomsky Normal Form": it reads iff it pops, and pushes two symbols otherwise. Formally, its instructions are of the form

* $(p,\varepsilon,A) \mapsto (q,BC)$
* $(p,a,A) \mapsto (q,\varepsilon)$

Recall that this can be transformed into CFL using non-terminals of the type $\[p,A,r\]$, and the productions

* $\[p,A,r\] \to \[q,B,s\]\[s,C,r\]$ for any "guessed" states $r,s$
* $\[p,A,q\] \to a$

Note that $\[p,A,r\]$ is a non-terminal that derives all strings using certain computations (see below).

We do not have to explicitly perform the latter construction, but we can build it in the CYK itself, by introducing a table $P(i,j)$ that contains elements that are such triplets. So this would mean $\[p,A,r\] \in P(i,j)$ iff there is a computation on $w\_i\dots w\_j$ starting in state $p$ and ending in state $r$ that starts with $A$ on the stack and ends with an empty stack.

---
Tags: turing-machines, automata, pushdown-automata, polynomial-time, simulation
---


# Question
Title: Comparing floating-point numbers as integers
In the article http://floating-point-gui.de/errors/comparison/, a method for comparing floating-point numbers is suggested:

> There is an alternative to heaping conceptual complexity onto such an apparently simple task: instead of comparing a and b as real numbers, we can think about them as discrete steps and define the error margin as the maximum number of possible floating-point values between the two values.
>
> This is conceptually very clear and easy and has the advantage of **implicitly scaling the relative error margin with the magnitude of the values**. Technically, it’s a bit more complex, but not as much as you might think, because IEEE 754 floats are designed to maintain their order when their bit patterns are interpreted as integers.

So instead of some complex variant of abs(b - a) \< ε, we interpret a and b as integers and find abs(b - a) \< ε(steps(a, b)) where ε is somehow variable with regards to the density of floating-point numbers in the vicinity of a and b. **But how exactly?**

Also, does this method really alleviate checking for NaNs and Infs? Or are some of these "heaps of conceptual complexity" inevitable if you want a solid, generic method of floating-point comparison?

The following C code produces `1677722`:

```
#include <stdio.h>

int main(int argc, char *argv[])
{
    double x, y, z, a, b;
    int steps;

    sscanf("0.1", "%f", &x);
    sscanf("0.2", "%f", &y);
    sscanf("0.15", "%f", &z);

    a = x + y;
    b = z + z;
    steps = *(int*)&b - *(int*)&a;

    printf("%d\n", steps);
}

```

**Edit:** Rephrased so the word "discrete" is not misused. Rewrote "steps(a, b) \< ε(a, b)" into "abs(b - a) \< ε(steps(a, b))" to indicate that it may still just be floating-point operations, but that ε is chosen variably.

# Answer
There are a few fine tricks in the IEEE P754 format, which allows the use of integer operations for comparisons, or for rounding... It is useful for hardware implementations, for CPUs without an FPU, for some optimized libraries that need fast comparisons...

Caveats: \- The sign bit (MSB) must be handled separately. \- NaNs must be checked.

When comparing 0, denormals, normals or infinites **of the same sign**, integer comparisons work for floating point numbers.
> 4 votes

# Answer
If you graph $y = float(x)$, that is, the float value obtained by interpreting/casting the integer x bitwise as a float, you get an exponential curve approximated by a piecewise linear function, as the value of y increases in fixed steps of $2^{exponent}$ for each range where $exponent$ is constant. So the density of values undergoes discontinuous jumps as you move along x, but it approximates an exponential ($1/y$) decline in density as x increases.

So what the author is suggesting is to scale the acceptable error approximately by using a *fixed* difference $dx$ in x, ie the number of discrete values between two comparands. If $dx$ falls within one line segment, this allowed error is exactly $dx * 2^{exponent}$ for the local exponent (it's slightly more complex if it crosses two or more segments), and it scales up as $exponent$ increases. So we get a kind of auto-adapting error that scales approximately with the inverse of the local density.
> 3 votes

# Answer
Answer:

I think what this is describing is a matter of scaling.

Say you are comparing two floating-pointnumbers with a precision to two decimal places.

If you multiply both by 100 you have raised their values by two orders of magnitude, and end up with integers to compare.

This can be computationally more efficient, since every flop takes more time than an intop.
> -2 votes

---
Tags: floating-point
---


# Question
Title: Do not understand a lemma regarding dinics algorithm
Here you can find the following lemma with its proof.

Lemma: In a network with unit edge capacities, Dinitz algorithm terminates after $O(\sqrt{m})$ blocking flow computations.

Proof: Consider the layered network after $\sqrt{m}$ iterations. It has at most m edges. The average number of edges between any two layers is $\frac{m}{\sqrt{m}} = \sqrt{m}$. Hence, there must be at least one layer $i$ with at most $\sqrt{m}$ edges. Now consider the cut $S=\\{v | level\_f(v) \< i\\}$. It has capacity at most $\sqrt{m}$. Since each blocking flow augmentation increases flow by at least one, after $\sqrt{m}$ additional blocking flow augmentations, a maximum flow has been found. Hence, no more than 2$\sqrt{m}$ = $O(\sqrt{m})$ blocking flow augmentations are needed.

I don't understand the proof. The layered graph $G\_{L}$ has m edges. But how does it look like after $\sqrt{m}$ iterations? Is the average number of edges of $G\_{L}$ between any two layers $\frac{m}{\sqrt{m}} = \sqrt{m}$ after $\sqrt{m}$ iterations? And the confusion continuous with the set $S$.

Could someone unfold this proof for better understanding?

# Answer
"How does it look like after $\sqrt{m}$ iterations?"

To see this, we need a property: the number of layers increases by at least $1$ after each iteration. In other word, the shortest distance from $s$ (source) to $t$ (sink) increases by at least $1$. This is the key property of Dinic's algorithm. I'll put the proof at the end. (Please help if anyone has a better way to arrange these contents. I don't want to let the proof occupy too much space.)

So after $\sqrt{m}-1$ iterations, $G\_L$ has at least $\sqrt{m}+1$ layers, because there are at least $2$ layers at first, one for $s$ and one for $t$. This means there are at least $\sqrt{m}$ "edge layers" between the vertex layers. So the edge layer with the least number of edges has at most $\frac{m}{\sqrt{m}}=\sqrt{m}$ edges. One more thing you should notice is this edge layer forms a $s$-$t$ cut in the residual graph with capacity at most $\sqrt{m}$. (You can't jump across any layer, so you must pass this layer.) According to max-flow-min-cut theorem, capacity of maximum flow in the residual graph is at most $\sqrt{m}$. So we need at most $\sqrt{m}$ more iterations. In conclusion, the total number of iterations is $O(\sqrt{m})$.

Proof of the key property:

Suppose at some iteration we have residual network $G\_f$ and its corresponding level graph $G\_L$, and after one iteration we have residual network $G\_f'$. To prove that $s$-$t$ distance in $G'\_f$ is longer, first let's see the difference between $G\_f$ and $G\_f'$: if an edge $(u,v)$ is saturated, $(u,v)$ is removed and $(v,u)$ is added. Note that the blocking flow only contains edge in $G\_L$, so $(u,v)$ is a "foward" edge in $G\_L$, and $(v,u)$ is a "backward" edge in $G\_L$. Here "forward" means the edge moves from lower level to higher level in the level graph.

Consider a shortest path from $s$ to $t$. Each edge $e$ on this path has three possibilities:

1. $e\notin G\_f$. In this case $e$ is new, so it's "backward" in $G\_L$ according to our claim above.
2. $e\in G\_f$ but $e\notin G\_L$. In this case, $e$ can't be forward. Otherwise it would be contained in $G\_L$. (Note that a forward edge can't jump across a layer because the level graph is constructed based on shortest distance.)
3. $e\in G\_L$. This is the only possible forward edge, which increases the level by exactly $1$.

Consider the level in $G\_L$ of each vertex on the $s$-$t$ path. The level increases by at most $1$ after each step. So the shortest path from $s$ to $t$ in $G\_f'$ is never shorter than the shortest path in $G\_L$. Furthermore, it should be strictly longer: if the distance is the same, it means the shortest path in $G\_f'$ only consists of type $3$ edges. This means we can find an unsaturated path in $G\_L$, which violates the definition of blocking flow.

Therefore, the number of layers is strictly increasing.
> 1 votes

---
Tags: algorithms, graphs, optimization, network-flow
---


# Question
Title: A term for two algorithms which give same results but differ in complexity
Is there a technical term for a pair $(u,v)$ of algorithms, such that $u$ and $v$ have an identical output for each input (I include the option if not halting as a possible output), but they have different complexity (either time or space) as a function of their input?

An example of such a pair is (bubble sort, quicksort)

# Answer
What you are talking about is very narrow, there is no term that describes it exactly.

However, a closely related concept that you might be interested in is *extensional equivalence* as opposed to *intensional equivalence*. Intuitively, two objects are extensionally equivalent if they have the same external properties, and intensionally equivalent if they have the exact same definition.

Generally, mathematics and logic define equality as (some form of) extensional equivalence; for instance, the Zermelo-Fraenkel set theory includes some form of the following axiom:

$$ \forall x \forall y \[\forall z (z \in x \Leftrightarrow z \in y) \Rightarrow x = y\] $$

Since functions are really relations, and relations are really sets, two functions that are point-by-point identical are *literally the same function*. But still, I believe that most of us would agree that even though quicksort and bubblesort are somewhat related, they are *not the same thing*.

So the real question here is *what is the thing you call "the algorithm quicksort"*? It's certainly more than just a program: quicksort written in C is not the same program as quicksort written in Haskell, but we would still call both quicksort. But at the same time it's not really just a function, defined by its input and output: in order to deserve the name "quicksort" you also have to operate in a certain way.

It's not a question I have a good answer for, there is no precise and universal definition of "algorithm" (yet).

In the meantime, I would say that quicksort and bubblesort are *extensionally equivalent* but *not intensionally equivalent*.

---

(or, at least, none I'm aware of)
> 3 votes

---
Tags: algorithms, complexity-theory, terminology
---