# Question
Title: How are matchings a lower bound for an approximate vertex cover?
I am reading *Algorithms* by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.

They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $\log n$ of the greedy algorithm that is polynomial?

The images below show the optimal vertex cover = 8 but and a maximal matching of 12.

I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.

How can one improve on the edges picked then? My 16 vertices versus the book's 12?

# Answer
> 1 votes
Let $M$ be a maximal matching, that is, $M$ is a matching which is not contained in a larger matching. Note that $M$ need not be a maximum matching, which is a matching of maximal size.

If $M$ contains $m$ edges, then:

1. Any vertex cover contains at least $m$ vertices.
This is because any vertex covers at most one edge of the matching.
2. There exists a vertex cover containing $2m$ vertices, namely, all vertices of the matching.
Indeed, if the vertices of the matching $M$ do not form a vertex cover, then there is some edge $e$ which is not covered by the vertices of $M$, and so $M$ is contained in the larger matching $M \cup \\{e\\}$, contradicting the definition of $M$.

---
Tags: approximation, matching
---


# Question
Title: Do the following two CFGs describe the same language
Do the following two CFGs describe the same language

1. S → aS | bS | ε
2. S → aS | Sb | ε

Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused about how I would find out if they described the same language.

# Answer
No. The word "abab" is described by (1) but not (2). You can test and visualize this here.

Trying to think about it inductively: (1) can only prepend "a" or "b" to a string while (2) can only prepend "a" and only append "b".

Switching the order of a production does not necessarily change the language the grammar represents, but it is in this case. As to the second part of your question, there is no generalizable or efficient way to determine whether two CFGs describe the same language.
> 1 votes

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


title: Intersection of two arrays

text:
# Question
Title: Intersection of two arrays
As part of a project i'm doing I have been looking for a way to find common values between 2 arrays including duplicates. For example;

A = \[2, 2, 3, 5\] B = \[2, 2, 5\] would return the array;

Common values = \[2, 2, 5\]

I have attempted using sets, and the intersection function, but neither gave duplicates

Any help appreciated

# Answer
> 4 votes
Python-specific questions are probably off-topic here, but this question can be seen as a language-agnostic algorithmic task: given two arrays $A$ and $B$, each representing a multi-set, return an array containing the elements in the multiset $C = A \cap B$. Here an element $x$ that has multiplicity $a$ in $A$ and $b$ in $B$, has multiplicity $\min\\{a,b\\}$ in $C$.

To solve this problem you can preliminary sort $A$ and $B$. Then, you can keep a pointer $p\_A$ to some element of $A$ and a pointer $p\_B$ to some element of $B$. Initially $p\_A$ (resp. $p\_B$) will point to the first element of $A$ (resp. $B$). I will use $A\[p\_A\]$ (resp. $B\[p\_B\]$) to denote the element of $A$ (resp. $B$) pointed by $p\_A$ (resp. $p\_B$). Also, it is convenient to assume that, whenever $p\_A$ (resp. $p\_B$) points past the end of $A$ (resp. $B$), $A\[p\_A\]$ (resp. $B\[p\_B\]$) has value $+\infty$.

Proceed similarly to the merge step of Mergesort:

* Initialize $C$ as an empty array.
* While ($p\_A$ is not past the end of $A$) or ($p\_B$ is not past the end of $B$)
    + If $A\[p\_A\] = B\[p\_B\]$:
        - Append $A\[p\_A\]$ to $C$.
        - Advance $p\_A$
        - Advance $p\_B$.
    + Else if $A\[p\_A\] \> B\[p\_B\]$:
        - Advance $p\_B$
    + Else (in this case $A\[p\_A\] \< B\[p\_B\]$):
        - Advance $p\_A$

# Answer
> 3 votes
While Steven's answer is correct, it runs in time $O(n \log n)$. Here is a Pythonic way of doing it that uses dictionaries and runs in linear time.

```
from collections import Counter

A = [2, 2, 4, 5, 4, 5, 6]
B = [2, 3, 4, 4]
CA = Counter(A)
CB = Counter(B)

solution = []
for e in CA:
    occurrences = min(CA[e], CB.get(e, 0))
    solution += [e]*occurrences
print(solution)

```

You can of course implement Counter yourself easily in other languages.

# Answer
> -4 votes
#include \<stdio.h\>

