Data Structure

Unit 1

Introduction: Basic Terminology, Elementary Data Organization, Data Structure operations, Algorithm Complexity and Time-Space trade-off Arrays: Array Definition, Representation and Analysis, Single and Multidimensional Arrays, Character String in C, Character string operation, Ordered List, Sparse Matrices, and Vectors. Stacks: Array Representation and Implementation of stack, Operations on Stacks: Push & Pop, Array Representation of Stack, Linked Representation of Stack, Operations Associated with Stacks, Applications of stack: Conversion of Infix to Prefix and Postfix Expressions, Evaluation of postfix expression using stack. Recursion: Recursive definition and processes, Tower of Hanoi Problem, tail recursion, removal of recursion.

Unit 2

Queues: Array and linked representation and implementation of queues, Operations on Queue: Create, Add, Delete, Full and Empty. Circular queue, Deque, and Priority Queue, Linked list: Representation and Implementation of Singly Linked Lists, Two-way Header List, Traversing and Searching of Linked List, Overflow and Underflow, Insertion and deletion to/from Linked Lists, Insertion and deletion Algorithms, doubly linked list, Linked List in Array, Polynomial representation and addition, Generalized linked list.

Unit 3

Trees: Basic terminology, Binary Trees, Binary tree representation, algebraic Expressions, Complete Binary Tree. Extended Binary Trees, Array and Linked Representation of Binary trees, Traversing Binary trees, Threaded Binary trees. Traversing Threaded Binary trees, Huffman algorithm. Searching and Hashing: Sequential search, binary search, comparison and analysis, Hash Table, Hash Functions, Collision Resolution Strategies, Hash Table Implementation.