Quiz 2 Solution Sketches
CSE 101 Spring 2002 
4/18/2002

Problem 1. Summation

There are 1013 terms in the expression. These terms can be grouped such that
the first and the last terms form a pair, the second and the next to last terms
form a pair, and so on. The sum of each of such pairs is 3136.  
Thus the result is: (3136 * 1013) / 2 = 1588384
 
Problem 2. Recurrence relation

After iterating the recursion one can see that the closed form of T(n) is:
T(n) = 3 + sum(i=0 to (n-3)) [i]. Notice that the last term is just the
sum of the fist (n-2) integers, thus the correct answer should be: T(100)
= 3 + (97 * 98) / 2 = 4756.

Problem 3. Sum of Squares

For a solution please see:
http://www.shu.edu/projects/reals/infinity/answers/sm_sq_cb.html

For some general guide lines on induction proofs please see:
http://www.cs.cornell.edu/Courses/cs280/2001fa/assignments/induction-guidelines.html

For a handout on induction please see:
http://vlsicad.ucsd.edu/courses/cse101/handouts/induction.pdf 

Problem 4. Master Method

By Master Method case 1:

Since a = 7, b = 2, f(n) = n^2 - 50n + 101, by setting epsilon to be ((log 7) -2)
f(n) = BigO(n^(log 7 - epsilon)) and hence T(n) = BigTheta(n^(log 7)).