Data Structures & Algorithms
Course: Data Structures and Algorithms
Institute: IIIT Pune — F.Y. B.Tech Semester II (AY 2024-25)
Credits: 4 (3L + 2P)
Text Books: Langsam, Augenstin & Tannenbaum — Data Structures using C; Horowitz, Sahni & Anderson-freed — Fundamentals of Data Structures in C; Mark Allen Weiss — Data Structures and Algorithm Analysis in C
This page organizes Unit-wise comprehensive notes covering the full DSA syllabus. Each unit has detailed explanations, diagrams, C code examples, worked examples, and extensive practice questions.
Unit-wise Notes
Unit I — Fundamental Concepts (07 Hrs)
Introduction to Data Structures: Data, Data Objects, Data Types, Abstract Data Type (ADT); Static vs Dynamic, Linear vs Non-Linear data structures. Introduction to Algorithms: Definition, Characteristics, Flowcharts & Pseudo code. Algorithm Analysis: Time & Space Complexity — Big O, Omega Ω, Theta Θ; Best, Average & Worst case analysis.
Unit II — Linear Data Structures, Searching & Sorting (09 Hrs)
Sequential Organization; Arrays as ADT; Storage Representation; Array Insertion & Deletion; Matrix Operations; String Operations (without library functions). Searching: Linear & Binary Search. Sorting: Bubble, Insertion, Selection, Merge, Quick, Heap & Counting Sort; Stable & In-place sorting.
Unit III — Stacks & Queues (08 Hrs)
Stack & Queue as ADT; Operations & Implementation using arrays and dynamic memory. Application of Stack: Expression Conversion (Infix, Prefix, Postfix) & Evaluation. Recursion & Stacks. Linear Queue vs Circular Queue.
Unit IV — Lists (09 Hrs)
List as ADT; Linked Organization. Singly, Doubly & Circular Linked Lists — Implementation & Analysis. Operations: Insertion, Deletion, Searching. Polynomial & Set representation using Linked Lists. Dynamic Memory Management. Sparse Matrix — Representation, Addition & Transpose.
Unit V — Trees & Graphs (09 Hrs)
Binary Tree representation & traversals (Preorder, Inorder, Postorder). Binary Search Tree — Insertion & Deletion. AVL Trees. Graph representation (Adjacency Matrix & Adjacency List). DFS, BFS, Topological Sorting, Shortest Path Algorithms. Priority Queues, Heap Structures, Hashing Techniques & Hash Functions.