1

INSTITUTE VISION

To be an organization with potential for excellence in engineering

and management for the advancement of society and human kind.

INSTITUTE MISSION

1. To excel in academics, practical engineering, management and

to commence research endeavors.

2. To prepare students for future opportunities.

3. To nurture students with social and ethical responsibilities.

VISION OF DEPARTMENT

To create proficient graduates with technical

knowledge and social value.

MISSION OF DEPARTMENT
1. To improvise teaching and learning process through modern
tool usage.

2. To encourage participation between department and industry

through internships and interactions.

3. To cater ethical and value based education by addressing social

needs.
 2

Excelssior’s Education Society

K. C. COLLEGE OF ENGINEERING
AND MANAGEMENT STUDIES AND RESEARCH
THANE (EAST).

This is to certify that Mr. / Ms. ___________________________________

of Semester ________ Branch ____________ Roll No. _________

has performed and successfully completed all the practicals in the subject
of ______________________________________________ for the
academic year 20___ to 20___ as prescribed by University of Mumbai.

DATE :- ____________.

_____________________________ _____________________________

Practical Incharge Internal Examiner

_____________________________ _____________________________

Head of Department External Examiner

COLLEGE SEAL
 3

Lab Code Lab Name Credits

CSL303 Data Structures Lab 1

Lab outcomes:
1. Students will be able to implement various linear and nonlinear data structures.
2. Students will be able to handle operations like insertion, deletion, searching and traversing
on various data structures.

Description: Experiments based on creating and manipulating various data structures.

Suggested Experiments:
Students are required to complete at least 12 experiments.
Star (*) marked experiments are compulsory.
*1) Array Implementation of Stack.
*2) Conversion of Infix to Postfix.
3) Evaluation of Postfix Expression.
4) Check continuity of different types of parenthesis using stack.
5) Array Implementation of Queue.
7) Array Implementation of Priority Queue
*8) Implementation of Singly Linked List
9) Linked Implementation of Stack
10) Linked Implementation of Queue.
11) Implementation of Circular Linked List.
12) Implementation of Doubly Linked
List. *13) Implement Binary Search Tree.
14) Implementation of Bubble Sort.
15) Implementation of Insertion Sort.
16) Implementation of Merge Sort.
*17) Implementation of Quick Sort.
*18) Implementation of Binary Search.
19) Implementation of Hashing.
20) Implementation of Depth First Search and Breadth First Search.

University of Mumbai, B. E. (Computer Engineering), Rev 2016 28

 7

Term Work:
1. Term work should consist of at least 10 experiments.
2. Journal must include at least 2 assignments.
3. A case study should be conducted using a Mini Project by taking a good problem
definition and complete the following phases.

a. Decomposing the problem into modules

b. Identifying the best suited data structure for solving the sub problems with
justification

c. Define algorithms for various identified functions

d. Implement the modules

4. The final certification and acceptance of term work ensures that satisfactory
performance of laboratory work and minimum passing marks in term work.
5. Term Work:

Total 25 Marks = (Experiments: 10 mark + Mini Project: 05 mark + Assignments: 05

mark)
Practical and oral examination will be based on the above syllabus.
 8

Program Outcomes
Engineering Graduates will be able to:
1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.

2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems

and design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
considerations.

4. Conduct investigations of complex problems: Use research-based knowledge and

research methods including design of experiments, analysis and interpretation of data, and
synthesis of the information to provide valid conclusions.

5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to
assess societal, health, safety, legal and cultural issues and the consequent responsibilities
relevant to the professional engineering practice.

7. Environment and sustainability: Understand the impact of the professional

engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development.

8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities
and norms of the engineering practice.

9. Individual and team work: Function effectively as an individual, and as a member or

leader in diverse teams, and in multidisciplinary settings.

10. Communication: Communicate effectively on complex engineering activities with the

engineering community and with society at large, such as, being able to comprehend and
write effective reports and design documentation, make effective presentations, and give
and receive clear instructions.

11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member
and leader in a team, to manage projects and in multidisciplinary environments.
12. Life-long learning: Recognize the need for, and have the preparation and ability to
engage in independent and life-long learning in the broadest context of technological
change.
 9

LAB OUTCOMES
Subject: Data Structure Class: S.E.(A&B)
SEM : III

CODE LAB OUTCOMES

CSL303.1 Implement Various linear and Nonlinear Data structure
CSL303.2 Demonstrate Operation like insertion, deletion, searching
and traversing on various data structure
 10

RUBRICS OF PRACTICAL

Maximu
Rubrics m
10 10-7 7-4 4-0
Description Marks
Weight

Successful
Few errors in
completion Output correct Incorrect
Implementation the output
3 with accurate not precise output
(R1) (2-1)
output (3-2) (1-0)
(3)

