Question 1    The Cheapest Fridge

[30 marks] Song wants to buy a fridge with volume at least V cubic centimetres. The shop sells a large variety of fridges.  More precisely, for each positive integer x, the shop sells a fridge for x dollars with the following dimensions:

• width 3x centimetres,

• depth 2x + 1 centimetres and

• height 2x  centimetres.

1.1    [12 marks] Design an algorithm which runs in O(log V) time and finds the minimum amount that Song must spend to buy a suitable fridge.

1.2    [18 marks] Design an algorithm which runs in O(log(log V)) time and finds the minimum amount that Song must spend to buy a suitable fridge.

You may choose to skip 1.1, in which case your answer to 1.2will be marked as your answer to 1.1 also.

Question 2    Counting Occurrences

[30 marks] Answer the following:

2.1    [6 marks] Let X = [x1 , . . . ,xn] be a sorted array of n positive integers. Design an algorithm to count the number of occurrences of each distinct integer in X in worst case O(n) time.

2.2    [12  marks] Let Y  =  [y1 , . . . ,yn] be  an  unsorted  array of n positive integers.   Design an algorithm to count the number of occurrences of each distinct  integer in Y in expected  O(n) time.

2.3    [12 marks] Let Z = [z1 , . . . ,zn] be a sorted array of n positive integers. You are also given an integer k ≤ n, the number of distinct integers in this array.  Design an algorithm to count the number of occurrences of each distinct integer in Z in worst case O(k log n) time.

Question 3    Counting Inversions Between Arrays

[20 marks] Let A and B be two arrays of length n, each containing a random permutation of the numbers from 1 to n. An inversion between the two permutations A and B is a pair of values (x,y) where the index of x is less than the index of y in array A, but the index of x is more than the index of y in array B .