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

Kĩ năng: Thuật toán, Python

Về Bên Thuê:
( 1 Nhận xét ) Mlebourne, Australia

ID dự án: #17030462

Được trao cho:

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 Thêm

$111 AUD trong 3 ngày (5 Đánh Giá) 3.6 16 freelancer đang chào giá trung bình$162 cho công việc này

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 Thêm

$120 AUD trong 3 ngày (69 Nhận xét) 5.9 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 trong 2 ngày
(56 Nhận xét)
5.9
$155 AUD trong 3 ngày (15 Nhận xét) 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 Thêm$222 AUD trong 5 ngày
(21 Nhận xét)
4.6

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 trong 3 ngày (36 Nhận xét) 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 Thêm$222 AUD trong 3 ngày
(5 Nhận xét)
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 Thêm

$250 AUD trong 5 ngày (6 Nhận xét) 2.8$155 AUD trong 3 ngày
(1 Nhận xét)
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 trong 5 ngày (0 Nhận xét) 0.0 Naumanmalik1435 it's Not difficult.... I will do this...with loss cost$111 AUD trong 3 ngày
(0 Nhận xét)
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 trong 3 ngày (0 Nhận xét) 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 Thêm$30 AUD trong 3 ngày
(0 Nhận xét)
0.0
antongulikov

I'm a developer at [login to view URL], very good at algorithm [login to view URL]

$155 AUD trong 1 ngày (0 Nhận xét) 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 trong 3 ngày
(0 Nhận xét)
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 Thêm

\$155 AUD trong 3 ngày
(0 Nhận xét)
0.0