CIS 121 — Data Structures and Algorithms Practice Exam I Solutions
Important Note: Do not distribute or share these solutions. They are strictly for the personal use of students registered in the Spring 2020 edition of CIS 121 at the University of Pennsylvania. Any violations will be referred to the Office of Student Conduct.
[30] 1.
a. For each group of functions (from non-negative integers to non-negative integers) below, rank the functions by non-decreasing order of asymptotic growth. For any group of functions g1,g2,g3, if g1 = O(g2), and g2 = O(g3), then you should write g1 < g2 < g3. Similarly, if g1 = Θ(g2) and g2 = O(g3), then you should write g1 = g2 < g3. No justification is required.
i
ii.
f1(n) = nlgn, f2(n) = lg(n!), f3(n) = (lg n)!
Solution. f1(n) = f2(n) < f3(n). In recitation we proved that lg(n!) = Θ(n lg n). Moreover, letting x = lgn, we may write f1(n) = x2x,f3(n) = x! and hence since lim x2x = lim 2x =
0,wehavef1 =f2
c ← Jaadu(X)
d ← Jaadu(Y )
e ← Compute(X, Y ) return c+d+e
Assumenisapowerof4. ThislinerunsintimeO(1)
Select algorithm from class that uses median of medians Select algorithm from class that uses median of medians
X is a list of integers in arbitrary order Y isalistofintegersinarbitraryorder
a. Let T(n) be the running time of Jaadu on a list of n distinct integers. T(n) can be written as the following recurrence, with the base case being T (1) = 1.
T (n) = aT n + f (n) b
What are the values of a, b, and f (n)? You may express f (n) using big-Oh notation. No justification is necessary.
Solution. a = 2,b = 4, and f(n) = O(n2).
|X| = |Y | = n so b = 4. The calls to Select both take O(n) time. Forming the lists X and Y are
4
also O(n). Hence since the call to Compute(X,Y) takes O(|X||Y|) = On2 = O(n2) time, we 4
have f(n) = O(n) + O(n2) = O(n2). Lastly, since we make two recursive calls to Jaadu, a = 2.
b. Solve the recurrence and give the running time of the Jaadu function using the Big-Oh notation. Justify your answer. Your score on this question will depend on the tightness of your bound.
Spring 2020 Practice Exam I Solutions 4 Solution. Application of the Case 3 in the simplified Master’s Theorem gives us O(n2).
[12] 3. You are given an array A of n distinct numbers. You are told that the sequence of numbers in the array is an increasing-decreasing sequence, i.e., there is an index i such that the sequence A[1 .. i] is increasing (i.e., A[j ] < A[j + 1], for 1 ≤ j < i) and the sequence A[i .. n] is decreasing (i.e., A[j ] > A[j + 1], fori≤j
2
know the peak belongs to {1, 2, · · · , mid}, so recurse on the the array A[i .. mid]. Otherwise recurse on the right half.
The pseudocode for this algorithm is given below:
FindPeak(A[i .. j]) if i=j then return i
k ← ⌊ i+j ⌋ 2
if A[k] > A[k + 1] then return FindPeak(A[i .. k])
else
return FindPeak(A[k + 1 .. j])
Since we perform a single comparison in O(1) time and we only recurse on half of the array, the running time of the algorithm is given by the recurrence
O(1), n = 1 T(n) = T(n/2) + O(1), n > 1
which yields a running time of O(log n) (it is the same as binary search).
[14] 4. Suppose we are given an array A[0 .. n−1] of distinct numbers. You may assume that n is positive integer that is a multiple of 6. We wish to find a number x that simultaneously satisfies two properties: First, x should be in the middle two-thirds of the array (in other words, x = A[i], for some i such that n/6 ≤ i < 5n/6). Second, after sorting the array, x should still be in the middle two-thirds. For example, given the array [3, 4, 6, 1, 5, 2], the algorithm could return either 4 or 5.
a. Prove that such a number x always exists.
Solution. There are 2n elements in the middle two-thirds of the unsorted array. There are only n
33
elements not in the middle two-thirds of the sorted array. Hence there must be at least 2n − n = n 333
elements in both the middle two-thirds of the original array and of the sorted array. Since n ≥ 6, this implies there must exist a number x that is in the middle two-thirds of both the sorted and unsorted arrays.
Spring 2020 Practice Exam I Solutions 5 b. Describe a linear-time algorithm for finding such an x. No justification of running time is necessary.
No proof of correctness is required.
Solution. We know that whatever element we choose cannot be in the set of n/6 smallest elements
or the set of n/6 largest elements. Thus, we can simply take the middle two-thirds set of the un-
sorted array and use the Select algorithm done in class to find the (lower) median element of this
sub-array. Since the sub-array has 2n elements and n is a multiple of 6, we know the median will 3
necessarily be greater than at least n − 1 elements and less than at least n elements, and thus lies 33
in the middle two-thirds of the sorted array.
Runtime: Select with median of medians runs in O(n) time.
[19] 5. We are given an array A[0 .. n − 1], where n > 1 and all array elements are non-negative integers. Our goal is to find the minimum value of A[i]−A[j]2, where the indices i,j range over all values such that 0 ≤ i < j < n.
a. Fill in the blanks below to produce an efficient algorithm for the problem.
Solution.
MinDiff(A[0..n − 1]) if n≤1then
return ∞ k ← ⌊n⌋
2
x ← MinDiff(A[0..k − 1])
y ← MinDiff(A[k..n − 1])
z ← min{A[0], A[1], · · · , A[k − 1]} − max{A[k]2, A[k + 1]2, · · · , A[n − 1]2} return min{x, y, z}
b. Write a recurrence relation for the running time of your algorithm. No justification is required.
Solution.
O(1), n = 2 T(n) = 2T(n/2) + O(n), n > 2
c. What is the running time of your algorithm? Use Θ(·) notation. No justification is required. Solution. Notice the recurrence is a familiar one: it is exactly the same recurrence as Mergesort.
Hence the running time is Θ(n log n).
d. Describe a O(n) time algorithm for the problem. No proof of correctness or justification of running time is necessary.
MinDiff(A[0 .. n − 1]) if n≤1then
return ∞
k ← ⌊n⌋ 2
Spring 2020 Practice Exam I Solutions 6
(minl , maxl , dif fl ) ← MinDiff(A[0 .. k − 1]) (minr , maxr , dif fr ) ← MinDiff(A[k .. n − 1]) minlr = min{minl,minr}
maxlr = max{maxl,maxr}
difflr ← minl − max2r
return (minlr,maxlr,min{diffl,diffr,difflr})
[15] 6. Consider the Gale-Shapley algorithm for the stable marriage problem in which the men propose. Prove that at least one of the men or women must be matched to someone who is ranked in the top half of their preference list. You may assume that there are n men and n women and that n is even.
Solution. Assume that no man is matched with a woman in the top half of his preference list. We will prove that then there is a woman who is matched to some man who is in the top half of her preference list. Observe that each of the n men must have been rejected by at least n/2 women. Thus the total number of proposals is strictly greater than n2/2. By the pigeon hole principle, there must be a woman, say w, who must have received more than n/2 proposals. This means that at least one man m in the top half of her preference list must have proposed her. When m proposes to w, w either gets engaged to m or rejects m in favor of a man m′ whom she prefers to m. Since a woman’s partners can only get better, the man with whom finally w is matched with must be ranked higher than m and hence in the top half of her preference list.