FIT1045 Algorithms and programming in Python, S1-2019Assignment 2 (value 18%).Due: Friday 17th May, 2019, 11:55 pmObjectivesThe objectives of this assignment are: To demonstrate the ability to implement algorithms using basic data structures and operations on them. To gain experience in designing an algorithm for a given problem description and implementing thatalgorithm in Python.Submission Procedure
Put you name and student ID on each page of your solution.Save your files into a zip file called yourFirstName yourLastName.zipSubmit your zip file containing your solution to Moodle.Your assignment will not be accepted unless it is a readable zip file.Important Note: Please ensure that you have read and understood the university’s policies on plagiarismand collusion available at http://www.monash.edu.au/stud... Youwill be required to agree to these policies when you submit your assignment.Marks: This assignment will be marked both by the correctness of your code and by an interview withyour lab demonstrator, to assess your understanding. This means that although the quality of your code(commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write cleancode so that it is easier for you to understand and explain.This assignment has a total of 30 marks and contributes to 12% of your final mark. Late submission will have10% off the total assignment marks per day (including weekends) deducted from your assignment mark. (In thecase of Assignment 1, this means that a late assignment will lose 3 marks for each day (including weekends)).Assignments submitted 7 days after the due date will normally not be accepted.Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable toexplain your code via a code walk-through in the assessment interview. Readable code is the basis of aconvincing code walk-through.1Task 1: Talent Acquisition (15 Marks)BackgroundIn this task we investigate algorithmic solutions to what is called a constrained optimisation problem. Specifi-cally, we look into the problem of automatically composing a team to work on a given project. We want to makesure that between the team members, we have people who are capable of doing all the work that the projectrequires (constraint), but we also want to keep our total costs as low as possible in terms of the combined dailyrate charged by all team members (optimisation). For instance, a problem input might look like this:pythonmysqlmarketingweb designroboticsmysqlmarketingpythonweb designmysqlmarketing700$required:pythonphpweb design2000$ 300$Superman Daisy Mattall skills coveredcombined rate: 1000$marketingsales450$Sandymatlabstatisticspythontensorflow900$TracyMore formally, the problem can be stated as: Given a set of required skills and a set of possible candidates,each of which has a set of skills they posses and a daily rate, find a set of candidates such thatEvery skill required for the project is possessed by at least one of the candidates in the set.The total daily rate of all candidates in the set is minimum, i.e., there is no set satisfying Condition 1with a smaller total rate.As for all computational problems, there are various strategies to tackle it. In this task we will look at twoapproaches: one which tries to find a reasonably cheap team quickly (relaxing Condition 2 above), and onewhich takes more time but is guaranteed to compute the best possible team.InstructionsCreate a Python module called hiring.py. Your module must contain the six functions described in thesubtasks below, but you are allowed, and in fact encouraged, to implement additional functions as you deemappropriate. The module must not contain any imports. Throughout this task we will adhere to the followingconventions: We will represent a skill simply by a string (e.g., "java", "lua", or "marketing") and a set of skills willbe given by a list of strings. A candidate will be represented by a pair (skills, rate) consisting of a list of skills skills and apositive integer rate representing their daily rate. We will assume and ensure that lists of skills do not contain duplicates and that each required skill forthe input project is at least possessed by one of the available candidates.a) Write functions cost(candidates), skills(candidates) and uncovered(project, skills) for workingwith the basic ingredients of our constrained optimization problem as follows. The function cost(candidates)takes as input a list of candidates and produces as output the combined daily rates of all the given candidates.The function skills(candidates) takes as input a list of candidates and produces as output the list ofskills possessed by at at least one of the candidates (again, the output list should not have any duplicates).The function uncovered(project, skills) takes as input a list of required skills project and a list ofprovided skills skills and produces as output a new list of skills that contains all skills in project notcontained in skills.b) Write a function team of best individuals(project, candidates) that solves our problem approximatelyby iteratively finding the best next candidate evaluated in isolation, i.e., by only considering the number ofrelevant skills covered per dollar daily rate—without taking into account what it will cost to complete theteam around that candidate. To represent this evaluation metric, write another functionbest individual candidate(project, candidates) that accepts as input a list of required skills projectand a list of candidates candidates and that returns as output the index of the candidate with the maximumnumber of skills covered per dollar daily rate. If there is a tie, return the earliest candidate involved in thetie. Based on that evaluation metric, the function team of best individuals(project, candidates) has2Input: A list of strings project representing the required skills and a list of available candidates candidates.Output: A list of candidates team=[c1, c2, c3, ..., ck] taken from the input candidates such that For all the skills in project there is at least one candidate in team that has that skill. Candidate c1 is the best individual candidate for the required skills, c2 is the best individualcandidate for the skills required that are not covered by candidate c1 and so on. Every candidate possesses at least one skill relevant to the project that is not covered by all previouscandidates in the list.c) Write a function best team(project, candidates) that solves our optimization problem optimally. Thatis, function best team(project, candidates) hasInput: A list of strings project representing the required skills and a list of available candidates candidates.Output: A list of candidates team taken from the input candidates such that For all the skills in project there is at least one candidate in team that has that skill. The total daily rate cost(team) is less or equal to to all other possible sets of candidates fromcandidates which satisfy the first property.Hint: Think about how you can relate the problem of finding the best team for a project to itself. Relatedto that, can you come up with a criterion to determine whether an individual candidate is part of the bestteam?Examples Assume we have the following candidates and required skills for a project:jess = (["php", "java"], 200)clark = (["php", "c++", "go"], 1000)john = (["lua"], 500)cindy = (["php", "go", "word"], 240)candidates = [jess, clark, john, cindy]project = ["php", "java", "c++", "lua", "go"]a) Calling cost([john, cindy]) returns 740, the total daily rate of john and cindy.b) Calling skills([clark, cindy]) returns a permutation of the list ["php", "c++", "go", "word"] becausethese are the skills covered by at least one of clark and cindy.c) Calling uncovered(project, skills([clark])) returns ["java", "lua"] because these are the skills notcovered by clark.d) Calling best individual candidate(project, candidates) would return 0 because jess covers 2 requiredskills for a daily rate of $200 or 1/100 useful skills per dollar. Thus, jess covers more skills per dollarthan clark (3/1000), john (1/500), or cindy (1/120).e) Calling team of best individuals(project, candidates) returns a list equal to [jess, cindy, john,clark] because, as we know from Example d above, best individual(project, candidates)==0 and thenbest individual(uncovered(project, skills([jess])), [clark, john, cindy])==2 and so on.f) Calling best team(project, candidates) returns a list team equal to some permutation (same elementsbut possibly different order) of [jess, clark, john] because uncovered(project, skills(team))=[]and cost(team)=1700, which is less than the cost of all other feasible teams (i.e., those that cover all skills).Marking Guide (total 15 marks)Marks are given for the correct behaviour of the different functions:a) 1 mark for cost and 2 marks for each of skills and uncoveredb) 2 marks for best individual candidate and 2 marks for team of best individualsc) 6 marks for best teamAll functions are assessed independently to the degree possible. For instance, even if function skills does notalways produce the correct output, function team of best individuals can still be marked as correct.3Task 2: Calculator (15 Marks)BackgroundIn this task we explore a simple parsing problem. “Parsing” refers to the task of correctly interpreting structuredinformation that is given in a flat unstructured form such as a string. A simple example of this is the evaluationof arithmetic expressions. Arithmetic expressions involving the operations of addition (+), subtraction (?),multiplication (?), division (/), and exponentiation (∧) are normally written in “infix” notation, i.e., with theoperation symbol in-between the two operands that it is applied to. This leads to the problem that an expressioncould principally be interpreted in multiple ways and we have to decide which operator to give precedence to.For example, according to the standard arithmetic rules, we have5 4∧2 + 100/4 = 45because ∧ has a higher precedence than ? and / which in turn have a higher precedence than + and . Thesestandard precedence-based rules can be overridden by parentheses. For instance, we have((10 5) 4∧2 + 100)/4 = 45because expressions inside parentheses are evaluated first in a recursive manner before standard operator precedencerules are applied.In this task, we will implement these rules in Python to create a calculator that can evaluate well-formed infixexpressions given as a string that contains non-negative floating-point numbers (e.g, "0.0", "92", "7.5" or"943.2543"), operators "+", "-", "*", "/", "∧", parentheses "(" and ")", and whitespaces " ". We evaluatethe operators in the typical order outlined above (and in addition from left to right in case of equal operatorprecedence, which is relevant for the non-associative operator ∧).InstructionsCreate a python module parsing.py. Within that module create the five functions described in the subtasksbelow. The only import statement in the module must be from math import pow.a) Write a function tokenization(expr) that maps an arithmetic expression to its “tokens”, i.e., the individualsyntactic units it contains. This function takes as input a string representing a mathematical expressionconsisting of non-negative numbers and the symbols listed in the background including potentially spaces. Itreturns a list of tokens corresponding to the given expression. A token can either be a string correspondingto an operator from the set {"+", "-", "*", "/", "∧"}, a string containing a single opening or closingparenthesis ({"(", ")"}), or a non-negative float. Whitspace from the input string do not appear amongthe tokens.b) Write functions has precedence(op1, op2) and simple evaluation(tokens) that together can evaluatesimple arithmetic expression without parentheses. Function has precedence(op1, op2) takes as input two operator tokens, i.e., strings from the set {"+","-", "*", "/", "∧"} and outputs True if op1 has higher precedence than op2; otherwise False. Function simple evaluation(tokens) takes as input a list of tokens (excluding parentheses) and returnsthe single floating point number corresponding to the result of the tokenized arithmetic expression.c) Write functions complex evaluation(tokens) and evaluation(string) that put everything together andallow to evaluate strings representing well-formed arithmetic expressions. As an intermediate step, the functioncomplex evaluation(tokens) takes as input a list of tokens (this time including parentheses) andreturns the single floating point number corresponding to the result of the tokenized arithmetic expression.Finally, the function evaluation(string) has as input a string containing a well-formed arithmeticexpression and as output the single float corresponding to its result.Example:a) Calling tokenization("(3.1 + 62∧2) (2 - 1)") would return the list ["(", 3.1, "+", 6.0, "*",2.0, "∧", 2.0, ")", "*", "(", 2.0, "-", 1.0, ")"]. Note that the symbols are strings while thenumbers are floats.b) Calling has precedence("*","+") and has precedence("∧","+") both return True. In contrast, callinghas precedence("", "∧") as well as has precedence("","/") both return False.4c) Calling simple evaluation([2, "+", 3, "*", 4, "∧", 2, "+", 1]) would return 51.0. This is becausewe first evaluate ‘∧’, giving 2 + 3 16 + 1, then we evaluate ”*”, giving 2 + 48 + 1, and lastly we evaluate thetwo ”+” left to right giving 51. Returned as a float, this is 51.0.d) Calling complex evaluation(["(", 2, "-", 7, ")", "*", 4, "∧", "(", 2, "+", 1, ")"]) as well asevaluation("(2-7) * 4∧(2+1)") both return ?320.0. This is because we first evaluate the terms in parentheses,giving 5 4∧3. Then we evaluate the ∧, giving 5 64. Evaluating the ‘*’ gives ?320.0.Marking Guide (total 15 marks)Marks are given for the correct behaviour of the different functions:a) 3 marks for tokenizationb) 5 marks for simple evaluation and 1 mark for has precedence()c) 5 marks for complex evaluation and 1 mark for evaluationAll functions are assessed independently to the degree possible. For instance, even if function simple evaluationdoes not always produce the correct output, function complex evaluation can still be marked as correct.5Task 3: FIT1053 Students Only (5 Marks)In addition to the above work, you are required to complete one of the following two tasks:Argue the correctness of the function simple evaluation from Task 2. To do this, annotate loop invariantsas comments in your code and provide a complete argument in a block comment at the beginning of yourfunction. Your complete argument should refer to invariants you identify in your code.Marking Guide (total 5 marks)a) 2.5 marks for correctly identifying appropriate invariants within codeb) 2.5 marks for using invariants to formulate a proof of correctnessorThe aim of this task is to test your best team function from Task 1 and your complex evaluation functionfrom Task 2. To start, create a third module test modules.py. In this module, import your best teamfunction from your hiring.py module and your complex evaluation function from your parsing.py module.If you have followed the correct naming requirements, this can be done by having all three of yourmodules in the same folder and placing the following two lines of code at the start of your test modules.pymodule:from hiring import best_teamfrom parsing import complex_evaluationYou will now be able to use these functions from within your new module. You now need to write thefunction test(func, input, output) to be used to test an input function, func. Here, input is a validproblem input for the function being tested and output is the output we would expect from the function.If a test fails, appropriate information should be displayed to the user, such as what function was called,what the input was, what output the function produced, and the output that was expected.Provide at least 4 test cases (input and expected output) for each of your best team and complex evaluationfunctions. It is expected that these test cases cover a board range of problems of various difficulty. For example,the test cases for your complex evaluation function could start by testing each of the operationsseparately then build up to testing expressions that include a mixture of operations and parentheses.Marking Guide (total 5 marks)a) 2 marks for correct implementation of testb) 1.5 marks for providing at least 4 test cases for your best team function of various difficultyc) 1.5 marks for providing at least 4 test cases for your complex evaluation function of various difficulty