1. (10 points) 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. (10 points) 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(n^{2}) will NOT be marked.

3. (10 points) 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*.