Course Outline : The course consists of 3 lecture hours per week. The lectures will be focused on the design and analysis of the classical data structures. A basic syllabus will be followed as outlined in the school website here.
Course Instructor : Dr. Arun Kumar Das, SCIS
Teaching Assistants:
Venue: Wednesday at Room 10 at LHC1, Thursday with Lab
Timings : Wednesday 9 AM - 11 AM, Thursday 2 PM - 3 PM
Grading policy : Assignments - 20%, Minor (Mid Sem) - 20%, Major (End Sem) - 60%
Reference Books : 1. Data Structures and Program Design in C by R Kruse, CL Tondo
Lecture 1 (07/01/2025) : Course outline, Introduction, Complexity, Arrays and their operations, Addition and Multiplication of Large Integers.
Some definitions about the notation of the complexity analysis can be found here.
Lecture 2(08/01/2025) : Sparse Matrix, Stacks, Stack Operations, Factorial of a positive integer, Checking the matching of parentheses using stacks.
Lecture 3(15/01/2025) : Conversion and evaluation of expressions (Postfix, Postfix, and Prefix). Queue, Operations on queue, Linear structure vs. circular structure of queue, Operation for circular queue.
Lecture 4(22/01/2025) : Problems involving Stacks and Queues. Simulating Stack using queues and vice versa. Reporting the Maximum key in a stack in O(1) time, Stack permutations, Algorithmic Puzzle.
Lecture 5(23/01/2025) : Introduction to Linked Lists. Operations on Linked List.
Lecture 6(29/01/2025) : Simulating Stacks and Queues using Linked Lists. Operations on Linked Lists. Exercises on Singly Linked Lists.
Lecture 7(30/01/2025) : . Doubly Connected Linked Lists. Difference with the Singly connected linked lists.
Lecture 8(05/02/2025) : Circular Linked Lists. Exercises on Circular Linked Lists.
Lecture 9(06/02/2025) : Exercises on Stacks and Queues. Polynomials and Singly Linked Lists.
Lecture 10(19/02/2025) : Introduction to sorting algorithms. Bubble sort, Selection sort, Insertion sort.
Lecture 11(20/02/2025) : Merge Sort and analysis. Counting the number of Comparisons.
Lecture 12(26/02/2025) : Searching Techniques, Linear Search, Binary Search. Hashing: Hash table, Hash functions, Collision avoiding.
Lecture 13(27/02/2025) : Solving Algorithmic Problems in Sorting and Searching. Longest increasing subsequence in an array.
Lecture 14(05/03/2025) : Binary Trees: Introduction, Definitions, Recursive Calls, Finding Heights, Traversals: Inorder, Preorder, Postorder.
Minor (05/03/2025) : Theory Minor Examination!
Lecture 15(06/03/2025) : Algorithms for binary tree traversals, dry runs on the algorithms.
Lecture 16(12/03/2025) : Level order traversal, Euler tours, Reconstructing binary trees from their traversals, Introduction to Binary Search Trees(BST), Searching for a key in BST.
Lecture 17(13/03/2025) : Binary search tree problems, height of a node and subtrees.
Lecture 18(19/03/2025) : Introduction to AVL Trees, Rotations, Building an AVL tree.
Lecture 19(20/03/2025) : Implementation details of AVL Trees, insertions, rotations, traversals.
Lecture 20(26/03/2025) : Deletion Operations: BST and AVL Trees.
Lecture 21(27/03/2025) : Problems on BST and AVL Trees. BST balancing on the number of nodes.
Lecture 22(09/04/2025) : Introduction to Heap Structures, Priority Queues, Heapsort.
Lecture 23(16/04/2025) : Introduction to Graphs. Directed and undirected graphs, Adjacency Matrix, Adjacency List. Introduction to DFS and BFS.
Lecture 24(17/04/2025) : Implementation issues of adjacency matrix and list for a graph as an ADT.
Lecture 25(23/04/2025) : Details of DFS and BFS, finding connected components.
Project Minor evaluation (24/04/2025) : Evaluation of the assignment project!
Lecture 26(30/04/2025) : Shortest path finding between two vertices in graph, Dijkstra's shortest path algorithm, power of adjacency matrix: counting the number of paths between two vertices of a given length.
Lecture 27(01/05/2025) : Recaps and wrap up!