cs252-00-w15: Algorithms
Winter 2015, Carleton College

Basic Information

• Instructor: David Liben-Nowell
• Office Hours: see my homepage. Always feel free to email for an appointment if the scheduled times aren't good for you.

• This webpage was originally stored in Moodle, which does not have an easy capacity to publish a version of an old webpage for a course. Major thanks to Dave Musicant, whose Moodle-scraping tool I used to generated this page, which is an approximation of the original.

Course Materials:

Anonymous feedback form

Some useful LaTeX resources

Piazza

Week 1:

Monday:  course overview, algorithms in the Times, course logistics.

1. Reading: Kleinberg–Tardos, Preface; cs201-in-one-page handout.
2. ps1 is now available.  Part I is due on Wednesday; Part II is due on Friday.

Wednesday:  state health-care emulation; stable marriage.

1. Reading:  Kleinberg–Tardos, §1.1, §2.1–2.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.

Friday:  solving stable marriage: brute-force and the Gale–Shapley proposal algorithm.

1. Reading: Kleinberg–Tardos, §2.3–2.5.

Week 2:

Monday: stable-marriage variants that better model the NRMP; stable marriage wrapup.

1. Reading: §3.1; asymptotics-overview notes.
2. Optional (but skim page 1): Jack Edmonds, Paths, Trees, and Flowers. Canadian Journal of Mathematics, 1965.
3. Optional: Anna Maria Barry-Jester, Another 34,000 People Are About To Put Their Future In the Hands Of An Algorithm. FiveThirtyEight, 2015.

Wednesday:  census; data structures; asymptotics (O, Ω, Θ).

1. Reading: Kleinberg–Tardos, §1.2, §3.2–3.3.
2. PS3 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.

Friday:  graph representations; sample problems.

1. Reading: Kleinberg–Tardos, §3.4–3.6.

Week 3:

Monday:  BFS/DFS, a field trip to the art installation in the Boliou lobby.

1. Reading: Kleinberg–Tardos, §4.4.

Wednesday:  ricochet robots; the "edge-explosion" algorithm; Dijkstra's algorithm.

1. Reading: Kleinberg–Tardos, §4.1.
2. PS4 was handed out today. Part I is due on Monday; Part II is due on Wednesday; Part III is due on Friday.

Friday:  Dijkstra's algorithm wrapup; greedy algorithms; interval scheduling.

1. Reading: Kleinberg–Tardos, §4.2.
2. Because we're a little behind where I'd hoped we'd be, you're a little underprepared for ps4 right now.  So I'm giving you all one extra late pass to use at a time of your choice sometime in the term (probably for the first question of ps4, but it's up to you).

Week 4:

Monday:  max utilization; deadline scheduling ("exchange arguments").

1. Reading: Kleinberg–Tardos, §4.3, optionally.

Wednesday:  deadline scheduling; minimum spanning trees.

1. Reading: Kleinberg–Tardos, §4.5–4.6.
2. Optional reading:  the remainder of Kleinberg–Tardos Chapter 4 (for extra practice).
3. PS5 was handed out today.  Part I is due Monday; Part II is due Wednesday.

Friday:  MSTs: Reverse-Delete, Kruskal's, Prim's, Borůvka's, and Karger's algorithms.

1. Reading: minimum-spanning-trees notes.
2. Optional: David Karger, Philip Klein, and Robert Tarjan, A randomized linear-time algorithm to find minimum spanning trees, JACM, 1995; and Jeff Erickson, Notes on Disjoint Sets data structures.
3. Our first prelim 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. Any material up to and including greedy algorithms (ps05, class today and any spillover to Monday, KT through Chapter 4) is fair game for the exam.

Week 5:

Monday:  Karger's algorithm for MSTs.

1. Reading:  Kleinberg–Tardos, §6.1–6.2.
2. Reminder:  prelim #1 on Friday.

Wednesday:  dynamic programming; word segmentation.

1. Reading: Kleinberg–Tardos, §6.6–6.7.
2. PS6 was handed out today. Part I is due on Wednesday; Part II is due on Friday.
3. Reminder:  prelim #1 is next class!

Friday:  prelim #1!

Week 6:

Monday:  midterm break!

Wednesday:  dynamic programming: sequence alignment; shortest paths in a matrix; weighted interval scheduling; seam carving; 

1. Reading: Kleinberg–Tardos, §6.8, 4.4.
2. Optional reading: the seam-carving paper and video [vimeo.com/1347424] by Shai Avidan and Ariel Shamir.

Friday:  midterm course evals; dynamic programming: Bellman–Ford, Floyd–Warshall, the Fibonacci numbers.

1. Reading:  Wikipedia on Floyd–Warshall.
2. Optional reading: For optional additional practice with dynamic programming, read the remainder of Chapter 6.
3. More optional reading: NYT on Belichick.
4. PS7 was handed out today.  Part I is due on Wednesday; Part II is due on Friday; Part III is due on Monday.  There's a totally optional extension question, which is due by Monday if you choose to submit it.

Week 7:

Monday:  dynamic programming wrapup (solving problems via shortest paths?); divide and conquer.

1. Reading: Kleinberg–Tardos, §5.1, 5.2; notes on recurrence-relations.

Wednesday:   divide and conquer: recurrence relations; master method; pop quiz!

1. Reading: Kleinberg–Tardos, §5.3.

Friday:  counting inversions; order statistics.

1. Reading: Kleinberg–Tardos §5.4.
2. PS8 was handed out today. Part I is due on Wednesday; Part II is due on Friday.  The optional questions, if you choose to do them, are also due by Friday.

Week 8:

Monday:  order statistics; randomized select; magic five.

1. Reading: wikipedia on selection algorithm; posted magic-five notes.
2. Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, "Time bounds for selection", 1973.

Wednesday:  D&C wrap (closest points in the plane, Fibonacci); intro to network flow.

1. Reading: Kleinberg–Tardos §7.1.
2. I'm pushing back the second due date from ps8 until Monday.
3. Our second prelim 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.

Friday:  network flow: cuts, Zachary's Karate Club, Ford–Fulkerson.

1. Reading: Kleinberg–Tardos §7.2–7.3.
2. Reminder:  prelim #2 is a week from today.
3. PS9 was handed out today.  It's due on Wednesday, Monday, and Wednesday (nothing is due on the day of the second prelim).

Week 9:

Monday:  max flow/min cut.

1. Reading: review Kleinberg–Tardos, §7.3; start §7.5.
2. Reminder:  prelim #2 is on Friday.  Any material up to and including class today is fair game.  (I'm aware that you'll have started but not finished ps9, so the material that directly overlaps with class is fair game, but I won't ask anything that relies on you knowing any particular question in detail.)

Wednesday:  applications of max flow/min cut.  [vimeo.com/1370561]

1. Reading:  Kleinberg–Tardos, §7.5.  For extra practice, read the rest of Chapter 7.
2. Reminder:  prelim #2 next class!

Friday:  prelim #2!

Week 10:

Monday:  connecting algorithms and CS 254; approximation algorithms.

1. Optional reading: Kleinberg–Tardos, §8.0, 8.3, 9.1. Wikipedia on P vs. NP.
2. The final for this course will be held on Saturday, March 14th, 12:00pm–2:30pm, in our regular classroom Olin 149.
3. No late days allowed past Wednesday; all homework must be submitted by 5:00pm on the last day of class.

Wednesday:  course evaluations; ask me anything.