Advanced Core in Algorithm Design #6

算法設計要論 第 6 回

Yasushi Kawase
河瀬 康志

Nov. 8th, 2022

last update: 12:46pm, November 8, 2022

Yasushi Kawase Advanced Core in Algorithm Design 1 / 24

Schedule

Lec. # Date Topics

1 10/4 Introduction, Stable matching
2 10/11 Basics of Algorithm Analysis, Greedy Algorithms (1/2)
3 10/18 Greedy Algorithms (2/2)
4 10/25 Divide and Conquer (1/2)
5 11/1 Divide and Conquer (2/2)
6 11/8 Dynamic Programming (1/2)
7 11/15 Dynamic Programming (2/2)
— 11/22 Thursday Classes
8 11/29 Network Flow (1/2)
9 12/6 Network Flow (2/2)
10 12/13 NP and Computational Intractability
11 12/20 Approximation Algorithms (1/2)
12 12/27 Approximation Algorithms (2/2)
13 1/10 Randomized Algorithms

Yasushi Kawase Advanced Core in Algorithm Design 2 / 24

Algorithmic Paradigms

Divide-and-Conquer
• Divide up problem into several independent problems
• Solve each subproblems recursively
• Combine solutions to subproblems into overall solution

Dynamic Programming
• Divide up problem into several overlapping problems
• Solve each subproblems recursively (or bottom up)
• Combine solutions to subproblems into overall solution

Yasushi Kawase Advanced Core in Algorithm Design 3 / 24

Outline

1 Weighted interval scheduling

2 Subset sums and knapsacks

3 Segmented least squares

4 Sequence alignment

Yasushi Kawase Advanced Core in Algorithm Design 4 / 24

Weighted interval scheduling

Problem
• Input: jobs J = {1, 2, . . . , n},
job j starts at sj , finishes at fj , and has value vj > 0
• Goal: find maximum value subset of mutually compatible jobs
two jobs that don’t overlap

Example
v=2
4
4
7
2
1
time

Yasushi Kawase Advanced Core in Algorithm Design 5 / 24

Weighted interval scheduling

Problem
• Input: jobs J = {1, 2, . . . , n},
job j starts at sj , finishes at fj , and has value vj > 0
• Goal: find maximum value subset of mutually compatible jobs
two jobs that don’t overlap

Example
v=2
4
4
7
2
1
time

Yasushi Kawase Advanced Core in Algorithm Design 5 / 24

Recursive relation
• sort the jobs by finish time (f1 ≤ f2 ≤ · · · ≤ fn )
• OPT(j): optimal solution for subproblem consisting only of {1, 2, . . . , j}

Recursive formula

0 if j = 0,
(
OPT(j) =
max{vj + OPT(p(j)), OPT(j − 1)} if j > 0
maximum i such that f (i) ≤ s(j) (found in O(log n) via binary search)

v=2
4
p(j) 4
7
2
j 1
time

Time complexity: O(n log n)

Yasushi Kawase Advanced Core in Algorithm Design 6 / 24

Example

j
1 v=2
2 4
3 4
4 7
5 2
6 1
time

j 0 1 2 3 4 5 6

OPT(j)

Yasushi Kawase Advanced Core in Algorithm Design 7 / 24

Example

j
1 v=2
2 4
3 4
4 7
5 2
6 1
time

j 0 1 2 3 4 5 6

OPT(j) 0 2 4 6 7 8 8

Yasushi Kawase Advanced Core in Algorithm Design 7 / 24

Quiz

What is the optimal value of the following problem?

j
1 v=3
2 4
3 5
4 7
5 4
6 8
7 10
8 5
9 8
10 6
time

Yasushi Kawase Advanced Core in Algorithm Design 8 / 24

Outline

1 Weighted interval scheduling

2 Subset sums and knapsacks

3 Segmented least squares

4 Sequence alignment

Yasushi Kawase Advanced Core in Algorithm Design 9 / 24

Subset sum

Problem
• Input: positive integers a1 , a2 , . . . , an and W
• Goal: find I ⊆ {1, 2, . . . , n} such that i∈I ai = W
P

Examples
• a = (1, 3, 7, 8, 11), W = 20 possible (1 + 8 + 11 = 20)

• a = (2, 4, 8, 10, 12), W = 19 impossible

Yasushi Kawase Advanced Core in Algorithm Design 10 / 24

Dynamic programming for subset sum problem
ψ(k, w): solution for a1 , a2 , . . . , ak and w (True or False)
Recursive formula

True if k = 0 and w = 0


if k = 0 and w > 0

False

ψ(k, w) =

 ψ(k − 1, w) if w < ak
ψ(k − 1, w) ∨ ψ(k − 1, w − ak ) otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example: a1 = 2, a2 = 4, a3 = 3, W = 5
k \ w 0 1 2 3 4 5
0 — — — — — —
a1 = 2 1 — — — — — —
a2 = 4 2 — — — — — —
a3 = 3 3 — — — — — —
Yasushi Kawase Advanced Core in Algorithm Design 11 / 24
Dynamic programming for subset sum problem
ψ(k, w): solution for a1 , a2 , . . . , ak and w (True or False)
Recursive formula

True if k = 0 and w = 0


if k = 0 and w > 0

False

ψ(k, w) =

 ψ(k − 1, w) if w < ak
ψ(k − 1, w) ∨ ψ(k − 1, w − ak ) otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example: a1 = 2, a2 = 4, a3 = 3, W = 5
k \ w 0 1 2 3 4 5
0 True False False False False False
a1 = 2 1 — — — — — —
a2 = 4 2 — — — — — —
a3 = 3 3 — — — — — —
Yasushi Kawase Advanced Core in Algorithm Design 11 / 24
Dynamic programming for subset sum problem
ψ(k, w): solution for a1 , a2 , . . . , ak and w (True or False)
Recursive formula

True if k = 0 and w = 0


if k = 0 and w > 0

False

ψ(k, w) =

 ψ(k − 1, w) if w < ak
ψ(k − 1, w) ∨ ψ(k − 1, w − ak ) otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example: a1 = 2, a2 = 4, a3 = 3, W = 5
k \ w 0 1 2 3 4 5
0 True False False False False False
a1 = 2 1 True False True False False False
a2 = 4 2 — — — — — —
a3 = 3 3 — — — — — —
Yasushi Kawase Advanced Core in Algorithm Design 11 / 24
Dynamic programming for subset sum problem
ψ(k, w): solution for a1 , a2 , . . . , ak and w (True or False)
Recursive formula

True if k = 0 and w = 0


if k = 0 and w > 0

False

ψ(k, w) =

 ψ(k − 1, w) if w < ak
ψ(k − 1, w) ∨ ψ(k − 1, w − ak ) otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example: a1 = 2, a2 = 4, a3 = 3, W = 5
k \ w 0 1 2 3 4 5
0 True False False False False False
a1 = 2 1 True False True False False False
a2 = 4 2 True False True False True False
a3 = 3 3 — — — — — —
Yasushi Kawase Advanced Core in Algorithm Design 11 / 24
Dynamic programming for subset sum problem
ψ(k, w): solution for a1 , a2 , . . . , ak and w (True or False)
Recursive formula

True if k = 0 and w = 0


if k = 0 and w > 0

False

ψ(k, w) =

 ψ(k − 1, w) if w < ak
ψ(k − 1, w) ∨ ψ(k − 1, w − ak ) otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example: a1 = 2, a2 = 4, a3 = 3, W = 5
k \ w 0 1 2 3 4 5
0 True False False False False False
a1 = 2 1 True False True False False False
a2 = 4 2 True False True False True False
a3 = 3 3 True False True True True True
Yasushi Kawase Advanced Core in Algorithm Design 11 / 24
Knpsack problem

Problem
• Input: items E = {1, 2, . . . , n} and a capacity W ∈ Z+
item i has value vi ∈ Z+ and size wi ∈ Z+
• Goal: maximize i∈I vi subject to I ⊆ {1, 2, . . . , n} i∈I wi ≤ W
P P

Examples
W = 16
i vi wi
1 55 4
2 61 2
3 82 9
4 38 1
5 63 3

Yasushi Kawase Advanced Core in Algorithm Design 12 / 24

Knpsack problem

Problem
• Input: items E = {1, 2, . . . , n} and a capacity W ∈ Z+
item i has value vi ∈ Z+ and size wi ∈ Z+
• Goal: maximize i∈I vi subject to I ⊆ {1, 2, . . . , n} i∈I wi ≤ W
P P

Examples
W = 16 optimal value is 61 + 82 + 38 + 63 = 244
i vi wi
1 55 4
2 61 2
3 82 9
4 38 1
5 63 3

Yasushi Kawase Advanced Core in Algorithm Design 12 / 24

Dynamic programming for knapsack problem
OPT(k, w) = max vi | X ⊆ {1, 2, . . . , k}, wi ≤ w
P P
i∈X i∈X

Recursive formula

0 if k = 0,


OPT(k, w) = OPT(k − 1, w) if wk > w
max{OPT(k − 1, w), OPT(k − 1, w − wk ) + vk } otherwise



Compute for k = 0, 1, . . . , n and w = 0, 1, . . . , W O(nW ) time

Example (wi , vi ) = (4, 55), (2, 61), (9, 82), (1, 38), (3, 63), W = 16
k\w 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 55 55 55 55 55 55 55 55 55 55 55 55 55
2 0 0 61 61 61 61 116 116 116 116 116 116 116 116 116 116 116
3 0 0 61 61 61 61 116 116 116 116 116 143 143 143 143 198 198
4 0 38 61 99 99 99 116 154 154 154 154 154 181 181 181 198 236
5 0 38 61 99 101 124 162 162 162 179 217 217 217 217 217 244 244

Yasushi Kawase Advanced Core in Algorithm Design 13 / 24

Outline

1 Weighted interval scheduling

2 Subset sums and knapsacks

3 Segmented least squares

4 Sequence alignment

Yasushi Kawase Advanced Core in Algorithm Design 14 / 24

Least squares
Problem (xi , yi )

• Input: n points p1 , p2 , . . . , pi , . . . , pn ∈ R2
• Goal: find a line y = ax + b that minimizes the sum of the squared error
Pn
i=1 (yi − axi − b)2
Example
y

x
Pn Pn Pn Pn Pn
n i=1 xi yi −( i=1 xi )( i=1 yi ) yi −a i=1 xi
Optimal solution: a = Pn n
2 ,b= i=1
n
n i=1 xi2 − i=1 xi
P

O(n) time

Yasushi Kawase Advanced Core in Algorithm Design 15 / 24

Least squares
Problem (xi , yi )

• Input: n points p1 , p2 , . . . , pi , . . . , pn ∈ R2
• Goal: find a line y = ax + b that minimizes the sum of the squared error
Pn
i=1 (yi − axi − b)2
Example
y

x
Pn Pn Pn Pn Pn
n i=1 xi yi −( i=1 xi )( i=1 yi ) yi −a i=1 xi
Optimal solution: a = Pn n
2 ,b= i=1
n
n i=1 xi2 − i=1 xi
P

O(n) time

Yasushi Kawase Advanced Core in Algorithm Design 15 / 24

Least squares
Problem (xi , yi )

• Input: n points p1 , p2 , . . . , pi , . . . , pn ∈ R2
• Goal: find a line y = ax + b that minimizes the sum of the squared error
Pn
i=1 (yi − axi − b)2
Example
y

x
Pn Pn Pn Pn Pn
n i=1 xi yi −( i=1 xi )( i=1 yi ) yi −a i=1 xi
Optimal solution: a = Pn n
2 ,b= i=1
n
n i=1 xi2 − i=1 xi
P

O(n) time

Yasushi Kawase Advanced Core in Algorithm Design 15 / 24

Segmented least squares
Problem (xi , yi )

• Input: n points p1 , p2 , . . . , pi , . . . , pn ∈ R2 and c > 0

Pn
• Goal: find segments y = f (x) that minimizes i=1 (yi − f (xi ))2 + cL
# of segements

Examples
y

Yasushi Kawase Advanced Core in Algorithm Design 16 / 24

Segmented least squares
Problem (xi , yi )

• Input: n points p1 , p2 , . . . , pi , . . . , pn ∈ R2 and c > 0

Pn
• Goal: find segments y = f (x) that minimizes i=1 (yi − f (xi ))2 + cL
# of segements

Examples
y

L=2

Yasushi Kawase Advanced Core in Algorithm Design 16 / 24

Dynamic programming
Notation
• OPT(j): opt. val. of segmented least squares for p1 , p2 , . . . , pj
• eij : opt. val. of least squares for pi , pi+1 , . . . , pj computable in O(n) time

Recursive formula

0 if j = 0
(
OPT(j) =
min1≤i≤j {eij + c + OPT(i − 1)} if j > 0

Compute for j = 0, 1, . . . , n, each of which takes O(n 2 ) O(n 3 ) time

y

x
Yasushi Kawase Advanced Core in Algorithm Design 17 / 24
Improve the computational time

Pj
Bottleneck: computing eij = k=i (yk − aij xk − bij )2 takes O(n) time
(j−i+1)n jk=i xk yk −( jk=i xk )( jk=i yk )
P P P
• aij = 2
(j−i+1) jk=i xk2 −
 Pj
k=i xk
P

Pj
yk −aij jk=i xk
P
• bij = k=i
j−i+1

Approach
Pj Pj Pj 2
Pj
• precompute k=1 xk , k=1 yk , k=1 xk , k=1 xk yk (∀j) in O(n) time
• using cumulative sums, eij can be computed in O(1) time
segmented least squares is solvable in O(n 2 ) time

Yasushi Kawase Advanced Core in Algorithm Design 18 / 24

Outline

1 Weighted interval scheduling

2 Subset sums and knapsacks

3 Segmented least squares

4 Sequence alignment

Yasushi Kawase Advanced Core in Algorithm Design 19 / 24

String similarity

Q: How similar are two strings X = x1 x2 . . . xm and Y = y1 y2 . . . yn

Alignment of X and Y
set of ordered pairs xi –yj such that each character appears in at most one
pair and no crossing

Example “ocurrance” and “occurrence”

o c u r r a n c e – o c – u r r a n c e o c – u r r – a n c e
o c c u r r e n c e o c c u r r e n c e o c c u r r e – n c e
6 mismatches, 1 gap 1 mismatch, 1 gap 0 mismatches, 3 gaps

Yasushi Kawase Advanced Core in Algorithm Design 20 / 24

Edit distance
Edit distance: minimum sum of gap and mismatch penalties
• Gap penalty δ ≥ 0
• Mismatch penalty αpq ≥ 0 (αpp = 0)

Example
o c – u r r a n c e o c – u r r – a n c e

o c c u r r e n c e o c c u r r e – n c e
cost = δ + αae cost = 3δ

Problem
• Input: two strings X = x1 x2 . . . xm and Y = y1 y2 . . . yn , penalty δ, αpq
• Goal: compute the edit distance

Yasushi Kawase Advanced Core in Algorithm Design 21 / 24

Dynamic programming for knapsack problem
OPT(i, j): edit distance for x1 x2 . . . xi and y1 y2 . . . yj

Recursive formula

jδ if i = 0



iδ  if j = 0




OPT(i, j) = αxi yj + OPT(i − 1, j − 1)

 
OPT(i 1, j) otherwise

min δ + −



δ + OPT(i, j − 1)

  
  

Compute for i = 0, 1, . . . , m and j = 0, 1, . . . , n O(mn) time

X: o c u r r a n c e

Y: o c c u r r e n c e

Yasushi Kawase Advanced Core in Algorithm Design 22 / 24

Example
δ = 2, αpq = 1 (for any distinct p, q)

o c u r r a n c e

o
c
c
u
r
r
e
n
c
e

Yasushi Kawase Advanced Core in Algorithm Design 23 / 24

Example
δ = 2, αpq = 1 (for any distinct p, q)

o c u r r a n c e
0 2 4 6 8 10 12 14 16 18
o 2 0 2 4 6 8 10 12 14 16
c 4 2 0 2 4 6 8 10 12 14
c 6 4 2 1 3 5 7 9 10 12
u 8 6 4 2 2 4 6 8 10 11
r 10 8 6 4 2 2 4 6 8 10
r 12 10 8 6 4 2 3 5 7 9
e 14 12 10 8 6 4 3 4 6 7
n 16 14 12 10 8 6 5 3 5 7
c 18 16 14 12 10 8 7 5 3 5
e 20 18 16 14 12 10 9 7 5 3

Yasushi Kawase Advanced Core in Algorithm Design 23 / 24

Quiz
What is the edit distance if δ = 3, αpq = 2 (for any distinct p, q)

o c u r r a n c e

o
c
c
u
r
r
e
n
c
e

Yasushi Kawase Advanced Core in Algorithm Design 24 / 24