Dynamic Algorithms (Q4) (5 ECTS)

Objectives of the course

The participants will after the course have insight into design and analysis of dynamic algorithms and practical experience with implementation of dynamic algorithms. The working method of the course will also train the participants to plan and complete projects, and to read and understand research papers.

Learning outcomes and competences

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

Course contents

In some applications, where we have to compute a function repeatedly, the input is changed only slightly between computations. This poses the challenge of recomputing the function without starting from scratch each time. In the course, we study concrete examples of dynamic algorithms and their analysis in a representative selection of application areas: Graph algorithms, string algorithms, geometric algorithms, algebraic algorithms. We also study techniques and tools used in the design and analysis of dynamic algorithms and data structures: The balanced binary tree technique, global rebuilding, lazy initialization, van Emde Boas tree, linking and cutting trees, Euler tour tree data structure, deterministic coin tossing.

Prerequisites

dADS1+2

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/DynAlg/

Provider

Department of Computer Science

Course enrolment

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

Courseparameters