CS 373: Combinatorial Algorithms (Spring 1999)

TuTh 9:30-10:45, 1320 Digital Computer Laboratory

Course Schedule, Lecture Notes, Homeworks, and Exams

Please let me know if you find major bugs in the lecture notes.
I will gladly email homework and exam solutions to interested instructors.

Date Topics (with links to lecture notes) Reading Due
Tu 1/19 0. administrivia, introduction [Mitch Harris] CLR 1--6  
Design and Analysis Techniques
Th 1/21 1. divide and conquer: sorting, exponentiation CLR 8  
Tu 1/26 2. dynamic programming: Fibonacci numbers, edit distance CLR 16 hw 0
Th 1/28 3. randomization: matching/selecting nuts and bolts CLR 8  
Tu 2/2 4. amortized analysis: aggregate, taxation, and potential methods CLR 18  
Advanced Data Structures
Th 2/4 5. self-adjusting binary search trees (``splay trees'', ``scapegoat trees'') CLR 13, notes  
Tu 2/9 6. randomized binary search trees (``treaps'') notes hw 1
Th 2/11 7. Fibonacci heaps CLR 21  
Tu 2/16 8. More Fibonacci heaps CLR 21  
Th 2/18 9. Uniform and universal hashing CLR 12 hw 2
Tu 2/23 --- In-Class Midterm 1 ---
Graph Algorithms
Th 2/25 10. representing and searching graphs CLR 23  
Tu 3/2 11. minimum spanning trees: Kruskal, Jarnik ("Prim"), Boruvka CLR 24  
Th 3/4 12. shortest paths: Dijkstra, Moore ("Bellman-Ford") CLR 25  
Tu 3/9 13. union/find, path compression [Shripad Thite] CLR 22  
Th 3/11 14. union/find, path compression, cont'd [Shripad Thite] CLR 22 hw 3
Tu 3/16 Spring Break
Th 3/18 Spring Break
Geometric Algorithms
Tu 3/23 15. convex hulls: scanning, wrapping, splitting, and shattering CLR 35  
Th 3/25 16. plane sweep: segment intersection CLR 35  
Tu 3/30 17. polygon triangulation: cutting ears and sweeping notes  
Th 4/1 18. Bézier curves notes hw 4
Tu 4/6 --- In-Class Midterm 2 ---
String Algorithms
Th 4/8 19. string matching: naive, Rabin-Karp (``fingerprinting'') CLR 34  
Tu 4/13 20. string matching: Knuth-Morris-Pratt CLR 34  
Lower Bounds
Th 4/15 21. information theory: searching and sorting CLR 9  
Tu 4/20 22. adversary arguments: selection, graph properties notes  
Th 4/22 23. reductions and transformations CLR 36 hw 5
NP-completeness
Tu 4/27 24. NP-hard, NP-easy, and NP-complete problems CLR 36  
Th 4/29 25. more NP-hard problems CLR 36  
Tu 5/4 26. approximation algorithms CLR 37 hw 6
Fr 5/7 --- Final Exam --- projects

Administrivia

Instructor:
Jeff Erickson (jeffe@cs.uiuc.edu), 2113 DCL
Teaching assistants:
Mitch Harris (maharri@cs.uiuc.edu), 1216 DCL
Shripad Thite (thite@cs.uiuc.edu), 1216 DCL
Prerequisites:
Students are assumed to have working knowledge of the material taught in CS 225 and CS 273. (This is not the same as merely having passed.) If you're an undergraduate and you haven't taken those classes, you need my permission to enroll.

Coursework:
Grades will be based on 6-8 homeworks (30%) (dropping the lowest), two in-class midterms (20% each), and a final exam (30%). Graduate students taking the class for a full unit will have extra work: extra homework and exam problems, a semester project, or both. There will be three different grade scales: undergraduates, 3/4-unit graduates, and 1-unit graduates. Undergraduates interested in honors credit should contact the instructor.

Topics:
  • Design and analysis techniques: divide and conquer, dynamic programming, randomization, amortization
  • Advanced data structures: universal hashing, splay trees, treaps, Fibonacci heaps, union/find
  • Graph algorithms: representations, minimum spanning trees, shortest paths
  • Geometric algorithms: convex hulls, plane sweep, polygon triangulation, Bézier curves
  • Lower bounds: decision trees, adversaries, reductions, NP-hardness, approximation algorithms

Textbooks:
[CLR]
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press/McGraw­Hill, 1990. Required.

[Par]
Ian Parberry, Problems on Algorithms, Prentice­Hall, 1995. Recommended, especially for students who want or need practice with prerequisite material.

Some useful web pages and other handouts: