# Question
Title: What's the highest 'order' data structure
Not sure exactly how to define this but here's the basis of the question (very loosely)

* All lists can be contained in tree's
* all trees can be contained in a graph
* all graphs can be contained in a multi graph,
* and all multigraphs can be contained in a hypergraph (never actually heard of a hypergraph before searching for an answer to this, so may not have it quite right)

So there's a containment hierarchy of 'complexity' of data structures. Is Hypergraph the highest one, is there a proof of this, and is there a name for the study of whatever this is.

By highest one, I mean all structures can be represented as a hypergraph if I chose to. So in any code I could represent all the structures by using a number of hypergraphs (not that I would). tia

\[Update\] Perhaps an alternative way to ask it is, for any arrangement of data structures consisting of nodes and edges. Does there exist a structure that can't be contained in a hypergraph.

Then there is a second question - is there any data structure which can't be represented using nodes and edges.

# Answer
> 3 votes
Perhaps this is an interesting question with explicit answers, but you probably really have a problem with "exactly how to define this".

A list does not directly corresponds to a unique data structure, nor does a tree. A singly linked list corresponds to a (sufficiently unique) data structure, as does a binary tree. When you say multi graph, you probably want to refer to a quiver, i.e. a directed multigraph (edges with own identity). A binary or ternary quiver would again correspond to a (sufficiently unique) data structure.

However, any sufficiently canonical (and efficient) realization of a (n-ary) quiver as a data structure would probably not match well with the way datatypes are handled in "common" programming languages, where the size of an object with a certain datatype shouldn't depend on the actual content of that object. Therefore, this would be the point at which I would stop to look for a higher order data structure (than a quiver, looking for function like data structures and continuations certainly is useful). My reason for this is that I don't see the practical usefulness of a higher order data structure if it cannot be realized efficiently within "common" programming languages.

---
Tags: data-structures
---


# Question
Title: Is busy beaver the fastest growing function known to man?
I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver?

We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.

Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.

At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)

# Answer
> 51 votes
The busy beaver function grows faster than any computable function. However, it can be computed by a Turing machine which has been given access to an oracle for solving the halting problem. You can then define a "second order" busy beaver function, that grows faster than any function that can be computed even by any Turing machine with an oracle for the halting problem. You can keep doing this forever, building up a hierarchy of ever faster growing busy beaver functions.

See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.

# Answer
> 36 votes
There is no such thing as "the fastest growing function". In fact, there is even no sequence of fastest growing functions. This was already shown by Hausdorff. Given two functions $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$, say that $g$ grows faster than $f$ if $$ \lim\_{n\rightarrow\infty} \frac{g(n)}{f(n)} = \infty. $$ Given a function $f$, the following function $g$ grows faster than $f$: $$ g(n) = nf(n). $$ Given a sequence of functions $f\_n$, the following function $g$ grows faster than all of them: $$ g(n) = n \max\_{m \leq n} f\_m(n). $$ A natural question to ask is whether there is a "scale" of fastest growing functions. This is a well-ordered set of functions $g\_\alpha$ which is "cofinal", that is, given any function $f$, there is a faster-growing function $g\_\alpha$. (Instead of a well-ordered set, we can equivalently talk about a chain, that is, any two functions in the set need to be comparable.) The existence of a scale is independent of ZFC: assuming CH, there is a scale, while in Cohen's model that falsifies CH (adding $\omega\_1$ reals), no scale exists.

# Answer
> 5 votes
Other answers address the question directly. For more and deeper background, this paper by Lafitte on the subject considers the larger context of busy beaver-like functions. It also has some results and theorems fitting the idea into a more general framework. It shows that (informally) "busy beaver-like functions" have a close connection to Chaitin incompleteness phenomena (Theorem 2.1). It also shows that there are theories that are not "powerful" enough to "comprehend" the busy beaver-like functions, i.e. they are unprovable in those theories due to Godel-related incompleteness. It shows the idea of assuming busy beaver-like results as axioms and a logical progression of theories that results similar to ideas originally envisioned by Turing.

\[1\] Busy beavers gone wild by Grégory Lafitte. Abstract:

> We show some incompleteness results à la Chaitin using the busy beaver functions. Then, with the help of ordinal logics, we show how to obtain a theory in which the values of the busy beaver functions can be provably established and use this to reveal a structure on the provability of the values of these functions.

# Answer
> 0 votes
The Hartmanis-Stearns time and space hierarchy theorems prove that there is no "fastest growing" function in terms of time or space because the scale is unbounded. But it does give an *ordering* such that all "well behaved" computable/recursive functions can be compared. But many "fast growing" math functions do not seem to have been evaluated in terms of time/space complexity so far despite it being a somewhat obvious or even glaring theoretical "gap" to fill. Doing so could lead to important "bridge theorems".

---
Tags: computability
---


# Question
Title: References on collective intelligence with respect to CS applications
In recent years the field of "collective intelligence" sometimes known as Web 2.0 has had a big impact on computer science, software engineering, and software development. Stackexchange software itself is a large scale evolving application or implementation and experiment along the lines of harnessing collective intelligence.

> What are some references especially with a CS angle on this connection between collective intelligence/Web 2.0 and CS?

# Answer
> 1 votes
this area is also connected to "social applications"

---
Tags: reference-request, education, software-engineering, books
---


title: Chromatic polynomial of a square

text:
# Question
Title: Chromatic polynomial of a square
Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..

That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.

However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.

Could you tell me where I am going wrong with my thinking.

# Answer
The answer by Nicholas above and this one helped me see the flaw in my thinking. I thought of elaborating more specifically upon Nicholas',

> You must remember that the vertices diagonal from one another can be colored the same

and also obtain the chromatic polynomial by adjusting for my wrong reasoning.

I had initially figured that there are $\lambda - 2$ ways of picking colors for C. The "-2" accounted for the colors being different from that of B and D. What I did not think about is that B and D can have the same colors in which case there would be just $\lambda - 1$ way of picking colors for C. Thus

$P(ABCD, \lambda)$ = Number of ways of properly coloring ABCD when B and D are of the same color + Number of ways of properly coloring ABCD when B and D are colored differently
= $λ(λ−1)(1)(λ−1) + λ(λ−1)(λ−2)(λ−2)$
> 2 votes

# Answer
You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets.

The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.

Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A\_i$ is $$ \sum\_{I \subseteq \[n\]} (-1)^{|I|}|A\_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A\_I = \bigcap\_{i \in I} A\_i$$

Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A\_{e} = \\{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \\}$$

Before we get our final polynomial, we need to count the size of our sets $A\_{e}$, and the size of all intersecting subsets.

Observe that $|A\_{12}| = |A\_{23}| = |A\_{34}| = |A\_{41}| = \lambda^3$. This is due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,

$|A\_{12} \cap A\_{23} | = |A\_{23} \cap A\_{34} | = |A\_{34} \cap A\_{41}| = |A\_{41} \cap A\_{12}| = |A\_{12} \cap A\_{34}| = |A\_{41} \cap A\_{23}| = \lambda^2$

I'm not going to list each 3-set, but they all have the same count. $|A\_e \cap A\_{e'} \cap A\_{e''}| = \lambda$. And Finally, $|A\_{12} \cap A\_{23} \cap A\_{34} \cap A\_{41}| = \lambda$. Now lets collect our terms and add up.

$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$

Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.
> 8 votes

---
Tags: graphs, colorings
---


title: Infinite alphabet Turing Machine

text:
# Question
Title: Infinite alphabet Turing Machine
Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?

Intuition tells me not, since you need an infinite number of states to differentiate each symbol. So I think some of the symbols or the transitions caused by the symbols (or some subsets of the transitions) have to be equivalent. So you can actually simulate such machine with a regular TM and a bounded subset of such symbols or transitions.

How could I approach a formal proof of this?

# Answer
> 19 votes
No, it would be more powerful. The transition function would no longer be finite, and *that* buys you a lot of power.

With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of uncountable sets like the real numbers couldn't be represented in one symbol). And likewise for the output.

So you can make a two-state (one initial, one accept) infinite-alphabet-TM with a single transition that moves to the accept state and changes the symbol under the tape head in accordance with the function you're trying to compute. This recipe would allow you to compute any mapping between sets that can be put in a one-to-one correspondence with the alphabet.

So to avoid that degenerate sort of machine being the answer to everything, you'd need to restrict what the transition function can do. An obvious one would be to require the transition function itself to be computable (ordinary TM's transition functions are trivially computable after all, since they're finite). But then you'd be trying to use computable functions to define your model of computable functions.

# Answer
> 6 votes
The above answer is correct, but there is a little more that can be said about infinite alphabets and computability.

A Turing Machine is described in WP as $M = (Q, \Gamma,b,\Sigma,\delta, q\_0, q\_f)$ in which all sets are finite. Thus the transition function $$ \delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \\{L,R \\} $$ is necessarily finite.

In an infinite alphabet machine we would replace the input alphabet $\Sigma$ by say $\Sigma^{inf}$ and so the tape alphabet by $\Gamma^{inf}$ and the transition function by $\delta^{inf}$ obeying:

$$ \delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \\{L,R \\} $$

So $\delta^{inf}$ is necessarily an infinite function. As remarked if this function is to be non-computable, then the above is not representable finitely. Let us assume that we shall keep $\delta^{inf}$ (partial) recursive if possible. The question is whether the alphabet will always allow this.

