# Question
Title: what does it mean to extend an assignment?
For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a?

Sorry if this is super trivial, I did not find an answer

e.g here: No Small Linear Program Approximates Vertex Cover Within a Factor 2 − $ \epsilon $ pg 16 x does not extend \alpha

# Answer
> 3 votes
It means that you have a partial solution, and you *extend* that partial solution by assigning at least one more variable to some value, thus producing either a new partial solution or a solution where every variable is assigned a value.

Put differently, if $x$ extends an assignment $a$, it holds that $x$ does precisely the same assignments as $a$ *and* assigns any number of other variables in addition.

---
Tags: satisfiability, boolean-algebra, constraint-satisfaction
---


# Question
Title: What will happen to NP-Hard problems if P=NP
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.

He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.

Here is my question... What happens if P=NP. Thus it mean that *all NP-hard problems become polynomially solvable?* Will all NP hard problems reduce to polynomial order if P=NP?

# Answer
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
> 8 votes

# Answer
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.

We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
> 6 votes

# Answer
So just as your Prof. wikipedia says (emphasis mine):

> NP-hardness \[...\]is the defining property of a class of problems that are, informally, "*at least* as hard as the hardest problems in NP"

(Still Informally) you can think of the ‚at least‘ as:

NP $\leq$ NP-Hard

So you have to distinguish those NP-hard problems for which the equality holds from those which are ,*strictly*‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.

Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:

* For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
* For problems that are NP-hard but not in NP it will mean nothing.

This euler diagram from wikipedia might also help to clear things up
> 6 votes

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


# Question
Title: Is it possible to define a pairwise function that can either append to a tuple or make a tuple, potentially with nested tuples?
I lack the vocabulary to appropriately express the question succinctly, so I apologize if the title question is confusing.

Suppose you can define a binary infix operator that produces tuples, and you want this operator to be able to simultaneously:

1. Extend a tuple to arbitrary length by appending additional elements
2. Support nested tuples (in that they are not "flattened" into the tuple)

Suppose the operator is represented by `.`, I can do (1.) in pseudocode by:

```
define generic <Type T (T != Tuple), Type U>
operator (.) (T left, U right) => Tuple<T, U> {
  createTuple(left, right);
}

define generic <Type... T, Type U>
operator (.) (Tuple<...T> left, U right) => Tuple<...T, U> {
  appendTuple(left, right);
}

```

This violates (2.) though, if the leftmost value is a tuple:

```
# Good
1 . 2 . 3 . 4 -> (1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

# Also good
1 . (2, 3) . 4 -> (1, (2, 3)) . 4 -> (1, (2, 3), 4)

# Bad
(1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

```

What I'd like is to get `((1, 2), 3, 4)` for the last example. The only way I can think to do this would require constraining the types, which I would like to avoid. Is something like this even possible, in any programming language or type system?

# Answer
> 2 votes
The problem with this is that there is no way to distinguish between `(1, 2)` and `1 . 2`: both have to produce `(1, 2)`. This means that for a left-associative `.`, `1 . 2 . 3` and `(1, 2) . 3` *have to* produce the same result. (And switching to right-associative `.` does not help: it has the same issue with `1 . (2, 3)`.)

Some ways I could think of bypassing this:

1. The `.` operator does not directly produce a tuple, instead it produces a wrapper for a tuple. This way, you can distinguish between `1 . 2` and `(1, 2)`. But you also have to include an "unwrap" operation at the end. Though that could be handled by an implicit conversion, which makes the unwrap operation invisible in code.
2. The `.` operator looks like it's binary, but it's actually variadic. I.e. `(1, 2) . 3 . 4` compiles to `operator(.) ((1, 2), 3, 4)`. Though I don't know of any language that would do something like this.

---
Tags: programming-languages, meta-programming
---


# Question
Title: Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E\_c \subseteq E$ is a cutset of a bipartite graph $G = (U\cup V, E)$ then $E-E\_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.

# Answer
This is a partial answer that proves the NP-completeness of your problem, by a reduction from the EXACT-CUT problem for general graphs1.

Given an instance $(G=(V,E),k)$ of the EXACT-CUT problem (that asks whether there is a cut of size $k$ in the graph $G$), we construct a new graph $G'$ as follows.

* For each vertex $v\in V$, construct vertices $v\_0^0,\ldots,v\_m^0,v\_0^1,\ldots,v\_m^1$ as well as edges $(v\_i^0, v\_j^1)$ for all $i,j\in\\{0,\ldots,m\\}$ (so that they form a biclique). Denote $V\_v=\\{v\_0^0,\ldots,v\_m^0,v\_0^1,\ldots,v\_m^1\\}$.
* For each edge $(u,v)\in E$, construct two edges $(u\_0^0, v\_0^1)$ and $(u\_0^1, v\_0^0)$.

Here $m=2k$. Note $G'$ is a bipartite graph.

Now we can see if $(A,B)$ is a cut of size $k$ in $G$, then $(\cup\_{v\in A}V\_v,\cup\_{v\in B}V\_v)$ is a cut of size $2k$ in $G'$.

On the other hand, suppose there is a cut $(A',B')$ of size $2k$ in $G'$. Now consider a vertex $v$. Assume $|A'\cap\\{v\_0^0,\ldots,v\_m^0\\}|=a$ and $|A'\cap\\{v\_0^1,\ldots,v\_m^1\\}|=b$, then we have \begin{align} m=2k&\ge a(m+1-b)+b(m+1-a)\\ &=(m+1)(a+b)+\frac{1}{2}(a-b)^2-\frac{1}{2}(a+b)^2\\ &\ge(m+1)(a+b)-\frac{1}{2}(a+b)^2, \end{align} which implies $a+b\<1$ or $a+b\>2m+1$, i.e. $a=b=0$ or $a=b=m+1$. This means all vertices in $V\_v$ must belong to the same cut-set. Hence $(\\{v\mid V\_v\subseteq A'\\}, \\{v\mid V\_v\subseteq B'\\})$ is a cut of size $k$ in $G$.

Now we have shown that there is a cut of size $k$ in $G$ if and only if there is a cut of size $2k$ in $G'$, which concludes the proof of the NP-completeness of the EXACT-CUT problem on bipartite graphs.

---

1 Your reasoning for the NP-completeness of the EXACT-CUT problem is incorrect because you used a Turing reduction while a many-one reduction is required. However, it is not hard to find such a polynomial-time many-one reduction.
> 2 votes

# Answer
This is an $NP$-complete problem to which **EXACT**-**COVER**-**BY**-$3$-**SETS** (**X3C**) can be reduced.

Given an instance of **X3C**, construct the standard bipartite graph (i.e. the collection of $3$-sets forms one side, and the ground set forms the other side).

To prevent any cut that takes some and leaves some from the ground set, we do like this. Create a large amount of dummy vertices (on the side of the collection of $3$-sets, of course). For each element, connect it to all of these dummy vertices. Now, if we separate any pair of elements then for each dummy vertex, we need to take into the cut-set exactly one edge. And, this will blow up the total count for the cut-set.

*Note that the set of dummy vertices are common for every element*.

So, all the ground set needs to be on one side of the cut.

As a result, there can be at most one dummy vertex that resides on the opposite side of the ground set.

The value $k=\mid U\mid$ should now take care of the rest for us. **Nearly done**!

**What if** one takes only one dummy vertex on one side and every other vertex on the other side.

Just, similarly create a large enough amount of **dummy elements**. And connect each dummy element to all the dummy $3$-sets.

The argument that all ground set needs to be on one side still holds. And, one can take the exact cover on one side and all other vertices on the other side to construct a cut-set of size $k$ as required. **Now, really done, yet**? **Not yet**.

*We need to make sure the chosen $3$-sets are pairwise-disjoint*.

To do this, we need to utilize a restricted version of **X3C**. In this restricted version, each $3$-set intersects with exactly $6$ other $3$-sets. So for each pair of overlapping $3$-sets, connect both to a large enough number $M$ of dummy vertices (not elements, not $3$-sets, of course). $M$ can be taken as a large (still polynomially in magnitude) that is coprime to $\mid U \mid$, $m$ (number of $3$-sets). Now, connect each of the latest added dummy vertex to all the dummy $3$-sets above. This serves as guarantee that every last added dummy vertex is in the *safe* side. Finally, choose some $M'$ coprime to $M$ (and everything else) from the dummy vertices between each intersecting pair to connect them to other $3$-sets outside of the pair

Surely, we need to update $k$ accordingly as $k:=k+6M\frac{k}3+6M'(\frac{k}3-1)\frac{k}3$. **DONE**!

---

Note that the number of dummy $3$-sets must be much larger than $M$ (and so, certainly also $M'$).
> 0 votes

---
Tags: complexity-theory, graphs, np-complete, np, max-cut
---


# Question
Title: Pumping Lemma Question: About the cases for y in the xy^iz criterion
**Problem statement:**

Let $\Sigma = \\{a, b, c\\}$, and consider the task of multiplication encoded in the language $L = \\{a^n b^k c^{nk} : n \geq 0, k \geq 0\\}$.

Prove that L is not regular using the pumping lemma.

---

**Relevant sources:**

Sources (from three different people) arguing in favour of cases (where the links that are videos are set to the exact frame that I want you to see - there's no need to watch the video(s)):

1. https://youtu.be/dikEDuepOtI?t=393
2. https://youtu.be/Ty9tpikilAo?t=474
3. https://youtu.be/g4e2RElzCSQ?t=1282
4. https://www.physicsforums.com/threads/non-regular-language-pumping-lemma.945301/

---

**My attempted solution:**

> $L = \\{a^n b^k c^{nk} : n ≥ 0, k ≥ 0\\}$
>
> Let us choose the string generated when $n = k = P = 2$. That is, let us choose $S = a^2 b^2 c^4$ as a string.
>
> Furthermore, let us assume that $S$ is regular.
>
> Then, we try to make that string be of the form $S = xyz$, and it should meet the criteria of the pumping lemma, which are that
>
> (i) $x y^i z ∈ L$
>
> (ii) $|y| \> 0$
>
> (iii) $|xy| ≤ P$
>
> Then, there are six cases, and they are as follows:
>
> I) $y$ only contains occurrences of a.
>
> II) $y$ only contains occurrences of b.
>
> III) $y$ only contains occurrences of c.
>
> IV) $y$ contains occurrences of a and b.
>
> V) $y$ contains occurrences of b and c.
>
> VI) $y$ contains occurrences of a, b and c.
>
> So, for the string $S$ to fulfill the criteria of the pumping lemma, it must be shown that (i), (ii) and (iii) each hold true for at least one of I), II), III), IV), V) and VI). That is, for the string to not fulfill the criteria of the pumping lemma, it must fail at least one of the three parts of the pumping lemma for all six of the above cases.
>
> Case I):
>
> Let $x = a$, $y = a$ and $z = b^2 c^4$. Then, it is indeed the case that $|y| = 1 \> 0$ and that $|xy| = 2 \leq 2$. However, if an integer $i = 2$ is chosen, then a string $a a^2 b^2 c^4 = a^3 b^2 c^4 ∉ L$ is obtained. So, case I) fails.
>
> Case II):
>
> Let $x = a^2$, $y = b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 2 \> 0$, but it is not the case that $|xy| = 4 \leq 2$, and so case II) fails. (There is no need to examine part (i) of the pumping lemma.)
>
> Case III):
>
> Let $x = a^2 b^2$, $y = c^2$ and $z = c^2$. Then, it is indeed the case that $|y| = 2 \> 0$, but it is not the case that $|xy| = 6 \leq 2$. So, case III) fails.
>
> Case IV):
>
> Let $x = a$, $y = a b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 3 \> 0$, but it is not the case that $|xy| = 4 \leq 2$. So, case IV) fails.
>
> Case V:
>
> Let $x = a^2$, $y = b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 3 \> 0$, but is not the case that $|xy| = 5 \le 2$. So, case V) fails.
>
> Case VI:
>
> Let $x = a$, $y = a b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 4 \> 0$, but it is not the case that $|xy| = 5 \leq 2$. So, case VI) fails.
>
> Then, because all six cases have failed at least one of the pumping lemma’s criteria, it follows that the language $L$ is not regular.

---

**My teacher's solution:**

> Assume for contradiction that $L$ is regular and apply the Pumping Lemma. Let $m$ be the integer in the Pumping Lemma. Take $w = a^mb^1c^m$. Since $w ∈ L$ and $|w| ≥ m$, we can write $w = xyz$ such that $|xy| ≤ m$ and $|y| ≥ 1$ and any string of the form $xy^iz ∈ L$ for $i = 0, 1, 2, \dots$ This implies that $y =a^k$ for some $k ∈ \\{1, \dots , m\\}$. Taking $i = 0$, we get that $xz = a^{m−k}b^1c^m ∈ L$; however, this contradicts the definition of $L$, since $(m − k) \cdot 1 \neq m$. Contradiction.

---

**Are we both correct? Is at least one of us wrong? Why?**

Any input would be *greatly* appreciated!

# Answer
Your proof doesn't work, since the pumping lemma only applies to large enough words. The pumping lemma states that if a language $L$ is regular, then there exists a constant $m$ such that all words in $L$ of length at least $m$ have a certain decomposition $xyz$ such that $|xy| \leq m$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. However, there is no guarantee for words of length smaller than $m$.

In your case, the word that you chose has size 8, which might conceivably be smaller than $m$, and so is not guaranteed to have the decomposition $xyz$ satisfying the properties stated above.

As an aside, if $L$ is finite than $m$ has to be larger than the size of all words in $L$ (why?), and in that case the pumping lemma cannot be applied to pump *any* word.
> 1 votes

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


# Question
Title: Understanding Interval Schedulling problem requirement
Here is a modification of the weighted interval scheduling problem.

Given $n$ intervals by their end points $s\_i$ and $t\_i$ for $1 ≤ i ≤ n$, I want to minimize number of intervals so that every interval has a nonempty intersection with one of the selected intervals. In other words, select $S ⊆ {1,..., n}$ such that for each $1 ≤ j ≤ n$, interval $j$ intersects with some interval $i ∈ S$. We say that the $j^{th}$ interval $\[s\_j, t\_j\]$ overlaps with $i^{th}$ interval $\[s\_i, t\_i\]$ if there exists a point $x$ such that $x$ belongs to the $i^{th}$ interval and the $j^{th}$ interval. A point $x$ belongs to an interval $\[s, t\]$ if $s ≤ x ≤ t$. Assume that $s\_i ’s$ and $t\_i's$ are distinct.

What I'm confused on is what this problem is even asking. It says minimize the number of intervals so that every interval has a non-empty intersection with a selected interval. So I get that means I want to find an interval that overlaps with another interval. But am I trying to find a sequence that avoids this as much as possible? In other words, am I just trying to set it up so that I maximize number of intervals while also minimizing overlapping intervals or am I trying to do something different?

# Answer
Let us check some simple examples.

Suppose there are three intervals \[1,3\], \[2,5\], \[4, 6\]. Then the wanted number is 1. Here is how. Let $T$ be any two of the intervals. Then every interval will has a nonempty intersection with one of the intervals in $T$. For example, you can let $T$ be {\[1,3\], \[2,5\]}. You can also let $T$ be {\[1,3\], \[4,6\]}. On the other hand, Let $M$ be the set of \[2,5\], i.e., $M$={\[2,5\]}. Then every interval will has a nonempty intersection with the only one interval in $M$, \[2,5\]. Since the wanted number can not be smaller than 1, it is 1.

For a slightly more interesting example, suppose there are 5 intervals \[1, 3\], \[2,5\], \[4, 7\], \[6,9\], \[8,10\], where each interval intersects its two neighboring intervals.

* The wanted number is 2. Why? Firstly, any interval will not intersect either \[1,3\] or \[8,10\]. So one interval is not enough. Secondly, consider intervals \[2,5\] and \[8,10\]. We can see that every interval will intersect one of \[2,5\] and \[8,10\]. So two intervals are enough.
* If you name those five intervals A, B, C, D, E respectively and connect a pair of letters if the corresponding two intervals intersects, you get a graph with vertices {A,B,C,D,E} with edges AB, BC, CD, DE. (Graphs obtained this way are called interval graphs.) Now it is easy to translate our problem about intersecting intervals into a problem about graphs. The new problem is called the minimum dominating set of a graph.

---

Here is an equivalent version of the problem that is much simpler.

> Given $n$ fixed intervals all of whose endpoints are distinct. Select some intervals such that the intersection of every original interval and the union of selected intervals is nonempty. How to minimize the number of intervals selected?
> 0 votes

---
Tags: algorithms
---


# Question
Title: How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\\{1,\dots,n\\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum\_{i\in A}a\_i$ such that we always have $\pi(S) \ne \pi(S')$. For example, we can define $a\_i = 2^i$. This function satisfies the property because for each $A \subseteq N$, $\pi(A)$ uniquely represents an integer written in base 2. However, in this function $a\_i$ is bounded above by $\mathcal{O}(2^n)$. I am looking for a function such that $|a\_i|$ and $\frac{1}{|a\_i|}$ are bounded above by a polynomial. As an example that does not satisfy this last condition we can consider $a\_i = 2^{i-n}$. It would be great to know different functions that satisfy this property. I will try to proof the uniqueness myself (if it is not so difficult!), so please let me know if you are aware of such functions.

# Answer
> 3 votes
There are many functions that satisfy your condition. Here are a few.

1. $a\_i=1+c^{-i}$, for some constant $c\ge 2$.
2. $a\_i= 1+b\_i/p\_i$, where $p\_i$ is the $i^{th}$ prime number and $b\_i$ is any integer between 1 and $p\_i-1$.
3. $a\_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=e$ or $\alpha=0.110001000000000000000001\cdots$, an Liouville number. (Yuval's method)
4. $a\_i=c\_1b\_i+c\_0$, where $b\_i\>0$ is such a function and $c\_1, c\_0$ are positive constant.
5. One can choose random numbers between a positive constant $c\_0$ and 1, which should satisfy the requirement with probability one. The issue then is how to select/implement a random number generator and detect the outliers, which may or may not be trivial. (Yuval's method)

For the first three methods, the constant 1 can be replaced by some kind of polynomial of $n$. For example, a nonzero polynomial of $n$ with nonnegative integer coefficients.

These functions should get you going. If you find more ways, you can update this answer.

---
Tags: asymptotics, sets, polynomials, subset-sum, upper-bound
---


# Question
Title: How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?
I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'm afraid I simply don't know it.

I'm given an algorithm that starts with four numbers $a$, $b$, $c$ and $d$ which can be chosen freely. After each iteration, the numbers are recalculated as shown in the following images. $a\_{n+1}=|a\_n-b\_n|\ $, $b\_{n+1}=|b\_n-c\_n|\ $, $c\_{n+1}=|c\_n-d\_n|\ $, $d\_{n+1}=|d\_n-a\_n|\ $ for all $n\gt0$.

After a certain amount of time, this algorithm always results in all four columns ending and remaining at 0. Or so it appears. You can quickly try it out by replicating it in Excel or any other spreadsheet program.

The goal is to choose the four starting numbers a, b, c and d in such a way, that the columns all jump to 0 after the 50th iteration or later.

I have difficulties understanding how one can outsmart this algorithm, i.e., to make this algorithm compute as many rounds as possible before reaching all 0's. I've tried a brute force method by simple giving a, b, c and d random numbers with maximum lengths of 30 digits. And then seeing how far I can get. I let my computer try that for eight hours last night and the best I came up with was 17 several times - so obviously pure random brute force will not work and I will need a more thoughtful approach.

I'd be glad about any ideas!

# Answer
I am a bit cautious just in case you might be taking part of some kind of open competition or exam.

Before I could reasonably believe that you are raising this question in good faith, I will just say I can reach 51 iterations without going to all zeros using less than 18 digits for each number.

**As an evidence that I do have an answer, here are the last 5 digits of my numbers**. This will not help anybody to get a better answer, except when you are super good at math, in which situation you probably do not need this too tenuous a hint anyway. However, it can be used to prove beyond any doubt in the future that I did know an answer. $$(\***00000, \***22634, \***22881, \***60047)$$

---

Per request of the questioner, I will explain the simple "secret" of how to get an answer briefly. A full update may or may be followed later.

What you want is to let $a\_1, b\_1,c\_1,d\_1$ look like $a\_0, b\_0,c\_0,d\_0$ exactly. Since they look like exactly, the $a\_2, b\_2, c\_2, d\_2$ will look like $a\_1, b\_1, c\_1, d\_1$ exactly. You see you can actually go on forever. It will break down only when we cannot express the number accurately enough in its numerical representation, which is enforced since the geocacher owner does not accept values like $\sqrt 2$ (just for an example; there may or may not be a $\sqrt 2$ in my answer).

What does it mean by exactly alike? Well, for example, if the two circles of numbers are the same except by a factor and a rotation.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Simple Definition of a Simple Grammar (with confusing example)
This is the definition of simple grammar that I got from the book "Formal Languages and Automata" by Peter Linz.

There is a homework question that asks for a simple grammar for the language L(aaa\*b + b). This is the answer that I found.

I don't see how this could be right, or much less how there could be any answer to this question. If you go S -\> aA -\> aaBC -\> aaaBC ... then you will get infinite a's. The B-\>aB rule has no possibility of terminating. Is there something I am missing or is the answer to this question just wrong? If it is wrong then is there a possible answer and what is it?

# Answer
> 1 votes
You're right, the grammar is wrong. Everything would be fine, though, if you were able to eventually eliminate the $B$. Here's a way to do that: $$ S\rightarrow b\mid aA\\ A\rightarrow aB\\ B\rightarrow aB\mid b $$ The first production generates a singleton $b$ or the first $a$, the second generates the second $a$ and the third eventually generates an arbitrary number of $a$s followed by a $b$.

---
Tags: automata
---


# Question
Title: What is the "description" of a Turing machine?
I am currently reading about the Halting Problem in my course on the theory of computation and the following was given in my lecture slides

Now my question is that if $d$ is the description of a Turing machine, what exactly is $d$ from a strictly mathematical point of view? The way that $d$ is written above seems to suggest that $d \in Q$ (i.e. that $d$ is a state of the Turing machine $T$), but I can't be entirely sure.

# Answer
The description is a string that encodes the formal specification of the machine, comprising:

* the set of states,
* the start state,
* the set of halting states (or, where appropriate, the sets of accepting and rejecting states),
* the tape alphabet,
* the input alphabet,
* the transition function.

Some authors also explicitly include the identity of the blank symbol in the description of the machine; others leave it to convention (e.g., stating that the alphabet will always be $c\_1, \dots, c\_k$ for some $k$, and $c\_1$ is the blank symbol).
> 3 votes

# Answer
A formal way to approach this is to note the existence of Universal Turing Machines.

Let U be a universal turing machine. Then, for any other Turning Machine T there exists a tape state T' such that for every tape state S, there exists a tape state S' such that U(T' S') generates the same output at T(S).

Basically, a Universal Turing Machine can take as initial input a "description" of another Turing Machine (T'). From that "description" it can then consume the a transformation of a tape state and simulate everything the source Turing Machine does.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Relationship between complexity classes XP and W[1]?
I am reading the introductory chapter in Parameterized Algorithms by Cygan *et al.* and I am having some problems with the distinction between complexity classes $\mathsf{W\[1\]}$ and $\mathsf{XP}$.

They explicitly define complexity class $\mathsf{XP}$ on p. 13 as the those problems that, given an instance $(x, k)$ of a parameterized problem, can be correctly decided by an algorithm in $O(f(k)\cdot|(x,k)|^{g(k)})$ time for functions $g, k$. I believe I understand this.

Complexity class $\mathsf{W\[1\]}$ is not explicitly defined. However, in the discussion of $k$-cliques on p. 9, they give an $O(n^k)$ algorithm for deciding whether a $k$-clique exists in a graph. As I understand it, therefore, the $k$-clique problem must be in $\mathsf{XP}$. However, the authors discuss it as a $\mathsf{W\[1\]}$ problem in a way that I find confusing.

My question, then, is twofold: (1) **Am I right in thinking that $\mathsf{W\[1\]} \subseteq \mathsf{XP}$**? I haven't been able to settle this by looking ahead in the book or by searching online. (2) **Intuitively, what is the difference between the two classes?** I have found defitions online, e.g. on Wikipedia, but not in language that I have found accessible. I would appreciate, therefore, if someone could provide more of an overview.

# Answer
1) Yes, you are right: W\[1\] is a subset of XP. As you noticed, $k$-clique is in XP. The class W\[1\] is (usually by definition) the closure of that problem under FPT-reductions. XP is closed under these reductions. Hence the subsetship.

2) Citing another answer of mine, here is a bit of intuition about XP:

> The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.

In that sense, XP is the hardest intractable class of parameterized complexity theory. In an even fuzzier sense, on the very opposite side of the spectrum, W\[1\] is the easiest parameterized version of NP.

Gaining an intuition for W\[1\] is not exactly made easy (in the past I tried in this answer). As said, it is usually defined by completeness of a problem (like $k$-clique). Definitions using machine models exist (e.g. Chen, Flum, Grohe: Machine-based methods in parameterized complexity theory. TCS 339(2-3), 2005). But that does not imply they are suitable for entry-level understanding of the class. I suggest you just take W\[1\] as the sum of the facts you know about it.
> 1 votes

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


# Question
Title: How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?
For language $L = \\{ x \in \\{a,b\\}^\* \mid \\#\_a x = \\#\_b x \\}$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick example, for string $x = aabb$ we have these derivations: $S \rightarrow aSbS \rightarrow^\* aaSbSb\varepsilon \rightarrow^\* aa\varepsilon b \varepsilon b \rightarrow aabb$). Then I was asked to provide a mathematical proof, which is more like to be intended as a formalism, to prove, indeed, the correctness of such CFG.

Arguably, by induction, one could assume it holds that $\forall k\leq n$, $|x| = 2k$ and then test a string $x$ with number of characters $|x| = 2n + 2$. So string $x$ is in the form of $x = au'bu''$. But now how can I show that $u'$ and $u''$ still contain an equal number of $a$'s and $b$'s? Sorry if I'm missing something and might be easier than I think.

# Answer
> 1 votes
There are two implications involved in the correctness. Every string in $L$ can be derived by the CFG (completeness) and every string derived by the grammar belongs to $L$ (consistency). I think you want an argument to formalize the first implication by induction.

Assuming the string $x\in L$ starts with an $a$, there *must* be a position with letter $b$ such that the string is of the form $aubv$ such that the $\\#\_a(u)=\\#\_b(u)$. The argument I know is by counting. Read the letters in $x$ one by one, and add $1$ for each $a$, subtract $1$ for each $b$. As the number of $a$'s equals the number of $b$'s, the count starts and stops with $0$. The counts becomes $1$ after the first letter, and must drop back to $0$ at some position with a $b$. In between we have seen an equal number of $a$'s and $b$'s.

Now that $x=aubv$ with $x\in L$ and $u\in L$ it is easy to argue that also $v\in L$.

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


# Question
Title: Determine when Strassen's algorithm for matrix multiplication is better than regular MM
I'm trying to find out how to determine the size of the matrices $n$ such that Strassen's algorithm for matrix multiplication is better than the regular algorithm. I know that Strassen's algorithm is $\Theta(n^{lg 7})$, and regular matrix multiplication is $\Theta(n^3)$.

My reasoning goes along the following lines:

When the size of the matrices to be multiplied is $2x2$, Strassen's algorithm carries out 7 multiplications and 24 additions, whereas the regular multiplication requires 8 multiplications and 4 additions.

So I can do something like this, by the definition of the $\Theta$ notation

\begin{align} 31 &= c\_1 2^{lg 7} \\ 31/7& = c\_1 \end{align}

Using a similar reasoning,

\begin{align} 12 &= c\_22^{lg 8} \\ 12/8 &= c\_2 \\ 3/2 &= c\_2 \end{align}

If this is valid, having determined the constants all that remains is to set the equalities using these constants, and solve for $n$.

I would just like to know if my train of thought is correct, and if it isn't, how to go about finding the size of the matrix $n$ such that Strassen's algorithm is better. I know this might depend on specific implementations of hardware, architecture and so on, but the divide and conquer approach doesn't necessarily have to be used until the algorithm reaches the base case $2x2$. I want to know *when* to switch to another algoritm, which in this case is the regular matrix multiplication.

# Answer
> 1 votes
If you look at the number of operations, it's obvious that you would do a matrix multiplication using the smallest number of operations. For 2x2 the direct method is best. You calculate for 3x3, 4x4, 5x5 etc. how many operations you need using the direct method, and how many you need using the Strassen method, performing (n/2) x (n/2) products using the fastest method.

If you look at execution time, that is dependent on the computer where you run it, so the point where Strassen is better also depends on the implementation. You would do the same thing as above, but instead of calculating the number of calculations, measure the execution time.

# Answer
> 0 votes
Your question is underspecified, for two reasons:

* There are several ways of defining Strassen's algorithm when $n$ is not a power of 2.
* You haven't defined how you determine which algorithm is better.

To handle the first problem, let us only consider values of $n$ which are powers of 2. As for the second problem, perhaps the proper way to determine which algorithm is better is to run both and to see which is better in practice. But as a proxy for that, let us count just the number of arithmetic operations in the algorithm, giving the same weight to additions and multiplications, somewhat unrealistically. For a $2\times2$ algorithm using $a$ additions and $m$ multiplications, the recurrence for the number of additions $a\_n$ and multiplications $m\_n$ of $n\times n$ matrices (where $n$ is a power of 2) are $$ a\_1 = 0, m\_1 = 1, a\_{2n} = ma\_n + an^2, m\_{2n} = mm\_n. $$ Solving these recurrences on a computer, we find that Strassen's algorithm first improves on the standard algorithm for $n = 2^{12}$.

---
Tags: divide-and-conquer
---


title: Prove or disprove if L is CFL?

text:
# Question
Title: Prove or disprove if L is CFL?
Given $L=\\{a^ib^jc^k | i\neq j \space and \space j=k\\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks.

# Answer
Suppose that $L$ were context-free. According to Ogden's lemma, there is a constant $p$ such that each word in $L$ with at least $p$ marked positions satisfies the constraints of the lemma. Consider the word $s = \underline{a^p}b^{p+p!}c^{p+p!}$, in which the underlined part is marked. According to Ogden's lemma, there is a decomposition $s = uvwxy$ in which $vx$ contains at least one $a$, and $uv^iwx^iy \in L$ for all $i \geq 0$. We now consider several cases:

1. $x$ contains $b$s but not $c$s, or $c$s but not $b$s. Choosing $i = 0$, we obtain a word in which the number of $b$s differs from the number of $c$s, and so does not belong to $L$.
2. $x$ contains both $b$s and $c$s. Choosing $i = 2$, we obtain a word not belonging to $a^\*b^\*c^\*$, and so not belonging to $L$.
3. $x$ contains no $b$s nor $c$s, and $v \notin a^\*$. In this case $x = \epsilon$, and so $v$ must contain at least two different characters. Choosing $i = 2$, we again obtain a word not belonging to $a^\*b^\*c^\*$, and so not belonging to $L$.
4. $vx \in a^+$, say $vx = a^q$. Let $i = p!/q+1$. Then $uv^iwx^iy = a^{p+p!}b^{p+p!}c^{p+p!} \notin L$.

We have obtained a contradiction, and so $L$ is not context-free.
> 0 votes

---
Tags: context-free
---


# Question
Title: Positioning items to maximize separation
Say we want to place n items on the real line. Let us denote the position of item i by $p\_i$. We have interval constraints on the position $p\_i$, i.e. we are given $l\_i, r\_i$ such that $l\_i \le p\_i \le r\_i$. My problem is: given a specific item s, how do I compute the maximum gap possible to the right of s? By maximum gap to the right of s I mean the distance between s and the next item to its right.

### Mathematical Description:

More formally, given $s \in \[n\]$, and $(l\_i,r\_i)$ for $i\in\[n\]$ I want to find $$f(s) = \max\_{p\_1,\dots,p\_n} p\_t - p\_s$$ subject to \begin{align\*} 1)\\,& l\_i \le p\_i \le r\_i\\, \forall\\,i \in \[n\] \\ 2)\\,& \forall\\,i\ne s,t, \text{ either } p\_i \le p\_s \text{ or }p\_i \ge p\_t \text{ (there is no item between s and t)} \end{align\*}

In the absence of the second constraint the problem would have been a linear program. The second constraint makes it difficult.

I know how to model this question as an integer program (see https://bit.ly/2Jhf7kJ), but I am interested in an actual algorithm.

# Answer
> 2 votes
> Given a specific item $s$, how do I compute the maximum gap possible to the right of $s$? By maximum gap to the right of $s$ I mean the distance between $s$ and the next item to its right.

This is much more useful than the mathematical description.

First note that items that are to the left of $s$ don't hurt us in any way, so if it is possible to put an item to the left of $s$, do so. Then we note that if an item can't go to the left of $s$ we want it as far to the right as possible.

The conclusion? Each item is always at either its left or right boundary, with the exception of $s$. And once you know the position of $s$ you'll also know all the other positions.

So just loop over each interesting position of $s$, discard all items that can go on the left, and then choose the closest item on the right. Out of these closest items, which ever is the furthest is your answer (or well, it's associated position of $s$).

Now what are the interesting positions of $s$? Well it's each time you can put another item to the left of $s$. So it's all the left boundaries (plus one epsilon) of items that fall within $\[l\_s, r\_s\]$, and $l\_s$ itself.

---
Tags: algorithms, optimization, np-complete, linear-programming
---


# Question
Title: Show that the Laplace smoothing for bigrams is a valid probability distribution
If we consider any smoothing technique like laplace or delta smoothing. Intuitively we can see that the we are stealing from sequences with non zero probablity and re distribute to sequences with zero probablity and there by it should be a probability distribution function. But how do we prove this mathematically say for example laplace smoothing?

# Answer
First, let me rewrite your formula: $$ \Pr\_L\[w\_j|w\_i\] = \frac{\\#(w\_i,w\_j)+1}{\\#w\_i+|\Sigma|}. $$ The quantity $\\#w\_i$ should be defined so that $\sum\_j \\#(w\_i,w\_j) = \\#w\_i$ (so we should ignore the final character when calculating $\\#w\_i$). Therefore $$ \sum\_{w\_i \in \Sigma} \Pr\_L\[w\_j|w\_i\] = \frac{\sum\_{w\_i \in \Sigma} \\#(w\_i,w\_j) + \sum\_{w\_i \in \Sigma} 1}{\\#w\_i + |\Sigma|} = \frac{\\#w\_i + |\Sigma|}{\\#w\_i + |\Sigma|} = 1. $$
> 1 votes

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: Can there exist two minimal dfa for same regular language?
As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my understanding produce same language -please correct me if i am wrong ),then formed the minimal DFA for both of them,used equivalence method to show they are equal-by making table(i call it as like this but ,may be you say it something different you will know when you see the table). But contrary to this that for all language there exist a single minimal dfa.I found that both minimal dfa formed by my method can't be reduced to a single minimal dfa . which means for a language we could have 2 minimal dfa (here i found 2 , they could be more by this result)

I used two language , here in L1 i used "absolute function" in"|n(a)- n(b) |" ,

L1 ={ |n(a) - n(b)|=3m ,m is set of integers(positive or negative-but be aware the it hardly makes any difference if "m" is negative ,as we have used "absolute function" on the difference so "m" will always positive}. here "n(a)" is number of "a" in the string and similarly n(b). In simple words " L1 is the language generated by taking absolute difference of (n(a)-n(b)) and then checking that the length of string is divisible by 3 or not ".

Now comes the second language L2 = {(n(a) - n(b))mod 3 = 0 }

below are my methods used please correct me where i am wrong.

# Answer
After looking closely again to the minimization of the dfa1 you will found that dfa1 = dfa2 so both the language are equal.

during minimisation of dfa1 you will find that state 1=4 and 2=3 hence the final combination will be

$\pi$0 ={1,2,3,4} {0} (0 length-(by length i mean length of string) equivalent)

$\pi$1 = {1,4} {2,4} {0} (1 length equivalent )

$\pi$3 = {1,4} {2,4} {0} ( 2 length equivalence)

hence $\pi$2 =$\pi$3 means the dfa1 has been minimized. And when you make the tansition-table of minimized dfa1 its equal to dfa2.
> 1 votes

---
Tags: automata, regular-languages, finite-automata
---


# Question
Title: How can we form a graph from this problem?
So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written `"If we had intermingled common nodes across different branches, we would have got a graph instead"` I am unable to visualize how a graph can be formed out of this. Will it be a graph with only 2 columns? Please help

Source: https://loveforprogramming.quora.com/Backtracking-Memoization-Dynamic-Programming

# Answer
> 1 votes
If you just want the visualization, then have a look at this

---
Tags: algorithms, graphs, data-structures, binary-trees
---


title: communities problem with union and find

text:
# Question
Title: communities problem with union and find
I am trying to solve the following problem:

Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M\[1\]\[2\]=1$, $1$ and $2$ are friends (assuming symmetry it is also true that $M\[2\]\[1\]=1$). If $M\[2\]\[3\]=1$, then $\\{1,2,3\\}$ is a community. If all other entries are $0$, then $\\{0\\}$ is a community by itself, $\\{4\\}$ is a community by itself, etc. One can think of $M$ as representation of a graph with $V$ nodes, and $E$ edges. $M$ is $VxV$ matrix and the entries with value $1$ correspond to edges of an undirected graph. For the above example, the total number of communities is $V-2$.

I need to explain the following:

If we solve the above problem with union and find operations (weighted quick union), it will take $O(E+Vlog(V))$ time, explain.

I wrote the code for this. I am also including weighted union and find algorithm code as well below for completeness (but it is a standard known algorithm I guess). With the way I implement it, it does not look like this algorithm takes O(E+Vlog(V)) time. I need to understand how can this be done in O(E+Vlog(V)) time.

It is said that find operation takes O(log(V)) time because the tree is almost balanced with weighted quick union algorithm.

This is my code:

The code for weighted quick union and find (given):

```
public class WeightedQuickUnion {

    int[] parent; // parent[i] = parent of i
    int[] size; // size[i] = number of sites in subtree rooted at i
    int count; // number of components

    /**
     * Initializes an empty union–find data structure
     * Each site is initially in its own
     * component.
     * n is the number of sites
     */
    public WeightedQuickUnion(int n) {
        count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /**
     * Return the number of components.
     *
     */
    public int count() {
        return count;
    }

    /**
     * return the component identifier for the component containing p.
     * p the integer representing the item
     */
    public int find(int p) {
        validate(p);
        while (p != parent[p])
            p = parent[p];
        return p;
    }

    // validate that p is a valid index
    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
        }
    }

    /**
     * return true if the the item p and item q are in the same component.
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * Merge the component containing p with the
     * the component containing q.
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }

```

# Answer
> 0 votes
You are using **Adjacency matrix** representation, instead just maintain a list of pairs of friend (i.e. edge list) and iterate it once.

---
Tags: algorithms, graphs, union-find
---


# Question
Title: DFA that accepts any integer $n$ such that $n \bmod 7 =1$
It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.

Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.

# Answer
I assume you are talking about integers encoded in some base $b \geq 2$, and we're reading the integer from left to right.

An inductive hint: say we have read the number $n$ so far, and our inductive assumption is that we are in state $n \bmod 7$ (so we have 7 states). We read the digit $d$. Our next state should be $bn + d \bmod 7$. How do we correctly determine what state to go to, since we don't know $n$?

Well the trick is that while you don't know $n$, you do know $n \bmod 7$. And:

$$bn + d \equiv b(n \bmod 7) + d\mod 7$$

So for example, in base $10$, if we are in the state $3$ (meaning $n \equiv 3 \mod 7$) and we just read the digit $8$, our next state will be $10\cdot 3 + 8 \equiv 3 \mod 7$. In other words, state $3$ points to itself on reading digit $8$ in base $10$.
> 3 votes

# Answer
Place 7 nodes. Number them from 0 to 6. In Any time, in whatever node we are, represents the current number module 7. So starting node is 0. And note 0 is the accepting node.

For each node, there are 7 outgoing edges (from 0 to 6.) Say we are in node `i`; outgoing edge `j` from `i`, connects the node `i` to node `(i*10+j) mod 7`.
> 1 votes

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


# Question
Title: There could not be an edge from u to v in a DAG, if w is before v in a topological order
I am trying to prove that given a DAG. **There exists a valid topological ordering that has v in front of u iff there is no path from u to v.** The proof is related to the fact that reverse DFS post visit order satisfies the condition of topological order. How do I construct a proof?

# Answer
> 0 votes
Assume that there is path $u \rightarrow v$ as well. Then we have a cycle. What does this mean in terms of topological order? Can there be such an order? Whether u comes first or v comes first depends on where you start!

---
Tags: algorithms, graphs, proof-techniques, dag
---


# Question
Title: Which calculating running time are correct?
Let $C$ be an array with length $n$ (assume the elements are cities with some properties). We have some properties sorted by importance. For example, 1.area, 2.population size, .... We use the following algorithm to find the best city according to sorted properties:

We choose the first property and examine each city. Then we delete half of the cities. (assume we can do this by $O(n)$ time.) Now we apply the second properties and again delete half of the remain cities. We continue this way until one city remains.

Can we say the running time is equal to $O(n)$ according to the recursive function $T(n)= T(n/2)+ O(n)$, and the master theorem or the running time is equal to $n \log(n)$ because we use binary search and in each iteration, we apply an operator in linear time?

which is correct and why another one is incorrect?

# Answer
> 1 votes
The $T(n)= 2 T(n/2)+O(n)$ is $\mathcal{O}(n \log(n))$

Your recursion $T(n)=T(n/2)+O(n)$ is $\mathcal{O}(n)$ by The 3rd case of The Master Theorem.

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


# Question
Title: How can I write this backtracking algorithm using dynamic programming?
**Problem:**

There are $n$ points on a map, $p\_1,..p\_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer separately patrol a point). The point $p\_i$ must be visited before $p\_j$ if $i\< j$

I can write a backtracking algorithm to check all possible paths to cover $n$ points by two officers. However, the time complexity of that program is $O(2^n)$.

I wonder if I can write it using a dynamic programming. I can't distinguish the subproblems and common ones.

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University

# Answer
> 1 votes
Let $m(i,i)$ be the **optimal solution** when two officers cover $i$ points and one of them is at the point $i$.

Let $m(i,j) \mid 0\le j \< i $ be a solution (not optimal) when two officers cover $i$ points and one of them is at the point $i$ and the other officer is at the point $j$. Let $d(i,j)$ be the distance between $p\_i$ and $p\_j$.

$$m(i,j) = \begin{cases} 0 &\text { when } i=0 \\ m(i-1,j) + d(i-1,i) &\text { when } 0\le j \< i \\ \min \\{ m(i-1,k) + d(k,i)\mid 0\le k\<i \\} &\text { when } i = j \\ \end{cases}$$

When $i \neq j$, to have a solution (not optimal) for $m(i,j)$ we just need to have a solution for $m(i-1,j)$ to cover $i-1$ points, and we then move the officer at $i-1$ to the point $i$ to cover this point.

When $i = j$, to have an ***optimal solution*** for $i$ points, we look for the minimum cost to reach from a ***solution*** with $i -1$ points to an optimal solution with $i$ points by moving an officer from the point $k$ ($0 \leq k \< i$) to the point $i$.

# Answer
> 1 votes
Since this question is a part of homework assignment, for which you have demonstrated substantial amount of work and progress (or non-progress), I will give an explicit and strong direction below. See if you can complete the rest.

Dynamic programming is about combining optimal solutions to overlapping subproblems. What are the subproblems here? Let us construct the subproblems as simply as possible but whose solutions are strong enough to deduce the solutions of a large subproblem. In this particular homework assignment, the subproblems can be **$t(i,j)$, the minimal traveling distance for one officer to reach point $p\_i$ and the other officer reaches point $p\_j$**. I will let you figure out the following.

* Suppose you have got the value of $t(i,j)$ for every possible $i$ and $j$. Can you deduce the answer to the original problem easily?
* Build the hallmark and the most essential content of dynamic programming, the recurrence relation of the wanted quantities of subproblem here, i.e., the recurrence relation of $t(i,j)$. Can you compute the value of $t(i,j)$ at a "larger" subproblem from its values at "smaller" subproblems?

Just in case you didn't know or you forgot, you only need to solve each smaller problem once by recording its answer somewhere when you have computed its answer for the first time. When it is time you need the answer to the same smaller problem again, you will just retrieve it from your records.

---

Per questioner's request, I am writing the base case and the recurrence relation for $t(i,j)$ as defined above. Let $d(i,j)$ be the distance between $p\_i$ and $p\_j$. Without loss of generality, we will assume either $0=i=j$ or $i\<j$ since once started patrolling, two officers will reach different points.

$$t(i,j) = \begin{cases} 0 &\text { when } 0=i=j \\ t(i,j-1) + d(j-1,j) &\text { when } 0\le i\<j-1 \\ \min \\{ t(k,j-1) + d(k,j)\mid 0\le k\<j-1 \\} &\text { when } 0\le i=j-1 \\ \end{cases}$$

How can one find the recurrence relation above? It is sort of like thinking backwards from the ending. Suppose two officers are at $p\_i$ and $p\_j$ respectively where $i\<j$. What happened just before? One of the officers was at $p\_{j-1}$ and one of the officers just traveled from some points to $p\_j$. There are two cases, which correspond to the recurrence relations above respectively.

* Those two officers are the same officer. That means the location of the other officer, $p\_i$ is different from $p\_{j-1}$.
* Those two officers are different. The officer at $p\_{j-1}$ stayed at the same point and the other officer traveled from $p\_k$ for some $k\neq j-1$ to $p\_j$. That is, the former officer must be at $p\_i$, that is, $p\_i=p\_{j-1}$.

The above base case and recurrence relations can be implemented immediately as a recursive algorithm. Since the recurrence relations here are simple enough, it should be easy to convert the recursive algorithm to an iterative procedure.

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


# Question
Title: Variant of interval scheduling with varying task durations
I am probably just missing the correct term for my problem to find the solution but here it goes:

I have a set of tasks with a given duration and an interval for each task in which it has to be completed. I now need to find start times for the tasks, so that

1. each tasks is completed within its interval
2. no task overlaps with another task

Sketch:

# Answer
> 1 votes
The deterministic version of your problem (i.e. to determine whether there is a valid arrangement) is strongly NP-complete by a reduction from 3-Partition, as suggested in \[1\].

Given an instance $x\_1,x\_2,\ldots,x\_{3m}$ of 3-Partition, let the duration in your problem be $\[0, mB+m\]$ where $B=\sum\_{i=1}^{3m} x\_i/m$. For each element $x\_i$, there is a task with duration $x\_i$. The intervals for these tasks are all $\[0, mB+m\]$. In addition, there are additionally $m$ tasks with duration $1$, and their intervals are respectively $\[B, B+1\], \[2B+1, 2B+2\],\ldots,\[mB+m-1,mB+m\]$. Note the positions of these additional tasks are fixed.

Since we can assume $B/4\<x\_i\<B/2$ for all $i$ in 3-Partition, we can see there is a valid partition if and only if there is a valid arrangement in your problem.

---

\[1\] Garey, M. R., & Johnson, D. S. (1977). Two-processor scheduling with start-times and deadlines. *SIAM Journal on Computing*, 6(3), 416-426.

---
Tags: algorithms, optimization, greedy-algorithms, scheduling, intervals
---


# Question
Title: How can a fully encrypted homomorphic program resist copying?
Let's say that we have an original homomorphically encrypted program with any possible code inside. What methods can it use to ensure that it is impossible to create an exact copy of it? Are there such ways?

I understand that a person without a key will not see the internal content of a homomorphically encrypted program, I'm interested in whether it is possible to limit the exact copying of this program entirely.

# Answer
Homomorphic program encryption, assuming you want it fully operational, is not possible. At some point of time actual operations are executed (directly or in obfuscated form).
Encryption of any kind does not prevent copying, because with physical access to hard drive you can make verbatim copy at any moment.
There is also a huge slowdown with program obfuscation (like in Gentry's garbled scheme)/communication that drastically reduces realistic use.
> 1 votes

# Answer
Files can't resist copying. Files themselves are completely passive and the operating system decides what can and cannot happen to them.
> 1 votes

---
Tags: encryption
---


# Question
Title: Floating point Euclidean norm optimization
Past few days I've been struggling with floating point number exercises, trying to learn how they work and what are their limitations. The exercise I've encountered today is as follows:

> The Euclidean norm of an n-dimensional vector $x$ with components $x\_{1}...x\_{n}$ is defined by: $$||x||\_{2}=\left(\sum\_{i=1}^{n} x\_{i}^{2}\right)^{1/2}$$ How would you avoid overflow and harmful underflow in this computation?

I've come up with this solution, but I'm not sure if it really makes sense:

> There are some problems with underflow and overflow that can occur when computing Euclidean norm.Firstly, the component $x\_{i}$ of the vector can be in the machine range, however its square root might be not. It is possible, that the square of $x\_{i}$ can be either too small (underflow - $x\_{i}$ considered to be 0) or too large (overflow) or the sum of the squared components can be too large (overflow again).The solution could be implementing an algorithm, that firstly splits the components of the vector 'x' into 3 parts:
>
> 1. small magnitude numbers, for which underflow might occur: $x\_{i}\<y$
> 2. medium magnitude numbers, where $y\leq x\_{i}\<Y$
> 3. large magnitude numbers, for which $x\_{i}\>Y$
>
> When $y$ and $Y$ are thresholds set by machine precision limits. Then, small magnitude numbers will be scaled by a scalar $S$ and then their sum of squares 'unscaled' by the same $S$. Similarly, large magnitude numbers will be scaled by an appropriate $s$, and then descaled again.

I've taken the algorithm from this book, but I'm not sure if I understand it correctly and if I explained the solution properly. It would be also helpful to reproduce this algorithm in R language, however, I don't understand the explanation to the point of replicating it.

# Answer
Roughly right.

You can first calculate the sum of squares. If it overflows, then you find a large power of two M, divide all numbers by M, calculate the norm, and multiply by M. If overflow happens at $2^{1023}$, then you have numbers greater than $2^{500}$. Dividing by M=$2^{700}$ means you get neither overflow nor underflow.

You may have underflow in some of the squares. Check how much error an underflow can produce. Then you check how large a sum wouldn’t be influenced by these errors. If the sum of squares is larger than say $2^{-900}$ then there may be products with underflow but they don’t affect the sum. In that case you are fine.

Otherwise, multiply all numbers by M, calculate the norm, and divide by M.
> 0 votes

---
Tags: floating-point
---


# Question
Title: Kosaraju with connections between SSCs (strongly connected components)
*First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem.*

**I have a graph which i condense into SSC (strongly connected components) by Kosaraju's algorithm. Now what I need is to find connections between those SSCs. The best would be to somehow inject this process into Kosaraju's runtime but I did not come up with tangible solution there. My algorithm is logically similar to the one on wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s\_algorithm *(I can't provide my code because it is a school assignment)***

*I would very much appreciate any tip from smarter folk than me. :D*

---

*More information/What I came up with:* I thought about it and did not come up with better solution then after finishing Kosaraju I will go through each vertex, check his in/out edges and if the edge's other side is not part of this SSC than add this edge as connecting edge to my SSC. But this process is very expensive as i need to:

1. For each vertex go over its all edges
2. Compare every edge end with vertexes in SSC.

Computation would be something like **edges** X **\[vertexes in its SSC\]**. If my graph would be one huge SSC than I would basically get V\*E. There is no way this is best approach, I bet it is actually one of the worst.

# Answer
This should be more tangible solution.

What I can do (and I will get guaranteed speed of 2E) is in each vertex make note in which SSC it ended (during Kosaraju). Then just iterate over edges and compare if both ends have same SSC and if not, just add the connection into vector of SSCs (which is basically new graph but vertex = SSC). Also all necessary accesses are O(1).

Question solution detailed (optimalizations below can be also used in solution above).

In certain scenarios solution above will performe way better than what I proposed in question. Even if we (in question solution)

1) Check if there is only one SSC and in that case did nothing

2) Order all SSCs from smallest to biggest SSC -\> so we would not have to go over the biggest ones vectors, because it would be already connected

The question solution would still get serious performance hit on big graphs with almost no certainties and very variable performance.
> 0 votes

# Answer
Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|\*|E|)$. A complexity of $O(|V|\*|E|)$ would be the case if for each vertex you performed an operation on all of the edges in the graph, which you have no reason to do.

$O(|V|+|E|)$ complexity is actually the same complexity as calculating the SCCs in the first place, and therefore your general idea can, in-fact, be used (be careful with the details).
> 2 votes

---
Tags: algorithms, graphs
---


title: Uniqueness of byte arrays

text:
# Question
Title: Uniqueness of byte arrays
Consider the situation, when you're given `M` byte arrays of size `N`, and you need to check if all of them have unique content (so there are no two arrays that have the same sequence of bytes). What would be the best option to check this condition?

From my point of view, there are several approaches available for this problem (the examples provided below are relevant for Go programming language ecosystem):

**Compare hash sums**

Take some fast non-cryptographic hash (like murmur3) and compute hash sum from the every array. Store every sum in a set and find duplicates. Provided that hash is `O(N)`, the whole operation should be `O(M*N)`:

```
func unique(arrays [][]byte) bool {
   set := newSet()
   for _, array := range arrays {
       sum := hash(array)
       dump := hex(sum)
       if set.contains(dump) {
            return false
       }
       set.add(dump)
   }
   return true
}

```

**Compare arrays bytewise**

In Go there is `[bytes.Equal][2]` function written in pure assembly which can utilize platform-dependent optimizations. So it's possible to iterate over the arrays and check equality pairwise for `O(M^2*N)`:

```
func unique(arrays [][]byte) bool {
    for i := 0; i < len(arrays); i++ {
        for j := i + 1; j < len(arrays); j++ {
            if result := bytes.Equal(arrays[i], arrays[j]); result {
                return false
            }
        }
    }
    return true
}

```

Despite the fact that this algorithm has worse computational complexity, it may run faster due to above-mentioned optimizations.

**String(?) algorithm**

1. Take `i`th byte from every array
2. Compare bytes;
3. If all are unique, return true;
4. If there are repeating values, repeat step `#1` for `(i+1)`th bytes for only those arrays which had equal `i`th bytes.

This should be also `O(M*N)`, because in the worst case one would have to completely compare all arrays. But it seems like this approach will bring too much overhead (I mean state of algorithm between iterations etc.)

Please share your opinion about the optimal way to solve this problem.

# Answer
> 2 votes
You need to read all items in the worst case. Assume you have written some algorithm which reads items in any order and processes them with any amount of cleverness. And I'm your opponent and try to make you read as many items as possible.

Here's what I do: Whenever your algorithm reads an item I store an "X" just before you read it. I do that except when you have read one array completely, which consists of all X, and you are reading the last item of another array, in which case I store a value that makes this row different from all other rows that were read completely. When you read the very last item, I can decide to store a value that makes all arrays unique, or I store another X and you have two arrays that are identical.

Whatever you do, until you read the very last item you don't know whether two arrays are identical or all arrays are unique.

---
Tags: strings, equality
---


# Question
Title: Difference between graph-partitioning and graph-clustering
What is the difference between graph-partitioning and graph-clustering in graph theory?

# Answer
> 11 votes
Graph partitioning and graph clustering are informal concepts, which (usually) mean partitioning the vertex set under some constraints (for example, the number of parts) such that some objective function is maximized (or minimized). We usually have some specific constraints and objective function in mind. However *graph partitioning* and *graph clustering*, as vague informal concepts, are pretty much the same.

# Answer
> 3 votes
There tends to be an emphasis on edges in partitioning. ("A good partition is defined as one in which the number of edges running between separated components is small." from the English Wikipedia.) On the other hand, clustering tends to be about vertices (or the connectedness of the subgraph of neighbors of a vertex). This is entirely a linguistic artifact and I would not expect it to be as prevalent in non-English writing.

(Of course, it's challenging to separate the roles of vertices and edges in defining nearness or connectedness, so such a distinction is necessarily somewhat artificial.)

# Answer
> 2 votes
Both creates partitions/blocks. In partitioning number of partitions/blocks 'K' is given in advance. While in clustering we do not know what number of partitions/clusters/groups will be formed by clustering. Following screenshot is taken from this text.

---
Tags: graphs
---


title: Maxflow problem

text:
# Question
Title: Maxflow problem
I need help with the following practice problem on network flow:

> A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the railway system which we can think of as a directed graph $G = (V, E)$ with $V$ being the cities. Each spy $i$ has a starting point $s\_i\in V$ and needs to reach the consulate of a friendly nation; these consulates are in a known set of cities $T\subseteq V$. In order to move undetected, the spies agree that at most $c$ of them should ever pass through any one city. Our goal is to find a set of paths for each of the spies (or detect that the requirements cannot be met). Model this problem as a flow network. Specify the vertices, edges and capacities, and show that a maximum flow in your network can be transformed into an optimal solution for the original problem. You do not need to explain how to solve the max-flow instance itself.

My thought was to make all edge weights have capacity $c$. Then, just use Ford-Fulkerson to find paths in the residual graph. But I'm not sure if this is the right approach because maybe we will have more than $c$ go through a node.

# Answer
The question clearly states that the capacities apply to cities, not railway lines. Cities are vertices in the graph, not edges.
> 0 votes

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


# Question
Title: Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm
For the following algorithm,

> $X\leftarrow \\{(i, n - i) | i = 1, ..., n- 1\\}$
>
> **while** $\max\_{(a, b)\in X}b \> 0$ **do**
>
> $\quad X \leftarrow \\{(|a - b|, \min\\{a, b\\})|(a, b) \in X\\}$
>
> **return** $\max\_{(a, b)\in X}a$

show that the algorithm does **not** run in $o(n \log ^k n)$ for any constant $k$.

Summary: the algorithm uses the Euler's subtraction-based algorithm to compute the largest factor of $n$ in $1$ to $n - 1$.

My work: I can prove the upper bound case that $T(n) \in O(n^2)$. Since $n = (a + b)$ is strictly decreasing, gcd computation for each tuple takes at most $n$ operations. Since there are $n-1$ elements, $T(n) \in O(n^2)$.

I can also prove the lower bound case that $T(n) \in \Omega(n \log n)$. The best case for computing gcd of a single tuple occurs if $a = c\_1 \cdot b$ or $b = c\_2 \cdot a$ for $c\_1, c\_2 \in \mathbb{N}$. Then, the running time is $\Omega{\log n}$. Therefore, the total running time is $T(n) \in \Omega(n \log n)$.

My problem: But I don't know how to proceed from here. Basically, I need to prove $T(n) \in \Omega{(n^{1+\epsilon})}$ for $\epsilon \> 0$. This means I need to prove something polynomial with the gcd computation of a single tuple.

Can anyone help me out with this problem?

# Answer
It seems the algorithm tries to calculate n-1 gcd's simultaneously, and performs n-1 operations as long as one of the gcd's is not found. And since at least one gcd (gcd (n, 1)) takes n iterations, it is $\Theta (n^2)$.

Of course that is just due to the stupid implementation, but probably a good example for estimating the runtime of an *algorithm*, not the runtime of a problem.

You need to show that $n^2$ is not $o(n log^k n)$ for any k.
> 1 votes

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


# Question
Title: lower bound proof with adversary argument
We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full or empty is to put them in the Walkman and try it out. We cannot tell which one is empty or full if we put inside one full and one empty.

The question is to find the minimum needed step to run the walkman (to find 2 full batteries)

I modeled the problem like that :

> Let the Walkman br a function $f$ which take two arguments and returns 1 if the walkman works, and 0 otherwise. $$ f\colon \\{b\_1,b\_2 \dots b\_{30}\\} \times \\{b\_1,b\_2 \dots b\_{30}\\} \rightarrow\\{0,1\\}$$

I was given a hint to use the Turán lemma:

> When a graph $G=(V,E)$ with $V$ the vertex set and $|V|=n$ does not contain a $k$-clique with $k \>1$, then $$ |E|\leq \left(1-\frac{1}{k-1}\right)\frac{n^2}{2} $$

The idea was to consider the batteries as vertex and create a complete graph and then when $ f(b\_i,b\_j)=0$ we delete the edge between $b\_i$ and $b\_j$.

Using the adversary argument I have to prove that the lower bound to find the battery must be 18, so any help how to solve this?

# Answer
Here comes $A$ (is it Apass?), the simple smart adversary Walkman.

**For the first 18 pairs of batteries you put into $A$ to test, $A$ will just not operate**. So you will need at least 18 tests before finding 2 full batteries. On the other hand, the accepted answer to another question by OP shows 18 tests is enough. So the desired lower bound is 18 tests.

The real question is, of course, does this behavior of $A$ come from an actual combination of batteries regardless of whichever 18 pairs of batteries are chosen to be tested?

The answer is yes.

Instead of proving for the case of 30 batteries and 18 tests, let us prove the general cases, which is actually easier since we can use mathematical induction.

(**Consistency of $A$**) Let $n\ge2$ be a positive integer. $S=\\{\\{i,j\\}\mid 1\le i\lt j\le 2n\\}$ with $\\#|S|\le n+3$. Let $B=\\{i\mid1\le i\le 2n\\}$. Then there exists a function $f: B\to \\{0,1\\}$ such that $|f^{-1}(0)|=n$ (and hence $|f^{-1}(1)|=n$ as well) and for each $\\{i,j\\}\in S$, if $f(i)\ne 0$, then $f(j)=0$ (If we interpret 0 as an empty battery, this means no pair in $S$ will make $A$ operate).

**Proof by induction on $n$**

* $n=2$. $|S|\le5$. Since there are 6 different pair of numbers can be drawn from $\\{1,2,3,4\\}$, there is one pair of numbers which is not in $S$. WLOG, let that pair of numbers be 1 and 2. Let $f(1)=f(2)=1$ and $f(3)=f(4)=0$. Case proved.
* Suppose it is true for $n$. Let us consider the case of $n+1$, where $S'=\\{\\{i,j\\}\mid 1\le i\lt j\le 2(n +1)\\}$ with $\\#|S'|\le(n+1)+3$ and $B'=\\{i\mid1\le i\le 2(n+1)\\}$.
Since $\\#|S'|=n+4$ and each element of $S'$ has two numbers, the total number of appearances of numbers in all elements of $S'$ is $2(n+4)$, which is smaller than the double of $2(n+1)$. So there must be one number that appears less than 2 times. WLOS, let that number be $2n+2$. There are two cases.

+ If $2n+2$ appears in $\\{j, 2n+2\\}\in S'$ for some $j$, WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.
    + If $2n+2$ does not appear in any element of $S'$, choose any element $j$ that appear at least once in some element of $S$. WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.

Consider $S=\\{\\{i,j\\}\in S'\mid 1\le i\lt j\le 2n \\}$. Since either $2n+2$ or $2n+1$ appears in one of elements of $S'$, $\\#|S|\le\\#|S'|-1\le n+3$. By induction hypothesis, we can define $f$ on $B$ such that $f^{-1}(0)=n$. Extend $f$ by letting $f(2n+2)=1$ and $f(2n+1)=0$. Now we can see that $f^{-1}(0)=n+1$ and for each $\\{i,j\\}\in S'$, if $f(i)\ne 0$, then $f(j)=0$, thus concluding our proof.

---

Apparently, Turán lemma is not needed if it can be useful here at all.

---

Here are several related exercises I designed for the interested readers.

Exercise 1. Check that the original question is the case when $n=15$.

Exercise 2. Verify the last statement of the above proof.

Exercise 3. (**the case of 3 batteries**) Another Walkman needs 3 full batteries to operate. Let's say we have a mixed set of 30 batteries, 20 of which are empty and the remaining 10 of which are full. The only way to test whether a battery is full or empty is to put 3 of them in the Walkman and try it out. However, we can not tell which one is empty or full when the Walkman does not operate. What is the minimum number of tests that guarantees to identify 3 full batteries? Prove your answer.

Exercise 4. What is the average number of steps for the testing strategy shown here? Can we do better (this last question is a research topic)?
> 1 votes

---
Tags: algorithms, graphs, proof-techniques, lower-bounds, adversary
---


# Question
Title: What are the simplest examples of programs that we do not know whether they terminate?
The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?

# Answer
A pretty simple example could be a program testing the Collatz conjecture:

$$ f(n) = \begin{cases} \text{HALT}, &\text{if $n$ is 1} \\ f(n/2), & \text{if $n$ is even} \\ f(3n+1), & \text{if $n$ is odd} \end{cases} $$

It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.
> 47 votes

# Answer
> The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not.

"We" are not an algorithm =) There is no *general* algorithm that could determine if a given program halts **for every program**.

> What are the simplest (smallest) known examples of such programs?

Consider the following program:

```
n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

```

Function is\_perfect checks whether n is a perfect number. It is unknown whether there are any odd perfect numbers, so we don't know whether this program halts or not.
> 32 votes

# Answer
You write:

> The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not.

This is a non-sequitur, in both directions. You succumb to a common fallacy that is worth addressing.

Given any fixed program $P$, its halting problem ("Does $P$ always halt?") is *always* decidable, because the answer is either "yes" or "no". Even if you can not tell which it is, you know that one of the two trivial algorithms that answer always "yes" resp. "no" solves the $P$-halting problem.

Only if you require that the algorithm should solve the Halting problem for all¹ programs can you show that no such algorithm can exist.

Now, knowing that the Halting problem is undecidable does not imply that there are any programs *nobody* can not prove termination or looping of. Even if you are not more powerful than a Turing machine (which is only a hypothesis, not proven fact), all we know is that no single algorithm/person can provide such proof for *all* programs. There may be a different person being able to decide for each program.

Some more related reading:

---

So you see that your actual question (as repeated below) has nothing to do with whether the halting problem is computable. At all.

> What are the simplest (smallest) known examples of \[programs we don't know to halt or loop\]?

This in itself is a valid question; others have given good answers. Basically, you can transform every statement $S$ with unknown truth value into an example, provided it *does* have a truth value:

$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$

Granted, these are not very "natural".

---

1. Not necessarily *all*, but "many" in some sense. Infinitely many, at least.
> 13 votes

# Answer
Given that the Busy Beaver problem is not solved for a 5-state-2-symbol Turing machine, there must be a Turing machine with only five states and only two symbols which has not been shown to halt or not when started for an empty tape. That is a very short, concise, and closed program.
> 9 votes

# Answer
Any open problem regarding the existence of a number with particular properties gives rise to such a program (the one which searches for such a number). For example, take the Collatz conjecture; since we don't know if it is true, we also don't know if the following program terminates:

```
    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1

```
> 7 votes

# Answer
the question is tricky because decidability (the CS equivalent formalization/ generalization of halting problem) is associated with *languages* so it needs to be recast in that format. this seems to not be pointed out much, but many open problems in math/ CS can be readily converted to problems (languages) of unknown decidability. this is because of a tight correspondence between theorem proving and (un)decidability analysis. for example (somewhat like the other answer wrt odd perfect numbers), take the twin primes conjecture which dates to the Greeks (over 2 millenia ago) and is subject to major recent research advances eg by Zhang/ Tao. convert it to an algorithmic problem as follows:

> Input: *n*. Output: Y/N there exists at least *n* twin primes.

the algorithm searches for twin primes and halts if it finds *n* of them. it is not known if this *language* is decidable. resolution of the twin primes problem (which asks if there are a finite or infinite number) would also resolve the decidability of this language (if it is also proven/ discovered how many there are, if finite).

another example, take the Riemann hypothesis and consider this language:

> Input: *n*. Output: Y/N there exist at least *n* nontrivial zeroes of the Riemann zeta function.

the algorithm searches for nontrivial zeroes (the code is not especially complex, its similar to root finding, and there are other equivalent formulations that are relatively simple, which basically calculate sums of "parity" of all primes less than *x* etc) and halts if it finds *n* of them and again, its not known if this language is decidable and resolution is "nearly" equivalent to solving the Riemann conjecture.

now, how about an even more spectacular example? (*caveat,* probably more controversial as well)

> Input: c: Output: Y/N there exists an O(nc) algorithm for SAT.

similarly, resolution of decidability of this language is nearly equivalent to the P vs NP problem. however there is less obvious case for "simple" code for the problem in this case.
> 0 votes

# Answer
Write a simple program that checks whether for every n, $1 ≤ n ≤ 10^{50}$, the Collatz sequence starting with n will reach the number 1 in less than a billion iterations. When it has the answer, let the program stop if the answer is "Yes", and let it loop forever if the answer is "No".

We cannot tell whether this program terminates or not. (Who is we? Let's say "we" is anyone who could add a comment to my answer). However, someone with an incredibly powerful computer might tell. Some genius mathematician might be able to tell. There might be a rather small n, say n ≈ $10^{20}$ where a billion iterations are needed; that would be in reach of someone with a lot of determination, a lot of time, and a lot of money. But right now, we cannot tell.
> 0 votes

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


title: Max subarray product

text:
# Question
Title: Max subarray product
Is it possible to solve the max sub-array product problem using divide and conquer?

Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) which has the largest product.

Example 1:

Input: \[2,3,-2,4\]
Output: 6
Explanation: \[2,3\] has the largest product 6.

# Answer
> 1 votes
Yes, you can obviously solve it like that.

If you are dividing the array into two parts, than the maximal sub-array can be completely in the left half, completely in the right half, of it starts in the left and ends in the right half. The first two cases you will find using the recursive calls. For the third case, you have to do a little bit of work:

In that case the maximal subarray consists of two parts, a suffix from the left half of the array, and a prefix of the right half of the array. Either both products are positive, or both negative. It's obvious that you want their absolute value as big as possible, therefore you need to know the largest and smallest suffix from the left half, and the largest and smallest prefix from the right half. You can compute both in $O(n)$ time, which gives you the recurrence relation $T(n) = 2 T(\frac{n}{2}) + O(n)$ which gives you $T(n) = O(n \log n)$ by the master theorem.

Notice, you can also compute these values during the recursive calls, which gives you $T(n) = 2 T(\frac{n}{2}) + O(1)$, and this gives you the final complexity $T(n) = O(n)$.

---
Tags: algorithms, divide-and-conquer, maximum-subarray
---


title: Mutual Exclusion by disabling interrupt

text:
# Question
Title: Mutual Exclusion by disabling interrupt
I am reading *William Stallings* operating system book which gives this pseudo-Code for disabling interrupt to achieve Mutual Exclusion

```
while (true) {
 /* disable interrupts */;
 /* critical section */;
 /* enable interrupts */;
 /* remainder */;
}

```

But I don't get why there is a `While` loop in the code which is `true` this means that this part of the code repeats forever but why?

# Answer
> 1 votes
The while loop with true condition is just to ensure this process can enter and exit its critical section repeatedly. This usage is quite common when we are discussing concurrency programming.

Take a moment to reflect. How can you **create an environment to demonstrate easily the effect of two or more different concurrent processes are, for example, contending for one shared resources**? If you let each process just try to enter the critical section once, it might be hard to produce the various particular situations that could happen only to concurrent running processes. It may just happen all processes enter the critical section in order once and then exit. However, if we use a while(true) loop to run the processes long enough, it will be much more probable to observe all sorts of phenomenons.

---
Tags: operating-systems
---


# Question
Title: How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?

Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I cannot understand What kind of function lays there?

# Answer
> 1 votes
Consider the function $$ f(n) = \begin{cases} g(n) & \text{if $n$ is even}, \\ g(n)/n & \text{if $n$ is odd}. \end{cases} $$

# Answer
> 1 votes
$\Theta$ means "always roughly as big as". Little-o means "getting smaller and smaller compared to". Big-O means "always at most as big as" (all up to some constant).

Functions that are in O (g(n)) but neither in $\Theta (g(n))$ nor in o(g(n)) are those that vary between being as large as g(n) up to a constant and being arbitrary small compared to g(n). That's what Yuval's example does; it is often as large as g(n) but sometimes arbitrarily small compared to g(n). Both infinitely many times.

---
Tags: asymptotics, landau-notation
---


# Question
Title: How can I reduce the time of this program
I solved a problem similar to the knapsack problem.

There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w\_1,...w\_n$ in a pre-defined order (the best order). We can put an item in the package 1 or the package 2 or close one package and replace it with a new package and put the item in it. What is the minimum number of packages?

Let $m(n,p1,p2)$ be the minimum number of packages for $n$ items where the capacity of package 1 is $p1$ and the capacity of the package 2 is $p2$.

I must keep track of the free capacity of each package which is not always $P$ (empty state)

let $w\_n$ be the weight of the $n\_{th}$ item.

It's my solution using dynamic programming:

```
def packaging(N, P1, P2, w):
    M = np.zeros((N+1, P1+1, P2+1))
    for n in range(N+1):
        for p1 in range(P1+1):
            for p2 in range(P2+1):
                wn = 0 if n == 0 else w[n-1]
                if n == 0:
                    M[n][p1][p2] = 0
                elif wn > p1 and wn > p2:
                    M[n][p1][p2] = M[n-1][p1][p2] + 1
                elif wn > p1:
                    M[n][p1][p2] = M[n-1][p1][p2-wn]
                elif wn > p2:
                    M[n][p1][p2] = M[n-1][p1-wn][p2]
                else:
                    M[n][p1][p2] = min(M[n-1][p1-wn][p2], M[n - 1][p1][p2 - wn])
    return M[N][P1][P2]

```

Its order is $O(NP^2)$. There is an $O(NP)$ solution for it. How can I enhance my solution to reach it?

Further updates might come to reformat the solution in a mathematical notation.

Source: Tehran University, Fall 2018, Advanced algorithms practice

# Answer
> 1 votes
A very nice question.

Here is the brief idea of a more efficient algorithm. The central idea is how to fill one package and close it with minimal unfilled capacity left. That is a standard knapsack problem that can done efficiently with dynamic programming.

However, now we have two packages available, each might have different initial capacities available, as you have pointed out.

What to do? Then do two knapsack problems at the same time!

Right after you have closed one package, you have two packages, one with $a\_1$ available capacity and the other with $a\_2$ available capacity. We have two knapsack problems here: how to fill the one with $a\_1$ capacity as much as possible without bursting the other one and how to fill the one with $a\_2$ capacity as much as possible without bursting the other one. **Solve them separately. Compare the result to find which one get less free capacity left**. Choose that package and its maximal filling found just now and close it. Fill the other one with the items that should have been used before closing the previous one. Repeat the process.

(Further update might come to clarify the above explanation. But this should get you going.)

# Answer
> 0 votes
Thanks to whoever came up with the problem. *Very* nice problem. It is NP-complete even for the trivial case where the sum of weights equals 2P, because then it is equivalent into splitting a set of n weights into two subsets of equal weight, which is NP complete. It's different from bin packing, because one package must be closed when weights with a total of 2P have been processed. Interesting problem.

Your problem asked for ONE package size P. The same for all packages. Somehow you changed that to two package sizes. That explains why you need N\*P1\*P2 steps instead of N\*P. I still have no idea what you are trying to do.

Have you actually tried your algorithm with real numbers and got any success? If all wi = 1, P1 = P2 = P, n = 2P + k, then the solution is k. For example, 100 items of size 1, packed into packages of size 10, your solution says it needs 80 packages.

I suspect that you were asked to produce a greedy algorithm which will produce not the optimal solution, but a near optimal solution. I am saying that because an optimal solution is difficult and will take exponential time.

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


# Question
Title: Why does RAID-5 require an additional disk for parity blocks?
I know that RAID-5 consists of block-level striping across multiple disks, but using an additional parity-check block on each disk .. and that at least two disks are required for striping.

And it's obvious that each parity block is specific to each disk it belongs to (and so there is no need for allocating an additional disk).

Image from Wikipedia.

However I've been unable to understand why in fact there is an additional disk required for parity checks, as I found on this article:

> The minimum number of disks in a RAID 5 set is three (two for data and one for parity).

Any idea?

# Answer
> 11 votes
I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery from a failed disc.

Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and $1$ are data and disc $2$ is parity. "Parity" means that the $b$th block of disc $2$ is the xor of the $b$th blocks of discs $0$ and $1$. The point is that, if any single disc fails, we can recover its data because the $b$th block of *any* disc is the xor of the $b$th block on the other two discs. For this to work, it's crucial that the parity data is on a separate discs. If you only had two discs and put the parity data on those discs (e.g., each disc was two-thirds data blocks and one-third parity blocks) then the failure of a single drive would destroy some blocks and their corresponding parity data, so you'd be unable to recover the data using just what was left on the remaining disc.

RAID-5 is the same idea except that, instead of putting all the parity data on the last disc, it's spread across all the discs. So, for a three-disc set-up, a third of the blocks would have parity data on disc $2$, a third on disc $1$ and a third on disc $0$.

The point of using RAID-5 rather than RAID-4 is that every time you write data, the corresponding parity block must be updated. If all parity data is on the same disc, that disc will be written to much more than the other discs ($k$ times as much, in a $k$-disc sytem), so it will fail faster. Spreading the parity data across the discs evens out the wear on them.

---
Tags: storage, fault-tolerance, space-partitioning
---


# Question
Title: Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?
I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book *Introduction to the theory of computation*. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

# Answer
> 3 votes
Take some time to browse the book. Sipser has the result, but stated as Problem 2.30a. Luckily an answer is provided. (In my (third) edition it is Problem 2.18a, from which I quote below.)

> "\[...\] we construct a PDA $P'$ that recognizes $C\cap R$ with the set of states $Q\times Q'$. $P'$ will do what $P$ does and also keep track of the states of $D$. \[...\]"

# Answer
> 5 votes
There is a simple proof using context-free grammars. Let $L$ be a context-free language with context-free grammar $\langle V,T,P,S \rangle$, and let $R$ be a regular language with DFA $\langle \Sigma,Q,q\_0,F,\delta \rangle$. We construct a new context-free grammar whose nonterminals consist of a new start symbol $S'$ and the triples in $Q \times V \times Q$. The idea is that $\langle q\_1,A,q\_2 \rangle$ generates all words $w \in L(A)$ such that $\delta(q\_1,w) = q\_2$.

Let us assume, without loss of generality, that the grammar is in Chomsky normal form: all rules are of the form $A \to BC$, $A \to a$, $S \to \epsilon$; and $S$ doesn't appear on the right-hand side of a rule. We can carry out the construction even without this simplifying assumption – that's a good exercise for you.

The rules of the new grammar are:

1. For every $q \in F$: $S' \to \langle q\_0, S, q \rangle$.
2. If $S \to \epsilon$ is a rule and $q\_0 \in F$: $S' \to \epsilon$.
3. For every rule $A \to a$ and for every $q \in Q$: $\langle q,A,\delta(q,a) \rangle \to a$.
4. For every rule $A \to BC$ and for every $q\_1,q\_2,q\_3 \in Q$: $\langle q\_1,A,q\_3 \rangle \to \langle q\_1,B,q\_2 \rangle \langle q\_2,C,q\_3 \rangle$.

Correctness proof left to you.

# Answer
> 3 votes
I don't know of a simple *proof*, but there is a proof where the underlying idea is simple to understand.

Suppose you have a PDA $N$ (deterministic or nondeterministic; doesn't matter) which accepts the language $L\_M$, and whose set of states is $S$. And further suppose you have a DFA $M$ with $T$ as its set of states which accepts the language $L\_M$.

Conceptually, you can construct a new PDA, whose set of states is the Cartesian product $S \times T$, and awhich "runs" both the PDA and the DFA in parallel. A transition from state $(s\_i,t\_j)$ to state $(s\_p,t\_q)$ does whatever the PDA does when transitioning from state $s\_i$ to $s\_p$, but also takes the appropriate transition from $t\_j$ to $t\_q$.

An accept state in this new PDA is any state which corresponds to an accept state in both $M$ and $N$. Then this PDA should, assuming we get the details right, accept the language $L\_M \cap L\_N$.

There are a lot of details that you need to get right, which makes the proof fairly technical. So it's not a short proof. But it's simple to understand the idea behind it.

If you want to understand how this works, I would suggest trying to write a reasonably formal proof that the intersection of two regular languages is regular using a similar construction.

And as an additional exercise: Why can't you use this technique to prove that the intersection of two context-free languages is context-free?

# Answer
> 2 votes
We should imagine the way a pushdown automaton (PDA) works.

A PDA has a read-only head pointing at the input string. At each moment, it is resting at some index of the input string. And while the PDA is still running, it only moves from left to right once. But it may stay at some indices to "think" for a while.

Having said that, we can see that there are two kinds of transitions:

1. Consuming transition: the transitions that moves the input head one step to the right.
2. Non-consuming transition: the transitions that keeps the input head in place. These ones only manipulate the stack for sure.

Now, construct the cross product of the PDA $\mathbb{P}$ and the DFA $\mathrm{A}$ as usual, i.e. with the set of states as cartesian product of the set of states of $\mathrm{P}$ and the set of states of $\mathrm{A}$.

So, for each consuming transition of $\mathbb{P}$, we only allow it in the cross product PDA when the corresponding transition in $\mathrm{A}$ is also true.

---

And while the PDA is "thinking" (i.e. performing non-consuming moves), the DFA $\mathrm{A}$'s state must remain unchanged.

---
Tags: regular-languages, context-free, proof-techniques
---