# Question
Title: All pairwise shortest paths in a graph: does knowing the path weights help?
This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w\_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we want to get the lowest-weight path from every starting vertex $i$ to every ending vertex $j$),

The "Path reconstruction" subsection of the Wikipedia article on the Floyd-Warshall algorithm, claims:

> Floyd–Warshall algorithm typically only provides the lengths of the paths between all pairs of vertices. With simple modifications, it is possible to create a method to reconstruct the actual path between any two endpoint vertices. While one may be inclined to store the actual path from each vertex to each other vertex, this is not necessary, and in fact, is very costly in terms of memory. Instead, the Shortest-path tree can be calculated for each node in Θ(|E|) time using Θ(|V|) memory to store each tree which allows us to efficiently reconstruct a path from any two connected vertices.

In general (not simply on the FloydWarshall algorithm), if we were given the optimal path distances (i.e., the distances of the most efficient routes) between every starting vertex $i$ and every ending vertex $j$, but not given the paths themselves, is this of any help to finding the best paths? I can think of trivial uses (like branch and bound to discard any paths that exceed the provided optimal path length), but am curious if there are other uses for the minimal distances.

Do you know if starting with the minimum final path distances would help find the corresponding paths?

# Answer
> 3 votes
Yes, given the lengths of the shortest paths it is easy to actually find these paths. Suppose for example that you want to find the shortest path from $s$ to $t$. Let $d(s,t)$ be the length of the shortest path, and $w(s,t)$ the length of the edge from $s$ to $t$, or $\infty$ if there is none.

If $d(s,t) = w(s,t)$ then the shortest path is simply $s,t$. Otherwise, there must be a vertex $x$ such that $d(s,t) = w(s,x) + d(x,t)$ (why?). The shortest path then starts $s,x$ and continues with the shortest path from $x$ to $t$, which you can find recursively.

You can also go from $t$ back to $s$ if you prefer. You can also make progress by finding some point $u$ such that $d(s,t) = d(s,u) + d(u,t)$.

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


# Question
Title: When to use Djikstra or Bellman-Kallaba algorithm?
This the answer that was accepted for the arrangement problem of a library:

> we have books with heights $H\_n,$ $1 \le n \le N$ and widths $W\_n,$ with heights in ascending order for each book, and we want to group them into shelves.
>
> Reuse these numbers for solution nodes $n,$ where that node represents a solution state "all books $i \le n$ have been shelved." We will therefore start at node $0$ and seek to get to node $N$ by the shortest path with Dijkstra's algorithm. These nodes are the vertices of our graph.
>
> We then draw from node $i$ to any node $j \gt i$ a directed edge which assumes that all of those intermediary books will be shelved with one shelf, i.e. the length of this edge is $$L\_{ij} = F\_j + C\_j~\sum\_{n=i+1}^j W\_n,$$where I have assumed that when you were saying the cost of the sum was $F\_i + C\_i x\_i$ the subscript $i$ on the $x\_i$ was totally meaningless.
>
> **Dijkstra's algorithm will then give us a shortest-length path to node** $N.$

With such an array, showing how many books do we have of length $H\_i$ with $L\_i$ meters of documents of $type \ i$, and the cost of storing such documents: $F\_i$ a fixed command cost and $C\_i$ the varying cost accorfing to $x\_i$ the length of documents we would store within it,

\begin{array}{|c|rr} i & 1 & 2 & 3 & 4\\ \hline H\_i & 12\\,\mathrm{cm} & 15\\,\mathrm{cm} & 18\\,\mathrm{cm} & 23\\,\mathrm{cm}\\ L\_i & 100\\,\mathrm{cm} & 300\\,\mathrm{cm} & 200\\,\mathrm{cm} & 300\\,\mathrm{cm} \\ \hline F\_i & 1000€ & 1200€ & 1100€ & 1600€ \\ C\_i & 5€/\mathrm{cm} & 6€/\mathrm{cm} & 7€/\mathrm{cm} & 9€/\mathrm{cm}\\ \end{array}

The graph is:

My question is: **why should we use a Djikstra algorithm? We don't have any circuits and we can't go backward. Therefore, shouldn't we use Bellman-Kalaba algorithm?**

# Answer
> 8 votes
Dijkstra's algorithm is faster (more efficient) than Bellman-Ford for graphs where it is applicable, i.e., for graphs where all edge weights are non-negative. This is one such graph, as the cost of a bookshelf can never be negative. Therefore, for this graph, Dijkstra's algorithm is better than Bellman-Ford.

(Incidentally, that answer is the accepted answer because you accepted that one.)

---
Tags: algorithms, graphs
---


title: Optimizing NFL draft picks

text:
# Question
Title: Optimizing NFL draft picks
I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, and a salary cap, build the highest projected scoring NFL team that fits the salary cap. I am interested in finding an efficient way to do this.

An NFL team consists of 1 QB, 1 TE, 1 K, 1 D, 3 WRs and 2 RBs. Each position has a varying number of potential players available, but for the sake of argument we can say that from an initial list of about 600 players total, we can safely eliminate most of them so that there are 5-15 players to choose from for each position.

I have "solved" this problem with a brute force approach: I have a separate loop for each position, loop over all available players, and find the best team that fits the salary cap. This works, but having written a function containing 9 nested loops makes me feel dirty. To deal with a dataset with around 10 players in each position as options, it takes about 2 hours to finish. Past that, it would be too slow to be useful.

Several websites out there do exactly this: For Example. However, if you reject a player from their lineup and recalculate, it takes less than a second to find a new optimized lineup. It was pointed out to me that it is possible that they are doing a pre-computation and storing all possible teams in a database, and simply searching through it in order to find new optimized lineups when someone tweaks things, but I am hoping that is not the case.

So the question, finally: is there an efficient algorithm that guarantees an optimal solution, assuming that the best team mean maximizing the sum of projected points for the players on the team?

# Answer
Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem.

Basically, order the positions from 1 to 9. You're going to fill in a two-dimensional table $T$, where $T\[i,s\]$ denotes the score of the highest-scoring team that fills in just the first $i$ positions and has a salary cap of $s$. The key observation is: given the row $T\[i-1,\cdot\]$ of the table, you can compute $T\[i,s\]$ via a simple recurrence relation. In particular,

$$T\[i,s\] = \max \\{ T\[i-1,s-s\_j\] + p\_j : j=1,2,3,\dots\\},$$

where $j$ ranges over the candidates for the $i$th position, $s\_j$ is the salary of the $j$th candidate, and $p\_j$ is the projected points generated by the $j$th candidate. This lets you fill in the table, row by row.

The running time is quadratic: proportional to the total salary for the team, times the number of positions. There are two nested loops, rather than 9.
> 3 votes

---
Tags: algorithms, optimization, knapsack-problems, program-optimization
---


# Question
Title: How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?
I'm trying to compute a language defined as { ww | w ∈ {0,1}\* } in JFlap using a Multitape Turing Machine. It seems a hard problem because there is no delimiter to know when the word `w` is ended.

I already checked this and this question, but this didn't helped me at all. The answers from "Construct Turing Machine which accepts the language $ww$" talks about deterministic machines and one answer just cite non-deterministic, but dont give details on how this design can be achieved for the given problem.

I've found this algorithm, but this seems **very** confusing for me (I don't understand the first stage (for example), so I can't reproduce this answer at JFlap).

```
// Stage 1: Check length is even, change as / bs to As / Bs
while a or b {
    change a to A or b to B & move R
    while a or b move R
    move L
    change a to A or b to B & move L
    while a or b move L
    if A or B move R
}

// Stage 2: Change As and Bs in first half to as and bs
if Blank halt
if A or B move L
while A or B change to a or b & move L
if Blank move R

// Stage 3: Compare first and second halves
while true {
    if a {
        change a to A & move R
        while a or b or Blank move R
        change A to Blank & move L   // fail if B
        while a or b or Blank move L
        if A or B move R
    } else if b {
        ... similarly ...
    }
}
if Blank halt

```

Can someone clarify this question to me? How can I achieve the first stage in a multitape Turing machine? How can I proceed to solve the problem?

***P.S: It must be a multitape Turing machine.***

# Answer
Regarding the first part:

```
// Stage 1: Check length is even, change as / bs to As / Bs

```

and

```
// Stage 2: Change As and Bs in first half to as and bs

```

Are to find the word middle, then just compare the first half against the second half. Here is a SIMILAR picture for you at JFLAP:

As you can see, at state "q2", I came back to the tape's beginning, to really starts the computation at the state "q3".

After got at the state "q3" you can jump straight to you algorithm part:

```
"// Stage 3: Compare first and second halves"

```

And complete your Turing Machine. But this was your question 1.a) and now you want to solve the question 2.a)

To do it, you will only need to use the step "**// Stage 3: Compare first and second halves**", from you algorithm.

**To do it using a Multi-Tape Turing Machine**, you are going to need 4 tapes, the word is to be placed at the tape 1 and the others tapes must to be clean, i.e., contain only blank symbols:

**First** step, if the tape 1 has only the blank symbol, accept the language.

**Second** step, if the only symbol not marked at tape 1 is the blank symbol, reject the language.

**Third** step, is to copy the first symbol not marked from the tape 1 to the tape's 2 end. Then mark it at the tape 1.

**Fourth** step, is to copy the whole tape 1 to the tape's 3, and the tape 2 to the tape 4.

**Fifth** step, is to compare both tapes 3 and 4 are equal using yours algorithm step "// Stage 3: Compare first and second halves", but instead of failing to accept the language, go to the step **Sixth**.

**Sixth** step, if they are equal accept the language. If they are not, go to the **Second** step.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Does proving a problem is in P typically mean it will eventually be practically solvable?
I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P and NP.

First he says:

> $P$ roughly corresponds to the class of problems that are realistically solvable on a computer.

He then continues a little further down the page:

> Of course, a running time of $n^{100}$ is unlikely to be of any practical use. Nevertheless, calling polynomial time the threshold of practical solvability has proven to be useful. Once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained and further reductions in its complexity usually follow, often to the point of actual practical utility.

So my question is the following: What are examples of problems that were proven to be in P but were intractable, but after some theoretical advances became tractable?

I'm also welcome to hearing about problems that were proven to be in P whose runtime was significantly advanced by some algorithmic improvements but perhaps was not advanced enough to be tractable.

# Answer
> 2 votes
One example in which the running time became significantly better but still not necessarily practical is *submodular function minimization*, which went down from $O(n^7)$ (Grötschel, Lovász and Schrijver, 1981) to $\tilde{O}(n^4)$ (Lee, Sidford and Wong, 2015). The latter paper (and the ones preceding it) has many such results.

---
Tags: algorithms, complexity-theory, terminology, efficiency
---


title: An algorithm for vertex cover

text:
# Question
Title: An algorithm for vertex cover
Let $G = (V,E) $ and let be $T \subseteq V$ . $T$ is called vertex cover if each edge of the graph is incident to at least one vertex of $T$ .

Let be the following decisional problem :

$PROBLEM$

Input : $G = (V,E) $ with $n$ nodes ; $k\in \mathbb{N}$ , $k \le n$

Output : $YES$ if exists $T$ such that $T$ is vertex cover with $|T| \le k $ , else $NO$

$a)$ Proof the correctness of the following algorithm for solving $PROBLEM$ :

$V-COV ( G , k ) $

$IF$ ( $E(G)$ = $\emptyset $ ) then $return$ ($YES$ , $\emptyset$) ;

$IF$ ( $E(G)$ \> $k$ * ($|V(G)|$-1) ) then $return$ $NO$ ;

Let $\\{u,v\\}$ $\in$ $E(G)$ ;

$IF$ ( ($V-COV ( G - u , k- 1 ) $ return ($YES$ , $T$ ) ) then $return$ ($YES$ , $T \cup \\{u\\}$) ;

$ELSE$ $IF$ ( ($V-COV ( G - v , k- 1 ) $ return ($YES$ , $T$ ) ) then $return$ ($YES$ , $T \cup \\{v\\}$) ;

$ELSE$ $return$ $NO$ ;

$b)$ Find out time complexity $T(n,k)$ for this algorithm and prove if $k$ is constant then it has a polynomial time complexity .

For $a)$ the first $IF$ statement is trivial .. but the others ? For $b)$ vertex cover is in $NP$ , right ? So it has exponential time complexity , right ? I wait answers please ..

# Answer
> 1 votes
> For b) vertex cover is in NP, right ? So it has exponential time complexity, right?

Yes, vertex cover is in **NP**. However, that doesn't mean that vertex cover has exponential time complexity: for example, every problem in **P** is also in **NP**. You probably mean to say that vertex cover is **NP**-complete, which means it's probably not in **P** (unless **P = NP**). However, **NP**-completeness is not known to imply that every algorithm must be exponential.

Furthermore, the problem asked about in b) is not vertex cover. In vertex cover, we're given a graph $G$ and an integer $k$ and asked if $G$ has a vertex cover of size at most $k$. However, the problem asked about in b) is whether $G$ has a vertex cover of size at most some fixed value of $k$, which is not part of the input. In particular, you can determine whether any graph has a vertex cover of size at most 17 by testing every set of size 17 to see if it is a vertex cover. That requires testing $O(n^{17})$ sets, which is a polynomial number.

---
Tags: algorithms, algorithm-analysis, graphs, runtime-analysis, correctness-proof
---


# Question
Title: Exploring and interpolating a function using machine-learning?
Which general machine-learning methods are there that try to **"learn" or interpolate a smooth multivariate function** and which get to actually **choose the points** at which the function is evaluated during the learning process (exploration)?

The idea would be that each function evaluation is more or less costly and the algorithm learns to explore the regions of space where the gain of knowledge is greatest (vs. the cost of evaluating the function). The function may be non-analytic (e.g. with kinks) in the most interesting cases.

My background is physics, and I am sure that such methods exist, but despite some searching I could not find something that is directly relevant, possibly because I do not know the right terms to look for. I only know that more broadly speaking 'reinforcement learning' is the area of AI dealing with exploration and rewards, so maybe the methods I am asking for represent some special case of that.

For clarification, here is an example: You might want to get the phase diagram of a substance, i.e. the density as a function of pressure p and temperature T. So we are dealing with a (mostly) smooth function of two variables (p,T). Its evaluation at any given point (p,T) requires an expensive Monte-Carlo simulation (lots of CPU time; how much even depends on where in the p,T-space you are). The ideal algorithm would judiciously pick points (p,T) at which to evaluate the density, trying to go towards regions where the function has the most salient features (e.g. phase transition lines, i.e. non-analyticities). Then afterwards, when you ask the algorithm for the density at any other point (p,T), it provides the best possible interpolation/extrapolation that it can come up with, given all the information it has acquired during its exploratory phase.

# Answer
I would look into the field of "optimal experimental design" in bayesian inverse problems, particularly the recent work of Alen Alexandrian.

http://arxiv.org/abs/1410.5899

http://www4.ncsu.edu/~aalexan3/research.html

Essentially, one has an inner inverse problem for approximating the function based on point measurements of derived quantities, hosted within an outer optimization problem for choosing the points based on minimizing a combination of the error and the variance.

Furthermore, you don't need to do a full inner-outer solve procedure. Rather, you can use the KKT conditions for the inner problem as the constraint for the outer problem, and formulate a "meta" KKT system for the combined problem.

It is formulated in the language of PDE-constrained inverse problems, but would also apply to simpler situations like your problem (the "PDE" becomes the identity matrix..)
> 4 votes

# Answer
Active learning is a term used in the machine learning literature for the situation where the learning algorithm is allowed to interactively query the value of the function on certain points. I don't know if there are existing algorithms in the literature for active learning of smooth multivariate functions, but it sounds like that's what you want. You could spend a bit of time with Google Scholar looking for work in this area.

You could also look at optimal experimental design.
> 2 votes

# Answer
genetic algorithms can be used for this purpose. in some cases the fitness function evaluation is somewhat "expensive". part of the difficulty is encoding some kind of measurement of "interesting regions" and this metric would somehow have to quantify measurements over multiple function evaluations ie a single function evaluation is not enough to "notice a trend". ie:

> the algorithm learns to explore the regions of space where the gain of knowledge is greatest

and later you call it *"finding most salient features"*. this statement is problematic because it is generally hard to mathematically quantify *"where the gain of knowledge is the greatest"* or *"salient features".* one possibility to formalize/ quantify it is to consider "high-entropy vs low-entropy" for which there is a large body of theory.

your problem is also somewhat split along the lines of supervised vs unsupervised learning so thats an area to further analyze wrt your problem.

a recent major case of successful application of ML in physics was the Higgs machine learning challenge and incorporates many of the ideas you mention. in this case particle track behavior is predicted by the ML algorithm and it automatically learns about noise vs signal in the data. winning algorithms generally used decision trees as described in the paper.
> -2 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: How to prove the linear context free languages are closed under gsm mapping?
I'm stuck on the following question:

**How to prove the linear context free languages are closed under gsm mapping?**

# Answer
If you know that gsm mappings can be written as a composition of an inverse morphism, intersection with a regular language, and a morphism, then it suffices to observe that the linear languages are actually closed under these operations.
> 2 votes

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Is the language TMs that accept finite languages Turing-recognizable?
I know that $L=\\{ \langle M \rangle \mid |L(M)| \< \infty \\}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

# Answer
> 7 votes
If that method worked, semi-decidability would *always* imply decidability for infinite languages (note how you don't need any property of $L$ to make the proof work), which we know is not true.

Since your reasoning is sound, one of your assumptions has to be faulty. What you assume is, paraphrased:

> Assuming semi-decider $H$ for $L$, I can enumerate $L$ in lexicological order by using $H$.

You don't say how you do this, though, and we have already determined that you can not.

What you probably had in mind that we always get a recursive enumerator, and even a repetition-free one for infinite languages. Thus, it's the *order* that has to be impossible to achieve.

Intuitively, you can not reject $i$ as next output of the enumerator after only finite time.

---

Proving that $L$ is not semi-decidable works by reduction as well. See here for inspiration.

Hint:

> Reduce from $\overline{K}$, the complement of the Halting language.

Details:

> Define a computable mapping $\langle M \rangle \mapsto \langle M' \rangle$ so that $\langle M \rangle \in \overline{K}$ if and only if $\langle M' \rangle \in L$. For instance, define $M'$ by
>
> ```
>  M'(y) :
>    Simulate M(⟨M⟩) for y steps.
>    if M halts
>      accept y
>    else
>      reject y
> ```
> Note how $L(M') = \emptyset$ if $\langle M \rangle \in \overline{K}$, and $L(M') = \mathbb{N}\_{\geq N}$ if $M$ halts after $N$ steps on its own code.

# Answer
> 4 votes
I don't believe the method you're proposing works. While you will eventually enumerate a string that comes after $\langle M \rangle$, that doesn't mean that $L$ is decidable.

However, you can use an enumerator for $L$ and the recursion theorem to show that this language is not recognizable. Here's a proof sketch. Suppose $L$ is recognizable. Let $E$ be an enumerator for it. Now, design a machine $M$ that gets its own description, then runs the enumerator. If it ever sees its own description, it immediately accepts its input. Otherwise, it loops forever.

Now, if $\langle M \rangle \in L$, then $M$ will eventually see $E$ list its description, so it will always accept, meaning that it has an infinite language, a contradiction. Otherwise, the enumerator will never list $\langle M \rangle$, so it never accepts anything, but then its language is finite, a contradiction!

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Using dynamic programming to maximize work done
Say that there are $n$ days and there is $x\_1, x\_2, ...,x\_n$ amount of data to process on each day. Your computer can process $s\_1$ amount of work on the first day since rebooting your computer, $s\_2$ work on the second day since a reboot, up to $s\_n$. On each consecutive the day the amount of work your computer can perform without being rebooted decreases. In other words, $s\_1 \>s\_2\>...\>s\_n\>0$. Any day you reboot your system you cannot do any work.

The problem is to find an algorithm using dynamic programming to figure out the maximum amount of work possible given $x\_1...x\_n$ and $s\_1...s\_n$. This means we must determine which day(s), if any, we should reboot on.

For example:

```
n| 1 | 2 | 3 | 4
x| 8 | 3 | 11| 5
s| 9 | 4 | 2 | 1

```

The most optimal solution here would be to reboot on day 2, so that we can perform 8 work on day 1, 9 work on day 3, and 4 work on day 4 for a total of 21.

This seems somewhat similar to the partition problem but I am having trouble coming up with a recurrence relation I can convert to dynamic programming.

If we say that our final reboot occurs on day $i$, then our maximum work should be the amount of work done from days $i$ to $n$ plus the maximum work we can do on days $1$ to $i-1$.

So if we say $M\[x\_1...x\_m,s\_1...s\_n\]$ represents the maximum amount of work we can do on days $1$ to $m$, I write the following recurrence relationship:

$$M\[x\_1...x\_m,s\_1...s\_n\] = \max\_{i=1}^m\\{M\[x\_1...x\_{i-1},s\_1...s\_n\]+R\[i\]\\}$$

Where $R\[i\]$ is simply the max amount of work you can do from days $i$ to $n$ without rebooting, which is simple to calculate.

Does this seem like it is a valid recurrence relation? Also, I am not quite sure what my base cases would be. Perhaps that $M\[x,s\] = \\{x$ if $s \geq x$ else $s\\}$? I am not sure if this covers all possibilities though.

# Answer
> 5 votes
This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it.

Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$

For every $i$, there can be a reboot in any previous day $1\leq j \< i$. If it was on day $j$, than you processed $\sum\_{k=j+1}^i \min\left\\{s\_{k-j}, x\_k\right\\}$ terabytes. Furthermore, on day $j$ you cannot process anything. Than you can define the following recurrence relation: $$ OPT(i) = \displaystyle\max\_{1\leq j \< i} \left\\{\displaystyle\sum\_{k=j+1}^i \min\left\\{s\_{k-j}, x\_k\right\\} + OPT(j-1)\right\\} $$

The algorithm can be implemented in a bottom-up fashion, with $O(n^3)$ running time:

```
let OPT[0...n] be a new array of n+1 elements
OPT[0] = 0, OPT[1] = min(s[1], x[1])
for i = 2 to n
  m = -infinity
  for j = 1 to i-1
    l = 0
    for k = j+1 to i do l = l + min(s[k-j], x[k])
    l = l + OPT[j-1]
    if l > m then m = l
  OPT[i] = m
return OPT[n]

```

There is also a $O(n^2)$ solution based on a matrix of subproblems. Define $OPT(i, j)$ as the maximum from day $i$ to $n$ with last reboot done $j$ days before, more exactly on $i-j$ day. For every day $i$ you have to consider these alternatives:

* you have a reboot. So on day $i$ you cannot process anything: $OPT(i,j) = OPT(i+1, 1)$
* go on with processing: $OPT(i,j) = \min\left\\{s\_j, x\_i\right\\} + OPT(i+1, j+1)$

Because it's of no use reboot on last day, you have $OPT(n,j) = \min\left\\{s\_j, x\_n\right\\}$.

This last approach is taken from Mangat Rai's work, a user that shared a collection of solutions to Kleinberg's book problems, although the first one i reported is also very close to what you can find there. I suggest you to do a web search for it (no official site as far as i know).

---
Tags: algorithms, optimization, dynamic-programming, scheduling
---


# Question
Title: Why are states called locations in Timed Automata?
I started reading about timed automata lately. In the definition, they have *locations* instead of *states* as in automata theory. Can anyone explain why is this?

# Answer
It is mainly a matter of avoiding ambiguity.

At any moment in a Timed Automaton (TA), available transitions depend on the current location and the current clock valuation. Thus, the current *state* is the combination of the current control state (or *location*) and the current *clock valuation*.

If you see a Finite State Automaton as a TA with $0$ clocks, only one clock valuation is possible, and it is the same for every states. The clock valuation is thus irrelevant, and the current state is entirely determined by the current location. To simplify the vocabulary, we identify both terms.

The word "location" is often used because it is hard to mistake it for "state". But it is not uncommon to see "discrete state" instead of "location", and "extended state" instead of "state".
> 5 votes

---
Tags: terminology, automata
---


# Question
Title: How does one compute the probability of a false-based Monte Carlo algorithm being correct rigorously?
Recall that a false-biased Monte Carlo (MC) algorithm is always correct when it returns false for some decision problem i.e. it has a one sided error and its always correct on NO instances.

Assume that we have a false-biased MC algorithm. In this case when it says NO its always correct. This means that it is not allowed to say NO on YES instances (otherwise, it would make a mistake). So on YES instances it always says YES (and never NO) and when it says NO in NO instances, its correct. In other words:

> So if the answer to some problem is YES, then algorithm $A$ will always output YES, while if the answer is NO, it will output NO with probability at least $\frac{1}{3}$.

What confuses me is how one would calculate the probability of the algorithm being correct (say, for only 1 run of it, we can extend it to amplification if we want later). I was told that such an algorithm as described above has probability at least $\frac{1}{3}$ of being correct (i.e. $Pr\[\text{correct}\] \geq \frac{1}{3}$), however, I wasn't sure how to formally justify this.

These are my thought. For calculating the probability of the algorithm being correct I would write down the total law of probability (and Bayes rule)to decide if its correct:

$$ Pr\[correct\] = Pr\[correct \mid \text{NO instance} \] P\[\text{NO instance}\] + Pr\[correct \mid \text{YES instance} \] P\[\text{YES instance}\] $$

$$ Pr\[correct\] = Pr\[A(x) = NO \mid \text{NO instance} \] P\[\text{NO instance}\] + Pr\[A(x) = YES \mid \text{YES instance} \] P\[\text{YES instance}\] $$

However, it seems that this is not the approach people take when talking about the correctness of an MC algorithm. I understand that in this paradigm of algorithms one does not think of the input as being randomized, so, is the standard thing to say that the probability of getting any instances is 0.5?

In that case we have:

$$ Pr\[correct\] = Pr\[A(x) = NO \mid \text{NO instance} \] \frac{1}{2} + Pr\[A(x) = YES \mid \text{YES instance} \] \frac{1}{2} $$

$$ \geq \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{2} = \frac{2}{3}$$

From my analysis, it seems that the correct thing to say is its correct with probability at least $2/3$ however, one would say that its correct with prob at least $\frac{1}{3}$? I guess it is still correct but I am unsure if this is the correct way to think about it and also why one would say instead that the probability of it being correct is $\frac{1}{3}$ and not $\frac{2}{3}$? (I know that amplification makes which constant we say meaningless, but my question is not about which one we say, but rather how does one calculate the probability of a randomized algorithm being correct).

It seems to me that the usual way to think about it is to consider which type of instance we get separately but I don't quite understand why that is the case. I am saying that is the "usual" way because of the following excerpt:

I just want to clarify that I do understand how they got $1 - (\frac{2}{3})^k$ and that isn't what is confusing me. What is confusing me is how one deals with conditional probabilities in Monte Carlo algorithms and how one uses the total law of probability (and marginalization) to deal with these probabilistic events.

I guess my question can also be phrased as why goes the following phrase:

> A randomized algorithm for a decision problem with one-sided-error and correctness probability $\frac{1}{3}$

equivalent to:

> that is, if the answer is YES, it will always output YES, while if the answer is NO, it will output NO with probability 1/3.

From what I am reading from the solutions, it seems to me that one says an MC algorithm is correct if for each instances NO and YES, for both cases, the algorithm A outputs a correct answer with probability greater than whatever constant one is aiming for...and one doesn't involve the probabilities of the instances because we don't think of the probability of those events?

In other words, an MC algorithm being correct with prob greater than 0.5 doesn't mean we consider the event:

$$Pr\[correct\]$$

instead, we consider the probability of correct for each instances separately and if both satisfy the inequality that we need, then the algorithm succeeds with the desired probability?

# Answer
> 2 votes
We say that a randomized algorithm $A$ has success probability $p$ if

* On a YES instance $x$, $\Pr\[A(x)=YES\] \geq p$.
* On a NO instance $x$, $\Pr\[A(x)=NO\] \geq p$.

We say that a randomized algorithm $A$ has one-sided success probability $p$ if

* On a YES instance $x$, $\Pr\[A(x)=YES\] = 1$.
* On a NO instance $x$, $\Pr\[A(x)=NO\] \geq p$.

In all cases, the probability is taken (only) over the coin tosses of the algorithm. We can't take probability over $x$ since we are not given any distribution over instances.

The exercise has a slightly unorthodox definition that is useful mostly for the exercise (with $=$ instead of $\geq$).

These definitions are *worst-case* – the success probability of the algorithm (which can be taken as the optimal $p$) depends on the worst input. In a distributional setting – in which there is a distribution on the instances – we can also consider $\Pr\[A(x)=T(x)\]$, where $T(x)$ is the type of $x$, and this time the probability is taken over both $x$ and the coin tosses of the algorithm. In this setting it is also common to consider deterministic algorithms. We can consider both two-sided and one-sided algorithms in this setting as well.

---
Tags: algorithms, algorithm-analysis, randomized-algorithms
---


# Question
Title: What is the difference between computational model, model of computation and a computer?
I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model.

What is the difference between a computation model and model of computation and how can we relate them to computers ?

> A model of computation is the definition of the set of allowable operations used in computation and their respective costs.

what does it mean to 'define the allowable operations used in computation'?

Can we say that rule 110 or cellular Automata in general are computers ?

# Answer
A **model of computation** is an *abstract* device used to perform computation.

For example, Turing machines are a model of computation. They allow operations such as reading a symbol on the tape, writing a symbol on the tape, move left/right...
Minsky machines are another model of computation. They allow operations such as increment a counter, decrement a counter, test a counter for zero.
Models of computation are used to reason about algorithms, to answer questions like: is problem X realizable with the model of computation Y? If so, how many operations would be needed?

Those models are abstract because they only describe *what* the available operations are, not *how* they are realized. A **computer** is a *realization*, an *implementation* of an abstract model of computation. To ease their daily use, and to get efficiency from various technologies, computers have various sets of operations, and it is hard to describe an abstract model of computation for them. Yet, all the operations they perform can be expressed in terms of e.g. Turing machines or Minsky machines operations.

Note that a Turing machine cannot exist for real: a Turing machine has an *unbounded* tape, so it would not fit in our Universe. Similarly, the counters of a Minsky machine are supposed to be able to store arbitrarily high numbers.

From a strict theoretical point of view, since a computer has a finite fixed amount of memory, it is nothing more than a finite state automaton (with a large, yet fixed, number of states).
In practice, a computer is rather considered as a Turing machine, with a tape (memory) large enough not to run out.

To conclude, a **computational model** is a mathematical description of a complex system, often a physical one. Computational models are mostly intended for simulation, to be run on real computers.
> 5 votes

---
Tags: complexity-theory, computability, cellular-automata
---


# Question
Title: Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input
Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input arrays, with all permutations of the numbers being equally likely) is concerned?

Or perhaps, has a case been made for the assertion that a generalization is not possible?

# Answer
The asymptotic expected running time of quicksort is $\Theta(n \log n)$: this is true for all three pivot methods you mention.

Wikipedia says that the expected number of comparisons is approximately $1.386 n \log n$ when using a random pivot, and approximately $1.188 n \log n$ when using median-of-three pivot. There's some experimental evidence that the number of comparisons might be about $1.094n \log n$ when using a ninther pivot for large arrays, median-of-three for medium-sized arrays, and single element for small arrays. See the following research paper:

Jon L. Bentley, M. Douglas McIlroy, "Engineering a Sort Function". Software Practice and Experience, 23(11):1249-1265, Nov 1993.

(This paper is cited in the Wikipedia article I mentioned above.)

I'm not familiar with the "uniform shuffle" pivot selection method. It sounds equivalent to choosing a random element and using that as the pivot.
> 4 votes

---
Tags: algorithms, sorting, efficiency
---


title: run time analysis of a for loop

text:
# Question
Title: run time analysis of a for loop
I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me.

the loop is

```
for(j=1; j< n; j=j*2)

```

J is increasing at an increasing rate so it will be less than n/2 however I am having trouble concluding what exactly it will be.

# Answer
> 1 votes
In your loop, $j$ will take the values $1, 2, 4, 8, \dotsc, 2^k$ where $2^k\<n$. You need to know how many times this will iterate. In other words, what will be the largest $k$ for which we have $2^k \< n$? Take the log to the base 2 of each side of the inequality and you're asking what the largest $k$ will be for which $k\<\log\_2n$. What this means is that you're right in your comment: the loop will iterate no more than $\log\_2n$ times.

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


