Advanced Algorithms

Catalog description

The purpose of this course is to acquire a thorough grounding in the core principles and foundations of computer science. After a review of foundational algorithm analysis, students will learn advanced algorithmic techniques such as randomized and approximation algorithms. Problems arising in number theory such as Primality Testing and Factorization will lead the path to study the RSA public-key crypto-system. Classical algorithms for String Matching, with applications to computational biology, such as Rabin-Karp and Knuth-Morris-Pratt, will also be studied. Advanced data structures particularly suited for certain applications, such as B-trees, van Emde Boas trees, and skip lists, will be studied. The question of what problems are hard to compute will be addressed studying the NP-completeness theory, including the identification of NP-hard problems by reductions. Hard problems such as Traveling Salesman, Knapsack, and Vertex Cover will be studied in the context of approximation algorithms.Instructor approval required for student registration.