Lecturer
Assistant
News & Log
17.02: Big O notation. Basic arithmetic operations. School method for addition and multiplication. Karatsuba algorithm. Notes
24.02: Division with remainder. (Extended) Euclidean algorithm. Basics of modular arithmetic and groups. Notes
03.03: Groups, subgroups, cosets. Lagrange and Fermat’s little theorem. Rings and homomorphisms. Fast modular exponentiation. Notes
10.03: Chinese Remainder Theorem. Euler’s totient function. Introduction to RSA cryptosystem and primality testing. Notes
17.03: Weak Fermat and Miller-Rabin primality tests. Carmichael numbers. Introduction to the density of prime numbers. Notes
24.03: Chebyshev’s Theorem on the density of primes. Hadamard bound on the determinant of a matrix. Notes
31.03: Schwartz-Zippel Lemma. Randomized test for the existence of a perfect matching in a graph. No slides. For notes, check lecture 5 of last semester’s randomized algorithms course by Prof. Eisenbrand.
07.04: No lecture.
14.04: Primitive roots of the unity, Discrete Fourier Transform and Fast Fourier Transform in fields and commutative rings with unity. Check the scanned notes, and the slides from last year’s lecture.
21.04: Introduction to lattices. Hermite Normal Form of a matrix: uniqueness and polynomial-time algorithm for computing it. Check the scanned notes, and the slides from last year’s lecture. Also, most of the content of this and the following lectures can be found in this survey.
28.04: Analysis of algorithm for computing HNF, shortest vector problem, Gauss-Lagrange algorithm for shortest vector in 2 dimensions. Slides of last year’s lecture.
05.05: Minkowski’s convex body theorem, with application to shortest vector and simultaneous approximation. Orthogonality defect. Slides of last year’s lecture.
12.05: The LLL algorithm (first part). Slides of last year’s lecture.
19.05: The LLL algorithm (second part).
26.05: An application of geometry of numbers: diophantine approximation and continued fractions. Check this article by Prof. Eisenbrand
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 (GR B3 30); first lecture on February 19th
Exercises: Tuesday 17:15 – 19:00 (GR B3 30); 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.
You find a past exam here.
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. Theoretical exercises can be submitted in groups of up to 3 people. Coding exercises must be submitted individually. Please comment your code thoroughly. Correct solutions to selected “star” problems give bonus points. The deadline is two weeks after the sheet is issued. More precisely, the deadline is:
- 15:00 if you leave your solutions in the box next to office MA B1 533 (be sure you put them in the correct box).
- 17:10 if you are sending your solutions via mail or you hand them personally to the assistant before the exercise session starts.
We will discuss solutions during the exercise sessions. Notes on some of the previous exercises will also be posted below.
- Due March 3: Assignment 1, python file. Notes, implementation, plot.
- Due March 17: Assignment 2. Notes, implementation.
- Due March 31: Assignment 3. Notes, implementation.
- Due April 21: Assignment 4. Notes, implementation.
- Due May 5: Assignment 5. Notes, implementation.
- Due May 19: Assignment 6. Notes, implementation.
- due May 26: Assignment 7. Notes.
Literature and Links
- Here you can find a survey written by Prof. Eisenbrand on some algorithmic question about lattices and related topics.
- 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 Python 2.
- You can run Python 2 online here.