false

Class Notes
(838,243)

Canada
(510,789)

University of Toronto Scarborough
(31,563)

Computer Science
(312)

CSCC73H3
(10)

Vassos Hadzilacos
(10)

Lecture

by
OneClass4706

Unlock Document

Computer Science

CSCC73H3

Vassos Hadzilacos

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.