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
https://coursys.sfu.ca/2021-cmpt-307-d1/. You are required to have your answers
received at CourSys by 12:30. Answers received after 12:30 will get penalty of reducing
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
learning) are required to have your answers received at CourSys by 13:00; answers received
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
answers received after 13:30.
Students who receive 25% extra time accommodation from CAL are required to have
your answers received at CourSys by 12:45; answers received after 12:45 will get penalty
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.
The work you submitted must be your own. Include your student number, your first
name and last (family) name, the course number and name, and examination date in the
top of your answers.
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).



























































学霸联盟