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 j but a[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 technique to count the number of inversion in the array. Describe briefly in a separate file how your divide-and-conquer algorithm works.
2. Given two lists of n integers A, B and a sum S, where all the elements in each list are unique, write a program that uses a transform-and-conquer algorithm with efficiency classT(nlogn) to decide whether there is an integer from A and an integer from B such that the sum of these two integers is equal to S.
For example, if A = {8, 3, 4, 7} and B = {5, 6, 12, 1} and S is 10, then your program should output "4 + 6 = 10" (where 4 is from A and 6 is from B)
Another example, if A = {1, 5, 4, 2} and B = {6, 3, 2, 1} and S is 9, then your program should output "No two integers from A and B add up to 9"
Describe briefly in a separate file how your transform-and-conquer algorithm works.Please note that a program using a brute-force algorithm with efficiency classT(n2) will NOT be marked.
3. Write a program that implements the distribution counting sort algorithm as discussed in class to sort a list of letters from a small set {a, b, c, d}. For example, the list contains b, a, c, c, d, d, a, your program should output a, a, b, c, c, d, d.