Algorithmic paradigms and design patterns
Divide and conquer
- Decompose and combine
- Divide - conquer - combine
- eg. Merge sort
- Name?? - Decompose and overlap
- Can be seen as a special D&C where caching is applied.
- Gives an optimised solution - reuse previous solutions.
- eg. Knapsack, Fibonacci
wiki | challenges | patterns
- never reconsiders
- reduce problem into a small one with each step
- eg. Coin problem, Kruskal's algorithm
Updated 02 January 2023