Summer 2003: Algorithm Library Design

Algorithm Library Design: Syllabus

Course Goal

To learn how to implement software libraries, such as STL, CGAL, LEDA, ..., that have a focus on algorithms and data structures. To learn advanced programming techniques in C++, such as templates, generic programming, object-oriented design, design patterns, and large-scale C++ software design.

Prerequisites

Programming knowledge in C. Knowledge of an OO language such as C++, Java, Eiffel or Smalltalk is a plus but not a must.

Course Home Page

http://www.mpi-sb.mpg.de/~kettner/courses/lib_design_03/

Introduction (1 classes)

General organization and overview. Student projects. Design goals. Multiparadigm design in a nutshell and a design process. Feature diagrams. Domain dictionary and domain analysis. Commonality and variability analysis. Brainstorming Session.

The C++ Language (3 classes)

C++ constructors, destructor and assignment. Derivation. C++ virtual member functions and templates. Templates made C++ Turing equivalent at compile time, e.g., C++ can compute prime numbers at compile time. Keywords typename and explicit. Implicit instantiation and its consequences for member functions. Member templates. Static members.

STL and Generic Programming (3 classes)

STL (Standard Template Library, part of the C++ standard library). Iterators, generic functions, iterator adaptors, function objects and iterator traits. Implementation of back_inserter, not1, and bind2nd.

Intermediate Project Presentation (1 class)

Building and Documenting a Library (1 class)

Example files and the use of doxygen.

Design Strategies (3 classes)

Generative programming. Policy-based design.

Advanced C++ Programming (3 classes)

Const correctness. Library initialization. Cyclic type dependencies with templates, for example, in implementing graph data strutures with nodes and edges: the Barton-Nackman trick and other twisted template code. Proxy and smart pointers. How to access data referred to by iterators (e.g., data accessors). Double dispatch problem. How to associate (additional) data to items in a data structure. Property maps (Boost Graph library). Exception mechanism and exception safety.

Computational Geometry Algorithms Library (CGAL) (3 classes)

Overview and introduction to programming in CGAL. Exact computation: number types, Cartesian and homogeneous representation. Degeneracy handling: explicit special case handling. Intersection uses CGAL::Object, a polymorphic type, as return type. CGAL::Object is a local design solution without introducing a common base class for all objects. Geometric traits class to separate algorithms and data structures from the underlying geometric representation. An affine-geometry kernel: Points, vectors, covectors, and hyperplanes. Coordinate-free geometry and frames.

Design Patterns (2 classes)

Introduction to patterns. Examples: Abstract Factory, Singleton, Adaptor, Visitor pattern, and the polymorphic type in CGAL.

Template Metaprograms (3 classes)

Expression templates, expression templates for vector arithmetic, and template metaprograms as used in Blitz++. Metaprograms assuming type reflection in C++. boost::type_traits (currently reviewed by the C++ std commitee). Type lists. Higher-order functors. Concept checking.

Large-Scale C++ Software Design (1 classes)

Motivation, coding rules, component definition, physical hierarchy, levelization, insulation.

Final Project Presentation (1 class)

Lutz Kettner (<surname>@mpi-inf.mpg.de). Last modified on Tuesday, 17-Jan-2006 17:53:40 MET.