# Question
Title: What's wrong with this problem (Inclusion-Exclusion principle)
There are 120 students at University College taking the introductory Java programming class. The students have access to the following computers:

```
80 students have access to a PC running Microsoft's Windows operating system.
40 students have access to a computer running the Apple operating system.
10 students have access to a computer running the Linux operating system.
30 students have access to a computer running the Apple or Windows operating system.
7 students have access to a computer running the Windows or Linux operating system.
5 students have access to a computer running the Apple or Linux operating system.

```

How many have access to computers running all three operating systems?

The solution, using the Inclusion-Exclusion principle for 3 sets wikipedia link, is 32. However, how can it be 32 when the number of students who have access to Linux is only 10?

# Answer
Let $A$, $B$, and $C$ be the set of pupils that have access to a PC running Windows, Apple, and Linux, respectively.

We know that \begin{align\*} |A \cup B \cup C| &= 120 \\ |A| &= 80 \\ |B| &= 40 \\ |C| &= 10 \end{align\*}

As @Tom van der Zanden pointed already pointed out in the comments, the wording of *"... running the Apple or Windows operating system"* is unclear. Thus I will cover all three interpretations of that wording.

---

**Interpretation 1**: *"... running the Apple or Windows operating system"* means the PC has installed both the Apple and Windows OS.

This means \begin{align\*} |A \cap B| &= 30 \\ |A \cap C| &= 7 \\ |B \cap C| &= 5 \end{align\*} Using inclusion-exclusion, we come to the result that \begin{align\*} |A \cap B \cap C| &= |A \cup B \cup C| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C|\\ &= 120 - 80 - 40 - 10 + 30 + 7 + 5 \\ &= 32 \end{align\*} So your calculation is correct and there is a contraction. That means that either

1. the inclusion-exclusion princliple does not hold in general, or
2. the exercise description is inconsitent, i.e. some of the cardinalities are wrong.

Since the inclusion-exclusion principle is proven to hold for any arbitrary set of sets, the latter case must be true.

---

**Interpretation 2**: *"... running the Apple or Windows operating system"* means that the PC runs **either** the Apple **or** the Windows OS.

We can calculate the cardinalities of the intersections $A \cap B$, $A \cap C$, and $B \cap C$. However, we also run into a contradiction by using this interpretation:

\begin{align\*} & |(A \cup C) \setminus (A \cap C)| = |A \cup C| - |A \cap C| = |A| + |C| - 2|A \cap C| \\ \implies & |A \cap C| = \frac{|(A \cup C) \setminus (A \cap C)| - |A| - |C|}{-2} = \frac{7 - 80 - 10}{-2} = 41.5 \end{align\*} The above is a contradiction, since the cardinality of a finite set must be a natural number.

---

**Interpretation 3**: *"... running the Apple or Windows operating system"* is a regular logic or.

We have $|A| = 80 \> 30 = |A \cup B|$. This is also a contradiction, since the cardinality of a set cannot be greater than the cardinality of its superset.

---

For either interpretation we show that there is a contradiction, therefore there must be a problem in the exercise description
> 5 votes

---
Tags: discrete-mathematics
---


# Question
Title: Why do I need high fps values in simulations?
Sometimes I see NVIDIA simulations with an additional information abbreviated "fps". I've figured out that fps stands for frames per second, but isn't it enough to support 25 fps? Why do I need 60fps ? Most of the movies use 25 fps and not 60. So does anybody know a reason for that ?

# Answer
This is actually a *cinematography* question, but what makes it interesting for computer science is that it does influence computer graphics. Computer graphics, as Steve Hollasch famously said, is the only area of science where if it looks right, it is right. So we do need to understand what it means for something to look right.

The question that you're really trying to ask is why movies look smooth even at low frame rates like 24fps, given that our eyes have a much higher effective frame rate. The persistence of vision effect should mean that if a character or object is moving, it would be seen as multiple instances of the same object, an effect known as "strobing".

The reason why it was never a problem in chemically-photographed movies is a device called the rotary disc shutter. Photographic film requires that the shutter be open for a certain amount of time, however for a moving film this presents a problem. A rotary disc shutter is a circular plate with a sector of around 180 degrees cut from it, which rotates in front of the film plate. While the shutter is open, light falls on the film. While it's closed, the frame can be advanced.

The shutter angle is one of the variables that a film-era cinematographer could control. It represents how much of the 1/24th of a second the film is exposed for. If the angle is large and the subject is moving fast, rather than seeing two copies, you see motion blur. A point becomes a line, and that line represents the motion of the subject.

Changing the shutter angle affects the exposure time and the amount of motion blur. A smaller angle means the exposure time is shorter (so you may need to use faster film or brighter lights), but the blur is less.

So a fast-moving point moving in a straight line would appear, on film, as a series of "dashes" which are colinear. The answer to the question, why film looks smooth despite the low frame rate, is that the film looks smooth *because our brains can follow that line*, and hence interpret the motion correctly.

(As an aside, TV cameras worked differently, but they had similar analogue properties which meant that you got motion blur.)

Animators quickly worked all this out. Cartoons are inherently unrealistic, so we accept a certain amount of unreality, but animators learned how much you could move an object before strobing took over. If fast motion was needed, they would have to blur manually, using drawings which mimicked temporal subsampling, were distorted in a way that simulated motion blur, or used speedlines, drybrush, and whatever other manual techniques worked.

The image following shows a great combination of some of these techniques. At 24fps, this wouldn't register.

This has implications for computer graphics, both for computer-generated imagery and digital movie cameras. What chemical cameras get for free, digital images must produce somehow.

Rendering fast motion at 24fps, and retaining the illusion of smoothness, requires rendering motion blur. Doing it "right" can be extremely expensive, because it interacts with hidden surface removal in nontrivial ways. (Consider a spinning top with a pattern on it. As time moves on, different parts of the top become visible.)

This is why computer animated movies (where frames are not produced in real-time) tend to look smoother than video games even though the frame rate of a movie is lower. Video games have recently started using screen-space approximations to motion blur, and they can help a lot, but there is usually still apparent strobing.

One of the interesting things about digital cameras is that the "degree of blur" control is effectively decoupled from the "amount of light exposure" control. A modern cinematographer can control these variables independently, where a film cinematographer would have to manipulate them together.

The choice of shutter angle was (and still is) often made for artistic as well as practical reasons. Famously, Janusz Kamiński used a 45 degree shutter angle for some of the shots in *Saving Private Ryan*, which had the effect of making action scenes appear *less* smooth, and hence more jarring, gritty, and frightening (Kamiński used the word "staccato") compared with most action films.
> 1 votes

# Answer
Tricky part is "enough". Although it is sufficient to have a fluent visual effect with merely 22-26 fps (which is what movies commonly use), you will notice a much more comfortable and soothing experience with much higher fps.

Youtube supports both 30 and 60 fps. You could try to find a video that **is prepared for 60fps** and play it twice with different fps (by changing playback resolution/fps in youtube player). I am sure you will see the difference in no time.
> 0 votes

