19.5. Proof of Correctness

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about the choices the algorithm makes.

2. 2.

   Why is it important to prove correctness for an algorithm?

   Hint

   Consider the implications of an unproven algorithm.

3. 3.

   What primary strategy is used in greedy algorithms?

   • Maximize overlaps
   • Make local optimal choices
   • Random selection

   Hint

   Think about the goal of optimization.

4. 4.

   True or False: Greedy algorithms always guarantee an optimal solution.

   • True
   • False

   Hint

   Consider the definition of 'greedy'.

5. 5.

   Create a complex interval scheduling scenario with at least 10 overlapping intervals and prove whether the earliest finishing time strategy achieves an optimal solution.

   Hint

   List the start and end times of each interval to visualize overlaps.

6. 6.

   Demonstrate how varying the selection criteria (like shortest versus longest interval) affects the overall optimal solution in interval scheduling using at least three examples.

   Hint

   Data visualization can greatly help in illustrating differences.