This course teaches competences in algorithmic thinking with a special focus on correctness, runtime analysis and design of algorithms as well as application of data structures. Participants learn about important data structures and algorithms and how to determine their runtime behavior and storage space requirements. Additionally this course provides foundations for core database algorithms (e.g., indexing structures).

**Course content:** Complexity of Algorithms, Sorting Methods, Graph
Algorithms, General Trees and Binary Trees, Binary Search Trees, Multiway
Trees, B-Tres and variants, Digital Search Trees, Hashing Methods (internal,
external, expandible), Graphical Data Structures, Special Topics (Bitmap
Index, Indexing Structures for "broadcast data", etc.).

## News

Currently not offered by DVS. Please consult TUCaN for the current offering.

Old material: The slides listed here refer to the lecture as given in **summer term 2009**!

## Table of Contents

## Slides

Lecture Topic | Slides | |
---|---|---|

1 | Introduction | Slides (pdf, 0.4MB) |

2 | Overview: Problem Solving | Slides (pdf, 0.5MB) |

3 | Analysis | Slides (pdf, 0.8MB) |

4 | Graph Definitions | Slides (pdf, 0.9MB) |

5 | Graph Algorithms | Slides (pdf, 2.1MB) |

6 | Graph Representations | Slides (pdf, 0.47MB) |

7 | Tree: Defs and Concepts | Slides (pdf, 0.36MB) |

8 | Binary Trees | Slides (pdf, 0.77MB) |

9 | Binary Search Trees | Slides (pdf, 0.77MB) |

10 | Multipath Trees | Slides (pdf, 1.4MB) |

11 | Sorting | Slides (pdf, 1.2MB) |

12 | Hashing | Slides (pdf, 1.5MB) |

13 | Geometric Algorithms | Slides (pdf, 0.8MB) |

## Exercises

Exercise | Exercise Sheet | Solutions Group Tasks | Solutions Homework | |
---|---|---|---|---|

1 | Giggle | Assignments | Group Tasks | Homework |

2 | Simiantec | Assignments | Group Tasks | Homework |

3 | Coloring | Assignments | Group Tasks | Homework |

4 | mq306 | Assignments | Group Tasks | Homework |

5 | Feldfrau | Assignments | Group Tasks | Homework |

6 | e-minus | Assignments | Group Tasks | Homework |

7 | Trees | Assignments | Group Tasks | Homework |

8 | Multiway Trees | Assignments | Group Tasks | Homework |

9 | Deutsche Tekeloom | Assignments | Group Tasks | Homework |

10 | Stooges | Assignments | Group Tasks | Homework |

11 | Heaps / Hash | Assignments | Group Tasks | Homework |

12 | Hashing | Assignments | Group Tasks | Homework |

13 | Geometric | Assignments | Group Tasks | Homework |

## Literature

- Thomas Cormen et al. 2010.

Introduction to Algorithms, 2nd Edition

ISBN 0-262-03293-7.

Relevant chapters: 1-4, 6, 7, 10-13, 16.3, 18, 22-26, Appendix A + B

### Additional Papers

Additionally this course refers to the following scientific papers:

- Jagan Sankaranarayanam, Hanan Samet. Distance Oracles for Spatial Networks. ICDE 2009, Shanghai, April 2009
- Hanan Samet, Jagan Sankaranarayanan, Houman Alborzi. Scalable Network Distance Browsing in Spatial Databases. SIGMOD 2008, Vancouver June 2008
- Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi. Tree Indexing on Flash Disks. ICDE 2009, March 29 - April 2, 2009, Shanghai, China
- Devesh Agrawal, Deepak Ganesan, Ramesh Sitaraman, Yanlei Diao, and Shashi Singh. Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices. VLDB 09, August 24-28, 2009, Lyon, France