University of Illinois at Urbana-Champaign, Department of Mathematics

Instructors : Yuliy Baryshnikov and Anil N. Hirani

**Schedule:**

In **bold** below are the main algorithm lectures. Other
lectures are reports on applications/extensions/related topics and
algorithms.

08/26 Introduction

08/28 **Metropolis**

09/02 **Integer relations detection**

09/04 **Simplex algorithm for linear programming**

09/09 **LU decomposition for solving linear systems**

09/11 **Quicksort**

09/16 Metropolis application to physical problem

09/18 **QR decomposition and least squares**

09/23 ...

09/25 **Conjugate gradients**

09/30 LP duality, image segmentation using LP

10/02 Kalman filter

10/07 Interior point methods, max-flow, other LP applications

10/09 Kalman filter contd.

10/14 Particle filters; **Bloom filter**

10/16 **Bloom filter** contd.; LLL basis reduction

10/21 LLL basis reduction contd.

10/23 Iterative linear solvers

10/28 **QR iteration for eigenvalue computation**

10/30 **Fast Fourier Transform**

11/04 Multi-pivot quicksort

11/06 Metropolis applications

11/11 ...

11/13 FFT applications

11/18 Isospectral domains and spectrum computation

11/20 FFT applications

11/25 [Fall break]

11/27 [Fall break]

12/02 Introduction to parallel algorithms

12/04 **Fast multipole method**

12/09 Bloom filter applications

**Description:** In January 2000, Computing in Science
and Engineering magazine published a list of 10 algorithms which (in
their words) had the "greatest influence on the development and
practice of science and engineering in the 20th century". With an eye
towards the future we have prepared a slightly modified list of Top 10
algorithms which we will study in this class.

There will be approximately 2-3 sessions (lecture/discussion) on
each algorithm. The first session for each algorithm will be a lecture
by the instructors. In it we will give an overview of the algorithm
and its applications and provide the relevant reading list and
programming suggestions. Later sessions on that algorithm will largely
be student-led and moderated by the instructors. For each algorithm
there will be a team of 3 students working with the instructors : a
**historian**, a **programmer** and
a **scribe**.

The historian will have primary responsibility for leading the survey of the literature, the programmer will do the computer experiments, and scribe will record the material collected and presented by that team.

**List of algorithms:**

- Metropolis algorithm for Monte Carlo (with Gibbs sampler)
- Integer relation detection (PSLQ, LLL and related algorithms)
- Simplex method for linear programming (with interior point methods)
- Matrix factorization algorithms for solving linear systems and least squares
- Quicksort
- Conjugate gradients and Krylov subspace methods for solving linear systems
- Bloom filter
- QR algorithm for eigen computations
- Fast Fourier transform
- Fast multipole method

**Readings:** Reading material is available
on U of I Box. You will need a
U of I Box account. (This is different from a general Box account
that you might have signed up for directly with Box.) Once you have a
U of I box account you can download
the readings.

**Grading:** Grading will be based on class
participation and project.

**Computing environment:** The programmer in each
team of 3 will have to do some programming. For a course like this
we prefer Python (and occasionally MATLAB). Sage is basically Python
so that works too. Any code we provide will be in Python (and
perhaps sometimes in MATLAB). Students are free to use any
programming environment. In addition to or instead of Python/Sage,
students are free to use MATLAB/Octave, C/C++, Java, Fortran,
Mathematica or any other programming environment.

**Prerequisite:** Calculus and linear
algebra. Programming is not a prerequisite for everyone (we need about
a third of the students to know some programming).

**Announcements:** will be posted
on Compass.

**Contacts:**

Anil N. Hirani, email

375 Altgeld Hall

Yuliy Baryshnikov, email

302 Altgeld Hall

Page maintained by Yuliy Baryshnikov and Anil N. Hirani

Last modified: Mon Nov 10 21:03:06 CST 2014