Part 1) Write pseudocode for an iterative algorithm which finds the maximum value of a listof integers. Use a loop invariant to prove your algorithm is correct. (Presumably you havealready written a program like this over the course of your studies! The interesting part hereis the proof.)

Part 2) Prove by induction the recursive program F oo is correct:

Foo determines if there are two indices i and j, p ≤ i < j ≤ q, such that ai + aj = x.(We’re looking in a particular range of sorted list A, indices [p, q] (so including index p aswell as index q), for two values ai and aj which sum to x. We don’t allow i and j to be equal.)

Require: A is sorted in increasing order; 1 ≤ p ≤ q ≤ n

procedure Foo(A = a1, . . . an: integer list; p,q,x: integer)

if p = q then

return False

else

if ap + aq = x then

return True

end if

if ap + aq > x then

return Foo(A, p, q − 1, x)

end if

if ap + aq < x then

return Foo(A, p + 1, q, x)

end if

end if

end procedure