Unit - I
Introduction: Basic Terminology, Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time
and Space Complexity, Asymptotic notations: Big-Oh, Time-Space trade-off.
Abstract Data Types (ADT)
Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and
Column Major Order, Application of arrays, Sparse Matrices and their representations.
Linked lists: Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List,
Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation
and Addition,Generalized Linked List .
Unit – II
Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack
in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Recursion, Tower
of Hanoi Problem, Simulating Recursion, Principles of recursion,Tail recursion, Removal of recursion Queues,
Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation
of queues in C, Dequeue and Priority Queue.
Unit – III
Trees: Basic terminology, Binary Trees, Binary Tree Representation: Array Representation and Dynamic
Representation, CompleteBinary Tree, Algebraic Expressions, Extended Binary Trees, Array and Linked
Representation of Binary trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Threaded Binary
trees, Traversing Threaded Binary trees, Huffman algorithm.
Unit – IV
Graphs: Terminology, Sequential and linked Representations of Graphs: Adjacency Matrices, Adjacency List,
Adjacency Multi list, Graph Traversal : Depth First Search and Breadth First Search, Connected Component,
Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transistive Closure and Shortest
Path algorithm: Warshal Algorithm and Dijikstra Algorithm, Introduction to Activity Networks
Unit – V
Searching : Sequential search, Binary Search, Comparison and Analysis Internal Sorting: Insertion Sort,
Selection, Bubble Sort, Quick Sort, Two Way Merge Sort, Heap Sort, Radix Sort, Practical consideration for
Internal Sorting.
Search Trees: Binary Search Trees(BST), Insertion and Deletion in BST, Complexity of Search Algorithm,
AVL trees, Introduction to m-way Search Trees, B Trees & B+ Trees .
Hashing: Hash Function, Collision Resolution Strategies
Storage Management: Garbage Collection and Compaction.