Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
• 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:
||, 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.
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]
k = k + 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.
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.
Use the fact that the loop invariant is now proven to always
hold to prove that percolateMax really is correct.