IT 3rd sem IT 305 Data Structure & Algorithem DSA Syllabus RGTU/RGPV Information Technology(IT) Syllabus
IT 305 Data Structure & Algorithem Course Contents:
Introduction: Basic Terminology, Data types and its classification, Algorithm complexity notations like 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 and linked 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: Algebraic Expression, 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.
1. R. Kruse et al, “Data Structures and Program Design in C”, Pearson Education Asia, Delhi- 2002ISRD Group; Data structures using C; TMH
2. Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication Pvt. Ltd., N Delhi.
3. A M. Tenenbaum, “Data Structures using C & C++”, Prentice-Hall of India Pvt. Ltd., New Delhi.
4. Data Structures Trembley and Sorenson, TMH Publications
5. Pai; Data structure and algorithm; TMH
6. Introduction to Algorithm- Corman, AWL
7. Lipschutz; Data structure (Schaum); TMH
List of Experiments (expandable):
Programs in C relating to different theory units.