Mathematical Software: Computer Algebra

Mathematics 69.387/95.387: CLASS OUTLINE WINTER 2002

Week Dates Assignments Sections Topics
1 Jan.3-Jan.4 ~ Chapter 1 Introduction to the course.
2 Jan.7-Jan.11 ~ 25.1-25.3; 2.1-2.2 Review of algebraic concepts. Addition of numbers and polynomials.
3 Jan.14-Jan.18 A1 handed-out 2.3-2.4 Multiplication of numbers and polynomials. Data structures. Division with remainder.
4 Jan.21-Jan.25 ~ 3.1-3.2 Euclidean and extended Euclidean algorithm.
5 Jan.28-Feb.1 ~ 3.2-3.3 Correctness and analysis of extended Euclidean algorithm.
6 Feb.4-Feb.8 A1 handed-in;
A2 handed-out
3.3; 4.1-4.2 Analysis of extended Euclidean algorithm (cont). Application: modular arithmetic. Modular inverses and finite fields.
7 Feb.11-Feb.15 ~ 4.3-4.4; 5.1-5.3 Repeated squaring. Change of representation. Evaluation and interpolation. Application: secret sharing.
~ Feb.18-Feb.22 WINTER BREAK NO CLASSES THIS WEEK
8 Feb.25-Mar.1 ~ 5.4 Chinese remainder theorem and algorithm.
9 Mar.4-Mar.8 A2 handed-in;
A3 handed-out
8.1; 12.1 Karatsuba's algorithm. Strassen's algorithm.
10 Mar.11-Mar.15 A4 handed-out 8.2 Discrete Fourier transform.
11 Mar.18-Mar.22 ~ 8.2 Multiplication of polynomials and DFT.
12 Mar.25-Mar.29 A3 handed-in 9.1 Newton iteration. Fast division with remainder.
13 April 1-April 4 A4 handed-in Overview of Chap. 14 or 21 Factorization of polynomials over finite fields or Groebner basis. Review of the course.

Note. Sections and chapters are from the textbook: Modern Computer Algebra by Joachim von zur Gathen and Jurgen Gerhard.