
CSE Home  About Us  Search  Contact Info 
P = 1 x ^{3} + 1 x ^{2} + 1 x + 1
Q = 2 x ^{3}  3 x ^{2}  4 x + 5
M(1) = c, andShow that the solution to this recurrence is O(n^{log27}), (log_{2}7 = 2.81...). Assume that n is a power of 2. Use the "tree" method shown in lecture and on the slides.
M(n) = 7 M(n/2) + c n^{2} for n > 1.
The following identities that you've probably seen before might be useful:
1 + x + x^{2} + x^{3} + ... + x^{k} = (x^{k+1}  1)/(x  1) for any x != 1, and
a^{logbn} = (b^{logba})^{logbn} = (b^{logbn})^{logba} = n^{logba},
Input: an unordered list of triples (x_{l}, x_{r}, h), where 0 < x_{l} < x_{r} and 0 < h.
Problem: Each triple describes a rectangle of height h whose base is on the x axis, and whose left and right sides are at positions x_{l} and x_{r}, respectively. Imagine that each rectangle is opaque, and that the whole collection is illuminated from behind. The problem is to calculate the silhouette of the set of rectangles  a description of the visible edges in the resulting scene. (This is a very simple case of what's called hidden line elimination in computer graphics.)
Output: A list of pairs (x_{i},y_{i}), ordered by increasing x_{i}, of the coordinates of points where the height of the silhouette changes.
Example: Given input:
(1,2,1) (10,12,2) (2,4,1) (5,8,3) (3,6,4)the output should be:
(0,0) (1,0) (1,1) (3,1) (3,4) (6,4) (6,3) (8,3) (8,0) (10,0) (10,2) (12,2) (12,0) (infinity,0).
INPUT OUTPUT . ++ . ++   .     .    +++ .  ++     .       .       ++ .   ++       .           .     ++++      . ++             .              .     ++++++++++ . ++ ++ + 0 1 2 3 4 5 6 7 8 9 10 12 0 1 2 3 4 5 6 7 8 9 10 12Give a brief English description of your algorithm, plus pseudocode for it. Give a recurrence relation for its running time and solve it. (If the recurrence is one we solved in class, just state that and give the solution; otherwise, justify your solution.)
Partial credit for correct but nondivideandconquer solutions.
(Extra Credit) The following recurrence generalizes all of the recurrences for divide and conquer algorithms we've seen so far, and many others.
T(1) = c, andShow, for any positive integers a, and c, any k ≥ 0, and any integer b ≥ 2, that its solution is:
T(n) = a T(n/b) + c n^{k} for n > 1.
Loosely speaking, it says that if the number of subproblems is large in comparison to the other parameters, then the work at the leaf level of the recursion tree dominates the run time (case a); if the number of subproblems is small, then the work at the root level dominates (case b), and at the critical inbetween value, all levels contribute equally (case c).
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 981952350 (206) 5431695 voice, (206) 5432969 FAX [comments to cse417webmaster@cs.washington.edu] 