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, linear programming), paradigms (e.g. approximation algorithms, online algorithms, streaming algorithms), and methods for analyzing algorithms and prolems (e.g., lower bounds, amortized analysis, probabilistic analyses of randomized algorithms). The complete list of topics is on the "Schedule" page linked above. 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 fundamental algorithm design tools discussed including hashing, graphs, randomization, dynamic programming, network flows, and linear programming, as well as basic data structure and algorithm design principles.
  • Design algorithm for different paradigms such as approximation algorithms, online algorithms, and streaming algorithms.
  • Use and explain analytical tools and frameworks discussed including recurrences, probabilistic analysis, minimax optimality, amortized analysis, analysis within different concrete models, and potential functions.
  • Identify and critique incorrect analyses, find counterexamples to faulty claims and "proofs" of correctness.