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 and 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, Complete binary 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. Transitive 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 and B+ trees. Hashing : Hash function, Collision resolution strategies. Storage management : Garbage collection and compaction.