# Question
Title: What is the relation between First Order Logic and First Order Theory?
I thought that any FOT is a subset of FOL, but that does not seem to be the case, because FOL is complete (every formula is either valid or invalid), while some FOT (like linear integer arithmetic) is not complete.

So, is FOL more expressive than any of FOT? Or incomparable?

Also, the statement "there are statements that are valid in LIA but cannot be proved using axioms of LIA" is weird. How can the statement be valid if we cannot prove its validity? I always thought that if you cannot prove the validity of the statement, then you cannot claim it is valid.

# Answer
First-order logic is a mathematical subject which defines many different concepts, such as *first-order formula*, *first-order structure*, *first-order theory*, and many more. One of these concepts is *first-order theory*: it is a set of first-order formulas. Often we consider the first-order theory generated by a finite number of axioms and axiom schemes. Such a theory is *closed with respect to logical derivations*, and we usually only consider theories satisfying this condition.

A first-order theory is *complete* if for every statement $\sigma$, it contains either $\sigma$ or its negation. Not every theory is complete. Indeed, Gödel's incompleteness theorem highlights the fact that many interesting first-order theories are necessarily incomplete.

A *model* of a first-order theory is a valid interpretation of the theory (we leave the exact definition for textbooks). For example, the first-order theory of groups consists of all statements that follow from the group axioms. Every group is a model of the first-order theory of groups.

For every given model, very given sentence is either true or false. Gödel's completeness theorem states that if a first-order sentence is true in all models of a first-order theory, then it is provable from a finite number of sentences in the theory. For example, every first-order statement in the language of groups which holds for all groups is provable from the group axioms.

LIA is (presumably) a first-order theory which is interesting enough to be incomplete due to Gödel's incompleteness theorem. However, in the standard model – the "true" integers – every sentence is either true or false. In particular, if $\sigma$ is a statement such that neither $\sigma$ nor $\lnot \sigma$ belong to LIA, then either $\sigma$ or $\lnot \sigma$ holds for the true integers, but this fact isn't provable in LIA.
> 12 votes

# Answer
The phrase "first-order logic" has two meanings:

1. It is a chapter of mathematical logic in which we study certain kinds of formal systems and everything related to them.
2. It is a special kind of first-order theory, namely the one generated by an empty signature and an empty set of axioms.

Your question refers to the second meaning, but to understand this, we need to build things up:

1. There is a certain formal language called *the language of first-order logic*. Speaking informally, it is the stuff you can build from variables, equality, $\land$, $\lor$, $\lnot$, $\Rightarrow$, $\forall$ and $\exists$. This stuff is known as *first-order formulas*.
2. There is a certain formal system called *first-order logic* which tells us what it means that we *prove* a first-order formula. The system is given as a set of inference rules.
3. A *first-order theory $\mathcal{T}$* is given by:

* a *signature $\Sigma\_{\mathcal{T}}$* which consists from a set of constants, function symbols, and relation symbols. Think of these as extensions of the basic language of first-order logic. We call it the *language of $\mathcal{T}$*.
    * a deductively closed set of first-order formulas written in the language extended by the signature.

A set $S$ of formulas is said to be *deductively closed* if any application of inference rules of first-order logic to formulas in $S$ gives formulas which are again in $S$. In other words, $S$ contains all of its logical consequences. A common way of creating such a set $S$ is: start with some chosen set of formulas $A$, and add to it all of its logical consequences, and the consequences of those consequences, and so on. This is called the *deductive closure* of $A$. We often call the formulas in $A$ *axioms*.

A theory may or may not be complete. It is not important to know what "complete" means here, but it is important to know that the following can happen: we can have two sets of formulas $A$ and $B$, such that $A \subseteq B$, the deductive closure of $A$ is a complete theory, and the deductive closure of $B$ is *not* a complete theory.

We are now ready to answer your question. Let $T$ be the theory whose signature is empty and whose set of formulas is the deductive closure of the empty set. Let $P$ be the theory whose signature is that of Peano arithmetic (constant $0$, unary operation $S$, binary operations $+$ and $\times$) and the formulas are the deductive closure of Peano axioms. It is a fact that

1. $T$ is contained in $P$ (in fact $T$ is contained in every theory),
2. $T$ is complete,
3. $P$ is not complete.

The theory $T$ is popularly called "first-order logic", but this really is a misnomer. Some people are a bit more precise and call it "the pure theory of first-order logic".

In summary, your question revealed the following:

1. You did not know that "first-order logic" may refer to the theory with empty signature generated by the empty axioms.
2. A complete theory may become incomplete when we extend it.
3. You used the wrong definition of completeness. The correct definition is: a theory is complete if, every *sentence* or its negation is a theorem of the theory.

NB: a *sentence* is a closed formula (one that does not contain any free variables).

Lastly, let me address your question about validity:

* a formula is *provable* if there is a proof of it
* a formula is *valid* if it is true in every model

A basic meta-theorem about first-order logic is that every provable formula is valid. The reverse holds as well and is known as Gödel's completeness theorem.

However, it often happens that in some particular situation one purposely makes a mismatach between validity and provability for a good reason. For instance, if we limit attention to just *finite* models, then it may easily happen that there would be valid statements which have no proof. Why would one do that? In computer science it could be for algorithmic reasons, or because one is interested in a particular class of models only.

HYou say "the only way to know that a sentence is valid is to prove it". This may be the case at some informal level (I think God would disagree with you), but notice that any such proof of validity happens *outside* the theory, at the meta-level. Indeed, since establishing validity requires one to talk about *all models* this is certainly not something we would expect to perform inside the theory.
> 7 votes

# Answer
A minor clarification:

You may be thinking that the theory with empty signature is an empty theory, i.e contains no closed formulae. That is incorrect. First-order logic allows one to prove - *without appeal to axioms* \- certain closed formulae known as tautologies. These are 'true' due solely to their form; they have no meaningful content as such. Godel's Completeness Theorem then says that the collection of tautologies is complete - i.e, *all* closed formulae which are *valid* (i.e 'true in all models') are actually derivable in first-order logic. *\[The proof is interesting and decidedly nontrivial.\]*
> 3 votes

---
Tags: logic, first-order-logic
---


# Question
Title: Maximum flow with Edmonds–Karp algorithm
I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.)

If we first follow path **S - A - C - T** , we will get max flow equals to 1 as we cannot take path S - B - C - T (residual flow from C -- T became 0). I am also assuming that while doing BFS when we reach to t from c, we are stopping our BFS search and returning path. There is D left in the queue but we will ignore it as we have got one augmenting path. On next iteration we will move to B as S -- A edge residual capacity is 0.

If we first follow path as **S - A - D - T** and then **S - B - C - T** , we get max flow as 2.

I think, I am missing some basics, I belive algorithm does not dependend on which path I take first.

Thanks in advance.

# Answer
I'm sure you have a misunderstanding. Try simulating the Edmonds-Karp algorithm by hand on the first example, then edit the question to show the residual graph you've got after it finishes. I'm sure you'll find there remains an augmenting path from $s$ to $t$ in the residual graph. If you don't draw the residual graph explicitly, you might fail to notice the path -- you can't do this in your head without drawing the graph on paper.

Many students get tripped up by the fact that there might be an augmenting path in the residual graph that looks like it goes "backwards" in the original graph; that's OK, and it still counts as an augmenting graph.
> 3 votes

---
Tags: algorithms, graphs, max-flow
---


title: Recursive definition of Matrix

text:
# Question
Title: Recursive definition of Matrix
Like Linked-list for Array, is there a recursive counter-part for Matrix?

Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?

# Answer
> 7 votes
## Multiple Dimensions

For a recursive counterpart for matrices, we need dependent types.

Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of columns and likewise all columns need to have the same number of rows for a matrix to be (conventionally) meaningful. I mean, for example, usually no one thinks of, say, two rows that have two different length columns as being a matrix.

## A Quick Implementation

So for concatenation, we need to keep track of the lengths. We can do so by using a language that supports dependent types, such as Idris or Agda. Haskell can mimic them, but a difficult task onto itself. So here's a naive implementation in Agda.

```
data Matrix (A : Set) : (rows columns : ℕ) → Set where
  ∣_∣ : A → Matrix A 1 1
  _Φ_  : ∀ {r c₁ c₂} → Matrix A r c₁ → Matrix A r c₂ → Matrix A r (c₁ + c₂)
  _⊝_  : ∀ {c r₁ r₂} → Matrix A r₁ c → Matrix A r₂ c → Matrix A (r₁ + r₂) c

```

The first constructor embeds the type `A` into 1-by-1 matrices and the other two constructors are for horizontal and vertical concatenation. Notice that the natural numbers are used to keep the matrices meaningful. For example, you can stick two matrices side-by-side to produce a wider matrix precisely if the two have the same number of rows.

For example, the 2-by-2 identity matrix

```
id₂ : Matrix ℕ 2 2
id₂ = (∣ 1 ∣ Φ ∣ 0 ∣) ⊝
      (∣ 0 ∣ Φ ∣ 1 ∣)

```

## Map

In one of the above comments, you remark that its troubling that we cannot pattern match and define recursive functions. Well, we can :-)

For example, the usual map of lists has a matrix counterpart.

```
map : ∀ {A B} (f : A → B) → ∀ {c r} → Matrix A r c → Matrix B r c
map f ∣ x ∣ = ∣ f x ∣
map f (m Φ m₁) = map f m Φ map f m₁
map f (m ⊝ m₁) = map f m ⊝ map f m₁

toString : ℕ → String
toString zero = "Zero"
toString (suc zero) = "One"
toString _ = "just no"

map-test : map toString id₂ ≡ (∣ "One"  ∣ Φ ∣ "Zero" ∣) ⊝
                              (∣ "Zero" ∣ Φ ∣ "One"  ∣)
map-test = refl

```

## More Involved Example

As a more complicated example, let's consider matrices made by a single constant ---compare to Haskell's `repeat` operation that takes an element `e` and returns a list `[e,e,...,e]`.

```
 : ∀ {A} → A → ∀{r c} → Matrix A (suc r) (suc c)
 e {0} {0} = ∣ e ∣                     -- 1x1 singleton matrix
 e {0} {c + 1} = ∣ e ∣ Φ  e             -- row-vector of length r+1
 e {r + 1} {0} = ∣ e ∣ ⊝  e             -- column vector of length r+1
 e {r + 1} {c + 1} = (∣ e ∣ Φ  e) ⊝  e -- (∣ e ∣ ⊝  e {m} {0}) Φ  e {m+1}{c}

```

The last one says:

```
                   (    e  |  e   )
 e {r+1} {c+1} =  (  ------------- )
                   (  e {r} {c+1} )

```

Indeed any × matrix can be construed as the vertical concatenation of an -row vector above an (-1)× matrix ---note a recursion! In this case, our row vector is the element `e` followed by an `r`-row vector of e's.

Example usage:

```
test :  5 {2} {2}
   ≡   (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣)
test = refl

```

## Sources

Of course, the implementation was brief and just to answer your question. A more full account can be found in the elegant lecture notes of Richard Bird.

Hope this helps!

---
Tags: functional-programming, matrices, linked-lists
---


# Question
Title: Find all non-isomorphic graphs with a particular degree sequence
I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?

# Answer
To the best of my knowledge, nothing considerably better is known. For instance, your problem was part of the Combinatorics REGS 2012 program at Illinois.

With that being said, I can think of three possible engineering approaches that might work:

1. Use what you have (perhaps as a baseline for benchmarking other approaches).
2. Use the suggestion of Yuval: use the configuration model to generate all such graphs, and check for isomorphism between them. For instance, you can use nauty that is fast and highly optimized.
3. If your degree sequences are of length $n$ for some small $n$ (or you can afford to do a lot preprocessing), generate all $n$-vertex graphs. For this, you can either download them all from McKay's homepage, or use e.g., geng. If you have additional information, you might use an even more specific generator such as plantri (geng has options too). Once you have the graphs, iterate over them and check whether they have the right degree sequence.

By the way, Sage also has much of this functionality built-in, see e.g., here (for instance, search for "Generate all graphs with a specified degree sequence").
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: Complexity analysis of an unsolvable algorithmic problem?
In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned that any unsolvable problem would have a complexity of infinite.

However, this strikes me as strange. It feels intuitive to me to say that an unsolvable problem would have no complexity, as any attempt to solve it would be impossible. The quantity of infinity says to me that "if you had unlimited time, you could solve it", but what if it's a question that the answer simply cannot be computed for?

Is this O(infinity) concept common in algorithmic complexity analyses?

# Answer
Basically, this is a degenerate case. We can adopt the convention that the running time of any algorithm is $\infty$ (so its complexity is $\infty$), or we can adopt the convention that it doesn't have a complexity. For informal conversation, probably it doesn't matter much what convention you adopt, as long as it's clear which you're using and what you mean.

See also how to calculate time complexity of non terminating loops for discussion of the running time of an algorithm that never terminates, and What is the difference between an algorithm, a language and a problem? for background on the difference between the complexity of an algorithm vs the complexity of a problem.
> 2 votes

# Answer
Your instructor is right, and this seems like an odd choice.

$O(\infty)$ arises usually as a way to say "this algorithm may never terminate, it's awful, let's never use it."

**Big-O and Running Time**

First, what about big-O complexity of your problem? Well, problems don't have big-O complexity, algorithms do. So if there is no algorithm to solve your problem, then we can't talk about how many steps it takes an algorithm to solve your problem.

**Complexity Classes, P, NP, etc.**

But, what about complexity classes, NP-hard, etc?

The main classes are restricted to decidable problems. For example, $NP$ is the class of problems solveable by a Turing Machine running in non-deterministic polynomial time. But this is a subset of the class of solveable problems. Similar statements can be made about $P$, $EXP$, $PSPACE$, etc.

What about "hardness?" Can an undecidable problem be $NP$-hard? Yes, but not in an interesting way.

Informally, to show that a problem is $NP$-hard, we assume that we have an algorithm solving it, and we show that we can then solve another $NP$-hard problem in polynomial time with a polynomial number of calls to our algorithm.

But in your case, to do so is to assume that there is an algorithm solving an unsolveable problem. This means we've assumed a contradiction, so we can derive a polynomial time algorithm for some NP-hard problem, since we can derive literally anything from the contradiction. We've assumed False, and this provides us with no useful information.

**Summing Up**

The idea of standard complexity isn't even well-defined for an undecidable problem.

You problem will be in basically no complexity classes, but it will be Hard for almost every complexity class.
> 2 votes

# Answer
Do you want to talk algorithm analysis or complexity theory?

### Algorithms

*Every* algorithm has running time in $O(\infty)$ since that, by definition, means

$\qquad \exists\\, c, n\_0.\ \forall\\, n \geq n\_0.\ T(n) \leq c \cdot \infty$,

assuming a reasonable extension of $\leq$ to $\mathbb{R} \cup \\{\infty\\}$.

Every algorithm that *always terminates* has running time *not* in $\Theta(\infty)$; if one extends the definitions carefully enough, they have running time in $o(\infty)$.

Algorithms that do not terminate (sometimes) do not solve any problem (in a strict sense).

### Problems

The time "complexity" of a problem $P$ is the $\Theta$-class of the running time of a $\Theta$-time-optimal algorithm for $P$.

There *are no algorithms* for undecidable problems, so they do not have a complexity.

If you want to start thinking about what is possible with infinitely many monkeys, you should be aware that there are degrees of uncomputability; see the arithmetical hierarchy.
> 2 votes

# Answer
When dealing with undecidable problem, the correct way of classifying problems is *recursion theory* rather than *complexity theory*. For example, whereas a hard computable problem might be, say, NP-complete, a hard uncomputable problem might be $\Sigma\_1^0$-complete.

NP is just the first rung on the polynomial hierarchy, and is also known by the name $\Sigma\_1^P$. The recursion-theoretic analog (which of course predates the polynomial hierarchy) is the arithmetical hierarchy, of which $\Sigma\_1^0$ (which corresponds to the halting problem) is the first rung.
> 1 votes

---
Tags: complexity-theory, computability, asymptotics
---


# Question
Title: How can a Turing machine accept infinite number of inputs?
How it is possible for a turing machine to process an infinitely long input ?

# Answer
> 3 votes
It is possible for a Turing machine to process an infinite length input in finite time, if the language is such that we can determine if a string is accepted or not just by looking at a finite prefix. But the trouble is how are you going to initialize the input tape with an infinite input?

As for how Turing machine accepts infinite number of inputs, it is easy, it accepts them one at a time, for each input.

---
Tags: computability, turing-machines, computation-models
---


# Question
Title: How fast can one compute the power of a number?
Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \\{0\\}$ then how fast can one compute $x^k$?

---

If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many operations at maximum needed to compute powering of a number, i.e. $N^k$?

# Answer
There are several methods given in wikipedia article https://en.wikipedia.org/wiki/Exponentiation\_by\_squaring.

If both $x,k \in \mathbb{R}$, then you can compute $x^k$ as $e^{k \log x}$ as there are somewhat efficient algorithms for $e^x$ and $\log x$.
> 1 votes

---
Tags: time-complexity, runtime-analysis, polynomial-time, arithmetic, modular-arithmetic
---


# Question
Title: Travelling salesman very rough min and max estimates
Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the *minimum estimate is lower (or equal) to the actual distance* and that the *maximum estimate is higher (or equal) to the actual distance*.

EDIT: Metric TSP unfortunately does not apply. To add some context: I'm searching for non-dominated fronts (pareto fronts) for a Multiobjective TSP, e.g. optimizing for multiple variables like travel time *and* distance. I'm using NSGA-II which requires an upper and lower bound for each objective function, which translates into rough estimates for single-objective TSP, with the constraint that the upper estimate has to be higher than the real max distance and vice versa.

# Answer
It is conjectured (but unproven) that the Held-Karp relaxation (*not* the Held-Karp algorithm) has an integrality ratio of 4/3 (on metric TSP). Various proofs exists for even better bounds if some assumptions are made.

Practically it performs even better, gaps of ~2% are normal, and there is a lot of literature about adding more cuts that get that gap (typically) a fair way below 1%, but that would not fit with your goal of "fast and easy to implement" anymore. Just the basic degree constraints + lazy sub-tour elimination is, when using an existing LP solver, both fast and easy, and a lot better than taking one of the well known upper bounds and dividing them by their approximation ratio (which tends to be give terrible results, because they typically approximate much better than their worst case, resulting in an overly optimistic lower bound).
> 2 votes

# Answer
There are efficient constant-factor approximation algorithms for your problem, which are described (for example) on the Wikipedia page. Such an approximation algorithm usually returns a tour whose value is at most $C$ times the value optimal tour (and at least the value of the optimal tour), where $C$ is some small constant (for the Christofides algorithm, $C = 1.5$).
> 1 votes

# Answer
You can look on this lecture notes: TSP-Aprrox

If your Problem is a metric TSP than there is 2-approx (Using Minimum Spanning Tree) and 1.5-approx algorithm for minimum TSP.

If your problem is not metric then there is no constant- approx algorithm for minimum TSP

Max TSP is as hard as Min TSP and again for Metric TSP there are constant approx Algorithms. You can check for algo here
> 1 votes

---
Tags: graphs, optimization, approximation, traveling-salesman
---


# Question
Title: Give a function that is in EXPTIME but is not in O(2^n)
Give a function that is in EXPTIME but is not in O(2^n). Thanks.

# Answer
> 1 votes
There are many examples. You should check the definitions of $EXPTIME$ and $DTIME$ and also the time-hierarchy theorem.

$EXPTIME = \cup\_{k\in \mathbb{N}} DTIME(2^{n^k})$, and by time-hierarchy theorem $DTIME(2^n) \subsetneq DTIME(2^{n^2})$. Now construct a language following the proof of the time-hierarchy theorem that is in $DTIME(2^{n^2})$ and therefore in $EXPTIME$ but not in $DTIME(2^{n})$. This you should be able to do yourself.

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


title: Address space definition

text:
# Question
Title: Address space definition
I'm learning by my self about OS theory and I have some troubles to understand what is a process address space.
So far, I came across two definitions of what a process address space is:
1 - The set of virtual addresses available to a process. Hence the address space, would be the numbers from 0x0 to 0x7FFFFFFF.
2 - The virtual memory addressable by a process. I picture it as a set of cells with addresses from 0x0 to 0x7FFFFFFF.

