Course pages 2013–14
Discrete Mathematics
Lectures 1-17: Mathematical Argument, Number Systems, and Mathematical Structure
- Notes and
Workouts
Handout 1
Handout 2
Handout 3 - Slides
Lecture 1 (Jan 17)
Lecture 2 (Jan 20)
Lecture 3 (Jan 22)
Lecture 4 (Jan 24)
Lecture 5 (Jan 27)
Lecture 6 (Jan 29)
Lecture 7 (Jan 31)
Lecture 8 (Feb 3)
Lecture 9 (Feb 5)
Lecture 10 (Feb 7)
Lecture 11 (Feb 10)
Lecture 12 (Feb 12)
Lecture 13 (Feb 14)
Lecture 14 (Feb 17)
Lecture 15 (Feb 19)
Lecture 16 (Feb 21)
Lecture 17 (Feb 24) - Exercise sets
Lectures 1-11
Lectures 12-17: Workouts 21--34; Workout 35, items 1--3; Workout 37, items 1 & 2; and Workout 38. - A list of recent relevant past exam questions
2013 Paper 2 Question 5 --- solution notes
2012 Paper 1 Question 4 (a) & (b) --- solution notes
2011 Paper 2 Question 5 --- solution notes
2009 Paper 1 Question 3 (c) --- solution notes
2009 Paper 1 Question 4 --- solution notes
2009 Paper 2 Question 6 --- solution notes
2008 Paper 2 Question 3 --- solution notes
2007 Paper 2 Question 3 --- solution notes
2007 Paper 2 Question 5 --- solution notes
2006 Paper 2 Question 3 --- solution notes
2006 Paper 2 Question 4 --- solution notes
2006 Paper 2 Question 5 (a) & (b) --- solution notes - Complementary reading
- Sample chapters of How to Think Like a Mathematician by K. Houston.
- The preprint Mathematics for Computer Science (Revised Edition) by E. Lehman, F.T. Leighton, and A.R. Meyer.
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 in previous years was lectured in courses called
Discrete Mathematics II and Regular Languages and Finite
Automata. Here is a list of recent relevant Tripos Questions:
- 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:
- 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).