Channabasaveshwara Institute of Technology

(Affiliated to VTU, Belgaum & Approved by AICTE, New

Delhi) (NAAC Accredited & ISO 9001:2015 Certified
Institution)
NH 206 (B.H. Road), Gubbi, Tumkur – 572 216. Karnataka.

Department of Information Science & Engineering

Analysis and Design of Algorithms Lab

Subject Code: BCSL404

B.E – 4th Semester

Lab Manual - 2023-24

Page | 1
 Channabasaveshwara Institute of Technology
(Affiliated to VTU, Belgaum & Approved by
AICTE, New Delhi) (NAAC Accredited &
ISO 9001:2015 Certified Institution)
NH 206 (B.H. Road), Gubbi, Tumkur – 572 216. Karnataka.
Analysis & Design of Algorithms Lab Semester 4
Course Code BCSL404 CIE Marks 50
Teaching Hours/Week (L:T:P: S) 0:0:2:0 SEE Marks 50
Credits 01 Exam Hours 2
Examination type (SEE) Practical
Course objectives:
● To design and implement various algorithms in C/C++ programming using suitable development tools to address different
computational challenges.
● To apply diverse design strategies for effective problem-solving.
● To Measure and compare the performance of different algorithms to determine their efficiency and suitability for specific tasks.

Sl.No Experiments
1 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Kruskal's algorithm.
2 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Prim's algorithm.
3 a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's algorithm.
b. Design and implement C/C++ Program to find the transitive closure using Warshal's
algorithm.

4 Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted
connected graph to other vertices using Dijkstra's algorithm.
5 Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given
digraph.
6 Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.
7 Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack
problems using greedy approximation method.
8 Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n
positive integers whose sum is equal to a given positive integer d.
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.
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.

Page | 2
 11 Design and implement C/C++ Program to sort a given set of n integer elements using Merge 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.
12 Design and implement C/C++ Program for N Queen's problem using Backtracking.

Course outcomes (Course Skill Set):

At the end of the course the student will be able to:
1. Develop programs to solve computational problems using suitable algorithm design strategy.
2. Compare algorithm design strategies by developing equivalent programs and observing running times for
analysis (Empirical).
3. Make use of suitable integrated development tools to develop programs
4. Choose appropriate algorithm design techniques to develop solution to the computational and complex
problems.
5. Demonstrate and present the development of program, its execution and running time(s) and
record the results/inferences.
Assessment Details (both CIE and SEE)
The weightage of Continuous Internal Evaluation (CIE) is 50% and for Semester End Exam (SEE) is 50%. The minimum
passing mark for the CIE is 40% of the maximum marks (20 marks out of 50) and for the SEE minimum passing mark is
35% of the maximum marks (18 out of 50 marks). A student shall be deemed to have satisfied the academic
requirements and earned the credits allotted to each subject/ course if the student secures a minimum of 40% (40 marks
out of 100) in the sum total of the CIE (Continuous Internal Evaluation) and SEE (Semester End Examination) taken
together

Continuous Internal Evaluation (CIE):

CIE marks for the practical course are 50 Marks.
The split-up of CIE marks for record/ journal and test are in the ratio 60:40.
● Each experiment is to be evaluated for conduction with an observation sheet and record write-up. Rubrics for the
evaluation of the journal/write-up for hardware/software experiments are designed by the faculty who is handling
the laboratory session and are made known to students at the beginning of the practical session.
● Record should contain all the specified experiments in the syllabus and each experiment write-up will be
evaluated for 10 marks.
● Total marks scored by the students are scaled down to 30 marks (60% of maximum marks).
● Weightage to be given for neatness and submission of record/write-up on time.
● Department shall conduct a test of 100 marks after the completion of all the experiments listed in the syllabus.
● In a test, test write-up, conduction of experiment, acceptable result, and procedural knowledge will carry a
weightage of 60% and the rest 40% for viva-voce.
● The suitable rubrics can be designed to evaluate each student’s performance and learning ability.
● The marks scored shall be scaled down to 20 marks (40% of the maximum marks).
The Sum of scaled-down marks scored in the report write-up/journal and marks of a test is the total CIE marks scored by
the student.

Page | 3
 BCSL404-Algorithms Lab IV Sem ISE

● SEE shall be conducted jointly by the two examiners of the same institute, examiners are appointed by the Head of
the Institute.
● The examination schedule and names of examiners are informed to the university before the conduction of the
examination. These practical examinations are to be conducted between the schedule mentioned in the academic
calendar of the University.
● All laboratory experiments are to be included for practical examination.
● (Rubrics) Breakup of marks and the instructions printed on the cover page of the answer script to be strictly
adhered to by the examiners. OR based on the course requirement evaluation rubrics shall be decided jointly by
examiners.
● Students can pick one question (experiment) from the questions lot prepared by the examiners jointly.
● Evaluation of test write-up/ conduction procedure and result/viva will be conducted jointly by examiners.
General rubrics suggested for SEE are mentioned here, writeup-20%, Conduction procedure and result in -60%, Viva-
voce 20% of maximum marks. SEE for practical shall be evaluated for 100 marks and scored marks shall be scaled
down to 50 marks (however, based on course type, rubrics shall be decided by the examiners)
Change of experiment is allowed only once and 15% of Marks allotted to the procedure part are to be made zero.
The minimum duration of SEE is 02 hours

Suggested Learning Resources:

● Virtual Labs (CSE): http://cse01-iiith.vlabs.ac.in/
Semester End Evaluation (SEE):
● SEE marks for the practical course are 50 Marks.

Dept. of ISE, CIT, Gubbi- 572 216 Page No.4

BCSL404-Algorithms Lab IV Sem ISE

CONTENT SHEET

Sl.No. Name of Program Page

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

2. Design and implement C/C++ Program to find Minimum Cost Spanning

Tree of a given connected undirected graph using Prim's algorithm.

3. a. Design and implement C/C++ Program to solve All-Pairs Shortest

Paths problem using Floyd's algorithm.
b. Design and implement C/C++ Program to find the transitive
closure using Warshal's algorithm.

4. Design and implement C/C++ Program to find shortest paths from a

given vertex in a weighted connected graph to other vertices using
Dijkstra's algorithm.

5. Design and implement C/C++ Program to obtain the Topological

ordering of vertices in a given digraph.

6. Design and implement C/C++ Program to solve 0/1 Knapsack

problem using Dynamic Programming method.

7. Design and implement C/C++ Program to solve 0/1 Knapsack

problem using Dynamic Programming method.

8. Design and implement C/C++ Program to find a subset of a given set

S = {sl , s2,.....,sn} of n positive integers whose sum is equal to a given
positive integer d.

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.

Dept. of ISE, CIT, Gubbi- 572 216 Page No.5

BCSL404-Algorithms Lab IV Sem ISE

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.
11. Design and implement C/C++ Program to sort a given set of n integer elements
using Merge 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.
12.
Design and implement C/C++ Program for N Queen's problem using Backtracking.

Dept. of ISE, CIT, Gubbi- 572 216 Page No.6

BCSL404-Algorithms Lab IV Sem ISE

Algorithm: Abdullah Muhammad bin Musa al-Khwarizmi was the founder of

Algorithm. Algorism and algorithm stem from Algoritmi, the Latin form of his name
Khwarizmi.

Fig: Founder of algorithm Musa al-Khwarizmi

Algorithm: An algorithm is defined as finite sequence of unambiguous instructions followed

to accomplish a given task.

An algorithm must satisfy the following criteria:

Input: Each algorithm should have zero or more inputs. The range of inputs for which
algorithm works should be satisfied.
Output: The algorithm should produce correct results. At least one output has to be
produced.
Definiteness: Each instruction should be clear and unambiguous.
Effectiveness: The instructions should be simple and should transform the given input to the
desired output.
Finiteness: The algorithm must terminate after a finite sequence of instruction.

Analysis framework:
The efficiency of the algorithm depends on two factors:
Space efficiency
Time efficiency
Space efficiency: The space efficiency of an algorithm is the amount of memory required to
run program completely and efficiently.
Components that affect space efficiency:

Dept. of ISE, CIT, Gubbi- 572 216 Page No.7

BCSL404-Algorithms Lab IV Sem ISE

Program space
Data space
Stack space
Time efficiency: The Time efficiency of an algorithm is measured purely on how fast a given
algorithm is executed. Since the efficiency of an algorithm is measured using time, the word
time complexity is often associated with an algorithm.
Components that affect space efficiency:
Speed of the computer
Choice of the programming language
Compiler used
Choice of the algorithm
Number of inputs/outputs
Size of inputs/outputs

Worst case, best case and average case efficiency

An item we are searching for may be present in the very first location itself.
In this case only one item is compared and this is the best case.
The item may be present some where in the middle which definitely takes some time.
Running time is more when compared to the previous case for the same value of n. Since we
do not know where the item is we have to consider the average number of cases and hence
this situation is an average case.
The item we are searching for may not be present in the array requiring n number of
comparisons and running time is more than the previous two cases. This may be considered
as the worst case.
Asymptotic notations:
The value of a function may increase or decrease as the value of n increases.
The asymptotic behavior of a function is the study of how the value of a function varies for
large value of n where n is the size of the input. Using the asymptotic behavior of a function,
we can easily find the time efficiency of an algorithm.
Example Algorithm:
ALGORITHM GCD (M, N)
//description: computes GCD (M, N)
// input: M and N should be positive integers
//output: Greatest common divisor of M and N

Dept. of ISE, CIT, Gubbi- 572 216 Page No.8

BCSL404-Algorithms Lab IV Sem ISE

While N! =0 do
RM%N //compute the remainder
MN //Assign N to M
N R // Assign remainder to N
End while
Return M //Return the GCD

Understanding the problem

Model development

Ascertain the capabilities of computational device.

Select exact/appropriate algorithms

Select the data structures

Design an algorithm

Prove algo correctness.

Analyze the algorithm.

Implement the algo

Program testing

fig: Phases in program development

Dept. of ISE, CIT, Gubbi- 572 216 Page No.9

BCSL404-Algorithms Lab IV Sem ISE

Parallel Programming:
In parallel programming, the processing is broken up into parts, each of which can be
executed concurrently. The instructions from each part run simultaneously on different CPUs.
These CPUs can exist on a single machine, or they can be CPUs in a set of computers
connected via a network.
It is possible to write parallel programming for multiprocessors using MPI and
OpenMP

OpenMP:
 OpenMp is an application programming interface (API) for parallel programming on
multiprocessors
 It consists of a set of compiler directives and a library of support functions
 OpenMp works in conjunction with Standard Fortran, C or C++

Steps to execute parallel programming:

1. To write the program “vi filename.c”
2. For Compiling “cc –fopenmp filename.c”
3. To run the program ./a.out

Dept. of ISE, CIT, Gubbi- 572 216 Page No.10

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 1 Date: __ /__ / _____

Selection Sort
(Sorting Problem)

1. 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
Aim:
Sort a given set of elements using the Selection sort method and determine the
time required to sort the elements. Repeat the experiment for different values of
n, the number of elements in the list to be sorted and 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.

Design of Algorithm:
Algorithm: (Pseudo Code)
SelectionSort(A[0…n-1])
//sort a given array by select5ion sort
//input:A[0…n-1]of orderable elements
Output:Array a[0…n-1] Sorted in ascending order
for i<- 0 to n-2 do
min<-i
for j<-i+1 to n-1 do
if A[j]<A[min] min<-j
swap A[i] and A[min]

Code: (Implementation)

#include<stdio.h>
#include<unistd.h>
#include<time.h>
void selsort(int a[],int n)
{
int i,j,small,pos,temp;
for(j=0;j<n-1;j++)
{

Dept. of ISE, CIT, Gubbi- 572 216 Page No.11

BCSL404-Algorithms Lab IV Sem ISE

small=a[j];
pos=j;
for(i=j+1;i<n;i++)
{
if(a[i]<small)
{
small=a[i];
pos=i;
}
}
temp=a[j];
a[j]=small;
a[pos]=temp;
}
}
int main()
{
int a[100],i,n;
clock_t start,end;
float dura;
printf(" To sort the Integer elements using Selection Sort Method\n\n");
printf("\nEnter the Number of elements to be sorted which is less than the array size
50\n");
scanf("%d",&n);

if(n>0 && n<=50) // array bound check

{
for(i=0;i<n;i++)
{
a[i] = rand()%1000;
}
}
else
{
printf("Invalid input.. please try again...\n");
return -1;
}
printf("The Inputs generated by Random Number Generated are \n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
start=clock();
selsort(a,n);
usleep(100);
end=clock();

Dept. of ISE, CIT, Gubbi- 572 216 Page No.12

BCSL404-Algorithms Lab IV Sem ISE

dura=(end-start)/CLOCK_PER_SEC;
printf("\nTime taken is:%f",dura);
printf("\nSorted array is:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.13

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.14

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 2 Date: __ /__ / _____

Quick Sort
(Sorting Problem)

2) 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.
Aim:
Sort a given set of elements using the Quick sort method and determine the time
required to sort the elements. Repeat the experiment for different values of n,
the number of elements in the list to be sorted and 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.

Design of Algorithm:
Algorithm: (Pseudo Code)
Quick Sort:
ALGORITHM Quicksort (A[l….r])
//Sorts a subarray by quicksort
//Input: A subarray A[l…r] of A[0…n-1], defined by its left & right indices l & r
//Output: Subarray A[l…r] sorted in increasing order
if l < r
s  Partition (A[l…r]) // s is a split position
Quicksort ( A[l….s-1] )
Quicksort (A[s+1…r])

ALGORITHM Partition (A[l…r])

//Partitions a subarray by using its first element as pivot
//Input: A subarray A[l…r] of A[0…n-1], defined by its left & right indices l & r (l<r)
//Output: A partition of A[l…r],with the split position returned as this function’s value
P  A[l]
il; j  r+1
repeat
repeat i  i +1 until A[i] ≥ p
repeat j  j - 1 until A[i] ≥ p

Dept. of ISE, CIT, Gubbi- 572 216 Page No.15

BCSL404-Algorithms Lab IV Sem ISE

swap (A[i], A[j])

until i ≥ j
//undo last swap when i ≥ j
swap (A[l], A[j])
return j

Code: (Implementation)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
int ct,sw;
void quicksort(int a[],int low,int high)
{
int s;
//To check for boundary condition
if(low<high)
{
s=partition(a,low,high);
quicksort(a,low,s-1);
quicksort(a,s+1,high);
}
}
int partition(int a[],int low,int high)
{
int p,i,j,temp;
p=a[low];
i=low+1;
j=high;
while(1)
{
while(a[i]<=p && i<high)
i++,ct++; // count for the comparision
while(a[j]>p)
j--,ct++; // count for the comparision
if(i<j)
{
sw++; // count for the swap
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
sw++; // count for the swap
temp=a[low];

Dept. of ISE, CIT, Gubbi- 572 216 Page No.16

BCSL404-Algorithms Lab IV Sem ISE

a[low]=a[j];
a[j]=temp;
return j;
}
}
}
int main()
{
int a[5000],i,n;
printf(" To sort the Integer elements using Quick Sort Method\n\n");
printf("\nEnter the Number of elements to be sorted which is less than
the array size5000\n");
scanf("%d",&n);
if(n>0 && n<=5000) // array bound check
{
for(i=0;i<n;i++)
{
a[i] = rand()%1000;
}
}
else
{
printf("Invalid input.. please try again...\n");
return -1;
}
printf("The Inputs generated by Random Number Generated are \n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
quicksort(a,0,n-1);
printf("\n Sorted Integer Array \n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf(" \nThe number of Comparisions are : %d units",ct);
printf(" \nThe number of Swaps are : %d units",sw);
return 0;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.17

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.18

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.19

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 3 Date: __ /__ / _____

Merge sort
(Sorting Problem)

3)Design and implement C/C++ Program to sort a given set of n integer

elements using Merge 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.
Aim:
Sort a given set of elements using the Merge sort method and determine the
time required to sort the elements. Repeat the experiment for different values of
n, the number of elements in the list to be sorted and 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.

Algorithm:(Pseudo Code)
Merge Sort:
ALGORITHM Mergesort (A [0...n-1])
//Sorts array A [0…n-1] by recursive mergesort
//Input: An array A[0…n-1] of orderable elements
//output: Array A[0…n-1] sorted in increasing order

if n>1
Copy A[0..[n/2]-1] to B[0…[n/2]-1]
Copy A[0..[n/2]-1] to C[0…[n/2]-1]
Mergesort (B[0…[n/2]-1)
Mergesort (C[0…[n/2]-1)
Merge(B,C,A)

Merging Two List:

ALGORITHM Merge(B[0…p-1],C[0…q-1],A[0…p+q-1])
//Merges two sorted arrays into one sorted array
//Input: Arrays b[0..p-1] and C[0…q-1] both sorted
//Output: Sorted array A[0…p+q-1] of the elements of B & C

i 0; j0 ; k0
while i<p and j<q do
if B[i] ≤ C[j]
A[k]B[i] ; i  i+1
else A[k]C[j] ; j  j+1
k  k+1
if i=p
copy C[j…q-1] to A[k…p+q-1]
else copy B[i…p-1] to A[k…p+q-1]

Dept. of ISE, CIT, Gubbi- 572 216 Page No.20

BCSL404-Algorithms Lab IV Sem ISE

Code: (Implementation)
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<time.h>

void simple_merge(int a[],int low,int mid,int high);

void merge_sort(int a[],int low,int high);

void main()
{
int a[200],i,n;
double startTime,endTime;
printf("=========== Parallelized Merge Sort ==========\n");
printf("Enter the number of elements\n");
scanf("%d",&n);
randomize();
for(i=0;i<n;i++)
{
a[i]=random(1000);
}

printf("\n The random numbers generated are:\n");

for(i=0;i<n;i++)
printf("%d\t",a[i]);
startTime=omp_get_wtime();
merge_sort(a,0,n-1);
endTime = omp_get_wtime();
printf("Time taken is %10.9f\n",(double)(endTime-startTime));
printf("The sorted elements are:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
void simple_merge(int a[],int low,int mid,int high)
{
int i=low,j=mid+1,k=low,c[200];

while(i<=mid && j<=high)

{
if(a[i]<a[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=a[j];

Dept. of ISE, CIT, Gubbi- 572 216 Page No.21

BCSL404-Algorithms Lab IV Sem ISE

j++;
k++;
}
}
while(i<=mid)
c[k++]=a[i++];
while(j<=high)
c[k++]=a[j++];

for(i=low;i<=high;i++)
a[i]=c[i];
}
void merge_sort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
#pragma omp parallel sections
{
#pragma omp section
merge_sort(a,low,mid);
#pragma omp section
merge_sort(a,mid+1,high);
}
simple_merge(a,low,mid,high);
}
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.22

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.23

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.24

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 4 Date: __ /__ / _____

Knapsack problem:
(Combinatory Problem)

4) Design and implement C/C++ Program to find Minimum Cost Spanning

Tree of a given connected undirected graph using Kruskal's algorithm.

Aim:
To Implement 0/1 Knapsack problem using dynamic programming.

Problem Statement:
We are given n objects and a knapsack. Each object has a weight, w and the
maximum weight or capacity of the knapsack is M. Each object is associated with a value or
profit is carried when it is places in the knapsack.
Objective:
We must fill the knapsack which maximizes the profit control and the output is subset
of object number.
Algorithm:(Pseudo Code)
Algorithm Knapsack(i,j)
If j<weights[i]
Value= Knapsack(i-1,j)
Else
Value=max(knapsack(i-1,j),vaues[i]+ knapsack(i-1,j-weights[i]))
V[I,j]=value
Return v[i,j]

Code: (Implementation)
#include<stdio.h>
#define INF 999
#define MAX 100
int p[MAX],c[MAX][MAX],t[MAX][2];
int find(int v)
{
while(p[v])
v=p[v];
return v;
}
void union1(int i,int j)

Dept. of ISE, CIT, Gubbi- 572 216 Page No.25

BCSL404-Algorithms Lab IV Sem ISE

{
p[j]=i;
}
void kruskal(int n)
{
int i,j,k,u,v,min,res1,res2,sum=0;
for(k=1;k<n;k++)
{
min=INF;
for(i=1;i<n-1;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)continue;
if(c[i][j]<min)
{
u=find(i);
v=find(j);
if(u!=v)
{
res1=i;
res2=j;
min=c[i][j];
}
}
}
}
union1(res1,find(res2));
t[k][1]=res1;
t[k][2]=res2;
sum=sum+min;
}
printf("\nCost of spanning tree is=%d",sum);
printf("\nEdgesof spanning tree are:\n");

Dept. of ISE, CIT, Gubbi- 572 216 Page No.26

BCSL404-Algorithms Lab IV Sem ISE

for(i=1;i<n;i++)
printf("%d -> %d\n",t[i][1],t[i][2]);
}
int main()
{
int i,j,n;
printf("\nEnter the n value:");
scanf("%d",&n);
for(i=1;i<=n;i++)
p[i]=0;
printf("\nEnter the graph data:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
kruskal(n);
return 0;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.27

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.28

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.29

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 5 Date: __ /__ / _____

Prim’s Algorithm
( Graph Problem)

5) Design and implement C/C++ Program to find Minimum Cost Spanning

Tree of a given connected undirected graph using Prim's algorithm.
Aim:
To construct a minimum spanning tree of a weighted connected graph.

Algorithm:
ALGORITHM prim(G)
// Prim’s Algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G=(V,E)
//Output: ET , the set of edges composing a minimum spanning tree of G
VT <-- {V0}
ET <-- Ø
for i <-- 1 to |V| − 1 do
find a minimum-weight edge e* = (v*, u*) among all the edges (v,u)
such that v is in VT and u is in V − VT
VT <-- VT U {u*}
ET <-- ET U {e*}
return ET

Code: (Implementation)

#include<stdio.h>
#define INF 999
int prim(int c[10][10],int n,int s)
{
int v[10],i,j,sum=0,ver[10],d[10],min,u;
for(i=1;i<=n;i++)
{
ver[i]=s;
d[i]=c[s][i];
v[i]=0;
}
v[s]=1;

Dept. of ISE, CIT, Gubbi- 572 216 Page No.30

BCSL404-Algorithms Lab IV Sem ISE

for(i=1;i<=n-1;i++)
{
min=INF;
for(j=1;j<=n;j++)
if(v[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
v[u]=1;
sum=sum+d[u];
printf("\n%d -> %d sum=%d",ver[u],u,sum);
for(j=1;j<=n;j++)
if(v[j]==0 && c[u][j]<d[j])
{
d[j]=c[u][j];
ver[j]=u;
}
}
return sum;
}
void main()
{
int c[10][10],i,j,res,s,n;
printf("Prims Algorithm");
printf("\nEnter the number of nodes");
scanf("%d",&n);
printf("\nEnter the %d*%d matrix:\n",n,n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
printf("\nEnter the souce node:");
scanf("%d",&s);
res=prim(c,n,s);
printf("\nCost of minimum spanning tree is=%d",res);
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.31

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.32

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.33

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 6a Date: __ /__ / _____

Floyd’s Algorithm
(Graph Problem)

6) a. Design and implement C/C++ Program to solve All-Pairs Shortest

Paths problem using Floyd's algorithm.

Aim:
Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.
Parallelize this algorithm, implement it using OpenMP and determine the speed-
up achieved

Algorithm:
ALGORITHM Floyd (W [1…n, 1…n])
// Implements Floyd’s algorithm for all-pair shortest-paths problem
//Input: The weight matrix W of a graph with no negative-length cycle
//Output: The distance matrix of the shortest paths’ lengths D  W is not
//necessary if W can be overwritten

for k  1 to n do
for i  1 to n do
for j  1 to n do
D[i,j]  min { D[i,j], D[i,k] + D[k,j] }
return D

Code: (Implementation)

#include<stdio.h>
#include<omp.h
int min(int a,int b)
{
return a<b?a:b;
}
void floyd(int w[10][10],int n)
{
int i,j,k;

Dept. of ISE, CIT, Gubbi- 572 216 Page No.34

BCSL404-Algorithms Lab IV Sem ISE

#pragma omp parallel for private(i, j, k) shared(w)

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
}
void main()
{
int a[10][10],n,i,j;
double startTime,endTime;

printf("\n Enter the no. of vertices:");

scanf("%d",&n);
printf("\n Enter the cost matrix, 0-self loop and 999-no edge\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);

startTime=omp_get_wtime();
floyd(a,n);
endTime = omp_get_wtime();

printf("\n Shortest path matrix:\n");

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
printf("Time taken is %10.9f\n",(double)(endTime-startTime));
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.35

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.36

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.37

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 6b Date: __ /__ / _____

Warshall’s Algorithm
(Graph Problem)

6b. Design and implement C/C++ Program to find the transitive

closure using Warshal's algorithm.

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

Concepts Required:The transitive closure of a directed graph with n vertices can be
define as the n-by-n Boolean matrix T={t i,j },in which the element in the element in the I th
row and jth column is 1 if there exists a non trivial directed path from the I th vertex to j th
vertex Otherwise, t i,j is 0.

Algorithm:
ALGORITHM Warshall’s (A[1..n,1..n])
//Implements Warshall’s Algorithm to compute the transitive closure
//Input: The adjacency matrix A of a directed graph with n vertices
//Output: The transitive closure of the digraph
R(0) <-A
For k<- 1 to n do
For i<-1 to n do
For j<- 1 to n do
R(k) [ i,j]<- R(k-1) [ i,j] or R(k-1) [ i,k] and R(k-1) [ k,j]
Return R(n)

Code:

#include<stdio.h>
#include<stdlib.h>
void warshalls(int a[20][20], int n)
{
int i,j,k;
for (k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j] = a[i][j] || a[i][k] && a[k][j];
printf("\n The transitive closure is:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.38

BCSL404-Algorithms Lab IV Sem ISE

}
void main()
{
int a[20][20],n,i,j;
printf(" Compute transitive closure using Warshalls Algorithm \n");
printf("\n Enter the number of vertices of the graph:\n");
scanf("%d",&n);
if(n>0 && n <90)
{
printf("\n Enter the adjacency matrix:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
warshalls(a,n);
}
else
{
printf("Enter the valid number of vertices\n");
}
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.39

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.40

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.41

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 7 Date: __ /__ / _____

Dijkstra’s algorithm
(Graph Problem)

7) Design and implement C/C++ Program to find shortest paths from a

given vertex in a weighted connected graph to other vertices using
Dijkstra's algorithm.

Aim:
To find shortest paths from a given starting vertex to other vertices in a
weighted connected graph using Dijkstra's algorithm.

Algorithm: ( Pseudo Code)

ALGORITHM Dijkstra(G,s)
// Dijkstra’s algorithm for single-source shortest paths
// Input: A weighted connected graph G={V,E} with nonnegative weights & its
vertex s
// Output:The length dv of a shortest path from s to v & its penultimate vertex
pv for a vertex v in V

Intialiize(Q) //initialize vertex priority queue to empty

for every vertex v in V do
dv  ∞;pv  null
Insert (Q, v, dv) //initialize vertex priority in the priority queue
ds  0 ; Decrease(q,s,ds) //update priority of s with ds
Vt  Ø
for i  0 to |V| - 1 do
u*  Deletemin(Q) //delete the minimum priority element
Vt  Vt U {u*}
for every vertex u in V – Vt that is adjacent to u* do
if du* + w(u*,u)<du
du  du* + w(u*,u); pu  u*
Decrease (Q,u,du)

Dept. of ISE, CIT, Gubbi- 572 216 Page No.42

BCSL404-Algorithms Lab IV Sem ISE

Code:

#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10],int n,int s,int d[10])
{
int v[10],min,u,i,j;
for(i=1;i<=n;i++)
{
d[i]=c[s][i];
v[i]=0;
}
v[s]=1;
for(i=1;i<=n;i++)
{
min=INF;
for(j=1;j<=n;j++)
if(v[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
v[u]=1;
for(j=1;j<=n;j++)
if(v[j]==0 && (d[u]+c[u][j])<d[j])
d[j]=d[u]+c[u][j];
}
}
int main()
{
int c[10][10],d[10],i,j,s,sum,n;
printf("\nEnter the number of vertices of graph:");
scanf("%d",&n);
printf("\nEnter the weights of the edges of the graph\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
printf("\nEnter the souce vertex to find shorest path:");
scanf("%d",&s);
dijkstra(c,n,s,d);
for(i=1;i<=n;i++)
printf("\nShortest distance from %d to %d is %d",s,i,d[i]);
return 0;

Dept. of ISE, CIT, Gubbi- 572 216 Page No.43

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.44

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.45

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 8 Date: __ /__ / _____

Topological Ordering
(Sorting Problem)

8) Design and implement C/C++ Program to obtain the Topological

ordering of vertices in a given digraph.
Aim:
Obtain the Topological ordering of vertices in a given digraph.

Algorithm: ( Pseudo Code)

Step 1: Start

Step 2: Find the indegree of all the nodes

Step 3: Push all the nodes which is having the indegree zero

Step 4: Pop the element from the stack and delete all the edges outgoing from the deleted
node

Step 5: If the indegree of the node is zero, push that node to the stack.

Step 6: Repeat steps 3 to 5 until the stack is empty.

Step 7: Stop

Code:
#include<stdio.h>
int temp[10],k=0;
void sort(int a[][10],int id[],int n)
{
int i,j;
for(i=1;i<=n;i++)
{
if(id[i]==0)
{
id[i]=-1;
temp[++k]=i;
for(j=1;j<=n;j++)
{
if(a[i][j]==1 && id[j]!=-1)
id[j]--;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.46

BCSL404-Algorithms Lab IV Sem ISE

i=0;
}
}
}
void main()
{
int a[10][10],id[10],n,i,j;
printf("\nEnter the vertices of the graph:");
scanf("%d",&n);
for(i=1;i<=n;i++)
id[i]=0;
printf("\nEnter the matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
id[j]++;
}
}
sort(a,id,n);
if(k!=n)
printf("\nTopological ordering not possible");
else
{
printf("\nTopological ordering is:");
for(i=1;i<=k;i++)
printf("%d ",temp[i]);
}
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.47

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.48

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.49

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 9 Date: __ /__ / _____

Knapsack problem:
(Combinatory Problem)

9) Design and implement C/C++ Program to solve 0/1 Knapsack problem

using Dynamic Programming method.

Aim:
To Implement 0/1 Knapsack problem using dynamic programming.

Problem Statement:
We are given n objects and a knapsack. Each object has a weight, w and the
maximum weight or capacity of the knapsack is M. Each object is associated with a value or
profit is carried when it is places in the knapsack.

Objective:
We must fill the knapsack which maximizes the profit control and the output is subset
of object number.

Algorithm:(Pseudo Code)

Algorithm Knapsack(i,j)
If j<weights[i]
Value= Knapsack(i-1,j)
Else
Value=max(knapsack(i-1,j),vaues[i]+ knapsack(i-1,j-weights[i]))
V[I,j]=value
Return v[i,j]

Code:
#include <stdio.h>
#include <stdlib.h>
int w[10], v[10], a[10][10], t[10];
int c, i, n, j;
int max(int a, int b)
{
return (a > b) ? a : b;
}
void knapsack(int c, int n)

Dept. of ISE, CIT, Gubbi- 572 216 Page No.50

BCSL404-Algorithms Lab IV Sem ISE

{
int i, j;
for (i = 0; i <= n; i++)
{
for (j = 0; j <= c; j++)
{
if (i == 0 || j == 0)
a[i][j] = 0;
else if (w[i] > j)
a[i][j] = a[i - 1][j];
else
a[i][j] = max(a[i - 1][j], (a[i - 1][j - w[i]] + v[i]));
}
}
i = n;
j = c;
while (i > 0 && j > 0)
{
if (a[i][j] != a[i - 1][j])
{
t[i] = 1;
j = j - w[i];
}
i--;
}
}
void read_capacity()
{
printf("\n\n Enter the capacity of the knapsort:");
scanf("%d", &c);
if (c > 0)
read_numofitems();
else
{
printf("\n\n Invalid capacity, please try again...");
read_capacity();
}
}
int read_numofitems()
{
printf("\n\n Enter the number of items:\n");
scanf("%d", &n);
if (n > 0)
read_weights();

Dept. of ISE, CIT, Gubbi- 572 216 Page No.51

BCSL404-Algorithms Lab IV Sem ISE

else
{
printf("\n\n Invalid items, please try again...");
read_numofitems();
}
return 1;
}
int read_weights()
{
printf("\n\n Enter the corresponding weights:\n");
for (i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (i = 1; i <= n; i++)
{
if (w[i] > 0 && w[i] <= 999)
{
// Valid weight, continue to read values
}
else
{
printf("\n\n Invalid weights, please try again..");
read_weights();
}
}
read_values();
return 0;
}
int read_values()
{
printf("\n\n Enter the corresponding values:\n");
for (i = 1; i <= n; i++)
scanf("%d", &v[i]);
for (i = 1; i <= n; i++)
{
if (v[i] > 0 && v[i] <= 999)
{
// Valid value, continue to knapsack
}
else
{
printf("\n\n Invalid values, please try again...");
read_values();
}
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.52

BCSL404-Algorithms Lab IV Sem ISE

knapsack(c, n);
return 0;
}
int main()
{
printf("\t\t **THIS PROGRAM DEMONSTRATES KNAPSACK PROBLEM**");
read_capacity();
printf("\n\n Resultant matrix is:\n");
for (i = 0; i <= n; i++)
{
for (j = 0; j <= c; j++)
printf("\t%d", a[i][j]);
printf("\n");
}
printf("\n\n The optimal solution is: %d", a[n][c]);
printf("\n\n Items selected are:\n");
for (i = 1; i <= n; i++)
if (t[i] == 1)
printf("\t%d", i);
return 0;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.53

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.54

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.55

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 10 Date: __ /__ / _____

Sum of subset problem
(Combinatory Problem)

10) Design and implement C/C++ Program to find a subset of a given set S
= {sl , s2,.....,sn} of n positive integers whose sum is equal to a given positive
integer d.

Aim:
To Find a subset of a given set S = {sl,s2,.....,sn} of n positive integers
whose sum is equal to a given positive integer d. For example, if S= {1,2, 5, 6,
8} and d = 9 there are two solutions{1,2,6}and{1,8}.

Algorithm:
Step 1: Start
Step 2: Find the subset for given set
Step 3: Add the elements of the subset
Step 4: If the sum of the subset is equal to the given positive integer d, solution is found,
otherwise solution is not found.
Step 5: Stop

Code:

#include<stdio.h>
#include<math.h>
void subset(int num, int n, int x[])
{
int i;
for(i = 1;i<=n;i++)
x[i]=0;
for(i=n;num!=0;i--)
{
x[i] = num%2;
num = num/2;
}
}
void main()
{
int a[50],x[50],n,j,i,d,sum,present = 0;

Dept. of ISE, CIT, Gubbi- 572 216 Page No.56

BCSL404-Algorithms Lab IV Sem ISE

printf("Find subset of the given set whose sum is equal to a given integer \n");
printf("\n Enter the number of elements of the set\n");
scanf("%d",&n);
if(n>0 && n<90)
{
printf("\n Enter the elements of the set \n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
}
else
{
printf("Enter the valid number of elements\n");
}
printf("\n Enter the positive integer sum\n");
scanf("%d",&d);
if(d>0)
{
for(i=1;i<=pow(2,n)-1; i++)
{
subset(i,n,x);
sum=0;
for(j=1;j<=n;j++)
if(x[j]==1)
sum = sum +a[j];
if(d==sum)
{
printf("\n subset={");
present = 1;
for(j=1;j<=n;j++)
if(x[j]==1)
printf("%d ",a[j]);
printf("}=%d",d);
}
}
}
else
{
printf("Enter the valid positive integer\n");
}
if(present==0)
printf("solution does not exist");
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.57

BCSL404-Algorithms Lab IV Sem ISE

To compile the program Use ->cc filename.c-lm

Dept. of ISE, CIT, Gubbi- 572 216 Page No.58

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.59

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 11 Date: __ /__ / _____

N-queen’s problem

11) Design and implement C/C++ Program for N Queen's problem using
Backtracking.

Aim:
To Implement N Queen's problem using Back Tracking

Problem Statement:
The problem is to place n queens on an n by n matrix so that no two queens attack
each other by being in same row or in the same column or on the same diagonal.

Algorithm:

ALGORITHM NQueen(K,n)
// Using backtracking
// possible placements of ‘n’ queen on n*n chessboard

For i:= 1 to n do

If Place(k,i) then
x[k]=I;
if k=n then write x[1:n]
else NQueen(k+1,n)
end if
end for

ALGORITHM Place(k,i)
// return true if a queen can be placed in kth row and ith column
// otherwise return false

For j=I to k-1 do

If (x[j]=I ) or (abs(x[j]=i) = abs(j-k) then //two in the same
return false //column or in the same diagonal
Return true

Dept. of ISE, CIT, Gubbi- 572 216 Page No.60

BCSL404-Algorithms Lab IV Sem ISE

Code:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int b[20], count;
int place(int row, int col)
{
int i;
for(i = 1; i < row; i++)
{
if(b[i] == col || abs(b[i] - col) == abs(row - i))
return 0;
}
return 1;
}
void dis(int n)
{
int i, j;
printf("\n Solution number: %d\n", ++count);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(b[i] == j)
printf("\tQ");
else
printf("\t*");
}
printf("\n");
}
printf("\n\n");
}
void queen(int row, int n)
{
int col;
for(col = 1; col <= n; col++)
{
if(place(row, col))
{
b[row] = col;
if(row == n)
dis(n);
else

Dept. of ISE, CIT, Gubbi- 572 216 Page No.61

BCSL404-Algorithms Lab IV Sem ISE

queen(row + 1, n);
}
}
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.62

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.63

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.64

BCSL404-Algorithms Lab IV Sem ISE

Experiment No. 12 Date: __ /__ / _____

12.Design and implement C/C++ Program to solve discrete Knapsack and

continuous Knapsack problems using greedy approximation method.

Aim
This program first calculates the profit-to-weight ratio for each item, then sorts the
items based on this ratio in non-increasing order. It then fills the knapsack greedily by
selecting items with the highest ratio until the knapsack is full. If there's space left in the
knapsack after selecting whole items, it adds fractional parts of the next item. Finally, it prints
the optimal solution and the solution vector.

Code
#include <stdio.h>
#define MAX 50

int p[MAX], w[MAX], x[MAX];

double maxprofit;
int n, m, i;

void greedyKnapsack(int n, int w[], int p[], int m) {

double ratio[MAX];

// Calculate the ratio of profit to weight for each item

for (i = 0; i < n; i++) {
ratio[i] = (double)p[i] / w[i];
}

// Sort items based on the ratio in non-increasing order

for (i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (ratio[i] < ratio[j]) {
double temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;

int temp2 = w[i];

w[i] = w[j];
w[j] = temp2;

temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.65

BCSL404-Algorithms Lab IV Sem ISE

}
}

int currentWeight = 0;
maxprofit = 0.0;

// Fill the knapsack with items

for (i = 0; i < n; i++) {
if (currentWeight + w[i] <= m) {
x[i] = 1; // Item i is selected
currentWeight += w[i];
maxprofit += p[i];
} else {
// Fractional part of item i is selected
x[i] = (m - currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
}
}

printf("Optimal solution for greedy method: %.1f\n", maxprofit);

printf("Solution vector for greedy method: ");
for (i = 0; i < n; i++)
printf("%d\t", x[i]);
}

int main() {
printf("Enter the number of objects: ");
scanf("%d", &n);

printf("Enter the objects' weights: ");

for (i = 0; i < n; i++)
scanf("%d", &w[i]);

printf("Enter the objects' profits: ");

for (i = 0; i < n; i++)
scanf("%d", &p[i]);

printf("Enter the maximum capacity: ");

scanf("%d", &m);

greedyKnapsack(n, w, p, m);

return 0;
}

Dept. of ISE, CIT, Gubbi- 572 216 Page No.66

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.67

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.68

BCSL404-Algorithms Lab IV Sem ISE

VIVA questions

1. What is Algorithm?
2. Name the design techniques.
3. Which is efficient Sorting technique?
4. Which sorting technique has the lowest worst case efficiency?
5. Which sorting technique is space efficient?
6. Which sorting technique is Time efficient?
7. Define order of growth.
8. How binary search is advantageous over linear search?
9. What is CLK_TCK?
10. What is divide &conquer technique?
11. Give few problems which can be solved using divide &conquer technique.
12. What is dynamic programming?
13. Give few problems which can be solved using dynamic programming.
14. What is Back Tracking?
15. Define N-Queens problem.
16. What is Brute force Methodology?
17. What is Greedy Technique?
18. Give few problems which can be solved using Greedy Technique.
19. Which is the efficient method for finding MST?
20. What is MST?
21. What is DFS& BFS?
22. What is a heap?
23. What is Clock ( ) function?
24. Which is the header to include Clock function?
25. What are P NP problems?
26. Which are the String Matching algorithms?
27. What is Transitive closure?
28. Define Knapsack problem.
29. Define topological sorting?
30. Which algorithm used for checking graph is connected or not?

Dept. of ISE, CIT, Gubbi- 572 216 Page No.69

BCSL404-Algorithms Lab IV Sem ISE

Dept. of ISE, CIT, Gubbi- 572 216 Page No.70