COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 7 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?
(b) What is the standard technique to prove correctness of a dynamic programming algorithm?
(c) How to recover an optimal solution? 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? 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? 4. Shortest path
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases?
(d) Why do we use dynamic programming instead of using Dijkstra’s algorithm?
(e) Why does the proof of correctness for Dijkstra’s break down when the graph has negative edges?
Tutorial
Problem 1
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. 1
0
K
A
T
A
N
A
0
B
A
N
A
N
A
S
Solution:
0
K
A
T
A
N
A
0
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
A
0
0
1
1
1
1
1
N
0
0
1
1
1
2
2
A
0
0
1
1
2
2
3
N
0
0
1
1
2
3
3
A
0
0
1
1
2
3
4
S
0
0
1
1
2
3
4
Problem 2
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.)
Solution: Let s be the input string, and let s[i, j] be the substring consisting of characters in positions i through j. Let M[i] be True if it is possible to insert spaces into s[1,i] to obtain a valid text. Then we can define the base case as M[0] = True by regarding the empty string as a valid text. Then the recursive case is
M[i] = lookup(s[j, i]) ∧ M[j − 1]). 1≤j 1,wecandefineM[j,j]= h1h2…hj. For j > 1 and i < j the event that we flip i heads can be divided into two subcases: that the jth coin came up heads (in which case we need i − 1 heads from the first j − 1 coins, or that the jth coin came up tails (in which case we need i heads from the first j − 1 coins. The two events are mutually exclusive, so we get the following recurrence
M [i, j ] = hj M [i − 1, j − 1] + (1 − hj )M [i, j − 1].
In order for the recurrence to work for the boundary case i, j we can define M [i, i − 1] = 0. There are n2 states and each takes O(1) time to compute. Thus, the overall time is O(n2).
Problem 4
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.
A D B C D B C A, A D C D A,
Solution: (Sketch) First, observe that this problem is equivalent to finding the longest subsequence of A that is a palindrome: the minimum number of deletions is n minus the length of the longest subsequence that is a palindrome. The natural instinct is to have M[i] be the longest subsequence of A[1 . . . i] that is a palindrome. However, this does not work. If A[i] = A[1], then the subproblem is to find the longest subsequence of A[2 . . . i − 1] that is a palindrome. We need to do dynamic programming on intervals instead.
Let M[i,j] be the longest subsequence of A[i,j] that is a palindrome. The base case is M[i,i] = 1 and M[i,i − 1] = 0 for all i. For the recursive case we check if A[i] = A[j] if so, there is no harm in assuming that they will not be deleted, otherwise, the need to delete either i or j:
M[i + 1, j − 1] + 2 if A[i] = A[j] M[i,j]= max(M[i+1,j],M[i,j−1]) ifA[i]̸=A[j]
There are n DP states in total. Each state takes O(1) time to compute, so the overall 2
running time is O(n2).
Problem 5
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.
3
Solution: For each 0 ≤ w ≤ W, let M[w] denote the value of an optimal solution to the subproblem with all n items and weight limit w. Then, we have the recurrence
M[w]= max M[w−wi]+vi 1≤i≤n
because if the optimal solution for the subproblem with weight limit w chooses to take a copy of item i, then it must also contain the optimal solution for the subproblem with all n items and weight limit w − wi. The base case is M[0] = 0, because we cannot take any item if the weight limit is 0. There are W + 1 DP states and each takes O(n) time to compute. Thus, the overall time is O(nW) and space is O(W).
Problem 6
Run the Bellman-Ford algorithm on the directed graph below. Use vertex z as the destination and illustrate how first changes throughout the execution.
5 -2
t
72 y9z
x
6
8
-4 s7
-3
4
Solution: Use vertex z as the destination and the weights as shown in the figure
i=1: Only need to consider edges ending in z; the rest are ∞+? = ∞. (t,z) → −4, (y, z) → 9
i=2:
i=3:
i=4:
• Fors,checkM[1,t]+6=2andM[1,y]+7=16.
• Fort,checkM[1,y]+8=17,M[1,x]+5=∞andM[1,z]+(−4)=−4. • Forx,checkM[1,t]+(−2)=−6.
• Fory,checkM[1,x]+(−3)=∞andM[1,z]+9=9.
• Fors,checkM[2,t]+6=2andM[2,y]+7=16.
• Fort,checkM[2,y]+8=17,M[2,x]+5=−1andM[2,z]+(−4)=−4. • Forx,checkM[2,t]+(−2)=−6.
• Fory,checkM[2,x]+(−3)=−9andM[2,z]+9=9.
• Fors,checkM[3,t]+6=2andM[3,y]+7=−2.
• Fort,checkM[3,y]+8=−1,M[3,x]+5=−1andM[3,z]+(−4)=−4. • Forx,checkM[3,t]+(−2)=−6.
• Fory,checkM[3,x]+(−3)=−9andM[3,z]+9=9.
M
0
1
2
3
4
z s t x y
0
∞ ∞ ∞ ∞
0
∞
-4
∞
9
0 ∞→2 -4
∞ → −6 9
0
2
-4
-6
9 → −9
0
2 → −2 -4
-6
-9
-
0
1
2
3
4
first
z s t x y
NIL NIL NIL NIL NIL
NIL NIL z NIL z
NIL t z t z
NIL t z t x
NIL t z t x
NIL t z t x
So we have:
Shortest path from s to z is: s–t–z Shortest path from t to z is: t–z Shortest path from x to z is: x–t–z Shortest path from y to z is: y–x–t–z
Problem 7
Let G = (V, E) be a connected undirected graph. Given two vertices s and t we can compute the shortest path (shortest in terms of number of edges) in linear time using BFS. It is easy to come up with examples where the there could be multiple shortest paths going from s to t. Design a dynamic programming algorithm to compute the number of shortest paths connecting s and t. Notice that the number of shortest paths connecting s and t may be exponentially large, so we don’t want to list them, just count them.
5
Solution: First compute the distances from s to every other node in the graph using BFS, let dist(u) be the length of the shortest path (in terms of number of edges) from s to u. We define M[u] to be the number of shortest s-u paths in the graphs. We define M[s] = 1 as we see the vertex s by itself as a path from s to s having length 0. For vertices u at distance k > 0 from s, every shortest s-u path can arrive at u through some vertex v such that dist(v) = k − 1 and v and u are connected by an edge. This observation leads to the following recurrence:
M[u] = M[v]. v:(v,u)∈E
dist(v)=dist(u)−1
Suppose the graph has n vertices and m edges. There are n DP states and each takes O(n) to fill in the worst case; thus, the algorithm runs in O(n2). A sharper bound on the running time is possible if we are more careful about how much time we spend at each node. Assuming the graph is represented with adjacency lists, computing M[u] takes O(deg(u)) time; thus, the overall all time to compute all M-values is O(u deg(u)) = O(m).
Problem 8
[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 9
[Advanced] Design an algorithm for the knapsack problem that finds an optimal solution using O(nW) time and O(W) space.
6