# Question
Title: Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)
The problem (copy-pasted from this question on cs.stackexchange):

Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either **red** or **blue**, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

My algorithm:
We first add weights to the edges:
If the edge goes into a red vertex, we let its weight be -1.
If the edge goes into a blue vertex, we let its weight be 1.
Any edge going into $t$ has weight 0.

This way, any path from $s$ to $t$ with negative weight is a solution.

We now formulate a linear program, which finds the path with lowest weight from all paths with length $\le c$ (i.e. it only looks at paths with $\le c$ edges ):

Minimize the function: $$ \sum\_{e\in E} c\_e\cdot x\_e $$

Under the constraints: $$ \forall v\in V-\\{s,t\\}: \sum\_{e\in in(v)}x\_e -\sum\_{e\in out(v)} x\_e = 0 \\ \sum\_{e\in out(s)} x\_e = 1 \\ \sum\_{e\in in(t)} x\_e = 1 \\ \sum\_{e\in in(s)} x\_e = 0 \\ \sum\_{e\in out(t)} x\_e = 0 \\ \sum\_{e\in E} x\_e \le c \\ \forall e\in E: x\_e \ge 0 $$

Here $c\_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

This linear program is, except for the constraint $\sum\_{e\in E} x\_e \le c$, identical to the one which I asked about in my previous question, and in which it is proved that that linear program indeed returns a shortest path.

Even with the newly added constraint $\sum\_{e\in E} x\_e \le c$ to me it looks like my previous reasoning is still valid.

If that were the case however, we could solve the linear program for $c=1,...,|E|$, and for each solution check whether its weight is negative. If we find any solution for which the weight is negative, we have a path as is requested by the problem.

If all solutions have positive weight, then there is no such path.

As each LP-program runs in polynomial time, and we have to run $|E|$ variations of this program, the whole algorithm should still be run in polynomial time.

This however clashes with the fact that the problem itself is NP-hard.

So, somewhere in my reasoning is a mistake (most likely the result of the linear program doesn't have to be a path anymore or something similar) - however, I simply can't find what exactly is going wrong. Where is it?

---

Edit:

The reasoning (copied from the previous question) for the correctness of the linear program:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$ is an $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p\_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality: $$1\cdot p\_{min} \le \sum\_{p\in M} \lambda\_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda\_p \ge 0 , \sum\_{p\in M} \lambda\_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.

# Answer
> 1 votes
In your program specification, "$\forall e\in E: x\_e \ge 0$" should be "$\forall e\in E: x\_e=0\text{ or } 1$".

"Each LP-program runs in polynomial time". However, your instance is an instance of integer linear programming (ILP), which is NP-hard, even when all variables are restricted to be either 0 or 1. In particular, this answer shows that the instances of ILP as given in this question is NP-complete.

---
Tags: graphs, linear-programming
---


# Question
Title: prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction

\*Edit: my professor had a significant typo in this assignment, I have attempted to correct it.

I am trying to construct a proof by induction to show that the recursion tree for the nth fibonacci number would have exactly n Fib(n+1) leaves.

that is to say that the complete recursion tree generated by the function F(n), which returns the nth fibonacci number in the sequence, has the same number of leaves as the number returned by the F(n+1), the n+1st fibonacci number.

Edit: The complete recursion tree for n = 5 would look like this

```
                         F(5)
                      /        \
                 F(4)           F(3)
                /   \          /    \
             F(3)   F(2)      F(2)  F(1)
            / \      /  \     /   \
         F(2) F(1) F(1) F(0) F(1)  F(0)
        /   \
     F(1)  F(0)

```

# Answer
To compute the nth Fibonacci number, expressed as Fib(n), we use the following formula, noting that n is a positive integer:

```
 Fib(n)= { 0 if n = 0
           1 if n = 1
           Fib(n - 1) + Fib(n - 2) if n > 1

```

we want to show that the complete recursion tree for the nth Fibonacci number has the same number of leaves as the value that Fib(n+1) evaluates to.

For n = 0 there are no recursive calls made. This is because for values of n such that n \< 2, the function is not defined recursively in terms of the sum of the previous two numbers in the sequence. Instead, the function is defined merely as a constant, in this case 0. Because of this, if one were to attempt to draw a recursion tree, there would be only one single node, the root Fib(0) with no subsequent children. This essentially represents the fact that no recursive function calls are made during an invocation of Fib(0).

In this case, counting the only node in this trivial tree, the root Fib(0), as itself a leaf since it has no children, you can conclude that the complete recursion tree for Fib(0) contains only one leaf. Noticing that for n = 0, the number that Fib(n+1) evaluates to = Fib(1) = 1. We can thus conclude that for the case n = 0 the number of leaves in the recursion tree of Fib(n) is indeed equal to the value that Fib(n+1) evaluates to.

Similarly, for n = 1 there are also no recursive calls made. The reasoning is much the same as described above. For n \< 2, the function is not defined recursively as the sum of the previous two numbers and instead is defined only as a constant, in this case 1. Again following the same logic outlined above, we can easily see that, a complete recursion tree for this value of n would again be a trivial tree with only the root Fib(1) and no children.

Once again we can consider this trivial, single node tree to have one leaf being the root F(1) since it again has no children. Noticing that for n = 1, the number that Fib(n+1) evaluates to = Fib(2) = 1. We can again conclude that the number of leaves in the complete recursion tree of Fib(n) is equal to the number that Fib(n+1) evaluates to.

Thus, having proved the trivial base cases for n = 0 and n = 1, we assume that for all k \>= 2, the number of leaves in the complete recursion tree produced by Fib(k) is equal to the value that Fib(k+1) evaluates to.

Then, by the inductive hypothesis, this must also be true for the

(k +1)st term in the sequence. Taking this into account, we can say that the number of leaves in the complete recursion tree produced by Fib(k+1) must be equal to the value that Fib((k+1)+1) or Fib(k+2) evaluates to.

Because k is \>= 2 and therefore the function is indeed defined recursively as the sum of the previous two terms, we can rewrite Fib(k+1) as (Fib(k) + Fib(k-1)).

Similarly, we can rewrite Fib(k+2) as (Fib(k+1) + Fib(k)), then we can restate the statement that we are trying to prove, and we can say that the number of leaves in the complete recursion tree produced by \[Fib(k) + Fib(k-1)\] must be equal to the value that \[Fib(k+1) + Fib(k)\] evaluates to.

If we let n equal a term in the sequence defined by Fib(k) + Fib(k-1), then the next number in the sequence, the (n+1)st term, would be defined by Fib((k) +1) + Fib((k-1)+1) which simplifies to:

Fib(k+1) + Fib(k) which, by the definition of the Fibonacci function, is equal to Fib(k+2) which proves our inductive hypothesis to be true.
> 1 votes

# Answer
Apparently, the question is messed up. Either the original homework question is wrong or there is serious misunderstanding reading or copying the original homework question.

Here is the correct title and question, "How to prove the complete recursion tree for computing $F\_n$ has $F\_n$ leaves where $F\_n$ is the $n$-th Fibonacci number?". Here the Fibonacci sequence is defined classically by $F\_1=1$, $F\_2=1$ and $F\_{n+1}=F\_n + F\_{n-1}$. Note that we exclude $F\_0=0$.

The complete recursion tree for n = 5 would look like the following, where we have $5=F\_5$ leaves.

```
                      F(5)
                    /      \
                 F(4)      F(3)
                 /  \      /  \
              F(3)  F(2) F(2) F(1)
              /  \
           F(2)  F(1)

```

The proposition $P(n)$ for $n\ge1$ is the complete recursion tree for computing $F\_n$ has $F\_n$ leaves. The base case $P(1)$ and $p(2)$ are true by definition. If we use strong induction, the induction hypothesis $IH(k)$ for $k\ge2$ is for all $n\le k$, $P(n)$ is true. It should be routine to prove $P(k+1)$ given $IH(k)$ is true.

The main point of this answer is to point out the number of leaves in the complete recursion tree for computing $F\_n$, the $n$-th Fibonacci number should be $F\_n$ if $F\_0=0$ is not in the definition of Fibonacci sequence. Or it should be $F\_{n+1}$ if $F\_0=0$ is included in the base case and $F\_2$ is not included in the base case.

---

Here is an easy exercise to describe the general situation.

**Exercise.** Let $S\_1, S\_2, \cdots$ be a sequence defined by $S\_1=a$, $S\_2=b$, $S\_{n+1}=S\_{n}+S\_{n-1}$ for some $a$ and $b$. Show that the complete recursion tree to compute $S\_n$ has $F\_n$ leaves, where $F\_n$ is the $n$-th Fibonacci number.
> 2 votes

---
Tags: trees, proof-techniques, recursion, induction
---


# Question
Title: Dynamic programming approach for finding perfect square subsequence
Given an array of numbers $a\_i$ with length $n$, such that $0\<a\_i\<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.

# Answer
Let us assume first that by *subsequence* you mean *non-contiguous subsequence*.

There are 10 primes in the range $1,\ldots,29$: $$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$ You can represent each number in the range $1,\ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

---

Suppose now that you’re after *contiguous* subsequences.

Let $b\_i = a\_1 \cdot a\_2 \cdots a\_i$. The subsequence $a\_i,\ldots,a\_j$ multiplies to a perfect square iff $b\_j/b\_{i-1}$ is a perfect square, which happens if the vectors corresponding to $b\_{i-1}$ and $b\_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b\_i$ (do this by computing the vectors for $a\_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c\_1,\ldots,c\_\ell$. The answer is then $\sum\_i \binom{c\_i}{2}$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: How does KMV (k minimum value) perform set intersection better than hyperloglog?
In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams.

`Set Intersection. multiKMV can be tweaked in a natural way to handle set intersection and other set operations.`

I am having a hard time understanding how intersection on kmv set can perform intersection accurately

The way I understand it, KMV can be describe by the following

Given a stream of number $x = \[x\_1, .... x\_n\]$ if we hash each number in $x$ and produce $h = \[hash(x\_1).....hash(x\_n)\]$

KMV attempts to represents and capture the characteristic of the stream by storing $k$ minimum value of $h$

The intersection of 2 streams is basically the naive intersection of 2 kmv set.

However this can't be true because if its true the operation is lossy, and probably cannot sustain more than a couple intersection without loosing its accuracy on estimating cardinality.

Can someone point me a direction on how kmv achieve accurate cardinality estimation of 2 or more streams?

# Answer
There is no sketching algorithm that is able to estimate the intersection cardinalities without accuracy loss. What is meant by the paper is that it is easy to construct KMV sketches that represent the intersection. However, given two $k$-minimum value sketches, you usually cannot construct a $k$-minimum value sketch for the intersection. You rather end up with a $k'$-minimum value sketch with $k'$ smaller than $k$. Since the number of hashes kept within the KMV sketch determines the estimation accuracy, calculating the intersection also comes with accuracy loss.

For HyperLogLog sketches there is no natural way to construct a HyperLogLog that represents the intersection which makes it more difficult to estimate the intersection cardinality. Since HyperLogLogs can be easily merged, a popular way is to use the inclusion-exclusion principle $|A\cap B| = |A| + |B| - |A\cup B|$ to calculate the intersection cardinality. As investigated by the paper, the accuracy loss of this approach is usually much worse than calculating the intersection cardinality for KMV sketches. However, there also exists another (much more complex) technique for HyperLogLogs which uses the maximum-likelihood method and gives better estimates than the inclusion-exclusion principle, see https://arxiv.org/abs/1702.01284.
> 2 votes

---
Tags: algorithms, probabilistic-algorithms
---


# Question
Title: Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes
I was tasked with finding a way to decide the language $A=\\{0^k1^k \mid k\ge 0\\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was asked to check if it is possible to reduce the time from $O(n\log n)$ to $O(n)$ if using a determinstic Turing machine with two tapes (instead of one).

I am really stuck on it and don't know how to implement it. This is what I have so far:

First, we check that in the input word there are no zeros right of the ones. Then, for each zero in the input, we increase a binary counter and for the ones we do the same, creating a binary counter and increasing by one. if the counters are equal, accept, if not, reject. But i don't know how to implement it on a Turing machine, aside from the problem that if the counters of one and zero are far from the writing-reading head, then reaching it would take a lot of steps (time).

Regarding improving it to $O(n)$ time using a deterministic Turing machine with two heads: we go over with one head along the input string until we meet the first 1. then we count the number of one with one tape, and with the other the number of 0's. then we compare and accept if they are equal. So it is basically $k$ steps until the first 1, creating the counter, and counting each 1 $n$ times, then creating a counter with the second tape and comparing to the number of 0's in the beginning until the first one. So the total is $O(n)$. But how do I implement it on a Turing machine?

# Answer
> 2 votes
If you are allowed an auxiliary tape, then the algorithm is very simple:

* Scan to the end of the input, while checking that the input belongs to $0^\*1^\*$.
* Copy the input in reverse to the auxiliary tape, switching 0s and 1s.
* Check that both tapes contain the same word.

If the input is $0^a 1^b$ then the second tape will contain $0^b 1^a$, so the algorithm will accept if and only if $a = b$. It clearly runs in linear time.

If you only have one tape, then the algorithm is more subtle. We scan the input from left-to-right, maintaining a counter just left of the current symbol being scanned. At each step, we do as follows:

* Read the next symbol $\sigma$ and remember it.
* Copy the counter one step to the right; this step takes $O(\log n)$ time.
* Either increment the counter (if $\sigma = 0$) or decrement it (if $\sigma = 1$).

At the end, we accept if the input belongs to $0^\*1^\*$, and additionally the counter has the value zero.

Using crossing sequences, you should be able to show a matching $\Omega(n \log n)$ lower bound for one-tape Turing machines. The idea is to consider the set of inputs $0^m1^m,\ldots,0^{2m}1^{2m}$, and to consider the states that the Turing machine is when it crosses the window between the $m$th and $2m$th position. There must be $m+1$ different crossing sequences, hence there must exist a crossing sequence of length $\log m$, which corresponds to a running time of $\Omega(m\log m) = \Omega(n\log n)$.

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


title: Sizeof function definition in a system

text:
# Question
Title: Sizeof function definition in a system
Why sizeof(int) and sizeof(int \*) takes different value in a system? I mean generally size of integer is 4 B, but size of integer pointer is 8 B. But why they cannot take same value, although their return type is same?

# Answer
> 1 votes
An integer is a value, whereas a pointer to an integer is a *pointer*, that is, a memory address. In most systems, all pointers have the same size, but the objects they point to can have different sizes. For example, in your systems pointers are 8 bytes long, whereas integers come in various sizes — possibly from 1 byte up to 8 bytes.

You might be misled by the specific quirky syntax of C, which allows declarations of the form

```
int a, *b;

```

This declares an integer `a` and a *pointer* `b`. This is just a confusing feature of C syntax.

---
Tags: programming-languages, c
---


# Question
Title: How to find examples of best cases for sorting algorithms?
I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort

If I give an already sorted table ex: {1,2,3,4,5,6,7,8} shouldn't it already be the best case for all of them? If I can be considered a best case for each?

# Answer
Bubble sort can "stop early" should the array already be sorted. Other algorithms have their own advantages or applications, but none of the algorithms mentioned in your question - other than bubble sort - can "stop early".

Therefore for any input Insertion & Selection runtime will be $\Omega (n^2) $, and Mergesort $\Omega(nlog(n))$, so the order of elements doesn't matter at all.

$\bullet $ If you perform bubble sort on an already sorted array, the algorithm can stop when not performing any swaps, and run at $O(n)$

$\bullet $ Merge sort (to which you refer as 'fusion sort' from some reason) is the only algorithm that requires $O(nlog(n))$ rather than $O(n^2)$

$\bullet $ Insertion sort is useful when receiving the array online (one element at a time) and maintaining it sorted. Its noteworthy that since you maintain a sorted array, new elements can be inserted via binary search, which make the insertion sort perform $O(nlog(n))$ comparisons, but still cost $O(n^2)$ due to moving elements.

$\bullet $ Selection sort is very easy to implement and intuitive to explain
> 1 votes

---
Tags: data-structures, asymptotics, sorting
---


# Question
Title: Generalization of Functors to other datatypes?
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$, we have a functor $F$ which contains $f$, but *additionally* also maps morphisms on $A$ to morphisms on $B$ (i.e. maps not only $A$ to $B$ but also maps "structure on $A$" to "structure on $B$").

In the category theory of functional programming, objects $A,B$ are types and morphisms are functions $A\to B$ between types. That means functors map types $A,B$ to other types $X,Y$ and map functions $A\to B$ to functions $X\to Y$. **Functors in functional programming can thus be seen as a mapping between datatypes that additionally also maps the functional structure on those data types.**

My thought was: In the context of object-oriented programming, there really are more kinds of structure on datatypes than just functions between them. For example, given two types $Int$ and $Bool$, we can not only define functions $f:Int\to Bool$, but also things like $p:Int\times Bool$, or more complex datatypes like classes with private component classes.

**Is there a generalization of functors to "mappings between datatypes that also preserve structure", where that doesn't need to be functorial? In particular I'm wondering whether such a concept is used in analyzing programming languages.**

# Answer
> 3 votes
I guess no one else is going to answer this, so I'll take a crack.

First, there's nothing inherently 'functional' about categories, necessarily. For instance, you can make any monoid into a category, where you have one object, and then the arrows from that one object to itself are the elements of the monoid. The identity element is the identity arrow, and composition is monoid multiplication. Then functors between two monoids in this sense are homomorphisms between the monoids; they are functions that preserve identity and multiplication.

Categories are then generalizations of this to situations where the monoid values have types, and can only be multiplied together when the types correspond. The specifics of this work for functions, but it could be a lot of other things, too. You *could* try to devise a category where $Hom(X,Y) = X×Y$, and then functors from/to that category would be obligated to map from/to products.

However, it is also common to define additional structure beyond just being a category. For instance, even for 'functional programming,' you are usually talking about (at least) Cartesian closed categories. These are categories $C$ that have additional structure:

$$-×- : C × C → C$$ $$1 : C$$ $$\[-,-\] : C^{op} × C → C$$

Where $×$ forms binary products, $1$ is a terminal object, and $\[-,-\]$ forms exponentials, so:

$$C(X×Y,Z) \cong C(X, \[Y,Z\])$$

And when you have categories with additional structure like this, you also want to talk about functors that preserve that extra structure. So there are Cartesian closed functors between Cartesian closed categories that map products to products, terminal objects to terminal objects, and exponentials to exponentials.

So, yes, you can describe plenty of structure besides just $Hom$, and talk about maps that preserve all that structure (in various senses), not just functors.

---
Tags: programming-languages, functional-programming, category-theory
---


# Question
Title: Interpretation of an asymptotic notation
Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no algorithm that solves the given problem in $o(m + \log{n})$?

In particular, does it mean that an $O(\log{n})$ algorithm is possible?

# Answer
What this means is:

> For every algorithm solving the problem, it is *not* the case that the worst-case running time $T(m,n)$ in terms of $m,n$ satisfies the following property: for every $c \> 0$ there is $m\_0(c)$ such that for all $n \geq m \geq m\_0(c)$, $$ T(m,n) \< c(m + \log n). $$

This doesn't rule out an $O(\log n)$ algorithm, since $\log n$ doesn't satisfy the property written above.
> 1 votes

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Prove that NP is closed under karp reduction?
A complexity class $\mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B \in \mathbb{C}$ $\implies$ $A \in \mathbb{C}$

How would you go about proving this if $\mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B \in NP$ $\implies$ $A \in NP$

# Answer
> 7 votes
I was able to figure it out. In case anyone (mans in ECE 406) was wondering:

$B \in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where $i$ is the input to $B$.

$A$ karp reducing to $B \implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and same for false case),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

1. Take input $i$ and apply $m$ to yield $m(i)$
2. Apply $b$ with input $m(i)$

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.

---
Tags: complexity-theory
---


title: Task Distribution Algorithm

text:
# Question
Title: Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:

```
| T/M | M1  | M2  | M3  |
| T1  | a11 | a21 | a31 |
| T2  | a12 | a22 | a32 |
| T3  | a13 | a23 | a33 |

```

So, Machine $M\_1$ needs $a\_{11}$ time on finishing Task $T\_1$.

Each machine can process one task everytime. Each single task cannot be splited up. How to find the min finishing time for all tasks in sum? (finishing time of each task include its waiting time and processing time).

I only has a awful enumerate algorithm for this, enumerate all possible solution and find out the min one. That costs $O(n^n)$.

Is there any optimized algorithm for this question?

# Answer
> 0 votes
The problem is also called *scheduling unrelated machines* and as observed in the comments, it is NP-hard.

If you really want an optimal solution, I recommend to use an integer linear programming solver, such as lp\_solve, SYMPHONY or GLPK. The problem can be formulated as an integer linear program as follows:

$$ \sum\_{i=1}^m x\_{ij}=1, \qquad j = 1,...,n $$ $$ \sum\_{j=1}^n p\_{ij} x\_{ij} \le T, \qquad i = 1, ..., m $$ $$ x\_{ij}=0, \qquad \text{if} p\_{ij}\>T $$ $$ x\_{ij} \in \\{0,1\\}, \qquad \forall i, j. $$

Here $m$ is the number of machines, $n$ the number of jobs, $p\_{ij}$ the time required to run job $j$ on machine $i$, and the variable $x\_{ij}$ stands for 1 or 0 depending whether the job $j$ will be assigned to machine $i$ or not. The number $T$ is a parameter: if the integer linear system can be satisfied, then there is an assignment of jobs to machines that has overall finishing time (makespan) at most $T$. For any given $T$, the integer linear programming solver will tell you if the system is feasible (and if so, what are the values $x\_{ij}$). Then you can find the best value of $T$ (and the corresponding $x\_{ij}$s) by running a simple binary search.

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


# Question
Title: Does "$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$" hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals?
Suppose we have a CNF formula $F$ built on the set of literals $L=\\{x\_1,\neg x\_1,\cdots,x\_n,\neg x\_n\\}$ where each variable is used in at least one clause of $F$. Consider a permutation $\sigma$ of $L$ such that $\sigma(F)$ is logically equivalent to $F$ i.e. $\sigma(F)\equiv F$.

Does it hold that $\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$ ?

I tried to find a counter example without success.

# Answer
No. Suppose $F$ is the formula

$$(x\_1 \lor x\_2) \land (\neg x\_1 \lor x\_2) \land (x\_1 \lor \neg x\_2) \land (\neg x\_1 \lor \neg x\_2) \land (x\_1 \lor \neg x\_1) \land (x\_2 \lor \neg x\_2),$$

and consider the permutation $\sigma$ such that $\sigma(x\_1)=x\_2$, $\sigma(x\_2)=\neg x\_1$, $\sigma(\neg x\_1)=x\_1$, and $\sigma(\neg x\_2)=\neg x\_2$.

Then $\sigma(F) \equiv F$, but $\sigma(\neg x\_1) \ne \neg \sigma(x\_1)$.
> 1 votes

---
Tags: permutations, propositional-logic
---


# Question
Title: Why is a Tree a concrete data structure and not abstract?
It seems to me that a tree or a heap is a concept and not a concrete implementation of some other abstract data structure.

For example a heap can be implemented with a table. Then why it is not considered abstract?

# Answer
> 3 votes
An abstract data type (ADT) is an interface: it describes the operations that can be performed and what their externally visible behavior should be. There are typically many possible ways to implement that interface.

A data structure is an implementation of such an interface: it provides code or fully specifies the internal behavior.

A binary search tree is not an ADT; it specifies more than a list of supported operations (like insert, find) but also how they can be implemented (by a particular data structure in the shape of a tree). A heap is not an ADT; it specifies more than a list of supported operations (extract-min, insert), but also how those operations should be implemented (by storing the elements in an array in a particular way and manipulating them in a specific fashion).

See also https://en.wikipedia.org/wiki/Abstract\_data\_type.

# Answer
> 0 votes
A concrete data type is absolutely defined. only certain inputs and outputs can exist in this.

Stacks, queues and heaps are abstract datatypes. They are just ideas, i.e. "black boxes" with a defined behavior. To implement them, you have to choose a suitable concrete datatype.; Abstract Data types can be constructed from known - or unknown data.

Now, Binary Trees are one of the most important data structures in computer science. We can think of a tree both as a mathematical abstraction and as a very concrete data structure used to efficiently implement other abstractions such as sets and dictionaries.

For example, to implement heap or AVL, we make use of a binary tree which makes tree as concrete data structure and heap as the ADT.

---
Tags: data-structures
---


title: The Clique vs. Independent Set Problem

text:
# Question
Title: The Clique vs. Independent Set Problem
Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.

Is there any algorithm in $O(\log^2 n)$ bits that finds whether $ A ∩ B = Ø $?

This is a well known communication complexity problem called CIS problem that was described by Yannakakis.

I'm not sure why and how does this work exactly. and which part of the $n/2$ vertices are reduced by both players.

P.S. I came to a conclusion that an independent and a clique can intersect in at most one vertex.

# Answer
> 6 votes
The two players construct a sequence $V\_0 \supset V\_1 \supset \cdots \supset V\_m$ of sets of vertices such that:

1. $V\_0$ consists of all vertices in the graph.
2. $|V\_{i+1}| \leq (|V\_i|+1)/2$.
3. $V\_i \supseteq C \cap I$.

The players stop once $|V\_m| \leq 1$. At this point they can answer the question using $O(1)$ communication.

At round $i$, the players know $V\_{i-1}$, and wish to construct $V\_i$. They act as follows:

* If $C \cap V\_{i-1}$ contains a vertex $v$ with fewer than $|V\_{i-1}|/2$ neighbors in $V\_{i-1}$, then Alice sends Bob one such vertex $v$, and both players set $V\_i$ to be this set of neighbors, together with $v$ (this is valid since $C \cap I \subseteq C \subseteq V\_i$). Otherwise, she sends $\bot$.
* If Alice sent $\bot$ and $I \cap V\_{i-1}$ contains a vertex $v$ with fewer than $|V\_{i-1}|/2$ non-neighbors in $V\_{i-1}$, then Bob sends Alice one such vertex $v$, and both players set $V\_i$ to be this set of non-neighbors, together with $v$ (this is valid since $C \cap I \subseteq I \subseteq V\_i$). Otherwise, he sends Alice $\bot$.
* If both players sent $\bot$, then $C \cap I = \emptyset$. Indeed, if $v \in C \cap I$, then $v$ has at least $|V\_{i-1}|/2$ neighbors and at least $|V\_{i-1}|/2$ non-neighbors inside $|V\_{i-1}|$, whereas the number of potential neighbors and non-neighbors is just $|V\_{i-1}|-1$. Therefore the players can abort and conclude that $C \cap I = \emptyset$.

Each round takes $O(\log n)$ bits of communication, and there are $O(\log n)$ rounds, for a total of $O(\log^2 n)$ bits of communication.

# Answer
> 4 votes
The $O(\log n)$ rounds comes from the fact that we are doing a binary search:

If the algorithm fails to terminate, then either Alice or Bob share a vertex v.

If Alice shares $v$, then $v$ has fewer than $|V\_{i-1}|/2$ neighbors in $V\_{i-1}$. $V\_i$ is set to be this neighborhood (along with v). Observe that $|V\_i|\< |V\_{i-1}|/2+1$. We will be a little hand-wavy and say $|V\_i|\leq |V\_{i-1}|/2$ (although it may actually be $|V\_{i-1}|/2+1/2$ when $|V\_{i-1}|$ is odd).

Similarly, if Bob shares $v$, then $v$ has fewer than $|V\_{i-1}|/2$ non-neighbors in $V\_{i-1}$. $V\_i$ is set to be this non-neighborhood (along with v). As such, $|V\_i|\leq |V\_{i-1}|/2$ (again we are being a little hand-wavy).

In both cases $|V\_i|\leq |V\_{i-1}|/2$. As such, if the algorithm fails to terminate after $k$ iterations, then, inductively, $|V\_k|\leq |V\_0|/2^k$. Finally, observe that the algorithm terminates if $|V\_k|\leq 1$, i.e., we will terminate if ever $V\_k$ is a singleton or empty. Finally, $|V\_k|\leq |V\_0|/2^k\leq 1$ if $k\geq \log |V\_0|=\log n$ implying that we must terminate in $\log n$ iterations.

---
Tags: algorithms, graphs, communication-complexity
---


# Question
Title: Does $E_{TM}$ accpets the empty word $\varepsilon$?
Let $L = E\_{TM} = \left\\{ \left\<M \right\> | M \text{ is a TM and L(M)} = \emptyset \right\\}$.

Does $L$ accepts the empty word $\varepsilon$?

In other words, is $$\varepsilon \in L$$

I'm a little bit confused by this.

My intuition says it doesn't since the empty set rejects every input.

# Answer
> 2 votes
I would answer that *no*, $\varepsilon \notin L$.

The reason is that the typical definition of a Turing machine is that its representation should contain a *non-empty* set of states and a *non-empty* tape alphabet.

In order to represent those, you typically would need a non-empty string.

*However*, as Yuval points out, you are free to define your own Turing Machine description language, and if you were to say *"We use $\varepsilon$ to denote the "empty" TM (with alphabet `0`), the TM that runs forever"*, you are free to do so, in which the answer becomes *Yes*.

I would go with *No*, $\varepsilon \notin E\_{TM}$.

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


# Question
Title: Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)
For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to find a binary coding ($M=2$) for English language ($N=26$).

If $M$ is not equal to $2$ and have a value **larger than $N$**, is there any method to find good coding (or optimal coding) for compression? Is there any research for this type of problem?
Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?

# Answer
> 3 votes
Both arithmetic coding and asymmetric numeral systems can be done in arbitrary base $b$.

> Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?

The above algorithms do not work by finding a 'mapping' from source to target symbols. Such a mapping doesn't deal well with fractional 'bits' - where an event has a probability that does not fit nicely in the output size.

Instead these algorithms work conceptually by dumping buckets of entropy from source symbols into a single uniform pool of entropy (in arithmetic coding this is a single fractional number, in asymmetric numberal systems this is a single large number), while scooping out entropy on the other side with output symbols. The trick is that the 'bucket size' of source symbols and output symbols do not have to have the same size at all.

---
Tags: information-theory, data-compression, coding-theory
---


# Question
Title: Why is this basic language not a regular language?
L = {x in {0,1}\* | x has an equal number of 0s & 1s}

Based on the recursive definition of regular languages, isn't it possible to form a single regular language set over the binary alphabet {0,1} by doing the following?

1. concatenating 0's and 1's to form each of the binary strings satisfying the condition, resulting in a regular language consisting of that single string
2. union all the single-string regular languages together into one single regular language

# Answer
> 3 votes
Every language is the union of regular languages: $$ L = \bigcup\_{x \in L} \\{ x \\}. $$ However, the set of regular languages is not closed under infinite unions. It isn't even closed under countably infinite unions, as your example demonstrates.

You can prove that your language is not regular in many ways. For example, if your language were regular, then so would its intersection with $0^\*1^\*$ be; yet this language is $\\{ 0^n 1^n : n \geq 0 \\}$, the classical example of a non-regular language. You can also prove non-regularity of your language directly, using either the pumping lemma or Myhill–Nerode theory.

# Answer
> 1 votes
You're on the right track! There's just one thing you're missing.

The "build all the strings and union them together" approach works great—*if you have a finite number of strings*. There's a theorem that says "a union of *finitely many* regular languages is regular", but the key is the *finitely many*.

In this case, there are *infinitely* many strings in the language, so the union-them-all trick no longer works.

If you want to prove that the language is not regular (as opposed to just failing to prove that it *is* regular), try a fooling set proof:

* Let $F$ be the language $1^\*$. It's clearly infinite.
* Let $x$ and $y$ be two distinct strings in $F$. These can be written as $1^i$ and $1^j$ with $i \neq j$.
* Now, let $z$ be $0^i$. From the definition of your language, we can see that $xz$ is in the language, but $yz$ is not.
* Therefore, all the different strings in $F$ are distinguishable as prefixes. Since the language has infinitely many distinguishable prefixes, it cannot be regular.

# Answer
> 1 votes
After you process n zeroes, the set of following strings leading to an accept state are all those with n 1’s more than 0’s. All these sets are different. And each set is roughly the same as a state in a state machine - so you can’t have a state machine with finite number of states.

---
Tags: regular-languages
---


# Question
Title: Interview Questions for Minimum Cost of Tasks
I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution would be more helpful than just explaining it as I am just trying to move on from this problem and do something else, more of like a review question that i can look at for the next interview prep. Thanks in advance.

Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n) that must be done in list order on your house. You can either do each task i yourself at a positive cost (that includes your time and effort) of c\[i\]. Alternatively, you could hire a handyman who will do the next 4 tasks on your list for the fixed cost h (regardless of how much time and effort those 4 tasks would cost you). You are to create a dynamic programming algorithm that finds a minimum cost way of completing the tasks. The inputs to the problem are h and the array of costs c\[1\], . . . , c\[n\].

Here is an example. \[1,3,5,6,7,2,1,3,1000\] is the cost array by yourself. The handyman cost is 11. For any sequence greater than or equal to 4 tasks we would add handyman to do the tasks. In this case we would add handyman for 1...4, and 5....8, hence the total cost here is 23, and it is the minimum. Note that the handyman can not do less than 4 consecutive tasks.

Here are the subproblems I was given to solve:

1. find and justify a recurrence (with boundary conditions) giving the optimal cost for completing the tasks
2. O(n)-time recursive algorithm with memoization for calculating the value of the recurrence and a bottom up algorithm

# Answer
### Equivalence to another question

Here is how we can find the problem in the question is basically the same as the problem in another question. Hence the answer over there can be adapted easily to this problem.

```
     the problem here <---> the problem over there
           home tasks <---> weekly shipments
cost c[i] by yourself <---> cost s_i * r by company A
         next 4 tasks <---> next 4 weeks
   cost h by handyman <---> cost 4c by company B
         minimum cost <---> minimum cost

```

For example, for cost array \[1,3,5,6,7,2,1,3,1000\] and handyman cost 11 here, we have the corresponding problem of $r=1$, frights by pounds\[1,3,5,6,7,2,1,3,1000\] and $c=11/4=3.75$.

You might want to ask why or how I can connect these two problems together. A simple reason is that I wrote the answer to the other question. Another reason is that I have been solving, modifying and creating problems about algorithms constantly. I would encourage you to try that kind of exercises from time to time.

### Exercises

**Exercise 1.** Imagine a different backdrop of this problem.

**Exercise 2. (A slight generalization)** Let us have the same problem as in the question, the same list of $n$ consecutive tasks and a handyman with the following change. Besides 4 consecutive tasks of the fixed cost $h$, the handyman can also do the next 3 consecutive tasks on your list for the fixed cost of $g$, regardless of how much time and effort those 3 tasks would cost you. Find an $O(n)$-time recursive algorithm that calculates the lowest cost for completing the tasks. (This problem degenerates to the original problem if we let $g$ be sufficiently large.)

Here is the idea to solve exercise 2.

Let $dp\[i\]$ be the lowest cost to do tasks 1 to $i$ inclusive. The base cases and the recurrence relation for $dp\[i\]$ is given by the following description.

* When $1 \leq i \leq 2$, you have to do all the tasks by yourself.
* When $i=3$, either you do all the tasks or let the handyman does all 3 tasks.
* When $i\geq 4$, the arrangement of lowest cost to complete all tasks must be one of the following ways.
    + You will do the last task by yourself. Complete the other $i-1$ tasks with the lowest cost.
    + Let the handyman do the last three tasks with cost $g$. Complete the other $i-3$ tasks with the lowest cost.
    + Let the handyman do the last four tasks with cost $h$. Complete the other $i-4$ tasks with the lowest cost.
> 1 votes

# Answer
For every i you calculate the best cost to do tasks 1 to i. For 0 \<= i \<= 3, you have to do the tasks yourself. For i \>= 4, you have the choice of doing task i yourself and doing tasks 1 to i-1 in the best possible way, or let the handyman do the last 4 tasks, and do the previous i-4 tasks in an optimal way.
> 1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Image segmentation generates inclusions and is not smooth
I am performing segmentation using opencv, but the segmented image has regions with breaks and also the border isn't smooth. How can I handle this problems?

# Answer
If I understand correctly, you need to use erosion and dilation morphological filter.
To ged rid of inclusion, like below ring finger, blob detection would be helpful, to detect small blob and erase it (meassure its area and decide based on that).
As for continuity, simple blur after errosion helps to get it smoother, if effect is too small, then use contour trace and smooth it via curves (RDP algorithm, convert it to Catmull-Rom or B-spline and smooth it from here). If you take curves approach, take the contour and discard rest, it automatically solves component inclusions.

The inclusion in index finger is too big to be handled by erosion and dilation, as it may change geometry too much. Fast idea is to generate circles of estimated radius (you know from scale or further detection that finger should be say 40px wide), so circles should push contour of finger, standardizing it's size). With curves, it is quite simple to handle checking distance to "parallel" wall.

Another approach is to take skeleton and draw fingers yourself, but this requires separate palm handling.
> 1 votes

---
Tags: image-processing
---


# Question
Title: Why CLRS example on residual networks does not follows its formula?
I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure:

That is:

