CS252 (Algorithms)
Winter 2011, Carleton College

[Jump to current week]

Basic information:

Course Materials:

Week 1: intro to 252, algorithms, and some representative problems (Chapter 1).
Week 2: review of asymptotics, proofs of correctness, and graphs (Chapters 2 and 3).
Week 3: greedy algorithms (Chapter 4).
Week 4: greedy algorithms and dynamic programming (Chapters 4 and 6).
Week 5: dynamic programming (Chapter 6).
Week 6: divide and conquer (Chapter 5).
Week 7: divide and conquer (Chapter 5); network flow (Chapter 7)
Week 8: network flow (Chapter 7).
Week 9: hard problems and reductions (Chapter 8)
Week 10: wrapup
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.
  1. You do not need to maintain the vertical "order" of nodes; you can place nodes in any configuration as long as the nodes and edges are intact. (Think of the root as being a specially marked node, so that "height" is determined by graph distance from the root.)

    An edge (u,v) cannot pass through any node other than u and v.

  2. Nothing yet.
  3. You may assume that the inputs b and d are both given as arrays indexed by town number.
  4. Nothing yet.