# Question
Title: Algorithm to find exactly two sets of numbers that have the same sum
I am searching for the most efficent implementation of a specific algorithm:

Assume you have a set of positive integers, for example:

X = \[1,1,2,3,3,6,8\]

The aim is to find exactly two sets (containing together all elements of X), so that the sum of all elements of the one is equal to the sum of the other.

So for example a solution would be (there can be more than one solution of course, or no solution): A = \[1,2,3,6\] B = \[1,3,8\]

(Sorry if my wording is wrong, just a curious developer and no computer scientist)

# Answer
This is called the Partition Problem, and it's NP-complete, meaning that it's very unlikely that any algorithm can solve every instance of the problem quickly. On the bright side, if there are $n$ numbers and their total sum is $t$, there is a fairly simple $O(nt)$-time dynamic programming algorithm (see section "Pseudo-polynomial time algorithm" on that webpage), and this is fast enough to solve many practical instances.
> 5 votes

---
Tags: algorithms
---


# Question
Title: Fitting different rectangles inside a rectangle
I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes.

I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate any one of them by 90°.

Any great algorithm to do this ?

I know that some packing algorithm exists and several threads discuss it but it's not exact and it does not support rectangle rotation, therefore I cannot apply it to find a minimum rectangle and compare it afterwards to the given X x Y rectangle.

# Answer
> 4 votes
As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions.

A lot approaches ignore rotation, but can be expanded fairly easily to support it. As you seem to be aware of approaches without rotation, I'll focus on the rotating part.

A good resource is 'One thousand ways to pack the bin', by Jukka Jylänki. It covers many heuristic algorithms, and considers rotation part of the problem. Most of the rest of this post summarizes this paper.

While rotation makes the problem a lot harder to solve *exactly*, it doesn't make most heuristic methods much more complicated, as they cannot afford to make complicated choices and so choose heuristically how to rotate.

## Shelf heuristic

For the shelf algorithms, rotation is quite simple:

1. If the current rectangle starts a new shelf, we rotate such that the shelf height is minimal.
2. Otherwise, rotate such that the width is minimal while still fitting the shelf (if it fits at all)

Point 2 is actually the best way to rotate given that the rectangle will be packed in the current shelf while for point 1 one could argue to do the opposite and this could indeed be better in some cases. (such as the case that all remaining rectangles are squares with length equal to the long side of the first rectangle of the shelf)

## Guillotine heuristic

For the guillotine algorithm, the choice for rotation isn't so clear (perhaps a reason why Jylänki leaves this open), but one reasonable method is to try both orientations to decide whether a rectangle 'fits'. If both fit, one could try to pick the one that matches the split rule (for example, choose the rotation that minimizes the area of the chosen free rectangle when using the Best Area Fit variant)

## Other heuristics

For the Maximal rectangle algorithm and the Skyline heuristic, supporting rotation here is similar to the Guillotine case, there aren't really any particular choices other than trying to fit with both orientations and pick the one which makes more 'sense' with respect to the rest of the specific heuristic.

There are more algorithms, but I think this gives a good overview of the ideas of how to support rotation. As you might have noticed, these methods aren't too fancy, that is sometimes the best you're going to get.

---
Tags: algorithms, optimization, packing
---


title: Proving that $xy=yx$ iff $x^2y^2=z^2$

text:
# Question
Title: Proving that $xy=yx$ iff $x^2y^2=z^2$
I was given the following problem as homework:

> Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word $z$ such that $x^2y^2 = z^2$.

I was hinted that I am supposed to approach this problem using structural induction. Considering the case where $|x| = |y|$, you obviously get $x=y=z$, as commutativity of concatenation satisfies only under that case.

Taking the case of $|x| \< |y|$, we can conclude that $x$ is a prefix of $y$, assuming the induction hypothesis ($xy=yx$), and we can further say that $y=xt$, where $t$ can be assumed to be the trailing symbols of $y$ after the prefix $x$, and hence using $xy=yx$, we get $xxt = xtx$. And I'm stuck here. Can somebody guide me?

# Answer
> 3 votes
One direction is easy: if $xy = yx$ then $x^2y^2 = xxyy = xyxy = (xy)^2$.

In the other direction, we split into cases. If $|x|=|y|$ then, as you mention, $x = y$.

If $|x|\<|y|$ then let $y=y\_1y\_2$, where $|y\_1|=|y|-|x|$ and $|y\_2|=|x|$. We have $z = x^2y\_1$ and $z = y\_2y = y\_2y\_1y\_2$. Since $|x| = |y\_2|$, it follows that $x = y\_2$. Substituting this, we obtain $y\_2^2 y\_1 = y\_2y\_1y\_2$, and so $y\_2y\_1 = y\_1y\_2$. This implies that $xy = y\_2y\_1y\_2 = y\_1y\_2y\_2 = yx$.

If $|y| \< |x|$, then notice that $(y^R)^2(x^R)^2 = (z^R)^2$ (where $w^R$ is the reverse of $w$) and $|y^R| \< |x^R|$, so we can apply the previous case to deduce that $y^R x^R = x^R y^R$ and so $xy = yx$.

---

Let us use this opportunity to characterize when $xy=yx$, by proving that there exist a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$ iff $x^2y^2$ is a square.

One direction is easy: if $x = w^n$ and $y = w^m$ then $x^2y^2 = w^{2n+2m} = (w^{n+m})^2$.

In the other direction, we use induction on $|x|+|y|$. The base case $x=y=\epsilon$ is trivial. For the inductive case, we split into cases. If $|x| = |y|$ then $x = y$ and so we can take $w = x = y$.

If $|x| \< |y|$ then as before we get that $y = y\_1 x = x y\_1$, which implies that $y\_1^2 x^2 = (y\_1 x)^2$. The inductive hypothesis shows that there exist $w,n,m$ such that $y\_1 = w^n$ and $x = w^m$. Then $y = y\_1 x = w^{n+m}$.

---

We have shown that $xy = yx$ iff there exists a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$.

Equivalently, let us define the radical $\sqrt{x}$ of a word $x$ as the shortest word such that $x$ is a power of $\sqrt{x}$. Then $xy = yx$ iff $\sqrt{x} = \sqrt{y}$.

Indeed, if $\sqrt{x} = \sqrt{y}$ then clearly $xy = yx$. Conversely, suppose that $xy = yx$. Then there exist $w,n,m$ such that $x = w^n$ and $y = w^m$. We can assume that $w = \sqrt{w}$. I claim that $\sqrt{x} = w$. Otherwise, there exists a word $z$ shorter than $w$ and an integer $\ell$ such that $x = z^\ell$. The word $x$ thus has both $|w|$ and $|z|$ as periods ($p$ is a period of $x$ if $x\_i = x\_{i+p \bmod |x|}$ for all $i$), and so $|w| \bmod |z|$ is also a period. If $|w| \bmod |z| \neq 0$ then this contradicts the fact that $z$ is the radical of $x$ (since $x$ is a power of $x\_1 \ldots x\_{|w| \bmod |z|}$). If $|z|$ divides $|w|$ then $w = z^{|w|/|z|}$, contradicting the assumption $w = \sqrt{w}$. We reach a contradiction either way, and so $\sqrt{x} = w$. By the same reasoning, $\sqrt{y} = w$, and so $\sqrt{x} = \sqrt{y}$.

# Answer
> 2 votes
From $xy = yx$, we can say $x^2y^2 = x (xy) y = x (yx) y = (xy)^2$, Hence $z = xy$. Hence, first part is proved.

Now, suppose there exists a word $z$ such that $x^2 y^2 = z^2$. Moreover, suppose $|x| \< |y|$ w.l.o.g. Hence there is a $w$ such that $x^2w = w'y$, $ww'=y$, $|w| = |y|-|x|$, and $|w'| = |x|$. As $x^2w = w'y$ and $|w'|=|x|$, we can say $w' = x$. Hence, $x^2w = x xw = xy$. Therefore, $xw = y$. Also, $y = ww'$ and we know that $w' = x$, so $y = wx$.

From the above argument $xy = x(xw)$ and $yx = (xw) x = x(wx) = x (xw) = xy$. Here, the proof is completed.

---
Tags: word-combinatorics
---


# Question
Title: Can someone give a generic definition of any Definite Language in set builder notation?
What I have come across as a definition is - a language $L ⊆ Σ^\*$ is said to be definite if and only if $L = E ∪ Σ^\*Η$, for some finite languages $E,H ⊆ Σ^\*$

Using these questions - Show that every definite language is accepted by a finite automaton

and What are definite languages? How do you formally define them?,

I understand that a definite language is a language where the membership of a string depends on it's last k-symbols only, i.e, those strings sharing the last k-symbols either belong to the language or don't. On these lines, I don't understand how the definition correspond to - $L = E ∪ Σ^\*Η$, for some finite languages $E,H ⊆ Σ^\*$.

Having an intuitive idea, I am not quite able to get my head around a generic definition of a definite language in **Set Builder Form**. Could you please give a definition in **Set Builder Notation** specifically? I also request you to explain why you have defined it in such a manner, as I don't want to be in a situation where I couldn't understand the prior definition being $L = E ∪ Σ^\*Η$. I have been going at this for an entire week, now.

# Answer
> 2 votes
In set-builder notation, it's just $E\cup \\{vw\mid v\in\Sigma^\*\text{ and }w\in H\\}$.

So, why is this the same thing as "Languages that can be recognized by the last $k$ characters of the string"

One direction is fairly simple. If $L$ can be recognized by looking at the last $k$ characters, then there must be some set $H$ of length-$k$ strings such that, if the last $k$ characters form a string in $H$, you accept the string, and if they form a string not in $H$, you reject. Furthermore, there may be some strings that you accept even though they have fewer than $k$ characters: this set is $E$.

The other direction is a little more complex. Suppose that $L = E\cup\Sigma^\*H$ for some finite $E$ and $H$. We need to show that there is some $k$ and sets $X\subseteq\Sigma^{\<k}$ and $Y\subseteq \Sigma^k$ such that $L=X \cup\Sigma^\*Y$. Note that this is different from the hypothesis that $L=E\cup\Sigma^\*H$ because it's more specific: $E$ and $H$ can be any finite sets of strings, whereas $X$ contains only strings of length less than $k$ and $Y$ contains only strings of length exactly $k$.

The solution is to take $k$ to be whichever is the larger of:

* the length of the longest string in $H$;
* one plus the length of the longest string in $E$.

(Since both $E$ and $H$ are finite, each has a longest string, or several longest strings of the same length.)

We start by taking $X=E$, which we're allowed to do because every string in $E$ has length strictly less than $k$. Now, consider some string $h=h\_1\dots h\_\ell\in H$. We have $\ell\leq k$ by the choice of $k$. If $\ell=k$, we're happy: just add $h$ to $Y$. Now suppose that $\ell\<k$. If a string ends with $h$, then either it has length less than $k$ or it has length at least $k$ and its last $k$ characters are $a\_1\dots a\_{k-\ell}h\_1\dots h\_\ell$ for some $a\_1, \dots, a\_{k-\ell}\in\Sigma$. Therefore, we add to $X$ all strings of length less than $k$ that end with $h$, and we add to $Y$ all strings of length exactly $k$ that end with $h$. And we repeat this for every $h\in H$.