I would like to know which one is correct?
This is important for me because I read sentences like "the address space is organized into pages of 4096 bytes" which makes me lean towards the second definition.

Thank you.

# Answer
The address space is the space (i.e., set) of addresses – see, e.g., Wikipedia. It's an abuse of terminology to claim that the address space is divided into pages. It isn't: it's the memory addressed by the addresses that's divided into pages.

(This confusion between addresses and the things referred to by addresses is common. How many times have you heard people say, "I'll give you my email" when they mean "I'll give you my email address"?)
> 1 votes

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Find k compatible objects with minimum total penalty
Assume we have a set of $n$ objects $X=\\{x\_1,x\_2,\ldots,x\_n\\}$, where each object $x\_i$ has a penalty $p\_i$. Additionally, we have a set of incompatibility constraints $C=\\{(x\_i,x\_j),\ldots\\}$, where a tuple $(x\_i,x\_j)$ says that object $x\_i$ is incompatible with object $x\_j$. The problem is to find a subset $Y$ of $k\<n$ compatible objects that minimize the sum of penalties, i.e. $\min\_{Y} \sum\_{x\_i \in Y} p\_i$. The objects in $Y$ need to be compatible, i.e. $\forall x\_i,x\_j \in Y: (x\_i,x\_j) \not\in C$.

Let me make an example. Assume we have 4 objects $X=\\{x\_1,\ldots,x\_4\\}$ with penalties $p\_1 = 2,\ p\_2 = 0.1,\ p\_3=3,\ p\_4=100$. Furthermore the following incompatibilities are given: $C=\\{(x\_1,x\_2),\ (x\_2,x\_3),\ (x\_3,x\_4)\\}$. The $k=2$ compatible objects that minimize the function are $Y = \\{x\_1,x\_3\\}$ with a total penalty of $5$. Object $x\_2$ with the least penalty is not part of the solution, because the only compatible object is $x\_4$ with a penalty $p\_4=100$.

I have two questions:

* Is this problem already known under some name or a variation of a known problem?
* Is there an efficient (polynomial time) algorithm to solve it?

# Answer
First of all you have to find if there exist independent sets of size $k$ and then select the one with the minimum penalty. We have maximum weighted independent problem (size of independent set is unconstrained), but I am not aware of any optimization problem which select exactly $k$-sized independent set and minimizes/maximizes the total weight.

The decision version of the optimization problem that you describe will be: Does there exist an independent set of size $k$ and penalty less than or equal to $P$.

We can reduce standard independent set problem to this problem by specifying the penalty of each vertex as 1 and $P = k$. Thus the decision version of the described optimization problem is NP-complete.

So there won't be polynomial time algorithm for the problem unless $P = NP$.
> 1 votes

# Answer
Well, the graph is obvious, isn't it? Independent set
> 1 votes

---
Tags: optimization, combinatorics
---


# Question
Title: How to find FOLLOW for variables which has next value ε
Its very easy to find FIRST in compiler design. Im finding difficult to find follow , suppose if we have one variable(say B) then we need to search the variable in the whole question .If there was a terminal or a variable after B (say Ba,BA) we can find it easily. but if we have epsilon (say Bε).How to find the follow for such values(Bε) and if there was ε in the same variable then we need to go to the next variable.then how to continue the problem. help me to find the solution for the following question.

# Answer
> 3 votes
For production of the form $A \rightarrow \alpha B \beta,\ FOLLOW(B) = FIRST(\beta)-\\{\epsilon\\}$.

If $\epsilon$ belong to $FIRST(\beta)$ or in case the production is of the for $A \rightarrow \alpha B$, whatever is in $FOLLOW(A)$ must be in $FOLLOW(B)$

**Exercise**

Find $FIRST\ \\&\ FOLLOW$ of all the symbols in the grammar $G = \\{\\{S,B,C\\},\\{a,b\\},P,S\\}$, where $S$ is the start symbol and $P$ is the set of productions given below.

\begin{align\*} S \rightarrow BC\\ B \rightarrow aB\ |\ \epsilon\\ C \rightarrow bC\ |\ \epsilon\\ \end{align\*}

Drop a comment in case you need a more detailed explanation. However, I encourage you to solve the exercise problem first.

---
Tags: compilers
---


# Question
Title: What is the effect of having a transition in an epsilon-NFA upon "$\epsilon$,0"?
When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states?

Does it simply mean that the $0$ is ignored, since it is technically in both states at the same time?

# Answer
I suggest you review the definition of epsilon-NFA, especially the definition of when an epsilon-NFA accepts a word.

To answer your question, no, the $0$ is not ignored. Consider an epsilon-NFA with two states, the initial state $q\_0$ and the accepting state $q\_1$, connected by two edges labeled $\epsilon$ and $0$. This epsilon-NFA accepts the words $\epsilon$ and $0$. If you remove the edge labeled $0$, the epsilon-NFA will accept only $\epsilon$.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: What is the difference between apprenticeship and imitation learning?
There are many sub-domains of reinforcement learning, two of which are apprenticeship and imitation learning - but that appears just to be two different names for the same thing?

# Answer
> 4 votes
In general, yes, they are the same thing, which means to learn from demonstration (LfD). But, usually, apprenticeship learning is mentioned in the context of "Apprenticeship learning via inverse reinforcement learning" (IRL). Both methods learn from demonstration, but they learn different things:

* Imitation learning (a.k.a. behavioral cloning) will try to copy the teacher. This can be achieved by supervised learning alone. The AI will try to copy even irrelevant actions such as blinking or scratching, for instance, or even mistakes. You could use RL here too, but *only if you have a reward function*.
* Apprenticeship learning via inverse reinforcement learning will try to **infer the goal** of the teacher. In other words, it will learn a reward function from observation, which can then be used in reinforcement learning. If it discovers that the goal is to hit a nail with a hammer, it will ignore blinks and scratches from the teacher, as they are irrelevant to the goal.

---
Tags: terminology, reinforcement-learning
---


# Question
Title: Length of an Edit Script and the Number of Deletions
I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller. The algorithm sounds like a good fit for a project I'm doing at work. I have found some implementations in my target language that I could reuse, but I want to make sure that I understand the algorithm (and the code) because it is so crucial to my project.

I am a ways into the paper, and seem to be understanding it, but there's something important in the abstract that still doesn't make sense to me. This is the relevant portion:

> Let $A$ and $B$ be two sequences of length $M$ and $N$ respectively, where without loss of generality $N \ge M$, and let $D$ be the length of a shortest edit script between them. A parameter related to $D$ is the number of deletions in such a script, $P = D/2 - (N - M)/2$. We present an algorithm...

This relationship between $P$, $D$, $N$, and $M$ is not proven in the paper. And when a try using it with a simple example (turning "xy" into "x", for instance), I get a nonsensical answer. Can someone please explain the relationship?

# Answer
> 0 votes
This is a straightforward consequence of the fact that the edit script only contains insert and delete operations. It follows from a little bit of basic arithmetic -- it's nothing especially deep.

Consider a script that contains $I$ insert operations and $P$ delete operations. Then the total number of operations in the edit script is $I+P$. If we're given that the total number of operations is $D$, we know $D=I+P$. Also we know $M+I-P=N$ (since each insert operation increases the length of the document, and each delete decreases it). Solving these two simultaneous equations yields the relationship you list.

---
Tags: algorithms, string-metrics, edit-distance
---


# Question
Title: Levenshtein distance cabable working with (large) vectors - not strings
**Long version:**

Is there any algorithm similar to Levenshtein distance which can compare vectors? I will post several examples with desired inputs/outputs and then I will also show that it is not the same as if the vectors are (prefixed with zeros) concatenated to strings and then Levenshtein is computed:

**Desired inputs/outputs:**

```
[1, 2, 555] vs [1, 2, 777]
1: replace 555 with 777.

[1, 2, 556] vs [1, 2, 778]
1: replace 556 with 778.

[1, 2, 555] vs [3, 4, 777]
3: replace 1 with 3, replace 2 with 4, replace 555 with 777.

[1, 2, 5] vs [3, 4, 7]
3: replace 1 with 3, replace 2 with 4, replace 5 with 7.

[1, 2, 556] vs [3, 4, 778]
3: replace 1 with 3, replace 2 with 4, replace 556 with 778.

[1, 2, 3] vs [1, 2, 2, 3]
1: insert 2 at position 1.

[1, 2, 3, 4, 5, 666] vs [1, 2, 4, 3, 6, 777] # same as e.g.: "123456" vs "124378"
4:
[1, 2, 4, 3, 4, 5, 666] - inserted 4 at position 2
[1, 2, 4, 3, 6, 5, 666] - replaced 4 with 6 at position 4
[1, 2, 4, 3, 6, 5, 666] - replaced 5 with 777 at position 5
[1, 2, 4, 3, 6, 5]      - deleted 666 at position 6

```

**Concatenating to strings:**

```
"12555" vs "12777"
3: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 5 with 7 at position 5.

"12556" vs "12778"
3: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 6 with 8 at position 5.

"12555" vs "34777"
5: replace 1 with 3 at position 1, replace 2 with 4 at position 2, replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 5 with 7 at position 5.

"125" vs "347"
3: replace 1 with 3 at position 1, replace 2 with 4 at position 2, and replace 5 with 7 at position 3.

"12556" vs "34778"
5: replace 1 with 3 at position 1, replace 2 with 4 at position 2, replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 6 with 8 at position 5.

"123" vs "1223"
1: insert 2 at position 1.

"12345666"vs "12436777"
5: delete 3 at position 3, replace 5 with 3 at position 5, replace 6 with 7 at position 7, replace 6 with 7 at position 8, and insert 7 at position 8.

```

**Padding zeros to get same element size and concatenating to strings:**

```
"001002555" vs "001002777"
3: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 5 with 7 at position 9.

"001002556" vs "001002778"
3: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 6 with 8 at position 9.

"001002555" vs "003004777"
5: replace 1 with 3 at position 3, replace 2 with 4 at position 6, replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 5 with 7 at position 9.

"001002556" vs "003004778"
5: replace 1 with 3 at position 3, replace 2 with 4 at position 6, replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 6 with 8 at position 9.

"001002003004005666"vs "001002004003006777"
6: replace 3 with 4 at position 9, replace 4 with 3 at position 12, delete 5 at position 15, replace 6 with 7 at position 17, replace 6 with 7 at position 18, and insert 7 at position 18.

```

