COMP3027/COMP3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 5 School of Computer Science
Note: Problems 1 and 2 were leftover from the last tutorial as several groups were not able to get to it. If it has been covered in your tutorial or you feel comfortable with them, feel free to move on to the other problems.
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?
(b) What is the standard technique to prove correctness of a dynamic programming algorithm?
(c) How to recover an optimal solution?
(d) In what order should we evaluate the subproblems?
2. Longest common subsequence
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases?
(d) In what order should we evaluate the subproblems?
3. RNA secondary structure
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases?
(d) In what order should we evaluate the subproblems?
Tutorial
Problem 1
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.
1
Using dynamic programming, design an efficient algorithm for solving this problem. Your algorithm should run in O(n2k) time.
Problem 2
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 3
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.)
Problem 4
Run the longest common subsequence algorithm on the strings X = BANANAS, Y = KATANA. In particular, compute the DP table M. Recall the recurrence:
0 if i = 0 or j = 0
M[i,j]= max{M[i−1,j−1]+1,M[i,j−1],M[i−1,j]} ifX[i]=Y[j] max{M[i, j − 1], M[i − 1, j]} if X[i] ̸= Y [j]
Note that in the table below, the 0 column and 0 row corresponds to M(i,0) and M(0,j), respectively.
0
K
A
T
A
N
A
0
B
A
N
A
N
A
S
Problem 5
You are given a string with n characters. The string comes from a corrupted text where all white spaces have been deleted (so it looks somethings like “thefoxjumpedoverthelazydog”). Suppose that you are given a function lookup(w) that takes as input a some string w and return True iff w is a valid word.
Design an algorithm based on dynamic programming to test whether it is possible to insert spaces into the input string to obtain a valid text (we don’t care about meaning.)
Problem 6
Suppose you are given n biased coins h1, . . . , hn; here hi is the probability that the ith coin comes up heads. Consider the following random experiment: Flip all n coins and let X be the number of heads. Define pi to be the probability that X = i. Design an efficient algorithm to compute pi for i = 0, . . . , n.
2
Problem 7
A palindrome is a string that reads the same left to right as right to left. Given a string A of length n over some alphabet Σ, your task is to design O(n2) time algorithm that will delete the fewest characters from A so that what remains of the string is a palindrome. For example
can be turned into
by deleting only three characters.
Problem 8
A D B C D B C A, A D C D A,
In this problem, we will consider a variant of the knapsack problem called the unbounded knapsack problem. We are given as input n items with values and weights (the i-th item has value vi and weight wi) and a weight limit W. Unlike the knapsack problem we saw in class, we are allowed to choose multiple copies of each item. For example, suppose we have two items with where item 1 have value v1 = 2, weight w1 = 2, anditem2hasvaluev2 =3,weightw2 =3andaweightlimitW =4. Ifweareonlyallowedtochooseat most one copy of each item, then the optimal solution is to take item 2 for total value of 3. On the other hand, if we can choose multiple copies of each item, then the optimal solution is to take 2 copies of item 1 for a total value of 4.
Your task is to design an algorithm that finds an optimal solution to the unbounded knapsack problem that takes O(nW) time and O(W) space.
Problem 9
[Advanced] Design an algorithm that given two strings A of length n and B of length m, finds the longest common subsequence of A and B using O(n + m) space and O(nm) time.
Problem 10
[Advanced] Design an algorithm for the knapsack problem that finds an optimal solution using O(nW) time and O(W) space.
3