title: Box and triangle intersection

text:
# Question
Title: Box and triangle intersection
I am looking for geometry algorithm.

I have an axis-aligned box $B$ and a triangle $T$ in 3D space. I want to compute an axis-aligned bounding box of their intersection.

Both $B$ and $T$ are convex polytopes and $B\cap T$ is also convex polytope. I don't need general algorithm, I need something fast and simple.

Have you heard about such an algorithm? Or is it trivial and I can't see it?

I got an idea to "crop" the triangle with each of 6 box's faces. Cropping triangle with each plane can add 1 new vertex, so the resulting object may have up to 9 vertices. Then I compute the bounding box of that object. Am I right? Can it be simplified to get only bounding box output?

# Answer
> 3 votes
**The following answer is incorrect.**

Suppose the triangle has vertices $(x\_1,y\_1,z\_1), (x\_2,y\_2,z\_2), (x\_3,y\_3,z\_3)$ and the box has coordinates $\[x\_\min, x\_\max\] \times \[y\_\min,y\_\max\] \times \[z\_\min, z\_\max\]$. Then the bounding box of their intersection is $\[x'\_\min, x'\_\max\] \times \[y'\_\min,y'\_\max\] \times \[z'\_\min, z'\_\max\]$, where \begin{align\*} x'\_\min &= \max\\{\min\\{x\_1,x\_2,x\_3\\}, x\_\min\\}, \\ x'\_\max &= \min\\{\max\\{x\_1,x\_2,x\_3\\}, x\_\max\\}, \\\\[1ex\] y'\_\min &= \max\\{\min\\{y\_1,y\_2,y\_3\\}, y\_\min\\}, \\ y'\_\max &= \min\\{\max\\{y\_1,y\_2,y\_3\\}, y\_\max\\}, \\\\[1ex\] z'\_\min &= \max\\{\min\\{z\_1,z\_2,z\_3\\}, z\_\min\\}, \\ z'\_\max &= \min\\{\max\\{z\_1,z\_2,z\_3\\}, z\_\max\\}. \\\\[1ex\] \end{align\*}

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


# Question
Title: Complement of Non deterministic Finite Automata
It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^\* \setminus L(M)$.

Is it possible to construct such a complement for a non-deterministic finite automation (NFA)? To my knowledge, it isn't.

# Answer
I'm going to assume that you know that there is an equivalence between DFAs and NFAs in the following sense: For every NFA $M$ there exists a DFA $M'$ such that $L(M') = L(M)$. I'm also going to assume that you know how to, given $M$, calculate $M'$. These are standard methods and they (and their proofs) can be found in any good textbook on automata such as: Hopcroft and Ullman

Given these facts the result is almost immediate: Given an NFA $N$ all you have to do is calculate the corresponding DFA $N'$ and use the complement algorithm which you've mentioned you already know. The resulting DFA is an NFA (since DFAs are just special cases of NFAs) which accepts the complement of the language accepted by the NFA you started with.

So to answer your question, yes it is possible to construct such an NFA, however, if you want to do it quickly you may have some problems
> 8 votes

# Answer
The language represented by an NFA is regular. The complement of a regular language is regular. Every regular language can be represented by an NFA. Hence NFAs can be "complemented".

More concretely, convert your NFA to a DFA and then complement it.

What you're really asking is, probably, is there a *more direct* way to complement NFAs. There are examples in which there is a large gap between the NFA complexity of a language and its complement. For example, the language of all words over $\\{1,\ldots,n\\}$ which *don't* contain all symbols is accepted by an NFA of size $n$ (or $n+1$ if you don't allow multiple starting states), but its complement needs exponentially many states $2^n$.
> 7 votes

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Filling Rows of a Matrix Subject to Conditions
I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)*(N+2)*(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that:

* The sum of values in any row is N
* No rows are repeated (this should ensure that every such possibility is listed)

For example, with N=2, we have 10 (=3\*4\*5/6) rows:

```
2 0  0 0
1 1  0 0
0 2  0 0
1 0  1 0
1 0  0 1
0 1  1 0
0 1  0 1
0 0  2 0
0 0  1 1
0 0  0 2

```

I've been trying for a while to program this (in R, for what it's worth), but I'm struggling to get anywhere. Any advice?

# Answer
Below is some pseudo-code to generate the rows.

It basically uses recursion as follows:

* Try all values up to the remaining total in the current cell.
* Recurse onto the next cell.

Pseudo-code:

```
// (N+1)*(N+2)*(N+3)/6 is a lot
array[2*N]

// What you'll call
printRows(N)
   printRows(N, 1)

printRows(N, pos)
   if pos == array.length + 1
      // reached the bottom-most recursion call
      // we don't really have a choice of value here since we need to get to N
      //   and only have the current value left
      array[array.length] = N
      print array
   else
      for i = N; i >= 0; i--
         array[pos] = i
         printRows(N-i, pos+1)

```

Calling `printRows(2)` will print:

```
[2, 0, 0, 0]
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 2, 0, 0]
[0, 1, 1, 0]
[0, 1, 0, 1]
[0, 0, 2, 0]
[0, 0, 1, 1]
[0, 0, 0, 2]

```

Java test.
> 0 votes

# Answer
If you are allowed to repeat rows, then a simple solution is to repeat the row $(N,0,0,0)$ as many times as needed.

If you are not allowed to repeat rows, this should also be pretty easy to solve. This sounds like an exercise where you learn by doing, so I don't want to spoil it by giving away the answer, but I'll give you some tips and suggestions that will help you develop an answer:

1. What are the requirements for a row to be valid? If $(w,x,y,z)$ are the four numbers in a row, what are the requirements on $w,x,y,z$ for this row to be allowable?
2. If I have one candidate row that meets all the requirements, and another candidate row that also meets all the requirements, can I put the first one in the first row of the matrix and the second row of the matrix? Will that always be valid, or are there any constraints where my choice of the first row of the matrix restricts what I'm allowed to put in the second row of the matrix? (If there are any restrictions, make sure you understand and can state precisely exactly what they are.)
3. How many possible ways are there to choose a single row that meets all of the requirements? Hint: this is a standard problem in combinatorics/counting. If you are in a computer science-oriented course on counting, your textbook will probably include a worked-out problem where it shows how to count the number of ways to place $k$ balls into $n$ bins with replacement, when order does not matter. Make sure you understand the solution to that -- you might find it helpful.
4. How many different rows do you need? Compare this to your answer to #2 above. Relevance: If you need more rows than there are possibilities, and you need them to all be different, you're hosed. If there are more possibilities than you need to list in your matrix, you can pick any subset.
5. How would you enumerate all valid rows? You probably want to use some nested loops, e.g., loop over some range of values of $w$, and for each such $w$, loop over some range of values of $x$, and so on. What range of values should you use for $w$? (What values of $w$ are allowable?) What range of values should you use for $x$? (Since this is a nested loop, your range of values for $x$ is allowed to depend upon $w$.) Fill out the rest of the details.

**Update:** Here's an overview of how to enumerate over these possibilities. (This is really more of a Stack Overflow question than a question for this site, to be honest.) I suggest you use three nested loops: loop over $w$ (over the range $0\ldots N$), then loop over $x$ (over the range $0 \ldots N-w$), then loop over $y$ (over the range $0\ldots N-w-x$), then set $z=N-w-x-y$. In other words:

```
for w=0,1,2,...,N:
    for x=0,1,2,...,N-w:
        for y=0,1,2,...,N-w-x:
            z = N-w-x-y
            append the row (w,x,y,z) to the matrix

```

To generalize this code to enumerate all valid rows with $k$ columns, you should probably ask on Stack Overflow, as that's a coding question. But here's a tip. Think about how you'd enumerate all possible values of a $d$-digit odometer. You'd create an array $A\[0\ldots d-1\]$, initially all zeros, to hold the $d$ digits, and you'd increment through odometer values, one by one. How do you increment an odometer value? Start with your finger pointing to the rightmost digit. Increment that digit; except that if it increments from 9 to 10, that digit has rolled over, so change the 10 to a 0, move your finger left one place, and repeat the whole process (until nothing rolls over). In code, here's how you increment an odometer value:

```
for i=d-1,d-2,...,2,1,0:
    A[i] = A[i]+1
    if A[i] == 10:
        A[i] = 0  // roll-over
    else:
        break out of the loop

```

What does this have to do with your problem? Think of the first $k-1$ columns of each row as an odometer value. We're going to enumerate through them. Except, now the condition for when a digit rolls over is different: instead of rollover happening when that digit goes from 9 to 10, it will instead happen when the sum of that digit and all digits to its left goes from $N$ to $N+1$. Everything else remains the same. So, enumerate all possible values for the first $k-1$ columns, in this way. Then, you can fill in the $k$th column to whatever it needs to be to make sure the entire row sums to exactly $N$. If this doesn't help you, you might need to ask a separate question on Stack Overflow.

Once you work through the answers to all of these questions, you should have a solution. If you have gotten stuck, edit your question show us how far you got so far (e.g., which of these questions you've figured out how to answer), at what stage you've gotten stuck, and what you've tried at that stage.
> 3 votes

---
Tags: algorithms, integers, linear-programming
---


title: How does insertion work in an AVL tree?

text:
# Question
Title: How does insertion work in an AVL tree?
From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, feel free to share. I am a bit lost with this idea of maintaining a certain height in this data structure.

# Answer
> 6 votes
AVL trees should be binary search trees. In the example you gave, 2 is the right child of 3. That isn't right since 2 \< 3. Assume the 2 and 3 are switched, which results in a correct binary tree.

Remember the rule for AVL trees: for any node, the height difference between the left child and right child is at most 1. Following the tree down, the 10 is inserted as the right child of 9. This breaks the rule. Look at the subtree rooted at 6. The height of the left child is 0 while the height of the right child is 2. The tree must be rotated, which is the tricky part. 8 becomes the right child of 4. 6 becomes the left child of 8. 7 becomes the right child of 6. After all of that, the final AVL tree would look like this:

(courtesy of Uottawa). I always visualized rotations like this:

1. With your left hand, "hold" the 6 and "detach" it from the 4.
2. With your right hand, "hold" the 8.
3. "Drop" the 6 so that it swings counterclockwise, due to gravity of course. (6 is now the left child of 8)
4. The 6 "hits" the 7. (7 is now the right child of 6)
5. "Attach" this whole subtree (now rooted at 8, since the 6 "fell") back onto the 4.

---
Tags: data-structures, trees, search-trees
---


# Question
Title: Neural network diverging instead of converging
I have implemented a neural network (using CUDA) with 2 layers. (2 Neurons per layer). I'm trying to make it learn 2 simple quadratic polynomial functions using **backpropagation**.

But instead of converging, it is diverging (the output is becoming infinity)

Here are some more details about what I've tried:

* I had set the initial weights to 0, but since it was diverging I have randomized the initial weights (Range: -0.5 to 0.5)
* I read that a neural network might diverge if the learning rate is too high so I reduced the learning rate to 0.000001
* The two functions I am trying to get it to add are: 3 * i + 7 * j+9 and j\*j + i\*i + 24 (I am giving the layer i and j as input)
* I had implemented it as a single layer previously and that could approximate the polynomial functions better than it is doing now
* I am thinking of implementing momentum in this network but I'm not sure it would help it learn
* I am using a linear (as in no) activation function
* There is oscillation in the beginning but the output starts diverging the moment any of weights become greater than 1

I have checked and rechecked my code but there doesn't seem to be any kind of issue with it.

So here's my question: what is going wrong here?

Any pointer will be appreciated.

# Answer
1. With neural networks, you always need to randomly initialize your weights to break symmetry.
2. If you don't use a non-linear activation function in the hidden units, then you might as well have stayed with a single layer. Your network is now just a composition of two linear functions, which is of course just another linear function.
3. That learning rate seems excessively small. If I'm using a fixed learning rate I normally find a value somewhere between 0.1 and 0.0001 to work well for most problems. This is obviously problem dependent so take my experience for what it is.
4. In addition to checking your code against the math you've learned, when doing gradient based optimization it can be very helpful to analytically calculate the gradients required using finite differences and compare them to the values you're computing in your code. See here for a discussion of how you can do this. I've caught many errors this way and seeing these types of tests pass always helps me feel much more sure of code correctness.
> 8 votes

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


# Question
Title: Proving greedy choice property of fractional knapsack
A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:

---

From Slide 5 of this link:

Given: A set of items $I = \\{I\_1,I\_2..I\_n\\}$ with weights $\\{w\_1,w\_2 ... w\_n\\}$ and values $\\{v\_1,v\_2 ...v\_n\\}$. Let $P$ be the problem of selecting items from $I$, with the weight limit $K$ such that the resulting value is maximum.

Let $O = \\{o\_1,o\_2 ... o\_j\\} \subseteq I$ be the **optimum** solution of problem $P$.

Let $G = \\{g\_1,g\_2 ... g\_k\\} \subseteq I$ be the greedy solution, where the items are ordered according to the greedy choices.

We need to show that there exists some optimal solution $O'$ that includes the choice $g\_1$ .

CASE 1: $g\_1$ is non-fractional.

1. If $g\_1$ is included in $O$, then we are done.
2. If $g\_1$ is not included in $O$, then we arbitrarily remove $w\_{g\_1}$ worth of stuff from $O$ and replace it with $g\_1$ to produce $O'$.
3. $O'$ is a solution, and it is at least as good as $O$.

---

In the above proof, step $3$ for CASE 1 merely shows that weight criteria is satisfied. How does it show that $O'$ is also an optimal solution(i.e. in terms of value achieved), more so when we are "arbitrarily removing $w\_{g\_1}$ worth of stuff" without paying attention to corresponding change in value ?

**UPDATE**: I found the answer in terms of change in value here. I am not sure if this should go into the answer part. Mods, please suggest.

# Answer
Remember that $O$ is assumed to be an optimal solution. If $O'$ is a solution that is at least as good as $O$, then $O'$ has to be optimal too.

In particular, since $O$ is optimal, $O'$ cannot be *better* than $O$; so $O'$ must be exactly as good as $O$. Since there's nothing better than $O$, and since $O$ and $O'$ have the same goodness, there can't be anything better than $O'$ either. Consequently, $O'$ is also optimal: both $O$ and $O'$ are optimal solutions. (There can be more than one optimal solution.)
> 3 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof, greedy-algorithms
---


title: How do the non-∪ variants of NFAs work?

text:
# Question
Title: How do the non-∪ variants of NFAs work?
I've only recently learned anything substantial about finite automata, and I've just come across some things I hadn't seen before. Specifically, that classic NFAs are ∪-NFA, and there are also these things ⊕-NFA , ∩-NFA and ⋆-NFA (I love unicode). These can all be seen in http://fastar.org/publications/PresentationFEW2006Geldenhuys.pdf or http://www.cs.sun.ac.za/~lvzijl/publications/fsmnlp2009.pdf

How are these different from the NFAs I'm familiar with?

# Answer
> 2 votes
Alright, I think I've figured it out. It can be seen in working with the transition function Δ : Q × Σ → *P*(Q), where Q is the set of states and Σ is the alphabet.

First, lets define some unary functions (*P* is powerset, of course):

* ∪ : *P*(S) -\> S, ∪(X) = X1 ∪ X2 ∪ ... Xk where k = |X| (classic NFA)
* ∩ : *P*(S) -\> S, ∩(X) = X1 ∩ X2 ∩ ... Xk where k = |X|
* ⊕ : *P*(S) -\> S, ⊕(X) = X1 ⊕ X2 ⊕ ... Xk where k = |X| (symmetric difference NFA)

So basically, take a set of sets, and either and, or, or xor them all together.

Now, we extend the domain of our transition function to Δ : Q × Σ\* → *P*(Q), where Σ\* is a string of Σ, via the following recursive definition:

* Δ(s, *e*) = s, where *e* is the empty string
* Δ(s, *xa*) = ⋆({ *s'* ∈ Δ(s, x) | Δ(*s'*, a) })

Where ⋆ can be any one of the three unary operators we defined above (and as specified in the second link in the original question, can be any associative and commutative operator on sets, converted into a combining unary function like above). The ⋆-NFA is the generalized NFA, so ⋆ is basically a wild card.

This is most intuitively understood in how an NFA is converted to a DFA by the subset construct. With a ∪-NFA, when you're creating your DFA states, you are taking the union of each result of the transition function from all the previous NFA states. With the other operators, its the intersection or symmetric difference of those states, respectively. If you take another look at that first link that I put in the original question, with this information in mind, it makes a pretty good example that should be relatively easy to understand. It seems this was the original intent of the slides, but without accompanying lecture it was a bit difficult to follow. I guess that about covers it.

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


# Question
Title: Something I don't understand about Genetic Algorithms
I've had a bit of experience programming Neural networks but I am fairly new with genetic algorithms (I'm only 17). I have a major issue that I can't understand. If a child get's one chromatid from one parent and another from another parent, then the genes are crossed over, how do you determine which alleles are active in the child? How do other people go about mating with genetic algorithms. No need to go deep into it because I also want to work somethings out for myself but a general idea would be good enough. Thanks in advance.

