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_______)

Look back at the loop invariants we came up with in class for insertionSort and selectionSort. Both algorithms have the same outer loop:
for i from 0 to n-2 do

Problem 1 (assessment: self_______ final_______)

Suppose that we want to sort an array $A$ of length $n$, in which each element of $A$ is itself an array of $n$ integers. We will define "<" for these arrays as
Algorithm: lt(a,b)
Inputs: a and b, both n-element arrays of integers
Output: true if a is "less than" b, false otherwise

k = 0;
while k < n and a[k] = b[k] do
  k = k + 1

if k < n and a[k] < b[k]
  return true
  return ralse
Analyze the worst-case running time of insertionSort in this case, i.e. with an n-element array $A$, each element of which is array of $n$ integers, using the above algorithm as "<".
Note1: You must justify both your lower bound and upper bound!
Note2: Assume the elements of $A$ are pointers to arrays of ints, so that swapping two elements of $A$ is a constant time operation.

Problem 1 (assessment: self_______ final_______)

From Wikipedia: Gnome sort (or Stupid sort) is a sorting algorithm originally proposed by an Iranian computer engineer Dr. Hamid Sarbazi-Azad (Professor of Computer Engineering at Sharif University of Technology) in 2000 and called "stupid sort".
The following sorting algorithm is called "Gnomesort":
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]
The beautiful thing about Gnomesort is that it's not at all clear that this thing ever halts, much less halts with the array in sorted order. How can we convince ourselves that this algorithm is correct. Consider the following function \[ f(A,n,k) = (n-k) + 2*\# \text{ pairs $i,j$ such that $0 \leq i \lt j \lt n$ and $A[j] \lt A[i]$} \]
So, for example, if $A=$ $, n=4, k = 2$ then
(8,5), (8,6), (8,4), (5,4), (6,4) are out of order, so $f(A,n,k) = (4 - 2) + 2*5 = 12$.
  1. Compute the value of $f$ in the example below:

    $A=$ , n = 6, k = __3__ and $f(A,n,k) = $ ___________
  2. After one iteration of gnomesort, we would have:

    $A=$ n = 6, k = _____ and $f(A,n,k) = $ ___________
  3. After another iteration of gnomesort, we would have:

    $A=$ n = 6, k = _____ and $f(A,n,k) = $ ___________
  4. Prove that $f(A,n,k)$ gets smaller every time the body of the gnomesort loop is executed.
  5. How does this prove that the algorithm halts?