程序代写代做代考 algorithm C chain graph COMP90038 – Algorithms and Complexity Lecture 18

COMP90038 – Algorithms and Complexity Lecture 18
COMP90038 Algorithms and Complexity
Lecture 18: Dynamic Programming
(with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274

COMP90038 – Algorithms and Complexity
Lecture 18
Review from Lecture 17: Hashing
• If we have a hash table of size m and keys are integers, we may define hn =nmodm.
• But keys may be other things, such as strings of characters, and the hash function should apply to these and still be easy (cheap) to compute.
• We need to choose 𝑚 so that it is large enough to allow efficient operations, without taking up excessive memory.
• The hash function should distribute keys evenly along the cells of the hash table.

COMP90038 – Algorithms and Complexity
Lecture 18
Review from Lecture 17: Hashing of Strings
𝑐h𝑎𝑟
𝑀
𝑌
𝐾
𝐸
𝑌
𝑠!
12
24
10
4
24
𝑏𝑖𝑛(𝑠! )
01100
11000
01010
00100
11000
𝑖
0
1
2
3
4
• Now concatenate the binary string:
𝑀 𝑌 𝐾 𝐸 𝑌 ⟼0110011000010100010011000 (=13379736)
13379736 mod 101 = 64
• So 64 is the position of string of string 𝑀 𝑌 𝐾 𝐸 𝑌 in the hash table.
• We deliberately chose m to be prime.
13379736=12×32! +24×32″ +10×32# +4×32$ +24×32%
• With m = 32, the hash value of any key is the last character’s value!

COMP90038 – Algorithms and Complexity
Lecture 18
Review from Lecture 17: Collision Handling
• Consider h 𝑘 = 𝑘 𝑚𝑜𝑑 7. Draw the resulting hash tables after inserting 19, 26,13,48,17 (in this order).
• Separate chaining
0123456
•Linearprobing 0 1 2 3 4 5 6
• Double hashing, using s 𝑘 = 5 − 𝑘 𝑚𝑜𝑑 5 offset 0123456
17
19 13 26 48
13
48
17
19
26
48
26
17
19
13

COMP90038 – Algorithms and Complexity
Lecture 18
Review from Lecture 17: Rabin-Karp String Search
• Repeatedly hashing strings of length 𝑚 seems like a bad idea. However, the hash values can be calculated incrementally. The hash value of the length-𝑚 substring 𝑠 that starts at position 𝑗 is:
$%&
h𝑎𝑠h𝑠,𝑗 =(𝑐h𝑟𝑠'(! ×𝑎$%!%&,
!”#
where a is the alphabet size. From that we we can get the next hash value, for the
starts at position 𝑗 + 1, quite cheaply:
h𝑎𝑠h 𝑠,𝑗+1 = h𝑎𝑠h 𝑠,𝑗 −𝑎$%&𝑐h𝑟(𝑠’) ×𝑎+𝑐h𝑟(𝑠'($)
modulo 𝑚.
• The first substring “the” = 𝑡 4 26 ) + h 4 26 + 𝑒
• If we have “the”, can we compute “her”?
“h𝑒𝑟”=h4 26 ) +𝑒4 26 +𝑟 =264 h4 26 +𝑒 +𝑟
=264 𝑡. 26)+h4 26 +𝑒−𝑡. 26) +𝑟 =264 “𝑡h𝑒”−𝑡. 26 ) +𝑟
substring that

COMP90038 – Algorithms and Complexity
Lecture 18
Dynamic Programming
•
•
• •
Dynamic programming is an algorithm design technique that is sometimes applicable when we want to solve a recurrence relation and the recursion involves overlapping instances.
In Lecture 16 we achieved a spectacular performance improvement in the calculation of Fibonacci numbers by switching from a naïve top-down algorithm to one that solved, and tabulated, smaller sub-problems.
The bottom-up approach used the tabulated results, rather than solving overlapping sub-problems repeatedly.
That was a particularly simple example of dynamic programming.

