# Question
Title: Finding the total capacity of two communication channels
I have the transition matrices of two communication channels. I am able to find the capacity of each by performing an optimization calculation, however I need the total capacity of the two channels. The channels are not weakly symmetric so I don't think I am able to simply add the two capacities. I think what I need to do is perform the optimization calculation over the combined channels but I'm not sure how to do this. I think I need to construct a transition probability matrix but I'm not sure how to go about this. If anyone can give some advice on this I'd be grateful.

Thanks

# Answer
If the channels are not coupled (i.e., their effect on the input is independent of each other) then their combined capacity is the sum of their individual capacities. See for example Wyner, Capacity of Product of Channels, who also considers the converse.
> 1 votes

# Answer
You have to consider different scenarios. The capacity of a broadcast channel is different than a multiple access channel. The total capacity also varies for symmetric and asymmetric channels. See "Network Information Theory" by Abbas El Gamal and Young-Han Kim
> 0 votes

---
Tags: information-theory, communication-protocols
---


# Question
Title: Prove {0^n OR 1^2n OR 2^3n | n >= 0} is not context free
How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n \>= 0} is not context free

This isnt the same language as {0^n1^2n2^3n | n \>= 0} as this language the numbers need to be in order.

# Answer
It is not specified but I'll assume the alphabet to be $\Sigma = \\{0,1,2\\}$ and also that your *strange* notation means the language

\begin{align\*} L&= \\{x \in \Sigma{}^\* : x=0^n \lor x=1^{2n} \lor x=2^{3n}, n \in \mathbb{N}\\} \\ &=\\{0^n : n \in \mathbb{N}\\}\cup\\{1^{2n} : n \in \mathbb{N}\\}\cup\\{2^{3n} : n \in \mathbb{N}\\} \end{align\*}

Well, the answer is that actually it **is** context-free since each of those three languages is trivially CF and the union of CFLs is also CF.

But it is also Regular! By ***definition*** a language is said to be regular if it is accepted by some $DFA$ or, equivalently, if it is expressible by a regular expression.

In our case, $L = 0^\*+(11)^\*+(222)^\*$.
> 1 votes

---
Tags: turing-machines, regular-languages, context-free, pumping-lemma
---


# Question
Title: Maximizing the weighted average value of a set of items by doubling the weight of a subset of items
Given a set of $n$ items, each represented by $t\_i=(w\_i,v\_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as: $$ \frac{\sum\_{i=1}^{n}v\_iw\_i}{\sum\_{i=1}^nw\_i} $$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized.

For example, suppose you have the following set of items, where $t\_i = (w\_i,v\_i)$:

$$ t\_1 = (12, 1100000)\\ t\_2 = (12, 1000000)\\ t\_3 = (12, 850000)\\ t\_4 = (10, 800000) \\ t\_5 = (8, 1200000) $$ The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight?

Thanks in advance.

# Answer
Suppose $v\_1\>\cdots\>v\_n$ without loss of generality, there is an greedy algorithm working as follows.

```
vw = v_1 * w_1 + ... + v_n * w_n
w = w_1 + ... + w_n
for i = 1 to n:
    if v_i > vw / w:  // #1
        choose item i to double its weight
        vw += v_i * w_i
        w += w_i

```

Note condition #1 means doubling $w\_i$ will enlarge the current weighted average value. Also note `vw / w` does not decrease, so finally $w\_1,w\_2,\ldots,w\_k$ are doubled for some $k$.

To prove the correctness of the algorithm, we only need to prove the algorithm behaves correctly in each step, i.e. if whether $w\_1,\ldots,w\_{i-1}$ are doubled are already determined (for convenience, in the following analysis, $w\_j$ $(j=1,\ldots,i-1)$ represents the value after doubling if it is determined to be doubled), then

1. if $v\_i \> \sum\_{j=1}^n v\_jw\_j/\sum\_{j=1}^n w\_j$, then there is an optimal solution that doubles $w\_i$, and
2. if $v\_i \le \sum\_{j=1}^n v\_jw\_j/\sum\_{j=1}^n w\_j$, then there is an optimal solution that does not double $w\_i$.

Let's firstly prove statement 1 by contradiction. Assume no optimal solution doubles $w\_i$, and suppose an optimal solution chooses to double $w\_{i\_1}, w\_{i\_2},\ldots, w\_{i\_m}$ where $i\< i\_1\<\cdots \<i\_m$. We can assume $m\ge1$, otherwise the optimal solution doubles none of $v\_i,v\_{i+1},\ldots,v\_n$, then doubling $v\_i$ will make this solution better since $v\_i \> \sum\_{j=1}^n v\_jw\_j/\sum\_{j=1}^n w\_j$, a contradiction. Note doubling $w\_i,w\_{i\_1}, w\_{i\_2},\ldots, w\_{i\_m}$ is not an optimal solution, we have $$\frac{\sum\_{j=1}^n v\_jw\_j+\sum\_{j=1}^mv\_{i\_j}w\_{i\_j}}{\sum\_{j=1}^n w\_j+\sum\_{j=1}^mw\_{i\_j}}\>v\_i.$$

Also note the optimal solution is no worse than the solution that doubles $w\_{i\_2},\ldots,w\_{i\_m}$, we have

$$\frac{\sum\_{j=1}^n v\_jw\_j+\sum\_{j=1}^mv\_{i\_j}w\_{i\_j}}{\sum\_{j=1}^n w\_j+\sum\_{j=1}^mw\_{i\_j}}\le v\_{i\_1}.$$

Hence $v\_{i\_1}\>v\_i$, a contradiction.

Now let's prove statement 2. Suppose an optimal solution doubles $w\_{i\_1},\ldots, w\_{i\_m}$ where $i\le i\_1\<\cdots \<i\_m$, since $v\_i \le \sum\_{j=1}^n v\_jw\_j/\sum\_{j=1}^n w\_j$, we have

$$\frac{\sum\_{j=1}^mv\_{i\_j}w\_{i\_j}}{\sum\_{j=1}^mw\_{i\_j}}\le v\_i \le \frac{\sum\_{j=1}^n v\_jw\_j}{\sum\_{j=1}^n w\_j},$$ thus $$\frac{\sum\_{j=1}^n v\_jw\_j+\sum\_{j=1}^mv\_{i\_j}w\_{i\_j}}{\sum\_{j=1}^n w\_j+\sum\_{j=1}^mw\_{i\_j}}\le \frac{\sum\_{j=1}^n v\_jw\_j}{\sum\_{j=1}^n w\_j},$$

which means not doubling any of $w\_i,w\_{i+1},\ldots, w\_n$ is also an optimal solution, i.e. there is indeed an optimal solution that does not double $w\_i$.
> 1 votes

# Answer
This can be solved in polynomial time.

Hint: consider the decision version of the problem.

> Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.

Could you solve that version of the problem? Does this give you any ideas about how to solve the original problem?

---

Alternate hint:

> Keep trying other greedy strategies. You've tried one greedy algorithm, but there might be other plausible greedy algorithms.
> 0 votes

# Answer
I think the below gives the correct answer, but I am not sure how to prove it.

1. For every pairing, work out the difference it would make to the weighted average if the weight were doubled. This is given by $\frac{x+vw}{y+w}-\frac{x}{y}$ where:

* $x$ is the numerator of the weighted average
    * $v$ is the value of the current pairing
    * $w$ is the weight of the current pairing
    * $y$ is the denominator of the current weighted average
2. Pick the largest positive difference and double the weight. If there are no positive differences, stop.
3. Repeat, ignoring the value you just doubled.

It seems intuitively that in the worst case, you will end up doubling all but one values, in which case you will make $2n(n+1)/n$ passes (factor of 2 in the numerator to find the largest difference after working them all out: two passes over the dataset per iteration).

I think this is the best naive solution, but can surely be optimised further for practical applications.
> -1 votes

---
Tags: algorithms
---


# Question
Title: Big O notation: removing big O from denominator
In *A First Course in the Numerical Analysis of Differential Equations* (page 26) Arieh Iserles gives the following derivation: \begin{equation} \frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\xi^2+\frac{1}{3}\xi^3+\mathcal{O}(\xi^{4})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)} \end{equation} where $\xi=w-1$, $\rho(w)=w^2-w$ and $\xi\to 0$. I understand the expansion of the logarithm in the denominator, but how does the second step work? I have no idea how this big O is removed from the denominator. Can anyone explain this please?

# Answer
> 2 votes
Let's start out simple:

$${1 \over 1 + x} = 1 - x + x^2 - \cdots$$

so it follows that

$${1 \over 1 + O(x)} = 1 + O(x)$$

as $x \to 0$.

(Background: I interpret $O(x)$ as representing any function $f(x)$ where $|f(x)|$ is asymptotically no larger than $x$, i.e., there exist constants $c\_0,x\_0$ such that $|f(x)| \le c\_0 |x|$ for all $-x\_0 \le x \le x\_0$. This is the likely meaning of big-O notation in this context, where we are concerned about the asymptotic behavior as $x \to 0$ and where values can be either positive and negative. If it looks a little different from what you are used to in computer science, that's because in CS we most commonly deal with the situation where we have a function $f(n)$ where $n \to \infty$ and where all values are positive, so the definition looks a bit different in that context.)

Now suppose $v=O(1)$, and take a more complex expression:

$${1 \over 1 + v + O(x)} = {1 \over 1+v} \cdot {1 \over 1 + O(x)} = {1 \over 1+v}(1 + O(x)) = {1 \over 1+v} + O(x),$$

where I have used that $v \cdot O(x)=O(x)$, etc.

Finally, if $u=O(1)$, we can multiply both sides by $1+u$ to see that

$${1+u \over 1+v+O(x)} = {1+u \over 1+v} + O(x).$$

Now plug in $x=\xi^3$ and $u = \xi$ and $v = -\frac12 \xi + \frac13 \xi^2$, and we obtain

$$ \frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)} $$

which is the step of the derivation you are asking about.

# Answer
> 2 votes
Let us compute the difference.

$$\begin{aligned} &\frac{\xi+\xi^2}{\xi-\frac{1}{2}\xi^2+\frac{1}{3}\xi^3+\mathcal{O}(\xi^{4})} -\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}\\ =&\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})} -\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}\\ =&(1+\xi)\left(\frac{1}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})} -\frac{1}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}\right)\\ =&(1+\xi)\frac{-\mathcal{O}(\xi^3)}{(1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3}))(1-\frac{1}{2}\xi+\frac{1}{3}\xi^2)}\\ =&(1+\xi)\frac{-\mathcal{O}(\xi^3)}{1-\mathcal{O}(\xi)}\\ =&-\mathcal{O}(\xi^3)\frac{1+\xi}{1-\mathcal{O}(\xi)}\\ =&-\mathcal{O(\xi^3)}\\ =&\mathcal{O(\xi^3)} \end{aligned}$$

Just in case it is confusing, $\mathcal{O}(f(\xi))$ for a function $f$ of $\xi$ just means some function of $\xi$ whose absolute value is smaller than $c|f(\xi)|$ for some constant $c\>0$ when $\xi$ is near 0 enough. It might mean a different function at each of its occurrence above.

---
Tags: asymptotics, numerical-analysis
---


title: Variation of knapsack problem

text:
# Question
Title: Variation of knapsack problem
I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items:

item 1: $4

item 2: $5

item 3: $8

with the total purchase price = $14

There is only one solution in the case, 1 purchase of item 1 and 2 purchases of item 2.

How do I go about solving this?

# Answer
> 2 votes
This is called the subset sum problem. There's lots written about the problem; go read about it.

How you could have figured this out on your own: you already know it is a variant of the knapsack problem, so if you had read the Wikipedia page on the knapsack problem, you would have encountered a description of the subset sum problem in the section of that page on variations of the knapsack problem. In the future, I encourage you to do research before posting, to make sure your question isn't already answered in the obvious places (e.g., Wikipedia, textbooks).

# Answer
> 0 votes
Basically to solve these type of problems we make use of **Inclusion-exclusion** principle. For each element which in this case are purchasable items with some monetary value, we have a choice either to buy the item or to not buy it. If we buy the item then it is an instance of inclusion of item and we choose not to buy it then it is an instance of exclusion.

So we can say that for each item we have two possible choices and because of these two choices for each item these problems can be solved in exponential time recursively. Surely, Dynamic programming comes handy to optimize it to polynomial time.

Also i noticed that the problem is similar to coin change problem. You can go through this problem as well and see the **inclusion-exclusion** principle in action.

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


# Question
Title: What does a faster algorithm mean in theoretical computer science?
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?

> Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?

# Answer
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.

In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.

If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $\Theta$ rather than just as a big $O$.
> 26 votes

# Answer
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.

Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n\>10$.

So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n\>100000$, which one would you pick? What would you do if your problem size varies greatly?
> 11 votes

# Answer
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) \in o\bigl(f\left(n\right)\bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.

Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $\Theta(n^2)$ whereas we know others that run in $\Theta(n \log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.

And sometimes, even theoretical computer scientists use “faster” the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.” In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of *asymptotic* time complexity.
> 5 votes

# Answer
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) \in O(f(n))$.

$$ \exists \ 0 \le c\_f \lt \infty \mid \ \limsup\_{n \to \infty} \frac{A(n)}{f(n)} = c\_f $$

Now, let us assume we are talking about an *arbitrarily increasing* function $g(n)$ where $ \limsup\_{n\to\infty} g(n) = \infty $ and let us create the function $ h(n) = \frac{f(n)}{g(n)}$.

We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.

$$ \exists \ 0 \le c\_h \lt \infty \mid \ \limsup\_{n \to \infty} \frac{A(n)}{h(n)} = c\_h $$

Using the rules of limits, we can also write:

$$ c\_h = \limsup\_{n \to \infty} \frac{A(n)}{h(n)} = \limsup\_{n \to \infty} \frac{A(n)g(n)}{f(n)} = c\_f \cdot \limsup\_{n \to \infty} g(n) $$

Since $c\_h \lt \infty$, this can only be true if $c\_f = 0$.

The contrapositive statement is: If $ c\_f \neq 0$, then $A(n) \notin O(h(n))$.

In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) \in \Theta(f(n))$ and $g(n)$ is arbitrarily increasing.

Additionally, this should show why the statement that $A(n) \in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
> 1 votes

# Answer
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.

To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.

The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.

If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.

```
Pick up the jar
Grab the lid
Unscrew the lid

```

Versus

```
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid

```

Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.

By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.

So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
> 1 votes

---
Tags: algorithms
---


title: Fast sampling from discrete space

text:
# Question
Title: Fast sampling from discrete space
Assume we are given a set $X = \\{x\_1,...,x\_n \\}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x\_i) =p\_i$.

More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $\[0,1\]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.

