Assignment 3

6 Pages
254 Views
Unlock Document

Department
Computer Science
Course
CSCC73H3
Professor
Vassos Hadzilacos
Semester
Fall

Description
Computer Science C73 November 11, 2010 Scarborough Campus University of Toronto Solutions for Homework Assignment #3 Answer to Question 1. For all i [1..n], dene M[i] = maximum number that is the sum of a contiguous subsequence of S that ends in position i We claim that the following is a recursive formula to compute M[i] for all i [1..n]. S[1], if i = 1 M[i] = max(S[i],S[i] + M[i 1]), if i > 1 This is obvious for i = 1. For i > 1, let x be the contiguous subsequence of S that ends in position i and i has the maximum possible sum among all such subsequences. Thus, x = yS[i], wiere y is the (possibly empty) prex of x ui to and excluding the last element, S[i]. There are two possibilities. Case 1. y is empty. Then x = i[i] and obviously M[i] = S[i]. Case 2. y is nonempty. Therefore, y is a contiguous subsequence of S that ends in position i1 (otherwise xiwould not be a contiguous subsequence of S that ends in position i). Furthermore, y has the maximum sum among all such subsequences of S; for if there was a contiguous subsequence y of S that ends in position i1 and has sum strictly greater than y, then y S[i] would be a contiguous subsequence of S that ends in position i and has sum strictly grater than x , cintrary to the denition of x . So,iy = x i1 and therefore x = x S[i]. Thus, in this case M[i] = M[i 1] + S[i]. i i1 Note that, by denition, the quantity we are interested in (the maximum sum of all elements of a contiguous subsequence of S) is simply max{M[i] : i [1..n]}. Therefore, our dynamic programming algorithm computes M[1],M[2],...,M[n], in this order, using the above recursive formula, and returns the maximum of these values. Expressed in pseudocode, the algorithm is as follows (m keeps track of the maximum sum of contiguous subsequences of S ending in positions examined so far). M[1] := S[1] m := M[1] for i := 2 to n do M[i] := max(S[i],M[i 1] + S[i]) m := max(m,M[i]) return m The correctness of the algorithm follows by the previous argument regarding the recursive formula for M[i] given above. The running time of the algorithm is obviously (n). 1Answer to Question 2. I noticed, albeit too late to do anything about it, that in rewording the question as stated in DPV, I inadvertently changed the question itself. I intended to ask for a longest palindrome that is a subsequence of S, not a substring of S. (The dierence is that a substring is a contiguous subsequence.) The hint was misleading for the question I actually asked, which may have led some of you to read the question as (correctly) stated in DPV and hence solve the correct problem. However, I can only expect you to answer the questions I ask, and not the questions I meant to ask! The only reasonable way that I can think of to deal with this situation is to ignore this question and mark the assignment out of 40 (instead of 50) points. I apologize for this error, and the confusion I have caused. What follows is a solution to the question I should have asked: Finding in quadratic time a maximum length subsequence that is a palidrome. a. For any i,j [1..n] such that i j, dene P[i,j] = maximum length of a palindrome that is a subsequence of S[i..j] The quantity we wish to compute, i.e., the maximum length of a palidrome that is a subsequence of S, is simply P[1,n]. We claim that the following is a recursive formula to compute P[i,j] for all i,j [1..n] such that i j. 1, if i = j max(P[i,j 1],P[i + 1,j])if i < j and S[i] = S[j] P[i,j] = 2, if i = j 1 and S[i] = S[j] 2 + P[i + 1,j 2], if i < j 1 and S[i] = S[j] For i = j this is obviou
More Less

Related notes for CSCC73H3

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit