MTHM032/MAS400 Advanced Algorithmic Mathematics Syllabus & Aims and objectives 2006

1 Course information

This course builds on basic linear algebra and abstract algebra, and examines in detail two recent and very important mathematical algorithms and some of their (many) applications. The algorithms are:

• The Buchberger Algorithm for determining a Gröbner basis of an ideal of a (multivariate) polynomial ring over a field.

• The Lenstra, Lenstra, Lovász (LLL) Algorithm for calculating an LLL-reduced basis for a lattice contained in ℝ^{n}.

The mathematical background to these algorithms will be covered, together with proofs of their correctness and some analysis of their complexity. No background in computation will be assumed, and computers will not be used.

2 Aims and objectives

At the end of the course, one hopes the students are able:

• to understand the theory behind the above two algorithms;

• to reproduce (some of) the proofs underlying the above two algorithms; and

• to apply these algorithms, and related algorithms, to small examples.