CS 6515HW 2 SolutionsInstructor: Gerandy BritoProblem 1: [DPV] 6.8: LCS.(a)P(i; j) = length of the LCStr for x1x2:::xi and y1y2:::yjending at a = xi = yj.For those i and j such that xi 6= yj, we set P(i; j) = 0.(b) Recurrence.P(i; j) = (1 + 0 P(i - 1; j - 1) if if xxii =6= yyjjThe base cases are simple, P(0; j) = P(i; 0) = 0 for any i; j.(c) Pseudocode:• FOR i = 0 ! n: P(i; 0) = 0.• FOR j = 0
...[Show More]
CS 6515
HW 2 Solutions
Instructor: Gerandy Brito
Problem 1: [DPV] 6.8: LCS.
(a)
P(i; j) = length of the LCStr for x1x2:::xi and y1y2:::yjending at a = xi = yj.
For those i and j such that xi 6= yj, we set P(i; j) = 0.
(b) Recurrence.
P(i; j) = (1 + 0 P(i - 1; j - 1) if if xxii =6= yyjj
The base cases are simple, P(0; j) = P(i; 0) = 0 for any i; j.
(c) Pseudocode:
• FOR i = 0 ! n: P(i; 0) = 0.
• FOR j = 0 ! m : P(0; j) = 0.
• FOR i = 1 ! n :
FOR j = 1 ! m
∗ IF xi = yj : P(i; j) = 1 + P(i - 1; j - 1).
∗ ELSE P(i; j) = 0
• RETURN maxi;jfP(i; j)g
(d) The running time is O(nm) as there are two nested loops of size n and m.
Problem 2: Longest Common Sub*!?*
(a)
T(i; j): the length of the longest substring Zij that ends at the ith position of X, i.e.,
Zij = xi-T (i;j)+1; xi-T (i;j)+2; · · · ; xi, and Zij is a subsequence of y1; y2; · · · ; yj.
(b) Recurrence:
T(i; 0) = 0; i = 0; 1; 2; · · · ; n
T(0; j) = 0; j = 1; 2; · · · ; m
T(i; j) = (TT((ii; j --1; j 1)- 1) + 1 if if xxii =6= yyjj
CS 6515 HW 2
This study source was downloaded by 100000797203008 from CourseHero.com on 09-06-2021 04:53:39 GMT -05:00
https://www.coursehero.com/file/50691260/hw2-solutionpdf/
This study resource was
shared via CourseHero.com
CS 6515 2
(c) Pseudocode:
Set values for the rst column (complexity O(n))
for i = 0 to n: T(i; 0) = 0
Set values for the rst row (complexity O(m))
for j = 1 to m: T(0; j) = 0
Compute values for other entries in T (complexity O(nm))
for j = 1 to m:
for i = 1 to n:
if xi = yj:
T(i; j) = T(i - 1; j - 1) + 1
else:
T(i; j) = T(i; j - 1)
Return the maximum value of the entries in the last column (complexity O(n))
return max(T(1; m); T(2; m); · · · ; T(n; m));
(d) The overall time complexity is O(n + m + nm + n) = O(mn).
Problem 3: 6.19 [DPV]: making change with at most k coins
(a) A valid approach is to set T(v; i) be TRUE or FALSE whether it is possible to make value
v using exactly i coins. This leads to an O(nkV ) time solution. Alternatively, we can use a 1-
dimensional array.
For 0 ≤ v ≤ V , let
[Show Less]
-by-Gary-Donell-SOLUTIONS-MANUAL-preview.jpeg)
-by-Gary-Donell-INSTRUCTOR’S-SOLUTIONS-MANUAL-preview.jpeg)