The basic issue is that a finite alphabet is presented in its entirety (so we can choose to define our functions recursively), but an infinite alphabet can never be presented in its entirety. So what mechanism is generating the alphabet?

The simplest way to consider this is to imagine that there is a finite "core" alphabet, say $A=\\{a,b\\}$. Then generate a language $L \subset A^\*$. Assume that string **abaab** $\in L$. Then define $\alpha = \<abaab\> \in \Gamma^{inf}$. So the infinite alphabet consists of sets of strings from $L$ concatenated into a *single* symbol like $\<abaab\>$.

The simplest such alphabet is basically **\<1\*\>**, the regular language in which any two symbols are distinguished by counting the number of vertical strokes in each symbol. This will be computable with a finite state parser (as an LBA though, not as a Finite Automata). Turing argued for a finite alphabet to avoid any appearance of a non-finite operation in a TM operation. However it is worth noting that the 26 letters of the English alphabet do not follow this counting pattern: letter z does not contain 26 strokes or dots or anything. So other patterns are possible with the most general computational pattern that based on a recursively enumerable (r.e.) language $L$.

The problem here though is that constructing $\delta^{inf}$ will not be possible unless the definition of $L$ is explicitly provided. This is partly because equivalence of r.e. sets is undecidable and partly because otherwise we only ever have a finite sample to work with and cannot infer $L$ from that. *If* we do have the definition of $L$ (and hence $\Gamma^{inf}$) then if $f$ is recursive in $\Gamma^{inf}$ then $f$ is recursive in finite A, and so $f$ is absolutely recursive and $\delta^{inf}$ can be recursive.

Finally we consider the case that $L$ is not r.e. with two examples:

**Example1**. $\<n\>\in \Gamma^{inf}$ iff $\phi\_{n}(n)$ provably diverges. In this case the alphabet $\Gamma^{inf}$ will obviously not have a finite description - instead it will "grow" over time (and only be fully defined itself in some computational limit). But then it is an infinite alphabet which cannot be presented at once in any case. So if $f$ is recursive in $\Gamma^{inf}$, then f is in $\Delta\_2^0$ - the Halting set. So $\delta^{inf}$ cannot be recursive.

**Example2**. A more geometric example considers Penrose-like Tiles. Let symbol $S\in\Gamma^{inf}$ if $S$ is a unit of N aperiodic tiles which provably can tile the plane. This alphabet is infinite since one can construct, for any N, an N-tile unit of Penrose tiles. However tiling the plane itself is undecidable, so the set of S will grow as more tiles like this are discovered. A possible $f$ recursive in $\Gamma^{inf}$ but not absolutely recursive might be f(S) = number of tiles in S.

---
Tags: computability, turing-machines, reductions, simulation
---


# Question
Title: How to find the vertices on simple path between two given vertices in a directed graph
Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T?

It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph: S -\> a; a -\> b; b -\> c; b-\> T; c -\> a

While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).

A closely related problem is the following: Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.

A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).

# Answer
> 3 votes
Thanks for your answers. As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.

From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.

Here are few definitions from this paper:

> The subgraph homeomorphism problem is to determine: if a pattern graph p is homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in the input graph.

Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.

> Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.
>
> \[...\]
>
> Next we show that for each pattern P not in C the fixed subgraph homeomorphism problem with pattern P is NP-complete.

I have not read the proof yet so I'll stop here.

There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:

> Given a directed graph and four distinct vertices $s\_1, t\_1, s\_2, t\_2$, decide if there exist two pairwise node disjoints simple paths from $s\_1$ to $t\_2$ and from $s\_2$ to $t\_2$.

This problem for directed graphs is well known to be NP-complete. However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t\_1 \to i$ and $i \to s\_2$.

If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.

# Answer
> -1 votes
This is an NP-hard problem.

```
@article{DBLP:journals/tcs/FortuneHW80,
  author    = {Steven Fortune and
               John E. Hopcroft and
               James Wyllie},
  title     = {The Directed Subgraph Homeomorphism Problem},
  journal   = {Theor. Comput. Sci.},
  volume    = {10},
  year      = {1980},
  pages     = {111-121},
  ee        = {http://dx.doi.org/10.1016/0304-3975(80)90009-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

```

---
Tags: algorithms, graphs
---


# Question
Title: Are today's massive parallel processing units able to run cellular automata efficiently?
I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.

If we choose whatever finite grid would fit inside the memory of the chip, can we expect one transition of a cellular automaton defined on this grid to be computed in (quasi)constant time?

I assume 2D cellular automata would require more bandwidth for communication between the different parts of the chips than 1D automata.

I'd also be interested by the same question in the case of FPGA programming or custom chips.

# Answer
Excellent question. I believe the answer is yes.

Evolving a cellular automaton is essentially equivalent to performing a stencil computation. On some 1D, 2D, or 3D grid, successive values of points (or cells) are computed based on the last value of point's neighborhood. In a simple 1D CA, this neighborhood might be the cell and the two cells to the left and right. There are lots of examples of stencil computations being performed on GPUs; ORNL's SHOC benchmark suite for OpenCL/CUDA contains a 2D stencil example, for instance.

The basic idea is to have each thread get a local copy of the neighborhood for several points, then compute the next values for points determined by that neighborhood. By appropriately using the memory hierarchy in e.g. CUDA (registers, shared, constant, texture, and global memories) and the SIMT processing model (e.g., by appropriately computing the transition function without introducing excessive warp divergence), good performance can be achieved.

This answer would be a lot better if I were to give an example, but I am too busy to write any code right now... But in theory, I think it should be feasible to efficiently simulate CAs on GPUs by modeling them after stencil computations. Lots of considerations go into writing a good stencil computation for GPUs, though.
> 7 votes

# Answer
Whatever you do, computing the next state for a cellular automaton ask for as many computation than there are cells in the automaton. Thus to get a constant time, you need as many computing core as there are cells.

The number of these in GPU are currently at most a few thousands, while the computation of the next state is so simple that I expect the result to be IO bound, i.e. you can get a very good approximation of the time needed by just considering the data movement needed (and if it isn't a good approximation, either the implementation has an inefficiency or the architecture isn't suitable, but that would be very surprising).

For FPGA, the question is more difficult and will probably depend on the mix of memory and computation units available. If I'm not too far out, you won't have enough memory to keep all units busy and if you rely on external memory, you are in the same seat as GPU, memory bandwidth will be the limiting factor and I'd not be surprised if the conclusion is that there is no advantage over GPU. (Note that while I've worked with FPGA, it was years ago, there may now be FPGA models with a right mix).

ASIC offers more flexibility. You can easily have a systolic like implementation (but with bidirectional data flow, some systolic is usually restricted to unidirectional data flow), each physical cell is one logical one: bit of memory and the needed logic to compute it's next state and is layed out so that it's physical neighbor are it's logical one. You are obviously in constant time realm. Depending on which hard macros you have, you may be better to be a little less obvious and have physical cells which regroup several logical one. The goal is to maximize what is done in one chip, in other word to minimize the communication with the outside of the chip as as soon as your communication needs are proportional to the number of cells, you'll be bandwidth limited. Yes, that mean that if you need to look at all the cells for each step, you are probably not a lot better than with GPU. (Full custom would provide only better integration, i.e. more cells per chip).

Summary: \- if you want to look at all the intermediate states, GPU is the most effective approach \- if you don't, you need the volume to justify an ASIC to have something better, FPGA probably won't offer enough advantage if they have any.
> 5 votes

# Answer
*I wonder whether the massively parallel computation units provided in graphic cards nowadays are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.*

being very general, yes GPU computing is the best alternative in standard hardware available for everybody.

More in detail; in theory, under the PRAM model, the cost per time step is indeed $O(1)$, you already know that. However the GPU differs a little from PRAM since memory acceses cost more and it is divided in different hierarchies (one should consider the PMH model for a finer theoretical analysis). Additionally, threads work in groups or ***warps***, they are lockstep computations that progress in a SIMD way. The programming model of the GPU works with the concept of ***grid*** (CUDA) or ***workspace*** (OpenCL) which is practically a 1-to-1 mapping to the space of computation of the cellular automata. This is the key feature to identify and realize that GPUs are CA-friendly. Tecnical details: If the warp divergence is treated correctly (replacing if-else conditionals by closed math expressions), memory acceses are coalesced and $n \le P$ ($n$ number of cells and $P$ number of processors), then one could say that the computational complexity is sort of $O(1)$.

on the FPGA and ASIC side, i know that there is research on building a physical CA as a grid of logic gates with states, all connected by their neighbors; i.e ***systolic arrays***. The idea would be to not use a global memory anymore but instead rely on the states of each node in the grid. A machine of this type would be revolutionary since then we could stop talking about a computer simulating a CA and start talking about a CA running as a computer (some CA are turing complete).
> 2 votes

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


# Question
Title: Hiring one person out of n -- rank and probablity
I am studying algorithms from CLRS book. I try to understand the difference between

* probability of hiring the $i$th person out of $n$ and
* probability of hiring the $i$th person out of $n$ persons based on ranks.

Using the normal probability, we know the answer for the first one is $\frac{1}{n-i}$ and the answer for the second is given as $\frac{1}{i}$ in the CLRS book. I am unable to understand the concept here. How is it $\frac{1}{i}$? Can it also be $\frac{1}{n-i}$ taking in ranks, too?

We have n candidates lined up for an intertiew.Once a candidate is interviewed he is given a rank.If the rank of the next candidate is greater the current greatest rank he is hired and his rank is now the current greatest rank

```
HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i

```

# Answer
When people are interviewed following a *random* arrival order, the probability of candidate $i$ being hired is $\frac{1}{i}$. This follows from the fact that, assuming a random order of arrivals, for each $i$ the group of initial $i$ candidates is random, so that the $i$-th candidate has probability $\frac{1}{i}$ of being chosen which happens if he/she is better qualified than the previous $i-1$ candidates.

Now instead of considering a random order on the arrivals, *impose your own order*, based on ranks: the first candidate is the less qualified, and the last one is the one which is the best overall. In this case, if the group is made of $n$ candidates, numbering them from $0$ to $n-1$ you get for the $i$th candidate a probability of being hired which is $\frac{1}{n-i}$, since candidates are now arriving on the basis of their ranks, and the $i$-th candidate is always better qualified than the previous $i-1$.

This is why you want to permute the group of candidates: so that no particular input elicits the worst case behavior associated to the permutation in which candidates are sorted by rank.

CLRS explains how this minor modifications allows you to hire, on average, $O(\lg n)$ candidates instead of $n$ in the worst case. Note that this is only a probabilistic guarantee: nothing prevents the pseudorandom generator, if you are really unlucky, from generating the permutation corresponding to the candidates sorted by rank. But we do not expect this to happen frequently: the probability of generating the bad permutation is only $\frac{1}{n!}$ which, for large $n$, is very low.
> 3 votes

---
Tags: probability-theory
---


# Question
Title: Why bound of linear function is same as that of quadratic equation
I am learning algorithms. So, I came along with something very interesting.

The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a\>0$.

This is same as for $an^2 + bn + c$. But shouldn't it be different?

# Answer
$O$ only gives an *upper bound*; see also here. Clearly, $n^2$ is -- up to a constant factor -- an uppper bound for linear functions.

In fact, you can prove that

> $n^{k\_1} \in O(n^{k\_2})$ for all $k\_1 \leq k\_2$.

Together with

> $n^{k\_1} + n^{k\_2} \in O(n^{\max \\{k\_1,k\_2\\}})$ for all $k\_1,k\_2$

and the obvious

> $cn^k \in O(n^k)$ for all $c,k$,

you get a general version of your statement.
> 4 votes

# Answer
$\mathcal{O}(g)$ (read Big oh of $g$) is a formalization of the idea that a function becomes nearly proportional to another one as we evaluate it at large values. Take for example the function $f(n) = 1000 + n + n^2$. For small values of $n$, most of the cost is coming from the constant $1000$; as $n$ becomes larger, the term $n$ contributes more to the cost. As $n$ becomes even larger, $n^2$ becomes more important to the point that most of the cost is coming from $n^2$. Therefore $f(n)$ becomes nearly proportional to $n^2$ as $n$ gets larger.

$\mathcal{O}$ is the set of functions that grow no faster than $g$ (times some constant). $n$ grows no faster than $n^2$ therefore it's in $\mathcal{O}(n^2)$, $n^2$ grows no faster than $n^2$, therefore $n^2$ is in $\mathcal{O}(n^2)$. The function in the previous paragraph is in $\mathcal{O}(n^2)$. In fact, any polynomial of degree $p$: $c\_0 + c\_1n^1 + c\_2n^2 + \dots + c\_pn^p$ is in $\mathcal{O}(n^p)$.

To prove that a function $f(n)$ is in $\mathcal{O}(g(n))$, you have to find constants $n\_0$ and $c$ such that for large values of $n$ (means when $n$ \>= $n\_0$), it's always the case that $f(n) \le cg(n)$.

Let's prove that every polynomial is on the order of its highest degree term (on the order of is the same as saying in big oh of). Let $f(n) = c\_0 + c\_1n^1 + c\_2n^2 + \dots + c\_pn^p$ be a polynomial function. Let $c\_{max} = \max\\{c\_0, \dots, c\_p\\}$.

We have $$f(n) \le c\_{max}(p+1)n^p$$ We can set our constant $c$ to $c\_{max}(p+1)$. Now we have to find $n\_0$, that is for what values of $n$ does the inequality hold. Well, if $n=1$ the inequality holds so we can choose $n\_0$ to be $1$.
> 1 votes

---
Tags: algorithms, asymptotics
---


title: Collectively pay the bill problem

text:
# Question
Title: Collectively pay the bill problem
There are $n$ people at a table. The $i$th person has to pay $p\_i$ dollars.

Some people don't have the right bills to pay exactly $p\_i$, so they come up with the following algorithm.

> First, everyone puts some of their money on the table. Then each individual takes back the money they overpaid.

The bills have a fixed set of denominations (not part of the input).

An example: Suppose there are two people, Alice and Bob. Alice owes \\$5 and has five \\$1 bills. Bob owes \\$2 and has one \\$5 bill. After Alice and Bob put all their money on the table, Bob takes back \\$3, and everyone is happy.

Of course, there are times where one doesn't have to put *all* his money on the table. For example, if Alice had a thousand \\$1 bills, it's not necessary for her to put them all on the table and then take most of them back.

I want to find an algorithm with the following properties:

1. The input specifies the number of people, how much each person owes and how many bills of each denomination each person has.
2. The algorithm tells each person which bills to put on the table in the first round.
3. The algorithm tells each person which bills to remove from the table in the second round.
4. The number of bills put on the table + the number of bills removed from the table is minimized.

If there is no feasible solution, the algorithm just return an error.

# Answer
> 6 votes
If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:

There are $n$ parties involved: $n-1$ persons, and one restauarant. Let $p\_i$ be the amount of money party $i$ should have **after** the meal is finished and paid for. For example, if Alice has \\$36 and owes \\$25, Bob has \\$12 and owes \\$11, and Carl has \\$30 and owes \\$25, we say that $p\_0$ is the restaurant and have:

$p = (61, 11, 1, 5)$

That is, when the meal is over the restaurant should have \\$61, Alice should have \\$11, Bob should have \\$1 and Carl should have \\$5.

Now let $b$ enumerate all of the $m$ bills involved. For example:

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.

We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\\{0,1\\}$ matrix $C$. Entries of 0 in this matrix indicate which bills each party starts with ($C\_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).

Continuing our example:

$$ C = \left\[ \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \right\] $$

indicates that Alice started with \\$1, \\$5, \\$10, \\$20, Bob started with \\$1, \\$1, \\$5, \\$5, and Carl started with \\$10 and \\$20.

Again, the goal is to minimize the number of bills that change hands. In other words:

$$ \begin{align} \text{Minimize:} & \sum\_{i=0}^{n-1}{\sum\_{j=0}^{m-1}{C\_{i,j} x\_{i,j}}} \\ \text{subject to:} & \sum\_{i=0}^{n-1}{x\_{i,j}} = 1 \text{ for } 0 \le j \lt m, \\ & \sum\_{j=0}^{m-1}{x\_{i,j}b\_j = p\_i} \text{ for } 0 \le i \lt n, \\ \text{and} & x\_{i,j} \ge 0 \end{align} $$

The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.

This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see \[Karp 1972\]). The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.

There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:

$$ x = \left\[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} \right\] $$

which means Alice pays exactly \\$5 and \\$20, Bob pays exactly \\$1, \\$5 and \\$5, and Carl overpays \\$10 and \\$20 and then removes a \\$5 from the table.

I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi). The first solution it gave was

$$ x = \left\[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right\] $$

which is almost the same except that Carl took the "other" $5 that Bob put on the table.

Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$). The exception is perhaps #4 which was discussed in the comments of the question. It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:

Identify a subset of people that can pay the reduced total? Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.

Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.

In any case, there is also an $O(1)$ solution in which every person pays with a credit card.

# Answer
> -2 votes
Certainly some basic starts could be to include the smallest bills available to reach the total amount of the overall bill. If you don't care to allow \\$2 bills, each person could simply remove the largest bill they can take from the pool then and would get there relatively quickly. The \\$2 bill throws that off as it doesn't sub-divide nicely in to the other denominations and greatly complicates the problem. There are also certainly a number of other optimizations that could be done to make observations about the need for further funds to be added during round 1 (for example, if the total number of \\$1 bills is ever sufficient to cover the bill, then everyone can stop putting in unless they have not yet put in enough for their bill).

---
Tags: algorithms, optimization
---


title: Using Funk SVD with SGD?

text:
# Question
Title: Using Funk SVD with SGD?
I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here).

However the framework that we are trying to integrate doesn't support Funk SVD, only SGD (Stochastic Gradient Descent).

Since shouldn't these be compatible? In other words, I should be able to create the U and V matrices with SGD and then treat them like they were made via the Funk SVD process?

Are there any disadvantages of using this versus the algorithm detailed by Funk?

# Answer
> 2 votes
simon funk is the apparent inventor of a simple & ingenious SVD (singular value decomposition) algorithm during the netflix contest although the algorithm may have predated his discovery (would like to know a ref if anyone knows). SGD = stochastic gradient descent (?) which can be applied to all kinds of optimization problems, incl SVD.

so it depends on your recommender system framework and if its trying to use SVD for recommendations, which is common, but not universal. if it is using SGD to compute the SVD, then that is very similar to the Funk algorithm except the Funk algorithm is probably more prone to get stuck in local minima.

