Chapter 18: Advanced Algorithms (Divide & Conquer, Greedy, DP, Backtracking)

Introduction

Advanced algorithmic paradigms provide systematic approaches to problem-solving. This chapter explores four fundamental techniques: Divide and Conquer, Greedy algorithms, Dynamic Programming, and Backtracking. Mastering these paradigms enables you to tackle complex problems efficiently and recognize patterns across different domains.

Why This Matters

These paradigms solve real-world problems:

Divide & Conquer: Merge sort, quick sort, binary search
Greedy: Huffman coding, Dijkstra's algorithm, task scheduling
Dynamic Programming: Route optimization, resource allocation, bioinformatics
Backtracking: Sudoku solvers, chess engines, constraint satisfaction

How to Study This Chapter

Understand the paradigm - When and why to use each technique
Recognize patterns - Identify problem characteristics
Practice implementations - Solve classic problems
Analyze complexity - Time and space trade-offs
Compare approaches - Same problem, different paradigms

Divide and Conquer

Divide and Conquer: Break problem into smaller subproblems, solve recursively, combine results.

Pattern

1. Divide: Split problem into smaller subproblems
2. Conquer: Solve subproblems recursively
3. Combine: Merge solutions

Merge Sort Example

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Divide
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Combine
        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    cout << "Original: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    mergeSort(arr, 0, arr.size() - 1);

    cout << "Sorted: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    return 0;
}

Maximum Subarray (Divide & Conquer)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int maxCrossingSum(vector<int>& arr, int left, int mid, int right) {
    int leftSum = INT_MIN;
    int sum = 0;

    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        leftSum = max(leftSum, sum);
    }

    int rightSum = INT_MIN;
    sum = 0;

    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        rightSum = max(rightSum, sum);
    }

    return leftSum + rightSum;
}

int maxSubarraySum(vector<int>& arr, int left, int right) {
    if (left == right) {
        return arr[left];
    }

    int mid = left + (right - left) / 2;

    int leftSum = maxSubarraySum(arr, left, mid);
    int rightSum = maxSubarraySum(arr, mid + 1, right);
    int crossSum = maxCrossingSum(arr, left, mid, right);

    return max({leftSum, rightSum, crossSum});
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    int maxSum = maxSubarraySum(arr, 0, arr.size() - 1);
    cout << "Maximum subarray sum: " << maxSum << endl;

    return 0;
}

Complexity: O(n log n)

Greedy Algorithms

Greedy: Make locally optimal choice at each step, hoping to find global optimum.

Characteristics

Makes choice that looks best at the moment
Never reconsiders decisions
Fast but not always optimal
Works when problem has greedy-choice property

Activity Selection Problem

Select maximum number of non-overlapping activities.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, finish;

    bool operator<(const Activity& other) const {
        return finish < other.finish;
    }
};

vector<int> activitySelection(vector<Activity>& activities) {
    // Sort by finish time
    sort(activities.begin(), activities.end());

    vector<int> selected;
    selected.push_back(0);  // First activity always selected

    int lastFinish = activities[0].finish;

    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastFinish) {
            selected.push_back(i);
            lastFinish = activities[i].finish;
        }
    }

    return selected;
}

int main() {
    vector<Activity> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9},
        {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
    };

    cout << "Activities (start, finish):" << endl;
    for (int i = 0; i < activities.size(); i++) {
        cout << i << ": (" << activities[i].start << ", "
             << activities[i].finish << ")" << endl;
    }

    vector<int> selected = activitySelection(activities);

    cout << "\nSelected activities: ";
    for (int idx : selected) {
        cout << idx << " ";
    }
    cout << endl;

    return 0;
}

Fractional Knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int weight, value;

    double valuePerWeight() const {
        return (double)value / weight;
    }

    bool operator<(const Item& other) const {
        return valuePerWeight() > other.valuePerWeight();
    }
};

double fractionalKnapsack(vector<Item>& items, int capacity) {
    sort(items.begin(), items.end());

    double totalValue = 0.0;
    int currentWeight = 0;

    for (const Item& item : items) {
        if (currentWeight + item.weight <= capacity) {
            // Take whole item
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            // Take fraction
            int remaining = capacity - currentWeight;
            totalValue += item.value * ((double)remaining / item.weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {
        {10, 60}, {20, 100}, {30, 120}
    };
    int capacity = 50;

    cout << "Items (weight, value):" << endl;
    for (int i = 0; i < items.size(); i++) {
        cout << i << ": (" << items[i].weight << ", "
             << items[i].value << ") = "
             << items[i].valuePerWeight() << " per unit" << endl;
    }

    double maxValue = fractionalKnapsack(items, capacity);
    cout << "\nMaximum value: " << maxValue << endl;

    return 0;
}

Complexity: O(n log n)

Dynamic Programming (DP)

Dynamic Programming: Solve complex problems by breaking into overlapping subproblems, storing results to avoid recomputation.

Characteristics

Overlapping subproblems
Optimal substructure
Memoization (top-down) or tabulation (bottom-up)

Fibonacci with DP

#include <iostream>
#include <vector>
using namespace std;

// Naive recursion: O(2^n)
int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Memoization (top-down): O(n)
int fibMemo(int n, vector<int>& memo) {
    if (n <= 1) return n;

    if (memo[n] != -1) return memo[n];

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Tabulation (bottom-up): O(n)
int fibTabulation(int n) {
    if (n <= 1) return n;

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// Space-optimized: O(1) space
int fibOptimized(int n) {
    if (n <= 1) return n;

    int prev2 = 0, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

int main() {
    int n = 10;

    cout << "Fibonacci(" << n << "):" << endl;
    cout << "Recursive: " << fibRecursive(n) << endl;

    vector<int> memo(n + 1, -1);
    cout << "Memoization: " << fibMemo(n, memo) << endl;

    cout << "Tabulation: " << fibTabulation(n) << endl;
    cout << "Optimized: " << fibOptimized(n) << endl;

    return 0;
}

0/1 Knapsack Problem

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                // Can include item i-1
                dp[i][w] = max(
                    dp[i - 1][w],  // Don't include
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  // Include
                );
            } else {
                // Can't include item i-1
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

int main() {
    vector<int> weights = {1, 3, 4, 5};
    vector<int> values = {1, 4, 5, 7};
    int capacity = 7;

    int maxValue = knapsack(weights, values, capacity);
    cout << "Maximum value: " << maxValue << endl;

    return 0;
}

Longest Common Subsequence (LCS)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int lcs(string& s1, string& s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

string reconstructLCS(string& s1, string& s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Build DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Reconstruct LCS
    string result;
    int i = m, j = n;

    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            result = s1[i - 1] + result;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result;
}

int main() {
    string s1 = "ABCDGH";
    string s2 = "AEDFHR";

    cout << "String 1: " << s1 << endl;
    cout << "String 2: " << s2 << endl;
    cout << "LCS length: " << lcs(s1, s2) << endl;
    cout << "LCS: " << reconstructLCS(s1, s2) << endl;

    return 0;
}

Complexity: O(m × n)

Backtracking

Backtracking: Try all possibilities systematically, abandoning paths that don't lead to solution.

N-Queens Problem

#include <iostream>
#include <vector>
using namespace std;

class NQueens {
private:
    int n;
    vector<vector<string>> solutions;

    bool isSafe(vector<int>& board, int row, int col) {
        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i] == col) return false;
        }

        // Check diagonal (top-left to bottom-right)
        for (int i = 0; i < row; i++) {
            if (abs(board[i] - col) == abs(i - row)) {
                return false;
            }
        }

        return true;
    }

    void solve(vector<int>& board, int row) {
        if (row == n) {
            // Found solution
            vector<string> solution;
            for (int i = 0; i < n; i++) {
                string rowStr(n, '.');
                rowStr[board[i]] = 'Q';
                solution.push_back(rowStr);
            }
            solutions.push_back(solution);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                solve(board, row + 1);
                // Backtrack (implicit - just try next column)
            }
        }
    }

public:
    NQueens(int size) : n(size) {}

    vector<vector<string>> solveNQueens() {
        vector<int> board(n, -1);
        solve(board, 0);
        return solutions;
    }

    void printSolutions() {
        cout << "Found " << solutions.size() << " solutions:" << endl;

        for (int s = 0; s < solutions.size(); s++) {
            cout << "\nSolution " << (s + 1) << ":" << endl;
            for (const string& row : solutions[s]) {
                cout << row << endl;
            }
        }
    }
};

int main() {
    int n = 4;
    NQueens nQueens(n);

    nQueens.solveNQueens();
    nQueens.printSolutions();

    return 0;
}

Sudoku Solver

#include <iostream>
#include <vector>
using namespace std;

class SudokuSolver {
private:
    vector<vector<int>> board;

    bool isValid(int row, int col, int num) {
        // Check row
        for (int j = 0; j < 9; j++) {
            if (board[row][j] == num) return false;
        }

        // Check column
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) return false;
        }

        // Check 3x3 box
        int boxRow = (row / 3) * 3;
        int boxCol = (col / 3) * 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[boxRow + i][boxCol + j] == num) {
                    return false;
                }
            }
        }

        return true;
    }

    bool solve() {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == 0) {
                    for (int num = 1; num <= 9; num++) {
                        if (isValid(row, col, num)) {
                            board[row][col] = num;

                            if (solve()) {
                                return true;
                            }

                            // Backtrack
                            board[row][col] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;  // All cells filled
    }

public:
    SudokuSolver(vector<vector<int>>& initial) : board(initial) {}

    bool solveSudoku() {
        return solve();
    }

    void printBoard() {
        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0 && i != 0) {
                cout << "------+-------+------" << endl;
            }
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0 && j != 0) {
                    cout << "| ";
                }
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    vector<vector<int>> puzzle = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    cout << "Sudoku Puzzle:" << endl;
    SudokuSolver solver(puzzle);
    solver.printBoard();

    if (solver.solveSudoku()) {
        cout << "\nSolution:" << endl;
        solver.printBoard();
    } else {
        cout << "No solution exists!" << endl;
    }

    return 0;
}

Paradigm Comparison

Paradigm	Approach	Time Complexity	When to Use
Divide & Conquer	Split, solve, combine	Often O(n log n)	Sorting, searching
Greedy	Local optimum	Often O(n log n)	Optimization with greedy-choice
Dynamic Programming	Overlapping subproblems	Often O(n²) or O(n×m)	Optimization, counting
Backtracking	Try all, prune bad	Exponential	Constraint satisfaction

Common Mistakes

Using DP when greedy works - Unnecessary complexity
Not identifying overlapping subproblems - Missing DP opportunity
Forgetting base cases - Infinite recursion
Not pruning in backtracking - Exploring too many paths
Wrong DP state definition - Incorrect subproblem structure
Greedy when optimal needed - Greedy doesn't guarantee optimum
Stack overflow - Too much recursion without memoization

Debugging Tips

Trace small examples - Work through by hand
Print DP table - Visualize subproblem solutions
Check base cases - Ensure correct handling
Verify recurrence relation - Correct formula
Test greedy counterexamples - Ensure greedy works
Limit backtracking depth - Prevent infinite exploration
Use iterative when possible - Avoid stack overflow

Mini Exercises

Implement quick select (divide & conquer)
Solve coin change problem (DP)
Implement Huffman coding (greedy)
Solve subset sum (backtracking/DP)
Find edit distance (DP)
Implement job scheduling (greedy)
Solve graph coloring (backtracking)
Matrix chain multiplication (DP)
Closest pair of points (divide & conquer)
Traveling salesman (DP/backtracking)

Review Questions

When should you choose DP over greedy?
What makes a problem suitable for divide and conquer?
How do you identify overlapping subproblems?
When is backtracking the only option?
What's the difference between memoization and tabulation?

Reference Checklist

By the end of this chapter, you should be able to:

Apply divide and conquer to sorting and searching
Recognize greedy-choice property
Implement DP with memoization and tabulation
Use backtracking for constraint satisfaction
Choose appropriate paradigm for problem
Analyze time and space complexity
Optimize DP solutions
Prune backtracking search space

Next Steps

Chapter 19 focuses on debugging and optimization techniques—profiling, performance analysis, and practical strategies for writing efficient, bug-free code.

Key Takeaway: Advanced algorithmic paradigms provide systematic problem-solving approaches. Divide and conquer splits problems efficiently. Greedy makes locally optimal choices. Dynamic programming reuses solutions to overlapping subproblems. Backtracking explores all possibilities with pruning. Mastering these paradigms enables you to solve complex problems efficiently.