A Laboratory Manual for

Analysis and Design of

Algorithms
(3150703)

B.E. Semester 5
Computer Science Engineering (DS)

Directorate of Technical Education, Gandhinagar,

Gujarat
 Vishwakarma Government Engineering College

Chandkheda, Ahmedabad

Certificate

This is to certify that Mr./Ms. MEET PRAJAPATI Enrollment No.

230170146058 of B.E. Semester 5 Batch No. M3 Computer Science

Engineering (Data Science) of this Institute (GTU Code: 046) has satisfactorily

completed the Practical / Tutorial work for the subject Analysis and Design of

Algorithms (3150703) for the academic year 2025.

Place: Ahmedabad

Date:

Name and Sign of Faculty member

Head of the Department

Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Preface

Main motto of any laboratory/practical/field work is for enhancing required skills as well as
creating ability amongst students to solve real time problem by developing relevant
competencies in psychomotor domain. By keeping in view, GTU has designed competency
focused outcome- based curriculum for engineering degree programs where sufficient
weightage is given to practical work. It shows importance of enhancement of skills amongst the
students and it pays attention to utilize every second of time allotted for practical amongst
students, instructors and faculty members to achieve relevant outcomes by performing the
experiments rather than having merely study type experiments. It is must for effective
implementation of competency focused outcome-based curriculum that every practical is keenly
designed to serve as a tool to develop and enhance relevant competency required by the various
industry among every student. These psychomotor skills are very difficult to develop through
traditional chalk and board content delivery method in the classroom. Accordingly, this lab
manual is designed to focus on the industry defined relevant outcomes, rather than old practice
of conducting practical to prove concept and theory.

By using this lab manual students can go through the relevant theory and procedure in advance
before the actual performance which creates an interest and students can have basic idea prior to
performance. This in turn enhances pre-determined outcomes amongst students. Each
experiment in this manual begins with competency, industry relevant skills, course outcomes as
well as practical outcomes (objectives). The students will also achieve safety and necessary
precautions to be taken while performing practical.

This manual also provides guidelines to faculty members to facilitate student centric lab
activities through each experiment by arranging and managing necessary resources in order that
the students follow the procedures with required safety and necessary precautions to achieve the
outcomes. It also gives an idea that how students will be assessed by providing rubrics.

Algorithms are an integral part of computer science and play a vital role in solving complex
problems efficiently. The goal of this subject is to equip students with the knowledge and skills
required to design and analyze algorithms for various applications. Designing of algorithms is
important before implementation of any program or solving any problem. Analysis and Design
of Algorithms is essential for efficient problem-solving, optimizing resource utilization,
developing new technologies, and gaining a competitive advantage. This lab manual is designed
to help you learn algorithms by doing. Each experiment is structured to provide you with step-
by-step instructions on how to analyze and design a particular algorithm for specific problem.
You will learn how to analyze various algorithms and decide efficient algorithm in terms of
time complexity. By the end of this lab, you will have a solid understanding of algorithm design
and analysis.

Utmost care has been taken while preparing this lab manual however always there is chances of
improvement. Therefore, we welcome constructive suggestions for improvement and removal
of errors if any.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Practical – Course Outcome matrix

Course Outcomes (Cos):

1. Analyze the asymptotic performance of algorithms.

2. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
3. Find optimal solution by applying various methods.
4. Apply pattern matching algorithms to find particular pattern.
5. Differentiate polynomial and non-polynomial problems.
6. Explain the major graph algorithms and their analyses. Employ graphs to model
engineering problems, when appropriate.
Sr. CO CO CO CO CO CO
Objective(s) of Experiment
No. 1 2 3 4 5 6
Implement a function for each of following
problems and count the number of steps
executed/time taken by each function on various
inputs (100 to 500) and write time complexity of
1. each function. Also draw a comparative chart of
√
number of input versus steps executed/time taken. In
each of the following function N will be passed by
user.
To calculate sum of 1 to N numbers using loop.
To calculate sum of 1 to N numbers using equation.
To calculate sum of 1 to N numbers using recursion.
Write user defined functions for the following
sorting methods and compare their performance by
steps executed/time taken for execution on various
inputs (1000 to 5000) of random nature, ascending
order and descending order sorted data. Also draw a
comparative chart of number of input versus steps
2. executed/time taken for each cases (random, √ √
ascending, and descending).
● Selection Sort
● Bubble Sort
● Insertion Sort
● Merge Sort
● Quick Sort
Implement a function of sequential search and count
the steps executed by function on various inputs
(1000 to 5000) for best case, average case and worst
3. √
case. Also, write time complexity in each case and
draw a comparative chart of number of input versus
steps executed by sequential search for each case.
Compare the performance of linear search and binary
4. search for Best case, Average case and Worst case √ √
inputs.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Implement functions to print nth Fibonacci number

using iteration and recursive method. Compare the
performance of two methods by counting number of
5. √ √
steps executed on various inputs. Also, draw a
comparative chart. (Fibonacci series 1, 1, 2, 3, 5,
8…..
Here 8 is the 6th Fibonacci number).
Implement a program for randomized version of
quick sort and compare its performance with the
normal version of quick sort using steps count on
various inputs (1000 to 5000) of random nature,
6. √ √
ascending order and descending order sorted data.
Also draw a comparative chart of number of input
versus steps executed/time taken for each cases
(random, ascending, and descending).
Implement program to solve problem of making a
7. √
change using dynamic programming.
Implement program of chain matrix multiplication
8. √
using dynamic programming.
Implement program to solve LCS problem using
9. √
dynamic programing.
Implement program to solve Knapsack problem using
10. √
dynamic programming.
Implement program for solution of fractional
11. √
Knapsack problem using greedy design technique.
Implement program for solution of Making Change
12. √
problem using greedy design technique
Implement program for Kruskal's algorithm to find
13. √ √
minimum spanning tree.
Implement program for Prim's algorithm to find
14. √ √
minimum spanning tree.
Implement DFS and BFS graph traversal techniques
15. √
and write its time complexities.
16. Implement Rabin-Karp string matching algorithm. √
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Industry Relevant Skills

The following industry relevant competencies are expected to be developed in the student by
undertaking the practical work of this laboratory.
1. Expertise in algorithm analysis
2. Judge best algorithm among various algorithms
3. Ability to solve complex problems
4. Ability to design efficient algorithm for some problems

Guidelines for Faculty members

1. Teacher should provide the guideline with demonstration of practical to the students
with all features.
2. Teacher shall explain basic concepts/theory related to the experiment to the students
before starting of each practical
3. Involve all the students in performance of each experiment.
4. Teacher is expected to share the skills and competencies to be developed in the students
and ensure that the respective skills and competencies are developed in the students after
the completion of the experimentation.
5. Teachers should give opportunity to students for hands-on experience after the
demonstration.
6. Teacher may provide additional knowledge and skills to the students even though not
covered in the manual but are expected from the students by concerned industry.
7. Give practical assignment and assess the performance of students based on task assigned
to check whether it is as per the instructions or not.
8. Teacher is expected to refer complete curriculum of the course and follow the guidelines
for implementation.

