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.
-
Identify and critique incorrect analyses, find
counterexamples to faulty claims and "proofs" of
correctness.