- Aug 24: Interval Scheduling (Sections 1.2, 4.1): Problem Definition and motivation, brute force approach, various greedy approaches with bad examples for some, a successful greedy approach with a sketch of why it works.
- Aug 26: Proof of correctness of greedy approach for interval scheduling,
an initial implementation with quadratic running time, an improved n log n
implementation, quiz.
- Aug 31: Material corresponding to Section 2.2
- Sep 2: Material corresponding to Section 2.4
- Sep 7: The subsection "A Related Problem: Scheduling All Intervals" in Sec 4.1
- Sep 9: Completion of previous discussion, then Section 4.2 of book: scheduling to minimize lateness, quiz
- Sep 14: Completion of analysis of earliest deadline first algorithm for scheduling to minimize lateness, then Section 4.8 on Huffman coding
- Sep 16: Huffman coding: analysis of optimal tree
- Sep 21: Huffman coding algorithm developed and analyzed. Implementation issues.
- Sep 23: Divide and Conquer. The mergesort recurrence and Counting Inversions (Sec 5.3 plus a bit of 5.1)
- Sep 28: Closest Pair, Section 5.4
- Sep 30: Polynomial multiplication and convolutions (Section 5.5 and the discussion on convolutions in Section 5.6 but not the FFT algorithm)
- Oct 5: Above topic continued.
- Oct 7: Randomized algorithms: Probability spaces, events, contention resolution Protocol, Section 13.1
- Oct 12: Analysis of Contention Resolution Protocol
- Oct 14: Midterm
- Oct 19: A randomized algorithm for the fraud detection problem from HW3, randomized algorithm for global min-cut
- Oct 21: Analysis of global min-cut, analysis of randomized quicksort.
- Oct 26: Algorithm development using recursive thinking, and its application to the fraud detection problem from midterm, and to weighted interval scheduling and weighted interval covering as preparation for dynamic programming.
- Oct 28: Dynamic programming for weighted interval scheduling, Sections 6.1 and 6.2
- Nov 2: Dynamic programming for weighted interval covering. This is not from the text but I have posted notes on icon.
- Nov 9: Dynamic programming for the Knapsack problem (Section 6.4) and
a problem on finding the maximum sum in a contiguous subarray (notes posted in
icon)
- Nov 11: Guest lecture on edit distance, its motivation, and computation.
- Nov 16: Introduction to reductions (Chapter 8), notes posted in icon.
- Nov 18: The boolean satisfiability problem and motivation for it. The
3CNF-SAT problem. The notion of an efficient verifier, and efficient verifiers
for various problems (Chapter 8).
- Nov 30: Review of efficient verifiers, P, NP, and the notion of
NP-completeness, the first NP-complete problem 3CNF-SAT, obtaining
NP-completeness of Independent Set from NP-completeness of 3CNF-SAT
(Slides for this lecture on icon).
- Dec 2: NP-completeness of vertex cover, set cover, and 3-coloring.
- Dec 7: The two solved exercies in chapter 8
- Dec 9: A sample final distributed, discussion of a HW 7 problem.