# Answer
Most LCD panels have a refresh rate of 60 Hz, i.e. the screen is refreshed 60 times per second. Video looks better when the number of screen refreshes between two successive frames is constant, otherwise the frame rate will look jittery. That makes 30 fps and 60 fps good choices, whereas 25 fps would cause jitter. Obviously a larger value provides more control (but values above 60fps would be useless except with a screen that refreshes faster), so it will in principle look nicer (there's no guarantee that the difference will be visible though).
> 0 votes

---
Tags: graphics
---


# Question
Title: How is the directory implementation done using a linear list?
I am reading Operating System Concepts by Silberchatz, Galvin, Gagne and they write that a directory can be implemented using a linear list. \[pg 470, 8th ed\]

However, I visualize directories as a rather hierarchical data structure which can be implemented using a B-tree.

Also, when they say that the nodes contain a pointer to the data blocks, what do they mean?

# Answer
> 2 votes
A directory is a collection of files, some of which could be directories. You can store the list of files forming a directory as a linear list. This is somewhat similar to the adjacency list representation of a graph (imagine that the graph were a tree).

Each node in the list contains some sort of information regarding the file, such as the name, size and contents. The contents themselves are not stored at the list, but somewhere else in the filesystem. Each node just contains a pointer to the data, which is what is meant by *data blocks*. The exact way in which this is implemented depends on the file system – the main issue here is that the file isn't stored contiguously.

---
Tags: operating-systems, linked-lists, filesystems
---


# Question
Title: Find one-variable recursive formula for running time of Karatsuba multiplication
I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion for two $n$ bit integers for Karatsuba multiplication would be:

$T\_{n} = \begin{cases} 3T\_{n/2} + cn &\mbox{if } n \> 1 \\ 1 &\mbox{if } n = 1\end{cases}$

However, when working with two integers with different number of bits, the expression would be different, as we would have $T\_{n,m}$ as a recursion. Is there any way to reduce the problem of setting up the recursion in terms of only one variable $n$? I was thinking of letting $T\_{n}$ be the maximum number of operations with the pairs $(n,m)$, and basically giving the same recursive formula as stated above. Would that change the running time of the program or is there a more clever way to change it into a one variable recursion?

# Answer
The recurrence with two variables $n,m$ is as what you have obtained:

$$T(n, m) = 3T(n/2, m/2) + O(\max(n,m))$$

Assume $n = \Omega(m)$. We have

$$T(n, m) = 3T(n/2, m/2) + O(n)$$

Although the master theorem cannot be applied directly, if you expand this recurrence, then you will eventually identify the patterns and the result:

$$T(n, m) = 3T(n/2, m/2) + O(n) = \cdots = \sum\_{k=?}^{k=?} (3/2)^{k} \cdot O(n) + c \cdot T(n/m,1) = \cdots$$ Please find out $c$ and the range of $k$, and fill the gaps.

---

There is a method to reduce the two variables $n,m$ recurrence to a single one:

> Assume $n = \max(n,m)$ and pre-append $n-m$ $0$'s to the integer with less bits.

The problem is this will yield a different time complexity from that given above. This can be seen from an extreme example: $1$-bit $\times$ $O(n)$-bit.
> 1 votes

---
Tags: algorithm-analysis, recursion, divide-and-conquer
---


# Question
Title: Intuition for convolution in image processing
I have read many documents about *convolution* in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing convolution on an image. For example, intuition of derivation on the graph is make it more linear for example.

I think a quick summary of the definition is: convolution is multiplied overlap square between image and kernel, after that sum again and put it into anchor. And this doesn't make any sense with me.

According to this article about convolution I cannot imagine why convolution can do some "unbelievable" things. For example, line and edge detection on the last page of this link. Just choose appropriate convolution kernel can make nice effects (detect line or detect edge).

Can anyone provide some intuition (doesn't need to have to be a neat proof) on how it can do that?

# Answer
> 14 votes
I think the simplest way to think of Convolution is as a method of changing a pixel's value to a new value based on the weight of nearby pixels.

It's easy to see why Box Blur:

```
_____________
|1/9|1/9|1/9|
|1/9|1/9|1/9|
|1/9|1/9|1/9|
-------------

```

works. Convolving this kernel is the same as going through every pixel of a photo and making the new value of the pixel the average of itself and the eight surrounding pixels.

If you get that, you can see why Gaussian Blur works:

```
_____________________
|.01|.04|.07|.04|.01|
|.04|.16|.26|.16|.04|
|.07|.26|.41|.26|.07|
|.04|.16|.26|.16|.04|
|.01|.04|.07|.04|.01|
---------------------

```

It's basically the same thing, except the averaging is weighted more strongly toward pixels that are closer. The function that defines how quickly the weights fall off as you move further away is the Gaussian Function, but you don't need to know the details of the function in order to use it for blurring.

The edge detection kernel in the linked article makes sense if you stare at it long enough too:

```
__________
|-1|-1|-1|
|-1|.8|-1|
|-1|-1|-1|
----------

```

It's basically saying that the value of any pixel starts at 8/9ths of it's original value. You then subtract the values of every pixel around it to arrive at your new pixel.

So if the value of a pixel is high and the value of the pixels around it are high too, they will cancel each other out. If the value of the pixel is low and all of the pixels around it are low as well, they will also cancel each other out. If the value of the pixel is high and the value of the pixels around it are low (as in a pixel on the edge of an object) the new pixel value will be high.

# Answer
> 7 votes
One way to think about convolution/crosscorrelation is as if you were searching for some signal in your data. The more the data looks like the kernel, the higher the resulting value will be. I actually take the reverse of the kernel, i.e. as in cross-correlation, but it is basically the same thing.

For example, let's say you are looking for a directional step in your 1d data.

The kernel could be

```
[-1 1]

```

and let's apply that to the data

```
[2 2 2 2 2 1 1 1 1 1]

```

The result will be

```
[0 0 0 0 0 1 0 0 0 0]

```

Which detects the location of the step. A larger step would give a larger value.

This works because when you multiply a pattern by the one appearing in the kernel you get a high value.

Edge detection (or any other pattern detection) works the same way, for example with the kernel

```
[-1 2 -1]

```

Extensions to higher dimensions can also be thought if this way.

This should give you intuition at least about some of the applications of convolution image processing.

# Answer
> 4 votes
If you think convolution is a little too hard to understand, I recommend you start searching about Mathematical Morphology applied to image processing, the big idea behind Mathematical Morphology is that you'll do a operation very close to the convolution, to "change" the morphology of the image, but retain the topology information, this way, you can make a image of a standing human, a skeleton, which is pretty much a stick human, try applying the erosion operation, then dilate operation, then go to the open/close operation, you'll start to understand what a mask applied to every pixel of image can do, and how they can be used in a big scenario to achieve great results(like finding a spot to start something using last erosion), once you understand Mathematical Morphology, convolution is a little bit harder, because its based on calculus, and defined after integrate, but still, alot of convolution are easy to understand, like median blur, gaussian blur, sharpen, edge detection, laplace, gradient, etc.

---
Tags: terminology, intuition, graphics, computer-vision
---


title: Complexity of nested loops

text:
# Question
Title: Complexity of nested loops
I'm trying to figure out the complexity of the following algorithm.

```
for(int i=1; i <= N; i++)
        for(int j=1; j <= i; j++)
            for(int k=1; k <= i*sqrt(j); k++)

```

I'm trying to figure it out using a method similar to rizwanhudda's solution in this similar question. I'm having some trouble though because the innermost loop references both i and j. Can somebody translate this problem into something similar to rizwanhudda's approach (ie count the number of triplets (i, j, k))? Thanks!

# Answer
> 3 votes
I'm not convinced the approach translates well. In particular, the last statement would become something like "the square root of the number of boxes \[...\]" and that doesn't work out well. A more traditional way to approach this is:

The inner loop has complexity $\Theta(i\sqrt{j}))$. This loop is executed for $1\leq j \leq i$ (middle loop) which gives a complexity of

$\Sigma\_{j=1}^i i\sqrt{j}=i\Sigma\_{j=1}^i \sqrt{j}$

Evaluating $\Sigma\_{j=1}^i \sqrt{j}$ is tricky. There is no closed-form formula, but we can obtain an approximation by changing the sum to an integral. Note that

$\int\_0^i x^{1/2}=\frac{2}{3}i^{3/2}$

is a lower bound, while

$\int\_1^{i+1} x^{1/2}=\frac{2}{3}{i+1}^{3/2}-\frac{3}{2}$

is an upper bound. We may conclude that

$\Sigma\_{j=1}^i \sqrt{j}=\Theta(i^{3/2})$.

Hence the middle loop has complexity $\Theta(i^{5/2})$. For the outer loop, we have to evaluate

$\Sigma\_{i=1}^n i^{5/2}$

for which there is once again no closed-form formula. By applying the same integral technique, we find that the complexity is

$\Theta(n^{7/2})$.

However, finding a closed-form formula for the exact complexity (without asymptotic notation) is impossible.

# Answer
> 0 votes
An easy form of deciding the $O$ for your problem is: Think the second and the third loop is just $N$ and what you did there is just an optimization, this way you'll have $O(n^3)$ which I believe most approximates it. Once $N$ is big enough($\infty$), your algorithm will surely converge near $O(n^3)$.

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


# Question
Title: Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?
Consider the following langugage:

$\qquad L = \\{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\\}$.

I've been asked to decide whether this language is in R/RE/CO-RE. I've proved that the language doesn't belong to R and RE using Rice theorem, but I can't find a formal proof for CO-RE. Any suggestions?

# Answer
You can show that this language $L$ is not co-RE in the following way:

Assume $L$ was co-RE, that is you have a semi-algorithm $A$ to decide given an input machine $M$ whether there exists a word $w\in L(M)$ such that $ww\notin L(M)$.

We show that we can build a semi-algorithm to decide the complement of the halting problem (on empty input), which is impossible.

The algorithm goes like this, on input $M$:

1. Build a machine $M'$ that

* simulates $M(\varepsilon)$ on input $00$ and accepts if $M$ halts,
    * accepts on input $0$,
    * and accepts on all other inputs.
2. Run algorithm $A$ on $M'$.

Now $A(M')$ will answer yes iff $M'$ accepts $0$ but rejects $00$, meaning iff $M$ does not halt on empty input. Hence we have constructed an algorithm that semi-decides the complement of the Halting problem, which is a contradiction (it is not possible).
> 3 votes

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


# Question
Title: Three languages and how to decide if they are regular
From following languages which one is regular and why others are not?And what is the regular expression for regular one.

$L\_1= \\{wxwy | x,y,w \in (a+b)^+\\}$

$L\_2 = \\{xwyw | x,y,w \in (a+b)^+\\}$

$L\_3 = \\{wxyw | x,y,w \in (a+b)^+\\}$

Also where can I find these type of problems?

# Answer
> 2 votes
The first two are regular, because they can be written as $aA^\*aA^\*+bA^\*bA^\*$ and $A^\*aA^\*a+A^\*bA^\*b$ (where $A=a+b$). This is because it is enough to check them for $|w|=1$, as it is implied by longer $w$.

The last language is not regular, because its intersection with the regular language $a^+b^+aba^+b^+$ is $\\{a^nb^maba^nb^m| n,m\geq 1\\}$ which is not regular (you can show this by pumping lemma).

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


# Question
Title: If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?
Given two **increasing** functions $f$ and $g$ with values in the **natural numbers**, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C\>0$ and $\forall n\>N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)\>Cg(n)$, for some $C\>0$ and $\forall n\>N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression

# Answer
> 4 votes
Here is a simple counterexample: $$ \begin{align\*} &f(2m) = 2^{2^{4m}} & &g(2m) = 2^{2^{4m+1}} \\ &f(2m+1) = 2^{2^{4m+3}} & &g(2m+1) = 2^{2^{4m+2}} \end{align\*} $$ The first few values (starting at $0$) are $$ f = 2^{2^0}, 2^{2^3}, 2^{2^4}, 2^{2^7}, 2^{2^8}, 2^{2^{11}}, \ldots \\ g = 2^{2^1}, 2^{2^2}, 2^{2^5}, 2^{2^6}, 2^{2^9}, 2^{2^{10}}, \ldots $$ When $n$ is even, $g(n)$ is much larger than $f(n)$. When $n$ is odd, $f(n)$ is much larger than $g(n)$.

Hardy (*Orders of infinity*) showed that if $f,g$ are both *logarithmo-exponential* functions then exactly one of the following holds: $|f| = o(|g|), |f|=\Theta(|g|), |f| = \omega(|g|)$ (here $|f|$ is the norm of $f$, which can be complex-valued). In particular, either $|f| = O(|g|)$ or $|g| = O(|f|)$. Here logarithmo-exponential functions are those that can be formed using the four arithmetic operations and the two functions $\log$ and $\exp$; complex constants can be used, so you can represent, for example $\sin$ (though not $\arcsin$).

# Answer
> 4 votes
If $f = O(g)$, then

$$\exists n\_0. \exists c. \forall n. (n \> n\_0 \rightarrow f(n) \le c g(n))$$

The negation of this statement is

$$\forall n\_0. \forall c. \exists n. (n \> n\_0 \land f(n) \> c g(n))$$

This doesn't match your negation, so I believe your proof is incorrect.

I actually think the statement you're trying to prove is false. Try constructing functions f and g so that f is double g for a while, then g overtakes f and is triple f for a while, the f overtakes g and is quadruple g for a while, etc. Could you show that neither function is O of the other?

Hope this helps!

# Answer
> 2 votes
Here's an explicit construction of $f$ and $g$ such that neither $f=O(g)$ nor $g=O(f)$. To make the calculations slightly easier, I've chosen $g$ to be increasing and $f$ to be nondecreasing (namely, $f$ will be a step function), but one can follow the technique and tweak $f$ so that it's increasing, as well.

First, let $g(n)=n$. Construct $f$ as follows:

1. For $1\le n \< 4$, define $f(n)=2$.
2. For $4\le n \< 36$, define $f(n)=12$.
3. For $36\le n \< 576$, define $f(n)=144$.
4. For $576\le n \< 1440$, define $f(n)=2880$.
5. In general, for the $i$th interval, $\prod\_{k=1}^ik^2\le n \< \prod\_{k=1}^{i+1}k^2$, define $f(n)=(i+1)\prod\_{k=1}^ik^2$.

Now consider the endpoints of these segments in the graph of $f$: At the left endpoint of the $i$th segment, $(x\_i,y\_i)$, it's not difficult to verify that $f(x\_i)=(i+1)x\_i=(i+1)g(x\_i)$ and similarly at the right endpoint, $(x\_{i+1}, y\_i)$, we'll have $f(x\_i)=(1/(i+1))x\_{i+1}$ (well, not quite, since the function jumps there, but the value of the function will be quite close to that value as you approach the right endpoint).

The whole point of this construction is that at $x\_i$ you'll have $f$ take a value that is $i+1$ times that of $g$s value, meaning that you won't be able to find a fixed constant $c\>0$ such that $f(n)\le cg(n)$ eventually, meaning that $f=O(g)$ isn't satisfied. In simple terms, $f$ eventually gets twice as large as $g$, then three times as large, then four times as large, and so on.

In a similar way, $f$ gets half as large as $g$, then a third as large, then a fourth as large, and so on, meaning that we don't have $g=O(f)$ either.

---
Tags: asymptotics, proof-techniques, check-my-answer
---


# Question
Title: ILP and number of variables in constraints
This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation. Most people try to reach the minimum number of constraints/variables, but I couldn't find anything that considers the size of the constraints.

In more concrete terms, I have some maximization problem for which I can make two different formulations $A$ and $B$. Both have $O(n^2)$ variables, $n$ being the size of the input.

Formulation $A$ has $O(n^3)$ constraints, each having a constant number of variables (say each constraint is a summation over four variables).

Formulation $B$ has $O(n^2)$ constraints, but many constraints are of linear size - i.e. they include summations over $O(n)$ variables.

In terms of performance, does $B$ have an advantage over $A$ ?

# Answer
> 3 votes
There are no hard rules for which formulation would be better especially for mixed-integer problems, however

* The time to solve an lp relaxation usually increases with the number of nonzeros in the constraint matrix, but
* Tighter lp relaxations usually reduce the number of lp relaxations that need to be solved.

To take your example, suppose you have a variable $y$ that is 1 only if all variables $x\_0, x\_2, \ldots, x\_{n-1}$ have value 1, and all values are binary. You could write a single constraint $$ny \le \sum\_{i=0}^n x\_i$$

or $n$ constraints $$y \le x\_i, \forall i \in \\{0, \ldots n-1\\}$$

Both sets of constraints will have the same integer-feasible set, but the $n$ constraints have a much smaller continuous-feasible set, so it is *probably* be much faster to solve.

---
Tags: linear-programming, integer-programming
---


# Question
Title: is it possible to minimize pushdown automata?
is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?

# Answer
Unfortunately the problem is not computable. It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.
> 9 votes

# Answer
I answered basically the same question (put more generally) here.

The argument in short: if you could do this, you could decide universality, and a couple of other undecidable properties of PDA/CFG. Hence, by reduction, there can be no such minimizer.
> 7 votes

# Answer
Sorry, minimize in terms of what?

Every PDA has an equivalent one having a single state.
> 4 votes

# Answer
I don't know about minimizing in the way you do with non-pushdown automata, but...

You can convert a CFG to PDA right? And that conversion according to Hopcroft has only one state, which is very minimized dont you think? So, all you have to do, is, convert your PDA to CFG, and then your CFG back to PDA, you'll have a 1-state PDA.
> 2 votes

# Answer
"minimize" typically means "global minimum" but sometimes can refer to a "local minimum" in which case there do exist heuristics ie strategies that can result in some reduction but not consistently find the global minimum. and also some special classes of PDAs can be minimized or "trimmed". "non guaranteed terminating" machine learning optimization algorithms eg genetic algorithms can be employed here also. here are two papers on "visibly push down automata" a subclass. 2 example papers along these lines:
> 1 votes

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


# Question
Title: Overlap between theory and systems fields in CS
I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, reductions to prove NP-Completeness), and algorithm analysis. I am still very interested in Operating Systems, software engineering, and network/information security.

