Problem Decomposition with Divide and Conquer

Overview

Problem decomposition is the process of breaking down a complex problem into smaller, more manageable sub-problems. This approach is often combined with the divide and conquer strategy, where each smaller task is solved independently and the solutions are then combined to address the overall problem. Additionally, some tasks can be performed simultaneously to increase efficiency.

Understanding how to apply problem decomposition and identify opportunities for concurrent execution is crucial for developing effective and scalable solutions.

Divide and Conquer

Definition:

• A problem-solving strategy that involves:

  1. Dividing a problem into smaller, independent sub-problems.
  2. Solving each sub-problem individually.
  3. Combining the results to form a solution to the original problem. Purpose:

• Simplifies complex problems by focusing on smaller, easier-to-solve parts.

FUNCTION mergeSort(array)
    IF length(array) <= 1 THEN
        RETURN array
    ENDIF
    mid = length(array) / 2
    left = mergeSort(array[0:mid])
    right = mergeSort(array[mid:])
    RETURN merge(left, right)
END FUNCTION

Parallel or Simultaneous Task Execution

Definition:

• Some sub-tasks can be executed concurrently, either on different processors or in separate threads, to speed up the solution. Benefits:

• Reduces the overall time required to solve a problem.

• Utilises system resources more efficiently.

Applying Problem Decomposition

To effectively decompose a problem:

1. Analyse the Problem:

• Understand the overall goal and identify key tasks.

2. Divide the Problem:

• Split the main problem into smaller, self-contained sub-problems.

3. Solve Sub-Problems:

• Address each sub-problem individually.

4. Combine Solutions:

• Integrate the results to form the complete solution.

5. Identify Parallel Tasks:

• Determine which sub-problems can be executed concurrently to improve efficiency.

Divide and Conquer in Practice

Search Algorithms:

Binary Search splits the search space in half at each step.

FUNCTION binarySearch(array, target)
    low = 0
    high = length(array) - 1
    WHILE low <= high
        mid = (low + high) / 2
        IF array[mid] == target THEN
            RETURN mid
        ELSEIF array[mid] < target THEN
            low = mid + 1
        ELSE
            high = mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
END FUNCTION

Pathfinding Algorithms:

Algorithms like A* use decomposition by exploring possible paths and prioritising the most promising ones.

Benefits of Problem Decomposition

1. Simplifies Complex Problems: By breaking them into smaller parts, making them easier to understand and solve.
2. Enables Reusability: Sub-solutions can often be reused in other problems.
3. Improves Debugging and Testing: Smaller tasks are easier to test and debug individually.
4. Facilitates Parallelism: Concurrent execution of sub-tasks speeds up problem-solving.

Note Summary