This is a log of the topics we cover in each lecture. A link to notes will be posted in some cases.

• 01/18: The interval scheduling problem from Section 1.2 and 4.1. This is our introduction to the course as well as the topic of greedy algorithms. Here are some notes from a previous offering.
• 01/20 and 1/25: We cover the material in Sections 2.1, 2.2, and 2.4 of the book. I highly recommend reading these sections from the book; some of this should be a review of what you have already seen. Here are some notes for part of the 01/20 class.
• 02/01: Bipartite matching (page 14) and independent set (page 16), two problems related to interval scheduling. The Section "A Related Problem: Scheduling All Intervals" on page 122.
• 02/03: Scheduling to minimize lateness, from Section 4.2 of the book.
• 02/08: The Huffman Coding algorithm (4.8), a review of Dijkstra's algorithm for shortest paths (4.4), and minimum spanning tree algorithms (4.5). In all these cases, we will not justify why the algorithms work. These are important examples of greedy algorithms.
• 02/10: Divide and Conquer (Chapter 5). The MergeSort algorithm and the problem of counting inversions (5.3). Problem Statement of Exercise 3.
• 02/15: A Divide-and-Conquer Solution to Exercise 3; Notes for this can be found by clicking on "Content" tab on icon course web page. Integer Multiplication (Section 5.5)
• 02/17: Integer Multiplication Continued. The algorithm for finding the closest pair of points (Section 5.4).
• 02/22: Discussion of closest pair algorithm completed. Introduction to dynamic programming, via weighted interval scheduling (Section 6.1).
• 02/24: Weighted Interval Scheduling algorithms completed.
• 03/01: Weighted Set Cover on the Line. This is not from the text, but the notes can be found by clicking the "Content" tab on icon web page.
• 03/03: The Knapsack Problem (Section 6.4)
• 03/08: A segmentation problem that is related to the one studied in Section 6.3, but not quite the same thing. Notes posted within "Content". This problem is related to at least one of the homework 4 problems.
• 03/10: Midterm Exam
• 03/22: Network Flow Algorithms (Chapter 7). Slides posted within "Content".
• 03/24: We'll complete the discussion of the Ford-Fulkerson Algorithm (see notes from 03/22). This corresponds to Sections 7.1 and 7.2 of the text. **PLEASE NOTE**: I am using the slides that come with the textbook, and they contain more material than we will cover. So please keep track of what we cover. I hope to update the notes later with just the portions we cover.
• 03/29: We'll start on applications of network flow (slides posted), and do the bipartite matching application today. That's Section 7.5. We'll start on the image segmentation application from 7.10.
• 03/31: We complete the image segmentation application, and do the baseball elimination application from 7.12
• 04/05: Randomized Algorithms, Contention Resolution (Section 13.1)
• 04/07: Global Minimum Cut (Section 13.2)
• 04/12: Quicksort analysis (will post notes) and a brief introduction to polynomial time reductions (Chapter 8)
• 04/14: More reductions: matching to maximum independent set. Introduction to CNF satisfiability, and reduction of 3-colorability to CNF satisfiability.
• 04/19: Decision problems, formal statement of one decision problem being reducible to another, and reduction from decision version of unweighted independent set to CNF satisfiability. Most of the reductions in the last two lectures are not from the book, and I've posted brief notes in icon.
• 04/21: Efficient verifiers, the classes NP and P, P vs. NP, NP-completeness (8.3 and 8.4)
• 04/26: NP-completeness of CNF-SAT, deducing the NP-completeness of Independent set via reduction from CNF-SAT (the reduction is in 8.2), Exercise 2 of Chapter 8
• 04/28: Vertex Cover and its NP-completeness, Solved Exercise from the book on Lecture Planning.
• 05/03: Overview of Final and NP-completeness of 3-colorability (8.7).
• 05/05: Problems solved at request of students in class.