15-451 Course Information, Fall 2010

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.

Manuel Blum, mblum@cs.cmu.edu, GHC 7205, x8-3742. Office hours: Tue-Thur after class.

Teaching Assistants:
Jeremiah Blocki, jblocki+451@cs.cmu.edu. Office Hours: Monday @ 3:30 PM. GHC 7th floor lounge. Students can email me if they want to meet at a different time.
Anvesh Komuravelli, anvesh+451@cs.cmu.edu. Office Hours: Friday @ 4 PM. GHC 7th floor lounge.
Sarah Loos, sloos+451@cs.cmu.edu. Office Hours: Tuesday @ 11 AM. GHC 7th foor lounge.
Eric Seo, eseo+451@andrew.cmu.edu. Office Hours: Wednesday @ 12:30 PM . GHC 7th floor lounge.
Jon Chu, jechu+451@andrew.cmu.edu. Office Hours: Monday @ 4:30 PM. GHC 7th floor lounge.

Course Secretary:
Nicole Stenger, nstenger@cs.cmu.edu, 412-268-3779. GHC 7129.

Lectures: Tues/Thurs 12:00-1:20. GHC 4401

Rec A: Wed 10:30 AM (WEH 5312) - Jon Chu
Rec B: Wed 11:30 AM (GHC 4211) - Eric Seo
Rec C: Wed 9:30 PM (SH 208) - Sarah Loos
Rec D: Wed 2:30 PM (DH 1211) - Anvesh Komuravelli
Rec E: Wed 3:30 PM (DH 2105) - Jeremiah Blocki

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.

Final Exam: TBA

Course Home page: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www
Check it frequently for announcements and updates, lecture notes, handouts, assignments, solutions, and other goodies.

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:

Important Dates:
The first quiz will be September 21. The midterm will be October 12. The second quiz will be November 11. The date of the final is not yet known. A detailed course schedule is available from the course home page.

There will be a problem set every two weeks. These will alternate between ones that require written answers (homeworks 1, 3, and 6) and ones that require an oral presentation (homeworks 2, 4, and 5). Here are guidelines for each type of assignment.

Written homeworks:
Oral Homeworks:

Mini-homeworks will be handed out on Thursdays, 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. As with written homeworks, you should do minis by yourself -- if you have questions, contact your TA.

The textbook for the course Introduction to Algorithms (Second Edition) by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). If you have a (very) old version of CLRS, known as "CLR", you can use that too. We will be providing lecture notes covering all the material in this course, but we would like you to have a book to give you more detailed coverage (as well as an alternative perspective if you cannot understand what the instructor is saying!). Specific readings are listed on the course schedule. It is recommended that you skim the reading before lecture, with a more thorough read afterwards.

Other helpful material can be found in: Algorithm Design by J. Kleinberg and E. Tardos, Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 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.