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
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
