1: (5 points) Below is part of the definition of the UndorderedList class, given in your textbook. To implement the length method (this is called size in the digital version of the textbook), we counted the number of nodes in the list. An alternative strategy would be to store the number of nodes in the list as an additional piece of data in the head of the list. class UnorderedList: def init (self): self.head None def add(self, item): tempNode(item) temp.setNext (self.head) self.head = temp def length (self): current self.head count 0 while current !- None: count count + 1 current current. getNext() return count In the space below, rewrite the partial UnorderedList class definition to include, maintain, and use this new information. (Don't just make changes above, rewrite the new version below.) 2: (5 points) When giving the specification for the UnorderedList class, your textbook's authors left the definition of the pop () method as an exercise. Your task now is to add the definition for pop to the revised UnorderedList class definition that you provided as your solution to Problem 1. Be sure to use and maintain the information about list length that you added in your solution to Problem 1. Here is the specification for the pop () method as given in your book: pop() removes and returns the last item (i.e., the tail end, not the head) in the list. It needs nothing as an argument and returns the item. Assume the list has at least one item. Write your pop) method in the space below. 3: (5 points) Suppose we perform the following sequence of operations (as defined in your textbook) on a queue which is initially empty. What number will be printed? q = Queue( ) q.enqueue(77) q.enqueue (40) x = q.dequeue() q.enqueue (56) q.dequeue) x = q.dequeue() print(x) answer. 4: (5 points) Suppose we perform the following sequence of operations (as defined in your textbook) on a stack which is initially empty. What number will be printed? s = Stack() s.push(77) s.push (40) s.push (12) s pop () x = s.peek ( ) s pop () s.push (56) print (x) answer. 5: (10 points) Suppose an algorithm solves a problem of size n in at most the number of steps listed given below: T(n) - (n+2n) (3/) Calculate the asymptotic time complexity (big-0 or big-theta) for T(n). Show your work, including values for c and no along the way. 6: (10 points) Assume that T(n) for the following code segment tells us exactly how many times the instruction x = x + 1 is executed for some given n. for i in range (0, n): for j in range(1, 2*n): for k in range (0, (6*n)//3): for m in range (1, 4): print(x) 6a: If the value of n is 3, what is the value of x when it is printed? 6b: What is the best O-notation for T(n)? (Or in other words, what is the most appropriate Big- O for this code segment?) Explain your reasoning
