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

These notes have been archived since 2023. I recommend referring to the most recent notes as they may correct some typos.

- 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).

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%)

There is no required textbook for the course, but the following books are excellent references:

- Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard
- A Computational Introduction to Number Theory and Algebra by Victor Shoup (freely available)
- Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance

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.