Skip to main content Skip to navigation

DCS

CS356 Approximation and Randomised Algorithms

CS356 15 CATS (7.5 ECTS) Term 2

Availability

Core - DM, Option - CS, Mathematics

Prerequisites

CS260 Algorithms

Academic Aims

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.
Students will learn the mathematical foundations underpinning the design and analysis of such algorithms

Learning Outcomes

By the end of the module, students should:

  • Understand and use suitable mathematical tools to design approximation algorithms and analyse their performance.
  • Understand and use suitable mathematical tools to design randomised algorithms and analyse their performance.
  • 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.

Content

  • - 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.

Books

  • Mitzenmacher and Upfal. Probability and Computing. CUP
  • Motwani and Raghavan. Randomized Algorithms. CUP
  • Dubhashi and Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. CUP
  • Williamson and Shmoys. The Design of Approximation Algorithms. CUP
  • Vazirani. Approximation Algorithms. Springer

Assessment

Two-hour examination (80%), Coursework (20%)

Teaching

30 one-hour lectures plus 9 one-hour seminars


Jalote P, Fault Tolerance in Distributed Systems, Prentice Hall, 1994.
Lynch N, Distributed Algorithms, Morgan Kauffman, 1996.
Gouda M, Elements of Network Protocol Design, John Wiley, 1998.
  • Background: development and scope of social informatics; practical goals.
  • Understanding individual behaviour: perception, memory and action.
  • Modelling human interaction with digital systems.
  • Design methodologies and notations.
  • Techniques and technologies: dialogue styles, information visualisation.
  • Designer-user relations: iteration, prototyping.
  • Evaluation: formative and summative; performance and learnability.
  • Mobile computing and devices: novel interfaces; ubiquitous computing.
  • Organisational factors: understanding the workplace; resistance; dependability.
Innovation processes at scale: social shaping of IT, actor-network theory, co-production.