CSci223 - Spring 2005

Programming Assignment #1

Euclid's GCD and LCM Algorithms

---

For your first programming assignment you will be implementing Euclid's Greatest Common Divisor and Least Common Multiple algorithms. The purpose of this assignment is to get you familiar with the C programming language and to test your ability to take a "mathematical" algorithm and turn it into code.

The instructor will provide students with a copy of pages 316-323 from Donald Knuth's Seminumerical Algorithms, Second Edition, the second volume in his The Art of Computer Programming Series. This will serve as your "definition" of the GCD and LCM algorithms.

You should begin this assignment with the code in this tarball. The only file that must be modified is the math2.c file. Take care to ensure that your math2.c works with the "standard" Makefile and math2.h files.

Your objective is to implement the gcd() and lcm() functions so that they return correct results for all combinations of negative and non-negative integer arguments.

This assignment will be graded according to the Programming Assignment Grading Sheet. Any solutions that don't compile on onyx using the supplied Makefile will receive a healthy deduction.

Students should submit their solutions by email to the instructor. They should only submit the math2.c file.

This assignment is due by class time on Wednesday, February 9th. It will be considered late at 11:00am on Thursday, February 10th. Any solutions received after graded solutions have been distributed to the class will receive a zero. Graded solutions will be distributed in class on either February 11th or 14th.

Please review the Honor Code section of the syllabus and be sure you are familiar with the applicable documents.