Programme And Module Handbook
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 LM Randomness and Computation
Department Mathematics
Module Code 06 36084
Module Lead Dr Richard Mycroft & Dr Matthew Jenssen
Level Masters Level
Credits 20
Semester Semester 2
Restrictions None
Description Randomness and Computation comprises a selection of topics in Probability and an introduction to the foundations of the Theory of Computation with the aim of aiding students to develop a detailed understanding of the design and analysis of randomised algorithms. The module is aimed at students who have an 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 and applications, for example, in stochastic models in finance.

The module is structured into two coherent parts: Randomness and Computation. 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 considers 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.
Learning Outcomes By the end of the module students should be able to:
  • Understand the concept of (martingale) concentration inequalities and be able to apply these in both standard and more advanced situations.
  • Apply the mathematical ideas and techniques introduced throughout the module to the analysis of random graphs and related problems, including those in a modern mathematical and research-informed context.
  • Demonstrate a sound understanding of the concepts of complexity classes and their connections and be able to apply these to solve appropriate problems.
  • Understand the efficiency and application of randomised algorithms in a research-led context to the study of hard problems.
  • Understand the applications of the ideas, techniques and theories studied within the module to applications and subject areas outside of mathematics.
Assessment 36084-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions 3 hour Written Unseen Examination (80%); In-course Assessment (20%).
Reading List