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