My question is: What would some starting places to look into if I want to find direct overlaps between CS Theory (algorithm design and analysis, complexity theory, information theory, etc) and, OS, or software engineering? I guess I am looking for areas that might have project possibilities that will test and expand my knowledge in both theory and either OS or SE.

For Security the best one I could think of is theory of cryptography, but I am kind of at a loss when it comes to the other two.

# Answer
> 1 votes
I can see a lot of overlap in the field of `Cloud Computing or Distributed Computing` \- being that it relies heavily on process scheduling and parallel processing on the operating systems side and optimization algorithms to both traverse data across multiple nodes (servers) and optimize hardware resources on the network grid. Graph theory and NP issues come up often when trying to reconcile issues concerning "Big Data" within the distributed computing space.

The software engineering CS component arises when developing designs for new operating system based applications like system monitors that help stabilize and secure distributed computing systems.

From this example, one can see much of the overlapping of said disciplines that go into Cloud Computing.

# Answer
> 1 votes
here are some areas touching on OS design that can be very advanced, involve ongoing research, and lead into deep CS theory, some of it applied in the software engineering of the real systems.

* scheduling algorithms, optimization
* multithreading
* computer language design, garbage collection
* fault tolerance/ recovery
* routing algorithms & optimization
* security
* distributed computing, parallel/ supercomputing

for further ideas there are many graduate level course syllabuses on the internet, eg Georgia Tech online master of CS / advanced OSes

---
Tags: complexity-theory, operating-systems, software-engineering
---


# Question
Title: Is Starvation Possible in LOOK Algorithm
The LOOK algorithm (wiki) is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served.

In wiki there is a line which says

> LOOK behaves almost identically to Shortest seek time first (SSTF), but avoids the starvation problem of SSTF.

Is it(LOOK) always successful in avoiding starvation or there might be some order of disk request where it may lead to starvation.

# Answer
The wiki article also says that

> This is because LOOK is biased against the area recently traversed, and heavily favors tracks clustered at the outermost and innermost edges of the platter.

However, I found it confusing.

The reason why LOOK avoids starvation is quite easy: For any request, it will be served within a finite time interval $t$ (since it is submitted): Suppose the number of cylinders in a disk is $N$, then we can set $t = 2N$.
> 0 votes

---
Tags: operating-systems, scheduling
---


title: Particle Swarm Optimization Algorithm

text:
# Question
Title: Particle Swarm Optimization Algorithm
I am studying about Particle Swarm Optimization (PSO) and I was wondering what the user-defined constants in the update equations are for.

First update equations: $v(t) = w\*v(t) + c\_1\*rand\*(x\_{best} - x) + c\_2\*rand\*(g\_{best} - x)$

$w$ is known as the weight/inertial constant. Usually values here are in the interval $(0,1)$. What are $c\_1$ and $c\_2$ for?

Thanks

# Answer
> 0 votes
they are known as the Learning factors: c1 and c2 usually equal to 2. However, other settings were also used in different papers. But usually c1 equals to c2 and ranges from \[0, 4\]

if you need more information about PSO i'd have a quick read of the tutorials at http://www.swarmintelligence.org/tutorials.php

---
Tags: algorithms
---


title: What's the meaning of the name P/poly?

text:
# Question
Title: What's the meaning of the name P/poly?
I understand the normal definitions of the P/poly class, but I'm curious how the name came about.

The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly that would use a quotient. Is 'A/B' defined to be something like "the class of problems that would be solvable as efficiently as those in A when given B amounts of advice"?

If the 'poly' in 'P/poly' refers to the polynomial amount of advice, why is it not 'P/P'? That is, why do we have two different abbreviations for 'polynomial'?

# Answer
Your second intuition is correct, the $poly$ refers to the bound on the advice. The first definition of this class (that I can find) is in Karp & Lipton's "Turing Machines that Take Advice" (pdf), and in particular:

> We are mainly interested in $poly$, the collection of all polynomially-bounded functions... (p. 192)

Of course they don't give the *reasons* for choosing that name, so on the speculative part!

Firstly, it should be clear that $P$ and $poly$, although both derived most immediately from the word *polynomial*, have rather distinct meanings. $P$ as a name refers to *deterministic polynomial time*, and as a class is the set of all problems solvable in such. $poly$ however is a bound on the advice function, not a time-complexity statement.

This is where I speculate that the difference in names stems from; $P$ and $poly$ are quite separate concepts and it would only serve to confuse if we were to write $P/P$ - this notation would suggest some idea of $\bigcup\_{k} DTIME\[n^{k}\]/\bigcup\_{k} DTIME\[n^{k}\]$, which is certainly an incorrect impression to gives, whereas $P/poly$ immediately suggest $P$ which has something polynomial attached to it *but is different to $P$*.
> 9 votes

---
Tags: terminology, complexity-classes
---


# Question
Title: CTL vs LTL - when a formula satisfy a model
I'm trying to understand the difference between LTL and CTL. In particular, i'm trying to understand when a model (a transition system eg. Kripke structure) satisfy a formula. This is my point of view:

