| Basic techniques for randomized algorithms |
- applies the most important principles of algorithm design (Design and analysis of algorithms)
|
- describes basic examples of the main paradigms for randomized algorithms: Monte Carlo, Las Vegas, fingerprinting, load balancing, symmetry breaking
|
- applies the main paradigms to design randomized solutions to simple algorithmic problems
- analyses the performance of randomised algorithms based on models seen on the course
|
- solves difficult algoritmic problems with randomization
- uses a large variety of tools to analyse randomized algorithms
|
| Deviation bounds |
- basic properties of discrete random variables
|
- applies Markov's and Chebyshev's inequalities and Chernoff bounds in simple situations
|
- explain the use of deviation bounds in more complicated situations familiar from the course
- derives Chernoff bounds
|
- applies deviation bounds in deriving and analysing new non-trivial algorithms
|
| Probabilities and combinatorics |
- basic properties of discrete random variables
|
- applies the balls and urns model to simple random processes
- uses the Poisson approximation to analyse balls and urns models
- uses the probabilistic method for simple combinatorial existence proofs
|
- proves the basic properties of the Poisson approximation
- derandomises probabilistic existence proofs to obtain deterministic algorithms
- proves simple threshold properties in random graphs
|
- applies the balls and urns model to analyse complicated situations
|
| Markov chains |
|
- models random systems as Markov chains
- explains the basic concepts of Markov chains
- finds the stationary distribution of a simple Markov chain and uses it to analyse the behaviour of the system
|
- applies random walks in designing algorithms
- designs and analyses Markov chain Monte Carlo methods based on examples seen on the course
|
- uses Markov chain Monte Carlo in real-world applications
|
| Continuous random variables |
- basic properties of continuous random variables
|
- models random systems as Poisson processes and applies basic properties of Poisson processes to analyse them
- models random systems as continuous time Markov chains
|
- solves the stationary distribution of a simple continuous time Markov chain and uses it to analyse the system
|
- uses Poisson processes and Markov chains to analyse complicated continuous time systems
|
Printer-friendly version