L 3 C 3
Teachers Continuous Evaluation: as per university examination norms. End Term Theory Examination: as per university examination norms.
Course outcomes
- Understand data structures, algorithm analysis, searching, and sorting techniques. [K2]
- Apply linear data structures such as arrays, linked lists, stacks, and queues in solving computational problems. [K3]
- Evaluate tree-based data structures and balancing techniques for efficient storage, searching, and sorting. [K5]
- Analyze graph traversal methods, disjoint data structures, and hashing techniques for efficient problem solving. [K4]
Unit I (9 lectures)
Introduction to Data Structures: Overview of Data Structures, Data types – primitive and non-primitive, Basics of Algorithms Analysis, Performance Analysis and Measurement (Time and space analysis of algorithms-Average, best and worst case analysis), Asymptotic Notations, Types of Data Structures- Linear & Non Linear Data Structures, Concept of Abstract Data Types. Sorting – Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Sequential (Linear) Search and Binary Search
Unit II (8 lectures)
Linear Data Structures: Array: Representation of arrays, Applications of arrays: sparse matrix and its representation, polynomials and polynomials arithmetics; Linked List: Singly Linked List, Doubly Linked list, Circular linked list; Applications of linked list: Stack-Definitions & Concepts, Operations On Stacks, Linked List vs Array implementation of Stack; Applications of Stacks: Prefix, Infix and Postfix Expressions; Queue: Representation Of Queue, Operations On Queue, Linked List vs Array implementation of Queue, Circular Queue, Priority Queue.
Unit III (7 lectures)
Trees: Tree-Definitions and Concepts, Representation of binary tree, Binary tree traversal (Inorder, postorder, preorder), Binary search trees, Conversion of General Trees To Binary Trees, Applications Of Trees, Balanced trees: AVL trees, Height Balanced Tree, B Tree, B+ Tree; Introduction to Heap, Heap Sort.
Unit IV (8 lectures)
Fundamentals of Graphs & Hashing: Disjoint Data Structures, Union-Find Algorithm,Representation Of Graphs, Graph Traversals: Breadth First Search and Depth First Search; Hashing: Hashing Functions, Collision Resolution Techniques.
Textbooks
- Horowitz, E., Sahni, S., & Mehta, D. P. (2008). Fundamentals of Data Structures in C++ (2nd ed.). Universities Press (India).
- Langsam, Y., Augenstein, M. J., & Tenenbaum, A. M. (2015). Data Structures Using C and C++ (2nd ed.). Pearson Education India.
- Tremblay, J. P., & Sorenson, P. G. (2012). An Introduction to Data Structures with Applications. Tata McGraw Hill.
- Gilberg, R. F., & Forouzan, B. A. (2011). Data Structures: A Pseudocode Approach with C (2nd ed.). Cengage Learning India Pvt. Ltd.
References
- Cormen, T. H., Leierson, C. E., Riest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.
- Weiss, M. A. (2014). Data Structures and Algorithm Analysis in C++ (4th ed.). Pearson Education.