JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
ADVANCED DATA STRUCTURES LAB
M.Tech I Year I Semester (R19)
Prerequisites
A course on Computer Programming & Data Structures
Course Objectives:
1. Introduces the basic concepts of Abstract Data Types.
2. Reviews basic data structures such as stacks and queues.
3. Introduces a variety of data structures such as hash tables, search trees, tries, heaps, graphs, and B-trees.
4. Introduces sorting and pattern matching algorithms.
Course Outcomes:
1. Ability to select the data structures that efficiently model the information in a problem.
2. Ability to assess efficiency trade-offs among different data structure implementations or combinations.
3. Implement and know the application of algorithms for sorting and pattern matching.
4. Design programs using a variety of data structures, including hash tables, binary and general tree structures, search trees, tries, heaps, graphs, and B-trees. List of Programs
1. Write a program to perform the following operations:
a) Insert an element into a binary search tree.
b) Delete an element from a binary search tree.
c) Search for a key element in a binary search tree.
2. Write a program for implementing the following sorting methods:
a) Merge sort b) Heap sort c) Quick sort
3. Write a program to perform the following operations:
a) Insert an element into a B- tree.
b) Delete an element from a B- tree.
c) Search for a key element in a B- tree.
4. Write a program to perform the following operations:
a) Insert an element into a Min-Max heap
b) Delete an element from a Min-Max heap
c) Search for a key element in a Min-Max heap
5. Write a program to perform the following operations:
a) Insert an element into a Lefiist tree
b) Delete an element from a Leftist tree
c) Search for a key element in a Leftist tree
6. Write a program to perform the following operations:
a) Insert an element into a binomial heap
b) Delete an element from a binomial heap.
c) Search for a key element in a binomial heap R19 M. TECH. CN/CNIS/CYBER SECURITY
7. Write a program to perform the following operations:
a) Insert an element into a AVL tree.
b) Delete an element from a AVL search tree.
c) Search for a key element in a AVL search tree.
8. Write a program to perform the following operations:
a) Insert an element into a Red-Black tree.
b) Delete an element from a Red-Black tree.
c) Search for a key element in a Red-Black tree.
9. Write a program to implement all the functions of a dictionary using hashing.
10. Write a program for implementing Knuth-Morris-Pratt pattern matching algorithm.
11. Write a program for implementing Brute Force pattern matching algorithm.
12. Write a program for implementing Boyer pattern matching algorithm.
TEXT BOOKS:
1. Fundamentals of Data structures in C, E.Horowitz, S.Sahni and Susan Anderson Freed, 2nd Edition, Universities Press
2. Data Structures Using C – A.S.Tanenbaum, Y. Langsam, and M.J. Augenstein, PHI/Pearson education.
3. Introduction to Data Structures in C, Ashok Kamthane, 1st Edition, Pearson.
REFERENCES:
1. The C Programming Language, B.W. Kernighan, Dennis M.Ritchie, PHI/Pearson Education
2. C Programming with problem solving, J.A. Jones & K. Harrow, Dreamtech Press
3. Data structures: A Pseudocode Approach with C, R.F.Gilberg And B.A.Forouzan, 2nd Edition, Cengage Learning. R19 M. TECH. CN/CNIS/CYBER SECURITY M. Tech. (CNIS/CN/Cyber Security) – I Year – I Semester Common to CNIS, CN and Cyber Security