Explain two main advantages that Double Hashing has over Linear Probing.

Assume that the size of this hash table is 7.

Consider an implementation of hash table with separate chaining and the hash function is defined as hash(key) = key mod 7.

You insert the following keys [1, 8, 15, 4, 11, 7, 2] into the hash table.

Which hash position/positions will have 2 or more items in their chain? [3 marks]

Which key would be slowest to search? [2 marks]

Consider when quicksort chooses a random pivot. If the pivot chosen comes from the middle 50% of the list, then it is a good pivot, ie: the good pivot is closer to the median than either maximum or minimum.

Since half of the list contains good pivots, we should expect roughly half of the quicksort calls to choose a good pivot.

Suppose we guarantee that every second call, quicksort picks a good pivot. What would be the worst case complexity and recursion depth of quicksorting a list of n unique elements? [2 marks]

Explain your recursion depth using the (smallest) reduction in problem size at each layer, and thus your complexity using the work done at each layer. No explanation no marks. [3 marks]

Suppose when merging during mergesort, we find two equal keys of value 8: left_list = [..., 8$, ...]; right_list = [..., 8#, ...]

What do we know about the relationship between 8$ and 8#? [1 mark]

How should we merge 8$ and 8# and why? [1 mark]

Consider when quicksort selects a random pivot in O(1) time.

State and explain the worst case time complexity of quicksorting list of unique values. No explanation no marks.

What does this function do? Assume that for any node, node.item will be less than or equal to all items in node.link. [2.5 marks]

State and explain the best case complexity of this function [2.5 marks]

def mystery(node1: Node[int], node2: Node[int]):
    if node1 is None: 
        return node2
    if node2 is None:
        return node1
    if node1.item <= node2.item:
        node1.link = mystery(node1.link, node2)
        return node1
    else:
        node2.link = mystery(node1, node2.link)
        return node2

Consider an implementation of linked stack with only one pointer: top.

Which of the following operations CANNOT be implemented in O(1) time?

Which is TRUE?

Consider an implementation of a hash table with separate chaining

where the hash function runs in constant time and the cost of comparison is also constant.

What is the worst-case time complexity of the

What is tail recursion?