15-451/651 Algorithms
Course Information, Fall 2012

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, Balanced Search Trees, Hashing, Randomization, Dynamic Programming, Network Flows, Linear Programming, and the Fast Fourier Transform, as well as basic data structure and 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, and NP-Completeness.
  • Identify and critique incorrect analyses, finding counterexamples to faulty claims and "proofs" of correctness.

Avrim Blum, avrim@cs, GHC 8111. Office hours: Fri 11:00-12:00.
Daniel Sleator, sleator@cs, GHC 8113. Office hours: Fri 1:00-3:00.

Course Secretary:
Marilyn Walgora, mwalgora@cs, GHC 8120 , x8-3505.
Teaching Assistants:
Andrew McKinnie, amckinni@andrew. Office hours: Mon 7-9 pm in GHC 4122/4126.
Dennis Meng, dmeng@andrew. Office hours: Thu 8-10pm, near GHC 4122/4126.
Ankit Sharma, ankits@cs. Office hours: Thu 5:00pm in GHC 7703.
Patrick Xia, pjx@cs. Office hours: Fri 2pm in GHC 6004.
Fan Xiang, fxiang@andrew. Office hours: Mon 10:30am, in GHC 4122/4126.
Carol Wang, carolwan@cs. Office hours: Mon 5-7 pm, in GHC 7517.
John Wright, jswright@cs. Office hours: Fri 2pm, Hillman 7th floor common area (near GHC 7501).

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

Rec A: Wed 10:30 (BH 136A)
Rec B: Wed 11:30 (WEH 4709)
Rec C: Wed 12:30 (WEH 4709)
Rec D: Wed 2:30 (WEH 5421)
Rec E: Wed 3:30 (DH 2105)
Rec F: Wed 9:30 (DH 1117)
Rec G: Wed 4:30 (GHC 4211)

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 often contain new material as well.

Course Home page: http://www.cs.cmu.edu/~avrim/451/
Check it frequently for announcements and updates, lecture notes, handouts, assignments, solutions, and other goodies.

We will be using a system called piazza for online discussions. Go to http://www.piazza.com/cmu/fall2012/15451. You will need to use a cmu.edu address to sign up.

Grading: Grading will be done as follows:

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
    • 1-2 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)
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 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 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.

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.

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 my 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 new book based on Algorithms courses at UC Berkeley and UCSD.
Specific readings in CLRS 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 Manber, and the classic Aho-Hopcroft-Ullman book.