# Question
Title: Valid method to prove NP completeness of a problem?
Suppose we are given that checking if there is a Hamiltonian path in a graph is NP Complete (HP problem). I want to prove that given a graph, node x, and node y, checking if there is a Hamiltonian path between x and y is NP Hard (HPN problem). Here is my proof:

Define a conversion from HP to HPN as follows:

`result = False
for x in Nodes(G):
 for y in Nodes(G):
 result = result or hpn(G,x,y)
return result`

This clearly solves the HP problem since it considers all possible starting and ending points. Also, HPN is called a polynomial (O(|Nodes(G)|^2) number of times. Hence, HPN must be NP-Hard since if it wasn't HP wouldn't be NP Complete and we know that this isn't true.

I understand I haven't used a reduction in the formal sense in my proof. However, I wanted to know if these sorts of "conversions" are valid in proving NP Hardness/Completeness.

Edit : The goal was actually to prove NP hardness, not completeness, sorry!

# Answer
No, they're not. **NP**-completeness is defined using many-one reductions and you've used a Turing reduction. The difference, in a nutshell, is that for a many-one reduction, you're only allowed to make one call to the function you've called `hpn`, and you must return its result as your result. Schematically, your reduction needs to look like:

```
Compute a graph G' and vertices x and y from the input graph G;
return hpn(G',x,y);

```
> 1 votes

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


# Question
Title: Determining a value in an algorithm on its first run
I was given the following algorithm as a solution to one of my problems. However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never set the first time. Can someone explain this to me? Am I just missing where c' gets set?

This is for Kleinberg and Tardos, Chapter 11, Question 12.

# Answer
Posting Yuval Filmus's comment as an answer since they didn't:

> It’s a typo - should be $c’=$ instead of $c’-$ in line 5.
> 2 votes

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


# Question
Title: Worst Case Scenario for Quicksort algorithm with pivot element n/2
What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the worst case occurs if:

1. Array is already sorted in same order
2. Array is already sorted in reverse order
3. All elements are same

and that the complexity in that cases is $\mathcal{O}({n^2})$. However, this cases should not be a problem if I take the middle index of the partition as my pivot element.

# Answer
> 3 votes
Since you're not guaranteed anything about the order of the input, it's possible that the n/2 position has the smallest/largest element of the input. Then quicksort will proceed and put everything else on one side of the pivot.

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


# Question
Title: How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length
If I have the following system, I am wondering how to calculate the number of valid strings it contains.

The system is something like this, which can have arbitrary variations.

* Only consists of an alphabet $\Sigma$.
* It can't spell any words in a blacklist word list $\rho$.
* It can't have more than $n$ characters of the same type in a row.
* Every word $\omega$ it generates is no more than $m$ in length.

So for example, we might have this system:

* $\Sigma = (a, b, c, d, e, f, g, h)$
* $l = \texttt{len}(\Sigma)$
* $\rho = (\texttt{bed},\texttt{fad},\texttt{dad},\texttt{bead},\texttt{deed},\texttt{fade})$
* $n = 3$ (so can't match `/aaaa|bbbb|cccc|dddd|eeee|ffff|gggg|hhhh/`)
* $m = 20$

Say we have a random number generator, which uses a radix algorithm to convert it into a string using the characters in the alphabet $\Sigma$. The thing is, this random number generator might generate strings like the following, which we just have to drop and forget, then try generating another one until we get one that matches the constraints. Don't know of a better way to do that, but that's beside the point. So it might generate these ones, which are *invalid*.

```
afbcdeabeadbeaaaadaf
[bead and aaaa]
bedddddagheadfffeeee
[bed and dddd]

```

So the question is, how do I calculate how many strings are invalid? I know how to calculate the possible strings given the constraints, that is simply:

$$z = l^m = 8^{20}$$

I don't know how to calculate the number of strings that are invalid though, *in a general way* (so I can change the value of $m$, $n$, $\Sigma$, or $\rho$). Wondering how to formulate this problem mathematically or algorithmically so that I can figure out that "there are x number of invalid strings", and so I can calculate:

$$y = z - x$$

to get the total amount of possible strings given the constraints.

# Answer
The language of valid strings is regular. Build a DFA to recognize the language, then use standard techniques to count the number of words accepted by the DFA (see Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038).

How do you build a DFA to recognize the language? Via a product construction. Let $L\_a$ denote the set of all words that don't have $n+1$ $a$'s in a row, and let $L\_\rho$ denote the set of all words that aren't in the blacklist. Then your language is $\Sigma^{\le m} \cap L\_\rho \cap L\_a \cap L\_b \cap \cdots$. You can easily build DFAs for each of the individual languages, and then use the product construction to build a DFA for their intersection.

Warning: the size of the DFA can potentially blow up exponentially in $|\Sigma|$. However, this will remain polynomial in $n$, $m$, and $|\rho|$.
> 1 votes

---
Tags: algorithms, discrete-mathematics, constraint-satisfaction
---


title: Solve Maze Without Feedback

text:
# Question
Title: Solve Maze Without Feedback
Suppose that we have the following maze (\_ = open, + = blocked), and we can move left,right,up,down:

```
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ _ _ _ _ _ _ _ + _ _ _ _ _ _ _ + _ _ _ _ _ _ _ +
+ _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ + + + + + + _ + + + + + + + + + _ + + + + + + +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ + + + + + + + + + + + + + + + + + + + + + + + +

```

Given that we start at a random open square in the maze, assuming there is no feedback as to if a move was successful (i.e. we encountered a blocked square) and not knowing where we started, what is a sequence of moves such that we will always end up in the square S.

# Answer
This question is just a puzzle, so clearly off-topic here, but still it's funny to find answer :-)

For this specific maze there exists sequence of moves that we end up in S.

> a) 12\*D - and we can end up on top of any +:

```
 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ @ _ @ @ _ + _ @ @ _ @ @ _ + _ @ @ _ @ @ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + @ @ @ + _ + _ + @ @ @ + _ + _ + @ @ @ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ @ @ @ @ @ _ @ @ @ @ @ @ @ @ @ _ @ @ @ @ @ @ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ @ _ @ @ _ @ _ @ @ _ @ @ _ @ _ @ @ _ @ @ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + @ @ @ + _ + _ + @ @ @ + _ + _ + @ @ @ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

```

> b) 22\*L

```
 + + + + + + + + + + + + + + + + + + + + + + + + +
 + @ _ _ _ _ _ _ + @ _ _ _ _ _ _ + @ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + @ _ _ + _ + _ + @ _ _ + _ + _ + @ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + @ _ _ + _ + _ + @ _ _ + _ + _ +@_ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

```

> c) 1\*R

```
 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ _ _ _ _ _ + _ @ _ _ _ _ _ + _ @ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ @ _ + _ + _ + _ @ _ + _ + _ + _ @ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ @ _ + _ + _ + _ @ _ + _ + _ + _ @ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

```

> d) 3\*U

```
 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ _ @ _ _ _ + _ @ _ @ _ _ _ + _ @ _ @ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ _ @ _ _ _ _ _ _ _ @ _ _ _ _ _ _ _ @ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

```

> e) 19\*L

```
 + + + + + + + + + + + + + + + + + + + + + + + + +
 + @ _ _ _ _ _ _ + _ _ _ _ _ _ _ + _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

```

> Now it's simple: 5\*D, 16\*R, 7\*D, 5\*U, 3\*R, 2\*D and finish
> 1 votes

---
Tags: algorithms, maze
---


# Question
Title: What are the differences between computer vision and image processing?
What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?

# Answer
In **image processing**, an image is "processed", that is, transformations are applied to an input image and an output image is returned. The transformations can e.g. be "smoothing", "sharpening", "contrasting" and "stretching". The transformation used depends on the context and issue to be solved.

In **computer vision**, an image or a video is taken as input, and the goal is to understand (including being able to infer something about it) the image and its contents. Computer vision uses image processing algorithms to solve some of its tasks.

The main difference between these two approaches are the goals (not the methods used). For example, if the goal is to enhance an image for later use, then this may be called image processing. If the goal is to emulate human vision, like object recognition, defect detection or automatic driving, then it may be called computer vision.
> 31 votes

# Answer
Basically, Image processing is related to enhancing the image and play with the features like colors. While computer vision is related to "Image Understanding" and it can use machine learning as well.
> 1 votes

# Answer
In Image processing, image is taken as an input and a processed image come as an output but in computer vision image is taken as input and we get information as the output about the image.
> 0 votes

---
Tags: terminology, computer-vision, image-processing, education
---


title: shortest path tree algorithm

text:
# Question
Title: shortest path tree algorithm
Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$.

I want to find an algorithm for the shortest path tree rooted in $s$ with time complexity of $O(V+E)$.

We may assume that all vertices are reachable from $s$.

I thought of running something like BFS traversal on $G$ and for each vertex $u$ I examine, for each neighbor $v$ of him, I'll check that $\delta(u)+w(u,v)=\delta(v)$ and if so, I'll add $(u,v)$ to the output SPT.

Is that sounds right? or has any pitfalls I haven't thought about? If so, how would you prove that? by induction?

# Answer
> 3 votes
Use a proof by induction on the length of the paths. In other words, prove first that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 1; then that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 2; and so on.

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


title: The power of relativised proofs

text:
# Question
Title: The power of relativised proofs
I've been trying to understand why, for instance, even though there are oracles $A$ for which $P^A \neq NP^A$, we still don't know if $P=NP$.

As I understand it, it's because it's easy to construct languages that can only be efficiently taken advantage of in a non-deterministic settings. For example, pick a single arbitrary string and call that your language; then all you need is non-determinism to try every string and you're okay in $NP$, yet still trapped into brute force in $P$.

My question is, what exactly separates this from a regular $NP$ problem? Why is this fundamentally different from an $NP$ problem that accepts only on some arbitrary predetermined certificate (or is it even possible to construct such a problem)?

Is it just the fact that $NP$ problems are required to have some sort of structure, whereas in the relativised case we're free to build our language arbitrarily? Or is there some deeper difference I'm missing?

# Answer
> 3 votes
The reason has little to do with the problems in $\mathbf{P}$ and $\mathbf{NP}$ themselves; it is due to the *computation models* they describe. Recall that, if $A$ and $B$ are complexity classes, $A^B$ only really makes sense if $A$ can be expressed as a class of machines which can be equipped with oracle access (to the problems in $B$). $A^B$ *does not make sense* if $A$ cannot be expressed in terms of machines (which can use oracles).

