Computer Laboratory

Course pages 2016–17

Discrete Mathematics

Lectures 1-19: Proofs, Numbers, and Sets

Lectures 20-24: Formal Languages and Automata

  • 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:
  • 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).