PRACTICAL FILE
Subject : Analysis and Design of Algorithms
Subject Code : BTIT-305
Institute : Shri Vaishnav Institute of Information Technology
Submitted by : Submitted to :
Aman Bind Mr. Ankit Jain
Roll No. – 19100BTCSEMA05472 Shri Vaishnav Institute of
Information Technology (SVIIT)
Class – B.Tech CSE (MA)
Shri Vaishnav Vidyapeeth
Semester – III (2nd Year) Vishwavidyalaya, Indore (MP)
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
1. Write a Program to find the time complexity of linear Search.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
int ct = 0;
int main(){
int arr[15] = {1594, 6548, 7842, 9410, 6512, 9431, 5120, 8413, 4201, 6969, 3313, 2615,
9991, 5050, 1649}; ct++;
int item; ct++;;
cout<<"\nEnter the element to be searched : "; ct++;
cin>>item; ct++;
int j; ct++;
for(j=0; j<15; j++){
ct++;
if(item == arr[j]){
ct++;
cout<<"\n"<<item<<" found at position "<<j+1; ct += 4;
break; ct++;
}
if(j == 15){
ct++;
cout<<"\nItem "<<item<<" not found in array"; ct += 3;
}
}
cout<<"\nTime complexity of Linear Search is "<<ct;
return 0;
}
Output:
Worst Complexity is O(25).
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
2. Write a program to find the time complexity of recusive binary search.
Code:
#include<iostream>
using namespace std;
int ct = 0;
int binaryScr(int arr[], int start, int end, int data){
ct += 4;
if (end >= start){
ct++;
int mid = start + (end - start) / 2; ct++;
if (arr[mid] == data){
ct++;
return mid; ct++;
}
if(arr[mid] > data){
ct += 2;
return binaryScr(arr, start, mid - 1, data);
}ct++;
return binaryScr(arr, mid + 1, end, data); ct++;
} ct++;
return -1; ct++;
}
int main(){
int arr[15] = {1594, 1649, 2615, 3313, 4201, 5050, 5120, 6512, 6548, 6969, 7842, 8413,
9410, 9431, 9991};
int data;
cout<<"\nEnter the element to be searched : ";
cin>>data;
int result = binaryScr(arr, 0, 14, data);
if(result == -1){
ct++;
cout<<data<<" not found in array"; ct += 2;
}
else{
cout<<data<<" found at position "<<result+1; ct += 3;
}
cout<<"\nTime complexity of Recursive Binary Search is "<<ct;
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
3. Write a program to find the time complexity of Iterative binary search.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
int ct = 0;
int main(){
int arr[15] = {1594, 1649, 2615, 3313, 4201, 5050, 5120, 6512, 6548, 6969, 7842, 8413,
9410, 9431, 9991}; ct++;
int data, start, end, mid; ct += 4;
cout<<"\nEnter the element to be searched : "; ct++;
cin>>data; ct++;
start = 0; ct++;
end = 14; ct++;
mid = (start + end)/2; ct++;
while(data != arr[mid] && start <= end){
ct += 3;
if(data > arr[mid]){
ct++;
start = mid + 1; ct++;
}
else{
end = mid-1; ct++;
}
mid = (start + end)/2; ct++;
}
if(data == arr[mid]){
ct++;
cout<<data<<" found at position "<<mid+1; ct += 3;
}
if(start > end){
ct++;
cout<<data<<" not found in array"; ct += 2;
}
cout<<"\nTime complexity of Iterative Binary Search is "<<ct;
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
4. Write a program for sorting in case heap.
Code:
#include<iostream>
using namespace std;
int insert(int arr[], int n){
int i = n;
int item = arr[n];
while((i>1) && (arr[i/2]<item)){
arr[i] = arr[i/2];
i = i/2;
}
arr[i] = item;
return 0;
}
int main(){
int arr[]={0,9,18,24,155,10,71,84,31,72};
//arr[0] = 0 so that indexing can tart from 1 and thus making everything more clear to average
user
for(int i=1; i<=9; i++){
insert(arr, i);
}
cout<<"\nElement in array are :";
for(int i = 1; i<=9; i++){
cout<<"\n"<<arr[i];
}
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
5. Write a program of heapify.
Code:
#include<iostream>
using namespace std;
int adjust(int arr[], int i, int n){
int j = 2*i;
int item = arr[i];
while(j<=n){
if((j<n) && (arr[j]<arr[j+1])){
j = j + 1;
}
if(item>=arr[j]){
break;
}
arr[j/2] = arr[j];
j = 2*j;
}
arr[j/2] = item;
return 0;
}
int heapify(int arr[], int n){
for(int i = n/2; i >= 1; i--){
adjust(arr, i, n);
}
return 0;
}
int main(){
int arr[]={0,9,18,24,155,10,71,84,31,72};
//arr[0] = 0 so that indexing can start from 1 and thus making everything more clear to average
user
heapify(arr, 9);
cout<<"\nElement in array are :";
for(int i = 1; i<=9; i++){
cout<<"\n"<<arr[i];
}
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
6. Write a program of heap sort.
Code:
#include<iostream>
using namespace std;
int adjust(int arr[], int i, int n){
int j = 2*i;
int item = arr[i];
while(j<=n){
if((j<n) && (arr[j]<arr[j+1])){
j = j + 1;
}
if(item>=arr[j]){
break;
}
arr[j/2] = arr[j];
j = 2*j;
}
arr[j/2] = item;
return 0;
}
int heapify(int arr[], int n){
for(int i = n/2; i >= 1; i--){
adjust(arr, i, n);
}
return 0;
}
int HeapSort(int arr[], int n){
heapify(arr, n);
int t;
for(int i = n; i >= 2; i--){
t = arr[i];
arr[i] = arr[1];
arr[1] = t;
adjust(arr, 1, i-1);
}
return 0;
}
int main(){
int arr[]={0,9,18,24,155,10,71,84,31,72};
cout<<"\nElement in array before Heap Sort :";
for(int i = 1; i<=9; i++){
cout<<"\n"<<arr[i];
}
//arr[0] = 0 so that indexing can start from 1 and thus making everything more clear to average
user
HeapSort(arr, 9);
cout<<"\n\nElement in array after heap Sort :";
for(int i = 1; i<=9; i++){
cout<<"\n"<<arr[i];
}
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
7. Write a program of merge sort.
Code:
#include<iostream>
using namespace std;
#define MAX 1000
int array[MAX];
void merge(int low, int mid, int high){
int temp[MAX];
int i = low;
int j = mid + 1;
int k = low;
while((i <= mid) && (j <= high)){
if (array[i] <= array[j]){
temp[k++] = array[i++];
}
else{
temp[k++] = array[j++];
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= high){
temp[k++] = array[j++];
}
for(i = low; i <= high; i++){
array[i] = temp[i];
}
}
void merge_sort(int low, int high){
int mid;
if(low != high){
mid = (low + high)/2;
merge_sort(low, mid);
merge_sort(mid + 1, high);
merge(low, mid, high);
}
}
int main(){
int n;
cout<<"\nEnter the number of elements : ";
cin>>n;
for(int i = 0; i < n; i++){
cout<<"Enter Element "<<i+1<<" : ";
cin>>array[i];
}
cout<<"\nSorted List is :-\n";
merge_sort(0, n-1);
for(int i = 0; i < n; i++){
cout<<array[i]<<"\n";
}
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
8. Write a program of quick sort.
Code:
#include<iostream>
#define MAX 100
using namespace std;
int array[MAX];
int interchange(int array[], int i, int j){
int p=array[i];
array[i]=array[j];
array[j]=p;
return 0;
}
int partition(int array[], int m, int p){
int v=array[m];
int i=m;
int j=p+1;
do{
do{
i++;
}while(array[i]<v && i<=p);
do{
j--;
}while(v<array[j]);
if(i<j){
interchange(array,i,j);
}
}while(i<j);
array[m]=array[j];
array[j]=v;
return j;
}
int quicksort(int array[], int p, int q){
int j;
if(p<q){
j=partition(array,p,q);
quicksort(array,p,j-1);
quicksort(array,j+1,q);
}
return 0;
}
int main(){
int n;
cout<<"Enter the no. of Elements :";
cin>>n;
for(int i=0; i<n; i++){
cout<<"Element "<<i+1<<" : ";
cin>>array[i];
}
quicksort(array,0,n-1);
cout<<"\nAfter Quick Sort :\n";
for(int i=0; i<n; i++){
cout<<array[i]<<"\n";
}
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
9. Write a program of Stressen’s matrix multiplication.
Code:
#include<iostream>
using namespace std;
//Aman Bind (section K)
int main(){
int array1[2][2],array2[2][2],array3;
int p,q,r,s,t,u,v,i,j,c11,c12,c13,c14;
cout<<"Enter the elements of 2x2 Matrix 1:\n";
for(i=0;i<2;i++){
for(j=0;j<2;j++){
cin>>array1[i][j];
}
}
cout<<"Enter the elements of 2x2 Matrix 2:\n";
for(i=0;i<2;i++){
for(j=0;j<2;j++){
cin>>array2[i][j];
}
}
p=(array1[0][0]+array1[1][1])*(array2[0][0]+array2[1][1]);
q=(array1[1][0]+array1[1][1])*array2[0][0];
r=array1[0][0]*(array2[0][1]-array2[1][1]);
s=array1[1][1]*(array2[1][0]-array2[0][0]);
t=(array1[0][0]+array1[0][1])*array2[1][1];
u=(array1[1][0]-array2[0][0])*(array2[0][0]+array2[0][1]);
v=(array1[0][1]-array1[1][1])*(array2[1][0]+array2[1][1]);
c11=p+s-t+v;
c12=r+t;
c13=q+s;
c14=p-r+q+u;
cout<<"\nProduct of above matrix by Strassen matrix is:\n" ;
cout<<"C11 = "<<c11;
cout<<"\nC12 = "<<c12;
cout<<"\nC13 = "<<c13;
cout<<"\nC14 = "<<c14;
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
10. Write a program of 0/1 Knapsack using Greedy Method.
Code:
#include<iostream>
using namespace std;
void knapsack(float*,float*,float,float);
int main()
{
float value[50],weight[50],max,n;
cout<<"Enter the maximum capacity of knapsack: ";
cin>>max;
cout<<"Enter the number of item: ";
cin>>n;
cout<<"Enter the values of item,according to per unit value in descending order:\n";
for(int i=0; i<n; i++){
cin>>value[i];
}
cout<<"\nEnter the values of weight according to value of item:\n";
for(int i=0; i<n; i++){
cin>>weight[i];
}
cout<<"\nElements enter by you is \n";
for(int i=0; i<n; i++){
cout<<"value = "<<value[i]<<" & weight = "<<weight[i]<<"\n";
}
knapsack(value,weight,max,n);
}
void knapsack(float value[],float weight[],float max,float n){
float current=0,i,rem;
float currentval=0;
for(int i=0; i<n; i++){
if((current<=max)&& (weight[i]<=max-current)){
current=current+weight[i];
currentval=currentval+value[i];
}
}
rem = max - current;
cout<<"\n\nmaximum profit is: "<<currentval;
cout<<"\nweight left: "<<rem;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
11. Write a program of Prim’s Algorithm for MST.
Code:
#include <iostream>
#define v 6
#define MAX 9999
using namespace std;
int minVertex(int value[6], bool setMST[6]){
int minimum = MAX;
int vertex;
for(int i=0; i<v; i++){
if(((setMST[i] == false)) && (value[i] < minimum)){
vertex = i;
minimum = value[i];
}
}
return vertex;
}
void find_mst(int graph[6][6]){
int parent[v];
int value[v];
bool setMST[v];
for(int i=0; i<v; i++){
parent[i] = 0;
value[i] = MAX;
setMST[i] = false;
}
parent[0] = -1;
value[0] = 0;
for(int i=0; i<v; i++){
int minV = minVertex(value, setMST);
setMST[minV] = true;
for(int j=0; j<v; j++){
if((graph[minV][j] != 0) && (setMST[j] == false) && (graph[minV][j] < value[j])){
value[j] = graph[minV][j];
parent[j] = minV;
}
}
}
cout<<"\nMinimum Spanning Tree is: \n";
int total_weight = 0;
for(int i = 1; i<v; i++){
cout<<"for "<<parent[i]<<" to "<<i<<" weight = "<<graph[parent[i]][i]<<"\n";
total_weight += graph[parent[i]][i];
}
cout<<"\nTherefore total weight is "<<total_weight;
}
int main()
{
int graph[v][v] = {{0,4,6,0,0,0},
{4,0,6,3,4,0},
{6,6,0,1,8,0},
{0,3,1,0,2,3},
{0,4,8,2,0,7},
{0,0,0,3,7,0}};
find_mst(graph);
return 0;
}
Output:
SHRI VAISHNAV VIDYAPEETH VISHWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
NAME - Aman Bind SUBJECT – Analysis and Design of Algorithms
ROLL NO. - 19100BTCSEMA05472 DEPARTMENT - SVIIT (CSE)
CLASS – B.Tech CSE MA CODE NO. – BTIT-305
12. Write a program of Kruskal’s Algorithm for MST.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
class Edge {
public:
int source;
int dest;
int weight;
};
int find_parent(int vertex, int *parent){
if(parent[vertex] == vertex){
return vertex;
}
return find_parent(parent[vertex], parent);
}
bool compare_weight(Edge E1, Edge E2){
return E1.weight < E2.weight;
}
void kruskals(Edge *input, int n, int E){
sort(input, input+E, compare_weight);
Edge *output = new Edge[n-1];
int *parent = new int[n];
for(int i=0; i<n; i++){
parent[i] = i;
}
int count = 0;
int i = 0;
while(count != n-1){
Edge currentEdge = input[i];
int sourceParent = find_parent(currentEdge.source, parent);
int destParent = find_parent(currentEdge.dest, parent);
if(sourceParent != destParent){
output[count] = currentEdge;
count++;
parent[sourceParent] = destParent;
}
i++;
}
int total_weight = 0;
for(int i=0; i<n-1; i++){
cout<<"\nfor "<<output[i].source<<" to "<<output[i].dest<<" weight =
"<<output[i].weight<<"kg";
total_weight += output[i].weight;
}
cout<<"\nTotal Weight is "<<total_weight;
int main()
{
int n, E;
cout<<"Enter total no. of vertices : ";
cin>>n;
cout<<"Enter total no. of edges :";
cin>>E;
Edge *input = new Edge[E];
for(int i = 0; i<E; i++){
int s, d, w;
cout<<"Enter Source, Destination and Weight of Edge "<<i+1<<" : ";
cin>>s>>d>>w;
input[i].source = s;
input[i].dest = d;
input[i].weight = w;
}
kruskals(input, n, E);
return 0;
}
Output:
