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
Academic Honesty and Integrity
Class
Schedule (Includes all handouts)
Administrivia
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.
- Graph algorithms: minimum spanning trees, shortest paths, and network flows
- Design techniques: divide and conquer, randomization, dynamic programming, and greedy algorithms
- Analysis techniques: asymptotic analysis, probabilistic analysis, average-case analysis, and amortized analysis
- Selected general paradigms: matroid theory, linear programming
- Introduction to number-theoretic algorithms: primality testing
- Lower bounds
- NP-completeness
- Introduction to approximation algorithms
- A subset of other advanced topics: Markov chains, Fast Fourier Transform, expander graphs, multithreaded algorithms, number-theoretic algorithms
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.
Prerequisites
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.
Grading
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%).
- Each week, a ``Problem of the Week'' (or two) will be handed out, and a student will be called on to present his/her solution to the problem in the following week's class, and submit a writeup on the problem. Everbody is required to present once during the course. The quality of the presentation and writeup will determine the grade for this component (3%).
- The remaining 2% will be determined by participation in class discussions and the discretion of the instructor.
Exams
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.