What is the best-case and worst-case complexities of inserting an item into a List ADT, if implemented with an array?

Assume the array has enough space (no resizing needed). Explain your answer, and don't forget to define any variables you may use (no explanation, no marks).

We want to implement a new data type: it takes a number N, and allows us to insert exactly N items.

Then, we can retrieve items from it one by one, but the order it gives the items out is by always returning the middle element with respect to the insertion order.

For example, if we say N = 6 and we insert 1, 2, 3, 4, 5, 6, the first item we get when we call retrieve will be 3, then 4, then 2, then 5, then 1, and lastly 6.

How can we implement this data type using only stacks and queues? Explain how the insert and retrieve operations should work.

• Assume N is a positive integer, and that we always have to call insert exactly N times and add all the items, before we start retrieving them.
• Assume you can create any number of stacks and queues you'd like, but you don't have access to the arrays storing the data in the stacks/queues.

We have a Linked List called lst, and we want to reverse this linked list. That means after our code runs, we want lst.head to point to what's currently the last item in the list, and iterating on the links from there one by one would get us to the current head of the list. Finish the implementation given below to achieve this.

Your code doesn't need to have perfect formatting and syntax - the main point is to write down the idea behind the algorithm, not an executable code.

def reverse(lst):
    current = lst.head
    prev = None
    while current is not None:
        ... insert your code here ...

Describe the Set ADT giving details about:

• its main properties (1 mark)

• its key operations (1 mark)

• possible data structures that one can use to implement it (0.5 marks)

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

Apply one outer loop iteration of Selection Sort to the list [6, 1, 4, 8]. What is the result?

Assume we have a function f that receives a collection of elements as input.

It iterates over these elements and for each one, it calls another function g that performs 20 basic operations.

What is the best case complexity of functions f and g?

Explain your answer and don't forget to define any variables. (No explanation, no marks)

State (in total) 3 advantages/disadvantages of implementing an ADT using Linked Nodes structure instead of an Array.

Apply two outer loop iterations of Insertion Sort to the list [9, 3, 2, 7]. What is the result?

What principle does the Queue ADT implement?