Basic information:
- 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.
Course Resources:
- 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.
Course Materials:
Week 0:
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!)
Week 1:
introduction to 227, algorithms, and some representative problems (Chapter 1).
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).
Week 2:
review of asymptotics, proofs of correctness, and graphs (Chapters
2 and 3).
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).
Week 3:
greedy algorithms (Chapter 4).
Problem Set 2 is due on Monday (Part I) and
Wednesday (Part II).
- 15 January 2007 (M): Review of BFS/DFS (animations: BFS, DFS, BFS/DFS).
Reading: §4.4.
- 17 January 2007 (W): Dijkstra's algorithm (animations: Dijkstra
[1,
2]).
Reading: §4.1–4.2.
- 19 January 2007 (F): greedy algorithms. Reading:
§4.1–4.2.
Week 4:
greedy algorithms and dynamic programming (Chapters 4 and 6)
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.
Week 5:
dynamic programming (Chapter 6)
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.
Week 6:
divide and conquer (Chapter 5)
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
Week 7:
divide and conquer (Chapter 5)
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).
Week 8:
network flow (Chapter 7).
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.
Week 9:
hard problems and reductions (Chapter 8)
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.
Week 10:
NP-completeness (Chapter 8)
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.
Finals Period:
Resources/clarifications for the final:
- 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.