# Question
Title: How to tell if a language is recognizable, co-recognizable or decidable?
If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?

Basically any hints or tricks that can be used to tell. Or maybe the common patterns to search for to tell which kind it is?

# Answer
## L is recognizable

A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^\*$, $w \in L \leftrightarrow \exists c \in \Sigma^\*. V\text{ accepts }\langle w, c\rangle$. Commonly, $c$ is thought of as a "certificate" or "proof" that $w$ is in $L$ and the verifier $V$ checks whether $c$ is a valid proof of $w$ being in $L$. (Note that this definition is equivalent to the recognizer definition because we can construct a recognizer for a language from a verifier for that language). Now to determine whether or not a language is in RE we can ask the following question:

> Given a string $w \in L$, could you *prove* that $w \in L$?

For example, consider $HALT = \\{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\\}$. $HALT$ is recognizable because to prove to you that $M$ halts on $w$, I can just tell you the number of steps you should run $M$ for and if $M$ does halt after that many steps, you would be convinced that $\langle M, w\rangle \in HALT $.

## L is co-recognizable

Similarly, a language $L$ is co-recognizable if and only if its complement is recognizable, or in other words if there exists a verifier for $\overline{L}$. Thus to see if a language is in co-RE, we can ask:

> Given a string $w \not\in L$, could you *prove* that $w \not\in L$?

Taking again the example of $HALT$, we can use this intuition to show that $HALT$ is not co-recognizable. This is because if I told you that some machine $M$ does not halt on input $w$, there isn't really anything I can tell you to convince you of that fact. I could run $M$ on $w$ but even if we've been watching $M$ run and haven't seen it halt yet, we don't know that it won't go and halt sometime in the future.

## L is decidable

Finally, a language $L$ is decidable if both $L$ and $\overline{L}$ are recognizable. So if the answer to both of the above two questions is yes, then the language is decidable.

As an example, consider $L = \\{a^nb^n\ |\ n \in \mathbb{N}\\}$. Given a string $w \in L$, could I prove to you that $w \in L$? Sure, I could count up the number of $a$s and the number of $b$s and show that they're equal, so $L$ is recognizable. What about if $w \not\in L$? I could prove that a string is not in $L$ by showing that it's either not of the form $a^nb^n$ or that there's a mismatch in the number of $a$s and $b$s. Thus, $L$ is co-recognizable. Since it's both recognizable and co-recognizable, $L$ is also decidable.

*Reference:* I'm a TA for an introductory computability/complexity theory class at my university and my professor made this really helpful animated guide for reasoning about regular, decidable, and recognizable languages.
> 6 votes

# Answer
# Main ideas