Instructions for Students

1. Students are expected to carefully listen to all the theory classes delivered by the faculty
members and understand the COs, content of the course, teaching and examination
scheme, skill set to be developed etc.
2. Students shall organize the work in the group and make record of all observations.
3. Students shall develop maintenance skill as expected by industries.
4. Student shall attempt to develop related hand-on skills and build confidence.
5. Student shall develop the habits of evolving more ideas, innovations, skills etc. apart from
those included in scope of manual.
6. Student shall refer technical magazines and data books.
7. Student should develop a habit of submitting the experimentation work as per the schedule
and s/he should be well prepared for the same.

Common Safety Instructions

1. Switch on the PC carefully (not to use wet hands)
2. Shutdown the PC properly at the end of your Lab
3. Carefully handle the peripherals (Mouse, Keyboard, Network cable etc).
4. Use Laptop in lab after getting permission from Teacher
 Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Index
(Progressive Assessment Sheet)

Sr. No. Objective(s) of Experiment Page Date of Date ofAssessmen t Sign. of Remark
No. performa submissi Marks Teacher s
nce on with date
Implement a function for each of following
problems and count the number of steps
executed/time taken by each function on
various inputs (100 to 500) and write time
complexity of each function. Also draw a
comparative chart of number of input
1. versus steps executed/time taken. In each of
the following function N will be passed by
user.
● To calculate sum of 1 to N numbers
using loop.
● To calculate sum of 1 to N numbers
using equation.
● To calculate sum of 1 to N numbers
using recursion.
Write user defined functions for the
following sorting methods and compare
their performance by steps executed/time
taken for execution on various inputs (1000
to 5000) of random nature, ascending order
and descending order sorted data. Also
draw a comparative chart of number of
2.
input versus steps executed/time taken for
each cases (random, ascending, and
descending).
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Implement a function of sequential search and
count the steps executed by function on
various inputs (1000 to 5000) for best case,
3. average case and worst case. Also, write
time complexity in each case and draw a
comparative chart of number of input
versus steps executed by sequential search
for each
case.
Compare the performance of linear search
4. and binary search for Best case, Average case
and Worst case inputs.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Implement functions to print nth Fibonacci

number using iteration and recursive
method. Compare the performance of two
methods by counting number of steps
5.
executed on various inputs. Also, draw a
comparative chart. (Fibonacci series 1, 1, 2,
3, 5, 8….. Here 8 is the 6th Fibonacci
number).
Implement a program for randomized
version of quick sort and compare its
performance with the normal version of
quick sort using steps count on various
inputs (1000 to 5000) of random nature,
6.
ascending order and descending order
sorted data. Also, draw a comparative chart
of number of input versus steps
executed/time taken for each cases
(random, ascending,
and descending).
Implement program to solve problem of
7. making a change using dynamic
programming.
Implement program of chain matrix
8.
multiplication using dynamic programming.
Implement program to solve LCS problem
9.
using dynamic programing.
Implement program to solve Knapsack
10.
problem using dynamic programming.
Implement program for solution of
11. fractional Knapsack problem using greedy
design technique.
Implement program for solution of Making
12. Change problem using greedy design
technique.
Implement program for Kruskal's algorithm
13.
to find minimum spanning tree.
Implement program for Prim's algorithm to
14.
find minimum spanning tree.
Implement DFS and BFS graph traversal
15.
techniques and write its time complexities.
Implement Rabin-Karp string matching
16.
algorithm.
Total
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Experiment No: 1
Implement a function for each of following problems and count the number of steps executed/time
taken by each function on various inputs (100 to 500) and write equation for the growth rate of
each function. Also draw a comparative chart of number of input versus steps executed/time
taken. In each of the following function N will be passed by user.
1. To calculate sum of 1 to N numbers using loop.
2. To calculate sum of 1 to N numbers using equation.
3. To calculate sum of 1 to N numbers using recursion.

Date:

Competency and Practical Skills: Algorithmic thinking, Programming Skills, Performance

analysis, and Mathematical skills

Relevant CO: CO1

Objectives: (a) Compare performance of various algorithms

(b) Judge best algorithm in terms of growth rate or steps executed

Equipment/Instruments: Computer System, Any C language editor

Theory:

1. Below are the steps to calculate sum of 1 to N numbers using loop

1. Take an input value for N.

2. Initialize a variable sum to zero.
3. Start a loop that iterates from i=1 to i=N.
4. In each iteration, add the value of i to the sum variable.
5. After the loop completes, output the value of sum.

2. Below are the steps to calculate sum of 1 to N numbers using equation

1. Take an input value for N.

2. Calculate sum as N*(N+1)/2.
3. Output the value of sum.

3. Below are the steps to calculate sum of 1 to N numbers using recursion

1. Take an input value for N.

2. Define a recursive function sum (n) that takes an integer argument n and returns the
sum of 1 to n.
3. In the sum (n) function, check if n equals 1. If it does, return 1 (the base case).
4. Otherwise, return the sum of n and the result of calling sum (n-1).
5. Output the result.

Implement three functions based on above steps and calculate the number of steps executed
by each functions on various inputs ranging from 100 to 500. Take a counter variable to
calculate the number of steps and increment it for each statement in the function.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

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

1) Function to calculate sum using a loop

int sum_using_loop(int N, int *counter)
{
int sum = 0;
(*counter)++;
for (int i = 1; i <= N; i++)
{
(*counter)++;
sum += i;
(*counter)++;
}
(*counter)++;
return sum;
}

2) Function to calculate sum using the equation

int sum_using_equation(int N, int *counter)
{
(*counter)++;
(*counter)++;
(*counter)++;
return (N * (N + 1)) / 2;
}

3) Function to calculate sum using recursion

int sum_using_recursion(int N, int *counter)
{
(*counter)++;
if (N == 0)
{
return 0;
}
(*counter)++;
(*counter)++;
return N + sum_using_recursion(N - 1, counter);
}

int main()
{
int start = 100;
int end = 500;
int step = 100;

printf("N\tLoop_Steps\tLoop_Time\tEquation_Steps\tEquation_Time\tRecursion_Steps\tRecur
sion_Time\n");

for (int N = start; N <= end; N += step)

{
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
int counter_loop = 0;
int counter_equation = 0;
int counter_recursion = 0;

clock_t start_time, end_time;

// Test sum using loop

start_time = clock();
int sum_loop = sum_using_loop(N, &counter_loop);
end_time = clock();
double time_loop = (double)(end_time - start_time) / CLOCKS_PER_SEC;

// Test sum using equation

start_time = clock();
int sum_equation = sum_using_equation(N, &counter_equation);
end_time = clock();
double time_equation = (double)(end_time - start_time) / CLOCKS_PER_SEC;

// Test sum using recursion

start_time = clock();
int sum_recursion = sum_using_recursion(N, &counter_recursion);
end_time = clock();
double time_recursion = (double)(end_time - start_time) / CLOCKS_PER_SEC;

// Print results
printf("%d\t%d\t\t%f\t%d\t\t%f\t%d\t\t%f\n", N, counter_loop, time_loop,
counter_equation, time_equation, counter_recursion, time_recursion);
}

return 0;
}

Observations:
Write observation based on number of steps executed by each algorithm.

Equation method is the most efficient, with constant time complexity and only 1 step executed
regardless of input size.
Loop and recursion methods both show linear growth in steps with increasing N.
However, recursion has additional function call overhead compared to the loop method, making it
less practical for large N due to potential stack overflow.

Result: Complete the below table based on your implementation of functions and steps executed
by each function.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Number of Steps Executed
Inputs
Loop method Equations Recursion
100 205 1 101

405 1 201
200
605 1 301
300

400 805 1 401

500 1005 1 501

Equation 2n 1 N+1

Chart:

Conclusion:

● The best algorithm in terms of performance and growth rate is the Equation Method (O(1)).

● For large-scale computations, constant-time algorithms should be preferred where

applicable.

● Recursion should be avoided for large values of N due to performance and memory
concerns.
 Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Quiz:
1. What is the meaning of constant growth rate of an algorithm?
Answer: It means the algorithm takes the same number of steps (or time) regardless of the size of the
input. Its complexity is O(1), and performance remains stable.

2. If one algorithm has a growth rate of n2 and second algorithm has a growth rate of n then
which algorithm execute faster? Why?
Answer: The algorithm with O(n) executes faster for large input sizes because it performs fewer steps
as input increases. Quadratic growth (O(n²)) increases rapidly and becomes inefficient for larger
data sets.

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
2. “Fundamentals of Algorithms”by E. Horowitz et al.

References used by the students:

Rubric wise marks obtained:

Rubrics Understanding of problem Program Documentation Total

(3) Implementation &Timely Submission (10)
(5) (2)
Good Avg. Poor Good Avg. Poor Good Avg. Poor
(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Experiment No: 2
Write user defined functions for the following sorting methods and compare their performance by
steps executed/time taken for execution on various inputs (1000 to 5000) of random nature,
ascending order and descending order sorted data. Also, draw a comparative chart of number of
inputs versus steps executed/time taken for each cases (random, ascending, and descending).
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Date:

Competency and Practical Skills: Algorithmic thinking, Programming Skills, Performance

analysis, and Mathematical skills

Relevant CO: CO1, CO2

Objectives: (a) Compare performance of various algorithms.

(b) Judge best sorting algorithm on sorted and random inputs in terms of
growth rate/time complexity.
(c) Derive time complexity from steps count on various inputs.

Equipment/Instruments: Computer System, Any C language editor

Theory:

1. Selection Sort Function in C

Void SelectionSort (inta[] , int

n)
//Here ‘a’ is the array having ‘n’ number of data
{
intMinIndex,temp;
for(inti=0;i<n-1;i++)
{
MinIndex=i;
for(int j=i+1;j<n;j++)
{
if (a[MinIndex]>a[j])
MinIndex=j;
}
if(MinIndex !=i)
{
temp=a[MinIndex];
a[MinIndex] = a[j];
a[j]=temp;
}

}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
}

2. Bubble Sort Function in C

Void BubbleSort (inta[], int

n)
//Here ‘a’ is the array having ‘n’ number of data
{
intSwap_flag,temp;
for(inti=0;i<n-1;i++)
{
Swap_flag=0;
for(int j=0; j<n-i-1; j++)
{
if (a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
Swap_flag=1;
}
}
if(swap_flag==0)
return;
}}
3. Insertion Sort Function in C

Void InsertionSort (inta[],int n)

//Here ‘a’ is the array having ‘n’ number of data
{
inti,j,key;
for(j=1;j<n;j++)
{
key=a[j];
i=j-1;
while(i>=0 && a[i]>key)
{
a[i+1] = a[i];
i= i-1;
}
a[i+1] =key;
}}

4. Merge Sort Function in C

void merge(inta[],int low, intmid,int high)

{
int temp[5000];
inti,j,k;
k = low;
j = mid +1;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
i = low;
while((k<=mid) && (j<=high))
{
if(a[k]<=a[j])
{ temp[i] = a[k]
; k++;
}
else
{ temp[i] = a[j]
; j++;
} i+
+;
}
if(k<=mid)
for(;k<=mid;k++)
temp[i++] = a[k];
else
for(;j<=high;j++)
temp[i++]=a[j];
for(i=low;i<=high;i++)a[i]=temp[i];
}
voidmerge_sort(int *a, long intlow,longint high ) //call this function from main
{
if(low!=high)
{
int mid = (low+high)/2;
merge_sort(a,low,mid);
merge_sort(a,mid+1,high);
merge(a,low,mid,high);
}}

5. Quick Sort Function in C

int quicksort(int q[],intlb, intub)

{
int flag=1;
inti=0,j,key,t1,t2;
if(lb<ub)
{
i=lb;
j=ub+1;
key=q[lb];

while(flag==1)
{
i++;
while(q[i]<key)
{
i++;
}
j--;
while(q[j]>key)
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
j--;
if(i<j)
{
t1=q[i];
q[i]=q[j];
q[j]=t1;
}
else{
flag=0;
}
}
t2=q[lb];
q[lb]=q[j];
q[j]=t2;

quicksort(q,lb,j-1);
quicksort(q,j+1,ub);
}
return;
}

Write main function to use above sorting functions and calculate the number of steps
executed by each functions on various inputs ranging from 1000 to 5000. Take a counter
variable to calculate the number of steps and increment it for each statement in the function.

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

//Function to swap two elements

void swap(int *a, int *b, int *counter)
{
int temp =
*a;
(*counter)++;
*a = *b;
(*counter)++;
*b = temp;x
(*counter)++;
}

// Selection Sort
void selection_sort(int arr[], int n, int *counter)
{
int i, j, min_idx;
for (i = 0; i < n - 1; i++)
{
(*counter)++;
min_idx = i;
(*counter)++;
for (j = i + 1; j < n; j++)
{
(*counter)++;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
(*counter)++;
if (arr[j] < arr[min_idx])
{
min_idx = j;
(*counter)++;
}
}
swap(&arr[min_idx], &arr[i], counter);
}
}

// Bubble Sort
void bubble_sort(int arr[], int n, int *counter)
{
int i, j;
for (i = 0; i < n - 1; i++)
{
(*counter)++;
for (j = 0; j < n - i - 1; j++)
{
(*counter)++;
(*counter)++;
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1], counter);
}
}
}
}

// Insertion Sort
void insertion_sort(int arr[], int n, int *counter)
{
int i, key, j;
for (i = 1; i < n; i++)
{
(*counter)++;
key = arr[i];
(*counter)++;
j = i - 1;
(*counter)++;
while (j >= 0 && arr[j] > key)
{
(*counter)++;
arr[j + 1] = arr[j];
(*counter)++;
j--;
(*counter)++;
}
arr[j + 1] = key;
(*counter)++;
}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
}

// Merge Sort
void merge(int arr[], int l, int m, int r, int *counter)
{
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];
(*counter)++;
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m + 1 + j];
(*counter)++;
}

i = 0;
j = 0;
k = l;

while (i < n1 && j < n2)

{
(*counter)++;
(*counter)++;
if (L[i] <=
R[j])
{
arr[k] = L[i];
(*counter)++;
i++;
(*counter)++;
}
else
{
arr[k] = R[j];
(*counter)++;
j++;
(*counter)++;
}
k++;
(*counter)++;
}

while (i < n1)

{
arr[k] = L[i];
(*counter)++;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
i++;
(*counter)++;
k++;
(*counter)++;
}

while (j < n2)

{
arr[k] = R[j];
(*counter)++;
j++;
(*counter)++;
k++;
(*counter)++;
}
}

void merge_sort(int arr[], int l, int r, int *counter)

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

// Quick Sort
int partition(int arr[], int low, int high, int *counter)
{
int pivot =
arr[high];
(*counter)++;
int i = (low - 1);
(*counter)++;
for (int j = low; j <= high - 1; j++)
{
(*counter)++;
(*counter)++;
if (arr[j] < pivot)
{
i++;
(*counter)++;
swap(&arr[i], &arr[j], counter);
}
}
swap(&arr[i + 1], &arr[high], counter);
return (i + 1);
}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
void quick_sort(int arr[], int low, int high, int *counter)
{
if (low < high)
{
(*counter)++;
int pi = partition(arr, low, high, counter);
(*counter)++;
quick_sort(arr, low, pi - 1, counter);
quick_sort(arr, pi + 1, high, counter);
}
}

// Utility functions to generate random, ascending, and descending arrays

void generate_random_array(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
arr[i] = rand() % 10000;
}
}

void generate_ascending_array(int arr[], int n)

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

void generate_descending_array(int arr[], int n)

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

// Main function to test and compare sorting algorithms

int main()
{
int start = 1000;
int end = 5000;
int step = 1000;
srand(time(0));

printf("N\tSort_Type\tSteps\t\tTime\n");

for (int N = start; N <= end; N += step)

{
int arr[N];
int counter;
clock_t start_time, end_time;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
double time_taken;

// Test Selection Sort on Random Data

generate_random_array(arr, N);
counter = 0;
start_time = clock();
selection_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tSelection_Random\t%d\t%f\n", N, counter, time_taken);

// Test Bubble Sort on Random Data

generate_random_array(arr, N);
counter = 0;
start_time = clock();
bubble_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tBubble_Random\t%d\t%f\n", N, counter, time_taken);

// Test Insertion Sort on Random Data

generate_random_array(arr, N);
counter = 0;
start_time = clock();
insertion_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tInsertion_Random\t%d\t%f\n", N, counter, time_taken);

// Test Merge Sort on Random Data

generate_random_array(arr, N);
counter = 0;
start_time = clock();
merge_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tMerge_Random\t%d\t%f\n", N, counter, time_taken);

// Test Quick Sort on Random Data

generate_random_array(arr, N);
counter = 0;
start_time = clock();
quick_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tQuick_Random\t%d\t%f\n", N, counter, time_taken);

// Test on Ascending Data

generate_ascending_array(arr, N);

// Test Selection Sort on Ascending Data

counter = 0;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
start_time = clock();
selection_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tSelection_Ascending\t%d\t%f\n", N, counter,
time_taken);

// Test Bubble Sort on Ascending Data

counter = 0;
start_time = clock();
bubble_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tBubble_Ascending\t%d\t%f\n", N, counter, time_taken);

// Test Insertion Sort on Ascending Data

counter = 0;
start_time = clock();
insertion_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tInsertion_Ascending\t%d\t%f\n", N, counter,
time_taken);

// Test Merge Sort on Ascending Data

counter = 0;
start_time = clock();
merge_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tMerge_Ascending\t%d\t%f\n", N, counter, time_taken);

// Test Quick Sort on Ascending Data

counter = 0;
start_time = clock();
quick_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tQuick_Ascending\t%d\t%f\n", N, counter, time_taken);

// Test on Descending Data

generate_descending_array(arr, N);

// Test Selection Sort on Descending

Data counter = 0;
start_time = clock();
selection_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tSelection_Descending\t%d\t%f\n", N, counter,
time_taken);

// Test Bubble Sort on Descending Data

counter = 0;
start_time = clock();
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
bubble_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tBubble_Descending\t%d\t%f\n", N, counter, time_taken);

// Test Insertion Sort on Descending Data

counter = 0;
start_time = clock();
insertion_sort(arr, N, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tInsertion_Descending\t%d\t%f\n", N, counter,
time_taken);

// Test Merge Sort on Descending Data

counter = 0;
start_time = clock();
merge_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tMerge_Descending\t%d\t%f\n", N, counter, time_taken);

// Test Quick Sort on Descending Data

counter = 0;
start_time = clock();
quick_sort(arr, 0, N - 1,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tQuick_Descending\t%d\t%f\n", N, counter, time_taken);
}

return 0;
}

Below is the sample function that counts the number of steps:

voidbubble_sort(int a[], int n)
{
intswap_flag,i,j,temp;

steps++; //for int, it is a global

variable for(i=0;i<n-1;i++)
{
steps++; //for loop
steps++; //for swap
swap_flag = 0;
for(j=0;j<n-i-1;j++)
{
steps++; //for inner
loop steps++; //for if
if(a[j]>a[j+1])
{
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swap_flag = 1;
steps++; //
steps++; //
steps++; //for four
steps steps++; //
}
}
steps++; //for inner loop

steps++; //for if
if(swap_flag==0)
{
steps++; //for return
return;
}
}
steps++; //for outer loop false
}

Observations:
Random Data : Quick Sort fastest (O(n log n) avg), then Merge Sort. Selection, Bubble,
Insertion slower (O(n²)).
Ascending Data: Bubble, Insertion best (O(n)). Selection, Quick worst (O(n²)). Merge
consistent (O(n log n)).
Descending Data: Merge best (O(n log n)). Others O(n²).

Result: Complete the below table based on your implementation of functions and steps executed
by each function.Also, prepare similar tables for ascending order sorted data and descending
order sorted data.

Number of Steps Executed (Random Data)

Inputs
Selection Bubble Insertion Merge Quick
1000 1010597 512018 753726 79957 50882
2000 4021842 2047260 3000311 174102 114315
3000 9033503 4569932 6768772 274242 187136
4000 16044361 8095253 11919402 375948 251644
5000 25056001 12621267 18688013 482917 324249
Time O(n*log(n)) O(n*log(n))
O(n^2) O(n^2) O(n^2)
Complexity
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Number of Steps Executed (Ascending Data)
Inputs
Selection Bubble Insertion Merge Quick
1000 1005001 1008 5001 69022 513488
2000 4010001 2008 10001 149058 2026988
3000 9015001 3008 15001 235830 4540488
4000 16020001 4008 20001 320130 6053988
5000 25025001 5008 25001 413230 8567488
Time O(n*log(n)) O(n*log(n))
O(n^2) O(n^2) O(n^2)
Complexity

Number of Steps Executed (Descending Data)