# Question
Title: Shortest path in a dynamic tree with vertex updates
There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries:

* Set(X): change the given vertex X from type 0 to type 1,
* Dist(X): find the shortest path from X to a node of type 1 and return the length of this path. This will return zero if X is of type 1.

The naive method would be to just maintain a tree and on every update change the type of vertex; to answer queries of second type, run a bfs starting at X and stop as soon as a vertex with type 1 is found. With this simple scheme, Set(X) would run in $O(1)$ time, but Dist(X) would take $O(n)$ time.

However, in my application the number of queries and number of nodes are both of the order of $10^5$, so the naive method is too slow. In particular, $O(n)$ time is too slow.

Can somebody suggest a better algorithm for doing this?

# Answer
One can improve your naive method by augmenting the data structure. At each node in the tree, store an extra field that contains the distance to the closest descendant of type 1. Assume each node as a pointer to its parent. Let the depth of the tree be $d$.

Now Set(X) takes $O(d)$ time: you traverse the parent pointers to visit each of X's ancestors and update their distance field. Also Dist(X) takes $O(d)$ time: the distance field for X tells you the shortest path to a descendant of X, and by looking at the distance fields for the siblings of the nodes along the path from X to the root, you can find the shortest path to a non-descendant of X. Thus, both operations can be done in $O(d)$ time.

If the tree is balanced, we'll have $d = O(\lg n)$, so both operations run in $O(\lg n)$ time -- a significant improvement over the naive method you mention.

Of course, in the worst case the depth of the tree could be $\Theta(n)$, so this method won't help for such trees. But in practice many trees (e.g., random trees) tend to have depth $O(\lg n)$. And if you need an algorithm that works for all trees, you might be able to take advantage of a heavy-light decomposition to achieve good worst-case running time bounds.
> 1 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: How many operations at maximum needed to compute powering of a number, i.e. $N^k$?
Suppose $N$ is $L$-bit long and $k$ is also $L$-bit long.

How to show that it takes at most O$(L^2)$ operations to compute it.

For example $N = 1010$ and $k = 10$. Then $N^k = 6^2 = 100100$. But I am not familiar with how $100100$ comes up without going back to decimal and using the fact that $6\*6 = 36$. Therefore, I also find it hard to realize that it takes at most O$(L^2)$ operations to compute the powering of a number.

# Answer
> 4 votes
It depends on what you mean by *operations*. If multiplication of unbounded numbers is considered one operation, then repeated squaring takes at most $2L$ operations. In that case we don't care about the size of $N$.

If we only consider multiplication of $L$-bit integers as a unit operation, then multiplying $ML$-bit integers takes $O(M^2)$ operations using the high-school algorithm (in fact, much better algorithms are known), and so repeated squaring, in which the integers have size $L,2L,4L,\ldots,2^LL$, takes $O(1^2 + 2^2 + \cdots + 2^{2L}) = O(2^{2L}L)$ operations. Using fancier multiplication algorithms that take $\tilde{O}(L)$ operations (if they exist in this setting) reduces the number of operations to $\tilde{O}(2^L)$.

---
Tags: complexity-theory, number-theory
---


# Question
Title: Question about "Type checking a multithreaded functional language with session types" by Vasconcelos et al
I have been reading the paper\[\] in the title. But there are some parts of it that are unclear to me, more specifically the way you typecheck a lambda. I have attached the typing rules below as images\[\] \[\] Typing them all in Mathjax would have been a lot of work.

I will explain the issue I am having by means of an example.

Given the program in listing 1, we first apply the rule `C-Let`. This means that we typecheck the first binding, namely `new !Int.End` which yields the type `[!Int.End]`. $\Gamma$ now contains a mapping $x \rightarrow \[!Int.End\]$. Then we typecheck the next let, using `C-Let` once more. This time we typecheck `accept x`, which first makes sure that $x$ is of the proper type. $\Gamma$ contains this mapping so that is indeed the case. This yields the type `Chan c`. Note that when you look at the typing rule for `accept`, $c$ in this case is a so-called "fresh" variable. The rule `C-Accept` also inserts the session type into $\Sigma$. So $\Sigma$ contains a mapping $c \rightarrow\ !Int.End$ and $\Gamma$ contains two mappings, namely $\Gamma = x \rightarrow \[!Int.End\] , v \rightarrow Chan \ c$

We then proceed to typecheck the last body of the most-inner let. The first statement is a `send` statement so we apply rule `C-SendD`. Typechecking the number $5$ yields type `Int`, so that part is correct. $v$ yields the type $Chan\ c$. $\Sigma$ indeed contains a mapping $c \rightarrow\ !Int.End$. So the rule `C-SendD` finally yields the type $\Sigma;Unit;c:End$ where the first part of the entry in $\Sigma$ has been consumed, leaving the session type for $c$ to $End$.

Finally we can apply the rule `C-Close` which also typechecks properly.

### Listing 1

```
let x = new !Int.End in
let v = accept x in
  send 5 on v;
  close v;

```

We can now transform the above example to the following:

### Listing 2

```
let x = new !Int.End in
let v = accept x in
let f = (Lambda x:Int . (close v))
  send 5 on v;
  (f 1);

```

Listing 2 shows that instead of just calling `close` on the channel we have stored that operation inside a lambda. We will play typechecker one more.

The first part of the typechecking is the same as above. So we have arrived at typechecking the body of the second let, namely `let f =...`. At this point $\Sigma = c \rightarrow\ !Int.End$ and $\Gamma = x \rightarrow \[!Int.End\] , v \rightarrow Chan \ c$.

The body of the lambda uses a channel that is defined outside of the lambda, namely $v$. According to the paper, the required $\Sigma$ should be embedded in the type signature of the lambda. However, this is where things get unclear. If I follow the typing rules I would have written down the lambda as $(Lambda\ \[c \rightarrow End,\ x:Int\]\ .\ (close\ v))$. But this is impossible, I think.

Recall that the rule `C-Accept` uses $fresh$ to "generate" a symbol that will be the identifier in $\Sigma$ and the second part of the type of the channel (e.g., $Chan\ c$). This means that it is impossible for the programmer to write down this identifier. Unless, of course, the channel is the parameter of the lambda itself. Then we can use $\alpha$-renaming. But this is not the case here, the channel is simply captured by the lambda and the parameter is $x$ which is ignored in the body of the lambda.

So, there are two options the way I see it. The text in Listing 2 is illegal for the reason that you can not capture a channel that has not been passed to the lambda as a parameter. However, the paper shows an example of this at page 9. So this reasoning is probably faulty.

The second reasoning I can come up with is the following. At the time the lambda is typechecked (as the binding to $f$), the typechecker will error because we are calling `close` on a channel that has session type $!Int.End$ in $\Sigma$. But, this could then be resolved by delaying the typechecking of the lambda until the point that it is invoked. But then, this does not require the programmer to write down the $\Sigma$ in the type signature of the lambda.

I hope the problem I have sketched here is clear. Any feedback is appreciated.

\[\] Paper discussed in this question

# Answer
> 4 votes
I think

```
(Lambda [c→End, x:Int] . (close v))

```

is indeed what you need to write. As you mention, it's "impossible" to write it because "c" is fresh. From my reading of it, it does seem to be a problem in the paper.

I don't think this is a very serious problem, tho, since the same problem appears in other systems and has known solutions (look at the papers about "Calculus of Capabilities" or "Alias Types", for example).

* if, as you do in your own syntax, you rely on type-inference, the problem disappears: the type inference can write the "c" since by that time it is known.
* you can change `accept` and `request` to return two things: a type `c` and a value of type `Chan C`. I.e. introduce "channel type parameters". Indeed `Chan c` is a *singleton type*, so you need `c` to be able to parameterize over `c` in order to be able to do anything useful.

---
Tags: type-checking
---


# Question
Title: Balanced allocation-Hash table- overflow probability
My question is related to this: Hash-Table in Practice

---

In \[1\] page 7, it is said that if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt\[2\]{(\frac{n}{k})\log k}+\log k)$ elements with a high probability.

**Question 1**: Why is $O()$ used in the above estimation?

**Question 2**: Does it mean the probability that a bin contains more than the above value is negligible?

---

\[1\]. http://www.pinkas.net/PAPERS/FNP04.pdf

# Answer
> 3 votes
A more formal statement of the claim is as follows. There is a constant $C \> 0$ and for each $k$, a function $\epsilon(n)$ satisfying $\lim\_{n\to\infty} \epsilon(n) = 0$, such that if you throw $n$ balls into $k$ bins, then with probability at least $1-\epsilon(n)$ the contents of each bin is at most $ \frac{n}{k} + C(\sqrt{(\frac{n}{k})\log k}+\log k)$.

---
Tags: algorithm-analysis, data-structures, probability-theory, hash-tables
---


title: Union grouping in bipartite graphs?

text:
# Question
Title: Union grouping in bipartite graphs?
I'm trying to figure out a good (and fast) solution to the following problem:

I have two roles I'm working with, let's call them *players* and *teams* having many-to-many relationship (a player can be on multiple teams and a team can have multiple players). I'm working on creating a UI element on a form that allows a user to select multiple teams (checkboxes). As the user is selecting (or deselecting) teams, I'd like to display the teams grouped by the players.

So for examples:

1. If the selected teams have no common players, each team will have its own section.
2. If the user selects two teams and they have the same players, there would be one section containing the names of the two teams and all the players.
3. If TEAM\_A has players \[1, 2, 4, 5\] and TEAM\_B has players \[1, 3, 5, 6\]. There would be the following sections: SECTION\_X = \[TEAM\_A, TEAM\_B, 1, 5\], SECTION\_Y = \[TEAM\_A, 2, 3\], SECTION \_Z = \[TEAM\_B, 3, 5\]

I hope that's clear. Essentially, I want to find the teams that players have in common and group by that. I was thinking maybe there is a way to do this by navigating a bipartite graph? Not exactly sure how though and I might be overthinking it. I was hoping to do this by creating some type of data structure on the server and using it on the client. I would love to hear your suggestions and I appreciate any help you can give!

# Answer
> 2 votes
I'll present an algorithm by example. Initialize a list of lists containing a list containing all of the players.

```
[[1, 2, 3, 4, 5, 6]]

```

For the first team, `TEAM_A`, replace each list by two lists, where the first list contains `TEAM_A` and the players on `TEAM_A` and the second list contains the players not on `TEAM_A`. Duplicate all of the existing team entries in both lists (none here).

```
[[TEAM_A, 1, 2, 4, 5], [3, 6]]

```

Discard all lists with no players (none here). For the second team, `TEAM_B`, replace each list by two lists, where the first list contains `TEAM_B` and the players on `TEAM_B` and the second list contains the players not on `TEAM_B`. Duplicate all of the existing team entries in both lists.

```
[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6], []]

```

Discard all lists with no players.

```
[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6]]

```

