The module aims to introduce students to modern techniques, methods, and results from the rapidly developing field of algorithms and complexity. The main topic may change year to year.
Students will learn the algorithmic, mathematical, and probabilistic foundations underpinning modern design and analysis algorithms.
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
Typical topics include a mixture of:
By the end of the module, students should be able to:
"An Introduction to Computational Learning Theory". Umesh Vazirani and Michael Kearns.
"Mathematics + Computation". Avi Wigderson.
"Analysis of Boolean Functions". Ryan O'Donnell.
"Computational Complexity". Sanjeev Arora and Boaz Barak.
"Probability and Computing". Michael Mitzenmacher and Eli Upfal.
Students will learn basic properties and applications of a range of concrete computational models, including decision trees, small-depth circuits, threshold circuits (discrete analogues of neural networks), Boolean formulas, and general Boolean circuits.
This advanced module will provide a gentle introduction to fundamental questions connected to the power and limits of algorithms (e.g. randomness in computation, efficient learning algorithms, exhaustive search) from the vantage point of the aforementioned computational models.
Students will be introduced to a variety of mathematical techniques that can be used to establish limits on the computational power of some of these models (complexity lower bounds) and to design new algorithms (complexity upper bounds). It will cover probabilistic, algebraic, combinatorial, and analytic techniques, which will be introduced in a self-contained way through a sequence of accessible examples.
The computational models covered in this module have far-reaching applications in computer science, appearing in areas such as machine learning, optimisation, algorithms, cryptography and theoretical computer science.
The algorithmic and mathematical techniques introduced in this module are widely applicable and transcend the topics covered in this module (e.g. algebraic methods have significant applications in communication protocols, analytic techniques are employed in machine learning, and probabilistic and combinatorial techniques are ubiquitous in algorithms and optimisation).
This module will highlight fruitful interactions between computer science and mathematics, introducing new problem-solving skills and stimulating creative ideas in the design and analysis of algorithms.
|20 sessions of 1 hour (13%)
|9 sessions of 1 hour (6%)
|121 hours (81%)
Private study will consist of:
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
|Problem Set 1
Homework assignment 1
|Problem Set 2
Homework assignment 2
|Problem Set 3
Homework assignment 3
|In-person Examination - Resit
CS938 resit examination
Individual written feedback and group feedback in seminars
This module is only suitable for MSc students and mathematics students with familiarity of algorithms and complexity at the level of CS260 and CS301.
This module is Optional for: