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 |