# Question
Title: Is $P=NP$ even if we need infinitely many algorithms?
If $P=NP$ was proven with an algorithm, would that have to mean that there is **one** algorithm that has to work for all inputs of length $n$?

More specifically, what if there were infinitely many polynomial time algorithms for $n=1,2,3,...$, but no algorithm would work for more than one value $k=n$. I don't mean that $n$ would be fixed, but that for each greater $n$ we would have to modify or construct a new algorithm that solves the problem in polynomial time.

I am thankful for any answers :)

# Answer
> 3 votes
I'll start with your first question:

> If $P=NP$ was proven with an algorithm, would that have to mean that there is **one** algorithm that has to work for all inputs of length $n$?

Yes, in order for $P$ to equal $NP$, there has to be *one* algorithm for all inputs. It can't be infinitely many algorithms that each solve some subset of the problem.

For your more specific question, though, you may be surprised: we already do have an algorithm that solves SAT for each *specific* value of $n$ and runs in polynomial time! In fact, we have an algorithm for each specific $n$ that works in constant time. Take $n = 3$, for example. Then just write out all the possible inputs of length $3$, and make a table of all the answers for each input. The algorithm just looks at the input, queries the table, and returns the result:

$$ \begin{array}{cc} \text{input} & \text{answer} \\ 000 & 0 \\ 001 & 1 \\ 010 & 1 \\ 011 & 0 \\ \cdots \end{array} \\ \text{Algorithm: on input $x$ of length 3, return the answer given in the above table.} $$

What went wrong here? The problem lies in what we mean by **polynomial time.** Hidden in the word "polynomial" is that we usually mean **polynomial in $n$**, i.e. it has to run in time that is a polynomial function of the input length. If the input length is a fixed constant, then it no longer makes sense to ask for a polynomial time algorithm: **all algorithms (no matter how fast or slow) will be polynomial time** since there are only finitely many possible inputs we care about, so the running time is always bounded by a constant.

---

**Addendum.** You raise an interesting question in the comments. My initial interpretation of it was, what if we require that the algorithm for each $n$ runs in a fixed polynomial $p(n)$ (so the polynomial upper bound has to be the same for every $n$)? To this the answer is still that we can already do this, because we can hardcode the table in the program so that it runs in exactly $n$ steps (the time to read the input). Think of it as the following program:

```
ANSWER_TABLE = [000: 0, 001: 1, 010: 1, 011: 0, ...]
On input x:
  return ANSWER_TABLE[x]

```

Now the program size is $2^n$, sure, but the program runs in time $n$. You could also explicitly write out a giant set of nested if-then-elses instead of hardcoding the table. Anyway, we have an algorithm for each $n$ that solves SAT and runs in at most $n$ steps.

But you still would object that the program size is still exponential in $n$. If you also require that the program itself has size polynomial in $n$, then I am not sure if it is possible anymore. That may be related to the field of circuit complexity.

---
Tags: algorithms, complexity-theory, time-complexity, p-vs-np
---


title: Formulate a 2-clustering problem in LP

text:
# Question
Title: Formulate a 2-clustering problem in LP
The problem:

Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance between each pair of points.

My question is, how we can formulate above problem in LP manner?

My attempt:

I think so much to find a LP formulation for above problem but i have no idea.

# Answer
Let $P$ be the given set of points. Declare a variable $x\_p$ for every point $p \in P$ in the plane. Set $x\_p = 1$ if point $p$ belongs to cluster $1$ and $x\_p = -1$ if point $p$ belongs to cluster $2$. Then, the integer linear program would be as follows:

**Objective function:** minimize $d\_1+d\_2$

**Constraints:**

$\frac{(x\_p + x\_{p'})}{2} \cdot d(p,p') \leq d\_1$ for every pair $p,p' \in P$

$-\frac{(x\_p + x\_{p'})}{2} \cdot d(p,p') \leq d\_2$ for every pair $p,p' \in P$

$x\_p \in \\{1,-1 \\}$ for every point $p \in P$

$d\_1,d\_2 \geq 0$

---

Here, $d(p,p')$ denotes the distance between points $p$ and $p'$.
> 2 votes

---
Tags: algorithms, linear-programming, clustering
---


title: Mapping reduction properties exercise

text:
# Question
Title: Mapping reduction properties exercise
I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help.

We know about three languages, A, B and C. There exists a mapping reduction from A ≤m B, and A ≤m C.

What can be concluded about: A ≤m B union C ? What can be concluded about: A ≤m B intersection C ?

# Answer
> 1 votes
Not much can be concluded about $A \le\_m B \cup C$ since it might not exist. For example let $A$ and $B$ be two non-trivial languages and define $C = \Sigma^\* \setminus B$. Then there is no way to map a word in $\Sigma^\* \setminus A$ to a word in $\Sigma^\* \setminus (B \cup C)$.

The same choices of $A$, $B$, and $C$ also show that $A \le\_m B \cap C$ might not exist. Indeed, there is no way to map a word in $A$ to one in $B \cap C = \emptyset$.

---
Tags: automata, reductions, discrete-mathematics
---


# Question
Title: Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:

> Given a graph G and a number k, does G contain an independent set of size at least k?

> Given a graph G and a number k, does G contain a vertex cover of size at most k?

My question is, what is the reasoning behind using "at least" for the independent set and "at most" for the vertex cover? When we want to optimize, we want to maximize Independent Set and minimize Vertex Cover. So shouldn't it be finding at most size *k* for Independent Set and at least size *k* for Vertex Cover?

# Answer
## Theory

Note that the set of all vertices is trivially a vertex cover, and any set containing only one vertex is trivially an independent set.

What is hard with an independent set is to make it larger. The more vertices it has, the more it "risks not being independent" by two vertices being adjacent. Formally, if U and V are two sets of vertices such that $U \subseteq V$, then "V is independent" implies "U is independent" (or equivalently: "U is not independent" implies "V is not independent").

What is hard with a vertex cover is to make it smaller. The more vertices you remove, the more chances there are that you no longer have a vertex cover. Formally, if U and V are two sets of vertices such that $U \subseteq V$, then "U is a vertex cover" implies "V is a vertex cover" (or equivalently, "V is not a vertex cover" implies "U is not a vertex cover").

## Applications

Practical applications of vertex cover include the situation where you want some service to be available to everyone, while minimizing the cost of deploying your service everywhere. For instance, imagine we need to build fire stations in a city. I have divided the city into small districts, and I want to make sure that every district either has its own fire station, or is adjacent to a district with a fire station. What I need to find, then, is a vertex cover of the graph formed by the districts. Of course, I could just put one fire station in every district, which would trivially solve the problem; but if I want to minimize my budget, then I need to find a minimum vertex cover.

Practical applications of independent set include the situation where a bunch of tasks each depend on some resources. You want to perform as many tasks as you can, but cannot perform two tasks which share the same resource. We model this problem by building a graph where each vertex is a task, and two vertices share and edge if they depend on the same resource. A feasible set of tasks is an independent set: a set of tasks such that no two tasks of the set are adjacent in the graph. Performing a single task is trivially a solution, but if we want to maximize the number of simultaneous tasks that we can perform, we need to look for a maximum independent set. Concretely, the tasks could for instance be courses in a university, and the resources the teachers and students: two courses cannot be held simultaneously if one student is taking both courses, or if the same teacher teaches the two courses.
> 4 votes

---
Tags: complexity-theory, graphs, polynomial-time-reductions, vertex-cover, independent-sets
---


# Question
Title: A proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any MST
I cant proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any Minimum Spanning Tree. please help.

# Answer
> 0 votes
Lets assume that it did participate in an MST $T$.

Now, removing $f$ will split $T$ into two connected components - $T\_1,T\_2$. In particular, both vertices of $f$ need to be in *different* connected components. Lets call the vertices $v\_1$ and $v\_k$, and w.l.o.g. assume $v\_1\in T\_1$ and $v\_k\in T\_2$.

Lets name all vertices in the cycle by $v\_1,v\_2,\dots,v\_k$ such that there is an edge between $v\_i$ and $v\_{i+1}$ for all $i$ (and of course, $v\_1,v\_k$ are the vertices of $f$).

Since $v\_1\in T\_1$ and $v\_k\in T\_2$, and also $v\_i\in T\_1\lor v\_i\in T\_2$ then there must be some index $i\_0\<k$ with $v\_{i\_0}\in T\_1$ **and** $v\_{i\_0+1}\in T\_2$. We know that $(v\_{i\_0} , v\_{i\_0 + 1})$ is an edge in $G$, and its weight is lower than that of $f$ \- and in addition it will connect the two components! Therefore, by replacing $f$ with this edge we get another spanning tree with a lower weight, which is a contradiction to the assumption we started with an MST!

---
Tags: graphs, discrete-mathematics
---


# Question
Title: How did 8-bit computers (Intel 8088) iterate numbers beyond 256?
I never recall any problem making FOR loops in BASIC to 10000 on old IBM PC computers, but how does it work at the machine level when the number in the data register is (presumably) limited to a number from 0-255?

\[Edit: I can speculate that the processors had special instructions to use more than one word, but I never recall hearing such techniques.\]

# Answer
The obvious answer is also the correct one here -- if the number of bits in a register or memory architecture is smaller than the number of bits needed for a particular data type, then the data type is represented using more than one register or memory unit.

This isn't really unique to 8-bit computing. On 32-bit architectures if you use a 64-bit or 128-bit long, it will be physically a sequence of 2 or 4 blocks, respectively.
> 2 votes

---
Tags: assembly
---


# Question
Title: Confusion regarding calculation of estimated memory access time in a system containing only a cache and main memory for simplicity
Let us consider a system having cache and main memory. Now suppose we are asked to find the average memory access time. Let $h$ be the hit ratio for the cache, $t\_c$ be the cache access time, $t\_m$ be the time to access a word of data from the main memory and cache block size be $b$ words.

The picture below is from *William Stalling's Computer Organization and Architecture* text.

*RA: Required Address*

From the diagram above, it seems that in case of a cache miss, the transfer of the block of words from main memory to cache takes place at the same time the word required by CPU is transferred to it directly by main memory.

In most places I have seen unclear formula for *Estimated Memory Access Time* $\text{(EMAT)}$ as:

$$\require{color}\colorbox{cyan}{$\text{EMAT}= t\_c+(1-h)\* \text{main-memory-access-time}$}$$

But they do not say clearly whether this $\text{main-memory-access-time}$ is for a single word or for a block of words.

What I feel from the block diagram shown above:

$$\require{color}\colorbox{cyan}{$\text{EMAT}= t\_c+(1-h)\*t\_m$}$$

Since, once the required word has reached the CPU there ends the memory access as seen by CPU while in the background the block transfer might occur (taking a total of $b\*t\_m$ time for the block transfer)... So in this point of view $\text{miss-penalty} = \text{memory-access-time-for-one-word}$.

Upon second thoughts the thing which bothers is that, after having a miss, since the block transfer occurs in background, during that $\[(b\*t\_m) + t\_c\]$ time, reference to the cache block which is being transferred shall lead to a miss, so this makes me feel that the $\text{EMAT}$ could have been:

$$\require{color}\colorbox{cyan}{$\text{EMAT}=t\_c+(1-h)\*\[(b\*t\_m) + t\_c\]$}$$

So, could anyone guide me as to how I should proceed with such calculations?

# Answer
> 1 votes
Think of RAM access like accessing one train wagon, when you have a locomotive that can pull a dozen wagons. Getting one wagon or 12 wagons takes about the same time.

Same with RAM. The time to read from memory consists of the time for sending an address to RAM, plus the time for the RAM to find the line of memory containing the address, and the time of transmitting the data. The transmission is done several words at a time. Trying to read a single word would safe very little because the RAM would have to find that word in the memory line, wastes all the extra words that could be transmitted at the same time.

There are systems where a cache line needs two transmissions from RAM, and the RAM sends the half cache line containing the requested memory first. Still, two transmissions take very little longer than one.

So when the memory word that you wanted arrives at the CPU, the cache line is filled or will be filled very quickly.

---
Tags: computer-architecture, cpu-cache, memory-access, performance
---


# Question
Title: "Greater than" condition in integer linear program with a binary variable
How can one model the following condition in an integer linear program?

$$A = \begin{cases} 1 & \text{if } B \> C\\ 0 & \text{otherwise}\end{cases}$$

where $A \in \\{0,1\\}$ and $B, C \in \mathbb N$. We have upper and lower bounds on both $B$ and $C$.

# Answer
> 1 votes
I think I found the answer here! It is sufficient to use the big-M method by introducing the following constraints:

B \>= C + 1 - M\*(1-A);

C \>= B + 1 - M\*A

# Answer
> 1 votes
The second inequality of the answer of Salah doesn't hold if $B=C$. I think the correct answer is the following two inequalities:

$$ B \geq C + 1 - M (1-A) $$ $$ B \leq C + M A $$

where $M$ is an upperbound on $|B-C| + 1$.

The **first inequality** restricts $A$ to $0$ if $B \leq C$.

For example, if $B=0$ and $C=0$, then

$$ 0 \geq 0 + 1 - M(1-A) \rightarrow A = 0 $$

The **second inequality** restricts $A$ to $1$ if $B \> C$.

For example, if $B=1$ and $C=0$, then

$$ 1 \leq 0 + M A \rightarrow A = 1 $$

# Answer
> 0 votes
Is it possible to enforce this through your objective function? For instance, if your objective function was $$\max A,$$ the constraint $$A\leq (B-C) M,$$ where $M$ is a "big-$M$" (large value) will work provided B is larger than C by some tolerance. The tolerance will be $\frac{1}{M}$, i.e. $B-C \geq \frac{1}{M}$ before the constraint is properly enforced.

# Answer
> 0 votes
If you are in a MILP setting, then I think the following should work. Assume $\underline{B},\underline{C}$ and $\overline{B},\overline{C}$ are your respective lower/upper bounds. Then the constraint $$A \geq \frac{B-C}{\overline{B}-\underline{C}}$$ ensures that $A=1$ if $B-C$ is positive, since the RHS of the equation is between 0 and 1 in this case. When $B-C$ is negative, then the constraint is useless. The constraint $$\frac{\underline{C}-\overline{B}}{C-B}\geq A$$ ensures that $A=0$ if $B-C$ is negative, for similar reasons.

# Answer
> 0 votes
This is another possibility for the "greater or equal" and "lower or equal" version. For the pure greater and pure lower version you must remove the +1 resp. -1 from first constraint. You must also add a +1 to the second constraint "... \>= yM+1".

---
Tags: linear-programming, integer-programming, constraint-satisfaction
---


# Question
Title: Why we get at most $N^2$ probe sequences using double hash function
**Question**:Given the following double hash function:

$$h(k,i) = (h\_1(k) + i\times h\_2(k)) \bmod{N}$$, where $h\_1(k): key \to \mathbb{Z}$. $h(k,i)$ can generate $N^2$ probe sequences at most and $h\_2(k)$ can determine the increment for the probe sequence. Also, $N$ is the number of slots.

**Problem**:Each sequence generated from double hash function regarded as 1 of $N^2$, so my question is why at most we can have $N^2$ probe sequences please? For example, in linear hashing where $h(k,i) = (h\_1(k) + i) \bmod{N}$ , we can have N probe sequences at most because for each number $i=0,1, \cdots$ we can get a sequence. Similarly, why we get $N^2$ probe sequences in the double form please?

# Answer
Note that $(h\_{1}(k))\mod N$ can take $N$ distinct values and $(h\_{2}(k))\mod N$ can take $N$ distinct values. To show that the total number of sequences are $N^2$, we will need to show that for some different inputs $k\_1$ and $k\_2$, if $(h\_{1}(k\_{1}) \not\equiv h\_{1}(k\_2) \mod N)$ or $(h\_{2}(k\_1) \not\equiv h\_2(k\_2) \mod N)$, then the probing sequences would be different for $k\_1$ and $k\_2$. Let the sequence generated by $k\_1$ is $P\_1$ and the sequence generated by $k\_2$ is $P\_2$.

**Proof:** Suppose $(h\_{1}(k\_{1}) \not\equiv h\_{1}(k\_2) \mod N)$. Then, for $i = 0$, the first element of the $P\_1$ would be $h\_{1}(k\_{1}) \mod N$, and the first element of the $P\_2$ would be $h\_{1}(k\_{2}) \mod N$. Since their first elements are different, the sequences are different.

And, suppose if $(h\_{1}(k\_{1}) \equiv h\_{1}(k\_2) \mod N)$ and $(h\_{2}(k\_{1}) \not\equiv h\_{2}(k\_2) \mod N)$. Then, for $i = 1$, the second element of $P\_1$ would be $(h\_{1}(k\_{1}) + h\_{2}(k\_{1})) \mod N$ which is different from the second element of $P\_2$, i.e., $(h\_{1}(k\_{2}) + h\_{2}(k\_{2})) \mod N$. You can easily prove this statement using contradiction.

---

Note: I noticed later that you are just asking for **at most** $N^2$ sequences. It is actually trivial since $(h\_{1}(k)\mod N)$ can take $N$ distinct values and $(h\_{2}(k)\mod N)$ can take $N$ distinct values. For a fixed value of $(h\_{1}(k)\mod N)$ and $(h\_{2}(k)\mod N)$, we have a particular sequence. Therefore, the sequences can be at most $N^2$. But, what I proved earlier is much stronger, i.e., the number of possible sequences could **actually be** $N^2$.
> 1 votes

---
Tags: algorithms, hash, number-theory
---


# Question
Title: Are recursion and a stack equivalent in terms of inplementing DFS?
It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem:

> Given a directed acyclic graph (DAG) of n nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in any order.
>
> The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node `i` (i.e., there is a directed edge from node `i` to node `graph[i][j]`).

Here is a solution which uses DFS and maintains the current path in the graph with a stack `stk`.

```
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    ans = list()
    stk = list()

    def dfs(x: int):
        if x == len(graph) - 1:
            ans.append(stk[:])  # stk[:] returns a copy of stk
            return

        for y in graph[x]:
            stk.append(y)
            dfs(y)
            stk.pop()

    stk.append(0)
    dfs(0)
    return ans

```

If recursion and stacks are equivalent, then there must exist an iterative solution that uses two stacks, one to implement DFS and another to maintain the current path (same purpose as `stk`). However, I'm struggling to come up with one. The trick park is maintaining `stk`. When using recursion, `stk` is simply the call stack, but that's no longer true with an explicit stack, because nodes from different branches may co-exist in it.

**Question:** how to write an iterative version of the DFS solution presented above?

# Answer
Does this pseudocode help? Let me know of any clarifications.

```
stack_0.push(0) // stack containing only vertex 0
stack_of_stacks = empty
stack_of_stacks.push((stack_0, vertex 0)) // added a tuple of stack and vertex 0

while stack_of_stacks is not empty:

      (temp_stack, temp_vertex) = stack_of_stacks.pop()

      if temp_vertex = n-1
            print temp_stack
      else, for every y in graph[temp_vertex]
            new_stack = temp_stack
            new_stack.push(y)
            new_vertex = y
            stack_of_stacks.push((new_stack, new_vertex))
end

```
> 2 votes

---
Tags: algorithms, graphs, recursion, graph-traversal, stacks
---


title: Implication of the Pumping lemma

text:
# Question
Title: Implication of the Pumping lemma
I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma\[sic\] does not state that every sufficiently long string in a regular set is of the form $uv^iw$ for some large $i$". I can't see how this is true.

If I'm not wrong, the pumping lemma states that if $L$ is a regular set, then **every** "sufficiently" long string $x\in L$ can be written as $uvw$ such that $uv^iw\in L$ for all $i\geq 0$, then shouldn't there be some $i\geq 0$ such that every "sufficiently" long string $x\in L$ be of the form $uv^iw$ for some strings $u,v,w$?

Also, the authors state (whose proof is left as an exercise) that the set $(0+1)^\*$ contains arbitrarily long strings in which no substring appears three times consecutively. I can't seem to see how this is true as well.

Any help or perhaps even a hint is well appreciated.

# Answer
> 3 votes
Yes, since we can let $i$ be 0. Every non-empty word $x\in L$ can be expressed as "$xx^0\epsilon$".

We can also let $i$ be 1. Every non-empty word $x\in L$ can be expressed as "$\epsilon x^1\epsilon$".

The statements above are rather trivial and banal.

So, the real question is, given a regular language $L$, is there some $i\geq 2$ such that every "sufficiently" long string $x\in L$ is of the form $uv^iw$ for some strings $u,v,w$ where $v$ is nonempty?

---

The answer is, "not necessarily".

We call a string of the form $vv$ for some non-empty $v$ a square string. There exists an infinite string $t\in \\{a,b,c\\}^\*$ such that it does not contain any square string. An example of such a string is given in this post.

That means there are arbitrary long strings, such as the prefixes of that infinite string, that do not contain any square string. So the answer for the regular language $\\{a,b,c\\}^\*$ is "no".

---

**Exercise.** Show that every sufficiently long string over the alphabet $\\{a,b\\}$ is of the form $uv^2w$ for some strings $u,v,w$ where $v$ is nonempty.

---

> The set $(0+1)^\*$ contains arbitrarily long strings in which no substring appears three times consecutively.

A classical example is the Thue–Morse sequence. For a proof, check a proof to the cube-freeness of the Thue-Morse sequence by Yuval Filmus.

---
Tags: regular-languages, finite-automata, pumping-lemma
---


# Question
Title: Implement a dictionary by using direct addressing on a huge array
For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct address dictionary on a huge array. Each stored object should use $ O(1)$ space; the operations SEARCH, INSERT, and DELETE should take $O(1)$ time each; and the initialization of the data structure should take $O(1)$ time. (**Hint**: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)"

**Problem**: can you please help explaining the wording of the question in your own words? No solution is needed.

# Answer
> 1 votes
"We wish to implement a dictionary by means of an hashing function that maps all its possible inputs to a huge but finite set of natural numbers of size $k$. The function is implemented by values of an array witnessing the presence/lack of any element. The array is expensive to setup, so we ask that the algorithm does not clear it. (It is used for holding pointers to present elements.) Describe an algorithm for granting, constant time operations, constant space usage for items storage (pointers to objects) and constant initialisation time. ( Hint. Employ and additional stack for avoiding false positives on insert/removal and lookup operations.)"

False positives are due to the presence of garbage. Possibly the most nebulous part is the usage of the stack. Since it is bounded in size (at most $k$), you will have to scan from it at most $k$ elements. Since it's size is bounded you can have lookups in O($k$) and that's constant time.

# Answer
> 2 votes
Here is another hint: how would you find whether an element is valid in $O(1)$ in this auxiliary stack? Try to somehow "connect" the index at the original huge array, to the place in the stack that says that this element is indeed valid. Don't be afraid to use another auxiliary array for this!

---
Tags: algorithms, hash
---


title: How does $Θ(\log(n!))=Θ(\log(n^n)$?

text:
# Question
Title: How does $Θ(\log(n!))=Θ(\log(n^n)$?
How does $Θ(\log(n!))=Θ(\log(n^n)$?

I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the following:

$$\lim\_{x\to \infty}\left(\frac{\log\_2(x^x)}{\log\_2(x!)}\right)=\infty. $$

So how could there be constants such that $Θ(\log(n!))=Θ(\log(n^n))$?

Where has my understanding gone wrong?

# Answer
As a matter of fact, $$\lim\_{x\to \infty}\frac{\log\_2(x^x)}{\log\_2(x!)}=1.$$ So there is no problem to reconcile.

Looking at the first revision of the question, it seems to me that you are confused about the fact that $\frac{n^n}{n!}$ has different behaviour from $\frac{\log n^n}{\log n!}$: $$\lim\_{n\to+\infty}\frac{n^n}{n!}=+\infty,\qquad\text{while}\qquad\lim\_{n\to+\infty}\frac{\log(n^n)}{\log(n!)}=1\<+\infty.$$ There is no problem with this. Unboundedness of ratios of functions is not preserved by applying arbitrary functions such as $\log$, because $\exp$ (the inverse of $\log$) is not polynomially bounded. For a simpler example, $$\lim\_{n\to+\infty}\frac{n^2}{n}=+\infty,\qquad\text{while}\qquad\lim\_{n\to+\infty}\frac{\log(n^2)}{\log(n)}=2\<+\infty.$$

In general, a function $h\colon\mathbb R\_{\>0}\to\mathbb R\_{\>0}$ satifies the condition that $$\limsup\_{n\to+\infty}\frac{f(n)}{g(n)}\<+\infty\implies\limsup\_{n\to+\infty}\frac{h(f(n))}{h(g(n))}\<+\infty$$ for all $f,g\colon\mathbb N\to\mathbb R\_{\>0}$ if and only if there exists a constant $c$ such that $$y\le2x\implies h(y)\le ch(x)\tag1$$ for all $x,y\in\mathbb R\_{\>0}$. For example, (1) holds for all function of the form $h(x)=x^\alpha$ for some $\alpha$. On the other hand, any function $h$ satisfying (1) is *polynomially bounded*, specifically, $h(x)=O(x^{\lceil\log\_2c\rceil})$.
> 7 votes

# Answer
$$\log (n!)=\log\left(\prod\_{i=1}^{n}i\right)$$ $$=\log(1)+\log(2)+\dots+\log n$$ $$=\sum\_{i=1}^{n}\log i\leq n\log n.$$ $$\sum\_{i=1}^{n}\log i=\sum\_{i=1}^{\frac{n}{2}}\log i+\sum\_{i=\frac{n}{2}+1}^{n}\log i$$ $$\geq\frac{n}{2}\log(\frac{n}{2})=\Theta(n\log n).$$

Since $$\log n^n=n\log n$$ $$\implies \log (n!)=\Theta(\log n^n).$$
> 3 votes

---
Tags: asymptotics, big-o-notation
---


title: recurrence with exponentials

text:
# Question
Title: recurrence with exponentials
I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such:

t(n)=4t(n/2)+2^n

with t(1)=1 for n\>=5

From what I know, the recurrence should lay in Θ(2^n).

My own attempts:

Usually I would approach this problem via master-theorem case 3, but from the condition that it wouldn't be able to fullfill it via Ԑ\>0, with log2(4)=2 meaning, f(n) in Ω(n^2+Ԑ), could be only Ԑ=0 since 2^n in Ω(n^2). So I know pretty much, I can't use master theorem to figure out the problem.

But not sure how else to approach it. I considered using the expansion approach:

t(n)=t(n)=4t(n/2)+2^n

=4(4t(n/4)+2^(n/2))+2^n

4(4((4t(n/8)+2^n/4)+2^(n/2))+2^n

... after several reccurence I assume this comes pattern (4(t(n/2^k)+square\_root(2)^(n) comes out, but I believe that is wrong. Even with knowing the pattern by using expansion, I am not sure how it would point that it lays in Θ(2^n).

# Answer
> 2 votes
Obviously, for sufficiently large $n$:

$$t(n) \ge 2^n$$

To show that $t(n)$ is $\Theta(2^n)$, all we need to show is there exists some constant $c$ such that for sufficiently large $n$:

$$t(n) \le c\\,2^n$$

If we want to do this by induction on $n$, consider what you'd need to prove the inductive step. Suppose $t(n/2) \le c\\,2^{\frac{n}{2}}$. Then:

$$t(n) \le c\\,2^{\frac{n}{2}} + 2^n$$

So we'd like to find a $c$ such that $c\\,2^{\frac{n}{2}} + 2^n \le c\\,2^n$, that is:

$$c \ge \frac{2^n}{2^n - 2^{\frac{n}{2}}}$$

As $n \rightarrow \infty$, the right-hand side approaches $1$, so pick any such $c\>1$ that makes your base case correct, and the proof should be straightforward.

# Answer
> 0 votes
Alternatively, you can substitute

$$n = \log{(m)} \tag{1}$$

Then

$$2^n = 2^{\log{(m)}} = m \tag{2}$$

Our original problem becomes

$$t(n) = 4t(\underbrace{n/2}\_{ \log{(m)} / 2\\\=\log{(m)}-\log{(2)}\\\=\log{(m)}-1 }) + 2^n \tag{3}$$ $$t(\log{(m)}) = 4 t(\log{(m)}-1)+m \tag{4}$$

At this point, we can substitute $n$ back in place of $\log{(m)}$:

$$t(n) = 4 t(n-1)+m \tag{5}$$

Since $t(1) = 1$, we have

$$t(2) = 4t(1) + m = m+4 \tag{6}$$ $$t(3) = 4t(2) + m = 4(m+4) + m = 4m + m + 16 \tag{7}$$ $$t(4) = 4t(3) + m = 4(4m + m + 16) + m = 4^2m + 4m + m + 64 \tag{8}$$

You can probably see a pattern at this point. Consider that we have

$$t(n) = \left( \sum\_{k=1}^{n-2}{4^k m} \right) + 4^{n-1} \tag{9}$$ $$t(n) = \left( \frac{1-4^{n-1}}{1-4}m \right) + 4^{n-1} \tag{10}$$

Finally, substituting $m = 2^n$ from $(2)$

$$t(n) = \left( \frac{1-4^{n-1}}{1-4}2^n \right) + 4^{n-1} \tag{11}$$

Alternatively, we know that

$$\left( \sum\_{k=1}^{n-2}{4^k m} \right) \in O(4^{n-2}) \tag{12}$$

So, combining $(9)$ and $(12)$, we have

$$t(n) = O(4^{n-2}) + 4^{n-1} \tag{13}$$

and can conclude that $t(n) \in O(4^{n-1})$.

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


title: Definition of M-type in type theory

text:
# Question
Title: Definition of M-type in type theory
According to nLab, M-types are the dual of W-types. What are the introduction and elimination rules for M-types?

**Edit:** For example, the formation/introduction/elimination rules for W-types are:

$$\frac{A:Type\quad x:A⊦B:Type}{(W x:A)B(x):Type}-\text{W-Formation}$$

$$\frac{a:A\quad t:B(a)\rightarrow W}{sup(a,t):W}-\text{W-Introduction}$$

$$\frac{w:W⊦C(w):Type\\ x:A,u:B(x)\rightarrow W, v:(\Pi y:B(x))C(u(y))⊦c(x,u,v)C(sup(x,u))}{w:W⊦wrec(w,c):C(w)}-\text{W-Elimination}$$

I'm wondering what the corresponding rules for M-types are.

# Answer
> 1 votes
As far as I can tell, these are the rules:

$$\frac{A:Type\quad x:A⊦B:Type}{(M x:A)B(x):Type}-\text{M-Formation}$$

$$\frac{C:Type\quad t: C\rightarrow \Sigma(a: A)(B\[a / a\]\rightarrow C)\quad c:C}{unfold(C,t,c):M}-\text{M-Introduction}$$

$$\frac{m:(M x:A)B(x)}{head(m):A\quad tail(m):B\[head(m)/a\]\rightarrow (M x:A)B(x)}-\text{M-Elimination}$$

---
Tags: type-theory, coinduction
---


# Question
Title: What's the time complexity of finding all size-$k$ combinations from a set of size $n$?
I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time complexity of finding all combinations of all sizes (involving ${n\choose 1}+{n\choose 2}+...{n\choose n} $ operations)? I need to add a remark on this in a project of mine, but I have zero training or background in computer science.

My guess is that the time complexity of the former is $O({n\choose k})$ and that the time complexity of the latter is $O({n\choose 1}+{n\choose 2}+...{n\choose n})$. Is this correct?

It would be great if you could add some intuition in your explanation. Thanks!

# Answer
Your first guess is correct- the time complexity of finding all size-k combinations is $O({n\choose k})$. This can be done by first ordering your set, and then selecting each element from this set in turn, and combining it with each size-`k-1` combination of elements ordered to be *after* the element itself, recursively.

Regarding the second question- the worst-case time complexity to find all combinations of all sizes is indeed greater, and your guess is *almost* correct. Technically, we need to count the empty set / combination of 0 elements, which there is exactly one of, so $O({n\choose 0}+{n\choose 1}+...{n\choose n})$, which simplifies to merely $O({2^n})$.
> 2 votes

---
Tags: time-complexity, combinatorics
---


# Question
Title: is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?
is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?

# Answer
> 0 votes
Suppose $f(n)=\sqrt{\frac{1}{n}}$, and $g(n)=n$. It's clear that $f(n)=\mathcal{O}(g(n)).$ Let $h(n)=\sqrt{\frac{1}{n}}$ therefore $$f(h(n))=\sqrt\[4\]{n}$$ and$$g(n)=\sqrt{\frac{1}{n}}.$$

Obviously $$f(h(n))\neq\mathcal{O}(g(h(n))).$$

Note that if $\lim\_{n\to \infty }h(n)=+\infty$ then we can conclude that $$f(h(n))=\mathcal{O}(g(h(n))).$$

# Answer
> 1 votes
Formally it's easy to bring counterexample: suppose $f(1)=1$, $g(1)=0$ and then, for other values of argument, $f, g$ are any pair of non-zero functions with property $f(n)\in O(g(n))$. Now taking $h(n)=1,\forall n \in \mathbb{N}$ makes impossible $f(h(n)) \in O(g(h(n)))$.

On other hand, for example, if $h$ is strictly increasing function, then your claim will be true, because we obtain property for subsequence from sequence.

**Addition.**

And about question about invertibility of $h$. If we consider counterexample (from comments below) $f=g=h=1, \forall n \in \mathbb{N}$, then implication $$f(n)\in O(g(n)) \Rightarrow f(h(n)) \in O(g(h(n)))$$ holds for brought triple, but $h$ is not invertible.

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: Easy-to-prove example of non-contextual language
When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next level (because some very easy grammar can be described).

For instance, after having studying for a while type-3 (regular grammars), you can easily prove that $\\{a^n b^n\\}$ or $\\{ww^R\\}$ are not regular (by using the pumping lemma for the first one, and the pigeonhole principle on the various states of a finite automaton for the second one); but simple type-2 grammars can be described for the very same language.

Now jumping to the type-2 (context-free frammars), you finally encounter $\\{a^nb^nc^n\\}$ and use a variant of the pumping lemma to show the language can't be context-free; again, a simple context-sensitive grammar can be described.

But I have no good example for the next step; *is there some easy proof that such or such language can't be context-sensitive while a rather simple unrestricted grammar (or a Turing Machine for the same language) could be described for it?*

I think the following question Is there an example of a recursive language which is not context sensitive? is close to mine, but doesn't focus on the same aspect.

# Answer
> 1 votes
Since nobody answered my question yet, I have my own try; I would be happy to have comments about it.

Since context-sensitive languages are accepted by linear bounded automata, finding minimalist toy examples of languages which are not context sensitive is not easy, because such automata are already quite powerful.

However, starting from the previous fact, and remembering that:

> PSPACE is a strict superset of the set of context-sensitive languages.

(source: https://en.wikipedia.org/wiki/PSPACE)

we can have a look a list of complete PSPACE-problems for finding an idea.

Unfortunately, many PSPACE-complete puzzles are 2D board games (which could be encoded into words of a language, but that wouldn't exactly match the "minimalist" requirement of my initial question), but looking carefully at the list we notice the generalized geography game which can probably be turned into a more or less easy to describe language:

I would be happy to have people simplify my proposal, but here is it.

Let $L$ be a language over three symbols: $a$, $b$ and a separator $","$. Words of this language are split into a list of non-empty substrings made of $a$ and $b$ symbols (splitting obviously occurs at the $","$ symbol locations). We require also the resulting substrings to be of even length. For instance the word `aa,baba,bbaa` follows the previous requirements. Let's call "country names" such substrings.

Each word in $L$ describes a game, and two players will pick in turn an available country name (no repetition will be allowed). A country name $B$ may follow another one $A$ $iff$ the second half of $A$ matches the first half of $B$. Sizes may differ, for instance $aabb$ may be followed by $bbbaab$ (but not by $abbbbb$ because only the $bb$ part of $aabb$ is taken into account).

A word is in $L$ if the described game is a winning game for the first player. Here is an example of a word in $L$: `ab,baba,bb` (initial player can pick the second or the third country name and win). Another different example is `ab,aa`.

I must admit that the "easy to prove" requirement is not fullfilled, but maybe my attempt could give ideas for other answers. Is everything else correct here?

---
Tags: formal-grammars, context-sensitive, chomsky-hierarchy
---


# Question
Title: Is there an algorithm to solve the following point clustering problem?
According to this post

Given $n$ points $P=\\{p\_1,p\_2,\dots,p\_n\\}$ in 2D space, and a matrix $D^{n\times n}$ with the distances between each pair of points, we want to partition the points into two clusters so as to minimize the clusters' diameters.

This can be formulated as an integer programming problem as follows:

* Let the diameter of first cluster $C\_1$ be $r\_1$.
* Let the diameter of the second cluster $C\_2$ be $r\_2$.
* For all points $p\_i$, let $x\_i=1$ if $p\_i \in C\_1$, else $x\_i=-1$.
* Determine $min\hspace{4pt} r\_1+r\_2$ such that
    + $\frac{1}{2}(x\_i+x\_j) D(i,j)\leq r\_1 \hspace{5pt}\forall p\_i,p\_j$
    + $-\frac{1}{2}(x\_i+x\_j) D(i,j)\leq r\_2 \hspace{5pt}\forall p\_i,p\_j$
    + $x\_i\in\\{-1,1\\}.$

My questions: is there a way to relax above ILP to find a approximation factor, and after relation how i can find the approximation factor?

# Answer
Consider the natural LP relaxation of this problem, i.e., $ -1 \leq x\_{i} \leq 1$ for every $x\_i \in \\{x\_1,\dotsc,x\_n\\}$.

Then, using the relaxation techniques, no approximation algorithm is possible since the integrality gap for this LP is $\infty$.

**Proof:** Consider any instance of this problem that has a non-zero cost. Then, in the relaxed LP, you make $x\_i = 0$ for every $x\_i \in \\{x\_1,\dotsc,x\_n\\}$. The optimal cost of the fractional solution will be $0$. Here the ratio of the optimal integral to the fractional solution is $\infty$; therefore the integrality gap is $\infty$.

Read more about integrality gap here.
> 1 votes

---
Tags: algorithms, computational-geometry, linear-programming
---


# Question
Title: Test whether words of less a's than b's or c's but not at the same time is context-free
I want to test whether $L= \\{w\in\\{a,b,c\\}^\* \mid |w|\_a\<|w|\_b \text{ or } |w|\_a\<|w|\_c,\text{ but not at the same time} \\}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L\_1=\\{a^nb^{n+1}c^n\mid n\ge0 \\}$ and $L\_2=\\{a^nb^nc^{n+1}\mid n\ge0 \\}$, for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?

# Answer
> 1 votes
In fact, you have identified a tip!

Let me make it more explicit. Suppose $L$ is context-free and $p\>0$ is a pumping length for it as in the pumping lemma for context-free language. Try pumping up or down the word $a^pb^{p+1}c^p$ out of $L$.

(You can also pump up or down the word $a^pb^pc^{p+1}$ out of $L$.)

---
Tags: formal-languages, context-free
---


# Question
Title: What is the computational complexity in big O notation of an algorithm computing n^n?
I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we increase n by one bit, so the algorithm computing n^n has exponential computational complexity?

Second question, what is the computational complexity with respect to n of operations on the result n^n, such as multiplying n^n by a number of similar size?

n can be a large number, so I guess multiplication should not be considered O(1), am I wrong?

# Answer
> 1 votes
Let M(x) be the time needed to calculate the product of two x-but numbers. n^n is a number with n log n bits. Calculating n^n using repeated squaring, the last product takes M(n log n). All the earlier products needed take M(n/2 log n), M(n/4 log n) etc, and this sums up to roughly 2 M(n log n). A bit more, because we’ll need some multiplications by n, which are quite fast.

So roughly 2 M(n log n), and M(x) is O(x log x), so O(n log^2 n). There may be some small corrections needed.

---
Tags: complexity-theory, time-complexity, big-o-notation
---


# Question
Title: How many unique Huffman codes can you make. Image I has size 256x256 and has pixels of values 50,100 and 200
Let I (M x N) be an image made only of 3 pixels, how many unique Huffman code can you make (example: Image I has size 256x256, and has pixels of values 50,100 and 200).

If someone can help me how to solve this problem or give me a hint.

I get it there are 6 unique Huffman codes : 0,10,11 or 1,00,01, is the solution correct?

# Answer
> 0 votes
If there are only three possible values, all possible Huffman codes have symbol lengths 1, 2, 2. One value has a 1 bit symbol which is 0 or 1, that’s 6 choices. Then we know the two possible 2 but symbols; one of the remaining two values uses one code, and the other value uses the other. 2 more choices, so a total of 12 choices.

---
Tags: image-processing, huffman-coding, digital-image-processing
---


title: All 1D lines overlap each other

text:
# Question
Title: All 1D lines overlap each other
I want to verify the correctness of this algorithm.

Problem: given a list of intervals, where the first index is greater than the second, determine if every interval overlaps with every other interval.

Examples

```
----
  ----
True

--------
  --
  -
True

----
    ---
False

-----
 ---
-
False, 3rd line does not overlap with second

```

This Typescript solution finds the maximum start and minimum end of all intervals. Then it checks that every interval overlaps the max start and min end.

```
const overlaps = ([min1, max1]: [number, number], [min2, max2]: [number, number]): boolean => {
    const overlapDist = Math.max(0, Math.min(max1, max2) - Math.max(min1, min2))
    return overlapDist > 0
}

export const allOverlap = (intervals: [number, number][]): boolean => {
    const [maxStart, minEnd] = intervals.reduce(([maxStart, minEnd], [start, end]) => {
        const ms = (start > maxStart) ? start : maxStart
        const me = (end < minEnd) ? end : minEnd
        return [ms, me]

    }, [-Infinity, Infinity])

    if (minEnd < maxStart)
        return false

    for (const interval of intervals) {
        if (!overlaps([maxStart, minEnd], interval))
            return false
    }

    return true
}

```

From my tests, this seems to work. However, I am unsure how to prove its correctness.

# Answer
> 1 votes
Let $I\_{max}$ be the interval with max\_start and $I\_{min}$ be the interval with min\_end.

**Statement:** All intervals overlap each other if and only if all intervals contain max\_start and min\_end

**Proof: (\<-)** This direction is easy. If all intervals contain max\_start and min\_end, then they all overlap each other at max\_start and min\_end.

**(-\>)** (Using Contraposition) Suppose some interval $I$ does not contain max\_start. We also know that start time of $I$ is smaller than max\_start. It means that it will not overlap with $I\_{max}$ since it will end earlier than $I\_{max}$. Similarly, you can show that if an interval does not contain min\_end, it will not overlap with $I\_{min}$.

---
Tags: algorithms
---


# Question
Title: Query sum of values between lo and hi for a stream of numbers
Suppose you have a stream of incoming numbers that you're storing and at any given instant in time, you want to query the sum of values between a given `lo` and `hi` in the stream you've read thus far.

It it possible to solve this problem with segment trees?

The only solution I could come up with is either O(n) insertion and O(log n) query (using a sorted array and prefix sum) or O(log n) insertion and O(n) query (using a binary search tree).

# Answer
> 1 votes
Use an AVL tree $T$ to store the incoming numbers. At every node, $v \in T$ also store the sum of the values of all the nodes in the subtree rooted at $v$. The structure is more like a segment tree.

A range query can be easily answered in $O(\log n)$ time.

For the insertion operation, use the AVL insertion. It takes $O(\log n)$ time. Let $v$ be the newly added node and $u$ be the unbalanced node. Then, you will need to update the sum values of the children and grand children nodes of $u$. That constitutes $O(1)$ update operations. You also need to change the sum values on the nodes that appear on the path from root to $v$. Therefore, this operation also takes $O(\log n)$ time.

---

Maybe a Dynamic Segment tree is a better term for it.

---
Tags: trees
---


title: Computation branches on NTM

text:
# Question
Title: Computation branches on NTM
I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string.

$\text{Start: }(q\_0) 011101 $

$0(q\_3)11101$

$(q\_1)011101$

$a) 0(q\_{rej}) 11101 \\:\\:\\: b) 0(q\_{acc}) 11101$

My questions are:

* Does the T.M continues on $b) 0(q\_acc) 11101$ and reads a $1$, thus going to $q\_2$ or it halts whenever it hits an accepting or rejecting state?
* Does the T.M accept the string above?

# Answer
The final states of a Turing machine (deterministic or not) have immediate effect and terminate the current computation. In your example, you have two final states $q\_{acc}$ and $q\_{rej}$ which will terminate any computation that reaches one of those state.

Now since there exists a computation that reaches the state $q\_{acc}$, your non-deterministic Turing machine will terminate and accept the input. Therefore, your input $w = 011101$ will be accepted.
> 0 votes

---
Tags: turing-machines, computability, nondeterminism
---


title: Can I multiply Big-O time complexities?

text:
# Question
Title: Can I multiply Big-O time complexities?
Can I multiply Big-O time complexities?

For example: $O(n) \cdot O(n) = O(n^2)$?

UPDATE:

The question came from my observation that different sources analyze their algorithms in different ways. For example, some use the following $O(n \cdot n + n \cdot log (n) )$ notation and some more like $O(n) \cdot O(n) + O(n) \cdot O(log (n))$ notation. I was wondering if it is equivalent notations.

# Answer
Yes, you can and yes, it is.

Considering, for example, the non-negative case, we have a more general property: $$O(f)\cdot O(g) = O(f\cdot g )$$ Let's take $ \varphi \in O(f) \cdot O(g) $. Then we have $\varphi = \varphi\_{1} \cdot \varphi\_{2}$ where $$\exists C\_{1} \> 0, \exists N\_{1} \in \mathbb{N}, \forall n \> N\_{1},\ \varphi\_{1} \leqslant C\_{1} \cdot f $$ $$\exists C\_{2} \> 0, \exists N\_{2} \in \mathbb{N},\ \forall n \> N\_{2},\ \varphi\_{2} \leqslant C\_{2} \cdot g $$ From above $\varphi = \varphi\_{1} \cdot \varphi\_{2} \leqslant C\_{1} \cdot f \cdot C\_{2} \cdot g = C\_{1} \cdot C\_{2} \cdot f \cdot g $ when $ n\>N=max(N\_{1},N\_{2}) $.

Accordingly, we can also see that there is a second general property: $$O(f)+O(g) = O(f+ g )$$ The proof uses the same technique.

**Definitions:** $$O(f)\cdot O(g) = \left\lbrace a\cdot b \colon (a,b)\in O(f)\times O(g) \right\rbrace $$ $$O(f)+O(g) = \left\lbrace a + b \colon (a,b)\in O(f)\times O(g) \right\rbrace $$
> 20 votes

# Answer
It's an abuse of notation.

$O(n)$ is a set of functions.

So $O(n)\*O(n)$ is not really defined. $O(n)\times O(n)$ is defined, but it is defined as cartesian products of the set of functions in $O(n)$ by itself. This is probably not what you are after.

Within the context of algorithm analysis most would interpret $O(f)\*O(g)$ to mean that we do some operation a number of time bounded by $f$, and each operation takes relevant resource (e.g. time or space) bounded by $g$. By that interpretation $O(f)\*O(g)\subset O(f\*g)$
> 12 votes

---
Tags: algorithm-analysis, big-o-notation
---


# Question
Title: How to use pumping lemma on languages that do not follow a strict structure?
Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem.

For example, I have a language: $$L = \\{w \mid w \in \\{0, 1\\}^\*,\ \\#\_0\ge\\#\_1\\}$$

As you can see, 0's and 1's can occur in any order, I have found it easy to prove this is not regular using the pumping lemma, for example the string: $0^p1^p$ can be pumped easily.

Proving that this is not context-free, as I believe it is not context-free, has me stumped.

**EDIT**

Thanks to nir shahar, Using their example I was able to work out the issue I was having. I was able to split my PDA into two sections, one where the number of 0's was greater than the number of ones, and one where the number of 1's was greater than the number of 0's. It sort of makes a mirrored image that accounts for all possibilities. Thank you so much for the help!

# Answer
> 0 votes
The language is context free.

Here is a hint: as you have proved, it isn't regular. Therefore, when you try to construct a PDA for this language you will have to use the stack. Try to think how to count numbers using the stack, maybe start with a simpler language like $\\{0^n1^m\mid n\ge m\\}$. This is the main "crux" of your problem :)

---
Tags: context-free, pumping-lemma
---


# Question
Title: Prove that the expected length $E [n_{h(k)}]$ of the list containing key $k $ is at most $1 + \alpha$
**Theorem**: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key $k$ is not in the table, then the expected length $E \[n\_{h(k)}\]$ of the list that key $k$ hashes to is at most $\alpha$. If key $k$ is in the table, then the expected length $E \[n\_{h(k)}\]$ of the list containing key $k$ is at most $1 + \alpha$.

**Solution**: (Courtesy to Introduction to Algorithms book):

We note that the expectations here are over the choice of the hash function, and do not depend on any assumptions about the distribution of the keys. For each pair $k$ and $l$ of distinct keys, define the indicator random variable $ X\_{kl}=I\\{h(k) = h(l)\\}$. Since by definition, a single pair of keys collides with probability at most 1/m, we have $Pr\\{h(k) = h(l)\\}\le \frac{1}{m}$, so $E\[X\_{kl}\] \le \frac{1}{m}$.

Next we define, for each key $k$, the random variable $ Y\_k$ that equals the number of keys other than $k$ that hash to the same slot as $k$, so that

$$ Y\_k=\sum\_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{X\_{kl}} $$

Thus we have $$ E\left\[ Y\_k \right\] =E\left\[ \sum\_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{X\_{kl}} \right\] \le \sum\_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{\frac{1}{m}} $$

So, have 2 cases here,

1. When $k$ is **NOT** table $T$: If $k \notin T$ , then $n\_{h(k)} = Y\_k$ and $|{l : l \in T ~and~ l \ne k}| = n$. Thus $ E \[n\_{h(k)}\] = E\[Y\_k\] \le n/m = \alpha$, where $h(k)$ is the hash function that hashes $k$ to a slot. $h(k)$ is a simple division method.
2. When $k$ in table $T$: If $k \in T$ , then because key $k$ appears in list $T\[h\_{(k)}\]$ and the count $Y\_k$ does not include key $k$, we have $n\_{h(k)} = Y\_k +1$ and $|{l : l ∈ T ~and~ l \ne k}| = n −1$. Thus $E\[n\_{h(k)}\] = E\[Y\_k\]+1 \le (n−1)/m+1 = 1+ \alpha −1/m \< 1 + \alpha$.

**Problem**: I would like to discuss case 1 above please. Why this is the case that we have $ E \[n\_{h(k)}\] = E\[Y\_k\] \le n/m = \alpha$ please?

# Answer
Let $I$ be the set of input keys. We have $|I| = n$.

If $k$ is not in the table, it means that $k \notin I$. If $k$ is in the table it means that $k \in I$.

Let $S\_h$ be the slot in the table that key $k$ maps to, if the hash function $h$ is selected. Our aim is to find the expected length of $S\_h$. Note that we are taking expectation over the choice of the hash function $h$ picked from the family $\mathcal{H}$, and not the expectation over $I$. The set of input keys $I$ is fixed for this problem.

Consider the case when $k \in I$. In this case, there are $n-1$ other keys in $I$. Whatever be the choice of hash function $h$, key $k$ always maps to $S\_{h}$. Therefore, it accounts to a length of $1$ at $S\_h$. To find the expected number of keys in $I \setminus \\{k\\}$ that maps to the same slot as $k$, you simply take the sum of expectation for every key in $I \setminus \\{k\\}$. It is simply at most $\frac{|I \setminus \\{k\\} | }{m}$ using linearity of expectation as stated in your question. Therefore, the expected length of $S\_h$ is at most $1 + \frac{|I \setminus \\{k\\} | }{m} = 1 + (n-1)/m \leq 1 + n/m = 1+\alpha$.

Similarly, you can solve for the case when $k \notin I$. There you simply take the sum of expectation for every key in $I \setminus \\{k\\} = I$. Therefore, the expected length of $S\_h$ is at most $\frac{|I| }{m} = n/m = \alpha$.
> 1 votes

---
Tags: algorithms, hash
---


# Question
Title: Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?
I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition:

> A grammar G is ambiguous if some sentence in L(G) has more than one rightmost (or leftmost) derivation.

One of the exercises asks the following:

> *When asked about the definition of an unambiguous context-free grammar on an exam, two students gave different answers. The first defined it as “a grammar where each sentence has a unique syntax tree by leftmost derivation.” The second defined it as “a grammar where each sentence has a unique syntax tree by any derivation.” Which one is correct?*

I tried to deduce the definition of **unambiguity** by negating the definition of ambiguity the chapter has given me:

A grammar G is unambiguous if for every sentence in L(G) there is one and only one rightmost (**and** leftmost) derivation.

I changed the **or** to an **and** because not (a or b) = not a and not b

However most definition of ambiguity I managed to find online states that

> A grammar G is unambiguous if for every sentence in L(G) there is one and only one rightmost (**or** leftmost) derivation.

I've also found that

> If a grammar is unambiguous, that means that the rightmost derivation and the leftmost derivation of every sentence represent in the same parse tree.

Reading the last two quotes confuses me in many ways:

* Does the **or** in the **definition of unambiguity** implies that there can exist an **unambiguous** grammar where for every sentence of it, there is only one leftmost derivation, **but more than one rightmost derivation**?
* Does the last quote implies that I only need to find out if for a given grammar, every sentence of it has only one leftmost **or** rightmost derivation, **because if there is, I don't need to find if the other derivation is unique because they're the same**?
* If the statement above is correct, does that mean that only the second student in the excercise are correct? Or that both students are correct?
* Some other definitions of unambiguity state only about leftmost derivation. Which is correct?

Thanks in advance to everyone who reads this.

# Answer
In a word, no.

Every tree has exactly one left-to-right depth-first traverse and exactly one right-to-left depth-first traverse, either of which can be used to unambiguously recreate the original tree.

Since the leftmost derivation of a sentence is just another way of writing the left-to-right depth-first traverse of the parse tree for that sentence (and analogously the rightmost derivation), it is only possible for a sentence to have more than one rightmost derivation if there is more than one parse tree, each of which corresponds to a different leftmost derivation.

In other words, for a given sentence generated by a given grammar, the following are exactly the same number:

* The number of different leftmost derivations of the sentence.
* The number of different rightmost derivations of the sentence.
* The number of parse trees whose leaves spell out the sentence.

If that number is one for every sentence generated by the grammar, then the grammar is unambiguous.

So you can use whichever definition for "unambiguous" you find most convenient.
> 1 votes

---
Tags: context-free, formal-grammars, compilers, ambiguity, derivation
---


# Question
Title: Can one brute force entries to create the whole file?
I want to know if one can brute-force a large list of entries (\>10,00,000) in linear time to form a whole file.
For example:
I have an ebook and i extract all the words and symbols from that ebook.
Then I count the frequency of all words and symbols.
Then I get the binary representation of file and I hash it with SHA256.
Then I will create a program that take the frequency of all symbols and words to form meaningful sentences from it (a kind of brute-force with grammatical expressions as inputs).
Then I will hash every possible structure generated by the program to find one which matches the hash of the original file.
So, will this kind of brute-force be any better (faster) than the brute-force with just a hash.
A normal brute-force may involve:
Brute-forcing all permutaions of all n bit binary segments, which formed the ebook.
Problem is:
1.That it is not possible to brute-force these segments in less time (May require more time than the current age of the universe).
2. Computing power to complete this task is way more than what quantum computers have today.
3. Rate of Collision is very high when one is mapping a larger set of entries to a smaller one.
So, I think brute-forcing with english words with grammatical restrictions (how sentences are formed as the word is more likely to be 'I have' and not 'I me') will require way less computing power and time as opposed to a normal brute-force which may have n! or 2^n permutations (2^n ,in case of binary). Is this method as inefficient as normal brute-force attack (or worst) ?
Note:
Sample space is the set of english words such as the, are, I etc.
Will this kind of brute-force take months if not years ?
Will it really generate way less files (as grammatical restrictions are there) as opposed to a n MB file which is made up of n bytes hence will have 2^n permutations ?
Is this as impractical as brute forcing a file with just a hash ?
Will Dynamic programming be any helpful in this task ?

# Answer
> 1 votes
There have been many estimates of the entropy of the English language, ranging (depending on how you define it, how you measure it, and which corpus you use) between slightly less than 1 bit per character to close to 5 bits per character.

This means that even a very short text such as your question already has between 1500 and 7500 bits of entropy.

Even if we assume only 0.5 bits per character, then a 512 character long text will already have more entropy than the resulting hash. Which means even this short answer already has more entropy than the resulting hash.

---
Tags: hash
---


# Question
Title: Proving O(log n) bound for the number of iterations when we select the average as the pivot
## Motivation

So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: `O(k)` and `Ω(log(k))`. However, my rough logic says that we should be able to prove a tighter bound of `O(min(k,log(n)))`, but I was unable to prove it. Moreover it seems like an interesting, general-case problem.

---

To save time for the reader I have changed my space complexity problem to an equivalent complexity problem (the complexity of a function \[not of space or time\]):

## Data:

Array of size `k`; where elements, `e`, are unique integers: `0 <= e < n`, for some `n`.

## Events:

Find the `average` (rounded down) of the elements.
Randomly discard either all the elements `>` than the average, or all the elements `<=` the average.
We then do the same thing to the reduced array size.
We keep repeating the above steps until the array is size 1.

## My Question:

Is it `O(min(k,log(n)))` on the number of times `average` is counted? and if so, how do we prove it? (**NOTE** that we don't care about the time it takes to calculate the average or remove the elements. This is because this questions is deliberately designed to be equivalent to my space-complexity problem.)

---

## My thoughts:

It seems really intuitive that it's `O(min(k,log(n)))` because if `k` is `n`, then taking the `average` will always divide the elements in half. However, I can't seem to prove that it doesn't sometimes perform worse when `k < n`.

Thinking about this a bit we recognise that having outliers is really what makes for bad performance, so I try to imagine a worst-case scenario:

`array = [1, 2, ..., (x-2), (x-1), (n-1)]`, where `(x-1) < average < (n-1)`

In this scenario, we in worst-case reduce the array size to `x-1`; however, by increasing `k` by adding any number of elements, `e`: `(x-1) < e < (n-1)`, the worst-case array size (for the next iteration) is still `x-1`.

Moreover:

`average = (x(x-1)/2 + n-1)/x`

Thinking about the complexity, for a given `n`, worst case `x`:

`x = average`

=\> `x^2 - x^2/2 + x/2 = n-1`
=\> `O(x) = O(sqrt(n))`

and here `x` represents the biggest sub-size.

So in this artificial "worst case" scenario, we get O(sub-array size) = `O(min(k,sqrt(n)))`, which kind of implies that the overall complexity = `O(min(k,log(sqrt(n)))) = O(min(k,log(n)))`.

However, this proof is quite informal and I'm not sure how to show that this genuinely represents the worst-case scenario.

# Answer
We introduce a weight measure for $S$, a set of numbers with respect to its average, namely: $w(S) = \sum\_{s\in S} |s-avg(S)|$. The measure $w(S)$ expresses the total distance to the average. Based on this weight we will prove the number of iterations is in $O(\log\ n)$.

If we apply one iteration of your described algorithm on a set $S$ we obtain either the set $S\_\leq = \\{s \leq avg(S) \mid s\in S\\} $ or the set $S\_\> = \\{s\>avg(S) \mid s\in S\\}$. Now we show that $w(S\_\leq)\leq \frac{w(S)}{2}$ and $w(S\_\>) \leq \frac{w(S)}{2}$. The weight of both sets $S\_\leq, S\_\>$ w.r.t. the old average of $S$ is equal to: $$\sum\_{s\in S\_\leq} |s-avg(S)| = \sum\_{s\in S\_\>} |s-avg(S)| = \frac{w(S)}{2},$$

which follows from the observation that $$\sum\_{s\in S} (s - avg(S)) = \sum\_{s\in S} s - |S|\*avg(S) = \sum\_{s\in S} s - \sum\_{s\in S} s = 0.$$

By the construction of the sets $S\_\leq$, $S\_\>$ only contain negative, and positive terms in $s-avg(S)$, and their sum is the total.

Note that $w(S\_\leq) \leq \sum\_{s\in S\_\leq} |s-avg(S)|$ since $avg(S\_\leq)\leq avg(S)$ and symmetrical for the other case.

To complete the complexity bound we confirm that

* $w(S)\in O(n^2)$ initially since $S\subseteq\\{0,\dots,n-1\\}$.

* if $w(S)\leq 1$ it is a base case in $O(1)$ (only 1 more split).
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, recursion, binary-search
---


# Question
Title: What are some uses of the Thue-Morse sequence in computer science?
Note: I come from a mathematics background.

---

The Thue-Morse sequence $t\_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is even, $1$ otherwise.

A definition that is closer to computer science states that $t\_n$ is the binary sequence obtained by starting with $0$ and successively appending the boolean complement of the sequence obtained so far.

Thus, $t\_n$ begins $0,1,1,0,1,0,0,1,\ldots$

This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:

* The Thue-Morse sequence is *automatic*, i.e., the sequence is fully characterized by a finite automaton,
* It is a binary sequence.

> What theoretic or practical applications of the Thue-Morse sequence are there in computer science?

# Answer
> 4 votes
I don't know if this counts as an application but at least it shows up. When using a polynomial rolling hash, it's tempting to do it modulo $2^{32}$ or $2^{64}$ (depending on the word size of the computer) since on most modern architectures addition and multiplication of integers just handle overflows this way, saving time. This method will fail often on Thue-Morse-like strings (like `ABBABAAB...`), as explained here. I remember not understanding the factorization of $T$ a few years ago, the key is the recurrence relation $t\_{2n} = t\_n$, $t\_{2n+1} = 1-t\_n$

Alternative explanation of the factorization: from the "append the negated sequence" definition one can directly see $\Pi\_n (1-x^{2^n})$ , since each each term does exactly that.

# Answer
> 3 votes
The problem of computing $t\_N$ given $N$ is famous in theoretical computer science as the PARITY problem and is a well-known example of a decision language that can be recognized by linear-size $O(\log n)$-depth circuits but cannot be recognized by polynomial-size circuits of constant depth; here $n$ is the length of the binary expansion of $N$.

Parity computation finds application in error-correction codes, to calculate a check bit to append to data (example). It is also useful in multiplying 0/1 matrices in the binary field GF(2) (where the add operation is $\oplus$ and the multiply operation is $\wedge$), since the inner product of, for example, $(a\_1, a\_2, a\_3, a\_4)$ with $(b\_1, b\_2, b\_3, b\_4)$ is $$ (a\_1 \wedge b\_1) \oplus (a\_2 \wedge b\_2) \oplus (a\_3 \wedge b\_3) \oplus (a\_4 \wedge b\_4), $$ which is just the parity of the bit-by-bit conjunction $a \wedge b$.

# Answer
> 3 votes
In the paper https://arxiv.org/abs/1408.5963 Thue-Morse sequence was used to construct a distributed algorithm which is non-local but halts on every finite network (input).

# Answer
> 1 votes
This is not an answer, but too long for a comment.

> so far I have not come across any applications in computer science. This surprises me, for the two following reasons:
>
> * The Thue-Morse sequence is *automatic*, i.e., the sequence is fully characterized by a finite automaton,
> * It is a binary sequence.

You may want to refine your criteria for what makes something applicable in computer science. These two properties don't seem like very good criteria:

* The fact that this sequence is *automatic* is true and does suggest studying it in the domain of computer science, but it's a very weak statement; most sequences (almost all that I am aware of) are computable.

Also, this sequence is not regular, so your statement that it is "characterized by a finite automaton" seems misleading.
* The fact that the sequence is binary means nothing, I don't see that as relevant to its applicability.

# Answer
> 0 votes
For coding test like this one :D. Using breadth first search could solve this but it soon eats up memory as *pos* grows large. Binary search works but Thue-Morse has the best runtime.

---

Consider a special family of Engineers and Doctors. This family has the following rules:

* Everybody has two children.
* The first child of an Engineer is an Engineer and the second child is a Doctor.
* The first child of a Doctor is a Doctor and the second child is an Engineer. All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

```
            E
       /         \
      E           D
    /   \        /  \
   E     D      D    E
  / \   / \    / \   / \
 E   D D   E  D   E E   D

```

Given the level and position of a person in the ancestor tree above, find the profession of the person. Note: in this tree first child is considered as left child, second - as right.

**Example:** For level = 3 and pos = 3, the output should be findProfession(level, pos) = "Doctor".

**Constraints:**

* 1 ≤ level ≤ 30
* 1 ≤ pos ≤ 2^(level - 1)

Note: this test is from codesignal.com

---
Tags: finite-automata, binary, applications
---


# Question
Title: Algorithm to Check for Upper Bound of Levenshtein Distance
I am looking for an algorithm that checks if the Levenshtein distance between two strings $s\_1$ and $s\_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating the Levenshtein distance, but I expect a possible efficiency gain in scenarios where $B$ \<\< $Levenshtein(s\_1, s\_2)$, because an algorithm not aiming to determine the actual distance, but just aiming to answer the question whether the distance is below $B$ or not, can terminate earlier, as soon as it becomes clear that the distance must surpass $B$.

For such an algorithm, I have the idea of using a recursive function which takes the parameters $s\_1$, $s\_2$ and $B$ checks if the first character of $s\_1$ and $s\_2$ are equal, and recursively calls itself (with a potentially decremented $B$ and accordingly adapted $s\_1$ and $s\_2$). The function would sort out all scenarios where $B$ falls below 0. (And of course, the function will make use of the trivial lower bounds of $Levenshtein(s\_1, s\_2)$.) If no recursion branch is left, the algorithm would terminate, asserting $Levenshtein(s\_1, s\_2) \geq B$.

But before reinventing the wheel, I wanted to ask if there are already existing solutions for my problem. I googled this and didn't find any, but maybe my google results were just polluted with the Levenshtein Distance Algorithms. If there is no such algorithm yet, is my approach a good idea, or are there more efficient ways which I oversee?

# Answer
> 1 votes
You may be interested in this implementation: https://github.com/fujimotos/polyleven

---
Tags: dynamic-programming, string-metrics, edit-distance
---


# Question
Title: Why XML dumps from Wikipedia are so compressed?
Few years ago I downloaded an XML dump of one of Wikipedia's fandom sites.
It was the XML datadump of Marvel Fandom.
The XML was zipped , size was 900 MB (approx).
But when I unzipped it , it was somewhere 10 - 11 GB big.
And according to Wiki Taxi (A software I used to convert those XML dump into readable format for offline reading) it had 1,50,000 pages (approx).
So, I want to know is :
Do they used any specific kind of algorithm to compress it ?
How they achieved so much compression, despite having 1,50,000 pages ?
Do wikipedia uses any "more compressible" XML syntax ?
Will converting ebooks to XML be any helpful in reduction of size of ebook ?

# Answer
There are two dumps available at https://marvel.fandom.com/wiki/Special:Statistics at the moment. The "current pages" dump is 1.6 GB uncompressed, 167 MB compressed, for a ratio of 9.5:1, and the "current pages and history" dump is 30 GB uncompressed, 552 MB compressed, for a ratio of 55:1.

Both are compressed using LZMA2, which is a standard, widely used algorithm. It's an LZ77 variant, meaning that if a string of bytes appears more than once within the window distance (here 16 MiB), all occurrences after the first are replaced with references to the first one, usually costing just a few bytes each time.

The full-history dump compresses so well because most page versions are very similar to each other, with only small parts changed. Most of the text of most versions can be compressed down to a reference to a previous version which takes just a few bytes.

The current-pages dump is highly compressible because it contains a lot of boilerplate text. For example, here's an excerpt from an image description:

```
| Others1     = [[Red Skull (1940s Impostor) (Earth-616)|1947's Unnamed Impostor]]; Red Skull (1940s Impostor) (Earth-616) from Captain America Comics Vol 1 61 Cover.jpg
| Others2     = [[Red Skull (1950s Impostor) (Earth-616)|1950's Unnamed Impostor]]; Red Skull (1950s Impostor) (Earth-616).jpg
| Others3     = Albert Malik (Earth-616); Albert Malik (Earth-616) from Amazing Spider-Man Vol 5 69 001.jpg
| Others4     = George Maxon (Earth-616); George Maxon (Earth-616) from Captain America Comics Vol 1 1 0002.jpg
| Others5     = [[Johann Shmidt (Heroes Reborn) (Earth-616)|Johann Shmidt<br>(Heroes Reborn)]]; Johann Shmidt (Heroes Reborn) (Earth-616).jpg
| Others6     = [[Red Skull (Tsum Tsum) (Earth-616)|Tsum Tsum]]; Red Skull (Tsum Tsum) (Earth-616) from Marvel Tsum Tsum Vol 1 4 0001.jpg
| Others7     = [[Red Skull (Earth-1610)|Captain America's Unnamed Son]]; Ultimate Comics Avengers Vol 1 1 Textless Red Skull Variant.jpg

```

It goes on up to `Others17`, and that's just part of the description, and there are probably similar descriptions on many other images. This is full of long duplicated strings that can be compressed to a few bytes after their first occurrence.

Even ordinary English text tends to compress fairly well for similar reasons.

> Will converting ebooks to XML be any helpful in reduction of size of ebook ?

No. But ebooks tend to be small anyway if they're just text.
> 3 votes

---
Tags: data-compression
---


# Question
Title: Hamiltonian cycle in $C_n^k$ in polynomial time for constant $k$?
Let $C\_n$ denote the cycle graph over $n$ vertices. Let $C\_n^k$ denote the $k$-th power of the cycle graph, or namely that for two vertices $i,j$, $(i,j)\in Edges(C\_n^k) \iff |i-j|\leq k$ for a constant $k$.

Now given a subgraph $G$ of $C\_n^k$, how can we find a hamiltonian cycle (if it exists) in $G$ in polynomial time (in $n$)?

I've tried solving this with DP but the best I've reached is $O(2^nn)$ which just matches the known DP for hamiltonian cycle. I would prefer hints over full answers.

# Answer
Addressing another question of OP:

Suppose $k$ is equal to $n$. If so, then $C\_{n}^{k}$ would be a complete graph. And, suppose if we could check if a Hamiltonian cycle exists in any subgraph $G$ of $C\_n^{k}$ in polynomial time (i.e., $poly(n,k)$), then it would mean that we can solve Hamiltonian Cycle problem in polynomial time on any graph with $n$ vertices.

Since the Hamiltonian Cycle problem is $\mathsf{NP}$-hard; therefore, the stated problem is also $\mathsf{NP}$-hard. In other words, it is hard to find a Hamiltonian cycle in $G$ in time polynomial in $k$ and $n$.
> 1 votes

# Answer
Here is an overkill solution:

Lemma: The subgraph $G$ has tree-width at most $2k$.

*Proof.* Treat all additions and subtractions in what follows in circular modulo arithmetic (for example $n+1 = 1$). Also assume $n\gg k$. Let $L\_j=\\{j-1, j-2, ..., j-2k\\}$ and $R\_j=\\{j+1, ..., j+2k\\}$. Then the path decomposition for $C\_n^k$ of $(L\_1\cup \\{1\\}\cup R\_1), (L\_1\cup \\{2\\} \cup R\_2), (L\_1\cup\\{3\\}\cup R\_3), ...$ is a path (tree) decomposition with width $2k$, and so the tree-width of $C\_n^k$ is at most $2k$ so a subgraph of $C\_n^k$ has tree-width at most $2k$.

Since the tree-width of $G$ is at most $2k$, then there is a $O(n^{O(k)})$ algorithm that finds a nice tree decomposition $T$ for $G$. We can then run the FPT hamiltonian cycle algorithm on $T$ to find a hamiltonian cycle for $G$ in $O(k^{O(k)}n)$ time.

Overall, the algorithm takes $O(n^{O(k)})$, which is polynomial time. I would still be interested in a polynomial time solution without a $k$ dependency, or even with dependency $k$ but simpler.
> 1 votes

---
Tags: hamiltonian-path, hamiltonian-circuit
---


# Question
Title: Checksum Algorithm that produces correct 16-bit checksum value for any given input
I need a checksum algorithm that produces the correct 16-bit checksum value for a given input. It's a packet recording from serial communication that I would like to reverse engineer.

I have two data files, one dataset1.txt, that checksum is the last 2 bytes in the hex, for example, first entry:

4573500506000004047a6e126100eed1f268eb2de68d20a2f05b24842ef0e379976596733f20ee9143936adf5536f230c24b00005ee8000000000000000000000000000000000000000000000000000000000093c1

Checksum (in hex): 93c1.

And the second dataset (where I suspect the same checksum algorithm is used) dataset2.txt. The checksum is known to be the fourth and fifth byte, for example, the first entry:

457304 ccba 0f8a231a

Checksum(in hex): ccba.

I am interested in the checksum algorithm for dataset1.txt (dataset2.txt is included, as it hopefully can provide some extra information).

If you think you have cracked it, drop me a message and I will provide a small testing dataset from which accuracy (in the case of ML methods, targeting 90%+ accuracy on unseen data) can be determined. In principle, any programming language can be used, but C-based syntax (C/C++/C#/Java) is preferred.

# Answer
That checksum matches (perhaps accidentally, but it does match) an lsb-first CRC16 using 0xB31C as the reflected polynomial. That's if the checksum is actually 0xC193 but stored in little-endian, which wouldn't be strange. The polynomial was found by brute force.

I don't see how to match that with dataset2 though. This match could be a total fluke. I could not find any reference to that polynomial, neither in its reflected form nor in its "unreflected" form. There are certainly also other ways to get that checksum from that data. However, the fact that a CRC16 solution exists is not meaningless, because it is not the case that any combination of data and a crc has a solution for a polynomial that produces that crc from that data. The certainty that the match is meaningful is not very high, but it is not zero.

Example C# code to compute this type of crc, not accelerated using a lookup table or anything fancy, just a basic implementation:

```
static ushort crc16(byte[] data)
{
    int crc = 0;

    for (int i = 0; i < data.Length; i++)
    {
        crc ^= data[i];
        for (int j = 0; j < 8; j++)
        {
            if ((crc & 1) != 0)
                crc = (crc >> 1) ^ 0xB31C;
            else
                crc = crc >> 1;
        }
    }

    return (ushort)crc;
}

```
> 0 votes

---
Tags: algorithms, data-structures, c
---


# Question
Title: Can 2 files have "same" "many" "different" types of hash?
I know that **hash collision** is possible with large number of files. But i want to know if **2** files can share "**many** , **different**" types of hash.
I have 2 hashes **SHA256** and **BLAKE256** (Both will result in **different** hashes)
For example:
File **A** have **SHA256** hash : jhsj8sd87a89sihd8d78a7... etc.
And **BLAKE256** : js8us8d8saa621g2h34hg... etc.
So what is the **probability** that a File **B** will have the same **SHA256** and **BLAKE256** when **hashed**.
And will chance of collision decreases with more hashes, Say **5**.
**Note** : Both the files **A** and **B** have exactly same size but different content.
I have read on internet about hash collision with 2 hashes. But here is the case of **4** hashes. **2** of File **A** and **2** of file **B**.
And both types are different, one is **SHA256** and one is **BLAKE256**.

# Answer
> 1 votes
If you use multiple hashes it can be viewed as if you had used a single hash. Lets say A is the hash of object using first hash function, and B is the hash of same object using a different function. Then you can consider a hash function which computes first A, then B, and then outputs its hash as (A,B). You can repeat this as many times as you want to obtain a single hash composed of n different hashes. Therefore no matter how many hash functions you use it will be the same as with a single hash, the only difference will be that the resulting hash will be larger, and thus the probability of two objects having the same hash will be lower (assuming that the individual hashes share no mutual information).

# Answer
> 0 votes
If you have say four 256-bit hashes, that’s the same as one 1024 but hash. If you examine all files of 1025 bits, there *must* be files with equal 1024 bit hashes.

Finding a “collision”, that is two files with identical hash, will be very very difficult. You’d need to perform about 2^512 operations to find a collision. For 256 bit hashes, there might be some maths that you could exploit to get a hash faster, but with 4 different hashes, such a weakness is unlikely to exist.

---
Tags: hash
---


# Question
Title: Can a non deterministic finite automaton go into infinite loop?
Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and quite intuitively one can verify that a DFA shall halt when the input string is exhausted.

Lately I came across a question as :

> State true/false:
>
> "Whether a finite state automaton halts on all inputs" is a decidable problem.

I came to the conclusion that the above statement is True, with the following thought process. Be it an $\epsilon$-NFA or DFA, every finite automata has an equivalent simplified DFA and hence it is this DFA which is bound to halt on all (finite) input.

Just as I mentioned above about $\epsilon$-NFA, I was wondering, that we can have an infinite loop in this finite automaton. Possibly using $\epsilon$ transitions as follows:

But the possible loop in the red path in the diagram is harmless (unlike a loop in Turing Machine TM), as it is just a parallel path, which me might not even consider while the parallel processing of the contemporary instances of NFA is going on.

I cannot possibly think of a situation of finite automata where it goes into a situation like TM. Is such a situation at all possible ?

# Answer
> 4 votes
Not really, unless you include TMs in some way or another in the "situation".

Any infinite loop in an NFA must constitute only of $\epsilon$ transitions (since the input is finite, if the loop would have "eaten up" some letters, it must also be finite). As you already know, its pretty easy to get rid of those epsilon transitions, so after we do it, the automaton will never have any other infinite loops.

I will highly recommend reading this for a few minutes, and try to understand the basic decidability properties of regular languages. In particular, we can decide whether two automatons accept the same language - which is something that is impossible when dealing with TMs instead.

Now lets talk about the question you saw - there isn't a good definition of "halting" for automatons, since they don't operate like TMs. Automatons accept a word only if there is a "good path" in the automaton's states for that word. Therefore, I think the question actually meant the following instead:

> Given an NFA, we can think of emulating it by running it in a step-by-step basis. Considering that, is it decidable to know whether on *all inputs*, the emulation of **this particular NFA** (and not an equivalent DFA) will *always* either accept, or will never have 0 "running threads" in the emulation?

Notice that this question, now talks about whether a **turing machine** (that emulates the NFA behavior) halts or not. This question is well defined, and it is not as trivial to solve it anymore (since you must use this NFA and not any other NFA\DFA).

---
Tags: turing-machines, automata, finite-automata, theory
---


title: Simplifying the Language of this DFA

text:
# Question
Title: Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0\*1(1+00+01)\*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)\*1(00)\*. But I just cannot derive Sipser's language from what I have obtained. Any help at all would be appreciated.

# Answer
> 1 votes
The automaton is deterministic, so any string over $\\{0,1\\}$ has a unique path.

We need at least one $1$ to move from $q\_1$ to the component where is the accepting state.

Immediately after reading $1$ we are always in accepting state $q\_2$.

Look at the *last* $1$ in the input. At that moment we accept in $q\_2$. To return to the accepting state, only reading $0$'s, we need an even number of $0$'s.

---
Tags: complexity-theory, regular-languages, finite-automata, regular-expressions
---


title: Number of comparisons in Binary search

text:
# Question
Title: Number of comparisons in Binary search
I know this question is very trivial to ask, but I have got some doubt while solving this problem.Code is given below

```
public class BinarySearch {
public static int binSearch(int a[], int x) { // a is sorted
int low = 0, high = a.length - 1;
while (low <= high) {
 int mid = (low + high) / 2;
 if (x < a[mid])
 high = mid - 1;
 else if (x > a[mid])
 low = mid + 1;
 else
 return mid;

}

return Integer.MIN_VALUE;

}

```

If we want to calculate the worst case **comparisons** of binary search,then

it will be $2 \log n+1$, because $\log n+1$ for checking `(low<=high)` and $\log n$ for `(x < a[mid])` or `if (x > a[mid])`.

Alright , i have no issue here , i can happily say that worst case comparison for Binary search is $2\log n +1$

---

I faced issue when i tried to solve the recurrence equation, given as-:

> $$T(n)=T(\frac{n}{2})+1$$
>
> $\text{Base Case}\\,\\,T(1)=1$

$T(\frac{n}{2})=T(\frac{n}{4})+1$

Generalizing the equation i got-:

$T(n)=T(\frac{n}{2^{k}})+1+1..+1(k \text{times})$

$T(n)=T(\frac{n}{2^{k}})+k$

> $\frac{n}{2^k}=1$
>
> $k=\log n$

So $T(n)=\log n+1$ What actually this value signifies? Is it Minimum number of comparison? Confused Please help me out

# Answer
The value that you've got is the number of searches required in the worst case by binary search. Each function call is responsible for only 1 search. And your recurrence relation justifies that. So the recurrence relation you wrote is for the number of searches. Indeed we require $\log n +1$ searches if it's a worst case. Take any $n$, say $n=7,8$, and try and see for yourself.
> 2 votes

# Answer
The recurrence is supposed to express the worst-case runtime of binary search on an input of size $n$ (the letter $T$ might stand for time). The range you have to search search is halved in each step, so you get the $T(n/2)$ term on the right side.

Most of the time people only count the comparisons of the data, not the extra comparison for the loop condition, so it takes 1 comparison to halve the search space. For your analysis you might want to write a $+2$ instead of the $+1$, since you do count the loop condition.

As we want to express the worst case runtime, we assume that the element is not in the array, so the recursion terminates only when there is just one element left. This provides us with the base case of $T(1)=1$.
> 1 votes

# Answer
It's an upper bound on the number of comparisons. It's not lower bound because in the best case, you find $x$ immediately (its the middle element), but in the worst case, $x$ isn't in the array, so you had to dive down till the base case in the recursion.
> 0 votes

# Answer
@laura the `2logn+1` is the number of search comparisons happening in the worst case.

But the recurrence relation that you are using i.e. `T(n) = T(n/2) + 1` is the Worst-case Time complexity recurrence relation of the Binary Search and not the number of searches that are being done in binary search in the worst case.

Both notions are different things the first one talks about the comparisons in worst case and the second one talks about the running time in worst case.
> 0 votes

---
Tags: algorithms, search-algorithms, recurrence-relation, binary-search
---


# Question
Title: What does “linear” in Linear Temporal Logic refer to?
Consider the term *linear temporal logic* (in the meaning of *linear-time temporal logic*). In *linear temporal logic*, what does *linear* refer to:

1. to *temporal* or
2. to *logic*?

If I interpret http://en.wikipedia.org/wiki/Linear\_logic and http://en.wikipedia.org/wiki/Linear\_temporal\_logic correctly, the linear temporal logic is ***not*** an instance of the linear logic and ***not*** related to it in any way (except that both are, well, logics), is it? So, *linear* must refer to *temporal*. Shouldn't we write then

*linear-temporal logic*

(i.e., with a hyphen) then to avoid misinterpretation?

# Answer
> 2 votes
Linear (used the same way as in linear extensions) refers to the fact that the semantic model is an infinite "path" ("linear", if you will) without cycles; every state has a well-defined *next* element.

There is a total ordering over the Kripke-structure (possible worlds).

I.e. it refers to *temporal*.

---
Tags: terminology, linear-temporal-logic
---


title: Another version of Geography Game

text:
# Question
Title: Another version of Geography Game
The classic definition of normal “Geography Game” is the following:

Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (Called “Generalized Geography” in Sipser Chapter 8 and called “The Game of Geography” in papadimitiou Chapter 19. This version is a classic problem in Space Complexity which you probably already know it).

There is another version of the game, in this version player $I$ and player $II$ are restricted to the words that choosed by themeselves. e.g. If player $I$’s last word is *Alaska* and player $II$’s last word is *Kansas* then player $I$ next word must start with *A* not *S*. The game has a structure like *Tron* , to be more percise players attempt to block each other ways in the graph. We want to decide if player $I$ has a winning strategy.

This game is also PSPACE-complete. But i don’t know it’s name so i could not find any information about that.

I am looking for the paper which introduced this problem and prove this problem is also PSPACE-complete with reduction from classic version of Geography Game.

# Answer
> 1 votes
At first let me describe "The Game of Geography"; i borrow the definition from this article: On the complexity of some two-person perfect-information games

> Input is a pair $\langle G, s \rangle$, where $G$ is a directed graph and $s$ is a node of $G$. A marker is initially placed on node $s$. A move consists of moving the marker along a directed arc to an adjacent node. Each directed arc can be used once only. The first player unable to move loses.

In Sipser *ToC 3rd edt. (2012)*, Chapter 8 (Space complexity), Theorem 8.14 *(p. 345)*, this Problem called $GG$:

> $GG=\\{\langle G,s \rangle |$Player $I$ has a winning strategy for the generalized geography played on graph $G$ starting at node $s\\}$

Now consider this problem which introduced by *Simonson (February 5, 1986 SIGART/Issue 96 )*:

> The game is played on an $N\times N$ board. Two players alternately put markers down and the first player who puts his marker on and edge of boards loses. The main rule is that each player must place his marker only on squares which are adjacent to the last marker he placed down.

This explain the similarity between altered version of $GG$ and *Tron* game. now we can describe the altered $GG$. This variation as *Hendrik Jan* has mentioned in comments, called $PG$ or *Partizan Geography*. I borrow the definition from this paper: Theor. Comput. Sci. 110 (Mathematical Games):

> There are **two** specified vertices $s\_1$ and $s\_2$. The players alternately chooses arcs. The first arc chosen by the two players, must have its tail, respectively, at $s\_1$ and $s\_2$; and each subsequently chosen arc must have its tail at the vertex that was the head of the arc previously chosen by that player.

Now we can define altered $GG$ in order to describe this variant:

> $PG=\\{\langle G,s\_1,s\_2 \rangle |$Player $I$ has a winning strategy for the partizan geography played on graph $G$ starting at nodes $s\_1$ and $s\_2\\}$

As i mention, This variant is also PSPACE-complete, in fact $PG$ is proved to be PSPACE-complete under the name $TRON$ (Theor. Comput. Sci. 110 (1993) 215-245 (Mathematical Games))

What *Hendrik Jan* in comments mentioned, is more interesting. Because before now i did not know there are different restrictions that we can apply to the game which when they applied, the game still stay PSPACE-complete. This article: On the Computational Complexities of Various Geography Variants examine four different rule variants.

---
Tags: complexity-theory, space-complexity, complexity-classes
---


# Question
Title: Constraining function inputs; what concept/terminology am I looking for?
A function takes some set of inputs and creates a set of outputs; however there will be some set of invalid inputs. For example say we have F(a,b) =\> a / b and we constrain 'a' & 'b' to be numbers, and 'b' must never be zero.

The process of defining those constraints; what CS concept/terminology am I looking for?\*

I'd like to improve my codebase's quality and I feel unexpected/unanticipated inputs are a big problem. I am looking for languages/frameworks\** that it easier for developers to define those constraints; so I feel if I know the concept/terminology, I might have better success in my search.\***

---

\*Mathematically, I think I'm talking about domain. But is there a more specific CS term?

\**Type constraints such as 'number' is standard for strongly typed languages, but having compile time constraint that say 'b' != 0 seems more esoteric. Runtime checks can be done, but I'd like to have something that defines the constraint on the interface/signature. Something of a 'strongly set range/set' of inputs.

\***While my goal is to find framework/language, product recommendations get marked as off topic on most stack exchange sites. So I'm looking for the underlying concept.

# Answer
> 0 votes
I believe the concept you are looking for, is simply a *Type*. For example, one possible type of the function `F` from your question would be: `F :: (Number, NonZeroNumber) -> Number`.

There are of course many other related concepts, such as *Contracts*. But they can mostly be interpreted as just different ways to write types. In fact, I believe there is actually a proof that (certain kinds of) contracts are always expressible as (potentially exponentially large) types.

As a *very* general rule, there are three different ways of turning a *partial* function into a *total* function:

* Modify the Range
* Modify the Domain
* Modify the Codomain

Let's look at division. Typically, we would define division like this:

```
(/) :: (Number, Number) -> Number
a / b = … naive implementation of division

```

Of course, this function is *partial*. It will diverge for `b = 0`.

We can fix that by modifying the Range:

```
a / 0 = 0
a / b = … naive implementation of division

```

Now, our function is *total*: it does not diverge if `b = 0`. It returns a result. It is a *wrong* result, of course, but it is *not* an error!

The second option, as already mentioned above, is to modify the Domain:

```
(/) :: (Number, NonZeroNumber) -> Number
a / b = … naive implementation of division

```

Problem solved. Now, it is impossible to pass in `b = 0`, and there can never be an error.

A third option is to modify the Codomain:

```
(/) :: (Number, Number) -> Option Number
a / 0 = None
a / b = Some (… naive implementation of division)

```

None of these require any fancy stuff. However, even if we were to introduce something like Contracts into our language:

```
(/) :: (Number, Number) -> Number
    where
        b ≠ 0
    in
        a / b = … naive implementation of division

```

This can be viewed as equivalent to defining an unnamed type `__someUnnamedType__ = Number \ { 0 }` and rewriting the function definition to

```
(/) :: (Number, __someUnnamedType__) -> Number
a / b = … naive implementation of division

```

As I mentioned above, I vaguely remember reading about a proof that contracts and types have equivalent expressive power, but some contracts may generate exponentially large types. So, whether to choose contracts or types partially depends on usability and convenience.

The most well-known Contract system is probably Eiffel's, but I have a soft spot in my heart for Microsoft Research's Spec#.

---
Tags: terminology
---