19.1. Design and Analysis of Algorithms

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about local vs. global decisions.

2. 2.

   Which strategy does our greedy algorithm use for interval scheduling?

   Hint

   What does 'earliest' help achieve?

3. 3.

   What does a greedy algorithm rely on to make decisions?

   • Future possibilities
   • Initial parameters
   • Local criteria

   Hint

   Think about how it makes choices without looking back.

4. 4.

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

   • True
   • False

   Hint

   Have we tested this in our discussions?

5. 5.

   Given the bookings [(0, 5), (1, 3), (2, 4), (3, 7), (5, 8)], find the optimal set of bookings and explain your choice.

   Hint

   Remember to select those that leave the most room for future choices.

6. 6.

   Analyze the impact if the intervals were sorted in the wrong order initially. How would that affect the greedy algorithm's performance?

   Hint

   Consider the sequence of choices and their effects on possible selections.