CS252 (Algorithms)
Winter 2008, Carleton College


[Jump to current week]

Basic information:

Course Materials:

Week 0:
There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
The CS department has an email newsletter, the Carleton Sentinel, that we use for occasional updates on things that might be of interest. Sign up here!
Week 0.5: intro to 252 (Chapter 1).
Week 1: some representative problems; review of asymptotics, data structures (Chapters 1 and 2).
PS0 is due on Monday.
One question from PS1 is due on Wednesday.
One question from PS1 is due on Friday.
Week 2: review of graphs; greedy algorithms (Chapters 3 and 4).
The last question from PS1 is due on Monday.
One question from PS2 is due on Wednesday.
One question from PS2 is due on Friday.
Week 3: greedy algorithms and dynamic programming (Chapters 4 and 6).
The last question from PS2 is due on Monday. (If you've done optional problems, submit them on Monday as well.)
There will be an information session for the CS major at 4:00p on Tuesday in Hill Lounge (with free food!). Hope to see you there!
One question from PS3 is due on Wednesday.
One question from PS3 is due on Friday.
Our first midterm is scheduled for Wednesday, 30 January 2008, 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 2008 in class, through Problem Set 3 and the MST problem on PS4, and Chapters 1–4) is fair game for the exam.
Week 4: dynamic programming (Chapter 6); midterm exam.
The last question from PS3 is due on Monday.
One question from PS4 is due on Friday.
Week 5: dynamic programming and divide-and-conquer algorithms (Chapters 6 and 5).
Two questions from PS4 are due on Wednesday. You must have completed question #1 from PS4 by Wednesday.
The last question from PS4 is due on Friday.
Week 6: divide and conquer; network flow (Chapters 5 and 7).
One question from PS5 is due on Monday.
One question from PS5 is due on Wednesday.
One question from PS5 is due on Friday.
Week 7: network flow (Chapter 7).
The last question from PS5 is due on Monday.
One question from PS6 is due on Friday.
Our second midterm is scheduled for Wednesday, 27 February 2008, 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 2008 in class, through Problem Set 6, and Chapters 1–7) is fair game for the exam.
Week 8: hard problems and reductions (Chapter 8); midterm exam.
One question from PS6 is due on Monday.
The last question from PS6 is due on Wednesday.
If you would like to see the solution set for PS6 before the exam, you may hand in your PS6 solutions to me by 4:00p on Tuesday, 26 February 2008. I will trade them for a solution set (obviously not to be shared with anyone else).
Week 9: NP completeness (Chapter 8).
Two questions from PS7 are One question from PS7 is due on Wednesday.
One question from PS7 is due on Friday.
Week 10: wrapup and current research in algorithms
The last question from PS7 is The last two questions from PS7 are due on Monday.
Finals Period:
Our scheduled finals slot is on Friday, 14 March 2008, from 7–9:30p.
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.