Homework 2ASolutions PDF

Preview

Summary

Homework 2ASolutions...

Description

CS 3510: Homework 2A Due on September 27, 11pm

Professors Abernethy & Brito

CS 3510 Staff

1

CS 3510 Staff

CS 3510 (Professors Abernethy & Brito ): Homework 2A

Problem 1

Note: Please use pseudocode and not actual code for these problems.

Problem 1 (30 Points) You are given a n × n matrix M of non-negative integers. Suppose you walk along the matrix starting at coordinate (1, 1) in order to reach coordinate (n, n) accumulating the integers along the way. At any coordinate, you may only move right or down. That is, if you are at coordinate (i, j), you can only move to either (i + 1, j) or (i, j + 1) in a single step. Design a dynamic programming algorithm to find the minimum sum you can accumulate in your walk subject to the above constraints. Example Input: 

2 M = 1 9

1 3 0

 4 5 1

Output: 7 Explanation: This sum comes from the path (1, 1) → (1, 2) → (2, 2) → (3, 2) → (3, 3). The accumulated sum is M [1][1] + M [1][2] + M [2][2] + M [3][2] + M [3][3] = 2 + 1 + 3 + 0 + 1 = 7. Please answer the following parts: (a) Define the entries of your table in words. E.g. T (i) or T (i, j ) is ... (b) State recurrence for entries of table in terms of smaller subproblems. Briefly explain in words why it is correct. (c) Write pseudocode for your algorithm to solve this problem. (d) Analyze the running time of your algorithm.

Solution (a) T (i, j) is the minimum possible sum that can be accumulated in a path from coordinate (1, 1) to coordinate (i, j).   if i = 1  T (i, j − 1) (b) Recurrence relation: T (i, j) = M [i][j] + T (i − 1, j) if j = 1   min{T (i, j − 1), T (i − 1, j)} otherwise Base case(s): T (1, 1) = M [1][1]

Since we can only enter coordinate (i, j) where i > 1 and j > 1 from coordinates (i − 1, j) and (i, j − 1), the minimum cost path from (1, 1) to (i, j) must be the minimum of the minimum cost paths till (i − 1, j) and (i, j − 1) plus the amount accumulated at coordinate (i, j). We account for the edge cases where either i = 1 or j = 1 accordingly.

2

CS 3510 Staff

c)

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:

CS 3510 (Professors Abernethy & Brito ): Homework 2A

Problem 2

function MinPathInMatrix(M, n) Initialize T as matrix of size n × n for i = 1, . . . , n do for j = 1, . . . , n do if i == 1 & j == 1 then T [i][j] = M [i][j] else if i == 1 then T [i][j] = T [i][j − 1] + M [i][j] else if j == 1 then T [i][j] = T [i − 1][j ] + M [i][j ] else T [i][j] = min{T [i − 1][j], T [i][j − 1]} + M [i][j] return T [n][n]

(d) Since we fill a table of size O(n2 ) and our transitions (filing up an entry of the table) take O(1) time, the time complexity of the algorithm is O(n2 ).

Problem 2 (30 Points) You are given two strings x and y of lengths n and m respectively. Design a dynamic programming algorithm to find the length of the longest common substring of x and y. That is, find the largest value k for which there exist indices i and j such that x[i : i + k − 1] = y[j : j + k − 1]. (Note that this problem is different from “longest common subsequence.”) Example: Input: x = “tacocat”, y = “mycatlikestacos” Output: 4 Explanation: The longest common substring is “taco”. Please answer the following parts: (a) Define the entries of your table in words. E.g. T (i) or T (i, j ) is ... (b) State recurrence for entries of table in terms of smaller subproblems. Briefly explain in words why it is correct. (c) Write pseudocode for your algorithm to solve this problem. (d) Analyze the running time of your algorithm.

Solution (a) T (i, j) is the length of the longest common substring for x1 x2 . . . xi and y1 y2 . . . yj where the substring ends with xi /yj . ( 1 + T (i − 1, j − 1) if xi = yj (b) Recurrence relation: T (i, j) = 0 if xi 6= yj Base case(s): T (i, 0) = 0 and T (0, j) = 0 for 0 ≤ i ≤ n and 0 ≤ j ≤ n.

3

CS 3510 Staff

CS 3510 (Professors Abernethy & Brito ): Homework 2A

Problem 3

In the case where xi = yj , we can append the last character to the longest common substring for x1 x2 . . . xi−1 and y1 y2 . . . yj−1 to get a longest common substring for x1 x2 . . . xi and y1 y2 . . . yj . In the case where xi 6= yj , the last characters mismatch and we can only have the empty string as the longest common substring. (c)

function LongestCommonSubstring(x, y, n, m) Initialize T as matrix of size (n × 1) × (m × 1) 3: for i = 0, . . . , n do 4: T [i][0] = 0 1:

2:

5: 6: 7: 8: 9: 10: 11: 12:

for j = 0, . . . , m do T [0][j] = 0 for i = 1, . . . , n do for j = 1, . . . , m do if x[i] == y[j] then T [i][j] = T [i − 1][j − 1] + 1 else T [i][j] = 0 return maxi,j T [i][j ]

(d) We fill a table of size (n + 1) × (m + 1) = O(mn) and the transitions take O(1) time. So, this step takes O(mn) time. Returning the maximum value in the table also takes O(mn) time. Thus, the algorithm takes O(mn) time in total.

Problem 3 (40 Points) You are given a nonempty string s of length n only consisting of alphabetical characters. This string does not contain any spaces, punctuation etc. You want to see if this string can be broken up into a sequence of valid words. To aid you in doing so, you are given a blackbox boolean function is a word. For an input string w, is a word is defined as follows: ( true if w is a valid word is a word(w) = false if not Design a dynamic programming algorithm that returns true if s can be broken up into a sequence of valid words and returns false if it cannot. Assume that each call to is a word takes constant time. Also assume that a substring s[i : j] of s can be retrieved in constant time. Examples: Input: s = “helloworldtacocat” Output: true Explanation: s can be broken up into “hello”, “world”, “taco”, and “cat”. Input: s = “crowarrior” Output: false Explanation: Even though “crow“ and ‘warrior‘ are valid words and exist in s as substrings, s cannot be broken up into “crow” and “warrior”. Please answer the following parts: Problem 3 continued on next page. . .

4

CS 3510 Staff

CS 3510 (Professors Abernethy & Brito ): Homework 2A

Problem 3 (continued)

(a) Define the entries of your table in words. E.g. T (i) or T (i, j ) is ... (b) State recurrence for entries of table in terms of smaller subproblems. Briefly explain in words why it is correct. (c) Write pseudocode for your algorithm to solve this problem. (d) Analyze the running time of your algorithm. (e) Suppose you find that s can be broken up into a sequence of valid words after running your algorithm. Provide pseudocode that returns this sequence. Use your filled up DP table directly.

Solution (a) T (i) is boolean valued and denotes whether s1 s2 . . . si can be broken up into a sequence of valid words. (b) Recurrence relation: T (i) =

i _

(is a word(sj+1 . . . si ) ∧ T (j))

j=0

Base case(s): T (0) = true We check if for any j, s1 . . . sj can be written as a sequence of valid words and sj+1 . . . si is a valid word. Here, j is an index at which we can break the string s1 . . . si into two parts. (c)

1: 2: 3: 4: 5: 6: 7: 8:

function SequenceOfValidWords(s, n) Initialize T as an array of size n + 1 T [0] = true for i = 1, . . . , n do T [i] = false for j = 0, . . . , n do if T [j] & is a word(sj+1 . . . si ) then T [i] = true return T [n]

(d) We fill a table of size O(n) where each transition takes O(n) time. Therefore, the running time is O(n2 ). (e)

1: 2: 3: 4: 5: 6: 7:

function SequenceOfValidWords(s, n) seq is an empty array j=n for i = n − 1, . . . , 0 do if T [i] is true & is a word(si+1 . . . sj ) then seq.append(si+1 . . . sj ) j=i return seq

5...