# Discrete Math- Write pseudocode for an iterative algorithm && Prove by induction the recursive program

I’m studying for my Computer Science class and need an explanation.

Part 1) Write pseudocode for an iterative algorithm which finds the maximum value of a list of integers. Use a loop invariant to prove your algorithm is correct. (Presumably you have already written a program like this over the course of your studies! The interesting part here is 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 as well 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