CS356 Approximation and Randomised Algorithms
CS35615 Approximation and Randomised Algorithms
Introductory description
The module aims to introduce students to the area of approximation and randomised algorithms, which often provide a simple and viable alternative to standard algorithms.
Module aims
Students will learn the mathematical foundations underpinning the design and analysis of such algorithms.
Outline syllabus
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.
 Linearity of expectation, moments and deviations, coupon collector's problem
 Chernoff bounds and its applications
 Balls into bins, hashing, Bloom filters
 The probabilistic method, derandomization using conditional expectations
 Markov chains and random walks
 LP duality, relaxations, integrality gaps, dual fitting analysis of the greedy algorithm for set
cover.
The primal dual method: Set cover, steiner forest  Deterministic rounding of LPs: Set cover, the generalized assignment problem
 Randomized rounding of LPs: Set cover, facility location
 Multiplicative weight update method: Approximately solving packing/covering LPs
If time permits, more topics can be covered such as Tail inequalities for martingales, SDP based algorithms, local search algorithms, PTAS for Euclidean TSP, metric embeddings, hardness of approximation, online algorithms or streaming.
Learning outcomes
By the end of the module, students should be able to:
 1. Understand and use suitable mathematical tools to design approximation algorithms and analyse their performance.
 2. Understand and use suitable mathematical tools to design randomised algorithms and analyse their performance.
 3. Learn how to design faster algorithms with weaker (but provable) performance guarantees for problems where the best known exact deterministic algorithms have large running times.
Indicative reading list
Please see Talis Aspire link for most up to date list.
View reading list on Talis Aspire
Subject specific skills
 Use of LP relaxations and related algorithm design paradigms in approximation algorithms
 Use of Chernoff bounds and related tools from discrete probability in randomised algorithms
 Systematic techniques for derandomising randomised algorithms
Transferable skills
 Communication  Reading and writing mathematical proofs
 Critical Thinking  Problem solving
 Technical  Technological competence and staying current with knowledge
Study time
Type  Required 

Lectures  30 sessions of 1 hour (20%) 
Seminars  9 sessions of 1 hour (6%) 
Private study  111 hours (74%) 
Total  150 hours 
Private study description
Revision of lectures
Reading up on lecture notes and book chapters posted on the module webpage
Going through the problems solved during seminar sessions
Solving past exam papers
Costs
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.
Assessment group D2
Weighting  Study time  

Homework Assignment  20%  
Inperson Examination  80%  
CS356 exam.

Assessment group R1
Weighting  Study time  

Inperson Examination  Resit  100%  
CS356 resit examination

Feedback on assessment
 Marked scripts available on students' request
 Group feedback in seminars
Prerequisites
Students must have studied the material in CS260 or studied equivalent relevant prerequisite material.
Courses
This module is Core for:

UCSAG4G1 Undergraduate Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of UCSAG4G3 Undergraduate Discrete Mathematics
 Year 4 of UCSAG4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
 Year 4 of UCSAG4G2 Undergraduate Discrete Mathematics with Intercalated Year
This module is Optional for:
 Year 4 of UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)

USTAG1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
 Year 3 of G1G3 Mathematics and Statistics (BSc MMathStat)
 Year 4 of G1G3 Mathematics and Statistics (BSc MMathStat)

USTAG1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
 Year 4 of G1G4 Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
 Year 5 of G1G4 Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
This module is Option list A for:
 Year 4 of UCSAG504 MEng Computer Science (with intercalated year)

UCSAG500 Undergraduate Computer Science
 Year 3 of G500 Computer Science
 Year 3 of G500 Computer Science

UCSAG502 Undergraduate Computer Science (with Intercalated Year)
 Year 4 of G502 Computer Science with Intercalated Year
 Year 4 of G502 Computer Science with Intercalated Year

UCSAG503 Undergraduate Computer Science MEng
 Year 3 of G500 Computer Science
 Year 3 of G503 Computer Science MEng
 Year 3 of G503 Computer Science MEng

USTAG302 Undergraduate Data Science
 Year 3 of G302 Data Science
 Year 3 of G302 Data Science
 Year 3 of USTAG304 Undergraduate Data Science (MSci)
 Year 4 of USTAG303 Undergraduate Data Science (with Intercalated Year)
This module is Option list B for:

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)
 Year 4 of G105 Mathematics (MMath) with Intercalated Year
 Year 5 of G105 Mathematics (MMath) with Intercalated Year

UMAAG100 Undergraduate Mathematics (BSc)
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics

UMAAG103 Undergraduate Mathematics (MMath)
 Year 3 of G100 Mathematics
 Year 3 of G103 Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)

UMAAG106 Undergraduate Mathematics (MMath) with Study in Europe
 Year 3 of G106 Mathematics (MMath) with Study in Europe
 Year 4 of G106 Mathematics (MMath) with Study in Europe

USTAGG14 Undergraduate Mathematics and Statistics (BSc)
 Year 3 of GG14 Mathematics and Statistics
 Year 3 of GG14 Mathematics and Statistics
 Year 4 of USTAGG17 Undergraduate Mathematics and Statistics (with Intercalated Year)
 Year 4 of UMAAG101 Undergraduate Mathematics with Intercalated Year