CS 302 Assignment 1

Due date: Thursday, Septembler 6, 2007, 8:30 AM in class.


All written assignments must be <strong><font color=red>handwritten
(not typed or printed from a
computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4
paper.  Write your name on each sheet, and do not fold the pages or crimp the
corners.  (You may use a paper clip or a staple.)

Turn the pages in to me or to the graduate assistant on the due date.

Work the following problems from your textbook:

Problems 2.1, 2.7 on pages 64-69.

2.1:

N
sqrt{N}
N^{1.5}
N^2
N log N
N log log N
N log^2 N
N log(N^2)
2/N
2^N
2^{N/2}
37
N^2 log N
N^3

Answers:

2/N << 37 << sqrt{N} << N << N log log N << N log N ~ N log(N^2) <<
N log^2 N << N^{1.5} << N^2 << N^2 log N << N^3 << 2^{N/2} << 2^N

2.7

(1)  sum = 0;
     for ( i = 1; i < n; i++ )
         sum++;

Ans: O(n)

(2)  sum = 0;
     for ( i = 1; i < n; i++ )
         for ( j = 1; j < n; j++ )
             sum++;

Ans: O(n^2)

(3)  sum = 0;
     for ( i = 1; i < n; i++ )
         for ( j = 1; j < n*n; j++ )
             sum++;

Ans: O(n^3)



(4)  sum = 0;
     for ( i = 1; i < n; i++ )
         for ( j = 1; j < i; j++ )
             sum++;

Ans: O(n^2)

(5)  sum = 0;
     for ( i = 1; i < n; i++ )
         for ( j = 0; j < i*i; j++ )
             sum++;

Ans: O(n^3)


(6)  sum = 0;
     for ( i = 1; i < n; i++ )
         for ( j = 0; j < i*i; j++ )
             if (j % i == 0)
                for ( k = 0; k < j; k++ )
                    sum++;

Ans: O(n^4)


Add just two more code fragment to 2.7, namely (7) and (8):

(7)  sum = 0;
     for ( i = 1; i < n; i = 2*i )
         sum++;

Ans: O(log n)


(8)  sum = 0;
     for ( i = 1; i < n; i++ )
         for( j = i; j < n; j = 2*j )
            sum++;

Ans: O(n)