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

[ search CSE | CSE | bsy's home page | links | webster | MRQE | google | yahoo | citeseer | pgp certserver | openpgp certserver ]

bsy+cse127.w03@cs.ucsd.edu, last updated

email bsy.