M269-23J_TMA02.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 02 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 02 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 02 is in this document. There are two questions worth 100 marks. PART 1 Question 1 (50 marks) You should be able to answer this question after you have studied up to Chapter 5. 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. Explain how an algorithm or data structure works in order to communicate with relevant stakeholders. Write readable, tested, documented and efficient Python code. Jo sells second hand car tyres. Jo organises the tyres in stacks. So that they do not fall over, Jo ensures that each stack is organised such that any tyre is on top of a tyre with the same or wider diameter. This question will present a simulation of some of the processes that Jo may use while operating the tyre shop. Note: This content has been simplified for the question. The module team is aware that tyres are not sold by diameter. Q1(a) (12 marks) Jo has represented each stack of tyres as a stack ADT using the LinkedStack implementation (see 7.1.3). Each element in the stack is an integer representing the tyre diameter in millimetres. The whole shop is represented as a dictionary of stacks, with the stack being the value and the key being one or more uppercase letters which Jo uses to identify the stack. The following code creates two stacks of tyres (A and B) and adds some sample tyres to them. tyre_shop = dict() tyre_shop['STACK_A'] = LinkedStack() tyre_shop['STACK_A'].push(330) tyre_shop['STACK_A'].push(310) tyre_shop['STACK_B'] = LinkedStack() tyre_shop['STACK_B'].push(410) The results of this are illustrated below: image When a new tyre is received into stock, Jo needs to identify the most suitable of the existing stacks to put it on. Jo does this by applying two rules: 1. The diameter of the top tyre must be as close as possible to the new tyre without being smaller than the new tyre. 2. The candidate stack must be as short as possible. Rule 1 takes priority over rule 2. Example: Stack C contains 3 tyres, the top one being 200mm. Stack D contains 2 tyres, the top one being 300mm. Stack E contains 4 tyres, the top one being 200mm. Note this example discounts stacks A and B from the prior example. If the new tyre was 190mm, Jo would choose stack C since: The top tyre on the stack is the closest size to the new tyre without being smaller than it. It is shorter than the other potential stack, E. Stack D is discounted as, although it is shorter than the other stacks, it does not meet the criteria of rule 1. Note that if stack E were only 3 tyres high, then Jo's method would give both stack C and stack E as options. Q1(a)(i) (8 marks) Outline an algorithm in English which will return a list of the stack keys which are suitable candidates for the new tyre to be placed on, according to Jo's rules above. 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(a)(ii) (2 marks) If you were to translate your code from Question 1 Part (a)(i), you would have to use a method from the LinksedStack class to examine data within the stack. Identify which method you would use and justify your decision. Write your answer here Q1(a)(iii) (2 marks) Identify the type of search carried out. Justify your choice of search technique. Write your answer here Q1(b) (18 marks) The file m269_tyre_shop.py implements the tyre shop dictionary as a class, TyreShop , and adds the following methods: add_stack (to add a given stack name to the dictionary) add_tyre (to add a given tyre diameter to a given stack name if possible and return success or failure) remove_tyre (to remove the top tyre from a given stack name, returning the diameter of the tyre removed) check_tyre (to return the diameter of the top tyre of the stack with the given stack, without removing it from the stack) is_empty (to return a Boolean indicating whether a stack is empty or not) top_tyres (returns a dictionary of stack names mapped to the top tyre diameters) get_stack_height (returns an integer height of a given stack name) show (a helper method to print out a visible representation of the stacks. This may help you in debugging!) Jo is now considering the process of searching for exisiting tyres in the stacks. As Jo always tries to put tyres on the most suitable stack, they assume that the tyre they are searching for is most likely to be in the stack(s) with the closest diameter top tyre, as long as that diameter is either equal to or smaller than the tyre being searched for. Q1(b)(i) (15 marks) Complete the Python function below which returns a list of stacks that a given tyre could be in. The list should be ordered so that the most likely stack is first and the least likely stack should be last. If it is not possible for the tyre to be in a stack, then that stack should not be included. You should use at least one appropriate divide and conquer technique in answering this question. You should implement your own sorting technique rather than using any existing Python methods. You can use the tests below to help check if your code is working.\ NOTE that failing the tests is a clear indication your code is faulty, but passing the tests is NOT a guarantee it is correct.\ Your tutor may run additional tests. In [ ]: %run -i m269_tyre_shop #Tyre shop class %run -i m269_tyre_shop_test_data #Test data for your function %run -i m269_util #Utilities for testing data def get_stacks_to_search(shop_to_search: TyreShop, tyre_to_find: int) -> list: pass #Write your answer here test_table = [ ['150',tyreshop,150,[('A', 190), ('B', 200), ('D', 400), ('E', 400), ('F', 400), ('G ['450',tyreshop,450,[]], ] test(get_stacks_to_search, test_table) #Ensure the function name in this line matches yo Q1(b)(ii) (3 marks) Identify where you used a divide and conquer technique in Q1(b)(i). Justify your choice of using this technique. Write your answer here Q1(c) (20 marks) As the diameter of each tyre is written on the sidewall, the only way for Jo to find if a particular diameter tyre is in a given stack of tyres is to take off the tyre above it, and then inspect the resulting new top tyre. This process is repeated until the tyre needed is found in the given stack or the stack is empty. Jo has to rebuild the stack afterwards. As Jo’s tyre shop is very tightly packed, there is not much room to move tyres around. Jo leaves two empty stack spaces, MOVEA and MOVEB, which can be used to build temporary stacks of tyres while a particular stack is being searched. Note that Jo is not removing the tyre. Write an operation to implement the definition below to find whether a tyre of tyre diameter is within stack name within tyre shop. You should make use of a recursive technique and may create additional functions or operations if you wish. Operation: tyre in stack \ Inputs/Outputs: tyre shop, a TyreShop\ Inputs: tyre diameter, an integer, stack name, a string\ Preconditions: stack name exists within tyre shop, MOVEA and MOVEB exist within tyre shop and are empty stacks.\ Output: found a Boolean\ Postconditions: tyre found is true if tyre diameter is found within stack name, else false; MOVEA and MOVEB are empty; stack stack name has the same contents and order as it did prior to operation call. You can use the tests below to help check if your code is working.\ NOTE that failing the tests is a clear indication your code is faulty, but passing the tests is NOT a guarantee it is correct.\ Your tutor may run additional tests. Note This is a challenging question designed to encourage you to explore recursive solutions to problems. While you are encouraged to tackle the problem recursively, some marks are available if you complete the question in a non-recursive manner. You might like to research the "Towers of Hanoi" when tackling this question. In [ ]: #Write your answer here #Tests tyreshop.show() test_table = [ ['Exists at top',tyreshop,190,'A',True], ['Exists in middle',tyreshop,200,'A',True], ['Does not exist',tyreshop,7,'A',False], ] test(tyre_in_stack, test_table) #Ensure the function name in this line matches your fun tyreshop.show() PART 2 Question 2 (50 marks) You should be able to answer this question after you have studied up to Chapter 10. 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. Explain how an algorithm or data structure works in order to communicate with relevant stakeholders. Write readable, tested, documented and efficient Python code. The M269 module team enjoys playing board games and have developed a simple game where the board consists of a number of adjoining territories. Each player owns one or more territories and places one or more armies in each territory. This can be represented as a graph. The following code implements a territory as a class: class Territory: """A territory for a board game""" def __init__(self, territory_name: str, owner: str, armies: int): """Initialise name, owner and armies""" self.territory_name = territory_name self.owner = owner self.armies = armies def __str__(self): return self.territory_name We have modelled one continent (a group of territories) of the game, Australasia, as well as implementing the Territory class, in the m269_territories file. The graph of the continent is shown below. Do not worry about the names being cut off, this is just a limitation of the drawing. In [ ]: %run -i m269_digraph #The M269 undirected graph code %run -i m269_ungraph #The M269 directed graph code %run -i m269_territories #Create the territories australasia.draw() Q2(a) (2 marks) Identify two nodes which are not adjacent to one another. Write your answer here Q2(b) (2 marks) What is the degree of New Guinea? Write your answer here Q2(c) (4 marks) You have been introduced to a number of different types of graph in M269. Identify two reasons why the graph shown in Q2 above is not a binary tree. Write your answer here Q2(d) (2 marks) Cycles can be useful for resupply routes within the game. Identify every distinct cycle within the graph shown above. Write your answer here Q2(e) (6 marks) Defensible territories are those with the fewest neighbours, while vulnerable territories are those with the largest number of neighbours. Write a function which meets the following function definition to identify the territory or territories with the highest number of neighbours. Function: list vulnerable territories\ Inputs: board_game an UndirectedGraph\ Preconditions: True\ Output: vulnerable territories, a list of nodes\ Postconditions: vulnerable territories is a list of nodes that have the highest degree, or is blank if empty graph. Example\ If there territory X has 4 neigbours, and territory Y and Z have 6 neighbours, then the function should return ['Y', 'Z'] A far larger graph, board_game , has been produced for you (in the file m269_territories) to test this function. There are too many nodes to plot automatically here, but it is similar to the image below. Note that in this example colours are used to denote players and the numbers indicate the number of armies within the territory. This is for indication only and has no impact upon this question. image In [ ]: #Write your answer here #These lines for testing - don't worry if you don't understand how they work! print('passed') if (set([NAfrica,EAfrica,SEurope,Ukraine,MEast,China,Ontario]) == set(li for territory in list_vulnerable_territories(board_game): print(territory) Q2(f) (6 marks) We have chosen a particular representation of the graph to work with the code we have implemented. The graph could have been represented as: an adjacency list an adjacency matrix or a node/edge list. Describe the pros and cons of each method in the context of the board_game graph. Write your answer here Q2(g) (10 marks) Upon their turn, a player can “attack” an adjoining territory by rolling a dice against the defender’s dice. If the attacker’s die is highest, they win and the defender loses an army. If the attacker’s die is lowest, they lose and remove one of their own armies. If the dice are equal, then they roll again. The attacker has to leave at least one army in their existing territory and, upon winning, has to move at least one (and as many as they like up to the amount they have available) into the defeated territory. A player cannot move through or attack their own territories. Therefore, regardless of how many armies they have in a given territory, the territories they can move into from a given starting point may be limited. image In the image above, the owners are designated by different colours. Eastern Australia is owned by a player designated yellow. New Guinea and Western Australia are owned by a player designated orange. Indonesia is owned by a player designated pink. Siam is owned by a player designated green. Ignoring the number of armies as written on the map, the orange player could, from Western Australia: attack Eastern Australia, but that is as far as they could go. atack Indonesia and then Siam. not attack Siam directly from Western Australia, as they cannot travel through New Guinea. image In this example, from Western Australia the orange player can only attack into Eastern Australia. As they own Indonesia, Siam now becomes inaccessible from Western Australia. Again, in this image we have to ignore the number of armies as the image is for illustration only. Create a function, possible_routes , which, given a graph and a starting node, will return a graph with possible routes to all connected territories other than their own. When you run the test you should get something that looks like this: image In [ ]: def possible_routes(graph: DiGraph, start: Hashable) -> DiGraph: #Write your answer here pass #If your code works, the following should draw a path: #Indonesia -> Western Australia -> Eastern Australia -> New Guinea path = possible_routes_AL(australasia,Indonesia) path.draw() Q2(h) (18 marks) We have created a weighted digraph, with edge weightings being the number of armies it is expected to be needed to take the territory from the point of view of the attacker. Given a map that looks like this: image A slightly extended Australasia, australasia_w graph will look like this, with the weights being the number of armies the attacking player, dark orange, expects to need to take the other territories. In [ ]: %run -i m269_territories #Create the territories australasia_w.draw() Create a function lowest_cost which, given starting and ending nodes and a graph, implements Dijkstra’s algorithm to return either the minimum estimated cost in troops to take the ending node from the starting node, or -1 if a route is not possible. For this question you should not use the heapq module You can use the tests below to help check if your code is working.\ NOTE that failing the tests is a clear indication your code is faulty, but passing the tests is NOT a guarantee it is correct.\ Your tutor may run additional tests. In [ ]: def lowest_cost(starting_node: Hashable, ending_node: Hashable, graph: WeightedDiGraph) #Write your answer here pass #Tests test_table = [ ['NGuinea',Indonesia,NGuinea,australasia_w,3], ] test(lowest_cost_AL, test_table) #Ensure the function name in this line matches your fun Submit this TMA by zipping together the notebook along with all of the helper and data files you have used, and submitting your.zip file using the online TMA/EMA service.