Complete the python method that implements the push method for a Linked Stack class. [4 marks]

Perfect python syntax is not required.

Provide one advantage/disadvantage of a Linked Stack over an Array-Based Stack. [1 mark]

class Node:
    def __init__(self, item):
        self.item = item
        self.link = None
class LinkedStack(Stack):
    def __init__(self):
        self.top = None
        self.length = 0
    
    def push(self, item):
        pass

Consider sorting a list of n integers with quick sort.

What is the best-case time complexity if we always select the largest number as the pivot?

Assume picking the pivot can be done in constant time.

What does the following function do if n >= 0?

def mystery(n):
    i = 0
    yield i
    while i < n:
        if i % 4 != 0:
            yield i
        i = i + 2

What are the main operations on a Priority Queue?

I have decided to use a balanced Binary Search Tree (BST) to implement Separate Chaining in a Hash Table. What is the complexity of updating an item in such a hash table?

O(hash) - complexity of the hash function

I want to generate a balanced BST from a list with numbers from 1 to 10 (in ascending order) inclusive and apply no self-balancing. To do that, what order should I insert items in?

What is the time complexity of the following function if measured with respect to n?

def mystery(n: int) -> int:
    count = 0
    for i in range(n):
        count += 1
    if n == 0:
        return count
    else:
        return mystery(n - 1)

What is the worst-case time complexity of getting the union of two sets (see example code below), if implemented with an array?

Explain your answer (no explanation, no marks) and define your input variables.

def union(self, other):
    res = ArraySet(len(self.array) + len(other.array))
    for i in range(len(self)):
        res.array[i] = self.array[i]
    res.length = self.length
    for j in range(len(other)):
        if other.array[j] not in self:
            res.array[res.length] = other.array[j]
            res.length += 1
    return res

What is the best-case and worst-case time complexities of adding an item to a Stack implemented with an array and meant to allow resizing?

Define any input variables (no explanation, no marks).

Describe the Stack ADT giving details about:

• The main property of the stack

• The two main operations of the stack