Name: ____________________________________________________ Alpha: _____________________

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.

## Problem 0 (assessment: self_______ final_______)

Recall Gnomesort from the previous homework:
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.

## Problem 1 (assessment: self_______ final_______)

Suppose A is an array, and i..j a range in A such that the values in A are strictly decreasing from i..k, and strictly increasing from k..j, though we don't know the value of k. Our job is to find the value of k. Below is a recursive algorithm that does this.
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.