Data Structures

Module 1:

Unit 1

• Basic concepts - Algorithm Specification, Performance analysis - time complexity and space complexity, Asymptotic Notation - Big O, Omega and Theta notations, Introduction to Linear and Non Linear data structures.

Unit 2

• Linear list – singly linked list implementation, insertion, deletion and searching operations on linear list, circular linked list implementation, doubly linked list implementation, insertion, deletion and searching operations. Applications of linked lists.

Module 2:

Unit 1

• Stacks - Operations, array and linked representations of stacks, stack applications-infix to postfix conversion, postfix expression evaluation, recursion implementation.

Unit 2

• Queues - operations, array and linked representations. Circular Queue operations, Dequeue, applications of queue.

Module 3:

Unit 1

• Trees – Terminology, Representation of Trees, Binary tree ADT, Properties of Binary Trees, Binary Tree Representations-array and linked representations, Binary Tree traversals, Threaded binary trees, Binary Heap-Properties, Max and Min Heap, Operations-Insertion and Deletion, Heap sort.

Unit 2

• Search Trees - Binary Search tree, Tree traversals, AVL tree – operations, B-tree – operations, B+ trees, Red Black tree.

Module 4:

Unit 1

• Graphs - Terminology, sequential and linked representation, graph traversals: Depth First Search & Breadth First Search implementation. Minimum spanning trees, Prims and Kruskals method.

Unit 2

• Searching and Sorting - Linear Search and Binary Search, Bubble sort, Insertion sort, Quick and Merge sort.

Module 5:

Unit 1

• Hashing - Hash table, Hash table representations, hash functions, collision resolution techniques- separate chaining, open addressing-linear probing, quadratic probing, double hashing, Re hashing, Extendible hashing.

Unit 2

• Pattern matching - Introduction, Brute force, the Boyer –Moore algorithm, Knuth-Morris-Pratt algorithm.

---

Data Structures Lab

Experiment 1:

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

Experiment 2:

Write a C 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 C program that implement stack operations using > I. Arrays II. Linked Lists

Experiment 4:

I. Write a C program to convert infix expression to postfix expression using stack
II. Write a C program to evaluate postfix expression`

Experiment 5:

Write a C program to convert infix expression to prefix expression using stack

Experiment 6:

Write a C program to implement linear queue using. I.Arrays II. Linked Lists.

Experiment 7:

Write a C program to perform following operations on a circular Queue I. Insertion II. deletion III. search and count

Experiment 8:

Write a C Program to implement binary tree traversals

Experiment 9:

Write a C Program to implement AVL tree operations

Experiment 10:

Implementation of a Graph representation using Adjacency Matrix.

Experiment 11:

I.Write a program to implement Linear Search technique.

II. Write a program to implement Binary Search technique.

Experiment 12:

I. Write a program to implement Bubble sort technique.

II. Write a program to implement Insertion sort technique.

Experiment 13:

I. Write a program to implement Quick sort technique.

II. Write a program to implement Merge sort technique