Data Structure

Unit I

Introduction, Arrays & Linked Lists: Basic Terminology, Elementary Data Organization, Built-in Data Types in C, Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic Notations — Big Oh, Big Theta and Big Omega, Time-Space Trade-off, Abstract Data Types (ADT). Arrays: Single and Multidimensional Arrays, Row Major and Column Major Order, Derivation of Index Formulae for 1-D/2-D/3-D/n-D Arrays, Sparse Matrices. Linked Lists: Array and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Insertion, Deletion, Traversal, Polynomial Representation and Addition/Subtraction/Multiplication.

Unit II

Stacks & Queues: Stack ADT, Push & Pop, Array and Linked Implementation in C, Prefix and Postfix Expressions, Evaluation of Postfix Expression. Iteration and Recursion — Principles, Tail Recursion, Removal of Recursion, Binary Search, Fibonacci Numbers, Tower of Hanoi, Iteration vs Recursion Trade-offs. Queues: Create, Add, Delete, Full and Empty, Circular Queues, Array and Linked Implementation, Dequeue and Priority Queue.

Unit III

Searching & Sorting: Concept of Searching, Sequential Search, Index Sequential Search, Binary Search, Concept of Hashing & Collision Resolution Techniques. Sorting: Insertion Sort, Selection Sort, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.

Unit IV

Trees: Basic Terminology, Binary Trees, Array and Pointer (Linked List) Representation, Binary Search Tree, Strictly Binary Tree, Complete Binary Tree, Extended Binary Trees, Tree Traversal Algorithms — Inorder, Preorder and Postorder, Constructing Binary Tree from Traversals, Insertion, Deletion, Searching & Modification in BST, Threaded Binary Trees, Huffman Coding using Binary Tree, AVL Tree, B-Tree & Binary Heaps — Concepts & Basic Operations.

Unit V

Graphs: Terminology, Graph Representations — Adjacency Matrices, Adjacency List, Graph Traversal — Depth First Search and Breadth First Search, Connected Components, Spanning Trees, Minimum Cost Spanning Trees — Prim's and Kruskal's Algorithms, Transitive Closure and Shortest Path — Warshall's and Dijkstra's Algorithms.