CS252 (Algorithms) Winter 2010, Carleton College

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

4 January 2010 (M): course overview, algorithms in the Times, quickfire data structures review, stable marriage.
Reading: Preface and §1.1.

PS1 was handed out today. Part I is due on Wednesday; Part II is due on Friday.
6 January 2010 (W): solving stable marriage: brute-force and the Gale–Shapley proposal algorithm.
Reading: §1.1, §2.1–2.2.

PS2 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.
8 January 2010 (F): data structures; implementing Gale–Shapley; stable-marriage variants that better model NRMP.
Reading: §2.3–2.5.

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

11 January 2010 (M): asymptotics (O, Ω, Θ); efficiency=polytime
Reading: §3.1
13 January 2010 (W): graph definitions and some sample graph problems.
Reading: §1.2, §3.2–3.5.

PS3 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.
15 January 2010 (F): a BFS/DFS refresher; shortest paths in weighted graphs.
Reading: §3.4–3.6

Week 3: greedy algorithms (Chapter 4).

18 January 2010 (M): the "edge-explosion" algorithm; Dijkstra's algorithm, "reducing in the wrong direction".
Reading: §4.4.
20 January 2010 (W): interval scheduling ("greedy stays ahead").
Reading: §4.1–4.2. And, if you please, a philosophical diversion on defining "greedy"

PS4 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.
22 January 2010 (F): deadline scheduling ("exchange arguments").
Reading: §4.5–4.6. For optional additional practice with greedy algorithms, read the remainder of Chapter 4.

Our first midterm is scheduled for next Friday, 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 2010 in class, through Problem Set 4, and Chapters 1–4) is fair game for the exam. If you would like to submit your last solution for Problem Set 4 by next Thursday afternoon, I will be happy to give you an prepublication copy of the PS4 solution set.

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

25 January 2010 (M): minimum spanning trees.
Reading: review Chapter 4; start Chapter 6 if you please.
27 January 2010 (W): dynamic programming: Fibonacci numbers, word segmentation.
Reading: §6.1–6.2.

PS5 was handed out today. ~~Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.~~ Part I is due on Wednesday; Part II is due on Friday; Part III is due on Wednesday (after midterm break).
29 January 2010 (F): midterm #1

Week 5: dynamic programming (Chapter 6).

1 February 2010 (M): dynamic programming: word segmentation; seam carving.
Reading: §6.6–6.7; if you please, NYT on Belichick, and the seam-carving paper by Shai Avidan and Ariel Shamir.
3 February 2010 (W): dynamic programming: seam carving; sequence alignment; shortest paths revisited.
Reading: §6.8, 4.4. For optional additional practice with dynamic programming, read the remainder of Chapter 6.
5 February 2010 (F): dynamic programming: shortest paths, Floyd–Warshall, Bellman–Ford.
Reading: §5.1–5.2.

PS6 was handed out today. It's due next Friday.

Week 6: divide and conquer (Chapter 5).

8 February 2010 (M): midterm break!
10 February 2010 (W): divide-and-conquer algorithms, recurrence relations, and counting inversions.
Reading: §5.1–5.3.

PS7 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday. Part IV, if you choose to complete it, is due a week from Monday.
12 February 2010 (F): median and order statistics; randomized select; the "magic five" algorithm.
Reading: §5.4; 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.)
Optionally: notes on randomized select by Vijaya Ramachandran.

Week 7: network flow (Chapter 7).

15 February 2010 (M): closest pairs of points in the plane; introduction to network flow.
Reading: §7.1.
17 February 2010 (W): augmenting paths, residual graphs, Ford–Fulkerson.
Reading: §7.1–7.2.
19 February 2010 (F): max flow/min cut.
Reading: §7.2–7.3.

PS8 was handed out today. Part I is due on Wednesday; ~~Part II is due on Friday; Part III is due next Monday~~ Part II is due next MondayFriday; Part III is due next Wednesday.

Our second midterm is scheduled for Friday, 26 February 2010, 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 2010 in class, through Problem Set 8, and Chapters 1–7) is fair game for the exam.

Week 8: network flow (Chapter 7); hard problems and reductions (Chapter 8); midterm.

22 February 2010 (M): Edmonds–Karp, applications of network flow.
Reading: §7.3, §7.5, §7.6.
Optionally, for more practice with network flow, §7.7–7.12
24 February 2010 (W): reductions.
Reading: §8.1

Note updated due dates for PS8. Part I is due today; ~~Part II is due on Friday; Part III is due next Monday~~ Part II is due next Monday; Part III is due next Wednesday. If you submit the entire assignment by Thursday, I'll give you a copy of my solution set (for your eyes only).
26 February 2010 (F): midterm #2

Week 9: hard problems and reductions (Chapter 8)

1 March 2010 (M): more reductions.
Reading: §8.2.

PS9 was handed out today. Part I is due on Friday; Part II is due next Monday; Part III is due next Wednesday.
3 March 2010 (W): P and NP.
Reading: §8.3–4.
5 March 2010 (F): Cook–Levin Theorem and NP-completeness.
Reading: §8.9; §8.10 (for the difference between NP and coNP); §8.5–8.6 (for more practice).

Week 10: NP-completeness (Chapter 8).

8 March 2010 (M): NP-completeness: subset sum, graph coloring.
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.
The Status of the P Versus NP Problem, by Lance Fortnow. Communications of the ACM, September 2009.
10 March 2010 (W): mountains of miscellenea: 3-coloring, course evals, approximation algorithms, take-home.

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:

If you'd like to consider the decision version of the question on #1 (not the optimization version), that is fine with me. Just state what you're doing explicitly.
Think of monetary exchange as directed. If WOS A paid $3 to WOS B, and WOS B paid $2 to WOS A, then separating A and costs $5 (5=3+2). (Yes, it would be possible to change this situation to A pays B $1 and B pays A nothing without affecting the WOSes' bottom lines, but don't assume that's been done.)
Also, when I say "amount of WOS-to-WOS transactions", I mean the total dollar amount of those transactions. That's different from the "number of WOS-to-WOS transactions". So it's total dollars, not total number of transactions, that you're trying to minimize.
Assume that P and J are given to you as lists. (Note for the record that the problem does not say that P and J are disjoint, or that every node is in either P or in J.)
Any subset X that meets the listed criteria is fine.
You may assume that you can compare two names in O(1) time, but that's it. Here's the unambiguous restatement of the conditions of the kind of solution I'm looking for: (a) You have the ability to compare two names from the arrays (<, >, or =). (b) No other operations on the names is permitted.
It suffices to return the number of rectangles; you don't have to worry about returning the set itself.

CS252 (Algorithms)
Winter 2010, Carleton College

[Jump to current week]

Basic information:

Course Materials: