# Greedy Algorithm

1. Oct 3, 2011

### athrun200

1. The problem statement, all variables and given/known data
See photo 1 for question
photo 2 for tutorial

2. Relevant equations

3. The attempt at a solution
I have 2 questions

1. It seems the 2 methods in part(a) are not optimal.
But I don't know if my counter examples are correct.
If we use the (1) algorithm, that in my drawing 1, it choose event A only. However, choosing B, C and D is better.
If we use (2), that my second drawing shows it will choose either C or B. However, choosing A and D is better.

2. In part b, how to calculate the time needed?
For me, I decompose the greedy algorithm in to 4 steps.(See the tutorial sheet to see which 4 steps)

I know that step 1 takes n times because it compare n events.
step 2 doesn't take time because it choose the event only.
step 3 takes n times again since it compares n events to see which one has time crash and then discard them.

I think step 4 is the tricky. It repeat step 3 with fewer events. I assume i events have been discarded, but I am sure if I can do this.

File size:
50.4 KB
Views:
81
File size:
48.6 KB
Views:
81
File size:
45.9 KB
Views:
72