CS计算机代考程序代写 algorithm Divide & Conquer Master Theorem

Divide & Conquer Master Theorem
2021-01-12 CSC373 Winter 2021 – Sam Toueg 1

Divide & Conquer
• Divide & conquer algorithm:
Ø divide problem of size 𝑛 into 𝑎 smaller subproblems of size 𝑛/𝑏 each
Ø recursively solve each subproblem
Ø combine the subproblem solutions into the solution of the original problem
• Runtime 𝑛>1: 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛% integer𝑎≥1,𝑏>1,𝑐≥0,𝑑≥0
Time on input of size 𝑛
Assume that 𝑛 is a power of 𝑏
Time for the
recursive calls
Time for dividing the problem and combining the subproblem solutions
# Problems Size
1𝑛
𝒂 𝒂𝒂
……
𝒂
𝑎 𝑎&
𝑎!”#!$
= 𝑛!”#!’
𝑛/𝑏 𝑛/𝑏&
1= 𝑛/𝑏!”#!$ = 𝑛/𝑛 2

𝒂𝒂𝒂𝒂𝒂𝒂𝒂𝒂𝒂
………………
………
… … …
2021-01-12
CSC373 Winter 2021 – Sam Toueg

Master Theorem
• Divide & conquer algorithm:
Ø divide problem of size 𝑛 into 𝑎 smaller subproblems of size 𝑛/𝑏 each
Ø recursively solve each subproblem
Ø combine the subproblem solutions into the solution of the original problem
• Runtime 𝑛>1: 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛% integer𝑎≥1,𝑏>1,𝑐≥0,𝑑≥0 Time on input Time for the Time for dividing the problem and
of size 𝑛 recursive calls combining the subproblem solutions
𝑛=1: 𝑇(1)=𝑐
Master Theorem: See course handout for a proof!
special case 𝑑 = 1 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛
Θ 𝑛% ,
𝑇(𝑛)= Θ 𝑛%𝑙𝑜𝑔𝑛, Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏% if𝑎=𝑏% if 𝑎>𝑏%
Θ 𝑛 , 𝑇(𝑛)=:Θ 𝑛𝑙𝑜𝑔𝑛,
Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏 if𝑎=𝑏 if 𝑎>𝑏
Note 1: the running time does not depend on the constant 𝑐
Note 2: in many algorithms 𝑑 = 1 (dividing and combining takes linear time) 2021-01-12 CSC373 Winter 2021 – Sam Toueg 3

Master Theorem — Well-Known Examples Master Theorem: 𝑇(𝑛) = 𝑎 · 𝑇(𝑛/𝑏) + 𝑐 ·𝑛%
Θ 𝑛% ,
𝑇(𝑛)= Θ 𝑛%𝑙𝑜𝑔𝑛, Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏% if𝑎=𝑏% if 𝑎 > 𝑏%
• Merge Sort — sorting array of size 𝑛
Ø Split array into two arrays of size 𝑛/2 each
Ø Sort each subarray (recursively)
Ø Merge the two sorted subarrays (takes linear time)
Ø𝑎=2,𝑏=2, 𝑑=1 ⇒𝑎=𝑏! so: 𝑇(𝑛)=Θ 𝑛𝑙𝑜𝑔𝑛
• Binary Search — search an item 𝑥 in a sorted array of size 𝑛
Ø Compare 𝑥 with middle element of the array; depending on outcome: Ø Return found, or recursively search first or second half of the array
Ø𝑎=1,𝑏=2, 𝑑=0⇒𝑎=𝑏! so:𝑇(𝑛)=Θ 𝑙𝑜𝑔𝑛
2021-01-12 CSC373 Winter 2021 – Sam Toueg 4

Divide & Conquer
Karatsuba’s integer multiplication
2021-01-12 CSC373 Winter 2021 – Sam Toueg 6

Overview and Motivation • Binarynumber:100111010….
• Add two binary numbers of length 𝑛 Ø Running Time: Θ(𝑛)
• Multiply two binary numbers of length 𝑛 Ø Running Time: Θ(𝑛#)
𝑥 𝑦
• Can we multiply two numbers in less than Θ(𝑛#) time complexity? • Kolmogorov conjectured (in 1956) that Θ(𝑛#) is the best possible!
2021-01-12 CSC373 Winter 2021 – Sam Toueg 7

Assume 𝑛 is a power of 2
𝑥
𝑛/2
𝑛/2
Divide & Conquer – Idea I
𝑥;
𝑥< 𝑦; 𝑦< 𝑦 𝑛 This is a D&C algorithm 𝑥 = 𝑥; ' 2=/> + 𝑥< 𝑦 = 𝑦; ' 2=/> + 𝑦< 𝑥 ' 𝑦 = 𝑥; ' 𝑦; ' 2= + (𝑥; ' 𝑦< + 𝑥< ' 𝑦;) ' 2=/> + 𝑥< ' 𝑦< •𝑇𝑛 =4'𝑇 => +𝑐’𝑛 for𝑛>1;𝑇(1)=𝑐for𝑛=1 Ø Master Theorem: 𝑎 = 4, 𝑏 = 2, 𝑑 = 1
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=4>𝑏; =2):
Ø𝑇 𝑛 =Θ 𝑛”#$!% =Θ 𝑛”#$”& =Θ 𝑛’
2021-01-12 CSC373 Winter 2021 – Sam Toueg computation! 8
We did not speed up the

Divide & Conquer – Idea II (Karatsubas 1962)
𝑥@𝑦=𝑥( @𝑦( @2$ +(𝑥( @𝑦) +𝑥) @𝑦()@2$/& +𝑥) @𝑦)
Idea: Rewrite the above expression to have 3 multiplications instead of 4 𝑥M𝑦=𝑥(M𝑦(M2)+(𝑥(+𝑥* M 𝑦(+𝑦* −𝑥(M𝑦(−𝑥*M𝑦*)M2)/’+𝑥*M𝑦*
• 𝑇 𝑛 = 3 C 𝑇 &# + 𝑐 C 𝑛
Ø Master Theorem: 𝑎 = 3, 𝑏 = 2, 𝑑 = 1
• Since𝑎=3>𝑏$ =2,thisiscase(𝑐)oftheMasterTheorem: Ø𝑇 𝑛 =Θ 𝑛!”#!$ =Θ 𝑛!”#”% =Θ 𝑛&.()(…
• Minorissue:acarrymayincreaselengthof𝑥$ +𝑥% and 𝑦$ +𝑦% to=> +1 1 𝑛/2
𝑢$
𝑢%
𝑥$ + 𝑥% 𝑦$ + 𝑦%
2021-01-12
= 𝑢$· 2&/# + 𝑢%
= 𝑣$· 2&/# + 𝑣%
𝑢$ ·𝑣$ ·2& +(𝑢$ ·𝑣% +𝑢% ·𝑣$)·2&/# +𝑢% ·𝑣%
𝑣$
𝑣%
1×1 1x$ $x1 $x$ &&&&
CSC373 Winter 2021 – Sam Toueg 9

𝑥@𝑦=𝑥( @𝑦( @2$ +( 𝑥( +𝑥) @ 𝑦( +𝑦) −𝑥( @𝑦( −𝑥) @𝑦))@2$& +𝑥) @𝑦)
MULT(𝑥,𝑦):
• 𝑛 ← max{𝑙𝑒𝑛𝑔𝑡h 𝑥 ,𝑙𝑒𝑛𝑔𝑡h 𝑦 }
𝑐
𝑢
𝑏𝑠𝑡𝑏𝑎𝑎
• Put 0’s to the left of the shortest of 𝑥 and 𝑦 so both have length 𝑛
𝑥 ;
𝑦;
𝑥 < 𝑦< • 𝑥# ←leftmost𝑛/2bitsof𝑥 • 𝑦# ← leftmost 𝑛/2 bits of 𝑦 • 𝑥$ ← rightmost 𝑛/2 bits of 𝑥 • 𝑦$ ← rightmost 𝑛/2 bits of 𝑥 • 𝑠 ← 𝐴𝑑𝑑(𝑥$, 𝑥#) • 𝑡 ← 𝐴𝑑𝑑(𝑦$, 𝑦#) • 𝑎 ← 𝑀𝑢𝑙𝑡(𝑥$, 𝑦$) • 𝑏 ← 𝑀𝑢𝑙𝑡(𝑥#, 𝑦#) • 𝑐 ← 𝑀𝑢𝑙𝑡(𝑠, 𝑡) • 𝑢 ← 𝑆𝑢𝑏𝑡𝑟𝑎𝑐𝑘(𝑐, 𝐴𝑑𝑑(𝑎, 𝑏)) • Put𝑛zerostotherightof𝑏 • Put 𝑛/2 zeros to the right of 𝑢 • Return 𝐴𝑑𝑑(𝑏, 𝐴𝑑𝑑 (𝑢 , 𝑎)) 2021-01-12 𝑥 𝑦 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 CSC373 Winter 2021 - Sam Toueg 10 Integer Multiplication • Whatcanwedowhen𝑛isnotapowerof2? • Embed each vector in a vector whose dimension is the next power of 2 • In the worst-case, this doubles the dimension: Ø from 𝑛+,-". we go to at most (2𝑛)+,-". Ø Since 2+,-". = 3 this increases the time complexity by a factor of at most 3 Example: 35 𝑥 𝑦 6 000 00 2 2021-01-12 CSC373 Winter 2021 - Sam Toueg 11 Integer Multiplication • Can one multiply two 𝑛 -digits integers in less than Θ 𝑛KLM+N time? • 1962: Karatsuba Θ 𝑛KLM+N ≈ Θ 𝑛;.PQP... • 1971: Schönhage-Strassen Θ 𝑛 ' 𝑙𝑜𝑔 𝑛 ' 𝑙𝑜𝑔𝑙𝑜𝑔 𝑛 • 2019: Harvey and van der Hoeven Θ 𝑛 ' 𝑙𝑜𝑔 𝑛 !! • https://rjlipton.wordpress.com/2019/03/29/integer-multiplication-in-nlogn-time/ 2021-01-12 CSC373 Winter 2021 - Sam Toueg 12 Divide & Conquer Strassen's Matrix Multiplication Algorithm 2021-01-12 CSC373 Winter 2021 - Sam Toueg 13 Overview and Motivation • Let 𝐴 and 𝐵 be two 𝑛×𝑛 matrices ØAssume 𝑛 is a power of 2 •Wewanttocompute𝐶= 𝐴·𝐵 Ø Running Time: Θ(𝑛N) • Can we multiply two 𝑛×𝑛 matrices in less than Θ(𝑛Q) time? 2021-01-12 CSC373 Winter 2021 - Sam Toueg 14 Divide & Conquer – Idea I 𝑛/2 𝐴𝑛/2 𝑛/2 𝐵𝑛/2 𝑛× 𝑏; 𝑏>
𝑏N
𝑏T
𝑐;
𝑐>
𝑐N
𝑐T
𝑎;
𝑎>
𝑎N
𝑎T
𝑛/2 𝑛/2
𝑛/2 𝐶𝑛/2 𝑛𝑛𝑛
=
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏. 𝑐& = 𝑎( @ 𝑏& + 𝑎& @ 𝑏/ 𝑐. = 𝑎. @ 𝑏( + 𝑎/ @ 𝑏. 𝑐/ = 𝑎. @ 𝑏& + 𝑎/ @ 𝑏/
•𝑇𝑛 =8’𝑇 => +𝑐’𝑛> for𝑛>1;𝑇(1)=𝑐for𝑛=1 Ø Master Theorem: 𝑎 = 8, 𝑏 = 2, 𝑑 = 2
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=8>𝑏S =4): Ø𝑇 𝑛 =Θ 𝑛”#$!% =Θ 𝑛”#$”, =Θ 𝑛- Wedidnotspeed
up the
2021-01-12 CSC373 Winter 2021 – Sam Toueg computation! 15
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏.

Divide & Conquer – Idea II (Strassen)
Idea: Compute 𝑐;, 𝑐>, 𝑐N, 𝑐T with 7 ()’ x )’ ) matrix multiplications, not 8
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏. 𝑐& = 𝑎( @ 𝑏& + 𝑎& @ 𝑏/ 𝑐. = 𝑎. @ 𝑏( + 𝑎/ @ 𝑏. 𝑐/ = 𝑎. @ 𝑏& + 𝑎/ @ 𝑏/
• 𝑚( = (𝑎’ − 𝑎&) M (𝑏- + 𝑏&) • 𝑚’ = (𝑎( + 𝑎&) M (𝑏( + 𝑏&) • 𝑚- = (𝑎( − 𝑎-) M (𝑏( + 𝑏’) • 𝑚& = (𝑎( + 𝑎’) M 𝑏&
• 𝑚. = 𝑎( M (𝑏’ − 𝑏&) • 𝑚/ = 𝑎& M (𝑏- − 𝑏() • 𝑚0 = (𝑎-+𝑎&) M 𝑏(
instead of computing 𝑐#, 𝑐%, 𝑐&, 𝑐’ like this…
• 𝑐( = 𝑚( + 𝑚’ − 𝑚& + 𝑚/
• 𝑇 𝑛 = 7 M 𝑇 )’ + 𝑐 M 𝑛 ‘
Ø Master Theorem: 𝑎 = 7, 𝑏 = 2, 𝑑 = 2
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=7>𝑏! =4): Ø𝑇 𝑛 =Θ 𝑛!”#!’ =Θ 𝑛!”#”0 =Θ 𝑛&.2(
• 𝑐’ = 𝑚& + 𝑚.
• 𝑐- = 𝑚/ + 𝑚0
• 𝑐& = 𝑚’ − 𝑚- + 𝑚. + 𝑚0
Check it at home (when boredJ)
2021-01-12 CSC373 Winter 2021 – Sam Toueg
16

Divide & Conquer – Idea II (Strassen)
• Whatcanwedowhen𝑛isnotapowerof2?
• Embed each matrix in a matrix whose dimension is the next power of 2
• In the worst-case, this doubles the dimension:
Ø From 𝑛+,-“0 we go to at most (2𝑛)+,-“0
Ø Since 2+,-“0 = 7 this increases the time complexity by a factor of at most 7
Example: 𝑛 = 155 155
101
155 101 155 + 101 = 256 = 22
𝐴
0
0
0
2021-01-12
CSC373 Winter 2021 – Sam Toueg 17