COSC122 2022 Semester 2 INTRODUCTION TO ALGORITHMS
Assignment 1: Spotting Stolen Cars
6% of overall grade
Due Part A: 11.55pm on Fri August 19 2022, Part B: 11.55pm on Fri August 26 2022
Copyright By PowCoder代写 加微信 powcoder
1 Assignment Overview 1.1 Introduction
Thanks to advances in computer and network technologies we live in an age of increasingly
pervasive surveillance. As with most things, there are pros and cons to such widespread
Assignment Project Exam Help
surveillance but we will leave the ethical discussion to other courses. This assignment isn’t
going to take sides in the debate—our aim is simply to give you some insight into how data from such surveillance systems might be used efficiently to meet whatever good/evil ends that one might have for the data.
1.2 Due date
Ideally your assignment code should be submitted by Part A: 11.55pm on Fri August 19 2022,
Add WeChat powcoder
Part B: 11.55pm on Fri August 26 2022. However, you can submit it up to one week after those due dates without penalty. If you submit it more than a week late, but no more than two weeks late, you will incur a 15% absolute penalty (in other words, your mark will be the raw mark less 15 marks (given the assignment is marked out of 100). Assignments cannot be submitted more than two weeks after the deadline unless you’ve organised an extension with the course supervisor because of illness etc.
1.3 Submission
Submit via the quiz server. There are two submission pages: one for Part A, and another for Part B. The submission page will be open about a week after the assignment is released. This emphasises the point that the quiz won’t offer much help, as your own testing and the provided unit tests are what you should be using to test your code. The submission quiz will not test your code properly until after submissions close, so submission won’t give you any more information than the provided tests! This means you can start on the assignment straight away.
This assignment is a step up from COSC121/131 so please make sure you start early so that you have time to understand the requirements and to debug your code. The first part uses a very simple algorithm, but you’ll need time to understand the structure you’re working in.
1.4 Implementation
All the files you need for this assignment are on the quiz server. You must not import any additional standard libraries unless explicitly given permission within the task outline. For each section of the assignment there is a file with a function for you to fill in. You need to complete these functions, but you can also write new functions that these functions call if you wish. All submitted code needs to pass the PYLINT style check before it is tested on the quiz server. Please allow extra time to meet the style requirements for this assignment.
1.5 Getting help
The work in this assignment is to be carried out individually, and what you submit needs to be
your own work. You must not discuss code-level details with anyone other than the course
tutors and lecturers. You are, however, permitted to discuss high-level details of the program
with other students. If you get stuck on a programming issue, you are encouraged to ask your
tutor or the lecturer for help. You may not copy material from books, the internet, or other
Assignment Project Exam Help
students. We will be checking carefully for copied work. If you have a general assignment
question or need clarification on how something should work, please use the class forums on
Learn, as this enables everyone to see responses to common issues, but never post your own
program code to Learn (or make it available publicly on the internet via sites like GitHub) .
Remember that the main point of this assignment is for you to exercise what you have learned from lectures and labs, so make sure you do the relevant labs first, so don’t cheat yourself of the learning by having someone else write material for you.
1 Add WeChat powcoder
Check out section 3 of UC’s Academic Integrity Guidance document. Making your code available to the whole
class is certainly not discouraging others from copying.
2 Spotting stolen cars
In this assignment you will be working with the data from a roadside camera based Automatic Number Plate Recogniser (ANPR). You will be carrying out a simplified version of what might be done in reality—so you can focus on a basic implementation. You will be processing a stream of number plates from a single ANPR and making a list of the seen number plates that appear in a list of stolen car plates.
2.1 Task Overview
This assignment takes two different approaches to solving the same problem. Each task re- quires you to make a function that:
• TakestwolistsofuniqueNumberPlateobjects:
1. stolen_plates–platesofstolenvehiclesfromacentraldatabase
2. sighted_plates–platesofvehiclessightedbyanumberplatecamera
• Goes through each sighted plate and searches for a matching plate in the stolen plates list, recording how many comparisons occurred between NumberPlate objects.
• Returns a list of plates sighted by the camera that belong to stolen cars, along with the Assignment Project Exam Help
number of comparisons used.
You will need to use NumberPlate objects, located in classes.py. You do not have to im- plement these data structures, you will just have to interact with them. Details of these data
structures are in the Provided Classes section below.
You are expected to test your code using both your own tests and the provided tests. More
information about testing your code is in the Testing your Code section. Add WeChat powcoder
2.2 Provided classes
2.2.1 NumberPlate
The main class in this assignment is the NumberPlate class, located in classes.py:
• NumberPlate is a repackaged str class, but with the added benefit of being able to keep track of every NumberPlate comparison that is made.
• Allthecomparisonoperatorsfromstr(==,<,>,<=,>=,!=)areavailable – ifaandbareNumberPlates
– expressionslikea < banda == b,etc,willworkasexpected.
• Every time a comparison occurs between two NumberPlate objects, a counter in the StatCounter class is incremented.
• Thisclassholdsallthecomparisoninformationthatyoumightneedtocheckyourcode against. We also use it to verify that you do perform the correct number of comparisons.
• StatCounter.get_comparisons() returns how many comparisons have been made between NumberPlate objects.
• You should be counting how many NumberPlate comparisons your functions do—in a similar fashion to what you did in Lab 1. This count should give the same value as StatCounter, which will be a check that you’re counting comparisons correctly.
2.2.2 Example Code
The following example code should help you further understand the NumberPlate class:
>>> from classes import NumberPlate
>>> from stats import StatCounter
>>> my_numberplate1 = NumberPlate(‘ABC123’) # Create two NumberPlate instances
>>> my_numberplate2 = NumberPlate(‘XYZ789’)
>>> my_numberplate1 # Looking at a single plate object
NumberPlate(‘ABC123’)
>>> my_numberplate1 < my_numberplate2 # Comparing two NumberPlate objects
>>> StatCounter.get_comparisons() #This is allowed only for testing!
>>> my_list = [] # Make a list to put our plates in
Assignment Project Exam Help
>>> my_list.append(my_numberplate2)
>>> my_list
[NumberPlate(‘ABC123’), NumberPlate(‘XYZ789’)]
>>> my_list.append(my_numberplate1)
>>> my_list[0] == NumberPlate(‘ABC123’)
>>> StatCounter.get_comparisons() # See actual comparison count,this is allowed only for testing!
>>> my_list[0] > my_list[1]
>>> StatCounter.get_comparisons() #This is allowed only for testing!
False Add WeChat powcoder
2.2.3 Important Notes on the StatCounter Class
• Notethatbecauseofthewayitisimplemented,itwillnotbehavelikearegularclass. – Donotinitialiseit,ie,counts = StatCounter()-youwillgetanexception.
– ItwillnotworkontheQuizServer!
• Only use the StatCounter.get_comparisons() method for testing. Remove all calls to it from the code you submit to the Quiz Server.
• Removeanyimportsrelatedtostatsfromyourcode—otherwisepylintmightgetup- set about an unused import.
Important: StatCounter will not work on the quiz server! You must do your own comparison counting to get marks.
3 Tasks[100 Marks Total]
3.1 Part A: Sequential/Linear search [40 Marks]
This task requires you to complete the linear_simple_plate_finder function in the linear_finder.py module. This first method isn’t going to be very efficient, but it’s a starting point!
You should start with an empty list representing the stolen number plates that have been sighted by the camera, which will collect the matches found.
Go through each NumberPlate in the sighted_plates and sequentially search the stolen_plates to try find the NumberPlate.
If a match is found add that number plate to the stolen plates sighted so far and stop searching the rest of the stolen_plates for that NumberPlate (it can be assumed that no number plate occurs twice in the stolen list).
Yourfunctionshouldreturnatuplecontainingthepopulatedlistofstolennumber plates that were sighted NumberPlates, and the number of NumberPlate comparisons that the function made (see the example return line in the supplied code).
ThereturnedlistofNumberPlatesshouldbeinthesameorderthattheplatesappear in sighted_plates.
Assignment Project Exam Help
General Notes
You cannot assume that either the stolen_plates or the sighted_plates will be in https://powcoder.com
any particular order.
Think about when it’s OK for your function to stop scanning through the stolen list before reaching the end of that list.
Add WeChat powcoder
Youcanassumethatbothlistsprovidedtoyourfunctionwillonlycontainuniqueele- ments. You should use this knowledge to finish scanning the sighted list earlier in some cases.
We recommend writing your own tests with very small lists first, eg, start out with one plate in each list, then try using one in the first list and two in the second list, etc, …
The provided tests are really just a final check — they won’t help you very much when debugging your code. Remember you can do some initial test with simple lists of num- bers and then switch to testing with lists of NumberPlate objects.
Important: Part A of this assignment is due: 19/08/2022 Part A: Theory Questions [6 Marks]
What is the worst case big-O complexity for the number of comparisons made by the linear/sequential method (to identify all stolen cars sighted by the camera) given there
are n items in the stolen list and m items in the sighted list. Note, you can include both m and n in your answer. Explain how this would come about and give a small example of worst case input.
2. What is the best case big-O complexity for the number of comparisons made by the linear/sequential method (to identify all stolen cars sighted by the camera) given there are n items in the stolen list and m items in the sighted list, AND n > m. Note, you can include both m and n in your answer. Explain how this would come about and give a small example of best case input.
3. Givetheequationforthenumberofcomparisonsusedbythelinear/sequentialmethod (to identify all stolen cars sighted by the camera) given there are n items in the stolen list, n items in the sighted list AND that all the number plates in the sighted list are also in the stolen list. NOTE: you are giving an equation for the exact number of compar- isons made, NOT the big-O complexity.
3.3 Part B: Binary Search [50 Marks]
In the first task, we made no guarantees about the order of the number plates. If we guarantee the stolen list is sorted (in lexicographic order) can we make a more efficient program?
ThistaAskresqusiriesgyonutomcomeplnetethePbirnaoryj_seimcplte_pElatxe_afimnderfuHnctieonlinpthe
binary_finder.py module. It should generate the list of stolen number plates that were
sighted by the camera, using binary search to find each NumberPlate from the sighted_plates
in the stolen_plates. You can assume the stolen list will be sorted. https://powcoder.com
• Again, start with an empty list to accumulate the stolen number plates that have been sighted by the camera.
• Go through each NumberPlate in the sighted_plates and perform a binary search, Add WeChat powcoder
trying to find that NumberPlate in the list of stolen plates.
• AhelperfunctionthatdoesabinarysearchforaniteminasortedlistandreturnsTrue/-
False along with the number of comparisons used could be helpful here.
• Ifamatchisfoundaddthatnumberplatetothestolenplatessightedsofar.
• Yourfunctionshouldreturnatuplecontainingthepopulatedlistofstolennumber plates that were sighted NumberPlates, and the number of NumberPlate comparisons that the function made (see the example return line in the supplied code).
• ThereturnedlistofNumberPlatesshouldbeinthesameorderthattheplatesappear in sighted_plates.
3.3.1 General Notes
• Important:Yourbinarysearchmustonlydoonecomparisonperloopwhenitissearch-
ing the stolen list and should only compare number plates for equality once. This ap-
proach will basically narrow the search down to one number plate and then check if that is the one being searched for. This method will be discussed in lectures and labs; it is not the commonly given form of a binary search algorithm (which makes two com- parisons per loop).
3.4 Part B: Theory Questions [4 Marks]
1. What is the worst case big-O complexity for the number of comparisons made by the binary search method (to identify all stolen cars sighted by the camera) given there are n items in the stolen list and m items in the sighted list. Explain how this would come about and give a small example of worst case input.
2. 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 stolen list and m items in the sighted list. Explain how this would come about and give a small example of best case input.
Assignment Project Exam Help https://powcoder.com
Add WeChat powcoder
Important: Binary search can be difficult to implement correctly. Be sure to leave sufficient time to solve this task.
4 Testing Your Code
There are two ways to test your code for this assignment (you are required to do both): • Writingyourowntests–usefulfordebugingandtestingedgecases
• Usingtheprovidedtestsintests.py–afinalcheckbeforeyousubmit
The tests used on the quiz server will be mainly based on the tests in tests.py, but a small number of secret test cases will be added, so passing the unit tests is not a guarantee that full marks will be given for that question (it is however a strong indication your code is correct; and importantly, failing the test indicates that something fundamental may be wrong). Be sure to test various edge cases such as when an input list is empty or when no number plates are sighted etc. . .
4.1 Writing your Own Tests
In addition to the provided tests you are expected to do your own testing of your code. This should include testing the trivial cases such as empty parameters and parameters of differing sizes. You will want to start by testing with very small lists, eg, with zero, one or two items in each list. This will allow you to check your answers by hand.
Assignment Project Exam Help
4.1.1 Provided Data for Testing
The utilities.py module contains functions for reading test data from test files. https://powcoder.com
Test files are in the folder test_data to make it easier to test your own code. The test data files are named stolen[s]-sighted-matches-seed.txt, where:
• stolen=thenumberofstolenplatesinthefile
Add WeChat powcoder
• sisoptionalandindicatesthattheyareinsortedorder
• sighted=thenumberofplatesinthelistthatweresightedbythecamera
• matches = the list of expected plates (in the order your functions should return them) which is used for testing
• seed=theseedvaluethatwasusedwhengeneratingthetestfile.
For example 10-20-5-a.txt was generated with a as the random key and contains 10 stolen plates and 20 sighted plates, where 5 of the sighted plates were in the stolen list. If the file name was 10s-20-5-a.txt then the stolen plates would be provided in sorted order— obviously useful for testing your binary search function.
You should open some of the test data files and make sure you understand the format— remember to open them in Wing or a suitably smart text editor. If you are using windows then try Notepad++ because the normal Notepad is pretty horrible. If you are using Linux (or a Mac) then almost any text editor will do.
The test files are generated in a quasi-random fashion and the seed suffix indicates the ran- dom seed that was used when generating the data—you don’t need to worry about this. But, you do need to worry about the fact that we can easily generate different random files to test with.
4.1.2 Provided Tools for Testing
The read_dataset function in utilities.py reads the contents of a test file and returns three lists. The lists all contain NumberPlate objects. The first list contains the number plates of stolen vehicles, the second contains all the number plates that were seen by the camera and the third contains the stolen number plates that were seen by the camera (this third list is the plates that your functions should return).
The following example shows how to use the utilities module:
>>> from utilities import read_dataset
>>> filename = ‘./test_data/5-5-2-a.txt’
>>> stolen, sighted, matches = read_dataset(filename)
>>> print(stolen)
[‘IQ1998’, ‘FS1860’, ‘JI9400’, ‘NN3705’, ‘AS0734’]
>>> print(sighted)
[‘AR3546’, ‘QT0780’, ‘NN3705’, ‘PB2873’, ‘AS0734’]
>>> type(stolen[0])
>>> filename = ‘./test_data/5s-5-2-a.txt’
>>> stolen, sighted, matches = read_dataset(filename)
>>> print(matches)
[‘NN3705’, ‘AS0734’]
Assignment Project Exam Help
>>> print(stolen) # the same list as before but sorted https://powcoder.com
[‘AS0734’, ‘FS1860’, ‘IQ1998’, ‘JI9400’, ‘NN3705’]
Add WeChat powcoder
Off-line tests are available in the tests.py module:
• These tests are not very helpful for debugging–do your own smaller tests using hand
workable examples when debugging!
• Youshouldusethemtocheckyourimplementedcodebeforesubmission:thesubmis-
sion quiz won’t fully mark your code until submissions close.
• TheprovidedtestsusethePythonunittestframework.
– Youarenotexpectedtoknowhowthesetestswork,ortowriteyourownunittests
– Youjustneedtoknowthatthetestswillcheckthatyourcodefindsthelistofstolen number plates that were sighted, and that the number of comparisons that your code makes is appropriate.
4.2 Provided tests
4.2.1 Running the Provided Tests
The tests.py provides a number of tests to perform on your code:
• Theall_tests_suite()functionhasanumberoflinescommentedout:
– Thecommentedouttestswillbeskipped.
– Uncommenttheselinesoutasyouprogressthroughtheassignmenttaskstorun
subsequent tests.
• Runningthefilewillcausealluncommentedteststobecarriedout.
• Each test has a name indicating what test data it is using, what it is testing for, and a contained class indicating which algorithm is being tested.
• In the case of a test case failing, the test case will print which assertion failed or what exception was thrown.
Assignment Project Exam Help
Important: In addition to the provided tests you are expected to do your own testing of your code. This should include testing the trivial cases such
as empty lists and lists of differing sizes.
• 16August2022:Updatedtheoryquestionwording
https://powcoder.com Add WeChat powcoder
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com