CSE 7350/5350

D.W. Matula

Homework Set # 4

Divide-and-Conquer

 

[60 points]

Due date:

15 April 2008

1.     [Numerical Series] Match the following series to the appropriate formulas:

a)           1  3  12  60  360  …       (i)    fn  = n2 – 6n + 8

b)          3  3  6  9  15  24  …       (ii)   fn  = n2 – 6n + 10

c)           2  4  8  14  22  32  …     (iii)  fn  = n2 + n – 2

d)          4  1  0  1  4  …              (iv)  fn  = n2 – n + 2

e)           1  4  10  20  35  …        (v)   fn  = 2Fn,  where Fn is the n th Fibonacci number

f)            0  2  6  14  30  …          (vi)  fn  = 3Fn

g)           1  8  27  64  125 …       (vii)  fn  = 2( n choose 2)

h)          5  2  1  2  5  …             (viii)  fn  = 2n – 1

(ix)  fn   =  (n+2 choose 3)

(x)  fn   =  n2

(xi)  fn = (n + 1)! / 2

(xii)          fn = 2n!

(xiii)        fn   =  n3

(xiv)        fn   =  (n – 3)2

(xv)          fn   =  3n2

(xvi)        fn = n!

(xvii)      fn   =  n3

(xviii)    fn   =  2n - 2

(xix)        fn   =  2n - 2

(xx)          fn   = (-1)n – 1 3 n – 1

(xxi)        fn  =  (n2 – n) / 2

 

2. [Recurrences]  

a)      Use induction to verify the candidate solution to each of the following recurrence equations.

                                 i.            tn = tn-1 + 5            for   n > 1        t1 = 2

The candidate solution is tn = 5n - 3.

                               ii.            tn = tn-1 +  n           for   n > 1        t1 = 1

The candidate solution is tn  = ((n+1)2 - (n+1))/2                                      

b)      Solve the following recurrence equations using substitution.

                                 i.            tn =  tn-1  + n2          for   n > 1        t1 = 1 

                               ii.            tn = 3 tn-1  + 2n        for   n > 1        t1 = 1

 

3. [Recurrences] Text problem 4-4, p. 86.

 

4. [Polynomial and Matrix Multiplication]

a)      Text problem 30-1, p. 844.(a and b only)

b)      Text Problem 28.2-1, p. 741.

c)      Text Problem 28.2-4, p.741.

 

5. [Weighted Median] Text exercise 9-2 (a, b, c only), pp. 194.

 

6. [Points in space] Describe how to solve by divide-and-conquer in O(n lg n) time either the convex hull problem [text pp 947, 948] or the Voroni diagram problem.