This is an old revision of the document!
Table of Contents
Chapter 4
4.1: Interval Scheduling: The Greedy Algorithm Stays Ahead
- A greedy algorithm is the optimum algorithm for a given problem
- Starts with a simple rule then continues using that rule to solve the rest of the equation.
- In this particular problem the greedy algorithm is the algorithm which produces the fewest conflicts between intervals.
- To prove that an algorithm is optimal one must prove that the greedy algorithm always “stays ahead”
- These proofs are on pages 120 to 121
- Of course there exist certain circumstances presented by outside factors that can affect the optimality of a greedy algorithm
4.2: Scheduling to Minimize Lateness: An Exchange Argument
- This is a different take on the scheduling algorithm describe above
- Instead of a definite start and end time these tasks just have deadlines
- The optimal way to schedule this is one in which the tasks are sorted in increasing order of deadlines
