Lecture: 3a (MW 11:10a--12:20p, F 12:00--1:00p), Laird 206.
Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
Official catalogue description:
A course on techniques used in the design and analysis of efficient
algorithms. We will cover several major algorithmic design paradigms
(greedy algorithms, dynamic programming, divide and conquer, and
network flow); applications of those techniques to a variety of
domains (natural language processing, economics, computational
biology, and data mining, for example); and computational complexity,
particularly NP-completeness, including how to cope algorithmically
when confronted with intractable problems. Prerequisites: CS 201; Math
111; CS 202 or Math 236.
Course Materials:
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!
PS5 was handed out today. Question #1 is due in
one week. Question #2 is due next Friday.
Our first prelim is scheduled for Monday, 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. I may ask you to
hand in your crib sheet with your exam. Any material up to and
including greedy algorithms (through 26 January 2011 [MSTs] in class, through
Problem Set 4, and Chapters 1–4) is fair game for the
exam.
28 January 2011 (F):
dynamic programming: word segmentation; seam carving.
PS6 was handed out today. It's due Wednesday
and Friday.
Because we're slightly behind in class
relative to where I'd thought we'd be, I'm giving you all another free
late pass to use as you please throughout the term. Enjoy!
4 February 2011 (F):
dynamic programming: shortest paths, Floyd–Warshall,
Bellman–Ford.
Reading: §6.8, 4.4. For optional
additional practice with dynamic programming, read the remainder of
Chapter 6.
Week 6:divide and conquer (Chapter 5).
7 February 2011 (M): midterm break!
9 February 2011 (W): Floyd–Warshall wrap; divide and
conquer: overview and recurrence relations.
Reading: §5.1–5.2.
PS7 was handed out today. Part I is due on
Monday; Part II is due on Wednesday; Part III is due on Friday. Part
IV is optional.
11 February 2011 (F):
counting inversions; order statistics.
Reading: §5.3; wikipedia on selection
algorithm.
Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan,
"Time bounds for selection", 1973. (Posted in the Courses folder for
CS252.)
Week 7:divide and conquer (Chapter 5); network flow (Chapter 7)
14 February 2011 (M): magic 5; closest pairs of points in the plane.
Reading: §5.4; handout on Magic Five.
16 February 2011 (W): introduction to network flow.
Reading: §7.1–7.2.
PS8 was handed out today. It's due on
Monday, Wednesday, and Friday Wednesday (2/23),
Friday (2/25), and Monday (2/28).
18 February 2011 (F): augmenting paths, residual graphs,
Ford–Fulkerson, max flow/min cut.
Reading: §7.2–7.3.
Week 8:network flow (Chapter 7).
21 February 2011 (M): max flow/min cut; Edmonds–Karp; bipartite matching.
Reading: §7.3, §7.5, §7.6.
Optionally, for more practice with network flow, §7.7–7.12
23 February 2011 (W):
disjoint paths; intro to computational complexity and reductions.
Reading: §8.1
25 February 2011 (F):
more reductions.
Reading: §8.2–8.3.
PS9 was handed out today. It's due on Wednesday
(3/2), Friday (3/4), and Wednesday (3/9).
Week 9:hard problems and reductions (Chapter 8)
28 February 2011 (M):
P and NP.
Reading: §8.3–8.4 (over the next few classes)
We're slightly behind in class, so I'm giving
you all another free late pass to use on ps9. Enjoy!
2 March 2011 (W): P, NP, NP-Completeness; the Cook–Levin Theorem.
Reading: §8.4, 8.9.
Our second prelim is scheduled for Monday, 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. I may ask you to
hand in your crib sheet with your exam. Any material up to and
including NP-Completeness (through 4 March 2011 in class, through
Problem Set 9, and Chapters 1–8) is fair game for the
exam.
4 March 2011 (F): NP-completeness: SAT, subset sum, etc.
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:
You do not need to maintain the vertical "order" of nodes; you
can place nodes in any configuration as long as the nodes and edges
are intact. (Think of the root as being a specially marked node, so
that "height" is determined by graph distance from the root.)
An edge (u,v) cannot pass through any node other than u and v.
Nothing yet.
You may assume that the inputs b and d are both
given as arrays indexed by town number.