Algorithms

Algorithms Skill

Production-Grade Learning Skill | Algorithms & Data Structures

Master algorithm design and implementation in C++ with complexity analysis.

Complexity Analysis

Big O Notation Reference

Complexity Analysis Framework

// Time Complexity Analysis Template
// 1. Count primitive operations
// 2. Express as function of input size n
// 3. Keep highest order term
// 4. Drop constants

// Example: Find maximum
int findMax(const std::vector<int>& v) {  // O(n)
    int max = v[0];                        // O(1)
    for (int i = 1; i < v.size(); ++i) {   // O(n) iterations
        if (v[i] > max) {                  // O(1)
            max = v[i];                    // O(1)
        }
    }
    return max;                            // O(1)
}  // Total: O(1) + O(n) * O(1) = O(n)

Sorting Algorithms

STL Sorting

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1, 9};

// Introsort - O(n log n) guaranteed
std::sort(v.begin(), v.end());

// Stable sort - preserves relative order of equal elements
std::stable_sort(v.begin(), v.end());

// Partial sort - only first k elements sorted
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// Nth element - partition around nth element (O(n) average)
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());

// Custom comparator (descending order)
std::sort(v.begin(), v.end(), std::greater<int>());

// Sort by projection (C++20)
std::ranges::sort(v, {}, [](int x) { return std::abs(x); });

Sorting Algorithm Comparison

Searching Algorithms

Binary Search

#include <algorithm>

// STL binary search - O(log n), requires sorted range
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// Check existence
bool found = std::binary_search(v.begin(), v.end(), 5);

// Find position
auto it = std::lower_bound(v.begin(), v.end(), 5);  // First >= 5
auto it2 = std::upper_bound(v.begin(), v.end(), 5); // First > 5

// Range of equal elements
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 5);

// Custom binary search with predicate
template<typename T, typename Pred>
T binary_search_first_true(T lo, T hi, Pred pred) {
    while (lo < hi) {
        T mid = lo + (hi - lo) / 2;
        if (pred(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

Graph Algorithms

Graph Representations

// Adjacency List (preferred for sparse graphs)
std::vector<std::vector<int>> adj(n);
adj[0].push_back(1);  // Edge 0 -> 1

// Adjacency List with weights
std::vector<std::vector<std::pair<int, int>>> adj(n);
adj[0].push_back({1, weight});  // Edge 0 -> 1 with weight

// Adjacency Matrix (for dense graphs)
std::vector<std::vector<int>> adj(n, std::vector<int>(n, 0));
adj[0][1] = 1;  // Edge 0 -> 1

BFS - Breadth First Search

std::vector<int> bfs(int start, const std::vector<std::vector<int>>& adj) {
    std::vector<int> dist(adj.size(), -1);
    std::queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;  // Shortest distances from start
}

DFS - Depth First Search

void dfs(int node, const std::vector<std::vector<int>>& adj,
         std::vector<bool>& visited, std::vector<int>& result) {
    visited[node] = true;
    result.push_back(node);

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited, result);
        }
    }
}

Dijkstra's Algorithm

std::vector<int> dijkstra(int start,
    const std::vector<std::vector<std::pair<int,int>>>& adj) {

    std::vector<int> dist(adj.size(), INT_MAX);
    std::priority_queue<std::pair<int,int>,
        std::vector<std::pair<int,int>>,
        std::greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;  // Skip outdated entries

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Dynamic Programming

DP Framework

// 1. Define state: What subproblem does dp[i] represent?
// 2. Define transition: How to compute dp[i] from previous states?
// 3. Define base case: What are the initial values?
// 4. Define answer: Which state(s) give the final answer?

// Example: Longest Increasing Subsequence
int lis(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);  // dp[i] = LIS ending at i

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}

// Optimized LIS with binary search - O(n log n)
int lisOptimized(const std::vector<int>& nums) {
    std::vector<int> tails;
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}

Common DP Patterns

Algorithm Selection Flowchart

What type of problem?
├── Searching
│   ├── Sorted data? → Binary Search O(log n)
│   └── Unsorted? → Linear Search O(n) or Hash O(1)
├── Sorting
│   ├── Need stable? → std::stable_sort
│   ├── Partial sort? → std::partial_sort
│   └── General? → std::sort
├── Optimization
│   ├── Overlapping subproblems? → Dynamic Programming
│   └── Greedy choice property? → Greedy Algorithm
├── Graph
│   ├── Shortest path (unweighted)? → BFS
│   ├── Shortest path (weighted)? → Dijkstra/Bellman-Ford
│   ├── All pairs shortest? → Floyd-Warshall
│   └── Minimum spanning tree? → Kruskal/Prim
└── String
    ├── Pattern matching? → KMP/Rabin-Karp
    └── Longest common? → DP

Troubleshooting Decision Tree

Algorithm not working correctly?
├── Wrong output
│   ├── Check base cases
│   ├── Verify loop bounds
│   ├── Test edge cases (empty, single element)
│   └── Print intermediate values
├── Time Limit Exceeded (TLE)
│   ├── Check complexity matches constraint
│   ├── Look for unnecessary recomputation
│   ├── Consider memoization/DP
│   └── Use better data structure
├── Memory Limit Exceeded (MLE)
│   ├── Reduce DP state dimensions
│   ├── Use rolling array technique
│   └── Clear visited sets between runs
└── Runtime Error
    ├── Check array bounds
    ├── Check integer overflow
    └── Check stack overflow (recursion depth)

Unit Test Template

#include <gtest/gtest.h>
#include "algorithms.hpp"

class AlgorithmTest : public ::testing::Test {
protected:
    void SetUp() override {
        sorted_vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        unsorted_vec = {5, 2, 8, 1, 9, 3, 7, 4, 6, 10};
    }

    std::vector<int> sorted_vec;
    std::vector<int> unsorted_vec;
};

TEST_F(AlgorithmTest, BinarySearchFindsElement) {
    EXPECT_TRUE(std::binary_search(sorted_vec.begin(), sorted_vec.end(), 5));
    EXPECT_FALSE(std::binary_search(sorted_vec.begin(), sorted_vec.end(), 11));
}

TEST_F(AlgorithmTest, SortProducesOrderedOutput) {
    std::sort(unsorted_vec.begin(), unsorted_vec.end());
    EXPECT_TRUE(std::is_sorted(unsorted_vec.begin(), unsorted_vec.end()));
}

TEST_F(AlgorithmTest, BFSFindsShortestPath) {
    std::vector<std::vector<int>> adj = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};
    auto dist = bfs(0, adj);
    EXPECT_EQ(dist[0], 0);
    EXPECT_EQ(dist[1], 1);
    EXPECT_EQ(dist[3], 2);
}

TEST_F(AlgorithmTest, LISHandlesEdgeCases) {
    EXPECT_EQ(lis({}), 0);
    EXPECT_EQ(lis({1}), 1);
    EXPECT_EQ(lis({3, 2, 1}), 1);  // Decreasing
    EXPECT_EQ(lis({1, 2, 3}), 3);  // Increasing
}

Integration Points

C++ Plugin v3.0.0 - Production-Grade Learning Skill