# Question
Title: Algorithm to generate all N-size variations of natural numbers
For a size N\>=1 (an input variable) I need an algorithm to generate all variations (no duplicates allowed) of natural numbers greater than zero.

For N=1, this is trivial:

```
[1], [2], [3], ...

```

For N=2, I think of having rounds with an increasing limit L where the first element starts from 1 to L and the second element is L when the first element not equals L or goes from 1 to to L+1 otherwise:

```
L = 1
  [1,2],
L = 2
  [1,3], [2,1], [2,3],
L = 3
  [1,4], [2,4], [3,1], [3,2], [3,4],
L = 4
  [1,5], [2,5], [3,5], [4,1], [4,2], [4,3], [4,5],
L = 5
  ...

```

Is it possible to scale this algorithm to any N\>2? Like for N=3:

```
[1,2,3], [?,?,?], ...?

```

Or is there a better algorithm to achieve this?

Thanks!

# Answer
> 1 votes
As a first observation, if you can do it for $N=2$, then you can do it for any $N$ using the same process.

Think of the case $N=2$ as "diagonalising" two copies of the infinite list for $N=1$ by just dropping duplicates. Then you can do $N=3$ by "diagonalising" a copy of $N=2$ with a copy of $N=1$. The details are left as an exercise.

However, there's also a way to enumerate all of the sets that lets you do random access.

I'm going to use the natural numbers $\mathbb{N} = \left\\{ 0, 1, \ldots \right\\}$ because the maths works out better, but all you need to do is add one to every element to solve your problem.

Suppose you have a set of natural numbers $X$ with cardinality $N$. Let $x\_1, x\_2, \cdots x\_N$ be the integers in increasing order. Then the index of this set in the lexicographic ordering of *all* sets with this property is:

$$i\_N(X) = \sum\_{1 \le i \le N} { x\_i \choose i }$$

For example, suppose that $N=3$. Then:

$$\begin{eqnarray\*} i\_3\left(\left\\{0, 1, 2\right\\}\right) & = & { 2 \choose 3 } + { 1 \choose 2 } + {0 \choose 1 } = 0\\ i\_3\left(\left\\{0, 1, 3\right\\}\right) & = & { 3 \choose 3 } + { 1 \choose 2 } + {0 \choose 1 } = 1\\ i\_3\left(\left\\{0, 2, 3\right\\}\right) & = & { 3 \choose 3 } + { 2 \choose 2 } + {0 \choose 1 } = 2\\ i\_3\left(\left\\{1, 2, 3\right\\}\right) & = & { 3 \choose 3 } + { 2 \choose 2 } + {1 \choose 1 } = 3\\ i\_3\left(\left\\{0, 1, 4\right\\}\right) & = & { 4 \choose 3 } + { 1 \choose 2 } + {0 \choose 1 } = 4 \end{eqnarray\*}$$

...and so on. If you represent the set as a bit vector, this is known as enumerative coding.

At any rate, this index function can be inverted in a reasonably straightforward way.

Let's suppose you want to find $i\_4^{-1}(85)$. The first step is to find the largest $x$ such that ${x \choose 4 } \le 85$. We find that

$${ 8 \choose 4 } \le 85 \< { 9 \choose 4 }$$

so the highest value in the set is going to be $8$. Then:

$$i\_4^{-1}(85) = \left\\{ 8 \right\\} \cup i\_3^{-1}\left(85 - {8 \choose 4}\right)$$

Using the base case:

$$i\_0^{-1}(0) = \emptyset$$

We get:

$$i\_4^{-1}(85) = \left\\{ 8, 5, 3, 2 \right\\}$$

For more details, see:

* Cover, T., *Enumerative Source Encoding*. IEEE Transactions on Information Theory, Vol IT-19, No 1, Jan 1973.

---
Tags: algorithms, combinatorics, number-theory
---


# Question
Title: Proving Equivalence of Two Regular Expressions
Consider the regular expressions

* $(1+01)^\*(0+\epsilon)$
* $(1^\*011^\*)^\*(0+\epsilon) + 1^\*(0+\epsilon)$,

where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. Intuitively it seems they are equivalent because they seem to generate the languages of strings without two consecutive $0s$.

**a.** Is this correct?
**b.** How it can be proved mathematically?

# Answer
One way to prove that two regular expressions $r\_1,r\_2$ generate the same language is to show both inclusions:

* Show that if $w$ is generated by $r\_1$ then it is generated by $r\_2$.
* Show that if $w$ is generated by $r\_2$ then it is generated by $r\_1$.

Another way is to mechanically convert the regular expressions to NFAs, then to DFAs, then use the product construction to construct a DFA for the symmetric difference of the languages generated by the two regular expressions, then to show that no accepting state is reachable from the initial state.

You are suggesting a third way — show that both regular expressions generate a particular language $L$. You can use the methods above, or other methods, to show separately that each of $r\_1,r\_2$ generate the language $L$.

A fourth way is to use the algebra of regular expressions, some axiomatizations of which are complete for the equational theory of regular expressions (which means that if two regular expressions generate the same language, then this can be proved using the axioms).
> 31 votes

# Answer
If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's `regular_expressions` library

```
import computability.regular_expressions

open regular_expression

abbreviation c0 := char ff
abbreviation c1 := char tt

-- the statement is that the two regular expressions match the same thing
example :
  ((c1 + c0*c1).star*(c0 + 1)).matches
    = ((c1.star*c0*c1*c1.star).star + c1.star*(c0 + 1)).matches :=
begin
  simp, -- this gets you started, and turns it into a statement about languages
  sorry
end

```

Note here that your $0$ is `c0`, your $1$ is `c1`, your $x\*$ is `x.star`, your $\epsilon$ is $1$, and your concatenation is `*`.

To complete this, you have to replace the `sorry` with the rest of the proof!
> 4 votes

# Answer
If you generate a minimal DFA from a regular expression, then you can label each state uniquely with the lexically smallest string that reaches the state.

This makes it very easy to check for isomorphism between two minimal DFAs, which determines if the languages that generated them are equivalent.

If you number the states in label order, and write out a description of the DFA based on that ordering, then the string you produce is a canonical representation of the language.

Not only can you simply compare two such strings to determine if their generating REs are equivalent, but you can also make a database of them and efficiently check to see if a new language matches any one in the database.
> 3 votes

# Answer
The most direct procedural way that I have found to determine whether two regular expressions $R\_0$ and $R\_1$ are equivalent is the following:

1. Convert $R\_0$ and $R\_1$ to NFAs $N\_0$ and $N\_1$.
2. Convert $N\_0$ and $N\_1$ to DFAs $D\_0 = (Q\_0, \Sigma, \delta\_0, q\_0, F\_0)$ and $D\_1 = (Q\_1, \Sigma, \delta\_1, q\_1, F\_1)$.
3. Form a "union" DFA $D = (Q\_0 \cup Q\_1, \Sigma, \delta\_0 \cup \delta\_1, -, F\_0 \cup F\_1)$. The start state doesn't matter (hence the "$-$"). The idea comes from these lecture notes by Ana Bove.
4. Test whether $q\_0$ and $q\_1$ are equivalent using the table-filling algorithm. Details on the table filling algorithm can be found in these lecture notes by Ryan Williams.
> 1 votes

# Answer
It appears it should be possible to show the regular expressions $r\_1=(1+01)^\*$ and $r\_2=(1^\* 011^\*)^\*+1^\*$ generate the same language, by showing that each string generated by $r\_1$ can also be generated by $r\_2$, and conversely. This equality would be preserved when an optional $0$ is concatenated at the end.
> 0 votes

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


# Question
Title: Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?

TLDR: Halting problem is undecidable because it leads to infinite recursion and never stops.

Elaborating:

At the bottom, I have attached an example of how I have seen the proof presented in a few books(1), but to see recursion, I will express the proof in pseudocode:

Assume the existence of a decider H (an Turing machine that can determine if any program accepts or rejects):

```
function H(M: str, w: str) -> boolean:
   # returns true if M accepts w, false if M rejects w.
   result = M(w) # simulate running M on w
   return result

```

We can then build a Turing Machine D that computes the opposite of H:

```
function D(M: str) -> boolean:
   result_h = H(M, M)
   return not result_h

```

BUT if we call D on a description of itself, D(D), it will first call H(D, D) that in turn will call D(D) once again.

This is an infinite recursion that clearly never terminates. Therefore, the proof is invalid and the assumption of H is wrong and therefore H is not computable.

Question:

I find this to be an extremely intuitive explanation of why the problem is undecidable: because the assumption that H exists leads to an algorithm clearly never terminates.

So I was wondering what holes could there be in this argument or is this a solid way of thinking about undecidability?

Thanks!

1 The usual proof goes something like this (Introduction to the Theory of Computation, Third International Edition, Michael Sipser):

# Answer
> 1 votes
$\newcommand{\D}{\langle D \rangle}$

No, your argument does not prove the undecidability of the halting problem.

For one, your pseudocode for $H$ doesn't appear to even attempt to decide the Halting problem. All it does is simulate its arguments and yield the result. That is what a universal Turing machine does, not a halting decider.

Now, if you construct a diagonal machine for a universal Turing machine $U$, then it will go into an infinite loop, because $D(\D)$ simulates $U(\D,\D)$ which simulates $D(\D)$ and so on. That part is correct.

However, this shows that $U$ does not even satisfy the definition of a "decider," which is supposed to always halt on every valid input. $(\D,\D)$ is a valid input on which $U$ does not halt, so it is not a decider at all. If instead you say that the 'valid inputs' are necessarily deciders themselves, so that the simulation $U$ does must terminate, then this instead shows that the diagonal machine is not a decider, and thus not valid input to $U$. But a halting decider is supposed to operate successfully for *every* Turing machine, not just for terminating ones (since the 'halting problem' for halting Turing machines is trivial).

Also, your proposed proof is about a specific $H$. This does not establish that *all* Turing machines fail to decide halting, which is what the undecidability theorem is about. Your argument *does* show that any $H$ that implements a decision procedure for all machines *cannot* be like your pseudocode, because if it simply simulated its arguments there would be a diagonal program on which it didn't halt, and would not be a decider. But a proof needs to show that actual terminating algorithms also don't decide the halting problem, which your argument does nothing to establish.

# Answer
> 0 votes
No, you only gained intuition about why the code `H` *you* wrote is not the halting oracle.

What about all other possible attempts of implementing `H`? (Warning: do *not* try to argue that they too must enter an infinite loop, because that is blatantly false.)

---
Tags: turing-machines, computability, automata, undecidability, halting-problem
---


# Question
Title: If I want to prove that a problem is in NP, can the vertifier use exponential space?
I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate strings of exponential size. Is this allowed?

# Answer
> 0 votes
If your verifier (a Turing machine) runs in polynomial time then it must also use polynomial space since you can write at most one tape cell (or a constant number of tape-cell in case of multi-tape machines) per time-step.

In other words $\mathsf{P} \subseteq \mathsf{PSPACE}$.

---
Tags: np, decision-problem
---


# Question
Title: How to prove that the subset of a language L that is in P is also in P?
Given that $L∈\textrm{P}$, how do we show that an arbitrary subset $L\_{A}$ of $L$ is also in P?

# Answer
You cannot show that, since the claim is false. Let $L = \Sigma^\*$ and let $L\_A \subset \Sigma^\*$ be the language of the halting problem. Clearly $L \in \mathsf{P}$ (a Turing machine that decides $L$ is the one that ignores its input and immediately accepts). However $L\_A$ is well-known to be undecidable (and hence not in $\mathsf{P}$).
> 4 votes

# Answer
By $\textrm{P}$ do you mean the languages that are decidable in polynomial time? If so, I am pretty sure this isn't true. For example, let $L$ be the language of graphs that are 2-edge-connected, and $L\_A$ the language of graphs that contain Hamiltonian cycles. Then $L \in \textrm{P}$ and $L\_A \subseteq L$ but $L\_A \not\in \textrm{P}$, unless $\textrm{P} = \textrm{NP}$.
> 1 votes

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


# Question
Title: Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b\_1$ and $b\_2$ both from part $B$, at most one of them can be matched. The goal is to find the maximum weighted matching which qualifies these constraints.

Is it a famous problem? If yes, what is its name? Do you have any exact or approximation algorithms for it? If you know that it is NP-hard, can you reduce this problem to another famous NP-hard problem?

Generally, I want to know what has been done about this problem by previous computer scientists.

# Answer
> 3 votes
The problem is not approximable in polynomial-time within a factor of $n^{1-\varepsilon}$ for any constant $\varepsilon\>0$, unless $\mathsf{NP} = \mathsf{ZPP}$.

To see this you can reduce from independent set. Let $G$ be of independent-set. Define $H$ as the graph that contains two-vertices $v\_A, v\_B$ for each vertex $v$ of $G$. For each edge $(u,v)$ of $G$, there is a constraint \`\`at most one of $u\_B$ and $v\_B$ can be matched''. All edges of $H$ weigh $1$, and $H$ is bipartite (all vertices $v\_A$ (resp. $v\_B$) belong to $A$ (resp. $B$)).

Notice that $H$ has $2n$ vertices, where $n$ is the number of vertices of $G$, and that $H$ has a constrained matching of weight at least $k$ if and only if $G$ has an independent set of size at least $k$ (the independent set consists of the matched vertices in $B$). The claim follows from the inapproximability of maximum independent-set (i.e., maximum of clique on the complementary graph).

---
Tags: np-hard, weighted-graphs, bipartite-matching, constraint-satisfaction, polynomial-time-reductions
---


# Question
Title: Optimizing findMissingNumber algorithm to O(N)
This problem is from *Cracking the Code Interview*:

> An array A contains all the integers from Oto n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A\[ i \],"which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

I've put together a working solution, the remaining task is to optimize it to O(N) runtime. My solution:

1. Converts the binary number to decimal
2. Checks if the difference between i-1 and i elements \> 1 to find the missing number
3. Converts the decimal back to binary by dividing repeatedly decimal % 2.

Additionally I've attempted to optimize by removing a separate for loop used for step # 2, that loops through the converted numbers.

Are there redundancies in the algo? How can I optimize this further?

const fetchNthBit = (bit: string, n) => {
    if (n <= 0) return 'Invalid index';
    return bit.charAt(bit.length - n);
}

const convertToBinary = (number) => {
    let result = '';
    while (number > 0) { // O(N)
        const remainder = number % 2;
        number = Math.floor(number/2);
        result = remainder + result;
    }

    return result;
}

const findMissingNumber = function(arr) {
    let converted = [];
    let missingNumber = 0;
    // Convert numbers to binary
    arr.forEach((binaryNumber, i) => {
        let binaryString = binaryNumber.toString();
        let nth = 0;
        let nthBaseValue = 0;
        while (nth < binaryString.length) {
            let nthBit = fetchNthBit(binaryString, binaryString.length - nth);
            if (nthBit === '1') {
                nthBaseValue += 2**(binaryString.length - 1 - nth);
            }
            nth++;
        }
        if (nthBaseValue - converted[i - 1] > 1) {
            missingNumber = convertToBinary(nthBaseValue - 1);
            return;
        }
        converted.push(nthBaseValue);
        nth = 0;
        nthBaseValue = 0;
    });

    return missingNumber ? missingNumber : 'No missing number.';
}

console.log('findMissingNumber: ', findMissingNumber([1, 10, 11, 101])); // 100
```

# Answer
Query the least significant bit (LSB) of all the numbers and split them into two sets $E, O$ where $E$ contains the even numbers (the least significant bit is 0) and $O$ contains the odd numbers.

Now xor together all these bits. If the result matches the LSB of $\sum\_{i=0}^n i = \frac{i(i+1)}{2}$ then the missing number must be even (its LSB is 0), and you can apply this algorithm recursively to find the missing number between $0$ and $\lfloor n/2 \rfloor$ among all the numbers on $E$ without their LSBs.

Otherwise the LSB of the missing number is $1$ and you can apply this algorithm recursively on $O$.

The overall time spent is described by the recurrence equation $T(n) = T(\lfloor n/2 \rfloor) + O(n)$ which has solution $T(n)=O(n)$.
> 2 votes

---
Tags: algorithms, optimization, runtime-analysis
---


# Question
Title: Why is the weight matrix diagonal in weighted least squares regression?
I was going through the theory for weighted least-squares fitting and I understood its basic underlying concepts, but I couldn't understand why exactly do we keep the weights as a diagonal matrix during calculations.

This might be a dumb question but I don't have much experience with matrices and I am in the process of using them to solve more real-world problems so any input will be helpful.

# Answer
> 0 votes
$$ \text{Least Squares solves }\quad A \vec x = \vec b \quad\text{ for }\vec x $$ Say you have some matrix $A$ in the above equation and you would like each row to have different weight. Since Least Squares minimizes the squared differences, if you scale one row and its right-hand side up by a big factor, that will be deemed more important.

Now consider how matrix multiplication works on this small example:
$$ W \mathbin{:=} \begin{bmatrix}w\_0&0&0\\0&w\_1&0\\0&0&w\_2\end{bmatrix},\quad A \mathbin{:=} \begin{bmatrix}a\_{00}&a\_{01}&a\_{02}\\a\_{10}&a\_{11}&a\_{12}\\a\_{20}&a\_{21}&a\_{22}\end{bmatrix} $$ If you work through it manually, you'll see that already for the first row of $W$, it makes sense: $$ \text{Weighted Least Squares solves }\quad WA\vec x = W\vec b\quad \text{ for }\vec x\\ W\_0A = \begin{bmatrix} w\_0a\_{00} & w\_0a\_{01} & w\_0a\_{02} \end{bmatrix} $$ Similarly, the other rows all get their weight multiplied to each element in the row. So generally we can say $$ W\_iA = \begin{bmatrix} w\_ia\_{i0} & w\_ia\_{i1} & w\_ia\_{i2} \end{bmatrix} $$

That should answer your question as to why it works. If you also are asking why it would be done in this specific way - well, it just happens to be the way mathematicians tend to think in, allows for some nice notation, and Matrix operations are usually pretty fast compared to loops because they are heavily optimized.

---

#### Addendum: Deriving the Weighted Least Squares Formulation

Related, though not technically asked for: How we get from that equation $A\vec x = \vec b$ to the actual WLS formulation.

$$ WA\vec x = W \vec b\\ A^T WA \vec x = A^T W \vec b\\ (A^T W A)^{-1} A^T W A \vec x = (A^T W A)^{-1} A^T W \vec b $$

Notice that sometimes we need to be careful whether inverses exist. Here, the inverse $(A^T W A)^{-1}$ does exist. Because $W$ is just a square diagonal matrix, so not very relevant to this argument (it's always invertible) and $A^T A$ is always invertible if $A$ has independent columns. This trick allows us to add an inverse into the equation even if $A$ itself might not be invertible.

$$ \require{cancel} \cancel{((A^T W A)^{-1} A^T W A)} \vec x = (A^T W A)^{-1} A^T W \vec b\\ \vec x = (A^T W A)^{-1} A^T W \vec b $$

# Answer
> 0 votes
The weights are stored in a matrix rather than a vector so that the weighting can be expressed as a matrix/vector product.

E.g.

$$\begin{pmatrix}w\_0&0&0\\0&w\_1&0\\0&0&w\_2\end{pmatrix}\begin{pmatrix}c\_0\\c\_1\\c\_2\end{pmatrix}=\begin{pmatrix}w\_0c\_0\\w\_1c\_1\\w\_2c\_2\end{pmatrix}.$$

This is a common trick in linear algebra, they don't use element-wise products between vectors. In implementations, the weights remain stored in a vector.

---
Tags: matrices, linear-algebra, matrix-multiplication
---


# Question
Title: Minimum number of comparisons to find $2$nd smallest element
> Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ **comparisons** in the worst case. (Hint: Also find the smallest element.) \[1\]

I tried but I have no idea how to, e.g. the best I could do is

```
//assume n>=2
//A: array of size n
//returns second smallest in A
//0 indexing in C++

int second_smallest(int*A,int n){
    queue<int> q;//always keep the size to 2 by push & pop. Also it stores indices.
    q.push(1);//2nd smallest
    q.push(0);//smallest
    for(int i=1;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    int i=q.back()+1;//we know for sure A[0],...,A[q.back()-1] are greater than A[q.front()]. And A[q.back()] is the smallest.
    q.push(q.front());//after this line, assume q.back() is 2nd smallest
    q.pop();
    for(;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    return A[q.back()];
}

```

which conducts $(n-1)+(n-2)=2n-3$ **comparisons** in worst case. When input is uniformly distributed over all permutation the average **number of comparisons** is $(n-1)+n-E\[q.back()\]=\frac{3}{2}n-\frac{1}{2}$ where $q.back()$ refers to the one at $(\*)$, and we know $E\[q.back()\]=\frac{1}{n}(1+...+n)=(n-1)/2$.

But this's no where near $n+\lceil\lg n\rceil-2$ so I'm out of idea could someone help?

\[1\] Introduction to Algorithms,MIT

# Answer
> 1 votes
Assume that all elements are distinct (if not, replace each element with a pair $(element, position)$ and perform the comparisons lexicographically) and consider a rooted binary tree $T$ with $n$ leaves in which each vertex has either $0$ or two children and every level, except possibly the last, is completely filled. Arbitrarily associate each leaf of $T$ with a distinct input element.

You can find the minimum by computing, for each interval vertex $v$, the minimum among all the elements associated to the leaves of the subtree of $T$ rooted at $v$. This can be done by performing a postorder visit of $T$: whenever $v$ is visited, let $v\_\ell$ and $v\_r$ be its two children, compare the elements associated with $v\_\ell$ and $v\_r$ and let the minimum among the two be the *winner*; the element associated with $v$ is exactly such winner.

At the end of the visit, the root of the tree will be associated with the minimum element of the input sequence.

Consider now the set $P$ of the vertices that have been associated with the minimum element and notice that they induce a root-to-leaf path in $T$. Let $C(P)$ denote the set of all children of the vertices in $P$. Since the second-smallest element $x$ can only *lose* against the minimum element, there must be a vertex associated with $x$ among those in $C(P) \setminus P$ (and this set contains no vertex associated with the minimum element). Then, you find the second-minimum of the input sequence be looking for the minimum of the elements associated with the vertices in $C(P) \setminus P$.

The overall number of comparisons is given by the sum of 1) the number of comparisons used to find the minimum, and 2) the number of comparisons needed to handle $C(P) \setminus P$. Regarding 1), we perform exactly $1$ comparison for each internal vertex, for a total of $n-1$ comparisons. Regarding 2), we perform $|C(P) \setminus P| - 1$ comparisons, where $|C(P) \setminus P|$ is at most the depth of $T$, i.e., $|C(P) \setminus P| \le \lceil \log n \rceil$. Then: $$ (n-1) + (|C(P) \setminus P|-1) \le (n-1) + (\lceil \log n \rceil - 1) = n + \lceil \log n \rceil - 2. $$

The above is this is just a handy description for the analysis of the number of comparison. You don't actually need to build and traverse the tree $T$. Here is a possible recursive implementation:

```
Input: a non-empty list L of distinct elements
Output: the second-minimum in L
Second-Minimum(L):
    (x, S) = Find-Candidates(L)
    Return the minimum in S

Input: a non-empty list L of distinct elements
Output: a pair (x, S), where x is the minimum in L, and S is a set of candidate second-minimum elements
Find-Candidates(L):
    If |L|==1:
        return (x, {}), where x is the only element in L

    Split L into L' and L'' with | |L'| - |L''| | <= 1
    (x', S') = Find-Candidates(L')
    (x'', S'') = Find-Candidates(L'')

    If x' < x'':
        Return (x', S' U {x''})
    Else:
        Return (x'', S'' U {x'})

```

