Analysis & Design of Algorithms Laboratory(BCSL404)

IV Semester Lab Manual

Course Co-ordinator : VACHANA C

Asst. Professor ,AI & ML

Department of Artificial Intelligence & Machine Learning

Academic Year 2024-2025
 Analysis &Design of Algorithms Lab(BCSL404)

1. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of
agiven connected undirected graph using Kruskal's algorithm.

#include<stdio.h>
int ne=1,min_cost=0;
void main()
{
int n,i,j,min,a,u,b,v,cost[20][20],parent[20];
printf("Enter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the costmatrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
for(i=1;i<=n;i++)
parent[i]=0;
printf("\nThe edges of spanning treeare\n");
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
printf("Edge %d\t(%d->%d)=%d\n",ne++,a,b,min);
min_cost=min_cost+min;
parent[v]=u;
}
cost[a][b]=cost[a][b]=999;
}
printf("\nMinimum cost=%d\n",min_cost);
}

Dept.of AIML, VKIT Page 1

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 2

 Analysis &Design of Algorithms Lab(BCSL404)

2. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of
agiven connected undirected graph using Prim's algorithm.

#include<stdio.h>

int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{

printf("\nEnter the number of nodes:");

scanf("%d",&n);
printf("\nEnter 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("\nEdge %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);
}

Dept.of AIML, VKIT Page 3

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 4

 Analysis &Design of Algorithms Lab(BCSL404)

3.a Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using
Floyd's algorithm.

#include <stdio.h>
#include<limits.h>

#define V 4

void floydWarshall(int graph[V][V]){

int dist[V][V];

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

for(int j = 0;j < V;j++)
dist[i][j]= graph[i][j];

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

for(int i=0;i<V;i++)
for(int j = 0; j <V; j++)
if(dist[i][k]!=INT_MAX && dist[k][j]!=INT_MAX&&dist[i][k]+dist[k][j]<
dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];

printf("Shortest distances between every pair of vertices:\n");

for (int i = 0; i < V; i++) {
for(int j= 0;j <V;j++) {
if(dist[i][j]==INT_MAX)
printf("INF\t");
else
printf("%d\t",dist[i][j]);
}
printf("\n");
}
}

int main() {
int graph[V][V]={{0,INT_MAX,3, INT_MAX},
{2,0,INT_MAX,INT_MAX},
{INT_MAX,7, 0, 1},
{6,INT_MAX,INT_MAX,0}};

floydWarshall(graph);

return 0;
}

Dept.of AIML, VKIT Page 5

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 6

 Analysis &Design of Algorithms Lab(BCSL404)

3.b Design and implement C/C++ Program to find the transitive closure using
Warshal'salgorithm.

# include<stdio.h>
int n,a[10][10],p[10][10];
void path()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1)p[i][j]=1;
}
void main()
{
int i,j;
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
path();
printf("\nThe path matrix is showm below\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d",p[i][j]);
printf("\n");
}
}

Dept.of AIML, VKIT Page 7

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 8

 Analysis &Design of Algorithms Lab(BCSL404)

4. Design and implement C/C++Program to find shortest paths from agiven vertex in a
weighted connected graph to other vertices using Dijkstra's algorithm.

#include<stdio.h>
void dij(int, int[20][20],int[20],int[20],int);
void main() {
int i,j,n,visited[20],source,cost[20][20],d[20];
printf("Enter no. of vertices: ");
scanf("%d",&n);
printf("Enter the cost adjacency matrix\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d",&cost[i][j]);
}
}
printf("\nEnter the source node:");
scanf("%d", &source);
dij(source, cost, visited, d, n);
for (i = 1; i <= n; i++) {
if(i != source)
printf("\nShortest path from %d to %d is %d",source, i, d[i]);
}
}
void dij(int source,int cost[20][20],int visited[20],int d[20],int n){
int i, j, min, u, w;
for(i=1;i<=n;i++){
visited[i] = 0;
d[i] =cost[source][i];
}
visited[source]=1;
d[source]=0;
for(j=2;j<=n;j++){
min = 999;
for(i=1;i<=n;i++){
if (!visited[i]) {
if(d[i]<min){
min = d[i];
u =i;
}
}
}
visited[u]=1;
for(w =1; w<=n; w++) {
if(cost[u][w]!=999 && visited[w]==0){
if (d[w] > cost[u][w] + d[u])
d[w]=cost[u][w]+d[u];

Dept.of AIML, VKIT Page 9

 Analysis &Design of Algorithms Lab(BCSL404)

}
}
}
}

