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.