Dynamic Programming 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 415 / 606
Weighted Interval Scheduling Problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 416 / 606
Reflecting on Divide and Conquer
The promise of divide and conquer
Many problems naturally decomposable into sub-problems Sub-problems have the same form as original problem Recursive solutions appear to solve the problem elegantly
Problem: Sometimes there is redundancy!
Same sub-problems instances re-occur frequently
Inefficient to repeatedly solve the same problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 417 / 606
Example: Syntactic Parsing
Checking valid syntax
Suppose that you need to check that a string is syntactically valid
Rules specify when a string is well-formed Various possible scenarios:
◮ checking syntax of a program
◮ analysing syntax of a natural language expression
◮ checking that user input is suitable
This is known as parsing
David Weir (U of Sussex) Program Analysis Term 1, 2015 418 / 606
Example Rules
1 2 3 4
The string has to be an S phrase
An S phrase is an S1 phrase followed by an S2 phrase An S1 phrase is an A phrase followed by a B phrase An S2 phrase is a C phrase followed by a D phrase
S
S1 ABCD
S2
David Weir (U of Sussex) Program Analysis Term 1, 2015 419 / 606
Applying Divide and Conquer
We must consider all ways of breaking the string in two
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 420 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1 S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1 S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Alternative Ways of Dividing up the Problem
S
S1
S2
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis
Term 1, 2015 421 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S
S2 ABCD
S1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S2 ABCD
S1
S
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Recurring Sub-Problems
S2 ABCD
S1
S
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
David Weir (U of Sussex) Program Analysis Term 1, 2015 422 / 606
Dynamic Programming Approach
Only solve each sub-problem once
Start by solving ‘smallest’ sub-problems and remember solutions
Using solutions to the small sub-problems solve slightly ‘bigger’ sub-problems
Systematically solve entire space of sub-problems, remembering solutions
Eventually the original problem will be solved
David Weir (U of Sussex) Program Analysis Term 1, 2015 423 / 606
Dynamic Programming Approach
For a specific problem, we need three things:
A way of decomposing problems into subproblems systematically
An efficiently index-able place to store solutions to sub-problems
A way of systematically enumerating sub-problems from smaller ones to larger ones
David Weir (U of Sussex) Program Analysis Term 1, 2015 424 / 606
Weighted Interval Scheduling
Suppose we have a set of weighted intervals: A = {α1,…,αn}
where w(α) is the weight of interval α.
Problem: Find a set of compatible intervals O where O ⊆ A that
maximises w(O) where
w(O) = w(α)
α∈O
In plain English:
The goal is to choose intervals from A that don’t overlap in time that gives the highest possible total weight
David Weir (U of Sussex) Program Analysis Term 1, 2015 425 / 606
Applying the Dynamic Programming Approach
Decomposing the problem
Consider sub-problems involving sub-part of entire time period Let the entire series of time stamps be t0, t1, . . . , tk
Let B(i) denote best solution for the time period t0 to ti
Finding B(i) involves finding the best among:
The best solution from 0 to time ti−1, i.e., B(i − 1)
A solution that includes α where f(α) = ti together with B(s(α))
Note the recursive nature of this definition
David Weir (U of Sussex) Program Analysis Term 1, 2015 426 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 427 / 606
Decomposing the Example
To find B(10) we need to choose the best from: the solution in B(9)
the solution that includes α8 and B(9)
the solution that includes α7 and B(7)
(Note that the same sub-problem has occured twice!)
To find B(9) we need to choose the best from: the solution B(8)
the solution that includes α6 and B(7) the solution include α5 and B(6)
David Weir (U of Sussex) Program Analysis Term 1, 2015 428 / 606
Tabulating Sub-solutions
For each i we need to compute B(i)
Store optimal solution for each B(i) in a table Index the table using i
The table has place to store the n solutions
B(0)
B(1)
…
B(n)
How can we systematically tackle each of the sub-problems?
David Weir (U of Sussex) Program Analysis Term 1, 2015 429 / 606
Controlling Exploration Problem Space
Top-down:
Start with B(10)
Recursively explore sub-problems that arise Eventually recursion bottoms out
— B(0) = {}
Build up solutions when returning from recursion
Store optimal solutions in table as they are found
When sub-problem arises look-up table to see if already solved
This is called Memoization
David Weir (U of Sussex) Program Analysis Term 1, 2015 430 / 606
Controlling Exploration of Problem Space
Bottom-up:
Start with B(0)
Then consider next biggest problem B(1), and so on
Finally B(10) is considered
Store optimal solutions as they are found
Guarantees that all sub-problems already solved when they are needed
Bottom-up is standard approach in Dynamic Programming
David Weir (U of Sussex) Program Analysis Term 1, 2015 431 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 432 / 606
Illustration of Approach
Here is the table:
i B(i) w(B(i))
0
1
2
3
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 433 / 606
Illustration of Approach
Initialize with solution to smallest problem
i B(i) w(B(i))
0
{}
0
1
2
3
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 434 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 435 / 606
Illustration of Approach
i = 1: no intervals end at t1 so B(1) = B(0)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
3
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 436 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 437 / 606
Illustration of Approach
i = 2: no intervals end at t2 so B(2) = B(1)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 438 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 439 / 606
Illustration of Approach
i = 3: no intervals end at t3 so B(3) = B(2)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 440 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 441 / 606
Illustration of Approach
i = 4: two intervals end at t4
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 442 / 606
Illustration of Approach
i = 4: α1 with B(0) better than α2 with B(2)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 443 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 444 / 606
Illustration of Approach
i = 5: no intervals end at t5 so B(5) = B(4)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 445 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 446 / 606
Illustration of Approach
i = 6: two intervals end at t6
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 447 / 606
Illustration of Approach
i = 6: α3 with B(3) better than α4 with B(5)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 448 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 449 / 606
Illustration of Approach
i = 7: no intervals end at t7 so B(7) = B(6)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 450 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 451 / 606
Illustration of Approach
i = 8: no intervals end at t8 so B(8) = B(7)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
{α3 }
9
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 452 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 453 / 606
Illustration of Approach
i = 9: two intervals end at t9
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
{α3 }
9
9
10
David Weir (U of Sussex) Program Analysis Term 1, 2015 454 / 606
Illustration of Approach
i = 9: α5 with B(6) better than α6 with B(7)
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
{α3 }
9
9
{α3, α5}
13
10
David Weir (U of Sussex)
Program Analysis Term 1, 2015 455 / 606
Example
α2
5
α3
2
9
α4
3
α5
α6 α7
4
3
3
α8
1
α1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 456 / 606
Illustration of Approach
i = 10: clearly α8 with B(9) is best solution
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
{α3 }
9
9
{α3, α5}
13
10
{α3, α5, α8}
14
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 457 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 458 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
B(1) = {α1}, B(2) = {α2}, B(3) = B(4) = B(5) = {α1, α3}, B(6) = {α2, α4}, B(7) = B(8) = {α1, α3, α5}, B(9) = {α1, α3, α5, α6}, B(10) = {α1, α8}
sum elements to get weight of each B(i)
David Weir (U of Sussex) Program Analysis Term 1, 2015 458 / 606
Removing dependency on Discrete Time Steps
As stated the algorithm iterates over each of the time steps
This does not always make sense
— how fine-grained should these steps be?
Determines running time of the algorithm
Alternative:
Iterate over interval end times ordered from earliest to latest Let A = (α1, . . . , αn) be the intervals ordered by end time One row in table for each interval αi
Number of iterations is equal to the number of intervals: n
David Weir (U of Sussex) Program Analysis Term 1, 2015 459 / 606
Revised Algorithm
Let A = (α1, . . . , αn) be the intervals ordered by end time
Let p(αi ) be the latest interval in sequence that ends no later than s(αi )
In order to complete row for αi choose the best of: Solution in row for αi−1
Solution involving αi and solution in row for p(αi) When no such interval p(αi ) then just consider w (αi )
David Weir (U of Sussex) Program Analysis Term 1, 2015 460 / 606
Using Interval Ending Times
i B(i) w(B(i))
0
{}
0
1
{}
0
2
{}
0
3
{}
0
4
{α1 }
5
5
{α1 }
5
6
{α3 }
9
7
{α3 }
9
8
{α3 }
9
9
{α3, α5}
13
10
{α3, α5, α8}
14
i
B(i) w(B(i))
f(α1)
{α1 }
5
f(α2)
{α1 }
5
f(α3)
{α3 }
9
f(α4)
{α3 }
9
f(α5)
{α3, α5}
13
f(α6)
{α3, α5}
13
f(α7)
{α3, α5}
13
f(α8)
{α3, α5, α8}
14
⇒
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 461 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 462 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
B(1) = {α1}, B(2) = {α2}, B(3) = {α1, α3}, B(4) = {α2, α4},
B(5) = {α1, α3, α5}, B(6) = {α1, α3, α5, α6}, B(6) = {α1, α3, α5, α7}, B(8) = {α1,α8}
sum elements to get weight of each B(i)
David Weir (U of Sussex) Program Analysis Term 1, 2015 462 / 606
Efficiency of Revised Weighted Interval Scheduling Algorithm
Suppose that A contains n intervals
n iterations, one for each row of the table
How long does it take to complete a row?
Need to consider each intervals that finishes at that time In total for all iterations is n
BUT…
David Weir (U of Sussex) Program Analysis Term 1, 2015 463 / 606
Deficiency is Algorithm
It takes time to complete entries in table Size of entries is O(n)
n entries to complete
Total running time O(n2)
We can avoid storing sets of intervals in each row
David Weir (U of Sussex) Program Analysis Term 1, 2015 464 / 606
Efficient Storage of Interval Sets
i B(i) w(B(i)) i ‘B(i)’ w(B(i))
f(α1)
{α1 }
5
f(α2)
{α1 }
5
f(α3)
{α3 }
9
f(α4)
{α3 }
9
f(α5)
{α3, α5}
13
f(α6)
{α3, α5}
13
f(α7)
{α3, α5}
13
f(α8)
{α3, α5, α8}
14
f(α1)
α1
5
f(α2)
α1
5
f(α3)
α3
9
f(α4)
α3
9
f(α5)
α5
13
f(α6)
α5
13
f(α7)
α5
13
f(α8)
α8
14
⇒
David Weir (U of Sussex) Program Analysis Term 1, 2015 465 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 466 / 606
Example for you
3
6
α3
α8
α4
5
α5
7
9
23
α6 α7
1
6
α1 α2
0 1 2 3 4 5 6 7 8 9 10 time →
B(1) = α1, B(2) = α2, B(3) = α3, B(4) = α4, B(5) = α5, B(6) = α6, B(6) = α7, B(8) = α8
Weights as for previous examples
David Weir (U of Sussex) Program Analysis Term 1, 2015 466 / 606
Recovering Optimal Interval Set
Recall A = (α1, . . . , αn) is ordered by interval end time
Recall p(αi ) is latest interval in sequence that ends no later than s(αi )
Finding elements of B(n): the optimal set of intervals Starting with row n traverse back in time
First look at entry in row n, finding say α
Find the next element in row for p(α) and repeat Finish at the beginning of time
Note, each probe into table produces one more element of B(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 467 / 606
A Last Look at Efficiency
n iterations of loop
One new interval considered on each iteration
Total of n intervals considered across all iterations Constant number of steps for each interval considered Total running time is Θ(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 468 / 606
Dynamic Programming: The Subset Sum Problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 469 / 606
Subset Sum Problem
A new scheduling problem:
Given a collection of requests that need to be scheduled A = {α1,…,αn}
Each request has a duration or non-negative weight: w(αi) Given total time available, i.e. total weight capacity: W
Possible solutions are subsets of the requests: S ⊆ A such that:
w(α) ≤ W α∈S
and w (α) is as large as possible α∈S
David Weir (U of Sussex)
Program Analysis Term 1, 2015 470 / 606
Potential Greedy Approaches
Consider requests in order of increasing weight: Include request if it fits within weight capacity
But what about A = {α1, α2, α3} where
W =10,w(α1)=1,w(α2)=5,w(α3)=5
Optimal solution is {α2, α3}
Consider requests in order of decreasing weight: Include request if it fits within weight capacity
But what about A = {α1, α2, α3} where
W =10,w(α1)=6,w(α2)=5,w(α3)=5
Optimal solution is {α2, α3}
David Weir (U of Sussex) Program Analysis Term 1, 2015 471 / 606
Space of Subproblems
Arrange requests in A in some fixed order (α1, . . . , αn) We will consider the space of subproblems: B(i,w) where
1≤i≤n
1≤w≤W
Choosing from among the requests {α1, . . . , αi } Total weight capacity is w
For overall problem we need to find: B(n, W ) Let w(αi) = wi for each i
Assume that each wi is a whole number
David Weir (U of Sussex) Program Analysis Term 1, 2015 472 / 606
Recursive Decomposition
Is αn in optimal solution B(n,w)?
Can’t be when wn > w
If it is then B(n,w) = wn + B(n − 1,w − wn) If not then B(n,w) = B(n − 1,w)
In general, find optimal solution to B(i,w) as follows: If wi > w then
B(i,w) = B(i − 1,w) Else
B(i,w)=max(wi +B(i−1,w−wi),B(i−1,w))
David Weir (U of Sussex) Program Analysis Term 1, 2015 473 / 606
Dynamic Programming Algorithm
SubsetSum(n, W ):
LetB(0,w)=0foreachw ∈{0,…,W} for i ← 1 to n
for w ← 0 to W
if w < wi then
B(i,w) ← B(i − 1,w) else
B(i,w)←max(wi +B(i−1,w−wi),B(i−1,w))
David Weir (U of Sussex) Program Analysis Term 1, 2015 474 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
475 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
476 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
477 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
478 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
479 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
480 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
481 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
482 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
483 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
484 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
485 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
486 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
4
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
487 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
4
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
488 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
489 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
490 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
491 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
492 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
493 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
494 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
495 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
496 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
497 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
7
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
498 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
7
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
499 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10 4
3
i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
500 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
501 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
502 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
503 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
8
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
504 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
8
9
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
505 / 606
Illustration
i w(αi) 14 22 35 44
0 1 2 3 4 5 6 7 8 9 10
4
3 i2 1 0
A = {α1,α2,α3,α4} W = 10
w
0
0
2
2
4
5
6
7
8
9
10
0
0
2
2
4
5
6
7
7
9
9
0
0
2
2
4
4
6
6
6
6
6
0
0
0
0
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
506 / 606
Dynamic Programming Algorithm
SubsetSum(n, W ):
LetB(0,w)=0foreachw ∈{0,...,W} for i ← 1 to n
for w ← 0 to W
if w < wi then
B(i,w) ← B(i − 1,w) else
B(i,w)←max(wi +B(i−1,w−wi),B(i−1,w))
David Weir (U of Sussex) Program Analysis Term 1, 2015 507 / 606
Running Time
Outer loop iterated n times
Inner loop iterated W times for each i Total iterations of inner loop is nW Running time of algorithm is Θ(nW )
David Weir (U of Sussex) Program Analysis Term 1, 2015 508 / 606
Example for You
i w(αi) 16 23 34 45
A = {α1,α2,α3,α4} W = 12
0 1 2 3 4 5 6 7 8 9 10
11 12
0
0
0
0
0
0
0
0
0
0
0
0
0
4
3 i2 1 0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
509 / 606
Example for You
i w(αi) 16 23 34 45
A = {α1,α2,α3,α4} W = 12
0 1 2 3 4 5 6 7 8 9 10
11 12
0
0
0
3
4
5
6
7
8
9
10
11
12
0
0
0
3
4
4
6
7
7
9
10
10
10
0
0
0
3
3
3
6
6
6
9
9
9
9
0
0
0
0
0
0
6
6
6
6
6
6
6
0
0
0
0
0
0
0
0
0
0
0
0
0
4
3 i2 1 0
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
509 / 606