# Question
Title: Efficiently shuffling items in $N$ buckets using $O(N)$ space
I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows:

* We have $N$ buckets, $B\_1$ through $B\_N$. Each bucket $B\_i$ maps to a unique **item** $a\_i$ and a **count** $k\_i$. Altogether, the collection holds $T=\sum\_1^N{k\_i}$ items. This is a more compact representation of a vector of $T$ items where each $a\_i$ is repeated $k\_i$ times.
* We want to output a shuffled list of the $T$ items, all permutations equally probable, using only $O(N)$ space and minimal time complexity. (Assume a perfect RNG.)
* $N$ is fairly large and $T$ is much larger; 5,000 and 5,000,000 in the problem that led me to this investigation.

(EDIT: further research instigated by @YuvalFilmus’s comment shows that this is equivalent to **weighted sampling without replacement**, a search term that leads to quite a lot of research.)

Now clearly the time complexity is at least $O(T)$ since we have to output that many items. But how closely can we approach that lower bound? Some algorithms:

* Algorithm 1: Expand the buckets into a vector of $T$ items and use Fisher-Yates. This uses $O(T)$ time, but also $O(T)$ space, which we want to avoid.
* Algorithm 2: For each step, choose a random number $R$ from $\[0,T-1\]$. Traverse the buckets, subtracting $k\_i$ from $R$ each time, until $R\<0$; then output $i$ and decrement $k\_i$ and $T$. This seems correct and does not use extra space. However, it takes $O(NT)$ time, which is quite slow when $N$ is large.
* Algorithm 3: Convert the vector of buckets into a balanced binary tree with buckets at the leaf nodes; the depth should be close to $\log\_2{N}$. Each node stores the total count of all the buckets under it. To shuffle, choose a random number $R$ from $\[0,T-1\]$, then descend into the tree accordingly, decrementing each node count as we go; when descending to the right, reduce $R$ by the left count. When we reach a leaf node, output its value. It uses $O(N)$ space and $O(T\log{N})$ time.
* Algorithm 3a: Same as Algorithm 3, but with a Huffman tree; this should be faster if the $k\_i$ values vary widely, since the most often visited nodes will be closer to the root. The performance is more difficult to assess, but looks like it would vary from $O(T)$ to $O(T\log{N})$ depending on the distribution of $k\_i$.

Algorithm 3 is the best I’ve come up with. Here are some illustrations to clarify it:

Does anyone know of a more efficient algorithm? I tried searching with various terms but could not find any discussion of this particular task.

# Answer
Step 1. Store the buckets cumulatively. E.g. instead of storing $\[3, 5, 2, 2\]$ you store $\[3, 8, 10, 12\]$. This allows you to find using binary search in $\log n$ time what bucket the $k$th (out of $T$) item belongs to (and by extension which $a\_i$ to output).

Step 2. Use a memory-less permutation of the range $\[1, T\]$. I personally like Sometimes-Recurse Shuffle. A memory-less permutation can give you $\pi(k)$ directly for arbitrary $k$ in $\log T$ time. Some example code I have written a couple years back show how simple it is (with toy PRF implementation - replace that): https://gist.github.com/orlp/33535eefce782a59e185e4a971cda1a3.

Step 3. To actually shuffle simply enumerate $k = 1, 2, \dots$, compute $\pi(k)$ using the memory-less permutation, and find which bucket $\pi(k)$ belongs to output the proper $a\_i$. Total time complexity is $\log(T)$ per item, or $T \log(T)$ for the whole permutation.

The advantage is that you don't have to compute the whole permutation, you can also just directly compute the $k$th element in the permutation.
> 2 votes

# Answer
Here's a pretty simple algorithm for weighted random selection without replacement, which is O(N) space and stochastic O(1) time per element selected (i.e. O(T) time for a complete permutation).

It's a combination of two common algorithms for weighted random selection: the rejection method (I can't find a reference for this one; it's as old as the hills although it frequently gets rediscovered, as for example the frequently-cited Lipowski & Lipowska 2011) and the alias method (Walker 1977; Kronmal & Peterson 1979). A good discussion of both of these methods (and many more) can be found in Chapter 3 of *Non-Uniform Random Variate Generation* (Luc Devroye, 1986) which is freely-downloadable through that link. (And kudos to Devroye for his rant about academic ~~bloodsuckers~~publishers. I can't find any unpaywalled copies of the 40-year-old papers cited above, so Devroye is the best reference I have. The algorithms are described below.)

The basic problem with both of these methods is that they require O(N) setup time, and the fact that the weight distribution varies after each selection is extracted would require reprocessing at every step, resulting in O(NT) time. In addition, the rejection method only provides O(1) selection time over a restricted range of possible weight distributions \[Note 1\], and we cannot guarantee that requirement for all distributions which might occur during a permutation. However, putting the two algorithms together solves both problems:

1) We use the alias method (slightly modified) to guarantee that the rejection method's distribution requirement is honoured; and

2) Because of the flexibility provided by the rejection method, we do the O(N) auxiliary processing less then once every N selections, so that it has an O(1) amortised contribution to the cost of doing a selection.

### The rejection method

The rejection method is incredibly simple. We start with some weight $\omega\_\alpha$ which is at least as great as any weight in the distribution. (That's the required precomputation; clearly, we could compute $\omega\_\alpha = max\_{i=1}^N(\omega\_i)$

At each step:

* Repeatedly generate two random variates $u, v$ over the uniform ranges $\[1, N\]$ and $\[1, \omega\_\alpha\]$ respectively \[Note 2\] until $v \< \omega\_u$, and then return $u$.

In effect, this corresponds to firing a dart at an $N \times \omega\_\alpha$ grid, in which the bottom $\omega\_i$ squares in column $i$ are coloured. If the dart falls on a coloured square, we return the number of that column; otherwise, we try again. It should be clear both that the values returned obey the desired probability distribution, and that the probability of returning a value on any given iteration is $\sum \omega\_i \over { N \omega\_\alpha }$.

If we knew that ${\omega\_\alpha \over \omega\_{mean}} \lt c$ for some constant $c$, then the expected number of iterations would be $c$. (Or, to put it another way, the expected number of rejections would be $c-1$.)

But, of course, without doing some more work we cannot make this assertion. However, it's worth noting that if $\omega\_{mean}$ is not too small, then removing an element has little impact on the ratio. Consequently, we can avoid recomputing $\omega\_\alpha$ on every step. But that's getting a bit ahead of ourselves.

### The alias method

Suppose we take the chessboard described above and attempt to level it out by filling in small columns using coloured squares from the big columns. It turns out that we can always find an arrangement in which there are only two colours in any column, and in which all of the columns are the same height (within one square, since there is no guarantee that the total weight evenly divides N). We call the alternative value for each column it's *alias* ($a\_i$) and we store two weights for each column: $\omega^0\_i$, the number of squares corresponding to the value at index $i$, and $\omega^1\_i$, the total number of coloured squares in that column. \[Note 3\]

Evidently, we can choose $\omega\_\alpha = \lceil T / N \rceil$ and then run a slightly modified version of the rejection algorithm. The only difference is that the iteration is changed to:

* Repeatedly generate two random variates $u, v$ over the uniform ranges $\[1, N\]$ and $\[1, \omega\_\alpha\]$ respectively \[Note 2\] until $v \< \omega^1\_u$, and then select

$$\begin{cases} u, & \text{if } v \lt \omega^0\_u \\ a\_u, & \text{otherwise} \end{cases} $$

The alias table (in this version) requires storing $3N$ numbers, all of them in the same range as the problem's inputs. That means that when we have reduced $T$ to $3N$, we can switch to an alternative algorithm without using any more space: collect all the remaining values in a single array of size $3N$, shuffle it randomly, and then generate its elements in sequence. That lets us assume that $\omega\_\alpha$ is at least 3, which is convenient because it lets us limit the expected number of rejections without recomputing the alias table too often.

As noted above, if we recompute the alias table no more often than every $N$ steps, we will contribute amortised O(1) to the cost of a single step. So a simple approach is to recompute the alias table every time $T$ is an exact multiple of $N$, until $T = 3N$. In that case, it will always be the case that

$${\omega\_\alpha \over \omega\_{mean}} \lt { 4 \over 3}$$

so the expected number of rejections is (much) less than $1/3$.

Indeed, we might be prepared to live with a larger number of rejections. If, for example, we wanted to limit the expected number of rejections to 1, it would suffice to recompute the alias table every time $T$ fell to half its previous value (again, stopping at $T = 3N$), which would mean that we would do $lg N$ recomputations. However, experimentation indicates that the cost of recomputing the alias table is so small that this is not worthwhile.

---

### Notes

1. The algorithm is O(1) for any given weight distribution, although the constant can be quite large, but if we do the analysis over all possible distributions which sum to $T$, the worst-case expected time increases without bound as $|T|\rightarrow \infty$. In practice, we will want to limit the size of the constant.
2. In practice, we normally generate a single variate over the range $\[0, N\omega\_\alpha)$ and then extract the two required variates through division and modulo by $N$. I've written this answer using the usual mathematical convention of 1-indexing lists, but clearly the arithmetic will be tidier when implemented using a 0-indexed programming language.
3. In Walker's paper, and indeed in most descriptions of the alias method, it is assumed that the weights are infinite-precision real values, in which case all of the columns will be exactly the same height. Of course, that is not true of any practical implementation; usually, the weights are adjusted very slightly to even out the columns. In the case that the weights are integers, this adjustment is not possible, so the second weight must be stored, although only a single bit is required since each column's total weight is either $\lceil T / N \rceil$ and $\lfloor T / N\rfloor$. We don't even have to store this bit, if we ensure that the short columns are all at the end (which is easy to do); we could just store the number of short columns.

However, here we are going to want to modify the weights dynamically (by subtracting one each time an item is selected) so the column sizes will vary unpredictably as the algorithm proceeds. So we store three values instead of two.
> 0 votes

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


# Question
Title: How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?
$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n\<4$. I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess and demonstrate it by induction? also, it should be computed given both upper and lower bound.

# Answer
> 1 votes
*Summary: $T(n) = \Theta(\alpha^n)$, where $\alpha=\sqrt\[3\]{\frac{9+\sqrt{69}}{18}}+\sqrt\[3\]{\frac{9-\sqrt{69}}{18}}\approx 1.324718$.*

## Find $\alpha$

Let $\alpha$ be the unique positive root of $x^3=x+1$.

We can solve the equation manually by the standard method, letting $x=w+\frac 1{3w}$ and solving $w$. If we trust the online calculators or you can use some software package such as MatLab, Maple, Wolfram Alpha or Python numpy.root, you can find all the exact roots or the approximate roots. In fact, since all we need is a positive root, we could also cheat a bit by just verifying directly the following quantity is a root. $$\alpha=\sqrt\[3\]{\frac{9+\sqrt{69}}{18}}+\sqrt\[3\]{\frac{9-\sqrt{69}}{18}}\approx 1.324718$$

## Reference function $S$

Let $S(n)= S(n-2)+S(n-3)$ and $S(n)=1$ for $n\<4$.

Claim: $\frac{\alpha^n}{3}\<S(n)\<\alpha^n$ for all $n\ge1$.

Proof by mathematical induction on $n$.

* The base case when $1\le n\le3$ is easy since $1\<\alpha$ and $\alpha^3\<3$.
* Since $\alpha^3=\alpha+1$, the induction step is easy. Assume the claim is true when $n\le k-1$ for some $k\ge3$. Then $$S(k)=S(k-2)+S(k-3)\>\frac{\alpha^{k-2}}{3}+\frac{\alpha^{k-3}}3=\frac{\alpha^k}3$$ $$S(k)=S(k-2)+S(k-3)\<\alpha^{k-2}+\alpha^{k-3}=\alpha^k$$

## Last Trick

Claim One: $S(n)\le T(n)$ for all $n\ge1$.

Proof: It is easy to prove by mathematical induction that $T(n)\>0$ for all $n\ge1$. $S(n)\le T(n)$ follows easily by mathematical induction.

Lemma: there exists a constant $c\>0$ such that for all $n\ge c$, $\alpha^{\frac{2n}3} \> 3n^2$.

Proof. This is obvious since any growing exponential function grows faster than any polynomial, a well-known fact that is (almost) proved in this answer. (We can take c=72, for example.)

Claim Two: There exist a constant $d\>0$ such that $T(n)\<d(1-\frac1n)S(n)$ for all $n\ge1$. (That factor $1-\frac1n$ is the "last trick".)

Proof. Let $c\>4$ be a constant as in the lemma. Let $d=1+2\max\_{1\le n\<c}(T(n))\>1$. Let us prove $T(n)\<d(1-\frac1n)S(n)$ by mathematical induction on $n$.

* The base case when $n\<c$. $T(n) \< d/2 \le d(1-\frac1n) \le d(1-\frac1n)S(n)$.
* Suppose the inequality is true for all $n\le k-1$, where $k\ge c$. Then

$$ \begin{aligned} T(k)=& T(k-2) + T(k-3) + 2T(k/3)\\ \lt& d(1-\frac1{k-2})S(k-2) + d(1-\frac1{k-3})S(k-3) + 2d(1-\frac1{\frac k3})\alpha^{\frac k3} \\ \lt&d(1-\frac1{k-2})(S(k-2)+S(k-3)) + 2d\alpha^{\frac k3}\\ =&d(1-\frac1{k-2})S(k) + 2d\alpha^{\frac k3}\\ =&d(1-\frac1{k})S(k) - \frac{2d}{(k-2)k}S(k)+ 2d\alpha^{\frac k3} \\ \lt&d(1-\frac1{k})S(k) - \frac{2d}{(k-2)k}\frac13\alpha^k+ 2d\alpha^{\frac k3} \\ =&d(1-\frac1{k})S(k) - \frac{2d\alpha^{\frac k3}}{3(k-2)k}(\alpha^{\frac {2k}3} - 3(k-2)k)\\ \end{aligned}$$

Since $\alpha^{\frac {2k}3} - 3(k-2)k \gt \alpha^{\frac {2k}3} - 3k^2\gt0$, we obtain $T(k) \lt d(1-\frac1{k})S(k)$.

Claim Three: $T(n)=\Theta(\alpha^n)$

Proof: This follows immediately from the two above claims since $\frac{\alpha^n}{3}\<S(n)\<\alpha^n$ and $d(1-\frac1n)\le d$.

# Answer
> 1 votes
You can notice that $T(n) \< 3T(n-2)$. This gives you the complexity as $O(3^{n/2})$. You can also observe that $T(n) \> 2T(n-3)$. This gives you the complexity as $\Omega(2^{n/3})$. Now, you can at least tell that the complexity is an exponential one.

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


# Question
Title: What if traversal order of two of pre-order, in-order and post-order is same?
Supposing a tree T has the identical:

1. Pre-order traversal and in-order traversal
2. Pre-order traversal and post-order traversal
3. In-order traversal and post-order traversal

How does T look like?

From the previous discussion in SO, I learned that pre- and post-order are same iff. only one node is in the T.

How about the left two conditions?

I suppose that only purely left-skewed tree can make post- and in-order the same, and only right-skewed tree can make pre- and in-order the same.

Am I on the right way?

---

Edit: To avoid being solely a 'yes' or 'no' problem, the actual doubt is that **how to prove this statement**, but I have a idea about the proofs using contradiction. So maybe this problem is a little redundant.

# Answer
A proper proof uses the recursive definitions of the tree-orders. Here is a sketch.

For inorder the recursive definition is: *in(left) - root - in(right)*. For postorder we similarly have: *post(left) - post(right) - root*.

Look at the position of *root* in both orders. If we want this to be the same we need to have there are no nodes in *in(right)* which means the right subtree (at the root) is empty. Same for the root at other levels.
> 3 votes

# Answer
Hendrik is almost right but did not conclude well. Therefore, I am giving a more comprehensive answer.

In the followings, `r` denotes root, `l` denotes left sub-tree, and `r` denotes right sub-tree. Now, let's consider each case separately, starting from the second one.

* **Pre-order is the same as post-order**: In this case `r-pre(l)-pre(r)` should be the same as `post(l)-post(r)-r`. For them to be equal both `r` and `l` should be empty trees (`null`). So the tree should only have one node as follows:

```
                         a
                        / \
                     null null

```
* **Pre-order is the same as In-order**: In this case `r-pre(l)-pre(r)` should be the same as `in(l)-r-in(r)`. For them to be equal we need to get rid of `in(l)` enforcing the left sub-tree to be empty (`null`). However, `in(r)` should be the same as `pre(r)`. Now again we need in-order traversal to be the same as pre-order traversal. ***Although formally an induction proof is required for this case***, intuitively one can observe that the tree should only have right child at every node (not necessarily a one node tree). Here is an example:

```
                         a
                        / \
                     null  b
                          / \
                       null  c
                            / \
                             ...

```
* **In-order is the same as post-order**: This is the same as the previous case but the tree should only have left child at every node.

```
                         a
                        / \
                       b  null
                      / \
                     c  null
                    / \
                   ...

```
> 3 votes

---
Tags: binary-trees
---


title: Interval extensionality?

text:
# Question
Title: Interval extensionality?
For example, in the proof of lemma 6.4.1 in the HoTT book, a function inductively defined over a function is simply applied on paths `loop` and `refl`, and then a path between `loop` and `refl` is used (presumably by congruence via `f`) to construct a path between `f loop` and `f refl`:

> Suppose that `loop = refl base`. \[...\] with `x : A` and `p : x = x`, there is a function `f : S1 → A` defined by `f(base) :≡ x` and `f(loop) := p`, we have
>
> ```
> p = f(loop) = f(refl base) = refl x.
>
> ```

But in a cubical setting, things are not so clear-cut. `f(loop)` is not well-typed, only `f(loop i)` is, for some `i : I`. But then that above proof becomes

```
p = <i> f (loop i) = <i> f (refl base i) = refl x

```

but doesn't that need some kind of "interval extensionality" in the middle step? What exactly is the justification of the middle step in cubical type theory? I can see how to prove `∀ i → f (loop i) = f (refl base i)`, but how does one "lift" that to `<i> f (loop i) = <i> f (refl base i)`?

# Answer
Originally I was going to give an assurance that something like your extensionality principle must hold, but I decided to puzzle out enough cubical Agda to actually demonstrate the proof.

However, I should say that your `all : ∀ i → f (loop i) = f (refl base i)` is actually a digression. This is equivalent to a square with *arbitrary* sides, which looks like this:

$$ \require{AMScd} \begin{CD} x @\>all(0)\>\> x \\ @VpVV \Rightarrow @VVreflV \\ x @\>\>all(1)\> x \end{CD} $$

but something with type `p ≡ refl` is actually more uniform than that, because if `e` has that type, then `e i : x ≡ x` *regardless of* `i`, which is more uniform than the above square (where `e i : all i0 i ≡ all i1 i`), and is equivalent to a square of the form:

$$ \begin{CD} x @\>refl\>\> x \\ @VpVV \Rightarrow @VVreflV \\ x @\>\>refl\> x \end{CD} $$

*But*, if we have `loop ≡ refl`, we already have this sort of square, and applying `f` point-wise produces a new square of this type. So, the following code is accepted:

```
module Path
    (S1 Z : Set)
    (base : S1)
    (loop : base ≡ base)
    (f : S1 → Z)
    (x : Z)

    (sq : loop ≡ refl)
  where
  rfl : base ≡ base
  rfl = refl

  z : Z
  z = f base

  p : z ≡ z
  p i = f (loop i)

  zrfl : z ≡ z
  zrfl = refl

  hsq : p ≡ zrfl
  hsq j i = f (sq j i)

```

So, the bit in the HoTT book is just a consequence of the composition of 'functions'.

The more arbitrary square can be expressed using the `PathP` type, which is also written `_[_≡_]` in cubical Agda, and the proof of equivalence to the ∀ type is:

```
module Square
    (A : Set)
    (x y : A)
    (e₁ e₂ : x ≡ y)
    (lines : ∀ i → e₁ i ≡ e₂ i)
  where
  f₀ : x ≡ x
  f₀ = lines i0

  f₁ : y ≡ y
  f₁ = lines i1

  square : (λ i → e₁ i ≡ e₂ i) [ f₀ ≡ f₁ ]
  square i j = lines i j

```

If you want to fool around with cubical Agda yourself to try this out interactively, I've been using a recent Agda from the development branch with `{-# OPTIONS --cubical #-}`, along with this library.
> 2 votes

---
Tags: homotopy-type-theory
---


# Question
Title: Generate Evenly Distributed Pattern Based on Weights
I have an array of items $A = \\{A\_i\\}, i \in I $ with integer weights $W\_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements predictable manner.

For example: an array of 3 elements: $A\_1 = 1, A\_2 = 2, A\_3 = 3$ and weights: $W\_1 = 1, W\_2 = 2, W\_3 = 2$. This means that pattern will consist of 5 repeating elements. One example of this pattern: $1, 2, 3, 2, 3, 1, 2, 3, 2, 3, 1$ (each iteration of 5 elements has exactly one 1, two 2's and two 3's).

What I need is the name of this problem to search for suitable algorithms. Thank you!

# Answer
The name of this problem is **weighted sampling without replacement**. One can search the web or stackoverflow. Not much result on this site yet.
> 1 votes

# Answer
Normalize $W$ by calculating the greatest common divisor of $W$ and dividing every element by it.

Then just repeatedly iterate over $W$ in order, and if $W\_i \> 0$ subtract $1$ from it and output $A\_i$. You stop when all $W\_i = 0$.

If $1, 2, 2, 3, 3, 1, 2, 2, 3, 3, \dots $ in your example is also fine then just output $W\_i$ copies of $A\_i$ after normalization.
> 0 votes

---
Tags: arrays
---


title: Sum of zero nim sum series

text:
# Question
Title: Sum of zero nim sum series
The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum\_{\substack{x\_0 ⊕x\_1⊕\cdots⊕x\_k=0\\x\_i≥0,\ 0≤i≤k\\\sum\limits\_{i=0}^kx\_i≤n-2k}}\binom{n-k-\sum\limits\_{i=0}^kx\_i}k$$ in $O(nk·\log n)$ time, where $⊕$ is exclusive or.

Let $\sum\_{i=0}^{k}x\_i=S$. The straightforward method is enumerating $S$ from $0$ to $n-2k$, and using dynamic programming to count nonnegative solutions to $\begin{cases}&x\_0 ⊕x\_1⊕\cdots⊕x\_k=0 \\\&\sum\_{i=0}^{k}x\_i=S \end{cases}$ (this is the number of winning positions for the first player of a Nim with $k$ piles and a total of $S$ stones, allowing empty piles). But it runs in $O(n^3 k)$ which is too large.

I think there may be some other dynamic programming technique to solve it, but cannot work out that. Any thoughts are welcome.

# Answer
I finally figure out an answer. This paper "Nim Fractals" by Tanya Khovanova and Joshua Xiong gives a formula to count the solutions to $$\begin{cases} x\_0 \oplus \cdots \oplus x\_k =0 \\\sum\_{i=0}^{k}x\_i=S\end{cases}$$ in $O(kS)$. Denote the number as $f(k,S)$. We may utilize $f$ to see that the problem reduces to $\sum\_{S=0}^{n-2k}\binom{n-k-S}{k}f(k,S)$. The overall complexity is $O(nk\cdot log(n))$.
> 0 votes

---
Tags: algorithms, dynamic-programming, combinatorics
---


title: Why is this NP complete?

text:
# Question
Title: Why is this NP complete?
I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image:

Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $\neq$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?

# Answer
The algorithm you described isn't polynomial time because it has to consider every possible *subset* of customers (they are $2^m$ of these).

### Solution

This problem is NP-hard because the vertex cover problem can be reduced to it.

https://en.wikipedia.org/wiki/Vertex\_cover#Computational\_problem

HINT: To do the reduction, consider how you would model $A$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.
> 1 votes

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


# Question
Title: Is the longest Hamiltonian cycle NP-complete?
As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I'm confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I'm looking at really is the longest?

Any help would be appreciated!

# Answer
> 4 votes
Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the *decision version* of that problem.

Here, the decision version is:

> Does the weighted graph $G$ have a Hamiltonian path with total weight at least $x$?

For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least $x$. So, the decision version is in NP.

---

To understand why we look at the decision version, first note that NP is a class of decision problems, so only a decision problem can be NP-complete. (although we can construct an analogue of NP for optimisation problems, as in this answer). Solving the optimisation version also solves the decision version, so the optimisation version is at least as hard as the decision version. Since the theory gets easier when working with decision problems, focusing on the decision version is often helpful.

# Answer
> 2 votes
Longest Hamiltonian Cycle probably isn't known to be in **NP**. We can certainly check in deterministic polynomial time if proposed solution is a Hamiltonian Cycle but, as you say, it doesn't seem possible to check that it's the longest one.

We usually consider the decision version of this kind of maximization problem to be, "Given an instance $X$ and a target $t$, is there a solution with value at least $t$?" So, for Longest Hamiltonian Cycle, we're given a graph $G$ and a number $t$ and we're asked if there's a Hamiltonian cycle of length at least $t$.

Clearly, Hamiltonian Cycle for unweighted graphs is reducible to this: set all the weights to $1$ and ask if there's a Hamiltonian cycle of length at least $1$ (or $n$, if you prefer).

Longest Hamiltonian Cycle is also reducible to it, though using Turing reductions rather than the many-one reductions we use for **NP**-completeness. We can decide LHC by binary search. Assuming all the edge weights are non-negative, we know that the longest Hamiltonian cycle must have length at least zero, and that it can't be longer than $M$, the sum of the longest edge out of each vertex. We can do binary search on the interval $\[0,M\]$ with $\log M$ calls to a subroutine that decides the "LHC at least $t$?" problem, and $M$ can't be more than exponential in the length of the input, so this reduction runs in polynomial time.

---
Tags: np-complete, np, hamiltonian-path
---


# Question
Title: Big O understanding given different input sizes
I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 algorithms take $a$, $b$ and $c$ seconds for the worst, average and best cases given an input of size $n$. What could be the actual time of these 3 algorithms given an input of size $2n$? Based on my understanding it should be:

* $O(n)$: $2a$, $2b$, and $2c$.
* $O(n^2)$: $a^2$, $b^2$, and $c^2$.
* $O(n \log n)$: $a \log a$, $b \log b$, and $c \log c$.

My questions are:

* Is this correct?
* In case not, why?
* In case this is correct, would the same hold for $\Theta$ and $\Omega$?

# Answer
> 1 votes
No, this isn't correct, for a number of reasons.

1. $O(\cdot)$ only gives upper bounds. Being told that $f(n)=O(n\log n)$ doesn't exclude the possibility that $f(n)=n$, $f(n)=1$, etc.
2. The bounds only apply to sufficiently large $n$. Perhaps your measurements were for values of $n$ that are too small to exhibit the asymptotic behaviour.
3. Even if $n$ was large enough, consider the algorithm "If my input has odd length, return immediately; otherwise, perform some calculation that takes exactly $n^2$ steps." This has running time $O(n^2)$, so you'd expect an input twice as big to take four times as long. But an odd-length input will take about $n$ steps, whereas $2n$ is even, so an input of that length would take time at least $(2n)^2$, which is much more than four times as much.
4. The actual running time of the code on an actual computer will depend on all kinds of factors that aren't included in the theoretical analysis. You could be careful to exclude things such as interruptions by other processes, but consider something like disc access. Suppose that your input of size $n$ takes up a quarter of a disc block. Most of the running time of your algorithm might be waiting for that one block to be transferred; the input of length $2n$ will also fit in one block, so you do the same amount of disc I/O and doubling the input takes only a small fraction longer to run. On the other hand, if your length-$n$ input is a whole block, then reading two blocks will take twice the time. Except that the OS will probably cache the second block for you, so probably it won't. Similar effects apply to memory accesses and their interaction with the cache.
5. Your arithmetic is off. Consider the three functions $f(n)=n$, $g(n)=n^2$ and $h(n)=n\log\_2 n$. Then $$f(2n)=2n=2f(n)\\ g(2n)=(2n)^2=4n^2=4g(n)\\ h(2n)=2n\log\_2 2n = 2n(\log\_2 n+\log\_2 2) = 2h(n)+2n\\,.$$

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, landau-notation
---


# Question
Title: Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww
Today I did a test in my class, the trace was:

> *Prove that the language $L =\\{\langle M\rangle\mid \forall w \in \\{0,1\\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \\}$, is undecidable with a reduction from $A\_{\mathrm{TM}}$.<br>Hint: You can suppose that $w\in \\{0,1\\}^\*$*

I answered:

> Suppose that $L$ is decidable. Therefore, there is a TM $R$ such that $L(R)= L$, so we can construct a new TM $S$ that decides $A\_{\mathrm{TM}}$.
> First, construct $N$ as follows:
> $\\\$
> "On input $x$:
>
> * if $x$ is of the form $ww$, accept
> * otherwise, run $M$ on $w$ and do what $M$ does.
>
> Now we can construct $S$ as follows:
>
> * Construct $N$ as above.
> * Run $R$ on $N$; if $R$ accepts, accept; otherwise, reject.

Now I know this isn't correct, but I don't why. More generally, how to recognize a language of a reduction? For example, in my reduction, $S\text{ accepts } w \iff \text{the language of } N\text{ is ?} \iff \langle M,w\rangle \in A\_{\mathrm{TM}} $
I think I'm missing something about reductions but I don't know what.

# Answer
> 1 votes
First of all, assume the TM $S$ receives a (correctly encoded) instance $\langle M, w \rangle$ of $A\_{\text{TM}}$. $N = N\_{M,w}$ must be constructed in terms of $M$ and $w$, that is, its description depends on the problem instance $\langle M, w \rangle$. (It is sloppy to just describe $N$ without having fixed this instance first.)

Your overall proof structure is correct, only you made a couple of mistakes in the constructions of $N = N\_{M,w}$ and $S$. Instead you should have for $N$:

> On input $x$:
>
> * If $x$ is of the form $w'w'$ for some $w' \in \\{0,1\\}^\ast$, reject;
> * Otherwise, simulate $M$ on input $w$ and do what $M$ does.

Why this? Consider the following: $$\begin{align\*} \langle N \rangle \in L &\iff \forall w' \in \\{0,1\\}^\ast: (w' \in L(N) \implies w'w' \in L(N)) \\ &\iff \forall w' \in \\{0,1\\}^\ast: w' \not\in L(N) \lor w'w' \in L(N) \\ &\iff \forall w' \in \\{0,1\\}^\ast: w' \not\in L(N) \\ &\iff \not \exists w' \in \\{0,1\\}^\ast: w' \in L(N) \\ &\iff \lnot (\text{$M$ accepts input $w$}) \end{align\*}$$

The third equivalence is the reason behind constructing $N$ so as to reject inputs of the form $w'w'$. The last equivalence holds because not all strings are of the form $w'w'$ for some $w' \in \\{0,1\\}^\ast$.

To complete the construction of $S$, have it feed $\langle N \rangle$ to $R$ and accept if $R$ rejects and reject otherwise (i.e., $S$ returns the opposite of what $R$ returns). By the equivalences above, $S$ reduces $A\_{\text{TM}}$ to $L$, so $L$ must be undecidable.

---

As to your more general question regarding reductions: Unfortunately, I am afraid these kind of problems are rather tricky in of themselves. (I suppose that, at the core of it, the problem is that we are dealing with paradoxes, which are, of course, very nasty little things.) Nevertheless, Rice's theorem generalizes a great deal of these questions and makes it much simpler to prove something reduces to $A\_{\text{TM}}$ or the halting problem.

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


# Question
Title: Efficient simulation of an NFA, while preserving the paths to the accept states
The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.

However, for my purpose I need to know which paths the NFA went through for accepted words. This is obviously not trivial if I simply use the subset construction method. The NFA could also have $\epsilon$ transitions.

Of course, any such simulation could have a bad worst-case, in which there are a humongous amount of ways that the automaton could accept a given word. However, it'd be nice to have some sort of algorithm that runs, in, say, $O(m+n)$ for a word of length $m$ that the NFA has $n$ ways of accepting.

Is there any efficient way to do this?

# Answer
There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the transitive closure of the $\epsilon$-transitions. As you fill the table, you can include data that will allow you to reconstruct at least some of the accepting paths (or all of them, if you insist, though it will be more tricky to handle the $\epsilon$-transitions). The running time, however, won't be linear but more like $O(q^2m)$, where $q$ is the number of states; perhaps you could optimize this further for sparse NFAs, but probably not to $O(m+n)$.
> 6 votes

# Answer
*(I know I'm 4 years late, but I think I have a better solution than the one accepted.)*

You rarely want to build the full DFA from an NFA since the number of states in the DFA can be exponential larger. You might want to look up the Thompson's NFA algorithm for simulating an NFA in linear time.

In short, you parse the input string one symbol at a time, and at each step you have a set of active states. The new set of active states is the union of all the reachable states from each of the current states. The string matches if an accepting state is active when you reach the end of the input string.

Your problem seems pretty equivalent to tracking submatches in a regular expression, which can be done in linear time at the cost of an $O(n^2)$ memory usage.

The idea would be to attach to each active state one path that lead to this state. When a state is reachable from two distinct path, you pick either one of them. This path selection is what prevents the exponential blow from happening. In the worst case, each state is active and has to store a path through all the states, hence an $O(n^2)$ memory requirement. But the time is not modified.
> 1 votes

---
Tags: automata, finite-automata, simulation
---


# Question
Title: How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?
The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.

# Answer
> 0 votes
The given recurrence is: $T(n) = 3T(n/4) + \log n$

Using the substitution method, we get:

\begin{align} T(n) &= 3^2T \left(n/4^2\right) + \log n + 3\log (n/4) \\ &= 3^3T \left(n/4^3\right) + \log n + 3\log(n/4) + 9 \log(n/4^2)\\ \end{align} and so on.

Can you see a pattern now?

# Answer
> 0 votes
I use a simpler master theorem for scholar recurrences. Consider the general form $T(n) = aT(n/b) + f(n)$. Call $c=log\_ba$. Now you have 3 cases:

1. $\theta(n^c) = f(n)$ then $T(n) = \theta(f(n)log^k(n)) \text{ where }k\geq1$
2. $\theta(n^c) \gt f(n)$ then $T(n) = \theta(n^c)$
3. $\theta(n^c) \lt f(n)$ then $T(n) = \theta(f(n))$

In your exercise you have the 2nd case, so $T(n) = \theta(n^{log\_43})$.
However this method works only with simple recurrences.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Can a Turing Machine tell if an input string is a description of itself?
Can some Turing Machine $M$ with description $\langle M\rangle$, check if an input string $w$ is a description of itself? That is, can $M$ be constructed such that $M$ can tell if $w$ = $\langle M\rangle$?

The closest related problem I could find was: Can I construct a Turing machine that accepts only its own encoding?

But I want to consider the case where $M$ must recognize its own description as an intermediate step, and then accept or reject based on that and some additional criteria. Is this possible?

# Answer
> 1 votes
The answer is **yes**, and this is a standard application of the recursion theorem \- the slogan for this theorem being, "you can assume at the *beginning* of your construction that you know what the index of the construction will be at the *end*."

Let me outline how it is applied in this case:

You have a description of the machine you want, *with* a "gap" - a point where you want to insert the code for the machine itself. This really defines a *family of* machines, where we have $M\_k$ being the version where we stick in the number "$k$."

The process of building $M\_k$, given $k$, is recursive; that is, the function sending $k$ to the index for $M\_k$ is recursive.

Now on the face of it, that doesn't help since we just get an infinite regress: $M\_0$ has index $5$, $M\_5$ has index $17$, $M\_{17}$ has index $2$, ... However, the recursion theorem lets us catch our tail. Let $f$ be the recursive function mentioned above, which sends $k$ to the index for $M\_k$. Then by the recursion theorem, we get a fixed point for $f$: some $c$ such that the machine with index $c$ behaves identically to the machine with index $f(c)$.

But this means exactly that the machine $M\_c$ \- whose index is $f(c)$ \- behaves as if it was given its *own* index! (Intuitively, it "thinks" it has index $c$, and that's good enough: index $c$ and index $f(c)$ are "the same.")

---
Tags: turing-machines
---


# Question
Title: Transition diagram for following token number
**number -\> digits(.digits)?(E\[+ -\]?digits)?** This transition diagram runs the above mentioned token I can not understand this how this is work.what is meaning of "?"Symbol and digits. can anyone explain me this

# Answer
> 0 votes
**digits(.digits)?(E\[+ -\]?digits)?** is a regular expression for the set of strings that the pictured automaton accepts. That is, all of the strings accepted by the automaton will match this pattern. If you're unfamiliar with regular expression syntax, you can check out this explanation from Wikipedia.

In particular, if you see some pattern followed by the **?** operator, it means that pattern is optional. So something like **digits(.digits)?** will match strings of the form **digits.digits** or just **digits** because the last **(.digits)** part is optional.

I would guess that **digits** is a placeholder for a series of numeric digits (0-9). So something like **digits(.digits)?** would match strings like "33.5", "0.8", "1.892", "7", etc.

---
Tags: automata, compilers
---


# Question
Title: How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt $\mid \textbf{other} $

This grammar is called as Dangling Else Problem . However the ambiguity is resolved by parser as described as follows

> In all programming languages with conditional statements of this form, the first parse tree is preferred. The general rule is, "Match each else with the closest unmatched then"

It is rarely built into productions

$\textbf{stmt} \to$ $ \textbf{matched\_stmt}$ $\mid $ $\textbf{open\_stmt}$

$\textbf{matched\_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ matched\_stmt $ \textbf{else}$ matched\_stmt $\mid $ $\textbf{other}$

$\textbf{open\_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ matched\_stmt$ \textbf{else}$ open\_stmt

However this grammar is also ambiguous . Moreover no grammar is there that could eliminate ambiguity problem of Dangling else problem . Hence we can say that dangling else problem in also inherently ambiguous

Source : Compilers: Principles, Techniques, & Tools -Aho & Ullman

My question is How to prove that Ambiguity is still present in this resolved Production of Dangling Else Problem ? What I know is that if two different parse trees are possible then the grammar in ambiguous . Does any such parse trees possible for the resolved grammar ? If so could u please give an example parse tree for the same

# Answer
> 4 votes
A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you have to do is to come up with a string generated by your grammar that has two different parse trees.

# Answer
> 2 votes
First, we know that there are unambiguous grammars for this language. Let's ignore that.

A language isn't just defined by the grammar. It's defined by the grammar, plus our rules how to generate parse trees. The usual rule is "find every possible parse tree". With that rule some grammar might be ambiguous because we can find two or more parse trees.

If a compiler uses a different set of rules, and with those rules there is only *one* parse tree, then the combination of grammar and rules is **not ambiguous**. That's what's happened here: The compiler says "in case of ambiguity we decide to use one parse tree and not the other". That makes the language created by grammar + compiler rules unambiguous.

As an example, we often have a grammar and try to produce lets say an LR-1 parser for the grammar, and trying to produce that parser might fail (because at some point there are two different productions that could be used, especially if the grammar is ambiguous). But we can always produce a non-deterministic parser, and turn it into a deterministic parser by picking *one* production wherever the non-deterministic parser would give us a choice. We now have a deterministic, unambiguous parser, derived from the grammar, which will parse some language in an unambiguous way.

# Answer
> 2 votes
While the first grammar is ambiguous, the second is not.

We can see that the first is ambiguous by considering the string

$\mathbf{if} \\; \mathit{expr} \\; \mathbf{then} \\; \mathbf{if} \\; \mathit{expr} \\; \mathbf{then} \\; \mathbf{other} \\; \mathbf{else} \\; \mathbf{other}$

which has two left-most derivations with the first grammar.

We can prove that the second is not ambiguous by showing that it is LALR; this we can do by compiling the following file with bison.

```
%start stmt
%token IF THEN ELSE EXPR OTHER
%%

stmt : matched_stmt
    | open_stmt ;
matched_stmt : IF EXPR THEN matched_stmt ELSE matched_stmt
    | OTHER ;
open_stmt : IF EXPR THEN stmt
    | IF EXPR THEN matched_stmt ELSE open_stmt ;

```

No conflicts are reported, so the grammar is LALR, and hence it is unambiguous.

As @rici pointed out in the comments, the Aho et al. book does not claim that the second grammar is ambiguous.

In my copy (1986, corrected) the following grammar *is* claimed to be ambiguous in an exercise.

$\mathit{stmt} \rightarrow \mathbf{if} \\; \mathit{expr} \\; \mathbf{then} \\; \mathit{stmt} \mid \mathit{matched\\\_stmt}$ $\mathit{matched\\\_stmt} \rightarrow \mathbf{if} \\; \mathit{expr} \\; \mathbf{then} \\; \mathit{matched\\\_stmt} \\; \mathbf{else} \\; \mathit{stmt} \mid \mathbf{other}$

And it is.

# Answer
> -1 votes
To prove some Grammar is Ambiguous You have find Atleast 2 or more $LMD or RMD$(Left or right most derivative tree) for a string $w$ which belongs to the grammar.

There is small catch here, it is not necessary that if a string has two derivation it will produce a ambiguity but if the derivation of the string has more than two parse tree it surely produce ambiguity.

If we talk about the Inherently ambiguous here are some explanation given by friend Rahul I think Its worth reading it.

let's say we have

$S \to A\mid B $

A generates all the strings where m=n

B generates all the strings where n=p

Now, we can observe that both A and B can generate common strings which are m=n=p.

So while deriving such strings we can either go by

$S \to A$

Or

$S \to B$

We have two possible derivations (LMD or RMD doesn't matter because in either case we derive only one non-terminal). Hence it is inherently ambiguous.

We can have 2 parse trees to generate the common strings. Remember this rule of thumb,

If you find a production of the form

$S\to A \mid B$

Of a grammar that generates a language AND A&B can generate strings that are common AND you can't MODIfy the grammar to eliminate this commonality then it is inherently ambiguous.

---
Tags: context-free, formal-grammars, parsers, ambiguity
---


title: Amplification for Randomized Algorithms

text:
# Question
Title: Amplification for Randomized Algorithms
I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.

---

**Amplification for randomized algorithms:**
Given a randomized algorithm with time complexity $f(n)$ and error probability $\frac{1}{4}$, show there is an algorithm that solves the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\varepsilon}\right)\right)$ run time, and error probability of $\varepsilon$, for a given $\varepsilon\>0$.

I managed to show this running the original algorithm $k$ times, and choosing by majority vote the answer. Using Multiplicative Chernoff Bound (Which I've proven as well), I've shown $k\geq O\left(ln\left(\frac{1}{\varepsilon}\right)\right)$ gives us the required results.

---

Now I'm trying to do the same for approximation algorithms.

**Amplification for randomized approximation algorithms:**
Given a randomized approximation algorithm that returns an $\varepsilon$-additive-approximation with a probability of $\frac{3}{4}$, with run time complexity of $f\left(n\right)$, show there is an algorithm that returns an $\varepsilon$-additive-approximation with a probability of $1-\delta$, for the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\delta}\right)\right)$ run time, for a given $\delta\>0$.

The first thing that comes to my mind, is use a similar approach as before - run the original algorithm $k$ times, but this time instead of using majority vote, return the average.

I have to somewhow find a $k\geq O\left(ln\left(\frac{1}{\delta}\right)\right)$ such that $\mathbb{P}\left\[\left|OPT-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}X\_{i}\right|\>\varepsilon\right\]\<\delta$.

