Assignment 3

3 Pages
Unlock Document

Computer Science
Vassos Hadzilacos

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 definition 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 defined in step (a), and (ii) why the computation in (d) yields a solution to the given problem. Part (ii) is often immediate from the definitions. 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 5,15,−30,10,−5,40,10 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 define 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. 2 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] defined 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
More Less

Related notes for CSCC73H3

Log In


Join OneClass

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

Sign up

Join to view


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.