This space will be used for announcements. Check it regularly.
The course is over. Have a nice Summer.
General Information
Course goals: This course is an introduction to basic
algebraic algorithms that are useful for computer algebra systems.
More specifically, operations like multiplication, division,
greatest common divisors and factorization are studied over
several domains including the ring of integers, finite fields,
polynomial rings, and quotient rings. The basic tools considered
include modular arithmetic, discrete Fourier transform, Chinese
remainder theorem and Newton iteration. Time permitting, we may
consider advanced topics like Grobner bases and their applications,
Hensel techniques or an overview of the structural properties of
finite fields covering some applications to cryptography or
coding theory.
Prerequisities: mathematical maturity is recommended.
Although not required, at least one undergraduate abstract
algebra course may be useful; undergraduate courses in
discrete mathematics and in data structures could be helpful.
Tentative lecture schedule
(html file) as of December 2003 (before classes start).
The actual material covered in each lecture is below.
Textbook:
Modern Computer Algebra by Joachim von zur Gathen
and Jurgen Gerhard, 2nd edition, Cambridge University Press, 2003.
Language: Maple, a system for symbolic mathematical
computation. Here is a list of Maple
manuals and books that present mathematical material with
the help of Maple. For the implementations in the assignments,
C can also be used.
Classes begin: Monday, January 5, 2004. Classes end: Wednesday, March 31, 2004. Winter break: February 16-20, 2004.
Term mark:
There will be two assignments and a project for a total of 50%
of the mark. The tentative schedule of assignments is below.
Assignment
Hand-out Date
Due Date
Contents
Worth
1
February 9
March 1
Multiplication, gcd, EEA
15%
2
March 1
March 22
Interpolation, Chinese remainder,
fast algorithms, DFT
15%
Evaluation:
In addition to the two assignments there is an individual project
worth 20% of the final mark. Projects can not exceed 10 pages and
can be about any topic in the textbook not covered in lectures or
assignments. The lecturer and the student must agree on the project
by the first week of March. The deadline to hand-in the project is
the last day of classes (March 31, 2004).
Term mark is 50% and final examination is 50%.
Withdrawal:
The last day for withdrawal from the course without academic penalties
March 12, 2004.
Students with Disabilities:
Students with Disabilities who require academic accommodations
please feel free to see me, and contact the Paul Menton Centre
to complete the required forms.
Some files may be in postcript format. If you don't have
a software to view postscript files, you may download a
ghostview software.