CS 170 Reading Quiz -- Week 1, Monday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. Is n² = O(n³)? Yes or no.

(If you cannot read the superscripts, this is asking: "Is n^2 = O(n^3)?".)

2. We want to split an unsorted array A[] into two parts, a left part and a right part. The left part should contain all of the values less than or equal to a midpoint value, specified as input to the algorithm. The right part should contain all values that are greater than the midpoint value. Here is an algorithm that does this by modifying the array in-place:

Algorithm Partition(A[0..n-1], midpoint):
1. Set i := 0.
2. For j := 0,1,..,n-1:
3.   /* Invariant: ??? */
4.   If A[j] <= midpoint:
5.      swap(A[i], A[j]).
6.      Set i := i+1.

In other words, after executing this algorithm, the array A[] should contain all of the original array elements that are less than or equal to the midpoint value (in some arbitrary order), followed by all of the original array elements greater than the midpoint (also in some arbitrary order).

Let's prove that the Partition algorithm shown above is correct. State an invariant (at line 3) which is sufficient for this purpose.

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page