For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\\{0,1\\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?

# Answer
The Alias Method provides a means of sampling from a discrete distribution in $O(1)$ time, with $O(n)$ space and $O(n)$ pre-processing time.
> 2 votes

# Answer
Sampling can always be done in $O(\log n)$ time. As a precomputation, compute the prefix sums $p\_1$, $p\_1+p\_2$, $p\_1+p\_2+p\_3$, etc., and put them in an array. To randomly sample from $P$, pick a random real number $r \in \[0,1\]$ (via a uniform distribution), then use binary search to find the first index $i$ such that $p\_1+\dots+p\_{i-1} \le r$, then output $x\_i$. I will let you prove why this is correct.
> 0 votes

---
Tags: probability-theory, discrete-mathematics, probabilistic-algorithms, sampling
---


# Question
Title: Average depth of a Binary Search Tree and AVL Tree
My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary search trees and I don't think I am understanding the concept correctly. For example, if $n=4$ the tree is either going to have a node with a maximum depth of $3$ or node(s) with a maximum depth of $2$. In the case of where the maximum is $3$, then we would have nodes of $0$, $1$, $2$, and $3$ depths. This would give us an average depth of $1.5$ and $log(4)$ is $2$.

My professor also said that an AVL tree's nodes will ALWAYS have an average depth of $O(log(n))$, which makes even less sense to me, since with the example above of $n=4$ the closest we got to $log(4)$ was $1.5$ with a tree that had nodes of depth $0$, $1$, $2$, $3$ but in an AVL tree we couldn't have that tree.

The $O(log(n))$ stuff would kind of make sense if the root started with a depth of $1$, but I specifically asked the professor if that was the case and he said no.

# Answer
True, the height any fixed tree can range from logaritmic to linear (in terms of the number of nodes). The avarage depth of the nodes ranges correspondingly. So, trees can range from good (logaritmic) to bad (linear). The statement your professor seems to make is that the avarage binary search tree (BST) is in fact good. Or alternatively that by far most trees are good. Note that AVL-trees are designed to be good by their balanced construction.

How can we make this precise? A "random" BST with $n$ nodes is generated by taking a permutation $a\_1,a\_2,\dots,a\_n$ of $1,\dots,n$ and adding the numbers in that order to the bst. Of course $a\_1$ will be in the root. A measure for the total depth of all nodes in the tree is called internal path length (counting steps from root to all nodes). Now there is a nice "recursive" way of looking at internal path length. All numbers smaller than $a\_1$ will end up in the left subtree, those larger than $a\_1$ in the right subtree. So we can look at the smaller and larger numbers separately and consider the subtrees.

This forms the basis for a computation of the average internal path length over the $n!$ different permutations. (Actually, there are less trees than that: some permutations will give the same tree. That is only natural, as it is the way BST's are built.) This computation then shows the average internal path length to be in the order of $n \lg n$, so the avarage depth of a node in the avarage BST is order $\lg n$.

At least two books on Data Structures and Algorithm Analysis that I know have that derivation, by Weiss and Drozdek respectively. It also is in the TAoCP books by Knuth.
> 2 votes

# Answer
Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of nodes in the tree can be $\frac{n}{2}$. But assuming the tree is balanced, or the input is randomized, the expected depth will be $O(\log n)$ because the number of nodes present at each depth in the tree grows exponentially with the depth of the tree. ($2^0$ nodes at depth 0, and $2^1$ nodes at depth 1, etc). This is of course, subject to the constraint that the count of all nodes is equal to $n$, so the height of the tree will be $O(\log n)$.

The average depth of all the nodes in the tree will of course grow as the depth of the tree increases, and since the number of nodes present at a particular depth increases exponentially with the depth, the larger the tree is, the denser the deeper layers of the tree will be, and the more the deeper layers will dominate the average. So the average depth of nodes in the tree will approach the height of the tree, which we know to be $O(\log n)$. So the average depth of nodes in the tree is also $O(\log n)$.

Your professor mentioned that AVL trees will always have an average depth of $O(\log n)$. This is because AVL trees are balanced, so everything mentioned above always applies to AVL trees. They cannot end up being linear.

This is just an intuitive argument, not a proof. If you need a proof, see CLRS (Cormen Leiserson Rivest Stein) Introduction to Algorithms Third Edition pg 300. They have 3 pages of algebra as a proof.
> 3 votes

# Answer
These are balanced trees. That means, the algorithm for adding / removing elements from it provides that the difference of the depth of the subtrees remains below a (low) limit.

These trees are also recursive structures: the left and right child is of an AVL tree is also an AVL tree for which this property also consists. And so on.

This $O(log(n))$ is an asymptotic value, which means, while $n$ grows to infinity, the depth of an AVL tree will grow with $log(n)$. (More exactly, for AVL trees a $depth \< 1.44log(n)$ is guaranteed, it has a very beautiful proof, I suggest, don't miss it). For small $n$s it is possible some relatively larger deviation.

The BSTs aren't balanced for *every* inputs, it is easy to construct such an insertion ordering which degenerates them (the most simple if you add numbers linearly - essentially, you will get a list). But they will be nearly balanced if your insertions are quasi-randomly.

In the practical IT it is not a problem, because the explicit goal of these balanced trees is to handle *big* data structures (i.e. large $n$) *fast*. This is why is $O()$ used so many times in the Computer Science.
> 2 votes

---
Tags: algorithm-analysis, data-structures, search-trees, average-case, balanced-search-trees
---


# Question
Title: Does UDP always deliver packets inorder to the application layer
I was reading about UDP and TCP. TCP is a stream-oriented, connection-oriented protocol and always delivers the segments in order to the application layer.

But UDP being connectionless, does it also always deliver the datagrams to the application layer in order?

# Answer
> 4 votes
No. While UDP *does* deliver packets reliably 98-99% of the time, without duplicating packets 99.9% of the time, and in-order 99.9% of the time, there is absolutely no guarantee for either of these (in fact you are expected to be prepared for all of these), and reality verifiably *doesn't* look 100% perfect all the time.

UDP does very little more than raw IP. Datagrams are fired and forgotten (unless the application explicitly does *something* extra). They make it through a router, or they don't. Eventually, they arrive at the other end, possibly in a different order -- or they don't, for known and for unknown reasons. Rarely, they're duplicated for unknown and unpredictable reasons, and the two packets may take different routes, arriving in either order, and even after later datagrams.

Normally, UPD *just works*, but every now and then, there's packet loss, that's an unavoidable truth. Usually this happens in bursts (so you don't *randomly* lose one out of a hundred packets, but you get a few thousand of them 100% reliably, and then suddenly an intermediate router gets a hiccup on a full queue, and you lose a dozen packets).

If a datagram arrives, *and* if its checksum is good, *and* if there is space remaining in the receive buffer, it is placed in the receive buffer. Otherwise it is dropped (datagrams already in the buffer remain there).

An application using UDP **must** be prepared to deal with any and all of this.

Each time the receiving application performs a read/receive, a *complete* datagram -- if there is one -- is removed from the receive buffer, and gone forever thereafter (even if you've only read half of it). Never anything more, never anything less. Applications must also be prepared to deal with this.

If you want ordering, you must put in an explicit counter of sorts, and implement it yourself. If you want reliability, you must implement it (with some sort of ACK/NACK scheme).

# Answer
> 3 votes
Conversely from TCP, UDP does not guarantee a reliable or ordered delivery of the packets.
As the RFC states:

> This protocol provides a procedure for application programs to send messages to other programs with a minimum of protocol mechanism. The protocol is transaction oriented, and delivery and duplicate protection are not guaranteed. **Applications requiring ordered reliable delivery of streams of data should use the Transmission Control Protocol (TCP)**

Indeed, if you look at the UDP header there is nothing such as Sequence Number or Acknowledgment Number.

```
             0       7 8     15 16    23 24      31
             +--------+--------+--------+--------+
             |     Source      |   Destination   |
             |      Port       |      Port       |
             +--------+--------+--------+--------+
             |                 |                 |
             |     Length      |    Checksum     |
             +--------+--------+--------+--------+

```

Note also that using UDP does not mean that an ordered delivery of packets to the application layer cannot be achieved.
Indeed, UDP can be used in conjunction with an upper layer protocol that adds additional information, such as the sequence number.
See, e.g., RTP which is a Session layer protocol (OSI model) or Application layer (TCP/IP model).

---
Tags: computer-networks
---


# Question
Title: Are all terms of type forall a. a operationally bottom?
Is there a proof that all terms of type $\forall{a}. a$ are operationally $\bot$, in a non-weakly-normalising version of System F?

If you ask a free theorem calculator such as this one for the free theorem of $\forall{a}. a$ (written just $a$, as the tool adds implicit $\forall$s for each free type variable), you get the rather unhelpful

```
forall t1,t2 in TYPES, R in REL(t1,t2). (f_{t1}, f_{t2}) in R

```

Which seems to me only to imply that instantiations of $f$ at any two types are related by any relation.

Does this imply that $f$ must be a looping term?

# Answer
> 1 votes
Sure, just take `R` to be $\\{(\bot,\bot)\\}$, the relation which only relates bottoms.

This is a strict continuous relation, so it satisfies the requirements of the free theorem you linked to.

---
Tags: computability, type-theory
---


# Question
Title: Maximum subset pairwise not divisible by $K$
I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$. I tried to solve this problem, but I have found the quadratic solution, which is not efficient response.
$K \< 100, N \< 10000$, where $N$ is the number of elements and $K$ is given constant. Is there better than quadratic solution?

# Answer
Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n\_1$ and $n\_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words,

$$K \mid ( n\_1 + n\_2 ) ~~~~ \Longleftrightarrow ~~~~ K \mid \left((n\_1 ~mod ~K) + (n\_2 ~mod ~K)\right).$$

The second concept that you need to consider is that, the sum of two numbers $r\_1 \neq r\_2$ is $K$, only if one of them is strictly smaller than $K/2$ and the other is no less than $K/2$. In other words,

$$r\_1 + r\_2 = K ~~~\Rightarrow~~~ r\_1 \<K/2, ~r\_2 \geq K/2~~~~~~ (r\_1 \neq r\_2,~\text{w.l.g.}~r\_1 \< r\_2).$$

The third concept that you need to consider is that, if the sum of two numbers $r\_1 \neq r\_2$ is $K$, they both deviate from $\lceil K/2 \rceil -1$ by a certain $k \leq \lceil K/2 \rceil$, i.e.,

$$r\_1 + r\_2 = K ~~~\Rightarrow~~~ \exists\_{k \leq \lceil K/2 \rceil -1}~~~\text{such that}~~~ r\_1 = \lceil K/2 \rceil -1 -k, ~r\_2 = \lceil K/2 \rceil +k.$$

So, for evey $k$ in the third concept, you need to put either $r\_1$ or $r\_2$ in the solution set, but not both of them. You are allowed to put one of the numbers that are actually divisible by $K$ and if $K$ is even, you can add only one number that its remainder is $K/2$.

Therefore, here is the algorithm.

Given a set ${\cal N}=\\{ n\_1, n\_2, \cdots, n\_N \\}$, let's find the solution set ${\cal S},$

1. Consider ${\cal R} = \\{ r\_1=(n\_1 ~mod ~K), r\_2=(n\_2 ~mod ~K), \cdots, r\_N=(n\_N ~mod ~K) \\}$
2. ${\cal S} \gets \emptyset$
3. for $k \gets 1$ to $\lceil K/2 \rceil -1$:
4. $\hspace{1.3em}$ if $count({\cal R},k) \geq count({\cal R},K-k)$:
5. $\hspace{2.6em}$ add all $n\_i$ to ${\cal S}$, such that $r\_i=k$
6. $\hspace{1.3em}$ else:
7. $\hspace{2.6em}$ add all $n\_i$ to ${\cal S}$, such that $r\_i=K-k$
8. add only one $n\_i$ to ${\cal S}$ such that $r\_i=0\hspace{1em}$*// if exists*
9. if $K$ is even:
10. $\hspace{1.3em}$ add only one $n\_i$ to ${\cal S}$ such that $r\_i=K/2\hspace{1em}$*// if exists*
11. Output ${\cal S}$

The algorithm is quite long, but the idea is very simple.
> 15 votes

# Answer
Consider a set S of size n containing all distinct natural numbers. We have to form the maximal subset from this set . We use a basic modulus property and add a few deductions to it to solve the problem. I hope it is helpful for you all.

For any two natural numbers N1 and N2 : (N1+N2)mod(K)=(R1+R2)mod(K) where R1=N1modK and R2=N2%K. 1. If we (N1+N2)modK=0 it means (R1+R2)%K=0. 2. That means R1+R2 must equal either K,2K,3K.... 3. But R1 lies between 0 & K-1 and so does R2 , which means their sum can't exceed K-1+K-1 = 2(K-1). 4. From 2 and 3 we can conclude that R1 + R2 must be equal to K. 5. Further if R1+R2 =K that means either both of them must be equal to K/2 (only possible if K is even) or one of them must be lesser than floor\[K/2\] and one greater than the same. 6. Suppose R1=T and R2=K-T , if we take any number N1 from S whose remainder is R1 and any number N2 from S whose remainder is R2 then their sum will be divisible by K. Therefore the Solution subset can have either those numbers with remainder R1 or those with remainder R2 but not both .

Now Suppose we construct an Array R of size K with index 0 through K-1 , The element in each index denoting the number of numbers in the set S with remainder (on division with K ) equal to the index number. We cant have more than 2 numbers with their remainder 0 as their sum would be divisible by K therefore we must initialise our counter with min(R\[0\],1). For T=1 to T

The code for the same algorithm in C++ is as shown below:

```
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {

    int n,k;
    cin>>n>>k;
    vector <int> a(n);
    vector <int> r(k,0);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        r[a[i]%k]++;
    }
    int ctr=min(1,r[0]);
    for(int a=1;a<(k/2+1);a++)
        {
            if(a!=k-a)
                ctr+=max(r[a],r[k-a]);
        }
    if(k%2==0&&r[k/2]!=0)
        ctr++;
    cout<<ctr;
    return 0;
}

```
> 1 votes

# Answer
I tried translating to C# code, the first to only count the size of the subset array and another including the entire (hash)subset.

Count:

```
static int nonDivisibleSubset(int k, int[] S)
{
    var r = new int[k];

    for (int i = 0; i < S.Length; i++)
        r[S[i] % k]++;

    int count = Math.Min(1, r[0]);

    if (k % 2 == 0 && r[k / 2] != 0)
        count++;

    for (int j = 1; j <= k / 2; j++)
    {
        if (j != k - j)
            count += Math.Max(r[j], r[k - j]);
    }

    return count;
}

```

With subset:

```
static int nonDivisibleSubset(int K, int[] S)
{
    var r = new HashSet<int>();
    var d = S.GroupBy(gb => gb % K).ToDictionary(Key => Key.Key, Value => Value.ToArray());

    for (int j = 1; j <= K / 2; j++)
    {
        var c1 = d.GetValueOrDefault(j, new int[0]);
        var c2 = d.GetValueOrDefault(K - j, new int[0]);

        if (c1.Length == c2.Length) continue;

        r.UnionWith(c1.Length > c2.Length ? c1 : c2);
    }

    if (d.ContainsKey(0))
        r.Add(d[0].Max());

    if (K % 2 == 0 && d.ContainsKey(K / 2))
        r.Add(d[K / 2].Max());

    return r.Count;
}

```
> 0 votes

---
Tags: algorithms, efficiency
---


# Question
Title: Probability that a random graph will remain planar after adding an edge
According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is a necessary condition for planarity) is: $$2^{-n(n-1)/2}\sum\_{k=0}^{3n-6}{n(n-1)/2\choose k}$$

Therefore, the plot for this equation is:

> If I choose a random graph with 10 vertices, what is the probability that it will remain planar after adding an edge between two randomly chosen vertices?

To be more clear:

Consider event $P\_{1}$, the event of choosing a planar graph $G\_{1}$ in the universe $U\_{10}$ of graphs with 10 vertices.

Consider a subset $S$ of the universe of graphs with 11 vertices $U\_{11}$ conditionally defined by the graph $G\_{1}$ we got in event $P\_{1}$ in this way: $S$ is formed by all possible graphs that can result from adding one edge to $G\_{1}$.

And then finally consider event $P\_{2}$, the event of choosing a planar graph in the universe $S$ defined in the previous step.

Therefore I want to know what is the probability of event $P\_{2}$.

**Possible solution**:

I followed D.W.'s advice below and wrote a small simulation. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ).

```
#!/usr/bin/python3
import planarity
from itertools import combinations
import random
from multiprocessing import Process, Manager, Pool, cpu_count
import json

nodes = [str(x) for x in range(10)]
edges = list(combinations(nodes,2))
tests = 10**6
filename = 'results.json'
runs = 100

def make_test():
    while 1:
        chosen_edges = list(filter(lambda x: x != None, [x if random.choice([0,1]) else None for x in edges]))
        if planarity.is_planar(chosen_edges):
            break
    extra_edge = random.choice( list(set(edges) - set(chosen_edges)) )
    chosen_edges += [extra_edge]
    return planarity.is_planar(chosen_edges)

if __name__ == '__main__':

    for i in range(runs):
        with Pool(processes=cpu_count()) as pool:
            results = [ pool.apply_async(make_test, ()) for i in range(tests) ]
            lst = [ res.get(timeout=1) for res in results ]
        pool.close()
        pool.join()

        n = len(lst)
        p = len(list(filter(lambda x: x != False, lst)))
        prob = ( p / n )
        print(prob)

        try:
            with open(filename,'r') as f:
                file_lst = json.load(f)
        except:
            open(filename,'w+').close()
            file_lst = []
        file_lst += [prob]
        with open(filename,'w') as f:
            json.dump(file_lst,f)

```

# Answer
Let $S$ be the set of planar graphs on $n$ vertices, and let $E(S,\overline{S})$ be the set of edges between $S$ and its complement, that is, the set of pairs $(G,e)$ where $G \in S$ and $G \cup \\{e\\} \notin S$. The edge-isoperimetric inequality states that $$ \frac{|E(S,\overline{S})|}{|S|} \geq \binom{n}{2} - \log\_2 |S|. $$ It follows that the probability that you're after is at most $$ \frac{\log\_2 |S|}{\binom{n}{2}-(3n-6)}. $$ It is known that $\log\_2 |S| = O(n \log n)$ (see for example Gimenez and Noy, The number of planar graphs and properties of random planar graphs, and so we conclude that your probability is at most $O\left(\frac{\log n}{n}\right)$.

On the other hand, the same paper shows that with constant probability, a random planar graph has an isolated vertex. When this happens, there is $\Omega\left(\frac{1}{n}\right)$ probability to add an edge adjacent to it, leaving the graph planar. Hence your probability is at least $\Omega\left(\frac{1}{n}\right)$.
> 4 votes

# Answer
I don't know that you're going to find an explicit formula. (You don't even seem to have a formula for the probability that a random graph on 10 vertices is planar, let alone the more complex random process you describe. The formula you give is merely an upper bound for the probability of being planar, not a formula for that probability.)

But you can easily estimate this probability through simulation. Generate 1 million random graphs using this procedure, and test whether the result is planar. Then the fraction that were planar is a good estimate of the underlying probability. That should be easy to code up and fast to run.
> 0 votes

---
Tags: graphs, probability-theory
---


# Question
Title: How to collect all states of a behavior in TLA+?
***Description of the problem:***

I am modeling checking a distributed protocol against a global property with TLA+ developed by Leslie Lamport. The global property is defined on all states of a behavior (more details can be found below). However, by the nature of exhaustive enumeration of model checking, the state transition graph explored consists of all states of all behaviors. How should I collect all states of each behavior against which the global property can be checked?

---

***More on the global property:***

Consider an implementation of a replicated list object. The property requires that for any two list states, e.g., $l\_1$ and $l\_2$, across the whole system, if they contain two common elements such as $a$ and $b$, then $a$ precedes $b$ in $l\_1$ if and only if $a$ precedes $b$ in $l\_2$.

My solution is to check this property against each behavior. This requires to collect all states of a behavior. Is this feasible? Are there better solutions?

---

***Note:*** This is a re-post.

# Answer
> 1 votes
***An answer from Stephan Merz at tlaplus-googlegroup:***

In a linear-time framework such as TLA+, a system satisfies a property if the property holds of all system behaviors, and from your description it appears to me that this is what you want. TLC will compute all states that are reachable in your system and evaluate the property over all behaviors: there is nothing that you need to do explicitly.

The potential problem with this is that your system may have a lot of states, and TLC may not finish computing the entire state graph (or at least not in a reasonable amount of time). The TLA+ literature and resources give much advice for working around this problem, in short, you will want to choose small parameters and perhaps constrain the set of states considered by TLC using a state constraint (in the advanced options pane of the Toolbox interface).

---
Tags: formal-methods, model-checking, tlaplus
---


# Question
Title: Chernoff-like Concentration Bounds on Permutations
Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y\_i$ the number of black balls in the first $i$ positions of our permutation $\pi$. I would like to show that $Y\_i$ is sharply concentrated around its mean.

**The expected value**

It is not hard to compute the expected value of $Y\_i$: the probability that a black ball appears somewhere along the first $i$ positions is $i/n$; moreover, there are $m$ black balls, hence $$\mathbb{E}\[Y\_i\] = \frac{m\cdot i}{n}.$$

But can we show that $Y\_i$ is actually very close to its mean?

**A failed attempt**

For every black ball $b$, one can define an indicator variable $X\_b$ which equals 1 if $b$ appears in the first $i$ positions of $\pi$ and 0 otherwise. Denoting the set of all black balls by $B$, we have

$$ Y\_i = \sum\_{b \in B} X\_b.$$

I was hoping to be able to use a Chernoff bound type of a concentration bound, but unfortunately for two black balls $b$ and $b'$, $X\_b$ and $X\_{b'}$ are not completely independent. If $X\_b = 1$, then there are only $i-1$ spots left for $b'$ to appear in the first $i$ locations and hence the probability of $X\_{b'}$ being 1 gets smaller.

# Answer
Chernoff's bound applies to *negatively correlated* random variables, such as your hypergeometric distribution. You can find a full treatment in Dubhashi and Panconesi's very useful monograph *Concentration of measure for the analysis of algorithms*, as well as in many lecture notes, such as this one by Hariharan Ramesh.
> 4 votes

# Answer
Following Yuval's answer, I found the following inequality in Dubhashi and Paconesi's book:

$$ \Pr \Big\[\big|Y\_i - \mathbb{E}\[Y\_i\]\big| \geq t \Big\] \leq \exp\Big(\frac{-(n-1)t^2}{2(n-i)(i-1)} \Big)$$
> 2 votes

---
Tags: permutations, chernoff-bounds
---


# Question
Title: Randomized quicksort expected running time analysis
I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis.

### Setting in CLRS

First let $Z = \\{z\_1, ..., z\_n\\}$ be the set of elements of the input array $A$ in sorted order. $X$ is defined as the number of comparison we make (i.e., between pivot and an element). Because any two elements of the array $A$ is compared at most once, we have $X = \sum\_{i=1}^{n-1} \sum\_{j = i+1}^{n} X\_{ij}$ where $X\_{ij} = 1$ if $z\_i$ and $z\_j$ are compared. So we just need to calculate the expectation, $\mathbb{E} \left\[ X \right\] = \sum\_{i=1}^{n-1} \sum\_{j=i+1}^{n} \mathbb{P} \left(X\_{ij} = 1\right)$.

So we just need to calculate $\mathbb{P} \left(X\_{ij} = 1\right)$. According to the book, $\mathbb{P} \left(X\_{ij} = 2\right) = \frac{1}{j - i + 1}$ and I don't follow this result.

### My analysis

Let $k$ be the index of the randomly selected pivot. Conditioning on the event that $k \in Z\_{ij}$ where $Z\_{ij} = \\{z\_i, z\_{i+1}, ..., z\_j\\}$,

\begin{equation} \begin{aligned} \mathbb{P} \left(X\_{ij} = 1\right) &= \mathbb{P} \left( \left.X\_{ij} = 1 \right| k \in Z\_{ij}\right) \mathbb{P} \left(k \in Z\_{ij} \right) + \mathbb{P} \left( \left.X\_{ij} = 1 \right| k \not\in Z\_{ij}\right) \mathbb{P} \left(k \not\in Z\_{ij} \right) \\ &= \frac{2}{j - i + n} \frac{j - i + 1}{n} + \mathbb{P} \left( \left.X\_{ij} = 1 \right| k \not\in Z\_{ij}\right) \left(1 - \frac{j - i + 1}{n} \right). \end{aligned} \end{equation}

From this, we can see that if $\mathbb{P} \left( \left.X\_{ij} = 1 \right| k \not\in Z\_{ij}\right) = \mathbb{P} \left(X\_{ij} = 1 \right)$, then indeed $\mathbb{P} \left(X\_{ij} = 1 \right) = \frac{2}{j-i+n}$ agreeing the book's result. But I don't think that equality holds.

Suppose we choose pivot $k \> j$ which is not in $Z\_{ij}$. Then, we reduce the problem size to $\\{1, ..., k-1\\}$. Because $z\_i$ and $z\_j$ still belong to the same partition, we are given another chance to pick another pivot such that it is either $i$ or $j$. So I would expect that $\mathbb{P} \left( \left.X\_{ij} = 1 \right| k \not\in Z\_{ij}\right) = \mathbb{P} \left(X\_{ij} = 1 \right)$ does not hold.

### Question

Is my analysis correct, i.e., $\mathbb{P} \left( \left.X\_{ij} = 1 \right| k \not\in Z\_{ij}\right) \not= \mathbb{P} \left(X\_{ij} = 1 \right)$? If not, how to derive $\mathbb{P} \left(X\_{ij} = 1 \right)$ considering the fact that if the chose pivot is not in $Z\_{ij}$ we are given another chance?

---

### Update

Yuval Filmus' answer is very good and complete in itself. But let me just add a little more step just for completeness. In particular steps leading to $\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1}$ were not trivial to me. So hopefully this may help others.

As Yuval Filmus said we can prove that $p(n,i,j) = 2/(j-i+1)$ using (strong) induction (over $n$). First check the base case which is $n = 2$ because we need at least two elements in order to even think about comparing $z\_i$ and $z\_j$. With $n = 2$, $j = 2$, $i = 1$ and $p(2,1,2) = \frac{2}{2 - 1 + 1} = 1$. If we have 2 elements, then pivot has to be one of them, and $\mathbb{P} \left(X\_{ij} =1; 2\right) = 1$. This proves the base case.

Now consider the inductive step. Assume that $p(m,i,j) = \frac{2}{j-i+1}$ for all $m \< n$. In particular, note that all the values of the first argument of $p(\cdot, \cdot, \cdot)$ inside both summations are less than $n$. Hence, we can plug in $p(m,i,j) = \frac{2}{j-i+1}$.

\begin{equation} \begin{aligned} p(n,i,j) &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{1}{n} \sum\_{k=1}^{i-1} \frac{2}{(j-k)-(i-k)+1} + \frac{1}{n} \sum\_{k=j+1}^{n} \frac{2}{j-i+1} \\ &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{2}{n} \frac{i-1}{j-i+1} + \frac{2}{n} \frac{n-j}{j-i+1}, \end{aligned} \end{equation}

which is the expression given by Yuval Filmus. The rest of the step is in his answer.

# Answer
Let us denote by $p(n,i,j)$ the probability that $X\_{ij} = 1$ given that there are $n$ elements.

Let $k$ be the first chosen pivot. If $k \in \\{i,j\\}$ then $X\_{ij} = 1$. If $i \< k \< j$, then $X\_{ij} = 0$. Otherwise, if $k \< i$ then $X\_{ij} = 1$ with probability $p(n-k, i-k, j-k)$, and if $k \> j$ then $X\_{ij} = 1$ with probability $p(k-1, i, j)$. Altogether, we get $$ p(n,i,j) = \frac{2}{n} + \frac{1}{n} \sum\_{k=1}^{i-1} p(n-k, i-k, j-k) + \frac{1}{n} \sum\_{k=j+1}^n p(k-1,i,j). $$ We can now prove that $p(n,i,j) = 2/(j-i+1)$ by induction, by noticing that $$ \frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1} = \\ \frac{2}{n} + \frac{2}{n} \cdot \frac{n-(j-i+1)}{j-i+1} = \\ \frac{2}{n} + \frac{2}{j-i+1} - \frac{2}{n} = \\ \frac{2}{j-i+1}. $$ Another way to get this result is to follow the algorithm until the first time when a pivot (at any level of recursion) in $\\{i,\ldots,j\\}$ gets selected. Elements $i$ and $j$ are compared if and only if this pivot happens to be $i$ or $j$, which happens with probability $2/(j-i+1)$.
> 1 votes

---
Tags: time-complexity, randomized-algorithms, quicksort
---


# Question
Title: Why use logic gates in this situation? (XOR gates)
I came across this circuit that swaps logical signals:

However I don't understand why would you need to use logic gates. Would it be possible to just connect the A on the left to the B on the right and the same with the B on the left (maybe add a diode to prevent current from going back?).

And one last question; would an "Enable" signal make this circuit more useful (only swaping when Enable is high)?

Maybe I'm missing something. Thank you.

# Answer
One reason for using such a circuit is to avoid wire crossing. Integrated circuits are laid out on several planar layers, and inside each layer, wires are not allowed to cross (for obvious reasons). Hence if you want to switch two wires, you either need to reach out to a different layer, or to use a gadget such as the one shown. I have no idea whether this kind of gadget is actually used in practice.

It should be noted that same idea can be used to swap two values without using any additional memory:

1. $A \gets A \oplus B$
2. $B \gets B \oplus A$
3. $A \gets A \oplus B$

In a C-like language, this would be `A ^= B; B ^= A; A ^= B`. This code corresponds to an execution of your circuit in topological order.
> 1 votes

---
Tags: logic
---


# Question
Title: Why is static-single assignment preferred over continuation passing style in many industry-used compilers?
According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects using continuation-passing style (CPS) is a bit lacking in comparison.

I have this notion that CPS is preferred by compilers and interpreters that implement primarily functional languages -- particularly, Haskell and Scheme seem to have strong inclinations towards CPS style due to the restrictions on mutation or need for first-class continuation support (I would guess that Smalltalk would possibly need this as well). The major literature that I've encountered that uses CPS seems to be those that are primarily working on Scheme or are related to Scheme in some respect.

Is there any particular reason why SSA is used in industry besides momentum of adoption? SSA and CPS have a close relationship; that means that it would be easy to state either in terms of another, but perhaps the information representation would be less compact or less efficient for CPS.

# Answer
> 17 votes
I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-based techniques for compilation unless the language itself supports control operators like `call/cc`. Something more like Administrative Normal Form (ANF) (sometimes also referred to as Monadic Normal Form which is intimately related for reasons that will become clear) is used which has an even tighter relationship to SSA than CPS does.

If I remember correctly, administrative normal form gets its name from the fact that CPS-based compilation can lead to beta-redexes in the intermediate code that didn't correspond to anything in the source code. These were referred to as "administrative redexes". These could reduced at compile-time, but there was a good amount of research on performing a CPS transform that would output code without the administrative redexes in the first place. The goal then was to produce output in a normal form where all "administrative" redexes were reduced, and this was the origin of Administrative Normal Form. It didn't take long to realize there wasn't a whole lot of benefit to viewing this as a(n optimization of a) two-step process: CPS-transform, reduce administrative redexes. In particular, administrative normal form looks rather like monadic-style as practiced (by hand) most notably in Haskell. The CPS transform can be understood as a conversion to monadic-style where you just happen to be using the CPS monad (so there's really multiple ways to "convert" to monadic-style corresponding to different evaluation orders). In general, though, you could be using a quite different monad, and so conversion to monadic-style and thus administrative normal form isn't really related to CPS in particular.

Nevertheless, there were some benefits to CPS versus ANF. In particular, there were certain optimizations that you could do in CPS with just standard optimizations, such as beta reducing, that required (seemingly) ad-hoc rules for ANF. From the monadic perspective, these rules correspond to commuting conversions. The upshot is now there is a theory that can explain what rules should be added and why. A recent paper gives a (new and) pretty clear description of this (from a logical perspective) and its related work section serves as a brief but decent survey of and references into the literature on the topics I mention.

The problem with CPS is tied to one of its main benefits. CPS transforming allows you to implement control operators like `call/cc`, but this means every non-local function call in the CPS intermediate code has to be treated as potentially performing control effects. If your language includes control operators, then this is just as it should be (though even then most functions probably aren't doing any control shenanigans). If your language *doesn't* include control operators, then there are global invariants on the use of continuations that are not evident locally. This means there are optimizations that are unsound to perform on general CPS code that would be sound to perform on this particularly well-behaved use of CPS. One way this manifests is in the change in precision of data and control flow analyses. (CPS transforming helps in some ways, hurts in others, though the ways it helps are mostly due to duplication rather than the CPS aspect itself.)1 You could, of course, add rules and adjust analyses to compensate for this (i.e. to exploit the global invariants), but then you've partially defeated one of the major benefits of CPS-based compilation which is that many (seemingly) special-purpose, ad-hoc optimizations become special-cases of general-purpose optimization (particularly beta reduction).

Ultimately, unless your language has control operators, there is usually not much reason to use a CPS-based compilation scheme. Once you compensate for the issues I mentioned above, you've typically eliminated the benefits of CPS-based compilation and produced something equivalent to not using CPS. At that point, CPS is just making convoluted looking intermediate code for not much benefit. An argument for CPS-based compilation from 2007 addresses some of these issues and presents some other benefits using a different form of CPS conversion. The things that paper brings up are covered in part by the (2017) paper I mentioned before.

1 Doesn't the equivalence between SSA and CPS make this more or less impossible? No. One of the first things the paper introducing this equivalence states is that the equivalence does *not* work for *arbitrary* CPS code, but it does work for the output of a CPS transform (which they define) for a language *without* control operators.

# Answer
> 2 votes
I'm not a compiler expert, so take what I say with a grain of salt, I hope that a real compiler expert will chime in. I was told that:

* CPSed code tends to jump non-locally a lot, which ruins cache locality, hence performance.
* CPS requires more expensive garbage collection than conventional compilation which can typically store a lot of stuff on the stack (which is faster to allocate and deallocate).

Both conspire to making code compiled by CPS-transform comparatively slow.

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


title: Counting Inversions with merge-sort

text:
# Question
Title: Counting Inversions with merge-sort
I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array.

The idea that they used was:

1. Break the original array in half.
2. Count the inversions in each half
3. Pass the original array through mergeSort to get the split inversions

If this is so, then I do not understand how can the mergeSort not recount the inversions from each half.

From what I thought, every time I pick the element from the right array over the element from the left array that would be an inversion. And since we work recursively into basic single elements of the array, this would also go through each of the halves when merging, therefore recounting.

Am I missing something?

# Answer
> 2 votes
An inversion is a pair of indices $(i, j)$, with $i \< j$ and $a\_i \> a\_j$. If you separated the array into two halves, then the inversions fall into three categories:

* both indices of an inversion appear in the left half -\> we count those in the first recursive call
* both indices of an inversion appear in the right half -\> we count those in the second recursive call
* $i$ is in the left half, and $j$ is in the right half.

So in the merge step, we need to make sure that we **only** count those inversions of the third type.

By taking the definition of inversion, this translates as follows: For each element in the left half ($a\_i$), count how many elements in the right side are smaller ($a\_j$). It should be obvious, that this really counts all inversions of the third category, and that it only counts these. This translation also gives a very native $O(n^2)$ implementation of this step.

To make this more efficient, we can use the fact that both halves are sorted after the recursive calls, and we can use two pointers so that we can accomplish this step in $O(n)$. The pointers point to the first unprocessed element in each half. Then we take the smaller one of the two unprocessed elements, and put it in our merged array. If this one is of the first half, then we can count in constant time how many were smaller than it in the second half (by looking at the index of the second pointer).

---
Tags: mergesort
---


# Question
Title: Is there an efficient algorithm for expression equivalence?
e.g. $xy+x+y=x+y(x+1)$ ?

The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or division. Letters are variables.

If it helps, we can forbid any expression representable with numeric values other than $1$; i.e. not $x^2$ nor $3x$ nor $4$:

* *multilinear*, no **powers** other than $1$: $x+xy \equiv x^1+x^1y^1$ is OK, but not $x^2+x^3y^4$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $x(x+y) \equiv x^2+y$;
* *all one*, no **coefficients** other than $1$: $x+xy \equiv 1.x+1.xy$ is OK, but not $2x+3xy$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $a(x+y)+x(a+b) \equiv 2ax+ay+bx$ ; and
* no **constants** other than $1$: again, in the fully expanded sum-of-products e.g. not $(a+1)+(b+1) \equiv a+b+2$

$Q.$ Is there an efficient algorithm to determine if two expressions are equivalent?

---

To illustrate, here's an inefficient brute-force algorithm with exponential time:

> expand both expressions fully to *sum-of-products*, which can easily be checked for equivalence (just ignore order, since commute/associate can reorder).

e.g.
$(a+b)(x+y) \rightarrow ax+ay+bx+by$
$a(x+y)+b(x+y) \rightarrow ax+ay+bx+by$

---

This seems a well-known problem - even high school students are taught manual ways to solve it. It's also solved by automated theorem provers/checkers, but they concentrate on more sophisticated aspects.

Here's a working online automated theorem prover: http://tryacl2.org/, which shows equivalence by finding a sequence of commute/associate/distribute etc:

$xy+x+y=x+y(x+1)$ ?
`(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))` --- 188 steps

$y+x(y+1)=x+y(x+1)$ ?
`(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))` --- 325 steps

*This is my first question here, so please let me know if I've chosen the wrong place, wrong tags, wrong way of describing/asking etc. Thanks!*
*NB: this question has been rewritten in response to comments*
*Thanks to all responders! I've learned a lot.*

# Answer
> 8 votes
Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms.

Your expressions are all multivariate polynomials. Apparently, your expressions are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e\_1,e\_2$ are expressions, then $e\_1+e\_2$ and $e\_1e\_2$ are expressions. If that's indeed what you intended, every expression is a multivariate polynomial over the variables.

Now, you want to know if two expressions are equivalent. This amounts to testing whether two multivariate polynomials are equivalent: given $p\_1(x\_1,\dots,x\_n)$ and $p\_2(x\_1,\dots,x\_n)$, you want to know if these two polynomials are equivalent. You can test this by subtracting them and checking whether the result is identically zero: define

$$q(x\_1,\dots,x\_n) = p\_1(x\_1,\dots,x\_n) - p\_2(x\_1,\dots,x\_n).$$

Now $p\_1,p\_2$ are equivalent if and only if $q$ is the zero polynomial.

Testing whether $q$ is identically zero is the zero testing problem for multivariate polynomials. There are efficient algorithms for that. For instance, one example algorithm is to evaluate $q(x\_1,\dots,x\_n)$ at many random values of $x\_1,\dots,x\_n$. If you find a value of $x\_1,\dots,x\_n$ such that $q(x\_1,\dots,x\_n)$, then you know that $q$ is not identically zero, i.e., $p\_1,p\_2$ are not equivalent. If after many trials they are all zero, then you can conclude that $q$ is identically zero (if $q$ is not identically zero, the probability that all of those trials yield zero can be made exponentially low). The number of iterations you need to do is related to the degree of $q$; see the literature on polynomial identity testing for details.

For instance, see https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel\_lemma and http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/

These algorithms apply if you are working over a finite field. You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$. If you are working over a finite field, the methods above apply immediately.

If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients. You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$. Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.

# Answer
> 0 votes
To follow up on the **one-power**, **one-coefficent** and **one-constants** constraints in the question:

These define a subset the problem of polynomial identity testing. Clearly, they can be solved with a technique that solves the general problem. The question is whether they form a subset that is more easily solved.

**one-coefficient**: in problems without this, terms might be combined, making the problem easier. Consider the Binomial Theorem/Pascal's triangle for $(a+b)^n$. This can be expanded one factor at a time, producing terms with overlapping orders e.g. $(a+b)(a+b) = aa+ab+ab+bb = aa+2ab+bb$ The fewer terms make it easier to expand with the next factor: $(aa+2ab+bb)(a+b) = aaa+2aab+abb + aab+2abb+bbb = aaa+3aab+3abb+bbb$ and again terms are combined, making a smaller simpler problem. This combining of terms is a form of dynamic programming.

That is, the possibility of combining terms, creating a non-one coefficient, makes the problem easier not harder.

(Although there is more work in calculation in multiplying non-one coefficients)

**non-one constants** are included in the above argument by considering constants as variables with zero exponent.

**one-power** I don't think this makes any difference. Although non-one exponents can be created in more than one way (e.g. $a^4=a^2a^2=a^1a^3$), and this can lead to overlap and combination (as in the Binomial Theorm/Pascal's triangle above), actual combination is only possible if non-one coefficients are allowed.

The above is not a formal or rigorous argument. It rests on an assumption about what makes the problem difficult. But it does seem to me that combining terms only makes for an easier problem - so preventing this by the **one coefficient** constraint is not going to make the subset easier.

---
Tags: complexity-theory, time-complexity, decision-problem
---


# Question
Title: Is Alan Turing's proof of the incomputability of halting problem invalid?
I fail to see a contradiction in the halting machine proposed by Alan Turing.

**Definition of halting machine**
Where
H = all possible programs that terminates
N = all possible programs that do not terminate
$N\_p$ = a program that does not terminate e.g.while True do x:=0
T = true
F = false
if a program outputs T or F then it also means that the program terminates
f is a program
h(f) is the halting machine
n(x) is the negator
\begin{equation\*} h(f) = \begin{cases} T & \text{if } f \subset H \\ F & \text{if } f \subset N \end{cases} \quad \end{equation\*}

\begin{equation\*} n(x) = \begin{cases} N\_p & \text{if } x = T \\ F & \text{if } x = F \end{cases} \quad \end{equation\*}

\begin{equation} \begin{aligned} nh(f) &= n(h(f)) \\ & = \begin{cases} N\_p & \text{if } f \subset H \\ F & \text{if } f \subset N \end{cases} \quad \end{aligned} \end{equation}

\[$nh\_0, nh\_1, nh\_2$ are all the same program as $nh$\]
**Showing contradiction** \- finding output of $nh\_2(nh\_1(nh\_0))$

\begin{equation} nh\_2(nh\_1(nh\_0))= n\_2(h\_2(n\_1(h\_1(nh\_0)))) \end{equation}
\[Step by step execution of $n\_2(h\_2(n\_1(h\_1(nh\_0))))$\]
let $nh\_0 \subset N$ \[we make an assumption that $nh\_0$ do not halt\]
$h\_1(N)=\>F \equiv h\_1(nh\_0)=\>F$
$n\_1(F)=\>F$
$h\_2(F)=\>T \equiv h\_2(nh\_1)=\>T$
$n\_2(T)=\>N$
**Alan Turing's argument**
$nh\_0$ and $nh\_1$ is the same program, therefore output of the halting machine should be the same when the programs are passed in as an input but they contradict, therefore halting machine can not be made.
\begin{equation} nh\_0 \equiv nh\_1 \\ h\_1 \equiv h\_2\\ \therefore h\_1(nh\_0) = h\_2(nh\_1)\\ \text{However, } h\_1(nh\_0)=F \text{ and }h\_2(nh\_1)=T\\ \therefore \text{logical contridiction and thus halting machine can not exist} \end{equation}
**Objecting Alan Turing's argument**
$h\_1(nh\_0)$ and $h\_2(nh\_1)$ gives different output not because halting machine can not exist but because $nh\_0$ and $nh\_1$ are not the same.
$nh\_0$ and $nh\_1$ is the same program, but in this case they are receiving different input, therefore they represent a different thing.
The halting machine gives different output for the same program because they are analyzing different part of the same function.
i.e.
h(if(f==H)Then func1 else func2) $\equiv$ if(f==H)Then h(func1) else h(func2))
h(func1)!=h(func2)
I think this idea is backed up by Professor Eric C.R. Hehner's paper - **Reconstructing the Halting Problem** and **Problems with the Halting Problem**.
**To summarize my question.**

1. Is my understanding of Alan Turing's take on halting problem correct?
2. Is my objection to Alan Turing's idea correct?
3. Is Professor Eric C.R. Hehner's objection and my objection agreeing / the same thing?

# Answer
Alan Turing's proof of incomputability(**the Original Proof**) is presented in the last paragraph in this paper that is cited by OP. A sketch of the proof (**Wikipedia Proof**) at wikipedia are more or less the same as as the original proof. I will assume that OP is talking about (some version of) the Original Proof or the Wikipedia Proof. Either proof should fit for OP's question and this answer, although the latter one might be easier for us modern readers.

"1. Is my understanding of Alan Turing's take on halting problem correct?"
"2. Is my objection to Alan Turing's idea correct?"

**I doubt.**

In fact, **it is not easy for me to understand your symbols and logic unambiguously**. For example, is $N$ in your exposition a set of programs or just a single specific program or either one depending on which line(or context) it appears? For example, you have not introduced $h\_0$ before using it. For example, you are using "$\Rightarrow$" (or its not-formatter form "=\>") to mean output, while all (modern) textbooks on logic or computer science or mathematics (that I know) use that symbol to mean implication. For example, I fail to see exactly why you choose to use $\equiv$ in some occasion and $=$ in other occasions(although I did have some clue).

Your objection to Alan Turing's argument seems to be resting on the statement "The halting machine gives different output for the same function because they are analyzing different part of the same function". **That statement alone makes it hard for me to believe you understand fully Alan Turing's construction and argument.** By the rigorous definition of the (imaginary) halting machine, it must have the same well-defined output every time when it is given the same well-defined input, no matter what else may happen. To ensure that the halting machine is getting exactly the same well-defined input, Turing employs his well-defined mapping from machines (or programs as you call them) (or algorithms as we may call) (that have been defined precisely by Turing for purpose thereof and much beyond) to natural numbers.

So I have to wonder and I could not understand that you believe "The halting machine ... are analyzing different part of the same function" and "The halting machines are both receiving representation of the same program as an input but they are representation of same program with different parameter." Let me state again. **The input to the halting machine used in Turing's proof is the same (although imaginary) program (with the same parameter, if one considers some part of it as its parameter).** There has been one specific and concise description of that input.

In fact, I would venture to say that you miss one simple point of the Original Proof or the Wikipedia Proof or, simply, the proof of concept at wikipedia. However, I cannot find which simple point you missed. I have failed to actually fully understand your notation and semantics after many attempts (which, you can say, render (part of) my answer useless). Well, I welcome other answers that can claim to understand your approach and logic. I do claim that I understand professor Eric's objection to the Original Proof (and some of his later work on "Objective and Subjective Specification")

