# Question
Title: Best data structure for queries about subsets?
I am interested in finding a data structure that supports the following operations:

* Insert Set: Insert a set into the data structure.
* Decide Subset: Determine whether a given set is a subset of any of the inserted sets.

The most obvious way to implement this would be as a hash set of hash sets, but I think some performance gains could be had by exploiting common subsets among the stored sets. For example, if {1} and {1,2} were both stored, only {1,2} would need to be kept. Any ideas?

# Answer
There is a popular algorithm in bioinformatics for solving this exact problem. I believe it is known as the multi-set membership testing problem (MSMT).

# BigSI

The idea in BigSI is that you represent each of the $N$ inserted sets as a bloom filter of length $m$ with $k$ hashes. Let $Q$ be our $m\times N$ table, where the columns represent each of the $N$ bloom filters for each of our $N$ sets $\\{X\_1, ... , X\_N\\}$.

Now we wish to query $Q$ for an input set $S$. Let $A=\\{h\_i(s) \\;\\;\forall i\in\[k\],s\in S\\}$ be all of the hash values for the input set. We have the following condition $$S\subseteq X\_i \iff Q\[r\]\[i\] = 1 \\;\\;\forall r\in A$$ It remains to find columns such that the right hand side holds true. To do this, we create a subset of the rows $Q'=\\{row\_i(Q) \\; | i \in A\\}$ . Now our condition is that $$S\subseteq X\_i \iff Q'\[r\]\[i\] = 1 \\;\\;\forall r\in \[|A|\]$$ i.e. any columns with all $1$s in $Q'$ is a superset of $S$. We can find such columns $C$ by performing $$ R = \bigwedge\_{r\in\[|A|\]}Q'\[r\]$$ $$ C = \\{i \\;\\;| \\;\\; R\[i\] = 1\\}$$ If $C\neq \emptyset$, then $S$ must have been a subset of one of the original $N$ sets. Of course this algorithm is also able to tell you *which* of the original sets $S$ is a subset of. Since your question doesn't need that information, there may be some minor optimizations.

Here is a figure from the BigSI publication, where the input sets are FASTQ files which are broken down into $k$-mers. Part (a) represents the 5 input sets, each of cardinality 2. Figure (b) shows the resulting $Q$ table and the $\texttt{AND}$ operation used to find the superset inputs. Figure (c) is a naive alternative, where each row represents a possible element from one of the input sets, however this table would have to grow vertically as well as horizontally for each input set, as we may see new elements.
> 4 votes

---
Tags: data-structures
---


title: Shortest cycle for each vertex

text:
# Question
Title: Shortest cycle for each vertex
I have an unweighted undirected graph.How is it possible in this graph for each vertex to find the length of the shortest cycle containing it?

P.s This graph have not non-tree edge, but it have a cycle. What can be considered subtrees of the vertical 10? How will the algorithm work when the BFS reaches 16 and 17?

# Answer
> 2 votes
An easy way is as follows: For each vertex $s$, perform a BFS visit to discover the shortest cycle containing $s$.

When a visit from $s$ is performed a BFS tree $T\_s$ is built and each non-tree edge $(u,v) \not\in E(T)$ for which $u$ and $v$ belong to different subtrees rooted in the children of $s$ in $T$ tree induces a cycle containing $s$. Since, the shortest cycle containing $s$ must use a non-tree edge $(u,v)$ with this property, it will be found by the visit. You can optionally stop the visit early: if you find a cycle while visiting $u$, you can stop the BFS as soon as all the vertices in the level of $T$ containing of $u$ are visited.

The overall required time is $O(n \cdot m)$.

---
Tags: algorithms, graphs
---


# Question
Title: Reduction from a m-coloring to a m-partition
define a m-partition as: Given an undirected graph G = (V, E) and an integer j. Does there exist a partition of the vertices into m parts {V1, V2, ... , Vm} such that at least j of the edges have their endpoints in different parts of the partition?

I started by partitioning the graph into k parts: each partition represents 1 colouring of the graph. From there, I thought of reverting all edges: so converting all edges into non-edges and vice-versa. I'm stuck here. Am i on the right track? Thank you.

# Answer
By definition, a $m$-coloring is a function $f : V \to \\{1,\dots, m\\}$ such that $\forall u,v \in V \\; f(u) = f(v) \implies (u,v) \not\in E$. This means that at least $|E|$ edges have their endpoints in different sets of the partition $\\{V\_1, \dots, V\_m\\}$ of $V$ with $V\_i = \\{ v \in V : f(v)=i \\}$.

On the contrary, if there is a partition $\\{V\_1, \dots, V\_m\\}$ of $V$ such that at least $|E|$ edges have their endpoints in different sets, then the function $f : V \to \\{1, \dots, k\\}$, where $f(u)$ is the unique index $i\_u \in \\{1, \dots, m\\}$ such that $u \in A\_{i\_u}$, satisfies $\forall u,v \in V \\; f(u) = f(v) \implies (u,v) \not\in E$.

The above shows that the instance $G=(V,E)$ of $m$-coloring can be reduced (w.r.t. Karp reductions) to the instance $\langle G, |E| \rangle$ of $m$-partition.
> 2 votes

---
Tags: np-complete, colorings
---


# Question
Title: "Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency?
For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So imagine an array of size 10 with elements (9, 2, 4, 1, 6, 8, 5, 3, 7, 0) in that order. We want the algorithm to sort them into (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). There are many ways to implement this, but the simplest I found is to use a 2nd array (call it B). After the first pass thru A, B\[0\] will become 0 and B\[9\] will become 9. Those are the smallest and largest elements in A. I also have an array of flags telling me which numbers from A I already "plucked" so I will skip over those on any subsequent passes. For simplicity, I rescan the entire array of 10 elements even on the 2nd, 3rd, 4th... passes to find the lowest and highest remaining pairs from A. This is obviously a slow algorithm since it is O($n^2$).

So I got this working quickly because it is so simple, however, it is very slow as N (the # of elements in the array to be sorted) becomes large. For example, if N=1000 vs. N=500, the N=1000 takes 4 times as long. N=2000 takes 4 times as long as N=1000....

So what I am wondering is why not have the program first break up the array into smaller arrays, sorts those, and then just merge the results into 1 big array. The question is, what is the optimal final (smallest) size array "chunks" we should work on? Breaking it up has overhead, but an n squared algorithm can go so much faster operating on small chunks, then merging the results which takes O(N) time.

For example, suppose someone wants to sort 1 million random integers and they pass me an array of those. I cannot just use my simple algorithm on that, it would take forever and a day. But is there an optimal way to break it up into pieces, or does that depend on too many things such as the compiler/interpreter, cache memory size...? Should I just try many different subarray sizes such as 1024, 512, 256... and just pick the best for my computer, timing each one? I would suspect that if breaking the subarrays too small, the overhead of doing that and merging all the tiny little pieces (such as arrays of size 2) might not be optimal, especially on a slow computer and/or in an interpreted environment (like I am using).

Also I am interested in the time complexity as the big initial array gets chopped into pieces. For example, with N=1000, I would make 1000 passes on 1000 numbers so 1 million "examinations" (array references) which is O($n^2$), however if I "chop" only once, now I would have 2 * (500$^2$) = 1/2 million + 1 merge, 4 sub-blocks would be 4 * (250$^2$) = 1/4 million but with 3 merges.... What I am thinking is eventually there will be a point of diminishing returns, meaning that chopping any smaller is of no advantage (and may actually slow things down). Question is, is trial and error the only way to find this point?

# Answer
My plan of attack is to simply try many different final block sizes such as 1024, 512, 256.... and just time them all. I chose a power of 2 block sizes cuz they can be halved in size easily without any fractions. For testing purposes, I would force the array sizes to be a perfect power of 2 so they divide perfectly. My goal is not a generic sorting algorithm but rather more of a divide and conquer optimization speed question.

So in array B, there would be sorted subarrays which I can then merge back into A, so the storage for this algorithm is roughly 2N.

Also regarding the merge part of this (or any sort using merge), why not just start with sorted arrays of size 1 and work your way up? For example, if we had an array of size 1024, start by merging adjacent pairs of numbers, then merge those pairs into quads...
> 1 votes

# Answer
If you break your array into groups of $k$ elements, sort them with your algorithm, and them merge them a-la mergesort, then your algorithm will take time: $O(\frac{n}{k} \cdot k^2 + n \log \frac{n}{k}) = O(n k + n\log \frac{n}{k})$.

This is minimized when $k$ is minimized. Therefore the best choice is $k=\Theta(1)$, resulting in a running time of $O(n \log n)$. This is essentially mergesort. Notice that **any** choice of $k = \omega(1)$ will lead to a slower algorithm, also in practice, once $n$ is big enough.

I also suspect that, even finding the best value of $k$ for your machine, this approach won't be much faster than a careful **iterative** implementation of merge-sort with one global auxiliary array $B$. Alternate between 1) using $A$ to store the sorted sub-arrays and merging into $B$, and 2) merging the sorted sub-arrays already in $B$ back into $A$. Process subarrays in the order you would visit the nodes of a binary tree in a a postorder DFS.
> 1 votes

---
Tags: optimization, sorting, divide-and-conquer
---


# Question
Title: How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?
Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.

I am having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)

For example:

Sequence: `[A, C, C, C, A, B, Y, B]` is made up from 2 subsequences, namely `[A, C, C, C, A], [B, Y, B]`

So, therefore, my output for this example would be `2`.

Thanks in advance!

# Answer
> 1 votes
Let $S$ be your input sequence and denote by $S\[i:j\]$ the subsequence going from the $i$-th to the $j$-th element of $S$ (inclusive).

Let $OPT\[i\]$ be the minimum amount of continuous palindromic subsequences in which $S\[1:i\]$ can be partitioned. Let $OPT\[0\]=0$. For $j=1,\dots,|S|$, you have:

$$ OPT\[j\] = \min\_{\substack{i=1,\dots,j\\S\[i:j\] \text{ is a palindrome}}} \\{1+ OPT\[i-1\] \\}. $$

The value you are looking for is $OPT\[|S|\]$. This algorithm requires time $O(|S|^2)$. Notice that all the pairs $(i,j)$ for which $S\[i:j\]$ is palindrome can be precomputed in $O(|S|^2)$ time.

---
Tags: algorithms, dynamic-programming, recurrence-relation, recursion
---


# Question
Title: Is topological sort of an original graph same as post-ordering dfs of its transpose graph
I have an intuition that topo-sort of an original graph

```
 A -> B -> C
 D -> B

```

topo-sort is \[D, A, B, C\] or \[A, D, B, C\]

If I transpose the graph

```
  C -> B -> A
       B -> D

```

the postordering dfs of this transposed graph also gives \[D, A, B, C\] or \[A, D, B, C\]

Please, I can't mathematically prove/disprove it. If not true, an counter example would helpful.

> A postordering is a list of the vertices in the order that they were last visited by the algorithm

https://en.wikipedia.org/wiki/Depth-first\_search

# Answer
> 0 votes
Let $G$ be a graph and $G'$ be it's transposed version. Your property follows from the following two facts:

1) The order in which vertices are visited by a postorder visit on $G'$ is the reverse of a topological order $\sigma'$ for $G'$ (in fact, that's a standard way to compute a topological order). You can see that this is true by noticing that if $(u,v) \in G'$ then $v$ must be visited before $u$ can be visited, i.e., $v$ follows $u$ in $\sigma'$.

2) If $\sigma'$ is a topological order for $G'$, then the linear order $\sigma$ obtained by reversing $\sigma'$ is a topological order for $G$. You can see that this is true because, for every edge $(u,v)$ of $G$, $G'$ contains $(v,u)$ and therefore $v$ precedes $u$ in $\sigma'$. This means that $(u,v) \in G \implies u$ precedes $v$ in $\sigma$.

---
Tags: graphs, topological-ordering
---


# Question
Title: How many times in this pseudo-code is the function F called?
For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)?

**How many times in this pseudo-code is the function F called?**

```
Main
    Declare K as Integer
    K = 3
    Set Result = F(K)
    Write Result
End Program

Function F(N) as Integer
        If N == 1 Then
Set F = 1
    Else
        Set F = N * F(N - 1)
        Set N = N - 1
    End If
End Function

```

# Answer
To understand what is happening you have to execute the code "on paper". One way of showing this is to number the lines of code so we can see what is happening:

```
01 Main
02    Declare K as Integer
03    K = 3
04    Set Result = F(K)
06    Write Result
07 End Program
08
09 Function F(N) as Integer
10    If N == 1 Then
11        Set F = 1
12    Else
13        Set F = N * F(N - 1)
14        Set N = N - 1
15    End If
16 End Function

```

Now if we work through the code one line at a time and record the values in the variables we can see what is happening:

```
Line Code                       K    N   Result
01   Main
02   Declare K as Integer       ?
03   K - 3                      3
04   Set Result = F(3)          3          ?
09   Function F(3) as Integer        3
10   If 3 == 1 Then                  3
13   Set F = 3 * F(2)                3
09   Function F(2) as Integer        2
10   If 2 == 1 Then                  2
13   Set F = 2 * F(1)                2
09   Function F(1) as Integer        1
10   If 1 == 1 Then                  1
13   Set F = 1                       1
15   End If                          1
16   End Function                    1
14   Set N = 2 - 1                   1
15   End If                          2
16   End Function                    2
14   Set N = 3 - 1                   2
15   End If                          2
16   End Function                    2
06   Write Result                3        6
07   End Program                 3        6

```

What we are seeing is recursion in action, with different scopes of the variable `N`.

You can see in the execution trace three calls of `F` with the values of 1,2,3. The first comes from Line 4 and the last two from line 9. So `F(K)` and `F(N-1)` are the only calls.
> 1 votes

# Answer
The function is called 3 times. F(3) F(2) F(1)
> 0 votes

# Answer
The pseudocode calls the F 3 times
> 0 votes

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


# Question
Title: Eliminating left recursion and left factoring this grammar
I have a grammar
S-\> SS\* | SS+ | a
Really confused on how to remove the left recursion and do left factoring

My attempt on removing left recursion : S -\> aS' S' -\> S+S' | S\*S' | epsilon
If this is correct, I'm stuck in left factoring. Help!

# Answer
> 1 votes
check this image the problem is explained

# Answer
> 0 votes
This is correct. There is an epsilon production.

---
Tags: context-free, compilers, left-recursion
---


title: What are Contexts in Lambda Calculus?

text:
# Question
Title: What are Contexts in Lambda Calculus?
What is a Context? Is it like a scope in C? Does it have a start and an end? Can contexts contain other contexts?

I see Contexts being used in lambda calculi type system rules, but I don't understand concretely what they *are* and why they are necessary. If they are too abstract, then is there some visual or metaphorical description?

**Update:** I am referring to "contexts" as what is to the left of ⊢ in typing calculi.

# Answer
> 1 votes
Typing contexts are the way to remember previously declared variables when type-checking a program/term. The rule for term abstraction usually is something like $$\dfrac{\Gamma,x:A\vdash e : B}{\Gamma\vdash \lambda x.e : A\to B}$$ In the conclusion, $x$ is not in $\Gamma$ yet. At this point, $x$ is declared to be the variable of the function $\lambda x.e$ and this variable appears in $e$. So, $x$ is a free variable in $e$. The typing rule above expresses that $\lambda x.e$ is of type $A\to B$ under context $\Gamma$ iff $e$ is of type $B$ under context $\Gamma,x:A$. So in the premise of the rule, we are type-checking the body of $\lambda x.e$ (which is $e$), but we need to remember that $x$ (which appears free in $e$) is a variable of type $A$.

---
Tags: lambda-calculus, type-theory
---


title: How to convert NPDA to PDA?

text:
# Question
Title: How to convert NPDA to PDA?
I have been given this Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be transitions where the pda doesnt read anything from the stack but i dont know how to solve this.

Thanks in advance!

# Answer
> 0 votes
Suppose your stack alphabet is $\Gamma =\left\\{Z\_0,X\right\\}$. You can eliminate transitions which don't pop stack, by guessing which stack symbol is at the top. like this:

before: $(a,\epsilon)/XXX$

after: $(a, X)/XXXX$, and $(a, Z\_0)/XXXZ\_0$

---
Tags: pushdown-automata
---


# Question
Title: For which values of $m$ is $m$-partition hard?
Consider the following reduction: $m$-colouring to $m$-partition.

Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices into $m$ parts $\\{V\_1, V\_2, \ldots , V\_m\\}$ such that at least $j$ of the edges have their endpoints in different parts of the partition?

I was able to come up with the reduction, but now I'm stuck at this question:

What I need to find is the values of $m$ where the reduction implies that $m$-Partition is NP-complete?

# Answer
The $1$-partition problem is trivial, since there is only one possible partition.

The $2$-partition problem is the same as MAX-CUT, which is known to be NP-complete.

For $m \> 2$, the $m$-partition problem is NP-complete by reduction from $m$-coloring, which is NP-complete for that range of $m$.
> 1 votes

---
Tags: np-complete, partitions, colorings
---


# Question
Title: Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language
$A = \\{0^i1^j \text{ where }j\>(i \text{ mod }3), i \geqslant 0, j \geqslant 0\\} $

I know that A is a regular language, since we can construct the DFA or the NFA, but i dont know how to construct it, Can somebody help me please? Thank you

# Answer
> 3 votes
$A$ is regular since it's the union of the following $3$ regular languages:

* $\\{0^i 1^j : i \bmod{3} = 0, j \> 0 \\}$ for which a regular expression is $(000)^\*11^\*$.
* $\\{0^i 1^j : i \bmod{3} = 1, j \> 1 \\}$ for which a regular expression is $(000)^\*0111^\*$.
* $\\{0^i 1^j : i \bmod{3} = 2, j \> 2 \\}$ for which a regular expression is $(000)^\*001111^\*$.

A reguar expression for $A$ is then $E = (000)^\*(1 + 011 + 00111)1^\*$. You can now easily construct a NFA from $E$.

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


# Question
Title: Reduce Vertex Cover with size k to Vertex Cover with size n/2
Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \\{G \mid G\text{ has a vertex cover of size } |V(G)|/2\\}\\,.$$

I have divided the problem into three parts:

* $k = n/2$: This case is trivial.
* $k \> n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
* $k \< n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.

# Answer
> 2 votes
For $k\<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k\>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.

# Answer
> 0 votes
For k \< n/2, add enough vertices with a single edge out of them (pointing back at themselves) such that the size of the new vertex cover is half the size of the new graph.

For k \> n/2, add enough vertices connected to an arbitrary vertex already in the vertex cover such that the size of the original vertex cover is half the size of the new graph.

# Answer
> -2 votes
This question was answered in the following video (By me): https://www.youtube.com/watch?v=rKNasOecTu0

In a nut-shell, the key here is to modify the graph in such a way it wouldn't be profitable to select vertices from the modified graph, and by finding a full vertex cover in the original graph, you could get a half vertex cover in the modified graph.

Hope that helps :-)

---
Tags: graphs, np-complete, reductions, vertex-cover
---


# Question
Title: PDA that accepts if there is an "a" in the second half of the string
How could I build a PDA on $Σ = \\{a,b\\}$ that accepts if there is an "a" in the second half of the string?

Formally the language is the following: $L = \\{xy \mid x ∈ Σ^\*, y ∈ Σ^\*aΣ^\* \land |x| ≥ |y|\\}$.

# Answer
> 1 votes
The PDA has three phases. In the first phase, it adds $A$ to the stack per character. It switches to the second phase nondeterministically. In the second phase, it removes $A$ per character. It switches to the third phase nondeterministically, during which it empties the stack. The PDA accepts if it encountered an $a$ during the second phase.

---
Tags: automata
---


title: Rolling hash hacking

text:
# Question
Title: Rolling hash hacking
The hash value of a string $s$ is given by

$$ h(s) = \sum^{|s|}\_{i = 1} s\_i \cdot p^{|s| - i} \mod m; \text{ $m$ is prime, $m \< 10^{12}$}. $$

The string $s$, $p$, $m$ is given, $|s| \le 14$, alphabet size $= 62$ (letters and digits).

I need to find a string $s^{\prime}$:

$s^{\prime} \neq s$, but $h(s^{\prime}) = h(s)$

$s^{\prime}$ must meet the same requirements as $s$. The answer is always exist.

I know about Birthday-attack, but $m$ is too large and if I generate random strings, probability of collision is too small. Simple brute-force is also not suitable, because the string may be too long (14 characters).

# Answer
Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6

Also note that your question have nothing with *rolling* hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.
> 1 votes

# Answer
Hint: Write out the condition for $h(s)=h(s')$, expressed in terms of the variables $s\_1,\dots,s\_{14},s'\_1,\dots,s'\_{14}$. Use linear algebra.
> 0 votes

---
Tags: hash, rolling-hash
---


# Question
Title: Turing machine on input w tries to move its head past the left end of the tape
Consider the language

> $$ L = \\{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\\}. $$

Prove whether L is decidable or not.

I tried to prove it as undecidable through reduction method but could'nt reduce the language halt to L inorder to prove that it is undecidable.

# Answer
> 0 votes
```
Construct Turing Machine M':
        On input x: Ignore the input x
        Simulate the run of machine M on w a separate tape
        If M accepts or reject:
             Move the head of M' left
        Else:
             Do Nothing

```

The machine M' described above will "try" to move the head on left only if M halts on w.

If L is decidable, then we can check for membership of $(M',\epsilon)$; but that will decide that $M$ halts on $w$ (The Halting Problem).

Hence, the language L is undecidable.

---
Tags: formal-languages, turing-machines, undecidability
---


# Question
Title: Use or Importance of $\Rightarrow^*$ operator
Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^\*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar.

As stated here, when $\Rightarrow^\*$ is used, it means *derive in 0 or more steps* and when $\Rightarrow^+$ is used, it means *derive in 1 or more steps*.

What I don't understand is **what is the use or importance of $\Rightarrow^\*$ operator?**. It just replaces the head of the production with the head itself.
*Is it that the $\Rightarrow^\*$ operator is just there to define operators in some standard way or it actually differs in the way it is used as compared to $\Rightarrow^+$?*

Also, while deriving strings, to skip some obivious steps(like replacing multiple non-terminals in a string with their respective terminals), **should I use $\Rightarrow^\*$ or $\Rightarrow^+$?**

# Answer
> 2 votes
It is false that $\Rightarrow^\*$ " just replaces the head of the production with the head itself". $A \Rightarrow^\* B$ means that the sentential form $B$ can be obtained from the sentimental form $A$ by applying **any** number of productions (which might be $0$ or more than $0$).

For example if your grammar is $S \to a$, then all of the following are true $S \Rightarrow^\* S$, $S \Rightarrow^\* a$, and $S \Rightarrow^+ a$, while it is false that $S \Rightarrow^+ S$.

If you are deriving strings and applying *at least one* production per step then both $\Rightarrow^\*$ and $\Rightarrow^+$ are correct. The latter is more specific since it implies the former (but not vice-versa).

---
Tags: context-free, derivation
---


# Question
Title: Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights
I want to find labeled samples in $\\{0,1\\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are linearly separable, but require every linear separator to have at least one exponentially large weight. To show that the samples are linearly separable, it is enough to show that they are consistent with a decision list, which should be apparent from the list of samples. So, my question is

> Does there exist a set of labeled samples $S$ in $\\{0,1\\}^n$ that are consistent with a decision list and such that any linear threshold function that correctly labels $S$ has at least one exponentially large weight $w\_i = 2^{\Omega(n)}$?

Here are the definitions that I'm working with: A linear threshold function $f \colon \\{0,1\\}^n \to \\{0,1\\}$ with associated weights $w\_0, \dots, w\_n \in \mathbb{R}$ gives $f(x) = 1$ if and only if $w\_1x\_1 + w\_2x\_2 + \dots + w\_nx\_n \geq w\_0$. Given a set $S$ of points in $\\{0,1\\}^n$ labeled $0$ or $1$, we say that a linear threshold function $f$ correctly labels $S$ if $f(x) = 1$ whenever $x$ is labeled $1$ and $f(x) = 0$ whenever $x$ is labeled $0$ for all $x \in S$.

**Note:** I had asked the same question on math.stackexchange since it seemed relevant to both fields. Here is the link for that.

# Answer
> 3 votes
Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights.

A simple example which requires exponential weights is the function $\sum\_i 2^i (x\_i - y\_i) \geq 0$ or variants.

---
Tags: algorithms, time-complexity, machine-learning, linear-programming, learning-theory
---


title: algorithm with $f(n) = log^2(n)$

text:
# Question
Title: algorithm with $f(n) = log^2(n)$
I have to write an algorithm that exactly reflects this recurrence: $$ T(n)=\begin{cases} Θ(1)\\;\\;\\;\\;n \leq 1\\ 2T(n/2)+log^2(n)\\;\\;\\;\\;n \>1 \end{cases} $$ I have tried this way:

```
//the array starts from 1
    mergesort(A[], b, e)
    {
       if(b < e)
       {
          p = (b+e)/2;
          mergesort(A, b, p);
          mergesort(A, p+1, e);
          for(i = 1; i <= e; i = i*2)
             for(j = 1; j <= e; j = j*2)
                puts("");
       }
    }

```

does the algorithm respect the recurrence?

EDIT:

could a solution be?

```
//I have only changed the two fors
            mergesort(A[], b, e)
            {
               if(b < e)
               {
                  p = (b+e)/2;
                  mergesort(A, b, p);
                  mergesort(A, p+1, e);
                  for(i = 1; i <= e-b; i = i*2)
                     for(j = 1; j <= e-b; j = j*2)
                        puts("");
               }
            }

```

# Answer
Your first algorithm as written cannot be correct since it has a time complexity of at least $\Omega(n \log^2 n)$ and the solution to your recurrence equation is $T(n)=\Theta(n)$. To see this notice that at least half of the $\Theta(n)$ leaves of the recursion tree requires time $\Theta(\log^2 n)$ to execute the two nested for loops at the end.

Your second algorithm is correct but it is overcomplicated and has a misleading name.

Assuming that $n$ denotes the **value** of the input (and not its size), that arithmetic operations require constant time, and that `/` denotes integer division, a simple algorithm is:

```
Input: a positive integer n.

f(n):
   if(n==0)
      return;

   f(n/2);
   f(n/2);

   for(i=1; i<x; i=i*2)
      for(j=1; j<x; j=j*2)
         no-op;

```
> 0 votes

---
Tags: algorithms, time-complexity, algorithm-analysis
---


title: Struggling with NP-Complete Problem

text:
# Question
Title: Struggling with NP-Complete Problem
I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows:

*The Set Cover problem is the following:*

*Instance:* A set $U = \\{1,2,...,n\\}$ of $n$ elements, a collection of subsets $S\_1,S\_2,...,S\_m$ of U, and an integer $K$.

*Question:* Are there $K$ sets among the $S\_i$’s whose union is equal to $U$? In other words, are there $K$ sets which together cover all the elements of $U$?

*Prove that Set Cover is NP-complete*

Any guidance here would be greatly appreciated. My thought is that I should try reducing from the Vertex Cover problem, but I am not entirely sure how to reduce from there.

# Answer
> 0 votes
An instance of (the decision version of) vertex cover is a pair $\langle G, k \rangle$ where $G = (V,E)$ is a graph and $k$ is an integer. The problem is that of deciding whether $\exists S \subseteq V$ such that $|S| \le k$ and $\forall (u,v) \in E, \\; \\{u,v\\} \cap S \neq \emptyset$.

Let $v\_1, \dots, v\_n$, be the vertices of $V$, in an arbitrary order.

You can see that vertex cover is a special case of set-cover. Indeed, it suffices to define $U=E$, $S\_i = \\{u \in V : (v\_i, u) \in E \\}$ for $i=1,\dots,n$, and $K = k$.

If there is a set-cover $C$ of size at most $K$, then for each element $e = (v\_i, v\_j) \in U = E$ at least one of $V\_i$ and $V\_j$ is in $C$ (since these are the only two sets that contain $e$). This means that $S = \\{v\_h : V\_h \in C \\}$ is a vertex-cover for $G$ of size $|S| = |C| \le K = k$.

If there is a vertex cover $S$ of size at most $k$ for $G$, then for each edge $e = (v\_i, v\_j) \in E = U$, $\exists v\_k \in \\{v\_i, v\_j\\} \cap S$. This means that $V\_k \ni e$ is in the set $C = \\{ V\_h : v\_h \in S \\}$ and hence $C$ is a set-cover of size $|C|=|S| \le k=K$.

---
Tags: algorithms, np-complete, vertex-cover
---


# Question
Title: Runtime of Divide and Conquer Flavored Bogo Sort
Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively.

https://en.wikipedia.org/wiki/Bogosort.
**Input:** An unsorted array A\[1...n\].
**Output:** A sorted array.

Let's remind ourselves of why normal Bogo Sort's runtime is O(n!).

Let's say we were to randomly guess the smallest element of an array. What are our odds of guessing right? Our odds would be 1/n of course. Let's say we guessed right! Now let's try to randomly guess the second smallest element of an array, after guessing the first right. What are our odds of guessing right? Our odds would be 1/(n-1) of course.

$$\frac{1}{n}\*\frac{1}{n-1}\*\frac{1}{n-2}\\; * \\;... \\;\*\\; \frac{1}{n-n+1}$$ **Expectation is n!**

Let's use a Divide and Conquer strategy on Bogo Sort to improve the runtime. We will use a modified Merge Sort to achieve this. We recall that merge sort merges two sorted arrays recursively. Can Bogo Sort take advantage of the fact that we are merging two already sorted arrays? Let's say we were to randomly guess the smallest element of two sorted arrays. We know that the smallest element of both can only ever be the first element of one of these two arrays. If we randomly guess from just the first two smallest elements in each array, what are our odds of guessing right? Our odds would be 1/2. This sounds better than 1/n, but let's look at an example recurrence tree.

**Example Recurrence Tree:**
n = 4 brackets \[ \] represent a merge being performed.

$$\[\frac{1}{2}\*\frac{1}{2}\*\frac{1}{2}\*\frac{1}{2}\]$$ $$\[\frac{1}{2}\*\frac{1}{2}\]\\;+\\;\[\frac{1}{2}\*\frac{1}{2}\]$$ $$\[\frac{1}{2}\]+\[\frac{1}{2}\]+\[\frac{1}{2}\]+\[\frac{1}{2}\]$$

**\[Depth 0\]** Expectation is 16
**\[Depth 1\]** Expectation is 4 + 4 = 8
**\[Depth 2\]** Expectation is 1 + 1 + 1 + 1 = 4

Note, that in our base case we only need sort two values, guess between two values, a total of n times. From the above, we see the expected runtime of D&Q Bogo Sort:

Runtime: $$O(\sum\_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ Recurrence: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ i++ each recurrence

> I need help confirming the runtime. My assumption originally was that the runtime is simply O(2^n). However, I believe I need a log( ) in there somewhere. I am unsure how to apply the Master Theorem to O(2^n) in my hypothesized recurrence:

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

We have successfully reduced Bogo Sort from factorial runtime to exponential runtime using divide and conquer. Let me know how I can improve my analysis.

# Answer
> 0 votes
The solution to the recurrence $T(n) = 2T(n/2) + O(2^n)$ is $T(n) = O(2^n)$.

---
Tags: sorting, recurrence-relation, divide-and-conquer, mergesort
---


title: Path NFA-eplison to DFA conversion

text:
# Question
Title: Path NFA-eplison to DFA conversion
Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA? The only simplifications I have come up with relate to the NFA-epsilon representation, the computation of the epsilon closure, and the DFA representation. Each NFA node can be represented as a set of symbols transitioned on, if it has an epsilon transition, and a unique reference to the following node. The DFA representation can use shared references as it is acyclic.

# Answer
> 1 votes
Unless I misunderstood your question, in a NFA $N$ that is a path one vertex has in-degree $0$ and outdegree $1$, one vertex (possibly the same) has in-degree $1$ and out-degree $0$, and all the other vertices have in-degree $1$ and out-degree $1$.

Let $N'$ be the NFA obtained by identifying all the vertices in the same component of the (undirected version of the) subgraph induced by all the edges labelled $\varepsilon$ in $N$. All vertices of $N'$ have maximum out-degree $1$, moreover $N'$ contains no edge labelled $\epsilon$. This shows that $N'$ is a DFA. The process can be performed in linear time.

A note: when a set $S$ of vertices from $N$ is identified into a single vertex $v$ in $N'$, you will need to mark $v$ as a final state in $N'$ iff at least one the vertices in $S$ is a final state in $N$.

---
Tags: graphs, automata, finite-automata
---


# Question
Title: Write an algorithm for finding the minimum element
Given array A=\[31, 40, 41, 16, 41, 58,20\], min algorithm returns 16. Write an algorithm for finding the minimum element.

# Answer
Algorithm:

Traverse the array and compare with every element to update the minimum element.

Code:

```
int getMin(vector<int> &A){
    int minElement = INT_MAX;
    for(auto num: A){
        minElement = min(minElement, num);
    }
    return minElement;
}

```

Algorithm Analysis:

Time Complexity:

If given input has `n` elements, then we have to go through every element to identify the minimum of them all. It is easy to prove by contradiction that we have to compare with each and every element. So the time complexity is `Omega(n)` or `O(n)` or `Theta(n)`.

Space Complexity:

We don't use extra space in above algorithm. So `O(1)`.
> 2 votes

# Answer
```
int min=A[0]
for(int i=1;i<sizeof(A);i++)
{
   if(min>A[i])
   {
       min=A[i];
   }
}
//the minimum element is 'min'

```
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Minimisatiom using Myhill-Nerode Theorem
I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because they are indistinguishable?

In the first FSM below, if I group states (q3,q4) on 0, q3 reaches q4 and q4 reaches q4, but on 1 both behave differently as q4 has no transition on 1.

Same trouble with the second FSM.

I want to understand how to group together the states while using the theorem.

# Answer
In the first automaton, you can see that every accepting state has a transition with 0 to an accepting state, while a transition with 1 goes to either a sink or is just non-existing. But this means that reading a 1 from an accepting state leads always to rejecting the input. Thus, all accepting states are equivalent.

In the second automaton, you can see that $q\_2$ has a 0-transition to $q\_5$, a non-accepting state, while the other two accepting states have 0-transitions to accepting states. Thus, $q\_2$ cannot be equivalent to both $q\_4$, and $q\_3$. Moreover, $q\_3$ and $q\_4$ cannot be equivalent because reading 00 from both states leads to different behavior (one run is accepting, th other rejecting). Thus, in this case you cannot merge any of the accepting states.
> 1 votes

# Answer
In the first automata you can group $\<q0,q1\>$ and $\<q2,q3,q4\>$ (which is final) and in the second automata you cannot minimize any states.
> 0 votes

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


# Question
Title: CFG for language of words with odd many $a$ and exactly two $c$
I am trying to construct a context-free grammar for the language $$ L = \\{ w \in \\{a,b,c\\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \\}. $$

I am currently stuck with this and any help would be appreciated, thanks in advance!

# Answer
Your language is regular.

You can construct a DFA/NFA for your language, and then convert it to a right regular grammar.

If you're having difficulties with construct a DFA/NFA, try using the product construction.
> 0 votes

# Answer
Make a symbol E meaning “even number of A’s, any number of B’s”, a symbol O meaning “odd number of a’s and any number of b’s”, and use S-\>AcAcO | AcOcA | OcAcA | OcOcO.
> 0 votes

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


# Question
Title: Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list
**Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

**

Please tell me if my understanding is correct: each slot in T\[0,1,2….m-1\] is storing (1) a flag (2) an element (3) 2 pointers
So, instead of the slot T(h(k)) being a pointer to a list, it is able to save one element and then that element points to a list
There is also a “free list”
There is only one flag for each slot T\[0,1,2….m-1\]
To insert an element ‘x’ we will first check T\[h(x.key)\] to see if it is free. If it is free then we insert T\[h(x.key)\] and change the flag = 1
If it was not free, then there is a list, so we insert it at the beginning of the list
To delete we will check x.prev and x.next to see if they are NULL. So when we delete the element ‘x’ we will be left with an empty list at that slot. So we insert T\[h(x.key)\] into the free list and update the flag to 0 and then delete the element x from the list its stores in
What I don’t understand is the functionality of maintaining a free list?
Is there a single free list for the whole hash table or does each slot have its own free list?
Also why insert the element to be deleted into the free list and then delete it? Why don’t just delete it without using the intermediate free list?
I am unable to visualize the use of the free list as mentioned in the question.

# Answer
> 3 votes
Practical implementations that I have seen worked like this:

1. In a hash table, a slot is either used (contains a hash value and a value), has been never used, or has been used and emptied, and we need to distinguish this. With no additional space if at all possible.
2. If the values are pointers, and neither “all bits zero” nor “all bits one” are valid pointers, then we store “all bits zero” or “all bits one” as data to mark a “never used” or “not used anymore” slot.
3. If (2) doesn’t work: There are many more possible hash values than slots. Therefore most hash values never happen. We pick two random hash values which we store as the hash value to represent “empty” and “not used anymore” slots. As long as these are not used, fine. If they are used, we pick two different random hash values and modify the table accordingly (number of slots used should be less than the square root of possible hash values).

I’ve never seen a “free list” being used, because the hash value determines where an entry needs to be stored. Everyone just uses an array.

---
Tags: algorithms, hash-tables, hashing
---


# Question
Title: Can this "double pop" Heapsort variation speed up sorting on average?
For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-heapified". This to me seems somewhat inefficient. We have more knowledge from the maxheap, namely, that the root node and one of its children are the 2 largest elements in the maxheap (assuming the children of the root have different values). So why not pluck off the root node and the larger child, and THEN re-heapify? That should reduce the number of comparisons and movements. What we are attempting here is to exploit the fact that we have knowledge of where the 2 largest elements are in a maxheap so it makes sense to grab BOTH of them, not just the root node. Also when swapping in the 2 elements from the tail end of the tree, part of the enhancement is to put the larger of those 2 as the new root node and the smaller as the replacement for the other element (the larger child of the root we "popped"). Reason being that we might get lucky and maintain the maxheap property this way (as can be seen from the second example trace), thus avoiding excessive sifting down.

So I am wondering if and how this possible tweak will change the analysis of heapsort and if (and by how much) it may (or may not) speed up heapsort on say 1 million random integers (or some reasonable number where a speedup or slowdown can be noticed easily).

Hand trace results of (9,5,8,4,1,6,2). This is the input array I would like sorted in ascending order using Heapsort. I cannot draw out the heaps here so I will just list them in the parenthesis for each step and the operations are pop (pull an item out of the heap from the root position and place it one position past the end of the heap, thus holding that position as part of the sorted output), top (move an item from the tail end of the heap to the root), and swap (exchange positions of 2 items that are both still in the heap). Note that data will not be "clobbered" and it is assumed if we move data into a certain position where data already is, that "old" data is saved somewhere temporarily for later use (such as to be moved elsewhere in the heap).

So first using classic Heapsort:

(9,5,8,4,1,6,2) this is already a maxheap.

step 1. pop 9 (according to the rules above, the 2 will not be clobbered)
step 2. top 2
(2,5,8,4,1,6) 9 this is NOT a maxheap.

step 3. swap 2 and 8
(8,5,2,4,1,6) 9 this is STILL not a maxheap.

step 4. swap 2 and 6
(8,5,6,4,1,2)

step 5. pop 8
step 6. top 2 (notice 2 is bouncing between root & leaf often which is bad).
(2,5,6,4,1) 8 9

step 7. swap 2 and 6 (again).
(6,5,2,4,1)

step 8. pop 6
step 9. top 1
(1,5,2,4) 6 8 9

step 10: swap 5 and 1.
(5,1,2,4) 6 8 9

step 11: swap 1 and 4.
(5,4,2,1)

step 12: pop 5
step 13: top 1
(1,4,2) 5 6 8 9

step 14: swap 1 and 4.
(4,1,2)

step 15: pop 4
step 16: top 2
(2,1) 4 5 6 8 9

step 17: pop 2
step 18: top 1
1 2 4 5 6 8 9 (DONE in 18 steps).

General comments about classic Heapsort... There seems to be too much readjusting of the heap because of low values being put at the root of the heap and that induces many required swaps which although those reform the maxheap, they waste some processor time.

Now look what happens if instead of just popping 1 element (the root node) at each maxheap, we instead pop the root AND the larger child (if one exists):

(note that we grab the 2 last entries still in the maxheap and the larger of those becomes the new root and the smaller fills in the space of the 2nd element we popped). So we introduce a new function called nrc which stands for new root child and means to put an element as the new child of the root which had one of its children (the larger) popped (so we are filling in the missing space)

Starting with the same (9,5,8,4,1,6,2) which is already a maxheap...

Step 1: pop 9 (the root node)
Step 2: top 6 (move the larger of 2 last leaves in the heap as the new root)
Step 3: pop 8 (the larger of the 2 children of the root)
Step 4: nrc 2 (fill in the tree position of the larger child of the root)

(6,5,2,4,1) 8 9 (notice how we filled 2 spots in the sorted portion of the array in one pass before checking if we have to reheapify the entire tree).

Luckily, this modified tree is STILL a maxheap so we pluck 2 more elements.

Step 5: pop 6
Step 6: top 4
Step 7: pop 5
Step 8: nrc 1

(4,1,2) 5 6 8 9

Luckily, this modified tree is STILL a maxheap so we pluck 2 more elements.
Step 9: pop 4
Step 10: pop 2
Step 11: top 1 (only 1 element left so that is the new root and we are done)

1 2 4 5 6 8 9 DONE in only 11 steps! This is 7 fewer steps than classic Heapsort took and there are 0 swaps in this example. That is somewhat by luck, but also because we are putting the higher of the last 2 remaining elements still in the heap as the new root, and cuz we are plucking 2 elements from the heap at each pass (so there are less iterations that might require a swap). It seems this first example is showing promising signs for this "double pop" modification. Also, one of the nice things about this mod is that it should be a fairly straightforward implementation change once you have the classic heapsort code working properly.

# Answer
This technique of "double pop" belongs to the general idea of loop unrolling. Similarly, we could have "double selection" variant of selection sort, which will select the smallest and second smallest elements together while scanning the unsorted elements. We could also have "double insertion" variant of insertion sort, which will insert two elements together, where we can compare two elements first.

---

As promised by OP, it is quite easy to follow his pseudocode, despite the difference that indices in the pseudocode start from one while indices in my Java or C++ start from 0.

I made several improvements after porting the procedure `Heapsort2` to java, which I renamed to `doublePopHeapsort`.

* all four variables, `lg1`, `lc`, `lg2` and `lcp` are eliminated.
* the loop variable `i` and the conditional check `if (i >= 3)` are removed.

Here is my code for the method `doublePopHeapsort`, that is valid both in Java and in C/C++. The method `buildMaxHeap` and `heapify`, not listed here, are the same for both ordinary heapsort and doublePopHeapsort.

```
    // A is the given array of length n.
    void doublePopHeapsort() {
        if (n <= 1) return;

        buildMaxHeap();

        /* Grabs 2 largest numbers in maxheap each pass */
        while (--n > 2) {
            swap(0, n);
            --n;
            if (A[1] >= A[2]) {
                swap(1, n);
                heapify(1);
            } else {
                swap(2, n);
                heapify(2);
            }
            heapify(0);
        }

        /* regular heapsort to handle no more than 3 unsorted elements. */
        do {
            swap(0, n);
            heapify(0);
        } while (--n > 0);

```

Here on repl.it is my benchmark program that compares the performance of a version of ordinary heapsort and its corresponding version of double-pop heapsort. Hit the "run" button and see the results. However, the results over there fluctuates too much to be reliable at all, because, I assume, it runs on a shared machine with forceful time-sharing management.

Instead, I use my local compute. My computer is a "2.2 GHz Quad-Core Intel Core i7" with "16 GB 1600 MHz DDR3". Java version is "Java HotSpot(TM) 64-Bit Server VM (build 14.0.1+7, mixed mode, sharing)". I have run the benchmark program for many hours using various parameters. Here are typical results for arrays of integers that are randomly distributed over an interval.

```
   "Array size" is the size of array to be sorted.
   "Variations" is the number different arrays.
   "repetitions" is the number of times the same array is sorted.
   "ordinary total" is the total time used by ordinary heapsort.
   "double-pop total" is the total time used by double-pop heapsort.

       Array size: 10
       Variations: 10000
       repetition: 43429
   ordinary total: 41944 ms
 double-pop total: 36771 ms
 average speed-up: 14.1%

       Array size: 100
       Variations: 10000
       repetition: 2171
   ordinary total: 43297 ms
 double-pop total: 40672 ms
 average speed-up: 6.5%

       Array size: 1000
       Variations: 1000
       repetition: 1447
   ordinary total: 100123 ms
 double-pop total: 97193 ms
 average speed-up: 3.0%

       Array size: 10000
       Variations: 1000
       repetition: 108
   ordinary total: 107437 ms
 double-pop total: 105253 ms
 average speed-up: 2.1%

       Array size: 100000
       Variations: 100
       repetition: 86
   ordinary total: 108346 ms
 double-pop total: 106668 ms
 average speed-up: 1.6%

       Array size: 1000000
       Variations: 100
       repetition: 7
   ordinary total: 121017 ms
 double-pop total: 119892 ms
 average speed-up: 0.9%

       Array size: 10000000
       Variations: 10
       repetition: 6
   ordinary total: 147249 ms
 double-pop total: 145372 ms
 average speed-up: 1.3%

```

The above data indicates convincingly that double-pop heapsort is faster than ordinary heapsort. The improvement ranges from more than 10% for very short arrays to about 1% for large arrays.

It might be argued that the improvement should be better for larger array since the time saving of double-pop heapsort over the ordinary heapsort comes from less call to the `heapify` method. The cost of `heapify` depends largely on the depth of the leaf elements of the heap. However, as seen from the data above, the improvement as a percentage decreases as the size of array increases. Further analysis is needed to understand why.

---

I have also written a program that counts the number of swaps used. Here are the typical results, again for arrays of integers that are randomly distributed over an interval.

```
      Array size: 10
      Variations: 1000000
  ordinary total: 25109682 swaps
double-pop total: 21020795 swaps
    swap savings: 19.5%

      Array size: 100
      Variations: 100000
  ordinary total: 82995859 swaps
double-pop total: 73891119 swaps
    swap savings: 12.3%

      Array size: 1000
      Variations: 100000
  ordinary total: 990804913 swaps
double-pop total: 931577233 swaps
    swap savings: 6.4%

      Array size: 10000
      Variations: 1000
  ordinary total: 1115005054 swaps
double-pop total: 1050774991 swaps
    swap savings: 6.1%

      Array size: 100000
      Variations: 1000
  ordinary total: 2689951677 swaps
double-pop total: 2575706461 swaps
    swap savings: 4.4%

      Array size: 1000000
      Variations: 100
  ordinary total: 4594778322 swaps
double-pop total: 4430536135 swaps
    swap savings: 3.7%

      Array size: 10000000
      Variations: 100
  ordinary total: 26978266897 swaps
double-pop total: 26314038249 swaps
    swap savings: 2.5%

```

The percentages of swap saving of double-pop over ordinary heapsort are roughly compatible with the typical result above of performance. Higher savings implies greater speed-up, roughly.

It is expected the performance of double-pop heapsort may vary on different situations such as size of input array, type of array elements, programming language and the compiled code, cpu and memory type, cold or warmed-up run. Although it is not a surprise that it may take more time for double-pop heapsort than an ordinary heapsort to sort a particular array, double-pop heapsort is faster than heapsort in general.

---

Further investigation may include the following and more.
> 2 votes

# Answer
If you pluck your largest child in place of root then you have to pluck something in now empty space after your max child. If you pluck its max child... you need to apply it until leaf, so this change will result in different order of same operations or break indexing scheme for heap.

Heap uses properties of complete binary tree, if you just move pointer, then you have broken indexing scheme and need to remember new place of root and its children. If you continue this way, you have to fix your heap or keep indices, so more memory and more work.

Please check how it really works, prove it doesn't break anything and make proper average case analysis, because some random test (as requested, by some random people on internet) with relatively big input does not prove speedup, it only shows that given sample benefits from it. Making more random tests is still not enough, it is pure luck or not random enough PRNG.
> 2 votes

# Answer
Actually I tried implementing this and I do see a slight (3%) speedup in most cases, but I used an interpreted language so I am not sure if similar results would happen for a compiled language. My main test was I used 100,000 randomly generated integer numbers in the range 0 to 99,999 and tried sorting them with both "classic" heapsort and my modified heapsort. All of the test data is integer numbers only (no floating point, no strings...).

The code just grabs the 2 "highest" numbers in the maxheap, then calls Heapify on those 2 nodes, making sure the swapped numbers in those positions don't violate the maxheap property. Depending on which child of the root is larger, it either calls Heapify(2) or Heapify (3), followed by Heapify(1).

Results: "Classic" Heapsort = 16.63 seconds runtime. My "double pop" variation: 16.15 seconds (about 3% quicker in actual speed). The computer I used to test was an old Dell inspiron 1420 laptop slowed to 1.0 Ghz (but capable of up to 1.67 Ghz), with 4GB main memory.

Other test results were as follows (classic first then mine): (in seconds)

Already sorted (in order): 17.4 vs. 16.85.
Backwards sorted : 15.84 vs. 15.37.
All same numbers: 1.308 vs. 1.44 (mine is actually slower in this case).
Small range random numbers (0-99): 16.5 vs. 16.03.

n = # of elements in the unsorted heap (will get decremented as we sort)
FI = shorthand for ENDFOR.
LOCAL means those variables are only visible within the procedure defined.
You will need to generate your own random numbers for testing.

Here is the "classic" Heapsort pseudocode:

---

PROCEDURE Heapsort()

LOCAL i

BuildMaxHeap()

FOR i = n TO 1 STEP -1
...Swap(1, i)
...n = n - 1
...Heapify(1)
ENDFOR i

RETURN

---

PROCEDURE Swap(p1, p2) ..... /\* p1 and p2 are the array positions to swap \*/

LOCAL temp

temp = A\[p1\]
A\[p1\] = A\[p2\]
A\[p2\] = temp

RETURN

---

PROCEDURE BuildMaxHeap

LOCAL i

FOR i = INT(n/2) TO 1 STEP -1
...Heapify(i)
ENDFOR i

RETURN

---

PROCEDURE Heapify(i)

LOCAL left, right, max

left = i + i
right = left + 1

IF (left \<= n) AND (A\[left\] \> A\[i\])
...max = left
ELSE
...max = i
FI

IF (right \<= n) AND (A\[right\] \> A\[max\])
...max = right
FI

IF max # i
...Swap(i, max)
...Heapify(max)
FI

RETURN

---

"This is my modified Heapsort which grabs 2 numbers at a time"
lg1 is the first largest number we want.
lg2 is the 2nd largest number we want.
lc = largest child.
lcp = largest child position.

```

PROCEDURE Heapsort2()  /* Grabs 2 largest numbers in maxheap each pass */

LOCAL i, temp, lc, lcp, lg1, lg2

FOR i = n TO 1 STEP - 1

  IF (i >= 3)  /* make sure there are at least 2 children to check */
    lg1 = A[1]
    lc = Larger(A[2], A[3])  /* larger valued child of root node */
    lg2 = IIF(lc = A[2], lc, A[3])
    lcp = IIF(lc = A[2], 2, 3)
    A[1] = A[i]
    A[i] = lg1
    i = i - 1
    A[lcp] = A[i]
    A[i] = lg2
    n = n - 2     /* the unsorted heap is now 2 elements smaller */
    Heapify(lcp)  /* re-heapify the larger child we swapped data with */
    Heapify(1)

  ELSE  /* regular Heapsort to handle when there are < 3 unsorted nodes left. */
    Swap(1, i)
    n = n - 1
    Heapify(1)
  FI

ENDFOR i

RETURN

```
> 1 votes

---
Tags: optimization, sorting
---


title: Bitwise XOR of regular languages

text:
# Question
Title: Bitwise XOR of regular languages
Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language?

For example, consider $$L=\\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \\},$$ where $A$ and $B$ are both regular languages.

Can I say that $L$ is also a regular language?

# Answer
> 2 votes
You can show that $L$ is regular by using an NFA. Briefly, the NFA is going to simulate DFAs for $A$ and for $B$, guessing the decomposition of the input into $x \oplus y$ as it goes. The same works for any other operation such as AND and OR.

In more detail, suppose that we are given DFAs for $A,B$:

* Sets of states $Q^A,Q^B$.
* Initial states $q\_0^A,q\_0^B$.
* Final states $F^A,F^B$.
* Transition functions $\delta^A,\delta^B$.

We construct an NFA for your language $L$ as follows:

* Set of states is $Q^A \times Q^B$.
* Initial state is $\langle q\_0^A,q\_0^B \rangle$.
* Final states are $F^A \times F^B$.
* Transition function is $$ \begin{align} &\delta(\langle q^A,q^B \rangle, 0) = \\{\langle \delta^A(q^A,0), \delta^B(q^B,0) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,1) \rangle \\}, \\ &\delta(\langle q^A,q^B \rangle, 1) = \\{\langle \delta^A(q^A,0), \delta^B(q^B,1) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,0) \rangle \\}. \end{align} $$ You can prove inductively that $$ \delta(\langle q^A,q^B \rangle, w) = \\{ \langle \delta^A(q^A,x), \delta^B(q^B,y) \rangle \mid x \oplus y = w \\}, $$ from which the correctness of the construction easily follows.

# Answer
> 2 votes
Consider the one-state (non determinstic) transducer $\tau$ from $\\{0,1\\}^\*$ to $\\{0,1\\}^\* \times \\{0,1\\}^\*$ defined by the transitions $0 \to (0,0)$, $0 \to (1,1)$, $1 \to (0,1)$ and $1 \to (1,0)$. Now $$ \tau^{-1}(A \times B) = \\{u \in \\{0,1\\}^\* \mid \tau(u) \cap (A \times B) \not= \emptyset \\}= L $$ Since $A$ and $B$ are regular, $A \times B$ is a recognizable subset of the monoid $\\{0,1\\}^\* \times \\{0,1\\}^\*$ and thus $L$ is regular.

# Answer
> 0 votes
Assume we have finite state machines for languages X and Y. Let f(a, b) be any function of two symbols x and y, and let F(A, B) for strings A, B of same length be the string consisting of the symbols f(a\_i, b\_i). Let g(c) be the set of all pairs (a, b) such that f(a, b) = c. And we want the language L = { F(A, B): A, B have same length, A is in X, B is in Y }.

We try to build a finite state machine for L.

If we process a symbol c, two state machines for X and Y would process any pair of symbols (a, b) where f (a, b) = c, in other words any pair of symbols (a, b) element of g(c).

So if these two state machines were in states S\_i and T\_j, they would transfer into any pair of states that the first machine would transfer to with input a, and the second would transfer to with input b.

This tells us what the states of the state machine for L should look like: Each state for L is a set of pairs (S\_i, T\_j) where S\_i, T\_j) are states of the state machines for X and Y. The initial state is { (S\_0, T\_0)} }. A state is accepting if any of the pairs (S\_i, T\_j) consists of two accepting states.

To calculate the state we transition to from one state with input c: Let the state be the set { (S\_i, T\_j) }. Let { (a\_n, b\_m) } be the set of pairs with f(a\_n, b\_m) = c. Then the new state is the set of all states that S\_i transitions to with input a\_n, and S\_j transitions to with input b\_m.

Yours is a special case. Since we can construct a state machine, it's regular. If X and Y have I and J different states, then there are I\*J pairs of states, and $2^{I\*J}$ different sets of pairs of states, which is the maximum number of states needed for L.

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


title: convert RE to NFA

text:
# Question
Title: convert RE to NFA
The Regular Expression i am having trouble with is the following a(b|bcc\*)\*c. My main concern is what do i do with the c\*? I can lay the rest of the diagram correctly (i think) but that part is beyond me. Any help would be great, thank you. What i have:

# Answer
> 0 votes
Your NFA does not recognize $abcc \in L$. To fix it you need to make $2$ non-final and then either:

* Change the label of edge $(5,2)$ from $c$ to $\varepsilon$; or
* Delete vertex $5$. Add the edges $(4,4)$ and $(4,2)$ with label $c$.

# Answer
> 0 votes
I simplified your NFA and I got this DFA:

>

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


# Question
Title: Representation of -40 in 8bit computer using 2's complement
What is the representation of -40 in a 8bit computer using 2's complement intiger?