This means the class $A^B$ is not obtained simply by taking the class $A$ (as a set of languages) and performing some operation on them using $B$ as a parameter (as the rather deceivingly simple "exponentiation-looking" notation would lead you to believe). Rather, it is a class belonging to a *machine model of its own accord*, namely the machine model of $A$ given oracle access to problems in $B$. In fact, it is rather surprising that the whole thing is well-defined, that is, that taking any two machine models for $A$ and granting both of them oracle access to $B$ yields the same class $A^B$ (actually, this only works if you are so careful as to give them both oracle access in a proper way).

That we can obtain relativizing results from certain (i.e., relativizing) proofs is, thus, even more surprising. As you can see, these are the sort of proofs which still work *even if you replace the machine models with any closely-related ones* (i.e., their oracle versions). Since they generalize in this way, they actually turn out to be very useful in that we can derive corollaries from them (for the respective relativized classes). An example of such a proof would be the inclusion $\mathbf{BPP} \subseteq \Sigma\_2$.

In a nutshell, $\textbf{P}^A \neq \textbf{NP}^A$ does not really tell us anything about the relation of $\textbf{P}$ to $\textbf{NP}$ since $\textbf{P}^A$ (resp., $\textbf{NP}^A$) can be a class which is *completely unrelated* to $\textbf{P}$ (resp., $\textbf{NP}$). For an extreme example, consider what happens when $A$ is the class of languages which are (efficiently) reducible to the halting problem; in this case $\mathbf{P}^A$ contains languages *which are not even recursively enumerable*. And there are even classes which have been shown to be equal, but which *do not relativize in almost any way* (e.g., $\mathbf{IP}$ and $\mathbf{PSPACE}$).

---
Tags: oracle-machines, relativization
---


# Question
Title: What is an approximation factor for the Greedy Motif Search algorithm?
What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native speaker and there is almost nothing about it available in my first language which makes it really hard to even understand the definition of the "approximation factor" which may lead to this question that could be rather obvious to answer.

A possible algorithm is shown on page 4: http://veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf

I know that there isn't a known approximation factor because sources like the book "An Introduction to Bioinformatics Algorithms" are stating it.
I haven't really formed thoughts on it, because I'm not certainly sure what the definition of approximation factor is in a case like this. What I mean is: "The approximation ratio, or performance guarantee of algorithm A is defined as its maximum approximation ratio over all inputs of size n".
I would've thought that it may be unknown due to the fact that we could have a input of infinite, which is probably not the right thought in this regard. Another thought I had was that the algorithm has no lower bound for the optimal solution.

# Answer
> 1 votes
Quoting Master’s Thesis in Computer Science by Finn Rosenbech Jensen0, Dec. 2010, Greedy Motif algorithm approximation factor, using common superstring1 and its linear approximation2, was proved it cannot be better then 2.
Using proof by Kaplan and Shafir3 author shows that $\mid t\_{greedy}\mid = 3.5 * OPT(S)$.

\[0\]: Master thesis by Rosenbech Jensen
\[1\]: Tarhio, J. and E. Ukkonen (1988). A greedy approximation algorithm for constructing shortest common superstrings.Theor. Comput. Sci. 57(1),131–145.
\[2\]: Blum, A., T. Jiang, M. Li, J. Tromp, and M. Yannakakis (1994, May).Linear approximation of shortest superstrings. InProceedings of the23rd Annual ACM Symposium on Theory of Computing, pp. 328–336. \[3\]: Kaplan, H. and N. Shafrir (2005). The greedy algorithm for shortest su-perstrings.Inf. Process. Lett. 93(1), 13–17.

---
Tags: algorithms, approximation, greedy-algorithms, bioinformatics
---


# Question
Title: Do the minimum spanning trees of a graph have the same number of edges with a given weight?
I'm asking about the answer here:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

I didn't understand the best answer here

> Choose edge $e \in T\_1 \mathop{\Delta} T\_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T\_1 \mathop{\Delta} T\_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T\_1$ and assume $T\_1$ has more edges of weight $\min W$ than $T\_2$.

First of all, what does minimum *disagreeing* weight mean?

> assume $T\_1$ has more edges of weight $\min W$ than $T\_2$.

Does the above line mean, $T\_1$ has multiple edges with weight $\min W$

> Now consider all edges in $T\_2$ that are also in the cut $C\_{T\_1}(e)$ that is induced by $e$ in $T\_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T\_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T\_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T\_2 \cap C\_{T\_1}(e)$ (where $T\_1$ is the updated version) have weights other than $g(e)$.

This paragraph seems to be a problem for me. So, we remove edges with weight $e$ which is also $\min W$ and replace it with $e'$. So we do that for all edge weight $e$ present in $T\_1$

> Therefore, we get after finitely many steps to a setting where all edges in $T\_2 \cap C\_{T\_1}(e)$ (where $T\_1$ is the updated version) have weights other than $g(e)$.

I didn't understand this line at all. What is supposed to be $g(e)$?

