Problem 2 (8 marks, 1.5 pages). Let A be an array of n integers.

a) [2 marks] Describe a brute-force algorithm that finds the minimum difference be-

tween two distinct elements of the array, where the difference between a and b is

defined to be la – b] [1 mark]. Analyse the time complexity (worst-case) of the

algorithm using the big-O notation [1 mark]. Pseudocode/example demonstration

are NOT required. Example: A = [3, -6, 1,-3,20,6,-9,-15], output is 2 = 3-1.

b) [2 marks] Design a transform-and-conquer algorithm that finds the minimum

difference between two distinct elements of the array with worst-case time

complexity O(n log(n)): description [1 mark], complexity analysis [1 mark].

Pseudocode/example demonstration are NOT required. If your algorithm only

has average-case complexity O(n log(n)) then a 0.5 mark deduction applies.

c) [4 marks] Given that A is already sorted in a non-decreasing order, design an al-

gorithm with worst-case time complexity O(n) that outputs the absolute values of

the elements of A in an increasing order with no duplications: description and

pseudocode [2 marks], complexity analysis [1 mark], example demonstration on the

provided A [1 mark]. If your algorithm only has average-case complexity O(n) then

2 marks will be deducted. Example: for A = [-15,-9,-6,-3,1,3,6,20], the output is

B = [1,3,6,9,15,20].