SUBJECT
Title
Design, analysis and implementation of algorithms and data structures II
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
- Data structures for the UNION-FIND problem. Pairing and radix heaps. Balanced and self-adjusting search trees.
- Hashing, different types, analysis. Dynamic trees and their applications.
- Data structures used in geometric algorithms: hierarchical search trees, interval trees, segment trees and priority search trees.
Readings
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, McGraw-Hill, 2002.
- A. Schrijver: Combinatorial Optimization, Springer-Verlag, 2002.
- Robert Endre Tarjan: Data Structures and Network Algorithms , Society for Industrial and Applied Mathematics, 1983.
- Berg-Kreveld-Overmars-Schwarzkopf: Computational Geometry: Algorithms and Applications , Springer-Verlag, 1997.