CS G713: Advanced Algorithms

Instructor:  Rajmohan Rajaraman

113 Cullinane Hall                                                                  Work: 617-373-2075
College of Computer Science                                                 Email: rraj@ccs.neu.edu
Northeastern University                                                          Home: 617-232-8298
Boston, MA 02115                                                                  Fax:    617-373-5121

Class meeting times/location:     W 6:00-9:00 PM, 236 FR

Office Hours:    M 4:00-5:00 PM and W 2:00-3:00 PM

Textbook

Prerequisites

Grading

Academic Honesty and Integrity

Class Schedule (Includes all handouts)

Administrivia

Tentative Course Schedule
Questionnaire
Books for Reference

Course Description

This course will present advanced techniques for the design and analysis of algorithms.  The course is divided into two parts.  Part I, lectures 1 through 8, will cover fundamental graph algorithms, optimization techniques, and advanced data structures.  Part II, lectures 9 through 13, will cover selected advanced topics including linear programming, number-theoretic algorithms, NP-completeness, and approximation algorithms.  Here is a tentative list of topics that will be covered:

• Graph algorithms: minimum spanning trees, shortest paths, and network flows
• Data structures for ordered sets and disjoint sets: Union-find, binary search trees and splay trees
• 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
  
• Introduction to complexity theory: NP-completeness
• Introduction to approximation algorithms

Required Textbook

The first edition of the textbook will also suffice though I must add that there will be a few topics (approximately 10% of the course content) that are discussed in the second edition and not in the first.  The course will also include material that is not covered in either of the books.  A recent version of the known errors in the first edition may be found here.  

Prerequisites

Grading

Problem Sets

Problem sets are due at the beginning of class. As a general rule, a problem set turned in late will be penalized 10% for every weekday it is late, and no homework will be accepted beyond 1 week past its due date.    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

• In each class, 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 class. Everbody is required to present at least once during the course.  The preparation and presentation quality will determine the grade for this component (4%).
• Every student is required to scribe one half of a lecture.  The notes will be prepared using Latex, and will be distributed to the students as and when they get completed.  This component accounts for 4% of the grade.
  
• The remaining 2% will be determined by participation in class discussions and the discretion of the instructor.

Exams