Divide-and-conquer approach
Divide and conquer is a problem-solving strategy that decomposes a problem into smaller parts, handles them separately, and combines or completes their results.
Grokking Algorithms, Second Edition
A divide-and-conquer strategy solves a problem by dividing it into smaller subproblems, solving those subproblems, and combining their results.
- How it is used
- Uses recursive decomposition as a general way to approach unfamiliar problems and develop quicksort.
- How deep it goes
- Works through base and recursive cases with a field and quicksort code, while deferring the proof behind the field reduction.
- Examples
- Uses equal square plots on a 1,680 m × 640 m field, recursive array summation, and pivot-based array sorting.
- What you can do after
- Build it from scratch by identifying a base case, reducing each recursive problem, and combining results in quicksort.
Read how Grokking Algorithms, Second Edition explains divide-and-conquer approach →
Functional Design and Architecture: Examples in Haskell
Divide and conquer is a design strategy that manages complexity by separating a problem into smaller, more independently tractable parts.
- How it is used
- Manages software complexity by separating responsibilities, interfaces, implementations, architectural layers, and error domains.
- How deep it goes
- Explains interface boundaries, substitution, dependency injection, adapters, and error-domain conversion, while stopping short of formal algorithmic analysis.
- Examples
- Uses sensor interfaces, thermometer implementations, an Observer, an IoC wiring example, and a Kelvin-to-Celsius adapter.
- What you can do after
- Apply interfaces, adapters, and dependency injection to isolate implementations and make software more maintainable, testable, and readable.
Machine Learning Algorithms in Depth
Divide and conquer is a problem-solving paradigm that recursively decomposes a problem into smaller subproblems and combines their solutions.
- How it is used
- Uses recursive decomposition to organize algorithmic solutions, including binary search and CART decision-tree construction.
- How deep it goes
- Explains decomposition, combination, recursion, binary-search complexity, and a from-scratch implementation, while deferring detailed CART treatment.
- Examples
- Uses binary search, quick sort, merge sort, heap sort, and recursive CART threshold partitioning as concrete examples.
- What you can do after
- Builds a recursive binary-search algorithm from scratch and recognize divide-and-conquer structure in machine-learning algorithms.
Read how Machine Learning Algorithms in Depth explains divide-and-conquer approach →
Related concepts
- quicksortused by · Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot and recursively sorts the resulting subranges.
- binary searchincludes · Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
- accuracyproduces · Accuracy is the degree to which an output, prediction, or measurement agrees with a correct or reference outcome under a specified criterion.
- couplingproduces · Coupling is the degree of dependency between software components, including how their behavior, availability, or changes affect one another.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.