Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-1
Chapter 8
Divide-and-Conquer
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-2
Lecture Notes
Overview
In Chapter 8 we discuss the divide-and-conquer strategy and apply it to solve some important
problems such as polynomial, (large) integer and matrix multiplication (Strassen’s algorithm),
and selecting the kth smallest element in a list. We also discuss divide-and-conquer solutions to
two classical problems in computational geometry, the closest-pair problem and the convex
hull problem.
Chapter Objectives
After completing the chapter the student will know:
• The divide-and-conquer paradigm
• That recurrence relations usually naturally arise for the complexities of divide-and-
conquer algorithms, since, for example, the worst case input must involve solving worst
case subproblems
Instructor Notes
The instructor may wish to point out that more efficient algorithms exist for polynomial and
integer multiplication using the Fast Fourier Transform which is the topic of Chapter 22. In
fact, the instructor may even want to discuss the Fast Fourier Transform now, since it is such an
important divide-and-conquer algorithm. Also, the instructor may wish to conclude the
discussion on Strassen’s matrix multiplication algorithm by mentioning the discovery (as
described in the closing remarks) of more efficient, but less practical algorithms for matrix
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-3
Solutions to Selected Exercises
Section 8.1 The Divide-and-Conquer Paradigm
8.1
procedure MaxDivideAndConquer(L[low:high],Max) recursive
Input: L[low:high] (an array of list elements)
{initially called with low = 0 and high = n – 1}
Output: Max (maximum value in L[low,high])
endif
endif
end MaxDivideAndConquer
If W(n) denotes the number of list comparisons performed by MaxDivideAndConquer for a list
of size n, for n = 2k we have
8.2 The following algorithm is a revised version of the solution to problem 4 given in Hour
Test 2. The revision amounts to solving the problem nonrecursively for two element lists,
and actually results in an optimal algorithm.
procedure MaxMinDivideAndConquer(L[low,high],Max,Min) recursive
Input: L[low:high] (an array of list elements)
{initially called with low = 0, and high = n – 1}
Max ← L[high]
Min ← L[low]
endif
else
mid ← (low + high)/2
Min ← Min2
endif
endif
endif
end MaxMinDivideAndConquer
2)2/(2)( += nWnW
2222 22)2/(22)22/(2(2 ++=++= nWnW
.
=
121 2...22)2(2 −− ++++ kk W
=
22/322/ −=−+ nnn
.
It follows from results in Chapter 10 that MaxMinDivideAndConquer exhibits optimal worst-
case behavior.
8.3 The solution we give is based on the following definition. Define a list element
x L[0:n – 1] to be unmatched of order m 0 if we can delete m occurrences of x from the
list and the remaining elements (if any) can matched into pairs yi,yj so that yiyj. Note that
an element x can be unmatched of order m for more than one value of m. Note also that if a
list has a majority element, then it must be the only unmatched element (of any order) in the
mid ← (low + high)/2
Unmatched(L[low,mid], x1, m1)
Unmatched(L[mid + 1, high], x2, m2)
if x1 = x2 then
x ← x1
endif
end Unmatched
The following function then returns the majority element in L[0:n – 1] if one exists.
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-6
function Majority(L[0:n – 1])
or -1 if x is not a majority element
Ct ← 0
i ← 0
while L[i] x do
i ← i + 1
2. The first divide-and-conquer algorithm that might come to mind to find a majority
2) both sublists contain a common majority element,
3) each sublist contains a different majority element.
In case 1) we conclude that there is no majority element in L[0:n – 1]. In case 2), the
8.4 We will use insertionsort as the threshold sort (bubblesort could be used in place of
insertionsort), that is, in place of a recursive call to quicksort, insertionsort will be called to
sort sublists of size less than or equal to some threshold constant value. A good choice of the
threshold constant, which we denote by THRESHOLD, is a value between 8 and 16. Using a
threshold improves the performance of quicksort because insertionsort outperforms Quicksort
InsertionSort(L[0:n – 1])
endif
end Quicksort
An alterative solution is to do nothing once the bootstrap condition is reached, resulting in an
output list that is close to being sorted. After this near sort is complete insertionsort is called to
QuickNearSort(L[0:n – 1], position + 1, high)
else
end QuickNearSort
InsertionSort(L[0: n – 1])
Note that the operations performed by InsertionSort are exactly the same in both versions; that
8.5
procedure DirectPolyMult(P(x), Q(x), R(x))
Input: P(x) = am – 1xm – 1 + . . . + a1x + a0 and Q(x) = bn – 1xn – 1 + . . . + b1x + b0 (polynomials)
Output: R(x) = cm+n – 2 x m+n – 2+ . . . + c1x + c0 (product polynomial P(x) Q(x))
for k ← 0 to m + n – 2
8.6 a)
procedure DirectPolyMult(a[0:m – 1], b[0:n – 1], c[0:m+ n – 2])
Input: a[0:m – 1], b[0:n – 1] (coefficient arrays of two polynomials)
Output: c[0:m + n – 2] (coefficient array of product polynomial)
c[k] ← 0
ListNode = record
Info: data type of coefficients
Next: →ListNode
Previous: →ListNode
end ListNode
HeadR ← AllocateNewNode //allocate a new node and assign HeadR to point to it
HeadR→Previous ← null
CurrentR ← HeadR
while Done = .false. do
Sum ← 0
Done ← .true.
else
CurrentR→Next ← AllocateNewNode
CurrentR ← CurrentR→Next
if BeginQ→Next ≠ null then
8.8 Suppose P(x) is a polynomial with coefficient array [a0,a1,...,an-1] . Then xiP(x) is a
polynomial with coefficient array [b0,b1,...,bn-1+i] , where bj=0, 0ji-1 , and
8.9 The number of multiplications performed by the algorithm based on (13.3.2) satisfies the
recurrence
T(n) = 4T(n/2), init. cond. T(1) = 1.
Unwinding this recurrence yields T(n) (n2) .
8.11 a)
procedure AddInt(a[0:m – 1], NumDigitsA, b[0:m – 1], NumDigitsB, c[0:m – 1],
NumDigitsC)
Input: a[0:m – 1], b[0:m – 1] (arrays implementing two integers)
NumDigitsA, NumDigitsB (positive integers equal to number of digits of a
8.13
m1 + m4 – m5 + m7 = (a00 + a11) (b00 + b11) + a11 (b10 – b00) – (a00 + a01) b11
+ (a01 – a11) (b10 + b11)
= a00b00 + a00b11 + a11b00 + a11b11 + a11b10 – a11b00 – a00b11 – a01b11
8.14
m2 + m3 = a00b00 + a01b10
m1 + m2 + m5 + m6 = (a10 + a11 – a00) (b11 – b01 + b00) + a00b00 + (a10 + a11) (b01 – b00)
+ (a01 – a10 + a00 – a11) b11
8.15 15 additions/subtractions (and 7 multiplications) are as follows:
s1 = a10 + a11, s2 = s1 – a00, s3 = b11 – b01, s4 = s3 + b00
m1 = s2s4
m2 = a00b00
+−
5575
msms
8.16 In the following pseudocode for the algorithm StrassenMatMult, we use the shorthand
notation for submatrices used in Section 13.5. For example, if A[0:n – 1, 0:n – 1] is an nn
matrix, then A11 denotes the submatrix of size n/2n/2 in the upper left quadrant.
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-13
procedure StrassenMatMult(n,A,B,C)
8.17
=++= 14
25
35
77
))((110011001BBAAM
=+= 10
20
42
38
)( 0011102BAAM
−−
−
=−= 14
14
03
02
)( 1101003BBAM
−
=−= 06
23
32
75
)( 0010114BBAM
=+= 04
05
43
13
)( 1101005BAAM
−
−
=+−= 00
31
13
41
))((010000106BBAAM
−
−−
=+−= 110
08
12
64
))((111011017BBAAM
Computing matrix product
=14
25
35
77
1
M
60)15)(37())((110011001=++=++= bbaam
405)35()( 0011102=+=+= baam
7)1(7)( 1101003==−= bbam
3)54(3)( 0010114−=−=−= bbam
141)77()( 1101005=+=+= baam
14)25)(75())((010000106−=+−=+−= bbaam
20)14)(37())((111011017=+−=+−= bbaam
−+−+−+
++−−+
=
+−++
++−+
=)14(40760)3(40
1472014)3(60
623142
537541
1mmmmmm
mmmmmm
M
=1337
2163
Performing similar calculations for M2, …, M7 we obtain:
=80
190
2
M
,
−
−
=312
28
3
M
,
−
−
=424
1057
4
M
,
=031
019
5
M
,
−−
=93
31
6
M
−
−−
=16
692
7
M
−
=
−−+−−−−+
+−++−−−+
++−+−−−+
++−−−−−+
=
+−++
++−+
=
122424
756957
3191024
21159
9831330123748240
319221108631019570
03311214136312437
021986102192195763
623142
537541
MMMMMM
MMMMMM
AB
Section 8.5 Selecting the kth Smallest Value in a List
8.18 a) The algorithm Select calls Partition exactly one more time than it calls itself
recursively. Each recursive call narrows the list by at least one. If n-1 recursive calls are
8.19
procedure Select(L[0:n – 1], low, high, t, x) recursive
Input: L[0:n – 1] (an array of size n), low, high (indices of L[0:n – 1])
t (a positive integer such that low ≤ t ≤ high)
8.20 Suppose we have 5 distinct numbers x1, x2, x3, x4, x5. Using three comparisons, and
(1) x2 < x3 If x2 < x4 then the median is min(x3, x4) (since if x3 will be greater than x1, x2
(2) x2 > x3 If x3 > x4, then the median is min(x3, x5) (since if x3 then x3 will be greater than
x1, x4 and less than x2, x5, and if x5 then x5 will be greater than x1, x4 and less than x2,
8.21 Since W(n) 6 for n 5, we have W(n) 24n for n 5. For the induction step, assume
that W(k) ≤ 24k for all k < n, and consider W(n). We have:
8.22 The first step in writing Select2 is to make the same change to the pseudocode as was done
in Exercise 8.19 when writing Select nonrecursively. This leaves us with the recursive call
8.23 To ensure linear worst-case behavior, we can first arrange for distinct elements by altering
an input list L[0:n – 1] to a new list L’ where each element L[i] is replaced with the pair
8.25 It is sufficient to solve the special case of the problem when k = n, i.e., the median
element, since we can eliminate all but the first k elements from both sorted sublists.
Equivalently, we solve the problem of finding the median element of the combined elements
from two sorted lists L1[0:n – 1] and L2[0: n – 1]. A recursive solution is as follows.
function Median(L1[low1:high1], L2[low2:high2])
8.26 The point is here that the value of Pivot is known, but not its index. A version of
8.27 Without loss of generality we may assume that d = 1. We first prove the following lemma
Algorithms: Sequential, Parallel and Distributed, Second Edition 8-17
Lemma. If the pair-wise distance between any set of 4 points in the unit square is at least 1
then these points must be the four corner points of the square.
8.29 Assume for convenience that n = 2k for some k. Since the complexity of the combined
8.30 We first verify the case when n = 2. The convex hull of two points P1 and P2 is simply the
line joining them. Letting P be any point on this line segment, we have that P = P1 + P1P =
P1 + sP1P2 for some s, 0 ≤ s ≤ 1, i.e, P = P1 + s(P1 – P2) or
P = (1 – s)P1 + sP2, 0 ≤ s ≤ 1. (1)
Now consider the general case of the convex hull C of n points P1, …, Pn in the plane. Let P be
1.
Induction Step. Assume true for n = k, i.e., and consider the case n = k + 1, i.e., suppose P =
λ1P1 + λ2P2 + … + λkPk for some choice of λi, λ1 + λ2 + … + λk = 1, λi ≥ 0, i = 1, …, n. We
8.32 Since the n points Pi = (xi, xi2), i = 1, …, n, all lie on the parabola y = x2, they all lie on the
boundary of their convex hull. Further, scanning them in counterclockwise order starting with
n
iii xxx ...
21
n
1
8.33 Letting n = 70k and using repeated substitution we obtain
