Greedy Algorithm

  • Thread starter athrun200
  • Start date
  • #1
277
0

Homework Statement


See photo 1 for question
photo 2 for tutorial


Homework Equations





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.
 

Attachments

  • question.PNG
    question.PNG
    50.4 KB · Views: 438
  • tutor2.PNG
    tutor2.PNG
    48.6 KB · Views: 453
  • a.jpg
    a.jpg
    45.9 KB · Views: 436

Answers and Replies

Related Threads on Greedy Algorithm

Replies
4
Views
3K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
2
Views
7K
  • Last Post
Replies
5
Views
971
Top