15-451 Course Information, Fall 2004
avrim+@cs, Wean 4130, x8-6452. Office hours: Mon 1:00-2:00.
mblum+@cs, Wean 4113, x8-3742. Office hours: Tues, Thurs 1:30-2:00.
dbalcan@cs, Wean 3715, x8-1405. Office hours: Thurs 2:30-3:30.
Nina Balcan, ninamf@cs,
Wean 3715, x8-1405. Office hours: Mon 5:00-6:00.
jonderry@cs, Wean 8201, x8-3898. Office hours: Mon 12:30-1:30.
runting@cs, Wean 3709, x8-5182. Office hours: Mon 1:30-2:30.
Lectures: Tues/Thurs 12:00-1:20. Wean Hall 7500
expected to go to one of the recitation sections.
Recitations are a chance to engage in
more discussion than is usually possible in a large lecture, with a
focus on the process of solving algorithmic problems. Recitations
will often contain new material as well.
- Rec A: Wed 12:30 (SH 222) - Jon Derryberry
- Rec B: Wed 1:30 (SH 222) - Nina Balcan
- Rec C: Wed 2:30 (SH 222) - Doru Balcan
- Rec D: Wed 12:30 (SH 214) - Runting Shi
Course Home page:
Check it frequently for announcements and updates, for copies of
handouts, assignments, solutions, and other goodies. We will also post
outlines of the lecture notes on the web page.
Bboards: There are two bulletin boards for the course:
academic.cs.15-451.discuss is for general discussion, and
academic.cs.15-451 is for staff announcements. Please read them
Grading: Grading will be done as follows:
- homeworks and minis: 45% (7 hwks at 5% each, 5 minis at 2% each)
- quizzes: 10% (2 quizzes at 5% each)
- midterm: 15%
- final: 30%
- class participation: adjust borderline scores
Important Dates: See the course
There will be a problem set every two weeks. These will alternate
between ones that require written answers (hwks 1,3,5,7) and
ones that require an oral presentation (hwks 2,4,6). Here are
guidelines for each type of assignment.
- Written homeworks:
- Written homeworks are due at the start of class on
their due date. You should do each problem on a separate page, with
your name and recitation section at the top of each page. There
will be separate boxes to hand in each problem.
- You should do the homeworks by yourself. This is to be your
- Typed homework is not required, but we don't discourage it.
It is your responsibility to make sure your handin is legible. Latex
(see miktex for Windows machines) is a good typesetting system for
documents with lots of math.
- Lateness Policy: We have adopted the following lateness
policy in order to allow us to post solutions soon after the due date.
- later in the same day: 10% off
- 1-2 days late: 25% off
- more than 48 hours late: 75% off
- Oral Homeworks:
- The oral-presentation homeworks will be done in groups of
Each of these assignments will consist of three problems. The members
of your group will work together to solve the problems and you will
then present your solutions, as a group, to one of the instructors or
- Presentations will be given in 1-hour time slots (there will
electronic sign-up sheet reachable from the course home page). At the
presentation, each member of the group will spend 15 minutes presenting
one of the problems. The instructor (or TA) will decide who presents
which problem, but when one member is presenting,
other members are allowed to chime in too. In the end, the three
presentations together will determine the grade for the
- If you are nervous about your presentation, you may
in addition hand in a written sketch of your solution as well.
We will then take this writeup into
consideration in determining your grade on the assignment.
Minis: Mini-homeworks will be made available on the course
web page on Friday, and will be due via email to your TA by the
upcoming Tuesday night . These will typically be practice-type
problems or sometimes may consist of a single open-ended question to
think about. Unlike the regular homeworks, these are intended to
require at most one hour of work. If you are taking more time than
that, please let one of us know.
Readings: The textbook is Introduction to Algorithms
(Second Edition), by Cormen, Leiserson, Rivest, and Stein. Specific
readings are listed on the course schedule. It is recommended that you
skim the reading before lecture, with a more thorough read afterwards.
We will also provide lecture
notes and other handouts for material that is not covered by the
Other helpful material can be found in: Data Structures
and Network Algorithms by R. E.
Tarjan, Randomized Algorithms by Motwani and Raghavan, Programming
Pearls by J. Bentley, Introduction to Algorithms: a Creative
Approach by Manber, and the classic Aho-Hopcroft-Ullman book.