Problem $2$

You are given an array $A$ of $m$ keys $A[0..m-1].$ We want to determine whether the keys are distinct $($and thus answer YES$)$ or are not$-$distinct $($and thus answer NO$).$ Distinct means that no key appears twice or more; not$-$distinct means there is at least one key appearing twice or more. Give an algorithm that is time efficient that solves this problem. Analyze its worst$-$case running time and justify your arguments. $($Time efficient means it cannot be solved asymptotically faster than other methods.$)$

Problem $3$

You are given $n.$keys each one of which is an $A,B,C,$ or D $($say A means freshperson, B sophomore and so on$).$ Sort the keys in worst$-$case linear time $(n)$ so that in the output sequence the As are before $($on the left of$)$ the Bs$,$ which are before the Cs$,$ which are before the Ds$.$