title: Find The missing number in range [0,n]

text:
# Question
Title: Find The missing number in range [0,n]
Given Array $A$ of size $n$ that contains all the integer values $\[0,n\]$ except one.

In this question we assume that the time we need to check one bit $j$ in number $A\[i\]$ is $O(1)$,and to check the number $A\[i\]$ is $O(\log n)$.

Find an algorithm that finds the missing number in $O(n)$.

So creating a trivial counter array and searching for a 0 count wouldn't help - it would be $O(\log n)$.

I also thought about counting the bits and finding the missing one, but that wouldn't help either.

# Answer
Compare all the Least Significant bits, and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... \< 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.
> 7 votes

# Answer
Perhaps I am missing the point but this seems trivial.

```
var previousBit = 1;

for index = 0 to n -1 // -1 because the array is one short of n.
   begin
   var currentBit = A[index].bit(0)
   if(currentBit == previousBit)
       break;
   else
       previousBit = currentBit
   end

print "missing number is ", index

```

Assuming A\[index\].bit(0) gives the zero-th bit of the number at the array position index.

This is plainly O(n)

This would be based on the observation that the least significant bit of the number toggles as you increase from 0 to n, and where it doesn't you have found the missing number.
> 0 votes

# Answer
This is similar to NightRa's answer, but I believe they were missing a few details. Simply following which Least Significant Bits there are *less* of will not get you to the correct solution.

You need to follow which bit has fewer than you *expect*.

For example, let's say $n = 6$ and $A = \[0, 1, 3, 4, 5, 6\]$.

Our bits are:

```
0 - 000
1 - 001
3 - 011
4 - 100
5 - 101
6 - 110

```

Our least significant bits are `[0, 1, 1, 0, 1, 0]`, which have an equal amount of both `0` and `1` bits. However, since we know $n=6$, from $0$ to $6$ we *expect* there to be 4 even numbers (0, 2, 4, 6) and 3 odd numbers (1, 3, 5).

This means, of the least significant bits, we expect there to be 4 even bits (`0`) and 4 odd bits (`1`). We can see there are *not* 4 even bits, but rather only 3, so we recurse on those, going to the next least significant bit.

---

It's more clear to me how we can determine the *expected* number of bits if we start with the Most Significant Bits rather the Least Significant. The most significant bits will give us a range (`[0, 3]` for 0 and `[4, 6]` for 1 in the prior example), where as the least significant will give us even or odds (`[0, 2, 4, 6]` for 0 and `[1, 3, 5]` for 1 in the prior example) which will be trickier when you recurse.

### Algorithm

For simplicity I'm assuming we can simply "index" into the value in $A$ to determine the value of it's $i$th bit. For example if $A = \[5\]$ then $A\[0\]\[0\] = 1$, $A\[0\]\[1\] = 0$ and $A\[0\]\[2\] = 1$.

```
find_missing(n, A):
    # number of bits in n
    bits = floor(log2(n) + 1)
    return find_missing_recursive(bits, 0, n, A)

find_missing_recursive(i, start, end, A):
    if start = end:
        # We've found our missing value
        return start

    expected_0s = 2^(i - 1)
    expected_1s = (end - start) - expected_0s + 1

    actual_0s = 0
    actual_1s = 0
    A_0s = []
    A_1s = []
    for j in [0, 1, ..., length(A) - 1]:
        if A[j][i] = 0:
            actual_0s += 1
            A_0s.append(A[j])
        else:
            actual_1s += 1
            A_1s.append(A[j])

    if actual_0s < expected_0s:
        # Recurse on the 0s
        return find_missing_recursive(i - 1, start, start + expected_0s - 1, A_0s)
    else:
        # Recurse on the 1s
        return find_missing_recursive(i - 1, start + expected_0s, end, A_1s)

```

### Example

Let $n = 6$ and $A = \[3, 0, 2, 6, 4, 1\]$ (5 is missing).

We can now walk through the algorithm:

```
find_missing(6, [3,0,2,6,4,1]):
    # number of bits in n
    return find_missing_recursive(3, 0, 6, [3,0,2,6,4,1])

find_missing_recursive(3, 0, 6, [3,0,2,6,4,1]):
    expected_0s = 4
    expected_1s = 6 - 4 + 1 = 3

    actual_0s = 4
    actual_1s = 2
    A_0s = [3,0,2,1]
    A_1s = [6,4]

    # Recurse on the 1s
    return find_missing_recursive(2, 4, 6, [6,4]):
               expected_0s = 2
               expected_1s = 2 - 2 + 1 = 1

               actual_0s = 1
               actual_1s = 1
               A_0s = [4]
               A_1s = [6]

               # Recurse on the 0s
               return find_missing_recursive(1, 4, 5, [4]):
                          expected_0s = 1
                          expected_1s = 1

                          actual_0s = 1
                          actual_1s = 0
                          A_0s = [4]
                          A_1s = []

                          return find_missing_recursive(0, 5, 5, []):
                                     return 5

```

Thus `5` is returned which is indeed the missing value.

### Analysis

The complexity for `find_missing_recursive` is:

$$T(n) = \begin{cases} c & n = 1\\ T(2^{\lceil \log\_2(n) - 1\rceil}) + c n + c \log\_2 n & n \> 1 \end{cases}$$

If we assume $n = 2^k$ this becomes simpler:

$$T(n) = \begin{cases} c & n = 1\\ T(n / 2) + c n + c \log\_2 n & n \> 1 \end{cases}$$

This then evaluates to:

$$\begin{align} T(n) &= T(n / 2) + c n + c \log\_2 n\\ &= T(n/4) + c 3n/2 + 2c \log\_2 n - c\\ &= T(n/8) + c 7n/4 + 3c \log\_2 n - 3c\\ &= \vdots\\ &\< T(1) + 2cn + c(\log\_2n)^2 - c2^{\log\_2n}\\ &= cn + c(\log\_2n)^2 + c\\ &= O(n) \end{align}$$

You can also prove this bound by induction.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Find the shortest path that goes through an even number of red edges
I'm looking for an algorithm for the problem:

"Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the shortest (lightest) path which includes an even number of red edges, that goes from S to any vertex v."

The solution I thought about was, why not take the original Graph G(V,E) and create (I'm not quite sure if I can say "given" though I think it is) a sub graph which will include only the red edges, let's say Red(V',E'), intersect those two, so now I will have a new graph say G' which includes only the red edges.

And on that graph I will use dijkstra algorithm in order to find the shortest path.

The problem is it can ofc make some edges un-reachable so it will return there's no such path, while there might be a path if added some blue edges. I'm not quite sure how to go around it in order to get the perfect solution.

# Answer
Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). So just run any shortest-paths algorithm on this new "doubled" graph and keep only the shortest paths that both start and end in $A$.

More formally, let $v\_A$ and $v\_B$ be the two copies of $v$ that appear in $A$ and $B$, respectively. For each original edge $(u,v)$,

* if $(u,v)$ is blue, the new graph will have edges $(u\_A, v\_A)$ and $(u\_B, v\_B)$.
* if $(u,v)$ is red, the new graph will have edges $(u\_A, v\_B)$ and $(u\_B, v\_A)$.

Note that this transformation only works because the edge weights are positive. Otherwise you could do funky things like traverse a negative edge twice (once within $A$ and once within $B$) to achieve lighter paths in the doubled graph.
> 7 votes

# Answer
An alternative (but essentially equivalent to @SamWestrick's) way of thinking about it is to run Dijkstra on the original graph but keeping track of two parameters for each vertex: the shortest path with an even number of red edges found so far, and the shortest with an odd number.

Here's a more precise description of the algorithm. For each vertex $v$, store values $d\_{\mathrm{even}}(v),d\_{\mathrm{odd}}(v)$. Initialise these by setting $d\_{\mathrm{even}}(S)=0$ and all others (including $d\_{\mathrm{odd}}(S)$) to $\infty$. For each vertex have two flags $f\_{\mathrm{even}},f\_{\mathrm{odd}}$ which determine whether the $d$ values are final or not. Initialise all flags to `False`.

Now, iteratively do the following. Find a choice of $\mathrm{par}\in\\{\mathrm{even},\mathrm{odd}\\}$ and $v\in V$ such that $f\_{\mathrm{par}}(v)$ is `False` and $d\_{\mathrm{par}}(v)$ is finite and as small as possible (obviously you can use a priority queue to make this efficient). Write $\mathrm{\overline{par}}$ for the opposite of $\mathrm{par}$.

Now set $f\_{\mathrm{par}}(v)$ to `True`. For each $vw\in E$,

* if $vw$ is blue, update $d\_{\mathrm{par}}(w)$ to $\min\\{d\_{\mathrm{par}}(w),d\_{\mathrm{par}}(v)+\ell(vw)$;
* if $vw$ is red, update $d\_{\mathrm{\overline{par}}}(w)$ to $\min\\{d\_{\mathrm{\overline{par}}}(w),d\_{\mathrm{par}}(v)+\ell(vw)$.

Continue to do this until there are no finite distance values for which the corresponding flag is false. (It may be that there are some values which remain infinite, because there is no path from $S$ of the required parity.)

If you need to find the paths, not just the lengths, you similarly need two different variables keeping track of the predecessor of each vertex, which are updated when the corresponding distances are.

This really is exactly the same as @SamWestrick's elegant answer, though: the "odd" variables are just another way of thinking about the variables for the "B copy" of each vertex.
> 3 votes

---
Tags: algorithms, graphs, dijkstras-algorithm
---


# Question
Title: Size of order-preserving minimal perfect hash family
Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $M\subset U$ of size $m$ has at least one function $h\in H$ which is an over preserving minimal prefect hash. It is shown in \[1,2\] that for every $(U,m)$-OPMPHF $H$ obeys:

$$H=m! \cdot \left.\binom{u}{m}\middle/\left(\frac{u}{m}\right)^m\right. $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $\log\_2 |H|$ bits.

In particular, if $m=3,u=8$, we have that $|H|\geq 17.7$.

However, I think I can create as set of $|H|=6$ functions for such family. For every $2\leq i\leq 7$ we define $f\_i(x)$ to be equal $1$ if $x\<i$, equal $2$ if $x=i$ and equal $3$ if $x\geq i$. Every function $f\_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f\_i$.

Do I miss something in my analysis?

\[1\] Havas and Majewski, Optimal algorithms for minimal perfect hashing

\[2\] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984

# Answer
Reference \[1\] defines order-preserving as follows:

> A hash function is *order preserving* if it puts entries into the hash table in a prespecified order.

In your case, this means that given any three elements $x,y,z \in \\{1,\ldots,8\\}$, you want there to be a hash function which maps $x$ to $1$, $y$ to $2$, $z$ to $3$.

In particular, it need not be the case that $x \< y \< z$.

If you add the assumption that $x \< y \< z$, then you can remove the $m!$ factor in the lower bound on $H$. The new lower bound states $H \geq 2.95$, that is, $H \geq 3$, which is not tight.
> 1 votes

---
Tags: hash
---


# Question
Title: Having trouble understanding a proof of Mahaney’s theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.

I am not sure why $a’$ cannot be in between $w\_i$ and $w\_j$ in Case 1, and also why $a’$ cannot be in between $w\_0$ and $w\_1$ in Case 2.

Can anyone give me some explanation?

# Answer
Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.

For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is satisfiable and $a(\varphi) \leq w$ (in lexicographic order).

Since $B$ is in NP, there is a polytime reduction $f$ such that $(\varphi,w) \in B$ iff $f(\varphi,w) \in A$. Since $f$ runs in polytime, $|f(\varphi,w)|$ is polynomially bounded, say $|f(\varphi,w)| \leq N$ (where $N$ depends on $n = |(\varphi,w)|$). Since $A$ is sparse, we can bound $$ |\\{f(\varphi,w) : w \text{ is an assignment for $\varphi$}\\} \cap A| \leq \sum\_{k \leq N} k^c =: m, $$ where $m$ is also polynomial in $n$.

We will show how to use $f$ to decide SAT in polynomial time. Given a CNF $\varphi$, we will assume that $\varphi$ is satisfiable, and will attempt to verify it. That is, under the assumption that $\varphi$ is satisfiable, we will run an algorithm that is guaranteed to find a satisfying assignment for $\varphi$. If it succeeds, we can conclude that $\varphi$ is indeed satisfiable (since we have found a satisfying assignment). If it fails, then $\varphi$ couldn't have been satisfiable.

We will use $f$ to determine $a(\varphi)$ using some sort of binary search. The idea is to pick $m+1$ many assignments $w\_1,\ldots,w\_{m+1}$, equally spaced in assignment space, and to calculate $f(\varphi,w\_1), \ldots, f(\varphi,w\_{m+1})$. We now consider two cases:

* $f(\varphi,w\_i) = f(\varphi,w\_j)$ for some $i \< j$. If $f(\varphi,w\_i) \notin A$ then this means that $a(\varphi) \> w\_i,w\_j$. If $f(\varphi,w\_i) \in A$ then this means that $a(\varphi) \leq w\_i,w\_j$. In both cases, it is clear that $a(\varphi) \notin \\{w\_i+1,\ldots,w\_j\\}$ (where $w\_i+1$ is the successor assignment in lexicographic order).
* All $f(\varphi,w\_i)$ are distinct. By construction, at least one of them is outside of $A$, say $f(\varphi,w\_i)$. Then $a(\varphi) \> w\_i \geq w\_1$. In particular, $a(\varphi) \notin \\{0,\ldots,w\_1\\}$, where $0$ is the first assignment in lexicographic order.

Since we chose the $w\_i$ to be evenly spaced, in both cases we eliminate a (roughly) $1/m$ fraction of the search space. After $O(nm)$ such iterations, we will be left with only $\operatorname{poly}(n)$ potential values of $a(\varphi)$, and can check them one by one (in order), thereby finding $a(\varphi)$ (if it is there to be found). (I am sketching this part since your question is about the preceding part.)
> 5 votes

---
Tags: complexity-theory, np-complete, np-hard, np, satisfiability
---


# Question
Title: Data extaction vs information extraction
How is information extraction related to data extraction? Is it a subfield or can it be used equivalently? Data is also information. What is the relation and what are the differences?

I want to write about the general topic "data extraction". I can hardly find papers about "data extraction", but most papers deal with "web data extraction", which I want to consider separately. Maybe someone can provide me some solid papers about "data extraction".

Of course, I had a look at https://en.wikipedia.org/wiki/Information\_extraction and https://en.wikipedia.org/wiki/Data\_extraction but this is not a reliable source. There must be more solid information about that somewhere.

# Answer
Information gives semantics e.g. the meaning to data. Consider pulling out of the tweets from the last hour as a raw data. If you carry out sentiment analyses form this data you get something meaningful out of raw data: information about the mood of tweeters at the moment.

Data can be sourced by other means other than extracting. For example apps can be developed to track information through sensors. Imagine a sensor tracking movements in the wild, that would be raw data. If you analyze the patterns of those movements you may infer the type of animal you have observed through the sensors e.g. information.

On a side note web extraction is possibly the most common way to extract data. The only other common extraction scenario I can think of are ETL (Extraction and Transformation Loading) for Data-warehousing purposes using BI (Business Intelligence) tooling.
> 2 votes

---
Tags: information-retrieval
---


title: Thread - contention vs race

text:
# Question
Title: Thread - contention vs race
The terms `contention` and `race` are used interchangeably when it comes to thread's state(at critical section). Are they same?

# Answer
> 1 votes
These are two distinct phenomena. Contention refers to the fact that when thread $A$ has accessed a resource $B$ needs to wait until $A$ frees it.

Race refers to the fact when both threads $A$ and $B$ want to secure access to a resource. The fastest will secure it and thus lead to contention.

---
Tags: parallel-computing, threads, multi-tasking, critical-section
---


title: Solution of CLRS question 4.6-2

text:
# Question
Title: Solution of CLRS question 4.6-2
I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log\_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

1. $T(n)= n^{\log\_ba} + n^{\log\_ba}\left( \sum\_{j=0}^{\log\_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

2. $T(n)= n^{\log\_ba} + n^{\log\_ba}\left( \sum\_{j=0}^{\log\_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
3. $T(n)= n^{\log\_ba} + n^{\log\_ba}\left( \sum\_{j=0}^{\log\_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
4. $T(n)= n^{\log\_ba} + n^{\log\_ba}( \log\_bn \cdot \lg^k(n)+ \log\_bn \cdot o(\lg^k(n))) $
5. $T(n)= n^{\log\_ba} + \Theta(n^{\log\_ba}\lg^{k+1}(n)) $

I did not understand the following points:

* $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
* In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
* There is a small o in equation 4, then how can we write theta in equation 5.

# Answer
> 2 votes
The first point seems like a mistake. Find a different solution.

For the second point, $o(f(n))$ often refers to a function whose absolute value is $o(f(n))$. So $-o(f(n))$ and $o(f(n))$ are really the same thing. For example, you can write $n - 1 = n + o(n)$.

For the third point, here is a simpler example: $n + o(n) = \Theta(n)$. You can check that if $|f(n)|/n \to 0$ then $(n + f(n))/n \to 1$, and in particular $n + f(n) = \Theta(n)$.

---
Tags: algorithm-analysis, recurrence-relation
---


# Question
Title: Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.

Prove that the given problem is in NP-complete.

I was able to prove that the problem is in NP. Hint is that we need to come up with a polynomial time reduction of the independent set problem to this problem prove that it is in NP-hard.

# Answer
Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.

Construct the graph $H = (V', E')$ where $V' = V \cup \\{ x\_{u,v} \\, : \\, (u,v) \in E \\}$ and $E' = V' \times V'$.

For each $u \in V$ let $v\_1, v\_2, \dots, v\_h$ be the neighbors of $u$ in $G$ and define the path $P\_u = \langle u, x\_{u,v\_1}, x\_{u,v\_2}, \dots, x\_{u,v\_h} \rangle$ in $H$. Let $\mathcal{P} = \\{P\_u \\, : \\, u \in V\\}$.

There is an independent set of size at most $k$ in $G$, if and only if there is a subset $\mathcal{P}'$ with $|\mathcal{P}'| \le k$ such that the paths in $\mathcal{P}'$ are pairwise vertex-disjoint.

More precisely, if $S$ is an independent set of $G$, then $\\{ P\_u \\, : \\, u \in S \\}$ is a collection of pairwise vertex-disjoint paths in $H$ and, if $\mathcal{P}'$ is a collection of pairwise vertex-disjoint paths in $H$, then $\\{u \\, : \\, P\_u \in \mathcal{P}' \\}$ is an independent set of $G$.
> 5 votes

---
Tags: graphs, np-complete, np-hard, polynomial-time-reductions, directed-graphs
---


# Question
Title: Importance of space constructability in time space relation in complexity
I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem.

Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $S$ is not space constructible?

My other question is about Remark 4.3, the book claims that if $S$ is space constructible then you can make an $NSPACE(S(n))$ machine halt on every sequence of non-deterministic choices by keeping a counter till $2^{O(S(n))}$. I am not sure how we can keep such a counter in $S(n)$ space. The space constructability of $S$ implies that we can compute $S(n)$ in $O(S(n))$ space, not $2^{O(S(n))}$ in $O(S(n))$ space.

# Answer
> 1 votes
To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably some of these inclusions do hold regardless of space-constructibility.

Regarding the second question, suppose that you computed $S(n)$ (in binary), and are interested to compute $2^{CS(n)}$. First, multiply $S(n)$ by $C$; this uses $O(\log S(n))$ space. Second, count $CS(n)$ spaces, fill them with zeroes, and add a one to the left. You have computed the binary representation of $2^{CS(n)}$, using additional $S(n)+1$ space.

---
Tags: complexity-theory, time-complexity, space-complexity
---


# Question
Title: Dynamic length of union of segments (1d Klee's measure problem)
Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of their union. There is a simple $O(n \log n)$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let's look at a dynamic variant of this problem: we are receiving $n$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $O(n \log n)$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.

Update:

What if we make the problem even more difficult by also allowing to delete previously added segments? Can it still be solved offline in $O(n \log n)$ time where $n$ is the total number of add/delete segment queries?

# Answer
> 3 votes
The online version can be solved in $O(n\log n)$ *amortised* time, possibly using the technique you already came up with. The key is to maintain just the **nonoverlapping** intervals that result from merging intervals wherever necessary.

Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, type)$, where $type$ is either $start$ or $stop$. New intervals will be merged with these so that the segments in the tree are nonoverlapping at all times. When a new segment $\[a, b\]$ arrives, add $b-a$ to the total length, and search the tree to find all contained endpoints. For each such endpoint:

* If it is $(x, start)$, add $x$ to the total length.
* If it is $(x, stop)$, subtract $x$ from the total length.
* Delete it.

If the leftmost such endpoint is a $start$, or if there are no endpoints, then insert $a$ as a $start$ endpoint; otherwise, if there was at least one endpoint (the leftmost of which must be a $stop$), add $a$ to the total length. If the rightmost such endpoint is a $stop$, or if there are no endpoints, then add $b$ as a $stop$ endpoint; otherwise, if there was at least one endpoint (the rightmost of which must be a $start$), subtract $b$ from the total length.

To understand why the time complexity is not quadratic even though an individual operation can take $O(n)$ time, notice that a preexisting interval never needs to be merged with other intervals more than twice (once to its left, once to its right), so we can conservatively pay the cost of these potential merges at the time we create the interval; since merging amounts to removing an endpoint, the cost of performing a merge is constant, so the overall time complexity doesn't change. Basically, any time we have to merge a bunch of intervals, we remove the possibility of having to merge them in the future.

# Answer
> 1 votes
In the case when all additions and deletions are known beforehand, there is an algorithm of $O(n\log n)$ time-complexity. The basic idea is to decompose each interval into $O(\log n)$ "key intervals" and keep track the number of times key intervals are covered in a designated binary tree.

Collect and sort all endpoints of all intervals that have been added or deleted. We get $a\_0, a\_1, \cdots, a\_{n-1}$, where $n$ is the total number of distinct endpoints. (If $n-1$ is not a power of 2, add some extra points.

Construct a tree each node of which has an interval as its key. The keys of the leaves are all intervals of the form $\[a\_i, a\_{i+1}\]$. The parent of the leaves with key $\[a\_{2i}, a\_{2i+1}\]$ and $\[a\_{2i+1}, a\_{2i+2}\]$ is the node whose key is $\[a\_{2i},a\_{2i+2}\]$. The parent of the nodes with key $\[a\_{2i}, a\_{2i+2}\]$ and $\[a\_{2i+2}, a\_{2i+4}\]$ is the node with key $\[a\_{2i},a\_{2i+4}\]$. And so on. Each node of the tree has a key of the form $\[a\_i,a\_j\]=\[a\_{2^mk}, a\_{2^m(k+1)}\]$. Its left child is the node with key $\[a\_i, a\_{(i+j)/2}\]$ and its right child is the node with key $\[a\_{(i+j)/2}, a\_j\]$. We will call all those intervals "key intervals". Any interval whose endpoints are among $a\_0, a\_1, \cdots, a\_n$ decomposes into $O (\log (n))$ key intervals naturally.

Each node of the tree will store a couple of other quantities. First, it will store the real\_length, $a\_j-a\_i$ where $\[a\_i,a\_j\]$ is its key interval. Second, it will store covering\_intervals\_count, the number of intervals in the current set of intervals containing its key interval. Thirdly, it will store covered\_length, which is the the length of the union of all current intervals covered by its key interval. The current covered\_length of the root node is the current length of the union of all current intervals.

How to maintain the values of these three quantities when intervals are added and removed?

* The value of read\_length does not change during these operations. They will be set when the tree is initialized. Note that for parent node $s$, $s$.real\_length = left\_child($s$).real\_length + гight\_child($s$).real\_length.
* The value of covering\_intervals\_count increases by one iff an added interval covers the corresponding key interval. Similarly, it decreases by one if a deleted interval covers the corresponding key interval.
* The value of covered\_length is equal to real\_length if the current value of covering\_intervals\_count is positive. So, real\_length does not need to be touched as long as covering\_intervals\_count is positive. If it is reduced to zero, then we have to compute, recursively as further as necessary, s.covered\_length = left\_child(s).covered\_length + right\_child(s).covered\_length.

Further detail in Russian are available in WPS2010.pdf, a file in this folder on Google Drive. You can find Problem D, Длина объединения (Join Length) and more explanation, starting from page 109.

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


# Question
Title: How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $
I am trying to answer this question: $3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$

My question is how to solve this question.

Here is what I have tried so far:

I applied the definition $3x^3 + 2x + 1 \> c \cdot x\log x$ for all c, given $n \geq k$, for some k

I tried to apply the technique of applying the equality that: $n \< n^3$

Since n is less than the highest order term we can just move all terms to order n ??

Giving $6x \< c \cdot x \log x$

Then you can choose: $k \< 2^\frac{6}{c}$

# Answer
What I recommend first is to notice that if you're looking at the **complexity** of the function $3x^2+2x+1$, really all you should care about is the function $x^2$. because **if** you will prove that $x^2 = \omega(xlogx)$ then adding the $2x + 1$ won't ruin that proof since $x^2$ is polynomially bigger than $2x + 1$ and so we can just look at the $x^2$.

(I will use $n$ instead of $x$ because that is what I'm familiar with but it's exactly the same for $x$)

So now what we want to prove is that $$n^2 = \omega(nlogn)$$

which as you offered only you need to flip your sides in the equation, we will need to find a positive $C$, so that for any $n\>n\_0$ or $n\>k$ : $$f(n)\ge C\cdot g(n)$$ when $f(n) = n^2$ , $g(n) = nlogn$

That will get us to: $n^2 \ge Cnlogn $

We can divide both side by $n$: $$n \ge Clogn$$

Now that's a bit of a tricky one. but "it is known" that polynomial running time is SLOWER than logarithmic one.

Basically what that means is that you'd prefer to reach a logarithmic complexity running time if possible because than you'll get faster execution.

Generally this is the order of running times when the first is the fastest:

$$1.Constant$$ $$2.Logarithmic$$ $$3.Linear$$ $$4.Linearithmic$$ $$5.Polynomial$$ $$6.Exponential$$

(you can read more about it here: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/)

Another way to see it is if you'll find the limit of the division of the two functions, let's say we'll choose: $${f(n) \over g(n)}$$

If $$\lim\_{n\to \infty} {f(n) \over g(n)} \rightarrow \infty$$ It means that $f(n)$ is "much bigger" than $g(n)$

If $$\lim\_{n\to \infty} {f(n) \over g(n)} \rightarrow 0$$ It means that $f(n)$ is "much smaller" than $g(n)$

The last option (Atleast in this method) is: $$\lim\_{n\to \infty} {f(n) \over g(n)} \rightarrow C$$ When $C \gt 0$ which means both of the functions have Asymptotically the same complexity.

Back to our functions, we can see that : $$\lim\_{n\to \infty} {n \over log(n)}$$

We will use lupital rule and get: $$\lim\_{n\to \infty} {1 \over 1/n} \rightarrow \infty$$

We now can see that $f(n) = n$ is bigger Asymptotically from $g(n) = log(n)$ hence : $$n = \omega (log(n))$$

---

I really hope I explained as clear and easy as possible, it's just English isn't my mother tongue language so I apolegize in advance for any mistakes with grammer etc.

---

Update : I've noticed you've made changes to the original function and now it is $3x^3+2x+1$, yet the proof will be the same, just use $n^3$ and than you'll still get the same result when using lupital. That because, inevitably, if we just proved that $n^2$ is much bigger than $log(n)$ than of course that $n^3$ which is much bigger than $n^2$ would also be bigger than $log(n).$
> 1 votes

# Answer
The easiest way is to check that $\lim\_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$.

$$ \lim\_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = \lim\_{x \to \infty} \frac{3x^3}{ x \log x} = \lim\_{x \to \infty} \frac{3x^2}{ \log x} = \lim\_{x \to \infty} 6x^2 = +\infty. $$
> 1 votes

---
Tags: complexity-theory, asymptotics, proof-techniques, complexity-classes, landau-notation
---


title: Process synchronization problem

text:
# Question
Title: Process synchronization problem
The atomic fetch-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. Consider the following implementation of P and V functions on a binary semaphore S.

```
   void P (binary_semaphore *s) {
        unsigned y;
        unsigned *x = &(s->value);
        do {
            fetch-and-set x, y;
        } while (y);
    }

    void V (binary_semaphore *s) {
        S->value = 0;
    }

```

Which one of the following is true?

1. The implementation may not work if context switching is disabled in P()
2. Instead of using fetch-and–set, a pair of normal load/store can be used
3. The implementation of V is wrong
4. The code does not implement a binary semaphore

Option 1 is correct. I am unable to understand the reason for it. Please explain.

# Answer
Explanations for the truth-value of each assertion:

(1) is true because any process running P() after another process has already run P() will see y==1 and so be stuck in the do-loop. If context-switching is disabled inside P() \[and we assume re-enabled on exit from P()\], then the process stuck in the do-loop will be the ONLY running process, so no other process can release that one from the do-loop by calling V().

(2) is false because a context-switch may occur between the load of y and the store to x. Consider processes P1, P2, both calling P(). The following sequence is possible: (a) P1 loads y, which happens to be 0; (b) The context switches to P2; (c) P2 loads y -which is still 0-, then sets x to 1 and exits the loop (because for it y==0) and enters the critical section; (d) The context switches back to P1, which now sets x to 1 -but still sees its version of y as 0, so it exits the loop and enters the critical section. Verdict: Mutual-exclusion is NOT enforced!

(3) The implementation of V() is not wrong, given the implementation of P(). Execution of V() WILL set 'value' to 0, and by the atomicity property this must occur either entirely before or entirely after any test\_and\_set. If before, then test\_and\_set will set y to 0 immediately; if after, the same thing will happen on the next do-loop iteration.

(4) \[because of 2 & 3\].
> 0 votes

---
Tags: operating-systems, synchronization, semaphore
---


# Question
Title: Proving a certain primitive recursive function exists
Assume $f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $g\colon ω × ω → ω$ where the following holds:

$∀n \[∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)\]$

So for every $n$, there is an $s$ such that $f(n, s) = 1$ if and only if there is a $k$ such that $g(n, k) = 1$.

Been working on this problem for a while now, if anyone could please help?

# Answer
The function $g$ interprets $k$ as two inputs $k\_1,k\_2$. It runs $f(n,k\_1)$ for $k\_2$ steps, returns whatever $f$ does if $f$ halts, and returns $0$ otherwise.
> 1 votes

---
Tags: computability, logic, primitive-recursion
---


# Question
Title: Worst simultaneous blowup when converting to CNF and DNF
I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the two normal forms. Or, stated otherwise, given the predicate $p$, how to find:

$$ \rho = \max \min \left\\{\alpha, \beta\right\\} $$

where

$$ \alpha = \mathcal{O}(\text{CNF}(p)) $$

$$ \beta = \mathcal{O}(\text{DNF}(p)) $$

# Answer
> 0 votes
You haven't explained how you measure the size of a CNF/DNF – two common options are number of clauses/terms and total size of the clauses/terms.

The worst example is parity. Any CNF/DNF for parity must contain $2^{n-1}$ terms of size $n$. In contrast, this answer on cstheory shows that every CNF/DNF contains at most $2^{n-1}$ terms.

In the monotone case, the worst example is Majority. Majority has $\binom{n}{\lfloor n/2 \rfloor}$ many minterms/maxterms (for odd $n$), each of size $\lceil n/2 \rceil$. Since the set of minterms/maxterms is an antichain, by Sperner's theorem it contains at most $\binom{n}{\lceil n/2 \rceil}$ many minterms/maxterms. Moreover, the LYM inequality easily implies that the maximum total size of sets in an antichain is $\lceil n/2 \rceil \binom{n}{\lceil n/2 \rceil}$, exactly matching the performance of Majority.

---
Tags: space-complexity, boolean-algebra
---


# Question
Title: Log space reduction from STCONN to CYCLE
I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.

# Answer
There is no need to store the new graph on the tape. We just need to be able to output it in logspace. This is straightforward, for any reasonable encoding of graphs.
> 1 votes

---
Tags: reductions, space-complexity
---


# Question
Title: Why ASCII letter A has a Hamming Distance of 3?
My question is what does \[this construction gives a Hamming Distance a distance of 3\] means? Why the Hamming Distance of ASCII letter A is 3? How do you determine the Hamming Distance is 3?

This is an excerpt from Computer Network by Andrew S. Tanenbaum page 206.

# Answer
> 0 votes
A *code* is a collection of binary vectors of some length $n$, known as *codewords*. The *Hamming distance* between two codewords $x,y$ is the number of positions $i$ such that $x\_i \neq y\_i$. The *minimum distance* of a code is the minimum Hamming distance between two different codewords.

For example, the Hamming(7,4) code consists of 16 codewords of length 7:

```
0000000
1110000
1001100
0111100
0101010
1011010
1100110
0010110
1101001
0011001
0100101
1010101
1000011
0110011
0001111
1111111

```

You can check that any two codewords differ in either 3 or 4 positions. For example, 1010101 and 0100101 differ in the first 3 positions. Therefore the minimum distance of the code is 3.

There is absolutely no meaning for the Hamming distance of a single codeword. Hamming distance is a property of pairs of codewords.

# Answer
> 0 votes
Tanenbaum is not saying that ASCII character "A" has a particular Hamming distance. Computerphile has a video that may clear things up.

# Answer
> 0 votes
The Hamming distance between two codes is the number of times there is a different bit between them, for example between `1011` and `1111` a Hamming distance of 1.

The example that you're seeing is code correction. When you send anything through a cable there could be some errors (*change of bits `1 to 0` or `0 to 1`*). So there are some common algorithms that minimise these errors within the domain of **Information Theory**. In this example they show the binary code of the letter A before and after being received by destination, **a Hamming distance of 3 was found means that 3 bits have changed.**

I previously implemented some related functions and more details are explained on my GitHub. You can check my git repository if you're interested.

---
Tags: hamming-code, hamming-distance
---


# Question
Title: How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?
Given an one dimensional array of size nxn, where n is a perfect square

How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a mathematical way to traverse the subsquare?

# Answer
> 1 votes
Let the one-dimensional cells be $c\_1, c\_2, \cdots, c\_{n^2}$.

Assume the top-left cell is at $(1,1)$, i.e., the first row and the first column. Assume the top right cell is at $(1,n)$, i.e., the first row and the $n$-th column. Then the $i$-th cell, $c\_i$ is at $(i/n + 1, i \\%n +1)$. Here $i/n$ is the *integer division* and $i\\%n$ is the modulo operation in any popular programming language. For example, let $n=9$. Then the $42$-th cell, $c\_{42}$ is at $(42/9+1, 42\\%9+1)=(5, 7)$.

Suppose the subsquares are lined up in the same order as the cells, so that we have subsquares $S1, S2, \cdots, Sn$. Consider each subsquare as a kind of "large cell". So that we would have the following coordinates for subsquares.

Note that $c\_i$ belongs to the $(i/n+1)$-th subsquare, i.e. subsquare $S(i/n+1)$. For example, $c\_{37}$ belongs to the $5$-th subsquare, i.e, subsquare $S5$. We are in the same situation as before, but with the $(i/n+1)$-th "large cell" and a $\sqrt n\times\sqrt n$ of "large cells". So similarly we see that the $(i/n+1)$-th subsquare is at $((i/n+1)/\sqrt n + 1,(i/n+1)\\%\sqrt n + 1)$, using the coordinates for subsquares.

Suppose we want to traverse the subsquare at $(j,k)$ (where $(j,k)$ is in the coordinates for subsquares).

* The first cell (the top-left cell) of that subsquare is $c\_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1}$
* The first cell of the second row of that subsquare is $c\_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1 + n}$
* $\cdots$
* The first cell of the last row of that subsquare is $c\_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + 1 + (\sqrt n -1 )n}$

So we can traverse all cells in that subsquare by the following pseudocode.

$\quad$ for $row$ in $1, 2, \cdots, \sqrt n$
$\quad\quad$ for $column$ in $1, 2, \cdots, \sqrt n$
$\quad\quad\quad$ visit the cell at $row$-th row and $column$-th column of the subsquare at $(j,k)$, which is $c\_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + (row -1 )n + column}$

Note "$row$-th row and $column$-th column" are referring to cells in that subsquare.

For example, we will traverse the cells at subsquare (2,3) in the following order.

* cells in its first row, $c\_{34}$, $c\_{35}$, $c\_{36}$,
* cells in its second row, $c\_{43}$, $c\_{44}$, $c\_{45}$,
* cells in its third row, $c\_{52}$, $c\_{53}$, $c\_{54}$.

---
Tags: algorithms, arrays, square-grid
---


title: Can 3-coloring be reduced to 3-clique?

text:
# Question
Title: Can 3-coloring be reduced to 3-clique?
I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm fairly confident that 3-Coloring is NP-Complete, while 3-Clique is P. Correct me if I'm wrong (which is very likely), but for any k-clique where the k is fixed, is $V^k$, meaning the 3-clique is $V^3$, right? I asked my professor about this and his response was:

"3-clique is definitely not in P. You (apparently) have to examine all thrices of vertices to settle the matter."

And I still don't understand how this is not a $V^3$ operation.

If I figured out a way to reduce 3-coloring to 3-clique wouldn't I be millionaire?

# Answer
You are correct.

3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard.

So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.
> 5 votes

# Answer
The number of k-tuples of vertices in a graph with $n$ vertices are: $^nC\_k$. You can iterate through each possible k-tuple and check in $O(k^2)$ time whether the given k-tuple forms a clique. For **any fixed natural $k$**, the number $^nC\_k$ is $O(n^k)$, and hence you can check whether a graph has $k$-clique in $O(k^{2}.{^n}C\_k)$; the problem would be in $P$.

The problem of $k$-clique is $NP$-complete for arbitrary $k$.
> 3 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Will the minimum spanning tree not have only those edges specified by the cycle property?
I have just started to understand the "Minimum Spanning Trees" (MSTs), and had come across the cycle property. I am referring to the book - Algorithm Design by Jon Kleinberg and Eva Tardos. The statement of the property as written in the book is:

> Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v,w) be the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree.

Now my doubt is: Are the edges of a graph (undirected graph with edges having distinct positive weights) that do not satisfy the cycle property the only ones which aren't present in the MST or will there be any other edges that don't belong to the MST and aren't covered by this property?

I am unable to come up with a proof to argue about whether such edges exist or not. Can some please give a proof for this?

# Answer
> 1 votes
Let us say that an edge $e$ in $G$ is **BAD** if there exists a cycle in $G$ in which $e$ has maximum weight.

Define ${\cal B}=\\{e~|~e$ is **BAD** in $G\\}$ to be the collection of all bad edges.

Your question is whether the graph $(G - {\cal B})$ the MST of $G$ (assuming all edge-weights are distinct). The answer is YES!

In order to prove this it suffices to show that $(G - {\cal B})$ is acyclic.

Assume on contrary that $(G - {\cal B})$ contains a cycle, say $C$. Observe that $C$ is a cycle in $G$ also. Let $e^\*$ be the edge of maximum weight in cycle $C$. Now $e^\*$ is a **BAD** edge, so it should not have been is graph $(G - {\cal B})$ on first place. This shows that $(G - {\cal B})$ is acyclic.

# Answer
> 0 votes
Sorry if I didn't understand your question, but what I think you meant to ask is, whether it is possible for an edge to not be in a MST if this edge is not in a cycle.

Here's my answer.

Let us assume that we have an edge (u,v) in a graph G, that isn't part of a cycle. This would mean that there is no path from u to v that isn't the edge (u,v). If the edge (u,v) weren't in the MST, this would mean that there is no path from u to v in this MST, meaning that the MST would be disconnected, and thus not an MST at all. Hence if an edge is not part of a cycle, it must be in the MST of the graph.

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


title: Calculating efficiency?

text:
# Question
Title: Calculating efficiency?
A program must construct and then use a set $S$ of 1000 integers.

```
/* part 1 */

S = empty
for i from 1 to 10000 {

...

x = ...

add x to S

}

/* part 2 */

for j from 1 to 100000 {
...
y = ....
test if y belongs to S
...
}

```

To represent S you have the choice between

* a double-linked list
* a balanced binary search tree
* an open hash table size 100
* an open hash table size 5000

---

1. What will be the most efficient solution for Part 1 of the program?
2. What will be the most efficient solution for Part 2 of the program?
3. What will be the most efficient solution overall?

# Answer
> 0 votes
All solutions are equivalent, as far as asymptotic complexity is concerned, since they all require $\Theta(1)$ time.

# Answer
> 0 votes
The most efficient would be a hash table with say 15,000 slots or one that dynamically changes its size. The most efficient solution overall is to use whatever your development environment provides.

Note that you don’t say what x is. For a hash table, you need the ability to calculate hash values and check for equality. For a search tree, you need an ordering (\<, =, \>) of the values. For a linked list, you need plenty of time :-)

---
Tags: complexity-theory, efficiency, hash
---


# Question
Title: Calculating time it takes to download content
I have a network line that runs at a speed of 400kbps. How long do I have to download 6GB.

# Answer
> 1 votes
Most likely what you have is a line with a 400kbps bandwidth. That means a maximum throughput of 400kbps.

If you divide by 8 bits you get KiloBytes/s = 50Kbs.

1GB = 100000KB, thus 6GB = 600000KB,

600000KB / 50KB/s = 12000 seconds = 200 minutes = 3 hours 20 minutes

That means it would take **at least** 3 hours 20 minutes to download. It could take significantly longer depending on network traffic.

---
Tags: network-topology
---


title: Organizing a "speedback"

text:
# Question
Title: Organizing a "speedback"
Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people.

I'm in a team and I want to plan the ideal speedback setup: all team members have to give feedback to eachother. I want to group people in a way that maximizes the concurrency of simultaneous pairs so we reduce the total time of the sessions.

Consider the input: "alexandre", "sergiu", "joana", "tiago", "susana", "david"

combinations(6,2) = 15 possible pairs

1st session:

```
"alexandre" with "sergiu"
"joana" with "tiago"
"susana" with "david"

```

2nd session:

```
"alexandre" with "joana"
"sergiu" with "tiago"
"joana" with "david"

```

3rd session:

...

you get the ideia.. until everyone "dates" everyone.

I need all the possible pairs to be matched in the end.

Do you how to get this output? (or can you hint about the solution)?

# Answer
> 5 votes
Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K\_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$.

**Case 1: $n$ is even.** In this case, $K\_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ edges. Hence we can hope for a partition of $K\_n$ into $n-1$ perfect matchings. This is a standard problem, known as *1-factorization of the complete graph*. Here is one solution: $$ (0,n-1),(1,n-2),(2,n-3),(3,n-4),\ldots,(n/2-1,n/2) \\ (1,n-1),(2,0),(3,n-2),(4,n-3),\ldots,(n/2,n/2+1) \\ (2,n-1),(3,1),(4,0),(5,n-2),\ldots,(n/2+1,n/2+2) \\ \ldots $$ Explanation: the $i$'th row consists of $(i,n-1)$ together with $(j+i,n-1-j+i \bmod n-1)$ for $1 \leq j \leq n/2-1$. For example, when $n = 6$ you get: $$ (0,5),(1,4),(2,3) \\ (1,5),(2,0),(3,4) \\ (2,5),(3,1),(4,0) \\ (3,5),(4,2),(0,1) \\ (4,5),(0,3),(1,2) $$

**Case 2: $n$ is odd.** In this case, $K\_n$ still contains $\binom{n}{2}$ edges, but now each matching contains at most $(n-1)/2$ edges. Hence we can hope for a partition of $K\_n$ into $n$ almost-perfect matchings. We can take the solution above for $n+1$, and just ignore the match of vertex $n$. This gives the following solution: $$ (1,n-1),(2,n-2),(3,n-3),\ldots,((n-1)/2,(n+1)/2) \\ (2,0),(3,n-1),(4,n-2),\ldots,((n+1)/2,(n+3)/2) \\ (3,1),(4,0),(5,n-1),\ldots,((n+3)/2,(n+5)/2) \\ \ldots $$ Explanation: the $i$th row consists of $(j+i,n-j+i \bmod n)$ for $1 \leq j \leq (n-1)/2$. For example, when $n = 7$ you get: $$ (1,6),(2,5),(3,4) \\ (2,0),(3,6),(4,5) \\ (3,1),(4,0),(5,6) \\ (4,2),(5,1),(6,0) \\ (5,3),(6,2),(0,1) \\ (6,4),(0,3),(1,2) \\ (0,5),(1,4),(2,3) $$

---
Tags: combinatorics, functional-programming
---


# Question
Title: Worked out example of Slepian-Wolf Theorem
*Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.*

The Slepian-Wolf theorem states that sequences of outputs from two separate random variable sources A and B that have a joint probability distribution defined on them, if encoded with the following rates, can be completely retrieved when decoded together:

$$ R\_A \geq H(A|B) \\ R\_B \geq H(B|A) \\ R\_A + R\_B \geq H(A,B) $$

$R\_x$ refers to the bits required for encoding one symbol of $X$, assuming all logarithms are taken to the base 2.

Given this, I wanted to try out an example, especially because I find fractional number of bits per symbol slightly confusing to think about.

Consider two sources $A$ and $B$, that either sprout out 0 or 1 following this probability distribution:

`**`A \ B`**`  `**`0`**`  `**`1`**`
`**`0`**`   ``0.5``  ``0``
`**`1`**`   ``0.25`` ``0.25``

We calculate the entropies as follows: $$ H(A,B) = 3/2 = 15/10\\ H(A|B) = 7/10 \\ H(B|A) = 1/2 = 5/10\\ $$

Now, assume that the a certain sequence of bits that A and B give out are as follows:

`**`A`**`  `**`B`**`
``0``  ``0``
``0``  ``0``
``1``  ``0``
``1``  ``1``
``1``  ``0``
``0``  ``0``
``0``  ``0``
``1``  ``1``
``1``  ``0``
``0``  ``0``

I should be able to find an encoding that allows A to send atleast 7 bits, B atleast 5 and a total of atleast 15, such that they can be decoded completely, right?

Unfortunately I am unable to think of an encoding where they send less than 10 bits each.

For example, B does not have to send anything when A sends 0, however B does not know when A sends 0.

I would also like to know if this is the wrong way to interpret the theorem (perhaps a longer sequence is required), or if there is another way to see its working.

# Answer
> 1 votes
Here's a simpler example. Consider the binary erasure channel which erases its input with probability $1/2$. The channel capacity is $1/2$, so you should be able to send one bit of information by sending two bits on the channel. Or should you?

Shannon's theorem only guarantees that for every $\epsilon \> 0$, you can send $(1/2-\epsilon) N$ bits of information by sending $N$ bits across the channel, with failure probability approaching zero as $N\to\infty$. There are two features of this theorem (shared by Slepian–Wolf) that you didn't take into account:

* The theorem talks about asymptotic rates.
* The theorem allows for some small failure probability.

The article you link to assumes you are already aware of all this. Since you appear not to be, I suggest reading a textbook on information theory, where all the relevant concepts are defined and explained.

---
Tags: information-theory, coding-theory, encoding-scheme, entropy
---


# Question
Title: Why double error correction and quadruple error detection cannot occur at the same time?
What does \[ we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways\] means? I understand how double error correction works but I cannot imagine quadruple error detection. Can anybody show me example why double error correction and quadruple error detection cannot occur at the same time because it requires different interpretation?

For example, if double error correction occur,

will be something like this. How about quadruple error detection?

This is an excerpt from Computer Network Book by Andrew S. Tanenbaum

The data link layer(chapter 3), Page 208, Fifth edition.

# Answer
Your interpretation is mistaken. Both properties are satisfied at the same time, since they are properties of the code itself.

In more detail, using the notation $d(x,y)$ for the Hamming distance between $x,y$:

* If $x$ is the sent codeword, $y$ is the received codeword, and $0 \leq d(x,y) \leq 4$, then we would be able to detect that $y \neq x$. This is *quadruple error detection*.
* If $x$ is the send codeword, $y$ is the received codeword, and we are promised that $0 \leq d(x,y) \leq 2$, then we can recover $x$ from $y$. This is *double error correction*.

Rephrasing:

* If there were errors in the channel but at most 4, we will be able to detect that errors occurred.
* If there were errors in the channel but at most 2, we can not only detect that errors occurred, but also determine their locations.

In the second case, we both detect that errors occurred, and are able to undo them. In that sense, we can both detect and correct errors at the same time.

Your quote is trying to make a different point. Given a codeword $y$, what can you do with it?

* You can try to detect whether errors occurred. This detection is guaranteed to be successful if up to 4 errors have occurred.
* You can try to determine the sent codeword $x$. This will be successful if up to 2 errors have occurred.

In practice, this is used in the following way:

* It is highly unlikely that more than 4 errors occur (or this is taken care of in some other way). Your error-handling strategy is to detect whether any errors occurred, and if so, ask the sender to resend the message.
* It is highly unlikely that more than 2 errors occur (or this is taken care of in some other way). Your error-handling strategy is to silently correct the errors, without communicating with the sender.

The two strategies are mutually exclusive, since the error detection mechanism doesn't differentiate between the case in which the number of errors is 0,1,2 and the case in which the number of errors is 3,4. So if you assume that there are at most 4 errors, you have no way of knowing whether the input can be corrected (there were up to 2 errors) or not.

The author doesn't mention a third approach, *list decoding*, which allows you to handle more errors as part of a longer communication protocol. In list decoding, you get a small "list" of possible sent messages, which you winnow down in some other way. I don't know whether this is actually used in practice, but it has been very influential in coding theory and theoretical computer science.
> 1 votes

# Answer
With a hamming distance of five, you can make one of two assumptions:

A. No word has more than four errors. Since you need five changes to get from one valid word to another valid word, and five errors don’t happen, every invalid word has 1 to 4 errors.

B. No word has more than two errors. If you find an invalid word, then it has at most two changes from a valid word. To reach any different valid word would take at least 3 more changes, so there is only one valid word within two changes, so you can fix the errors.

But you can’t assume both at the same time. If you find an invalid word, it could have two or four errors, and trying error correction would give you a totally wrong result.

If you have a hamming-distance of 7, you can indeed detect up to four errors and fix up to two errors at the same time. A word with four or three errors cannot be made valid with 1 or 2 changes, so you can detect 3 or 4 errors without being able to fix them, and you can fix 1 or 2 errors.
> 2 votes

---
Tags: error-correcting-codes
---


# Question
Title: Turing machine with a finite tape after the input word ends
How can I prove that for a natural number K, a language that accepted by a Turing machine with K cells after the input word ends, belongs to R (which R is the set of languages that there is Turing machine that accept them while for each input the run is finite)?

# Answer
Given the length of the input $n$, you can come up with a bound $N(n)$ on the number of configurations that the Turing machine can have. If the machine hasn't stopped on an input within $N(n)$ time steps, then it will never stop (why?), and you can use this to complete the proof. Details left to you.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: $\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language
Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as $$\mathcal{G} = \\{ v\_2 v\_4 \ldots v\_{k} : v\_1 v\_2 v\_3 v\_4 \ldots v\_{k-1} v\_{k} \in \mathcal{L}, \text{ $k$ even} \\} $$

I have seen a similar question (asked 5 years ago) but I am not sure how it can work.

## Proposition

$\mathcal{L}$ is CFL so it has own push-down automata. So let copy states of $\mathcal{L}$ and if it has a state called $S$ and it gets to state $T$ upon letter $x$ then $\mathcal{G}$ will have states $S\_1, S\_2, T\_1, T\_2$ and letter $x$ turns $S\_1$ to $T\_2$ and $S\_2$ to $T\_1$.

My question is why it is correct apporach? $\mathcal{G}$ automata won't read any of $v\_1, v\_3, v\_5,... v\_{k-1}$ so how it can ensure that this word belongs to $\mathcal{L}$?

# Answer
> 3 votes
Let the PDA for the given language $L$ be $P$. Take two copies of *states* of $P$: $P\_1$ and $P\_2$. We will join $P\_1$ and $P\_2$ as follows: if there is transition state $S$ from $T$ on reading $x$ pushing/popping $Y$, then add an $\epsilon$-transition from $S\_1$ to $T\_2$ pushing/popping $Y$, and add a transition from $S\_2$ to $T\_1$ on reading $x$ pushing/popping $Y$. The initial states will be in $P\_1$ and the final states in $P\_2$.

The idea is: We start from an initial state in $P\_1$. We have to non-deterministically take an $\epsilon$-transition (because only those are present when we are at a state in $P\_1$): this will correspond to reading $v\_1$. Then, when we are in a state in $P\_2$, we will read $v\_2$ and move to an appropriate state in $P\_1$ allowed by the transitions. This will make sure that we guess a letter $v\_i$ before reading any letter $v\_{i+1}$ from the input for all $i$ from $1$ to $k$.
This will make sure that $v\_1v\_2\ldots$ is in $L$. Hence, even though we are only reading letters at even positions, we are guessing the letters at odd positions such that the whole word should have been accepted by $P$.

You can try formally proving this.

# Answer
> 3 votes
This answer assumes that $v\_i \in \Sigma$ are individual symbols.

You can prove this using closure properties. The advantage is that any class of languages closed under the requisite closure properties will be closed under this operation. Specifically, we will need closure under homomorphism, reverse homomorphism, and intersection with regular language, which are exactly the so-called "full trio".

Let $\Sigma' = \\{ \sigma' : \sigma \in \Sigma \\}$ be a copy of $\Sigma$. Define homomorphisms $r,d\colon \Sigma \cup \Sigma' \to \Sigma$ by $r(\sigma) = r(\sigma') = \sigma$ and $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then $$ \mathcal{G} = d(r^{-1}(\mathcal{L}) \cap (\Sigma' \Sigma)^\*). $$

Some families of languages, for example context-sensitive languages, are closed under the so-called "trio", in which homomorphism is replaced with $\epsilon$-free homomorphism (meaning $h(\sigma) \neq \epsilon$ for all letters $\sigma$). We can accommodate these as well with a slightly more complicated argument.

Let $e\colon \Sigma' \times \Sigma \to \Sigma \cup \Sigma$ be given by $e(\sigma',\sigma) = \sigma' \sigma$, and let $p\colon \Sigma' \times \Sigma \to \Sigma$ be given by $p(\sigma',\sigma) = \sigma$. Then $$ \mathcal{G} = p(e^{-1}(r^{-1}(\mathcal{L}) \cap (\Sigma'\Sigma)^\*)). $$

