$$QUESTION $3$

You are asked to implement in Java an Abstract Data Type $($ADT$)$ that can dynamically

compute the median age of a changing group of people. We assume that there is a maximum

limit to the size of the group, m$.$ This ADT should implement the following API:

MedianGroupAge $($int m$)$ Initialises a MedianGroupAge object

which can compute the median age of

a group of up to m people.

void addPerson $($int age$)$ Adds the age of a new person in the

group.

void removePerson $($int age$)$ Removes the age of a person from the

group.

Integer getMedian $()$ Returns the median age of the people

currently in the group.

A client of this ADT will perform an arbitrary sequence of calls to the methods of the ADT,

$0$ starting with a call to the constructor. You can assume that getMedian is never called with an T

empty group of people.

The median of an even number of ages is the average of the two middlemost ages.

Provide an asymptotically optimal implementation of the methods of this ADT. You should

describe your implementation, calculate its asymptotic runtime and memory performance, and

argue about its optimality.

If you choose, you can use any known ADTs without providing their implementations.

However, for each ADT you use you should provide:

$*$ An API of the ADT, similar to the one given above for MedianGroupAge. The API only

needs to contain the methods you use in your implementation.

o A brief English description of an implementation of the ADT that has the running time and

memory space properties you specify below.

$*$ A tight upper bound of the worst$-$case asymptotic running time of each of the API methods.

e The memory used by the ADT using the asymptotic notation.

$[$T $\{\}\{]$