I recommend strongly that you find some knowledgeable guy around you (or remotely) to have an interactive discussion, perhaps learning a bit of rigorous logic and notations. That is the best reasonable answer to your question I believe. Or you can try reading some popular textbooks beyond "my high school computer science". ( I did several). Or, as Yuval Filmus suggested, (if you have not), try taking a look at some of the other questions on this site or on the web which contain (discussion on or) objections to Turing's proof. (I did). By the way, sorry if I sound insincere, but do you believe that you are able to explain the Original Proof to any fellow round you (or to yourself)? I would also suggest that you raise a new question instead of updating this one after you have followed my advice seriously.

"3. Is Professor Eric C.R. Hehner's objection and my objection agreeing / the same thing?"

**I would not believe that.** Note that it takes quite some writing effort for Professor Eric C.R. Hehner (even in his second paper where he presents "a drastically shortened version" of his first paper) to explain his proposition that because of a logic gap, Alan Turing's famous reasoning on halting problem does not prove the incomputability of the halting problem.

**Profess Eric argues that the halting machine constructed by Turing is logically inconsistent in the same way as (or in a similar way to) Bertrand Russell's definition of a barber.** That inconsistency exists before we even have the notion of incomputability. That inconsistency exists both with and without the concept of incomputability. Hence Turing's argument does not prove the incomputability of the halting problem. He does not object that the input to the halting machine is unique. He does notice or emphasize that that there is some logic inconsistency about that input (which is sort of the halting machine itself).

