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	Name	Example	Operations (n=1000)
O(1)	Constant	Array access	1
O(log n)	Logarithmic	Binary search	10
O(n)	Linear	Linear search	1,000
O(n log n)	Linearithmic	Merge sort	10,000
O(n²)	Quadratic	Bubble sort	1,000,000
O(2^n)	Exponential	Recursive fib	10^301

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

Algorithm	Best	Average	Worst	Space	Stable
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
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
Tim Sort	O(n)	O(n log n)	O(n log n)	O(n)	Yes

---

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

Pattern	Example	State	Complexity
Linear	Fibonacci	dp[i]	O(n)
2D Grid	Path count	dp[i][j]	O(n×m)
Interval	Matrix chain	dp[i][j]	O(n³)
Subset	Knapsack	dp[mask]	O(2^n)
Tree	Tree DP	dp[node]	O(n)

---

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

Component	Interface
stl-master	Container selection
performance-optimizer	Algorithm optimization
modern-cpp-expert	Ranges and concepts
cpp-fundamentals-agent	Basic concepts

---

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