COMP90038 Algorithms and Complexity
Lecture 18: Dynamic Programming
(with thanks to Harald Søndergaard & Michael Kirley)
Andres Munoz-Acosta
munoz.m@unimelb.edu.au
Peter Hall Building G.83
Recap
• Hashing is a standard way of implementing the abstract data type “dictionary”, a collection of
• A key k identifies each record, and should map efficiently to a positive integer. The set K of keys can be unbounded.
• The hash address is calculated through a hash function h(k), which points to a location in a hash table.
• Two different keys could have the same address (a collision).
• The challenges in implementing a hash table are:
• Design a robust hash function
• Handling of same addresses (collisions) for different key values
Hash Functions
• The hash function:
• Must be easy (cheap) to compute.
• Ideally distribute keys evenly across the hash table.
• Three examples:
• Integer: h(n) = n mod m.
• Strings: sum of integers or concatenation of binaries
Concatenation of binaries
• Assume a binary representation of the 26 characters
• We need 5 bits per character (0 to 31)
• Instead of adding, we concatenate the binary strings
• Our hash table is of size 101 (m is prime)
• Our key will be ‘MYKEY’
char
a
bin(a)
char
a
bin(a)
char
a
bin(a)
A
0
00000
J
9
01001
S
18
10010
B
1
00001
K
10
01010
T
19
10011
C
2
00010
L
11
01011
U
20
10100
D
3
00011
M
12
01100
V
21
10101
E
4
00100
N
13
01101
W
22
10110
F
5
00101
O
14
01110
X
23
10111
G
6
00110
P
15
01111
Y
24
11000
H
7
00111
Q
16
10000
Z
25
11001
I
8
01000
R
17
10001
Concatenating binaries
STRING
KEY
KEY mod 101
M
Y
K
E
Y
int
12
24
10
4
24
bin(int)
01100
11000
01010
00100
11000
Index
4
3
2
1
0
32^(index)
1048576
32768
1024
32
1
a*(32^index)
12582912
786432
10240
128
24
13379736
64
• By concatenating the strings, we are basically multiplying by 32 • We use Horner’s rule to calculate the Hash:
Handling Collisions
• Two main types:
• Separate Chaining
• Compared with sequential search, it reduces the number of comparisons by a factor of m
• Good for dynamic environments
• Deletion is easy
• Uses more storage
• Linear probing
• Spaceefficient
• Worst case performance is poor
• It may lead to clusters of contiguous cells in the table being occupied
• Deletion is almost impossible
Double Hashing
• Double hashing uses a second hash function s to determine an offset to be used in probing for a free cell.
• It is used to alleviate the clustering problem in linear probing.
• For example, we may choose s(k) = 1 + k mod 97.
• By this we mean, if h(k) is occupied, next try h(k) + s(k), then h(k) + 2s(k), and so on.
• This is another reason why it is good to have m being a prime number. That way, using h(k) as the offset, we will eventually find a free cell if there is one.
Rehashing
• The standard approach to avoiding performance deterioration in hashing is to keep track of the load factor and to rehash when it reaches, say, 0.9.
• Rehashing means allocating a larger hash table (typically about twice the current size), revisiting each item, calculating its hash address in the new table, and inserting it.
• This “stop-the-world” operation will introduce long delays at unpredictable times, but it will happen relatively infrequently.
An exam question type
• With the hash function h(k) = k mod 7. Draw the hash table that results after inserting in the given order, the following values
[19 26 13 48 17]
• When collisions are handled by: • separate chaining
• linear probing
• double hashing using h’(k) = 5 – (k mod 5)
• Which are the hash addresses?
Solution
Index
0
1
2
3
4
5
6
Separate Chaining
17
19
13
26
48
Linear Probing
13
48
17
19
26
Double Hashing
48
26
17
19
13
Rabin-Karp String Search
• The Rabin-Karp string search algorithm is based on string hashing.
• To search for a string p (of length m) in a larger string s, we can calculate hash(p) and then check every substring si … si+m-1 to see if it has the same hash value. Of course, if it has, the strings may still be different; so we need to compare them in the usual way.
• If p = si … si+m-1 then the hash values are the same; otherwise the values are almost certainly going to be different.
• Since false positives will be so rare, the O(m) time it takes to actually compare the strings can be ignored.
Rabin-Karp String Search
• Repeatedly hashing strings of length m seems like a bad idea. However, the hash values can be calculated incrementally. The hash value of the length-m substring of s that starts at position j is:
• where a is the alphabet size. From that we can get the next hash value, for the substring that starts at position j+1, quite cheaply:
• modulo m. Effectively we just subtract the contribution of sj and add the contribution of sj+m, for the cost of two multiplications, one addition and one subtraction.
An example
• The data ‘31415926535’
• The hash function h(k) = k mod 11 • The pattern ’26’
STRING
3
1
4
1
5
9
2
6
5
3
5
31 MOD 11
9
14 MOD 11
3
41 MOD 11
8
15 MOD 11
4
59 MOD 11
4
92 MOD 11
4
26 MOD 11
4
Why Not Always Use Hashing?
• Some drawbacks:
• If an application calls for traversal of all items in sorted order, a hash table is
no good.
• Also, unless we use separate chaining, deletion is virtually impossible.
• It may be hard to predict the volume of data, and rehashing is an expensive “stop-the-world” operation.
When to Use Hashing?
• All sorts of information retrieval applications involving thousands to millions of keys.
• Typical example: Symbol tables used by compilers. The compiler hashes all (variable, function, etc.) names and stores information related to each – no deletion in this case.
• When hashing is applicable, it is usually superior; a well-tuned hash table will outperform its competitors.
• Unless you let the load factor get too high, or you botch up the hash function. It is a good idea to print statistics to check that the function really does spread keys uniformly across the hash table.
Dynamic programming
• Dynamic programming is a bottom-up problem solving technique. The idea is to divide the problem into smaller, overlapping ones. The results are tabulated and used to find the complete solution.
• An example is the approach that used tabulated results to find the Fibonacci numbers: • Note that:
• F[0…n] is an array that stores partial results, initialized to zero
• If F[n]=0, then this partial result has not been calculated, hence the recursion is calculated
• If F[n]≠0, then this value is used.
Dynamic programming and Optimization
• Dynamic programming is often used on Optimization problems.
• The objective is to find the solution with the lowest cost or highest profit.
• For dynamic programming to be useful, the optimality principle must be true:
• An optimal solution to a problem is composed of optimal solutions to its subproblems.
• While not always true, this principle holds more often than not.
Dynamic programming vs. Divide-and- Conquer
• While the two techniques divide the problem into smaller ones, there is a basic difference:
• In D&C, the sub-problems are independent of each other, while in DP the problems are dependent.
• Because of the dependencies, in DP we memorize the solutions to the sub- problems in order to be re-used. That does not happen in D&C.
• Think about MergeSort for a moment. Do you keep the solution from one branch to be re-used in another?
The coin row problem
• You are shown a group of coins of different denominations ordered in a row.
• You can keep some of them, as long as you do not pick two adjacent ones.
• Your objective is to maximize your profit , i.e., you want to take the largest amount of money.
• This type of problems are called combinatorial, as we are trying to find the best possible combination subject to some constraints
The coin row problem
• Let’s visualize the problem. Our coins are [20 10 20 50 20 10 20]
The coin row problem
• We cannot take these two.
• It does not fulfil our constraint (We cannot pick adjacent coins)
The coin row problem
• We could take all the 20s (Total of 80).
• Is that the maximum profit? Is this a greedy solution?
The coin row problem
• Can we think of a recursion that help us solve this problem? What is the smallest problem possible?
• If instead of a row of seven coins we only had one coin
• We have only one choice.
• What about if we had a row of two? • We either pick the first or second coin.
The coin row problem
• If we have a row of three, we can pick the middle coin or the two in the sides. Which one is the optimal?
The coin row problem
• If we had a row of four, there are sixteen combinations
• For simplicity, I will represent these combinations as binary strings:
• ‘0’ = leave the coin • ‘1’ = pick the coin
• Eight of them are not valid (in optimization lingo unfeasible), one has the worst profit (0)
• Picking one coin will always lead to lower profit (in optimization lingo suboptimal)
0
0000
PICK NOTHING (NO PROFIT)
1
0001
SUBOPTIMAL
2
0010
SUBOPTIMAL
3
0011
UNFEASIBLE
4
0100
SUBOPTIMAL
5
0101
6
0110
UNFEASIBLE
7
0111
UNFEASIBLE
8
1000
SUBOPTIMAL
9
1001
10
1010
11
1011
UNFEASIBLE
12
1100
UNFEASIBLE
13
1101
UNFEASIBLE
14
1110
UNFEASIBLE
15
1111
UNFEASIBLE
The coin row problem
• Let’s give the coins their values [c1 c2 c3 c4], and focus on the feasible combinations:
• Our choice is to pick two coins [c1 0 c3 0] [0 c2 0 c4] [c1 0 0 c4]
• If the coins arrived in sequence, by the time that we reach c4, the best that we
can do is either:
• Take a solution at step 3 [c1 0 c3 0]
• Add to one of the solutions at step 2 the new coin: [0 c2 0 c4] [c1 0 0 c4]
• Generally, we can express this as the recurrence:
The coin row problem
• Given that we have to backtrack to S(0) and S(1), we store these results in an array.
• Then the algorithm is:
The coin row problem
• Lets run our algorithm in the example. Step 0.
• S[0] = 0.
The coin row problem
• Step 1
• S[1] = 20
The coin row problem
• Step 2
• S[2] = max(S[1] = 20, S[0] + 10 = 0 + 10) = 20
The coin row problem
• Step 3
• S[3] = max(S[2] = 20, S[1] + 20 = 20 + 20 = 40) = 40
The coin row problem
• Step 4
• S[4] = max(S[3] = 40, S[2] + 50 = 20 + 50 = 70) = 70
The coin row problem
• At step 5, we can pick between: • S[4] = 70
• S[3] + 20 = 60
• At step 6, we can pick between: • S[5] = 70
• S[4] + 10 = 80
• At step 7, we can pick between: • S[6] = 80
• S[5] + 20 = 90
1
2
3
4
5
6
7
0
20
10
20
50
20
10
20
STEP 0
0
STEP 1
0
20
STEP 2
0
20
20
STEP 3
0
20
20
40
STEP 4
0
20
20
40
70
STEP 5
0
20
20
40
70
70
STEP 6
0
20
20
40
70
70
80
STEP 7
0
20
20
40
70
70
80
90
SOLUTION
1
1
1
1
1
1
1
3
4
4
4
4
6
7
Two insights
• In a sense, dynamic programming allows us to take a step back, such that we pick the best solution considering newly arrived information.
• If we used a brute-force approach such as exhaustive search for this problem:
• We had to test 33 feasible combinations. • Instead we tested 5 combinations.
The knapsack problem
• You previously encountered the knapsack problem:
• Given a list of n items with: • Weights{w1,w2,…,wn}
• Values{v1,v2,…,vn}
• and a knapsack (container) of capacity W
• Find the combination of items with the highest value that would fit into the knapsack
• All values are positive integers
The knapsack problem
• This is another combinatorial optimization problem:
• In both the coin row and knapsack problems, we are maximizing profit
• Unlike the coin row problem which had one variable
The knapsack problem
• The critical step is to find a good answer to the question: what is the smallest version of the problem that I could solve first?
• Imagine that I have a knapsack of capacity 1, and an item of weight 2. Does it fit? • What if the capacity was 2 and the weight 1. Does it fit? Do I have capacity left?
• Given that we have two variables, the recurrence relation is formulated over two parameters:
• the sequence of items considered so far {1, 2, … i}, and • theremainingcapacityw≤W.
• Let K(i,w) be the value of the best choice of items amongst the first i using knapsack capacity w.
• Then we are after K(n,W).
The knapsack problem
• By focusing on K(i,w) we can express a recursive solution. • Once a new item i arrives, we can either pick it or not.
• Excluding i means that the solution is K(i-1,w), that is, which items were selected before i arrived with the same knapsack capacity.
• Including i means that the solution also includes the subset of previous items that will fit into a bag of capacity w-wi ≥ 0, i.e., K(i-1,w-wi) + vi.
The knapsack problem
• Let us express this as a recursive function. • First the base state:
• Otherwise:
The knapsack problem
• That gives a correct, although inefficient, algorithm for the problem.
• For a bottom-up solution we need to write the code that systematically fills a two- dimensional table of n+1 rows and W+1 columns.
• The algorithm has both time and space complexity of O(nW)
The knapsack problem
• Lets look at the algorithm, step-by-step.
• The data is:
• The knapsack capacity W = 8
• The values are {42, 12, 40, 25} • The weights are {7, 3, 4, 5}
The knapsack problem
• On the first for loop:
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
42
7
1
0
12
3
2
0
40
4
3
0
25
5
4
0
The knapsack problem
• On the second for loop:
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
12
3
2
0
40
4
3
0
25
5
4
0
The knapsack problem
• Now we advance row by row:
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
12
3
2
0
40
4
3
0
25
5
4
0
The knapsack problem
• Is the current capacity (j=1) sufficient?
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
?
12
3
2
0
40
4
3
0
25
5
4
0
The knapsack problem
• We won’t have enough capacity until j=7
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
0
0
0
0
0
0
42
42
12
3
2
0
40
4
3
0
25
5
4
0
• 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
The knapsack problem
• Next row. We won’t have enough capacity until j=3
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
0
0
0
0
0
0
42
42
12
3
2
0
0
0
12
40
4
3
0
25
5
4
0
• i= 2
• j= 3
• K[2-1,3]=K[1,3]=0
• K[2-1,3-3] + 12 = K[1,0] + 12 = 0 + 12 = 42
The knapsack problem
• But at j=7, it is better to pick 42
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
0
0
0
0
0
0
42
42
12
3
2
0
0
0
12
12
12
12
42
40
4
3
0
25
5
4
0
• i= 2
• j= 7
• K[2-1,7]=K[1,7]=42
• K[2-1,7-3] + 12 = K[1,4] + 12 = 0 + 12 = 12
The knapsack problem
• Next row: at j=4, it is better to pick 40
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
0
0
0
0
0
0
42
42
12
3
2
0
0
0
12
12
12
12
42
42
40
4
3
0
0
0
12
40
25
5
4
0
• i= 3
• j= 4
• K[3-1,4]=K[2,4]=12
• K[3-1,4-4] + 40 = K[2,0] + 40 = 0 + 40 = 40
The knapsack problem
• What would happen at j=7? • Can you complete the table?
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
0
0
0
0
0
0
42
42
12
3
2
0
0
0
12
12
12
12
42
42
40
4
3
0
0
0
12
40
40
40
52
52
25
5
4
0
0
0
12
40
40
40
52
52
• i= 3
• j= 7
• K[3-1,7] = K[2,7] = 42
• K[3-1,7-4] + 40 = K[2,3] + 40 = 12 + 40 = 52
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 which are
unnecessary
• In this situation, a top-down approach, with memoing, is preferable. • There are many implementations of the memo table.
• We will examine a simple array type implementation.
The knapsack problem
• Lets look at this algorithm, step- by-step
• The data is:
• The knapsack capacity W = 8 • The values are {42, 12, 40, 25} • The weights are {7, 3, 4, 5}
• F is initialized to all -1, with the exceptions of i=0 and j=0, which are initialized to 0.
The knapsack problem
• We start with i=4 and j=8
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
-1
-1
-1
-1
-1
-1
-1
-1
12
3
2
0
-1
-1
-1
-1
-1
-1
-1
-1
40
4
3
0
-1
-1
-1
-1
-1
-1
-1
-1
25
5
4
0
-1
-1
-1
-1
-1
-1
-1
-1
• i= 4
• j= 8
• K[4-1,8]=K[3,8]
• K[4-1,8-5] + 25 = K[3,3] + 25
The knapsack problem
• Next is i=3 and j=8
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
-1
-1
-1
-1
-1
-1
-1
-1
12
3
2
0
-1
-1
-1
-1
-1
-1
-1
-1
40
4
3
0
-1
-1
-1
-1
-1
-1
-1
-1
25
5
4
0
-1
-1
-1
-1
-1
-1
-1
-1
• i= 3
• j= 8
• K[3-1,8]=K[2,8]
• K[3-1,8-4] + 40 = K[2,4] + 40
The knapsack problem
• Next is i=2 and j=8
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
-1
-1
-1
-1
-1
-1
-1
-1
12
3
2
0
-1
-1
-1
-1
-1
-1
-1
-1
40
4
3
0
-1
-1
-1
-1
-1
-1
-1
-1
25
5
4
0
-1
-1
-1
-1
-1
-1
-1
-1
• i= 2
• j= 8
• K[2-1,8]=K[1,8]
• K[2-1,8-3] + 12 = K[1,5] + 12
The knapsack problem
• Next is i=1 and j=8
• Here we reach the bottom of this recursion
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
-1
-1
-1
-1
-1
-1
-1
42
12
3
2
0
-1
-1
-1
-1
-1
-1
-1
-1
40
4
3
0
-1
-1
-1
-1
-1
-1
-1
-1
25
5
4
0
-1
-1
-1
-1
-1
-1
-1
-1
• 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
The knapsack problem
• Next is i=1 and j=5.
• As before, we also reach the bottom of this branch.
j
0
1
2
3
4
5
6
7
8
v
w
i
0
0
0
0
0
0
0
0
0
0
42
7
1
0
-1
-1
-1
-1
0
-1
-1
42
12
3
2
0
-1
-1
-1
-1
-1
-1
-1
-1
40
4
3
0
-1
-1
-1
-1
-1
-1
-1
-1
25
5
4
0
-1
-1
-1
-1
-1
-1
-1
-1
• i= 1
• j= 5
• K[1-1,5] = K[0,5] = 0
• j – w[1] = 5-8 < 1 → return 0
The knapsack problem
• We can trace the complete algorithm, until we find our solution.
• The states visited (18) are shown in the table.
• Unlike the bottom-up approach, in which we visited all the
states (40).
• Given that there are a lot of places in the table never used, the algorithm is less space-efficient.
• You may use a hash table to improve space efficiency.
i
j
value
0
8
0
0
1
0
1
8
42
0
5
0
1
5
0
2
8
42
0
4
0
1
4
0
0
1
0
1
1
0
2
4
12
3
8
52
0
3
0
1
3
0
1
0
0
2
3
12
3
3
12
4
8
52
A practice challenge
• Can you solve the problem in the figure?
• W = 15
• w = [1 1 2 4 12]
• v = [1 2 2 10 4]
• FYI the answer is $15/15Kg
Next lecture
• 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.