* a model satisfy an LTL formula if an only if all its path starting from its initial state satisfy the formula
* a model satisfy a CTL formula if and only if all of its state satisfy the formula. So i have to check that it is valid for all the path (or for some path if there's a E quantifier) starting from each state. -

Is it correct? can someone help me?

# Answer
> 5 votes
For what it concerns LTL, your understanding is almost correct except that there may be more than one initial states in a transition system.

An LTL formula $\varphi$ holds in state $s$ of a transition system $TS$ if all paths starting in $s$ satisfy $\varphi$.

> The transition system $TS$ satisfies an LTL formula $\varphi$ if if all initial paths of $TS$, paths starting in an initial state $s\_0 \in I$, satisfy $\varphi$.

---

For what it concerns CTL, we have

> The transition system $TS$ satisfies an CTL formula $\Phi$ if and only if $\Phi$ holds in *all initial states* of $TS$.

Note that, similar to the case in LTL, we are only concerned with the *initial states* of $TS$ in the semantics of CTL. However, this does *not* imply that you don't need to check other states of $TS$ against a specific CTL formula $\Phi$. This is both $\Phi$-dependent and checking algorithm-dependent.

For example, the well-known checking algorithm (see the lecture note) is a *global* model-checking procedure, meaning that it does check for any state $s$ in $TS$ whether $s \models \Phi$, and not just for the initial states. This is because the algorithm is computing fixed points recursively: The result of $s \models \Phi$ may rely on each of $s' \models \Phi$, where $s' \in \text{Post}(s)$ is a direct successor of $s$ in $TS$.

Furthermore, it also checks for any state $s$ whether $s \models \Phi\_{sub}$, where $\Phi\_{sub}$ is any subformula of $\Phi$, by backward search.

---
Tags: logic, linear-temporal-logic, temporal-logic, computation-tree-logic
---


# Question
Title: Clock skew vs clock offset in the context of clock synchronization network protocols
In the context of clock synchronization among nodes of a network, what is *clock offset* and what is *clock skew*?

Are these terms synonymous or is there a difference between them?

# Answer
> 1 votes
The terms aren't exactly the same, although have some similarities.

* Clock Skew - a skew in the clock signal is referred to a time gap between the expected arrival of the clock to it's actual arrival, the skew can be positive or negative. This might also be called jitter, it may be considered as sort of instability parameter of your system. Skew is measured in time units (i.e. ns, us, etc.) When designing a synchronous system you must make sure that your system doesn't have timing violations due to clock skews.
* Clock Offset - offset of the clock is a delay of a given clock source, it might be known, or unknown. Offset can be measured in time units or phase degree. Many times clock offset is intentional, for instance it's very common for data to be synchronised to falling edge of a clock, in this case, the receiver of the data, might consider the clock to have an offset of 180 degrees.

Another popular case might be receiving data in a certain clock, for instance 100MHz, while your system also has 100MHz clock, the 2 clocks might have a very low jitter rate, but the offset between them is usually unknown, there are components that can compensate and "fix" the offset and synchronise clocks such as PLL's.

Hope it's more clear now.

---
Tags: terminology, distributed-systems, clocks
---


# Question
Title: Quality LISP/Scheme compilers to compete with C/C++
Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin?

In my testing, I've found that the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are **20-50 times slower than equivalent C code**.

The **only outlier is the Stalin compiler**. For simple programs, it produces binaries that are equivalent to C. However, what I find suspicious is that none of the other projects (Bigloo, Chicken, Clozure, etc) have attempted to implement whatever tricks Stalin uses ("whole program optimization", etc).

I'm a huge fan of LISP since the mid 90s and would love to bring it on board so my team can crank out projects in half the time in normally takes using C/C++/.NET/etc, but...the performance issues are a huge roadblock.

I wonder if the lack of quality LISP compilers are due to the fact that no serious time and money has been invested into the subject OR if this simply isn't a feasible task given the current state of compiler technology??

# Answer
As noted in the comments, it isn't very exact to state "the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code", without qualifying how you tested and what you tested.

For **my** use, I find that for many things Gambit and Chicken Scheme are quite close to the equivalent 'C' code in speed, with the current version of Gambit (4.7.3) generally faster than Chicken (4.9.0.1) but **over pre-optimizing** the output 'C' code (making assumptions about the number of available registers - assumes x686 - and forcing the use of stack memory for any extra memory requirements, which decisions should be left to the 'C' compiler as Chicken does, which often eliminates the requirement for extra registers and combines processing steps) so as to prevent the 'C' compiler from doing its own optimizations resulting in very tight small loops being up to about twice as slow as those same tight small loops in 'C' (or Chicken); Chicken just defines as many variables local to a given function as it sees fit (mostly used immutably) and then depends on the compiler to optimize most of those away. Chicken doesn't seem to optimize Continuation Passing Style (CPS) algorithms with multiple forked levels of continuations as well as Gambit and can be up to about eight times slower than Gambit for these, but then one thinks that CPS isn't really formalized for 'C' code at all so...

**EDIT\_ADD:** I have done some more research into the Chicken and Gambit-C Scheme versions and have found the following:

1. Chicken is faster than Gambit for small tight loops for the above reason (depends more on the 'C' compiler for optimizations without doing as much itself and thus takes better advantage of x86-64 extra registers), but also because it doesn't include a "POLL" stack maintenance check inside the loops, whereas Gambit includes the "POLL" check inside the loop. Even when this isn't triggered (the usual case), it will take several CPU clock cycles to determine that nothing is required (about 6 cycles). A future smarter compiler might see that there is no need to do a stack check when inside a tight loop and not doing stack-building operations, doing it just before or after the loop and save this time.
2. Gambit's 'C' macro's do too much work, as said, in precisely defining how the operations should be carried out, especially including fixed stack size operations, and these are likely harder for the 'C' compiler to optimize; using registers more effectively could reduce tight loop time by perhaps 4 cycles, which in combination with the above would put it into the Chicken ballpark.
3. Neither output "read/modify/write" optimizations for say vector operations that are modify in place and don't output code so that the compiler does it. A smarter backend such as LLVM when used with Haskell does this kind of thing. This would reduce register use by one and execution time in using only a single instruction rather than a separate read, computation of the modification, and a write to the same location; this would become just a calculation of the modification (say a bit or), and then a read modify (|=) write single instruction. This might make the speed faster by a cycle or so
4. Both are dynamically typed and process data "tag" bits as part of their data. Neither are smart enough for tight loops to reduce the tags, perform the loop "tag-less", then add the tags back for any results from the loop, nor do they produce code where the 'C' compiler can see to do this although it does combine these operations for some cases. Optimization here could reduce loop times by a couple of CPU cycles or so, depending on the loop.
5. Very tight 'C' loops can take about 3.5 CPU clock cycles per loop on a fast CPU that isn't memory cache access speed throttled (such as AMD Bulldozer, which is about twice as slow); the same loop in Chicken currently takes about 6 cycles and Gambit takes about 16.9 cycles. With all of the optimizations as per the above, there is no reason that these implementations of Scheme couldn't do that, however some work is required:
6. In the case of Gambit, the harder work might be improving the flow analysis to recognize when no "POLL" tests need to be inserted (ie. could this be interrupt driven, although the compiler does allow interrupts to be turned off for some uses?); the easier improvement would be to just implement better register usage (ie. recognize x86-64 registers better rather than the default x686 architecture). For both, better flow analysis to recognize that they can "untag" the data, especially "fixnum", "flonum", and vector, data so these operations aren't necessary inside tight loops and combining read/modify/write instructions. Both of these ends could be accomplished by using a better backend such as LLVM (not a trivial amount of work, but both are already partly there).

Conclusion: Chicken is currently about 50% slower than 'C' on the fastest CPU's (not my Bulldozer, where it is about the same speed due to cache throttling of the 'C' code) and Gambit is about 400% slower (only about 125% slower on my slow Bulldozer). However, future improvements to the compilers could reduce this so that either code is no slower than 'C' or within the margin that the OP specifies.

A more complex language such as Haskell, when using the LLVM backend, paying careful attention to strictness use (not a problem with scheme which is always eager by default), and using appropriate data structures (ST unboxed arrays rather than lists for tight loops; somewhat applicable to Scheme using vectors), runs at about the same speed as 'C' if the LLVM backend is used with full optimizations. If it can do this, so can Scheme with the above compiler improvements.

**AGAIN, there is no way that either of these is 20 to 50 times as slow when used with proper optimization flags. END\_EDIT\_ADD**

Of course, all benchmarks are invalidated if one does not use the appropriate optimization settings for each as one would in a production environment...

I would think that the commercial Chez Scheme compiler would be in the ballpark as to producing high performance output as do Gambit and Chicken, as being commercial it surely has some "serious time and money invested into it".

The only way I can get Gambit or Chicken to run as slow as "20 to 50 times slower than 'C'" is to not use any optimization settings, in which case they often don't run much faster than as interpreted in their REPL's - 10's of times slower than as properly using those settings.

Is it possible that the OP hasn't tested using these settings properly?

If the OP cares to clarify his testing procedures, I will gladly edit this answer to show that at least Gambit and Chicken don't have to be that slow.
> 7 votes

---
Tags: optimization, compilers
---


title: IS and matching

text:
# Question
Title: IS and matching
I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why.

First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n AND an independent set of size n?

Second problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n OR an independent set of size n?

The AND problem is in NP and the OR problem is in L. Can someone explain why? Thanks.

# Answer
Note that both problems are in NP. It's just that the first is also NP-hard, and the second is also in L.

Hint for the first problem: Prove that it's NP-hard by reduction from independent set. Given a graph $G=(V,E)$ and a parameter $k \leq |V|$, add an independent set of size $|V|-k$ and a clique of size $|V|^2-|V| \geq 2|V|$ (the case $|V| \< 3$ has to be handled separately), and connect all vertices of the clique to all other vertices.

Hint for the second problem: Suppose that $G$ doesn't have an independent set of size $n$. Show that it has a matching of size $n$ by dividing the $n^2$ vertices into $n$ sets of $n$ vertices, and picking an edge from each.
> 1 votes

---
Tags: complexity-theory, time-complexity, space-complexity, np
---


# Question
Title: Filling a matrix with the sum of conditional values
I have $P$ vectors of size $N$ with elements in $\\{0,1\\}$. Each vector $v$ has a value $\alpha\_v$.

I would like to Fill a square matrix $M$ of size $N\times N$ in the following way:

$$\forall i,j \in \\{1,2,...,N\\}~ M\_{i,j} = \sum\_{\text{vectors}~v : v\_i v\_j =1} \alpha\_v$$

Is it possible to fill the matrix $M$ in time complexity better than $O(P\cdot N^2)$?

Assuming that each vector has at most $Q$ elements equal to $1$, is it possible to do better than $O(P\cdot(N+Q^2))$ ?

# Answer
Let $V$ be the $N\times P$ matrix whose columns are the vectors $v$, and let $D$ be the $P\times P$ diagonal matrix with elements $D\_{vv} = \alpha\_v$. Then you want to compute $VDV^T$. Computing $U = DV^T$ takes time $NP$, and it remains to compute $VU$. When $P \< N^{0.3029}$, for every $\epsilon \> 0$ there is an (impractical) algorithm to compute this product in time $O\_\epsilon(N^{2+\epsilon})$. See Le Gall, who improved on an earlier result of Coppersmith.
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Union of finite and non-regular language
**Question:** ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular:

Prove/Disprove: $C\cup B$ isn't regular.

**Thoughts:** My intuition says this is true, but I need an idea to prove it. Since I don't know if $C$ as a CFG or RE language I don't know what kind of machine I can build for it.

# Answer
Hint 1: Try to prove the contrapositive, namely: if $C\cup B$ is regular and $B$ is finite, then $C$ is regular.

Hint 2: Use closure properties of regular languages.
> 5 votes

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


title: SAT-3CNF - Clique

text:
# Question
Title: SAT-3CNF - Clique
Could someone show me ( or give me a valuable hint) how to reduce k-Clique problem to SAT-3CNF problem ? I am able to prove reduction from SAT-3CNF to k-Clique, but in the opposite direction it's hard.

# Answer
Here's your hint: write down a Boolean formula $\varphi$ (it doesn't have to be in 3CNF) that expresses the condition that your graph contains a $k$-clique.
> 0 votes

---
Tags: np-complete, reductions
---


# Question
Title: Turing machines with a finite number of states
In a class on Turing machines, the lecturer said that the language for a machine with 100 states is both recognizable and decidable.

How can we infer this just from the number of states in the machine?

# Answer
You misunderstood your lecturer's claim. Their claim was that the language of *descriptions* of Turing machines with 100 states is decidable. The language *accepted* by each such machine need not be.

In other words, given a string, you can decide whether it describes a Turing machine having 100 states. That's the extent of the claim.
> 3 votes

---
Tags: automata
---


# Question
Title: How to compute time complexity of a program if the time complexity of a function called inside a loop is known?
This is the question-

> Let $A\[1,....,n\]$ ba an array storing a bit $(1\\,\\,or\\,\\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program -

```
counter = 0;
for( i = 1; i <= n; i++)
{
    if(A[i] == 1)
        counter++;
    else
    {
        f(counter);
        counter = 0;
    }
}

```

> Options are :
> (A)$\Omega(n^2)$
> (B)$\Omega(n\log n)$ and $O(n^2)$
> (C)$\Theta(n)$
> (D)$\mathcal{O}(n)$

The solution says - "Since it contains only one loop, so compute with linear complexity, hence the complexity will be $\Theta(n)$".
My doubt is, what if the time complexity of the function $f(m)$ was given to be $\theta(2^n)$ or of the order that grows in exponential time? Would the solution given in the book be correct in case of exponential time?

# Answer
> 1 votes
This is actually an example of amortized analysis. The easiest way to see what's going on is to separate $A$ as follows: $A=1^{n\_1}01^{n\_2}0\cdots1^{n\_k}$. You can check that the function $f$ is called with arguments $n\_1,n\_2,\ldots,n\_{k-1}$. Since $n\_1+\cdots+n\_k = n-(k-1)$, in particular $n\_1+\cdots+n\_{k-1} \leq n$, and so the total time spent running $f$ is $O(n\_1+\cdots+n\_{k-1}) = O(n)$. The time spent on executing the rest of the program is $\Theta(n)$, and so the total running time is $\Theta(n)$.

If we did want to use amortized analysis, the idea would be as follows. Suppose for simplicity that $f(m)$ runs in time $m$ (exactly). Each time the counter is incremented, we set aside another "time unit", and withdraw the time units set aside when $f$ is called. You can check that we always have enough time units in store. Under this scheme of accounting, incrementing the counter takes time $O(1)$, and calling $f(m)$ takes no time; this can only overestimate the actual running time (since we might have leftover time units). Therefore the total running time is $O(n)$.

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


title: Reduce Clique to Vertex Cover

text:
# Question
Title: Reduce Clique to Vertex Cover
I read on the internet that it's possible to reduce *clique* to *vertex cover*. Almost everyone use this theorem:

> if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of size $n-k$, where $n$ is the number of vertices.

Consider the graph on five vertices and the following edges: a clique on $\\{1,2,3,4\\}$ and $(1,5),(2,5),(3,5)$. The complement of this graph has only one edge, and it does *not* cover the set of vertices.

Is the statement I quoted correct?

# Answer
> 1 votes
You're misunderstanding what Vertex Cover is: the task is to find a set of *vertices* which "cover" or "touch" all edges. Each of the vertices $4,5$ covers the unique edge $(4,5)$ in the complement of your graph.

The theorem states that the size of the maximum clique in a graph equals the size of a minimum vertex cover in its complement. This is because a set $A$ of vertices is a clique in a graph $G$ if and only if its complement $\overline{A}$ is a vertex cover in the complement graph $\overline{G}$.

Indeed, $A$ is a clique in $G$ if any two $x,y \in A$ are connected in $G$; $\overline{A}$ is a vertex cover in $\overline{G}$ if for every edge $(x,y) \in \overline{G}$, one of $x,y$ is in $\overline{A}$. So $\overline{A}$ is *not* a vertex cover in $\overline{G}$ if there exists an edge $(x,y) \in \overline{G}$ such that $x,y \notin \overline{A}$, i.e. if for some $x,y \in A$, $(x,y) \notin G$; this is exactly the condition that $A$ is *not* a clique in $G$.

---
Tags: np-complete, reductions
---


# Question
Title: How do I calculate response time of a multiple core cpu when given certain information?
On my homework the question asks:

> A program executes serially in 200 seconds. If it is parallelized, 7 seconds of overhead are required for synchronization, locking, and communication. Compute the execution time, ideal speedup (if there were no overhead required), actual speedup, and the percentage of the ideal speedup that is obtained for 1, 2, 4, 8, 16, 32, 64, and 128 processors.

How do I calculate the answer to this? It is not something that has been covered in class yet and the homework is due before the next time the class meets.

My guess is that I divide 200 seconds by the number of cores and then add 7 * # cores to get the total response time. I don't think it is that simple.

Edit:
Amdahl's law says: T(n) = T(1)\[B + 1/n(1-B)\] where B is the percentage of the algorithm that is not parallelized and n is the number of cores. If I assume that the 7 seconds mentioned is the part of the algorithm that is not parallelized, I can get the percentage by saying:

```
      7sec * n
B  =  --------
       200sec

```

Then I plug the value for B into Amdahl's equation. Coencidentally, this gives me the same answers as I got before when I did my own formula:

```
 200
 ---  +  [7 * (n - 1)]
  n

```

After doing a little bit of algebra, I discovered that my formula is a simplified version of Amdahl's formula. Of course all of this assumes I am correct when I read the question as if the 7 seconds are the part of the algorithm that is not parallelized.

Thanks for looking,

Zach

# Answer
I think you don't need to add (7\*number of cores) to the total response time. The overall execution time requires just 7 more seconds, because each piece of code is running in parallel with others. So just divide 200 by the number of cores and add 7 to it. Obviously in the ideal case you don't need to add anything. Also look at the Amdahl's law in the Wikipedia... It also states a law about speedup with parallelism and these problems share the same concept.
> 1 votes

# Answer
I guess this type of optimization is calculate based on SpeedUp measurement.
> 0 votes

---
Tags: computer-architecture, parallel-computing
---


title: Computing modular exponent given order

text:
# Question
Title: Computing modular exponent given order
I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m\<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of computing $g^{mn}$ directly.

My question stems from an implementation of the Paillier cryptosystem that I'm working on. Right now, I'm following the original paper "Public-key cryptosystems based on composite degree residuosity classes", scheme 3 with the recommendation of generating $g$ using DSA. I have looked at different methods of computing modular exponentiation directly such as square and multiply, k-ary, window sliding, etc. I want an algorithm for computing $g^{mn} \bmod n^2$ that does not rely upon knowledge of the factorization of $n$.

# Answer
There's a small chance you might be able to get a speed-up by using properties of arithmetic modulo $n^2$, depending on how $g$ was chosen.

Suppose $g=a(1+bn)$. Then note that, by the binomial theorem,

$$g^x = a^x (1+bn)^x = a^x \sum\_i {x \choose i} (bn)^i = a^x (1 + bx n + n^2 \times \text{stuff})$$

so we see that

$$g^x = a^x (1 + bx n) \pmod{n^2}$$

Thus if you can compute $a^x \bmod n^2$ efficiently, you can compute $g^x \bmod n^2$ with just a tiny bit more work. Here you want to take $x=mn$. The simplification is that now $g$ can always be expressed in the form $g=a(1+bn)$ where $0 \le a \< n$.

What can we say about $a$? Well, for one thing we know that $g^{kn}=1 \pmod{n^2}$, so it follows that $a^{kn}=1 \pmod{n^2}$. Thus, the order of $a$ modulo $n^2$ has to be a divisor of $kn$.

If the order of $a$ is exactly $kn$, we haven't gotten anywhere.

But if the order of $a$ is a strict divisor of $kn$, we can get some speedup. We first reduce $mn$ modulo the order of $a$, then compute $a^{mn} \bmod n^2$, and finally use the relationship above to get the value of $g^{mn} \bmod n^2$. (For instance, if you get lucky, it is possible that the order of $a$ might be $k$, and then you'll get a non-trivial speedup.)

Whether this yields a speedup in practice will depend on the value of $g$ and how $g$ was chosen; since that wasn't specified in your question, it's not possible to evaluate whether this is likely to help in practice, but it might.
> 5 votes

---
Tags: algorithms, cryptography, modular-arithmetic
---


title: Nested Big O-notation

text:
# Question
Title: Nested Big O-notation
Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$.

It feels natural to write that the running time on this graph would be $O(O(V^2)+V)$ and then simplify to $O(V^2)$.

Are there any pitfalls to using such a "remove-the-nested-O" shortcut (not just in this case, but more generally)?

# Answer
Let me start of with a recommendation: treat Landau notation just as you (should) treat rounding: round rarely, round late. If you know something more precise than $O(.)$, use it until you are done with all calculations, and Landauify at the end.

---

As for the question, let's dig through this abuse of notation¹. How would we interpret something like $h \in O(f + O(g))$? We should replace $O$ with its definition from the inside out. So, we get

$\qquad \displaystyle \exists g' \in O(g).\\, h \in O(f + g')$

and then

$\qquad \displaystyle \exists g' \in O(g).\\,\exists d\>0.\\, \forall n.\\, h(n) \leq d(f(n) + g'(n))$

