dsa-algorithm-paradigms

name

dsa-algorithm-paradigms

description

Core algorithm design paradigms including dynamic programming, greedy algorithms, divide and conquer, sorting, searching, and backtracking with decision guidance and trade-off analysis. Use when: selecting an algorithm paradigm for a new problem, teaching dynamic programming memoisation vs tabulation, reviewing greedy algorithm correctness, explaining divide-and-conquer recursion, analysing sorting algorithm choices, or recognising which algorithmic strategy applies to a given problem shape.

DSA Algorithm Paradigms

When to Use

• Selecting the right algorithm paradigm before writing code
• Teaching DP (memoisation vs tabulation) or explaining overlapping sub-problems
• Reviewing greedy code for correctness (does local optimum imply global optimum?)
• Analysing divide-and-conquer recursion depth and merge cost
• Explaining sorting algorithm trade-offs (stability, in-place, adaptive)
• Recognising backtracking as constrained exhaustive search

Sorting and Searching

Sorting Algorithm Reference

Algorithm	Best	Average	Worst	Space	Stable?
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Introspective sort (.NET Array.Sort() / List<T>.Sort())	O(n log n)	O(n log n)	O(n log n)	O(log n)	No (not guaranteed)

.NET's Array.Sort() and List<T>.Sort() use an introspective sort variant and are not guaranteed stable. If you need a stable sort in .NET, LINQ's OrderBy is stable.

Binary Search

Binary search requires a sorted collection and halves the search space at each step.

// Canonical binary search template
int left = 0, right = array.Length - 1;
while (left <= right)
{
    int mid = left + (right - left) / 2;  // avoids integer overflow
    if (array[mid] == target) return mid;
    if (array[mid] < target)  left = mid + 1;
    else                      right = mid - 1;
}
return -1; // not found

Common variants:

• Find first occurrence: when array[mid] == target, set right = mid - 1 and continue
• Find insertion point: return left after the loop
• Search on a function: binary search the answer space, not an array

Dynamic Programming

Two Signs That DP Applies

1. Overlapping sub-problems — the same smaller problem is solved multiple times
2. Optimal substructure — the optimal solution to the full problem is built from optimal sub-solutions

Memoisation (Top-Down)

var memo = new Dictionary<int, long>();

long Fib(int n)
{
    if (n <= 1) return n;
    if (memo.TryGetValue(n, out var cached)) return cached;
    memo[n] = Fib(n - 1) + Fib(n - 2);
    return memo[n];
}

• Natural recursive structure — add cache to existing recursion
• Space: O(n) cache + O(n) call stack

Tabulation (Bottom-Up)

long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];

• Iterative, no call stack overhead
• Space: O(n); often reducible to O(1) for linear recurrences

Biotrackr Anchor — Report Caching as DP

CachingMcpToolWrapper stores tool results keyed by tool name + parameter hash. This is tabulated DP applied to AI tool calls: if the same tool call (same inputs) was made before, return the cached result rather than re-executing.

Teaching angle: Memoisation and caching are the same idea at different scales. DP memoises recursive sub-problem results; a service cache memoises expensive computation results. Both trade space for time.

Greedy Algorithms

When Greedy Works

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a globally optimal solution. It is correct only when the greedy choice property holds: local optima compose into a global optimum.

Classic Greedy Problems

• Activity selection (interval scheduling maximisation)
• Dijkstra's shortest path (greedy on distances)
• Huffman encoding (greedy on frequencies)
• Fractional knapsack

Biotrackr Anchor — Quota Allocation

Azure Container Apps and APIM apply greedy throttling: allow a request if quota remains, reject immediately if not. This is a greedy policy — no lookahead, no reservation.

Teaching angle: Greedy works here because quota is consumed in the order of arrival and there is no future information that would change the decision. If the problem were "maximise the number of high-priority requests served given a quota window", greedy fails — you would need DP or a priority queue.

Divide and Conquer

Pattern

1. Divide — split the problem into independent sub-problems
2. Conquer — solve each sub-problem recursively
3. Combine — merge sub-results into the final answer

Recurrence Analysis (Master Theorem)

For T(n) = aT(n/b) + O(n^d):

• a > b^d: T(n) = O(n^log_b(a))
• a = b^d: T(n) = O(n^d log n)
• a < b^d: T(n) = O(n^d)

Merge sort: a=2, b=2, d=1 → a = b^d → O(n log n).

Biotrackr Anchor — Parallel Service Health Checks

Health checks across 14 Biotrackr services can run in parallel then be merged — divide and conquer on the service graph:

// Conquer: each check runs independently
var tasks = services.Select(s => CheckHealthAsync(s));

// Combine: aggregate results
var results = await Task.WhenAll(tasks);

Teaching angle: Divide-and-conquer is why Task.WhenAll is faster than sequential awaits. You pay O(max individual duration) instead of O(sum of all durations). The "merge" step is trivial (collect results), so the paradigm reduces to parallel fan-out.

Backtracking

Pattern

Backtracking is constrained exhaustive search — explore all candidate solutions, prune branches that violate constraints early.

def backtrack(state, candidates):
    if is_solution(state): record(state); return
    for each candidate in candidates:
        if is_valid(state + candidate):
            apply(candidate)
            backtrack(state + candidate, remaining)
            undo(candidate)           // backtrack

Use for: permutations, combinations, N-Queens, Sudoku, constraint satisfaction problems.

Note: Backtracking is inherently exponential — it is only practical when pruning significantly reduces the search space.

Recognising Which Paradigm to Apply

Problem Signal	Likely Paradigm
Overlapping sub-problems, optimal substructure	Dynamic Programming
Local choice leads to global optimum (provable)	Greedy
Split into independent equal sub-problems	Divide and Conquer
"All valid combinations / arrangements"	Backtracking
Sorted input, find target	Binary Search
Need all items sorted once	Merge/Tim sort
Streaming data, min/max per window	Monotonic deque or heap