Algorithms and Techniques in C++

A comprehensive collection of algorithms and data structures commonly used in competitive programming and software development, implemented in C++.

📋 Table of Contents

• Overview
• Algorithms and Data Structures
  • Graph Algorithms
  • Search Algorithms
  • Data Structures
  • Mathematical Algorithms
  • Array Techniques
  • Dynamic Programming
• Project Structure
• Getting Started
• Usage Examples

🚀 Algorithms and Data Structures

Graph Algorithms

Breadth-First Search (BFS)

Location: BFS/

Implements multiple variants of BFS for different use cases:

• bfs1 - Basic BFS traversal returning distances
• bfs2 - BFS with visited tracking for long long integers
• BFSPath - BFS that finds and returns the shortest path between two nodes
• bfs2path - BFS path finding with long long integers

Use Cases:

• Finding shortest path in unweighted graphs
• Level-order traversal
• Connected components detection

Depth-First Search (DFS)

Location: DFS/

Implements DFS variants for graph traversal:

• dfs1 - DFS with for-each loop iteration
• dfs2 - DFS with normal for loop iteration

Use Cases:

• Graph traversal
• Cycle detection
• Topological sorting
• Connected components

Dijkstra's Algorithm

Location: library.cpp

Two implementations for finding shortest paths in weighted graphs:

• Priority queue-based implementation
• Set-based implementation with parent tracking

Use Cases:

• Finding shortest path in weighted graphs with non-negative weights
• Network routing

Floyd-Warshall Algorithm

Location: library.cpp

All-pairs shortest path algorithm.

Use Cases:

• Finding shortest paths between all pairs of vertices
• Transitive closure
• Detecting negative cycles

Bellman-Ford Algorithm

Location: library.cpp

Multiple variants:

• Basic Bellman-Ford for single-source shortest paths
• Path reconstruction variant
• Negative cycle detection variant

Use Cases:

• Shortest paths with negative edge weights
• Detecting negative cycles
• Currency arbitrage detection

Search Algorithms

Binary Search

Location: binary_search/

Two implementations:

• BINARY_SEARCH_recursive - Recursive binary search
• BINARY_SEARCH_iterative - Iterative binary search

Time Complexity: O(log n)

Use Cases:

• Searching in sorted arrays
• Finding boundaries
• Answer optimization problems

Data Structures

Disjoint Set Union (DSU / Union-Find)

Location: DSU/

Efficient implementation with path compression and union by size:

• intial - Initialize the DSU
• lead - Find operation with path compression
• samelead - Check if two elements are in the same set
• mergeg - Union operation with size optimization

Time Complexity: Nearly O(1) amortized per operation

Use Cases:

• Kruskal's MST algorithm
• Dynamic connectivity
• Cycle detection in undirected graphs

Mathematical Algorithms

Location: Math/

A collection of mathematical utilities:

• GCD (Greatest Common Divisor) - Euclidean algorithm
• Prime Checking - Isprime - Efficient primality test
• Sieve of Eratosthenes - Generate all primes up to n
• Power Function - Pow - Fast exponentiation
• Binary Exponentiation - Efficient power computation
• Bit Counting - Count set bits in an integer
• Longest Common Subsequence (LCS) - Dynamic programming solution

Array Techniques

Cumulative Sum 2D

Location: cummulative_sum_2D/

Prefix sum for 2D arrays:

• cumm_sum - Initialize cumulative sum
• calc_cumm_sum_row - Calculate row-wise prefix sums
• calc_cumm_sum_col - Calculate column-wise prefix sums
• range_sum - Query sum of any rectangular subarray in O(1)

Use Cases:

• Range sum queries on 2D arrays
• Image processing
• Dynamic programming optimization

Cumulative Sum 3D

Location: cummulative_sum_3D/

Prefix sum for 3D arrays:

• cumm_sum - Initialize cumulative sum
• calc_cumm_sum_x, calc_cumm_sum_y, calc_cumm_sum_z - Calculate prefix sums along each dimension

Use Cases:

• 3D range queries
• Volume calculations
• Scientific computing

Dynamic Programming

