Chapter 11 Advice and information for the exam
11.1 Format of the exam
The exam is 2 hours long and consists of 4 25 mark questions all of which are compulsory. It won’t cover every area of the course. The first two questions are designed to be easier than the second two.
11.2 List of bookwork topics
This list looks very long but I hope its mainly easy definitions. This is the list of stuff I expect you to know for the exam. For example I might say: Given a set \(A\) state the definition of the power set of \(A\).
- Definition of an element of a set
- definition of equality of sets
- natural numbers, integers and rationals (normal definitions not with quotients)
- empty set
- definition of a subset
- definition of a power set
- specification
- definition of a function
- image and preimage of points
- image and preimage of sets
- definition of injectivity, surjectivity and bijectivity
- definition of a set being finite or infinite
- statement of Cantor’s theorem
- definition of an ordered pair
- formal definition of a function
- definition of set union, interesection and difference
- distributive laws of intersection and union
- De Morgan’s laws
- definition of composition of functions
- definition of left and right inverses
- pigeonhole principle
- statement of Cantor-Schoeder-Bernstein
- definition of a relation
- reflexivity, symmetry, transitivity, antisymmetry and totality
- definition of an equivalence relation
- definition of a partition
- definition of an equivalence class
- definition of a quotient by an equivalence relation
- definition of partial and total order
- definition of a divisor
- definition of a prime number
- definition of a congruence modulo \(n\)
- definition of a Boolean operator
- equality of Boolean operators
- laws for how Boolean operators distribute, negate etc
- definition of a tautology
- how to use and make truth tables
- how to distribute and negate quantifiers \(\forall, \exists\)
- All the different patterns of proof
- Induction, strong induction and well-ordering
- definition of greatest common divisor
- definition of coprime
- definition of the least common multiple
- how to use Euclid’s algorithm
- what is a continued fraction
- Bezout’s lemma and how to compute \(x\) and \(y\) from Euclid’s algorithm
- statement of the fundamental theorem of arithmetic
- one proof of FTA
- statement of the Chinese remainder theorem
- definition of a unit modulo \(n\)
- statement of Wilson’s theorem
- proof of Wilson’s theorem
- Definition of the Euler totient function
- statement of the divisor sum
- statement of Fermat’s little theorem
- definition of a primitive root
- definition of big and little O notation
- Statement of theorem 8.1 about complexity of Euclid’s algorithm
- definition of the discrete logarithm problem
- definition of the Diffie-Hellman problem
- how to do Diffie-Hellman key exchange
- how to do RSA
11.3 Other topics you should be familiar with
In general everything else in the lecture notes which isn’t marked as non-examinable and all the questions on the exercise sheets which are easy or medium count as seen material. This means that I might reuse questions, ask for examples, or get you to do stuff similar to lemmas or parts of proof. In particular with the big proofs where I haven’t specified that the proof is bookwork I might put the proof in the exam but it will be broken into steps and have hints. I’m not expecting you to remember this stuff by heart but I hope you’ve understood it and can reconstruct it through a combination of working in out and vague recollections.
11.4 Guide to past papers
I changed some small things in the course this year and there were larger changes 3 years ago (polynomials, complex numbers and countability were removed from the course - unfortunately for me they were my favourite bits, algorithmic complexity and cryptography were added). This means some past paper questions are not relevant or may seem more difficult than they actually were. Here is a list which I hope is complete but I may have missed something.
2024: Irrelevant questions are 2 (d), (e), (f) and 3(c) 2023: I think everything is relevant 2022: 2(a) is interesting but probably was covered in lectures so will seem harder for you all, the rest of 2 is irrelevant. 3(b) is also irrelevant. 2021: This exam was open book due to covid so it may seem harder/less bookwork. 2 (c) and (d) are irrelevant. 2020: no exam due to covid 2019: 2(c) was probably seen material so will seem harder for you, q4 is irrelevant