TA: Raghav Kulkarni
email: raghav (at) cs.uchicago.edu
office hours: M/W 4:00-5:00 in Eck 2 (basement of Eckhart)
Lecture: MWF 11:30-12:20 in Ryerson 251
Textbook: Algorithm Design by Kleinberg and Tardos
Other useful sources:
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
Algorithms by Dasgupta, Papadimitriou and Vazirani
Grading will be based on weekly homework assignments, two midterms and a final.
Students may submit up to two assignments late. Late homework is due Friday after the original deadline.
Homework 1, due Wednesday January 14.
- Exercises 2,3 in Chapter 1.
- Exercise 6 in Chapter 2.
Homework 2, due Wednesday January 21.
- Exercises 2,5,9,17 in Chapter 4.
Homework 3, due Wednesday January 28.
Homework 4, due Wednesday February 11.
Homework 5, due Monday February 23th.
Homework 6, due Friday March 6th.
- Exercise 8 in Chapter 2.
- Exercise 3 in Chapter 5.
- Finding high-capacity paths.
- Exercises 1,4,7 in Chapter 6.
- Sleep pattern.
- Exercises 1,2,4,5,8 in Chapter 7.
- Exercise 20 in Chapter 6.
- Exercises 1,6 in Chapter 8.
Approximate Syllabus
| Lecture | Topics | Reading |
| 1 | Stable matchings | Chapter 1 |
| 2 | Running time analysis | Chapter 2 |
| 3 | Interval Scheduling | Section 4.1,4.2 |
| 4 | Minimum Spanning Trees | Section 4.5 |
| 5 | Union-Find | Section 4.6 |
| 6 | Dijkstra's shortest-paths | Section 4.4 |
| 7 | Sorting: lowerbound and mergesort | Section 5.1,5.2 |
| 8 | Dynamic programming | |
| 9 | Shortest paths | Section 6.8 |
| 10 | Sequence alignment | Section 6.6 |
| 11 | Matrix chain multiplication | |
| 12 | Convex hulls | |
| 13 | Max-flow part 1 | Section 7.1 |
| 14 | Max-flow part 2 | Section 7.2 |
| 15 | Matchings, Image segmentation | Section 7.5 |
| 16 | Circulations, etc. | Section 7.7 |
| 17 | Reductions | Section 8.1 |
| 18 | Satisfiability, NP | Section 8.2,8.3,8.4 |
| 19 | Set cover approximation | Section 11.3 |
| 20 | Knapsack approximation | Section 11.8 |
| 21 | Randomized 3-SAT approximation | Section 13.4 |
| 22 | Global min-cuts (random contraction) | Section 13.2 |
| 23 | Quicksort | Section 13.5 |
| 24 | Local search for max-cut | Section 12.4 |