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

Budget $30-250 AUD

• 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

## 18 freelancers are bidding on average $159 for this job

Hi... I am a Python specialist, certified by Freelancer. I fully understand your project and I am sure I can help you. Let's discuss details by chat.

Hi. My name is Uzair.I am in final semester of my masters in Electrical Engineering. I am doing my thesis in biomedical signal processing and Machine learning. I have more than 3 years of experience in MATLAB speciall More

Hello Having experience of python, I can do what you want. Python is my primary programming language. Let us discuss details in chat.

Hello How are you? I have rich experience of python so that I can do what you want. Let us discuss details in chat.

Hi, thank you for looking for my cover letter. I’ve carefully gone through your job posting. I can work with you anytime you want. I believe I possess the necessary skills and experience you are seeking. I will be a More

Hello I am expert with C++ and I can handle the project easily. Moreover I have studied algorithms and data structure. contact me to discuss the details. Regards

I am competing internationally representing Ireland in competitive programming. I could do this easily. Look forward to working with you.

As you can see on my github account I have been doing alot of algorithms and data structures for awhile now, and it's kind of my experience spot, so it would be a pleasure to Let me help you with what you need.

HI, I have 3 years of python experience. I understand all the questions and shall be able to do them efficiently and accurately. Looking forward to hearing from you. Thanks

Hi, I have 20+ years of total development experience in multiple technologies including Python I am also providing Online Training from last 5 years. Please give me a single chance to prove my skills I have More