DESIGN AND ANALYSIS OF ALGORITHMS LAB

[U21CS5L1]

III.BE - CSE – V Semester

A.Y: 2023-2024

LABORATORY MANUAL

Compiled by

Mr. Mohammad Azeem

Assistant Professor

LORDS INSTITUTE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
HIMAYATHSAGAR, HYDERABAD – 500091
SEPTEMBER-2023
 DEPARTMENT (CSE) VISION & MISSION

Vision of the Department

To emerge as a Centre of excellence by imparting quality technical education
through innovation, team work & value creation, and to contribute to advancement
of knowledge in the field of Computer Science & Engineering.

Mission of the Department

DM1: Providing the students with in-depth understanding of fundamentals and
practical training related to professional skills, problem solving skills and
their applications through effective Teaching-Learning Process and State of
the art laboratories pertaining to computer science & engineering and inter-
disciplinary areas
DM2: Preparing students in developing research, design, entrepreneurial skills and
employability capabilities
DM3: Providing consultancy services and promoting Industry-Department
Interactions

Note: DM: Department Mission

PROGRAM OUTCOMES
Engineering graduates will be able to:
PO1: Engineering knowledge: Apply the knowledge of mathematics, science,
engineering fundamentals, and an engineering specialization to the solution of
complex engineering problems.
PO2: 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.
PO3: 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.
PO4: 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.
PO5: Modern tool usage: Create, select, and apply appropriate techniques,
resources, and modern engineering and IT tools including prediction and modelling
to complex engineering activities with an understanding of the limitations.
PO6: 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.
PO7: 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.
PO8: Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice.
PO9: Individual and team work: Function effectively as an individual, and as a
member or leader in diverse teams, and in multidisciplinary settings.
PO10: 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.
PO11: 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.
PO12: 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 OUTCOMES

At the end of 4 years, Computer Science and Engineering graduates at LIET will be
able to:
PSO1: Professional Skills: The ability to research, understand and implement
computer programs in the areas related to algorithms, system software, multimedia,
web design, big data analytics, and networking for efficient analysis and design of
computer-based systems of varying complexity.
PSO2: Problem-Solving Skills: The ability to apply standard practices and
strategies in software service management using open-ended programming
environments with agility to deliver a quality service for business success.
GENERAL LABORATORY INSTRUCTIONS:
1. Students are advised to come to the laboratory at least 5 minutes before to starting
time, those who come after 5 minutes will not be allowed into the lab.
2. Plan your task properly much before to the commencement, come prepared to the
lab with the program / experiment details.
3. Student should enter into the laboratory with:
a. Laboratory observation notes with all the details (Problem statement, Aim,
Algorithm, Procedure, Program, Expected Output, etc.,) filled in for the lab
session.
b. Laboratory Record updated up to the last session experiments.
c. Formal dress code and Identity card.

4. Sign in the laboratory login register, write the TIME-IN, and occupy the computer
system allotted to you by the faculty.

5. Execute your task in the laboratory, and record the results / output in the lab
observation note book, and get certified by the concerned faculty.

6. All the students should be polite and cooperative with the laboratory staff, must
maintain the discipline and decency in the laboratory.

7. Computer labs are established with sophisticated and high-end branded systems,
which should be utilized properly.

8. Students / Faculty must keep their mobile phones in SWITCHED OFF mode
during the lab sessions. Misuse of the equipment, misbehaviors with the staff and
systems etc., will attract severe punishment.

9. Students must take the permission of the faculty in case of any urgency to go out.
If anybody found loitering outside the lab / class without permission during working
hours will be treated seriously and punished appropriately.

10. Students should SHUT DOWN the computer system before he/she leaves the lab
after completing the task (experiment) in all aspects. He/she must ensure the system
/seat is kept properly.
CODE OF CONDUCT FOR THE LABORATORY
• All students must observe the dress code while in the laboratory
• Footwear is NOT allowed
• Foods, drinks and smoking are NOT allowed
• All bags must be left at the indicated place
• The lab timetable must be strictly followed
• Be PUNCTUAL for your laboratory session
• All programs must be completed within the given time
• Noise must be kept to a minimum
• Workspace must be kept clean and tidy at all time
• All students are liable for any damage to system due to their own negligence
• Students are strictly PROHIBITED from taking out any items from the
• laboratory
• Report immediately to the lab programmer if any damages to equipment

BEFORE LEAVING LAB:

• Arrange all the equipment and chairs properly.
• Turn off / shut down the systems before leaving.
• Please check the laboratory notice board regularly for updates.

