Data Structure (IT-303) - B Tech RGPV AICTE Flexible Curricula Notes -->

## Course objectives

The main objectives of this course are:
1. To introduce the concepts of linear, non-linear data structures , the operations performed on them and the applications of various data structures.
2. To introduce various algorithms of searching and sorting.
3. To understand the basic concepts of stacks, queues, linked lists, trees and graphs
4. To enable students to write algorithms for solving various problems using data structures.

## Syllabus

UNIT 1:
Introduction Data, data type, data object. Types of data structure – primitive &n nonprimitive , linear & non-linear. Operations on data structures – traversing, searching , inserting , deleting. Complexity analysis – worst case, best case, average case. Time – space trade off , algorithm efficiency, asymptotic notations – big oh , omega , theta.

UNIT 2:
Arrays & Structure Introduction , declaration of arrays , operations on arrays – inserting , deleting , merging of two arrays , 1 dimensional & 2 dimensional arrays, row & column major representation , address calculation in array , storing values in arrays , evaluation of polynomial – addition & representation. Searching & sorting – Introduction , sequential search, binary search , Fibonacci search , indexed sequential search, hashed search. Types of sorting with general concepts – bubble , heap , insertion , selection , quick , heap , shell , bucket , radix and merge sort.

UNIT 3:
Stacks & Queues Basic concept of stacks & queues, array representation of stacks, operation on stacks – push , pop , create , getTop , empty , linked representation of stack , multiple stack. Application of stack – Conversion: infix , prefix , postfix and evaluation of arithmetic expression. Linked representation of queue, operations on queue – insertion & deletion. Types of queue with functions – circular , deque , priority queue. Applications of queues – job scheduling , Josephus problem.

UNIT 4:

UNIT 5:
Trees Basic terminology – general tree , representation of general tree, types of trees, binary tree- realization and properties , traversal in binary trees – inorder , preorder , postorder , applications of trees. Graph- Basic Terminologies and representations, Graph search and traversal algorithms.

• Unit 1
• Unit 2
• Unit 3
• Unit 4
• Unit 5

## Course Outcomes

On completion of the course:
1. For a given search problem (linear search and binary search) student will be able to implement it.
2. For a given problem of stacks, queues and link lists, students will be able to implement it and analyze the same to determine the time and computation complexity
3. Students will be able to write an algorithm for selection sort, insertion sort, quick sort, merge sort, heap sort, bubble sort and compare their performance
4. Students will be able to implement tree, graph search and traversal algorithms

## References :

1.Varsha H. Patil “Data Structure Using C++” Oxford. 2. Rajesh K. Shukla “Data Structures Using C & C++” Wiley India. 3. Reema Thareja “ Data Structure Using C ” Oxford. 4. D. S Malik “Data Structure Using C++ ” Second Edition Cengage. 5. Kushwaha and Mishra “Data Structure: A programming Approach with C”, PHI Learning. 6. A. K Sharma “Data Structure Using C” Pearson. 7. Ellis Horowitz, Sartaj Sahni, “Fundamentals of Data Structures”, Computer Science Press

## List of Experiments

1. Write a program to search an element in the array using Linear and Binary Search.
2. Write a program to perform the following operation in Matrix:
1. Addition 2. Subtraction 3. Multiplication 4. Transpose
3. Write a program to perform the following operation on strings using string functions:
1. Addition 2. Copying 3. Reverse 4. Length of String
4. Write program for implementing the following sorting methods to arrange a list of integers in ascending order:
a) Quick sort b) Selection sort c) Insertion sort d) Merge sort
5. Write a program that uses stack operations to convert a given infix expression into its postfix equivalent.
6. Write a program to merge two sorted array into one sorted array.
7. Write a program to implement stack using array and linked list.
8. Write a program to implement queue and circular queue using array.
9. Write a program to insert an element in the beginning and end of singly linked list.
10. Write a program to insert an element at any position in singly and doubly linked list.
11. Insert and delete a node at any position in doubly linked list.
12. Write a program of Tower of Hanoi.
13. Write a program that uses functions to perform the following:
a) Create a binary search tree of integers.
b) Traverse the above Binary search tree non recursively in in order.

## You May Also Like

#### Services

###### COMPLETELY FREE !!!

Yup, everything is free....

###### NO REGISTRATION REQUIRED

User doesn't have to register for accessing the files, all the files are free & universally accessible without any condition or restriction.

###### RESPONSIVE DESIGN & USER-FRIENDLY

Our webpages are responsive & user-friendly, which means it will automatically adjust according to your device screen size and you will find stuff without ant hustle.

All the files are uploaded on our super-fast servers so that they can be easily downloaded with high speed.

###### NEW PROJECTS

For providing a better experience to our users we are developing our Android application, the application will have a lot of awesome features so stay tuned ;).

###### AWESOME SUPPORT TEAM

Our AI-powered Chatbots are always here to help you so, feel free to ask any question or report if you face any problem. Our team also monitors all chatbots traffic & they will contact you if chatbot fails to help.