# Question
Title: Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?
In order to show that $ \\{A^nB^nA^nB^n \mid n \geq 0 \\}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p\<|vxy|, p\<j.$

* if $vy$ contains just $a$s we choose i=0 for $w^i$, so in this case the number of $a$s isn't equal to the $b$s.
* if $vy$ contains just $b$s we choose i=0 for $w^i$, so in this case the number of $b$s isn't equal to $a$s.
* if $vy$ contains both $a$s and $b$s then for any i there will be a difference in there quantity compare to the $n$ $a$s and $b$s that aren't in $vy$. Also $vy$ can't contain the whole world since the number of $a$s larger than $p$.
* Isn't it CFL? Can pumping lemma help here?

I was told in class that it isn't correct to use pumping lemma here, why?

# Answer
Sure you can use the pumping lemma,

String in $L$ consists of four consecutive segments: a $A$ segment followed by a $B$ segment followed by another $A$ segment followed by another $B$ segment. Assume that $L$ is context free and let $p$ denote the pumping length of $L$. consider the string $A^pB^pA^pB^p\in L$.We can write this string as $uvxyz$ where $|uxy|\leq p$ and $|uv|\>1$. We look at two cases:

* case 1: Either $v$ or $y$ contains more than one type of character (i.e at least one of $v$ and $y$ contains both $A$'s $B$'s). In this case, pumping up once to $uv^2xy^2z $ inserts an extra $A^iB^j$ sequence into $s$ i.e the resulting string will contain at least $3\quad A$ segments and $3\quad B$ segments. For instance, if $v=AABB$, then pumping once would result in an additional $AA$ segment followed by an additional $BB$ segment. But string in $L$ contain only four segments
* case 2: Both $v$ and $y$ contain only one type of character (i.e they are both all $A$'s or all $B$'s). Since $uxy\leq p$, $uxy$ contains letters from at most $2$ segments of $s$. Pumping once to $uv^2xy^2z$ increases the number of characters in one or two of the segments, but leaves the remainig segments untouched. Thus, the number of characters in each segment will be unbalanced.
> 3 votes

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


# Question
Title: Prove by induction that the running time of recursive Fibonacci is exponential
This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! But I am finding it difficult to fully understand how to prove things involving lower and upper-bounds. After looking up many resources including some things from Stanford, this is what I have been able to come up with:

Let $T(n) =$ time for $fib1(n)$, where $T(n) = T(n-1) + T(n-2) + 3$

**Claim:** For $n \ge 6$, the running time of $fib1(n)$ is exponential, i.e $T(n) \ge (1.41)^n$

**Base Case:** $$T(6) = 8 \ge (1.41)^6 = 7.86$$ $$T(7) = 13 \ge (1.41)^7 = 11.08$$

**Inductive Hypothesis:** Assume that for an arbitrary n, $T(n) \ge (1.41)^n$

**Prove $T(n+1) \ge (1.41)^{n+1}$:** $$T(n+2) = T(n+1) + T(n) + 3$$ $$\ge 1.41^n + 1.41^{n+1} \text{ \[By the I.H\]}$$ $$ = (1.41^n)(1+ 1.41) \> 1.41(1.41)^n$$

Thus, the running time of $fib1(n)$ is $\Omega{(1.41^n)}$

**Edit:**

I'm not entirely sure how correct this is, but I'm not as worried about that. My main concern is in the induction step, I feel like there is something I am missing conceptually. Specifically, how exactly can we be sure that $$T(n+2) = T(n+1) + T(n) + 3 \ge 1.41^n + 1.41^{n+1} $$ if we only know that $$T(n) \ge 1.41^n$$

I hope this clarifies my question. Thanks!

# Answer
Observe that with

$\qquad T(n) = T(n−1)+T(n−2)+3$

and

$\qquad T'(n) = 2 T'(n-2)$,

you have $T \> T'$ assuming similar anchors, in particular because both functions are non-decreasing. $T'$ solves to $T'(n) \approx 2^{n/2} \geq 1.41^n$.

I intentionally provide only a sloppy sketch; I'll leave the formal proof to the interested reader.
> 1 votes

---
Tags: recurrence-relation, lower-bounds, induction
---


# Question
Title: Having a problem understanding the execution of I/O in Von Neumann model
I might have gone too deep in my search after the answer which might be much easier than what I figured.

Essentially I wanted to figure out how I/O are executed in a Von Neumann machine, but more I read, the more confused I became.

What they are saying in "Introduction to computing systems" (Patt and Patel) and other websites covering this is that I/O devices in the VN machine has an I/O controller which works as a liaison between the I/O device(s) and the CPU which will interrupt the CPU once the I/O operation is finished. (1. it receives the write/read request, 2. notifies the cpu and let it go back to doing whatever task it was doing, 3. interrupts it once the I/O operation is finished).

1. So this is some kind of Interrupt-driven I/O, but is that enough to explain how I/O are executed in VN machine?
2. How does a program communicate with an I/O device?
3. How will you explain the data transfer between memory and I/O devices?

# Answer
> 4 votes
You are not wrong in stating that you went too deep in your search.

To counter these confusions, you might want to study how instructions are executed electronically in a computer.

The one thing worth remembering is: In a computer *everything* is controlled by the CPU. That includes the IO devices, their interfaces, the instructions put forth by them and the ones relegated to them.

Typically, what happens is that a program or a facility in your machine generates interrupts. Generally, the interrupt itself is an instruction to the CPU coming from the memory, loaded in the memory by the CPU itself at a prior time. When the CPU executes the interrupt, it checks the status of I/O device (like a key press), registers it and manipulates it as per instructions that follow. When modern computers turn on, BIOS - Basic Input Output System, that is - is used for generating interrupts and is used as an interface/liaison between the CPU and I/O devices. BIOS itself is a program (set of instructions) that resides on ROM and is read by the CPU at time zero. After the boot up is complete and OS is loaded to the memory, this facility is provided by the Operating System.

> How does a program communicate with an I/O device?

That depends upon the level of abstraction you are working on. If you want to see the program as a single and lone set of instructions to the CPU then the I/O interrupts are a part of the program. They are executed and tell the processor which device is to be contacted and in what manner. A little knowledge of assembly would be helpful for clarification in this context. But a small example of instructions to CPU is as follows:

```
1. Load integer 8 in Register 1.  //Instruction 'Load', Data '8'
2. Check keyboard for key press.  //An interrupt to Keyboard
3. Store key press value in Register 2.
4. Add contents of Register 1 and Register 2 in Register 3.
5. Pass contents of Register 3 to Display. //An output interrupt.

```

In the case of an operating system like Windows, the interrupts are a part of operating system program and are used to call the CPU's attention not only to I/O devices, but also to other programs in the memory. The IO interrupts here are in driver domain present in the memory as an interface. The user applications or the other programs in memory make calls to the operating system to make these interrupts, they can not directly make interrupts. Following is an example of a simple program in MSIL assembly.

```
.maxstack 2
.entrypoint   //begins here.
ldc.i4 8      //load integer 8 to stack.
ldc.i4 9      //load integer 9 to stack too.
add           //Add last two integers.
call void [mscorlib]System.Console.WriteLine(int32)  //A call to windows to
              //display the answer in console. Windows does the rest.

```

> How will you explain the data transfer between memory and I/O devices?

An instruction by a program to check the status of IO device. An instruction to get the data from the device and store it into a register. An instruction to store the value of that register into a memory location at a certain address in RAM. That location can be read by the program when required.

# Answer
> 2 votes
Many, rather different, machines are lumped under "von Neuman". The critical pieces are that there is a read/write memory (RAM), which contains instructions and data. Instructions are executed by a processor (CPU) while reading/writing data to memory. I believe the original model did not consider I/O, other than some rudimentary method of setting memory contents by hand (toggling switches) and reading out results the same way.

Modern computers are not von Neuman, far from it. There are several processors (just lower-end cellphones have a single core anymore), and futhermore many of the "I/O devices" are handled by DMA (Direct Memory Access, the device takes instructions to read/write to a memory area without CPU intervention). Modern, high-performance devices are quite capable computers on their own. Handling part of the network stack is integrated into higher-end network cards; WiFi requires a very complex set of operations, again most of those are done by the card, not the CPU. Graphics cards are built around fast vector processors (the same operation is executed on an array of data in parallel), which are programmed in their own language, with the CPU mostly shuffling data into/out of the card,

---
Tags: computer-architecture
---


# Question
Title: Informed search with a lower-bound heuristic?
I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state.

However, what about when one only has a heuristic that never *under*estimates the minimum cost from a node to any goal state? (Also: is there a name for such a heuristic?)

What I am currently doing is as follows. I first find *some* path to a goal state (luckily in my case this is relatively trivial) and record its cost and path as the best cost and path. Then I do a depth-first search, with two modifications. One, I do not stop when I reach a goal state, instead updating the best cost found so far and record the path to get here. Two, anytime I find myself at a node where the sum of the cost to get here and the heuristic is greater than or equal to the best cost found so far, I backtrack. Then at the end I output the best path found.

(Two nice things about this: 1) it's guaranteed to return an optimal solution, 2) if interrupted it has a solution, albeit a suboptimal one)

I've been calling this "iterative shallowing" (as opposed to iterative deepening), but I have no clue as to the actual name.

So: is there a name for this? If so, what is it? Is there a name for a lower-bound heuristic? Is there a name for informed search algorithms using only a lower-bound heuristic?

# Answer
After some consideration, this appears to be an alternative formulation of the depth-first variant of the Branch-and-Bound algorithm.
> 1 votes

---
Tags: algorithms, graphs, terminology, heuristics, search-problem
---


# Question
Title: Finding a closed form for a discrete sum using generating functions
Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N cigarettes in the Banach cigarette problem ; so there is a combinatorial explanation which I do not consider here.

$$ \sum\_{i=0}^{N} \binom{2N-i}{N} 2^i = 2^{2N} $$

I wish to know how one would go about finding this closed form using generating functions. More precisely, how would you evaluate

$$ \sum\_{N \geq i} \binom{2N-i}{N} x^N $$

Thanks!

