title: Variants of the 3-SUM problem

text:
# Question
Title: Variants of the 3-SUM problem
The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there are are three arrays $X,Y,Z$, and we have to find a number per array $a\in X, b\in Y, c\in Z$ such that $a+b+c=0$. Call the first variant 3SUMx1 and the second one 3SUMx3.

**Given an oracle for 3SUMx3, can we solve 3SUMx1 in linear time**?

One option that comes to mind is just to create 3 replicates of the input array $S$ and run: 3SUMx3($S,S,S$). However, this may return two copies of the same item. E.g. if $S$ has only two elements, 1 and -2, then the 3SUMx1 problem has no solution, but 3SUMx3($S,S,S$) will return the fake solution $(1,1,-2)$.

I currently have a solution but it is not linear. To explain the solution, consider first the simpler problems 2SUMx1 and 2SUMx2, in which we only look for two numbers $a+b=0$ in either one array or two different arrays. Given an oracle for 2SUMx2, the problem 2SUMx1 can be solved in the following way.

Let $n$ be the number of elements in the input array $S$.

```
For i = 1 to log(n):
  Partition the array S to two arrays, X and Y, based on bit i of the index. I.e.:
    X contains all elements S[k] where bit i of k is 0;
    Y contains all elements S[k] where bit i of k is 1.
  Run 2SUMx2(X,Y)
  If there is a solution, return it and exit.
If no solution were found for any i, return "no solution".

```

This algorithm works because, if there are two different items, $a,b\in S$, whose sum is 0, then their index must have at least one bit different, say bit $i$. So, in iteration $i$ they will be in different parts and will be found by 2SUMx2($X$,$Y$). The time complexity is $O(n \log n)$.

This algorithm can be generalized to 3SUM by using trits instead of bits, and checking all possible pairs of them. The time complexity is therefore $O(n \log^2 n)$.

Is there a linear-time algorithm?

# Answer
> 8 votes
## Randomized algorithms

If you'll accept a randomized algorithm, yes, it can be done in linear time. There's a randomized algorithm whose expected running time is $O(n)$, and where the probability that it takes longer than $c \cdot n$ time is exponentially small in $c$.

Here's the idea. Randomly permute the entries of $S$, then split it into three equal-sized pieces, each of length $n/3$: let $X$ be the first one-third, $Y$ the second one-third, and $Z$ the third one-third. Now call 3SUMx1(X, Y, Z). If this finds a solution, you have a solution to the 3SUMx3 problem. Moreover, I claim that if there is a solution to the 3SUMx3 problem, then with probability at least $6/27$, this procedure finds a solution. Therefore, the expected number of times you have to repeat it (before finding the first solution) is constant.

The running time of each iteration is $O(n)$, and you do a constant number of iterations (on average), so the total expected running time is $O(n)$. The probability that you fail to find a solution after $k$ iterations is $(21/27)^k$, which is exponentially small in $k$.

Where does $6/27$ come from? Suppose there's a solution to the 3SUMx3 problem, say, $S\[i\]+S\[j\]+S\[k\]=0$. What is the probability that $i,j,k$ all come from different thirds of the array? This probability is $3!/3^3 = 6/27$. So, if a solution to the 3SUMx3 problem exists, then each iteration of the above procedure has at least a probability $6/27$ of finding it.

## Deterministic algorithms

What about a deterministic algorithm? I don't have a specific proposal in mind, but I feel like it's plausible that this construction could be derandomized.

For instance, to give you an idea of the sort of thing I'm talking about, suppose we split the array into thirds once (deterministically). Suppose there exists a solution $S\[i\]+S\[j\]+S\[k\]=0$. Then there are $3^3=27$ cases for which third each $i,j,k$ falls into. After you remove symmetries, there are only $1+6+3$ cases:

* Type A (1 case): All three indices fall in different thirds.
* Type B (6 cases): Two of the indices fall into the same third, and the other index falls a different third.
* Type C (3 cases): All three indices fall into the same third.

You can test for a type-A solution in $O(n)$ time, with a single invocation of the oracle: 3SUMx1(X, Y, Z). Also, you can test for a type-C solution by making three recursive calls to the same solution (one on X, one on Y, one on Z). This leaves only the question of how to test for a type-B solution. It seems like you might also be able to test for a type-B solution using a similar recursive algorithm, though I haven't tried to work out the detailed case analysis. It seems not impossible that perhaps some ideas along these lines could lead to a deterministic algorithm -- though I haven't worked out the details and I'm just speculating at this point.

# Answer
> 1 votes
My paper (Reducing 3SUM to Convolution-3SUM, to be published in SOSA 2020) studied a relevant version of your problem. Basically the result we get is we can solve 3SUMx1 deterministically with the same deterministic running time as for 3SUMx3. (However this does not directly give any results in your oracle description.)

# Answer
> 0 votes
My original post regarding a variant of the 3SUMx3 problem was in error. However, I believe I was in the right path and have edited the post with a new algorithm.

Let's say we have a set S which needs to be split into 3 sets such that we can then run the 3SUMx3 algorithm on it. Also let's assume that the entries in S form an alphabet of range (0, M\] such that for some a, b, c in alphabet M, a + b + c = M, aka 0 (and M % M = 0).

So for numbers from 0 - 256, we would have 64 + 64 + 128 = 256 = 0.

I propose we sort the entries in set S and put them into three buckets with the following ranges. X = (0, M/3\] Y = (M/3, M/6\] Z = (2M/3, M\].

The property of the sets is such that, sum of any three elements within set X would not equal to M since they are all less than a third of M.

Any element in set Y can be expressed as M/3 + an equivalent element from set X. Consequently sum of any three elements from set Y would also never equal M (aka 0). For some a1, b1, and c1 from set Y, a1 + b1 + c1 = 3\* M/3 + (a + b + c) where a, b, and c would be some elements from set X. Since (a + b + c) cannot equal M (aka 0), a1 + b1 + c1 cannot equal 0.

The same can also be said about elements from set Z. Elements a2, b2, c2 being from set Z, it can be said that a2 + b2 + c2 equals 3 * 2M/3 + (a + b + c) where a, b, and c are elements from set X and thus a2 + b2 + c2 cannot equal M (aka 0).

So with these three sets as defined, if we were to run the 3SUMx3 algorithm on sets X, Y, and Z, I theorize that we would be able to definitively know if we have a solution.

Does that sound correct ? comments ?

---
Tags: algorithms, reductions, discrete-mathematics
---


# Question
Title: Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs
Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...

# Answer
The question shows several misconceptions. I'll try to clarify the key aspects.

If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it *must* halt in infinitely many cases.

A TM halting on infinitely many cases does not imply that the recognized language is decidable. (I'm unsure about why you think this would be the case, it would make the halting problem decidable, for instance.)

There is no such a thing as an uncountable language, at least in a conventional setting where the alphabet is countable, and words have finite length. Hence, a TM can never halt on "uncountably many" words.
> 0 votes

---
Tags: formal-languages, turing-machines, automata, undecidability, halting-problem
---


title: Multivariate polynomials

text:
# Question
Title: Multivariate polynomials
Given a Diophantine equation $p(x\_1,x\_2,...,x\_n)$,

Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}\_e)$?

$\mathbb{N}\_e$ is the set of even numbers.

So I have to find a manipulation of $p$ such that I only have even numbers as solution.

How can I do this? Unfortunately I have no Idea.

# Answer
> So I have to find a manipulation of $p$ such that I only have even numbers as solution.

Not so. You have to find a manipulation of $p$ such that *if* you can find a solution / all the solutions of the manipulated $p'$ in even numbers, *then* you can find a solution / all the solutions of $p$. That's a *very* different problem.
> 1 votes

# Answer
How about $p(x\_1/2,x\_2/2,...,x\_n/2)$? For example, if we had $x\_1^2+x\_2^2=5$, we will have $\dfrac{x\_1^2}4+\dfrac{x\_2^2}4=5$.
> 0 votes

---
Tags: complexity-theory, reductions, diophantine-equation
---


# Question
Title: Hash function to return only positive number from integer
What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative numbers with some positive value so I can use them later.

UPDATE: (summary) I need to find a bijection $f: \mathbb{Z}\to\mathbb{N}$ which also has the property that: $$ f(x) + f(y) = f(x + y) $$

# Answer
From your comments, it appears all you need a bijection from $\mathbb{Z}$ to $\mathbb{N}$ that is easy to compute.

The simplest one I can think of: $x \mapsto 1/2 + 2 \mid\\!(x - 1/4)\mid$.

This isn't really a hash function: it doesn't "hash" (scatter its consecutive function values across their range).
> 2 votes

# Answer
Hint: map the positive numbers to the odd numbers and the negative numbers to the even numbers.
> 1 votes

---
Tags: hash, hashing
---


# Question
Title: Prof Knuth's MIX computer - Card Reader and illegal characters
I'm reading through Knuth's "The Art of Computer Programming" volume 1 (3rd edition), with the goal of understanding the complete workings of his hypothetical MIX computer in order to implement MIX in software. Needless to say this is a long term project! (I'm not in college or anything, just an amateur CS enthusiast doing this for fun, I have no Professors to ask!)

In Section 1.3.1 (onwards) of "The Art of Computer Programming" Prof Knuth describes in detail his MIX computer and its IO devices such as Tape, Drum and Card Readers. The main Text does not describe the "bootstrapping" process for this machine, but Exercice 26 *does*.

There is one particularly onerous limitation of the Card Reader described in Exercise 26 -- that is certain characters are not allowed to be written to or read from Cards.

To me this is an important point because if this "illegal characters" limitation does apply to the MIX proper, then I cannot see any easy way to write a MIX program by hand without constantly stumbling over illegal characters. The CMPx operators are explicitly forbidden by Ex 26 for instance.

If I was to attempt to implement MIX myself in software I would find it very convenient to ignore this "illegal characters" limit and just indiscriminately accept all characters without error. Although in my mind this gives me some doubt as to whether my implementation would be "compliant" with Prof Knuth's MIX spec. Accepting "illegal" characters would also make creating a MIXAL assembler a lot easier.

**Questions:**

1. Am I to understand that concepts discussed in the Exercises are not formally part of the MIX specification?
2. It seems arbitrary to add such a tricky obstacle, is this rather severe limitation ***only*** supposed to be true within the scope of Exercise 26 or should it be understood that it applies to the formal specification of the MIX computer throughout the entire TAOCP book set?

# Answer
> 2 votes
I imagine the concepts developed in the Exercises are meant to be formally part of the MIX specification, but there will also be some degree of arbitrariness.

For example, the MIX character set of $56$ characters supports only upper case text, but also includes three Greek characters ($\Delta$, $\Sigma$, $\Pi$) and an arbitrary selection of punctuation characters (no '%', '?', '!' or '^'; '/' but no '\\').

Similarly, the restriction on allowed characters in the card reader is probably just to make the point that not all input devices will support the full character set. Knuth may have regarded the typewriter terminal (which presumably *does* support the full character set) as the main input for program instructions, and may have seen the card reader as primarily for data input.

I think you can make your MIX implementation a completely faithful implementation or a looser interpretation of the original specification - it is your choice.

---
Tags: simulation
---


# Question
Title: Time complexity of kruskal using array data structure
I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps:

1. Sort the edges as per there edge weights. O(ElogE)
2. And then select edges one by an check by the union and find algorithm if they form a cycle or not. Time for this step for the single edge will be O(logv) so for E edges it will be O(ElogV).

Time complexity according to this implementation is O(ElogE)+O(ElogV)

For Desnse graph E=O(V^2) so time is O(ElogV^2) + O(Elogv) = O(Elogv)

But now the question is How to implement Kruskal using array data structure. From above algorithm step, 1 will remain the same So time for sorting edges will be O(ElogE)

But how to implement the second step using array data structure without using Disjoint-set data structure?

If I store each set of disjoint set in an array then the second step will take O(V) time for each edge. So total time will O(EV) for the second step. So total time for Kruskal using array data structure will be O(ElogE)+O(EV).

But questions in the below link does not have this option where I am wrong in above steps?

https://gateoverflow.in/92864/kruskals-mst

# Answer
Here is the original question encountered by the OP, quoted here so that readers do not have to register to that website just to take a look at the question.

> Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?
> a.) E+ElogV
> b.)VlogV
> c.)V^2
> d.)Vlog^2V

**The only correct answer as I see is, the original question is ill-posed.** It is ill-posed because of its unconventional, ambiguous, almost meaningless use of "using array data structure".

Array is such a fundamental data structure, it usually converys little information when you say an algorithm is implemented using array data structure. Especially in the current case of Kruskal's algorithm, we usually refer to the disjoint-set data structure used in the algorithm to keep track of which vertices are in which connected components and to determine whether an edge will join two different connected components. In fact, the whole page about Kruskal's algorithm in wikipedia does not mention "array" even once. Although well versed regarding to minimal spanning tree and Kruskal's algorithm\[\], I am confused by this "using array data structure".

Let us also take a look at other aspects of the original question. It has bad capitalization, bad punctuation, and inconsistent white spacing. It introduces "$e$ edges" but use $E$ in the choices. When it lists the time complexities, it should apply the big $O$ notation such as $O(E+E\log V)$. It skips the basic description of the graph as connected edge-weighted.

All in all, it is fair to say the original question is of such a low quality, you should just ignore it. Try not to learn from it.
> 1 votes

# Answer
the time complexity for sorting edges wt wise is ElogE and then
while adding each edge you have to check for cycle the corresponding time complexities will be like ... 1(for detecting cycle after adding 1st edge in mst ) + 2( detecting cycle after adding 2nd edge) +3..........+(v-1). = O(v^2) hence total time complexity is ..... ElogE +V^2 = Elog E + E as V^2 is almost equal to E.

hence time complexity is ELogE
> 0 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, minimum-spanning-tree
---


title: Water Jug Problem in AI

text:
# Question
Title: Water Jug Problem in AI
In AI we can classify a problem in 3 classes, **ignorable, recoverable** or **irrecoverable** problems. Now while reading Water jug Problem

I am wondering in which of these 3 class it should fall? It should reside under **recoverable** right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?

# Answer
> 18 votes
**Recoverable**, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:

```
[12, 0, 0]
[4,  8, 0]
[4,  3, 5]
[9,  3, 0]
[9,  0, 3]
[1,  8, 3]
[1,  6, 5]
[6,  6, 0]  # <-- SOLVED; 7 steps

```

---

**DETAILS**: The problem stated *as-is* is recoverable, and in a machine learning problem statement, we take the problem *as-defined*, not how it *could be* defined. For any # of jugs of any sizes, as long as we start with *only one jug filled*, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.

```
[0, 0, ..., X,   ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?,   ..., 7] <-- some arbitrary state
...
[0, 0, ..., X,   ..., 0] <-- RECOVERED; empty all other jugs into original jug

```

**Update**: the system is also recoverable if starting with any # of jugs filled, *as long as they're fully filled*. They also don't *necessarily* have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.

---

**DEFINITIONS**: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:

* **Recoverable**: state `t0` can be restored from any other state `T` when starting at `t0`
* **Irrecoverable**: there exists some state `T` we can get to from `t0`, but no longer revert to `t0`
* **Ignorable**: we don't care, and can solve the problem at hand either way

---

**Irrecoverable example**: `[0, 1, 2] --> [0, 0, 3]`. Goodbye forever, 1 liter & 2 liters.

---

**Ignorable example**: goal: two jugs empty. In this case, both the original `[12, 0, 0]` and the irrecoverable case `[0, 1, 2]` work.

# Answer
> 7 votes
I couldn't in a quick Google through the textbooks tell whether recoverability requires immediate, single-move recoverability (ctrl-Z-style) with each undo step being O(1) complexity, and which can be implementable as a sequence of moves in a push/pop stack. They always use guaranteed-single-move-undo examples (8-puzzle, Towers of Hanoi) for their recoverable examples, and always chess for their irrecoverable example.

Textbooks never describe the interesting cases :(

If our criteria for recoverability requires single-move-undo, then it's easy to think of an example where **it is not recoverable in a single move**:

(1,8,3) -\> (0,8,4) cannot be undone in a single move (or pour).

If recovery can be multi-move, then (0,8,4 -\> (some magic steps here) -\> 1,8,3) gives recovery in multiple pours. However, this recovery path requires solving a path to recovery, which is sort of putting the cart before the horse: to undo a step towards solving the problem, we have to first solve the problem!

But in the example given, we can always guarantee that we can regain a previous position by doing: rightmost jug to leftmost jug; center jug to leftmost jug (thus returning to the initial condition); repeat all steps from the start until we get back to the desired recovery step. This does require that we store all moves made, though; but I think that would likely be the output of most answers anyway, so may be considered OK?

It seems intuitively obvious that we can't, through any sequence of moves, get to a position that we can't duplicate by repeating that set of moves from the initial condition. So **the problem as given is recoverable**, though we can't just implement it as a push/pop stack: while that's all we need for write, we need to be able to iterate it for reading.

More importantly, this makes undo an O(N+2) operation, instead of an O(1) operation. For most problems, we can just hit the reset button and replay in O(N), so we really gain nothing from doing this. Unless initial setup is prohibitively expensive for some reason, we'll be slightly more efficient if we solve it as non-recoverable, than if we kept replaying the whole thing every time we backtracked. **So the problem given is not worth recovering this way.**

And what if the problem stated instead: "We start with the same jugs, this time containing 9, 1.5, and 1.5 liters." Now we can *never* regain that initial state through any sequence of moves, so **there exist jug problems which are not recoverable**.

I think this makes the class of jug problems as a whole "non-recoverable", but any example we'll ever find in a textbook is likely to be "recoverable but not worth recovering", because textbooks never describe the interesting cases :(

# Answer
> 6 votes
Suppose the leftmost jug had 3 liters, the center jug had 2 liters, the right jug is empty. Suppose you poured the leftmost jug to the center jug. Now the leftmost jug is empty, and the center jug contains 5 liters. At this point you cannot go back to your original state. Consequently, your problem is *irrecoverable*.

# Answer
> -2 votes
In Recoverable method: 12lit. 8lit. 5lit. ( 4 , 8, 0) ( 4, 3, 5) ( 9, 3, 0) ( 1, 8, 3) ( 1, 6, 5) ( 6, 6, 0) //step 6 Splited. In step 6,you can split up the water to give away exactly 6 litres and keep 6 litres

---
Tags: artificial-intelligence
---


# Question
Title: What is the computational power of Parsing Expression Grammars?
Parsing Expression Grammars were introduced by Bryan Ford in *Parsing Expression Grammars: A Recognition Based Syntactic Foundation.*. Wikipedia says that it is an open problem to provide a Context Free language that can not be recognized by a PEG.

I am trying to understand the results from this paper -- The computational power of Parsing Expression Grammars by Loff et al. However, I am struggling to understand the notation used. What does the `#` mean in the following quote?

> We show that PEGs are computationally "universal". Take any computational function $f: \\{0,1\\}^{\*} \rightarrow \\{0,1\\}^{\*};$ then there exist a computable function $g:\\{0,1\\}^{\*} \rightarrow N$ such that
>
> $\\{ f(x)\\#^{g(x)}x | x \in \\{0,1\\}^{\*} \\}$
>
> has a PEG.

They use a slightly different symbol in Theorem 18.

> $ L = \\{ f(x){⧖}^{g(x)}x | x \in \\{0,1\\}^{\*} \\} \in PEG $

Where they talk about the $⧖$ as the *number of symbols* read (interpretation mine). How do I read this?

Further, can I take this to mean that the question whether a CFL exist that can not be recognized by a PEG is settled?

Essentially, if there exist a PEG for a P complete language, then all other problems in P can be reduced to it. Given that recognizing CFLs are in P, all CFLs should be reduced to recognizing this language.

Note that a similar question was asked by another user three years back, but this is new research.

# Answer
> 2 votes
$\\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.)

$\\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count.

The double-triangle used in the later proof is just another such symbol without special significance.

In response to your second question, the paper seems to be pretty clearly state (on page 4) that the question of whether there is a CFL with no PEG is still open. In particular, it is not known whether the language of even-length palindromes has a PEG, although it is certainly a CFL.

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


# Question
Title: How undecidable is it whether a given Turing machine runs in polynomial time?
The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at cs.SE and cstheory.SE. However, what is different is a footnote, which highlights that proving both $\mathsf{R}$-hardness and $\mathsf{coR}$-hardness seems to be new:

> 1The undecidability of PTime seems to be folklore, but non-semi-decidability seems to be new, even though semi-decidability is a natural property here.

But I want to ignore the question whether this observation is new. What interests me is what is known about the degree of undecidability of PTime. For example, is computation in the limit powerful enough to decide PTime? Are there better lower bounds than $\mathsf{R}\cup\mathsf{coR}$ for the difficulty of PTime?

**Note**: I denote the problem to decide "whether a given Turing machine runs in polynomial time" as PTime here. I know that this is incorrect, because PTime is a class of languages and not a class of Turing machines. However, I found this misuse of terminology convenient for this question.

# Answer
The answer is $\bf 0''$ (and so in particular computation in the limit - which corresponds to $\le\_T\bf 0'$ \- is not enough). And this stronger result is also folklore (I was assigned it as an exercise way back when).

As an upper bound we just check quantifier complexity: $\Phi\_e$ runs in polynomial time iff *there exists* some polynomial $p$ such that *for every* input $n$ we have $\Phi\_e(n)\[p(\vert n\vert)\]\downarrow$ (that final clause only uses bounded quantifiers). So running in polynomial time is a $\Sigma^0\_2$ property.

Now we just need to show optimality. We'll actually show a bit more: not just that the Turing degree is $\bf 0''$, but that the set is $\Sigma^0\_2$-complete. Supposing $$A=\\{x:\exists y\forall z\theta(x,y,z)\\}$$ (with $\theta\in\Delta^0\_0$) is any other $\Sigma^0\_2$ set, we want to reduce $A$ to the set of programs running in polynomial time.

So fix an instance $i$. We'll say *$m$ is $s$-bad for $i$* if $m\<s$ and there is some $n\<s$ such that $\neg\theta(i,m,n)$. Let $t\_i(s)$ be the least $m$ which is not $s$-bad for $i$. Now we'll whip up a stupid program $\Phi\_{e\_i}$ as follows: on input $s$, $\Phi\_{e\_i}(s)$ runs for ${\vert s\vert}^{t\_i(s)}$-many steps and then halts and outputs $0$. The point is that if $i\in A$ then $t\_i(s)$ stabilizes and so $\Phi\_{e\_i}$ runs in polynomial time, and otherwise $\Phi\_{e\_i}$ does not run in polynomial time.

Now the map $\mu: i\mapsto e\_i$ is computable, so we get a many-one reduction of $A$ to our set.

---

As a quick comment, note that we only used one property of polynomial time above: that there is no biggest polynomial time bound. This let us keep pushing up the runtime bit by bit (each time $t\_i(s)$ goes up) while preserving the possibility of still running in polynomial time. By contrast, "halts within seven steps on all inputs" (say) is merely $\Pi^0\_1$-complete. Basically, whenever we have a concrete resource-bounded complexity class with no "maximal bound," being in that class will be $\Sigma^0\_2$-complete. In particular, this applies to NP, EXPTIME, PSPACE, ...
> 2 votes

---
Tags: computability, undecidability, polynomial-time
---


title: No nonfinal states in NFA

text:
# Question
Title: No nonfinal states in NFA
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^\*$.

What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^\*$? Can there be an NFA with no non-final states whose minimal NFA has some non-final state?

---

Oh , no nonfinal states means all are final states. So DFA - all final states means every string gets accepted. So language is $\sum^\*$. For NFA, it need not be $\sum^\*$. Please correct me if i am wrong here. Other case --\> If there are no final states(all non-final states) means in DFA, language accepted is empty language. In case of NFA with no final state means empty language right?

# Answer
> 1 votes
Imagine an NFA with a single state, which is final/accepting. It has no edges.

This NFA accepts the language $\\{\varepsilon\\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.

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


# Question
Title: Performant algorithm to find edges without cross overs
I have a series of graphs with points plotted like this:

Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don't know the starting position sometimes this can result in crossed paths.

I could resolve this with more costly algorithms like 2-opt, but because this is being used in real time graphics it isn't quite performant enough.

It might help to know all of these graphs are mapping slightly deformed ovals and so they will have no intrusions. I basically need something that would act as if a rubber band was placed over the points on a graph.

I feel there's probably a better way to do this rather than relying on generic path optimisation algorithms?

# Answer
> 1 votes
As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).

---
Tags: optimization, shortest-path, traveling-salesman
---


# Question
Title: Can we solve this problem more efficiently than trying all possible combinations
Here is the context of the problem I am struggling with.

I have a set of strings, for example:

```
"my name is john",
"i like cheese",
"what is your name",
"the cheese is in the kitchen",
"john likes cheese"

```

Let $S$ be union of all words appearing in the previous strings. `my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes`

The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :

* Words are separated by a comma.
* The sum of the lengths of selected words is bounded by a constant number (say 25).
* A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.

For example, the combination `john,cheese,like,likes,i` uses 24 characters and allows to rebuild both `"i like cheese"` and `"john likes cheese"`.

Here is what I have tried to implement.

First, I sort every single word by the number of strings it's contained in. In this example:

```
is      (3)
cheese  (3)
john    (2)
name    (2)
my      (1)
i       (1)
like    (1)
what    (1)
your    (1)
...

```

So I'm now using this array: `[is, cheese, john, name, my, i, like, ...]`, let us call it `initial_array`

And here is the idea of the algorithm I amm using. First, I initialize another array of strings containin of all the strings g the first word from `initial_array`, let's call it `new_array`:

`[is]`

Then, while the total length of all the strings of `new_array` plus the commas does not exceed the limit of 25 chars, I append them:

```
[is,cheese] (9)
[is,cheese,john] (14)
[is,cheese,john,name] (19)
[is,cheese,john,name,my] (22)
[is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john"
[is,cheese,john,name,my,i,like] (29) --> up to 25 chars

```

When I reach a length up to 25 chars, I try to replace the last element of `new_array` by the following of `initial_array`:

```
[is,cheese,john,name,my,i,what] (29) --> up to 25 chars
[is,cheese,john,name,my,i,your] (29) --> up to 25 chars
...

```

And when I reach the last word of `initial_array`, I remove it from `new_array` and replace the previous one by the next one of `initial_array`:

```
// if the last word of initial_array is "likes"
[is,cheese,john,name,my,i,likes] --> we reached the last word
[is,cheese,john,name,my,like]
[is,cheese,john,name,my,like,what]
etc...

```

If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the `initial_array`, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.

Thank you for your help.

# Answer
I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, strings
---


# Question
Title: Doubt on Karger's Algorithm for Min-Cuts
I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My doubt is in the 2nd part of the question.

2nd part of the question asks to find the probability of contracting 2 vertices in each step of the algorithm.

My approach is that - Since contracting 2 vertices is equivalent to contracting an edge, because every time we contract an edge, we are contracting 2 vertices into 1, so to answer the question, I can just find the number of edges at each step 'i' in my algorithm and and find the probability.

For example, if the number of edges in step 'i' of my algorithm run is 5, I can say that Probability(Contracting 2 vertices) = 1/5. since we can pick anyone of the 5 edges.

Please help me out in finding if my approach is right or wrong.

# Answer
> 1 votes
The approach is right, however, you are missing a little detail. Karger's algorithm runs on multigraphs. Hence, two vertices can have more than one edge between them and hence, the probability of contracting them the disjoint sum of the probability of contracting any of the edges between them which is the number of edges between them over the total number of edges in the graph.

---
Tags: algorithms, graphs, randomized-algorithms
---


# Question
Title: An example where the algorithm of Hopcroft and Karp performs poorly?
I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I came up with where solved on paper in almost constant number of rounds.

Other questions here in the community targeting this problem tackle the worst-case running time or the time-bound proven in the original paper.

This running time seems to be a bit too loose, especially because the maximum matching problem in general and in bipartite graphs lacks a conditional lower-bound on its running time and I couldn't find any tight lower-bound on the number of needed rounds. I couldn't find a bound on the number of needed operations in constrained models of computing either (For example binary decision tree or so).

On the other side, the $O(\sqrt n)$ bound on the number of rounds from the original paper has not been improved since was found in the 1973 except in the parameterized context and in special classes of graphs.

Any ideas/suggestions are much appreciated :)

# Answer
> 2 votes
I was able to construct a simple example where the algorithm taken literally is easy to trick. The case goes as follows. Given a bipartite graph consisting of a union of simple paths of odd lengths $P\_1, P\_3, P\_5, \dots, P\_{2r-1}$ for some $r \in \mathbb{N}$. Assuming $P\_i = v\_{i,0}, v\_{i,1} \dots v\_{i,i}$ for $i = 2k-1; k \in \[r\]$. The shortest augmenting path in the first iteration has length one (namely any edge in the graph is such a path). Consider the following scenario of the algorithm.

In the first iteration, the algorithm chooses $\left\lfloor \frac{i}{2} \right\rfloor$ edges from each path $P\_i$, namely the edges $v\_{i, 2}, v\_{i, 4}, \dots v\_{i, i-1}$ as a maximal set of shortest augmenting paths. The set is maximal, since any other edge share an endpoint with an edge in the set. However, the matching resulting from these edges admits an augmenting path in each path $P\_i$ of the length $i$. Since all paths have distinct lengths, the algorithm as given in the paper from Hopcroft and Karp augment exactly one path in each phase (in the pahse $j$ it will not look for paths longer than $2j-1$ since an augmenting path of this length exists). In total we need $\Omega(r)$ phases which is $\Omega(\sqrt n)$ with simple math. This bound is tight to the proven bound.

I considered this case trivial, since all augmenting paths are vertex disjoint and instead of looking for maximal set of vertex-disjoint shortest augmenting paths in each phase, we can look for a maximal set of vertex-disjoint augmenting paths with monoton-increasing lengths of the paths. I mean with that, that in each phase, after we run the BFS, we do not stop when a maximal set of vertex disjoint shortest augmenting paths are found, but we look further for (second-shortest) augmenting paths that are vertex-disjoint from what we already found and so on. In this case we would have considered all augmenting paths in the given graph in the previous example in one step.

On the other hand, it is not directly clear how to implement this kind of rounds in linear or almost-linear time from the given implementation of the algorithm in the paper of Hopcroft and Karp.

I was able to go further and construct examples with a bit more complicated structures and the same number of rounds, where we add edges arbitrarily between the middles of these given simple paths or parallel copies of subpaths. Even though, these edges might change the sequence of the algorithm, since they can be chosen at the first round of the algorithm, it is not hard to see that the total number of rounds does not change critically.

On the other hand, dense graphs seem to need less rounds in general. This can also be seen "intuitively" from results proben by Hegerfeld and Kratsch in this paper, which gives more insight about the number of needed rounds.

---
Tags: algorithms, graphs, lower-bounds, bipartite-matching, fine-grained-analysis
---


title: Finding stages in routing algorithm

text:
# Question
Title: Finding stages in routing algorithm
I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently unable to accurately and in reasonable time locate where I can pack my terminals.

In the whole problem, from a connected graph $G$, a node $s$ and a set of nodes $t$ we are looking for a collection of path that have the following properties:

* All elements of $t$ must have a path to either $s$ or an intermediate point. These paths are weighted the sum of their arc distance.
* If an element of $t$ have a path to an intermediate point, there must be between 3 and 5 paths from distinct nodes of $t$ to that point.
* All intermediate points must have a path to the $s$. These paths are weighted the double of the sum of their arc distance.
* We look for an algorithm approaching or computing exactly a minimum weight solution.

Note that because the weight is being proportional to distance, we will admit a minimum weight solution is easily found once the intermediate points, along with the set of $t$ nodes that have a path to it, are know.

For example in this graph I'd expect the algorithm to return me a pack $\\{t1, t2, t3, t4, t5\\}$ on node $p$ because it would be the minimum cost setup:

Total cost here being 7 for routing $t$ points + 6 for routing the intermediate point = 13, much less than if all $t$ were routed to the source (5\*4 = 20) and a bit less than if they were packed at point 3 (5\*2 + 2\*2 = 14)

We need to find as close as possible to the optimal setup, but in our actual datasets, there is usually over 400 terminals, and we can't enumerate all possible partitions of 3 to 5 terminals to compute a routing. How can I efficiently find these intermediate stage routing points (where to "pack" my terminals) ? Is there any existing research or algorithms on the matter ?

# Answer
I don't know whether there is an efficient (polynomial-time) algorithm for this problem. I wouldn't be surprised if it is NP-hard.

One approach would be to formulate this as an instance of integer linear programming, and then apply an off-the-shelf ILP solver to find the best solution it can within some fixed amount of time. This gets awfully ugly. You could introduce a bunch of zero-or-one variables to represent the solution, write down constraints (inequalities) to capture that they are consistent, express the cost of a solution as a linear combination of these variables, and then use the ILP solver to minimize the cost. However, writing down the set of inequalities might get super messy.

Alternatively, it might be possible to apply heuristics for weighted set cover or weighted exact cover to this problem. Given any candidate combination of 3..5 terminals and a candidate location for the intermediate point, you can easily compute the cost of connecting them. Consider this as a "set" that covers those terminals and that intermediate node, and whose cost is equal to the computed cost. There are $n\_1 \times ({n\_2 \choose 3} + {n\_2 \choose 4} + {n\_2 \choose 5})$ many such "sets", where $n\_1$ is the number of internal nodes and $n\_2$ is the number of terminals. This is $O(n^6)$, where $n$ is the number of nodes in the graph. Now the goal is to find a cover, i.e., a subset of "sets" that covers each terminal exactly once and that covers each internal node at most once.

In principle you could then try applying any algorithm for exact cover. However, I suspect this will be far too slow, as there will be a few hundred billion possible "sets" or so.

An alternative might be to apply a heuristic or approximation algorithm for set cover. For instance, consider the greedy algorithm for set cover: at each step, it chooses a set that minimizes the cost of the set divided by the number of terminals that are newly covered by that set and haven't been covered yet (best "bang-for-the-buck"). This gives a solution that is not too much more expensive than the optimal solution.

Moreover, you can implement the greedy algorithm efficiently, without enumerating all sets. At each step, we have already covered some of the terminals and some of the internal nodes, and we want to choose the next set with the best bang-for-the-buck ratio. This seems feasible. One naive way to do that is to iterate over all possible choices for the location of the intermediate point, and for the number $k$ of terminals (3..5), and then find the $k$ closest uncovered terminals to that intermediate point; each gives you a candidate set. Also find the closest uncovered terminal to $s$; this gives you another candidate set (with no intermediate point). Among these candidates, take the one with the lowest bang-for-the-buck ratio and add it to your solution so far. If you precompute all-pairs shortest paths (e.g., with the Floyd-Warshall algorithm), then each step can be implemented in $O(n^2)$ time. You need to do at most $n$ steps, so the total running time will be $O(n^3)$.

This might give a highly suboptimal solution, but it is at least one solution, and it should be relatively efficient with your parameter settings.

Alternatively, it might be possible to use local search or simulated annealing to optimize your solution. The key requirement is to have a way, given a current solution, to find a way to perturb the solution in a random way. The algorithm then tries this many times, hopefully gradually decreasing the cost of the solution over time. In your situation, one way to random perturb a candidate solution is to either (1) randomly pick three terminals that currently aren't part of any pack and merge them into a pack, (2) randomly pick a terminal that currently isn't part of any pack and a pack of size 3..4, and merge them into a single pack, or (3) randomly split a pack of size 4..5 into a pack of size 3..4 and a terminal that isn't part of any pack. You could then try simulated annealing together with such a choice of perturbation (neighborhood relation). There might be smarter ways to choose the perturbation that makes those algorithms more effective.

Maybe someone else will be able to come up with a better approach.
> 1 votes

---
Tags: graphs, routing
---


# Question
Title: Number of concurrent schedules in database
In a database system, say there are $N$ transactions each having $m\_1,m\_2,\dots,m\_N$ operations. How many concurrent schedules are possible?

$(m\_1+m\_2+....+m\_n)!$ is the number of possible interleavings.
Is this number equal to number of concurrent schedules? Serial schedules have to be discarded from the total number?

# Answer
> 2 votes
Number of possible Concurrent schedules are

$$^{m\_1+m\_2+m\_3+...+m\_n}C\_{m\_1}\*^{m\_2+m\_3+...+m\_n}C\_{m\_2}\*^{m\_3+...+m\_n}C\_{m\_3}\*...\*^{m\_n}C\_{m\_n}$$

We need to maintain order of operations of an individual transaction.
Total no of Serial Schedule = n!
Total no of Non-serial Schedule = (Concurrent Schedule - Serial Schedule)

*For Example:* Consider 4 transactions T1,T2,T3 and T4 having 2,2,3 and 4 operations respectively.
Total operations = 2+2+3+4=11
Total no. of concurrent schedules : $$^{11}C\_2\*^9C\_2\*^7C\_3\*^4C\_4 = 69300$$
Out of the 11 possible positions we choose 2 places for T1 and place it operations sequentially , again we choose 2 places for T2 and place its operation sequentially , again we choose 3 places for T3 and place its operation sequentially , The remaining 4 places are used for T4.

# Answer
> 1 votes
First of all let's permute everything; all operations of every transaction. Doing this will result in $(m\_1 + m\_2 + m\_3 + ... + m\_k)!$

Now since we cannot change the relative order of execution of operations within individual transactions, therefore, to remove the permutations of internal operations of transaction $T\_1$,so we need to divide the above expression by $m\_1!$. Same goes for all remaining transactions. Thus we get the expression

$ \dfrac{(m\_1 + m\_2 + m\_3 + ... + m\_k)!}{m\_1! m\_2! ... m\_k!}$

# Answer
> -1 votes
Total number of schedules = (m1+m2+m3+....+mk)! / (m1!\*m2!*m3!*...\*mk!)
Total serial schedules = N!
So, total concurrent schedules = (m1+m2+m3+....+mk)!/(m1!\*m2!*m3!*...\*mk!) - **N!**

# Answer
> -2 votes
Number of Concurrent schedules possible are

$\qquad\displaystyle \frac{(m\_1 + m\_2 + m\_3 + \dots + m\_k)!}{m\_1! \cdot m\_2! \cdot m\_3! \cdot \dots \cdot m\_k!}$

---
Tags: concurrency, databases
---


# Question
Title: Can current quantum computers decide languages that Turing Machines cannot?
I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to reductions got me thinking about all the Quantum Computer craze.

As such my question is as follows

> Does there exist some language *L* that is not decidable by a Turing Machine, but is decidable by a quantum computer?

My hunch is *no*, as from what I understand about Quantum Computers, you can simulate them (albeit slower) using a Turing Machine. However my knowledge of Quantum Computing is limited to a 1.5 hour lecture from Microsoft on YouTube, and I would assume there was a lot more in the way of recent developments that I am not knowledgeable enough to understand

# Answer
No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, is contained in the class of problems solvable by a classical computer in polynomial space, PSPACE.

All this information is from the Wikipedia page https://en.wikipedia.org/wiki/Quantum\_computing
> 7 votes

---
Tags: turing-machines, reductions, undecidability, quantum-computing, church-turing-thesis
---


# Question
Title: Are regular languages and their regular expressions part of computer science?
I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular.

In math discourse there was always the question like "Are mathematics discovered or invented?".
I am quite sure regel-regex is not a mathematical theory but a linguistics theory (even though it was first theorized by a mathematician - Stephen Cole Kleene).

Is regex part of computer science and if so, is it generally accepted as "discovered" or as "invented", and what could be one example of what's being further researched in regards to matching information on a computer document?

# Answer
> 6 votes
There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about.

The three relevant distinctions for this question in my opinion are as follows:

### First

The notion of regular languages and related things like recursive enumerability.

Individual regular languages are isomorphic, (i.e. able to be losslessly transformed to and from,) to deterministic finite automata and reducing something to a regular language demonstrate results about that thing's computablity, so I would argue it is part of computing science.

If linguistics folks find the notion or regular languages useful, however, then we can share it. Human languages are (generally?) not regular languages but something more complex, so I would be surprised if that was the case.

I think most interested people would give the same answer to whether regular languages are invented or discovered as they would about mathematics.

### Second

The particular notation for describing regular languages, in the formal literature, developed by Kleene and others.

This is clearly invented. There's no particular reason we have to have used `*` and `+` in particular to represent those ideas. If you want to assign this notation to one or more fields, I would argue it belongs to any field that publishes papers using it.

### Third

Computer programs which take as input an expression in a language and produce an automata or something resembling one and that result can then be used to perform operations on a different input including search and replace.

The languages these programs define which usually contains some form of the Kleene Star and Kleene Plus, along with several other more complicated but useful constructions, which are generally absent from formal regular language literature to my knowledge. Backreferences would be one example of this. These programs are invented, as are their particular sets of notations. They are also instances of computer engineering rather than computing science per se. Although of course they are building on at least a certain amount of computing science results, and computing science results can be stated about these programs. For example, it is possible to construct regular expressions of this sort that produce exponential running times, and subsets of those notations can be defined where that is impossible.

# Answer
> 2 votes
Regular expressions are at the very core of computer science, conceptually and historically.

Kleene's article in which he introduced them and proved them equal in power to finite automata is one of the foundational articles of computer science. It was the foundation of formal language theory, which was based on its results and its approach; it is an important branch of computer science, a rich body of strictly mathematical theory, the basics of which are taught in all computer science curricula, including the theory of regular expressions. It is devoted to the subject of parsing input, one of the essential problems to address when programming. The techniques we use daily to parse text, both natural language and computer languages, are based on this theory - they may deviate from it, but we need basic insight into the theory in order to know which parsing techniques to apply when.

So yes, regular expressions are a prime example of what computer science is about.

Historically, they were developed in the context of cybernetics and the quest for artificial intelligence: mathematicians at MIT and elsewhere were studying formalisms such as state machines and neural networks, which could exhibit interesting behavior and do such things as recognize patterns of input stimuli. This is why Kleene's article speaks of *nerve nets* and the recognition of *events* (stimuli to the net).

However, the same techniques were applied to the recognition of written natural language; e.g. people such as Noam Chomsky were working on machine translation; they were hoping to create computer systems that could take a Russian text and translate it into English, or vice versa. Chomsky realized that regular expressions weren't powerful enough to describe human language, that the grammars used in linguistics have more descriptive power; this led to the development of the formal (mathematical) theory of grammars and the rest of formal language theory, which were subsequently employed in linguistics (by followers of Chomsky) and in computer science and the daily practice of IT (by all programmers who need to parse input).

# Answer
> 1 votes
Honestly, I don't think the "discovered" vs "invented" is a distinction that matters. If you want to get into that, fine, but it's a matter of philosophy, not science.

To your main point, yes, regular languages are very much a part of computer science because, regardless of their history, they identify a class of computational problems and correspond to a class of computational machines (finite automata). They are also a part of mathematics and of linguistics.

The entire field of information retrieval deals with matching information in text documents.

---
Tags: terminology, logic, regular-expressions, mathematical-programming
---


# Question
Title: Determine shortest path in a 4x5 grid graph
Suppose we had a graph $G = (V,E)$.

This graph can also be seen as a $4x5$ grid graph as shown in the image.

There is a directed edge from $v\_{i,j} \rightarrow v\_{i,j+1}$ for $1 \leq i \leq n$ and $1 \leq j \leq m-1$.

Similarly, there is a directed edge from $v\_{i,j} \rightarrow v\_{i+1,j}$ for $1 \leq i \leq n-1$ and $1 \leq j \leq m$.

What is the most efficient algorithm to determine the shortest path from $v\_{1,1} \rightarrow v\_{n,m}$? My main idea is to use the Bellman-Ford algorithm, but I am clearly not taking advantage of how this graph is laid out. Any guidance would be much appreciated.

EDIT: The edges are weighted and may possibly be negative.

# Answer
Since your graph is a DAG you can topologically sort $V$ and solve your problem via dynamic programming by considering the vertices in reverse topological order.

For each vertex $v$, let $d(v)$ be the distance from $v$ to $v\_{n,m}$. Clearly, if $v = v\_{n,m}$, then $d(v)=0$.

For $v \neq v\_{n,m}$, you have: $$ d(v) = \min\_{(v,u) \in E} \\{ w(v,u) + d(u) \\}, $$

where $w(v,u) \in \mathbb{R}$ is the weight of edge $(v,u)$ in $G$.

Both the topological order of $V$ and all the quantities $d(v)$ can be found in $O(|E|)$ time. Therefore the overall time required is $O(|E|) = O(|V|) = O(nm)$.
> 3 votes

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


title: Special case of the $MST-$ Problem

text:
# Question
Title: Special case of the $MST-$ Problem
I am working on the following exercise:

> Consider an undirected complete graph $G(V,E)$ and positive real numbers $a\_1,a\_2,\ldots,a\_n$. The task is to find a MST with respect to the edge weights $w\_e = a\_ia\_j$ for each $e = \\{i,j\\}$. Provide an algorithm that solves this problem that is as efficient as possible.

It is safe to say that just using Kruskal's or Prim's algorithm will not be sufficient here. So we should use the special structure of $w$. I came up with the following idea:

1. Sort the edges in increasing order according to their edge weights. This can be done in $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time.
2. Traverse the edges, starting from the smallest and add it to $T$ if it contains an unvisited vertex. Mark the newely visited vertices. This can be done in $\mathcal{O}(\lvert E \rvert)$ time.

But this algorithm is not as efficient as possible for it has $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time complexity. The problem here is the procedure in step 1. Could we somehow leave it out?

# Answer
Since the graph is complete, you can connect each vertex with any other vertex. Note that each vertex must be connected to the tree and hence has an incident edge in the tree.

Assuming all weights are positive, choose a vertex $v$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $v$ the center of the star.

Assuming the numbers can be negative (which is not specified in you question), then distinct two cases. the first one, all weights are negative. Hence, it turns into the case above, since all products have to be positive.

The second case is where we have at least one negative weight and one positive weight. Let $u$ be a vertex with the maximum positive weight. Let $v$ be a vertex with negative weight with maximum absolute value among all negative weights. connect $u$ to all vertices with negative weights and $v$ to all vertices with positive weights. Be aware of not adding the edge between $u$ and $v$ twice.

Try to proof the correctness as an exercise. It should be clear using elementary math and an exchange argument.
> 1 votes

---
Tags: graphs, time-complexity, minimum-spanning-tree
---


# Question
Title: Proving that Rice's theorem does not apply to a property
This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic.

The question is about if Rice theorem applies to certain property. For example for a structural property such as number of states. I would argue that:

* The property is decidable through its definition in encoded form.
* The property is irrelevant to the language, because given the same language we can easily find another TM that does not have this property, ie one with empty states, so the property is not a language property, and hence Rice Theorem does not apply, since by definition, Rice theory only applies if it is a non trivial language property.

To me, this seems to be a good argument, but the question is assign a substantial mark of 10, and I feel like this is not enough for 10 marks, am I missing out some rigorous argument that I need to include to make my explanation crystal clear?

# Answer
The answer is right but the argument is not sufficient. Try to build a contradicting example as a proof. Describe how to encode each machine into a binary number (can be found in any tcs book). Then choose some random non-trivial property, say the number of states is equal to 4. Show that there is a machine that admit this property and a machine that does not. Finally describe a universal machine deciding this property (which is doable if the encoding is injective/reversible (which is usually the case). Since the example contradicts the theorem, it clearly does not apply here.

The intuitive reason is that you defined a property of a machine (the encoding itself) and not the language accepted by the machine.
> 1 votes

---
Tags: rice-theorem
---


# Question
Title: Writing a factorial function in ARM assembly language
I am required to write a factorial function in ARM assembly language that takes an integer $ n $ as input and returns the value of $ n! $. However, I can only use the $ 4 $ basic arithmetic operations $ + - * / $ (so no if-else or loop or recursion). Can anyone suggest a hint to do that? I can only do if I am allowed to use if-else or recursion.

# Answer
> 1 votes
we were required to do something similar. We were given a number to calculate, which was 7!.r0 will hold the final value. I ended up doing the following:

MOV r1, #7 MOV r1, #6 MOV r1, #5 MOV r1, #4 MOV r1, #3 MOV r1, #2 MOV r1, #1

MUL r0, r1, r2 MUL r0, r0, r3 MUL r0, r0, r4 MUL r0, r0, r5 MUL r0, r0, r6 MUL r0, r0, r7

---
Tags: algorithms
---


title: Sensitivity analysis of $MST$ edges

text:
# Question
Title: Sensitivity analysis of $MST$ edges
I am working on the following exercise:

> Consider an undirected graph $G = (V,E)$. Let $T^\* = (V,E\_{T^\*})$ be a $MST$ and let $e$ be an edge in $E\_{T^\*}$. We define the set of all values that can be assigned to $w\_e$ such that $T^\*$ remains a MST as $I\_e$.
>
> 1. Show that $I\_e$ is an interval.
> 2. Devise an efficient algorithm to calculate $I\_e$ for a given edge $e$.
> 3. Devise an efficient algorithm that determines all $I\_e$ in one step. It should be more efficient than repeatedly using the algorithm from 2.

I did the following:

1. Consider an edge $e$ in $E\_{T^\*}$. Delete it from $G$ and find the new lowest weighted edge connecting the resulting components, say $e'$. The upper bound for $I\_e$ is $w(e')$. The lower bound would be $-\infty$.
2. Use the algorithm sketched in 1.
3. I do not know what to do here. Could you help me?

# Answer
The solution in short. For each edge $e$ not in the tree, check the path between its endpoints in the tree. The weight of each edge on this path is upper-bounded buy the weight of $e$. Keep track of the smallest upper-bound for each edge on the tree while iterating over all edges not in the tree. Following is a sketch of the correctness.

Let us call an edge in a simple cycle **Heavy** for this cycle, if its weight is maximum among all edges in the cycle. We claim that each edge $e$ in $G\setminus T^\*$ is Cycle heavy for some cycle in $G$.

Proof. By adding the edge $e$ to the tree, it constructs a cycle with a path in the tree between its endpoints. If there is an edge in the cycle with strictly heavier weight, we can remove this edge and keep $e$ constricting a lighter tree which contradicts the assumption that the given tree is minimum.

On the other hand, it is not hard to prove that an edge is in an MST of a given graph if it is not heavy for any simple cycle containing this edge. The correctness of the sketched algorithm follows directly from this statement.
> 1 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and outputs $n'th$ perfect number.

How to solve this problem for large $n$ , for example $n$ close to $10^{18}$ ? we can't use brute force method since input can be so large .Can we solve it using DP or binary search ?

Source of the problem : Perfect Number

Note: In given problem statement (in link) $n$ is not large and thus can be solved using brute force.But i am curious to solve it for large $n$.

# Answer
I will describe a method running in $O(|n|) = O(\log n)$ where $|n|$ is the length of the number written in decimal representation. We will follow a dynamic programming scheme. For each $k \in \\{0, \dots 10\\}$ and each positive integer $j \leq n$ we will compute the number of integers of length $k$, whose sum of digits is equal to $k$. This can be computed using dynamic programming where $$C(k, j) = \sum\limits\_{i\in\\{0, \dots k\\}}C(k-i, j-1),$$ since we can add $i$ to the left of a number of length $j-1$ and sum $k-i$ to construct a number of length $j$ and sum $k$.

Let $P$ be a prefix sum over $C(10, j)$ for $j = 0, 1 \dots$, clearly $P(i)$ tells how many integeres of length at most $i$ sum up to 10. Now the solution to you problem can be fond recursively by finding the greatest $i$ such that $P(i) \leq n$ and subtract it from $n$. This $i$ tells the lengths of your number. And the result of the subtraction is the order of your number among numbers of length $i+1$. Now you can find the left most digit of your number by trying to set the left most number to some value $k \in {1 \dots 9} and checking how many ways you can construct the rest of the number.

I suspect the solution can be found in $O(\log |n|) = O(\log\log n)$ by only building $C(k, 2^r)$ for integers $r$ and binary search for the greatest value of $r$ where $C(10, 2^r)$ is at most $n$.
> 1 votes

---
Tags: algorithms, dynamic-programming, binary-search
---


# Question
Title: Finding the similarity between large text files
**My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.**

Let's say I have two large text files (original file A and new file B). Each file is English prose text (including dialogue) with a typical size 256K to 500K characters.

I want to compare them to find out how similar the contents of B are to A.

Similar in this case means: all, or a significant part, of B exists in A, with the condition that there may be subtle differences, words changed here and there, or even globally.

In all cases we have to remember that this is looking for similarity, not (necessarily) identity.

Preprocessing for the text:

1. Remove all punctuation (and close up gaps "didn't" -\> "didnt");
2. Lowercase everything;
3. Remove common words;
4. Reduce all whitespace to single space only, but keep paragraphs;

Other possible optimisations to reduce future workload:

Ignore any paragraph of less than a certain length. Why? Because there's a higher probability of natural duplication in shorter paragraphs (though arguably not in the same overall position).

Have an arbitrary cut-off length on the paragraphs. Why? Mostly because it reduces workload.

Finally:

For every word, turn it into a Metaphone. So instead of every paragraph being composed of normal words it becomes a list a metaphones which help in comparing slightly modified words.

We end up with paragraphs that look like this (each of these lines is a separate paragraph):

```
WNT TR0 ABT E0L JRTN TTKTF INSPK WLMS E0L UTRL OBNKS JRL
TM RL SRPRS LKT TRKTL KM N SX WRT
LT ASK W0R RT WRKS T ST N WLTNT RT 0M AL

```

But I admit, when it comes to the comparison I'm not sure how to approach it, beyond a brute force take the first encoded paragraph from B (B\[0\]) and check every paragraph in A looking for a high match (maybe identical, maybe very similar). Perhaps we use Levenshtein to find a match percentage on the paragraphs.

If we find a match at A\[n\], then check B\[1\] against A\[n+1\] and maybe a couple further A\[n+2\] and A\[n+3\] just in case something was inserted.

And proceed that way.

What should be detected:

* Near-identical text
* Global proper noun changes
* B is a subset of A

Thanks.

# Answer
> My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.

Yes, the problem you expose is widely studied in *computer science*/*machine learning* and there are dozens of algorithms to do what you are looking for. Depending on the precise specifications of what you are looking for, the complexity of the algorithm may vary. When I happened to have to perform this computation, I personally used the TF-IDF approach.

As I said it depends a lot on what you want to achieve and even a minimum change in the initial specifications can lead to a drastic change in the algorithm. You could also take a look at this link.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Example of non-regular context free language L such that prefix(L) is regular
Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L.

> What can be an example of non-regular language L such that language of it's prefixes is regular (Can be represented by a finite automaton)?

I don't understand how language of prefixes can ever be regular, since the set of prefixes of a word include the word itself.

For example $L= a^nb^n$ is my non-regular language. The language of it's prefixes would include : $\epsilon,a^n$ where $n\ge 1$,$a^nb$ where $n\ge 1$ etc...

But what about b's ? We need to know how many a's there were in the first place. Therefore I don't see how the language of prefixes can be regular.

# Answer
> 9 votes
Consider the language of words with the same number of a's and b's. It is non-regular but the set of prefixes is the set of all words which clearly is regular.

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


# Question
Title: What is the worst case for C++ "sort" function?
So, what is the worst case for C++ "sort" function, when does it go to O(n^2) time? I know it's QuickSort, therefore, it's very fast in most cases, but it gets to O(n^2) in special cases. I've tried to figure it out via measurements, but I have trouble interpreting the results.

# Answer
> 5 votes
The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from $\Theta(n \log n)$ (if you choose the pivot to be the median) to $\Theta(n^2)$ (if the pivot is always a constant number of elements away from the minimum/maximum element).

That said, C++ standards do not mandate any particular implementation of the sort() function. So it is just a "coincidence" that your implementation happens to use Quicksort.

The answer to your question about the worst case depends on which C++ standard you are referring to. Before C++11, sort() was required to take "approximately $O(n \log n)$ comparisons on the average" (whatever "approximately" means) but, since no particular implementation is mandated, you'd have to look at the sources of the standard library you are using.

If you are referring to C++11 or later, then sort() is required to perform $O(n \log n)$ comparisons **in the worst case** (see Section 25.4.1.1). To be pedantic, you'd still need to inspect the implementation to know **what** the worst case is (I could imagine a conforming implementation that first checks whether the input array is any specific permutation (or class of permutations), and then sorts it in linear time).

To be even more pedantic: the standard mandates an asymptotic number of **comparisons**, so I'm not sure whether a sort() function with a running time of $O(2^n)$ (or some weird function of the input) would conform to the standard, as long as it only performs $O(n \log n)$ comparisons...

---
Tags: quicksort
---


# Question
Title: Grouping n points into groups of size m with objective to have least traveling distance in each group
Assumptions: * There are "n" jobs which are distributed over the city.
* Company has "k" available workers.
* Each worker can do "x" jobs per day.
* "x" is dependent to the worker skills and the distance he travels each day so it's not a constant.
* Workers have no initial traveling distance.
* "s" is a set that shows each workers can do how many jobs based on the distance he travels
* "d" is the number of days that takes for company to do all the jobs.

Objective: Minimize the "d"

---

I know this problem is probably NP-hard so I don't need the exact answer. I think it's kinda a variation of Traveling salesman problem combining with scheduling and assignment problems.

My algorithm for this problem is to "some how" efficiently ( of course not the most efficient way ) grouping the jobs based on their traveling distance in the groups in to groups of "m" which is the mean of set "s". Then after each day rerun the algorithm to get better results.

My question is what is the best way to do that grouping? Anyway if you know a better algorithm I would be more than happy to know them.

# Answer
It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. But that is an extreme case.

Even an approximation is difficult. I assume each worker goes from company office to location 1 to location 2 ... to location n to company office. I'd try to group far away locations into clusters so that a worker can do a complete cluster and not be left with a single job in a cluster; doing half a cluster one day and the other half the next day would be fine, or picking jobs up on the way. Problem changes if each worker starts at home and ends up at home, then you'd want each one to do jobs near his home.

In reality, you will have new jobs coming in every day, so you need a solution for one day, and then recalculate the next day. Plus take into account that customers waiting a long time will get angry.
> 1 votes

---
Tags: optimization, np-hard, scheduling, traveling-salesman, assignment-problem
---


# Question
Title: Relabel to front, what does topological sort according to admissible network mean?
In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with zero excess flow are moved to the front of the list.

I do not fully understand what is the meaning of it. ~~I would imagine that the vertices are sorted according to the number of admissible edges incident on it~~. But then how would moving vertices with no excess flow to front affects the sorting order in this case. Also how come the list is already sorted when it is initialized with random order of vertices?

**Edit:**

Just realized that topological sorting of vertices in the admissible network means that for every admissible edge (u,v) in the admissible network the vertex u appears before v in the list.

This does not answer the last two parts of my question though, how is that the list is already sorted when initialized and how does moving zero-excess-flow vertices to front affect the order. Thanks.

# Answer
By definition an "admissible edge" $(u,v)$ is an edge that has a residual capacity $c\_f(u,v) \> 0$ and the height of the vertex it enters is greater than the vertex it leaves by exactly one $h.u = h.v + 1$.

1- When the list is initialized, there exist no admissible-edges in the admissible-network because the height difference between all pairs of vertices in the network is either $|V|$ or $0$; only the source vertex has a height of $|V|$ while all other vertices has a height of $0$. Therefore, no matter which order of vertices we use, the list will be topologically sorted.

2- After relabeling a vertex $u$, there is at least on edge leaving $u$, but there are **no** edges entering it (according to lemma 26.28 in CLRS book p.750). Therefore, there can exist no other vertex $v$ such that $(v,u)$ is an edge and $v$ precedes $u$ in the topological order. So moving $u$ to the front of the list keeps it topologically sorted.
> 0 votes

---
Tags: network-flow
---


# Question
Title: How to determine minimum word length of regular language
Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$?

A straightforward example:

Let's say we have a regular expression $r=aac^\*aa$, then $L(R) = \\{aaaa, aacaa, aaccaa, \dots, aac^naa\\}$. To determine the minimal length I would erase everything that is postfixed with $\*$, leaving $r'=aaaa$. Now I would count the concatenations and add 1, which would yield in this example, not unsurprisingly, a minimum length of 4.

Is there a general approach to do this for more complex expressions?

**Sidenote:** I need to achieve this without the help of automata.

# Answer
First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, which define an operator $E$ on regular expressions:

* $E\[\sigma\] = \sigma$, $E\[\epsilon\] = \epsilon$, $E\[\emptyset\] = \emptyset$.
* $E\[r\_1 r\_2\]$ is $\emptyset$ if one of $E\[r\_1\],E\[r\_2\]$ is $\emptyset$, and $E\[r\_1\]E\[r\_2\]$ otherwise.
* $E\[r\_1 + r\_2\]$ is $E\[r\_1\]$ if $E\[r\_2\] = \emptyset$, $E\[r\_2\]$ if $E\[r\_1\] = \emptyset$, and $E\[r\_1\] + E\[r\_2\]$ otherwise.
* $E\[r^\*\] = \epsilon$ if $E\[r\] = \emptyset$, and $E\[r\]^\*$ otherwise.

You can prove inductively that $E\[r\]$ either doesn't contain $\emptyset$, or is equal to $\emptyset$.

Applying these rewriting rules, we have either determined that the denotation of the regular expression is empty, or are given a regular expression without $\emptyset$. Now we define an operator $m$ which determines the length of the minimal word in an $\emptyset$-free regular expression:

* $m(\sigma) = 1$, $m(\epsilon) = 0$.
* $m(r\_1r\_2) = m(r\_1) + m(r\_2)$.
* $m(r\_1 + r\_2) = \min(m(r\_1),m(r\_2))$.
* $m(r^\*) = 0$.

---

You can also implement both operators at once, by allowing $m$ to output $\infty$ (meaning that the language defined by the regular expression is empty):

* $m(\sigma) = 1$, $m(\epsilon) = 0$, $m(\emptyset) = \infty$.
* $m(r\_1r\_2) = m(r\_1)+m(r\_2)$, where $\infty + \ell = \ell + \infty = \infty$.
* $m(r\_1+r\_2) = \min(m(r\_1),m(r\_2))$, where $\min(\infty,\ell) = \min(\ell,\infty) = \ell$.
* $m(r^\*) = 0$.
> 15 votes

# Answer
The general idea from the previous answer is right but unnecessarily inefficient. Compute a NFA recognizing the regular expression. Find with BFS the shortest path from the start state to some endstate. The corresponding word is the shortest accepted word.
> 6 votes

# Answer
> Is there a general approach to do this for more complex expressions?

Yes, there is a way. Note that a regular language is the language accepted by a *NFA/DFA* so the general approach to problems of this kind is to convert your expression into its corresponding *NFA/DFA* and then lexicographically search through all the words of the language until you find the first one that is accepted by your machine (reach the final state). I am not aware of other general methods besides this one.
> 2 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Divide numbers into fewest groups with each group's sum bounded
We have an integer $K$ and an array of $N$ positive integers each smaller than $K$. How do we group the numbers into the minimum number of groups where the sum of each group is less than or equal to $K$?

# Answer
> 0 votes
As comments suggested it is called the Bin Packing Problem.

---
Tags: algorithms
---


# Question
Title: Regular Expression with at least one a, even number of b
I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\\{a, b\\}$, the text asks for a regular expression for the language of all words having at least one a and an even number of b's, using only | and * (maybe $\varepsilon$ too). My idea so far has been something like $(a^\*ba^\*b)^\*a^\*a(a^\*ba^\*b)^\*a^\*$, but this doesn't match cases like bab, bbbab, or baaab.

# Answer
Another way of seeing this which gives a factorized representation is to try to locate the first $a$. It appears after either an odd or an even number of $b$.

If it appears after an even number of $b$ then you only have to check that what follows also has an even number of $b$ which can be done with Yuval's expression $a^\*(ba^\*ba^\*)^\*$.

If the first $a$ comes after an odd number of $b$, then you also have to find another $b$ and then check that the rest contains an even number of $b$.

This could be translated as follows: $(bb)^\*(a+ba^+b)a^\*(ba^\*ba^\*)^\*$. Again, you can replace $a^+$ by $aa^\*$.
> 3 votes

# Answer
Let us start with a regular expression for the language of all words over $\\{a,b\\}$ containing an even number of $b$s: $$ a^\*(ba^\*ba^\*)^\*. $$ If we want to guarantee that there is at least one $a$, which just need one of these $a^\*$'s to be $a^+$: $$ a^+(ba^\*ba^\*)^\* + a^\*(ba^\*ba^\*)(ba^+ba^\* + ba^\*ba^+)(ba^\*ba^\*). $$ (This can be simplified by replacing some instances of $ba^\*ba^\*$ by $bb$.)

Finally, you can eliminate $a^+$ by replacing it with $aa^\*$.
> 2 votes

# Answer
Take the OR of these three expressions:

$(a^\*ba^\*b)^\* (aa^\*ba^\*b) (a^\*ba^\*b)^\* a^\*$

$(a^\*ba^\*b)^\* (a^\*baa^\*b) (a^\*ba^\*b)^\* a^\*$

$(a^\*ba^\*b)^\* aa^\*$

You need any number of groups with two b’s, with any number of a’s in front of each b, followed by any number of a’s. That gives you the even number of b’s, but you need another a. You can add the a in front of a b at an odd position, or in front of a b in an even position, or after all the b’s.

State machine is a lot easier. Four states for odd/even number of b’s, and any a’s or no a, with obvious transitions. Not only is the state machine easier, it’s also much easier to find.
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: Is 3-colouring NP-hard for 5-colourable graphs?
Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph. More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, for $k\ge 3$.

Turning the question around:

> Is deciding if a 5-colourable graph is 3-colourable NP-hard?

# Answer
Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.
> 9 votes

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


# Question
Title: When and how to generate parse tree while top down parsing
I am trying to build a parser that will eventually output a 3 address code.

My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse tree?

I am looking for more psudo code than anything. Not anything concrete. For example, I have a table with the first and follow sets of all non-terminal. I take this non terminal and do the standard parsing technique for table driven parsing.

When and how do I take those choices for the parsing to create the parse tree?

Below is the grammar I am trying to parse out, I take the corresponding first and follow sets to the grammar and the parse out the input using the table driven parsing technique.

Grammar

> expr ::= term {addop term}
> term ::= factor {mulop factor}
> factor ::= variable| unsigned-number| ( expr)
> variable ::= identifier
> addop ::= + | -
> mulop ::= * | /

# Answer
As the name indicates, the parse tree is generated top-down. Specifically, you start with a place-holder node for the start symbol. Each time you *predict* a production, you fill in the placeholder with the right-hand side of the production, where each symbol is represented by a placeholder. Each time you shift over a token, you fill in the placeholder with the token's semantic value.

Since parsing nodes are expanded into the tree before their children, it's not possible to compute synthesized attributes with this algorithm, although inherited attributes can be computed when the node is predicted. You can slightly modify the algorithm to allow the computation of synthesized attributes by adding an "end production" pseudo-token at the end of every production. When a such a token is encountered, instead of shifting a token from the input, the code associated with the production is executed to fill in the synthesized attributes. However, it might be easier to compute attributes post-parse by performing one or more traverses over the parse tree.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
Consider a set $P$ of $N$ intervals $\\{I\_i = (l\_i, r\_i)\\}$ partially ordered according the standard interval order: $I\_i \< I\_j$ iff $r\_i \le l\_j$.

I want to find a minimum cardinality partition of $P$ into chains. By Dilworth's theorem, the cardinality will equal the maximum cardinality of any antichain. We can find such a maximum antichain in $O(N\log N)$ time: note that $I\_i$ and $I\_j$ are incomparable iff $I\_i\cap I\_j \ne \emptyset$, and applying Helly's theorem in one dimension, deduce that any antichain has nonempty overall intersection, and hence any maximal antichain $A$ is exactly the set of intervals containing $x$ (let us call this $A(x)$) for some point $x$. So it is sufficient to find a point $x$ that maximizes $|A(x)|$. After sorting the endpoints this can be done in $O(N)$ time.

I'm having trouble getting the dual partition though. We can find an optimal partition in $O(N^{2.5})$ time using Hopcroft-Karp to compute a maximum bipartite matching, but it seems like it should be possible to get close to linear time in this case using the duality between antichains and chain partitions. Unfortunately staring at the Wikipedia pages for Dilworth's and Kőnig's theorems doesn't seem to be getting me anywhere.

# Answer
Your problem is the same as interval graph coloring.

There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
> 4 votes

---
Tags: matching, bipartite-matching, partitions, intervals, partial-order
---


# Question
Title: runtime to a BFS flood-fill with multiple centres?
If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding them onto the queue to have their own neighbours processed if they have not been. What is the runtime, It seems it would be O(n) where n is the number of pixels but some sources have said it should be O(4^n). And how would this runtime change if the number of centres were changed, such that it was a multiple or fraction of n.

# Answer
Suppose there are `n` pixels on the screen.

We add the neighbours onto the queue only if they haven't yet been processed.

This way a pixel is added onto the colouring queue only if it hasn't been coloured yet.

Thus a pixel can be added onto the queue for a maximum of `1` time.

So if there are `n` pixels, then at most `n` additions would be done to the queue and thus `n` operations would be needed to colour the entire display.

It doesn't matter if number of centres are increased or decreased since each pixel would need to be added onto the queue at most once.

Thus the complexity would remain `O(n)` in both the cases.

Sources that claim the complexity to be `O(4^n)` are considering a brute force approach where we don't remember the pixels we have already coloured and end up colouring it over and over again.
> 1 votes

---
Tags: algorithms, runtime-analysis, search-algorithms
---


# Question
Title: What is the formal justification for the correctness of the second formulation of rod cutting DP solution
CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.

Define $r\_j$ to be the optimal way to cut a rod of integer length $j$. Since we do not know where is the optimal place to cut the rod we consider every location $ i \in \\{0,\cdots,j\\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally. If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r\_j$ optimally. i.e. we get the following recursion:

$$ r\_j = \max \\{p\_n, r\_1 + r\_{k-1}, r\_2 +r\_{j-2}, ..., r\_{j-1} + r\_1 \\}$$

However there seems to be an alternative (or maybe simpler strategy to solve such a problem):

$$r\_n = \max\_{1 \leq i \leq n} \\{ p\_i + r\_{n-i} \\}$$

CLRS has the following discussion about it:

> In a related, but slightly simpler, way to arrange a recursive structure for the rod- cutting problem, we view a decomposition as consisting of a first piece of length $i$ cut off the left-hand end, and then a right-hand remainder of length $n -i$. Only the remainder, and not the first piece, may be further divided. We may view every decomposition of a length-n rod in this way: as a first piece followed by some decomposition of the remainder. When doing so, we can couch the solution with no cuts at all as saying that the first piece has size $i = n$ and revenue $p\_j$ and that the remainder has size $0$ with corresponding revenue $r\_0 = 0$. In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.

Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.

Usually I've tried to justify it to myself by having the following thought experiment: well, if I want to have an optimal revenue I need to make sure that I some how explore all good solutions exhaustively and not miss any. If I want the solution to the whole thing $r\_j$ then it could be that the full rod is required, then the cut is at position $i=n$. That is if the optimal solution contains no cuts. But if we have a cut we will have some part of the rod that must remain un cut. If that is the case, then just consider all possible full parts of the rod from the beginning of the rod to the end that remain uncut. Basically, it seems that the solution is as follow, every solution to $r\_j$ must contain a piece of rod from the beginning that is uncut to some cutting location $i$. Since this is part of the optimal solution, we just consider all beginnings that are "full" rods up to $i$ and then make sure to solve the remaining optimally. This justification feels close to being the argument of correctness but for some reason it just seems to be missing something (wish I knew what it was).

Does someone know how to write a better clear proof of correctness of this? If its really formal or rigorous that is ok with me, I just sort of want some proof for the second recursion where there is no doubt that its correct.

Thanks for the help!

---

Recall the rod cutting problem. You manufacture steel rods of some fixed length and sell them in segments of integer length and because of the laws of supply and demand, the price per length is not constant. Given a set of prices (i.e. an array $p\_i$ indicating the price for an integer cut of length $i$) for each possible length segment, how should you cut a given rod of length $n$ into integer length segments to maximize revenue? You may assume that no cost or loss incurred with each cut.

# Answer
The proof of $r\_n = \max\_{1 \leq i \leq n} (p\_i + r\_{n-i})$ is divided into two parts. In the first part, we prove that $r\_n \geq \max\_{1 \leq i \leq n} (p\_i + r\_{n-i})$. In the second part, we prove that $r\_n \leq \max\_{1 \leq i \leq n} (p\_i + r\_{n-i})$.

**First part.** It suffices to prove that for *each* $1 \leq i \leq n$, $r\_n \geq p\_i + r\_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p\_i + r\_{n-i}$.

**Second part.** It suffices to prove that for *some* $1 \leq i \leq n$, $r\_n \leq p\_i + r\_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p\_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r\_{n-i}$. In total, the profit is at most $p\_i + r\_{n-i}$. In particular, the optimal profit $p\_n$ is at most $p\_i + r\_{n-i}$.
> 3 votes

# Answer
Let's assume the optimal cut for 8 is: $8 = 1+2+3+2$.

When $i=3$, it means you cut at length 3, and leave 5 as a second part.

You can get the optimal value from $r\_3$ and $r\_5$, of course.

But please be noted, you must have already get this optimal value when $i=1$. When $i=1$, $r\_8 = r\_1 + r\_7$, where $r\_7$ can give you optimal cut as $7 = 2+3+2$.

Therefore, to avoid redundant re-calculation as above, keeping one side uncut, and try to find the best cut at the other side is the best solution.
> -1 votes

---
Tags: dynamic-programming, recursion
---


# Question
Title: Is there an example of when DFS will not return the min. spanning tree?
If we have a connected, weighted, undirected graph. Can anyone provide an example where DFS will not return the MST? No matter what vertex we start from ?

# Answer
> 3 votes
Here is one such example of undirected weighted graph.

---
Tags: graph-traversal, minimum-spanning-tree
---


# Question
Title: Partition into pairs with minimum absolute difference, NP-hard?
I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t\_1,t\_2,\ldots,t\_m$ where each $t\_i\leq1$ for all $i$.

The question is: can you select $m$ *disjoint* pairs $(a\_i,b\_i)$ from $S$ such that $|a\_i-b\_i|\geq t\_i$?

I was trying to prove that this problem is NP-hard by a reduction from 3-Partition Problem. I failed because if I choose the numbers as in 3-partition I cannot guarantee that their absolute difference is at least $t\_i$.

Do you have any hints?

# Answer
> 2 votes
You can reduce Numeric 3D Matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\\{x\_1,\ldots,x\_m\\},Y=\\{y\_1,\ldots,y\_m\\},Z=\\{z\_1,\ldots,z\_m\\}$, construct $2m$ elements $x\_1+2M,\ldots,x\_m+2M,M-y\_1,\ldots,M-y\_m$ and $m$ values $b-z\_1+M,\ldots,b-z\_m+M$ for your problem, where $M$ is a very large number. Now the constructed instance of your problem has a solution if and only if the instance of N3DM has a solution.

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


# Question
Title: Computing a pre-topological sort using a BFS/a queue
Computing a *topological sort in a DAG* using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes that are newly with indegree 0.

This of course does not apply to computing a *pre-topological* order in a general graph, that is, an order satisfying:

If $u\leadsto v$ and not $v \leadsto u$, then $u$ appears before $v$.

Such an order is used for instance in Kosaraju's algorithm, and the wikipedia page states:

> As given above, the algorithm for simplicity employs depth-first search, but it could just as well use breadth-first search as long as the post-order property is preserved.

I believe that what is meant by "the post-order property" is just the pre-topological property.

**Question:** How can one compute a pre-topological order using a BFS(-like) algorithm?

# Answer
> 0 votes
For post-order see: https://en.wikipedia.org/wiki/Tree\_traversal#Post-order.

The algorithm just says perform step 2 using BFS traversal rather than DFS traversal, and then let $L$ be vertices of BFS in the postorder. After that perform step 3 to compute SCCs.

---
Tags: algorithms, graphs, graph-traversal, connected-components
---


title: Treap union unrandomizes priorities?

text:
# Question
Title: Treap union unrandomizes priorities?
The algorithm for the union of two sets represented by treaps is defined in this paper and on Wikipedia, but the algorithm seems flawed.

Take for example the following loop.

```
X := {a}
for (i := 0; i < 1000; i := i + 1)
  X := X ∪ {a}

```

At the end of execution, the variable $X$ contains the set $\\{a\\}$, but the priority of the element $a$ is elevated and not random because the union algorithm always picks the element with the highest priority.

Am I missing something?

# Answer
> 0 votes
My question was answered by email after I posted it here.

The answer is that the priorities of the elements can't be chosen completely randomly when an element is inserted into the treap that represents the set. The priorities need to be given by a hash function. That way, the same elements are always associated with the same priorities and the union algorithm, which always picks the element with the highest priority, doesn't return a biased treap.

---
Tags: balanced-search-trees
---