Classes: Mondays and Wednesdays 09:30-11:15
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)
Open Data Structures: Pat Morin [PM]
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 (Jul 31) : Introduction to Algorithms: Recursion, Finding the n-th Fibonacci number [Read MAW 1.3, DPV 0.1, 0.2]
Class 02 (Aug 02): 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 07): Basic Algorithms: Addition, Multiplication, Division, Modular Arithmetic, Exponentiation, GCD, Extended Euclid, Primality Testing [ Read DPV]
Class 04 (Aug 09): Basic Algorithms: Karatsuba Multiplication, Merge Sort, Divide and Conquer Recurrences [Read DPV 2.1, 2.2, 2.3 ]
Class 05 (Aug 14): Abstract Data Types, List ADT, Stack and Queue ADTs, Array implementation of Stack [ Read PM 1.2, 1.2.1, 1.2.2, 2.1]
Class 06 (Aug 16): Amortized Analysis [ Read CLRS 17.1-17.3]
Class 07(Aug 22): Array implementation of stacks with array resizing, amortized analysis [Read PM 2.1,2.2; CLRS 17.4]
Class 08 (Aug 24): Array implementation of queues, rootish-array stack [Read PM 2.3, 2.4, 2.6]
Class 09 (Aug 28): Linked lists: Stack and queue implementations using linked lists, doubly linked lists[Read PM 3.1, 3.2]
Class 10 (Aug 30): Finishing Linked lists; Power of Randomness [Read Justin Thaler 2.1, 2.2]
Class 11 (Sep 04): Skiplists: [Read PM Chapter 4]
Class12 (Sep 06): Skiplists: [Read PM Chapter 4]
Class 13(Sep 11): Skiplists: [Read PM Chapter 4]
Class 14 (Sep 13): Revision (Midterm 2018, Midterm 2022, Final 2018, Final 2022)
Class 15(Sep 27): Hash Functions: Introduction [read DPV 1.5]
Class 16(Sep 28): Hash Functions: Universal hash functions, almost universal hash functions [Read class notes, PM 5 ]
Class 17(Oct 09): Hash Functions: Open addressing, linear probing [Read Class Notes PM 5]
Class 18(Oct 11): Trees: Basic terminology, Representations, Tree Traversals [Read PM 6]
Class 19(Oct 14): Binary Search Trees: Find, Insert, Delete in Binary Search trees [Read PM 6, MAW 4.1]
Class 20(Oct 16): AVL Trees [Read MAW 4.4]
Class 21(Oct 18): AVL Trees [ Read MAW 4.4 ]
Class 22(Oct 30): AVL Trees [ Read MAW 4.4 ]
Class 24(Nov 06): Splay Trees [ Read MAW 4.5]
Class 25(Nov 08): Analysis off Splay Trees [Read MAW 11.5, class notes]
Class 26(Nov 13): String Representations, TRIES
Class 27(Nov 15): Patricia Trees, Suffix Trees and Suffix Arrays [Read 7.1, 7.3, 7.4, 7.5 from here]