CS252 (Algorithms)
Winter 2012, 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).
Week 8: network flow (Chapter 7).
Week 9: hard problems and reductions (Chapter 8)
Week 10: NP-completeness (Chapter 8).
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:

  1. 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 pcrush need to take shortest paths.
  2. You're asked to find the total sum of the synergies. There's no requirement of any kind of balance between Florida and Minnesota.
  3. Nothing yet.
  4. A bundle may not contain a single class more than once.
  5. Nothing yet.