# Answer
The term $t\_N = {2 N - i \choose N} x^N$ of the sum is *hypergoemtric* ($t\_{N+1}/t\_N$ is a rational function of $N$) which means that the closed form of the sum can be found using Gosper's algorithm, if it exists and is hypergeometric.

When I run the algorithm with Mathematica it says $$x^i \cdot {}\_2F\_1(\frac{i+1}{2}, \frac{i+2}{2}; i+1; 4 x)$$ where ${}\_2F\_1$ is the hypergeometric function. This means that a closed form of the kind you are expecting does not exist.

**Supplemental:**

Gosper's algorithm computes $$\sum \_{i=0}^n \binom{2 n-i}{n} 2^i = 4^n$$ and then $$\sum \_{n=0}^{\infty } x^n \sum \_{i=0}^n \binom{2 n-i}{n} 2^i = \frac{1}{1 - 4 x}.$$
> 2 votes

---
Tags: combinatorics, discrete-mathematics
---


# Question
Title: Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s
This is for formal-language-style regular expression and not about Unix-style regular expression.

I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings composed of only 0's, and doesn't accept strings composed of only 1's. The regular expression should only accept strings composed of 0's and 1's but without consecutive 1's.

Here's what I've seen so far: $(0+10)^\*(ε+1)$

The problem is that it can accept empty string or just 1-character string `1`. I would like to skip empty string and `1` since they are not strings of 0's and 1's.

I just couldn't find a good pattern. It seems that I have to create 2 regular expressions so that the first will be $(01+10)(0+1)^\*$. If I am right, that will not accept empty string, will not accept just 0's, and will not accept just 1's. Then I would pass the result to the 2nd pattern $(0+10)^\*(ε+1)$ to further validate that it has no consecutive 1's.

Could anyone explain what is the best solution to have the correct regular expression for strings of 0's and 1's?

# Answer
I would suggest you to draw a small finite state automaton. Things to keep track in the states are "seen 0", "seen 1" and "last letter 1" (to avoid consecutive 1's).

There is an "official" algorithm to go from automaton to expression, but with small examples you usually can read the expression directly.
> 3 votes

# Answer
Starting from what you have, let's try to improve it.

So you have $(0+10)^\*(ε+1)$. That's a very good start, as it covers all binary strings with no consecutive `1`s. I think of this as saying that a binary string with no consecutive `1`s is like a string made up of `0` and `10` sequences, with an optional `1` added at the end.

Now, as you want only non-empty strings, and furthermore want strings that contain both a `0` and a `1`, let's extend that so that we have at least one `10` sequence: $0^\*10(0+10)^\*(ε+1)$

Now, the only case not covered is the case where there is no `10` in the string at all - that is, where we have one or more `0`s and then a final `1`, so we add that: $0^\*10(0+10)^\*(ε+1) + 00^\*1$
> 0 votes

# Answer
You can at least use two regex' in parallel instead of your chained solution. In Unix syntax it could look like this (should be easily translatable to your style):

```
(10+)+1?|(0+1)+0?

```

The first regex forces a group of zeros **after** every `1` while the latter forces a group of zeros **before** a `1`.
> -1 votes

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


# Question
Title: How can I check that the language of one context-free grammar is a subset of a second context-free grammar?
Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2).

G1 and G2 are two LL(1) grammars with identical alphabets:

```
{a, b, c, d, f}

```

Production rules are look like:

```
A -> αB

```

or

```
A -> α

```

and α is a non-epsilon string (of terminal symbols).

Context-free grammar G1:

```
S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE

```

Context free grammar G2 :

```
S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU|f
V -> aQ
U -> aP
Q -> cY
P -> bZ

```

**Automatic way is preferred.**

> In additional, how can I check that the languages of two **arbitrary** **context-free grammars** are equal.

# Answer
Here you have a couple of salient points. Firstly, the grammars are right linear (strictly $G\_{1}$ needs some small changes, but they're trivial). This means that the two languages are regular. Given this fact, there's an automated way of determining whether $L(G\_{1}) \subseteq L(G\_{2})$ or not.

In this case however, things are fairly simple, and we can show a simple mapping between the non-terminals, with only the transitions $A \to abC$ and $B \to acE$ causing a small amount of trouble. If you draw out the finite automata though, you should be able to see the mapping. Doing so, it should be fairly clear that $S\_{1}$ maps to $S\_{2}$ (obviously), $K$ to $X$, $C$ to $Z$ and $E$ to $Y$. $A$ maps to the pair $U,P$. $U \to aP \to abZ$, and $Z$ already maps to $E$, so you can see the rule is essentially the same in both grammars, just split in $G\_{2}$ into an intermediate step. The same observation applies to $B$ and $V,Q$.

Note that in general, we need the fact that $L(G\_{1})$ and $L(G\_{2})$ are regular, deciding containment for context free languages is undecidable.
> 8 votes

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


# Question
Title: If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?
I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time?

Problem statement: Given a set of formulas in CNF in Łukasiewicz logic, I want to find an assignment for the variables in some truth set T\_k, for some k, such that the assignment maximizes the number of satisfied formulas. I wanted to model this problem into CSP or SAT, hence my question. The SAT problem for CNF Łukasiewicz logic formulas is solvable in linear time. So, maybe we can take advantage of that.

# Answer
Probably not, since clauses can be encoded using only linear inequalities.
http://web.stanford.edu/~rrwill/cnf-sat-feasible.pdf
> 2 votes

---
Tags: logic, polynomial-time, constraint-satisfaction
---


# Question
Title: Is no language with the non-primes property context-free?
A language $L$ is said to have the "no primes" property if:

1. For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$.
2. For every non-prime $m$ there is at least one word $w\in L$ of length $|w|=m$.

Given a language $L$ that has the no primes property, must $L$ be non-context-free?

Intuitively I believe yes, since the languages of all primes is not context free. But how can I prove this for every language that has this property?

I thiught proving using the sequence of lengths of words from any such language $L$, but this sequence is bounded by (at most) 3 (if 1 is consideres non prime, otherwise bounded by 2).

I also thiught proving by using the pumping lemma, but since I have no information on $L$ I am not sure if its possible.

Is there another method to prove so? Or a counter example that dissproves this?

# Answer
> 7 votes
You can use Parikh's theorem to prove this claim.

Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it only talks about length of words). It's very easy to prove that no regular language can satisfy this condition (e.g. by complementing it and using the pumping lemma).

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


# Question
Title: How Can I Recognize When to Use ε-Transitions in an NFA?
I am learning about finite automata for the first time. I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA and therefore an equivalent DFA.

Here is an example question that confuses me: *What is the minimum number of states a DFA recognizing the language of a(bc)\*d can have?*

To answer this question, I first drew this NFA (dashed line indicates acceptance):

Because I think the above NFA is already a DFA, I thought the answer was "5".

However, the correct NFA and equivalent DFA look like this:

Which means the answer is "4". I understand why these are correct. But, I have some questions:

1) Is my original drawing actually an NFA? If not, why?

2) If the original drawing is an NFA, does it describe the language *a(bc)\*d*? If not, why?

3) If the original drawing is an NFA that describes the language *a(bc)\*d*, is it also a DFA? If not, why?

4) If the original drawing is an NFA and DFA that describes the language *a(bc)\*d*, why should I have known to draw the NFA with ε-transitions instead?

# Answer
Your first drawing is a DFA (and thus an NFA) and does match the language described. The NFA with $\varepsilon$ transitions is a fairly natural (and mechanical) translation of the regular expression, but other than that, it isn't inherently "more correct" than the NFA you started with.

The only confusion I see here other than uncertainty is once you validated that your NFA was a DFA you seemed to have just taken it for granted that it was minimal. Starting from your DFA, you could have noticed that S4 has the same out-transitions as S2 and that they might possibly be joined. Doing so would have immediately produced the final DFA.
> 3 votes

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: What is the most efficient way to find bSmooth values in QS?
The heaviest part of QS is to search for bSmooth numbers.

So far I thought about two algorithms for solving this.

1. Trial division
2. * calculate $X$ as a product of all the values in the factor base
    * speed up the trial division with $gcd(X,Y)$ where $Y$ is a potential bSmooth value

# Answer
The most efficient method is to use a *sieve*; this is why the method is called the quadratic *sieve*. It should be mentioned, though, that the sieve is just an optimization over Dixon's method, and doesn't affect the asymptotic running time apart from some (multiplicative) lower order terms. For a description of the sieve, you can start with Wikipedia.
> 3 votes

---
Tags: algorithms, efficiency, number-theory, factoring
---


title: Non Recursively Enumerable Languages

text:
# Question
Title: Non Recursively Enumerable Languages
Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?

# Answer
> 9 votes
Every undecidable yet semi-decidable language provides an example: its complement.

That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.

You should know at least one such language from class.

> The Halting language, and probably numerous others from exercise problems.

# Answer
> 6 votes
An example of a language which is not recursively enumerable is the language $L$ of all descriptions of Turing machines which *don't* halt on the empty input. We know that $\overline{L}$ is recursively enumerable (exercise) while $L$ is not recursive (this is Turing's classical result), so it follows that $L$ is not recursively enumerable.

For a deeper look, we have to delve into the arithmetical hierarchy. We can write $L$ symbolically as follows: $$ L = \\{ \langle M \rangle : \forall t \text{ $M$ doesn't halt within $t$ steps}\\}. $$ The reason for expressing $L$ in this particular way is that the predicate $\phi(\langle M \rangle,t)$ which holds when $M$ doesn't halt within $t$ steps *is recursive* (exercise). So $$ L = \\{ \langle M \rangle : \forall t \phi(\langle M \rangle, t) \\}, $$ where $\phi$ is some computable predicate. This puts $L$ in the complexity class $\Pi\_1$ (here $1$ means that there is $1$ quantifier alternations, and $\Pi$ means that the first quantifier is $\forall$; in contrast $\overline{L} \in \Sigma\_1$, since for $\overline{L}$ the first quantifier is $\exists$). Note that $\Sigma\_1$ consists of all recursively enumerable languages, while $\Pi\_1$ consists of all co-r.e. languages.

It so happens that $L$ is $\Pi\_1$-complete. This means that for every language $A \in \Pi\_1$ there is a computable reduction $f$ such that $x \in A$ iff $f(x) \in L$. I outline a proof below. Turing's argument implies that $\Pi\_1 \neq \Sigma\_1$, and in particular no $\Pi\_1$-complete language (or more generally, no $\Pi\_1$-hard language) can belong to $\Sigma\_1$.

It remains to show that $L$ is $\Pi\_1$-complete. Consider any language $A \in \Pi\_1$, so $A = \\{ x : \forall y \psi(x,y) \\}$, where $\psi$ is computable. The function $f$ will construct a Turing machine that runs $\psi(x,y)$ on all values of $y$, and terminates if it finds a value of $y$ for which $\psi(x,y)$ is false. Thus $x \in A$ iff $f(x) \in L$.

---
Tags: computability, turing-machines, turing-completeness
---


# Question
Title: Is it decidable whether a given context free grammar generates an infinite number of strings?
Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or not, we can write a program that would test this but would not halt. So it should be undecidable. Is this so?

# Answer
> 18 votes
Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule $S\_0\to \epsilon$ (where $S\_0$ is the initial variable, which cannot be derived from other variables).

Thus, any other derivation adds some non-trivial part to a word.

Now, let $n$ be the number of variables in the grammar, and let $k$ be the maximal length on the right-side of a derivation rule. That is, $A\to B\_1\cdots B\_k$ is the maximal length. We are going to show the following theorem:

> $G$ generates an infinite word iff it generates a word of length at least $k^{n+2}$.

Consider some word $w$ generated by the grammar, and a derivation tree for it. The derivation tree has branching factor of at most $k$, and thus it needs to be of height at least $\log\_k |w|$ in order to derive $w$.

Take a really long word $w$. Just how long? take $w$ of length $k^{n+2}$. Then, every derivation tree of $w$ requires at least height $\log\_k(k^{n+2})=n+2$. That means that there is some path in the tree of length $n+2$, and on this part there is some variable that repeats (since there are only $n$ variables). We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree.

Now, you can "pump" the word $w$ to infinitely many other words that are generated, by repeating the subtree of the variable that derives itself.

If this sounds complicated, take a look at the pumping lemma, it's the same idea.

So now what? Well, take your grammar, and "remove" from it all words of length less than $k^{n+2}$ by intersecting it with a regular language of all words of length at least $k^{n+2}$, and check if the resulting grammar is non-empty. If it is, the original grammar generated an infinite language, and otherwise - a finite language.

# Answer
> 11 votes
Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in *reduced* form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^\* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

*Sketch of proof:* For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

It's obvious that this criterion can be decided algorithmically; check for cycles of weight³ $\> 0$ in the (multi-)graph made up of non-terminals as nodes, edges from $A$ to $B$ if $B$ appears on a right-hand-side of a rule for $A$, and weights are the number of terminals generated by these rules. Hence, the given problem is decidable.

---

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.
3. If we eliminate *chain rules* $A \to B$ as well (a standard exercise), *any* cycle suffices.

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


# Question
Title: Why is a (collision-less) hashtable lookup really O(1)?
Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for.

My question is: why is collision-*less* lookup `O(1)` in the first place?

Let's assume I have this hashtable:

```
Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

```

Now I'm looking for the key `k` where the hash function `h(k)` gives `h(k) = mkwer`. But how does the lookup "know" that the hash `mkwer` is at position 5? Why doesn't it have to scroll through all keys in `O(n)` to find it? The hashes can't be some kind of real hardware addresses because I'd lose the abbility to move the data around. And as far as I know, the hashtable is not sorted on the hashes (even if it was, the search would also take `O(log n)`)?

How does knowing a hash help finding the correct place in the table?

# Answer
> 24 votes
The hash function *doesn't* return some string such as `mkwer`. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.

# Answer
> 7 votes
**Hash function calculates array position from given string**. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of elements.

For example I will give very poor hash for letters, just to ilustrate mechanism:
0) $x = 0;$
1) for each character in string take ascii value, subtract 'a' if it is lower case, subtract 'A' if upper case, add value to x. $x = x mod 52$
2) the resulting number e.g. 15 is index of array.

This very simple hash (limited and prone to collisions) differs from other hashes in mechanism of hashing, does not consider given input. In more advanced scheme the hash is bigger number, adjusted to number of elements. Perfect hash is generated for all inputs to guarantee no collisions.

This is $O(1)$ because calculating hash from string depends on how sophisticated is function computed, but does not depend on number of elements.

In case of perfect hash, when elements are added $h(k)$ is recalculated, the simpler case with collisions when array load is big the array size increases, function takes bigger modulo of output, and elements are shifted to the new places.

Array is continous memory fragment, to get $n-th$ element you take address of the first element (array start) and then add to this address $n * (size of element)$ so you have explicit memory cell.

# Answer
> 4 votes
To expand on David Richerby's answer, the term "hash function" is a little overloaded. Often, when we talk about a hash function we think of MD5, SHA-1, or something like Java's `.hashCode()` method, which turns some input into a single number. However the domain of this number (i.e. is maximum value) is very unlikely to be the same size as the hashtable you're trying to store data in. (MD5 is 16 bytes, SHA-1 is 20 bytes, and `.hashCode()` is an `int` \- 4 bytes).

So your question is about that next step - once we have a hash function that can map arbitrary inputs to numbers, how do we put them into a data structure of a particular size? With another function, also called a "hash function"!

A trivial example of such a function is modulo; you can easily map a number of arbitrary size to a specific index in an array with modulo. This is introduced in CLRS as "the division method":

> In the *division method* for creating hash functions, we map a key $k$ into one of $m$ slots by taking the remainder of $k$ divided by $m$. That is, the hash function is
>
> $ h(k) = k$ mod $m$.
>
> ...
>
> When using the division method we usually avoid certain values of $m$. For example, $m$ should not be a power of 2, since if $m = 2^p$ then $h(k)$ is just the $p$ lowest-order bits of $k$.
>
> *~Introduction to Algorithms, §11.3.1 - CLRS*

So modulo isn't a great hash function, since it restricts what sizes we can safely use for our underlying data structure. The next section introduces a slighly more complex "multiplication method", which also uses modulo but is advantageous because "the value of $m$ is not critical". It however works best with some prior knowledge of "characteristics of the data being hashed" - something we often don't know.

Java's `HashMap` uses a modified version of the division method that does a pre-processing step to account for weak `.hashCode()` implementations so that it can use power-of-two sized arrays. You can see exactly what's happening in the `.getEntry()` method (comments are mine):

> ```
>  // hash() transforms key.hashCode() to protect against bad hash functions
>  int hash = (key == null) ? 0 : hash(key.hashCode());
>  // indexOf() converts the resulting hash to a value between 0 and table.length-1
>  for (Entry<K,V> e = table[indexFor(hash, table.length)];
>      ...
>
> ```

Java 8 brought along a rewrite of `HashMap` which is even faster, but a little harder to read. It uses the same general principle for index lookup, however.

---
Tags: complexity-theory, hash, hash-tables, performance
---


# Question
Title: Difference between order of convergence and order of consistency?
I understand that, as the time step is reduced:

Consistency: The local error must approach zero.
Convergence: The global error must approach zero.

But why are both the order of convergence and consistency of explicit Euler = 1, if the global error is $O(h)$ while the local error is $O(h^{2})$?

More details: The Euler method is used to approximate an initial value ODE by time stepping using the derivative.

For example, for ODE form: $y'(t) = f(t,y(t)), \qquad \qquad y(t\_0)=y\_0 $

The solution at point $n$ is: $y\_{n+1} = y\_n + hf(t\_n,y\_n)$

This formula can be obtained from the Taylor expansion, where $h$ is your time step:

$y(t + h) = y(t) + hy'(t) + \frac{h^{2} y''(t)}{2!} + ... $

So the local error is of order $O(h^{2})$. Now the global error is one order less which is why Euler is called a first-order method. So my question is: Why is the order of consistency *also* 1, even though the local error is of order 2?

# Answer
A quick and dirty answer: by definition.

Let's use the definition from Wikipedia. Let $\delta^h\_{n+k}$ be the local error. A method has order $\textbf{p}$ if $$\delta^h\_{n+k} = O(h^{\textbf{p+1}}) \text{ as } h \to 0.$$

Notice $p$ and $p+1$ in the definition. Since the explicit Euler method has local error of order $O(h^2)$, $p+1 = 2$, hence $p = 1$.

On the other side, if you want to know the reason behind such definition, then I think it is about showing you the part of the solution's Taylor polynomial which the method reproduces correctly (by giving you the degree of the last correct term).
> 1 votes

---
Tags: algorithms, numerical-analysis, numerical-algorithms
---


# Question
Title: Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm
From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL\_G$) and if we find a lower bound $L\_B$ on $OPT$ then $$L\_B \leq OPT$$

and if we correctly analyze the following $$SOL\_G \leq f . L\_B$$ Then we can conclude that $$SOL\_G \leq f. OPT$$ where $f$ is the approximation factor of our greedy solution.

*Vijay Vazirani* in his book approximation algorithm on page 16 proposed the Greedy Set cover and his analysis of the lower bound on the optimum (**Lemma 2.3**). I have problem with understanding this Lemma:

From his convention at the beginning of the book, $OPT$ stands for the optimum solution of the problem instance (not the optimum that is obtained by the approximation algorithm).

At the beginning of the Lemma he says

> In any iteration, the leftover sets of the optimal solution can cover the remaining elements at a cost of at most *OPT*

It is clear because $\sum\_{e \in U} price(e) = OPT$. (The price assignment is based on the selection of the sets)

In the next sentence he says

> Therefore, among these sets, there must be one having cost-effectiveness of at most $OPT/|\bar{C}|$ where $\bar{C} = U - C$

and $C$ is the current list of selected sets.

**I can't understand, why is it true? $OPT$ is the optimum of problem instance not the algorithm. Because in the algorithm the price of each set is distributed among its elements, it seems he uses this fact but $OPT$ is not about the algorithm! it is the optimum of problem instance**

Thanks.

# Answer
Let's assume for simplicity that $C = \emptyset$; I'll let you work out the general case. Note that there are at most $|U|$ sets in OPT. Let $OPT = \\{O\_1,\ldots,O\_m\\}$, where $m \leq |U|$. We have $$ \sum\_{i=1}^m \frac{c(O\_i)}{|O\_i|} \frac{|O\_i \setminus (O\_1 \cup \cdots \cup O\_{i-1})|}{|U|} \leq \sum\_{i=1}^m \frac{c(O\_i)}{|O\_i|} \frac{|O\_i|}{|U|} = \frac{OPT}{|U|}. $$ On the left-hand side we have a weighted average of the quantities $c(O\_i)/|O\_i|$, so one of them must be at most $OPT/|U|$. The greedy algorithm selects a set $S$ with $c(S)/|S|$ minimal, so in particular $$ \frac{c(S)}{|S|} \leq \min\left(\frac{c(O\_1)}{|O\_1|},\ldots,\frac{c(O\_m)}{|O\_m|}\right) \leq \frac{OPT}{|U|}. $$
> 3 votes

---
Tags: algorithms, approximation, set-cover
---


title: Question about bigram model

text:
# Question
Title: Question about bigram model
I am trying to build a bigram letter model.

I obtain a sequence of words in a form of \['hello','I','am','Johnny'\].

Firstly, I lower all the words to obtain : \['hello','i','am','johnny'\].

I am capable of building a bigram letter model, but I have read somewhere that you should provide some kind of empty strings / padding to the model.

Does anybody know why do you have to provide padding to the input data to build a proper language model? And how to use padding on this sample input to build letter model?

I was thinking about making a space in front of every word, but I am not convinced that this is the right solution - other options that I am considering are adding padding at the end of every sentence or after each sequence of 2 characters as this is a bigram letter model.

# Answer
> 1 votes
The padding is there since the distribution of letters at the beginning and end of words is very different from their distribution inside words. To capture that, separate words with spaces and add trailing spaces on both sides: `' hello i am johnny '`.

---
Tags: natural-language-processing
---


title: Travelling plan between two places

text:
# Question
Title: Travelling plan between two places
There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$.

At each step $i$ there are two choices: stay where you are or change. Whatever you choose you pay a cost $A\_i$ or $B\_i$ depending on where you are, anyway if you change you pay also an addition that is usually a constant value.

For example, in Kleinberg's problem 6.4 you have two cities (New York and San Francisco), a set of $n$ months, a moving cost $M$ and two sequences of operating costs: $N\_1 \ldots N\_n$ and $S\_1 \ldots S\_n$. A plan is a sequence of $n$ locations, such that the $i$-th location indicates the city in which you will be based in the $i$-th month. The cost of a plan is the sum of the operating cost of each of the $n$ months, plus a moving cost of $M$ for each time you switch cities. You have to find a plan of minimum cost.

You eventually approach such problems using two variables. For example defining $OPT(i,j)$ with $i \in \left\\{1\ldots n\right\\}$ and $j\in \left\\{N,S\right\\}$ as the cost ending up in month $i$ at $j$ city . $$ OPT(i,N) = \min\left(N\_i + OPT(i-1,N), N\_i + OPT(i-1,S) + M \right) $$ $$ OPT(i,S) = \min\left(S\_i + OPT(i-1,S), S\_i + OPT(i-1,N) + M \right) $$

At the end of the process, solution is given by $\min\left\\{ OPT(n,N), OPT(n,S) \right\\}$.

This is pretty straightforward, but i perceive it as a pragmatic way. How may we prove that two variables are strictly required here? Is there any particular property related to this class of problems?

I'd like to know also if there is a way for solving it with a different recurrence with a variable only, or why if it is not possible.

# Answer
Before proving a lower bound you have to formalize your computational model. This can be done in several ways for dynamic programming. The pioneer here is Allan Borodin, who came up with priority branching trees. Buresh-Oppenheim et al. extended this to the strong model of priority branching programs. Jukna considered incremental dynamic programming algorithms,tropical circuits and tropical switching networks. The last model is particularly simple, and Jukna proves some tight results for it, so you may be able to prove that your algorithm is optimal for that model.
> 1 votes

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


# Question
Title: Solving/Optimizing a linear system in a finite field (Z/2Z)
I'm trying to solve the following optimization problem.

A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.

In the best case, there would be a solution with Y\_i = 1 for all i, and I would find it using the Gauss algorithm. But I know it's not the case.

So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and somehow backtrack when a run into a contradiction (and switch the b\_i that prevent me to get a solution). Could matrix factorization help somehow?

