15-451 Course Information, Spring 2006

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. Some tools we will discuss are 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 are 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). Other topics which may be included are computational geometry, cryptography, and game theory.

Instructor:

Danny Sleator, sleator+@cs, Wean 4128, x8-7563. Office hours: Mon 1:00-2:00pm.

Teaching Assistants:

Daniel Golovin, dgolovin@cs, Wean 8104, x8-2582. Office hours: Thursday 2-3pm.

Lea Kissner, leak@cs, Wean 3721, x8-1549. Office hours: Tuesday 10-11am.

Course Secretary:

Nicole Stenger, Wean 4116, x8-3779.

Lectures: Tues/Thurs 12:00-1:20. Hammerschlag Hall B103

Recitations:

Rec A: Wed 11:30 (PH 226B) - Daniel Golovin

Rec B: Wed 12:30 (PH 225B) - Lea Kissner

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-s06/www/

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

Blackboard

The Blackboard Site for this course will be used for discussion groups and maintaining a grade book.

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 quizzes at 5% each)
• midterm: 15%
• final: 30%
• class participation: adjust borderline scores

Important Dates:

The first quiz will be February 21. The midterm will be March 9. The 2nd quiz will be April 6. The date of the final is not yet known. Check out the course schedule for more information.

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're probably learn more by solving the problems all by yourself. But we're not going to restrict discussions among the students. But 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 blackboard discussion groups.
• 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 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.

Minis:

Mini-homeworks will be made available on the course web page on Friday, 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. You should do these completely by yourself -- if you have questions, contact your TA.

Textbook:

The required text for the course is Algorithm Design by Kleinberg and Tardos, (hereafter referred to as "KT"). We will also be providing lecture notes covering most of the material in this course, but it is important 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: 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.