University of Toronto
Department of Computer Science
CSC148H, Summer 2007

Assignment 1

Due date: Thursday, May 31st @ 4pm. Please submit your assignment on paper at the beginning of lecture.

Purpose

This review assignment (knowledge at the level of CSC108 is enough to answer the questions) is mainly about carefully tracing code, a skill important in understanding other's code and debugging one's own code. Successful programmers debug by tracing their code, not fiddling with it by trial-and-error. As the programs you write become more complex, the difference in productivity between tracing and trial-and-error starts to become very significant.

Question 1: Loops

For each of the following snippets of code, give the total number of times method callme() is called (in terms of a and b), with a brief explanation. Assume that a and b are nonnegative integers.

Snippet A

  
  int i = 1; int j = 2 * a;
  while (i <= j) {
    --j;
    i++;
    callme();
  }
  for (int k = a; k < a*a*a; ++k) {
    callme();
  }

Snippet B

For this one, first we define a method callmany:

  public static void callmany(int a) {
    for (int i = a*a; i > 0; --i) {
      if (a % 2 == 0){
        callme();
      }
    }
  }

Now the snippet:

  callmany(a*a*b);

Snippet C

 
  for (int k = 108; k < 148; ++k) {
    for (int i = a ; i != a + b ; i += 2) {
      for (int j = i; j > 0; --j) {  
        callme();
      }
    }
  }

Question 2: Arrays and Indices

Part A

Complete the body of the following method, as indicated by the comment:

  class Q2A {

    /** Remove duplicate elements from array p and return the result array.
        The relative order of elements is preserved.
        Example: [1,3,4,1,5,2,3,2,1,11,5,1,3] -> [1,3,4,5,2,11]
        @param p  array with possibly duplicate elements
        @return   array p with duplicate elements removed */

    public static int[] removeDuplicate(int[] p) {

      int[] temp = new int[p.length];
      int t = 0;
      for (int i = 0; i < p.length; i++) {
	  boolean isDuplicate = false;

        // FILL IN THIS PART.
        // check temp array to see if the ith element of p is in there
        // and assign a proper value to isDuplicate
        // You may use only one loop, but may not define any new array








        if (!isDuplicate) {
           temp[t++] = p[i];
        }
      } //for

      // FILL IN THIS PART.
      // create the result array with appropriate size using temp array, 
      //and return the result array




    }
  }

Part B

The transpose method below is supposed to transpose a given integer matrix m (i.e. each element [i][j] is swapped with element [j][i] so the result matrix is the mirror of original matrix w.r.t. main diagonal). However, the code is incorrect. Fix all the bugs and hand in the modified code, and then state how many times the statements in the inner loops are executed (in the correct code).

 class Q2B {

  //transposing matrix m. Assume m is a matrix with at least one element
  public static int[][] transpose(int[][] m) {
    for (int r = 0; r < m.length; r++) {
      for (int c = 0; c < m[0].length; c++) {
        m[r][c] = m[c][r];
        m[c][r] = m[r][c];
      } 
    }
    return m;    
  }
}

Question 3: JUnit

Write JUnit test cases to properly test the removeDuplicate and transpose methods in question 2. Annotate each test case with proper explanation of its purpose.