MATH3502: Combinatorial Optimisation
Wilf's Algorithms and Complexity (1st edition) (1.1Mb pdf file)
Python programs to calculate extended GCDs
. (Both binary gcd and Euclid.)
Examples of calculating extended GCDs (using both extended binary gcd and extended Euclid algorithms)
Rene Schoof's paper on primality tests, including proof that the Miller-Rabin test returns "composite" for three-quarters of the bases with gcd(b,n)=1 and a proof of the Agrawal-Kayal-Saxena theorem that PRIME is in P. (Both for interest - neither of these examinable.)
Martin Fürer's paper on Fast Multiplication using Fast Fourier transform, with a good overview of the FFT method.
Example sheet 1
Example sheet 2
Example sheet 3
Example sheet 4
Example sheet 5
Example sheet 6
Example sheet 7
Answers to Homework 1
Answers to Homework 2
Answers to Homework 3
Answers to Homework 4
Answers to Homework 5
Answers to Homework 6
Answer to Homework 6.5
Answer to Homework 6.6
Answers to Homework 7