CSE 421,  Au '11:  Assignment #4, Due: Thursday, October 27, 2011

CSE Home

About Us

Search

Contact Info

Problems:

1. Give a fast divide and conquer algorithm for the following silhouette problem:

   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   12   
   

   Give a brief English description of your algorithm, plus pseudocode for it. Give a recurrence relation for its running time and solve it. (As in the lecture slides, very carefully state exactly what your recurrence is counting. If the recurrence follows one of the forms solved in class or in the text, just state that and give the solution; otherwise, justify your solution.)

2. Kleinberg and Tardos, Chapter 5, Problem 2.

3. Kleinberg and Tardos, Chapter 5, Problem 3.

4. Generalize Karatsuba's integer multiplication algorithm to use multiplications of integers of size ~n/3 in the recursion. What is the time bound for the resulting algorithm (i.e., give the recurrence and solve it). For purposes of solving the recurrence, you may ignore the fact that the subproblems are not exactly of size n/3, but do indicate what size they might be in the worst case (e.g., due to "carries" in the additions). Likewise, when solving the recurrence, you may assume that n is a multiple of 3. (You should be able to do better than Karatsuba's O(n^1.59...) time bound.)

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX