CS W4241

CS W4241 - Numerical Algorithms and Complexity

Spring 2013

Monday, Wednesday, 4:10 - 5:25 pm

Professor: Joseph F. Traub

Office Hours: TBA

TA: TBA

Grading:

  • Midterm 30%
  • Final 40%
  • Homework 30%
  • Extra credit homework 10%
  • TOTAL 110%

The course consists of two parts, complexity and algorithms.

PART I - COMPLEXITY

Rather than a text IŽll give you handouts.

The following is an indication of the topics IŽll cover.

  1. Overview
  2. Integration Example
  3. Breaking the Curse
  4. Mathematical Finance
  5. Model of Computation
  6. Formal Models and Scientific Knowledge
  7. Complexity of Linear Programming
  8. Complexity of Verification
  9. Clock Synchronization in Distributed Networks
  10. Assigning Values to Mathematical Hypotheses

OPTIONAL MATERIAL

  1. General Formulation of Information-Based Complexity
  2. Integration Example Concluded
  3. Value of Information in Computation

A number of additional complexity topics will be covered in the lectures. There will be handouts for this material also. Topics include

  • Playing 20 questions against a liar
  • Continuous binary search
  • Fast matrix multiplication
  • Fast Fourier transform (FFT)
  • Polynomial Evaluation
  • Effect of precomputation

PART II - ALGORITHMS

The material on algorithms will be covered by handouts.

  1. Nonlinear Equations
    1. Univariate
    2. Multivariate
  2. Polynomial zeros
    1. Bernoulli algorithm
    2. Jenkins - Traub algorithm
  3. Randomization
    1. High dimensional integration 
  4. Numerical solution of partial differential equations
    1. Elliptic equations
    2. Parabolic equations
    3. Hyperbolic equations  
  5. Applications to science, engineering, finance.