| Instructor: | Pedro F. Felzenszwalb |
| Email: | pff (at) cs.uchicago.edu |
| Lecture: | MWF 11:30-12:20 Ryerson 251 |
| Office hours: | Monday 3:00-4:00 in Ryerson 162C |
TAs
| Paolo Codenotti |
| Email: paoloc (at) cs.uchicago.edu |
| Office hours: Thursday ? |
| Duru Turkoglu |
| Email: duru (at) cs.uchicago.edu |
| Office hours: Tuesday 1:00-3:00 in Ryerson 256 |
Textbook: Algorithm Design - Jon Kleinberg and Eva Tardos
Grading will be based on weekly homework assignments (50%) and two exams (50%).
Students may submit up to two assignments late. Late homework is due Friday after the original deadline.
Homework 1, due Wednesday January 10.
- Exercises 2,3,4 in Chapter 1.
- Exercise 6 in Chapter 2.
Homework 2, due Wednesday January 18.
- Exercises 2,5,8,9,17 in Chapter 4.
- Extra credit: exercise 26 in Chapter 4.
Homework 3, due Wednesday January 24.
Homework 4, due Friday February 2nd.
Homework 5, due Wednesday February 14th.
Homework 6 due Wednesday February 21st.
Homework 7 due Friday March 2nd.
- Exercise 8 in Chapter 2.
- Exercise 3 in Chapter 5.
- Merging sorted arrays.
- Finding high-capacity paths.
- Extra credit: give an O(n) algorithm for the problem in Exercise 3 in Chapter 5.
- Exercises 1,4,6,20 in Chapter 6.
- Sleep pattern.
- Exercises 1,2,4,5 in Chapter 7.
- Exercise 7 in Chapter 7.
- k-connected graphs.
- Excercises 1,14 in Chapter 8.
- Exercises 1,3 in Chapter 11.
- Exercises 9,12 in Chapter 13.
Extra credit: Exercise 7 in Chapter 5.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 | Closest pair of points / DP | Section 5.4 |
| 9 | Shortest paths, Sequence alignment | Section 6.8,6.6 |
| 10 | Convex hulls | |
| 11 | Max-flow part 1 | Section 7.1 |
| 12 | Max-flow part 2 | Section 7.2 |
| 13 | Matchings, Image segmentation | Section 7.5 |
| 14 | Circulations, etc. | Section 7.7 |
| 15 | Reductions | Section 8.1 |
| 16 | Satisfiability, NP | Section 8.2,8.3,8.4 |
| 17 | Set cover & Vertex cover approximation | Section 11.3,11.4 |
| 18 | Knapsack approximation | Section 11.8 |
| 19 | Randomized 3-SAT approximation | Section 13.4 |
| 20 | Global min-cuts (random contraction) | Section 13.2 |
| 21 | Quicksort | Section 13.5 |
| 22 | Local search for max-cut | Section 12.4 |
| 23 | Matrix search, min-filter | |
| 24 | Matrix chain multiplication |