Module overview
Computer Science has evolved significantly over the past decades, and various subfields require a strong foundation in probability. Such fondation is important in studying randomized algorithms, algorithm analysis, approximation algorithms and artificial Intelligence.
Aims and Objectives
Learning Outcomes
Subject Specific Practical Skills
Having successfully completed this module you will be able to:
- Use probabilistic concepts and randomisation to implement approximation algorithms.
- Implement randomised data structures.
- Implement exact randomised algorithms.
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- The use of randomness in the design of algorithms.
- The use of randomness in the analysis of algorithms.
- The use of concentration inequalities.
- The difference between worst-case and average-case complexity of algorithms and its importance.
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Apply various concentration bounds to analyse the behaviour of random variables and algorithms in a probabilistic setting.
- Describe the relationship between average-case complexity and hard problems.
Syllabus
Concentration bounds and applications
- Markov, Chernoff, Chebyshev
- set balancing
- birthday paradox
- balls into bins,
- bucket sort
Average-case complexity
- Bin packing
- Traveling salesman problem
Randomised data structures
- Treaps
- Skip lists
- Universal hashing
- Bloom filters
Randomised algorithms.
- Quicksort and Quickselect
- Primality testing
- Karger min-cut
Approximation algorithms
- Set cover
- Monte Carlo
- SAT
- LP relaxation
- Randomised rounding
Sampling
- VC dimension
- Rademacher complexity
- Probably approximately correct learning
Learning and Teaching
Teaching and learning methods
The modules consists of
- Lectures
- Guided self-study
Type | Hours |
---|---|
Tutorial | 12 |
Wider reading or practice | 45 |
Lecture | 36 |
Assessment tasks | 45 |
Revision | 12 |
Total study time | 150 |
Assessment
Summative
This is how we’ll formally assess what you have learned in this module.
Method | Percentage contribution |
---|---|
Class Test | 10% |
Computing assignment | 10% |
Computing assignment | 10% |
Exam | 60% |
Computing assignment | 10% |