I've explained how to construct $X$ and $Y$. I won't write out their formal definitions as sets because those definitions are so full of notation that they're not enlightening.

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


# Question
Title: Find the minimum set of intervals for given set of numbers
For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\\}$$ the answer is $${\\{\[1.5,2.5\],\[2.8,3.8\]\\}}$$

On the example above $\[1.5,2.5\]$ is an interval with length $1$ ($2.5-1.5=1$). And there are 2 sets of intervals ($\[1.5,2.5\]$ and $\[2.8,3.8\]$).

I need to find the most efficient greedy algorithm for this problem with $O(n\log n)$ time complexity.

My thought is to sort the elements in ascending order (using merge sort for minimum time complexity) and then, starting from the first element, use the current element as the lowest limit, and (element+1) as the highest limit.

This has a running time of $O(n\log n + n)$. $n\log n$ from mergesort and $n$ for running through the elements to decide the intervals.

But I can't tell whether this is the most efficient greedy algorithm I can use for this problem.

# Answer
To show that the problem has a lower bound of $\Omega (n\log n)$, you can reduce the Element distinctness problem to your problem.
> 1 votes

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


# Question
Title: Among $k$ unit vectors, find odd set with sum length less than 1
I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v\_1, \dots v\_{2n+1}$ such that $\sum\_{i\< j} v\_i\cdot v\_j \< -n$ for any $n$ -- or determine that no such set exists?

As some motivation, if I have 3 vectors (so that $n=1$), the minimum value of their pairwise dot products if $-3/2$, given by them forming the corners of a triangle. This places all 3 vectors in the same two-dimensional plane. Anything out of that plane (so, more than 2 dimensions) will raise the minimum to some sum $\>-3/2$. If I go to a fewer number of dimensions by constraining all the vectors to 1D, then my only possible sums are -1 or 3.

In general, if I have $2n+1$ vectors, then by putting them at corners of a $2n$-simplex, you get a sum of dot products of $-(2n+1)/2$. But by putting them in 1D, you get a minimum of $-n$. I'd like to find sets of vectors that "don't look very 1D" in the sense that they violate this bound.

This is equivalent to the question, "Find an odd-size set of vectors such that their sum has length less than 1" -- the equivalence can be shown by taking the norm of the sum. I think this is more natural, so I'll change the question title.

# Answer
I have now learned that this problem is co-NP-complete. The question can be reduced to testing whether a point in $R^{n^2}$ (given by the Gram matrix generated by the vectors) satisfies all the pure $(2k+1)$-gonal hypermetric inequalities. This fact is stated (without proof?) on Page 454 of "Geometry Cuts and Metrics" by Michel Deza and Monique Laurent, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.215.1108&rep=rep1&type=pdf .
> 2 votes

# Answer
The latter problem feels similar to the Shortest Vector Problem (SVP) in integer lattices.

The Shortest Vector Problem is:

Input: vectors $v\_1,\dots,v\_k$
Goal: find a non-empty subset of vectors whose sum has length as short as possible

Your problem is:

Input: vectors $v\_1,\dots,v\_k$
Goal: find a non-empty subset of vectors whose sum has length $\le 1$, such that the number of vectors in the subset is odd

If we omit the "odd-size" constraint for the moment, the two are very similar: one asks for the sum to be as small as possible, the other asks for the sum to be $\le 1$. Thus, any algorithm for SVP would immediately yield an algorithm for your problem (ignoring the odd-size constraint). And solving your problem sounds like it might be about as hard as the SVP (if we replace $\le 1$ with $\le t$ where $t$ is an additional input, your problem becomes as hard as the SVP; reduction by binary search on $t$).

Unfortunately, the SVP is hard: roughly speaking, it's hard if $P \ne NP$ (this isn't quite right, but it's close). This makes me think that your problem might be hard, too.

That said, there *are* approximation algorithms for the SVP. You can use LLL lattice reduction to find a subset whose sum is not *too* much larger than the shortest possible. Unfortunately the gap between "the true minimum" and "what LLL finds" is pretty large, so this might not be good enough in practice. But it is something you could try and see if you get lucky.

I'm not sure how to accommodate the extra restriction that the subset be of odd size. You could try solving with LLL reduction and hope the resulting subset has odd size (50% chance). I can't think of a better technique, unfortunately.
> 2 votes

---
Tags: optimization, linear-algebra, search-problem
---


# Question
Title: Explain Hashed page tables in operating system
I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to:

I understand that p is hashed and then the hash is checked in the page table for a match. What is elements referring to here? Is it the page table entry? What does chain mean and where is virtual page number located?

Can someobody help me understand the flow chart? Thanks

# Answer
# Definitions (What's with the symbols?)

In the diagram, we have these guys:

* Virtual Page Number (VPN): `p`, `q`
* Page Frame Number (PFN): `r`
* Offset: `d`
* Hash Function: `h(x)`
* Hashed Page Table with schema `(key, VPN, PFN, Pointer to next entry with key)` for each entry in the table

It so happens that `h(p) = same_key` and `h(q) = same_key`. There is hash collision. Both `p` and `q` are hashed to the `same_key`.

This is resolved by chaining the entry with `VPN = q` to the entry with `VPN = p`. Chaining means to use the `Pointer` field in the entry with `VPN = q` to **point** to the entry with `VPN = p`.

# Workflow (How the system works)

Operating system (OS) grabs `p` from the CPU, and performs `h(p)` to get `same_key`.

OS looks up the first entry in the Hashed Page Table with `key = same_key` and checks `p` against the first entry's `VPN` field. It checks `p` against `q`. This is incorrect.

OS uses the `Pointer` in the first entry to find the second entry. It knows that the second entry has the same `key = same_key`, because the Page Table is constructed this way. OS checks `p` against the seond entry's `VPN` field. It checks `p` against `p`. This is correct. Bam. Kill confirmed.

OS knows that this is the correct entry it is looking for. It grabs `PFN` from the second entry. It grabs `r`. `r` is the correct physical frame number that corresponds to virtual page number `p`.

OS uses `r` to look for the physical frame it wants in physical memory, and looks for the exact word wanted which is offset by `d` within frame `r` in physical memory. OS grabs the contents of the word and we're done.

### Source: Dave Johnson's COMP 421 (Rice University CS Dept)
> 2 votes

---
Tags: operating-systems, hash, hash-tables, virtual-memory, paging
---


title: Semidecidability and NP-Hard

text:
# Question
Title: Semidecidability and NP-Hard
Im studying the semidecidability of First Order logic.

According to wiki

> A logical system is semidecidable if there is an effective method for generating theorems (and only theorems) such that every theorem will eventually be generated. This is different from decidability because in a semidecidable system there may be no effective procedure for checking that a formula is not a theorem

The semidecidability seems to me exactly equal to halting problem, which is NP-HARD. 1) Is it correct ? 2) So also First Order Logic is NP-HARD ?

# Answer
A language $L$ is *semidecidable* if there is a Turing machine that on input $x$, halts if $x \in L$, and doesn't halt if $x \notin L$. It is *decidable* if there is a Turing machine that on input $x$, halts at an accepting state if $x \in L$, and halts at a rejecting state if $x \notin L$. It's not hard to check that every decidable language is also semidecidable.

A logical system is semidecidable (decidable) if the language of all theorems in the system is semidecidable (decidable).

Being semidecidable is an *upper bound* on the complexity of a language. Being NP-hard is a *lower bound* on the complexity of a language. If all you know about a language is that it is semidecidable, you cannot deduce that it is NP-hard, just as you cannot conclude that $x \geq 0$ from the inequality $x \leq 1$.

The halting problem is $\Sigma\_1^0$-complete, which means that it is semidecidable (an upper bound), and moreover, every semidecidable language can be reduced to it using a computable reduction (a lower bound). To be equivalent to the halting problem, you need both an upper bound on your language and a lower bound on your language. The language of theorems in a logical system is guaranteed (by definition) to be semidecidable, but it could also be decidable, in which case it is definitely not equivalent to the halting problem.

Finally, you don't explain what you mean by First Order Logic, but assuming that it can express propositional tautologies, then the corresponding language of theorems is definitely NP-hard, by reduction from SAT. In fact, the language of true quantified Boolean formulas, known as TQBF, is known to be PSPACE-complete.
> 2 votes

---
Tags: complexity-theory, logic
---


# Question
Title: Longest Common Sequence reduction proof question
I'm trying to get at least a laymans understanding of how the Longest Common Sequence (LCS henceforth) can be shown to be NP-Hard and I'm trying to do that by reducing it to an NP-Complete problem like Vertex Cover. I read through this downvoted question on another stack exchange.

> I am trying to understand the demostration of intractability of the LCS problem, as stated as a reduction from Vertex-Cover problem, and so far, i'm stuck with the demostration of the problem in this paper from David Maier
>
> Anybody know some simple example to reduce LCS from Vertex-Cover?

With a self answer of

> It was as simple as:
>
> * Take a Vertex-Cover problem to convert to LCS
> * Create a string template from the Vertex-Cover graph
> * Take each vertex from the Vertex-Cover problem and generate an equivalent string for it, ommiting the vertex selected
> * Presto, you have a LCS problem equivalent.
>
> Thanks for the downvotes

I've been trying to work out on paper how this makes sense but keep coming up against a wall. Could someone show me how this is either incorrect or how it is correct with a more worked out example/proof?

# Answer
> 3 votes
We can prove that LCS (with an unbounded number of sequences!) is NP-hard by reduction from 3SAT. Let us be given a CNF $\varphi$ with $m$ clauses $C\_j$ of the form $$ (x\_{i\_{j,1}} = b\_{j,1}) \lor (x\_{i\_{j,2}} = b\_{j,2}) \lor (x\_{i\_{j,3}} = b\_{j,3}). $$ Here $b(j,c)$ is either T or F, and we assume that $i\_{j,1},i\_{j,2},i\_{j,3}$ are all distinct.

We will consider the following strings:

* $S\_1 = x\_{i\_{1,1},1}^{b\_{1,1}} x\_{i\_{1,2},1}^{b\_{1,2}} x\_{i\_{1,3},1}^{b\_{1,3}} \ldots x\_{i\_{m,1},m}^{b\_{m,1}} x\_{i\_{m,2},m}^{b\_{m,2}} x\_{i\_{m,3},m}^{b\_{m,3}}$.
* $S\_2 = x\_{i\_{1,2},1}^{b\_{1,2}} x\_{i\_{1,3},1}^{b\_{1,3}} x\_{i\_{1,1},1}^{b\_{1,1}} \ldots x\_{i\_{m,2},m}^{b\_{m,2}} x\_{i\_{m,3},m}^{b\_{m,3}} x\_{i\_{m,1},m}^{b\_{m,1}}$.
* $S\_3 = x\_{i\_{1,3},1}^{b\_{1,3}} x\_{i\_{1,1},1}^{b\_{1,1}} x\_{i\_{1,2},1}^{b\_{1,2}} \ldots x\_{i\_{m,3},m}^{b\_{m,3}} x\_{i\_{m,1},m}^{b\_{m,1}} x\_{i\_{m,2},m}^{b\_{m,2}}$.

For each variable $x\_i$, let $T\_i$ be the string obtained from $S\_1$ by removing all occurrences of $x\_{i,j}^F$ (for all $j$), and let $F\_i$ be the string obtained from $S\_1$ by removing all occurrences of $x\_{i,j}^T$.

* For each variable $x\_i$, $TF\_i = T\_i F\_i$ and $FT\_i = F\_i T\_i$.

Let $R$ be a common subsequence of all these strings.

1. For every $j$, the string $R$ contains at most one of $x\_{i\_{j,1},j}^{b\_{j,1}},x\_{i\_{j,2},j}^{b\_{j,2}},x\_{i\_{j,3},j}^{b\_{j,3}}$. Indeed, suppose that it contained both $x\_{i\_{j,k\_1},j}^{b\_{j,k\_1}}$ and $x\_{i\_{j,k\_2},j}^{b\_{j,k\_2}}$, in this order. Since $R$ is a subsequence of $S\_1$, we must have $k\_1 \< k\_2$. However, if $k\_1 = 1$ then $R$ cannot be a subsequence of $S\_2$, and if $k\_1 = 2$ then $R$ cannot be a subsequence of $S\_3$.

* Thus $|R| \leq m$, and if $|R| = m$ then we can associate with $R$ a choice of equation in each clause.
2. For every $i$, if $R$ contains both $x\_{i,j\_1}^{b\_1}$ and $x\_{i,j\_2}^{b\_2}$ then $b\_1 = b\_2$. Indeed, in any subsequence of $TF\_i$ all symbols $x\_{i,j\_1}^T$ precede all symbols $x\_{i,j\_2}^F$, and in any subsequence of $FT\_i$ all symbols $x\_{i,j\_1}^F$ precede all symbols $x\_{i,j\_2}^T$.

* Thus the chosen equations are all compatible.

This shows that if $|R| = m$ then $\varphi$ is satisfiable. The converse is also easy to establish: given a satisfying assignment, we can choose a satisfied equation in each clause, and then concatenate the corresponding symbols.

Let us give an example. Consider the formula $$ \varphi = \[(x\_1 = T) \lor (x\_2 = T) \lor (x\_3 = T)\] \land \[(x\_2 = F) \lor (x\_4=F) \lor (x\_1 = F)\]. $$ The strings are

* $S\_1 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $S\_2 = x\_{2,1}^T x\_{3,1}^T x\_{1,1}^T x\_{4,2}^F x\_{1,2}^F x\_{2,2}^F$.
* $S\_3 = x\_{3,1}^T x\_{1,1}^T x\_{2,1}^T x\_{1,2}^F x\_{2,2}^F x\_{4,2}^F$.
* $TF\_1 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $FT\_1 = x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F$.
* $TF\_2 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $FT\_2 = x\_{1,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{4,2}^F x\_{1,2}^F$.
* $TF\_3 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $FT\_3 = x\_{1,1}^T x\_{2,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $TF\_4 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F$.
* $FT\_4 = x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{4,2}^F x\_{1,2}^F x\_{1,1}^T x\_{2,1}^T x\_{3,1}^T x\_{2,2}^F x\_{1,2}^F$.

One string $R$ of length $m=2$ which is common to all of these is $x\_{1,1}^T x\_{2,2}^F$. This corresponds to the (partial) truth assignment $x\_1=T,x\_2=F$, which satisfies $\varphi$.

---
Tags: np-complete, np-hard
---


# Question
Title: Computing min and max using median of 3 elements
How can I write an O(n)-time algorithm to find the minimum and maximum, given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of three elements x,y,z? You are not allowed to read or compare the elements directly; the only operation that is allowed is invoke the median3 subroutine.

# Answer
> 1 votes
Let the list be $x\_1,\ldots,x\_n$. The algorithm is as follows:

1. Let $S = \\{x\_1,x\_2\\}$.
2. For $i = 3,\ldots, n$:
    * Add $x\_i$ to $S$.
    * Compute the median of $S$, and remove it from $S$.
3. Output $S$.

I'll let you figure out why this works.

Note that we cannot possibly tell which is the minimum and which is the maximum. Indeed, $\operatorname{median3}$ works the same for both the original order and its reverse.

---
Tags: algorithms, searching
---


# Question
Title: Finding the regular expression equivalent for the given finite automaton
This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression.

On inspecting the given automata, I started deducing the expressions that it accepts and tried to find a pattern, and this is what I was able to figure out -

The automata makes the following transitions to a final state upon said input -

1. $q\_1 to \ q\_3$ on input of a single symbol $b$, $a^\*b$, $ba^\*$, or $a^\*ba^\*$.
2. Traversing through the cycle $q\_1,q\_3,q\_2$ (and so on repeating) on input of $(a^\*b^4a^\*)^\*$, a $((a^\*b)^4)^\*$.

Now the equivalent regular expression must be the sum of all these expressions,

R = $b + (a^\*b) + (ba^\*) + (a^\*ba^\*) + (a^\*b^4a^\*)^\* + ((a^\*b)^4)^\*$.

Is there a better, concise expression for this or am I missing something? If not, How do I approach the simplification process of this expression?

# Answer
Your DFA accepts the language of all words over $\\{a,b\\}$ in which the number of $b$s is of the form $3n+1$ (i.e., it is equivalent to 1 modulo 3). More generally, upon reading a word $w$, the DFA will be in state $q\_1$ if it read a number of $b$s which is a multiple of 3; in state $q\_3$ if it read a number of $b$s which is equivalent to 1 modulo 3; and in state $q\_2$ if it read a number of $b$s which is equivalent to 2 modulo 3.

Using this description, it is easy to come up with a regular expression equivalent to your DFA. Rather than do that, let me give regular expressions for the language $L\_{even}$ of words over $\\{a,b\\}$ containing an even number of $a$s, and for the language $L\_{odd}$ of words over $\\{a,b\\}$ containing an odd number of $a$s:

* $L\_{even}$: $b^\*(ab^\*ab^\*)^\*$.
* $L\_{odd}$: $b^\*ab^\*(ab^\*ab^\*)^\*$.

These examples should enable you to solve your specific problem.
> 2 votes

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


title: Propositional Logic Time complexity

text:
# Question
Title: Propositional Logic Time complexity
If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

So if i have a propositional formula with 3 variables i have 8 interpretations.

So, is the time complexity of the SAT problem of propositional logic a $O(2^{x})$ ?

# Answer
Your question hints at multiple misconceptions which I'm going to address.

> If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

First, let's be clear about terminology.

* variable vs literal -- the formula $a \lor b \land a$ has three literals but two variables.
* model vs interpretation -- every logical formula has exactly one of two possible interpretations, true and false.

It would be correct to say: the number of *models* grows exponentially (with base 2) in the number of variables.

> So, is the time complexity of the SAT problem of propositional logic a $O(2^x)$?

No, that does not follow.

* What is $x$? In complexity theory, we usually express complexity in the input length. So if $x$ is the number of literals, that thought makes sense; if it's the number of variables, it does not. However, in the *worst* cases (if we consider search space alone), the number of variables and literals is the same.
* The number of possible models (e.g. valuations of the variables) alone is not trivially an upper bound on the complexity. The brute-force algorithm also has to evaluate the formula for every candidate, so you have to add a linear factor at least (depends on the computational model and cost model you use).
* When somebody says, "the complexity *is* X" that implies a lower bound in addition to an upper bound. Your observation does not provide a lower bound, even after correction.

That is because the size of the search space does not correlate with solving complexity. Take sorting, for instance: finding the correct permutation has a search space of size $n!$ and yet we can solve the problem in linearithmic time. SSSPP is another common example.
> 5 votes

# Answer
The complexity of determining the satisfiability of a given propositional formula is unknown. It is conjecture not to be polynomial – this is the celebrated $\mathsf{P} \neq \mathsf{NP}$ conjecture. A more refined conjecture is the exponential time hypothesis and its variants, which have recently seen applications in (conditionally) analyzing the complexity of problems in $\mathsf{P}$, a pursuit known as fine-grained complexity.
> 4 votes

---
Tags: complexity-theory, time-complexity, logic
---


title: Solving complexity using summation

text:
# Question
Title: Solving complexity using summation
I have the following algorithm:

```
func()
{
    for(i=1; i<n; i=i*2)
        print("aa");
}

```

How can I find Big-Oh using summation?

# Answer
> 2 votes
Finding a suitable sum here is a bit awkward since sums in mathematics tend to step up by one, always. So we have to normalize the sequence of values of `i`

$\qquad i = 1, 2, 4, 8, \dots \[i\<n\]$

to

$\qquad i' = 0,1,2,3, \dots \[???\]$.

My notation already suggests that it's about finding the right termination predicate.

Roughly speaking, you're looking for the *inverse operation* to the repeated step function, which by itself is $i \mapsto 2i$. I'm not sure how to lead you towards an answer unless you know about logarithms. If you do, it should be kind of obvious; roughly:

$\quad i' = 0,1,2,3, \dots \[i'\<\log\_2 n \pm 1\]$.

Do some tinkering to find out whether you need to use $\lfloor \log\_2 n \rfloor$ or $\lceil \log\_2 n \rceil$ as upper bound on $i'$. Now, the rest is elementary.

Note that you can go about this by normalizing the `for` loop first:

```
for(i=1; i<n; i=i*2)
    print(i)

```

becomes

```
for(i' = 0; i' < log(2,n) +- 1; i'++)
    print(2^i');

```

Note that for functional equivalence, I start with $i'=0$ so that $2^{i'} = i$ in each iteration; you can also use $2^{i'-1}$ instead and start with $i'=1$. Try out a few things -- some make the code nicer, others the mathematics afterwards.

Make sure -- by proof and/or testing -- that the normalized loop computes exactly the same thing as the old one, and then it's all standard. You might need a cheat sheet to simplify the sum.

# Answer
> 0 votes
Summation is not the correct technique here. The running time is proportional to the number of loop iterations, which is the number of times you have to double 1 until you reach $n$ (or more). For example:

* If $n \leq 1$, the loop is run zero times.
* If $1 \< n \leq 2$, the loop is run once.
* If $2 \< n \leq 4$, the loop is run twice.
* If $4 \< n \leq 8$, the loop is run thrice.
* If $8 \< n \leq 16$, the loop is run four times.

And so on. It remains to relate $n$ to the number of iterations of the loop.

It is possible to express the number of iterations as an infinite sum: $$ T(n) = \sum\_{k=0}^\infty \[\\!\[n \> 2^k\]\\!\], $$ where $\[\\!\[n \> 2^k\]\\!\]$ is $0$ if $n \leq 2^k$ and $1$ if $n \> 2^k$. However, I'm not sure that this representation brings us any closer to finding the formula $T(n) = \lceil \log\_2 n \rceil$.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem
Show that $L = L\_\phi \cup L\_{\\{\sum^\*\\}} \notin RE$ with Rice theorem.

Well I did show that with reduction, by using $HP'$.

Simply by creating a function from $f(\langle M \rangle, x) = (M')$

Thus, if $M$ stops on $x$ then $M'$ simulates the machine that stops on the empty word and accepts/rejects like it.

> $(\langle M \rangle, x) \in HP' \rightarrow M$ rejects every input$ \rightarrow \langle M' \rangle \in L\_2$
>
> $(\langle M \rangle, x) \notin HP' \rightarrow M$ halts on $x \rightarrow L(M') = \phi $(it stops only on the empty word) $ \rightarrow \langle M' \rangle \notin L\_2$

**EDIT:** In other words, can I just say that there're languages that contains $L$ thus $\in RE$ and languages that don't contain $L$ thus $\notin RE$. For example $L\_{\phi \cup \sum^\*\cup L\_1}$ or just $L\_1$. And $L\_1$ is defined as a language that accepts all the languages with at least 200 words for example. Will this work for the Rice's theorem?

# Answer
> 0 votes
Rice's theorem only proves undecidability, not un-semi-decidability. There is a variant that does that, but that has other conditions (obviously).

---
Tags: computability, reductions, semi-decidability, rice-theorem
---


# Question
Title: A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers
As we know, $\epsilon$ is the empty string, with length 0. It is not part of any any alphabet by default, unless specifically defined so. However, it is a string over any alphabet.

For example, Given that I need to design a Deterministic or Nondeterministic finite state automaton (without $\epsilon$ transitions) that accepts decimal numbers that are say, divisible by 2, would I have to account for the empty string as an input word as well? If so, how does divisibility work for null input?

# Answer
> 2 votes
The language has been defined as the set of strings that have some property. If the empty string has that property, then it is in the language. If the empty set does not have that property, then it is not in the language. It doesn't matter whether the property is "being a decimal representation of an even number" or anything else.

If the property is expressed in an imprecise or open-ended way that doesn't make it clear whether the empty string has the property or not, then you should choose whichever is most convenient for you and say what you have done.

# Answer
> 2 votes
It is rather standard to assume that `0` represents zero (and is divisible by two). Also it is usually assumed that decimal numbers do not start with `0`.

I once presented a finite state automaton without these assumptions, where I took $\varepsilon$ as a representation for zero, and likewise `0000`, and my students protested.

# Answer
> 2 votes
The short answer is: no, you don't have to.

In the context of representations, the empty string is usually associated with the absence of *representamen* (that which might stand for something else). Technically, by definition, it could only represent itself, which is why we adopt a symbol from a meta-alphabet to denote it, when we have to.

In formal languages, it arises from the need to introduce the empty sequence as a legitimate word. For instance, it is the identity element of the concatenation operation, the complement of $\Sigma^+$, and so on.

That said, we could have a language for the representation of numbers on which the absence of representamen is equated to a value (zero, for instance). If your alphabet is unary, that would have to be the case. It wouldn't be properly a *representation* (except on the meta-alphabet). In some situations, what amounts to a *value* can still be produced by the absence of an event.

---
Tags: formal-languages, automata, finite-automata
---


title: Fast searching through bitarray?

text:
# Question
Title: Fast searching through bitarray?
I've been thinking for some time but can't figure a way out. I have big bitarray i.e. 1000+ items of 10\_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of memory).

I'm looking for some better algorithm for searching/matching !

Do you have any idea ?

bitarray looks like this :

```
 0) 1011.... <= 10_000 bits
 1) 1100....
 2) 0010....
 3) ........
 ...........

```

now find index of "1100...." :

```
 find(1100....) = 1

```

---

50% of bits are 1, 50% are 0, always.

---

I could probably sort it by hamming distance, but will be time consuming! (and array grows dynamically, so i have to re-sort) and the search will still be slower if I search one by one (probably because python overhead). Currently the search is binary op+, but as you expect doesn't scale well i.e.

```
#duplicate the search item to the size of array
si_dup = search_item * array_size
dist's = (array ^ si_dup).count_by_row(1s)
top_idx = dist's.argmin()

```

The bad thing is that this is parallelize-able (I can process it in chunks), but python is not multi-threaded :(. Also can seem to find a DB which handle large binary-strings, that will be a way out for large sets, I think!

---

thanks, "locality sensitive hashing" was the key, I researched it a bit and that seem will be the solution for large bitarrays (LSH via BitSampling). For small ones the current approach I think will be faster.

# Answer
> 2 votes
If you want to look for an exact match, use a hashtable. Choose a hash function that hashes a 10,000-bit string to a short hashcode. This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.

# Answer
> 1 votes
IMO, no sensible answer can be given without some knowledge on the distribution of the bits in those keys.

It might very well be that the first, say, 32 bits of the keys are completely discriminant and sorting or hasing on these will do the trick, with no need for full comparisons.

It could also be that the 600 first bits are always the same and this would defeat the above techniques.

There is not one-fits-all answer. Most probably, some form of compression followed by hashing would be welcome.

---
Tags: algorithms, arrays, binary, bit-manipulation
---


title: Prefix Sums in Mutable 2D Array

text:
# Question
Title: Prefix Sums in Mutable 2D Array
Suppose I have a 2D array `M[n][n]` of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate pair $k,l$, what is $$ \sum\_{i = 0}^{k-1} \sum\_{j = 0}^{l-1} M\[i\]\[j\]? $$ Of course, all these values can be computed in $\mathcal O(n^2)$ time total, and after that queries take $\mathcal O(1)$. However, my array is mutable, and each time I change a value, the obvious solution requires a $\mathcal O(n^2)$ update.

We can create a quad tree over `M`; the preprocessing takes $\mathcal O(n^2\log(n))$, and this allows us to do queries in $\mathcal O(n\log(n))$, and updates in $\mathcal O(\log(n))$.

My question is:

> Can we improve significantly on the queries without sacrificing too much on the updates?

I am especially interested in getting both the update and query operations sub-linear, and in particular getting them both to $\mathcal O(n^\epsilon)$.

Edit: for some more information, although I think the problem is interesting even without this further restriction, I expect to do roughly $\mathcal O(n^3)$ queries, and about $\mathcal O(n^2)$ updates. The ideal goal is to get the full runtime down to about $\mathcal O(n^{3+\epsilon})$. Thus, a situation where an update takes $\mathcal O(n \log(n))$ while a query takes $\mathcal O(\log(n))$ would also be interesting to me.

# Answer
There is a relatively straightforward solution where each query and each update can be done in $O(\log^2 n)$ time. The data structure uses $O(n^2)$ space.

We will have $\lg n$ "granularities" of data structure, one for each power of two $2^m$ such that $1 \le 2^m \le n$. The data structure for granularity $2^m$ stores the sums

$$\sum\_{i=k\_0 \cdot 2^m}^{(k\_0+1) \cdot 2^m -1} \sum\_{j=0}^{l-1} M\[i,j\]$$

for each $k\_0,l$. This data structure for granularity $2^m$ can in turn be represented using $n/2^m$ balanced trees (one for each possible value of $k\_0$) to store prefix sums.

Now to look up the prefix sum for $k,l$, we break up the interval $\[0,k-1\]$ into a union of intervals of power-of-two length; at most $\lg n$ intervals are needed. For each such interval of length $2^m$, we do a lookup into the data structure of granularity $2^m$. Thus queries can be answered by doing $O(\log n)$ lookups into a balanced tree, each of which takes $O(\log n)$ time, for a total time of $O(\log^2 n)$ per query.

Updates can also be done in $O(\log^2 n)$ time. To update $M\[i,j\]$, for each granularity $2^m$, you update the appropriate balanced tree in the data structure of granularity $2^m$. This is $O(\log n)$ updates oin $O(\log n)$ balanced trees; each such takes $O(\log n)$ time, so the total time is $O(\log^2 n)$ time.

Finally, the data structure of granularity $2^m$ contains $n/2^m$ trees, each taking up $O(n)$ space, so the total space usage is $O(n^2 \cdot (1 + 1/2 + 1/4 + \cdots)) = O(n^2)$.
> 4 votes

---
Tags: complexity-theory, data-structures, trees
---


# Question
Title: Python: A doubt on time and space complexity on string slicing
This qns is from my school's exam paper.

Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase.

The function remove takes as inputs 2 strings, a letter and a word, and outputs the word with all occurrences of letter removed.

Provide an iterative implementation of the function remove and briefly explain the time and space complexity of the function you have written.

Attached below was my code, which is the same as the solution provided.

However I got stumped when I tried to explain the time and space complexity as O(n) and O(1) respectively as the answer given was O(n^2) and O(n).

The explanation provided by the examiner is:

Time complexity: O(n^2) where n is the length of the input string. This is because in every loop iteration, the string concatenation of new\_word gets longer until it is at worst, length n.

Space complexity: O(n), even though there are no delayed operations or new objects being created every iteration, the new string created at worst can be the same length as the original string if there are no letters removed.

My practice is when I explain something, I should be able to map it out mathematically.

Time: Sum of time taken for each iteration OR Sum of time for each recursion

1)I do not understand why string concatenation contributes to time complexity. For recursive codes its clear cut as there is string slicing involved(s\[0\] and s\[1:\], formation of s\[1:\] will take O(n-1),O(1) from s\[0\] is negligible) in every recursive call, sum of time is n+(n-1)+…+1=O(n^2). For the explanation of iterative, should I just accept it or is there a theory behind why concatenation adds to time complexity.

Space: Sum of space taken for each recursion OR sum of space taken for each iteration

2) I initially thought space for recursion and iteration is calculated the same way. Is it correct to accept that for iteration, space should be calculated as the space needed for the most demanding iteration instead of the accumulative sum of space for all iterations. Most demanding would then be when new\_word and word are equivalent.

3) I actually accepted the fact that iteration usually takes up O(1) space and would bomb it everytime I can. What is really the reason behind deeming the space complexity of iterative to be O(1)?

Correct me at any point as I find that I am memorising and not understanding many things at this point.

```
def remove(letter,word):
    new_word=""
    for i in word:
        if letter!=i:
            new_word+=i
    return new_word

```

# Answer
The running time of string concatenation depends on how it is implemented. It is impossible to tell whether `new_word += i` takes $O(1)$ or $\Theta(|\text{new\_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using.

In contrast, it is quite clear that the procedure uses $\Theta(|\text{word}|+1)$ space, since it builds `new_word` from scratch, not reusing the memory of `word`. This has nothing to do with the loop; the statement `new_word = word[:]`, which makes a copy of `word`, also uses up $|\text{word}|$ space. Space consumption is the amount of memory used. If you're constructing a new string of length $|\text{word}|$, then it uses up memory proportional to $|\text{word}|$.

I suggest forgetting about what you call the "mathematical perspective", and focusing instead on the intuitive meaning of time and space complexity. Time complexity is the number of instructions executed by the program. Space complexity is the amount of memory that needs to be allocated in order to run the procedure. You are stating some rules for calculating these quantities, but it's much more important for you to understand *what* you are calculating rather than specific tricks which are dubious when applied mechanically.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, space-analysis
---


title: Complement of Mealy machine

text:
# Question
Title: Complement of Mealy machine
How could one reasonably *define* and *construct* the complement of a deterministic Mealy machine?

My intuition is that the complement should give exactly the opposite of output strings after a specific input string. I think this means the complement is non-deterministic. So let's define a (non-deterministic) Mealy machine: $\mathcal{M} = \langle S,I,\Sigma,\Omega,\delta,\lambda\rangle$, where

* $S$ is a finite nonempty set of states,
* $I \subseteq S$ is the nonempty set of initial states,
* $\Sigma$ is a finite input alphabet,
* $\Omega$ is a finite output alphabet,
* $\delta: S \times \Sigma \to 2^S$ is the transition function, and
* $\lambda: S \times \Sigma \to 2^\Omega$ is the output function.

A Mealy machine is deterministic iff $\vert I\vert = 1 \land \forall s \in S, \forall i \in \Sigma: \vert\delta(s, i)\vert \leq 1 \land \vert\lambda(s, i)\vert \leq 1$.

I believe defining and constructing the complement is easier if we assume the transition function, and output function are total. That is fine for me.

So, given a Mealy machine $\mathcal{M}$ how would one *define*, and *construct* (using an algorithm) the complement $\overline{\mathcal{M}}$?

If the algorithm follows trivially from the definition of $\overline{\mathcal{M}}$ that is fine too.

My first idea is that one could, for every transition, add new transitions (from, and to the same state) that give exactly the complement of outputs. However, I am afraid I am missing important corner cases.

# Answer
You are right: it is easy to miss corner cases, so whatever you choose to define, you will need to prove that you defined the right thing.

To do so, you need to first define what you actually want, i.e., the **language** of $\overline{M}$.

From what I can tell, you want $$\mathcal{L}(\overline M) = \\{ (w^I\_0 ,w^O\_0) (w^I\_1 ,w^O\_1) \ldots \in (\Sigma \times \Omega)^\omega \mid (w^I\_0,w^O\_0) (w^I\_1 ,w^O\_1) \ldots \not\in \mathcal{L}(M)\\}$$

If you just just invert the set of possible outputs along an edge, then get an automaton $\overline M$ for which you can then try to prove that it has the right language, i.e., that (1) every word accepted by the automaton is in the language that we defined for it, and (2) vice versa.

Because this seems to be connected to your research, I will not give you the answer whether such a proof works (as I don't want you to force to give non-citation credit to the work of others, which you would need to do if someone else gives you a solution), but rather let you try this out on your own.

Should this approach not work, here is an idea that allows you to cover all corner cases:

* Translate the Mealy automaton to a DFA (deterministic automaton over finite words) that accepts all prefix traces of the Mealy automaton's language
* Complement the DFA
* Conjunct the DFA with with a DFA accepting all words from $(\Sigma \times \Omega)^\*$.
* The resulting automaton accepts the words that you want your Mealy automaton to have. So define a suitable translation to a non-deterministic Mealy automaton.

The idea here is the complementation part is done by a well-known and known-to-work algorithm, so you avoid parts of your problem. The last step is still non-trivial, but probably easier than before.
> 3 votes

---
Tags: automata, finite-automata, closure-properties, nondeterminism
---


title: Integer Problems are NP-HARD

text:
# Question
Title: Integer Problems are NP-HARD
I studied that Integer problems are properly NP-HARD problems. I know that NP-HARD include problems that arent solvable, like the halting problem. This mean that there are instances of Integer problems that arent solvable ?

# Answer
> 1 votes
No, it doesn't mean that.

The set of NP-hard problems is upward-closed in the sense that there is no upper bound on the hardness of problems in it. You are correct to say that the class of NP-hard problems contains undecidable problems.

That does not imply, however, that every NP-hard problem has "unsolvable instances".

1. There is no such thing as an "unsolvable instance" in integer programming. There always is an answer, true or false (considering the decision version). Every finite set of instances is trivially computable. Only infinite sets can be undecidable.
2. We *do* know upper bounds on integer programming. For the decision version, we know that it's in NP; the optimization version is in NPO. Therefore, we know IP is decidable.

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


# Question
Title: Shortest Non-Subsequence String With Constant-Size Alphabet
Let $S\[1..n\] \in \Sigma^\*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (possibly no) symbols.

For instance, we are given $\Sigma = \\{ A, C, G, T \\}$ and $S = ACGTACGT$. In this case, one valid answer is $CCA$, because it does not occur as a subsequence in $S$ (i.e. cannot be obtained by removing some of the symbols from $S$) and there is no such string of length $2$.

I am looking for an algorithm which takes $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ time. It is not sufficient to compute the length of the answer, an example should also be constructed.

**Observations and Approaches.** The length of the answer does not exceed $\displaystyle \frac{n}{|\Sigma|} + 1$ by pigeonhole principle. This upper bound is attained for $S = ACGTACGT...ACGT$ in the above example. If we are only interested in the length of the answer, the following approach should work. Let $f(i)$ denote the largest $k \in \mathbb{N}$ such that every string of length $k$ is a subsequence of the prefix $S\[1..i\]$. Our final answer is $f(n) + 1$ and $f$ can be computed by dynamic programming in $\mathcal{O}(n)$ time for $1 \le i \le n$ simply by recurrence

$\displaystyle f(i) = 1 + f\left(\min{(\ell(i, \sigma\_1), \ell(i, \sigma\_2), \dots, \ell(i, \sigma\_{|\Sigma|})) - 1}\right)$

where $\ell(i, \sigma)$ denotes the last occurrence of $\sigma \in \Sigma$ in the prefix $S\[1..i\]$. Obviously, the function $f$ is increasing, i.e. $f(i + 1) \ge f(i)$ for $1 \le i \le n - 1$. It seems more difficult to construct an example from this information, that is where I am stuck.

Finally note that the problem is a lot easier, if we require the subsequence do be contigous. Since there are only $\mathcal{O}(n^2)$ substrings, but $\mathcal{O}(|\Sigma|^k)$ strings of length $k$ over $\Sigma$, $k$ turns out to be very small and even brute-force will succeed.

Any kind of help is appreciated, thanks in advance.

*Original Source: CSES Problem Set (https://cses.fi/problemset/task/1087/).*

# Answer
> 3 votes
For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S\[1\ldots i\]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma\_1\right),\ldots,\ell\left(i,\sigma\_{|\Sigma|}\right)\right)$. $g(i)$'s can be computed in $O(n)$ time in advance.

We have $$ s(i)=s(g(i)-1)S\[g(i)\]. $$ Firstly $s(g(i)-1)S\[g(i)\]$ is of length $f(i)+1$. Suppose by contradiction $s(g(i)-1)S\[g(i)\]$ is a subsequence of $S\[1\ldots i\]$, then the index that the last character $S\[g(i)\]$ matches must be less than or equal to $g(i)$, which means $s(g(i)-1)$ is a subsequence of $S\[1\ldots (g(i)-1)\]$, a contradiction. So the recurrence is correct.

Now you can use this recurrence to compute $s(n)$:

1. Let $i \leftarrow n$, and let $s$ be an empty string.
2. If $g(i)$ does not exist, which means there is at least one character not appearing in $S\[1\ldots i\]$, insert this character to the beginning of $s$ and return $s$.
3. Insert $S\[g(i)\]$ to the beginning of $s$.
4. Let $i\leftarrow g(i)-1$.
5. Go back to step 2.

---
Tags: algorithms, dynamic-programming, strings, subsequences
---


# Question
Title: Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?
For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations

1. Calculating the $n^\text{th}$ root of an integer $x$, $$ \sqrt\[\leftroot{-3}\uproot{3}n\]{x} $$
2. Checking whether $$ a \equiv b \mod r $$ for $a,b,r \in \mathbb{N}$

I now think I may have come close to finding an answer to the second of these problems, but I am not certain.

On pages 10-11 of the book Édouard Lucas and Primality Testing (by Hugh C. Williams), the following statement is made:

> For any $m$ and $a,b$ with $0 \< |a|, |b| \< m$ calculating $$ r \equiv ab \mod m $$ can be done in $O((\log m)^2)$ operations.

Am I to assume, based on this, that operation 2. has complexity $O((\log m)^2)$?

I also suspect that operation $1$ has complexity $O((\log m)^2)$, but I have no justification for this. Could someone please also tell me whether this is correct?

# Answer
You can multiply two n-bit numbers trivially in $O(n^2)$, but using FFT (fast fourier transform) you can get the time down to $O (n \log n \log \log n)$. Lets call this time T(n).

For the modulo, you would calculate ab, then z = floor (ab / m), then r = ab - mz. If mz \> ab then z was too large, so decrease z by 1 and subtract m from mz.

To find ab / r, you can use Newton iteration. There is a clever way to arrange this without any divisions, just multiplications. This is an iterative method with about log n iterations, but only the last iteration needs the full precision, so the total time is O (T(n)).

Things are even better if you want $z = a^{1/b}$ rounded to an integer, and to check if it is an integer. Again you use Newton iteration, but you only need a result with a bit over n / b bits precision. The result itself is a bit harder to calculate, requiring about log b multiplications, so the time to calculate this is $O (T (n / b) \log b)$. If you can't decide whether z is an integer or not due to precision, you can calculate $round(z)^b$ in T(n).
> 2 votes

---
Tags: complexity-theory, time-complexity, asymptotics
---


title: ILP runtime seems to be linear?

text:
# Question
Title: ILP runtime seems to be linear?
I have a variation the shortest path problem, formulated as an ILP. The system model is as follows:

* There is a connected digraph consisting of 20 nodes, with each link having an associated weight *delay* which is a *float*. The graph is modeled as a python networkx object as follows:

```
g = nx.DiGraph(nx.barabasi_albert_graph(20, 2))
for u, v in g.edges:
    g[u][v]['delay'] = random.uniform(50, 1000)  # uS

```
* There are multiple source-destination pairs and each pair has an associated 'demand' in terms of *delay*. The problem is modeled in python PuLP and solved using Gurobi solver.

```
# get cost
delay_d = nx.get_edge_attributes(self.graph, 'delay')

# get links
links = []
for i, j in self.graph.edges:
    links.append((i, j))

# instantiate the problem
prob = pulp.LpProblem("Shortest Path Problem", pulp.LpMinimize)

# create binary variables to state a link is chosen on shortest path
var_dict = {}
for flow_name in self.list_of_flows:
    for (i, j) in links:
        var = pulp.LpVariable('x_(%s,%s)_%s' % (i, j, flow_name), cat=pulp.LpBinary)
        var_dict[(i, j, flow_name)] = var

# create slack variables for every flow
delay_slack = {}
for flow_name in self.list_of_flows:
    delay_slack[flow_name] = pulp.LpVariable('d_%s' % flow_name, lowBound=0.0, cat=pulp.LpContinuous)

# formulate the objective
prob += pulp.lpSum([pulp.lpSum([delay_d[(i, j)] * var_dict[(i, j, flow_name)] for (i, j) in links])
                    for flow_name in self.list_of_flows ]) \
        + pulp.lpSum([1000 * delay_slack[flow_name] for flow_name in self.list_of_flows])

# formulate the constraints
for flow_name, flow in self.list_of_flows.items():
    # conservation of flow constraints
    for node in self.graph.nodes:
        if node == flow['source']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 1
        elif node == flow['target']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == -1
        else:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 0

    # delay constraint
    prob += pulp.lpSum([var_dict[(i, j, flow_name)] * delay_d[(i, j)]
                        for (i, j) in links]) - delay_slack[flow_name] <= flow['qos']['delay']

# solve the optimization problem
prob.solve(pulp.GUROBI_CMD(msg=0))

```

There are no issues with the solution and correct results are obtained. However, when I calculated the runtime, the results seem to be linear.

Now, I know that if an ILP satisfies the property of *unimodularity*, then the LP relaxation gives integer solution. Thus such an ILP can be solved in polynomial time using methods such as simplex.

However, if we look at the delay constraints, the coefficients of LHS are not integers, nor is the RHS integer. Thus it seems unimodularity property is not satisfied. Hence, shouldn't the runtime be exponential?

Can anyone explain why the runtime graph is linear?

# Answer
I will try to answer to your question with an example.
Consider the following time complexity: $f(n)=2^\frac{n}{1000}$.

It is clearly exponential in $n$, but look at the plot.

For $n \in \[0,80\]$:

From this perspective it looks constant, right?

For $n \in \[0, 1.5 \cdot 10^4\]$:

From this perspective everything changes.

What I want to show, is that inferring the complexity just looking at the runtime with different inputs size is not possibile.
> 3 votes

# Answer
Remember that NP-hardness is about *worst-case intractability*. For example, it is perfectly possible you can solve even large ILP instances quickly. If and when this happens, the instance has some structure the ILP solver is able to exploit to find a solution quickly.
> 3 votes

---
Tags: time-complexity, optimization, np-hard, integer-programming
---


# Question
Title: Why is integer programming more difficult than (real) linear programming?
Why is integer programming (IP) more difficult than (real) linear programming (LP)?

I searched a lot on the web, but I didn't find an answer.

# Answer
Given a starting solution, the Simplex algorithm will systematically find solutions with better values of your goal function. However, it runs using real numbers (or rational numbers). You can use the Simplex algorithm to find a solution for an integer programming problem that is optimal, except that it ignores the need for integer values.

Lets say you have a solution where a variable x has a value of x = 1000.525. Clearly that's not an acceptable solution. So you take your system, make two copies, and in one copy you add the condition x ≤ 1000, in the other you add the condition x ≥ 1001. You solve both copies of the problem, but then you have other non-integer values and you go on.

So starting with your non-integer solution, you have many, many ways to try to turn them into integer solutions.

The smaller the numbers, the worse it gets. In that example I gave, you'd expect that the solution doesn't change a lot. If you have a solution x = 0.7, you add the equation x = 0 or x ≥ 1, and that can make a massive change.
> 1 votes

---
Tags: complexity-theory, optimization, linear-programming, integer-programming
---


title: Big-O notation analysis

text:
# Question
Title: Big-O notation analysis
Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct.

I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$

```
(a)
   sum=0;
   for ( i =0; i<n ; i +=10)
      sum++;

(b)
    sum=0;
    for ( i =0; i<n*n;++ i )
        for ( j =n ; j >0;--j )
            ++sum;

(c)
    sum=0;
    for ( i =0 , j =n ; i<j ;++ i , j --)
        ++sum;

(d)
    int function (long n){
       int sum = 0 ;
       for (;n>0;n/=2){
        sum+=n%2;
       }
       return sum;
    }

```

# Answer
> 1 votes
As you said:

a)running n/10 times therefore O(n)

b)outer loop n^2 times inner loop n times hence O(n^3)

c)Runs n/2-1 times :hence O(n)

d)Runs n/(2^k)=1 where k is some integer(no of times loop runs) on solving we get k=O(logn) , in base 2.

# Answer
> 2 votes
c) is incorrect.

It looks like you are saying it is $O(n^{\frac{1}{2}})$ or $O(\sqrt{n})$. That cannot be the case. You are adding one to $i$ and subtracting one from $j$ on each loop iteration. That means the counters should meet in the middle.

---
Tags: time-complexity, asymptotics, runtime-analysis, performance
---


# Question
Title: Which algorithm for game matchmaking in tournament
I organize amateur tournaments every week with random players. Every week, players sign up, and I get a list with:

* Name
* Rank (1, 2 or 3)
* Role (s) (DPS, TANK and HEALER)

I need to get balanced teams of 6. Ideally, there are 2 DPS, 2 TANKS and 2 HEALERS but in practice there are not enough healers and I have to make 3 DPS, 2 TANKS and 1 HEALER.

The other problem is that some players register together, up to 3 players grouped.

The process is currently done by hand but I would like to automate it.

I learned about the algorithm Knapsack problem, is this a good track?

Do you have any advice to help me in my research?

Thanks you.

# Answer
> 0 votes
One plausible approach is to use local search. In its simplest form, you could start by randomly assigning people to teams, then repeatedly picking a random pair of people and swapping them gives a better assignment, and iterating. This kind of approach should be easy to implement and flexible. But there's a lot more to say, so let me explain in more depth.

First, you need an objective function: a way to measure, quantitatively, how good a candidate assignment is. In your case, you might define a way of computing a penalty score for any proposed team grouping (say, 2 point penalty for each extra or missing DPS, 2 point penalty for each extra or missing tank, 2 point penalty for each extra or missing healer, 3 point penalty for each extra person on the team over 6 or each missing person under 6; or whatever, you pick the penalty scheme). Then you could plausibly define the objective function to be the sum of the penalty scores of all of the teams, and your goal is to find an assignment that minimizes this total penalty.

