Question $4$

You are asked to efficiently implement an abstract data type $($ADT$)$ that keeps records of

temperatures in various towns around the world at different dates$/$times$.$ This ADT should have

the following public API.

Y

$\{$public class GlobalTemps

GlobalTemps $()$ create an empty object of the ADT

void setTemp$($String town, store a temperature for the given town

Integer timestamp, Integer temp$)|$andtimestamp$.$

Integer getTemp$($String town, return the most recent temperature

Integer ts$)$ recorded for a town, with a timestamp

$\{$ older than or equal to ts$.$

$|$ Integer getMaxTemp $($String town$)$ return the highest temperature

recorded for a town

Note that a timestamp is an integer representation of a date$/$time with the property that more

recent dates$/$times have chronologically higher timestamp values.

You can assume that no two calls to set Temp will have identical town$-$timestamp parameters.

The two get methods should return null when the town is not recorded in the data structure,

or the timestamp requested is older than the oldest recorded temperature for that town.

Your implementation can use internally any known ADT, for which you must provide:

e the name of the ADT, as it is known in the literature,

o the signatures of the relevant APt methods $\{$only those you use$),$ which can $($but do not

need to$)$ employ Java generics,

e the asymptotic worst case running time of these methods, with a justification that

identifies the underlying implementation of the ADT.

Analyse the performance of your GlobalTemps implementation and calculate the worst case

asymptotic running time for each of its methods. In this analysis you should assume that:

o the number of towns stored in the data structure is N$,$

o for each town there are M different temperature measurements

You should calculate running times as functions of both N and M$.$