Instructions
You must work on this assignment individually. We check for similarities and find collusion cases every semester. You've been
warned!
This assignment contributes 20% towards your final mark in FIT5211.
The subjects are sorting, trees and dynamic programming.
The exercises are roughly given by increasing difficulty. Obtaining a 100% mark may be very hard, depending on your
background, and will probably take many hours. The assignment is written such that everyone can correctly complete the first
exercises, but it is likely that the last ones will only be succesfully completed by few.
You are expected to comment your code. Marks will be removed if your code is insufficiently documented.
You may create auxiliary/helper functions for each question, as long as you use the pre-defined functions, if any is given.
Unit tests have only been provided for Exercise 1. You will need to write your own tests when they are not provided.
The expected deliverable is this Jupyter Notebook, completed with your answers.
For questions on this assigment, please use the Moodle forum.
The deadline is October 19, 23:55, submission via Moodle. If this does not work, and only in this case, send your Notebook to
pierre.lebodic@monash.edu.
The late penalty is 10 marks (deducted from your original mark) per late day.
Have fun!
Exercise 1: Sorting Lists of Pairs (45 marks)
(Note that in this exercise, questions may be attempted without having completed all previous questions)
Consider the abstract Python class below:
In [ ]:
class Comparison:
def __init__(self):
pass
#returns True if the two objects are comparable,
#False otherwise
def areComparable(self, other):
raise Exception("NotImplementedException")
#returns True if the two objects are equal,
#False otherwise
def __eq__(self, other):
raise Exception("NotImplementedException")
#returns True if self > other,
#False otherwise
def __gt__(self, other):
raise Exception("NotImplementedException")
#returns True if self < other,
#False otherwise
def __lt__(self, other):
raise Exception("NotImplementedException")
def __ne__(self, other):
return not self.__eq__(other)
def __ge__(self, other):
return self.__eq__(other) or self.__gt__(other)
def __le__(self, other):
return self.__eq__(other) or self.__lt__(other)
def compare(self, other):
if self.areComparable(other) is False:
return None
elif self == other:
return 0
elif self < other:
elif self < other:
return -1
elif self > other:
return 1
else:
assert False, "Inconsistent operation definitions"
The Comparison class provides a way to model items that are not always comparable. For instance, the pair of integers $(5, 10)$ is
greater than $(4, 8)$, but it is not comparable to $(6, 5)$, because $5 < 6$ and $10 > 5$.
In this exercise, we will look into different ways to sort list of pairs. We will suppose that the pairs in a list are all different.
Question 1.1 (10 marks)
The rules of comparison between two Pairs $(a, b)$ and $(c, d)$ are:
$(a, b) == (c, d)$ if and only if $a == c$ and $b == d$,
$(a, b) > (c, d)$ if and only if ($a > c$ and $b \geq d$) or ($a \geq c$ and $b > d$),
$(a, b) < (c, d)$ if and only if ($a < c$ and $b \leq d$) or ($a \leq c$ and $b < d$).
We say that $(a, b)$ and $(c, d)$ are comparable if
$(a, b) == (c, d)$, or
$(a, b) > (c, d)$, or
$(a, b) < (c, d)$.
We ask that you implement the rules above in the class called Pair below, by completing the functions that have a comment "#TODO"
in the body. Note that the class Pair inherits from Comparison.
In [ ]: