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.

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;