I tried using the triangle inequality, then using union bound, but this doesn't lead me to being able to use Chernoff. In order to use Chernoff, I thought of defining an indicator random variable for each run of the original algorithm, stating if the result - $X\_{i}$ is bad (that is, if $\left|X\_{i}-OPT\right|\>\varepsilon$), but this is where I get stuck.

Would appreciate any help. Thanks!

# Answer
Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.
> 1 votes

---
Tags: algorithms, approximation, randomized-algorithms
---


# Question
Title: PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?
In *Practical Foundations for Programming Languages*, on page 138 (page 156 of the pdf), it says:

> Requiring solutions to all type equations may seem suspicious, because we know by Cantor’s Theorem that an isomorphism such as $X \cong (X \rightarrow \mathbf{2})$ is set-theoretically impossible. This negative result tells us not that our requirement is untenable, but rather that types are not sets.

I understand why solving such an isomorphism is set-theoretically impossible, and therefore why being able to solve it means that "types are not sets". However, I cannot think of any possible type $X$ that would actually solve this isomorphism.

Can anyone give an example of such a type (and ideally, some advice for more generally solving such type isomorphisms)?

# Answer
> 6 votes
To say that we cannot solve $X \cong (X \to 2)$ in sets means that we have to do it in another category. And because we're talking programming languages, we should be looking for one in domain theory. The buzzword to look for is *recursive domain equation*.

There are several kinds of domains, but to give you an idea of what they are, perhaps we can recall the definition of $\omega$-cpos. An $\omega$-cpo $(P, {\leq})$ is a set $P$ with a partial order $\leq$ which has a least element $\bot \in P$ and such that every increasing sequence $x\_0 \leq x\_1 \leq x\_2 \leq \cdots$ in $P$ has a supremum.

In the particular case we look for a domain $X$ which satisfies $$X \cong \[X \to 2\_\bot\]$$ where:

* the domain $2\_\bot = \\{0, 1, \bot\\}$ is ordered by $\bot \leq 0$, $\bot \leq 1$ (i.e., $\bot$ is below $0$ and $1$, and $0$ and $1$ are incomparable). The domain $2\_\bot$ corresponds to the datatype `bool`: $0$ and $1$ are the boolean values, while $\bot$ represents a non-terminating program.
* the domain $\[E \to D\]$ is the domain all all continuous maps from $E$ to $D$, where a map is said to be continuous if it is monotone and it preserves suprema of increasing chains.

Now, the reason why an equation such as $X \cong \[X \to 2\_\bot\]$ has a solution is complicated. Figuring out that soultions exist when we take a good enough notion of "domain" was done in the early 1970s, with poineering work of Dana Scott and several other people. It takes a short course on domain theory to get to the point where the construction of solutions becomes explainable.

Perhaps I can comment on why domain theory avoids the usual problem from set theory, where Cantor's diagonal argument shows that $X$ always has fewer elements than $X \to 2$. In domain theory $\[X \to 2\_\bot\]$ is *not* the set of all maps, but just the continuous ones, and there are many fewer of those.

Let's attempt a more familiar setup. Consider the real number $\mathbb{R}$ and the Sierpinski space $\mathbb{S}$, which just the set $2 = \\{0, 1\\}$ with the topology in which the open sets are $\emptyset$, $\\{1\\}$ and $\\{0, 1\\}$. It is well known that the set of continuous maps $\mathcal{C}(\mathbb{R}, \mathbb{S})$ is in bijective correspondence with the open subsets of~$\mathbb{R}$, of which there are $2^{\aleph\_0}$, and so we have "solved" $X = X \to 2$ in sets by restricting to continuous maps: $$\mathbb{R} \cong 2^{\aleph\_0} \cong \mathcal{C}(\mathbb{R}, \mathbb{S}).$$ This is not a solution, however, because the bijection between $\mathbb{R}$ and $\mathcal{C}(\mathbb{R}, \mathbb{S})$ can never be a homeomorphism.

Sometimes we can actully solve a recursive equation with much less work. For instance, working in topological spaces, we have $$\mathbb{N} \cong 2^{2^\mathbb{N}}$$ because $2^{\mathbb{N}}$ is the Cantor space, whose set of clopen sets is countable and discrete (under the compact-open topology), therefore homeomorphic to $\mathbb{N}$.

Yet another example comes from ordinal arithmetic (*not* cardinal arithmetic!) where have $2^\omega = \omega$, so that is maybe the closest to what you're asking for.

---
Tags: programming-languages, type-theory, sets
---


# Question
Title: Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$
The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$

But is it possible to use the master theorem for recurrence relations of the form $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$?

# Answer
Yes, you can, as David has pointed out. However, his answer only mentions the case of the upper bounds explicitly, leaving the case of the lower bounds dangling.

In fact, the conclusion of master theorem, which gives asymptotic approximation of the given function $T$ in $\Theta$ notation, still holds if we change the recurrence relation from $$ T(n) = aT(\frac{n}{b}) + g(n)$$ to $$T(n) = aT(\lfloor\frac{n}{b}\rfloor) + g(n),$$ or $$T(n) = aT(\lceil\frac{n}{b}\rceil) + g(n),$$ or, even more generally, $$T(n) = aT\left(\frac{n}{b}+ h(n)\right) + g(n),\text{ where } h(n)\in O\left(\frac n{\log^2n}\right).$$

These variants of the master theorem can be obtained by applying Akra–Bazzi method.
> 1 votes

# Answer
Yes, you can.

We use the master theorem in the context of giving upper bounds to increasing functions $T$. In this context, we know that $T(n)=aT(\lfloor n/b\rfloor) + g(n) \leq aT(n/b)+g(n)$ so any upper bound on the recurrence without $\lfloor\cdots\rfloor$ is also an upper bound on the recurrence with $\lfloor\cdots\rfloor$.
> 2 votes

---
Tags: recurrence-relation, recursion, master-theorem
---


# Question
Title: Formula for finding number of colors to color a map such that no two adjacent counties have the same color
Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?

# Answer
> 5 votes
No.

* The famous four-colour theorem says that four colours are always enough (assuming that counties are contiguous areas of land).
* It's easy to tell if one colour is enough: this is the case only if every county is an island, so has no border with any other county.
* It's easy to tell if two colours is enough: this corresponds to the adjacency graph being bipartite. You can determine this by colouring an arbitrary county red, then colouring all its neighbours blue, then colouring all their neighbours red, and so on. If this process produces a legal colouring, you have your colouring; if it fails, it turns out that there is no colouring with two colours.
* If two colours isn't enough, then it's **NP**-complete to tell whether three is enough or you have to use four. This means that, as far as we know, there's no efficent algorithm to determine whether an arbitrary map can be coloured with three colours. This is a result due to Garey, Johnson and Stockmeyer (*Some simplified NP-complete graph problems*, Theoretical Computer Science, 1(3):237--267, 1976; Science Direct).

There are efficient algorithms to find four-colourings of planar graphs: the two computer-assisted proofs that four colours is enough both gave algorithms. But, as noted above, there's no known efficient algorithm to tell whether four colours is optimal for a given map.

# Answer
> -1 votes
In this case the problem is NP-complete. By the way we know that:

Given a graph $G$, let $\chi(G)$ be the number of colors of $G$ and $\Delta(G)$ the maximum degree in $G$. we have that $\chi(G)\le \Delta(G)+1$.

However if $G$ is a planar graph (a map), then $\chi(G)\le 4$.

For more information see the "Four color theorem by Kenneth Appel and Wolfgang Haken".

---
Tags: algorithms, graphs
---


# Question
Title: Relationship between Deterministic Finite Automata languages
What this "⊃" superset means? What do I need to prove here. Can someone, please, explain in English? Do I need to do a cross product? Plus, in textbooks and online I only see "∩" "∪" these kinda symbols. What this symbols "⊃" means?

```
Let M = (K, Σ, δ, s, F) be a deterministic finite automaton. Let M' =
(K, Σ, δ, s, F') be a similar deterministic finite automaton where F is
a proper
subset of F'. For each of the following provide an example to show that
the
relationship between L(M) and L(M') is possible or explain why the
relationship
is not possible.

The problem to prove: L(M) ⊃ L(M')

```

# Answer
> 0 votes
There are a wealth of set theory symbols that are in wide usage. I have seen or used most of those symbols .

In particular, "$L(M) \supset L(M')$" means $L(M) $ is a superset of $L(M')$, but $L(M)$ is not equal to $L(M')$. This is consistent with the explanation given by Wikipedia. To be more specific, it means all words in $L(M')$ are in $L(M)$, but at least one word is in $L(M)$ but not in $L(M')$.

A simple example of that situation can be the following. $M'$ is the finite automaton depicted at Wikipedia example with $S\_0$ being the only accepting state. $M'$ accepts words with even number of 0's. Let $M$ be the same as $M'$ except that both states are accepting states. Then $M$ accepts all words.

---
Tags: finite-automata
---


# Question
Title: What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?
Consider the recurrence $$ T(n,m) = T(n,m-1) + T(n-1,m) + c, $$ with base cases $T(n,0) = T(0,m) = 1$.

