1. A[0..n 1] is an array of n distinct numbers. A pair of array members (A[i], A[j]) is called an inversion if A[i] > A[j] for i < j.

1.1 Design a brute force algorithm to count the number of inversions in an array, analyze the number of executions of the basic operation, and determine the efficiency class.

1.2 Design a recursive divide-and-conquer algorithm of (nlogn) to count the number of inversions in an array, create a recurrence to analyze the number of executions of the basic operation, and determine the efficiency class. Use the Master Theorem to verify the efficiency class in your analysis result.

1.3 Implement the two algorithms, and test them by using data 1.txt, which includes 50,000 integers. Your programs are required to display execution time. Compare the differences in execution time and theoretical analysis.

2. The convex hull of a set of S is the smallest convex set containing S. (You can find more about the convex hull problem on pages 109-113 in the textbook.) It is assumed that not all the points in S are on a straight line.

2.1 Design a brute force algorithm to solve the convex-hull problem and analyze its efficiency.

2.2 Design a recursive divide-and-conquer algorithm of (nlogn) to solve the convex-hull problem, create a recurrence to analyze the number of executions of the basic operation, and determine the efficiency class. Use the Master Theorem to verify the efficiency class in your analysis result.