# Answer
Generally speaking, evolutionary algorithms stop well short of trying to model real biology, and this is one example of something that occurs in nature but not in commonly used evolutionary algorithms.

Instead, we tend to use a system where all individuals have only one value for each gene, and they're all "active". Replication, mutation, and recombination are considered to be atomic operations with no concern given to any intermediate stages. Consider the simplest case of a binary encoding. You might have two parents, A and B, as

```
A = 0101101001
B = 1001010010

```

To do crossover, we simply create an offspring by choosing exactly one parent for each bit in the offspring to copy from. We can formalize this a bit with something called a mask -- a bit string where a 1 indicates that we choose the value from A and a 0 indicates we choose from B. Thus, one point crossover might have a mask like

```
M = 0000001111

```

with our parents A and B, we would then get a child C as

```
A = 0101101001
          ^^^^
B = 1001010010
    ^^^^^^
C = 1001011001

```

So here, the offspring C has gotten copies of the first six genes of parent B and the last four of parent A, but at no point do we consider the process by which chromosomes would be copied in a biological system. We simply allocated a new variable and did a memory copy to instantaneously duplicate parts of the parents.

If we want to mutate the offspring, we might simply pick a bit at random and flip it. Again, we don't worry about biology here and how mutations actually occur in nature. We just define mutation to be the flipping of a single bit in memory and do it.

One point crossover is about the simplest thing you could do, but essentially all commonly used methods look similar in that the child gets a single value for each position and no explicit notion of binding or connection to the parents is considered. We don't really think of crossover in terms of chromatids -- we just directly copy allele values using some well-defined (but probably not biologically plausible) crossover operator. So there's never any question of which allele values are active -- they all are.
> 5 votes

---
Tags: artificial-intelligence, neural-networks, genetic-algorithms
---


# Question
Title: Problems unsolvable by an oracle machine?
Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?

Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...

# Answer
> 5 votes
Every problem $P$ can be solved with an oracle machine with oracle access to $P$. In order to get a more meaningful answer, we consider the concept of *Turing semi-degree*, which is the set of all problems computable with an oracle to $P$, for some problem $P$. The same diagonalization argument used to prove that the halting problem isn't decidable shows that no Turing semi-degree encompasses all languages. (Alternatively, there are uncountably many languages but only countable many problems computable with any given oracle.)

A Turing degree consists of the "hardest" problems in a Turing semi-degree. More formally, it is the set of problems *equivalent* to some problem $P$: problems which are computable given an oracle to $P$, and conversely $P$ can be computed given an oracle to them. The study of Turing degrees consists a significant part of classical *recursion theory*.

---
Tags: complexity-theory, oracle-machines
---


title: Convert regular expression to DFA

text:
# Question
Title: Convert regular expression to DFA
How do you construct a DFA from a language that has a + sign? e.g. $L = \\{(a+b)\\}\*$

# Answer
> 2 votes
In this case + stands for the OR-operation. So the automaton is indifferent using an $a$ transition or a $b$ transition.

It's sufficient to construct an automaton with one state which is initial and final state and having one transition labeled with a, b.

# Answer
> 2 votes
It looks like your language is specified as a regular expression. (Regular expressions are allowed to contain the `+` and `*` operators.)

So, in general, you can use the following procedure:

