Prof. Friedrich Eisenbrand

Nicolai Hähnle

• Fixed a typo in the hint of Sheet 7, Exercise 5
• May 17: Lattices, Minkowski's theorem
• May 10: Black box linear algebra (Wiedemann's algorithm)
• May 3: Bipartite matchings, linearly recurrent sequences
• April 26: Gauss elimination, testing the existence of perfect matchings using determinants
• The deadline for submitting the practical exercise of assignment 4 (multiplying polynomials via FFT) has been extended by one week to May 4th
• April 19: Fast integer multiplication using discrete FFT
• April 12: Fast Fourier Transform continued
• March 29: Polynomial multiplication using Fast Fourier Transform (this material is covered in pp. 58 of the Algorithms book by Dasgupta, Papadimitriou, Vazirani)
• March 22: Probabilistic primality testing, asymptotic prime number theorem
• March 15: RSA, Fast modular exponentiation (repeated squaring), Fermat
• Fixed a mistake in the description of the second practical exercise and added a clarification about the timing task; added a reference implementation of the multiplication operator in the repository.
• March 8: (Extended) Euclidean algorithm, modular arithmetic, Euler's phi function
• March 1: Karatsuba multiplication, Division with Remainder, gcd
• Please inscribe yourself in the group computer-algebra-2010 on groups.epfl.ch to be able to access the Subversion repository for practical exercises
• February 22: Fibonacci numbers, Big Oh notation, basic arithmetic
• Announcements and course topics will be posted here

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.

Lecture: Monday 10:15 - 12:00 (MA A330); Lectures start on February 22nd
Exercises: Tuesday 8:15 - 10:00 (MA A330); first session on February 23rd
Final exam: Tuesday, June 29th, 8:15 - 11:15 (CM 1100)

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.

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 7 (May 25; no solutions to hand in due to end of semester)
• Assignment 6 (May 11; hand in solutions on May 25)
• Assignment 5 (April 27; hand in solutions on May 11)
• Assignment 4 (April 13; hand in solutions on April 27)
• Assignment 3 (March 23; hand in solutions on April 13)
• Assignment 2 (March 9; hand in solutions on March 23)
• Assignment 1 (February 23; hand in solutions on March 9)

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

• Coursebook description