Advanced Randomized Algorithms (Spring 2009, Q4)

Messages

• 10/3 2009: Webpage created.

Objectives

The participants will after the course know how to apply randomized techniques in the context of parallel algorithms, online algorithms, graph algorithms, and computational geometry.

Learning outcomes and competences

The participants must at the end of the course be able to:

• design and analyze randomized parallel algorithms, online algorithms, graph algorithms, computational geometry algorithms, and sampling based algorithms.

Contents

Randomized algorithms for the above mentioned topics. Details will appear in the course plan below.

Lecturers

Mohammad Ali Abam, Peyman Afshani, Deepak Ajwani, and Peter Hachenberger.

Time and Place

First lecture will be Tuesday April 14, 15.15, in Ada-018.

Course plan

Week	Date	Content	Literature	Lecturer
16	14/4	VC-dimension,   pages 11-14 of the book	The Discrepancy Method: Randomness and Complexity, B. Chazelle, Cambridge University Press, 2001 (available online) Approximation Algorithms in Geometry, Lecture Notes, Sariel Har-Peled	Peyman Afshani
17	21/4  14:00-15:00  at Turing-014	ε-net, ε-approximation,   page 171 of the book
	23/4  14:00-15:45  at Ada-018	ε-net, ε-approximation,   pages 177-178, 180-181 of the book; pages 72-73 of the lecture notes
18	28/4  13:00-14:00  at Shannon 157	weak ε-nets,   pages 187-189 of the book
	30/4  14:00-15:45  at Ada-018	PRAM- Introduction, Prefix sum, Maximum	Chapter 12: Parallel and Distributed Algorithms from Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995 PRAM Algorithms, Lecture notes, Satish Rao PRAM Algorithms, Lecture notes, Siddhartha Chatterjee and Jan Prins	Deepak Ajwani
19	5/5  13:00-14:00  at Shannon 157	PRAM - List Ranking, Integer Sorting
20	12/5  13:00-14:00  at Shannon 157	PRAM - General Sorting, Maximal Independent Set
	14/5  14:00-15:45  at Ada-018	Markov chains and random walks	Chapter 6: Parallel and Distributed Algorithms from Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995 Chapter 1: Markov Chains by James Norris The PageRank Citation Ranking: Bringing Order to the Web by L. Page, S. Brin, R. Motwani, and T. Winograd	Peter Hachenberger
21	19/5  13:00-14:00  at Shannon 157
22	26/5  13:00-14:00  at Shannon 157
	28/5  14:00-15:45  at Ada-018	Probabalistic Method	The Probabalistic Method, J. Matousek	Mohammad Abam
23	2/6  13:00-14:00  at Shannon 157	Randomized Divide-and-Conquer Algorithms	Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, editors, CRC Press (Chapter 40)
	4/6  14:00-15:45  at Ada-018	Randomized Incremental Algorithms

Handin exercises

• Exercise I
• Exercise II
• Exercise III
• Exercise IV
• Exercise V
• Exercise VI
• Exercise VII
• Exercise VIII
• Exercise IX

Literature

Literature for the course will be chapters from the below book and additional handouts.

(larger picture)

Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995. 492 pages. ISBN: 0-521-47465-5.

Quarter

4th (Spring 2009).

Credits

5 ETCS points.

Prerequisites

Randomized Algorithms.

Course language

English.

Compulsory programme

Homework handin.

Evaluation

Based on mandatory hand-in's and attendance, pass/fail.