Understand
Understand
experiment
experiment but Improper No
Understanding and drawn
4 conclusion conclusion conclusion
(R2) correct
less accurate (3-2) (2-0)
conclusion
(4-3)
(4)

Submission
Submission
Punctuality and Submission Submission after three
after two
discipline 3 within a week after a week weeks or
weeks
(R3) (3) (3-2) more
(2-1)
(1-0)
 8

TABLE OF CONTENTS

Sr. Date of Date of Pg Grade

No Name of Experiment Performance Submission No. Sign
Sr. Date of Date of Pg Grade
No Name of Experiment Performance Submission No. Sign

Total Grade / Marks :-

Avg. marks of Experiments Avg. marks of Assignments

(A) (B) Total Marks

(A+B)

Obtained Out of Obtained Out of

Practical Incharge Date

 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge

Experiment no 1
Aim : Implementation of stack using array.
Theory:A stack data structure can be implemented using one dimensional array. But
stack implemented using array, can store only fixed number of data values. Define a
one dimensional array of specific size and insert or delete the values into that array by
using LIFO principle with the help of a variable 'top'. Initially top is set to -1.
Whenever we want to insert a value into the stack, increment the top value by one and
then insert. Whenever we want to delete a value from the stack, then delete the top
value and decrement the top value by one.
Algorithm:
INITIALIZATION:
Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2 - Declare all the functions used in stack implementation.
Step 3 - Create a one dimensional array with fixed size (intstack[SIZE])
PUSH(VALUE)
Step 1 - Check whether stack is FULL. (top == SIZE-1)
Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then increment top value by one (top++) and set
stack[top] to value (stack[top] = value).
POP() - DELETE A VALUE FROM THE STACK
Step 1 - Check whether stack is EMPTY. (top == -1)
Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value by
one (top--).
DISPLAY() - DISPLAYS THE ELEMENTS OF A STACK
Step 1 - Check whether stack is EMPTY. (top == -1)
Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then define a variable 'i' and initialize with top.
Display stack[i] value and decrement i value by one (i--).
Step 4 - Repeat above step until i value becomes '0'.

Conclusion :
 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge

Experiment No 2
Aim :Implement Of Queue Using Array.
Theory: Queue is a linear data structure in which the insertion and deletion
operations are performed at two different ends. In a queue data structure, adding and
removing of elements are performed at two different positions. The insertion is
performed at one end and deletion is performed at other end. In a queue data structure,
the insertion operation is performed at a position which is known as 'rear' and the
deletion operation is performed at a position which is known as 'front'. In queue data
structure, the insertion and deletion operations are performed based on FIFO (First
In First Out) principle.

Algorithm:
INITIALIZATION:
Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2 - Declare all the user defined functions which are used in queue
implementation.
Step 3 - Create a one dimensional array with above defined SIZE
(intqueue[SIZE])
Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'.
(int front = -1, rear = -1)

enQueue(value) - Inserting value into the queue

Step 1 - Check whether queue is FULL. (rear == SIZE-1)
Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

deQueue() - Deleting a value from the Queue

Step 1 - Check whether queue is EMPTY. (front == rear)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++).
Then display queue[front] as deleted element. Then check whether
both frontand rear are equal (front == rear), if it TRUE, then set
both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Queue

Step 1 - Check whether queue is EMPTY. (front == rear)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set
'i = front+1'.
 Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the
same until 'i' value reaches to rear (i <= rear)

Conclusion:
 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge
 Experiment No 3.
Aim: Implementation of Infix to postfix transformation using Stack.
Theory:
Infix to Postfix Conversion using Stack Data Structure
To convert Infix Expression into Postfix Expression using a stack data structure, We
can use the following steps...
Read all the symbols one by one from left to right in the given Infix Expression.
If the reading symbol is operand, then directly print it to the result (Output).
If the reading symbol is left parenthesis '(', then Push it on to the Stack.
If the reading symbol is right parenthesis ')', then Pop all the contents of stack until
respective left parenthesis is poped and print each poped symbol to the result.
If the reading symbol is operator (+ , - , * , / etc.,), then Push it on to the Stack.
However, first pop the operators which are already on the stack that have higher or
equal precedence than current operator and print them to the result.
Example:
Conclusion:
 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge
 Experiment No 4.
Aim: Implementation of circular queue

Theory:Circular Queue is a linear data structure in which the operations are

performed based on FIFO (First In First Out) principle and the last position is
connected back to the first position to make a circle.
Algorithm:
Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2 - Declare all user defined functions used in circular queue implementation.
Step 3 - Create a one dimensional array with above defined SIZE
(intcQueue[SIZE])
Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'.
(int front = -1, rear = -1)
Step 5 - Implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on circular queue.

