Description
Suggested reading: Chapter 0.3 and Chapter 2 of the book. Section 2.2 contains the Master Theorem covered in class.
Practice problems (don’t turn in)
Problem (Big-O order, part (a) and (b) are independent)
-
For the following list of functions, cluster them into groups of functions of the same order (i.e., f and g are in the same group if and only if f = O(g) AND g = O(f)), and then rank the groups in increasing order. You do not have to justify your answer.
log2(n) log(n2)
pn n
2n + 5
n log(n) + 2019
n2:5
2n
n log2(n)
-
The geometric series of ratio a 6= 1 is the sum
S(n) = 1 + a + a2 + + an:
Prove that
an+1 1
S(n) = a 1 :
Deduce that S(n) = O(an) for a > 1 and S(n) = O(1) for a < 1. (Hint: you may prove the equality by induction or just directly by checking that both sides are equal after multiplication by a 1. )
Problem (Problems from the book) [DPV], Chapter 2, exercises:
2.4 (Choosing between three algorithms).
2.5 (Solving recurrences).
2.19 (k-way merge, we discussed this problem in class).
Problem (Order Statistics in a union of two lists) Describe an algorithm that takes as input two sorted lists of length n and m and an integer k and outputs the kth smallest element in their union. You can assume both lists contain integers and all entries are di erent.
See next page for those problems you need to submit.
2
