Rajiv Gandhi Technological University, Bhopal (MP)
RGTU/RGPV CS-305 DATA STRUCTURES SYLLABUS
B.E. (CS) Computer Science and Engineering Third III SEMESTER SYLLABUS
CS-305 DATA STRUCTURES Course contents:
Unit I Introduction: Basic Terminology, Data types and its classification, Algorithm complexity notations like big Oh,Theta,Omega. 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.
UNIT II 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.
UNIT III 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.
UNIT IV 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.
Unit V Graphs: Introduction, Sequential Representations of Graphs, Adjacency Matrices, Traversal, Connected Component and Spanning Trees, Minimum Cost Spanning Trees.
Reference:
1. R. Kruse et al, “Data Structures and Program Design in C”, Pearson Education Asia, Delhi-2002
2. ISRD Group; Data structures using C; TMH
3. Lipschutz; Data structure (Schaum); TMH
4. Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication Pvt. Ltd., N Delhi.
A. M. Tenenbaum, “Data Structures using C & C++”, Prentice-Hall of India Pvt. Ltd., New Delhi.
5. Data Structures Trembley and Sorenson, TMH Publications
6. Pai; Data structure and algorithm; TMH
7. Introduction to Algorithm- Corman, AWL
ConversionConversion EmoticonEmoticon