# Answer
> 2 votes
The other answers use pushdown automata and closure properties. Lets try a solution with context-free grammars.

We may assume that $L$ has a context-free grammar in Chomsky normalform. Which means its productions are of the form $A\to BC$ and $A\to a$, with $A,B,C$ nonterminals, and $a$ terminal (in $\Sigma$).

We will build a grammar for the derived language $G$, where every other symbol is skipped. The new grammar will have nonterminals that keep track of the even/odd position of the next terminal in the string.

For each nonterminal $X$ we introduce four nonterminals $\[i,X,j\]$ with $i,j$ either $0$ or $1$.

For each production $A\to BC$ we introduce eight productions $\[i,A,k\] \to \[i,B,j\] \[j,C,k\]$

For earch terminal production $A\to a$ we introduce two productions $\[0,A,1\] \to \varepsilon$ and $\[1,A,0\] \to a$. (These productions toggle the parity of the symbol.)

The axiom for the new grammar is $\[0,S,0\]$ where $S$ is the original axiom.

This construction actually works that same way as one that can be used to prove that context-free languages are closed under intersection with regular languages. Usually that is shown using pushdown automata, but it can be done with context-free grammars.

---
Tags: context-free, pushdown-automata, closure-properties
---


# Question
Title: BFS for transforming one word to another
I'm having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI):

> Let $s$ and $t$ be stings and $D$ a dictionary, i.e., a set of strings. Define $s$ to *produce* $t$ if there exists a sequence of strings from the dictionary $P = \langle s\_0,s\_1,\ldots,s\_{n-1} \rangle$ such that the first string is $s$, the last string is $t$, and adjacent strings have the same length and differ in exactly one character. The sequence $P$ is called a *production sequence*. For example, if the dictionary is {bat,cot,dog,dag,dot,cat}, then ⟨cat,cot,dot,dog⟩ is a valid production sequence.
>
> Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. Assume that all characters are lowercase alphabets. If $s$ does produce $t$, output the length of a shortest production sequence; otherwise, output -1.
>
> *Hint:* Treat strings as vertices in an undirected graph, with an edge between $u$ and $v$ if and only if the corresponding strings differ in one character.

Here is the solution:

> The number of vertices is $d$, the number of words in the dictionary. The number of edges is, in the worst-case $O(d^2)$. The time complexity is that of BFS, namely $O(d+d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

So I agree with number of vertices being $d$, and the worst case number of edges is $d^2$. We know that the complexity of BFS is $O(V+E)$, hence $O(d+d^2) = O(d^2)$, though if we used a set to record visited vertices (or removed a vertex once we visited it from the graph), that should reduce BFS's complexity to $O(d)$. But then things get funky.

> If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$.

don't agree with this. Imagine we have 5 words in our dictionary $\\{ab, ac, ad, ae, af\\}$, so $d=5$ and $n=2$. All these vertices are connected and you can see that each vertex has 4 edges leaving it... which is more than $O(n)$. You can have $26^n$ possible edges leaving the vertex, but you only have $d$ vertices in the graph, so the number of edges leaving a single vertex should be $O(d)$.

I ultimately agree that the final complexity of the algorithm is $O(nd)$, but I calculated that simply given that we can visit up to $d$ vertices (we use a visited set to prevent cycles) and for each vertex visited one we iterate over the string of length $n$ as we look for differences in the alphabet of lower characters $O(26nd) = O(nd$).

Interested to hear what people think, Thanks :)

# Answer
> 1 votes
The maximum degree of a vertex is $25n$, since this is the number of words which can be obtained by changing a single character. I'm not sure how you get to $26^n$.

You are writing "$4$ is more than $O(n)$" (where $n=2$). This is completely meaningless, since $O(n)$ stands for a function bounded by $Cn$ for some unknown constant $C$. If you don't know the value of $C$ (in this case, $C=25$) then you cannot possibly determine that $4 \> Cn$.

---
Tags: graphs, breadth-first-search
---


# Question
Title: Is solving a quadratic equation using Turing machine impossible?
I've just started Algorithms at university. There's a task to write an algorithm for a Turing machine to solve quadratic equations. The task doesn't specify if it's x^2+bx+c or ax^2+bx+c. I've searched whole bunch of information over Russian and English Internet.

I did find articles, which say it's not possible because we've got real numbers A, B, C. Please confirm if that's true. I may not get it correct.. But I think that's impossible. I still don't know how to prove my thoughts.

Thanks in advance!

# Answer
The problem is not clear enough. Turing Machines can or cannot solve problems if those problems are languages, that means, sets of strings over a finite alphabet. You cannot represent all reals in this way, so it is not even a problem that a TM could even attempt to solve. In the same fashion that world hunger is not a problem in the precise sense that a computational complexity requires it to be.

