Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

This lab, which is really more of a problem set than a lab, will give you a chance to practice with the analysis tools we have considered in class. You may again discuss the lab with your classmates and give and receive some help, but your submission must be your own work.

Written Problems

See the PDF version of this document for a better version of of the assignment, as the HTML rendering of these kinds of problems is poor and improving it is more trouble than it's worth.

1. Compare the asymptotic growth rates of the following pairs of functions and decide if one grows faster than the other or if they grow at the same rate. Prove your answers using limits. All logarithms are base 2, unless otherwise noted. (4 points)
   1. 5N² + 2N + 5 and N²
   2. NlogN and N²
   3. 2^logN and N
   4. 2^N and 2^2N
2. Prove the following using limits (4 points):
   1. N in Omega(logN)
   2. 5N + 6 in Theta(N)
   3. N logN in Omega(N)
   4. N in Theta(N - N^(1)/(2))
3. For each of the following functions, indicate the class Omega(g(n)) to which the function belongs. Use the simplest g(n) possible. Prove your assertions. (6 points)
   1. 762n² - 56n + 37
   2. (n³ + 100)⁵
   3. 2ⁿ + n²
4. Analyze the following code segment and give an exact formula involving summations for the number of times the word "hello" is printed. Then simplify your formula to obtain an exact formula for the number of times the word "hello" is printed that does not involve summations (i.e., give a closed form solution). (In the code segment, Math.pow(2,j) is a function that returns 2 raised to the j^th power.) (6 points)

   for ( i = 1; i <= N; i++ )
       for ( j = 1; j <= N; j++ ) {
           for ( k = 1; k <= Math.pow(2,j); k++ ) {
                System.out.println("hello");
           }
           System.out.println("hello");
       } 
   

   Note: you may test your formula by implementing this code and then running it for different values of N.

Submission

Before 11:59 PM, Monday, September 30, 2013, submit a PDF of your responses for grading using Submission Box under assignment "Analysis".