CS 213 - Long Quiz

A problem involves finding the maximum sum of a contiguous subarray in an array of integers. Which algorithm design technique is most suitable?

• Brute Force

• Divide and Conquer

• Dynamic Programming

• Greedy Algorithm

Consider a merge sort implementation on an array of size 8. How many times will the array be split before merging begins?

• 2

• 3

• 4

• 7

A company needs to calculate the number of inversions in an array. Which Divide and Conquer-based algorithm can efficiently solve this problem?

• Quick Sort

• Merge Sort

• Binary Search

• Heap Sort

Which of the following is NOT a characteristic of Divide and Conquer?

• Breaking the problem into smaller subproblems.

• Solving subproblems independently.

• Combining solutions to subproblems.

• Iteratively solving the subproblems.

What is the purpose of combining solutions in Divide and Conquer?

• To ensure correctness of the base case.

• To merge subproblem solutions into the final result.

• To analyze the complexity.

• To eliminate overlapping subproblems.

In Divide and Conquer, what is a common base case for recursive algorithms?

• When the problem size is reduced to a single element.

• When the input is sorted.

• When the recursion depth reaches n/2.

• When the solution is already optimal.

In the context of Divide and Conquer, what does “divide” refer to?

• Splitting the input into multiple overlapping subproblems.

• Splitting the input into two or more independent subproblems.

• Merging solutions.

• Reusing previously solved subproblems.

A problem requires finding the nth Fibonacci number. Which method demonstrates the essence of dynamic programming?

• Recursive calls with memoization.

• Iterative computation.

• Using a divide and conquer approach.

• Both A and B.

Which of the following problems is best solved using dynamic programming?

• Finding the shortest path in a graph with non-negative weights.

• Sorting an array of integers.

• Finding the maximum sum of a contiguous subarray.

• Solving the 0/1 Knapsack Problem.

Which of the following conditions is necessary for using dynamic programming?

• Subproblems must be independent.

• The problem must have overlapping subproblems and optimal substructure.

• The problem must be recursive.

• Subproblems must not depend on each other.