CMPT307 21-1 Midterm Test 1 1
11:30-12:20 Feb 10 (Wed), open book, extra 10 minutes for submission. There are
100 points in this test. Submit your answers (must be typed) in pdf file to CourSys
points: 10 and 20 points deductions for answers received at (12 : 30, 12 : 40] and (12 : 40, 12 :
50], respectively; no points will be given to answers received after 12:50.
Students who receive 50% extra time accommodation from CAL (center for accessible
after 12:30 will get penalty of reducing points: 10 and 20 points deductions for answers
received at (13 : 00, 13 : 15] and (13 : 15, 13 : 30], respectively; no points will be given to
Students who receive 25% extra time accommodation from CAL are required to have
of reducing points: 10 and 20 points deductions for answers received at (12 : 45, 12 : 58] and
(12 : 58, 13 : 10], respectively; no points will be given to answers received after 13:10.
name and last (family) name, the course number and name, and examination date in the
1. 20 points
Rank the following functions by order of growth, that is, find an arrangement f1, .., f5
of functions satisfying fi = O(fj) for 1 ≤ i < j ≤ 5:
n2.05, n2 log n, (log n)50, n50, 2n.
2. 40 points
An array A[1..n] of n distinct numbers is called unimodal if for some position p with
1 ≤ p ≤ n, the value of A[i] is monotone increasing in i when i = 1, 2, .., p and the
value of A[i] is monotone decreasing in i when i = p, p + 1, .., n. A[p] is called the
peak element of A. For example, A[1..7] = [5, 7, 8, 10, 9, 6, 4] is unimodal and A[4] = 10
is the peak element. Design an algorithm in pseudo code which, given a unimodal
array A of n elements, finds the index p such that A[p] is the peak element of A in
O(log n) time (20 points). Give a proof for the correctness (15 points) and an analysis
of the running time of your algorithm (5 points). (Hint: A[p] is the peak element if
A[p− 1] < A[p] > A[p + 1].)
3. 40 points
Insertion sort (slides 10-14,18 of lec1) is a comparison based sorting algorithm. In-
sertion sort discussed in class sort an array A[1..n] of n elements by inserting each
element A[j] into subarray A[1..j − 1]. In the worst case, it uses n(n − 1)/2 compar-
isons between the elements of A: A[j] is inserted at A[1] (j − 1 comparisons) for every
j. The following approach gives an improved insertion sort which reduces the number
of comparisons between the elements of A to n2/4 + O(n) in the worst case: Assume
CMPT307 21-1 Midterm Test 1 2
we sort A into increasing order. Let A[m], A[m+ 1] be the two elements in the central
locations of A.
• Compare A[m] with A[m + 1] to have A[m..m + 1] sorted.
Compare A[m − 1] with A[m + 2], if A[m − 1] > A[m + 2] then exchange the
elements of A[m− 1] and A[m + 2] (exchange step);
insert A[m + 2] into A[m..m + 1] to have A[m..m + 2] sorted and then insert
A[m− 1] into A[m..m + 2] to have A[m− 1..m + 2] sorted.
• In general, assume A[i..j] is sorted (i ≤ m and m + 1 ≤ j).
Compare A[i− 1] with A[j + 1], if A[i− 1] > A[j + 1] then exchange the elements
of A[i− 1] and A[j + 1] (exchange steps);
insert A[j + 1] into A[i..j] to have A[i..j + 1] sorted and then insert A[i− 1] into
A[i..j + 1] to have A[i− 1..j + 1] sorted.
Repeat this step until A[1..n] is sorted.
Assume n is even (m = n/2). Implement the above approach in pseudo code to
give an improved insertion sort algorithm (20 points); prove the correctness of the
algorithm using a loop invariant (10 points); and show the number of comparisons
between elements of A to sort A is n2/4 +O(n) in the worst case (10 points) (hint for
the number of comparisons: A[i− 1] ≤ A[j + 1] after the exchange step).