This is the complexity of a recursive algorithm for the longest common subsequence, I know that the complexity is exponential and equals $\Theta(2^i)$, but I'm not sure if $i=\max(n, m)$ or $i=nm$. Also, how can I demonstrate it using induction?

# Answer
The function $f(n,m) = \binom{n+m}{n}$ satisfies the recurrence $$ f(n,m) = f(n-1,m) + f(n,m-1), $$ with base cases $f(n,0) = f(0,m) = 1$. This already gives you the solution when $c = 0$, assuming that the base cases are $f(n,0) = f(0,m) = 1$.

One function which satisfies the recurrence, though (in general) not the base case, is $g(n,m) = -c$: $$ g(n,m) = g(n,m-1) + g(n-1,m) + c. $$ This gives the solution when $c = -1$.

Finally, note that any function of the form $\alpha f(n,m) + g(n,m)$ is also a solution of the recurrence. Since $$ \alpha f(n,0) + g(n,0) = \alpha f(0,m) + g(0,m) = \alpha - c, $$ we see that $$ T(n,m) = (c + 1) f(n,m) + g(n,m) = (c+1) \binom{n+m}{n} - c. $$
> 4 votes

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


title: Is this a valid use of big-O notation?

text:
# Question
Title: Is this a valid use of big-O notation?
Suppose that $m=O(n^{c+1/2})$ for some real $c\>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.

**Computation 1** \begin{align} f(x)\leq \exp(-x^2/2)&=\exp(-O(\log m))\\ &=\exp(-O(\log O(n^{c+1/2})))\\ &=\exp(-O(\log n^{c+1/2}))\\ &\leq \exp(-K\_1\log n^{c+1/2})))\\ &=n^{-O(1)} \end{align} where $K\_1\>0$ when $n$ is sufficiently large (i.e. there exists $K\_1\>0$, $n\_0$ such that when $n\geq n\_0$, $\exp(-O(\log n^{c+1/2}))\leq \exp(-K\_1\log n^{c+1/2})))$. The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions (see accepted answer in this post).

**Computation 2** $$ f(x)\frac{m}{n^{1/2}} \leq n^{-O(1)}\frac{m}{n^{1/2}}=\leq n^{-O(1)}\frac{m}{n^{c+1/2-c}}=O(1)?? $$

# Answer
If these computations appear in a paper for me to review, I would like to ask the author to rewrite.

> $$\exp(-x^2/2)\leq \exp\left(-K\_1\log n^{c+1/2\\,}\right), \text{ where } K\_1\>0$$

This is wrong. The direction of inequality should be switched. For example, let $n\to\infty$ and $x$ be constant 1, the left hand side remains a constant while the right hand side goes to 0. This error means "Computation 2" is wrong from the start.

> The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions.

Instead of $n^{-O(1)}\\,$, $n^{O(1)}$ represents asymptotically the set of polynomially-bounded functions.
> 1 votes

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


# Question
Title: Forming polylines from a list of individual lines
I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example:

* `M10,10 L20,10 M20,10 L20,20` becomes `M10,10 L20,10 L20,20`.
One line ends where there other begins, it can become a polyline.
* `M10,10 L20,10 M20,10 L30,10` becomes `M10,10 L30,10`.
The second line extends the first line, they can be merged into one line.

I found a basic way to do it in $O(n^2)$.

1. Start with an empty list of polylines.
2. Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline. If the slope between the new and last points is the same as the slope between the last and before last points, then only replace the last point with the new point.
3. Remove the line from the list.
4. Repeat until list is empty.

As you can guess this algorithm performs quite badly, taking forever with as little as 20,000 lines.

How to do it in $O(n)$?

# Answer
> 2. Loop over all invidivual lines. **If a point of the line is the same as one of the polylines head or tail**, extend the polyline

(My emphasis). How are you doing that test? To take $\Theta(n^2)$ time, I think you must be testing each point by linear scan in $\Theta(n)$. Use a decent hashmap instead and it will take $\Theta(1)$ on average.
> 1 votes

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


title: Is this algorithm of constant time?

text:
# Question
Title: Is this algorithm of constant time?
I have the following code in Python:

```
def is_unique(string):
    if len(string) <= 1:
        return True

    if len(string) > 128:
        return False

    char_set = defaultdict(lambda: False)

    for char in string:
        if not char_set[char]:
            char_set[char] = True
        else:
            return False

    return True

```

It's basically checking if a string is unique or not. I think that my algorithm is O(1):

No matter what it's the length of the string, I will only iterate over at most 128 times in the worst case. All the operations (`len`, `dict` lookup etc) are of constant time as well.

I guess my generic question here is if you can proof that your algorithm will always iterate for a constant number of times, can you claim that this is O(1)?

# Answer
Under the assumptions you've stated, yes, the code runs in constant time. The running time for any string can't be longer than the running time for a 128-character string, which is some constant number of steps.
> 4 votes

# Answer
You have to be careful with your assumptions, particularly the one on constant time dictionary lookup in the worst case. In general, this does *not* hold (see e.g., Wikipedia on hash tables). It depends precisely on the implementation details of the dictionary, but I would assume the general purpose dictionary implementation does not guarantee this.

With that being said, it seems that your setting is static so you can guarantee constant time lookups in the worst case by at least FKS hashing. In fact, you can more simply just use a direct access table instead of the dictionary.
> 3 votes

# Answer
Generally yes. I mean if an algorithm can run in $O(f(n)) = c$ time, where $c$ is a $constant$, then it is in $O(1)$ time.
> 1 votes

---
Tags: time-complexity
---


# Question
Title: Minimum perfect matching with uneven vertices?
Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?

# Answer
> 1 votes
A perfect matching is one that includes every vertex so only graphs with an even number of vertices can have a perfect matching. If the number of vertices is odd, there is simply no perfect matching.

---
Tags: graphs, matching
---


# Question
Title: Linear ordering of all subsets of size k
I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\\{1,\ldots, n\\}$ into $\\{1, \ldots, {n \choose k}\\}$ that can be computed in $O(1)$ at best.

The most trivial way for this would be to use a tree where each leaf node corresponds to such a subset but then I have to save the entire tree and each lookup will cost more than $O(1)$. We could also totally order those subsets such that $\\{1, 2, 3\\}$ would be the smallest subset for $k=3$ and $\\{n, n-1, n-2\\}$ the largest one and then use the number of smaller/equal subsets in this ordering as our index. I tried to come up with a closed form solution and it ended in some gnarly sums of binomial coefficients.

So maybe there is a well known solution to this problem and somebody could give me a reference?

# Answer
The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.
> 0 votes

---
Tags: algorithms, data-structures, terminology, combinatorics
---


# Question
Title: Find shortest prefix to generate original string by overlapping
Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\\{0,3,8\\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.

# Answer
What you are looking for is called the *quasiperiod* of a string. If such a string has a *quasiperiod* of $|S|$ it is called *superprimitive*, and can not be *covered* by a substring.

A method for computing it in $O(n)$ time is given in *"An On-Line String Superprimitivity Test"* by Dany Breslauer. You might also be interested in *"Of Periods, Quasiperiods, Repetitions and Covers"* by Alberto Apostolico and Dany Breslauer.
> 1 votes

---
Tags: substrings, string-matching, suffix-trees, suffix-array
---


# Question
Title: Need help to come up with definitive proofs with regard to Planar Graphs
I was working through a few problem sets and came across this question

> Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle consisting of three edges).
>
> Question 1: Into how many regions does a representation of the Planar Graph $G$ Split the plane?

Incase of this question, since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$ and got my final answeras $2(v+2)$.

> Question 2: Suppose the vertices of the planar graph G are colored in three colors. A region is called to be tricolored (or bicolored) if its vertices are colored in exactly three (or two) different colors. Similarly, a monocolored region is the one with all its vertices colored in exactly one color. Prove that the number of tricolored regions is always even no matter how the vertices are colored.
>
> (Hint: If you place a new vertex inside a region (triangle) of G and connect it with all vertices of that region, then all regions are still triangles and the parity of the total number of regions stays the same.)

This question seemed very straight-forward to me on account of my previous answer. Since I derived the value $r = 2(v+2)$ which would always remaining even while incrementing $v$. I don't really understand the point of the Hint or maybe what exactly we have to prove here.

Any help with regard to the same would be appreciated. Thanks!

# Answer
> 1 votes
> Since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$ and got my final answer as $2(v+2)$.

The final answer should be $2(v-2)$.

> Since I derived the value $r=2(v-2)$ which would always remaining even while incrementing $v$.

You are right that $r$, the number of regions will always remain even since $r=2(v-2)$. However, question 2 is asking you to prove "the number of **tricolored** regions is always even no matter how the vertices are colored.".

> I don't really understand the point of the Hint or maybe what exactly we have to prove here.

The hint is meant to give you a clue how to reduce the number of vertices. The proof (or my proof) is quite easy and direct once you know it. I will let you figure out your proof.

---
Tags: graphs, planar-graphs
---


# Question
Title: Can someone explain the language L = {w: w = uu, u \in La(1*01*)}
I need help understanding the language `L` above.

These are my understanding:
\- `w = uu` is a concatenation of `u`
\- `La(1*01*)` can be expressed in regular language i.e. `r1 = 1*01*` so `La(r1)`
\- also we have regular expression property of concatenation: `L(r1r2) = L(r1)L(r2)`

So base on my understanding the language `L` can be simplified to

I'm not quite sure about this.

# Answer
No, your simplification is wrong.

Consider, as a simpler case, $A=\\{a,b\\}$ and $L'=\\{ w \mid w=uu , u\in A\\}$. Then, $L'=\\{aa,bb\\}$.

Instead, if we apply your simplification and write $L''=AA$ then we have $L''=\\{aa,ab,ba,bb\\}$ which is a larger language, since we forgot that both $u$'s in $w=uu$ must be the *same* word.

Keeping that into account, your original language $L$ seems to be $\\{1^n01^m1^n01^m \mid n,m\geq 0 \\}$
> 0 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Find total number of assignment in the worst case?
I have this algorithm

```
Algorithm (A[1..n])
    for i <- 1 to n do
        if (A[i] < 0) then
            A[i] <- 1 * A[i]
        End if
    End for

```

I have to find the total number of assignment in the worst case, but I'm a little bit confused, do I say I have 2 or 1, one for the assign A\[i\] in the statement and second for the i in the for loop (i \<- 1).

# Answer
> 1 votes
Likely the question is asking you to focus on line 4, in which you assign a value to A\[i\]. You can also focus on the for-loop with and its control variable to get a complete answer, but the only way to know for sure is to ask the person responsible for the problem.

Anyway, more precisely, the question is how many assignments do you do in the worst case as a function of the array length $n$. As you can see, this number is determined by the number of times the preceding if-branch evaluates to true. Your task is to argue how many times that can happen in the worst case.

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


