程序代写代做代考 algorithm Dynamic Programming 1

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