Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Describe help received: _________________________________________________________________

Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Algorithm: gnomesort(A,n) Input: array A of n elements Output: side effect - the elements of A are sorted k = 0 while k < n if k > 0 and A[k] < A[k-1] swap(A[k],A[k-1]) k-- else k++Prove that "$A[0\ldots k-1]$ is in sorted order" is a loop invariant

for Gnomesort, and use this to prove gnomesort is correct.

This algorithm still isn't right! Next year I should give a (flawed) "proof" of correctness for this algorithm and ask the students to find the flaw!

findMinSpec(A,i,j) Input: array A and range i..j such that for some index k, values in A are strictly decreasing from i..k, and strictly increasing from k..j Output: the special index k if i == j return i a = (2*i + j)/3 → was erroneously a = (i + j)/3 b = (i + 2*j)/3 → was erroneously b = (2*i + 2*j)/3 if A[a] < A[b] { ip = i; jp = b; } else { ip = a; jp = j; } r = findMinSpec(A,ip,jp); return r;

- Write down a recurrence for an upper bound on the $T_w(n)$, the worst-case running time on a range of $n$ elements.
- Give an inducive proof that the algorithm meets its specification.