CS3401-ALGORITHMS

DEPARTMENT OF COMPUTER SCIENCE

&
ENGINEERING

KANYAKUMARI DISTRICT - 629 302.

 Register No:

Certified that, this is the bonafide record of work done by

Mr/Ms.……………………………………………………….... of VI Semester
Computer Science and Engineering of this college, in the CS3401-
ALGORITHMS during 2023-2024(Even) in partial fulfillment of the
requirements of the B.E. Degree course of the Anna University,
Chennai.

Staff-in-charge. Head of the Department.

This record is submitted for the University Practical Examination

held on…………………………..

Internal Examiner. External Examiner

 DO’S DON’T’S

1. Be regular to the lab. 1. Do not take leave on lab days.

2. Follow proper dress code. 2. Do not eat or drink inthe laboratory.
3. Know the location of the fire 3. Avoid stepping on electrical
extinguisher and the first aid box andhow wires or any other computer
to use them in case of an emergency. cables.

4. Read and understand how to carry out an 4. Do not open the system unit casing
activity thoroughly before coming to the or monitor casing particularly

laboratory. when the power is turned on.

Some internal components hold
5. Report fires or accidents to your faculty
electric voltages of up to 30000
members/laboratory technician immediately.
volts, which can be fatal.
6. Report any broken plugs or exposed
5. Do not insert metal objects such as
electrical wires to your faculty
clips, pins and needles into the
members/laboratory technician immediately.
computer casings. They may cause
7. Maintain Silence.
fire.
6. Do not remove anything from the
computer laboratory without
permission.
7. Do not touch, connect or disconnect
any plug or cable without your
faculty members/laboratory
technician’s permission.
 Vision of the Institute Mission of the Institute
Empowering the rural and less privileged IM 1. To enlighten the rural students.
students with value based technical knowledge, IM 2. To provide quality technical education of
forming them as responsible citizens. societal development and entrepreneurship
IM 3. To instill interpersonal skills and shape
the students to become good leaders to serve
the society.

Vision of the Department Mission of the Department

To be a reputed center producing socially M1: To build Computer Engineers with
committed Computer Engineers with leadership professional ethics and entrepreneurship skills.
qualities to serve the rural society. M2: To inculcate problem solving and team
. building skills to promote lifelong learning with
the sense of social responsibilities.
M3: To produce effective Computer Engineers
with exposure to current industrial
advancements through higher education and
serve the common people through their
expertise.
 Program Educational Objectives (PEOs)
1. PROFESSIONAL CAREER: The graduates will be able to pursue higher education and
research to have a successful career in Computer Science industries or as entrepreneurs.
2. LEADERSHIP QUALITIES AND TEAM SPIRIT: The graduates will be able to perform
efficiently while working in teams.
3. LIFE LONG LEARNING: The graduates will be empowered through emerging technical

Knowledge and inspired with life-long learning to serve the society.

Program Outcomes (POs)

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.

PROGRAM SPECIFIC OBJECTIVES (PSOs)

PSO 1: To analyze, design and develop computing solutions by applying foundational

concepts of Computer Science and Engineering.
PSO 2: To apply software engineering principles and practices for developingquality
software for scientific and business applications.
PSO 3: To adapt to emerging Information and Communication Technologies (ICT) to
innovate ideas and solutions to existing/novel problem

Course Outcomes (COs)

COs COURSE OUTCOME C LEVEL

CO1 Implement various Searching and Sorting Algorithms K3
CO2 Implement graph algorithms to solve problems K3
Implement algorithm design techniques like divide and conquer, dynamic
CO3 K3
programming and greedy techniques to solve problems
CO4 Implement state space tree algorithm for solving problems. K3
CO5 Implement approximation algorithms and randomized algorithms K3
 INDEX

PAGE
S.NO DATE TOPIC NO. SIGNATURE

1 IMPLEMENTATION OF LINEAR SEARCH

IMPLEMENT RECURSIVE BINARY

2 SEARCH. DETERMINE THETIME
REQUIRED TO SEARCH AN ELEMENT
3 FUNCTION SEARCH
4.a INSERTION SORT
4.b HEAP SORT
5.a BREADTH FIRST SEARCH
5.b DEPTH FIRST SEARCH

6.a DIJKSTRA’S ALGORITHM

6.b PRIMS’S ALGORITHM

7.a FLOYD’S ALGORITHM

7.b WARSHALL’S ALGORITHM

8 DIVIDE AND CONQUER TECHNIQUE

9.a MERGE SORT

9.b QUICK SORT

N-QUEENS PROBLEM USING
10.a
BACKTRACKING

10.b TRAVELLING SALESPERSON PROBLEM

IMPLEMENT RANDOMIZED ALGORITHMS

11 FOR FINDING THE KTH SMALLEST
NUMBER

Content Beyond the Syllabus

GRAPH COLORING ALGORITHM USING

12
BACKTRACKING IN C
 EXP.NO: 1

IMPLEMENTATION OF LINEAR SEARCH

DATE:

AIM:
To write a C program for “implementation of linear search”.

ALGORITHM:
1. Start the program

2. Initialize the required variables

