Homework 2

Due Thursday, July 1st @ 8pm

1. Using the Iterative Substitution method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	2T(n/2) + bn	n > 1

2. Using the Iterative Substitution method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	T(n/2) + bn	n > 1

3. Using the Recursion Trees method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	T(n - 1) + bn	n > 1

4. Using the Recursion Trees method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	T(n/2) + 2n	n > 1

5. Using the Master method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	9T(n/3) + n	n > 1

6. Using the Master method, solve for T(n):
   

   T(N) = {	b	n <= 1
   	3T(n/4) + n log n	n > 1

7. Solve for T(n):
   

   T(N) = {	b	n <= 1
   	4T(n/2) + n2	n > 1

8. Solve for T(n):
   

   T(N) = {	b	n <= 1
   	2T(n/3) + n2	n > 1

9. In class we proved that any comparison-based sorting algorithm runs in Omega(n log n), if we know nothing about the input. Give a sorting algorithm that is not Omega(n log n) for the following problems:
   1. The input consists of log n sorted lists, each containing an equal amount of input.
   2. The input is a list of integers, each of which is within log n positions of its sorted position.
10. Given a board of 2^k x 2^k squares with a single (arbitrarily chosen) square covered and a sufficient supply of L-shaped pieces (see figure), describe a Divide-and-Conquer algorithm to fill the board such that every square is covered and nothing hangs off the edge of the board.