Parallel searching In Section 8.1, a lower bound for parallel searching of a sorted input list using comparison operations was obtained and an algorithm was given that matched the lower bound. a....

Parallel searching

In Section 8.1, a lower bound for parallel searching of a sorted input list using comparison operations was obtained and an algorithm was given that matched the lower bound.

a. Obtain a lower bound for parallel searching of an unsorted input list.

b. Provide a parallel search algorithm that matches the lower bound of part (a).

c . Can one improve the lower bound of part (a) or the algorithm of part (b) if the input list is known to be partially sorted in the sense that no element is more than m locations away from its correct position in a sorted input list, where m