CMSC 27200 - Winter 2006
Theory of Algorithms

General information

Instructor:Pedro F. Felzenszwalb
Email:pff (at) cs.uchicago.edu
Lecture:MWF 1:30-2:20 Ryerson 251
Office hours:Tuesday 4:00-5:00 in Ryerson 162C

TAs
Paolo Codenotti
Email: paoloc (at) cs.uchicago.edu
Office hours: Monday 2:30-4:30 in Eckhart 2A (basement).
Parinya Chalermsook
Email: parinya (at) cs.uchicago.edu
Office hours: Wednesday and Friday 3:30-4:30 in Ryerson 162.

Textbook: Algorithm Design - Jon Kleinberg and Eva Tardos

Grading will be based on weekly homework assignments (50%) and two exams (50%).

Schedule

LectureTopicsReading
1Stable matchingsChapter 1
2Running time analysisChapter 2
3Interval SchedulingSection 4.1,4.2
4Minimum Spanning TreesSection 4.5
5Union-FindSection 4.6
6Dijkstra's shortest-pathsSection 4.4
7Sorting: lowerbound and mergesortSection 5.1,5.2
8Closest pair of points / DPSection 5.4
9Shortest paths, Sequence alignmentSection 6.8,6.6
10Convex hulls
11Max-flow part 1Section 7.1
12Max-flow part 2Section 7.2
13Matchings, Image segmentationSection 7.5
14Circulations, etc.Section 7.7
15ReductionsSection 8.1
16Satisfiability, NPSection 8.2,8.3,8.4
17Set cover & Vertex cover approximationSection 11.3,11.4
18Knapsack approximationSection 11.8
19Randomized 3-SAT approximationSection 13.4
20Global min-cuts (random contraction)Section 13.2
21QuicksortSection 13.5
22Local search for max-cutSection 12.4
23Matrix search, min-filter
24Matrix chain multiplication

Homework

Students are encouraged to work together, but each student must independently write up their solutions. Write-ups must include the names of any collaborators and any sources used to help solve a problem. Do NOT search the web for homework problems!

Homework 1, due Wednesday January 11.
- Exercises 2,3,4 in Chapter 1 of the textbook.
- Extra credit: Show that the greedy algorithm for interval scheduling that selects the shortest valid interval in each step is not "too bad".

Homework 2, due Wednesday January 18.
- Exercises 2,5,8,9,17,26 in Chapter 4 of the textbook.

Homework 3, due Wednesday January 25.
- Exercise 8 in Chapter 2.
- Exercise 3 in Chapter 5.
- Merging sorted arrays.
- Finding high-capacity paths.

Homework 4, due Wednesday February 1.
- Exercises 1,4,6,20 in Chapter 6.
- Sleep pattern.

Homework 5 due Wednesday February 8.
- Exercise 3 in Chapter 4.
- Exercise 6 in Chapter 5.
- Exercises 1,2,7 in Chapter 7.
- k-connected graphs.
Extra credit: Exercise 7 in Chapter 5 (please turn in separately from the rest).

Homework 6 due Wednesday February 22.
- Exercises 1,6,14,29 in Chapter 8.

Homework 7 due Friday March 3.
- Exercises 1,10,11 in Chapter 11.
- Exercises 1,9,12 in Chapter 13.

Challenge problems

1. Cyclic string alignment

Midterm: Wednesday, February 8

Practice problems
Problem/Review sessions: Monday and Tuesday (February 6,7) at 5pm in Ryerson 251