2. A list of n distinct integers a1, a2,..., an is called a mountain list if...

  

Transcribed Image Text:

2. A list of n distinct integers a1, a2,..., an is called a mountain list if the elements reading from left to right first increase and then decrease. The location of the peak is the value i where a; is greatest. For example, the list 1, 2, 3, 7, 6 is a mountain list with a peak at 4 since the greatest number occurs in the fourth position. We also consider a list of n increasing numbers to be a mountain list with a peak at n, and a list of n decreasing numbers to be a mountain list with a peak at 1. (a) Give pseudocode for an algorithm based on linear search that takes as input a mountain list a1, a2,,an and returns the location of the peak. procedure LinearPeak(a1, a2,..., an: mountain list) 1. for 1 ton-1 2. if 3. return i 4. return n (b) (5 points) Give an algorithm based on binary search that takes as input a mountain list a1, a2,..., an and returns the location of the peak. procedure BinaryPeak (a1, a2, ..., an: mountain list) 1. i = 1 2. 3. 4. j = n while (i < j) m == [i+1] 5. if 6. i = m +1 7. else 8. j := m 9. return i 2. A list of n distinct integers a1, a2,..., an is called a mountain list if the elements reading from left to right first increase and then decrease. The location of the peak is the value i where a; is greatest. For example, the list 1, 2, 3, 7, 6 is a mountain list with a peak at 4 since the greatest number occurs in the fourth position. We also consider a list of n increasing numbers to be a mountain list with a peak at n, and a list of n decreasing numbers to be a mountain list with a peak at 1. (a) Give pseudocode for an algorithm based on linear search that takes as input a mountain list a1, a2,,an and returns the location of the peak. procedure LinearPeak(a1, a2,..., an: mountain list) 1. for 1 ton-1 2. if 3. return i 4. return n (b) (5 points) Give an algorithm based on binary search that takes as input a mountain list a1, a2,..., an and returns the location of the peak. procedure BinaryPeak (a1, a2, ..., an: mountain list) 1. i = 1 2. 3. 4. j = n while (i < j) m == [i+1] 5. if 6. i = m +1 7. else 8. j := m 9. return i

Answer rating: 100% (QA)

a Linear search will be searching max element so procedure will be procedure Linear... View the full answer