Data Structures

Unit 1

• Introduction to Data StructuresBasic Terminology, Classification of Data Structures, Operation on Data Structures, abstract data types, selecting a Data Structure, Linear list – Introduction, singly linked list, Circular Linked Lists, Doubly Linked List, Stacks- Operations, Stack algorithm, Stack ADT, Stack applications, Queues- operations, Queue Algorithm, Queue ADT, Queue Applications.

Unit 2

• Trees – Introduction, Types of Trees, creating a Binary Tree from a General Tree, traversing a Binary Tree, Binary Search Trees (BST), BST Operations- Searching, Insertion and Deletion, BST ADT, BST Applications, Threaded Binary Trees, AVL Trees, Red –Black Trees, Splay Trees

Unit 3

• Multi way Search Trees - Introduction, B Trees, B Trees ADT, 2-3 Trees, 2-3- Tree, B* Tree, B+ Trees Heaps: Binary Heaps, Binomial heaps, Fibonacci heaps, Comparison of Various Heaps, Applications Searching: Introduction, Interpolation Search, Jump search.

Unit 4

• Graphs - Introduction, Directed Graphs, Bi connected Components, Representation of Graphs, Graph Traversal Algorithms, Graph ADT, and Applications of Graphs Sorting: Radix Sort, Heap sort, Shell Sort, Tree Sort.

Unit 5

• Hashing and Collision: – Introduction, Hash Tables, Hash Functions, Different Hash Functions: Division Method, Multiplication Method, Mid-square Method, Folding Method; collisions: Collision Resolution by Open Addressing, Collision Resolution by Chaining Files and their Organization: Introduction, Data hierarchy, File Attributes, Text and Binary Files, Basic File Operations, File Organization, Indexing.

Data Structures Lab

Experiment 1:

Write a program that uses functions to perform the following operations on singly linked list: I. Creation. II. Insertion. III. Traversal. IV. Traversal.

Experiment 2:

Write a program that uses functions to perform the following operations on doubly linked list: I. Creation II. Insertion III. Deletion IV. Traversal

Experiment 3:

Write a program that uses functions to perform the following operations on circular linked list: I. Creation II. Insertion III. Deletion IV. Traversal

Experiment 4:

Write a program that implement stack (its operations) using I.Arrays II.ADT

Experiment 5:

Write a program that implement Queue (its operations) using I.Arrays II.ADT

Experiment 6:

Write a program that implements the following sorting methods to sort a given list of integers in ascending order I. Radix Sort II. Heap sort III. Shell Sort IV. Tree Sort.

Experiment 7:

Write a program to implement the tree traversal methods (Recursive and Non-Recursive).

Experiment 8:

Write a program to implement I. Binary Search tree II. B Trees III. B+ Trees IV. AVL trees V. Red - Black trees.

Experiment 9:

Write a program to implement the graph traversal methods.

Experiment 10:

Write a program to implement the following Hash Functions: I. Division Method II. Multiplication Method III. Mid-square Method IV. Folding Method