CS 573: Schedule and Lecture Notes

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:

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
ACM Conference
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