Competitive Programming

A curated collection of algorithms and data structures implemented in Java. Some of the code is from indy256 and the categorisation is based on Sibyter

Contents

• Backtracking

  • Bron–Kerbosch Algorithm
  • Graph Colouring
  • Maximum Weighted Independent Set - Bitset algorithm
  • Maximum Weighted Independent Set - Alternate implementation

• Combinatorics

  • Enumeration of arrangements
  • Binomial coefficients and factorials
  • Enumeration of combinations
  • Enumeration of combinatorial sequences
  • Enumeration of partitions
  • Enumeration of permutations
  • Random tree and graph generation using Prufer sequence
  • Random permutations arrangements and shuffling
  • Enumeration of set partitions

• Data Compression

  • Arithmetic coding
  • Burrows-Wheeler Transform
  • Lempel–Ziv–Welch Algorithm

• Data Structures

  • Binary heap with increased priority operation
  • Binary heap
  • Binary Search Tree
  • Hashmap with chains
  • Cover Tree
  • Cover Tree Test
  • Disjoint Set data structure
  • Disjoint Set data structure with ranks
  • Doubly Linked List
  • Fenwick Tree 2D for sum
  • Fenwick Tree 3D for sum
  • Fenwick Tree for sum with extended operations
  • Fenwick Tree for sum and maximum
  • Heavy Light improved version
  • Heavy Light decomposition without recursion
  • Heavy Light tree decomposition for vertices or edges
  • KdTree for nearest point query
  • KdTree for rectangular query
  • Lowest Common Ancestor - Schieber and Vishkin algorithm
  • Link Cut Tree - Dynamic tree connectivity
  • Link Cut Tree - dynamic tree with path queries
  • Link Cut Tree - Dynamic tree LCA
  • Mergeable Heap
  • Metric Tree for nearest point query
  • Mo's Algorithm second version
  • Mo's Algorithm for square root decomposition
  • Persistent Tree
  • Quad Tree for rectangular queries on NxM board
  • Queue with minimum query in O(1)
  • Range Minimum Query: Sparse Table
  • RTree for nearest segment query
  • 2D Segment Tree with single element modification
  • Segment Tree second version
  • 3D Segment Tree with single element modification
  • Non Recursive Segment Tree - second version
  • Non Recursive Segment Tree
  • Segment Tree for Add/Max - second version
  • Segment Tree for Add/Max
  • Segment Tree with interval modification
  • Segment Tree - Simple non recursive implementation
  • Segment Tree with sum lower bound operation
  • Treap with explicit keys
  • Treap with implicit keys and interval modification - second version
  • Treap with implicit keys and interval modification

• Depth_First Search

  • Biconnectivity - Bridges, cut points, edge biconnected components, condenstaion tree
  • Non recursive DFS
  • Eulerian Cycle
  • Strongly Connected Components - Kosaraju's Algorithm
  • Strongly Connected Components - Tarjan's Algorithm
  • Tarjan's Algorithm for SCC without recursion
  • Test for all SCC algorithms
  • SCC - Transitive closure algorithm
  • Topological sorting

• Dynamic Programming

  • Convex Hull Optimization
  • Domino Fill
  • Linear Equality - number of solutions
  • Longest Increasing Subsequence
  • Optimal matrix chain multiplication
  • Longest Palindromic Subsequence
  • Shortest Hamiltonian Cycle - second version
  • Shortest Hamiltonian Cycle
  • Shortest Hamiltonian Path
  • String Distances

• Elementary Algorithms

  • Binary Exponentiation
  • Binary Search
  • Ternary Search

• Flows

  • Hungarian algorithm for assignment problem
  • Max Flow - Dinic's algorithm
  • Max Flow - Edmonds Karp algorithm
  • Max Flow - Ford Fulkerson's algorithm
  • Max Flow - Simplified Ford Fulkerson's
  • Max Flow - Push relabel algorithm
  • MaxFlowPreflowN4
  • MaxFlowRetreat
  • Max Flow with min cost - Bellman Ford's algorithm
  • Max Flow with min cost - with potential for dense graphs
  • Min Cost Flow
  • Min Cost Flow Simple

