Problem Decomposition with Divide and Conquer (OCR A-Level Computer Science): Flashcards

Problem decomposition

Breaking complex problem into smaller, manageable sub-problems

3 steps of divide & conquer

1. Divide into sub-problems 2) Solve each 3) Combine results

Purpose of divide & conquer

Simplifies complex problems by focusing on smaller parts

Parallel task execution

Sub-tasks executed concurrently on different processors/threads

Benefit of parallel execution

Reduces overall time & uses system resources more efficiently

Merge Sort strategy type

Divide & conquer algorithm

Binary Search strategy type

Divide & conquer (splits search space in half each step)

How decomposition simplifies problems

Breaks into smaller parts, easier to understand & solve

Reusability benefit of decomposition

Sub-solutions can be reused in other problems

Testing benefit of decomposition

Smaller tasks easier to test & debug individually

Over-decomposition mistake

Breaking into too many sub-problems makes solution too complex

Ignoring dependencies mistake

Not handling tasks that depend on results of others