ONLY PART 2 OF THE ASSIGNMENT
FIT1045 Algorithms and programming in Python, S1-2020 Programming Assignment (rev. 02/06/20) Assessment value: 22% (10% for Part 1 + 12% for Part 2) Due: Week 6 (Part 1), Week 11 (Part 2) Objectives The 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 that algorithm in Python. • To explain the computational problems and the challenges they pose as well as your chosen strategies and programming techniques to address them. Submission Procedure You are going to create a single Python module file products.py based on the provided template. Submit a first version of this file at the due date of Part 1, Friday midnight of Week 6. Submit a second version of this file at the due date of Part 2, Friday midnight of Week 11. For each of the two versions: 1. Save the current version of your products.py into a zip file called yourStudentID yourFirstName yourLastName.zip. 2. Submit this zip file to Moodle. 3. Your assignment will not be accepted unless it is a readable zip file containing a file called products.py. Important Note: Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. You will be required to agree to these policies when you submit your assignment. A common mistake students make is to use Google to find solutions to the questions. Once you have seen a solution it is often difficult to come up with your own version. The best way to avoid making this mistake is to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel free to ask for assistance on Moodle, ensuring that you do not post your code. Marks and Module Documentation This assignment will be marked both by the correctness of your module and your analysis of it, which has to be provided as part of your function documentations. Each of the assessed function of your module must contain a docstring that contains in this order: 1. A one line short summary of what the function is computing 2. A formal input/output specification of the function 3. Some usage examples of the function (in doctest style); feel free to augment and alter the examples for the assessed functions that are already provided in the template if you feel they are incomplete or otherwise insufficient (provide some explanations in this case) 4. A paragraph explaining the challenges of the problem that the function solves and your overall approach to address these challenges 1 http://www.monash.edu.au/students/policies/academic-integrity.html 5. A paragraph explaining the specific choices of programming techniques that you have used 6. [only for Part 2] A paragraph analysing the computational complexity of the function; this does not imply that a specific computational complexity such as O(n log n) is required just that the given complexity is understood and analysed 7. [only for FIT1053 for Part 2]: A paragraph discussing the correctness of the function, giving either a theoretical argument (potentially using loop invariants) or a discussion of how the given doctest example systematically cover a certain range of possible inputs and special cases. For example, if scaled(row, alpha) from Lecture 6 was an assessed function (in Part 2 and you are a FIT1045 student) its documentation in the submitted module could look as follows: def scaled(row, alpha): """ Provides a scaled version of a list with numeric elements. Input : list with numeric entries (row), scaling factor (alpha) Output: new list (res) of same length with res[i]==row[i]*alpha For example: >>> scaled([1, 4, -1], 2.5) [2.5, 10.0, -2.5] >>> scaled([], -23) [] This is a list processing problem where an arithmetic operation has to be carried out for each element of an input list of unknown size. This means that a loop is required to iterate over all elements and compute their scaled version. Importantly, according the specification, the function has to provide a new list instead of mutating the input list. Thus, the scaled elements have to be accumulated in a new list. In my implementation, I chose to iterate over the input list with a for-loop and to accumulate the computed scaled entries with an augmented assignment statement (+=) in order to avoid the re-creation of each intermediate list. This solution allows a concise and problem-related code with no need to explicitly handle list indices. The computational complexity of the function is O(n) for an input list of length n. This is because the for loop is executed n times, and in each iteration there is constant time operation of computing the scaled element and a constant time operation of appending it to the result list (due to the usage of the augmented assignment statement instead of a regular assignment statement with list concatenation). """ res = [] for x in row: res += [alpha*x] return res Beyond the assessed functions, you are highly encouraged to add additional functions to the module that you use as part of your implementation of the assessed functions. In fact, such a decomposition is essential for a readable implementation of the assessed function, which in turn forms the basis of a coherent and readable analysis in the documentation. All these additional functions also must contain a minimal docstring with the items 1-3 from the list above. Additionally, you can also use their docstrings to provide additional information, which you can refer to from the analysis paragraphs of the assessed functions. This assignment has a total of 22 marks and contributes to 22% of your final mark. For each day an assignment is late, the maximum achievable mark is reduced by 10% of the total. For example, if the assignment is late by 3 days (including weekends), the highest achievable mark is 70% of 15, which is 10.5. Assignments submitted 7 days after the due date will normally not be accepted. Mark breakdowns for each of the assessed functions can be found in parentheses after each task section below. Marks are subtracted for inappropriate or incomplete discussion of the function in their docstring. Again, readable code with appropriate decomposition and variable names is the basis of a suitable analysis in the documentation. 2 Overview In this assignment, we implement the backend of an intelligent product search engine where potential customers can search a database of products characterised by different features taking into account the customer’s prefer- ences. Products are represented as lists of feature values, and, correspondingly, a product database is a table where each row represents an individual product. For example, consider the following database of phones using the features of ’name’, ’manufacturer’, ’size’, ’battery’, ’price’ (Source (https://www.allphones.com.au/); note that this database is just for the purpose of illustration and your module must work for other database as well which may use different and a different number of features.). >>> phones = [[’iPhone11’, ’Apple’, 6.1, 3110, 1280], ... [’Galaxy S20’, ’Samsung’, 6.2, 4000, 1348], ... [’Nova 5T’, ’Huawei’, 6.26, 3750, 497], ... [’V40 ThinQ’, ’LG’, 6.4, 3300, 598], ... [’Reno Z’, ’Oppo’, 6.4, 4035, 397]] Again, this is just one limited example of a product database. You are supposed to write a module that can be used for searching arbitrary product databases. For instance, another illustrative application are movies where the data could look as follows: >>> movies = [ ... [’Australia’, 6.6, False, ’English’, 2008, 165], ... [’Lake Placid’, 5.7, False, ’English’, 1999, 82], ... [’Tommy Boy’, 7.1, False, ’English’, 1995, 97], ... [’Life is Beautiful’, 8.6, False, ’Italian’, 1997, 116], ... [’Top Secret’, 7.2, False, ’English’, 1984, 90], ... [’Back to the Future’, 8.5, False, ’English’, 1985, 116], ... [’Twister’, 6.4, True, ’English’, 1996, 113]] with each movie being described by: ‘title’, ‘IMDB rating’, ‘passes the Bechdel test’, ‘language’, ‘year released’, ‘running time’. As a run through example, the instructions below will utilise the phone database. However, it is important that you keep in mind that your functions are supposed to work in any other product context as well. Consider creating your own examples to test this generality. Part 1: Selection and Ranking (10%, due in Week 6) Task A: Product selection (satisfies, 3 Marks; selection, 3 Marks) The first functionality to implement is product selection based on one or more hard criteria. For that we will represent conditions in Python as triples (i, c, v) where i is an integer feature index, c is a relation symbol in [’<’,><=’ ’="=’," ’="">=’, ’>’, ’!=’], and v is some feature value. For example, for the phone database above the following conditions represent that a phone is inexpensive, has a large screen, and it is manufactured by Apple, respectively. >>> inexpensive = (4, ’<=’, 1000)="">>> large_screen = (2, ’>=’, 6.3) >>> apple_product = (1, ’==’, ’Apple’) For this task, your module has to contain at least the two mandatory functions satisfies and selection. The first determines whether a product satisfies an individual condition. The second selects all products from an input table that satisfies all of a given list of conditions. The details are as follows. Implement a function satisfies(product, cond) with the following specification. Input: A product feature list product and a condition cond as specified above. Output: True if condition holds for the product otherwise False. For example, for the above phone database and conditions, satisfies behaves as follows. 3 (https://www.allphones.com.au/) >>> satisfies([’Nova 5T’, ’Huawei’, 6.26, 3750, 497], inexpensive) True >>> satisfies([’iPhone11’, ’Apple’, 6.1, 3110, 1280], inexpensive) False >>> satisfies([’iPhone11’, ’Apple’, 6.1, 3110, 1280], large_screen) False >>> satisfies([’iPhone11’, ’Apple’, 6.1, 3110, 1280], apple_product) True Implement a function selection(products, conditions) with the following specification. Input: A product table products and a list of conditions conditions as specified above. Output: The list of products satisfying all condition cond in conditions. Building again on the above scenario, the behaviour of this function can be illustrated by the following examples: >>> cheap = (4, ’<=’, 400)="">>> selection(phones, [cheap, large_screen]) [[’Reno Z’, ’Oppo’, 6.4, 4035, 397]] >>> not_apple = (1, ’!=’