Next, you use some local search procedure to find an assignment that makes the total penalty as small as possible. The simplest is hillclimbing, which works as follows. Pick an arbitrary initial assignment (e.g., randomly assign each person to a team; or use any other heuristic method of computing an assignment -- it doesn't have to be optimal). Then, in each iteration you randomly pick a modification to the assignment, check whether the proposed modification reduces the total penalty, and if so, you apply the proposed modification. Repeat this over and over, until you go a long time with no improvement.

You need a way to generate a random modification. A simple one would be to randomly pick two people, and swap which team they are on. You can also consider more complex modifications. For instance, randomly pick three or fourpeople, and randomly permute them among their teams. Or, randomly pick two people on two different teams, then randomly assign the first person to one of the two teams, then randomly assign the second person to one of the two teams (so this might put both people onto the same team; this modification is useful if you want to consider solutions where some teams have more than 6 people or fewer than 6 people).

This should be easy to program, and I suspect it'll give a reasonable solution. I suggest trying it and see if you're happy with the solutions it generates.

There are a number of ways to make this more sophisticated, to try to generate solutions that are even better (lower total penalty). You can use a more sophisticated form of local search. For instance, you could try hill-climbing with random restarts, where you do the above process 100 times from 100 different random initial assignments, and keep the best solution found. You could also try simulated annealing, where if the modification makes things worse we still have a (small) probability of applying the proposed modification, and we reduce this probability over time in a specific way.

You'll have to modify this to deal with people who pre-register as a group. Fortunately, it should be easy to generate modifications that respect this constraint. For instance, suppose you randomly pick two people to swap, say Alice and John. If you Alice is part of a pre-registered group with one other, then you might randomly pick someone on John's team so you can swap Alice + her partner with John + that additional person. There are many possibilities; you should be able to select something that makes sense for your particular situation.

---
Tags: algorithms, matching, computer-games
---


# Question
Title: How to define whitespace for certain rules but else ignore it
I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? Like when you declare an int people usually write "int b", and the whitespace separate these two items, but if I write something like "5 + 5" it should ignore the whitespace. Is that simply done by implementing in the rule for declarations like this:

Dcl --\> int" " Id

Expr --\> "int+int".

This should force a user to write a whitespace between the int and Id, but don't care whether there is a whitespace in the Expr rule. Is this correctly understood?

# Answer
I think you're approaching this the wrong way. Writing spaces is better handled as a problem of parsing, not of defining your grammar. That is, your grammar should only concern itself with lists of 'tokens' and your parser is concerned with transforming text into 'tokens' properly.

In a sense, whitespace is something the grammar should be completely unaware of. Whitespace can be useful for your parser to determine whether something is one or two tokens, but I doubt that you want to consider whitespace as a token by itself.
> 2 votes

---
Tags: context-free, programming-languages, parsers
---


title: The Number of Paths in a Directed Graph

text:
# Question
Title: The Number of Paths in a Directed Graph
Suppose I have a directed graph $G = (V,E)$. Suppose that $v\_1$ and $v\_2$ are two nodes in the graph. Am I correct the number of simple paths (that is, it has no cycles) from $v\_1$ to $v\_2$ is $O(E)$? Is it true for the special case of directed acyclic graphs?

Bob

# Answer
That's not true even for DAGs: consider the following, with all edges directed left-to-right:

```
  o   o   o ... o
 / \ / \ /       \
x   o   o   ...   y
 \ / \ / \       /
  o   o   o ... o

```

There are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is set of all regular languages on a specific alphabet a regular language?
so i know that the set of all strings over any finite alphabet is countable, but this question is different

so if our language is set of all regular languages(or set of all regular expressions) on a specific and finite alphabet, then is this set regular? if not then what is it? CFL?

i really can't come up with any FA that can accept this!

# Answer
The language of regular expressions is context-free, but not regular. It is given by the following grammar:

$$E ::= 0 | 1 | (E)^\* | E E | (E|E)$$

Because of the parenthesis matching effect, it's not regular -- the language of matched parentheses is not regular.
> 3 votes

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


# Question
Title: How to verify the solution to n queens problem
I have made an algorithm by which I recently finished counting solutions to 28 queens problem and I have the number. How do I verify that it is correct?

I have heard that it can be done in quadratic time. That is, given a solution to an nqueen problem it can be verified in polynomial time. I would like to know the algorithm too.

Thanks

# Answer
> 0 votes
I suspect what they meant was that if you are given a placement of $n$ queens, you can verify in quadratic time whether that is a valid solution (i.e., none of the queens attack any of the others).

I don't know of any way to verify the count of the number of solutions in quadratic time, and I doubt that such a thing is possible in quadratic time.

# Answer
> 0 votes
I couldn't think of any way to determine the count that is faster than finding all the solutions. There are quite a few problems like that, which may be quite unsatisfactory. In this case, even if I gave a list of all solutions, proving that there are no others would be hard.

So there is likely no *fast* way to check that your solution is correct. Actually, even checking it in a slow way is hard. You might run your software translated to a different programming language, using a different compiler, using a different computer, to check that your solution is not incorrect due to unexpected behaviour of the programming language, bugs in the compiler, or hardware bugs.

That doesn't rule out errors in your algorithm or in your implementation, so you could get a bit more confident if someone else solved the same problem independently from you and came up with the same answer. On the other hand, there may be some subtlety in the problem that both you and the other implementor missed and that means you have identical but wrong answers.

---
Tags: time-complexity
---


# Question
Title: Bellman Ford for directed graph G finds shortest paths within one iteration
Given directed graph G, vertex s, and all v∈V(G) are 1 edge distant from vertex s.

Is it possible to find a specific edges order (from E(G)) such that a single iteration of Bellman Ford pass over these edges in this order finds all the shortest paths (in weight) from vertex s to all vertices?

I couldn't find a counterexample for that, and it seems correct. But I have no idea how to prove it - would appreciate any hint and direction....

# Answer
If there's no negative cycle, this is true even without the constraint that all $v\in V(G)\backslash\\{s\\}$ are one edge distant from vertex $s$.

---

> *Lemma.* There exists a shortest path $e(v,1)e(v,2)\ldots$ (where $e(v,1),e(v,2),\ldots \in E(G)$) from $s$ to $v$ for each $v\in V(G)\backslash \\{s\\}$, such that for each $v\_1,v\_2\in V(G)\backslash \\{s\\}$, if there exists $i\_1,i\_2,j\_1,j\_2$ such that $e(v\_1,i\_1)=e(v\_2,i\_2)$, $e(v\_1,j\_1)=e(v\_2,j\_2)$ and $i\_1\<j\_1$, then $i\_2\<j\_2$.

*Proof.* Suppose there are such shortest paths corresponding to $v\_1,\ldots,v\_k$. Fix these paths and consider any shortest path $e(v\_{k+1},1)e(v\_{k+1},2)\ldots$ from $s$ to $v\_{k+1}$. Let $i$ be the largest index such that $e(v\_{k+1},i)$ appears in those fixed shortest paths corresponding to $v\_1,\ldots,v\_k$. Say $e(v\_{k+1},i)=e(v,j)$ for some $v\in\\{v\_1,\ldots,v\_k\\}$ and some index $j$. Now consider the new path from $s$ to $v\_{k+1}$: $e(v,1)\ldots e(v, j) e(v\_{k+1},i+1)\ldots$ Note $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points (otherwise $e(v,1)e(v,2)\ldots$ is not the shortest path from $s$ to $v$), the new path is no longer than $e(v\_{k+1},1)e(v\_{k+1},2)\ldots$ Now regarding this new path as the shortest path corresoponding to $v\_{k+1}$, we have proved there are shortest paths corresponding to $v\_1,\ldots,v\_{k+1}$ satisfying the conditions in the lemma. Furthermore, the lemma is proved by mathematical induction. $\blacksquare$

---

Due to the lemma, there exists a total order of edges that is consistent with the order of edges in each shortest path selected by the lemma. Apply the first iteration of Bellman-Ford algorithm according to this total order and consider a vertex $v\in V(G)\backslash \\{s\\}$. Recall that $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points, so after dealing with $e(v,1)$, the minimum distance from $s$ to the vertex to which $e(v,1)$ points is computed correctly, and after dealing with $e(v,2)$, the minimum distance from $s$ to the vertex to which $e(v,2)$ points is computed correctly, and so on. Finally we can conclude the minimum distance from $s$ to $v$ is computed correctly. As a conclusion, one iteration corresponding to this total order is sufficient.
> 2 votes

# Answer
what Bellman Ford algorithm does is :It relaxes every edges in graph n-1 times ,In every ith relaxation it checks if distance of a vertex from source vertex got decrease or not.

say all vertices are at infinite distance from source vertex is S (Initially).Then if you relax all edges(In any Order) single time then it will give distance to all vertices which are located at unit edge distance. see:

bellman ford worst case

Improvements(Bellman Ford algorithm)
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to embed Pearson distance into Euclidean space
I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time and too slow. Ideally I would like to be able to perform efficient approximate nearest neighbour searches instead.

If I could embed the vectors into Euclidean space then I could use standard tools to do this.

> Is there a way to embed vectors from a space using the Pearson distance into Euclidean space?

# Answer
> 2 votes
Yes. Normalize the vectors, then use the Euclidean ($L\_2$) distance.

In particular, map the vector $v=(v\_1,\dots,v\_n)$ to the vector

$$\tilde{v} = ((v\_1-\mu)/s,\dots,(v\_n-\mu)/s)$$

where $\mu=(v\_1+\dots+v\_n)/n$ is the mean of the elements and $s=\sqrt{(v\_1-\mu)^2 + \dots + (v\_n-\mu)^2}$. (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\dots,1/\sqrt{n})$.) Then the vector $\tilde{v}$ has unit length.

Now the Pearson distance $d\_P$ satisfies

$$d\_P(u,v) = 1 - \tilde{u} \cdot \tilde{v} = \\|\tilde{u} - \tilde{v}\\|^2 / 2,$$

where $\\|\cdot\\|$ is the Euclidean ($L\_2)$ norm. (See here and here for a derivation of the above equation.)

Thus, minimizing the Pearson distance between $u,v$ is equivalent to minimizing the Euclidean distance between $\tilde{u},\tilde{v}$. So once you've mapped vector $v$ to its embedding $\tilde{v}$, you can use a standard nearest neighbor data structure (with Euclidean distance) to answer nearest neighbor searches.

---
Tags: nearest-neighbour, euclidean-distance
---


# Question
Title: Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)
I'm stuck with another homework question - "Design an NFA with $n$ states such that the corresponding equivalent DFA constructed using the subset-construction method has less than $n$ states."

What I have learnt is that using subset (or powerset) construction, you can convert a given NFA with $n$ states to it's equivalent DFA with atmost $2^n$ states. I've tried constructing NFA's and tried converting them to check their equivalent DFA's number of states, with multiple attempts, but in vain.

DFA with less states than NFA

The above question tackles the possibility of a DFA having less than equivalent states to it's corresponding NFA. The question, as mentioned in some comments, doesn't take into account the fact that a DFA can have multiple equivalent NFAs, and also suggests the solution of having unreachable states to solve the problem.

Now, this does offer a solution to my homework problem, as the given problem doesn't specify that I shouldn't use unreachable states. Regarding epsilon moves, I believe my professor mentioned not to use them, if not said in the question, or indicated as an option to use, in the given question. Regardless, I can solve my problem by adding unreachable states. But that is not my question, here.

My question is, given an arbitrary NFA with $n$ states, to begin with. (without $\epsilon$ moves or unreachable states). Is there any specific case, where the NFA (please provide an example) under said conditions is such that I can use subset construction and get a DFA with less than $n$ states?

# Answer
Consider an automaton with $n$ states, all final, and a transition between every pair of states for every symbol.

There are two variants of the subset construction. A "formal" one where always $2^n$ subsets are considered, and a "practical" one, where you consider only states that are reachable. Of course only the latter interpretation of subset construction will work.
> 2 votes

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


# Question
Title: Moving an edge in a weighted tree to maximize longest path length
Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A *move* of an edge $\\{u,v\\} \in E(G)$ is the operation of deletion of $\\{u,v\\}$ and the addition of a new edge $\\{x,y\\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.

Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:

The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.

One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.

My question is the following: could we do better than brute-forcing all possibilities?

# Answer
Hints:

When you remove an edge from the graph, you split it into two trees.

Given a tree, can you find the longest path in that tree? (It's not hard.)

Given two trees, can you find which edge to add to make the longest path in the resulting graph as long as possible? (Hint: first find the longest path in each of the two trees. Then..)

This is your exercise, so I'll let you take it from here. That should give you plenty to work with.
> 3 votes

---
Tags: graphs, optimization, discrete-mathematics
---


# Question
Title: Turing machine that accepts L = {#a != #b}
Trying to figure out how to make a deterministic single-tape Turing machine for the language of words comprising as many $a$'s as $b$'s.

I am very confused, because I can't figure out how I would keep track of how many $a$'s and $b$'s there would be. The method for finding $a^nb^n$ goes right and back left to do this but this language would include things like $abaaaababab$.

How can I keep track of number of $a$'s and $b$'s?

# Answer
> 4 votes
You dont need to keep track of them. At each iteration you have three possibilities. Either you first see an A, or a B or a nothing. If nothing accept. If an A first, replace it with some special character and search for a B. If you see one replace that one as well with some special character go back to beginning but if you dont just reject. Do the same for B first. After you cross our 2 characters loop back to beginning. It is actually very similar to $a^nb^n$.

The TM design should be straightforward actually. Similar to $a^nb^n$ but considers $b$ first option as well at each iteration.

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


title: Which definition of PRFs is correct?

text:
# Question
Title: Which definition of PRFs is correct?
Assume the $\mathcal{F} = \\{\\, f\_{s} \\,\\}\_{s \in \\{\\, 0,1 \\,\\}^{\*}}$ be a family of computable functions, where $f\_{s} \colon \\{\\, 0,1 \\,\\}^{|s|} \rightarrow \\{\\, 0,1 \\,\\}^{|s|}$.

Let $F\_{n}$ be a distribution of functions $f\_s$ where $s$ is uniformly distributed over $\\{\\, 0,1 \\,\\}^{n}$, and let $RF\_n$ denote the uniform distribution over the set of all functions from $\\{\\, 0,1 \\,\\}^n$ to $\\{\\, 0,1 \\,\\}^n$.

So, $F\_{n} = f\_{\\{\\, 0,1 \\,\\}^{n}}(x)$ for a fixed $x \in \\{\\, 0,1 \\,\\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left\[ A^{F\_{n}}\left( 1^{n} \right) = 1 \right\] - \Pr \left\[ A^{RF\_{n}}\left( 1^{n} \right) = 1 \right\] \right\vert \< \varepsilon \left( n \right)$$

This definition is seems correct, but it implies that $A$ can ask the query of $f\_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

How about let $F^{\prime}\_{n}$ be distribution of functions $f\_s$ whose input $x$ is uniformly distributed over $\\{\\, 0,1 \\,\\}^{n}$ with any fixed $s$, and let $RF^{\prime}\_n$ denote the uniform distribution over the set $\\{\\, 0,1 \\,\\}^n$.

So $F^{\prime}\_{n} = f\_{s}\left( \\{\\, 0,1 \\,\\}^{n} \right)$ for a fixed $s \in \\{\\, 0,1 \\,\\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left\[ A^{F^{\prime}\_{n}}\left( 1^{n} \right) = 1 \right\] - \Pr \left\[ A^{RF^{\prime}\_{n}}\left( 1^{n} \right) = 1 \right\] \right\vert \< \varepsilon \left( n \right)$$

This definition implies that $A$ can ask the query of $f\_{s}$ for a fixed key $s$ at most $poly(n)$ times.

Is the first definition is correct? Why not choose the another one?

Or even they are both wrong, $F\_{n} = f\_{\\{\\, 0,1 \\,\\}^{n}}\left( \\{\\, 0,1 \\,\\}^{n} \right)$?? It makes me confused.

# Answer
> 2 votes
> So, $F\_{n} = f\_{\\{\\, 0,1 \\,\\}^{n}}(x)$ for a fixed $x \in \\{\\, 0,1 \\,\\}^{n}$, right?

Nope. That's not right. Consider the set of functions $\\{f\_s : s \in \\{0,1\\}^n\\}$. According to what you have written, $F\_n$ is a random variable that is drawn uniformly at random from that set. (I find this a confusing choice of notation, but I'm going with your proposed definitions.)

> This definition is seems correct, but it implies that $A$ can ask the query of $f\_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

Actually, what it means is that $s$ is the same for every query, but $x$ can be different for each query. Yes, $A$ can only ask polynomially queries -- that's a crucial restriction.

> How about let $F\_{n}$ be distribution of functions $f\_s$ whose input $x$ is uniformly distributed over $\\{\\, 0,1 \\,\\}^{n}$

First off: Please don't redefine the meaning of existing notation. $F\_n$ was already defined to mean something else. Don't define it to mean two different things in two different parts of your post. That's just confusing.

Second, that definition doesn't make sense. There's nothing such thing as a function whose input is uniformly distributed over something. That doesn't make sense. A function is a function; its a mapping from inputs to outputs. You don't get to specify an input distribution; a function is whatever it is. Think of a function as a truth table -- there's no way to specify an input distribution, as that's not part of the definition of a function.

---

I suggest finding a textbook on theoretical cryptography -- e.g., Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell -- and follow the definitions there. I wouldn't recommend relying upon Wikipedia for definitions or to learn from.

---
Tags: pseudo-random-generators
---


# Question
Title: Conversion of ambiguous left recursive grammar to LL(1)
I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\\{V\_N, V\_T, S, \Phi \right\\}$, with the non-terminal set $V\_N = \left\\{S\right\\}$, terminal set $V\_T = \left\\{\underline{o}, \underline{l}, \underline{r}, \underline{i}\right\\}$, start symbol $ S $ and the production rules in $\Phi$:

$$ \begin{equation}\begin{split} S \rightarrow & \ S \underline{o} S \\ S \rightarrow & \ S \underline{l} S \underline{r} \\ S \rightarrow & \ \underline{i}\end{split}\end{equation}$$

I have tried the standard tricks like left factoring, left recursion removing, which lead to an infinite transformation loop. Trying to fix first and follow set clashes also did not help. Here are some results after applying the transformations:

$$ \begin{equation}\begin{split} S \rightarrow & \ \underline{i} A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ S A \\ A \rightarrow & \ \underline{o} S A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ \underline{i} \\ A \rightarrow & \ \underline{l} S \underline{r} A & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{o} S \\ A \rightarrow & \ \epsilon & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{l} S \underline{r} \end{split}\end{equation} $$

However I go about the problem, I cannot seem to get even close to eliminating the double entries in my LL(1) table.

# Answer
> 1 votes
I don't want to do your homework, but the two insights that appear to solve it for me are:

1. What the first rules

$S \rightarrow SoS$

$S \rightarrow SlSr$

say is that whatever else $S$ can be rewritten to (which, in this case, is just $i$) can be followed by any number of occurrences of $oS$ and $lSr$ arbitrarily often.

2. If we introduce a nonterminal for that (the part that follows the $i$), left-factorized rules for it follow immediately.

---
Tags: formal-languages, formal-grammars, parsers, left-recursion
---


# Question
Title: What is the name for the comparison used in C's memcmp?
The C `memcmp` function (and `strcmp`) does a comparison similar to the function below for comparing integers:

```
int compare(const int a, const int b) {
     if (a > b) return 1;
     if (b > a) return -1;
     return 0;
}

```

Microsoft information for their `strcmp` says:

> The strcmp function performs an ordinal comparison of string1 and string2 and returns a value that indicates their relationship.

The manual of GNU's libc describes the comparison in this way:

> Your comparison function should return a value the way `strcmp` does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater".

But doesn't define any name for this comparison type.

What is the name for this comparison algorithm?

And why doesn't `memcmp` simply return say 0 if a and b the same and 1 otherwise?

# Answer
The question is about a three-valued function in a situation where a boolean is often used (eg \<=). I personally refer to this as the sign or signum: the sign of the difference of the comparands. However I have not seen a widely-used term; the best supportable answer I can give is that there is none.

In Quicksort, when a three-way partition (based on this "signum") is used instead of two-way, it's called ternary (and there are ternary search trees based on the same distinction), but that's about as specific as it gets.

My reasoning behind my naming this quantity signum is that comparison is often implemented as subtraction; the CMP instruction is essentially a SUB instruction that discards the actual result but retains the sign and zero flags.

Strings are obviously not numbers, but they have a commonly-used embedding into \[0,1) that makes lexicographic comparison equivalent to subtraction and signum extraction.

As to the idea of a two-valued (==, !=) predicate, there is some precedent for this idea in contexts where the signum may not be obtainable. Fagerbergh, Pagh et al. construct what they call a "unordered trie" on hashed string values, where the original order of the strings is obscured due to hashing, but the position where they first disagree is still known. This practice also has some use in applying collations, where only the branching character needs to be looked up to get the collated order (the equal prefix is skipped).
> 3 votes

# Answer
You said:

> And why doesn't memcmp simply return say 0 if a and b the same and 1 otherwise

As the comparison of two numbers or strings has three states, we should specify the state of the comparison. The statement is correct when we are seeking about the equality not the comparison in general term.
> 1 votes

---
Tags: terminology, comparison
---


# Question
Title: create large data sets for machine learning
I am trying to research a new topic using machine learning. The problem is, I have a very small dataset, consisting of 5 months of data. I have been told that my dataset is too small. I want to know if there is any way of making my dataset larger, using an automated tool/algorithm I can implement fast, and more than that, if it is a good idea.

My dataset contains also months with peculiar data (or outliers) and they have cases from generic and standard to unexpected data.

I mention that I have already searched for similar datasets on the available websites. The dataset I am interested in it's about personal budgets, incomes, expenses, consumer behavior.

# Answer
> 1 votes
I know nothing about machine learning, so take the following with a pinch of salt. (I originally posted it as a comment and was encouraged to repost as an answer, so I guess it can't be terrible.)

You get more data by, well, collecting more data...

Simply using some algorithm to generate more data similar to the data you already have won't help, because it doesn't change the distribution of the data, so doesn't do anything to address the problem that your data might not be representative of reality. For example, suppose I make a crappy painting (I can't paint at all) and I ask ten people from my family and close friends if it's any good. They all say, "Yes, David, it's wonderful" because they don't want to hurt my feelings. If you advise me to ask more people's opinion, that's because you feel that I didn't get a proper variety of opinions. Just asking the same ten people again won't change anything: it'll just make me more confident in my bad data because now "twenty" people have told me that my crappy painting is wonderful.

Ultimately, the same problem applies to any algorithmic approach: the best it can do is to generate more data like the data you already have, but that can't possibly have higher quality. And note that any algorithmic approach is, essentially, "use machine learning to generate more data like the data I already have, and then use machine learning to do X with all that data" so it can't be any better than just using machine learning on the original dataset.

# Answer
> 1 votes
There is no way around collecting more data if you want to **increase your test set** and thus how meaningful your benchmark results are.

If you, however, are worried that your training set is too small, then there are two main ways to deal with that: **Data augmentation** which adds invariant transformations to the data (e.g. see Analysis and Optimization of Convolutional Neural Network Architectures, B.2 on page 80 for techniques used in Computer Vision) and **using more restricted algorithms** (e.g. smaller neural networks, linear regression).

Also, **k-fold cross validation** is a way to deal with very limited datasets.

---
Tags: machine-learning, data-sets
---


# Question
Title: Loop invariant condition IsPrime program
I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization. My intuition is that as a loop invariant condition we need i in the range \[2,floor(sqrt(n))\] and then n mod i !=0 implies n is prime

```
bool IsPrime(int n)
{
    if (n == 1) return false;
    if (n == 2) return true;

    //if n (>2) is prime, it's prime factor is just n
    //if n (>2) is not prime, n=a*b, where both a,b<n and we have either a<sqrt(n) or b<sqrt(n)
    var bound = (int)Math.Floor(Math.Sqrt(n));

    //invariant: 2<=i<=bound and n mod i=0
    int i = 2;
    while (i<=bound)
    {
        //if n is divisible by some integer smaller than the upper bound it is not prime
        if (n % i == 0)
        {
            Console.WriteLine(" " + n/i);
            Console.WriteLine("x" + i);
            return false;
        }
        i+=1;
    }
    return true;
}

```

Could you please tell me if that is enough? I already made many attempts and that's the only statement that holds true for the whole loop until i=floor(sqrt(n)).

# Answer
The condition $2 \leq i \leq \lfloor \sqrt{n} \rfloor$ is a reasonable part of the invariant you seek. As I think you realize, this is not enough.

You proposed to also require $n \\!\\!\\!\mod i \neq 0 \implies n$ prime, but this can not realistically hold. For instance, take $n=3^2=9$: running the loop we would start from $i=2$ and have $n \\!\\!\\!\mod i = 1 \neq 0$ but clearly $n=9$ is not prime, which makes the condition false. Hence, that is not really an invariant.

What we need is something expressing "we checked all the numbers from $2$ to $i-1$, and we did not find any divisors". This can be written as "for all the numbers $k$ such that $2\leq k \< i$, we have $k\\!\\! \mod n \neq 0$".

That might be enough, but the loop seems to have a bug to me: for e.g. $n=5^2$ we never try to divide for $i=5$, consequently returning that $25$ is prime. Perhaps you should fix the bug first, and then adapt the first "range" invariant accordingly.
> 2 votes

---
Tags: correctness-proof, loop-invariants
---


# Question
Title: Status questionis for whether a machine can or can't "think"
In his paper Computer Machinery and Intelligence, Turing addresses some arguments against the ability of a computer to pass the Turing test, such as the Theological Argument, the Mathematical Objection and the Argument from Consciousness. I wonder what is the current status of this debate; are there strong counterarguments for Turing's objections? Moreover, what is the most relevant bibliography on this topic?

# Answer
EWD898 might be an intersting starting point.

> The Fathers of the field had been pretty confusing: John von Neumann speculated about computers and the human brain in analogies sufficiently wild to be worthy of a medieval thinker and Alan M. Turing thought about criteria to settle the question of whether Machines Can Think, a question of which we now know that it is about as relevant as the question of whether Submarines Can Swim.
> 1 votes

---
Tags: artificial-intelligence, turing-test
---