Randomised Algorithms: 2008-2009
Information
|
Lecturer |
|
|
Class Tutor |
|
|
Degrees |
Schedule C1 — Honour School of Computer Science Part C — Honour School of Mathematics and Computer Science |
|
Term |
Michaelmas Term 2008 (20 lectures) |
Overview
Many computationally 'difficult' problems in computer science can be solved efficiently using randomised algorithms. Such algorithms typically guarantee a correct answer or result only with high probability, which is however often adequate in practice. This course covers some of the main paradigms in analysis of randomised algorithms, enabling one to design, and reason about, such algorithms in a rigorous and precise way.Required background: basic grounding in (i) probability theory [at the level of Section 2.2 of the course text], (ii) discrete mathematics and combinatorics, (iii) algorithms and/or complexity, (iv) calculus of one and several variables, (v) linear algebra. Diligent students lacking some of the required background but willing to acquaint themselves with the necessary material are encouraged to contact the lecturer to discuss their situation prior to registering for this course.
Learning outcomes
At the end of the course students are expected to:
- Understand some of the main paradigms used in the analysis of randomised algorithms, such as foiling an adversary, abundance of witnesses, fingerprinting, amplification, and random sampling.
- Be able to design randomised algorithms to solve various problems, and to reason rigorously about the correctness and complexity of such algorithms.
The information on this course is subject to possible minor updates.
Synopsis
The material will be mostly drawn from the required text 'Design and Analysis of Randomized Algorithms', by Hromkovic. It is expected that the following will be covered:
- Fundamentals (including models and classification of randomised algorithms, overview of main paradigms)
- Foiling an Adversary (e.g. randomised online algorithms)
- Fingerprinting (e.g. substring problem, matrix multiplication, equivalence of two polynomials)
- Amplification and Random Sampling
- Abundance of Witnesses (e.g. primality testing, generation of random primes)
- Optimisation and Random Rounding (e.g. linear programming, MAX-SAT)
Syllabus
The material will be mostly drawn from the required text 'Design and Analysis of Randomized Algorithms', by Hromkovic. It is expected that the following will be covered:
- Fundamentals (including models and classification of randomised algorithms, overview of main paradigms)
- Foiling an Adversary (e.g. randomised online algorithms)
- Fingerprinting (e.g. substring problem, matrix multiplication, equivalence of two polynomials)
- Amplification and Random Sampling
- Abundance of Witnesses (e.g. primality testing, generation of random primes)
- Optimisation and Random Rounding (e.g. linear programming, MAX-SAT)
Reading list
Required text: Design and Analysis of Randomized Algorithms, by Juraj Hromkovic, Springer.
Recommended text: Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press.