# Question
Title: How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for *all* grammars (or automata) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

# Answer
To my knowledge the pumping lemma is *by far* the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.

That said, I am also interested in other techniques than the pumping lemma if there are any.

EDIT: Here is an example for the pumping lemma: suppose the language $L=\\{ a^k \mid k ∈ P\\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

1. The pumping lemma gives you a $p$
2. You give a word $s$ of the language of length at least $p$
3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
4. You give an integer $n≥0$
5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is a prime number) will do the trick. Then the pumping lemma gives you $uvxyz$ with $|vy|≥1$. Do disprove the context-freeness, you need to find $n$ such that $|uv^nxy^nz|$ is not a prime number.

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

A second example is the language $\\{ww \mid w \in \\{a,b\\}^{\ast}\\}$. We (of course) have to choose a string and show that there's no possible way it can be broken into those five parts and have every derived pumped string remain in the language.

The string $s=a^{p}b^{p}a^{p}b^{p}$ is a suitable choice for this proof. Now we just have to look at where $v$ and $y$ can be. The key parts are that $v$ or $y$ has to have something in it (perhaps both), and that both $v$ and $y$ (and $x$) are contained in a length $p$ substring - so they can't be too far apart.

This string has a number of possibilities for where $v$ and $y$ might be, but it turns out that several of the cases actually look pretty similar.

1. $vy \in a^{\ast}$ or $vy \in b^{\ast}$. So then they're both contained in one of the sections of continguous $a$s or $b$s. This is the relatively easy case to argue, as it kind of doesn't matter which they're in. Assume that $|vy| = k \leq p$.
    * If they're in the first section of $a$s, then when we pump, the first half of the new string is $a^{p+k}b^{p-k/2}$, and the second is $b^{k/2}a^{p}b^{p}$. Obviously this is not of the form $ww$.
    * The argument for any of the three other sections runs pretty much the same, it's just where the $k$ and $k/2$ ends up in the indices.
2. $vxy$ straddles two of the sections. In this case pumping *down* is your friend. Again there's several places where this can happen (3 to be exact), but I'll just do one illustrative one, and the rest should be easy to figure out from there.
    * Assume that $vxy$ straddles the border between the first $a$ section and the first $b$ section. Let $vy = a^{k\_{1}}b^{k\_{2}}$ (it doesn't matter precisely where the $a$s and $b$s are in $v$ and $y$, but we know that they're in order). Then when we pump down (i.e. the $i=0$ case), we get the new string $s'=a^{p-k\_{1}}b^{p-k\_{2}}a^{p}b^{p}$, but then if $s'$ could be split into $ww$, the midpoint must be somewhere in the second $a$ section, so the first half is $a^{p-k\_{1}}b^{p-k\_{2}}a^{(k\_{1}+k\_{2})/2}$, and the second half is $a^{p-(k\_{1}+k\_{2})/2}b^{p}$. Clearly these are not the same string, so we can't put $v$ and $y$ there.

The remaining cases should be fairly transparent from there - they're the same ideas, just putting $v$ and $y$ in the other 3 spots in the first instance, and 2 spots in the second instance. In all cases though, you can pump it in such a way that the ordering is clearly messed up when you split the string in half.
> 73 votes

# Answer
## Ogden's Lemma

> **Lemma (Ogden).** Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of *marking* $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that
>
> 1. $vx$ has at least one distinguished position.
> 2. $vwx$ has at most $N$ distinguished positions.
> 3. For all $i\geq 0$, $uv^iwx^iy\in L$.

**Example.** Let $L=\\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\\}$. Assume $L$ is context-free, and let $N$ be the constant given by Ogden's lemma. Let $z=a^Nb^{N+N!}c^{N+2N!}$ (which belongs to $L$), and suppose we *mark* as distinguished all the positions of the symbol $a$ (i.e. the first $N$ positions of $z$). Let $z=uvwxy$ be a decomposition of $z$ satisfying the conditions from Ogden's lemma.

* If $v$ or $x$ contain different symbols, then $uv^2wx^2y\notin L$, because there will be symbols in the wrong order.
* At least one of $v$ and $x$ must contain only symbols $a$, because only the $a$'s have been distinguished. Thus, if $x\in L(b^\*)$ or $x\in L(c^\*)$, then $v\in L(A^+)$. Let $p=|v|$. Then $1\leq p\leq N$, which means $p$ divides $N!$. Let $q=N!/p$. Then $z'=uv^{2q+1}wx^{2q+1}y$ should belong to $L$. However, $v^{2q+1}=a^{2pq+p}=a^{2N!+p}$. Since $uwy$ has exactly $N-p$ symbols $a$, then $z'$ has $2N!+N$ symbols $a$. But both $v$ and $x$ don't have $c$'s, so $z'$ also has $2N!+N$ symbols $c$, which means $z'\notin L$, and this contradicts Ogden's lemma. A similar contradiction occurs if $x\in L(A^+)$ or $x\in L(c^\*)$. We conclude $L$ is not context-free.

**Exercise.** Using Ogden's Lemma, show that $L=\\{a^ib^jc^kd^{\ell}:i=0\text{ or }j=k=\ell\\}$ is not context-free.

## Pumping Lemma

This is a particular case of Ogden's Lemma in which all positions are distinguished.

> **Lemma.** Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$, $z$ can be written as $z=uvwxy$, such that
>
> 1. $|vx|\>0$.
> 2. $|vwx|\leq N$.
> 3. For all $i\geq 0$, $uv^iwx^iy\in L$.

---

## Parikh's Theorem

This is even more technical than Ogden's Lemma.

**Definition.** Let $\Sigma=\\{a\_1,\ldots,a\_n\\}$. We define $\Psi\_{\Sigma}:\Sigma^\*\to\mathbb{N}^n$ by $$\Psi\_{\Sigma}(w)=(m\_1,\ldots,m\_n),$$ where $m\_i$ is the number of appearances of $a\_i$ in $w$.

**Definition.** A subset $S$ of $\mathbb{N}^n$ is called *linear* if it can be written: $$ S = \\{\mathbf{u\_0} + \sum\_{1 \le i \le k} a\_i \mathbf{u\_i} : \text{ for some set of $\mathbf{u\_i} \in \mathbb{N}^n$ and $a\_i \in \mathbb{N}$}\\} $$

**Definition.** A subset $S$ of $\mathbb{N}^n$ is called *semi-linear* if it is the union of a finite collection of linear sets.

> **Theorem (Parikh).** Let $L$ be a language over $\Sigma$. If $L$ is context-free, then $$\Psi\_{\Sigma}\[L\]=\\{\Psi\_{\Sigma}(w):w\in L\\}$$ is semi-linear.

**Exercise.** Using Parikh's Theorem, show that $L=\\{0^m1^n:m\>n\text{ or }(m\text{ is prime and }m\leq n)\\}$ is not context-free.

**Exercise.** Using Parikh's Theorem, show that any context-free language over a unary alphabet is also regular.
> 49 votes

# Answer
### Closure Properties

Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this:

> Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$.

This is often shorter (and often less error-prone) than using one of the other results that use less prior knowledge. It is also a general concept that can be applied all kinds of class of objects.

**Example 1:** *Intersection with Regular Languages*

We note $\mathcal L(e)$ the regular language specified by any regular expression $e$.

Let $L = \\{w \mid w \in \\{a,b,c\\}^\*, |w|\_a = |w|\_b = |w|\_c\\}$. As

$\qquad \displaystyle L \cap \mathcal{L}(a^\*b^\*c^\*) = \\{a^nb^nc^n \mid n \in \mathbb{N}\\} \notin \mathrm{CFL}$

and $\mathrm{CFL}$ is closed under intersection with regular languages, $L \notin \mathrm{CFL}$.

**Example 2:** *(Inverse) Homomorphism*

Let $L = \\{(ab)^{2n}c^md^{2n-m}(aba)^{n} \mid m,n \in \mathbb{N}\\}$. With the homomorphism

$\qquad \displaystyle \phi(x) = \begin{cases} a &x=a \\ \varepsilon &x=b \\ b &x=c \lor x=d \end{cases}$

we have $\phi(L) = \\{a^{2n}b^{2n}a^{2n} \mid n \in \mathbb{N}\\}.$

Now, with

$\qquad \displaystyle \psi(x) = \begin{cases} aa &x=a \lor x=c \\ bb &x=b \end{cases}\quad\text{and}\quad L\_1 = \\{x^nb^ny^n \mid x,y \in \\{a,c\\}\wedge n \in \mathbb{N}\\},$

we get $L\_1 = \psi^{-1}(\phi(L)))$.

Finally, intersecting $L\_1$ with the regular language $L\_2 = \mathcal L(a^\*b^\*c^\*)$ we get the language $L\_3 = \\{a^n b^n c^n \mid n \in \mathbb{N}\\}$.

In total, we have $L\_3 = L\_2 \cap \psi^{-1}(\phi(L))$.

Now assume that $L$ was context-free. Then, since $\mathrm{CFL}$ is closed against homomorphism, inverse homomorphism, and intersection with regular sets, $L\_3$ is context-free, too. But we *know* (via Pumping Lemma, if need be) that $L\_3$ is not context-free, so this is a contradiction; we have shown that $L \notin \mathrm{CFL}$.

---

### Interchange Lemma

The *Interchange Lemma* \[1\] proposes a necessary condition for context-freeness that is even stronger than Ogden's Lemma. For example, it can be used to show that

$\qquad \\{xyyz \mid x,y,z \in \\{a,b,c\\}^+\\} \notin \mathrm{CFL}$

which resists many other methods. This is the lemma:

> Let $L \in \mathrm{CFL}$. Then there is a constant $c\_L$ such that for any integer $n\geq 2$, any set $Q\_n \subseteq L\_n = L \cap \Sigma^n$ and any integer $m$ with $n \geq m \geq 2$ there are $k \geq \frac{|Q\_n|}{c\_L n^2}$ strings $z\_i \in Q\_n$ with
>
> 1. $z\_i = w\_ix\_iy\_i$ for $i=1,\dots,k$,
> 2. $|w\_1| = |w\_2| = \dots = |w\_k|$,
> 3. $|y\_1| = |y\_2| = \dots = |y\_k|$,
> 4. $m \geq |x\_1| = |x\_2| = \dots = |x\_k| \> \frac{m}{2}$ and
> 5. $w\_ix\_jy\_i \in L\_n$ for all $(i,j) \in \[1..k\]^2$.

Applying it means to find $n,m$ and $Q\_n$ such that 1.-4. hold but 5. is violated. The application example given in the original paper is very verbose and is therefore left out here.

*At this time, I do not have a freely available reference and the formulation above is taken from a preprint of \[1\] from 1981. I appreciate help in tracking down better references. It appears that the same property has been (re)discovered recently \[2\].*

---

### Other Necessary Conditions

