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
Recall the optimal time investment window problem from Lecture 1. In this problem, we are given an array A of n integers (each integer can be positive, zero, or negative). A time window is an interval [i,j] and its return is the sum of elements of the array with indices between i and j (inclusive), i.e. the return of [i,j] is i≤k≤j A[k]. Note that a time window with i = j is allowed; in this case, its return is A[i]. An empty time window is also allowed; its return is 0.
Give a divide-and-conquer algorithm that finds a time window with maximum return and runs in time O(n log n).
Problem 2
(Exercise 6, Chapter 5 from textbook Algorithm Design) Let T be a complete binary tree with n vertices. Each vertex v has a distinct weight w(v). A vertex is a local minima if its weight is less than the weight of its neighbors. Give a divide-and-conquer algorithm that finds a local minima in time O(log n).
Problem 3
Consider the following function computing the n-th Fibonacci number.
1
Algorithm 1 Fibonacci
1: 2: 3: 4: 5: 6: 7:
function Fib(n)
if n==0orn==1then
return n else
return Fib(n − 1) + Fib(n − 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.
Problem 4
Show all intermediate steps of the dynamic programming algorithm for the weighted interval scheduling problem, for the following input.
Problem 5
Solve the following instance of the {0, 1} Knapsack Problem with four items where the maximum allowed weight is Wmax = 10.
Problem 6
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.
Problem 7
Consider a post office that sells stamps in three different denominations, 1c, 7c, and 10c. Design a dynamic programming algorithm that will find the minimum number of stamps necessary for a postage value of n cents. (Note that a greedy type of algorithm won’t necessarily give you the correct answer, and you should be able to find an example to show that such a greedy algorithm doesn’t work.) What is the running time of your algorithm?
Problem 8
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
i bi wi
1 25 7
2 15 2
3 20 3
4 36 6
2
[COMP3927 only] In class, we designed a dynamic programming algorithm for the knapsack problem that uses O(nW) space where n is the number of items and W is the weight limit. Design a space-efficient algorithm that computes the optimal value that uses only O(W) space.
3