 Course Details in 2025/26 Session

If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title LH Randomness and Computation Mathematics Mathematics 06 31131 Richard Mycroft Honours Level 20 Semester 2 LC Probability & Statistics - (06 25663) LC Algebra & Combinatorics 1 - (06 25659) LI Algebra & Combinatorics 1 - (06 27363) LI Probability & Statistics - (06 26709) None Lecture-40 hours Tutorial-10 hours Guided independent study-150 hours Total: 200 hours This module comprises a selection of topics in Probability and an introduction to the foundations of the Theory of Computation. The final goal of the module is to develop a detailed understanding of the design and analysis of randomised algorithms. The module is aimed at students with interest in theoretical aspects of computing, graph theory, combinatorics, statistics or data science. Structures arising throughout the module also play important roles in other settings, for example, in stochastic models in finance.The module is structured into two parts: Randomness and Computation. The first part of the module (Randomness) covers advanced techniques in probability theory including classical concentration inequalities, martingale theory and an introduction to random graphs. This part of the module also treats simple randomised algorithms such as randomised Quicksort. The second part of the module (Computation) provides an introduction to the Theory of Computation covering topics such as (randomised) complexity classes, P vs. NP, Las Vegas and Monte Carlo algorithms and decidability. The module concludes with the presentation of the design and the analysis of several efficient randomised algorithms, which provide approximate solutions to computationally hard problems such as satisfiability and Max-cut. In each part of the module practical examples supplement and illustrate the theoretical concepts developed. By the end of the module students should be able to:Understand the concept of (martingale) concentration inequalities and apply these in standard situationsApply the techniques introduced in the course to the analysis of random graphs and related problemsDemonstrate an understanding of the concepts of complexity classes and their connectionsUnderstand the efficiency of randomised algorithms in the study of hard problems 31131-03 : Raw Module Mark : Coursework (100%) Assessment: 2 hour Summer Examination (80%); In-course Assessment (20%).