Course Overview

This course is about the design and analysis of algorithms. We will study specific algorithms for a variety of problems, as well as powerful modelling techniques (e.g. graphs and linear programming) and design paradigms (e.g. amortized analysis, dynamic programming, and sweep-line). (The complete list of topics is on the "Home/Schedule" page linked above.) We will study ways to analyze the efficiency of algorithms, and give lower bounds on the complexity of a problem. The topics have been chosen for their power, beauty, and practicality.

Learning Outcomes

The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. By the end of this course, you should be able to:

• Use and explain algorithm design tools discussed including divide-and-conquer, balanced search trees, hashing, graphs, randomization, dynamic programming, network flows, and linear programming, as well as basic data structure and algorithm design principles.
• Use and explain analytical tools and frameworks discussed including recurrences, probabilistic Analysis, minimax optimality, amortized analysis, analysis within different concrete models, and potential functions.
• Understand and explain important concepts in complexity theory including NP, Co-NP, and NP-Completeness.
• Identify and critique incorrect analyses, find counterexamples to faulty claims and "proofs" of correctness.