Course pages 2015–16
Discrete Mathematics
Lectures 1-17: Proofs, Numbers, and Sets
- Notes and Workouts
- Supervision exercises
Michaelmas term
Xmas break
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]
Lent term
Easter break
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] - A note on enumerability.
- Q&A forum
- Lecture slides and topics
Michaelmas term
Lecture 1 (Nov 6): proof; implication.
Lecture 2 (Nov 9): contrapositive; modus ponens; bi-implication; divisibility; congruence.
Lecture 3 (Nov 11): divisibility; congruence; universal quantification; equality; conjunction.
Lecture 4 (Nov 13): existential quantification; unique existence; disjunction.
Lecture 5 (Nov 16): Fermat's Little Theorem.
Lecture 6 (Nov 18): negation; contrapositive; proof by contradiction.
Lecture 7 (Nov 20): natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; division theorem and algorithm.
Lecture 8 (Nov 23): modular arithmetic; sets; membership; comprehension; gcd; Euclid's Algorithm.
Lecture 9 (Nov 25): Euclid's Algorithm; properties of gcds; Euclid's Theorem; fields of modular arithmetic; Extended Euclid's Algorithm.
Lecture 10 (Nov 27): Extended Euclid's Algorithm; linear combinations; Diffie-Hellman cryptographic method: shared secret key, key exchange.
Lecture 11 (Nov 30): Mathematical induction; Fundamental Theorem of Arithmetic.
Lecture 12 (Dec 2): Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox. empty set; cardinality; powerset axiom.
Lent term
Lecture 13 (Jan 15): cardinality of powersets; powerset Boolean algebra; pairing axiom; ordered pairs.
Lecture 14 (Jan 18): products; big unions; big intersections; union axiom; disjoint unions.
Lecture 15 (Jan 20): relations; internal diagrams; relational composition; relational extensionality; relations and matrices.
Lecture 16 (Jan 22): directed graphs; adjacency matrix; reflexive-transitive closure; preorders; partial functions; functions; retractions; sections; bijections; equal cardinality.
Lecture 17 (Jan 25): equivalence relations; set partitions; calculus of bijections; characteristic functions; finite cardinality; infinity axiom; surjections; enumerability; injections; replacement axiom; set-indexed constructions; foundation axiom.
Lectures 18-24: Formal Languages and Automata
- Lecture notes [pdf].
- Slides [colour pdf]:
- Exercise sheet [pdf].
- Past exam questions This part of the course contains
material which before 2013-14 was lectured in courses called
Discrete Mathematics II and Regular Languages and Finite
Automata. Here is a list of recent relevant Tripos Questions:
- 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
- Further resources:
- The material in lectures 1 and 2 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 material in lectures 3-7 (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).