# Final Project List

###
CS 680-503 Computer Algebra I

Instructor: Jeremy Johnson

Due date: Wed. Mar. 15 by 6pm

Computer Algebra I requires a final project inplace of a final exam.
The final project is due when the final exam would be held (i.e. at
the regular class time during finals week). All project must be
done individually. They typically require studying, implementing,
and analyzing an algorithm - the analysis will require empirical
benchmarking. The list of topics is given below. A topic must be
selected by class time on Wed. Feb. 23.
Everyone should read through the references for their project prior
to class on Wed. Mar. 1.
Please arrange an appointment to see me if you have questions.

## Possible Project Topics

More details and references will be provided.
- Project 1:
Lehmer based integer gcd algorithm. Study the performance gain due
to exact integer quotient algorithm.
- Project 2:
Empirically and theoretically analyze the performance of several
polynomial remainder sequence (PRS) based gcd algorithms.
- Implement, in SACLIB, the fast Gaussian integer gcd algorithm due
to Caviness and Collins. Empirically compare its performance to the
Euclidean algorithm using nearest quotient based remainder computation
as discussed in class. See handout from a paper from the Proceedings of
SYMSAC '76.
- Investigate the worst case behavior of the Euclidean algorithm for
Gaussian integers. See handout from a paper by Rolletschek.
- Empirically investigate the average number of divisions and probability
of relative primality for rings of quadratic integers that are
Euclidean domains (e.g. Z[i], Z[rho]). A complete list will be provided
shortly. Students doing this project should begin with Z[rho]. See
extra assignment 2.
- Implement, in SACLIB, and empirically analyze an asymptotically fast
polynomial gcd computation. Computation should be performed with polynomials
whose coefficients are in Z_p, where p is a prime BETA-digit. See handout
from Aho, Hopcroft, and Ullman text on the Design and Analysis of Algorithms.
- Implement and empirically investigate the Sparse-Zipple polynomial gcd
algorithm. This is described in chapter 7 of the text.
- Implement and empirically investigate the EZGCD polynomial gcd algorithm. This is described in chapter 7 of the text.
- Implement and empirically investigate GCDHEU (heuristic
polynomial gcd algorithm using integer gcd computation)
due to Char et. al. This is described in chapter 7 of the text.