Algorithms Across the Mathematics Curriculum


#1

There are several algorithms that students can and should be learning in an upper-division mathematics curriculum. Most degrees seem to only touch a few algorithms outside of a numerical analysis course (e.g., Newton’s method, the Euclidian algorithm, and maybe the simplex method), but there are so many more that students need to see.

It’s a mistake to only put algorithms in elective numerical analysis courses. They should be integrated into the curriculum.

Most of the following are covered in BYU’s relatively new Applied and Computational Mathematics undergrad degree.

I would love to hear from people who want to add to the list, argue about the list, and/or have experienced with these and related topics.

  • Encryption Algorithms: probabilistic primes (using Fermat’s little theorem), RSA, Euclidian algorithm, Diffie Hillman key exchange
  • Solving Linear Systems and Finding Eigenvalues: Row reduction, Jacobi, Gauss Seidel, Successive over relaxation (SOR), and Krylov methods such as Arnoldi, Lancos, GMRES.

  • Spectral Decomposition: FFT in 1-2-3 dimensions, convolution, windowing and other signal processing algorithms (just inner products and FFT)

  • State Estimation: Kalman, extended Kalman, particle filters, recursive least squares, etc.

  • Compression: Huffman, LWZ, wavelet approximation

  • Tree Search: AVL trees, Black-White trees, B-trees

  • Constrained Optimization: simplex, interior point, \ell^1
    regularization (which includes compressed sensing)

  • Sampling and Markov Chain Monte Carlo: Gibbs, Metropolis, Metropolis-Hastings

  • Matrix Decompositions: LU, QR, SVD, etc.

  • Graph Algorithms: Minimum Spanning tree, traveling salesman, breadth-first search, depth-first search

  • Unconstrained Optimization: Newton, BFGS, conjugate-gradient

  • Dynamic programming (backward iteration)

  • Classification: Logistic regression, random forests, support vector
    machines, neural networks

  • Multi-armed bandit problems and Markov Decision Processes

Others are:

  • ODE Solvers (RKF, Dormand-Prince)

  • PDE solvers: finite difference/element: Most of these are just linear algebra solvers

  • Pseudorandom number generation: Twistor

  • Time series: ARMA, ARIMA (these can be done with the Kalman filter, but almost nobody does it this way)

  • Splines/Interpolation: Most of these are linear algebra solvers, Chebyshev interpolation uses FFT, barycentric Lagrange interpolation


#2

This is a great list to begin a discussion. There are many algorithms on your list that do not appear in our undergraduate courses, but many do. I like your point that these should be integrated in courses throughout the curriculum. This is a direction in which we have been heading too. For example, we cover PCA, unconstrained and constrained optimization, regression, and other algorithms in our (data-driven) mathematical modeling course. Other algorithms appear in applied linear algebra and applied harmonic analysis courses. We are trying to find the best ways to do this — i.e. to learn from other people’s mistakes and successes as well as our own. There should be mini symposiums at SIAM national meetings and special sessions at the JMM that explore this.