CMPT307 21-1 Assignment 2 Answers 1
Due 16:00 Feb 8 (Monday). There are 100 points in this assignment.
Submit your answers (must be typed) in pdf file to CourSys
https://coursys.sfu.ca/2021sp-cmpt-307-d1/.
The work you submitted must be your own. Any collaboration and consulting outside
resources must be explicitly mentioned on your submission.
1. 15 points (P 5-2 of text book)
Searching an unsorted array problem: Given an array of n elements which are not sorted
and a value x, find the index i such that A[i] = x. A randomized algorithm Random-
Search for the problem is as follows: select a number i from {1, .., n} independently
and uniformly; if A[i] = x then return i and terminate; otherwise repeat the above
process until the i with A[i] = x is found or A[i] 6= x for every i = 1, .., n is concluded.
(a) Write a pseudo-code for Random-Search.
(b) Assume there is exactly one i such that A[i] = x. What is the expected number of
checks of A[i] = x Random-Search performs before terminates.
Ans: (a) Assume that A has n elements. An array P is used to track the elements
which have been seen, and add to a counter c each time a new element is checked. Once
this counter reaches n, it is concluded that every element has been checked. Let RI(A)
be the function that returns a random index of A. Below are two possible random
search algorithms (either one is OK). (5 points)
Random-Search1
Initialize array P of size n containing all zeros;
c = 0;
while c < n do
i = RI(A);
if A[i] = x then return i;
if P [i] = 0 then {P [i] = 1; c = c + 1};
return A does not contain x.
Random-Search2
Initialize array P of size n containing all zeros;
c = 0;
while c < n do
i = RI(A);
if P [i] = 0 then
if A[i] = x then return i else {P [i] = 1; c = c + 1};
return A does not contain x.
(b) 10 points. Let N be the random variable for the number of checks required and pk
be the probability that k checkes of A[i] = x are performed by the algorithm. Then
for Random-Search1, pk = (
1
n
)(n−1
n
)k−1 and
E[N ] =
∑
k≥1
kpk =
∑
k≥1
k(
n− 1
n
)k−1(
1
n
) =
1
n
× 1
(1− n−1
n
)2
= n.
CMPT307 21-1 Assignment 2 Answers 2
(Since krk−1 is the derivative of rk,
∑
k≥1 krk−1 =
d
dr
(
∑
k≥0 rk) =
d
dr
( 1
1−r ) =
1
(1−r)2 for
0 < r < 1.)
For Random-Search2, p1 = (
1
n
),
pk = (
1
n− k + 1)Π
k
j=2(
n− j + 1
n− j + 2) = (
1
n
).
for 2 ≤ k ≤ n, and
E[N ] =
n∑
k=1
kpk = (
n∑
k=1
k)/n = (n + 1)/2.
2. 10 points (Ex 6.5-3 of text book)
Write pseudo-code for procedures Min-Heapify, Heap-Minimum, Heap-Extract-Min,
Heap-Decrease-Key, and Min-Heap-Insert that implement a min-priority queue with a
min-heap.
Ans: (2 points for each procedure)
Min-Heapify(A, i)
l =Left(i); r =Right(i);
if l ≤ s(A) and A[l] < A[i] then min = l else min = i;
if r ≤ s(A) and A[r] < A[min] then min = r;
if min 6= i then exchange A[i] with A[min] and Max-Heapify(A,min);
Heap-minimum(A)
Return A[1]
Min-Heap-Extract(A)
if s(A) < 1 then output ”error, heap underflow” and stop;
min = A[1]; A[1] = A[s(A)]; s(A) = s(A)− 1;
Min-Heapify(A, 1);
return min
Heap-Decrease-Key(A, i, key)
if key > A[i] then output ”error, new key > current key” and stop;
A[i] = key;
while i > 1 and A[Parent(i)] > A[i] do
exchange A[i] with A[Parent(i)]; i = Parent(i);
Min-Heap-Insert(A, key)
s(A) = s(A) + 1; A[s(A)] =∞;
Heap-Decrease-Key(A, s(A), key);
CMPT307 21-1 Assignment 2 Answers 3
3. 20 points (P 6-2 of text book)
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes
have d ≥ 2 children instead of 2 children.
(a) How would you represent a d-ary heap in an array A[1..n]?
(b) What is the height of a d-ary heap of n elements in terms of n and d?
(c) Give an efficient pseudo code of MAX-HEAPPIFY and pseudo code of EXTRACT-
MAX in a d-ary max-heap. Analyze the running times in terms of d and n.
(d) Give an efficient pseudo code of INSERT in a d-ary max-heap. Analyze its running
time in terms of d and n.
(e) Give an efficient pseudo code of INCREASE-KEY(A, i, k), which flags an error if
k < A[i], but otherwise sets A[i] = k and then updates the d-ary max-heap structure
appropriately. Analyze its running time in terms of d and n.
Ans:
(a) It suffices to show how to access parent and child nodes. In a d-ary array of A[1..n],
PARENT(i) = bi + d− 2/dc, and CHILD(k, i) = d(i− 1) + 1 + k, where CHILD(k, i)
gives the kth child of the node indexed by i. (2 points)
(b) The height of a d-ary heap of n elements is dlogd ne. (2 points)
(c) The following is a pseudo code of HEAP-EXTRACT-MAX for a d-ary heap. A
pseudo code of DMAX-HEAPIFY is also given, which is the analog of MAX-HEAPIFY
for d-ary heap. HEAP-EXTRACT-MAX consists of constant time operations, followed
by a call to DMAX-HEAPIFY. The number of times this recursively calls itself is
bounded by the height of the d-ary heap, so the running time is O(d logd n). (2 points)
Note that the CHILD function is meant to be the one described in part (a).
Let A.size be the size of heap A.
HEAP-EXTRACT-MAX(A) for a d-ary heap
if A.size < 1 then error heap underflow;
max = A[1]; A[1] = A[A.size]; A.size = A.size− 1;
DMAX-HEAPIFY(A, 1)
(3 points)
DMAX-HEAPIFY(A, i)
largest = i;
for k = 1 to d do
if CHILD(k, i) ≤ A.size and A[CHILD(k, i)] > A[i] then
if A[CHILD(k, i)] > largest then largest =CHILD(k, i);
end for
if largest 6= i then {exchange A[i] with A[largest]; DMAX-HEAPIFY(A, largest)}
(3 points)
CMPT307 21-1 Assignment 2 Answers 4
(d) The runtime of this pseudo code of INSERT is O(logd n) since the while loop runs
at most as many times as the height of the d-ary array. (2 points) Note that when we
call PARENT, we mean it as defined in part (a).
INSERT(A, key)
A.size = A.size + 1; A[A.size] = key; i = A.size;
while i > 1 and A[PARENT(i)] < A[i] do
exchange A[i] with A[PARENT(i)]; i =PARENT(i);
end while
(2 points)
(e) This is identical to the pseudo code of HEAP-INCREASE-KEY for 2-ary heaps,
but with the PARENT function interpreted as in part (a). The runtime is O(logd n)
since the while loop runs at most as many times as the height of the d-ary array. (2
points)
INCREASE-KEY(A, i, key)
if key < A[i] then error new key is smaller than current key ;
A[i] = key;
while i > 1 and A[PARENT(i)] < A[i] do
exchange A[i] with A[PARENT(i)]; i =PARENT(i);
end while
(2 points)
4. 15 points (Ex 7.4-5 of text book)
One variant of (randomized) quicksort algorithm is that for a constant k > 1, the
algorithm does not sort any subarray of size smaller than k and returns with the
subarray unsorted, and after the top-level call to quick-sort returns, run insertion sort
on the entire array to complete the sorting. Prove that the average running time of
the variant of randomized quicksort is O(nk+n log(n/k)). In theory, how should k be
selected?
Implement the algorithm Randomized-Quicksort discussed in class and the variant of
Randomized-Quicksort above. Report the running times of the two algorithms for sort-
ing n numbers with n = 2i× 1000, i = 0, 1, 2, 3, 4, 5. Give your suggestion on selecting
k in practice (e.g., the k achieves the best running time in your implementation).
Ans: If we stop call quicksort when the problem size becomes ≤ k, then there are
log(n/k) levels of recursive calls, since, as in the original analysis of randomized quick
sort, we expect there are log n levels to the recursion tree. After the quicksort on the
entire array, each element is within k of its final position. This means that an insertion
sort will take the shifting of at most k elements for every element that needed to change
position. This gets us the running time of O(nk + n log(n/k)). (4 points)
In theory, a k which minimizes O(nk + n log(n/k)) should be selected. Taking a
derivative with respect to k, we want it to be evaluating to zero. So, n(cn/k) = 0,
c > 0 is a constant, implying k = c. (4 points)
CMPT307 21-1 Assignment 2 Answers 5
(7 points for reported running time and suggested k).
5. 10 points (Ex 8.3-2 of text book)
Which of the following sorting algorithms are stable: insertion sort, merge sort, heap-
sort, and quicksort? Give a simple scheme that makes any sorting algorithm stable.
How much additional time and space does your scheme entail?
Ans: Insertion sort and merge sort are stable. Heapsort and quicksort are not (4
points).
To make any sorting algorithm stable we can preprocess, replacing each element of an
array with an ordered pair. The first entry will be the value of the element, and the
second value will be the index of the element. For example, the array [2, 1, 1, 3, 4, 4, 4]
becomes [(2, 1), (1, 2), (1, 3), (3, 4), (4, 5), (4, 6), (4, 7)]. We now interpret (i, j) < (k,m)
if i < k or i = k and j < m. Under this definition of less-than, the algorithm is
guaranteed to be stable because each of our new elements is distinct and the index
comparison ensures that if a repeat element appeared later in the original array, it
must appear later in the sorted array. This doubles the space requirement, but the
running time will be asymptotically unchanged (6 points).
6. 15 points (P 8-2 of text book)
Given an array A of n elements, each element is 0 or 1, an algorithm for sorting A into
increasing order might possess some subset of the following three desirable properties:
(1) The algorithm runs in O(n) time.
(2) The algorithm is stable.
(3) The algorithm sorts in place, using no more than a constant amount of storage
space in addition to A.
(a) Give an algorithm that satisfies (1) and (2) above.
(b) Give an algorithm that satisfies (1) and (3) above.
(c) Give an algorithm that satisfies (2) and (3) above.
Ans: (a) Algorithm O(n) time and Stable(A)
Create a new array C; index = 1;
for i = 1 to n do
if A[i] = 0 then {C[index] = A[i]; index = index + 1}
end for
for i = 1 to n do
if A[i] = 1 then {C[index] = A[i]; index = index + 1}
end for
This algorithm first selects all the elements with key 0 and puts them in the new array
C in the order in which they appeared in A, then selects all the elements with key 1
CMPT307 21-1 Assignment 2 Answers 6
and puts them in C in the order in which they appeared in A. Thus, it is stable. Since
it only makes two passes through the array, it is O(n). (5 points)
(b) The algorithm maintains the 0′s seen so far at the start of the array. Each time an
element with key 0 is encountered, the algorithm swaps it with the position following
the last 0 already seen. This is in-place and O(n), but not stable. (5 points)
(c) Insertion sort. (5 points)
7. 15 points (P 9-2 of text book)
For n elements x1, ..., xn with positive weights w1, .., wn such that
∑n
i=1wi = 1, we
say xi < xk if wi < wk or wi = wk and i < k. The weighted (lower) median is the
element xk satisfying
∑
xi1
2
and
∑
xi>xk wi ≤ 12 . Example: for x1, .., x7 with
w1 = 0.1, w2 = 0.35, w3 = 0.05, w4 = 0.1, w5 = 0.15, w6 = 0.05, w7 = 0.2, the median of
x1, .., x7 is x4 but the weighted median is x7.
(a) Prove that the median of x1, .., xn is the weighted median of x1, .., xn with weight
wi = 1/n for 1 ≤ i ≤ n.
(b) Show how to compute the weighted median of n elements in O(n log n) worst-case
time using sorting.
(c) Show how to compute the weighted median in Θ(n) worst-case time using a linear-
time median algorithm such as SELECT from Section 9.3.
Ans: (a) Let mk be the number of xi smaller than xk. When weights of 1/n are
assigned to each xi, we have
∑
xi∑
xi>xk wi = (n−mk− 1)/2. Only
when mk = dn/2e − 1, mk/n < 1/2 and (n −mk − 1)/2 ≤ 1/2. Therefore, xmk with
mk = dn/2e − 1 is the median since it has equal numbers of x′is which are larger and
smaller than it. (5 points)
(b) First use mergesort to sort the x′is by weight in O(n log n) time. Let Si be the sum
of the weights of the first i elements of this sorted array A[1..n] and note that it is O(1)
to update Si. Compute S1, S2, .. until you reach j such that Sj−1 < 1/2 and Sj ≥ 1/2.
The weighted median is xk in A[j]. (5 points)
(c) We modify SELECT to do this in linear time. Let x be the median of medians.
Compute
∑
xi∑
xi>xwi and check if either of these is larger than 1/2. If not,
stop. If so, recurse on the collection of smaller or larger elements known to contain the
weighted median. This doesnt change the runtime, so it is Θ(n). (5 points)
































































































































































































































































