Introduction
Most algorithmic problems can be approached using a small set of recurring strategies, known as design paradigms. Rather than inventing a new technique for every problem, experienced problem-solvers recognize which paradigm fits the structure of the problem at hand. This lesson previews the four major paradigms covered in depth later in this course: divide and conquer, greedy algorithms, dynamic programming, and backtracking. Recognizing these patterns early will help you classify new problems quickly.
Cricket analogy: A captain doesn't invent a new field placement for every ball; MS Dhoni recognized recurring match situations - death overs, powerplay, spin-friendly pitch - and applied a known tactic, just as recognizing a problem's paradigm beats reinventing a strategy each time.
Key Concepts
Divide and conquer breaks a problem into independent subproblems of the same type, solves each subproblem recursively, and then combines the results; it works best when subproblems do not overlap. Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution; they work only when the problem has the greedy-choice property and optimal substructure. Dynamic programming also breaks a problem into subproblems, but unlike divide and conquer, those subproblems overlap, so DP stores and reuses previously computed results to avoid redundant work. Backtracking incrementally builds candidate solutions and abandons a candidate as soon as it determines the candidate cannot possibly lead to a valid solution, making it well suited to constraint-satisfaction and combinatorial search problems.
Cricket analogy: Splitting a run chase into two non-overlapping powerplay and death-over targets that each batter tackles independently before adding the totals is divide and conquer, while a fielding captain who always takes the safest catch each ball without reviewing past overs is playing greedy.
Example
# A one-line taste of each paradigm, detailed later in this course.
# Divide and conquer: merge sort splits the array in half, sorts each half,
# and merges the sorted halves.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
# Greedy: activity selection picks the activity that finishes earliest first.
def max_activities(activities):
activities.sort(key=lambda a: a[1]) # sort by finish time
count, last_finish = 0, float('-inf')
for start, finish in activities:
if start >= last_finish:
count += 1
last_finish = finish
return count
print(merge_sort([5, 2, 4, 1, 3]))
print(max_activities([(1, 3), (2, 5), (4, 7), (6, 9)]))Analysis
merge_sort demonstrates divide and conquer: the array is split into independent halves that do not share data, so each half can be sorted on its own before merging, giving O(n log n) time. max_activities demonstrates the greedy paradigm: sorting by finish time and always picking the next compatible activity is provably optimal for this specific problem, achieving O(n log n) time dominated by the sort. Later modules will contrast these with dynamic programming, where overlapping subproblems require memoization or tabulation (as in the 0/1 knapsack problem), and backtracking, where invalid partial solutions are pruned early (as in the N-Queens problem). Choosing the right paradigm is often the single biggest factor in whether a solution is efficient or intractable.
Cricket analogy: Sorting fielders by their fastest reaction time and always assigning the next catch to the quickest available fielder is the greedy max_activities pattern, while splitting the scorecard into first-innings and second-innings halves computed independently before merging is merge_sort's divide and conquer.
Key Takeaways
- Divide and conquer: split into independent, non-overlapping subproblems, solve recursively, and combine. Canonical example: merge sort.
- Greedy: make the locally optimal choice at each step and never reconsider it. Canonical example: activity selection problem.
- Dynamic programming: break into overlapping subproblems and cache results to avoid recomputation. Canonical example: 0/1 knapsack problem.
- Backtracking: build candidate solutions incrementally and prune branches that cannot lead to a valid solution. Canonical example: N-Queens problem.
- Recognizing which paradigm fits a problem's structure is often more important than knowing any single algorithm by heart.
Practice what you learned
1. What is the key structural difference between divide and conquer and dynamic programming?
2. Which condition must hold for a greedy algorithm to guarantee an optimal solution?
3. Backtracking is most naturally suited to which type of problem?
4. In the max_activities example, why is sorting by finish time (rather than start time or duration) the correct greedy choice?
Was this page helpful?
You May Also Like
The Divide and Conquer Paradigm
Learn how divide, conquer, and combine steps break large problems into smaller solvable subproblems.
The Greedy Algorithm Paradigm
Learn how greedy algorithms build solutions one locally optimal choice at a time, and when that strategy actually yields a global optimum.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.
The Backtracking Paradigm
Learn how backtracking systematically builds candidate solutions and abandons paths that cannot possibly succeed.