19.5.2. Conclusion of Optimality

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about how it approaches decision making.

2. 2.

   Name one algorithm that follows a greedy approach.

   Hint

   Consider what you learned about minimum spanning trees.

3. 3.

   What is one key characteristic of greedy algorithms?

   • They always guarantee the best solution.
   • They make local decisions.
   • They require global knowledge.

   Hint

   Consider how they operate step-by-step.

4. 4.

   True or False: Prim’s algorithm is used to find the shortest path in graphs.

   • True
   • False

   Hint

   Remember the distinction between paths and trees.

5. 5.

   Design an example where the use of a greedy algorithm fails to yield the optimal solution. Describe the algorithm and the scenario.

   Hint

   Think about job selection in terms of maximizing rewards versus minimizing time.

6. 6.

   Using the interval scheduling algorithm, outline the procedure step-by-step for a given set of time intervals. Explain the outcome.

   Hint

   Keep track of finish times at each stage.