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 cu
ent 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 co
ectness 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 co
ectness 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 ca
ied 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).
"""
es = []
for x in row:
es += [alpha*x]
eturn 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
eadable 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
eakdowns 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,
eadable 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, co
espondingly, 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 a
itrary 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. Conside
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
epresent 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
y 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, ’!=’