Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a greedy algorithm like the following:

procedure selection($s_1, s_2, ...,s_n$, $f_1,f_2,...,f_n$)
S = (empty set)
for j = 1 to n
    if task j is compatible with S
    S = S U {j}
return S

S = tasks selected by algorithm above. A = tasks selected by optimal algorithm.

Thus, the greedy algorithm is optimal if |S| is always equal to |A|. How can I use induction to show that this is true? Would my base case just be that both trivially sort 1 task?

NOTE: $s_1,s_2,...s_n$ and $f_1,f_2,...,f_n$ signify start and end times, respectively, for the tasks.

share|improve this question
    
This depends on the problem, you need to provide more context and details for the question to be meaningful. –  dtldarek Dec 4 '12 at 21:37
    
@dtldarek I think he's referring to the Activity Selection Problem –  Haile Dec 4 '12 at 22:14
    
@Haile That was also my guess (especially after the note had been added), however, understanding the question is an important part of understanding the solution, and there is still a crucial piece missing: what we are optimizing? –  dtldarek Dec 4 '12 at 22:45
    
@dtldarek, I'm sorry, the number of tasks is being optimized such that they are all compatible with S. So S, at the end of this algorithm, should hold the largest number of tasks possible, such that no two tasks "overlap," if it is to be the most optimal algorithm for this problem. –  user1038665 Dec 4 '12 at 22:53
add comment

1 Answer

up vote 1 down vote accepted

Well, I don't want to be picky, I'll just assume that the tasks given are sorted with regard to their ending times, i.e. $f_i \leq f_{i+1}$ (or you could just sort the input).

The first thing you would like to do is to decide why you can use induction. Does the problem contains similar, but smaller subproblems? In our case it does, but it is not clear from the code you have given, i.e. you would need to argue why running last $n-1$ runs of the loop is similar to runing them all (this is kind of trivial, but tedious if it were to be done formally).

To make it easier, consider the following rewrite:

procedure selection($s_i, s_{i+1}, ...,s_n$, $f_i,f_{i+1},...,f_n$)
if n < i
  return (empty set)
else
  j = i+1
  while task j is incompatible with S and j <= n
      j = j + 1
  return {i} U selection($s_j, s_{j+1}, ..., s_n$, $f_j, ..., f_n$)

This recursive version gives a clear indication where the subproblem structure is, and it is much easier to work with. For example you can read-off the base case: it is for an empty input (the first if-clause). You can also guess what your assumption should be: selection works for all $|S| \leq n-j+1$, but you don't know $j$, so it has to work for all $|S| \leq n-1$. All that is left, is to observe that $f_i$ has to be smaller or equal of the finish time of the corresponding task in the optimal solution. From there follows that the remaining set $s_j, \ldots, s_n$ is the largest possible worth considering, and the rest is implied by the step's assumption.

In my timezone it is getting late, so please consider this a huge hint, try to work out the rest on your own and leave a comment whether you succeeded; if not, I shall complete this answer tomorrow.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.