[SS] Data Structures, Algorithms and Applications in C++, Sartaj Sahni, 2nd Ed.
[RS] Algorithms in C++, Robert Sedgewick, 3rd Ed.
[FC] Data Abstraction and Problem Solving with C++, Frank M. Carrano, 5th Ed.
| Sr. No, Date | Topic | Resource |
|---|---|---|
| 1: 23/07 | Motivation: Data Structures in Real Life, How to implement a search engine |
Slides-Om |
| 2,3: 27,28/07 | Union-Find Algorithms | [RS].1, Slides-[RS] |
| 4: 30/07 | Complexity Analysis and Recurrence Relations | [RS].2, [SS].3, Slides-Om |
| 5: 03/08 | Motivating Link Lists: implementing Dynamic Sets using arrays, problems: a) deletion, b) maintaining it in sorted fashion. | |
| 6: 04/08 | Insertion Sort, Selction Sort. Applying Link Lists: Bucket Sort | [SS].6.1,6.5.1 |
| 7: 06/08 | Assignment 2 solution | |
| 8: 06/08 (evening) | Link List Implementation | Slides-[FC] |
| 9: 10/08 | Abstract Data Types | Slides-[FC] |
| 10: 11/08 | Link List Continued | Slides-[FC] |
| 13-19/08 | Swine Flu Break | |
| 11: 20/08 (morn + even) | Quiz, Prog. Assignment 4 Discussion | |
| 12: 24/08 | Writing Bug Free code, using a debugger | gdb |
| 13: 25/08 | Stack, Solving Algebraic Expressions | [SS].8.1, 8.2, 8.3, 8.5.2, 8.5.6 Historic Notes Dijkstra discusses this problem in 1962 , a html version of the same |
| 14: 27/08 | Implementation choices for Stack, Removing Recursion using Stack | From a text-book by Langsam |
| 15: 28/08 | Repeat Lecture on Removing Recursion using Stack | |
| 16: 31/08 | ADT Queue and its applications | [RS].8.7, [SS].9.1,9.2,9.5. Instead of [SS].9.5, various other applications discussed in class. |
| 17: 01/09 | Queue Implementation Issues, circular array based implementation | From Carrano |
| 18: 03/09 | Hashing: ADT, Applications, Implementation - Chaining | [SS] 10.5-10.6.5, [RS] 14.0 Our discussion follows [RS] |
| 19: 07/09 | Hash function for various data types: float, string. | [RS] 14.1-.2 |
| 20: 08/09 | Linear Probing: Motivation, Implementation, Properties | [RS] 14.3 |
| 21: 09/09 | Clustering. Double Hashing. Analysis. Random Probing. Real Life Issues. | [RS] 14.4-6. Note that this material is not covered in [SS] |
| 22: 22/09 | A simple sorting algorithm from basic specification and its analysis | |
| 23: 23/09 | QuickSort, Partition method from basic specification | [RS] 7.1; Check the pages 12-15 of Sequencing Primitives Revisited for Dijkstra's Dutch National Flag Problem that introduced the 3-way, in-place partition. |
| 24: 29/09 | QuickSort Analysis | [RS] 7.2, Average case intution based on CLR |
| 25: 30/09 | Trees, Basic Recursive Definition, Properties | [RS] 5.4, 5.5 |
| 26: 01/10 | Tree Traversal, Complete Binary Tree, Priority Queue ADT and Implementation, Heap and Array Based Implementation | [RS] 9.1-9.3,9.5 |
| 27: 05/10 | Optimizing N consecutive insertions in Heap | [RS] 9.4 |
| 28: 06/10 | Pointer Based Heap - various methods, removing complete binary tree condition | In Moodle: A formal description of Optimal Binary Tree and the insertion code for pointer based heap. |
| 29: 08/10 | Binary Search Tree: Definition, Insert, Search | [RS] 12.5, [SS] 14.1-14.3 |
| 30: 12/10 | Binary Search Tree: Analysis of Avergae Search Cost, Deletion, Merge | [RS] 12.6, 12.9, [SS] 14.3, Lecture Notes in Moodle |
| 31: 20/10 | Rotation and Height Balanced Binary Search Trees: Randomized BSTs and Treap | [RS] 13.1, not given in [SS], Slides based on Sedgewick in Moodle |
| 32: 22/10 | 2-3-4 Tree | [RS] 13.3, not given in [SS], we discussed bottom-up approach as per a book by Goodrich/Tamassia, as opposed to top-down approach given in Sedgewick. Slides by Goodrich/Tamassia in Moodle |
| 33: 26/10 | Red-Black Tree: Basic properties, insertion. Allows red link in 3-node to be either left or right child. | [RS] 13.4, [SS] 15.2, our discussion based on the book by Goodrich/Tamassia. Slides by Goodrich/Tamassia in Moodle. It will be hard to follow Red-Black Tree without understanding 2-3-4 Tree first. |
| 34: 27/10 | Search Structures for Strings: Tries, Ternary Search Trees | [RS] 15.2,15.4. Slides by Sedgewick in Moodle. |
| 35: 28/10 | KD-Tree: Search Structure for multi-dimensional data | Writeup by Sedgewick is part of assignment 10. |
| 36: 29/10 | Left Leaning Red-Black Tree: Red link in 3-node can be only left child. Split all 4 nodes. | Slides by Sedgewick in Moodle. |
| 37: 03/11 | Left Leaning Red-Black Tree: Do not split 4 nodes | |
| 38: 05/11 | Graphs: Basic Definitions and Properties | [SS] 16.1-16.3 |
| 39: 09/11 | Unweighted Graphs: Finding a path between given set of points/DFS | [SS] 16.8-16.9, our discussion was inspired by Kleinberg-Tardos's Algorithm's book |
| 40: 10/11 | Unweighted Graphs: Finding the shortest path between given set of points/BFS; properties of BFS/DFS tree | [SS] 16.8-16.9, our discussion was inspired by Kleinberg-Tardos's Algorithm's book |
| 41: 12/11 | Weighted Graphs: Shortest path - Dijkstra's Algorithm | [SS] 16.8-16.9, our discussion was inspired by Kleinberg-Tardos's Algorithm's book |
| 42: 12/11 | Generic Graph Traversal using various data-structures | Our discussion was inspired by Kleinberg-Tardos's Algorithm's book |
| 43: 12/11 | Discussion session on Minimal Spanning Tree, Topological Sorting, Bi-partite Graphs | [SS]16.9 for MST. Our MST discussion was inspired by Kleinberg/Tardos. Other topics from other places. |