Graduate Computer Science

CS G713: Advanced Algorithms

Presents advanced mathematical techniques for designing and analyzing computer algorithms. Reviews some of the material covered in CSG113 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.
Credit hours: 4