20.2. Greedy Strategies

Try these first

1. 1.

   Define what a 'greedy algorithm' is.

   Hint

   Think about how it relates to local choices.

2. 2.

   What is 'lateness' in job scheduling?

   Hint

   Consider how this relates to deadlines.

3. 3.

   What is the primary goal of minimizing lateness in job scheduling?

   • To complete all jobs as quickly as possible
   • To reduce maximum lateness across all jobs
   • To prioritize the longest jobs

   Hint

   Consider what it means to arrive before deadlines.

4. 4.

   True or False: The shortest job first strategy is guaranteed to minimize lateness.

   • True
   • False

   Hint

   Think of how choices impact overall outcomes.

5. 5.

   Consider three jobs: Job A (3 hours, deadline 9), Job B (5 hours, deadline 5), and Job C (2 hours, deadline 7). Arrange them using the deadline-first approach and calculate the maximum lateness.

   Hint

   Pay attention to how each job’s completion time relates to its deadline.

6. 6.

   Create a counterexample where the slack-first strategy leads to higher lateness than the deadline-first method.

   Hint

   Analyze job lengths and deadlines closely.