Lab In – charge
 Experiment No. 1

Implement a program to sort the elements by using quick sort method.

#include <stdio.h>
// function to swap elements
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int A[], int p, int r)
{
int x = A[r]; // select the rightmost element as pivot
int i = p - 1;
// traverse each element of the array and compare them with the pivot
int j;
for (j = p; j < r; j++)
{
if (A[j] <= x)
{
i=i+1; // if element smaller than pivot is found then swap it with the greater element pointed by i
swap(&A[i], &A[j]); // swap element at i with element at j
}
}
i=i+1;
// swap the pivot element with the greater element at i
swap(&A[i], &A[r]);
// return the partition point
return i;
}
void quickSort(int A[], int p, int r)
{
if (p < r)
{
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
 int q = partition(A, p, r);
quickSort(A, p, q - 1); // recursive call on the left of pivot
quickSort(A, q + 1, r); // recursive call on the right of pivot
}
}
// function to print array elements
void printArray(int array[], int size)
{
int i;
for (i = 0; i < size; ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {18, 17, 12, 11, 10, 19, 16};

int n = sizeof(data) / sizeof(data[0]);

printf("Unsorted Array\n");
printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
getchar();
return 0;
}

OUTPUT:
 Experiment No. 2

Implement a program to sort the elements by using merge sort method.

#include <stdio.h>
// Merge two sorted subarrays ino one sorted array
void merge(int arr[], int low, int mid, int high)
{
int h=low;
int i=low;
int j=mid+1;
int len = sizeof(arr) / sizeof(arr[0]);
int b[len];
while ((h <= mid) && (j <= high))
{
if (arr[h] <= arr[j])
{
b[i] = arr[h];
h = h + 1;
}
else
{
b[i] = arr[j];
j = j+1;
}
i = i + 1;
}
int k;
if (h >mid)
{
for(k=j; k<=high; k++)
{
b[i]=arr[k];
i=i+1;
}
}

else
{
 for(k=h; k<=mid; k++)
{
b[i]=arr[k];
i=i+1;
}
}
for(k=low; k<=high; k++)
{
arr[k]=b[k];
}
}

// Divide the array into two subarrays, sort them and merge them

void mergeSort(int arr[], int low, int high) {

if (low < high)
{
// mid is the point where the array is divided into two subarrays
int mid = (low+high)/2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
// Merge the sorted subarrays
merge(arr, low, mid, high);
}
}
// Print the array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main()
{
int data[] = {16, 15, 12, 10, 19, 11, 18};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
 // perform mergesort on data
mergeSort(data, 0, n - 1);

printf("Sorted array in ascending order: \n");

printArray(data, n);
getchar();
return 0;
}

OUTPUT:
 Experiment No. 3

Obtain the Topological ordering of vertices in a given digraph.

#include <stdio.h>
#include <stdlib.h>
int temp[10],k=0;

void topo(int n,int indegree[10],int a[10][10])

{
int i,j;
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{
indegree[i]=1;
temp[++k]=i;
for(j=1;j<=n;j++)
{
if(a[i][j]==1&&indegree[j]!=-1)
indegree[j]--;
}
i=0;
}
}
}

int main()
{
int i,j,n,indegree[10],a[10][10];
printf("Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
indegree[i]=0;

printf("\nEnter the adjacency matrix\n");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
 if(a[i][j]==1)
indegree[j]++;
}
topo(n,indegree,a);

if(k!=n)
printf("topological ordering is not possible\n");

else
{
printf("\n topological ordering is :\n");
for(i=1;i<=k;i++)
printf("v%d\t",temp[i]);
}

system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 4

From a given vertex in a weighted connected graph, find shortest paths to other
vertices using Dijkstra's algorithm.

#include<stdio.h>
#include <stdlib.h>
#define infinity 999
void dijkstra(int n,int v,int cost[10][10],int dist[100])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n ;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}
int main()
{
int n,v,i,j,cost[10][10],dist[10];
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the cost matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
}
printf("\n Enter the source Vertex:");
scanf("%d",&v);
dijkstra(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 5

Implement 0/1 Knapsack problem using Dynamic Programming.

#include<stdio.h>
#include <stdlib.h>

// Function to find maximum of two integers

int max(int a, int b) { return (a > b)? a : b; }

// Function to find the maximum value that can be put in a knapsack of capacity W

int knapSack(int W, int weight[], int value[], int n)

{
if (n == 0 || W == 0) // Base Case
return 0;

// If weight of the nth item is more than Knapsack capacity W

if (weight[n-1] > W)
return knapSack(W, weight, value, n-1); /* this item cannot be included in the optimal solution */

else return max( value[n-1] + knapSack(W-weight[n-1], weight, value, n-1), knapSack(W, weight,
value, n-1));
}

int main()
{
int n;
printf("\nEnter the number of items : ");
scanf("%d", &n);
int value[n];
int weight[n];
int i;
printf("\nEnter the item's weight and its value \n");
for(i = 0; i < n; i++)
{
scanf("%d %d", &weight[i], &value[i]);
}
int W;
printf("\nEnter the capacity of the knapsack : ");
scanf("%d", &W);
printf("\nMaximum value in a 0/1 knapsack : %d\n", knapSack(W, weight, value, n));
system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 6

Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's
algorithm.

#include<stdio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);

int main()
{
printf("\n\n\tImplementation of Kruskal's algorithm\n\n");
printf("\nEnter the no. of vertices\n");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf("\nThe edges of Minimum Cost Spanning Tree are\n\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
system("PAUSE");
return 0;
}

int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}

int uni(int i,int j)

{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
OUTPUT:
 Experiment No. 7

Find Minimum Cost Spanning Tree of a given undirected graph using Prim's
algorithm.

#include<stdio.h>
#include<stdlib.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
int main()
{
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 8 [a]

Compute the transitive closure of a given directed graph using Warshall's algorithm.

# include <stdio.h>
#include<stdlib.h>
int a[10][10];
int main()
{
int i,j,k,n;
printf("\nEnter the number of vertices\n");
scanf(" %d",&n);
printf("\nEnter the adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(" %d",&a[i][j]);

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=a[i][j] || a[i][k] && a[k][j];
printf("\n\t The tranitive closure is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\t %d",a[i][j]);
printf("\n");
}
system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 8 [b]

Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.

#include<stdio.h>
#include<stdlib.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
if(a<b)
return(a);
else
return(b);
}
int main()
{
int p[10][10],w,n,e,u,v,i,j;
printf("\nEnter the number of vertices: ");
scanf("%d",&n);
printf("Enter the number of edges: ");
scanf("%d",&e);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++)
{
printf("Enter the end vertices of edge%d with its weight \n",i);
scanf("%d%d%d",&u,&v,&w);
p[u][v]=w;
}
printf("Matrix of input data:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d \t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\nThe shortest paths are:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("<%d,%d>=%d\n",i,j,p[i][j]);
}
system("PAUSE");
return 0;
}

OUTPUT:
 Experiment No. 9 [a]

Print all the nodes reachable from a given starting node in a digraph using BFS
method.

#include<stdio.h>
#include<stdlib.h>
int a[20][20],q[20],visited[20],r=-1,f=0,i,j,n;
void bfs(int v);
int main(){
int v;
printf("Enter no. of vertices:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("Enter Adjacency Matrix of the graph:\n");
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
printf("Enter the node of ur Choice:\n");
scanf("%d",&v);
bfs(v);
printf("All the nodes reachable from node->%d is/are :\n\n",v);
for(i=1;i<=n;i++){
if(visited[i])
printf("%d\t",i);
}
printf("\n");
system("PAUSE");
return(0);
}
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++]);
}
}

OUTPUT:
 Experiment No. 9 [b]

Check whether a given graph is connected or not using DFS method.

#include<stdio.h>
#include<stdlib.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);
}
}
int main()
{
int i,j,count=0;
printf("\nEnter number of vertices:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
}
printf("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("Graph is connected\n");
else
printf("Graph is NOT connected\n");
system("PAUSE");
return(0);
}

OUTPUT 1:

OUTPUT 2:
 Experiment No. 10

Implement N Queen's problem using Back Tracking.

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int x[30],count=0;
int place(int k,int i)
{
int j;
for(j=1;j<=k-1;j++)
{
if((x[j]==i)||((abs(x[j]-i)==abs(j-k))))
return 0;
}
return 1;
}
void print_sol(int n)
{
int i,j;
count++;
printf("\n\nSolution #%d:\n",count);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(x[i]==j)
printf("Q\t");
else
printf("*\t");
}
printf("\n");
}
}
void queen(int k,int n)
{
int i,val;
for(i=1;i<=n;i++)
{
if(place(k,i))
{
x[k]=i;
if(k==n)
print_sol(n);
else
queen(k+1,n);
}
}
}
int main()
{
int i,n;
printf("Enter the number of Queens\n");
scanf("%d",&n);
queen(1,n);
printf("\nTotal solutions=%d\n",count);
system("PAUSE");
return(0);
}

OUTPUT: