Other links:
Other links:
Course objective: This course will introduce students to the mathematical modeling and solution of computational problems, and teach them how to design and analyze efficient algorithms. Students will: 1. Cover the standard algorithmic paradigms like induction, divide-and-conquer, prune-and-search, greedy, dynamic programming and a toolkit of common algorithms including randomized techniques for design, correctness proofs and rigorous analysis of time and space complexity.
2. Explore different ways of thinking about and representing problems coming from diverse domains like sets, graphs, geometry, algebra and number-theory.
3. Develop an understanding of performance metrics like worst-case, average-case and expected-case and how the underlying computational framework is intrinsically tied to the design of efficient algorithms and the notion of optimality.
Pre-requisite: Data Structures, Probability and Statistics.
Coverage: Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics include divide-and-conquer; dynamic programming; greedy algorithms; branch and
bound; backtracking; amortized analysis; randomized techniques and randomized data structures; graph algorithm including flows and matching. Advanced topics may include computational geometry including
dimension-reduction techniques, number-theoretic algorithms, polynomial and matrix calculations, external-memory and caching, and some flavor of distributed and parallel computing. Introduction to NP-Completeness, reductions and approximation algorithms.
