&
, 
, ^
, ~
, <<
, >>
.yield
statement.NOTE: Once the exam starts you are not allowed to share any items with anyone else.
Pen, pencil, eraser, pencil sharpener.
Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.
Personal cheat sheet with the following characteristics:

Name an algorithm that has an \(O(2^N)\) complexity.
Given the set \(S = \{ w, x, y, z \}\), calculate the power set of \(S\).
How would you explain the A* search algorithm to a smart tenyearold child?
You have the following Python code:
def f(n: int) > int: r: int = 0 while n: r += n & 1 n >>= 1 return r % 2 def g(n: int) > int: s: int = 0 for i in range(n): s += f(i) return s
What is the time complexity of function g
? Explain your answer.
Assume that the following code completes the program that started with the code from the previous question. What gets printed to the standard output when running the program?
if __name__ == '__main__': print(g(5))
What is the output of the following Python program?
def h(n: int) > list[int]: return [x for x in range(1, n + 1) if n % x == 0] if __name__ == '__main__': print(h(19)) print(h(20))
Write in Python or pseudocode a function called heap_children
. The function takes as input a list \(a\) containing a binary heap and an index \(i\). It returns a tuple with the values of the left and right children corresponding to the element contained in \(a[i]\). The tuple should contain None
in place of the value of a non existing child. The function’s signature is as follows:
def heap_children( a: list[int], i: int ) > tuple[Optional[int], Optional[int]]:
Usage examples:
>>> heap: list[int] = [1, 3, 6, 5, 9, 8] >>> heap_children(heap, 1) (5, 9) >>> heap_children(heap, 2) (8, None)