Greedy Algorithm2

• What did we do for activity selection?

1. Determine the optimal substructure.
2. Develop a recursive solution.
3. Prove that at any stage of recursion, one of the optimal choices is the greedy choice.
   Therefore, it’s always safe to make the greedy choice.
4. Show that all but one of the subproblems resulting from the greedy choice are empty.
5. Develop a recursive greedy algorithm.
6. Convert it to an iterative algorithm.

 

 

Regarding optimal structure when applying it to greedy algorithm :
• Just show that optimal solution to subproblem and greedy choice
-> optimal solution to problem.