Preliminary notes on most lecture topics are already available; Jeff will revise and update these notes as the semester progresses. We may also post additional notes on more advanced course material, which will not be covered on any homework or exam. Future lecture topics and homework due dates are subject to change; however, exam dates are fixed. Links to future homeworks and exams are placeholders; they won't work until the homework has actually been released.
Please tell Jeff if you find bugs in the lecture notes. Any student who describes a bug and its solution on the course newsgroup will be awarded extra credit (but only once per bug). Please also tell Jeff if you have trouble downloading or printing anything.
Students are strongly encouraged to consult sources in addition to than the notes posted here. Several algorithms textbooks are on reserve in Grainger Library, and many complete sets of course materials can be found on the web. Here is a small sample:
- Jeff's notes, homeworks, and exams from previous semesters
- Sariel Har-Peled (CS 473G = CS 573, Fall 2003 and Fall 2007)
- Chandra Chekuri (CS 473, Fall 2009)
- Mahesh Viswanathan (CS 473, Spring 2008).
- MIT (Spring 2008; Fall 2005, with video and alternate notes)
- CMU (Fall 2008; Spring 2010)
- University of Washington (several semesters)
Date Lecture topics Deadlines Wed Aug 25 Introduction, history, and administrivia
Additional notes on induction and recurrences
Fri Aug 27 P vs NP, NP-hardness, Cook's theorem, SAT, 3SAT Wed Sep 1 More NP-hardness: Independent Set, Clique, Vertex Cover, 3-Color (more examples in the notes) Homework 0 in class Fri Sep 3 Divide and conquer: mergesort and quicksort review, O(n)-time median selection Online add deadline Wed Sep 8 Fast Fourier transforms Fri Sep 10 Backtracking: subset sum, longest increasing subsequence, maximum independent set Mon Sep 13 Homework 1 Wed Sep 15 Dynamic programming: Fibonacci numbers, edit distance, optimal binary search trees Fri Sep 17 More dynamic programming: maximum independent sets in trees, Wed Sep 22 Advanced dynamic programming tricks: saving space via divide-and-conquer, exploiting sparseness Fri Sep 24 Greedy algorithms: Tape sorting, scheduling, Huffman codes Mon Sep 27 Homework 2 Wed Sep 29 — Midterm 1 — 7:00-8:30 — David Kinley Hall 119 and 123 — No lecture —
prerequisite material, NP-hardness, recursion, dynamic programming
Fri Oct 1 Greedy approximation: load balancing, vertex cover, set cover/hitting set Paper add deadline Wed Oct 6 More approximation algorithms: dumb vertex cover, traveling salesman (both without and with the triangle inequality) Approximation schemes: k-center clustering Fri Oct 8 Randomized algorithms: sorting/matching nuts and bolts Wed Oct 13 Randomized treaps and skip lists Fri Oct 15 Chernoff bounds Online drop deadline
Mon Oct 18 Homework 3 Wed Oct 20 Balls and bins; perfect hashing; universal hashing; cuckoo hashing Fri Oct 22 Amplification: Randomized minimum cut Wed Oct 27 Maximum flows and minimum cuts Fri Oct 29 Maximum flow algorithms: augmenting path, push-relabel Mon Nov 1 Homework 4 Wed Nov 3 — Midterm 2 — 7:00-8:30 — location TBA — No lecture —
greedy algorithms, approximation algorithms, randomized algorithms, treaps and skip lists, hashing, amplification
Fri Nov 5 Applications of maximum flow: maximum matching, edge-disjoint paths Wed Nov 10 More applications: assignment, baseball
Generalizations of max-flow: edge demands, min-cost flow
Fri Nov 12 Linear programming: definitions, examples, geometry, duality Paper drop deadline Wed Nov 17 Linear programming duality Fri Nov 19 The simplex algorithm: falling marbles and rising bubbles Homework 5 Wed Nov 24 — Thanksgiving break — no lectures — Fri Nov 26 Wed Dec 1 Network simplex (maximum flows, shortest paths, etc.) Fri Dec 3 Randomized rounding Wed Dec 8 Any questions? Homework 6 (not graded) Tue Dec 14 — Final Exam — 7:00—10:00 — location TBA —
everything, with slightly more emphasis on maximum flows, minimum cuts, and linear programming