Exercise 1 Consider a Node class which defines a node for a linked data structur
ID: 3720029 • Letter: E
Question
Exercise 1 Consider a Node class which defines a node for a linked data structure, and which is defined as follows: class Node: def __init__(self, itemNone, linkNone): self.item item self.next link Suppose you have a List class that implements a Linked List using the Node class above, and has the following method. def mystery (self): mystery aux (self.head) def mystery_aux (current) if current None: return else: current.item mystery_aux (current.next) return current.item (a) What does the method do? Explain in terms of its effect on the value of a list, that consists of the following items in order 1,2,3.4.5 (b) What is the best and worst complexity in Big O notation of our mysteryO method in terms of the length of the list (N)? c) How would you define the method iteratively?Explanation / Answer
Solution
class Node:
# method to initialize variables of Node class
def __init__(self, item = None, link = None):
self.item == item
self.next = link
# mysetery method calls the mystery_aux method
def mystery(self):
mystery_aux(self.head)
# method with recursively calls itself such that each node has the sum of all the nodes ahead of it
# until it reached the end
def mystery_aux(current):
if current == None:
return 0
else:
current.item += mystery_aux(current.next)
return current.item
'''
(a)
method mystery_aux get the input of current node in list and
recursively calls the list elements such that each node has
sum of all the nodes ahead of it and the node itself
if items are 1,2,3,4,5
updated items will be 15,14,12,9,5
(b)
since the method recursively called itself with the next node dividing the problem into smalled sub problems making a recursive tree, the worst and best case complexity of method will be O(2^n)
(c)
iterative method
def mystery_aux(current):
while current != None:
Node n = current
while n != None:
# sum of all items till end
current.item = current.item + current.next.item
current = current.next
# time complexity will be O(n^2) as it iterates the items twice
'''
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.