DOC PREVIEW
PSU CSE 565 - Algorithm Design and Analysis

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithm Design and Analysis October 5, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 10Homework 6 – Due Friday, October 10, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not b e acc epted.• Collaboration is permitted, but you must write the solutions by yourself without a ssistance,and be ready to explain them orally to a me mber of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, please write down your solution to each problem on a separate sheet ofpaper. Make sure to include all identifying information and your collaborators on each sheet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time.You may use algorithms from class as subroutines. You may also use any facts that we provedin class or from the book.Exercises These should not be handed in, but the material they cove r may appear on exams:1. Recall the maxup, maxdowntemperature problem for Homework 5. Give a linear-time algorithmfor the same problem which makes a single pass through the data and uses only a constantamount of workspace (b e yond the space needed to store the input).2. Chapter 5, Problem 2, 4,5.3. (Divide-and-conquer: local minimum in a tree) Chapter 5, Problem 6.4. The algorithm we saw in class for the segmented least squares problem requires the quantity ei,j(the best squared error of any single-line for points i through j). Give a O(n2)-time algorithmto simultaneously compute all the values ei,j. (Hint: See footnote 1 on page 266. The formulafor ei,jis given in the lecture notes and on page 262 of the book.)5. (One-dimensional Dynamic Programming) Chapter 6, Problems 1,3,10,12.1Problem to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. (Multiplication via Divide and Conquer) Given the coefficients of n polynomials of degree1 each, f1, f2, ..., fn, we would like to compute the coefficients of their product, g(x) = πni=1fi(x).(a) Suppose we multiply the polynomials into the product one at a time, that is:1 g0← 12 for i ← 1 to n3 do gi← Multiply(gi−1, fi)4 Output gnwhere “Multiply” takes time O(d) to multiply a polynomial of degree d with a polynomialof degree 1. How long will this procedure take?(b) Give an algorithm that computes the coefficients of the product in time O(n log2n). (Hint:Use divide and conquer to break the product up into evenly balanced sub-products. It mayalso help to think about what kind of recurrence has n log2n as a solution.)2. (Word Segmentation): Chapter 6, Problem


View Full Document

PSU CSE 565 - Algorithm Design and Analysis

Download Algorithm Design and Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithm Design and Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithm Design and Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?