COMP90038 – Algorithms and Complexity Lecture 18
Review from Lecture 16: Fibonacci Numbers with Tabulation
• We assume that, from the outset, all entries of the table 𝐹 are 0.
Initial
𝐹 = 0,0,⋯,0
𝑛=2
result=FIB(1)+FIB(0) =1+1=2
𝐹 = 0,0,2,0,⋯,0
𝑛=2
result=FIB(2)+FIB(1) =2+1=3
𝐹 = 0,0,2,3,0, ⋯ , 0
𝑛=4
result=FIB(3)+FIB(2) =3+2=5
𝐹 = 0,0,2,3,5,0, ⋯ , 0
• 𝐹[0, ⋯,n] is an array that stores partial results, initialised to 0.
• Base cases FIB(0) = 1 & FIB(1) = 1.

COMP90038 – Algorithms and Complexity
Lecture 18
Dynamic Programming and Optimisation
•
Optimisation problems sometimes allow for clever dynamic programming solutions.
– the objective is to find the best possible combination: the one with the lowest cost, or higher profit, subject to some constraints.
For dynamic programming to be useful, the optimality principle must hold:
– An optimal solution to a problem is composed of optimal solutions to its subproblems.
While not always, this principle often holds.
•
•

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Given a row of coins, pick the largest possible sum, subject to this constraint: no two adjacent coins can be picked.
• Think of the problem recursively.
• Let the values of the coins be 𝑣$, 𝑣#, ⋯, 𝑣&.
• Let 𝑆(𝑖) be the sum that can be gotten by picking optimally from the first 𝑖 coins.
• Either the 𝑖th coin (with value 𝑣’) is part of the solution or it is not.
• If we choose to pick the 𝑖th coin, we cannot also pick its neighbour on the left, so the best we can achieve is S(𝑖 − 2) + 𝑣’.
• Otherwise we can leave it, and the best we can achieve is S(𝑖 − 1).

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• We can say the same thing formally, as a recurrence relation: 𝑆𝑖 =𝑚𝑎𝑥𝑆𝑖−1,𝑆𝑖−2 +𝑣’
• This holds for 𝑖 > 1.
• We need two base cases: S(0) = 0 and S(1) = 𝑣$.
• You can code this algorithm directly like that in your favourite programming language.
• However, the solutions suffers the same problem as the naïve Fibonacci program: lots of repetition of identical sub-computations.

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Since all values S(1) to S(n) need to be found anyway, we may as well proceed from the bottom up, storing intermediate results in an array S as we go.
• Given an array C that holds the coin values, the recurrence relation tells us what to do:

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=0 •𝑆0=0
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=1
• 𝑆1=20
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=2
• 𝑆2 =𝑚𝑎𝑥 𝑆1 =20, 𝑆0 +10=0+10 =20
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=3
• 𝑆3 =𝑚𝑎𝑥 𝑆2 =20, 𝑆1 +20=20+20 =40
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=4
• 𝑆4 =𝑚𝑎𝑥 𝑆3 =40, 𝑆2 +50=20+50 =70
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40
70

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=5
• 𝑆5 =𝑚𝑎𝑥 𝑆4 =70, 𝑆3 +20=40+20 =70
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40
70
70

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=6
• 𝑆6 =𝑚𝑎𝑥 𝑆5 =70, 𝑆4 +10=70+10 =80
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40
70
70
80

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
• 𝑖=7
• 𝑆7 =𝑚𝑎𝑥 𝑆6 =80, 𝑆5 +20=70+20 =90
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40
70
70
80
90

COMP90038 – Algorithms and Complexity
Lecture 18
Example 1: The Coin-Row Problem
• Let us run the algorithm on the seven coins 20, 10, 20, 50, 20, 10, 20:
index
0
1
2
3
4
5
6
7
C
20
10
20
50
20
10
20
S
0
20
20
40
70
70
80
90
Using
1
1
1
1
1
1
1
3
4
4
4
4
6
7
• Keeping trach of the (indices of the) coins used in an optimal solution is an easy extension to the algorithm.

