Divide & Conquer Algorithms (OCR A Level Computer Science)
Revision Note
Written by: Robert Hampton
Reviewed by: James Woodhouse
Divide & Conquer Algorithms
What is the Divide & Conquer Strategy?
Divide and conquer is a strategy to make a complex task easier by breaking it into smaller, more manageable tasks
For example, organising a large conference can be split into smaller tasks such as booking the venue, coordinating with speakers and marketing
Implementing divide and conquer
Divide and conquer contains three steps:
Divide - The problem needs to be broken down into sub-problems
Conquer - The sub-problems then need be solved independently
Combine - The solutions to the sub-problems can then be combined to form the overall solution to the problem
For example, in home renovation, the project can be broken down into individual rooms or specific elements such as flooring, painting and electrics
Process of divide and conquer to solve problems
Benefits | Drawbacks |
|---|---|
Divide and conquer can make programs more time efficient. | Not all problems can be broken down and solved independently. |
As problems are divided into sub-problems they can make effective use of cache memory. | It can possibly cause stack overflows if recursion is being used. |
Task parallelism
This is when several tasks or sub-tasks can be carried out concurrently (at the same time) to speed up the overall completion time
For example, on a factory assembly line, different components of a product can be put together at the same time by different teams or machines
Worked Example
You are the lead software engineer for a company building an e-commerce platform. Your team has been tasked with improving the website's search functionality, which has recently been sluggish due to an exponential growth in the number of products available.
Describe how you would use the divide and conquer strategy and task parallelism to tackle this problem. Make sure you provide specific examples for each.
How to answer this question:
Introduction: Briefly explain the problem of sluggish search functionality in the e-commerce platform
Divide and conquer: Describe how you would break the problem into smaller, more manageable tasks
For example, consider breaking down the search process into tasks like query parsing, data retrieval, and front-end rendering
Task parallelism: Explain how tasks or sub-tasks can be executed simultaneously to speed up the problem-solving
For instance, data retrieval can be parallelised by dividing the product database into smaller chunks that can be searched simultaneously
Answer:
The issue at hand is the slow search functionality on the e-commerce platform. This is a critical problem as it hampers the user experience and could decrease sales.
The problem can be divided into smaller, more manageable parts to approach this issue efficiently. Specifically, we can isolate query parsing, which involves translating user text input into a query. We could work on data retrieval, where the relevant product information is fetched from the database as well as front-end rendering which is responsible for displaying the products to the users.
Once the problem is segmented, we can apply task parallelism to expedite the resolution. During the data retrieval process, we can partition the product database into smaller index-based segments, allowing multiple server instances to search them simultaneously. Concurrently, front-end rendering can implement lazy loading techniques to begin displaying products as they are retrieved, thus improving the speed of the search function.
We can notably improve the search functionality and user experience by employing both divide and conquer and task parallelism.
Acceptable Answer You Could Have Given Instead
Our website's slow search function needs to be fixed. The problem could be broken down into a few parts:
improving the search algorithm
making our database faster
optimising the user interface
We can work on multiple steps simultaneously to solve this problem. For instance, one team can focus on the database while another works on the user interface. This approach would help make the search function faster and satisfy our users.
Both answers effectively address the problem but vary in the depth and clarity with which they explain the concepts of divide and conquer and task parallelism.
Last updated:
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?
