*** Remember signing up for examination: dansk, English (February 1-15) ***
Advanced course at the Department of Computer Science, University of Aarhus in the 3rd quarter, Spring 2006.
Usually each two-hour class will start with a lecture and end with a problem session related to the lectures of the previous week.
The course is evaluated by a grade from the 13-scale based on a project and a multiple choice test.
| Feb. 1 | Lecture R1 | Introduction to randomized algorithms Randomization on inputs versus algorithms. Analysis by linearity of expectation and indicator variables. Las Vegas and Monte Carlo algorithms. MR 1-1.2 |
| Feb. 3 | Lecture R2 | Introduction to randomized algorithms (cont.) Another example of a Las Vegas algorithm and analysis by linearity of expectation. Proof of existence by the probabilistic method. A Las Vegas algorithm that beats any deterministic strategy. The complexity classes RP, BPP. MR 1.3, 1.5, 2.1 |
Problems for R1,R2: MR 1.1, 1.2, 1.4, 1.8 |
Feb. 8 | Lecture R3 | Randomized algorithms: Proving lower bounds von Neumann's minimax principle Yao's techniques for proving lower bounds Average case time usage for best deterministic algorithm relative to a known worst case input distribution equals expected time usage of best randomized algorithm on worst case input MR 2.2 |
|
Feb. 10 | Lecture R4 | Derandomization Trading randomness for nonuniformity. Markov's and Chebyshev' inequalities. Trading time for random bits. MR 2.3, 3.2, 3.4 |
Problems for R3,R4: MR 2.3, 2.7, 2.12 |
Feb. 15 | Lecture R5 | Chernoff bounds and randomized rounding Chernoff Bound: The sum of independent indicator variables is distributed closely around the expectation. Randomised rounding: Good approximate solutions to hard combinatorial problems. MR 4.1, 4.3 |
|
Feb. 17 | Lecture R6 | Chernoff bounds (cont.) Application to analysis of a routing algorithm. MR 4.2 |
Problems for R5,R6: MR 4.12, 4.13, 4.9 |
Feb. 22 | Lecture R7 | Algebraic techniques in randomization Fingerprinting for result checking. Schwarz-Zippel theorem. Application to perfect matching. MR 7-7.3 |
|
Feb. 24 | Lecture R8 | Algebraic techniques (cont.) Distributed equality test. (On-line) pattern matching. MR 7.4-7.6 |
Problems for R7,R8: MR 7.2, 7.8, 7.10, 7.12 |
Mar. 1 | Lecture R9 | Dictionaries Universal hashing and dynamic dictionaries. 2-level hashing and static dictionaries. MR 8.4-8.5 |
|
Mar. 3 | Lecture R10 | Dictionaries (cont.) Random Treaps MR 8.2 |
|
Mar. 8 | Lecture R11 | Competitive analysis of on-line algorithms Competitiveness: Comparison of on-line solution to best off-line solution. Paging algorithms: deterministic and randomised solutions. MR 13-13.3 |
|
Mar. 10 | Lecture R12 | Competitive analysis of on-line algorithms Paging algorithms: Lower bounds on competitiveness using Yao's technique. MR 13.3 |
Problems for R11,R12: MR 13.6, 13.10, 13.12 |
Mar. 15 | Lecture R13 | Primality test (if time permits) Randomised primality test. Generation of random primes. MR 14.6 |
Problems for R13: MR 14.12 1,2 |
Mar. 17 | Last session Multiple Choice Test. Course evaluation. |
|