CSC478/2412 preliminary overview, Spring 1997
Updated January 14, 1997
Introduction to computer algebra, including applications.
Fast algorithms for integers and polynomials: multiplication,
division with remainder, greatest commod divisors and Euclid's
Algorithm, Chinese Remainder Theorem computations, primality testing,
irreducibility tests for polynomials, polynomial factorization.
Tools include modular arithmetic, the Discrete Fourier Transform,
Newton iteration.
Applications include signal processing, error-correcting codes,
and cryptography.
Background
- Abstract algebra: MAT301H/(247H with preparation in ring theory)
- Algorithm analysis and complexity: CSC364
Although we will provide all the definitions required to complete
the course, familiarity with abstract algebra is a definite asset.
Evaluation
- 4 to 5 assignments, including work using Maple
- a project in Maple
Recommended reading
- Geddes, K.O., Czapor, S.R., Labahn, G.
Algorithms for Computer Algebra,
Kluwer, 1992.
- Lipson, J.D.,
Elements of Algebra and Algebraic Computing,
Addison-Wesley, 1981.
- Knuth, D.E.,
The Art of Computer Programming: Volume 2, Seminumerical
Algorithms, 2nd edition,
Addison-Wesley, 1981.
Back to CSC478/2412 home page
Back to David Neto's teaching page
Back to David Neto's home page