Faculty of Science

Objectives

To provide an advanced treatment of data structures and their effective use in a variety of computer applications. It emphasizes data structure concepts, and the importance of data structure choice and implementation.

Contents

Heaps (mention binomial and Fibonacci heaps); binary search trees; red-black trees, B-trees and their variants; tree balancing algorithms. Hash tables (universal, perfect, dynamic hashing); structure for disjoint sets; table structures. Advanced data structure (DS) concepts usually based on above data structures: Persistence; Randomisation (treaps, random search trees); Self-adjusting (e.g., splay trees, queaps); retroactive; fractional cascading (e.g., skip lists, iterated search, segment trees); succinct DS (space optimising); string DS (tries, suffix trees, etc.); cache-oblivious DS; integer DS (e.g., van Emde Boaz). Applications of data structures; application domains/algorithms such as computational geometry, range queries, large collections, string matching, dynamic programming algorithms.