Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:holmesr:section_4.2 [2018/02/27 03:48] – created holmesr | courses:cs211:winter2018:journals:holmesr:section_4.2 [2018/02/27 04:07] (current) – holmesr | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Section 4.2 Scheduling to Minimize Lateness ====== | + | ====== Section 4.2 Scheduling to Minimize Lateness: an Exchange Argument |
| This problem gives a set of requests which all may begin at time s and must use the resource for a specific interval of time. The difference from the previous problem is that instead of a start and end time, these requests only come with a deadline before which they must be completed. These criteria allow us a few possible rules by which we may define the greedy algorithm. | This problem gives a set of requests which all may begin at time s and must use the resource for a specific interval of time. The difference from the previous problem is that instead of a start and end time, these requests only come with a deadline before which they must be completed. These criteria allow us a few possible rules by which we may define the greedy algorithm. | ||
| Line 8: | Line 8: | ||
| The rule we should use is scheduling the intervals with the earliest deadlines first. The algorithm will schedule one task as soon as the previous one is completed, and so there will be no idle time. Additionally, | The rule we should use is scheduling the intervals with the earliest deadlines first. The algorithm will schedule one task as soon as the previous one is completed, and so there will be no idle time. Additionally, | ||
| + | |||
| + | Since there is an optimal schedule that has no inversions and no idle time and all schedules with no inversions and no idle time have the same maximum lateness, the schedule produced by the greedy algorithm which will have no inversions and no idle time will be an optimal schedule. | ||
| + | |||
| + | This algorithm will run in O(n log n) time, since the costliest step in the algorithm will be sorting the intervals by deadline. | ||
| + | |||
| + | This was a dense section which took me a while to get through due to the level of technicality and specification of some of the proofs. It required a good deal of attention and focus at some points, including the proof for statement 4.9. | ||
