CSE373, MAT373: Analysis of Algorithms, Mock Midterm Exam 1 (Solution Hints)

CSE373, MAT373: Analysis of Algorithms, Spring 2021 Date: March 23, 2021


Mock Midterm Exam 1 (Solution Hints)
( 6:35 PM – 7:50 PM : 75 Minutes )

• This exam will account for 20% of your overall grade.

• There are five (5) questions, worth 75 points in total. Please answer all of them.

• This is a closed book, closed notes exam. No cheat sheets are allowed.

• You are allowed to use scratch papers for your calculations.




Good Luck!




Question Parts Points
1. Asymptotic Bounds (a), (b), (c) 5 + 5 + 5 = 15
2. Recurrences. (a), (b), (c) 5 + 5 + 5 = 15
3. Cutting Rod – 12
4. Insertion Sort – 18
5. Prefix Sums (a), (b) 10 + 5 = 15
Total 75




This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00


https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/

, Question 1. [ 15 Points ] Asymptotic Bounds. For each of the following statements state
whether it is True or False. You must justify each answer. Assume that all log’s are of base 2.

2
(a) [ 5 Points ] 2log n = Θ n2




(b) [ 5 Points ] n1.2 = Ω n log2 n




(c) [ 5 Points ] 22n = O (3n )

Solution Hints.


2
2
(a) We have, 2log n = 22 log n = 2log n = n2 = Θ n2



Hence, the given statement is True.

(b) We have,
   
n1.2 n0.2
limx→∞ n log2 n
= limx→∞ log2 n  
n0.2 ln n
= (ln 2)2 limx→∞ 2 {∵ log2 n = ln 2 }
ln n 
0.2n0.2−1
= (ln 2)2 limx→∞ 2 ln n {L’Hopital’s rule}
 n 
n0.2
= 0.1(ln 2)2 limx→∞
 ln n 0.2−1 
0.2n
= 0.1(ln 2)2 lim x→∞ 1 {L’Hopital’s rule}
n
= 0.02(ln 2)2 limx→∞ n0.2
= ∞≥c {where, c is any positive constant}
2
n1.2


So, = Ω n log n .
Hence, the given statement is True.
 
22n 4n 4 n




(c) We have, limx→∞ 3n = limx→∞ 3n = limx→∞ 3 = ∞.
So, 22n = ω (3n ).
Hence, the given statement is False.




1



This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00


https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/