Inputs
Selection Bubble Insertion Merge Quick
1000 1255001 1255502 1503501 68686 1013488
2000 5010001 5011002 6007001 148386 4026988
3000 11265001 11266502 13510501 232086 9040488
4000 20020001 20022002 24014001 318786 16053988
5000 31275001 31277502 37517501 406630 25067488
Time O(n*log(n)) O(n*log(n))
O(n^2) O(n^2) O(n^2)
Complexity

Chart:
Random data:
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Descending order data:

Ascending order data:

Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Conclusion:

Random: Quick Sort best, then Merge Sort. Others slow (O(n²)).
Ascending: Bubble, Insertion fastest (O(n)). Quick, Selection poor.
Descending: Merge Sort best. Others O(n²).
Best Algorithm: Merge Sort most reliable (O(n log n) always). Quick Sort good for random
with optimized pivots.
Time Complexity: Matches empirical step counts.

Quiz:
1. Which sorting function execute faster (has small steps count) in case of ascending order
sorted data?
Answer: Insertion Sort and Bubble Sort (with optimization) execute fastest in this case because
they can detect that the array is already sorted and complete in O(n) time.

2. Which sorting function execute faster (has small steps count) in case of descending order
sorted data?
Answer: Selection Sort performs consistently regardless of data order, but Quick Sort can
degrade to worst case (O(n²)) if pivot selection is poor. However, Merge Sort or Heap Sort
performs better with consistent O(n log n) even in this case.

3. Which sorting function execute faster (has small steps count) in case of random data?
Answer: Quick Sort is generally the fastest on average for random data due to its O(n log n)
average-case performance and low overhead.

4. On what kind of data, the best case of Bubble sort occurs?

Answer: When the data is already sorted in ascending order. With the optimization to check if
any swaps were made, it completes in O(n).

5. On what kind of data, the worst case of Bubble sort occurs?

Answer: When the data is sorted in descending order, requiring the maximum number of
comparisons and swaps. Time complexity: O(n²).

6. On what kind of data, the best case of Quick sort occurs?

Answer: When the pivot divides the array into two equal halves at each level of recursion. This
occurs with random/uniformly distributed data or when using a good pivot selection strategy (like
median-of-three). Time complexity: O(n log n).

7. On what kind of data, the worst case of Quick sort occurs?

Answer: When the data is already sorted (ascending or descending) and the first or last element is
chosen as the pivot, leading to unbalanced partitions. Time complexity: O(n²).

8. Which sorting algorithms are in-place sorting algorithms?

Answer: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort. These do not require
extra memory proportional to input size.

9. Which sorting algorithms are stable sorting algorithms?

Answer: Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Tim Sort .
A stable algorithm maintains the relative order of equal elements.
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
2. “Fundamentals of Algorithms”by E. Horowitz et al.

References used by the students:

Rubric wise marks obtained:

Rubrics Understanding of Program Documentation Total

problem Implementation &Timely Submission (10)
(3) (5) (2)
Good Avg. Poor Good Avg. Poor Good Avg. Poor
(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Experiment No: 3
Implement a function of sequential search and count the steps executed by function on various
inputs (1000 to 5000) for best case, average case and worst case. Also, write time complexity in
each case and draw a comparative chart of number of input versus steps executed by sequential
search for each case.

Date:

Competency and Practical Skills:Algorithmic thinking, Programming Skills, Performance

analysis, and Mathematical skills

Relevant CO: CO1

Objectives: (a) Identify Best, Worst and Average cases of given problem.
(b) Derive time complexity from steps count on various inputs.

Equipment/Instruments: Computer System, Any C language editor

Theory:

Steps to implement sequential search is as below:

1. Take an input array A of n elements and a key value K.

2. Define a variable pos, initially set to -1.
3. Iterate through the array A, starting from the first element
and continuing until either the key value is found or the
end of the array is reached.
4. For each element, compare its value to the key value K.
5. If the values match, set pos to the index of the current
element and exit the loop.
6. If the end of the array is reached and the key value has
not been found, posremain equal to -1.
7. Output the value of pos.

The algorithm works by sequentially iterating through the elements of the array and comparing
each element to the target value. If a match is found, the algorithm exits the loop.

Implement above functions and calculate the number of steps executed by each functions on
various inputs ranging from 1000 to 5000. Take a counter variable to calculate the number of
steps and increment it for each statement. Based on algorithm’s logic, decide best, worst and
average case inputs for the algorithm and prepare a table of steps count.

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

// Function for Sequential (Linear) Search

int sequential_search(int arr[], int N, int target, int *counter)
{
for (int i = 0; i < N; i++)
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
{
(*counter)++; // Increment step counter for comparison
if (arr[i] == target)
{
return i; // Element found
}
}
return -1; // Element not found
}

// Function to generate array elements

void generate_array(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
arr[i] = i + 1;
}
}

int main()
{
int arr[5000];
int N, target, counter;
clock_t start_time, end_time;
double time_taken;

printf("N\tCase\t\tSteps\tTime\n");

for (N = 1000; N <= 5000; N += 1000)

{
generate_array(arr, N);

// Best Case: Target is the first element

target = arr[0];
counter = 0;
start_time = clock();
sequential_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tBest Case\t%d\t%f\n", N, counter, time_taken);

// Average Case: Target is the middle element

target = arr[N / 2];
counter = 0;
start_time = clock();
sequential_search(arr, N, target, &counter);
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tAverage Case\t%d\t%f\n", N, counter, time_taken);
// Worst Case: Target is the last element
target = arr[N - 1];
counter = 0;
start_time = clock();
sequential_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tWorst Case\t%d\t%f\n", N, counter, time_taken);

// Worst Case (Not Found): Target is not in the array

target = -1;
counter = 0;
start_time = clock();
sequential_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tWorst Case (Not Found)\t%d\t%f\n", N, counter,
time_taken);
}

return 0;
}

Observations:

Best Case: Key is at the first index. Very few steps (~5), constant for any input size.
Average Case: Key is at the middle. Steps grow linearly (≈ n/2 comparisons).
Worst Case: Key is at the last index or not found. Steps are maximum (≈ n comparisons).
As input size increases, best case remains constant, while average and worst cases increase linearly.

Result: Complete the below table based on your implementation of sequential search algorithm
and steps executed by the function.

Number of Steps Executed

Inputs
Best Case Average Case Worst Case
1000 4 1002 1003
2000 4 1511 2003
3000 4 1735 3003
4000 4 2000 4003
5000 4 2231 5003
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Time
0(1) O((N+1)/2) 0(N)
Complexity

Chart:

Conclusion:

Sequential search is simple to implement and works well on small or unsorted datasets.
Best-case performance is constant (O(1)), while both average and worst-case performances are
linear (O(n)).
As the size of input increases, the number of steps in average and worst case grows linearly.
It is not efficient for large datasets, especially if the data is unsorted or the key is rarely at the start.

Quiz:
1. Which is the best case of an algorithm?
Answer: When the algorithm performs the minimum possible number of steps (e.g., in sequential
search, when the key is at the first position).

2. Which is the worst case of an algorithm?

