Course objective: Introduce students to a wide variety of data structures, mechanisms of analysis, implementation, along with when and how to use them. Students will:
1. Understand and implement the wide spectrum of available data structures and how they influence algorithm design to achieve efficiency of space and time complexity.
2. Design and analyze out-of-the-box data structures for new scenarios that regularly arise in practice and require understanding of basic data types and their internal representation models like RAM and pointers.
3. Be able to clearly understand and distinguish between static and dynamic versions where there are trade-offs between space and time complexity.
4. Implement and analyze the real-world performance of these data structures.
Pre-requisite: Discrete Mathematics, Introduction to Computer Science
Coverage: Basic data structures (linear lists, arrays, stacks, queues) and analysis, trees, heaps, hash-tables and related randomized constructions like universal hash functions, skiplists, self-organizing lists, graphs, strings and tries, integers, geometric data-structures like k − d trees, segment trees, range trees; The significance of abstract and primitive data types; some background on word RAM vs pointer machines.
Application to sorting and searching algorithms whose performance depend on the data structures taught in class as well as some elementary graph algorithms like DFS, BFS and MST. Some exposure
to notions like amortization, deferred data-structuring and filtering search using suitable examples.
References: CLRS will be followed primarily for the course.
Additional reference books include Goodrich and Tamassia (Algorithm Design and Applications), Aho and Ullman (Data Structures and Algorithms), and Aaron M. Tenenbaum (Data Structures using C)
