# CS 373: Combinatorial Algorithms (Spring 1999)

## 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.

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

Instructor:
Jeff Erickson (jeffe@cs.uiuc.edu), 2113 DCL
Teaching assistants:
Mitch Harris (maharri@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: