Course description

In the January/February 2000 issue of Computing in Science and Engineering, Jack Dongarra and Francis Sullivan selected 10 algorithms with the greatest influence on science, numerical analysis, and engineering in the 20th century. In March 2016, Nick Higham (SIAM president, 2017-2018) presented a slightly revised list. In this course we will cover the motivations, ideas, history, and future impact of these ten algorithms.

Prerequities: A passion for numerical algorithms.

The top ten algorithms

Honorable mentions: Bootstraping methods, fast multipole method, and quicksort.

Lecture notes
Lecture notes:

The lecture notes are written in Julia and published using Jupyter. Julia Cheat Sheet

To download Julia, see: Julia website

Who, when, and where

Date and Time: Tu-Th, 11:40 - 12:45, Rockefeller 112
Instructors: Alex Townsend.


Evaluation
Whenever necessary there will be out-of-class exercises. These are mostly designed to save time in class.

Course project: The course project can be on anything related to a top-ten algorithm. Hopefully, the project will be on the student's research interest. A project report should be written up as a 5-7 page publication, i.e., clear and concise. It is a good idea to use LaTeX for the typesetting. Please select a project as soon as possible.

Important dates: 2nd and 4th of May, student presentation in-class. Written reports due on the 4th of May. Project information

Exercises
Here, are some exercises to aid the class discussion:

Matrix factorization: pdf
QR algorithm: pdf
Krylov subspace methods: pdf
Fast Fourier transform: pdf, Mat-vecs, Signal processing
JPEG: pdf
Quasi-Newton: pdf
Simplex:
Monte-Carlo:
PageRank: pdf
Fast Multipole method:

Classic publications
Classic publications on the ten algorithms: