Design and Analysis of Algorithms

Catalog description

Building on both Mathematics for Computer Science and Introduction to Algorithms, this course focuses on techniques for the creation and understanding of efficient algorithms. Students will learn to analyze the computational complexity of a problem, recognize classes of problems, design new algorithms, and analyze proposed solutions. All concepts will be internalized via application to real-world problems. Specific topics include; Complexity and Computability: decidability, reducibility, time, space, asymptotics, worst case, average case, tradeoffs, Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, randomization, etc., and Algorithm analysis: recurrences, generating functions, analytic combinatorics, verification of correctness. Prerequisite(s): COM 2545 .