---------------------------- 4 ---------------------------- 4-2

Divide-and-Conquer A brute-force solution

all pairs of i, j 4-2xy
(Recurrences)
n
* Examine all   possible S[i, j]
Divide-and-Conquer: 4-1x  2
Divide: (into the same problems of
smaller size) * Two implementations O(j – i + 1)
Conquer:
Combine: (1) compute each S[i, j] in O(n) time  O(n3) time

Two examples of divide-and-conquer: 4.1, 4.2 (2) compute each S[i, j+1] from S[i, j] in O(1) time
Solving recurrences: 4.3, 4.4, 4.5 (S[i, i] = A[i] and S[i, j+1] = S[i, j] + A[j+1])
 O(n2) time
(ex. S[2, 12] = S[2, 11] + A[12])
4.1 The maximum-subarray problem
i=2
i 1 2 3 4 5 6 7 8 9 10 11 12 13
Input: an array A[1..n] of n numbers
A[i] 13 -15 23 4 -13 -16 -23 18 20 -7 12 -5 -22
Output: a nonempty subarray A[i..j] having S[2, 2] = -15
the largest sum S[i, j] = ai + ai+1 +... + aj S[2, 3] = 8
S[2, 4] = 12
S[2, 5] = -1 O(n) time for each i
20 18

A divide-and-conquer solution

* Possible locations of a maximum subarray A[i..j]

S[8, 11] = 43
of A[p..r], where q = (p+r)/2
 4-3 4-4
(1) entirely in A[p..q] * Find a maximum subarray crossing the midpoint
(2) entirely in A[q+1..r]
(3) crossing the midpoint (p  i < q < j  r) A[q+1..j]
p i q r
(3)
crosses the midpoint
q+1 j
p 4q = (p+r)/2 r A[i..q]
-
A[i..j] comprises two subarrays
q+1 A[i..q] and A[q+1..j]
(1) entirely in A[p..q] (2) entirely in A[q+1..r]
Locations of a maximum subarray A[i..j] of A[p..r] FINDMAXCROSSING(A, p, q, r)
4-3x 1 s1  
* A divide-and-conquer algorithm
2 sum  0
3 for i  q downto p do Find maxleft, s1
FINDMAXSUBARRAY(A, p, r)
4 sum  sum  A[i]
1 if p = r then return (p, p, A[p]) //base case (A[i..q])
take it even negative 5 if sum > s1
2 else (nonempty subarray) recursive
3 q  (p + r)  2 calls 6 then s1  sum
4 (i1, j1, s1)  FINDMAXSUBARRAY(A, p, q) 7 maxleft  i
5 (i2, j2, s2)  FINDMAXSUBARRAY(A, q+1, r) 8 s2  
6 (ic, jc, sc)  FINDMAXCROSSING(A, p, q, r) 9 sum  0
7 if s1  s2 and s1  sc then return (i1, j1, s1) 10 for j  q  1 to r do
11 sum  sum  A[j] Find maxright, s2
8 elseif s2  sc then return (i2, j2, s2) (A[q+1..j])
9 else return (ic, jc, sc) 12 if sum > s2
13 then s2  sum
14 maxright  j
15 return (maxleft, maxright, s1  s2)
 4-5 4-6
Example: (2) FINDMAXSUBARRAY:
q=6 T(n) = 2T(n/2) + (n) (with T(1) = (1))
1 2 3 4 5 6 7 8 9 10 11 12 = (nlg n) (similar to merge-sort)
A
-7 8 -5 20 -3 -8 -23 18 20 -7 12 -5
s1 =  maxleft Remark: See Ex4.1-5 for an O(n)-time algorithm.
S[6, 6] = -8 8 6
S[5, 6] = -11 4-6a
S[4, 6] = 9 9 4 4.2 Strassen’s algorithm for matrix
S[3, 6] = 4 multiplication
S[2, 6] =` 12  (maxleft = 2) 12 2
S[1..6] = 5
Input: two n  n matrices A and B 4-6y

q=6 Output: C = AB, where ci , j   aik bkj

1 2 3 4 5 6 7 8 9 10 11 12 1 k  n
A
-7 8 -5 20 -3 -8 -23 18 20 -7 12 -5
An O(n3) time naive algorithm
s2 = 
S[7, 7] = -23 23
S[7, 8] = -5 5 SQUARE-MATRIX-MULTIPLY(A, B)
S[7, 9] = 15 15
S[7, 10] = 8 1 n  rows[A]
S[7, 11] =` (maxright = 11)  20 20 2 let C be an n  n matrix
S[7, 12] = 15 3 for i  1 to n do
4 for j  1 to n do
 maximum subarray crossing q is A[2, 11] 5 cij  0
(with S[2, 11] = 32)
6 for k  1 to n do compute cij
7 cij  cij + aik • bkj
* Time complexity
8 return C
cij = aij + bij
(1) FINDMAXCROSSING: (n), where n = r  p + 1
* Computing A+B  O(n2) time
 4-7 4-8
