**CHHATTISGARH SWAMI VIVEKANAND TECHNICAL UNIVERSITY, BHILAI (C.G.)**

**Semester: B.E. IV Sem. Branch: Information Technology**

**Subject: Data Structure**

Unit –1 Simple Linear Data Structure Array (No. of periods 8+2)

Representation of Linear Arrays in Memory, Traversing Linear Array, Inserting and Deleting, Searching: Linear and

Binary, Sorting : Bubble, Selection, Insertion, Quick, Merge, Heap. Polynomial Addition, Representation of

Multidimensional Array in memory, Representation of Sparse Matrices and its Transpose Algorithm.

Unit-2 Linear Linked List (No. of periods 8+2)

Singly Linked List: Representation in Memory, Traversing, Searching, Memory Allocation, Garbage Collection,

Insertion into a linked list, Deletion from a linked list, Header Linked List, Polynomial Addition, Circular Linked List,

Operations on Doubly Linked List : traversing, Searching, Deleting, Inserting.

Unit-3 Stack, Queue and Recursion (No. of periods 8+2)

Stacks: Array Representation, Linked Representation, Arithmetic Expression, Polish Notation, Recursion, Towers of

Hanoi, Queues: Array Representation, Circular Queues, Linked Representation, D-Queues, Priority Queues.

Unit-4 Non-Linear Data Structure Graphs (No. of periods 8+2)

Binary Tress, Representation of binary Trees in Memory, Traversing binary trees, Traversal algorithm using stacks,

Header nodes, Threads, Binary search trees, Searching, Inserting and Deleting in a binary search trees, AVL search

tree, Insertion and Deletion in an AVL search Tree, m-way search tree, Searching Insertion and Deletion in an m-way

search tree, Searching, Insertion and Deletion in a B- tree.

Unit-5 Non-Linear Data Structure Graphs (No. of periods 8+2)

Graph theory terminology, Sequential Representation of Graphs, Adjancy Matrix, Path Matrix, Warshall’s algorithm,

Shortest Paths, Linked Representation of a Graph, Operations on Graph, Traversing on Graphs, Posets, Topological

Sorting.

Name of Text Books :

1. Data Structure by Seymour Lipschutz & G. a. Vijayalaksmi Pai ( Schaum’s outlines)

2. Data Structures using C/C++ by Langsam, Augenstein & Tananbaum ( PHI )

3. Data Structures & Program Design by Robert L Kruse ( PHI )

Name of Reference books :

1. An Introduction to Data Structures with Application by Tremblay & Sorenson ( Tata Mc)

2. Data Structures using C by ISRD Group ( Tata Mc)

3. Classic Data Structure by D Samanata, Prentice-Hall of India

4. Expert Data Structures with C ( 2

nd

Editin ) by R.B. Patel , Khanna Publishing House.