This page is archived

• 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.