Requirement
In the following questions, express the algorithms in the pseudocode we use in lectures (in the textbook), and implement your algorithms in the C programming language.
Algorithm 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.
- 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.
- Design a divide-and-conquer algorithm of Θ(n log n) 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.
- 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. Please compare the differences in execution time and theoretical analysis.
Algorithm 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.
- Design a brute force algorithm to solve the convex-hull problem and analyze its efficiency.
- Design a divide-and-conquer algorithm of Θ(n log n) 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.
- Implement the two algorithms and test them using data_2.txt, which includes 30,000 points (pairs of x-y coordinates). Your programs are required to display execution time. Please compare the differences in execution time and theoretical analysis.
Submit
Please submit your design and analysis (i.e. 1.1, 1.2, 2.1, 2.2) in hard-copies to the instructor after the Monday class, and submit your code to Moodle.