Question 2 15 points Consider functions max and min so that

Question 2 (15 points): Consider functions max and min so that max(a1,a2,...,an) and min(a1,a2,...,an) are the maximum and minimum of the n numbers a1, a2, . . . , an, respectively.

a) Give recursive definitions of the functions max and min.

b) Give recursive algorithms for finding max and min.

c) Prove that the recursive algorithms that you found in part b are correct.

Solution

max(a₁)=a₁   min(a₁)=a₁

max(a₁, a₂) = a₁ if a1 a2, min(a₁, a₂) = a₁ if a₁ a₂,

a₂ if a₂ a₁    a₂if a₂ a₁,

max(a₁, . . . , a_n) = max(max(a₁, . . . , a_n1), a_n), min(a₁, . . . , a_n) = min(min(a₁, . . . , a_n1), a_n).

the original definitions of max and min for n 2, hence our base case is already guaranteed to be true. Now suppose that the extended definitions of max and min compute the maximum or minimum element for a list of length (n 1); we will show that this entails that they compute the correct value for a list of length n.

Let m = max(a₁, . . . , a_n) = max(max(a₁, . . . , a_n1), a_n) = max(a₁, . . . , a_n1). In this case, m an by the outer max, and by inductive assumption, m ai for all 1 i < n by the inner max and moreover m is one of the ai . These are the two defining properties of max, and hence our definition computes it correctly.

Suppose m = a_n instead. In this case, a_n max(a₁, . . . , a_n1) — but, as max(a₁, . . . , a_n1) a_i for 1 i < n, transitivity shows a_n a_i for all i in this range. Hence, an is the maximum element, and our definition computes max correctly.

If the inequalities reversed ,the proof of correctness for minimum proceeds the same.