On the other hand, apparently, regardless of how you have been reasoning, you are trying to show that there is actually no (real or unresolvable) inconsistency in the specification or the behavior of the halting machine. That is very different from Eric's view. **That is exactly the opposite of Eric's clear belief in the (immediate) inconsistency of the halting machine.** Neither could I see the possibility that Eric's argument and your argument is just two different sides of the same coin (that is, the same perspective or the same argument but described differently).

To readers with more formal logic and computer science background, please excuse me that I am not writing in rigorous formal logic. That would not be necessarily more helpful here, anyway. Indeed, if needed, we can just read Eric's wonderful papers.
> 8 votes

---
Tags: computability, halting-problem, mathematical-foundations
---


# Question
Title: Dijkstra Partitioning Algorithm : Special Case
I have been exploring Dikstra partitioning Algorithm. Below are my given:

```
R = Red
W = White
B = Blue

```

I have this unpartitioned array.

```
| W | B  | R |  W  | R  | W | B |  W  |  W |

```

I want it partition in the format: R, W, B consecutively.

```
| R  |  ?  | W  |  B |
0     i     j    k    n

```

Given:

```
 i = 0
 j = n
 k = n
 n = number of elements

```

Below is my algorithm:

```
 while  (i < j)
 {
     case a[i]:
         R : i++;
         W : j--; swap(a[i], a[j]);
         B : j--; k--; swap(a[i], a[k]); swap(a[i], a[j]);
     end case
 }
 //Done Sorting

```

The output should be like this:

```
 |  R  | R  | W  |  W  |  W  |   W  |  W  |  B  |  B |

```

My question is:

1. Can I reduce the number of swaps? If yes, how?
2. Is the algorithm applicable if there are 4 colors to be partitioned?

Thank you. I really need to understand this concept.

# Answer
> 2 votes
Short answer: No. Note that the worst case of this algorithm is when all elements are blue. In such case, you will need $2\cdot n$ swaps in the worst case. When all elements are blue the number of swaps can be zero.

Optimal algorithm:

I think that the following algorithm is the optimal one:

1. Count the number of Reds, Blues and Whites in the array.
2. Denote $n\_{color}$ the number of elements of $color\in \\{ Blue,Red,White \\}$ in the array.
3. Define $i=0, j=n\_{Red}-1$, and $k=n\_{Blue}+n\_{Red}-1$, i.e., counters over the Reds,Blues and Whites arrays in the corresponding , respectively.
4. Increase i,j,k until either the counter is lager than the size of the corresponding array (i.e., $i=n\_{Red},j=n\_{Blue}+n\_{Red}$ and $k=n$), or that the corresponding element is not in the appropriate color (i.e., $a\[i\]$ is not red, $a\[j\]$ is not blue, $a\[k\]$ is not white). The algorithm stops iff when all counters are lager than the size of the corresponding array $i=n\_{Red},j=n\_{Blue}+n\_{Red}$ and $k=n$.

Now, if $a\[i\]$ is blue and $a\[j\]$ is red, then we can swap between them, and increase the counters of $i$ and $j$ until possible. The same can be said if $a\[i\]$ is white and $a\[k\]$ is red or $a\[j\]$ is white and $a\[k\]$ is blue. Thus if there are two elements of $(a\[i\],a\[j\],a\[k\])$ with the same color- we can swap the corresponding pair, and increase the corresponding counters.

In the edge case where $a\[i\]$ is blue and $a\[j\]$ is white, and $a\[k\]$ is red, we must do $2$ swaps. The same happens if $a\[i\]$ is white and $a\[j\]$ is red, and $a\[k\]$ is blue.

The number of swaps in such algorithm is at most $\frac{2}{3}n$, in case the array begins with $\frac{n}{3}$ blues, continues with $\frac{n}{3}$ whites, and ends with $\frac{n}{3}$ reds.

I think that this is the optimal algorithm, I will try to show later the correctness.

2.Is the algorithm applicable if there are 4 colors to be partitioned? I think it does. In the worst case, you can use counting sort, which runs at $O(nk)$ given $n$ elements and $k$ colores.

---
Tags: algorithms, algorithm-analysis, sorting, partitions
---


# Question
Title: Path in a vertex-weighted undirected graph
Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$.

Does there exists a path in $G$ with total weight $W$ that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

# Answer
> 4 votes
So this is a simple solution to this question. Given an instance of Hamiltonian path problem $G(V, E)$. Just set $w$ and $\mathrm{max-visit}$ to be equal to $1$ everywhere and $W=|V|$. A path in $G$ satisfies the requirements in our problem now corresponds to a Hamiltonian path in the original instance, and vice versa.

---
Tags: graphs, np-complete, reductions, weighted-graphs
---


# Question
Title: Path in an edge-weighted undirected graph
Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary.

Does there exist a path in $G$ with overall product of edge weights equal $W$ and that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

# Answer
As D.W., point out in his comment. This problem is not $NP$-hard unless $NP\subseteq QuasiPoly$. The idea is that any such path must not contain more than $\log(n)$ edge of weight \> 1.

Enumerate every such sequences of edges (with edge-weight \> 1). There are ${O(n^2)}^{\log(n)}$ sequences like that.

For each sequence, to turn it into a solution, we need to fill in the "gap" with weight-1 edges.

This one is a little bit different from his comment. A **flow** is not the exact idea. What we need is the $k$ vertex-disjoint paths from classical work of **Robertson** and **Seymour**.

If the above description is not satisfying enough. Just note that we may split each vertex $v$ into a $\text{max-visit}(v)$-clique, and remember to connect each pair of cliques according to the original edges.
> 2 votes

---
Tags: graphs, np-complete, weighted-graphs
---


title: Time complexity of base conversion

text:
# Question
Title: Time complexity of base conversion
**Why can't arbitrary base conversion be as fast as converting from base $b$ to base $b^k$ ?**

Seems to be a big time complexity difference! I am also interested in *reading material about it*.

---

**Old. Original detailed question**

Conversion between **power-2-radix** can be done faster than between **non-power-of-2 radix**, they can be even done in *parallel*, as every digit (or some groups of them) can be decoded *independently* of the rest.

For example the binary number `00101001` can be converted to hexadecimal `0x29` nibble by nibble (`0010` and `1001`), and vice versa (i.e. every hex-digit can be parsed to 4 bits independently of the rest), but doing that conversion from decimal (or any other non-power-of-2 radix) to binary, it's not so easy because digits affects each other!.

I've seen time complexity of maths operations in wikipedia, and there is also a related question in stackoverflow saying time complexity of conversions of arbitrary digit length to be $\mathcal{O}(M(n) log(n))$

I'm not interested in a "general time complexity bounds for any base conversion" but I would like to know more about these big differences in time complexity between "power-of-2 conversions" vs "any other base conversions".

I think there is a general fact about conversions that can be done faster if they are done between numbers where its bases are power among themselves, not only for 2, but the same to a base 10 to base 100.

Is there any known proof or materials around this ?

# Answer
Conversion from base $b^k$ to base $b^l$ can be done by reading the original number in chunks of length $\mathrm{lcm}(k,l)/k$, and converting each such chunk into $\mathrm{lcm}(l,k)/l$ digits in the new base. For *fixed* $b,k,l$, this is linear time.

There is a non-trivial algorithm for base conversion in time $O(M(n)\log n)$, where $M(n)$ is the time it takes to multiply two $n$-bit numbers, $n$ is the length of the number (in digits), and the two bases are fixed. See for example page 14 of these notes by Brent.

The question you are asking is, for fixed $b\_1,b\_2$ which cannot be written in the form $b^k,b^l$, whether there exists a linear time algorithm for converting from base $b\_1$ to base $b\_2$. One possible approach to show that this is impossible might be by reducing multiplication (or any other equivalent operation, such as division) to base conversion *for some fixed constant bases* -- but it's not clear if it is in fact possible to build such a reduction or not. I don't believe the question has been asked in the literature.
> 6 votes

# Answer
You seem to have asked 2 questions:

1. Why is it that for some pairs of bases, there is no linear time algorithm for converting from one base in that pair to the other?
2. How to you compare converting between any two bases to converting to and from base 2?

I'm afraid I don't know how to answer the first question because I don't know how to prove that for some pairs of bases, there is no linear time algorithm for converting from one to the other, but I'm pretty sure that for any two bases that are not a power of the same number, there is no linear time algorithm for converting from one to the other.

However, I will answer the second question because nobody else seems to have. Converting between any two bases is provably no harder than converting between any base and base 2. That's easy to prove because for any two bases, converting from one to the other can be done by converting from one base to base 2 and then from base 2 to the other base. It probably does not go the other way. Converting between one base and another base is probably sometimes easier than converting from some base to base 2. For example, converting from base 3 to base 9 is a linear time problem but converting from base 3 to base 2 probably isn't.
> 2 votes

# Answer
To make a conversion of a natural number

Representation $A$ in base $r\_a$ with $n$ digits $a\_{n-1}a\_{n-2}...a\_0$ , $A=\sum\limits\_{k=0}^{n-1} a\_k{r\_a}^k$

Representation $B$ in base $r\_b$ with $m$ digits $b\_{m-1}b\_{m-2}...b\_0$ , $B=\sum\limits\_{k=0}^{m-1}b\_k{r\_b}^k$

As they are the same number, $A$=$B$ then $A-B=0$

$\sum\limits\_{k=0}^{n-1}a\_k{r\_a}^k - \sum\limits\_{k=0}^{m-1}b\_k{r\_b}^k = 0$

Representations can be forced to be the same length by filling with zeros the shorter. $n=m$, so

---

$\sum\limits\_{k=0}^{n-1}a\_k{r\_a}^k - b\_k{r\_b}^k = 0$

**Equation 1**

$a\_k = b\_k(\frac{r\_b}{r\_a})^k$

---

That's not a method for solving the conversion but complexity of base conversion is related to solving that equation, where either $a\_k$ or $b\_k$ are the unknown variables (depending on what base conversion we are doing).

On the other hand, in the case of power related bases $r\_b={r\_a}^c \implies {r\_b}^k={{r\_a}^c}^k$ so the equation get simpler, taking out ${r\_a}^k$ as common factor

$\sum\limits\_{k=0}^{n-1} (a\_k- b\_k{r\_a}^c){r\_a}^k = 0$

So for it to be zero

---

$a\_k=b\_k{r\_a}^c$

name the constant $Q={r\_a}^c$

**Equation 2**

## $a\_k=b\_k{Q}$

Solving $a\_k$ or $b\_k$ is just a product to, or a division by, a constant factor Q for every k.

So comparing $(1)$ with $(2)$ this second one is clearly simpler.

To speed up $(1)$ there are some techniques by the moment I've found The Horner Method that reduce operations in solving polynomials.

This what I've found by now to answer my own question..
> 0 votes

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


# Question
Title: Best algorithm to make a smooth route through a raw set of GPS-points with some errors?
We're developing a mobile application where one of it's functions is tracking user driving route. The app simply pushes GPS-coordinates to the server, which stores them into a route.

Then we need to display that route gracefully on a map.

There are 2 problems:

1. Too many points to draw it all. I solve this by applying my variation of RDP algorithm
2. GPS coordinates aren't ideal, sometimes there is an error up to 100-200 meters. Which causes loops or zigzags on the map and no one of the polyline simplification algorithms which I know can deal with it.

Do you know a way or an algorithm how to deal with errors in coordinates data to draw smooth routes?

The black is the actual polyline. The red is kind of my desired simplification.

# Answer
Use a Kalman filter. This is a powerful way to smooth the data to eliminate noise, in a way that takes into account the dynamics of how physical objects move.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$
my solution is that $L\in co-RE$ by showing that $\overline{L}\in RE$

TM $M$ on input:$\langle M\_1,M\_2,w\rangle$

1. Build TM $M\_1,M\_2$
2. Simulate $M\_1$ on $x\in\Sigma^\*$, before that check if $x\neq w$
3. If $M\_1$ accepts some $x$, than Simulate $M\_2$ on $x$
4. If $M\_2$ accepts than $M$ accepts. If $M\_2$ reject, that we back at $M\_1$ on the next $x$

$\* $ $M\_1$ and $M\_2$ will run on each $x$ at the most $|x|$ steps.

Is that correct?

Thanks.

# Answer
> 1 votes
No. It is not correct.

For example, suppose that $x=0$, $w=00$, $L(M\_1)\bigcap L(M\_2)=\\{x,w\\}$. If $M\_1(x)$ or $M\_2(x)$ takes more than $|x|=1$ steps to answer "yes", then your proposed algorithm will failed.

---
Tags: turing-machines
---


# Question
Title: Understanding reductions for NP-completeness
Let's I have to make the following reduction:

$$\text{CLIQUE}\le\_p \text{VERTEX-COVER}$$

The technique of building the reduction is -

1. Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in polynomial time.
2. Building a new graph, in which I say that if a $\text{VERTEX-COVER}$ exists of size $k$, then in the original graph, a $\text{CLIQUE}$ of size $k$ exists?

I just want to understand the technique of these proofs.

# Answer
> 0 votes
> 1. Assume you can find a $vertex-cover$ of size $k$, in polynomial time.

Actually, this step is not correct. When we show that $A \le\_p B$, where $A$ and $B$ are languages (also known as decision problems), we do not assume that either $A$ or $B$ can be solved in polynomial time. What we do is "reduce" problem $A$ to problem $B$: that means that we take an instance of problem A, and return an instance of problem $B$. The part that has to be polynomial time is this "reduce" function.

In other words, it's possible that $A$ and $B$ are both really "hard" -- they can't be done in polynomial time, or maybe they aren't even decidable. But what we show is that the *reduction* is polynomial time.

So what is this "reduction" that we have to show is polynomial time? You mentioned part of it:

> 2. Building a new graph, in which I say that if a $vertex-cover$ exists of size $k$, then in the original graph, a $clique$ of size $k$ exists?

That's half. You also have to show that if a vertex-cover *doesn't* exist of size $k$, then in the original graph, a clique of size $k$ *doesn't* exist.

**To summarize:** when doing a reduction from $A$ to $B$ ($A \le\_p B$), here are the three things you should show:

1. If the output of the reduction is in $B$, then the input is in $A$. (For example, if a vertex-cover exists in the output, then in the original graph, a clique exists.)
2. If the output of the reduction is *not* in $B$, then the input is *not* in $A$. (For example, if a vertex-cover does not exist in the output, then in the original graph, a clique does not exist).
3. The whole reduction -- which takes instances of problem $A$ to instances of problem $B$ -- runs in polynomial time.

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


# Question
Title: Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?
So in this math exchange question I asked, it was proven that for $n\>2$ dimensions, you can *always* find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you pre-defined. What I wanted to know is if there is a polytime algorithm (polynomial in $k$) for determining this curve.

If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?

# Answer
> 3 votes
> What I wanted to know is if there is a polytime algorithm (on the order of k) for determining this curve. If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?

Yes, this is possible. The equation for the curve will be nonlinear. (It is not possible to have a *linear* equation which describes the curve, because there exists sets of $k$ points (as long as $k \ge 4$) where no linear separator exists.)

Let the $k$ points in $n \ge 3$ dimensions be $\vec{x}\_1, \vec{x}\_2, \ldots, \vec{x}\_k \in \mathbb{R}^n$. For each point $\vec{x}\_i$, suppose the set it is in is given by a *label* $\ell\_i$, which is either $+1$ or $-1$. So the points are divided into those labeled $+1$ and those labeled $-1$.

Then we define the following function: \begin{align\*} f: \mathbb{R}^n &\to \mathbb{R} \\ f(\vec{x}) &:= \sum\_{i=1}^k \ell\_i \cdot \exp \left(- \frac{\log k}{d\_{min}} \\|\vec{x} - \vec{x}\_i\\| \right), \end{align\*} where $d\_{min}$ is the *minimum distance between a pair of points*, over all pairs of $2$ out of the $k$ points. That is, we take the minimum over $\\|\vec{x}\_1 - \vec{x}\_2\\|$, $\\|\vec{x}\_1 - \vec{x}\_3\\|$, etc. I am using $\\| \cdot \\|$ to denote the norm, that is, the length of vectors in $\mathbb{R}^n$.

Now I claim that your desired curve is given by the set $$ \big\\{ x \\;\mid\\; f(\vec{x}) = 0 \big\\}. $$

To justify this, we should show that $f$ separates the points labeled $+1$ from those labeled $-1$. So we first calculate $f(\vec{x}\_i)$. We get \begin{align\*} f(\vec{x}\_i) = \underbrace{\ell\_i \cdot \exp \left(- \frac{\log k}{d\_{min}} \\|\vec{x} - \vec{x}\_i\\| \right)}\_{= \ell\_i \cdot e^0 = \ell\_i} \+ \underbrace{\sum\_{j \ne i} \ell\_j \cdot \exp \left(- \frac{\log k}{d\_{min}} \\|\vec{x} - \vec{x}\_j\\| \right)}\_{\text{small}} \end{align\*} Now the first term is just $\ell\_i$, which is $1$ or $-1$, and the second term is small enough that it doesn't change the sign. Specifically, we can bound the second term (in absolute value) by $$ (k-1) \exp \left( -\frac{\log k}{d\_{min}} \cdot d\_{min}\right) = (k-1) \cdot \frac{1}{k} \< 1. $$

So $f$ is positive on points labeled $+1$ and negative on points labeled $-1$. Also, $f$ is continuous on the entire $\mathbb{R}^n$. So, the points $\vec{x}$ where $f(\vec{x}) = 0$ *must* be a separating boundary curve between the positively and the negatively labeled points. $\square$

---

Finally, some notes:

* **Definition of a curve:** In the question, it is not defined what a curve is, here; I took it to be the zero set of a continuous function, but you might want something more specific. This curve is actually a $(k-1)$-dimensional surface, but it might not be smooth at the points $\vec{x}\_i$. A modification could be made that would smooth out these points by replacing $\\|\vec{x} - \vec{x}\_i\\|$ with $\\|\vec{x} - \vec{x}\_i\\|^2$ and $d\_{min}$ with $d\_{min}^2$.
* **Polynomial time:** Returning the function $f$ is polynomial time: the only hard part is to compute the quantity $d\_{min}$, which requires computing the distance between every pair of points in the set. So this is $O(k^2)$ time. The rest is just $O(k)$ time. Note that this requires that we have a model of computation in mind where arithmetic can be done on real-number values (it won't be a traditional Turing machine).

# Answer
> 2 votes
I think that the proof in your provided link describes an algorithm that runs at $O(k^2\cdot n)$ time.

---
Tags: algorithms, polynomial-time, classification
---


title: Preserving a propositional formula

text:
# Question
Title: Preserving a propositional formula
I know I must be getting stuck on notation. However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf. They define what preserving a propositional formula means.

So, I'm trying to understand a basic example. Take X = A or (Not B) or (Not C) as an example Horn Clause. Define the assignments f1 and f2 by f1(A) = f1(B) = f1(C) = true and f2(A) = f2(B) = f2(C) = false. Both f1 and f2 satisfy X.

What does it mean to say AND preserves X with respect f1 and f2?

# Answer
> 2 votes
In your example the assignment $f\_1\wedge f\_2$ is $(f\_1\wedge f\_2)(A)=f\_1(A)\wedge f\_2(A)=\text{True} \land \text{False} = \text{False}$. similarly: $(f\_1\wedge f\_2)(B)=(f\_1\wedge f\_2)(C)=\text{False}$ so actually $f\_1\wedge f\_2 \equiv f\_2$.

As they define, AND is preserving $X$ if for every two assignments $f\_1, f\_2$ that satisfy $X$, the assignment $f\_1 \wedge f\_2$ (defined by $(f\_1\wedge f\_2)(v)=f\_1(v)\wedge f\_2(v)$) also satisfies $X$.

---
Tags: satisfiability, propositional-logic
---