Course finder

Semester 1

Randomized Algorithms (INFR11201)

Subject

Informatics

College

SCE

Credits

10

Normal Year Taken

4

Delivery Session Year

2023/2024

Pre-requisites

As above.

Course Summary

This course is about randomness as a resource in algorithms and computation. The course introduces basic mathematical models and techniques and applies them to the design and analysis of various randomized algorithms. We will also cover a variety of applications of probabilistic ideas and randomization in several areas of computer science.

Course Description

1) Introduction, review of discrete probability, and elementary examples including randomized algorithms for checking identities, matrix multiplication verification, minimum cut in graphs.2) Discrete Random Variables, Moments, Deviations and Tail Inequalities; applications, including the coupon collector problem.3) Chernoff bounds and applications: random sampling and estimation of discrete distributions. The birthday paradox and applications.4) The Probabilistic Method: random graphs and threshold phenomena. Max-cut approximation. Lovasz Local Lemma and application to boolean satisfiability.5) Random Walks and Markov Chains: hitting and cover times; stationary distributions, random walks on undirected graphs.6) The Monte Carlo Method; applications including sampling and approximate counting, the markov chain monte carlo method, the Metropolis algorithm.7) Coupling of Markov Chains, mixing time, and applications, including card shuffling and sampling of graph colourings and independent sets.

Assessment Information

Written Exam 80%, Coursework 20%, Practical Exam 0%

Additional Assessment Information

Exam 80%Coursework 20%You should expect to spend approximately 30 hours on the coursework for this course.

view the timetable and further details for this course