kaidul/Data_Structure_and_Algorithms_Library

Data Structures and Algorithms for Online Programming Contest

Dynamic Programming

• Coin Change and variants
• Knapsack Problem and variants
• Matrix Chain Multiplication
• Longest Increasing Subsequence( O(n^2) )
• Longest Increasing Subsequence( O(nlogn) )
• Travelling Salesman Problem
• Maximum Sum Subarray( O(n^4) and O(n^3) )
• Kadane Algorithm
• Maximum Sum Subarray using Kadane( O(n^3) )
• Optimal Binary Search Tree
• Subset Sum
• Catalan Number
• DAG Minimum Path
• Minimum Cost Path
• Digit Dp I
• Digit Dp II
• Digit Dp III
• Digit Dp IV

Backtracking

• Permutation Generator
• N-Queen
• Prime Ring

Greedy Algorithm

• Huffman Coding

String Algorithm

• Aho-Corasick Algorithm
• Knuth-Morris-Pratt’s Algorithm
• Rabin Karp Pattern Searching
• Z Algorithm
• Finite Automata Pattern Searching
• Trie (Prefix/Radix Tree)
• Longest Common Subsequence
• Edit Distance
• Longest Palindromic Subsequence
• Suffix Array
• Longest Common Prefix
• Minimum Expression
• Suffix Automata

Graph Theory

• Floyd Warshall’s
• Loop Detection
• Topological Sort
• Bipartite Graph Check
• Strongly Connected Component (Kosaraju)
• Lowest Common Ancestor(sparse table)
• Articulation Point
• Bridge
• Breadth First Search
• Dijkstra
• Bellman Ford's
• Kruskal Minimum Spanning Tree
• Minimum Vertex Cover
• Maximum Flow (Edmonds Karp’s) I
• Maximum Flow (Edmonds Karp’s) II
• Maximum Bipartite Matching
• Stable Marriage Problem
• Heavy Light Decomposition

Mathematics

• Power Function(Big mod)
• Modular Mutiplicative Inverse(using Big mod)
• Prime(Sieve of Erathonesis)
• Segmented Sieve of Erathonesis
• Prime factorization(using Sieve)
• Prime factorization
• Primality Test(School method)
• Miller–Rabin Primality Test
• Euler Totient (Phi Function)
• Extended Euclid
• Linear Diophatine Equation
• Modular Mutiplicative Inverse(using Extended Euclid)
• Matrix Exponentiation
• Floyd Cycle Finding Algorithm
• Big Integer
• Josephus Recurrence
• Fast Fourier Transform

Combinotorics

• Factorial
• nCr
• De-arrangement

Game Theory

• Game Tree(Memorization)
• Nim
• Misère Nim
• Nimble Nim
• Poker Nim
• Prime Power Nim
• Spagrue Grundy Problem
• Grundy Variant: Zero Nim Game
• Grundy Variant: Coins on Chessboard
• Green HackenBush(Colon Principle)

Binary Search

• Binary Search
• Lower Bound
• Upper Bound
• Equal Range

Data Structure

• Singly Linked List
• Doubly Linked List
• Vector
• Stack
• Queue
• List
• Hashtable
• HashMap
• HashSet
• Union Find(Disjoint Set)
• Binary Search Tree
• Segment Tree
• Segment Tree (Lazy Propagation)
• 2D Segment Tree (Quad tree)
• Binary Indexed Tree
• 2D Binary Indexed Tree
• (AVL Tree) Self Balanced BST
• (Splay Tree) Self Balanced BST
• Ternary Search Tree
• Heap (Min)

Computational Geometry

• Computational Geometry Template
• Convex Hull (Jarvis’s Algorithm or Wrapping)
• Convex Hull (Graham Scan)

Hashing

• Double Hashing
• String Hashing by Map
• Berenstain String Hashing
• Rolling Hash

Sorting

• Merge Sort
• Quick Sort
• Heap Sort
• Bubble Sort
• Insertion Sort
• Selection Sort
• Bucket Sort
• Count Sort
• Radix Sort
• Pancake Sort

Miscellaneous

• Template