15-451/651 Algorithms
Course Information, Fall 2013

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. We will also discuss a bit of Complexity Theory (which looks at the intrinsic difficulty of computational problems) as well as some Algorithmic Game Theory, Computational Geometry, and Machine Learning.

By the end of this course, you should be able to:

• Use and explain algorithm design tools discussed including Divide-and-Conquer, Hashing, Randomization, Dynamic Programming, Network Flows, Linear Programming, Reduction, and the Fast Fourier Transform, as well as basic algorithm design principles.
• Use and explain analytical tools and frameworks discussed including Recurrences, Probabilistic Analysis, Minimax Optimality, Amortized Analysis, analysis within different Concrete Models, and Potential Functions.
• Understand and explain important concepts in Complexity Theory including NP, Co-NP, NP-Completeness, and reductions.
• Identify and critique incorrect analyses, finding counterexamples to faulty claims and "proofs" of correctness.

Instructors:

Avrim Blum, avrim@cs, GHC 8111. Office hours: Wed 2:00-4:00.

Anupam Gupta, anupamg@cs, GHC 7203. Office hours: Tue 4:00-6:00.

Course Secretary:

Marilyn Walgora, mwalgora@cs, GHC 8120 , x8-3505.

Teaching Assistants:

Miguel Araujo, maraujo@cs. Office hours: Tue 10:30am. Location GHC 8023.

Michael Arntzenius (rntz), marntzen@andrew. Office hours: Wed 3:30-5:30pm. Location GHC 8129.

Eugene Choi, dechoi@andrew. Office hours: Mon 2:30pm. Location GHC 4122.

Paul Davis, pauldavi@andrew. Office hours: Sun 6:00 pm. 3rd floor Gates, by window facing Wean

Kristy Gardner, ksgardne@cs. Office hours: Sun 5:00-6:00pm GHC 4101, Thurs 5:00-6:00pm GHC 4102.

Andrea Klein, andreakl@andrew. Office hours: Wed 5:30pm. Location GHC 4211.

Yuzi Nakamura, ynakamur@cs. Office hours: Fri 3:30pm. GHC 7513.

Kevin Su, ksu@andrew. Office hours Mon 11:30am. Location GHC 4162.

Office Hours:

Sunday	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday
5P (Kristy, GHC 4101) 6P (Paul, 3rd floor Gates)	11:30A (Kevin, GHC 4162) 2:30P (Eugene, GHC 4122)	10:30A (Miguel, GHC 8023) 4-6P (Anupam, GHC 7203)	3:30P (rntz, GHC 8129) 2-4P (Avrim, GHC 8111) 5:30P (Andrea, GHC 4211)	5P (Kristy, GHC 4102)	3:30P (Yuzi, GHC 7513)

(Note: check Piazza for most up-to-date information on moved/canceled office hours.)

Lectures: Tues/Thurs 12:00-1:20. DH 2210

Recitations:

Rec A: Wed 10:30 (DH 2122) - Miguel Araujo

Rec B: Wed 11:30 (WEH 4709) - Kevin Su

Rec C: Wed 12:30 (WEH 4709) - Michael (rntz) Arntzenius

Rec D: Wed 2:30 (DH 2122) - Eugene Choi

Rec E: Wed 3:30 (DH 2105) - Yuzi Nakamura

Rec F: Wed 9:30 (DH 1117) - Kristy Gardner

Rec G: Wed 4:30 (GHC 4211) - Andrea Klein

Rec H: Wed 2:30 (PH A22) - Paul Davis

Everyone is expected to go to their recitation section. 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 at times contain new material as well.

Course Home page: http://www.cs.cmu.edu/~15451/

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

Bboards:

We will be using Piazza for online discussions and course announcements, so sign up! Go to http://www.piazza.com/cmu/fall2013/15451. You will need to use a cmu.edu address to sign up.

For almost all questions related to the class, it makes sense to use Piazza instead of email. It is faster: you can get a response to your questions from any of the staff members or even from your classmates, instead of waiting for the staff member you emailed. Also, your queries (and their answers) can help your classmates who have the same questions.

Grading: Grading will be done as follows:

• homeworks and minis: 45% (7 hwks at 5% each, 5 minis at 2% each)
• quizzes: 10% (Two 30-min in-class quizzes at 5% each)
• midterm: 15% (in-class)
• final: 30%
• class and piazza participation: adjust borderline scores

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 Andrew ID 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. No collaboration is allowed. If you get stuck, clarification questions should be posted to the bboards, or come to office hours. We are here to help!
• Typed homework is not required, but it is your responsibility to make sure your handin is legible, and typesetting can help with that. LaTeX (see Miktex for Windows machines) is a good typesetting system for documents with lots of math; you probably know it from taking 15-251. (Info on LaTeX installs from 15251 F12.) Here is a Latex template for Hwks. You can customize it as you like.
• Lateness Policy: We have adopted the following lateness policy in order to allow us to post solutions soon after the due date.
  • up to 24 hours late: 10% off (i.e., if the homeworks are worth 100 points, we subtract 10 points from what you got.)
  • 24-48 hours late: 20% 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)
  Each student also gets 2 "mercy days", aka "10% off off coupons". These will be automatically applied to counteract up to 20% total in lateness penalties. Not good on hwks turned in after solutions have been posted. Non-transferrable. Void where prohibited.
• Late homeworks should be slipped under Prof. Blum's door (GHC 8111).

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). You will then present your solutions, as a group, to one of the course staff.
• 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/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 score for the group. (However, we reserve the right to give different members different scores when we believe it is warranted.)
• 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 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 the course staff (on Piazza).

Textbook:

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 find our own confusing!). We recommend you get one of the following:

• Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). It's big, it's fairly expensive, but it is the gold standard of algorithms books with a lot of material. Based on the Algorithms course at MIT.
• Algorithms, by Dasgupta, Papadimitriou, and Vazirani (herafter referred to as "DPV"). Smaller, cheaper, more informal. A relatively new book based on Algorithms courses at UC Berkeley and UCSD. A preliminary (incomplete) version is available here.

Specific readings in CLRS and DPV 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, 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 U. Manber, and the classic Aho-Hopcroft-Ullman book. See also some excellent lecture notes by Jeff Erickson at UIUC.

Academic Integrity:

We assume that you understand the issues and do not need an explanation here. Remember, please do not collaborate on the written homeworks. Issues will be handled in accordance with the University Policy on Academic Integrity.