Course pages 2016–17
Discrete Mathematics
Lectures 1-19: Proofs, Numbers, and Sets
- Lecture notes
- Lecture slides and topics
Michaelmas term
Lecture 1 (Nov 4): proof; implication.
Lecture 2 (Nov 7): contrapositive; modus ponens; bi-implication; divisibility; congruence.
Lecture 3 (Nov 9): divisibility; congruence; universal quantification; equality; conjunction.
Lecture 4 (Nov 11): existential quantification; unique existence; disjunction.
Lecture 5 (Nov 14): Fermat's Little Theorem; negation.
Lecture 6 (Nov 16): contrapositive; proof by contradiction; natural numbers; monoids; commutativity; semirings.
Lecture 7 (Nov 18): cancellation; inverses; integers; rationals; division theorem and algorithm; modular arithmetic.
Lecture 8 (Nov 21): modular arithmetic; sets; membership; comprehension; gcd; Euclid's Algorithm.
Lecture 9 (Nov 23): properties of gcds; Euclid's Theorem; fields of modular arithmetic; extended Euclid's Algorithm; linear combinations.
Lecture 10 (Nov 25): Diffie-Hellman cryptographic method: shared secret key, key exchange; mathematical induction.
Lecture 11 (Nov 28): Fundamental Theorem of Arithmetic; Euclid's infinitude of primes; sets; extensionality.
Lecture 12 (Nov 30): subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets.
Lent term
Lecture 13 (Jan 20): powerset axiom; powerset Boolean algebra; pairing axiom; ordered pairs.
Lecture 14 (Jan 23): ordered pairs; products; big unions.
Lecture 15 (Jan 25): big intersections; union axiom; disjoint unions; relations; internal diagrams; relational composition.
Lecture 16 (Jan 27): relational extensionality; relational composition; relations and matrices; directed graphs.
Lecture 17 (Jan 30): adjacency matrix; reflexive-transitive closure; preorders.
Lecture 18 (Feb 1): partial functions; functions; retractions; sections; bijections; equal cardinality; equivalence relations; set partitions.
Lecture 19 (Feb 3): calculus of bijections; characteristic functions; finite cardinality; infinity axiom; surjections; enumerability; injections. - A note on enumerability.
- Exercises
Michaelmas term
Lent term - Past exam questions
Xmas break
2016 Paper 2 Question 9 (a) [solution notes]
2016 Paper 2 Question 8 (a) & (b) [solution notes]
2016 Paper 2 Question 7 (a) [solution notes]
2015 Paper 2 Question 9 (a) [solution notes]
2015 Paper 2 Question 8 (a) & (b) [solution notes]
2015 Paper 2 Question 7 (a) & (b) [solution notes]
2014 Paper 2 Question 7 [solution notes]
2007 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 4 [solution notes]
Easter break
2016 Paper 2 Question 9 (b) & (c) [solution notes]
2016 Paper 2 Question 8 (c) [solution notes]
2016 Paper 2 Question 7 (b) [solution notes]
2015 Paper 2 Question 9 (b) & (c) [solution notes]
2015 Paper 2 Question 8 (c) [solution notes]
2015 Paper 2 Question 7 (c) [solution notes]
2014 Paper 2 Question 8 [solution notes]
2013 Paper 2 Question 5 [solution notes]
2011 Paper 2 Question 5 [solution notes]
2009 Paper 1 Question 4 [solution notes]
2008 Paper 2 Question 3 [solution notes]
2007 Paper 2 Question 5 [solution notes]
2006 Paper 2 Question 5 [solution notes]
Lectures 20-24: Formal Languages and Automata
- Lecture slides as distributed
- Errata to distributed slides
- Lecture slides with corrections
- Examples Sheet
- 2014 Paper 2 Question 9 – solution notes
- 2014 Paper 2 Question 10 – solution notes
- 2013 Paper 2 Question 6 – solution notes
- 2013 Paper 2 Question 8 – solution notes
- 2012 Paper 2 Question 6 – solution notes
- 2012 Paper 2 Question 8 – solution notes
- 2011 Paper 2 Question 8 – solution notes
- 2010 Paper 2 Question 5 – solution notes
- 2010 Paper 2 Question 9 – solution notes
- 2009 Paper 2 Question 5 – solution notes
- 2009 Paper 2 Question 9 – solution notes
- 2007 Paper 2 Question 6, part (a) – solution notes
- 2007 Paper 2 Question 8 – solution notes
- 2006 Paper 2 Question 6, part (b) – solution notes
- 2006 Paper 2 Question 8 – solution notes
- The material on inductively defined subsets and proof by rule induction is of fundamental importance for many computer science applications (especially those connected with semantics of languages). However, it is not as well covered in the literature as the later parts (for which see the recommended text by Kozen, for example). One undergraduate text covering rule-based induction is: Moller, F and Struth, G (2013) Modelling Computing Systems, Springer Undergraduate Topics in Computer Science (ISBN 978-1-84800-321-7); see chapters 8 and 9.
- Russ Cox's article Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...). (Summary: "Regular expression matching can be simple and fast, using finite automata-based techniques that have been known for decades. In contrast, Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be excruciatingly slow. With the exception of backreferences, the features provided by the slow backtracking implementations can be provided by the automata-based implementations at dramatically faster, more consistent speeds.")
- The script of a stage play about regular expressions (really).