1. What is an abstract data type and how does it differ from data type? Give an example of an abstract data type and also of a data type in Python. [3]

2. Briefly describe Stack ADT giving details about [4]

• Main property of a Stack ADT [2]
• Key operations of the Stack ADT [2]

3. What is the best-case and worst-case time complexity of operation pop() for a Stack ADT, if implemented with an array? (no explanation, no marks) . [3]

Is the following function tail-recursive?

def fib (n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

What is the main advantage of using tail recursion?

For a function to be recursive (and practical in Python), what should it have?

Is the following function tail-recursive?

def fib (n: int, a: int = 0, b: int = 1) -> int:
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return fib(n - 1, b, a + b)

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

def mystery(n: int) -> None:
    if n <= 0:
        return
    else:
        if n % 2 == 0:
            mystery(n - 1)
        else:
            mystery(n // 2)