COMSATS University, Islamabad

Islamabad Campus
Department of Computer Science

Read before Attempt

FA24 Page 1
Subject: Design and Analysis of Algorithm | Instructor: Tanveer Ahmed Siddiqui

Class: BS(CS)- 5A, BS(CS)- 5B, BS(AI), BS(DS)

Assigned Date: September 23, 2024 Due Date: October 7, 2024

CLO-4: Analyze best, average, and worst-case behaviors of an algorithm.

Read the following instructions before attempting to solve this assignment.

Submission: This is an individual assignment. Submit handwritten soft copy. (Word or PDF format).
Understand the Assignment Thoroughly:
el

Make sure you fully grasp the requirements and objectives of the assignment.
Clarify any doubts with your instructor if necessary.
Read recommended books to gain a deeper understanding of various concepts in this assignment.
Try to consolidate key concepts and ideas from these questions.
Ensure academic integrity and prevent plagiarism: Try to make the solution by yourself and protect your
work from other students. If I found the solution files of some students are same then I will reward

ZEero mal'kS to all those students.

8. Performance Indicators for Every Assicnment (Grading rubric)
The following criteria will be used to grade the assignment.
Category Criteria

Correctness of Complexity e 30%: Correctly identifies the time and space complexity in Big-O
Analysis (30%) notation for all sections.
e 20%: Mostly correct, but with some minor errors or omissions in
complexity analysis.
e 10%: Partially correct complexity analysis but contains significant
errors.
e 0%: Incorrect or missing complexity analysis.

Justification of Complexity e -25%: Provides thorough and well-explained reasoning for time and
(25%) space complexity calculations.
e 15%: Adequate reasoning but lacks depth or completeness.
e 10%: Some justification provided, but it is weak or incorrect.
e 0%: No justification for the complexity analysis.

Comparison of Algorithms e 20%: Clear and accurate comparison of multiple algorithms in terms
(20%) of efficiency, scalability, and trade-offs.
e 15%: Comparison is mostly correct but lacks detail or misses key
points.

FA24 Page 2
 10%: Limited comparison with some inaccuracies or omissions.
0%: No comparison or completely incorrect.

Edge Case and Worst-Case 15%: Thorough analysis of best-case, average-case, and worst-case
Analysis (15%) complexities, with edge case examples.
10%: Provides analysis but lacks completeness (e.g., missing worst-
case or edge cases).
5%: Only one scenario (e.g., best-case) is analyzed.
0%: No consideration of edge or worst cases.

Clarity and Structure of 10%: Well-structured, with clear language and supporting diagrams or
Explanation (10%) examples where needed.
7%: Generally clear but could use more structure or examples.
3%: Unclear or confusing, with minimal supporting details.
0%: Poorly structured, hard to understand, or no explanations
provided.

In order to discourage copying/cheating, 30% marks may be awarded based on the marks obtained either in the
corresponding quiz or a question(s) in the Midterm exam that will be used as multiplying factor. Hence, the
final grades (out of 100) will be calculated as follows:
Obtain Marks = 40% of (marks obtain using

Submission marks (given by the letter grades shown above) + 30 * multiplying factor

FA24 Page 3
Consider the following Algorithm Test(n). Provide a line-by-line analysis and construct function T(x) that gives
the runtime of this algorithm as a function of “”. Also determine the Big-Oh of this algorithm.
Algorithm Test(n)
// Tnput:
// Output:
1. sum « 0
2 fori < Oton
3 if (%2 #0)
4. sum « sum+ Test1(i) + Test1( i+1)
5 else
sum < sum + Testl (i) + Test2(i)
6. end for
7. return sum
Algorithm Test1(a) Algorithm Test2(b)
// Tnput: // Input:
// Output: // Output:
1. fori « Oton’ 1. fori «Oton
2. ac—a*i 2 forj<O0toi
3. end for 3 beb*(i+)
4. return a 4. end for
5 end for
6. return b

Consider the following Algorithm Test(n). Provide a line-by-line analysis and construct function T(x) that gives
the runtime of this algorithm as a function of “”. Also determine the Big-Oh of this algorithm.
Algorithm Test(n)
// Tnput:
// Output:
1. fori < 1ton
2 if (%2 = 0)
3 Testl(i))
4 else
5. forj < 1toi
6. Print(Test2( i ))
7 Print ()
8 end for
9 end for

FA24 Page 4
Algorithm Test1(n) Algorithm Test2(a)
// Tnput: // Input:
// Output: // Output:
1 fori <« Oton 1. sum« 0
2. forj«—0toi 2 fori
< Oton
3. Print (j) 3. sum < sum+a *i
4. end for 4. end for
5. for k< 0 to 3n 5 return sum
6. Print (j)
7. end for
8. end for

Find time complexity of the following algorithms. Use the most suitable notation among O, Q,
and @to specify the time efficiency class of the given algorithm.
Algorithm cOUNT1
Input: n = k? for some integer k.
Output: 37 i for each perfect square j between 1 and n.
Ck—yn
. forj — 1tok
Si al ol i

sumlj]— 0
for i «— 1 to j°
sumlj]— sumlj] +i
end for
end for
return sum[l..k]
Algorithm counT2
Input: A positive integer n.
Output: count = number of times Step 5 is executed.
1. count+ 0
2. fori—1ton
3 m— [n/i|
4. for j —1tom
5. count < count + 1
6. end for
7. end for
8. return count
Algorithm counT3
Input: n = 2¥, for some positive integer k.
Output: count = number of times Step 5 is executed.

1. count+« 0 In for loop analyze

2. i1 ending variable.
3. whilei <n
4. forj —1toi
5. count«+ count + 1
6. end for
7. i 2i
8 . end while
9 . return count

FA24 Page 5
Algorithm counTt4
Input: n = 2¥, for some positive integer k.
Output: count = number of times Step 4 is executed.

count+— 0
W . while n > 1
for j —1lton
count+ count + 1
end for
PNPOP

ne—mn/2
end while
. return count
Algorithm counT5H
b . B
Input: n = 2% , for some positive integer k.
Output: Number of times Step 6 is executed.
1. count— 0
2. fori —1ton
3. je—2
4 while j <n When analyzing inner
5. i3t loop we look into the
6. count« count + 1 LHS of condition and
7. end while and study its behavior,
8. end for at end k gives no. of
9. return count time out loops runs/
Algorithm MODINSERTIONSORT calls inner loop.
Input: An array A[l..n] of n elements.
We use finite AP or GP
Output: A[l..n] sorted in nondecreasing order. that uses k total no of
times it runs.
1. for i<—2ton
2. x— Al
3. k < MODBINARYSEARCH (A[l..i — 1],z)
4. for j—i— 1 downto k
5. Alj + 1] A[j]
6. end for
7. Akl—z
8. end for
Algorithm BOTTOMUPSORT
Input: An array A[l..n] of n elements.
Output: A[l..n] sorted in nondecreasing order.
1 t—1
2. whilet <n
3. s—t; t— 2s; 71— 0
4. while i+t <n
5. MERCE(A,i+ 1,i+s,i+1)
6. ie— i+t
7. end while
8. if i + s <n then MERGE(A,i+1,i+ s,n)
9. end while
‘Where Merge function has time complexity O(n)

FA24 Page 6
Algorithm BRUTE-FORCE PRIMALITYTEST
Input: A positive integer n > 2.
Output: true if n is prime and false otherwise.

L s—|vn]
2. for j —2tos
3. if j divides n then return false
4. end for
5. return true
Consider modifying Algorithm selection sort as shown in Algorithm modselectionsort.
Algorithm MODSELECTIONSORT
Input: An array A[l..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
.fori—1lton—1
for j—i+1lton
G oo

if A[j] < A[z] then interchange A[i] and A[j]

end for
end for
a) What is the minimum number of element assignments performed by Algorithm modselectionsort? When is this
minimum achieved?
b) What is the maximum number of element assignments performed by Algorithm modselectionsort? Note that each
interchange is implemented using three element assignments. When is this maximum achieved?
Algorithm BUBBLESORT
Input: An array A[l..n] of n elements.
Output: A[l..n] sorted in nondecreasing order.
1. 1—1; sorted— false
2. while 7 <n — 1 and not sorted
3. sorted — true
4. for j—n downto i + 1
5. if A[j] < A[j — 1] then
6. interchange A[j] and A[j — 1]
7. sorted < false
8. end if
9. end for
10. ie—1+1
11. end while
a) What is the minimum number of element comparisons performed by the BUBBLESORT algorithm?
‘When is this minimum achieved?
b) What is the maximum number of element comparisons performed by the BUBBLESORT algorithm?
‘When is this maximum achieved?
c) What is the minimum number of element assignments performed by the BUBBLESORT algorithm?
‘When is this minimum achieved?
d) What is the maximum number of element assignments performed by the BUBBLESORT algorithm?
‘When is this maximum achieved?
e) Express the running time of Algorithm BUBBLESORT in terms of the O and Q notations.

FA24 Page 7
 f) Can the running time of the algorithm be expressed in terms of the ®-notation? Explain.
Consider the following insertion sort algorithm.
Algorithm INSERTIONSORT
Input: An array A[l..n] of n elements.
Output: A[l..n] sorted in nondecreasing order.
1. fori—2ton
z— Ali]
PRSPWD

je—i—1
while (j > 0) and (A[j] > z)
Alj + 1] A[j]
j—3j—1
end while
Aj+1]—=z
9. end for
Computing the average number of comparisons performedby Algorithm INSERTIONSORT.

uppose you have algorithms with the five running times listed below. (Assume these are the exact
running times.) How much slower does each of these algorithms get when you
1. Double the input size
2. Increase the input size by one?
Solution:

(—

nlogn
on

n2
n3
100n2
nlogn
on

Set up a recurrence relation for the given functions. Solve recurrence relation using Recursion Tree Method.
Use appropriate asymptotic notation among O, Q, and 0 to specify the time efficiency class of the given
function.
Test(n) Test(n)
{ {
if(n == 1) if(n = @)

FA24 Page 8
 return return
else else
{ {
for (i = 1; i < n; i++) for (i = 1; i < n; i= i*2)
{ {
Print(i) Print(i)
} }
Test(n-1)
Test(n/2) }
Test(n/4) }
Test(n/8)
}
3
Test(n) Test(n)
{ {
if(n = @) if(n == @)
return return
else else
{ {
for (i = 1; i <= n; i++) for( i =n/2; i <= n; i++)
{ for( j = 1; j+n/2 <= n; j++)
for (3 =1; j <n; j+=1) for( k = 1; k <= n;
{ k=k*2)
// Some 0(1) task Print(k)
} Test (n/2)
} }
for (k = 1; k < 5; k+) }
{
Test(n/2)
}
}
}
Test(n) Test(n)
{ {
if(n = @) if(n = @)
return return
else else
{ {
for (i = 1; i <= n; i++) for (i = 1; i <= n; i++)
{ {

// Some 0(1) task // Some 0(1) task

} }

Test(n/3) Test(n-1)
Test(n/3) Test(n/2)
Test(n/3) }
Test(n/3) }

FA24 Page 9
 }
}
Test(n) Test(n)
{ {
if(n = @) if(n = @)
return return
else else
{ {
0(1) Task for (i = 1; i <= n; i++)
Test(n-1) {
Test(n-1)
} // Some 0(1) task
} }

Test(n/3)
Test(2n/3)
}
}

Consider the following recursion for integer multiplication of two positive number a and b:
a*l=a
a*b=ab-1)+a
This can be implemented using following recursive algorithm as follows:
Algorithm recursive_multiplication(a, b)
if b=1 then
return a
else
return a+ recursive_multiplication ( a, b-1)
a) Setup and solve a recurrence relation for the number of times the algorithm’s basic operation is executed.
Consider the following recursion for integer multiplication of two positive number a and b
ALGORITHM multiplication(x . y)
// Input: Two positive integers
// Output: The product of the positive integers x and y.
answer « 0 // initialize answer
i<0
while(i < x) do
answer « answer +y
i «i+1
retwn answer
b) Setup a summation expressing the number of times the algorithm’s basic operation is executed. What is
the efficiency class of this algorithm?
¢) How does the given algorithm compare with the straightforward iterative algorithm for computing this
multiilication?

Set up and solve a recurrence relation for the number of times the algorithm’s basic operation is executed. Use
the most suitable asymptotic notation among O, Q, and © to specify the time efficiency class of the following
given algorithm.
ALGORITHM Sum (X, 7, n)

FA24 Page 10
// This algorithm compute the sum of the numbers x; through x, in a list X from left to right
// Pre-Condition:
// Post-Condition:
if i = n then
sum « x;
else
sum « X; + SumiX, i+1,ni

Find time complexity of the following algorithm. Use the most suitable notation among O, Q,
and ©to specify the time efficiency class of the given algorithm.
Algorithm BinaryInsertionSort (4, n) BinarySearch (A, low, high, key)
if (low = high) then
for i <— 1ton-1do return low
ins = BinarySearch (4, 0, 7, A[i]) mid = low + ((high - low) / 2)
if (ins <1) then if (key > A[mid]) then
temp = A[i] return BinarySearch (A, mid + 1, high, key)
for j < i-1to ins do else if (key < A[mid])
A[j+1]1=4[j] return BinarySearch (A, low, mid, key)
Alins] = temp return mid;

Find time complexity of the following algorithms. Use the most suitable asymptotic notation
among O, Q, and © to specify the time efficiency class of the given algorithm.

Algorithm binomial Coeff(n, k)

// Base Cases
if (k >n)
return 0;
ifk=0] k=n)
return 1;
// Recursive definition
return binomialCoeff(n - 1, k - 1)+ binomialCoeff(n - 1, k);

Algorithm binomial Coeff{( n, k)

fori <~ Otondo

forj < 0 to min(i, k); do
if G=0|j
=1) then
Chlpl=1;
else
CllG]=Cli- 1][j - 1]+ C[i - 1][j];
return C[n][k];
Solution:
Om*k;

FA24 Page 11
 Compute the time complexity of the following algorithms. Use the most suitable asymptotic
notation among O, Q, and @ to specify the time efficiency class of the given algorithm.
Algorithm les(X, Y, m,n)

ifm=0[n=0)
return 0;
if X[m-1] = Y[n-1])
return 1 +les(X, Y, m-1, n-1);
else
return max(les(X, Y, m, n-1), les(X, Y, m-1, n));

Algorithm les(X, Y, m, n)
ifm=0[n=0)
return 0;
if X[m-1]=Y[n-1])
return dp[m][n]=1+1les(X, Y, m-1,n- 1, dp);

if (dp[m][n] !=-1)
return dp[m][n];

return dp[m][n] = max(les(X, Y, m, n - 1, dp),les(X, Y, m - 1, n, dp));

Algorithm les(X, Y, m, n)
for (inti=0;1<=m; i++)

! for (int j = 0; j <=n; j++)

! if(i=0j==0)
L[] =0;
elseif X[i-1]=Y[j-1])
LOJGI=LE-1]0-1]+1;
else
) L{][j] = max(L[i - 1[G, LE]G - 10);

}
return L[m][n];

—
Consider the following algorithm.
i. Setup arecurrence relation for the number of times the algorithm’s basic operation is executed.
ii. Solve the recurrence relation that you obtained in part (i) using:
a. Iteration Method
b. Recursion Tree Method
c. Substitution Method

ALGORITHM Search(A[/....]. I, . key)

/I' A recursive search function.

FA24 Page 12
// Input: An Array A[l..r]
// Output: It returns location of key in given array A, otherwise -1

if (> 1) then
{
my=1+@-1)3;
my=mi+ (r-1)/3;
// If key is present at the m;
if (A[m] = key) then
return m;;
// If key is present at the m
if (A[m2] =key) then
return mo;
// If key is present in left one-third
if (A[m1] > key) then
return Search (A, /, m;-1, key);
// If key is present in right one-third
if (A[m2] < key) then
return Search (A, my+1, 7, key):
// If key is present in middle one-third
return Search (A, mxt1, mx-1, key):
}
// We reach here when element is not present in array
return -1;
}

Consider the following algorithm.

iii. Setup arecurrence relation for the number of times the algorithm’s basic operation is executed.
iv. Solve the recurrence relation that you obtained in part (i) using
a. Iteration Method
b. Recursion Tree Method
c. Maser Theorem
MERGE-SORT( array A, int p. int 1)
1if (p < r) then
2 q <13
3 qp <2(0/3)
4 MERGE-SORT(A, p. q;) /sort Alp.. q;]
5 MERGE-SORT(A, q, + . qp) //sortAfq; + 1.. q;]
6 MERGE-SORT(A, q, + 1, 1) //sortAlq, + 1.r]
7 MERGE(A. p. q;. q5.1) ./ merge the three pieces

FA24 Page 13
 MERGE (array A, it p. int q;. int g,. int r)
1 nt Blp.rl:int i~ & printj - q; + Lint ke g, + 1
2. while(7 = q;) and(j = q,) and (k - r) do
3. if (A[/] = A[j])
and ((A[j]- A[k])) then
4 Bl/++] « Alk++]
5
elseif (A[/] =~ A[/]) and ((A[/] = A[k])) then
6. B[l++] « A[j++]
7. else (A[7/] — A[/]) and ((A[j] = A[£])) then
8. B[+ < A[i++]
9. while (7 = q;)do
10. B[l++] < A[i++]
11. while (j - ;) do
12. B[++] < A[j++]
13. While (k= r)do
14. B[l++] < Alk++]
15. Fori-ptor
16. A[i] < B[i]

a) Give asymptotic upper and lower bounds for T (n) of the following recurrence relation.
T(n)= 2T(\3/Z_b +lgn
b) Use arecursion tree to give an asymptotically tight solution to the recurrence 7'(n) = 5T(n — c) + f(n)
¢) The recurrence 7(n) = 7T (n/2)+n* describes the running time of an algorithm 4. A competing algorithm
A’ has arunning time of 7’(n) = a T’(n/4) + n>. What is the largest integer value for a such that 4" is
asymptotically faster than 4?
d) Can the master method be applied to the recurrence T (n) = 4T(w/2) + n? Ig n? Why or why not? Give an
asymptotic upper bound for this recurrence.

St ate the general formula for the following recurrence of the form:

1 d ifn<l1
T(n) = { aTl'(n/c)+ b otherwise.

2 d ifn<l
T(n) = { al'(n/c) + bn? otherwise.

T i d ifn<l
n)= aT(n/c) 4+ bn* otherwise.

FA24 Page 14