MATH3502: Combinatorial Optimisation

MATH3502 course Syllabus (pdf file)

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

Charles Morgan, Oct 2009