Design & Analysis of Algorithm
Mid-Term (Fall 2024)
[Link]: __________________ Time: 90 mins
Q1: (10 Marks)
Solve the following recurrence equation, with all the steps and details, using Iterative
substitutionas method, and find the Asymptotic Complexity O(?) for the recurrence.
{
1; if n=1
T ( n )=
4T
n
2
+ cn ; if n>1 ()
Marks Division
1. Three steps correctly opened 3 marks
2. Kth term rightly formed 2 marks
3. K value solved, replaced with k variable 2 marks
4. Series identification and solved the series 2 marks
5. Correct worst case time complexity 1 marks
Solution:
T ( n )=4 T ( n2 )+cn equ M
Put n=n/2 in equ M
T ( n2 )=4 T ( 2n )+ cn2 2
Substitute T ( n2 )value in equ main
T (n)=4 4 T
( ( ) )n cn
2
2
+
2
+cn
¿4 T
n
2
2
2 ( )
+2 cn+ cn
2 n
( )
¿ 8 T 2 +3 cn equ 1
2
Put n=n/4 in equ M
T
( ) ( )
n
2
2
n cn
=4 T 3 + 2
2 2
Substitute T ( 2n )value in equ1
2
T (n)=4 4 T
( 2 )+ 2 )+3 cn
( n cn
2
3 2
¿4 T
( 2n )+ 4 cn+3 cn
3
3
Design & Analysis of Algorithm
Mid-Term (Fall 2024)
[Link]: __________________ Time: 90 mins
¿4 T
3
( 2n )+7 cn equ 2
3
Put n=n/8 in equ M
T
( 2n )=4 T ( 2n )+ cn2
3 4 3
Substitute T ( 2n )value in equ2
3
3
T (n)=4 ¿
4 N
( )
¿ 4 T 4 +8 cn +7 cn
2
th
4 n
( )
¿ 8 T 4 +15 cn
2
K Term … … … … … … .
k
T (n)=4 T
( )n
2
k
k
+ cn(2 −1)
K Value Solved … … … … … … .
n k
Let k =1=¿ n=2
2
k =lo g2 n
K Value Replaced … … … … … … .
lo g n
( )
n
T ( N )=4 ∗T lo g n +cn(2 −1)
2
2 2
lo g n 2
T ( N )=n ∗T ( 1 ) +cn (nlo g 2−1)
lo g 4
2 2
2
T ( N )=n +cn (n−1)
2
T ( N )=O(n )
Q2: (5 Marks)
Irtaza and Muzaffar each have come up with a divide and conquer algorithm to solve a
problem.
Irtaza algorithm (algorithm A) splits a problem of size n into four pieces, each of size n/2,
solves the pieces recursively, and takes time 30n to combine the results.
Muzaffar algorithm (algorithm B) takes time n 3 to turn a problem of size n into a smaller
problem of size n/2, which it then solves recursively.
Marks Division
1. Correctly write down the recurrence equation of both algorithm 1 + 1 marks
2. Correctly write down the running time of both algorithm 1+1 mark
3. Which algorithm has an asymptotically better runtime? 1 mark
a) Write a recurrence for the runtime of Irtaza algorithm, TA(n), and a recurrence for the
runtime of Muzaffar algorithm, TB(n).
TA(n) = 4T(n/2) + 30n
Design & Analysis of Algorithm
Mid-Term (Fall 2024)
[Link]: __________________ Time: 90 mins
TB(n) = T(n/2) + n3
b) What are the running times of each of these algorithms (in big-O notation), and which
algorithm has an asymptotically better runtime?
TA(n) = O(n2)
TB(n) = O(n3)
Q3: (10 Marks)
Given a set N of integers and an integer y, determine if there exit two elements in N whose
absolute difference is equal to y and also print those numbers. The algorithm should take
O(nlgn) time. Justify why your algorithm runs in O(nlgn) time.
e.g. Let N = 3, 7, 2, 1, 4, 10
y=1
1,2 ,3, 4, 7, 10
There are three pairs of elements in N whose absolute difference is 1.
Pair 1 = |3 - 2| = |-1| = 1
Pair 2 = |3 - 4|= |-1| = 1
Pair 3 = |2 -1| = 1
Marks Division
Note: Give the zero marks if the algorithm take O(n2).
1. Function with right general argument and return type 2 Marks
2. sort elements (NlogN) 3 Marks
3. for each element x use binary search (logN per element) to find |x - y| in sorted list. 5 Marks
Ans:
1. sort elements (NlogN)
2. for each element x use binary search (logN per element) to find |x - y| in sorted list.
3. Total time (NlogN + NlogN) = (2NlogN) = O(NlogN)
Psuedocode
Algorithm FindAbsoluteDifferencePairs(N, y):
Input: A list N of n integers, and an integer y
Output: Print all pairs (a, b) from N such that |a - b| = y
1. Sort the list N in ascending order // O(n log n)
2. for each element x in N: // O(n)
a. target1 ← x - y
b. target2 ← x + y
c. if BinarySearch(N, target1) then
print "Pair:", (x, target1)
Design & Analysis of Algorithm
Mid-Term (Fall 2024)
[Link]: __________________ Time: 90 mins
d. if BinarySearch(N, target2) then
print "Pair:", (x, target2)
Procedure BinarySearch(A, key):
Input: Sorted list A, value key
Output: true if key exists in A, else false
1. low ← 0, high ← length(A) - 1
2. while low ≤ high:
a. mid ← (low + high) // 2
b. if A[mid] == key: return true
c. else if A[mid] < key: low ← mid + 1
d. else: high ← mid - 1
3. return false
Q4: (3+3+4Marks)
MergeSort (arr, start, end)
{
If (start < end)
Let mid = start + ⌊(end-start)/2⌋
{
MergeSort (arr, start, mid) //Line 3
MergeSort (arr, mid+1, end) //Line 4
Merge (arr, start, mid, end) //Line 5
}
}
Suppose the size of “arr” is 13 (start=1, end=13) when MergeSort is first called.
(Note: The indexing starts from 1.” )Let “arr” be
4 1 18 5 3 7 2 15 1 1 8 29 2
1
Solve the following:
Marks Division
Note: Give the zero marks if the answer is incorrect or partially incorrect.
a) Write the values of “start”, “mid”, and “end” when “Line 3” is reached for 5th time.
“start”=3; “mid”=3, and “end”=4
b) Write the values of “start”, “end” and “arr content” when “Line 4” is reached for 4th time.
“start”= 1 , “end”= 7 and “arr content”
1 4 5 1 3 7 2 15 1 11 8 29 2
8
Design & Analysis of Algorithm
Mid-Term (Fall 2024)
[Link]: __________________ Time: 90 mins
c) Write the values of start”, “mid”, “end” and “arr content” when “Line 5” is reached for 4th
time.
“start”=5; “mid”=5, and “end”=6
“arr content”=
1 4 5 1 3 7 2 15 1 11 8 29 2
8
Q5: (2+2+4+2Marks)
Find the operations/cost and frequency of each line of code given below. Show detailed
calculations as done in class.
Marks Division
Correctly find out the time complexity of Line 1 1mark
Correctly find out the time complexity of Line 2 1mark
Correctly find out the time complexity of Line 3 2marks
Correctly find out the time complexity of Line 4 1mark
Operation Cost * Frequency
for (i = 1; i <= n; i = i *2) c 1∗⌊ lo g2 n ⌋ +2
{
m
for (j = 1; j <= m; j = j + 2) c 2∗(⌊lo g2 n ⌋ +1)(⌈ ⌉ +1)
2
{
m
for (k = j; k > 0; k = ⌊k / 2 ⌋ ) c 3∗(⌊ lo g2 n ⌋ +1) ∑ (⌊ ¿ lo g2 j ⌋ +2)¿
j=1
j odd
{
m
a = a * 2 – 3; c 4∗( ⌊lo g2 n ⌋ +1) ∑ (⌊ ¿ lo g2 j ⌋ + 1)¿
j=1
j odd
}
}
}