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
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.)
Problem 3
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.
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.
Problem 5
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 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.
2
5 -2
x
t
72 y9z
6
8
-4 s7
-3
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.
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.
3