in other words the SGD may find a superior solution but it may take longer. so basically both SGD/Funk are two approaches to computing the U,V matrices & you can do experimental testing to see which gives you the best results or desirable performance.

Funks algorithm is basically just straight *gradient descent* and SGD is stochastic gradient descent that adds a simulated annealing-like approach to the optimization where earlier in the convergence/search, weights are randomly perturbed to avoid local minima, and then as the search progresses & hopefully converges, the perturbation factor decreases.

fyi for SVD it can be possible to find the optimal solution using matrix based methods even for large matrices (esp if large distributed resources are available) and one could possibly compare either the Funk algorithm or SGD to the actual global optimum.

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


# Question
Title: Redundancy elimination in the superposition calculus
When proving theorems with the superposition calculus, we deal with three kinds of rules:

1. Generating rules: from pair of clauses A and B, generate new clause C while keeping the original pair, e.g. superposition in the general case.
2. Rewriting rules: from clause A generate new clause B, e.g. equality reflexivity, equality factoring; superposition with a unit equation can also be regarded as a rewriting rule.
3. Eliminating rules: delete a clause, e.g. subsumption, tautology elimination.

The question is, regarding the second category, can we perform a strict rewrite, *replacing* the original clause with the new one, or do we have to keep the original *as well as* the new one? In the case of equality reflexivity it looks like we can do the former, but for equality factoring and superposition with a unit equation it's not immediately clear whether this would preserve completeness.

Is there a general way of knowing which is the case? Or a list of which needs to be done in each case?

# Answer
> 2 votes
a leading implementation of the superposition calculus theorem prover is E. in its description of their technology it states some basic theory & background under **Proof Procedure**:

> E uses the DISCOUNT \[DKS97\] variant of the given-clause algorithm. The proof state is represented by two sets of clauses, the set P of processed clauses (initially empty) and the set U of unprocessed clauses. Clauses in U are ranked according to a heuristic evaluation function, and are processed in order. Processing will first simplify the selected clause g with all clauses in P, then simplify P with g (moving all affected clauses from P back into U), and then compute all direct consequences between g and P that can be derived using the generating inference rules (superposition, equality factoring, and equality resolution). The new clauses are simplified with respect to P and added to U, g is added to P.
>
> This proof procedure is different from the given-clause algorithm implemented in Otter (and many provers since), which also uses U for simplification. The variant E uses was first popularized by DISCOUNT, but also is at the core of Waldmeister. Vampire and SPASS implement it in addition to their primary algorithm.

so \[iiuc\] the word "rewriting" may be somewhat a misnomer in the actual implementations of the theorem proving rules, because the original clauses are never "deleted" & always retained in case they can be affected or combined with later derivations. the rewriting "moves" "rewritten" clauses between $P$ and $U$ in both directions.

ie rewriting is basically like an *addition* of new derived (true) clauses to a list of known true clauses, and the movement between $P$ and $U$ is a strategy to find new true clauses in an efficient way (basically tracking the "frontier" in a mixed depth/breadth search, ordered by the priority function), and $P \cup U$ is the set of known true clauses.

dont know of a ref for this but think that heres the theory on all this. suppose $A \implies B$ and then $A$ was "deleted". it might still be possible to derive $B \implies A$ by other derivations and clauses. in that case it would have no effect. but if its not derivable by other routes, then in theory it *could* lead to changing a complete problem into an incomplete problem. dont know of a reference that shows this. it could be a doable exercise for the reader to come up with an example.

fineprint: taking stab at this question due to lack of other responses. am interested in a really authoritative answer to this question also. there is probably a better one than above but this is the best found so far after some research. suspect the question might be better addressed on say math.se, mathoverflow or TCS.se. also found it hard to come by basic descriptions of these concepts & without heavy specialized jargon.

---
Tags: logic, automated-theorem-proving
---


# Question
Title: The order of growth analysis for simple loop
What would the order of growth for this loop be:

```
int sum = 0;
for (int n = N; n > 0; n /= 2)
    for(int i = 0; i < n; i++)
        sum++;

```

The first loop seems to run for $\log N + 1$ times and the second loop runs $n$ times.

So is the correct answer $O(n \log n)$?

# Answer
When the iterations of the inner loop depend on the outer loop, it's better to sum over the amount of iterations of the inner loop. There is no need to overcomplicate this and think of logarithms just because the outer loop has logarithmic behavior.

## Iterations

In this example, we can see the number of iteration the inner loop performs is halved in each step of the outer loop:

* $N$ iterations of the inner loop
* $\frac{N}{2}$ iterations
* $\frac{N}{4}$ iterations
* $\dots$
* $\frac{N}{2^i}$ iterations
* $\dots$
* 1 iteration

as the outer loop iterates.

## Formalizing

Factoring $N$, we get: $$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N})$$

Knowing that: $$\sum\_{i=0}^\infty \frac{1}{2^i} = 1 + \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+\cdots = 2$$

we can conclude that:

$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N}) \< 2N$$

Which is why the algorithm's complexity is bounded by $\mathcal{O}(N)$

Since the algorithm performs at least $N$ steps (assuming $N \geq 1$), it follows that the runtime behavior is also described by $\Omega(N)$, which implies that it is in $\Theta(N)$
> 8 votes

# Answer
The first loop runs $\log\_2N$ times but in nested loops we are interested in the running time of the inner loop (thanks to Tsuyoshi Ito for the clarification). The second loop depends on the value of $n$ in the first. When $n=N$, the second loop runs $N$ times, when $N$ is halved it runs $\frac{N}{2}$ times and so on. The second loop runs in total: $N + \frac{N}{2} + \frac{N}{4} + \dots +1=N(1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^{k}})\approx N$. So the running time is $\Theta(N)$.
> 3 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Definition of $\Theta$ for negative functions
I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:

$$\Theta(g(n)) = \\{ f(n)\\,|\\, \exists\\, c\_1, c\_2 \> 0, n\_0 \in \mathbb{N}: 0 \leq c\_1 g(n) \leq f(n) \leq c\_2 g(n)\ \ \forall n \geq n\_0\\}$$

But then on the next page the text says that:

> The definition of $\Theta(g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever $n$ is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$.) Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set $\Theta(g(n))$ is empty.

That last part about the how if the function is negative the set $\Theta(g(n))$ is empty and the general requirement of a positive function is sort of confusing. Can anyone out there clarify this definition for me and what it means, possible with an example, it would be much appreciated.

# Answer
> 7 votes
This is just a technicality. In asymptotic analysis we are only "really" interested in positive functions like $n^3$ or $n\log n$. However, if we want to be very formal and general, we could take into account non-positive functions (and that could turn it to be useful, see below). The definition of $\Theta$ states that $f(n) = \Theta(g(n))$ if from some point on, $f(n)/g(n)$ is bounded from both sides by constants, and furthermore $g(n) \geq 0$. (That's what you get if you unroll the definition.) In particular, if $f(n) = \Theta(g(n))$, then from some point on, $g$ is non-negative.

Here is an alternative definition of big $\Theta$. Suppose $f,g \colon \mathbb{N} \rightarrow \mathbb{N}$ are *positive* functions, that is $f(n),g(n)\>0$. Then $f(n) = \Theta(g(n))$ if there exist positive constants $c\_1,c\_2$ such that $c\_1 \leq f(n)/g(n) \leq c\_2$. I don't know why the more complicated definition is presented in introductory texts.

What are the advantages of the more complicated definition? It can handle functions which have some non-positive values (there has to be a finite number of them). For example, this definition accommodates the (true) statement $n-10 = \Theta(2n-30\log n)$. Although functions encountered in practice are usually positive, sometimes negative functions could be encountered: for example, say we're interested in some genuine complicated function $k$, and we estimate it from below by a function $t$, which is however negative for small $n$.

# Answer
> 3 votes
## Why $\Theta(g)$ may be empty

It follows directly from the definition.

$$\Theta(g(n)) = \\{ f(n)\\,|\\, \exists\\, c\_1, c\_2 \> 0, n\_0 \in \mathbb{N}: 0 \leq c\_1 g(n) \leq f(n) \leq c\_2 g(n)\ \ \forall n \geq n\_0\\}$$

The important part here is this: $ f(n) | \exists\\, c\_1 \> 0: 0 \leq c\_1 g(n)$

Obviously, the constraint on $ f$ (as of now, it does not even depend on $f$), states that $g$ multiplied with some positive constant $c\_1$ must itself be positive (for large values of $n$, *implied from here on*).

Of course, if $g$ is not strictly positive, this constraint will prevent all possible functions $f$ from being a member of the set $\Theta(g)$.

It follows that such a set will be empty.

## For all $f \in \Theta(g)$, $f$ is strictly positive

This also follows directly from the same part of the definition: $ f(n) | \dots : 0 \leq f(n) $

Obviously, if $f$ is not strictly positive, the condition is not met, hence no such $f$ can be contained in $\Theta(g)$.

*Note*: I'm not entirely sure *what* is unclear to you, because all you wrote is "confusing".

---
Tags: terminology, asymptotics
---


title: Sorting as a linear program

text:
# Question
Title: Sorting as a linear program
A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of \[1\] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, a form of linear regression, and even circuit evaluation!

Since circuit evaluation reduces to linear programming, any problem in $P$ must have a linear programming formulation. Therefore, we have a "new" sorting algorithm, via reduction to a linear program. So, my questions are

1. What is the linear program that will sort an array of $n$ real numbers?
2. What is the running time of the reduce-to-LP-and-solve sorting algorithm?

---

1. Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani (2006)

# Answer
The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know.

For a permutation $\sigma$ of $\\{1, \ldots, n\\}$ define the permutation matrix $P\_\sigma$ as the 0-1 matrix such that $P\_{ij} = 1$ if $j = \sigma(i)$ and $P\_{ij}=0$ otherwise. This is simply the matrix which permutes the coordinates of a vector $x$ according to $\sigma$: if $y = P\_\sigma x$ then $y\_i = x\_{\sigma(i)}$. I'll denote $y=P\_{\sigma}x$ as $\sigma(x)$ from now on.

One more definition: a non-negative $n\times n$ matrix $M$ is doubly-stochastic if each one of its rows and each one of its columns sums to 1.

And one fact which is very important in combinatorial optimization - the Birkhoff-von Neumann theorem:

> A matrix $M$ is doubly stochastic if and only if it is a convex combination of permutation matrices, i.e. if and only if there exist permutations $\sigma\_1, \ldots, \sigma\_k$ and positive reals $\alpha\_1 , \ldots, \alpha\_k$ such that $M = \sum\_{i = 1}^k{\alpha\_i P\_{\sigma\_i}}$ and $\sum{\alpha\_i} = 1$.

Notice that a doubly stochastic matrix is defined by the inequalities

$$\forall i: \sum\_{j = 1}^n{M\_{ij}} = 1$$ $$\forall j: \sum\_{i = 1}^n{M\_{ij}} = 1$$ $$\forall i, j: M\_{ij} \geq 0$$

All these inequalities taken together determine a polytope $P$, and the Birkhoff-von Neumann theorem states that the extremal points (vertices) of this polytope are all permutation matrices. From basic linear programming, we know this implies that any linear program which has the above inequalities as its constraints (and no other constraints) will have a permutation matrix as an optimal solution.

So given an input $a = (a\_1, \ldots, a\_n)$ to be sorted, we just need to come up with a linear objective $f\_a(M)$ for which:

* $f\_a(P\_\tau) \< f\_a(P\_\sigma)$ if $\sigma(a)$ is sorted but $\tau(a)$ is not.

Then formulate a linear program with objective to maximize $f\_a(M)$ and the inequalities above as constraints, and you are guaranteed that an optimal solution is the permutation matrix $P\_\sigma$ for $\sigma$ such that $\sigma(a)$ is sorted. Of course, it's easy to "read off" $\sigma$ from $P\_\sigma$.

One choice for $f\_a(M)$ is $v^T M a$ where $v = (1, \ldots, n)$. Verify that

* this is linear in $M$;
* for $P\_\sigma$, $f\_a(P\_\sigma) = \sum\_{i = 1}^n{i a\_{\sigma(i)}}$;
* the above is maximized at the $\sigma$ for which $\sigma(a)$ is sorted (by contradiction: otherwise you could switch two coordinates of $\sigma(a)$ and achieve a higher value).

And voila, you have a linear program for sorting. Seems silly for sorting, but this is in fact a powerful method in optimization.
> 36 votes

---
Tags: algorithms, reductions, sorting, linear-programming
---


# Question
Title: complexity of decision problems vs computing functions
This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens being NP hard, But it got downvoted there & goes unanswered because the audience felt it was poorly phrased.

The issue seems to be that some questions in CS have to be phrased as decision problems to measure their complexity, and it is not always obvious how to do that. also other questions are studied from the POV(point of view) of computing a function with integer or string inputs and outputs, in which case eg their time or space complexity can be studied. for some NP complete problems e.g. SAT its proven that the decision problem (e.g. determining whether an answer exists) is roughly equivalent in time/space complexity to solving the function problem (finding a satisfying assignment), but of course that's not always the case.

Moreover much of CS theory is focused on NP complete problems \[esp that presented to undergraduates in textbooks\], which are nec. decision problems, which might lead to a mistaken impression that other types of problem formats are not as central to the theory. Also NP complete is sometimes shown in a hierarchy that includes other complexity classes such as PSpace which can be used to measure *function* complexity in addition to *decision* complexity.

Think that the N-Queens example question & related comments also shows that a bunch of related questions about the same problem in this case N-Queens can vary widely/dramatically in their complexity depending on slight variations of the phrasing. e.g. in this case:

* Is there a solution to the N-Queens problem on a $n \times n$ chessboard? this problem turns out to have O(1) time complexity— the answer is always Y.
* What is the complexity of finding a solution to the N-Queens problem given $n$ as the input referring to a square $n \times n$ chessboard? as that question notes in comments by Peter Shor, an advanced and subtle thm from CS called "mahaney's" thm applies because it might refer to a "sparse input". also JeffE found a paper that says its in P.
* There is an NP complete or NP hard version of this problem if the squares are *irregularly specified* as the input. i.e. some kind of input that specifies the square allowed/unallowed locations (haven't looked up the details).

---

While advanced theorists may find all this verging on trivial, feel its a legitimate area of focus which sometimes gets glossed over in theoretical treatments. my question
> Is there a reference somewhere that points/sorts out these kinds of subtleties/difficulties in formulating CS problems?

It would be helpful if it also talks about how the issue relates to the complexity hierarchy. know that this is covered in some textbooks, but even then haven't seen a nice concise discussion of that and wonder if anyone has a favorite ref for this type of issue. (suppose Garey and Johnson might have some discussion of this although don't have a copy close to check.)

Am not specifically focused on the N-Queens problem with this question, but an answer that sketches out the distinctions wrt N-Queens might be helpful. \[eg an expanded explanation of Shor's comment how Mahaneys thm applies, the irregular board construction input format, etc\]

fyi here are two other example problems Ive noticed that can vary widely in complexity depending on various restrictions on the input

Post correspondence problem. it can go from undecidable to NP complete or even in P depending on various restrictions on the solution.

\[2\] Finding whether a regular expression is equivalent to all strings over the alphabet. with squaring this was shown to be in ExpSpace by Stockmeyer/Meyer, but restrictions on length lead to it to being in NP complete or P. see e.g. Chee Yap, Intro to Complexity classes, ch5 on complete problems.

# Answer
> 10 votes
A quick highlight to underline how easily the time complexity of a *function* problem (calculate $f(x)$) can differ from the time complexity of the corresponding *decision* problem (is $f(x)=^?y$).

If we take $f(x) = 2^x$, then in order to calculate $f(x)$ we need exponential time, but the corresponding decision problem $\\{ (x,y) | f(x)=y \\}$ is trivially in $P$ (given $x$ and $y$ just check that $y$ is a 1 followed by $x$ 0s).

The difference between search and decision is underlined (and explained) in many books and a lot of information can also be found online.

For example given an $NP$ problem, it is obvious that if you can quickly find a solution then you can quickly answer if the problem has a solution or not; hence the decision problem reduces to the search problem in $O(1)$. But the question: "Does search reduce in polynomial time to decision?" is more subtle. It is easy to prove that if you have an oracle for $SAT$ then you can solve in polynomial (linear) time the corresponding search problem: if the formula is not satisfiable then output undefined, else for each variable $x\_i$, set it to true and call the oracle, if the formula is not satisfiable then set $x\_i$ to false (this technique is called *self-reducibility*).

It turns out that this result can be extended to all $NP$-complete problems.

But for problems that are not $NP$-complete, under a complexity assumption ($EE \neq NEE$), there is a language in $NP$ for which search does not reduce to decision (see "The Complexity of Decision versus Search").

# Answer
> 2 votes
Check out this lecture by Sam Buss on total NP search problems: http://www.newton.ac.uk/programmes/SAS/seminars/032811301.html. It discusses how to define complexity classes, reductions, and completeness for search problems which always have a solution but such a solution may be hard to find.

Note, that any theorist realizes that function problems are important and are often the object we're *really* interested in. The focus on decision problems is usually entirely for the purpose of lower bounds. It is often more convenient to prove a lower bound on a decision problem, so we choose a decision problem which can be solved if the function problem could be solved. Then the lower bound on the decision implies a lower bound on the function problem.

As Vor explains, in many cases of interest, decision and search are also equivalent, by some version of binary search/self reducibility. But total search problems are one example where this equivalence fails (solutions always exist, but may be hard to find). A popular example is computing mixed Nash equilibria.

---
Tags: algorithms, complexity-theory, reference-request, time-complexity, np-complete
---


# Question
Title: Chromatic polynomial of a cycle - Interpreting its terms
I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C\_n, n \ge 3$).

$P(C\_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda - 1)$, where $\lambda$ is the number of colours available

Is it possible to interpret the terms of above polynomial? I need help doing the same.

# Answer
> 2 votes
There is a theorem of Whitney answering your question. Let $$ P(G,\lambda) = \sum\_{k=0}^n (-1)^k a\_k \lambda^{n-k}. $$ Then $a\_k$ is the number of $k$-subsets of the edges of $G$ not containing any *broken cycle*. A broken cycle of $G$ is obtained from a cycle of $G$ by removing its maximum edge according to some fixed ordering of the edges.

For example, if $G = C\_n$ then for $k \< n-1$, $a\_k = \binom{n}{k}$, and $a\_{n-1} = \binom{n}{n-1} - 1$, since we miss one broken cycle.

For a proof and references to other proofs, see this paper.

---
Tags: graphs
---


# Question
Title: How to calculate the number of states in designing a Turing machine?
I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example:

$\qquad \displaystyle L = \\{wcw \mid w \in \\{0,1\\}^\*\\}.$

I mean how to know how many states are there in the set $Q$, with the information from the description of that language.

# Answer
> 3 votes
I think that given a decidable language $L$, you can always build a *2-states* TM that recognizes it.

Indeed there exists a 2 state Universal Turing Machine $UTM\_{2U}$ (with alphabet $|\Sigma| \geq 18$).

If $TM\_i$ decides $L$ then $UTM\_{2U}(i,x)$ decides $L$; so you can build a 2-states $TM\_{2L}$ hard encoding $i$ in $UTM\_{2U}$ but keeping only two states; the idea is:

* add $2\*|i|\*|\Sigma|^{|i|}\*|\Sigma|$ symbols to the alphabet that will represent the possible combinations of *(state, head position, tape content, first symbol $\alpha$ of $x = \alpha x'$ on the tape)* of $UTM\_{2U}$ on input $(i,\alpha x')$
* adjust the transition table of $TM\_{2L}$ in order to simulate the behaviour of $UTM\_{2U}$ on the first $|i|+1$ characters of the tape using only the first cell of the tape (that initially will contain $\alpha$).

### EDIT (alternate take :)

Given a generic $TM\_L$ that recognizes $L$ there is an *easier way* to build an equivalent 2-states $TM\_{2L}$.
I'll try to sketch its construction (*anybody wants to check if it is correct?* :)

**Idea**: simulate $TM\_L$ using the tape to store at the same time the alphabet symbol of the original tape, plus the current state and head position of $TM\_L$.
A single cell of the tape is a 5-tuple:

```
[(direction)(symbol)(current_state)(state_to_copy)]

```

that represents:

```
direction: 0 = we are scanning the tape from left to right
           1 = we are scanning the tape from right to left
symbol:    symbol from the alphabet of TM_L
current_state: if > 0 then the head position of TM_L is here and
               the state is current_state
state_to-copy: if > 0 then we are copying the next state to
               the left or right according to direction

```

Using the direction flag we can move from left to right and "execute" the $TM\_L$ transitions that moves the head to the right (i.e. we can copy the next head/state to the right), then we can go back and "execute" the $TM\_L$ transitions that moves the head to the left (i.e. we can copy the next head/state to the left).
The transition table with two states is built in the following way:

### STATE0

**...from LEFT to RIGHT**

```
// scan left to right until we found the cell with the head
Read(0, X, 0, 0)  -> Write(1, X, 0, 0)    stay in STATE0 and move R

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then add the
// following transition  which will start the copy of Qj on the right cell
Read(0, A, Qi, 0) -> Write(0, B, 0, Qj-1) enter STATE1 and move R

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then
// add the following transition (we will process it later):
Read(0, A, Qi, 0) -> Write(1, A, Qi, 0)   stay in STATE0 and move R

// if we are copying a state to the right continue:
Read(0, X, 0, Qj) -> Write(0, X, 0, Qj-1) enter STATE1 and move R

// when we reach a blank symbol, start moving from right to left
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move L

```

**... from RIGHT to LEFT**

```
// scan right to left until we found the cell with the head
Read(1, X, 0,  0) -> Write(0, X, 0, 0)    stay in STATE0 and move L

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then add the
// following transition which will start the copy of Qj on the left cell
Read(1, A, Qi, 0) -> Write(1, B, 0, Qj-1) enter STATE1 and move L

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then
// add the following transition (we will process it later):
Read(1, A, Qi, ) -> Write(0, A, Qi, 0)    stay in STATE0 and move R

// if we are copying a state to the left continue:
Read(1, X, 0, Qj) -> Write(1, X, 0, Qj-1) enter STATE1 and move L

// when we reach a blank symbol, start moving from left to right
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move R

```

### STATE1

```
// we are copying the head/state to the right
Read(0, Y, Qk, 0) -> Write(0, Y, Qk+1, 0) enter STATE0 and move L

// we are copying the head/state to the left
Read(1, Y, Qk, 0) -> Write(1, Y, Qk+1, 0) enter STATE0 and move R

```

The 5-tuple (direction)(symbol)(current\_state)(state\_to\_copy) must be encoded using a single symbol of $TM\_{2L}$, so its alphabet size is:

$|\Sigma\_{2L}| = 2 \times |\Sigma\_L| \times |Q\_L| \times |Q\_L|$

**P.S.** with the same technique (if it is correct) a generic UTM can be converted to a *2-states* UTM ... unfortunately we are not in 1956 :-)))

# Answer
> 2 votes
If there is a Turing machine that can compute a given language at all, which in your case there is, then there must be at least one such machine, which the number of its states are no more than any other alike TM, i.e. You may always ask what is the minimal TM (with minimum number of states) which could accept a given language (and anticipate infinity, if the language can not be generated by an unrestricted grammar). But, as far as I know, this is a deep and difficult question and I imagine no one knows a general description of such relation, except for restricted cases. Otherwise, my hope is an expert would join this question and give us some light. (I have assumed that the number of alphabets is some constant, not subject to manipulation)

# Answer
> 0 votes
it has been known since Shannon 1956 that "small" (in either states or alphabets) universal Turing machines exist and there is a long history of their study, see \[1\] for a survey. this implies that any Turing machine can be converted to those universal Turing machines as Vor sketches out in his answer as an example. there is a systematic study of this subject in Kolmogorov complexity and the "minimal description". but basically its tightly coupled with incompleteness phenomena such that the minimum description is not really computable in general.

\[1\] Small universal Turing machines by Neary

---
Tags: formal-languages, turing-machines, descriptive-complexity
---


# Question
Title: Planarity conditions for Planar 1-in-3 SAT
**Planar 3SAT** is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:

1. add a vertex for every $x\_i$ and $\bar{x\_i}$
2. add a vertex for every clause $C\_j$
3. add an edge for every $(x\_i,\bar{x\_i})$ pair
4. add an edge from vertex $x\_i$ (or $\bar{x\_i}$) to each vertex that represent a clause that contains it
5. add edges between two consecutive variables $(x\_1,x\_2),(x\_2,x\_3),...,(x\_n,x\_1)$

In particular, rule 5 builds a "backbone" that splits the clauses in two distinct regions.

**Planar 1-in-3 SAT** is NP-complete, too.

> But for planar 1-in-3 SAT are the planarity conditions defined in the same way as in Planar 3SAT ? In particular, can we assume that there is a backbone that links the variables $(x\_i,x\_{i+1})$ ?

# Answer
> 10 votes
Yes you can. Actually you can even show that something stronger is true. The problem know as **Positive Planar 1-in-3-SAT** is NP-complete as shown by Mulzer and Rote.

In this version of 1-in-3-SAT, you require for every input formula that

* you have three variables per clause, none of them negated
* the graph of the formula is planar, even if you add the "backbone" between the variable vertices

The reduction is from **Planar 3-SAT**.

---
Tags: np-complete, reductions, satisfiability, 3-sat
---


# Question
Title: Proof of equivalence of parse-trees and derivations
Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa.

Is this intuition correct? If so how can I formalize and prove such a thing?

# Answer
> 3 votes
**Theorem**. Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $\forall A \in V, A \rightarrow^\* \alpha \Leftrightarrow \exists$ a parse-tree $T'$ rooted at node $A$ with yield $\alpha \in (V \cup T)^\*$.

Meanings of symbols:

1. $V$ is the set of non-terminals
2. $T$ is the set of terminals
3. $P$ is the set of productions
4. $S \in V$ is a designated start symbol.

A parse-tree $T'$ for a derivation is defined as follows:

1. The root is labeled with a symbol $\in V$
2. If $T'$ has a node labeled $A$ whose children are labeled $X\_1, X\_2, \dots, X\_n$ such that $X\_i$ is to the left of $X\_j$ for all $i \lt j$, then $A \rightarrow X\_1X\_2\dots X\_n$ is a production $\in P$.

*proof*. We prove $\forall A \in V, A \rightarrow^\* \alpha \Rightarrow\exists$ a parse-tree $T'$ rooted at $A$ with yield $\alpha \in (V \cup T)^\*$ and vice-versa. We will refer to a node with label $L$ as node $L$.

First we show the ($\Leftarrow$) part.

Assume there is a parse-tree $T'$ rooted at $A$ with yield $\alpha$. If the tree has $1$ internal node, then $A \rightarrow \alpha$ is a production in $P$ (by definition of a parse-tree). Since $A \rightarrow \alpha \Rightarrow A \rightarrow^\* \alpha$, we are done.

Assume that the ($\Leftarrow$) part holds for all parse-trees with fewer than $n$ internal nodes (induction hypothesis). If the parse-tree has $n \gt 1$ internal nodes, let $X\_i, i = 1, 2, \dots, m$ (be it a non-terminal or a terminal) denote the label of the $i^{th}$ child of the root-node $A$. Each of the $X\_i$ nodes has fewer than $n$ nodes. By the induction hypothesis, each of the $X\_i$ nodes is the root of a parse-tree with yield $x\_i$. Knowing that all the descendants of $X\_i$ are to the left of all of the descendants of $X\_j$ for all $i \< j$, we can write $\alpha = x\_1x\_2\dots x\_m$. $A \rightarrow X\_1X\_2\dots X\_m$ is a production in $P$ and a derivation looks like: $A \rightarrow X\_1X\_2\dots X\_m \rightarrow^\* x\_1X\_2\dots X\_m \rightarrow^\* \dots \rightarrow^\* x\_1x2\dots x\_m = \alpha$.