# Answer
> 0 votes
Based on Steven's great answer, and some modification so that the second minimum is computed "on the fly" (this won't change the number of comparison) below implemented the algorithms in C++ that also prints the tree for visualization

e.g. with input array L = `3,1,5,2,4` the second smallest is `2` and the tree is printed after $90$ degree rotation to the right

```
                4
        2
                2
1
                5
        1
                        1
                1
                        3

```

code:

```
#include <iostream>
#include <stack>
using namespace std;
//declare only
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order);
void print_in_order(stack<int*>&post_order,int depth);

//L is continuous array starting from indices p to r inclusive
//returns Second Minimum ie. smallest loser (second min) to winner (min)
int*Second_Minimum(int*L,int p,int r){
    int*winner=nullptr;
    stack<int*>post_order;
    int*second_minimum=Find_Candidates(L,p,r,winner,post_order);
    print_in_order(post_order,0);
    return second_minimum;
}

//post_order is solely for printing purpose
//returns pointer to second minimum or nullptr if it doesn't exist
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order){
    //a single element must be winner
    if(p==r){
        winner=L+p;
        post_order.push(nullptr);//left child
        post_order.push(nullptr);//right child
        post_order.push(winner);//this node
        return nullptr;//no one lost to the winner
    }
    int q=(p+r)/2; //same as floor((p+r)/2), aka lower median
    int*lt_smallest_loser=Find_Candidates(L,p,q,winner,post_order); //smallest loser to winner in left subtree
    int*lt_winner=winner; //winner from left subtree
    int*rt_smallest_loser=Find_Candidates(L,q+1,r,winner,post_order); //smallest loser to winner in right subtree
    int*rt_winner=winner; //winner from right subtree

    if(*lt_winner<*rt_winner){
        winner=lt_winner;//rt_winner becomes a loser now
        post_order.push(winner);
        if(lt_smallest_loser!=nullptr&&
            *lt_smallest_loser<*rt_winner){
            return lt_smallest_loser;// still the smallest loser
        }else
            return rt_winner;// rt_winner becomes the smallest loser
    }else{
        winner=rt_winner;//lt_winner becomes a loser now
        post_order.push(winner);
        if(rt_smallest_loser!=nullptr&&
            *rt_smallest_loser<*lt_winner){
            return rt_smallest_loser;// still the smallest loser
        }else
            return lt_winner;// lt_winner becomes the smallest loser
    }
}

void print_in_order(stack<int*>&post_order,int depth){
    int*root=post_order.top();
    post_order.pop();
    if(root==nullptr)
        return;
    else{
        //print right
        print_in_order(post_order,depth+1);
        for(int i=0;i<depth;++i)
            cout<<'\t';//print tab
        cout<<*root<<endl;
        //print left
        print_in_order(post_order,depth+1);
    }
}

int main(){
    int L[]{3,1,5,2,4};
    int n=sizeof(L)/sizeof(int);
    int*result=Second_Minimum(L,0,n-1);
    cout<<"2nd smallest: ";
    if(result!=nullptr)
        cout<<*result<<endl;
    else
        cout<<"doesn't exist"<<endl;
}

```

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, statistics
---


# Question
Title: Proving T(n) = 3T(n/9) + n^1/2 using induction
I'm confused on how to prove the below using induction:

T(n) = 3T(n/9) + √n

I have been given the base case T(1) = 1. I know using the master theorem that the time complexity is O(√n log n). However, when trying to find the inductive hypothesis (function form) of the recurrence by substituting k = 0, 1, 2, 3... into T(9^k), I'm not sure how to find the function form.

Thanks!

# Answer
$$\begin{align}T(9^4)&=3T(9^3)+3^4 \\\&=3(3T(9^2)+3^3)+3^4=3^2T(9^2)+2\cdot3^4 \\\&=3^2(3T(9)+3^2)+2\cdot3^4=3^3T(9)+3\cdot3^4 \\\&=3^3(3T(1)+3^1)+3\cdot3^4=3^4T(1)+4\cdot3^4 \end{align}$$

and we can infer

$$T(9^m)=3^m(T(1)+m),$$ which is

$$T(n)=\sqrt n(T(1)+\log\_9(n)).$$

---

**Verification:**

$$\begin{align}\sqrt n(T(1)+\log\_9(n))&=3\sqrt{\frac n9}\left(T(1)+\log\_9\left(\frac n9\right)\right)+\sqrt n \\\&=\sqrt n(T(1)+\log\_9(n))-\sqrt n+\sqrt n\end{align}$$

is indeed an identity.
> 0 votes

# Answer
**Other method:**

We divide both membres by $\sqrt n$:

$$\frac{T(n)}{\sqrt n}=\frac{3T\left(\dfrac n9\right)}{\sqrt n}+1=\frac{T\left(\dfrac n9\right)}{\sqrt{\dfrac n9}}+1.$$

This is of the form

$$S(n)=S\left(\frac n9\right)+1$$ and denotes the number of times you can divide by $9$ before reaching $1$, or $$\log\_9(n)+S(1).$$
> 0 votes

---
Tags: induction
---


title: Empty string in an ambiguous grammar?

text:
# Question
Title: Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:

```
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S

```

So what does B -\> empty string mean/do? Does that mean B could transition to A? And "if", "else", and "null are terminals, then what is the empty string?

# Answer
> 1 votes
In a grammar when a rule transitions to the empty string, that means that the symbol just disappears. For example, here is a possible derivation:

```
A'
A
if A B
if null B
if null

```

Notice that on the last line, `B` is replaced by the empty string -- nothing. It goes away. (We could have instead decided to replace B by `else S`.)

# Answer
> 0 votes
You can eliminate `B` by substituting all its expansions wherever it appears, giving the equivalent grammar

```
A' -> A
A -> if A
A -> if A else S
A -> null

```

---
Tags: regular-languages, context-free, regular-expressions, strings
---


title: Matching 2 sets of items by price

text:
# Question
Title: Matching 2 sets of items by price
I'm trying to solve the following problem in the most efficient way I can find.

I want to trade my items for someone elses items, every item have a price and a value.

I want to maximize the value of the items I trade, so for example:
My items:

> Banana, P: 10, V: 5
> Pen, P: 3, V: 1
> Paper, P: 1, V: 1

Their Items:

> Phone, P: 10, V: 8
> Key, P: 1, V: 2
> Wallet, P: 30, V: 100

You can see that I can trade my Banana and Paper (with value of 6) with Phone and Key (with value of 10)

I can overpay but can not pay less and the amount I overpay is lost.
Currently my solution is to use generate all the possible combinations of my items and try to match the price with knapsack algorithm and check each result.

This is however very not efficient because I can have over 1000 items (both mine and the other person).

Does anyone have a possible solution to this problem? I need it to be efficient but also give me the best solution (best value)

* The items are not infinite and they have a limit.

# Answer
Assume you have a table of items of quantity Q, price P and Value, V and a computed value ratio P/V for each item.

I would use a Successive Approximation Register approach using the most significant item rated by P/V ratio using a product sum that does not exceed the total or consumes all your inventory of that item then repeat down your ranked list by Price/value ratio. Just as SAR is the fastest for ADC's, this would be my optimum solution.

The trade may not be attractive to the other person, since you have offered items with the least value to you, so a practical solution must consider the V/P ratio of your item to the other person, which may be unknown.

Tony EE since 1975.
> 0 votes

# Answer
This problem is polynomially equivalent to the Knapsack problem.

It is quite easy to reduce the Knapsack problem to this problem, where given a list of items $L$ and a budget $k$, one can build the following instance of your problem, where your own list contains exactly one item of value $0$ and price $k$, meanwhile the other list is exactly $L$. Clearly in an optimal solution you have to sell your item and buy as much value as you can from the other list, which corresponds to an optimal solution of the Knapsack problem.

On the other hand, since you only optimize for the value, one can also reduce your problem through a simple observation: You can always sell all the items you have, and then buy some of them back (the ones you shouldn't have sold in the first place). So the resulting instance of the Knapsack problem consists of the union of both lists, and a budget equal to the sum of the prices of the items you have.
> 0 votes

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


# Question
Title: How to identify Dominant terms in big-O notation and understand Time Complexity of an algorithm?
I understand that *Time Complexity is the measure of how an algorithm scales with respect to the input size*.
Let us say an algorithm is having a runtime of O($3^n$) + O($n^{20}$)

In order to identify the Non-Dominant term, I followed my intuition for a sample of values:
$3^n$ = {1, 3, 9, 27, ...} for n={0, 1, 2, ...}
$n^{20}$ = {0, 1, 1048576, 3486784401, ...} for n={0, 1, 2, ...}

I see that **$n^{20}$ scales up more quickly than $3^n$ for all values of n\>=2**
Can I say in this regard that the **Non-Dominant** term is $3^n$?

# Answer
> 2 votes
No, when we talk about dominant terms in big-O notation we talk about asymptotic domination, i.e. how terms scale as $n \to \infty$. To see this you can think about the limit: $$\lim\_{n \to \infty}\frac{f(n)}{g(n)} = C \ .$$

If this value is $C \in \mathbb{R}$, then we have that $f(n)=O(g(n))$ and so the sum $O(f(n))+O(g(n))=O(g(n))$.

If instead, $C=+\infty$, then it's the opposite, i.e. $g(n)=O(f(n))$ and so the sum will be $O(f(n))+O(g(n))=O(f(n))$.

In your case, even if for small values of $n$ it seems that $n^{20}$ grows faster than $3^n$, this is not the case.

Indeed, $\lim\_{n\to \infty} \frac{3^n}{n^{20}} = + \infty $.

You can see it in this way: $3^n=(3^{\log\_3 n})^{n/\log\_3 n}=n^{n/\log\_3 n}$ which grows obviously bigger than $n^{20}$, in particular it surpasses $n^{20}$ as soon as the exponent $\frac{n}{\log\_3 n}$ surpasses $20$.

It it worth to notice that asymptotic behavior isn't everything. In practice, polynomials with large exponents or large multiplicative constants can be bigger than exponentials for values of $n$ from real world applications.

# Answer
> 2 votes
Numerical examples can be misleading.

$$100^{20}=10000000000000000000000000000000000000000, \\3^{100}=515377520732011331036461129765621272702107522001.$$

---

When you consider the ratios $\dfrac{T(n+1)}{T(n)}$, you get

$$\frac{(n+1)^{20}}{n^{20}}=\left(1+\frac1n\right)^{20}\sim1+\frac{20}n\to1$$ and $$\frac{3^{n+1}}{3^n}=3.$$

So in fact the second function grows much faster !

---

Another argument is by taking the $20^{\text{th}}$ roots of both functions, to get

$$n$$

vs.

$$\sqrt\[20\]{3^n}=(\sqrt\[20\]3)^n.$$

The first function is linear and the second exponential.

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


# Question
Title: Time complexity of the fast exponentiation method
I am trying to analyse the time complexity of the fast exponentiation method, which is given as

$$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &\text{if n is odd} \newline 1 &\text{if n=0} \end{cases} $$

I tried to write it as, $$ T(n)=\begin{cases} T(\frac{n}{2}).T(\frac{n}{2}) &\text{if n is even}\newline T(n-1) &\text{if n is odd}\newline 1 &\text{if n=0} \end{cases} $$

I think I am lacking somewhere and so not able write correct recurrence relation here.

Need help to do so.

# Answer
Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the computation model).

Denote the number of multiplications when computing $x^n$ using your algorithm by $S(n)$. Let's consider your cases from bottom to top:

* Calculating $x^n$ for $n = 0$. The answer is $1$, so no multiplications are needed: $S(1) = 0$.
* Calculating $x^n$ for $n$ odd. In this case we first calculate $x^{n-1}$ using the same method, which takes $S(n-1)$ multiplications by definition. Then we multiply the result by $x$, which uses up one multiplication. This gives $S(n) = S(n-1) + 1$ in this case.
* Calculating $x^n$ for $n\>0$ even. In this case we first calculate $x^{n/2}$ using the same method, which takes $S(n/2)$ multiplications by definition. Then we multiply the result by itself, which uses up one multiplication. This gives $S(n) = S(n/2) + 1$ in this case.

In total, we get the following recurrence for the number of multiplications: $$ S(n) = \begin{cases} 0 & n = 0 \\ S(n-1) + 1 & n \text{ odd} \\ S(n/2) + 1 & n\>0 \text{ even} \end{cases} $$ We can improve on the algorithm slightly using the identity $x^1 = x$. This gives the following alternate recurrence: $$ S'(n) = \begin{cases} 0 & n \leq 1 \\ S'(n-1) + 1 & n\>1 \text{ odd} \\ S'(n/2) + 1 & n\>0 \text{ even} \end{cases} $$
> 6 votes

# Answer
You somehow confuse the result of the multiplications and the time they take.

$$x^{n/2}\cdot x^{n/2}$$

does not take $T(\frac n2)\cdot T(\frac n2)$ units of time but $T(\frac n2)+M+T(\frac n2)$ where $M$ denotes the time for a multiplication (assuming they can be done in constant time).

Hence the complete recurrence

$$T(n)=\begin{cases}2T(\frac n2)+M\\T(n-1)+M\\T(1)\end{cases}.$$

We can solve it for the best and worst cases.

**Best:**

$\frac n2$ decreases $n$ faster than $n-1$. So the best case is achieved when $n$ is a power of $2$, let $2^m$. After $m$ applications of the first line, we have

$$T(2^m)=2^mT(1)+(2^{m-1}+2^{m-2}+\cdots 1)M=2^mT(1)+(2^m-1)M.$$

**Worst:**

Occurs when every division leads to an odd number, which is when $n$ is a power of $2$ minus $1$. We easily see that every reduction by one bit takes $2M$ multiplications instead of $1$, leading to a similar formula.
> 0 votes

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


# Question
Title: Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting
The following theorem was proven by R.E. Tarjan in 1984:

> **Theorem (Sequential Access Theorem).** If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time spent is $O(n)$

But if we remove the smallest element one at a time, then does it imply that we sorted the element in $O(n)$ time? Of course not, because then it contradicts the following Theorem.

> Any comparison sort algorithm requires $\Omega(n\lg n)$ comparisons in the worst case.

What was wrong with the way I tried to use the Sequential Access Theorem?

# Answer
> 2 votes
There is nothing wrong in saying that if you access the nodes of a BST (not necessarily a splay tree) in symmetric order in time $O(n)$ then the sequence of the corresponding elements is sorted.

However this alone is not enough to obtain a sorting algorithm that runs in time $O(n)$ since you're disregarding the time needed to construct the tree itself.

In fact, your observation shows that the time spent to build a BST from an unsorted set of elements must be $\Omega(n \log n)$ in the worst case.

---
Tags: data-structures, binary-search-trees, amortized-analysis, splay-trees
---


title: Confusion on RSA attack equation

text:
# Question
Title: Confusion on RSA attack equation
I am reading this paper on RSA attacks and it describes the equation where ed = 1 mod φ(N)

This confuses me because wouldn’t 1 mod of anything (not 1) just always be equal to 1?

# Answer
This is what is known as a modular inverse.

The easiest way to think about this is to think of the multiplication table in modular arithmetic. Let's start with the modulus being a prime number, 5.

$$\begin{array} {}\times{} & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 5 \\ 4 & 0 & 4 & 3 & 2 & 1 \end{array}$$

Every element, apart from zero, has a multiplicative inverse, in the sense for every $x$ there is a $y$ such that $xy = yx = 1$.

Now we'll look at a composite modulus. Let's try 6. $$\begin{array} {}\times{} & 0 & 1 & 2 & 3 & 4 & 5\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3 & 4 & 5\\ 2 & 0 & 2 & 4 & 0 & 2 & 4\\ 3 & 0 & 3 & 0 & 3 & 0 & 3\\ 4 & 0 & 4 & 2 & 0 & 4 & 2\\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{array}$$

Here, only 1 and 5 have a multiplicative inverse. These two are also the numbers that are coprime to 6, and this is not a coincidence.

Intuitively, if $x$ has a factor $f$ in common with the modulus $M$, then any multiple of $x$ is a multiple of $f$ modulo $M$, so it cannot be 1. What may not be obvious is that the converse also holds: if $x$ is coprime to $M$, then $x$ has an inverse modulo $M$.

To say that $xy$ is congruent to $1$ modulo $M$ is to say that there exists an integer $k$ such that:

$$xy + Mk = 1$$

The problem of finding a suitable $y$ is, therefore, equivalent to solving the above linear Diophantine equation. This always has a solution if $\gcd(x,M) = 1$ (i.e. $x$ and $M$ are coprime), and it can be found with the extended Euclidean algorithm.
> 2 votes

---
Tags: encryption
---


title: Can parser split tokens?

text:
# Question
Title: Can parser split tokens?
Is it valid to have the token split up, in a parser; as shown in the below grammar:

```
expr   -> expr addop term
term   -> term mulop factor
factor -> factor digit | digit
addop  -> + | -
mulop  -> * | /
digit  -> 0 | 1 | ... | 9

```

Say, for the arithmetic expression:

```
12 + 7 * 45 / 9 - 6 + 5

```

for the input: 12, the split of token 12 occurs, in two parts; with first reading digit 1, then 2.

# Answer
> 0 votes
~~The arithmetic expression you provided `12 + 7 * 45 / 9 - 6 + 5` will cause the parser to return syntax error because `12` is not part of the language (same problem for `45`...). Specifically, it is not a token and will be recognized as the symbol `1` followed by `2` that is obviously illegal. To manage numbers in the intuitive way you should define a lexer accepting numbers and refer to its language, that is `[0-9+]`.~~

It is possible to define the language this way, however it is not a best practice and that will have two implications:

1. in case blanks are ignored it is perfectly possible to write $1\underline{ }2 * 3\underline{ }4$ that is equivalent to $12 * 34$. This is generally not what the programmer would expect.
2. you need to carry out integer computation in semantic actions attached to your productions rather than in the lexer; this is possibly a maintainance problem because you are mixing two components that should be separated.

---
Tags: compilers
---


# Question
Title: Correct way to derive parse trees, for a given input, to show ambiguity
Is it correct to state that the below grammar can handle the expression: a - b * c, by the below two different parse trees.

Grammar:

```
Expression = Expression "-"
Expression | Expression "*"
Expression | Factor
Factor = "a" | "b" | "c"

```

Parse tree #1:

```
Expression -> Expression - Expression
=> Factor - Expression
=> a - Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c

```

Parse tree #2:

```
Expression -> Expression * Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c

```

I feel that the second derivation above is completely wrong, as not considers the left-to-right scan of the input string. The decision should have been based on the lookahead symbol only.

*If possible show by a C language code snippet, how the implementation of the second derivation, is correct, as the book titled: Compliers and Compiler Generators An Introduction With C++, by Patrick D. Terry, shows the above example, in Section 6.4, page #131*

For me, the ambiguous grammar can only be shown by the below second derivation:

Parse tree #2:

```
Expression -> Expression - Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Factor * Expression
=> a - b * Expression
=> a - b * Factor
=> a - b * c

```

# Answer
> 0 votes
You provided a grammar of the shape:

* $E \rightarrow E - E$
* $E \rightarrow E * E$
* $E \rightarrow F$
* $F \rightarrow a | b | c$

The second last production has $E$ on its LHS; it is a unit production that can be removed to produce the grammar:

* $E \rightarrow E - E$
* $E \rightarrow E * E$
* $E \rightarrow a | b | c$

This second grammar is ambiguous and this fact can be shown exhibiting two distinct derivation trees for the same string (they need to be both leftmost or rightmost though.) Since the removal of the production $E\rightarrow F$ preserves the language the initial grammar must be ambiguous as well.

Both derivations are correct since the grammar does nothing to prevent them to be generated: the fact you can show the existence of the derivation tree is sufficient to tell the string belongs to the language generated by the grammar.

---
Tags: compilers
---


title: How to create a DFA with memory

text:
# Question
Title: How to create a DFA with memory
How can I create a DFA that has memory such that I could write a rule for this DFA that states `transition to state B after transitioning from state A at some point (doesn't matter when. Could have been the last state or 5 states ago)`.

I'm not even sure if creating a DFA like this is possible, hence why I'm asking here. If it's not possible, is there any other state transition algorithm I can use

# Answer
By *rule*, I assume you mean a transition.

You can do this by first replacing the original DFA, $M$, with a new one that records whether or not an $a$ has ever been read, as follows:

* for each state $q$ of $M$, it has two states:
    + $q\_b$ ("$q$ before $a$")
    + $q\_a$ ("$q$ after $a$")
* for each transition $(q, c, r)$ of $M$, it has two transitions:
    + $(q\_b, c, r\_a)$ if $c = a$; $(q\_b, c, r\_b)$ if $c \not= a$
    + $(q\_a, c, r\_a)$
* its initial state is $s\_b$
* its final states are $\cup\_{q \in F} \\{ q\_a,q\_b \\}$

Now you can create a transition that only exists for $q$ after $a$ has been read by creating it for $q\_a$.
> 0 votes

# Answer
I am confused by some of your terminology. By "DFA table" do you mean the DFA's transition function? Also you want a rule of the form "Accept state $B$ after accepting state $A$" but an accepting state of a DFA is (basically) a terminating state. Do you mean that $B$ should be an accepting state only after visiting $A$?

This is doable. All you need to do is create a second, duplicate copy of your DFA. Then $B$ in the original is not an accepting state while the copy of $B$ is. Finally, the only way to transition from the original to the copy is at state $A$ (if you would normally transition to $C$ when you receive input $x$ while at $A$, you now transition to the copy of $A$).
> 0 votes

# Answer
Though the meaning of "transition to state B after transitioning from state A" is quite unclear, you don't need any special device to memorize if the state A has been reached or not. It suffices to define a set of states from which you can reach A, and another set of states that includes A and such that no transition returns to the first set. What you put in these sets is entirely up to you.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: A variant of hitting set problem? Is this also a NP-hard problem?
Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\\{S\_1,S\_2,S\_3,S\_4,S\_5,S\_6\\}=\\{\\{1, 2, 3\\}, \\{1, 3, 4\\}, \\{1, 4, 5\\}, \\{1, 2, 5\\}, \\{2, 3\\}, \\{4, 5\\}\\}$,
it is easy to know that a minimum hitting set is $\\{2,4\\}$.

I am thinking what this "hitting set" problem would be if the set $S$ is also a collection of sets.
For instance, given
$S\_1=\\{\\{1,2,3\\},\\{3,4\\},\\{1,2\\}\\}$,
$S\_2=\\{\\{3\\},\\{3,5\\},\\{1,3\\}\\}$,
$S\_3=\\{\\{2,5\\},\\{4\\},\\{1,5\\},\\{1,10,6,7\\}\\}$,
and in this new problem, the "hitting set $H$" should be a set that:
1. For each $S\_i$, there must exist an element $s$ which is a subset of $H$;
2. The cardinality of $H$ is as small as possible.

Therefore, we can see that $\\{3,4\\}$ is a solution.

It looks like I am trying to select an element from each set where each is a collection of sets, and then the cardinality of the union of these selected elements is as small as possible.

Does anyone have an idea to solve this problem? Do you think it is a variant of hitting set problem? Is it an NP-hard problem?

# Answer
> 1 votes
The special case of your variant where every set $S\_i$ contains only single-element sets are exactly the standard hitting set problem, so this variant is at least harder than the standard hitting set problem, thus is NP-hard.

# Answer
> 0 votes
I think this paper will help you: https://link.springer.com/article/10.1007/s00453-022-00964-6

---
Tags: algorithms, complexity-theory, np-complete, np-hard, vertex-cover
---


# Question
Title: Is minimum interval hitting problem NP-HARD?
Consider this problem:

We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in interval $\[i,j\]$ should be marked such that $i \leq j$ and $k \leq j-i+1$. Is this problem NP-HARD? If yes, please prove it. If no, please provide a polynomial time algorithm for it. If you know any papers about it, please inform me.

# Answer
> 1 votes
It should be solvable in Polynomial time (in the number of constraints + $\max j$) by MaxFlow algorithms. Consider first this link explaining how you can determine the minimum amount of flow on a network with edge demands. Then build the following network:

Start with a source node $s$, then create a set $J$ of $\max j$ nodes that $s$ points to with edges of capacity $1$ and no demand. Next, create a set $C$ with $\\# \text{constraints}$ nodes and for every constraint node in $C$ create an edge of capacity $1$ and demand $0$ from every node in $J$ that's in the range of the constraint toward the constraint node. Then, create a target node $t$ and connect each constraint node in $C$ with an edge of infinite capacity but demand $k$.

It should be clear by construction that the minimal amount of flow satisfying all capacity and demands is the answer to your problem.

---
Tags: algorithms, np-complete, np-hard, constraint-satisfaction, intervals
---


# Question
Title: Sum of unique elements in all sub-arrays of an array
Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \\{1, 2, 1, 3\\}$ the desired sum is $18$.

Subarrays:

```
{1} - 1 unique element
{2} - 1
{1} - 1
{3} - 1
{1, 2} - 2
{2, 1} - 2
{1, 3} - 2
{1, 2, 1} - 2
{2, 1, 3} - 3
{1, 2, 1, 3} - 3

```

I have a working solution which sums the unique elements for all sub-arrays starting at index $0$, then repeats that process at index $1$, etc. I have noticed that for an array of size $n$ consisting of only unique elements, the sum I desire can be found by summing $i(i + 1) / 2$ from $i = 1$ to $n$, but I haven't been able to extend that to cases where there are non-unique elements. I thought I could use that fact on each sub-array, but my control logic becomes unwieldy. I've spent considerable time trying to devise a solution better than $O(n^2)$ to no avail. Is there one?

Secondary question: if there is no better solution, are there any general guidelines or hints to recognize that fact?

# Answer
> 0 votes
**Hint**: Use an extra $O(n)$-spaced array of pointer to the last (biggest) index of each distinct value. Then, this array is very helpful when you do your above algorithm.

Lastly, we should have an $O(n)$ algorithm.

# Answer
> 1 votes
It's easy to do this using the technique of finding individual contribution of each element.

Consider a subarray, each unique element contributes 1 to answer, but if there are multiple occurences of it, only one will contribute to answer.

so rather than finding distinct elements for each subarray, we take an element and count all subarrays where it will contribute an answer to.

An element should only be considered once per subarray, so we need to define which element must be counted, by counting only first occurrence of each distinct element we can avoid overcounting.

We take an element, and count all subarrays where it is first occurrence of it's value, ie. subarrays which start after previous occurrence of current value, then current element will be first occurrence in this subarray.

Algorithm is as follows:

1. store last occurrence of each element, initially it's -1
2. traverse array from left to right
3. contribution of this element will be $ (i - last\[arr\[i\]\]) \times (n - i) $, add to answer
4. update last occurrence index of current value

It will work in $ O(N) $ time and $ O(N) $ space complexity.

Here's implementation along with test generator in Python.

https://ideone.com/vNIJMG

# Answer
> 0 votes
Let $a\_1,\ldots,a\_m$ be the distinct values. Now consider the positions of $a\_i$'s in $A$. Assume the number of $a\_i$'s is $b\_i$ and the positions are as follows:

```
(x_{i0} non-a_i's) a_i (x_{i1} non-a_i's) a_i ... a_i (x_{ib_i} non-a_i's)

```

In your example $A=\\{1,2,1,3\\}$, when considering the value $a\_1=1$, we have $x\_{10}=0,x\_{11}=1,x\_{12}=1$ because the positions of $1$s are like `1 * 1 *`: there is $0$ element before the first $1$, $1$ element between the first $1$ and the second $1$, and $1$ element after the second $1$.

Then there are \begin{align} &\sum\_{j=0}^{b\_i} \frac{x\_{ij}(x\_{ij}+1)}{2}\\ =\ &\frac{1}{2}\sum\_{j=0}^{b\_i}x\_{ij}^2+\frac{1}{2}\sum\_{j=0}^{b\_i}x\_{ij}\\ =\ &\frac{1}{2}\sum\_{j=0}^{b\_i}x\_{ij}^2+\frac{1}{2}(n-b\_i) \end{align} subarrays that do not contain $a\_i$. Note there are $n(n+1)/2$ subarrays in total, so the final result we want is \begin{align} &\sum\_{i=1}^m\left(\frac{n(n+1)}{2}-\frac{1}{2}\sum\_{j=0}^{b\_i}x\_{ij}^2-\frac{1}{2}(n-b\_i)\right)\\ =\ &\frac{1}{2}\left(mn^2+n-\sum\_{i=1}^m\sum\_{j=0}^{b\_i}x\_{ij}^2\right). \end{align}

To calculate $\sum\_{i=1}^m\sum\_{j=0}^{b\_i}x\_{ij}^2$, you can scan the array and maintain a lookup table that, for each distinct value, keeps the position of the last element with this value. With this table, when the $(j+1)$-th $a\_i$ is scanned, you can compute $x\_{ij}$ easily. This leads us to an $O(n\log n)$ solution (or $O(n)$ in average if you use a good hash table to implement the lookup table).

# Answer
> 0 votes
If the maximum number $k$ is not too high, a Counting Sort based solution can be used;

In the first step, we count the number of elements into the array $C$ by

```
for j = 1 to length(A)
    C[A[j]] = C[A[j]]+1

```

now the array contains all the information we need to sum;

```
sum = 0;
for j = 1 to k
    if C[i] > 1
         sum =  C[i] * i

```

**Complexity**:

$\mathcal{O}(n)$ additions (increment) for the counting step

$\mathcal{O}(n)$ additions for the summation step

$\mathcal{O}(n)$ multiplications for the summation step

result $\mathcal{O}(n)$.

**Note**: indeed the multiplications are not necessary since we will have at most $n-1$ addition.

---
Tags: algorithms, combinatorics, arrays, counting, substrings
---


# Question
Title: Could there be a computer or components based on a non-classical logic?
Since circuits and processors are heavily influenced and designed based upon boolean logic, which is itself a subset of propositional logic, could there be different interpretations of hardware or software based on another logic, like linear temporal logic or a description logic?

I mean, for example, could it be possible to apply the concepts of a different logic to come up with a new kind of compiler or digital circuits or even a new processor architecture based on a non-classical logic?

# Answer
Computers make heavy use of sequential logic (as opposed to combinatorial). Isn't this an instance of temporal logic ?

One might think of implementing fuzzy logic in hardware, which would be reminiscent of analog computers. But I can't see the benefit.

Tri-state logic computers have been tried. And abandoned due to the excessive complexity.

Nothing beats good old zeroes and ones. I did not notice that any non-classical logic became pervasive in any domain.
> 0 votes

---
Tags: computer-architecture, logic, compilers, software-engineering
---


title: Difference between CRC and Hamming Code

text:
# Question
Title: Difference between CRC and Hamming Code
I am a bit confused on the difference between Cyclic Redundancy Check and Hamming Code. Both add a check value attached based on the some arithmetic operation of the bits in the message being transmitted. For Hamming, it can be either odd or even parity bits added at the end of a message and for CRC, it's the remainder of a polynomial division of their contents.

However, CRC and Hamming are referred to as fundamentally different ideas. Can someone please elaborate on why this is?

Also why is the CRC compared with the FCS(Frame check sequence) to see if the received message is with or without error? Why not just use the FCS from the beginning? (I might be totally flawed in my understanding by asking this question, please correct me.)

# Answer
* CRC is conceived as the remainder of a polynomial division. It is efficient for detecting errors, when the calculated remainder does not match. Depending on the CRC size, it can detect bursts of errors (10 bits zeroed, for example), which is great for checking communications.

The "FCS" term is used sometimes for some transformed version of the CRC (Ethernet for example) : The purpose is to apply the CRC algorithm to both the data and its FCS to cancel the remainder value and get a constant (just like even parity is ensuring an even number of "1" bits, including the parity bit).

* Hamming codes are both detection and correction codes. Adding the Hamming code bits, you ensure some distance (as the number of differing bits) between valid codes. For example, with 3 bits distance, you can correct any 1 bit error **OR** detect any 2 bit error.

Reduced to a single check bit, Hamming codes and CRC are identical (x+1 polynomial) to parity.
> 2 votes

# Answer
Both CRC and the Hamming code are binary linear codes. One significant difference is that the Hamming code only works on data of some fixed size (depending on the Hamming code used), whereas CRC is a convolutional code which works for data of any size.

So, are CRC and the Hamming code *fundamentally different ideas*? This is a philosophical rather than a technical question, and so has no definite answer. It could also depend on your point of view. From far away, both are binary linear codes. From up close, there are some crucial differences.
> 2 votes

# Answer
One big difference is hamming codes can only correct 1-bit errors and detect 2-bit errors with an additional parity bit. CRCs on the other hand can detect an arbitary number of bit errors with high reliability even with a relatively short code.

Hamming codes require a minimum number of parity bits based on the data length. CRCs can have any arbitary number of bits regardless of the data length.

An 8-bit CRC can't guarantee the detection of more than 8-bits of error. However, it can detect more than 8-bits of error with a statistical probablity of 255/256. i.e. there is only a 0.4% chance that an 8-bit CRC will fail to detect any arbitrary number of errors greater than 8-bits.

A 32-bit CRC is even better, it can detect up to 32-bits of error, but for more than 32-bits of error there is only a 1 in 4 billion chance that it will fail to detect any number of bit errors.

Hamming codes on the other hand can only deal with 1-bit correction and 2-bit detection (with additional parity bit).

Because error correction requires not just detecting an error but identifying the exact bit that is wrong, longer code words are requried.

Side note, hamming codes with an additional parity bit can detect 3-bit errors when not using error correction, but hamming codes are pointless if your not using the error correction.
> 0 votes

---
Tags: communication-protocols, error-correcting-codes, crc
---


# Question
Title: Find combination of elements, one element from each list, whose average is the closest to a target number
**Problem:**

There are L lists of positive integers, say L\_0, L\_1, L\_2 ... L\_|L|-1.

The lists have equal length.

There is a target number T.

Find what is the combination of elements, one element from each list, whose average is the closest to T.

**Example:**

```
L_0 = [10, 20, 15]
L_1 = [9000, 400, 550]
L_2 = [1, 2, 3]
L_3 = [700, 500, 1000]
T = 3000

```

The combination of elements, one element from each list, whose average is the closest to 3000 is: 20, 9000, 3, 1000.

**Question:**

Is there a better way to solve this problem than just bruteforce (testing all possible combinations)?

# Answer
The problem is NP-Hard by a reduction from subset sum. Let $X = \\{x\_1, x\_2, \dots, x\_n\\}$ be a set of integers and let $t$ be an integer. The subset-sum problem asks whether there is a subset $S \subseteq X$ such that $\sum\_{x \in S} x = t$.

To reduce to your problem pick $L=n$, $L\_i = \[0, x\_i\]$, and $T = \frac{T}{n}$. There is a solution to the subset sum instance if and only if there is a way to choose an item from each list such that their average is exactly $T$.

If you are willing to settle for a pseudopolynomial-time algorithm then you can use dynamic programming. Assume $T \ge 1$ (otherwise the solution is trivial). Let $OPT\[t,ji\]$ be true ($\top$) if there is a way to choose one element from each of $L\_1, \dots, L\_i$ so that the sum of the chosen elements is $t$, and false ($\bot$) otherwise.

Then, $OPT\[t,0\] = \top$ if and only if $t=0$. For $i = 1 \dots, n$ and $t=1,\dots, \lceil nT \rceil$: $$ OPT\[t,i\] = \bigvee\_{x \in L\_i} OPT\[t-x, i-1\] $$

You can compute all $OPT\[t,i\]$ in time $O(n^2T)$. Then the absolute difference between the average best choice of elements and $T$ is: $$ \min\_{\substack{t=0, \dots, \lceil nT \rceil \\ OPT\[t,n\]=\top} } \left| \frac{t}{n} - T \right|. $$ The actual choice of elements can be found with standard techniques (e.g., whenever $OPT\[i,t\]=\top$ keep track of an element $x \in L\_i$ such that $OPT\[t-x, i-1\] = \top$ and trace back the optimal choices from $OPT\[t^\*, n\]$, where $t^\*$ is a value of $t$ that attains the above minimum).
> 1 votes

---
Tags: algorithms
---


# Question
Title: For each of the following languages, give a regular expression over {a, b}
$\\{a^{2n}b^{n+k+1}a^k ∈ \\{a, b\\}^∗ \mid n \ge 0, k \ge 0\\}$

# Answer
> 0 votes
$L = \\{ a^{2n} b^{n+k+1} a^k \mid n,k \ge 0\\}$ is not a regular language.

Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $b^{p} a^{p-1} \in L$. By the pumping lemma there is some positive integer $i \le p$ such that, for every $h \ge 0$: $$b^{p-i} b^{hi} a^{p-1} \in L.$$ Choosing $h=0$ we obtain: $$b^{p-i} a^{p-1} \in L,$$ which provides the sought contradiction.

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


# Question
Title: Why are the two farthest points vertices of the Convex Hull?
I read that in a 2D space, the two points farthest away must be in the convex hull (CH).

Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point that is outside the convex hull (contradiction). I know that a vertex of CH has two adjacent edges that converge at that point, which is of further distance from any other vertex or point within CH, than the non-vertices beside it. What I mean is shown in the image below: a vertex (p) with two adjacent edges,

**Problem is**, I don't see how I can prove this more formally. I am looking for a more concrete proof.

Thank you in advance.

# Answer
Let $p,q$ be two points in your set of points. The point $p$ can be represented as some convex combination $\sum\_i \alpha\_i p\_i$ of points on the convex hull. The triangle inequality gives $$ \\|p - q\\| = \left\\| \sum\_i \alpha\_i (p\_i - q) \right\\| \leq \sum\_i \alpha\_i \\|p\_i - q\\| \leq \max\_i \\|p\_i - q\\|, $$ where both inequalities used $\alpha\_i \geq 0$ and the second also $\sum\_i \alpha\_i = 1$. We conclude that $p$ can be replaced by some point on the convex hull. Similarly, having replaced $p$ by a point on the convex hull, we can replace $q$ by a point on the convex hull.
> 3 votes

# Answer
Actually, the farthest point in *any* direction is on the convex hull. Actually, this applies much more generally. (I think probably for any closed and bounded set, but my real analysis is a little rusty.) Let $P$ be a simple closed polygon in the plane. Then $P$ partitions the plane into 3 regions: the interior of $I$ of $P$, the exterior $E$ of $P$, and the boundary $P$ itself. (Bonus reading: see the the Jordan Curve Theorem.) Without loss of generality, we assume that the direction is the positive $x$ axis (just rotate your coordinate system).

Let $p$ be a point in $I \cup P$. If $p$ is not on the boundary $P$, then there exists another point $q$ in $I \cup P$ near $p$ with a larger $x$ coordinate, and so $p$ is not the point in $I \cup P$ with maximum $x$ coordinate. The contrapositive is that the point in $I \cup P$ with maximum $x$ coordinate is on the boundary $P$.
> 2 votes

# Answer
I'm late for the party, but anyway... Let $p$ and $q$ be two points, such that the distance $d$ between them is maximum over all the pairs of points in the given point set. All the *other* points must be inside the **intersection of two disks** with radius $d$ \- one disk with center in the point $p$ and another disk with center in the point $q$. This intersection looks like a *curvilinear rhombus* with diagonal $(p, q)$ and circular sides with radius $d$.  Now we'll use the observation from the @Joe answer - *the farthest point in any direction belongs to the convex hull*. In our case this direction is defined by the line, passing through points $p$ and $q$, and these two points are obviously farthest along this direction.
> 0 votes

---
Tags: algorithms, computational-geometry
---


title: How does the Stockham FFT work?

text:
# Question
Title: How does the Stockham FFT work?
I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously confusing me.

This paper describes the use of the Stockham FFT on the GPU. It contains the following diagram:

I understand how to calculate the discrete fourier transform for any individual point, but I'm confused how exactly the Stockham FFT proceeds. My understanding was that the FFT in general divides the input into odd and even data points, and then recursively processes these. But the diagram I added above looks reversed to me. It starts by dividing the input into the smallest segments and then adds up to larger ones, I would have expected this to work exactly the other way around.

How exactly does the divide-and-conquer part of the Stockham FFT work?

# Answer
> 1 votes
Both algorithms are DIT, but the main difference is in memory access patern.
Cooley-Tukey - the most popular form of transformation from DFT to FFT comes from cache awareness, which is optimal for CPU pipeline.
Cooley-Tukey in first phase reverses bit order while Stockham changes order at each stage.
This is observable if you take look at edges - once you have half of the data it stays in place for Cooley-Tukey but moves for Stockham.

For CPU Stockham makes cache mispredictions while Cooley-Tukey makes thread serialization for GPU.

FFT \- look at BFS vs DFS strategy.

FFT stage decomposition \- very nice pdf showing butterfly explicitly for different FFT implementations.

# Answer
> 0 votes
There are two variants of FFT: Decimation in Time (DIT) and Decimation in Frequency (DIF). What you describe is DIT, whereas the diagram shows DIF. The only difference is the order in which the bits are processed – LSB to MSB in DIT, and MSB to LSB in DIF.

There are many online resources describing this – see for example these slides.

# Answer
> 0 votes
I could not find a good source on the Stockham FFT either. So here is my attempt of a comprehensive answer. Disclaimer: I did not track down the original source of the Stockham FFT. Most of my information comes from the following **non-encrypted** japanese website, *so make sure You at least **use a script blocker** if You visit*:

```
http://wwwa.pikara.ne.jp/okojisan/otfft-en/stockham1.html

```

# Stockham vs. Cooley-Tukey

To unterstand the Stockham FFT, let's compare it to Cooley-Tukey, looking at very simple implementations of both in the Scala programming language, using Spire for the complex numbers. Here's the Stockham FFT:

```
import spire.implicits.*
import spire.math.Complex
import spire.math.Complex.rootOfUnity

def fft_stockham( u: Array[Complex[Double]] ): Array[Complex[Double]] =

  require(Integer.bitCount(u.length) == 1)
  val v = u.clone

  def fft( off: Int, n: Int ): Unit =

    if n <= 1 then return;

    val half = n / 2
    val  mid = off + half

    for i <- 0 until half do
      val x = v(off + i)
      val y = v(mid + i)
      v(off + i) =  x+y
      v(mid + i) = (x-y) * Complex.rootOfUnity[Double](n,-i)
    end for

    fft(off,half)
    fft(mid,half)

  end fft

  fft(0,v.length)
  return bitReversalPermutation(v)

end fft_stockham

```

And here's the Cooley-Tukey FFT:

```
def fft_cooleyTukey( u: Array[Complex[Double]] ): Array[Complex[Double]] =

  require(Integer.bitCount(u.length) == 1)
  val v = bitReversalPermutation(u)

  def fft( off: Int, n: Int ): Unit =

    if n <= 1 then return;

    val half = n / 2
    val  mid = off + half

    fft(off,half)
    fft(mid,half)

    for i <- 0 until half do
      val x = v(off + i)
      val y = v(mid + i) * Complex.rootOfUnity[Double](n,-i)
      v(off + i) = x+y
      v(mid + i) = x-y
    end for

  end fft

  fft(0,v.length)
  return v

end fft_cooleyTukey

```

For completeness' sake, here's a simple implementation of the Bit-reversal permutation:

```
def bitReversalPermutation( u: Array[Complex[Double]] ): Array[Complex[Double]] =
  require( Integer.bitCount(u.length) == 1 )
  val s = 1 + Integer.numberOfLeadingZeros(u.length)
  return Array.tabulate(u.length)( i => u(Integer.reverse(i<<s)) )
end bitReversalPermutation

```

Note that there are endless variants of each algorithm:

* stackless implementations
* implementations that perform bit-reversal permutation during recursion
* implementations that use pre-computed roots
* ...

The simplified variants however are particularly well-suited for comparison. You can easily see two characteristic differences between Stockham and Cooley-Tukey:

* Stockham uses a top-down approach, first modifying the array and then calling FFT recursively. Cooley-Tukey uses a bottom-up approach, first applying FFT recursively and then modifying the array.
* Stockham applies bit-reversal permutation at the very end, whereas Cooley-Tukey applies it at the very beginning.

Other than that, You can also see that both implementations are *incredibly similar*. For that reason, I would tend to disagree with anyone who claims that one algorithm is inherently more efficient than the other. They are just to similar for that to be true. Put the same optimization effort into either one of them and You will very likely end up with the same performance.

# Stockham Use Cases

If both algorithms are so similar, why is the Stockham FFT even a thing? Why not always use Cooley-Tukey? One very good reason is the difference in where the bit-reversal permutation takes place. Let's say You want to compute the positive wrapped convolution (PWC) of two vectors $u$ and $v$ of the same power-of-2 length. The PWC is an important building block of fast polynomial and large integer multiplication and division. We can use the FFT to compute it:

$$ \operatorname{pwc}\left(u,v\right) = \operatorname{ifft}\left( \operatorname{fft}\left(u\right) \circ \operatorname{fft}\left(v\right) \right) $$

Where $\circ$ is the element-wise product, which is agnostic to (bit-reversal) permutation in the sense that:

$$ \operatorname{bitReverse}\left(\operatorname{bitReverse}\left(u\right) \circ \operatorname{bitReverse}\left(v\right) \right) = u \circ v $$

This means we can use Stockham for the FFT, Cooley-Tukey for the IFFT, drop the bit-reversal permutation from both and still get the correct result for the convolution.

Bit-reversal permutation can be implemented as an $\mathcal{O}(n)$ operation. It should be negligible compared to the $\mathcal{O}\left(n \log{n}\right)$ operations of the FFT, but due to the pseudo-random nature of bit-reverse indices, it produces many cache-misses, even on modern CPUs. In my experience it can make up 5-10% of the time of a vectorized, optimized FFT implementation, even for large inputs.

# Theory behind Stockham

If You've made it this far, or skipped to this part, You must be *really* interested in the math behind the Stockham FFT. So here is my best attempt to explain it. Let's say we have a polynomial $P$ defined by its coefficient vector $p = \[p\_0, p\_1, \dots, p\_{n-1} \]$ where $n$ is the number of coefficients and also a power of 2.

$$ P\left(x\right) = p\_0 + p\_1 x + p\_2 x^2 + \dots + p\_{n-1} x^{n-1} $$

Applying the FFT to $p$ is equivalent to evaluating $P$ at the first $n$ powers (starting at zero) of the $n$-th root of unity $\omega\_n$:

$$ \operatorname{fft}(p) = \left\[P\left(1\right), P\left(\omega\_n\right), P\left(\omega\_n^2\right), \dots, P\left(\omega\_n^{n-1}\right)\right\] $$

To split the FFT into two smaller FFT problems, let's look at the even index (starting at 0) and odd index entries of $\operatorname{fft}(p)$ separately.

## Even Indices

$$ k \in \left\\{0, 1, 2, \dots, \frac{n}{2}-1\right\\} $$

$$ P(\omega\_n^{2k}) = p\_0 + p\_1 \omega\_n^{2k} + p\_2 \omega\_n^{2k \cdot 2} + p\_3 \omega\_n^{2k \cdot 3} + \dots + \omega\_n^{2k \frac{n}{2}} \left( p\_{\frac{n}{2}} + p\_{\frac{n}{2}+1} \omega\_n^{2k} + p\_{\frac{n}{2}+2} \omega\_n^{2k \cdot 2} + p\_{\frac{n}{2}+3} \omega\_n^{2k \cdot 3} + \dots \right) $$

Due to the definition of the principal $n$-th root of unity we have:

$$ \omega\_n^{2k \frac{n}{2}} = \left(\omega\_n^n\right)^k = 1 $$ $$ \omega\_n^{2k} = \left(\omega\_n^2\right)^k = \left(\omega\_{\frac{n}{2}}\right)^k $$

Where $\omega\_{\frac{n}{2}}$ is the $\frac{n}{2}$-th root of unity. This allows us to simplify the even index FFT components further:

$$ P(\omega\_n^{2k}) = p\_0 + p\_{\frac{n}{2}} + \left(p\_1 + p\_{\left(\frac{n}{2}+1\right)}\right) \left(\omega\_{\frac{n}{2}}\right)^{k} + \left(p\_2 + p\_{\left(\frac{n}{2}+2\right)}\right) \left(\omega\_{\frac{n}{2}}\right)^{k \cdot 2} + \left(p\_3 + p\_{\left(\frac{n}{2}+3\right)}\right) \left(\omega\_{\frac{n}{2}}\right)^{k \cdot 3} + \dots + \left(p\_{\left(\frac{n}{2}-1\right)} + p\_{n-1}\right) \left(\omega\_{\frac{n}{2}}\right)^{k \cdot \left(\frac{n}{2}-1\right)} $$

This means we can use a half sized FFT to compute the even indices of our full-sized FFT as follows:

$$ \operatorname{fft}\left(\left\[\left(p\_0 + p\_{\frac{n}{2}}\right), \left(p\_1 + p\_{\left(\frac{n}{2}+1\right)}\right), \dots, \left(p\_{\left(\frac{n}{2}-1\right)} + p\_{n-1}\right) \right\]\right) = \left\[P\left(1\right), P\left(\omega\_n^2\right), \dots, P\left(\omega\_n^{n-2}\right) \right\] $$

## Odd Indices

$$ P(\omega\_n^{2k + 1}) = p\_0 + p\_1 \omega\_n \omega\_n^{2k} + p\_2 \omega\_n^2 \omega\_n^{2k \cdot 2} + p\_3 \omega\_n^3 \omega\_n^{2k \cdot 3} + \dots + \left(\omega\_n\right)^{\frac{n}{2}} \omega\_n^{2k\frac{n}{2}}\left(p\_{\frac{n}{2}} + p\_{\left(\frac{n}{2}+1\right)} \omega\_n \omega\_n^{2k} + p\_{\left(\frac{n}{2}+2\right)} \omega\_n^2 \omega\_n^{2k \cdot 2} + p\_{\left(\frac{n}{2}+3\right)} \omega\_n^3 \omega\_n^{2k \cdot 3} + \dots\right)$$

From the properties of principal roots of unity, we can derive:

$$ \left(\omega\_n\right)^{\frac{n}{2}} = -1 $$

Analogous to the proof of the even index entries, we get the following half-sized FFT for the odd index entries:

$$ \operatorname{fft}\left(\left\[\left(p\_0 - p\_{\frac{n}{2}}\right), \left(p\_1 - p\_{\left(\frac{n}{2}+1\right)}\right) \cdot \omega\_n, \left(p\_2 - p\_{\left(\frac{n}{2}+2\right)}\right) \cdot \omega\_n^2, \dots, \left(p\_{\left(\frac{n}{2}-1\right)} - p\_{n-1}\right) \cdot \omega\_n^{\left(\frac{n}{2}-1\right)} \right\]\right) = \left\[P\left(\omega\_n\right), P\left(\omega\_n^3\right), \dots, P\left(\omega\_n^{n-1}\right) \right\] $$

# Answer
> 0 votes
The division step involves no computation, it is a mere permutation of the elements. It can indeed be described as a recursive process, top down (consider two halves of the input array and rearrange them, then two halves of each half and son on). In the diagram, this step is only represented by its final result (element-wise permutation).

The conquer step recombines the elements in larger and larger subarrays, and this is explicit in the diagram.

The Stockam method combines subdivision and computation, so that the initial rearragement step is unnecessary.

---
Tags: fourier-transform
---


title: Proof of halting problem

text:
# Question
Title: Proof of halting problem
if we change the halts to do\_not\_halt() function, it works, so how can this be a proof?

```
def g():
    if halts(g):
        loop_forever()

```

if we change the halts to do\_not\_halt() function, it works, so how can this be a proof?

# Answer
I think you misunderstood the proof strategy for the undecidability of the halting problem.

The proof goes as follows:

* Suppose towards a contradiction that there is some magic computable function `halts(x)` that takes as input a (description of an) algorithm $x$ and returns true if $x()$ halts and false otherwise.
* Then you can define a function `g` that uses `halt` as a subroutine as in your question.
* If `g()` halts, then `halt(g)` must return false, which contradicts the correctness of `halt`. If `g()` does not halt, then `halt(g)` must return true, which is again a contradiction.
* Since we always reach a contradiction, our hypothesis cannot be true. I.e., there is no computable function that decides whether an input function halts.

If you replace `halts(x)` with another function `does_not_halt(x)` that returns true if and only if `x()` runs forever, then you won't be able to derive a contradiction using the above proof. This *does not mean that there is no proof* that the halting problem is undecidable, just that the above proof attempt is not a good one.

In fact, you can show that no computable function `does_not_halt(x)` can exist with a minor modification of the above proof. Consider the following function `h`:

```
h():
   if not does_not_halt(h):
       loop forever

```

and examine what happens when `h()` is run. If `h()` halts, then the condition in the `if` statement must be false, i.e., `does_not_halt(h)` must return true. If `h()` does not halt, then the condition in the `if` statement must be true, i.e., `does_not_halt(h)` must return false. This leads to a contradiction in either case.
> 1 votes

# Answer
```
def g():
    if does_not_halt(g):
        loop_forever()

```

defines a function `g` that halts if `g` is proven to halt and does not halt if `g` is proven not to halt. This says nothing about the existence of `g` and does not help us.

The original `g`, on the opposite

```
def g():
    if halts(g):
        loop_forever()

```

cannot exist as its definition is contradictory (`g` does not halt if `g` is proven to halt and halts if `g` is proven not to halt!), and this proves the theorem.
> 1 votes

---
Tags: halting-problem
---


# Question
Title: Efficient algorithm to find the outflow of a lake
Consider a raster image representing a elevation map

$$ z = f(x, y) $$

An "extended lake" $L$ is the largest domain such that the elevation of every point $\partial L$ is greater than the elevation of any point within $L$. The outflow $P$ is the point on $\partial L$ with the lowest elevation. I came up with the following algorithm in order to find $P$:

1. Let $\partial L$ be the set of points on the boundary
2. Define visit($O$) as follows:
    1. Assume $O\in L$
    2. For all $P\_k$ in $\\{(x + 1, y),\\, (x, y +1),\\, (x - 1, y),\\, (x, y - 1)\\}$
        1. If $P\_k$ is visited, continue
        2. If $P\_k$ is outside the domain, continue
        3. If $f(P\_k) \< f(O)$
            1. add $O$ to $\partial L$
            2. continue
        4. visit $P\_k$
3. Pick any point $P\in L$ and visit $P$
4. Return the element $P$ in $\partial L$ that minimizes $f(P)$

While this works, the algorithm may need to visit too many pixels. Is it possible to avoid the full search by using a clever strategy such (for example) as a greedy choice of $P\_k$. That is, only consider $P\_k: f(P\_k) \< f(P\_l) \land f(P\_k) \geq f(O)$. Terminate when $f(P\_k) \< f(O)$, with $P\_k$ as the outflow.

# Answer
There is no particular relation between the elevations of the points of $\partial L$, so you can't avoid an exhaustive traversal of $\partial L$. Make sure that the boundary is 4-connected, otherwise looking only at the four neighbors may fail.

To find an initial point on $\partial L$, just walk straight from $O$.
> 0 votes

---
Tags: optimization
---


title: $m-$way merge sort, extended merge sort

text:
# Question
Title: $m-$way merge sort, extended merge sort
Consider Merge-sort algorithm that we modify as follow:

Suppose we extend it to divide the input array into $m$ not necessary equal and after sorting each of them, merge them. Now can we conclude that the running time will be $O(n\log n)$?

I think the running time should be $O(n^2)$ as follow:

If the algorithm divide to three sections such that two first sections contains some constant number of elements and third sections contains all most elements then the running time will be $O(n^2)$ if the algorithm continue dividing as mentioned scenario.

# Answer
> 1 votes
The linlogarithmic behavior of MergeSort is due to the fact that the size of the subsets decreases geometrically rather than arithmetically, so that the number of passes over the whole data is logarithmic.

You might very well roll a modified MergeSort that subdivides in fractions $\frac12,\frac13,\frac16$ and keep the same complexity.

But if we pursue your idea of handling subarrays of constant size, the archetypal algorithm that you obtain is StraightInsertionSort (recursively split $n$ in $n-1$ and $1$ sizes), that notoriously has an $O(n^2)$ behavior, because the number of passes is linear.

---

You get a similar situation when comparing dichotomic search and linear search in a sorted array.

# Answer
> 0 votes
The question leaves some room for interpretation, so I apologize in advance if my answer misses the mark.

You can in fact merge (sort) $m \le n$ sorted "runs" in at most $\mathcal{O}(n\log n)$ time. This is one of the many great ideas that went into the TimSort algorithm. You can find the original design document here.

One of the ideas of TimSort is to look for already sorted subsequences (Tim Peters dubbed them runs). This of course may lead to runs of vastly different size, just like You proposed. In order to merge the runs efficiently, TimSort delays the merging, putting the runs on a stack, looking for opportunities to merge sequences of roughly equal size. To prevent the stack from growing super-logarithmically, TimSort ensures that the sizes of the runs on the stack (top to bottom) grow at least as fast as the Fibonacci sequence.

So if You use such a "Fibonacci" stack for merging, then You can even handle arbitrary splits during recursion (provided Your programming language and/or runtime supports call stacks of size $\mathcal{O}(n)$). Of course it is not exactly merge sort anymore...

---
Tags: algorithms
---


title: What are quines (layman friendly)?

text:
# Question
Title: What are quines (layman friendly)?
I was going through the Wikipedia page on Quines and did not understand this paragraph -

> A quine is a fixed point of an execution environment, when the execution environment is viewed as a function transforming programs into their outputs. Quines are possible in any Turing-complete programming language, as a direct consequence of Kleene's recursion theorem.

I did not understand -

1. What is a fixed point?
2. What is the Kleene's recursion theorem?
3. How do these two relate with Quines?

I followed the links to both fixed point and Kleene's recursion theorem on Wikipedia but wasn't able to understand the content in there. It was a little too complex for me. I am looking for a simplified explanation of this paragraph. If it's not possible to do that (because for instance the topic requires knowledge of some higher level Computer Science concepts) that's understandable, please comment the same.

Thanks!

# Answer
## What is a fixed point?

A fixed point of a function is a value unchanged by that function. For example $0^2=0$ and $1^2=1$, so $0$ and $1$ are fixed points of the squaring function. Similarly “ASDF” is a fixed point of the function converting text into upper case.

*This was unclear at the time of asking, as ‘fixed point’ in Wikipedia was inappropriately linked; this has been fixed.*

## What is Kleene’s recursion theorem?

There are actually two, but they both say that certain functions have fixed points. The second theorem, which is relevant here, applies to computable functions. (The first concerns “enumeration operators”, which are mathematical relations between natural numbers and sets of natural numbers.)

## How do these two relate to quines?

Kleene’s second recursion theorem can be used to prove that quines, which are fixed points, exist in most programming languages.

As the paragraph that confused you said, a quine (a self-printing programme) can be seen as a fixed point of the function that turns a programme (in a given programming language) into the output of that programme (when run with no input): the output is the same as the input. If the programming language is Turing complete, this function satisfies the conditions of Kleene’s recursion theorem, so it must have a fixed point, i.e. a quine in that language. This applies to most current programming languages.

To follow the proofs of all this you need some technical knowledge and some mathematical maturity. You may be able get the former from the Wikipedia articles or from a course or book on computability theory, while the latter comes with practice.
> 3 votes

# Answer
Quines are programs which when executed, print their own code.
> 2 votes

---
Tags: algorithms, turing-machines, compilers, turing-completeness
---


title: Origin of "Cookie" in Computing?

text:
# Question
Title: Origin of "Cookie" in Computing?
"Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997.

Many claim the use in HTTP followed from UNIX "magic cookies." Eric Raymond provided a definition of *what* a "magic cookie" is:

> Something passed between routines or programs that enables the receiver to perform some operation; a capability ticket or opaque identifier \[...\]

OK.

But why did the UNIX community start using the phrase "cookie" to begin with? Is it because you put cookies into a jar, and take them out? When did this whole thing begin? Does anyone have a citation of the first usage?

# Answer
According to the Wikipedia article on magic cookie, it was used already in 1979 in the manpage of fseek. The talk page of the Wikipedia article on magic cookie discusses questions regarding the origin and meaning of the word. The following quote of Douglas W. Jones from the talk page nicely summarizes it:

> Once upon a time, I asked Dennis Ritchie about the origin of the term magic cookie as used in the man page for ftell and fseek in the C library. He said that, so far as he knew, the usage in that man page was a new coinage. That man page is not present in V5 UNIX but it is present in the manuals for V7 UNIX and 4.2BSD. I have quoted the relevant sentence from that manual on the Wikipedia page; the wording makes it clear that the meaning is the same as the contemporary meaning for magic cookie (in the broader sense than HTML cookie). Any speculation about derivation from cookie monsters or LSD cookies seems, at this point, irrelevant compared to tracking down the first use of the term in its modern sense. Douglas W. Jones 21:15, 24 February 2017 (UTC)
> 2 votes

# Answer
The "Magic Cookie" was a plot device, symbolizing hallucinogenic drugs, in the comic strip "Odds Bodkins" that ran in the San Francisco Chronicle from 1969 to 1970 (https://en.wikipedia.org/wiki/The\_Collective\_Unconscience\_of\_Odd\_Bodkins).
> 0 votes

---
Tags: terminology, history
---


# Question
Title: Constrained Delaunay triangulation algorithm?
I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the presenter it's hard to follow.

Ideally I am looking for a strategy that only involves edge flipping, without the need for deletion and reinsertion.

# Answer
You can find Johnathan Shewchuck's UC Berkely website here, which contains:

* Excellent lecture notes on Delaunay Mesh Generation
* sample chapters from the book "Delaunay Mesh Generation" (which might well be worth buying)
* Many other excellent papers and references

Ages ago, I have used his lecture notes to implement Constrained Delaunay Triangulations in Scala. If You're interested, you can find the source code on GitHub.

I am not sure what you mean by flipping instead of deletion. Technically, edge flipping is the removal of two triangles followed by an insertion of two other triangles.
> 1 votes

# Answer
Page 7 of "FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" (a publication on a CDT algorithm) explains the process very clearly and the figures are extremely useful.
> 1 votes

---
Tags: graphs, computational-geometry, discrete-mathematics, triangulation
---


# Question
Title: Faster selection algorithm for small order statistics
`SELECT(A,p,r,i)` is an algorithm that

1. partitions $A\[p:r\]$ around the $i$ th order statistic ie. in the output, we have $l\in A\[p:p+i-2\]\<A\[p+i-1\]\< h\in A\[p+i:r\]$. Where $A\[p+i-1\]$ is the $i\in \\{1,...,r-p+1\\}$ order statistic (basically the $i$ th smallest element).
2. returns the $i$ th order statistic
3. worst case run time is $\Theta(n)$

it's same as the popular `RANDOMIZED-SELECT` e.g. the `std::nth_element` in C++ (I guess) except the run time and implementation.

The problem is that

> Denote by $S(n)$ the worst case **number of comparisons** used by SELECT **to select the $i$ the order statistic from $n$ numbers** . When $i$ is small relative to $n$, below algorithm makes fewer comparisons in worst case.
> Describe an algorithm that uses $U\_i(n)$ **comparisons** to find the $i$ th smallest of $n$ elements, where $$ \newcommand{\floor}\[1\]{\lfloor #1\rfloor} \newcommand{\ceil}\[1\]{\lceil #1\rceil} U\_i(n) = \left\\{\begin{array}{cc} S(n)&\text{if } i\ge n/2 \\ \floor{n/2}+U\_i(\ceil{n/2})+S(2i)& \text{otherwise } \end{array}\right. $$ Hint: Begin with $\lfloor n/2\rfloor$ disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair. \[1\]

But I still have no idea, because there's no guarantee that the set $Q$ containing the smaller element from each pair contains the $i$ th smallest element e.g. suppose we want $2$ nd smallest in $2,1,3,4,6,5$, then one possible $Q$ is $\\{1,3,5\\}$ which doesn't contain the $2$ nd smallest ie. $2$.

I'm even more confused by the extra $S(2i)$ term, like which $2i$ elements are we going to run `SELECT` on ?

\[1\] Introduction to Algorithms,MIT

# Answer
> 1 votes
Thanks to comment by @Yuval Filmus I get the idea. Basically we abuse transitivity that $x\_j\< x\_{j+1}$ and $x\_{j+1}\< y\_{j+1}\implies x\_j\< y\_{j+1}$. Therefore we can conclude $(x\_j,y\_j)$ can never be one of $i$ smallest for any $i\<j$ by partitioning the array around $(x\_i,y\_i)$ using `SELECT` (we select only on $x$ entries but we move pairs around, not elements).

As we go deeper into recursion, entries e.g. $x\_j$ will be become pair of pairs of ... below program resolves this by using a doubly link list, where we always ensure $list.front()$ is the smallest element in the whole list. We don't care about the relative ordering of other elements in the list however.

Below program consists of few stages, for the base case we just run `SELECT` (or `nth_element` which is similar). For recursive case, we have

* pairing stage: form $(x\_j,y\_j)$ such that $x\_j\<y\_j$ and put them at front of array $A\[0:n/2-1\]$. The rest of the array $A\[n/2-1:n-1\]$ is empty due to pairing.
* recursion stage: recurse on $n/2$. Select the $i$ smallest $(x\_j,y\_j)$ pairs (in terms of $x$ entry) and put them at the front of array $A\[0:i-1\]$. So that $x\_h\in A\[0:i-1\]\<x\_k\in A\[i:n/2-1\]$.
* unpairing stage: we know pairs in $A\[i:n/2-1\]$ can never contain any of $i$ smallest elements in $A$, so we push them to the back and unpair them (get out of the way). $A\[0:i-1\]$ surely contains all $i$ smallest elements (but we don't know where exactly) so we unpair them near the front of array $A\[0:2i-1\]$ first.
* selection stage: (this's the actual work) select the $i$ smallest elements in $A\[0:2i-1\]$ and put them at the front of array $A\[0:i-1\]$. Then returns to caller (which will then unpair what it has paired...).

Below is an implementation which selects in place. Although we're frequently moving large lists around, it's actually quite fast thanks to move semantics in C++. The slower part is probably the link list traversal during unpairing.

```
input: 9 12 7 5 -1 19 3 2 45 18 33 6 -35 98 111 160
3 smallest: -35 -1 2

```

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

//assume n is powers of 2. if not we may break n into powers of 2 and combine solutions.
//A is input array, initially A[i] is a list containing only 1 element of type T
//i is the order statistic we desire, takes value in 1,...,n
//selects in place so that A[0:i-1] contains i smallest elements upon return
//to answer the question simply replace nth_element with SELECT
template<typename T>
void SMALL_ORDER_STAT_SELECT(vector<list<T> >&A,int n,int i){
    if(i>=n/2)
        //partition subarray A[0:n-1] around the ith order statistic
        nth_element(A.begin(),A.begin()+i-1,A.begin()+n,[](list<T>&a,list<T>&b){return a.front()<b.front();});
    else{
        //pairing step
        for(int j=0;j<n/2;++j){
            //so that A[j].front is smallest in A[j]. But we don't know relative order within A[j] other than that.
            if(A[j].front()<A[n/2+j].front())
                A[j].splice(A[j].end(),A[n/2+j]);//pair
            else
                A[j].splice(A[j].begin(),A[n/2+j]);//pair
        }
        SMALL_ORDER_STAT_SELECT(A,n/2,i);//so that A[0:i-1] contains pairs each with one of the i smallest fronts
        //unpairing step
        //move indices [i,n/2) to [2i,i+n/2)
        //we know those entries cannot contain the ith smallest elements (they arn't important)
        //so push them to back of array to make room so that A[0:i-1] unpair to form A[0:2i-1]
        for(int j=n/2-1;j>=i;--j)
            swap(A[j],A[i+j]);
        //unpair (above unimportant entries) [2i,i+n/2) to form [i+n/2,n) formula: f(j)=j-i+n/2
        for(int j=i+n/2-1;j>=2*i;--j){
            auto it=A[j].begin();
            for(int k=0;k<A[j].size()/2;++k)
                ++it;
            A[j-i+n/2].splice(A[j-i+n/2].begin(),A[j],it,A[j].end());//unpair
        }
        //unpair (important entries) A[0:i-1] unpair to form A[0:2i-1] formula: f(j)=i+j
        //those entries are important because they contain the ith smallest elements (but may also contain other elements)
        for(int j=0;j<i;++j){
            auto it=A[j].begin();
            for(int k=0;k<A[j].size()/2;++k)
                ++it;
            A[i+j].splice(A[i+j].begin(),A[j],it,A[j].end());//unpair
        }
        //so that A[0:i-1] contains the i smallest of the i pairs
        nth_element(A.begin(),A.begin()+i-1,A.begin()+2*i,[](list<T>&a,list<T>&b){return a.front()<b.front();});
    }
}

int main(){
    int n=16;
    int i=3;//3 smallest
    vector<list<int> >A{{9},{12},{7},{5},{-1},{19},{3},{2},{45},{18},{33},{6},{-35},{98},{111},{160}};
    cout<<"input: ";
    for_each(A.begin(),A.end(),[](list<int>&l){cout<<l.front()<<' ';});
    cout<<endl;
    SMALL_ORDER_STAT_SELECT(A,n,i);
    cout<<i<<" smallest: ";
    for_each(A.begin(),A.begin()+i,[](list<int>&l){cout<<l.front()<<' ';});
    cout<<endl;
}
```

---
Tags: algorithms, complexity-theory, search-algorithms, algorithm-design, selection-problem
---