Divide and Conquer Quiz: Test Your Knowledge

📚 Quick Study Guide

• ➗ Definition: Divide and Conquer is an algorithmic paradigm where a problem is recursively broken down into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
• 🔨 Three Steps:
  • Divide: Break the problem into smaller subproblems.
  • Conquer: Solve the subproblems recursively. If the subproblems are small enough, just solve them in a straightforward manner.
  • Combine: Combine the solutions to the subproblems into the solution for the original problem.
• ⏱️ Time Complexity (General): Many Divide and Conquer algorithms achieve logarithmic time complexity (e.g., $O(n \log n)$ for Merge Sort).
• 🧮 Common Examples:
  • Merge Sort
  • Quick Sort
  • Binary Search
  • Strassen's Matrix Multiplication
• 🧐 Key Idea: Dividing reduces problem size, making them easier to handle.

🧪 Practice Quiz

1. Which of the following is NOT a core step in the Divide and Conquer approach?
   1. Divide
   2. Conquer
   3. Combine
   4. Simplify
2. What is the primary advantage of using Divide and Conquer?
   1. Guaranteed optimal solution.
   2. Reduced time complexity for certain problems.
   3. Simpler code implementation.
   4. Avoidance of recursion.
3. Which sorting algorithm is a classic example of Divide and Conquer?
   1. Bubble Sort
   2. Insertion Sort
   3. Merge Sort
   4. Selection Sort
4. In the context of Divide and Conquer, what does "Conquer" typically involve?
   1. Ignoring the subproblems.
   2. Solving subproblems recursively.
   3. Combining subproblems directly.
   4. Dividing the subproblems further.
5. Binary search is an example of Divide and Conquer. What is the condition for it to work?
   1. The array must be unsorted.
   2. The array must be sorted.
   3. The array must contain only positive numbers.
   4. The array must be empty.
6. Strassen's algorithm is a Divide and Conquer algorithm used for:
   1. Sorting arrays
   2. Searching elements
   3. Matrix multiplication
   4. Graph traversal
7. What is the time complexity of Merge Sort?
   1. $O(n^2)$
   2. $O(n)$
   3. $O(n \log n)$
   4. $O(\log n)$