&
, 
, ^
, ~
, <<
, >>
.yield
statement.heapq
module. Functions heappush
, heappop
, and heapify
.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:
Vector = list[int] Matrix = list[Vector] def e(m: Matrix) > Matrix: def f(i: int) > Vector: def g(j: int) > int: return m[j][i] return [g(j) for j in range(n)] n = len(m) return [f(i) for i in range(n)]
What is the time complexity of function e
? 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(e([])) print(e([[1]])) print(e([[1, 2], [3, 4]])) print(e([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
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)
Using Kruskal’s or Prim’s algorithm find the minimum spanning tree (MST) for the following weighted undirected graph. Draw the resulting tree and indicate its total cost.
Using the graph from the previous problem, apply Dijkstra’s algorithm to find the shortestpath between the vertex C and all the other graph’s vertices. Write the corresponding shortestpath table and draw the resulting graph.
Suppose you’re going camping. You have a knapsack that will hold 6 lb, and you can take the following items. Each has a value, and the higher the value, the more important the item is:
Use dynamic programming to build the corresponding table in order to find what’s the optimal set of items to take on your camping trip.