Greedy Algorithm: Homework Statement, Questions & Tutorials

[athrun200]

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 into 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.

 

[KataKoniK]

Thank you for your questions. I understand your concerns about the optimality of the methods in part(a) and the calculation of time needed in part(b).

Regarding your first question, your counter examples seem valid and it is important to consider all possible scenarios when evaluating the efficiency of an algorithm. However, it is also important to note that in real-life situations, there may be constraints or limitations that may make one method more practical or feasible than the other. Therefore, it is important to carefully analyze the problem and consider all factors before determining the optimal method.

For your second question, your approach of decomposing the greedy algorithm into different steps is a good start. However, I would suggest considering the worst-case scenario in which all events have time crashes and need to be discarded in step 3. This would result in a total of n^2 comparisons in steps 1 and 3 combined. As for step 4, you can assume that i events have been discarded and repeat the same process with the remaining events, resulting in a total of n^2-n comparisons. Overall, the time complexity of the greedy algorithm would be O(n^2).

I hope this helps clarify your doubts. If you have any further questions or concerns, please do not hesitate to ask. As scientists, it is important to constantly evaluate and improve our methods and approaches, so your questions are valuable in this process.