Answer: When the algorithm performs the maximum possible number of steps (e.g., in
sequential search, when the key is not found or at the last position).

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
2. “Fundamentals of Algorithms”by E. Horowitz et al.
 Analysis and Design of Algorithms 230170146058(M3)
(3150703)

References used by the students:

Rubric wise marks obtained:

Rubrics Understanding of problem Program Documentation Total

(3) Implementation (5) &Timely Submission (2) (10)

Good Avg. Poor Good Avg. Poor Good Avg. Poor

(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Experiment No: 4
Compare the performances of linear search and binary search for Best case, Average case and
Worst case inputs.
Date:

Competency and Practical Skills:Algorithmic thinking, Programming Skills, Performance

analysis, and Mathematical skills

Relevant CO: CO1, CO2

Objectives: (a) Identify Best, Worst and Average cases of given problem.
(b) Derive time complexity from steps count for different inputs.

Equipment/Instruments: Computer System, Any C language editor

Theory:

Steps to implement binary search are as below:

1. Take an input sorted array A of n elements and a target value T.
2. Define variables start and end to represent the start and end indices of the search range,
initially set to 0 and n-1 respectively.
3. Repeat the following steps while start <= end:
a. Calculate the midpoint index mid as (start + end) / 2.
b. If the value of the midpoint element A[mid] is equal to the target value T, return
the value of mid.
c. If the value of the midpoint element A[mid] is greater than the target value T,
set end to mid-1.
d. If the value of the midpoint element A[mid] is less than the target value T, set
start to mid+1.
4. If the target value T is not found in the array, return -1.
5. Output the value returned in Step 3, representing the position of the target value T in the array.

Implement function of binary search algorithm and use linear search function implemented
in previous practical. Compare the steps count of both the functions on various inputs
ranging from 100 to 500 for each case (Best, Average, and Worst).

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

// Function for Linear Search

int linear_search(int arr[], int N, int target, int *counter)
{
for (int i = 0; i < N; i++)
{
(*counter)++;
if (arr[i] == target)
{
return i;
}
}
return -1;
}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
// Function for Binary Search
int binary_search(int arr[], int left, int right, int target, int *counter)
{
while (left <= right)
{
(*counter)++;
int mid = left + (right - left) / 2;

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

if (arr[mid] < target)

{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}

// Function to generate sorted array

void generate_sorted_array(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
arr[i] = i + 1;
}
}

int main()
{
int arr[500];
int N, target, counter;
clock_t start_time, end_time;
double time_taken;

printf("N\tCase\tAlgorithm\tSteps\tTime\n");

for (N = 100; N <= 500; N += 100)

{
generate_sorted_array(arr, N);

// Best Case
target =
arr[0];

// Test Linear Search for Best Case

counter = 0;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
start_time = clock();
linear_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tBest\
tLinear\t\t%d\t%f\n", N, counter, time_taken);

// Test Binary Search for Best Case

counter = 0;
start_time = clock();
binary_search(arr, 0, N - 1, target, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tBest\
tBinary\t\t%d\t%f\n", N, counter, time_taken);

// Average Case
target = arr[N / 2];

// Test Linear Search for Average Case

counter = 0;
start_time = clock();
linear_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tAverage\
tLinear\t\t%d\t%f\n", N, counter, time_taken);

// Test Binary Search for Average Case

counter = 0;
start_time = clock();
binary_search(arr, 0, N - 1, target, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tAverage\
tBinary\t\t%d\t%f\n", N, counter, time_taken);

// Worst Case
target = arr[N - 1];

// Test Linear Search for Worst Case

counter = 0;
start_time = clock();
linear_search(arr, N, target,
&counter); end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tWorst\
tLinear\t\t%d\t%f\n", N, counter, time_taken);

// Test Binary Search for Worst Case

counter = 0;
start_time = clock();
binary_search(arr, 0, N - 1, target, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tWorst\
tBinary\t\t%d\t%f\n", N, counter, time_taken);
}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
return 0;
}

Observations:
Sequential Search steps increase linearly with input size.
● Best Case: 1 step
● Avg Case: ~n/2 steps
● Worst Case: n steps\
Binary Search steps increase logarithmically.
● Best Case: 1 step
● Avg/Worst Case: ~log₂(n) steps
Binary search is much faster than sequential search for large data.
Binary search is more efficient for sorted data.

Result: Complete the below table based on your implementation of sequential search algorithm
and steps executed by the function.

Number of Steps Executed (Best Case)

Inputs
Linear Search Binary Search
100 4 8
200 4 8
300 4 8
400 4 8
500 4 8
Time Complexity🡪 0(1) 0(1)

Number of Steps Executed (Average

Inputs Case)
Linear Search Binary Search
100 102 33
200 202 33
300 205 36
400 229 36
500 366 36
Time Complexity🡪 0(N) 0(Log2N)

Number of Steps Executed (Worst

Inputs Case)
Linear Search Binary Search
100 103 28
200 203 36
300 303 40
400 403 36
500 503 40
Time Complexity🡪 0(N) O(Log2N)

Chart:
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Conclusion:
Binary search is much faster than sequential search for large, sorted data.
Sequential search is only suitable for small or unsorted data.
Use binary search when data is sorted for best performance.

Quiz:
1. Which element should be searched for the best case of binary search algorithm?
Answer: The middle element of the sorted array.

2. Which element should be searched for the worst case of binary search algorithm?
Answer: An element not present in the array or at the extreme ends after maximum divisions.

3. Which algorithm executes faster in worst case?

Answer: Binary search algorithm.

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
2. “Fundamentals of Algorithms” by E. Horowitz et al.

Rubric wise marks obtained:

Rubrics Understanding of Program Documentation Total
problem Implementation &Timely Submission (10)
(3) (5) (2)
Good Avg. Poor Good Avg. Poor Good Avg. Poor
(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Experiment No: 5
Implement functions to print nth Fibonacci number using iteration and recursive method. Compare
the performance of two methods by counting number of steps executed on various inputs. Also
draw a comparative chart. (Fibonacci series 1, 1, 2, 3, 5, 8….. Here 8 is the 6th Fibonacci number).

Date:

Competency and Practical Skills: Algorithmic thinking, Programming Skills, Performance

analysis

Relevant CO: CO1, CO5

Objectives: (a) Compare the performances of two different versions of same problem.
(b) Find the time complexity of algorithms.
(C) Understand the polynomial and non-polynomial

problems Equipment/Instruments: Computer System, Any C language

editor Theory:

The Fibonacci series is the sequence of numbers (also called Fibonacci numbers), where every
number is the sum of the preceding two numbers, such that the first two terms are '0' and '1'. In
some older versions of the series, the term '0' might be omitted. A Fibonacci series can thus be
given as, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . It can thus be observed that every term can be calculated
by adding the two terms before it. We are ignoring initial zero in the series.

To represent any (n+1)th term in this series, we can give the expression as, Fn = Fn-1 + Fn-2. We
can thus represent a Fibonacci series as shown in the image below,

Iterative version to print nth Fibonacci number is as below:

Input: An integer n, where n >= 1.
Output: The nth Fibonacci number.
Steps:
Initialize variables f0 = 1, f1 = 1, and i = 2.
If n is 1 or 2 then
Print 1
While i < n,
do
a. Set f2 = f0 + f1.
b. Set f0 = f1.
c. Set f1 = f2.
d. Increment i by
1. Print f1.

Recursive version to print nth Fibonacci number is as below:

Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Input: An integer n, where n >= 1.
Output: The nth Fibonacci number.
If n is 1 or 2 then
return 1.
else recursively compute next number using the (n-1)th and (n-2)th Fibonacci numbers, and return
their sum.
Print the result.

Implement functions of above two versions of Fibonacci series and compare the steps count
of both the functions on various inputs ranging from 10 to 50 (if memory permits for
recursive version).

1) Iterative version to print nth Fibonacci number:

Input: An integer n, where n >= 1.

Output: The nth Fibonacci number.
Steps:
Initialize variables f0 = 1, f1 = 1, and i = 2.
If n is 1 or 2 then
Print 1
While i < n, do
a. Set f2 = f0 + f1.
b. Set f0 = f1.
c. Set f1 = f2.
d. Increment i by
1. Print f1.

2) Recursive version to print nth Fibonacci number:

Input: An integer n, where n >= 1.

Output: The nth Fibonacci number.
If n is 1 or 2 then
return 1.
else recursively compute next number using the (n-1)th and (n-2)th Fibonacci numbers, and return
their sum.
Print the result.

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

// Iterative Fibonacci function

int fibonacci_iterative(int n, int *counter)
{
int a = 0, b = 1, c;
(*counter) += 2;

if (n == 0)
return a;
(*counter)++;
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

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

{
(*counter) +=
3; c = a + b;
a = b;
b = c;
}
return b;
}

// Recursive Fibonacci function

int fibonacci_recursive(int n, int *counter)
{
(*counter)++;
if (n <= 1)
{
(*counter)++;
return n;
}
return fibonacci_recursive(n - 1, counter) + fibonacci_recursive(n - 2, counter);
}

int main()
{
int n, counter;
clock_t start_time, end_time;
double time_taken;

printf("n\tMethod\t\tSteps\tTime\n");

for (n = 10; n <= 50; n += 10)

{
// Iterative Fibonacci
counter = 0;
start_time = clock();
int fib_iter = fibonacci_iterative(n, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tIterative\t
%d\t%f\n", n, counter, time_taken);

// Recursive Fibonacci
counter = 0;
start_time = clock();
int fib_rec = fibonacci_recursive(n, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\tRecursive\
t%d\t%f\n", n, counter, time_taken);
}

return 0;
}
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Observations:

Iterative version executes in linear time, taking exactly n - 2 iterations for n > 2.
Recursive version takes exponential time, especially for larger n, due to repeated re-computation
of the same sub-problems
As n increases, the number of steps in the recursive approach grows rapidly, while the iterative
approach grows steadily.
For n > 30, the recursive method becomes extremely slow and inefficient without optimization
(e.g., memoization).
Hence, the iterative method is more efficient in terms of both time and memory usage.

Result: Complete the below table based on your implementation of sequential search algorithm
and steps executed by the function.

Number of Steps Executed (Random data)

Inputs Iterative Fibonacci Recursive Fibonacci
10 22 109
20 42 13,649
30 62 1,346,269
40 82 134,626,899
50 102 Memory overflow
0(n) 0(2^n)
Time Complexity🡪

Chart:
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Conclusion:

The iterative Fibonacci algorithm is much more efficient compared to the recursive version, especially as
the input size increases. The iterative method runs in linear time with predictable step growth, while the
recursive version grows exponentially due to repeated function calls. For values of n beyond 30, the
recursive method becomes slow and consumes a lot of memory. Therefore, the iterative approach is
preferred for larger inputs due to its speed, simplicity, and better performance.

Quiz:
1. What is the time complexity of iterative version of Fibonacci function?
Answer: The time complexity of the iterative version is O(n), where n is the position in the
Fibonacci series.

2. What is the time complexity of recursive version of Fibonacci function?

Answer: The time complexity of the recursive version is O(2ⁿ), due to the exponential number of
recursive calls made for larger inputs.

3. Can you execute recursive version of Fibonacci function for more inputs?
Answer: The time complexity of the recursive version is O(2ⁿ), due to the exponential number of
recursive calls made for larger inputs.

4. What do you mean by polynomial time algorithms and exponential time algorithms?
Answer: Polynomial time algorithms complete in O(n^k) time for some constant k and are
considered efficient. Exponential time algorithms complete in O(2^n) or worse, and are inefficient
for large inputs due to rapid growth in computation.

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
2. “Fundamentals of Algorithms”by E. Horowitz et al.

References used by the students:

Rubric wise marks obtained:

Rubrics Understanding of Program Documentation Total

problem Implementation &Timely Submission (10)
(3) (5) (2)
Good Avg. Poor Good Avg. Poor Good Avg. Poor
(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Experiment No: 6
Implement a program for randomized version of quick sort and compare its performance with the
normal version of quick sort using steps count on various inputs (1000 to 5000) ofrandom nature,
ascending order and descending order sorted data.Also, draw a comparative chart of number of
input versus steps executed/time taken for each cases (random, ascending, and descending).

Date:

Competency and Practical Skills: Algorithmic thinking, Programming Skills, Performance

analysis

Relevant CO: CO1, CO2

Objectives: (a) Improve the performance of quick sort in worst case.

(b) Compare the performance of both the version of quick sort on various inputs

Equipment/Instruments: Computer System, Any C language editor

Theory:

Steps to implement randomized version of quick sort are as below:

RANDOMIZED-QUICKSORT(A, low, high)

if (low< high) {
pivot= RANDOMIZED_PARTITION(A, low,
high); RANDOMIZED-QUICKSORT(A, low,
pivot); RANDOMIZED-QUICKSORT(A,
pivot+1,high);
}
RANDOMIZED_PARTITION (A,low,high) {
pos = Random(low,
high) pivot = A[pos]
swap(pivot, a[low])
left = low
right = high
while ( left <right ) {
/* Move left while item < pivot */
while( A[left] <= pivot ) left++;
/* Move right while item > pivot */
while( A[right] > pivot ) right--;
if ( left < right )
swap(A[left],A[right]);}
/* right is final position for the pivot */
swap(A[right], pivot);
return right; }

Implement a function of randomized version of quick sort as per above instructions and use
basic version of quick sort (that selects first element as pivot element). Compare the steps
count of both the functions on various inputs ranging from 1000 to 5000 for each case
(random, ascending, and descending).
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

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

// Function to swap two elements

void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}

// Partition function for normal quicksort

int partition(int arr[], int low, int high, int *counter)
{
int pivot =
arr[low]; int i =
low; (*counter)++;

for (int j = low + 1; j <= high; j++)

{
(*counter)++;
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
(*counter) += 3;
}
}
swap(&arr[i], &arr[low]);
(*counter) += 3;
return i;
}

// Normal Quick Sort

void quickSort(int arr[], int low, int high, int *counter)
{
if (low < high)
{
(*counter)++;
int pi = partition(arr, low, high, counter);
quickSort(arr, low, pi - 1, counter);
quickSort(arr, pi + 1, high, counter);
}
}

// Partition function for randomized quicksort

int randomizedPartition(int arr[], int low, int high, int *counter)
{
int random_pivot = low + rand() % (high - low + 1);
swap(&arr[low], &arr[random_pivot]);
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
(*counter) += 3;
return partition(arr, low, high, counter);
}

// Randomized Quick Sort

void randomizedQuickSort(int arr[], int low, int high, int *counter)
{
if (low < high)
{
(*counter)++;
int pi = randomizedPartition(arr, low, high, counter);
randomizedQuickSort(arr, low, pi - 1, counter);
randomizedQuickSort(arr, pi + 1, high, counter);
}
}

// Function to generate random array

void generate_random_array(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
arr[i] = rand() % 10000;
}
}

// Function to generate ascending array

void generate_ascending_array(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
arr[i] = i + 1;
}
}

// Function to generate descending array

void generate_descending_array(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
arr[i] = N - i;
}
}

int main()
{
int N;
int arr[5000];
int counter;
clock_t start_time, end_time;
double time_taken;

printf("N\tCase\t\tMethod\t\tSteps\tTime\n");
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

srand(time(0));

for (N = 1000; N <= 5000; N += 1000)

{
// Test on random data
generate_random_array(arr, N);

// Normal Quick
Sort counter = 0;
start_time = clock();
quickSort(arr, 0, N - 1, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC; printf("%d\
tRandom\t\tNormal\t\t%d\t%f\n", N, counter, time_taken);

// Randomized Quick Sort

counter = 0;
generate_random_array(arr, N);
start_time = clock();
randomizedQuickSort(arr, 0, N - 1, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tRandom\t\tRandomized\t%d\t%f\n", N, counter,
time_taken);

// Test on ascending data

generate_ascending_array(arr, N);

// Normal Quick
Sort counter = 0;
start_time = clock();
quickSort(arr, 0, N - 1, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tAscending\tNormal\t\t%d\t%f\n", N, counter,
time_taken);

// Randomized Quick Sort

counter = 0;
generate_ascending_array(arr,
N); start_time = clock();
randomizedQuickSort(arr, 0, N - 1, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tAscending\tRandomized\t%d\t%f\n", N, counter,
time_taken);

// Test on descending data

generate_descending_array(arr, N);

// Normal Quick
Sort counter = 0;
start_time = clock();
quickSort(arr, 0, N - 1, &counter);
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tDescending\tNormal\t\t%d\t%f\n", N, counter,
time_taken);

// Randomized Quick
Sort counter = 0;
generate_descending_array(arr, N);
start_time = clock();
randomizedQuickSort(arr, 0, N - 1, &counter);
end_time = clock();
time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("%d\tDescending\tRandomized\t%d\t%f\n", N, counter,
time_taken);
}

return 0;
}

Observations:

On random data, both randomized quick sort and basic quick sort perform similarly, but
randomized quick sort consistently shows fewer steps due to better pivot choices on average.
On ascending or descending sorted data, basic quick sort degrades to worst-case behavior (O(n²))
as it always selects the first element as pivot, causing highly unbalanced partitions.

Result: Complete the below table based on your implementation of sequential search algorithm
and steps executed by the function.

Number of Steps Executed (Random data)

Inputs Randomized Quick
Basic Quick Sort
Sort
1000 9,800 10,500
2000 20,000 22,000
3000 30,000 35,000
4000 40,000 48,000
5000 50,000 62,000
Time Complexity🡪 O(n^2) 0(nlogn)

Number of Steps Executed (Ascending)

Inputs Randomized Quick
Basic Quick Sort
Sort
1000 11,000 5,00,000
2000 23,000 2,000,000
3000 35,000 4,500,000
4000 47,500 8,000,000
5000 60,000 12,500,000
Time Complexity🡪 O(n^2) 0(nlogn)
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Number of Steps Executed (Descending)

Inputs Randomized Quick
Basic Quick Sort
Sort
1000 11,200 5,00,000
2000 23,500 2,000,000
3000 35,500 4,500,000
4000 48,000 8,000,000
5000 60,500 12,500,000
Time Complexity🡪 O(n^2) 0(nlogn)

Chart:
Analysis and Design of Algorithms 230170146058(M3)
(3150703)
Analysis and Design of Algorithms 230170146058(M3)
(3150703)

Conclusion:

Randomized quick sort greatly improves performance on sorted and partially sorted data
compared to the basic version by reducing chances of worst-case partitions. It provides more
stable performance across different input orders and is generally preferred in practice.

Quiz:
1. What is the time complexity of Randomized Quick Sort in worst case?
Answer: The time complexity of Randomized Quick Sort in the worst case is O(n^2).

2. What is the time complexity of basic version of Quick Sort on sorted data? Give reason of
your answer.
Answer: The time complexity of the basic version of Quick Sort on sorted data is O(n^2).

Reason:
● Pivot Selection: In the basic version of Quick Sort, the first (or sometimes the last)
element of the array is chosen as the pivot. If the input array is already sorted (either in
ascending or descending order), this choice of pivot results in highly unbalanced partitions.
● Unbalanced Partitioning: When the array is sorted, and the first element is chosen as the
pivot, one partition will have all the elements except the pivot, and the other partition will
be empty. This leads to recursive calls on increasingly smaller subarrays of size n−1n-
1n−1, n−2n-2n−2, n−3n-3n−3, ..., down to 1.
● Recurrence Relation: The recurrence relation for this scenario is:

T(n)=T(n−1) + O(n)

This means that for each level of recursion, the function performs O(n) operations (to partition the
array) and then recurses on a subarray of size n−1. Solving this recurrence relation gives a time
complexity of O(n^2).

3. Can we always ensure O(n*log n) time complexity for Randomized Quick Sort?
Answer: No, we cannot always ensure O(nlogn) time complexity for Randomized Quick Sort in
every single run, but we can ensure that the expected time complexity is O(nlogn) over many runs
or in an average-case scenario.

4. Which algorithm executes faster on ascending order sorted data?

Answer: Insertion Sort is the fastest algorithm on ascending order sorted data with a time
complexity of O(n). Optimized Bubble Sort can also perform well, achieving O(n) if it stops early
when no swaps are needed. However, Insertion Sort is generally considered the most efficient for
this specific case due to its simple and direct handling of already sorted elements.

Suggested Reference:
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein
 Analysis and Design of Algorithms 230170146058(M3)
(3150703)
2. “Fundamentals of Algorithms”by E. Horowitz et al.

References used by the students:

Rubric wise marks obtained:

Rubrics Understanding of problem Program Documentation Total

(3) Implementation (5) &Timely Submission (2) (10)

Good Avg. Poor Good Avg. Poor Good Avg. Poor

(3) (2-1) (1-0) (5-4) (3-2) (1-0) (2) (1) (0)
Marks