CS 213/293: Data Structures and Algorithms + Lab (Autumn 2009)

Schedule: Lecture: Slot 2 in SIC 301 Kresit, Lab: Fri 2-5 in OSL
Instructor: Om Damani Office hours: M,Thu 5-6
TA list: cs213-tas TA office hours M,Thu 6-7 (by appointment only in NSL)
Moodle : Slides, Assignments, Solution, Newsgroup etc.

Credit Eligibility: The course is open only to those students who are required to take this course.
Audit Requirements
: You have to do at least 80% of the programming assignments. There will be one assignment per week.

Text Books

Following text-books are available in Indian edition. You are strongly urged to buy both books and are required to buy at least one of the books.

[SS] Data Structures, Algorithms and Applications in C++, Sartaj Sahni, 2nd Ed.
[RS] Algorithms in C++, Robert Sedgewick, 3rd Ed.

Supplementary books

Following book is not available in Indian edition. The instructor will be providing slides for some topics from this book:

[FC] Data Abstraction and Problem Solving with C++, Frank M. Carrano, 5th Ed.

Suggested Readings

Unix Programming Environment by Brian W. Kernighan, Rob Pike.

Lectures

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.