# Question
Title: Perceptron learning rule for classification
That's the problem

$$y=(x,w,\rho) = \begin{cases} 1 & \sum\_{i=1}^3 w\_ix\_i \>\rho\\ 0 & \text{otherwise} \end{cases},$$

where $x=\\{x\_1,x\_2,x\_3\\}$ are inputs, $w=\\{w\_1,w\_2,w\_3\\}$ are weights and $\rho$ is the threshold value.

The problem asks to find an opportune set of weights that can classify these inputs.

$$A = \\{(1, 2, 0), (−1, 3, 0), (−2, −3, 0)\\},$$ $$B = \\{(0,1,2),(9,0,1),(−3,−3,3)\\}.$$

The first step is to assign a random weights to all inputs

$w\_1= 0.5$, $w\_2= 0.7$, $w\_3=0.3$.

For the first example $(1,2,0)$ that I know is part of the A class

$\sum\_{i=1}^3 w\_ix\_i=1.9 \< \rho~ \Rightarrow y=0$ is the result.

I need to update the weights but I can't understand how.

The formula is

$w\_i'=w\_i\*n\*x(t-y)$.

Correct?

# Answer
> 1 votes
The biggest problem is your equation is wrong for how to update the weights. Your response that $t$ is the target value is correct. Furthermore, the $n$ should almost certainly be the greek letter eta, $\eta$. Anyway, sticking as close to your notation and example as possible, say we have some input/output pair $(x, t) \in \mathbb{R}^3 \times \\{0,1\\}$ and $y$ is the output of the perceptron on input $x$. Then the weight update should be

$$ w\_i^\prime = w\_i + \eta x\_i (t - y), \\; i = 1,2,3. $$

# Answer
> 1 votes
The first thing to do is to treat the bias ($\rho$) as a weight on an extra input whose activity is always 1 so that you won't need a separate learning rule for the bias and then the decision for your binary threshold outputs a 1 iff $\sum\limits\_{i=1}^{3} w\_i x\_i \geq 0$

To learn the weights of perceptrons, you are right to start with random weights. The remainder of the procedure is to do the following: if for an input your weights correctly classify an output, you leave the weights alone. If, however, you incorrectly output a zero, add the input vector to the weight vector. And on the other hand, if you incorrectly output a 1, subtract the input vector from the weight vector. I would be able to show you an example run with your inputs and random weights above but you're missing the outputs which map to the inputs in order to correct the weights.

Also, note that the above procedure gives you a correct set of weights iff one exists. Otherwise, the learning procedure will fail and you will eventually find it impossible to classify one of the inputs.

**EDIT**: Here's another example to try and explain things. Let's use initial weights where $w = (w\_1, w\_2, w\_3) = (1, 0, -2)$, letting $\rho = 0$, with:

Target: $t\_1 = 1$, $t\_2 = 1$, $t\_3 = 0$, $t\_4 = 1$, $t\_5 = 0$

Input: $x\_1 = (1,0,1)$, $x\_2 = (0,1,1)$, $x\_3 = (1, 0, 0)$, $x\_4 = (1,0,1)$, $x\_5 = (1, 0, 0)$

$y\_1 = wx\_1 = 1\times 1 + 0\times 0 + -2\times1 =-1 \leq \rho$ --\> outputs a 0, which does not equal $t\_1$. In this case, we add the input to the weight vector so $w\prime = w + x\_1 = (1+1,0+0,-2+1) = (2,0,-1)$, $w = w\prime$

$y\_2 = wx\_2 = 0\times 2 + 1 \times 0 + 1\times -1 = -1 \leq \rho $ --\> outputs a 0, which does not equal $t\_2$. In this case, we add the input to the weight vector so $w\prime = w + x\_2 = (2,1,0)$, $w = w\prime$

$y\_3 = wx\_3 = 1\times 2 + 0\times 1 + 0\times 0 = 2 \> \rho$ --\> outputs a 1, which does not equal $t\_3$. In this case, we subtract the input from the weight vector so $w\prime = w - x\_3 = (2-1,1-0,0-0) = (1,1,0)$, $w = w\prime$

$y\_4 = wx\_4 = 1\times 1 + 0\times 1 + 1\times 0 = 1 \> \rho$ --\> outputs a 1, which equals $t\_4$ so the weight vector remains unchanged.

$y\_5 = wx\_5 = 1\times 1 + 0\times 1 + 0\times 0 = 1 \> \rho$ --\> outputs a 1, which does not equal $t\_5$. In this case, we subtract the input from the weight vector so $w\prime = w - x\_5 = (1-1,1-0,0-0) = (0,1,0)$, $w = w\prime$

**Final weight vector** $w= (0,1,0)$

---
Tags: artificial-intelligence, probability-theory, neural-networks, classification
---


# Question
Title: How to check ambiguity of a specific grammar
Giving the following Grammar:

```
S → ^ | SaSMSM |  SMSaSM | SMSMSa
M → b | c

```

^ means eopsilon.

How can i check whether its ambgious or not? My intuition is that its not: every time you derive,the a is placed in different places between the M's.

Can you give me a clue to get a better prove? Or give an example for its ambiguity?
In other words,Can i have to different derevation trees for a same string in this grammar?
Thank you.

# Answer
The grammar is ambiguous. The word $abbabb$ can be derived in at least 3 ways:

$$S \Rightarrow SaSMSM \Rightarrow^2 SaMM \Rightarrow SaSMSMaMM \Rightarrow^7 abbabb,$$ $$S \Rightarrow SaSMSM \Rightarrow^2 aSMM \Rightarrow aSMSMSaMM \Rightarrow^7 abbabb,$$ $$S \Rightarrow SaSMSM \Rightarrow^2 aMSM \Rightarrow aMSMSaSMM \Rightarrow^7 abbabb.$$

I found this by thinking about how words in the language might be parsed. My first observation was that if a word ends with $a$, the derivation must have started with the last rule for $S$. If it ends with $b$ or $c$ one of the other non-$\epsilon$-rules must have been used in the first step.

In order to distinguish these two rules, I looked at the preceding symbol, which is $S$ for both rules. The symbol before that differs again. So if we could uniquely identify the word resulting from the $S$ we could determine the initial rule unambiguously. If we furthermore could uniquely identify which subword results from which symbol of the rule in each case, we would get a procedure that yields a unique parse tree for each word, proving unambiguity.

Alas, I noted that it is not possible to uniquely determine the yield of the rightmost $S$. But now I had a better idea, how an ambiguous word should look like.
> 3 votes

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


# Question
Title: Possible to connect arbitrary number of dots without intersections?
A (now closed) question on SO made me think about the following problem:

> Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point exactly once and does not intersect with itself.

I came to the conclusion that this is easy if I can chose starting and ending point:

```
sort points by their x coordinate
use point with mininmal x coordinate as starting point
connect remaining points in left-to-right order

```

If there are multiple points with the same x value, start with the point with minimal y value and go bottom-up. This way, no intersections can occur.

Now my question is: **is this still possible if start and end point are fixed?** I assume that there are well known algorithms for this problem, but my search didn't reveal any useful results.

As @hyde points out, there is no solution if more than two points are on a straight line and start/end points are not the outermost points.

# Answer
It is (almost always) possible. Let the two points be $p\_1=(x\_1,y\_1)$ and $p\_2(x\_2,y\_2)$. Wlog, assume that $x\_1\<x\_2$. Denote by $q\_1$ ($q\_2$) the point with smallest (largest) $x$-value greater (smaller) then $x\_1$ ($x\_2$) (and smallest (largest) $y$, if there are multiple candidates). Then you can do the following:

* Determine the set $S\_1$ of all the points with $x\leq x\_1$.
* If $|S\_1|=1$, connect $x\_1$ and $q\_1$.
* If $|S\_1| \> 1$ and all the points in $S\_1$ are on the same straight line:

+ If all points outside of $S\_1$ are on the same straight line, there is no solution
    + Otherwise denote by $r\_1$ the point with smallest $x$-coordiate not on the straight line. (If there are multiple such points choose the one with smallest $y$-coordinate.)
    + Connect the points in $S\_1$ starting with $x\_1$. Connect the last of these points with $r\_1$ and (if $r\_1 \ne q\_1$) connect $r\_1$ with $q\_1$.
* If $|S\_1| \> 1$ and the points are not all on one straight line, determine the convex hull of $S\_1$.
At least one of the neighbours $n\_1$ of $p\_1$ on the convex hull can be reached from $q\_1$ without intersecting the convex hull.

+ Draw a (reverse) path from $q\_1$ to $n\_1$ and then along the convex hull to the point with smallest $x$. Continue in left-to-right-order (skipping points already included) until $p\_1$.
* Analoguously connect the points with $x\geq x\_2$.
* Connect the points with $x\_1\<x\<x\_2$ (i.e. from $q\_1$ to $q\_2$) in left-to-right-order (ignoring $r\_1$ resp. $r\_2$, if applicable).
> 5 votes

---
Tags: graphs, computational-geometry
---


title: Faster growing busy beaver function

text:
# Question
Title: Faster growing busy beaver function
Standard busy beaver function draws attention to final count of nonzero symbols on tape. We could instead look at largest amount of nonzero symbols appearing on tape at *any* point of computation. This function's lower bound would be $\Sigma(n)$ and upper bound would be $S(n)$ (max shifts function). Was there made any research on such functions? If so, are there any known values for this?

# Answer
Suppose there is a machine using $n$ states which, at some point, has $X$ nonzero symbols on the tape. One can build a machine with $O(n)$ states which simulates a run of the original machine with a tape alphabet of three symbols $\\{0,1,2\\}$, with the following small change: whenever the original machine changes $1$ to $0$, the new machine changes it to $2$; whenever the tape is read, $2$ is interpreted as $0$. The new machine ends up with $Y \in \[X,2X\]$ nonzero symbols on the tape (we get $\Theta(X)$ instead of $X$ since the simulation requires using two symbols for each original symbol). So your new function, let's call it $F(n)$, satisfies $B(n) \leq F(n) \leq B(O(n))$.
> 8 votes

# Answer
Your function (call it $F$) obviously satisfies $$\Sigma(n) \le F(n) \le space(n)$$ where $space(n)$ is the maximum number of tape squares visited by any $n$-state halting TM in the same class as those considered in the definition of $\Sigma$. Furthermore, $$space(n) \le \Sigma(3n-1)$$ as proved in the following paper:

Ben-Amram, A. M., B. A. Julstrom, and K. Zwick. "A Note on Busy Beavers and Other Creatures." Mathematical Systems Theory 29.4 (1996).

Therefore $$\Sigma(n) \le F(n) \le \Sigma(3n-1)$$
> 5 votes

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


title: EM algorithm for two Gaussian models

text:
# Question
Title: EM algorithm for two Gaussian models
This is about basic machine learning which I do not understand clearly.

I have 2 Gaussian models $G\_1$ and $G\_2$ and given a list of data as below.

(1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

I do not know which numbers were generated by which $G\_i$ model, but I want to do Expectation Maximization for clustering.

So, what are the hidden variables? and how to perform Expectation and Maximization steps?

Could you show some calculation or short Python code of the likelihood metric? (Perhaps 2 iteration)

I got the basics of EM algorithm from here, but I cannot apply to this question. http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html

# Answer
$\newcommand{\I}{\mathbb{I}}\newcommand{\E}{\mathbb{E}}$Given our observed variables $x = \\{x\_i\\}$, hidden variables $z = \\{z\_i\\}$ and distribution parameters $\theta = \\{(\mu\_j, \sigma\_j)\\}$, let's define the *complete-data* log-likelihood as $$ \begin{align\*} \ell\_c(\theta) &= \sum\_{i=1}^n \log \Pr\[x\_i, z\_i|\theta\] = \sum\_{i=1}^n \sum\_{j=1}^k \I\[z\_i = j\] \log \Pr\[x\_i, z\_i = j| \theta\]\\ &= \sum\_{i=1}^n \sum\_{j=1}^k \I\[z\_i = j\] \log (\Pr\[x\_i|\theta\_j\] \Pr\[z\_i=j|\theta\]) \end{align\*} $$ where $\I\[\cdot\]$ is the indicator function, $\Pr\[x\_i|\theta\_j\]$ is the probability of observing $x\_i$ given the $j$th Gaussian and $\Pr\[z\_i=j|\theta\]$ is the *mixing weight* of the $j$th distribution (i.e., the probability of observing the $j$th hidden variable). This is the model we have if we somehow knew which Gaussian generated a given data-point. We obviously don't know, so we would like to compute the *expected* value of this complete-data log-likelihood. That is, what is the expected outcome of this full-knowledge formulation? To do that let us define the $Q(\theta^t|\theta^{t-1})$ function as $$ \begin{align\*} Q(\theta^t|\theta^{t-1}) &= \E\left\[\sum\_{i=1}^n \sum\_{j=1}^k \I\[z\_i = j\] \log \Pr\[x\_i, z\_i = j| \theta\]\right\]\\ &= \sum\_{i=1}^n \sum\_{j=1}^k \E\[\I\[z\_i = j\]\] \log \Pr\[x\_i, z\_i = j| \theta\]\\ &= \sum\_{i=1}^n \sum\_{j=1}^k \Pr\[z\_i = j | x\_i\] \log \Pr\[x\_i, z\_i = j| \theta\]\\ &= \sum\_{i=1}^n \sum\_{j=1}^k \underbrace{\Pr\[z\_i = j | x\_i\]}\_{r\_{ij}} \log (\Pr\[x\_i|\theta\_j\]\underbrace{\Pr\[z\_i = j| \theta\]}\_{\pi\_j}).\\ &= \sum\_{i=1}^n \sum\_{j=1}^k r\_{ij} \log \Pr\[x\_i|\theta\_j\] + \sum\_{i=1}^n \sum\_{j=1}^k r\_{ij} \log \pi\_j. \end{align\*} $$ Computing $r\_{ij}$ for the E-step is done by simple Bayes theorem, $$ r\_{ij} = \frac{\pi\_j \Pr\[x\_i|\theta\_j^{t-1}\]}{\sum\_{j'=1}^k \pi\_{j'} \Pr\[x\_i|\theta\_{j'}^{t-1}\]}.$$ Now for the M-step we would like to compute the mixing weights $\pi$ and parameters $\theta$ that maximize $Q$. Luckily for us, we can optimize for each independently as seen by the final formulation! By taking the derivative of $Q$ wrt $\pi$ with the Lagrange constraint that $\sum\_j \pi\_j = 1$ we have $$ \pi\_j = \frac{\sum\_{i=1}^n r\_{ij}}{n}. $$

In order to optimize $Q$ wrt $(\mu\_j, \sigma\_j)$ lets look at the part only dependent on them (ignoring some constants). $$ \sum\_{i=1}^n r\_{ij} \log \Pr\[x\_i|\theta\_j\] = -\frac{1}{2}\sum\_{i=1}^n r\_{ij} \left(\log \sigma\_j + \frac{(x\_i - \mu\_j)^2}{\sigma\_j}\right) $$ Using this information helps when taking the derivative of $Q$ wrt to each parameter. Finally we have, $$ \begin{align\*} \mu\_j &= \frac{\sum\_{i=1}^n r\_{ij} x\_i}{\sum\_{i=1}^n r\_{ij}}, &\sigma\_j &= \frac{\sum\_{i=1}^n r\_{ij} x\_i^2}{\sum\_{i=1}^n r\_{ij}} - \mu\_j^2. \end{align\*} $$

In your case, $x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)$, $z = (z\_1,\dotsc, z\_{13})$, $k=2$, and $\theta = ((\mu\_1, \sigma\_1),(\mu\_2, \sigma\_2))$. EM begins by randomly initializing $\pi = (\pi\_1, \pi\_2)$ and $\theta$ and then alternating between E-step and M-step. Once the parameters haven't changed much (or better the observed-data log-likelihood hasn't changed much) you can stop and output your current values $\theta^t$ and $\pi$.

One benefit from using $|\ell(\theta^t) - \ell(\theta^{t-1})|$ over $||\theta^t - \theta^{t-1}||$ as a stopping condition is for bug checking. EM guarantees that the likelihood will always monotonically increase; therefore, you can simply check the values each iteration to much sure that your likelihood is greater than or equal to last iteration's. If it isn't, then something is wrong.

Finally one important thing to note is that computing a MLE for a mixture of Gaussians will tend to overfit. One way to overcome this is by incorporating priors for $\pi$ and $\theta$ and then computing the MAP estimate instead. This would only change the M-step; however, its derivation is dependent on which prior you choose.

---

**EDIT**: Since it is clear you are more interested in just a working example than really understanding any of this here is Python code that will run EM for a basic GMM. Running this in ipython gives:

```
In [1]: import em

In [2]: x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

In [3]: em.em(x, 2)
Out[3]:
(array([ 0.49645528,  0.50354472]),
 array([ 15.89753149,   5.10207907]),
 array([ 3.8611819 ,  2.65861623]))

```

where the final output are the mixing weights, means for each Gaussian, and stdevs for each Gaussian.
> 6 votes

# Answer
What you describe is a Gaussian mixture model (GMM) with two components. You can think of the latent variable as a categorical r.v. indicating which Gaussian generated each point. In general if you had $K$ Gaussians you would have a prior $\alpha\_k$ and mean and covariance $\mu\_k$, $\Sigma\_k$ for each $k=1,\ldots,K$. Given i.i.d data $x\_1, \ldots, x\_n$ the likelihood would is given by $$ P(x\_1, \ldots, x\_n \mid \theta) = \prod\_{i=1}^n \sum\_{k=1}^K P(k) P(x\_i \mid \mu\_k, \Sigma\_k) $$ where $P(k) = \alpha\_k$ and $P(x\_i \mid \mu\_i, \Sigma\_k)$ is the pdf of a multivariate normal distribution with parameters $\mu\_k$, $\Sigma\_k$.

In your specific case things are a little simpler since you have only two components and univariate Gaussians. Let $\alpha$ be the prior probability of the first component (the probability of the second is then $1 - \alpha$) and $\mu\_1, \sigma\_1^2$ and $\mu\_2, \sigma\_2^2$ be the mean and variance of the two component distributions respectively. The the likelihood is given by $$ P(x\_1, \ldots, x\_n \mid \theta) = \prod\_{i=1}^n \left\[\alpha f\_1(x\_i) \+ (1 - \alpha) f\_2(x\_i) \right\] $$ where $$ f\_k(x\_i) = \frac{1}{\sigma\_k\sqrt{2\pi}}\exp\left\\{-\frac{(x\_i - \mu\_k)^2}{2\sigma\_k^2}\right\\}. $$ See this tutorial for an intro to EM which discusses GMMs.
> 2 votes

---
Tags: algorithms, machine-learning
---


# Question
Title: Is summing over all possible $k$-combinations NP-hard?
Say we have a set of numbers $A=\\{a\_1, a\_2, \dots, a\_n\\}$, and we wish to sum over all possible combinations of $k$ terms to compute

$$ \sum\_{\substack{C \subseteq \\{1,2,\dots,n\\} \\ |C|=k}} \prod\_{c \in C} a\_c $$

Naively this requires $O(k\binom{n}{k})$ operations.

This is different from from computing the permanent where there are permutations.

Is this problem known to be NP-hard when $n=2k$ or other conditions such as $n=\Theta(k^2)$?

# Answer
> 5 votes
You can compute the coefficient of $x^k$ in $$ \prod\_{i=1}^n (1+xa\_i). $$ Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,\ell)$ be the sum of $\ell$-combinations of $a\_1,\ldots,a\_m$. We have $$ b(m,\ell) = b(m-1,\ell) + a\_m b(m-1,\ell-1), $$ where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,\ell) = 0$ for $\ell \neq 0$. What you want is $b(n,k)$.

In both cases, there is an optimization that only keeps track of $\ell$-combinations for $\ell \leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.

# Answer
> 4 votes
This can be done in polynomial time because this is an elementary symmetric polynomial.

Either we can expand a polynomial from the factors as shown in the section "Elementary Symmetric Polynomials" of http://rjlipton.wordpress.com/2009/07/10/arithmetic-complexity-and-symmetry/

Or we can use the Newton-Girard Formulas http://mathworld.wolfram.com/Newton-GirardFormulas.html

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


# Question
Title: Are there any steps or rules to draw a DFA?
In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two switches, is this question.

I understand what an Alphabet as well as the Language of a DFA is, but are there any rules or steps to followed to reach a correct automaton for a given Language? Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

Note:- Please keep your language as simple as you can, since this is my first lecture and I am not yet aware of concepts like regular expressions or any other thing in the subject for that matter.

# Answer
Yes, there are procedures that help you draw a DFA.

One of them is to draw first an NFA (Non deterministic finite automaton), if we cannot draw instantly a DFA. We humans cannot with ease draw a DFA, especially for a complex language as you've seen. So we draw a NFA which is closer to our understanding. Then, rules are applied on the NFA in order to transform it into DFA. You will see that later on class.

Generally, in order to draw a NFA maybe we will use (only) a bit our imagination. With a given language, we firstly have to understand what is doing and after that we can start drawing pieces of the puzzle.
> 2 votes

# Answer
Do not confuse defining an automaton and drawing an automaton.

The drawing is intended as a support for better intuition, and because it can often be read more easily in a single look. That is what drawing are usually for.

However, you are supposed to actually (be able to) give a formal definition, with the mathematical notation you learned, including specifying the transitions (not necessarily one by one).

In your example you could say, after specifying the transitions for the accepted string: this is completed by all transitions on terminals not yet considered in each state, each going to $q\_{die}$, and all transitions on $q\_{die}$ going back to it. Even this can be said more formally.

It is up to you, and to your instructor, to decide on the proper level of formalism. A drawing is usually enough in simple cases, as it is clear how to get the formal mathematical definition from it.

But for some more abstract problems, drawings are inconvenient, and the mathematical notation is much more easily used. Up to you to decide.

Constructing the automaton, as drawing or as math definition, depends on the problem at hand. There are many way, and your problem may often be to find the right one. Much of your course will be to teach you ways of building automata. These are only early and very simple exercises.

One point worth remembering. In order not to clutter drawings or descriptions, the state $q\_{die}$ (or some equivalent states) is often onitted, as well as all transitions leading only to it (the reader is supposed to complete as I explained above). This is convenient, but dangerous ... some constructions or reasonnings based on automata rely on the fact that all transitions are taken into consideration ... and you may forget those that do not show explicitly.
> 5 votes

# Answer
The answer to your first question is YES for *regular* languages: there are indeed some algorithms to compute a DFA for a given regular Language. These algorithms should be given in the future lessons of your course.

> Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

You can just apply one of the algorithms (or use a computer to do it for you). However, for simple cases, you can sometimes guess the solution by yourself, but this needs practice.
> 1 votes

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


# Question
Title: How to determine if a black-box is polynomial or exponential
I have a problem which essentially reduces to this:

1. You have a black-box function that accepts inputs of length $n$.
2. You can measure the amount of time the function takes to return the answer, but you can't see exactly how it was calculated.
3. You have to determine whether the time-complexity of this function is polynomial or exponential.

The way I did this was by running thousands of random sample inputs of varying lengths through the function, then plotting them on a scatter plot with times on the y-axis and input length on the x-axis.

What are some metrics and methods I can use to determine if these points best fit to a polynomial curve or to an exponential curve?

(Similar question asking how to draw polynomial/exponential best fit lines in Python on Stack Overflow: https://stackoverflow.com/questions/23026267/how-to-determine-if-a-black-box-is-polynomial-or-exponential)

# Answer
Theoretically speaking, this is impossible to accomplish, basically because "polynomial" and "exponential" are asymptotic concepts, and no prefix of the data guarantees *anything* about the behavior at infinity.

Practically speaking, you can try to compute $t(n)^{1/n}$ and so if it approaches a constant bounded away from 1. If so, it is exponential. To test whether it's polynomial, you see whether $\log t/\log n$ approaches a constant. These are only rough tests, of course, but they could be useful in practice.
> 12 votes

# Answer
Let's say your black box takes n^2 * 1.000001^n seconds to process input of size n. For n from 1 to 1,000,000 this is between n^2 and 2.718 n^2 seconds. Unfortunately, for n = 1,000,000 it will take about 80,000 years. So how are you going to find out that the time is exponential? On the other hand, since it takes 80,000 years anyway, do you care that it is exponential?

In practice, many algorithms have very non-smooth behaviour. For example, the naive algorithm for multiplying two n x n matrices of floating-point numbers does about n^3 multiplications and additions, but if you chart the time it takes on a current computer, that chart is all over the place.
> 1 votes

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


# Question
Title: Need solution for infinite right recursive grammar in Predictive parsing?
i am new to compiler design, currently studying Ullmans book on this.He says:

Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite loop.Thus, to make grammar suitable for predictive parsing we need to eliminate the left recursion by immediately or indirectly.

```
 E -> E+T|t

```

My problem is, same can happen with right recursion also.What is the solution for it?

```
 T -> E+T|t

```

Please correct me if i am wrong! thanks.

# Answer
You don't get infinite recursion with right recursive rules if the prediction sets for the rules are different.

In the example `T -> E + T | t`, if the *first* set of `E` does not contain `t` (I am presuming `t` is a terminal), you are fine. The parsing procedure will be:

```
def T
  if look_ahead is in first(E)
    E
    match ('+')
    T
  else if look_ahead == t
    advance_lookahead
  else syntax_error

```

With this, the recursion will stop when the look ahead contains `t`.

With left recursion `T -> T + E | t`, you are in trouble because first(T) *always* contains `t`.

Conversion of left- to right recursion solves one problem but creates another. Right-recursive rules have the disadvantage that parsing lists requires stack space proportional to list length. Ideally you'd like the space a parser takes to be limited by a constant. So what to do?

The practical way to prevent many cases of right-recursion is to extend grammars to allow for iteration. In your case

```
T -> E + T | t

```

would become

```
T -> E + { E + } t

```

The curly braces denote "0 or more".

When the parser is implemented, the curly braces would become a while loop that uses the look ahead to decide whether to parse another instance of what's in the braces. With your example, you'd need first(E) not to contain terminal t.

A more common example is the standard expression grammar:

```
Expr -> Term { '+' Term }
Term -> Factor { '*' Factor }
Factor -> '0' | '(' Expr ')'

```

In this case, the recursive descent procedure for `Expr` would be

```
def Expr
  Term
  while look_ahead == '+'
    advance_lookahead
    Term

```

If we didn't have the curly braces, the grammar would have to be:

```
Expr -> Term ExprTail
ExprTail -> '+' Term ExprTail | \eps
Term -> Factor TermTail
TermTail -> '*' Factor TermTail | \eps
Factor -> '0' | '(' Expr ')'

```

To parse `Expr`s we now need two procedures:

```
def Expr
  Term
  ExprTail

def ExprTail
  if look_ahead == '+'
    advance_lookahead
    Term
    ExprTail

```

Interestingly, if you use a good compiler to compile both versions with optimizations turned on, it will detect tail recursion in `ExprTail`, convert it into a loop, and then in-line the loop in `Expr`. The resulting compiled codes will be exactly the same.
> 4 votes

# Answer
Left recursion is not supported by LL(k) parsers. They cannot generate a parse tree. So as you see, the real problem is the left recursion itself and not the ability to go infinite.

> Why the infinity does not bother us? Here is a proof of mine:

In Computer Science, and generally in machines, infinity does not exist.

If you have a language with recursion, you could only achieve infinity in parsing only of you have a program of infinite (well formed) commands. In order to have such a program, you have to write it for infinite amount of time. Infinite does not stop. So you will never parse the infinite program. ;)
> 0 votes

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


# Question
Title: Which kind of interrupt has the highest priority on 8086 processors?
Which of the following interrupts has the highest priority in 8086 micro-processor:

1. Overflow,
2. NMI or
3. Type 255?

The book I read suggests that type 255 has highest priority. But most of the searches on google showed that it is NMI. Which is true?

# Answer
The Intel manual for 8086 on page 2-23's diagram and also in the text says that internally generated interrupts are processed before hardware. It says in particular an overflow is processed as part of the instruction that generated the over flow, and hardware interrupts aren't checked until instructions are complete. So overflow is the answer.
> 4 votes

---
Tags: computer-architecture
---


# Question
Title: Why is data stored on a flash disk irretrievable if the memory chip is cracked?
All data recovery companies, regardless of skill, unanimously say that if the memory chip of a device has just a hair line crack, data recovery is impossible. Not unlikely, not expensive, but impossible. One company even stated that even the FBI can't retrieve the data. Is this true?

Why is this? I find it hard to believe if just a tiny section of an extremely common chip has a tiny crack, all of the data is completely gone.

I would have thought someone talented person somewhere would be able to patch up the area of the chip and get some of the data back...

Is it something to do with the charge? I know flash memory uses transistors to store its ones and zeroes in the form of an electrical charge. If the chip is cracked, do the transistors "short-out", turning them all to zeroes, something like that? Is the data gone rather than irretrievable?

# Answer
> 2 votes
The data may well still be there, the problem is that there is no (reasonable) way to get an electrical signal into or out of the data cells. When you crack a chip you are cracking wires. The minimum feature size in many chips made these days is around 20nm=200 Angstroms. I suppose that if you (a) had an electron microscope, (b) knew exactly how the manufacturer had laid out the chip (what every wire means, and what signals need to be sent where to get the data), and (c) had some kind of electron microscope based soldering iron or micro-manipulator with a tip just a few atoms wide, you could laboriously and painstakingly repair all those broken connections.

But, while data recovery companies (the super duper ones) *might* have electron microscopes, I doubt they have either (b) any access to the manufacturer's layout or (c) a micromanipulator that could actually be used to do the repair. Also, we're talking about potentially needing to repair thousands of connections, so even if someone were able to do it, they'd probably charge tens or hundreds of thousands of dollars.

---
Tags: storage
---


# Question
Title: How is A* search superior to Dijkstra's algorithm
Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A\* search which is a extension of Dijkstra's algorithm.

How is it that A\* search algorithm is able to perform better compared to Dijkstra's algorithm , what sort of technique does it used that Dijkstra's algorithm did not use ???

# Answer
Consider providing driving directions from an origin to a destination. Although sometimes traveling away from the destination for short distances is required (think highway on ramp), in general it is best to travel toward the destination. In this case A\* is likely to outperform Dijkstra's algorithm because it (probably) will traverse less of the graph.

Dijkstra's algorithm uses a single heuristic, $g(n)$, which is the distance from the origin. In selecting the next road to evaluate, the road with the least $g(n)$ is selected; however, this road may travel away from the destination. A\* adds an estimate of the remaining distance, $h(n)$, to bias the search towards the destination. The full A\* heuristic is $f(n) = g(n) + h(n)$. Note that as the search progresses, $f(n)$ must monotonically increase or else the path found may not be the shortest. Thus, $h(n)$ must be optimistic and never underestimate the remaining distance (in the directions example, assume the remainder of the trip can be a straight line).
> 4 votes

# Answer
First, you have to note that A\* is a generalization of Dijkstra's and the two are equivalent when you have a uniform-cost heuristic and your evaluation function $f(n) = g(n) + h(n)$ can be simplified by just using $f(n) = g(n)$ (where $g(n)$ is the actual cost at node $n$) since each node will have the same heuristic estimate. On the other hand, you can specify a non-uniform heuristic function $h$ which allows you to favour expanding certain nodes before others and this is more effective when your heuristic $h(n)$ is more representative of the distance from node $n$ to your goal node. By evaluating certain nodes before others, you can reach the goal node a whole lot sooner, but remember: this depends on your heuristic whose purpose is to provide a fast, representative estimate.
> 1 votes

# Answer
This two algorithms use the same method - choose the best state and expand it by all possible methods, don't use state twice. The problem is - "which one is the best?". Dijksta algorithm solve concrete case of directed graph with positive edges weight. And it's easy to get the best vertex - it have smallest distance from initial vertex and adjacent to one of visited vertexes. So, dijkstra will find the shortest path on every input data.

A\* can be used for any task, even when you can't say exactly what state is the best, for example I've solved 15-puzzle with it. In this case there are many table states which can be considered "best" so we choose the first. But found path isn't shortest.

I used obvious heuristic h(state) = manhattan distances between numbers and it final positions (in reverse, it is 0 when puzzle solved). g(state) = number of steps to achieve this state (as always). Priority is f(x) = h(x) + g(x). Of course, there can be much better estimation (mb it's better to don't touch 1 2 3 4 but stay shuffling 5 6 7 8 ... just as first thoughts).

So, when A\* used for something (in STRIPS planning system, or simple pathfinding), it's possible to find very good h(x) for concrete case of graph, so perfomance can become really unexpected (for example, "jump point search" for uniform-cost grid map gives optimal soultion and much better perfomance than bfs-like steps + manhattan heuristic).

Anyway, determined solution still stay preffered. There is no need to solve Rubik's cube with A\*, as you can solve it by usual algorithms (you can predict steps count then). And proved classic dijkstra is better than A\* when you need to find short path in directed graph with positive edges (and it will be the shortest).
> 1 votes

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


# Question
Title: The most frequent integer value from set of intervals
What is the fastest way to get one of the value from set of intervals which occurs most frequently?

For example if I have interval (0, 3) and (2, 4) the most frequent value can be 2 or 3.

# Answer
> 1 votes
It seems to me that the answer to your question will have a technique similar to this - https://stackoverflow.com/a/9676296/477522

---
Tags: algorithms, intervals
---


# Question
Title: Why is TIME(n log (log n)) \ TIME(n) = ∅?
In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be the empty set. Can anyone show me why this is?

both $TIME(n\log(\log n))$ and $TIME(n)$ are regular. I think that only means we can subtract the two sets and the result will still be regular. I just dont understand how its possible to subtract the collection of $O(n\log(\log n))$ time TM decidable languages from the collection of $O(n)$ time TM decidable languages and get the empty set. These two collections are not equal so I feel like there will be something left over

# Answer
> 4 votes
The quick explanation is that

$TIME\[o(n\log n)\]\subseteq REG\subseteq TIME\[n\]\subseteq TIME\[o(n\log n)\]$, and therefore $TIME\[o(n\log n)\]=REG$.

Similarly:

$TIME\[n\log\log n\]\subseteq TIME\[o(n\log n)\]\subseteq REG\subseteq TIME\[n\]\subseteq TIME\[n\log \log n\]$, so $TIME\[n\log\log n\]=REG$

But I think this is not the point you are missing.

You say that $TIME\[n\log \log n\]$ is regular. This is not exact. When we say that something is regular, we mean that it is a language $L\subseteq \Sigma^\*$, which is regular (i.e. can be recognized by a DFA).

The class REG is not a language, but a set of languages. That is, $REG\subseteq 2^{\Sigma^\*}$. Similarly, $TIME\[f(n)\]\subseteq 2^{\Sigma^\*}$ for every function $f$. These are all classes of languages.

Since we have that $TIME\[n\log\log n\]\subseteq TIME\[o(n\log n)\]\subseteq REG$, then $REG\setminus TIME\[n\log\log n\]=\emptyset$. This follows from the simple property that if $A\subseteq B$, then $A\setminus B=\emptyset$.

---
Tags: complexity-theory, regular-languages, time-complexity, complexity-classes
---


# Question
Title: Mathematical function vs Computer program
In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration.

Let us take $A\_1,A\_2,A\_3 \cdots A\_n$ be the n sets.

Then relation $R \subseteq A\_1\times A\_2\times A\_3 \times A\_n$ .

Here $X$ represents cross product betwen two sets.

If we consider first $k$ sets as input domain and next $n-k$ sets as output range.

Then $R$ is an $k$-ary function that returns $n-k$ multiple outputs. $0 \le k \le n$

As we know function is a well-behaved relation. i.e.., A relation can assign same input to any number of outputs.

In the case of functions (well-beahaved relations) one input at most maps to one output.

My doubt is whether

1. Any program written in any program language ultimately a mathematical relation.
2. Any program written in any program language ultimately a mathematical function.
3. Some programs written in programming languages cannot be a mathematical relation.
4. Some programs written in programming languages cannot be a mathematical function.

We know that 2. $\implies$ 1. and 3. $\implies$ 4.

Which of the four arguments above are true for all set of programs in all programming languages?

I am arguing with my colleague that 1.,2. are true independent of programming language and program.

But his argument is that procedural languages like c, c++, pascal etc.., doesn't obey 2. but in case of functional programming languages like Haskell it's true.

So, is functional programming is syntactical extension of mathematical functions or conceptual extension?

# Answer
So, the notion of mathematical function is broader than that of a computable function i.e. one you can write in a programming language. There are some mathematical functions which can't be written as programs, such as the function from binary encodings of Turing Machines to booleans representing whether that machine halts on every input.

A Turing machine can be thought of as a function in one of two ways. In case 1, it's a function from its alphabet $\Sigma^\*$ to the set ${\top, \bot}$ of boolean values, where the value for an input string is either true if the machine accepts, or false if it does not. This is also what corresponds to a decision problem in formal language theory. The second, more complex way, is where we see a Turing machine as a function from $\Sigma^\*$ to $\Sigma^\*$, where the value for an input string is whatever value is on the tape at the time of termination.

Note that all other types of Turing machines, such as non-deterministic, multi-tape, etc. can be converted into a deterministic one. (Unless you get something really weird that can do infinite computation in finite time). Also, you can encode most mathematical data in strings, but things get complicated for things such as real numbers or certain infinite sets.

The lambda calculus interpretation is more straight-forward. The lambda calculus is a term rewriting system, where everything is a function. A lambda calculus expression can usually be taken to a normal (irreducible) form through some sequence of $\beta$ and $\eta$ reductions. (Beta-reduction is basically just substituting values for arguments, eta is just writing $\lambda x . f x$ as $f$).

So, every lambda-calculus expression $f$ can be viewed as a function from lambda-calculus expressions to lambda-calculus normal forms, where the value of $f$ with argument $a$ (some other expression) is the normal form of $f a$. Again, most things, like integers, strings, etc, can be encoded in the lambda-calculus, but some things, such as real numbers, are more tricky.

Now's where things get fun. This is all assuming a lambda-calculus or Turing-machine model. What these are very bad at modelling is IO, or some interaction with the outside world.

The Haskell approach to this is to view these as pure functions with some "world" argument, which gets destroyed every time it's updated (a new world state is created).

Likewise, for something like interactive programs, you can stretch our definitions and model the pixels shown on the screen, the files written to disk, the audio waves played, etc. as bits which are part of the program's output.

For example, consider a Python program which prints the current date and time $n$ times for some argument $n$. At first glance, this isn't a function, since you can give it the same $n$ and get a different result. However, if you view the state of the world, namely the current date and time, as an argument to the program, then it always does give the same result for the same input, it's just that input is physically impossible to reproduce because we don't control the passage of time. (You could fudge the computer clock if you wanted, but you can apply the same principal to physical sensors and such).

So, let's look at your four specific questions.

1. Yes (see 2 below).
2. Yes, by expressing that program either as a Turing Machine or $\lambda$-calculus expression.
3. No, see 4.
4. No, assuming that you model programs with IO as taking the entire state of the world as input and outputting a new state of the world as output. Otherwise, yes.

You have to be careful, because some languages, such as Prolog, let you write something that's closer to a relation than a function. But at the end of the day, if you massage the notation enough you get something that is a function.
> 4 votes

# Answer
Every program in any programming language is equivalent to an expression in lambda calculus, which is a function on expressions in lambda calculus.
> 3 votes

---
Tags: terminology, computability, programming-languages, functional-programming
---


# Question
Title: What is the asymptotic runtime of the best known TSP solving algorithm?
I always thought that TSP currently requires time exponential in the number of cities to solve.

> How, then, has Concorde optimally solved a TSP instance with **85,900 cities**?!?

Is this a typo? Is the base of the exponential 1.0000000000000001 or similar? Was it an instance specifically constructed to be solvable easily? What *is* the asymptotic runtime of the best known TSP solving algorithm?

# Answer
> 4 votes
The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different worst case run times.

See the accepted answer in this question on CSTheory to see a list of algorithms.

---
Tags: algorithms, np-hard, traveling-salesman
---


title: n-Cube as a Cayley Graph

text:
# Question
Title: n-Cube as a Cayley Graph
I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how to interpret it. It runs as follows:

> Let $\Gamma$ be a group and $S$ be a subset of $\Gamma$ not including the identity element. Suppose that the inverse of every element in $S$ also belongs to $S$. The Cayley graph of $\Gamma$ with respect to $S$ is the graph $CG(\Gamma, S)$ with vertex set $\Gamma$ in which two vertices $x$ and $y$ are adjacent iff $xy^{-1}\in S$.

Okay. I follow so far.

> Recall that the n-cube is the graph whose vertex set is the set of all n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ in precisely one coordinate.

Makes sense.

> Show that the n-cube is a Cayley graph.

What does it mean to talk about "$xy$" when $x$ and $y$ are n-tuples? What is the inverse of an n-tuple?

Someone I asked about the problem suggested that I treat $\Gamma$ here as the additive group $({\mathbb Z}/2{\mathbb Z})^n$, and so take $xy^{-1}$ to mean elementwise subtraction of $y$ from $x$, mod 2. But then it seems like $(0, 0, ..., 0)\in\Gamma$ and, since it's the identity element, every vertex will have an edge connecting to it, and that isn't what the n-cube looks like. Googling, I also see that there is an interpretation of tuples as nested sets, but then I don't see how the product of two nested sets would ever be in S, since it will have a different cardinality from either of the original tuples. Interpreting the tuples as vectors can't work either since then $xy^{-1}$ will have different dimensions than either of the original tuples.

What is this question asking?

# Answer
> 3 votes
The question is asking you to find a suitable group $\Gamma$ and a subset $S$, so that $CG(\Gamma,S)$ is the n-cube.

Since by definition of $CG$, the nodes are the elements of $\Gamma$, you don't have a choice here, leaving the group operation and $S$.

$xy$ and the inverse of $y$ are then understood with respect to the group operation you choose.

Also be aware that the identity element being in $\Gamma$ does not imply that all other vertices are connected with it, since the edges are determined by $S$, not $\Gamma$.

---
Tags: graphs, terminology, group-theory
---


# Question
Title: $T(n)=2T(n/2)+n\log n$ and the Master theorem
According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?

And which case of master theorem is it?

# Answer
$\log n$ grows slower than $n^\epsilon$ for any $\epsilon\>0$. Thus $n\log n$ grows slower than $n^c$ for any $c\>1$. However, the third case of the Master theorem requires the existance of a $c\>1$ so that $n\log n$ grows at least as fast as $n^c$ (up to a constant factor).

The function is covered by the second case of the Master theorem as given in Wikipedia.
> 4 votes

# Answer
Case 3 of Master Theorem:

> If $f(n)=\Omega(n^{\log\_b a+\epsilon})$ for some constant $\epsilon \> 0$, and if $f (n/b) ≤ cf (n)$ for some constant $c \< 1$ and all sufficiently large $n$, then $T (n) = \Theta(f (n))$.

Here $f(n)=n\log n$ and $n^{\log\_ba}=n^{\log\_2 2}=n^1=n$. So $n^{log\_ba+\epsilon}=n^{1+\varepsilon}$. But $n\log n$ is not $\Omega(n^{1+\epsilon})$.

So it is not under case 3. It is also not under second case: If $f(n)=\Theta(n^{\log\_ba})$, then second case can be applied. But here $n^{\log\_ba}=n$ and $f(n)=n\log n$ is not $\Theta(n)$.

This recurrence can't be solved by Master method.
> 3 votes

---
Tags: algorithms, algorithm-analysis, master-theorem
---


# Question
Title: Branch Prediction - LOCAL BHR without tag
I have a question about the common course "Computer Architecture".

How is it possible to have a LOCAL Branch Predecitor with 1024 entries, 3 bits for HISTORY but without a TAG.

As I understand,in that way i will get a Global branch predictor because i dont have a way to map a branch to an entry. Am I right? If not,How can it be possible?

# Answer
The 1024 entries would be indexed by bits from the instruction address, so the history is likely to be for the same branch (especially since there is temporal locality in instruction execution, so the same branch is more likely to be executed nearby in time than some other branch that happens to have the same index in the branch predictor). Without complete tags, there is the possibility of aliasing (where the history at a given index is actually from a different branch than the instruction address being looked up), but since only a prediction is provided even destructive aliasing would only cause a misprediction. With 32-bit addresses and fixed-length 4-byte instructions, 1024 entries would use 20 bits per entry for complete tags, requiring over six times as much storage as an untagged table with 3 bits of history per entry.

(Aliasing can reduce prediction accuracy enough that techniques like agree predictors have been developed to reduce destructive aliasing. In an agree predictor a second source of prediction information \[usually static for a per-address predictor, often a dynamic per-address table for a global history based predictor since adding the per-address table also allows tournament prediction\] provides a bias for the other predictor; instead of predicting taken or not-taken, the other predictor predicts agree or disagree. Bi-Mode prediction is similar, but uses two tables with table selection based on the branch bias.)

For a local history predictor there can also be aliasing in the table translating the local history into a prediction. If only one table is used one branch's behavior could interfere with predictions for another branch. (This is *not* a terrible design; the Alpha 21264 used a 1024-entry local history predictor with 10 bits of history and a single shared 1024 entry \[indexed by the 10 history bits\] predictor with 3 bit saturating counters, along with a global predictor and chooser.)

Using tags (even partial tags) allows the use of associativity and the percentage storage overhead is less if the branch target buffer is merged with the local predictor. (A unified direction predictor and branch target buffer would generally have fewer direction entries than separate predictors and BTB entries for unconditional control flow operations do not need direction prediction.) However, direct-mapped structures are faster (and using tags increases energy use), so there are tradeoffs.

(Similar tagging tradeoffs exist for bimodal \[distinct from Bi-Mode\] predictors, where a single table indexed by a hash of the branch address provides the prediction, typically using either a two bit saturating counter or a prediction bit and a hysteresis bit.)
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: Has there been any more progress on P vs. PSPACE compared to P vs. NP?
I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown for P vs. NP but have not been shown for P vs PSPACE, so that there is hope that certain proof techniques might resolve P vs PSPACE even though they cannot resolve P vs NP? And are there any non-trivial results that say that if P = PSPACE then there are implications that do not necessarily hold under P = NP? Or anything else non-trivial in the literature that suggests it's easier to prove P != PSPACE than it is to prove P != NP?

# Answer
This doesn't really answer your question, but there is a result that under a restricted form of time travel (yes, time travel), it holds that $P=PSPACE$. I'll remark that the result is nontrivial, given the restrictions on the model. See this explanation by Scott Aaronson.
> 9 votes

# Answer
To prove that $\mathsf{NP}^A=\mathsf{coNP}^A$ for a "sufficiently natural" $\mathsf{PSPACE}$ oracle $A$ implies $\mathsf{NP}^A=\mathsf{PSPACE}$ should be much easier than to prove $\mathsf{P}\neq\mathsf{PSPACE}$. By "sufficiently natural", I'm especially thinking about languages complete for a certain level of the polynomial hierarchy. Nailing down the exact naturality conditions would be part of proving such a statement.

There are some reasons to believe that such a theorem should exist. We already can prove that $\mathsf{NP}^A=\mathsf{coNP}^A$ for some $\mathsf{PH}$ oracle $A$ leads to the collapse of the polynomial hierarchy at $\mathsf{PH}=\mathsf{NP}^A$. The difference between $\mathsf{PH}$ and $\mathsf{PSPACE}$ in descriptive complexity theory is so small, that it is hard to imagine how the polynomial hierarchy could collapse without also affecting $\mathsf{PSPACE}$. A more subtle reason to believe this which also hints at a strategy for a proof is that $\mathsf{NP}^A$ is closed under finite intersections and nearly arbitrary (=PSPACE bounded) unions.
> 4 votes

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


# Question
Title: Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed
How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)?

Examples:

Is there some general idea to handle these or other similar dynamic algorithms?

# Answer
In the two examples you mention, the dynamic programming algorithms work just as well. Let's take *partition* as an example. The dynamic programming approach computes, for every $m$, the sums of all subsets of $\\{w\_1,\ldots,w\_m\\}$. This works just as well if negative numbers are allowed. The range of the table has to be modified accordingly, to account fo the largest possible positive and negative amounts. With knapsack it's similar, and I'll let you work out the details.
> 0 votes

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


title: 3-SAT to Max-2-SAT Reduction

text:
# Question
Title: 3-SAT to Max-2-SAT Reduction
I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck.
Let me first describe it.

> **3-SAT**: Given a CNF formula $\varphi$, where every clause in $\varphi$ has *exactly* 3 literals in it, one should determine if there exist an assignment that satisfies it.
>
> **Max-2-SAT**: Given a CNF formula, where every clause in $\phi$ has *exactly* 2 literals in it, and a positive number $k$, one should determine if there exist an assignment that satisfies *at least* $k$ clauses.

Let me first show what I have tried so far.
Given $\varphi=\wedge \_{i=1}^{n}C\_i$ where: $C\_i=(l\_{i\_1}\vee l\_{i\_2} \vee l\_{i\_3})$,
I set: $\phi=\wedge \_{j=1}^{3n}D\_i$, where: $D\_i=(l\_{i\_1}\vee l\_{i\_2})\wedge(l\_{i\_1}\vee l\_{i\_3})\wedge(l\_{i\_2}\vee l\_{i\_3})$ and $k=2n$.
It's quite easy to see that this will not work...
Although, if there exist an assignment which satisfies $\varphi$ it means there exist an assignment that satisfies $k=2n$ clauses in $\phi$, the second direction is not true.
I found several reductions online (such as this, for example), but none of them were useful since in my problem, each clause in $\phi$ must have **exactly** two literals, where in the link above, the formula can also contain 1-length clause in it.

I could really use some help here.

# Answer
Hint: Replace a singleton clause $a$ with $a \lor b$ and many copies of $\lnot b \lor c$, $\lnot b \lor \lnot c$.

---

Reductions without extra variables don't work even when singleton clauses are allowed. There are five types of clauses: $\ell\_1,\lnot \ell\_1, \ell\_1 \lor \ell\_2$, $\ell\_1 \lor \lnot \ell\_2$, $\lnot \ell\_1 \lor \lnot \ell\_2$. Suppose that $k$ of $\ell\_1,\ell\_2,\ell\_2$ are true. The probability that a random clause of each type is true is: $$ \begin{array}{c|cccc} k&0&1&2&3\\\hline \ell\_1 & 0 & 1/3 & 2/3 & 1 \\ \lnot \ell\_1 & 1 & 2/3 & 1/3 & 0 \\ \ell\_1 \lor \ell\_2 & 0 & 2/3 & 1 & 1\\ \ell\_1 \lor \lnot \ell\_2 & 1 & 1/3 & 1/3 & 1\\ \lnot \ell\_1 \lor \lnot \ell\_2 & 1 & 1 & 2/3 & 0 \end{array} $$ We would like to take a convex combination of these rows which is of the form $$ \begin{array}{cccc} \alpha & \beta & \beta & \beta \end{array} $$ However, all such convex combinations have $\alpha = \beta$.
> 1 votes

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


# Question
Title: Confusion with the Running Time of an algorithm that finds duplicate character
I have the following simple algorithm to find duplicate characters in a string:

```
for i = 1 -> n
    for j = i + 1 -> n
        if A[i] == A[j] return true
return false

```

Why is the running time of this algorithm $\mathcal{O}(n^2)$? If the first iteration is $n$ steps then, $n-1, n-2,n-3,..,1$ it seems to me that adding all these would never be $n^2$ or am I wrong?

# Answer
> 1 votes
Don't confuse the $n$ in $O(n)$ with the $n$ in your algorithm! If you consider the number of times the line `if A[i] == A[j] return true` is evaluated, this will in the worst case indeed be $(n-1) + (n-2) + (n-3) + \dots + 1$. There is a closed formula for this sum:

$\sum \_{i=1}^n i = \frac{n(n+1)}{2} = \frac{n^2 + n }{2}$, (see Wiki)

so asymptotically you get the runtime of $O(n^2)$.

# Answer
> 3 votes
When we sum all numbers we get $n(n-1)/2$, which is in the class of functions $O(n^2)$. Make sure that you understand what big O notation is about.

Another way of seeing that this sum is $O(n^2)$ since each summand is at most $n$ and there are at most $n$ summands, so the sum is at most $n^2$.

# Answer
> 1 votes
The inner loop is executed $\sum\_{1\le i\le n}\sum\_{i\lt j\le n} 1$ times. $$\sum\_{1\le i\le n}\sum\_{i\lt j\le n} 1=\sum\_{1\le i\lt j\le n} 1=\sum\_{1\le j\le n}\sum\_{1\le i\le j-1}1=\sum\_{1\le j\le n}(j-1)$$ $$=0+\dots+n-1=(n-1)n/2.$$

This is $\cal O(n^2)$.

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


title: Constraints on subset sum problem

text:
# Question
Title: Constraints on subset sum problem
Subset sum is given by this question: "The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?"

My question is: If the numbers in the set are functions of other numbers, is that still subset sum? For example The set {1,2,3} where the first number is X, the second is X+1, third is X+2 and so on. So it is a general set.

