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

Consider the algorithm Alg1(A,n,r,t) from the lecture 3 notes, with input:

A = , n = 7 , r = 3 , t = 6

a. In the space to the right, write the program represented by the A and n.
b. Show the
prior to iteration i = 6, M =
prior to iteration i = 5, M =
prior to iteration i = 4, M =
prior to iteration i = 3, M =
after leaving the loop, M =
according to invarant, $x_t = $ _____________________________________________________

Problem 1 (assessment: self_______ final_______)

Define a PROBLEM "max": of finding the largest element in a given range of elements within an array of integers. Note: In your definition, be precise and try not to use the word "max" or words like "largest", but rather define it in terms of basic comparisons like greater-than or less-than.

Problem 2 (assessment: self_______ final_______)

Consider the algorithm "percolateMax" given below that (hopefully) solves the "max" problem you defined above: 
percolateMax(A,i,j) /* A is an array of integers, i..j is a valid range of indices */
  k = i
  while k < j do
    if A[k+1] < A[k]
      swap(A[k],A[k+1])
    k = k + 1
  return A[j]
  1. Give a loop invariant for the "while" loop in this algorithm, i.e. a condition that is true every time test condition is evaluated, and which makes it easy to give a convincing argument that the algorithm is correct.
  2. Prove the loop invariant always holds: i.e. prove that it holds prior to the first loop iteration, and prove that assuming it holds at the beginning of a loop iteration, it must hold at the end of that loop iteration.
  3. Use the fact that the loop invariant is now proven to always hold to prove that percolateMax really is correct.