Description

Assignment 2 (100%)
In the following questions, express the algorithms in the pseudocode we are using (in the textbook and lecture slides), and implement your algorithms in the C programming language.
1. (40%) A[0..n − 1] is an array of n distinct numbers. A pair of array elements (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 its 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, set up a recurrence to analyze the number of executions of its basic operation of the best case, 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 the numbers of inversions and execution time. Compare the two algorithms in execution time and theoretical analysis.
2. (60%) S is a set of points in a 2-dimensional plane. The convex hull of set S is the smallest convex set containing S. (Please find more about the convex hull problem, especially the definition of extreme point, 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, set up a recurrence to analyze the number of executions of the basic operation of the best case, and determine the efficiency class. Use the Master Theorem to verify the efficiency class in your analysis result.
2.3 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 the number of points on the convex hull and their x-y coordinates (sorted by their x coordinates). Your programs are also required to display execution time. Compare the two algorithms in execution time and theoretical analysis.
Note: Write your own code for this assignment. NO code from any source is allowed.
1