The problem is obviously solvable if you define it as the sets of words that encode three rational numbers a, b and c in a standard way. How do you solve this? Well, the construction of the machine that does this is rather complicated, but you know how to do this in let's say, Python, right? So you can always compile your Python code into a TM.
> 2 votes

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


# Question
Title: Logarithmic space verifier with unbounded witness
this is a HW question, but its considered a bonus question so I'd appreciate a direction.

**Definitions:**

**The actual question:**

\**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.

**My thoughts on the question:**

My intuition is that C2 = NL, because NSPACE(O(f(n)) ⊆ DTIME(2^O(f(n))), so for a verifier for a language in C2 as defined in the question, as it anyway runs in logarithmic space will run in polynomial time and therefore it won't be able to read more than a polynomial length witness so it doesn't add power. I already proved that the set of languages that are decided by a logspace verifier with read once witness tape and polynomial length witness are NL.

So more formally:

**For Nl ⊆ C2**, then for a language L that is in NL and decided by a logspace NTM M, it feels to me like I could just treat the witness as a configurations sequence that describes the choices that M did, and just check the validity of the transitions according to the delta function of M and accept only if all transitions are valid and the last configuration is accepting. This will need logarithmic space. So L in C2 (basically this is the same as bounded length witness case).

**For C2 ⊆ NL:** This feels harder. Denote L as a C2 language that is decided by a verifier as defined in the question. When I think about this, the verifier can read from the witness tape without writing the content to the work tape, so it could read the whole witness and still remain in the logarithmic space bound, and it would be equal to a NTM that performs |w| (length of the witness) of non deterministic choices while using logarithmic space on its work tape. Basically it means the NTM makes unbounded number of choices.

So on one hand, I don't think the definition of a NL NTM bounds the number of non-deterministic decisions (as long as the space complexity holds). So even with the arbitrary number of non deterministic choices, the complexity class is still NL because the space complexity doesn't change. But on the other hand, this means a "deeper configuration graph" and it feels like the time complexity of this NTM is greatly increasing and it doesn't feel right.

So in the case that the number of choices doesn't affect the complexity, this will mean that C2 ⊆ NL cause every time the verifier reads a character of the witness, we can make a non deterministic choice for that character and simulate the verifier.

But if this is wrong, then I'm not sure how to proceed.

**I would appreciate pointing me to the correct direction, thanks!**

\*** Again, this is not for submission, by I would really like to solve it.

# Answer
Let $N$ be the total number of configurations of the machine other than the witness tape, namely state, location of the input tape head, contents of the work tape, and location of the work tape head. Note that $N$ is polynomial in $n$.

We can assume without of generality that at each step, the machine reads a bit from the witness tape, and it affects its decision (we can accommodate that by adding dummy bits to the witness tape at locations where the original machine doesn't read the witness tape). The machine terminates once the witness tape runs out.

I claim that for any witness $w$, there is an equivalent witness $w'$ with $|w'| \< N$. Here *equivalent* means that when the machine terminates, it is in the same configuration. The proof resembles that of the pumping lemma: if $|w| \geq N$, then some configuration must repeat, and so we can remove the corresponding part from the witness.

Thus, without loss of generality, the witness is of size at most $N=\operatorname{poly}(n)$. So this definition coincides with the usual definition of $\mathsf{NL}$.
> 2 votes

# Answer
$C\_2 \subseteq NL$: Let $L \in C\_2$. Let the log-space verifier for $L$ be $T$. We can construct a log-space NTM $T'$ which on any input simulates $T$ on the same input. Whenever $T$ tries to read the witness-tape, $T'$ just non-deterministically guesses an alphabet.

This will have the same effect as having a read-once witness tape.
> 1 votes

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


# Question
Title: If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?
Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$.

The $powers~of~2$ have only one 1-bit at the start of the binary-string.

## Verify Solution Efficently

```
n = 8
N = 3
IF only ONE 1-bit at start of binary-string:
  IF total_0-bits == N:
   if n is a power_of_2:
     OUTPUT solution verified, 2^3 == 8

```

A solution will always be approximately $2$^$N$ digits. Its not possible for even a non-deterministic machine to arrive to a solution with $2$^$N$ digits faster than $2$^$N$ time.

**Question**

*Can this problem be solved efficently in non-deterministic poly-time? Why not if the solutions can be verified efficently?*

# Answer
You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$).

If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^n$. This problem can indeed be solved (and thus verified) in polynomial time.

If you choose to talk in terms of function problems, then the problem is given $n$, compute $2^n$. This cannot be done in polynomial time, even with non-determinism, but just because the output is exponentially big with respect to the input. Verification has nothing to do here.
> 4 votes

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


# Question
Title: Unification Algorithm without Occur Check
I have been reading about Unification algorithm here https://en.wikipedia.org/wiki/Unification\_(computer\_science)#A\_unification\_algorithm . And I wonder about the importance of occur check.

I know that without occur check an unsound inference may occur. But OTOH, does the algorithm always terminate without occur check? If the two literals to unify have no variables in common I feel like the algorithm should at least always terminate right?

# Answer
Say you tried to solve $f(A, g(A)) = f(B, B)$ after applying $A \to B$ you'd then have $f(A, g(A)) = f(A, A)$ and you'd have to unify $A = g(A)$ as a sub problem.
> 1 votes

---
Tags: logic, first-order-logic, propositional-logic, unification
---


# Question
Title: Efficient way to concatenate strings to find specific split up values
I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting to implement a method that searches for a specific (given) value and returns the Section object(s) it found the value in. There are however two different scenarios as described below.

Value: *restaurant*

**Scenario 1**

1. "John went to the restaurant to pick " ✔
2. "up the food he ordered online before "
3. "he went to his mother's house."

Current behaviour: Found in Section 1

Desired behaviour: Found in Section 1

**Scenario 2**

1. "John went to the restaura"
2. "nt to pick up the food he ord"
3. "ered online before he went to his mother's house."

Current behaviour: Couldn't find the value

Desired behaviour: Found in list(Section 1, Section 2)

---

Scenario 1 is easily solved as the value is found completely in section 1. In the 2nd scenario, the value is never found as it is split up between sections. I have written an algorithm that tries to stitch these sections together. It appears to work when the given value is simple e.g., "car" or "boat". I'm having troubles with compound strings such as "the supermarket" or "a green flower". I wrote the code a couple of months ago and tried debugging it, but even I fail to understand my own code here.

I deliberately left my code out of this post as it has rough hardcoded rules and has extreme levels of code complexity. I'd like to rethink the algorithm without looking at the current one to refrain from blatantly copying sections of the existing code.

The code is written in Java in case anyone knows some handy Java functions that might help.

# Answer
> 1 votes
If all the words are going to be English words, you can run all the words through a dictionary. If you find any non-dictionary words at the start or end of the sections and you are unable to find the "key", you can just combine those words until the key is found.

Alternatively, you can trivially just combine the the words (once) at the start/end of sections until the word is found. I don't believe this will to too inefficient computationally since the described sections are quite large.

# Answer
> 0 votes
First , you'll have to create a `List<String>` , which will **contains all possible substring**s of your desired value , **then you will search if any of the lines contains at least one of the elements of the list**

* *Example :*

*value* : "abc"

*List of possible susbtrings* : { "a" , "b" , "c" , "ab" , "bc" , "abc" }

*The phrases* : { "I want to find ab" , "c here it is" }

**The 2 phrases contains "ab" and "c" , their concatenation is equal to the value , so the phrases contains the value**

---
Tags: algorithms, strings
---


# Question
Title: What purpose was the Von Neumann machine intended for? And what hardware limitations existed when von Neumann invented it?
Its namesake invented the Von Neumann architecture (VNA) in a specific computing environment and a specific context. In light of those two:

1. What kind of *limitations* was the VNA designed to work with?
2. What features in the VNA reflect that?
3. What kind of purpose did Von Neumann intend for the VNA?
4. How did the design of the VNA accomplish his purpose?

# Answer
The von Neumann architecture was built for sequential computing. It was groundbreaking because it combined the instructions in memory along with the data for the instructions in the same space. Before this, programming required rewiring because each machine was built with a specific purpose in mind.

The essential idea is abstraction on some level. The people who design the actual machines don't need to concern themselves with what software will be written for the machine. Rather, they make a few basic commands extremely efficient. The software teams then efficiently use these commands, allowing a generalizable/abstractable computer model.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?
Equip any complexity classes $C$ and $B$ (to be more specific: any complexity classes that contain only decidable problems) with the same oracle $O$ that solves the halting problem for a Turing Machine. Is $C^O = B^O$ for any $B$ and $C$ that, again, only contain problems decidable by a TM with no access to an oracle (only the empty oracle)?

# Answer
> 3 votes
No, they are not in general - and focusing on the halting problem specifically makes the situation look more complicated than it actually is. The real point is the following:

## There are lots of separation results which relativize to all oracles.

*There's a slight technical issue here, actually: how exactly should we treat space-based complexity classes in the oracle context? See the bottom of page $5$ here. I'll only talk about time-based classes here to avoid having to think about this.*

For example, the classical argument that $\mathsf{P}\subsetneq\mathsf{EXPTIME}$ in fact shows that $$\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$$ for every oracle $A$. In particular, we can take $A$ to be the Halting Problem. Another example of a separation which relativizes to all oracles - including the halting problem - is the time hierarchy theorem.

This topic is treated in chapter $3$ of Arora/Barak:

> "Any result about TMs or complexity classes that uses only Properties I and II above also holds for the set of all TMs with oracle $A$. Such results are called relativizing results. All of the results on universal Turing machines and the diagonalizations results in this chapter are of this type."
>
> *(pg. 72; I've replaced their "$O$" with an "$A$" to avoid conflict with your use of "$O$" for the halting problem specifically.)*

Of course not everything relativizes - and see in particular Baker-Gill-Solovay \- but *some* things do relativize, and all relativizing separation results yield negative answers to the OP as special cases.

---

Just for completeness, here's one proof that $\mathsf{P}^A\not=\mathsf{EXPTIME}^A$ for any oracle $A$ goes; unsurprisingly, it's a direct diagonalization. Fix an oracle $A$; we want to show $\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$. We'll use an exponential-time machine with oracle $A$ to diagonalize against polytime machines with oracle $A$. Fix appropriate enumerations $(\Phi\_i)\_{j\in\mathbb{N}}$ and $(p\_j)\_{j\in\mathbb{N}}$ of oracle machines and polynomials respectively and an appropriate pairing function $\langle\cdot,\cdot\rangle$, and let $$X=\\{\langle a,b\rangle: \neg\Phi\_a^A(\langle a,b\rangle)\[p\_b(\lfloor\log (\langle a,b\rangle)\rfloor)\]\downarrow=1\\}$$ (here "$\[s\]\downarrow=$" means "halts in $s$ steps and equals"). By construction we have that $X\not\in \mathsf{P}^A$ *(suppose $\Phi\_a^A$ decided it in time $p\_b$ ...)*; however, the "brute force" calculation of $X$ from $A$ only takes exponential time, so $X\in \mathsf{EXPTIME}^A$.

**Note that this is just the usual proof, with an "$A$" superscript added everywhere.** The point is that diagonalization is such a "coarse" technique that - when it works at all - it tends to work for all objects *like* Turing machines. And this includes Turing machines relative to a fixed oracle.

# Answer
> 1 votes
No. Consider $RE^O = \Sigma^2\_0 \neq \Pi^2\_0 = (coRE)^O $.

Thanks @Noah Schweber for pointing out a big mistake in my original answer. See his answer for a much more general treatment of the question.

# Answer
> -1 votes
~~If I have understood your question correctly, the answer would be no.~~

~~Here is a counterexample: Let C be the complexity class of finite state automata. The halting problem for C is thus computable by a turing machine, hence the problems that C^O can solve is a subset of the problems that a turing machine can solve. Let B be the complexity class of turing machines. The halting problem for B is not computable by a turing machine, hence B^O contains problems that C^O does not, and hence B^O and C^O are not equivalent.~~

As it turns out I have misunderstood your question.

If you meant for both oracles to be able to solve the halting problem for any turing machine, the answer is that they are equal. This is because an oracle for the turing machine can solve any problem a turing machine can solve, as it the oracle can just compute whether a turing machine would return a certain result for a certain input.

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?
I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and $x$, you clearly get out of language when you pump up. If you do the same with $b$'s and pump down, you get out of language as well. But how dow do you show situation where there are only $a$'s in $v$ and just $b$'s in $x$?

Thank you

# Answer
Suppose towards a contradiction that $L$ is context-free and let $c$ be the pumping length of $L$. Consider the word $a^{c^2} b^c$ which, by the pumping lemma, can be written as $uvwxy$ with $1 \le |vx| \le c$.

Notice that:

* $vx$ cannot contain only $b$s, since otherwise $uwy \not\in L$.
* $vx$ cannot contain only $a$s, since otherwise $uv^2wx^2y \not\in L$.
* none of $v$ and $x$ contains both $a$s and $b$s, since otherwise $uv^2wx^2y \not\in L$.

We conclude that $v$ contains only $a$s, $x$ contains only $b$s, and $x$ contains at least one $b$. Then, by the pumping lemma, $a^{c^2-|v|} b^{c-|x|} = uwy \in L$. This is a contradiction since: $$ (c - |x|)^2 \le (c - 1)^2 = c^2 - 2c + 1 \le i^2 - c \< i^2 - |v|. $$
> 1 votes

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


# Question
Title: What is the fastest algorithm to solve $k$-path problem?
**$k$-Path problem**

**The problem:** Given a graph $G$ with $n$ vertices and $m$ edges, does there exist a path of length $k$ in the graph?

The trivial algorithm to solve is in $O^\*(n^k)$ time using dynamic programming. ($^\*$ hides the polynomial factor.)

**Question:** What is the fastest algorithm for the $k$-Path problem?

# Answer
> 3 votes
For FPT algorithms (ignoring the polynomial factors), there is a $2.851^k \cdot n^{O(1)}$ deterministic algorithm and a $1.66^k \cdot n^{O(1)}$ randomized algorithm.

See Table of FPT races for references.

---
Tags: algorithms
---


# Question
Title: What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"?
What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)

# Answer
The notation $\tilde{O}(f(n))$ is not completely standard and is usually defined as $\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $\tilde{O}(n^2)$ in place of $O(n^2 \frac{\log^3 n}{\log \log n})$.

That said, in your paper $\tilde{O}(f(n))$ seems to be used as a shorthand for $O( f(n) \cdot \text{poly} \log n)$, although I was not able to find a definition within the paper by quickly skimming it. This only differs from the previous definition when $f(n)$ is smaller than or larger than any polynomial.

In the specific sentence you are quoting, the authors want $\Lambda$ to be in $O(\text{poly} \log M)$.
> 2 votes

---
Tags: complexity-theory, algorithm-analysis, error-estimation
---


title: Converting Polynomials into Binary form

text:
# Question
Title: Converting Polynomials into Binary form
How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$

# Answer
> 6 votes
Just put the value of $x=10$ then

$$10^3+1=1001$$

# Answer
> 6 votes
The polynomial notation is a shortcut to write binary code while omitting the zeros, it's useful to crunch CRC communication checksum to verify electric signal quality with an XOR comparison operation. Then a binary code like 1 1000 0000 0000 0101 may be noted $x^{16} + x^{15} + x^2 +1$.

# Answer
> 3 votes
For converting polynomial to its binary form $$p(x) = x^{3} + 1$$ you have to first reduce the coefficients mod 2. This gives us $$x^{3} + 1$$ Now simply substitute $x=2\\;$ and evaluate, this gives the d+1 bit number(where d is degree of the polynomial):

$$1000\_2 + 0001\_2 = 1001\_2 = 9\_{10}$$

for ex: $$p(x) = x^2-x$$ for each coefficient of p(x) take mod 2 then this gives us : $$p'(x) = x^2-x$$ Now, substitute x = 2 (since degree of polynomial is 2 then it gives us 3(=2+1) bit number) and convert each value to its binary form then evaluate it $$100\_2 - 010\_2 = 010\_2 = 2\_{10}$$

# Answer
> 1 votes
For this example: $x^7 + x^5 +1$

1. Look at the degree of the polynomial. In the case of the above example it is 7.
2. Write down all numbers from the degree of the polynomial down to 0. These will correspond to the exponents of $x$ in the polynomial. In our case:

7 6 5 4 3 2 1 0
3. And, finally write a 1 under each exponent for which that power of $x$ occurs in the polynomial, and 0 under the others. Like this:

7 6 5 4 3 2 1 0

1 0 1 0 0 0 0 1

So the result is 10100001. Basically you are replacing each power of $x$ with a 1, and replacing the powers that do not occur with a 0.

Note: The last digit stands for 1 because that is $2^0$.

---
Tags: arithmetic, polynomials
---


title: Maximum Circular Subarray sum

text:
# Question
Title: Maximum Circular Subarray sum
This is a question from the book Algorithms by Jeff Erickson.

Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A\[i .. j\] or a suffix followed by a prefix A\[i .. n\] · A\[1 .. j\]. Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum. The input array consists of real numbers.

My approach:

There are two possibilities

1.) No Wrapping around (We can use Kadane's Algorithm)

2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)