Output:

Dept.of AIML, VKIT Page 10

 Analysis &Design of Algorithms Lab(BCSL404)

5. Design and implement C/C++ Program to obtain the Topological ordering of vertices in
a given digraph.

#include<stdio.h>
void findindegree(int [10][10],int[10],int);
void topological(int,int [10][10]);
void main()
{
int a[10][10],i,j,n;
printf("Enter the number of nodes:");
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]);
printf("\nThe adjacency matirxis:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
topological(n,a);
}
void findindegree(int a[10][10],int indegree[10],int n)
{
int i,j,sum;
for(j=1;j<=n;j++)
{
sum=0;
for(i=1;i<=n;i++)
{
sum=sum+a[i][j];
}
indegree[j]=sum;
}
}
void topological(int n,int a[10][10])
{
int k,top,t[100],i,stack[20],u,v,indegree[20];
k=1;
top=-1;
findindegree(a,indegree,n);
for(i=1;i<=n;i++)

Dept.of AIML, VKIT Page 11

 Analysis &Design of Algorithms Lab(BCSL404)

{
if(indegree[i]==0)
{
stack[++top]=i;
}
}
while(top!=-1)
{
u=stack[top--];
t[k++]=u;
for(v=1;v<=n;v++)
{
if(a[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
{
stack[++top]=v;
}}
}}
printf("\nTopological sequence is\n");
for(i=1;i<=n;i++)
printf("%d\t",t[i]);
}

Output:

Dept.of AIML, VKIT Page 12

 Analysis &Design of Algorithms Lab(BCSL404)

6. Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.

#include<stdio.h>
#define MAX 50
int p[MAX],w[MAX],n;
int knapsack(int,int);
int max(int,int);
void main()
{
int m,i,optsoln;

printf("Enter no. of objects: ");

scanf("%d",&n);
printf("\nEnter the weights:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("\nEnter the profits:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("\nEnter the knapsack capacity:");
scanf("%d",&m);
optsoln=knapsack(1,m);
printf("\nThe optimal soluntion is:%d",optsoln);
}
int knapsack(int i,int m)
{
if(i==n)
return(w[n]>m) ? 0 : p[n];
if(w[i]>m)
return knapsack(i+1,m);
return max(knapsack(i+1,m),knapsack(i+1,m-w[i])+p[i]);
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}

Dept.of AIML, VKIT Page 13

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 14

 Analysis &Design of Algorithms Lab(BCSL404)

7. Design and implement C/C++ Program to solve discrete Knapsack and continuous
Knapsack problems using greedy approximation method.

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
//Structuretorepresentanitem
struct Item {
int weight;
int value;
};
//Function to solve discrete knapsack using greedy approach
int discreteKnapsack(vector<Item>& items, int capacity) {
// Sort items based on their value per unit weight
sort(items.begin(),items.end(), [](const Item& a,const Item& b){
return (double)a.value / a.weight>(double)b.value / b.weight;
});
int totalValue=0;
int currentWeight=0;
// Fill the knapsack with items
for(const Item& item:items){
if(currentWeight+ item.weight <= capacity){
currentWeight += item.weight;
totalValue+= item.value;
}
}
return totalValue;
}
// Function to solve continuous knapsack using greedy approach
double continuousKnapsack(vector<Item>&items,int capacity){
// Sort items based on their value per unit weight
sort(items.begin(),items.end(),[](const Item&a, const Item& b){
return (double)a.value/a.weight>(double)b.value/b.weight;
});
double totalValue=0.0;
int currentWeight = 0;
//Fill the knapsack with items fractionally
for (const Item& item : items) {
if(currentWeight + item.weight<=capacity){
currentWeight += item.weight;
totalValue+= item.value;
}else {
int remainingCapacity= capacity - currentWeight;
totalValue+= (double)item.value/ item.weight * remainingCapacity;
break;

Dept.of AIML, VKIT Page 15

 Analysis &Design of Algorithms Lab(BCSL404)

}}
return totalValue;
}
int main() {
vector<Item>items;
int n, capacity;
//Input number of items and capacity of knapsack
cout <<"Enter the number of items: ";
cin>>n;
cout<<"Enter the capacity of knapsack:";
cin >> capacity;
// Inputtheweightand valueofeachitem
cout<<"Enter the weight and value of each item:"<<endl;
for (int i = 0; i < n; i++) {
Item item;
cout <<"Item "<< i + 1 <<": ";
cin>>item.weight>>item.value;
items.push_back(item);
}
//Solvediscreteknapsackproblem
int discreteResult=discreteKnapsack(items,capacity);
cout<<"Maximum value for discreteknapsack: "<<discreteResult <<endl;
//Solvecontinuousknapsack problem
double continuousResult=continuousKnapsack(items, capacity);
cout<<"Maximum value for continuous knapsack:"<<continuousResult<<endl; return 0;
}

Output:

Dept.of AIML, VKIT Page 16

 Analysis &Design of Algorithms Lab(BCSL404)

8. Design and implement C/C++Program to find a subset of a given setS={sl, s2, .......... ,sn}of
N positive integers whose sum is equal to agiven positive integerd.

#include<stdio.h>
void subset(int,int,int);
int x[10],w[10],d,count=0;
void main()
{
int i,n,sum=0;

printf("Enter the no.ofelements:");

scanf("%d",&n);
printf("\nEnter the elements in ascending order:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum:");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d)
{
printf("No solution\n");

return;
}
subset(0,0,sum);
if(count==0)
{
printf("No solution\n");

return;
}

}
void subset(int cs,int k,int r)
{
int i;
x[k]=1;
if(cs+w[k]==d)
{
printf("\n\nSubset %d\n",++count);
for(i=0;i<=k;i++)
if(x[i]==1)
printf("%d\t",w[i]);
}
else

Dept.of AIML, VKIT Page 17

 Analysis &Design of Algorithms Lab(BCSL404)

if(cs+w[k]+w[k+1]<=d)
subset(cs+w[k],k+1,r-w[k]);
if(cs+r-w[k]>=d && cs+w[k]<=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
}

Output:

Dept.of AIML, VKIT Page 18

 Analysis &Design of Algorithms Lab(BCSL404)

9. Design and implement C/C++ Program to sort a given set of n integer elements using
Selection Sort method and compute its time complexity. Run the program for varied values
of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The
elements can be read from a file or can be generated using the random number generator.

#include <stdio.h>
#include<stdlib.h>
#include <time.h>
//Function to perform selection sort
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for(i = 0; i < n-1; i++){
minIndex=i;
for(j = i +1; j <n; j++) {
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
//Swapthefoundminimumelementwiththefirstelement
temp = arr[minIndex];
arr[minIndex]=arr[i];
arr[i] = temp;
}
}
//Functiontogeneraterandomnumbersbetween 0 and 999
int generateRandomNumber() {
return rand() % 1000;
}
int main() {
//Setnvalue
int n =6000;

// Allocate memoryforthe array

int* arr=(int*)malloc(n * sizeof(int));

//Generate random elements for the array

srand(time(NULL));
printf("Random numbers for n=%d:\n",n);
for (int i = 0; i < n; i++) {
arr[i]=generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");

//Recordthestarttime
clock_t start= clock();

Dept.of AIML, VKIT Page 19

 Analysis &Design of Algorithms Lab(BCSL404)

//Performselectionsort
selectionSort(arr, n);
//Recordtheendtime
clock_t end= clock();
//Calculatethetimetakenfor sorting
double time_taken=((double)(end-start)) / CLOCKS_PER_SEC;
//Output the time taken to sort for the current value of n
printf("\nTime taken tosort forn=%d: %lfseconds\n\n", n, time_taken);
// Displaysorted numbers
printf("Sorted numbers for n=%d:\n",n); for
(int i = 0; i < n; i++) {
printf("%d",arr[i]);
}
printf("\n\n");
//Free the dynamically allocated memory
free(arr);
return 0;
}

Output:

Dept.of AIML, VKIT Page 20

 Analysis &Design of Algorithms Lab(BCSL404)

10. Design and implement C/C++ Program to sort a given set of n integer elements using
Quick Sort method and compute its time complexity. Run the program for varied values of
n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The
elements can be read from a file or can be generated using the random number generator.

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

//Functiontoswaptwoelements
void swap(int* a, int* b) {
int temp =*a;
*a= *b;
*b =temp;
}

//Functiontopartitionthearrayandreturnthepivotindex
int partition(int arr[], int low, int high) {
int pivot=arr[high];
int i = (low - 1);

for(int j=low;j<=high-1;j++){
if (arr[j] < pivot) {
i++;
swap(&arr[i],&arr[j]);
}
}
swap(&arr[i+1],&arr[high]);
return (i + 1);
}

//FunctiontoperformQuickSort
void quickSort(int arr[],int low,int high){
if (low < high) {
int pi=partition(arr,low,high);

quickSort(arr, low, pi - 1);

quickSort(arr,pi+1,high);
}
}

//Function to generate random numbers between 0 and 999

int generateRandomNumber() {
return rand()% 1000;
}

Dept.of AIML, VKIT Page 21

 Analysis &Design of Algorithms Lab(BCSL404)

int main() {
//Set nvalue
int n =6000;

// Allocate memoryforthe array

int* arr=(int*)malloc(n * sizeof(int));

//Generaterandomelementsforthearray
srand(time(NULL));
printf("Random numbers for n=%d:\n",n);
for (int i = 0; i < n; i++) {
arr[i]=generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");

//Recordthestarttime
clock_t start= clock();

// Perform quick sort

quickSort(arr,0,n-1);

//Recordtheendtime
clock_t end=clock();

//Calculatethetimetakenfor sorting
double time_taken=((double)(end-start))/ CLOCKS_PER_SEC;

//Output thetime takento sort forthe currentvalue ofn

printf("\nTime taken to sort forn=%d: %lf seconds\n\n", n, time_taken);

// Displaysorted numbers
printf("Sorted numbers for n=%d:\n",n); for
(int i = 0; i < n; i++)
{
printf("%d",arr[i]);
}
printf("\n\n");

//Free the dynamically allocated memory

free(arr);

return 0;
}

Dept.of AIML, VKIT Page 22

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 23

 Analysis &Design of Algorithms Lab(BCSL404)

11. Design and implement C/C++ Program to sort a given set of n integer elements using
MergeSort method andcomputeits timecomplexity.Run theprogramforvaried values of n>
5000, and record the time taken to sort. Plot a graph of the time taken versus n. The
elements can be read from a file or can be generated using the random number generator.

#include <stdio.h>
#include<stdlib.h>
#include <time.h>
//Merge two subarraysof arr[]
//First subarray is arr[l..m]
//Second subarrayis arr[m+1..r]
void merge(int arr[],int l,int m,int r){
int i, j, k;
int n1=m-l+1;
int n2 = r - m;

//Create temporary arrays

int L[n1], R[n2];

//Copy data to temporary arrays L[]andR[]

for (i = 0; i < n1; i++)
L[i]=arr[l+i];
for (j = 0; j < n2; j++)
R[j]=arr[m+1+j];

//Mergethetemporaryarraysbackinto arr[l..r]
i=0;//Initial indexof firstsubarray
j=0;//Initial index ofsecondsubarray
k=l;//Initial indexofmergedsubarray
while (i < n1 && j < n2) {
if(L[i] <=R[j]) {
arr[k]=L[i];
i++;
}else {
arr[k]=R[j];
j++;
}
k++;
}

//CopytheremainingelementsofL[],ifthereareany
while (i < n1) {
arr[k]=L[i];
i++;
k++;
}

Dept.of AIML, VKIT Page 24

 Analysis &Design of Algorithms Lab(BCSL404)

//CopytheremainingelementsofR[],if there are any

while (j < n2) {
arr[k]=R[j];
j++;
k++;
}
}

//Mergesort function
void mergeSort(int arr[],int l,int r){
if (l < r) {
//Sameas(l+r)/2,but avoids overflow for large l and r
int m = l + (r - l) / 2;

//Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

//Mergethesortedhalves
merge(arr, l, m, r);
}
}

//Functiontogeneraterandomnumbersbetween0and999
int generateRandomNumber() {
return rand()% 1000;
}

int main() {
//Setnvalue
int n = 6000;

// Allocate memoryforthe array

int* arr=(int*)malloc(n * sizeof(int));

//Generaterandomelementsforthearray
srand(time(NULL));
printf("Random numbers for n=%d:\n",n);
for (int i = 0; i < n; i++) {
arr[i]=generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");

//Recordthestarttime

Dept.of AIML, VKIT Page 25

 Analysis &Design of Algorithms Lab(BCSL404)

clock_t start= clock();

// Perform merge sort
mergeSort(arr,0,n-1);
//Recordtheendtime
clock_t end=clock();
//Calculatethetimetakenfor sorting
double time_taken=((double)(end-start))/ CLOCKS_PER_SEC;

//Output thetime takento sort forthe currentvalue ofn

printf("\nTimetaken tosort forn=%d: %lfseconds\n\n", n, time_taken);
// Displaysorted numbers
printf("Sorted numbers for n=%d:\n",n);
for (int i = 0; i < n; i++) {
printf("%d",arr[i]);
}
printf("\n\n");
//Freethedynamicallyallocatedmemory
free(arr);
return 0;
}

Output:

Dept.of AIML, VKIT Page 26

 Analysis &Design of Algorithms Lab(BCSL404)

12. Design and implement C/C++ Program for N Queen's problem using Backtracking.
#include <iostream>
#include <vector>
using namespace std;

// Function to print the solution board

void printSolution(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}

// Function to check if it's safe to place a queen at board[row][col]

bool isSafe(vector<vector<char>>& board, int row, int col) {
// Check the column for previous queens
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}

// Check the upper-left diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}

// Check the upper-right diagonal

for (int i = row, j = col; i >= 0 && j < board.size(); i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}

return true;
}

// Recursive function to solve the N Queens problem

bool solveNQUtil(vector<vector<char>>& board, int row) {
int n = board.size();

// If all queens are placed, return true

if (row == n) {
return true;
}
 Analysis &Design of Algorithms Lab(BCSL404)

// Try placing a queen in each column of the current row

for (int col = 0; col < n; col++) {
// Check if it's safe to place the queen
if (isSafe(board, row, col)) {
board[row][col] = 'Q'; // Place queen

// Recur to place the rest of the queens

if (solveNQUtil(board, row + 1)) {
return true;
}

// If placing queen in board[row][col] doesn't lead to a solution, backtrack

board[row][col] = '-';
}
}

// If the queen cannot be placed in any column of this row, return false
return false;
}
// Function to solve the 4 Queens problem
void solve4Queens() {
int n = 4;
vector<vector<char>> board(n, vector<char>(n, '-'));

// Start solving from the first row

if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist" << endl;
return;
}

// Print the solution

printSolution(board);
}

// Driver function
int main() {
cout << "Solution for 4 Queens problem:" << endl;
solve4Queens();
return 0;
}

Dept.of AIML, VKIT Page 27

 Analysis &Design of Algorithms Lab(BCSL404)

Output:

Dept.of AIML, VKIT Page 28

 Analysis &Design of Algorithms Lab(BCSL404)

VIVAQUESTIONS

1. What is an Algorithm?
Algorithm is a Step by step procedure to Solve a given problem for a finite number of input
producing finite number of output with desired output.
2. What is a Flow Chart?
Flow chart is a Graphical Representation of a solution to the Problem.
3. What is the difference between Algorithm,FlowChart,Program?
 Algorithm specifies the different things to be followed for solving a Problem.
 FlowChart is a Graphical Representation of a Solution to the Problem.Both
Algorithm and Flow Chartare Machine Independent.
 Program is a Set of Instructions which is used a satool to communicate to the machine
to get our workdone,Program is Machine Dependent for particular Machine.
4. What is the Aim of DAA labor why we need to study DAA Lab
DAA is a discipline, where we are dealing with designing or writing the algorithm
keeping in Consideration of Space and Time Complexity, Such that Our Algorithm
should execute in a very minimum amount of time by Minimum Space or RAM.
5. Define Space and Time Complexity?Among this which one is more prioritized?
Space Complexeity is a measure of Amount of Space taken by a Program to finish its
Execution.
Time Complexeity is a measure of amount of time taken by a program to complte its
Execution.DependingUpon Application it is considered,EX:For Mobile or Handheld
Devices,We give Prefernce for both Spaceand time.
For a Huge and Inter active Systems like Web Applications we give more Preferences to
time Complexeity.
6. What is Design and what is Analysis of a Program?
Design is a Process of Writing an algorithm to a given Problem so that it should accept
finite number of input and finite number of output with a definite output and Should Exit
appropriately.
Analysis:Analysis is a next Phase of Writing an Algorithm ,in this phase we calculate
the Efficiency of an Algorithm i.e time and space needed by an algorithm.

Dept.of AIML, VKIT Page 29

 Analysis &Design of Algorithms Lab(BCSL404)

7. Write the general plan for analyzing the recursive algorithms.

 Identify the inputs.
 Identify the output is depended only on number of inputs.
 Identify the Basic Operation in Algorithm.
 Form or write the Recursive Relation to the Algorithm.
8. What are the various notations used to write an algorithm?
(i)Pseudocode(ii)NaturalLanguageandetc..
9. What is a Pseudocode?
It’s a notation which is having the combination of Programming Constructs and Englishl \ike
Statements.

10. What is the Time Complexeity of BubbleSort,SelectionSort,MergeSort,Quick

Sort?(L3)
BubbleSort-n2,SelectionSort-n2MergeSort-nlog.n Quick
Sort -nLogn, Worst case for Quick Sort- n2
11. Which sorting algorithm is more Efficient and why?
QuickSorting is More Efficient ,because this algorithm is
instablealgorithmandinplace.
12. What do you mean by the term Instable Algorithms?
The Instable Algorithms are one,which divides the arrayas certainly depending upon
pivot or key elementand hence i index precedes index j
13. Which algorithms are faster?
Instable Algorithms are much Faster compared to Stable Algorithms.
14. ForwhattypeofinstanceMergesortdobetterthanQuick Sort?
ForaLargerinputandasortedinputvalues.
15. For what type of instance Quick sort do better than MergeSort?
For Smaller Set of input numbers.
16. What are Inplace Algorithms?
Inplace Algorithms are the one which doesn't occupies ExtraSpace.
17. Write the order of growth terms asper the time Execution in Ascending Order.
logn,n,nlogn,n2,n3,...... nn,2n,n!

Dept.of AIML, VKIT Page 30

 Analysis &Design of Algorithms Lab(BCSL404)

18. What is Brute Force Technique?When We Should Use?

Brute Force is a straight Forward Technique to solve a problem, We used to solve a
Problem through this approach when we don't have sufficient data to solve a problem in
Efficient Way.
19. What is the difference between Divide and Conquer,Decrease and Conquer?
Divide and Conquer can be solved to solve a problem with a larger data set
andwhen there is no dependency between any of the data sets.
 Divide and Solve as Small as Smallsets.
 Conqueror Merge it get one final result ant dataset.
Decrease and Conquer is almost similar to Divide and Conquer but we are finding a
solutions to the problemin a different variations, EX:Decrease by Constant (Usually
byOne),Decrease byConstant factorwhich is almost similar to Divide and Conquer
Technique(Usually by two),Decrease by Variable(The Dividing Criteria changes for
each iteration depends upon the data set.
20. Define Greedy Technique.
Greedy Technique is always applied for the problem of the type optimization type,
which reduces loss and increases profit.
21. Define Optimal and Feasible Solution.
Optimal Solution is a solution which is best among N Feasible Solution. Feasible Solution is
a solution which Satisfies a Problem Constraints/conditions.
22. Can A Problem solved by all the algorithmic Techniques.
Yes,but some problems will give better results with some Algorithmic Technique
and it may give worst result when it is applied with other technique.
23. State and Explain Knapsack Problem.
Filling the Maximum number of items to the Knapsack (Container) Which
Increases the profit and decreases the Loss.
24. Which one is Most Admired algorithmic Technique?
Dynamic Programming.
25. What is Spanning tree and Minimum Spanning tree?
AtreeWithout Cycles are called as Spanning tree.A Minimum Spanning Tree is a
spanning tree which yeilds the very less Cost when all the edges cost summed up.

Dept.of AIML, VKIT Page 31

 Analysis &Design of Algorithms Lab(BCSL404)

26. How Many Spanning Tree can a Tree can have?

A tree can have 1 to many number of Possible ways of Spanning Tree.

27. Differentiate between Prims and Kruskals Algorithm for finding MST.
In Prims We consider any one vertex in the graph as Source and We compute the
distance from that source to other vertices ,after computing the vertices which has
minimum value among (n-1) vertices is added to tree vertices and that respective edges
added to tree Edges Set.The above mentioned Process continues till we reach (n-1)
vertices.
In Kruskals we first arrange the edges in Ascending Order and then we start to form the
tree which wont formcycles,if adding that edges forms cycles then that edges is dropped
fromadding to tree edges.The above saidprocess is continues till we reach the count of
(n-1)Vertices.

28. What is the Application of Prims and Kruskals Algorithm?

In Network sto remove the Cyclicity of the Network.
29. Explain Job Sequencing With Deadlines?
Placing or scheduling them aximum number of Jobs to a machine without tv iolating
the deadlines constraint of any of the Jobs in Sequence.
30. Why the Name Bubble Sort named?
Because in first Pass the first highest data will bubbles up,so since the largest
element bubbles up in the first and second largest element bubbles up in the Second pass
and so on, so hence the name bubble sort.
31. Why the Name Selection Sort?(L3)
The Selection sort is named because we initially first select an arrays first element as
minimum and will compare with other elements ,so in pass one first least elementgoes
to the first position and soon so forth for 2nd,3rd and so on. Selecting
32. What is the difference between Brute forcestring smatching to Horspool String
Matching Method? (L2)In brute Force we compare each and everyelement of the
text to the pattern byshiftingthe text positionbyone and in Horspool method we shift
it bynumber of shift positions recorded in theshift table.

Dept.of AIML, VKIT Page 32

 Analysis &Design of Algorithms Lab(BCSL404)

33. Explain Merge Sort?

In Merge Sort will divide the entire input set by 2 until we reach low<high and later
will find a solution to each item by comparing half of the array data set to the other
half array data set and finally wemergeit to form a sinle array(conquer)
34. What is the Basic Operation sin Merge sort and Quick sort?
InMergeSorttheBasicOperationsisComparisionsandinQuicksortbasicOperations is
Partitioning and hence also known as partitioning sort.
35. Why the Insertion Sort?
We are Inserting an element to its suitable place by comparing elements for each pass.
36. What is the Use of DFS and BFS?
DFS and BFSboth used to check the Connectivity of a graph,Cyclicity in a
graph,Spanning tree of agraph.
37. Differentiate between DFS and BFS.
DFS and BFS are both the Graph Traversing Technique,in which DFS Traverse the
Graph in adepth wise(Vertical) and BFS Traverse the Graph from left to
right(Horizontal)
38. Which Data structures used in BFS and DFS.
BFS Uses Queue as its data structure and DFS uses as stack its Data structure.
39. What are backed ges in DFS and Cross Edge sin BFS.
Back Edges and Cross edges are the Edges which already visited by a ancestor node.
40. What is Topological Sorting?
Topological Sorting is a Sorting Technique used for sortingVertices in the Graph.
41. What is the Conditions necessary for a Topological Sorting?
For a Topological Sorting the Graph Should be DAG(DirectedAcyclicGraph)
42. What are the Different methods used to solve a topological Sorting ?
1. Source Removal Method
2. Using DFS based Scheme.
43. What is the Use of Topological Sorting?
Use of Topological Ordering is in the field of Operating System for Scheduling and in
Networks,Automation and Robotics.

Dept.of AIML, VKIT Page 33

 Analysis &Design of Algorithms Lab(BCSL404)

44. What is Dijikstra's Algorithm?

Dijikstra's Algorithm is Used to find the Single shortest Path from source to the other
vertex.
45. What is a graph?
Graph is a component which is having a set of Edges and verticesG={V,E}
46. What are the different ways that can be represents a graph?
Adjaceny Matrix and Adjacency List.
47. What is Adjacency Matrix?
Is a Matrix which illustrates the Graph in the form of Matrix,if itis a weights Graph
then we initialize the value of the cost in that position(i,j) or else simply we write 1 to
mention ther exist an edge between (i,j) OR else we use 0 or 9999 to mention non
connectivity of a graph.
48. What is the limitations of Algorithms?
Algorithm can't find the better the soltions when we come across the tight lower
bound,So wecanfindthebettersolutinswhichisnotpossiblewithAlgorithmicway.To find
the Tight lower bound we use DecisionTrees.
49. What is Tight lower Bound?
It is a Lower bound which is a best lower bound for an problem,beyond that no
algorithm will produce better results.
50. What are Decision Trees?
DecisiontreesarealsoknownasComparisionTreesusedtofindthetightlower bound for a
particular Problem EX:Tight Lower Bound For Sorting is n.logn
andtightlowerboundforSearchingislognwhichisnotpossibletogetthebetterresult.
51. Whatisapolynomialproblem(P-type)
P-type problemare decision problems in whichwe can find the solutions in a
polynomial time and is oftype deterministic.
52. What is NP-problem?
NP-Problem belongs to decision problem and these problems are Non Deterministic
Polynomial i.e for which the problemdoesn't have deterministic solutions and Can be
solved in Polynomial time
Thereare2phasesinsolvingaproblem.
(i) Guessing(Non-Deterministicstage)ProducingNnumberofCandidateOutputs.

Dept.of AIML, VKIT Page 34

 Analysis &Design of Algorithms Lab(BCSL404)

(ii) Verification(DeterministicStage)VerifyingThecorrectnessofNNumberof
Candidate Outputs.
53. What is NP-Complete Problems?
Np_Complete Problems belongs to Decision problems and NP type Problems .
These problems can be find the solutions byconverting or reducing to the problem
which we know theSolutions.

54. What is atrivial lowerbound?

Trivialboundcanbederivedbyformulatingthenumberofinputsthat hastobegiven and
number ofoutputs that has to be generated.
55. Explain BactrackingW.r.t
(I)SubsetProblem(ii)N-QueensProblem

56. ExplainSubsetProblem.
In a given Set S ,find the Subset,in which the sum of all subset elements is equal tothe
sum d which is predefined in a problem.
57. ExplainN-QueensProblem.(
N-Queens Problem is of Placing a N-Queens in a N*N Chess board such that No 2-
Queens Should be placed in the same Row,Column and same diagnol(N=Should
consider both principal diagonal elements)
58. What is HamiltonianCircuit?(L2)
Hamiltonian circuit is a problem in which that circuit starts from a source vertex and
has other vertex in anyorder without repeatingandShould endwiththeSourcevertex
onlyi.e source and Destination vertexshould be same.
59. Explain the ProblemofTSP.(L2)
Travelling Sales Person Problem is a problem in which he should Visit N number of
cities with a minimumnumber of Cost by visiting every city Exactly one and the city
what he is started should end with same city.
60. What is the Concept of Dynamic Programming?(L3)
Deriving a Solution to thebasic Condition and Extracting thesolutions for therest of
the other data sets by Previously drawnd Solution.Computer to other algorithmic
Technique Dynamic Programming because it avoids lot of reworking on the same
Solution what we have solved in the earlier phases of deriving the solution to the

Dept.of AIML, VKIT Page 35

 Analysis &Design of Algorithms Lab(BCSL404)

problem.
61. What is the goal of Warshalls Algorithm?(L3)
Warshall’s algorithm is to find the shortest distance between a node to all the other
nodes in thegraph.It Uses thePropertyofTransitiveClosurei.eifthereexist apath
between (i,k) and (k,j) then there surelyexist a path between (i,j)
(i,k)&(k,j)---◻(I,J)
62. What is the use of Floyds algorithm?(L3)
It is use to find the All pairs shortest Path of an Graph.

Dept.of AIML, VKIT Page 36