Boonyavatana and Slutzki \[3\] survey several conditions similar to Pumping and Interchange Lemma.

---

1. An “Interchange Lemma” for Context-Free Languages by W. Ogden, R. J. Ross and K. Winklmann (1985)
2. Swapping Lemmas for Regular and Context-Free Languages by T. Yamakami (2008)
3. The interchange or pump (DI)lemmas for context-free languages by R. Boonyavatana and G. Slutzki (1988)
> 36 votes

# Answer
There is no general method since the set non-context-free-languages is not semi-decidable (a.k.a. r.e.). If there was a general method, we could use it to semi-decide this set.

The situation is even worse, since given two CFL's it is not possible to decide whether their intersection is also a CFL.

Reference: Hopcroft and Ullman, "Introduction to Automata Theory, Languages, and Computation", 1979.
> 19 votes

# Answer
A stronger version of the Ogden's condition (**OC**) is the

### Bader-Moura’s condition (BMC)

> A language $L\subseteq \Sigma^\*$ satisfies BMC if there exists a constant $n$ such that if $z \in L$ and we label in it "distinguished" positions $d(z)$ and $e(z)$ "excluded" positions, with $d(z) \> n^{e(z)+1}$, then we may write $z = uvwxy$ such that:
>
> 1. $d(vx) \geq 1$ and $e(vx) =0$
> 2. $d(vwx) \leq n^{e(vwx)+1}$ and
> 3. for every $i \geq 0$, $uv^iwx^iy$ is in $L$.

We say that a language $L \in BMC(\Sigma)$ if $L$ satisfies the Bader-Moura’s condition.

We have $CFL(\Sigma) \subset BMC(\Sigma) \subset OC(\Sigma)$, so BMC is strictly stronger than OC.

Reference: Bader, C., Moura, A., A Generalization of Ogden’s Lemma. JACM 29, no. 2, (1982), 404–407
> 13 votes

---
Tags: formal-languages, context-free, proof-techniques, reference-question
---


# Question
Title: Time complexity and space complexity in recursive algorithm
```
"The designer of an algorithm needs to balance between space complexity and time
complexity." - Comment on the validity of the statement in the context of recursive
algorithms.

```

This is a question from my university's previous paper. But i couldn't find a decent answer. Actually i am confused about how can a developer minimize the time-complexity for any recursive function. I get that if there is a **tail-recursion** then space complexity can be minimized. But can't get the idea of time-complexity.

# Answer
> 6 votes
One thing comes in mind is memoization. Simple well studied problem for this is Fibonacci numbers, simple recursion is as follow:

```
fib(int n)
{
  if (n < 3)
    return 1;

  return fib(n-1) + fib(n-2);
}

```

But with memoization, we can use an auxiliary array to get rid of extra calls:

```
f[1]=f[2] = 1;
fib(int n)
{
  if (n < 3)
    return 1;

  if (f[n] == 0)
     f[n] = fib(n-1) + fib(n-2);

  return f[n];
}

```

This simple change, reduces the time from $\Theta(\phi^n)$ to $\Theta(n)$.

The memoization technique sometimes uses more memory, but very faster in time, and one of a tradeoffs that software developer should be care about it is this.

**Explanation of the memoization of Fibonacci numbers:**

First we create an array $f$, to save the values that already computed. This is the main part of all memoization algorithms. Instead of many repeated recursive calls we can save the results, already obtained by previous steps of algorithm. As shown in the algorithm we set the $f\[1\],f\[2\]$ to $1$.

In the first `if` we actually check whether we are in the start or not. But we can remove this `if` statement. But for make it simpler to read I left it.

In the second `if`, we check if the value of `fib(n)` is already computed or not. This prevents us from multiple call for the same number, for example suppose we want to compute `f(6)`, then in normal recursion we have the first recursion tree as shown in the following figure and in the memoization version we have the second tree. The reason is, in memoization we just compute the green vertices one time and then we save them into the memory (array $f$) and if needed we fetch them later.

In the following figure, green nodes are parts which are necessary to be computed (in this way), yellow nodes are precomputed ones, and red nodes are the nodes that are repeatedly computed in the first recursion.

As is clear from the image, in the normal case we have just precomputed `f(1)` and `f(2)`, but in the memoization case, all functions for less than $n-1$ are precomputed, and this causes exponentially smaller recursion tree. (In memoization number of red nodes is zero, which is exponential in the normal recursion).

---
Tags: algorithms, time-complexity, space-complexity
---


# Question
Title: Event Prediction through Machine Learning
I have a large data set consisting of ca. 40 categorical data items and a few interval data items (real numbers, less than 5 such items). Most categories should have a lot of values that repeat themselves over and over, and very few that appear very rarely. Some categories are also overcategories of others (like country and city). The outcome of each data is either 1 if the event occurred, or 0 if it did not occur.

The idea is to calibrate a machine learning model or a statistical model that can predict for every given data row the probability that the outcome is 1. The data set I will use will have at least 1 million rows.

Which machine learning approaches and statistical models will perform well on such a task? My initial thoughts are logarithmic regression and support vector machines (with extensions like random forest).

How do I deal with the interval data items? The easiest approach is obviously to convert different ranges into categories, which I think will not be a problem.

What libraries and tools can I use when my data set has a size of 10 GB? I am interested in tools/libraries that include machine learning algorithms but also statistical tools to help me find attributes with significant influence on the outcome. I can code in Java and C++ at the moment. I looked into Root, a data analysis tool from CERN for large data sets, and its machine learning module TMVA, but it can only handle real numbers and integers as input as far as I know.

# Answer
> 2 votes
As usual in these kinds of situations, the best way to find out which machine learning approaches will perform best is to try them out and see which ones work best. You can evaluate them using cross-validation.

It's unlikely that anyone here will be able to guess what will work best without knowing your data set. So I recommend that you get to work trying some likely candidates.

The Orange software tool is very convenient for trying multiple different machine learning algorithms on the same data set.

# Answer
> 1 votes
I agree with @D.W. that you need to try a number of models and compare the results. I would include Naive Bayes as well, but there are many other algorithms that could give you the results you're looking for. You'll want to compare the performance of the model on it's accuracy, as well as precision and recall, in addition to the other measures of a model's performance, such as kappa statistic and F-measure. As far as packages, Weka might also be a good option, especially if you're already familiar with Java. Though it doesn't have ordinal types that would be useful if you're discretizing the ranges into categories, there are ways of compensating for that.

Since you're working with such a large dataset, I'd recommend sampling down to a smaller subset of your data that can be easily run in memory to test the different packages and models. This may give you a better feel for the algorithms and tools that work best, help you troubleshoot any problems with your attributes (such as your categorical attributes and over-categories, as well as your ranges) without also having to deal with memory issues and other issues unrelated to your actual data mining task.

Good luck!

---
Tags: machine-learning, data-mining
---


title: A hard $n$-fold integral

text:
# Question
Title: A hard $n$-fold integral
Consider the $n$-fold integral $$ J = \int\_{\theta\_1 \in I\_1, \theta\_2 \in I\_2 \ldots, \theta\_n \in I\_n} d\theta\_n\ldots d\theta\_2 d\theta\_1 $$

whose intervals are defined by $$ \begin{align} I\_1 = \[0,1\] \\ I\_i = \[\max(c\_i,\theta\_{i-1}),1\] , 2\leq i\leq n \end{align} $$

and the $c\_i \in \[0,1\]$ are predefined **rational** constants. Given a rational $v\in \[0,1\]$,

> is deciding if $J=v$ NP-hard?

Informally , each $\max$ in the lower limits of the intervals leads to a two-way split in evaluating the integral, and thus to $2^{n-1}$ integrals that sum to $J$.

# Answer
This question received an answer on MO ; the integral can be computed in $O(n^2)$ time.
> 2 votes

# Answer
Your problem is a special case of the following: given a convex polyhedron defined by a set of linear inequalities, compute its volume. I believe that problem has been studied in the literature.

For instance, for related work on computing the volume of convex polyhedra/polytopes, see the following:

There is probably lots more work out there that might be relevant, but maybe this gives you a start. You might start by reading that work to see if there are any techniques you can adapt; and by doing a literature review with the above as an entry point into the literature.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: A variant of job assignment (scheduling) problem with variable time span
The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take anything from 5 mins to 10 mins. The list of jobs and their duration interval is given to the scheduler and the aim is to minimize the time all jobs would be finished. In interval scheduling, the job start and end time is given and the length is fixed. Here, the job can start and end anytime (should be done in whole though) but its duration (length) is not exactly known.

I searched the literature for this problem but couldn't find it. Is there any keywords I can use or any reference for this problem? Is it well-defined?

# Answer
> 2 votes
I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf. I hope it helps.

I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times. An algorithm for exponentially distributed times might be very different than an algorithm for a uniform distribution.

I think you will also need to trade off expected completion time vs. variance. With *known* completion times a decent approximation algorithm is Coffman's list scheduling algorithm: sort the jobs by length (longest to shortest) and then schedule greedily (next job starts as soon as a machine is free.) With uniform completion times you might try sorting by best-case completion times, expected completion times or worst-case completion times, and you would be getting different answers.

---
Tags: optimization, scheduling, process-scheduling, assignment-problem
---


title: Sabatier conjectures

text:
# Question
Title: Sabatier conjectures
While I was doing CLRS (3rd edition), I came across this question on page 629:

**Professor Sabatier conjectures** the following converse of Theorem 23.1:

> Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A \subseteq E$ that is included in some minimum spanning tree for $G$, let $(S,V -S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a safe edge for $A$ crossing $(S, V - S)$. Then, $(u,v)$ is a light edge for the cut.

Show that the professor’s conjecture is incorrect by giving a counterexample.

**Theorem 23.1**:

> Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V \- S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a light edge crossing $(S, V - S)$. Then, edge $(u,v)$ is safe for $A$.

Can anybody please give a proof or a counterexample to the conjecture also because I used to think that all safe edges added to the graph are light edges.

> **DEFINITIONS** :
> 1. **Cut (S ,V-S)** : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
> 2. **Light edge**:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
> 3. A cut **Respects** a set A of edges if no edge in A crosses the cut.
> 4. **Safe edge** is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

I have written most of the definition but for more queries you can also refer to CLRS chapter 23.

# Answer
> 1 votes
OK, here's a big hint.

Take any $G,A,S$ that satisfy the premises of the question. Now add a new vertex $v'$ to the graph, and draw an edge from $v'$ to one of the vertices of $A$ with a weight of your choice. (This means that $v'$ will be connected to the rest of the graph only by this one new edge; there are no other edges out of $v'$.)

What can you say about this new edge? Does it cross the cut? Is it a light edge? Is it a safe edge? Does this suggest any method for choosing the weight on that edge, to make things fortuitous to you? Hint: if you think about it (or try some examples), I bet you'll see how you can arrange things to get a violation of the conjecture.

People learn best by finding the solution for themselves (rather than reading someone else's solution), so I'm not going to post more than a hint. This hint ought to be enough to understand what's going on here....

---
Tags: graphs
---


# Question
Title: what does it mean by problem of size $0$?
I am having problems understanding a basic concept in CLRS, it is about worst case partitioning during quicksort --

> The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with $n − 1$ elements and one with $0$ elements.

What does it mean by subproblem of size $0$? But what I see is there will be two subproblems, one with size $n-1$ and another with size $1$. I fail to grasp the idea of $0$ size.

Can someone explain?

# Answer
> 6 votes
We're talking about algorithms to sort a list. Therefore, in this context, a problem of size 0 is a list of size 0, i.e., the empty list.

Quicksort splits a list of size $n$ into two sublists of size $m$ and $n-m-1$. They sum to $n-1$ (not $n$), because quicksort removes the pivot element: the pivot element is not included in either sublist. Therefore, the text you have quoted is correct. If one sublist has size $n-1$, then the other will have size 0 (not size 1).

---
Tags: algorithms, quicksort
---


# Question
Title: Where can a student learn image processing?
I am a student of computer science with interest in image processing. I have learned how to apply a few effects to images like making them grayscale, sketching them out of lines, etc.

I would like to learn more about the algorithmic techniques behind creative manipulation of images like making them sepia-tone, smudging them, etc.

**Can someone please point me in the right direction?** How do I learn the fundamentals of these algorithms?

# Answer
There are books on digital image processing which you can look into. Many common image manipulation techniques, such as smudging (usually known as blurring) are accomplished by image filtering, which is a process of applying a two-dimensional filter to an image: the value of each pixel in the new image is a linear combination of its original value and the original values of its neighbors. Sepia tone is an example of color manipulation: assuming the image is stored as RGB, this amounts to applying some carefully constructed mapping on the R,G,B values of each pixel. The mapping can be represented as a table $\\{0,\ldots,255\\}^3 \to \\{0,\ldots,255\\}^3$, or alternatively some formula can be applied instead.
> 5 votes

# Answer
I have been working on that very same thing recently, albeit for a very different purpose. Asides from SO, I have been referring to Google code examples, and forums related to the platform and language that I am working in. Sometimes, I found some information and techniques from Image Processing Online.

One technique that I found was particularly helpful, was to outline the processes that I wanted to do first and research each major programming decision, testing it as I go.

I hope this helps.
> 3 votes

# Answer
What you are referring to is not a branch of just image processing, but specifically digital image processing.

Also, linear filtering should help a bit.
> 3 votes

# Answer
you seem to be interested in image enhancement techniques such as used on Instagram to add "cool effects". these algorithms tend to be somewhat more advanced and proprietary. however for basic image manipulation which is the underlying basis for these algorithms, there are many places to start. here are a few:

* Image processing basics tutorials with java applets.
* Image processing basics tutorial Zip files of many tutorials. the overall site has a comprehensive list of resources eg books.
* CMSC 426 Image processing U Maryland/Jacobs 2003 there are many university classes some with very good online notes/resources
* Image processing in MATLAB Matlab is a leading mathematical package for image processing and math packages can simplify many algorithms. another leading package for image manipulation is Mathematica.
* Coursera, now a leading online course site, has a course on Image and video processing by Sapiro/Duke university.
* another option for the hacker types is taking an open source image processing program and reverse-engineering the code, ie learning the algorithms by looking at code and/or tweaking it. Gimp is a very full featured open source image processing program with many advanced effects, some as "plugins".

note most image techniques have many fundamental connections to linear/matrix/vector algebra and thats an important mathematical area to study for basic background.
> 2 votes

# Answer
If you already know the name of some specific image processing technique, Wikipedia has pretty good explanations -- such as "closing" in morphological image processing.

The computer vision wiki is a good place to read and write about computer vision stuff that doesn't fit into an encyclopedia format -- HOWTOs, example code, etc.

There exist many "type this, click there" tutorials on how to get a specific effect with a specific piece of software -- GIMP Tutorials, Kdenlive/Video effects, MATLAB Image Processing Toolbox, etc.

Many universities have classes in image processing or computer graphics or both; a few have an entire department dedicated to image processing. Some of them even have a web site that has lots of information about image processing. A few even record class lectures and post them online.
> 1 votes

---
Tags: reference-request, image-processing
---


title: About metric TSP instances

text:
# Question
Title: About metric TSP instances
Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that the resulting complete graph still satisfies the triangle inequality, and, of course, the TSP solution for the complete graph only uses original edges? Thank you.

# Answer
If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.
> 4 votes

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


title: The language of all borderless words

text:
# Question
Title: The language of all borderless words
Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please?

A word $w$ has a border $u$ if $u$ is both prefix and suffix of $w$ (and $u$ does not equal $\lambda$ or $w$).

# Answer
The borderless words are also known as *unbordered* or *bifix-free* ("A note on bifix-free sequences", PT Nielsen, in a paper as early as 1973).

The language of unbordered words is not even context-free, see the paper "Inverse star, borders, and palstars" by Ramparsad etal, in TCS with a preprint on ArXiv. The technique to obtain this result is Ogden's Lemma, an extension of classical pumping, and discussed elsewhere on this forum.
> 4 votes

---
Tags: regular-languages, pumping-lemma, word-combinatorics
---


title: 3 Colorability reduction to SAT

text:
# Question
Title: 3 Colorability reduction to SAT
I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.

Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, let the boolean variable $i\_r$ tell you whether the $i$-th vertex is red (or more precisely, that the $i$-th vertex is red when $i\_r = 1$). Similarly, define $i\_b$ and $i\_g$.

Suppose two vertices $i$ and $j$ were connected by an edge $e$. Consider the clause \begin{align} (\bar i\_r \vee \bar j\_r) \end{align} If we demand the clause is true, it means that the vertices cannot both be red at the same time. Now consider the bigger clause $\phi\_e$ \begin{align} (\bar i\_r \vee \bar j\_r)\wedge(\bar i\_b \vee \bar j\_b)\wedge(\bar i\_g \vee \bar j\_g) \end{align} which, if true, demands that the vertices $i$ and $j$ aren't both the same color. By itself, this clause is in 2-SAT.

For every edge $e \in E$, I now make a clause $\phi\_e$ of the above form and put them all together using $\wedge$'s \begin{align} \phi = \wedge\_{e \in E} \phi\_e \end{align} Thus, for the entire graph, I've come up with a 2SAT formula which is equivalent to 3 coloring.

This is obviously wrong, but I can't tell where I've screwed up.

# Answer
> 3 votes
With your modeling, setting $i$, $i\_r$, $i\_g$ and $i\_b$ to false for all vertices yields a solution of the SAT problem and this is not a solution of the graph coloring problem.

You need to add clauses to say that each vertex is blue or green or red, namely $(i\_r\vee i\_g\vee i\_b)$. Then it becomes a 3-SAT problem.

Note that if a vertex is assigned to more then one color, then we can take any of its colors and obtain a 3-coloring.

---
Tags: complexity-theory
---


# Question
Title: Howto formally go about proving that two LTL formulas are equivalent?
Do they need to "unwind" exactly to the same set of paths or does it suffice when one set is contained in the other ?

Or is it sufficient to argue that M,s satisfies both LTL formulas for any starting s and a model M, that is, reaching with both at "true" ?

**Generally.**

Let $M$ be any model. Further, let $s$ be any state $M$ might be in.

Let $\phi$ and $\psi$ be two LTL formulas.

If $\forall$ paths $\pi$ in $M$ starting at $s$ it holds that $\pi \models \phi \leftrightarrow \pi \models \psi $ then we say $\phi$ and $\psi$ are equivalent ($\phi \equiv \psi$).

More succinct

$(\pi \models \phi \leftrightarrow \pi \models \psi) \rightarrow (\phi \equiv \psi)$.

**Example.** *Prove that $\neg G \chi \equiv F \neg \chi$.*

If we can show that $(\pi \models \neg G \chi \leftrightarrow \pi \models F \neg \chi)$ we would have proven that $(\neg G \chi \equiv F \neg \chi)$. So we reduce to the former.

Step 1. We show that $(\pi \models \neg G \chi \rightarrow \pi \models F \neg \chi)$:

$\\{(\pi \models \neg G \chi) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\forall i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\\} \rightarrow \\{(\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\pi \models F \neg \chi)\\}.$

Step 2. We show that $(\pi \models F \neg \chi \rightarrow \pi \models \neg G \chi)$:

$\\{(\pi \models F \neg \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\\} \rightarrow \\{?\\}.$ *How do I get back?*

**Ok.** I can semantically understand that if for every model and any path in it, it is true eventually that $\neg \chi$ holds, it cannot be the case that generally for every model and any path in it $\chi$ will hold. How can I write this down formally?

Would for $\\{?\\}$: $\\{\neg (\forall i \geq 1, i \in \mathbb{N}. \pi^i \models \chi) \leftrightarrow (\neg (\pi \models G \chi)) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\pi \models \neg G \chi)\\}$ be a valid argumentation ? It looks different than Step 1. and anyway is there a rule to pull $\neg$ "out" from $\not\models$ this way ?

# Answer
The semantics of LTL is (initially) defined with respect to infinite computations. So in that sense, two formulas $\psi\_1,\psi\_2$ are equivalent if for every computation $\pi$ it holds that $\pi\models \psi\_1$ iff $\pi\models \psi\_2$.

So in this sense - yes, you need the formulas to unwind the same set of computations.

The semantics is then extended to Kripke structures in the $ALTL$ model, meaning that a formula is satisfied in a structure if all its computations satisfy the formula. However, testing for equivalence should be done with respect to paths.

As for proving formally the equivalence of formulas: if this is an exercise, it will probably be easiest to analyze the formulas and prove that a path satisfies the first iff it satisfies the second. However, if you are handling complex formulas, then the best approach will probably be via nondeterministic Buchi automata, by testing the equivalence of the automata that correspond to the formulas. In practice, there are tools to do just that, but doing it manually may prove quite time-consuming (as the problem is PSPACE complete).
> 7 votes

# Answer
You are in fact asking when two LTL formulas are equivalent. Two formulas are equivalent if they have the same truth value on all models. Given the definition, you should be able to answer your question yourself. Until you can do so, you haven't understood the definition, and so cannot expect to work with it other than mechanically.
> 3 votes

# Answer
Hint: LTL (on infinite strings) is equivalent to Büchi automata.

> There are transfer algorithms and many properties of Büchi automata are decidable.
> 2 votes

---
Tags: logic, proof-techniques, linear-temporal-logic
---


# Question
Title: Is lambda calculus suitable for expressing semantics of non-functional languages?
Would it be convenient to express semantics of imperative languages (e.g. C) and object-oriented languages (e.g. Java) with $\lambda$-calculus?

Or in the other words: is $\lambda$-calculus a suitable candidate for expressing semantics of all context-sensitive languages?

# Answer
There are two main approaches to giving the semantics of a language that I'm aware of. $\lambda$-calculus is a suitable candidate for expressing semantics in either approach. (Note that my knowledge of programming language semantics is restricted to a single course that I took in the mid-1990s, so I may be missing significant developments from the past 20 years.)

The first approach is *operational semantics*. According to David Schmidt's *Denotational Semantics*, Allyn&Bacon, 1986, page 2, operational semantics "uses an interpreter to define a language." In this sense writing a syntax-directed translator or attribute grammar as an extension of your parser gives an operational semantics to the language. Somewhat more abstractly, you might define a small-step operational semantics (like those on the Wikipedia page) where you define the meaning of each syntactic expression with respect to the actions it takes to transform a formally defined *state* or *environment*. The imperative programming language Scheme (which is notable for having "first-class" functions and continuations and as being the progenitor of JavaScript) has switched to an operational semantics in their most recent standard.

The other approach is *denotational semantics*. In denotational semantics you define a domain of program outcomes, and then for every syntactic structure in the program its meaning is a function that maps from an environment (a map from variable names to values) to the outcome domain. Scheme Revision5 and earlier have denotational semantics. The semantics of `set!` (Scheme's imperative construct) are given towards the end of Page 41.

I would guess that language semantics are largely used to prove the correctness of implementations, and in particular to clarify what optimizations are legal and under what circumstances those optimizations are legal. But my only experience in this domain is with respect to compiler optimizations and the memory semantics of C++11, which does not have a formal semantics.
> 5 votes

---
Tags: programming-languages, lambda-calculus, semantics
---


title: How to find polygons overlap reign

text:
# Question
Title: How to find polygons overlap reign
I have an algorithmic problem.

I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (`x` and `y` coordinates) and may contain up to `N` different vertices.

Assuming I have a set of `N` polygons, then for a new polygon `k`, how do I determine whether or not `k` overlaps with each one of the `N` polynomials in the set AND what is the overlapping reign percentage?

This is a purely algorithmic question but I plan on writing the algorithm in parallel using the CUDA platform, therefore any highly parallel solution would be preferred.

# Answer
> 1 votes
Building on top of *polygon intersection*, a naive process would just intersect each polygon with every other polygon and using the area of the polygons and the area of the intersection could compute what you call the overlapping reign percentage. This is easily parallel, and one could use a simple bounding box intersection to avoid computing the polygon intersect when the polygons's bounding boxes don't overlap.

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


# Question
Title: Why is this sequence of recurrence relevant?
I am learning how to solve the time complexity for the recurrence relation

$$ T(n) = 2T(n - 1) + n^2\text{, where }T(1) = 1 $$

The solution notes that I should begin by considering the following sequence:

$$ \text{Define }T^k(n) = T^{k - 1}(n + 1) - T^{k - 1}(n) \\ \text{and let }T^{(0)}(n) = T(n) $$

How is the sequence $T^k(n)$ relevant to solving my original recurrence relation? This just seems to be complicating the problem by defining an entirely new sequence.

# Answer
> 7 votes
## Calculus of differences

We make Kaya's nice observations slightly more formal. The sequence $T^k$ is the $k$th difference sequence of the original sequence $T$. You can think of it as a discrete $k$th derivative. For example, if $T$ is a $k$th degree polynomial then $T^k$ is constant. We will see below what happens when $T$ is exponential.

For a sequence $T$ (all sequences range over the positive integers), let $\Delta(T)$ be defined by $$ \Delta(T)(n) = T(n+1)-T(n). $$ So $T^k = \Delta^{(k)}(T)$, that is $T^k$ is obtained by applying $k$ times the operator $\Delta$. The operator $\Delta$ has an inverse, which corresponds to indefinite integration: $$ T(n) = T(1) + \sum\_{k=1}^{n-1} \Delta(T)(k). $$ If we are only given the sequence $\Delta(T)$ then we don't know $T(1)$, and we can think of it as a constant of integration. For concreteness, define another operator $\Sigma$ given by $$ \Sigma(T)(n) = \sum\_{k=1}^{n-1} T(k). $$ The "fundamental theorem of calculus" then states that $$ \Delta(\Sigma(T)) = T $$ and $$ \Sigma(\Delta(T)) = T - T(1). $$ Another useful property of the operators $\Delta$ and $\Sigma$ is their linearity.

Furthermore, we have the nice formula $$\Delta^{(k)}(n^k) = k!,$$ which can be proved by induction on $k$. This formula also implies that $$\Delta^{(k+1)}(n^k) = 0.$$ In fact, this is true for any polynomial of degree at most $k$. Conversely, $\Sigma(n^k)$ is some polynomial of degree $k$.

We can do the same for exponentials: $$ \Delta(c^n) = (c-1)c^n, \quad \Sigma(c^n) = \frac{c^n-1}{c-1}.$$

Finally, it will be useful to use the shift operator $S$ given by $$S(T)(n) = T(n+1).$$ This operator commutes with $\Delta$: $S(\Delta(T)) = \Delta(S(T))$.

## Solving the recurrence

Now to the problem at hand. The sequence $T$ satisfies $$S(T) = 2T + (n+1)^2. $$ Taking the third difference, we get $$S(\Delta^{(3)}(T)) = 2\Delta^{(3)}(T).$$ Here we used the linearity of $\Delta$, the commutativity of $\Delta,S$, and the fact that the third derivative of $(n+1)^2$ vanishes. We can conclude that $$ \Delta^{(3)}(T) = C 2^n, \quad C = \Delta^{(3)}(T)(1)/2. $$ We now want to repeatedly apply the operator $\Sigma$. Each time we apply $\Sigma$, we get some constant of integration. After the first time, we get $$ \Delta^{(2)}(T) = C 2^n + C\_1 $$ for some $C\_1$, using $\Sigma(2^n) = 2^n-1$. While we can express $C\_1$ in terms of $T$, it is better not to. The next time we apply $\Sigma$, $C\_1$ turns into a linear terms, and so $$ \Delta^{(1)}(T) = C 2^n + C\_1 n + C\_2 $$ for some $C\_2$. The next time we apply $\Sigma$, $C\_1 n$ turns into a quadratic term, and so $$ T = C 2^n + P\_2 $$ for some quadratic polynomial $P\_2$.

It remains to find $C$ and $P\_2$. Recall that $C = \Delta^{(3)}(T)(1)/2$. Kaya calculated $\Delta^{(3)}(T)(1) = 12$ and so $C = 6$. Therefore $$ T = 6 \cdot 2^n + P\_2. $$ The first few values in $T$ are $1,6,21$, and so $P\_2(1) = -11$, $P\_2(2) = -18$, $P\_2(3) = -27$. Write $P\_2 = B\_2 n^2 + B\_1 n + B\_0$, and so $\Delta^{(2)}(P\_2) = 2B\_2$. On the other hand, $\Delta(-11,-18,-27,\ldots) = (-7,-9,\ldots)$ and so $\Delta^{(2)}(-11,-18,-27,\ldots) = (-2,\ldots)$, and we conclude that $B\_2 = -1$. We can now calculate $B\_1 n + B\_0 = (-10,-14,\ldots)$, and so $B\_1 = -4$ and $B\_0 = -6$. We can conclude that $P\_2 = -n^2 - 4n - 6$, and we get Kaya's formula.

## Generalities

More generally, if $T$ is a sequence satisfying $T(n+1) = c T(n) + P\_k(n)$ for some polynomial $P\_k$ of degree $k$, then the very same method shows that $$ T(n) = C c^n + P\_{k+1}(n) $$ for some constant $C$ and polynomial $P\_{k+1}$ of degree $k+1$. In order to find $C$ and $P\_{k+1}$, we can either follow the route used above - express $C$ in terms of $c$, $k$ and $\Delta^{(k+1)}(T)(1)$ - or calculate $T(1),\ldots,T(k+2)$ and solve linear equations in the unknowns $C$ and the coefficients of $P\_{k+1}$.

Even more generally, we can handle recurrences of the form $T(n) = c\_1 T(n-1) + \cdots + c\_l T(n-l) + P\_k(n)$. As before, after applying $\Delta^{(k+1)}$, the inhomogeneous terms $P\_k$ disappears, and we can solve the resulting recurrence relation. Applying $\Sigma^{(k+1)}$, we will get an "error term" of the form $P\_{k+1}$ as before.

General recurrence relations have solutions which are sums of expressions of the form $n^r c^n$ for integer $r \geq 0$, so we also need to calculate the (iterated) discrete integrals of these functions; the result of applying $\Sigma$ once is $P\_{r+1}(n) c^n$ for some polynomial $P\_{r+1}$ of degree $r+1$, and so applying it $k+1$ time we obtain $P\_{r+k+1}(n) c^n$ for some polynomial $P\_{r+k+1}$ of degree $r+k+1$. As before, we can find the coefficients of all polynomials by solving linear equations, given enough values of the sequence $T$.

# Answer
> 3 votes
First we write out recurrence relationships for the first few $T^{k}$ functions $k\in\\{0,1,2,3\\}$. $T^{0}$ is given. $$ T^{0}(n)=2T^{0}(n-1)+n^{2} \\ T^{1}(n)=2T^{1}(n-1)+2n+1 \\ T^{2}(n)=2T^{2}(n-1)+2 \\ T^{3}(n)=2T^{3}(n-1) $$

Then we compute initial conditions for $k\>0$. These aren't too tricky as they only require computing up $T^{k-1}(2)$ for finding what $T^{k}(1)$ equals. $$ T^{1}(1)=5 \\ T^{2}(1)=10 \\ T^{3}(1)=12 \\ $$

Now the function $T^{3}$ is trivial to express in closed form: $$ T^{3}(n)=3\cdot 2^{n+1} $$

I admit I do not know why this next step is valid formally, however an ansatz would lead me to try working backwards like this: $$ T^{2}\overset{?}=3\cdot 2^{n+1}+c \\ 3\cdot 2^{n+1}=T^{2}(n+1)-T^{2}(n) \\ 3\cdot 2^{n+1}=3\cdot 2^{n+2}+c -(3\cdot 2^{n+1}+c) \\ 3\cdot 2^{n+2}=3\cdot 2^{n+2} $$

Since this seems to confirm that the guess was right, we look to the initial conditions and solve for $c=-2$. For the next step, $T^{1}(n)$, the auxiliary function would be 1 degree higher in $n$ so again we verify that $T^{1}(n)\overset{?}=3\cdot 2^{n+1}-2+(an+b)$ fits the definition of $T^{2}$, and since it does the value of $T^{1}(1)$ requires that $b=-3$ and $T^{1}(2)$ requires that $a=-2$. Thus we find that $T^{1}(n)=3\cdot 2^{n+1}-2n-5$. Finally for $T^{0}$ the guess is something of the form $T^{0}(n)=T^{1}(n)+(dn^{2}+en+f)$. Again, after verification with definitions of $T^{k}$, looking at the first few values of $T$ we discover that $d=-1$, $e=-2$, and $f=-1$. This leads to the conclusion that: $$ T(n)=3\cdot 2^{n+1}-n^{2}-4n-6 \\ $$

Some quick checks to verify correctness: $$ T(1)=3\cdot 2^{2}-1^{2}-4-6=12-1-4-6=1 \\ 2T(n-1)+n^{2}=2(3\cdot 2^{n}-(n-1)^{2}-4(n-1)-6)+n^{2} \\ = 3\cdot 2^{n+1}-2(n-1)^{2}-8(n-1)-12+n^{2} \\ = 3\cdot 2^{n+1}-2n^{2}+4n-2-8n+8-12+n^{2}\\ = 3\cdot 2^{n+1}-n^{2}-4n-6 = T(n) \\ $$

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: What mathematics can be interesting for these CS areas?
For my CS degree I have had most of the "standard" mathematical background:

* Calculus: differential, integral, complex numbers
* Algebra: pretty much the concepts up until fields.
* Number Theory: XGCD and related stuff, mostly for crypto.
* Linear Algebra: up until eigenvectors/eigenvalues
* Statistics: probabilities, testing
* Logic: propositional, predicate, modal, hybrid.

My main interests in the CS area are security, cryptography and artificial intelligence. I was wondering if there are any suggestions for mathematical topics that could be interesting for these areas, particularly for AI as it is not my main field of study at the moment.

# Answer
For the field of A.I. and machine learning, I would recommend you to explore and learn more about these topics:

* Statistics
* Probability
* Stochastic processes
* Bayesian Data Analysis
* Convex Optimization
* Graph Theory

With your math background, you could easily pick any good machine learning book and learn the required math that you don't have as you go. Kevin Murphy's new book, Machine Learning: A Probabilistic Perspective, covers most of these topics and it serves as a good introductory textbook to machine learning.

I personally learned a lot from Dephne Koller's book, Probabilistic Graphical Models. It also covers most of the previously mentioned topics, but, as the book's name suggests, it focuses on graphical models.

Although both of these books have enough math to keep you busy for a while, you might find "The Elements of Statistical Learning", by Hastie et al. more useful if you want to focus more on the mathematical part of the machine learning.
> 10 votes

# Answer
AI is 99% statistics these days. Learn about probability, and how it intersects with graph theory (bayes nets, etc.).

As for cryptography, if you've got number theory, the only real thing I can think of to extend this is group/field theory. In particular, learn about eliptic curves, but I doubt you'd find a math class that taught that that wasn't specifically a crypto class.
> 5 votes

---
Tags: artificial-intelligence, cryptography, discrete-mathematics
---


# Question
Title: Deciding between two algorithms with similar runtime in two parameters
Let's say I have a problem which depends on two variables, $m$ and $n$. I also have two algorithms for solving the problem. How do I decide which algorithm to use?

For example, say I have an array of unique numbers $A$, not necessarily sorted, and a second sorted array $B$. I want to create a third array $C$ which contains how many times each number in $A$ appears in $B$.

Algorithm 1 runs in time $O(m \lg n)$ and algorithm 2 in $O(m \lg m + n)$.

It seems to me I would need to divide into three cases:

1. $n=\Theta(m)$
2. $n\gg m$
3. $m \gg n$

How would I generally proceed from here?

# Answer
A better comparison is $n$ versus $m\log m$. When $n = \Theta(m\log m)$, both algorithms have running times $\Theta(m\log m)$. When $n \gg m\log m$ (or rather $n = \omega(m\log m)$, the second algorithm has running time $\Theta(n)$ and the first one has running time $\Theta(m\log n) = o(n)$ since $m = o(n/\log n)$. When $n \ll m\log m$ (or rather $n = o(m\log m)$) the second algorithm has running time $\Theta(m\log m)$ and the first one has running time $\Theta(m\log n) = o(m\log m)$.
> 6 votes

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Find out the largest LCM of the partitions of n
I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$.

Example: $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) \< \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.

The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5. More examples(Let g(n) be the answer that I want to get): g(11) = 30 g(12) = 60 g(13) = 60

I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.

# Answer
It seems that this a competition problem. Your best bet is to pre-calculate maximum values for all numbers(250 isn't very big) and store it into an array. That would be the best bet as this can give you timing near to zero.
> 4 votes

# Answer
For partitioning into two numbers the product is maximized when the two variables are closest to one another: $$g(n) \equiv \mathrm{max} \\{ xy : x + y = n\\} = \left\\{ \begin{array}{clll} \frac{n}{2}\cdot \frac{n}{2} &=& \frac{n^2}{4} & \text{even} \\ \frac{ n-1}{2 }\cdot \frac{ n+1}{2 } &=& \frac{ n^2-1}{4 }& \text{odd} \end{array}\right. $$ This is called convexity.

Since we are looking for LCM and not product, call that result $f(n)$.

In the even case, we should be careful that $\mathrm{LCM}(n,n) = n$ so we need to find the next best one: $$\left(\frac{n}{2} -1 \right)\cdot \left(\frac{n}{2} +1\right)= \frac{n^2}{4}-1$$ Two consecutive numbers will have an LCM of at most 2.

In the odd case, two consecutive numbers will be relatively prime.

* f(9) = 4\*5 = 20
* f(8) = 3\*5 = 15
* f(10) = 3\*7 = 21

Here's a draft answer:

$$f(n) \equiv \mathrm{max} \\{ xy : x + y = n\\} = \left\\{ \begin{array}{cr} \frac{n^2}{4}-1 & 0 \mod 4 \\ \frac{n^2}{4}-4 & 2 \mod 4 \\ \frac{ n^2-1}{4 }& 1,3 \mod 4 \end{array}\right. $$

Because the integers are discrete, and the irregularities of the LCM, you have to make all sorts of corrections.

* for small $n$ this is certainly wrong
* the answer seems to depend on the factors of $\frac{n}{2}$ for even values of $n$

You may not want to follow this logic to several variables - and there may be a slicker totally different way. At least we can see some of the continuity of the numbers you are generating.
> -1 votes

---
Tags: algorithms, number-theory
---


title: Contracts for Java Bytecode

text:
# Question
Title: Contracts for Java Bytecode
**Introduction**
For a paper I need contracts, which are also referred to as Design by Contract (DbC), and conceptually go back to Hoare\[2\]. For my work I need to apply contracts to Java bytecode. The question is only about using contracts on Java bytecode, nothing more.

If you ask, why do you want to use contracts on Java bytecode, there is a reason. The reason is that I use a Java extension. This Java extension takes source code consisting of extended Java code, from which it generates bytecode. I want to use this Java extension and additionally I want to use contracts. The extension doesn't support contracts. So I have my extended Java code, I apply to it the compiler of the Java extension and I get Java bytecode. On this resulting bytecode I want to apply contracts.

The Java extension is called Object Teams\[4\], also called eclipse object teams. The Java extension allows to use dynamic collaborations and aspects, which are not part of regular Java code.

Right now I only need a hack or workaround to get one or two small examples working.

**My idea so far:**
This is irrelevant to the question. But it shows that my current plan is cumbersome and I need a better solution (thus the question). Also, perhaps someone has worked with JML/OpenJML and might know how to do this plan but better.

There is a tool for contracts for Java language. The tool is called java modeling language(JML)\[3\]\[5\]. The tool does not support contract for Java bytecode. The tool only supports contracts on Java source code. I want to rewrite part of the tool to support contracts on java bytecode (a solution to my question but a cumbersome one).

Currently there is only one working version of the java modeling language(JML), which is called OpenJML\[6\]. I plan to use OpenJML on Java bytecode (remember, OpenJML doesn't support contracts for bytecode, only contracts for Java source code). I don't want to use contracts on any bytecode. I want to use contract on bytecode that is generated by a Java extension. (The Java extension is called ObjectTeams, but this is irrelevant for the question).

(Annotations mean annotations that are part of the Java language, e.g., "@Overrides".)

The approach would be to search for specific annotations in the bytecode that is generated by a Java extension. Those specific annotations specify contracts. I have to look for the specific annotations in the bytecode (bytecode that is generated by a Java extension), compile them to Java guard expressions, i.e., code that throws an exception if the contracts are not honored. I can get the compiled Java guard expression by using the library behind OpenJML. Then I need to add the byte code of the Java guard expression at the place where I found the specific annotations that represent contracts.

**My question:**
Using OpenJML seems possible, but difficult to achieve. Right now I just need a solution that works for one or two small examples, so the solution can be a hack or just a temporary solution. As my approach via OpenJML is probably difficult to achieve and further will take quite some time, I look for different solutions.

**Question:** *What options would you recommend to apply contracts (design by contract) for java bytecode?*

Requirements:

1. a up to date tool or library (i.e., not a project where development has ceased or stopped three years ago)
2. ideally, it should be straightforward to use the tool or library (i.e., not a project with zero or almost no documentation)

## --

---

***Update / Clarification:***

* I forgot to mention that don't need any form of static checking. I
only need to check that the contracts hold during run time. Further I only need to use very basic contracts (pre- and postcondition,
invariants) applied to only a few methods of my program.
* As Dave as pointed out in the comments, there may be another option to apply contracts together with Object Teams. This would mean modifying or extending Object Teams and the CoreJDT module of Object Teams (it's in the comments).
* I also got a reply from the creator of Object Teams that using JML and Object Teams together via JDT isn't an easy fix.

References:

B. Meyer. Applying Design by Contract. Computer, 25(10):40{51, 1992.

\[2\] C. A. R. Hoare. Proof of correctness of data representations. Acta Informatica, 1(4):271–81, 1972.

\[3\] Lilian Burdy, Yoonsik Cheon, David R. Cok, Michael Ernst, Joseph R.Kiniry, Gary T. Leavens, K. Rustan M. Leino, and Erik Poll. An overviewof JML tools and applications. International Journal on Software Tools for Technology Transfer (STTT), 7(3):212–232, 2005.

\[4\] http://www.eclipse.org/objectteams/

\[5\] http://www.eecs.ucf.edu/~leavens/JML//index.shtml

\[6\] http://jmlspecs.sourceforge.net/

# Answer
I recommend you look at BML. It is like JML, but for Java bytecode. It allows you to specify contracts (preconditions, postconditions, data structure invariants) at the bytecode level. I think the tools Umbra, JACK, and the Mobius program verification environment support BML, and the Mobius project is building tools that work with BML. See, e.g., the following papers:

You might also look at BCSL and JVer, which are intended for verifying Java bytecode, and JML2BML, which translates JML to BML:

You might also want to ask on the JML mailing list, as they might have other recommendations/suggestions.

Other possibly related work: JINJA (Tobias Nipkow), Claire Quigley's work. And, you might look at the proceedings of the BYTECODE workshop over the past decade, as it presents research on verification and analysis of bytecode (including Java bytecode).

Caveat/disclaimer: Be warned that you might not find an equivalent of JML for Java bytecode that's as convenient and easy-to-use and well-supported as JML. The reason is that contracts are designed to be used and understood by programmers. The natural place to put contracts is on the source code, because that's a lot easier for programmers to use; putting contracts on bytecode is a more niche requirement.
> 3 votes

---
Tags: programming-languages, formal-methods, object-oriented, java
---


# Question
Title: Coordinated Attack Problem Different Requirements
There is a famous Coordinated Attack Problem. Let define a simple message-passing system $S$ with requirements

* Uniform Agreement: No two processes decide dierently.
* Validity:

(a) If all processes start with 0, then no process decides 1.

(b) If all processes start with 1, and there are no failures, then no process decides 0.

* Termination: All nonfaulty processes eventually decide.

System $S$ consisting of two processes $p$ and $q$ connected by a bidirectional communication link such that (a) processes proceed in synchronous rounds, (b) processes do not fail, and (c) any number of messages can be lost.

It's well known that system $S$ cannot satisfy all above requirements, therefore let consider different requirements.

* Weak Termination: If there are no failures, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

> All processes eventually decide when there is no failures, so when inputs are $0$ and $0$ and no failures, both generals decide $0$. By dropping one of the message I cannot ensure the termination, therefore the standard reasoning doesn't work here.

* Unanimous Termination: If any process decides, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

> It's also very tricky requirement. Assume the both inputs are $0$ and $0$ and no failures than both decide $0$, let drop the message from $P\_1$ to $P\_0$, regarding to $P\_1$ it is the undistinguishable execution, therefore $P\_1$ still decide $0$ and according to unanimous termination, someday $P\_0$ will decide the same $0$ according to agreement, noq according to the standard schema, change the input of $P\_0$ to $1$ and this undistinguishable execution to $P\_0$, so the same agreement and so forth we reach a contradiction, no solution.

I am sure if it's correct. In addition the case with weak termination I don't know how to solve, even if it's solvable.

# Answer
This looks like the Byzantine generals problem. There's a lot written on that subject; I suggest you start by reading the available literature and material on that subject.

I'm not entirely clear on you mean by "solvable in system S" (system S says processes don't fail, but the weak termination condition refers to failures, so what's going on there?), so I can't confidently answer that part of your question.

There's an obvious algorithm for the case of two parties:

* Each party continually broadcasts a message saying "my input is X" (fill in X with whatever its input bit is).
* Whenever you receive one of those messages, you respond with an acknowledgement describing your input, what you received from the other party, and what you will output; then you immediately produce the appropriate output and halt.
* If you receive an acknowledgement message and have not halted yet, then produce the appropriate output and halt.

It looks like this satisfies all three of your requirements, including weak termination, assuming that messages can be dropped/lost but are not modified in transit and no forged/fake messages are inserted by the network.
> 1 votes

---
Tags: proof-techniques, distributed-systems
---


# Question
Title: Why is software emulation of alternative architectures so hard/slow?
I recall hearing briefly about this back in one of my CS courses on hardware, but I can't recall many of the details, nor can I find anything online that talks about it. A search on Google only yields a bunch of pages about Android emulators and people complaining that PCSX2 is slow. I'd like to know, in general, why software emulation of hardware is inefficient.

Can anybody point me to a good resource or explain briefly here?

# Answer
> 2 votes
If the underlying machine is similar to the simulated one, you can run most code natively (no speed loss unless there are hard to handle instructions or other characteristics, this is the "virtualization" business). If it is very different, you have to really simulate each instruction (for a cost of half a dozen or so native instructions for a typical machine). If it is important enough, you can use tricks like JIT compilation to native code to speed it up.

---
Tags: computer-architecture, simulation
---


# Question
Title: Iterative and/or tail-recursive implementations of merge sort?
I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented in an iterative style?

In general how can a recursive algorithm converted into an iterative and tail-recursive algorithm? What are the possible pros and cons of this conversion?

# Answer
> 6 votes
An iterative implementation is easy: you just introduce an explicit stack (instead of using the call stack as the implicit stack). You can always convert any recursive algorithm to be in iterative form by using an explicit stack; each recursive call is translated into pushing something onto the stack.

However, I don't know of any reason why you'd want to do that, in this case; the resulting algorithm just becomes harder to understand. The amount of stack space used by merge-sort is $O(\lg n)$, where $n$ is the length of the list, so you're not going to exhaust the size of the available stack.

Merge-sort is not purely tail-recursive. First of all, the result of a call to merge-sort is not the result of either recursive call; the results of the two recursive calls must be further processed (by merging the sorted sublists). Second of all, merge-sort contains two recursive calls, so even if there were some way to convert the last call to a tail-call (there isn't), you'd still be left with one other recursive call inside the body of the function. So, no, merge-sort is not tail-recursive. And there's little or no benefit to try to rewrite it in a form that is tail-recursive.

(Technically speaking, just as any algorithm can be transformed to be iterative, anything can be transformed to be tail-recursive form by using continuation-passing style. This includes merge-sort. Nonetheless, in this case there is no reason why anyone would want to do that. It's unlikely to make the code noticeably faster, and it's sure to make the code harder to understand. Therefore, this is a technicality that can be safely ignored. If you don't know what continuation-passing style is, don't worry about it, you can just pretend that merge-sort cannot be made tail-recursive, and that'll be close enough.)

# Answer
> 1 votes
As DW says, the iterative version is fairly easy. The way to convert recursion into iteration is by using a stack, which emulates the call stack for function calls.

As I alluded to in my comment, to convert it to tail-recursive form, you'll need a language with first-class functions so that you can build continuations.

In CPS, you add an extra argument to each function, which is the continuation, representing the instructions to do next.

Each recursive "base case" of (lambda x (baseCase)) turns into (lambda x k (k baseCase)) i.e. you pass the base case value as the argument to the continuation.

Each recursive call then turns into "recursively call this function after adding another instruction to the continuation." You directly call your function recursively, but pass a different value of k (the continuation) which is a new function redefined to incorporate the operations you do in the recursive case.

There's more in this Wikipedia article.

# Answer
> 0 votes
I find iterative merge sort somewhat easier to read than the recursive version.

I Googled "iterative merge sort" and found this c# iterative implementation.

Recursive merge sort is somewhat more cache friendly than iterative merge sort. There is a *big* difference between the order in which this iterative merge sort algorithm touches data elements and the order in which recursive merge sort touches data elements. (Although merge sort isn't very cache friendly compared to an in-place sort like randomized quick sort. And your version of `merge_parts` does an extra array copy which is yet less cache friendly.)

So something like this (I'm sure I've got some off-by-one errors, but this is the basic idea):

```
// each outer loop iteration merges together subarrays that are twice as large
for (subLength = 1; subLength < arrayLength; subLength = subLength * 2):
  swap(inputArray, outputArray)
  // iterate through entire array (which is "cache unfriendly")
  for (i = 0; (i + subLength) < arrayLength; i = i + (2 * subLength)):
    end = min(i + (2*subLength), arrayLength)
    mid = i + subLength
    mergeParts(inputArray, outputArray,
               i, mid, end)

```

and `mergeParts` here merges `inputArray[i...mid-1]` with `inputArray[mid...end-1]` placing the result in `outputArray[i...end-1]`.

---
Tags: algorithms, sorting, recursion
---


# Question
Title: Is this NP-hard: min-weight n-clique in a complete n-partite graph
I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the graph. I would like to know whether the problem can be solved in polynomial time.

More details of the terms:

**Complete $n$-partite graph**: a graph in which vertices are adjacent if and only if they belong to different partitions (wikipedia). There are $n$ partitions in the graph. (In my case, each partition contains exactly $n$ vertices.)

**Minimum weight clique**: Every edge in the graph has a weight. The weight of a clique is the sum of the weights of all edges in the clique. The goal is to find a clique with the minimum weight.

Note that the size of the required clique is $n$, which is the largest clique size in a complete $n$-partite graph, and it is always attainable.

I have searched for hours and there seems no research tackling the exact problem. Any suggestions?

# Answer
> 3 votes
The decision version of your problem (whether there is a clique of weight at most something) is NP-hard, by reduction from 3-SAT. Let $\varphi$ be a 3CNF formula with $m \geq 7$ clauses. We create an $m$-partite graph. Each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause, and $m-7$ dummy vertices. All edges touching a dummy vertex have weight $1$. Edges connecting two conflicting assignments also have weight $1$. Edges connecting two non-conflicting assignments have weight $0$. The graph has a clique of weight $0$ iff $\varphi$ has a satisfying assignment.

We can also get a hardness of approximation result this way. Given a 3CNF formula $\varphi$ with $m \geq 7$ clauses, we create an $(m+1)$-partite graph. There is a part corresponding to each clause, which has $8$ vertices corresponding to all assignments to the clause, and $m-7$ dummy vertices. In addition, there is a part with $m+1$ special vertices. All edges touching a dummy vertex have weight $m^2$. Edges connecting two conflicting assignments also have weight $m^2$. Edges connecting two non-conflicting assignments have weight $0$. Edges connecting satisfying assignments (for clauses) and special vertices have weight $0$. Edges connecting non-satisfying assignments and special vertices have weight $1$. The minimal clique in this graph has weight equal to the minimal number of unsatisfied clauses in any assignment to $\varphi$. Therefore for every $\epsilon \> 0$ it is NP-hard to decide, for $(m+1)$-partite graphs, whether the minimal clique has value $0$ or at least $(1/8-\epsilon)m$. In fact, by modifying $\epsilon$ slightly we get the same result for $m$-partite graphs.

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


# Question
Title: Electrical resistance of expander graphs
Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper and lower bounds in terms of $n,d$?

# Answer
> 2 votes
Next time you ask a question you should try to google it first. I googled "electrical resistance expander graph" and the very first result was a paper stating that $d$-regular graphs have resistance $\Theta(1/d)$.

---
Tags: graphs, random-walks, expanders
---


title: Consensus and Perfect Failure Detector

text:
# Question
Title: Consensus and Perfect Failure Detector
I try to get a better understanding about Failure Detectors in the field of Distributed Computing.

Let consider the algorithm for reaching consensus with Perfect Failure Detector, it's named as Perfect FDAgreement in the textbook *Distributed Algorithms by Nancy A. Lynch* on the page 679. In addition, it can be found in the following presentation Asynchronous Network Computing with Process Failures. Slide 16.

The basic idea of the algorithm is each process $P\_i$ attempts to stabilize two pieces of data: a vector val, indexed by $\\{1,2,...,n\\}$, with values in $V \cup \\{null\\}$.$val(j) = v \in V$, it means that $P\_i$ knows that $P\_j$’s initial value is $v$. A set stopped of process indices. If $j \in stopped$, it means that $P\_i$ knows that $P\_j$ has stopped.

The question is as one of the step of the algorithm *every process that receive a message ignores it from the processors it has already placed in stopped.*

I don't understand why we need this, even we don't ignore the message from stopped process it won't broke anything. This case may occur when $P\_j$ sends a message to $P\_i$ and crashes, FailureDetector see the crash and informs the process $P\_i$ that $P\_j$ is stopped after that $P\_j$'s message reaches $P\_i$, but this message contains a correct data, and it doesn't change the state of $P\_j$ in stopped set, because only INSERT (insert new values that previously was null) and COMPARE are allowed operations on the set.

If you see the real reason for ignoring messages from the crashed process please share it with us.

**Addendum**: Unfortunately I didn't find any use of the aforementioned fact (ignoring message from crashed node) in the algorithm (Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch).

In addition, in main papers Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors forasynchronous systems and Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus slightly different algorithm can be found without ignoring messages from crashed nodes.

# Answer
> 1 votes
It could be that the analysis works either way, or perhaps the analysis (or the algorithm) could be slightly modified to handle this change. I suggest you go over the correctness proof of the algorithm and see where this step is used (if at all).

---
Tags: distributed-systems
---


title: Remove divisors from a set of integers

text:
# Question
Title: Remove divisors from a set of integers
I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \\{y \in S : \forall d \in S . d \nmid y \\}$.

How do I do this efficiently?

I can see how to do it in $\Theta(|S|^2)$ time, by examining all pairs of elements of $S$ and keeping only the ones that don't have any divisor in $S$. Can it be done substantially faster? (For simplicity, I'm willing to assume that all standard integer operations---addition, multiplication, division, etc.---can be done in $O(1)$ time. Yes, I know this is an imperfect approximation, but if it makes your answer cleaner, I'm fine with it.)

# Answer
Let me first repeat my remark: in the application you have in mind (finding the maximal LCM of a partition of $n$), you can assume that the elements of $S$ come factored, and so can represent them as vectors of non-zero integers corresponding to the powers of the various primes. The problem of computing all maxima in this setting has been considered by Kung, Luccio and Preparata, but they only give efficient algorithms in the case when the dimension (number of different primes) is constant, which is not your case. They also give a lower bound of $\Omega(n\log n)$. The problem has took up in the database literature under the name of Skyline \- perhaps these people have practical algorithms which could be useful here.
> 3 votes

# Answer
Here's a divide-and-conquer algorithm that in principle might improve slightly upon the naive approach, but in practice doesn't seem much better. It is inspired by one of the techniques used by Kung, Luccio, and Preparata, but without adopting some of their other clever methods.

* If the set $S$ is small (say, fewer than 10 elements), use the naive approach. Otherwise, initially set $p=2$ and do the following:
* Split the set $S$ into $S\_0,S\_1$, where $S\_0 = \\{x \in S : p \mid x\\}$ is the subset of elements that are a multiple of $p$ and $S\_1 = \\{y \in S : p \nmid y\\}$ is the rest of $S$.
* Recursively compute the solution for each of $S\_0,S\_1$, obtaining $T\_0,T\_1$, but replacing $p$ with the next prime after $p$ for the recursive call. (Thus, each recursive call advances to the next prime; if you are $i$ deep in the recursion tree, you use the $i$th prime as your $p$.)
* Now we want to merge $T\_0,T\_1$. To do this, we note that no element of $T\_0$ can be a divisor of $T\_1$, so we only need to check each element of $T\_1$ to see whether it is a divisor of $T\_0$. The running time for the merge operation is $O(|T\_0| \cdot |T\_1|)$.

However, this doesn't seem to do all that much better than the naive approach, sadly.

Reference:

* On finding the maxima of a set of vectors. H.T. Kung, F. Luccio, F.P. Preparata. Journal of the ACM, vol 22 no 4, pp.469--476, 1975.
> 2 votes

---
Tags: algorithms, integers, number-theory
---


# Question
Title: Subset product problems (one "easy" one "difficult")
This question is from an exam preparation that I have to demonstrate to my teacher to show him that I understood the topic thoroughly .

Given a set $S$ of integers with $n$ elements, an integer $z$ and an integer $k \leq 2$, sketch an algorithm that checks whether there are $k$ elements in $S$ of which the product equals $z$.

I need to find two algorithms: one that solves the problem in $O(n^k)$ and the other one that solves the problem in $O(n^{k-1}\log n)$.

How can I do this? Could you help me with some hints? Thank you!

# Answer
> 3 votes
**Hint1:** How many subsets of $k$ elements can be selected from an $n$-elementary set? Try to enumerate them efficiently and check if their product equals $z$ alongside.

**Hint2:** Suppose you know (enumerate) all the products of the $k-1$-elementary subsets of $S$. Can you then check for every subset fast, if there is one remaining element in $S$ that is missing to give you the right product? Try to sort the elements in $S$ in a preprocessing step to achieve the speed-up.

---
Tags: algorithms, sets
---


# Question
Title: To what does typing correspond in a Turing Machine?
I hope my question makes sense: Starting with the premise that the untyped $\lambda $ calculus is equivalent in power to a Turing machine, to what in a Turing machine does adding types to the $\lambda $ calculus correspond? Is there some kind of automaton analog to typing, whether static or dynamic?

# Answer
I can't give you a direct answer for automatons, but for functions on numbers.

The untyped lambda calculus corresponds to $\mu$-recursive functions.

For typed systems, it naturally varies for different systems.

An interesting one is System F, also known as the polymorphic lambda calculus. There is a theorem that says that

> A function (on natural numbers) is expressible in System F if and only if it can be proved in the second order Peano arithmetic that the function is total.

This means that in System F you can express basically all imaginable total functions.

There is a bit weaker system, Gödel's System T, for which there is a very similar theorem for *first* order Peano arithmetic. (However this system is not as nice as System F. In System F you can represent natural numbers, booleans etc. natively, while System T is constructed as the simply typed lambda calculus with externally added naturals and booleans. Also System F has type polymorphism, which makes it much more elegant in many cases.)

See also:
> 4 votes

# Answer
I'm going to say that typing doesn't correspond to anything for Turing Machines. Here's my reasoning: typing doesn't actually have to do with computation, and Turing Machines only model computations.

For the most part, the types of a program don't actually affect how that program runs. Rather, they're tools at compile time which are used for one of two reasons. One is to cause poorly typed programs not to compile. This is a purely compile-time operation, which doesn't affect how the resulting computation is carried out.

The second is to allow multiple functions to have the same name. This isn't really affecting the underlying computation, it's just letting us write programs in a way that's easier to understand.

Types aren't a tool of computation. They can be used for proofs, for understanding programs, for structuring them in ways that are easier to understand, but their presence doesn't change the fundamental way we perform the computation.
> 2 votes

---
Tags: turing-machines, lambda-calculus, type-theory, church-turing-thesis
---


# Question
Title: Different feature sets for training and testing?
Is it common to have a different feature set for samples in the train set and in the test set?

My use case is text categorization: when training, I use the words as the features. But when testing, I want to add hypernyms.

For example, if the training set contained the sentence "I eat a fruit", and there is a test sentence "I eat an apple", then I want to have the word "fruit" as a feature of the test sentence, in addition to its words, so that it will be classified positive. However, I don't want to add those hypernyms in the training set - if the training set contained only "I eat an apple", I don't want the sentence "I eat a fruit" to be classified positive.

So, I thought of having a small feature set for training, and a larger feature set for testing.

Is this common? If so, I would be happy to have some references.

# Answer
> 2 votes
The answer to the question in the title is no. Most ML algorithms are built around the assumption that the training and test data are drawn from the same distribution. So you should do the same pre-processing and use the same features at train and test time.

That being said, the procedure you describe sounds more like using background knowledge to make the features in the test set more similar to what you saw during training. This certainly seems like a reasonable thing to do and might fall under the heading of Domain Adaptation, when the distribution of the training and test sets change. Unfortunately I'm not familiar enough with the area to say for sure or give you a reference.

---
Tags: reference-request, machine-learning
---


title: Recurrence for recursive insertion sort

text:
# Question
Title: Recurrence for recursive insertion sort
I tried this problem from CLRS (Page 39, 2.3-4)

> We can express insertion sort as a recursive procedure as follows. In order to sort `A[1... n]`, we recursively sort `A[1... n-1]` and then insert `A[n]` into the sorted array `A[1... n-1]`. Write a recurrence for the running time of this recursive version of insertion sort.

The recurrence I formed was

$$ T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\ T(n-1) + \Theta(n) & \textrm{if } n \> 1. \end{cases} $$

**My reasoning**

* the base case of $n = 1$ the list is sorted so there is no work hence constant time.
* For all other cases the time depends on sorting the sequence `A[1...n-1]` and then insertion into that sequence. Hence it should be their sum, i.e., $T(n-1) + \Theta(n)$.

I wanted to know whether the recurrence relation is correct. If not what are the mistakes and how to correctly formulate a recurrence relation?

# Answer
According to the description you provided the recurrence is correct.
you might think it should be
T(n)=\begin{Bmatrix} 1 & ,\ n=1\\ T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise \end{Bmatrix}
because you can find the insertion place by using Binary-Search, however in order to actually insert the element you'll have to move away all the elements in the worst case.
> 6 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, sorting
---


# Question
Title: $\epsilon$ - Nash Equilibrium exceeds Nash Equilibrium
I wonder if there exists a game in which $\epsilon$ - Nash equilibrium leads to a much higher payoff than any other Nash equilibrium.

Show, for every $\epsilon$ \> 0, a two player game where there is an $\epsilon$-Nash equilibrium in which both players have a much higher payoff then in any Nash equilibrium.

What is $\epsilon$ Nash - equilibrium.$\sigma$ is $\epsilon$-Nash equilibrium, if $ u\_i(\sigma) \geq u\_i(\sigma\_i, \sigma\_{-i}) - \epsilon, \forall \sigma\_i \in \Delta(S\_i), \forall i \in N$.

It sounds very counter-intuitive, in other word I have to show the game where $\epsilon$ - Nash equilibrium, which is according to the definition not the best strategy to play indeed leads to the best payoff.

Could you give such en example?

# Answer
> 1 votes
It is quite simple: if you enlarge the set of possibilities you can get better values.

Here, in place of requiring the possibilities to be equilibrium we require them to be almost equilibrium, a larger set of possibilities, therefore a higher possible value.

Here is a simple example:

$$\left\[\begin{array}{cc} 5/5 & 0/6 \\ 6/0 & 1/1 \\ \end{array}\right\]$$

Let $\epsilon = 2$. Now $5/5$ on the top left corner is an $\epsilon$-equilibrium where as the equilibrium is $1/1$.

---
Tags: game-theory
---


# Question
Title: Counting subarrays that satisfy either of two conditions
We have an array of integers $a\[\]$, with each $|a\[i\]| \leq 10^{6}$, $size(a)\leq10^{5}$, and $a\[i\]-a\[i-1\]\leq100$.

Then we define the term range as a subarray $\[x,y\]$ of the array $a\[\]$, $x \lt y$.

We need to find total number of ranges that satisfy the property that for two given ranges $(\[x\_{1},y\_{1}\]$ and $\[x\_{2},y\_{2}\])$ either one or more of the below conditions are true:

1) $(y\_{1} – x\_{1} \neq y\_{2} – x\_{2})$

2) $a\[x\_{1}+k\] – a\[x\_{1}+k-1\] \neq a\[x\_{2}+k\] – a\[x\_{2}+k–1\]$ for some $k \in \\{1, 2, ... y\_{1}-x\_{1}\\}$.

How can we visualize this problem? Is this related to some classical problem?

# Answer
> 4 votes
I don't want to give away the solution -- I want you to have the chance to experience the pleasure of finding a nice solution on your own -- but I'll suggest a bunch of hints that might help:

* To count the number of range-pairs that satisfy either 1) or 2), you could instead count the number of range-pairs that satisfy neither 1) nor 2) (and then adjust your answer appropriately). What would it mean for a range-pair to violate 1) and violate 2)? Try writing out the conditions. I think you might find that those conditions are easier to think about. When I suggest you write out the conditions, I really do mean it: write it down, in full, and then stare at the result for a while. I think you'll be able to find how this is related to another problem that is easier to state.
* You might look at the first derivative of the array $a\[\]$. In other words, let the array $b\[\]$ be defined by $b\[i\] = a\[i\]-a\[i-1\]$ (so $size(b) = size(a)-1$). Now translate the conditions so that they refer to $b$ instead of $a$. Write down the result, simplify as much as possible, and stare at it. I think you'll find that helps you write down a cleaner version of the problem statement, which makes this problem look even cleaner and helps you see how this might be related to some other problem that is easier to restate. Hint: repeated substrings....
* You might find it interesting and helpful to learn about algorithms for the longest common substring problem, the Rabin-Karp hash function, and rolling hash functions. Suffix trees may be helpful, too.
* If you're still stuck, try counting the number of such range-pairs where the ranges are of length 1 (i.e., $y\_1-x\_1=y\_2-x\_2=1$). Can you do it? Now try counting the number of such range-pairs of length 2. How would you do that? Can you do it? Is there a simple way to think about what that's counting? Now how about the number of range-pairs of length 3. Once you've solved all three of those, does that give you any ideas for how to generalize? I'm not trying to suggest that this is literally the algorithm you should use (it's one possible algorithm, but you can build better ones), but that this will help you conceptualize what this is asking you to solve and it might help you think about the problem more clearly so that you can identify even better solutions.

Finally: You'll need to spend some significant time struggling with this problem on your own. Be prepared to have to try out many different ideas and have most of them go nowhere. Be persistent. Don't expect it's just going to magically come to you in 5 seconds. Solving these kinds of algorithm problems takes hard work and a lot of effort, so don't just assume it's not going to work before you put in that kind of effort.

**Bottom line.** I'm pretty sure this can be solved in $O(n\ell)$ time, where $n=size(a)$ and $\ell$ is the length of the longest repeated substring (and thus in $O(n \lg n)$ time on average, if the input string is random). Also I believe it should be possible to solve this in $O(n)$ worst-case running time, using sufficiently advanced algorithmics machinery (augmented suffix trees). Caveat: I haven't checked all the details carefully, so you should do that yourself.

---
Tags: algorithms, arrays
---


# Question
Title: Can the shortest simple cycle between two given nodes be found in polynomial time?
Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, the problem is NP-complete if the two constraint were changed to arbitrary, but what if the number is given?

# Answer
> 5 votes
The problem isn't NP-hard, one way to solve it is to treat the graph as a flow network where each edge has capacity $1$ and cost $1$, and set $s$ as the source and $t$ as the sink, if you find a minimum-cost flow of $2$, you have two edge-disjoint paths from $s$ to $t$ (just finding a flow of 2 or more gives disjoint paths - this is basically Menger's Theorem \- the min-cost part will lead to shortest cycles).

Of course what we really want is vertex disjoint paths, rather than edge disjoint. If we treat the input graph $G$ as a digraph $D$, replacing each edge $uv$ with two edges $(u,v)$ and $(v,u)$, we can create a new graph $D'$ by splitting each vertex $v$ into $v\_{1}$ and $v\_{2}$ with the edge $(v\_{1},v\_{2})$ with cost zero, and any edge $(u,w)$ in $D$ becomes $(u\_{2},w\_{1})$ in $D'$. Then edges disjoint paths in $D'$ correspond to vertex disjoint paths in $D$ (and hence $G$).

Now we only need to solve the min-cost part. Suurballe & Tarjan (Networks 14(2), pp. 325–336, 1984) give an algorithm to do this with running time $O(m\log\_{1+m/n}n)$ where $m$ is number of edges and $n$ the number of vertices, which is somwhere between $O(n^{2})$ and $O(n\log n)$, depending on how dense the graph is.

This may not be the fastest though: Bjorklund, Husfeldt & Taslaman (published at SODA '12, the linked version is a preprint) give a randomised FPT algorithm for finding the shortest cycle that includes a set of $k$ specified vertices, but in the introduction they also mention a (deterministic) linear time algorithm for $k=3$, which suggests $k=2$ should be quicker than the older algorithms suggest too.

What is NP-hard is finding *long* cycles (the extreme case is Hamiltonian Cycle).

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


# Question
Title: Is there an algorithm which can compute every algorithm's time complexity?
I think of an algorithm which computes the time complexity. It would be great if a code editor could compute the time complexity of the selected lines and even compare two pieces of codes in order to help developer to select one of them. I heard something related with halting problem but couldn't figure out.

# Answer
> 3 votes
It would be great, wouldn't it? And like most problems regarding Turing Machines (or "algorithms"), there is no such algorithm, and there never will be:

Consider for example the language $$\\{M: M\text{ is a TM that runs in time }O(n^3)\\}$$ It is quite easy to reduce the halting problem to this language. Indeed, given input $M,w$ for the halting problem, the reduction outputs a machine $K$ that given input $x$, runs $M$ on $w$, and accepts $x$ iff $M$ halts on $w$, and does not halt otherwise. Since running $M$ on $w$ takes constant time (if it halts at all), then $K$ runs in time $O(n^3)$ iff $M$ halts on $w$.

Thus, it is undecidable (not in $coRE$, to be exact). There is nothing special about $n^3$, the same reduction works easily for every function greater than $n\log n$ (below $n\log n$ things get a bit more involved).

Also, the Halting problem itself can be regarded as a sort of "run-time problem", in the sense that you don't even ask what the runtime of an algorithm is, but just whether it halts. Even that is undecidable.

It is interesting to note that the language, as formulated in this answer, is also not in $RE$, it is an easy exercise to show it. However, if you replace the $O(n^3)$ with exactly $n^3$, then the problem is in $coRE$. Then, the former reduction needs certain adjustments, but the problem is still undecidable.

# Answer
> 1 votes
What you are proposing can be used to implement an algorithm to solve this problem:

> Given a runtime bound $\Theta(f)$ and a procedure `proc`, decide whether `proc` runs in that time (in the worst case).

There may be special cases where you can decide such things (e.g. certain primitive recursive programs that can be identified as such), but in general, no, you can't decide runtime of programs.

As a matter of fact, you can't even decide between two given runtime bounds.

---
Tags: computability, time-complexity
---


# Question
Title: Subgraph isomorphisms: does large out-expansion imply large in-expansion?
Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)

A subgraph isomorphism $\varphi$ from $G$ to $H$ is a graph isomorphism from some subgraph of $G$ to $H$. In other words, it is a bijective function $\varphi:V\to V$ (where $V$ is the vertex set of $G$) such that if $(\varphi(u),\varphi(v))$ is an edge in $H$, then $(u,v)$ is an edge in $G$.

Let $\Phi$ denote the set of all subgraph isomorphisms from $G$ to $H$. For a vertex $v \in V$, define the out-expansion of $u$ in $\Phi$ to be $|\\{\varphi(v) : \varphi \in \Phi\\}|$ (i.e., the number of vertices that $v$ can be mapped to, under some subgraph isomorphism), and the in-expansion of $v$ to be $|\\{\varphi^{-1}(v) : \varphi \in \Phi\\}|$ (i.e., the number of vertices that can map to $v$, under some subgraph isomorphism).

Consider the following proposition:

> If every vertex has out-expansion $\ge k$, then every vertex has in-expansion $\ge k$.

Is this proposition true for all $G,H$?

I haven't been able to find any reason why it should be true. (For instance, I don't think $\Phi$ is closed under inversion: $\varphi \in \Phi$ doesn't seem to imply $\varphi^{-1} \in \Phi$.) However, playing with a few small examples, I haven't found a counter-example yet. That said, I only tried a few simple examples, so it's possible that more trial-and-error might give a better sense. But I thought I'd check whether anyone here has any suggestions for how to answer this.

Motivation: this problem arises in the security analysis of a proposed scheme for obfuscating/protecting circuits. The graph represents the circuit (actually, they use a colored graph, where each vertex is given a color, and the isomorphism has to respect the color scheme; but that can probably be ignored, for simplicity), and subgraph isomorphisms represent different possible ways that the circuit might have been hidden/obfuscated.

# Answer
> 3 votes
Yes: if each vertex maps to at least $k$ vertices by a set $S$ of bijections of a finite set, then there are at least $k$ vertices that map to each vertex by these bijections.

In fact, the in-spectrum (the sequence of in-expansions) is a permutation of the out-spectrum (the sequence of out-expansions). Note that $f$ is a bijection iff $f^{-1}$ is a bijection. Hence one can define a bijection between $S$ and $S^{-1} = \\{f^{-1}\mid f\in S\\}\ $ so the spectra are then permutations of each other.

---

An aside: this doesn't necessarily hold for bijections of infinite sets. Let $f\_i$ be the map $1\mapsto i, 2\mapsto 1, 3\mapsto 2, \dots, i \mapsto i-1, i+1\mapsto i+1,\dots$, and take the collection of all these maps. Then the out-spectrum is $(\omega,2,2,\dots)$ while the in-spectrum is $(2,2,2,\dots)$.

---
Tags: graphs, discrete-mathematics, graph-isomorphism
---