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: Rahies Arrival and Denarture Times at the Crche In table 2, clearly, Babyl 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. oour task is to: TY \&file CAPF) Give the algorithm (step by step) and explain/justify why it takes about n2 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 3) Write a 1-2 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: CSC 211 Practical 2 Report (Name, Surname and Student number) 1.0 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. NB: We will use some other random test cases to check the correctness of your code. So please pay attention to your solution. 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 Fhe distinct pairs of babies who are at the crche simultaneously are (1,2)(3,5)(4,5) 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: Rahies Arrival and Denarture Times at the Crche In table 2, clearly, Babyl 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. oour task is to: TY \&file CAPF) Give the algorithm (step by step) and explain/justify why it takes about n2 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 3) Write a 1-2 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: CSC 211 Practical 2 Report (Name, Surname and Student number) 1.0 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. NB: We will use some other random test cases to check the correctness of your code. So please pay attention to your solution. 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 Fhe distinct pairs of babies who are at the crche simultaneously are (1,2)(3,5)(4,5)