PS: There are various vector distances, but according to my quick research they are all variations of Euclidean distance (they works with vector's elements at same position but does not account with deletion, insertion, substitution).

PPS: Some working implementation instead of pseudo code or paper would be useful (preferably in python, perl, R but whatever language would be fine) There are also various implementation of Levenshtein and some of them are pretty fast (according to my understanding they are storing only result and not how the result was computed). So I would like to have as fast as possible algorithm. Thank you very much.

**Short version:**

I need algorithm which will compute Levenshtein distance for those two vectors `[1, 2, 3, 4, 5, 666]` vs `[1, 2, 4, 3, 6, 777]` in simmilar way as if it would e.g. for those two strings `"123456"` vs `"124378"`

Here is the algorithm for comparing `"123456"` vs `"124378"` strings in details (positions starts from 0):

```
"123456"  - 1st string
"1243456" - 1. inserted 4 at position 2
"1243756" - 2. replaced 4 with 7 at position 4
"1243786" - 3. replaced 5 with 8 at position 5
"124378"  - 4. deleted 6 at position 6
The Levenshtein distance is 4

```

Here is my desired algorithm for vectors `[1, 2, 3, 4, 5, 666]` vs `[1, 2, 4, 3, 6, 777]` in details (positions starts from 0):

```
[1, 2, 3, 4, 5, 666]      - 1st vector
[1, 2, 4, 3, 4, 5, 666]   - 1. inserted 4 at position 2
[1, 2, 4, 3, 6, 5, 666]   - 2. replaced 4 with 6 at position 4
[1, 2, 4, 3, 6, 777, 666] - 3. replaced 5 with 777 at position 5
[1, 2, 4, 3, 6, 777]      - 4. deleted 666 at position 6
The Levenshtein distance is 4

```

If I create strings from vectors `[1, 2, 3, 4, 5, 666]` and `[1, 2, 4, 3, 6, 777]` I get `"12345666"` and `"12436777"`. But Levenshtein distance on this strings is different to what I want (see above vector example).

Here is the algorithm for comparing `"12345666"` vs `"12436777"` strings in details (positions starts from 0):

```
12345666 - 1st string
1245666  - 1. deleted 3 at position 2
1243666  - 2. replaced 5 with 3 at position 3
1243676  - 3. replaced 6 with 7 at position 5
1243677  - 4. replaced 6 with 7 at position 6
12436777 - 5. inserted 7 at position 7
The Levenshtein distance is 5

```

# Answer
Don't convert the numbers to decimal digits and then concatenate. Instead, just use the sequence of numbers directly. The Levenshtein distance can be used on any sequence, not just a sequence of characters.

Formally, the Levenshtein distance can be used to compute the similarity of two elements of $\Sigma^\*$, where $\Sigma$ is some alphabet. Normally for strings we let $\Sigma$ be the set of characters. However, in this case you can take $\Sigma=\mathbb{Z}$ (the set of all integers), so that each element of $\Sigma^\*$ is just a sequence of integers. Now you can apply the Levenshtein edit distance directly to two sequences of integers, without doing any kind of conversion to decimal, concatenation of digits, or zero padding.
> 1 votes

---
Tags: algorithms, strings, string-metrics
---


# Question
Title: How to express time complexity when the exponential "e" comes into play?
I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size.

While timing the execution of such algorithm I have figured out that the time elapsed follows an exponential law:

```
Time(size)=0.15*exp(0.05*size)

```

My question: is it correct to define this complexity according to

`T(n)=O(e^n)`?

# Answer
It depends on whether you're talking about $O$ or $\Theta$. The notation $O$ indicates that the complexity is "this much or smaller", and the notation $\Theta$ indicates that the complexity is "this much, no more or less".

The complexity of $0.15 e^{0.05 n}$ is $\Theta(e^{0.05 n})$. The complexity is not $\Theta(e^n)$, because $e^n$ grows faster than $e^{0.05 n}$ does (the ratio between the two increases without bound).

It is, in fact, true that $0.15 e^{0.05 n}$ is an $O(e^n)$ function, but this isn't a *good* description of the complexity, in much the same way that "more than a thousand people live in China" is not a good description of the population of China.

What this comes down to is that you should state the complexity as $\Theta(e^{0.05 n})$ or as $O(e^{0.05 n})$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: If L is a regular language, how to prove that L' is also regular?
I've been trying to construct a proof of the following statement the whole day but I got stuck:

If $L$ is a regular language, the language $L\_{}{'}$ consisting of all words in $L$ containing the letter $\sigma$ (where $\sigma$ is an arbitrary fixed letter in $\Sigma$) is also regular.

I know that the first thing to do is to construct an NFA that recognizes $L\_{}{'}$ from the NFA that recognizes $L$, but I can't find a conversion that is general enough. It might me silly, but I think one just have to change the transition function. I hope you guys can give me some advice.

# Answer
> 3 votes
Yes, but changing the transition function also might involve changing the states. In this case, the states should "remember" whether we have seen the letter $\sigma$ in the past.

Alternatively, one can prove closure properties like this using well-known properties, like the fact that regular languages are closed under intersection. The language of all words containing the letter $\sigma$ is regular.

# Answer
> 1 votes
As Hendrick alluded, here are a couple of hints, assuming that the alphabet of $L$ is $\Sigma$:

1. Can you show that the language of all strings over $\Sigma$ containing a particular $\sigma\in\Sigma$ is regular? (A two-state DFA will do it.)
2. What do you know about the intersection of two regular languages?

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


# Question
Title: How can ships in Battleship be partitioned into B subsets, each with a capacity C?
I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf The paper states that the input would be an array of positive integers (the items), C (an integer capacity), and B (an integer number of subsets). The question that is posed then becomes: can the items be partitioned into B subsets, each of which has total capacity C? How is this even guaranteed to be possible? For example, if the total size of 6 ships is 19, it seems actually impossible to partition them according to the requirements of the problem? Maybe I am just understanding the reduction wrong. Any ideas?

# Answer
> 1 votes
The idea is to reduce the bin packing problem to battleship, not the other way around.

The variant of bin packing they use in the paper is to decide if it is possible to partition $n$ numbers into $B$ subsets (the bins) so that the numbers into each subset add to a quantity $C$.

Example:

Input:

The set $\\{2,3,5\\}$ , $B=2$ and $C=5$

Possible solution:

Two subsets $1$ and $2$:

$1 = \\{2,3\\}$

$2 = \\{5\\}$

This problem can be reduced to battleships in the following way:

Create a board of width $B \times 2$ and height $S + n$ , where $n$ is the cardinality of the subset we are going to partition and $S$ is the sum of all the elements of the multiset we want to partition.

Then for each pair of columns that belong to each bin, we set the number that the first column should ammount to $0$ and the other one to $C$. These numbers are the number of pieces of a ship that there should be in each column.

For the rows: For each number $a\_i$ that belongs to the multiset that we want to partition, we have a separator row with a value of $0$ and $a\_i$ rows with a value of $1$. These numbers make reference to the number of boat pieces that there should be in each row. For each row that belongs to a number, we have only a ship piece because we want each of the $a\_i$ numbers to be covered by a single ship of that size.

So in one column of each column pair we will have a separator row and a vertical strip of $a\_i$ rows of height for each number of the multiset we have to partition. We can cover that strip with a ship or not, but we have to cover enough strips of a column so that the number of ship pieces of that column adds to exactly $C$.

Because a picture is worth a thousand words i made a picture of a solved example board that we obtain by reducing an instance of bin packing to battleship

The instance of bin packing that i'm going to use as an example is:

The set $\\{2,3,5\\}$.

$B=2$

$C=5$

The shaded squares are squares that are occupied by a boat.

Thanks for bringing my attention to this problem, i didn't know it.

Hope this is helpful.

---
Tags: np-complete
---


# Question
Title: Reconstruct the minimal path cost from the delta-stepping algorithm?
I was coding the *delta-steppping algorithm* from this paper. They describe almost everything about the algorithm but not how to get the path. As an output I am getting the dictionary **tent** where `tent[v]` contains the minimal cost to go from $s$ to $v \in V$. How can I retrieve the path of the minimum cost based on this algorithm?

# Answer
> 1 votes
The algorithm that you're implementing is based on the Dijkstra Algorithm, so we can use the same idea to get the path, that is, keep the predecesor data each time you relax the edges (see `pred` data structure below). Actually, in the same paper, they state where you have to look at in the following method.

However, we need the information of the vertex we are using in the relaxation method, as you know we are comparing these two values, $tent\[w\]$ vs $tent\[v\] + Cost\[v,w\]$. So if after all $tent\[v\] + Cost\[v,w\]$ is less than $tent\[w\]$, we need keep $v$ to say we are going to use the edge $(v,w)$.

Then I suggest you to introduce $v$ as follows:

Replace $Req$ for this definition, $$ Req = \\{(w, tent(v) + c(v,w), v)\ :\ v\in B\[i\] \text{ and } (v,w) \in light\[v\]\\}. $$

Add a third argument to the method `relax`:

```
 relax(w,d,v)
    if d < tent[w]:
        pred[w] = v
        ...

```

And fix all `for each` with $(w,d,v)\in Req$ and the other.

To retrieve the path from $s$ to $w$, do something like:

```
for v in V: pred[v] = INF
...
def findpath(w):
  v = w
  path = []
  while pred[v] is not INF:
     path.append(v)
     v = pred[v]
  path.reverse()
  return path

```

---
Tags: algorithms, graphs
---


# Question
Title: Is there an example of a recursive language which is not context sensitive?
I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^\*$ is prototypical of regular languages, $a^nb^n$ for context free languages and $a^nb^nc^n$ for context sensitive languages. I usually consider the language which is accepted by a universal Turing machine (UTM) as prototypical of recursively enumerable. However for the the recursive languages I don't have one. I used to think that $\\{1^p | p \text { is prime}\\}$ was recursive but verifying a number is prime can be done by a bounded Turing machine. I also had $\\{1^{2^{n}}\\}$ but again verifying this can be done by a bounded Turing machine.

On the other hand, the other options I have found are computing Turing machines that requiere that the output of the computation to be store somewhere in the machine, however the output is no part of the accepted language which makes every of those language regular or context free so far. For instance the machine that sums two numbers represented by 1s and separated by a space, and puts the result after. In this case, the accepted language is actually $1^\*B1^\*$ which is regular! If we try to do it like verification if become context free $1^nB1^mB1^{n+m}$ but no recursive!

So is it possible to talk about a recursive language which it might be regular in essence but since it is conditioned to do the computation and put a result in the output as a kind of recursive language? Those definitely can not be done in a bounded Turing machine.

# Answer
> 11 votes
Here's a more formal proof, by the standard trick of diagonalization (it must be folklore, but I saw it recently here)

Let $G\_1, G\_2, ...$ be some enumeration of context sensitive grammars (convince yourself that there are only countable many of them; Why can they be enumerated?),

Let $x\_1, x\_2, \ldots,$ be enumeration of $\Sigma^\*$ (i.e., $x\_1=\epsilon$, $x\_2=0$, $x\_3=1$, $x\_4=00$, etc. in the case of binary alphabet).

Consider the language:

$$L = \\{ x\_i \mid x\_i \notin L(G\_i)\\}.$$

**Claim 1** $L$ is not context sensitive: if it was, there was a specific $G\_j$ generating it, but $x\_j\in L$ while $x\_j \notin G\_j$.

**Claim 2** $L$ is decidable: given $x\_i$ we just check if $G\_i$ generates it (this problem is known to be PSPACE complete, thus decidable).

---
Tags: formal-languages, turing-machines, context-sensitive
---


title: Lookahead in LL(k) parsing

text:
# Question
Title: Lookahead in LL(k) parsing
I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them?

Any help is appreciated.

# Answer
> 6 votes
No, you still *consume* one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol.

Here's a simple example: the grammar of context-free grammars. Informally, a CFG is a sequence of *productions*, where each production consists of a *non-terminal*, the *derives symbol* ($\to$) and a *replacement list*, which is a possibly-empty sequence of *non-terminal* and *terminal*. Formally, we have

$$\begin{align} Grammar &\to \lambda \\ Grammar &\to Nonterminal \ Arrow \ Derivation \ Grammar \\ Derivation &\to \lambda \\ Derivation &\to Nonterminal \ Derivation \\ Derivation &\to Terminal \ Derivation \\ \end{align}$$

That's not an LL(1) grammar, because when $Derivation$ is on top of the stack and the next input symbol is $Nonterminal$, then there are two possible actions:

1. Predict $Derivation \to \lambda$, which means popping the $Derivation$ off the stack without consuming the input token.
2. Predict $Derivation \to Nonterminal Derivation$, which means popping the $Derivation$ off the stack and replacing it with $Derivation \ Nonterminal$; then matching the $Nonterminal$ from the input and the $Nonterminal$ on top of the stack, discarding both.

How can the parser decide which action to take? If it can only see one input symbol, then it has no way to decide. But if it can see 2 input symbols, then it can choose action 1 if the second next input symbol is $Arrow$ and action 2 in any other case.

So we can conclude that our grammar for grammars is LL(2).

---
Tags: parsers, ll-k
---


# Question
Title: How do you know a problems is non-computable?
I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which admits no algorithm exists for solving it. The book then goes on to use an adaption of Wangs Tile's as an example of this - stating that no algorithm exists which will output yes or no when a solution is/is not found.

Although I haven't proved it I would have thought that this could be done via a backtracking algorithm (yes it would be inefficient but surely doable)? Or am I looking at the meaning of non-computable the wrong way? Or maybe just not understanding that Wangs Tiles cannot be done full stop.

# Answer
> 0 votes
"Non-Computable" is very broad. Do you mean a problem that has no solution or a problem that is running seemingly infinitely? Also I'd like to note that non-computable doesn't mean has no answer.

If you mean a problem that seemingly runs forever, those problems do have solutions, but we're never going to see them. For example, Ackermann recursion for large numbers is a problem with "no solution" because after 3 recursions it takes days for the next answer, the 5th takes weeks and it grows exponentially after that. That's "non-computable" but it does have an answer, but we'll never know it.

Any algorithm or process that never stops also is also non-computable since it will never give you an answer to a problem. This is different than ackermann recursion in the fact that ackermann has an answer, but counting the number of molecules in the universe has no answer as the universe is infinitely expanding and the number is growing. That problem would just go on forever as there is no answer since the inputs grow infinitely. This is similar to the example you give as there are infinite possibilities to check.

---
Tags: computability, decision-problem
---


# Question
Title: Is there a name for graphs which contain oriented and non-oriented edges?
Is there a name for graphs which contain oriented and non-oriented edges?

I couldn't find on the internet if there exist a specific name for such graphs.

# Answer
They are called mixed graphs.
> 2 votes

# Answer
Yes.  (Nothing stops them from having *both* $\langle u,v\rangle$ *and* $\langle v,u\rangle$ as edges.)
> 1 votes

---
Tags: graphs, terminology
---


# Question
Title: What is the complement of the language with all ucv with u ≠ v?
If $L = \\{w\_1cw\_2: w\_1,w\_2 \in \\{a,b\\}^\* , w\_1 \neq w\_2\\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \\{w\_1cw\_2: w\_1,w\_2 \in \\{a,b\\}^\* , w\_1 = w\_2\\}$ and he said that we can ignore $c$ and it's not in $\Sigma$ of language $L$. but I think $c$ should be in $\Sigma$ of language $L$ and the complement mentioned above is wrong based on definition of complement that is $\\{a,b,c\\}^\* \backslash L$. which answer is right?

Based on transition relation of pushdown automata where is maping from $(Q\times (\Sigma \cup \\{\lambda \\}) \times \Gamma) $ to $(Q \times \Gamma^\*)$ so if we construct a pushdown automata for string $aabcabb$ for example here $c$ should be in $\Sigma \cup \\{\lambda \\}$.

# Answer
The complement of a language $L$ over an alphabet $\Sigma$ consists, by definition, of all words over $\Sigma$ that are not in $L$. If you use this definition, you find out that $\overline{L}$ consists of all words of the form $wcw$ for $w \in \\{a,b\\}^\*$ (like your friend said), as well as all words which contain either no $c$ or at least two $c$s.

---

The complement operation for languages, like the complement operation for sets, assumes an underlying universe. In the case of languages, the underlying universe is $\Sigma^\*$, where $\Sigma$ is the alphabet that the language is defined over. You an think of languages in at least two ways:

* A language is a pair consisting of an alphabet $\Sigma$ and a subset of $\Sigma^\*$. We usually only explicitly mention the second part.
* A language is a collection of "words" over some universal alphabet. We can think of the language as being over any alphabet which includes all the symbols appearing in the language.

While the more correct view is the first, the more practical view is the second. Therefore, whenever you take the complement of a language, you must make sure with respect to which alphabet the complement is taken. This can be done in at least two ways:

* When you define the language, you also mention the underlying alphabet.
* When you take the complement, you state with respect to which alphabet you are complementing it.

For example, you could say:

> Let $L$ be the language over $\\{a,b,c\\}$ given by $L = \\{ w\_1 c w\_2 : w\_1,w\_2 \in \\{a,b\\}^\* \text{ and } w\_1 \neq w\_2 \\}$. What is the complement of $L$?

Or you could say

> Let $L = \\{ w\_1 c w\_2 : w\_1,w\_2 \in \\{a,b\\}^\* \text{ and } w\_1 \neq w\_2 \\}$. What is the complement of $L$ (as a language over $\\{a,b,c\\}$)?
> 3 votes

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


# Question
Title: Is the given language finite or infinite?
I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that basically a language such as $0^\*$ is obviously infinite since there can be any nonnegative number of $0$'s. However, is a language such as $(0 \cup 1)((0 \cup 1)^p)((0 \cup 1)^p)(0 \cup 1))$ also infinite? Technically, there can be any number of $0 \cup 1$ as it matters on the $p$ value, but I am also under the impression that there can only be so many values for $p$ and therefore the language is indeed finite. Can anyone explain as to why the language is either finite or infinite? I have read other examples but get a little confused when the language is in the gray area. Thanks!

# Answer
> 4 votes
`(0 U 1)((0 U 1)^p)((0 U 1)^p)(0U1))` is not a language, but a regular expression. Moreover, to be well-defined, you must specify what $p$ is.

Is $p$ a specific value? Then, this expression generates a finite number of words -\> it generates a finite language.

But maybe you look at the language generated by the above expression for **any** p? then, there will be infinitely many generated words.

**you** need to tell us what is $p$ and what is the language under consideration.

# Answer
> 0 votes
> what makes a language finite or infinite

That's pretty clear by definition. In general, it's (algorithmically) impossible to tell from some description. There are also examples that are deliberately obscure so students have to think.

> as it matters on the p value

Exactly. Regular expressions do, syntactically, not allow for integer variables. So you have to consider a fixed (if arbitrary) value for p.

> when the language is in the gray area

There is no gray area; the question you ask is ill-posed is all. What is the *exact* definition of the language?

---
Tags: formal-languages, regular-languages
---


# Question
Title: CFG for the language "number of a's = number of b's + 2"
How can I construct a context-free grammar for the following language?

$$ L = \\{ w \in \\{a,b\\}^\* : \\#\_a(w) = \\#\_b(w) + 2 \\}. $$

Please help me out in this. I am not sure how to approach this question. I would also appreciate general tips on constructing context-free grammars. I find it highly difficult.

# Answer
> 2 votes
There are essentially two general tips on constructing context-free-grammars. A wide range of normal context-free languages (those that do not require any tricks) have easy grammars for them. And the tricky one that are present in relatively hard exercises are relatively few and these involve knowing some finite number of tricks to construct grammar for them.

Of course the following two tips won't cover all the problems. Also if you can construct a PDA, theoretically you can construct a CFG with it, but it will involve many more symbols than what most of the exercise problems require.

If you are writing a context-free grammar for a compiler of new language then it is understood that you know the tricks of the trade already. And sometimes the grammars of the new language are not even context-free.

**First tip:** Look for substrings in the language which are strings in some regular language. For regular languages you need to add rules of the form $A\rightarrow aB$ or $A \rightarrow Ba$ (or $A\rightarrow \alpha B$ or $A \rightarrow B\alpha$) whichever suits your intuition.

**Second tip:** Look for substrings in the language which need to balance some kind of count/symbols around strings of some other context free language. Then you have to add rules of the form $A\rightarrow aAb\ | \ B$ (or $A\rightarrow \alpha A\beta\ | \ B$).

With these two tips you will be able to construct grammars for many simpler context free language. For example

$S\rightarrow aa\ | \ \epsilon$ for context-free language (which is also regular) of even number of $a$'s.

$S\rightarrow aSb \ | \ \epsilon$ for context-free language of strings of the form $a^nb^n$. Here you need to balance a count.

Unfortunately, the language of balanced parenthesis, which is the variant of the language you are talking about needs a simple trick. Basically any production rule that requires two or more non-terminals is not very intuitive, in my humble opinion, unless the symbols are just placeholders (if there is some recursion involved, you will have difficult time in understanding the language accepted, see some grammars for context-sensitive languages, for example, they are truly difficult to understand if you do not have practice reading them). You have to get down to write a proof to see if the language generated by the grammar is indeed the same.

The language of balanced parenthesis is

$S\rightarrow (S) \ | \ SS \ |\ \epsilon$

or,

$S\rightarrow (S)S\ | \ \epsilon$.

You can easily modify the grammar above to a grammar for language of strings with equal number of $a$'s and $b$'s. That can again be easily modified to another grammar for language of strings with number of $a$'s greater than number of $b$'s by 2. However, proofs that language of grammar is indeed the same as in question will involve some non-trivial logic.

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


# Question
Title: If P=NP, are there cryptosystems that would require n^2 time to break?
If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption algorithms? Do any such algorithms already exist?

# Answer
> 14 votes
Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure Communications over Insecure Channels" by Ralph Merkle, where he proposed to use “puzzles”. This is a key agreement protocol.

1. Alice sends $n$ encrypted messages (called puzzles), each containing a unique identifier $I\_i$ and a session key $K\_i$, with the keys for each messages chosen among a set of $n$ keys. This takes $O(n)$ time ($O(1)$ per message).
2. Bob decrypts one of the messages by brute force and sends back $I\_i$ encrypted with $K\_i$. This takes $O(n)$ time ($O(1)$ per key, times $n$ possible keys).
3. Alice tries all the keys to decrypt the message. This takes again $O(n)$ time.

Each party requires only $O(n)$ computation, but an eavesdropper who wishes to find $K\_i$ needs to try out half the puzzles on average to calculate the right key (the eavesdropper does not know which message Bob chose to decrypt), so the eavesdropper requires $\Theta(n^2)$ computation on average.

After Merkle invented his puzzles, Diffie and Hellman published a key agreement protocol based on the discrete logarithm problem. This protocol is still used today.

The problem with Merkle puzzles, or anything where the amount of work to be done by the attacker only increases as the square of the legitimate party, is that it takes huge key sizes and amounts of computation to achieve a decent security margin.

In any case, it is not clear that merely proving that P=NP will invalidate existing cryptographic algorithms. If the polynomial increase is a high enough power, it might not matter so much in practice. See How will security need to be changed if P=NP?, Can we say that if P=NPP=NP there is no CPA secure public key encryption?, P = NP and current cryptographic systems, …

# Answer
> 1 votes
https://en.m.wikipedia.org/wiki/One-time\_pad

A One Time Pad is secure regardless of complexity, as long as your numbers are truly random.

Even if you can try every key quickly, it's useless because this will reveal every possible message, and there's no way to know which one was the desired one.

For what you describe, if the analysis only took the square of the encryption time, it would be considered insecure by modern standards. Encryption needs to happen in seconds or even less , so a quadratic increase would allow messages to be decoded in a few hours.

---
Tags: cryptography, encryption
---


# Question
Title: Is the "modular subset product" problem NP-complete?
While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is replaced by modular arithmetic?

A concrete example is the subset product problem, which was known to be $NP$-complete. I wonder if we consider the problem over ring $\mathbb{Z}\_n$, as formulated below, it is still $NP$-complete?

> Given $t, n \in \mathbb{N}$ and a finite set of integers $S$, determine whether there exists $S' \subseteq S$ such that $\prod\_{s \in S'}s \equiv t \pmod n$.

My principal difficulty in approaching the problem is that I cannot figure out how the (polynomial) reduction works, supposing the $NP$-completeness is retained, due to the "cyclic" behavior of modular arithmetic. I've tried to search for variants of the problem but no luck. Thank you for any explanations, suggestions or references.

# Answer
> 1 votes
The claim that you linked to (that subset product is strongly $NP$-complete), is incorrect: it is only weakly so. The numbers $s\in S$ are small and can be represented in unary, but $t$ has to be represented in binary for the reduction to work.

If you consider it over $\mathbb{Z}\_n$ it remains weakly $NP$-complete, since we can just take $n$ to be $\Pi\_{s\in S} s$. In this case, the fact that we're doing modular arithmetic becomes irrelevant. $n$ will be exponential in $\Sigma\_{s\in S} s$ so that $\log n$ (the size of a binary representation of $n$) will be polynomial in the size of the original instance (in which all $s\in S$ were represented in unary).

# Answer
> 0 votes
Yes it is still NP because it can be modified or altered into satisfactory algorithm and the numbers which are mentioned s∈S are given as unary but 't' has to be given in binary. This will in turn reduce work load.

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


# Question
Title: Can the reproduction function of an evolutionary algorithm consider gene strength?
I am trying to solve the Zen Garden puzzle using an evolutionary algorithm. My question relates to evolutionary algorithms in general.

***Bit about evolutionary algorithms:*** An evolutionary algorithm is an algorithm which tries to solve a given problem in a semi-random way. Most often I have seen it is implemented thusly: for a given starting state of the problem a generation of random solution approaches for is generated. Each *speciemen* (approach) has a set of genes which define it. Each speciemen is then used to try and find a solution to the problem. If no solutions are found, then we try to determine the fitness of each speciemen by some set of rules. For example- if the problem was to collect all treasures on a map, then the fitness a speciemen could be determined by the ammount of treasures it managed to collect. Once we determine their fitness we try to crossbreed the speciemen semi-randomly, giving higher chance of reproduction to those with higher fitness. This way we create a new generation of speciemen, where each of them has some genes from both of its parents. Then we try to solve the problem using the new generation of speciemen and the cycle goes on until a solution is found or we reach some kind of pre-determined limit of max-generations.

**Question:** Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen? What I mean by that is that for example if I could measure how much a certain gene contributed to the solution attempt can I give the gene a higher chance to be passed on or should child genes be passed on randomly?

# Answer
> Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen?

Of course it can.

Anyway, consider that in GA this already happens *implicitly*. Using the established methods and genetic operators of genetic algorithms (not only reproduction but also crossover and mutation) the Holland's schema theorem states that low-order schemata with above-average fitness increase exponentially in successive generations.

(a schema is a template that identifies a subset of strings with similarities at certain string positions)

In **Genetic Programming** things are different:

1. GA representations are often fixed size whereas GP representations and usually variable sized;
2. GA normally have a semantic interpretation for a given location in a chromosome while GP solutions often do not exhibit location dependent meanings.

John Koza attempted to explain why genetic programming works by extending Holland's schema model and theorem to GP but with various differences / limitations (the class of problems and problem representations for which block processing is useful remains a challenging and open research topic in GP).

In GP your idea is the base of the modularization approach, e.g.

* The **encapsulation operation** is a genetic operation that identifies a potential useful subtree and gives it a name so that it can be referenced and used later (see *Genetic Programming: On the Programming of Computers by Means of Natural Selection*)
* Better yet, **Adapting Representation through Learning** (ARL). With ARL New subroutines are created using blocks of genetic material from the pool given by the current population.

The detection of what are salient blocks of code is based on two notions: differential offspring-parent fitness and "active" blocks.

The process of discovering building blocks and creating new subroutines based on simple blocks of code is applied recursively so that subroutines of any complexity can be discovered.

Subroutines beneficial to some individuals could be invoked also by other individuals. The end result is the collection of subroutines that acquires the necessary structure for solving the problem (take a look at *Towards Automatic Discovery of Building Blocks in Genetic Programming* by Justinian Rosca for a complete description).
> 2 votes

---
Tags: genetic-algorithms, evolutionary-computing
---


# Question
Title: Can a regular language have uncountably many strings?
Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0\* as an example.) But can a RL have uncountably many strings? I'm leaning toward no, but I can't really back it up.

# Answer
> 4 votes
No, there are only countably many finite strings over any finite alphabet. Given an alphabet $\Sigma = \\{s\_0, \dots, s\_d\\}$, you can associate the string $w$ with the number $1w$ written in base-$d$, giving an injection from the natural numbers to $\Sigma^\*$. (The reason we use the number $1w$ rather than $w$ is to avoid problems with, e.g., $2$, $02$, $002$, etc. all mapping to the same number.)

# Answer
> -3 votes
Yes,a regular language can have uncountable number of strings as a regular language can have unlimited strings by Kleene closure or sigma closure.

---
Tags: formal-languages, regular-languages, uncountability
---


# Question
Title: Huffman encoding: why is there no need for a separator?
```
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

```

Original text:

> Eerie eyes seen near lake

Encoded:
0000101100000110011100010101101101001111101011111100011001111110100100101

Why is there no need for a separator in the Huffman encoding?

# Answer
> 53 votes
You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10.

This means that you can decode greedily by reading the encoded string from left to right and outputting a character as soon as you've seen a codeword. For example, 0, 00 and 000 don't code anything so you keep reading bits. When you read 0000, that encodes "E" and, because the code is prefix-free, you know there's no other codeword 0000x, so you can now output "E" and start to read the next codeword. Again, 1 doesn't encode anything but 10 encodes "e". No other codewords begins with "10", so you can output "e". And so on.

# Answer
> 13 votes
It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that this sort of structure is created in the process.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

# Answer
> 3 votes
No code other than E starts with 0000. No code other than i starts with 0001. And so on. As an extreme case, no code other than e starts with 01. You don't have things like E = 0000, space = 000, where you wouldn't know what to do if you find three zeroes.

Look at your encoded string: 0000101100000...

You read the first zero. You know the code is one of E, i, y, l, k, comma, or space. The next zero means it's not k, comma or space, but E, i, y or l. The next zero means it is E or i. The next zero means it's an E. When you know which code it is, you know you have parsed all the bits for that code.

Then you have 101100000... The 1 means you have e, r, s, n or a. The next bit is 0, so the code is e. Again, you're done with that character.

# Answer
> -2 votes
We cant use separator in Huffman encoding because every letter's binary equivalent doesn't matches the prefixed code of any letter, so we can do without even using separator.

---
Tags: coding-theory, encoding-scheme, huffman-coding
---


# Question
Title: How is the environment designed for testing a reinforcement learning algorithm?
I'm working on a project, and have a candidate algorithm which I'd like to test. Before I go any further, I need to get the hang of how to code the "structure" of the environment in which my system is embedded, like what the relevant signals are, how they interact with each other, how they evolve with time, and so on.

I'm looking for resources on design of the environment, for artificial intelligence problems, as I don't want to reinvent any wheels. Any information would be welcome, especially introductory to intermediate level. Thanks!

# Answer
> 1 votes
In reinforcement learning, the "environment" is typically a set of states the "agent" is attempting to influence via its choice of "actions".

For example, in "Reinforcement learning design for cancer clinical trials" by Zhao, Kosorok, and Zeng (2009),

> ..."states" may represent individual patient covariates and "actions" can be denoted by various treatments or dose levels.

More abstractly, in "A brief introduction to reinforcement learning" by Murphy (1998),

> The environment is a modeled as a stochastic finite state machine with inputs (actions sent from the agent) and outputs (observations and rewards sent to the agent).

So, the "structure of the environment," what signals are relevant, and how they interact is highly specific to the problem you're trying to solve, as is the choice of where to draw the boundary between the agent and the environment.

In "Reinforcement Learning: an Overview", Sutton and Barto (1998), give an overview of the Agent-Environment interface and note:

> The agent-environment boundary can be located at different places for different purposes. ... In practice, the agent-environment boundary is determined once one has selected particular states, actions, and rewards, and thus has identified a specific decision-making task of interest.

"Reinforcement Learning: A Survey" by Kaelbling, Littman, and Moore (1996) also provides an overview of the problem.

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


# Question
Title: Complexity classes of undecidable Turing Machines
I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always accepts, the TM that always halts respectively) are in. If anyone could explain which class they're in an why that would be great. Also what about languages like NEtm(langague of TM no equal to null). What langague would that fall into and why. Thanks in advance

# Answer
> 4 votes
The correct measure for the complexity of undecidable problems is the arithmetical hierarchy and its extensions. Undecidable problems sit outside all of the complexity classes defined by time or space constraints.

---
Tags: complexity-theory, computability
---


# Question
Title: Are all problems approached and solved in fundamentally the same way?
This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot.

This questions stems from a conversation a friend and I were having about the google interview process. It boiled down to my argument that they are searching for individuals who are fundamentally better problem solvers than others (His argument is that prior job experience proves this, mine is that it doesn't).

This got me thinking. Say we want to solve a simple problem `2 + 2`, we could go about this the simply way and just count `1 2, 3 4` to get to the answer or we could chose a much more complex way to arrive there. I argue that both ways fundamentally solve the problem the same way; that the more complex solution is reducible to the simplest.

This linked up in my brain to Big O. It has been shown that all problems in `NP` are equivalent and can be translated (reduced?) to each other (I might be completely wrong on this); essentially if you solve one (in `P` time) you solve them all. It kind of shows to me that all problems within their given class are fundamentally the same.

This leads me to question, is the way that problems are solved fundamentally the same? Moreover, is there a way to solve all problems (nothing about running time)?

Again disclaimer, not a full complete thought. I just wanted to get it out there before I forget it and never think of it again. I found it interesting enough to share and just wanted input. Please correct if (where.) I am wrong.

# Answer
> 1 votes
What you're missing is that, although all **NP**-complete problems can be reduced to one another, so it is true that solving one lets you solve them all, that doesn't mean that they're all equally easy, so they're not all "the same problem".

In particular, the reduction takes some amount of time to perform. Although all problems in **NP** can be reduced to, say, SAT, that doesn't mean that all problems in **NP** are as easy as SAT. Some require very little effort to translate to SAT; others require much more effort. And there's no bound1 on how much effort might be needed, as you look at more and more complex problems within **NP**.

A way to make this concrete is with the time hierarchy theorem. That says that, essentially, allowing more time for computations lets you compute more things, and it applies to nondeterministic machines as well as deterministic ones. So, solving SAT instances takes some amount of time but, if you allow yourself more time than that, you can solve strictly more things.

---

1 OK, its always a polynomial but there's no bound on the degree of that polynomial.

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


title: Explanation of Grammar Ambiguity

text:
# Question
Title: Explanation of Grammar Ambiguity
Consider now the grammar G

S -\> (S + S)
S -\> (S * S)
S -\> a

Is it ambiguous?

Answer: No because there are disambiguating parentheses and so no left or right recursion.

Can someone explain how the parentheses are disambiguating. I could understand if they were "\[" and "(".

Appreciate the help

# Answer
A grammar $G$ is *non-amgibuous* if every word in $L(G)$ has a unique *parse tree*. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (here $L(\alpha)$ is the set of all words that can be generated from the sentential expression $\alpha$); given this, an easy induction shows that $L(G)$ is non-ambiguous.

It is clear that $L(S + S)$ and $L(S * S)$ are disjoint from $L(a)$. To prove that $L(S + S)$ and $L(S * S)$ themselves are disjoint, you can prove by induction that each word generated by $S$ is either $a$ or of the form $(w)$, where $w$ is a well-parenthesized expression (parenthesis close each other correctly), and this gives you a rule for identifying the first and the second $S$ in word generated by $L(S + S)$ and $L(S * S)$; the symbol in between determines whether the word belongs to $L(S + S)$ or to $L(S * S)$.
> 3 votes

---
Tags: formal-grammars, ambiguity, left-recursion
---


title: On intersection of classes

text:
# Question
Title: On intersection of classes
Consider classes $\mathcal C\_1$ and $\mathcal C\_2$ of problems both of which are $\mathsf{NP}$-complete. Does it mean $\mathcal C\_1\cap\mathcal C\_2$ of problems is $\mathsf{NP}$-complete?

# Answer
I'm not sure what you mean by a class of problems being **NP**-complete ndash; perhaps that every problem in the class is **NP**-complete?

In any case, it sounds like it's possible that $\mathcal{C}\_1\cap\mathcal{C}\_2 = \emptyset$, in which case the answer seems to be "no". (Well, except that every problem in $\emptyset$ is **NP**-complete, in which case the answer would be "yes" but for vacuous reasons.)

In general, whenever you're asked about closure properties of families of languages, a good first question to ask yourself is, "Can I make the answer trivial by engineering the intersection/union/whatever to be either the emptyset or every possible thing?"
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Is there a bounded-time algorithm for Envy-free cake-cutting?
I am engineering student,i have doubts regarding the topic can anyone help me to find solution.

# Answer
A bounded-time algorithm for the problem has been presented by Haris Aziz and Simon Mackenzie (*A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents*, arXiv:1604.03655, April 2016).
> 4 votes

---
Tags: algorithms
---


title: minimize $l_1$ distance between vectors

text:
# Question
Title: minimize $l_1$ distance between vectors
Given two vectors $a$ and $b$ I need to find $k$ such that $\sum\_i|a\_i - kb\_i|$ is minimal. In other words, my goal is to find $k$ that minimizes the $l\_1$ norm distance between $a$ and $kb$.

How should I approach such problem? The $l\_1$ norm has weird derivative. Is there some analytical solution, or should I use something like ternary search?

# Answer
> 1 votes
Define $r\_i=a\_i/b\_i$. Sort the vectors in increasing order of $r\_i$. Let's assume (wlog) the $r\_i$'s are in increasing order, i.e., $r\_1 \le r\_2 \le r\_3 \le \cdots$. Let $R=\\{r\_1,r\_2,\dots,r\_n\\}$.

Notice that your objective function is differentiable at all $x$ such that $x \notin R$. In fact, it is linear on each open interval $(r\_i,r\_{i+1})$. It follows that it attains a maximum at one of the values $r\_i$.

So, it suffices to try each of $r\_1,r\_2,\dots,r\_n$ as possible values for $k$, and see which minimizes the objective function. This leads to a simple $O(n^2)$ time algorithm. With some optimization and clever tricks you can get this down to $O(n \lg n)$ time, by avoiding re-computing the objective function from scratch each time and re-using work.

---
Tags: algorithms, optimization
---


# Question
Title: Question about time-complexity for MST-like algorithm
I have got a problem with an excercise about graphs:

Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has about 50 stops and the company wants to save money by driving the shortest possible distance. Your friend ignores your advice and decides on an algorithm, as follows:

* Start at the depot,
* Go to the nearest location that has not yet been delivered to:
    + Deliver
    + Repeat until you have delivered all the beer
* Return to depot

And the quesiton is: What is the Big-O complexity of this approach? Why?

I do not think this way of solving problem is any algorithm like Prim's algorithm, and I have no clue what can be a complexity. Could anyone explain me?

# Answer
This problem looks variant of TSP problem(more precisely metric TSP). As you want to traverse all node with the minimum distance.

TSP is one of the classical NP-Hard problem.

What your friend did is a Greedy approach making minimum Spanning tree Which is 2-Approx(metric-TSP) of the minimum distance.

This greedy approach generally works in E log V time but does not have guarantee for exact solution.

By using graph structure we can implement in linear time also.
> 2 votes

# Answer
E(logV) where E is the number of edges in the graph and V is the number of nodes i.e. here number of stops=50 So, E log50 will be the time complexity
> -2 votes

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


title: Understanding Dijkstra's algorithms

text:
# Question
Title: Understanding Dijkstra's algorithms
As far as I understand, Dijkstra's algorithm always picks the nearest neighbour.

But how does it work for the following graph?

```
    2
A-------B
 \     /
1 \   / 3
    C

var result = dijkstra(fromA, toB);

Step1: A->C is the shorter
Step2: C->B is the shorter
Answer: 1 + 3 === 4 // This is clearly wrong

```

What am I missing?

# Answer
Dijkstra works as follows:

1. Take the first node from OPEN. Let $n$ denote such node. OPEN contains all nodes generated in ascending order of $g(n)$, where $g(n)$ is defined as $\sum\limits\_{i=1}^{n-1} c(v\_i, v\_{i+1})$, and $c(v\_i, v\_{i+1})$ is the cost of the edge from $v\_i$ to $v\_{i+1}$. In other words, $g(n)$ is the sum of the edge costs in the path from the start state to node $n$.
2. If $n$ is the goal state, then halt. The optimal solution is the path from $s$ to $n$.
3. If $n$ is not the goal state, then verify whether it has been expanded before or not. Another list, called CLOSED contains those nodes already expanded. If $n$ is found in CLOSED, then go to 1. Otherwise, expand $n$ generating its successors. Evaluate $g(n')$ for each descendant $n'$ and add them to OPEN.
4. Remember you expanded $n$, so add it to another list called CLOSED. Go to 1.

Initially, OPEN=$\\{s\\}$ where $s$ is the start state and CLOSED=$\varnothing$ as you have expanded no node yet.

From your execution trace, it seems to me that you overlooked step 2, ie., Dijkstra stops when it is about to expand the goal state, *and not when it is generated*. As a matter of fact, you may generate the goal state an arbitrary number of times, but condition 2 is met only once.

Hence, in your specific case, Dijkstra works as follows:

**Iteration #1** OPEN=$\\{A\\}$ and CLOSED=$\varnothing$

1. Take the first node from OPEN, $n=A$
2. It is not the goal state $A\neq B$
3. It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $C$ with a cost equal to 1 and $B$ with a cost equal to 2. They are now added to OPEN in ascending order of $g(n)$ so that OPEN=$\\{C, B\\}$
4. Add $A$ to CLOSED as it has been expanded, CLOSED=$\\{A\\}$

**Iteration #2**

5. Take the first node from OPEN, $n=C$
6. It is not the goal state, $C\neq B$
7. It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $B$ (its parent $A$ is easily removed as it is clearly its parent, but you can try to generate it as well and you'll see Dijkstra works smoothly the same). $B$ has now a $g$-value equal to 4 as it has been generated through the path $\langle A, C, B\rangle$. Hence, OPEN contains now $B$ twice: OPEN=$\\{B, B\\}$, the first one with a value equal to 2 (generated in the first iteration) and the second with a value equal to 4 (generated in this iteration).
8. Add $C$ to CLOSED as it has been expanded, CLOSED=$\\{A, C\\}$

**Iteration 3**

9. Take the first node from OPEN, $n=B$ (with a cost equal to 2).
10. It is the goal state. Halt with the path $\langle A, B\rangle$

Hope this helps,
> 4 votes

# Answer
According to me every node must be visited as per the given representation given. So the answer would be 2 because firstly it goes from A to C and then to be B so cost would be high.(directly from A to B is efficient)
> 3 votes

# Answer
I suggest you visit the following link, it really helped me at understanding algorithms, including Dijkstras algorithm. Dijkstra Visualisation

As far as I understand, the algorithm says that at each new node visited, the distances from the source node to its adjacent nodes is updated, in case it is a shorter path.(Initially for all nodes except the adjacent nodes of source node, shortest path is infinity)

Here is an **incomplete execution** of the algorithm. Eventually, when we reached D, we updated the cost/path to B.

Hence, unless your graph is directed, your implementation may be incorrect.You should have recorded the path to B in your graph from A

You can also see the video that the picture is taken -\> Dijkstra's Algorithm: Another example

Cheers
> 2 votes

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


# Question
Title: When is the output of shortest path $\subset$ MST?
I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like:

The shortest path $B \rightarrow C$ is in no way contained in the MST. Are there known conditions on the graph and the edge weights that ensure that all vertex-to-vertex shortest paths are contained in the minimum spanning tree?

# Answer
A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either endpoint of that edge, the shortest path tree contains the edge. So if we fix the source node for the SSSP tree, then it'll be difficult to say more than that the SSSP tree and the MST are equal for graphs that are trees themselves.

Raphael mentions in a comment that the same argument holds for weighted graphs with triangle inequality; to adapt the argument, we only need to consider the lightest edge on that cycle.

Generalizing in a different direction, **whenever you have a weighted graph with weight function $w \> 0$ that doesn't have a unique MST, then for every MST there is some node for which the MST is not a shortest path tree**. The proof will assume that all edge weights are positive; I originally thought that since the set of MSTs is invariant under adding the same value to all edge weights, this would show the result for general graphs, but it doesn't since the set of shortest path trees is not invariant under that operation. Thus, the result will only be proven for graphs with positive weights. Regarding notation, $w \> 0$ means that $w$ is positive everywhere.

**Proof:** Take two different MSTs $S = (V, E\_S)$ and $T = (V, E\_T)$ of some graph $G = (V,E)$. Consider a lightest edge that is in $S$ but not $T$, that is $ \\{u,v\\} = e \in \arg \min \\{w(f): f \in E\_S \setminus E\_T\\}$. Take the unique $u-v-$path $p\_{u,v}^T \subseteq E\_T$ in $T$. We know $e \not \in p\_{u,v}^T$. Note also that $|p\_{u,v}^T| \geq 2$.

Any two MSTs have the same multiset of edge weights, see e.g. Raphael's proof here; due to this, the weight of the lightest edge in $E\_S \setminus E\_T$ is the same as that of the lightest edge in $E\_T \setminus E\_S$. Now take all edges on $p\_{u,v}^T$ that are not in $S$, that is $\Delta = (p\_{u,v}^T \setminus E\_S) \subseteq (E\_T \setminus E\_S)$. We know that $\Delta \neq \emptyset$ since otherwise, $\\{e\\} \cup p\_{u,v}^T$ would be a cycle in $S$. Any lightest edge in this difference, $e' \in \arg \min \\{w(f): f \in \Delta\\}$, satisfies $w(e) \leq w(e')$ due to the choice of $e \in \arg \min \\{w(f): f \in E\_S \setminus E\_T\\}$. Since all edge weights are positive and $|p\_{u,v}^T| \geq 2$, we know that $w(e) \leq w(e') \< w(p\_{u,v}^T)$. Thus, $T$ is not a shortest path tree for $u$. $\square$
> 3 votes

---
Tags: graphs, shortest-path, minimum-spanning-tree
---


# Question
Title: Conversion from nondeterministic PDA to deterministic PDA
Why is the conversion from nondeterministic PDA to deterministic PDA not possible?

# Answer
> 3 votes
There are languages accepted by nondeterministic PDAs that cannot be accepted by deterministic PDAs. Perhaps the easiest way to see this is to consider inherently ambiguous context-free languages. As context-free languages, they are accepted by some nondeterministic PDA. On the other hand, every language accepted by a deterministic PDA has an unambiguous grammar, so they cannot be accepted by any deterministic PDA.

---
Tags: automata, pushdown-automata
---


# Question
Title: Shortest path in a weighted graph with coloured edges
I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of different colour I have to pay an additional fee equal to $K$. Given two vertices $A$ and $B$, I want to find the shortest path between them.

For example, given a multigraph with 3 vertices, $K = 5$, and 3 edges: ($1\rightarrow 2$ of weight 3 and colour 1), ($1\rightarrow 2$ of weight 5 and colour 2), ($2\rightarrow 3$ of weight 2 and colour 2), weight of the shortest path is 12.

I would like to design an algorithm that would solve this problem in reasonable time. My first idea was to use Dijkstra's algorithm and for every vertex store an information about the edge from which I went into that vertex, but that strategy won't work for the example given above. So I don't have any other idea than brute-force search.

Constraints:

* $N \leq 10^5$
* $M \leq 10^5$
* $K \leq 10^5$

# Answer
Replace each vertex $x$ by $C$ vertices $(x,c)$, where $C$ is the number of colors (actually you only need the colors that appear in edges adjacent to $x$), and connect these vertices by edges of weight $K$. Replace an edge $(x,y)$ of weight $w$ and color $c$ by an edge $((x,c),(y,c))$ of weight $w$.

You can now solve your problem by running Dijkstra's algorithm on the new graph $C^2$ times. You can optimize this approach so that you only need to run Dijkstra's algorithm once by adding two new vertices $A,B$ and connecting $A$ to the vertices $(A,c)$ with directed edges, and similarly connecting the vertices $(B,c)$ to $B$ with directed edges.
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: The name for this genetic algorithm variant
What is the name for this variant of genetic algorithm. I'm sure I have read about this in Wikipedia, but now I could not find it:

There in no thing as sequential population. The phenotypes lives and dies just like people. The death comes after random period of time. During life phenotypes can have children. The better phenotype is (fitness function) the bigger is chance to have (more) children. The better phenotype is the better can be it's candidate form wife or husband. Yes, phenotypes have sex (man or woman).

# Answer
> 0 votes
I think you mean a genetic algorithm with a steady state population model.

# Answer
> 3 votes
Most EAs may be divided into *generational* algorithms, which update the entire population once per iteration, and *steady-state* algorithms, which update the sample a few candidate solutions at a time.

*Steady-state* GAs (popularized by the Darrell Whitley and Joan Kauth's GENITOR system) iteratively breed a new child or two, assess their fitness and then reintroduce them directly into the population, thus killing some preexisting individuals to make room (take a look at Essential Metaheuristics by Sean Luke for further details).

So a steady-state GA fits part of the description ("death comes after random period of time").

Other characteristics ("the better phenotype is (fitness function) the bigger is chance to have (more) children") are shared with *generational* algorithms.

*Gender-specific selection / crossover operators / GAs* fit the last part of the description ("phenotypes have sex (man or woman)"):

> instead of selecting individuals from a single group for mating, a *gender genetic algorithm* create two groups and permits mating only between opposite groups; the selection from two groups helps to increase diversity.

Anyway many GA variants based on a more natural governing framework are possible:

* delayed reproduction / breeding age (most life forms aren't able to breed during the early stages of their life);
* life span for individuals (no matter how poor the fitness is, it would still stay in the population for a length of time) / predetermined death age;
* progressive ageing (*Individual Aging in Genetic Algorithms* by Ashish Ghosh, Shigeyoshi Tsutsui and Hideo Tanaka);
* Age-Layered Population Structure (ALPS) evolutionary algorithms (The Age-Layered Population Structure by Gregory S. Hornby)
* ...

---
Tags: terminology, genetic-algorithms, evolutionary-computing
---