The Midterm exam is in class on Oct 14, and will be based on what we
covered about Greedy Algorithms (Chapter 4) and Divide and Conquer
- Greedy Algorithms: Topics include Interval Scheduling, Interval
Partitioning, Scheduling to Minimize Lateness, Huffman Coding, and
the homework problems we solved. We will not be asked to give proofs
of optimality, though this was a big part of the lectures. The questions
will be on the above topics or variants, asking for counterexamples
or algorithms that always produce an optimal solution.
- Divide and Conquer: In the lectures, we covered MergeSort, Counting
Inversions, Closest Pair, and Polynomial Multiplication. These were
meant to get us to appreciate the power of divide-and-conquer. The
exam will not directly ask about the Closest Pair and Polynomial
Multiplication algorithms. We are more interested in whether we can
apply the divide-and-conquer paradigm in nontrivial ways, and so the
questions will be either variants of the homework problems or some
simple new ones.