# Answer
> 1 votes
First of all, 40 in binary is 101000.

The 8-bit representation is obtained by zero-padding: 00101000.

The one's complement of this is obtained by inverting the bits: 11010111.

To obtain the two's complement, we simply add 1: 11011000.

---
Tags: computer-architecture
---


# Question
Title: Efficiently finding the intersections of sets that yield a desired set
Given a collection of sets $\\{S\_1, S\_2, \dots, S\_n\\}$, find all the "reduced" intersections between those sets that yield the desired set $\\{x\\}$ as the result. A "reduced" intersection is defined as an intersection between sets where $S\_i\cap S\_j\cap \dots \cap S\_k = \\{x\\}$, such that removing any one of the sets in the intersection changes the result from the desired set $\\{x\\}$ to something else.

For example, for the collection of sets $\\{A,B,C,D,E,F\\}$, where:

$A = \\{c,d,f,g,x\\}$,

$B = \\{c,d,g,p,t,x\\}$,

$C = \\{e,i,x,y\\}$,

$D = \\{a,i,o,p,q,w,x\\}$,

$E = \\{f,t,w,x\\}$, and

$F = \\{a,b,c,d,e\\}$, then:

* $A \cap B \cap E = \\{x\\}$ is a reduced intersection, because $A\cap B = \\{c,d,g,x\\}$, $A\cap E = \\{f,x\\}$, and $B\cap E = \\{t,x\\}$. Removing any of the sets $A$, $B$, or $E$ from the intersection $A \cap B \cap E$ yields a different result than the desired set $\\{x\\}$.
* $C \cap D \cap E = \\{x\\}$ is NOT a reduced intersection, because $C\cap E = \\{x\\}$. Removing set $D$ from the intersection $C \cap D \cap E$ still yields the desired set $\\{x\\}$ as the result.

