IIT Gandhinagar · ES242
This archived edition introduces data structures through the operations they support, then develops graph representations and traversal, searching, sorting, heaps and search trees.
Published lecture schedule
| Date | Topic |
|---|---|
| 02 Aug, 2022 | 1. Introduction to Data Structures Data Structures - philosophy and examples • Representing games |
| 03 Aug, 2022 | 2. Introduction to Data Structures Representing Sequential Data • Arrays • Lists |
| 09 Aug, 2022 | Institute Holiday |
| 16 Aug, 2022 | 3. Representing Graphs Adjacency Lists • Adjacency Matrices • Edge Lists |
| 17 Aug, 2022 | 4. Representing Graphs (contd.) Adjacency Lists • Adjacency Matrices • Edge Lists |
| 23 Aug, 2022 | 5. Dequeues Introducing the cardstack data structure • The Gilbreath Shuffle |
| 24 Aug, 2022 | 6. Dequeues Queues and Stacks as special cases of Dequeues |
| 30 Aug, 2022 | 7. Euler Tours Euler Tour Demonstration • Card trick • de Bruijn sequences • Constructing de Bruijn sequences using Euler Tours |
| 31 Aug, 2022 | 8. Euler Tours Computing Euler Tours • Hierholzer's algorithm |
| 06 Sep, 2022 | 9. Stable Marriages The Stable Marriage Problem • Gale-Shapley Algorithm |
| 07 Sep, 2022 | 10. Stable Marriages Proof of Termination • Bounding the number of proposals • Proving the stability of the output |
| 13 Sep, 2022 | 11. Recap Lecture Review of arrays, linked lists, stacks, queues, and graphs |
| 20 Sep, 2022 | 12. Navigating Graphs An introduction to navigating graphs |
| 21 Sep, 2022 | 13. Navigating Graphs (BFS) Breadth-First Search • Correctness • Analysis of Running Time |
| 11 Oct, 2022 | 14. Navigating Graphs (DFS) Depth-First Search • Pre-Post Intervals |
| 12 Oct, 2022 | 15. Navigating Graphs (DFS) Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges |
| 18 Oct, 2022 | 16. DFS Applications Topological Sort (Algorithm) |
| 19 Oct, 2022 | 17. DFS Applications Postorder • Preorder • Topological Sort (Analysis) |
| 25 Oct, 2022 | 18. Shortest Paths A teaser the challenges in extending BFS to weighted graphs • Pseudopolynomial running time |
| 26 Oct, 2022 | 19. Heaps Selection Sort • Supporting only Insert and FindMin • The challenge of ExtractMin |
| 01 Nov, 2022 | 20. Heaps The Heap Property • Insert • FindMin • ExtractMin |
| 02 Nov, 2022 | 21. Heaps Representing Heaps with Arrays |
| 08 Nov, 2022 | Institute Holiday |
| 15 Nov, 2022 | 22. Heaps Revisited Analysis • Heapify is Linear Time |
| 16 Nov, 2022 | 23. Balanced Binary Search Trees (2,3)-Trees • Insertion • Deletion |
| 22 Nov, 2022 | 24. Balanced Binary Search Trees (2,3)-Trees Height Analysis |
| 23 Nov, 2022 | 25. Recap Review of BFS, DFS, Heaps, and Balanced BSTs |