Your task is to: 1) Give the algorithm (step by step) and explain/justify why it takes about 2 time complexity. 2) Write a program called contactTracing.java, which implements the algorithm in 1. a) Ask the user to input the number of babies in the creche b) Followed by arrival and departure times (separated by ,) for each baby c) Store these data into a data structure d) Apply algorithm 1 on the data structure and determine the pairs

Sample Input How many pairs of baby: 5 Give the times of arrival (i) and departure (j), e.g.: 2,4 2,4 Give the times of arrival (i) and departure (j), e.g.: 2,4 3,6 Give the times of arrival (i) and departure (j), e.g.: 2,4 8,9 Give the times of arrival (i) and departure (j), e.g.: 2,4 10,11 Give the times of arrival (i) and departure (j), e.g.: 2,4 7,11

Sample Output The distinct pairs of babies who are at the crche simultaneously are (1, 2) (3, 5) (4, 5)

Write a 12 page report (max) detailing how you structured your contactTracing algorithm. Explain how you traversed the data structure you used and how to compare the adjacent elements. Your final report should follow as thus:

Introduction (The solution presented in this report is about/summarises ) 2.0 Contact Tracing Algorithmic Solution (Give the stepwise algorithmic solution) 3.0. Explanation of Algorithmic Solution in (2.0) (Explain your solution step by step) 4.0. (Add an appropriate header if you need another section) 5.0. Response to Bonus Question (Improvement and Explanation) (summarise and explain your answer as required) 4) (Bonus Mark) Could we possibly improve on the time complexity of the algorithm in question (2)? If yes, give a detailed algorithm and justification for your answer. If no, also justify your answer with some clear explanation.

Consider a crche that experienced a sudden outbreak of an infection. This infection caused n number of babies to get sick at different periods (NB: n is an integer). For each i=1,,n, a baby that enters the crche at time ai leaves at time di>=ai, suppose we are interested in knowing how many distinct pairs of babies are ever at the crche at the same time? (NB: pair (i,j) is the same as pair (j,i) ). For example, consider Table 2: Suppose there are 5 babies with the following arrival and departure times: Table2: Babies Arrival and Denarture Times at the Crche In table 2, clearly, Baby 1 arrived at time 2 and left at time 4, but note that Baby 2 also arrived at time 3, which is before Baby 1 left the crche. Hence, the number of distinct pairs of babies who are at the crche simultaneously is three: These pairs are {(1,2),(4,5),(3,5)} Considering the input (a1,d1)(a2,d2)(an,dn) as earlier described, there is a straightforward algorithm that takes about n2 time complexity to compute the number of pairs of babies that are at the crche at the same time