« Homework Syllabus for all sect | Main | Lecture #Syllabus for all sect »
January 24, 2006
Homework Syllabus for all sect
1. Problem 7.2
2. Problem 7.7
3. Use equation 7.1 to give a bound on the running time of a divide and conquer algorithm that splits a problem into pieces that are 1/5 the size of the original problem, solves 4 of the pieces and requires Θ(n^2) to recombine subproblems at each level. Suppose that you could recombine the subproblems using an Θ(n) algorithm if you solved all 5 subproblems rather than only 4. Which algorithm has a better bound?
Posted by jones at January 24, 2006 02:47 PM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)