## 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.