Winter 2008, Carleton College

- 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.*

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!

- 4 January 2008 (F): course overview, algorithmic problems in the
*Times*, quickfire review of data structures, and stable marriage.**Reading:**Preface and §1.1.

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.

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.

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.
**Reading:**§6.1–6.2; if you please, NYT on Belichick.

The last question from PS3 is due on Monday.

One question from PS4 is due on Friday.

- 28 January 2008 (M): dynamic programming: Fibonacci numbers, word
segmentation.
**Reading:**§6.3–6.5 (for extra practice with dynamic programming). - 30 January 2008 (W): midterm #1
- 1 February 2008 (F): dynamic programming: sequence alignment.
**Reading:**§6.6.

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.

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.

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.

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.

One question from PS7 is due on Friday.

- 3 March 2008 (M): P, NP, and NP-completeness.
**Reading**: §8.4. - 5 March 2008 (W): Cook–Levin Theorem and more NP-completeness.
**Reading**: §8.8; §8.5–8.6 (for more practice); §8.9 (for the digression about NP and coNP). - 7 March 2008 (F): NP-completeness: subset sum, graph coloring.
**Reading**: §8.7

- 10 March 2008 (M): mountains of miscellenea: 3-coloring, approximation algorithms, the takehome.

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.