Old final from last year is here [PDF]
An example find-the-error proof-of-correctness question: What is wrong with the following code? (Assume that the median_to_front implementation is correct.) #define SSWAP(x,n) do {if (x[n] > x[n+1]) SWAP(x,n);} while(0) /* 0 <= nelt < INT_MAX, base[0..nelt-1] valid */ void quicksort(int *base, int nelt) { int pivot, t, hi, lo; switch (nelt) { /* base cases */ case 2: SSWAP(base,0); /* fall through */ case 0: case 1: return; } median_to_front(base, nelt); pivot = base[0]; lo = 1; hi = nelt-1; /* base[1..lo-1] <= pivot < base[hi+1,nelt-1] */ while (lo <= hi) { while (lo < nelt && base[lo] <= pivot) lo++; while (0 <= hi && pivot < base[hi]) --hi; t = base[lo]; base[lo] = base[hi]; base[hi] = t; } while (0 <= hi && base[hi] == pivot) hi--; if (0 < hi) quicksort(base,hi+1); if (lo < nelt) quicksort(base+lo,nelt-lo); }Use the concepts of preconditions and postconditions in your analysis. |
Who | Where | When |
---|---|---|
Bennet Yee | AP&M 5141 | Tue/Thu 2pm-3pm |
Matthew Hohlfeld | AP&M 3337A | Mon/Wed 1pm-2pm |
Eric Liu | AP&M 2331 | Tue/Thu 9am-10am |
There is a DISCUS web board for discussions and Q&A.
bsy+cse127.w03@cs.ucsd.edu, last updated
email bsy.