Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491

Time and Place: Tuesdays and Fridays, 2:00pm-3:20pm, in DCC 232
Office Hours: Wednesday 5pm-6pm, Thursday 4pm-5pm (or by appointment)

Announcements:

12/04/07 - The office hours this Wednesday (12/5) will take place at 2pm.
11/30/07 - The Final Exam is out. It is due Dec 14th at 5pm. By that time, you should either give it me, or leave it in my mailbox on the second floor of Lally. Please do not slide the exam under my office door.
11/16/07 - Problem Set 7 is out. It is due Nov 30th at the beginning of class.
11/13/07 - Because of the colloquium this Thursday, office hours will take place at 5pm.
11/06/07 - There will be no office hours this Wednesday 11/7, and the office hours on Thursday 11/8 will take place at 5pm.
11/02/07 - Problem Set 6 is out. It is due Nov 16th at the beginning of class.
10/19/07 - Problem Set 5 is out. It is due Nov 2nd at the beginning of class.
10/5/07 - The Midterm exam will take place next week on October 12. It will be in-class, and you will have 1 hour and 50 minutes to do it. You will be allowed to use only your notes, and nothing else (including laptops, textbooks, etc).
10/5/07 - Problem Set 4 is out. It is due October 19 at the beginning of class. You must solve problems 8.6, 8.9, and 8.19 from the Kleinberg-Tardos textbook. If you do not have this textbook, you can pick up a hard copy of the problems from me.
9/21/07 - Problem Set 3 is out. It is due October 5 at the beginning of class. You must solve problems 7.43, 6.15, and 6.28 from the Kleinberg-Tardos textbook. If you do not have this textbook, you can pick up a hard copy of the problems from me.
9/21/07 - There will be no class or office hours all next week. The next time we will meet after today is on Tuesday, Oct 2nd.
9/19/07 - Because of the CS colloquium this Thursday, office hours will take place at 3pm instead of 4pm.
9/14/07 - Problem Set 2 is out. It is due September 21st at the beginning of class. You must solve problems 7.8 and 7.28 from the Kleinberg-Tardos textbook. If you do not have this textbook, you can pick up a hard copy of the problems from me.
8/31/07 - Problem Set 1 is out. It is due September 14th at the beginning of class, and is only available in hard copy. Note: You only need to do two problems (your choice of which ones). If you do all three, you will get extra credit.

Course Overview

This course is an introductory graduate-level course on algorithms. Its focus is on general techniques for designing and analyzing algorithms, and their use in a variety of application areas. The goal of this course is to provide a toolkit of algorithmic techniques for graduate students in any area that makes use of algorithms. The second half of the course will focus especially on approximation algorithms. For more details, see the Syllabus.

Pre-requisites

Some sort of undergraduate algorithms course, such as CSCI 4020, is required before taking this class. Students are assumed to be familiar with the basics of data structures and algorithms, discrete mathematics, and probability. Specifically, knowledge of the following will be assumed:

• Mathematical Proofs, in particular induction and contradiction.
• Big-Oh notation (Big-O, Omega, Theta), how to apply them.
• Basic data structures: arrays, linked lists, trees, balanced trees, heaps (priority queues), graphs.
• Basic graph algorithms: connected components, BFS, DFS.
• Other algorithms: binary search, sorting.
• Discrete mathematics: evaluating sums and simple recurrences.

Note that a lot of the themes we will cover appear in undergraduate algorithms courses, such as in CSCI 4020. The coverage here will focus on more advanced topics, and will involve little overlap with CSCI 4020, although it also counts for the Algorithms qualifying exam if the student receives an A or A-.

Books

There is no required book for this course. However, it is recommended that you purchase a copy of:

• Jon Kleinberg/Éva Tardos: Algorithm Design.

• Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms (2nd edition) - useful as reference for first half of course
• Kozen: The Design and Analysis of Algorithms - useful as reference for first half of course
• Vazirani: Approximation Algorithms - very useful for second half of the course
• Hochbaum: Approximation Algorithms for NP-Hard Problems - very useful for second half of the course
• Garey/Johnson: Computers and Intractability
• Motwani/Raghavan: Randomized Algorithms

Homework, Exams, and Grading

Homeworks will be assigned approximately every 2 weeks. There will not be any programming assignments. Homeworks should be handed in at the end of lecture on the day they are due. Late homeworks will not be accepted, except in case of a genuine emergency.

You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments separately, and include the names of everyone you discussed the assignment with. You may not copy a solution from another. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and will be penalized severely.

You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness.

There will be two exams: an in-class midterm on October 12, and a take-home final given out on November 30, and due December 14. Unlike the homeworks, you must do these entirely on your own. The final exam will be worth 25% of your grade, the midterm will be worth 20%, and the homework will be worth 55%.