xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CMPT307 21

时间：2021-03-08

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

学霸联盟

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

学霸联盟