$2$ pts each$)$ For each of the following pairs of functions, f$($x$)$ and g$($x$),$ state whether

$,$

$,$ or both $($i$.$e$.$

$)$

One common data processing task is deduplication: taking an array containing values and removing all the duplicate elements. There exist a wide range of different algorithms for completing this task efficiently. Assume that the array of n values, A$,$ you are using supports three operations,

get$($A$,$ i$)$: Returns the value of the ith element of the array A

search$($A$,$ i$)$: Searches the array A for all elements at indexes larger than i that are the same as the element at index i using a linear search and returns the indexes as a list.

delete$($A$,$ i$)$: Deletes the element at index i from the array by shifting all elements at index i$+1$ to n$-1$ backwards by one.

You may assume that get, as well as the comparison between two elements of the array, require constant time, and that search and delete require linear time. You may assume that the maximum size of the output array of search is a small constant, and so the space and time costs of handling it can be neglected.

$(5$ pts$)$ Propose an algorithm for performing deduplication of an array of elements in place with

space complexity and

worst$-$case time complexity. Prove both the correctness of this algorithm, and its time and space complexity bounds.

$(5$ pts$)$ Deduplication can be made more efficient by using additional memory. Next, propose an algorithm for performing deduplication with

time complexity, and

space complexity. You may use an auxiliary array that supports assignment, but do not use any other data structures and do not sort the data. Prove both the correctness and the time and space complexity bounds of this new algorithm.

$(5$ pts$)$ The UNIX core utilities include a program called uniq, which can perform deduplication on an input stream in linear time, assuming the data is sorted. Given this assumption, propose a new deduplication algorithm that requires

space and time. Prove its correctness.

Consider the Bubble Sort algorithm described in this video.

$(10$ pts$)$ In the video, I showed two approaches for showing that the worst$-$case complexity of Bubble Sort is

$,$ but there are others. Construct a proof of the worst$-$case complexity of Bubble Sort by constructing a recurrence relation describing the number of comparison operations required by the algorithm and solving it$.$

$(10$ pts$)$ Construct a proof of the correctness of Bubble Sort. Make sure that you first formalize the problem of sorting, including what it means for a list to be sorted. Then show that, following the completion of Bubble Sort, it is impossible for this condition to not be satisfied by the array.

$(5$ pts$)$ Determine whether Bubble Sort is

$,$ and prove your answer.