1. *Convert the regular expression to a NFA.* There are standard methods for this; for instance, Thompson's algorithm is perhaps the best-known. See Russ Cox's explanation for a great tutorial.
2. *Convert the NFA to a DFA.* Again, there are standard algorithms for this task as well: namely, the subset construction, where you have one state in the DFA for each possible subset of states of the NFA.

All of this should be covered in standard sources, e.g., Wikipedia or an automata theory book. In the future, please go check those standard sources and do a bit of research on your own before asking here, to comply with this sites' expectations.

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Finding exact corner solutions to linear programming using interior point methods
The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior point methods walk the inside of the polytope. As a result, when a whole plane of the polytope is optimal (if the objective function is exactly parallel to the plane), we can get a solution in the middle of this plane.

Suppose that we want to find a corner of the polytope instead. For example if we want to do maximum matching by reducing it to linear programming, we don't want to get an answer consisting of "the matching contains 0.34% of the edge XY and 0.89% of the edge AB and ...". We want to get an answer with 0's and 1's (which simplex would give us since all corners consist of 0's and 1's). Is there a way to do this with an interior point method that guarantees to find exact corner solutions in polynomial time? (for example perhaps we can modify the objective function to favor corners)

# Answer
> 6 votes
You might want to read the paper:

> Sanjay Mehrotra, On finding a vertex solution using interior point methods, Linear Algebra and its Applications, Volume 152, 1 July 1991, Pages 233-253, ISSN 0024-3795, 10.1016/0024-3795(91)90277-4. sciencedirect article link

# Answer
> 4 votes
While the question in general makes sense, it's odd that you pick maximum matching as an example, because there are many algorithms (max flows for max cardinality bipartite matching, Edmonds' algorithm for nonbipartite matching, and the Hungarian algorithm for max weight bipartite matching) that will all give integer vertex solutions to the problem.

# Answer
> 3 votes
*For the lack of detail, this is merely a longer comment:*

Karmarkar's polynomial time algorithm does only move *near* the edge. At the end, it finds a suitable basic solution (e.g. corner) which is optimal using a *purification scheme*¹. You can use this or a similar technique to move to a corner from a plane.

---

¹ I can't make it out in in Karmarkar's original paper. My reference is "Lineare Optimierung und Netzwerkoptimierung" (English: Linear and network optimisation) by Hamacher and Klamroth which has German and English text side by side.

# Answer
> 2 votes
Yes, there is a simple method and I have implemented it in C++ to combine the speed of interior point methods with the accuracy of simplex methods (using iterative refinement of the inverse of the basis matrix I can achieve accuracies of 1 part in 10^15 and better on dense constraint matrices with more than 1000 variables and constraints).

The key is in the simplex method that you use. Assume that the simplex method has a mechanism for refactoring a basis (e.g. after cumulative rounding errors render it necessary), and that this refactorization method simply recreates a basis inverse matrix for a basis that contains all the desired list of basic variables. Furthermore assume that even if the desired basis cannot be recreated in full, that the simplex algorithm is able to continue from a basis that contains 95% of the target basis, then the answer is very simple.

All you have to do is take the solution from your interior point method, eliminate the variable whose primary solution values are implied to be zero by complementary slackness, and given a basis size in the simplex problem of b, take the b variables in the interior point solution with the largest values (or as many as there are non-zero values if that is less than b), and refactor the simplex basis to contain those b variables. Then continue the simplex method until it solves. Since you are starting the simplex problem close to the finish this is usually very fast.

---
Tags: algorithms, optimization, linear-programming
---


# Question
Title: What is the impact of synchronisation overhead on parallel speedup?
When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used?

Is coarse-grained parallelism better than fine-grained parallelism in certain situations?

# Answer
For current multicore CPUs with support for SMT (Simultaneous Multi Threading), coarse-grained parallelism is strictly required, independently of the parallel technology used (pthreads, OpenMP, MPI). You need to feed each thread or process with enough work, otherwise the cost of thread creation/management and synchronization (for Pthreads and OpenMP) or the cost of communication and synchronization (for MPI processes) will be much higher than the work done per thread/process.

For GPUs, since these are actually SIMD units, i.e., data parallel machines, you need to feed them with data according to a fine-grained data decomposition (again, this is independent from the actual technology used, such as CUDA or OpenCL). In this case, thread management is lower (because it is done in hardware, not in software), but in general synchronization must be avoided, as much as possible. If you can not restructure your code so as to avoid synchronization you are going to experience bad performances on GPUS. Both NVIDIA and AMD recommend to avoid synchronization and to use GPUs for very simple data parallel tasks. Moreover, you need to copy the data to be processed from the host to the GPU and back once results are computed, and this will also incur a performance penalty, depending on the size of your data processed by the GPU device.
> 2 votes

# Answer
There is no general answer to this question. There certainly are situations where coarse-grain parallelism is better than fine-grain parallelism.

It is important to note that the efficiency of an algorithm depends not only on the problem but also on the environment. You usually want to break down your work in pieces of sensible size and let the environment (e. g. the JVM) determine the optimal number of parallel executions. Do benchmarks on different setups and with different parameters to your algorithm and you will see if your assumptions are right. There really is no substitute for testing here.

Edit: I must admit I never did anything serious with CUDA nor with OpenCL. I guess similar rules apply but I will be happy if you correct me.
> 1 votes

---
Tags: efficiency, parallel-computing, concurrency, synchronization
---


# Question
Title: Optimization of Hierarchical Data Propagation
I have a system in existence which works on parent-child model.

1. They share common attributes, as they belong to same class.
2. A parent can enforces certain data on any user selected attribute, and the data is required to be propagated down the hierarchy for the same attribute in all children and their children.
3. For a given attribute, if a child's parent dies (object gets destroyed) or child has not been enforced by parent, child can behave the same way, like in point #2, (on user request) for its children.

My system is pretty big (in database). For example:

* Each object of the class has 150 atributes.
* There are in total about 8 million attributes for objects created. Hence, the objects are close to 53,333.
* There is a single parent for the objects. Its a big tree.

If I want to enforce data on the top most parent for a single attribute, it takes about 8 mins for it to complete.

Does anyone know a model which can perform faster than hierarchical model, but similar to behaviour?

# Answer
I am guessing that you used a technique known as "Adjacency list" to store your tree in the database. However, other solutions are also available, including "Path enumeration", "Nested sets" and "Closure table". The latter one, closure table, is the best one and you may want to design again your database using this technique for storing your hierarchical data.

For more information, see these slides, in particular the section on naive trees which starts at the slide #48. Or, this book from the same author. Finally, a more formal treatment of this subject is also included in this book.
> 1 votes

---
Tags: algorithms, databases, performance
---


# Question
Title: Finding all marked elements using Grover's algorithm
Grover's algorithm uses an oracle function $f(x) \to \\{0,1\\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an assignment I am supposed to design a variant of the algorithm that finds *all* of the $t$ marked elements ($t$ is known). I want to do this by repeating the following procedure $t$-times:

1. Use Grover's algorithm to find any marked element $x$.
2. Delete $x$ from the data base.

I think my solution is correct, but I am still not feeling comfortable with quantum computing. In particular, I am unsure of how one could implement the removal step since it would mean to manipulate the function $f$.

Can anyone clarify?

# Answer
> 3 votes
After discussing the problem with some people from my institute that work on quantum computing, it turns out that one can augment the oracle to not provide elements that have already been found in previous iterations of the search. The trick is to modify Grover's algorithm as follows:

Say, we already know that 2 is an answer (from a previous iteration). After using the oracle to invert the phase of the marked elements within Grover's algorithm, we apply another operation that inverses the phase of the known answers again (thus cancelling the previous inversion for answers that are already known). Accordingly, the inversion about the mean in Grover's algorithm will not amplify the amplitude of these states.

# Answer
> 2 votes
This approach suffers from a couple of problems. First of all, Grover's algorithm in its usual form *depends* on the fact that there is *exactly one* good item in the search space, so you'll need to modify it to account for the fact that there are now several.

