CMPSC 465 Data Structures & Algorithms
Spring 2021 Paul Medvedev and Chunhao Wang Midterm 1
Complete by: March 2nd, 2:20 pm
Instructions:
• Please log into the regular lecture Zoom meeting.
• If you have a question during the exam, you may ask the Instructor privately via Zoom chat.
• Instructor will announce any major corrections vocally over Zoom.
• All clarifications and corrections will be placed in https://docs.google.com/document/ d/1k63Ah5Ay4e-y6OGPAQc0Po6OFnA02V82mgq1mhzcPkA/edit?usp=sharing.
• Write your solutions by hand. Typed solutions will not be accepted. You may handwrite on a tablet as well.
• At2:20pm,youmustputyourpensdown.Youhaveuntil2:30touploadyoursolutionstoGradescope.
• You must use a scanning app and not just take pictures.
• You must use the template solution sheet provided on Gradescope.
1. (10 pts.) Loop invariant
Consider the following algorithm to find the maximum number in an array. The input is an array of n integers, A[1..n].
Algorithm 1: FIND-MAX(A[1..n])
x←A[1]
for k = 2 to n do
x ← max(x, A[k]) end
return x
Use the loop invariant technique to prove that Find-Max(A) returns the maximum value in A.
2. (10 pts.) Divide-and-conquer
Let A[1..n] be an array. It has n elements, and n ≥ 3. We also know something about the array: the first element is smaller than the second element, and the last element is smaller than the second to last element. A location x is said to be uphigh if A[x] ≥ A[x − 1] and A[x] ≥ A[x + 1]. For example, there are six uphighs in the following array. The uphighs are in boldface.
5,6,6,2,3,7,5,4,8,3,3,4,10,6
CMPSC 465, Spring 2021, Midterm 1
1
Observe that, given what we know about the first and last element, our array must always have at least one uphigh (think about why this is). The task is to find the location of an uphigh. If there are multiple uphighs, we only need to find the location of one.
(a) Fill in the missing code lines in the code below so that it works to find the location of an uphigh in O(logn) time.
Algorithm 2: FINDUPHIGH(A[1..n], s, e)
Result: Returnsthelocationofanuphighinthesub-arrayA[s..e].Tofindthelocationofanuphighin
the whole array, you would call FINDUPHIGH(A,1,n). mid ← ⌈ s+e ⌉
y ← A[mid] z←A[mid+1]
MISSING CODE LINES
(b) Give the intuition behind why your algorithm is correct.
2 x←A[mid−1]
CMPSC 465, Spring 2021, Midterm 1 2