National University of Computer & Emerging Sciences, Karachi
Fall-2018 Department of Computer Science
Mid Term - I
1st October 2018, 11:00 am– 12:00 noon
Course Code: CS302 Course Name: Design and Analysis of Algorithm
Instructor Name / Names: Dr. Muhammad Atif Tahir, Subhash Sagar and Zeshan Khan
Student Roll No: Section:
Instructions:
• Return the question paper.
• Read each question completely before answering it. There are 7 questions on 2 pages.
• In case of any ambiguity, you may make assumption. But your assumption should not
contradict any statement in the question paper.
Time: 60 minutes. Max Marks: 12.5
Question # 1 [2 marks]
Use worst case analysis to construct a function T(n) that gives the runtime complexity of the
algorithm as a function of n. Simple example is shown in Figure: 1.
Function_A(a, n) { Figure: 1
int i, j, temp, flag=true;
for (i=0; i<n-1;i++) {
for (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 ;
}
}
}
}
Solution # 1
SUBHASH SAGAR
Function_A(a, n) {
int i, j, temp, flag=true; c1 (0.5)
for (i=0; i<n-1;i++) { c2*n
for (j=0; j<n-i-1; j++) { c3*n(n+1)/2
if (a [j] > a [j+1]) { c4*n(n+1)/2
temp = a[j]; c5*n(n+1)/2 (1.0)
a [j] = a [j+1]; c6*n(n+1)/2
a [j+1] = temp ; c7*n(n+1)/2
}
}
}
}
Hence T(n) = c1+c2*n+(c3+c4+c5+c6+c7)/2*n(n+1)
= c1+ (c2+(c3+c4+c5+c6+c7)/2)*n+(c3+c4+c5+c6+c7)/2*𝑛2 ≈ 𝑎𝑛2 + 𝑏𝑛 + 𝑑
𝑻(𝒏) = 𝜽(𝒏𝟐 ) ------- (0.5)
Question # 2 [1 mark]
Let A, B and C are three different algorithms designed for some task T. Their worst time
complexity are respectively: 𝑓1 (𝑛) = 3𝑛20 𝑙𝑜𝑔𝑛, 𝑓2 (𝑛) = 2𝑛22 and 𝑓3 (𝑛) = 90𝑛17 +
𝑛20 respectively. Which algorithm is suitable for task T (Explain Briefly?).
Solution # 2
f3(n) due to lowest growth function (1 mark)
Question # 3 [0.75*4=3 marks]
Mark each of following expression by True or False. State the reason.
a) 𝟐𝒏 + 𝒏! ∈ 𝑶(𝒏!)
𝒏(𝒏+𝟏)
b) ∈ 𝛀(𝒏)
𝟐
c) √𝟏𝟎𝒏𝟐 + 𝟕𝒏 + 𝟑 ∈ 𝜽(𝒏𝟐 )
d) 𝟒𝐥𝐨𝐠𝟐 𝒏 ∈ 𝒐(𝒏)
Solution # 3 True or False (0.25) and Correct Reasoning (0.5)
True: [As 𝑛! is greater than 2𝑛 ]
True: [𝑓(𝑛 >= 𝑐𝑔(𝑛) 𝑠𝑎𝑡𝑖𝑓𝑖𝑒𝑠 𝑖𝑓 𝑐 >= 1 𝑎𝑛𝑑 𝑛 >= 1 ],
False: [If we solve square root, equation will be linear so 𝜃(𝑛2 ) is not possible],
False: [𝑛2 is always greater than n so 𝑜(𝑛) is not possible]
SUBHASH SAGAR
Question # 4 [0.5 marks]
Find the recursive relation (e.g. T(n)=T(n-1)+n) for the following algorithm:
Function_A(n){ Solution # 4
if (n > =1) {
m = 1; T(n)=2T(n/2)+1
return 0;
}
else
m=n/2;
for (i=1; i<=2; i++)
Function_B(m);
}
Function_B(n) {
Function_A (n); }
Question # 5 [2.5 marks]
Compute the time complexity of the following recursive relation by using Recurrence-Tree
Method or Iterative Substitution Method.
𝑻(𝒏) = 𝟏𝟔𝑻(𝒏/𝟐) + 𝒏, 𝑻(𝟏) = 𝟏
Solution # 5 Right Hand Side Eq. (𝟏𝟔𝒌 ) (1 mark)
Left Hand Side Eq. (n+8n_+..) (1 mark)
Final Answer - (0.5 marks)
SUBHASH SAGAR
Question # 6
[0.5*4=2 marks]
Solve the following recurrences using Master’s Method. Give argument, if the recurrence cannot
be solved using Master’s Method.
a) 𝑻(𝒏) = 𝟗𝑻(𝒏/𝟑) + 𝒏
𝒏
b) 𝑻(𝒏) = 𝟐𝒏 𝑻 (𝟐) + 𝒏𝒏−𝟏
c) 𝑻(𝒏) = √𝟐𝑻(𝒏/𝟐) + 𝐥𝐨𝐠 𝟐 𝟐
d) 𝑻(𝒏) = 𝟑𝑻(𝒏/𝟑) + 𝒏
Solution # 6 (0.5 marks) each
(a) a = 9, b = 3, d = 1. Since a > bd , Thus T(n) = Theta(nlog39)
(b) Cannot be applied since f(n) is not polynomial
(c) a =sqrt(20, b= 2, d = 0 (Since log2 = 1 i.e. n^0). Since a > bd Thus T(n) =
Theta(nlog2sqrt(2))
(d) a= 3, b = 3, d = 1, a = bd, Thus T(n) = Theta(nlogn)
Question # 7 [1.5 marks]
Consider the following algorithm with 𝑂(𝑛3 ) complexity. Provide a 𝑂(𝑛2 ) solution for this
algorithm.
Algorithm (Matrix A, Matrix B){
a=n/2
for (i=0;i<n;i++){
for (j=0;j<=a;j++){
if (j%i==0){
j+=1;}
for (k=0;k<n;k++){
X[i][k]=A[i][k]+B[i][k]
}
}
}}
Solution # 7
Algorithm(Matrix A, Matrix B){ or
a=n/2
for(i=0;i<n;i++){
for(j=0;j<=a;j++){
if(j%i==0) (0.75)
j+=1;
}
}
for(i=0;i<n;i++){
for(k=0;k<n;k++){
X[i][k]=A[i][k]+B[i][k]; (0.75)
SUBHASH SAGAR
}}}
Or
for(i=0;i<n;i++){
for(k=0;k<n;k++){ (1.5)
X[i][k]=A[i][k]+B[i][k];
}}
SUBHASH SAGAR