3. Declare the position

4. Get the input from the user

5. Enter the search elements

6. If the element is found print”element is found”

7. Give the input from the time taken cpu cycles

8. Display the result

9. Stop the program

PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>#defi
ne max 20

int pos;

Int Linearsearch(int,int[],int);

void main()
{
int ch=1;
double t;
int n,i,k,op,pos,a[20]; Clock_t
begin,end; Clrscr();
While(ch)
{
Printf(“\n….MENU……\n1.Linearsearch\n2.Exit\n”);

Printf(“\n enter your choice\n”);

Scanf(“%d”,&op);
Switch(op)
{
Case 1:
Printf(“\n enter the number of elements\n”);

Scanf(“%d”,&n);

Printf(“\n enter the elements of an array\n”);

for(i=0;i<n;i++)

Scanf(“%d”,&a[i]);

Printf(“\n enter the element to be searched\n”);

Scanf(“%d”,&k);
begin=clock();
 pos=Linearsearch(n,a,k);
end=clock();

if(pos==-1)
printf(“\n\n unsuccessful search”);

else
printf(“element %d is found at position %d”,k,pos+1);
printf(“\n Time taken is %if CPU cycles\n”,(end_begin)/CLK_TCK); getch();
break;
default:

printf(“Invalid choice entered\n”);

exit(0);

}
Printf(“\n Do you wish to run again(1/0)\n”);

Scanf(“%d”,&ch);
}
getch();
}
int Linearsearch(int n,int a[],int k)
{
delay(1000); If(n<0)
return -1;
if(k==a[n-1])
return(n-1); else
return Linearsearch(n-1,a,k);
}

OUTPUT:
….MENU….
1.Linearsearch 2.Exit
Enter your choice : 1 Enter
the number of elements3
Enter the number of an array in the
order25 69 98 Enter
the elements to be searched98
 Element 98 is found at position3
Time taken is 1.978022CPU cycles

Value of n Time

3 1.978022

4 2.032967

6 3.956044

8 1.978022

10 3.021978

12 8.956044

14 10.12345

15

10

Value of n Time

Linearsearch

RESULT:
Thus the C program “Implementation of Linear search” has been executed successfully.
 EX:NO:2
IMPLEMENT RECURSIVE BINARY SEARCH. DETERMINE THE TIME
DATE: REQUIRED TO SEARCH AN ELEMENT.

AIM:
To implement a recursive binary search program and determine the time required to search an element.

ALGORITHM:
1. start the program.
2. Set the low index to the first element of the array and the high index to the lastelement.
3. Set the middle index to the average of the low and high indices.
a. If the element at the middle index is the target element, return the middleindex.
b. Otherwise, based on the value of the key to be found and the value of themiddle
element, decide the next search space.
i. If the target is less than the element at the middle index, set the highindex to
middleindex – 1.
ii. If the target is greater than the element at the middle index, set the lowindex to
middleindex + 1.
4. Perform step 2 repeatedly until the target element is found or the search space is
exhausted.
5. And also calculate the time complexity.
6. Stop the program.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
#define MAX 20
int pos;
int binsearch(int,int[],int,int,int);
void main()
{
int ch=1;
double t;
int n,i,a[20],e,low,high,pos;
clock_tbegin,end;
clrscr();
printf("Enter The Size Of The Array:");
scanf("%d",&n);
printf("Enter The Elements Of the Array:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Enter The Element To Search");
scanf("%d",&e);
low=0;
high=n-1;
begin=clock();
pos=binsearch(n,a,e,low,high);
end=clock();
pos=binsearch(n,a,e,low,high);
end=clock();
if(pos==-1)
printf("Unsuccessfull Search");
else
printf("Element %d found at pos %d",e,pos+1);
printf("\ntime taken is %f if cpu1 cycles",(end-begin)/CLK_TCK);
getch();
}
int binsearch(int n,int a[],int e,int low,int high)
{
int mid;
delay(1000);
mid=(low+high)/ 2;
if(low>high)
Return -1;
if(e==a[mid])
return(mid);
 else
if(e<a[mid])
return binsearch(n,a,e,low,mid- 1);
else
return binsearch(n,a,e,mid+1,high);
}

OUTPUT:

Enter the size of the array:34

Enter the elements of the array:1

Enter the elements to

search:1Element 1 is found at 0

Time take is 1.944 CPU cycle

 Value of n Time
(t)

1 1.944

2 2.967

3 0.989

4 3.021

RESULT:
The c program to implement the recursive binary search has been executed successfully.
 EXP.NO: 3
FUNCTION SEARCH

DATE:

AIM:
The Aim of this function is to search for all occurrences of a given pattern within
given text and print the indices where the pattern is found

ALGORITHM:

Step 1: Start

Step 2: Loop through the text from index 0 to n-m, where n is the length of the text and m is the
length of the pattern.

Step 3: For each iteration, check if the substring of text from the current index to current index
+pattern length is equal to the pattern.

Step 4 : If there's a match, print the index where the pattern is found.

Step 5: Continue looping until all occurrences of the pattern in the text are found
PROGRAM:

