Randomised Algorithms: 2008-2009
Lecturer | |
Class Tutor | |
Degrees | Schedule C1 — Computer Science Part C — 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.
Feedback
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.
Taking our courses
This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses
Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.