Lecturer
Assistant
News & Log
- 21.2.: O-notation, addition and multiplication, 3 algorithms to compute Fibonacci numbers
- 28.2.: Algorithms for Addition, Multiplication, Divide & Conquer, Karazuba
- 07.3.: Division with remainder, quadratic lower and upper bound for Euclidean Algorithm
- 14.3.: Modular Arithmetic, Euler Phi-Function, Chinese Remainder Thm., RSA
- 22.3: Randomized Primality Tests: Fermat & Miller-Rabin
- 29.3: Density of Primes and finding large primes
- 04.4: Determinants, Gaussian Elimination is a polynomial-time algorithm, Schwartz-Zippel Lemma
- 11.4: Tutte’s Lemma, Computing max.cardinality matchings with an algebraic algorithm
- 18.4: Multiplication of polynomials, evaluation and interpolation, Fast Fourier Transform (in fields)
- 02.5: Modular Fourier transform and modular FFT
- 09.5: Lattices, Lattice Determinant and Minkowski’s Theorem (the content of this and the next lectures is described here)
- 16.5:The LLL-Algorithm
- 23.5: Analysis of the LLL Algorithm, Factoring rational polynomials
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: Monday 10:15 – 12:00 (MA A3 30); first lecture on February 21st
Exercises: Tuesday 8:15 – 10:00 (MA A3 30); first session on February 22nd
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.
Assignments
We will publish an assignment sheet with problems and practical exercises on this website every two weeks. 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, assignment01.py, (discussion from February 22, hand in on March 8) Notes;
- Assignment 2, (discussion from March 8, hand in on March 22) Notes;
- Assignment 3, assignment03.py, (discussion from March 22, hand in on April 5) Notes;
- Assignment 4, (discussion from April 5, hand in on April 19) Notes;
- Assignment 5, (discussion from April 19, hand in on May 10) Notes;
- Assignment 6, (discussion from May 10, hand in on May 24) Notes;
- Assignment 7, (discussion from May 24) Notes.
Literature
- 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)