Classes: Mondays and Wednesdays 09:35-11:05
References:
Data Structures and Algorithm Analysis in C++: Mark Allen Weiss [MAW]
(This contains almost every thing that we intend to cover in this course, but the specific C++ constructs will not be used by us)
Notes on Data Structures: David Mount [DM]
Introduction to Algorithms: Cormen, Leiserson, Rivest, Stein (CLRS)
Data Structures and Algorithms: Aho, Hopcroft and Ullman [AHU]
Algorithms: Dasgupta, Papadimitriou, Vazirani [DPV]
Grading: Midterm 30%, Assignments/Class tests 20%, Final 50%
Class 01 (Aug 03): Introduction to Algorithms: Recursion, Finding the n-th Fibonacci number [Read MAW 1.3, DPV 0.1, 0.2]
Class 02 (Aug 08): Introduction to Algorithms: Model of Computation, RAM model, Running Time, Asymptotic Notations, Insertion Sort [Read CLRS 2.1, 2.2, 3.1]
Class 03 (Aug 10): Basic Algorithms: Algorithms to Add, Subtract, Multiply and Divide. Analyzing running times [Read DPV 1.1 and parts of 1.2]
Class 04 (Aug 22): Basic Algorithms: Merge Sort, Karatsuba Multiplication, Divide and Conquer Recurrences, Masters Theorem [Read DPV 2.1, 2.2, 2.3]
Class 05 (Aug 24): Abstract data types. The List ADT. Implementing Lists with arrays [read CLRS 10.1, 10.2, MAW 3.1,3.2]
Class 06 (Aug 25): Linked lists. Implementing lists by linked lists [Read Notes]
Class 07 (Aug 29): Stacks and Queues: Array and Linked list Implementations [read CLRS 10.1, 10.2, MAW 3.6, 3.7]
Class 08 (Aug 31): Application of Stacks: Infix and Postfix expressions [Read MAW 3.6.3]
Class 09 (Sep 05): Dynamic Arrays, Amortized Analysis: Aggregate Analysis, Accounting Method [Read CLRS 17]
Class 10 (Sep 07): Amortized Analysis: Potential function method. [Read CLRS 17]
Class 11 (Sep 09): Amortized Analysis: Binary Counter, Dynamic arrays. Introduction to Priority Queues [Read CLRS 17]
Class 12 (Sep 12): Heap as a priority queue [Read CLRS 6]
Class 13 (Sep 14): Skiplist [Read Class notes]
Class 14 (Sep 15): Finishing Skiplist. Review [Read Class notes]
Class 15 (Sep 28): Power of Randomness. Introducing Hash tables [Read DPV 1.5]
Class 16 (Oct 17): Direct Addressing, Chaining, Universal hash functions [Read CLRS 11, DPV 1.5]
Class 17 (Oct 19): Expected running time for hash table operations, perfect hashing [Read CLRS 11]
Class 18 (Oct 20): Introduction to Binary Search Trees [ Read CLRS 12]
Class 19 (Oct 25): Insertion and Deletion in BST, Introduction to AVL Trees [Read CLRS 12, MAW 4]
Class 20 (Oct 28): AVL Trees: Rotations [Read MAW 4]
Class 21(Oct 31): AVL Trees: Routines for Insertion and Delete [Read MAW 4]
Class 22(Nov 02): Splay Trees [MAW 4.5]
Class 23 (Nov 09): Splay Trees: Analysis [MAW 11.5]
Class 24 (Nov 11): Data Structures for strings Strings: Tries
Class 25(Nov 16): Compressed Tries, Suffix trees, Suffix arrays [read 7.1, 7.3, 7.4, 7.5 from here]
Class 26(Nov 17): Data Structures for external memory: B-Trees [read Chapter 14 from Open Data Structures]