1. (4 pts.) Unsorting a sorted array. In a recent lecture, we considered the problem of unsorting a sorted array. Let A be an array containing n numbers in sorted order. To unsort A is to move the elements of A so that no two consecutive entries are the same. Our goal is to design an algorithm that outputs an unsorted version of A if it is possible to unsort A and returns cannot_be_unsorted otherwise. Additionally, we want the algorithm to run in O(n) time.

I sketched an algorithm but with some details missing: an implementation for MaxOccurrence(A) that outputs the maximum number of times some number in A occurs and a way to unsorting A when n is odd.

a. (2 pts.) Provide an implementation of MaxOccurrence(A) that runs in O(n) time and explain why it is correct. b. (2 pts.) Next, describe what the algorithm should do when n is odd. Again, implement it in O(n) time and prove correctness like what we did in class. a. (2 pts.) Provide an implementation of MaxOccurrence(A) that runs in O(n) time and explain why it is correct. b. (2 pts.) Next, describe what the algorithm should do when n is odd. Again, implement it in O(n) time and prove correctness like what we did in class