# 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

Skills: Algorithm, Python

( 1 review ) Mlebourne, Australia

Project ID: #17030462

## Awarded to:

sunny2309

Hello, I can help you with your task of data structure and algorithms. Below is list of skills on which i have good hands-on: - Languages: Python, Java, R Programming. - Tools: Jupyter Notebook, PyCharm, Ecli More

$111 AUD in 3 days (2 Reviews) 2.5 ## 17 freelancers are bidding on average$161 for this job

edecena75

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.

$130 AUD in 2 days (49 Reviews) 5.8 ahmsak Hello Sir, I am a computer science tutor, I teach (among others) Python, Scala, and Advanced Algorithms. I have done many projects like this, and I'm one of the top developers, and you can check by clicking on my pro More$120 AUD in 3 days
(69 Reviews)
5.9
$155 AUD in 3 days (14 Reviews) 5.1 uzairrzahid 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$222 AUD in 5 days
(14 Reviews)
4.4
SimbaMoor

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

$150 AUD in 3 days (6 Reviews) 4.2 Vadimwang Hello How are you? I have rich experience of python so that I can do what you want. Let us discuss details in chat.$166 AUD in 3 days
(36 Reviews)
4.4
Webstar0426

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

$222 AUD in 3 days (4 Reviews) 3.3 RajuPitta Hey There, I have very strong expertise in Python and having more than five years of experience in enterprise level software development and automation. I am very passionate about engineering and delivering quality so More$250 AUD in 5 days
(5 Reviews)
2.8
$155 AUD in 3 days (1 Review) 1.7 mueliwa 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$222 AUD in 5 days
(0 Reviews)
0.0
Naumanmalik1435

it's Not difficult.... I will do this...with loss cost

$111 AUD in 3 days (0 Reviews) 0.0 MToba 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.$111 AUD in 3 days
(0 Reviews)
0.0
gd015828

I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I am very good at DS/Algo I More

$30 AUD in 3 days (0 Reviews) 0.0 antongulikov I'm a developer at [login to view URL], very good at algorithm [login to view URL]$155 AUD in 1 day
(0 Reviews)
0.0
caolanfleming

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

$277 AUD in 3 days (0 Reviews) 0.0 atingupta2005 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$155 AUD in 3 days
(0 Reviews)
0.0