PennID (e.g., 12345678):
Practice Midterm Exam I Spring 2020
Initials:
CIS 121 — Data Structures and Algorithms
Advice: This was an actual midterm exam given during a previous iteration of CIS 121. Try to get an 80 minute chunk of time and take the practice test as if it were a real test. This will give you practice at thinking on your feet and concisely stating your solutions. However, you shouldn’t ignore the practice exam after that. Once you’re done, start thinking about variations of the practice exam problems. If we dropped one of the guarantees, how would that change your algorithm’s runtime? How could you vary the problem to make it significantly different? Think about these variations and how you might solve them, as it will give you additional practice.
Solutions: Solutions will be posted after the review session. Rubrics will not be released, but statis- tics have been posted below for your reference.
Exam Statistics: Max: 97, Mean: 54.3, Median: 54, Std Dev: 16.9 Instructions:
• Do not open the exam booklet until you are told to begin. You may write your PennID, initials, and circle your recitation on the cover sheet now. Do NOT write your name.
• This exam is closed-book and closed-notes. Calculators and other external resources are prohibited.
• There are six (6) questions totaling 100 points, and 16 pages.
• The last page contains reference equations. Feel free to tear it off.
• You may use any algorithm, presented in the textbook or done in the class or homeworks, as a building block for your solutions.
• Pseudocode is acceptable, but please try to explain your algorithms in plain English as well.
• All answers must be written on the exam. Write clearly and neatly. If there is any doubt, draw a
box around your answer to clearly indicate what we should grade.
• If you find yourself spending too long on a problem, skip it and move on to the next one. Be certain to write your name on all materials you turn in.
Sign this statement after you have completed the examination. Your exam will not be graded without your signature.
I certify that my responses in this examination are solely the product of my own work and that I have fully abided by the University of Pennsylvania’s academic integrity policy while taking this exam.
Signature:
Spring 2020 CIS 121 – Practice Midterm Exam I 2 [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 f1(n) = nlgn, f2(n) = lg(n!), f3(n) = (lg n)!
ii f1(n) = nlg n, f2(n) = 2n,
f3(n) = 3lg n
Spring 2020 CIS 121 – Practice Midterm Exam I 3 b. Suppose you have access to algorithm X that does the following.
Input: an array A of length n, containing integers.
Output: with probability 1/2, a sorted version of A. With probability 1/2, it outputs an array which may not be sorted.
Design a randomized algorithm which uses algorithm X and sorts an array of integers in O(n) time and which succeeds with probability at least 1 − 2−10. You may assume that the running time of X is O(1). Briefly justify the correctness of your algorithm, i.e., argue why your algorithm outputs a sorted array with the success probability specified above. No need to justify the running time.
Spring 2020 CIS 121 – Practice Midterm Exam I 4
c. For the code fragment given below, give a bound of the form Θ(f(n)) on its running time on an input of size n. Justify your answer.
sum = 0
for(i←1; i
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.
Spring 2020 CIS 121 – Practice Midterm Exam I 7
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 CIS 121 – Practice Midterm Exam I 8
[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
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).
Scratch Paper (Work done on this page will not be graded – feel free to use both sides)