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

**Instructors:**

- Pittsburgh: Manuel Blum, mblum@cs.cmu.edu, Wean 4113, x8-3742. Office hours: Mondays from 1:30 to 2:30pm.
- Qatar: Yonina Cooper, yonina@cs.cmu.edu

**Teaching Assistants:**

- Dafna Shahaf, _dshahaf+451@cs.cmu.edu. Office: 3703 Wean, x8-7375. Office hours: Mondays from 4:30 to 5:30pm.
- Bryant Lee, bryantl@cs.cmu.edu. Office: 1315 Wean. Office hours: Tuesdays from 11am to 12pm
- Dan Nuffer, dnuffer@andrew.cmu.edu. Office hours: Wean 8th floor couches, Thursdays from 4:30 to 5:30
- Andrew Warshaver, awarshav@andrew.cmu.edu. Office hours: Wean Hall 3108, Wednesdays from 2:30 to 3:30pm.
- Evan Hoke, ehoke@andrew.cmu.edu

**Course Secretary:**

ameliaw@cs.cmu.edu Wean 4114, x8-7897.

**Lectures:**

Tuesday/Thursday 12:00-1:20, Wean Hall 7500.

**Recitations:**

- Rec A: Wed 1:30 (SH 222) – Andrew Warshaver
- Rec B: Wed 2:30 (SH 214) -, Dan Nuffer
- Rec C: Wed 3:30 (Wean 5302) - Bryant Lee

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.

**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:**

- Homeworks and minis: 45% (7 homeworks at 5% each, 5 minis at 2% each)
- Quizzes: 10% (Two 30 min. quizzes at 5% each)

- Midterm: 15%

- Final: 30%

- Class participation: adjust borderline scores

**Important Dates:**

The first quiz will be Tuesday February 19th. The midterm will be Tuesday March 4th. The second quiz will be Thursday April 10th. The Final Exam is on Cinco de May (May 5th) from 5:30 to 8:30pm. A detailed course schedule is available.

**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 do the homeworks by yourself. What you hand in is to be your own work. If you get stuck, come see the TAs or instructor. Clarification questions can also be posted to the bboards.

- 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

- One to two days (up to 48 hours) late: 25% off

- More than 48 hours 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)

- Later in the same day: 10% off

**Textbook:**

The course will closely follow Avrim Blum’s lecture notes, which will be handed out in class (or pick up from Amy Williams, the course secretary, in 4114 Wean).

The textbook for the course is 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. While we will be providing lecture notes covering all the material in this course, 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 Abo-Hopcroft-Ullman book.