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)

We are given an integer A that represents a bit-vector set containing N elements (N is an even number, greater than 0, and we know its value).

How can we break up A into two smaller numbers X and Y, representing two other bit-vector sets, so that each contains exactly half of the N elements?

A doesn't need to remain intact after the operations.

Explain your approach and its best and worst case time complexities. You must define your input variables and provide an explanation as part of your complexity analysis.

What is the worst-case time complexity of this function?

Make sure you define any variables you use and you can ignore the cost of comparison. (no explanation, no marks)

def func(arr: List[int], target: int) -> List[int]:
    n = len(arr)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                return [i, j]
    return []

What is the worst-case time complexity of this function?

• Try to find the tightest upper bound you can.
• Try to simplify as much as you can.
• Even if your answer isn't the tightest upper bound/the most simplified, still write your attempt - there are partial marks.
• Provide some reasoning for your answer (no explanation, no marks), and don't forget to define the variables you use.

def func(n):
    counter = 0
    i = 1
    while i <= n:
        for j in range(i):
            counter += 1
        i *= 2
    
    return counter

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

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)