Skip to main content Skip to navigation

Module Catalogue

CS356-15 Approximation and Randomised Algorithms

Department
Computer Science
Level
Undergraduate Level 3
Module leader
Sayan Bhattacharya
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

Download as PDF

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
  1. Use of LP relaxations and related algorithm design paradigms in approximation algorithms
  2. Use of Chernoff bounds and related tools from discrete probability in randomised algorithms
  3. Systematic techniques for derandomising randomised algorithms
Transferable skills
  1. Communication - Reading and writing mathematical proofs
  2. Critical Thinking - Problem solving
  3. 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%
In-person Examination 80%

CS356 exam.

  • Answerbook Pink (12 page)
Assessment group R1
Weighting Study time
In-person Examination - Resit 100%

CS356 resit examination

  • Answerbook Pink (12 page)
Feedback on assessment
  • Marked scripts available on students' request
  • Group feedback in seminars

Past exam papers for CS356

Pre-requisites

Students must have studied the material in CS260 or studied equivalent relevant pre-requisite material.

Courses

This module is Core for:

  • UCSA-G4G1 Undergraduate Discrete Mathematics
    • Year 3 of G4G1 Discrete Mathematics
    • Year 3 of G4G1 Discrete Mathematics
  • Year 3 of UCSA-G4G3 Undergraduate Discrete Mathematics
  • Year 4 of UCSA-G4G2 Undergraduate Discrete Mathematics with Intercalated Year

This module is Optional for:

  • USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
    • Year 3 of G1G3 Mathematics and Statistics (BSc MMathStat)
    • Year 4 of G1G3 Mathematics and Statistics (BSc MMathStat)
  • USTA-G1G4 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 UCSA-G504 MEng Computer Science (with intercalated year)
  • UCSA-G500 Undergraduate Computer Science
    • Year 3 of G500 Computer Science
    • Year 3 of G500 Computer Science
  • UCSA-G502 Undergraduate Computer Science (with Intercalated Year)
    • Year 4 of G502 Computer Science with Intercalated Year
    • Year 4 of G502 Computer Science with Intercalated Year
  • UCSA-G503 Undergraduate Computer Science MEng
    • Year 3 of G500 Computer Science
    • Year 3 of G503 Computer Science MEng
    • Year 3 of G503 Computer Science MEng
  • USTA-G302 Undergraduate Data Science
    • Year 3 of G302 Data Science
    • Year 3 of G302 Data Science
  • Year 3 of USTA-G304 Undergraduate Data Science (MSci)
  • Year 4 of USTA-G303 Undergraduate Data Science (with Intercalated Year)

This module is Option list B for:

  • UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
    • Year 3 of G105 Mathematics (MMath) with Intercalated Year
    • Year 5 of G105 Mathematics (MMath) with Intercalated Year
  • UMAA-G100 Undergraduate Mathematics (BSc)
    • Year 3 of G100 Mathematics
    • Year 3 of G100 Mathematics
    • Year 3 of G100 Mathematics
  • UMAA-G103 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)
  • UMAA-G106 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
  • USTA-GG14 Undergraduate Mathematics and Statistics (BSc)
    • Year 3 of GG14 Mathematics and Statistics
    • Year 3 of GG14 Mathematics and Statistics
  • Year 4 of USTA-GG17 Undergraduate Mathematics and Statistics (with Intercalated Year)
  • Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year