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
Disclaimer
All course information obtained from this visiting student course finder should be regarded as provisional. We cannot guarantee that places will be available for any particular course. For more information, please see the visiting student disclaimer: