Recitation 8
Recitation notes for the week of October 23, 2017.
Midterm Solutions
Note to TA
Walk through the solutions to questions on both the mid-terms. Only do an quick overview first. If someone asks for more details, present a more detailed version of the solution (e.g. this might be needed for say Q 1(a), 1(g), 1(h) and 2(c)).
Greedy Algorithms
Here are the basic "tenets" of greedy algorithms:
- Build final solution piece by piece.
- Being short sighted on each piece (can't see the future and don't care).
- Never undo a decision.
Interval Scheduling
The Problem
Input: $n$ intervals, $s_i$ is the start time of each interval, $f_i$ is the finish time for each interval.
Output: valid schedule with the maximum number of intervals.
A valid schedule means that it has no conflicts and intervals $i$ and $j$ conflict if they overlap in time.
Exercise 1
Go over the four possibilities of $i$ and $j$ overlapping.
Possible Algorithms
Talk about different ways to sort the intervals:
- Shortest interval first. Counterexample of suboptimal: \[____________ ____________\] \[ ________ \]
- Earliest start time first. Counterexample of suboptimal: \[ ___ ____ ___ ____\] \[_________________________________\]
- Conclude with the correct answer: Sort all of the intervals by finish time and go over example on board. Ex. Page 119 of textbook.
In case of extra time
If there is extra time, go over the minimizing maximum lateness problem.