1
2
and
∑
xi>xk wi ≤ 12 . Example: for x1, .., x7 with
w1 = 0.1, w2 = 0.35, w3 = 0.05, w4 = 0.1, w5 = 0.15, w6 = 0.05, w7 = 0.2, the median of
x1, .., x7 is x4 but the weighted median is x7.
(a) Prove that the median of x1, .., xn is the weighted median of x1, .., xn with weight
wi = 1/n for 1 ≤ i ≤ n.
(b) Show how to compute the weighted median of n elements in O(n log n) worst-case
time using sorting.
(c) Show how to compute the weighted median in Θ(n) worst-case time using a linear-
time median algorithm such as SELECT from Section 9.3.
Ans: (a) Let mk be the number of xi smaller than xk. When weights of 1/n are
assigned to each xi, we have
∑
xi∑
xi>xk wi = (n−mk− 1)/2. Only
when mk = dn/2e − 1, mk/n < 1/2 and (n −mk − 1)/2 ≤ 1/2. Therefore, xmk with
mk = dn/2e − 1 is the median since it has equal numbers of x′is which are larger and
smaller than it. (5 points)
(b) First use mergesort to sort the x′is by weight in O(n log n) time. Let Si be the sum
of the weights of the first i elements of this sorted array A[1..n] and note that it is O(1)
to update Si. Compute S1, S2, .. until you reach j such that Sj−1 < 1/2 and Sj ≥ 1/2.
The weighted median is xk in A[j]. (5 points)
(c) We modify SELECT to do this in linear time. Let x be the median of medians.
Compute
∑
xi∑
xi>xwi and check if either of these is larger than 1/2. If not,
stop. If so, recurse on the collection of smaller or larger elements known to contain the
weighted median. This doesnt change the runtime, so it is Θ(n). (5 points)

学霸联盟