Lab.

Report
On

ALOGORITHM LAB.
Submitted in partial fulfillment of the
requirements for the degree of

Bachelor of
Technology in
Information Technology

Submitted by

Group - 1 (IT-G2)
1806467 - Arunima, 1806473 – Hopansh Gahlot,
1806477 – Ishwari Kumari, 1806505 – Rohan
Kakar,
1806506 – Ronit Kumar Nayak, 1806510 – Sahil Kumar (GR)

Under the Guidance of

Prof. Anil Kumar Swain

School of Computer Engineering

Kalinga Institute of Industrial
Technology Deemed to be University,
Bhubaneswar

08 NOV 2020

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 School of Computer Engineering AUTUMN 2020
Kalinga Institute of Industrial Technology (KIIT), ALGO LAB.
Deemed to be University, Bhubaneswar REPORT
Algorithm Laboratory
Sem:6THSection:IT-G2Gr. Leader Roll1806510Name:Sahil Kumar
TA/ Instructor(s) 1. Prof. Rajeev Jena Faculty: Prof. Anil Kumar Swain
2. Prof. Meena Moharana

CONTENTS
Sl. Page
No. Title of Lab. Exercises No.
1. Review of Fundamentals of Data Structures 3
Fundamentals of Algorithmic Problem Solving-I:
2. Analysis of time complexity of small algorithms through 22
step/frequency count method.
Fundamentals of Algorithmic Problem Solving-II:
3. Analysis of time complexity of algorithms through asymptotic
notations.
Divide and Conquer Method:
4. Binary Search, Merge Sort, Quick Sort, Randomized Quick Sort
Heap & Priority Queues:
5. Building a heap, Heap sort algorithm, Min-Priority queue, Max-
Priority queue
Greedy Technique:
6. Fractional knapsack problem, Activity selection
problem, Huffman’s code
Dynamic Programming:
7. Matrix Chain Multiplication, Longest Common Subsequence

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 1

Review of Fundamentals of Data Structure

PROGRAM

CONTENTS
Prog. Page
No. Program Title No.
Write a program to store random numbers into an array of n integers and
1.1 then find out the smallest and largest number stored in it. n is the user 4
input.
Write a program to store random numbers into an array of n integers,
where the array must contain some duplicates. Do the following:
1.2 6
a) Find out the total number of duplicate elements.
b) Find out the most repeating element in the array.
Write a program to rearrange the elements of an array of n integers such
that all even numbers are followed by all odd numbers. How many
1.3 ways you can solve this problem? Write your approaches & strategy for
8
solving this problem.
Write a program that takes three variable (a, b, c) as separate parameters
1.4 and rotates the values stored so that value a goes to be, b, b to c and c to a 10
by using SWAP(x,y)function that swaps/exchanges the numbers x & y.
Let A be n*n square matrix array. WAP by using appropriate user defined
functions for the following:
a) Find the number of nonzero elements in A
1.5 12
b) Find the sum of the elements above the leading diagonal.
c) Display the elements below the minor diagonal.
d) Find the product of the diagonal elements.
Write a program to find out the second smallest and second largest
element stored in an array of n integers. n is the user input. The array
1.6 takes input through random number generation within a given range. 15
How many ways you can solve this problem? Write your approaches &
strategy for solving this problem
Write a program to swap pair of elements of an array of n integers from
1.7 starting. If n is odd, then last number will remain unchanged. 18
Write a program to display an array of n integers (n>1), where at every
index of the array should contain the product of all elements in the array
1.8 20
except the element at the given index. Solve this problem by taking
single loop and without an additional array.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 PROGRAM SOLUTIONS
1.1 Program Title:
Write a program to store random numbers into an array of n integers and then find out the
smallest and largest number stored in it. n is the user input.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

int largest(int arr[], int n)

{
int i;
int max = arr[0];
for (i = 1; i < n; i+
+) if (arr[i] >
max)
max =
arr[i]; return max;
}

int smallest(int arr[], int n)

{
int i;
int min = arr[0];
for (i = 1; i < n; i+
+) if (arr[i] <
min)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
int main()
{
int length = 0;
printf("Enter the length of the array:
"); scanf("%d",&length);
int arr[length];
for (int i = 0; i < length; i++)
{
arr[i] = rand()%99;
}
printf("The Array :\n");
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\nLargest = %d", largest(arr, sizeof(arr) / sizeof(arr[0])));
printf("\nSmallest = %d", smallest(arr, sizeof(arr) / sizeof(arr[0])));
printf("\n");
return 0;
}

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.2 Program Title:
Write a program to store random numbers into an array of n integers, where the array must
contain some duplicates. Do the following:
a) Find out the total number of duplicate elements.
b) Find out the most repeating element in the array.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

int duplicates(int arr[], int

length){ int count = 0,i,j;
for (i = 0; i < length; i++)
{
for(j = i + 1; j < length; j++)
{
if(arr[i] == arr[j])
{
count+
+;
break;
}
}
}
return count;
}

int mostOccurance(int arr[], int n)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 for (int i = 0;i<=n-1;i++)
{
int curr_freq = 1;
for (int j = i+1;j<=n-1;j++)
if (arr[j] == arr[i])
curr_freq = curr_freq + 1;

if (max_freq < curr_freq)

{
max_freq = curr_freq;
ans = arr[i];
}
else if (max_freq == curr_freq)
ans = ans<arr[i]?ans:arr[i];
}
return ans;
}

int main()
{
int length = 0;
printf("Enter the length of the array: ");
scanf("%d", &length);
int arr[length];
for (int i = 0; i < length; i++)
{
arr[i] = rand() % 5;
}
printf("The Array :\n");
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("No of duplicate elememts: %d \n",duplicates(arr,length));
printf("Most repeating elememts: %d \n",mostOccurance(arr,length));
return 0;
}

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.3 Program Title:
Write a program to rearrange the elements of an array of n integers such that all even numbers
are followed by all odd numbers. How many ways you can solve this problem? Write your
approaches & strategy for solving this problem.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

void swap(int *a, int

*b){ int temp = *a;
*a = *b;
*b = temp;
}

void EvenOdd(int arr[], int size){

int left = 0, right = size - 1;
while (left < right){
while (arr[left] % 2 == 0 && left <
right) left++;
while (arr[right] % 2 == 1 && left <
right) right--;

if (left < right){

swap(&arr[left],
&arr[right]); left++;
right--;
}

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
int main()
{
int size = 0;
printf("Enter the length of the array: ");
scanf("%d", &size);

int arr[size];
for (int i = 0; i < size; i+
+) arr[i] = rand() % 99;

printf("The Array :\n");

for (int i = 0; i < size; i+
+) printf("%d ", arr[i]);
printf("\n");

EvenOdd(arr,

size);

printf("Array after sorting: \n");

for (int i = 0; i < size; i++)
printf("%d ", arr[i]);

printf("\
n"); return

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.4 Program Title:
Write a program that takes three variable (a, b, c) as separate parameters and rotates the values
stored so that value a goes to be, b, b to c and c to a by using SWAP(x,y)function that
swaps/exchanges the numbers x & y.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

void swap(int *x, int

*y){ int temp = *x;
*x = *y;
*y = temp;
}

void rotate(int *a, int *b, int

*c){ swap(a,c);
swap(b,c);

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
void main(){
int a,b,c;
printf("Enter 3 integers:
"); scanf("%d%d%d", &a, &b,
&c);
printf("Before Rotation:\n a = %d\n b = %d\n c = %d\n", a, b, c);
rotate(&a, &b, &c);
printf("After Rotation:\n a = %d\n b = %d\n c = %d\n", a, b, c);

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.5 Program Title:
Let A be n*n square matrix array. WAP by using appropriate user defined functions for the
following:
a) Find the number of nonzero elements in A
b) Find the sum of the elements above the leading diagonal.
c) Display the elements below the minor diagonal.
d) Find the product of the diagonal elements.

Input/Output Screenshots:

RUN-1:

Source code:

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

void countZeros(int n,int arr[][n]){

int zeros = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(arr[i][j] == 0){
++zeros;
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 }

printf("Number of zeros = %d\n",zeros);

void sumLeading(int n,int arr[][n]){

int sum = 0;
for(int i = 0;i<n;++i){
for(int j=i+1;j<n;++j)
{
sum+=arr[i][j];
}
}

printf("Sum of elements above leading diagonal = %d\n",sum);

}

void showBelowMinorDiagonal(int n,int arr[][n]){

printf("Elements below minor diagonal are \n");
for(int i=1;i<n;++i)
{
for(int j=0;j<i;++j)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
}

void diagonalProduct(int n,int arr[][n]){

int product = 1;
for (int i = 0; i < n; i++)
{
product*=arr[i][i];
}

printf("Product of diagonal elements = %d\n",product);

int main(){
printf("Enter order of the matrix\n");
int input;
scanf("%d",&input);
const int n = input;
int arr[n][n];
for (int i = 0; i < n; i++)
{

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 printf("Enter arr[%d][1-%d]\n",i,n);
for (int j = 0; j < n; j++)
{
scanf("%d",&arr[i][j]);
}

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

{
for (int j = 0; j < n; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}

countZeros(n,arr);
sumLeading(n,arr);
showBelowMinorDiagonal(n,arr
); diagonalProduct(n,arr);
}

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.6 Program Title:
Write a program to find out the second smallest and second largest element stored in an array of
n integers. n is the user input. The array takes input through random number generation within a
given range. How many ways you can solve this problem? Write your approaches & strategy
for solving this problem.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

int randInt(){
time_t t;
srand((unsigned)
t*rand()); return rand()
%50;
}

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
const int n1 = m - l + 1;
const int n2 = r - m;

int L[n1], R[n2];

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

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

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
}
else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}

while (j < n2) { arr[k+

+] = R[j++]; ;
}
}

void mergeSort(int arr[],int l,int r){

{
if(l<r){
int m = l + (r - l) / 2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
}
void main(){

printf("Enter length of array\n");

int input = 7;
scanf("%d",&input);
const int n = input;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 int arr[n];
printf("Populating array\
n"); for (int i = 0; i < n;
i++)
{
arr[i] = randInt();
}
printf("\n");
for(int i =0 ; i<n ; +
+i){ printf("%d
",arr[i]);
}
printf("\n");

mergeSort(arr,0,n-
1); printf("\
nSorted\n");
for (int i = 0; i < n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.7 Program Title:
Write a program to swap pair of elements of an array of n integers from starting. If n is odd,
then last number will remain unchanged.

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:
#include
<stdio.h>
#include
<stdlib.h>

int randInt(){
time_t t;
srand((unsigned)
t*rand()); return rand()
%50;
}
void printArray(int n,int arr[n]){
for (int i = 0; i < n; i++)
{
printf("%d ",arr[i]);
}
}

void swap(int *a,int

*b){ int temp = *a;
*a = *b;
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
void swapNumbers(int arr[], int l, int r)
{
if (l < r)
{
swap(&arr[l], &arr[r]);
swapNumbers(arr, l + 1, r -
1);
}
}
void main()
{
printf("Enter length of array\
n"); int input = 7;
scanf("%d",
&input); const int
n = input; int
arr[n];
printf("Populating array\
n"); for (int i = 0; i < n;
i++)
{
arr[i] = randInt();
}
printf("Entered array is \
n"); printArray(n, arr);
if (!(n & 1))
{
swapNumbers(arr, 0, n - 1);
}
else
{
swapNumbers(arr, 0, n - 2);
}
printf("\nAfter swapping\

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
1.8 Program Title:
Write a program to display an array of n integers (n>1), where at every index of the array
should contain the product of all elements in the array except the element at the given index.
Solve this problem by taking single loop and without an additional array.
Input/Output Screenshots:

RUN-1:

RUN-2:

Source code:

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

int randInt(){
time_t t;
srand((unsigned)
t*rand()); return rand()
%50;
}
void printArray(int n,int arr[n]){
for (int i = 0; i < n; i++)
printf("%d ",arr[i]);
}

int calcProduct(int arr[],int l,int

r){ if(l<r)
return arr[l] * arr[r] * calcProduct(arr,l+1,r-1);
else if (l == r)
return arr[l];

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
void findProduct(int n,int index,int arr[n]){
if(index == n){
return ;
}
int productl = calcProduct(arr,0,index-1);
int productr = calcProduct(arr,index+1,n-
1); int temp = productl * productr;
findProduct(n,index+1,arr);
arr[index] = temp;
}

int main(){
printf("Enter length of array\
n"); int input;
scanf("%d",
&input); const int
n = input; int
arr[n];
printf("Entering array\
n"); for (int i = 0; i <
n; i++)
{
arr[i] = randInt();
}
printf("Entered array is \
n"); printArray(n, arr);
findProduct(n,0,arr);
printf("\nproducts\n");
printArray(n,arr); printf("\

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 2

Fun(dAnaalmysiseonf
ttimaelscsomopflexAitylgofosmriatllhalmgori
Solving –
ictchmPs roblem through step/frequency count
method.)
PROGRAM EXERCISE

CONTENTS
Prog. Page
No. Program Title No.
Write a program to test whether a number n, entered through keyboard is
prime or not by using different algorithms you know for at least 10 inputs
and note down the time complexity by step/frequency count method for each
2.1 algorithm & for each input. Finally make a comparison of time complexities
23
found for different inputs, plot an appropriate graph & decide which
algorithm is faster.
Write a program to find out GCD (greatest common divisor) using
the following three algorithms.
a) Euclid’s algorithm
2.2 b) Consecutive integer checking algorithm.
26
c) Middle school procedure which makes use of common prime factors.
For finding list of primes implement sieve of Eratosthenes algorithm.
Write a menu driven program as given below, to sort an array of n integers
in ascending order by insertion sort algorithm and determine the time
required (in terms of step/frequency count) to sort the elements. Repeat the
experiment for different values of n and different nature of data (i.e. apply
insertion sort algorithm on the data of array that are already sorted, reversely
sorted and random data). Finally plot a graph of the time taken versus n for
each type of data. The elements can be read from a file or can be generated
using the random number generator.
INSERTION SORT MENU
2.3 1.n Random numbers=>Array
28
2.Display the Array
3.Sort the Array in Ascending Order by using Insertion Sort
Algorithm 4.Sort the Array in Descending Order by using any sorting
algorithm 5.Time Complexity to sort ascending of random data
6.TC to sort ascending of data already sorted in ascending order
7.TC to sort ascending of data already sorted in descending order
8.Time Complexity to sort ascending of data for all Cases in Tabular form
for values n=5000 to 50000, step=5000

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 PROGRAM SOLUTIONS
2.1 Program Title:
Write a program to store random numbers into an array of n integers and then find out the smallest
and largest number stored in it. n is the user input.

Input/Output Screenshots:
RUN-1:

Graph:

Source code:

#include<stdio.h>
#include<stdlib.h
>
#include<stdbool.
h>
#include<string.h
>
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
void resetCounter(){
approach1Counter = 0;
approach2Counter = 0;
approach3Counter = 0;
}
bool approach1(int n) {
int count = 0, num = n-1; approach1Counter++;
while (n % num != 0 && num >= 1) {
num--; approach1Counter++;
}
if (num==1) {
approach1Counter++;
return true;
}
else {
approach1Counter++;
return false;
}
}

bool approach2(int n) {
int count = 0, num = n/2; approach2Counter++;
while (n % num != 0 && num >= 1) {
num--; approach2Counter++;
}
if (num==1) {
approach2Counter++;
return true;
}
else {
approach2Counter++;
return false;
}
}

bool approach3(int num) {

if (num < 2) {
approach3Counter++;
return false;
}
if (num == 2) {
approach3Counter++;
return true;
}
int count = 0;
for (int i=2;i<num/2;++i) {
if (num % i == 0) {
count++;
approach3Counter++;
break;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 }
else
approach3Counter++;
}
if(count > 0)
return false;
else
return true;
}

void main() {
printf("Enter 10 numbers\
n"); int arr[10];
for(int i = 0;i<10;i+
+)
scanf("%d",&arr[i]
);
printf("\t\tTime\tTaken\tBy\t\t\n");
printf("S.No\tInput\tAlgo-1\tAlgo-2\tAlgo-3\tResult\t\tFastest\n\n");
char result[10];
for(int i = 0;i<10;i++){
bool res =
approach1(arr[i]);
approach2(arr[i]);
approach3(arr[i]);
if (approach1Counter < approach2Counter && approach1Counter < approach3-
Counter)
strcpy(result,"algo-1");
else if (approach2Counter < approach3Counter
) strcpy(result,"algo-2");
else
strcpy(result,"algo-3"); printf("%d\t%d\t%d\t%d\t%d\t%s\t%s\
n",i+1,arr[i],approach1Counter,ap-
proach2Counter,approach3Counter,res?"is prime":"not prime",result);

Conclusion/Observation:

The three algorithms used were

1. Brute Force from 1 to n
2. Brute force from 1 to n/2
3. Half range search

Findings: Approach 2 and 3 had same time complexity but took half the amount of time as Approach
1 because the range was half.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
2.2 Program Title:
Write a program to find out GCD (greatest common divisor) using the following three algorithms.
a) Euclid’s algorithm
b) Consecutive integer checking algorithm.
c) Middle school procedure which makes use of common prime factors. For finding list of
primes implement sieve of Eratosthenes algorithm.

Input/Output Screenshots:
RUN-1:

Source code:

#include<stdio.h>
#include
<string.h>

int count1 =
0; int count2
= 0; int
count3 = 0;
void
resetCounter()
{ count1 = 0;
count2 = 0;
count3 = 0;
}
int euclid(int a, int
b){ count1++;
if (a == 0)
return b;
return euclid(b%a, a);
}
int cid(int a,int b,int
t){ count2++;
if( a%t == 0 && b%t ==
0) return t;
else return cid(a,b,t-1);
}
int middleSchool(int n1, int
n2){ int gcd;
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 gcd = i;
}
return gcd;
}
void main(){
int arr[12];
for(int i=0;i<12;i++) scanf("%d",&arr[i]);
char result[12];

printf("S.No\t Input\tEuclid\tCIC\tMid Sch\tGCD\tFastest\n");

printf("\n")
;
for(int i=0,j=0;i<12;i+=2){
int gcd1 = euclid(arr[i],arr[i+1]);
int gcd2 = cid(arr[i],arr[i+1], arr[i]>arr[i+1] ? arr[i+1] : arr[i]); int gcd3 = middleS
if (count1 < count2 && count1 < count3) strcpy(result,"Euclid");
else if (count2 < count3 ) strcpy(result,"CIC");
else
strcpy(result,"Mid Sch"); printf("%d\t(%d,\t%d)\t%d\t%d\t%d\t%d\t%s\n",+
+j,arr[i],arr[i+1],count1,count2,count3,gcd1,result); resetCounter();
}
}

Conclusion/Observation:

Three procedures were used

1. Euclid
2. CIC
3. Middle School

Findings: Middle School algorithm performed the worst with a time complexity of O(N^3).
Euclid was generally faster with a time complexity of log(min(a,b))

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
2.3 Program Title:
Write a menu driven program as given below, to sort an array of n integers in ascending order by
insertion sort algorithm and determine the time required (in terms of step/frequency count) to sort
the elements. Repeat the experiment for different values of n and different nature of data. Finally
plot a graph of the time taken versus n for each type of data. The elements can be read from a file or
can be generated using the random number generator.
INSERTION SORT MENU
1. n Random numbers=>Array
2. Display the Array
3. Sort the Array in Ascending Order by using Insertion Sort Algorithm
4. Sort the Array in Descending Order by using any sorting algorithm
5. Time Complexity to sort ascending of random data
6. TC to sort ascending of data already sorted in ascending order
7. TC to sort ascending of data already sorted in descending order
8. Time Complexity to sort ascending of data for all Cases in Tabular form for values
n=5000 to 50000, step=5000

Input/Output Screenshots:
RUN-1:

Graph:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code:

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

int randInt()
{
time_t t;
srand((unsigned)t * rand());
return rand() % 50;
}

long insertionSort(int arr[], int n)

{
long count = 1;
for (int j = 1; j < n; ++j, count++)
{
count++; //number of times temp is assigned
int temp = arr[j];
count++; //number of times i is assigned
int i = j - 1;
count++; //number of times while loop is initialized
while (arr[i] > temp && i >= 0)
{
count++; //number of shift operations
arr[i + 1] = arr[i];
count++; //number of i decrements
i--;
}
count++; // number of times temp is assigned to it's position
arr[i + 1] = temp;
}
return count;
}

long insertionSortDescending(int arr[], int n)

{
long count = 1;
for (int j = 1; j < n; ++j, count++)
{
count++; //number of times temp is assigned
int temp = arr[j];
count++; //number of times i is assigned
int i = j - 1;
count++; //number of times while loop is initialized
while (arr[i] < temp && i >= 0)
{
count++; //number of shift operations
arr[i + 1] = arr[i];
count++; //number of i decrements

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 i--;
}
count++; // number of times temp is assigned to it's position
arr[i + 1] = temp;
}
return count;
}

void analyze(int n){

int *arr1 = malloc(n*sizeof(int)),*arr2 = malloc(n*sizeof(int)),*arr3 = mal-
loc(n*sizeof(int)); //for ascending, descending and random respectively
for (int i = 0; i < n; ++i)
{ int num = randInt();
arr1[i] = num;
arr2[i] = num;
arr3[i] = num;
}
insertionSort(arr1,n); //sort data in ascending order
insertionSortDescending(arr2,n); //sort data in descending order

long count1 = insertionSort(arr1,n); //count steps for sorting already as-

cending sorted data;
long count2 = insertionSort(arr2,n); //count steps for sorting descending sor
ted data;
long count3 = insertionSort(arr3,n); //count steps for sorting random data

printf("%5d\t%5d\t%10ld\t%10ld\t%10ld",n/5000,n,count1,count2,count3);
}
void main()
{
int *arr;
int n;
int ch = 0;
long count = 0;

do
{
printf("Select an option\n");
printf("\
0. Quit\n\
1. n Random numbers=>Array\n\
2. Display the Array\n\
3. Sort the Array in Ascending Order by using Insertion Sort Algo-
rithm\n\
4. Sort the Array in Descending Order by using any sorting algorithm\
n\
5. Time Complexity to sort ascending of random data\n\
6. Time Complexity to sort ascending of data already sorted in as-
cending order\n\

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 7. Time Complexity to sort ascending of data already sorted in de-
scending order\n\
8. Time Complexity to sort ascending of data for all Cases (Data As-
cending, Data in Descending & Random Data) in Tabular form for values n=5000 to 5
0000, step=5000\n");
scanf("%d", &ch);
switch (ch)
{
case 0:
break;
case 1:
{
printf("Enter length of array\n");
scanf("%d",&n);
arr = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i)
arr[i] = randInt();
break;
}
case 2:{
printf("The array is \n");
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
break;
}
case 3:{
count = insertionSort(arr,n);
printf("Array of length %d sorted in %ld steps \n",n,count);
printf("Array after sorting is \n");
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
break;
}
case 4:{
insertionSortDescending(arr,n);
printf("Array after sorting is \n");
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
break;
}
case 5:{
count = insertionSort(arr,n);
printf("Array of length %d sorted in %ld steps \n",n,count);
break;
}
case 6:{
insertionSort(arr,n);

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 count = insertionSort(arr,n);
printf("An already sorted array was sorted in %ld steps\n",count);
break;
}
case 7:{
insertionSortDescending(arr,n);
count = insertionSort(arr,n);
printf("An array sorted in descending order was sorted in %ld steps\
n
",count
);
}
case 8:{
printf("S.No\tVal N\tData in Asc\tData in Desc\tRandom Data\n");
for(int i=5000;i<=50000;i+=5000){
analyze(i);
printf("\
n");
}
break;
}

Conclusion/Observation:

For insertion sort, 3 cases were taken

1. Random Data
2. Sorted Data
3. Reverse sorted data

Findings: The algorithm shows best case time complexity of o(N) on sorted data. It shows worst
case time complexity O(N^2) on reverse sorted data. It tends to perform moderately on random
data.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 3

Fundamentals of Algorithmic Problem

Solving-II:

(Analysis of time complexity of algorithms

through the concept of asymptotic notations)
PROGRAM EXERCISE

CONTENTS
Prog. Page
No. Program Title No.
Rewrite the program no- 2.1 (Insertion Sort) with the following details.
i. Compare the best case, worst case, and average case time
complexity with the same data except time complexity will
count the CPU clock time.
3.1 ii. Plot a graph showing the above comparison (n, the input data
Vs. CPU times for best, worst & average case)
iii. Compare manually program no- 2.1 graph vs program no-
3.1 graph and draw your inference
Let A be a list of n (not necessarily distinct) integers. Write a program by
using User Defined Function (UDF)s to test whether any item occurs
3.2 more than ⌈n/2⌉ times in A.
a) UDF should take O(n2) time and use no additional space.
b) UDF should take O(n) time and use O (1) additional space.
Write a program by using a user defined function for computing ⌊√n⌋ for
3.3 any positive integer n. Besides assignment and comparison, your
algorithm may only use the four basic arithmetical operations.
Let A be an array of n integers a0, a1,... ,an-1 (negative integers are
allowed), denoted, by A [i... j], the sub-array ai, ai+1,... ,aj for i≤j. Also
let Si-j denote the sum ai + ai+1 +· · · + aj. Write a program by using an
udf that must run in O(n2) time to find out the maximum value of Si-j for
all the pair i, j with 0 ≤ i ≤ j ≤ n-1. Call this maximum value S. Also
obtains the maximum of these computed sums. Let j < i in the notation A
3.4 [i... j] is also allowed. In this case, A[i... j] denotes the empty sub-array
(that is, a sub-array that ends before it starts) with sum Si-j = 0. Indeed,
if all the elements of A are negative, then one returns 0 as the maximum
sub-array sum.
For example, for the array A []={1, 3, 7, -2, -1, -5, -1, -2, -4, 6, 2}. This
maximum sum is S = S0-2 = 1+3+7=11.
3.5 Design a data structure to maintain a set S of n distinct integers that
supports the following two operations:
a) INSERT (x, S): insert integer x into S
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 b) REMOVE-BOTTOM-HALF(S): remove the smallest ⌈ n/2⌉
integers from S. Write a program by using UDFs that give the
worse-case time complexity of the two operations INSERT(x,
S)
in O(1) time and REMOVE-BOTTOM-HALF(S) in O(n) time.
Consider an n × n matrix A = (aij), each of whose elements aij is a
nonnegative real number and suppose that each row and column of A
sums to an integer value. We wish to replace each element aij with
3.6 either
⌊aij⌋ or ⌈aij⌉ without disturbing the row and column sums.
Write a program by defining a user defined function that is used to
produce the rounded matrix as described in the above example. Find out
the time complexity of your algorithm/function.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 PROGRAM SOLUTIONS
3.1 Program Title:
Rewrite the program no- 2.1 (Insertion Sort) with the following details.
i. Compare the best case, worst case, and average case time complexity with the same
data except time complexity will count the CPU clock time.
ii. Plot a graph showing the above comparison (n, the input data Vs. CPU times for
best, worst & average case)
Compare manually program no- 2.1 graph vs program no- 3.1 graph and draw your inference

Input/Output Screenshots:

RUN-1:

Graph:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code:

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

int randInt(){
time_t t;
srand((unsigned)t * rand());
return rand() % 1000;
}

void insertionSort(int arr[], int n,int p){

for (int j = 1; j < n; ++j){
int temp = arr[j];
int i = j - 1;
while (arr[i] > temp && i >= 0){
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = temp;
}
if(p==1){
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
}
}

void insertionSortDescending(int arr[], int n,int p){

for (int j = 1; j < n; ++j){
int temp = arr[j];
int i = j - 1;
while (arr[i] < temp && i >= 0){
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = temp;
}
if(p==1){
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
}
}

void analyze(int n){

int *arr1 = malloc(n*sizeof(int)),*arr2 = malloc(n*sizeof(int)),*arr3 = mal-
loc(n*sizeof(int)); //for ascending, descending and random respectively
for (int i = 0; i < n; ++i){

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 int num = randInt();
arr1[i] = num;
arr2[i] = num;
arr3[i] = num;
}
clock_t t;
double time_taken;
insertionSort(arr1,n,0); //sort data in ascending order
insertionSortDescending(arr2,n,0); //sort data in descending order

t = clock();
insertionSort(arr1,n,0); //count seconds for sorting already ascending sorted
data;
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
double count1 = time_taken;

t = clock();
insertionSort(arr2,n,0); //count seconds for sorting descending sorted data;
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
double count2 = time_taken;

t = clock();
insertionSort(arr3,n,0); //count seconds for sorting random data
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
double count3 = time_taken;
printf("%5d\t%5d\t%10f\t%10f\t%10f",n/5000,n,count1,count2,count3);
}
void main(){
int *arr;
int n;
int ch = 0;
double count = 0;
clock_t t;
double time_taken;
do{
printf("MAIN MENU FOR INSERTION SORT");
printf("Select An Option:");
printf("\
0. Quit\n\
1. n Random numbers=>Array\n\
2. Display the Array\n\
3. Sort the Array in Ascending Order by using Insertion Sort Algo-
rithm\n\
4. Sort the Array in Descending Order by using any sorting algorithm\
n\
5. Time Complexity to sort ascending of random data\n\

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 6. Time Complexity to sort ascending of data already sorted in as-
cending order\n\
7. Time Complexity to sort ascending of data already sorted in de-
scending order\n\
8. Time Complexity to sort ascending of data for all Cases\n\t\t(Data
Ascending, Data Descending & Random Data) in a table for values n=5000 to 50000,s
tep=5000\n");
scanf("%d", &ch);
switch (ch)
{
case 0:
break;
case 1:{
printf("Enter length of array\n");
scanf("%d",&n);
arr = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i)
arr[i] = randInt();
break;
}
case 2:{
printf("The array is \n");
for(int i=0;i<n;++i)
printf("%d ",arr[i]);
printf("\n");
break;
}
case 3:{
insertionSort(arr,n,1);
break;
}
case 4:{
insertionSortDescending(arr,n,1);
break;
}
case 5:{
t = clock();
insertionSort(arr,n,0);
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
double count = time_taken;
printf("Array of length %d sorted in %f seconds \n",n,count);
break;
}
case 6:{
t = clock();
insertionSort(arr,n,0);
insertionSort(arr,n,0);
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 double count = time_taken;
printf("An already sorted array was sorted in %f seconds\n",count);
break;
}
case 7:{
t = clock();
insertionSortDescending(arr,n,0);
insertionSort(arr,n,0);
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
double count = time_taken;
printf("Array sorted in descending order was sorted in %f seconds\
n",
count);
break;
}
case 8:{
printf("S.No\tVal N\tBest Case\tWorst Case\tRandom Data\n");
for(int i=5000;i<=50000;i+=5000){
analyze(i);
printf("\
n");
}
break;
}
}

Conclusion/Observation

It was observed that the data arranged in descending order took the highest time whereas data
arranged in ascending order took least time, to arrange the data in ascending order, whereas data
arrange in random order always took time in between ascended and descended sorted array. Hence
it can be concluded that time complexity of insertion sort depends on data.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
3.2 Program Title:
Let A be a list of n (not necessarily distinct) integers. Write a program by using User Defined
Function (UDF)s to test whether any item occurs more than ⌈n/2⌉ times in A.
a) UDF should take O(n2) time and use no additional space.
b) UDF should take O(n) time and use O (1) additional space.

Input/Output Screenshots:
RUN-1:

Source code

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

int randInt(){
time_t t;
srand((unsigned)t *
rand()); return rand() %
50;
}

int findMax(int arr[],int

n){ int max = 0;
for(int i=0;i<n;+
+i){ if (max <
arr[i]) max =
arr[i];
}
return max;
}

void main(){
int arr[] = {1,2,3,4,2,2,6,2,2};

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 for(int i=0;i<n;+
+i){ int num =
arr[i]; int
count = 0;
for(int j=i+1;j<n;+
+j) if(num ==
arr[j])
count+
+;
if(count>=n/2)
printf("%d occurrs more than n/2 times\n",num);
}

int max =
findMax(arr,n); int
b[max];
for(int i=0;i<max;+
+i) b[i] = 0;
for(int i=0;i<n;+
+i){ int num =
arr[i]; int
count = 0;
b[num]++;
}

Conclusion/Observation

Elements repeating more than n/2 time were found using two different approach. Two different
UDF found same result but with different time complexity as O[n] and O [n2].

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
3.3 Program Title:
Write a program by using a user defined function for computing ⌊√n⌋ for any positive integer
n. Besides assignment and comparison, your algorithm may only use the four basic arithmetical
operations.

Input/Output Screenshots:
RUN-1:

RUN-2:

Source code:

#include <stdio.h>

void compute(int number)

{
int sqrt = number /
2; int temp = 0;
while (sqrt != temp)
{
temp = sqrt;
sqrt = (number / temp + temp) / 2;
}
printf("Result: %d\n", sqrt);
}

void main()
{
int n;
printf("Enter a number:
"); scanf("%d", &n);
compute(n);
}

Conclusion/Observation

Square root of number was found using an UDF with time complexity O[n].

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
3.4 Program Title:
Let A be an array of n integers a0, a1,... ,an-1 (negative integers are allowed), denoted, by A [i...
j], the sub-array ai, ai+1,... ,aj for i≤j. Also let Si-j denote the sum ai + ai+1 +· · · + aj. Write a
program by that must run in O(n2) time to find out the maximum value of Si-j for all the pair i,
j with 0≤i≤j≤n-1. Call this maximum value S. Also obtains the maximum of these computed
sums. Let j < i in the notation A [i... j] is also allowed. In this case, A[i... j] denotes the empty
sub-array (that is, a sub-array that ends before it starts) with sum Si-j=0. Indeed, if all the
elements of A are negative, then one returns 0 as the maximum sub-array sum.

Input/Output Screenshots:
RUN-1:

Source code:

#include
<stdio.h>
#include
<stdlib.h>
int findMax(int arr[], int n)
{ int max = 0;
for(int i=0;i<n;+
+i){ int sum =
0;
for(int j=i;j<n;+
+j){
sum+=arr[j];
if(sum > max)
max = sum;
}
}return max;
}

int main(){
int A[] = {1, 3, 7, -2, -1, -5, -1, -2, -4, 6, 2};
int max = 0;
int n = sizeof(A) /
sizeof(int); max = findMax(A,
n);

Conclusion/Observation:

Range with maximum sum of elements was found using a brute force method with time complexity
O [n2].

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
3.5 Program Title:
Design a data structure to maintain a set S of n distinct integers that supports the following two
operations:
a) INSERT (x, S): insert integer x into S
b) REMOVE-BOTTOM-HALF(S): remove the smallest ⌈ n/2⌉ integers from S. Write a
program by using UDFs that give the worse-case time complexity of the two
operations INSERT(x, S) in O(1) time and REMOVE-BOTTOM-HALF(S) in O(n)
time.

Input/Output Screenshots:

RUN-1:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 Source code:

#include <stdio.h>
#include <stdlib.h>
int A[100000];
int size=0;
struct node{
int val;
struct node* next;
};
void Insert(struct node **head, int value)
{
if(A[value]==0){
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("Failed to insert element.Out of memory");
return;
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
A[value]=1;
}
}
void Display(struct node *head)
{
struct node *temp;
temp=head; printf("\
033[0;32m");
printf("H");
while(temp)
{
printf("->%d", temp->val);
temp = temp->next;
}
printf("\n\n");
printf("\033[0m");
}
void Asc(struct node *head){
int max;
struct node *temp2=head,*temp3=head,*temp4=head,*temp5=head;
for(int i=0;temp2->next!=NULL;temp2=temp2->next){
if(max<=temp2->val) max=temp2->val;
size=size+1;
}
int M[max+1];
for(int i=0;i<=max;i++) M[i]=0;
while (temp3!=NULL)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 {
M[temp3->val]=1;
temp3=temp3->next;
}
for(int i=0;i<=max;i++){
if(M[i]==1){
temp4->val=i;
temp4=temp4->next;
}
}
size=size/2;
}
void deleteFirstNode(struct node *head)
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\n Node deleted from the begining ...");
}
}
void delete(struct node *head)
{
while (size!=0)
{
deleteFirstNode(head);
size=size-1;
}
}
void main(){
int val;
struct node * head = NULL;
int n=1;
while (n!=0)
{
printf("\n0.To exit\n 1.To Insert Element\n 2.Remove Bottom Half(S)\n");
scanf("%d",&n);
switch (n)
{
case 0:
n=0;
break;
case 1:
printf("Enter the value to insert\n");

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 scanf("%d",&val);
Insert(&head,val); printf("\
nAfter Operation\n");
Display(head);
brea
k; case
2:
Asc(head);
Display(head
);
delete(head)
;
printf("\nAfter Operation\
n"); Display(head);
brea
k;
default:
printf("Enter valid

Conclusion/Observation:

A Data Structure was formed to maintain a set S of n distinct integers, then two functions were
written to facilitate Element Insertion and removal bottom half elements within time complexity of
O[1] and O[n], respectively.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
3.6 Program Title:
Consider an n × n matrix A = (aij), each of whose elements aij is a nonnegative real number
and suppose that each row and column of A sums to an integer value. We wish to replace each
element aij with either ⌊aij⌋ or ⌈aij⌉ without disturbing the row and column sums.
Write a program by defining a user defined function that is used to produce the rounded matrix
as described in the above example. Find out the time complexity of your algorithm/function.

Input/Output Screenshots:

RUN-1:

Source code

#include
<stdio.h>
#include
<math.h>

float M[4][4];
float floatA[5]
[5]; float
sum_row[5]; float
sum_col[5]; float
A[5][5];
int n;
void display(){
for (int i = 0; i < n; i++)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 printf("%.1f\t",A[i][j]);
}
printf("\n");
}
}
void FloatSum(){
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
floatA[i][j]=A[i][j]-(int)A[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum_row[i]=(sum_row[i]+floatA[i][j]);
}
sum_row[i]=round(sum_row[i]);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum_col[i]=(sum_col[i]+floatA[j][i]);
}
sum_col[i]=round(sum_col[i]);
}
}
void algo(){
printf("\n");
for(int w=0;w<n;w++){
for(int q=0;q<n;q++){
if(sum_col[q]>0 && sum_row[w]>0){
A[w][q]=ceil(A[w][q]);
sum_col[q]=sum_col[q]-1;
sum_row[w]=sum_row[w]-1;
}
else A[w][q]=floor(A[w][q]);
}
}
}
void main(){

printf("\nEnter the size of Matrix upto 5x5\n");

scanf("%d",&n);
printf("Enter The values of array (rows followed by columns)\n");
for(int i=0;i<n;i++){
for (int j = 0; j < n; j++)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 {
scanf("%f",&A[i][j]);
}
}
printf("\nEntered Matrix\
n"); display();
FloatSum(
);
algo();
printf("\nAfter Round off\
n"); display();

Conclusion/Observation:

A matrix’s elements were rounded of while maintaining the rows and columns sum. A UDF with
time complexity O[n2] was written to find the result. It was observed that multiple results are possi-
ble and the very first fit found was displayed by the written UDF.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 4

D i v vi d eand
(B i a n d C o n q u
nar y Se arch ,M erg e Sor t, Q uic kS ort ,

e PROGRAM
r M eEXERCISE
t h o d
Ra nd om ized Qu ick So rt)

CONTENTS
Prog. Page
No. Program Title No.
Write a program to search an element x in an array of n integers using
binary search algorithm that uses divide and conquer technique. Find out
the best case, worst case, and average case time complexities for different
4.1 values of n and plot a graph of the time taken versus n. The n integers can
be generated randomly, and x can be chosen randomly, or any element of
the array or middle or last element of the array depending on type of time
complexity analysis.
Write a program to sort a list of n elements using the merge sort method
and determine the time required to sort the elements. Repeat the
experiment for different values of n and different nature of data
4.2 (random data, sorted data, reversely sorted data) in the list. n is the user
input and n integers can be generated randomly. Finally plot a graph of
the time
taken versus n.
Write a program to use divide and conquer method to determine the time
required to find the maximum and minimum element in a list of n
elements. The data for the list can be generated randomly. Compare this
4.3 time with the time taken by straight forward algorithm or brute force
algorithm for finding the maximum and minimum element for the same
list of n elements. Show the comparison by plotting a required graph for
this problem.
Write a program that uses a divide-and-conquer algorithm/user defined
function for the exponentiation problem of computing a n where a > 0
4.4 and n is a positive integer. How does this algorithm compare with the
brute-force algorithm in terms of number of multiplications made by
both
algorithms

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 PROGRAM SOLUTIONS
4.1 Program Title:

Write a program to search an element x in an array of n integers using binary search algorithm
that uses divide and conquer technique. Find out the best case, worst case, and average case
time complexities for different values of n and plot a graph of the time taken versus n. The n
integers can be generated randomly, and x can be chosen randomly, or any element of the
array or middle or last element of the array depending on type of time complexity analysis.

Input/Output Screenshots:

RUN-1:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Graph:

Source code:

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

int randInt(int n)
{
time_t t;
srand((unsigned)t *
rand()); return rand() %
n;
}

void printArray(int arr[],int n){

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

void insertionSort(int arr[], int n, int p)

{
for (int j = 1; j < n; ++j)
{
int temp =
arr[j]; int i =
j - 1;
while (arr[i] > temp && i >= 0)
{
arr[i + 1] =
arr[i]; i--;
}
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 for (int i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
}

int binarySearch(int arr[], int l, int r, int x)

{
if (r >= l)
{
int mid = l + (r - l) / 2;

if (arr[mid] == x)
{
return mid;
}

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}
return -1;
}

void analyse(int n)
{
int *arr = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i)
{
arr[i] = i+1;
}

// printArray(arr,n);

clock_t t;
double time_taken;
int x, result;

x = 0;
t = clock();
result = binarySearch(arr, 0, n - 1, x);
t = clock() - t;
time_taken = ((double)t) / CLOCKS_PER_SEC;
double count3 = time_taken;

x = arr[randInt(n)];
t = clock();

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 result = binarySearch(arr, 0, n - 1,
x); t = clock() - t;
time_taken = ((double)t) / CLOCKS_PER_SEC;
double count1 = time_taken;

x = arr[n /
2]; t =
clock();
result = binarySearch(arr, 0, n - 1,
x); t = clock() - t;
time_taken = ((double)t) / CLOCKS_PER_SEC;
double count2 = time_taken;

printf("%f %f %f \n", count1, count2, count3);

}

int main(void)
{
printf("avg\t best\t worst\n");
for (int i = 5001; i <= 50001; i += 5000)
{
analyse(i);
}
return 0;

Conclusion/Observation

Using a lower CPU speed machine Raspberry Pi 3 we were able to get the accurate results.
We observe that for Binary Search, the best-case scenario, which is when the element is in
middle of the array, the search takes 0.000003/0.000004s to complete hence almost equal to
O(1) time for the range 5000 to 50000 elements. Progressively the avg and the worst-case
scenario, when the element is at the extreme end of the array, the search takes a logarithmic
increasing time curve hence satisfying the condition of O (log n).

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
4.2 Program Title:
Write a program to sort a list of n elements using the merge sort method and determine the time
required to sort the elements. Repeat the experiment for different values of n and different
nature of data (random data, sorted data, reversely sorted data) in the list. n is the user input and
n integers can be generated randomly. Finally plot a graph of the time taken versus n.

Input/Output Screenshots:

RUN-1:

Graph:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int randInt()
{
time_t t;
srand((unsigned)t * rand());
return rand() % 5000;
}

void rvereseArray(int arr[], int start, int end)

{
while (start < end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

void printArray(int A[], int size)

{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

void merge(int arr[], int l, int m, int r)

{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 else {
arr[k] = R[j];
j++;
} k+
+;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)

{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void analyse(int n){

int *arr1 = malloc(n*sizeof(int));
for (int i = 0; i < n; ++i)
{
arr1[i] = randInt();
}

clock_t t;
double time_taken;
int x,result;

t = clock();
mergeSort(arr1,0,n-1);
t = clock() - t;
time_taken = ((double)t) / CLOCKS_PER_SEC;
double count1 = time_taken;

t = clock();
mergeSort(arr1,0,n-1);
t = clock() - t;
time_taken = ((double)t) / CLOCKS_PER_SEC;
double count2 = time_taken;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 rvereseArray(arr1, 0, n-1);

t = clock();
mergeSort(arr1,0,n-
1); t = clock() - t;
time_taken = ((double)t) /
CLOCKS_PER_SEC; double count3 =
time_taken;

printf("%d\t%f %f %f \n", n,count1, count2, count3);

}

int main(void)
{
printf("n\tavg\t best\t worst\n");
for (int i = 5000; i <= 50000; i += 5000)
{
analyse(i);
}
return 0;

Conclusion/Observation

For merge sort, different no of elements sorted in ascending order, descending order, and
random order were taken for best case, worst case, and average case, respectively. After
running the program multiple times for values ranging from 5000 to 50000, we observe that the
time taken by merge sort for all three cases is almost equal hence concluding that merge sort
takes O (n log n) time for all cases. This can also be seen in the graph where all the 3 slopes
overlap each-other.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
4.3 Program Title:
Write a program to use divide and conquer method to determine the time required to find the
maximum and minimum element in a list of n elements. The data for the list can be generated
randomly. Compare this time with the time taken by straight forward algorithm or brute force
algorithm for finding the maximum and minimum element for the same list of n elements. Show
the comparison by plotting a required graph for this problem.

Input/Output Screenshots:

RUN-1:

Graph:

Source code:

/* C implementation QuickSort
*/ #include <stdio.h>
#include
<stdlib.h>
#include <time.h>

int randInt(){
time_t t;
srand((unsigned)t *

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
}

void swap(int *a, int *b){

int t = *a;
*a = *b;
*b = t;
}

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);
}

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);
}
}

void printArray(int arr[], int size){

int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

void analyse(int n){

int *arr = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i)
{
int num = randInt();
arr[i] = num;
}

int mx,mn,i;
clock_t t;
double rt, bt;
t = clock();
mx = arr[0];
mn = arr[0];

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 for(i=1; i<n; i+
+){
if(arr[i]>mx)
mx =
arr[i];
if(arr[i]<mn)
mn = arr[i];
}
t = clock() - t;
bt = ((double)t) / CLOCKS_PER_SEC;

t = clock();
quickSort(arr, 0, n -
1); t = clock() - t;
rt = ((double)t) / CLOCKS_PER_SEC; printf("%d\t%5d\t%10f\
t%10f", n / 5000, n,rt,bt);
}

int main(){
printf("S.No\tVal N\t Using DnC\t Using Brute Force\n");
for (int i = 500; i <= 5000; i += 500){
analyse(i);
printf("\

Conclusion/Observation

We observe that to find the maximum and minimum element, the brute force method is way more
effective than that of a divide and conquer algo as in brute force we only need to traverse the array
one time thus giving the time complexity of O (n) where n is number if elements, whereas in divide
and conquer method, the time taken is O (n log n ) which is exponentially higher as seen in the
graph.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
4.4 Program Title:
Write a program that uses a divide-and-conquer algorithm/user defined function for the
exponentiation problem of computing a n where a > 0 and n is a positive integer. How does this
algorithm compare with the brute-force algorithm in terms of number of multiplications made
by both algorithms?

Input/Output Screenshots:

RUN-1:

RUN-2:

Source code
#include<stdio.h>
int count_divide_and_conquer =
0; int count_naive = 0;
unsigned long long int divide_and_conquer_Power(int a,int n){
+
+count_divide_and_conquer
; if(n == 1) return a;
if(n == 0) return 1;
int number = divide_and_conquer_Power(a,n/2);
if(n&1)
return number * a * number;
else
return number * number;
}
unsigned long long int naive_Power(int a,int n)
{ if (n==0) return 1;
if (n==1) return
a; int num = a;
++count_naive;
for(int i=1;i<n;i+
+){
+
+count_naive
; num*=a;
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
int main(){
int a =
4; int b
= 12;
unsigned long long int pow1 =
divide_and_conquer_Power(a,b); unsigned long long int pow2
= naive_Power(a,b); printf("Soln by Divide and conquer :\
n");
printf("Ans: %lli\nNo. of Multiplications: %d\n",pow1,count_divide_and_con-
quer);
printf("Soln by Brute Force :\n");
printf("Ans: %lli\nNo. of Multiplications: %d\n",pow2,count_naive);

Conclusion/Observation:

The divide and conquer algorithm takes lesser number of multiplication compared to brute force
method hence is more efficient.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 5

Hp, Heeaap psort&algoPritrhmio, Mrinit-

(Building a hea

tPyriorQiQty quueeueu, Meaxs-Priority queue)

PROGRAM EXERCISE

CONTENTS
Prog. Page
No. Program Title No.
Write a menu (given as follows) driven program to sort an array of n
integers in ascending order by heap sort algorithm and perform the
operations on max heap.
Determine the time required to sort the elements. Repeat the experiment
for different values of n, the number of elements in the array 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.
MAX-HEAP & PRIORITY QUEUE MENU
0. Quit
1. n Random numbers=>Array
2. Display the Array
3. Sort the Array in Ascending Order by using Max-Heap
Sort technique
5.1
4. Sort the Array in Descending Order by using any algorithm
5. Time Complexity to sort ascending of random data
6. Time Complexity to sort ascending of data already sorted
in ascending order
7. Time Complexity to sort ascending of data already sorted
in descending order
8. Time Complexity to sort ascending all Cases (Data Ascending,
Data in Descending & Random Data) in Tabular form
for values n=5000 to 50000, step=5000
9. Extract largest element
10. Replace value at a node with new value
11. Insert a new element
12. Delete an element
Similar to above program no.5.1, write a menu driven program to sort an
5.2 array of n integers in descending order by heap sort algorithm.
Hints: Use min heap and accordingly change the menu options.

PROGRAM SOLUTIONS
5.1 Program Title:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Write a menu (given as follows) driven program to sort an array of n integers in ascending
order by heap sort algorithm and perform the operations on max heap.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Determine the time required to sort the elements. Repeat the experiment for different values
of n, the number of elements in the array 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.

Input/Output Screenshots:

RUN-1:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Graph:

Source code:

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

void swap(int *xp, int *yp){ int temp = *xp;

*xp = *yp;
*yp = temp;
}

int partition(int arr[], int low, int high){ int pivot = arr[high]; // pivot
int i = (low - 1);// Index of smaller element for (int j = low; j <= high - 1; j++){
// If current element is smaller than the pivot if (arr[j] > pivot){
i++; // increment index of smaller element swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); return (i + 1);
}

/* The main function that implements QuickSort arr[] --> Array to be sorted,
low --> Starting index, high --> Ending index */
void sortDescending(int arr[], int low, int high){ if (low < high){
/* pi is partitioning index, arr[p] is now
at right place */

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
sortDescending(arr, low, pi - 1);
sortDescending(arr, pi + 1, high);
}
}

void printArr(int arr[], int n){

printf("[ ");
for (int i = 0; i < n; ++i)
printf("%d, ", arr[i]);
printf("]\n");
}

void heapify(int arr[], int n, int i)

{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && arr[l] > arr[largest])

largest = l;

if (r < n && arr[r] > arr[largest])

largest = r;

if (largest != i)
{
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n)

{

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i > 0; i--)

{
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

void buildHeap(int arr[], int n)

{
// Index of last non-leaf node

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 int startIdx = (n / 2) - 1;

// Perform reverse level order traversal

// from last non-leaf node and heapify
// each node
for (int i = startIdx; i >= 0; i--)
{
heapify(arr, n, i);
}
}

void fillRandom(int arr[], int n)

{
srand(0);
for (int i = 0; i < n; i++)
arr[i] = rand() % n;
}

void analyze()
{
int arr[50000];
printf("RANDOM\t");
printf("\tASCENDING\t");
printf("DESCENDING\n");
for (int n = 5000; n <= 50000; n += 5000)
{
fillRandom(arr, n);
//Start timer for random
clock_t t_random = clock();
heapSort(arr, n);
//Stop timer for random
t_random = clock() - t_random;

//Start timer for data in ascending

clock_t t_ascending = clock();
heapSort(arr, n);
//Stop timer for sorted data
t_ascending = clock() - t_ascending;

//Sort in descending
sortDescending(arr, 0, n);
//Start timer for descending sort
clock_t t_descending = clock();
heapSort(arr, n);
//Stop timer for descending sort
t_descending = clock() - t_descending;

printf("%f\t%f\t%f\n", (double)t_random / CLOCKS_PER_SEC, (double)t_as-

cending / CLOCKS_PER_SEC, (double)t_descending / CLOCKS_PER_SEC);
}

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
}

int heap_extract_max(int arr[], int n)

{
if (n < 1)
return -1;
int max = arr[0];
arr[0] = arr[n - 1];
heapify(arr, n, 0);
printArr(arr, n - 1);
return max;
}

int main()
{
clock_t t_asc;
double tt_asc;
int i, j, temp;
int arr[100000];
int n;
int ch = 0;
do
{
printf("\
0. Quit\n\
1. n Random numbers=>Array\n\
2. Display the Array\n\
3. Sort the Array in Ascending Order by using Max-Heap Sort\n\
technique\n\
4. Sort the Array in Descending Order by using any algorithm\n\
5. Time Complexity to sort ascending of random data\n\
6. Time Complexity to sort ascending of data already sorted in\n\
ascending order\n\
7. Time Complexity to sort ascending of data already sorted in\n\
descending order\n\
8. Time Complexity to sort ascending all Cases (Data Ascending,\n\
Data in Descending & Random Data) in Tabular form for\n\
values n=5000 to 50000, step=5000\n\
9. Extract largest element\n\
10. Replace value at a node with new value\n\
11. Insert a new element\n\
12. Delete an element\nInput Choice\n");

scanf("%d", &ch);

switch (ch)
{
case 1:
{
printf("Number of elements?\n");

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 scanf("%d", &n);
fillRandom(arr, n);
buildHeap(arr,n);
}
break;

case 2:
printArr(arr, n);
break;

case 3:
heapSort(arr, n);
printArr(arr, n);
break;

case 4:
sortDescending(arr, 0, n);
break;

case 5:
{
fillRandom(arr, n);

clock_t start = clock();

heapSort(arr, n);
printf("Time taken to sort random data = %f", (double)(clock() - star
t) / CLOCKS_PER_SEC);
}
break;

case 6:
{
fillRandom(arr, n);
heapSort(arr, n);

//Start the clock

clock_t start = clock();
heapSort(arr, n);
//Stop the clock and print time
printf("Time taken to sort already sorted data is = %f", (double)
(clock() - start) / CLOCKS_PER_SEC);
}
break;

case 7:
{
sortDescending(arr, 0, n);
//Start the clock
clock_t start = clock();
heapSort(arr, n);

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 //Stop the clock and print time
printf("Time taken to sort already descending data is = %f", (double)
(clock() - start) / CLOCKS_PER_SEC);
}
break;
case 8:
analyze();
break;

case 9:
{
buildHeap(arr, n);
int max = heap_extract_max(arr, n);
printf("Max element is %d\n", max);
}
break;

case 10:
{
int index;
printf("Enter index of value to be changed\n");
scanf("%d", &index);
printf("Enter new value\n");
int num;
scanf("%d", &num);
arr[index] = num;
buildHeap(arr, n);
printArr(arr, n);
}
break;

case 11:
{
int num;
printf("Enter number to be inserted\n");
scanf("%d", &num);
printf(";-;\n");
arr[n + 1] = num;
buildHeap(arr, n + 1);
printArr(arr, n + 1);
}
break;

case 12:
{
int index;
printf("Enter index of element to delete\n");
scanf("%d", &index);
arr[index] = INT32_MAX + 1;
n--;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 buildHeap(arr,
n);
printArr(arr,
n);
}
break;

default:
break;
}

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
5.2 Program Title:
Similar to above program no.5.1, write a menu driven program to sort an array of n integers in
descending order by heap sort algorithm.

Input/Output Screenshots:
RUN-1:

GRAPH:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void swap(int *xp, int *yp){

int temp = *xp;
*xp = *yp;
*yp = temp;
}

int partition(int arr[], int low, int high){

int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++){
// If current element is smaller than the pivot
if (arr[j] > pivot){
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sortDescending(int arr[], int low, int high){
if (low < high){
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
sortDescending(arr, low, pi - 1);
sortDescending(arr, pi + 1, high);
}
}

void printArr(int arr[], int n){

printf("[ ");
for (int i = 0; i < n; ++i)
printf("%d, ", arr[i]);
printf("]\n");
}

void heapify(int arr[], int n, int i)

{
int smallest = i;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && arr[l] < arr[smallest])

smallest = l;

if (r < n && arr[r] < arr[smallest])

smallest = r;

if (smallest != i) {
swap(&arr[i], &arr[smallest]);

heapify(arr, n, smallest);
}
}

void heapSort(int arr[], int n){

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--){
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

void buildHeap(int arr[], int n){

// Index of last non-leaf node
int startIdx = (n / 2) - 1;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for (int i = startIdx; i >= 0; i--)
heapify(arr, n, i);
}

void fillRandom(int arr[], int n){

srand(0);
for (int i = 0; i < n; i++)
arr[i] = rand() % n;
}

void analyze(){
int arr[50000];
printf("RANDOM\t");
printf("\tASCENDING\t");
printf("DESCENDING\n");
for (int n = 5000; n <= 50000; n += 5000){
fillRandom(arr, n);
//Start timer for random
clock_t t_random = clock();

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 heapSort(arr, n);
//Stop timer for random
t_random = clock() - t_random;

//Start timer for data in ascending

clock_t t_ascending = clock();
heapSort(arr, n);
//Stop timer for sorted data
t_ascending = clock() - t_ascending;

//Sort in descending
sortDescending(arr, 0, n);
//Start timer for descending sort
clock_t t_descending = clock();
heapSort(arr, n);
//Stop timer for descending sort
t_descending = clock() - t_descending;

printf("%f\t%f\t%f\n", (double)t_random / CLOCKS_PER_SEC, (double)t_as-

cending / CLOCKS_PER_SEC, (double)t_descending / CLOCKS_PER_SEC);
}
}

int heap_extract_min(int arr[], int n){

if (n < 1)
return -1;
int max = arr[0];
arr[0] = arr[n - 1];
heapify(arr, n, 0);
printArr(arr, n - 1);
}

int main(){
clock_t t_asc;
double tt_asc;
int i, j, temp;
int arr[100000];
int n;
int ch = 0;
do{
printf("\
0. Quit\n\
1. n Random numbers=>Array\n\
2. Display the Array\n\
3. Sort the Array in Ascending Order by using Min-Heap Sort\n\
technique\n\
4. Sort the Array in Descending Order by using any algorithm\n\
5. Time Complexity to sort ascending of random data\n\
6. Time Complexity to sort ascending of data already sorted in\n\
ascending order\n\

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
7. Time Complexity to sort ascending of data already sorted in\n\
descending order\n\
8. Time Complexity to sort ascending all Cases (Data Ascending,\n\
Data in Descending & Random Data) in Tabular form for\n\
values n=5000 to 50000, step=5000\n\
9. Extract largest element\n\
10. Replace value at a node with new value\n\
11. Insert a new element\n\
12. Delete an element\nInput Choice\n");

scanf("%d", &ch);
switch (ch){
case 1:{
printf("Number of elements?\n");
scanf("%d", &n);
fillRandom(arr, n);
}
break;

case 2:
printArr(arr, n);
break;

case 3:
heapSort(arr, n);
printArr(arr, n);
break;

case 4:
sortDescending(arr, 0, n);
break;

case 5:{
fillRandom(arr, n);
clock_t start = clock();
heapSort(arr, n);
printf("Time taken to sort random data = %f", (double)(clock() - star
t) / CLOCKS_PER_SEC);
}
break;

case 6:{
fillRandom(arr, n);
heapSort(arr, n);

//Start the clock

clock_t start = clock();
heapSort(arr, n);
//Stop the clock and print time

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 printf("Time taken to sort already sorted data is = %f", (double)
(clock() - start) / CLOCKS_PER_SEC);
}
break;

case 7:{
sortDescending(arr, 0, n);
//Start the clock
clock_t start = clock();
heapSort(arr, n);
//Stop the clock and print time
printf("Time taken to sort already descending data is = %f", (double)
(clock() - start) / CLOCKS_PER_SEC);
}
break;
case 8:
analyze();
break;

case 9:{
buildHeap(arr, n);
int min = heap_extract_min(arr, n);
printf("min element is %d\n", min);
}
break;

case 10:{
int index;
printf("Enter index of value to be changed\n");
scanf("%d", &index);
printf("Enter new value\n");
int num;
scanf("%d", &num);
arr[index] = num;
buildHeap(arr, n);
printArr(arr, n);
}
break;

case 11:{
int num;
printf("Enter number to be inserted\n");
scanf("%d", &num);
printf(";-;\n");
arr[n + 1] = num;
buildHeap(arr, n + 1);
printArr(arr, n + 1);
}
break;

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 case 12:{
int index;
printf("Enter index of element to delete\n");
scanf("%d", &index);
arr[index] = INT32_MAX ; n--;
buildHeap(arr,
n);
printArr(arr,
n);
}
break;

default:
break;
}

} while (ch);

Conclusion/Observation
write here your conclusion/inference/final comment.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 6

Gprrobeleem,dAcytivitMy
(Fractional knapsack

seeletcthionopdrdobslem, Huffman’s code)

PROGRAM EXERCISE

CONTENTS
Prog. Page
No. Program Title No.
6.1 Write a program to implementation of Fractional Knapsack algorithm.
Write a program to implement the activity-selection problem stated as
follows:
You are given n activities with their start and finish times. Select the
maximum number of activities that can be performed by a single person,
6.2 assuming that a person can only work on a single activity at a time.
Example: Consider the following 6 activities (0, 1, 2, 3, 4, 5). start[] = {1,
3, 0, 5, 8, 5}; finish[] = {2, 4, 6, 7, 9, 9}; The maximum set of activities
that can be executed by a single person is {0, 1, 3, 4}.
Write a program to implement the file or code compression using
6.3 Huffman’s algorithm.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 PROGRAM SOLUTIONS
6.1 Program Title:
Write a program to implementation of Fractional Knapsack algorithm.

Input/Output Screenshots:

RUN-1:

Source code

#include <stdio.h>

int weight[] = {50,5,1000};

int price[] = {5000,500000,5000};

void Greedy_Knapsack(int M,int n)

{ int current_value;

//Total value of items in

bag float total_value;
int i, maximum;

//Check if item has been picked

up int used[n];
for (i = 0; i < n; +
+i) used[i] = 0;
current_value = M;
while (current_value > 0)
{ maximum = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0)
&&
((maximum == -1) || (price[i]*1.0/weight[i] > price[maxi-
mum]*1.0/weight[maximum])))
maximum = i;
//Set that item has been picked up

used[maximum] = 1;
current_value -= weight[maximum];
total_value += price[maximum];

if (current_value >= 0)
printf("Add object %d (₹%d, %d weight). Space left: %d.\n", maximum
+ 1, price[maximum], weight[maximum], current_value);
School of Computer Engineering, KIIT Deemed to be University,
Bhubaneswar
 printf("Add %d%% (₹%d, %d weight) of object %d.\n", (int)((1 + cur-
rent_value*1.0/weight[maximum]) * 100), price[maximum], weight[maximum], maximum
+ 1);
total_value -= price[maximum];
total_value += (1 + (float)current_value/weight[maximum]) *
price[max
imum];
}
}
printf("Filled the knapsack with items worth ₹%.2f.\n", total_value);
}

int main() {
//Max
weight int
M = 60;
//Number of items
int n = 3;
Greedy_Knapsack(M,n

Conclusion/Observation

In Fractional Knapsack, we can break items for maximizing the total value of knapsack. This
problem in which we can break an item is also called the fractional knapsack problem.
A brute-force solution would be to try all possible subset with all different fraction but that will be
too much time taking.

An efficient solution is to use Greedy approach. The basic idea of the greedy approach is to
calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the
item with the highest ratio and add them until we can’t add the next item as a whole and at the end
add the next item as much as we can. Which will always be the optimal solution to this problem.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
6.2 Program Title:
Write a program to implement the activity-selection problem stated as follows:
You are given n activities with their start and finish times. Select the maximum number of
activities that can be performed by a single person, assuming that a person can only work on a
single activity at a time. Example: Consider the following 6 activities (0, 1, 2, 3, 4, 5). start[] =
{1, 3, 0, 5, 8, 5}; finish[] = {2, 4, 6, 7, 9, 9}; The maximum set of activities that can be
executed by a single person is {0, 1, 3, 4}.

Input/Output Screenshots:
RUN-1:

Source code

#include<stdio.h>

void greedy_activity_selector(int s[],int f[],int n)

{ int i = 0; printf("activity 0\n");
for(int m = 1;m<n;m+
+){ if(s[m] >=
f[i]){
printf("activity %d\
n",m); i = m;
}
}
}

int main(){
int start[] = {1,3,0,5,8,5};
int finish[] = {2,4,6,7,9,9};
greedy_activity_selector(start,finish,6);

Conclusion/Observation

For the given activities that uses a single resource individually, Activity selection problem find outs
the maximum subset of mutually compatible activities (non-conflicting). Each activity is assumed
with a start time and an end time. The greedy choice is to always pick the next activity whose finish
time is least among the remaining activities and the start time is more than or equal to the finish time
of previously selected activity. We can sort the activities according to their finishing time so that we
always consider the next activity as minimum finishing time activity.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
6.3 Program Title:
Write a program to implement the file or code compression using Huffman’s algorithm.

Input/Output Screenshots:

RUN-1:

RUN-2:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code

#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100

struct MinHeapNode{
char data;
unsigned freq;
struct MinHeapNode *left, *right;
};
struct MinHeap{
unsigned size;
unsigned capacity;
struct MinHeapNode** array;
};
struct MinHeapNode* newNode(char data, unsigned freq){
struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct Min-
HeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
struct MinHeap* createMinHeap(unsigned capacity){
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(minHeap -> capacity * sizeo
f(struct MinHeapNode*));
return minHeap;
}
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b){
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
void minHeapify(struct MinHeap* minHeap, int idx){
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;

if (left < minHeap->size && minHeap->array[left]-> freq < minHeap->ar-

ray[smallest]->freq)
smallest = left;
if (right < minHeap->size && minHeap->array[right]-> freq < minHeap->ar-
ray[smallest]->freq)
smallest = right;
if (smallest != idx){
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 minHeapify(minHeap, smallest);
}
}

int isSizeOne(struct MinHeap* minHeap){

return (minHeap->size == 1);
}

struct MinHeapNode* extractMin(struct MinHeap* minHeap){

struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode){
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq){
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap* minHeap){
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
void printArr(int arr[], int n){
int i;
for (i = 0; i < n; ++i)
printf("%d", arr[i]);
printf("\n");
}

int isLeaf(struct MinHeapNode* root){

return !(root->left) && !(root->right);
}
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size){
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] = newNode(data[i], freq[i]);
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
{
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
while (!isSizeOne(minHeap)){
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}

void printCodes(struct MinHeapNode* root, int arr[], int top){

if (root->left){
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right){
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (isLeaf(root)){
printf("%c: ", root->data);
printArr(arr, top);
}
}
void HuffmanCodes(char data[], int freq[], int size){
struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
int main(){
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}

Conclusion/Observation

We can observe that the codes (bit sequences) are assigned in such a way that the code assigned to
one character is not the prefix of code assigned to any other character. This is how Huffman Coding
makes sure that there is no ambiguity when decoding the generated bitstream.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 LAB - 7

Dynamic Programming
(Matrix Chain Multiplication, Longest Common Subsequence)

PROGRAM EXERCISE

CONTENTS
Prog. Page
No. Program Title No.
7.1 Finding longest common subsequence using dynamic programming.

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 PROGRAM SOLUTIONS
7.1 Program Title:
Finding longest common subsequence using dynamic programming.

Input/Output Screenshots:

RUN-1:

RUN-2:

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
 Source code

#include <stdio.h>
#include <string.h>

void lcstable(char str1[],char str2[]){

int m = strlen(str1);
int n = strlen(str2);
char B[m+1][n+1];
int C[20][20];
for (int i = 0; i <= m; i++)
C[i][0] = 0;
for (int i = 0; i <= n; i++)
C[0][i] = 0;

// Building the mtrix in bottom-up way

for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
C[i][j] = C[i - 1][j - 1] + 1;
B[i][j]='\\';
}
else if (C[i - 1][j] >= C[i][j - 1]) {
C[i][j] = C[i - 1][j];
B[i][j]='^';
}
else {
C[i][j] = C[i][j - 1];
B[i][j]='<';
}
}

int index = C[m][n];

char lcsAlgo[index + 1];
lcsAlgo[index] = '\0';
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcsAlgo[index - 1] = str1[i - 1];
i--;
j--;
index--;
}
else if (C[i - 1][j] > C[i][j - 1])
i--;
else
j--;
}

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar
for (int i = 0; i <=m; i++)
{
for (int j = 0; j <=n; j++)
{
if(i==0 || j==0) printf("%d\t",C[i][j]);
else printf("%d%c\t",C[i][j],B[i][j]);
}
printf("\n");
}
printf("str1 : %s \nstr2 : %s \n", str1, str2);
printf("LCS: %s\n", lcsAlgo);
}
void main(){
char str1[50],str2[50];
printf("Enter the string 1\
n"); scanf("%s",str1);
printf("Enter the string 2\
n"); scanf("%s",str2);
lcstable(str1,str2);
}

Conclusion/Observation

Dynamic programming is an algorithmic technique for solving an optimization problem by

breaking it down into simpler subproblems and utilizing the fact that the optimal solution to
the overall problem depends upon the optimal solution to its subproblems.

We use the method of dynamic programming to find the longest common subsequence
(LCS), defined as the longest subsequence that is common to all the given sequences,
provided that the elements of the subsequence are not required to occupy consecutive
positions within the original sequences.

The time taken by a dynamic approach is the time taken to fill the table (i.e. O(mn)).

School of Computer Engineering, KIIT Deemed to be University,

Bhubaneswar