COMP90038 – Algorithms and Complexity
Lecture 18
Example 2: The Knapsack Problem
• In Lecture 5 we looked at the knapsack problem.
• Given n items with
– weights:𝑤$,𝑤#,⋯,𝑤& – values:𝑣$,𝑣#,⋯,𝑣&
– knapsack of weight capacity W.
• Find the most valuable selection of items that will fit in the knapsack.
• We assume that all entities involved are positive integers.

COMP90038 – Algorithms and Complexity
Lecture 18
Example 2: The Knapsack Problem

COMP90038 – Algorithms and Complexity
Lecture 18
Example 2: The Knapsack Problem
• We previously devised a brute-force algorithm, but dynamic programming may give is a better solution.
• The critical step is to find a good answer to the question “what is the sub-problem?”
• In this case, the trick is to formulate the recurrence relation over two parameters, namely the sequence 1, 2, ⋯, 𝑖 of item considered so far, and the remaining capacity 𝑤 ≤ 𝑊.

COMP90038 – Algorithms and Complexity
Lecture 18
Example 2: The Knapsack Problem
• The reason we focus on 𝐾(𝑖, 𝑤) is that we can express a solution to that recursively.
• Amongst the first 𝑖 items we either pick item 𝑖 or we don’t.
• For a solution that excludes the item 𝑖, the value of an optimal subset is simply K(𝑖 − 1, 𝑤).
• For a solution that includes item 𝑖, apart from that item, an optimal solution contains an optimal subset of the first 𝑖 − 1 items that will fit into a bag of capacity w − 𝑤’. The value of such a subset is 𝐾(𝑖 − 1, 𝑤 − 𝑤’) + 𝑣’.

