title: Priority in formal grammar

text:
# Question
Title: Priority in formal grammar
From my recitation class, I have the following exercise:

> $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$
>
> The above grammar is ambiguous.
>
> Make an unambiguous grammar which produce same language as the above.
>
> In the new grammar, $a$ has priority over $b$ and $b$ has priority over $m$. Also $m$ is associative.

Can you explain what the phrases

* "has priority over" and
* "$m$ is associative"

mean?

# Answer
> 3 votes
`b0a` has two subtly different productions (Note: I always expand the leftmost non-terminal):

* `EXP --> bEXP --> bEXPa --> b0a` and
* `EXP --> EXPa --> bEXPa --> b0a`,

so that's an example of an ambiguous string.

To give `a` priority over `b` means that if you have `b0a` it will always be parsed as `b(0a)` (i.e. the first production I showed).

---

For the bit involving `b` and `m`, can you find two different productions for `b0m0`?

---

`1m1m0` also has two subtly different productions:

* `EXP -> EXPmEXP --> 1mEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0` and
* `EXP -> EXPmEXP --> EXPmEXPmEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0`.

To make `m` associative is to remove this ambiguity, so that only one of these parses is possible (from the question, it doesn't seem to matter which one exactly, as long as you choose one and stick to it!)

# Answer
> 2 votes
1. I'm going to guess that, in the case of your example grammar, that "$a$ has priority over $b$, and $b$ has priority over $m$" means that once a $b$ is generated, no more $a$s can be generated, and likewise, once an $m$ is generated, no more $b$s can be generated in any derivation using this grammar.
2. The general property of associativity for a (binary) operator $+$:

$\forall a,b,c\in U: (a +b)+c = a+(b+c)$

But, in the context of formal grammars, binary operators are generally declared to be either left-associative, meaning the string $a+b+c$ always has the meaning $(a+b)+c$, or right-associative, meaning the string $a+b+c$ always has the meaning $a+(b+c)$, or non-associative, meaning the string $a+b+c$ has no meaning (it is not a valid string in the language).

---
Tags: formal-languages, formal-grammars, parsing, ambiguity
---


title: Operators in descriptive complexity

text:
# Question
Title: Operators in descriptive complexity
When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ where $x$ is input? or is it something else?

Also, when we say $FO(t(n))$, what does quantifier block being iterated $t(n)$ times mean?

# Answer
First Part: Let's first define the TR operator (Why do you use $TR$ and not $TC$?) Given a formula $\phi$ with free variables $x\_{i\_1},\dots,x\_{i\_{2k}}$ than the string $\psi =TR(x\_{i\_1},\dots,x\_{i\_{2k}},\phi)(y\_{i\_1},\dots,x\_{i\_{yk}})$ is also a formula. If you now consider an interpretation $\mathcal{I}$ than $\psi$ is true under $\mathcal{I}$ iff $(y\_{i\_1},\dots,y\_{i\_{2k}})^{\mathcal{I}}\in R^+$, where $(y\_{i\_1},\dots,y\_{i\_{2k}})^{\mathcal{I}}$ is the tuple assigned to $(y\_{i\_1},\dots,y\_{i\_{2k}})$ by $\mathcal{I}$, $R$ is the binary Relation on $k$-tuples defined by $\phi$ and $^+$ the transitive closure.

As your input is (only) a structure, your Formula can't have free variables, but of course it can have constants, e.g. $\psi = TR(x\_1,x\_2,\phi,c\_1,c\_2)$ where $\phi$ is $x\_1 P x\_2$.

Let's assume your input ${\mathcal{G}}$ is a graph and two of it's vertices: $(V,E,v\_1,v\_2)$ ($E$ being a symmetric relation, not a set of pairs). Then $P^{\mathcal{G}} = E = R$ (the $R$ from above). Now $\psi^{\mathcal{G}}$ is true (i.e. your input accepted) iff $v\_1$ and $v\_2$ belong to the same connected component.

---

Second part: $t(n)$ is a function of the input size, so if your input has size $n$ the quantifier block is repeated as-is $t(n)$ times, using the same variables in each instance.

Again the example of checking whether there is a path:

$$QB(x,y) = (\forall z: \neg(x = y \vee x E y))\\\(\exists z )(\forall u)(\forall v (u = x \wedge v = z) \vee (u = z \wedge v = y)) \\\(\forall x: x=u)(\forall y: y=v)$$

This block consists of three parts:

1. Check if there's a short path (length 0 or 1), then "quit".
2. Check if there is an intermediate z.
3. Rename the variables to recurse.

Since $(\forall z \phi)\psi$ is short for $\forall z (\phi\rightarrow\psi)$ the formula $QB(x,y)\exists x\neq x$ is only satisfiable if $\neg(x = y \vee x E y)$ is false, i.e. there is a path of length $1$ or $0$ between $x$ and $y$.

If your input has size $n$, you only need $1+\log\_2 n$ recursion levels, i.e. $QB(x,y)^{1+\log\_2 n}\exists x\neq x$ tests whether $x$ and $y$ are in the same connected component.

This example is taken from: Expressibility and parallel complexity (Immerman,1989)
> 1 votes

---
Tags: complexity-theory, descriptive-complexity
---


title: Is The Following Language Regular?

text:
# Question
Title: Is The Following Language Regular?
Let $L\_{1}$ and $L\_{2}$ be 2 languages over the same alphabet $\Sigma$.

$$A(L\_1,L\_2)=\\{x\in \Sigma^\*|\exists y,z\in L\_2\text{ such that } yxz\in L\_1\\}$$

Assume that $L\_{1}$ is regular and $L\_{2}$ is context-free. The language $A(L\_{1},L\_{2})$:

1. is always a regular language
2. is always not a regular language
3. can sometimes be a regular language
4. cannot be context free

They say that the correct answer is 1.

# Answer
Hint: Take a DFA for $L\_1$. Check which states are reachable from the initial state via a word in $L\_2$. Check from which states a final state can be reached via a word in $L\_2$.
> 2 votes

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


title: Definition of uniform boolean circuit

text:
# Question
Title: Definition of uniform boolean circuit
> Definition
> A family of circuits $(C\_{1}, C\_{2}, \ldots)$ is uniform if some log space transducer $T$ outputs $\langle C\_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/Boolean\_circuit#Uniform\_Boolean\_Circuits)

Can anyone exlain this? I know what boolean circuits are, so only explanation needed is what and transducer exactly are.

# Answer
> 3 votes
Uniformity definition means that there is a deterministic Turing machine running in logarithmic space $\mathsf{L}$ that generates the description of the $n$th circuit from the unary encoding of $n$.

To have a better idea of what this is talking about, assume that we have a Turing machine $M$ in $\mathsf{P}$. Then for every input size $n$ we can generate a circuit of size $poly(n)$ that compute $M$ on inputs of size $n$. So we obtain a family of circuits $\\{C\_n\\}\_{n \in\mathbb{N}}$. However these circuits are not arbitrary independent circuits but coming from a single machine $M$.

The definition is good for large classes like $\mathsf{P}$ but it doesn't work for small complexity classes. For those classes we use deterministic logarithmic time $\mathsf{DLogTime}$ in place of $\mathsf{L}$. In place of printing the whole circuit we just require it to compute any given bit of the description of the $n$th circuit in logarithmic time.

# Answer
> 0 votes
A transducer is a finite state automata that (in effect) has both an input tape and an output tape. So instead of the normal DFA/NFA computation where the automaton has an input that it recognises (or equivalently, no input at all, and an output that it generates), a transducer reads from the input and writes to the output. Otherwise the definition is in essence a DFA/NFA.

So in this case the transducer takes a number (in the form of a string of $1$s - so $4$ would be $1111$) and produces the encoding of the circuit $C\_{n}$ ($\langle X \rangle$ means the encoding of $X$ under some \[sensible\] encoding scheme). So even though the family of circuits is infinite, they can be compactly expressed by giving the transducer.

More details about transducers can be found on the all-knowing wiki (side note, the name transducer is also used to mean some completely different things in other fields).

---
Tags: complexity-theory, finite-automata, circuits
---


# Question
Title: What does "number of gates" mean in circuit complexity?
By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.

# Answer
> 3 votes
The number of inputs to a gate is an independent restriction or allowance on the circuit. The number of gates in a circuit is simply the number of gates.

Of course you can always measure the two separately. For example the $W$-hierarchy in Parameterized Complexity can be defined in terms of the *large-gate depth* (called in this context the *weft*) of families of circuits (i.e. the maximum number of gates with unbounded fan-in on any path from the inputs to the output).

Of course we can also take an unbounded fan-in gate (if we're sticking to AND/OR at least) and replace it with a circuit consisting of a several bounded fan-in gates, but the size may increase significantly.

# Answer
> 3 votes
In the general sense Luke is right, there is no relation between the number of gates and fa-in.

But in the literature what authors mean depends on the context. Note that by itself the number of gates is not a robust notion. What kind of circuits are we talking about?

If we are talking about unbounded fan-in circuits for $\mathsf{AC^0}$ then we count each gate as one no matter what the fan-in is.

If we are talking about bounded fan-in circuits for $\mathsf{NC^1}$ then you should convert each such gate first into a number of bounded fan-in gate and then count it.

---
Tags: complexity-theory, circuits
---


title: Show that the multiplication lies in FL

text:
# Question
Title: Show that the multiplication lies in FL
I don't know exactly how to solve the exercise below.

> Show that the multiplication lies in $\text{FL}$.
>
> Hint: A useful approach to a solution is to split the exercise into two parts and to explain that each function lies in $\text{FL}$. The standard multiplication scheme can be used as an intermediate step. Example:
>
> $\begin{align} 1001 \cdot{} 1100 & = \\ 1001000\\ \+ \ \ \ 100100\\ \+ \ \ \ \ \ \ \ \ \ \ \ \ 0\\ \+ \ \ \ \ \ \ \ \ \ \ \ \ 0\\ \end{align}$
>
> Other useful approaches are certainly also accepted.

Useful definitions from our lecture notes:

---

Let $f : \Sigma^\* \to \Sigma^\*$ be a function, let $t : \mathbb N \to \mathbb N$ be a time bound and let $s : \mathbb N \to \mathbb N$ be a memory space bound.

$\bullet$ It is $f \in \text{FDTIME}(t),$ if there exists a DTM $M$ with an output tape, calculating $f$ and for which $T\_M \in O(t)$ holds.

$\bullet$ It is $A \in \text{FDSPACE}(s),$ if there exists an offline DTM $M$, calculating $f$ and for which $S\_M \in O(s)$ holds. The fields being written on the output band are not considered for the amount of memory space.

$\text{FP}=\bigcup\_{k \in \mathbb N} \text{FDTIME}(n^k), \text{FL}=\text{FDSPACE}(\log n)$

---

I think the hint wants me to find two functions (one for the multiplication and one for the addition), but I don't see how to find two functions that do the calculation of the example in the appropriate way. Can somebody help me, please?

# Answer
Hint: Consider the standard multiplication scheme. Suppose that we compute the sum column by column, starting with the LSB. How big is the carry we have to remember?

Comment: Multiplication is actually in NC1 (hard) and even in TC0 (harder).
> 3 votes

# Answer
Wikipedia gives great information about the complexity of various elementary operations.

Multiplication takes $n^2$ time by the "school-book" algorithm, and thus it is in $\mathsf{FTIME}(n^2)$ and in $\mathsf{FL}$. Better solutions exist.

Also, it's quite simple to see that all you need is 3 registers of size $2\log n$, to complete the schoolbook algorithm, so the problem is $\mathsf{FSPACE}(\log n)$
> 2 votes

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


# Question
Title: How to relate circuit size to the running time of Turing machine
From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/,

> Define, $M\_{\[x,c\]}$ as the deterministic Turing machine that operates as follows on an input $y$. The machine treats $x$ as a deterministic program, and simulates $x$ on input $y$. At the same time the machine runs a counter that stops its execution after steps $|y|^c$. If the machine accepts before the counter stops, then it accepts; otherwise, it rejects.
>
> Let $f(i,c)$ be the smallest natural number so that $M\_{\[i,c\]}$makes a mistake on the input $y$. Then, if $P \neq NP$ is true, the function $f(i,c)$ is always defined.
>
> Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that $$f(i,c) \> 2^{2^{|i|+c}}$$ Then, for infinitely many $n$, SAT has circuit size $n^{O(\log n)}$.
>
> Proof: Let $i\>1$ and $c$ be so that $$f(i,c) \> 2^{2^{|i|+c}}$$ Define $n = 2^{|i|+c-1}$. Note, that $c$ is at most $\log n$. Then, $M\_{\[i,c\]}$ on all $y$ of length $n$ is correct, since $y \leq 2^n = 2^{2^{|i|+c-1}} \< f(i,c)$. The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine. The machine, by definition, runs in time $|y|^c \leq n^c \leq n^{\log n}$

I am not getting this part. Can anyone explain this (to specify, “The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine” in the quote)? (So the question is how can we relate the running time of Turing machine to the size of the circuit.)

# Answer
The way to show that circuits are equivalent to TMs is as follows: for a TM, you encode it in binary (i.e states, transitions, etc.)

Then, you construct a circuit whose gates represent the transitions between each configuration of the TM. Since configuration transitions are local, then you only need local gates (i.e gates that depend on a constant number of inputs).

The idea is that you can compute configuration $c\_i$ from configuration $c\_{i-1}$ by examining the contents of 3 adjacent cells, and if the head of the machine is there, update them accordingly. It's rather technical to write formally, but it's a generally simple proof (See "Computational complexity" by Arora and Barak for a proof).

Using this proof, you see that the size of the circuit is polynomial in the running time of the machine and the input length, because the circuit is constructed in "levels", where each level corresponds to a configuration of the TM.
> 4 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Minimizing Turing machine-like automaton with no final states
I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):

* The tape is initially finite.
* The automaton can insert and delete cells from the tape.
* Actions are associated with states rather than with transitions (this includes head shift and tape manipulation).
* The automaton has no accepting/final state. The computation is only terminated when the machine exits the tape. The final state of the tape is the machine's output.

I know most of the states in the machine are redudant (equivalent to other states). However the good old DFA minimization algorithm won't work here, because it starts its work on the final states (which I don't have).

The algorithm should be efficiently computable (the machines in question have hundreds of thousands to millions of states).

Is this possible in the general case? Every algorithm I make up fails in some cases.

# Answer
What exactly is the difference between your machine and a TM? (apart from not having accepting states, which is quite meaningless since you have an output)

It sounds like this is a very powerful model, and its halting problem will be undecidable, let alone minimization.

EDIT: Minimizing TMs is undecidable (actually, not in $RE\cup coRE$). It is easy to reduce the universality problem to it: given a TM, if you could minimize it, then the minimal TM will consist of a single, accepting state iff its language is $\Sigma^\*$.
> 3 votes

---
Tags: turing-machines, automata, finite-automata
---


title: Algorithm for generating heat maps

text:
# Question
Title: Algorithm for generating heat maps
I am looking to generate a heat map from some data. I have a value and a location (longitude and latitude). I understand generating a colour from the value, however I'm not sure how I would go about generating the matrix to use for this.

I figure it's best to place the location points into buckets essentially (so that I have the same number of buckets as pixels in my map) but I'm not sure how to calculate the values for the buckets where I don't have any readings.

Has anyone got any experience with this?

Thanks!

# Answer
You have to interpolate the missing heat values. There's some mathematics that explains this pretty well (man, it's been a while) but, if I recall correctly, the correct physical way to do this (assuming no heat sources in the area being interpolated) is the following:

1. For each pixel for which there wasn't original data, assign the value of the pixel to the average value of all surrounding pixels.
2. Repeat (1) until no pixel changes its value by at least some $\epsilon$

To be safe, you should probably double-buffer this process, so that while doing the first step, changing the value of the first pixel doesn't affect the value for the second pixel. Example:

```
   5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0
   2.0 --- --- 1.0    2.0 3.0 2.5 1.0    2.0 2.6 2.6 1.0    2.0 2.8 2.5 1.0
   1.0 --- --- 3.0 => 1.0 2.0 2.5 3.0 => 1.0 2.4 2.4 3.0 => 1.0 2.3 2.5 3.0
   3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0

=> 5.0 4.0 4.0 3.0
   2.0 2.7 2.6 1.0
   1.0 2.3 2.5 3.0 ...
   3.0 3.0 2.0 4.0

```

Already the values are beginning to settle down a bit. This is easy and fast to automate, though naturally, you'll only get an approximation. See here and here for more information on the physics and mathematics behind this (and whether this is even applicable to your situation!!!)
> 4 votes

---
Tags: algorithms, matrices
---


# Question
Title: Does the following transformation preserve context-freeness?
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\\#} = \\{ x : x^i \in L$ for every $i=0,1,2,...\\}$. Is $L^{\\#}$ always context-free?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?

# Answer
Counter-example:

$L\_1 = \\{a^n b^n c^m \mid m,n \ge 1 \\}$

$L\_2 = \\{a^m b^n c^n \mid m,n \ge 1 \\}$

$L = (L\_1 \cdot L\_2^\*) \cup \epsilon$ is context-free.

Any nonempty word $x \in L^\\#$ has a prefix $p = a^n b^n c^m \in L\_1$. It must be $n = m$, because due to $L\_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:

$L^\\# = (\\{a^n b^n c^n \mid n \ge 1 \\} \cdot L\_2^\*) \cup \epsilon$, which is not context-free.
> 5 votes

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


# Question
Title: How does 'deforestation' remove 'trees' from a program?
I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the wikipedia entry on the technique it talked about 'removing trees' from a program.

I understand how a program can be parsed into a syntactic parse tree (is that right?), but what is the meaning of this use of deforestation for some kind of simplification (is it?) of programs? And how would I do it to my code?

# Answer
Yatima2975 seems to have covered your first two questions, I'll try to cover the third. To do this I'll treat an unrealistically simple case, but I'm sure you'll be able to imagine something more realistic.

Imagine you want to compute the depth of the *full* binary tree of order $n$. The type of (unlabeled) binary trees is (in Haskell syntax):

```
type Tree = Leaf | Node Tree Tree

```

Now the full tree of order $n$ is:

```
full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

```

And the depth of a tree is computed by

```
depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

```

Now you can see that any computation of $\mathrm{depth}\ (\mathrm{full}\ n)$ will first *construct* the full tree of order $n$ using $\mathrm{full}$ and then *deconstruct* that tree using $\mathrm{depth}$. Deforestation relies on the observation that such a pattern (construction followed by deconstruction) can often be *short-circuited*: we can replace any calls to $\mathrm{depth}\ (\mathrm{full}\ n)$ by a single call to $\mathrm{full\\\_depth}$:

```
full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

```

This avoids memory allocation of the full tree, and the need to perform pattern matching, which greatly improves performance. In addition, if you add the optimization

```
max t t --> t

```

Then you have turned an exponential time procedure into a linear time one... It would be cool if there was an additional optimization that recognized that $\mathrm{full\\\_depth}$ was the identity on integers, but I am not sure that any such optimization is used in practice.

The only mainstream compiler that performs automatic deforestation is GHC, and if I recall correctly, this is performed only when composing *built-in* functions (for technical reasons).
> 10 votes

# Answer
First, lists are a kind of trees. If we represent a list as a linked list, it's just a tree whose each node has either 1 or 0 descendants.

Parse trees are just an utilization of trees as a data structure. Trees have many many applications in computer science, including sorting, implementing maps, associative arrays, etc.

In general, list, trees etc. are recursive data structures: Each node contains some information and another instance of the same data structure. Folding is an operation over all such structures that recursively transforms nodes to values "bottom up". Unfolding is the reverse process, it converts values to nodes "top down".

For a given data structure, we can mechanically construct their folding and unfolding functions.

As an example, let's take lists. (I'll use Haskell for the examples as it's typed and its syntax is very clean.) List is either an end or a value and a "tail".

```
data List a = Nil | Cons a (List a)

```

Now let's imagine we're folding a list. At each step, we have the current node to be folded and we have already folded its recursive sub-nodes. We can represent this state as

```
data ListF a r = NilF | ConsF a r

```

where `r` is the intermediate value constructed by folding the sublist. This allows us to express a folding function over lists:

```
foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil            = f NilF
foldList f (Cons x xs)    = f (ConsF x (foldList f xs))

```

We convert `List` into `ListF` by recursively folding over its sublist and then use a function defined on `ListF`. If you think about it, this is just another representation of standard `foldr`:

```
foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
  where
    g NilF          = z
    g (ConsF x r)   = f x r

```

We can construct `unfoldList` in the same fashion:

```
unfoldList :: (r -> ListF a r) -> r -> List a
unfoldList f r = case f r of
                  NilF        -> Nil
                  ConsF x r'  -> Cons x (unfoldList f r')

```

Again, it's just another representation of `unfoldr`:

