LABORATORY RECORD

for

23IT221 - DATA STRUCTURES AND ALGORITHMS

LABORATORY
of

[Link] –INFORMATION TECHNOLOGY

(AUTONOMOUS REGULATION 2023)
For the Batch (2023 - 27)

Semester: II
Academic Year: 2023-2024

DEPARTMENT OF INFORMATION TECHNOLOGY

KCG COLLEGE OF TECHNOLOGY,
CHENNAI – 600 097
 KARAPAKKAM, CHENNAI 600 097

REG. No. …………………………….

LABORATORY RECORD
Course Code: ………………….

Name of the Course: ……………………………………………………………………………..

It is to certify that this is a bonafide record of the work carried out by

…………………………………………………………………………………………………………………… of

……………….semester………………………………………department, during the odd

semester of the academic year 2023-2024.

Faculty In-charge: …………………………………… HOD…………………………………………….

Int. Examiner: ………………………………………… Ext. Examiner ………………………………..

Date of the Examination: ……………………

 VISION OF THE COLLEGE

KCG College of Technology aspires to become a globally recognized Centre of excellence for science,
technology & engineering education, committed to quality teaching, learning, and research while
ensuring for every student a unique educational experience which will promote leadership, job creation,
social commitment and service to nation building.

MISSION OF THE COLLEGE

• Disseminate knowledge in a rigorous and intellectually stimulating environment

• Facilitate socially responsive research, innovation and entrepreneurship

• Foster holistic development and professional competency

• Nurture the virtue of service and an ethical value system in the young minds

VISION OF THE DEPARTMENT

The department of Information Technology aspires to become a globally acclaimed center of

excellence offering quality education and enabling innovative research in Information Technology
department by producing competent Information Technology graduates to contribute towards nation
building

MISSION OF THE DEPARTMENT

● Impart knowledge of fundamentals as well as emerging trends in Information Technology

● Inculcate innovative and entrepreneurial abilities as well as ethical values among the students

● Establish computing facilities and research activities to enhance the knowledge

● Enhancing competency of faculty with the advanced technologies in Information Technology

 PROGRAMME EDUCATIONAL OBJECTIVES
The graduates of [Link] INFORMATION TECHNOLOGY will

Outstand as technically skilled professionals in Information Technology and relevant

PEO 1 sector.

PEO 2 Devise, Implement and Deploy software solutions for computational problems.
PEO 3 Build software solutions for the challenging problems in industry and research.
PEO4 Manifest the ethical values and exhibit social responsibility.

PROGRAMME OUTCOMES AND PROGRAMME SPECIFIC OUTCOMES

After successful completion of [Link] INFORMATION TECHNOLOGY Programme,
the students will be able to
PO No. Description of the PO
Engineering knowledge: Apply the knowledge of mathematics, science,
engineering fundamentals, and an engineering specialization for the solution of
PO 1
complex engineering problems.
Problem analysis: Identify, formulate, research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
PO 2
mathematics, natural sciences, and engineering sciences.
Design/development of solutions: Design solutions for complex engineering
problems and design system components or processes that meet t h e specified
PO 3
needs with appropriate consideration for public health and safety, and cultural,
societal, and environmental considerations.
Conduct investigations of complex problems: Use research-based knowledge and
PO 4 research methods including design of experiments, analysis and interpretation of
data, and synthesis of the information to provide valid conclusions.
Modern tool usage: Create, select, and apply appropriate techniques, resources, and
PO 5 modern engineering and IT tools, including prediction and modeling to complex
engineering activities, with an understanding of the limitations.
The engineer and society: Apply reasoning informed by the contextual knowledge
PO 6 to assess societal, health, safety, legal and cultural issues and the consequent
responsibilities relevant to the professional engineering practice.
Environment and sustainability: Understand the impact of the professional
PO 7 engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development.
Ethics: Apply ethical principles and commit to professional ethics and
PO 8
responsibilities and norms of the engineering practice.
PO 9 Individual and team work: Function effectively as an individual, and as a
 member or leader in diverse teams, and in multidisciplinary settings.