Is this allowed?

# Answer
> 3 votes
A set such as $\\{1,2,3\\}$ is valid input to the problem you defined, so yes, it is "allowed". When setting such constraints, you typically want to know "does the problem still remain NP-complete?". In this sense, notice there is a difference between "can my input take form such as this" and "if my input always takes this form, is the problem still NP-complete?"

I believe you are after the latter; if you impose some constraints on the input, does the problem remain NP-complete? For example, if your input is the set $\\{1,\ldots,n\\}$ for some positive integer $n$, the answer is *no*, the problem can easily be decided in polynomial time (can you see why?)

# Answer
> 1 votes
The problem SUBSET-SUM is defined usually as follows. An input string belongs to the language SUBSET-SUM if it is a space-separated list of numbers encoded in binary, denoted $x\_0,\ldots,x\_n$, such that some subset of $\\{x\_1,\ldots,x\_n\\}$ sums to $x\_0$ (this differs from your account since we don't necessarily have $x\_0 = 0$). An *instance* of SUBSET-SUM is an informal notion meaning a space-separated list of numbers encoded in binary.

Even more informally, the problem SUBSET-SUM is to decide, given a list $x\_0,\ldots,x\_n$, whether $x\_0$ is the sum of some subset of $\\{x\_1,\ldots,x\_n\\}$. This notion is used in reductions. Suppose, for example, we want to show that PARTITION is NP-hard. An input string belongs to the language PARTITION if it is a space-separated list of numbers encoded in binary, denoted $x\_1,\ldots,x\_n$, such that some subset of $\\{x\_1,\ldots,x\_n\\}$ sums to $(x\_1 + \cdots + x\_n)/2$. This reduces to the SUBSET-SUM instance $(x\_1+\cdots+x\_n)/2,x\_1,\ldots,x\_n$. What this really means is that there is a polynomial time function $f$, such that $x \in \mathrm{PARTITION}$ iff $f(x) \in \mathrm{SUBSET-SUM}$, which implements the following algorithms:

1. Attempt to decode the input $x$ to a list of numbers $x\_1,\ldots,x\_n$. (These are supposed to be encoded as space-separated binary integers.)
2. If unsuccessful, output `1` (or any other string not in SUBSET-SUM, such as `1 2`).
3. If successful and $x\_1+\cdots+x\_n$ is odd, output `1`.
4. If successful and $x\_1+\cdots+x\_n$ is even, output the concatenation of the binary representation of $(x\_1+\ldots+x\_n)/2$ followed by a space () followed by $x$.

The description of this reduction uses variables, but the output string itself is just a list of numbers encoded in binary as a space-separated string. Any other input format does not constitute a well-formed instance of SUBSET-SUM.

You can define more general versions of SUBSET-SUM, for example allowing variables. These versions will always be NP-hard (since SUBSET-SUM is a special case), and usually also NP-complete.

# Answer
> 1 votes
A set of integers that does not contain functions can be converted into a set of the form your describe by multiplying every element in the set by $x$. Conversely, you can convert a set that contains functions by letting $x=1$ (assuming the functions are defined at 1) and evaluating the functions. So the two problems are equivalent.

---
Tags: complexity-theory, decision-problem
---


# Question
Title: Grammar for parsing simple mathematical expression
mexp ::= (\< mexp \>) | \< mexp \>\< mathlowop \>\< mexp \> | \< mulexp \> | \< float \> | \< var \>

mulexp ::= \< mexp \>\< mathhighop \>\< mexp \>

mathlowop ::= + | -

mathhighop ::= / | *

That's the BNF I've come up with for parsing simple mathematical expressions where the operands can only be floats or variables. I've looked at a number of resources in books and on the web and for the same type of problem, they usually have a slightly longer, more complex bnf. Is my BNF incorrect in some way? Or is it correct but there is a significant advantage in doing it another way?

# Answer
Your grammar will generate mathematical expressions, but you haven't captured the notion of operator precedence. For instance, there are two different ways your grammar can generate the expression $a+a\*a$, one having the interpretation we'd write as $a+\[a\*a\]$ and the other having $\[a+a\]\*a$. Using the jargon, we'd say your grammar is ambiguous.

A grammar that avoids this problem is

\< expression \> ::= \< term \> + \< expression \> | \< term \> - \< expression \> | \< term \>

\< term \> ::= \< factor \> * \< term \> | \< factor \> / \< term \> | \< factor \>

\< factor \> ::= (\< expression \>) | \< float \> | \< var \>

See if you can generate $a+a\*a$ in two different ways using your grammar and then try the same thing with this grammar. That should give you an idea of what's going on here.
> 7 votes

# Answer
If you are looking for a grammar, then yours is correct. If you are going to implement a parser, you might want to tweak your grammar a bit. It depends on the tools you are going to use.
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: What is the difference between maximal flow and maximum flow?
What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a reasonable answer. I believe maximum flow is quite clear as it means maximum amount of flow that can be transferred from source to sink in a network, but what exactly is maximal flow.

Please answer in layman terms if possible.

Thanks.

# Answer
As saadtaame mentions, *maximum* usually means global maximum, whereas *maximal* means local maximum. For example, a *maximal independent set* in a graph is one to which no vertex can be added (making it a *dominating set*), while a *maximum independent set* is one with largest cardinality among all independent set.

My guess is that a *maximal flow* is one in which every source-to-sink path has a saturated edge (i.e., the flow equals the capacity). Such a flow cannot be improved by pushing more flow through some source-to-sink path.

It so happens that such a flow is also *maximum*. To see this, consider the residual network, formed by the unsaturated edges. Let $C$ be the connected component containing the source. Since the flow is maximal, $C$ does not contain the sink, and so it forms a source-sink cut in the graph. The value of every flow in the graph is bounded by the capacity of edges crossing the cut. Yet by definition, this is also the value of the flow under consideration, completing the proof.
> 5 votes

# Answer
Boils down to knowing the difference between maximal and maximum. maximal is relative whereas maximum is absolute. I guess, maximal flow means maximum flow in a sub-network but I'm not sure.
> 2 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: What order of growth does a ratio of Bigh-Ohs have?
Say that $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

If $h(n)=f(n)/g(n)$, is it true that $h(n) =\cal O(n)$?

Is it mathematically correct to say that $h(n) = \cal O(n^2)/ O(n) = O(n)$? if not, what would be the correct way to show this?

# Answer
Let $f(n)= n^2$ and $g(n)=1$. Then $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

However, $h(n)=f(n)/g(n)=n^2/1 = n^2 \neq \cal{O}(n)$.
> 9 votes

---
Tags: asymptotics
---


# Question
Title: Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree
I'm writing a balanced $n\_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton z-curve.

Using only this information:

* The level of a node can be computed by traversing to the root of the tree.
* Neighbor searches are performed by traversing the tree up until a common parent is found, and then traversing the tree back down again.

I can compute the following constants depending on the number of spatial dimensions $n\_d$:

* the #of children of a node: $2^{n\_d}$,
* the #of $n\_d - m$ dimensional neighbors for each node (in 3D, $n\_d - 1$ neighbors are faces, $n\_d - 2$ neighbors are edges, $n\_d - 3$ neighbors are corners):

$2^{n\_d} \begin{pmatrix} n\_d \\ m \end{pmatrix}$

The neighbors sharing a $n\_d - 1$-dimensional face with each Hypercube form the set $\mathcal{N}\_{n\_d - 1}$. They are numerated within this set as follows. The neighbor at the negative side from the node center comes first, then it comes the neighbor at the positive side. That is, for $n\_d = 1$ I just have $\mathcal{N}\_{n\_d - 1} = \lbrace 0, 1 \rbrace = \lbrace \mathrm{Left}, \mathrm{Right} \rbrace$.

* In $n\_d = 2$, $\mathcal{N}\_{n\_d - 1} = \lbrace 0, 1, 2, 3 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{Top}, \mathrm{Bottom} \rbrace$.
* In $n\_d = 3$ it is $\mathcal{N}\_{n\_d - 1} = \lbrace 0, 1, 2, 3, 4, 5 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{T}, \mathrm{B}, \mathrm{Front}, \mathrm{Back} \rbrace$

and so on.

I haven't been able yet to generalize the algorithm for finding the $n\_d - 1$ neighbor located at a given position to arbitrary dimensions. My current algorithm traverses the tree up until a common parent node is found. During the up traversal it stores the child positions w.r.t. their parents of the nodes traversed. Then it traverses the tree back down using the reversed path of the up traversal. The child positions are found by finding the siblings of the child positions during the up traversal in the inverted neighbor direction, which can be computed as:

$\mathrm{inverted\\\_neighbor\\\_position}\_{n\_d - 1}(p) = (p + 1) * (p \\% 2 = 0) + (p - 1) * (p \\% 2 \neq 0)$

However, to know if a common parent has been found, it checks if a parent node has a childe at a given relative position of another child which expressed as a neighbor position, i.e., it checks if a node has a sibling in a given neighbor direction within its parent. I have only a hand-coded stencil for this check and haven't been able to generalized.

* Can this check for a "common parent" be generalized to arbitrary dimensions? How?
* Example up to 3D: for a child and a neighbor position, returns the child position of the sibling:

```
// i means, there is no sibling for that child in that direction
//0  1  2  3  4  5     << nghbr position
{ i, 1, i, 2, i, 4},  // child 0
{ 0, i, i, 3, i, 5},  // child 1
{ i, 3, 0, i, i, 6},  // child 2
{ 2, i, 1, i, i, 7},  // child 3
{ i, 5, i, 6, 0, i},  // child 4
{ 4, i, i, 7, 1, i},  // child 5
{ i, 7, 4, i, 2, i},  // child 6
{ 6, i, 5, i, 3, i}   // child 7

```

Assuming that the $n\_d - 1$ dimensional neighbors can be found:

* How can I find $n\_d - m$ dimensional neighbors?

+ Right now, I hand-coded traversals that perform $m$ times searches for $(n\_d - 1)$ neighbors. Is there a general way to generate these traversals for $n\_d$ dimensions and the $n\_d - m$ neighbors?
* What is a suitable order for $n\_d - m$ dimensional neighbors where $m \> 1$ ?

Most of the research I've found in the literature uses hand coded stencils for, 1,2,3 and 4 dimensions, but no general ways of generating these stencils. So if anyone can point me to relevant literature I would appreciate it.

# Answer
> 1 votes
You are asking two different questions:

1. What are the $2^{n\_d} \binom{n\_d}{m}$-many codimension $m$ neighbors of a given node?
2. Given a description of a neighbor, how to locate it?

Regarding the first question, a neighbor of codimension $m$ is given by (1) a subset $S$ of the coordinates of size $m$, (2) for each $x \in S$, a direction $d\_x \in \\{-1,+1\\}$. The *address* of a neighbor is obtined by adding $d\_x$ to coordinate $x$.

Regarding the second question, the simplest algorithm would consist of the following steps:

1. Find the address of the node by traversing the tree up.
2. Find the address of the neighbor. This part is described above.
3. Find the neighbor by traversing the tree down.

These steps are straightforward generalizations of the algorithm described in the link.

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


title: Partitioning NP-complete problems

text:
# Question
Title: Partitioning NP-complete problems
Let's suppose I have an NP-complete problem A.

Can there be $A\_1$, $A\_2$ such that $A\_1$ and $A\_2$ are disjoint, $A = A\_1 \cup A\_2$, and $A\_1$ and $A\_2$ are NP-complete?

My guess would be yes. For example, just partition SAT into formulas with an even number of variables and formulas with an odd number.

Follow up: Can I partition $A$ into infinitely many such $A\_i$? (I suppose yes: take formulas with $2^n$ variables, $3^n$, $5^n$, $7^n$, $11^n$, or something like that)

# Answer
> 1 votes
There are many ways of accomplishing this. Consider SAT for example. Let SAT$\_p$ denote a YES instance of SAT with $n$ clauses, where $p$ is the smallest prime factor of $n$. Clearly $\\{ \mathrm{SAT}\_p : p \text{ prime} \\}$ is a partition of SAT. SAT$\_p$ is clearly in NP. To show that it is NP-hard, we reduce from SAT. Given an instance of SAT having $n$ clauses, with add $m$ times the clause $x \lor y \lor z$ ($m$ to be chosen later so that $p$ is the smallest prime factor of $n+m$), where $x,y,z$ are new variables. The new instance is satisfiable iff the original one is, and by definition $p$ is the smallest prime factor of $n$. It remains to define $m$ and show that the reduction can be done in polynomial time (this depends only on the value of $m$ compared to the value of $n$).

Let $P$ be the product of all primes at most $p$. We will choose $m$ so that $n + m \equiv p \pmod{P}$. Clearly some $p \< P$ fits the bill. I leave the reader to show that $p$ is the smallest prime factor of $n + m$.

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


title: Minimum cut versus sparsest cut?

text:
# Question
Title: Minimum cut versus sparsest cut?
My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since all weights = 1) while maximizing the number of vertices in the resulting subgraph. How do I approach this problem with flow?

