PROBLEM 3 30 POINTS Design an algorithm to approximately sort a vector of real numbers in [0, 1] using the following approximation criterion: if the difference between two numbers is less than a tolerance level 8, then the ordering of the two numbers does not matter. The tolerance level 8 is also in the range [0,1], where 8 = 0 denotes an exact sort. For example, if 8 = 0.005, then 0.451 and 0.454 can be sorted as 0.451,0.454 or 0.454, 0.451 since the difference between them is less than 8. Hint: start by considering a case with a large tolerance level, e.g. 8 = 0.1 so that the order of any two numbers within 0.1 of each other does not matter. How would you solve this problem? Then generalize to arbitrary 8 [0,1]. a) Describe your algorithm using pseudocode. Compute the worst-case time complexity for your algorithm using big o notation as a function of the number of elements N and the tolerance level 8. State how your approximate sorting algorithm reduces computation time compared to an exact sorting algorithm. For full credit, design your algorithm to achieve the best possible worst-case big O time complexity. (20 points) b) Implement your algorithm as a C++ function with the following header: (10 points) void approxSort(std::vector& numbers, double tol); The parameter tol denotes the tolerance level 8. Your approximate sort algorithm should sort the vector numbers in place. For full credit, your function needs to perform the approximate sort correctly and terminate in less than 5 minutes wall clock time on a vector of 10,000 elements! Submit your code in a C++ source file named approxSort.cpp! PROBLEM 3 30 POINTS Design an algorithm to approximately sort a vector of real numbers in [0, 1] using the following approximation criterion: if the difference between two numbers is less than a tolerance level 8, then the ordering of the two numbers does not matter. The tolerance level 8 is also in the range [0,1], where 8 = 0 denotes an exact sort. For example, if 8 = 0.005, then 0.451 and 0.454 can be sorted as 0.451,0.454 or 0.454, 0.451 since the difference between them is less than 8. Hint: start by considering a case with a large tolerance level, e.g. 8 = 0.1 so that the order of any two numbers within 0.1 of each other does not matter. How would you solve this problem? Then generalize to arbitrary 8 [0,1]. a) Describe your algorithm using pseudocode. Compute the worst-case time complexity for your algorithm using big o notation as a function of the number of elements N and the tolerance level 8. State how your approximate sorting algorithm reduces computation time compared to an exact sorting algorithm. For full credit, design your algorithm to achieve the best possible worst-case big O time complexity. (20 points) b) Implement your algorithm as a C++ function with the following header: (10 points) void approxSort(std::vector& numbers, double tol); The parameter tol denotes the tolerance level 8. Your approximate sort algorithm should sort the vector numbers in place. For full credit, your function needs to perform the approximate sort correctly and terminate in less than 5 minutes wall clock time on a vector of 10,000 elements! Submit your code in a C++ source file named approxSort.cpp