Now we show the ($\Rightarrow$) part.

Assume $A \rightarrow^\* \alpha$ for some $A \in V$. If $A \rightarrow \alpha$, then the tree in Fig. 1 is a parse-tree with yield $\alpha$ and we are done.

Assume that the ($\Rightarrow$) part holds for all derivations with fewer than $n$ steps (induction hypothesis). If $A \rightarrow^\* \alpha$ is a derivation with $n$ steps, let $A \rightarrow X\_1X\_2\dots X\_n$ be the first step in the derivation-chain. Let $V' = {X\_1, X\_2, \dots, X\_n} \cap V$. Each of the elements of $V'$ derives a sub-string of $\alpha$ with fewer than $n$ steps. By the induction hypothesis, there is a parse-tree rooted at node $V'\_i$ with yield $v'\_i$. We form a parse tree rooted at $A$ with yield $\alpha$ as follows:

1. Add a root-node labeled with $A$
2. Add a link between $A$ and every node labeled with a symbol $\in V'$
3. Add a link between $A$ and every node labeled with a symbol $\in \\{X\_1, X\_2, \dots, X\_n\\} \cap T$

This ends the proof.

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


# Question
Title: Eliminating useless productions resulting from PDA to CFG converison
In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.

For example, for two transitions, I am getting the following productions

> $$\begin{gather\*} \delta(q\_0,1,Z) = (q\_0,XZ) \\ {}\[q\_0,Z,q\_0\] \to 1\[q\_0,X,q\_0\]\[q\_0,Z,q\_0\] \\ {}\[q\_0,Z,q\_0\] \to 1\[q\_0,X,q\_1\]\[q\_1,Z,q\_0\] \\ {}\[q\_0,Z,q\_1\] \to 1\[q\_0,X,q\_0\]\[q\_0,Z,q\_1\] \\ {}\[q\_0,Z,q\_1\] \to 1\[q\_0,X,q\_1\]\[q\_1,Z,q\_1\] \\ \end{gather\*}$$
>
> $$ \begin{gather\*} \delta(q\_1,0,Z) = (q\_0,Z) \\ {}\[q\_1,Z,q\_0 \] \to 0\[q\_0,Z,q\_0\] \\ {}\[q\_1,Z,q\_1 \] \to 0\[q\_0,Z,q\_1\] \\ \end{gather\*}$$

How do I decide which state makes it into final production, and which one will be excluded ?

# Answer
> 3 votes
It is not very clear what you wish to achieve. Do you wish to reduce the number of productions to the minimal possible? Do you only wish to avoid productions that are "not helpful" i.e., never appear in any valid derivation?

The first question seems difficult (e.g., This Work shows that it is NP-hard to approximate the length of the smallest grammar within a certain constant factor)

If you talk about the second issue, more things can be done. You should look on methods for converting grammar into a *normal form* (like Chomsky\- or Greibach\- normal form), since usually the first step in those conversions is to eliminate any unnecessary productions.

To be more specific, the most easy thing we can do, is to eliminate **unreachable** variables:

> For a given grammar $G=(V,T,S,P)$, we say that some variable $X \in V$ is *unreachable* if it cannot be reached from $S$, that is, there is no $\alpha \in (V \cup T)^\*$ such that $S\to^\* \alpha$ and $X\in \alpha$.

You can find unreachable variables by a straightforward BFS search starting from "$S$".

To complete the answer, let me also note that there are another type of variables, which we call **unproductive** (or "dead"). Those variables will cause the derivation never to terminate. Formally:

> We say that a variable $X\in V$ is *unproductive* if for any $\alpha \in (V\cup T)^\*$ such that $X\to^\*\alpha$, $\alpha$ has at least one variable, that is, $\alpha \notin T^\*$.

For instance, if $S\to A \mid 1$ and $A\to A1$, then $A$ is unproductive—you can never get rid of it. Unproductive variables are also quite easy to find, and can be removed from the grammar (possibly along with some other productions, in which they appear on the right-hand-side.)

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


title: Hardness and directions of reductions

text:
# Question
Title: Hardness and directions of reductions
Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard.

As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By conflating one of the colors in the 3-coloring you have a 4-coloring, ergo 4-coloring is hard.

That's the how. But why is this a proof that 4-coloring is hard? Is it that you can use the solution to the 4-coloring problem to solve the 3-coloring problem? If so, how? If not, why is it a valid proof?

Bonus q: Must the polynomial reductions be able to go in both ways?

Edit: if you would be able to explain why this is so by an example you would do the internet a favor. I couldn't find this explained in a concrete way anywhere.

# Answer
A reduction from a problem $A$ to another problem $B$ is a transformation $f$ of any instance $a$ of $A$ into an instance $f(a)$ of $B$, such that

$$\qquad\qquad x∈A ~~⇔~~ f(x)∈B \qquad \qquad (E)$$

If $f$ is a transformation preserving the complexity you are interested in (e.g. $f$ is a polynomial transformation if you consider $\mathsf{NP}$-hardness) then the existence of an algorithm $\mathcal A\_B$ solving $B$ implies the existence of an algorithm solving $A$: it is enough to run $f$, then $\mathcal A\_B$.

Hence the existence of such a reduction from $A$ to $B$ means that $B$ is not easier than $A$. It is not necessary to have a reduction the other way.

For example, for graph coloring. You can reduce 3-coloring to 4-coloring but not in the immediate way. If you take a graph $G$ and you choose $f(G)=G$ then you will have that $x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$ but you don't have $f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$ of course. The conclusion is that the equivalence $(E)$ is not respected, so $f$ is **not** a reduction.

You can build a correct reduction $f$ from $3\mathsf{COL}$ to $4\mathsf{COL}$ but it is a little more complicated: for any graph $G$, let $f(G)$ be the graph $G$ extended with another node $u$ that is linked with an edge to every other node.

* The transformation is complexity-preserving (polynomial, here);
* if $G$ is in $3\mathsf{COL}$ then $f(G)$ is in $4\mathsf{COL}$: just use the fourth color for $u$;
* if $f(G)$ is in $4\mathsf{COL}$ then you can prove that all the nodes except $u$ have a color that is not $u$'s, hence $G$ is in $3\mathsf{COL}$.

That proves that $f$ is a reduction and that $4\mathsf{COL}$ is harder than $3\mathsf{COL}$. You can prove the same way that $n\mathsf{COL}$ is harder than $m\mathsf{COL}$ for any $n≥m$, the interesting proof being of the fact that $3\mathsf{COL}$ is harder than any $n\mathsf{COL}$.
> 7 votes

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


# Question
Title: Fastest square root method with exact integer result?
I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in \[0,30000^2\]$. The common `sqrtf(x)` on C language is too slow for this case, however it always gives me the correct result. I've tried with the Newton's method but I get very small errors when the square root of a number is exact. This leads to an uncertain pattern of $s-1$ results along the interval. If I increase the number of iterations the method becomes too slow but more exact.

Does anyone know of faster methods or directions on the latest research done in the area?

note to clarify: input is idealy a real number (i.e floating point) but i also accept solutions with integer as input.

# Answer
You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$ such that $|z - \sqrt{x}| \< 1$. You can just:

* Compute $z = \mathcal{A}(x)$
* Let $z\_0 = \lfloor z \rfloor$
* Let $S = \\{z\_0 - 1, z\_0, z\_0 + 1\\}$
* Output $y = \max\\{y \in S: y^2 \leq x\\}$ (in words: output the largest integer among $z\_0 - 1$, $z\_0$, $z\_0 + 1$ whose square is at most $x$).

You can also verify you have the correct number by checking that $(y+1)^2 \> x$.

Correctness follows from the fact that if $|z - \sqrt{x}| \< 1$, then $|\lfloor z \rfloor - \lfloor \sqrt{x} \rfloor| \leq 1$.

I think Newton's method with a small number of iterations is the best thing you can do. Since you only need error smaller than 1, I believe a few iterations will indeed suffice. Doing extra three integer multiplications and comparisons at the end cannot slow you down so much.
> 5 votes

---
Tags: algorithms, integers, discrete-mathematics
---


# Question
Title: How do you prove that two languages are equivalent?
How can you show that the Language accepted by an NFA and the reverse NFA is the same?

For a language $L$, there is an $L^R=\\{ w^R \mid w \in L\\}$

Let's say that $w^R$ is the string obtained by reversing the string $w$.

I know that it involves using induction on the length of the input, but I would really appreciate some help.

# Answer
> 5 votes
There's an algorithm for this. Construct a DFA from you NFA, construct the reverse DFA, and check whether the two DFAs accept the same language (for example, you could construct the DFA for the symmetric difference and see if it accepts anything). If you want a more serious answer, you'll need to tell us more about your $L$.

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


# Question
Title: If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?
I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components.

I believe I have an algorithm to identify sources and sinks in the input list of edges in form

```
1 2
2 5
3 1
etc

```

And I know that the minimum number of edges to be added in order to create connected components is equal to MAX(sources,sinks).

My question is, is there a way to come up with where I should add edges so that I can have the minimum number and still be linear complexity?

Here is an example of what I'm after.

Given this input edges:

```
1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

```

Output these edges to be added:

```
3 1
4 5
7 6
8 1
9 2

```

# Answer
Assuming there are no isolated vertices in the graph you only need to add $max(|\mbox{sources}|,|\mbox{sinks}|)$ edges to make it strongly connected.

Let $T = \lbrace t\_1,\ldots,t\_n\rbrace$ be the sinks and $\lbrace s\_1,\ldots,s\_m \rbrace$ be the sources of the DAG. Assume that $n \le m$ (the other case is similar). Consider a bipartite graph $G(T,S)$ between the two sets defined as follows: $G(T,S)$ has an edge $(t\_i, s\_j)$ if and only if $t\_i$ can be reached from $s\_j$.

Let $M$ be a maximal matching in $G(T,S)$. Without loss of generality assume that $M$ consists of $k$ edges: $\lbrace (t\_1, s\_1), (t\_2, s\_2), \ldots, (t\_k, s\_k) \rbrace$. In the original DAG $G$, add directed-edges $\lbrace (t\_1\rightarrow s\_2), (t\_2\rightarrow s\_3), \ldots, (t\_{k-1}\rightarrow s\_k),(t\_k\rightarrow s\_1)\rbrace$. It's easy to see that by adding these edges, the vertices induced by $M$ are strongly connected in $G$.

Now consider the remaining vertices in $G(T,S)$. Because $M$ is maximal, each vertex in $S-M$ (resp. $T-M$) should be connected to a vertex in $T$ (resp. $S-M$). So we pair up the remaining vertices arbitrarily, say $\lbrace (t\_{k+1}, s\_{k+1}), \ldots, (t\_n, s\_n)\rbrace$ and add the corresponding directed edges in $G$. For each remaining source vertex source $s\_i$ ($i$ belongs to $\lbrace n+1,\ldots, m\rbrace$ we add the edge $(t\_1\rightarrow s\_i)$ in $G$. Thus the total number of edges added is $max(|\mbox{sources}|,|\mbox{sinks}|)$.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Understanding the definition of reduction
From Wikipedia:

> Given two subsets A and B of N and a set of functions F from N to N which is closed under composition, A is called reducible to B under F if $$ \exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B $$ We write $$ A \leq\_{F} B $$ Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if $$ \forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Rightarrow A \in S $$ A subset A of N is called hard for S if $$ \forall s \in S \mbox{ . } s \leq A $$ A subset A of N is called complete for S if A is hard for S and A is in S.

I am trying to relate the above definitions to those for problems: problem A can be reduced to problem B, a set of problems are NP-hard, a set of problems are NP-complete. But I don't know how to relate. I think one link I am missing is to see how a subset of problem can be seen as a subset of $\mathbb{N}$?

# Answer
> 8 votes
The definition you're quoting is very abstract, but the concepts you're trying to understand are pretty intuitive. A problem $A$ is NP-hard if you can solve any problem in NP using it. This means that any $B \in NP$ can be reduced to $A$, i.e. there is some polytime function $f$ such that $x \in B$ iff $f(x) \in A$; so you can test whether $x \in B$ by computing $f(x)$ and test whether the latter is in $A$.

A problem is NP-complete if it is both in NP-hard and in NP. This means that it is hardest among problems in NP. A problem can be NP-hard without being in NP, for example the halting problem.

You're mentioning sets of problems as belonging to NP, but that's a typing error: members of NP are problems, in the guise of subsets of the set of natural numbers (or of the set of finite binary strings, which is the same). The subset specifies the set of inputs for which the problem has the answer YES.

---
Tags: complexity-theory, terminology, reductions
---


# Question
Title: What is an example for which the purely functional programming approach gives better results than imperative style?
*I* have seen some questions related to functional programming on stackexchange sites which suggests it has significant popularity. *I* have some experience with it from many *years* ago in Lisp/Scheme and have seen commentary on the difference between functional and imperative/mutable approaches eg \[4\].

*The* wikipedia page on the *subject* says "Pure functional programming disallows side effects completely and so provides referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks." *But* it is known to have a cost of up to a factor of $O(\log(n))$ slowdown factor \[2\] due to lack of mutable data structures, leading to a lot of research in functional programming datastructures that have a much different flavor than mutable approaches \[3\].

*Along* these lines,

> *What* is an example for which the purely functional programming approach leads to better overall results than the imperative approach?

(*Also* it seems the word "mutable" here is a bit subtle. functional languages appear to allow one to "store" data eg via balanced trees, but not later "change" it. *This* is a little different than mutability eg in java, where initial storage and later changing are nearly identical operations eg with "setter" methods on the Java objects.)

\[1\] functional programming, wikipedia

\[2\] stackexchange, efficiency of purely functional programming

\[3\] tcs.se, What's new in purely functional data structures since Okasaki?

\[4\] Structure and interpretation of computer programs, by Abelson & Sussman

# Answer
> 8 votes
"Better" is obviously subjective but Evan Farrer did his master's thesis on rewriting python programs into Haskell (a purely functional language) and seeing how many bugs it caught. You can read his paper, but the Haskell compiler caught many non-trivial bugs.

A less controversial example is that pure languages are more easily parallelized.

---
Tags: programming-languages, functional-programming
---


# Question
Title: Fast k mismatch string matching algorithm
I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P matches a substring of T with at most k mismatches. This is different from the k-differences problem (edit distance). A mismatch implies the substring and the pattern have a different letter in at most k positions. I really only require k=1 (at most 1 mismatch), so a fast algorithm for the specific case of k=1 will also suffice. The alphabet size is 26 (case-insensitive english text), so space requirement should not grow too fast with the size of the alphabet (eg., the FAAST algorithm, I believe, takes space exponential in the size of the alphabet, and so is suitable only for protein and gene sequences).

A dynamic programming based approach will tend to be O(mn) in the worst case, which will be too slow. I believe there are modifications of the Boyer-Moore algorithm for this, but I am not able to get my hands on such papers. I do not have subscription to access academic journals or publications, so any references will have to be in the public domain.

I would greatly appreciate any pointers, or references to freely available documents, or the algorithm itself for this problem.

# Answer
> 5 votes
Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA.

Once the suffix array has been constructed, we need to construct a Longest Common Prefix (LCP) array for the suffix array. The LCP array stores the length of the longest common prefix between two consecutive prefixes in the suffix array (lexicographic consecutive suffixes). Thus, LCP\[i\] contains the length of the longest common prefix between SA\[i\] and SA\[i+1\]. This array can also be constructed in linear time: see here, here and here for some good references.

Now, to compute the length of the longest prefix common to *any* two suffixes in the suffix tree (instead of consecutive suffixes), we need to use some RMQ data structure. It has been shown in the references above (and can be seen easily if the array is visualized as a suffix tree), that the length of the longest common prefix between two suffixes having positions $u$ and $v$ ($u \< v$) in the suffix array, can be obtained as $min\_{u\<=k\<=v-1}{LCP\[k\]}$. A good RMQ can pre-process the $LCP$ array in $O(n)$ or $O(n\log n)$ time and respond to queries of the form $LCP\[u, v\]$ in $O(1)$ time. See here for a succint RMQ algorithm, and here for a good tutorial on RMQ's, and the relationship (and reductions) between LCA and RMQs. This has another nice alternative approach.

With this information, we construct the suffix array and associated arrays (as described above) for the concatenation of the two strings with a delimiter in between (such as T#P, where '#' does not occur in either string). Then, we can perform k mismatch string matching using the "kangaroo" method. This and this explain the kangaroo method in the context of suffix trees, but can be directly applied to suffix arrays too. For every index $i$ of the text $T$, find the $LCP$ of the suffix of $T$ starting at $i$ and the suffix of $P$ starting at 0. This gives the location after which the first mismatch occurs when matching $P$ with $T\[i\]$. Let this length be $l\_0$. Skip the mismatching character in both $T$ and $P$ and try to match the remaining strings. That is, again find the $LCP$ of $T\[i + l\_0 + 1\]$ and $P\[l\_0 + 1\]$. Repeat this till you obtain $k$ mismatches, or either string finishes. Each $LCP$ is $O(1)$. There are $O(k)$ $LCP$'s for each index $i$ of $T$, giving this a total complexity of $O(nk)$.

I used an easier to implement RMQ giving a total complexity of $O(nk + (n+m)\log(n+m))$, or $O(nk + n\log n)$ if $m = O(n)$, but it can be done in $O(nk)$ too as described above. There may be other direct methods for this problem, but this is a powerful and generic approach that can be applied to a lot of similar problems.

# Answer
> 4 votes
Below is an expected $\mathcal{O}(n + m )$ algorithm (which can be extended to other $k$, making it $\mathcal{O}(nk +m )$). (I haven't done the calculations to prove it is so, though).

The idea is similar to the Rabin-Karp rolling hash algorithm for exact substring matches.

The idea is to separate each string of length $m$ into $2k$ blocks of $m/2k$ size each and compute the rolling hash for each block (giving $2k$ hash values) and compare those $2k$ hash values against the one from the pattern.

We allow at most $k$ mismatches in those values.

If more than $k$ mismatches occur, we reject and move on. Otherwise we try and confirm an approximate match.

I expect (caveat: haven't tried it myself) this will probably be faster in practice, and perhaps easier to code/maintain, than using a suffix tree based approach.

---
Tags: algorithms, reference-request, strings, string-metrics, substrings
---