Introduction: The objective of this homework is to further enhance the understanding of the SELECT, min$-$max finding algorithm, and the application of SELECT algorithm in the Quick$-$Sort

Also, this is an individual submission, and no collaboration is expected.

$1.[$Optimal Max and Min Finding $15$ Pts$]$ In the max and min finding algorithms that we have discussed, we need n$-1$ comparisons. According to our textbook, however, at most $3*$n$/2$ comparisons suffice to find both the minimum and maximum $($pages $214-215)$:

Basic Strategy: Maintain the minimum and maximum of elements seen so far. Don$$t compare each element to the minimum and maximum separately. Process elements in pairs. Compare the elements of a pair to each other. Then compare the larger element to the maximum so far, and compare the smaller element to the minimum so far. This leads to only $3$ comparisons for every $2$ elements.

Setting up the initial values for the min and max depends on whether n is odd or even.

If n is even, compare the first two elements and assign the larger to max and the smaller to min. Then process the rest of the elements in pairs. If n is odd, set both min and max to the first element. Then process the rest of the elements in pairs.

a$)$ Write the above description in algorithmic form. Follow the notations that we have discussed in class $($see the minimum finding algorithm presented on page $214)$

b$)$ Show that your algorithm needs at most $3*$n$/2$