# Answer
> 4 votes
(Note that a *random* assignment has probability at least 1/(1+$\hspace{.03 in}$(size($\hspace{.03 in}$Y$\hspace{.03 in}$)))
of making at least 1/2 of Y's entries equal 1.  That can be derandomized
by sequentially setting each variable to \[something that forces at least
as many of Y's entries to 1 as it forces to 0, with ties broken arbitrarily\].)
By this paper's proof of Theorem 5.6, for all real
numbers $\epsilon$, if  $0 \< \epsilon$  then the promise problem

Input:  instance of your problem in which each row of A has exactly 4 ones
must output YES if:    there is an assignment which makes more than 1-$\hspace{.03 in}\epsilon$ of Y's entries equal 1
must output NO if:     for every assignment, less than  (1/2)$\hspace{.03 in}$+$\hspace{.03 in}\epsilon$  of Y's entries equal 1

is NP-hard.
When parameterized by the number of zeros in Y, your problem is obviously in W$\[\hspace{-0.02 in}$P$\]$O,
but I don't know anything else about your problem's parameterized complexity.

This paper gives a possible try for your problem,
although it looks like it's just a student's "3rd Year Project Report".

# Answer
> 2 votes
This is known as "the maximum-weight codeword problem": it is the problem of finding the maximum-weight codeword of a linear code. It is closely related to the minimum-weight codeword problem. For instance, if you add a row containing all ones, then there's a correspondence between the maximum-weight codeword and the minimum-weight codeword.

The minimum-weight codeword problem (for a general linear code) is known to be NP-hard. However, there are non-trivial algorithms for it: I believe there are algorithms with subexponential running time. (The problem has been studied extensively in the cryptographic literature.) You might look at those algorithms; perhaps they can be adapted to solve the maximum-weight codeword problem, too.

---
Tags: algorithms, optimization, linear-algebra
---


# Question
Title: Efficiently locating the maximum value in interval over large amounts of data points
I have a set of $n$ two-dimensional data points $(x\_i,y\_i)$. I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within that interval. In other words, for this query we are given an interval $\[\ell,u\]$, and we want to find the point $(x\_i,y\_i)$ such that $x\_i \in \[\ell,u\]$ and $y\_i$ is maximal (or minimal).

What data structure would be appropriate for this task? I'm interested in both the static case (where the set of points doesn't change) and the dynamic case (where we also want to be able to insert and/or delete points from the set).

# Answer
> 4 votes
This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time.

Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-coordinate of the points (so the leaves contain the points, sorted from left to right). Augment the tree, so that in each node $t$ of the tree, you store a pointer to the highest and lowest of all the points within the subtree rooted at $t$.

Now we are given an interval $\[\ell,u\]$, and asked for the highest point whose $x$-coordinate is within that interval. It turns out that any such interval can be expressed as a union of $O(\lg n)$ subtree. In other words, you can find nodes $t\_1,t\_2,\dots,t\_k$ such that (1) every leaf that is a descendant of some $t\_i$ has an $x$-coordinate in the interval $\[\ell,u\]$, (2) every leaf whose $x$-coordinate is in the interval $\[\ell,u\]$ is the descendant of one of these $t\_i$'s, and (3) $k = O(\lg n)$. Recall that the augmentation tells you what is the highest leaf under each $t\_i$. So, to answer the query, take the highest of all those: that will be the highest leaf whose $x$-coordinate is within $\[\ell,u\]$. Since we only need to examine $O(\lg n)$ nodes, the running time is $O(\lg n)$.

How do you find those $k$ nodes? That's described here: Delete a consecutive range of leaves from a binary tree. You can verify that you can find those $k$ nodes explicitly in $O(\lg n)$ time, given $\ell$ and $u$.

Conveniently, this data structure works both for the static case (where the set of points doesn't change) as well as the dynamic case (where we want to insert and delete points). You can insert and delete points in $O(\lg n)$ time: in particular, you can update the augmented information within those time bounds (you just have to touch each node on the path to the root from the inserted/deleted node).

---
Tags: algorithms, data-structures, search-problem, intervals
---


title: Question on synchronisation

text:
# Question
Title: Question on synchronisation
The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

```
P1() {

    C = B - 1;
    B = 2 * C;
}

P2(){

    D = 2 * B;
    B = D - 1;
}

```

The set of distinct values that B can possibly take is ?
My understanding: Say *P1* executes first , then *B=2*, after that *P2* executes next then value of *B=3*. Again *P1* executes and we get *B* value as *4*, yet again *B* executes and we get *B* value as *7* etc. So does this mean *B* will take up infinitely many values? The order of my execution is *P1-P2-P1-P2-P1....* Is this correct?

# Answer
> 1 votes
Label the four statements $$\begin{align} x &: C=B-1\\ y &: B=2C\\ z &: D=2B\\ w &: B=D-1 \end{align}$$ The only constraint is that $x$ must be executed before $y$ and $z$ must be executed before $w$, giving us six possible orders: $xyzw,xzyw,xzwy,zxyw,zxwy,xwzy$. Trace the execution of each of these possible orders and you'll find that $B$ can have a final value of $2$ (twice), $3$ (three cases), and $4$ (in one case).

For what it's worth, if P1 consists of $n$ assignments and P2 has $m$ assignments, the total possible orders is given by the binomial coefficient $\binom{n+m}{n}$, though that won't necessarily be the same as the number of possible final values of the shared variable $B$.

# Answer
> 1 votes
Each of the two functions (P1 and P2) has two statements. Each statement is labelled as follows:

```
            function P1() {             function P2() {
    T_0^0:    C = B – 1;        T_0^1:    D = 2 * B;
    T_1^0:    B = 2 * C;        T_1^1:    B = D – 1;
            }                           }

```

Assumptions:

1. Every statement is atomic; it executes without pre-emption.
2. There is one processor. When the processor is executing a statement it cannot be interrupted. After the statement executes, it can switch to executing any other statement that has not yet executed.
3. Each of the functions executes once.
4. Precedence constraints:

o T\_0^0 executes before T\_1^0 executes.

o T\_0^1 executes before T\_1^1 executes.
5. The initial values of B, C and D are 2, 0 and 0 respectively.

To answer the question “what are the possible values of B?”

1. List all possible execution sequences

a. T\_0^0  T\_1^0  T\_0^1  T\_1^1

b. T\_0^0  T\_0^1  T\_1^0  T\_1^1

c. T\_0^0  T\_0^1  T\_1^1  T\_1^0

d. T\_0^1  T\_1^1  T\_0^0  T\_1^0

e. T\_0^1  T\_0^0  T\_1^1  T\_1^0

f. T\_0^1  T\_0^0  T\_1^0  T\_1^1
2. Compute the value of B for every execution sequence. To assist in this computation, an interactive, dynamic Petri Net model of the computation was created (see Figure 1): to execute a statement, click on a green square. An interactive, dynamic source code of the computation was also provided (see Figure 2): to execute a statement, click on a green rectangle.\[For the PDF version of this reply, the figures are interactive, dynamic diagrams.\]

Figure 1

Figure 2 Please see PDF version of this reply

```
Thus, the possible values of B, C and D are:

Computation Sequence                B   C   D
T_0^0  T_1^0  T_0^1  T_1^1     3   1   4
T_0^0  T_0^1  T_1^0  T_1^1     3   1   4
T_0^0  T_0^1  T_1^1  T_1^0     2   1   4
T_0^1  T_1^1  T_0^0  T_1^0     4   2   4
T_0^1  T_0^0  T_1^1  T_1^0     2   1   4
T_0^1  T_0^0  T_1^0  T_1^1     3   1   4

```

---
Tags: algorithms, concurrency, synchronization
---


# Question
Title: What does > mean in this TAOCP solution?
For our assignment we have to implement a solution given to one of the problems in *The Art of Computer Programming* by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.

> ***Problem:*** Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.
>
> At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?
>
> In other words, given the pairs $(x\_i, x\_{i+1})$ for $1 \le i \< N$, in random order, where the $x\_i$ are distinct, how can the sequence $x\_1 x\_2 \ldots x\_N$ be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other.

---

> ***Solution by Norman Hardy, c. 1967:*** Make another copy of the input file; sort one copy on the first components and the other on the second. Passing over these files in sequence now allows us to create a new file containing all pairs $(x\_i, x\_{i+2})$ for $1 \le i \le N-2$ and to identify $(n-1,x\_{n-1})$. The pairs $(n-1, x\_{n-1})$ and $(n,x\_n)$ should be written on still another file.
>
> The process continues inductively. Assume that file F contains all pairs $(x\_i,x\_{i+t})$ for $1 \le i \le n - t$, in random order, and that file $G$ contains all pairs $(i,x\_i)$ for $n-t \< i \le n$ in order of the second components. Let $H$ be a copy of file $F$, and sort $H$ by first components, $F$ by second. Now go through $F$, $G$, and $H$, creating two new files $F'$ and $G'$, as follows. If the current records of files $F$, $G$, $H$ are, respectively $(x,x')$, $(y,y')$, $(z,z')$, then:
>
> 1. If $x' = z$, output $(x,z')$ to $F'$ and advance files $F$ and $H$.
> 2. If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.
> 3. If $x' \> y'$, advance file $G$.
> 4. If $x' \> z$, advance file $H$.
>
> When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.

So here is my question:

> 3. If $x' \> y'$, advance file $G$.
> 4. If $x' \> z$, advance file $H$.

What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is it referring to string size?

# Answer
> 7 votes
> What does \> denote here?

It's not stated explicitly, but a reasonable meaning can be inferred from context.

The authors assume that the data can be *sorted* so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.

For instance, if we wanted to sort natural numbers in increasing order, $\>$ would mean the usual. I we wanted to sort them in *decreasing* order, you'd have to replace $\>$ by $\<$ in the solution.

---
Tags: algorithms, sorting, notation
---


# Question
Title: What are functions called that yield the same result when applied to one of their result values
Suppose one of the following holds for all `x`, or all `y`, or all `z`:

```
f(f(x)) = f(x)
f(f(y)) = f(y)
f(f(f(z))) = f(f(z)) = f(z)

```

... how do you call such a function?

# Answer
A function satisfying that property is called idempotent.
> 7 votes

---
Tags: terminology, functional-programming, mathematical-foundations
---


# Question
Title: Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$?
Does the Context Free Language $\\{(1^n2^n)^t \mid t,n\ge0\\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.

# Answer
> 4 votes
$t$ and $n$ are independent numbers. Any string in the language consists of $t$ units, where each unit consists of $n$ $1$s followed by $n$ $2$s. In particular, then, the string generated by any choice of $t$ and $n$ contains $tn$ $1$s and $tn$ $0$s.

# Answer
> 1 votes
The way language is defined 121122 is not an acceptable string. 1212 or 11221122 is acceptable string.

The string 121122 belongs to another similar language $L\_1$ where $L = \\{1^n2^n\ |\ n \geq 0 \\}$, $L\_1 = L^\*$. This might be the source of confusion.

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


title: Flipping accept states DFA vs. NFA

text:
# Question
Title: Flipping accept states DFA vs. NFA
I realized that if a language L is recognized by a DFA, then **flipping its accept and reject states** (aka switching all the accept to reject states and all the reject states to accept) works to recognize the complement of L (which wold be L^c).

I was curious if that worked also with NFAs (flipping the accept and reject states to go from L to L complement), but with their additional paths it doesn't seem like it would work..Definitely seems like it would have too many accept states that aren't correct.

Is this correct? Is there more to it? Thank you!

# Answer
> 2 votes
Same thing does not hold for an NFA. Example

```
q0 -> 0 -> q1
q0 -> 0 -> q2

```

q0 is the start state, q1 is the final state.

---
Tags: automata, finite-automata
---


title: Which process comes first?

text:
# Question
Title: Which process comes first?
Let's say we have 3 processes:

* Process 1 service time 6 arrival time 0
* Process 2 service time 2 arrival time 1
* Process 3 service time 5 arrival time 3

We know that:

* after 1 time, process 2 will come and process 1 will go back having 5 service time left.
* then process 3 will come, after process 2 ends, at 3 time.

Now the conflict is:

Since process 1 and process 3 have equal service time - which one gets service time first?

# Answer
This really depends on the scheduling algorithm. Most of the scheduling algorithms will decide arbitrary. I assume that you are talking about shortest-job-first. SJF will schedule arbitrarily.

The real life scheduling algorithms are round-robin as we usually do not know the completion time. And they usually want to give a quick response to a new job. These algorithms will schedule process 3.
> 1 votes

---
Tags: operating-systems, concurrency, process-scheduling
---


# Question
Title: Graph "coloring" problem minimal number, each edge has a colored end
(there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not covered that in the lecture yet.)

again I am facing homework and thus, would appreciate it, if you did not(!) give me the solution, but helped me to get there on my own.

I've got an exercise to solve and I think, I'm pretty close, but I seem to can't get there.

I've got a graph and have to color the vertices such that the following conditions are met:

-there are two colors (a,b)

-each edge has precisely ONE a-colored vertex

-the number of a-colored vertices is minimal

I've tried to reduce the problem to 2-coloring. BUT: I don't know how to deal with the condition that the number of a-colored vertices has to be minimal. I am pretty sure that I can reduce it to a coloring problem, because I also need to show NP-completeness.

Can anyone push me into the right direction?

# Answer
A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x\_i$ vertices on one side, and $y\_i$ on the other side. Which side would you color $a$?
> 3 votes

---
Tags: graphs
---


# Question
Title: Designing a DFA for binary strings having 1 as the fourth character from the end
I came across someone else's old post here

Designing a DFA that accepts strings such that nth character from last satisfies condition

And decided to try it. Apparently it was a homework problem but it was from 2013 so I assume it is okay to discuss it openly by now.

The problem is:

> Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

The regular expression that does this I believe is `(0|1)*1(000|001|010|011|100|101|110|111)`.

My NFA:

Used Google to see how DFAs work and tried this translation:

Was this a valid solution to the problem?

(Blue arrow = points to starting state, green states are accepting states)

# Answer
> 2 votes
You have not created a DFA.

What you have created is a second slightly less messy NFA. (Sort of; as mentioned in comments elsewhere you need the explosion of internal states out from (2) that you have out from (9) in the original NFA)

So let's pretend that we have an NFA that is made by chopping off state (2) in the second picture and adding state (9) from the first picture in its place.

Now, let's walk through the powerset construction on that new NFA:

Start in state `{1}`. So let's call the DFA state corresponding to the singleton set `{1}`, `DFA_1`.

From `DFA_1` you can see either a `0` or a `1`. On `0`, `DFA_1` goes to `{1}`, so `DFA_1` again. On `1`, it goes to `{1,9}`. Call that `DFA_2`.

From `DFA_2`, on `0` it goes to `{1,10,13,16,19}`. Call that `DFA_3`. On `1` it goes to `{1,9,22,25,28,31}`. Call that `DFA_4`.

For `DFA_3`, on `0` it goes to `{1,11,14}` (since the other nodes only have transitions out on `1`). Call that `DFA_5`. On `1`, from `DFA_3` we go to `{1,9,17,20}`. Call that `DFA_6`.

For `DFA_4`, on `0` it goes to `{1,10,13,16,19,23,26}` \- call that `DFA_7`. On `1`, `DFA_4` goes to `{1,9,22,25,28,29,31,32}`. Call that `DFA_8`.

For `DFA_5`, on `0` it goes to `{1,12}`. Call that `DFA_9`. Note that `DFA_9` is an accepting state. On `1` it goes to `{1,9,15}`. Call this `DFA_10`, also an accepting state.

For `DFA_6`, on `0` it goes to `{1,10,13,16,18,19}`. Call this `DFA_11`. On `1`, we get `{1,9,21,22,25,28,31}`. Call this `DFA_12`. Note that `DFA_11` and `DFA_12` are accepting states.

For `DFA_7`, on `0` it goes to `{1,11,14,24}`. Call that `DFA_13`. On `1`, we get `{1,9,17,20,27}`. Call that `DFA_14`. (DFA states 13 and 14 are accepting states)

For `DFA_8`, on `0` it goes to `{1,10,13,16,19,23,26,30}`. Call that `DFA_15`. On `1`, it goes to `{1,9,22,25,28,29,31,32,33}`. Call that `DFA_16`. (DFA states 15 and 16 are accepting states)

For `DFA_9`, on `0` it goes to `{1}`. We've seen this before! That's `DFA_1`. On `1` it goes to `{1,9}`, which is `DFA_2`.

For `DFA_10`, on `0` it goes to `{1,10,13,16,19}`, that is, `DFA_3`. On `1` it goes to `{1,9,22,25,28,31}`, that is `DFA_4`.

For `DFA_11`, on `0` it goes to `{1,11,14}`, which is `DFA_5`. On `1` it goes to `{1,9,17,20}`, that is, `DFA_6`.

For `DFA_12`, on `0` it goes to `{1,10,13,16,19,23,26}`, or `DFA_7`. On `1`, it goes to `{1,9,22,25,28,29,31,32}`, or `DFA_8`.

For `DFA_13`, on `0` it goes to `{1,12}` (`DFA_9`). On `1` it goes to `{1,9,15}` (`DFA_10`).

For `DFA_14`, on `0` it goes to `{1,10,13,16,18,19}` (`DFA_11`). On `1`, we get `{1,9,21,22,25,28,31}` (`DFA_12`)

For `DFA_15`, on `0` it goes to `{1,11,14,24}` (`DFA_13`) On `1`, we get `{1,9,17,20,27}` (`DFA_14`).

For `DFA_16`, I hope you can see the pattern by now. On `0` it goes to `DFA_15` and on `1` to `DFA_16`.

So, in summary:

```
DFA state #  |   Next for 0  |  Next for 1  |  Accepting?
---------------------------------------------------------
          1  |       1       |      2       |
          2  |       3       |      4       |
          3  |       5       |      6       |
          4  |       7       |      8       |
          5  |       9       |     10       |
          6  |      11       |     12       |
          7  |      13       |     14       |
          8  |      15       |     16       |
          9  |       1       |      2       |  yes
         10  |       3       |      4       |  yes
         11  |       5       |      6       |  yes
         12  |       7       |      8       |  yes
         13  |       9       |     10       |  yes
         14  |      11       |     12       |  yes
         15  |      13       |     14       |  yes
         16  |      15       |     16       |  yes

```

As a side note, I think this process might have been simpler had you started with an NFA of only 5 states corresponding to the regex `(0|1)*1((0|1)(0|1)(0|1))`.

(Though you'd still end up needing 16 DFA states - it can be proven that that's the minimal number of DFA states needed for this problem)

# Answer
> 1 votes
No. The problem statement asks for a DFA. Your solution isn't a DFA; it's a NFA. For instance, it has two transitions out of the start state on the symbol 1. So, this is not a valid solution.

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


# Question
Title: Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions
I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk stating specifically that :

> If a transition graph has a walk labeled $w$, then there is a walk *w* of length no more than $\Lambda + (1 + \Lambda)|w|$ where $\Lambda$ is the number of $\lambda$ transitions in the graph.

The book does not define $|w|$ which is causing part of my confusion. I'm assuming $|w|$ is the length of the label of the walk. So in this case it would be 1 when going from $q\_1 \to q\_0 \to q1$ because $a$ is the only labeled edge. I am trying to understand this concept and how it works because when I have tested out this claim it has not held true.

Here is the test I did with this NFA

$q\_1$ is the final state. So assuming you were trying to find the length of the walk $a$, the label would indicate that the length is 1 (e.g. $\delta^\* (q\_1, a)$) . However due to the lambdas you actually have $\lambda \lambda a$ to go from $q\_1 \to q\_0 \to q\_1$.

This theorem doesn't hold with my math though because it is defined as Λ + (1 + Λ)|w| where Λ is the number of λ-edges in the graph.

Since there are two λ-edges (and it doesn't state whether it means λ-edges in the walk itself or in the graph in total...) this would then be 2 + (1 + 2)|w|. So thats 2 + 3|w|. This clearly is more than 3, which is the length of q1 -\> q1 of λλa.

What am I missing here? Any help is greatly appreciated.

This comes from Peter Linz "An Introduction to Formal Languages and Automata" 5th edition.

Some more information about the argument for this claim:

> While λ-edges may be repeated, there is always a walk in which every repeated λ-edge is separated by an edge labeled with a nonempty symbol. Otherwise, the walk contains a cycle labeled λ, which can be replaced by a simple path without changing the label of the walk.

Also the book never names this as a theorem or lemma or anything of the sort so it has been very difficult to find online resources about this topic.

# Answer
The length of the walk is the number of edges in the walk. Suppose $p$ is a walk labeled $w$. We can decompose $p$ into $p\_1 e\_1 p\_2 e\_2 \cdots p\_{|w|} e\_{|w|} p\_{|w|+1}$, where each $p\_i$ consists only of $\lambda$-transitions, and $e\_i$ is a transition labeled $w\_i$. There is always an equivalent walk in which no transition is taken twice in each $p\_i$ (this is what is proved in the paragraph you quote), and so $|p\_i| \leq \Lambda$. Therefore the entire walk has length at most $(1 + \Lambda) |w| + \Lambda$.
> 1 votes

# Answer
|w| is the length of the input word being read for example if w=a then |w|=1 . if w=aaa then |w|=3 and Λ is the number of λ-edges in the graph.

for example to read the symbol **a** its 2+(1+2)\*1=5 so all the walk to read **a** have a lentgh less or equal than **5**

∂\*(q0,a)={q1,q2,q0} of length 3≤5 because the path is q0-\>q1-\>q2-\>q0

∂\*(q1,a)={q1,q2,q0} of length 5≤5 because the path is q1-\>q2-\>q0-\>q1-\>q2-\>q0

∂\*(q2,a)={q1,q2,q0} of length 5≤5 because the path is q2-\>q0-\>q1-\>q2-\>q0
> 0 votes

---
Tags: graphs, finite-automata, nondeterminism
---


title: Computer cache - data removing

text:
# Question
Title: Computer cache - data removing
I am programming **CPU cache simulator** and I am supposed to implement removing of entries. I will not use LRU but just random.

I am not really clear, when should I call the removing function? When cache *(2 or 4 caches)* are full and CPU wants to write into cache where all *(data and tag)* of specific indexes are same? Are there some other possible situations, or maybe I am completely wrong?

Hope you understand my question, if no, please tell me and I will edit my question. Thank you in advance.

# Answer
> 6 votes
Cache lines are evicted :

* When the OS requests it, it may occur for example in non cache-coherent systems when a peripheral does a DMA transfer (direct transfer from a peripheral to main memory), or if the CPU is shut down to save its state to RAM...
* When all the ways of the cache are already used for the requested line.

In a write-through cache, new data can be directly loaded, overwriting previous contents. In a write-back cache, if the cache line was modified, it must be written back before loading new data.

There could be other exceptional cases, for example if a parity error is detected and new data must be loaded... But, generally, caches are filled but never emptied.

# Answer
> 2 votes
The simple (possibly, overly simplified) answer is that you need to remove entries whenever a new entry is to be written to the cache, but the cache is full.

That is, if there is a memory access which is a miss and the record is brought to the cache from the main memory, but there is no place to put the new record (all possible places *for that record* are full), you need to make some room by removing one of the records.

Of course, you should write the record(-to-be-removed) back to the main memory before removing it form the cache, and obviously, you should remove a record that resides in the cache in a place that can be used to place the new record. Note that the cache needs not be completely full -- whatever happens in entries where the new record cannot be mapped to is irrelevant.

---
Tags: terminology, computer-architecture, cpu-cache, memory-hardware
---


# Question
Title: Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n))
I have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? I'm lost..

# Answer
Let $d(n) = 2n$ and $e(n) = n$. Then $$d(n)-e(n) = n.$$ Since $d(n) = O(n)$ and $e(n) = O(n)$, we have that $$f(n) = g(n) = n,$$ so $$O(f(n)-g(n)) = O(n-n) = O(1),$$ and clearly $$n \neq O(1).$$
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: How to properly solve T(n) = T(n-1) + O(2^n)?
I've been trying to solve this recurrence: **T(n) = T(n-1) + O(2^n)**

My approach when writing everything out and solving the geometric series was: T(n) = O(2^n).

T(n) = c2^n * (1 + 1/2 + 1/4 + ...)

= c2^n * (1/2)^i for i from 0 to infinity

T(n) \<= d\*2^n for some constant d.

# Answer
> 2 votes
What you did is fine for most purposes. If you want a really rigorous proof without "dot dot dots," then you need to use induction. For that you need to make the constant in big-Oh explicit, and use your "back of the envelope calculation" to come up with the induction hypothesis.

---
Tags: recurrence-relation
---


# Question
Title: Is the halting problem always decidable for non-universal programs?
For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ halts on $I$?

**Some concrete definitions:**
A program $P$ that takes some data type $D$ as input is **computable** iff there exists some total computable function $h$ that takes a input string and returns a $D$, and some Turing machine $T$, which takes a binary string, such that $P(h(I)) \cong T(I)$ for all strings $I$. "$\cong$" includes both not halting as well as both producing the same output.

A program $P$ that takes some data type $D$ as input is **universal** iff there exists some total computable function $f$ that takes both a description of a Turing Machine and an input string and produces something of type $D$ such that for every Turing machine $T$ and every string $I$, $P(f(T, I)) \cong T(I)$.

# Answer
> 5 votes
To answer the first part of your question - Two counter machines are not exactly Turing-complete. That is, there are some functions that cannot be computed with them, for certain counter-values. This is a very slight weakness, so 2CM are actually very close to being Turing complete, but still.

As for your suggested model - could you formalize it in more detail? It's not clear enough as it is.

# Answer
> 4 votes
You might feel this is a cheat but consider the following "model". A program is a natural number and the meaning of program $P$ is as follows. If the Turing machine whose code is $P$ halts when started with a blank tape, then program $P$ just halts; otherwise, $P$ loops forever.

This is not Turing powerful because, up to operational equivalence, there are only two programs: one is equivalent to "halt" and the other to "loop forever". However, no Turing machine can decide, when given $P$, whether $P$ halts.

# Answer
> 1 votes
a more limited version of automata used for verification are known as "counter machines" with some associated decidable problems, but also an undecidable halting problem (Theorem 6 p4).

# Answer
> 0 votes
Yes. That is essentially base of a lot of work in formal methods/model checking in software engineering. See e.g.

It has been some time but IIRC Moshe Vardi gave a talk a few years ago at the Fields institute on their work on how they solve some hard problems about programs in practice. The intuition, if I remember correctly, was that you can define a parameter for programs and although the running time increase uncomputably as that parameter increases for programs that we care about in practice the parameter is rather small and as a result the problem is tractable in practice. I will add a link to their paper if I recall it.

---
Tags: turing-machines, turing-completeness
---


title: Universal/existential quantification?

text:
# Question
Title: Universal/existential quantification?
I'm struggling to understand the purpose of universal and existential quantification of types. I'm playing around with writing a toy language based on the calculus of constructions. I've been reading about Morte and Henk to help me get a better understanding.

I don't understand why the CoC has both lambda and forall abstraction.

$$(\lambda x:A . B)$$ $$(\forall x:A . B)$$

It seems to me that lambda subsumes forall in a system where types are passed manually. In other words, that the following

$$(\forall x : \*. \lambda a : x. a)$$

Could be replaced with

$$(\lambda x : \*. \lambda a : x. a)$$

If it was first applied to the type being used.

What am I missing? What papers or blogs or articles are there to read that might help me?

Thanks.

# Answer
> 12 votes
It helps to remember that $\forall$ (or $\Pi$ as you sometimes see) is a type. It's generalizing $\to$. So while it makes perfect sense to say $(\lambda x : A. M)\ N$, it doesn't make sense to say $(\forall x : A. M)\ N$ because $\forall ...$ is just a type. You wouldn't say $(A \to B)\ N$ becaues $\to$ isn't for computing per-se, it's there to *classify lambda terms which can be applied like this*.

This was something that tripped me up as well, but this is how the calculus of constructions (as well as any other dependently typed system is defined).

The two programs you wrote have very different intentions and the first one is ill-typed. It doesn't make sense to say $\forall x : A.\ \lambda x.\ x$ because $\forall$ requires both its arguments by types which means that if $\forall x : A. B$ is to be well-typed, we must have $B : \*$. However, $\lambda x. x$ isn't a type, it can only ever be assigned a type of the form $\forall x : A. B$, never $\*$. The second one on the other hand is almost (I think you meant to return $a$ not $x$) is a function and is given a type using two $\forall$s.

# Answer
> 5 votes
Keep in mind that existential and universal types are rather different. It is constructive logic, not classical logic and in constructive logic $\forall$ and $\exists$ are not as related as they are in classical logic.

$\forall x:A. B(x)$ is the type of programs that receive an object of type $A$ and return an object of type $B(x)$. The important thing here is that the type $B(x)$ *depends* on $x$ and is not the same for all $x$. It can vary depending on what $x$ is. For one input $x$ we might output an integer. For another one we might output a real number. For yet another one we might output a function over real numbers. If $B(x)$ doesn't vary with $x$ then you can use $A\to B$ in place which is the type of functions from $A$ to $B$.

$\exists x:A. B(x)$ is the *dependent* version of (constructive) disjunction. You can think of constructive disjunction $A \lor B$ of two types $A$ and $B$ as the disjoint union of $A$ and $B$. $\exists x:A.B(x)$ is the disjoint union of a collection of types $B(x)$ indexed by $x:A$. The fact that the type $B(x)$ van vary depending on the value of $x:A$ makes it a dependent type. Compare with the case where $B$ does not depend on $x:A$: $\exists x:A. B$. We are taking one copy of the same $B$ for each $x:A$. This is isomorphic to $A \times B$.

Now you can ask why we need *dependent* product and sum types? Because they give us more expressive power. Now we can ignore the types completely and have untyped type theory/functional programming. But that removes the benefits of having types in the first place, e.g. you will not know if all programs will always terminate (strong normalization). See Lambda Cube and Dependent Type. I think a good way to understand dependent types well is to look at the rules for introducing and eliminating the dependent types in Martin-Lof's type theory.

The main point of dependent types is: we want to remain inside a nice typed theory for various reason (e.g. avoiding bugs, automatic proof of termination, etc.). We don't want to go to something like untyped lambda calculus where we can make expressing like those you stated and way more powerful stuff. We can say that dependent types were invented to allow expressing more things while still remaining inside a nice type theory.

---
Tags: lambda-calculus, type-theory, calculus-of-constructions
---


# Question
Title: Why do Θ-bounds not survive taking differences?
$f\_1$, $f\_2$, $g\_1$, and $g\_2$ are functions such that:

$$f\_1 = \Theta(f\_2)$$ $$g\_1 = \Theta(g\_2)$$

I was able to prove that:

$$\frac{f\_1}{g\_1} = \Theta\biggl(\frac{f\_2}{g\_2}\biggr)$$

But I can't understand why the following statment is not necessarily true:

$$f\_1 - g\_1 = \Theta(f\_2 - g\_2)$$

# Answer
> 12 votes
The proof is by counterexample. Consider the following functions:

$$f\_1(x) = 2x$$ $$f\_2(x) = x+1$$ $$g\_1(x) = x$$ $$g\_2(x) = x$$

First, we can see that $f\_1 = \Theta(f\_2)$ and $g\_1 = \Theta(g\_2)$. Finding constants to prove the four big-Oh relationships involved is straightforward (in particular for $g\_1$ and $g\_2$).

Next, we can observe that $f\_1 - g\_1 = x \neq \Theta(1) = \Theta(f\_2 - g\_2)$.

Notice that the choice of $2$ and $1$ for the above functions is unimportant, so long as you choose them so that the difference between $f\_1$ and $g\_1$ is more than constant and the difference between $f\_2$ and $g\_2$ is constant.

# Answer
> 0 votes
If $f\_2 = o(g\_2)$ then it is indeed the case that $f\_1 = \Theta(f\_2)$ and $g\_1 = \Theta(g\_2)$ imply that $|f\_1 - g\_1| = \Theta(|f\_2 - g\_2|)$ = \Theta(f\_2). Same works if $g\_2 = o(f\_2)$. Otherwise there no guarantee possible – you can easily come up with examples in which $|f\_1-g\_1| = o(|f\_2-g\_2|)$ (for example $f\_1=g\_1=f\_2=n$ $g\_2=2n$) or $|f\_1-g\_1| = \omega(|f\_2-g\_2|)$ (for example $f\_2=g\_2=f\_1=n$, $g\_1=2n$).

---
Tags: asymptotics, landau-notation
---


# Question
Title: Is the complement of the given language necessarily in NP?
> $A$ is a given language so that $A \in NP$.
>
> Assume that $P = NP$.
>
> Is $A'$ necessarily in NP?

What I did:

$A \in NP , P=NP$

$P=coP$ (Can be proven by running a TM $M$ as a decider for P, and building a TM $M'$ and switching 'accept's to 'reject's and vice-versa).

---

If $P=NP$, then $L \in NP \Rightarrow L \in P$

$P=coP \Rightarrow L' \in P \Rightarrow L' \in NP \Rightarrow L \in coNP$

---

Which proves that $coP=coNP$

And hence that $NP=coNP$

So $A \in NP \Rightarrow A \in coNP \Rightarrow A' \in NP$

**So the answer is YES**

---

Is this the correct way of solving this kind of questions?

Is there a better way?

Did I make any mistakes?

Is the proof of $coP=coNP$ correct?

Thanks in advance

# Answer
> 1 votes
You are correct. Though you don't have to argue over accept/reject states. You can exploit that deterministic languages are closed under complement.

That can make your argument very concise: $A \in NP \Rightarrow A \in P \Rightarrow A' \in P \Rightarrow A' \in NP$

---
Tags: complexity-theory, time-complexity, closure-properties, np
---


# Question
Title: Detecting all cycles in un-directed graph
I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a cycle, but what if i want to continue to find other cycles? how would i make any node to be considered for other cycle?

# Answer
> 0 votes
Following is an algorithm better than the brute force search.

Given graph $G$, find the DFS tree $T$ of $G$. We know from the structural property of $T$ that any for edge $(u,v)$ in $G$, we have that either $u$ is an ancestor of $v$ in $T$ or $v$ is an ancestor of $u$ in $T$. Therefore, brute force search for cycles in $G$ only along subsets of the branches in $T$. This is equal to the trivial brute force search if $G$ is a clique but better otherwise.

However, one can hope for better heuristics. For instance, see \[1\].

\[1\] Hongbo Liu, Jiaxin Wang: A new way to enumerate cycles in graph. AICT/ICIW 2006: 57.

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


title: Is the empty string of even length?

text:
# Question
Title: Is the empty string of even length?
There is this example of regular expressions:

$$(\Sigma\Sigma)^\*= \\{w\mid |w|\text{ is even}\\}\\,.$$

From that I understand the empty string is valid as a string of even length. Is this true?

# Answer
> 8 votes
A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.

# Answer
> 1 votes
Even number - Even number = even number.
Odd number - odd number = even number.
0 - 0 = 0
Since it cannot change parity it must be even.

Furthermore 0's neighbours are odd, which also implies it is even (as every second number has the same parity).
Zero parity

# Answer
> -1 votes
Yes, that's correct. Empty string is valid as string of even length.

If you consider any language of even length of strings, it will also include an empty string.So, it is true.

---
Tags: formal-languages, regular-expressions, modular-arithmetic
---


# Question
Title: Regular languages that can't be expressed with only 2 regex operations
I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular operations (concatenation, union, and star) for that to hold.

For example, I have been told that **if I can *only* use the union and concatenation** regex operations (2 out of the 3), there would be a regular language I can't describe with just those two.

Same with just Kleene star and union. What are some examples of this?

# Answer
With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \\{ab\\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only concatenation and the Kleene star, you can't describe a language such as $L = \\{a,b\\}$.
> 19 votes

# Answer
A perhaps more interesting question is that of star height. The other answer mentions that if you can't use star, then you can only generate finite languages. What if you are not allowed to *nest* stars (so something like $(a^\*b^\*c)^\*$ is not allowed)? What if you are only allowed to nest stars two levels deep? $d$ levels deep? It turns out that for every $d$ there are regular expressions expressible in nesting $d$ but not in nesting $d-1$. The link contains some examples.
> 11 votes

# Answer
Another interesting case arises by allowing complementation as a possible operation. Using union, concatenation and complement (but no star), one can obtain the language $A^\*$ as the complement of the empty language. One can also obtain languages like $(ab)^\*$ and $(a(ab)^\*b)^\*$ (not so easy to see if you don't know the trick), but there is no way to obtain $(aa)^\*$.

If one now allows to use star, but not *nested* stars, then it is an open problem (for at least 45 years) to know whether one can obtain all regular languages. This question is known as the generalized star height problem. It is similar to the star height problem mentioned by Yuval Filmus, with the difference that complementation is now allowed.
> 4 votes

---
Tags: formal-languages, regular-languages, regular-expressions, kleene-star
---


title: complement of a language-nfa

text:
# Question
Title: complement of a language-nfa
hi i know that the question 5 is true because by definition w ∈ L if and only if δ\*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L"

but iam really confused about the question 6 our teacher told us that it's false but i think it's true because i don't see any difference between the 2 questions

i get this picture from peter linz book : An-Introduction-to-Formal-Languages-and-Automata

# Answer
Your teacher is right. $\delta^\*(q\_0, w) \cap (Q - F) \neq \emptyset$ does not necessarily imply that $\delta^\*(q\_0, w) \cap F = \emptyset$. Question 5 says that you don't terminate in any of the accept states, question 6 says that you terminate in some non accepting states, but NFA can still terminate in some accepting state.
> 0 votes

---
Tags: regular-languages, automata
---


# Question
Title: Distributed parallel computing algorithms for content dependent data
I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel and send data to master node. Here linear improvement in encoding is seen as number of nodes are increased. But now I want to further optimize this algorithm to get better results. Chunks I send to different machines might take different amount of time for encoding depending on content in that video chunk. So which algorithms in distributed parallel processing can be used here to optimize this process? To implement his system I am using OpenMPI framework.

# Answer
> 2 votes
You have a static number of tasks to be executed, and each task is independent (i.e., no communication among tasks is required). However, the chunks assigned to different machines might take a different amount of time for encoding.

In this situation, the simplest and probably the best possible approach, consists in cyclically mapping tasks to processors, in order to balance the computational load. This is a form of probabilistic mapping (see sub-section on Probabilistic Methods and Cyclic Mappings, just before Section 2.5.2 on the linked web page). As an example, if you have $p$ processors and $n$ tasks (with $n \> p$), you can simply assign task $i$ to processor $i \mod p$.

---
Tags: optimization, distributed-systems, parallel-computing, scheduling
---


# Question
Title: Is the following language decidable, enumerable or non-enumerable?
$$L = \\{\langle M\_1 \rangle, \langle M\_2 \rangle \mid \text{\\(M\_1\\) and \\(M\_2\\) are TMs and \\(\forall X, M\_1(X) = M\_2(X)\\)}\\}$$ Is this language decidable, enumerable, or non-enumerable?

And in general, how can I tell if a language is decidable, non-decidable, semi-decidable, enumerable or non-enumerable? I am confused.

# Answer
> 1 votes
The language TOT of all Turing machines halting on all inputs reduces to your language $L$ (take $M\_2$ to be a constant machine that always halts, and ensure that both machine have the same outputs when they do halt), so $L$ is $\Pi\_2$-hard. It's not difficult to write a $\Pi\_2$ expression for $L$, so we conclude that $L$ is $\Pi\_2$-complete. In particular, it's neither r.e. nor co-r.e.

If you don't understand these concepts, I suggest following Shaull's advice and reading a textbook on computability, and then to read some stuff on the arithmetical hierarchy.

# Answer
> 1 votes
The language $E=\\{\langle\\,M\\,\rangle\mid M \text{accepts no string}\\}$ is known to be not recursively enumerable. Consider a reduction $E\le L$ defined by $$ \langle\\,M\\,\rangle\mapsto (\langle\\,M\\,\rangle,\langle\\,Z\\,\rangle) $$ where $Z$ is a TM that accepts no string. Then it's not hard to show that $$ \langle\\,M\\,\rangle\in E\Longleftrightarrow(\langle\\,M\\,\rangle,\langle\\,Z\\,\rangle)\in L $$ establishing the reduction you need.

---
Tags: computability, undecidability, semi-decidability
---


# Question
Title: Sort a list of points to form a non-self-intersecting polygon
Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p\_0 \rightarrow p\_1 \rightarrow \ldots \rightarrow p\_{n-1} \rightarrow p\_n \rightarrow p\_0$ would form a non-self-intersecting polygon?

# Answer
Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.

The first step of the Grahm Scan is to sort the points in a set based on the angle made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the problem for all point sets that I can think of, with a single addition...

If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

Here is an implementation of the algorithm in JavaScript:

```
function sortPoints(points) {
    points = points.splice(0);
    var p0 = {};
    p0.y = Math.min.apply(null, points.map(p=>p.y));
    p0.x = Math.max.apply(null, points.filter(p=>p.y == p0.y).map(p=>p.x));
    points.sort((a,b)=>angleCompare(p0, a, b));
    return points;
};

function angleCompare(p0, a, b) {
    var left = isLeft(p0, a, b);
    if (left == 0) return distCompare(p0, a, b);
    return left;
}

function isLeft(p0, a, b) {
    return (a.x-p0.x)*(b.y-p0.y) - (b.x-p0.x)*(a.y-p0.y);
}

function distCompare(p0, a, b) {
    var distA = (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y);
    var distB = (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
    return distA - distB;
}

```
> 11 votes

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


# Question
Title: Spanning tree with chosen leaves NP-Complete proof
I want to prove that the problem described here

Spanning tree with chosen leaves

is NP-Complete.

Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how would that work?

# Answer
> 3 votes
The question you link to shows that the problem can be solved in polynomial time. If the problem was NP-complete, then this would prove that P = NP. Of course, it's a famous open problem to prove that P = NP or P != NP. Therefore, you shouldn't expect anyone to know of any such proof.

Also, many computer scientists expect P != NP; if they're right, then the problem you list is not NP-complete.

---
Tags: np-complete, spanning-trees
---


title: Regex to NFA to complement

text:
# Question
Title: Regex to NFA to complement
So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear.

Now to go from that NFA to the **complement** of the NFA, since I can't just flip accept and reject states, this means turning the NFA into a DFA.

If $n$ is the number of states in the NFA, the DFA simulating the NFA can have $2^n$ states.

So would the process of **regex to NFA to complement of the NFA** be $O(2^n)$?

Trying to figure out what big-O notation it would be.

# Answer
No. As you said, the NFA can have $m=O(n)$ states, and the DFA can have as many as $2^m$ states, so the DFA can have as many $2^{O(n)}$ states. Consequently, converting a regexp to a NFA and then complementing the NFA can yield an automaton with $2^{O(n)}$ states. $2^{O(n)}$ is larger than $O(2^n)$: notice the difference between $2^{cn}$ vs $c \cdot 2^n$.
> 2 votes

---
Tags: algorithm-analysis, automata, finite-automata, regular-expressions, lower-bounds
---


# Question
Title: Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree
I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest if the approach is correct:

```
public class Solution {
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
    return null;
}if((p.val == root.val) || (q.val == root.val)){
    return root;
}
if(root.left == null && root.right == null){
    return null;
}
boolean leftChildP = isLeftChild(root,p);
boolean leftChildQ = isLeftChild(root,q);

if(isRightChild(root,p) && isLeftChild(root,q)){
    return root;
}if(isRightChild(root,q) && isLeftChild(root,p)){
    return root;
}
if(leftChildP && leftChildQ){
        return lowestCommonAncestor(root.left,p,q);
}
return lowestCommonAncestor(root.right,p,q);}

private boolean isLeftChild(TreeNode root, TreeNode node){
return isChild(root.left,node);
}

private boolean isRightChild(TreeNode root, TreeNode node){
 return isChild(root.right,node);
 }

private boolean isChild(TreeNode parent, TreeNode child){
 if(parent == null){
    return false;}
 if(parent.val == child.val){
    return true;
 }return (isChild(parent.left,child) || isChild(parent.right,child));
 }}

```

The recurrence for isChild() is: T(n) = T(n/2) + T(n/2) +1

But I cannot write the recurrence for lowestCommonAncestor(). Can someone please help?

# Answer
> 2 votes
To analyze the performance of this algorithm. We see what your code does.

You start with the root node. You ask if `p` is the child a your left subtree, and then you asked if `q` is the child of your left subtree. You stored them as a variable.

And then in your next 2 if statements, you make 4 more similar checks.

For each is in subtree query, it is obvious that your worst case performance is the size of the subtree.

Suppose the two nodes are not in the tree, then you will always go right. That seems to be a worst case in your algorithm.

So in the worst case, you have a right going chain, and too bad both input never exists in your tree, you will end up spending `n^2` time and finally return null.

As a side point, you could do much better in terms of time complexity. Here is an example I done.

http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-lowest-common-ancestor-of\_12.html

---
Tags: algorithms, data-structures, recurrence-relation, binary-trees, recursion
---


# Question
Title: Is something more than Turing complete Turing complete?
In complexity theory, we do not call a decision problem that is not in NP "NP-complete".

But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing machines can not?

The definition from Wikipedia didn't address this problem explicitly, and likely assumed yes:

> A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

For example, if there is a system that can:

* Compute every Turing-computable function.
* Compute the halting problem for a Turing machine.

And nothing else. Is it Turing complete?

# Answer
Yes. The "complete" in NP-complete and in Turing-complete are two different notions.

For Turing-complete it means (as per the definition in the question) that the system can compute the complete (in the basic English sense) set of Turing computable functions (i.e. it can do at least everything a Turing Machine can).

For NP-complete, it's not obvious that the word has anything to do with its basic English meaning except perhaps in the tenuous sense that the problem has all the complexity inherent in the class, whatever that means.

Another way to express the difference is that NP-complete can be rephrased as "complete for the class NP", whereas Turing-complete does not mean "complete for the class R" (or RE).
> 9 votes

---
Tags: computability, terminology, turing-completeness
---