Overview: Midterm Exam

Topics

1. Algorithm analysis review.
   1. Big O notation.
   2. Common runtime functions: \(O(1)\), \(O(\log N)\), \(O(N)\), \(O(N \log N)\), \(O(N^2)\), \(O(N^3)\), \(O(2^N)\), \(O(N!)\). Examples of algorithms for each of these.
2. Python language specific features.
   1. Type hints.
   2. Bitwise operators: &, |, ^, ~, <<, >>.
   3. Comprehensions: lists, sets, dictionaries, generators.
   4. Generator functions and the yield statement.
   5. Classes, data classes, named tuples.
3. Combinatorics.
   1. Power set.
   2. Combinations (with and without repetitions).
   3. Permutations (with and without repetitions).
4. Search algorithms.
   1. Depth-first search (DFS).
   2. Breadth-first search (BFS).
   3. A* search.
   4. Constraint-satisfaction problems (CSP).
5. Priority queues.
   1. Min heaps and max heaps.
   2. Heap insertion and deletion.
   3. Heapsort.

Allowed Items During the Exam

NOTE: Once the exam starts you are not allowed to share any items with anyone else.

1. Pen, pencil, eraser, pencil sharpener.

2. Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.

3. Personal cheat sheet with the following characteristics:

   Must be one of these: \(5 \times 8\) inches index card (\(12.7 \times 20.32\) cm). Half letter size sheet of paper (\(13.97 \times 21.59\) cm). Must be handwritten. Computer-made cards/sheets are not allowed. You can write in both sides of the card/sheet. Must include your student ID and full name on the upper-left corner of both sides of the card/sheet. There are no restrictions on the specific content written on the card/sheet.

Sample Questions

1. Name an algorithm that has an \(O(2^N)\) complexity.

2. Given the set \(S = \{ w, x, y, z \}\), calculate the power set of \(S\).

3. How would you explain the A* search algorithm to a smart ten-year-old child?

4. 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.

5. 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))
   

6. 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))
   

7. 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)