Strassen’s algorithm
* We have r = P5 + P4 - P2 + P6
* Assume that n is an exact power of 2 s = P1 + P2
t = P3 + P4
* We divide each of A, B, and C into four n/2  n/2
u = P5 + P1 – P3 – P7 (EQ-3)
sub-matrices and rewrite C = AB as
C A B
n n
× r s   a b  e g 
2 2     (EQ-1) * Strassen’s divide-and-conquer algorithm
t u   c d  f h 
1 2 3 4 Step 1: Divide each of A, B, and C into four
* We have r = ae + bf s = ag + bh sub-matrices. (EQ-1)
t = ce + df u = cg + dh
5 6 7 8
Step 2: Recursively, compute P1, P2, …, P7.
* A straightforward divide-and-conquer algorithm
(EQ-2) 7 '×', 10 '+'
T(n) = 8T(n/2) + O(n2) Step 3: Compute r, s, t, u according to EQ-3.
= O(n3) n
4×( )2 for addition
2 8 '+'
1
* Let P1 = a(g-h) (=ag-ah) * Time complexity
2
P2 = (a+b)h (=ah+bh)
3
P3 = (c+d)e (=ce+de) T(n) = 7T(n/2) + O(n2)
4
P4 = d(f-e) (=df-de) = O( n log2 7 ) 18×( n )2 (for addition)
2
5
P5 = (a+d)(e+h) (=ae+ah+de+dh) = O(n 2.81 ) (by Master Thm)
6
P6 = (b-d)(f+h) (=bf+bh-df-dh)
P7 = (a-c)(e+g) (=ae+ag-ce-cg) (EQ-2)
7
 4-9 4-10
4-10x
4.3 The substitution method
Discussion:
The substitution method: (i) Guess an answer
1. Strassen’s method is largely of theoretical and then (ii) prove it by induction. (for both upper
interest. (for n  45) and lower bounds)
n
T(n) = qT( ) + O(n2) "q < 7?" Example: Find an upper bound for
2
2. Strassen’s method is based on the fact that we T(n) = 2T(n/2) + n (with T(1) = 1)
can multiply two 2  2 matrices using only 7
multiplications (instead of 8). It was showed that (i) Guess T(n) = O(nlg n).
it is impossible to multiply two 2  2 matrices
using less than 7 multiplications. (ii) Try to prove there exist constants c and n0
such that T(n)  cn lg n for all n  n0.
4-9x

3. We can improve Strassen’s algorithm by finding Basis: (n = n0)

an efficient way to multiply two k  k matrices
using a smaller number q of multiplications, For n = 1, no constant c satisfies T(1)  cn lg n=0.
where k > 2. The time is T(n) = qT(n/k) + O(n2). For n  2, any constant c  T(n)/(n lg n) satisfies
q < k3 T(n)  cn lg n. That is, we can choose
*1990
4. The current best upper bound is O(n2.376). (1) n0  2 and c  T(n0)/(n0 lg n0).
*2010: 2.374; 2011: 2.3728642; 2014: 2.3728639
Induction: (n > n0)
Assume: T(x) cx lg x for x = n0 ~ n-1
Assume that it holds for all n between n0 and n1.
We have
 x 將T(x)  cx lg x代入
T(n) = 2T(n/2) + n 4-11 4-12
x x  If c and n0 are known, we can prove (1)
T(n)  2(cn/2 lg n/2) + n (Substitution) by induction
 cn lg (n/2) + n
= cn lg n – cn lg 2 + n (a) Basis step: (1) holds for n = n0
= cn lg n – cn + n (b) Induction step: (1) holds for n > n0
 cn lg n, goal
 How to find c and n0 satisfying the
where the last step holds for induction proof?
* to make substitution holds, we
(2) c  1. also need n0  n/2  n-1 (i) find the condition of c and n0 for
=> n0 = 2, 3, n  4 which the basis step holds
From (1) and (2), we can choose n0 = 2, 3 and c (ii) find the condition of c and n0 for
= max{1, T(2)/(2 lg 2), T(3)/(3 lg 3)} = 2 to make which the induction step holds
both the basis and the induction steps holds. (iii) Combine conditions (i) and (ii)
/'sʌtltI/
Substitution Method Subtleties: 微妙之處(細微的差別) 4-12a

(Revise a guess by subtracting a lower-order

Step 1. Guess T(n) = O(g(n)) term.) induction proof does not always work
unless the exact form is given
Step 2. Prove the guess by induction Example: T(n)=T(n/2)+T(n/2)+1 (with T(1)=1)

Prove T(n) = O(g(n)) Guess T(n) = O(n).

 c, n0 s.t.
 Prove that there are c and n0 such that Try to prove T(n)  cn. (for all n  n0)