```
unfoldr :: (r -> Maybe (a, r)) -> r -> [a]

```

(Notice that `Maybe (a, r)` is isomorphic to `ListF a r`.)

And we can construct a deforestation function too:

```
deforest :: (ListF a r -> r) -> (s -> ListF a s) -> s -> r
deforest f u s = f (map (deforest f u) (u s))
  where
    map h NilF        = NilF
    map h (ConsF x r) = ConsF x (h r)

```

It simply leaves out the intermediate `List` and fuses the folding and unfolding functions together.

The same procedure can be applied to any recursive data structure. For example, a tree whose nodes can have 0, 1, 2 or descendants with values on 1- or 0-branching nodes:

```
data Tree a = Bin (Tree a) (Tree a) | Un a (Tree a) | Leaf a

data TreeF a r = BinF r r | UnF a r | LeafF a

treeFold :: (TreeF a r -> r) -> Tree a -> r
treeFold f (Leaf x)       = f (LeafF x)
treeFold f (Un x r)       = f (UnF x (treeFold f r))
treeFold f (Bin r1 r2)    = f (BinF (treeFold f r1) (treeFold f r2))

treeUnfold :: (r -> TreeF a r) -> r -> Tree a
treeUnfold f r = case f r of
                  LeafF x         -> Leaf x
                  UnF x r         -> Un x (treeUnfold f r)
                  BinF r1 r2      -> Bin (treeUnfold f r1) (treeUnfold f r2)

```

Of course, we can create `deforestTree` just as mechanically as before.

(Usually, we'd express `treeFold` more conveniently as:

```
treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r

```

)

I'll leave out the details, I hope the pattern is obvious.

See also:
> 6 votes

# Answer
It's a bit confusing, but deforestation is applied (at compile time) to eliminate intermediate trees that would be created (at run time). Deforestation doesn't involve hacking away parts of the abstract syntax tree (that's dead branch elimination :-)

Another thing that may have thrown you off is that lists *are* trees, just very unbalanced ones!
> 4 votes

---
Tags: terminology, compilers, functional-programming
---


title: Longest path in undirected tree

text:
# Question
Title: Longest path in undirected tree
Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge has length 1 by default).
Obviously one idea is to check the path lengths between all pairs of vertices (e.g. by doing a DFS from each vertex), but there should be a more efficient solution. Please include a short proof in your answer.

# Answer
> 0 votes
I think one solution is to do a single DFS (from any node) to determine the longest path, in "divide and conquer" fashion. Apologies in advance for the clumsiness of the description - I'm not sure what's the proper notation for these things.

First, some background: at each step of the DFS we're exploring a subtree T, with the current vertex R considered to be the root of that subtree. All the neighbors of the root (excluding the "parent" in the DFS sense, which is not part of T) form subtrees T1, T2 ... Tk of T.
At each step, we determine both the longest path in T, let's call it p(T), and the longest root path in T (root path = path starting from R), let's call that rp(T).
To do that, we find the same for each subtree T1, T2 ... Tk, then
`rp(T) = R--longest(rp(Ti))`, i=1...k (I'm using "--" to symbolize joining the vertex R to the path), and
`p(T) = longest(rp(T), longest(p(Ti)), rp(T)--2ndlongest(rp(Ti)))`
Some explanation about the last term: it only appears if k\>1 (at least 2 subtrees), and it joins the 2 longest root paths in the subtrees, through R.
If k=0, then both p(T) and rp(T) are the 0-length path R.

I think a rigorous proof is not necessary - it is quite obvious that for each subtree T, p(T) is either in one of its subtrees Ti, or starts from R going into a subtree (this is rp(T)), or passes through R, going into 2 subtrees. And all the path parts going into subtrees must be the longest root paths in those subtrees. All the cases are handled.

As far as I can tell, the complexity is O(n) since this is a tree.

Implementation note: for each vertex we can store the lengths of p(T) and rp(T), a flag indicating which of the 3 situations we're in for p(T), references to (up to) 2 neighbors that contain a piece of p(T), and the next neighbor vertex for rp(T). At the end, we can reconstruct the longest path from this information.

# Answer
> 0 votes
I would use breath-first search and dynamic programming.

Let $A$ be a matrix where $A\[i,j\]$ is the distance between $v\_i$ and $v\_j$.

As we are in a tree, there are no loops and you can just counting the distances by taking the distances to the previous vertex and adding 1 to them.

Let $v\_v$ a vertex that has already been visited. In our matrix we know the distances from the other vertices. Let $v\_n$ be a new vertex, then the distances of the other vertices will be the ones for $v\_v$ plus 1.

So in every step of the algorithm you will know all the distances between all the vertices that have already been visited.

Base case is that you have visited just one vertex and it has zero distance to itself.

You also need to save the length of the longest path found so far and the indices of the vertices of the longest path and check them every time that you visit a new node.

---
Tags: algorithms, graphs, trees
---


# Question
Title: Difference between heuristic and approximation algorithm?
i have a problem regarding the following situation.

I have two arrays of numbers like this:

```
index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

```

now suppose the second array is very hard to compute but I have noticed that if I add

A\[i\] + A\[i+1\]

in the array 1 I get the number very close to the number A\[j\] in the array 2.

1. Is my solution a heuristic or approximation?
2. If I had a reason to believe that I will never overshoot the value of A\[j\] by +-x with this algorithm and can prove it, would then my solution be a heuristic or approximation?

Is there any literature that deals with heuristic vs. approximation questions for P class problems where the solution can be achieved in polynomial time but the input is just too big for a poly time algorithm to be practical.

thank you

# Answer
> 14 votes
A *heuristic* is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a *proof* it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a *plausible* idea, that *should not* give a too bad solution. In this case, it can be shown that it won't always give a good solution.

An *approximation algorithm* is usually understood to give an approximate solution, with some kind of guarantee of performance (i.e., it solves TSP, and the total cost is never off by more than a factor of 2; or even better, it solves TSP and, depending on \<some parameters that can be varied\> the solution is never worse than optimal by more than a factor $1 + \epsilon$, where $\epsilon$ depends on \<parameters\>).

# Answer
> 7 votes
You can see this very interesting answer about Heuristic in Wikipedia:

" a heuristic is a technique designed for solving a problem **more quickly** when **classic methods** are too slow. The objective of a heuristic is to produce quickly enough a solution that is good enough for solving the problem at hand. ".

Heuristic could derive from theory or experimental experience, but approximation algorithms have solid theory foundation (provable solution).

# Answer
> 5 votes
As for your last question, there is no separate theory for approximation algorithms for problems that are solvable in polynomial time. In fact, it might be that $\mathsf{P}=\mathsf{NP}$. Some examples of approximation algorithms for problems in $\mathsf{P}$ include algorithms for numerical linear algebra and computational geometry. See the question Approximation algorithms for problems in P for more.

---
Tags: approximation, heuristics
---


# Question
Title: A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language
Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program.

But Simply-typed lambda calculus has to stop - so the question is, can anyone show some "useful" program in Turing-complete language (e.g. untyped lambda calculus) that does not go into infinite loop but cannot be written in (simply-)typed lambda calculus?

from comment section:

"Yes I know all of these and I know that they are more expressive and those - but halting problem would only have meaning if there is an algorithm (program) that typed ones cannot express - otherwise, we can write all programs into typed one and see whether it is well-formed, right? Then we automatically know whether a program halts or not. This is what I am asking."

# Answer
> 3 votes
The distinction isn't just about being able to write non-terminating programs. There are significant differences even between normalizing lambda calculi. For example, consider System F. It's normalizing, so all its programs are terminating (so it's not Turing complete), but it has much more expressive power than the simply-typed lambda calculus (it can express any function that can be proved total in second-order Peano arithmetic).

Perhaps the simplest example is Church numerals. In System F Church numerals can be expressed as terms of type $\forall\alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Each natural number $n$ is then represented as $$\Lambda\alpha.\lambda f:(\alpha\to\alpha).\\;\lambda x:\alpha.\\; f^n x$$ where $f^n x \equiv \underbrace{f(f(...f}\_{n\mbox{-times}} (x)...))$. In the untyped lambda calculus it would be just $\lambda fx.f^n x$.

However, we cannot represent Church numerals and operations on them in the simply typed lambda calculus, because it lacks the necessary polymorphism.

Church numerals can be viewed as one of the simplest recursive data structures. In Haskell we could represent them as

```
data Nat = Z | S Nat

foldNat :: Nat -> (r -> r) -> (r -> r)
foldNat Z     f z  = z
foldNat (S n) f z  = f (foldNat n f z)

```

(Observe that `foldNat` actually converts our representation into the System-F representation.)

System F and the untyped lambda calculus allow us to represent any (inductive) recursive data structures such as list, trees etc. in the similar way as we represented Church Numerals (see System F Structures). This is not possible in the simply typed lambda calculus - it can express only non-recursive data structures with bounded size.

A good source of information is Proofs and Types by Jean-Yves Girard, Yves Lafont and Paul Taylor.

---
Tags: complexity-theory, computability, programming-languages, lambda-calculus
---


# Question
Title: Finding the shortest path in a n-dimensional grid
I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at a time. Is there an algorithm for this or at least one I can refer to?

# Answer
> 3 votes
It's easy: first get the 1st dimension right, then the 2nd dimension, then the 3rd dimension, etc.

For example, if you want to get from $(1,3,0)$ to $(3,4,1)$, you go via the following sequence of points: $(1,3,0), (2,3,0), (3,3,0), (3,4,0), (3,4,1)$.

# Answer
> 1 votes
Take a look at Floyd's algorithm. I would also suggest reading up on how to permute co-ordinates to generate Hamiltonian paths through n-dimensional space. Gray codes mutate one bit at a time and are related to the problem you state. As an aside, I don't understand how you can define a point in n-dimensional space with just a pair of co-ordinates, unless n=2.

# Answer
> 0 votes
Its the best you can do. Because its the minimum distance.

Its like driving taxicab in n-dimensional space.

$$d(P,Q) = \sum\limits\_{i = 1}^{n} | P\_i - Q\_i|$$

P and Q are points in n-dimensional space and $P\_i$ is gives $i^{th}$ co-ordinate of P.

It will take time linear in the distance between P and Q which is $d(P,Q)$.

---
Tags: computational-geometry
---


# Question
Title: Are the non-regular languages closed under reverse, union, concatenation, etc?
My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)

# Answer
> 9 votes
Non regular languages are closed under reverse, because $L = (L^R)^R$. Same is true for complement.

Non regular languages are not closed under most other basic operations though. Consider, for example, that $L \cup \overline{L} = \Sigma^\star$. Similarly, if $L = \\{1^{x^2} | x \> 1\\}$ then $\overline{L} \circ \overline{L} = 1^\star$.

There is no complete list of operations on languages, so a complete answer cannot be given.

# Answer
> 0 votes
Well, if $L$ is regular, then $L^{R}$ is also regular. The contra-positive of this is that if $L^{R}$ is non-regular, then $L$ is non-regular...

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


title: Origin of theta-joins

text:
# Question
Title: Origin of theta-joins
I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, *A Relational Model of Data for Large Shared Databanks*, and the concept of $\theta$-joins is nowhere to be found. He does use the symbol $\theta$ in the paper in section 2.2 though, but to refer to something much more general than joins.

In fact, Natural Joins are even defined slightly differently then the definition I'm familiar with. It requires that the original relations be completely recoverable from the joined relation.

So my question is when/in what paper/by who was the modern notion of the $\theta$-join introduced that is often taught by universities?

(A link to Wikipedia's definition of a $\theta$-join, similar to the one I learned in my course)

# Answer
Section 2.3.3 in :

Codd, E.F. (1972). "Relational Completeness of Data Base Sublanguages" is what you need.
> 1 votes

---
Tags: reference-request, history, relational-algebra
---


title: Free and Bound in Lambda Calculus

text:
# Question
Title: Free and Bound in Lambda Calculus
Here's something from Slonneger's "Syntax and Semantics of Programming Languages":

> A variable may occur both bound and free in the same lambda expression: for example, in λx.yλy.yx the first occurrence of y is free and the other two are bound.

I assume the free variable is the y right after the λx. and the bound y's are the λy.y which I can sort of intuitively grasp. So ((λx.yλy.yx)a)b) would reduce to (yλy.ya)b) then to bba ? Can someone explain how this came to be? In the end it's the expression b twice. Can someone perhaps provide more examples of bound and free variables?

# Answer
> 11 votes
I've added brackets to disambiguate $$\lambda x.(\color{red}y (\color{green}{\lambda y}.(\color{blue}yx)))$$ the red $y$ is free and the blue one is bound by the green abstraction. I don't think it makes sense to say that the green $y$ is bound, but it together with the lambda is a binder.

We can beta reduce the term once

$$\begin{array}? && \lambda x.(y (\lambda y.(yx)))ab \\ &\to\_\beta& (y (\lambda y.(ya)))b \end{array}$$

but no further, as there are no remaining redexes left.

---
Tags: lambda-calculus
---


# Question
Title: Mutable Object Values in a Functional Interpreter
I am writing a functional style interpreter for a non-functional programming language that supports both primitive and object values. Primitives are passed by value while objects are passed by reference. I understand how to deal with primitive values but cannot find any good resources on handling mutable object values.

For example, take this ECMAScript inspired language:

```
var a = {'x': 1};
var b = a;
a.x = 3;

print a.x; // outputs 3
print b.x; // outputs 3

```

What is not clear to me is where the object's internal representation should live in the interpreter's non-mutable state. I can store non-mutable values in lexical environment records but I believe I need another level of indirection for storing objects because they are mutable.

I have considered having the interpreter state store a record of active objects, with lexical environments then storing a reference to one of these objects. Such references would need to be resolved dynamically against the current state object.

How has this been addressed in other works?

# Answer
> 2 votes
The basic way of implementing state is to explicitly implement the state monad. In fact, if you want a pure interpreter, you will be forced to do so one way or another. Since you have objects, and very likely recursion on those, you probably cannot get away with a stack, you need a heap (beware of memory leaks).

Thus, your interpreter shall carry around *three* things:

1. The current runtime environment $\eta$, which assigns values to variables, and acts like a stack. When a new variable is declared, you push its initial value onto the runtime environment, and pop it when it goes out of scope.
2. The *current state* $s$, which maps locations to values. Thus a location is a primitive value. Since objects are the only mutable values, a location is the same thing as an object id (but not the object itself!). The state may be implemented in any number of ways, but it has to support `lookup : state -> location -> object` and `update : state -> location -> object -> state`, i.e., updates return the new state.
3. The program $p$ to be evaulated.

Because the run-time environment $\eta$ is like a stack whose discipline reflects the recursive calls of the interpreter to itself, you probably won't have any trouble with it (you called it the "lexical environment"). The main point is that you need to carry around the state *s* explicitly and thread it through the interpreter so that each interpreted command takes in the current state and return the new state. This way a command like

```
a.x = 3;

```

can be interpreted as:

1. In the runtime environment lookup the value of `a`, expect it to be a location `L`.
2. Modify the object at location `L` so that its field `x` is set to `3`.

The second step is done with `update`, i.e., it takes in the current state and returns the new state.

You may wonder why the small-step evaluator should take in the *whole* program `p` and return a *whole* program `p'` yet to be evaluated (as opposed to taking in just one command). This is not strictly necessary (few things are), but it lets you implemented non-local control (exceptions) and loops. For example, to evaluate

```
WHILE B DO C DONE
P

```

we use the fact that this is equivalent to

```
IF B THEN
   (C ; WHILE B DO C DONE)
ELSE
   P

```

So you could evaluate a while loop by converting it to the above conditional statement. There are other, more efficient ways of course, but this is the essential insigth about while loops, i.e., they are a form of recursion.

The interpreter for *boa* in my Programming Languages Zoo is a bit like what you want, but I am cheating because `ObjDict` in type `ob` uses mutable references. However, this is the only place where mutable store is used by the interpreter, see lines 149 to 161 of eval.ml where `Project` dereferences and `Assign` mutates object attributes. Perhaps it is not too hard to change the source to get what you want.

---
Tags: programming-languages
---


# Question
Title: Handwritten character recognition as characters are being traced
I'm looking for an OCR technique (PCA or SVM or anything else) in a peculiar setting. I want to detect the motion of the finger so that if someone writes something in front of the camera in the air, I want to recognize the characters online (meaning as soon as they are written).

# Answer
> 2 votes
There is a paper "Using Mobile Phones to Write in Air". It basically uses the mobile sensors and machine learning to detect words. The Results show that English characters can be identiﬁed with an average accuracy of 91:9%.

There are some open source projects like "hand-gesture-detection" on Google code. I think you can use them as the start for your project.

# Answer
> 1 votes
What you describe is a whole research field, and IMHO a bit out of scope here, but I'll try to provide some pointers anyway.

You should be able to find some review papers on Google scholar that can help you deciding on a technique to use.

Personally I would advise that you divide the task in two: first, detect the path that the finger takes (computer vision), then recognise that path as a character ("handwritten" character recognition).

Now bouncing on the techniques you mention in your question, I want to point out that the choice of the representation and the choice of the features to use is as important (if not more) as the technique itself. Also, PCA is not a classifier, but more of a tool to pre-process your features.

# Answer
> 0 votes
For recognizing hand written letters, you might want to have a look at the detexify website, which is a neat tool for recognizing LaTeX Symbols you write on the screen. On this site, you can also find links to Github with the source code.

---
Tags: machine-learning, computer-vision, pattern-recognition, ocr
---


# Question
Title: Input size of 3-SAT when analyzing complexity
We know that $\text{3-SAT}$ problem is NP-complete, but I am not sure what is meant by size of input. Does this mean number of literals, or number of variables?

# Answer
> 3 votes
At the most basic level, the size of the input is the length of the string that encodes the input given to the Turing Machine - *i.e.* the number of cells it takes up on the tape under the chosen encoding scheme.

In practice though, we often measure the size of the input via proxy measurements. So for problems like 3-SAT, we might choose the number of variables or the number of clauses as a proxy for the size of the input. Another example is for many graph based problem the number of vertices is chosen as a proxy for the size of the input, even though the length of the encoding of a graph may be something more like $O(|V|^{2}\log|V|)$. Note that this is polynomial in $|V|$, so when we are considering polynomial time algorithms or reductions, the polynomial factor between the proxy and the actual size poses no problem.

---
Tags: complexity-theory
---


# Question
Title: The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired
In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated:

> Note that the "CPS" approach has done great harm to performance in SML/NJ. Its physical evaluation model violates too many assumptions that are built into the hardware. If you take big symbolic applications of SML like Isabelle/HOL, SML/NJ with CPS comes out approx. 100 times slower than Poly/ML with its conventional stack.

Can someone explain the reasons for this? (Preferably with some examples) Is there an impedance mismatch here?

# Answer
> 9 votes
At first approximation, there is a difference in "locality" of memory access, when a programm just runs forward on the heap in CPS style, instead of the traditional growing and shrinking of stack. Also note that CPS will always need GC to recover your seemingly local data placed on the heap. These observations alone would have been adequate 10 or 20 years ago, when hardware was much simpler than today.

I am myself neither a hardware nor compiler guru, so as second approximation, here are some concrete reasons for the approx. factor 100 seen in Isabelle/HOL:

* Basic performance loss according to the "first approximation" above.
* SML/NJ heap management and GC has severe problems to scale beyond several tens MB; Isabelle now uses 100-1000 MB routinely, sometimes several GB.
* SML/NJ compilation is very slow -- this might be totally unrelated (note that Isabelle/HOL alternates runtime compilation and running code).
* SML/NJ lacks native multithreading -- not fully unrelated, since CPS was advertized as "roll your own threads in user space without separate stacks".

The correlation of heap and threads is also discussed in the paper by Morriset/Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey" (CiteSeerX) Note: PDF at CiteSeerX is backward, pages from from 10-1 instead of 1-10.

---
Tags: compilers, functional-programming, proof-assistants, continuations
---


# Question
Title: Usage of master theorem for solving recursions
I know that master theorem is used for the recurrence relations of the form:

T(n) = aT(n/b) + f(n)

But in my question, i am supposed to solve the following recurrence relation by using master theorem:

T(n) = 2T(n/7) + 5T(n/8) + n

Can i take f(n)=n and since f(n)=Θ(nlogba), i say T(n) is O(nlogn)? But if i do this, i neglect the fact that the relation must be of the form T(n) = aT(n/b) + f(n). What should i do? Thanks

# Answer
> 5 votes
You may solve this recurrence by using the Akra-Bazzi method, which generalizes the master theorem and allows solving recurrences of the form

$T(n)= \sum\limits\_{i = 1}^k {a\_i T(n/b\_i) + f(n)}$

You need to solve for $p$ the equation

$\sum\limits\_{i = 1}^k {a\_i b\_i^{-p} = 1}$

and the solution to the recurrence can be obtained exactly as in the master theorem, but you must compare $f(n)$ with $n^p$ instead of $n^{\lg\_b a}$.

For your recurrence, $p = 0.954101 \quad$ so that $f(n) = n \quad $ dominates $n^p = n^{0.954101}$ and therefore, $T(n) = O(n) \quad$ (you may want to verify that the master theorem regularity condition also holds).

Akra and Bazzi also proved a more general result.

# Answer
> 3 votes
Well, you can easily get $T(n)=O(n\log n)$, since $2T(n/7)+5T(n/8)\le 7T(n/7)$, and the master theorem gives you that $S(n)=7S(n/7)+n$ is $\Theta(n\log n)$.

The question is, can you do better - that is to prove that $T(n)=\Theta(n)$. I think that if you follow the proof of the master theorem, you will be able to conclude that.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Expressing complexity class P using first-order logic with LFP
Can anyone show how to express complexity class P using first-order logic with LFP? (descriptive complexity)

# Answer
In Neil Immerman's Descriptive Complexity the proof that P = FO + LFP uses alternating graphs: an alternating graph is a directed graph $G= \\{ V, E, A, s, t\\}$ where $A$ is the set of nodes marked as universal ($V \setminus A$ are existential). The accessibility relation is defined in this way:

* $P\_a^G(x,x)$
* if $x \in V \setminus A$ $\land P\_a^G(z,y)$ holds for some edge $(x,z)$ then $P\_a^G(x,y)$
* if $x \in A$ $\land \\; outdeg(x)\>0 \land P\_a^G(z,y)$ holds for all edges $(x,z)$ then $P\_a^G(x,y)$

The reachability problem $REACH\_a$ is defined as $\\{G | P\_a^G(s,t)\\}$ and is complete for P via first-order reductions.

Using LFP one can give a FO + LFP definition of $REACH\_a$ (i.e. $REACH\_a \subseteq FO+LFP$):

$$\varphi\_{as}(P,x,y)\equiv x = y \lor \[\exists z(E(x,z)\land P(z,y)) \land (A(x)\rightarrow \forall z(E(x,z)\rightarrow P(z,y)))\]$$

and $REACH\_a = (LFP\_{P\_{xy}\varphi\_{ap}})(s,t)$

We have $P \subseteq REACH\_a \subseteq FO+LFP$, the inverse $FO+LFP \subseteq P$ follows from the fact that a FO query can be evaluated in $L$ and at most $n^k$ evaluations of $\varphi(R,x\_1,...,x\_k)$ are needed for $(LFP\_{R \varphi})$ ($R$ is a k-ary relation).

For further details you can see the proof on Immerman's book.
> 3 votes

---
Tags: logic, descriptive-complexity
---


title: Fastest mode of data transfer

text:
# Question
Title: Fastest mode of data transfer
Which of the following modes of data transfer is the fastest?

a. DMA

b. Interrupt-based

c. Polling

d. All are equally fast

I do not have the answer, so I cannot check, that's why I am posting here.

I think the answer is D. All are equally fast. In all data transfer cases the speed of data transfer is same, but in case of DMA we save CPU time by that we improve the efficiency of CPU since data transfer job is done by DMA. Is my understanding correct ?

# Answer
First, "fastest" is an ambiguous term--it can refer to latency or throughput/bandwidth.

Second, DMA is orthogonal to interrupts and polling. I.e., the completion of the DMA can trigger an interrupt or be determined by polling an I/O register (or the memory that is being written in some cases). (Explicit processor copying to/from memory is the alternative to DMA.)

Third, the tradeoffs between polling and interrupts will vary depending on the hardware. In general, because an interrupt involves saving and restoring processor state, it has higher latency (saving and restoring state takes time). When I/O events are extremely frequent and of a limited number of types, the overhead of repeatedly reading an limited number of I/O registers will be less than the overhead of context switching. (Obviously, increasing the number of events polled--in terms of unique I/O registers or memory accesses--decreases the relative disadvantage of interrupts.)

With polling, the polling thread is taking up processor resources that could otherwise be used to run other code and the reading of an I/O device register (or ordinary memory location) when the polled event has not happened (the probed value has not changed) uses bandwidth that could otherwise be used for productive purposes. Excessive polling could also reduce the availability of buffers between processors and I/O devices, delaying fast I/O communication behind slow communication (and in some cases the I/O bus is optimized for larger packets so small read responses \[which do not communicate any new information\] would waste bandwidth).

However, hardware can optimize interrupts in several ways. It can coalesce interrupts at the I/O device or at an intermediate point between I/O devices and the processor. At the processor, it is possible to fold interrupts together so that instead of immediately returning from an interrupt (with the overhead of restoring state) a pending interrupt is handled. Some processors also have shadow registers that are used to avoid the need to save and restore state on interrupts. (Software can also combine the use of interrupts and polling by performing some polling while in the interrupt handler. This can reduce the number of interrupts.)

*In theory*, hardware could also reduce the overhead of polling with multithreading and throttling the execution of a polling thread that is not performing useful work. (Even with efficient polling--where every read indicates an I/O has completed--multithreading can allow work to be done while waiting for the read of the I/O device register to be completed--this tends to have relatively high latency.)

In a **very** theoretical sense, I/O device register values could be pushed into cache when they change (a variant on DMA). Such could reduce the wait time for reading such values (helping both interrupt handlers and polling) and facilitate hardware thread throttling (because the processor could quickly determine that no change had occurred). However, such is incompatible with how most ISAs are defined and with how I/O devices are implemented, and such would **greatly** increase the complexity of the system.
> 4 votes

---
Tags: computer-architecture
---


# Question
Title: Find the point with minimum max distance to any point in a set
Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?

# Answer
> 7 votes
This is the smallest enclosing circle problem, and can be solved in linear time. Also, these slides describe a randomized algorithm that runs in expected linear time.

---
Tags: computational-geometry
---


title: Are these two languages regular?

text:
# Question
Title: Are these two languages regular?
Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c & a \end{array}$

Is $L=\\{xy \mid |x|=|y| \land \operatorname{value}(x) = \operatorname{value}(y)\\}$ regular?

Is $L=\\{xy \mid \operatorname{value}(x)= \operatorname{value}(y)\\}$ regular?

# Answer
Hint for (1): consider a different type of value, $\mathrm{value}(s) = 1$ if $s$ ends with $z$, and $\mathrm{value}(s) = 0$ otherwise. Define the language $L$ as in your case, and consider $L \cap x^\* z y^\* z$.

Hint for (2): consider the language $L\_\alpha = \\{xy : \mathrm{value}(x) = \mathrm{value}(y) = \alpha \\}$. What is the relation between $L\_\alpha$ and $M\_\alpha = \\{ x : \mathrm{value}(x) = \alpha \\}$? Is $M\_\alpha$ regular?
> 6 votes

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


# Question
Title: Why do some inference engines need human assistance while others don't?
*I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.*

Why is it that automated theorem provers, i.e. ACL2, and SMT solvers do not need human assistance while proof assistants, i.e. Isabelle and Coq, do?

*Find the series' next question here.*

# Answer
Validity of higher order formulae is in general not decidable and search spaces are *huge*, so all you can hope to do is to *try* to find a proof -- assuming it exists -- by cleverly enumerating the proof space (think sledgehammer, aptly named) but that is rough. Humans can play the oracle, providing the key lemmata to guide proof.

Automated provers, on the other hand, typically deal only with decidable (subsets of) logics, for instance propositional logic or subclasses of first-order logic, so they may run a long time but you know they are going to be successful eventually.

Note that there are approaches to enable proof assisstants to find those important lemmata, e.g. IsaPlanner. The tool guesses (inductive) lemmata by enumeration and random testing and then tries to prove them. By iterating the process, many lemmata of e.g. typical data type definitions can be found automatically.

---

*Small ABC*

* *validity* -- a formula is valid it holds whatever you assign to the free variables.
* *free variables* -- those variables that are not bound by quantifiers such as $\forall$ and $\exists$
* *decidability* -- a (boolean) property is (Turing) decidable if there is an algorithm that answers "yes" or "no" (correctly) after a finite amount of time.
* *propositional logic* -- also *zero order logic*; no quantification allowed.
* *first order logic* -- quantification is only allowed over individuals, i.e. you can do $\forall x. P(x)$ but not $\forall f. f(4) \> 0$.
* *higher order logic* -- you may quantify over (and "build") arbitrarily complex objects, e.g. higher order functions (functions that take functions).
> 14 votes

# Answer
I would say that the classic distinction of "automated theorem proving" (ATP) vs. "interactive theorem proving" (ITP) needs to be reconsidered. If you take a well-known ITP system like Isabelle/HOL today (Isabelle2013 from February 2013), it integrates quite a lot of add-on tools from the ATP portfolio:

* On-board generic automated proof tools: old-school Isabelle tools like `fast` and `blast` (by L. Paulson) and newer automated provers like `metis` (by J. Hurd).
* External ATPs for First-Order Logic that are invoked via Sledgehammer: E prover, SPASS, Vampire. The proof that is found is analyzed to figure out which lemmas have contributed to it, reducing 10000s to 10s, and feeding the result to `metis`.
* External SMTs with partial proof reconstruction, notably for Z3 (by S. Boehme).
* Tools to find counter examples of unproven statements: Nitpick/Kodkodi (J. Blanchette) and Quickcheck (L. Bulwahn).

Does all that automated stuff make Isabelle an automated theorem prover?

Ultimately, I think the distinction of "ATP" vs. "ITP" is just some kind of "label" that tells how you want to position or "sell" your system: ATPs claim to be "push-button tools", but in practice you will have to interact (indirectly), by providing parameters or hints, or reformulating your problem. That might actually be quite challenging, due to the long runtimes that are common-place in the ATP community.

In contrast, an ITP system is made for people waiting on the spot, with half-decent access to internal proof states, to see what's missing to finish a proof. An ITP system that wraps up ATP tools in the manner of Isabelle might turn out more appealing for more users and more applications, than either ITP or ATP alone.
> 7 votes

---
Tags: logic, proof-assistants, automated-theorem-proving, smt-solvers
---


# Question
Title: Show complement of language in same complexity class?
If $L$ is a binary language ($\Sigma = (0, 1)^\*$) and $\overline{L}$ is the complement of $L$, the set of binary strings not in $L$.

How can I show that, if $L$ is in the complexity class $P$, then so is $\overline{L}$?

# Answer
Deciding $L$ means you have a way to answer "YES" or "NO" on each input.

$\bar L$ is the complement language of $L$: if some input is in $L$, then it is not in $\bar L$ (and vice versa)..

Thus, deciding $L$ and deciding $\bar L$ are equivalent up to the final answer. If an algorithm to decide one of them takes $x$ time, the similar algorithm (up to the final state) for the other language will take... the same time.
> 2 votes

# Answer
Hint: Given a polynomial time algorithm for $L$, come up with a polynomial time algorithm for $\overline{L}$.
> 2 votes

---
Tags: complexity-classes, formal-languages
---


# Question
Title: How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$?
If $L$ is a binary language (that is, $L \subseteq \Sigma = \\{0,1\\}^∗$) and $\overline{L}$ is the complement of $L$:

How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as well?

# Answer
Suppose you have an algorithm that decides membership in $L$ in polynomial time (by assumption since it's in $P$). You can easily write an algorithm that uses the previous one for deciding membership in $\bar L$ and prove that it takes polynomial time.
> 2 votes

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


# Question
Title: Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar
How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar

Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$

# Answer
I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$.

A grammar $G$ is strong $LL(k)$ *iff* for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have:

$$ First\_k( \alpha \\; Follow\_k(A) ) \\; \cap \\; First\_k( \beta \\; Follow\_k(A) ) = \emptyset $$

The steps to obtain a $k$ for a certain grammar $G$ are thus as follows:

* For each $n \> 0$:
    1. Check wether $G$ is $LL(n)$
    2. If so, try proving $G$ is $LL(n)$
    3. If not, we have found our $k = n - 1$

Some documents that might help with the actual proof:
> 2 votes

---
Tags: context-free, formal-grammars, parsers, ll-k
---


# Question
Title: Test if there are two subsets which cover a set
Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?

# Answer
There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to $$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$ Indeed, if $\chi\_U$ is the indicator vector of $U$ then $$ \chi'\_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi\_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$ The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\\{0,1\\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h\_U = g\_{\overline{U}}$. The FFT algorithm uses the basic operation $h\_{U \cup \\{i\\}} = h\_U \lor h\_{U \cup \\{i\\}}$. This makes it clear why $\bigvee\_U f\_U g\_U = \bigvee\_U f\_U h\_{\overline{U}}$ is what we want.
> 3 votes

# Answer
A solution to this problem is the two subsets $U$ and $V$ from $\mathcal{X}$. If we know $U$ upfront, we can answer this question in $O(n\*m)$.

So let us examine the case where we would have a unique $U$, this happens when there is an element $a \in S$ is covered only by $U$. We can check this possibility in $O(n\*m)$.

Afterwards, we can find $V$ through brute force in $O(n\*m)$. If we don't have this possibility, I am not sure whether we can solve it more efficiently.
> -2 votes

---
Tags: algorithms, data-structures, sets
---


title: Context free grammar for $1^k0^{2k}$

text:
# Question
Title: Context free grammar for $1^k0^{2k}$
I need a hint for writing a context-free grammar for the language $L=\\{1^k0^{2k}:k\in \mathbb N\\}$. I'm starting to doubt that it can be done for general $k$.

# Answer
Based on the comments:

$$S \to 1S00 \mid 100$$
> 4 votes

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


# Question
Title: Proving closure under reversal of languages accepted by min-heap automata
*This is a follow-up question of this one.*

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

> Is HAL closed under reversal?

# Answer
> 4 votes
Consider the language $$L\_{\times 2} = \big\\{ x\bot y\bot z \mid x,y,z\in \\{0,1\\}, \\#\_0(x)=\\#\_0(y) \text{ and } |x|+|y|=z\big \\}$$ (where $\\#\_0(x)$ denotes the number of zeros in $x$).

It is easy to decide $L\_{\times 2}$ using a HAL machine — observe that the machine needs to keep track of two properties: the number of zeros in $x$ vs $y$ and the length of $x,y$ (vs $z$). It can push a `0` into the heap for every zero it sees in $x$ (and then later pop `0` for any zero seen in $y$); additionally it pushes `1` for any bit in $x,y$ (and later pops `1` for any bit of $z$). Since all the `1`s are pushed down the heap, they don't interfere with the `0` count. The $\bot$ serves as a delimiter, and can be practically ignored.

Now, let $L = L\_{\times 2}^R$, be the reverse language. That is, $$ L = \big\\{z\bot y \bot x \mid x,y,z\in \\{0,1\\}, \\#\_0(x)=\\#\_0(y) \text{ and } |x|+|y|=z\big \\}$$ We will show that no HAL machine can decide $L$.

The intuition is the following. As above, the machine must keep track of both the length of $z$ and the number of zeros in $x,y$. However, in this case it need to track them *simultaneously*. This cannot be done via a heap. In more details, after reading $z$, the heap contains information about the length of $|x|+|y|$. while reading $y$ the machine must also keep in the heap the number of zeros in $y$. However, this information cannot interfere with the information the heap already has on the length we expect $x$ to be. Very intuitively, either the information about the number of zeros will be "below" the information about the length of $x$, and then we cannot access it while reading $x$, or it is "above" that information, rendering the latter inaccessible, or the two information will be "mixed" and become meaningless.

More formally, we are going use some kind of a "pumping" argument. That is, we will take a very long input, and show that the "state" of the machine must repeat itself during processing that input, which will allow us to "replace" the input once the machine repeats its "state".

For the formal proof, we require a simplification of the structure of the HAL machine, namely, that it doesn't contain a "loop" of $\varepsilon$-transitions$^1$. With this assumption we can see that for every input symbol the machine processes, the content of the heap can increase/decrease by at most $c$ (for some large enough constant $c$).

*Proof.*
Assume $H$ decides $L$, and consider a long enough input (say, of length $4n$, thus $|x|=|y|=n$, $|z|=2n$, ignoring the $\bot$s hereinafter). To be concrete, fix $z,y$ and assume that $\\#\_0(y) = n/2$. Observe that there are ${n \choose n/2}$ different $x$'s such that $z\bot y \bot x \in L$.

Consider the heap's content immediately after processing $z\bot y$. It contains at most $3nc$ symbols (where each symbol is from a fixed alphabet $\Gamma$), by our assumption. However, there are ${n \choose n/2}$ different $x's$ that should be accepted (which is substantially larger than the amount of possible different contents for the heap, as this increases exponentially, while the different number of heaps increases polynomially, see below). Take two inputs $x\_1,x\_2$ that should be accepted, so that the following holds:

1. The prefix of length $n/2$ of $x\_1$ has different number of zeros than the prefix of $x\_2$ of the same length.
2. By the time the machine reads a prefix of length $n/2$ of the $x$ part, the heap looks the same for both $x\_1$ and $x\_2$, and also, the machine is in the same state (this must happen for some $x\_1,x\_2$, for large enough $n$, as there are more than $2^{0.8n}$ different options$^2$ for $x\_1,x\_2$, and at most $(3.5cn)^{|\Gamma|}|Q|$ different options for heap content and state$^3$).

It is clear that the machine must accept the word $z\bot y \bot x\_1^px\_2^s$, where $x\_1^p$ is a prefix of $x$ of length $n/2$ and $x\_2^s$ is a suffix of $x\_2$ of the same length. Note that the number of zeros in $x\_1^px\_2^s$ differs from the number of zeros in $x\_1$ and $x\_2$ (that is, from $\\#\_0(y)$), due to the way we chose $x\_1$ and $x\_2$, thus we reached a contradiction.

$^1$  Does this assumption damages generality? I don't think so, but this indeed requires a proof. If someone sees how to get around this extra assumption, I'd love to know.
$^2$  Let's fix $x\_1$ so that it's prefix (of length $n/2$ has exactly $n/4$ zeros). Recall that using Stirling's approximation we know that $\log {n \choose k} \approx nH(k/n)$ where $H()$ is the Binary entropy funciton. Since $H(1/4) \approx 0.81$ we have ${n \choose n/4} \> 2^{0.8n}$ for large enough $n$.
$^3$  Assuming alphabet $\Gamma$, there are $|\Gamma|^n$ different strings of length $n$, so if this was a stack we were screwed. However, pushing "01" into a heap is equivalent to pushing "10" - the heap stores only the sorted version of the content. The number of different *sorted* strings of size $n$ is ${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$, for a constant $|\Gamma|$.

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


# Question
Title: Why is $n \log \log n$ not tightly bounded by $n$?
I don't understand why $n \log \log n $ is not $\Theta (n)$.

Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n \log \log n \geq Cn$?

# Answer
> 10 votes
As $n$ grows bigger, the ratio between $n\log\log n$ and $n$, namely $\log\log n$, tends to infinity. Hence it is not possible to upper bound $n\log\log n \leq Cn$ for any constant $C$. If you stare at this inequality, you discover that the constant $C$ must satisfy $\log\log n \leq C$ for all $n$, yet the function $\log\log n$ is not bounded.

# Answer
> 4 votes
You could not narrow $f(x) = x\log \log x$ with $ g = n $, because inequalities that must be met for this, never occur. Remember that the logarithm function is always increasing. So, If We had it, $f$ should perform the next inequalite for some constants $c$ and $C$. $$ cn\leq f \leq Cn$$

Let's see that, for example a right side of these inequalities and see the contradiction.

$$ \begin{align} x\log \log x \leq cx\\ e^{x\log \log x }\leq e^{cx}\\ e^x\log x \leq e^{cx}\\ \log x \leq e^c \end{align} $$ So, you are saying that $\log x \leq k$, for any $x\in R$, that's not true.

# Answer
> 3 votes
Simply, because $\log\log n$ is **not** a constant! actually, $$\lim\_{n\to \infty} \log\log n = \infty$$

while for some function to be $\Theta(n)$ it is required that it is bounded by $cn$ for some **constant** $c$.

**tl;dr** you didn't look at large enough $n$'s. try $n$ = Graham's number.

---
Tags: terminology, asymptotics
---


title: Function that spreads input

text:
# Question
Title: Function that spreads input
I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:

* $f$ should be bijective
* Both $f$ and $f^{-1}$ should be calculable pretty fast
* $f$ should return a number that has no significant correlation to its input.

The rationale is this:

I want to write a program that operates on data. Some information of the data is stored in a binary search tree where the search key is a symbol of an alphabet. With time, I add further symbols to the alphabet. New symbols simply get the next free number available. Hence, the tree will always have a small bias to smaller keys which causes more rebalancing than I think should be needed.

My idea is to mangle the symbol numbers with $f$ such that they are widely spread over the whole range of $\[0,2^{64}-1\]$. Since the symbol numbers only matter during input and output which happens only once, applying such a function should not be too expensive.

I thought about one iteration of the Xorshift random number generator, but I don't really know a way to undo it, although it should theoretically be possible.

Does anybody know such a function?
Is this a good idea?

# Answer
You can use *Fibonacci hashing*, namely

$\qquad h\_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$.

For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $\[0,1\]$. By scaling to $\[1..M\]$ and rounding (down), you get about evenly spread numbers in that interval.

For example, these are $h\_F(1), \dots, h\_F(200)$ scaled to $\[0..10000\]$ (left original sequence, right sorted):

This is an instance of what Knuth calls *multiplicative hashing*. For $w$ the computer's word size, $A$ some integer relatively prime to $w$ and $M$ the number of addresses needed, we use

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

as hashing function. The above follows with $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ (make sure you can compute it with a sufficient precision). While this also works with any other irrational number besides $\phi^{-1}$, it is one of only two numbers that lead to the "most uniformly distributed" numbers.

Find more in The Art of Computer Programming, Volume 3 by Donald Knuth (chapter 6.4 from page 513 in the second edition). In particular you'll find why the resulting numbers are pairwise distinct (at least if $n \ll M$) and how to compute the inverse function if you use natural $A$ and $w$ instead of $\phi^{-1}$.
> 6 votes

# Answer
For $k$-bit inputs, this function works:

$\mathrm{hash}(n) = (n \bmod 2^{\lceil\frac{k}{2}\rceil})\cdot 2^{\lceil\frac{k}{2}\rceil} + n \\,\mathrm{div}\\, 2^{\lceil\frac{k}{2}\rceil}$

This is reversible, in that $\mathrm{hash}(\mathrm{hash}(n)) = n$, and has non-sequential pairs $\\{n,m\\}, n \< m$, where $\mathrm{hash}(m) \< \mathrm{hash}(n)$. Beware that output and input may correlate, especially if your input is in $\\{1,\dots,2^{\lceil\frac{k}{2}\rceil}-1\\}$.

Ref: Reversible hash function
> 1 votes

---
Tags: binary-trees, hash, binary-arithmetic
---


title: What is the Meaning of the Notation

text:
# Question
Title: What is the Meaning of the Notation
What is meant by saying an algorithm runs in time $Poly(|S|,n,\frac{1}{\epsilon})$.

Can somebody explain with an example.

# Answer
It means that there exists a polynomial $f(x,y,z)$ such that the algorithm runs in time $f(|S|,n,\frac{1}{\epsilon})$.

Specifically, it means that there are constants $c\_1,c\_2,c\_3\ge 0$ such that the algorithm runs in time $O(|S|^{c\_1}\cdot n^{c\_2}\cdot (\frac{1}{\epsilon})^{c\_3})$.
> 5 votes

---
Tags: complexity-theory, machine-learning
---


# Question
Title: Why does PCP theorem imply that NP problems are hard to approximate?
What I only got currently from PCP theorem is that it needs at most $O(\log n)$ randomness and $O(1)$ query of proof to approximate. So how does this result relate to the fact that solution to NP problems are hard to approximate?

# Answer
> 4 votes
Take as an example SAT. The PCP theorem (in one formulation) shows that there is a PCP for SAT which uses $O(\log n)$ bits of randomness, queries $O(1)$ places, always accepts on YES instances, and rejects on NO instances with probability at least $\alpha \> 0$. The PCP queries at most $2^{O(\log n)} = n^{O(1)}$ different locations in the proof, so the entire proof can be encoded in polynomial size. For each of the $2^{O(\log n)}$ possible queries, we can write a formula of constant size that is true if and only if the verifier accepts. Taking all these formulas together in CNF form, we get a CNF $\psi$ (which depends on the instance of SAT) on polynomially many variables (representing the bits of the proof) with polynomially many clauses (each possible query gives rise to $O(1)$ many clauses).

By the definition of PCP, for each $\phi \in \mathrm{SAT}$, there is a proof that satisfies the verifier on *all* possible queries. In other words, $\psi$ is satisfiable. On the other hand, for each $\phi \notin \mathrm{SAT}$, every proof is rejected with probability at least $\alpha$. This means that any assignment satisfies at most $1-\alpha/O(1)$ of the clauses of $\psi$, the $O(1)$ factor coming from the fact that the result of each query is encoded using $O(1)$ different clauses, one of which must be falsified if the query leads to rejection by the verifier.

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


# Question
Title: $1+\epsilon$ approximation for inapproximable problems
I am currently confused by the following situation:

1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can approximated within $1+\epsilon$ in time $O(k^{O(k/ \epsilon)})$

Did I just win a million dollars or why isn't this a contradiction? I guess my confusion comes from the unprecise statement "in polynomial time" in 1).

# Answer
> 11 votes
The first sentence says there is no approximation algorithm with $2-\epsilon$ for k-center, which means $k$ is part of an input, because there is no limitation on $k$, so $k$ can be arbitrary large (as $n$). This is common mistake in the context of approximation algorithms and parametrized complexity, this doesn't mean the algorithm runs in polynomial time, this says if you "fix" some parameters (e.g here k) you can have polynomial time algorithm, exactly like what you mentioned, mentioned algorithm is polynomial in $n$ but not in $k$, and when $k$ is not fix and is part of input, the algorithm is not polynomial. You can read more detail on fix parameter tractability in reference question.

---
Tags: complexity-theory, np-complete, approximation, p-vs-np, parameterized-complexity
---


# Question
Title: How to find the maximum independent set of a directed graph?
I'm trying to solve this problem.

> **Problem**: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$.

I have to find the Maximum independent set and the size of this set. The size can be found by König's theorem. But how can I find the Maximum Independent Set (i.e. which vertex are part of the set).

I did some search also and found something here:

`If removing a vertex does not change minimum path cover then I can get the desired result without that vertex.`

But I don't understand the underlying theorem. Any help will be greatly helpful.

# Answer
You are trying to find the *width* of the poset defined by the given subset of integers and the divisibility relation. The *width* is the maximum number of anti-chains, which is the same as the maximum set of incomparable elements in the poset.

This corresponds exactly to the maximum independent set in the Comparability Graph, where each integer is a vertex and there is an edge from $u$ to $v$ if and only if $u$ divides $v$.

Finding the maximum independent set in general is a hard problem, but comparability graphs are a special case for which efficient algorithms exist.

Dilworth's Theorem characterizes the width of any poset as a partition of the poset into *chains* (source to sink paths in the directed comparability graph). Dilworth's Theorem is equivalent toKönig's theorem on Bipartite Matching, which, as you suggested, leads to an algorithm. The bipartite graph you construct in order to use Konig's theorem and find the maximum independent set via a bipartite matching is described simply in the above Wikipedia link. For completeness, we include it here (in annotated form):

"Define a bipartite graph $G = (U,V,E)$ where $U = V = S$ \[the set of integers\] and where (u,v) is an edge in $G$ when $u \< v \in S$ \[integer $u$ divides integer $v$\]. By König's theorem, there exists a matching $M$ in $G$, and a set of vertices $C$ in $G$, such that each edge in the graph contains at least one vertex in $C$ and such that $M$ and $C$ have the same cardinality $m$.

"Let $A$ be the set of elements of S that do not correspond to any vertex in $C$; then $A$ has at least $n - m$ elements (possibly more if $C$ contains vertices corresponding to the same element on both sides of the bipartition). Let $P$ be a family of chains formed by including $x$ and $y$ in the same chain whenever there is an edge $(x,y)$ in M$; then $P$ has $n - m$ chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality."

The set of distinct vertex labels (integers) in $A$ is the answer to your question.

Section 3 of the paper Online Algorithms for Dilworth's Chain Partition by Ikiz and Garg describes two different offline algorithms to compute the chain partition, and thus the independent set you are looking for. One of the algorithms is based on the Bipartite matching method.
> 6 votes

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


# Question
Title: Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other tags would be more appropriate.

I am trying to solve this problem for which I need to compute the number of Hamiltonian cycles $C(n)$ in the $n$th order Sierpinski-graph $S\_n$. (Please also see the above link for the definition and pictures of Sierpinski-graphs)

I have found $C(n)$, but I must have messed up something, because my solution does not match the given value $C(5) = 71328803586048$. My argumentation consists of very basic thoughts, and I cannot find the mistake. Any help is greatly appreciated. Even if it seems lengthy, the thoughts become trivial if you look at the graphs while following.

**(a)** In a given graph $S\_n$ call the outer corners $A,B,C$. Then I define the following quantities:

$N(n) := $ the number of Hamiltonian paths from $A$ to $C$.

$\bar{N}(n) := $ the number of paths from $A$ to $C$ which visit each node once except $B$.

I will also call such paths $N$- or $\bar{N}$-type paths in the following.

**(b)** It is easy to see that $N(n)=\bar{N}(n)$.

The reason is the following: Consider a $N$-type path. Starting at $A$ this path is of the form $(A,...,X\_1,B,X\_2,...,C)$. By replacing the segment $(X\_1,B,X\_2)$ by $(X\_1,X\_2)$ we obtain a $\bar{N}$-type path. This operation uniquely maps all $N$-type paths to $\bar{N}$-type paths.

**(c)** We derive the recursion $N(n+1)=2N(n)^3$.

Consider an $N$-type path from $A$ to $B$ and denote the subtriangles at the outer corners $A,B,C$ by $T\_A,T\_B,T\_C$, respectively. It is clear that the $N$-type path will visit each subtriangle exactly once starting from $T\_A$ over $T\_B$ to $T\_C$. Now consider the node $Z$ at which the subtriangles $T\_A$ and $T\_C$ touch. There are two possibilities, when this point is visited by the path, either **(i)** before leaving $T\_A$ or **(ii)** after entering $T\_C$. In these cases the three subpaths inside $T\_A,T\_B,T\_C$ are of the types **(i)** $N,N,\bar{N}$ or **(ii)** $\bar{N},N,N$, respectively. With this in mind we can count

$N(n+1)=N(n)N(n)\bar{N}(n)+\bar{N}(n)N(n)N(n)$ and with **(b)** we arrive at the upper recursion.

**(d)** We solve the recursion **(c)** with $N(1)=1$ and obtain $N(n)=2^{3^0+3^1+...+3^{n-2}}$.

**(e)** Consider a Hamiltonian cycle in the graph $S\_n$. As each of three subtriangles is connected to the others via two nodes only, it is clear that the cycle will enter each subtriangle exactly once via one connecting node, then "fill" it, an finally leave it via the other connecting node. Hence the Hamiltonian cycle in $S\_n$ consists of three $N$-type subpaths in the subtriangles which all have the structure of $S\_{n-1}$. We can conclude for the number of Hamiltonian cycles

$C(n) = N(n-1)^3$.

However it follows for $n=5$

$C(5) = N(4)^3 = 8192^3=549755813888 \neq 71328803586048$

where the latter should be obtained according to the problem page (link above).

Thanks again for any help or comments.

# Answer
Nice idea! The problem seems to be in step $(b)$. Replacing $(X\_1,B,X\_2)$ in an $N$-path by $(X\_1,X\_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X\_1,X\_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$.

Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.
> 11 votes

---
Tags: graphs, combinatorics, check-my-proof
---


# Question
Title: Maximum variance and useful information of dataset
I am reading through PCA and it says that the maximum variance principal component has most of the information. Can we apply that to any data set? If a data set has n attributes and most of the attributes show high variance then can we infer that the dataset has captured lot of useful information?

I am trying to understand how a high variance dataset contains useful information?

# Answer
I'll answer this, even thought the question is not well defined and would possibly be better suited for cross validated. But since it has some connection to information it's not totally off topic here.

Short version: **Now, we can't apply that to any data set**. Variance alone is not a good measure of information. PCA chooses the components with the highest eigenvalue, because they explain the input variance (i.e. euclidean distance from the origin). That's why you should normalize your input, if you don't want to emphasize a certain input component.

---

Long version:

Let's say you have two random variables $X$ and $Y:=10X$ where $E(X)=E(Y)=0$, $\mathrm{Var}(X)=1$ and thus $\mathrm{Var}(Y) = 100$. Now assume a third variable $K$ uniformly distributed among $\\{1,\dots,k\\}$ (this models drawing a random individual form your sample).

The variance before the PCA is not a sufficient measure for information, e.g. if we use $X$ and $Y$ to distinguish the individuals: $$P(K=k|X=x) = P(K=k|Y=10x)$$

The covariance matrix looks like this: $$\left(\matrix{1&10\\10 & 100}\right)$$

Using R's "eigen" we get:

```
$values
[1] 101   0

$vectors
           [,1]        [,2]
[1,] 0.09950372 -0.99503719
[2,] 0.99503719  0.09950372

```

If we now transform $X$ and $Y$ to $X'=M\_{11}\cdot X + M\_{21}\cdot Y$ and $Y'=M\_{12}\cdot X + M\_{22}\cdot Y$ (where $M$ is "vectors" from $R$), $X'$ contains "all the information": $$\forall y\\;:P(K=k|X'=x) \neq P(K=k|Y'=y)=P(K=k)$$

But, of course, again $X''=10^{-100}\cdot X'$ contains "the same information".
> 1 votes

---
Tags: terminology, data-mining, data-sets, statistics
---


# Question
Title: What can be learned from the weights in a neural network?
I'm very new to neural networks, and have been trying to figure some things out. So, let's say you come across a neural network which has 100 inputs, a hidden layer with 200 nodes, and 32 outputs. Let's also say that you, the "discoverer" of this particular instance of a neural network, are able to read the weights of the individual neurons. What could you figure out about it's function?

1) Are you able to determine what the algorithm or logic is contained within the neural network? Other than feeding in all possible inputs and studying the outputs it produces.

2) If you were given information about the connection of the neural network (maybe the network isn't fully connected), would solving question one above be easier?

# Answer
It depends. Weights of neural networks can be graphed or visualized for some insight. This is especially useful if the neural network works with visual processing. It is possible to "derive" what low-level inputs to the neural network create particular neurons in higher levels to "fire" by working backwards through the neural network weights— in other words, the problem of finding/deriving the low-level input patterns that maximally excite particular neurons, and graphing the results. A great example of this is the recent breakthrough result by Google in a self-trained visual network that self-organized to find higher-level patterns like cats and human faces, etc. \[1\],\[2\],\[3\]

This is also known as "feature detection" and there is Nobel-prize winning research (1981 Hubel/Weisel) that demonstrates that real brain neurons function in a similar way, to varying degrees. Active research is ongoing/continuing in this area in both biological and artificial systems.

Another way of analyzing neural net weights is to conclude what factors (inputs) affect the neural network and which don't. For example, suppose the neural net is used to predict stock prices and it has various inputs relating to different economic variables such as say GDP, gold prices, DJIA (an index), and interest rates. After the network is trained (successfully!) to predict something (say future prices), one can determine how much effect each one of the input variables has on the final prediction.

Also a determination can be made of basic negative or positive correlation between input and output. In this way neural networks can be used in a manner very similar to statistical techniques like factor analysis.

So the answer is "yes absolutely," but only in the sense that there are different ways to reveal "algorithms" in neural networks via graphical or other "human-readable" representations other than with the typical representation of algorithms, i.e. code. But representing neural network weights in a human-readable way and finding new useful representations is an active area of research.

\[1\] Google Puts Its Virtual Brain Technology to Work Technology Review

\[2\] Google’s Artificial Brain Learns to Find Cat Videos Wired

\[3\] How Many Computers to Identify a Cat? 16,000 NYT
> 7 votes

# Answer
> Are you able to determine what the algorithm or logic is contained within the neural network? Other than feeding in all possible inputs and studying the outputs it produces.

No, I don't think so, not in a meaningful way. That would be akin to studying the bits in each individual byte of a computer program in an effort to evaluate its purpose. You need *meaning* to determine that, and you can only get that by studying the inputs and outputs, or evaluating actual opcodes.

There's no meaning in individual neuron weights; it's only when those weights are combined into an answer that they become meaningful.

You could probably ascertain the *training method* of the neural net by observing its overall structure and the pattern of relative weights in the neuronal structure.
> 6 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Subtracting a two's complement value from another two's complement value
I'm trying to solve the following problem:

$$ 6AD3 - AF20 $$

Both of these are hex values in two's complement.

I keep getting one answer but it's turning out worng. What I tried to do, was take the complement of AF20, which I got as 50D1, and instead of subtracting, I added it to 6AD3, and I got BBA4, however, I am being told this is the wrong answer.

Where am I going wrong?

# Answer
Converting 6AD3 to binary gives 0110 1010 1101 0011 (the division to 4's is just to make it readable)

Converting AF20 to binary gives 1010 1111 0010 0000 To complement the latter in two's complement, we take the bitwise negation (one's complement) and add 1.

So the one's complement is 0101 0000 1101 1111, and adding 1 gives us 0101 0000 1110 0000 Adding this to 0110 1010 1101 0011 we have:

0101 0000 1110 0000

+

0110 1010 1101 0011

=

1011 1011 1011 0011

Which is BBB3.
> 2 votes

---
Tags: binary-arithmetic
---


# Question
Title: Asymptotics of a function that decreases as n increases
A homework assignment asks me to state the complexity in Big-O notation of the function $$f(n) = 7n – 3n \log n + 100000 $$

I graphed this function and decreases all the way down to zero nearly its entire lifespan. Therefore I concluded that the complexity is bounded by a constant and has the complexity $O(1)$.

Is this correct?

Also out of curiosity, what is the Big-Omega of this function is? The best it could ever run is also O(1). What about Big-Theta? I'm having trouble getting my head around these.

# Answer
If you use suitable definitions, you'll find that your function is in

* $O(2^n)$,
* $O(n^4)$,
* $o(1)$ and
* $\Omega(-n^2)$,

among many others. It's likely that the question (implicitly) asks for sharper bounds; I'll leave that for you to figure out.
> 1 votes

---
Tags: asymptotics
---


title: min-cut with extra condition

text:
# Question
Title: min-cut with extra condition
I have a undirected graph with no edge costs. A subset of the nodes are labeled $c\_1, c\_2, ..., c\_k$ and one node is labeled $K$. I want to find the minimum cut of the graph with the extra condition that all nodes $c\_i$ are in the same half of the cut and the node K is in the other cut.

My idea was to begin by doing a BFS from $K$ to all nodes $c\_i$, saving predecessors and then finding all paths from $K$ to a node $c\_i$ and finally picking the minimum set of edges from the paths so that at least one edge from each path was chosen. Unfortunately, if I understand this correctly, this is equivalent to the NP-complete set cover problem.

Is there anything sane with this approach? Do you have any hints to push me in the right direction?

Note: this is homework so I'd rather have some hints than a full solution.

# Answer
We'll use the **max-flow min-cut theorem** to solve this.

Therefore we map each instance $(G,K,\\{c\_{1},\dots,c\_{k}\\})$ to the network $N:=(V(G) \stackrel{.}{\cup} \\{C\\},E(N),e,K,C)$, where $C$ is a new vertex not in $V(G)$ (our sink), $K$ is our source and $e$ denotes the edge capacities,

$$E(N) := \\{(u,v)|\\{u,v\\}\in E(G)\\} \cup \\{(c\_i,C)|i\in\\{1,\dots,k\\}\\}$$ and $$e((u,v)) := \begin{cases}2|E(G)|+1&v=C\\1&\text{else} \end{cases}\qquad.$$

Then $(V\_1,V\_2)$ is a minimum $K$-$C$-cut in $N$ if and only if $(V\_1,V\_2\setminus\\{C\\})$ is minimum cut in $G$ subject to the condition that $K\in V\_1,\forall i: \\, c\_i\in V\_2$:

"$\Rightarrow$": Every $K$-$C$-cut with the property $\forall i: \\, c\_i\in V\_2$ has a capacity of at most $2E(G)$, every cut with $\exists i: \\, c\_i\in V\_1$ has capacity of at least $2E(G)+1$. Therefore only those having the desired property can be a minimum cut. Since for each $(u,v), u\in V\_1, v \in V\_2$ of a minimum cut the edge capacity is $1$, $\mathrm{cap}(V\_1,V\_2)=||\\{\\{u,v\\}\in E(G)|u\in V\_1,v\in V\_2\\}||$.

"$\Leftarrow$": analogous to second part of "$\Rightarrow$".

If we have computed a maximum flow $f$ by e.g. the Edmonds–Karp algorithm, we compute the residual Network $N\_f$ where $e(N\_f)=e-f$ and $E(N\_f)=E(N)\setminus\\{(u,v)|f((u,v))=1\\}$, i.e. we remove the edges used by the maximum flow. Let $V\_1$ be the set of vertices reachable from $K$ in $N\_f$ and $V\_2=V(G)\setminus V\_1$. Then $(V\_1,V\_2\cup\\{C\\})$ is a minimum cut in $N$ and thus $(V\_1.V\_2)$ is a minimum cut in $G$ separating $K$ and $\\{c\_1,\dots,c\_k\\}$.
> 3 votes

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