Dynamic Algorithms

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:

distinguish and explain basic concepts related to dynamic algorithms.
describe and analyze known dynamic algorithms within a representative selection of application areas.
apply and compare known techniques for design and analysis of dynamic algorithms.
implement simple dynamic algorithms.
predict and analyze the efficiency of proposed dynamic algorithms.
perspectivate the use of dynamic algorithms as modules within more complex algorithms.

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

dynamicF09