Question 1.
Let a[0..n-1] be an array of n distinct integers. A pair (a[i], a[j]) is said to be an inversion if these numbers are out of order, i.e., i a[j].
For example: if array a contains the following numbers:
9, 8, 4, 5
then the number of inversions is 5.
(inversions are 9 > 8, 9 > 4, 9 > 5, 8 > 4, 8 > 5)
Write a program that uses the divide-and-conquer techniqueto count the number of inversion in the array.
Question 2. Given two sets of nunique integers A and B, determine if A is equal to B, i.e., all the elements of A are in B.Write a program that uses a transform-and-conqueralgorithm with efficiency class Θ(nlogn) to solve this problem.
Example #1: Enter the number of integers in the sets: 4
Enter the first set: 9 5 3 2
Enter the second set: 3 2 9 5
These two sets are equal.
Example #2: Enter the number of integers in the sets: 6
Enter the first set: 1 4 3 2 8 6
Enter the second set: 1 3 9 4 6 8
These two sets are not equal.
Please note that a program using a brute-force algorithm with efficiency class Θ(n2) will NOT be marked.