Second of all, you ought to justify whether or not you can easily delete arbitrary elements from the database. The oracle function $f$ need not be (indeed probably won't be) a literal lookup in a literal database. One good example might be an $f$ that tells you whether $x$ is a factor of $N$ for some $x$ and $N$ integers. You can't just stop $x$ from being a factor of $N$ once you find it, but you might well be able to use $f$ to manufacture a new function that tells you when $y$ is a factor of $N$ that is not $x$. If you can come up with a function that flips the $x$ component of the state, then you can just do $f$, which flips the $x$ component, and then flip it back, to get the desired modified indicator.

You ought to think about whether you really need to do that, though. You're working with a probabilistic algorithm anyway, so it probably wouldn't hurt to get the same answer twice a few times.

---
Tags: algorithms, quantum-computing
---


# Question
Title: Knapsack problem -- NP-complete despite dynamic programming solution?
Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right?

I have read it is actually an NP-complete problem, though, which would mean that solving the problem in polynomial problem is probably impossible.

Where is my mistake?

# Answer
> 47 votes
Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as *binary* numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.

On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in polynomial time (in the size of the input).

This kind of problems is called weakly $\sf{NP\text{-}complete}$.

$\dagger$: Another good example to understand the importance of the encoding used to give the input is considering the usual algorithms to see if a number is prime that go from $2$ up to $\sqrt{n}$ and check if any of them divide $n$. This is polynomial in $n$ but not necessarily in the input size. If $n$ is given in binary, the size of input is $\lg n$ and the algorithm runs in time $O(\sqrt{n}) = O(2^{\lg n/2})$ which is exponential in the input size. And the usual computational complexity of a problem is w.r.t. the size of the input.

This kind of algorithm, i.e. polynomial in the largest number that is part of the input, but exponential in the input length is called *pseudo-polynomial*.

# Answer
> 44 votes
The main confusion lies in the difference between "**size**" and "**value**".

"**Polynomial Time**" implies polynomial w.r.t the **size** of input.

"**Pseudopolynomial Time**" implies polynomial w.r.t the **value** of the input. It can be shown (below) that this is equivalent to being exponential w.r.t the **size** of the input.

---

In other words: Let $N\_{size}$ represent the size of the input and $N\_{val}$ represent the value of the input.

**Polynomial Time:** $O(N\_{size}^x)$ for $x\in\mathbb{N}$

**Pseudopoly. Time:** $O(N\_{val}^x)$ for $x\in\mathbb{N}$

Now, the knapsack problem has a pseudopolynomial, ***not polynomial***, solution because the dynamic programming solution gives a running time dependent on a **value** -- i.e. $O(nW)$, where $W$ is a **value** representing the max capacity.

Now, a **value** can be converted into a **size** by representing it in terms of # of digits it takes to represent it. $N\_{size}=Log\_b(N\_{val})$ tells you how many digits are needed to represent $N\_{val}$ using base $b$. This can be solved for $N\_{val}$ to give:

$$N\_{val}=b^{N\_{size}}$$

Plugging this into the pseudopolynomial time definition shows that it is exponential w.r.t $N\_{size}$:

**Pseudopoly. Time:** $O(b^{xN\_{size}})$ for $b, x\in\mathbb{N}$

# Answer
> 7 votes
The Knapsack problem as defined in Karp's paper is NP-Complete since there is a reduction from other NPC problem (Exact Cover, in this case) to Knapsack. This means that there is **no** polynomial algorithm that can solve **all** instances of the Knapsack problem, unless $\text{P}=\text{NP}$.

There are, however, different variants (e.g., 0-1 Knapsack and others) that may or may not have polynomial-time solutions or good approximations. But this is not the same as the general Knapsack problem. Also, there might be efficient algorithms that work for specific (families of) *instances*, but these algorithms will take longer on other instances.

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


# Question
Title: What is the size of the Perfect binary tree with n nodes in last level
I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be calculated

# Answer
A perfect (binary) tree of depth $k$ has exactly $2^{k+1}−1$ nodes.

There are probably several ways to prove it. A simple way is by induction. Each level has twice as many nodes as the previous level (since each node has exactly 2 children in a binary tree). The base level - the root - has 1 nodes. Note that the root is depth 0, not 1.

Let's denote the number of nodes in level $i$ by $N\_i$. We know,

$N\_0 =1$
$N\_i = 2N\_{i-1} = 2^{i}$

The total amount of nodes (of tree of depth $k$) is $S\_k \equiv N\_1 + N\_2 + \cdots + N\_k$, that is,

$$ S\_k = 1 + 2 + 4 + 8 + \ldots +2^{k}.$$ This is a geometric series, whose sum is $S\_k = 2^{k+1}-1$.

Now for your question:
We are given a perfect (binary) tree with $n$ nodes *at the last level*, how many nodes does it have overall?
We are given that at the last level (call it level $k$) we have $N\_k=2^k=n$ nodes. Then $k=\log\_2 n$ and we get that $S\_k=2^{k+1}-1=2n-1$; Yes, each level has one more node than the entire tree above it.

A related question:
we are given a perfect (binary) tree with $n$ nodes, what is its depth?
Now we are given that the total number of nodes is $S\_k = 2^{k+1}-1 = n$, thus $k=\log\_2 (n+1)-1$ (again, the root is considered depth 0 here).
> 5 votes

---
Tags: data-structures, binary-trees
---


# Question
Title: What are efficient data structures for inserting and accessing elements?
Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time?

When I say "reasonable time", I mean that it should be equal to or better than $O(\log N)$.

I'm looking for a structure similar to a dynamic array, but I need a better behavior in the Insertion operation. When the array size grows, the time grows exponentially (Except at the end of the array).

# Answer
A balanced binary tree should meet your needs. You can achieve $O(\lg n)$ time for both operations, as long as the tree is kept reasonably balanced.

To support the "access by index" operation, you can augment the tree so that each internal node contains the number of children underneath it. Insert operations still take $O(\lg n)$ time (find the place where to insert a new leaf, then traverse the path from that leaf to the root, incrementing the counter in each such node). The "access by index" operation can be done using the counts in each node; they tell you at each stage whether to recurse to the left child or right child.

There are probably other data structures as well, but this should meet all of the requirements you listed.
> 7 votes

# Answer
Since you are after *average* efficiency, you may be interested in the following data structures (assuming amortisation is fair, too):

In fact, *most* dictionary data structures that are not a plain list will work for you. I recommend you do some reading, e.g. in CLRS for starters.
> 3 votes

---
Tags: data-structures, efficiency
---


title: Getting started with Compiler Design

text:
# Question
Title: Getting started with Compiler Design
This is the first time I will be studying compilers in depth. Can someone point me to best online resources (courses, articles, tutorials, video etc ) and books?

My main aim will be to do some practicals instead of just reading theory.-something where theory practical goes in parallel. So the reference must fulfill this expectations.

# Answer
Alex Aiken's Coursera course on compilers is very nice. I suggest to take it and do all exercises. Another interesting looking online course can be found here, although I have not checked it out in detail (I would be interested in opinions about it).

As to books, here are a couple.
> 6 votes

---
Tags: reference-request, compilers
---


# Question
Title: What linked list data structure adjustments would give me fast random lookup?
I am presently using an doubly linked list (C++ `std::list`) to hold a bunch of records that each have a unique integer identifier. The linked list is created in sorted order such that in the list, the next item always has a larger unique identifier than its predecessor.

The issue I'm facing is that occasionally I need to be able to insert an item quickly into its relative sorted position and using a plain linked list means this operation is $O(n)$ which is causing performance issues for me. Generally, this would mean I want to use something like a binary tree (C++ `std::map`), however, I am also depending upon the following feature of a doubly linked list for good performance:

* Ability to splice a contiguous section out of one linked list into another in $O(1)$ time. (Amortized $O(1)$ or $O(\log \log n)$ would be good enough.)

One feature of my data that I would like to leverage is that I often have long ranges of contiguous records where each one's unique integer is exactly one more than its predecessor. When searching for an item's relative sorted position, it would always be outside such contiguous records since there are no duplicate identifiers.

I'd like to find a replacement data structure or augmentation to a doubly linked list that will allow me to continue to splice whole sections from one list to another in constant time but allow me to locate the sorted position in which to insert a new record in better than $O(n)$ time.

Other operations include forward and backward iteration across the items. The record indexes begin at zero and grow upwards towards 64 bits, generally sequentially, and the code works well in such cases. Occasionally some records are not available before subsequent ones, it is the insertion of these missing records that causes the performance issues now.

One possible approach that occurs to me is to cache the location of several indexes. The cache would get invalidated whenever a splice removes items that might overlap the cached entries. With this cache, instead of doing a linear search, the search could instead begin from the cache point iterator whose unique index is closest to the one whose position is being searched for. However, I'd like to more fully utilize the feature of the contiguous records. I also thought about a hierarchical linked list where I have a top level linked list of contiguous regions, where each region is a linked list of records that are consecutive, but I didn't see a clean way to adapt a linked list to provide this functionality. Perhaps something like this has been done before? I find skip lists to be close, but do not see the splice() functionality, plus a generic skip list would not leverage the fact that insertion never occurs within contiguous records.

# Answer
One simple approach might be to use a doubly-linked list of extents, where each extent represents a sequence of contiguous records. The records within each extent could in turn be represented with a doubly linked list.

This preserves your ability to do $O(1)$ time splicing, and now the insert operation takes $O(k)$ time, where $k$ is the number of extents (rather than $O(n)$, where $n$ is the number of records). If you have many fewer extents than records, this might be a partial improvement.

I don't know whether this will be better than a simple skip list or binary tree.

Note that if you use a binary tree, you can still do efficient splicing. The splicing operation is no longer $O(1)$ time, but it can be done in $O(\log \ell)$ time, where $\ell$ is the number of records in the spliced segment. This is not as fast as $O(1)$ time splicing, but depending upon the relative frequency of your different operations, it is another data structure you could consider (e.g., benchmark on realistic data sets).

And, of course, you could combine these ideas, e.g., with a binary tree of extents, where each extent is in turn a doubly-linked list of contiguous records. Inserts will take $O(\lg k)$ time, and splicing can be done in $O(\lg \ell)$ time (both of which might potentially be better than the $O(\lg n)$ achieved through a simple binary tree).
> 6 votes

---
Tags: data-structures, time-complexity, binary-trees, linked-lists
---


title: Solving a simple recurrence

text:
# Question
Title: Solving a simple recurrence
I'm having a real hard time solving recurrences using the substitution method.

Show that: $T(n) = T(n/2) + 1$ is $O(\lg n)$

I thought this to be relatively easy:

We have to show that $T(n) \leq c \lg n$

Substitution gives me:

$\qquad \begin{align} T(n) &\leq c \lg(n/2) + 1 \\ &= c \lg n - c \lg 2 + 1 \\ &= c \lg n - c + 1 \\ &\leq c \lg n \end{align}$

for every c.

I was under the impression this was it, but when I was looking for an answer, I came around a much more elaborate answer on the web, given involving subtracting a constant. I don't get why that's needed, I thought I had shown what was needed.

Any help would be greatly appreciate, starting Monday I'm enrolled in an algorithms class and I don't want to get behind!

We are using the CLRS book (surprise) and though I appreciate the amount of information in it, I'd rather have some more resources. I've really enjoyed a datastructures class and I really think I can enjoy this as well, but more resources would be very much appreciated.

# Answer
> 1 votes
Luckily i had 2 day ago the algorithm exam and so i was able to solve your question :-) When solving recurrences try first to use the Master method, if you can't succeed than try other methods.

# Answer
> 0 votes
**An easy way to solve recurrence relations**

Using your example:

T(n) = T(n/2)+1 is O(lgn)

T(1) = 0 .....suitable basecase

**STEP 1**

Solving the recurrence relation

```
 T(n) = T(n/2) + 1

      = T(n/4) + 1 + 1

      = T(n/8) + 1 + 1 + 1
      :
      :
      = T(n/2^k) + k    ...(3)      (this step summarizes the recursive steps)

```

**STEP 2**

Now, let

```
      n/2^k = 1

      n = 2^k .... (1)

      also k = logn .... (2)

```

**STEP 3**

Substituting (1) and (2) in (3)

```
 T(n) = T(n/n) + logn

      = T(1) + logn

      = 0 + logn    (recall T(1) = 0)

      = logn

```

Hence: Order is O(logn)

note: logn is of base 2

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


# Question
Title: Measures and probability in formal language theory
I am looking for references for the following problem: I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in some way (as a subset of the regular languages) and that the languages contained in this class are rather "bloated".

