**Overview:**- This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. Algorithm design tools we will discuss include Dynamic Programming, Divide-and-Conquer, Data Structure design principles, Randomization, Network Flows, Linear Programming, and the Fast Fourier Transform. Some analytical tools we will discuss and use include Recurrences, Probabilistic Analysis, Amortized Analysis, and Potential Functions. We will also discuss a bit of Complexity Theory (which looks at the intrinsic difficulty of computational problems) as well as Cryptography and Algorithmic Game Theory.
**Instructor:**- Manuel Blum, mblum+@cs, Wean 4113, x8-3742. Office hours: 2:30-3:30 Monday, 2-3(or until there are no questions) TTh
**Teaching Assistants:**- Brent Bryan, bryanba@cs, NSH 3123, x8-3076. Office hours: 10-11 Friday
- Elisabeth Crawford, alg.section.b@gmail, Wean 8201, x8-3898. Office hours: 9:30-10:30 Thursday
- Michelle Goodstein, mgoodste@cs, Wean 4126, x8-1188. Office hours: 3:30-4:30 Thursday
- Virginia Vassilevska, alg.section.b@gmail, Wean 3706, x8-1023. Office hours: 7-8pm Thursday
**Course Secretary:**- Amelia Williams, ameliaw@cs.cmu.edu, Wean 4114.
**Lectures:**Tues/Thurs 12:00-1:20. Wean Hall 7500**Recitations:**- Rec A: Wed 1:30 (DH1211) - Michelle
- Rec B: Wed 2:30 (SH 214) - Elisabeth/Virginia (shared)
- Rec C: Wed 3:30 (SH 220) - Brent

Everyone is
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.

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

Check it frequently for announcements and updates, lecture notes,
handouts, assignments, solutions, and other goodies.

**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 use them and
read them frequently.

**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
schedule.

**Homework**:- There will be a problem set every two weeks. These will alternate
between ones that require
*written answers*(homeworks 1, 3, 5, and 7) and ones that require an*oral presentation*(homeworks 2, 4, and 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 try to do the homeworks by yourself.*If you get stuck, come see the TAs or instructor. Clarification questions can also be posted to the bboards. While we encourage you to do the work yourself, you may work with other students, or consult other sources, as long as you properly cite where you received the information and write all homeworks in your own words.*Even if you do the homework alone, you need to cite yourself as the source for your ideas.*- 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. We consider Thursday noon to be 2 days late when assignments are due at noon Tuesday.
- more than 2 days late: 75% off

(at this point solutions will be posted and you may look at them, though anything handed in should be put into your own words)

**Oral Homeworks:**- The oral-presentation homeworks will be done 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 (so, unlike
written homeworks, here collaboration is
*required*) 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.
- 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.

- The oral-presentation homeworks will be done 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 (so, unlike
written homeworks, here collaboration is

**Minis**: Mini-homeworks will typically be made available
on Thursday, and due *via email
to your TA by the upcoming Tuesday night *. These will
usually 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. You should be able to do minis by yourself in one hour--
if you have questions, contact your TA. We will use the following lateness policy.
Minis that are turned in up to one day late are worth up to 50% credit, after one day late they are worth 0.

Questions concerning graded material should be presented in a timely fashion (within a week of return) if you wish a grade to be reconsidered.

**Textbook**: We will not be requiring the purchase of a
textbook. However, a book that covers much of the material in
this course and that we have used in previous years is the text
*Introduction to Algorithms (Second Edition)* by Cormen,
Leiserson, Rivest, and Stein (hereafter referred to as
"CLRS"). A new book 'Algorithms' by Dasgupta, Papadimitriou, and Vazirani (hereafter
referred to as "DPV"),
is good at presenting the high-level ideas. We will be providing lecture notes
covering all the material in this course, but if you would like
a book with more detailed description of the material
(as well as an alternative perspective when the lectures get confusing)
these are two that we
recommend. The course
schedule contains readings from CLRS, DPV and
one other (Kleinberg and Tardos) that correspond to the course lectures.

**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.
Another new book that is quite good is
*Algorithm Design* by Kleinberg and Tardos (hereafter
referred to as "KT"). It covers less but is more
in-depth in certain topics. We will be suggesting readings from this text as well as CLRS and DPV.