> Now we can always choose $e' \in C\_{T\_1}(e) \cap T\_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree
>
> $\qquad \displaystyle T\_3 = \begin{cases} (T\_1 \setminus \\{e\\}) \cup \\{e'\\} &, w(e') \lt w(e) \\\\[.5em\] (T\_2 \setminus \\{e'\\}) \cup \\{e\\} &, w(e') \gt w(e) \end{cases}$
>
> which has smaller weight than $T\_1$ and $T\_2$; this contradicts the choice of $T\_1,T\_2$ as minimal spanning trees. Therefore, $W\_1 = W\_2$.

Why is $w(e') \lt w(e)$ here? isnt $e'$ same as $e$ ? and why does $T\_1,T\_2$ contradict as minimal spanning trees?

# Answer
The question and this post refers to this answer at its version 2.

> First of all, what does minimum disagreeing weight mean?

The better word should have been "distinguishing". If the set of edges of some fixed weight in $T\_1$ is different from that of $T\_2$, then $T\_1$ and $T\_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal trees.

> What is supposed to be $g(e)$?

That is a typo. It should have been $w(e)$.

> Why is $w(e') \lt w(e)$ here? isn't $e'$ same as $e$ ? and why does $T\_1,T\_2$ contradict as minimal spanning trees?

Let us use a new dummy variable instead of $e'$ for the last part of that answer.

Let $f \in C\_{T\_1}(e) \cap T\_2$. Had $f$ weighed the same as $e$, we should have update $T\_1$ by using $f$ instead of $e$. Since we have done all such updates, $f$ must weigh differently from $e$. That is the conclusion in the previous paragraph, "all edges in $T\_2 \cap C\_{T\_1}(e)$ (where $T\_1$ is the updated version) have weights other than $w(e)$".

There are two disjoint cases.

* the case when $w(f)\lt w(e)$. Consider the spanning tree $(T\_1 \setminus \\{e\\}) \cup \\{f\\}$, which is lighter than $T\_1$.
* the case when $w(f)\gt w(e)$. Consider the spanning tree $(T\_2 \setminus \\{f\\}) \cup \\{e\\}$, which is lighter than $T\_2$.

In either case, we have found a spanning tree that is lighter than a minimum spanning tree, which is a contradiction.
> 1 votes

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


# Question
Title: On the time complexity of finding independent sets in hypergraphs
I am interested in the complexity of the following problems:

> (a) Finding an independent set of a fixed size in an arbitrary hypergraph
>
> (b) Finding an independent set of maximum size in an arbitrary hypergraph

It is well known that the analogues of (a) and (b) (say (a') and (b')) for graphs are NP-complete and NP-hard, respectively. However, I am having trouble finding references for the complexity of (a) and (b). In fact, all of the papers I've been able to find on these two problems (for hypergraphs) just cite the fact that (a') and (b') are NP-complete and NP-hard, as if these results trivially generalize to (a) and (b). Is this actually the case? If not, can anyone provide references that prove the complexity of (a) and (b)?

# Answer
> 3 votes
The ubiquitous principle is that **a generalized problem is at least as hard to the original problem**. This rather trivial principle is applied as truism in most if not all papers.

---

Here is a specific version of that principle for the case of time-complexity.

**Lemma**. Let $A,B, C$ be three languages such that $A= B\cap C$ and $A\not=C$. ($C$ is considered as a generalization of $A$.) It takes polynomial time to determine whether $x\in B$. Then deciding $C$ is as least as hard as deciding $A$ modulo polynomial time. If $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

**Proof**. Let $\beta$ be a polynomial-time algorithm that decides $B$. Suppose we have an algorithm $\gamma$ that decides $C$. Let $\alpha$ be the following algorithm:

* Given input string $x$, run $\beta$ to determine if $x\in B$. If not, return no. If yes, run $\gamma$ to determine if $x\in C$. If not, return no. Return yes otherwise.

It is routine to check that $\alpha$ return yes if and only if the input is in $A$, i.e., $\alpha$ decides $A$. Since $\beta$ takes polynomial time, deciding $C$ is at least as hard as deciding $A$ modulo polynomial time.

It follows immediately that if $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

---

Let

* $A=\\{\langle G,s\rangle \mid \text{ there is an independent set of size }s\text{ in an ordinary graph G}\\}$. (I use the phrase "ordinary graph" or simply "graph" to contrast with "hypergraph". "General graph" sounds more like hypergraph. Indeed, hypergraph is a generalization of an ordinary graph.)
* Let $B=\\{\langle G\rangle\mid G \text{ is an ordinary graph}\\}$.
* Let $C=\\{\langle G, s\rangle \mid \text{ there is an independent set of size }s\text{ in a hypergraph G}\\}$.

The lemma tells us that deciding $C$ is at least as hard as deciding $A$.

---

**Exercise 1.** Explain that deciding whether a graph is 3-colorable is at least as hard as deciding whether a given planar-graph is 3-colorable. (In fact, both problems are NP-complete.)

**Exercise 2.** Prove that it is NP-complete to determine whether there is independent set of given size in a given triangle hypergraph. A triangle hypergraph is defined as a hypergraph where each edge is a set of 3 vertices.

# Answer
> 2 votes
We known that maximum independent set (MIS) is NP-complete on general graphs. Because every graph is also a hypergraph, we have that MIS is also NP-complete on hypergraphs.

---
Tags: graphs, time-complexity
---


# Question
Title: Is an undirected graph consisting only two connected vertices cyclic?
I have two questions:

1. Does acyclic/cyclic classification only apply to directed graphs?
2. If not, does the following undirected graph have any cycle?

A --- B

# Answer
> 1 votes
(1.) No, undirected cycles are also natural.

(2.) No, what you describe is a path on two vertices. It does not form a cycle, since by definition, you cannot find a subset of the edges that form a *path* where the first node of the path corresponds to the last.

To be sure about these type of things, you must always look at the definitions.

---
Tags: graphs
---


# Question
Title: Space-efficient representation of potentially very large arbitrary-precision rationals?
I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to:

1. 2/3
2. 1/10
3. 4 * 10 ^ 1,000,000,000,000

I know arbitrary precision rationals can be represented by pairs of arbitrary precision integers, and they can be normalized using gcd, so operations like equality testing are efficient. But trying to represent (3) this way would quickly exhaust memory.

(3) can be dealt with efficiently and faithfully with a scientific-notation-like representation, but this can't faithfully represent all rationals.

Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with *very* large numbers efficiently?

# Answer
> 1 votes
> Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with very large numbers efficiently?

No.

We cannot even represent all integers faithfully as well as deal with very large integers efficiently. If we want to express all integers between 1 and $2^{1,000,000,000,000}$ faithfully, we need about $1000,000,000,000$ bits, i.e. 1000G bits for a single number on average. If we do not have that many bits, pigeon hole principle tells us that there must be two numbers that will be represented exactly in the same way.

Almost nothing around that magnitude of bits can be said to be efficient by the absolute scale even if you get hold of most powerful supercomputers. In fact, multiplication of two integers with mere 1000001 digits within 2 seconds is consider a pretty hard problem on a programming site.

As D.W. pointed out, "the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes."

Or we can restricted our playingground to those numbers that can be represented faithfully easily and, hopefully, manipulated efficiently. For example, the search for the largest prime numbers are mostly restricted to the Mersenne numbers, which are of the form $2^n-1$. Mersenne primes include all top 5 largest primes known to mankind, the largest one being is merely $2^{82,589,933} − 1$, i.e. a humongous number with 24,862,048 digits.

# Answer
> 2 votes
Representing a rational number as ${a \over b} \times c^d$ where $a,b,c,d$ are integers can represent all three classes of numbers you mentioned efficiently. You can do standard operations on numbers represented in this way, but some of those operations will be inefficient: for instance, $10^{10000000}+1$ will be inefficient.

For any representation you have in mind, there will be some rational numbers that can be specified concisely in English but that require a huge amount of memory to represent with that representation scheme, so there is no one answer that will handle everything efficiently -- the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes.

---
Tags: algorithms, number-formats
---


# Question
Title: Maximal cliques in a multipartite graph - efficient?
I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.

Now I am looking for the optimal subset such that each of the N classes is represented exactly once. Not all objects can be combined with each other, e.g. object (N=1,k=1) might not be compatible with (N=2, k=4).

I can formulate this problem as looking for the maximal clique on a N-partite graph (but maybe there are other formulations that I'm not aware of). My question is whether an efficient algorithm exists for solving this problem.

From https://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph:

> This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.
>
> If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time

This implies that an efficient algorithm might exist for my problem, but I can't find it...

# Answer
A *maximal clique* and a *maximum clique* are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$.

You mention bipartite graphs, but the complete $k$-partite graph is not bipartite if $k \geq 3$ (but it is for $k=2$). A bipartite graph contains no triangles, so in such a graph a maximum clique has size (at most) 2, so an efficient algorithm can just return a single edge.

Let $G = K\_{n\_1,\ldots,n\_q}$ for positive integers $n\_1,n\_2,\ldots,n\_q \geq 2$. You can verify that $G$ has maximum clique size $q$, and a total of $n\_1 \cdot n\_2 \cdots \cdot n\_q$ such cliques. An algorithm for enumerating all of them reduces to basic combinatorics (pick one vertex, then how many choices for the remaining vertices do you have when forming a clique?)
> 3 votes

# Answer
I'm afraid this is NP-hard, as it's essentially just the regular Maximum Clique problem in disguise: *every* graph $G = (V, E)$ is a $|V|$-partite graph, with a single vertex in each part. So if an algorithm could efficiently solve the $(N=|V|, k=1)$ setting of your problem, it could efficiently solve Maximum Clique.
> 2 votes

---
Tags: graphs, combinatorics, np-hard, clique
---


# Question
Title: Why reverse pipeline stages in cycle-level simulator?
In pipeline simulator exercise, it says that:

> Traversing the stages in backwards order simplifies the instruction flow through the pipeline.

Also, in gpgpu-sim source code, the stages are reversed (line `2442`):

```
void shader_core_ctx::cycle()
{
    m_stats->shader_cycles[m_sid]++;
    writeback();
    execute();
    read_operands();
    issue();
    decode();
    fetch();
}

```

Why? What problem it solves? Can anyone elaborate a bit or give a pointer to books/papers on this particular "trick"?

Many thanks!

# Answer
> 1 votes
This solves the problem that, if you put them in "forward" order, an instruction can stream all the way from fetch to writeback in a single cycle of the emulator. An other solution is explicitly emulating the clocked logic between the stages as it would exist in hardware, but it takes more effort that way. Running the stages in reverse is a simple trick that also ensures that instructions properly "wait" at the boundaries between stages.

# Answer
> 0 votes
`execute()` will look something like:

```
void execute(){
    switch(decode_execute_op){
        case EXECUTE_ADD: execute_result = readop_operand1 + readop_operand2; break;
        //...
    }

}

```

Then `read_operands()` can simply write to the globals `readop_operand1` and `readop_operand2` to let `execute()` get access to the result.

However there will need to be a way to propagate duplicate data that needs to skip pipeline stages. For example issue and read\_operands can forward the execution operation through to execute which will finally actually use it.

---
Tags: cpu-pipelines
---


# Question
Title: Are there variations of the regular runtimes of the Big-O-Notation?
There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically incorrect.

Or would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$? I can't and don't need to figure out runtimes yet and I do not need to improve anything, but I'd need to know if this how you describe your functions in reality.

# Answer
> I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect.

Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations.

However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ **is** $O(n^2)$. Similarly, $O(\log (n^2))$ **is** $O(\log n)$. That might be surprising to beginners. However, those equalities are more or less the very reason why big $O$-notations were introduced, to hide a multiplicative constant factor that is often hard to pin down and relatively insignificant.

> Would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$?

It is not an improvement at all if the time-complexity of an algorithm is changed from $O(5n^2)$ to a $O(3n^2)$ or from $\Omega(5n^2)$ to $\Omega(3n^2)$, because $O(5n^2)$ is $O(3n^2)$ while $\Omega(5n^2)$ is $\Omega(3n^2)$. So it is incorrect to say the time-complexity is improved from $O(5n^2)$ to $O(3n^2)$. It is correct to say the time-complexity of an algorithm is improved from $5n^2$ to $3n^2$, of course.

---

**Exercise 1.** Show that $O(5n^2)=O(3n^2)=O(n^2)$.

**Exercise 2.** Show that $O(\log n)=O(\log (n^2))$.

**Exercise 3.** Show that $\Omega(n^2+n)=\Omega(n^2)$.
> 21 votes

# Answer
You are always free to *not* use this notation at all. That is, you can determine a function $f(n)$ as precisely as possible, and then try to improve on that. For example, you might have a sorting algorithm that makes $f(n)$ comparisons, so you could try to come up with another sorting algorithm that only does $g(n)$ comparisons. Of course, all kinds of functions $f(n)$ exist (in theory) and can also come up (in practice).

Instead of treating the Big Oh notation as mysterious magic where you have to consult wizards to ask whether you can do something, you should look at its definition. Respect the definition, and then do whatever you need to get your job done.
> 13 votes

# Answer
While the accepted answer is quite good, it still doesn't touch at the real reason *why* $O(n) = O(2n)$.

# Big-O Notation describes *scalability*

At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to describe how an algorithm scales with the number of inputs.

Take a binary search, for example. Given a sorted list, how do you find an arbitrary value inside it? Well, you could start at the middle. Since the list is sorted, the middle value will tell you which half of the list your target value is in. So the list you have to search is now split in half. This can be applied recursively, then going to the middle of the new list, and so on until the list size is 1 and you've found your value (or it doesn't exist in the list). Doubling the size of the list only adds one extra step to the algorithm, which is a logarithmic relationship. Thus this algorithm is $O(\log n)$. The logarithm is base 2, but that doesn't matter - the core of the relationship is that multiplying the list by a constant value only adds a constant value to the time.

Contrast a standard search through an unsorted list - the only way to search for a value in this case is to check each one. Worst-case scenario (which is what Big-O specifically implies) is that your value is at the very end, which means for a list of size $n$, you have to check $n$ values. Doubling the size of the list doubles the number of times you must check, which is a linear relationship. $O(n)$. But even if you had to perform two operations on each value, some processing, for example, the linear relationship still holds. $O(2n)$ simply isn't useful as a descriptor, since it would describe the exact same scalability as $O(n)$.

I appreciate that a lot of these answers are basically telling you to come to this conclusion yourself by reading the definition of Big-O. But this intuitive understanding took me quite a while to wrap my head around and so I lay it out to you as plainly as I can.
> 8 votes

# Answer
You can write $O(f)$ for *any* function $f$ and it makes perfect sense. As per the definition, $g(n)=O(f(n))$ if there is some constant $c$ such that $g(n)\leq c\\,f(n)$ for all large enough $n$. Nothing in that definition says that $f$ must be some sort of "nice" function.

But, as other answers have pointed out, $g(n)=O(f(n))$ and $g(n)=O(2f(n))$ describe exactly the same situation: if $g(n)\leq c\\,f(n)$ for all all large enough $n$, then we also have $g(n)\leq \tfrac{c}{2}2f(n)$, so $g(n)=O(2f(n))$, also (taking the constant to be $c/2$).

As a side issue, don't write "$\log n^2$", because it's not 100% clear what it means. You could say that it obviously means $\log(n^2)$ but almost everybody would write that as $2\log n$, so it puts doubt in the reader's mind.

Also, note that big-$O$ notation has nothing to do with runtimes *per se*. It's just a notation for relationships between functions. Those functions are often used to measure the runtimes of algorithms but that's just one application, just like measuring people's heights is just one application of numbers.
> 5 votes

# Answer
Look at the definition of O(f(n)), and you see that for example O(2n^2) and O(n^2) are exactly the same. Changing an algorithm from 5n^2 to 3n^2 operations is a 40 percent improvement. Changing from O(5n^2) to O(3n^2) isn’t actually any change, they are the same.

Again, read the definition of O(f(n)).
> 4 votes

# Answer
It may be helpful to understand that Big-O describes a *set of functions*. That is $O(f(n)) = \lbrace g(n) | \exists n,c\>0: \forall m \> n: c\times g(m) \le f(m)\rbrace$

The usage of $=$ is kind of unfortunate and using $\in$ would make that relationship a lot clearer. but the set notation symbols are a bit difficult to type so now we are stuck with the current convention.

This then shows that $O(n) = O(2n)$ Or that constant factors don't matter when defining the Big O.
> 4 votes

---
Tags: complexity-theory, time-complexity, optimization, big-o-notation
---


title: Chordal graph question

text:
# Question
Title: Chordal graph question
In the below image, the graph is being triangulated (added edges are in red). My question is simple :
**Is the red edge between nodes 7 and 10 necessary in order to obtain a chordal graph?**

(this image comes from Yaroslav Bulatov's excellent answer on https://cstheory.stackexchange.com/questions/5018/the-origin-of-the-notion-of-treewidth/5020#5020)

# Answer
> 1 votes
No, it's not necessary.

Let $G$ be the graph made by deleting the edge $\\{7,10\\}$ from the graph in the question. Any cycle in $G$ that includes $7$ and $10$ must include both $6$ and $8$, because such a cycle must be the union of two disjoint $7$$10$ paths, and $\\{6,8\\}$ is a cut that separates $7$ from $10$. However, $\\{6,8\\}$ is an edge, so any cycle in $G$ that includes $7$ and $10$ already has $\\{6,8\\}$ as a chord, so it doesn't need $\\{7,10\\}$ as well.

# Answer
> 1 votes
No, you can delete that edge and the graph remains chordal. This is so because you don't introduce an induced cycle of length 4 or more.

---
Tags: graphs
---


title: Ford-Fulkerson vs Edmonds-Karp

text:
# Question
Title: Ford-Fulkerson vs Edmonds-Karp
I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead of DFS) variant of Ford-Fulkerson algorithm.

The point is on time complexity, Ford-Fulkerson algorithm has $O(|E||f\_{max}|)$ whereas Edmonds-Karp is presented to run in $O(|V||E|^2)$. My main is question is then, how can I decide which of these algorithm is the faster on an arbitrary max-flow problem ?

I feel very unconfortable with the $f\_{max}$ even if I understand it, because determining it is the goal of the algorithm so estimating it is likely to be hard on the very general case. Depending on problem, $f\_{max}$ may be very high with respect to $|E|$, even if one can possibly apply a scale factor on all edges.

I also do not understand where the runtime difference comes from. Generally BFS and DFS have the same expected runtime, the difference between them is more on problem dependant space requirement and features like shortest path, topological order...

# Answer
Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former. In other words, EK is $O(|E|\min(f\_{max}, |V||E|))$ time (and writing it this way does add information, since $f\_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other variant of FF in preference to EK).

The above does not imply that EK is faster than a particular (say, DFS-based) variant of FF on any *particular* instance.

BFS and DFS have the same runtime, but DFS only promises to find a path from source to sink in the residual graph -- not necessarily a shortest possible such path, which BFS does promise. It's possible to show that no modification to the residual graph ever reduces the distance from the source to any vertex; with this, and the fact that BFS always finds a shortest path, it's possible to show that after finding at most $|V||E|$ augmenting paths, no source-to-sink path remains in the residual graph. This page gives a full proof -- I've only skimmed it, but note that when it says that "That is, \[the distance from the source to all other nodes\] is *always* increasing", it in fact means (or should mean) that this never decreases -- that is, the distance from the source to a particular node can stay the same after an augmentation, or it can be larger, but it can never be smaller.
> 8 votes

---
Tags: time-complexity, network-flow
---


# Question
Title: How do we place $8n$ objects in a grid of size $n \times n$?
How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in the grid and two objects cannot occupy the same cell. We are given $n\geq 100$.

Example. The following can be a $7\times7$ portion of some large grid (say $200\times200$), where 0 and 1 denote empty and filled cells respectively):

```
0000111
0101001
0011100
0110010
1010001
1001010
1100100

```

What approach one should follow to solve the problem?

---

Source: codechef.com MAY Long challenge "Ada Rooks 2"

# Answer
Given a set of objects in a cell grid, if no 4-set of it forms a rectangle with sides parallel to the sides of the grid, we will call those objects **rectangle-free**.

The more general problem is to determine sequence A072567, whose $n$-th term $M\_n$ is the size of maximal set of rectangle-free cells in an $n \times n$ cell grid. Its first 13 entries are

$$1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, \cdots$$

It looks like the value of $M\_{14}$ is unknown, which does not matter for the current problem, though.

---

We know that $M\_{q^2+q+1}=(q+1)(q^2+q+1)$ when $q$ is a power of a prime number. In particular, letting $q=4,5,9,11,13$, we get $M\_{21}=105$, $M\_{31}=186$, $M\_{91}=910$, $M\_{133}=1596$, $M\_{183}=2548$.

For a square grid of size $n\ge100$, we will select disjoint smaller square grids along its main diagonal line and fill the maximal set of rectangle-free cells in each of those smaller squares.

* If $100\le n\le 113$, select a grid of size 91 since $91\<100$ and $M\_{91}=910 \gt 8 \times 113.$
* If $114\le n\le 125$, select one grid of size 91 and one grid of 21 since $91+21\lt 114$ and $M\_{91}+M\_{21}=910 + 105\gt 8 \times 125.$
* If $126\le n\le 132$, select one grid of size 91 and one grid of 31 since $91+31\lt 126$ and $M\_{91}+M\_{31}=910 + 186\gt 8 \times 132.$
* If $133\le n\le 182$, select one grid of size 133 since $133\le 133$ and $M\_{133}=1596\gt 8 \times 182.$
* If $183\le n\le 300$, select one grid of size 183 since $183\le 183$ and $M\_{183}=2548\gt 8 \times 300.$
* if $200+100k\le n\lt200+100(k+1)$ for some $k\ge1$, select one grid of size 183 and $k$ grids of size 91 since $183+91k\lt 200+100k$ and $M\_{183}+kM\_{91}=2548+910k\>800(300+100k)\gt8n$.

---

Now the problem is shifted to realize $M\_{q^2+q+1}=(q+1)(q^2+q+1)$ for $q=4,5,9,11,13$. The realizations comes from finite projective planes that is built on top of finite fields, which is explained in detail here.

There are many packages that helps computation of finite fields.

Here is how to fill $21\times21$ grid with 105 objects. Note that there are exactly 5 objects in each row and each column.

```
000000000000000011111
010001000100010000001
000100010001000100001
001000100010001000001
000011110000000010000
010010000001001001000
000110000010010000100
001010000100000100010
000000000000111110000
010000010010100000010
000100100100100001000
001001000001100000100
000000001111000010000
010000101000000100100
000101001000001000010
001000011000010001000
100010001000100000001
100001000010000101000
100000100001010000010
100000010100001000100
111100000000000010000

```

Here is how to fill $31\times31$ grid with 186 objects, where empty cells are left as whitespaces. Note that there are exactly 6 objects in each row and each column.

```
                         111111
    1    1    1    1    1     1
  1    1    1    1    1       1
   1    1    1    1    1      1
 1    1    1    1    1        1
                    111111
    1   1   1   1   1        1
  1      1 1      1 1       1
   1  1       1  1  1      1
 1     1     1     11     1
          11111          1
    1  1  1       1  1     1
  1   1   1        1   1     1
   1     11     1     1   1
 1      1 1      1      1   1
               11111     1
    1 1      1 1      1     1
  1     1     11     1    1
   1   1   1   1        1    1
 1       1  1  1       1   1
     11111               1
    11     1     1     1  1
  1  1       1  1       1  1
   1 1      1      1 1      1
 1   1        1   1   1      1
1    1    1    1    1         1
1        1   1   1   1       1
1       1  1       1  1    1
1      1      1 1      1    1
1     1     1     1     1 1
11111                    1

```

---

**Exercise 1.** Refine the algorithm so that it uses only $M\_{21}=105$, $M\_{31}=186$, $M\_{91}=910$, $M\_{133}=1596$, i.e., without $M\_{182}$.

**Exercise 2.** (Open problem) The smallest $n$ such that we can fill $8n$ rectangle-free objects in an $n\times n$ grid is 57 since $M\_{57}=8\times57$ for $q=7$. What is the biggest $n$ such that we cannot fill $8n$ rectangle-free objects?
> 5 votes

# Answer
Here is one way to do it. I figured this out through experimentation.

For any grid of size $n \geq 100$ we completely fill out the following diagonals:

$$\[0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76\]$$

We fill these out from top left to bottom right where diagonal $0$ is the top-left to bottom-right diagonal (slope -1) starting at index $G\_{0,0}$. Diagonal $i$ is the slope -1 diagonal starting at index $G\_{0,i}$ if $i \geq 0$ or the slope -1 diagonal starting at index $G\_{|i|,0}$ if $i \< 0$. This means diagonal 20 starts at $G\_{0,20}$ and diagonal -5 starts at $G\_{5,0}$. The first few on a small $10 \times 10$ grid would look like this:

```
  |0123456789
 -+----------
 0|1010000010
-1|1101000001
-2|0110100000
-3|0011010000
-4|0001101000
-5|1000110100
-6|0100011010
-7|0010001101
-8|0001000110
-9|0000100011

```

After you have determined one of the entries in the diagonal does not cause a rectangle, the rest will follow by symmetric translation$^\*$. For instance in this example, consider entry $G\_{5,0}$. It lines up with the following entries vertically: $$\[G\_{0,0}, G\_{1,0}\]$$ And the following entries horizontally: $$\[G\_{5,4}, G\_{5,5}, G\_{5,7}\]$$ We can take each pair of these to determine which diagonal would have to be present to form a rectangle:

* $G\_{0,0}$ and $G\_{5,4}$ need entry $G\_{0,4}$ on diagonal $4$.
* $G\_{0,0}$ and $G\_{5,5}$ need entry $G\_{0,5}$ on diagonal $5$.
* $G\_{0,0}$ and $G\_{5,7}$ need entry $G\_{0,7}$ on diagonal $7$.
* $G\_{1,0}$ and $G\_{5,4}$ need entry $G\_{1,4}$ on diagonal $3$.
* $G\_{1,0}$ and $G\_{5,5}$ need entry $G\_{1,5}$ on diagonal $4$.
* $G\_{1,0}$ and $G\_{5,7}$ need entry $G\_{1,7}$ on diagonal $6$.

This is why the "next" available diagonal is diagonal $8$ because all others would cause rectangles with the existing diagonals. You can use similar logic to show that diagonals $\[-2, -3, -4\]$ would have cause rectangles earlier. This logic can apply to all of the diagonals above for grids of size $83 \times 83$ or larger.

---

We can prove this setting will always give over $8n$ entries present $P(n)$. For $n \geq 76$, the number of entries present with the given diagonals is:

$$\begin{align\*} P(n) &= n + (n-1) + (n-2) + (n-5) + (n-8) + (n-15) + (n-20) + (n-31) + (n-42) + (n-48) + (n-67) + (n-76)\\ P(n) &= 12n - 315\\ \end{align\*}$$

Clearly for $n = 100$ this satisfies:

$$1200-315 =885 \geq 800$$

Then for any $n' = n + 1$ where $n \geq 100$ we simply get:

$$\begin{align\*} P(n') & \geq 8n'\\ 12 + P(n) & \geq 8n+8\\ 12 & \geq 8 & \square \end{align\*}$$

---

$^\*$ I add this asterisk because this is not *quite* always correct. It is correct for $n \geq 100$ but not in general. Consider the following diagonals on a $7 \times 7$ grid: $$\[0, -1, 2, -5, 6\]$$ We get:

```
  |0123456
 -+-------
 0|1010001
-1|1101000
-2|0110100
-3|0011010
-4|0001101
-5|1000110
-6|0100011

```

We see this is fine for $n = 7$, however, when we move to $n=8$, this diagonals will not work:

```
  |01234567
 -+--------
 0|10100010
-1|11010001<
-2|01101000
-3|00110100
-4|00011010
-5|10001101<
-6|01000110
-7|00100011
   ^      ^

```

There is a rectangle made of the rows and columns I've pointed out. So this does not always hold with translation symmetry because sometimes the grid size is actually helping us by preventing further rows and columns from conflicting on the diagonals.

---

My procedure for finding this was just to "select the next non-conflicting diagonal" and this actually works really well for small grids. For instance, it is perfect for $n \leq 13$ we get (best comes from A072567):

```
 n | best | I filled | diagonals to use
---+------+----------+-----------------
 2 |    3 |        3 | 0, -1
 3 |    6 |        6 | 0, -1, 2
 4 |    9 |        9 | 0, -1, 2
 5 |   12 |       12 | 0, -1, 2
 6 |   16 |       16 | 0, -1, 2, -5
 7 |   21 |       21 | 0, -1, 2, -5, 6
 8 |   24 |       24 | 0, -1, 2, -5
 9 |   29 |       29 | 0, -1, 2, -5, 8
10 |   34 |       34 | 0, -1, 2, -5, 8
11 |   39 |       39 | 0, -1, 2, -5, 8
12 |   45 |       45 | 0, -1, 2, -5, 8, -11
13 |   52 |       52 | 0, -1, 2, -5, 8, -11, 12
14 |    ? |       54 | 0, -1, 2, -5, 8
15 |    ? |       59 | 0, -1, 2, -5, 8
16 |    ? |       65 | 0, -1, 2, -5, 8, 15

```

You can see there is a pattern arising, but it's not consistent as you can see it changes when we get to certain values of $n$. To show how close of an approximation this gets, we can use the examples in Apass.Jack's answer:

```
  n | best | I filled | diagonals to use
----+------+----------+-----------------
 21 |  105 |       98 | 0, -1, 2, -5, 8, -15, 18
 31 |  186 |      171 | 0, -1, 2, -5, 8, -15, 20, -27, 30
 91 |  910 |      777 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76
133 | 1596 |     1335 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76, -100, 112

```

So it's clearly a lower bound. There also doesn't seem to be a known pattern in the diagonals other than the trivial pattern of "this is what I calculated under these constraints". What is interesting is if we only use non-negative diagonals then we get pattern A025582. However, I cannot find a pattern for positive and negative diagonals.
> 2 votes

# Answer
Exchanging rows and columns makes no difference. You need on average 8 items per row, so I'd try to find something with exactly 8 items per row. And any two rows must have at most one column in common.

So we put 8 items into the first eight columns of the first row. Row 2 has 1 item in column 1, and seven more in columns 9..15. Row 3 has 1 item in column 2, one in column 9, and six in columns 16..21. Similar for rows 4 to 8, showing that you need at least 36 columns (n ≥ 36).
> 0 votes

---
Tags: algorithms, constraint-satisfaction
---


# Question
Title: Self-balancing binary search tree optimized for insertion
I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable to least. The number of items is fixed. The current implementation can be seen at https://dfdx.us/core-values-quiz/.

What matters most is minimizing the number of comparisons the user needs to input, or, more accurately, minimizing the amount of *time* the user requires to make each comparison times the number of comparisons.

Currently I offer two sorting methods: Quicksort and insertion into a binary tree. Compared to a self-balancing BST, Quicksort will always require more comparisons, but because each consecutive comparison is against a single item (the partition item), the brain doesn't need to make much of a context switch and can answer the questions quicker. The binary search tree will present fewer questions that take longer. I let the user decide which method they want to use, given the pros and cons of each.

Since the comparisons required to rebalance the tree are handled by the computer, and not the user, those comparisons don't need to be optimized at all, only the number of comparisons required to determine the relative position within the current tree. I believe this optimization is equivalent to, between each item's insertion, balancing the tree as perfectly as possible. That is, requiring the strictest balancing constraint.

The best algorithm I've tested is the AVL tree. While the AVL tree is pretty terrible for insertion/deletion times for most applications, it has a decent balancing constraint which results in great look-up speeds. The rebalancing between each insertion/deletion is what makes it unperformant, but since, compared to human input, those comparisons are negligible, it is very good for my situation.

My situation requires one more constraint: the user must never be presented with the same comparison twice. For the AVL tree, rebalancing breaks this constraint, so I've just memoized all of the user's answers in a dictionary. I can't imagine a situation in which this case couldn't be handled with that memoziation, but I figured I'd mention it nonetheless.

I really have two questions:

1. Am I right with my assertion that balancing the tree as perfectly as possible guarantees the fewest number of prompts to the user?
2. Is there a better balancing algorithm than an AVL tree?

Given that before the quiz begins, the items' order is randomized, even using a non-auto-balancing BST should result in a roughly balanced tree. I could see an argument being made that *perfectly* rebalancing after every insertion could actually produce a greater number of prompts, since each one will have as close to lg(n) prompts as possible; a slightly less balanced tree could potentially have a few "lucky" insertions that require a few less than lg(n), and a few "unlucky" insertions that require more, but that the lucky ones will, on average, outweigh the unlucky ones. (I hope that made sense.)

# Answer
I realized, considering that memory and processing constraints are negligible in my situation, that it is trivial to produce a new, perfectly balanced tree from an in-order traversal of the unbalanced tree, where perfectly balanced means that the max depth of a leaf node is at most one more than the minimum depth of a leaf node.

For that matter, a tree isn't even necessary. Using a binary search over an ordered array to determine where to insert each new element is more efficient than using a binary search tree at all. Given that my input set is a fixed 58 items, using JavaScript's `Array.prototype.splice()` function is more than performant enough, and makes the code trivial, as well.
> 1 votes

---
Tags: sorting, binary-trees
---


# Question
Title: How to find optimal token set for compression?
By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like in LZ).

(Please feel free to correct me on this term, if I use it incorrectly.)

I'm thinking: what if we first find optimal set of tokens, and only then compress our data as a stream of these tokens? Will it improve compression of text or of xml or of some other kind of data? LZ sort of does this, but it is limited to letters. I'm asking about truly general approach when a token can have any bit-length. For example, it can be interesting to do it for compression of x86 executable files. Or in other cases, when sub-byte (and sup-byte) bit-strings behave as individual tokens.

How to find this set of tokens optimally? In a way that maximize average entropy of a stream of such tokens under 0-order Markov model?

Are there existing algorithms for it? Are there any algorithms related to the problem?

How to find approximation of this set? What is complexity of optimal and approximation solution?

And what if we want to maximize entropy for higher order Markov model? How harder the problem will be in this case?

# Answer
> 1 votes
> Are there existing algorithms for it? Are there any algorithms related to the problem?

---
Tags: data-compression, markov-chains
---


# Question
Title: Dana Angluin's L* algorithm - Hypothesis inconsistent
is it possible for the Dana Angluin's L\* algorithm that a hypothesis is inconsistent?

So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will get a counterexample w.

The Question is: Can the counterexample w be chosen in the hypothesis, so that I have two times the same counterexample?

Unfortunetaly I could not find any language and counterexample where it will work.

# Answer
I have no idea what it would mean for a hypothesis to be inconsistent in this context, but the answer to your second question is: No. You won't receive the same counterexample twice.

The teacher returns a counterexample $w$. Here a hypothesis is a DFA (a regular language) and $w$ is a word that the DFA gets wrong (either the DFA accepts, but $w$ is actually not in the language to be learned; or the DFA rejects, but $w$ is actually in the language to be learned). Angluin's L\* algorithm constructs a new DFA that is correct on all of the counterexamples that have been returned so far. Since this DFA is correct on all past counterexamples received from the teacher, we will definitely never get the same counterexample a second time.
> 1 votes

---
Tags: automata, finite-automata, learning-theory
---


# Question
Title: Could all CPU instructions get fundamentally faster if a better multiplication method was developed
I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019.

Could this discovery increase the throughput of future CPU's? If so could we determine by how much preemptively?

# Answer
I don't see the relevance.

* New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with numbers with thousands or even millions of bits. For an extreme example, Fürer's algorithm, which runs in time $O(n\log n\\, 2^{O(\log^\*n)})$ will only become competitive with Schönhage and Strassen's $O(n\log n\log\log n)$ algorithm for $n\>2^{64}$ bits and, let's be honest, whatever it is that you're multiplying, it doesn't have $2^{64}$ bits. In contrast, CPUs operate on fixed-length words with a few tens of bits.
* Most of what a CPU does isn't multiplying numbers, anyway.
* Also, note that Harvey and van der Hoeven "make no attempt to... exhibit a practical multiplication algorithm" (page 2 of their preprint).
> 6 votes

# Answer
No, it's not helping.

You can do n bit multiplication in O (log n) time, not O (n log n). The only problem is that you need an enormous amount of hardware to do this, growing as O (n^2), while this paper describes multiplication with a fixed amount of hardware.

But since a CPU typically just has only a 64 bit multiply unit, that O (n^2) space is no big deal, and the O (log n) is unbeatable. Even 256 bit would be doable, but there doesn't seem much need for it.
> 4 votes

---
Tags: algorithms, cpu, multiplication
---


# Question
Title: Proving NP hardness in Puzzle with SAT reduction
## Introduction

I have created an algorithm that generates *n^2 x n^2* Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on *circular matrix shift* of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1 and Here-2 and Grid generation and Grid generation written in Python

## SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

## SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

*shift(L) = the circular shifts*

> x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle
>
> x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle
>
> ¬x4 = valid grids and puzzles not following shift(L)
>
> ¬x3 = another valid grid and its puzzle not following shift(L)

## Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

## Question

Did I prove correctly that my puzzles are NP-hard assuming that the language used to generate these grids never have missing instances?

# Answer
> 3 votes
As far as I can tell, no, you have not proved NP-hardness of your puzzle. NP-hardness is precisely defined. If you want to prove a mathematical statement, you must do mathematical work and can't get there by only hope and intuition.

If you want to show that problem X is hard by a polynomial-time reduction from 3-SAT, you should proceed as follows. Take *any arbitrary* instance $I$ of 3-SAT and construct, in polynomial-time, an instance $I'$ of X. Once you've done this, prove that $I$ has a solution if and only if $I'$ has a solution. This is the "mathematical part", where you use the properties of $I$ and $I'$ to argue for both implications; you need some insight and practice in writing mathematical proofs, where in the argument the next step follows from the previous.

For example, contrary to what you seem to say, you can't show hardness by reducing one fixed instance of 3-SAT to your problem X.

If all this feels confusing but you are still excited, I recommend that you:

1. Read the relevant *definitions* of NP, NP-hardness and polynomial-time reductions. Think about what they mean intuitively as well.
2. Look at examples of reductions and NP-completeness proofs. Don't expect to get it straight away, but be willing to do some work. There are plenty of exercises out there and many questions on this site too.
3. Come back to your original problem later, perhaps after getting a little bit more familiar with writing proofs in general.

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


# Question
Title: Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?
Python quite famously uses indentation to *syntactically* define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very fond of this syntax feature.

But I wonder: Apart from Python and its "predecessor"(\*) language ABC **which other programming languages are out there using indentation for definition of code blocks**? *Code blocks* means here "multiple statements which in some way are treated as one component".

I'm particularly interested in *practical* programming languages, but *esoteric* languages might be worth mentioning as well.

---

(\*): "*Predecessor*" is my choice of word in default of knowing here a better one. Guido van Rossum, the creator of Python, described the relationship between Python and ABC regarding indentation in an interview like this: "*The choice of indentation for grouping was not a novel concept in Python; I inherited this from ABC.*"

# Answer
> 24 votes
Wikipedia has an extensive list of languages that use the off-side rule1:

> * ABC
> * Boo
> * BuddyScript
> * Cobra
> * CoffeeScript
> * Converge
> * Curry
> * Elixir (`, do:` blocks)
> * Elm
> * F# (if `#light "off"` is not specified)
> * Genie
> * Haskell (only for `where`, `let`, `do`, or `case ... of` clauses when braces are omitted)
> * Inform 7
> * ISWIM, the abstract language that introduced the rule
> * LiveScript
> * Miranda
> * Nemerle
> * Nim
> * occam
> * PROMAL
> * Python
> * Scheme, when using e.g. SRFI 119
> * Spin
> * XL

1: I've never heard this term before myself.

# Answer
> 10 votes
There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to language compilers with JavaScript as target and esoteric Whitespaces.

There is also Agda \- interactive theorem prover, which is probably not what you had in mind, but its lexer is very sensitive to white-space.
Makefile, which gathers targets with tab-based intends.

# Answer
> 4 votes
Make fits your description, even though it probably isn't quite what you have in mind, with its limited syntax and power.

It infamously indicates its code blocks (*recipes*) with a particular form of whitespace: one tab character. Alternative ways are available (e.g. GNU Make supports using an alternative character), but rarely used in practice.

Another example hovering at the edge is Ansible playbooks. They are specified in YAML, which is heavily indentation dependent. YAML is not a programming language, but Ansible playbooks can be regarded as domain-specific programs.

---
Tags: programming-languages, python, syntax
---


title: Why do computers keep old cache?

text:
# Question
Title: Why do computers keep old cache?
I cleaned up my computer and found 50GB of old cache on it and it made me wonder, why do computers keep old cache files?

# Answer
> 1 votes
The cached data might be needed again in the future and keeping it doesn't cause any particular performance problem, so you may as well keep it until you need the space for something else.

---
Tags: cache
---


# Question
Title: If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?
I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17:

> Prove that if P = NP, then every language in P, except $\emptyset$ and $\Sigma^\*$, is NP-Complete.

The solution is as follows:

> Let $A$ be any language in NP and let $B$ be another language not equal to $\emptyset$ or $\Sigma^\*$. Then there exist strings $x \in B$ and $y \notin B$. To reduce an instance $w$ of $A$ to that of $B$, we just check in polynomial time if $w \in A$. If yes, we output $x$ and $y$ when $w \notin A$.

But I don't see why this reduction could not be applied to **any language** (except $\emptyset$ and $\Sigma^\*$). It would not mean that the language is in P, but the reduction would be correct. The only point where I have doubts is the part where we say that $x$ and $y$ exist, do we somehow have to take into account some computing time for $x$ and $y$ ? Else the reduction would work even for unrecognizable languages for example.

# Answer
> 2 votes
**You are correct.** There is no other requirement to the language $B$ other than it is non-trivial (i.e., $x$ and $y$ with said requirements exist). This means that any language in $\mathbf{P}$ (or $\mathbf{NP}$, if you consider $\mathbf{P} = \mathbf{NP}$ as in the exercise's premise) is reducible to a non-trivial language.

**Why is this not surprising?** The key point here is that we are considering reducibility under *poly-time* many-one reductions. Since the reductions work in poly-time, they are outright powerful enough to *solve* the problem which they should be reducing (in your case, the language $A$). Hence, the entirety of the "work" is being done in the reduction itself rather than being transferred to the target which is reduced to (which is the intuitive notion of how a reduction works).

However, this is not in any way a phenomenon exclusively pertinent to $\mathbf{P}$ and poly-time (many-one) reductions. Notice that, for example, if you consider $A \in \mathbf{L}$ (i.e., $A$ is decidable in log-space) and *log-space* reductions, you will also obtain that $A$ is log-space reducible to any non-trivial language $B$ in the exact same way. In general, if $M$ is some (abstract) machine model which you use for your reductions, then any problems which can be directly decided by $M$ can be reduced to a non-trivial language. The upshot is that reductions are only useful when trying to relate problems which *cannot* (or you suspect they cannot) be solved directly by the machine model you are using for your reductions.

# Answer
> 3 votes
The reduction does indeed work for any non-trivial language $B$. And that's what the claim you've quoted says: "Let... $B$ be another language not equal to $\emptyset$ or $\Sigma^\*$", not "... another **NP** language..."

So, yes, it could be arbitrarily difficult to compute $x$ and $y$. It might even be impossible to compute them. But that doesn't affect the running time of the reduction because the reduction doesn't have to compute $x$ and $y$. Rather, the person who designs the reduction has to figure out those strings once. If you think in terms of computer programs, the reduction is a program that could be arbitrarily difficult to write but, once it's been written, it runs very quickly. In complexity theory, we don't care how difficult it is to write the program; we only care about how efficiently it runs. If the program *exists*, we're happy, and these programs certainly exist.

Note that it can still be possible to concretely and explictly write down the reduction, even if $B$ is uncomputable. For example, let $B$ be the language of descriptions of Turing machines that halt on every input. This is highly uncomputable: neither it nor its complement is recursively enumerable, for example, which means that there's no algorithm that can generate all the strings in $B$, or all the strings that are not in $B$. However, we don't need all the strings: we just need two strings. Let $M\_1$ be the Turing machine that immediately enters the halt state, regardless of its input, and let $M\_2$ be the Turing machine that moves its head to the right forever, regardless of its input. We have $\langle M\_1\rangle\in B$ and $\rangle M\_2\rangle\notin B$ so, if you cared to figure out the values of $\langle M\_1\rangle$ and $\langle M\_2\rangle$ as binary strings, you could explicitly write down the reduction from an polynomial-time language to $B$.

# Answer
> 1 votes
If $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is NP-hard, as your argument shows. However, that does not mean that every nontrivial language is NP-complete. For a language to be NP-complete, it needs to be *both* NP-hard *and* in NP. Your argument shows that if $\mathsf{P}=\mathsf{NP}$ then a language is NP-complete *if and only if* it is in P and non-trivial.

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


# Question
Title: Given matrix, count paths visiting each number exactly once
We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in the matrix.

We want to count paths that start in some cell, then moving in one of the four directions (up, down, left, right) visit all $21$ number exactly once.

It is impossible to move on cells marked as $-1$.

For example:

```
1,  2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1, 21
-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, -1, -1, -1, -1, -1, -1, 18, 19, 20
We can start in the upper-left cell, move right until 17 then down, right again, and up on the end.
The second path is the same as the first path but reversed (starting from 21).

```

My idea is to use dynamic programming with three states $i, j$, coordinates of the current point, and bitmask of the visited cells. However this is pretty slow for numbers up to 21. Is there any way to speed up this calculation.

Link from the task that appeared on the contest: mendo.club/Task.do?id=647

# Answer
> 1 votes
If I understand well, you are looking for an Hamiltonian path which is basically NP-complete. With your DP idea, there is $2^{21} = 2M$ possible bitmasks and there is no way to order them. So I am not sure to understand how it works.

In fact you can start building a graph and get rid of any direction/"-1 cells" consideration. In your example you would get a simple chain from 1 to 21.

Then, in the very general case you may have to explore all possible paths (using DFS for instance). But in this kind of problem you can look for some tricks. The point is to select the 20 edges of the path:

* Any vertex having only one edge is either start/end (**NB** a reversed valid path is valid like in your example) and its edge is selected
* A vertex having 2 edges have these edges selected (unless it is start or end)
* A vertex having 2 edges selected, have all the other edges removed.

# Answer
> 0 votes
You can use the bitmask of visited **numbers** instead of the bitmask of visited **cells**.

---
Tags: dynamic-programming, bit-manipulation
---


title: Show that CFG is not a LR(1) Grammar

text:
# Question
Title: Show that CFG is not a LR(1) Grammar
Let G b the following CFG (Where S is the start symbol):

```
S→aB|aDc
B→bBc|c
D→bc|c

```

(a) Show that G is ambiguous.
(b) Show that G is not an LR(1) grammar.
(c) Modify G into an equivalent grammar G′ that is LR(1). Explain why G′ is an LR(1) grammar and why G and G′ are equivalent.

**My current answers:**

(a) I showed that there exists two left derivation trees for string abcc - therefore it is ambiguous.

(b) I simply stated that an LR(1) grammar is not ambiguous by definition, and since (a) shows it is ambigious it follows that G is not an LR(1) grammar.

(c)
G':

```
S→aB
B→bBc|c

```

I removed the nonterminal D, which makes it unambiguous.

**Questions**:

Is there a more suiting answer for (b)?

How do I explain why G' is an LR(1) grammar in (c)?

Thank you!

# Answer
> 1 votes
Your answer to B is perfectly fine.

To show that something is LR(1) you should generate the automaton and show it has no conflicts.

Don't forget you have to show that G and G' generate the same language. Luckily this is simple because your removal of rules only involved a finite sub language thus you can exhaustively show equivalence.

---
Tags: formal-languages
---


# Question
Title: How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step
Consider the following matrix:

**Input:** The entire list of coordinates ranging from (0,0) to (4,4).

A list indicating certain coordinates which cannot be used to generate a path reached.

So,

* each position on the grid is a node
* nodes share an edge if exactly one coordinate differs by exactly 1
* X nodes (and their associated edges) are deleted

The problem then becomes, find the shortest path in the graph between two nodes. If the nodes are not in the same connected component, there is no such path.

**Output:** The shortest path between S and E, considering the positions of the X nodes, given by a sequence of coordinates.

So in the above picture, a possible route may be the following: (0,0)-\>(0,1)-\>(0,2)-\>(0,3)-\>(1,3)-\>(2,3)-\>(3,3)-\>(4,3)-\>(4,4)

A total of eight steps.

If the Xs occur in a way that prevents any movement (i.e, Xs at (0,1),(1,1), and (1,0), it should return -1 or indicate in some other way no path is possible.)

I have received advice that the A\* search algorithm (pseudocode in this link) is relevant to this problem, but I am having difficulty seeing how to apply it.

# Answer
You're asking how to compute the shortest path between two vertices in a graph. Solution: use an algorithm for computing shortest paths. In your case, BFS would be a good choice. There's no need for A\*.
> 2 votes

---
Tags: graphs, search-algorithms, network-analysis
---


title: P vs NP question from GeeksforGeeks

text:
# Question
Title: P vs NP question from GeeksforGeeks
From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (GATE CS 2006)

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

The answer they give is B and I can see that. But I'm curious as to what is Q then? If it's not in NP and if it's not in NP hard, is there some other set that I don't know about it belongs to?

# Answer
> 1 votes
In fact, $Q$ is in NP (since you can reduce it to $S$ in poly-time and $S$ is in NP). It's just not necessarily NP-complete or NP-hard.

For example, let's let $Q$ be the following decision problem:

> Given a number $n$, is $n$ prime?

This problem is known to be in $P$. But I can reduce it to something NP-complete, like *HamiltonianPath*:

> First, determine whether $n$ is prime (in poly-time).
>
> If it's prime, let $G$ be a graph with two vertices and one edge between them.
>
> If it's not prime, let $G$ be a graph with two vertices and no edges.
>
> Now, pass $G$ to *HamiltonianPath*, which will give you your answer.

In this case, $Q$ can be reduced to the NP-complete *HamiltonianPath*, but it clearly isn't NP-hard or NP-complete (since it can be solved in poly-time).

---
Tags: np-complete, np-hard, np, p-vs-np
---


# Question
Title: Can the sorting of a list be verified without comparing neighbors?
A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare *every* item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $e\_i$, I have a set of pairs of indices $(j,k)$ for which I know whether $e\_j \> e\_k$, $e\_j = e\_k$, or $e\_j \< e\_k$. There exists a pair $(l,l+1)$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?

# Answer
> 35 votes
It is impossible. Suppose that you have the result of *all* comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases: $$ 1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\ 1,2,\ldots,i-1,i+1,i,i+2,\ldots,n $$

---
Tags: sorting
---


title: Non consant size alphabet

text:
# Question
Title: Non consant size alphabet
Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.

# Answer
The classical example is *sorting*. For any constant-size alphabet, you can sort a string of length $n$ in time $O(n)$. However, for unbounded alphabets, the best you can do (under the comparison model, as well as some of its generalizations) is $\Theta(n\log n)$.
> 2 votes

---
Tags: algorithms, strings
---


# Question
Title: Optimization of Church-encoded booleans in System F
I can encode booleans in pure lambda calculus like this:

```
type Bool = forall t. t -> t -> t
true : Bool = \x y -> x
false : Bool = \x y -> y

```

Is there a procedure to optimize the following "dumb" function

```
dumb = \(b : Bool) -> b false false

```

to

```
dumb = \(b : Bool) -> false

```

I can imagine this is quite easy in Haskell with an ADT for example.

One way I can think of is counting the inhabitants of the type Bool (2) and then applying the function to both the inhabitants, discovering that the function will have the same result for any argument. This seems quite difficult to do in general though.

# Answer
> 4 votes
Without further assumptions you cannot perform the optimization because it is unsound in general. For example, we could interpret System F in a model that has fixed point operators, in which case there will be elements of `Bool` that are different from `false` and `true` (namely "undefined" ). In such a model, `dumb` will not be equal to `\ b . false` because `dumb ⊥ = ⊥` but `(\b . false) ⊥ = false`.

In your question you assumed that we know what it means to "optimize" a function. If we leave aside questions about efficiency, we still have to answer the question what it means for two closed terms in System F to be equal. There are several possibilities:

* closed terms $M$ and $N$ are equal if they reduce to the same normal form,
* closed terms $M$ and $N$ are equal if they are equal in some preferred model,
* closed terms $M$ and $N$ are equal if they are observationally equivalent,
* closed terms $M$ and $N$ are equal if they are extensionally equivalent (they give extensionally equivalent results when applied to extensionally equivalent arguments).

Parametricity, which was mentioned in the comments, may be helpful with some of the above. But it's difficult to discuss "optimization" until we know what counts as "equal", or else we cannot tell which optimizations are valid.

---
Tags: lambda-calculus
---


# Question
Title: Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma
I have the following alphabet: $Σ = {0, 1, . . . , 9}$

and the Language $L$ defined as: $L = \\{ abc | a + b = c\\} $

where substrings $a$, $b$ and $c$ are interpreted as ordinary integers.

**My answer so far**:

Assume $L$ is context-free. Then the pumping lemma for context-free languages applies to $L$.

Let $n$ be the the constant given by the pumping lemma.

Let $z=10^n20^n30^n$ clearly $z \in L$ and $|z| \geq n$

By the lemma we know that $z = uvwxy$ with $|vwx| \leq n$ and $ |vx| \geq 1$

There exists possibilities...

**My questions:**

I can see 8 possibilities where $vwx$ can be within $z$. For example in the beginning including the 1 and overlapping with the initial $0^n$. Another example the initial $0^n$. Is this one way to think in this particular question? How can I pump and show that the result does not belong to $L$?

**Thank you for your time.**

# Answer
> 3 votes
Suppose that $L$ were context-free. Then $L \cap 10^\*20^\*30^\*$ would also be context-free. What is this language? It is easy to see that each of $a,b,c$ needs to contain a non-zero digit. Therefore $a = 10^i$, $b = 0^j20^k$, and $c=0^\ell30^m$. Clearly $i=k=m$, and so $$L \cap 10^\*20^\*30^\* = \\{10^{i+j}20^{i+\ell}30^i : i,j,\ell \geq 0\\} = \\{10^i20^j30^k : i,j \geq k\\}.$$

To make our life easier, let us consider instances with more structure: $L \cap 30^\*130^\*160^\*2$. Consider any word $30^i130^j160^k2$. The only way in which $a+b$ ends with $2$ is if $a,b$ end with $1$, and so $a=30^i1$, $b=30^j1$, $c=60^j2$. This shows that $$ L' \triangleq L \cap 30^\*1 30^\*1 60^\*2 = \\{ 30^i130^i160^i2 : i \geq 0\\}. $$ If $L$ were context-free, so would $L'$ be. Now define a homomorphism $h$ which maps $1,2,3,6$ to themselves and $a,b,c$ to $0$. Clearly $$ L'' \triangleq h^{-1}(L') \cap 3a^\*13b^\*16c^\*2 = \\{3a^i13b^i16c^i2 : i \geq 0\\}. $$ If $L'$ were context-free so would $L''$ be. Finally, define a homomorphism $k$ which erases $1,2,3,6$ and fixes $a,b,c$. Then the following language would also be context-free: $$ k(L'') = \\{ a^i b^i c^i : i \geq 0 \\}. $$ However, this language is well-known to be non-context-free.

---

If for some reason you want to prove that $L$ is not context-free using the pumping lemma (the only reason I can see is that you were given this as an exercise), then you could consider instances of the form $30^n130^n160^n2$, which might be easier to handle than your original suggestion.

# Answer
> 3 votes
### Outline of a solution

Assume for the sake of contradiction, $L$ is context-free. Since $1^\*2^\*33^\*$ is regular, $M=L\cap 1^\*2^\*33^\*$ is context-free. Assuming the pumping length of $M$ is $p$, We can show that $M$ does not satisfy the pumping lemma by inspecting $1^p2^p3^p$. This contradiction shows that $M$ is not context-free.

### What is $M$?

**Claim.** $M= \\{ 1^i 2^{i+2d} 3^i : i\ge1, d\ge0 \\}$
**Proof:** Let $1^i2^j3^k=abc\in M$, where $k\ge1$ and $a+b=c$ as ordinary numbers.
The sum of the last digit of $a$ and the last digit of $b$ is the last digit of c, 3. So the last digit of $b$ must be 2. $$\begin{aligned} & &\phantom{22\cdots2}11\cdots1 &\quad(a)\\ &+&22\cdots222\cdots2 &\quad(b)\\\hline & &22\cdots233\cdots3 &\quad(c) \end{aligned}$$ Each 3 in $c$ must be the sum of a digit of $a$ and a digit of $b$, one of which must be 1 and the other must be 2. So $a$ must be contain all $i$ 1's and no 2. The number of 1s, $i$ must be the same as the number of 3s, $k$.

### $M$ is not pumpable as in the pumping lemma

Let $p$ be the pumping length of $M$. Consider $1^p2^p3^p=uvwxy$, where $|vwx|\le p$, and $|vx|\ge1$.

* Suppose there is a 2 in $vx$. Since $|vwx|\le p$, $vx$ cannot have both 1 and 3.
    + There is no 1 in $vx$. There are more 1s than 2s in $uxw=uv^0wx^0y$.
    + There is no 3 in $vx$. There are more 3s than 2s in $uxw=uv^0wx^0y$.
* Suppose there is no 2 in $vx$.
    + There is a 1 in $vx$. There are more 1s than 2s in $uv^2wx^2y$
    + There is a 3 in $vx$. There are more 3s than 2s in $uv^2wx^2y$

So in all cases, we can pump $1^p2^p3^p$ into a word that is not in $M$.

### Exercises

**Exercise 1.** Try pumping $1^p2^p3^p$ directly to outside of $L$ (instead of $M$).

**Exercise 2.** Let $\Sigma=\\{0,1,2,3,4,5,6,7,8,9\\}$ and language $\text{SUM} = \\{ abc\in\Sigma^\* \mid a + c = b\\} $ where substrings $a$, $b$ and $c$ in the equality are interpreted as ordinary integers. Show that $\text{SUM}$ is not context free.

**Exercise 3.** Let $\Sigma=\\{0,1,2,3,4,5,6,7,8,9\\}$ and language $\text{DOUBLE} = \\{ abc\in\Sigma^\* \mid 2 \times a = b\\} $ where substrings $a$ and $b$ in the equality are interpreted as ordinary integers. Show that $\text{DOUBLE}$ is not context free.

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


title: NP hardness of unique Puzzle Generation

text:
# Question
Title: NP hardness of unique Puzzle Generation
## Introduction

For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on *circular matrix shift* of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1, Here-2, Here-3 and algorithm in python

## Decision Problem

*Before reading make sure the links are read first.*

Given an *n^2 x n^2* grid **G** does there exist a mapping of a puzzle that will allow only one solution?

Here I test to see if my problem is in NP

*g = grid*

*p = mapped puzzle*

The certificate (g, p) is accepted by the checker

```
run backtracker....

print "analyzing puzzle to check possible solutions"

       if p == one solution

       print "valid shift-L puzzle"
else:
       print "false"

```

## Proof that Puzzle completion is NP-Complete

It is already proven by *Colborn* with a reduction from a NP-complete problem known as *Triangle Partition of tripartite graphs*. Explained here

## Question

With a pre-existing proof that latin square completion is NP-complete, is it safe for me to firmly say my puzzle generation (or puzzles) is at least NP-hard?

# Answer
Your problem is in NP.
Generalized Sudoku is NP-Complete, but your mapper is in P. Check whether given grid is generated by mapper runs in $\mathcal O(n^2)$ time.
Your mapper is not NP-Complete and your decision problem is not NP-hard.

On the other hand decision version of Sudoku is NP-hard.

The main problem is that you have not provided anything about checking uniqeness of solution, but since your mapper resolves only one solution from family of solutions it can't decide it.

If you insist on proving NP-hardness please provide valid reduction (hint, it will not run in polytime, so answer is no).
> 3 votes

---
Tags: np-complete, np, decision-problem
---


# Question
Title: Calculating all products of $n-1$ factors when given $n$ factors
Let's assume we have an operator $$ \times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$.

We're now given $n$ elements $e\_1,...,e\_n\in E$, and are tasked to calculate all $n$ products $$\def\bigtimes{\mathop{\vcenter{\huge\times}}} p\_j :=\bigtimes\_{i=1\\i\neq j}^n e\_i$$

Naively multiplying out all $n$ products takes $O(n^2M)$.

A more sophisticated approach that runs in $O(n^{3/2}M)$ splits $\bigtimes\_{i=1}^n e\_i$ at arbitrary positions into $\sqrt n$ factors.
For each of the $n$ products, we now only have to recalculate one factor, and multiply the resulting factor, and the other $k-1$ factors together.

What is the fastest algorithm for this problem, and how does it look like?

# Answer
Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below.

---

Input: $e\_1,\cdots,e\_n\in E$, where $n\ge 3$.
Output: $p\_1, \cdots, p\_n$, where $p\_j=e\_1\cdots e\_{j-1}e\_{j+1}\cdots e\_n$, the product of all input elements except $e\_j$.
Procedure:

1. Allocate array $p\_1, p\_2,\cdots, p\_n$ of $n$ element in $E$.
2. Let $s=e\_1$, $p\_1=1$
3. For $i$ from 2 to $n-1$ inclusive, let $p\_i = s$ and $s= se\_i$.
4. Let $p\_n=s.$

Now $$ \begin{pmatrix} p\_1\\p\_2\\ p\_3\\p\_4\\\cdots\\ p\_{n-1}\\ p\_n \end{pmatrix} \text{is} \begin{pmatrix} 1\\e\_1\\e\_1e\_2\\ e\_1e\_2e\_3\\\cdots\\ e\_1e\_2\cdots e\_{n-2}\\e\_1e\_2\cdots e\_{n-2}e\_{n-1} \end{pmatrix} $$.
5. Let $b=e\_n$.
6. For $i$ from $n-1$ to 2 inclusive downwards, let $p\_i=p\_ib$ and $b = e\_ib$.
7. Let $p\_1=b$.

---

The number of multiplications performed by the algorithm above is $3(n-2)$.

I believe that is the tight lower bound. However, I have not been successful proving it even though I have tried a few times. I am still trying from time to time.
> 7 votes

---
Tags: dynamic-programming, efficiency
---


# Question
Title: How to prove a bound function for a sequence of numbers?
Let $G\_n$ be defined by

$$G\_n = \begin{cases} 1 & n=0 \\ 2 & n = 1 \\ 3 & n = 2 \\ 4 & n = 3 \\ 2G\_{n-1}-2G\_{n-3}+G\_{n-4} & n\geq4 \end{cases}$$

How can I prove that $f(n) = n$ is a bound function (or loop variant) for the above sequence?

# Answer
If you have tried, you will find that $$\begin{aligned} G\_5&=6\\ G\_6&=7\\ G\_7&=8\\ G\_8&=9\\ G\_9&=10.\\ \end{aligned}$$

By now, you should have probably guessed that $G\_{n}=n+1$. Now you can try proving it, using induction on $n$.

Once that formula has been proved, $f(n)=n$ is of course a lower bound for $G\_n$.
> 2 votes

---
Tags: recurrence-relation, loop-invariants
---


# Question
Title: What is the time complexity of the following algorithm on graphs
Consider undirected graph with $O(n)$ nodes and $O(m)$ edges. We store the edges in adjacent list, so for each node we keep list of the nodes such there exist edge between those nodes.

Our search goes as follows: For each node in the graph (let it be i) we iterate over all pairs of nodes(let it be $n\_1 \text{ and } n\_2$) such that there is edge between $i \text{ and } n\_1 \text{ and between } i \text{ and } n\_2$.Let's just analyze the complexity of those iterations.

Here is the pseudo code to make sure everything is understood well

```
for each node i in graph G:
    for each node n1 in adjacent list of i:
        for each node n2 in adjacent list of i:
            O(1) work here

```

From first look it looks like $O(n^3)$ since there are three nested loops, however I don't think that this is correct. What is the correct way to analyze the time complexity here?

# Answer
For every $v$, there are $\binom{n-1}{2}$ pairs in the worst case that need to be checked, since $v$ may be connected up to $n-1$ other vertices.

Since $\binom{n-1}{2} = \Theta(n^2)$, your algorithm performs $O(n^2)$ queries for every vertex. Since there are $n$ vertices, the time complexity is $O(n^3)$ and your analysis is correct.

---

Suppose we want to express the algorithm cost in terms of $m$.

For every $v\_i$, we perform work equal to the number of neighbours over 2 of $v$, denoted by $N\_i$. Or $\binom{N\_i}{2}$

It is clear that the runtime would be $O(N\_1(N\_1-1) + N\_2(N\_2-1) +\dots +N\_n(N\_n-1))$ $$ = O(\sum\_{i=1}^n (N\_i)(N\_i-1)$$

We know that $\sum\_{i=1}^n (N\_i) = 2m$, since every arc is counted exactly twice. What is left is to prove $$\sum\_{i=1}^n (N\_i)(N\_i-1) = O(nm)$$

Since $N\_i \leq n-1$ it follows: $$\sum\_{i=1}^n (N\_i)(N\_i-1) \leq \sum\_{i=1}^n (N\_i)\*n = n\sum\_{i=1}^n (N\_i) = n\*2m=O(nm)$$
> 3 votes

---
Tags: time-complexity
---