Randomized Algorithms (Q3) (5 ECTS)

Objectives of the course

The participants will after the course have insight into use of randomization for design and analysis of algorithms and practical experience with implementation of randomized algorithms. The working method of the course will also train the participants to plan and complete projects.

Learning outcomes and competences

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

• distinguish and explain basic concepts related to randomized algorithms and analysis of randomized algorithms.
• describe and analyze known randomized algorithms within a representative selection of algorithmic models and application areas.
• apply basic tools from probability theory and probabilistic analysis for design and analysis of algorithms and data structures.
• implement randomized algorithms on standard hardware (without access to truly random bits).
• predict and analyze the usefulness of a proposed application of randomization in the solution of a concrete problem.
• perspectivate the use of true randomness and pseudo randomness for solving algorithmic problems.

Course contents

There are many problems that can be solved more efficiently and by a simpler algorithm, when we have free access to a source of random bits, compared to when we have no such access. In the course, we study concrete examples of randomized algorithms and their analysis in a representative selection of models and application areas taken from: Algorithmic models where randomization is / may be used: Monte Carlo and Las Vegas algorithms, on-line algorithms and competitive analysis, data structures, distributed algorithms, parallel algorithms, approximation algorithms. Application areas: Graph algorithms, geometric algorithms, algebraic algorithms, number theoretic algorithms, combinatorial optimization, cryptography. We also study basic tools from probability theory and probabilistic analysis: Sums of indicator variables; Game theoretic techniques and Yao's lower bound technique; Tail inequalities in particular Chernoff bounds.

Prerequisites

dADS1+2, Matematical Modelling 1

Name of lecturer

Gudmund Frandsen

Type of course / teaching methods

Lectures (2+2h/week)

Literature

To be announced

Course homepage

http://www.daimi.au.dk/~gudmund/RanAlg/

Provider

Department of Computer Science

Course enrolment

http://www.brics.dk/~mis/enrollment.html

Courseparameters

• Level of course: Optional advanced course
• Semester/quarter: Q3 in 2007/2008
• Hours per week: 4
• Assessment methods: Project and multiple choice
  7-scale
• Language of instruction: Danish or English
• Capacity limits: