Credits: 2-0-3-0 [9]
Who can take this course: Any UG student who has done ESO207 or CS345 and any PG student is eligible for doing this course. Instructor's consent will be needed for enrolling in this course. Moreover, while deciding enrolment, some filtering may be used based on the performance in the courses (Desirable: at least an A grade in ESO207 or at least a B grade in CS345).
Other Departments/IDPs which may be interested in the proposed course: Mathematics, Electrical Engineering.
Other faculty members interested in teaching the proposed course: Any faculty member from the area of theoretical computer science.
Proposing Instructor: Surender Baswana, Department of CSE
The data structures play a crucial role in solving various algorithmic problems. However, usually, the first course on data structures and algorithms fails to convey the power and elegance of the data structures. One feels that either the data structures are too elementary (e.g., stacks, queues) or they are too complex to be of any practical use (Fibonacci heaps). The aim of this course is to destroy this popular myth. For this objective, a student will be introduced to various well known data structures which are elegant, powerful, and sometimes just magical.
| S. No. | Broad Title | Topics | No. of Lectures |
|---|---|---|---|
| 1. | Overview and motivation of the course | Models of computation. Demonstrating the power of data structures through some simple but elegant data structures | 1 |
| 2. | Augmenting Red-Black trees with applications | Special union, Split, Findrank, and applications (i) dynamic sequences (ii) geometric data structures: orthogonal range searching, red-blue segments intersection. |
3 |
| 3. | Data Structures for Range Minima | Achieving O(log n) query time with O(n) space and achieving O(1) query time with O(n log n) space | 1 |
| 4. | Searching in multiple sorted arrays | Fractional Cascading with applications | 1 |
| 5. | Integer data structures | van Emde Boas queue, x-fast and y-fast trees. | 2 |
| 6. | Data structures for Static Trees | Level Ancestors, Lowest Common Ancestors, Range Minima. | 3 |
| 7. | Data structure for Dynamic Trees | Link-Cut tree, Euler-Tour Tree | 4 |
| 8. | Self organizing data structures | Self adjusting lists, An introduction to the Splay Trees | 4 |
| 9. | Data structure for union and find | Seidel-Sharir analysis for an ultra-fast data structure for union and find | 2 |
| 10. | Hashing beyond just a heuristic | Hashing with worst case O(1) query time and linear space | 2 |
| 11. | Miscellaneous Topics | Based on availability of time and interest of students, some topics from the following list will be covered (i) Approximate Distance Oracles (ii) Suffix trees (iii) Succinct data structures (iv) Persistent data structures (v) Kinetic data structures (vi) Heaps (vii) Bloom filters (viii) Lower bound on Data Structures |
4 |
None. However, the relevant research papers will be provided.