Algorithmic paradigms and design patterns

Divide and conquer

• Decompose and combine
• Divide - conquer - combine
• eg. Merge sort

Dynamic programming

• 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

Greedy

• never reconsiders
• reduce problem into a small one with each step
• eg. Coin problem, Kruskal’s algorithm

Backtracking

• eg. Eight queens

Design patterns

• The composition over inheritance principle
• C2 wiki
• Competitive programmers handbook