CMSC 435  Algorithms

Homework # 8

Due Thursday, October 29

Solve the following recurrence relations

                                    1                                  if n = 1

1.  T(n) =

5T(n/4) + n²                       otherwise

                                    1                                  if n = 1

2.      T(n) =

3T(n/2) + n²                 otherwise

1                                  if n = 1

3.      T(n) =

4T(n/2) + 3n²               otherwise

1                                  if n = 1

4.      T(n) =

2T(n/2) + n lgn             otherwise

1                                              if n = 1

5.      T(n)  =                  

                                    4 T(n/2) + n                              otherwise

1                                              if n = 1

6.      T(n)  =                  

                                    2T(n/2) + lg n                           otherwise

                                    1                                              if n = 1

7.      T(n)  =

7 T(n/4) + n lgn                        otherwise

8.      Given the Diagram shown below illustrating an intermediate stage of the bubbleSort algorithm , and the strategy of "bubbling"  the largest remaining element to the top of the front segment of the list, complete the description of the invariants before and after each iteration of the inner and outer loops and list the start and stop conditions for locating each segment boundary.  Use these invariants to write the algorithm for bubbleSort.