Preface and Notation

As html is not suited for mathematical formulas, some additional notation is used (as used in the typographical package Latex). a_i denotes a with subscript i. a^i denotes a to the power i. <= and >= are used as in most computer languages. Curly brackets, "{" and "}", are use to group things. sum_{i = 0}^j denotes the sum for i running from 0 to j. The same may also be written sum_{0 <= i <= j}. ~= stands for "approximately equal" and ~ for "proportional to". Greek letters are written out. For logical expressions we either use the notation from C or the operators are written out in text. So, "a && !b" is the same as "a and not b". sqrt stands for the square root function and log without specifying the base number for the logarithm to basis 2. There are a few more notations, but they should be understood easily. New notions are printed bold there where they are defined. Inside the chapters particularly important ideas and short key notes are highlighted without introductory text. There are many pictures. These are intended to be self-explanatory. Typically they are placed just after the text fragment to which they belong, generally there is no direct reference to them in the text.

There are very few references to the literature. Clearly most of the presented material is not new. A large part is even common knowledge. Next to several other lecture notes, the following book has been used as a source:

• Data Structures and Algorithm Analysis, Weiss, Addison Wesley, 1999.

Notice: the following text may be overcomplete. At the examination it is expected that the students only know all that has been presented during the lectures.

Table of Contents

• Chapter 1: Introduction
  • Covered Material
  • Mathematical Background
  • Asymptotical Notation
  • Computer Cost Model
  • Basic Algorithms
  • Exercises
• Chapter 2: Structured Programming: C
  • Primitive Data Types
  • Structured Data Types
  • Basic Instructions
  • Procedures
  • Exercises
• Chapter 3: Object Oriented Programming: Java
  • Introduction
  • Classes, Objects and Methods
  • Inheritance, Polymorfism and Encapsulation
  • Further Important Aspects
  • Summary
  • Further Code Examples
  • Exercises
• Chapter 4: Simple Data Types
  • Abstract Data Types
  • Lists
  • Stacks
  • Queues
  • Exercises
• Chapter 5: Dictionaries
  • Trees
  • Search Tree ADT
  • AVL Trees
  • 2-3 Trees
  • Other Operations
  • Exercises
• Chapter 6: Hashing
  • Context
  • Direct Addressing
  • Virtual Initialization
  • Hashing Idea
  • Chaining
  • Choice of Hash Function
  • Open Adressing
  • Rehashing
  • Exercises
• Chapter 7: Union-Find
  • Definition
  • Array-Based Implementation
  • Tree-Based Implementation
  • Analysis
  • Exercises
• Chapter 8: Sorting
  • Introduction
  • Bubble Sort and Variants
  • Merge Sort
  • Quick Sort
  • Lower Bound
  • Bucket Sort and Variants
  • Exercises
• Chapter 9: Priority Queues
  • Definition
  • Basic Realizations
  • Heaps
  • Binomial Forests
  • Applications and Extensions
  • Exercises
• Chapter 10: Graph Algorithms
  • Definitions
  • Representations
  • Graph Traversal
  • Edge Classification
  • Connected Components
  • Topological Sorting
  • Shortest Paths
  • Exercises