G22.3033-002


G22.3033-002

Applied Math for Algorithms

Siegel

Mondays 5-6:50, room 102

Office hours: M 7:00-8:00

Graduate Division

Computer Science

Link to the class wiki.


 

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.