I have put videos of my computer algebra course lectures (.mp4 files) here along with the handouts (and accompanying Maple worksheets) and my filled in lecture notes here.
Michael Monagan, April 2021.
Lecture 1 Integer multiplication: the grade school algorithm, Karatsuba, their complexity, and what is known.
Lecture 2 Analysis of algorithms: O(f(n)), properties, examples. Maple tutorial.
Lecture 3 Integer gcd: Euclid's and Stein's algorithms. Rings, subrings, and zero divisors.
Lecture 4 Integral domains: division, gcds, primes, irreducibles, factorization. Euclidean domains.
Lecture 5 The extended Euclidean algorithm. The polynomial ring R[x], division in F[x].
Lecture 6
Cost of division and the Euclidean algorithm in F[x], solving diophantine equations in F[x].
Multivariate polynomials, exact divison in D[x1,...xn].
Lecture 7 Multivariate gcds: content, pseudo division. The primitive Euclidean algorithm, expression swell.
Lecture 8 Ring homomorphisms, the Schwartz-Zippel Lemma. The Chinese remainder theorem and algorithm.
Assignment 3: Lectures 9 – 12.
Lecture 9 A modular algorithm for multiplication in ℤ[x]. Polynomial interpolation, homomorphic imaging.
Lec10AB.mp4 Lecture 10 Roots of unity, the Fast Fourier Transform. Cost of the FFT and fast polynomial multiplication.
Lecture 11 The modular GCD algorithm.
Lecture 12 The Sylvester resultant. Cost of the modular GCD algorithm.
Lec13ABC.mp4 Lecture 13 Fast integer multiplication using the FFT. Tutorial.
Assignment 4: Lectures 14 – 16.
Lecture 14 P-adic representations for ℤ, base conversion. A p-adic iteration for integer square root.
Lecture 15 Computing a square root in ℤ[x] using (1) a p-adic iteration and (2) single point evaluation.
Lecture 16 Linear Hensel lifting in ℤ[x]. Gcds in ℤ[x] using Hensel lifting.
Assignment 5: Lectures 17 – 20.
Lecture 17 Square-free factorization. Factoring polynomials in ℤ[x] using Hensel lifting and trial division.
Lecture 18 Factoring polynomials over finite fields using the Cantor-Zassenhaus algorithm.
Lecture 19 Binary powering with remainder and root finding. Representation and differentiation of formulae in Maple.
Lecture 20 Calculating resultants. Polynomial factorization tutorial. The Risch integration algorithm.
Assignment 6: Lectures 21 – 25.
Lecture 21 Rational function integration: the rational part. Hermite reduction and Horrowitz's algorithm.
Lecture 22 Rational function integration: the logarithmic part. The Trager-Rothstein resultant.
Lecture 23 Elementary function integration: the Risch structure theorem, Liouville's theorem.
Lecture 24 The Risch algorithm: logarithmetic extensions.
Lecture 25 The Risch algorithm: exponential extensions.
Lecture 26 Final exam info + review.
Lec10A.pdf Lec10B.pdf Lec10C.pdf
Lec11A.pdf Lec11B.pdf Lec11C.pdf
Lec12A.pdf Lec12B.pdf Lec12C.pdf
Lec14A.pdf Lec14B.pdf Lec14C.pdf
Lec15A.pdf Lec15B.pdf Lec15C.pdf
Lec16A.pdf Lec16B.pdf Lec16C.pdf
Lec17A.pdf Lec17B.pdf Lec17C.pdf
Lec20A.pdf Lec20B.pdf Lec20C.pdf
Lec21A.pdf Lec21B.pdf Lec21C.pdf
Lec22A.pdf Lec22B.pdf Lec22C.pdf Lec22D.pdf
Lec23A.pdf Lec23B.pdf Lec23C.pdf
Lec24A.pdf Lec24B.pdf Lec24C.pdf
Lec25A.pdf Lec25B.pdf Lec25C.pdf