Classes: Mondays and Wednesdays 09:30-11:10
Additional Lab Hours: Wednesdays 16:00-18:00
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]
The C Programing Language, Kerninghan and Ritchie [KR]
Grading: Midterm 20%, Assignments/Class tests 30%, Final 50%
Below we keep a record of what we do in each class along with references. We do not give explicit references to the topics in C that are covered. You can follow any standard text book on C (for example [KR]) for the C topics.
Class 01 (Jul 24) : Introduction: Algorithms and Pseudo Codes. Insertion Sort. Real Machines and models of computations. RAM model of computation. Topics in C: Basic structure of C Programs: for and while loops, conditional statements [Read CLRS 2.1, 2.2, 3.1]. Programs to write
Class 02 (Jul 29): Running Time of Algorithms, Asymptotic Notations, analysis of Insertion Sort. Linear Search and Binary search with analysis. Topics in C: Arrays, Implementing Insertion sort, Linear Search and Binary Search [Read CLRS 2.1, 2.2, 3.1] Programs to write
Class 03 (Jul 31): Introduction to Abstract Data Types. The stack ADT. Basic Array implementation of a stack. Topics in C: Characters and Strings. Pointers and Structures. Dynamic memory allocation. Implementing a stack. [ Read Class Notes] Programs to write
Class 04 (Aug 05): Stack Implementation with array resizing. Introduction to Amortized analysis. Accounting method applied to array resizing. Topics in C: Implementing a stack with array resizing. The malloc and realloc functions.[Read Class Notes ] Programs to write
Class 05 (Aug 07): The Queue ADT. Array implementation of Queue. The generalized list ADT. Topics in C: Implementing a array based queue.[PM 2.3 ] Programs to write
Class 06 (Aug 12): Introduction to Linked Lists. Implementing stacks and queues with linked lists. [read PM 3.1] . Programs to write
Class 07 (Aug 14): General list using linked list. Doubly linked lists; General list with doubly linked list [read PM 3.2]. Programs to write
Class 08 (Aug 19): Rootish Array [read PM 2.6]. Topics in C: Implementing a generic linear search. Read about pointer arithmetic and function pointers. Programs to write
Class 09 (Aug 26): Topics in C: Implementing a generic stack.
Class 10 (Aug 28): Topics in C: Implementing a generic stack. Programs to write [A Generic Stack]
Class 11 (Aug 28): Applications of stack: Converting Infix to Postfix [read MAW 3.6.3], Introduction to Amortized analysis: Aggregate method and Accounting method [read CLRS 17.1, 17.2]. Topics in C: Implementing a generic list. memcpy and memmove instructions with applications
Class 12 (Sep 02): Amortized analysis: Potential function method [read CLRS 17.3, 17.4]
Class 13 (Sep 04): Priority Queue: The priority queue ADT. Array and linked list based implementations. Max-Heap and Min-Heap. Implementing the priority queue ADT using heaps [read class notes and CLRS 6.1, 6.3, 6.5] [Practice Problems for Midterm]
Class 14 (Sep 18): Hash Tables: Introduction. Direct Addressing. Universal Hash functions [read class notes and CLRS 11.1, 11.2, DPV 1.5] [Assignment 1]
Class 15 (Sep 23): Hash Tables: Universal, Almost Universal and XOR-Almost Universal hash.[read class notes]
Class 16 (Sep 23): Hash Tables:Analysis and Implementation of Hashing with chaining [Read class notes, PM 5 ]
Class 17 (Sep 25): Hash Tables: Analysis and Implementation of Hashing with chaining [Read class notes, PM 5, CLRS 11.4 ]
Class 18 (Sep 30): Hash Tables: Open Addressing, linear probing [Read class notes, PM 5 ]
Class 19 (Oct 03): Hash Tables: Perfect hashing [read class notes and CLRS 11.5]
Class 20 (Oct 14): Skiplists [Read PM Chapter 4]
Class 21 (Oct 16): Skiplists [Read PM Chapter 4]
Class 22 (Oct 21): Recursion: Various examples [read class notes]
Class 23 (Oct 23): Recursion: Divide and Conquer, Merge Sort [read class notes]
Class 24 (Oct 28): Binary trees [Read PM 6, MAW 4.1]
Class 25 (Oct 30): Binary search trees: Insertion, find and deletion [Read PM 6, MAW 4.1]
Class 26 (Nov 04): Balanced trees: AVL trees [Read MAW 4.4]
Class 27 (Nov 06): AVL Trees [Read MAW 4.4]
Class 28 (Nov 13): Revision and some problem solving. Some previous years question papers: (Midterm 2018, Midterm 2022, Final 2018, Final 2022)
Assignment 2