Data Structures and Algorithms

Preliminary Overview

• Graph algorithms: Shortest path, Maximum Flows, Bipartite matchings
• Generic optimization methods: Tabu search, simulated annealing, genetic algorihtms, linear programming, branch-and-bound, backtracking branch-and-cut, dynamic programming, approximation algorithms, approximation schemes
• Advanced Data Stuctures: Fibonacci heaps, pairing heaps, radix heaps, perfect hashing, randomized search trees, segment trees, interval trees
• Geometry: Convex hulls, Delaunay triangulation, Voronoi diagrams, line segment intersection.
• Strings: Pattern matching, suffix trees
• Analysis Techniques: Amortized analysis, ...
• Contest: Make LEDA look bad
• Term Project:

Prerequisites

• Basic Algorithms and Data Structures, e.g., from last year's course. The course notes below give the prerequisites for particular chapters.
• Programming Experience in C++, C, or Java and the ability to follow the description of algorithms in simple C++ or Java

Course Notes

• Graph Algorithms
• Basic Optimization (New: the entire thing)

• Introduction, The Shortest Path Problem, Generic Shortest Path Algorithm, Acyclic Graphs
• Bellman-Ford, Dijkstra, Prioriry Queue ADT, Refined Bellman-Ford, Worst Case Inputs for Bellman-Ford, All-Pairs Shortest Paths
• Implementations of the Priority Queue ADT: Radix Heaps, Binomial Queues, Fibonacci Heaps
• Maxflow, cuts and residual graphs, Max-Flow-Min-Cut theorem, Ford-Fulkerson algorithm, bipartite matching and theorem of Hall, Dinic's algorithm, generic preflow push, excess scaling preflow push, selection rules for preflow push, implementation of preflow push, heuristic improvments, experimental findings
• Basic Optimization: Abstract Problems versus Applications, Declarative Optimization, Linear Programming, Integer Linear Programming
• Dynamic Programming
• Greedy Algorithms
• Hill Climbing and Simulated Anneling
• More Local Search

• shortest_path_time.c

Challenges and Topics for Diplomarbeiten

• Verified Result Checking (Fopra oder Diplomarbeit)
• Scheduling Communication and Accesses to Disks, Fast Maximum Flow Algorithms, Cache Efficient Priority Queues... (Fopra oder Diplomarbeit)

Books and other Information

Exercises