TAs:
Eric Purdy, email: epurdy (at) uchicago.edu
Duru Turkoglu, email: duru (at) cs.uchicago.edu
Lecture: MWF 11:30-12:20 in Ryerson 251
Office hours:
Monday 3-4 in Ryerson 162C (pff)
Tuesday 4-5 in Ryerson 165A (epurdy)
Friday 2-3 in Ryerson 256 (duru)
Textbook: Algorithm Design by Jon Kleinberg and Eva Tardos
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 16.
- Exercises 2,3,4 in Chapter 1.
- Exercise 6 in Chapter 2.
Homework 2, due Wednesday January 23.
- Exercises 2,5,9,17 in Chapter 4.
- Extra credit: exercise 26 in Chapter 4.
Homework 3, due Friday February 1.
Homework 4, due Wednesday February 6.
Homework 5, due Friday February 22th.
Homework 6, due Friday February 29th.
- Exercise 8 in Chapter 2.
- Exercise 3 in Chapter 5 (extra credit: give an O(n) algorithm for this problem).
- Finding high-capacity paths.
- Exercises 1,4,7 in Chapter 6.
- Sleep pattern.
- Exercises 1,2,4,5,8 in Chapter 7.
- Exercises 2,6,14 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 | 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 |