CS252 (Algorithms)
Winter 2010, 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: network flow (Chapter 7).
Week 8: network flow (Chapter 7); hard problems and reductions (Chapter 8); midterm.
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.
  1. 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.
  2. 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.
  3. 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.)
  4. Any subset X that meets the listed criteria is fine.
  5. 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.
  6. It suffices to return the number of rectangles; you don't have to worry about returning the set itself.