Now return the maximum of two cases as result.

For the second case, searching on the internet provided an approach without proof.

The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) - min\_subarray\_sum(A)). How is this solution correct?

Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

# Answer
Let $A$ be your array, let $B$ a circular subarray of $A$ that maximizes $\sum\_{b \in B} b$, and let $C$ be the subarray that contains all elements of $A$ that are not in $B$. Notice that $C$ is also a circular subarray.

You have $\sum\_{a \in A} a = \sum\_{b \in B} b + \sum\_{c\in C} c$, which implies that $\sum\_{c \in C} c = \sum\_{a \in A} a - \sum\_{b \in B} b $. Since $\sum\_{a \in A} a $ is a constant (w.r.t. $B$) and $B$ maximizes $\sum\_{b \in B} b$, $C$ minimizes $\sum\_{c \in C} c$.

Moreover, at least one of $B$ and $C$ is not only circular but also contiguous and can therefore be found in $O(n)$ time.
> 2 votes

---
Tags: algorithms, arrays, maximum-subarray
---


# Question
Title: Is there an undecidable language that is mapping reducible to its complement?
Is there an undecidable language A that is mapping reducible to its complement?

If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don't know whether undecidable languages is closed under complement or not.

# Answer
Yes, it is possible. Enumerate the set of all possible Turing machines and let $H$ (resp. $\overline{H}$) be the set of indices of the Turing machines that halt (resp. do not halt) on empty input.