enQueue(value) - Inserting value into the Circular Queue

Step 1 - Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front
== rear+1))
Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then check rear == SIZE - 1 &&front != 0 if it
is TRUE, then set rear = -1.
Step 4 - Increment rear value by one (rear++), set queue[rear] = value and check
'front == -1' if it is TRUE, then set front = 0.

deQueue() - Deleting a value from the Circular Queue

Step 1 - Check whether queue is EMPTY. (front == -1 && rear == -1)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then display queue[front] as deleted element and
increment the front value by one (front ++). Then check whether front == SIZE, if
it is TRUE, then set front = 0. Then check whether both front - 1 and rear are
equal (front -1 == rear), if it TRUE, then set both front and rear to '-1'
(front = rear = -1).

display() - Displays the elements of a Circular Queue

Step 1 - Check whether queue is EMPTY. (front == -1)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
 Step 4 - Check whether 'front <= rear', if it is TRUE, then display 'queue[i]' value
and increment 'i' value by one (i++). Repeat the same until 'i <= rear'
becomes FALSE.
Step 5 - If 'front <= rear' is FALSE, then display 'queue[i]' value and increment 'i'
value by one (i++). Repeat the same until'i<= SIZE - 1' becomes FALSE.
Step 6 - Set i to 0.
Step 7 - Again display 'cQueue[i]' value and increment i value by one (i++).
Repeat the same until 'i <= rear' becomes FALSE.

Conclusion:
 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge
 Experiment No 5.
Aim : Implementation Of Singly Linked List.

Theory: Single linked list, the individual element is called as "Node".

Every "Node" contains two fields, data and next. The data field is used to store
actual value of that node and next field is used to store the address of the next node in
the sequence.

Algorithm:

INITIALIZATION

Step 1 - Include all the header files which are used in the program.
Step 2 - Declare all the user defined functions.
Step 3 - Define a Node structure with two members data and next
Step 4 - Define a Node pointer 'head' and set it to NULL.
Step 5 - Implement the main method by displaying operations menu and make
suitable function calls in the main method to perform user selected operation.

Insertion

In a single linked list, the insertion operation can be performed in three ways. They
are as follows...
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked
list...
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
Step4- If t is Not Empty then, set newNode→next = head and head = newNode.

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...
Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize
with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the last node in
the list (until temp → next is equal to NULL).
Step 6 - Set temp → next = newNode.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked
list...
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize
with head.
Step 5 - Keep moving the temp to its next node until it reaches to the node after
which we want to insert the newNode (until temp1 → data is equal to location,
here location is the node value after which we want to insert the newNode).
Step 6 - Every time check whether temp is reached to last node or not. If it is
reached to last node then display 'Given node is not found in the list!!! Insertion
not possible!!!' and terminate the function. Otherwise move the temp to next node.
Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp →
next = newNode'

Deletion

In a single linked list, the deletion operation can be performed in three ways. They are
as follows...
1. Deleting from Beginning of the list
2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked
list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with head.
Step 4 - Check whether list is having only one node (temp → next == NULL)
Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.
Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Check whether list has only one Node (temp1 → next == NULL)
Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate
the function. (Setting Empty list condition)
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next
node. Repeat the same until it reaches to the last node in the list. (until temp1 →
next == NULL)
Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or
to the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to
its next node.
Step 5 - If it is reached to the last node then display 'Given node not found in the
list! Deletion not possible!!!'. And terminate the function.
Step 6 - If it is reached to the exact node which we want to delete, then check
whether list is having only one node or not
Step 7 - If list has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 (free(temp1)).
Step 8 - If list contains multiple nodes, then check whether temp1 is the first node
in the list (temp1 == head).
Step 9 - If temp1 is the first node then move the head to the next node (head =
head → next) and delete temp1.
Step 10 - If temp1 is not first node then check whether it is last node in the list
(temp1 → next == NULL).
Step 11 - If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).
Step 12 - If temp1 is not first node and not last node then set temp2 →
next = temp1 → next and delete temp1 (free(temp1)).

Displaying a Single Linked List

We can use the following steps to display the elements of a single linked list...
 Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with head.
Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to
the last node
Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data
---> NULL).

Conclusion:
 EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________
 Practical Incharge

Experiment No 6.
Aim: Implementation of Queue using Linked list.

Theory:The queue which is implemented using a linked list can work for an
unlimited number of values. That means, queue using linked list can work for the
variable size of data (No need to fix the size at the beginning of the implementation).
The Queue implemented using linked list can organize as many data values

Algorithm:

INITIALIZATION

Step 1 - Include all the header files which are used in the program. And declare all
the user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
Step 4 - Implement the main method by displaying Menu of list of operations and
make suitable function calls in the main method to perform user selected
operation.

enQueue(value) - Inserting an element into the Queue

Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.
Step 2 - Check whether queue is Empty (rear == NULL)
Step 3 - If it is Empty then, set front = newNode and rear = newNode.
Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not
possible!!!" and terminate from the function
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).

display() - Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...
 Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the
function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with front.
Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same
until 'temp' reaches to 'rear' (temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.

Conclusion:

EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)
 ______________________________________

Practical Incharge

Experiment No 7.
Aim: Implementation of Binary Search Tree.
Theory: Binary Search Tree is a binary tree in which every node contains only
smaller values in its left subtree and only larger values in its right subtree.
1. Search Operation - O(n)
2. Insertion Operation - O(1)
3. Deletion Operation - O(n)

Algorithm:
Operations on a Binary Search Tree

The following operations are performed on a binary search tree...

Search
Insertion
Deletion

Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time
complexity. The search operation is performed as follows...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.
Step 3 - If both are matched, then display "Given node is found!!!" and terminate
the function
Step 4 - If both are not matched, then check whether search element is smaller or
larger than that node value.
Step 5 - If search element is smaller, then continue the search process in left
subtree.
Step 6- If search element is larger, then continue the search process in right
subtree.
Step 7 - Repeat the same until we find the exact element or until the search
element is compared with the leaf node
 Step 8 - If we reach to the node having the value equal to the search value then
display "Element is found" and terminate the function.
Step 9 - If we reach to the leaf node and if it is also not matched with the search
element, then display "Element is not found" and terminate the function.

Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time
complexity. In binary search tree, new node is always inserted as a leaf node. The
insertion operation is performed as follows...

Step 1 - Create a newNode with given value and set its left and right to NULL.
Step 2 - Check whether tree is Empty.
Step 3 - If the tree is Empty, then set root to newNode.
Step 4 - If the tree is Not Empty, then check whether the value of newNode
is smaller or larger than the node (here it is root node).
Step 5 - If newNode is smaller than or equal to the node then move to
its left child. If newNode is larger than the node then move to its right child.
Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to
NULL).
Step 7 - After reaching the leaf node, insert the newNode as left child if the
newNode is smaller or equal to that leaf node or else insert it as right child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time
complexity. Deleting a node from Binary search tree includes following three
cases...

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child
Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - Delete the node using free function (If it is a leaf) and terminate the
function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has only one child then create a link between its parent node and
child node.
 Step 3 - Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.
Step 3 - Swap both deleting node and node which is found in the above step.
Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto
step 2
Step 5 - If it comes to case 1, then delete using case 1 logic.
Step 6- If it comes to case 2, then delete using case 2 logic.
Step 7 - Repeat the same process until the node is deleted from the tree.

Conclusion:

EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks
Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge

Experiment No 8.
Aim: Implementation of Quick Sort.
Theory: QuickSort is a Divide and Conquer algorithm. It picks an element as pivot
and partitions the given array around the picked pivot. There are many different
versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and
an element x of array as pivot, put x at its correct position in sorted array and put all
smaller elements (smaller than x) before x, and put all greater elements (greater than
x) after x. All this should be done in linear time.
Example:
Conclusion:

EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________

___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge

Experiment No 9.
Aim: Implementation Of Linear And Binary Search
Theory:

For a binary search to work, it is mandatory for the target array to be sorted. We shall
learn the process of binary search with a pictorial example. The following is our
sorted array and let us assume that we need to search the location of value 31 using
binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2

Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.
Now we compare the value stored at location 4, with the value being searched, i.e. 31.
We find that the value at location 4 is 27, which is not a match. As the value is greater
than 27 and we have a sorted array, so we also know that the target value must be in
the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.

low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target
value 31.

The value stored at location 7 is not a match, rather it is more than what we are
looking for. So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a
match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons
to be made to very less numbers.

Conclusion:

EXPERIMENT NO.________

Aim of the Experiment :-

___________________________________________________________
___________________________________________________________

Lab Outcome :-
___________________________________________________________

___________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(03) (04) (10)
(03)

______________________________________

Practical Incharge

Experiment No 10.
Aim: Implementation of Depth First Search and Breadth First Search.

Theory:

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are
sometimes also referred to as vertices and the edges are lines or arcs that connect any
two nodes in the graph. More formally a Graph can be defined as,
Algorithm:

DFS TRAVERSAL

Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push
it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at
the top of stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex
which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one
vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by
removing unused edges from the graph

BFS TRAVERSAL

Step 1 - Define a Queue of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and
insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of
the Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at
front of the Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by
removing unused edges from the graph

Conclusion: