*** Remember signing up for examination (before February 15th) ***
Advanced course at the Department of Computer Science, University of Aarhus in the 3rd quarter, Spring 2004.
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 your response to 2 project assignments. You will have approximately 3 weeks to do each assignment. Handwritten responses are not acceptable. You should use LaTeX or similar.
| Jan. 26 | 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, 10.2 |
| Jan. 29 | 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. 2 | 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. 5 | 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. 9 | 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. 12 | 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. 16 | Lecture R7 | Algebraic techniques in randomization Fingerprinting for result checking. Schwarz-Zippel theorem. Application to perfect matching. MR 7-7.3 |
|
Feb. 19 | 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 |
Feb. 23 | Lecture R9 | Dictionaries Universal hashing and dynamic dictionaries. 2-level hashing and static dictionaries. MR 8.4-8.5 |
Problems for R9: MR 8.22 |
Feb. 26 | Lecture R10 | 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 |
Problems for R10: MR 13.6 |
Mar. 1 | Lecture R11 | Competitive analysis of on-line algorithms Paging algorithms: Lower bounds on competitiveness using Yao's technique. MR 13.3 |
Problems for R11: MR 13.10, 13.12 |
Mar. 4 | Lecture R12 | Primality test Randomised primality test. Generation of random primes. MR 14.6 |
Problems for R12: MR 14.12 1,2 |
Mar. 8 | Lecture R13 | Data Structures Random Treaps MR 8.2 |
|