``What to study'' for RC Exam, May 2019

Exam Format

The exam format is the same as before - answer 2 out of the 3 questions offered.

There are five years of RC exams online, from 2013, 2014 and 2015, and then 2017 and 2018. The first 3 years were written by the previous RC lecturer, Ilias Diakonikolas. The 2017 and 2018 papers were written by me.
The 3 topics asked about will be to some extent spaced out throughout the sequence of lectures.
Ilias' papers tended to be very "problem based" and sometimes a single question would have sub-parts that were not related. In the past I have tended to have each of the questions grouped around a theme. The May 2019 paper is a slight variant on my usual style - the 1st question is "problem-solving" (with the sub-parts unrelated) and the 2nd and 3rd questions are my usual style. You may chose any two.

What to study

Lecture 19 is not examinable.
All of lectures 1-18 (inclusive) are examinable.
For the longer-proofs of topics like Coupon Collecting (lecture 5), I will sometimes "break up" the material into sub-parts if I was asking you to re-produce one of these longer proofs.
The second lecture on Balls-in-bins (Lecture 10) is new this year. I expect you to know the relationship between Poisson variables (with appropriate parameters) and Balls-in-bins/binomial distributions, and to know the statements of Thm (5.5), Thm (5.7), Corollary (5.9). I also expect you to know the full proof of Lemma 5.12 on slides 8-10.
Lecture 13 on the Lovasz Local Lemma is new this year. I don't expect you to know the proof of the LLL itself (indeed we didn't prove it in class), but I do expect you to know how to apply it to solve problems.
Shorter proofs (say just a couple of slides) I would expect you to be able to reproduce. And of course, how to use their results in practice (eg applying Markov, Chebyshev's Inequalities).
We did not talk much about asymptotic notation in the course, because I assumed you knew and understood these symbols. I assume you will know definitions for all the standard asymptotic symbols - to include O(.), Ω(.), Θ(.) and also "little-o" o(.) and "little-omega" ω(.). You should also be able to work with these concepts, as in questions on the probabilistic method on G(n,p), for example.
I expect you to know commonly-used equations in discrete Maths and probability - for example, how to sum a geometric series ... all those useful properties of "lg" and "log" ... and standard "sum-of-series" formulae for (sum i) and (sum i^2)... and of course the fact that (1+x) < e^x for all x (and the versions for (1+1/n)^n relating to e). And you should be able to *use* these. Formulae which are more rare would be provided as part of the question.
You should know the details of the statements of the key Chernoff Bounds off by heart: those are Corollary 4.6, the statements of Thm 4.4 and Thm 4.5, and also Theorem 4.7.
- You should also be comfortable *using* the Chernoff Bounds to work out how many samples suffice to have good estimates in various scenarios. We have seen C bounds used in many circumstances during the semester (both in the slides, and the coursework), so you've lots of practice.
- However, you do not need to know the proofs of Theorem 4.4 or Theorem 4.5 (as you remember, I did the proof of Thm 4.4 in class).
You should know the coursework assignments, and understand:
- Our feedback on your own submission.
- The Official Solutions (available on the course webpage).
The past exam papers (see Library) are good practice. If you have questions about solutions, drop me a line (we don't publish official solutions).
You should have practised the tutorial sheets (and I hope, attended the tutorials). Some of the solutions are already online, and I will upload the missing ones soon.
The course textbook has questions throughout, and those are good practice for the concepts you meet through the course.

Home : Teaching : Courses

Mary Cryan, mcryan AT inf DOT ed DOT ac DOT uk, Informatics Forum 5.18, ext. 505153