home search a-z help
University of Cambridge Computer Laboratory
Computer Science Syllabus - Discrete Mathematics I
Computer Laboratory > Computer Science Syllabus - Discrete Mathematics I

Discrete Mathematics I next up previous contents
Next: Foundations of Computer Science Up: Michaelmas Term 2006: Part Previous: Digital Electronics   Contents


Discrete Mathematics I

This course is taken by Part IA (50% Option) students.

Lecturer: Professor P. Robinson

No. of lectures: 12

This course is a prerequisite for all theory courses as well as Discrete Mathematics II, Security (Part IB and Part II), Artificial Intelligence (Part IB and Part II), Information Theory and Coding (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. [3 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}$. [4 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. [5 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 reading

* Humphreys, J.F. & Prest, M.Y. (1989). Numbers, groups and codes. Cambridge University Press.
Anderson, J.A. (2003). Discrete mathematics with combinatorics. Prentice Hall.
Conway, J.H. & Guy, R.K. (1996). The book of numbers. Springer-Verlag.
Davenport, H. (1992). The higher arithmetic (6th ed.). Cambridge University Press.
Giblin, P. (1993). Primes and programming. Cambridge University Press.
Pólya, G. (1980). How to solve it. Penguin.
Rosen, K.H. (1999). Discrete mathematics and its applications (4th ed.). McGraw-Hill.



next up previous contents
Next: Foundations of Computer Science Up: Michaelmas Term 2006: Part Previous: Digital Electronics   Contents
Christine Northeast
Tue Sep 12 09:56:33 BST 2006