int main() {

int n1,n2,n3,i,j,k,count=0;

int a\[n1\],b\[n2\],c\[n3\];

n1=sizeof(a)/sizeof(a\[0\]);

n2=sizeof(b)/sizeof(b\[0\]);

n3=sizeof(c)/sizeof(c\[0\]);

printf("Enter the size of each array\n");

scanf("%d %d %d",&n1,&n2,&n3);

printf("enter %d elements:\n",n1);

for(i = 0; i \< n1; i++) {

```
 scanf("%d", &a[i]);

```

}printf("enter %d elements:\n",n2);

for(i = 0; i \< n2; i++) {

```
 scanf("%d", &b[i]);

```

}printf("enter %d elements:\n",n3);

for(i = 0; i \< n3; i++) {

```
 scanf("%d", &c[i]);

```

}printf("Intersection elements:\n");

for(i=0;i\<n1;i++){

```
  for(j=0;j<n2;j++){

    if (a[i]==b[i]){

      for(k=0;k<n3;k++){

            if((a[i]==b[j])&&(b[j]==c[k]))

                    printf("%d\n",a[i]);

                    count++;

                }

          }

      }

}

```

printf("No.of loops %d\n",count);

return 0;

}

---
Tags: algorithms, arrays
---


# Question
Title: DFS produces the correct Topologically ordered sequence
> Prove that DFS produces the correct topologically ordered sequence.

I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?

# Answer
> 1 votes
Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph.

Now to prove that the above algorithm returns a topological sorting, we can use some lemmas about DFS $-$ namely the Parenthesis Theorem as well as the White Path Theorem. I will not get into the proofs of each lemma but we will use the following:

A corollary of the parenthesis theorem, as follows:

> Consider vertices $u$ and $v$ in $G$. Then $v$ is a descendant of $u$ in the DFS forest of $G$, if and only if $d(u)\<d(v)\<f(v)\<f(u)$, where $d(x')$ is the discovery time of vertex $x'$ and $f(x')$ is its finish time.

Also, we will use the white path theorem which states that

> Vertext $v$ is a descendant of vertex $u$ in the DFS forest if and only if at time $d(u),$ there exists a white path from $u$ to $v.$

Now let $e = (u,v)$ be an edge in the input graph. We want to prove that in our output, $u$ comes before $v$. We can show that by proving that in our DFS traversal, $f(u) \> f(v).$

CASE I: $d(u) \< d(v)$

By the White Path Theorem, $v$ is a descendant of $u$. This is because at time $d(u)$, there is a white path in $G$, which must be from $u$ to $v$ as there exists edge $e = (u,v)$. Hence, we can use the corollary of the parenthesis theorem to show that $f(u) \> f(v).$

CASE II: $d(v) \< d(u)$

At time $d(v)$, there is no white path from $v$ to $u$, as that would imply that $G$ has a cycle (meaning that it is not a DAG), and hence $u$ cannot be a descendant of $v$ in the DFS forest of $G$. So by the parenthesis theorem, we have $d(v) \< f(v) \< d(u) \< f(u)$. Again, we proved that $f(u) \> f(v)$.

Hope that helped :)

---
Tags: depth-first-search, topological-ordering
---


# Question
Title: Given a binary min-heap, find the $k$-th element
I'm given a binary min-heap (implemented with an array) and need to come up with a (simple) efficient (no more than $k$ comparisons) to find the $k$-th minimal element.

My attempt was as follows:

1. check who is the smallest among the root children
2. scan the corresponding sub-heap maintaining a counter counting how many nodes are smaller than the larger child of the root (but larger than the smaller child). If the counter reaches $k-1$ return the value of the current node. other-wise after the scan is finished, call this method recursively on the larger root child to find the ($k$ $-$ couter\_value + 1)-th minimal element of the larger child.

I just can't put this together formally and not sure this can be implemented with no more than $k$ comparisons.

Thanks for any help.

# Answer
> 1 votes
The minimum element will the root. So in constant time you can find the minimum element. Delete the minimum element from the root. Now min-heapify (make it minheap) the resultant tree.

The second minimum element will be the root again. Repeat the procedure mentioned above.

By this procedure, you will find $k$-th minimum element in time $O(k \log n)$ where $n$ is the number of elements in the given min-heap.

---
Tags: data-structures
---


title: Turing Machine for strings without bbb

text:
# Question
Title: Turing Machine for strings without bbb
I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \\{a, b\\}$.

When I implement this graph in JFLAP, I'm receiving an error that there are transitions out of final states. Is it OK to construct a transition graph like this, or is it considered bad practice? If so, can you help me understand the correct way to construct the transition graph?

# Answer
The state $q\_3$ is not necessary, because you couldn't have string with the pattern $bbb$ inside of them. So, just delete it. The next automaton accepts your language requirement.

Hope it helps
> 2 votes

# Answer
what you can do with that Jflap issue is that just remove the q3 from your turing machine and add new state and make an empty transition from all the final state to the new state added, make the new state as final state and change all previous final state i.e. q0, q1 and q2 to non final state your issue with jflap will be resolved here's your required turing machine
> 2 votes

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


# Question
Title: Select fixed-size connected induced subgraphs in a graph
I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions at random. It doesn't necessarily need to be *uniformly* at random, I just want the possibility of getting any possible solution.

For example, with this graph:

and $k=3$, $n=2$, here is a solution (in fact it's the only one):

And here's one of the two possible solutions for the same graph with $k = 2$ and $n = 3$:

Sometimes this is not possible, like with this graph, for $k = 3$ and $n = 2$:

Is there any (efficient) way of determining whether there is a solution, and if so, selecting one (not necessarily uniformly) at random?

# Answer
> 1 votes
The problem is unfortunately NP-hard. Thanks to Dmitry for finding this: https://www.sciencedirect.com/science/article/pii/0166218X85900083.

---
Tags: algorithms, graphs, connected
---


# Question
Title: If P = NP, do these NP-complete problems reduce to these specific easier versions?
I am trying to understand reductions and NP-completeness from *Algorithms* by Dasgupta et al.

Chapter 8 has the table below and I am wondering:

1. if $P = NP$ does each of the problems on the left reduce to the easy problem (in $P$)in its immediate right?

2. The book mentions that

> the problems on the left are all difficult for the same reason! At their core, they are all the same problem, just in different disguises! They are all equivalent:

does this imply that the problems on the right are also *the same problem but in different guises*? Can they be solved the same way like solving `SAT` for NP-complete problems? If so, what's the equivalent of `SAT` for problems in $P$ ? I understand that `SAT` reduces to all problems in $NP$ but is there a problem in $P$ that sort of holds the same position as `SAT` in $NP$?

3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if $P=NP$? This was asked in a true-false question and couldn't get it right. The options were: true, false, true if $P=NP$, true $P \neq NP$. In my opinion, the Rudrata/Hamiltonian path could be reduced to a *spanning tree* and **not** *necessarily the minimum spanning tree* as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

# Answer
> 2 votes
> 1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right?

If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally similar problems for the left and right columns to make the point that a seemingly small change to an efficiently solvable problem can make it NP-complete, and vice versa.

> 2. The book mentions that "the problems on the left are all difficult for the same reason! At their core, they are all the same problem \[...\]" does this imply that the problems on the right are also the same problem but in different guises?

I would say no. NP-complete problems are all polynomially equivalent, meaning that given an oracle that computes the answer to one in polynomial time, you can answer any other in polynomial time. Because there is no polynomial-time algorithm known for any of them without the oracle, the amount of time you save by using the oracle dominates the total time for large enough problem sizes, so you can argue that the oracle is doing the heavy lifting. This applies to any pair of NP-complete problems, so they all contain models of important parts of each other in a nontrivial way – somewhat like different computational models can simulate each other

Problems in P are trivially polynomially equivalent: given an oracle for one, you can solve any other one in the usual way and ignore the oracle. But you can't argue from this equivalence that the oracle played any role. P contains many problems like "is the input nonempty?" that are of no use in solving any other problem and clearly don't "contain" interesting problems like MST.

If it turns out that P=NP then it becomes much harder, perhaps impossible, to formalize the relationship between the problems that were formerly considered NP-complete; the apparent similarity between them might just be an illusion.

> 3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if P=NP?

In the trivial sense, yes. If P≠NP, then it doesn't (if it did, that would give you a polynomial-time algorithm for Hamiltonian path).

> In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

It might be reducible to some other spanning-tree algorithm, but that algorithm would have to be flexible enough that you could encode the Hamiltonian-path constraint somehow in the input.

---
Tags: optimization, np-complete, np, p-vs-np, hamiltonian-path
---


# Question
Title: If P = NP, would dynamic programming be obsolete?
I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic programming would have a more efficient (polynomial) way to solve? Or are there problems that even if P = NP, we would still use dynamic programming

# Answer
> 3 votes
Absolutely not. P = NP doesn't imply that problems that can be solved with dynamic programming can be solved easier or quicker with another algorithm.

---
Tags: complexity-theory, dynamic-programming
---


title: Arithmetical degree of suborders of Q

text:
# Question
Title: Arithmetical degree of suborders of Q
At the moment I am studying several questions about the arithmetical degree of some index-sets in relation to the standard-ordering on $\mathbb{Q}$. The situation is as follows: I fix some enumeration $r\_0, r\_1, \ldots$ of $\mathbb{Q}$ such that $\<$ is decidable. Then I take $R\_e=\\{r\_n \mid n \in W\_e\\}$, where $W\_e=dom(\varphi\_e)$ (the domain of the $e^{th}$ partial recursive function, refering to Kleene's Normal Form Theorem). Now $R\_e$ inherits the ordering from $\mathbb{Q}$.

$\textbf{Question 1}$
Define $$ A = \\{ e \mid (R\_e,\<) \cong (\mathbb{Z},\<)+(\mathbb{Z},\<) \\}. $$ I try to prove that every $\Sigma\_3$-set $m$-reduces to $A$ but I don't have a good idea. Does somebody see something useful I can do?

$\textbf{Question 2}$ I want to show that there exists $d$ such that the sets $\\{e \mid (R\_e,\<) \cong (R\_d,\<)\\}$ and $\\{e \mid (R\_e,\<) \equiv (R\_d,\<)\\}$ are not arithmetical at all. Does somebody has a good idea for this?

# Answer
Talking about suborders of $\mathbb{Q}$ explicitly makes things a bit harder to think about than is necessary, in my opinion. Really we should be talking about *general computable (or rather, c.e.) linear orders* \- the point is that $\mathbb{Q}$ is "big enough" that we can WLOG construe these as suborders of $\mathbb{Q}$ for concreteness. This does make some definitions snappier, but I think obscures the intuition; instead, I think it's best to think of linear orders being built by progressively "laying down points" (or refraining from doing so of course).

For example, suppose I have a Turing machine $\Psi$ and I want to tell whether $\Psi(0)$ halts. Consider the following process for building a linear order: I start building a descending sequence until I see $\Psi(0)$ halt, at which point I build an *ascending* sequence starting from the very first point I laid down. For example, if $\Psi(0)$ halts at step $5$, the linear order I build is $$\color{red}{a\_4\<a\_3\<a\_2\<a\_1\<a\_0}\color{green}{\<a\_5\<a\_6\<a\_7\<a\_8\<...,}$$ the red part corresponding to the points added *before* I saw the computation halt and the green part corresponding to the points added *after* I saw the computation halt. It should be clear that if $\Psi(0)$ halts then I wind up building something isomorphic to $\mathbb{N}$, whereas if $\Psi(0)$ doesn't halt I build something isomorphic to $\mathbb{N}^\*$ (= the "reverse order" of $\mathbb{N}$); thinking along these lines, you should be able to prove that $0'\le\_T \\{ e: (R\_e,\<)\cong (\mathbb{N},\<)\\}$.

Now thinking towards Question $2$, we want to generalize the above idea to higher jumps: e.g. find some "analogue of $\mathbb{N}$" which gets $0''$, and another which reduces $0'''$, and so on ... until we get an idea for one which gets every (finite) iterate of the jump all at once. At this point ordinals become useful for organizing ideas; I recommend thinking about $\omega^2$ in particular, and how we can think about this ordinal as $\omega$-many copies of $\mathbb{N}$ (keeping in mind how a single copy of $\mathbb{N}$ can encode a specific question about the halting problem).

---

OK, what about Question $1$?

Well, let's think about how hard it is to tell whether a computable linear order $L$ looks like $\mathbb{Z}+\mathbb{Z}$. This amounts to the following:

* **$L$ is nonempty.** This is $\Sigma\_1$: "At some stage we lay down a point."
* **Every point in $L$ has both an immediate successor and an immediate predecessor.** This is $\Pi\_3$: "For every point $a$ in $L$ there are $b,c\in L$ such that $b\<a\<c$ and at no stage do we add a point other than $a$ to $(b,c)$."

Note that these two conditions alone ensure that $L$ is a sum of copies of $\mathbb{Z}$. We now need to do the hard bit: ensure that we have *exactly two* copies of $\mathbb{Z}$ in $L$. This leads to our third and fourth conditions:

* **There are two points which are infinitely far from each other.** This is $\Sigma\_3$: "There are $a\<b$ such that at every stage there is some later stage at which we add a new point to $(a,b)$."
* **There are no three points which are each infinitely far from each other.** This is $\Pi\_3$: "For every $a\<b\<c$ we *either* stop adding points to $(a,b)$ at some stage *or* we stop adding points to $(b,c)$ at some stage."

Once appropriately formalized, this shows that $A$ is $\Pi\_3\wedge\Sigma\_3$; it's now natural to hope that every $\Pi\_3\wedge\Sigma\_3$ set $m$-reduces to $A$, and Question $1$ is a step towards this. If we want to reduce an arbitrary $\Sigma\_3$ set to $A$ we probably want to focus on the "$\Sigma\_3$-part" of the characterization of $A$; in the above, this was the "There are two points infinitely far apart from each other" bit.

Here's a construction which starts us off in the right direction:

> Suppose I have a $\Sigma\_3$ sentence $\varphi\equiv\exists x\forall y\exists z(\theta(x,y,z))$ with $\theta\in\Delta\_0$; I want to "computably build" a linear order which has a pair of points infinitely far from each other **iff** $\varphi$ is true. To do this, I work in "blocks:"
>
> * For each $i\in\mathbb{N}$ I have a block $B\_i$. Every point in $B\_i$ will be above every point in each $B\_j$ with $j\<i$ and below every point in $B\_k$ with $k\>i$, and each $B\_i$ starts off with a single point.
> * I add points to $B\_i$ in such a way that $B\_i$ is isomorphic to $\mathbb{N}$ iff $\forall y\exists z(\theta(i,y,z))$ and is finite otherwise. For example, add an element to the "end" of $B\_i$ each time I see $\\{y: \forall y'\<y\exists z(\theta(i,y',z))\\}$ gain an element.
>
> If $\varphi$ is true then at least one $B\_i$ is infinite, and this forces a pair of points to be infinitely far apart (consider a point in $B\_i$ and a point in $B\_{i+1}$). Conversely, if $\varphi$ is false then each $B\_i$ is finite and we wind up building a copy of $\mathbb{N}$.

Now (even ignoring the formalization) there are two issues with this, as far as Question $1$ goes. First, there's the problem that the "blocks" look like $\mathbb{N}$ instead of $\mathbb{Z}$; this is easily fixed, though. More serious is the issue that if $\varphi$ is true we might wind up with **too many** infinite blocks; fixing this will require some thought (and ultimately some *injury*).
> 2 votes

---
Tags: computability, order-theory
---


# Question
Title: K Nearest Neighbor using K-D Tree (What ratio makes K-D beneficial)?
I'm trying to implement a KNearestNeighbor model and came across the fact that many professional models use a K-D tree to index the K Nearest Neigbors. I also read that high-dimensional data makes a K-D tree less useful because you don't eliminate as many vectors for every branch in the tree when traversing it. All of that makes sense, but my question is at what ratio is there any benefit made of using a K-D tree?

For instance, I have a training set of shape (50000, 3072) but I am feeding only 10000 points to the model so the shape the model gets is (10000, 3072)... anyways, I assume these are the only two numbers which are relevant for the model to determine if a K-D would benefit it's runtime.

So in my fit method, I am making an if statement to either make a K-D model or not to make a K-D model for indexing, but I'm not sure what the condition should be. Given

```
n_data, n_dim = x.shape

```

I imagine the condition could be

```
if n_data / n_dim >= 1:
    pass

```

This is where my knowledge stops. I would be grateful if someone could propose a condition, and educate me about what makes a good condition.

# Answer
> 0 votes
There's no way to tell for sure without trying out. That said, a crude rule of thumb is that k-d trees tend to be useful when the number of dimensions is up to about 10-20, but in higher dimensions, often they are little better than a naive linear search over all points.

See also Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?, How can I make k nearest neighbor queries fast on unit hypersphere?, https://en.wikipedia.org/wiki/K-d\_tree#Degradation\_in\_performance\_with\_high-dimensional\_data

---
Tags: python, machine-learning
---


# Question
Title: Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".

I am trying to do Problem 7.4.4:

> "Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
>
> Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter)."
>
> Which of the following classes of functions are closed under left polynomial composition, and which under right polynomial composition?
>
> (a) - $\\{n^k: k \> 0 \\}$
>
> (b) - $\\{k \cdot n: k \> 0 \\}$
>
> (c) - $\\{k^n : k \> 0 \\}$
>
> (d) - $\\{2^{n^k} : k \> 0 \\}$
>
> (e) - $\\{\log^k n: k \> 0 \\}$
>
> (f) - $\\{\log n\\}$

After understanding the definition of closed under left/right polynomial composition, I think I was able to solve items (a), (b), (c) and (f). However, I was not able to solve items (d) and (e).

My solution for item (a):

> **Closed Under Left Polynomial Composition**: consider an arbitrary $f(n) \in C$ and an arbitrary polynomial $p(n)$. Then, $f(n)$ is of the form $n^{k'}$, for some $k' \> 0$ and therefore $p(f(n))$ is a polynomial. Let $k''$ be the degree of the polynomial $p(f(n))$. Take $g(n) = n^{k''} \in C$ and we have $p(f(n)) = O(g(n))$.
>
> **Closed Under Right Polynomial Composition**: same reasoning.

My solution for item (b):

> **Not Closed Under Left Polynomial Composition**: consider as a counterexample $f(n) = n \in C$ and $p(n) = n^2$. Then, $p(f(n)) = n^2$. For every $g(n) = k n \in C$ we have $O(g(n)) = O(n)$. Since $n^2 \neq O(n)$ we conclude.
>
> **Not Closed Under Right Polynomial Composition**: the previous counterexample applies.

My solution for item (c):

> **Closed Under Left Polynomial Composition**: Consider an arbitrary $f(n) = k\_1^n$ and a polynomial $p(n)$. Notice that $p(f(n))$ is a polynomial in $k\_1^n$. For sufficiently large $n$, there exists some $k\_2$ such that $p(n) \leq n^{k\_2}$ and therefore $p(f(n)) \leq \[f(n)\]^{k\_2} = (k\_1^{n})^{k\_2} = (k\_1^{k\_2})^n$. Therefore, taking $g(n) = (k\_1^{k\_2})^n \in C$ we obtain that $p(f(n)) = O(g(n))$.
>
> **Not Closed Under Right Polynomial Composition**: Consider as a counterexample $f(n) = 2^n$ and $p(n) = n^2$. Then, $f(p(n)) = 2^{n^2}$, which is greater than $g(n) = k^n$, for every fixed value of $k$, if $n$ is sufficiently large. Therefore, $f(p(n)) \not \in O(g(n))$.

My solution for (f):

> **Not Closed Under Left Polynomial Composition**: Consider as a counterexample $f(n) = \log n$ and $p(n) = n^2$. Then, $p(f(n)) = \log^2 n$. Also, $g(n) \in C$ implies that $g(n) = O(\log n)$. We have $\log^2 n \not \in O(\log n)$.
>
> **Closed Under Right Polynomial Composition**: If $f(n) \in C$ then $f(n) = \log n$. Given an arbitrary polynomial $p(n)$, we have that there exists some $k'$ such that, for sufficiently large $n$, $p(n) \< n^{k'}$. Then, for sufficiently large $n$: $ f(p(n)) \leq f(n^{k'}) = \log n^{k'} = k' \log n = O(\log n) = O(g(n)).$

Can anyone help me with items (d) and (e)?

Thanks in advance. Of course, corrections/comments on the other items are also welcomed.

# Answer
For item (d):

> **Closed under left polynomial composition**: Consider an arbitrary $f(n) = 2^{n^{k\_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k\_2$ such that $p(n) \leq n^{k\_2}$, for sufficiently large $n$. For sufficiently large $n$, $p(f(n)) \leq \[f(n)\]^{k\_2} = \[2^{n^{k\_1}}\]^{k\_2} = 2^{k\_2 n^{k\_1}}$. There exists $k\_3$ such that $2^{k\_2 n^{k\_1}} \< 2^{n^{k\_3}}$ for sufficiently large $n$. Therefore, choosing $g(n) = 2^{n^{k\_3}} \in C$ we have $p(f(n)) = O(g(n))$.
>
> **Closed under right polynomial composition**: Consider an arbitrary $f(n) = 2^{n^{k\_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k\_2$ such that $p(n) \leq n^{k\_2}$, for sufficiently large $n$. For sufficiently large $n$, $f(p(n)) = 2^{\[p(n)\]^{k\_1}} \leq 2^{(n^{k\_2})^{k\_1}} = 2^{(n^{k\_2 k\_1})}$. Therefore, taking $g(n) = 2^{(n^{k\_2 k\_1})} \in C$ we obtain that $f(p(n)) = O(g(n))$.

For item (e):

> **Closed under left polynomial composition**: Consider an arbitrary $f(n) = \log^{k\_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k\_2$ such that $p(n) \leq n^{k\_2}$, for sufficiently large $n$. Therefore, for sufficiently large $n$, $p(f(n)) \leq f(n)^{k\_2} = (\log^{k\_1} n)^{k\_2} = \log^{k\_1 k\_2} n$. Choosing $g(n) = \log^{k\_1 k\_2} n$ we have $p(f(n)) = O(g(n))$.
>
> **Closed under right polynomial composition**: Consider an arbitrary $f(n) = \log^{k\_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k\_2$ such that $p(n) \leq n^{k\_2}$, for sufficiently large $n$. Take $g(n) = \log^{k\_1} n$. We have, for sufficiently large $n$: $ f(p(n)) = \log^{k\_1} p(n) \leq \log^{k\_1} (n^{k\_2}) = (k\_2 \log n)^{k\_1} = {k\_2}^{k\_1} \log n^{k\_1} = O(\log n^{k\_1}) = O(g(n))$.
> 1 votes

---
Tags: complexity-theory, closure-properties
---


# Question
Title: Find the minimum cost of adding the elements of a set (greedy algorithm)
I'm VERY stuck with this problem:

Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$. For example, the possible costs of the next set $\\{1,2,5 \\}$ are:

* The cost of adding $1 + 2$ (with cost $3$), plus the cost of $3 + 5$ (with cost $8$). The overall cost is $11$.
* The cost of adding $1 + 5$ (with cost $6$), plus the cost of $6 + 2$ (with cost $8$). The overall cost is $14$.
* The cost of adding $2 + 5$ (with cost $7$), plus the cost of $7 + 1$ (with cost $8$). The overall cost is $15$.

We want to find the minimum overall cost (implementing a greedy-algorithm).

I've implemented two approaches:

```
const minCost = (l = []) => {
    sort(l);
    let cost = 0;
    let currentSum = 0;
    for(let i = 0; i < l.length - 1; i++){
        if(i === 0){
            currentSum = l[i] + l[i + 1];
            cost += currentSum;
        }
        else{
            currentSum += l[i + 1];
            cost += currentSum;
        }
    }
    return cost;
}

```

What im doing here is sorting in ascending order, and then simply computing the costs (like the first option in the example).

The issue I found is with the following instance: \[2,2,2,2\] will compute a cost of 18. But, I've realized that you can group the elements and compute the cost of the in this way: ((2+2) + (2+2)), with overall cost of 16.

So I also came out with this approach:

```
const cost = (l = []) => {
    if(l.length <= 1) return 0
    else return l.reduce((acc, val) => acc + val, 0)
}

const minCostRecursive = (l = []) => {
    if(l.length <= 2) return cost(l)
    let left = minCostRecursive([...l.slice(0, Math.ceil(l.length/2) )])
    let right = minCostRecursive([...l.slice(Math.ceil(l.length/2), l.length)])
    let newList = []
    left > 0 ? newList.push(left) : newList.push(...l.slice(0, Math.ceil(l.length/2)))
    right > 0 ? newList.push(right) : newList.push(...l.slice(Math.ceil(l.length/2), l.length))
    return left + right + minCostRecursive(newList)
}

```

The main idea is to partition the cost of the halves. If you have two items, the cost is the sum of the items. If you have one or fewer items, the cost is 0 (there is nothing to add). If not, I make a recursive call to the function with the halves, and with if its result is greater than zero, then I add it to a new list. If not, I add the element that was there before, and call the function again.

But also, I found a counterexample \[1,5,7,9\] (in the first implementation it gives 41, but in the second returns 44). Moreover, I think this isn't a greedy solution.

# Answer
I think the following algorithm can work (and is greedy):

* Put all elements in a priority queue
* While the priority queue has at least 2 elements, extract the two lowest elements, sum them, then add the sum to the priority queue

It gives a correct order for summing elements to get the minimal overall cost.
> 1 votes

---
Tags: recursion, greedy-algorithms
---


# Question
Title: Why has Windows used NTFS for 20+ years, while many different systems have trendend in the linux community over the same time?
I'm a first year MS:CS student, and my data structures class has inspired me to research file systems and their implementations. I recall using ext2, then ReiserFS, then ext3, then ext4, and now btrfs seems like the new thing. I understand (more or less) what changed from each of these, and their relative improvements, but what I don't understand is how NTFS has stayed relevant during roughly the same period of time (looks like the last major version of NTFS shipped with Windows XP).

Was NTFS simply that well spec'd and designed from the beginning, or has Windows been working around some NTFS deficiencies in the interest of not having to rewrite some core parts of Windows from scratch? If that is the case, why are linux distros much more flexible in changing FS (user can even select a different FS at install time).

# Answer
* NTFS is pretty good. From the start it had journaling (unlike ext2), size limits large enough that they would never be an issue (unlike ext2/3), and a flexible design that allowed arbitrary attributes to be defined and attached to files.
* Developing filesystems for Windows is difficult. The necessary headers and documentation were for years not included in the Windows driver development kit; instead you had to, I think, sign an NDA and pay thousands of dollars for the IFS kit and support. The number of features you'd have to implement to be able to replace NTFS is large. Filesystem design is a black art under the best of circumstances. And Microsoft probably wouldn't want to support a filesystem designed by a third party in the default Windows install no matter how good it was.
* Your list of popular Linux filesystems isn't all that long. ext2-4 are all pretty similar to each other, and btrfs is similar to ReFS.
> 1 votes

---
Tags: filesystems
---


# Question
Title: Why is CNOT the only non-trivial reversible gate for two input bits?
The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function: $$ 00 \to 00 \\ 01 \to 01 \\ 10 \to 11 \\ 11 \to 10 $$

I think I found a different non-trivial gate on two input bits: $$ 00 \to 01 \\ 01 \to 00 \\ 10 \to 10 \\ 11 \to 11 $$ I think the matrix corresponding to this gate is $$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} $$ which is different from $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{bmatrix} $$ and is also unitary.

# Answer
> 3 votes
The CNOT gate is definitely not the only non-trivial reversible gate on two input bits. For example, you could switch the order of inputs or the order of outputs. What Wikipedia means is that CNOT is the only non-trivial reversible gate *up to some allowed operations*, which consist of permuting the inputs and outputs, and applying reversible one-bit gates on the inputs and outputs.

If a two-input gate $G$ is reversible, then it is a permutation on $00,01,10,11$. By possibly negating the inputs (or the outputs), we can assume that $G(00) = 00$. By possibly switching the order of the inputs, we can assume that in $G(01) \< G(10)$. We are left with three possibilities: $$ 00 \to 00 \quad 00 \to 00 \quad 00 \to 00 \\ 01 \to 01 \quad 01 \to 01 \quad 01 \to 10 \\ 10 \to 10 \quad 10 \to 11 \quad 10 \to 11 \\ 11 \to 11 \quad 11 \to 10 \quad 11 \to 01 $$ The first possibility is the identity, which is trivial. The second possibility is CNOT. The third possibility is CNOT with outputs swapped.

---
Tags: quantum-computing, linear-algebra
---


# Question
Title: An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$
> If $n\<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient.

I am sure that this statement is valid, but I don't know how to prove it or justify it. Can someone please help me?

# Answer
Your statement is meaningless, since $O(n^2)$ and $O(n\log n)$ are just *upper bounds* on the time complexity. If you know that $A \leq 100$ and $B \leq 10$, you have absolutely no idea which is larger, $A$ or $B$.

Let us correct your statement to

> If $n\<100$ then $\Theta(n^2)$ is more efficient, but if $n \geq 100$ then $\Theta(n\log n)$ is more efficient.

This statement still has no truth value, since we don't know which functions are represented by $\Theta(n^2)$ and by $\Theta(n\log n)$. What we do know is that for large enough $n$, the $\Theta(n\log n)$ algorithm would be more efficient.

Suppose you instantiate your statement with specific functions $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n\log n)$. There is no reason to expect that there is a single crossover point. For example, take the following functions: $$ f(n) = \begin{cases} 100 & \text{if } n \< 20, \\ n^2 & \text{if } n \ge 20 \end{cases} \\ g(n) = \begin{cases} 50 & \text{if } n \< 10, \\ 200 & \text{if } 10 \le n \< 20, \\ 10^{300} n\log n & \text{if } n \ge 20 \end{cases} $$ As you can see, $g(n)$ is faster for $n \< 10$, and then for (astronomically) large enough $n$.

While such definitions are artificial, in practice we could have (say) $f(n) = 3n^2 + n\log n + 9n + 17$ and $g(n) = 10n\log n + 4\sqrt{n} + 50$, which might have several crossover points (I haven't checked).

Finally, even if there is a single crossover point, there is no reason to expect it to be exactly $n = 100$. The exact crossover point(s) depend on the functions $f(n),g(n)$. The only way to determine it is by running the two algorithms and comparing the running times.
> 4 votes

# Answer
We have $O(n\log n) \subset O(n^2)$ i.e. any $f$ from $O(n\log n)$ is also in $O(n^2)$.

Let's take any pair from $O(n\log n)$, for example $f\_1(n)=n$ and $f\_2(n)=n\log n$. Firstly we can consider them as $f\_1 \in O(n^2), f\_2 \in O(n\log n)$ and then we can consider them as $f\_2 \in O(n^2), f\_1 \in O(n\log n)$. It turns out, we cannot say that a representative of one class is definitely better than another.

Even more - we can formulate the following true sentence :

for any $f$ from $O(n\log n)$ we can find "faster" $g$ from $O(n^2)$.
> 1 votes

# Answer
$O(n\log n)$ is *always* faster. On some occasions, a faster algorithm may require some amount of setup which adds some constant time, making it slower for a small $n$.

So in reality, $O(n^2 + i)$ *may* be faster than $O(n\log n + j)$ if $j$ is sufficiently larger than $i$ for small enough $n$. There is certainly no number $n$ for which you can say there is definitely a crossover.

Note that we always ignore $i$ and $j$ in practice because big O notation is for when $n$ is large, so constants become increasingly meaningless and we only care about the fastest growing term.
> -4 votes

---
Tags: time-complexity
---


title: $O(n^2)$ and $O(n\log n)$ exercise

text:
# Question
Title: $O(n^2)$ and $O(n\log n)$ exercise
There is an exercise which says : Al and Bob are arguing about their algorithms. Al claims his $O(n \log n)$-time method is always faster than Bob’s $O(n^2)$-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n\<100$, the $O(n^2)$-time algorithm runs faster, and only when $n\ge 100$ is the $O(n \log n)$-time one better. Explain how this is possible.

# Answer
> 0 votes
Consider for Al $f\_{Al} \in O(n \log n) $:

$$f\_{Al}(n)=\begin{cases}n\log n, & \text{ when }n\lt 100 & \\ n , &\text{ when }n \geqslant 100\end{cases}$$

For Bob let's take $f\_{Bob}(n) \in O(n^2)$

$$f\_{Bob}(n)=\begin{cases}n, & \text{ when }n\lt 100 & \\ n\log n , &\text{ when }n \geqslant 100\end{cases}$$

Note also, that since for asymptotic relations it is only important what happens from some number to infinity, then Bob and Al are arguing in vain.

---
Tags: time-complexity
---


title: $P = NP$, what am I missing?

text:
# Question
Title: $P = NP$, what am I missing?
First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in advance for the help. Here we go:

Assuming we could solve a NP-complete problem in logn SPACE, e.g. TSP. Then by reachability we could show that $P = NP$.

The machine will keep track of this information:

* $\log n$ nodes for a path walked, call this memory `pathMem`
* $\log n$ nodes for a reconstructed path walked, call this memory `pathMemTemp`
* $\log n$ numbers indicating the chosen path, call this `chosenPathNums`
* $\log n$ nodes for ending nodes of each path, call this `endMem` some representation of the cost of the walk.

Step 1: Walk $\log n$ steps, note down the $\log n$ walked nodes in `pathMem`
Step 2: Check that there are no duplicates in `pathMem` (that means that you've walked $\log n$ unique nodes).
Step 3: Use a modified version of Savitch that counts the number of possible paths between start node and last node in `pathMem`. This should be at most $(\log(n)!)$ paths, represented in that number using binary and we get $O(log(log(n)!))$
Step 4: Find which of these paths that is in `pathMem`. Save that number in `chosenPathNums` at pos 1. This gives us a deterministic way of refinding a specific path.
Step 5: Move last node in `pathMem` to `endMem` pos 1, clear `pathMem`.

Step 6: Walk $\log n$ steps from node at `endMem` pos 1, note down walked nodes in `pathMem`.
Step 7: Check that there are no duplicates in `pathMem` (that means that you've walked $\log n$ unique nodes).
Step 8: Reconstruct path that was taken from start node to node at `endMem` pos 1 by using Savitch's and the `chosenPathNum`, save it in `pathMemTemp`.
Step 9: Check that `pathMem` and `pathMemTemp` has no overlap. If there is overlap, halt with no, otherwise continue.
Step 10: Find the path number that is in `pathMem`. Save that number in `chosenPathNums` at pos 2.
Step 11: Move last node in `pathMem` to `endMem` pos 2, clear `pathMem`.

Step 12: Rinse and repeat, now checking `pathMem` vs start-\>(`endMem` pos 1) and then (`endMem` pos 1)-\>(`endMem` pos 2) etc., until you've walked $n$ nodes, thus having $\log n$ nodes in `endMem` and $\log n$ numbers in `chosenPathNums`.
Step 13: Calculate distance walked, check if less or equal to threshold.

This algorithm could be turned deterministic by looping every possible $\log n$ walk that is found from a node to another node.

# Answer
> 3 votes
It is not clear what is your question, but I will guess that it is "what is my mistake in my proof of $P = NP$?"

In addition to the fact that the algorithm does not guarantee to find the minimal path (because the algorithm cant deterministicaly choose the endMem nodes), the number of possible $\log n$-walks given $\log n$ nodes is not polynomial: $(\log n)! \sim \left(\frac{\log n}{e}\right)^{\log n}\sqrt{2\pi\log n}\sim \frac{\sqrt{2\pi\log n}}{n}e^{\log n \log \log n}\sim \sqrt{2\pi\log n}\times n^{\log\log n - 1}$.

As for the space complexity, to check there are no overlap between two $\log n$-walks, you need to keep track of the whole path (and not only two consecutive $\log n$-walks). That needs $\Omega(n\log n)$ space ($n$ nodes with a binary encoding of size $\log n$). So the corresponding Turing Machine use polynomial space, not logarithmic space.

---
Tags: complexity-theory, turing-machines, np-complete, p-vs-np, traveling-salesman
---


# Question
Title: Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$
*Before you downvote, please note that this question is distinct from this similar looking question*

I came across the following the problem in "The Introduction to Algorithms" by Cormen et. al.

Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically non negative, either $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ or both.

In this book, $\overset{\infty}{\Omega}(g(n))$ is defined as follows:

$f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq cg(n) \geq 0$ for infinitely many *integers* $n$. Please note that here it says *integers*.

**Proof from a solution manual**

One approach is to show that if $f(n) \neq O(g(n))$ then $f(n) = \overset{\infty}{\Omega}(g(n))$.

In the book big Oh is defined as follows:

$f(n) = O(g(n))$ if there exists $n\_0 \> 0$ and $c \> 0$, such that $\forall n \geq n\_0$, $0 \leq f(n) \leq cg(n)$. Please note these inequalities are valid not just for integer $n$'s but for all $n \geq n\_0$.

$f(n) \neq O(g(n)) \implies $ $\forall n\_0 \> 0$ and $\forall c \> 0$ there exists $n \geq n\_0$ such that $f(n) \> cg(n)$

I am not going into the details but, by choosing different values for $n\_0$ we can show that there are infinitely many *real* $n$ such that $f(n) \> cg(n)$. However to prove that $f(n) = \overset{\infty}{\Omega}(g(n))$ we need to show that these infinitely many $n$'s are integers.

**My question is could you please show that there are infinitely many integers not just real numbers, that satisfy $f(n) \geq g(n) \geq 0$ when $f(n) \neq O(g(n))$**

# Answer
If you consider the following functions defined for $x\in \mathbb{R}$:

$f(x) = \left\\{\begin{array}{rl}1 & \text{if }x\in\mathbb{N}\\x&\text{otherwise}\end{array}\right.$ and $g(x) = \left\\{\begin{array}{rl}x & \text{if }x\in\mathbb{N}\\1&\text{otherwise}\end{array}\right.$

Then you have:

* neither $f \in O(g)$, because whatever the constant $C$, $x\in\]C,+\infty\[\setminus \mathbb{N}\Rightarrow f(x) \> Cg(x)$;
* nor $f\in \overset{\infty}{\Omega}(g)$ because whatever the constant $C$, $n\in\]\frac{1}{C},+\infty\[\cap\mathbb{N}\Rightarrow f(n)\<Cg(n)$ (so there cannot be infinitely many integers so that $f(x) \geq Cg(n)$).

So the question here implicitly supposes that the big Oh notation considers that $n\in\mathbb{N}$ (and I think that's why the chosen notation is $n$).
> 1 votes

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


# Question
Title: Find the minimum sum of distances between sets of points to a straight line in a plane
Given $n$ dots on a plane, such as: n couples ($x\_i$,$y\_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal

In order to do that, I need to write an alogrithem with a **linear** run-time ( $O(n)$ )

> MY METHOD
> I relate only for the $x$ values of each point as an element in an Array called $A$
> So I used the `Select(A,left, right, p)` & `Partition` Alogorithm in order to find the median of medians of the array

pseudo-code:

```
Select(A,left,right,p)
 n<-right-left+1
 if n=1 then
  return A[left]
 m<-⌈n/5⌉
 let B array with length m
 for i <-1 to m
  B[i]=medianOf5(A,left,right,x)
 x<-Select(B,1,m, ⌈m/2⌉)
 q <- partition(A,left,right,x)
 k <-q-left+1
 if p<k then
  return Select(A,left,q,p)
 if p>k
  return Select(A,q,right,p)

```

But, using median of medians seems unnecessary
If so, is there an easier way to that? if not ( or if yes for that matter ) was my way correct?

# Answer
Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is $\left| y - b\right|$.

The sum of a distances for a set of points $S = \\{(x\_1, y\_1), \dots, (x\_n, y\_n)\\}$ is then $$\left| y\_1 - b \right| + \cdots + \left| y\_n - b \right|$$ which is minimized for which $b$?
> 1 votes

---
Tags: data-structures, runtime-analysis, arrays, partitions, selection-problem
---


title: Maximize AND on a sequence of XORs

text:
# Question
Title: Maximize AND on a sequence of XORs
## Problem

We are given 2 arrays `a` and `b` both of length `n`. We build a third array `c` by rearranging the values in `b`. The goal is to find the optimal `c` that maximizes

```
result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])

```

where `^` is XOR and `&` is AND.

**Is it possible to do this efficiently?** It's straightforward to iterate through all possible permutations of `b`, but this is infeasible for large `n`.

## More details

* The order of the values in `a` is fixed.
* The order of the values in `b` may be rearranged to form `c`. That is, starting with `b = [1, 2, 3]`, it may be that the maximum result is obtained when the values are rearranged to `c = [2, 1, 3]`.
* `b` may be rearranged in-place if needed.
* Since the optimal `c` is not necessarily unique, any optimal `c` may be returned.
* Assume all values are 32-bit unsigned integers.
* `1 <= n <= 10,000`.

## Test cases

```
Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)

```

```
Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)

```

```
Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)

```

# Answer
> 1 votes
For bit #k to be set in the output, you need to arrange the numbers so that bit #k is either set in a\[i\] and cleared in c\[i\] or the other way round. Therefore bit #k must be set in exactly n of your 2n inputs. If that is not the case then bit #k cannot be set in the output. So first you determine all k such that bit #k is set in exactly n of the 2n inputs, and ignore all other ks.

Let k be the highest of these bit positions. Split the elements of b into those where bit #k is set and those where it is cleared, and pick c\[i\] from the correct one of these sets. That's always possible.

Let j be the second highest of these bit positions. Split the elements of b into four sets, where bit #k and #j are both set, bit #k is set and bit #j is cleared, etc. Depending on which bits in a\[i\] are set, you know from which subset of b you need to pick c\[i\]. This only works if the sets have the right sizes! If it doesn't work, ignore bit j and take the next highest bit. If it works you can set bit #k and #j in the result and proceed with the next higher bit.

---
Tags: algorithms, bit-manipulation
---


title: Time complexity of algorithms

text:
# Question
Title: Time complexity of algorithms
I have some questions that I don't understand about time complexity.

1. Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
2. Given that the best case complexity of the algorithm $A$ is $O(f(n))$ and the worst case complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
3. Given that the average case complexity of the algorithm $A$ is $Θ(f(n))$ and the worst case complexity of A is $O(g(n))$. It follows that $f(n) ∈ O(g(n))$.

I will appreciate if you can help me understand those!

Thanks a lot!

# Answer
The first and the last statements are correct, while the second one is *incorrect*.

## Statement 1

Denote by $T\_{min}$ the actual running time of the algorithm $A$, in the best case, and $T\_{max}$ in the worst case. By how we chose $T\_{min}$ and $T\_{max}$ it follows that $T\_{min}\le T\_{max}$.

From our assumptions, $T\_{min}=\Omega(g(n))\implies T\_{min}\ge c\_1g(n)$. Also from our assumptions, $T\_{max}=O(f(n))\implies T\_{max}\le c\_2f(n)$.

Combining them together we get:

$c\_1f(n)\le T\_{min} \le T\_{max} \le c\_2g(n)$, which means that $f(n)\le \frac{c\_2}{c\_1}g(n)\implies f(n)=O(g(n))$

## Statement 2

Consider the following algorithm:

```
if lst[0] != 0:
    for x in lst:
        print(x)

```

And consider the inputs $I\_1:=\[0,1,2,3,...,n\]$ and $I\_2:=\[1,2,3,...n+1\]$. Clearly, the algorithm takes $O(1)$ time with input $I\_1$, but $\Omega(n)$ time with input $I\_2$. Obvoiusly, $n\neq O(1)$ and thus the statement is incorrect.

## Statement 3

Repeat the proof of statement 1. Note that also $T\_{avg}\le T\_{max}$ and thus the proof still holds.
> 0 votes

---
Tags: time-complexity, data-structures, proof-assistants
---


# Question
Title: Big-O notation for lower bound instead of Big-Omega
In the Wikipedia's Binary search tree, one can read

> Traversal requires $O(n)$ time, since it must visit every node.

Since it is question of a *lower* bound, shouldn't we write

> Traversal requires $\Omega$(n) time, since it must visit every node.

Is the $O(n)$ statement here even correct?

# Answer
If you consider the **problem** Tree traversal, then the correct answer is indeed:

> Traversal requires $\Omega$(n) time, since it must visit every node.

We are here talking about requirement and lower bound, as in "what is necessary".

If you want to talk about common **algorithms** for tree traversal, then it is true that they also have a complexity $O(n)$, which means that it is an upper bound in "what we can do".

However, since your question, the wikipedia page was modified and the current sentence does not really make any sense (basically "Tree traversal is $O(n)$. Since it is also $O(n)$, it is optimal.").
> 1 votes

# Answer
Traversal of a binary tree is $O(n)$, $\Omega(n)$, and $\Theta(n)$. All three are correct.

Big-O is an upper bound, Big-Omega is a lower bound, and Big-Theta is a "tight" bound.

Big-O notation is often used in a non-formal context even when a stronger claim (i.e. $\Theta(n)$) can be made. Big-Omega alone isn't the most helpful metric. We're often much more concerned with the upper bound.
> 0 votes

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


title: Big-O-notations and Small-o-notations

text:
# Question
Title: Big-O-notations and Small-o-notations
$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \\{1, \ldots, 6\\}$ whether for the ones given below functions $f\_i ∈ O(f\_j)$ or $f\_i ∈ o(f\_j)$ or neither of the two applies as $n → \infty$:

$f\_1 = \log(n),$

$f\_2 = \log(\sqrt n),$

$f\_3 = \log(n + \log(n)),$

$f\_4 = \sqrt{\log(n)},$

$f\_5 = \log\log(n^{\log(n)}),$

$f\_6 = \log\_2(n)$

$b)$ Show that for the functions $ f(n) = \log(n!) $ and $g(n) = n\log(n)$ it holds that $f ∈ O(g)$ and $g ∈ O(f)$. In fact, $f$ and $g$ are even asymptotically equivalent.

I am confused about the big $O$ and small $o$. When is $f\_{i} ∈ O(f\_j)$ and when is $f\_i ∈ o(f\_j)$? How to prove asymptotic equivalence?

# Answer
The usual definitions are the following (assuming $f$ and $g$ are positive):

* $f(n) \in O(g(n))$ if $f$ is eventually less that than some constant multiple of $g(n)$. In more mathematical terms $f(n) \in O(g(n))$ if there exists some $C \> 0$ and $N \in \mathbb{N}$ such that $f(n) \leq C \cdot g(n)$ for all $n \geq N$.
* $f(n) \in o(g(n))$ if $f$ is dominated by $g(n)$ as $n \to \infty$. Again, more formally, $f(n) \in o(g(n))$ if $\lim\_{n\to \infty} \frac{f(n)}{g(n)} = 0$. (Notice that this is stronger than Big-O)
* $f(n)$ and $g(n)$ are asymptoticaly equivalent if as $n$ grows $f(n)$ and $g(n)$ get very close to each other. The definition in terms of limits is that $\lim\_{n\to \infty}\frac{f(n)}{g(n)} = 1$.

Let's examine $f\_1$ and $f\_2$ in your example. If you calculate the limits of $\frac{f\_1(n)}{f\_2(n)}$ and $\frac{f\_2(n)}{f\_1(n)}$ as $n\to \infty$ you'll see that neither is equal to 0 so $f\_1 \not\in o(f\_2)$ and $f\_2 \not\in o(f\_1)$.

Now notice that for all $n \geq 2$ we have $\sqrt{n} \leq n$ and since $\log$ is increasing $f\_2(n) = \log(\sqrt{n}) \leq \log(n) = f\_2(n)$ so $f\_2 \in O(f\_1)$. To see that $f\_1 \in O(f\_2)$ just write $\log(n)$ as $\log(\sqrt{n}^2) = 2\log(n)$.

For part b) a hint is given in another answer (this is actually the "proper" way to prove such things) but another approach would be to use Stoltz-Cesaro to prove that $\lim\_{n\to \infty}\frac{\log(n!)}{n\log(n)}=1$ and deduct that this also implies that $f \in O(g)$ and $g \in O(f)$ using the limit definition.
> 1 votes

# Answer
1. How many pairs we can choose from $1$ to $6$? I think, we can find someone to help you in couple, but all is a lot of work.
2. Hint: we have

$$\left(\frac{n}{e}\right)^n \lt n! \lt e\left(\frac{n}{2}\right)^n$$
> 0 votes

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


# Question
Title: Floating Point Arithmetic with 3 bits mantissa
Find all values of $ x ∈ R $ such that x + 1 = 1 in floating point arithmetic with 3 bits mantissa.

How do we represent number 1 in floating point arithmetic with 3 bits mantissa I wonder? After that, I think we can subtract 1 on both side? I am a little confused about representations of numbers in floating point arithmetic with a specific number of bits in mantissa.

# Answer
> 1 votes
The problem is underspecified, but I'll assume IEEE 754 default behavior.

In IEEE 754, at least in space-constrained floating-point formats, a bit is saved by not storing the leading bit of the mantissa, which is always 1. So the representation of the number 1 would have 000 in the three mantissa bits.

The next largest representable number is 1.001 in binary (001 in the mantissa bits). The next smallest representable number I'll leave for you to figure out (it's not 0.111).

In IEEE 754, addition works by calculating the exact sum of the addends over the reals (infinite precision), then rounding to a representable floating-point number. In the default mode (round to even), you round to the nearest representable value, or if you're exactly halfway between representable values, the tie is broken in favor of the one with 0 in the least significant mantissa bit.

If $a$ is the next smallest representable number below 1, and $b$ is 1.001, then sums in the interval $\left\[\frac{a+1}2, \frac{1+b}2\right\]$ will be rounded to 1. (It's closed on both ends because round-to-even breaks the tie in favor of 1.) From there it's easy to answer the question.

---
Tags: floating-point
---


# Question
Title: How is the run time calculated in this insertion sort algorithm?
I am looking at this algorithm in CLRS page 26:

I am a novice when it comes to these things so please make your explanations as simple as possible.

For the cost column, does c1, c2, c4, etc denote a value the same way n does, or are they just labels? My understanding is an operation takes one time unit (such as j=2 is an operation that writes something once, therefore its one time unit) so does c1 mean one time unit?

Secondly, why does key=A\[j\] happen n-1 times?

Thirdly, line 3 is a comment therefore does not have an execution, so why does it happen n-1 times?

# Answer
One question at a time:

To answer your first question: $c\_1, c\_2, c\_4, c\_5$ etc. are all costs. You can also look at them as constant time, or $O(1)$ operations. In practice, the value of these costs themselves get absorbed with really big $n$ and are not considered when calculating asymptotic runtime. So for instance, when calculating the total runtime, we eventually upper bound all constants into a single constant, say $C$. But $c\_1, c\_2, c\_4$, etc. are there to help you understand the process of how the algorithm actually works. The more important part is how many times each step occurs. The constant is there to tell you that *each operation* takes place in constant time, and is obviously not dependent on the input size (meaning it doesn't have any $n$ associated with it). Now every line has some number of operations - that's given by a function of $n$ in the right column. Your total runtime is just the sum of the runtimes of each step $i$, which in turn is some constant, $c\_i$ multiplied by the number of times the operation is repeated. I hope that helped give you some clarity about how runtime actually works.

Now regarding your second question: Note carefully that the array goes from 2 to $n$. So number of iterations is $n-2+1=n-1.$

I think you're a bit confused about what contributes to the total runtime: Remember that line can be executed how many ever times, but its contribution to the total runtime is just its cost times the number of times it occurs. As it's commented, the cost is 0 so it does not contribute to the total runtime.
> 0 votes

# Answer
Let me answer step by step:

1. $c\_1, c\_2, c\_4$ etc. are costs of the operation in the corresponding line. For example $c\_1$ is the cost of **for**: one pass of this line costs $c\_1$.
2. $key=A\[j\]$ happens $n-1$ times, because we start from $2$ and $n=A.\text{length}$.
3. As it is commented, its cost is $0$.
> 0 votes

---
Tags: algorithms, asymptotics, sorting
---


# Question
Title: Error correction for windowed reads from cyclic tapes
I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for such "channel"?

Also will this problem be simpler if tape is not cyclic?

# Answer
> 1 votes
You mentioned in a comment that your messages are very short, only 7-10 bits long. Another option is to explicitly construct a code, with encoding and decoding done via a lookup table rather than by an algorithm or a formula.

For instance, suppose you have $K=7$-bit messages, that you will encode to a $N=30$-bit codeword that will be written onto the tape, and then you'll read $M=13$ bits starting from somewhere on the tape. Let $p(c)$ denote the set of $M$-bit sequences that could be read if $c$ was the codeword on the tape, i.e., $p(c)$ is the set of all $M$-bit sequences of $c$ (i.e., the $M$-bit prefixes of all cyclical shifts of $c$). Let $e(m)$ denote the encoding of the 7-bit message $m$; we'll construct $e$ below. Consider the following algorithm to choose a lookup table for $e$:

1. Let $S := \emptyset$.
2. For each $K$-bit message $m$:

a. Pick $c$ randomly from all $N$-bit sequences such that $p(c)$ has no overlap with $S$.

b. Let $e(m) := c$ and $S := S \cup p(c)$.

If the algorithm gets stuck, then go back to step 1 and restart. When this algorithm finishes, it will built up an encoder $e$, as a lookup table; you can then build up a decoder as follows:

3. For each $K$-bit message $m$:

* For each $s \in e(m)$, set $d(s) := m$.

One inefficient way to implement step 2a is with rejection sampling: pick $c$ randomly from $\\{0,1\\}^N$, compute $p(c)$, and check whether it has any intersection with $S$; if there's no intersection, then keep it, otherwise repeat with a new $c$. The probability that a randomly chosen $c$ is acceptable will be about $(1 - N / 2^{M-K})^N$ (or higher) in each step, so for some parameter choices this might be OK, but with others, it might be too slow.

Another (possibly faster) way to implement step 2a is to choose $c$ bit-by-bit. In more detail:

1. For $i:=1,2,\dots,N$:

* Pick $c\_i$ randomly.
    * If $c\_{i-M+1},\dots,c\_{i-1},c\_i \in S$:

    + Flip $c\_i$. If $c\_{i-M+1},\dots,c\_{i-1},c\_i \in S$, discard $c\_1,\dots,c\_i$ and go back to step 1, starting over from the beginning (starting with $i=1$).

A third way to implement step 2a, if $N$ is not too large, is to build a giant bitvector that stores the subset $T$ of $\\{0,1\\}^N$ of safe $N$-bit sequences, i.e., the subset $T = \\{c \in \\{0,1\\}^N : p(C) \cap S = \emptyset\\}$. Each time we add some value, call it $s$, to $S$ in step 2b, we can remove all $N$-bit values that contain $s$ as a substring from $T$. There will be $N \times 2^{N-M}$ such values to remove from $T$. Then, step 2a amounts to picking randomly from $T$. This will be inefficient if $N$ is large, though, and I'm not sure it has any advantages over the second way.

If you have a set value of $K$ and $N$, you'll probably have to experiment with different values of $M$ to see what is the smallest value for which you can construct an explicit code in this way.

# Answer
> 1 votes
I don't know if this problem has been studied, and I bet there will be better solutions, but I'll suggest a scheme that I suspect might work well enough, even if it's not optimal.

# Naive approach: brute-force decoding

I would bet that any erasure code would work, if combined with brute-force decoding. For decoding, I am imagining that a naive algorithm is to enumerate all possibilities for what the starting point was, decode under that assumption, and check whether it leads to a correct reconstruction that is consistent with that assumption (i.e., all symbols you read match). Heuristically, I would expect that typically there will be only one decoding that is consistent with the observed data. This might be a bit slow -- decoding might take $O(MN)$ time for many codes, because of need to try all $O(N)$ possibilities for the starting point -- but if that's acceptable, it should be something that's easy to implement.

For instance, you could use a Reed-Solomon code. To encode a message, you treat it as a polynomial $p(x)$ of degree less than $M$ (say, of degree $M-1-\lg N$) over some finite field (i.e., the bits of the message determine the coefficients of $p(x)$). Then, you write $p(\alpha^i)$ in the $i$th position on the tape, for $i=1,2,\dots,N$ (where $\alpha$ is a fixed element of the finite field). For each guess at where the read symbols might have started from, you can decode using polynomial interpolation. The entire procedure will take $O(MN \log M)$ time, to decode.

# Faster approach: rolling hash

Here is an alternative that should be me faster: it runs in linear time. I expect it will be close to optimal.

**Encoding algorithm.** Let $C$ be a small constant, to be chosen later. Let's suppose we have a message that is $M-C$ symbols long. We'll compute a Rabin-Karp rolling hash of the message, a hash that is $C$ symbols long, and append it to the message. Then, we'll repeat these $M$ symbols cyclically, to get a $N$-symbol word. That will be the codeword that is the encoding of the message. Encoding can be done in $O(N)$ time.

**Decoding algorithm.** Given an observed value $Y$ with $M$ symbols, we'll try all $M$ possibilities for cyclically shifting it to see which is correct. We can recognize when we have the correct shift because the last $C$ symbols will be the valid hash of the first $M-C$ symbols.

Naively, this decoding procedure would take $O(M^2)$ time. However, we can use the properties of the Rabin-Karp rolling hash to make decoding much more efficient. Let $H(x)$ denote the Rabin-Karp hash of $x$. Note that we can apply the Rabin-Karp rolling hash to $Y$ and learn $H(Y\_{1..i})$ for each $i$; we can compute all $M$ of these hashes in $O(M)$ time. From $H(Y\_{1..i-1})$ and $H(Y\_{1..j})$, we can compute $H(Y\_{i..j})$ in $O(1)$ time. Also, given two hashes $H(x\_1)$ and $H(x\_2)$, we can compute the hash $H(x\_1||x\_2)$ of the concatenation of $x\_1$ and $x\_2$ in $O(1)$ time. Thus, for any candidate cyclical shift of $Y$, we can compute the hash of the first $M-C$ symbols in $O(1)$ time, given the precomputed values $H(Y\_{1..i})$, and thereby check whether this candidate shift is correct (by comparing that hash to the last $C$ symbols of the shifted value). This decoding algorithm does an initial $O(M)$-time precomputation to compute all of the $H(Y\_{1..i})$ values, and then checks $M$ candidates, each of which takes $O(1)$ time, for a total decoding time of $O(M)$.

**Choosing parameters.** Lastly, I need to describe how we choose the constant $C$. I suggest choosing it so that it is very unlikely that any incorrect decoding will survive the hash-value check. Suppose each symbol is $b$ bits long. Then, a $C$-symbol hash is $bC$ bits long, and each incorrect candidate shift has a $1/2^{bC}$ chance of being wrongly accepted (by having the hash value match just by sheer chance). We test $M$ candidate shifts, so there is about a $M/2^{bC}$ chance that one of these is wrongly accepted. We might set as a goal that this chance should be at most $1/2^{50}$ (so that the chance of wrongly accepting an invalid message is less than the chance of being struck by lightning multiple times, and less than the chance of a cosmic ray hitting your computer and causing a bitflip error, i.e., negligibly small). This means we need $M/2^{bC} \le 1/2^{50}$, so it suffices to take $C = \lceil(50 + \lg M)/b \rceil$.

---
Tags: coding-theory, encoding-scheme, error-correcting-codes
---


# Question
Title: Are problems that are fractions of constraints of NP-complete problems also NP-complete?
We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,

* is there a Hamiltonian path of size $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
* is there an independent set of size $b$ in $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
* is there a clique of size $k$ in $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?

# Answer
There is no general rule that they necessarily need to be NP-complete in general.

For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.
> 1 votes

---
Tags: np-complete, np-hard, np, complexity-classes
---


# Question
Title: Different definitions of complexity class DP
I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see:

1. Difference between two NP problems; i.e., DP $:=\\{A\setminus B\ :\ A,B\in NP\\}$.
2. $\\{L\_1\cap L\_2\ :\ L\_1\in \text{NP},\ L\_2\in \text{co-NP} \\}$.

Complexity zoo gives the full form "Difference Polynomial-Time" for DP and states that it is equivalent to BH$\_2$. They give Definition 3 above as the definition of BH$\_2$. (So, according to complexity zoo, the two definitions are equivalent).

This answer says that the definition of DP changed over time. Is this true? If so, which definition is accepted nowadays? Is there a book or survey that explains the complexity class DP (at least as a section) ?

According to this source, NP $\subseteq$ DP. Doesn't that mean DP-hard problems are NP-hard and the other direction is wrong (the latter, unless there is a collapse in complexity classes)?

# Answer
Equivalence follows immediately from the definitions. The definition of $\setminus$ is:

$$A \setminus B = A \cap \overline{B}$$

where $\overline{B} = \Sigma^\* \setminus B$ denotes the complement of $B$. Now taking $L\_1=A$ and $L\_2=B$, it is trivial to prove that $L$ meets the first definition iff it meets the second definition, since $B \in NP$ iff $\overline{B} \in coNP$.
> 2 votes

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


# Question
Title: Prove that not all languages over unary alphabet are regular
Let the alphabet be $\\{0\\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument.

**My Ideas:**

The set of all languages over $\\{0\\}$ is uncountable. This can be proved with the diagonalization argument. So to prove the statement, I have to show that set of all regular languages over $\\{0\\}$ is countable. Not sure how to prove that.

# Answer
You can show this in many ways. For example, every language can be defined using a regular expression, and the number of regular expressions over a fixed alphabet is countable, since a regular expression is just a word over some alphabet.
> 4 votes

---
Tags: regular-languages, uncountability
---


# Question
Title: Is an integer variable constant or logarithmic space?
My lecturer says that a variable takes up one memory position in RAM. This is the slide in question:

But CLRS (Introduction to Algorithms by Cormen, end of page 23) says an integer is represented by $c\ lg\ n$.

Are both statements true? How can that be?

# Answer
> 21 votes
The random-access machine is a common model of computation, which is the model of choice when analyzing algorithms. In this model, memory consists of words of length $\Theta(\log n)$ bits, where $n$ is the length of the input (in bits). Therefore both your lecturer and CLRS are right.

# Answer
> 13 votes
In practical computer machines (aka, real-world computers) variables can be considered to be stored in "one" memory position, since the variable's size is fixed beforehand. For example, `int` is usually 32 bit long, and hence we can say it takes up "one" memory position of length 32 bits.

However, in the theoretical terms, integers do not have to be bounded between some arbitrary values we defined beforehand. That is, in the practical world integer with size 32 bit cannot store a value larger than $2^{32}-1$, but in the theoretical model it *can*. The caveat here, is that since we do not restrict the value of a variable, we need to actually consider how much memory it eats up. To save the number $n$ we need $\log(n)$ bits, hence what the book says is true, in the theoretical model.

# Answer
> 3 votes
In mathematics, an integer can get arbitrarily big. However, the bigger a number, the more digits are needed to write it down.

A memory cell in a computer has finite capacity. Therefore, a single cell can only store integers up to a certain size.

A single variable, stored in a single memory cell, can therefore hold integers only up to a certain size. That's why most programming languages limit the size of their integral data types. For instance, in Java, a variable of type `int` can hold integers up to $2^{31}$ (about 2 billion).

That is, the word "integer" means something slightly different in mathematics and programming. CLRS was talking about the mathematical integers, while your professor was talking about the integral data types provided by a computer. The former may get arbitrarily big, and require many memory cells, while the latter fit within a cell by definition.

# Answer
> 2 votes
**Integers take up logarithmic space** but this is usually of little interest during algorithmic analysis of real-world problems.

Here are things to keep in mind:

**1. Not the same $n$**

The $n$ often used in Big-O notation conventionally refers to the number of data items, rather than the possible range of those items. For example, if you are sorting 50000 integers and they are all smaller than 2 billion, that's $n=50000$ and $m=2000000000$. The input data will consume $O(n\\,\text{log}\\,m$) space. But often this will just be expressed as $O(n)$ because in the real world it's rarely important to consider mind-bogglingly-huge integers which is what it would take to make a serious difference here.

**2. Most algorithms are comparably affected by datum size**

One of the main reasons to perform asymptotic analysis is to compare two algorithms which solve the same problem. Most important classes of algorithm, such as sorting and searching and graph algorithms (e.g. shortest-path etc.) and optimisation algorithms, generally have the same asymptotic complexity whether they are operating on say 32 or 64 bits.

**3. There are exceptions**

If we consider things like very large prime number testing, the size of the primes can be crucial to accurately characterise an algorithm's behaviour.

Also, in abstract or theoretical environments it is necessary to be more rigorous about such things. Turing Machines typically have a fairly small alphabet (i.e. "variables" can hold a quite small range of values) so it is impossible to hand-wave away the size of an `int`.

**4. Many languages use variable-sized integers by default**

In Python, Ruby, Haskell and Raku, an integer is automatically allocated as much memory as it needs. You can multiply `999999999 * 999999999 * 999999999 * 999999999` in any of these languages and get a 100% precise result—they are not floating-point numbers. So if you create an array of really big integers you will see logarithmic memory usage. (CPU operations will also increase if the numbers are larger!)

**5. In practice, integer size (or numerical precision generally) is usually about machine selection, not algorithm selection.**

If you are trying to process 20-digit numbers on an 8-bit computer, you are using the wrong machine. You will experience a blowout of both RAM and CPU operations. The solution is not a change of algorithm but a change of hardware.

**6. Sparse integers can usually be collapsed with e.g. hashing**

Algorithms that require several copies of very large integers to be stored can be modified to save memory by hashing the datum or using indices/pointers. This step does not increase big-O performance complexity (although it does slow things down.) Figuring out the right trade-off to make is not really something that can be captured in a simple big-O formula.

# Answer
> 0 votes
A variable refers to exactly one memory position, where "one memory position" is typically 64 bits on a modern computer.

When you want to store something bigger in a variable, you store a *reference* to the value in the original memory position. This reference can be used to find a sequence of memory positions that contain the actual value.

These extra memory positions do *not* belong to the variable, but to the value stored.

---
Tags: asymptotics
---


# Question
Title: Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $
For the following language, write grammar independent of the text.

$$\\{a^i b^j: j \< 2i \text{ and } j \ne i \\} $$

I want a hint to start solving this problem. Where should I start?

# Answer
> 1 votes
If $j \neq i$ then either $j \< i$ or $j \> i$. Hence you can write your language as $$ \\{ a^i b^j : j \< i \\} \cup \\{ a^i b^j : i \< j \< 2i \\}. $$ It suffices to find a grammar for each of these two languages. Such questions have been asked and answered on this site.

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


# Question
Title: Grammar for $\{ (n_a(w) - n_b(w)) mod\ 3 = 2 \} $
What is the grammar for $$\\{ (n\_a(w) - n\_b(w)) mod\ 3 = 2 \\} $$

please guide me with this. I tried to draw DFA to find grammar but I can't.

any help is much appreciated.

# Answer
Start from the initial state $q\_0$: the current value of $(n\_a(w) - n\_b(w)) \pmod 3$ is 0. Next, if you read $a$ in $q\_0$, then the current value of $(n\_a(w) - n\_b(w)) \pmod 3$, which is 0, becomes 1, so go to $q\_1$, while if you read $b$, the value of $(n\_a(w) - n\_b(w)) \pmod 3$ becomes 2, and so go to $q\_2$ (which will be a final state). Then you can do the same for $q\_1$ and $q\_2$: in $q\_1$, if you read $a$, then the current value of $(n\_a(w) - n\_b(w)) \pmod 3$, which is 1, becomes 2, so go to $q\_2$, and so on...

In conclusion: when you read $a$ the value of $(n\_a(w) - n\_b(w)) \pmod 3$ is incremented by 1 (modulo 3, of course), while if you read $b$ it is decremented by 1, and in state $q\_i$ the current value of $(n\_a(w) - n\_b(w)) \pmod 3$ is $i$.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: An algorithm to check if two DFA are disjoint
What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.

# Answer
Construct the intersection DFA of both DFA's. Then, check if there is a path from the starting state to any end state.

If there is a path, then the two DFA's are not disjoint. If there isn't, then they are.
> 0 votes

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


# Question
Title: SAT solvers for use in $P^{NP}$ and $NP^{NP}$
The original question I am answering:

> Can you use SAT solvers to solve problems complete in $\Sigma\_2^P,\Pi\_2^P,\Delta\_2^P$?

My first thought:

* Venn Diagrams show that the PH encloses NP, but does not equal NP. Therefore, there should be some problems that cannot be solvable using SAT?

My second thought:

* To be able to use a SAT solver on one of those PH classes, it would imply that they are reducible to SAT, and so $\Sigma\_2^P = \Pi\_2^P = \Delta\_2^P = \mathsf{NP}$.

This would imply that PH collapses to NP, which we know not to be true.

Are these thoughts correct?

# Answer
> 2 votes
We don't know that PH doesn't collapse to NP. We don't even know that PH doesn't collapse all the way to P.

The best you can say is that you can use SAT solvers to solve problems in one of these classes iff PH collapses to NP.

# Answer
> 2 votes
If you treat a SAT solver as being reasonably efficient and you can invoke it multiple times, then you can solve arbitrary problems in $P^{NP}$ (trivially; SAT lets you solve any problem in NP, and $P^{NP}$ is exactly the class of problems you can solve by invoking an oracle for a NP-complete problem multiple times).

---
Tags: complexity-theory
---


# Question
Title: Why is this youtuber applying comparing two functions with O(n^2), by applying a contant to one of the functions?
Here is the video in question:https://www.youtube.com/watch?v=BpiMRyWoDu0&t=131s

F(n) and g(n) are both equal to each other since they both have a time complexity of n^2

What's the point of applying the constant c to g(n) to make it 2n^2? What is this trying to show us?

Additionally, why does the inequality include 'equal to'? When will 2n^2 ever be equal to n^2 + n + 3?

Further more, why has he written n \>= 4? Where did the 4 come from? I understand why he wrote n \>= 3 because n(n-1)is the same as n for time complexity purposes, therefore this becomes n \>= 3

# Answer
Look up the definition of big-O. It states that $f=O(g)\iff \exists c\>0:\exists n\_0\in\mathbb{N}:\forall n\>n\_0:f(n)\le cg(n)$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous
> Prove that the following grammar is unambiguous:
>
> $$X \to aX | Y$$
>
> $$Y \to Yab | b$$

I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?

# Answer
First, figure out what the language is.

Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous?

Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect the resulting word?
> 4 votes

# Answer
The main observation is that every word generated by $Y$ starts with $b$.

Consider a word $w$. If it starts with $a$, it must have resulted by applying the rule $X \to aX$. Otherwise, it must have resulted by applying the rule $X \to Y$. In other words, if $w = a^n b z$, then the derivation must start by applying $n$ many times the rule $X \to aX$, and then deriving $bz$ from $Y$. We can determine the entire derivation given $|bz|$; details left to you.
> 1 votes

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


# Question
Title: What happens when we increase or decrease capacities in the minimum flow?
I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.

* If in a network we **increase** the capacity of an edge in the minimum cut, the maximum flow gets increased.
* If in a network we **decrease** the capacity of an edge in a minimum cut, the maximum flow gets decreased.

*My thoughts:*

* **Increase** case: I think this is not always true as increasing the minimum could result in what was originally the $2^{nd}$ min flow becoming the lowest value and thus the new max flow. Hence because it isn't always true, the answer is false. This question indicates that max flow needs to be recalculated.
* **Decrease** case: I think this is true because we already have the minimum cut so lowering the minimum brings us to a new minimum. Hence the answer is true.

Is my reasoning correct or is there something I misunderstood.

# Answer
> 1 votes
**Case 1**, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the **claim is false.**

**Case 2**, let $C$ be a minimum cut with cost $w(C)$. Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(C)$. Since $C$ is still a *cut* in the graph, but $w'(C)$ is smaller than any other minimum cut, the **claim is true**.

---
Tags: linear-programming, network-flow
---


# Question
Title: Is at least one of L and L complement Turing recognizable
Let the alphabet be {0,1}. Is it true that for every language over this alphabet at least
one of L and L\_complement is Turing-recognizable

# Answer
> 1 votes
No, try to think of a counting argument (i.e, the size of each class) in the following way:

There are $2^{\aleph\_0}$ possible words in the language, hence $2^{2^{\aleph\_0}}$ total languages. However, the number of turing machines is bounded by the total possible number of words (since you can encode a TM as a string), hence there are at most $2^{\aleph\_0}$ TMs, and thus we get that $|RE| \le 2^{\aleph\_0}$. Follow the definition of $co-RE$, to see that the same argument gives $|co-RE| \le 2^{\aleph\_0}$ as well. Thus, $|RE\cup co-RE| \le 2^{\aleph\_0}$ as well.

Thus $|RE\cup co-RE|\le 2^{\aleph\_0}\<2^{2^{\aleph\_0}}=|P(\\{0,1\\}^\*)|$, and thus there must be some $L\in P(\\{0,1\\}^\*)\setminus (RE\cup co-RE)$ as you asked.

In fact, this shows there are *waaaaay* more languages that aren't RE or co-RE than languages that are.

# Answer
> 0 votes
For a practical example of such a language, take a look at the following language:

$L = \\{\<M\_1, M\_2, w\> | M\_1 \text{ halts on } w \land M\_2 \text{ doesn't halt on } w\\}$

It is not in $co-RE$ since the halting problem isn't (there is a reduction from the halting problem to this problem)

And for a similar reason it is not in $RE$ (the complement of the halting problem is not in $RE$, and there is a reduction from $L$ to it)

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


title: Maximum weighted subgraph

text:
# Question
Title: Maximum weighted subgraph
**Problem:** Given a graph G with positive integral weights on nodes as well as edges, find an induced subgraph H with maximum total weight per node, i.e., the goal is to maximize $$ \frac{ \sum\_{e \in H}w(e) + \sum\_{v \in H} w(v) }{|V(H)|}.$$

If you allow negative weights, then it is NP-hard (easy reduction from Clique). I have a strong feeling that the above is not NP-Hard.

I would love to have some first-thoughts on the above, if not a full-fledged optimal algorithm. Does it seem to be NP-Hard? What is the closest known problem -- my thoughts were Prize Collection, Clique -- but both seem much harder.

# Answer
The Dense Subgraph Problem (thanks @PalGD) is a special case of the above problem--with no node weights and unit edge weights. See the solutions for the dense subgraph problem here. These solutions (LP and 2-approximation Greedy) easily generalize to the above problem (generalizing LP requires a bit of understanding/effort, but generalizing Greedy is trivial).
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation >
In the paper linked below by Knuth and Bendix, theorem 1:

> The set of all pure words is well-ordered by the relation '$\>$'

has a proof that I can't seem to follow despite staring at it all day. I can't even decipher what the notation is trying to represent.

So, we have four fixed sequences:

* An infinite sequence of variables $v\_1, v\_2, v\_3, ...$ etc. (not relevant for Theorem 1)
* A finite sequence of operators $f\_1, f\_2, f\_3, ..., f\_n$
* A finite sequence of degrees $d\_1, d\_2, d\_3, .., d\_n$
    + (i.e. degree of $f\_4 = d\_4$)
* and a finite sequence of weights $w\_1, w\_2, w\_3, ..., w\_n$
    + (i.e. weight of $f\_4 = w\_4$)

A word is then defined inductively as either a variable alone or an operator followed by an appropriate number of other words depending on the degree of said operator.

A 'pure word' is a word with no variables and the weight of a pure word, $\alpha$ is defined as follows:

* $w(\alpha) = \sum\_j w\_jn(f\_j , \alpha)$ where $n(f\_j, \alpha)$ is the number of occurrences of $f\_j$ in the word $\alpha$

Finally the relation $\>$ that orders all pure words that is proved to be well-ordered is defined as:

$ \alpha \> \beta $ if and only if:

* 1. $w(\alpha) \> w(\beta) $
    + (I'm assuming the '$\>$' here is strict integer inequality and not the same '$\>$' that is being defined.)
* 2. $w(\alpha) = w(\beta)$ and $\alpha = f\_j\alpha\_1 ... \alpha\_{dj}$, $\beta = f\_k\beta\_1 ... \beta\_{dk}$, and either:
    + 2a) $ j \> k$; or
    + 2b) $j = k$ and $\alpha\_1 = \beta\_1,..., \alpha\_{t-1} = \beta\_{t-1}, \alpha\_t \> \beta\_t$, for some $t, 1 \leq t \leq d\_j$

Finally on page 266, for the proof that $\>$ is well-ordered the exposition states:

> Now let $\alpha$ be a pure word with $n\_j$ symbols of degree $d\_j$. It is easy to prove inductively that:
>
> $n\_0 + n\_1 + n\_2 + ... = 1 + 0.n\_0 + 1.n\_1 + 2.n\_2 + ...,$
>
> i.e. $n\_0 = 1 + n\_2 + 2n\_3 + ...$

I don't know whether it really is 'easy' to prove the above because I don't really know what the above *is*.

I'm fairly sure symbols are just operators in this context of pure words but if $n\_0, n\_1,$ etc. are symbols then how are they being summed? Does $n\_0$ in the above actually represent $w(n\_0)$. That doesn't seem to provide any clarity as to what is going on with the proof.

I've reread the first four pages of the paper multiple times and nothing seems to be getting any clearer:

https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf

Any insight would be appreciated.

# Answer
> Now let $\alpha$ be a pure word with $n\_j$ symbols of degree $d\_j$. It is easy to prove inductively that:
>
> $n\_0 + n\_1 + n\_2 + ... = 1 + 0.n\_0 + 1.n\_1 + 2.n\_2 + ...,$
>
> i.e. $n\_0 = 1 + n\_2 + 2n\_3 + ...$

I think there is a small mistake here, since $n\_j$ should be considered as the number of symbols of degree $j$ and not of degree $d\_j$ in $\alpha$.

> $n\_0 + n\_1 + n\_2 + ... = 1 + 0.n\_0 + 1.n\_1 + 2.n\_2 + ...,$

In this formula, the left side can be interpreted as "the total number of symbols", and the right side can be interpreted as "the first operator symbol plus the total number of arguments". Intuitively, those quantities are indeed equals.

If we correct the mistake, then it is somewhat easy to prove by induction:

* if $\alpha$ does not contain any operator of degree $\geq 1$, then we have $\alpha = f()$, where $f$ is an operator of degree $0$ (that could be considered as a constant). We have then $n\_0 = 1$, and $n\_i = 0$ for any $i \geq 1$. The property $n\_0 = 1 + n\_2 + 2n\_3 + ...$ holds;
* if $\alpha = f(\alpha\_1, …, \alpha\_d)$ where $f$ is an operator of degree $d \geq 1$ and the $\alpha\_i$ are pure words that verify the property we want to prove, then we get:

+ $n\_k(\alpha) = \sum\limits\_{i=1}^d n\_k(\alpha\_i)$ if $k \neq d$;
    + $n\_d(\alpha) = 1 + \sum\limits\_{i=1}^d n\_d(\alpha\_i)$.

Therefore we get:

$\begin{array}{rcl} n\_0(\alpha)& = &\sum\limits\_{i=1}^d n\_0(\alpha\_i) \\ & =& \sum\limits\_{i=1}^d\left(1+\sum\limits\_{k=2}^{\infty}(k-1)n\_k(\alpha\_i)\right)\\ & = & d + \sum\limits\_{k=2}^{\infty}(k-1)\sum\limits\_{i=1}^dn\_k(\alpha\_i) \\ & = &d + (d-1)(n\_d(\alpha) - 1) + \sum\limits\_{k = 2,k\neq d}^{\infty}(k-1)n\_k(\alpha)\\ & = & 1 + \sum\limits\_{k = 2}^{\infty}(k-1)n\_k(\alpha)\end{array}$

And that proves the formula by structural induction on pure words. Please note that the previous sums can be interverted because the infinite sum is, in fact, finite (since $n\_k(\alpha\_i) = 0$ for $k$ big enough).

The fact that $n\_j$ is the number of symbols of degree $j$ and not of degree $d\_j$ is somewhat confirmed after the statement: "since each nullary operator has positive weight, we have $w \geq n\_0$". Why? Because $\alpha$ contains $n\_0$ occurrences of nullary operators, which are supposed to be of positive weights. The statement would make no sense if $n\_0$ was the number of symbols of degree $d\_j$ (since $w\_j$ could be zero).
> 1 votes

---
Tags: algorithms, proof-assistants, automated-theorem-proving, order-theory
---


# Question
Title: How many time and space units does this algorithm take?
This is what I counted but I know I'm wrong since my conclusion is not in the choices:

* t = time unit
* s = space unit
* y=1 : 1t & 1s
* for 0 \<= i \<= N : Nt & 1s
* y=y\*i : 2 reads, 1 write, 1 multiplication therefore 4 time units, the for loop is thus 4N time units
* total time = 4N+1
* total space = 2 (because there are only two variables that need to be stored)

# Answer
> 1 votes
## My thoughts about the question

Honestly speaking, this question is *really weird*. Usually when you ask about the time and space complexity, you mean it in big-O or other asymptotical notation. Not the actual literal number of steps the algorithm takes, since this can change depending on the hardware you are using and a lot of other factors.

So the fact that most answers are with the same asymptotics, it makes absolutely no sense!

---

## My answer to the question

The answer depends on what you define a "time unit" and "space unit". Under normal circumstances, you would say this algorithm takes $\Omega(N\log(N))$ time, and would need $\Theta(N\log(N))$ space as well.

The explanation for that comes from the fact that $y$ at the $k$'th iteration is computed to be $k!$ ($k$ factorial). Saving in memory the value $N!$ needs $\log(N!)=\Theta(N\log(N))$ space, and thus also the running time must be **at least** $\Omega(N\log(N))$.

An upper bound for the running time depends on the algorithm used for multiplication.

---

## Your answer to the question

Assuming multiplication takes $O(1)$ time, and a single unit of space is defined as a single variable, your solution is correct. This also demonstrates the problem of not using big-O notation, since your answer is correct however it is not one of the listed answers.

# Answer
> -1 votes
I didn't realise the system will give me an answer:

---
Tags: asymptotics
---


# Question
Title: Expressing division in relational algebra in terms of other operations
So, I've been conferred upon the opinion that:

> Union, difference, cross product, selection, projection form the "complete set of relational operations". That is, any other relational operation can be expressed as a combination of these (excluding domain manipulation operations like aggregate functions I assume).

*Question 1*: Is that true ?

*Question 2*: If yes, can someone help me break down division in terms of those operations.

# Answer
> 7 votes
Let $R(A,B)$ and $S(B)$ be two relations. Division should find all values of A in R that are connected with all values of B (in S). Think $AB\div B=A$.

Question 1: Yes. $R\div S=\pi\_A(R)-\pi\_A(\pi\_A(R)\times S-R)$

Question 2:

$\pi\_A(R)\times S$ : this contains all possible AB pairs.

$R$ : this contains the actual AB pairs.

For the values of A that are connected to all values of B, after we do the difference, those will be gone. In the difference $\pi\_A(R)\times S-R$ there are only values of A that are NOT connected to all B.

The rest is obvious.

# Answer
> 2 votes
> Q 1: Is that True?

No. It is the conventional minimal set, based on Codd's 1970 paper "Relational Completeness of Data Base Sublanguages". But Codd was wrong. He left out RENAME. Even to define Natural Join in terms of cross product needs RENAME. (Compare that Boolean Algebra's minimal set is usually taken as Union, Difference, Intersection. To achieve Intersection in RA, you can take it as a special case of Natural Join.)

Why did Codd miss out RENAME? Because his claim for completeness was based on the Relational Calculus/language ALPHA; and that had a special way to deal with attribute naming. (Very similar to the SQL dot-prefix `<table>.<column>` format.) The RA doesn't have that formalism (and no way to translate that from RC to RA). Furthermore that formalism is not extensible to nested operators `((A UNION B) MINUS C) TIMES D`. (How do you refer to an attribute in the result from the left operand of TIMES, noting that A, B, C must have the same attributes?)

Note there's nothing 'sacred' about any particular minimal set of operators. You could define EXTEND in terms of RENAME. Or you could define RENAME in terms of EXTEND (and projection).

Another possible minimal set is: Selection, Projection, Rename, Natural Join, Union, Difference.

> Q 2: Division

Curiously, Codd's very early writings did include Division as a primitive. He later realised it could be defined in terms of the others. @dimm's answer is good -- providing `S`'s attributes are a subset or `R`'s -- which is the usual presumption. But beware: there's lots of different operators called "Relational Division": Codd's Divide, Todd's Divide, the Great Divide, the Small Divide, ... \[See Chris Date's Chapter 12 in 'Database Explorations'\] They differ in how they handle corner cases like one of the relations being empty, or having no attributes in common, or having all attributes in common.

Before you try to use a Divide, I'd stop and carefully express what condition you're trying to apply in your query. Perhaps you don't need a Divide at all. Perhaps expressing your query using projection, difference, cross product will actually be easier to understand.

(I think Relational Division is one of those topics that instructors use to torture their students for sheer pedantry/no learning gain.)

# Answer
> 0 votes
I derived this solution using one particular example only, so it might not be full proof. Let R(A,B) and S(A), we want to do R÷S.

1. take T1=R(B) using project operator
2. take T2=S(A) X T1 (cross product)
3. take T3=T2-T1 /*we have the tuples not to be included in result*/ /*Scheme of T3 is (A,B)*/
4. take T4=T3(B) using project operator
5. Result= T1-T4 Thus we implemented Division operator using Project, Difference and Cross product which are all present in Minimal set of operators

---
Tags: relational-algebra
---