Quiz 2: Questions

Q2.1.

[10 pts] Below is a fragment for computing the first factor of a number n. The loop maintains the invariant that p = i ⋅ j. Suppose that at the beginning of one iteration, the invariant holds at that instant, with a representing the value of i, b the value of i, and q the value of p; thus, we know q = a ⋅ b. Argue for why the invariant will still be true at the end of that iteration.

int i = 2;
int j = n - 1;
int p = j + j;
while(p != n && i <= j) {
  if(p < n) { i++; p += j; }
  else      { j--; p -= i; }
}

Q2.2.

[10 pts] At right is a method whose parameter is a matrix, thought to include many zeroes. The method sorts the rows of a matrix so that the number of leading zeroes in each row gets progressively larger. With n representing both the number of rows and the number of columns in the matrix, how much time does this method take? Give your answer using Big-O notation, with the tightest and simplest bound possible. Justify your answer.

public void rearrange(double[][] m) {
  int n = m.length;
  int dst = 0;
  for(int j = 0; j < n; j++) {
    for(int i = dst; i < n; i++) {
      if(m[i][j] != 0.0) {
        for(int k = 0; k < n; k++) {
          int t = m[i][j];
          m[i][j] = m[dst][j];
          m[dst][j] = t;
        }
        dst++;
      }
    }
  }
}

Q2.3.

[10 pts] In your own words, describe how the Quicksort algorithm works.

Quiz 2: Solutions

Q2.1.

Suppose first that p < n. After the iteration completes, i will be a + 1, j will still be b, and p will be q + b. We wish to verify that still p = i ⋅ j, which follows since p = q + b = a ⋅ b + b = (a + 1) b = i ⋅ j.

If, however, p ≥ n, then after the iteration completes, i will still be a, j will be b − 1, and p will be q − a. We wish to verify that still p = i ⋅ j, which follows since p = q − a = a ⋅ b − a = a (b − 1) = i ⋅ j.

Q2.2.

O(n²). Each time we execute the innermost loop will take O(n) time. We will execute the innermost loop at most n times, since each row of the original matrix is swapped into dst only once; once it it is swapped into dst, dst is incremented so that the row is not examined again. Thus, over all iterations of the outermost loop, a total of O(n²) time is spent on the innermost loop. Also, we spend O(n²) time on the body of the middle loop — neglecting the time spent in the innermost loop. So overall we have O(n²) + O(n²) = O(n²) time.

Q2.3.

Given an array to sort, we choose a pivot number (typically through randomly selecting one of the numbers in the list) and partition the elements so that all numbers less than or equal to the pivot come at the beginning of the array, and all numbers greater than it come at the end of the array. We then recursively sort the two subsegments resulting from the partitioning.