Computational Mathematics
This class provides a broad introduction to discrete computational mathematics with a focus on symbolic computation.
That is, we cover how to effectively do mathematics on computers. This involves topics such as:
- Using a computer algebra system like Maple or Sage
- Algorithms for performing arithmetic on polynomials and arbitrarily large integers
- Solving linear Diophantine equations and the extended Euclidean algorithm
- Efficient modular arithmetic and the Chinese remainder algorithm
- Primality testing and factorization
- Polynomial evaluation and interpolation
- Karatsuba multiplication, fast multiplication, and the discrete Fourier transform
- Fast division and Newton iteration
- Satisfiability solving and the Davis–Putnam–Logemann–Loveland procedure
A number of applications of these topics will be discussed, such as to coding theory, cryptography, and computer-assisted proofs.
Instructor: Curtis Bright
Course Code: COMP8920-1-R-2022F Selected Topics
Class: Mondays and Wednesdays 4:00–5:20 PM (Erie Hall 1114)
Office Hours: Fridays 9:00–11:00 AM (Lambton Tower 5110)
Webpage: cm.curtisbright.com
Lecture Notes
- Sage Introduction (pdf, ipynb)
- Basic Algebraic Operations (pdf, ipynb)
- The Euclidean Algorithm (pdf, ipynb)
- Modular Arithmetic (pdf, ipynb)
- Cryptography and Coding Theory (pdf, ipynb)
- Finite Fields and Reed–Solomon Codes (pdf, ipynb)
- Satisfiability Solving (pdf, ipynb)
- Polynomial Evaluation and Interpolation (pdf, ipynb)
- Fast Multiplication and the Discrete Fourier Transform (pdf, ipynb)
- Primality Testing and Factoring (pdf, ipynb)
- A Modular Euclidean Algorithm (pdf, ipynb)
The lectures roughly cover the first eight chapters of Modern Computer Algebra as well as chapters 18 to 20. A few topics do not appear in MCA (such as satisfiability solving).
Exercises
Assessment
Assessment for the course will be based on a few things:
- Completing implementations of some of the algorithms that we discuss or related exercises (20%)
- Writing explanatory notes on topics related to the course that are of interest to you (30%)
- A final project that will consist of reviewing a paper or collection of papers and writing a report of around 10–15 pages (50%)
References
There is no required textbook for the course, but the following books are excellent references:
Software
Programming in this class will be done in either Maple or Sage.
Maple is a commercial computer algebra system developed by Maplesoft.
Sage is a computer algebra system that is freely available and runs on Linux, Windows, and MacOS.
Maple has a free trial and I can provide you with a discount code if you are interested in purchasing an indefinite license or a license for the term.