Practice for Test 1

1. Find the big-O complexity of each piece of code below in terms of N.

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

      Answer: O(N)

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

      Answer: O(N)

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

      Answer: O(N²)

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

      Answer: O(N²)

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

      Answer: O(N)

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

      Answer: O(log(N))

   7. for (int i = N; i > 1; i/=2)
        print(i);
      

      Answer: O(log(N))

   8. for (int i = N; i > N-5; i--)
        print(i);
      

      O(1)

2. Write Java code that prints the "border" (first and last rows, first and last columns) of a two-dimensional array a. No fancy formatting in output -- just print first row, last row, first col, last col.

   If a is N x N (square), what is the complexity of this code?

   Answer:

   int numRows = a.length;
   int numCols = a[0].length;
   //first row
   for (int col=0; col<numCols; col++)
     System.out.println(a[0][col]);
   
   //last row
   for (int col=0; col<numCols; col++)
     System.out.println(a[numRows-1][col]);
   
   //first col
   for (int row=0; row<numRows; row++)
     System.out.println(a[row][0]);
   
   //first row
   for (int row=0; row<numRows; row++)
     System.out.println(a[row][numCols-1]);
   
   Complexity is O(N).
   

3. Write code that counts the number of occurrences of integer x in array a. Do the same for a two-dimensional array a.

   //one-dimensional array
   int count = 0;
   for (int index = 0; index < a.length; index++)
      if (a[index] == x)
         count++;
   
   //two-dimensional array
   int count = 0;
   for (int row = 0; row < a.length; row++)
     for (int col = 0; col < a[0].length; col++)
      if (a[row][col] == x)
         count++;
   

4. Write code that reads in N integers in the range -25..+25 and counts the number of occurrences of each integer. N could be arbitrarily large.

   int[] a = new int[51];  //automatically inits to all 0
   //instead of for loop, could use while that stops
   //when read sentinel (eg, a number not in -25..+25)
   for (int i = 0; i < N; i ++)
    {
     int num = Keyboard.readInt();
     a[num+25]++;
    }
   

5. Write code that creates an array of 10 Square objects, fills it with new Square objects (use the default constructor for Square), and prints each Square. Assume that class Square has a printSquare method.

   Square[] squares = new Square[10];
   for (int i = 0; i < 10; i++)
    {
      squares[i] = new Square();
      square[i].printSquare();  //or could print in separate loop
    }