CS252 (Algorithms)
Winter 2013, Carleton College

[Jump to current week]

Basic information:

Instructor: David Liben-Nowell
Lecture: 1a (MW 8:30--9:40a, F 8:30--9:30a), Boliou 104.
Office Hours: Monday 9:45.10:45am, Thursday 10:00.11:00am, and by appointment. To make an appointment, give me at least 24 hours of notice, and list several times that you would be available to meet in your email.
Nick's office hours: Tuesday and Friday, 10:00.11:30a, in CMC 307. 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). Along the way, we will explore the application of these techniques to a variety of domains (natural language processing, economics, computational biology, and data mining, for example). As time permits, we will include supplementary topics like randomized algorithms, advanced data structures, and amortized analysis. Prerequisites: CS 201; CS 202 or Math 236.

Course Materials:

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!

Some useful LaTeX links: a tutorial from MIT and a reference guide from Cambridge. The LaTeX Wikibook.
A LaTeX symbol finder and an equation recognizer.
Also useful: an Emacs tutorial from Chicago.

Week 0: intro to CS 252.

4 January 2013 (F): course overview, algorithms in the Times, course logistics.
Reading: Kleinberg–Tardos, Preface.

Nick's office hours will be Tuesday and Friday, 10:00–11:30a, in CMC 307.

PS1 is now available on Moodle. Part I is due on Monday; Part II is due on Wednesday.

Week 1: review of asymptotics, algorithms, and problems (Chapters 1 and 2).

7 January 2013 (M): state health-care emulation; solving stable marriage: brute-force and the Gale–Shapley proposal algorithm.
Reading:Kleinberg–Tardos, §1.1, §2.1–2.2.

PS2 was handed out today. Part I is due on Friday; Part II is due on Monday; Part III is due on Wednesday.
9 January 2013 (W): Gale–Shapley; stable-marriage variants that better model the NRMP.
Reading: Kleinberg–Tardos, §2.3–2.5.
11 January 2013 (F): stable marriage wrapup; census; data structures; hint of asymptotics
Reading: §3.1; posted asymptotics notes.
Optional (but skim page 1): Jack Edmonds, Paths, Trees, and Flowers. Canadian Journal of Mathematics, 1965.

Week 2: proofs of correctness and graphs (Chapters 2 and 3).

14 January 2013 (M): asymptotics (O, Ω, Θ)
Reading: Kleinberg–Tardos, §1.2, §3.2–3.3.

PS3 was handed out today. Part I is due on Friday; Part II is due on Monday; Part III is due on Wednesday.
16 January 2013 (W): graph representations; sample problems
Reading: Kleinberg–Tardos, §3.4–3.6.
18 January 2013 (F): a parable of Alice and Bob; BFS/DFS.
Reading: Kleinberg–Tardos, §4.4.

Week 3: greedy algorithms (Chapter 4).

21 January 2013 (M): the "edge-explosion" algorithm; Dijkstra's algorithm.
Reading: Kleinberg–Tardos, §4.1.
23 January 2013 (W): Dijkstra's algorithm wrapup; greedy algorithms; interval scheduling.
Reading: Kleinberg–Tardos, §4.2.

PS4 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.
25 January 2013 (F): max utilization; deadline scheduling ("exchange arguments").
Reading: Kleinberg–Tardos, §4.5–4.6.

Week 4: greedy algorithms; dynamic programming (Chapters 4 and 6).

28 January 2013 (M): deadline scheduling; buggy greedy proofs; minimum spanning trees.
Reading: nothing new.
30 January 2013 (W): MSTs: Reverse-Delete, Kruskal's, Prim's, Borůvka's, and Karger's algorithms.
Our first prelim is scheduled for next Wednesday, 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. I may ask you to hand in your crib sheet with your exam. Any material up to and including greedy algorithms is fair game for the exam.

Reading: posted MST notes.
Optional: David Karger, Philip Klein, and Robert Tarjan. A randomized linear-time algorithm to find minimum spanning trees, JACM, 1995.
Optional: Jeff Erickson. Notes on Disjoint Sets data structures.
1 February 2012 (W): dynamic programming overview; word segmentation.
Reading: Kleinberg–Tardos, §6.1–6.2.

