M269-23J_TMA01.pdf

Edit this cell to enter your name and PI. Then run the JavaScript cell below to identify answer and feedback cells. Name:\ PI: In : %%javascript var head=document.getElementsByTagName('head'),style = document.createElement('style' TMA 01 M269 requires all assignments to be submitted electronically,...

Edit this cell to enter your name and PI. Then run the JavaScript cell below to identify answer and feedback cells. Name:\ PI: In : %%javascript var head=document.getElementsByTagName('head'),style = document.createElement('style' TMA 01 M269 requires all assignments to be submitted electronically, by following the link(s) from your StudentHome page to the online TMA/EMA service. If you foresee any difficulty with submitting your assignment on time then you should contact your tutor well in advance of the cut-off date. For further information about policy, procedure and general submission of assignments please refer to the Assessment Handbook, which can also be accessed via your StudentHome page. The learning outcomes assessed by each questions are outlined at the head of the question. In answering this TMA, remember that you can only use the Python data types, methods and functions listed in the chapter summaries, unless specified otherwise within this TMA. If you use an algorithm, data structure or operation that is not allowed in a part of a question, your answer to that part will be awarded zero marks. You may wish to make use of the allowed tool to help you check for any violations. Your TMA should be opened and edited in Jupyter notebooks. Ensure you put your name and PI at the top of this document. You should run the second cell to highlight the answer cells in yellow. All of TMA 01 is in this document. There are two questions worth 100 marks. PART 1 Question 1 (40 marks) You should be able to answer this question after you have studied up to Chapter 4. For Q1(b), it may be helpful to consult 6.4.1 as well. This question tests the following learning outcomes: Understand the common general-purpose data structures, algorithmic techniques and complexity classes. Develop and apply algorithms and data structures to solve computational problems. Analyse the complexity of algorithms to support software design choices. Write readable, tested, documented and efficient Python code. Q1(a) (6 marks) The function definition below is taken from Chapter 4 and describes the general problem of finding the first occurrence of a given character in a given string. Function: first index \ Inputs: text, a string; character, a string \ Preconditions: |character| = 1 \ Output: index, an integer \ Postconditions: if character occurs in text, index is the smallest integer such that text[index] = character, otherwise index = |text| Write a function defintion that finds the second occurrence of any vowel in a given string. If a second vowel is not found, the function should indicate this by returning the length of the string. The vowels do not need to be the same letter or the same case (i.e. uppercase or lowercase). Examples: \ In the string 'Hello', the first occurrence of any vowel is 'e', the second occurrence of any vowel is 'o', so the function would return 4.\ In the string 'Hi', there is no second occurence of any vowel, so the function would return 2. Q1(b) (8 marks) Outline an algorithm in English which will implement the function you defined in question 1(a) An outline in English should not be program code or pseudo-code; see Section 6.4.1 for further guidance on outlining algorithms in English. Not using an English outline will lead to marks being deducted. Write your answer here Q1(c) (10 marks) Implement the function described in Q1(a). Your implementation should broadly match your algorithm from Q1(b); failure to do so will cause a reduction in marks. You can use the tests below to help check if your code is working.\ NOTE that failing the tests is a clear indication you code is faulty, but passing the tests is NOT a guarantee it is correct. Your tutor may run additional tests. In [ ]: #Write your answer here %run -i m269_util test_table = [ ['test 1','aeon',1], ['test 2','yippee',4], ['test 3','mytzlplk',8] ] test(your_function_name, test_table) #Change the function name in this line to match you Q1(d)(i) (6 marks) Chapter 4 of the book provides the following algorithm for finding the index of the first occurrence of a given character in a given string, text: 1. for each index from 0 to |text| - 1: 1. if text[index] = character: 1. stop 2. let index be |text| What, if anything, would need to be changed in the algorithm in order to: find the n-th occurrence of a given character in a given string with n > 0. As above, if the n-th occurence is not found, then index should be set to the length of the string, text. You do not need to write out the algorithm, just identify changes. Write your answer here Q1(d)(ii) (4 marks) Identify the worst-case complexity for the modified algorithm you suggested in Q1(d)(i). Justify your answer. Write your answer here Q1(e) (6 marks) Exercise 4.8.4 in the course book asked you to implement a function that decides whether a string is a palindrom without modifying the input string. Write your code below. The function should: be named is_palindrome accept a single string parameter return a Boolean: True if the string is a palindrome; False otherwise. Your program should consider uppercase and lowercase letters as different, so 'anna' is a palindrome, 'Anna' is not. You can use the tests below to help check if your code is working. NOTE that failing the tests is a clear indication you code is faulty, but passing the tests is NOT a guarantee it is correct. Your tutor may run additional tests. In [ ]: #Write your answer here #Run these tests to ensure your code works %run -i m269_util test_table = [ ['test 1','anna',True], ['test 2','Anna',False], ['test 3','ana',True], ['test 4','anA',False], ] test(is_palindrome, test_table) PART 2 Question 2 (60 marks) You should be able to answer this question after you have studied up to Chapter 7. This question assesses the learning outcomes: Understand the common general-purpose data structures, algorithmic techniques and complexity classes. Develop and apply algorithms and data structures to solve computational problems. Analyse the complexity of algorithms to support software design choices. Explain how an algorithm or data structure works in order to communicate with relevant stakeholders. Write readable, tested, documented and efficient Python code. This question models a simplified restaurant booking system. The software manages table reservations and accommodates walk-in parties without a prior booking. Parties can have a maximum of four people. Each booking has a unique reservation ID which is associated with a single table and one name from the party of patrons. The system does not allow bookings for specific times. Advance bookings are able to choose a specific table number, but walk-in bookings are not. The tables are allocated on a first-come, first-serve basis within the restrictions above, with advance bookings taking priority. Q2(a) (8 marks) The following sequence shows all bookings (advance and walk-in) within the system for a given night. When a table is not allocated, 0 is used in place of a table number. Smith is assigned registration ID 22 and is a walk-in, so is not assigned a table number. Mason booked in advance and requested table 2. They are assigned reservation ID 23. Jones is also a walk-in and is assigned ID 24. They were also not assigned a table number. Nobody is currently assigned table 4. Note that the system does not record the party size. Reservation ID Name Table 22 Smith 0 23 Mason 2 24 Jones 0 If the booking data were to be stored in an array of dicts (instead of in a Python list), explain and justify the assumptions you would need to make. Explain the processes you would need to go through to be able to add a new advance booking for a patron as well as a walk-in booking. Refer to the table above to illustrate your points. Write your answer here Q2(b) (8 marks) The software is being further developed to store whether the whole party is present or not; party complete being 0 indicates the party is incomplete (and so cannot yet be seated), and party complete being 1 indicates the party is complete, and therefore can be seated when a table becomes available. The code below implents this as a class. The as_dict method can be used to return a dictionary of the bookings which can be used for testing purposes. In [ ]: %run -i m269_array class Bookings: """A dynamic array implementation to store bookings. """ def __init__(self): """Create a new empty array. """ self.bookings = DynamicArray(0) def add_booking(self, reservation_ID: int, name: str, table: int) -> None: """Adds a booking to the array. """ size = self.bookings.length() self.bookings.resize(size+1) self.bookings.set_item(size,(reservation_ID, name, table, 0)) def get_party_complete(self, reservation_ID: int) -> int: """Precondition: reservation_ID exists. """ for index in range(self.bookings.length()): booking = self.bookings.get_item(index) if booking == reservation_ID: return booking def as_dict(self) -> None: """Returns dictionary version of the bookings array. """ bookings = {} for index in range(self.bookings.length()): booking = self.bookings.get_item(index) bookings[booking] = booking,booking,booking return bookings Write a problem definition for a function which returns a tuple with two values: the first being the count of bookings with parties which are incomplete and the second being the count of bookings with parties which are complete. Write your answer here Function: \ Inputs: \ Preconditions: \ Output: \ Postconditions: Q2(c) (8 marks) The code below extends the Bookings class by adding a method which, for a given booking reference, will set the party complete value to 1 or 0 if a party becomes complete or incomplete. The code below creates a number of bookings and changes the completeness of one of them. In [ ]: class BookingsExtended(Bookings): def set_completeness(self, booking_number: int, party_complete: int) -> None: for index in range(self.bookings.length()): booking = self.bookings.get_item(index) if booking == booking_number: booking = (booking,booking,booking,int(not booking)) self.bookings.set_item(index,booking) TestQueue = BookingsExtended() TestQueue.add_booking(24,'Howson',11) TestQueue.set_completeness(24,1) TestQueue.add_booking(25,'Linson',12) TestQueue.set_completeness(25,0) TestQueue.add_booking(26,'Wermelinger',13) TestQueue.set_completeness(26,0) TestQueue.add_booking(27,'Hackett',14) TestQueue.set_completeness(27,1) TestQueue.add_booking(28,'Evans',15) TestQueue.set_completeness(28,0) TestQueue.add_booking(29,'Quinn',16) TestQueue.set_completeness(29,1) print(TestQueue.get_party_complete(24)) TestQueue.set_completeness(24,0) print(TestQueue.get_party_complete(24)) Add four different test cases to the table below to thoroughly test the method set_completeness using the data as entered above. Write your answer here Case booking reference party_complete Q2d (10 marks) The restaurant has decided to allow larger bookings. This is implemented by allowing multiple bookings under a single name, each booking being for a single table of up to four patrons. Tables are configured such that two tables seats 5-8 patrons, three tables seats 9-12, and so on. If Howson was to book for a party of 6, they would make two bookings. Each additional booking made would have the next available reservation ID after the one provided, so if Howson was booked under reservation ID 7, there would be a booking for reservation ID 7 and a booking for reservation ID 8, if 8 was available. If Linson has already booked under reservation ID 8, then Howson would have 7 and 9. It can be assumed that the initial reservation ID is available. When large bookings are made, patrons are not allowed to book a particular table number. The code below extends the BookingsExtended class. Amend the add_large_booking method to enable a booking of any party size to be added, with one table being booked per four party members. Any remaining party members would have a final table booked. You can use the tests below to help check if your code is working. NOTE that failing the tests is a clear indication you code is faulty, but passing the tests is NOT a guarantee it is correct. Your tutor may run additional tests. In [ ]: class BookingsLargerGroups(BookingsExtended): def add_large_booking(self, reservation_ID: int, name: str, party_size) -> None: pass #Write your code here #Tests start here TestQueue = BookingsLargerGroups() TestQueue.add_large_booking(8,'Linson',4) TestQueue.add_large_booking(7,'Howson',6) print(TestQueue.as_dict()) #Run this code to ensure code works %run -i m269_util test_table = [ ['One small one large',{8: ('Linson', 0, 0), 7: ('Howson', 0, 0), 9: ('Howson', 0, 0 ] test(TestQueue.as_dict, test_table) In [ ]: #Write your answer here Q2(e) (10 marks) bookings_dict is a dictionary exported from the BookingsLargerGroups class above. This has been provided in case your code above did not work. The dictionary has the booking reference as a key, followed by a tuple of booking name, table number and whether the party is complete (with 1 indicating a complete party, 0 indicating an incomplete party). We assume that keys are returned in the order they were inserted (this is how current Python versions operate). Write a function, tables_ready, which accepts as parameters a dictionary, bookings and an integer, number_of_tables, in that order. The function should return the name of the most appropriate person to call. The most appropriate person to call is always the one with the lowest booking reference whose party is complete and who needs no more than the number of tables available. If there is no suitable person to call, then the function should return an empty string. For the purposes of this question you should ignore the requested table number. You can also assume that all entries for a given name will have the same party complete value. In the example below all Howson's are incomplete, all Hackett's are complete. You can use the tests below to help check if your code is working. NOTE that failing the tests is a clear indication you code is faulty, but passing the tests is NOT a guarantee it is correct. Your tutor may run additional tests. In [ ]: bookings_dict = {7: ('Howson', 0, 0), 8: ('Howson', 0, 0), 9: ('Linson', 0, 0), 10: ('Li #Write your answer here #Run this code to ensure your code works %run -i m269_util test_table = [ ['Single table',bookings_dict,1,"Linson"], ['Four tables',bookings_dict,4,"Hackett"], ] test(#your_function_name, test_table) Q2(f) (16 marks) The manager of the restaurant is concerned about security so the developer has added a hashing aglorithm to encrypt the names before they are stored. This code is implemented in the function below: def enc(t,c): e = '' for ch in t: if 'a'