Course pages 2017–18
Discrete Mathematics
Lectures 1-19: Proofs, Numbers, and Sets
- Lecture notes
-
Lecture slides and topics
Michaelmas term
Lecture 1 (Nov 3): proof; implication; contrapositive.
Lecture 2 (Nov 6): modus ponens; bi-implication; divisibility; congruence; universal quantification; equality.
Lecture 3 (Nov 8): conjunction; existential quantification.
Lecture 4 (Nov 10): unique existence; disjunction; Fermat's Little Theorem.
Lecture 5 (Nov 13): negation; contrapositive; proof by contradiction; natural numbers; monoids; commutativity.
Lecture 6 (Nov 15): natural numbers; semirings; cancellation; inverses; integers; rationals; division theorem and algorithm.
Lecture 7 (Nov 17): modular arithmetic; sets; membership; comprehension; gcd.
Lecture 8 (Nov 20): Euclid's Algorithm; properties of gcds; Euclid's Theorem.
Lecture 9 (Nov 22): fields of modular arithmetic; extended Euclid's Algorithm; integer linear combinations; Diffie-Hellman cryptographic method: shared secret key, key exchange.
Lecture 10 (Nov 24): mathematical induction; Fundamental Theorem of Arithmetic.
Lecture 11 (Nov 27): Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets.
Lecture 12 (Nov 29): powerset Boolean algebra; pairing axiom; ordered pairs.
Lent term
Lecture 13 (Jan 19): products; big unions; big intersections; union axiom; disjoint unions; relations.
Lecture 14 (Jan 22): internal diagrams; relational extensionality; relational composition; relations and matrices.
Lecture 15 (Jan 24): relations and matrices; directed graphs; adjacency matrix; reflexive-transitive closure; preorders.
Lecture 16 (Jan 26): partial functions; functions.
Lecture 17 (Jan 29): retractions; sections; bijections; equal cardinality; equivalence relations; set partitions.
Lecture 18 (Feb 31): equivalence relations; set partitions; calculus of bijections.
Lecture 19 (Feb 2): characteristic functions; finite cardinality; infinity axiom; injections; surjections; enumerability; unbounded cardinality; axiom of choice; replacement axiom; set-indexed constructions; foundation axiom. - A note on enumerability.
-
Exercises
Michaelmas term
Lent term -
Past exam questions
Xmas break
2017 Paper 2 Question 9 (a) [solution notes]
2017 Paper 2 Question 8 (a) [solution notes]
2017 Paper 2 Question 7 (a) [solution notes]
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
2017 Paper 2 Question 9 (b) & (c) [solution notes]
2017 Paper 2 Question 8 (b) & (c) [solution notes]
2017 Paper 2 Question 7 (b) [solution notes]
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 notes
- Lecture slides (please do not print!)
- Exercises
- 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 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).