MH3400 tut5 solutions PDF

Preview

Summary

MH3400 Algorithms for the Real World AY 2020/ Thomas PeyrinTutorials (week 5) LetS={a, b, c, d, e, f, g}be a collection of objects with benefit-weight values,a: (12,4),b: (10,6), c: (8,5),d: (11,7),e: (14,3),f : (7,1),g: (9,6). What is an optimal solution to the fractional knapsack problem forSassum...

Description

MH3400 Algorithms for the Real World Thomas Peyrin

AY 2020/2021

Tutorials (week 5)

1. Let S = {a, b, c, d, e, f, g} be a collection of objects with benefit-weight values, a : (12, 4), b : (10, 6), c : (8, 5), d : (11, 7), e : (14, 3), f : (7, 1), g : (9, 6). What is an optimal solution to the fractional knapsack problem for S assuming we have a sack that can hold objects with total weight 18 ? Show your work. Solution: First, compute the benefit/weight ratio for each object: a : 3, b : 1.67, c : 1.6, d : 1.57, e : 4.67, f : 7, g : 1.5. Them sort them decreasingly according to that ratio: f : 7, e : 4.67, a : 3, b : 1.67, c : 1.6, d : 1.57, g : 1.5. As greedy choice, you would pick first the object with the highest ratio, that is f , which leaves a weight of 18 − 1 = 17. Then, we would pick the second-highest ratio, that is e, which leaves a weight of 17−3 = 14. Then, we would pick the third-highest ratio, that is a, which leaves a weight of 14−4 = 10. Then, we would pick the fourth-highest ratio, that is b, which leaves a weight of 10 − 6 = 4. Then, we would pick the fifth-highest ratio, that is c, but we only have 4 of weight remaining, so we can only take 4 of it, while 5 was originally available. At this point, the bag is full and we have a total value of 7 + 14 + 12 + 10 + 8 ∗ (4/5) = 49.4. 2. Suppose we are given a set of tasks specified by pairs of the start times and finish times as T = {(1, 2), (1, 3), (1, 4), (2, 5), (3, 7), (4, 9), (5, 6), (6, 8), (7, 9)}. Solve the task scheduling problem for this set of tasks. Solution: As greedy algorithm, we will consider the tasks one a time, ordered by start time. We assign a new task to any empty machine, and if none is available we create a new one. We first assign a machine M1 for task (1, 2), one machine M2 for task (1, 3), and one machine M3 for task (1, 4). Then, task (2, 5) is sent to M1 , task (3,7) is sent to M2 and task (4, 9) is sent to M3 . Finally, tasks (5, 6) and (6,8) are sent to M1 , and task (7, 9) is sent to M2 . Thus, the minimum number of machines required for this task schedule is 3. 3. Draw the frequency table and Huffman tree for the following string: "dogs do not spot hot pots or cats"

Solution: The frequency table is as follows: space character: 7 o: 7 t: 5 s: 4 d: 2 p: 2 1

a: c: g: h: n: r:

1 1 1 1 1 1

A possible resulting tree for that frequency table would looks like:

4. What is the best way to multiply a chain of matrices with dimensions that are 10 × 5, 5 × 2, 2 × 20, 20 × 12 and 12 × 4 ? Show your work. Solution: We apply the MatrixChain algorithm with input sequence d 0 = 10, d 1 = 5, d 2 = 2,d 3 = 20, d 4 = 12, d 5 = 4. First, we initialise all the Ni,i value to 0 for i ∈ [0, 4], that is: N0,0 = N1,1 = N2,2 = N3,3 = N4,4 = 0. Then, we will compute the following values: N0,1 = N0,0 + N1,1 + d 0 d 1 d 2 = 100 N1,2 = N1,1 + N2,2 + d 1 d 2 d 3 = 200 N2,3 = N2,2 + N3,3 + d 2 d 3 d 4 = 480 N3,4 = N3,3 + N4,4 + d 3 d 4 d 5 = 960

2

N0,2 = min{N0,0 + N1,2 + d 0 d 1 d 3 , N0,1 + N2,2 + d 0 d 2 d 3 } = 500 N1,3 = min{N1,1 + N2,3 + d 1 d 2 d 4 , N1,2 + N3,3 + d 1 d 3 d 4 } = 600 N2,4 = min{N2,2 + N3,4 + d 2 d 3 d 5 , N2,3 + N4,4 + d 2 d 4 d 5 } = 576

N0,3 =

min{N0,0 + N1,3 + d 0 d 1 d 4 , N0,1 + N2,3 + d 0 d 2 d 4 , N0,2 + N3,3 + d 0 d 3 d 4 } = 820

N1,4 =

min{N1,1 + N2,4 + d 1 d 2 d 5 , N1,2 + N3,4 + d 1 d 3 d 5 , N1,3 + N4,4 + d 1 d 4 d 5 } = 616

N0,4 = min{N0,0 + N1,4 + d 0 d 1 d 5 , N0,1 + N2,4 + d 0 d 2 d 5 , N0,2 + N3,4 + d 0 d 3 d 5 , N0,3 + N4,4 + d 0 d 4 d 5 } = 756

5. Show the longest common subsequence table, L, for the following two strings: X = "skullandbones" Y = "lullabybabies". What is a longest common subsequence between these strings? Solution: Strings X and Y have 13 characters each. We can create an empty L table and first set that L[−1, i] = L[j, −1] = 0 (i.e. first row and column are all zeros). Then, one can fill the table row per row.

l u l l a b y b a b i e s

L −1 0 1 2 3 4 5 6 7 8 9 10 11 12

−1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

s

k

u

l

l

a

n

d

b

o

n

e

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 0 0 0 0 0 1

2 0 0 1 1 1 1 1 1 1 1 1 1 1 1

3 0 1 1 2 2 2 2 2 2 2 2 2 2 2

4 0 1 1 2 3 3 3 3 3 3 3 3 3 3

5 0 1 1 2 3 4 4 4 4 4 4 4 4 4

6 0 1 1 2 3 4 4 4 4 4 4 4 4 4

7 0 1 1 2 3 4 4 4 4 4 4 4 4 4

8 0 1 1 2 3 4 5 5 5 5 5 5 5 5

9 10 11 0 0 0 1 1 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 5 5 6

s 12 0 1 1 2 3 4 5 5 5 5 5 5 6 7

Eventually, we see that the longest common subsequence between X and Y is 7: ullabes

3...