Efficient Algorithms
(with an emphasis on graph algorithms)

Sommersemester 2005

Contents:
The course will focus on general algorithm design principles like divide-and-conquer and dynamic programming and on selected algorithms for graph problems like graph exploration, shortest path, connectivity, minimum spanning trees, matching, edge coloring, transitive closure and reduction, planarity testing, graph drawing, and transitive orientation.

Prerequisites:
Basic knowledge in algorithms and data structures and in asymptotic analysis using Big-Oh notation. Practical exercises will use C++ programming language and LEDA and BOOST software libraries.

Exercises:
homework exercises 1
homework exercises 2

Slides:
Analysis of Algorithms (from Algorithm Design)
Graphs (from Algorithm Design)
Comparability Graphs

Literature:
Thomas H. Cormen, Charles E. Leiserson, Ron Rivest, Clifford Stein
Introduction to Algorithms
MIT Press

Michael Goodrich, Roberto Tamassia
Algorithm Design
Wiley

Kurt Mehlhorn, Stefan Näher
LEDA: A Platform for Combinatorial and Geometric Computing
Cambridge University Press

Webmaster -

Efficient Algorithms (with an emphasis on graph algorithms)

Sommersemester 2005

Efficient Algorithms
(with an emphasis on graph algorithms)