For the latter point, I could prove that all languages in the class have a large diameter with respect to many common metrics on strings. However, I want to consider the following: Given a language from the class, we know it has a large diameter, but does it also have a large "volume" (that is, measure), or put differently, if I choose randomly a finite word, is there anything meaningful to say about how "probable" it is that the word belongs to the language? Of course, we can lift the problem: Picking a random language, how probable is it to get a language in the class?

Are there any references or standard approaches for looking at classes of (regular) languages from this point of view (or is this considered as generally uninteresting)?

# Answer
There is the concept of *density* of languages (see e.g. here). The density $\operatorname{den}\_L : \mathbb{N} \to \[0,1\]$ of $L \subseteq \Sigma^\*$ is defined by

$\qquad \operatorname{den}\_L(n) = \frac{|L \cap \Sigma^n|}{|\Sigma^n|}$.

For any fixed length, the density corresponds to the probability of picking a word from the language, assuming we pick uniformly at random. Add a distribution over lengths and you may have what you need.

You may be able to express your concept of "volume" in terms of this notion, maybe by investigating $\lim\_{n \to \infty} \operatorname{den}\_L(n)$.

As for "randomly picking a language" -- how would you do that? There are uncountably many languages over any given alphabet so I'm not sure how you would define a (nice) probability distribution.
> 4 votes

# Answer
I don't know any standard measures, but here is an idea regarding your first question. It is known that the number of words of length $n$ in a regular language is $Cn^t \alpha^n (1 + o(1))$ for some integer $t \geq 0$ and reals $C,\alpha \geq 0$ (more accurately, for some integers $d,N \geq 1$ this is true for every residue class modulo $d$, given $n \geq N$). You could find the parameters $C,t,\alpha$ and using them argue that your language is "dense".
> 2 votes

---
Tags: formal-languages, reference-request, regular-languages, probability-theory
---


# Question
Title: Recursive definition of sum of two numbers in terms of the successor function
This is a question from the book `Data structures using C and C++ by Tenenbaum`. Not a homework problem but self-study.

> Recursive definition of a+b, where a and b are non-negative integers, in terms of successor function `succ` defined as
>
> succ(int x) { return(x++); }

I have been thinking how is it possible? Can I change the function? I am not sure from the problem definition in the book. So how can this be done?

# Answer
Here is a hint:

> a + 3 = succ(succ(succ(a)))

Also, by definition, every natural number is either 0 or the successor of some (smaller) natural number.
> 3 votes

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


# Question
Title: Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?
When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can never force the product of running time and consumed memory below a clearly palpable limit. This is formally similar to Heisenberg's uncertainty principle: the product of the uncertainty in position and the uncertainty in momentum of a particle cannot be less than a given threshold.

Is there a theorem of computer science, which asserts the same thing? I guess it should be possible to derive something similar from the theory of Turing Machines.

(I asked this question originally on StackOverflow.)

# Answer
This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a *Turing machine*, $T \cdot S = \Omega(n^2)$.
> 10 votes

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


# Question
Title: Does the time complexity of a problem change with encoding of the problem?
Suppose I have a decision problem $D$ and I encode it to a language $L \subset \\{0,1\\}^\*$. Now, I can also encode it to a different language $L'$.

Is there any theorem relating the time complexity of $L$ and $L'$?

How does the time complexity of a problem change with different encodings of the same problem?

# Answer
> 8 votes
Yes, the complexity depends on the encoding. The only thing you can be sure of is that if translating from encoding $L$ to encoding $L'$ or vice versa has the complexity $f$, and $D$ can be solved with complexity $g$, then $D'$ (same problem expressed with the encoding $L'$) can be solved with complexity $O(f+g)$ by going back and forth between encodings.

It isn't just a matter of length of the encoding. To give a simple example, let $L$ be positive integers represented in binary, and $L'$ be positive integers represented by their prime factorization. There is a polynomial bound in the size of one representation in terms of the other. Yet for a long time, it was not known whether primality testing can be solved in polynomial time in the binary representation; but in the factorization representation, it's trivially polynomial (probably $O(1)$ depending on the representation details).

Or consider the decision problem “is integer $n$ a member of set $S$”. If the set is represented by an unordered list of integers, this problem evidently requires at least linear time. But if the set is represented by a balanced search tree, lookup time is polylogarithmic in the size of the set.

In most concrete cases, there is an evident representation that everyone assumes, or more precisely there is a class of representations that are all equivalent up to a transformation that takes negligible time. But sometimes the representation is relevant, most frequently when analyzing data structures with more precision than polynomial time.

# Answer
> 6 votes
The time complexity depends upon the encoding. The time complexities for $L$ and $L'$ could be arbitrarily far apart, given a crazy enough encoding.

In practice we usually care about the time complexity for a "natural" encoding. Often, if there are multiple "natural" encodings, then they all tend to lead to approximately the same time complexity (e.g., if you can convert between the encodings efficiently). However, there is no formal guarantee of this.

Therefore, technically speaking, one cannot speak of the time complexity of a problem without specifying the particular encoding used.

# Answer
> 5 votes
Consider any NP-complete language $L$ and its brute-force (hence exponential-time) solver $A$. Now define

$\qquad L' = \\{ x\\$0^{|x|^{|x|}} \mid x \in L \\}$.

Now clearly, a slight adaption of $A$ (use input only up to $\\$$) decides $L'$ in time exponential *in $|x|$* and thus in time polynomial in the length of its own input (which is from $L'$). That is, $L' \in \mathsf{P}$.

A simpler consideration is to move from the standard binary to unary encoding. Suddenly, trivial primality checks and even factorisation run in polynomial time. This concept is related to pseudo-polynomial runtime.

So yes: the encoding matters *if it changes the input length significantly*. Therefore, the typical assumption is to use

* a non-unary encoding with
* at most a constant factor overhead (over the bare information),

as vague as that is.

Note that not even runtimes in terms of $\Theta$-classes are invariant using these assumption alone. Imagine an encoding of arrays that interleaves the numbers; this adds a polynomial factor to finding the maximum. So you should probably be careful even with "good" encodings if you want to say something with higher granularity than up to polynomial factors.

# Answer
> 4 votes
Not exactly an answer to your question, but the Berman-Hartmanis conjecture states (informally) that all NP-complete problems are encodings of each other, in some sense. The notion of encoding used in the conjecture does preserve time complexity, up to a polynomial difference.

---
Tags: complexity-theory, terminology, time-complexity
---


# Question
Title: Polynomial-time algorithm with exponential space is eligible?
I'm curious about two things.

1. When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space? For example, when algorithm is considered to be given a input from domain $\\{0,1\\}^n$, what if the algorithm internally queries its exponential sized table (ex. $0^n\to0,0^{n-1}1\to1$ and so on..) and outputs the result? Does it still polynomial-time algorithm?
2. In theoretical cryptography, one-way function $f:\\{0,1\\}^\*\to\\{0,1\\}^\*$ has a requirement, which is related with *hard-to-invert* property, as following block. If the answer to above question is yes, is it possible to construct algorithm $A'$ to simulate exactly same as $f$ for every value in $\\{0,1\\}^n$ using exponential table as described in above question? If then, it implies that it's impossible to design one-way function which is definitely not true. So what have i missed?