#include<stdio.h>
#include<string.>
#include<time.h>
#include<conio.h>
#include<stdlib.h>
#include<ctype.h>

void search(char pat[],char txt[])

{
int i,j;
int m = strlen(pat);
int n = strlen(txt);
int count = 0; //To keep track of the number of occurrences

//Iterate through the text

for(int i=0;i<=n- m;i++)

{
int j;

//Check if the current substring matches the pattern

for(j=0;j<m;j++)
{
if(txt[i+j] != pat[j])
{
Break;
}
}
if(j==m)
{
//If the pattern is found, print index and increment the count
printf("Pattern found at index %d\n", i);
count++;
}
}
if(count==0)
{
 //If no occurrence found,print a message
printf("Pattern not found in text.\n");
}

else
{ //Print the total count of occurrence
printf("Total occurenes : %d\n",count);

}
}
int main()
{
char txt[]="AABAACAADAABAAABAA";
char pat[]="AABA"; printf("Text: %s\n",txt);
printf("Pattern:%s\n",pat); printf("Occurences:\n");
search(pat,txt);
printf("Time Complexity:O(56)");
getch();

OUTPUT:
 Text: AABAACAADAABAAABAA
Pattern:
AABA
Occurrences:
Pattern found at index
0Pattern found at index
9Pattern found at index 13
Total occurrences: 3 Time
complexity:O(56)

RESULT:

The Function Search() Takes a Pattern and a Text as Input and Searches For all Occurrences of The
Pattern in The Text. It Then Prints the Indices Where The Patternis Found. In the Example Usage,
The Pattern "ABAB" is Found at Indices 0 and 10 inThe Text "ABABDABACDABABCABAB"
 EXP.NO: 4(a)
INSERTION SORT

DATE:

AIM:
To write a C program to sort the elements using insertion sort and plot a graph for the time taken.

ALGORITHM :
1. Start
2. Declare the variables.
3. Get the value of n from the user.

4. 4.Get the elements using for loop

5. Call the insertion() function and sort the elements .
6. Print the sorted array and also print the time taken to sort the elements.

7. 7.Stop
PROGRAM:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void insertion(int a[],int n)
{

int i,key,j;

for(i=1;i<n;i++)
{
key=a[i];
j=i-1;
while(j>=0&&a[j]>key)

{
a[j+1]=a[j
];j=j-1;
}
a[j+1]=key;
}
}
int main()
{
int a[50],i,n;
clock_t t;
double time;
t=clock();
printf("enter n\n ");
scanf("%d",&n);
printf("enter elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
insertion(a,n);
t=clock()-t;
printf("sorted elements\n ");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
time=((double)t)/CLOCKS_PER_SE C;
printf("time taken %f sec",time);
return 0;
}
OUTPUT:
Enter n3
Enter
elements122 34
2
Sorted
elements2 34
122
Time taken 11.098901 sec

GRAPH:

20
18
16
14
12
10 Series1
Series2

1 2 3 4 5 6

RESULT:

Thus the program for insertion sort has been executed successfully along with the

time complexity graph.

 EXP.NO: 4(b)
HEAP SORT

DATE:

AIM:
To write a c program to sort a set of elements using heap sort and plot a graph of the time taken .

ALGORITHM:
1. start the program
2. declare the variables and functions.
3. get the value of n and elements of the array.
4. using the heapify() function find the larger value and sort them by using
heapsort() function.
5. display the sorted elements and time taken in seconds.
6. stop the program.
PROGRAM:
#include<stdio.h> #include<time.h>

Void heapify(int*,int,int);

Void heapsort(int *,int);

Void print_array(int*,int);

int main()
{
int n,i,a[50]; clock_t t;
double time; t=clock();
printf("enter the value of n\n");
scanf("%d,&n);
printf("\n enter elements\n");
for(i=0;i<n;i++)
{
scanf("\n %d",&a[i]);
}
heapsort(a,n);
printf("\n\n after sorting\n"); for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
t=clock()-t; time=((double)t)/CLOCK_PER_SE C;
printf("time taken is %f",time);
return 0;
}
void heapsort(int * a,int n)
{
int i;
for(i=n-1;i>=0;i--)
{
heapify(a,n,i);
}
for(i=n-1;i>=0;i--)
{
int temp=a[i];
a[i]=a[0]; a[0]=temp;
heapify(a,i,0);
}
void heapify(int*a,int n,int i)
{
int large=i;
int left=2*i+1; int
right=2*i+2;
if(left<n&&a[left]>a[large])
{
large=left;
}
if(right<n&&a[right]>a[large])
{
large=right;
}
if(large!=i)
{
int temp=a[i];
a[i]=a[large];
a[large]=temp;
heapify(a,n,large);
}
}
void print_array(int *a,int n)
{
int i; for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
OUTPUT:
Enter n:5
Enter
element2
345
2
3
67
After sort:
2
3
23
45
67
Time taken:11.703297sec

GRAPH:

20
18
16
14
12
10 Series1
Series2

1 2 3 4 5 6

RESULT:
Thus the program for heap sort has been executed successfully along with the time complexity graph.
 EX. NO : 5(a)
BREADTH FIRST SEARCH
DATE:

AIM:
To develop a program to implement graph traversal using breadth first search.

ALGORITHM :
1. Start by putting any one of the graph's vertices at the back of a queue.

2. Take the front item of the queue and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited

list to the back of the queue.

4. Keep repeating steps 2 and 3 until the queue is empty.

5. Note : The graph might have two different disconnected parts so to make sure

that we cover every vertex, we can also run the BFS algorithm on every node

PROGRAM:

#include<stdio.h>
#include<conio.h>
int [20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
for (i=1;i<=n;i++)
if(a[v][i] &&!visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main ( )
{
int v;
clrscr();
 printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v); bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
else
printf("\n Bfs is not possible");
getch();
}
OUTPUT:

Enter the number of vertices:3 Enter

graph data in matrix form:
010
101
011
Enter the starting vertex:1
The node which are reachable are:
1 2 3

RESULT:

Thus to develop a program to implement a graph traversal using breadth first

search has been executed successfully.

 EX. NO : 5(b)
DEPTH FIRST SEARCH
DATE:

AIM:

To develop a program to implement graph traversal using depth first search.

ALGORITHM:
1. Start by putting any one of the graph's vertices on top of a stack.
2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of the stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

PROGRAM:

#include<stdio.h>
#include<conio.h>
int a[20] [20] , reach[20] , n;
void dfs(int v)
{
int i; reach[v]=1;
for (i=1;i<=n;i++)
if(a[v][i] &&!reach[i])
{
printf("\n %d->%d",v,i);
dfs(i);
}
}
void main( )
{
int i,j,count=0;
clrscr();
printf("\n Enter number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
reach[i]=0;
for (j=1;j<=n;j++)
 a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for (i=1;i<=n;i++)
{
if(reach[i])
count++;
}
if(count==n)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
getch();
}

OUTPUT:

Enter number of vertices: 3Enter

the adjacency matrix:
011
101
110
1->2
2->3

Graph is connected

RESULT:

Thus to develop a program to implement graph traversal using depth first search hasbeen executed
successfully.
 EX. NO : 6(a)
DIJKSTRA’S ALGORITHM
DATE:

AIM:

To develop a program for shortest paths to other vertices using Dijkstra's algorithm.

ALGORITHM:

1. Create a set short-path to store vertices that come in the way of the shortest
path tree.
2. Initialize all distance values INFINITE and assign distance values as 0 for source vertex so
that it is picked first.
3. Loop until all vertices of the graph are in the short-path.
4. Take a new vertex that is not visited and is nearest.
5. Add this vertex to short-path .
6. For all adjacent vertices of this vertex update distance. Now check every adjacent vertex of
V, if sum of distance of u and weight of edge is less the update it.

PROGRAM:

#include<conio.> #include<limits.>
#include <stdbool.h>
#include<stdio.h>
#define V 9

int minDistance(int dist[], bool sptSet[])

{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min =dist[v], min_index = v;

return min_index;

}
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n"); for (int i=
0; i < V; i++)

printf("%d \t\t\t\t %d\n", i, dist[i]);

}
 void dijkstra(int graph[V][V], int src)

int dist[V];

boolsptSet[V]:

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;

for (int count = 0; count < V - 1; count++)

int u = minDistance(dist, sptSet);

sptSet[u]= true;

for (int v = 0; v < V; v++)

if(!sptSet[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]<dist[v])

dist[v] = dist[u] + graph[u][v];

printSolution(dist);

int main()

{
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },

{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },

{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
 dijkstra(graph, 0);

getch();

return 0;

GRAPH:

OUTPUT:

RESULT:

Thus the program for develop the shortest paths to other vertices Using dijkstra’s algorithm has been
executed successfully.
 EX. NO : 6(b)
PRIMS’S ALGORITHM
DATE:

AIM

To write the program for minimum cost spanning tree of a given undirected graph using
prims algorithm.

ALGORITHM:

1. Determine an arbitrary vertex as the starting vertex of the MST.

2. Follow steps 3 to 5 till there are vertices that are not included in the
MST(known as fringe vertex).
3. Find edges connecting any tree vertex with the fringe vertices.
4. Find the minimum among these edges.
5. Add the chosen edge to the MST if it does not from any cycle.
6. Return the MST and exit.

PROGRAM:
#include <stdio.h>
#include<conio.h>
#include<limits.h>
#include<stdbool.h>
#define V 5

int minKey(int key[], bool mstSet[])

{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min =key[v], min_index = v;
return min_index;
}

int printMST(int parent[], int graph[V][V])

{
printf("Edge \tWeight\n");
for(int i = 1; i< V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int pare nt[V];

int key[ V];

bool mstS et[V];

for (int i = 0; i < V; i++)

key[i] = INT_MAX,mstSet[i] = false;

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++)

{
int u=minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] &&mstSet[v] == false&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

primMST(graph);
getch();
return0;}
GRAPH:

OUTPUT:

RESULT:
Thus the program for find the minimum cost spanning tree using prim’s algorithm has been executed
successfully.
EX.NO:7(A)
FLOYD’S ALGORITHM
DATE:

Aim:

To implement floyd’s Algorithm for all pairs shortest path problem

Algorithm:

1. Start the program

2. Initialize the solution matrix same as the input graph matrix as a first step.
3. Then update the solution matrix by considering all vertices as an intermediate vertex.
4. The idea is to one by one pick all vertices and updates all shortest paths which include the picked
vertex as an intermediate vertex in the shortest path.
5. When we pick vertex number k as an intermediate vertex, we already have considered
vertices {0, 1, 2, .. k-1} as intermediate vertices.
6. For every pair (I, j) of the source and destination vertices respectively, there are two possible
cases.
7. K is not an intermediate vertex in shortest path from I to j. We keep the value of dist[i][j] as it is.
8. K is an intermediate vertex in shortest path from I to j. We update the value of dist[i][j] as
dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]
9. Display the result
10. Exit
PROGRAM:
#include <stdlib.h>
void floydWarshall(int **graph, int n)
{
int i, j, k;
for (k = 0; k < n; k++)
{

for (i= 0; i < n; i++)

{
for (j = 0; j < n; j++)
{
if (graph[i][j] > graph[i][k] + graph[k][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}

}
}
int main(void)
{
int n, i, j;
int**graph=(int**)malloc((long unsigned)n*sizeof(int*));
printf(“Enter the number of vertices: “);

scanf(“%d”, &n); for (i = 0; i < n; i++)

{
graph[i] = (int *)malloc((long unsigned) n * sizeof(int));
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i == j) graph[i][j] = 0; else
graph[i][j] = 100;
}
}
printf(“Enter the edges: \n”);

for (i = 0; i < n; i++)

{
for (j = 0; j < n; j++)
{
printf(“[%d][%d]: “, i, j);
scanf(“%d”, &graph[i][j]);
}

}
printf(“The original graph is:\n”); for (i = 0; i< n; i++)
{
for (j = 0; j < n; j++)
{
printf(“%d “, graph[i][j]);
}
printf(“\n”);
}
floydWarshall(graph, n);
printf(“The shortest path matrix is:\n”);
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf(“%d “, graph[i][j]);
}
printf(“\n”);
}
return 0;

Output:
Enter the number of vertices: 4 Enter the
edges:
[0][0]: 2
[0][1]: 4
[0][2]: 5[0][3]: 6
[1][0]: 1
[1][1]: 0
[1][2]: 0
[1][3]: 4
[2][0]: 4
[2][1]: 7
[2][2]: 8
[2][3]: 9
[3][0]: 0
[3][1]: 5
[3][2]: 8
[3][3]: 9
The original graph is:
2456
1004
4789
0589
The shortest path matrix is: 2 4 4 6
1004
4779
0446

Result:

Thus to implement floyd’s algorithm for all pairs shortest path problem has been has been executed
successfully.
EX.NO: 7(B)

WARSHALL’S ALGORITHM

DATE:

Aim:
To compute the transitive closure of a directed graph using warshall
algorithm.

Algorithm:
1. Start the program
2. Initialize the variables and graph
3. Here we use warshall algorithm to compute the transitive closure of
the directed graph
4. Warshall algorithm has two rules
5. Rule 1: If an element in row I and column J is 1 in R(k-1) remains 1 in
R(k)
6. Rule 2: an element in row I and column j is 0 in R(k-1) it has to be
changed and only if to 1 In R(k) it has to be changed to 1 in R if and
only if (k) if
7. The element in its row I and column k and the element
8. In its column j and row k are both 1’s in
9. Display the result
10. Exit
Program:

#include<stdio.h> const int

MAX = 100;
void WarshallTransitiveClosure(int graph[MAX], int numVert); int main(void)
{
int I,j,numVert;
int graph[100][100];
printf(“Warshall’s Transitive Closure\n”);
printf(“Enter the number of vertices:”);
scanf(“%d”,&numVert);
printf(“Enter the adajacency matrix:-\n”);
for(i=0;i<numVert;i++)
for(j=0;j<numVert;j++);
scanf(“%d”,&graph[i][j]);
WarshallTransitiveClosure(graph,numVert);
printf(“\nThe Transitive closure for the given graph is :- \n);
for(i=0;i<numvert;i++)
{
for(j=0;j<numVert;j++)
{
printf(“%d\t”,graph[i][j]);
}
}
printf(“\n”);
}
return 0;
}
void WarhsallTransitiveClosure(int graph[MAX][MAX],int numVert)
{
int I,j,k; for(k=0;k<numVert;k++)
{
for(i=0;i<numvert;i++)
{
for(j=0;j<numVert;j++)
{
if(graph[i][j] || (graph[i][k]&&graph[k][j]))
graph[i][j]=1;
}
}
}
}
OUTPUT:

Warshall’s Transitive Closure Enter

the number of vertices:4 Enter the

adjacency Matrix:- 1 0 0 0

1001

1100

1100

1010

The transitive closure for the given graph is:-

1 0 0 0

1 1 1 1

1 1 1 1

RESULT:

Thus to compute the transitive closure of the directed graph using warshall algorithm has
been executed successfully.
 EX.NO: 8
DIVIDE AND CONQUER TECHNIQUE
DATE:

AIM:

To find the maximum and minimum numbers in given list of n numbers using divide and
conquer technique

ALGORITHM:

1. Set min and max to arr[0]

2. Start loop at 1, using index i

a) Check if arr[i] < min; if so, set min to arr[i]

b) Check if arr[i]>max; is so, set max to arr[i]

3. At the end of the loop, respond with and array

4. If the array is 1 element long, return [arr[0], arr[0]]

5. If the array is 2 elements long if arr[0] > arr[1], return [arr[1], arr[0]]

6. Otherwise, return arr

7. Split the array roughly into a left hald, calling minmax on each half

8. Return [min(left[0],right[0]), max(left[1],right[1]]

PROGRAM:
#include<stdio.h>
struct pair
{
Int min; Int
max;
};
Struct pair getMinMax(int arr[], int n)
{
Struct pair minmax; Int I;
If (n == 1)
{
Minmax.max = arr[0];
Minmax.min = arr[0];
Return minmax;
}
if (arr[0] > arr[1])
{
Minmax.max = arr[0];
Minmax.min = arr[1];

}
Else
{
Minmax.max = arr[1];
Minmax.min = arr[0];
}
For (I = 2; i<n; i++)
{
If (arr[i] > minmax.max) Minmax.max = arr[i]; Else if (arr[i] <
minmax.min) Minmax.min = arr[i];
}
Return minmax;
}
Int main()
{
Int arr[] = {1000, 11, 445, 1, 330, 3000};
Int arr_size = 6;
Struct pair minmax = getMinMax (arr, arr_size);
Printf(“nMinimum element is %d”, minmax.min);
Printf(“nMaximum element is %d”, minmax.max); Getchar();
Return 0;
}

OUTPUT:
nMinimum Element is 1 nMaximum
Element is 3000

RESULT:

Thus the program for finding maximum and minimum number of n numbers using divide and
conquer technique was executed successfully
EX.NO: 9(a)
MERGE SORT
DATE:

AIM:

To implement a merge sort to sort an array of elements

ALGORITHM:
1. Start the program
2. Declare array and left, right and mid values
3. Find the middle index of the array to divide int two half
4. Find mid=(left+right)/2
5. Call mergesort on (left,mid) and (right,n-mid)
6. Calculate the time taken to sort
7. Stop

PROGRAM:

#include <stdio.h> #include

<time.h>
// Function to merge two sorted arrays
void merge(int arr[], int left[], int left_size, int right[], int right_size)
{
int i = 0, j = 0, k = 0;
while (i < left_size && j < right_size)
{
if (left[i] < right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
while (i < left_size)
arr[k++] = left[i++];
while (j < right_size)
arr[k++] = right[j++];
}
// Function to perform merge sort void
mergeSort(int arr[10], int n)
{
if (n <= 1) return; int
mid = n / 2; int
left[10];
int right[20];
// Dividing the array into left and right halves for (int i = 0;
i < mid; i++)
left[i] = arr[i];
for (int i = mid; i < n; i++)
right[i - mid] = arr[i];
// Recursively sorting left and right halves m
mergeSort(right, n - mid);
// Merging the sorted left and right halves
merge(arr, left, mid, right, n - mid);
}
int main()
{
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[10];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("\nOriginal Array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// Recording the start time clock_t
start = clock();
mergeSort(arr, n);
// Recording the end time
clock_t end = clock();
printf("\nSorted Array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]); printf("\n");
// Calculating the time taken to sort
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort: %f seconds\n", time_taken);
return 0;
}
mergeSort(left, mid);

mergeSort(right, n - mid);
// Merging the sorted left and right halves
merge(arr, left, mid, right, n - mid);
}
int main()
{
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[10];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("\nOriginal Array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// Recording the start time
clock_t start = clock();
mergeSort(arr, n);
// Recording the end time
clock_t end = clock();
printf("\nSorted Array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// Calculating the time taken to sort
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC; printf("\nTime taken to sort: %f
seconds\n", time_taken);
return 0;
}

OUTPUT:
Enter the number of elements: 3Enter the
elements: 28 41 47
Original array: 28 41 47
Sorted array: 28 41 47
Time taken to sort: 0.000002

RESULT:

Thus to implement a merge sort to sort an array elements has been executed successfully.
 EX.NO: 9(b)
QUICK SORT
DATE:

AIM:

To implement a quick sort to sort an array of elements

ALGORITHM:

1. Start the program

2. Declare an array
3. Pick an element from an array, call it as pivot element
4. Divide an unsorted array into two array
5. If values less than pivot element come under first subarray
6. If value greater than pivot element come under second subarray
7. Stop

PROGRAM:

#include<stdio.h>
#include<stblib.h>
#include<time.h>
void swap(int*a, int*b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int partition(int arr[],int low,int high)
{
int pivot=arr[low];

int i=low+1;
int j=high;
while(1)
{
while(i<=j&&arr[i]<pivot)
i++;
while(i<=j&&arr[j]>pivot)
j--;
if(i<=j)
{
swap(&arr[i],&arr[j]);
i++;
j--;
}
else break;
}
swap(&arr[low],&arr[j]); return j;
}
void quicksort(int arr[],int low,int high)
{
if(low<high)
{
int pivotIndex=partition(arr,low,high);
}
}
int main()
{
int n;
printf(“Enter the number of elements:”);
scanf(“%d”,&n);
int arr[10];
stand(time(0));
for(int i=0;i<n;i++)
{
arr[i]=rand()%100;
}
printf(“Original array:\n”);
for(int i=0;i<n;i++)
{
printf(“%d”,arr[i]);
}
clock_t start=clock();
double time_taken=((double)(end-start))
printf(“\nSorted array:\n);
for(int i=0;i<n;i++)
{
printf(“%d”,arr[i]);
}
printf(“\nTime taken:%.2f ms\n”,time_taken);
return 0;
}

OUTPUT:

Enter the number of elements: 6 Original array:

60 56 27 20 77 9
Sorted array:
9 20 27 56 60 77
Time taken: 0.00 ms

RESULT:

Thus the quick sort to sort an array of element has been executed successfully.
 EX.NO: 10 a
N-QUEENS PROBLEM USING
DATE: BACKTRACKING

AIM:
To implement the program for N_QUEENS problem using Backtracking

ALGORITHM:
1. Initialize an empty chessboard for size NxN
2. Start with the leftmost column and place a queen in the first row of that column
3. Move to the next column and place a queen in the first row of that column
4. Repeat step 3 until either all N queens have been placed or it is impossible to place a
queen in the current column without violating the rules of the problem
5. If all N queens have been places, print the solution
6. If it is not possible to place a queen in the current column without violating the rules
of the problem, backtrack to the previous column
7. Remove the queen from the previous column and move it down one row
8. Repeat steps 4-7 until all possible configurations have been tired
PROGRAM:

#include<stdio.h>

#include<math.h>
#include<stdlib.h>
int board[20],count;
void print(int n)
{
int i,j;
printf(“\n\nSolution %d:\n\n”,++count);
for(i=1;i<=n;++i)
printf(“\t%d”,i);
for(i=1;i<=n;++i)
{
printf(“\n\n%d”,i);
for(j=1;j<=n;++j)
{
if(board[i]==j)
printf(“\tQ”);
else
printf(“\t-“);
}}}
int place(int row,int column)
{
int i;
for(i=1;i<=row-1;++1)
{
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==ans(i-row))
return 0;
}
return 1;
}
 void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
if(place(row,column))
{
board[row]=column;
if(row==n)
print(n);
else
queen(row+1,n);
}
}
}
void main()
{
int n,i,j;
void queen(int row,int n);
printf(“Enter number of Queens:”); scanf(“%d”,&n);
if(n<=3)
printf(“Number should be greater than 3”); else
queen(1,n);
}
 OUTPUT:

Enter number of Queens:3 Number should be greater than 3 D:\siya>queens

Enter number of Queens:4

Solution 1:
1 2 3 4
1 - Q - -
2 - - - Q
3 Q - - -
4 - - Q -

Solution 2:

1 2 3 4
1 - - Q -
2 Q - - -
3 - - - Q
4 - Q - -
D:\siya

RESULT:

Thus the C program for N-Queens problem has been executed

 EX.NO: 10b
TRAVELLING SALESPERSON PROBLEM
DATE:

AIM:

To write an algorithm for Travelling Salesperson Problem

ALGORITHM:
1. Start the program
2. Declare the variables
3. Get input for the row elements
4. Find the shortest path
5. Find the minimum cost
6. Print the result
7. Stop the program

PROGRAM:

#include<stdio.h>
int matrix[25][25],visited_cities[10],limit,cost=0;
int tsp(int c)
{
int count, nearest_city=999;
int minimum=999,temp;
for(count=0;count<limit;count++)
{
if((matrix[c][count]!=0)&&(visited_cities[count]==0))
{
if(matrix[c][count]<minimum)
{
minimum=matrix[count][0]+matrix[c][count];
}
temp=matrix[c][count];
nearest_city=count;
}
}
if(minimum!=999)
{
cost=cost+temp;
}
return nearest_city;
}
void minimum_cost(int city)
{
int nearest_city;
visited_cities[city]=1;
printf(“%d”,city+1);
nearest_city=tsp(city);
if(nearest_city==999)
{
nearest_city=0;
printf(“%d”,nearest_city+1);
cost=cost+matrix[city][nearest_city];
return;
}
minimum_cost(nearest_city);
}
int main()
{
int i,j;
printf(“Enter total number of cities:\t);
scanf(“%d”,&limit);
printf(“\nEnter Cost Matrix\n”);
for(i=0;i<limit;i++)
{
printf(“\nEnter %d elements in row[%d]\n”,limit,i+1);
for(j=0;j<limit,j++)
{
scanf(“%d”,&matrix[i][j]);
}
visited_cities[i]=0;
}
printf(“\nEnterted Cost Matrix:\n”);
for(i=0;i<limit;i++)
{
printf(“\n”);
for(j=0;j<limit;j++)
{
printf(“%d”,matrix[i][j]);
}
}
printf(“\n\nPath:\t”);
minimum_cost(0);
printf(“\n\nMinimum Cost:\t”);
printf(“%d\n”,cost);
return 0;
OUTPUT:

Enter total number of cities: 4 Enter

cost matrix
Enter 4 elements in row[1] 1 2 3
4
Enter 4 elements in row[2] 5 6 7
8
Enter 4 elements in row[3] 9 8 4
3
Enter Cost Matrix 1 2
3 4
5 6 7 8
3 4 5 6
9 8 4 3

Path: 1 4 3 2 1
Minimum Cost: 17

RESULT:

Thus the program was successfully executed

 EX.NO: 11
IMPLEMENT RANDOMIZED ALGORITHMS FOR FINDING
DATE: THE KTH SMALLEST NUMBER

AIM:

To implement randomized algorithms for finding kth smallest number

ALGORITHM:

1. Select a random element from a array as a pivot

2. Then partition to the array around the pivot, its help to all the smaller element were placed
before in the pivot and all greater element are placed after the pivot
3. Then check the position of the pivot. If it is the kth element then return it
4. If it is the less than the kth element then repeat the process of the sub array
5. If it is the greater than the kth element then repeat the process of the left sub array

PROGRAM:

#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h> int
N=20;
int A[20];
void swap(int dex1, int dex2)
{
Int temp=A[dex1];
A[dex1]=A[dex2];
A[dex2]=temp;
}
int partition(int start,int end)
{
int i=start+1;
int j=I;
int pivot=start;
for(;i<end;i++)
{
if(A[i]<a[pivpt])
{
swap(i,j);
j++;
}
}
if(j<=end)
swap(pivot,(j-1));
return j=1;
}
void quick_sort(int start, int end, int K)
{
int part; if(start<end)
{
part=partition(start,end);
if(part==K-1)
printf(“kth smallest element:%d”,A[part]);
if(part>K-1)
quick_sort(start, part, k);
}
return;
}
int main(int argc, char **argv)
{
int i;
time_t seconds;
time(&seconds);
srand((unsigned int)seconds);
for(i=0;i<N;i++)
A[i]=rand()%(1000-1+1)+1;
printf(“The Original sequence is: “);
for(i=0;i<N;i++)
printf(“%d”,A[i]);
printf(“\nEnter the Kth smallest you want to find:”);
int k;scanf(“%d”,&k);
quick_sort(0,N,k);
}
OUTPUT:

The original sequence is: 909 967 552 524 735 383 616 718 904 945 730 173
143 954 482 307 228 35 224 703

Enter the Kth smallest you want to find: 3 Kth

smallest element: 173

RESULT:

Thus, to implement randomized algorithms for finding kth smallest number was successfully executed.
 EX.NO: 12
GRAPH COLORING ALGORITHM USING BACKTRACKING
DATE:

AIM:

To implement Graph Coloring algorithm using backtracking

ALGORITHM:

1. If index == number.of.vertices, return TRUE.

2. else, for every k= 1 to M :

assign color to the current vertex, v, (color[v]=k)

if colour(graph,vertex+1,color)==TRUE,

return true

else ,

mark the colour as unassigned, (colour[v]=0) (backtracking step).

If none of the combination satisfies, return FALSE.

PROGRAM:

#include<stdio.h>
int G[10][10],m,edges,color_tab[10],v1,v2,i,j,n,a,b;
void Gen_Col_Value(int,int);
void Gr_coloring(int,int);
int main()
{
printf("\nEnter the number of nodes & edges\n");
scanf("%d%d",&n,&edges);
m=n-1;
printf("\nEnter the edges of the graph\n\n");
for (i=1;i<=edges; i++)
{
printf("Enter value of x,y\n");
 scanf("%d%d",&v1,&v2);
G[v1][v2] = G[v2][v1] = 1;
printf("\n");
}
Gr_coloring(1,n);
printf("\n The Vertices To be Coloured As...\n");
for(i=1;i<=n;i++)
printf("\n V%d:=%d",i,color_tab[i]);
return 0;
}
void Gen_Col_Value(int k,int n)
{
while(1)
{
a=color_tab[k]+1;
b=m+1;
color_tab[k] = a%b;
if(color_tab[k]==0)
return;
for(j=1;j<=n;j++)
{
if(G[k][j] && color_tab[k]==color_tab[j])
break;
}
if(j==n+1)
return;
}
}
void Gr_coloring(int k,int n)
{
Gen_Col_Value(k,n);
if(color_tab[k]==0)
return;
if(k==n)
return;
 else
Gr_coloring(k+1,n);
}
OUTPUT:
output:-
Enter the number of nodes & edges
4
5
Enter the edges of the graph
Enter value of x,y
0
1
Enter value of x,y
1
2
Enter value of x,y
1
3
Enter value of x,y
2
3
Enter value of x,y
3
0
The Vertices To be Coloured As...
V1:=1
V2:=2
V3:=3
V4:=1
--------------------------------

RESULT:

Thus, to implement Graph Coloring algorithm using backtracking was successfully executed.