19.3.3. Greedy Strategies

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about how it approaches optimization.

2. 2.

   Give an example of a greedy algorithm.

   Hint

   Consider algorithms used for pathfinding or tree construction.

3. 3.

   What does a greedy algorithm prioritize?

   • Maximizing overall results
   • Minimizing local choices
   • Making locally optimal decisions

   Hint

   Recall the definition of greedy in algorithms.

4. 4.

   True or False: Prim's algorithm is used for finding the shortest path between two vertices.

   • True
   • False

   Hint

   Think about the specific problem each algorithm solves.

5. 5.

   Given a list of intervals, develop a greedy algorithm to determine the maximum number of non-overlapping intervals and illustrate with an example.

   Hint

   Think about how sorting creates clear choices.

6. 6.

   Prove that the greedy strategy of choosing intervals by earliest finish time always produces the maximum number of non-overlapping intervals. Use an example to illustrate your proof.

   Hint

   Visual representations can help articulate the induction process.