Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Perproblem 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 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 nelement 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
else
return ralse
Analyze the worstcase running time of insertionSort in this
case, i.e. with an nelement 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 SarbaziAzad
(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[k1]
swap(A[k],A[k1])
k
else
k++
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) = (nk) + 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$.

Compute the value of $f$ in the example below:
$A=$ 

, n = 6, k = __3__ and
$f(A,n,k) = $ ___________ 

After one iteration of gnomesort, we would have:
$A=$ 

n = 6, k = _____ and
$f(A,n,k) = $ ___________ 

After another iteration of gnomesort, we would have:
$A=$ 

n = 6, k = _____ and
$f(A,n,k) = $ ___________ 

Prove that $f(A,n,k)$ gets smaller every time the body of
the gnomesort loop is executed.

How does this prove that the algorithm halts?