*printable version*
# Quiz 2

[1]
[2]
[3]

### Problem 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; }
}

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`

.

### Problem 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++;
}
}
}
}

`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.

### Problem Q2.3.

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

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.