which is equivalent to

$\qquad \displaystyle \exists c \> 0.\\,\exists d\>0.\\, \forall n.\\, h(n) \leq d(f(n) + cg(n))$.

As certainly² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, we see that this is equivalent to $h \in O(f + g)$; the loss of precision is ignored by $O$ anyway.

---

What about other combinations, say $h \in O(f + \Omega(g))$? If we try the same here, we get

$\qquad \displaystyle \exists g' \in \Omega(g).\\, h \in O(f + g')$.

But this is a tautology: $h$ is certainly bounded above by something arbitrarily large. So, combining upper and lower bounds in this fashion is not meaningful.

---

1. $O(.)$ and the other Landau symbols map functions to function classes. Feeding it a function class is not immediately meaningful.
2. At least if we consider only positive functions, which we can safely assume when talking about runtimes. I'm not sure this works in general.
> 14 votes

# Answer
I just wanted to add this because I recently encountered it. While this shortcut is fine with addition and multiplication (when not mixing $O$ with $\Omega$; see the accepted answer), care must be taken when using exponents. For instance: $$O(n^{O(m)}) \not= O(n^m).$$ In this example, $n^{2m}$ belongs to the first class but not to the second.
> 3 votes

# Answer
By definition, $O(g)$ is a set and if you use this notation nested, you would have a set in a set, which would be wrong.

### The definition of the O-Notation

$O(g) = \left \lbrace f|\exists c \> 0\exists x\_0\>0 \forall x \> x\_0: |f(x)| \leq c \*|g(x)|\right \rbrace $

### The mistake

You used terms like $ O(O(n)+k)$ where k and n are functions and $O(n)$ is a set. But what is the result of a function added to a set? It is not defined!

### Correct version

Instead of using the Landau-Symbols nested, you can do the following: $O(m+k),m \in O(n)$
> 1 votes

# Answer
In Section 9.3 "$O$ Manipulation" of the book *Concrete Mathematics* (Second Edition), Knuth has listed some *rules* of manipulation on the $O$-notation (In the following, I assume that both $f(n)$ and $g(n)$ are positive; notice that the ordering of rules has been changed).

\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}

By (3), you can wrap/unwrap a function $f(n)$ with an O-notation. Then by (5), you can actually wrap/unwrap (or called, *nest*) it arbitrarily finite times. Using (4), you can also add/remove constant multiplication factors to/from $O$.

Then, (2) and (6) allow you to manipulate *nested* $O$-notations in the way compatible with $+$ and $\times$.
> 0 votes

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


# Question
Title: Reducing optimization problem to decision problem
I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version:
Given $(G=(V,E),k)$ as input, where $G$ is an undirected weighted graph (all weights are positive integers, formally: $w: E\rightarrow \mathbb{N}$ is the weight function) and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V\_1,V\_2)$, s.t its weight is at least $k$, meaning $k\leq \sum \_{u\in V\_1, v\in V\_2}w(u,v)$.
The optimization version is simply **finding** the maximum weighted cut.
What I'm trying to achieve is, given an algorithm $A$ that can solve the decision problem, I want to describe an algorithm that can **find** the maximum cut in $G$.
So, first of all, this is what I had in mind:

* Find the weight of the maximum cut in $G$ (this can be done with a simple for loop that starts with 1 and stops at $m$, where $m=\sum \_{e\in E}w(e)$ while in each iteration the algorithm queries $A$), define $k$ to be the weight of the maximum cut.
* Initialize new set $S\leftarrow \phi$
* For $e\in E$ do:
    + Omit edge $e=(u,v)$ from $G$, to create new graph $G\_e$.
    + If $A(G\_e,k)=0$ (both ends of $e$ are at the same set), $S\leftarrow S\cup \left \\{ u,v \right \\}$
    + else if $A(G\_e,k)=1$ then...(?)
    This is where I'm stuck, I'm not sure how can I tell which end of $e$ should be in $S$...
    In fact, I'm not even sure if this is the right way to do it.

Any help and thoughts will be appreciated.

# Answer
> 2 votes
Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x\_u,x\_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x\_u,x\_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x\_u,x\_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in linear time (linear in the number of edges) to determine membership in set $S$. For example, if $(x\_u,x\_v) = (0, 0)$ or $(1,1)$ then you would add the two clauses $(x\_u \vee \neg x\_v) \wedge (\neg x\_u \vee x\_v)$ to your 2-sat formula.

# Answer
> 0 votes
After finding the set of edges which has no effect on the maxcut. remove the edges from the graph by making its cost 0. The remaining graph will be bipartite. we can use 2 color algorithm to get the bipartite sets.

This might be one of simple solution.

---
Tags: reductions
---


# Question
Title: Show this is a tautology without using a truth table
I am doing a homework assignment and I've been stuck on this question for a long time now. The question says to prove this equation is a tautology without using a truth table. I assume we have to use equivalences to do this but I can't figure out how to do this.

The equation is:

```
[⌐p AND (p OR q)] → q

```

Please help me!!

EDIT: The equivalences I know are associative, distributive, DeMorgan, absorption, negation, contraposition, implication elimination, and biconditional elimination. I can use ANY equivalence as long as I can show how I got it.

# Answer
You can work with the axiomatic system(I guess this is the name in english, not north-american natural here).

When you have 'something $\rightarrow$ anotherthing', you can separate then and think like this:

You have this hypothesis: $¬p \ and \ (p\ or\ q)$

And you can use some rules to derivate $q$ from that.

The main rule you want to use is called $modus\ ponens$, this rules says that, if you have a $p$ and a $p \rightarrow q$, then that is the same as $q$.

Another useful rule is $modus\ tollens$, this rule says, if you have $p \rightarrow q\ and\ ¬q$, then that is the same as $¬p$.

You can use also some equivalences, like, $p\ or\ q$, is the same of $¬p \rightarrow q$(just do the truth table and you'll see that is true), so, there are also alot of others equivalences and rules, but you'll see that at the right time, for now, those are enough to solve your problem.

Back to your problem: $¬p\ and\ (p\ or\ q) \rightarrow q$:

Do the following transformations:

1. $\[¬p\ and\ (¬p \rightarrow q)\]$ (equivalence from 'or' to '-\>' in the second term)
2. $Modus\ Ponens$ applied over $\[¬p\ and\ (¬p \rightarrow q)\]$ gives you $q$, because the rules says, if you have a $p\ and\ p\rightarrow q$ that is the same as $q$
3. then you transformed $\[¬p\ and\ (¬p \rightarrow q)\]$ to $q$

Now you have $q \rightarrow q$, and that, is for sure, a tautology.

In step 2, I applied $Modus\ Ponens$ over $¬p$ instead of $p$, and I can do that, because if you look very carefully, the $p$ from the rule is different from your $p$, so, in other means, I can call your $¬p$ of a new name, like, $a$, and substitute in the rule and get $\[a\ and\ (a \rightarrow q)\]$, and that is exactly in the format the $modus\ ponens$ rule says.

I know, that can be alot of things to assimilate now, but once you finish your logic class, this will be natural to you!

Any further doubts, just ask!
> 1 votes

# Answer
Prerequisites:

(p → q) is equivalent to (⌐p + q)
AND is '.'
OR is '+'

```
  [⌐p AND (p OR q)] → q

  => (⌐p.p) + (⌐p.q) → q (Using distributive law)
  => (⌐p.q) → q
  => ⌐(⌐p.q) + q
  => p + ⌐q + q          (Using De-morgan's law)
  => p + 1
  => 1

```
> 0 votes

---
Tags: logic, assignment-problem
---


title: Merge Sort proof

text:
# Question
Title: Merge Sort proof
I am trying to prove that merge sort is indeed $O(n \log n)$.

I was able to extract a pattern using constants, however now I am stuck. This is as far as I can get:

1. $T(n) = 2T(n/2) + cn$
2. $T(n/2) = 2T(n/4) + c(n/2)$

Now plug in 1. into 2.

3. $T(n) = 2(2T(n/4) + c(n/2)) + cn$
4. $T(n) = 4T(n/4) + 2cn$

Now the pattern I was able to find is the following:

5. $2^kT(n/2^k) + kcn$

Is there a way to use this pattern to prove that merge sort has complexity of $O(n\log n)$?

# Answer
> 4 votes
You correctly figured out that after unrolling the recursive equation $$T(n) = 2 \cdot T(n/2) + c n$$ $k$-times you get $$T(n) = 2^k \cdot T(n/2^k) + k c n.$$ To finish your proof, ask yourself when the unrolling process will stop. The answer: when we reach the base case, which is $T(1) = d$ where $d$ is a constant. For what value of $k$ do we reach $T(1)$? For this we need to solve the equation $$n/2^k = 1$$ whose solution is $k = \log\_2 n$. So now we plug in $k = \log\_2 n$: \begin{align\*} T(n) &= 2^{\log\_2 n} \cdot T(n/2^{\log\_2 n}) + c \cdot n \cdot \log\_2 n \\ &= n \cdot T(1) + c \cdot n \cdot \log\_2 n \\ &= d \cdot n + c \cdot n \cdot \log\_2 n \\ &\in O(n \cdot log\_2 n). \end{align\*}

---
Tags: asymptotics, recurrence-relation
---


title: Parallel algorithm for LU-decomposition

text:
# Question
Title: Parallel algorithm for LU-decomposition
I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets.

So, could you, please, recommend me some parallel algorithms for LU-decomposition which are really easy to understand and implement? The low difficulty of the implementation has the highest priority for me, because I'm not very familiar with Kaira and I'm in hurry a little.

I looked at a Fined-grained LU-factorization, but I'm curious if some other algorithms are used.

# Answer
Finally I've found some decriptions of these algorithms here.
> 0 votes

---
Tags: parallel-computing, matrices, decomposition
---


title: Big Omega Counterexample?

text:
# Question
Title: Big Omega Counterexample?
I am doing homework to practice for my midterm exam and cannot answer this question. I need to decide whether or not this statement is true of false and either give a proof or counter example.

For this particular question, I am leaning more towards saying it is false as the question does not really follow the definition of Big Omega. However, how do I come up with a counterexample for this? Can anyone show me how to do this question?

> Let $g$ and $h$ be any functions from $\mathbb{N}$ to $(0,\infty)$. Then $g(n)\in\Omega(h(n))$ implies there is some $N\in\mathbb{N}$ such that $g(n)\geq h(n)$ for all $n\geq N$.

Any help would be much appreciated.

# Answer
> 2 votes
The definition of $\Omega$ says that $g$ and $h$ might differ additively or multiplicatively by any constant. So a counter example could be:

$g(n) = n$

$h(n) = 2n$

$\lim\limits\_{n \rightarrow \infty} \frac{g(n)}{h(n)} = \frac{1}{2} \> 0$, hence $g \in \Omega(h)$. But obviously, $h(n) \> g(n)$ for all $n \> 0$.

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


# Question
Title: Contradiction between best-case running time of insertion sort and $n\log n$ lower bound?
If the best case for Insertion sort & bubble sort is $O(n)$ then how is lower bound for any comparison sort is $\Omega(n\log n)$? I mean, $O(n)$ is obviously smaller than $\Omega(nlogn)$. What am I missing here?

# Answer
The lower bound of $\Omega(n \log(n))$ is a lower bound for the worst-case behavior of a sorting method. Both insertion sort and bubble sort have $O(n^2)$ worst-case complexity.
> 5 votes

# Answer
Given an algorithm $A$, we often consider its *worst-case* time complexity $T(A)$ over all possible inputs $I$: $$T(A) = \max\_{I} T(A,I)$$ where, $T(A,I)$ is the time for the algorithm $A$ executed on this particular input $I$.

For a problem $P$, we may have several algorithms $A$ for it. The time complexity (or lower bound) of a problem $T(P)$ is defined with respect to its *best* algorithms.

$$T(P) = \min\_{A} T(A) = \min\_{A} \max\_{I} T(A,I)$$

---

For sorting problem, its lower bound (comparison-based) is $\Omega(n \lg n)$. Both $\texttt{Insertion-Sort}$ and $\texttt{Bubble-Sort}$ have *worst-case* time complexity of $\Theta(n^2)$, and thus do not match the lower bound. In contrary, both $\texttt{Merge-Sort}$ and $\texttt{Heap-Sort}$ have *worst-case* time complexity of $\Theta(n \lg n)$, matching the lower bound.
> 1 votes

---
Tags: time-complexity
---


title: Understanding Regular Grammers

text:
# Question
Title: Understanding Regular Grammers
I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with other like in $$a^nb^n|n\geq 0 (CFG)$$ It'll be regular. Like AP Series of symbols can be easily expressed as Regular expression but GP Series can not.

But I failed to understand why the following languages are regular

> $L\_1=\\{wxw^R \mid w,x \in (a,b)^+\\}$
>
> $L\_2=\\{wxwy \mid w,x,y \in (a,b)^+\\}$
>
> $L\_3=\\{xwyw \mid w,x,y \in (a,b)^+\\}$

# Answer
All these languages are regular. This comes from the fact $w$ could simply be a single letter, and thus the languages admit the following regular expressions (assuming here $\Sigma=\\{a,b\\}$, but this would work for any finite alphabet):

$$L\_1=a(a+b)^+a+b(a+b)^+b$$ $$L\_2=a(a+b)^+a(a+b)^++b(a+b)^+b(a+b)^+$$ $$L\_2=(a+b)^+a(a+b)^+a+(a+b)^+b(a+b)^+b$$

---

A more detailed explanation:

In the definition we had: $w\in\\{a,b\\}^+$.

This mean that $w$ could be a single letter, $a$, or $b$, and thus we can attribute the rest of the word to $x$ (or $y$).

For example, if: $$u=abbababa\in L\_1$$, because it can be decomposed as $w=a, x=bbabab$ and $$u=wxw^R$$. Similarly, each word which starts and ends with a $a$ is in $L\_1$ (pick $w=a$), and each word that starts and ends with a $b$ is also in $L\_1$ (pick $w=b$). This is why $$L\_1=\\{axa|x\in\\{a,b\\}^+\\}\cup\\{bxb|x\in\\{a,b\\}^+\\}$$, and thus regular. Same tricks apply to the other languages and all three are indeed regular (by the regex I gave).
> 0 votes

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


# Question
Title: Why is non-determinism a useful concept?
An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state.

When we are trying to model real systems, why include nondeterminism in Automata theory?

# Answer
Yes, you are correct computers are deterministic automate. Non-deterministic models are more useful for theoretical purpose, sometime the deterministic solution is not as obvious to the definition(or say problem statement) and so little hard to find solution. Then one approach is that first design a non-deterministic model that may be comparatively easy to design and then try to convert it into a deterministic one. Below, I have tried to demonstrate what I mean with an example. Consider regular expression:

```
(01)*01(0 + 1)*

```

Now suppose, if you are asked to draw DFA for the language generated by above RE.

With my knowledge of designing FAs, I know that **(1)** when a `*` present in regular expression indicated I need corresponding loop in FA **(2)** concatenate operations like `a.b` means something like: `(q<sub>0</sub>)─a→(q<sub>1</sub>)─b→(q<sub>2</sub>)`.

So, at my fist attempt I would draw an NFA like:

Thought this is *not* a deterministic solution but looks very simple FA that can be easily designed using the given regular expression. My kind-of-analogy to show similarity between the above regular expression and my NFA is as below:

1. The loop at state q0 should be for `(01)*`
2. `01` (after `(01)*`) gives `(q<sub>0</sub>)─0→(q<sub>1</sub>)─1→(q<sub>2</sub>)`
3. `(0 + 1)*` gives a self loop at state q2 for label 0, 1

According to my analogy I think the FA I drawn above is comparatively simple to draw from given RE. And luckily in class of finite automata every Non-deterministic model can be converted into an equivalent deterministic one. We have algorithmic method to convert an NFA into DFA. So I can easily convert above NFA into a DFA:

Other part is unfortunately this is not always possible to convert a non-deterministic model into deterministic one, for example class for deterministic push down automate is subset of class of deterministic push-down automate "check venn diagram" and you can't always convert an NPDA into a PDA.

Usually when it is not possible to convert a non-deterministic solution into deterministic one then with the help of non-deterministic solution we define deterministic solution in sub-domain (or say partial domain) instead of complete domain. Or we define solution in some other ways (e.g. greedy approach) that of-course may not give you an optimal solution.

Sometimes non-determinism is an effective mechanism for describing some complicated problem/solution precisely and effectively, for an example non-deterministic machines can serve as model of search-and-backtrack algorithm (read: How string process in non-deterministic model using backtrack). Oppositely deterministic models better represents efficient, minimized and less-redundant solutions.

Here I would also like to quote from Wikipedia Use of Nondeterministic algorithm:

> In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.
>
> A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.

As @keshlam also mentioned in his comment: "Nondeterminism" is in practice **used to** refer to any unpredictability in the outcome of some process. For an example, Concurrent programs exhibit non-deterministic behaviour - two executions of the same program with the same input can produce different results (if concurrency control mechanism are not applied ). Read more about this in "Usefulness Of Non Determinism".

I would also suggest you to read following links:
1. What is the difference between non-determinism and randomness?
2. 9.2.2 Nondeterministic vs. Probabilistic Models: (a). **Nondeterministic:** I have no idea what nature will do. (b). **Probabilistic:** I have been observing nature and gathering statistics.
3. Nondeterministic programming
> 19 votes

# Answer
It is more the other way around: automata arose first, as mathematical models. And nondeterminism is quite natural, you often have several paths open before you. Instead of some messy way of specifying that all paths must be followed to the end in some order, and perhaps getting bogged down by infinite branches, and... just use nondeterminism.

And while nondeterministic programming languages aren't mainstream, they have an ilustrious history, perhaps starting with Dijkstra's GCL. As machines acrue more and more cores (independent processors), some form of nondeterminism is seeping into all programming.
> 9 votes

# Answer
NFAs might be used in practice, check out this answer on stackexchange. The reason is that the powerset construction can be simulated on-the-fly, so to speak. In order to simulate an NFA on a deterministic computer, we just keep track of the *possible* states that the NFA could be in. Typically, this number would be small, and so the simulation would be fast. This is much more practical than running the actual powerset construction: the resulting automaton could be very large, even though in practice most of the sets would rarely be reached.

Nondeterminism is also important for computation complexity, where it is used for defining the class NP. (The class NP also has other, equivalent definitions, for example using witnesses.)
> 7 votes

# Answer
(This is a rewording of some of the other answers but I'll post it anyway:)

You write: *An automaton is an abstract model of a digital computer.*

I disagree! Automata model how we humans specify computation, not only how computers execute it. Nondeterminism is exactly the difference. Our specifications are often nondeterministic.

For instance, take merge sort. Merge sort is sorting by splitting the items to be sorted into two halves of roughly equal size, sorting each half using merge sort, and merging the sorted results. This completely specifies the idea of merge sort, but it isn't deterministic: it doesn't specify an order in which to sort the halves (for all we care, it may be done concurrently), nor does it specify an exact way to determine the split. Those details will need to be filled in in order to arrive at a deterministic, sequential version of merge sort that can be implemented by a single-threaded computer program, but I would say they are part of a particular way of doing merge sort, not the idea of merge sort itself.

The same thing is true for algorithms in general - e.g. cookbook recipes. Some people *define* algorithms to be deterministic, in which case this more general and in my opinion more natural notion of 'algorithm' needs a different name.

The idea of working with nondeterministic specifications was formalized by Dijkstra's method of programming, which starts out by specifications that only give pre- and postconditions to be met by the program, and systematically develops a deterministic, imperative program from them. Dijkstra would probably have said: *sorting* is the problem, the relationship between pre- and postconditions we're trying to establish; *merge sort* is an approach to doing that, somewhere halfway between the problem specification and a deterministic solution; a particular, deterministic merge sorting algorithm is a concrete deterministic solution. But the same general approach can be used for developing concurrent programs, in which the eventual program is still nondeterministic. Such programs can e.g. be run in distributed computing environments.
> 5 votes

# Answer
You state correctly that automata are models, so there are two parts of use non-determinism can have:

1. **Use in modelling real problems.**

Not all automata are equally powerful if you remove nondeterminism, e.g. pushdown automata (CFL $\neq$ DCFL). So while we will have to simulate an NPDA in a deterministic fashion in the end, i.e. when we actually implement a parser, we *need* it as model for some languages.

Furthermore, non-deterministic automata can provide more compact representations of languages. For example, it is well-known that there are NFA whose minimal equivalent DFA are exponentially larger.
2. **Use in theory.**

Using non-determinism can simplify proofs, see e.g. converting regular expressions into finite automata.
> 4 votes

# Answer
You are right, we can NOT build a nondeterministic machine. Therefore, the aim is not using the concept for building better machines. Rather, nondeterminism is a useful concept when trying to understand computation. For instance, we now know that, from a computability perspective, nondeterminism is not something more powerful than determinism, meaning that we can simulate a nondeterministic machine by using a deterministic one. However, from the complexity perspective, nondeterminism allows us, for instance, to reason and try to understand the relation among the difficulty of finding an efficient solution for a problem and the difficulty of verifying a solution (which is the famous P versus NP problem). And so on. Therefore, the main reason for studying nondeterminism is theoretical.
> 2 votes

# Answer
the invention of the Turing Machine was in 1936 by Turing. FSM-like models were introduced by McCulloch and Pitts, two neurophysiologists, as a model for neurobiological activity in 1943. from the Stanford CS history page:

> The exciting history of how finite automata became a branch of computer science illustrates its wide range of applications. The first people to consider the concept of a finite-state machine included a team of biologists, psychologists, mathematicians, engineers and some of the first computer scientists. They all shared a common interest: to model the human thought process, whether in the brain or in a computer. Warren McCulloch and Walter Pitts, two neurophysiologists, were the first to present a description of finite automata in 1943. Their paper, entitled, "A Logical Calculus Immanent in Nervous Activity", made significant contributions to the study of neural network theory, theory of automata, the theory of computation and cybernetics. Later, two computer scientists, G.H. Mealy and E.F. Moore, generalized the theory to much more powerful machines in separate papers, published in 1955-56. The finite-state machines, the Mealy machine and the Moore machine, are named in recognition of their work.

not a CS historian, but suspect that the McCulloch-Pitts model did not include nondeterminism and the Mealy-Moore model did, in a natural generalizing/abstraction of the formal/theoretical concept. note that DFAs and NFAs have the same representational power so that if one wishes to model real systems there is a choice of either. one basic difference is that an NFA may be much *smaller* than an equivalent DFA (so for example there is a natural element of data/information compression). there are also natural aspects/analogs of parallelism in NFA study.
> 2 votes

# Answer
First of all I would like to say thanks to all the people who answered the question.All the answers are important and add some useful information.But as it is a tricky question to the beginners, and need sufficient time to understanding it well, I would try to summarize what I have gained from all the answers and from some books:

Actually I had a confusion which was about the mechanism of nondeterministic model. I always wondered about the nondeterministic machine as it is a non-mechanical machine which does not exist in real world. I always compared Automata with our now days computers which is completely deterministic in nature.Actually I wasn't properly understanding the nondeterministic model. Now I think I am understanding nonderministic model quite well: A nondeterministic machine is a machine which always follow that path of execution which leads to acceptance of the string(Without Backtracking).But how this can be possible in real life? : It is absolutely impossible for present days computer to be such intelligent to predict the future. So why nondeterminism at all?. Answer of this question is quite tricky.What I concluded about the question is that: Automata Theory did exist when computers did not exist(First Theory then practical). It is purely theoretical subject and concept of nondeterminism came intuitively.The motive of the subject 'Automata Theory' was not to dealing with practical computers. But when practically computer come then using Automata Theory we are able to define practical computers precisely: what are the limitations of present day computers.which algorithmic problem are very complex to computers and so impractical(Here the role of nondererminism is very crucial by which we can distinguish two complexity classes P and NP).What is the solutions for these impractical problems by which it can be executed comparatively faster.etc. This is the usefulness of nondeterminism.

Please correct me if there is anything wrong.
> 0 votes

# Answer
non-determinism is useful because it helps you understand determinism, but not the other way around. You could say non-determinism is the bigger idea. A deterministic turing machine is a special case of a non-deterministic one. - Nondeterminism can help us understand why, on todays platforms, some problems are hard to pin down. There are a number of computational problems that have no efficient solution on a deterministic computing platform, but we understand that there can be efficient solutions on nondeterministic ones. ... state, encoding, nondeterminism they are all linked http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

In a deterministic Turing machine, the set of rules prescribes at most *one* action to be performed for any given situation. A non-deterministic Turing machine(NTM), by contrast, may have a set of rules that prescribes *more than one* action for a given situation. http://en.wikipedia.org/wiki/Non-deterministic\_Turing\_machine If you can build a software box that can manage state transitions so well that it can handle more than one action you can get performance beyond deterministic machines.
> 0 votes

# Answer
> Why is non-determinism useful concept?

Determinism has a strong tendency to break symmetries. This tendency is even stronger for sequential determinism, but the notion of an acyclic directed graph and a topological order of such a graph allows to ignore the difference between determinism and sequential determinism. Non-determinism is a superset of determinism, which allows to preserve more symmetries. When designing the solution of a problem, starting with the non-deterministic solution allows to preserve useful symmetries, and which keeps the description of the solution small and compact. The breaking of the symmetries can then be delegated to a later stage during implementation, while converting the non-deterministic solution to a deterministic solution.

Often non-determinism means that the notion of a partial function is replaced by the notion of a relation. In that case, a non-deterministic machine can run both forward and backward in time, while this is not possible in general for a deterministic machine. If we work with total functions for determinism and multivalued total functions for non-determinsim instead, the symmetry is no longer as nice, but it still can be made to work.
> 0 votes

---
Tags: automata, nondeterminism, applied-theory
---


title: What is meant by the notation $L(...)$?

text:
# Question
Title: What is meant by the notation $L(...)$?
I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of.

I have a question to find out the relationship between two languages $L\_1$ and $L\_2$:

$L\_1:$

$S \to aSa|bS|e$

$L\_2 \to L((ab+ba)^\*)$

My question is, does it mean that $L(ab+ba)$ is the set $\\{ab, ba\\}$?

I mean, $L(ab+ba) = L(ab)\cup L(ba)$

# Answer
**This** link confirms my intuition that $L(R)$ where $R$ is a regular expressions simply means "the language produced by the regular expression $R$".

In that case, $ab \in L\_2$ but $ab \notin L\_1$

In case link is down:

Operators used in regular expressions include:

**Union:** If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression. L(R1|R2) = L(R1) U L(R2).

**Concatenation:** If R1 and R2 are regular expressions, then R1R2 (also written as R1.R2) is also a regular expression. L(R1R2) = L(R1) concatenated with L(R2).

**Kleene closure:** If R1 is a regular expression, then R1\* (the Kleene closure of R1) is also a regular expression. L(R1\*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...
> 3 votes

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


# Question
Title: How do I show that $a^n w b^n$ is not regular?
Given $ \Sigma= \\{a,b\\} $, show that $ L:= \\{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\\} $ is not regular.

I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the middle part $w$.

I would pick the symbols $\ a^na^mb^mb^n $ as a starting point and show that this does breach at least one of the three properties of the pumping lemma. At this point I don't know if this is the right word to pick & how I do continue from here.

# Answer
> 5 votes
It's reasonable to conjecture that $L=\\{a^nwb^n\mid w\in (a+b)^\*, |w|=m\ge n\>0\\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^\*b, $$ assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^\*$). The key idea here is that $L$ is defined to be "all strings over $\Sigma=\\{a, b\\}$ **which can be expressed as** $a^nwb^n$ where $|w|\ge n\>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\\{axb\mid x\in (a+b)^\*, |x|\ge 1\\}$. Here's a proof that $L=M$:

* ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n\>0$, so $s\in L$.
* ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n \> 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.

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


# Question
Title: Why is the complexity of this nested for loop not $O(n^2)$?
I have the following pseudo-code:

```
mystery(n):
if n <= 50 :
    for i = 1 ... n :
        for j = 1 ... n :
            print i*j
else :
    mystery(n-1)

```

For the following nested for loop:

```
for i = 1 ... n :
        for j = 1 ... n :

```

For every `i` in `n`, `j` iterates through `n` as many as `i` times. So, why is it that the complexity is not $O(n^2)$?

# Answer
> 3 votes
Because $n$ is bounded by $50$, which is simply a constant. Observe that when $n$ is larger than $50$, you simply have a recursive call. It's only when $n \leq 50$ that you go into the first portion of the if statement and execute the for-loops. Therefore, both nested loops take $\Theta(1)$ time. Hence the total time complexity of the mystery function is linear.

Note that $O(n^2)$ is technically correct, though not tight since $O(1) \subset O(n^2)$. The exact running time is $\Theta(1)$ as pointed above.

---
Tags: algorithm-analysis, time-complexity, asymptotics
---


# Question
Title: Reweight general weighted graph to distinct graph for using Borůvka's
Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it?

I can't seem to think of a way to make a distinction between the same weights, it feels unnatural.

# Answer
Though the Borůvka's algorithm (wiki) for minimum spanning tree is (sometimes? often?) described for weighted graphs with distinct edge weights, this treatment is only for convenience.

If we have an algorithm that assumes the edge weights are unique, we can use it on graphs where multiple edges have the same weight, as long as we have some way of breaking the ties. For example, in graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints (suggested by the wiki article).

To apply the lexicographic order, assume two edges $(a,b)$ and $(c,d)$ have the same weight $w(a,b) = w(c,d)$, where $a,b,c,d$ are (not necessarily distinct) vertices. Then we can decide which of $w(a,b)$ and $w(c,d)$ have the "smaller" weight by comparing the pair $(a,b)$ and $(c,d)$ in their lexicographic order.

Therefore, you don't need to re-weight the equally-weighted edges. You only need to mark them distinct.
> 3 votes

---
Tags: graphs, weighted-graphs
---