Winter 2007, Carleton College

- Instructor: David Liben-Nowell
- Lecture: 2a (MW 9:50--11:00a, F 9:40--10:40a),
~~CMC 210~~CMC 328. - Office Hours: T10--11a, W2--3p, F 12--1p.

Always feel free to email for an appointment if the scheduled times aren't good for you. - Grader: Daniel Lew (lewda)
- Official catalogue description:
*How to think of good solution methods for solving computational problems and how to find the best methods and prove that they are the best. We'll consider the design and analysis of algorithms: divide and conquer, dynamic programming, greedy method, backtracking, branch-and-bound, and inductive approaches; recurrence relations, applications, complexity theory, NP-completeness.*

- 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 Carleton Sentinel is the mailing list of
the CS community here at Carleton. We'll use it to send occasional
updates on things that might be of interest (talks, summer jobs,
social events, etc.). Sign up here!

There is a form for
office-hours scheduling available. Please fill it out by Friday,
22 December 2006, and I'll schedule office hours soon thereafter. (Be
sure to include your email address!)

We've moved! We'll be in CMC 328 (instead of
CMC 210) for all class meetings.

- 3 January 2007 (W): course overview, stable marriage. Reading: §1.1; NYT on Google.
- 5 January 2007 (F): Gale–Shapley correctness and implementation. Reading: §1.2 (optional), Chapter 2 (which should be review).

Problem Set 1 is due on Monday (Part I) and
Wednesday (Part II).

- 8 January 2007 (M): stable-marriage variants, data-structures issues. Reading: syllabus, Chapter 2, NYT on energy optimization.
- 10 January 2007 (W): asymptotics (and nearest neighbors). Reading: §3.1–3.3, 3.5, NYT on Yahoo local search.
- 12 January 2007 (F): graphs intro/review. Reading: §3.1–3.3, 3.5 (again).

Problem Set 2 is due on Monday (Part I) and
Wednesday (Part II).

Problem Set 3 is due on Monday (Part I) and
Wednesday (Part II).

- 22 January 2007 (M): greedy algorithms, minimum spanning trees. Reading: §4.5–4.7.
- 24 January 2007 (W): minimum spanning trees. Reading: §4.5–4.7.
- 26 January 2007 (F): weighted interval scheduling, memoization, dynamic programming. Reading: §6.1–6.2.

Problem Set 4 is due on Monday (Part I)
~~Wednesday (Part II) and Friday (Part III)~~ and next
week (Parts II and III).

- 29 January 2007 (M): dynamic programming: Fibonnaci numbers, word segmentation, sequence alignment. Reading: §6.6.
- 31 January 2007 (W): dynamic programming: sequence alignment, pretty printing. Reading: §6.8, 4.4, and (optional) §6.10.
- 2 February 2007 (F): dynamic programming: Bellman–Ford shortest paths. Reading: §6.8.

The remainder of Problem Set 4 (Parts II and
III) is due on Tuesday at 5:00p, in my mailbox in the CMC.

Our midterm is scheduled for Monday, 12
February 2007, 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 dynamic programming (so through 2 February 2007 in class,
through Problem Set 4, and Chapters 1–4 and 6) is fair game for
the exam.

- 5 February 2007 (M): midterm break!
- 7 February 2007 (W): divide-and-conquer algorithms, recurrence relations, counting inversions. Reading: §5.1–5.3.
- 9 February 2007 (F): counting inversions, median and order statistics. Reading: wikipedia on select

Problem Set 5 Part I is due on Friday.

- 12 February 2007 (M):
*midterm exam!* - 14 February 2007 (W): magic 5, closest pair of points. Reading: §5.4.
- 16 February 2007 (F): closest pair of points, sorting lower bounds. Reading: §5.4; CLRS §9.1 (handout).

Problem Set 5 Part II is due on Monday.

- 19 February 2007 (M): introduction to network flow. Reading: §7.1–7.2.
- 21 February 2007 (W): Ford–Fulkerson, minimum cuts. Reading: §7.1–7.3.
- 23 February 2007 (F): max flow/min cut, Edmonds–Karp, bipartite matching. Reading: §7.3, 7.5–7.6.

Problem Set 6 is due on Monday (Part I) and
Wednesday (Part II).

The final exam will be a take-home exam. It
will be distributed in class on Friday, 9 March 2007, and it will be
due at 5:00p on Wednesday, 14 March 2007.

- 26 February 2007 (M): disjoint paths; hardness and reducibility. Reading: §7.6, §8.1–8.2.
- 28 February 2007 (W): reductions, reductions, reductions. Reading: §8.1–8.3.
- 2 March 2007 (F): more reductions, NP defined. Reading: §8.3–8.4.

Problem Set 7 is due on Wednesday (Part I) and
Friday (Part II).

- 5 March 2007 (M): NP-completeness; Cook–Levin. Reading: §8.5.
- 7 March 2007 (W): more NP-complete problems. Reading: §8.7–8.8, CLRS handout.
- 9 March 2007 (F): course wrapup, course evaluations, and a smattering of other types of algorithms.

- If you'd like to use LaTeX to type your solutions, you should take
a look at this tutorial.
(You have my official permission to use this tutorial as a resource
for the exam.) LaTeX is installed on the CS machines, and you can use
it by typing
`latex exam.tex`(or whatever). - In Question 3, "whether
*G*contains two paths" means "whether*G*contains*at least*two paths" - In Question 4, a point of emphasis: your solution needs to run in
*O(n)***worst-case**time. - In Question 1, "augment" in this context just means simply increment the amount of flow (by one) crossing every edge in the path.

The take-home final is due **Wednesday, 14
March 2007 at 5:00p** in my mailbox on the second floor of the
CMC.