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:
Email is the best way to get in touch with me.
Office hours: TBD
Location: 242 WVH