程序代写代做代考 information retrieval chain algorithm compiler COMP90038 Algorithms and Complexity

COMP90038 Algorithms and Complexity

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

mailto:munoz.m@unimelb.edu.au

Recap

• Hashing is a standard way of implementing the abstract data type “dictionary”, a
collection of pairs.

• 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

• By concatenating the strings, we are basically multiplying by 32
• We use Horner’s rule to calculate the Hash:

STRING

KEY
KEY mod

101M 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

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
• Space efficient
• 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 , we now
have two variables

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
• the remaining capacity w ≤ 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

• 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

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

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.