title: Solving two party problem

text:
# Question
Title: Solving two party problem
There are two parties A and B going on. Some people are going to party A, some are going to party B.

We are given instructions of the form

* `different 1 3`, meaning that person 1 and person 3 are attending different parties
* `same 3 4`,
* `different 4 5`,

and then given a command `tell 1 4` we have to answer if they are attending the same party or a different.

Like from above we can conclude that 1 and 4 must be attending different party as 1 and 3 are attending different and 3 and 4 attend the same.

---

**My thoughts :** Make a hash table for A and B given x and y determine which one belongs to which hashtable if any not present put it in the appropriate hashtable.

Not sure if this is an efficient algorithm for this.

I was wondering if we could build a graph from the given info and then we can answer any amount of questions like that.

# Answer
It will be difficult with your idea as you don't initially know which table to put a person in. For example will `different 1 2` and `different 3 4` have two solutions, namely $A = \\{1, 3\\}$ and $B = \\{2, 4\\}$, and also $A = \\{1, 4\\}$ and $B = \\{2, 3\\}$ (and symmetrically). When you get the information that `different 2 3`, you have now lost some crucial information that you need.

The answer is graphs.

A graph is bipartite if and only if it is two-colorable (if and only if it has no odd cycles).

You are creating a bipartite graph such that when there is an edge between two people then *they attend different parties*.

When the graph is connected, it is easy to say whether two people are in the same party or not: Given $u$ and $v$, if the shortest path from $u$ to $v$ has an even number of edges, they are in the same party, if it has an odd number of edges, they are in different parties.

The command `different u v` simply adds the edge between $u$ and $v$.

However, the command `same u v` is slightly worse since you need to record the fact that they *don't* have an edge.

I would do the following.

1. If $u$ or $v$ have neighbors, add edges from $u$ to $N(v)$ and/or $v$ to $N(u)$. One is enough, but you can also make it complete. This is a space/time tradeoff.
2. If neither $u$ nor $v$ have neighbors, construct an artifical vertex $x\_{uv}$ and connect both $v$ and $u$ to $x\_{uv}$. If $u$ or $v$ later get a *different* command, say `different v w`, you can remove $x\_{uv}$, or *identify* $x\_{uv}$ and $w$ (merge the vertices and their neighborhoods).

---

Complexity:

* `different a b`$O(1)$. Add edge in constant time. Check if $a$ or $b$ has an $x$-neighbor takes $O(1)$ time, delete that vertex takes time $O(1)$. Add at most two edges after $x$ deleted.
* `same a b`$O(1)$. Check existence of neighborhood, if so, add two edges in constant time. Otherwise, create $x$ vertex and add two edges in constant time.
* `tell a b`$O(n + m) = O(m)$ with a single BFS search. When you get the path $P$ you can add edge from $P\_i$ to $P\_{i+2}$ for all $i$; that could lower the future searching time.
> 2 votes

---
Tags: algorithms, graphs
---


title: Expected running time of an algorithm

text:
# Question
Title: Expected running time of an algorithm
This demonstrates the limitations of considering expected running time of an algorithm as a useful measure. For any $n\>0$, describe a function $f:\\{0,1\\}^n \to \mathbb{N}$ such that

* $\mathbb{E}\[f\] = \mathbb{E}\_{x\in \\{0,1\\}^n}\[f(x)\] = n^c$ for some constant $c$ and
* ${\sf var}\[f\] = E\[f^2\] - (E\[f\])^2 = \Omega(2^n)$.

I.e., there can be performance measures $f$ which is polynomial in expectation, but variance being exponential. Give formal justification for your answer (i.e., computation of expectation and variance for the function $f$ constructed).

I'm not able to approach the problem. I guess some hint would suffice.

# Answer
> 4 votes
There is a solution with $c = 0$: what would happen if $f(x) = 1$ for every value $x$ of $\\{0,1\\}^n$ but one $\tilde{x}$, for which $f(\tilde{x})$ is very big?

---
Tags: algorithms
---


# Question
Title: How does size of list in merge-sort, quick-sort, insertion-sort, matter?
We have been taught that:

> **Insertion-sort** will best work if we have a **small** list.
>
> **Quick-sort** will best work if we have a **long** list.
>
> **Merge-sort** will best work if we have a **huge** list.

It is not intuitively understandable.

However, let us say if we have `a list with 20 elements` and want to `sort` it because `shift`ing action `does cost a lot for us`, that would be a perfect choice to go with `Insertion-sort`.

I do not know If I am getting the idea right or not, but my issue is that I can not correlate the logic behind these sorting algorithms with the size of lists, Also does worst, average and best cases affect the size list.

getting me out of confusion would be really much appreciated, thanks.

# Answer
I'm by no means an expert, but these points are more-or-less right, however, we often use merge-sort if we suspect the array to be near (reversely) sorted.

Insertion sort is used in tiny lists (e.g. Java defines tiny to be less than 47), due to the fact that we have much less overhead in insertion sort than in merge sort and quicksort. As you may know, $O$ notation hides constants, and for two algorithms running in times $O(n^2)$ and $O(n \log n)$ respectively, the running time of the first algorithm can be smaller for small $n$.

As with quicksort, merge sort is easy to do *inplace*, meaning that we don't need much extra memory. However, merge sort is guaranteed to take $O(n \log n)$ whereas for subsequences of an array with a lot of structure, quicksort can take $O( n^2)$.

So, I would add one thing to your list, namely that if a list is almost reversely sorted, we prefer merge sort over quicksort.

Ps, there's a lot to learn from open source software, you can read Java's sort methods in their `DualPivotQuicksort.java`.
> 3 votes

# Answer
It's unclear to me why you put the algorithms in that order. Also, "best work" is quite informal. There are many ways to compare sorting algorithm (worst-case time, expected-time, space complexity, etc). Some considerations that might help you are below.

I can see how InsertionSort could be faster than MergeSort of QuickSort in practice for small lists.

The worst-case complexity of InsertionSort can be upper bounded by $c n^2$ for some constant $c$, while the worst-case (resp. expected) complexity of quicksort can be lower bounded by $c' n \log n$ for some $c'$. It might very well be that the multiplicative constant $c'$ is large enough to satisfy $c n^2 \< c' n\log n$ for small $n$.

For huge lists, a "standard" implementation of merge sort requires $O(n)$ auxiliary space, while quick-sort can be run in place. They both have the same asymptotic expected running time, so if that's how you are comparing your algorithms, QuickSort might be preferred.

If you're comparing the algorithms by their worst case running time then it might be the case (I didn't estimate the actual constant, which depends on the specific implementation anyway) that QuickSort runs in time $\approx c\_q n^2$ while MergeSort runs in time $\approx c\_m n \log n$. In this case MergeSort is clearly preferred for large enough list but, if $c\_q \ll c\_m$, QuickSort would be preferred for moderately-sized lists.

Notice that, in practice, you can just use QuickSort (since the extra overhead spent for small lists in negligible, in the absolute sense). Fancy implementations (such as the ones often found in standard libraries) use hybrid algorithms: they run QuickSort and if they realize that the size of the subproblems is somehow not shrinking fast enough, they revert to MergeSort. Whenever the number of elements left to sort is small, they switch to a quadratic-time sorting algorithm like InsertionSort.
> 2 votes

---
Tags: algorithms, runtime-analysis, sorting, quicksort, mergesort
---


# Question
Title: Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)
I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used to enumerate all $n \choose 2$ ways to choose $2$ values from a total of $\left|V\right|$ possible values.

For example:

Here, $V = \left\\{ 0, 1, 2, 3, 4, 5, 6 \right\\}$ and $E = \left\\{ (0,1),(0,2),\cdots,(5,6) \right\\}$ and creating the initial graph is of the order $O(n^2)$. $E$ readily contains all possible pairs of numbers chosen from the list.

I was wondering if the same strategy could be used to enumerate any $n \choose k$ where $0 \leq k \leq n$, or if there are more efficient algorithms for this purpose.

# Answer
To generalize your approach to $k$-subsets of an $n$-set, you would need to build a hypergraph. Ordinary graph edges are relations between *pairs* of vertices. Hypergraphs allow relations between arbitrary sets of vertices. They are *extremely* general objects, essentially representing families of sets.

This question provides two good answers for how to (reasonably) efficiently enumerate these subsets. The first uses bit magic and is a special case when $n$ is small enough. The second takes a recursive approach which saves having to compute the first $k-1$ elements of a $k$ subset multiple times, but only really helps if enumerating over several consecutive values of $k$.
> 2 votes

---
Tags: algorithms, graphs, combinatorics
---


# Question
Title: Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?
Show if $L = \\{a^mb^nc^n \mid m,n \geq 0\\} \cup \\{b,c\\}^\*$ is regular or not.

My attempt:

I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of regular languages is regular".

Assuming $L$ is regular. I already know that $S=\\{ab^\* c^\*\\}$ is regular. I'll now look at the intersection $L \cap S$.

$$(\\{a^mb^nc^n \mid m,n \geq 0\\}\cap \\{ab^\* c^\*\\}) \cup (\\{b,c\\}^\*\cap \\{ab^\* c^\*\\})$$ $$\\{ab^nc^n \mid n \geq 0\\} \cup \emptyset = \\{ab^nc^n \mid n \geq 0\\}$$

Which is not regular according to Pumping lemma. Is this idea correct?

# Answer
> 0 votes
Pumping lemma works easily. Somewhere it says "if the language is regular then for every string in the language..." Just check the pumping lemma for strings that start with exactly one a.

# Answer
> 0 votes
There are stronger versions of the pumping lemma that do apply directly to your language. For example, Wikipedia describes the following pumping lemma:

> If $L$ is regular then there is a constant $p$ such that any word $uwv \in L$, where $|w| \geq p$, can be decomposed as $uxyzv$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $uxy^tzv \in L$ for all $t \geq 0$.

Using this, let us prove that your language is not regular. Let $p$ be the constant promised by the lemma. Take the word $ab^pc^p$, where $u = a$, $w = b^p$, $v = c^p$. According to the lemma, we can decompose $w = xyz$ in such a way that $y \neq \epsilon$ and $uxy^tzv \in L$ for all $t \geq 0$. However, if $y = b^q$ then $uxy^0zv = ab^{p-q}c^p \notin L$, since $q \neq \epsilon$.

There should be an even stronger pumping lemma along the lines of Ogden's lemma, which is a strong analog of the pumping lemma for context-free languages. You can formulate and prove it, if you wish.

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


# Question
Title: Is the base of natural logarithms $e$ efficiently computable?
Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a polynomial time algorithm that takes a positive integer $C$ as input and outputs a rational number $y$ such that $r−\frac{1}{C}\leq y \leq r+\frac{1}{C}$.

If it is computable, what would the high-level algorithm be? Or how do we argue that it is not computable?

# Answer
> 1 votes
It is not hard to check (for example using a Taylor expansion of $e^x$ at $x=0$) that for all $n \geq 0$, $$ \sum\_{k=0}^n \frac{1}{k!} \< e \< \sum\_{k=0}^n \frac{1}{k!} + \frac{e}{(n+1)!} \< \sum\_{k=0}^n \frac{1}{k!} + \frac{3}{(n+1)!}. $$ Moreover, $$ \sum\_{k=0}^n \frac{1}{k!} = \frac{\sum\_{k=0}^n \prod\_{i=k+1}^n i}{n!}. $$ This formula gives an algorithm, running in time $\mathit{poly}(n)$, for computing $\sum\_{k=0}^n \frac{1}{k!}$. This quantity satisfies your requirements if $\frac{3}{(n+1)!} \leq \frac{1}{C}$, that is, if $(n+1)! \geq 3C$. Since $(n+1)! \geq 2^n$, it suffices to choose $n = O(\log C)$. This gives an algorithm running in time $\mathit{poly}(\log C)$. Since the length of the encoding of $C$ is $\Theta(\log C)$, the resulting algorithm runs in polynomial time.

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


# Question
Title: Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o
New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.

If you have a given an array such as `A[1...n]` of numeric values (can be positive, zero, and negative) how may you determine the `subarray A[i...j] (1≤ i ≤ j ≤ n)` where the sum of elements is maximum overall (subvectors). Regarding the brute force algorithm below, how do you go about analyzing its best case, worst case, and average-case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. How would you even show steps? Without building out the algorithm?

Thanks in advance.

```
// PSEUDOCODE
// BRUTE-FORCE-FIND-MAXIMUM-SUBARRAY(A)
n = A.length
max-sum = -∞
for l = 1 to n
    sum = 0
    for h = l to n
        sum = sum + A[h]
        if sum > max-sum
            max-sum = sum
            low = l
            high = h
return (low, high) # No, return of MAX-HIGH

```

Note: New to the forum, not sure if this is the correct exchange. But I am referring to and referencing problems from https://walkccc.me/CLRS/Chap04/4.1/.

# Answer
Your algorithm goes over all pairs $(\ell,h)$ of indices such that $1 \leq \ell \leq h \leq n$, and for each of them, runs $\Theta(1)$ operations (the rest of the steps are insignificant from an asymptotic point of view). If there are $M$ such pairs, then the best case, worst case, average case complexity are all equal to $\Theta(M)$.
> 1 votes

---
Tags: algorithms, polynomial-time, big-o-notation, notation
---


# Question
Title: Solving constants in the recursive term with master theorem
We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the problems were in the form of $aT(\frac{n}{b}) + f(n)$ where applying the Master Theorem is no sweat, but we're given this recurrence relation wherein there is a constant inside the recursive term, I am not sure anymore if Master Theorem would still work, or is there another way?

\begin{align\*} T(n) = 3T\left(\frac{n}{3}-2\right) + \frac{n}{2} \end{align\*}

This one has a constant 2 inside the term, and I don't know how to show that this recurrence relation is upper bounded by $ O (n \log n) $.

# Answer
If you are just interested in an upper bound you can notice that $T(n) \le S(n)$ where $S(n) = 3 S(n/3) + \frac{n}{2}$ and has solution $S(n) = O(n \log n)$.

Alternatively there is always induction. You can show that, for $n \ge 2$, $T(n) \le c n \log n$.

For $2 \le n \< 7$, $T(n)$ is a constant and $n \log n \ge 1$. Therefore the claim is true for a sufficiently large (constant) value $c^\*$ of $c$.

For $n \ge 7$ you have: $$ T(n) = 3T\left(\frac{n}{3} - 2\right) + \frac{n}{2} \le 3 c \frac{n}{3} \log \frac{n}{3} + \frac{n}{2} = cn \log n - cn \log 3 + \frac{n}{2}, $$

which is at most $cn \log n$ when $c n \log 3 \ge \frac{n}{2}$ or, equivalently, $c \ge \frac{1}{2 \log 3}$.

Simply pick $c = \max\\{c^\*, \frac{1}{2 \log 3} \\}$.
> 2 votes

# Answer
Akra and Bazzi proved a generalization of the master theorem which, in particular, implies that the formulas in the master theorem remain true even if you're adding some "noise" of the form you consider. In fact, the Akra–Bazzi theorem can handle noise of magnitude $O\bigl(\frac{n}{\log^2 n}\bigr)$.
> 1 votes

---
Tags: asymptotics, recurrence-relation, big-o-notation, master-theorem
---


title: What edges are not in any MST?

text:
# Question
Title: What edges are not in any MST?
This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.

# Answer
> 6 votes
A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, here is my solution to the question.

Let $G$ be a weighted undirected (finite) graph. An edge $e$ is called superheavy if it is the unique heaviest edge in some cycle. Here is a characterization of the edges that are not in any MST.

## An edge is not in any MST if and only if it is a superheavy edge

The well-known "if" part, a superheavy edge is not in any MST, is proved in the cycle property of MST.

The "only if" part, any edge $e$ that is not superheavy is in some MST, is harder to prove. Let me introduce an algorithm and a lemma first.

**The delete-heaviest-edge algorithm (DHE) on $G$ removes a heaviest edge in any cycle until no cycle remains.** Just to be extra clear, there might be multiple heaviest edges in one cycle. The edge removed can be chosen to be any one of them.

Lemma: **DHE is an MST algorithm.** That is, the final graph at the end of DHE is an MST of the original $G$.

One proof of the lemma can be developed by adapting the proof at reverse-delete algorithm.

For another proof of the lemma, reader can check my post at the delete-heaviest-edge algorithm on graphs with edges of distinct weights, where I proved the special case where all weights are distinct. For the general case of a given run of DHE where all weights of $G$ are not necessarily distinct, we can perturb the weights of all edges of $G$ so that all weights are distinct and that each edge removed is the unique heaviest edge in the corresponding cycle. We can then repeat the given run of DHE on the perturbed $G$, resulting in the same spanning tree, which is also the MST of the perturbed $G$, since this is the proven special case of distinct weights. By making the perturbation arbitrarily small, we can see the total weight of the resulting MST can be arbitrarily near to the weight of a (or any) MST of the original $G$. Once we take the limit of perturbation going to $0$, we can see that original given run of the DHE must produce a spanning tree with the minimal weight. The lemma is proved.

Now let us prove the "only if" part. Suppose edge $e$ is not a superheavy edge. Let us start a particular run of DHE. We will adjust that run whenever necessary to avoid deleting $e$. Suppose $e$, as a heaviest edge in some cycle is removed in some step. Because $e$ is not superheavy, there is another heaviest edge, say $f$, in that cycle. Let us modify that step so that it removes $f$ instead of $e$. Continue to run the algorithm, alway avoiding removing $e$ as we just did. At the end of the algorithm, we must arrive at an MST thanks to the lemma, which contains $e$. Proof of the "only if" part is done.

Since an edge not in any MST means it is superheavy, any algorithm that finds all the superheavy edges will also finds all edges that are not in any MST.

## Algorithms to find all superheavy edges

Here is a naive algorithm. Iterate over all edges. For each edge $e$, pick arbitrarily one of its two vertices. Starting from this chosen vertex, make a DFS or BFS along edges with weight lower than that of $e$, checking whether we have reached the other vertex of $e$ all along. Once we have, $e$ is superheavy. Otherwise we cannot at the end of the search, implying $e$ is not superheavy.

---

It often happens that there is a unique MST, for example when all edge-weights are distinct. We can use various algorithms such as Kruskal's algorithm or Prim's algorithm to compute that unique MST. The superheavy edges are the edges that are not in that unique MST.

---

Here is the efficient algorithm to find all superheavy edges in general cases. Its time-complexity is about the time-complexity to sort the edges by weights, or $O(m\log m + n)$, where $n$ is the number of vertices and $m$ is the number of edges. Its space-complexity is about $O(m+n)$.

1. Sort all edges in groups of increasing weights so that we have $$E=E\_1\cup E\_2\cup \cdots \cup E\_r$$ and $$w\_1\<w\_2\<\cdots\<w\_r,$$ where $E$ is the edge set of $G$ and every edge in $E\_i$ has weight $w\_i$.
2. Let $H$ be a graph that has the same vertices as $G$ but without any edges. Track the connected components of $H$ by a disjoint-set data structure.
3. For $i$ from 2 to $r$ do the following.
    1. Add all edges in $E\_{i-1}$ to $H$.
    2. For each edge in $E\_i$, check whether its endpoints are in the same connected component of $H$. If yes, it is a superheavy edge.

# Answer
> 2 votes
The harder part seems to be finding the superlight edges. Isura Manchanayake has provided a good implementation for determining other and superheavy edges. However, using the bridge processor which is effectively a depth first search to do an optimized strongly connected components algorithm, makes this $O(m^2+mn)$ considering a worst case where there are $m$ edge groups, adding one node each time since DFS is $m+n$. It might be constructive to also consider how to optimally discover the superlight edges.

Kruskal's algorithm of course generates an MST and superlight edges have to be any of the $n-1$ edges in such an MST. So we could determine superheavy, other edges and also potentially super light edges that are in the MST built during the pre-Kruskal step using the algorithm outlined in John L's answer. So we can first mark the superheavy nodes only.

Now we modify the Kruskal step. We mark the edges which are added to the tree as superlight even though this is potentially only, they may not be. When an edge $(u, v)$ is added which would merge the forest as $u$ and $v$ are in the same component but it was not superheavy, we know it induces a cycle with edges added in previous weights and some of the edges marked as superlight. So we do a BFS rooted at $u$, one of the ends of the cycle in the currently built MST which is $O(n)$ since there are at most $n-1$ edges. This finds the unique and of course shortest path to $v$. At the same time we keep another disjoint set forest for the superlight edges. Then we go through parents of $v$ unmarking $(v, p\[v\])$ as superlight (only if its in the list of newly added superlight edges, or alternatively has the same weight of the current edge set) and merging $(v, p\[v\])$ in the disjoint set forest for superlight nodes. After all edges are processed for this weight, we add all the superlight edges to the disjoint set forest in $O(n)$ time if they were not added during cycle detection. So we do at most $n-1$ BFS's and unmark at most $n-1$ nodes because the forest allows only this many merges.

Now we have achieved $O(n^2)$ time which is better than I can find any references for in any literature or questions or answers. Almost every algorithm or suggestion so far has involved $O(mn)$ or $O(m^2)$ or $O(m^2+mn)$. I am not sure the superlight edges can be deduced in better time, but its with certainty that $O(n^2 \log n)$ time should be a sufficient bound to classify all the edges as superheavy, superlight or otherwise. We also get a specific MST as output in addition to all of the classifications.

The worst case will occur on a complete graph with all equal weights. And such a case indeed benefits from using this algorithm. Of course all the edges are other edges, but we know that as the cycles are induced we will find many edges inducing cycles ($n(n-1)/2-n-1$ of them in fact), but only $n-1$ of them will cause processing. $n(n-1)/2$ is incidentally the number of paths in a tree or the MST connecting all the nodes. Which is a pretty decent hint that the cycle determination can be done from the perspective of the potentially superlight edges.

---
Tags: graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?
I'm following an online course which has the following (multiple-choice) quiz question:

> Which of the following statements cannot be true, given the current state of knowledge?
>
> 1. Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
> 2. There is an NP-complete problem that is polynomial-time solvable.
> 3. There is an NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.
> 4. There is no NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.

It seems to me that (1) and (2) are false since it has not been proven that any NP-complete problem is polynomial-time solvable. So I'm vacillating between (3) and (4).

In particular, I'm a bit nonplussed where the $O(n^{\log n})$ comes from; I haven't seen this expression in any of the lecture notes. However, I do know about the traveling salesman problem which can be solved in $O(n^2 2^n)$ time using the Held-Karp algorithm. It would seem to me like this function grows less faster asymptotically than $O(n^{\log n})$, since it is usually the expression in the exponent that matters the most, in which case the answer would be (3).

Is this correct? Also, how would I show this formally?

# Answer
> 6 votes
The *Exponential Time Hypothesis* (ETH) states that SAT cannot be solved in time $2^{o(n)}$. Now suppose that $A$ is some NP-complete problem which can be solved in time $O(n^{\log n})$. Since $A$ is NP-hard, there is a polytime reduction from SAT to $A$, say running in time $O(n^k)$. Using this reduction, we can solve SAT in time $O(n^{k^2 \log n})$, contradicting ETH.

Since ETH is still standing, it is safe to assume that no $O(n^{\log n})$ algorithm is known for any NP-complete problem. We don't know for sure that (3) is true, i.e. we don't know for sure that (4) is false.

Conversely, we can't prove that no $O(n^{\log n})$ algorithm is known for any NP-complete problem. So we don't know for sure that (3) is false either.

# Answer
> 7 votes
The accepted answer is incorrect. I've taken the same course, and option 1 is correct. They didn't say why, but I have the following argument.

Quoting Wikipedia:

> **polynomial time**: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $ T(n) = O(n^k) $ for some positive constant $ k $.
>
> **exponential time**: An algorithm is said to be exponential time, if $ T(n) $ is upper bounded by $ 2^{poly(n)} $, where $ poly(n) $ is some polynomial in $ n $. More formally, an algorithm is exponential time if $ T(n) $ is bounded by $ O(2^{n^k}) $ for some constant $ k $.

We don't know $ P \neq NP $, so option 2 can't be ruled out.

For all we know, the running time required to solve NP-complete problems could be anywhere between polynomial and exponential (note that $ n^{\log n} $ is more than polynomial but less than exponential). Thus, options 3 and 4 can't be ruled out.

That only leaves option 1. The claim in option 1 is incorrect because if there's a polynomial-time algorithm for any NP-complete problem X, then every other NP problem has a polynomial-time algorithm by reduction to X.

# Answer
> 0 votes
If you take a look at Wikipedia, we find that there is not a clear consensus on what NP-complete actually is. Namely if we define it with what was on Wikipedia for a long time until it was edited out just recently:

> A deterministic Turing machine can solve it in large time complexity classes (e.g., EXPTIME, as is the case with brute force search algorithms) and can verify its solutions in polynomial time.

If we assume this definition of NP-complete, then 3 is by definition True and 4 by definition False.

This means that if P=NP then NP-complete is a meaningless definition where no problems actually belong to it.

Hence the definition has been debated as it would seem to collapse down to P-complete in case P=NP if we remove the exponential time hypothesis from the definition.

Since the question asked regarding the current state of knowledge 3 is True and 4 is False as well if we go by the other definition of NP complete.

As for 1 and 2 they are also false in the current state of knowledge.

If it was asked for 1 whether some specific instances of NP-complete problems are solvable in polynomial time, the this is true. There are many cases in fact, where a specific problem instance of SAT for example, turns out to be 2-SAT, or finding the Hamiltonian path in a graph with only n edges, etc. Practical solvers make use of knowledge of specific instances where the NP-complete brute force strategy need not be deployed.

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