COMP90038 – Algorithms and Complexity
Lecture 18
Example 2: The Knapsack Problem
• Now it is easy to express the solution recursively:
𝐾 𝑖, 𝑤 = 0 if 𝑖 = 0 or w = 0
• Otherwise:
𝐾 𝑖,𝑤 = S 𝑚𝑎𝑥 𝐾 𝑖−1,𝑤 ,𝐾 𝑖−1,𝑤−𝑤’ +𝑣’ if 𝑤−𝑤’ ≥0 𝐾 𝑖−1,𝑤 if 𝑤−𝑤’<0 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Now it is easy to express the solution recursively: 𝐾 𝑖, 𝑤 = 0 if 𝑖 = 0 or w = 0 • Otherwise: 𝐾 𝑖,𝑤 = S 𝑚𝑎𝑥 𝐾 𝑖−1,𝑤 ,𝐾 𝑖−1,𝑤−𝑤' +𝑣' if 𝑤≥𝑤' 𝐾 𝑖 − 1, 𝑤 if 𝑤 < 𝑤' COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Now it is easy to express the solution recursively: 𝐾 𝑖, 𝑤 = 0 if 𝑖 = 0 or w = 0 • Otherwise: 𝐾 𝑖,𝑤 = S 𝑚𝑎𝑥 𝐾 𝑖−1,𝑤 ,𝐾 𝑖−1,𝑤−𝑤' +𝑣' if 𝑤≥𝑤' 𝐾 𝑖 − 1, 𝑤 if 𝑤 < 𝑤' • That gives a correct algorithm for the problem, albeit an inefficient one, if we take it literally. • For a bottom-up solution we need to write the code that systematically fills a two- dimensional table. • Thetablewillhave𝑛+1rowsand𝑊+1columns. COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • First fill the leftmost column and top row, then proceed row by row: • The algorithm has time (and space) complexity Θ 𝑛𝑊 . COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Here is a concrete example—like before, expect let 𝑊 = 8. 𝑖\j 0 1 2 3 4 5 6 7 8 0 1 2 3 4 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Here is a concrete example—like before, expect let 𝑊 = 8. 𝑖\j 0 1 2 3 4 5 6 7 8 0 1 2 3 4 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • On the first for loop: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 1 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • On the second for loop: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Now we advance row by row: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Is the current capacity (j=1) sufficient to fit the first item (i=1)? 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 ? 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • We won’t have enough capacity until j=7: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=1 • j=7 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • We won’t have enough capacity until j=7: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=1 • j=7 • K[1−1,7]=K 0,7 =0 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • We won’t have enough capacity until j=7: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=1 • j=7 • K[1−1,7]=K 0,7 =0 • K 1−1,7−7 +42=K 0,0 +42=0+42=42 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • We won’t have enough capacity until j=7: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=1 • j=7 • K[1−1,7]=K 0,7 =0 • K 1−1,7−7 +42=K 0,0 +42=0+42=42 • K1,7 =max0,42 =42 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • There are no more items to pack, then K 1,8 = K 1,7 : 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=1 • j=8 • K[1−1,8]=K 0,8 =0 • K 1−1,8−7 +42=K 0,1 +42=0+42=42 • K1,8 =max0,42 =42 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Next row, we won’t have enough capacity until j = 3: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 0 0 12 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=2 • j=3 • K[2−1,3]=K 1,3 =0 • K 2−1,3−3 +12=K 1,0 +12=0+12=12 • K2,3 =max0,12 =12 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • At j = 7, it is better to pick 42: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 0 0 12 12 12 12 42 3 0 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=2 • j=7 • K[2 − 1,7]=K 1,7 • K 2−1,7−3 +12=K 1,4 +12=0+12=12 • K2,7 =max42,12 =42 = 42 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • Next row, at j = 4, it is better to pick 40: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 0 0 12 12 12 12 42 42 3 0 0 0 12 40 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=3 • j=4 • K[3 − 1,4]=K 2,4 • K 3−1,4−4 +40=K 2,0 +40=0+40=40 • K3,4 =max12,40 =40 = 12 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • What happens at j = 7? 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 0 0 12 12 12 12 42 42 3 0 0 0 12 40 40 40 52 4 0 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=3 • j=7 • K[3 − 1,7]=K 2,7 • K 3−1,7−4 +40=K 2,3 +40=12+40=52 • K3,7 =max42,52 =52 = 42 COMP90038 – Algorithms and Complexity Lecture 18 Example 2: The Knapsack Problem • At the end, the best solution found is K[4,8]=52: 𝑖\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 42 42 2 0 0 0 12 12 12 12 42 42 3 0 0 0 12 40 40 40 52 52 4 0 0 0 12 40 40 40 52 52 𝑣" = 42 𝑣# = 12 𝑣$ = 40 𝑣% = 25 𝑤" = 7 𝑤# = 3 𝑤$ = 4 𝑤% = 5 • i=4 • j=8 • K[4 − 1,8]=K 3,8 • K 4−1,8−5 +25=K 3,3 +25=12+25=37 • K4,8 =max52,37 =52 = 52 COMP90038 – Algorithms and Complexity Lecture 18 Solving the Knapsack Problem with MEmoing • To some extent the bottom-up (table-filling) solution is overkill: it finds the solution to every conceivable sub-instance. • Most of the table entries cannot actually contribute to a solution. For a clearer example of this, let all the weights in the problem be multiplied by 1000. • In this situation, a top-down approach, with memoing, is preferable. • To keep the memo table small, make it a hash table. COMP90038 – Algorithms and Complexity Lecture 18 Solving the Knapsack Problem with Memoing • The hash table uses keys 𝑖, 𝑗 . These are stored together with their corresponding valuesk=K 𝑖,𝑗 . COMP90038 – Algorithms and Complexity Lecture 18 Coming Up Next • We apply dynamic programming to two graph problems (transitive closure and all- pairs shortest-paths); the resulting algorithms are known as Warshall’s and Floyd’s.

Related Posts