# Answer
> 2 votes
The sparsest cut problem, in which one attempts to minimize the ratio between the number of edges cut to the size of the smaller size of the bipartition, is NP-complete. The "last word" on this problem theoretically speaking is the $O(\sqrt{\log n})$ algorithm by Arora, Rao and Vazirani (affectionately knows as ARV), which has found many uses in the area of approximation algorithms.

You might want to start with the simpler algorithm of Leighton and Rao, which gives an $O(\log n)$ approximation and has a relation to flows. See for example these lecture notes, or many others.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: How do you prove that this TM decides a language that is undecidable?
In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A\_{TM}$, which is the language

$$A\_{TM} = \\{ \langle M,w \rangle | M \text{ is a TM and $w \in L(M)$}\\}.$$

$T$ is a TM defined as follows. On input $\langle M,w \rangle$,

1. Write the description of a TM $R$ that works as follows. On input $x$,
    * Run $T\_A$ on $x$.
    * If $T\_A$ accepts $x$ then accept.
    * If $T\_A$ rejects $x$ then run $M$ on input $w$ and accept if $M$ does.
2. Run $P$ on input $\langle R \rangle$, accept if $P$ rejects and reject if $P$ accepts.

Here:

* $T\_A$ is a TM that decides the language $A$.
* $P$ is a TM that can decide the language $$ Z = \\{\langle M\rangle | M\text{ is a TM and } L(M) = A\\}. $$
* $ A = \\{(0 \cup 1)^a(1 \cup 2)^b(2 \cup 3)^c | a \geq b\\} $.

How can you prove that $T$ decides $A\_{TM}$ ?

# Answer
> 0 votes
Hint: The exact definition of $A$ is not important; you just need $A \neq \Sigma^\*$. When is $L(R) \neq A$? (look at the third line!)

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: Method to recognize abstract objects such as hand-drawn objects?
My research is in the area of Document Image Analysis. To be specific, the topic of my thesis is to automatically recognize and index characters in a set of hand-drawn objects, e.g. given a volume of comics --\> how to localize, recognize then index the characters in it (e.g. return "Lucky Luke" position in some random volume).

First thing first, before I can work on the indexing part, I must have some reliable system to recognize the interested characters. After some months working on it, I find the recognition is extremely hard, because the drawings are some time very "abstract".

For normal face recognition, there are a lot of researches on it, thus we have Haar-like features, biometrics features, etc. For normal photograph objects, we may use e.g. SIFT/SURF, or other strong features for the purpose of object recognition.

But in cartoons or comics, we may extract so few or zero feature(s) following the traditional approaches. Human visual interpretation system is amazingly effective in recognize such abstract objects (e.g. only with 4 lines and 2 curves, we still recognize the familiar character).

So I think the solution must be somewhere in the understanding how human can interpret such a set of line strokes as a meaningful object. Once we understand it we can try to "teach" the computer the same way.

