Computer Laboratory

Course pages 2013–14

Discrete Mathematics

Principal lecturers: Prof Marcelo Fiore, Prof Andrew Pitts
Taken by: Part IA CST
Past exam questions: Discrete Mathematics, Discrete Mathematics I
Information for supervisors (contact lecturer for access permission)

No. of lectures: 24
Suggested hours of supervisions: 8
This course is a prerequisite for all theory courses as well as Probability (Part IB), Security (Part IB and Part II), Artificial Intelligence (Part IB and Part II), Compiler Construction (Part IB) and Information Theory and Coding (Part II).

Aims

The course aims to introduce the mathematics of discrete structures, showing it as an essential tool for computer science that can be clever and beautiful.

Lectures

  • Mathematical argument [3 lectures].

    Proofs in practice. Propositional statements: conjunction, disjunction, implication, equivalence, negation. Universal and existential statements: predicates and quantification. Logical notation and inference.

  • Numbers [4 lectures].

    Inductive definitions and induction principles (mathematical induction, course-of-values induction, least-number principle).

    Divisibility and prime numbers. The fundamental theorem of arithmetic. The greatest common divisor and Euclid’s algorithm.

    Modular arithmetic: the Chinese remainder theorem, Wilson’s theorem, Fermat’s theorem, Euler’s theorem.

    Public key cryptography: Diffie-Hellman, RSA.

  • Mathematical structure [10 lectures].

    Sets: membership, extensionality, comprehension, Russell’s paradox. Finite and infinite sets. Cardinality.

    Mathematical data types: product, sum (or disjoint union), powerset. Finite constructions and counting.

    The boolean algebra of sets: intersection, union, complement, difference, symmetric difference. Venn and Hasse diagrams.

    More mathematical data types: relations, partial functions, (total) functions. Finite constructions and counting. Characteristic (or indicator) functions.

    The algebra of relations and matrices. Directed graphs (or digraphs): reflexivity, symmetry, transitivity. Transitive closure. Weighted digraphs and shortest paths.

    Functions: bijections, injections, surjections. Finite constructions and counting. Inverse and direct images.

    Combinatorial identities and bijective proofs. Partitions, equivalence relations, Stirling and Bell numbers.

    The lattice of partitions and information theory. Discrete Shannon entropy for partitions of finite sample spaces. The equipartition-maximises-information lemma.

    Countable and uncountable sets. Infinite sets: indexed sets, big intersections and unions, indexed sums and products, finite sequences. Calculus of bijections.

    Set cardinality increase. Diagonalisation: Russell’s paradox, Cantor’s diagonalisation argument, Lawvere’s fixed-point theorem.

  • Formal languages and automata [7 lectures].

    Introduction to inductive definitions using rules and proof by rule induction. Abstract syntax trees.

    Regular expressions and their algebra.

    Finite automata and regular languages: Kleene’s theorem and the Pumping Lemma.

Objectives

On completing the course, students should be able to

  • prove and disprove mathematical statements using a variety of techniques;

  • apply the mathematical principle of induction;

  • know the basics of modular arithmetic and appreciate its role in cryptography;

  • understand and use the language of set theory in applications to computer science;

  • define sets inductively using rules and prove properties about them;

  • convert between regular expressions and finite automata;

  • use the Pumping Lemma to prove that a language is not regular.

Recommended reading

Biggs, N.L. (2002). Discrete mathematics. Oxford University Press (Second Edition).
Bloch, E.D. (2011). Proofs and fundamentals: a first course in abstract mathematics. Springer (Second Edition).
Devlin, K. (2003). Sets, functions, and logic: an introduction to abstract mathematics. Chapman and Hall/CRC Mathematics (Third Edition).
Eccles, P.J. (1997) An introduction to mathematical reasoning Cambridge University Press.
* Houston, K. (2009). How to think like a mathematician: a companion to undergraduate mathematics. Cambridge University Press.
* Kozen, D.C. (1997). Automata and computability. Springer.
* Lehman, E.; Leighton, F.T.; Meyer, A.R. (2012). Mathematics for computer science, Revised edition. Pólya, G. (1980). How to solve it. Penguin. Velleman, D.J. (2006). How to prove it: a structured approach. Cambridge University Press (Second Edition).