> For every probabilistic polynomial-time algorithm $A'$, every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,
>
> $Pr\[A'(f(U\_n),1^n)\in f^{-1}(f(U\_n))\]\<\frac{1}{p(n)}$
>
> where $U\_n$ is random variable uniformly distributed over $\\{0,1\\}^n$

# Answer
> 10 votes
Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain *instructions* for computing the table, but then it would have to first execute them, and constructing an exponential size table takes exponential time.

On the other hand, your program could use a (supposedly) exponential amount of *uninitialized* space. Since its running time is polynomial, it only accesses polynomially many cells. You can implement memory access in such a way that if $T$ cells are ever accessed then $\tilde{O}(T)$ memory is used (exercise). The corresponding running time might become much worse, but still polynomial.

A third possibility are *non-uniform* computation models, which are popular in cryptography. Here the idea is that the algorithm is allowed to use a certain hard-coded amount of data which depends only on $n$. However, this data has to be polynomial size. This restriction comes from the interpretation of the model in terms of *circuits*. A machine running in polynomial time corresponds to circuits for every $n$ of polynomial size. If we now relax the constraint that all these circuits come from some single algorithm, then we get *non-uniform polynomial time*, which is the same computation with advice depending on $n$ of polynomial size (exercise).

The answer to the first question should obviate the second one. I would just mention that sometimes, instead of probabilistic polynomial-time algorithms, one considers (deterministic) polynomial size circuits.

# Answer
> -1 votes
1. Nope. In the standard framework in the cryptographic community, that kind of algorithm is usually not considered probabilistic polynomial-time: if necessary, we tweak the definition to ensure that it's not.

Technically speaking, in cryptography some folks have suggested we use the sum of the running time plus the size of the program's code as our measure of the time for the attack (you can think of it like this: if the code of the program is $k$ bits, it will take $k$ time steps just to read that code into memory before you start running it). If you hear someone say "running time" in cryptography, they might actually mean that sum. I think I first learned this technical detail from Phil Rogaway, but I have no idea whether he is first.

If you don't believe me, here's an example citation to the literature: you can look at Bellare et al, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences. See Section 2.2, Model of computation, where they write:

> We fix some particular Random Access Machine (RAM) as a model of computation. \[...\] When we speak of A's running time this will include A's actual execution time plus the length of A's description (meaning the length of the RAM program that describes A). This convention eliminates pathologies caused if one can embed arbitrarily large lookup tables in A's description.

Notice how they anticipated this corner case and chose definitions that avoid it from being problematic. With this definition, everything works out in a reasonable way, and your proposed algorithm (with an exponential-sized constant) is not a probabilistic polynomial-time algorithm.

Many cryptographers aren't always this careful about their definition of running time. It is very common to be a little sloppy and omit this kind of detail. Often, it doesn't matter. But when we start to talk about exponential-sized constants, this detail *does* matter, very much, and that's when it is essential to know about this technical detail, if you want to argue over formalisms.
2. Nope.

By the way, I stand by my answer on this, despite the (unexplained) downvote. Many folks are not aware that others in the research community have already anticipated this kind of subtlety, and few papers make a big deal of it, so I don't blame others for being unaware of the relevant definitions in the cryptographic community.

---
Tags: complexity-theory, terminology, polynomial-time, one-way-functions
---


# Question
Title: What is the difference between exhaustive search & combinatorial search?
I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper!

What is the difference between exhaustive search & combinatorial search ?

# Answer
> 11 votes
My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, in general exhaustive search is in the worst case linear in the size of the search space to be explored.

On the other hand, combinatorial search instead is a smarter kind of search, which usually exploits one or more pruning strategies to avoid testing all of the possible candidate solutions. In this case, you can safely discard some candidates (depending on the particular algorithm of course) and therefore you can save precious time. An example of combinatorial search is, for instance, branch and bound. Here, you may safely skip some subtrees since, depending on your particular optimization problem, you know in advance that no node within a certain subtree can yeld a better solution than the current one during the execution of your algorithm.

# Answer
> 7 votes
Exhaustive search is used mainly in two different context:

* When trying to find some $x \in X$ that satisfies a property $P$, the exhaustive search algorithm tries all $x \in X$ until it finds one satisfying property $P$.
* When trying to optimize some function $f$ over some domain $X$, the exhaustive search algorithm computes the value on $f$ on all of $X$, and then finds the optimum.

Combinatorial search isn't a standard term, so I don't know what your paper meant by it, but at any rate it encompasses a wider class of algorithms. For example, greedy and local search heuristics might be considered combinatorial search. A good example is the simplex algorithm for linear programming. What makes these algorithms combinatorial is that they operate with combinatorial - that is, discrete - objects. In contrast, interior-point algorithms for linear programming work with a continuous relaxation of the problem, and so they aren't considered to be combinatorial search.

# Answer
> 5 votes
An essential component of combinatorial algorithms is that a *combinatorial structure is utilized to speed up the search*. What does this mean?

* "combinatorial" -- it's discrete, and usually efficiently enumerable. In CS terms, think of any data structure.
* "structure" -- as opposed to just a set of things. Graphs, for instance, specify *relations* between elements of a flat set. This additional information may be useful for algorithms.

In this sense, you could say that exhaustive/brute-force search is the dumbest combinatorial search possible.

For example, you can improve the brute-force algorithm for Vertex Cover by noting that there is always an optimal vertex cover without nodes of degree one (for connected graphs with more than two nodes) -- we use both the structure of graphs and the problem for achieving the speedup.

See, for instance, Vertex Cover: Further Observations and Further Improvements by Chen et al. (2001); they give an exact algorithm for Vertex Cover that runs in time $O(kn + 1.3^n)$ (free copy) which is a huge improvement over the brute-force $O(2^n)$-time algorithm.

---
Tags: algorithms, terminology, search-algorithms
---


# Question
Title: Dividing a weighted planar graph into $k$ subgraphs with balanced weight
I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?

# Answer
If the graph is sparse, may be it's also bounded tree width. Then we can find the optimum cut by using dynamic programming for graphs of bounded treewidth1. To check whether it's a bounded tree-width or not there are some tools and you can use them. On the other hand, one (may be good) heuristic approach is finding maximum spanning tree. This can be done by negating edge weights and running Kruskal algorithm to find MST. Because the graph is sparse then heaviest cuts along this tree are not bad, also good cut for tree can be found by bottom up dynamic programming approach. (I think it's in factor of at most 5 with high probability in most cases).

1: I didn't think about it, but seems to be as usual.
> 1 votes

---
Tags: algorithms, graphs, optimization, weighted-graphs, partition-problem
---


# Question
Title: Completeness of formal definition of 'hardness on the average'
While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for simplicity.)

> **Definition : Hard on the average** :
>
> $h:\\{0,1\\}^\*\to \\{0,1\\}^\* $ is hard on the average if **there exists** a probabilistic polynomial-time algorithm $G$ such that
> for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s, Pr$\[A'(X\_n)=h(X\_n)\]\<\frac{1}{p(n)}$
>
> where $X\_n := G(1^n)$ is a random variable assigned the output of $G$.

My question is why the statement of the existence of qualified algorithm G is sufficient?

In other words, why the above definition gives a formal definition of 'hardness on the average' instead of following definition, which is more intuitive(?) to understand and more strict. Why is the above definition sufficient?

( Now I'm thinking that problem might occur when $G$ has only polynomial number of possible outputs, but if so, let's replace 'for any $G$' with 'for any $G$ which have exponentially many possible outputs' in following definition.)

> **(strong?) Def : Hard on the average** :
>
> $h:\\{0,1\\}^\*\to \\{0,1\\}^\* $ is hard on the average if **for any** probabilistic polynomial-time algorithm $G$ and for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s, Pr$\[A'(X\_n)=h(X\_n)\]\<\frac{1}{p(n)}$
>
> where $X\_n := G(1^n)$ is a random variable assigned the output of $G$.

Another question is that whether a following simpler definition is equivalent to original definition or not?

> **(simple) Def : Hard on the average** :
>
> $h:\\{0,1\\}^\*\to \\{0,1\\}^\* $ is hard on the average if for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s, Pr$\[A'(U\_n)=h(U\_n)\]\<\frac{1}{p(n)}$
>
> where $U\_n$ is a random variable uniformly distributed over $\\{0,1\\}^n$.

# Answer
> 4 votes
Hard on average is sometimes defined as in your third (simple) definition: a function $h$ is hard on average if on a uniformly random input, its output cannot be predicted by a ppt with more than a negligible probability. The first definition also captures the situation in which the "correct" input distribution is different. For example, consider the function $$ h(xy) = \begin{cases} H(x) & y = 0, \\ 0 & y \neq 0, \end{cases} $$ where $|x| = |y|$ and $H$ is some hard-on-average function (under the simple definition). The function $h$ is not hard on average under the simple definition, but it's hard on average under the more complicated definition. I'm not sure why we should be interested in such functions, but there's probably a reason. You'll have to continue reading and reflect when the more complicated definition is needed.

As for your second definition, it is far too strong. Consider for example what happens if $G$ always outputs the zero string. You are still capturing something - the halting function will still be hard - but there's no notion of "average". You have indeed anticipated this in your comment (though it only really applies in the non-uniform setting), but the resulting notion is still probably too strong.

The notion of hard on average came out of an attempt to proof the security of some notion. While it is indeed meant to capture some intuitive sense of hardness on average, the details were determined from some argument who used them, from some construction that obtained them; they're not arbitrary. These notions have been found to be useful, which is why they continue being used. Your suggested notion might be helpful as well, but the onus of proof is on you.

---
Tags: complexity-theory, terminology, cryptography, randomized-algorithms, average-case
---


# Question
Title: Why are all problems in FPTAS also in FPT?
According to the Wikipedia article on polynomial-time approximation schemes:

> All problems in FPTAS are fixed-parameter tractable.

This result surprises me - these classes seem to be totally different from one another. FPTAS characterizes problems by how easy they are to approximate, while FPT characterizes problems by their difficulty relative to some parameter. Unfortunately, Wikipedia (as of the time I'm asking this question) doesn't provide a citation for this.

Is there a standard proof of this result? Or is there a source I could consult to learn more about this connection?

# Answer
> 14 votes
There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an *fptas*1: an $\varepsilon$-approximation running in time bounded by $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There's a more general class $\mathrm{EPTAS}$ which relaxes the time bound to $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ - essentially an $\mathrm{FPT}$-like running time with respect to the approximation factor.

Clearly $\mathrm{FPTAS}$ is a subset of $\mathrm{EPTAS}$, and it turns out that $\mathrm{EPTAS}$ is a subset of $\mathrm{FPT}$ in the following sense:

> **Theorem** *If an NPO problem $\Pi$ has an* eptas, *then $\Pi$ parameterized by the cost of the solution is fixed-parameter tractable.*

The theorem and proof is given in Flum & Grohe \[1\] as Theorem 1.32 (pp. 23-24), and they attribute it to Bazgan \[2\], which puts it two years before Cai & Chen's weaker result (but in a French technical report).

I'll give a sketch of the proof, because I think it's a nice proof of the theorem. For simplicity I'll do the minimization version, just mentally do the appropriate inversions for maximization.

*Proof.* Let $A$ be the *eptas* for $\Pi$, then we can construct a parameterized algorithm $A'$ for $\Pi$ parameterized by the solution cost $k$ as follows: given input $(x,k)$, we run $A$ on input $x$ where we set $\varepsilon := \frac{1}{k+1}$ (i.e. we choose the approximation ratio bound $1+\frac{1}{k+1}$). Let $y$ be the solution, $\text{cost}(x,y)$ be the cost of $y$ and $r(x,y)$ be the actual approximation ratio of $y$ to $\text{opt}(x)$, i.e. $\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$.

If $\text{cost}(x,y) \leq k$, then accept, as clearly $\text{opt}(x) \leq \text{cost}(x,y) \leq k$. If $\text{cost}(x,y) \> k$, reject as $r(x,y) \leq 1+\frac{1}{k+1}$ as $A$ is an *eptas* and

$$ \text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} \> k $$

Of course you get the running time bound for $A'$ simply from $A$ being an *eptas*. $\Box$

Of course as Pål points out, parameterized hardness results imply the non-existence of any *eptas* unless there is some collapse, but there are problems in $\mathrm{FPT}$ with no *eptas* (or even *ptas*), so $\mathrm{EPTAS}$ is a strict subset of $\mathrm{FPT}$ (in the sense of the theorem).

## Footnotes:

1. An *fptas* (equivalently *eptas* or *ptas*) is an approximation scheme with the running time bounded as described above. The *class* $\mathrm{FPTAS}$ (equiv. $\mathrm{EPTAS}$, $\mathrm{PTAS}$) is the set of problems in $\mathrm{NPO}$ that have such a scheme.

\[1\]: J. Flum and M. Grohe, *Parameterized Complexity Theory*, Springer, 2006.
\[2\]: C. Bazgan. *Schémas d’approximation et complexité paramétrée*, Rapport de DEA, Université Paris Sud, 1995.

---
Tags: complexity-theory, reference-request, approximation, parameterized-complexity
---


# Question
Title: What is the meaning of this pseudo-code function?
While reading the paper Holistic twig joins: optimal XML pattern matching I came across the pseudo code for liststack algorithm. (available through google scholar)

A function in the algorithm confused me, since I can understand what it is supposed to do, but can't deconstruct the notation:

$\qquad \mathtt{Function}\ \mathtt{end}(q\mathtt) \\ \qquad\qquad \mathtt{return}\ \forall q\_i \in \mathtt{subtreeNodes}(q) : \mathtt{isLeaf}(q\_i) \implies \mathtt{eof}(T\_{q\_i})$

This function is supposed to return a single boolean result. It is supposed to be true when all lists associated to leaf nodes of a query pattern node are at their end. So true means there are no more nodes in the query pattern to process.

But what is the meaning of the set builder(ish?) notation here? Is it

$\qquad$ "for all subtree nodes of $q$ for which $\mathtt{isLeaf}(q\_i)$ is true $\mathtt{eof}(T\_{q\_i})$ is also true"

(which means that the list is at the end position)?

Or is it

$\qquad$ "for all subtree nodes of $q$, $\mathtt{isLeaf}(q\_i)$ implies $\mathtt{eof}(T\_{q\_i})$ is true"?

Is double arrow representing implies with its truth table?

As you can see, I'm having a bit difficulty in associating the colon and its precedence.

# Answer
Let us abstract what you have there to$ \renewcommand{\models}{\mathop{|\\!\\!\\!=}}\newcommand{\rmodels}{\mathop{=\\!\\!\\!|}} \newcommand{\semeq}{\models\\!\rmodels}$

$\qquad \mathtt{return}\ \forall x \in X.\\, P(x) \implies Q(x)$.

For evaluation, remember that

$\qquad A \implies B \quad \models\\!\rmodels \quad \lnot A \lor B$.

What this means is that you return true if and only if for all $x$ it is true that

$\qquad$"whenever $P(x)$ holds, then $Q(x)$ holds".

In your example, that translates to

$\qquad$ return true if all subtree nodes that are leaves have also reached the end of their respective files.

This is exactly what you expected, up to semantics of the `eof` function.

> It is supposed to be true when all lists associated to leaf nodes of a query pattern node are at their end.

Note that the only other way to apply operator precendences, i.e.

$\qquad \mathtt{return}\ \bigl(\forall x \in X.\\, P(x)\bigr) \implies Q(x)$,

does not make sense: in the term $Q(x)$, variable $x$ is not bound and there is no global interpretation shadowed by the $\forall$, so it's free. Hence, the term does not have a (fixed) truth value.
> 2 votes

# Answer
"Implies" in the English language indicates that there is room for subjectivity. But this is not standard English you're looking at. When you read A⟹B as "A implies B" in Discrete Mathematics, it is just another way to say, "If A is true, then B is true." Formally, this is called material implication.

So the two ways you thought to read it are the same - as far as Comp.Sci. goes. Left to right and minimal imagination it reads (out loud), "Return the truth of this assertion: For all q-sub-i that are members of subtreeNodes of q, isLeaf of q-sub-i implies eof of T-sub-sub-i."
> 2 votes

---
Tags: algorithms, terminology
---


title: Prove that the syntax is equivalent

text:
# Question
Title: Prove that the syntax is equivalent
I don't "see" why the following syntax is equivalent to the second

syntax1:

```
E -> E + T
E -> T

```

syntax2:

```
E -> T E'
E' -> + T E'
E' ->

```

(it is to avoid left recursion and I am not understanding why the solution works)

How do I mathematically prove that both syntax definitions are equivalent

# Answer
> 3 votes
An intuitive approach towards the difference is understanding that the productions of syntax #1 add new material to the left of existing symbols whereas those of syntax #2 do so on the right-hand side.

* syntax #1:

```
derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ n ] [n-1] [n-2]     [ 2 ] [ 1 ]`

```
* syntax #2 (step #`n` is the application of rule 3 and produces no terminal) :

```
derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ 1 ] [ 2 ] [ 3 ]     [n-2] [n-1]`

```

for a rigorous proof note that under both syntaxes, each derivation leads to an initial `T` followed by sequence of `+ T`. for the grammars at hand this can be proven by induction over the number of rule applications.

---
Tags: programming-languages, proof-techniques, parsers
---


# Question
Title: Constructing Tree (forest) from Ancestor function
**Question:**

Suppose I have a

* set of male people, and
* a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) would return true.

What are some fast algorithms for constructing a complete "family tree" by using only this information? (or "family forest" as not everyone may be related to a single common ancestor).

**Comment:**

This is not homework or from a book. It is derived from some issues I'm having coupling an adaptive finite element code to some blackbox mesh generation software, boiled down to the core problem and expressed in an analogy that shares the same mathematical structure. Right now I have a brute-force $O(n^3)$ method that seems horribly inefficient.

Thank you for any help.

**Results:**

I've implemented Gilles suggestion in Matlab and tested it. Here is the pseudocode, code, and unit test script. I release it all to the public domain.

*Pseudo-code*:

```
function buildAncestorForest
    roots = empty list
    for each person p
        roots = graft(p, roots)

    subfunction new_roots = graft(q, old_roots)
        descendents = empty list
        nondescendents = empty list
        for each person t in old_roots
            if q is an ancestor of t
                append t to descendents
            else
                append t to nondescendents

        if descendents is still empty
            q_is_incomparable = true;
            for each person t in old_roots
                if t is an ancestor of q
                    new_roots = old_roots;
                    new children of t = graft(q, old children of t)
                    q_is_incomparable = false;
                    break for loop
            if (q_is_incomparable)
                new_roots = append q to old_roots;
        else
            new_roots = append q to nondescendents;
            for each person t in descendents
                children of q = graft(t, children of q);

```

*Matlab code:*

https://github.com/NickAlger/MeshADMM/blob/master/buildAncestorForest.m

*Unit test script:*

https://github.com/NickAlger/MeshADMM/blob/master/test\_buildAncestorForest.m

# Answer
### Assumptions

We have a finite set $\mathscr{D}$ of persons and a relation $\prec$: $x \prec y$ means that $x$ is an **ancestor** of $y$. This relation has the following properties:

* Transitivity: if $x \prec y$ and $y \prec z$ then $x \prec z$ (the ancestor of my ancestor is my ancestor).
* Antisymmetry: if $x \prec y$ then $y \nprec x$ (I am not my ancestor's ancestor).
* Chain: if $x \prec z$ and $y \prec z$ then either $x \prec y$ or $x = y$ or $y \prec x$ (my ancestors form an ordered chain).

### Data structures

Let it be given a **set** data structure on which the following operations are defined:

* empty set
* add an element to a set
* **splitting** a set according to a property: iterate over the elements, compute a property on each element, and build two subsets, the set of elements for which the property is true and the set for which the property is false. This operation is assumed to be linear in the size of the set.

We will also use a **tree** data structure, in which each node contains a person and the set of its children. If $t$ is a tree, write $t\_R$ for the person at the root node and $t\_C$ for the set of children. A **forest** is a set of trees.

### Algorithm

We start with an empty forest and add persons one by one. At each step, the parent-child relationship in the forest is the parent-child relationship for the ancestor relation. We define a recursive function **graft** that inserts a tree into a forest.

**Input of graft**: a forest $F$, and a tree $s$ such that none of the elements of the tree is related to any of the persons in $F$. Let $x = s\_R$.

First, check whether $x$ is the ancestor of any of the existing persons: split the set $F$ according to the property $x \prec t\_R$ for $t \in F$. Let $C$ be the subset of $F$ consisting of descendants of $x$ (if the root of a tree is a descendant of $x$ then all elements are also descendants by transitivity), and $F'$ be the remaining subset. By antisymmetry, none of the persons in $C$ is an ancestor of $x$. None of the elements of $s\_C$ are related to any of the persons in $C$ by assumption. Let $u$ be the tree where the root person is $x$ and the set of children of the root is $C \cup s\_C$.

By the chain assumption, $x$ can have ancestors in at most one of the trees in $F'$. Iterate over the trees $t \in F'$, and determine which one if any has an ancestor of $x$ at its root (this is a splitting operation where one of the sets is guaranteed to contain at most one element).

**Output of graft**:

* If no tree in $F'$ has an ancestor of $F'$ at the root, then add the new node to the remaining forest: return $F' \cup \\{u\\}$.
* If there is a tree $t$ in $F'$ such that $t\_R \prec s$, then we need to insert the new element with its descendants into that tree. Let $G = \text{graft}(t\_C, u)$. Return $(F' \setminus \\{t\\}) \cup \\{t'\\}$ where $t'$ has $t\_R$ at the root and $G$ for children.

**Main algorithm**: Start from an empty forest, and iteratively graft the persons in $\mathscr{D}$ (grafting a person means grafting the tree with this person at the root and no children).

### Correctness

From the remarks of this algorithm, it should be easy to prove that the recursive calls to graft are valid (all relatives of the nodes in the tree being inserted are inside that tree), and that $x$ is an ancestor of $y$ in the tree iff $x \prec y$.

### Complexity

$\textrm{graft}(F,t)$ performs at most $2 n$ ancestor tests, where $n$ is the number of persons in $F$: one test per root of $F$, one test per root that is not a descendant of the new node, and tests performed by the recursive call if any which applies to a subset of $F$ not including any of its roots. The complexity of other operations is linear in the number of ancestor tests performed.

Therefore the forest construction algorithm performs at most $2 + 4 + 6 + \ldots + 2(n-1) = n (n-1)$ ancestor tests where $n$ is the total number of persons. In fact, it is easy to see that it never performs the same test twice. The overall complexity is therefore $O(n^2)$.

In the worst case, all possible $n (n-1)$ tests are performed. This happens when no two persons are related, and it is unavoidable in this case.
> 5 votes

# Answer
what follows is a somewhat informal description of an $O(n^2)$ algorithm:

**main idea:**

we build a dag $G=(V,E)$ expressing ancestor relations and subsequently thin it into a family tree. the dag nodes will be the persons involved, edges shall represent ancestor relationships ($(u,v) \in E \to \text{$u$ is ancestor of $v$}$). let $n = |V|$.

**algorithmis steps**

1. step 1:
build the transitive closure of the ancestor relation by iterating over all pairs of candidates and adding $(u,v)$ to $E$ iff `isAncestor(u, v)`. complexity: $O(n^2)$.
2. step 2:
determine the source nodes in the dag. the source nodes represent the minimal elements in the ancestor relation seen as a partial order. note that there will be exactly 1 source node per connected component since we consider only ancestors among the same sex. thus all but 1 edge ending at any given node $v$ are actually forward edges introduced by the transitive closure of the underlying family tree. this step can actually be implemented as a part of step 1 by counting incoming edges for all visited nodes, adding any node $v$ with $indeg(v) = 0$ to a heap while deleting any node with $indeg(v) \> 0$ from that heap. after completion of step 1, the heap only contains nodes with $indeg(\cdot) = 0$ ie. all source nodes. as each node is at max once inserted into and once deleted from the heap, this step contributes $O(n \\; log\\,n)$.
3. step 3:
perform a depth first search on tha dag starting at the source nodes. if a node is visited for the first time, record the distance from the current source node and the immediate predecessor on the current dfs root path. if a node has been visited and if the current root path length is greater than that recorded with the node, set length and immediate predecessor to the values from the current dfs path and delete the recorded edge from the dag. after the dfs has finished the dag has been reduced to a family forest. as every edge is visited at max once, complexity is $O(E)$. this step works because the dag does not contain crossing edges. therefore for any given pair $(u,v) \in V$ there will never be 2 different paths from $u$ to $v$ of equal length.

in summary:

$O(n^2) + O(n \\; log\\,n) + O(E) = O(n^2)$
> 2 votes

---
Tags: algorithms, trees
---


# Question
Title: Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper
Given a list of pairs $(a\_1,b\_1),\ldots,(a\_n,b\_n)$, where all $a\_i \geq 0$ and all $b\_i \> 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization problem of finding the optimal combination of pairs,

$$I^\* = \hbox{argmax}\_I F(\sum\_{i \in I} a\_i) / G(\sum\_{i \in I} b\_i)$$

where $F,G$ are given increasing positive functions for positive inputs.

I have found a class of functions where there is a fast solution, namely $F(x) = x + A$ and $G(x) = (x + B)^\beta$ where $A,B \geq 0$ and $0 \leq \beta \leq 1$. In this case, the optimal solution can be found by sorting all pairs $(a\_i,b\_i)$ in decreasing order according to $a\_i/b\_i$, and then trying the first $k$ pairs in sorted order for all $k$ and choosing the best solution, and this gives the optimal solution. (This is an example of linear subset scan optimization.)

Now I want to know, if there a general class of functions $F,G$, ideally defined by abstract properties, where this linear subset scan approach works, where pairs are sorted either according to $a\_i/b\_i$ or perhaps sorted according to $H(a\_i,b\_i)$ where $H$ depends on $F,G$? This could be a question where someone has a new insight and proof, or simply someone has seen something like this in the literature. At any rate, I feel like the class of $F,G$ I stated where I have a proof is perhaps not the most general possible, and I'm missing some key abstract property that makes the linear subset scan work.

# Answer
> 1 votes
If I wanted to solve this problem, I wouldn't limit myself to the linear subset scan algorithm: I would consider other algorithms as well.

For instance, here is one approach that might be effective in many cases. If $\theta$ is a non-negative real number, define

$$h(\theta) = \max \left\\{\sum\_{i \in I} a\_i : \sum\_{i \in I} b\_i \le \theta\right\\}.$$

Note that

$$F(I^\*)/G(I^\*) = \max\_\theta F(h(\theta))/G(\theta).$$

So, define $f:\mathbb{R}\to \mathbb{R}$ by

$$f(\theta) = F(h(\theta))/G(\theta).$$

With these definitions, our goal is to find the maximum of $f$.

Also, note that we can compute $h(\theta)$ for any given $\theta$ of our choice, using integer linear programming. (In principle, there is no guarantee that ILP will run in polynomial time, but in practice, I bet it may often be possible to compute this reasonably efficiently.) Your linear subset scan algorithm (sort the $a\_i,b\_i$ by decreasing value of $a\_i/b\_i$) is a good heuristic for efficiently computing an approximate solution to this ILP (computing a lower bound on $h(\theta)$), but as far as I can see, there is no guarantee that it will actually find the true optimum value.

This means that we can also compute $f(\theta)$ for any given $\theta$ of our choice.

So, we have a function $f$ in one real variable, to which we have black-box access, and we want to maximize it. Now a reasonable approach is to apply any standard algorithm for black-box mathematical optimization, e.g., grid search followed by hill-climbing, coordinate descent, gradient descent, Newton's method, or other methods.

It is also possible that some suitable criterion on $F,G$ might imply that $f$ has a nice property that makes it easy to maximize (e.g., it is increasing or something), and which might imply that your linear subset scan algorithm is a good approach. I have not thought about that carefully, but you might look at that direction.

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Recommended readings for Probability theory applied to algorithms
Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start? Thanks in advance!

# Answer
The best intro probability book ever written is available online from MIT open courseware.

> Alvin W. Drake; *Fundamentals of Applied Probability Theory*, McGraw-Hill, 1967.

Old editions of standard textbooks are usually easy to get cheap. You might try Sheldon M. Ross; *A First Course in Probability*, a 5th edition from 1997 can be found for less than \\$5 at Abe Books (or Powell's, or Zubal). Another old standard is Jay L Devore; *Probably and Statistics for Engineering and the Sciences*, with similarly low prices for old used editions. (This is the secret of the textbook industry: they churn out new editions with slightly different homework problems every couple of years, so that the students need to buy new editions for way too much money. The result is that if you want a book but don't need it for the homework assignments you can get it for next to nothing.)

Finally: there are the recommendations from James M. Cargal's page of *Recommended Books in the Mathematical Sciences*. I've used his recommendations as a starting point for several investigations into areas of mathematics where I wanted remedial help.
> 2 votes

# Answer
I highly recommend Mitzenmacher and Upfal, Probability and Computing.

It has almost all the background needed for a beginning graduate student to start in probabilistic algorithms and analysis, and is clearly written, nice examples, etc.
> 3 votes

---
Tags: algorithms, algorithm-analysis, probability-theory
---


title: Detecting cycles in undirected graph

text:
# Question
Title: Detecting cycles in undirected graph
I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, b, d}, {b, c, d}.

I have read this and I think that when the iterative pseudocode from Wikipedia finds a back-edge then I can say the graph has a cycle. But I don't know how to find out which vertices/edges the cycle consists of.

Can you please help with an algorithm which would take a graph as input (or the information from DFS) and output list of lists describing the cycles?

# Answer
You're almost there, but when you find a back edge you already have all the information you need to describe the cycle it forms. Also, there's a bit of a complication where you might find duplicate cycles. Or you might not. Do you consider {A, B, C} to be the same cycle as {C, B, A}? What about {B, C, A}? Depends on what you're doing, but let's assume they're equivalent.

So you've got a graph you're DFSing. illustration http://imageshack.us/a/img687/1598/tjd.gif.

And you go down one branch and detect a few cycles. Cool. illustration http://imageshack.us/a/img14/9295/4bo.gif

But you haven't explored all possibilities, so you unwind the stack and take the next branch. You find some more cycles. Groovy. illustration http://imageshack.us/a/img818/3851/t69.gif

The adventure continues. You go down another path and find another cycle. Good. illustration http://imageshack.us/a/img543/48/c5mb.gif

No, wait. BAD. You've got two equivalent cycles. And when you unwind to having only explored A-B, and take A-B-E this time, that's going to reveal more duplicates. You'd need a way to get rid of those, if they are a problem in your application.
> 7 votes

# Answer
Make sure that you understand what DFS is doing and why a back-edge means that a graph has a cycle (for example, what does this edge itself has to do with the cycle). If you truly understand why the connection between back-edges and cycles, it should not be difficult to understand how the cycle can be found from the DFS, and then to write out an algorithm employing this knowledge. Good luck!
> 4 votes

---
Tags: graphs
---


title: NP-Hardness reduction

text:
# Question
Title: NP-Hardness reduction
I have a problem $\Pi\_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi\_2$ and a polynomial time reduction $f()$ from instances of $\Pi\_2$ to $\Pi\_1$ such that $I\_2$ is an Yes-instance of $\Pi\_2$ iff $I\_1=f(I\_2)$ is an Yes-instance of $\Pi\_1$.

What if I find a (constant sized) family of reductions $f\_i()$ such that $I\_2$ is an Yes-instance of $\Pi\_2$ iff at least one $f\_i(I\_2)$ is an Yes-instance of $\Pi\_1$? Is this enough? Is there a way of translating this one in the "classical" definition? How to formalize this?

I know that in the second situation I can say that I can't solve $\Pi\_1$ in polynomial time unless P=NP, but I'm no sure that is equivalent of saying that $\Pi\_1$ is NP-hard.

# Answer
NP-hardness is usually defined using many-to-one reductions, for various reasons, for example to separate NP from coNP (there was some question about it either here or in cstheory). What you're describing is a specific case of more general Turing reductions, which is more common in classical recursion theory, and it is natural since it has the consequences you mention. Unfortunately, the definition of NP-hardness requires a many-to-one reduction.
> 6 votes

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


# Question
Title: No of ways in which n indistinguishable items can be placed in m indistinguishable boxes
This problem is the same as number of ways to partition n into exactly m parts.

The recurrence given in Wikipedia has

p(n,k) = the number of partitions of n using only natural numbers ≥ k

How to find no of partitions of n which has exactly k non-zero parts? Is there a recurrence relation to solve this?

# Answer
The number of partitions of $n$ with exactly $k$ parts is the coefficient of $x^n y^k$ in the generating series $$ \prod\_{l=1}^\infty \frac{1}{1-x^ly}. $$ Asymptotically, this is probably $\Theta\_k(n^{k-1})$ (i.e. the constant depends on $k$).

The number of partitions of $n$ in which each part is at least $k$ is $$ \prod\_{l=k}^\infty \frac{1}{1-x^l}. $$ Asymptotically, my guess is that it's $\Theta\_k(p(n))$, where $p(n)$ is the number of *all* partitions of $n$.

We can write a recurrence relation for $p(n,k)$: $p(0,k) = 1$ and for $n \> 0$, $$ p(n,k) = \sum\_{t \leq \lfloor n/k \rfloor} p(n-kt,k+1). $$
> 2 votes

---
Tags: combinatorics, discrete-mathematics
---