Problem 3. (a) Suppose the entering freshmen class at some university has N students The information pertinent to each student in the class (name, sex identification number, etc.) can be found in some element of A, an array of records indexed from 1 to N. Assume the records are in some random order, and that we wish to rearrange the array so that all the female records precede all the male records. Give a linear (O(N)) time algorithm which performs this "partial sort" on A. Assume "sex" is a field in each record, with value Male" or Female". (b) Let A and B be two sequences of n integers each. Given an integer m describe an O(n logn) time algorithm for determining if there is an integer a in A and an integer b in B such thatm-a-b