Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Greedy Algorithm

  1. Oct 3, 2011 #1
    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.

    Attached Files:

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?