[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. |