CMSC 27200 - Winter 2008
Theory of Algorithms


Announcements

The second midterm will be Friday, March 7.

General information

Instructor: Pedro F. Felzenszwalb
email: pff (at) cs.uchicago.edu

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.

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!

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.
- Exercise 8 in Chapter 2.
- Exercise 3 in Chapter 5 (extra credit: give an O(n) algorithm for this problem).
- Finding high-capacity paths.

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

Homework 5, due Friday February 22th.
- Exercises 1,2,4,5,8 in Chapter 7.

Homework 6, due Friday February 29th.
- Exercises 2,6,14 in Chapter 8.

Approximate Syllabus

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