CS 7800: Advanced Algorithms

Fall 2003

Instructor:  Rajmohan Rajaraman

240 WVH                                                                  Work: 617-373-2075
College of Computer and Information Science         Email: rraj@ccs.neu.edu
Northeastern University                                                          
Boston, MA 02115                                                     Fax:    617-373-5121

Class meeting times/location:     MW 2:50-4:30, Forsyth 130

Office Hours:    M 4:45-6:00 PM, F 4:15-6:00 PM

Course Description




Academic Honesty and Integrity

Class Schedule (Includes all handouts)


Tentative Course Schedule

Course Description

This course will present advanced techniques for the design and analysis of algorithms.  The course is divided into two parts.  Part I, weeks 1 through 6, will cover fundamental design techniques, optimization methods, and graph algorithms.  Part II, weeks 7 through 14, will cover selected advanced topics including linear programming, randomized algorithms, NP-completeness, and approximation algorithms.  Here is a tentative list of topics that will be covered:

For a slightly more detailed listing of the topics covered, see the tentative schedule.

Required Textbook

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press/McGraw-Hill,  (3rd Edition, 2009) 

The course will also include material (approximately 10% of the course content) that is not covered in the text.  


This is a PhD core course; if you are not a PhD student in the college, then you need to get approval from the instructor. The course will be fast-paced and will cover a number of advanced topics in algorithms over the 13-week period.  A good test to find out whether you are well-prepared for taking this course is to look over material from the following chapters of the textbook: 1-4, 6-7, 10-12, and 22.  If you have studied the material in these chapters and are comfortable with it, then you are well-prepared.  Otherwise, you should talk to the instructor before taking the course.  Also it is highly recommended that you review the mathematical background covered in Appendices A, B, and C.1-C.3 by the end of the first week of class.


The course grade will be based on six problem sets (total 30%), a midterm (30%), a final exam (35%), and class participation (5%).

Problem Sets

Problem sets are due at the beginning of class on the due date. No late submissions will be accepted!     Students may discuss the problem sets with one another, but solutions should be written up separately.  If a key idea is obtained from another person (other than the instructor) or from another book or paper (other than the course textbook), then the source of that idea should be cited.  Solutions should be presented in a clear and concise manner.   Tentative out/due dates for the problem sets are listed in the schedule.

Class Participation

There are two components that make up class participation (5%).


The midterm will probably be a take-home exam that will be given out late October.  The final exam will probably also be a take-home exam that will take place during finals week.