Lecturer
Assistant
News & Log
- 19.02.: Basic arithmetic operations. School method for addition, subtraction, multiplication and Karatsuba algorithm
- 26.02: Division with remainder. Euclidean algorithm and Extended Euclidean algorithm
- 05.03: Modular Arithmetic, Euler Phi-Function, Chinese Remainder Thm., RSA
- 12.03: Randomized Primality Tests: Fermat & Miller-Rabin, Properties of Carmichael numbers
- 19.03: Density of prime numbers, randomized singularity test for matrices
- 26.03: Randomized check for perfect matching, Schwartz-Zippel-Lemma (see here 16.05: new link!)
- 09.04: Fast Fourier Transform and multiplication of polynomials (in fields)
- 16.04: Fast Fourier Transform in commutative rings with unity
- 23.04: Hermite Normal Form and unimodular transformations (the topics of this and of most of the following lectures can be found in here)
- 30.04: Integer solutions to systems of linear equations
- 07.05: Best approximation using continued fractions (see here)
- 14.05: Minkowski’s convex body theorem, with applications to simultaneous approximation and to the shortest vector problem
- 21.05: Basis reduction in dimension 2, orthogonality defect
- 28.05: The LLL algorithm for basis reduction
Description
Computer Algebra is concerned with algorithmic challenges emerging from the interplay of Algebra and Computer Science. In this course, students will learn how to design and analyze efficient algorithms for basic arithmetic, polynomials, fast linear algebra and elementary number theory.
Schedule
Lecture: Tuesday 15:15 – 17:00 (MA A1 12); first lecture on February 19th
Exercises: Tuesday 17:15 – 19:00 (MA A1 12); first session on February 19th
Grading
Your grade will be determined by a written final exam. You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you solve 50% or more of the exercises, the grade of your final exam will be improved by a half grade. If you solve 90% or more of the exercises, the grade of your final exam will be improved by a full grade.
Here you find a past exam.
Assignments
We will publish an assignment sheet with problems and practical exercises on this website. You can work on the exercises, ask questions, and discuss problems during the exercise sessions.
You will have the opportunity to hand in written solutions for feedback. Correct solutions to selected “star” problems give bonus points. We will discuss solutions during the exercise sessions.
Notes on some of the previous exercises will also be posted below. However, they typically do not contain complete solutions and only give final results and/or a rough sketch of a viable solution approach.
- Assignment 1 (due date: March, 05th);
- Assignment 2 assignment02.py (due date: March, 19th);
- Assignment 3 (due date: April, 09th);
- Assignment 4 (due date: April, 23rd);
- Assignment 5 (due date: May, 07th);
- Assignment 6 (due date: May, 21th);
- Assignment 7 (due date: May, 31th);
Literature and links
- Victor Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press. (available online)
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms, McGraw Hill. (library, online draft)
- Joachim von zur Gathen, Jürgen Gerhard. Modern Computer Algebra, Cambridge University Press. (library)
- A Tutorial on Sage.
- The Sage Notebook, an online tool for creating, sharing, and running Sage worksheets.