CPSC 220
Fall 2007
HW 1: Review

1. Show how memory is allocated as a result of each declaration below. Show as much information as you can.
   1. double[] a;

      
      
      

   2. String[] a = new String[5];

      
      
      

   3. int[][] a = new int[3][2];

      
      
      

2. Consider the array below:

     6  2  9  3  7  1  5
   

   Show how the array changes at each step as it is sorted using
   1. selection sort

      
      
      
      
      
      

   2. insertion sort

      
      
      
      
      
      

3. For each piece of code give i) the actual number of times the print statement(s) will be executed and ii)the complexity of the code in big-O notation.

   1. for (int i=0; i<N; i++)
         for (int j=0; j<3; j++)
            print(j);
      
      

   2. for (int i=1; i<2*N; i*=2)
         print(i);
      
      

   3. for (int i=3; i<10; i++)
         for (int j=N/4; j>0; j/=2)
            print(j);
      
      

   4. for (int i=0; i<N/2; i+=3)
         print(i);
      
      

   5. for (int i=0; i<N+5; i++)
         for (int j=i; j>=0; j--)
            print(j);
      
      

   6. for (int i=1; i<N; i*=2)
         print(i);
      for (int j=1; j<N+3; j++)
         print(j);
      
      

4. Write a method void printCR(int[][] a, int i) that prints the i^th column followed by the i^th row of a. If a has fewer than i rows or columns, your method should throw an IllegalArgumentException. Note that IllegalArgumentException is a subclass of RuntimeException.

   
   
   
   
   
   
   

5. Find a formula for each sum below, and then give the big-O equivalent. Show your work.

   
   1 + 2 + ... + N
   
   
   1 + 2 + ... + N-1
   
   
   3 + 4 + ... + N+8
   
   
   a + (a+1) + ... + N+b     (N >= a-b)