# Question
Title: Prove a^4n b^m is irregular using puming lemma
My assignment is to prove that the language

$L = \\{ a^{4n} b^m \mid n \> m \>= 0\\}$ is not a regular language.

My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an equal #a and #b if you "pump down" your $v$ so that it is $v^0$, so that the condition $n \> m$ is no longer fulfilled. Then I realized I completely disregarded that it's $4n$ and not just $n$, so I wasted a lot of time on that.

Now I'm absolutely out of ideas, because as I see it you can always find an number $p$, so that you can pump a number of as however often you want as long as p is divisible by 4 because if you divide your word $z = uvw$, both $u$ and $v$ need to have a number of as divisible by 4 as to not break the $4n$ condition.

However, that would mean that you absolutely can not prove that $L$ is not regular using the pumping Lemma, which contradicts the assignment. Where is the flaw in my logic?

I would really appreciate some pointers.

# Answer
Yes, you can use the pumping lemma. It looks like your line of thoughts just had a minor glitch.

Suppose your adversary claims the pumping lemma for $L$ works for some number $p\ge1$.
You can pick $z=a^{4(p+1)}b^p$, a word that "barely" satisfies the requirement.
Your adversary claims $z=uvw$ where $|v|\ge1$, $|uv|\le p$ and for all $n\geq 0$, $uv^{n}w\in L$.

Since $|uv|\le p\<4(p+1)$ and $z$ starts with $4(p+1)$ consecutive $a$'s, there must be no $b$ in $uv$. That is, $v=a^i$ for some $i=|v|\ge1$.

Consider $uv^0w=uw$. Since $z$ "barely" satisfies the requirement, removing some $a$'s without removing any $b$ will make $z$ not satisfying the requirement. You have beaten your adversary, again.

The above proof works, in fact, for any language $M$ such that $L\subseteq M\subseteq \\{w\mid \\#\_a(w)\ge4(\\#\_b(w)+1)\\}$.

I have been saying "$z$ 'barely' satisfies the requirement", since it is easier to understand that way although it is not very rigorous. It should be quite easy for readers to make it rigorous.
> 1 votes

# Answer
Assume L is regular with pumping length p.

Choose n = floor (p/5) + 1, m = n-1. Then w = $a^{4n} b^m$ is in L, and has length ≥ p. Choose w = xyz.

If y contains only b's then $xy^kz$ is not in L for k ≥ n because there are too many b's.

If y contains both a's and b's then $xy^2z$ is not in L because it has the form $a^+b^+a^+b^+$ which is not in l.

Therefore y contains only a's. If the number of a's in y is no multiple of four then xz is not in L because the number of a's in xz is not a multiple of 4.

Finally, if the number of a's in y is a multiple of four then xz has too few a's.
> 1 votes

# Answer
I find it easiest to prove that the language is not recognised by any finite state machine.

Assume a finite state machine has processed the string $a^{4k}$, k ≥ 0 and ended up in the state $S\_k$. The set of strings that lead from $S\_k$ to an accepting state is exactly ${a^{4n} b^m : n+k \> m \> 0}$. For every k, this set of strings is different, therefore each state is different, therefore the set of states is not finite.

PS. The proof for the pumping lemma just shows quite easily that a language with a finite state machine must fulfil the conditions of the pumping lemma, so checking that the pumping lemma fails to apply to a language shows a contradiction to the existance of an FSM. I think showing directly that there is no limit to the number of states is easier, especially if the language is a bit more complex.
> 0 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: What does binary NP-Hard exactly mean?

text:
# Question
Title: What does binary NP-Hard exactly mean?
Can someone tell me what binary NP-Hard exactly means. My understanding was that if the problem is encoded in binary and if the problem is binary NP-Hard, its complexity of solving is NP-Hard. Is this the correct interpretation?

I also wanted to know, if binary NP-Hard also says something about Strong or Weak NP-Completeness of the problem.

# Answer
> 4 votes
The complexity of a computational problem depends on the exact representation of the input.

One of the go-to examples here is the Knapsack problem. Given $n$ items with (integer) weights $w\_1,...,w\_n$, and two integers $W,V$, decide whether there exists a subset $S\subseteq \[n\]$ such that $V\le \sum\limits\_{i\in S}w\_i\le W$. We know that the problem can be solved in time $O(nW)$ in the word-ram model. This means that assuming $P\neq NP$, knapsack is not NP complete if the input is of size $\Omega(nW)$, hence it is not complete when $W$ is encoded in unary. Thus, when talking about the NP completeness of knapsack, it is important to specify that we're talking about the version where $W$ is encoded in binary, or "binary knapsack" for short.

---
Tags: complexity-theory
---


# Question
Title: expected pairwise square euclidean distance between points
How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?

Where $X$ is a $(x\_1,...x\_n)$ of points generated uniformly at random in the unit, d is d-dimensional cube , $x=(x(1),...x(d))$ the generic point has its -th component $x(i)$ chosen uniformly at random in$ \[0,1\] $independently of other components and points.

$\Theta(d)$ represent the largest possible distance is d.

I try to reconduct this problem to Bertrand Paradox but i dont think is right. Maybe I that show that $E(||x−y||2)=Θ(d)$ , because is a hint but i dont know how.

i m following this path: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

but is different to my point.

Thanks.

# Answer
> 1 votes
Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $\[0,1\]^d$. That is, $x\_1,\ldots,x\_d,y\_1,\ldots,y\_d$ are all uniform random samples of the uniform distribution over $\[0,1\]$. Then $$ \mathbb{E}\[\\|\vec{x}-\vec{y}\\|^2\] = \mathbb{E}\left\[\sum\_{i=1}^d (x\_i-y\_i)^2\right\] = \sum\_{i=1}^d \mathbb{E}\[(x\_i-y\_i)\]^2 = d \operatorname\*{\mathbb{E}}\_{x,y \sim \[0,1\]} \[(x-y)^2\]. $$ Let $C = \mathbb{E}\[(x-y)^2\]$. Then the expected squared distance of two points in $\[0,1\]^d$ is $Cd$.

It is not hard to calculate $C$ explicitly: $$ C = \mathbb{E}\[((x-1/2) - (y-1/2))^2\] = \mathbb{E}\[(x-1/2)^2\] + 2\mathbb{E}\[(x-1/2)(y-1/2)\] + \mathbb{E}\[(y-1/2)^2\] = \\ 2\mathbb{E}\[(x-1/2)^2\] + 2\mathbb{E}\[x-1/2\] \mathbb{E}\[y-1/2\] = 2\mathbb{E}\[(x-1/2)^2\] = \\ 2\int\_0^1 (x-1/2)^2 \\, dx = 2\int\_0^1 x^2-x+\frac{1}{4} \\, dx = 2\left(\frac{1}{3} - \frac{1}{2} + \frac{1}{4}\right) = \frac{1}{6}. $$

---
Tags: probability-theory, randomized-algorithms, euclidean-distance
---


# Question
Title: Trying to prove semidecidability of an undecidable language
I have been having a hard time understanding whether the set $S = \\{ M \mid |L(M)| = 5 \\}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, which consists of exactly five strings. Because $S$ is a property of the accepted language (there exists a TM that recognizes $L$), hypothesis of Rice Theorem applies, and because the set is not empty nor it is the set of all computable functions (equally, $S$ is non-trivial), it is undecidable. Yet, is it semidecidable? I was kinda attempting to prove that the complement of $S$ is semidecidable (thus guessing that $S$ is not semidecidable), but couldn't come up with anything useful.

# Answer
We know that the halting problem is semidecidable, but the non-halting problem is not semidecidable (since otherwise the halting problem would be decidable). Hence one way to show that a language is not semidecidable is by reduction from the non-halting problem.

Let $\langle M,x \rangle$ be an input the the non-halting problem. We construct a new Turing machine $M'$ which on inputs $1,2,3,4,5$ halts, on input $6$ simulates $M$ on $x$, and on all other inputs never halts. Then $M' \in S$ iff $M$ doesn't halt on $x$.

We can also construct another Turing machine $M''$ which on inputs $1,2,3,4$ halts, on input $5$ simulates $M$ on $x$, and on all other inputs never halts. Then $M'' \notin S$ iff $M$ doesn't halt on $x$.

These reductions show that neither $S$ nor its complement are semidecidable.
> 1 votes

---
Tags: turing-machines, computability, rice-theorem
---


# Question
Title: Can we remove duplicates faster than we can sort?
The problem is (integer) **duplicate removal**, which can also be perceived as producing the **image of an evaluated function** (of integers):

> Given a sequence $S\_\text{in}$ of $n$ integers, produce a sequence $S\_\text{out}$ of elements such that any element in $S\_\text{in}$ also appears in $S\_\text{out}$, and all elements in $S\_\text{out}$ are distinct.

Ignoring some details regarding the elements' size in bits, this can be done by sorting in $O(n \log n)$ time; or by hashing in expected time $O(n)$.

Given that we don't require $S\_\text{out}$ to be sorted - is it possible to do better than sorting in the worst case?

Notes:

* Some dependence on the output size (let's call it $m$) rather than $n$ is an improvement, but I'm mostly interested in getting closer to linearity in $n$.
* The details I've ignored may not be so insignificant.
* Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.
* We cannot make any assumptions regarding the input distribution.

# Answer
It is a classical result that the *element distinctness* problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (rather than just $x\_i - x\_j$).

The element distinctness problem asks whether all elements in the input are distinct. This is clearly easier than your problem, since you can just compare the sizes of the input and output arrays. Hence in these computation models, you cannot do asymptotically better than $n\log n$.
> 6 votes

# Answer
You can do $O(n \log m)$ if you use a (balanced) binary search tree as a set.

I don't know about a linear-time algorithm to solve this problem, perhaps there is a reduction to prove this is impossible?
> 1 votes

# Answer
If every element of the array ($a$) is in the range of $0$ to $k$, you can have $\theta(n)$ runtime when $k=O(n)$. All you have to do is to maintain an array ($c$) of $k$ elements initialized to $0$ and set $c\[a\[i\]\] = 1$ whenever $a\[i\]$ is encountered to be 0. At the same time you should write the corresponding element ($a\[i\]$) in an array $b$ only if the $c\[a\[i\]\] =0$.
> -1 votes

---
Tags: time-complexity, sorting, hashing
---


# Question
Title: Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be inserted in the tree. I am defining the ordering of the matrix elements simliar to how C handles a row-major ordered dense matrix. In particular, a matrix element $(i\_a,j\_a)$ comes before $(i\_b,j\_b)$ if: $$ N i\_a + j\_a \< N i\_b + j\_b $$ I need to write a routine which returns $-1$ if $(i\_a,j\_a)$ is less than $(i\_b,j\_b)$, $+1$ if $(i\_a,j\_a)$ is greater than $(i\_b,j\_b)$ and $0$ if they are equal. I want this routine to be as fast as possible since I will be calling it hundreds of millions of times.

I've tried two options so far, which I implement as macros to avoid the overhead of a function call.

**Option 1:** Comparing rows first and then compare columns

```
#define COMPARE(ia,ja,ib,jb) (ia < ib ? -1 : (ia > ib ? 1 : (ja < jb ? -1 : ja > jb)))

```

The worst case for this option is 4 comparisons between integers.

**Option 2:** Compare full linear index

```
#define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)

```

The worst case for this option is 2 multiplies, 2 adds, and 2 comparisons (assuming the compiler optimizes so that the quantities $N i\_a + j\_a$ and $N i\_b + j\_b$ are computed only once).

So far, Option 1 is a clear winner, and runs faster by around 20-30% on tests I have done.

**My question is: can anyone suggest a way to optimize this even more, by somehow improving on Option 1, or perhaps suggesting a completely different method of sorting matrix elements in the tree?**

Profiling has shown that a significant amount of time is spent in this comparison function, so it is worth it to me to make it as fast as possible.

Another idea I have is to use 2 levels of binary trees. The high-level tree uses only row indices for sorting. Then each node in that tree contains a pointer to another tree which uses the column indices for sorting. This way the comparison function only needs to compare two integers instead of 4. But having 2 levels of tree would make things more complicated. I have not implemented or benchmarked this approach yet.

# Answer
> 1 votes
> Option 2: Compare full linear index
> `#define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)`

Instead of `N`, use the minimal power of 2 that is not less than `N`. For example, if N = 10000, use $2^{14}=16348$. So we can have `#define COMPARE(ia,ja,ib,jb) ((ia << 14) + ja < (ib << 14) + jb ? -1 : (ia << 14) + ja > (ib << 14) + jb)`.

Instead of using #define, we can use a function to make sure that long expression is computed only once. `forceinline` is defined to be the cross-platform forceinline modifier.

```
#define TWO_EXPONENT 14
forceinline int compare(int ia, int ja, int ib, int jb) {
    int t1 = ((ia - ib) << TWO_EXPONENT) + (ja - jb);
    return (t1 > 0) - (t1 < 0);  //branchless computation
}

```

You have specified that you need to return 3 values, 1, 0, and -1. That sounds more than enough. You may want to double check if it is enough to use 1 for the case of "not smaller than". That is enough, for example, when we just want to sort an array of numbers.

Just in case you have not noticed, there are a wealth of information on how to store sparse matrix, Google search or Wikipedia entry.

---
Tags: sorting, binary-trees, program-optimization, comparison, sparse-matrices
---


title: Find the efficiency class

text:
# Question
Title: Find the efficiency class
I have to find the efficiency class of this algorithm

```
b = 3
a = 4
for i = 4 to n^2
    if (i mod 2 == 0)
        a = a+2
    else
        b = b*3
end for

```

I solve it like this, first I find the time for executed a then b and the total is the addition, is it right? I'm not sure if I have to do it like this or not, I let $n=\frac{n^2}{2}$ because of the $\bmod 2$ is it right?

$t\_a(n)=\sum\_{j=1}^{n^{2}/2}1=\dfrac{n^{2}}{2}$

$t\_b(n)=\sum\_{j=4}^{n^{2}}1-\dfrac{n^{2}}{2}=n^{2}-\dfrac{n^{2}}{3}-3$

$t(n)=\dfrac{n^{2}}{2}+n^{2}-\dfrac{n^{2}}{3}-3=\Theta (n^{2})$ by the polynomial theorem.

# Answer
> 2 votes
The final result is true. But, you have a fault in your computation, as in each iteration you have at least a comparison. Hence, instead of $\frac{n^2}{2}$, we will have $n^2 - 3$. Anyhow, the final result is the time complexity is $\Theta(n^2)$.

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


# Question
Title: How is CFL-reachability solvable in exponential time and space?
I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. However, I am not able to convince myself with this explanation. If someone could provide an explanation, it would be great.

# Answer
The input for CFL-reachability problem consists of two parts: the grammar and the graph. As far as time complexity should be measured in terms of the input size, we should include both grammar and graph sizes. But in some cases one can think that grammar size is a constant. For example, we do so when working with classical parsing algorithms: we say that LR is linear, CYK is cubic and so on. It is because the classical way is to create a fixed parser for the language $L$ and then apply this parser to different input strings. So, the main question in this case is how the behavior of parser depends on string length. But in CFL-reachability both parts of input are variable. Moreover, in the context of the static code analysis both grammar and graph are produced from code to be analyzed, and sizes of these parts are huge (in the context of graph DB querying graph is huge and grammar is small and this case is similar to programming languages parsing). So, we are interested in combined complexity. And as a result we get that complexity in terms of graph size is cubic (as mentioned in comments) and exponential in terms of grammar size. For more details look at Jelle Hellings. Conjunctive Context-Free Path Queries. So, yes, the combined time complexity of CFL-reachability is exponential.
> 4 votes

# Answer
Please refer to the paper Program Analysis via Graph Reachability by Thomas Reps where he mentions clearly that CF-reachability is solvable in cubic time.

I assume CFL-reachability is defined as follows:

A CFL-reachability problem is where a path is considered to connect two nodes only if the concatenation of the labels on the edges of the path is a word in a particular context-free language (an $L$-path):

Definition 2.1 (from paper above). Let $L$ be a context-free language over alphabet $\Sigma$, and let $G$ be a graph whose edges are labeled with members of $\Sigma$. Each path in $G$ defines a word over $\Sigma$, namely, the word obtained by concatenating, in order, the labels of the edges on the path. A path in $G$ is an $L$-path if its word is a member of $L$.
> 2 votes

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


# Question
Title: regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$
$r\_1=\Lambda+(a+b)^\*b$
$r\_2=(b+aa^\*b)^\*$
$r\_3=b+\\$+aa^\*b+(b+\\$+aa^\*b)(b+aa^\*b)^\*(b+\\$+aa^\*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r\_1$, then i used FSM2Regex which gave me $r\_3$ which i simplified into $r\_2$ using regex simplifier.
now $r\_2$ seems better than $r\_1$. **Should I go with it?** If so, what is lacking in $r\_1$? I can't see the difference between $(a+b)^\*b$ from $r\_1$ and $(aa^\*b)^\*$ from $r\_2$. Is one the subset of other? Are they overlapping or disjoint?

Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's especialy because for some reason that is beyond me, it also draws $\\$$ (null string) transitions. Even $r\_3$ doesn't give back the FA I used to generate it. So my question is : are $r\_1$ and $r\_2$ different? How? what should I go with?

# Answer
Yes, the regular expressions $r\_1=\Lambda+(a+b)^\*b$ and $r\_2=(b+aa^\*b)^\*$ are equivalent. There are several ways of doing this.

1. Just observe that both of them match the empty string and all strings ending with $b$.
2. Convert them to automata and then produce automata for $L(r\_1)\setminus L(r\_2)$ and $L(r\_2)\setminus L(r\_1)$. Minimize both automata and find that they both accept the empty language. (Actually, you'll find that you make a ton of mistakes and at least one of the automata accepts something, and at least one of the minimizations is wrong. But, if you were a computer, this wouldn't be an issue.)
3. Clearly both regular expressions match the empty string, so let's show that they match the same non-empty strings, too. Suppose that $w\in L(r\_2)\setminus\\{\Lambda\\}$. Then we can write $w=w\_1\dots w\_\ell$ where each $w\_i$ is a string that either matches $b$ or $aa^\*b$. In particular, $w\_\ell$ must match one of these things, so the last character of $w\_\ell$ is a $b$, so $w\in L(r\_1)$.

Conversely, suppose that $w\in L(r\_1)\setminus\\{\Lambda\\}$. Write $w=s\_1\dots s\_n$, where each $s\_i\in\\{a,b\\}$. Suppose there are $\ell$ $b$s in $w$ and let these be at positions $p\_1, \dots, p\_\ell$. Because $w\in L(r\_1)$, $p\_\ell=n$ (the last character is $b$). For convenience, let $p\_0=1$. We can now write $w=w\_1\dots w\_\ell$, where $w\_i=s\_{p\_{i-1}+1}\dots s\_{p\_i}$. For each $i\in\\{1, \dots, \ell\\}$, we have $w\_i=a^{p\_i-p\_{p-1}-1}b$, so each $w\_i$ matches either the regular expression $b$ or $aa^\*b$. Therefore, $w$ matches $(b+aa^\*b)^\*= r\_1$.

By the way, a fourth equivalent regular expression is $(a^\*b)^\*$, which you can see by observing that the inner part of $r\_1$ is equivalent to $b+a^+b$, which is $a^\*b$.
> 1 votes

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


# Question
Title: Intuitive proof for a tree with n nodes, has n-1 edges
I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.

# Answer
> 3 votes
You can see a (binary) tree as a directed graph: suppose the root is the "lowest" node and the leaves are the "highest" ones, then say that all the edges are oriented upwards. Then, every node that is not the root will have exactly one edge entering in it, and every edge will be pointing at exactly one node. This means that if you have $n$ nodes, you have to have $n-1$ edges (one per node with the exception of the root).

# Answer
> 1 votes
This is essentially a different perspective on OmG's answer.

The technical rendition is: A tree is contractible (i.e. homotopic to a point). Since the Euler characteristic (the number of vertices minus the number of edges) is a homotopy invariant, any tree has the same Euler characteristic as a point which is $1$ (one vertex minus zero edges).

The non-technical rendition is: If we collapse a leaf into its parent, we lose one edge and one node, so the difference between the number of edges and the number of vertices remains the same. Clearly, we can just keep doing this until we're left with only the root node for which the difference between vertices and edges is $1$ (one vertex and zero edges).

More generally, collapsing two distinct vertices along an edge that joins them is a homotopy, so for any graph at all we could collapse any distinct pair of vertices joined by an edge without changing the Euler characteristic. That means in the above we didn't need to work from leaves to root; we could have collapsed any edge, though that would have led to intermediates that aren't binary trees. It also means that since a loop (one vertex and one edge from that vertex to itself) has Euler characteristic $0$, then any cycle has Euler characteristic $0$.

# Answer
> 0 votes
The intuition is "as the binary tree is a tree and it has a connected component without any isolate node, and we know in a tree $|E| = |V| - 1$, hence the number of edges of the binary tree with the $n$ node is $n - 1$.

---
Tags: graphs, trees, proof-techniques
---