SCC461 – Programming for Data Scientists
Leandro Marcolino
Week 8
Assignment
Deadline: Monday, 06/12/2021, 9am
Write your answers on the Moodle Quiz. Feedback is immediate, and re-attempts are allowed
(“check button”), with a 10% penalty.
The code must have enough comments. Please note that the system only recognises # as
comments, and not """.
1. Trees (2%)
Consider the following Tree class:
c l a s s Tree :
de f i n i t ( s e l f , content , l e f t=None , r i g h t=None ) :
s e l f . content = content
s e l f . l e f t = l e f t
s e l f . r i g h t = r i g h t
# Your code w i l l come here
Let’s assume that only numbers will be stored in the tree. Write a function averagePositive(tree),
which returns the average across all nodes with positive numbers stored in the tree. We
will consider all numbers greater than or equal to 0.
For example, given the tree below:
5
7
4 9
3 8
−3
The average of positive numbers would be 366 = 6.0. Note that −3 was not considered.
The final result must be rounded to 5 decimal places. In order to avoid inconsistencies,
there will not be test cases where the result before rounding is a number with 6 decimal
places ending with 5 (e.g., 2.123455).
2. PriorityQueue (3%)
1
In a priority queue, each item x has an associated priority y. When items are removed,
they must be removed from the highest to the lowest priority. We will assume that 10 is
the highest priority, and 0 is the lowest priority. If two items have the same priority, the
item that was inserted into the queue first must be removed first.
Therefore, the insert method of a PriorityQueue must receive the content and the corre-
sponding priority of that content. Hence, the method interface would be “insert(content,
priority)”, instead of “insert(content)” as in a normal Queue. The interface of other
methods remains unchanged. Additionally, since insert and remove are forbidden calls
(see below), we will re-name these methods as insertInQueue, and removeFromQueue,
respectively.
Hence, in details, create a PriorityQueue class with the following methods:
ˆ init (self): constructor, initialises the Priority Queue.
ˆ is empty(self): returns True if the queue is empty, and False otherwise.
ˆ clear(self): clear up the queue. That is, after calling this method, the queue will be
empty.
ˆ insertInQueue(self, content, priority): inserts the element content into the Priority
Queue, with the corresponding priority given by priority.
ˆ removeFromQueue(self) : removes the element of the queue with the highest pri-
ority, and returns it to the user.
For this question, you must use the Linked List technique! You are not allowed to
use any of the list methods, apart from creating a list, and viewing or changing a specific
element.
Attention: The marking system cannot explicitly check the list manipulations of your
code. Hence, it will not accept any code with the following calls: append, extend,
insert, pop, remove, del. That applies even if these methods and commands are not
being used in connection with a list. Even if your solution is accepted by the automatic
system, it will not receive credits if Linked Lists are not being used.