T(n)  cg(n) for all n  n0 ------------(1) Basis: ok!
 Assume: T(x) cx for x = n0 ~ n-1 4-13 T(n) = S(m) = S(lg n) = lg n lglg n 4-14
Induction: T(n) = T(n/2) + T(n/2) + 1 Since O(m lg m) is the solution to S(m), we know
 c(n/2 + n/2) + 1 that O(lg n lglg n) is the solution to T(n).
= cn + 1
We can not prove that T(n)  cn !!!! 4.4 The iteration (recursion-tree) method 4-14x

goal
with T(0) = c = Θ(1)
Try to prove T(n)  cn – b. (for n  n0) Example: T(n) = 3T(n/4) + n
T(1) = c = Θ(1)
Induction: T(n)  (cn/2-b) + (cn/2 -b) + 1 T(x)= x + 3T(x/4)
4-14y

= cn – 2b + 1 T(n) = n + 3(n/4 + 3T(n/16))

 cn – b, goal = n + 3n/4 + 9(n/16 +n3T(n/64))
n
where the last step holds for any constant b  1. . 3kT( 4k) ≤1 k ≥ lg4 n
4klog n
陷阱 Basis: (n0 = 1) 1≤c-b . (note that n/( 4 4 )  1)
Avoiding pitfalls c≥b+1  n + 3n/4 + 9n/16 + 27n/64 + ... + 3log4 n (1)
T(n) = 2T(n/2) + n  3 T(0),T(1)
Guess T(n) = O(n). Try to prove T(n)  cn.  n  ( )  (n
i log 4 3 ) = 4n+o(n) = O(n)
i 0 4
Induction: T(n)  2cn/2 + n *a lgc b
=b lgc a

 cn + n * n/a/b = n/ab (similar for ceiling)

= O(n)  wrong !! 4-13x
Recursion trees: (for visualizing the iteration)
 cn (goal) with T(1) = 1 or Θ(1) 4-14z
Changing variable: Assume: T(x) cx T(n) = 2T(n/2) + n2 (Assume that n = 2h.)
for x = n0 ~ n-1
T(n) = 2T( n ) + lg n

For simplicity, assume n = 2m. Then

T(2m) = 2T(2m/2) +m
Let S(m) = T(2m). We have
S(m) = 2S(m/2) + m (Renaming m = lg n)
 Cost (Internal nodes) + Cost (leaves)
O(n2) L(1) = O(n) 4-15 4-16
4.5 The master method

Theorem 4.1 (Master theorem)

Let a  1 and b > 1 be constants, let f(n) be a
function, and let T(n) be defined on the
h= nonnegative integers by the recurrence

T(n) = aT(n/b) + f(n),

where we interpret n/b to mean either n/b or

T(1) T(1) T(1) T(1) . . . . . . . n/b. Then, T(n) can be bounded as follows.
n leaves 4-16a
  or  
但不可以同時取   1.If f(n) = O(n (logb a ) ) for some constant  > 0,
Example: T(n) = T(n/3) + T(2n/3) + n
(T(0)=T(1)=T(2)=1 or Θ(1)) then T(n) = (n logb a ).
≤
2n
2.If f(n) = (n logb a ), then T(n) = (n logb a lg n )
n
T( ) T( ) 
3 3 3.If f(n) = (n (logb a ) ) for some constant  > 0,
≤ 4-15a

and if af(n/b)  cf(n) for some constant c < 1 and
h=
all sufficiently large n, then T(n) = (f(n)).
≤

T(1) T(0) . . . . . . . .
4-15a

* Using recursive trees to make a good guess for S.M. 4-15y

 a=9 b=3 * logb a = 2 4-17 4-18
Example: T(n) = 9T(n/3) + n
f(n)
n n lg n (recur. tree, MS)
By applying case 1, we have T(n) = (n2).
a=1 b=3/2 n
* logb a = 0 T(n) = 2T( ) + n2 n2 (recur. tree, MS)
Example: T(n) = T(2n/3) + 1 2
f(n) n lg n n lg2 n (recur. tree)
By applying case 2, we have T(n) = (lg n).
a=3 b=4 * log4 3 ≈ 0.793 4-17x
Example: T(n) = 3T(n/4) + n lg n
* c = 3/4
By applying case 3, we have T(n) = (n lg n).

Note: The three cases do not cover all the 4-16a

possibilities for f(n). There are gaps between

cases 1 and 2, and between cases 2 and 3.

Example: T(n) = 2T(n/2) + n lg n O(n lg2 n)

(recursion tree)
In this example, both cases 2 and 3 cannot be
applied.
*Case 1. O(n
logb a - )
= o(n
logb a
) ???
4-16a

Homework: Ex. 4.1-5, 4.2-1, 4.2-4, 4.2-5, 4.2-7,

4.3-5 (using substitution method), 4.4-6, 4.4-9, 4.5-2,
and Pro.4-5bc(using substitution method), 4-6de.