CS代考程序代写 algorithm COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 6 School of Computer Science

COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 6 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Dynamic programming technique
(a) What are the three main ingredients in developing a dynamic programming algorithm?
2. Weighted interval scheduling
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases? 3. Knapsack
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases?
Tutorial
Problem 1
Consider the following function computing the n-th Fibonacci number. Algorithm 1 Fibonacci
1: 2: 3: 4: 5: 6: 7:
function Fib(n)
if i==0ori==1then
return i else
return Fib(i − 1) + Fib(i − 2); end if
end function
Draw the tree illustrating the recursive calls for Fibonacci(5). It turns out that the number of leafs in a call tree for Fibonacci is equal to the Fibonacci number itself, which is roughly 1.618n. Write an iterative implementation of Fibonacci(n) that only uses O(n) time and space.
1

Solution:
Algorithm 2 Fibonacci
1: function Fib(n)
2: initialise an array M [0..n]
3: M[0]←0
4: M[1]←1
5: fori=2tondo
6: M[i] ← M[i − 1] + M[i − 2]
7: end for
8: return M [n]
9: end function
Problem 2
Show all intermediate steps of the dynamic programming algorithm for the weighted interval scheduling problem, for the following input.
item
1
2
3
4
5
6
7
8
9
10
start
0
1
0
3
2
4
6
2
7
6
finish
2
3
4
5
6
7
8
9
10
11
weight
2
9
6
5
7
11
8
10
4
6
Solution:
The DP recurrence for the weighted interval scheduling problem is: M[j]=max(wj +M[p(j)],M[j−1]),
with M[0] = 0 as the base case. Recall that M[j] is the optimum value of the subinstance restricted to intervals I1,…,Ij. Let Oj be the optimum set of items that gives the value M[j].
The solution is at M [10] = 24 and corresponds to Oj = {2, 6, 9}.
j
1
2
3
4
5
6
7
8
9
10
sj
0
1
0
3
2
4
6
2
7
6
fj
2
3
4
5
6
7
8
9
10
11
wj
2
9
6
5
7
11
8
10
4
6
p(j )
0
0
0
2
1
3
5
1
6
5
M[j]
2
9
9
14
14
20
22
22
24
24
Oj
{1}
{2}
{2}
{2, 4}
{2, 4}
{2, 6}
{2, 4, 7}
{2, 4, 7}
{2, 6, 9}
{2, 6, 9}
Problem 3
Consider the following variant of the Interval Scheduling problem we saw in class. The input is defined by a set of intervals I1,…,In. We say that interval Ii = (si,fi) has length fi − si. We would like to pick a set of non-intersecting intervals that use as much as possible of the common resource; that is, we want to maximize the sum of the lengths of the scheduled intervals. Design an efficient algorithm for this problem using dynamic programming.
2

Solution: There is a simple solution to this problem: We define the weight of interval i to be fi − si. Now the problem reduces to finding a maximum weight set of non-intersecting intervals, which is a Weighted Interval Scheduling problem that can be solved in O(n) time using the dynamic programming algorithm that we went through in class.
Problem 4
Solve the following instance of the {0, 1} Knapsack Problem with four items where the maximum allowed weight is Wmax = 10.
i bi wi
1 25 7
2 15 2
3 20 3
4 36 6
Solution: We define B[k,w] to be the optimal solution that can be obtained using only the first k items, with maximum allowed total weight of w. Here k ranges from 1 to 4, while wrangesfrom0to10. WealsodefineB[0,w]=0forallw. Thenwehavetofillinthe table, one row at a time, to find the optimal solution, using the recurrence type of equation that can be found in the class notes. This table will end up having these values:
So the maximum benefit obtainable is 56. Since this example is small, we can easily figure out that we want to take items 3 and 4 to obtain this benefit. Otherwise, as also mentioned in class, we can “trace back” through the table to find this out.
1 2 3 4
0 0 0 0 0
1 0 0 0 0
2
0 15 15 15
3
0 15 20 20
4
0 15 20 20
5
0 15 35 35
6
0 15 35 36
7 25 25 35 36
8 25 25 35 51
9 25 40 40 56
10 25 40 45 56
Problem 5
Suppose we are going on a hiking trip along the Great North Walk from Sydney to Newcastle. We have a list of all possible campsites along the way, say there are n possible places where we could camp. (Assume campsite are right off the path.) We want to do this trip in exactly k days, stopping in k − 1 campsites to spend the night. Our goal is to plan this trip so that we minimize the maximum amount of walking done on any one day. In other words, if our trip involves 3 days of walking, and we walk 11, 14, and 12 kilometers on each day respectively, the cost of this trip is 14. Another schedule that involves walking 11, 13, and 13 kilometers on each day has cost 13, and is thus preferable. The locations of the campsites are specified in advance, and we can only camp at a campsite.
Using dynamic programming, design an efficient algorithm for solving this problem. Your algorithm should run in O(n2k) time.
3

Solution: Number all the locations along the trail. We start at location 0 and want to go to location n + 1; there are n campsites along the way. Let D(0, i) be the distance from 0 to location i; to compute the distance between two locations j < i we use D(j, i) = D(0, i) − D(0, j). The journey takes k days, and we stop at k − 1 places along the way. Let M(i,l) to be cost of the optimal solution to reach campsite i in l days. To derive a recurrence for this quantity we need to consider which campsite was used before the lth, suppose it was j then M (i, l) = max{M (j, l − 1), D(j, i)}. For the base case, if we want to reach location i in one day we must walk from 0 to i, thus M(i, l) = min 􏰢 max{M(j, l − 1), D(j, i)} 􏰣, j 10 then S[j] = 1 + min{S[j − 1], S[j − 7], S[j − 10]}.
Thus, finding S[n] takes O(n). Now we can find S[n] easily as above, but knowing this does not tell us the exact nature of the stamps we need. It would be nice to know that we can make 45c postage with six stamps, and that we need one 1c, two 7c, and three 10c stamps to do so. (For some values of n there could certainly be more than one way to do this. For example, we can get 63c with nine 7c stamps, or with six 10c and three 1c stamps.) Well, we can easily do this too with another array called, say, P. Then P[n] will be a vector of length 3 that will tell us what stamps we need to make postage for nc. For example, we would have P [45] = (1, 2, 3), meaning that we need one 1c, two 7c, and three 10c stamps. In general, if we have P [n] = (a, b, c), then we take a 1c stamps, b 7c stamps, and c 10c stamps to make nc postage.
The calculation for S[n] doesn’t change. All we do is determine which denomination of postage we use and add it to the appropriate value of P[n−1],P[n−7], or P[n−10]. The running time is still O(n).
Problem 7
You are hired by a financial company to design algorithms to find good investment opportunities. The company has done a lot of research on n different emerging markets. For market i they have a set of investment strategies Si,1 , Si,2 , . . . , Si,k . Strategy Si,j involves investing Ii,j dollars and yields a profit of Pi,j. Because two strategies for the same market typically overlap, for each market you must choose one strategy or not to invest. The company has a budget B for how much it can invest and its goal is to maximize profit.
Design an efficient algorithm for this problem using dynamic programming. (Assume all numbers are integers.)
5