Let $L = \\{ \langle T, 1 \rangle \\, : T \in H \\} \cup \\{ \langle T, 0 \rangle \\, : T \in \overline{H} \\}$.

Clearly $L$ is not decidable but it is possible to reduce $L$ to $\overline{L}$ since $\langle T, r \rangle \in L \iff \langle T, 1-r \rangle \in \overline{L}$.
> 1 votes

---
Tags: formal-languages, undecidability
---


title: Maximizing book picked using two stacks

text:
# Question
Title: Maximizing book picked using two stacks
There are two stacks $S\_1$ and $S\_2$ of books. Each book in stack has a weight. You are given a net weight $W$ of books that can be picked. You have to maximize the number of books that can be picked. Note that each time you can either pick from $S\_1$ or $S\_2$ only.

eg: $S\_1 = \langle 5, 1, 1\rangle$, $S\_2 = \langle 1,2,6 \rangle$, $W=10$.

So the answer is $5$ (pick $1$ and $2$ from $S\_2$, then all elements from $S\_1$)

I know this question can be done with a greedy approach by comparing top elements of both stacks, but can we solve it with the concept of trees?

Is there any other data structure that can be used to solve this problem?

# Answer
> 1 votes
The greedy algorithm does not always work. Example: $S\_1 = \langle 3, 1, 1,1\rangle$, $S\_2 = \langle 2, 2,2\rangle$, $W=6$.

In general, let $S\_1 = \langle x\_1, \dots, x\_k \rangle$ and $S\_2 = \langle y\_1, \dots, y\_h \rangle$. I will assume that individual book weights are positive integers. To solve your problem optimally you can use a sliding-window approach. Compute, for each $i=0,\dots k$, the quantity $X\_i = \sum\_{j=1}^i x\_i$. Similarly, for each $i=0,\dots,h$ compute $Y\_i = \sum\_{j=1}^i y\_i$.

Now start with $i=0$ and $j=h$ and iteratively do the following:

* If $X\_i + Y\_j \le W$ consider the solution $(i,j)$ that selects $i$ elements from $S\_1$ and $j$ elements from $S\_2$ as a *candidate* solution.
* If $i=k$ and $j=0$ stop and return the solution that maximizes $i'+j'$ among all candidate solutions $(i',j')$.
* If $X\_i + Y\_j \le W$ and $i\<k$, or if $j=0$, increment $i$ by $1$.
* Otherwise, decrement $j$ by $1$.

To see that this algorithm must work consider an optimal solution that selects $i^\*$ books from $S\_1$ and $j^\*$ books from $S\_2$. Since, at the end of the algorithm, $i=k$ and $j=0$ there must be some iteration for which $i=i^\*$ or $j=j^\*$. Consider the first such iteration.

If $i=i^\*$ then $j \ge j^\*$ meaning that for all $j' = j^\*+1, \dots, j$ we must have $X\_i + Y\_{j'} \> W$. This shows that in the next $j-j^\*$ iterations $j$ will be decremented until it reaches $j^\*$.

If $j= j^\*$ then $i \le i^\*$ meaning that for all $i' = i, \dots, i^\*-1$ we must have $X\_{i'} + Y\_j \> W$. This shows that in the next $i^\*-i$ iterations $i$ will be incremented until it reaches $i^\*$.

In any case the pair $i=i^\*$ and $j=j^\*$ is considered by one iteration of the algorithm and, since $X\_{i^\*} + Y\_{j^\*} \le W$ the solution $(i^\*,j^\*)$ must be one of the candidate solutions.

A straightforward implementation requires linear time in the combined size $n$ of the two stacks.

Since you can actually stop computing $X\_i$ (resp. $Y\_i$) as soon as $X\_i \ge M$ (resp. $Y\_i \ge M$) you can reduce the time complexity to $O(\min\\{n, W\\})$.

# Answer
> 0 votes
```
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner r =new Scanner(System.in);
        int arr1[]= new int[3];
        int arr2[]= new int[3];
        int w=r.nextInt();
        int temp[]= new int[3];
        int sum=0,cnt=0,flag=1;
        for(int i=0;i<arr1.length;i++){
            arr1[i]=r.nextInt();
        }
        for(int j=0;j<arr2.length;j++){
            arr2[j]=r.nextInt();
        }
        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){
                if(arr1[i]<arr2[j]){
                    temp[i]=arr1[i];
                    if(sum<w){
                        cnt++;
                        sum+=temp[i];
                        flag=0;
                    }
                }
                else{
                    temp[i]=arr2[j];
                    if(sum<w){
                        cnt++;
                        sum+=temp[j];
                        flag=0;
                    }
                }
            }
        }
        if(flag==0){
            if(w==sum){
                System.out.println(cnt);
            }
        }
  }
}

```

---
Tags: data-structures, trees, stacks
---


title: CFG for a given languague

text:
# Question
Title: CFG for a given languague
Give a CFG for the languague L = $ \\{ 1^n +1^m = 1^{n+m}| n,m \in N\_{0}\\} $ , with the alphabet $\Sigma =\\{1,+,=\\}$.

I am currently trying to solve the given task, I thought a good way is to split the Languague into two more simple languagues, but I am keep failing. May some can help

# Answer
The idea is to start generating the ones of the first addend from the axiom $S$, while simultaneously adding the corresponding number of ones at the end of the sentential form. Then you have a production from $S$ to non-terminal $A$ which takes care of generating the second added, while still appending ones at the end of the sentential form.

When you are done generating the second addend you can replace $A$ with $=$ in order to split all the ones from the two addends (on the left side) from the corresponding number of ones on the right size.

$$ \begin{align\*} S &\to 1S1 \mid +A \\ A &\to 1A1 \mid \\,= \end{align\*} $$
> 2 votes

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


# Question
Title: Is it possible to sort a linked list without copying its values but linking the nodes?
Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.

Also can this be done in a quadratic time?

I will be attempting this in Python.

# Answer
> 1 votes
Copy the list into an array, sort the array, construct a linked list from it. Done. It suffices to populate the array with pointers (references) to the values; you don't need to copy the values themselves. The running time will be $\Theta(n \log n)$ if you use an appropriate sorting algorithm -- much faster than quadratic time.

# Answer
> 1 votes
Quicksort and mergesort can both be implemented to work directly on a linked list with just $O(1)$ extra space. This actually improves the space complexity of the usual mergesort, which ordinarily requires $O(n)$ working space (this is because the pointers actually constitute $O(n)$ extra space themselves). As usual, mergesort will take $O(n\log n)$ time in the worst case, while quicksort has an $O(n^2)$ worst-case time but is $O(n\log n)$ on "most" inputs.

For quicksort, on each subproblem you can walk the list to find a suitable pivot without hurting the asymptotic complexity. Each partition step consists of simply growing 2 lists, those \< the pivot and those \>= it. Then append the pivot to the end of the first list, and the second list to that.

For mergesort, to find the halfway point of a singly linked list, walk 2 pointers forward, with one (the "hare") advancing twice at each step and the other (the "tortoise") only once. Once the hare reaches the end, the tortoise is halfway. Now you can merge the two half-length sublists that begin at the start of the original list, and at the tortoise.

Insertion sort can also be straightforwardly implemented to run directly on a linked list, but this is probably a bad choice as its performance will be $O(n^2)$ unless the list is already nearly *reverse-sorted* (note the difference to the array version in which insertion sort is fast on nearly *sorted* inputs). This is because the intermediate solution gets built by taking the next element and appending it to the *front* of the result, meaning it gets built in reverse order.

# Answer
> 0 votes
If you really, really want no extra space, you can do bubble sort. Normally bubble sort works on an array, starts at the first item, proceeds to the last item and exchanges consecutive items. You can do all this with a linked list.

---
Tags: sorting, linked-lists
---