Homework #10

 

Please, read the entire chapter 9. We did not cover it in class the way it is presented in the text-book, however, you will find that I touched upon many ideas mentioned in it.

 

Section 9.2, Problems 10, 26, 30 36

Section 9.3, Problems 9, 21, 32, 36

Section 9.4. 19 b), 26, 34

Section 9.5. 26

 

 

Not for submittal

 

As for solving recurrence equations, consider the generic form of the equations we discussed in class:

 

T(n) = a * T(n / b) + f(n) with initial condition T(1) = f(1), where a and b are constants and f(n) is some function depending on n, e.g. f(n) = 1, or f(n) = n or f(n) = 2 * n2 and so on

 

Just to familiarize yourself with the technique of solving such a type of recurrence equation, try to solve this equation for the following cases:

 

a)      a = 3, b = 2, f(n) = 1

b)      a = 2, b = 3, f(n) = n

 

When it comes to the sum, you can approximate it to a reasonable simpler form. For instance, if the sum, equals n2 + n, you can treat it to be just n2.