Midterm Solutions Spring 2025

PwnHero Please keep in mind these answers are brief only for your reference, based on the question mark, you had to explain in more detail Part A: Multiple Choice A1. What is the asymptotic bound for the recurrence T(n) = 4T(n/2) + n? (a) O(n2) (b) O(n log n) (c) O(n) (d) O(n2 log n) Answer: (a) O(n2) The recurrence grows at the same rate as n2. A2. Which sorting algorithm is guaranteed to be in-place and not stable? (a) Insertion Sort (b) Merge Sort (c) Heap Sort (d) Quicksort Answer: (c) Heap Sort Heap sort doesn’t need extra space, but it doesn’t keep equal elements in their original order. A3. Which of the following best describes the result of calling Min-Heapify on a subtree of a min-heap? (a) It sorts the subtree in ascending order. (b) It restores the min-heap property within the subtree. (c) It finds the minimum value in the heap. (d) It deletes the minimum value from the heap. Answer: (b) It restores the min-heap property within the subtree It fixes the heap so the smallest value is at the top of the subtree. A4. If f(n) = Θ(g(n)) and g(n) = O(h(n)), which of the following is necessarily true? (a) f(n) = O(h(n)) 1 PwnHero.com