Consider the element distinctness problem: Given an array A storing n integers, determine whether all the elements in the array are distinct or not. That is, if all the elements in A are unique, return true; return false if there is at least one duplicate element in A. Below four different problem instances are provided; elements bolded are duplicate elements.

a) Write pseudocode for the algorithm b) Prove your algorithm is correct, do this by proving the two following parts: i) Show that the algorithm terminates in nite time. ii) Show that the algorithm always produces the correct output.

0 1 23 4 5 6 1| 23 1 234 alse 0 1 2 3 0 1 234 5 41 22 6 8 false true 0 1 234 5 6 7 1098643 2|1 true