Computer Algebra

Assistant

Alfonso Cevallos

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.

 

  • 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.