# Question
Title: Show that LOOP is reducible to Complement of Halting problem
LOOP = {\<M,w1,w2,w3\>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {\<M,w\> : M is a Turing machine that doesn't halt on w}

Show that LOOP is polynomial time Turing reducible to HPC
I am not sure how to begin solving this kind of problem. Also the question I am trying to solve brings up the definition of A is polynomial reducible
to B if there is a B-oracle poly time Turing M such that M(x) accepts x iff x is in A.

Any hints or pointers on this ?

**My thoughts :**
What I understand by reducibility here is that If I have a Turing machine for HPC
Then I can use this turing machine to determine if \<M,w1,w2,w3\> is in LOOP
And same the other way If I have a turing machine for LOOP then I can use it
as a determiner for HPC. Is this a correct way to think about it?
This way it becomes simple and probably easier to prove. But not sure if it
is same as the question that is being asked

# Answer
> 1 votes
The question is given you have an oracle machine/black box for HPC can you decide if \<M,w1,w2,w3\> is in LOOP.

See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction\_(recursion\_theory)#Turing\_reducibility

The proof is very straightforward as you already know.

---
Tags: turing-machines, oracle-machines, polynomial-time-reductions
---


# Question
Title: TM with double-infinity tape semi-decides the same languages as classical TM
> Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the head's on the first letter of the entry-word

Under "classical" TM we understand a TM that has a tape that starts at the first letter and is infinite at the right side.

I don't quite understand what to prove here. The only difference between the two TM's is that I can/can't hit the left border of the tape. I could make this scenario a rejected state in the double infinite TM because it can't happen on the single infinite TM.

Any tips?

# Answer
> 2 votes
The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for *any* unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left" on the unbounded-tape TM, because our proof has to be applicable to *all* unbounded-tape TMs, not just ones that conveniently do this.

Understanding the equivalence of these two definitions of TM is important because both definitions are widely used in the academia, and many proofs using TMs are easier on one of these models over the other. Knowing that they are equivalent allows one to pick the easier model for a given situation.

For a basic idea of how to prove these two models of computation equivalent, consider that shifting the entire contents of the tape to the right can be done by a classical TM, allowing it to dynamically claim more space on the left of existing tape contents as needed. You can utilize this behavior to simulate an unbounded-tape TM in a classical TM.

---
Tags: turing-machines, semi-decidability
---


title: Finite automata start state

text:
# Question
Title: Finite automata start state
Can a finite automata not have a start state?

I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.

# Answer
It depends on the definition. Some definitions of a deterministic finite automaton (DFA) are a quadruplet $(Q, \delta, q\_0, F)$ where $Q$ is the set of states and $q\_0 \in Q$ is the initial state. Therefore, it must be defined.

However, the definition of non-deterministic finite automaton (NFA) is sometimes seen as a quadruplet $(Q, \Delta, I, F)$ where $Q$ is the set of states and $I\subset Q$ is the set of initial states. Here, you can chose $I = \emptyset$ and get an automaton without initial state.

Since a DFA can be seen as a special case of a NFA, it is not necessary for an automaton to have an initial state. In both cases (DFA and NFA), the language recognized by an automaton without initial state is $\emptyset$.
> 3 votes

---
Tags: algorithm-analysis
---


# Question
Title: In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?
I was going through the text *Compilers: Principles,Techniques and Tools* by *Ullman et. al.* where I came across the claim in the question by authors. Below is the definition and following it is the claim by the authors.

---

> **Form of a Syntax-Directed Definition**
>
> In a syntax-directed definition, each grammar production $A\rightarrow \alpha$ has associated with it a set of semantic rules of the form $b := f(c\_1, c\_2, . . . , c\_k)$ where $f$ is a function, and either
>
> 1. $b$ is a synthesized attribute of $A$ and $c\_1, c\_2, . . . , c\_k$ are attributes belonging to the grammar symbols of the production, or
> 2. $b$ is an inherited attribute of one of the grammar symbols on the right side of the production, and $c\_1, c\_2, ... , c\_k$ are attributes belonging to the grammar symbols of the production.

---

> **Claim:**
>
> ***In a syntax-directed definition, terminals are assumed to have synthesized attributes only, as the definition does not provide any semantic rules for terminals***. Values for attributes of terminals are usually supplied by the lexical analyzer.

That values of the terminals is provided by the lexical analyzer is a usual practice.(Which makes us assume that terminals have synthesized attributes usually). But cannot understand their claim, with the logic that the definition does not allow it. Going by point $2$ in the definition:

*$b$ is an inherited attribute of one of the grammar symbols on the right side of the production*: so the right hand side of a production might as well contain terminals, making $b$ an inherited attribute of a terminal.

The point $1$ applied to $b$ which is an attribute of a symbol(non terminal) on the LHS and only point $1$ talks about synthesized attributes, so $1$ makes no provisions for attributes for the non terminals. Hence there is no provision of synthesized attributes for the terminals.

Is this something like this?

# Answer
It's not a claim; it's a definition. In mathematics, we can define things however we want.  \[See Note 1\]

Our only obligation is to make sure we've shared the definition with our readers.

In any event, it doesn't make the slightest difference. If we want to define an inherited attribute for a terminal, we can just replace the terminal throughout the grammar with a non-terminal with a single production whose right-hand side consists only of the terminal. Then the surrogate non-terminal can carry whatever attributes we want it to carry.

This transformation does not in any way affect the parse (provided it is done consistently throughout the grammar).

---

### Notes

1. It's not a coincidence that Lewis Carroll was a mathematics professor.
> 1 votes

---
Tags: compilers, parsers, attribute-grammars
---


# Question
Title: How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$
Below is an excerpt from the Red Dragon book.

> $$(1) \quad S \rightarrow A\_1 \quad A\_2 \quad\\{ A\_1.in : = 1;\quad A\_2.in : = 2 ;\\}$$ $$(2) \quad A \rightarrow a \quad \\{ print(A.in) \\}$$
>
> We find that the inherited attribute $A.in$ in the second production is not defined when an attempt is made to print its value during a depth-first traversal of the parse tree for the input string $aa$.

Now the authors define inherited attributes as: An inherited attribute is one whose value at a node in a parse tree is defined in terms of attributes at ***the parent and/or siblings of that node***.

But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent or siblings. But rather it is sort of based on itself.

# Answer
> But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent of siblings.

Yes, it is. The parent of $A\to a$ is $S \to A\_1 A\_2$. $S$ has two children, both of which are instances of $A$. And the rule for $S \to A\_1 A\_2$ assigns values to the inherited attributes of both children.

That's precisely what an inherited attribute is. Inherited attributes (which are inherited from the parents in the parse tree) can be used in the synthesized rules for those non-terminals, which is what is happening in the rule for $A$.
> 1 votes

---
Tags: compilers, parsers, attribute-grammars
---


# Question
Title: L-attributed definitions include all syntax-directed definitions based on LL(1) grammars
I was going through the text *Compilers: Principles, Techniques and Tools* by *Ullman et. al* where I came across the following claim:

> ***L-attributed definitions include all syntax-directed definitions based on LL(1) grammars.***

What is the intuition or logic behind this statement?

In the later sections they show that L attributed grammars can be easily implemented by a DFS search algorithm of the parse tree (and hence easily by a predictive parser \[recursive/non recursive\]). $^\dagger$

Is it so that since LL(1) grammars can also be parsed by predictive parser and by the logic of $\dagger$, the authors make the claim?

# Answer
L-attributed definitions are definition whose attributes can be evaluated in depth-first order (as they say in the first sentence).

The statement "L-attributed definitions *include* all syntax-directed definitions based on LL(1) grammars" is perhaps a bit subtle. It's not saying that the two sets of definitions are the same; rather, that syntax-directed definitions "based on LL(1) grammars" are a subset of L-attributed definitions.

That's true because the predictive parser based on the LL(1) grammar visits the parse tree in strictly depth-first order. This was already noted in *Designing a Predictive Parser* in Section 2.4 of the text book, which goes on to build a recursive-descent parser illustrating how this works.
> 1 votes

---
Tags: compilers, parsers, attribute-grammars
---


title: Shared Elements Algorithm

text:
# Question
Title: Shared Elements Algorithm
I have a problem that I am working on an algorithm for:
I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$S=\\{A\_1,A\_2,A\_3,...,A\_k\\}$ where $\forall A\_i\in S,\ A\_i=\\{a\_{i1},a\_{i2},a\_{i3},...,a\_{in\_i}\\},\ a\_{ik}\in \mathbb{Z}^+, a\_{ip}=a\_{iq}\iff\ p=q$
(so $n\_i$ would be the amount of numbers in each set)

The algorithm should find 5 sets in $S$ I will call $B\_1,B\_2,B\_3,B\_4,B\_5$ where the following pairs of sets share an element:
$B\_1,B\_2$
$B\_1,B\_3$
$B\_1,B\_4$
$B\_1,B\_5$
$B\_2,B\_3$
$B\_3,B\_4$
$B\_4,B\_5$
$B\_5,B\_2$
where the element each of these pairs share is distinct

So if $A\_2=\\{4,5,7,37\\},\ A\_5=\\{8,11,37\\},\ A\_7=\\{4,11,21\\},\ A\_{12}=\\{7,21,131\\},\ A\_{19}=\\{5,8,131\\}$
Then those 5 sets would be a potential output of the algorithm.

The way I would do it currently would seem very inefficient which would be to iterate through the sets of $S$. I would take $A\_1$ and find all the sets in S that share an element with it. I would take one of those sets, $A\_m$, find the sets that share an element with it that isn't that element that $A\_1$ and $A\_m$ shared. And continue that until I found 5 sets that worked.

There must be a more efficient solution but I am unaware of this type of problem and googling didn't help much. So if anyone knows a good way to do this or can point me in the right direction with analogous problems or topics I should learn about that would be very appreciated.

# Answer
> 2 votes
Construct an undirected graph with $k$ vertices, where each vertex represents a set $A\_i$, and you draw an edge between two vertices if their sets share an element. Now you have an instance of subgraph isomorphism: you have a graph $H$ on five vertices (of the shape shown in your question), and you want to enumerate all subgraphs of $G$ that are isomorphic to $G$. You do have an additional distinctness condition, but if you can enumerate all isomorphic subgraphs, you can check whether they satisfy that additional condition in post-processing (and in most cases I expect they typically will).

This subgraph isomorphism problem looks challenging. A naive approach has $O(k^5)$ running time: enumerate all 5-tuples of vertices. You can improve this slightly, to $O(k^2m^{1.5})$ time, where $m$ counts the number of edges in the graph (note that $m\le k^2$, and might be much smaller, so this might be better). First, enumerate all 3-cliques (triangles). This can be done in $O(m^{1.5})$ time (see http://complexnetworks.fr/wp-content/uploads/2011/01/triangles.pdf and https://users.soe.ucsc.edu/~sesh/pubs/conf-triangle-enum.pdf). These will be your candidates for $A\_1,A\_2,A\_3$. Next, enumerate all possible candidates for $A\_4,A\_5$ and check to see if they meet the requirements. This might not be much faster, but maybe it would help a little bit.

---
Tags: algorithms, graphs, sets
---


# Question
Title: Can finding a witness be NP-hard even if we already know there is one?
The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand.

Suppose that we have a problem in which the we know the answer is yes, furthermore we can verify a witness in polynomial time.

Can we then always find a witness in polynomial time? Or can this "search problem" be NP-hard?

# Answer
TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.

There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:

Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L

and the references \[6\] and \[11\] within. PDF available here.
> 6 votes

# Answer
No, you can't always find a solution in polynomial time, even if you know there is a solution.

According to Khanna, Linial, and Safra \[1\] (see the 3rd paragraph), it follows already from the classic 1972 work by Karp that that coloring a 3-colorable graph with 3 colors is NP-hard. (Their work extends this to show that 4-coloring 3-colorable graphs is still NP-hard).

Note that this does not contradict the answer by Rahul Savani. This is because for all binary relations $P$ in FNP, we must be able to verify in polynomial time if $P(x,y)$ is in the relation. Given that deciding if a 3-colorable graph with 3 colors is NP-complete, it is unlikely the problem of finding a 4-coloring in a 3-colorable graph is in FNP since we cannot verify the validity of the input $x$ in polynomial time. Thus, there is no contradiction to the Megiddo-Papadimitriou result.

---

\[1\] Khanna, Sanjeev, Nathan Linial, and Shmuel Safra. "On the hardness of approximating the chromatic number." Theory and Computing Systems, 1993., Proceedings of the 2nd Israel Symposium on the. IEEE, 1993.
> 3 votes

# Answer
If an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then $\\: NP = coNP \\;$.
Proof:
If an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then:

Let $R$ be such a hard relation, and let $M'$ be a yes-answer-only co-nondeterministic polynomial-time Turing reduction from $SAT$ to $R$. $\\:$ Let $M$ be the coNP algorithm given by:
$\\;$ Attempt to parse the alleged anti-certificate into an inner certificate and responses.
$\\;$ If that fails then output YES, else attempt to run $M'$ on the inner anti-certificate by giving
$\\;$ the same response as was given before for repeat-queries and using the responses from
$\\;$ the (outer) anti-certificate for all other oracle queries. $\\:$ If $M'$ would make more distinct
$\\;$ queries than the number of responses or any of its queries would not be related by $R$ to
$\\;$ that query's response or $M'$ would output YES, the $M$ outputs YES, else $M$ outputs NO.
Since being an oracle for $R$ just imposes independent conditions on the oracle's responses
and $M'$ is a yes-answer-only reduction, the query-response pairs produced by $M'$
and a valid anti-certificate can always be extended to an oracle for $R$, so $M$ solves $SAT\hspace{-0.02 in}$.
Thus $\\: SAT\in coNP \\;$.
Since $SAT$ is $NP$-hard with respect to deterministic polynomial-time reductions, $\\: NP\subseteq coNP \\;$.
By symmetry, $\\: coNP \subseteq NP \\;$. $\\;\\;\\;\\;$ Thus $\\: NP = coNP \\;$.
Therefore, if an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then $\\: NP = coNP \\;$.
> 1 votes

# Answer
This depends slightly on the precise interpretation of your question, but I think your scenario can be generically described as a problem 'COMPUTE Y' where given some universally fixed polynomial time algorithm $T$ and polynomial $p$, on input $\langle x, 1^n \rangle$, output a string $y \in \\{0,1\\}^{p(n)}$, such that $T(x,y,1^n)$ outputs 1, and $y$ always exists for all possible $x$.

One question then might be whether a polynomial time algorithm for 'COMPUTE Y' implies $P = NP$

In this case, assume you can solve (say) 3SAT in polynomial time with a constant number of calls to an oracle that solves 'COMPUTE Y', i.e. some algorithm $A$ where $A(\phi) = 1$ iff $\phi$ is satisfiable, $A(\phi)=0$ otherwise. Flip the output bit to get $\bar{A}$, an algorithm where $\bar{A}(\phi) = 0$ iff $\phi$ is satisfiable and $\bar{A}(\phi) = 1$ if $\phi$ is unsatisfiable.

Convert this algorithm $\bar{A}$ (which uses an oracle for 'COMPUTE Y') into a nondeterministic algorithm (that uses no oracles) by simply replacing each oracle call with a nondeterministic guess of $y$ that you can check with a call to $T$. Now you have a nondeterministic algorithm which successfully decides unsatisfiable 3CNF instances, so $NP = coNP$

As an aside, if $NP = coNP$, that implies that all $NP$ complete problems (like $k$-clique or 3SAT) have slight variations whose decision problem is easy (always 'yes') yet whose search version is $NP$-hard
> 1 votes

# Answer
Here's a simple argument that the ability to find a witness in polynomial time would imply P=NP:

1. Assume that we have a poly-time algorithm for finding a witness to any YES-instance of some NP-complete problem. Then there exist absolute constants $k$ and $c$ such that when run on a valid input of size $n$, the algorithm completes after at most $n^k + c$ steps and reports a valid witness. (Note that on an invalid input -- specifically, a NO-instance -- the algorithm's behaviour is undefined. It may detect a contradiction and abort, or produce an invalid witness, or even loop forever.)
2. Analyse the algorithm to derive concrete values for $k$ and $c$. (Loose upper bounds are fine.)
3. To solve an arbitrary instance of the problem in poly-time:
    1. *Guess* that the instance is a YES-instance, and run the poly-time witness-finding algorithm on it for at most $n^k+c+1$ steps.
    2. If the algorithm aborts early, or runs for $n^k+c+1$ steps, report "NO".
    3. Otherwise check the witness it produced. This can be done in poly-time. If the witness is valid, report "YES", otherwise report "NO".
> 1 votes

---
Tags: complexity-theory, np-hard, search-problem
---


# Question
Title: NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states
I'm trying to build a NFA for the following language $ L = \\{ \sigma\_1 \sigma\_2 \sigma \_3 \ldots \sigma \_n \mid \sigma \_1 \neq \sigma \_n \\}$. The catch is that for $ \Sigma $ such that $ |\Sigma|=2^k $, the NFA should have $\Theta(k)$ states.

I was thinking of representing the letters in binary but I'm not sure what I should do exactly.

# Answer
> 3 votes
The original question referred to DFA (and not NFAs). However, no DFA for $L$ with $O(k)$ states exists.

Consider $\Sigma$ as a set of words (i.e., each word consists of a single character from $\Sigma$). Given any two distinct words $a,b \in \Sigma$, the word $a$ is a distinguishing extension for $a$ and $b$. I.e., $aa \not\in L$ but $ba \in L$.

This shows that the number of equivalence classes of $L$ w.r.t. the equivalence relation "not having a distinguishing extension" is at least $|\Sigma|$. By the Myhill-Nerode theorem, any DFA for $L$ must have at least $|\Sigma|$ states.

---

The idea to build a NFA with $O(k)$ states is as follows: in addition to an initial state $s$, and to an accepting final state $t$ there are $2k$ states indexed with $1, \dots, 2k$.

Assign a distinct integer $x\_a$ from $0$ to $2^k-1$ to each character $a \in \Sigma$ and consider the binary string $b\_a$ of length $2k$ obtained by concatenating the binary string of length $k$ representing $x\_a$ in binary, with its complement.

For each character $a \in \Sigma$ let $S\_a$ be the set of all states $i$ such that the $i$-th least significant bit in $b\_a$ is $1$, and define $\overline{S}\_a = \\{1, \dots, 2k\\} \setminus S\_a$.

For each $a \in \Sigma$, add the following transitions:

* A transition from $s$ to each state $i \in S\_a$.
* A transition from each state $i \in \\{1, \dots, 2k\\}$ to itself.
* A transition from each state $i \in \overline{S}\_a$ to $t$.

Given a word $\sigma\_1, \sigma\_2, \dots, \sigma\_n$ with $\sigma\_1 \neq \sigma\_n$, let $i$ be an index such that the $i$-th least significant bit of $b\_{\sigma\_1}$ is $1$ while the $i$-th least significant bit of $b\_{\sigma\_n}$ is $0$ (such an index always exists). Then, $s \to i \to i \to \dots \to i \to t$ is an accepting path in the NFA.

Conversely, any accepting path is of the form $s \to i \to i \to \dots \to i \to t$ for some $i$. This implies that $i \in S\_{\sigma\_1} \cap S\_{\sigma\_n}$, i.e., $b\_{\sigma\_1}$ and $b\_{\sigma\_n}$ differ (at least) on the $i$-th least significant bit. This shows that $\sigma\_1 \neq \sigma\_n$.

The number of states of the NFA is $2k+2$.

Here is an example for $\Sigma = \\{x,y,z,w\\}$. All edges for which no label is shown are actually labelled with $x,y,z,w$.

---
Tags: finite-automata
---


# Question
Title: How to calculate the average depth of a binary tree?
My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach this problem?

# Answer
You haven't stated which distribution of random binary trees you are interested in, but in many cases the answer is indeed $\Theta(\sqrt{n})$. See for example Flajolet and Odlyzko, The average height of binary trees and other simple trees.
> 1 votes

---
Tags: trees, recurrence-relation
---


# Question
Title: Which goes first stl or data structures and algorithms?
So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions.

Is it possible to learn DSA without knowing STL? Which one is advisory to learn first(STL or DSA) so that it will be easy further?

Also suggest some good references for both stl and dsa.

# Answer
> 2 votes
I think STL (assuming you mean C++ standard template library) is something you sort of learn as you use it. Exposure to DSA (data structures and algorithms) is *essential* for solving new problems or progressing in CS. Since you are just starting out and partial to C++, any DSA textbook in C++ will be a good reference. Just try to Google search “Data Structures and Algorithms C++,” maybe with your preferred file type.

# Answer
> 2 votes
Data structures and algorithms existed before any particular implementation, and they continue to exist independently of any particular implementation, such as the C++ STL.

You can study data structures from several points of view:

* What are the main data structures, what are their properties, and in what circumstances each of them is typically used.
* How these data structures are implemented, and why they satisfy the stated properties.
* Limits on data structures.

As a user of data structures, you are mostly interested in the first point. Introductory courses on data structures typically contain a mix of the first two points, with perhaps a sprinkling of the third one (lower bound on comparison-based sorting).

As a programmer, you also need to be aware of software libraries implementing various data structures, but this should be easy to pick up if you understand the underlying data structures themselves.

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


title: Cormen problem 13-1 part d

text:
# Question
Title: Cormen problem 13-1 part d
I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:

```
PERSISTENT-TREE-INSERT(T,z)
y= T.nil
x=T.root
while x != T.nil
   y=x
   if z.key < x.key
       x = x.left
   else x = x.right
if y == T.nil
    T'.root = z
    return T'
else if z.key = y.key
    y'=copy(y)
    y'.left = z
    z.p = y'
else y'= copy(y)
     y'.right=z
     z.p = y'
x = y'
while x.p != T.nil
  if x.key < x.p.key
     x' = copy(x.p)
     x'.left = x
     x.p = x'
 else x' = copy(x.p)
    x'.right = x
    x.p = x'
T'.root = x
return T'

```

Now the copy procedure is :

```
copy(x)
 w.p = x.p
 w.right= x.right
 w.left = x.left
 w.key = x.key
 return w

```

Now this means that I only need to copy the node that is going to be the father of the key that I'm adding and its ancestors. The book however says that additional copying is needed just because we have a reference to the parent, but I don't see it. If someone could point me in the right direction I would be much grateful.

For reference this is the exercise:

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. We call such a set persistent. One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better. Consider a persistent set S with the operations INSERT, DELETE, and SEARCH, which we implement using binary search trees as shown in Figure 13.8(a). We maintain a separate root for every version of the set. In order to insert the key 5 into the set, we create a new node with key 5. This node becomes the left child of a new node with key 7, since we cannot modify the existing node with key 7. Similarly, the new node with key 7 becomes the left child of a new node with key 8 whose right child is the existing node with key 10. The new node with key 8 becomes, in turn, the right child of a new root r0 with key 4 whose left child is the existing node with key 3. We thus copy only part of the tree and share some of the nodes with the original tree, as shown in Figure 13.8(b).

d) Suppose that we had included the parent attribute in each node. In this case, PERSISTENT-TREE-INSERT would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT would then require .n/ time and space, where n is the number of nodes in the tree.

# Answer
> 1 votes
Alright, it was all in the diagram:

We need to copy the descendants of the nodes in the path to make sure we don't end up with a single node having two parents

---
Tags: algorithms, binary-search-trees, red-black-trees
---


# Question
Title: Cormen RB-DELETE_FIXUP(T,x) when x has no siblings
I am working on chapter 13 of CLRS. I am studying how to fix the colors on a red-black tree after deleting a black node.

Suppose we want to delete the node 2. This is a black node. He will be replaced by his rith child in the RB-DELETE algorithm. Because we removed a black node and the node replacing it is black (all NIL are black) then we enter the loop in RB-DELETE-FIXUP. Now this loop immediately asks for x's sibling w to enter different cases. But w in this case would just be 3's right child which is T.nil. It gets even worse from here because we start asking about 3's right child children in case 3 or 4. What's supposed to happen when x does not have siblings?

These are the relevant algorithms:

```
RB-DELETE-FIXUP(T,x)
1 while x different from T.root and x.color == BLACK
2   if x == x.p.left
3      w = x.p.right
4       if w.color = = RED
5          w.color = BLACK // case 1
6          x.p.color = RED // case 1
7          LEFT-ROTATE(T, x.p)/ // case 1
8           w = x.p.right // case 1
9       if w.left.color == BLACK and w:right:color = = BLACK
10         w.color = RED // case 2
11         x = x.p // case 2
12      else if w.right.color == BLACK
13              w.left.color = BLACK // case 3
14              w.color = RED // case 3
15              RIGHT-ROTATE(T, w)/ // case 3
16              w = x.p.right // case 3
17           w.color = x.p.color // case 4
18           x.p.color = BLACK // case 4
19           w.right.color = BLACK // case 4
20           LEFT-ROTATE(T, x.p) // case 4
21           x = T.root // case 4
22    else (same as then clause with “right” and “left” exchanged)
23 x.color = BLACK

```

RB-DELETE(T,z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4      x = z.right
5      RB-TRANSPLANT(T, z, z.right)
6 elseif z.right = = T.nil
7        x = z.left
8       RB-TRANSPLANT(T,z,z.left)
9 else y = TREE-MINIMUM(z.right)
10   y-original-color = y.color
11   x = y.right
12   if y.p = = z
13      x.p = y
14   else RB-TRANSPLANT(T,y, y.right)
15           y.right = z.right
16           y.right.p = y
17   RB-TRANSPLANT(T,z,y)
18   y.left = z.left
19   y.left.p = y
20   y.color = z.color
21 if y-original-color == BLACK
22   RB-DELETE-FIXUP(T,x)

```

# Answer
> 2 votes
Let $x$ denote the node you want to delete and $p(x)$ its parent. If $x$ has no sibling, then it necessarily means that $x$ is a red node, otherwise two path from $p(x)$ could have a different number of black nodes (therefore the tree is not a Red-black tree).

So the situation where $x$ is black and has no sibling can never happen (and the tree in your example is not a Red-black tree).

---
Tags: red-black-trees
---


# Question
Title: Unix glob() function and formal language equivalence
Can we express the matching capabilities of Unix library function `glob()` using a single-stack push-down automata, i.e. set of context free formal languages? If not, which is the minimal automata that we need?

For those that do not know what `glob()` does, it is a pattern matcher generator using a few operators:

* `*` matches an unlimited number of consecutive characters. As this can be in any position, not only in the end of the pattern, I eliminated the possibility of expressing glob expressions in terms of regular expressions.
* `?` matches exactly one arbitrary character, which is similar to a skip state in a finite automaton.
* `[abc]` matches an arbitrary-length string consisting of only symbols in the brackets, and `[!abc]` matches an arbitrary-length string that includes anything but symbols in the brackets. Those character sets can also be listed in a shorthand notation like `[a-z]` or `[!a-z]`.

# Answer
Every glob expression can be recognized with a regular expression (the translation is straightforward). Every regular language is also context-free, and there is a straightforward translation: convert the regular expression to a DFA, then turn that into a pushdown automaton that never uses or looks at its stack. So, it follows that every glob expression can be recognized by some pushdown automaton, i.e., it recognizes a context-free language.
> 1 votes

---
Tags: algorithms, pushdown-automata
---


# Question
Title: How to determine the average of two strings?
Given two strings $s$ and $t$, is there a way to find a string $a$ such that $d(a,s)=d(a,t)$, where $d$ is the Levenshtein distance?

I am sure that a genetic algorithm would work pretty well but I would prefer an explicit solution.

# Answer
The computation of the Levenshtein distance is a classic example of application of dynamic programming.

In this algorithm, you modify iteratively a matrix that denotes the distance between two prefixes of the two words. A modification occurs according to the following formula:

```
d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                   d[i, j-1] + 1,                   // insertion
                   d[i-1, j-1] + substitutionCost)  // substitution

```

You can then keep track of what of the three operations gave its value to `d[i, j]`, to know what steps are necessary to transform the first word into the second.

Now to find the "average" of $s$ and $t$, you can:

* if $d(s, t) = 2k$, then just do half of the modifications needed from $s$, to get the word $a$
* if $d(s, t) = 2k+1$, then do $k$ modifications and add a $\*$ instead of the $k+1$-th operation and get $a$

In both cases, $d(s, a) = d(a, t) = \left\lceil\frac{d(s, t)}{2}\right\rceil$ which is optimal.
> 2 votes

# Answer
Consider the $d(s,t)$ additions, deletions, and edits that transform $s$ in $t$.

Let $\*$ be a new character.

Instead of inserting the prescribed character, insert $\*$. Instead of deleting a character, change it to $\*$. Instead of replacing a character with the prescribed character, replace it with $\*$.

---

As an example, the edit distance between "mars" and "toast" is 4, and the corresponding edits are:

* Change "m" in "t"
* Add "o"
* Leave "a" unchanged
* Delete "r"
* Leave "s" unchanged
* Add "t"

Replace these steps with:

* Change "m" in $\*$
* Add $\*$
* Leave "a" unchanged
* Change "r" in $\*$
* Leave "s" unchanged
* Add $\*$

Applying these steps yields "$\**$a$\*$s$\*$".
> 3 votes

---
Tags: algorithms
---


title: Language of regular grammar

text:
# Question
Title: Language of regular grammar
What is the regular grammar of the language: $$L=\left\\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\\}\\:above\\:\Sigma =\left\\{a,\\:b,\\:c,\\:d\right\\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow aAb|\epsilon$$ $$B \rightarrow cBd|\epsilon$$ But I'm not sure if I'm right until here. Is it good?
Edit: This language is not regular, for this language you can look for the answer down: $$L=\left\\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\\} \cup \left\\{a^nb^mc^md^n\left|n,m\ge 1\right|\right\\}$$

# Answer
> 5 votes
Here's a simpler grammar: $$ S\rightarrow XY\\ X\rightarrow aXb\mid ab\\ Y\rightarrow cYd\mid cd $$ The key observation in cases like this is that strings in the language consist of two pieces concatenated: $a^nb^n$ and $c^md^m$, each of which can be generated by a simple grammar.

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


# Question
Title: Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists
Below is Question 8.1 in *Algorithms* by Dasgupta et al.

There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.

My questions are:

1. When they say input size, are they just referring to edges or both edges and vertices?
2. Is it correct to say that we make at most $log( |E| log K)$ calls?
3. Does this work if the edge weights aren't integers, like `10.4` etc?
4. Why is this **NP-Hard** as the solution mentions? I thought that Traveling Salesperson Problem was **NP-Complete**

This question on stackoverflow asks for clarification of binary search use but doesn't answer the above question.

# Answer
1. Input size refers to memory size needed to represent the input. In this case, it means number of edges + number of vertices, and you could also add size of the weights (which is logarithmic in their values).
2. No. It is written that we do $\log T$ calls and $T \leq |E| K$ (and this value can be reached), so the number of calls is at most $\log (|E| K) = \log |E| + \log K$.
3. Yes. It is never used in the algorithm that weights must be integers.
4. A $NP$-complete problem is a $NP$-hard problem which also needs to be in $NP$. So when speaking about a $NP$-complete problem, it is not false to state that it is $NP$-hard. However, $NP$ is a set of decision problems, therefore, TSP-OPT being an optimization problem cannot be in $NP$. We can still speak about $NP$-hardness as it can be informally defined for a non-decision problem as "a problem more difficult than all problems in $NP$". When you say "I thought that Traveling Salesperson Problem was NP-Complete", it refers to the decision version, denoted TSP in your reference.
> 1 votes

---
Tags: np-hard, np, traveling-salesman, binary-search
---


title: Finding max flow in a undirected graph

text:
# Question
Title: Finding max flow in a undirected graph
According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents something like $f((u,v))=c$ and $f((v,u))=c$ (where c is the capacity in the original undirected edge) but then that means the original graph has flow $2c$. Could someone prove or explain why the capacity restrictions are still satisfied?

# Answer
What you describe can happen in a feasible flow. However the net flow across the (undirected) edge $\\{u,v\\}$ would be $0$. Also, you say that the original graph has flow $2c$, this is false since the amount of flow from a vertex $s$ to a vertex $t$ in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving $s$ or, equivalently, entering in $t$.
> 1 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: solve a rational equation as fast as possible
I would like to find the first positive solution(if there is one) to this equation:

$$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$

The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+f) * (gx+h)$$ $$(=)$$ $$ax^2+bx+c - (dx^2+ex+f) * (gx+h) = 0$$ $$(=)$$ $$Ax^3+Bx^2+Cx+D = 0$$ and find the roots of the cubic. But, finding the roots of a cubic is computationally expensive. As it requierers the use of sqrt, cos and sin.

*(I am only looking for the smallest positive if there is any, if you know some algorithm that does that even for cubics, I would like to know more about it)*.

So my question is: "is there another way to find the solutions of this equation?" Like IF the equation was: $$(ax^2+bx+c) * (dx+e) = 0$$ it could be solved by solving the quadratic and the linear separately instead of calculating the resulting cubic and solve it afterward. Any help is appriciated! Thanks in advance.

# Answer
It depends on what kind of answer you want. Finding closed-form algebraic solutions is different from finding numeric solutions.

Having said that, I agree with plop here. Your best bet is to get bounds on the roots, and then use an iterative algorithm. The good news is that for a cubic, it's not difficult to find bounds.

First off, I assume that you know to compute the roots of a quadratic using the Citardauq formula when appropriate. If $b\ge 0$ then:

$$x\_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$$

$$x\_2 = \frac{2c}{-b - \sqrt{b^2 - 4ac}}$$

Otherwise:

$$x\_1 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$

$$x\_2 = \frac{2c}{-b + \sqrt{b^2 - 4ac}}$$

Using this method, the addition/subtraction of $b$ and the square root of the discriminant have the same sign, so there is no cancellation there.

To find all roots of a cubic $p(x) = a x^3 + b x^2 + cx + d$ numerically, first find the roots of the derivative $x\_1$ and $x\_2$, and evaluate the cubic at those two points. Assuming that $x\_1 \le x\_2$, you have four cases to consider.

1. If $x\_1 = x\_2$, then the cubic is of the form $a(x - x\_1)^3 + d - ax\_1^3$. This means it has one real root at $\sqrt\[3\]{x\_1^3 - \frac{d}{a}} + x\_1$. If $ax\_1^3=d$ then it's a triply-repeated root.
2. If $p(x\_1)$ and $p(x\_2)$ have opposite sign, then the cubic has three distinct real roots. Specifically, there is a real root in each of the following ranges: $\left(-\infty,x\_1\right)$, $\left(x\_1,x\_2\right)$, $\left(x\_2,\infty\right)$. Use this to get an initial estimate and use a numeric root finder.
3. If $x\_1 \ne x\_2$ but $p(x\_1)$ and $p(x\_2)$ have the same sign, then the cubic has only one real root. It is either in the range $\left(-\infty,x\_1\right)$ or $\left(x\_2,\infty\right)$, depending on the sign of $a$.
4. If one of $p(x\_1)$ or $p(x\_2)$ are zero, then there is a repeated real root at that point and a third real root elsewhere. Again, it is either in the range $\left(-\infty,x\_1\right)$ or $\left(x\_2,\infty\right)$, depending on the sign of $a$.

Because you need the smallest positive root, you can eliminate ranges from consideration. For example, suppose you find yourself in case 2. If $x\_2 \le 0$, you only need to check the range $\left(x\_2,\infty\right)$ for a positive root, as the other two roots are guaranteed to be negative. You never have to perform the iterative algorithm on all three ranges in case 2.

Doing this kind of exhaustive case analysis becomes unwieldy for higher-degree polynomials, which is why we tend to prefer different methods there. This is beyond the scope of the question, but as a general guide:

* It's usually worth performing squarefree factorisation if possible, because numeric methods tend to converge more slowly around repeated roots.
* You can bound the roots using Vincent's theorem (or Sturm's theorem, which is slower but a bit easier to understand) and then use numerical root finding if you only need the real roots.
* You can use something like Aberth's method if you need complex roots.
> 2 votes

---
Tags: algorithms, optimization, linear-algebra, computer-algebra, optimal-strategy
---


# Question
Title: Worst-Case Complexity of Quantifiers in Thompson's Construction
My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the length of the regex pattern.

Consider this pathological example: $a^\*a^\*ab$, which should match at least one $a$ followed by exactly one $b$. I'm going to refer to the compiled NFA as having three parts, with a "front part" representing the first $a^\*$, a "middle part" representing the second $a^\*$, and a "back part" representing $ab$.

The front and middle parts would look like this, with a simple $a$ symbol transition for $N(s)$:

The back part would look like two of these symbol transitions, one for $a$ then one for $b$:

Let's try to match $aaab$:

1. The compiled NFA starts in the start state.
2. Having two options due to the first Kleene star, it splits execution. It doesn't matter which state goes where, so let's just say state #1 takes the epsilon transition to move on to the middle part, and state #2 stays in the front part.
3. State #2 would match the first $a$, then split again. Let's say state #2 proceeds along the loop-back epsilon transition and stays in the front part, while a new state #3 moves on to the middle part. Now there are three states.
4. Meanwhile, state #1 – now in the middle part – also splits due to the second Kleene star, and does basically the same thing as state #2 did in the front part. Let's say state #1 moves on again to the back part, while a new state #4 goes into the Kleene star construction in the middle part, matches the first $a$, and in turn splits *again* into a state #5 that loops back within the second Kleene star construction, so state #4 can move on to the back part like state #1 did, except that state #4 has already matched the first $a$.

At this point, you can probably see what I'm getting at; the first Kleene star causes execution to split, in the worst case, $O(n)$ times, where $n$ is the length of the input, then the second Kleene star potentially causes each of those $O(n)$ splits to split $O(n)$ times, resulting in $O(n^2)$.

So there must be some way of pruning the possible states and avoiding $O(n^2)$ splits. An obvious pruning strategy would be to prune states if we've already visited the same node before in another state which had already consumed exactly the same amount of the input string. Keeping track of how much input we've consumed at each state is important since we cannot greedily consume either as much or as little as possible in the Kleene star constructions; in the example above, the whole input is only matched if the front and middle parts consume only the first two $a$'s between the two of them, so the back part can get the third $a$ and the $b$. But, this pruning strategy would result in $O(nk)$ space and time complexity, where $k$ is the length of the regex pattern, since there are $O(k)$ nodes in the NFA, and each node can have a unique state depending on how much of the length-$n$ input string it's consumed. I'm ok with $O(nk)$ running time, but I'm concerned about $O(nk)$ space complexity for large inputs in my application.

Is there some more genius pruning strategy that I'm not aware of? I don't have access to ACM, so I'm not able to read the original paper, and none of the articles of read about it go into enough detail to untangle this kind of situation.

# Answer
The point of a finite automaton is that the number of possible states that it can be in is finite. Specifically, if a NFA has $n$ states, then at any point in the input string, you can be in at most $n$ states at the same time.

The first observation is that you can precompute $\epsilon$ transitions. Define $\mathbf{closure} : Q \rightarrow 2^Q$ to be a function that takes a state and returns the state which are reachable using zero or more $\epsilon$ transitions. Then from this, we can compute an "extended" transition function $\delta^{\*} : Q \times \Sigma \rightarrow 2^Q$, which maps a state and an input symbol to the set of states that are reachable from it, then you can use this algorithm to recognise a string:

* Given the start state $s$, set $W := \mathbf{closure}(s)$. (Again, this can be precomputed.)
* For each input symbol $a$, set $W := \cup\_{s \in W}\\,\delta^{\*}(w, a)$.
* Accept if there is a final state in $W$.

This algorithm looks like it takes $O(k^2n)$ space in the worst case, namely, the space to represent $\delta^{\*}$. And the inner loop operation, $\cup\_{s \in W}\\,\delta^{\*}(w, a)$, looks like it should take $O(k^2)$ time in the worst case.

This isn't quite true in the word RAM model, however. Consider that the space needed to store a set of states can be measured in *bits*; since $k$ is known in advance, the sets like $W$ and the codomain of $\delta^{\*}$ can be represented as a bit vector, and set union can be a logical or. So in the word RAM model, the inner loop will actually take $O\left(\frac{k^2}{\log k}\right)$ time in practice.

Having said that, as you correctly guessed, Thompson's construction is not ideal for this use case. It has many advantages (not the least of which is that the space is linear in the size of the input regular expression), but the efficiency of its "obvious" recogniser algorithm is not one of them. As you rightly suspected, it produces a lot of unnecessary states that we can get rid of.

One obvious point is that it's trivial to optimise common "leaf" cases. For example, Thompson's algorithm will turn $a^\*$ into a NFA with 4 states, but it should be obvious that you "need" fewer than that, and the complexity of the construction for $E^\*$ is only needed because $E$ may be more complex.

Following this reasoning, it is possible, without too much difficulty, to construct an NFA with the following properties:

1. The number of states is equal to the number of alphabet symbols in the original regular expression (in some formulations, plus one for the start state, but here we will use a *set* of start states). That is, $a^\*a^\*ab$ should require exactly 4 states.
2. There are no $\epsilon$ transitions.
3. Every transition into a state $s$ has the same label.

Property 1 gives an accurate bound on the number of states which is computable at *parse* time.

Property 3 means that you can label *states* with alphabet symbols instead of *transitions*. Together with property 2, the transition function $\delta$ doesn't need to consider input symbols.

We define a *normal NFA* (NNFA) to be a 6-tuple $(\Sigma,Q,\delta,I,F,A)$ where:

* $\Sigma$ is the alphabet.
* $Q$ is a set of states.
* $\delta : Q \rightarrow 2^Q$ (or, alternatively, $\delta \subseteq Q \times Q$) is the transition function.
* $I \subseteq Q$ is the set of initial states.
* $F \subseteq Q$ is the set of final states.
* $A : Q \rightarrow \Sigma$ is a function which assigns labels to states.

Then the inner loop of the recogniser algorithm is to set:

$$W := \left\\{ s\\,|\\,w \in W, s \in \delta(w), A(s) = \alpha\right\\}$$

This should give you a lot of ideas as to how to implement this in data structures. For example, consider representing $\delta$ as a bit matrix and $A$ as a map from $\Sigma$ to a bit vector, where $A(\alpha)$ is the set of states $q$ which have the label $\alpha$. Then the inner loop becomes a bunch of bit vector unions (i.e. logical or operations) with a final bit vector intersection (i.e. a logical and). In the word RAM model, this is extremely efficient.

As to how to construct a NNFA, it's worth trying to come up with the idea behind it yourself, now that you know that it's possible. As a hint, start with Thompson's construction, and create a new automaton where the "new" states are the $\mathbf{closure}$ of every state which has a terminal transition coming into it. You can then think about how you could compute *that* automaton without explicitly constructing Thompson's automaton to begin with.

Once you've tried it, the best explanation that I've seen is Chang's PhD thesis. But here's the amazing part: Chang then goes on to give a compressed representation for a NNFA which takes $O(k)$ space, with a construction algorithm that uses $O(k)$ auxiliary space and $O(r)$ time where $r$ is (in some sense) the "size" of the input regular expression.

That effectively answers your question. There is indeed an algorithm which recognises regular expressions, which stores the automaton in $O(k)$ space, where $k$ is linear in the size of the input regular expression, and which takes $O(nk)$ time to recognise a string.
> 3 votes

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


# Question
Title: Representing FP relations using witnesses
> Let a relation $R$ be *A-polynomial* if there is a polynomial $p$ and a polytime algorithm $A$ such that for each $x$:
>
> 1. If $(x,y) \in R$ then there is a witness $w$ of length at most $p(|x|)$ such that $A(x,w) = y$.
> 2. For each $w$ such that $A(x,w)$ halts, we have $(x,A(x,w)) \in R$.
>
> Prove or disprove: Each $R$ in FP is A-polynomial.

My attempt: I think the statement is incorrect, and so I'm looking for a counterexample. Let $R$ be a relation in FP where the algorithm $A$ helps us decide the undecidable halting problem. I thought maybe about $R= \left\\{0,1\right\\}^\*\times \left\\{0,1\right\\}^\*$, but perhaps there is a simpler counterexample?

# Answer
> 1 votes
An $A$-polynomial relation can't have two many pairs agreeing on the first coordinate. Namely for any $x$ there can be at most $2^{p(x)}$ $y$'s such that $(x,y)\in R$. This shows that the simple relation $R=\\{0,1\\}^\*\times\\{0,1\\}^\*$ is in FP but not A-polynomial.

---
Tags: complexity-theory
---


# Question
Title: Show that both set A and set B are Turing reducible to some mixture of A and B
Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \\{2x\mid x \in A\\}\cup \\{2x + 1\mid x \in B\\}$.

Show that both $A$ and $B$ are Turing-reducible to $A+B$
I am kind of confused about this notion of turing reducibility thing.
Does it mean that There is a turing machine which converts an input from $A$ to an element of $B$
on the tape. There is a term called `oracle` that also pops up. So if we have an oracle for $B$
does it mean that there is a decider for $B$? What's an intuitive workable definition of oracle?

# Answer
> 1 votes
The definition of Turing reducible, is that there exists a Turing reduction \- an algorithm for $A$ (or $B$) that uses an oracle to $A+B$.

To understand this, you must first understand oracle machines. Those machines, are like turing machines, but can ask an "oracle" whether any $x$ is in $A$ or not, and would get an answer in $O(1)$, regardless of what $A$ is (doesn't even matter if it is not decidable!)

So, a turing reduction between $A$ and $A+B$ basically means that if you know for any $x$ whether its in $A+B$ or not, then you can decide whether a given $x$ is in $A$. Formally, this statement can be written as $A^{(A+B)}\in R$.

So basically the question asks you to show that both $A^{(A+B)},B^{(A+B)}\in R$

---
Tags: turing-machines, reductions, oracle-machines
---


# Question
Title: Proving a certain hypothesis class on a given distribution is not learnable
I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to solve it:

> Let $\mathcal X\_N=\\{0,1\\}^N$, $\mathcal Y=\\{0,1\\}$ and define a uniform distribution, $\mathcal D\_N$, on $\mathcal X\_N \times \mathcal Y$. Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P\_{S\sim \mathcal D^m} (\exists \\,1\leq i \leq N: L\_\mathcal D(i) \> \epsilon \\,\wedge \forall \\, 1\leq j \leq m, \\,x\_j(i)=y\_j)\>\delta$
>
> Original phrasing:
>
> Let $\mathcal X\_N=\\{0,1\\}^N$, $\mathcal Y=\\{0,1\\}$ and define a uniform distribution, $\mathcal D\_N$, on $\mathcal X\_N \times \mathcal Y$. Define the hypothesis class $\mathcal H\_N = \\{h\_i: \mathcal X\_N \to \mathcal Y \mid 1 \leq i \leq N \\}$, where $h\_i(x) = x(i)$.
>
> Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P\_{S\sim \mathcal D^m} (\exists \\,1\leq i \leq N: L\_\mathcal D(i) \> \epsilon \\,\wedge L\_S(h)=0)\>\delta$

So a few things:

$S$ is obtained by randomly and independently drawing $(x,y)$ pairs from $\mathcal D\_N$,

$L\_D(i) = \mathbb P\_{(x,y)\sim \mathcal D} (x(i)\neq y)$,

x(i) - is the i'th coordinate of the $N$ dimensional vector x.

What I tried to do was:

First of all, fix an $i\in \\{1,...,N\\}$ and consider $\mathbb P\_{(x,y)\sim \mathcal D} (x(i)\neq y) = 2\frac{2^{N-1}}{2^{N+1}} = \frac{1}{2} \> \epsilon $ for any $\epsilon \in (0,\frac{1}{2})$ so the first requirement is rather redundant.

Second, independently drawing a sequence $S$ of $m$ pairs (with repetition) such that every pair has $x(i)=y$ is with probability $\mathbb P\_{S\sim \mathcal D^m} (\forall \\, 1\leq j \leq m : x\_j(i)=y\_j) = \prod\_{j=1}^m \mathbb P\_{(x,y)\sim \mathcal D} (x\_j(i)=y\_j) = \frac{1}{2^m}$.

Now that's for a single fixed $i\in \[N\]$, trying to lower bound the probability of an existence of such an $i$ could either be done by just ignoring the rest and saying $\mathbb P\_{S\sim \mathcal D^m} (\exists \\,1\leq i \leq N: \forall \\, 1\leq j \leq m, \\,x\_j(i)=y\_j)\geq \frac{1}{2^m} \> \delta$
But that is a very gross estimation so I calculated the probability exactly using inclusion-exclusion principle like so:

let $1 \leq i\_1 \< i\_2 \<... \< i\_k \leq N\\,$ then $\mathbb P\_{S\sim \mathcal D^m} (\bigwedge\_{t=1}^k \\{ \forall \\, 1\leq j \leq m, \\,x\_j(i\_t)=y\_j\\}) = (\prod\_{t=1}^k \mathbb P\_{S\sim \mathcal D^m} (x(i)=y))^m = \frac{1}{2^{km}}$

finally we get:

$\mathbb P\_{S\sim \mathcal D^m} (\exists \\,1\leq i \leq N: \forall \\, 1\leq j \leq m, \\,x\_j(i)=y\_j) = \sum\_{i=1}^N (-1)^{i-1}{{N}\choose{i}}(\frac{1}{2^m})^i$

And now my goal is to lower bound this by $\delta$ and using some closed form of this expression.

My question is first, is my analysis even correct and second, how would you proceed?

Thanks in advance!

# Answer
Since each $x$ is uniformly chosen, the probability of having a certain value at the $i$'th spot is independent of the probability of finding some other certain value in the $j$'th spot. You showed this already, but notice it means that you dont need the inclusion-exclusion principle, and instead the probability will just be the probability of the complement, which is $1-\frac{1}{2^{km}}$. You can now easily choose $k$ such that this probability would be bigger than $\delta$
> 3 votes

# Answer
Your analysis appears fine, it remains to apply the binomial formula to compute your sum.

$\sum\limits\_{i=1}^N (-1)^{i-1} {N\choose i}\frac{1}{2^{mi}}=1-\sum\limits\_{i=0}^{N}(-1)^i {N\choose i}\frac{1}{2^{mi}}=1-\left(1-\frac{1}{2^m}\right)^N\ge 1-e^{-N/2^m}\ge\delta$,

Where the last inequality holds for $N\ge 2^m\log\frac{1}{1-\delta}$.
> 2 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication
I've recently stumbled upon a problem that I struggle realy hard with ever since.

There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary representation of $A\*B$ are set (how many 1s are there in the binary representation). Now, for small numbers, that's trivial. You just multiply them, and then using bit-shifts compare each bit with a 1, incrementing a 1-counter every time `bit & 1` is true. However, for very large numbers, hardly any programming language will allow the user to perform such multiplication. So how to achieve thet without any high-level languages and fancy libraries?

I think the proper start here is to create arrays for both numbers, to store them as separate digits. That can be done in a number of ways, from using `sprintf` and then transcribing the char array to int array using `intarr[i] = chararr[i] - '0'`, or by a simple loop which divides the number modulo 10 and then divides it by 10. Either way, we're left with two arrays of the respective numbers' digits, and we can multiply them by each other quite easily. Now, we're left with and int array of the multiplication result's digits. Where do we go from here? How to get a binary representation of a *very* large number stored like that? How to count the 1s in its binary representation? Is there any trick for that?

# Answer
I would assume that a *very large* product is at least say up to 128 bits (product of two 64 bit integers). In that case there are simple algorithms that calculate the higher and the lower 64 bits of the result, and then you count individually how many bits are set in the higher 64 bits, and how many in the lower 64 bits, and add the two numbers.

If your very large product is the product of say two numbers of $10^6$ bits each, these numbers could each be split into say 15,625 64 bit integers, and the product can be calculated easily with O(n^2) operations for n = 15,625. Or it can be calculated faster but with much more difficulty with a more complicated algorithm. This gives a result of 31,250 64 bit integers, and you can easily count the number of bits set in each integer, and add those numbers.
> -1 votes

---
Tags: data-structures, integers, binary, multiplication
---


# Question
Title: Subintervals during backward search of a BWT
A Burrows-Wheeler Transform (BWT) can be used to find the suffix array intervals for a pattern $P$ by issuing $p=|P|$ paired $rank$ queries \begin{align} s^\prime &= C\[P\[i\]\] + rank(s-1, P\[i\]) + 1 \\ e^\prime &= C\[P\[i\]\] + rank(e, P\[i\]) \end{align} where $s$ denotes the start of the search range and $e$ is the end of the range. Initially $s=1$ and $e=|BWT|$. $C$ is a lookup table containing the count of all alphabet symbols in the BWT that sort lexicographically before $P\[i\]$.

The search proceeds backwards through the search pattern, so it starts at $i=|P|$ and finishes at $i=1$. For example, given the BWT for string $\text{mississippi\\\\$}$ and pattern $P=\text{iss}$, the backward search will first identify the interval $\[9,12\]$ for $\text{s}$, then $\[11,12\]$ for $\text{ss}$, and lastly $\[4,5\]$ for $\text{iss}$.

See \[1\] for a more complete description of backward search and a walk through the example.

My question is during backward search is it possible to determine which subinterval of the previous character's interval lead to the current character's interval?

For example, given the BWT for string $\text{mississippi\\\\$}$ and pattern $P=\text{issi}$, the backward search will first identify the interval $\[2,5\]$ for $\text{i}$ and then $\[9,10\]$ for $\text{si}$. What I want to know is what subinterval of $\[2,5\]$ for $\text{i}$ lead to the $\[9,10\]$ for $\text{si}$. For this toy example I can see the answer is the subinterval $\[3,4\]$ of $\[2,5\]$ for $\text{i}$, but I want to know if/how this can be computed during the paired rank queries described above.

The literature suggests that this could be achieved by utilizing a forward search, but this would require a bidirection representation of the BWT, which seems excessive given that we already know the intervals that contain the subintervals.

Any insight would be greatly appreciated!

# Answer
> 0 votes
The answer is deceptively simple. After a paired $rank$ query for a character $P\[i\]$ you can compute the positions of $P\[i\]$ in the BWT by performing a paired $select$ query with the ranks from the paired $rank$ query. As seen in the image below taken from the linked example in the question, the character at position $i$ in a BWT is the left extension of the suffix at position $i$ in the corresponding suffix array. This means the positions of $P\[i\]$ in the BWT found by the paired $select$ query are also the subinterval of $P\[i+1\]$'s interval that lead to $P\[i\]$'s interval.

In other words, the subinterval can be computed during the paired $rank$ query with a complimentary paired $select$ query as follows \begin{align} r\_s &= rank(s-1, P\[i\]) + 1 \\ r\_e &= rank(e, P\[i\]) \\ s^\prime &= C\[P\[i\]\] + r\_s \\ e^\prime &= C\[P\[i\]\] + r\_e \\ s^{\prime\prime} &= select(r\_s, P\[i\]) \\ e^{\prime\prime} &= select(r\_e, P\[i\]) \end{align} where $s^{\prime\prime}$ and $e^{\prime\prime}$ denote the subinterval of $s$ and $e$ that lead to the $P\[i\]$ interval $s^\prime$ and $e^\prime$. As previously described, $s^{\prime\prime}$ and $e^{\prime\prime}$ are also the positions of $P\[i\]$ in the BWT.

---
Tags: algorithms, string-matching, exact-string-matching, succinct-data-structures
---


title: small o notation

text:
# Question
Title: small o notation
Let $f$ be an $o(2^{-\sqrt n})$ function, and let $g$ be an $o(2^{-\frac{n}{2}})$ function. Is the function $ f + g - fg$ is an $o(2^{-\sqrt n})$ function?

Can you help me prove that?

I think the answer is correct, but when for example, I consider the expression $\frac{2^{-\sqrt n} + 2^{-\frac{n}{2}} - 2^{-\sqrt n - \frac{n}{2}}}{2^{-\sqrt n}}$, I get something that tends to 1 instead of 0. What am I missing?

# Answer
> 6 votes
Let's take accordingly $f=2^{-\sqrt n}\varepsilon\_1$ and $g=2^{-\frac{n}{2}}\varepsilon\_2$, where $\varepsilon\_1,\varepsilon\_2$ tends to zero. Then you would like to have $f + g - fg = 2^{-\sqrt n} \varepsilon$. So, for $\varepsilon $ we have: $$\varepsilon = 2^{\sqrt n}\cdot\big(2^{-\sqrt n}\varepsilon\_1 + 2^{-\frac{n}{2}}\varepsilon\_2 - 2^{-\sqrt n-\frac{n}{2}}\varepsilon\_1 \varepsilon\_2 \big)\to 0$$ You had missed little-$o$ in your example.

---
Tags: asymptotics
---


# Question
Title: Structuring a Regression Model for NCAA Basketball Spreads/Totals
I have a basic linear regression model that predicts the spread and total points of NCAA college basketball games. My inputs include various efficiency metrics about each team playing each other. A snippet of the data I am working with looks like:

```
Team_1 Team_2  Off_Eff_T1 Def_Eff_T1 Pace_T1 Off_Eff_T2 Def_Eff_T2 Pace_T2 Line Over_Under
UCLA   Michigan    116.9    95.2        64.2       118.9      88.7    66.8    6.5    135.5

```

These are my model coefficients: adjO\_T1 = offensive efficiency for Team 1 (UCLA), adjD\_T2 = defensive efficiency for Team 2, etc.

```
(Intercept)  -5.39321
adjO_T1       0.65668
adjD_T1      -0.67104
adjT_T1       0.01819
Luck_T1      -2.79183
oppO_T1       0.16446
oppD_T1      -0.20572
adjO_T2      -0.66651
adjD_T2       0.66858
adjT_T2       0.09720
Luck_T2       0.30050
oppO_T2      -0.12808
oppD_T2       0.18562

```

As can be seen, I have efficiency metrics for both teams playing each other. As I have trained my model, the coefficients between "Team 1" and "Team 2" are obviously different. T\_1 is the home team and T\_2 is the away team. But if I were to switch these (enter T\_2 as the home team), the prediction of the spread/total would be drastically different just due to the different model coefficients. Is there a way I can get around this? Aka, the prediction would be the same regardless of what team was entered as home or away. In the example above, if UCLA is T\_1 it predicts they should be 2.5 point underdogs. But if Michigan is T\_1, they are predicted to be 8 point favorites.

However, Home or Away is not an input to my model so I feel that the predictions should be the same. If someone could provide better suggestions as to how I could structure my data or if I am going about this the right way, that would be a huge help.

# Answer
> 2 votes
I think a natural approach would be to constrain the coefficient of adjO\_T2 to be the negation of the coefficient of adjO\_T1, the coefficient for adjD\_T2 to be the negation of the coefficient for adjD\_t1, etc. Then, you could learn a logistic regression model subject to that constraint.

This could be implemented in practice by having only the coefficients of adjO\_T1, adjD\_T1, etc. be model parameters; the coefficients for adjO\_T2, adjD\_T2, etc., are not additional parameters, but are derived from the coefficients of adjO\_T1, adjD\_T1, etc. You can write down a loss function, using the logistic loss, for the loss of any particular set of parameters, and then use optimization to find the parameters that minimize the loss on the training set.

Related: see the Bradley-Terry model. The above is basically equivalent to using the Bradley-Terry model with exponential score function $p\_i = e^{\beta\_i}$ where here $\beta\_i$ is a linear combination of the metrics for that team, and your goal is to learn the coefficients in that linear combination. Then $\beta\_i$ or $p\_i$ represent the "strength" of team $i$, and the Bradley-Terry model says that the probability that team 1 beats team 2 is given by $p\_1/(p\_1+p\_2)$, i.e., it is a function of their relative strengths.

---
Tags: data-structures, machine-learning
---


# Question
Title: Sorting n weight disks with decision tree
I was refreshing some old tests about sorting algorithms, there was a question as follow:

> **Question:** we have `n` weight disks with different weights and we want to sort them pair by pair, How many times we have to weight in worst case (maximum comparisons) to sort the whole disks?

> the answer was $ \lceil \log n! \rceil $.

My issue is that I could not get to the answer and could anyone elaborate on how the answer is working?

> Also one of the options was $ \lceil n\log n \rceil $, and as we know, the order of $\log n!$ and $n\log n$ are same, So why shouldn't the ceilings be equal too?

> and How does having an **ordered** and **distinct** set of size `n`, matter in **decision tree**?

# Answer
I suspect that the question is looking for a **non necessarily tight** lower bound to the number of comparisons needed.

The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the decision tree represents a comparison has has $2$ children. This means that the height of the tree must be at least $\log\_2 n!$. Since the height must be an integer, you can take the ceiling.

However no algorithm can attain this number of comparisons in the worst case for all values of $n$ (notice that the intended answer does not use the asymptotic notation). Here you can find the number of comparisons needed to sort $n$ elements for some small values of $n$. For $n=15$, $\lceil \log 15! \rceil = 41$ but $42$ comparisons are needed.

To answer your second question, $\lceil n \log n \rceil$ is incorrect since it not a valid lower bound. For example, for $n=2$, $2 \log 2 = 2$ but $1$ comparison is sufficient. You are right in saying that $O(\log n!) = O(n \log n)$ but notice how the answers are not using the big-Oh notation.

Finally, you need the discs to be linearly ordered otherwise it doesn't make sense to compare them. Moreover the fact that the input elements are distinct allows you to consider a decision tree where the outcome of each comparison is binary and is either "greater than" or "smaller than".
> 2 votes

---
Tags: algorithms, asymptotics, sorting, decision-problem
---