Lecture: 1a (MW 8:30--9:40a, F 8:30--9:30a), Boliou 104.
Office Hours: Monday 9:45.10:45am, Thursday 10:00.11:00am, and by appointment. To make an appointment, give me at least 24 hours of notice, and list several times that you would be available to meet in your email.
Nick's office hours: Tuesday and Friday, 10:00.11:30a, in CMC 307.
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). Along the way, we will explore the application of these
techniques to a variety of domains (natural language processing,
economics, computational biology, and data mining, for example). As
time permits, we will include supplementary topics like randomized
algorithms, advanced data structures, and amortized analysis.
Prerequisites: CS 201; CS 202 or Math 236.
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!
30 January 2013 (W): MSTs: Reverse-Delete, Kruskal's, Prim's,
Borůvka's, and Karger's algorithms.
Our first prelim is scheduled for next
Wednesday, 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 is fair game for the exam.
13 February 2013 (W):
dynamic programming: Bellman–Ford, and Floyd–Warshall.
midterm course evals.
Reading: Kleinberg–Tardos, §5.1, 5.2. For
optional additional practice with dynamic programming, read the
remainder of Chapter 6.
15 February 2013 (F):
seam carving (via Bellman–Ford, Floyd–Warshall, and custom DP);
divide and conquer;
Reading: posted notes on recurrences.
PS7 was posted. It's due on Wednesday,
Friday, and Monday Friday, Monday, and Wednesday.
Week 7:divide and conquer (Chapter 5).
18 February 2013 (M):
divide and conquer: recurrence relations (overview; master method; Karger's algorithm).
Reading: Kleinberg–Tardos, §5.3.
20 February 2013 (W):
counting inversions; order statistics.
Reading: Kleinberg–Tardos, §5.4;
handouts posted on Moodle (inversions, order statistics).
22 February 2013 (F):
randomized select; magic 5
Reading: wikipedia on selection
algorithm; posted magic-5 and closest-pair-of-points handout on Moodle.
Optionally: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan,
"Time bounds for selection", 1973 (posted on Moodle).
Week 8:network flow (Chapter 7).
25 February 2013 (M): D&C wrap (magic 5, closest points in
the plane); network flow.
PS8 was handed out today. It's due on
Friday and MondayMonday and Wednesday.
The second exam is scheduled for Wednesday, in
class. You may bring one 8.5"-by-11" sheet of paper
containing notes handwritten or typed by you. You may write on both
sides of the paper. Any material up to and including class on Friday
3/1 and ps8 is fair game.
8 March 2013 (F): bipartite matching; connecting algorithms and CS 254. [choose your own adventure]
Reading: Kleinberg–Tardos, §8.0,
8.3, 9.1. Wikipedia
on P vs. NP.
The final will be self
scheduled. You may use a one-page crib sheet for the exam, as for
the previous two exams. You must hand write or type the crib sheet
yourself. Because of the registrar's deadline for self scheduled
exams, to use a crib sheet, you must file your crib sheet in your exam
envelope BY NOON ON TUESDAY 12 MARCH. The box for these crib sheets
is in CMC 307 and will be there on Tuesday morning (and late-ish on
11 March 2013 (M): course evaluations; ask me anything.