Data Structure (IT-303)
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.
rgpv bhopal, diploma, rgpv syllabus, rgpv time table, how to get transcript from rgpv, rgpvonline,rgpv question paper, rgpv online question paper, rgpv admit card, rgpv papers, rgpv scheme
B.Tech RGPV notes AICTE flexible curricula Bachelor of technology
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:
Linked List Introduction – basic terminology , memory allocation & deallocation for
linked list. Linked list variants – head pointer , head node , types linked list – linear & circular
linked list. Doubly linked list , creation of doubly list, deletion of node from doubly linked list,
insertion of a node from doubly linked list, traversal of doubly linked list. Circular linked list –
singly circular linked list , circular linked list with header node , doubly circular linked list.
Applications of linked list – polynomial representation & garbage collection.
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.
NOTES
- 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
- ES-301 - Energy & Environmental Engineering
- IT-302 - Discrete Structure
- IT-304 - Object Oriented Programming & Methodology
- IT-305 - Digital Circuits & System
- IT-306 - JAVA Programming Lab
- BT-107 - Evaluation of Internship-I ompleted at I year level
- BT-307 - 90 hrs Internship based on using various software’s –Internship -II
