Algorithm and Data Structure (sorting, tree, dynamic programing)

• Unit tests have only been provided. You will need to write your own tests when they are not provided.  • The expected deliverable is this Jupyter PYTHON Notebook, completed with your answers. • The subjects are sorting, trees and dynamic programming. I. Sorting Lists of Pairs Consider the abstract Python class below: 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 [login to view URL](other) is False: return None elif self == other: return 0 elif self < other: return -1 elif self > other: return 1 else: assert False, "Inconsistent operation definitions" QUESTION 1: 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. Q2 Given a list l of Pairs in no particular order, use a sorting algorithm similar to *selection sort* to sort $l$ such that, at the end of the algorithm, for every two pairs $l[i]=(a, b)$ and $l[j]=(c, d)$ at index $i$ and $j$ in $l$, respectively, with $i <j$, we have: * either $(a, b) \leq (c, d)$, * or $(a, b)$ and $(c, d)$ are not comparable. Again, we provide a test class below. You don't need to edit it, but the method pairsort you wrote needs to pass these tests! ........ Question 3: Define a function pairSortFast that takes a list l of n Pairs as input and sort this list in O(n) time in the worst case (not the amortised worst case). Suppose that any pair (a,b) in l is such that a and b∈{0,…,U}, where U is a small integer. Hint: a clever hashing function may help. Question 4: Use the fact that Python's sort is stable to provide a simple solution to sort a list of pairs as stated in Question 1.2. Use unit testing as in the previous questions to test your solution. Both your solution and the unit testing will be assessed. (no need to rewrite new test cases; use the old ones). II> TREE III> DYNAMIC PROGRAMING