CMSC 27200 Theory of Algorithms
Course Mechanics
Course Overview
What we covered so far
Assignments and Handouts
Course Mechanics
Instructor
Janos Simon
165 Ryerson
email: simon (at) cs.uchicago.edu
Office Hours: Fridays 2-3 and by appointment
TAs
TAs: Denis Pankratov, Pooya Hatami
Office hours:
Pooya Hatami: Mondays 4-5
Dennis Pankratov: Tuesdays 5-6
Lecture:
MWF 11:30-12:20 in Ryerson 276
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, a midterm (on 2/8) and
a final.
Course Overview
We will study algorithms: roughly the first half will be deterministic exact algorithms, the second half
will examine hardness results, approximation algorithms and probabilistic algorithms.
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 | Divide and conquer: mergesort. Recurrence equations and recursive programs. | Section 5.1,5.2
|
| 8 | Lower bound on sorting. Dynamic programming |
|
| 9 | Shortest paths | Section 6.8
|
| 10 | Sequence alignment | Section 6.6
|
| 11 | Matrix chain multiplication |
|
| 13 | Max-flow part 1 | Section 7.1 |
|
| 14 | Max-flow part 2 | Section 7.2 |
|
| 15 | Max-flow part 3 | Section 7.3 |
|
| 15 | Matchings, Image segmentation | Section 7.5 |
|
| 16 | Circulations, etc. | Section 7.7 |
|
| 17 | Lower bounds: Sorting by comparisons, Halting Problem. |
|
| 18 | Probabilistic Algorithms. Sections 13.1 (beginning), 13.3, 13.5 |
|
| 19 | Reductions | Section 8.1 |
|
| 20 | Satisfiability, NP-hard problems | Section 8.2,8.3,8.4 |
|
| 21 | Proving NP-completeness: Hamitonian Circuits (Section 8.5) |
|
Other topics to be covered:
Strategies to cope with NP-hardness: approximation algorithms (sections from Chapter11)
Time permitting: local search and ideas about quantum algorithms.
Material covered so far
See here
Assignment 1 Due Wednesday January 11 in class.
Assignment 2 Due Wednesday January 18 in class.
Assignment 3 Due Wednesday January 25 in class.
Assignment 4 Due Wednesday February 1st in class.
Assignment 5 Due Wednesday February 15th in class.
Assignment 6 Due Wednesday February 22nd in class.
Assignment 7 Due Wednesday February 29th in class.
Bonus Assignment Due Wednesday March 7 in my office (1PM).
Important Homework Instructions
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, other than the textbook.
Do NOT search the web for solutions!