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.