Analysis and Design

of Algorithm

(3150703)
Lab Manual

Name: Nishar Alam

Er. No: 200570116024
Class : 5ED1 Batch-C
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Lab Practical: Page No Signature

1. Implementation and Time analysis of sorting algorithms:
a. Bubble sort
b. Selection sort
c. Insertion sort.
d. Merge sort.
e. Quick sort.
2. Implementation and Time analysis of linear and binary
search algorithms.
3. Implementation of max-heap sort algorithm.

4. Implementation and Time analysis of factorial program

using iterative and recursive method.

5. Implementation of a knapsack problem using dynamic

programming.
6. Implementation of chain matrix multiplication using
dynamic programming.
7. Implementation of making a change problem using
dynamic programming.
8. Implementation of a knapsack problem using greedy
algorithm.
9. Implementation of Graph and Searching algorithm BFS
and DFS.
10. Implement prim’s algorithm.

11. Implement kruskal’s algorithm.

12. Implement the LCS problem.

1
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
Practical 1

1. Implementation and Time analysis of sorting algorithms.

Bubble sort, Selection sort, Insertion sort,Merge sort, Quick sort

Algorithm:

Code for Bubble Sort:

// Code for time analysis of Bubble sort
#include <stdio.h>
#include <time.h>
int main()
{
int arr[50], num, x, y, temp;
time_t start, end;
double tc;
printf("Please Enter the Number of Elements: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements \n");
for (x = 0; x < num; x++)
scanf("%d", &arr[x]);
start = clock();
for (x = 0; x < num - 1; x++)
{
for (y = 0; y < num - x - 1; y++)
{
if (arr[y] > arr[y + 1])
{
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
end = clock();
printf("Array after bubble sort: ");
for (x = 0; x < num; x++)
{
printf("%d ", arr[x]);
}
tc = (difftime(end, start) / CLOCKS_PER_SEC);

2
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
printf("\nTime efficiency is %lf\n", tc);
return 0;
}

Output:

Time Complexity:
Best case: O(n)
Worst case: O(n2)
Average case: O(n2)

3
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Algorithm:

Code for Insertion Sort:

// Code for time analysis of Insertion Sort

#include <stdio.h>
#include <time.h>
void main()
{
int i, j, n, temp, a[30];
time_t start, end;
double tc;
printf("Please Enter the number of Element: ");
scanf("%d", &n);
printf("\nPlease Enter the Value of Elements \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
start = clock();
for (i = 1; i <= n - 1; i++)
{
temp = a[i];
j = i - 1;
while ((temp < a[j]) && (j >= 0))
{
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = temp;
}
printf("\nValue of Element After Sorting:\n");
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
end = clock();

4
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
tc = (difftime(end, start) / CLOCKS_PER_SEC);
printf("\ntime efficiency is %lf", tc);
}

Output:

Time Complexity:
Best case: O(n)
Worst case: O(n2)
Average case: O(n2)

5
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Algorithm:

Code for Selection Sort:

// Code for time analysis of Selection Sort

#include <stdio.h>
#include <time.h>
int main()
{
int a[10], i, j, n, min, temp;
time_t start, end;
double tc;
printf("Please Enter the number of Element: ");
scanf("%d", &n);
printf("\nPlease Enter the Value of Elements \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
start = clock();
for (i = 0; i < n - 1; i++)
{
min = a[i];
for (j = i + 1; j < n; j++)
{
if (a[j] < a[i])
{
min = j;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
printf("%d,", a[i]);
}
printf("%d", a[i]);
end = clock();
tc = (difftime(end, start) / CLOCKS_PER_SEC);

6
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
printf("\ntime efficiency is %lf", tc);
return 0;
}

Output:

Time Complexity:
Best case: O(n2)
Worst case: O(n2)
Average case: O(n2)

7
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Algorithm:

Code for Merge Sort:

// Code for time analysis of Merge Sort
#include <stdio.h>
#include <time.h>
void merge(int arr[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2)
{
if (L[i] <= M[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;

8
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
}
while (j < n2)
{
arr[k] = M[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);
}
}
// Print the array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
clock_t t;
double total_t;
int n = 10, i;
int arr[50] = {15, 94, 82, 72, 66, 59, 48, 38, 25, 51};
t = clock();
mergeSort(arr, 0, n - 1);
t = clock() - t;
total_t = (double)(t) / CLOCKS_PER_SEC;
printf("\nMerge Sort: ");
printArray(arr, n);
printf("Time efficiency is %f", total_t);
}

9
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Output:

Time Complexity:
Best case: O(nlogn)
Worst case: O(nlogn)
Average case: O(nlogn)

10
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Algorithm:

Code for Quick Sort:

// Code analysis for QuickSort
#include <stdio.h>
#include <time.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int array[], int low, int high)
{
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
if (array[j] <= pivot)
{
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high)
{
if (low < high)
{
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
// Print the array
void printArray(int arr[], int size)

11
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
{
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
clock_t t;
double total_t;
int n = 10, i;
int arr[50] = {10, 94, 67, 50, 66, 90, 55, 38, 25, 51};
t = clock();
quickSort(arr, 0, n - 1);
t = clock() - t;
total_t = (double)(t) / CLOCKS_PER_SEC;
printf("\nQuick Sort: ");
printArray(arr, n);
printf("Time efficiency is %f", total_t);
}

Output:

Time Complexity:
Best case: O(nlogn)
Worst case: O(n2)
Average case: O(nlogn)
12
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

13
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
Practical -2

2. Implementation and Time analysis of linear and binary search

algorithms.

Algorithm:

Code for Linear Search:

#include <stdio.h>
int search(int arr[], int n)
{
int i, flag;
for (i = 0; i < 5; i++)
{
if (arr[i] == n)
{
flag = i + 1;
break;
}
else
flag = 0;
}
if (flag != 0)
printf("Value found at location %d ", flag);
else
return -1;
}
int main()
{
int i, arr[5], n, value;
printf("Please enter 5 numbers one by one:\n");
for (i = 0; i < 5; i++)
scanf("%d", &arr[i]);
printf("Please enter which value do you want to search: ");
scanf("%d", &n);
value = search(arr, n);
}

14
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Output:

Time Complexity:
Best case: O(1)
Worst case: O(nlogn)
Average case: O(nlogn)

15
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Algorithm:

Code for Binary Search:

#include <stdio.h>
int main()
{
int n, s, f, m, l, i, a[100];
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter the numbers one by one:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Please enter a value to search: ");
scanf("%d", &s);
f = 0;
l = n - 1;
m = (f + l) / 2;
while (f <= l)
{
if (a[m] < s)
f = m + 1;
else if (a[m] == s)
{
printf("%d found at location %d", s, m + 1);
break;
}
else
l = m - 1;
m = (f + l) / 2;
}
if (f > l)
printf("Value not found!");
}

16
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm

Output:

Time Complexity:
Best case: O(1)
Worst case: O(nlogn)
Average case: O(nlogn)

17
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
Practical-3

3. Implementation of max-heap sort algorithm.

Algorithm:

Code for Max-heap Sort:

#include <stdio.h>

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

int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;

if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

18
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {1, 12, 8, 5, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}

Output:

Time Complexity:
Best case: O(nlogn)
Worst case: O(nlogn)
Average case: O(nlogn)

19
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
Practical-4

4. Implementation and Time analysis of factorial program using iterative and

recursive method.

Algorithm:

Code for: Iterative and recursive method.

#include <stdio.h>
#include <time.h>
int fact(int x)
{
double f = x;
if (x != 1)
f *= fact(x - 1);
else
return 1;
return f;
}
void main()
{
int i, n;
double a, fa = 1;
clock_t end, start;
double cpu;
printf("\nEnter a number to find factorial ");
scanf("%d", &n);
start = clock();
for (i = n; i > 0; i--)
{
fa *= i;
}
end = clock();
cpu = ((double)(end - start) / CLOCKS_PER_SEC);

printf("\nFactorial of %d is %lf", n, fa);

printf("\nTime for iterative is %lf\n", cpu);
start = clock();
a = fact(n);

20
 FACULTY OF ENGINEERING
Information Technology
Analysis and Design of Algorithm
end = clock();
cpu = ((double)(end - start) / CLOCKS_PER_SEC);

printf("\nFactorial of %d is %lf", n, a);

printf("\nTime for recursive is %lf", cpu);
printf("\n");
}

Output:

Time Complexity:
Best case: O(n)
Worst case: O(n)
Average case: O(n)

21