CPSC 220
Fall 2005
HW 1: Review

1. Draw the memory model for each piece of code 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 each step in sorting this array 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 the sum below, and then give the big-O equivalent for it. each. Show your work.

   a + (a+1) + ... + N+b     (N >= a-b)
   

6. Convert the following expressions as indicated.
   1. Infix to postfix: ((g + a) * (b + c)) / (d % f)
   2. Postfix to infix: a b c / + e f g d % * - +