CS252 (Algorithms) Winter 2012, Carleton College

Week 1: intro to 252, algorithms, and some representative problems (Chapter 1).

4 January 2012 (W): course overview, algorithms in the Times, quickfire data structures review.
Reading: Kleinberg–Tardos, Preface and §1.1.

PS1 is now available on Moodle. Part I is due on Friday; Part II is due on Monday.
6 January 2012 (F): solving stable marriage: brute-force and the Gale–Shapley proposal algorithm.
Reading:§2.1–2.2.

PS2 was handed out today. Part I is due on Wednesday; Part II is due on Friday; Part III is due on Monday.

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

9 January 2012 (M): census; data structures; implementing Gale–Shapley; stable-marriage variants that better model NRMP.
Reading: §2.3–2.5.
11 January 2012 (W): stable marriage wrapup; asymptotics (O, Ω, Θ)
Reading: §3.1
Optional: Jack Edmonds, Paths, Trees, and Flowers. Canadian Journal of Mathematics, 1965.
13 January 2012 (F): asymptotics; graphs.
Reading: §1.2, §3.2–3.3.

PS3 was handed out today. Part I is due on Wednesday; Part II is due on Friday; Part III is due on Monday.

Week 3: greedy algorithms (Chapter 4).

16 January 2012 (M): graph representations; sample problems
Reading: §3.4–3.6
18 January 2012 (W): a parable of Alice and Bob; the "edge-explosion" algorithm; Dijkstra's algorithm.
Reading: §4.4.
20 January 2012 (F): Dijkstra's algorithm; greedy algorithm (interval scheduling).
Reading: §4.1.

PS4 was handed out today. Part I is due on Wednesday; Part II is due on Friday; Part III is due on Monday.

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

23 January 2012 (M): interval scheduling ("greedy stays ahead"); max utilization; deadline scheduling ("exchange arguments").
Reading: §4.2
25 January 2012 (W): minimum spanning trees.
Reading: §4.5–4.6. For optional additional practice with greedy algorithms, read the remainder of Chapter 4.

Our first prelim is scheduled for Monday, 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 (through 27 January 2011 [MSTs] in class, through Problem Set 4, and Chapters 1–4) is fair game for the exam.

Because of the meshing of the exam and ps4 scheduling, I'm giving you all another free late pass to use as you please throughout the term. Enjoy!
27 January 2012 (F): MST wrapup; Fibonacci numbers
Reading: §6.1–6.2.
Optional: wikipedia on the disjoint sets data structure.

Week 5: dynamic programming (Chapter 6).

30 January 2012 (M): prelim #1
PS5 was posted over the weekend. It's all due next Wednesday.
1 February 2012 (W): dynamic programming overview; word segmentation.
Reading: nothing new.
3 February 2012 (F): dynamic programming: weighted interval scheduling; sequence alignment; seam carving.
Reading: §6.6–6.7.
Optionally: NYT on Belichick, and the seam-carving paper and video by Shai Avidan and Ariel Shamir.

Week 6: divide and conquer (Chapter 5).

6 February 2012 (M): midterm break!
8 February 2012 (W): dynamic programming: shortest paths, Bellman–Ford, and a hint of Floyd–Warshall.
Reading: §6.8, 4.4. For optional additional practice with dynamic programming, read the remainder of Chapter 6.

PS6 was posted. It's due on Friday and Monday.
10 February 2012 (F): Floyd–Warshall wrap; divide and conquer: overview and recurrence relations.
Reading: §5.1–5.2.

PS7 was handed out today. Part I is due on Wednesday; Part II is due on Friday; Part III is due on Monday. Part IV is optional.

Week 7: divide and conquer (Chapter 5).

13 February 2012 (M): counting inversions; order statistics.
Reading: §5.3.
15 February 2012 (W): magic 5; closest pairs of points in the plane.
Reading: §5.4; ; wikipedia on selection algorithm, handout on Magic Five.
Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, "Time bounds for selection", 1973 (posted on Moodle).
17 February 2012 (F): closest pair of points; introduction to network flow.
Reading: §7.1.

Week 8: network flow (Chapter 7).

20 February 2012 (M): augmenting paths, residual graphs, Ford–Fulkerson, max flow/min cut.
Reading: §7.2–7.3.

PS8 was handed out today. It's due on Friday, Monday, and Friday.
22 February 2012 (W): max flow/min cut; Edmonds–Karp
Reading: §7.3, §7.5, §7.6.
Optionally, for more practice with network flow, §7.7–7.12
24 February 2012 (F): maximum flow wrapup; bipartite matching; intro to complexity theory.
Reading: §8.1

Week 9: hard problems and reductions (Chapter 8)

27 February 2012 (M): more reductions.
Reading: §8.2–8.3.

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 network flow (so through class on Friday 2/24, and including PS 8) is fair game.
29 February 2012 (W): prelim #2
PS9 was posted today. It's due on Monday (3/5), Wednesday (3/7), and Friday (3/9). Because you will need material that we won't have covered in class until Friday, I'm giving you another free late pass to use for the question due Monday (or Wednesday) if you want to use it. Note that, by college policy, no extensions past the last day of classes are permitted.
2 March 2012 (F): P, NP, NP-Completeness; the Cook–Levin Theorem.
Reading: §8.3–8.4.

Week 10: NP-completeness (Chapter 8).

5 March 2012 (M): NP-completeness: Cook–Levin Theorem, 3SAT, etc.
Reading: §8.4, 8.9.
7 March 2012 (W): NP-completeness: independent set, subset sum, etc.
Reading: §3.4; §8.7, §8.8.
What happened to me and the new girl, from Joey deVilla's The Adventures of Accordion Guy in the 21st Century, 2003.
Optionally: the CLRS Subset Sum proof
Optionally: The Status of the P Versus NP Problem, by Lance Fortnow. Communications of the ACM, September 2009.
9 March 2012 (F): academic honesty and the final; ask me anything.

Finals Period:

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.

Clarifications:

For simplicity, you may assume that there are no edges of weight 0; special cases involving 0-weight edges are not the desired intent of the question. For 1(b), neither you nor p_crush need to take shortest paths.
You're asked to find the total sum of the synergies. There's no requirement of any kind of balance between Florida and Minnesota.
Nothing yet.
A bundle may not contain a single class more than once.
Nothing yet.

CS252 (Algorithms)
Winter 2012, Carleton College

[Jump to current week]

Basic information:

Course Materials: