Algorithms and Data Structures

Sample implementations of useful algorithms and data structures in C++.

Algorithms

> Dynamic Programming

• Change-making problem
• Grid paths extrema
• Kadane's Algorithm (maximum subarray sum)
• Knapsack Problem

Prefix Sum

• Prefix Sum 1D
• Prefix Sum 2D

> Encryption & Compression

• Caesar Cipher
• Huffman Coding

> Geometry

• Convex Hull (using Graham's scan)
• Shoelace Formula (polygon area)

Cross Product

• Clockwise placement of a segment
• Turn direction check

> Graph

• Eulerian Graph determining
• Graph components number counting (using DFS)

> Greedy

• Interval Scheduling Problem

> Math

• Euclidean Algorithm (GCD)
• Extended Euclidean Algorithm (extended GCD)
• Fast Power Modulo (binary exponentiation)
• Linear Diophantine Equation
• Multiplying Matrixes
• Perfect Numbers in range
• Reverse Polish Notation

Fibonacci Numbers

• Fibonacci Numbers (using easy iteration)
• Fibonacci Numbers (using easy recursion)
• Fibonacci Numbers (using fast doubling)
• Fibonacci Numbers (using Matrix)

Numerical analysis

• Newton-Raphson square root finding
• Newton-Raphson nth root finding
• Polynomial Evaluation (using Horner)

Primes

• Easy Primality Test
• Sieve of Eratosthenes

> Searching

• Binsearch
• Bitonic Point
• Interpolation Search
• Lower bound
• Upper bound

> Strings

• Knuth-Morris-Pratt (KMP)
• Longest Common Subsequence (LCS)

Data Structures

• Basic Segment Tree (Sum on interval)
• Find-Union (Disjoint-set)