Virtual Labs

1. Which of the following best describes the steps in the divide and conquer strategy?

a: Conquer → Divide → Combine Explanation

Explanation

b: Divide → Conquer → Combine Explanation

Explanation

c: Divide → Combine → Conquer Explanation

Explanation

d: Combine → Conquer → Divide Explanation

Explanation

2. In divide and conquer, how are the subproblems solved?

a: Dependently Explanation

Explanation

b: Concurrently Explanation

Explanation

c: Independently Explanation

Explanation

d: In parallel Explanation

Explanation

3. Which of the following is an example of the divide-and-conquer approach?

a: Merge sort Explanation

Explanation

b: Linear search Explanation

Explanation

c: Counting the number of elements in an array Explanation

Explanation

d: Finding the sum using a single loop Explanation

Explanation

4. In merge sort, what represents the "divide" step of the divide-and-conquer strategy?

a: Combining two sorted subarrays Explanation

Explanation

b: Splitting the array into smaller subarrays Explanation

Explanation

c: Comparing every pair of elements Explanation

Explanation

d: Removing duplicate elements Explanation

Explanation

5. In a divide-and-conquer algorithm, what is the purpose of the conquer step?

a: Divide the original problem into more subproblems Explanation

Explanation

b: Solve the smaller subproblems Explanation

Explanation

c: Randomly rearrange the input Explanation

Explanation

d: Delete the original input Explanation

Explanation

6. Why is merge sort considered a divide-and-conquer algorithm?

a: It divides the input into smaller subarrays, recursively sorts them, and combines the sorted results. Explanation

Explanation

b: It always selects the largest element first. Explanation

Explanation

c: It solves the entire array using only one comparison. Explanation

Explanation

d: It removes half of the elements before sorting. Explanation

Explanation

7. If a divide-and-conquer algorithm divides a problem of size

N

into two subproblems of size approximately

N/2

, what happens to the number of subproblems after each division level?

a: It approximately doubles. Explanation

Explanation

b: It remains constant. Explanation

Explanation

c: It becomes zero. Explanation

Explanation

d: It is always reduced by one. Explanation

Explanation

8. For a balanced divide-and-conquer algorithm that repeatedly halves a problem of size

N

, approximately how many levels of division are required to reach subproblems of size

1

N

Explanation

N^2

Explanation

\log_2 N

Explanation

d: 2N Explanation

Explanation

9. Which expression best represents the recurrence for an algorithm that divides a problem of size

N

into two subproblems of size

N/2

and performs

O(N)

work to combine their results?

T(N)=T(N-1)+O(1)

Explanation

T(N)=2T(N/2)+O(N)

Explanation

T(N)=T(N/2)+O(1)

Explanation

T(N)=2T(N-1)+O(N)

Explanation

Merge Sort