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.
  1. Project 1: Lehmer based integer gcd algorithm. Study the performance gain due to exact integer quotient algorithm.
  2. Project 2: Empirically and theoretically analyze the performance of several polynomial remainder sequence (PRS) based gcd algorithms.
  3. 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.
  4. Investigate the worst case behavior of the Euclidean algorithm for Gaussian integers. See handout from a paper by Rolletschek.
  5. 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.
  6. 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.
  7. Implement and empirically investigate the Sparse-Zipple polynomial gcd algorithm. This is described in chapter 7 of the text.
  8. Implement and empirically investigate the EZGCD polynomial gcd algorithm. This is described in chapter 7 of the text.
  9. 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.