Handout 1                                        Preliminaries                                                      9/7/11





Course homepage: http://www.ccs.neu.edu/course/cs7800f11


Course description: Presents advanced mathematical techniques for designing and analyzing computer algorithms.  Reviews some of the material covered in CS5800 and then covers advanced topics.  Emphasizes theoretical underpinnings of techniques used to solve problems arising in diverse domains. Topics include asymptotic analysis, advanced data structures, dynamic programming, greedy algorithms and matroid theory, amortized analysis, randomization, string matching, algebraic algorithms, and approximation algorithms. Introduces Turing Machines, P and NP classes, polynomial-time-reducibility, and NP-completeness.


Textbook: “Algorithm Design,” J .Kleinberg and E. Tardos. Addison Wesley, 1st Edition, 2005. Other good books are “Algorithms” by A. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw Hill, 2007 (an online draft version is available) and “Introduction to Algorithms,” T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009. There is excellent material online and we will be providing links.


Hours: Mon, Wed 2:50 PM – 4:30 PM

Classroom: 425 HA


Course mailing list: Please make sure that your emailid is on the course mailing list – csg7800@ccs.neu.edu.


Instructor: Ravi Sundaram, 617-373-5876, koods@ccs.neu.edu

Email is the best way to get in touch with me.


Office hours: TBD

Location: 242 WVH