Instructor: Dan Spielman.
Tuesday/Thursday 2:30-4:00 in 3-270
In this course, we will discuss rigorous approaches to explaining the typical
performance of algorithms. In particular, we examine alternatives to the
traditional worst-case and average-case analyses. Such analyses must
necessarily make assumptions about the inputs to algorithms.
We will develop this theory together, and I expect we will debate the merits of
various approaches, as well as the names I have tentatively assigned to them.
My lectures will center around the following three approaches.
1. smoothed analysis:
Analyzing algorithms assuming their inputs are subject to noise. That
is, we measure the maximum over inputs of the expected performance of
an algorithm under slight random perturbations of those inputs. This
is the intersection of Shannon Theory with Analysis of Algorithms by
assuming inputs come through a noisy channel.
2. condition numbers/parametric analysis:
In this approach, we find a simple parameter of the input that is
predictive of the running time of the algorithm. This parameter should
be significtanly simpler than "the running time of the algorithm".
Examples could include
a. feature size of point sets,
b. condition numbers of matrices or polynomials,
c. bit length of inputs
3. subclassing inputs:
In many practical problem domains, the inputs to algorithms have special
structure, and may form a proper subclass of the possible inputs. If it
is known an algorithm in a particular application only see inputs from this
subclass, then it is natural to analyze the performance of this algorithm
on the subclass.
Students will perform class projects examining the applicability of these
analyses to some problem area, and will present their findings to the class as
well as writing up their findings. Some students may wish to choose their
project from a list of tractable open problems that will be circulated within
the class.
Students will also be responsible for scribing lectures.
Prerequisites: At least one graduate course in algorithms or numerical analysis.
Enrollment may be limited.