SEMESTER III CS1201 – DATA STRUCTURES

NNA UNIVERSITY TIRUCHIRAPPALLI
Tiruchirappalli - 620 024
SEMESTER III CS1201 – DATA STRUCTURES

UNITI PROBLEM SOLVING 9
Problem Solving – Top-down Design – Implementation – Verification – Efficiency – Analysis –
Sample Algorithms.
UNIT II LISTS - STACKS AND QUEUES 8
Abstract Data Type (ADT) – The List ADT – The Stack ADT – The Queue ADT
UNIT III TREES 10
Binary Trees – The Search Tree ADT – Binary Search Trees – AVL Trees – Tree Traversals – Hashing
– General Idea – Hash Function – Separate Chaining – Open Addressing – Linear Probing – Priority
Queues (Heaps) – Model – Simple Implementations – Binary Heap
UNIT IV SORTING 9
Insertion Sort–Shell Sort – Heap Sort – Merge Sort – Quick Sort – External Sorting
UNIT V GRAPHS 9
Topological Sort – Shortest Path Algorithms – Unweighted Shortest Paths – Dijkstra’s Algorithm –
Minimum Spanning Tree – Prim’s Algorithm – Applications of Depth-First Search – Undirected
Graphs – Biconnectivity – Introduction to NP Completeness

L: 45 T: 15 Total: 60

TEXT BOOKS
1. R. G. Dromey, “How to Solve it by Computer”, First Edition, Pearson Education, 2006.
2. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Pearson Education, Second
Edition, 2002.

REFERENCES
1. Y. Langsam M. J. Augenstein and A. M. Tenenbaum, “Data Structures using C”, Pearson
Education, 2004.
2. Richard F. Gilberg, Behrouz A. Forouzan, “Data Structures - A Pseudocode Approach with
C”, Thomson Brooks / COLE, 1998.
3. Aho J. E. Hopcroft and J. D. Ullman, “Data Structures and Algorithms”, Pearson education,
1983.
4. Harowitz, Sahani, Anderson-Freed, “Fundamentals of Data Structures in C”, Second Edition,
Universities Press, 2007.