> A flow in a residual network provides a roadmap for adding flow to the original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in the corresponding residual network $G\_f$, we define $f \uparrow f'$, the augmentation of flow $f$ by $f'$, to be a function from $V \times V$ to $R$, defined by
>
> $$(f \uparrow f')(u, v) = \begin{cases} f(u,v) + f'(u, v) - f'(v, u) & \> \text{if (u,v) $\in$ E} \\ 0 & \text{otherwise} \end{cases}$$

How the flow network in (c), for example $(s, v\_2)$ got the flow 12 ? If we follow the formula, it must have a flow 5: $8 + 5 - 8 = 5$

# Answer
> 4 votes
That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s \to v\_2 \to v\_3 \to t$. In particular, $f(s,v\_2)=8$, $f'(s,v\_2)=4$, and $f'(v\_2,s)=0$, so the updated flow is $8+4-0=12$.

# Answer
> 3 votes
It is explained in part (b) of the caption of **Figure 26.4**.

> The residual network $G\_f$ with augmenting path $p$ shaded; its residual capacity is $c\_f(p)=c\_f(v\_2,v\_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G\_f$ that is defined by $f'(s,v\_2)=f'(v\_2,v\_3)=f'(v\_3,t)=4$. So for the network flow $f\uparrow f'$ in (c), we have $$ (f\uparrow f')(v\_2, v\_3)=f(v\_2,v\_3)+f'(v\_2,v\_3) = 8+4=12.$$

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


# Question
Title: Compute hash value according to multiplication method
In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN: 978-0262033848), p. 264 they state this:

I get everything *but* the last part stating $h(k) = 67$

```
>>> r = 17612864
>>> bin(r) # r's binary representation
'0b1000011001100000001000000'
>>> int(bin(r)[: 14 + 2], 2) # extract 14 most significant bits and convert to int
8600

```

# Answer
You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number: $$ 00000001000011001100000001000000 $$ Now you extract the 14 most significant bits: $$ 00000001000011 $$ Converting to decimal, this is 67.
> 3 votes

---
Tags: hash, python
---


# Question
Title: Multiple Source Shortest Paths in a weighted graph
In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at the beginning of the algorithm.

However, I'm wondering if we can use the same technique to solve Multiple Source Shortest Paths in a weighted graph using Dijkstra's algorithm (for non-negative weight edges) and Bellman-Ford algorithm (when negative weight edges are allowed, and of course there is no queue here).

If I'm right, we can think in this situation as there are edges with weight equal to zero between any source and all other sources in the graph.

So, can we use this technique in a weighted graph? And why?

# Answer
> 5 votes
Yes. Here is the trick that always works: create a new source, $s\_0$, and add an edge (with length 0) from $s\_0$ to each of your starting vertices. Then, run any shortest-paths algorithm starting from $s\_0$ to compute the distance from $s\_0$ to each other vertex.

Your technique for BFS is equivalent to this; but this is more general and can be used with Dijkstra's algorithm, Bellman-Ford, or any other shortest paths algorithm.

---
Tags: graphs, shortest-path, weighted-graphs
---


title: A tricky P=NP problem

text:
# Question
Title: A tricky P=NP problem
> Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under $\pi$ we have $\mathsf{P}=\mathsf{NP}$.

This is a homework question I had. My current sketch is: for a language $L\_1 \in \mathsf{NP}$, define another language $L\_2\in \mathsf{P}$ based on $L\_1$ such that deciding $\pi(L\_2)$ helps decide $L\_1$. Here $\pi(L\_2)$ is decidable as $\mathsf{P}$ is closed under $\pi(\cdot)$; $L\_1$ being decidable infers that $L\_1\in \mathsf{P}$ and thus $\mathsf{P}=\mathsf{NP}$.

I think my sketch is in the right direction but I'm struggling in defining the appropriate $L\_2$ here. Any hint would be appreciated!

# Answer
You are asked to prove: There is a language X which is in P, such that the language π(X) is NP complete. Because in this case, since P is closed under the operation π, π(X) is also in P, which means P = NP. The idea is: Define a language X, which consists of strings that are YES-instances of an NP-complete problem, followed by an oracle that proves the instance is a YES-instance. The details are a bit tricky.

Define an encoding of instances of the travelling salesman problem: The encoding starts with the number n of cities in decimal notation, a comma, the number K which is the maximum length of a tour, an opening bracket, n * (n-1) / 2 distances in decimal notation, separated by commas if there is more than one distance, and a closing bracket. It is easy to determine that a string is such an encoding of a TSP instance.

We define the language L as follows: Each string in L consists of the encoding of a TSP instance with answer "YES", followed by hyphen characters "-" to exactly double the length of the string so far, followed by a permutation of the numbers 1 to n in decimal notation, separated by commas, such that starting at town 1, then visiting towns in the given order, produces a cyclic tour with length at most K.

The language L is clearly in P. The language π(L) consists of strings that are the encoding of a YES-instance of TSP, followed by some number of hyphens, and if there are enough hyphens, part or whole of an oracle. Because the oracle is much shorter than the encoded instance, π(L) contains some strings that are just encoded TSP instances, followed by hyphens. But for these strings, deciding that they are in π(L) is hard, as hard as deciding that an ordinary instance of TSP is a YES-instance. So π(L) is NP-complete.

And if π(L) is also in P as assumed, then P = NP.
> 1 votes

---
Tags: complexity-theory, np, decision-problem, p-vs-np
---


# Question
Title: Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?
I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

\begin{align} C=\left\\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are natural numbers}\right.\\ &\left.\text{ and there's no prime number in the range}\left\[p,p+n\right\]\right\\} \end{align}

could you please check if my reasoning is okay to deduce NP? (I am not sure, but here's what I think): for each word $\langle p,n\rangle \in C$ we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between $\[p,p+n\]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).

# Answer
> 5 votes
Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n \< p$.

The complement (there exists a prime in range $\[p, p+n\]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q \in \[p, p+n\]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b \approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|\[p, p+n\]| \approx |\[p, 2p\]| \approx p \approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.

# Answer
> 2 votes
As orlp says, it's trivial to give a certificate if the answer is "YES" (just give a non-trivial factor of each of the numbers in question), the problem is whether this certificate is polynomial sized.

There is a conjecture, backed by heuristics and some computational evidence, that there is a constant c \> 0 such that for any k-bit prime p, there is a prime between p and p + c * k^2. If this conjecture is true, then the certificate is actually of size O (k^3) whenever the answer is YES, so the problem is in NP. But, it's just a conjecture.

But of course if we might be able to prove the much weaker conjecture "for some c, there is always a prime between p and p + c * k^3" or the even weaker conjecture "there is a polynomial pol (k) such that there is always a prime between p and p + pol(k)", then this problem would also be in NP. So we can prove that is in NP by proving something about prime gaps.

There is also the possibility that a less obvious and shorter certificate exists.

---
Tags: complexity-theory, turing-machines, computability, np, decision-problem
---


# Question
Title: How to count the biggest size of the problem during some time period?
We assume that time of solving the problem $=f(n)$$\mu$s. Now we have to calculate how big problem we can calculate for each time periods.

So there are: $\lg n, \sqrt{n}, n, n\lg n, n^2, n^3, 2^n, n!$,

How to calculate size of the biggest problem during those times periods?: 1s, 1min, 1h, 1 day, 1 month , 1 year, 100 years

I completely don't know how to start.

# Answer
Freeman,

the answer is somewhat easy and you can do it with a simple calculator. I will assume that $\mu s$ represents a *microsecond*, *i.e.,* 0.000001 second.

Let's take for example the calculus for $n^2$. You need to answer which value of $n$ makes $0.000001 f(n^2) = time\\\_limit$. Thus, we have:

$0.000001 f(n^2) = 1 ~~~~~~~~\rightarrow n = 1000 ~~~~~~~~\text{(1 second)}$
$0.000001 f(n^2) = 60 ~~~~~~\rightarrow n = 7,745.97~\text{(1 minute)}$
$0.000001 f(n^2) = 3600 ~~\rightarrow n = 60,000 ~~~~\text{(1 hour)}$
$0.000001 f(n^2) = 72000 \rightarrow n = 268,328 ~~\text{(1 day)}$

You need to compute that for all combinations of time limit and growth factor.
Try writing a simple computer program to compute such numbers and plot all of them like the figure below. Hope you go well on your studies :)

P.S.: This figure was retrieved from here.
> 0 votes

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


# Question
Title: Isoecursive Types When to Fold and Unfold
I'm trying to implement recursive types into my programming language. I've implemented extensible rows and was hoping to add some recursive typing in order to get something like `this` or `self` within a record (thus imitating objects). Recursive types would only occur in record definitions, like

```
record IntObject:
  val: int
  add: (IntObject -> IntObject)

```

Now `IntObject` is an alias for the type `mu X. {val: int, add: (X -> X)}`.

This represents an `IntObject` with a field `val` that has the type of a primitive integer, and an `add` method that takes in an `IntObject` and returns another `IntObject`, so I can use it like so:

```
IntObject(1).add(IntObject(2))

```

The definition of `add` would be something like.

```
record IntObject:
  def add(self, other):
    return IntObject(self.val + other.val)

```

Like in Python, instance method invocations have a reference to the object calling the method implicitly passed in as the first parameter. I'm not sure how Python does this, but I was thinking of doing the partial application of the instance methods at object creation. Therefore,

```
IntObject(1)

```

creates a record like this (using Haskell lambda syntax)

```
{val: 1, add: \other -> IntObject.add(self, other)}

```

I tried reading TAPL's section on recursive types, and isorecursion seems much easier to implement, especially since I will only allow records to have recursive types. What I'm unsure about is when to add `folds` and `unfolds`. TAPL says

> In Java each class definition implicitly introduces a recursive type, and invoking a method on an object involves an implicit unfold.

This is exactly what I want to do. If invoking a method introduces an `unfold`, that means that there needs to be a `fold` somewhere, and I'm unsure where to introduce that `fold`.

If this question is too vague, specifically since I probably haven't given enough information about the current state of my language, a general answer would suffice. Any advice regarding where to introduce folds and unfolds in an OOP language, say Java, would help a ton.

# Answer
As you've stated, the type of `IntObject` is `mu X. {val: int, add: (X -> X)}`. `fold` and `unfold` witness the isomorphism between a recursive type and its body, i.e. in this case between `mu X. {val: int, add: (X -> X)}` and `{val: int, add: ((mu X. {val: int, add: (X -> X)) -> (mu X. {val: int, add: (X -> X)))}`. Letting `Y` stand for `mu X. {val: int, add: (X -> X)}`, this can be more compactly written `unfold : Y ~= {val: int, add: (Y -> Y)}` with `fold` going the other direction.

You need `unfold` whenever you want to access any fields/methods. `mu X. {val: int, add: (X -> X)}` doesn't have any fields; `{val: int, add: (Y -> Y)}` does. Dually, whenever you want to make an `IntObject`, you need to use `fold`. A value of type `{val: int, add: (Y -> Y)}` is not an `IntObject`, but `fold` can inject that value into the type `IntObject`. In particular, any time you `new` up an `IntObject`, i.e. invoke the constructor to create an object.

Basically, your `IntObject(i)` "really means" something like

```
let self = fold({val: i, add: \other -> IntObject.add(self, other)}) in self

```

Similarly, your `add` method would look like:

```
def add(self, other):
    return IntObject(unfold(self).val + unfold(other).val)

```

where we'd use the definition of `IntObject` just mentioned above.
> 2 votes

---
Tags: type-theory, type-inference, types-and-programming-languages
---


title: Recurrence Relation Mergesort

text:
# Question
Title: Recurrence Relation Mergesort
I was reading *Algorithms 4th Edition* by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort:

> The number of compares is at most n and no less than $\lfloor n/2 \rfloor$.

The code they gave for the `merge()` routine is shown below:

```
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
{   int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) aux[k] = a[j++];
        else if (j > hi) aux[k] = a[i++];
        else if (less(a[j], a[i])) aux[k] = a[j++];
        else aux[k] = a[i++];
    }
}

```

From the code, it seems that the number of compares will be at most $\lfloor n/2 \rfloor$ since if there are $n$ elements and we only compare pairs of them, there will be $\lfloor n/2 \rfloor$ compares.

Then again, I'm sure that I'm just missing something.

Thanks for any help.

# Answer
> 1 votes
Please trace the following code.

```
Integer[] a = {2, 4, 6, 8,  1, 3, 5, 7}; // an array of 8 elements.
Integer[] aux = new Integer[a.length];
merge(a, aux, 0, 3, 7);

```

You will find the number of compares is $7= 8-1$.

Here is a fact about general situations.

(**Number of compares**) Let `a` be an array of distinct elements. The elements from a\[lo\] to a\[mid\] is sorted increasingly. The elements from a\[mid+1\] to a\[hi\] is sorted increasingly. Then the compare less(a\[j\], a\[i\]) will be run at most hi-lo times in the call merge(a, aux, lo, mid, hi). In particular, if there is $n$ elements in `a`, there will be at most $n-1$ compares. If we assume lo \< mid and mid + 1 \< hi, it will be run hi-lo times if and only if a\[mid - 1\] \< a\[hi\] \< a\[mid\] or a\[hi - 1\] \< a\[mid\] \< a\[hi\].

**Proof of "only if "**: Note that after each comparison, either j is increased by 1 or i is increased by 1. The value (j-(mid+1)) + (i-lo) is increased always increased by 1.

Consider the point of time when the last comparison `less(a[j], a[i])` happens. The value (j-(mid+1) + (i-lo) = hi - lo - 1. Since j \<= hi and i \<= mid, we must have j=hi and i = mid.

Now consider the point of time when the second last comparison happens. After that comparison, if `i` will be increased by 1 and we will find that `a[mid - 1] < a[hi] < a[mid]`. Otherwise, `j` will be increased by 1 and we will find that `a[hi - 1] < a[mid] < a[hi]`.

**Proof of "if"** is skipped.

---

**Exercise 1.** What if `lo = mid` or `mid + 1 = hi`?

**Exercise 2.** What if there are repeated elements in `a`?

---
Tags: algorithms, sorting, mergesort
---


# Question
Title: Does iterated PSPACE trace equal ELEMENTARY?
I have the following feeling (I wouldn't even call it a conjecture yet) which I'd like to ask whether it's true in some form.

Take the class of all programs running in polynomial space.

Surprisingly or not, they can still output an exponentially large output: at each step of their running they may output something, and since they may perform 2^poly(n) steps, they may output such a large output as well.

Now suppose we take this output and feed it again to a PSPACE machine, and so on. It can also be seen as inputing to one PSPACE Turing machine the trace (if we don't like the idea of outputting outside of the tape) of the running of another PSPACE Turing machine, which again might be exponential in size wrt the original input's size.

By that, do we cover the whole ELEMENTARY complexity class? If not, then any known class? It seems to me obviously beyond PSPACE and EXPSPACE or even n-EXPSPACE if we allow n+1 such iterations.

---

As per D.W.'s request, here's a more precise formulation of the question. Consider the class consisting of all possible pairs of PSPACE Turing machines. We consider running the pair of machines as follows. One machine takes an input and runs, and the second machine takes as input the trace of the running of the first machine. Which complexity class would this capture? It seems to me like EXPSPACE. Similarly if we took a triple of machines, two as above, and the third taking the trace of the second, it'd look to me like 2-EXPSPACE. Is that the situation indeed? What would be the computational power (in terms of complexity classes) of such iterated two (or more) different machines, one taking as input the trace of the other?

---

I guess that if this is correct and two iterated PSPACE machines capture EXPSPACE or beyond, then it'll prove that P!=PSPACE. So either it's all wrong and one can show me why it's wrong, or maybe even if it's right it doesn't actually imply P!=PSPACE.

# Answer
> 1 votes
Let's show that a single iteration captures EXPSPACE; the general case is similar.

It is clear that if you feed the output of a PSPACE algorithm to another PSPACE algorithm, then you get an EXPSPACE algorithm. In the other direction, let $L$ be a problem in EXPSPACE, say taking space $2^{p(n)}$. We run a PSPACE machine which pads the input with $2^{p(n)}$ zeroes (we can do this since we can count up to $2^{p(n)}$ using $p(n)$ space), and then feed the output to a PSPACE machine which first erases the padding and then transfers control to an EXPSPACE machine for $L$.

# Answer
> 1 votes
Yup. If you have two algorithms $A,A'$ both in PSPACE, and you run $A'$ on the output from $A$, the resulting algorithm is in EXPSPACE. Think about it: how much space is used by them together? Well, it's the amount of space for $A$, plus the amount of space for $A'$. If the input is length $n$, then the output of $A$ is at most $2^{p(n)}$, so the amount of space used by $A'$ is $q(2^{p(n)}$, where $p,q$ are polynomials. Thus the computation is in EXPSPACE.

Also, any computation in EXPSPACE can be expressed in this way. Suppose you have any language that can be computed in EXPSPACE, i.e., in $2^{p(n)}$ space. Then you can take $A$ to copy its input to the output, then output a string of $2^{p(n)}$ 1's; then $A'$ can do the computation itself, and since the input to $A'$ has length $2^{p(n)}$, $A'$ will use space polynomial (in fact linear) in its input length.

You are also correct about the iteration of three of these; the result is in 2-EXPSPACE.

---
Tags: complexity-theory
---


# Question
Title: Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
> Prove that $L = \\{ xy \in \\{a,b\\}^\* \mid |x|\_a = 2|y|\_b \\}$ is not regular.

I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. Could someone please help me?

I tried to use the pumping lemma with the word $w=a^{2p}b^p$. It is easy to see that for $p=1$ it cannot be "pumped". However, for the case $p=2$ and, particularly, splitting the string $w=aaaabb$ into $x=\lambda$, $y=aa$ and $c=aabb$, it is true that $\forall i \quad xy^iz\in L$ . Examples for the case $p=2$ are: $i=0 \mid w=aabb$ which can be split into $x=aab$ and $y=b$, $ i =1 \mid w=aaaabb$ into $x=aaaa$ and $y = bb$, $ i =2 \mid w=aaaaaabb$ into $x=aaaa$ and $y = aabb$, etc. So we can't reach to a contradiction.

# Answer
> 1 votes
Here are several routes to proving this:

* Intersect with $a^\*b^\*$ and apply an appropriate inverse homomorphism to reduce to the language $\\{a^nb^n : n \ge 0 \\}$, which you know isn't regular.
* Use Myhill–Nerode theory: the words $\\{a^n : n \geq 0\\}$ are pairwise inequivalent.
* Use the pumping lemma on the word $a^{2p} b^p$, where $p$ is the pumping constant.

---
Tags: complexity-theory, formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Resolution when clauses contain more than 1 complementary literals
Let's assume that we have clauses $(l\_1 \lor l\_2 \lor l\_3), (\neg l\_1 \lor \neg l\_2 \lor l\_4), (l\_1 \lor l\_2 \lor l\_5), (\neg l\_1 \lor \neg l\_2 \lor l\_6)$, where both $l\_1$ and $l\_2$ are complementary literals for the clauses.

If we apply the resolution technique for $l\_1$ we'll get clauses

$(l\_2 \lor \neg l\_2 \lor l\_3 \lor l\_4)$, $(l\_2 \lor \neg l\_2 \lor l\_3 \lor l\_6)$, $(l\_2 \lor \neg l\_2 \lor l\_5 \lor l\_4)$, $(l\_2 \lor \neg l\_2 \lor l\_5 \lor l\_6)$

How to proceed with $l\_2$ from here?

# Answer
> 1 votes
Clauses containing both a variable and its negation are not useful, since they're always correct. You can just ignore them.

Furthermore, you CNF is satisfiable - for example, you can set all variables to TRUE. So it's not completely clear what you are trying to accomplish.

---
Tags: satisfiability, 3-sat
---


# Question
Title: Is turing completeness related to recursive enumerable languages?
I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.

When I looked up for its relationship with recursive enumerable languages, I couldn't find anything substantial.

My question is:

> Will a turing computable machine always accept recursive enumerable languages?

Thanks in advance!

# Answer
> 2 votes
A language $L$ is *computable* if there is a Turing machine $M$ such that:

1. If $x \in L$ then $M$ halts on input $x$ with "YES" written on the output tape.
2. If $x \notin L$ then $M$ halts on input $x$ with "NO" written on the output tape.

A language $L$ is *recursively enumerable* if there is a Turing machine $M$ such that:

1. If $x \in L$ then $M$ halts on input $x$.
2. If $x \notin L$ then $M$ doesn't halt on input $x$.

As an example, consider the language HALT of all Turing machines that halt on the empty input. HALT is recursively enumerable, since given a Turing machine $M$, we can simulate it on the empty input. However, HALT is not decidable, as Turing showed using diagonalization.

*Turing completeness* is an informal concept (though it can probably be formalized). According tot he Wikipedia definition, a computing system is *Turing-complete* if:

1. Everything that can be computed by the system is computable (on a Turing machine).
2. Every computable language can be computed by the system.

However, we could just as well define Turing completeness with respect to recursive enumerability. The two definitions are probably equivalent for all reasonable computing systems.

---
Tags: turing-machines, turing-completeness, church-turing-thesis
---


title: Software metric for data growth

text:
# Question
Title: Software metric for data growth
I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.

Is there a software metric that describes "data growth" for an algorithm or do I simply write "the data grows exponentially"?

btw: The size of the $2^n$ elements varies , so I cannot determine their size (storage)

# Answer
> 1 votes
Apparently, the best you can do is write something on the lines of "the number of result sets is exponential in the number of input input elements". This is better than simply saying "the data grows exponentially" since such growth must happen *with respect to some quantity*. It also might be a good idea to state the value $2^n$ somewhere (in the more technical sections) so it is clear it is a precise and not an asymptotic estimate.

It is unfortunate you cannot estimate the size of each result set. Are you sure not even very conservative or even empirical estimates are possible? (If that is the case, then consider adding at least one of those.)

---
Tags: terminology, combinatorics
---


# Question
Title: Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$
I am trying to find a mapping reduction from $A\_{TM}$ to $\overline{CF\_{TM}}$, but I can't seem to find one.

Definitions: $$\begin{align\*} CF\_{TM} &= \left\\{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is context-free} \right\\} \\ A\_{TM} &= \left\\{ \langle M,w \rangle \mid \text{$M$ is a TM and $w \in L(M)$} \right\\} \end{align\*}$$

AFAIK the mapping reduction of the regular (i.e., not the complimentary) language is as follows: $\langle M,w \rangle \in A\_{TM}$ if and only if we can construct a language $L$ which is context-free in the sense that $L(F((\langle M,w \rangle)))$ is context-free.

# Answer
> 1 votes
Let $L$ be recursively enumerable but not context-free (and, therefore, not empty). We only need the existence of such an $L$; the actual choice is immaterial. In addition, recall the empty set $\varnothing$ is context-free. The idea is to map to a TM which accepts $L$ in case $M$ accepts $w$ (i.e., $\langle M,w \rangle \in A\_{TM}$) and to $\varnothing$ otherwise.

Given an instance $\langle M,w \rangle$ of $A\_{TM}$, map it to the description $\langle S \rangle$, where $S$ is the TM which does the following:

> On input $w'$:
>
> 1. Run $M$ on $w$. If $M$ rejects, reject.
> 2. If $M$ accepts $w$, then accept if and only if $w' \in L$.

Note that, if $M$ does not halt on $w$, then $S$ does not halt either. Also, $w' \in L$ can be checked because $L$ is recursively enumerable (and $S$ need not halt in case that is false). We conclude that $L(S) = L$ if $\langle M, w \rangle \in A\_{TM}$ and $L(S) = \varnothing$ (which is context-free) otherwise.

---

**An observation.** The trick behind 98% of these problems lies in understanding what you need to do (i.e., what I wrote in the first paragraph). The actual description for the instance you are reducing to (in this case, $\langle S \rangle$) might look tricky or esoteric at first sight, but it actually simply follows as a consequence once you have the right ideas in mind.

---
Tags: turing-machines, computability, context-free, reductions
---


# Question
Title: How to correctly describe this action, deleting an edge that "shortcut" some vertices
Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:

1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in linear time ? Basically, we don't want any edges that shortcuts our visit as every vertices need to be visited.

Here is something: Such edge removal can be achieved in linear time by scanning trough all the vertices in graph in the topological order, and for every outgoing edge(a, c) of v checking if the b comes after the vertex。

How can I correctly describe that if an algorithm remove (0,1),(3,4),(1,2) edges in this graph?

# Answer
Your operation replaces your graph with one of its *directed spanning trees*. See for example lectuire notes of Uri Zwick.
> 1 votes

---
Tags: algorithms, formal-languages, graphs, proof-techniques
---


# Question
Title: Some basic questions on halt and move in Turing machines
Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.

Firstly i define an operation as follows:

**Operation (Op)**

Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:

1. replace color $C$ with $0$ or $1$. (at current position of tape head) move
2. tape-head (change its position).
3. change state $S$ with $0$ or $1$ (at new position).

For each operation:

* In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).
* Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?

*My last question is basically the same as the last question..*

* Can the tape-head move more than one unit to the left or right?

The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.

**Example**

If something was unclear I can try this example:

```
  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*

```

Of the output ($b\_2b\_1b\_0$), where the first bit ($b\_0$) represent the tapehead-move direction, $b\_1$ represents the new state, and $b\_0$ represents the changed color. The asterisk shows that a halting operation should be performed.

The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:

```
  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*

```

**Recap**

So can more than one operation perform the halting operation?

Can we move the tape head more than one unit to the left or right, or can it stand still?

# Answer
To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.

> * In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).

It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h\_1$, $h\_2$ and $h\_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $\mathrm{HALT}$.

> * Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?

Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.

> * Can the tape-head move more than one unit to the left or right?

Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.

Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.
> 8 votes

---
Tags: turing-machines, automata
---


# Question
Title: Language whose intersection with a CFL is always a CFL
> Prove or disprove: If the language $L$ is such that for every context-free language $L\_0$, the language $L \cap L\_0$ is context-free, then $L$ is regular.

I haven't managed to prove this, but I'm pretty sure there is no counterexample.

# Answer
> 2 votes
Let $L = \\{a^n b^n : n \geq 0\\}$, and let $L\_0$ be an arbitrary context-free language. Define $L\_1 = L\_0 \cap a^\* b^\*$, and note that $L\_1$ is context-free and $L \cap L\_0 = L \cap L\_1$. Let $S = \\{(i,j) : a^i b^j \in L\_1\\}$.

According to Parikh's theorem, the set $S$ is semilinear. The set $D = \\{(n,n) \geq 0\\}$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S \cap D$ is also semilinear. Since $S \cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m \geq 1$ and a subset $A \subseteq \\{0,\ldots,m-1\\}$ such that $$ L \cap L\_1 = F \Delta \\{ a^n b^n : n \bmod m \in A \\}, $$ where $\Delta$ is symmetric difference. It is easy to check that $\\{a^nb^n : n \bmod m \in A\\}$ is context-free, and so $L \cap L\_1$ is context-free.

Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.

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


# Question
Title: Repeated String Match: need help to understand the maximum number of repeats needed to be looked at
There's this question on LeetCode (link):

> Given two strings `A` and `B`, find the minimum number of times `A` has to be repeated such that `B` is a substring of it. If no such solution exists, return `-1`.
>
> For example, with `A = "abcd"` and `B = "cdabcdab"`.
>
> Return `3`, because by repeating `A` three times (`“abcdabcdabcd”`), `B` is a substring of it; and `B` is not a substring of `A` repeated two times (`"abcdabcd"`).
>
> Note: The length of `A` and `B` will be between `1` and `10000`.

The brute force solution provided on the website is this:

> The question can be summarized as "What is the smallest `k` for which `B` is a substring of `A * k`?" We can simply try every `k`.
>
> ### Algorithm
>
> Imagine we wrote `S = A+A+A+...`. If `B` is to be a substring of `S`, we only need to check whether some `S[0:], S[1:], ..., S[len(A) - 1:]` starts with `B`, as `S` is long enough to contain `B`, and `S` has period at most `len(A)`.
>
> Now, suppose `q` is the least number for which `len(B) <= len(A * q)`. We only need to check whether B is a substring of `A * q` or `A * (q+1)`. If we try `k < q`, then `B` has larger length than `A * q` and therefore can't be a substring. When `k = q+1`, `A * k` is already big enough to try all positions for `B`; namely, `A[i:i+len(B)] == B` for `i = 0, 1, ..., len(A) - 1`.

I understand this part:

> If we try `k < q`, then `B` has larger length than `A * q` and therefore can't be a substring.

But I don't follow how the writer has arrived at this other conclusion:

> When `k = q+1`, `A * k` is already big enough to try all positions for `B`; namely, `A[i:i+len(B)] == B` for `i = 0, 1, ..., len(A) - 1`.

Why can we stop at `k = q+1`? Why is it not necessary to try `q+2` (and `q+3`, etc.)?

# Answer
Here is a proof by example. We want to check whether $B$ is a substring of some power of $A$. Instead, let us check whether $B$ is a substring of $A^\omega$, that is, $A$ repeated infinitely many times. It suffices to test the following starting positions (why?):

```
abcdabcdabcdabcd...
cdabcdab

abcdabcdabcdabcd...
 cdabcdab

abcdabcdabcdabcd...
  cdabcdab

abcdabcdabcdabcd...
   cdabcdab

```

In order to perform these checks, we don't need to consider $A^\omega$; it suffices to consider the smallest power of $A$ which covers the very last case. This power is $q+1$ (or possibly just $q$).
> 0 votes

---
Tags: algorithms, search-problem, substrings, string-matching
---


# Question
Title: "Immediate" method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":

```
x=1
x=f(x);
x=f(x);

```

We can rewrite this in "immutable style" **without changing the higher-level structure of the program:**

```
x1=1
x2=f(x1);
x3=f(x2);

```

We turned it into an immutable style program by only making "**local changes**": We simply took the mutable variable $x$ and changed the program wherever $x$ appeared to make it immutable.

**Question**: Can we in general turn an arbitrary mutable program into an immutable program *by only making local changes*, so that the higher level structure of the program stays the same?

* Obviously this will depend on the language. You may assume any language features you want. e.g. this answer talks about monads (though it's not clear to me whether they can always be used to translate programs using only local changes).

# Answer
> 3 votes
The state monad allows us to translate any stateful (you call it "mutable") program to a pure one. The changes required to the program are "local" in the sense that you only need to make superficial changes to the syntax, assuming you use Haskell-style `do` notation. For example, the following is the Haskell translation of your program into a pure program:

```
do x <- 1
   x <- f x
   x <- f x

```

You think you can make your transformation by renaming variables, but this will not do when recursion or loops are involved. For example, it is not clear how to use your idea here:

```
s = 0
i = 0
while (i < n) do
   s = s + i
   i = i + 1
done

```

Following your scheme we get the non-sensical:

```
s1 = 0
i1 = 0
while (i1 < n) do
   s2 = s2 + i1
   i2 = i2 + 1
done

```

You need to think more carefully about your idea (and I don't see how to make it work).

---
Tags: programming-languages, functional-programming, imperative-programming
---


# Question
Title: The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL
We have proved that the language $ L = \\{\omega\omega \mid \omega \in \\{0,1\\}^{\*} \\} $ is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following CFG:

$ G = (\\{S, S\_{1} \\},\\{0,1\\},R,S) $ where R has the following rules:

$$\begin{align\*} S &\rightarrow S\_{1}S\_{1} \mid \epsilon \\ S\_{1} &\rightarrow 0S\_{1} \mid 1S\_{1} \mid \epsilon \end{align\*}$$

It feels like that this CFG's language should be the language $L$ that I have defined above since each substitution adds the same letter on both sides. But it can't be since we can use pumping lemma on the word $0^{l}1^{l}0^{l}1^{l}$ (where $l$ is the pumping length). So either I'm not doing the substitution incorrectly, or the CFG's language contains $L$ and has more words that I'm not seeing currently...

Can someone help me out and point out where my mistake is?

# Answer
> 3 votes
You're assuming that, when you expand $S\to S\_1S\_1$, the two copies of $S\_1$ must be expanded in the same way, to give two copies of some string $w$. But it doesn't have to be that way. For example, you could do $$S\to S\_1S\_1 \to 0S\_1S\_1 \to 0 S\_1 \to 01S\_1\to 01\\,.$$

---
Tags: context-free
---


title: Check grammar for LL(1)?

text:
# Question
Title: Check grammar for LL(1)?
If I have to check a Left Recursive grammer for LL(1) then should I check it after removing left recursion?

For example:- S-\> (L)|a L-\>L.S|S

If I check after removing Left Recursion then the above grammer is LL(1). But if I do not remove left recursion then above grammer is not LL(1). which one is the right answer?

# Answer
If the question is, "Is this grammar LL(1)?", then the answer is "No".

If the question is, "Can this grammar be made LL(1)", then by all means remove the left-recursion.

The distinction is important because removing left-recursion does not preserve derivation order, so the left-recursion-eliminated grammar produces different parse trees. If it is being used to parse, it is not the same grammar.
> 1 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Is it possible to encode logical expression and interpret it with SQL?
Is it possible without any forms of `eval` or stored procedures to execute a query, which interprets logical expression, encoded in some way in a table (or two tables) of relational database?

For example, one table can contain a mapping for variable names into their truth values (V1), and another table or two (L1 and L2) - encode logical expressions, eg, in a conjunctive normal form.

Then some clever SQL query will interpret the logical expression from L1-L2, and apply values for variables from V1. (And of course same can also be done for multiple different expressions in the same query).

At first, this seems non-trivial to construct, but SQL has aggregating functions, so theoretically should be possible?

# Answer
> 2 votes
Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question):

```
> select * from F;
+------+------+
| f1   | f2   |
+------+------+
|    1 |    1 |
|    1 |    2 |
+------+------+

> select * from C;
+------+------+
| c1   | c2   |
+------+------+
|    1 | A    |
|    1 | B    |
|    2 | C    |
+------+------+

> select * from V;
+------+------+
| v1   | v2   |
+------+------+
| A    |    0 |
| B    |    0 |
| C    |    1 |
+------+------+

```

Where F is a table for formulae, mapping from formula number to a table of conjuncts (C), which has a pointers into table of variables (V). The formula encoded here is `(A AND B) OR C`.

Doing conjunction is simply a matter of applying `min()` and disjunction is done by `max()`.

Evaluating formula (number 1 in the example above) can be done by the following query:

```
> select max(A.v) as result from F, (select min(v2) as v, c1 from C, V
                                     where c2 = v1 group by c1) as A
  where c1 = f2 and f1 = 1;
+--------+
| result |
+--------+
|      1 |
+--------+

```

The above approach is a bit simplified - NOT is not possible to express, but it is easy to add it as an extra boolean column of table C and XORing it with the variable value.

---
Tags: first-order-logic, relational-algebra, interpreters
---


title: Assigning books to boxes

text:
# Question
Title: Assigning books to boxes
I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each book has a certain profit if I put it in the same box with another book. So for instance, if I pair book $i$ with book $j$ I might have a profit of 10 dollars so long as they're in the same box. If I have 3 books in one box, I'd have to sum the profit of 1 and 2, 2 and 3, and 1 and 3. I want to find the best way to assign the not-yet assigned books to either box 1 or 2 to maximize my profit. Formally:

* 2 boxes: $b\_1$ and $b\_2$
* Set: $N$ of $1...n$ books
* $S\_1$ = set of all books that **must** go to box 1
* $S\_2$ = set of all books that **must** go to box 2
* $p\_{ij}$ = The profit by having books $i$ and $j$ in the same box
* Objective (roughly): $max(\sum\_{i=1}^{2}\sum p\_{ij})$ (maximize the profit over all boxes)

**My ideas so far:**

* Formulate the problem as a min-cut problem because we are trying to end up with two sets of books (one for box 1, one for box 2). Would it be correct to say that $-min(-\sum\_{1}^{2}\sum p\_{ij})$ is equivalent to our maximization above? I tried simplifying it further but I'm not sure how.

+ Make source node for box 1, node for each book not assigned (not in $S\_1$ and not in $S\_2$) and a sink node for box 2.

**My question:**

With the previous formulation in mind, I'm confused on what the edges would be like. I have edges from box 1 to the book nodes and then the book nodes to box 2 but I'm not sure if this makes sense, largely because I need to make sure my summation notation is correct and how to turn that into an appropriate graph. Could anyone offer advice on the minimization I wrote above and how to translate it to a graph correctly?

# Answer
First, I assume that it doesn't matter which box a pair of books go into, e.g., the value of book 1 and 2 being in box 1 is the same as the value of book 1 and 2 being in box 2. Now, denote $B\_1, B\_2$ as the books in boxes 1 and 2 respectively. The value of this partitioning is precisely $$ \sum\_{{i,j} \in B\_1:\ i\<j} p\_{ij}+ \sum\_{{i,j} \in B\_2:\ i\<j} p\_{ij}= \sum\_{{i,j} \in N:\ i\<j} p\_{ij} - \sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}$$ (in words, the value of the paired books in box 1 + the values of the paired books in box 2 = the value of all paired books - the value of the books that aren't paired)

Observe that $\sum\_{{i,j} \in N:\ i\<j} p\_{ij}$ is constant regardless of how you place your books and therefore maximizing $\sum\_{{i,j} \in B\_1:\ i\<j} p\_{ij}+ \sum\_{{i,j} \in B\_2:\ i\<j} p\_{ij}$ is equivalent to minimizing $\sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}$ (as you've roughly stated).

Under this assumption (that the box doesn't matter), we now exactly have a min cut problem.

Let your set of vertices be $N$ (there is no need for a source node to identify which box is which). We let the graph be complete (there is an edge between every pair of nodes) the value of the edge between $i$ and $j$ is $p\_{ij}$. A cut on this graph is a partitioning ${B\_1,B\_2}$. The value of such a cut is $\sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}$. Hence, to find the maximum way to place your books, it suffices to find a minimum cut on this graph.

---

In the event you want a formulation with terminal nodes (sink/sources), you can add in dummy nodes s and t (denoting box 1 and box 2), connect edges from all books to these nodes with an arbitrary weight W. A partitioning that divides s, t has weight \begin{align}\sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}+\sum\_{j\in B\_2}p\_{sj}+\sum\_{i\in B\_1} p\_{it}&=\sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}+|B\_2|⋅W+|B\_1|⋅W\\ &=\sum\_{i \in B\_1}\sum\_{j\in B\_2}p\_{ij}+|N|⋅W.\end{align}

In this formulation, a valid cut is $\\{s\\},\\{t,N\\}$ with value $W\cdot |N|$ and therefore to ensure at least one book goes in each box, $W$ needs to be made large.

---

There is one final component of your problem we have not addressed, i.e., there is a set of books $S\_1$ that MUST go into box 1 and a set $S\_2$ that MUST go into box 2.

Off the top of my head, I do not see a way to fix this without incorporating a source and sink $s$ and $t$ (for box 1 and 2 respectively). The formulation I've given above is almost sufficient. If $j\in S\_1$ (book j MUST go into box 1), make $p\_{sj}$ arbitrarily large (much more than $W$). This ensures an arbitrarily large cost will be charged if you try to but a book that must go into box 1 into box 2. Similarly, if $i\in S\_2$, make $p\_{jt}$ arbitrarily large.

Assuming $S\_1$, and $S\_2$ are non-empty (that books are already forced into each box), $W$ can be taken as 0 (since a proper partition is enforced by $S\_1,S\_2$) and $p\_{sj}=p\_{it}$ for $j\in S\_1, i\in S\_2$ can be as little as $\sum\_{{i,j} \in N:\ i\<j} p\_{ij}$ (assuming each $p\_{ij}\geq 0$).
> 1 votes

# Answer
Make a graph with vertices $v\_1, ..., v\_n$ for the $n$ books. Let an edge $v\_i, v\_j$ for books $v\_i$ and $v\_j$ have weight $p\_{ij}$.

Now, create two vertices $b\_1$ and $b\_2$ and make edges from $b\_1$ to all vertices that should go to Box 1, respectively for $b\_2$ and Box 2. Let the weights be "infinite", e.g. $1+\sum\_{i, j \leq n} p\_{ij}$.

Now, a min-cut in this graph will create two or more components, one component that $b\_1$ belongs to and one component that $b\_2$ belongs to. These determine the optimal locations of the books. The rest are just "isolated" books that you can put wherever you want.
> 0 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Approximation algorithm for weighted set cover, using multiplicative weights
It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows how to do so.
The running time depends on the "width" of the problem, which equals to the number of sets in the unweighted case. However, in the weighted case, the width of the problem depends on the weight function, hence the running time is exponential with respect to the representation of the problem. Is there a way to overcome this issue? Either a way to reduce it to polynomial running time or proof that it's impossible (under plausible complexity assumptions)?

# Answer
Yes, fractional weighted set cover and, indeed, all explicitly given packing/covering LP's can be solved using multiplicative-weights algorithms in poly time independent of the width. There are many papers in this line of work. The earliest are probably due to Garg and Konemann. See e.g. https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 .
> 2 votes

---
Tags: approximation, linear-programming, set-cover, online-algorithms
---