Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Discrete Mathematics
Computer Laboratory > Computer Science Tripos Syllabus - Discrete Mathematics

Discrete Mathematics next up previous contents
Next: Foundations of Computer Science Up: Michaelmas Term 2004: Part Previous: Digital Electronics (50% option   Contents


Discrete Mathematics

Lecturer: Dr P. Robinson

No. of lectures: 8 (Continued into Lent Term)

This course is a prerequisite for all theory courses as well as Introduction to Security (Part IB), Artificial Intelligence I and II, Information Theory and Coding (Part II), Security (Part II).


Aims


This course will develop the idea of formal proof by way of examples involving simple objects such as integers and sets. The material enables academic study of Computer Science and will be promoted with examples from cryptography and the analysis of algorithms.


Lectures


  • Proof. Deduction, contradiction. Integers, mathematical induction. [2 lectures]

  • Factors. Division: highest common factors and least common multiples. Euclid's algorithm: solution in integers of $ax+b =c$, the complexity of Euclid's algorithm. Euclid's proof of the infinity of primes. Existence and uniqueness of prime factorisation. Irrationality of $\sqrt{p}$. [3 lectures]

  • Modular arithmetic. Congruences. Units modulo m, Euler's totient function. Chinese remainder theorem. Wilson's theorem. The Fermat-Euler theorems, testing for primes. Public key cryptography, Diffie-Hellman and RSA. [3 lectures]

Objectives


On completing the course, students should be able to

  • write a clear statement of a problem as a theorem in mathematical notation; prove and disprove assertions using a variety of techniques

  • describe, analyse and use Euclid's algorithm; explain and apply prime factorisation

  • perform calculations with modular arithmetic; use number theory to explain public key cryptography

Recommended books


* Humphreys, J.F. & Prest, M.Y. (1989). Numbers, groups and codes. Cambridge University Press.
Biggs, N.L. (1989). Discrete mathematics. Oxford University Press.
Conway, J.H. & Guy, R.K. (1996). The book of numbers. Springer-Verlag.
Davenport, H. (1992). The higher arithmetic. Cambridge University Press (6th ed.).
Giblin, P. (1993). Primes and programming. Cambridge University Press.
Pólya, G. (1980). How to solve it. Penguin.



next up previous contents
Next: Foundations of Computer Science Up: Michaelmas Term 2004: Part Previous: Digital Electronics (50% option   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004