1. Use strong induction to prove that the algorithm below correctly returns the maximum value for...

  

Transcribed Image Text:

1. Use strong induction to prove that the algorithm below correctly returns the maximum value for every array of size 1 or more. Input: data: array with n integers Input: n: size of data Output: the maximum of data; that is, an element data[m] such that data[m] is greater than or equal to every element of data 1 Algorithm: RecursiveMax 2 if n=1 then 3 | return data[1] 4 else mid=[n/2] Emax RecursiveMax(data[1..mid]) rmax = RecursiveMax(data[mid + 1..n]) if (max rmax then 5 6 7 8 9 return (max 10 else 11 return rmaz 12 end 13 end 1. Use strong induction to prove that the algorithm below correctly returns the maximum value for every array of size 1 or more. Input: data: array with n integers Input: n: size of data Output: the maximum of data; that is, an element data[m] such that data[m] is greater than or equal to every element of data 1 Algorithm: RecursiveMax 2 if n=1 then 3 | return data[1] 4 else mid=[n/2] Emax RecursiveMax(data[1..mid]) rmax = RecursiveMax(data[mid + 1..n]) if (max rmax then 5 6 7 8 9 return (max 10 else 11 return rmaz 12 end 13 end

Answer rating: 100% (QA)

To prove the correctness of the RecursiveMax algorithm for finding the m... View the full answer