Divide & Conquer Algorithms (OCR A Level Computer Science)

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:

1. Introduction: Briefly explain the problem of sluggish search functionality in the e-commerce platform

2. 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

3. 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.