Basic information:
- Instructor: David
Liben-Nowell
- Lecture: 1a (MW 8:30--9:40a, F 8:30--9:30a),
CMC
319 CMC 206.
- Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
- Official catalogue description:
A course on techniques used in the design and analysis of efficient
algorithms. We will cover several major algorithmic design paradigms
(greedy algorithms, dynamic programming, divide and conquer, and
network flow); applications of those techniques to a variety of
domains (natural language processing, economics, computational
biology, and data mining, for example); and computational complexity,
particularly NP-completeness, including how to cope algorithmically
when confronted with intractable problems. Prerequisites: CS 201; Math
111; CS 202 or Math 236.
Course Materials:
Week 0:
There is an
anonymous feedback form
available for any comments that you have about the course. If you
have any suggestions or comments on the class (style, content,
workload, etc.), please feel free to use this form to let me know.
The CS department has an email newsletter, the
Carleton Sentinel, that we use for occasional updates on things
that might be of interest. Sign up
here!
Week 0.5: intro to 252 (Chapter 1).
Week 1: some representative problems; review of asymptotics, data structures (Chapters 1 and 2).
PS0 is due on Monday.
One question from PS1 is due on Wednesday.
One question from PS1 is due on Friday.
- 7 January 2008 (M): solving stable marriage: brute-force and the
Gale–Shapley proposal algorithm.
Reading: §1.1, §2.1–2.3.
- 9 January 2008 (W): data structures review; implementing
Gale–Shapley; stable-marriage variants that better model the NRMP.
Reading: §2.4–2.5.
- 11 January 2008 (F): asymptotics, efficiency=polytime, graph
definitions begun.
Reading: §3.1, §1.2.
Week 2: review of graphs; greedy algorithms (Chapters 3 and 4).
The last question from PS1 is due on Monday.
One question from PS2 is due on Wednesday.
One question from PS2 is due on Friday.
- 14 January 2008 (M): graph definitions and some sample graph
problems.
Reading: §3.2–3.5.
- 16 January 2008 (W): a BFS/DFS refresher; shortest paths in
weighted graphs; the "edge-explosion" algorithm.
Reading: §4.4.
- 18 January 2008 (F): Dijkstra's algorithm, "reducing in the wrong
direction", and interval scheduling.
Reading: §4.1.
Week 3: greedy algorithms and dynamic
programming (Chapters 4 and 6).
The last question from PS2 is due on Monday.
(If you've done optional problems, submit them on Monday as
well.)
There will be an information session for the
CS major at 4:00p on Tuesday in Hill Lounge (with free food!). Hope
to see you there!
One question from PS3 is due on Wednesday.
One question from PS3 is due on Friday.
Our first midterm is scheduled for Wednesday,
30 January 2008, in class. You may bring one 8.5"-by-11"
crib sheet containing notes that you have handwritten or typed
yourself (no photocopying). You may write on both sides of the paper,
but don't staple/tape/superglue/attach anything to the paper. You
will be asked to hand in your crib sheet with your exam. Any material
up to and including greedy algorithms (so through 25 January 2008 in
class, through Problem Set 3 and the MST problem on PS4, and Chapters
1–4) is fair game for the exam.
- 21 January 2008 (M): interval scheduling ("greedy stays ahead");
defining "greedy"; deadline scheduling ("exchange arguments").
Reading: §4.2.
- 23 January 2008 (W): minimum spanning trees.
Reading: §4.5–4.6.
- 25 January 2008 (F): a brief MST wrapup; memoization and dynamic
programming.
Week 4: dynamic programming (Chapter 6);
midterm exam.
The last question from PS3 is due on Monday.
One question from PS4 is due on Friday.
Week 5: dynamic programming and
divide-and-conquer algorithms (Chapters 6 and 5).
Two questions from PS4 are due on
Wednesday. You must have completed question #1 from PS4 by
Wednesday.
The last question from PS4 is due on
Friday.
- 4 February 2008 (M): midterm break!
- 6 February 2008 (W): shortest paths revisited,
Floyd–Warshall, Bellman–Ford.
Reading: §6.8, 4.4.
- 8 February 2008 (F): divide-and-conquer algorithms, recurrence
relations, and counting inversions.
Reading: §5.1–5.3.
Week 6: divide and conquer; network flow
(Chapters 5 and 7).
One question from PS5 is due on Monday.
One question from PS5 is due on Wednesday.
One question from PS5 is due on Friday.
- 11 February 2008 (M): median and order statistics.
Reading: wikipedia on
selection
algorithm.
Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan,
"Time bounds for selection", 1973. (Posted in the Courses folder for
CS252.)
- 13 February 2008 (W): closest pairs of points in the plane.
Reading: §5.4.
- 15 February 2008 (F): introduction to network flow.
Reading: §7.1.
Week 7: network flow (Chapter 7).
The last question from PS5 is due on Monday.
One question from PS6 is due on Friday.
Our second midterm is scheduled for Wednesday,
27 February 2008, in class. You may bring one 8.5"-by-11"
crib sheet containing notes that you have handwritten or typed
yourself (no photocopying). You may write on both sides of the
paper, but don't staple/tape/superglue/attach anything to the paper.
You will be asked to hand in your crib sheet with your exam. Any
material up to and including maximum flow (so through 22 February 2008
in class, through Problem Set 6, and Chapters 1–7) is fair game
for the exam.
- 18 February 2008 (M): augmenting paths, residual graphs,
Ford–Fulkerson, max flow/min cut.
Reading: §7.2–7.3.
- 20 February 2008 (W): max flow/min cut, Edmonds–Karp.
Reading: §7.5.
- 22 February 2008 (F): applications of network flow
Reading: §7.6.
Week 8: hard problems and reductions
(Chapter 8); midterm exam.
One question from PS6 is due on Monday.
The last question from PS6 is due on Wednesday.
If you would like to see the solution set for
PS6 before the exam, you may hand in your PS6 solutions to me by 4:00p
on Tuesday, 26 February 2008. I will trade them for a solution set
(obviously not to be shared with anyone else).
- 25 February 2008 (M): reductions.
Reading: §8.1–8.2.
- 27 February 2008 (W): midterm #2
- 29 February 2008 (F): gadget reductions.
Reading: §8.3.
Week 9: NP completeness (Chapter 8).
Two questions from PS7
are One question from PS7 is due on Wednesday.
One question from PS7 is due on Friday.
Week 10: wrapup and current research in
algorithms
The last question from PS7 is
The last two questions from PS7 are due on Monday.
- 10 March 2008 (M): mountains of miscellenea: 3-coloring,
approximation algorithms, the takehome.
Finals Period:
Our scheduled finals slot is on Friday, 14 March 2008,
from 7–9:30p.
The final exam will be a take-home. I'll give it out
on the last day of classes and it will be due, as per college policy,
on the last day of finals period.