Thus are there some good approaches in the terms of recognition of abstract objects such as drawn comic objects? (I searched for some but they're not so relevant). Thanks.

# Answer
> 2 votes
It sounds like you're looking for *shape matching* techniques. Sven Loncaric's well-cited survey paper "A Survey of Shape Analysis Techniques" from 1998 can be found here.

In 2002, Belongie, Malik and Puzicha proposed a similarity measure between two shapes based on

> 1. solving for correspondences between points on the two shapes, then
> 2. using the correspondences to estimate an aligning transform.

David Marr's book 'Vision', particularly §3.6 and chapter 5, also provides some background about the correspondence between shape recognition in human visual systems and computers.

---
Tags: machine-learning, image-processing, pattern-recognition
---


# Question
Title: Is it compulsory that every infinite set be non regular?
I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing this example:

> $$L= \\{ 0^n 1^n | n\>=0 \\} $$ its formal as $\Sigma=\\{0,1\\}$ and thus we've a formal meaning as $\\{\epsilon,01,0011,000111,....\\}$
>
> ```
>                                no. of 0's = no. of 1's
>
> ```

The above language should be a non-regular as we need to keep track the value of 'n' in order to make it a equal no, of 0's & 1's and FA has no memory.

or am i mistaken.

Please, provide some oxygen regarding this confusion.thank you.

# Answer
> 6 votes
The statement should read " it is NOT compulsory that every infinite set is non-regular, though every finite set is regular." So being infinite is necessary but not sufficient for being irregular.

For example, for any alphabet $\Sigma$, the language $\Sigma^\*$ is infinite but regular. In fact, a regular language will be infinite iff a regular expression generating the language contains a $\*$ on some non-empty non-empty-string expresion, assuming union and concatenation are the only other operators.

A more accurate statement is that any language which needs an infinite amount of memory to recognize is non regular. For example, $\\{0^n 1^n | n \geq 0\\}$ is non-regular because we need to "count" how many 0s there are and see if the number of 1s matches, but since there can be any number of 0s, there is no limit to the size of the count we'd have to store. Thus, we need some unbounded memory structure, like a stack or a tape.

# Answer
> 10 votes
You must have misunderstood the comment, since the set $\Sigma^\*$ is infinite and regular. The correct notion of "infinite" is given by the Myhill–Nerode theorem. Every language is associated with a set of *states*, and a language is regular iff the set of states is finite.

A *state* in a language $L$ is a set of strings $S$ that are interchangeable with respect to $L$ in the sense that for all words $x$, either all words of the form $sx$ (where $s \in S$) are in $L$, or all are not in $L$. In the example $L = \\{0^n 1^n : n \geq 0\\}$, the states are $\\{ 0^{m+n} 1^n : n \geq 0 \\}$ for each $m \geq 0$, all other words forming another state. You can see that there are infinitely many states, and so the language is not regular.

Every regular language has a DFA whose states correspond to the states described above. This DFA is known as the *minimal DFA*. A "minimal DFA" for $\\{ 0^n 1^n : n \geq 0 \\}$ would need to have infinitely many states, since the DFA would have to remember how many zeroes it has seen so far, or more generally how many ones it expects at this point (if the next symbol is a one). No finite automaton can remember that much information, so the language isn't regular.

# Answer
> 3 votes
> "Is it compulsory that every infinite set is non regular though every finite set is a regular set".

No.

All finite sets are regular but infinite sets may or may not be a regular set. An infinite as well as regular set example is $a^\*$ And an infinite but non-regular example is $\\{ a^nb^n$ | $n \> 0 \\}$.

See the Venn-diagram below: In Venn-Diagram every finite set is regular. Infinite set may be regular or not. Actually, class of regular-languages ⊆ set of all possible infinite sets.

> **Venn:** Show class of regular sets are subset of set of all infinite stes

Some interesting points to be notice that will help you to understand properties of regular language e.g. pumping lemma:

* Any finite automata (without dead state) for a finite language does *not* contain a loop. Also regular expressions for finite language will be without $\*$ "star clouser" and $+$ "plus clouser" operation.
(read Raphael♦'s comments: a complete DFA defined on δ: Q×Σ → Q may contains loop but I am talking about partial δ ⊆ Q×Σ → Q that "FA without a loop that is reachable from the starting state and from which a final state can be reached").
* Any finite automata for a infinite language(regular) will contain the loop. We can't construct an automata for infinite language without loop; where loop may be a self loop of via some other state. {If its self loop then a single symbol repeats any number of time, if via other state a sequence of symbols comes in loop can be repeat any numbers of time}.

Additionally, to learn "What is called regular language?" And Why a languages like $(a + b)^\*$ is regular? But language $\\{ a^nb^n$ | $n \> 0 \\}$ is *not* a regular language? read this answer: I need clarification about DFA's and DFA acceptable languages.

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


# Question
Title: Shortest directed path connecting given subset of vertices
Given

* weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$
* source vertex $v \in V$
* vertex subset $U \subset V$

how to find a shortest directed path from $v$ containing all vertices from $U$? Note that such path may contain vertices that are not in $U$.

1. Does such problem have a name?
2. How to find a solution?

# Answer
This problem is NP-complete, by reduction from Hamiltonian path. Given an instance $G=(V,E)$ of Hamiltonian path, add a new vertex $s$ connected to all original vertices; this edges are directed *from* $s$, and all the original graph edges are bidirectional. Give all edges unit weight. There is a path from $s$ visiting all of $V$ of weight $|V|$ if and only if $G$ has a Hamiltonian path.
> 2 votes

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


# Question
Title: Lower bound on number of comparisons needed to search for a number in a sorted 3-d array
Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. However are $\Omega(N^2)$ comparisons needed in the worst-case? For an $N \times N$ 2-d sorted array I recall a proof that $\Omega(N)$ comparisons are needed; I'm having trouble seeing how to extend to the 3-d case though

# Answer
Let's suppose that the array is indexed using $\\{1,\ldots,N\\}$, and assume for simplicity that $N$ is odd. Divide the cells in the array into three parts: $$ \begin{align\*} X &= \\{ (i,j,k) : i+j+k \< 3 \tfrac{N+1}{2}, \\} \\ Y &= \\{ (i,j,k) : i+j+k = 3 \tfrac{N+1}{2}, \\}, \\ Z &= \\{ (i,j,k) : i+j+k \> 3 \tfrac{N+1}{2}, \\}. \end{align\*} $$ Consider a 3D array $A$ with $A(i,j,k) = -\infty$ for all $(i,j,k) \in X$ and $A(i,j,k) = \infty$ for all $(i,j,k) \in Z$ (you can think of $-\infty,\infty$ as stand-ins for large negative and positive numbers). We claim that any such array is sorted. Indeed, suppose for example that $i\_1 \< i\_2$ and $j,k$ are given. If $i\_1 + j + k \< 3\frac{N+1}{2}$ then $A(i\_1,j,k) = -\infty \leq A(i\_2,j,k)$. If $i\_1 + j + k \geq 3\frac{N+1}{2}$ then $A(i\_1,j,k) \leq \infty = A(i\_2,j,k)$.

It follows that you cannot rule out that a finite number is in $A$ without checking all entries in $Y$ (formally this can be proved using an adversary argument). The number of entries in $Y$ is at least $N^3 / (3N-2) = \Omega(N^2)$.

The same idea extends to give a lower bound of $N^{d-1}/d$ in the $d$-dimensional case.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, search-algorithms, arrays, lower-bounds
---


# Question
Title: What is the formal description of a Turing machine?
I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.

# Answer
In class you must have seen a formal definition of a Turing machine, such as the one given by Wikipedia. Formally, a Turing machine is given by a bunch of sets and functions. A formal description of a Turing machine is just this data. You can check out some examples on Wikipedia.

The definition in Wikipedia is only one possible definition — you will need to use the formal definition given in class. While the different formal definitions give rise to slightly different Turing machine models, these models are always equivalent in power (up to some small differences), in particular they are equivalent in terms of which functions can be computed in them.

Programming a Turing machine "formally" is like writing a program in a programming language (or assembly language). In contrast, informal descriptions of Turing machines are similar to *pseudocode* or to informal descriptions of algorithms. Programming Turing machines is very messy, and the point of this exercise is just to show you that it is possible in principle, and to help you understand how a Turing machine actually "works".
> 3 votes

---
Tags: terminology, turing-machines
---


title: Question about threads and locks

text:
# Question
Title: Question about threads and locks
I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote:

> In a fair locking scheme the lock is granted in the order it was requested. This can have negative impact on throughput due to the increased number of context switches. At the same time it can lead to the so called convoy problem. Since the locks are granted in the order of arrival, they all proceed at the speed of the slowest process, slowing down all waiting processes. A common solution to the convoy problem has been to mark the lock available upon release, wake all waiting processes and have them recontend for the lock. This is referred to as random fairness. However, this also leads to the thundering herd problem. Despite this, it can work well on uni-processor systems if the first task to wake releases the lock before being preempted or scheduled, allowing the second herd member to obtain the lock, etc...

I have a few questions about this quote.

First, does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

Second, how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

Finally, I don't understand how random fairness is any better on uni-processor systems in comparison to multiprocessor systems. For example, in both cases, all of the waiting processors are woken up, one gets the lock, and the others have to go to sleep again, right? So how does this work well on uni-processor systems?

# Answer
> 4 votes
Let me answer the last question first. It points out that the paper was written in 2002, when multi-core processors were much more expensive. I think the authors were largely concerned with optimizing for the single-core case.

> ... how \[is\] random fairness ... any better on uni-processor systems in comparison to multiprocessor systems.

On a uniprocessor only one process can be scheduled at a time. So everyone gets "woken up," but that just means they get moved from a waiting state to a ready state. Then the scheduler is invoked and it chooses one of the ready processes to run, and lets that process run for some period of time.

The first thing the newly running process does is acquire the lock. Then it does some processing and (if you are not unlucky) releases the lock. In this case the next time the kernel scheduler gets control it chooses another "ready" process and starts it running. If the first process released the lock, then the second process will acquire it, and so on.

On a multiprocessor on the other hand, all the processes might get "woken up" and then the scheduler starts some/many/all of them running simultaneously on different processors. One of the processes will acquire the lock, but all the other processes will try to acquire the lock, immediately fail, and put themselves back to sleep on the wait queue. So on all the processors but one you just wasted several kernel calls and several context switches just so you could tell a bunch of processes that there was nothing to do.

> does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

I think the case they have in mind is if you have multiple processes (on *one* processor), where each process acquires the same lock repeatedly for short periods of time. In the unfair case the first process can run for a while and acquire and release the lock many times without doing a context switch. Then the second process runs for a while and acquires and releases the lock many times.

In the "fair" case the first process locks/releases and then the second time it tries to lock it must be put to sleep, and the kernel has to do a context switch and wake up the other process. The processes ping-pong back and forth doing "wake up, lock, unlock, work a little while, try-to-lock, get put to sleep."

> how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

I think they are making the observation that, on a uniprocessor, shortest-job-first (unfair) has shorter average wait times than does round-robin (fair). But I don't understand how random decreases the average wait times compared to round-robin.

---
Tags: concurrency, threads
---


title: Why use languages in Complexity theory

text:
# Question
Title: Why use languages in Complexity theory
I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model.

I have a pretty basic question, but am really hoping some of you guys can help me understand the concept behind it:

> Why is everything centered around the notion and definition of LANGUAGES (i.e. regular languages and context free languages)? And how do these relate and describe the complexity of an algorithm and the possible computational models for solving them?

I read these sort of related questions:

but still don't have an answer to my doubts, since they provide a practical justification of why they are important (which I do understand) but don't help me understand why complexity theory is based upon them.

# Answer
> 15 votes
It's because languages are the best (only?) way we have of formalizing the concept of a "problem."

An algorithm (Turing Machine) has performance, which we express via big-O complexity. A problem (language) belongs to a complexity class. These are usually defined by existence: if there exists a machine accepting a language $L$ which runs in given performance (space or time), then the language belongs to the corresponding complexity class.

There's a few reasons for this. First is that languages are platform independent. You're not worrying about whether an integer is 32 or 64 bits, or whether floating point operations run in parallel with other operations. These things give performance speedup at the micro-level, but complexity analysis is interested in the macro level. As you scale from 100 to $10^6$ to $10^9$ to $10^{12}$ inputs, how does the algorithm performance change? Does it go from using 1 million tape cells to 1 billion, or from 1 million to more cells than there are atoms in the universe?

The second is that languages are just a nice abstraction for data. You need something you can do proofs about, something you can model formally. Encoding your input and output as a string mean that you're now dealing not with bits in memory, but with mathematical objects with specific properties. You can reason about them and prove proofs about them in a formal, and very simple sense.

Complexity theory tends to be focused on decision problems because they end up being difficult. When the decision version of travelling salesman is NP-complete (i.e. is there a tour shorter than length $k$), then obviously finding the shortest path is harder. There isn't as much focus on function/optimization problems because there's still a lot of open questions and unsolved problems about the simpler decision problems.

I guess here's my challenge to you: find way to mathematically describe problems that isn't languages. I don't know if languages are special, but I think they're the simplest tool we've got, the easiest one to deal with.

# Answer
> 8 votes
There are two basic answers to your question:

1. There is more to complexity theory than languages, for example function classes, arithmetic complexity, and the subareas of approximation algorithms and inapproximability.
2. Historical reasons: one of the basic papers in computability theory was discussing Hilbert's Entscheidungsproblem (a form of the halting problem).

Unfortunately I don't know much about the latter, but let me expand on the former.

## Complexity beyond languages

Every computational complexity class comes with an associated *function class*. For example, the class P of all problems decidable in polynomial time is associated with FP, the class of all functions computable in polynomial time. FP is important since it is used to define NP-hardness: a language $L$ is NP-hard if for every language $M$ in NP there is a function $f\_M$ in FP such that $x \in M$ iff $f\_M(x) \in L$. Another complexity class of functions, #P, is related to the so-called *polynomial hierarchy* via Toda's theorem.

*Arithmetic circuit complexity* (or *algebraic complexity theory*) deals with the complexity of computing various polynomials. Important complexity classes here are VP and VNP, and *geometric complexity theory* is an important project attempting to separate VP and VNP (and later P and NP) using algebraic geometry and representation theory.

Another important example of algebraic complexity is fast matrix multiplication. Here the basic question is *how fast can we multiply two matrices*? Similar questions ask how fast we can multiply integers, how fast can we test integers for primality (this is a decision problem!) and how fast can we factor integers.

*Convex optimization* deals with optimization problems that can be solved (or almost solved) efficiently. Examples are linear programming and semidefinite programming, both of which have efficient algorithms. Here we are interested both in the optimum and in the optimal solution itself. Since there is often more than one optimal solution, computing an optimal solution is not well represented as a decision problem.

*Approximability* is the area that studies how good an approximation we can get for an optimization problem in polynomial time. Consider for example the classical problem of Set Cover: given a collection of sets, how many of them do we need to cover the entire universe? Finding the optimal number is NP-hard, but perhaps it is possible to compute an approximation? *Approximation algorithms* is the subarea studying algorithms for computing approximations, while *inapproximability* studies limits of approximation algorithms. In the particular case of Set Cover, we have an algorithm giving a $\ln n$ approximation (the greedy algorithm), and it is NP-hard to do any better.

# Answer
> 3 votes
Let's look at this question from the perspective of category theory. The decision problems (or languages) would then correspond to the objects of a category, and the allowed reductions between two problems would correspond to the morphisms (arrows) of a category.

Talking about languages has the advantage that equivalence of languages is well defined (namely by extensional equality). Two unrelated problems might lead to the same language, and then we are allowed to consider them as equivalent. If we would want to talk about isomorphic problems instead, we would have to define the allowed morphisms between two problems. But the allowed morphisms depend on the actual complexity class under consideration, which makes this approach less suitable for comparing different complexity classes.

The notion of isomorphic problems will normally be coarser than the notion of equivalent languages, i.e. two problems can be isomorphic, even if their associated languages are not equivalent. What is worse is that there are often different reasonable notions for the allowed morphisms, which only agree with respect to the allowed isomorphisms. Focusing on languages allows to postpone such problems until we feel like talking about some different reasonable notions of reduction (like Karp reduction vs. Cook reduction).

---
Tags: complexity-theory, formal-languages
---