CMPUT204: Introduction to Algorithms
Final Exam
Instructions.
• This exam has 5 problems, each is worth 25pts.
• You may answer all 5 problems, but your grade will be composed of the best 4 answers.
• Closed books.
• You may use a scientific calculator.
• Collaborations of any kind...
CMPUT204: Introduction to Algorithms
Final Exam
Instructions.
• This exam has 5 problems, each is worth 25pts.
• You may answer all 5 problems, but your grade will be composed of the best 4 answers.
• Closed books.
• You may use a scientific calculator.
• Collaborations of any kind are strictly forbidden.
• Note: All logarithms are in base 2 unless specified otherwise.
n
P 1
• You can use the fact that H(n) = i = ln n + O(1) without proving it.
i=1
1
, Problem 1. (25 pts)
(i) (15 pts) Below is the description of the MergeSort algorithm for sorting n pairwise-comparable elements
given in an array A.
1. Prove the correctness of the MergeSort algorithm.
2. Derive the suitable recurrence relation representing the runtime of MergeSort.
3. Solve the recurrence relation to derive its runtime.
procedure Mergesort(A, l, h) ** Sorts the subarray A[l, ..., h]
if (l < h) then
m ← b l+h
2 c
MergeSort(A, l, m)
MergeSort(A, m + 1, h)
Merge(A, l, m, h)
You may assume that you are given a function Merge(A, p, q, r) whose input is an array of elements
A such that A[p, ..., q] is sorted and A[q + 1, ...r] is sorted; and that permutes the element of A so that
when Merge halts the elements in A[p, ..., r] are all sorted. This Merge function is given to you — so
you can use it, the fact that it makes at most p − r Key-Comparisons, and the fact that its runtime
is Θ(r − p) without specifying how it work, without proving its correctness and without analyzing its
runtime.
Answer.
Correctness. We prove correctness of MergeSort using full/complete induction on n, the number of
elements in the array, where n = h − l + 1.
In the base cases the array is either empty or contains a single element. Here MergeSort does nothing
as the array is ordered to begin with.
Fix n ≥ 2. Assuming MergeSort is correct for any array of any size < n, we argue MergeSort is correct
for any array of size n.
First, we claim that m < h and that m + 1 > l. This is true since if n ≥ 2 we must have l < h and so
m = b h+l
2 c≤
h+l
2 ≤ h+h
2 =h
and similarly
m + 1 = b h+l h+l
2 c+1≥d 2 e≥
h+l
2 ≥ l+l
2 =l
Now, the fact that m < h implies that m−l +1 < h−l +1 = n so the first recursive call in MergeSort is
over an array with < n elements. Similarly, the fact that m+1 > l implies that h−(m+1)+1 < h−l+1 = n,
so the second recursive call in MergeSort is also over an array with < n elements. By the IH, both calls
results in a sorted subarray.
Hence, when we invoke Merge(), both subarrays A[l, m] and A[m + 1, h] are sorted. By the correctness
of Merge(), it returns A fully sorted. The induction step is now complete.
Runtime. Clearly, for inputs of size ≤ 1 or algorithm’s runtime is some constant (checks that l ≮ h and
aborts). Hence, T (1) = O(1). For a general size input, we have that one subarray we recurse on is of size
b n2 c and the other subarray we recurse on is of size d n2 e, and then we invoke Merge() which runs in time
O(n). This gives a recurrence relation of
T (n) = T (b n2 c) + T (d n2 e) + Θ(n)
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Abbyy01. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.49. You're not tied to anything after your purchase.