My question is: given a collection of sets, what is the most efficient algorithm to find all the reduced intersections between those sets that yield a desired set?

Note that it doesn't matter whether the desired set has only a single element in it or not. In this example, I just used a single element $x$ for simplicity.

# Answer
Your problem is equivalent to enumerating all inclusion-minimal set covers, a problem addressed here.

Suppose that you're looking for all collections of sets whose intersection is some set $T$. All the relevant sets must contain $T$, so you can just consider all sets containing $T$, and remove $T$ from all of them. This reduces to the case $T = \emptyset$.

Now let $U$ be the union of all sets. The intersection of a collection of sets is empty iff the union of their complements is $U$. In other words, if you complement all sets, then you're interested in inclusion-minimal set covers.
> 0 votes

---
Tags: algorithms, sets, finite-sets
---


# Question
Title: Decision tree lower bound for finding two array elements summing to zero
I have to solve this exercise:

> Given an unordered array $A\[1\], \ldots, A\[n\]$ of positive and negative integers, determine if there are two indices $i \neq j$ such that $A\[i\] + A\[j\] = 0$. Establish a lower limit to the problem using the decision tree technique.

The solution should be $Ω(\log s(n))$, where $s(n)$ is number of possible solutions, in this case $n^2$.

But, I don't understand why the number of possible solutions is $n^2$ rather than $\binom{n}{2}$.

# Answer
You're right that there are only $\binom{n}{2}$ many inequivalent solutions. Fortunately, $\Omega(\log \binom{n}{2}) = \Omega(\log n)$, so there isn't much difference between $\binom{n}{2}$ and $n^2$, in this regard.

However, this is a pretty bad lower bound. You haven't specified which queries are allowed, but assuming you're allowed to compute signs of constant degree polynomials, then I would expect an $\Omega(n\log n)$ lower bound, since the similar problem Element Distinctness has such a lower bound. This also matches the upper bound obtained by sorting (assuming your model supports this).

Indeed, this is just 2SUM (a sibling of the more famous 3SUM problem), and an $\Omega(n\log n)$ lower bound was proved by Chan, Gasarch and Kruskal in their paper Refined Upper and Lower Bounds for 2-SUM.
> 3 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, lower-bounds
---


# Question
Title: Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$
I cannot understand the first paragraph of the proof, which comes from the known book *Introduction to Algorithms, third-edition*, and I consider it has some errors, could anyone help me check about it?

Possible errors:

1. It first prove the case $\text{height(x)=0},$ then it says "For inductive steps, consider a node $x$ that has **positive height**".

From my understanding of inductive proof, the base case should be able to trigger the inductive statement. I mean: the "first domino" should trigger the next one, so the statement should be something like **non-negative height**.
2. It says "each child has a black-height of either $\text{bh}(x)$ or $\text{bh}(x)-1$", but when applying, only the latter is used: $(2^{\text{bh}(x)-1}-1)+(2^{\text{bh}(x)-1}-1)+1=2^{\text{bh}(x)}-1$.

---

## Paragraph from the book:

# Answer
> 1 votes
The proof seems correct to me.

1) The base case proves the claim when the height of the subtree rooted at $x$ is $0$. The inductive step proves the claim for every subtree rooted at $x$ of positive height $h$ assuming that the claim is true for all subtrees of heights from $0$ to $h-1$. So the inductive step for $h=1$ is able to prove the claim for all subtrees of height $1$ using the fact that the claim is true for the base case, i.e., for all subtrees of height $0$. This is a standard proof by structural induction.

2) Each subtree $T\_u$ rooted in a child $u$ of $x$ has a black-height $bh(u)$ of either $bh(x)$ or $bh(x)-1$ but, in any case, the height of $T\_u$ is smaller than the height of the subtree $T\_x$ rooted in $x$. This means that the induction hypothesis can be applied, showing that the number of internal nodes is at least:

* $2^{bh(x)}-1$ if $bh(u)=bh(x)$; or
* $2^{bh(x)-1}-1$ if $bh(u)=bh(x)-1$.

In any case the number of internal nodes of $T\_u$ is at least the smaller of the above two quantities, i.e., $\min\\{ 2^{bh(x)}-1, 2^{bh(x)-1}-1 \\} = 2^{bh(x)-1}-1$. This means that the number of internal nodes in $T\_x$ is at least:

$$ 2 \cdot ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)}-1. $$

---
Tags: trees, proof-techniques, induction, red-black-trees
---


# Question
Title: Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$
I am trying to find a context sensitive grammar for the type-1 language

$L = \\{a^ib^jc^k \mid 0 \leq i \leq j \leq k\\}$

I can construct the first part with

\begin{align\*} S &\to aSbB \mid B \mid \epsilon\\ B &\to bB \mid \epsilon\\ \end{align\*}

but how do I continue from there? I tried

\begin{align\*} S &\to aSbBcC \mid B \mid \epsilon\\ B &\to bBcC \mid \epsilon\\ CB &\to BC \\ C &\to cC \end{align\*} but this does not seem to work e.g. $S \to aSbBC \to aaSbBCbBC \to aabBCbBC$

# Answer
> 1 votes
$$ \begin{align\*} S &\to XABS' \mid XBS' \mid XS' \mid XAB \mid XB \mid X \mid \epsilon \\ S' &\to ABCS' \mid BCS' \mid CS' \mid C \\ \\ BA & \to AB \\ CA & \to AC \\ CB & \to BC \\ \\ XA &\to aX \\ X &\to Y \\ YB &\to bY\\ Y &\to Z \\ ZC &\to cZ \\ Z &\to c \end{align\*} $$

For the intuition behind this construction see this question.

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


# Question
Title: The Partition Problem: Reducing to prove NP-Completeness
I am struggling with the below problem. Curious to hear any guidance.

---

The Partition Problem is the following:

$\textbf{Instance:}$ A multiset of numbers $S = \\{a\_1, a\_2, \ldots , a\_n \\}$.

$\textbf{Question:}$ Can $S$ be partitioned into two multisets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Prove that the Partition Problem is NP-complete.

---

Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Is anyone able to help shed some light on this? Also, any explanation in plain English (maybe with some notation) would be greatly appreciated as I'm struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

Thank you in advance!

# Answer
> 1 votes
Partition is equivalent to a special case of the subset-sum problem: $S$ can be partitioned into two sets $A$ and $B$ such that $\sum\_{x \in A} x = \sum\_{x \in B} x$ if and only if $\exists S' \subseteq S$ such that $\sum\_{x\in S'} x = \frac{1}{2}\sum\_{x \in S}x$.

**Proof of $\implies$:** Given $A$ and $B$ that partition $S$ and are such that $\sum\_{x \in A} x = \sum\_{x \in B}$ you must have $\sum\_{x \in S}x =\sum\_{x \in A} x + \sum\_{x \in B} x = 2 \sum\_{x \in A} x \implies \sum\_{x \in A} x = \frac{1}{2}\sum\_{x \in S}x$. The claim follows by picking $S' = A$.

**Proof of $\Longleftarrow$:** Given $S' \subseteq S$ such that $\sum\_{x\in S'} = \frac{1}{2}\sum\_{x \in S}x$ you must have $\sum\_{x\in S \setminus S'} x = \sum\_{x \in S}x - \sum\_{x \in S'}x = \frac{1}{2}\sum\_{x \in S}x$. The claim follows by picking $A=S'$ and $B = S \setminus S'$.

---

To show that this special case of subset sum (i.e. partition) is in $\mathsf{NP}$ notice that a subset $S' \subset S$ such that $\sum\_{x \in S'} x = \frac{1}{2}\sum\_{x \in S}$ is a yes-certificate.

To see that this special case of subset sum is still $\mathsf{NP}$-hard consider an instance $\langle S, T \rangle$ of subset sum where $S$ is a (multi-)set and $T$ is the target value. Let $M = \sum\_{x \in S} x$.

Create a new instance subset sum $\langle \overline{S}, \overline{T} \rangle$ where $\overline{S} = S \cup \\{ M-2T \\}$ and $\overline{T}=M-T$.

If there is a solution $S' \subseteq \overline{S}$ to $\langle \overline{S}, \overline{T} \rangle$ then $\sum\_{x \in S'} x = \sum\_{x \in \overline{S} \setminus S'} x= M-T$ (since the sum of the elements in $\overline{S}$ is $2(M-T)$). At least one of $S'$ and $\overline{S} \setminus S'$ contains element $M-2T$, call this set $S^\*$. Then the $S^\* \setminus \\{M-2T\\}$ is a subset of $S$ and the sum of its elements is $(M-T)-(M-2T)=T$, showing that the original instance $\langle S, T \rangle$ is a yes instance.

On the other hand, if there is a solution $S' \subseteq S$ to $\langle S, T \rangle$, then the set $S' \cup \\{ M-2T \\}$ is a subset of $\overline{S}$ and the sum of it's elements is $T + (M - 2T) = M-T = \overline{T}$, showing that $\langle \overline{S}, \overline{T} \rangle$ is a yes instance. This concludes the proof.

---
Tags: np-complete
---


# Question
Title: Converting a number to 16-bit Floating Point Format
I want to convert the number -29.375 to IEEE 745 16-bit floating point format. Here is my solution:

The format of the floating point number is: 1 sign bit unbiased exponent in 4 bits plus a sign bit 10 bits for the mantissa plus the explicit 1

First, I realize that 29.375 = 29 + 3/8.
Then realize that:
29 = 16 +13 = 16 + 8 + 5 = 16 + 8 + 4 + 1 1 1101.011 = 1.1101 0110 * 2^3

This gives us:
mantissa is: 1101 011000
sign: 1
exp: 00011

Hence in 16 bits, we have: 1000111101011000

Do I have this right? I was hoping that there would be a calculator on the web that I could use but I could not find one. They were all at least 32-bits.

# Answer
> 2 votes
First of all, the IEEE 745 16-bit format has:

* 1 bit for the sign.
* 5 bits (not 4) for the **biased** exponent. The bias is $15$.
* 10 bits for the mantissa. The leading $1$ is **implicit** (not explicit).

The calculation is incorrect since $(29.375)\_2 = (11101.011)\_2 = (1.1101011)\_2 \cdot 2^4$ (and not $2^3$).

Then:

* The sign bit is $1$ because the number is negative.
* The unbiased exponent is $(4)\_{10} = (100)\_{2}$ and therefore the biased exponent is $(19)\_{10} = (10011)\_2$.
* The mantissa, without the implicit leading $1$ and padded to 10 bits with trailing zeros, is $(1101011000)\_2$.

Then the final $16$-bit number is: $1100111101011000$.

---
Tags: floating-point, numerical-algorithms
---


# Question
Title: L= { x=y+z| x,y,z are binary integer, and x is the sum of y and z}
The alphabet is {0,1,+,=}.

I think it is a regular language since i can construct the NFA,

But i want to make sure

Thanks

# Answer
> 1 votes
Your language is not regular: $$ L \cap (\mathbf0+\mathbf1)^\*\mathbf=(\mathbf0+\mathbf1)^\*\mathbf{+0} = \\{x\mathbf=x\mathbf{+0} \mid x \in \\{\mathbf0,\mathbf1\\}^\*\\}, $$ which is easily seen to be non-regular.

# Answer
> 0 votes
Let bin(k) be the number k, represented by a binary string. Take any integer n ≥ 0, and let $z\_n$ = "bin(n) + 0 =". $z\_n$ must be followed by bin(n) to get a string in L. If n ≠ m then bin(n) ≠ bin(m), therefore the state reached after parsing $z\_n$ must be different from the state reached after parsing $z\_m$. Therefore the number of states is not finite, and therefore L is not regular.

---
Tags: formal-languages
---


title: Monotonic queues recurrence relation

text:
# Question
Title: Monotonic queues recurrence relation
I'm looking at the following explanation of monotonic queues and their applications in problem solving.

Monotonic Queue Summary

I have a reasonable understanding of this data structure and the problems described in the post. However, i'm struggling with the following "recurrence relation"

```
Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

```

I don't completely understand this formula. It looks like a recurrence relation but seems to to be in reference to the underlying array. I can't seem to see if the previous array range (j to k) is referring to a portion of the array or a portion of previously solved sub-problems.

I'm not sure what the base case is and it seems like the answer is the minimum value in this array range plus some constant. I don't see how this solves the problems above.

Am I looking for too much precision in this statement or am I missing something?

The following seems more intuitive

```
Any DP problem where DP[i] = smallest(prefix_sums[j:k]) where j < k <= i and prefix_sums[k] - prefix_sums[j] >= K

```

# Answer
> 2 votes
It is no wonder that you are confused.

One characteristic of DP problem is the recurrence relation that combines solutions to subproblems to a solution to larger subproblems. That article presents the following general "recurrence relation".

```
Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

```

However, because the same `A` appears on both sides of the equation, that "recurrence relation" cannot be specialized/instantiated as the recurrence relation of any problem listed in that article.

Instead of "DP problem", this kind of problem should better called "sliding window problem", or "SW problem". Basically, a first-in-first-out queue sliding over the given array are used to track the useful entries. We could argue that "SW problem" is a special kind of "DP problem", where the overlapping subproblems are to fill those sliding windows. Each sliding window will lead easily to a solution for the original problem at one end of a window. Or, if you prefer a visual identification of the "DP problem" as "table-driven bottom-up memoization", an "SW problem" is supposed to be solved by tracking useful data in a table moving across the given array.

An "SW problem" does not have the usual form of recurrence relation, as can be checked against all problems listed in that article. Instead of `Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i`, it should have been something like `Any problem to find M[i] where M[i] is defined as something like min(A[j:k]) where j < k <= i given array A`.

This technique, "sliding window" is indeed very powerful and easy to use. Except the glaring lapses mentioned above, that article is pretty nice. I encourage you to read the full article, ignoring that summary statement or using my replacement above.

---
Tags: data-structures, dynamic-programming, queues
---


# Question
Title: How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?
I came with this interesting question and could understand how did we get to this equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$

But in the next step, it reached to the following step which I cannot understand. Please help me out in understanding this:

$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$ Reference: Problem 6.3.3, CLRS. Difficulty understanding the solution of heap problem in CLRS book?

Thank you.

# Answer
Before starting, let me note that there seems to be an "off by 1" issue with the way that height is measured. It seems that you should replace $h$ throughout with $h+1$.

First of all, let us notice that $2^{\lfloor \lg n \rfloor} \leq 2^{\lg n} \leq n$. Therefore $$ (k-1)2^h + k(2^{h-1} + 1) \leq n. $$ Next, notice that $$ (k-1)2^h + k(2^{h-1} + 1) = k(2^h + 2^{h-1} + 1) - 2^h. $$ Therefore $$ k(2^h + 2^{h-1} + 1) \leq n + 2^h. $$ This immediately implies that $$ k \leq \frac{n + 2^h}{2^h + 2^{h-1} + 1} \leq \frac{n + 2^h}{2^h + 2^{h-1}} = \frac{n + 2^h}{(3/2)2^h}. $$

Now, $h + 1 = \lfloor \lg n \rfloor \le \lg n$, and so $2^{h+1} \leq n$, implying $2^h \leq n/2$. Therefore $$ k \leq \frac{n+2^h}{(3/2)2^h} \leq \frac{n+n/2}{(3/2)2^h} = \frac{(3/2)n}{(3/2)2^h} = \frac{n}{2^h} \leq \left\lceil \frac{n}{2^h} \right\rceil. $$
> 1 votes

---
Tags: heaps
---


# Question
Title: Several closure operations for regular languages
> Assuming that $L\_a$ is a regular language and $\Sigma=\\{0,1\\}$, prove that the following languages are regular:
>
> $$L\_1 = \\{u \mid \exists v\in\Sigma^\* \\, uv \in L\_a\\}$$
>
> $$L\_2 = \\{w \in \Sigma^\* \mid \exists x \in L\_a \\, n\_0(w) = n\_0(x) \\}$$
>
> $$L\_3 = \\{uv \mid u \in L\_a \text{ and } v \notin L\_a^{R}\\}$$
>
> where $n\_0(w)$ is the number of zeroes in $w$.

# Answer
> 0 votes
Let $\Sigma' = \\{\sigma' \mid \sigma \in \Sigma\\}$ be a copy of $\Sigma$. Let $e\colon (\Sigma \cup \Sigma')^\* \to \Sigma^\*$ be the homomorphism that erases the tags, and let $d\colon (\Sigma \cup \Sigma')^\* \to \Sigma^\*$ be the homomorphism that deletes all tagged letters. Then $$ L\_1 = d(e^{-1}(L\_a) \cap \Sigma^\* (\Sigma^{\prime\*})).$$

Let $d\_1\colon \Sigma^\* \to \Sigma^\*$ be the homomorphism that deletes all $1$s. Then $$ L\_2 = d\_1^{-1}(d\_1(L\_a)). $$

Finally, $$ L\_3 = L\_a \overline{L\_a^R}. $$

---
Tags: regular-languages
---


# Question
Title: Weighted interval set scheduling problem
Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is maximized. This can be solved in linear time with dynamic programming or memoized recursion.

Is there a version of this problem where intervals are grouped, i.e. interval $a$ can only be in the solution if intervals $b$ and $c$ are also in the solution? By this formulation, there would be a weight associated with each group, or *set*, of intervals.

The most similar problem I've come across is the exact cover problem, which is NP-Complete, but in this instance we're maximizing weight and all vertices need not be covered.

Any insight will be much appreciated. Thanks!

# Answer
This is equivalent to the maximum weighted independent set problem - given a graph with weighted vertices, find a subset of the vertices such that no two vertices in the subset are adjacent in the graph and the sum of their weights is maximized.

The graph the problem is being solved on is a type of interval graph where each vertex represents a group of intervals and its weight is the sum of the intervals' weights. An edge is drawn between two vertices if one or more of their intervals overlap.

I haven't determined if this formulation is tractable or not. While the problem is NP-hard, we know it can be solved efficiently for certain types of graphs, including interval graphs where each vertex represents a single interval.
> 0 votes

# Answer
Sure, you can define any problem you want. Effectively you would no longer seek a cover of intervals, but a cover of sets, where each set is a union of intervals. Over a discrete set, any set can be expressed as a union of intervals. Thus, this is equivalent to the maximum set packing problem. Consequently, it is NP-hard.
> 0 votes

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: How could you "solve" the halting problem if, hypothetically, the busy beaver numbers were "small"?
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.

I'm trying to figure out how you could specifically do this. One obvious possibility is to build an n-state Turing machine that looks for a solution to an undecidable problem, then simply waiting for it to pass BB(n) transitions. This should be feasible since BB(n), in this scenario, is small, and surpassing it would prove that the machine loops forever.

But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large? Shouldn't we just assume that the machine is independent of number theory instead?

# Answer
To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.

Since the halting problem *isn't* computable, this means that no such $f$ is computable; this is a "global" phenomenon. No *particular* value of $BB$ is too large to be used, but rather the **growth rate** of $BB(n)$ prevents us from having a whole sequence of upper bounds, one for each $n$. As a low-level analogy:

> There is no polynomial function which is always above $exp(n)=2^n$. Of course, this isn't because individual values of $exp$ are too big, but rather because of the overall behavior of the function across all inputs .
> 1 votes

# Answer
> But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large?

The problem is not so much that BB(n) is very large, the problem is that it is not computable. Your supposed decision procedure would not work because it would not know whether we have surpassed BB(n) transitions or not.
> 0 votes

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


# Question
Title: Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$?
Is master theorem applicable for this example?

$$T(n)= 8T \biggl(\frac{n-\sqrt n}4\biggr)+ n^2$$

# Answer
The master theorem isn't applicable, but the Akra–Bazzi theorem is, and it shows that your recurrence has the same solution (asymptotically) as the simpler one without the square root, that can be solved using the master theorem.
> 0 votes

# Answer
Master theorem not applicable, see
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: Finding the point with minimum x-ordinate, lying between two y-ordinates
Given a set of points $P=p\_1,p\_2,..p\_n$ in $R^2$ in where $p\_i=(x\_i,y\_i)$,finding the point with smallest x-ordinate having y-ordinates between $y\_1$ and $y\_2$, where $y\_1$ and $y\_2$ are given as inputs. I can compare the point with other points which gives me an $O(n)$ time algorithm ? Can this be improved any further ?

# Answer
> 2 votes
Not unless you assume something more. Without further assumptions, if you don't check all $n$ values, the minimum can be some of the unchecked points.

If you know there is just one minimum in (sorted) range, a variant of binary search (the minimum is the point where $x\_{k - 1} \> x\_k \< x\_{k + 1}$ or one of the endpoints; if $x\_k \> x\_{k + 1}$ the minimum is to the right, and so on) gets it in time $O(\log n)$.

# Answer
> 1 votes
If the points are provided in an arbitrary order (not sorted or anything), then no, you cannot do better than $O(n)$ time. You must examine every point. This is easily proven using an adversary argument: if there is any point your algorithm doesn't inspect, then that point could have had a valid $y$-value and a smaller $x$-value than whatever your algorithm outputs, meaning that any such algorithm will have inputs on which it outputs the wrong answer.

# Answer
> 1 votes
A Computational Geometry answer would include a description of a data structure and analysed algorithms for preprocessing/set-up and queries.
There is Edward McCreight's Priority Search Tree, use a min heap on $x$ with $y$ medians for telling left from right. (The first point you encounter between $y\_1$ and $y\_2$ is the one with the lowest $x$ in range.)
*Not* storing the additional median in each node, but using the point's coordinate works almost as well *for well behaved sets*.

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


# Question
Title: Complexity classes closed under finite union and intersection, why not infinite union and intersection?
All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)

But such classes are not closed under infinite union and intersection. Why?

# Answer
Consider the "singleton" languages: $L=\\{w\\}$ for some fixed word $w$. (e.g., the language $L=\\{00010100\\}$ would be a singleton language) Most "nice" complexity classes include the singleton languages.

*Every* language can be written as an infinite union of singleton languages. So, if all singleton languages are in the class, and if the class is closed under infinite union, then all languages are in the class.

Thus, if there is any language at all that isn't in such a complexity class yet it does contain all the singleton languages, then the class cannot be closed under infinite union.
> 3 votes

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


# Question
Title: How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it wants to, like a "witness"). Later, the client will submit the token (and optionally the witness) and the server needs to be able to quickly determine if it is a token value that it (the server) has previously issued. The token does not need to be "secure", so a trivially forgeable token is okay. Ideally, the server can:

* Generate the tokens in O(1) time and space
* Validate that it issued the tokens in O(1) time and space

The most obvious solution to this problem as stated would be to simply use an incrementing counter as the token. The server stores a single integer and increments it when asked for a new value. Determining if the token has been issued by this server means simply ensuring that the token submitted by the client is \<= than the server's currently stored value.

The twist: The server might crash and get restored from a backup, meaning that its counter value might regress to a previous value. (We'll call this the regression value). If this happens, any tokens previously issued that are less than or equal to its regression value should be considered valid, but any tokens *previously issued* with a value higher than its regression value should be considered invalid since they were not generated by "this" instance of the server. In short, we need to detect a "fork" in our token issuing.

For example: Imagine I issued tokens T0 to T20. Then, I restore the server to a backup right after it had issued T10. I want the server to continue to validate/recognize T0-T10, but no longer recognize T10-T20. Furthermore, I want to make sure that it never re-issues tokens that are identical to the previously issued T11-T20.

The restored server doesn't know what the previously highest (MAX) issued token was. (If it did, it could "mark" any token values as invalid if they had a value between its current value and its max value.)

We also need to avoid the restored server issuing the same token its previous incarnation did. The integer counter scheme would not be capable of such a guarantee since it is not sure what the previous maximum token issued was. Thus, it wouldn't know what value to safely increment its counter to. One way to solve this would be to have a separate "restoration counter" to note the number of times the server has been restored. But presumably, if we were capable of saving this separate state somewhere, we could just store the previously maximum issued counter as well.

Another way to solve this problem would be to use timestamps as the token. Assuming an accurate clock, the restored server would be guaranteed to never issue the same value that its predecessor did. However, if we use a timestamp, the server no longer knows which *specific* timestamp tokens it ever issued in the past, unless it keeps track of a full list of them, bringing the time and space complexity well above O(1). (It could keep a list of the times it was restored from backup and reference this list when validating tokens, but this adds complexity to time and space for validation).

However, if there were a way to compactly store a list of N timestamps and an easy way to test a given timestamp for set membership, the problem would be easy to solve.

**Options I have considered:**

Option 1: Bloom filter: The server could use a bloom filter and add each number issued to its filter. Unfortunately, the set membership test would be probabilistic, but I could make the filter big enough to reduce my probability of a false positive quite low. However, it seems like the addition of information *other* than just the token value in the form of witness changes allows us to offload additional information to the clients that later ask for verification, and would allow us to do better somehow.

Option 2: A cryptographic accumulator, like an RSA accumulator. If each of the numbers I was generating were prime, I believe I could use an RSA accumulator to store a single accumulator value of constant size S, where S is significantly fewer bytes than storing a list of N. Each time I add a new prime to my set, I add it to the accumulator, then I generate its witness as well and ship both the number and the witness to my client. Later, the client would submit the integer it is testing, and the witness and I would be able to quickly determine if the number being submitted is in fact a member of my set or not. Possible problems: I need to be able to hash to a prime number deterministically. (Not the end of the world, but adds complexity.) I think I have to update my witness values as I add new values to the accumulator which adds time to the verification step. Lastly: My understanding of accumulators is rudimentary, and I'm not sure how large the accumulator needs to be in relation to the set being accumulated.

Option 3: I'm overthinking this tremendously.

\** Related problems: \**

* This seems a lot like having a lot of hash values in a Merkle tree or hash chain (blockchain), and wanting to be able to determine if a particular hash value were ever seen in the chain, *without* having to store every value that had been seen in the chain. I'm hopeful that with the additional concept of generating a "witness" value of some sort to be stored along with the number, the server can make a membership determination with much less overhead than having to store all of the numbers. (Coda uses techniques to keep its last chain in its blockchain deterministic in size and offloads the full corresponding Merkle tree to clients. https://eprint.iacr.org/2020/352.pdf)
* This feels similar to a vector commitment accumulator, where the numbers being committed to are in a given order, but I think committing to a set is simpler than committing to a vector.
* I *think* that this is the same problem as labeling a tree that looks like the following:

```
       A -> B -> C -> D -> E
                  \
                   -> F -> G
                       \
                        -> H

```

Given any two labels (L1, L2), and *only* two labels, determine if L1 is an ancestor of L2. There are labeling schemes that allow for this determination in constant time in significantly less than N bits per label, but I am not sure that it perfectly maps to this.

# Answer
> 1 votes
The easiest and secure method of doing this is making a token an (id, signature) pair where you randomly generate a fixed-size id (e.g. 128-bits) using a method that avoids collisions (a hash of a counter plus timestamp plus system RNG works in almost every scenario). The signature could then be something as simple as hashing the concatenation of the id with some secret stored on the server.

To verify a token simply concatenate the id with your secret, hash it, and check whether it equals the signature. Unless the hash function is insecure or someone knows the secret on your server they not fake a token.

---
Tags: sets, hash, dag, bloom-filters, blockchain
---


# Question
Title: How to represent a recurrence that increments by one at each tree level?
I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows:

$$O(\sum\_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$

I am trying to find the recurrence. Since this is like merge sort we can start with the classic 2T(n/2). However, I am unsure how to write what comes after 2T(n/2) in the recurrence below: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ **i++ each recurrence**

I am aware that this is exponential time. My assumption is that this all simplifies to O(2^n). Is that assumption correct?

Bogo Sort + Merge Sort Example

# Answer
> 1 votes
As each time $n$ is divided by $2$ and $2$ multiplied by 2, it should be: $$ T(n) = 2T(\frac{n}{2}) + 2^n $$ Now, if you expand it:

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

How can we guess $T(\frac{n}{2})$? Because $i$ is changing from $0$ to $\log{n}$. If we suppose $T(0)$, when $i = 0$, it will be the not recurrent part of the equation. Hence, we found that it is $2^n$. How did we find we should multiply by $2$? Because each time the relation is multiplied by $2$ and we have a power of it in each iteration. Hence, it should be multiplied by the recurrent part of the relation, which is $T(\frac{n}{2})$ here.

Eventually, form the mater theorem, we can conclude that $T(n) = \Theta(2^n)$.

---
Tags: runtime-analysis, sorting, recurrence-relation, divide-and-conquer
---