Reference no: EM132603709
COSC122 Introduction To Computer Science - University of Canterbury
Assignment - Testing times
This assignment is based around matching quarantined people with their Covid-19 test results, if they have any. It is very loosely based on a Stuff article titled 50 people released early from quarantine without coronavirus test, an excerpt is given below. Basically the Ministry of Health took a long time to answer the simple question, how many of the people released from quarantined had been tested for Covid-19? In this assignment you will look at a couple of ways that could be used to match records from two different databases.
In this assignment the basic task will be to take a list containing the names of quarantined people and generate a list that contains the test results for any people that can be found in the ministry's list of tested people. The quarantined list will just have names as the quarantine hotels forgot to take down everyone's NHI (National Health Index) number whereas the ministry's list of tested people will contain the NHI, name, and result for each of those people.
The ministry of health had to be very careful to make sure they matched the records for quarantined people with their test records (eg, matching name, date of birth, etc) you will just need to look for matching names. You should be able to see that it's not too hard to expand to more precise matching methods.
For each task of the assignment you will be required to write a function that takes a list of test results and a list of quarantined people, and returns a list containing the quarantined peoples' test results, or lack thereof. The functions will need to count the number of times Name objects are compared and return this count along with the list of results-as a measure of the work done.
You can assume that there are no duplicate names in either the tested list or the quarantined list, ie, within either list no name will appear more than once.
The file tests.py provides you with a suite of tests to help you check your implemented code before submission. These tests use the Python unit-test framework and you are not expected to fully un- derstand how they work; you just need to know that the tests will check that your code generates the correct list of output, and that the number of comparisons that your code makes is appropriate. For the linear algorithm you should be able to match the exact number of comparisons, but for the binary algorithm the number of comparisons just needs to be in the right ballpark. If you think that you have an implementation that is very close to the test range, and works reliably, you can ask to have the ex- pected number of comparisons range reconsidered. The tests used on the quiz server will be mainly based on these unit-tests, but with a small number of added secret test cases. Therefore passing the unit tests is not a guarantee that full marks will be given (however it's a good indication your code is working as required).
Tasks
Finding results using linear/sequential search
This task requires you to complete the linear_result_finder function in linear_module.py us- ing a sequential/linear search when looking up names in the tested list. This approach is designed to model the worst case scenario and isn't going to be very efficient, but it gives a good baseline. You should start with an empty list representing the results found so far. Go through each Name in quarantined and sequentially search tested to try to find that Name. If a match is found add a (Name, nhi, result) tuple to the results list and stop searching the rest of the tested list for that Name (as it can be assumed that no name will appear twice in the tested list). If a match isn't found then add a tuple with (the_name, None, None) to the results list as you don't have a NHI num- ber or result for that person. You cannot assume that the Names will be in any particular order in either tested or quarantined. The returned list should be given in the same order that the names appear in the quarantined list. Your function should return a tuple containing the results list and the number of Name comparisons the function made, ie, a tuple in the form (your_results_list, comparisons_used).
Finding results using binary search
This task requires you to complete the binary_result_finder file binary_module.py.
The tested list will be in alphabetical order by name (ie, the <= operator is true between any suc- cessive names in tested) but you may not assume anything about the order of quarantined. Given that the tested list is sorted you will be able to employ a binary search and get considerably better performance than the sequential search.
Again, you should start with an empty list representing the results for quarantined people. Then you should go through each Name in quarantined and perform binary search on the tested list to try find that Name. If a match is found, append a tuple containing (Name, nhi, result) to the results list. If a match isn't found then add a tuple with (Name, None, None) to the results list as you don't have a NHI number or test result for that person. The returned list should be given in the same order that the names appear in the quarantined list.
To get full marks in this question you must minimise the average number of comparisons made- assuming that not many quarantined people have been tested. Therefore, you must implement your binary search in such a way that only uses only one Name comparison per halving of the search area. That is, your search should use the equality (==) operator at most once per name that is being looked up. Basically, you shouldn't be comparing Name objects for equality (ie, with ==) inside the while loop of the binary search.
Your binary_result_finder should return the results list and the number of comparisons as a tuple in the same form as the linear function, ie, in the form (your_results_list, comparisons_used). As for the linear function, your binary function shouldn't mutate the lists it is given in any way, eg, don't pop anything off the quarantined or tested list and don't insert anything into them either. You will, of course, need to append things to your results list, and this is fine.
Warning: fast binary search is difficult! Set aside a lot of time to get this right, and don't be put off if it doesn't work correctly straight away. You should test your function using some simple lists, eg, set the tested list to have names 'b', 'c', 'd', 'e', 'f' then make a quarantined list containing just 'b' and check that 'b' is reported in the results list. Then try with 'c', etc, until your are convinced that your function will find any name in the tested list. Then, try some names that aren't in the tested list, eg, 'a' or 'z'.
Analysis questions
The submission quiz will also ask you to answer the following questions. For each question in this section you can assume there are no duplicates in tested or quarantined. You should also answer with respect to the overall task in each case, ie, with respect to generating the complete list of results for the quarantined people which is what each of your result finder functions is doing. For example, the first question below is basically asking what is the worst case big-O complexity for the total number of name comparisons used by your linear_result_finder function.
• What is the worst case big-O complexity for the number of comparisons made by the linear/se- quential method given there are n items in the tested list and m items in the quarantined list. Explain how this would come about and give a small example of worst case input.
• What is the best case big-O complexity for the number of comparisons made by the linear/se- quential method given there are n items in the tested list and m items in the quarantined list, AND m < n. Explain how this would come about and give a small example of best case input.
• Give the equation for the number of comparisons used by the linear/sequential method given there are n items in the tested list, n items in the quarantined list AND that all the names in the quarantined list are also in the tested list. NOTE: you are giving an equation for the exact number of comparisons made, NOT the big-O complexity.
• What is the worst case big-O complexity for the number of comparisons made by the binary search method given there are n items in the tested list and m items in the quarantined list. Explain how this would come about and give a small example of worst case input.
• What is the best case big-O complexity for the number of comparisons made by the binary search method given there are n items in the tested list and m items in the quarantined list. Explain how this would come about and give a small example of best case input.
Attachment:- Introduction To Computer Science.rar