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

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