Problem Decomposition with Divide and Conquer (OCR A-Level Computer Science): Flashcards
📚Flashcards
Practise the cards
12 cards from this deck
ShowHide
Practise the cards
12 cards from this deck
Problem decomposition
Problem decomposition
Breaking complex problem into smaller, manageable sub-problems
3 steps of divide & conquer
3 steps of divide & conquer
- Divide into sub-problems 2) Solve each 3) Combine results
Purpose of divide & conquer
Purpose of divide & conquer
Simplifies complex problems by focusing on smaller parts
Parallel task execution
Parallel task execution
Sub-tasks executed concurrently on different processors/threads
Benefit of parallel execution
Benefit of parallel execution
Reduces overall time & uses system resources more efficiently
Merge Sort strategy type
Merge Sort strategy type
Divide & conquer algorithm
Binary Search strategy type
Binary Search strategy type
Divide & conquer (splits search space in half each step)
How decomposition simplifies problems
How decomposition simplifies problems
Breaks into smaller parts, easier to understand & solve
Reusability benefit of decomposition
Reusability benefit of decomposition
Sub-solutions can be reused in other problems
Testing benefit of decomposition
Testing benefit of decomposition
Smaller tasks easier to test & debug individually
Over-decomposition mistake
Over-decomposition mistake
Breaking into too many sub-problems makes solution too complex
Ignoring dependencies mistake
Ignoring dependencies mistake
Not handling tasks that depend on results of others