Being recognizable means you can build an automatic process (we'll get back to that later) that takes a word as a parameter such that

* If the automatic process ends, it returns either YES or NO.
* This automatic process doesn't have to terminate on every input, but it has to terminate if the input word is in the language.

Being co-recognizable means the language ${w\in \Sigma^\*, w\not\in L}$ (or, in english, the set of all the words that are not in $L$, i.e. its complementary) is recognizable.

Being decidable means you can build an automatic process that takes a word as an input, such that

* The automatic process always ends
* It answers YES or NO. If it answers YES, the word is in the language, if it answers NO, the word is not in the language.

One important result is that $L$ is decidable if and only if $L$ is recognizable and co-recognizable.

---

The idea to prove this result, is that you can build up an automatic process from the processes that recognizability and co-recognizability give you, by alternating steps from both processes, until one of those gives you the answer YES. One of those have to do so, as every word either is or isn't in the language)

---

# Automatic processes

Without being too formal, many types of machines have been designed, and basically all of them have been linked to types of languages (those types depend on the tools needed to define such languages. For more information, Chomsky Hierarchy may help).

The usual meaning of automatic process, regarding to decidability, is a Turing Machine. You can define a Turing Machine such that it can :

* Receive values from the input
* Store values
* Read the values it stored
* Compute basic mathematical operations on values
* Test basic mathematical properties on those values, and act accordingly, eventually looping.

Basically, a Turing Machine can do everything you can define in a program, except it is a mathematical object, with infinite memory and time to spend on a computation. *It doesn't always terminates.*

Another important property of Turing Machines, is that you can describe a Turing machine as a single word (this is encoding), and there exists a Turing machine that, given as inputs the encoding of a machine $M$, and a word $w$, can simulate the computation of $M$ on the input $w$. This will be important in a bit.

---

Let's just point out that regular languages — which are (almost) the simplest kind of language you can think of from a maths point of view — have the peculiar property that they are closed under complement. This basically means that on those languages, the notions of recognizability and decidability are equivalent. This doesn't hold as you move up in Chomsky Hierarchy.

---

# Example of an undecidable language

We will study the Halting problem. The question is, can we build a Turing Machine that, given the encoding of another Turing Machine $M$ and a word $w$, *decides* wether $M$ terminates on input $w$ ?

Obviously, this is *recognizable*, as we just have to simulate $M$ on $w$ until it terminates, and when it does, say YES. However, if $M$ never does terminate, we won't say NO, so we're recognizing this language, but not deciding it. It has been proven that this language cannot be decided by a Turing Machine. This involves a usual mathematical scheme : a diagonal argument, which I wouldn't call intuitive. You can check this sketch of proof to get used to it.

# To sum up

You won't be able, given a language, to just state if it's decidable or not. There isn't any algorithm that can do that, and proving a language isn't decidable takes some thinking, and can require some knowledge on Turing Machines, Diagonal arguments, etc...

However, here is my personal way of handling this question. Usually, when studying a language, I assume that it is decidable, *unless* it shows some form of reference to the way Turing Machine work. In that case, I start warying, and try to define an algorithm deciding the language. If this doesn't look easy, it sometimes help to split up the work in both a recognizing, and a co-recognizing algorithms. If I still can't do it, I'd try to make a connection between this language, and another undecidable one, such as "If I can decide that language, I can decide the halting problem". This is a Turing reduction to an undecidable problem, so the first problem can't be decidable. If all of those fails, I can try to use diagonal arguments, but this can be a bit tricky.
> 3 votes

# Answer
One trick is that if the language is finite, then you know for sure that it is decidable - as you can "hardcode" a machine to accept anything in that language. However I find the easiest way is to simply reduce from another language
> 1 votes

# Answer
As I mentioned in my comment above, I find it helpful to think about the solution space of the problem.

Think of something like $SAT$. We know that it is decidable, since to test it there is a finite number of solutions we have to try. If there is some finite set of conditions to check, where one of these succeeding guarantees a yes, and none of them succeeding guarantees a no, then the problem is decidable, since we just check the conditions in succession. Note that this set of conditions could be very large (like in the case of NP-complete problems).

Consider now when the solution space is countably infinite, and we can generate each possible solution in sequence, and testing each solution is decidable. In this case we know that the problem is recognizable. For example, a problem asking "is there a natural number such that ..." is recognizable, because we can start at 0, and keep trying every number in sequence. If there is a solution, we are guaranteed to find it, but there is not necessarily a bound on the time it will take to find it. Also, this algorithm would never halt if no such integer existed, so it doesn't prove that a problem is decidable.

You can apply the same technique to the set of all strings, all integers, all graphs, or any finite structure which we can enumerate. This wouldn't work for finding a real number, or a (possibly infinite) set of strings.

Note however, that some problems might have countably infinite solution spaces and still be decidable.
> 1 votes

# Answer
The trick to see if a language is undecidable is to ask yourself the question "can I code a computation of Turing machine using this language" ? Or more generally, "does it get as complicated as what happens in a computation ?". Of course sometimes this coding is hard, and it helps to know a list of undecidable problems to reduce to (like Post correspondance problem). If you don't find such a reduction, try thinking of algorithms to decide your language. For instance the language of lists of integers in increasing orders is not finite, but it is easy to design an algorithm testing whether a list is sorted in increasing order, so this language is decidable. And for a lot of languages, we don't know about their decidability, so this is a hard question.
> 0 votes

---
Tags: computability, undecidability, intuition
---


title: Running time with while loop

text:
# Question
Title: Running time with while loop
What's the running time of:

```
foo(n)
if(n==1) return;
int i=1;
while(i<n)
{
    i=i+2
}
foo(n-2)

```

There are $n/2$ recursive calls to `foo` but how to add to the calculation the while loop

# Answer
> 0 votes
You can write the relation likes the following: $$T(n) = T(n-2) + \frac{n}{2}$$ $$T(n) = \frac{n}{2} + \frac{n-2}{2} + \frac{n-4}{2}+\cdots +\frac{n-(n-2)}{2} = $$ $$\frac{n^2-2(1+2+3+\cdots+(\frac{n}{2}-1))}{2}=$$ $$\frac{n^2-(\frac{n}{2}-1)\times \frac{n}{2}}{2}= \Theta(n^2)$$

# Answer
> 1 votes
The number of the iterations of the while loop is

$$n/2+(n-2)/2 + (n-4)/2 + \dots +1$$

which is $O(n^2)$.

---
Tags: runtime-analysis
---


# Question
Title: MULT in a RISC - should instructions take the same amount of time in a RISC system
I am studying computing as part of my A level course, and my understanding is that all instructions in a RISC architecture should execute in roughtly the same, small number of clock cycles (ideally one).

This leads me to ask how multiplying two (possible very large) numbers takes (roughly) the same time as all the other commands, such as LOAD, STORE, ADD, etc. I believe the most common way a computer multiplies numbers is using a Binary Multiplier, which requires multiple addition executions, meaning that a multiplication, or PROD command (from an example from Stanford University) will execute with many cycles per second and not be consistent with the speed/cycles of other commands from a reduced instruction set.

# Answer
RISC processors are pipelined, and have been since the beginning. That is, at a single time there are several instructions which are in different phase of execution. That mean that there is two different numbers that you can give for the execution time. One, the latency, which measures the time between the start of an instruction and its end. The other, the throughput, which measures how many instructions can be executed in a given time.

When someone says that RISC have single clock instructions, they are thinking about throughput, that is that RISC processors are able to execute one instruction per clock, and not latency, that is that it take one clock to execute any given instruction.

Early RISCs did not have multiplication instructions. That was more a consequence of manufacturing process limitation of the time, which would not have allowed to put a multiplier on the chip along with the rest of the processor, than a fundamental characteristic of RISC. With increased integration density, RISC acquired such instructions.

Note that it is possible to achieve bigger throughput than one instruction per cycle. For that, you need to be able to decode several instructions per cycle, and have several execution unit. That is something called super-scalar and high-end processors are super-scalar since the early 90's.

Note also that the possibility to achieve the theoretical throughput in practice depend on the program (you need to have instructions which are independent to be able to execute them in parallel, you need to have the data available, and thus have pattern of memory accesses and a memory sub-system which together allow to provide the data rapidly enough).
> 1 votes

# Answer
Early RISC CPUs had no "real" multiply instructions because multiplication is a complex operation, usually multicycle or deeply pipelined, needing lots of gates, which breaks the simplicity of the pipeline where calculations are only performed in the EXECUTE stage, and are of moderate complexity (add/sub, logical operation...).

As a band-aid, some RISCs had primitive partial-multiply instructions which needed to be executed many times for a complete multiplication. A good example is the SPARC v7 MULScc "multiply step" instruction.

Nowadays, with transistors aplenty, most CPUs can afford a fast multiplier.
Division was also unavailable in early RISC CPUs. Integer division is less important than multiplication, though, and there is no reasonable method for making dividers as fast as multipliers.

Having a genuine multiply instruction is better than nothing, even if it is slow in first versions/low end variants, because it can be more easily enhanced than series of additions and shift instructions, or relying on dynamic patching of code depending on CPU versions (replacing the multiply subroutine call by a call to a single a multiply instruction, which was done sometimes).
> 0 votes

# Answer
Integer multiplication is actually something that can be done very fast (not much slower than an addition). If you throw enough hardware at it, which is usually done, you can perform a multiplication in about twice the time of an addition. And while an addition is usually done in one cycle, there is usually plenty of time to spare, and an integer multiplication does indeed fit into one cycle. You'll need a couple of thousand full adders for a 64x64 bit multiplication, but there are far more than one billion transistors in a modern smartphone, so that's no big deal.

See for example https://en.wikipedia.org/wiki/Wallace\_tree . And that was apparently invented in 1964 - just at that time it was very, very expensive. Today it's cheap.

Memory on the other hand is slooooooooow. 50 cycles is not unusual for random access. Sequential access is substantially faster, and caches are used to reduce the number of memory accesses.

Overall: It's not multiplications that are slow (today), it's memory access. Division and square root are also multiple cycles and usually implemented in hardware.
> 0 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Does big-Oh notation in optimization follow the same convention as in CS?
I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class.

Now I am doing a project on optimization. In our optimization class, we were introduced to the notion of rate of convergence which are characterized by the ratio:

$\lim\limits\_{k \to \infty} \dfrac{|x\_{k+1} - L|}{|x\_k-L|}$

where $L$ is the limit of the sequence $(x\_k)$. And from there we define linear, superlinear and sublinear convergence raes.

However, when I looked up on some reference online, the above notions of rate of convergence is almost never used. Instead, all the convergence rates are characterized in terms of big-Oh. Quoting from the slides:

> ***Theorem***: Gradient decent with fixed step size $t\le\frac{1}{L}$ satisfies $f(x^{(k)})-f(x^\*)\le\frac{\\|x^{(0)}-x^\*\\|^2}{2tk}$.
>
> I.e. gradient decent has convergence rate $O\left(\frac{1}{k}\right)$.
>
> I.e. to get $f(x^{(k)})-f(x^\*)\le\epsilon$, we need $O\left(\frac{1}{k}\right)$ iterations.

Unfortunately, these authors never define what their notations mean. I am in need of citing the definitions of big-Oh for my class project.

Is there any disparity between the rate of convergence in terms of big-Oh (and other asymptotic) used in optimization versus that used in CS (as can be found in a standard textbook such as CLRS)?

Is there an optimization textbook that addresses big-Oh notation?

# Answer
> 5 votes
They are using the standard Landau notation.

In the theorem you stated, it is said that after $k$ steps your distance from the optimal value is smaller than $\frac{c}{k}$, where $c$ is a constant which depends on your initial distance from the point where optimum is achieved, and on the step size. In that case you can indeed say that the convergence rate is $O\left(\frac{1}{k}\right)$, which is interpreted as you quoted in the following line, to get $\epsilon$-close to the optimal value one needs $O\left(\frac{1}{\epsilon}\right)$ iterations.

Note that I wouldn't take this answer as "anywhere in optimization this notation means the Landau notation", and you are probably right to say that it needs to be mentioned. However, in this context, you can pretty safely assume that this was the authors intention.

---
Tags: optimization, asymptotics, reference-request, notation
---


# Question
Title: Graph where only two vertices have the same degree
Let's say that $N$ is the number of vertices. We want to create a graph where only two vertices have the same degree. For what kind of $N$ is this possible?

I tried it and I've been able only to come up with such where $N$ is $3$ and $4$.

# Answer
> 5 votes
It is possible for every $N\ge 2$. We can prove it by mathematical induction.

For $N=2$, it is trivial.

Suppose there is such a graph for $N=n$, there are following two cases:

1. No vertex has degree $0$.
2. There is a vertex with degree $0$.

In case 1, we just add an isolated vertex. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

In case 2, no vertex has degree $n-1$. We add a vertex with edges to every vertex in previous graph. The new node has degree $n$. The degree of each vertex in previous graph is added by $1$, thus no one in the new graph has degree $n$. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

So such graph is possible for $N=n+1$.

As a conclusion, it is possible for every $N\ge 2$.

---

If you only care about connected graph (i.e. no vertex has degree $0$), the result is the same while the proof should be revised somewhat: the new graph for $N=n+1$ is constructed via first constructing an intermediate graph for $N=n$ from the graph for $N=n-1$ (this intermediate graph has a vertex with degree $0$), then constructing the graph for $N=n+1$.

---
Tags: graphs
---


# Question
Title: What are "state registers" and "code registers"?
While reading a chapter about `FSM`, I was stuck on the following slide:

In fact, I have been unable to determine what are "state registers" and "code registers", which were not explained in the course. Therefore, I have used to search for the definitions on the net, but I haven't yet found any result.

# Answer
While I've not heard those exact terms, my guess would be that "code registers" are the registers that code you would write set. For example, on an Intel x86 platform, that would be the general purpose registers like the AX, BX, CX, etc. and EAX, EBX, ECX, etc. registers. These are registers that you can either use directly if you're writing assembly code, or that are used by the code generated by your compiler.

Meanwhile, the computer also has a set of registers for its own use. Things like the program counter (or instruction pointer) register which points to the next instruction to execute in memory. They can also indicate statuses; things like carry registers that indicate whether there was a carry out of an addition between 2 other registers. (For example if you add 1 to MAX\_INT, you'll generate a 1-bit carry that the registers can't hold.)

Each processor is different. The 6502 had 2 registers (labeled X and Y) and an accumulator as general purpose (or code) registers. Then it has one status register that held 7 bits of status flags, a stack pointer, and a program counter, which would be "state registers".
> 5 votes

---
Tags: computer-architecture
---


title: Is this language in P?

text:
# Question
Title: Is this language in P?
L={ | M is a DFA, |w| is even for all w in L(M)}

Meaning we are looking for a Turing Machine or any algorithm that receives a description of a DFA and decides if all the words this DFA accepts are even in there length(length of 0, 2, 4, 6 ..). DFA stands for Deterministic Finite Automata. My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.For example 0011 has even length, 0 takes you to state2 0 state3 1 state4 1 state5. because when you start you are already at state 1(Qstart).

My question: is my solution solid, is it right? Does it run in Polynomial time? I think running time is: o(n^2)

# Answer
> 3 votes
Using the product construction, given $M$ you can construct (in linear time) a DFA for the language $L'(M) := L(M) \cap \Sigma(\Sigma\Sigma)^\*$. Using DFS/BFS, you can check whether $L'(M)$ is empty or not (you check whether some accepting state is reachable from the initial state) – $L'(M)$ is empty iff $M \in L$. The entire algorithm runs in linear time.

# Answer
> 2 votes
Your solution is insufficient as written:

> My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.

If there is an accept state at a position you expect a certain distance from the start state, what happens when that accept state has a 3-cycle that leaves it and comes back to it? In your example, it accepts a string of length 4. But then it would also accept a string of length 7.

You might be able to extend your solution to include these cases, similar to an algorithm for 2-colouring a graph.

# Answer
> 0 votes
Given M, construct in o(1) time a DFA M' that accepts all odd length words in M's language, basically a DFA with two states. Construct a product DFA M'' from M and M'. Check if L(M'') is empty, if so accept otherwise reject.

Both construction of M'' and checking if it's language is empty take polynomial time.

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


# Question
Title: monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies
I'm working on exercise 16.3-5 of CLRS:

> Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.

Perhaps I'm misunderstanding the question, but how can the lengths be monotonically increasing? In order for the code to be optimal, the binary tree representation must be *full* (like the StackExchange CS logo), e.g. every node with degree either 0 or 2 (if it's not full, then it cannot be optimal, since the code could be shortened by promoting the child of a node with degree 1, as discussed in exercise 16.3-2). That means there exists at least one pair of leaf nodes at the same depth, and depth is the same thing as the codeword length.

The Huffman code is optimal, and it always begins by merging two characters, so again there's at least a single pair of leaf nodes that will be at the same depth and hence same codeword length in the resulting tree.

Is it a typo, e.g. should it read "monotonically increasing *except* for the final two characters, which have the same length" or maybe even "monotonically non-decreasing"?

In fact, there is a trivial counterexample: suppose there are only two characters 'a' and 'b', with frequencies 0.6 and 0.4 respectively. The optimal code is clearly 'a'=0 and 'b'=1, or vice versa. However, the codelength is 1 for both characters, so clearly is not monotonically increasing.

# Answer
I misunderstood the phrase "monotonically increasing". It actually means the same thing as "non-decreasing", as explained on p 53 of the book. The phrase is different from "strictly increasing", also defined there, which is what I had thought it meant.

With "monotonically increasing" meaning "non-decreasing", the exercise makes a lot more sense.
> 2 votes

---
Tags: algorithms, algorithm-analysis, data-compression, huffman-coding
---


# Question
Title: Application of difference array for overlapping glass-tint problem
For this problem, I heard that using a *difference array* can solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad.

> Given an array of numbers, we can construct a new array by replacing each element by the difference between itself and the previous element, except for the first element, which we simply ignore. This is called the difference array, because it contains the first differences of the original array. We will denote the difference array of array A by D(A). For example, the difference array of A = \[9, 2, 6, 3, 1, 5, 0, 7\] is D(A) = \[2-9, 6-2, 3-6, 1-3, 5-1, 0-5, 7-0\], or \[-7, 4, -3, -2, 4, -5, 7\]. Source

I've found a solution in Python , but I can't understand it.

Canadian Computing Competition: 2014 Stage 1, Senior #4:

> You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.
>
> You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass).
>
> You would like to know the total area of the finished stained glass window with a tint-factor of at least T.

Input Specification:

> The first line of input is the integer $N$ ($1\leq N\leq 10^3$), the number of pieces of glass. The second line of input is the integer $T$ ($1\leq T\leq 10^9$), the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$-th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x\_1$ $y\_1$ $x\_2$ $y\_2$ $t$, where the top-left corner is at $(x\_1,y\_1)$ and the bottom-right corner is at $(x\_2,y\_2)$, and tint-factor is $t$. You can assume that $1\leq t\leq 10^6$. The top-most, left-most coordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x\_1\<x\_2\leq K$ and $0\<y\_1\<y\_2\leq K$, and ...

Output Specification: Output the total area of the finished stained glass window which has a tint-factor of at least $T$.

I have an implementation but I'm not quite sure how it works. Any explanation would be greatly appreciated.

# Answer
> 0 votes
First, I will look at this problem from a more (high-level) theoretical perspective and then go through the details required in an implementation, based on the solution you linked to.

---

Given all the rectangles, we can divide the area in *rectangular portions* such that every portion is rectangular and all points in the same portion intersect the same set of rectangles. An division of the example input in rectangular portions can be seen below:

Our task is to identify the rectangular portions of glass that have at least the required tint $T$. To do this, it is necessary that we iterate in some manner over all these rectangular portions to determine their tint. It is also sufficient: the portions are determined by considering all rectangles they intersect, at which point we can inspect their tint. So, we can create an algorithm that solves this problem in $O(R)$, where $R$ is the number rectangular portions and this is (asymptotically) the best we can do.

But how big can $R$ become? If we have some collection of rectangular portions of the intersection of $i$ rectangles and add a new rectangle, we create one new portions for each portion that is intersected by one of the four edges of the new rectangle. So how many portions can intersect the same horizontal line? At most $2i-1$, since the same horizontal line can be intersected by at most $2$ vertical lines for every rectangle added (apart from the first). So, after adding all rectangles, we get $R\leq \sum\_{i=1}^N 4\cdot (2i-1) = O(N^2)$.

So, our algorithm will run in $O(N^2)$. Given that $N\leq 10^3$, it should be fast enough if we implement it efficiently.

---

But implementing this efficiently could be rather tricky. Sure, it's easy to say that you can just add rectangles and create new portions as a result of their intersection, but that would be pretty cumbersome to implement and possibly inefficient.

This is where the 'difference array' approach comes in. The principle is slightly easier to explain with a 1D-array, so we will restrict the problem to that for now. Suppose we have input

```
x1 x2 t
11 20 1
13 14 2
17 18 1
12 19 1

```

So, we can draw it like this:

The array $A$ contains the tint values over all contiguous 'rectangles' in 1d, which is what we need. The array $dA$ is the difference array of $A$. Observe that this difference array can be easily found: after sorting the endpoints of our 'rectangles', we add the tint-value of the rectangle on the left side (when 'entering' the rectangle) and subtract it on the right side (when we 'leave' the rectangle). After we found are difference array $dA$, we can compute $A$ by noting that $A\[i\] = \sum\_{j=1}^n dA\[j\]$. Then, we scan $A$ to find the areas that have tint $\geq T$ and add the area to our final value and we're done.

For 2D arrays, we do exactly the same thing, but now with an extra dimension to keep track of.

---

Let me make a final remark: it is in general very hard to 1. reconstruct an algorithm from an implementation and 2. understand an implementation of an algorithm without understanding the algorithm. Therefore, just inspecting source code to understand an algorithm is generally a hopeless task. In this case, I could only understand the implementation in this source after I understood the explanation.

---
Tags: algorithms, data-structures, computational-geometry, arrays
---


# Question
Title: How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?
We have the following Lemma and proof:

> **Lemma 5.5.** If $A$ if FPT, then $A\leq\_{\mathrm{fpt}}$ Independent Set.
>
> *Proof.* We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a sought independent set. Given an instance $(x,k)$ of $A$,
>
> * solve $(x,k)$ in $f(k)\cdot \mathrm{poly}(|x|)$ time, (*the running time of this reduction is using the running time of problem $A$*)
> * if $(x,k)$ is a yes-instance, then output a one-vertex graph and $k'=1$.
> * if $(x,k)$ is a no-instance, then output a one-vertex graph and $k'=2$. (*Could this need more time to compute?*)
>
> It is clear that the input instance is a yes-instance if and only if the output IS instance is, and $k'\leq k+2$. $\quad\square$

The definition of parameterized reduction is as follows:

> **Definition 13.1 (Parameterized reduction).** Let $A,B\subseteq \Sigma^\*\times\mathbb{N}$ be two parameterized problems. A *parameterized reduction* from $A$ to $B$ is an algorithm that, given an instance $(x,k)$ of $A$, outputs an instance $(x',k')$ of $B$ such that
>
> 1. $(x,k)$ is a yes-instance of $A$ if and only if $(x',k')$ is a yes-instance of $B$,
> 2. $k'\leq g(k)$ for some computable function $g$, and
> 3. the running time is $f(k)\cdot |x|^{\mathcal{O}(1)}$ for some computable function $f$.

Now it seems from what he did is: if $(x,k)$ is yes-instance, then output a one vertex with $k'=1$, otherwise if $(x,k)$ is no-instance, then output a one vertex with $k'=2$. This makes the first condition of Parameterized reduction true. Now,for second condition, we should say $k' \leq g(k)$ where $g(k)=1$ if we have yes-instance, and $0$ otherwise. The running time would be just the running time of the parameterized algorithm. Done.

My question is that when I want to do a reduction, I should take the input of $A$ (like vertex cover) and turn it to input of IS instance. For example assume we have clique of $4$, with $k=3$, the vertex cover algorithm will return a yes-instance, now if we want to turn this instance to IS to make it yes-instance, we need to use $n-k$. But he use different way. Also, when we prove IS to VC using parameterized reduction, it gives us wrong reduction (because of $n-k$ isn't a computable function of $k$). I just want to know here how "VC to IS" using parameterized reduction works.

# Answer
It seems your confusion comes from the fact that Lemma 5.5 is a bit of a strange statement. In fact, we can replace Lemma 5.5 with the statement that for *any* problem $B$ such that $B\_Y$ is a yes-instance of $B$ and $B\_N$ is a no-instance of $B$ we have that $A\leq\_{\mathrm{fpt}}B$. The proof of this adapted lemma is precisely the same as Lemma 5.5, only now we use $B\_Y$ in the second bullet-point and $B\_N$ is the third.

The crucial reason why this works is that we already know that $A$ is fixed parameter tractable. In a sense, this lemma shows that we learn nothing from a fpt-reduction *from* a problem we already know is fpt.

So, this lemma is in fact useless when trying to create a reduction from a problem we don't know is fpt, such as $k$-Clique.

When you try to apply Lemma 5.5 when $A$ is not fpt (or at least not known to be), you fail to satisfy part 3 of the definition of an fpt-reduction.
> 2 votes

---
Tags: complexity-theory, reductions, parameterized-complexity
---


# Question
Title: Number of conflict serializable schedules
> Two transactions $T\_1$ and $T\_2$ are given as:
>
> $$T\_1: r\_1(X)w\_1(X)r\_1(Y)w\_1(Y)$$
>
> $$T\_2: r\_2(Y)w\_2(Y)r\_2(Z)w\_2(Z)$$
>
> where $r\_i(V)$ denotes a read operation by transaction $T\_i$ on a variable $V$ and $w\_i(V)$ denotes a write operation by transaction $T\_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T\_1$ and $T\_2$ is \_______________

I have tried finding the total number of schedules – nonconflict serializable schedules, but I think there is a higher possibility in committing mistakes in the exam for that method. Please suggest a better way to solve this.

# Answer
While checking for conflict serializable schedules, we should be sure to avoid RW, WW, WR conflicts. Also the relative order of operations internal to each transaction also needs to be maintained. For example T1's operations on $X$should come before T1's operations on $Y$. Also since $Y$ is the common datum here, therefore either all of T1's operation on $Y$ occur before T2's $Y$ operations or they may occur later, but they shouldn't be interleaved.

So let's try to see the number of such serializable schedules: Here is $T\_1$:

> (a) $r\_1(X)$ (b) $w\_1(X)$ (c) $r\_1(Y)$ (d) $w\_1(Y)$ (e)

Since $Y$ is the common datum so I pick it first from $T\_2$. put $w\_2(Y)$ at position (a)

> (a1) $w\_2(Y)$ (a2) $r\_1(X)$ (b) $w\_1(X)$ (c) $r\_1(Y)$ (d) $w\_1(Y)$ (e)

We now have two new positions (a1) and (a2). Now, see that $r\_2(Y)$ can come only at (a1) since it cannot come after $w\_2(Y)$. Now The $Z$ operations of $T\_2$ remain. See that they can come at any of the 5 postions starting from (a2) till (e). So for this case, we get total schedules as

$1 \*( \binom{5}{1} + \binom{5}{2}) = 15$

$\binom{5}{1}$ is the case when both $r\_2(Z)$ and $w\_2(Z)$ come together. $\binom{5}{2}$ is the case when they are separated. Note that $r\_2(Z)$ and $w\_2(Z)$ have not been permuted to maintain their relative order. Similarly, you can move $w\_2(Y)$ through positions (b) (c) and (e) (*note that (d) is an excluded possibility since interleaving is not allowed*) to get $20, 18, 1$ as the answer respectively for each individual case. They sum up to $54$.

In case you need the explanation for all cases, you can look up here.
> 1 votes

---
Tags: concurrency, database-theory
---


title: Recurtion equation

text:
# Question
Title: Recurtion equation
Does anyone know how to solve the below? I'm guessing that I need to use the Subtraction method or iteration but still I'm having a hard time with it.

$$T(n)=3T(n-1)+3^n\times n^2$$

# Answer
> 0 votes
Exapnd the equation:

$$T(n) = 3(3T(n-2) + 3^{n-1}\times(n-1)^2) + 3^n\times n^2=$$ $$3^2T(n-2) + 3^n(n^2 + (n-1)^2)= \cdots = $$ $$3^n\sum\_{i=1}^{n}i^2 = 3^n \times \frac{n(n+1)(2n+1)}{6} = \Theta(3^n\times n^3) $$

---
Tags: algorithms, complexity-theory
---


# Question
Title: Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?

# Answer
I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.
> 2 votes

# Answer
Here is the solutions from my university exercise sheet. But frankly speaking I still don't get it...
> 1 votes

---
Tags: graphs, combinatorics, network-flow
---


# Question
Title: Solving diophantine equations -- does having a bound on the size of the solution help?
Let's define the following languages over the alphabet $\Sigma=\\{0,1\\}$:

**H10** is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, i.e. there exists a root/solution in $\Bbb{Z}^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

**RH10** is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, each integer in the closed interval $\[-2^n,2^n\]$ or in other words there exists a root/solution in $\[-2^n,2^n\]^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

If **RH10** can be solved in deterministic polynomial time, does this imply that **H10** is decidable? If there is a polynomial-time algorithm for **RH10**, then it can't be enumerating all possible solutions in $\[-2^n,2^n\]^n$ (there are too many of them to try in polynomial time), so it seems like it must somehow find solutions regardless of how large they are, and thus also be able to solve **H10** too. Is that right? Does it follow from this that $P$ is unequal to $NP$, as **H10** is known to be, in fact, undecidable?

# Answer
No.

If I follow you correctly, your argument is that if P=NP, then $\mathrm{RH}10\in \mathrm{P}$ *and* the same procedure would be a valid algorithm for $\mathrm{H}10$, which contradicts with the fact that $\mathrm{H}10$ is undecidable.

The step that lacks proof is the claim that the implication:

> if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

To see that this claim doesn't follow, consider what a polynomial algorithm to solve $\mathrm{RH}10$ could be doing. We only know it lies in P somehow, so let's assume it runs in $O(n^k)$ time for some $k\in\mathbb{N}$. Let $l$ be such that we can verify whether a value is a solution for a Diophantine equation with $n$ variables in $O(n^l)$ time.

It is *possible* that this is done by the following algorithm $A$, given an instance $I$ of $\mathrm{RH}10$:

1. Identify a set $S\subseteq \[-2^n,2^n\]^n$ of size $O(n^{k-l})$ in $O(n^k)$ time such that $s$ is a solution to the Diophantine equation encoded in $I$ if and only if $s\in S$.
2. Iterate over all elements in $s\in S$ and test whether it is a solution of $I$. If a solution is found, report that $I$ has a solution, otherwise report it has not.

Observe that this is a valid algorithm to solve $\mathrm{RH}10$ in $O(n^k)$ if and only if there exist a procedure to carry out step 1. We don't know whether this is true, it is unlikely, but we don't know so it is at least *possible*.

Now, does the existence of algorithm $A$ give us a procedure to decide $\mathrm{H}10$? No. Algorithm $A$ requires that the solution values are restricted to some finite subset of $\mathbb{Z}^n$ to work. This is true even if we only use step 1. I hope it is clear that the existence of algorithm $A$ brings us no closer to deciding $\mathrm{H}10$.

Therefore, it is clear that the claim that

> if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

is not motivated, as the *possibility* of the existence of algorithm $A$ is not dis-proven, while we have seen that the existence of algorithm $A$ contradicts your claim.
> 6 votes

---
Tags: complexity-theory, computability, decision-problem, polynomial-time, p-vs-np
---


title: Minimum area of tarp to cover a carpet

text:
# Question
Title: Minimum area of tarp to cover a carpet
This problem takes place on a coordinate plane. I need assistance in creating the algorithm to solve this problem. I am solving this problem in java if you are interested.
I have 1 carpet and 2 tarps.
The 1 tarp covers the carpet (note in some scenarios it may not cover it at all).
The second tarp will cover the remaining area of the carpet, however, this is where it gets tricky. The tarp cannot be a special shape or tilted, meaning the tarp HAS to be rectangular. I am given the inputs of the lower left and top right corners of both the 1st tarp and the carpet. As of now, I have calculated the visible area of the carpet after the first tarp has been placed, the overlapping (non-visible) area of the tarp, and the areas of both the carpet and 1st tarp.
**So basically what I am saying is, given a rectangle *C* (the carpet) that intersects the rectangle T1 (tarp 1), find another rectangle T2T2 (tarp 2) such that the area of T2T2 is minimal.** Below is a picture of some test cases I drew up:

\*Excuse my messy handwriting

Cutting to the chase, what I need is help with is developing an algorithm that would satisfy all of the above test cases, given the lower left and top right coordinates of both the first tarp and carpet. Note I am going to be writing this in Java and I currently have an area function and visible area of the carpet function.

*Sorry if I was a little unclear on what I am asking, leave a comment and I'll be happy to clarify. Note: this is not a homework problem, as many of you may think. This is merely an interesting scenario of another programming problem I had.*

# Answer
To solve this, consider what happens when exactly $k$ corners of $C$ lie inside $T\_1$, for $k\in \\{0,1,2,3,4\\}$, where $C\setminus T\_1$ denotes the area of $C$ not covered by $T\_1$:

* If $0$ corners of $C$ lie in $T\_1$, then $T\_1$ doesn't cover any corner of $C$. So any rectangle covering $C\setminus T\_1$ must cover all corners of $C$, so the smallest of these rectangles is $C$ itself.
* If exactly $1$ corner of $C$ lies in $T\_1$, the $C\setminus T\_1$ contains $3$ corners of $C$ and the smallest rectangle covering this area is again $C$ itself.
* If exactly $2$ corners of $C$ lie in $T\_1$, then $C\setminus T\_1$ is a rectangle, so the smallest rectangle covering it is itself. More precisely, this is the rectangle with as corners the two intersection points of the edges of $C$ and $T\_1$ and the two corners of $C$ not covered by $T\_1$.
* If $3$ corners of $C$ lie in $T\_1$, then $4$ corners of $C$ lie in $T\_1$, so $k$ cannot be $3$.
* If $4$ corners of $C$ lie inside $T\_1$, then $C$ is fully covered by $T\_1$, so the smallest rectangle covering the remainder has area $0$.

So, to determine the size of the smallest rectangle covering $C\setminus T\_1$, we simply count the number of corners of $C$ inside $T\_1$, apply the proper case and we're done.
> 0 votes

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


# Question
Title: What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?
Arora-Barak says

> It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity, say $n^{20}$, but soon somebody simplified it to say an $n^5$ time algorithm

What are some examples of the above statement? I know AKS is one, are there any other?

# Answer
## Approximating volume of convex bodies

In Dyer et al.: **A random polynomial-time algorithm for approximating the volume of convex bodies**. Journal of the ACM (JACM) 38.1 (1991): 1-17. a $O(n^{19})$ approximation algorithm was proposed.

The work of Lovász et al.: **Simulated annealing in convex bodies and an $O^\*(n^4)$ volume algorithm**. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^\*(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).

---

Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/
> 5 votes

# Answer
Khachiyan's ellipsoid method (1979) for linear programming famously proved the polynomial-time solvability of linear programs, even so the older simplex algorithm is much faster than the ellipsoid method in practice. But it inspired new lines of research in linear programming, and Karmarkar's algorithm (1984) was able to reduce the exponent and compete again the simplex algorithm in practice:

> Denoting $n$ as the number of variables and $L$ as the number of bits of input to the algorithm, Karmarkar's algorithm requires $O(n^{3.5} L)$ operations on $O(L)$ digit numbers, as compared to $O(n^6 L)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus $$O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)$$ using FFT-based multiplication.

However, even so I vaguely remember the same $O(n^6)$ bound for the ellipsoid method from a lecture, I doubt that it is a sharp bound. Wikipedia says in a different article that

> this algorithm uses $O(n^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

---

The Ford–Fulkerson method (1956) for computing the the maximum flow in a flow network is not fully specified, but a reasonable implementation (1972) achieved a running time of $O(V E^2)$. Dinic's algorithm (1970) includes additional techniques that reduce the running time to $O(V^2 E)$. The Goldberg-Tarjan push-relabel methods (1988) use completely different paradigms and achieve significantly smaller (theoretical and practical) runtimes:

> The variant based on the highest label node selection rule has $O(V^2\sqrt{E})$ time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic1 $O(VE\log(V^2/E))$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

To summarize, an initial $O(n^5)$ got reduced to $O(n^4)$ by including additional techniques in less than 15 years, and more than 15 additional years later, different paradigms achieved $O(n^3)$.

---

1. Whether $O(VE\log(V^2/E))$ is subcubic is debatable. $E=o(V^2)$ is quite common in practice, but $O(V^2\sqrt{E})$ will also be subcubic in that case, and the corresponding algorithm apparently works better in practice. But one would have to fix Wikipedia first (same for the $O(n^4L)$ vs $O(n^6L)$ runtime for ellipsoid method issue).
> 4 votes

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


# Question
Title: How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent
Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:

To a regular expression equivalent. What I have tried was using arden's rule. However I just cant figure out how to simplify and return the appropriate regular expression corresponding to that NFA.

First I have created the initial equation corresponding to those states:

$1: q3 = q\_1 0 + q\_1 1$

$2: q1 = q\_0 0 + q\_1 1$

$3: q0 = q\_0 0 + q\_0 1 + \epsilon$

Which I have tried to simplify:

$1: q3 = (q\_0 0 + q\_1 1)0 + (q\_0 0 + q\_1)1$

$1: q3 = q\_0 00 + q\_1 100 + q\_0 01 + q\_1 11$

$1: q3 = q\_0(0+1) + q\_1(0+1)$

$2: q1 = q\_0 00 + q\_0 10 + \epsilon 0 + q\_0 01 + q\_1 11$

$2: q1 = q\_0(0+0+1)+ \epsilon 0 + q\_1 11$

$3: q0 = q\_0 0 + q\_0 1 + \epsilon$

$3: q0 = q\_0(0+1) + \epsilon$

Here I just lost. Maybe there is a different approach suitable in this context.

Appreciate any help!

# Answer
> 1 votes
The Arden's rule, as it is usually stated, is easier to use if you consider equations on $(L\_q)\_{q\in Q}$ depicting the language $L\_q$ the automaton accepts *from* state $q$. Doing this, you obtain the following equations. Check that you understand this properly :

* $L\_0 = 0L\_0 + 1L\_0 + 0L\_1$
* $L\_1 = 0L\_3 + 1L\_3$
* $L\_3 = \varepsilon$

(I use $L$ instead of $q$ as it looks less misleading to me)

Once you have those equations, you can solve this as follows

* $L\_1 = 0 + 1$ (I replaced $L\_3$ with its value)
* $L\_0 = (0+1)L\_0 + 0(0+1)$ (Replaced $L\_1$ and factorized. This is ready for Arden's rule)
* Since $\epsilon\not\in L\_0$, from Arden's rule : $L\_0 = (0+1)^\*0(0+1)$

The language accepted by the automaton is always the union of the $L\_{q\_i}$, where the $q\_i$ are the initial states. So here, $L = L\_0 = (0+1)^\*0(0+1)$

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


# Question
Title: Regular expression for strings that begin with 0 and contain an equal number of 01 and 10 substrings
I'm trying to write a regular expression for the language $L\subseteq\\{0,1\\}^\*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. Substrings can overlap, so $010$ is in the language but, e.g., $01101$ is not.

I've worked on a DFA where I can move on to create the RE. Here is my DFA:

I'm trying to use Arden's theorem to get the regular expression but I'm stuck. This is how I'm thinking:

\begin{align\*} a\_1 &= 0a\_2 + e\\ a\_2 &= 0a\_3 + 1a\_5\\ a\_3 &= 0a\_3 + 1a\_4\\ a\_4 &= 0a\_3 + 1a\_4\\ a\_5 &= 0a\_6 + 1a\_5\\ a\_6 &= 0a\_6 + 1a\_5\\,. \end{align\*} I dont describe $a\_7$, the "sink state" because it only results in the empty set.

My problem here is that I will never be able to get describe the language because of how $a\_3$, $a\_4$ ,$a\_5$, $a\_6$ are? Where did I go wrong?

After some work, I came to this solution, is it correct?

$$0 + 00(11^\*0 + 0)^\* + 01(1 + 00^\*1)^\*00^\*$$

# Answer
Part of your confusion stems from the fact that there are two different formulations of Arden's Lemma, which I'll call LR and RL. To illustrate them, let's take a simple FA with three states, $P,Q,R$, where $P$ is the start state and $R$ is the only final state. The transitions are $$\begin{array}{c|cc} & 0 & 1\\ \hline P & Q & \varnothing\\ Q & R & Q\\ R & R & R \end{array}$$ It's clear with a moment's thought that the language accepted by this FA is denoted by the regular expression $01^\*0(0+1)^\*$, so let's see what the two versions of Arden's Lemma produce.

**LR**: In this version we generate the regular expression from left to right. If we have a state $X$ with a transition on $a$ to state $Y$ we will include the equation $X=aY$, along with any other terms that arise from transitions from $X$ to other states. Along with this, we add a "$+\epsilon$" to the expression for $X$ if $X$ happens to be a final state. Having made the collection of equations, we may apply the simplification rule that says that whenever we have $X=rX + s$ for regular expressions $r, s$ we can replace the equation by its solution $X=r^\*s$. Note that here the goal is to product a regular expression for the start state.

In the example above, we'll have the equations $$\begin{align} P&=0Q\\ Q&=0R+1Q\\ R&=(0+1)R+\epsilon & \text{since R is final} \end{align}$$ Substituting, we see that $R=(0+1)^\*\epsilon = (0+1)\*$ and $Q=1^\*(0R)=1^\*0(0+1)^\*$, and finally $P=0Q=01^\*0(0+1)^\*$, as we expected.

**RL**: In this version we construct the regular expression from right to left. The difference is that if we have a state $X$ with transition on $a$ to state $Y$ we include the equation $Y=Xa$, along with any similar terms. In this case, we add the "$+\epsilon$" only to the *start* state's equation and the substitution in this case says that if we have $X=Xr+s$ we have the solution $X=sr^\*$.

Returning to our example, we'll have $$\begin{align} P&=\epsilon & \text{since $P$ is the start state and has no incoming transitions}\\ Q&=P0+Q1\\ R&=Q0+R(0+1) \end{align}$$ Now our goal is just opposite of what we had in the LR version: we want an expression for the *final* state, $R$. Working from the top down we have $Q=Q1+P0=Q1+0$ so $Q=01^\*$ and $R=Q0(0+1)^\*=01^\*0(0+1)^\*$: the same result generated in a different order.

Assuming you want to use the LR version, your equations should be $$\begin{align} a\_1&=0a\_2\\ a\_2&=0a\_3+1a\_5+\epsilon\\ a\_3&=0a\_3+1a\_4+\epsilon\\ a\_4&=0a\_3+1a\_4\\ a\_5&=0a\_6+1a\_5\\ a\_6&=0a\_6+1a\_5+\epsilon \end{align}$$ As for your problem with $a\_5, a\_6$, for example, we could do this: $$\begin{align} a\_5 &= 1^\*(0a\_6)=1^\*0a\_6 & \text{Arden}\\ a\_6 &= 0^\*(1a\_5+\epsilon) &\text{Arden again, now substitute $a\_6$}\\ a\_5 &= 1^\*0\[0^\*(1a\_5+\epsilon)\]\\ &= (1^\*00^\*1)a\_5+1^\*00^\* &\text{so we have}\\ a\_5 &= (1^\*00^\*1)^\*1^\*00^\* \end{align}$$
> 6 votes

# Answer
You can also do this noticing that a binary strings has exactly as many "01" substrings as "10" substrings iff it starts with the same character it ends with. Since you also need the first character to be 0, it's exactly the set of words that start and end with 0 :

$$L = 0 + (0(0+1)^\*0)$$
> 6 votes

# Answer
Converting a finite automata into regular expression is not a trivial problem. However, there are many ways in which one can proceed, discussed here.

The one I think will work best for this FSM is *State Elimination Method*. Go ahead and remove all states one by one other than *initial* and *final* states, preserving the path between states. It's always a better idea to convert such a FSM into NFA with $ \epsilon $-moves with only one *initial* and *final* state. This way after elimination you will be left with only two states.

Here I am including the FSM after eliminating couple of states, specifically states numbered as $4$ and $5$.

Note that $q\_f$ is a single final state obtained by introducing $\epsilon$-moves on three final states in original design of FSM.
Proceed by eliminating state $3$ and $5$ and at last state $2$ to obtain the solution of this problem.

Comment in case you get stuck at some point and want me to include complete answer. I strongly recommend you to do some simple practice problems using this method before you make an attempt to solve this particular problem.
> 2 votes

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


# Question
Title: Changing preference in Gale-Shapley algorithm?
Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm.

If a man were to switch the order of a pair of women, low on his preference list, say $x$ and $y$, would this yield any sort of advantage with regards to being matched with a woman higher than $x$ and $y$?

This seems like a fairly simple problem; I don't see how switching a pair low on the preference list would increase the chance of being matched with something higher on the list. How would one prove the existence or non-existence of such an advantage?

I've come to the conclusion that this would not yield an advantage, but would still appreciate some guidance with regards to proving that.

# Answer
The property your wish to prove is known as *strategy proofness*: Is it possible for an agent to report a preference $P'$ such that it gets matched to a strictly better result w.r.t. its true preference $P$ than reporting truthfully?

Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the preference to their advantage, as you can see with a simple example. In fact, there exists no stable matching mechanism that is strategy proof for *all* agents.

The proof of strategy proofness for men in the GS matching algorithm is, although it seems an obvious statement, rather involved. The clearest presentation I've been able to find is in the paper Machiavelli and the Gale-Shapely algorithm by Dubins and Freedman. In this paper, after proving strategy proofness, the authors proceed to prove the even stronger property of *coalition strategy proofness*:

> (17) THEOREM Suppose several students collude in a Gale-Shapley algorithm, each using a false rank ordering. They cannot all get better universities. "Better" is relative to each student's true rank ordering, and indicates strict inequality.

---

If you want a simple proof of strategy proofness of *some* matching mechanism, you can look at the *Serial Dictatorship* mechanism (also known under the perhaps less ominous name of Deferred Acceptance (DA) with single tie-breaks).

This is perhaps the simplest matching mechanism for the case with one-sides preferences and can relatively simply be shown to be both Pareto efficient and strategy proof.
> 4 votes

---
Tags: algorithms, graphs, algorithm-analysis, matching, bipartite-matching
---


# Question
Title: Counting number of permutations respecting partial order
Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c\_{ij} \in \\{-1, 0, 1\\}$ where $0$ represents unknown and $-1, 1$ represent $A\_i \< A\_j$ and $A\_i \geq A\_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A\_i \< A\_i$ or some chain of comparisons that violates transitivity.

# Answer
> 2 votes
Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, *estimate* the number of linear extensions efficiently.

---
Tags: permutations, counting, partial-order
---


# Question
Title: Does the language of TM's that repeat a configuration infinite times semi-decidable or not?
Let us define the following languages: <sub> $$ {L\_1 = \\{\langle M\rangle : M \ \text{is a TM and $\exists w\in \Sigma^\*$ s.t $M(w)$ repeats a configuration infinite times}\\}} $$</sub>

<sub> $$ L\_2 = \\{\langle M\rangle : M \ \text{is a TM and on all inputs there exists a configuration that repeats infinite times}\\} $$ </sub>

My question is what class does this languages belong to ($\mathcal{R},\mathcal{RE\setminus{R}}, etc...$)? I have shown that:

${H\_{TM}}\le\_m L\_2$: On input $\langle M,w\rangle$ return a new $TM$ $\langle M' \rangle$ such that on all inputs, runs $M$ on $w$. Keep a counter at the beginning on the number of steps (to avoid entering the same configuration infinite number of times, if it doesn't stop). If it does stop, repeat some configuration in a loop.

So that seem to prove that $L\_1,L\_2\notin \mathcal{R},\mathcal{co-RE}$.

But is it in $\mathcal{RE}$? I couldn't write a $TM$ that accepts those languages, nor derive a reduction from $\overline{H\_{TM}}$, $\overline{A\_{TM}}$ or any other relevant language.

Any ideas on solving this? Thanks!

# Answer
> 2 votes
$L\_1$ is indeed recursively enumerable. Suppose for simplicity that the input consists of a pair $M,w$ and you want to know whether $M$ repeats a configuration during its computation on $w$. You can then loop over the integers, and for each $n\in\mathbb{N}$ check if $M$ repeats a configuration with input $w$ during the first $n$ steps. This is possible since during the first $n$ steps $M$ uses at most $n$ cells from the tape, hence the number of possible configurations is finite (you can store them in memory and mark those which were seen).

Now, you want to add an additional existential quantifier over the words $w$, and this can be achieved by dovetailing. Simultaneously scan words and computations length, i.e. for each $n$ and for all words of length $\le n$, check if $M$ repeats a configuration during its first $n$ steps.

The additional universal quantifier prevents $L\_2$ from being recursively enumerable, you can show this by reduction from the complement of the halting problem. Given $(M,w)$, your reduction outputs a machine which on input $x$ simulates $M$ on $w$ for $|x|$ steps, and enters a loop iff $M$ did not halt in this time.

---
Tags: formal-languages, computability, reductions, undecidability, semi-decidability
---


# Question
Title: Why is $AF \phi \lor \varphi$ not equivalent to $AF \phi \lor AF \varphi$?
Can someone explain to me (perhaps with an example) why $AF (\phi \lor \varphi)$ is not equivalent to $AF \phi \lor AF \varphi$. This seems counter-intuitive, because in any path where $\phi$ (or $\varphi$) is true, $\phi \lor \varphi$ is true as well. Or is my reasoning wrong?

Thanks

# Answer
> 4 votes
You also need to argue the other way around. "Each path has either $\psi$ or $\varphi$" is not the same as "either each path has $\psi$ or each path has $\varphi$".

---
Tags: logic, computation-tree-logic
---


# Question
Title: Can a DPDA decide if two letters appear the same number of times mod 5?
$ L = \\{ w ∈\\{0,1\\}^\* \mid |w|\_0 = |w|\_1 \mod 5 \\}$

So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA!

I'm studying for my exam and this was on the book, the book says its CFL but doesn't say whether its DCFL or not and does not draw any PDA for it!

i tried making 5 states and go to the next state everytime i see a 0 {because 0 will always be between 0 and 4} but didn't work

also $|w|\_0$ means number of 0's

# Answer
What does $|w|\_0 = |w|\_1 \mod 5$ means ? It could either mean (depending on your book's notations) :

* $\exists k\in\mathbb Z, |w|\_0 + 5k = |w|\_1$
* The remainder from the Euclidean Division of $|w|\_1$ by 5 is $|w|\_0$

Let's first resolve the first case. You should accept if and only if 5 divides $|w|\_1 - |w|\_0$. This can be done with a finite automaton with 5 states, to keep track of $|w|\_1 - |w|\_0\mod 5$ and only accepting when it is in state 0 (I'll let you find the transitions).

In the second case, you need to also ensure that the value of $|w|\_0$ never goes beyond 4. That can be done by copying the same finite automaton as above 4 times, fixing the transitions accordingly (I would recommend to try doing that) and adding a "trash state" to go to if you have read more than four 0.

So we have deterministic finite state automata for both those languages. Finite state automata are just specific cases of PDA where you never use the stack. So there you have a DPDA for each of those languages.

---

Another way to do this, which is probably what the author was looking for, is to try to build a grammar. Hint : such a grammar has 5 non-terminal symbols, 2 terminals symbols, and 11 rules (this is for the first case). Those two constructions are equivalent though.
> 2 votes

# Answer
Your language is regular (it is accepted by a DFA having five states). Every regular language is deterministic context-free. Indeed, a DFA is a PDA which never looks at the stack, and always has exactly one move that it can execute. In other words, the PDA is deterministic, and so the language is deterministic context-free.
> 0 votes

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


# Question
Title: In the Hamming code, how many control bits are needed to be able to correct an error in 15-bits transmited
i don't know if right answer is 4 or 5 ! what did you understand from this question if it was a QCM ? thanks

# Answer
> 0 votes
Since Hamming codes have minimum distance 3, you can always correct a single error. What you are really asking is what is the rate of the Hamming code whose block length is 15 bits. This is information that is readily available from the Wikipedia page, according to which for every $r$ there is a Hamming code with block length $2^r-1$ and message length $2^r-r-1$ (which leaves $r$ control bits). Now it remains to find the value of $r$.

---
Tags: error-correcting-codes, hamming-code
---


# Question
Title: Can Double Hashing return the same value 2 times?
$h(i,k)=(h^{}\_{1}(k)+i * h^{}\_{2}(k)) mod |T|$

as it defined in wikipedia

I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from the other side, is it possible to build $h^{}\_{2}$ in such way to that it never happen?

# Answer
Let's demonstrate what you ask with a complete example. Let's say we have a table of size $|T| = 10$, in which we use double hashing to insert-search for an item. Initially we try to insert-search for an item using $i = 0$. This means we try at location $h\_1(k)\mod 10$ let's say that is $3$. If there is collision we try at the next position that is at distance $h\_2(k)$ from the current position. Or in other words we try for $i = 1$ thus at position $(h\_1(k)+ h\_2(k))\mod 10$ and so on. Usually $h\_2(k)$ is build in such a way that gives values in the range \[1, 10). So given an initial position if we move less than the 10 positions (but at least 1) there is no way to hit the same location again. You can think table $T$ as a circular buffer. That is if we index a position out of the it's length we wraparound from the beginning of the buffer. So if initial position is 3 the next 9 positions are in sequence $4,5,6,7,8,9,0,1,2$.

So $h\_2(k)$ gives the minimum length we move forward to probe for an empty position. This step is always \< |T|. So from step to step there is no way to hit the same location.

You may wonder now that if we miss to find an empty location to insert our k (or in case of search we don't hit k) after several tries (increments of i) then there is possibility to probe some location again after a lot of tries. That is true, but please correct me if I am wrong, that will happen if the load factor is high enough. In such a case you should use a bigger table size of try to fit in it smaller amount of items.

As far as I searched usually the $h\_2(k)$ has the form $m - k \mod m$ where $m$ is the biggest prime smaller than |T| so $h\_2(k)$ will always be $\neq 0$ and $\< |T|$
> 1 votes

---
Tags: hash, hash-tables
---


# Question
Title: Does the k-clique problem became easier on sparse graphs?
Some definitions, just to not create confusion:

1. A *sparse graph* is a graph that contains a number of edges less or equal than the number of vertices.
2. In *$k$-clique problem* we are given a graph and an integer $k$, and the task is to decide whether the graph contains a $k$-clique.

I think that even if we have a sparse graph, nothing changes for the $k$-clique problem (it always has complexity $O(n^k)$ if $k$ is less than number of vertices and it has complexity $O(n^n)$ if $k$ is equal to the number of vertices), but I'm not so sure about this.

Is a $k$-clique easier to find if the graph is sparse?

# Answer
Given a graph $G$ on $n$ vertices, you can always add $\binom{n}{2}$ new vertices not connected to anything to get a new sparse graph $G'$ with the same clique number. So assuming that the graph is sparse doesn't make it much easier to find its largest clique. In particular, determining whether a sparse graph has a clique of given size (which is part of the input) is NP-complete.
> 1 votes

# Answer
Let me not completely agree with Yuval's answer.

Indeed, in some sense sparsity does make a maximum clique problem easier, and this is proved also by solving it on real-life networks. Usually benchmarks for a maximum clique are pretty dense. And here is why.

1. If it is known an integer $k$ that is a lower bound of the clique number (or the number itself, but we are looking for a clique), then one can reduce the graph to $(k-1)$-core, that is the graph where each node has a degree at least $k-1$. The resulting graph might be considerably smaller in size and thus, for example, IP solver might get a huge boost. How to reduce: delete all vertices with degree smaller than $k-1$ until those exist.
2. If you look at sparsity not from the density perspective, but from the degeneracy perspective, things are even more formalized. Usually we say that graph is "sparse" when its degeneracy is low. And there exists FPT algorithms with running time around $O^{\*}(2^{d/4})$ where $d$ is graph's degeneracy (here big-O star means that the algorithm depends polynomially on the graph size).

Conclusively, the maximum clique problem is immensely easier on sparse instances, though it still remains $\mathcal{NP}$-Complete (but FPT on degeneracy).
> 3 votes

---
Tags: complexity-theory, graphs, clique
---


# Question
Title: return all strings contains given string in suffix tree
Here is my question:

Given a compressed suffix tree of string S and a substring T. I need to return all substrings of S that begins with the substring T sorted by lexicographic order.

My approach: I can traverse the suffix tree and find the edge / node which last letter of T is written on it. The subtree of this edge basically should be all the substrings of S beginning with the string T.

Am I right about this one? And How can I print all this subtree sorted?

# Answer
Yes, you are right. You need to consume the symbols of $T$ and all occurrences of it shall be in the sub-tree below the position you stopped.

Since the edges are stored in lexicographical order, you can perform a Depth-first to print all the substrings of $S$ starting with $T$ in lexicographical order.

Using this example from Wikipedia

and assuming $T = A$, we would arrive at an internal node. Doing a DFS, we would have: $A\\$$, $ANA\\$$, $ANANA\\$$.
> 0 votes

---
Tags: algorithms, data-structures, strings, searching, suffix-trees
---


# Question
Title: Finding maximum clique in a distance matrix created by certain pattern
I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum clique in the graph which is created with distance matrix.

Knowing that there exists a pattern in the distance matrix can I find the maximum clique more efficiently?

# Answer
> 1 votes
Although the question lacks some details, I propose my solution to the general version of your problem.

Yes. It really depends on the "pattern" based on which you create the graph. There is an infinite number of patterns. For example, one can propose a simple pattern that makes it easy to find the cliques in linear time:

Pattern 1: There is a link between two vertices if the labels of the vertices are two consecutive numbers. Clique detection algorithm? Simply list the cliques "{1,2}, {2,3}, ..., {n-1, n}".

Pattern 2: There is a link between two vertices if their distance in the original graph is at most two. Clique detection algorithm? Np-hard problem.

---
Tags: graphs, matrices, performance, clique
---


# Question
Title: Algorithm to find most efficent partitioning of a set
Given a set $S$ with a finite number of elements, where each $s\_i\in S$ is itself a set with a finite number of elements, how do you partition $S$ using *as few partitions as possible*, such that all elements of $S$ in each partition are disjoint?

For example, given $$S = \\{\\{1,2\\},\\{2,3\\},\\{1,4\\},\\{1,2,4,5\\},\\{2,5\\},\\{2,3,5,6\\},\\{3,6\\},\\{4,5\\},\\{5,6\\}\\}$$

we have the following partition:

Where each row represents a separate partition. Some simplifications to the problem are that each $s\_i$ contains non-negative integers less than or equal to $n$, where $n$ is the number of elements in $\cup\_{r\in S} r$.

Here's a more complex partition:

Here is an example input. It took 8 partitions, which I'm pretty sure is optimal.

```
{{67, 68, 77, 78}, {78, 88}, {35, 36}, {71, 81}, {78, 79, 88, 89}, {79, 89}, {19, 29}, {32, 33, 42, 43}, {77, 78, 87, 88}, {65, 66, 75, 76}, {34, 35, 44, 45}, {14, 15}, {55, 65}, {22, 23, 32, 33}, {28, 29}, {70, 80}, {88, 89}, {91, 92}, {46, 47, 56, 57}, {46, 56}, {5, 6, 15, 16}, {84, 85}, {56, 57}, {44, 45}, {89, 90, 99, 100}, {68, 69}, {24, 34}, {76, 77}, {53, 54}, {6, 7, 16, 17}, {36, 37, 46, 47}, {82, 83, 92, 93}, {24, 25}, {5, 15}, {43, 53}, {9, 10, 19, 20}, {76, 77, 86, 87}, {30, 40}, {72, 73}, {3, 4, 13, 14}, {8, 9}, {78, 79}, {63, 64}, {58, 59}, {24, 25, 34, 35}, {45, 46, 55, 56}, {3, 4}, {15, 25}, {8, 9, 18, 19}, {26, 27}, {21, 22}, {11, 21}, {55, 56, 65, 66}, {14, 15, 24, 25}, {77, 78}, {98, 99}, {65, 75}, {2, 3}, {5, 6}, {51, 52}, {4, 14}, {17, 27}, {63, 73}, {7, 8, 17, 18}, {12, 22}, {65, 66}, {74, 75, 84, 85}, {56, 57, 66, 67}, {36, 37}, {94, 95}, {64, 65}, {16, 26}, {41, 42}, {90, 100}, {92, 93}, {3, 13}, {52, 53, 62, 63}, {58, 68}, {48, 58}, {45, 55}, {9, 19}, {38, 48}, {47, 57}, {34, 44}, {14, 24}, {57, 58, 67, 68}, {87, 88}, {47, 48}, {31, 32}, {29, 30}, {52, 53}, {20, 30}, {43, 44, 53, 54}, {57, 67}, {81, 91}, {26, 36}, {89, 90}, {59, 60}, {67, 68}, {93, 94}, {10, 20}, {68, 69, 78, 79}, {59, 60, 69, 70}, {4, 5, 14, 15}, {75, 85}, {23, 33}, {72, 73, 82, 83}, {42, 52}, {77, 87}, {9, 10}, {85, 86, 95, 96}, {80, 90}, {50, 60}, {62, 72}, {32, 42}, {7, 17}, {83, 84, 93, 94}, {34, 35}, {41, 51}, {79, 80}, {86, 87, 96, 97}, {49, 59}, {27, 28}, {12, 13}, {18, 19}, {29, 39}, {83, 93}, {35, 45}, {74, 75}, {67, 77}, {18, 28}, {61, 62}, {29, 30, 39, 40}, {61, 71}, {39, 49}, {53, 54, 63, 64}, {82, 83}, {37, 38}, {76, 86}, {33, 34, 43, 44}, {44, 54}, {69, 70}, {81, 82}, {2, 3, 12, 13}, {63, 64, 73, 74}, {46, 47}, {54, 55}, {39, 40}, {51, 61}, {42, 43, 52, 53}, {25, 26}, {33, 34}, {6, 7}, {60, 70}, {66, 67, 76, 77}, {27, 37}, {32, 33}, {2, 12}, {57, 58}, {73, 83}, {16, 17, 26, 27}, {1, 11}, {19, 20, 29, 30}, {27, 28, 37, 38}, {62, 63, 72, 73}, {48, 49}, {28, 38}, {19, 20}, {75, 76, 85, 86}, {88, 98}, {58, 59, 68, 69}, {64, 65, 74, 75}, {66, 76}, {15, 16}, {52, 62}, {66, 67}, {79, 80, 89, 90}, {12, 13, 22, 23}, {55, 56}, {26, 27, 36, 37}, {53, 63}, {13, 23}, {8, 18}, {83, 84}, {73, 74}, {17, 18, 27, 28}, {31, 41}, {54, 64}, {1, 2}, {7, 8}, {13, 14, 23, 24}, {16, 17}, {38, 39, 48, 49}, {97, 98}, {96, 97}, {59, 69}, {71, 72}, {88, 89, 98, 99}, {68, 78}, {99, 100}, {47, 48, 57, 58}, {18, 19, 28, 29}, {28, 29, 38, 39}, {74, 84}, {72, 82}, {22, 23}, {69, 70, 79, 80}, {44, 45, 54, 55}, {56, 66}, {40, 50}, {73, 74, 83, 84}, {86, 96}, {87, 88, 97, 98}, {25, 35}, {69, 79}, {45, 46}, {35, 36, 45, 46}, {36, 46}, {85, 95}, {23, 24}, {23, 24, 33, 34}, {25, 26, 35, 36}, {84, 85, 94, 95}, {84, 94}, {86, 87}, {33, 43}, {15, 16, 25, 26}, {64, 74}, {21, 31}, {13, 14}, {87, 97}, {17, 18}, {54, 55, 64, 65}, {22, 32}, {82, 92}, {38, 39}, {62, 63}, {37, 47}, {85, 86}, {42, 43}, {95, 96}, {39, 40, 49, 50}, {75, 76}, {4, 5}, {11, 12}, {49, 50, 59, 60}, {43, 44}, {49, 50}, {48, 49, 58, 59}, {6, 16}, {37, 38, 47, 48}, {89, 99}}

```

The algorithm I used to do the partitioning on the above sets works as follows: (python pseudocode)

```
partitions = []
for s in S:
    found_partition = False
    for p in partitions:
        if p.isdisjoint(s):
            p.update(s)
            found_partition = True
            break
    if not found_partition:
        partitions.append(set(s))

```

However I know this algorithm isn't optimal because I've gotten different numbers of partitions depending on the order of the input data. When the above input data is sorted, it takes 8 partitions, but otherwise it takes 11.

# Answer
> 1 votes
I am not sure if you are looking for an exact polynomial algorithm or not. If so, I have bad news. This problem is NP-hard, due to a reduction from the vertex cover problem. In the following, please find a brief sketch of the proof/reduction (I did not deal with decision problems, it is very straightforward reduction after you read the following).

Given an instance of the vertex cover problem $I=\langle G=(V, E) \rangle$ (and a $k$ in the instance of the decision problem), you can construct an instance of your own problem $I'= \langle S \rangle$ (and a $k$ in the instance of the decision problem) that decides the answer to the vertex cover problem. Let $G'=(V, E')$ be the complement graph of $G$, where there is an edge between two vertices $v\_i$ and $v\_j$ in $G'$, if and only if there is no edge between $v\_i$ and $v\_j$ in $G$. Assign each vertex $v\_i \in V$ a set $S\_i$, initially set to empty. Start with a vertex $v\_1$ and for every neighbor $v\_i$ of $v\_1$, add the label $v\_1i$ to both sets $S\_1$ and $S\_i$. Then, do the same thing for vertices $v\_2$, ..., $v\_n$. You will end up with a set $S=\\{ S\_1, \cdots, S\_n \\}$. If you solve your proposed problem over $S$, this is identical to the vertex cover of $G$.

**Good news?** You can apply all approximation and heuristic algorithms presented for vertex cover problem to your problem easily.

---
Tags: optimization, sets
---


# Question
Title: Is Acceptance by Empty stack and Final state possible in the same PDA?
$L$ is the language accepted by the above PDA :
$L = \\{a^n\mid n\geq 0\\}\cup\\{a^n b^n\mid n\geq 0\\}$ and is deterministic context-free is the language accepted by the PDA how can we accept $a^n$? As it doesn't contain an epsilon transition at the end right ? Is acceptance by both the final state and empty stack possible in the same PDA?

# Answer
The PDA can accept $a^n$ because :

1. Till we don't read a $b$, we stay in start state.
2. The start state is a final state.

By acceptance by final state, the PDA accepts strings of the form $a^n$.

For strings $a^nb^n$, we have the following :

1. $X^n$ is pushed on the stack, by reading $a^n$ and looping over the start state.
2. For the first $b$, pop the stack, and continue to pop till we get only $Z$ in the stack.
3. When only $Z$ remainded, we have only one choice to do, and even if it's an epsilon transition, because it's the only possible transition at this point, the automaton is still deterministic.

We have also here an acceptance by final state.

In addition, we can define both acceptance by final state and by empty stack on the same PDA, but generally, the two don't lead to the same language. For your language, acceptance by empty stack lead to an empty language, because the stack can never be empty.
> 3 votes

---
Tags: pushdown-automata
---


# Question
Title: Smallest length such that all substrings of that length contain at least 1 common character
Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common character.

Examples:

1. y d c b f

Answer = $3$ (common character is 'c')

2. n n n n n n n n n

Answer = $1$ (common character is 'n')

3. y e y d y e y

Answer = $2$ (common character is 'y')

The only solution I have thought of till now goes like this:

Find all sub-strings of length $x$ from $1$ through $n-1$ (where $n$ is the length of the given string). Compare the sub-string for common characters (and store which characters are common). As soon as I come across a pair of the sub-string of length $x$ which doesn't have any common characters I move to the next value of $x$. If no such $x$ is found, return $n$.

Is a more efficient solution possible?

# Answer
> 0 votes
An equivalent formulation of your problem is:

> Given a string $S$ of length $n$, what is the minimal $k$ such that there exists an character $s\in S$ such that for all $i\in\\{1,\ldots,n\\}$, there exists a $j$ s.t. $|i-j|\leq k$ and $S\[j\]=s$. Report $k+1$.

Your approach seems to take $O(n^4)$ time in the worst case. If you try to see if the above formulation holds for all characters $s\in S$, you should be able to do it in $O(n)$:

Do a single linear scan trough $S$, while maintaining the last index you've seen each of the characters present in $S$ and the maximum gap size for each of those characters. After that, pick the character $s\in S$ with the smallest maximum gap size, this size is the value $k$. (Improved to a single pass thanks to @j\_random\_hacker's remark)

So, you can solve this problem in $O(n)$ time, which is a lot better than your initial approach. This approach is even asymptotically optimal, as we have to at least scan the entire string in the worst case, so we require at least $\Omega(n)$ time.

# Answer
> 0 votes
You assume that all substrings would need to have the same common character, but that is not the case.

Take a string that repeats the following:

abcdefghijxy0123456789xzabcdefghijyz0123456789xyabcdefghijxz0123456789yz

Every substring of length 12 contains two of x, y and z, so any two substrings of length 12 have a common character. But there are substrings of length 22 containing no x, substrings of length 22 containing no y, and substrings of length 22 containing no z.

You find the minimum length for a globally common character easily in O(n) by keeping track of the length of gaps for each character, and picking the shortest maximum gap. Here's how you do it:

```
for each character c
    c.lastfound = 0
    c.largestgap = 0

for 1 ≤ i ≤ length (string)
    let c = character #i of the string
    c.largestgap = max (c.largestgap, i - c.lastfound)
    c.lastfound = i

let minlength = length (string)
for each character c
    c.largestgap = max (c.largestgap, length (string) + 1 - c.lastfound)
    minlength = min (minlength, c.largestgap)

```

Any substring of length minlength contains the character(s) c where c.largestgap = minlength, and any two such substrings have those characters in common. On the other hand, if we take len \< minlength, then for every character c we have c.largestgap \> len. And when c.largestgap was set to that value \> len, the preceeding c.largestgap - 1 characters in the string didn't contain c, so there is a substring of length len not containing c.

Runtime is O (max (length (string), number of characters).

The original problem (where you asked for a common character, not for all substrings having the same common character), is a lot harder. Finding the length needed for *the same* common character is very easy and gives an upper bound.

---
Tags: algorithms, strings, substrings
---


# Question
Title: Explain why a language can be generated by a context free grammar
I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free grammar. I am not sure of what is asked here, will finding such a grammar work? What should I do?

# Answer
Usually, to prove that some language is a CFL (which is equal as asking whether it is generated by some CFG) you can show:

1. It is generated by some CFG. Proving is usually done by induction, where one direction is an induction on the number of derivation steps, and the other direction is usually an induction on the length of the word.
2. Showing a PDA that accepts the language.
3. Using closure properties of CFL, and generate the language from some finite number of CFL/regular languages using closure properties (like concatenation, union, etc..)
> 0 votes

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


# Question
Title: Minimum spanning tree - Prim's algorithm
I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I did wrong ?

Here is the exercise:

The first solution (using Prim's) is visiting the nodes in the following order: v0,v1,v8,v7,v6,v3,v2,v4,v5 Here the MST has a weight of 37, which is the same result that I got by using Kruskal's on the same graph.

The second solution (again using Prim's) however is the following order of visited notes: v0,v1,v3,v2,v7,v8,v6,v4,v5 , which leads to a MST with a weight of 39. How can this be ? Where is my mistake ?

Thanks in advance

# Answer
> 1 votes
Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here.

Your second solution: $v\_0,v\_1,v\_3,v\_2,v\_7,v\_8,v\_6,v\_4,v\_5$ is incorrect. After adding $v\_0,v\_1,v\_3,v\_2$ you add $v\_7$. But the minimum distance between $v\_7$ and any existing vertex in the tree is $6$. Vertex $v\_6$ however has a distance of only $4$, and should thereby be added first.

You could continue this, and end up with a solution that is indeed different from your solution 1, but has the same weight. For example, $v\_0,v\_1,v\_3,v\_2, v\_6, v\_7,v\_8,v\_4,v\_5$, which gives an MST of weight $37$, as expected.

---
Tags: algorithms, graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: How can I efficiently plot the inside of an ellipse?
I am given the the coefficients for an ellipse in the form: $$Ax^2 + Bxy + Cy^2 + Dx + Ey + F=0.$$

I have a 2 dimensional array of point objects (in Python) called "pixels", and I need to give each point a "count" if they lie inside the ellipse.

I initially tried iterating through every point with a loop like:

```
for row in pixels:
    for pixel in rows:
        x=point.get(pixel)[0]
        z=point.get(pixel)[1]
        if a*(x)**2 + b*(x*z) + c*(z)**2 + d*(x) + e*(z) + f >0:
            pixel.addpcount()

```

But this is taking *way* too long because I have several thousand ellipses I need to do this for. Is there a way I can efficiently do this?

(If this is not the right place to ask this question, I apologize.)

Edit: (I don't have enough reputation to comment). The Python is mostly irrelevant to my question at hand. I just want a better algorithm instead of iterating through every point.

In order to determine whether something is inside an ellipse, I am actually using this test https://math.stackexchange.com/questions/817130/how-to-determine-if-arbitrary-point-lies-inside-or-outside-a-conic.

The user Evil suggested using Axis Aligned Bounding Box. Does this mean finding the box which bounds an ellipse, and then testing only those points inside the box? That would seem a lot more efficient.

Greybeard, I am not sure what the Bresenham algorithm is, but I will take a look.

# Answer
Following @Evil's comment, I suggest two steps. For each ellipse $E$:

(1) Computing a bounding box $B$ for $E$.

(2) For each row of pixels in $B$, walk left-to-right until a pixel $p\_1$ is discovered to be inside $E$. Then walk right-to-left until $p\_2$ is in $E$. Then all the pixels from $p\_1$ to $p\_2$ are in $E$ (because of convexity).

---

---

The most difficult step is computing a bounding box for the ellipse. You likely don't need it exactly. Here are two sources:
> 2 votes

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


# Question
Title: What does synchronous and asynchronous mean in computer science?
Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example :

1. Synchronous and asynchronous circuits.
2. Synchronous and asynchronous calls.
3. Synchronous and asynchronous messages.

I never really understood the real meaning of those terms, and also the common sense that different usages of synchronous and asynchronous have.

So my question is : *What does synchronous and asynchronous really mean in computer science ?*

# Answer
As Discrete lizard suggests, there is not some precise CS-wide definition for these terms. Generally, you should not expect terms and notation to always mean the same thing even within a single field.

Nevertheless, a vague general statement is that in "synchronous" systems, things "wait" for other things, while in "asynchronous" systems, things don't "wait".

That said, it's probably better to split this into two broad interpretations of this. There's "synchronous" in the sense of everything moving in lock-step (i.e. everyone "waits" for the next "round" or everyone "waits" on a "clock"). This interpretation is probably the closer of the two to the colloquial notion. This applies to synchronous circuits, Bulk Synchronous Processing, and synchronous data flow. A synchronous circuit has a clock signal and it executes in time with the clock. An asynchronous circuit allows each subcomponent to execute whenever it's ready. It requires careful timing to make sure all the inputs to each subcomponent are ready when that subcomponent is ready.

The other interpretation is blocking where one thing makes a request to another thing and then *sits there waiting for the response*. The "waiting for the response" aspect is what is called "blocking". Synchronous calls/messages would fall under this. The alternative is to send a message and then continue on without waiting for a response. Any response is either ignored or collected in a "mailbox" to be read at some later time. This is often handled by the framework you're using which will then dispatch events to which you register.

The Ptolemy Project is a fantastic resource for in-depth thoughts on different models of computing and their notion of time.
> 6 votes

---
Tags: terminology, concurrency
---


# Question
Title: Learning to prove correctness of simple linked-list algorithms
I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm.

I haven't even found a good tutorial reference. Googling suggested that Cormen's book should be a good starting point. His discussion about linked-list (section 10.2) is quite clear, but doesn't demonstrate any correctness proof.

Where can I find a good resource (preferably a book, but can be any resource...) that will teach me that, with good examples?

# Answer
> 1 votes
Linked lists are data structures. They have a set of operations (like the rest of the data structures) and each operation has some properties. For example, the access in a linked list is performed in linear time.

When you are talking about an algorithm that uses a linked list, you assume you have a linked list that works (i.e. the operations are performing as expected) and you show that using those operations, you can achieve the desired goal. Also, in the algorithm analysis, you have to take into account the time complexity of each operation.

This is not very different from the arrays you probably took for granted in your proofs/programs. They too are a data structure, with some operations, each of which take some time. Actually, most of the times the difference between using and array or a linked list stands in the complexity difference obtained by leveraging the properties of each data structure.

Now, to prove that the linked list really works is not a massive problem, since the operations themselves are very straightforward.

---
Tags: reference-request, correctness-proof, linked-lists, software-verification
---


# Question
Title: Confused b/w non-deterministic finite state automata vs finite state automata
I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing".

As per definition of FSA you can only transition to one state after consuming one input. In this example if the input is say "twenty" to which state it will transition q2 or q1 ? Say if the input was "twenty one". After consuming first string which state it will transition to?

# Answer
The automaton in the image is indeed *nondeterministic*.

You need to think a little differently about nondeterministic machines. It's no longer a question of "what happens when X?" but about "what *can* happen when X?". For each input, there can be many different computations, even with different outcomes.

Note how the definition of acceptance is different. For DFA, it's "the (unique) computation is accepting"; for NFA, it's "there *exists* an accepting computation".

Here, in your example, if the input is "twenty", there are two computations:

1. $q\_0 \to q\_1$ and
2. $q\_0 \to q\_2$.

Since the second is accepting, "twenty" is in the language of this automaton.

---

*Side note:* A TCS book that uses `twenty` as terminal symbol and generally avoids LaTeX for it's mathematics typesetting is highly suspect. I recommend that if you run into any problems, look for a standard textbook before worrying too much.
> 0 votes

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


# Question
Title: Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?
In this question

Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have reached a contradiction or the current boolean formula cannot be simplified anymore.

**ratchet freak** answered that this method doesn't work on all inputs.

I have new idea:

Instead of using karnaugh maps let's use Quine McCluskey algorithm to simplify the entire/whole boolean formula by simplifying subformulas and if you have reached a contradiction then return "unsatisfiable" as answer.

If the current boolean formula cannot be simplified anymore then return "satisfiable" as answer.

Does the new algorithm work?

# Answer
If you're planning to apply this to each subformula with 16 variables:

No, that doesn't work for the same reason given in ratchet freak's answer. As the Wikipedia article states, Quine McCluskey is functionally identical to Karnaugh maps, so your idea has the exact same problem.

---

If you're planning to apply this to the entire formula:

No, that doesn't work. Quine McCluskey outputs a DNF formula or CNF formula. That alone doesn't tell you whether the resulting formula is satisfiable or not. You haven't said how to test whether there is a "contradiction"; testing for a "contradiction" is exactly the problem of testing satisfiability, so this hasn't gained you anything.

In any case, Quine McCluskey takes exponential time in the worst case. Therefore, this approach is inefficient for formulas of any substantial size. As far as asymptotic worst-case running time is concerned, you might as well just enumerate all possible assignments and see if any of them satisfy the algorithm -- that also takes exponential time.
> 1 votes

---
Tags: algorithms, logic, satisfiability, decision-problem, propositional-logic
---


# Question
Title: Obtain data structure able to do reverse range updates
For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to perform two types of operations.

A. Update operation: Reverse the elements in the range $A\[l\_i \dots r\_i\]$

B. Query operation: Find the index of element $x$.

My thinking was to build segment tree, but the reverse query is hard to do, then I was thinking about implementing a balanced interval tree, and reversing the nodes, but the problem is balancing the tree, which is too slow.

# Answer
> 0 votes
So I have two ideas, one is more mathy than the other.

# Double linked list

You can use a custom made double linked list, in which nodes also have a boolean field `reverse`, set to false by default.

When going through the list, every time a node has `reverse` field `true`, you start going backward (when supposed to go right, you go left), until you encounter a true valued `reverse` field again.

To reverse a range from $i$ to $j$, you go to $i$ from the start and retrieve the actual state of walkthrough (LtR or RtL). You do the same for $j$. You accordingly reconnect $i$ to $j+1$ and $j$ to $i-1$ (they are 16 cases to handle if I'm not mistaking). Finally, `i.reverse <- !i.reverse`, same for $j$, and you're done !

To get the index of element $x$, you just have to look for $x$ while going through the list.

Complexity :

* Update operation $(i,j)$ : $O(j)$
* Find $x$ : $O(k)$ where $k$ is the index of $x$.

So both are in $O(n)$ in worst case.

# An array and permutations

You just keep an array and a permutation $\sigma\in \mathfrak S\_n$. You'll find ways to encode them in the link. Whenever you have to reverse from $i$ to $j$, you do the following : $$\sigma \gets \begin{pmatrix} 1 & 2 & \cdots & i-1 & i & i+1 &\cdots & j-1 & j&j+1 &\cdots & n\\ 1 & 2 &\cdots & i-1 & j & j-1 & \cdots & i+1 & i & j+1 & \cdots & n\end{pmatrix}\cdot\sigma$$ This multiplication can be done in $O(n)$. Read is then constant time. Finding an element can be in $O(\log n)$, if you sort the array and keep it's starting permutation in $\sigma$ at the start.

---
Tags: data-structures, trees, binary-trees, intervals
---