**Instructors: **

Avrim Blum, avrim+@cs.cmu.edu, Wean 4107, x8-6452. Office hours: Thurs 1:30-2:30.

Danny Sleator, sleator+@cs.cmu.edu, Wean 4128, x8-7563. Office hours: Tues 2:00-3:00.

**Teaching Assistants: **

Nick Hopper, hopper+@cs.cmu.edu, Wean 8303, x8-2993. Office hours: Thurs 3:30-4:30.

Dan Tennant, dkt+@andrew.cmu.edu, Wean 3108, x8-4008. Office hours: Wed 3:30-4:30.

Mike Bowling, mhb+@cs.cmu.edu, Wean 8121, x8-3069. Office hours Tues 10:00-11:00am.

**Course Secretary: **

Dorothy Zaborowski, daz@cs.cmu.edu, Wean 4116, x8-3779.

**Lectures: **Tues/Thurs 12:00-1:20. Wean Hall 7500

**Recitations: **

- Rec A: Wed 12:30 (SH 220) - Nick Hopper/Mike Bowling
- Rec B: Wed 1:30 (CFA A6) - Danny Sleator/Dan Tennant
- Rec C: Wed 2:30 (PH 226A) - Dan Tennant/Danny Sleator
- Rec D: Wed 3:30 (BH 255A) - Mike Bowling/Nick Hopper

**Course Home page:**
http://www.cs.cmu.edu/afs/cs/academic/class/15451-f00/www/

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:** The main electronic bulletin board for this course
is the newsgroup `cmu.cs.class.cs451`. It will
be used for announcements by the course staff on such subjects as
reading assignments, topics of upcoming lectures, corrections to
homework assignments, etc. Please read it frequently.
You can also post on the bboard by sending email to: `outnews+netnews.cmu.cs.class.cs451@ANDREW.CMU.EDU`

**Grading:** Grading will be based on 7 problems sets (homeworks), two
short in-class quizzes, an in-class midterm, and a final. The
homeworks are worth 6% each (for a total of 42%), the quizzes
6% each, the midterm 16%, and the final 30%.

**Important Dates:**
The first quiz (1/2 hour) will be on Sept 26. The midterm will be
Oct 17. The 2nd quiz (1/2 hour) will be Nov 9. The date of the
final is not yet known.
A detailed course schedule is available
from the course home page.

**Homework**:
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. - Typed homework is not required, but we don't discourage it. It is your responsibility to make sure your handin is legible. If you want to use LaTeX, see the sample template files on the course web page.

- You must do the oral-presentation homeworks in groups of three. 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 TAs.
- Presentations will be given in 1-hour time slots (there will be an 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 group. In the last 15 minutes, the instructor (or TA) will hand back to you your previous written assignment and give you feedback on it.
- If you are uneasy about your presentation skills, you may in addition hand in a written sketch of your solution to accompany your presentation. We will then take this writeup into consideration in determining your grade on the assignment.

**Readings**: The textbook is *Introduction
to Algorithms: a Creative Approach*, by Udi Manber.
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
textbook.

**Other helpful material:** Other useful material
can be found in: *Data Structures and Network Algorithms *by R. E.
Tarjan, *Algorithmics: Theory and Practice* by Brassard and
Bratley, *Randomized Algorithms* by Motwani and Raghavan,
*Programming Pearls *by J. Bentley, *The Design and
Analysis of Computer Algorithms* by Aho, Hopcroft and
Ullman, and *Introduction to Algorithms* by Cormen,
Leiserson, and Rivest (known as CLR).