Although many mathematics courses have content that is useful in the design and analysis of algorithms, the more applicable material often comprises no more than 10% of the curriculum.

This course will endeavor to present that critical 10% as culled from a handful
of math courses and other sources. We will also endeavor to show how this
material is applied in the design and analysis of algorithms.

Some of the subjects that will be covered are:

**Performance-related equations **and their
direct solution.

Recurrence equations: first order
difference equations and beyond.

Eigenfunction methods, multiplicity
of eigenvalues, etc.

**ODEs** and their use in performance analyses.

A limited
presentation of limit theorems.

**PDEs** and their use in performance analyses.

Limited
implications of limit theorems.

**Probability**, and what properly
educated theoreticians might wish to know.

Conditional expectations are a powerful, highly expressive tool with a
foundation that is based on measure theory.
Yet the concept is very pragmatic, and allows us to present proofs and to acquire
understandings about probabilistic processes that would otherwise be difficult
to formalize.

It is also worth understanding what the central limit theorem says, what it
means, what it implies, and what it does not imply.

Likewise, it is useful to understand the more basic probability distributions
and the physical processes that they model.

**Statistics** is a little different from
probability.

One of the areas of statistical analysis that has had significant impact in TCS
is the theory of Hoeffding-Chernoff bounds. It is
probably a good idea to know how this material applies to more than Bernoulli Trials, and to stopping times in particular.

We might also cover some issues in the computation of random variables, and at
least comment on the importance of extreme points in the space of probability
distributions (which is to say that we will survey majorization
results).

**Complex variables gives valuable insights about the solution to many
algorithms-based difference equations, and provides** the
theory necessary for computing saddle point estimates and understanding some of
the limit results for ODEs PDEs.

**Combinatorics** is
less systematic than analysis, but gives a rich set of techniques that are as
varied as tableau methods (used to count seemingly complicated outcomes) and
the probabilistic method (which is arguably more combinatorial that
probabilistic).

Additional topics will be included as time/opportunities permit.