0 — Test 593

Correct Answer: B. It runs in O(n log n) in the worst case, is in-place, and is not stable
Explanation: Heap sort has good worst-case guarantees, but it is not stable.

Correct Answer: D. Insertion sort
Explanation: Shell sort runs insertion sort on elements spaced a gap apart, shrinking the gap each round.

Correct Answer: D. It is not guaranteed to be stable or even to use quick sort
Explanation: The C standard does not specify the algorithm or its stability.

Correct Answer: A. Divide and conquer
Explanation: Merge sort splits the input into independent subproblems, solves them, and combines the results. It does not cache overlapping subproblems.

Correct Answer: C. Optimal substructure and overlapping subproblems
Explanation: Divide and conquer suits independent subproblems. Dynamic programming reuses the solutions of overlapping ones. ALSO KNOW (related points): • Which paradigm does merge sort follow? → Divide and conquer • What is the time complexity of the dynamic programming solution to Longest Common Subsequence for strings of lengths m and n? → O(mn) • Which technique is typically used for the N-Queens problem? → Backtracking • Using the two-pointer technique, what is the time complexity of finding a pair with a given sum in a sorted array? → O(n)

Correct Answer: B. Fractional knapsack
Explanation: 0/1 knapsack requires dynamic programming. Greedy fails when items cannot be divided. ALSO KNOW (related points): • Huffman coding is an example of which paradigm? → Greedy • What distinguishes memoization from tabulation? → Memoization is top-down (recursion with a cache); tabulation is bottom-up (iteratively filling a table) • What is the time complexity of Kadane's algorithm for the maximum subarray sum, and what is the answer for [-2, 1, -3, 4, -1, 2, 1, -5, 4]? → O(n); 6

Correct Answer: C. Greedy uses 3 (4+1+1); the optimum is 2 (3+3)
Explanation: Greedy coin change is optimal only for canonical coin systems. ALSO KNOW (related points): • Kruskal's MST algorithm efficiently uses which data structure to detect cycles? → Disjoint-set (union-find) • What is the complexity of Strassen's matrix multiplication algorithm? → About O(n^2.81)

Correct Answer: B. When the graph has negative edge weights
Explanation: Bellman-Ford handles negative edge weights and can detect negative cycles. ALSO KNOW (related points): • Which algorithm can detect a negative-weight cycle reachable from the source? → Bellman-Ford • What is the time complexity of the Floyd-Warshall all-pairs shortest path algorithm? → O(V³)

Correct Answer: C. Bellman-Ford
Explanation: After V - 1 rounds of relaxation, if any edge can still be relaxed, a negative cycle exists.

Correct Answer: A. Disjoint-set (union-find)
Explanation: Kruskal's algorithm sorts the edges and adds one only if its endpoints are in different sets.