Description
All problem/exercise numbers are for the third edition of CLRS text book
1. Prove the Transpose Symmetry property, i.e. f(n) = O(g(n)) if and only if g(n) = Ξ©(f(n))
2. Problem 3-1 in CLRS Text book.
3. Problem 3-2 in CLRS Text book.
4. You have 5 algorithms, A1 took π(π) steps, A2 took Ξ(π log π ) steps, and A3 took Ξ©(π) steps, A4 took
π(π steps, A5 took steps. You had been given the exact running time of each algorithm, but 3
) π(π
2
)
unfortunately you lost the record. In your messy desk you found the following formulas:
(a) 3ππππ
2
π + πππ
2
πππ
2
π
(b) 3(2
2πππ
2
π
) + 5π + 1234567
(c)
2
πππ
4
π
3 + π + 9
(d) (πππ
2
π)
2
+ 5
(e) 3π!
(f) 2
3πππ
2
π
(g) 2
2πππ
2
π
For each algorithm write down all the possible formulas that could be associated with it.
5. For the following algorithm: Show what is printed by the following algorithm when called with
MAXIMUM(A, 1, 5) where A = [10, 8, 6, 4, 2]? Where the function PRINT simple prints its arguments in
some appropriate manner.