Probability in Computing

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

• The use of concentration inequalities.
• The use of randomness in the analysis of algorithms.
• The use of randomness in the design of algorithms.
• The difference between worst-case and average-case complexity of algorithms and its importance.

Subject Specific Practical Skills

Having successfully completed this module you will be able to:

• Implement exact randomised algorithms.
• Implement randomised data structures.
• Use probabilistic concepts and randomisation to implement approximation algorithms.

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.

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

The modules consists of

• Lectures
• Guided self-study

Summative

This is how we’ll formally assess what you have learned in this module.