Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI

Binary Decision Diagram Technology (Wintersemester 2005/2006)

Tutoren: Prof. Dr. Christoph Meinel

Allgemeine Information

  • Semesterwochenstunden: 4
  • ECTS: 6
  • Benotet: Ja
  • Einschreibefrist: 01.11.2005
  • Lehrform:
  • Belegungsart: Wahlpflichtmodul


  • IT-Systems Engineering MA


This course covers both the theoretic aspect and the practical application of Binary decision Diagrams.

The course is divided into three parts:

  • In the first part, the basic theory of BDDs is developed. Algorithms for BDD manipulation and minimization based on variable ordering are discussed. Approximation of the worst-case run-time for all algorithms is given.
  • The second part of the course considers the basic data structures (directed acyclic graphs, look-up tables) and essential programming techniques (hashing, dynamic programming) used to represent and manipulate Binary Decision Diagrams. The implementation of a high performance BDD package in C/C++ is discussed, based on a case study of a state-of-the-art BDD package.
  • The third part of the course is devoted to application of binary and other DDs to problems encountered in logic synthesis, verification, and testing, image processing.


Prerequisites: Basic knowledge in computer science, programming in C, data structures and algorithms.


Course literature:

Lern- und Lehrformen

Instruction Method: 50% of a class period is allocated to lectures while the remaining time will be spent on tools tutorials and exercises. The course is limeted to 15 participants.


Grading Policy:  

  • Assignments      30 %   ( are due on the date assigned by the lecturer )
  • Project               30 %   ( is due on one week before the final exam )
  • Final exam         40 %   ( written )


Mo 15:15 - 16.45 HPI A-1.1    Di  13:30 - 15:00 HPI A-1.1