Communication: Communicate effectively on complex engineering activities with
the engineering community and with the society at large, such as, being able to
PO 10 comprehend and write effective reports and design documentation, make effective
presentations, and give and receive clear instructions.
Project management and finance: Demonstrate knowledge and understanding of t
h e engineering and management principles and apply these to one’s own work, as
PO 11
a member and leader in a team, to manage projects and in multidisciplinary
environments.
Life-long learning: Recognize the need for, and have the preparation and ability to
PO 12 engage in independent and life-long learning in the broadest context of
technological change.

PROGRAMME SPECIFIC OUTCOMES (PSO)

PSO Description of PSO

Design system to solve complex IT related problems using algorithm analysis, database
PSO 1 technology, multimedia, web design, networking and principles of Software
Engineering, to face.
Communicate and function efficiently as an individual and as a member or leader in
PSO 2 multidisciplinary teams in software development process
Identify the need for sustainable development in software industries and follow the
PSO 3 professional code of ethics.

COURSE OUTCOMES
Upon completion of this course, the student will be able to:

CO No Blooms
Description of the Course Outcome
level
Remembering the concept of data structures through ADT including List,
CO 1 K2
Stack and Queues
CO 2 Understand basic concepts about stacks, queues, lists, trees and graphs. K3
Able to apply and implement various tree traversal algorithms and ensure
CO 3 K3
their correctness.
Ability to analyze algorithms and develop algorithms through step-by step
CO 4 K3
approach in solving problems with the help of fundamental data structures.
Design applications and justify use of specific linear and binary data structures
CO 5 K3
for various Applications.

1
 INDEX
Page
S. No. Topics Marks Signature
No
1a Array Implementation of Stack

1b Array Implementation of Queue

2 Array Implementation of List

Linked List Implementation of List

3a
[Singly Linked List]

3b Linked List Implementation of Stack

3c Linked List Implementation of Queue

Applications of List Polynomial Addition And

4a
Subtraction

4b Infix to Postfix

4c Expression Evaluation

5 Implementation of Binary Search Trees

6 Implementation of AVL Trees

7 Implementation of Heap Using Priority Queues

8a Representation Of Graph

8b Graph Traversal-Breadth First Traversal

8c Graph Traversal-Depth First Traversal

9a Linear Search

9b Binary Search

10a Insertion Sort

10b Bubble Sort

2
Ex. No. 1a ARRAY IMPLEMENTATION OF STACK
Date:

Aim: To implement stack operations using array.

Algorithm
1. Start
2. Define a array stack of size max = 5
3. Initialize top = -1
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
7. If top < max -1
8. Increment top
9. Store element at current position of top
10. Else
11. Print Stack overflow
12. If choice = 2 then
13. If top < 0 then
14. Print Stack underflow
15. Else
16. Display current top element
17. Decrement top
18. If choice = 3 then
19. Display stack elements starting from top
20. Stop

Program

3
4
Output

5
Result: Thus push and pop operations of a stack was demonstrated using arrays.
MARKS MAXIMUM MARKS
VIVA QUESTIONS SPLIT UP MARKS OBTAINED

Algorithm 5
1. Define global declaration?
Program 10

Output 5

Total 20
2. Define data types?

3. Define variable with example?

4. What is decision making statement?

5. What are the various decision making statements available in C?

6
Ex. No. 1b ARRAY IMPLEMENTATION OF QUEUE
Date:

Aim: To implement queue operations using array.

Algorithm
1. Start
2. Define a array queue of size max = 5
3. Initialize front = rear = –1
4. Display a menu listing queue operations
5. Accept choice
6. If choice = 1 then
7. If rear < max -1
8. Increment rear
9. Store element at current position of rear
10. Else
11. Print Queue Full
12. If choice = 2 then
13. If front = –1 then
14. Print Queue empty
15. Else
16. Display current front element
17. Increment front
18. If choice = 3 then
19. Display queue elements starting from front to rear.
20. Stop

Program

7
8
Output

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20
Result: Thus insert and delete operations of a queue was demonstrated using arrays.

9
 VIVA QUESTIONS

1. What is a circular queue?

2. Give few examples for data structures?

3. List out Applications of queue

4. How do you test for an empty queue?

5. What are types of Queues?

10
EX. 2 ARRAY IMPLEMENTATION OF LIST
Date:
Aim: To create a list using array and perform operations such as display, insertions and
deletions.

Algorithm
1. Start
2. Define list using an array of size n.
3. First item with subscript or position = 0
4. Display menu on list operation
5. Accept user choice
6. If choice = 1 then
7. Locate node after which insertion is to be done
8. Create an empty location in array after the node by moving the existing elements one
position ahead.
9. Insert the new element at appropriate position
10. Else if choice = 2
11. Get element to be deleted.
12. Locate the position of the element replace the element with the element in the
following position.
13. Repeat the step for successive elements until end of the array.
14. Else
15. Traverse the list from position or subscript 0 to n.
16. Stop

PROGRAM
{

11
12
Output

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Result: Thus the array implementation of Program 10

list was demonstrated.
Output 5

Total 20

13
 VIVA QUESTIONS

1. What is an array?

2. What is a linked list?

3. What is singly linked list?

4. What is a doubly linked list?

5. Define double circularly linked list?

14
EX. 3a LINKED LIST IMPLEMENTATION OF LIST [SINGLY LINKED LIST]
Date:

Aim: To define a singly linked list node and perform operations such as insertions and deletions
dynamically.
Algorithm
1. Start
2. Define single linked list node as self-referential structure
3. Create Head node with label = -1 and next = NULL using
4. Display menu on list operation
5. Accept user choice
6. If choice = 1 then
7. Locate node after which insertion is to be done
8. Create a new node and get data part
9. Insert the new node at appropriate position by manipulating address
10. Else if choice = 2
11. Get node's data to be deleted.
12. Locate the node and delink the node
13. Rearrange the links
14. Else
15. Traverse the list from Head node to node which points to null
16. Stop

Program

15
16
Output:

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED
Result: Thus operation on single linked list is performed.
Algorithm 5

Program 10

Output 5

Total 20

17
VIVA QUESTIONS
1. How to search an element in list.

2. Define Dqueue?

3. How to implement stack using singly linked list

4. What are the types of Linear linked list?

5. What are advantages of Linked lists?

18
Ex. No. 3b LINKED LIST IMPLEMENTATION OF STACK
Date:

Aim: To implement stack operations using linked list.

Algorithm
1. Start
2. Define a singly linked list node for stack
3. Create Head node
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
7. Create a new node with data
8. Make new node point to first node
9. Make head node point to new node
10. If choice = 2 then
11. Make temp node point to first node
12. Make head node point to next of temp node
13. Release memory
14. If choice = 3 then
15. Display stack elements starting from head node till null
16. Stop

Program

19
20
21
Output

Result: Thus push and pop operations of a stack was demonstrated using linked list.

22
 VIVA QUESTIONS

1. What is a Stack?

2. What are the two operations of Stack?

3. How to implement stack using singly linked list

4. What are the types of Linear linked list?

5. What are advantages of Linked lists?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

23
Ex. No. 3c LINKED LIST IMPLEMENTATION OF QUEUE
Date:

Aim: To implement queue operations using linked list.

Algorithm
1. Start
2. Define a singly linked list node for stack
3. Create Head node
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
7. Create a new node with data
8. Make new node point to first node
9. Make head node point to new node
10. If choice = 2 then
11. Make temp node point to first node
12. Make head node point to next of temp node
13. Release memory
14. If choice = 3 then
15. Display stack elements starting from head node till null
16. Stop

Program

24
25
26
Output

Result: Thus push and pop operations of a stack was demonstrated using linked list.

27
 VIVA QUESTIONS
1. Write down the operations that can be done with queue data structure?

2. What is a circular queue?

3. Give few examples for data structures?

4. List out Applications of queue

5. How do you test for an empty queue?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

28
Ex. No. 4a APPLICATIONS OF LIST
POLYNOMIAL ADDITION AND SUBTRACTION
Date:

Aim: To store a polynomial using linked list. Also, perform addition and subtraction on two
polynomials.

Algorithm
Let p and q be the two polynomials represented by linked lists
1. while p and q are not null, repeat step 2.
2. If powers of the two terms are equal
then If the terms do not cancel then
Insert the sum of the terms into the sum Polynomial
Advance p Advance q
Else if the power of the first polynomial> power of second Then
Insert the term from first polynomial into sum polynomial
Advance p
Else
insert the term from second polynomial into sum polynomial Advance q
3. Copy the remaining terms from the non empty polynomial into the sum polynomial.
The third step of the algorithm is to be processed till the end of the polynomials has not been
reached.

Program

29
30
;

31
32
Output

Result: Thus application of list for polynomial manipulation was demonstrated.

33
VIVA QUESTIONS
1. Define double circularly linked list?

2. What is the need for the header?

3. Define Polynomial ADT

4. How to search an element in list.

5. How to implement stack using singly linked list

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

34
Ex. No. 4b INFIX TO POSTFIX
Date:

Aim: To convert infix expression to its postfix form using stack operations.

Algorithm
1. Start
2. Define a array stack of size max = 20
3. Initialize top = -1
4. Read the infix expression character-by-character
5. If character is an operand print it
6. If character is an operator
7. Compare the operator‟s priority with the stack[top] operator.
8. If the stack [top] operator has higher or equal priority than the inputoperator,
Pop it from the stack and print it.
9. Else
10. Push the input operator onto the stack
11. If character is a left parenthesis, then push it onto the stack.
12. If the character is a right parenthesis, pop all the operators from the stack andprint it
until a left parenthesis is encountered. Do not print the parenthesis.

Program

35
36
37
Output

Result: Thus the given infix expression was converted into postfix form using stack.

38
Viva Questions

1. What are the different ways to implement list?

2. What are the postfix and prefix forms of the expression?

3. Explain the usage of stack in recursive algorithm implementation?

4. Write down the operations that can be done with queue data structure?

5. What is a circular queue?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

39
Ex. No. 4c EXPRESSION EVALUATION
Date:

Aim: To evaluate the given postfix expression using stack operations.

Algorithm
1. Start
2. Define a array stack of size max = 20
3. Initialize top = -1
4. Read the postfix expression character-by-character
5. If character is an operand push it onto the stack
6. If character is an operator
7. Pop topmost two elements from stack.
8. Apply operator on the elements and push the result onto the stack,
Eventually only result will be in the stack at end of the
expression.
9. Pop the result and print it.

Program

40
41
Output

Result: Thus the given postfix expression was evaluated using stack.

42
 VIVA QUESTIONS

1. What is a Priority Queue?

2. What are the different ways to implement list?

3. What are the postfix and prefix forms of the expression?

4. Explain the usage of stack in recursive algorithm implementation?

5. Write down the operations that can be done with queue data structure?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

43
Ex No. 5 IMPLEMENTATION BINARY SEARCH TREE
Date:

Aim:To construct a binary search tree and perform search.

Algorithm
1. Start
2. Call insert to insert an element into binary search tree.
3. Call delete to delete an element from binary search tree.
4. Call findmax to find the element with maximum value in binary search tree
5. Call findmin to find the element with minimum value in binary search tree
6. Call find to check the presence of the element in the binary search tree
7. Call display to display the elements of the binary search tree
8. Call makeempty to delete the entire tree.
9. Stop
Insert function
1. Get the element to be inserted.
2. Find the position in the tree where the element to be inserted by
checking the elements in the tree by traversing from the root.
3. If the element to be inserted is less than the element in the current node in
the tree then traverse left subtree
4. If the element to be inserted is greater than the element in the current node
in the tree then traverse right subtree
5. Insert the element if there is no further move
Delete function
1. Get the element to be deleted.
2. Find the node in the tree that contain the element.
3. Delete the node an rearrange the left and right siblings if any present for the
deleted node
Findmax function
1. Traverse the tree from the root.
2. Find the rightmost leaf node of the entire tree and return it
3. If the tree is empty return null.
Findmin function
1. Traverse the tree from the root.
2. Find the leftmost leaf node of the entire tree and return it
3. If the tree is empty return null.
Find function
1. Traverse the tree from the root.
2. Check whether the element to searched matches with element of the current
node. If match occurs return it.
3. Otherwise if the element is less than that of the element of the current node
then search the leaf subtree
4. Else search right subtree.
Makeempty function
Make the root of the tree to point to null.

44
Program

45
46
47
48
49
Output:

Result:
The program for binary search tree is executed and verified.

50
 VIVA QUESTIONS

1. Write down the algorithm for solving Towers of Hanoi problem?

2. What is a Stack ?

3. What are the two operations of Stack?

4. What is a Queue ?

5. What is a Priority Queue?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

51
Ex. No.6 IMPLEMENTATION OF AVL TREES
Date:

Aim: To implement AVL Trees.

Algorithm

A binary search tree x is called an AVL tree,

1. b([Link]) ∈ {−1, 0, 1}, and

if:

2. [Link] and [Link] are both AVL trees. = the height balance of every
node must be -1, 0, or 1

insert/delete via standard algorithms

• after insert/delete: load balance b(node) might be changed to +2 or −2 for certain nodes
• re-balance load after each step

Insert operation may cause balance factor to become 2 or –2 for some node
› only nodes on the path from insertion point to root node have possibly changed in height
› So after the Insert, go back up to the root node by node, updating heights
› If a new balance factor (the difference hleft – hright ) is 2 or –2, adjust tree by rotation
around the node
Let the node that needs rebalancing be α.
There are 4 cases:
Outside Cases (require single rotation) :
1. Insertion into left subtree of left child of α.
2. Insertion into right subtree of right child of
α. Inside Cases (require double rotation) :
3. Insertion into right subtree of left child of α.
4. Insertion into left subtree of right child of α.
The rebalancing is performed through four separate rotation algorithms.
You can either keep the height or just the difference in height, i.e. the balance factor; this
has to be modified on the path of insertion even if you don‟t perform rotations
Once you have performed a rotation (single or double) you won‟t need to go back up
the tree
SINGLE ROTATION
RotateFromRight(n : reference node pointer)
{
p : node pointer;
p := [Link];
[Link] := [Link];
[Link] := n;
n := p
}
You also need to modify the heights or balance factors of n and p

52
DOUBLE ROTATION
DoubleRotateFromRight(n : reference node pointer)
{
RotateFromLeft([Link]);
RotateFromRight(n);
}

INSERTION IN AVL TREES

Insert(T : tree pointer, x : element) :
{
if T = null then
T := new tree; [Link] := x; height := 0;
case
[Link] = x : return ; //Duplicate do nothing
[Link] > x : return Insert([Link], x);
if ((height([Link])- height([Link])) = 2){
if ([Link] > x ) then //outside case
T = RotatefromLeft (T);
else //inside case
T = DoubleRotatefromLeft (T);}
[Link] < x : return Insert([Link], x);
code similar to the left case
Endcase
[Link] := max(height([Link]),height([Link])) +1;
return;
}

DELETION
Similar but more complex than insertion
› Rotations and double rotations needed to rebalance
› Imbalance may propagate upward so that many rotations may be needed.

Program

53
54
55
OUTPUT

Result: Thus the implementation of AVL tree was demonstrated.

56
 VIVA QUESTIONS

1. What is an AVL tree?

2. Can you explain the basic structure of an AVL tree?

3. Is it possible to insert multiple nodes into an AVL tree at once? If yes, then how?

4. How can you determine whether an AVL tree is height-balanced or not?

5. Is it possible to retrieve the smallest element in an AVL tree? If yes, then how?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

57
 Ex. No.7 IMPLEMENTATION OF HEAP USING PRIORITY QUEUES
Date:

Aim To Implementation Of Heap Using Priority Queues.

Algorithm

 Priority queue is a type of queue in which every element has a key associated to it
and the queue returns the element according to these keys, unlike the traditional
queue which works on first come first serve basis.

 Thus, a max-priority queue returns the element with maximum key first whereas, a
min-priority queue returns the element with the smallest key first.

max-priority queue and min-priority queue

 Priority queues are used in many algorithms like Huffman Codes, Prim's algorithm,
etc. It is also used in scheduling processes for a computer, etc.

 Heaps are great for implementing a priority queue because of the largest and
smallest element at the root of the tree for a max-heap and a min- heap respectively.
We use a max-heap for a max-priority queue and a min-heap for a min-priority
queue.

There are mainly 4 operations we want from a priority queue:

1. Insert → To insert a new element in the queue.

2. Maximum/Minimum → To get the maximum and the minimum element from the
max-priority queue and min-priority queue respectively.

3. Extract Maximum/Minimum → To remove and return the maximum and the

minimum element from the max-priority queue and min-priority queue respectively.

4. Increase/Decrease key → To increase or decrease key of any element in the queue.

 A priority queue stores its data in a specific order according to the keys of the
elements. So, inserting a new data must go in a place according to the specified order.
This is what the insert operation does.
 The entire point of the priority queue is to get the data according to the key of the
data and the Maximum/Minimum and Extract Maximum/Minimum does this for
us.
 We know that the maximum (or minimum) element of a priority queue is at the root
of the max-heap (or min-heap). So, we just need to return the element at the root of
the heap.

 This is like the pop of a queue, we return the element as well as delete it from the
heap. So, we have to return and delete the root of a heap. Firstly, we store the value
of the root in a variable to return it later from the function and then we just make the
root equal to the last element of the heap. Now the root is equal to the last element of
the heap, we delete the last element easily by reducing the size of the heap by 1.

58
  Doing this, we have disturbed the heap property of the root but we have not
touched any of its children, so they are still heaps. So, we can
call Heapify on the root to make the tree a heap again.

EXTRACT-MAXIMUM(A)

max = A[1] // stroing maximum value

A[1] = A[heap_size] // making root equal to the last

element heap_size = heap_size-1 // delete last element

MAX-HEAPIFY(A, 1) // root is not following max-heap property

return max //returning the maximum value

Program

59
60
61
OUTPUT

RESULT:
Thus the implementation heap using priority queue was demonstrated.

62
 VIVA QUESTIONS

1. Write down the operations that can be done with queue data structure?

2. What is a circular queue?

3. Give few examples for data structures?

4. List out Applications of queue

5. How do you test for an empty queue?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

63
 Ex. No. 8a REPRESENTATION OF GRAPH
Date:

Aim To represent graph using adjacency list.

Algorithm

 For a graph with |V| vertices, an adjacency matrix is a |V|×∣V∣ matrix of 0s and
1s, where the entry in row i and column j is 1 if and only if the edge (i,j) in the
graph.
1. Consider the graph to be represented
2. Start from an edge
3. If the edge connects the vertices i,j the mark the ith row and jth column of the
adjacency matrix as 1 otherwise store 0
4. Finally print the adjacency matrix

Program

64
65
OUTPUT

Result : Thus the implementation of graph representation was demonstrated.

66
 VIVA QUESTIONS

1. What is graph in data structure interview questions?

2. How to approach graph interview questions?

3. How can I get better at answering graph interview questions?

4. Terminology and Representations of Graphs

5. What is a Graph?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

67
 Ex. No. 8b GRAPH TRAVERSAL-BREADTH FIRST TRAVERSAL
Date:

Aim To implement breadth first graph traversal.

Algorithm
BFS (G, s) //Where G is the graph and s is the source
node let Q be queue.
[Link]( s ) //Inserting s in queue until all its neighbour vertices are marked.

mark s as visited.
while ( Q is not
empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = [Link]( )

//processing all the neighbours of v

for all neighbours w of v in Graph
G
if w is not visited
[Link]( w ) //Stores w in Q to further visit its

Program

68
69
70
 Output

MARKS MAXIMUM MARKS

Result : Thus the graph using breadth first search
SPLIT UP MARKS OBTAINED
traversal was demonstrated.
Algorithm 5
VIVA QUESTIONS
Program 10
1. What is Breadth-First Search (BFS)?
Output 5

Total 20

2. Breadth First Search (BFS) | Iterative & Recursive Implementation

3. Find shortest path from source to destination in a matrix that satisfies given constraints

4. Traverse given directory using BFS and DFS in C

5. Find the shortest safe route in a field with sensors present

71
 Ex. No. 8c GRAPH TRAVERSAL-DEPTH FIRST TRAVERSAL
Date:

Aim To implement Depth first graph traversal.

Algorithm

DFS-iterative (G, s): let S be stack [Link](//Where

s) G is graph and s is source vertex
mark s as visited.
//Inserting s in stack

while ( S is not empty):

//Pop a vertex from stack to visit next v = [Link]( )
[Link]( )
//Push all the neighbours of v in stack that are not visited for all neighbours w of v in Graph G:
if w is not visited :
[Link]( w ) mark w as visited

DFS-recursive(G, s): mark s as visited

for all neighbours w of s in Graph G: if w is not visited:
DFS-recursive(G, w)

Program

72
73
 OUTPUT:

Result : Thus the graph using depth first search traversal was demonstrated.

VIVA QUESTIONS MARKS MAXIMUM MARKS

1. Define DFS SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10
2. Transitive closure of a graph using DFS
Output 5

Total 20
3. Application of DFS

4. Detect cycle in an undirected graph

5. Longest path between any pair of vertices

74
 Ex. No. 9a LINEAR SEARCH
Date:

AimTo perform linear search of an element on the given array.

Algorithm
1. Start
2. Read number of array elements n
3. Read array elements Ai, i = 0,1,2,…n–1
4. Read search value
5. Assign 0 to found
6. Check each array element against search
7. If Ai = search
then found = 1
Print "Element found"
Print position i
Stop
8. If found = 0 then
print "Element not found"
Stop

Program

75
76
 Output

Result
Thus an array was linearly searched for an element's existence.
MARKS MAXIMUM MARKS
VIVA Questions:
SPLIT UP MARKS OBTAINED
1. What is meant by Sorting and searching? Algorithm 5

Program 10

2. What are the types of sorting available in C? Output 5

Total 20

3. Mention the various types of searching techniques in C

4. What is linear search?

5. What is binary search

77
Ex. No. 9b BINARY SEARCH
Date:

Aim
To locate an element in a sorted array using Binary search method

Algorithm
1. Start
2. Read number of array elements, say n
3. Create an array arr consisting n sorted elements
4. Get element, say key to be located
5. Assign 0 to lower and n to upper
6. While (lower < upper)
a. Determine middle element mid = (upper+lower)/2
b. If key = arr[mid] then
i. Print mid
ii. Stop
c. Else if key > arr[mid] then
i. lower = mid + 1
d. else
i. upper = mid – 1
7. Print "Element not found"
8. Stop
Program

78
79
 Output

Result
Thus an element is located quickly using binary search method.

VIVA Question

1. What is meant by Sorting and searching?

2. What are the types of sorting available in C?

3. Mention the various types of searching techniques in C

4. What is linear search?

5. What is binary search

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

80
Ex. No. 10a INSERTION SORT
Date:

Aim:To sort an array of N numbers using Insertion sort.

Algorithm
1. Start
2. Read number of array elements n
3. Read array elements Ai
4. Outer index i varies from second element to last element
5. Inner index j is used to compare elements to left of outer index
6. Insert the element into the appropriate position.
7. Display the array elements after each pass
8. Display the sorted array elements.
9. Stop

Program

81
82
 Output

Result:Thus array elements was sorted using insertion sort.

MARKS MAXIMUM MARKS
VIVA Question
SPLIT UP MARKS OBTAINED
1. Define merge sort? Algorithm 5

Program 10

2. Define insertion sort? Output 5

Total 20

3. Define selection sort?

4. What is the basic idea of shell sort?

5. What is the purpose of quick sort and advantage?

83
 Ex. No. 10b BUBBLE SORT
Date:

Aim:To sort an array of N numbers using Bubble sort.

Algorithm
1. Start
2. Read number of array elements n
3. Read array elements Ai
4. Outer Index i varies from last element to first element
a. Index j varies from first element to i-1
i. Compare elements Aj and Aj+1
ii. If out-of-order then swap the elements
iii. Display array elements after each pass
iv. Display the final sorted list
5. Stop

Program

84
Output

Result
Thus an array was sorted using bubble sort.

85
VIVA Questions
1. Define selection sort?

2. What is the basic idea of shell sort?

3. What is the purpose of quick sort and advantage?

4. Define quick sort?

5. Advantage of quick sort?

MARKS MAXIMUM MARKS

SPLIT UP MARKS OBTAINED

Algorithm 5

Program 10

Output 5

Total 20

86