DATA STRUCTURE(CS-305)                

Introduction: Basic Terminology, Data types and its classification, Algorithm complexity notationslike big Oh,,. Array Definition, Representation and Analysis of Arrays, Single and Multidimensional Arrays, Address calculation, Array as Parameters, Ordered List and operations, Sparse Matrices,Storage pools, Garbage collection. Recursion-definition and processes, simulating recursion,Backtracking, Recursive algorithms, Tail recursion, Removal of recursion. Tower of Hanoi Problem.

Stack, Array Implementation of stack, Linked Representation of Stack, Application of stack:Conversion of Infix to Prefix and Postfix Expressions and Expression evaluation, Queue, Array andlinked implementation of queues, Circular queues, D-queues and Priority Queues. Linked list,Implementation of Singly Linked List, Two-way Header List, Doubly linked list, Linked List in Array.Generalized linked list, Application: Garbage collection and compaction, Polynomial Arithmetic.

Trees: Basic terminology, Binary Trees, , algebraic Expressions, Complete Binary Tree,Extended Binary Trees, Array and Linked Representation of Binary trees, Traversing Binary trees,Threaded Binary trees, Binary Search Tree (BST ), AVL Trees, B-trees. Application: AlgebraicExpression, Huffman coding Algorithm.

Internal and External sorting ,Insertion Sort, Bubble Sort, selection sort Quick Sort, Merge Sort, Heap Sort, Radix sort, Searching & Hashing: Sequential search, binary search, Hash Table, Hash Functions, Collision Resolution Strategies, Hash Table Implementation. Symbol Table, Static tree table,Dynamic Tree table.

Graphs: Introduction, Sequential Representations of Graphs, Adjacency Matrices, Traversal, Connected Component and Spanning Trees, Minimum Cost Spanning Trees.