Problem $1.$

$(30$ MARKs$)$ Consider an array of numbers that contain duplicates, i$.$e$.[9,11,9,8,8,23].$ Develop a divide$-$and$-$conquer algorithm to remove duplicates preserving the original order of the elements. For the array above, the algorithm must output $\backslash ([9,11,8,23]\backslash )($specifically$,$ for each duplicate, only the first one must survive$).$ Your algorithm must perform in $\backslash ($ n $\backslash$log n $\backslash )$ time where $\backslash ($ N $\backslash )$ is the size of the input. Your function must have signature remove$\_$duplicates$($A$,$ low, high$)$ where A is an array of length high$-$low $+1.$ Your function must return nothing and update A in place.

$($i$)(10$ marks$)$ Write the algorithm in pseudocode. No explanation is required, just the algorithm. You are not allowed to use sorting for this.

$($ii$)(5$ marks$)$ Compute the time complexity of your algorithm using Master Theorem. Write the details of step counting and justify the use of Master Theorem.

$($iii$)(10$ marks$)$ Using strong induction on the size of the input, prove the correctness of your algorithm.