| Fürstenallee F1.110
From most of the courses or textbooks on data structures and algorithms, unfortunately, one gets the following picture/impression about the data structures.
- The role of data structures is confined only to searching and sorting.
- Either the data structures are trivial (stacks, queues, Binary heaps, Red-Black trees), or they are too complex and impractical (Fibonacci Heaps).
- Most of the data structures lack the depth, richness, and elegance compared to the algorithms (e.g. Max-Flow).
The above picture/impression is totally wrong. Indeed, there are many simple and elegant data structures for various fundamental graph problems. These data structures achieve amazing, rather unbelievable, time complexities. In this talk, we shall discuss a few of such data structures.
Important note for this talk:
- The talk will be self contained. It will be followed by everyone who has done a course on data structures. However, the contents of the talk will be quite advanced.
- If you feel that majority of the data structures lack any elegance or depth, you must attend the talk.
- If you already know about dynamic trees (s-t tree and Euler Tour tree), you may skip this talk.
- The talk is the first talk in the series of talk on dynamic algorithms. This talk will cover the fundamental data structures that helped in designing efficient dynamic algorithms.