Chapter 4

My notes on Chapter 4 readings

• A greedy algorithm uses a sum of local optimizations to make a global optimization.
• We can show optimality by showing that greedy stays ahead or by making an exchange argument to show that the greedy solution and the optimal solution are equivalent.
• We can find a greedy algorithm to solve interval scheduling problems
  • We solve this by taking all requests, and, while there still exist requests to be processed, choose a request W with the smallest finishing time, add it to our schedule, then delete from the requests all requests incompatible with W.
• We can complete this in O(n*log(n)) time
• We can extend this to fulfill interval partitioning, in which the number of resources needed is at least the depth of the set of intervals - that is, the number of intervals overlapping.
  • We can solve this by sorting intervals by start time, then for each interval, either placing it in the first resource available for it, or allotting a new resource if none is available.
• This section wasn't very interesting to read. 6/10.

• Say we want to schedule jobs with start and end times and deadlines so that the maximum lateness for any job is minimized.
• We can't always do what we've done for the previous jobs, because in that example we just did as much as we could and here we have to do everything.
• We can't do jobs in increasing order of length, or of slack time. Instead, we order by deadline!
• We prove this by exchange argument: any optimal solution that isn't the greedy solution must have some sort of inversions! We un-invert those, get rid of lack time, then we have our greedy solution.
• Not that interesting a section, kind of overly wordy. 5/10.