• Geometry

  • General - Angle,area,orientation,sort,rotation,perpendicular
  • Circle Operations
  • Closest Points - in a planar point set using divide and conquer
  • Complex
  • Convex Cut
  • Convex Hull
  • Delaunay triangulation
  • Delaunay triangulation and Voronoi diagram
  • Connected graph using Force-Based method
  • Line Geometry
  • Point Classification
  • Point In Polygon
  • Point Location
  • Point Location Offline
  • Point Location Rtree
  • Point To Segment Distance
  • Polygon and Circle Intersection area
  • Polygons Intersection area
  • Random Polygon using 2-opt
  • Ray Sphere Intersections
  • Rectangle Union area using sweep line
  • Segments and Line Intersection
  • Finding a pair of intersected segments - second version
  • Finding a pair of intersected segments
  • Segments Union length
  • Vector2d class template

• Graphs

  • Centroid Decomposition
  • Graph Coloring Greedy - second version
  • Graph Coloring Greedy
  • Graph class template
  • Tree Centers

• Linear Algebra

  • Determinant - using Gauss and Crout algorithm
  • Determinant - second version
  • Determinant - third version
  • Gaussian elimination algorithm
  • Matrix

• Lowest Common Ancestor

  • LCA
  • LCA: Sparse Table

• Matching

  • Max Matching - second version
  • Max Matching for general graphs - Edmond's Blossom algorithm
  • Max Matching for bipartite graphs - Hopcroft-Karp algorithm
  • Max Matching - Kuhn's algorithm
  • Max Matching for bipartite graphs - randomised algorithm

• Miscellaneous

  • All Nearest Smaller Values - for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value.
  • Array Rotation
  • Contraction Hierarchies
  • Cycle Detection - Floyd's and Brent's algorithm
  • Inversions - number of inversions
  • Karatsuba Multiply
  • Knight Distance - minimum number of moves a knight needs to reach from one square to another on an empty board
  • Longest Increasing Subsequence
  • Maximum Zero Submatrix
  • Monotonic Approximation
  • Generic Pair class template
  • Pair Long class template
  • Rational numbers class
  • Two satisfiability
  • JFrame visualiser view

• Number_Theory

  • Euclid - Euclidean algorithm,GCD,LCM,mod inverse,Chinese remainder theorem
  • Factorisation - Fermat's and Pollard's methods
  • Primes and Divisors - Prime numbers, Sieve of Erasthosenes, Euler's totient function

• Numeric_Methods

  • FFT - Fast Fourier's Transform
  • IFFT - Inverse Fast Fourier's Transform
  • Simpson's Integration

• Optimisation

  • Genetic Algorithm for TSP
  • Hill Climbing
  • Lin Kernighan Heuristic for TSP - second version
  • Lin Kernighan Heuristic for TSP
  • Meet In The Middle
  • Simplex
  • Simulated Annealing

• Shortest_Paths

  • Bellman Ford algorithm - second version
  • Bellman Ford algorithm
  • Dijkstra Custom Heap - Shortest paths. Dijkstra's algorithm with custom binary heap
  • Dijkstra Heap - Shortest paths. Dijkstra's algorithm
  • Dijkstra
  • Dijkstra Segment Tree
  • Floyd's and Warshall's algorithm

• Sorting

  • NthElement - Kth order statistic
  • Array Partition
  • Quicksort
  • Sort - Quicksort, mergesort, heapsort, bubblesort, selection sort, insert sort, count sort and radix sort

• Spanning_Tree

  • Prim Heap
  • Prim's algorithm
  • Steiner Tree

• Strings

  • Aho-Corasick Algorithm
  • Aho-Corasick Algorithm - simple version
  • Calc - Expression parser
  • Expression Parser - Recursive Descent
  • Expression Parser - Shunting-yard algorithm
  • Hashing on Strings
  • Knuth–Morris–Pratt algorithm
  • Lyndon Decomposition - Minimal cyclic shift
  • Recursive Descent Parser
  • Suffix Array - improved version
  • Suffix Array
  • Suffix Automaton
  • Suffix Tree
  • Trie
  • ZFunction