PS5 was posted today. It is due next Friday.

Week 5: dynamic programming (Chapter 6).

4 February 2013 (M): midterm break!
6 February 2013 (W): prelim #1
8 February 2013 (F): dynamic programming: word segmentation; weighted interval scheduling; Fibonaccis.
Reading: Kleinberg–Tardos, §6.6–6.7.

PS6 was posted. It's due on Wednesday, Friday, and Monday.

Week 6: dynamic programming; divide and conquer (Chapter 5).

11 February 2013 (M): dynamic programming: sequence alignment; seam carving; shortest paths in weighted graphs with negative edges.
Reading: Kleinberg–Tardos, §6.8, 4.4.
Optionally: NYT on Belichick, and the seam-carving paper and video by Shai Avidan and Ariel Shamir.
13 February 2013 (W): dynamic programming: Bellman–Ford, and Floyd–Warshall. midterm course evals.
Reading: Kleinberg–Tardos, §5.1, 5.2.
For optional additional practice with dynamic programming, read the remainder of Chapter 6.
15 February 2013 (F): seam carving (via Bellman–Ford, Floyd–Warshall, and custom DP); divide and conquer; recurrence relations.
Reading: posted notes on recurrences.

PS7 was posted. It's due on ~~Wednesday, Friday, and Monday~~ Friday, Monday, and Wednesday.

Week 7: divide and conquer (Chapter 5).

18 February 2013 (M): divide and conquer: recurrence relations (overview; master method; Karger's algorithm).
Reading: Kleinberg–Tardos, §5.3.
20 February 2013 (W): counting inversions; order statistics.
Reading: Kleinberg–Tardos, §5.4; handouts posted on Moodle (inversions, order statistics).
22 February 2013 (F): randomized select; magic 5
Reading: wikipedia on selection algorithm; posted magic-5 and closest-pair-of-points handout on Moodle.
Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, "Time bounds for selection", 1973 (posted on Moodle).

Week 8: network flow (Chapter 7).

25 February 2013 (M): D&C wrap (magic 5, closest points in the plane); network flow.
Reading: §7.1.

PS8 was handed out today. It's due on ~~Friday and Monday~~Monday and Wednesday.

PS9 was handed out today. It's due next Friday.
27 February 2013 (W): network flow: cuts, Zachary's Karate Club, Ford–Fulkerson.
Reading: §7.2–7.3.
1 March 2013 (F): max flow/min cut
Reading: §7.5.

The second exam is scheduled for Wednesday, in class. You may bring one 8.5"-by-11" sheet of paper containing notes handwritten or typed by you. You may write on both sides of the paper. Any material up to and including class on Friday 3/1 and ps8 is fair game.

Week 9: exam 2, network flow, miscellanea (Chapter 7).

4 March 2013 (M): max flow/min cut; Edmonds–Karp.
6 March 2013 (W): prelim #2
8 March 2013 (F): bipartite matching; connecting algorithms and CS 254. [choose your own adventure]
Reading: Kleinberg–Tardos, §8.0, 8.3, 9.1. Wikipedia on P vs. NP.

The final will be self scheduled. You may use a one-page crib sheet for the exam, as for the previous two exams. You must hand write or type the crib sheet yourself. Because of the registrar's deadline for self scheduled exams, to use a crib sheet, you must file your crib sheet in your exam envelope BY NOON ON TUESDAY 12 MARCH. The box for these crib sheets is in CMC 307 and will be there on Tuesday morning (and late-ish on Monday night).

Week 10: wrapup.

11 March 2013 (M): course evaluations; ask me anything.

Finals Period:

The final is self-scheduled.

~~Our finals slot is scheduled for 15 March 2013, 7:00–9:30p.~~

CS252 (Algorithms) Winter 2013, Carleton College

[Jump to current week]

Basic information:

Course Materials:

CS252 (Algorithms)
Winter 2013, Carleton College