Computer Science

• Home | 
• Old Courses | 
• CMPT 243 | 
• Assignment #2 | 

Assignment #2

Due Tuesday, Sep. 18

2.2

2.5

2.7 (Big Theta is really more appropriate for part a, so give your analysis results using Big Theta. For part b, implement as Java methods and gather running times as illustrated in the file 'Timer.txt', which is in the Examples directory. For part c, just indicate whether the running times confirm your analysis or not.)

2.8 (Use a Java random number generator (look in the Java API) to code the three algorithms and then complete the tasks in part 3.b through 3.e (you may skip the proof in part a).

2.10

2.11

2.13

2.14

Solve the following recurrences, using the substitution method. For part a) assume that n is even. For part c) assume that n is an integral power of 3, and for part d) assume that n is an integral power of 2.

     a) T(n) = 3               if n = 0;
             = T(n-2) + 2;     if n > 0;


     b) T(n) = 1               if n = 0;
             = 3 T(n-1) + 2;   if n > 0;


     c) T(n) = 1               if n = 1;
             = 3 T(n/3) + 1;   if n > 1;


     d) T(n) = 1               if n = 1;
             = 3 T(n/2) + 1;   if n > 1;

Extra credit: 2.3, 2.4 (use limit rules on p. 31--may require l'Hopital's rule.), 2.12

Another Extra credit: Show that aⁿ = o(n!), for any arbitrary constant a. What is the threshhold where n! overtakes aⁿ ?