Location: library.cpp and main.cpp

Various DP implementations:

• 0/1 Knapsack - Classic optimization problem
• Longest Common Subsequence (LCS) - String matching
• Grid Path Counting - Count paths in a grid
  • red_to_green_brute_solution - Brute force approach
  • red_to_green_dp_solution - Optimized DP solution

📁 Project Structure

algorithms-and-techniques-in-CPP/
├── BFS/                    # Breadth-First Search implementations
│   ├── BFS.h
│   └── BFS.cpp
├── DFS/                    # Depth-First Search implementations
│   ├── DFS.h
│   └── DFS.cpp
├── DSU/                    # Disjoint Set Union (Union-Find)
│   ├── DSU.h
│   └── DSU.cpp
├── Math/                   # Mathematical algorithms
│   ├── MyMath.h
│   └── MyMath.cpp
├── binary_search/          # Binary search implementations
│   ├── binary_search.h
│   └── binary_search.cpp
├── cummulative_sum_2D/     # 2D prefix sum
│   ├── cum_sum.h
│   └── cum_sum.cpp
├── cummulative_sum_3D/     # 3D prefix sum
│   ├── cum_sum_3D.h
│   └── cum_sum_3D.cpp
├── library.cpp             # Additional algorithm implementations
├── main.cpp                # Main file with examples
└── README.md               # This file

🛠️ Getting Started

Prerequisites

• C++ compiler with C++11 support or higher (g++, clang++)
• (Optional) CMake for building

Building the Project

Using g++

# Compile a specific algorithm
g++ -std=c++11 -o my_program main.cpp BFS/BFS.cpp DFS/DFS.cpp DSU/DSU.cpp Math/MyMath.cpp binary_search/binary_search.cpp cummulative_sum_2D/cum_sum.cpp cummulative_sum_3D/cum_sum_3D.cpp

# Run
./my_program

For Competitive Programming

Most files use #include<bits/stdc++.h> which is a GCC-specific header that includes most standard libraries. This is common in competitive programming for faster coding.

💡 Usage Examples

Example 1: Binary Search

#include "binary_search/binary_search.h"

int main() {
    vector<long long> arr = {1, 3, 5, 7, 9, 11, 13};
    my_binary_search bs;
    
    long long target = 7;
    int low = 0, high = arr.size() - 1;
    
    int result = bs.BINARY_SEARCH_iterative(target, low, high, arr);
    cout << "Element found at index: " << result << endl;
    
    return 0;
}

Example 2: Disjoint Set Union (DSU)

#include "DSU/DSU.h"

int main() {
    DSU dsu;
    int n = 5;
    int parent[10], size[10];
    
    dsu.intial(n, parent, size);
    
    // Merge sets
    dsu.mergeg(1, 2, parent, size);
    dsu.mergeg(3, 4, parent, size);
    
    // Check if elements are in same set
    if (dsu.samelead(1, 2, parent)) {
        cout << "1 and 2 are in the same set" << endl;
    }
    
    return 0;
}

Example 3: BFS Shortest Path

#include "BFS/BFS.h"

int main() {
    int n = 6; // number of nodes
    vector<vector<int>> adj(n);
    
    // Build graph (example: 0-1-2-3-4-5)
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    // ... add more edges
    
    BFS bfs;
    int source = 0, destination = 5;
    vector<bool> visited(n, false);
    
    vector<int> path = bfs.BFSPath(source, destination, adj, n, visited);
    
    cout << "Shortest path: ";
    for (int node : path) {
        cout << node << " ";
    }
    
    return 0;
}

Example 4: 2D Cumulative Sum

#include "cummulative_sum_2D/cum_sum.h"

int main() {
    int n = 4, m = 4;
    vector<vector<int>> grid = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    
    cum_sum_2D cs;
    cs.cumm_sum(n, m, grid);
    
    // Query sum of rectangle from (0,0) to (2,2)
    int i = 0, j = 0, k = 2, l = 2;
    int sum = cs.range_sum(i, j, k, l, grid);
    cout << "Sum of subarray: " << sum << endl;
    
    return 0;
}

Happy Coding! 🚀