| Sr. No, Date | Topic | Resource |
|---|---|---|
| 1: 22/07 | Administrative Details, Motivation | Slides | 2: 26/07 | Object Based Programming: C++ Classes | Slides, Ch 4.1,4.5, 4.8,4.9 | 3: 27/07 | Data Structures in Real Life, How to implement a search engine |
Slides | 4: 29/07 | Performance Analysis | Slides, Ch 2.2 | 5: 02/08 | Performance Analysis | Slides based on Ch. 2.3-2.6 |
| 6: 03/08 | Motivating Link Lists: implementing Dynamic Sets using arrays, problems: a) deletion, b) maintaining it in sorted fashion. | Slides |
| 7: 05/08 | Dynamic Memory Allocation: Pointers | Slides |
| 8: 09/08 | Link List Implementation using Pointers | Slides, Ch 3.3-3.5 |
| 9: 10/08 | Queue, Applications | Ch 4.6 |
| 10: 12/08 | Stack, Applications | Ch 4.2-4.4 |
| 11: 12/08 | Extra Tutorial: HW and Lab Solutions | |
| 12: 16/08 | Recursion: examples, Towers of Hanoi | Ch 5.1-5.3 |
| 13: 17/08 | Iterative solution to Hanoi, other examples of recursion | |
| 14: 19/08 | Queue implementation using Arrays | Slides |
| 15: 23/08 | Insertion Sort | Ch 6.1,6.3 |
| 16: 26/08 | Selection Sort | Ch 6.2 |
| 17: 30/08 | Selection Sort - Exact Analysis | |
| 18: 31/08 | Merge Sort | Ch 8.1-8.3,8.5-8.7 |
| 19: 02/09 | Quick Sort, Partitioning Algorithm | Ch 7.1, pages 12-15 of Sequencing Primitives Revisited for Dijkstra's Dutch National Flag Problem that introduced the 3-way, in-place partition |
| 20: 06/09 | Quick Sort: Avg Case Analysis, Optimizations | Ch 7.2,7.4-7.6 |
| 21: 07/09 | Quick Sort: Recursion Removal | Ch 7.3 |
| 22: 20/09 | Trees: Formal Definition and Properties | Ch 5.4-5.5 |
| 23: 21/09 | Trees: Traversal Algorithms | Ch 5.6-5.7 |
| 24: 23/09 | Priority Queue | Ch 9.1-9.3 |
| 25: 27/09 | Heapsort | Ch 9.4 |
| 26: 28/09 | Priority Queue Application: Discrete Event Simulation | |
| 27: 30/09 | Binary Search Trees: Insertion, Deletion, and Join | 12.5-12.7 |
| 28: 04/10 | BST: Rotation, Root Insertion, Randomized BST | 12.8-12.9, 13.1 |
| 29: 05/10 | 2-4 Trees | 13.3, Slides in Moodle |
| 30: 07/10 | Splay Trees | 13.2, the classical paper by Sleator and Tarjan. A demo can be found here. |
| 31: 11/10 | Skip Lists | 13.5 |
| 32: 12/10 | Hashing: Hash Table and Hash Function, Chaining | 14.1,14.2 |
| 33: 14/10 | Hashing: Linear Probing, Double Hashing | 14.3,14.4 |
| 34: 18/10 | Hashing: Double Hashing Analysis, Perspective | 14.4, 14.6 |
| 35: 19/10 | Tries, Ternary Search Trees | 15.4 |
| 36: 21/10 | Graph: Introduction | slides |
| 37: 24/10 | BFS, DFS | slides |
| 38: 25/10 | Dijkstra's Shortest Path Algorithm | slides |
| 39: 26/10 | Minimum Spanning Tree: Prim's and Kruskal's Algorithm | slides |
| 40: 28/10 | Union-Find Algorithm | Ch 1, slides |
| 41: 8/11 | Union-Find Algorithm | Ch 1, slides |
| 42: 9/11 | Shortest Path with negative edge weights | slides |
| 43:11/11 | Topological Ordering | slides |