Well implemented, this should run in time proportional to the product of the number of teams and the number of players.

# Answer
> 1 votes
I'm assuming you want to maintain this data structure (essentially a Venn diagram) as edges are inserted and deleted. Maintain a hash table with the current regions, which is initialized as empty; each region contains a list of players using an appropriate data structure. For each player, maintain a pointer to its region.

When adding an edge connecting player $p$ to team $t$, locate the current region $R(p)$, and then:

1. Remove $p$ from $R(p)$. If $R(p)$ becomes empty then remove $R(p)$.
2. If $R(p) \cup \\{t\\}$ doesn't exist, add it. Then add $p$ to $R(p) \cup \\{t\\}$.
3. Assign $R(p) \cup \\{t\\}$ as the current region of $p$.

Deleting an edge is very similar and left to you.

---

There is also a simple offline solution. For each player $p$, calculate all teams $R(p)$ it belongs to. You get a list of pairs $(p,R(p))$, which you sort according to the second coordinate (either using a comparison-based sorting algorithm, or using radix sort). Now read off the regions. (When using radix sort, this is identical to David Eisenstat's suggestion.)

---
Tags: graphs, data-structures, bipartite-matching
---


title: Infinite Union of non-regular languages

text:
# Question
Title: Infinite Union of non-regular languages
Is infinite union of non-regular languages $L\_i$ that form a chain such that $L\_i\subseteq L\_{i+1}$ always non-regular?

Or is there a possibility that it be ever regular?

Is there an easy way to see this?

# Answer
> 2 votes
Let $L$ be a non-regular language over $\Sigma$, and let $w\_1,w\_2,\ldots$ be an enumeration of $\Sigma^\*\setminus L$. Define $L\_i = L \cup \\{ w\_j : j \geq i \\}$. Each $L\_i$ is non-regular (why?), $L\_i \subset L\_{i+1}$, and $\bigcup\_i L\_i = \Sigma^\*$.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: A Myhill-Nerode type characterization of the regular languages using fooling sets?
Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition.

Let $L$ be a language. A set of strings $S$ is called *pairwise distinguishable relative to $L$* if for any two distinct strings $x, y \in S$, there is a string $w \in \Sigma^\*$ such that exactly one of $xw$ and $yw$ belongs to $L$.

Assuming the axiom of choice, the Myhill-Nerode theorem can be framed in terms of pairwise distinguishable sets:

> *Theorem*: let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is pairwise distinguishable relative to $L$.

Now, let's consider a related definition. If $L$ is a language, a set $S \subseteq \Sigma^\* \times \Sigma^\*$ is called a *fooling set for $L$* if for any distinct pairs $(x\_i, y\_i), (x\_j, y\_j) \in S$, then $x\_i y\_i \in S, x\_j y\_j \in S$, and at least one of $x\_i y\_j$ and $x\_j y\_i$ isn't in $L$.

I'm curious whether the following statement is true:

> *Conjecture:* let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is a fooling set for $L$.

I can prove one direction of this using the Myhill-Nerode theorem: if there is an infinite fooling set $S$ for a language $L$, then we can take the first halves of each pair in $S$, gather them into a set $S'$, and we'll have an infinite set $S$ that is pairwise distinguishable relative to $L$, so $L$ is nonregular.

However, I keep getting stuck trying to go the other way. I'm not sure how to show that if $L$ is nonregular, then there must be an infinite fooling set for $L$. The equivalent direction of the Myhill-Nerode theorem follows by the contrapositive and the fact that the binary relation "is indistinguishable relative to $L$" is an equivalence relation. We don't - I believe - have a similar equivalence relation when it comes to fooling sets.

Does the other direction of implication hold here? Or is this a strictly weaker criterion than the Myhill-Nerode theorem?

Thanks!

# Answer
Your conjecture is refuted by the language $\\{ 0^n : \text{$n$ is not a power of $2$}\\}$. Let $\\{(x\_i,y\_i) : i \in \mathbb{N}\\}$ be an infinite fooling set for this language. We can identify $x\_i,y\_i$ with integers. These pairs have to satisfy the following conditions:

1. $x\_i + y\_i$ is not a power of $2$.
2. For each $i \neq j$, either $x\_i + y\_j$ is a power of $2$ or $x\_j + y\_i$ is a power of $2$.

Color $\mathbb{N}^2$ with two colors according to whether $x\_i + y\_j$ is a power of $2$ or $x\_j + y\_i$ is a power of $2$, where $i \< j$. Ramsey's theorem shows that without loss of generality we can assume that for all $i \< j$, $x\_i + y\_j$ is a power of $2$.

If $x\_i = x\_j$ for $i \< j$ then $x\_j + y\_j$ is a power of $2$, contradicting (1) above. Similarly, if $y\_i = y\_j$ for $i \< j$ then $x\_i + y\_i$ is a power of $2$, contradicting (1) above. Thus all $x\_i$ are distinct and all $y\_j$ are distinct.

Assume without loss of generality that $x\_1 \< x\_2$. Let $x\_1 + y\_3 = 2^a$ and $x\_2 + y\_3 = 2^b$. Choose $j$ so that $y\_j \> 2^b$. Let $x\_1 + y\_j = 2^c$. Then $2^c \< x\_2 + y\_j \< 2^c + 2^b \< 2^{c+1}$, and we obtain a contradiction.
> 2 votes

---
Tags: regular-languages, communication-complexity
---


# Question
Title: Lower bound for comparison algorithm - checking whether permutation is odd or even
I consider problem: proving lower bound for comparison algorithm that check whether permutation is odd or even.
I know that this bound is $\Omega(n\lg n)$.

Could you give me a clue ?

# Answer
> 2 votes
Hint: Show that if you know the parity of the input permutation then you know the entire permutation, and so you can sort the list.

In more detail, the information that you have at any leaf of the decision tree can be represented as a partial order on the elements. Show that if this partial order is not linear then it has a linear completion which is an odd permutation and another linear completion which is an even permutation.

---
Tags: algorithms, algorithm-analysis, permutations
---


# Question
Title: What real-world computer languages cannot be described by deterministic grammars?
Are there any examples of real-world computer languages that are non-deterministic?

By computer languages I include programming languages, markup languages, query languages, modeling language, transformation languages, etc.

By non-deterministic I mean they cannot be parsed with deterministic grammars.

# Answer
> 6 votes
Yes. Many modern programming languages have this property, including Algol 60, C, and C++; see below for details.

---

Algol 60 famously had the dangling else problem, for some programs, it was ambiguous how they should be parsed (what parse tree should be result).

Many modern languages resolve this by picking a grammar that resolves the ambiguity in a particular way. However, this requires carefully constructing the grammar to eliminate ambiguity. Often the most natural way to write the grammar leads to a grammar that is ambiguous, and you have to transform the grammar to avoid the ambiguity.

Another approach is to use a GLR parser, which can handle these grammars. Then you can check at runtime whether there are multiple possible parsers, and resolve the ambiguity.

---

Another classic example is the C and C++ programming languages. The reference grammar for C is not context-free, because when you see a name, you need to know whether it is the name of a type or of a variable to know how to parse the statement. For instance, consider the expression

```
(A)*B

```

If `A` is a variable, this is the multiplication of two variables and is equivalent to `A*B`. However, if `A` is the name of a type, then this is a pointer dereference and type-cast (so `B` is a variable name that holds a pointer type), and equivalent to `(A) *B`.

Similarly,

```
A*B;

```

could be either a variable declaration (if `A` is the name of a type, this is declaring a variable named `B` whose type is pointer-to-`A`) or a multiplication (if `A` and `B` are the names of variables).

Compilers typically fix this by including extra code that "goes outside" the language of pure context-free grammars. They keep track of all variable names and type names in scope, and use this to guide parsing in case of this ambiguity. See the lexer hack.

---

See also LL and LR in Context: Why Parsing Tools Are Hard and Bison's manual pages on its GLR parser (which includes a discussion of another ambiguous case in the C++ grammar).

---

Lastly: I think the question has some confusion about the difference between ambiguity vs non-determinism. Automata and languages can be deterministic/non-deterministic, but not grammars. Grammars and languages can be ambiguous/unambiguous. See Are there inherently ambiguous and deterministic context-free languages? and Grammatical characterization of deterministic context-free languages and If a parser can parse a non-deterministic grammar, is the parser non-deterministic?. The above examples actually qualify both as ambiguous grammars and non-deterministic languages.

---
Tags: formal-grammars, programming-languages, nondeterminism
---


# Question
Title: Why is there no deterministic algorithm for determining the majority vote of a recursive 3 branch tree without inspecting all the leafs?
Say that we have nodes in a tree and it has a branching factor of 3. At the leaves we have a binary value 1 or 0 (which can be viewed as "votes"). Each parent computes the majority of its children and assigns itself that value ("vote").

What I want to show is that in the worst case, a deterministic algorithm will have to query the value of all of the $n = 3^h$ leaves in order to determine the value assigned to the root.

I do have the following solution which I am having a hard time understanding:

But that algorithm doesn't seem to work in some trivial cases (unless I misunderstood the algorithm).

Say that A just started querying the leaves. So it queries the first leaf and since nothing has been assigned, when it goes to its first ancestor such that at most 1 is determined, since none of his siblings (which in this case are the siblings of the parent of the leaf, the uncles) have been determine, then that leaf is arbitrarily assigned true. When it goes to the next leaf, one should assign it false so that one has to inspect the other leaf, but when if you follow what the adversarial algorithm does it doesn't work. It says to go to the parent of the currently queried leaf and in this case, since still, none of the siblings of the parent have been assigned anything, then one would arbitrarily choose true, which is bad, because it determines the parent to be true without looking at the last leaf node of that subsection!

I am wrong or am I misunderstanding what $B$ is suppose to do?

Why isn't it just optimal to always choose 1 0 1 or 0 1 0 or 1 1 0 or however A queries leaves, to make sure that it always sees two leaf, such that it has to see the other leaf no matter what (i.e. if A sees a 1 to make sure the next thing it sees in that sub section of the leafs to see a 0 etc). I don't understand why we need to consider ancestors. Why does that matter?

For completeness I will provide the full text:

# Answer
> 2 votes
Yes, you are misunderstanding the algorithm. While I explain your misunderstanding below, in general, when such a misunderstanding occurs, see if you understand what the algorithm is trying to do, and then try to match your understanding with what is written.

While there are numerous errors in textbooks, usually they are slight and easy to correct. Whenever an error seems to have occurred (which doesn't seem to be the case here), see if you can try to correct it by making some small change to the argument.

In this case, the first ancestor of the second leaf which has at most one sibling determined is the leaf itself, which has one sibling determined. According to the strategy, our answer to the second leaf would be complementary to our answer to the first leaf.

Your misunderstanding might stem from the fact that for you a node is not considered its own ancestor. However, for this strategy to work, a node must be considered its own ancestor, as your example shows. Presumably the text defined ancestor correctly to include the node itself, but even if it doesn't you could correct the proof by changing slightly the meaning of ancestor. This demonstrates my points above regarding reading mathematical texts.

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


title: Regular expression for do not contain

text:
# Question
Title: Regular expression for do not contain
What is regular expression for language that does not contain $1110$?

It is easy to guess for language that contains. The shortest way I know is go through DFA. Is there a better way?

# Answer
> 1 votes
One solution is $(0+10+110+1111^\*0)^\*1^\*$.

However, I don't see how this helps you understand anything. It is much better for you to come up with the answer yourself. As an exercise, you can try proving that this expression indeed works correctly. (Or uncover any mistake, as the case may be.)

---
Tags: regular-expressions
---


# Question
Title: How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?
Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example.

## What I am trying to achieve with one sentence

How can I answer the following question by using constraint programming:

> The Euclidean distances between a point $p\_4$ and points $p\_1(0,0)$, $p\_2(0,5)$ and $p\_3(5,0)$ are $5.00$, $3.16$ and $4.47$ respectively. Where is $p\_4$ on the $xy$-plane?

without using quadratic constraints?

## Very short version of the question

There are five points placed on a 2D plane.

We only know the pairwise distance between these points.

\begin{matrix} d\_{12} &= 5.00\\ d\_{13} &= 5.00\\ d\_{14} &= 5.00\\ d\_{15} &= 5.00\\ d\_{23} &= 7.71\\ d\_{24} &= 3.16\\ d\_{25} &= 4.47\\ d\_{34} &= 4.47\\ d\_{35} &= 3.16\\ d\_{45} &= 1.41\\ \end{matrix}

In addition, we know the coordinates of first three points.

\begin{matrix} p\_1 &= &(0,0)\\ p\_2 &= &(0,5)\\ p\_3 &= &(5,0)\\ \end{matrix}

And we want to find the coordinates of remaining two:

\begin{matrix} p\_4 &= &(3,4)\\ p\_5 &= &(4,3)\\ \end{matrix}

How can I formulate this problem without using quadratic constraints? Note that in order to impose the Euclidean distance between two points, we need to use square of differences.

## Detailed version of the question

I am trying to formulate the graph embedding problem as constraint satisfaction problem.

Graph embedding is simply assigning coordinates to the vertices of a graph by considering edge weights, where the weight $w\_{ij}$ of an edge $\\{i,j\\}$ determines the Euclidean distance between the nodes $i$ and $j$.

My decision variables are two arrays, $X$ and $Y$. $X\_i$ and $Y\_i$ are the $x$ and $y$ coordinates of node $i$.

The mathematical model can be written as:

given: $G = (V,E)$

decision variables: $X = \\{x\_1, \dots, x\_{|V|}\\}$; $Y = \\{y\_1, \dots, y\_{|V|}\\}$

subject to: $\forall \\{i,j\\} \in E$; $(x\_i-x\_j)^2 + (y\_i-y\_j)^2 = w\_{ij}^2$

As discussed here,

> $(x\_i-x\_j)^2 + (y\_i-y\_j)^2 = w\_{ij}^2$

is a non-convex constraint. Is there any way to formulate this problem using convex constraints?

~~I came up with something: Assuming that the coordinates and the edge weights will be integers; I add two more decision variables: $O^X = \\{{O^X}\_{12}, {O^X}\_{13}, \dots, {O^X}\_{21}, {O^X}\_{23}, {O^X}\_{|V|(|V|-1)}\\} $ and $O^Y = \\{{O^Y}\_{12}, {O^Y}\_{13}, \dots, {O^Y}\_{21}, {O^Y}\_{23}, {O^Y}\_{|V|(|V|-1)}\\}$ where ${O^X}\_{ij}$ is the offset of the $x$ coordinate of a node $j$ with respect to node $i$. The same goes with $y$ coordinates as well. For instance, if $x\_i = 3$, $y\_i = 4$, ${O^X}\_{ij} = 2$, ${O^Y}\_{ij}j = -1$ then $x\_j = 5$ and $y\_j = 3$. As for the constraints, I have written: \begin{matrix} \forall \\{i,j\\} \in E;\\ x\_j = x\_i + {O^X}\_{ij}\\ y\_j = y\_i + {O^Y}\_{ij}\\ |{O^X}\_{ij}| + |{O^Y}\_{ij}| = w\_{ij} \end{matrix} My logic behind that approach is as follows: Since all the coordinates are integers, we are able to assume that we place the graph on a grid. If the Euclidean distance between $i$ and $j$ is $2$, and $i$ is on $(x,y)$ point, then $j$ should be on one of the following: \begin{matrix} (x-2,&y+0)\\ (x-1,&y-1)\\ (x-1,&y+1)\\ (x+0,&y-2)\\ (x+0,&y+2)\\ (x+1,&y-1)\\ (x+1,&y+1)\\ (x+2,&y+0) \end{matrix} Of course, this is just an approximation to the actual solution. However, the tool I work with (IBM ILOG CPLEX) does not give a solution. I think I am mistaken somewhere. \**Note:\** The above model (entitled as "I came up with something" is \**not\** what I am trying to achieve. However, I could not find a better way to impose convex constraints.~~

# Answer
> 4 votes
**You can't.** You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear.

---

That said, you *can* solve your one-sentence question directly, if you remove the requirement to use constraint programming. The basic technique is to use triangulation. I'll illustrate this below.

Suppose that you know point $p\_1$ is at $(0,0)$ and point $p\_2$ is at $(0,5)$, and you know $d(p\_1,p\_4)=r$ and $d(p\_2,p\_4)=s$ where $r,s$ are given; you want to find the location of $p\_4$. This can be found using some simple algebraic manipulations. Let $p\_4$ be at coordinates $(x,y)$. Then by the definition of the Euclidean distance, we have

$$\begin{align\*} r^2 &= x^2 + y^2\\ s^2 &= x^2 + (y-5)^2. \end{align\*}$$

Subtracting the two equations, we get

$$r^2 - s^2 = y^2 - (y-5)^2.$$

Simplifying the right-hand side and then solving for $y$, we find

$$y = (r^2 - s^2 + 25)/10.$$

Plugging this into the definition of $r$, we also find

$$x = \pm \sqrt{r^2 - y^2}.$$

Thus, in this way you can compute the coordinates $(x,y)$ of $p\_4$ (up to reflection) from the distances $r,s$ using a bit of simple algebra.

So, if you have a point $p\_4$ at some unknown location, and you know its distance to two other points at known locations, you *can* find the location of $p\_4$ using triangulation. Strictly speaking, we have found two possible candidates for the location of $p\_4$ (modulo a reflection across the line from $p\_1$ to $p\_2$), but if we know the distance from $p\_4$ to any third point we can try both possibilities and figure out which one of those two candidates is correct.

---

The same techniques can be used to solve your "very short version of the question". We know the location of $p\_1,p\_2$, and for each other point, we know its distances to $p\_1$ and $p\_2$, so we can calculate its location. Again, the problem becomes simple if we are allowed to use algebraic manipulations, rather than being forced to express it as a constraint system.

---

Your "detailed version of the problem" is a different problem entirely. If you have a complete graph -- or you have three points that are connected to all other points -- you can use the techniques outlined above. (You can fix locations for those three points, and then derive the location of all other points using the methods above.)

But if you have an arbitrary graph, the above techniques might not be enough. I don't believe your general problem can be expressed as a constraint program with only convex constraints: I think it's a non-convex problem. I don't have a proof of that, though.

# Answer
> 1 votes
the 2d case of "graph embedding" is also known simply as "graph drawing" and there is a very wide variety of techniques. the most common is probably force directed graph drawing. however heres a basic survey/ slide show that describes CSP, LP, ILP techniques in general. again there is large diversity and there does not really seem to be a unique or standard way to apply them in this area. the techniques generally find approximate solutions that roughly correlate edge weights to Euclidean distances (basically your problem). it is up to the designer to balance tradeoffs in this accuracy with other constraints of the drawing. some particular area of this research may better match your requirements if you are better able to specifically/ define/ articulate them and looking at other standard/ "typical" algorithms in the area can help you do that.

---
Tags: graphs, weighted-graphs, modelling, constraint-programming
---


title: Kleene plus in Thompson's construction

text:
# Question
Title: Kleene plus in Thompson's construction
**Is there a direct way to represent Kleene plus(+) using Thompson's construction algorithm?**

When I studied Thompson's construction I learned how to transform concatenation, union and kleene star of regular expresions directly into a NFA.

In wikipedia(and other websites) I found the same thing I learned in college(nothing about Kleene plus):Thompson's construction

In a non-direct method we can always transform $R^+$ in $RR^\*$ and then use Thompson construction.

There is a website that transform regular expressions into NFA. They claim to use Thompson-McNaughton-Yamada algorithm. Here they transform $a^+$ into:

Is this some kind of extension of Thompson's construction algorithm?

# Answer
It's technically an "extension" in the sense that Ken Thompson's original paper (ACM DL subscription required) doesn't mention it. This is presumably because his regular expression compiler didn't support "+" syntax in 1968.

However, pretty much every textbook presentation of Thompson's algorithm (e.g. see Bruce Watson's 1995 review paper on FA construction) mentions it. It's likely that no one person "extended" the method in Thompson's paper, or the "extension" was done by Thompson when he decided to support "+".
> 6 votes

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


# Question
Title: Space complexity of directed and undirected graph
I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then:

$$|E|\text{ close to }|V|^2$$ else if the graph is sparse then:

$$|E|\text{ is much less than }|V^2|$$

According to me the above two relations makes sense in respect of a complete graph where the total number of edges is $\frac{(V)\*(V-1)}{2}$ hence, $E = O(V^2)$.

Hence, we choose adjacency list representation where the length of the list is $\text{2|E|}$ for undirected graph and $\text{|E|}$ for directed graph. After that he simple concludes that space requirement for the adjacency list representation is $\Theta(V+E)$. I am really stuck on how he came to this conclusion without any explanation. According to me it should be $O(V\*(V-1))$ because for each vertex the maximum possible edge is $V-1$. What I am doing wrong?

# Answer
> 6 votes
It's hard to know for sure from what you've written, but I suspect what you're doing wrong is that you're considering what the space requirement would be for a complete graph. For a complete graph, the space requirement for the adjacency list representation is indeed $\Theta(V^2)$ -- this is consistent with what is written in the book, as for a complete graph, we have $E=V(V-1)/2 =\Theta(V^2)$, so $\Theta(V+E)=\Theta(V^2)$.

However, you shouldn't limit yourself to just complete graphs. There are other graphs that aren't complete, and have fewer edges than the complete graph. In general, the space for the adjacency list representation is $\Theta(V+E)$; this fact holds for all graphs, regardless of how many edges they have.

Why is this true? It's because for each vertex you have a pointer to the head of a linked list. That's $\Theta(V)$ space for all of those pointers. Also, the total number of nodes across all the linked lists is equal to $2E$, as each edge $(u,v)$ appears twice: once in the list for $u$, and once in the list for $v$. Therefore the space needed for all of the linked lists is $\Theta(E)$. Adding the space for the pointers and the space for the lists gives $\Theta(V+E)$.

---

You *could* say that the space requirement for the adjacency list is $O(V^2)$. It's true that it will never be more than that. However, for some graphs it will be much less. For instance, in a graph that is a simple path ($v\_1 \to v\_2 \to \dots \to v\_n$), there are $V$ vertices and $E=V-1$ edges in total. For that graph, the adjacency list representation will need $\Theta(V+E)=\Theta(V)$ space. Thus the $O(V^2)$ upper bound is very loose and too pessimistic.

# Answer
> 3 votes
You seem to be confusing the behaviour of a specific graph with the worst-case behaviour. A specific digraph has some given edge set $E$. $|E|$ could be as big as $|V|(|V|-1)$ but it could be much smaller.

To represent a specific digraph using adjacency lists, you need one list per vertex. The list for vertex $x$ contains every vertex $y$ such that $(x,y)$ is an edge. This means that every edge causes exactly one entry in the adjacency lists: it means that $y$ is in $x$'s list. So, for a specific digraph $(V,E)$, you need $|V|$ lists and the total number of entries will be $|E|$. That means the total cost is $|V|+|E|$. (Why not just $|E|$? Because some of the lists might be empty but it still takes some space to say "This list is empty.")

Now, in the worst case, $|E|$ could be as big as $|V|(|V|-1)$ but that's irrelevant: the space you need is $O(|V|+|E|)$, whether $|E|$ takes its maximum possible value or any other value.

---
Tags: graphs, data-structures, space-analysis
---


# Question
Title: NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)
The Google Hash Code 2015 Test Round (problem statement) asked about the following problem:

* input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in \mathbb{N}$
* output: the largest possible total area of a set of disjoint rectangles with integer coordinates in $M$ such that each rectangle includes at least $T$ marked squares and each rectangle has area at most $A$.

In Google's terminology, the grid is a pizza, the marked squares are ham, and the disjoint rectangles are slices.

We can clearly rephrase this problem to a decision problem by adding an additional input $n \in \mathbb{N}$ and let the answer be "is there a set of disjoint rectangles satisfying the conditions whose total area is at least $n$ squares".

**My question:** while the Google problem asked candidates to find a solution which is "as good as possible" for the computation problem on a specific instance, I think it is likely that the general problem (in its decision phrasing) is NP-complete. However, I cannot find a reduction to show NP-hardness. (NP-membership is immediate.) How to prove that this problem is NP-hard?

A few examples follow, to help visualize the problem. Consider the $4$ by $4$ grid $\\{0, 1, 2, 3\\} \times \\{0, 1, 2, 3\\}$, with marked squares $(1, 1)$, $(0, 2)$ and $(2, 2)$, represented graphically with `X` to indicate marked squares:

```
..X.
.X..
..X.
....

```

Set $A = 6$ (rectangles of at most $6$ squares) and $T = 1$ (at least one marked square per rectangle), an optimal solution (that covers the entire grid) is to take the following rectangles:

```
aaAa
bBcc
bbCc
bbcc

```

On the following grid, with $A = 3$ and $T = 2$:

```
XXX
.X.
...

```

One cannot do better than covering only three squares:

```
AAA
.X.
...

```

or

```
XBX
.B.
.b.

```

(remember that rectangles in the partition cannot overlap).

With other people looking at this question, we tried reductions from bin packing, covering problems, 3-SAT, and Hamiltonian cycles, and we didn't manage to get one to work.

# Answer
> 11 votes
This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT :

**Definition \[1-3 SAT problem\]:**
**Input:** A 3-CNF formula $\varphi = C\_1 \land C\_2 \land ... \land C\_m$, in which every clause $C\_j$ contains exactly three literals: $C\_j = (\ell\_{j,1} \lor \ell\_{j,2} \lor \ell\_{j,3})$.
**Question:** Does there exist a satisfying assignment for $\varphi$ such that each clause $C\_j$ contains exactly one true literal.

The problem remains NP-complete even if all literals in the clauses are positive (MONOTONE), if the graph built connecting clauses with variables is planar (PLANAR) and every variable is contained in exactly 3 clauses (CUBIC) (C. Moore and J. M. Robson, Hard tiling problems with simple tiles, Discrete Comput. Geom. 26 (2001), 573-590.).

We use $T=3, A=6$, and in the figures ham is represented with blue boxes (transgenic ham?), pizza with orange boxes.

The idea is to use tracks of ham that carry positive or negative signals; the track is made with an alternation of 1 and 2 pieces of hams placed far enough so that they can be covered exactly by one slice of pizza of area $A$; the segments of the track are marked alternately with $+$ or $-$, the track will carry a positive signal if slices are cut on the positive segments:

Each variable $x\_i$, which is connected to exactly 3 SAT clauses, is represented by three adjacent endpoints of three ham tracks (positive segment), in such a way that there are 2 distinct ways to cut it, one will "generate" a positive signal on all 3 tracks (it reppresent the $x\_i = TRUE$ assignment) the other a negative signal ($x\_i = FALSE$). Notice that we can also generate mixed positive and negative signals, but in that case *at least one ham remains uncovered*.

Each clause $C\_j$ of the 1-3 SAT formula with 3 literals $L\_{i,1}, L\_{i,2}, L\_{i,3}$ is simply represented by a single ham with three incoming positive segments of three distinct ham tracks; by construction *only one of the three tracks* carrying a positive signal can "cover" the ham-clause.

Finally we can build shift and turn gadgets to carry the signals according to the underlying planar graph and adjust the endpoints:

Suppose that the resulting graph contains $H$ hams. By construction every slice of pizza must contain exactly 3 hams, and in all cases every slice can be enlarged up to area $A$.

If the original 1-3 SAT formula is satisfiable then by construction we can cut $H /3$ pieces of pizza (with total area of $A H / 3$) and no ham remains uncovered.

On the oppposite direction, if we can cut $H /3$ pieces of pizza (with total area $A H / 3$) then no ham remains uncovered, and the signals on the variables gadgets and on the clauses are consistent: the ham on the clause is covered by exactly one positive slice coming from a positive variable, and every variable generates 3 positive signals or 3 negative signals (no mixed signals); so the cuts induce a valid 1-3 SAT assignment.

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


# Question
Title: How to denote the space complexity in terms of output
Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage an algorithm needs, i.e. if I have a Turing Machine with three tapes, one for the input, one for the computation, and one for the output, I would like to express the size of each one of them.

Is there a standard way of doing so? If so, is there a reference?

Currently I am using the symbol $\textrm{DATA}$. As an example consider function $list(n) = (1,\dots,n)$. The respective algorithm $List$ for computing the function $list$ is s.t. $\textrm{TIME}(List(n)) \in \mathcal{O}(n)$, since we need to write $n$ symbols, $\textrm{SPACE}(List(n)) = \mathcal{O}(1)$, since we only need to store the current symbol, and $\textrm{DATA}(List(n)) = \mathcal{O}(n)$, since the output is a vector of length $n$.

# Answer
> 2 votes
If your algorithm/TM is called $A$ and the input $x$, it is customary to denote the size of the output by using function and string notation, that is $|A(x)|$.

---
Tags: complexity-theory, space-complexity, notation
---


# Question
Title: How turing machine can be used as enumerator
Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an *enumerator*. I have studied the formal definition of enumerators that have no input. But I am unable to realize how a Turing machine can work as an enumerator for the language $L=\\{a^nb^n:n\geq0\\}$. Any help would be greatly appreciated.

# Answer
As your language $L$ is decidable ( lets its decider be $D$ ), you can build an enumerator $E$ for it ( which disregards its own input ). $E$ gives strings ( with alphabet being $\sum =\\{a,b\\}$ ) in increasing order ( lexicological order, which is possible as $\sum^{\*}$ is a countable set ) to $D$ and if $D$ accepts an input $E$ prints it, if $D$ rejects an input $E$ does not print it. If your language is undecidable but recognizable this method won't work for making an enumerator for such a language.
**EDIT**

If $L$ is a recognizable but not a decidable language we can build an enumerator for it in the following way. Let $R$ be the recognizer for the language and $E$ the enumerator. The strings in $\sum^{\*}$ are denoted as $s\_1,s\_2,....$ ( again in lexicological order ).

```
i = 1
while ( True )
  j = 1
  while ( j <= i )
     Give the string s_j as input to R and let R run for i steps,if R halts on
     s_j in at most i steps and accepts it, E prints the string s_j

     j = j + 1
  i = i + 1

```

Note with above method if a string belongs to $L$ it may be printed several times ( which can be avoided ). But unlike a decidable language there is no way to guarantee that strings are enumerated in lexicological order.
> 6 votes

# Answer
An enumerator is like a Python generator. It constantly enumerates words. There are several ways to define this formally, but suppose that the Turing machine has a special output tape, a special output state, and a special post-output state; whenever the Turing machine reaches the output state, the word on the output tape is output, and the Turing machines continues its operation in the post-output state. In this way, a Turing machine can output many words — possibly infinitely many. We say that the machine *enumerates* these words. In order to enumerate your language $L$, it can, for example, do the following:

* Output the empty word.
* Output the word $ab$.
* Output the word $aabb$.
*

Continuing in the same way, the machine eventually outputs every word of the form $a^nb^n$.
> 2 votes

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


title: Distance vector in a weighted graph

text:
# Question
Title: Distance vector in a weighted graph
I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv\_i$ is the shortest distance from $1$ to $i$. All edge weights are positive integers. I have to show that every distance vector $Dv$ satisfies:

1. $Dv\_1 = 0$.
2. For all $j \neq 1$ there exists $i$ such that $Dv\_j = Dv\_i + w(i,j)$.
3. For all $i,j$ it holds that $Dv\_j \leq Dv\_i + w(i,j)$.

I think that 1 is trivial: from 1 to 1 you have no distance. But the rest? Can you give me an idea how to prove 2 and 3?

# Answer
> 1 votes
Hint for 2: If $1,\ldots,i,j$ is a shortest path from $1$ to $j$ then $1,\ldots,i$ is a shortest path from $1$ to $i$.

Hint for 3: If $1,\ldots,i$ is a path from $1$ to $i$ then $1,\ldots,i,j$ is a path from $1$ to $j$.

In both cases $\ldots$ represents some list of vertices.

---
Tags: algorithms, graphs
---


title: Number of states in classical planning

text:
# Question
Title: Number of states in classical planning
With reference to the Heuristics section of Classical planning in *Artificial Intelligence: A Modern Approach* by Russell and Norvig, there is a question: consider an air cargo problem with 10 airports, 50 planes, and 200 pieces of cargo. Each plane can be at one of 10 airports and each package can be either in one of the planes or unloaded at one of the airports. So there are 5010 × 20050+10 ≈ 10155 states.

I think it should be 1050 \+ (50+10)200 (each of the 50 planes can be in any of 10 places; each of the 200 packages can be in any of the 50 planes or unloaded at any of the 10 airports).

What is the actual number of states?

# Answer
You're both wrong. It should be $10^{50} \times (10+50)^{200}$. If you have $k$ objects, and there are $n$ possible places for each, there are $n^k$ possible combinations of ways for where to put each of them.

This probably doesn't really change the main point that I suspect the AI book was making: there are a lot of possible states, far too many to iterate over one by one.
> 2 votes

---
Tags: combinatorics, artificial-intelligence, planning
---


# Question
Title: Given a moving ball in a grid, which squares does the ball reach?
You are given an m x n grid. A dimensionless ball is placed at the centre of one of the grid squares and starts moving in one of 4 directions: north-east, north-west, south-east, or south-west. The ball continues moving until it reaches the edge of the board at which point, it bounces back in accordance with the laws of Physics.

Given m, n, the initial position and direction (NE / NW / SE / SW) of the ball, is it possible to determine whether the ball will ever reach a specified target grid square (x0, y0)?

It is possible to answer the question by exhaustively tracing the movement of the ball, but is there any easier more efficient alternative? Any pointers to related literature would also be much appreciated.

# Answer
Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds. You should keep a hash table of all states of the ball that have been seen before (where the state of a ball is the grid square it is in, and which direction it is heading); if you see it repeat a past state, then you know it will loop forever and you can stop tracing the movement any further. With this way, tracing the ball's movement will take at most $O(mn)$ time in the worst case.

This can be sped up by using a little bit of simple algebra to calculate "given the current state, what's the next wall the ball will hit?" in $O(1)$ time -- that will be faster, but not easier.

---

There is a more elegant and efficient solution, based upon number theory and on Tom Van der Zanden's technique of extending the grid infinitely.

Imagine a parallel universe where ball travels in a straight line in an infinite grid; as Tom says, bouncing off the walls in our universe is equivalent to continuing in a straight line in the parallel universe. This is the first insight we will use.

Let's work out the implications of this insight. In our universe the ball starts at some initial coordinate $(x\_0,y\_0)$, moving NE, and we want to know if will ever reach coordinate $(x',y')$. What does this mean in the infinite universe? Well, imagine placing mines at coordinates $(x',y')$, $(x',2n-y')$, $(x',y'+2n)$, $(x',4n-y')$, ..., $(2m-x',y')$, $(2m-x',2n-y')$, ... -- in particular, at coordinates $(2im \pm x',2jn \pm y')$ where $i,j$ range over all integers. Then I claim that the ball will eventually reach coordinate $(x',y')$ in our universe if and only if the ball will eventually hit a mine in the parallel universe. So our problem reduces to asking: in the parallel universe, will the ball ever hit a mine?

The second insight is that we can use number theory to answer that question. In particular, after $t$ units of time, the ball will be at position $(x\_0+t,y\_0+t)$ in the parallel universe. We want to know whether there exists any integers $t,i,j$ such that $x\_0+t = 2im \pm x'$ and $y\_0+t = 2jn \pm y'$. Re-arranging these equations and using the language of modular arithmetic, we are asking whether there exists an integer $t$ such that both of the following equations hold:

$$\begin{align\*}t &\equiv \pm x' - x\_0 \pmod{2m},\\ t &\equiv \pm y' - y\_0 \pmod{2n}.\end{align\*}$$

Now we're all set to apply number theory. In particular, this is set up perfectly to apply the Chinese remainder theorem. Define $g = 2 \gcd(m,n)$. Then the above system of equations has a solution in the integers if and only if

$$\pm x' - x\_0 \equiv \pm y' - y\_0 \pmod{g}.$$

In other words, we should check the following four conditions:

* $x'-x\_0 \equiv y' - y\_0 \pmod{g}$
* $-x'-x\_0 \equiv y' - y\_0 \pmod{g}$
* $x'-x\_0 \equiv -y' - y\_0 \pmod{g}$
* $-x'-x\_0 \equiv -y' - y\_0 \pmod{g}$

If any of those four conditions holds, then there is a solution to the above system of equations and thus in the parallel universe the ball will hit some mine; if none of those four conditions holds, then the ball will never hit any mine. (These 4 conditions are the relevant conditions if the ball is initially travelling NE. The other directions can be handled symmetrically with a similar set of 4 conditions.)

Rephrasing in terms of the original problem, we get a solution to the original problem that is easy to implement and runs in $O(1)$ time. We compute $g=2 \gcd(m,n)$ and check the four conditions in the bullet list above. If any of the four conditions holds, then the answer is yes: the ball will eventually reach the point $(x',y')$. If none of the four conditions holds, then the answer is no: the ball will never reach the point $(x',y')$.
> 6 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Naive Bayes where Feature Space is LDA Output
I understand that the output for Latent Dirichlet Allocation is a distribution over K topics.

Suppose I have a Dx(K+1) matrix, where rows are documents and columns are the topic distribution + one column for class. For example, each row represents one movie review. The first K columns represent the topic distribution of the document, and the last column is the classification of this document. For example, if K=5, one row may read as:

2 | 0.25 | 0.4 | 0.1 | 0.15 | 0.1 | 1

where moview review 2 had 25% of the text about topic 1 (pleasure), 40% topic 2 (discontent), 10% topic 3 (personal feelings) ... and the classification of this document was to class #1.

How would I go about creating a Naive Bayes Classifier using this data?

Typically, I have used a Gaussian Naive Bayes where the feature space is iid over normally distributed variables, but this assumption I do not believe makes sense for LDA output. Would I need to assume the features are the individual columns distributed in a particular way (say a Dirichlet probability)?

This exercise is more for proof of concept to use Naive Bayes. I want to use, say 60%, of the data to construct a Naive Bayes Classifier and test the accuracy of the remaining 40%. My main concern is to how to define the PDF for the Naive Bayes Classifier.

# Answer
> 0 votes
The topic scores (the numbers in the first $K$ columns) come from a Dirichlet distribution. The marginals of the Dirichlet distribution are a beta distribution.

Therefore, it would be reasonable to model the distribution on each feature as beta-distributed, not normally-distributed. With this adjustment, all the math for Naive Bayes goes through.

---

Let me flesh this out. Given some data $x=(x\_1,\dots,x\_k)$, the Naive Bayes classifier computes the likelihood of a class $c$ as

$$L(c) = P(c) \prod\_{i=1}^k P(x\_i | c).$$

Here $x\_i$ is the value in the $i$th column (the estimated probability the document came from topic $i$). Given the comments above, we will estimate that the conditional distribution $P(x\_i | c)$ has a beta distribution with some parameters, i.e., $\text{Beta}(\alpha\_i,\beta\_i)$. Thus,

$$P(x\_i | c) = {1 \over B(\alpha\_i,\beta\_i)} x\_i^{\alpha\_i-1} (1-x\_i)^{\beta\_i-1}$$

for some parameters $\alpha\_i,\beta\_i$.

Where do we get the parameters from? From the training set, as usual. In other words, we take from the training set just the documents that are classified with class $c=0$, and from those, we fit a beta distribution to the conditional distribution $P(x\_i | c=0)$ and find the parameters $\alpha\_i,\beta\_i$ that make the beta distribution best fit the observed values of $x\_i$ (out of the training documents classified as class $c=0$). We use those as our estimate for $P(x\_i | c=0)$. How do we find $\alpha\_i,\beta\_i$? By using standard methods for estimating the parameters of a beta distribution, given a bunch of observations drawn from it.

Then, we do the same for the documents in the training set that are classified as $c=1$, to fit a beta distribution and use that as the distribution for $P(x\_i | c=1)$.

Finally, once you have formulas for $P(x\_i | c=0)$ and $P(x\_i | c=1)$, you plug that into the definition of $L(c)$ above and use that in the Naive Bayes classifier just as normal.

---
Tags: machine-learning
---


title: Running time of amstrong algorithm

text:
# Question
Title: Running time of amstrong algorithm
I have a problem how to find best, worst, average case in armstrong number algorithm?

Here the pseudo-code :

```
Declaration:
      n : integer
      Sum : integer
      Temp : integer
      Rem  : integer
Algorithm:
      Input(n)
      Temp <-- n
      Sum <-- 0
      Rem <--- 0
      While ( n != 0 ) do
               Rem <-- n mod 10
               Sum <-- Sum + Rem * Rem * Rem
               n <-- n / 10
      Endwhile

      if ( Sum = n ) then
         output (n ," is Armstrong number")
     else
         Output(n," is not armstrong number")
         Endif

```

I find

**Best-case** : Tmin(n) = 3,

**Worst-case** : Tmax(n) = 3n,

**Average-case** : Tavg(n) = 3 \[ **n(n+1)/2** \] / n = 3(n+1)/2 = 3n+3/2

**Sn= n(n+1)/2** The sum of the natural numbers from 1 to n

Thanks for you help.

# Answer
> 0 votes
Essentially, the only thing that affects the run time of your algorithm is the loop. This will iterate for as many times as it takes to get from $n$ to 0 by dividing $n$ by 10. So we're asking, how many times will it be before $n, n/10, n/100, n/1000, \dotsc$ gets to 0? That is, when is $n/10^k = 0$? Clearly, when $k=\log\_{10}n$. The loop is unaffected by any difference between the $n$ values, as long as they have the same number of decimal digits, so best-case time = worst-case time = average-case time = $3\log n$ plus some constant overhead for setting the variables and displaying the output.

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


# Question
Title: Formal construction of PDA intersecting a DFA
Given the PDA $P = (Q\_P,\Sigma,\Gamma\_P,\delta\_P,F\_P)$ and the DFA $D = (Q\_D, \Sigma, \delta\_D,q\_D,F\_D)$

What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$

I don't understand what the intersection of these two FAs represent, and my only guess at what the 6-tuple is would be something along the lines of: $P'=(Q,\Sigma,\Gamma,\delta,q\_0,F)$ such that:

$P=Q\_P$ x $Q\_D$
$\Sigma = \Sigma$
$\Gamma =..?$
$\delta =..?$
$F =..?$

The only other resource on this site I found that is remotely similar to this question is:
Cartesian construction of PDA and DFA

However, I didn't find the answer to be sufficient.

# Answer
The idea of the intersection is to construct a PDA that keeps track of the original PDA's state in the first component of the state (in the $Q\_P$ component) together with the stack, and keep track of the DFA's state in the $Q\_D$ component. If both accept by final state, you just need to accept if both automata end up in a final state.
> 4 votes

# Answer
The formal description of the new machine is a bit involved, but the basic idea is simple: for every new input character, do the original PDA's move and the DFA's move in parallel (i.e., work in the context of the Cartesian product of the two machines). If they both lead to an accept state, the new machine should accept; if one or the other doesn't accept, then the new machine won't. I'll leave the details to you.
> 2 votes

---
Tags: formal-languages, finite-automata, closure-properties, pushdown-automata
---