CSE 7350/5350

D.W. Matula

Homework Set # 4

Divide-and-Conquer

(Revised: 29  March  2005)

Due date:

12 Apr. '05

1.     Match the following initial segments of sequences and 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  = .                                                 

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

c)      Assuming in each case that T(n) is eventually nondecreasing, determine the order of the following recurrence equations.

                                 i.            T(n) = 2 T + 6n3                           for  n > 1,  n a power of 5;    T(1) = 6

                               ii.            T(n) = 40 T  + 2n3       for  n > 1,  n a power of 3;    T(1) = 5

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

4. [Polynomial Multiplication] Text problem 30-1, p. 844.

 

 

 

 

 

5. [Matrix Multiplication]

a)      Show how an extension of Strassen’s algorithm that adds an extra column and row of zeros computes


b)      What is the fastest running time O(nα) for Matrix Multiplication that you can find in the literature. Give α and your source for the result.      

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

7. [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.