Computer Science C73 October 19, 2010
Scarborough Campus University of Toronto
Homework Assignment #3
Due: November 9, 2010, by 10:30 am
(in the drop box for your CSCC73 tutorial section, near room SW-626A)
Appended to this document is a cover page for your assignment. Fill it out, staple your answers to it,
and deposit the resulting document into the course drop box (without putting it in an envelope).
Recall that a dynamic programming algorithm to solve a given problem P involves the following elements:
(a) A deﬁnition of a polynomial number of subproblems that will be solved (and from whose solution we
will compute the solution to P — see (d) below).
(b) An ordering of these subproblems.
(c) A recursive formula to compute the solution to each subproblem from the solutions to smaller sub-
problems (“smaller” in the sense of the ordering in (b)).
(d) A way to compute the solution to P from the solutions to the subproblems computed in (c).
Explaining the correctness of a dynamic programming algorithm amounts to justifying (i) why the recursive
formula in step (c) correctly computes the subproblems deﬁned in step (a), and (ii) why the computation
in (d) yields a solution to the given problem. Part (ii) is often immediate from the deﬁnitions.
Question 1. (10 marks) (Exercise 6.1 in DPV, slightly reworded.) A contiguous subsequence of a list
S is a subsequence consisting of consecutive elements of S. For instance, if S is
then 15,−30,10 is a contiguous subsequence of S, but 5,15,40 is not. Consider the following problem:
Input: A list of numbers S = a ,1 ,2..,a n
Output: The maximum number m such that m is the sum of all elements of a contiguous subsequence
of S. (We deﬁne the sum of an empty subsequence to be 0.)
It is trivial to design an O(n ) algorithm to solve this problem, since there are only O(n ) contiguous
subsequences of a sequence of length n. Use dynamic programming to give an O(n) algorithm to solve this
problem. Explain why your algorithm is correct.
Hint: For each integer i, 1 ≤ i ≤ n, consider the maximum number that is the sum of all elements of a
contiguous subsequence of S that ends with a . i
Question 2. (10 marks) (Exercise 6.7 in DPV, reworded.) A palindrome is a string that reads the same
backwards as forwards.
a. (9 marks) Give an O(n ) algorithm which, given a string S, returns the maximum number m such
that m is the length of a substring of S that is a palindrome. Explain why your algorithm is correct.
Hint: For all integers i,j, 1 ≤ i ≤ j ≤ n, consider the quantity P[i,j] deﬁned as the maximum length of
a substring of S[i..j] that is a palindrome.
b. (1 marks) Modify your algorithm in part (a) so that it returns a maximum-length substring of S
that is a palindrome.
1 Question 3. (10 marks) We are given a picture of some tissue in the form of an n × n array A of bits
representing pixels of the picture: A “1” in this array denotes the presence of blood in the pixel, and a
“0” denotes the absence of blood in that pixel. A blood clot is a contiguous lump of blood, and (for some
reason) we are only interested in square blood clots. Our