COMP SCI 404: Introduction to Algorithms and Complexity

Course Description

A rigorous review of asymptotic analysis techniques and algorithms: from design strategy (such as greedy, divide-and-conquer, and dynamic programming) to problem areas (such as searching, sorting, shortest path, spanning trees, transitive closures, and other graph algorithms, string algorithms) arriving at classical algorithms with supporting data structures for efficient implementation. Throughout, the asymptotic complexity is studied in worst case, best case, and average case for time and/or space, using appropriate analysis techniques (recurrence relations, amortization). Introduction to the basic concepts of complexity theory and NP-complete theory.