CIS 121 — Data Structures and Algorithms
Practice Problems for Exam I February 16, 2020
1. Prove using induction that n is O(2n).
2. Prove that 2(n2) is not O(5n). Do not use any theorems about Big-Oh that you might happen to
know other than the definitions.
3. Solve the following recurrence. Give a tight bound, i.e., express your answer using the Θ notation.
Assume that T(n) = 1, when n = 1.
T (n) = T (n − 1) + 1/n 4. Consider the following code fragment
for(int i=1;i<=n;i=2*i)
for (int k = i; k >0; k = k/2)
print(‘*’);
a. Compute the number of stars printed as a function of n. You can assume that n = 2m. b. Give a Θ-bound.
5. Modify the quicksort algorithm so that its running time is O(nlogn) in the worst case. You may assume that all elements are distinct.
6. Suppose that you have a “black box” worst-case linear-time median subroutine. Give a simple, linear- time algorithm that solves the selection problem for any arbitrary order statistic, i.e., given an unsorted array A containing n elements and an integer i, in O(n) time, your algorithm should return the element in A, which is the ith smallest element in A. Your algorithm must use the black-box median-finding subroutine. You may assume that i lies within the bounds of the input array A and that n is a power of 2. Justify your answer.
February 16, 2020 Practice Problems for Exam I 2 Useful Facts and Scrap Paper Sheet
Please DO NOT hand this page in.
1. Summations:
•∞ ci= 1 ,|c|<1 i=0 1−c
•∞ ci= c ,|c|<1 i=1 1−c
•∞ ici= c ,|c|<1 i=0 (1−c)2
• Hn =n 1 =lnn+O(1) i=1 i
• logaab =b
• logaa=1
• log1=0
• log b = logx b a logx a
• (xa)b = xab
3. Simplified Master Theorem. Let a ≥ 1, b > 1 be constants and let T (n) be the recurrence
T (n) = aT n + Θ(nk ) b
defined for n ≥ 0 (we assume that n is a power of b, though this does not make a difference in asymptotic analysis). The base case, T(1) can be any constant value. Then
• n i=1
i = n(n+1) 2
i2 = n(n+1)(2n+1) 6
• • •
n i=1
n 3 n2(n+1)2 i=1i= 4
n ci=cn+1−1,c̸=1 i=0 c−1
2. Log and Exponent Rules: • lgn=log2n
• lnn=logen • aloga b = b
• logab=loga+logb • loga =loga−logb
b
• logab = bloga
Case 1: Case 2: Case 3:
if a > bk, then T(n) ∈ Θ(nlogb a).
if a = bk, then T(n) ∈ Θ(nk logb n). if a < bk, then T(n) ∈ Θ(nk).