Sathyabama Institute of Science and Technology B.Tech IT SCSA1304 Advanced Data Structures Syllabus

[Rajkumar Agarwal]

Sathyabama Institute of Science and Technology B.Tech IT SCSA1304 Advanced Data Structures Syllabus

SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY

SCSA1304 ADVANCED DATA STRUCTURES

UNIT 1 BASIC TREE CONCEPTS 9 Hrs.
Trees- Ordinary and Binary trees terminology, Properties of Binary trees, Implementation using Array and Linked list -
Binary tree ADT representations, recursive and non recursive traversals - Binary Search Tree - Insertion and Deletion.
UNIT 2 ADVANCED TREE CONCEPTS 9 Hrs.
Threaded Binary Trees, AVL Tree, B-tree Insertion and deletion, Splay trees - Heap trees - Heapify Procedure, Tries.

UNIT 3 GRAPH CONCEPTS 9 Hrs.
Terminology, Representation using Array and Linked List - Types of graphs - Graph traversals - BFS and DFS -
Applications.

UNIT 4 ADVANCED GRAPH CONCEPTS 9 Hrs.
Minimum Spanning Tree - Kruskal’s, Prim’s and Sollin’s Algorithm - Shortest path using Dijkstra’s, Bellman Ford and Floyd
Warshall Algorithm.

UNIT 5 TABLES AND SETS 9 Hrs.
Rectangular tables - Jagged tables - Inverted tables - Symbol tables - Static tree tables - Dynamic tree tables - Hash tables.
Sets: Representation - Operations on sets - Applications.
Max. 45 Hrs.

COURSE OUTCOMES
On completion of the course, student will be able to
CO1 - Design and implement the various non-linear data structures and perform the intended operations.
CO2 - Understand the strength of balancing the height of the trees.
CO3 - Analyze the time complexity of various non linear data structures.
CO4 - Apply the algorithms to find the shortest path & to connect the nodes with minimum cost.
CO5 - Design the table and applying the table for many applications.
CO6 - Compare and identify the usage of different data structures.

TEXT / REFERENCE BOOKS
1. Ellis Horowitz and SartajSahni “Fundamentals of Data Structures” Galgotia Book Source, Pvt. Ltd., 2004.
2. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Second Edition, Pearson Education, 2005.
3. Jean Paul Tremblay and Paul G. Sorenson, “An Introduction to Data Structures with Applications”, Tata McGraw-Hill,
Second edition, 2001.
4. Aaron M Tanenbaum, Moshe J Augenstein and YedidyahLangsam, "Data Structures using C and C++", Pearson
Education, 2004.
5. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”, Pearson Education, 1st Edition Reprint
2003.
6. R. F. Gilberg, B. A. Forouzan, “Data Structures”, 2nd Edition, Thomson India Edition, 2005.


END SEMESTER EXAMINATION QUESTION PAPER PATTERN
Max. Marks: 100 Exam Duration: 3 Hrs.
PART A: 10 Questions carrying 2 marks each – No choice 20 Marks
PART B: 2 Questions from each unit of internal choice, each carrying 16 marks 80 Marks