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