ACM-ICPC Algorithms and Data Structures List Competitive programming

List of basic algorithms and data structures for algorithmic programming competitions (International Olympiad in Informatics (IOI), ACM International Collegiate Programming Competition (ICPC), Google Code Jam, Facebook Hacker Cup, etc.).

In the past, this list has been quite useful for solving algorithmic programming challenges on online judges like the Sphere Online Judge (SPOJ) and competitions.

Most of this has been coded during high-school (2008-2010) while preparing for the IOI. Consider this a disclaimer about the coding style. I will try to improve the code whenever I have some free time. Bullet-points that are not highlighted below have not been added yet.

If you see any errors or would like to make some improvements, please feel free to set an issue, or even better, make a pull request.

The code is licensed under the MIT License, free to use, have fun!



Algebra:

• Bignum (addition, subtraction, multiplication, division)
• Prime Factorization O(sqrt(n))
• Prime Number Generator (Sieve of Eratosthenes)
• GCD (Greatest Common Divisor)
• LCD (Lowest Common Multiple)
• Linear Congruence (Extended GCD)
• Miller-Rabin Primality Test

Combinatorics:

• All Permutation
• All Subsets
• Next Permutation (alphabetically higher)

Graph Theory:

• DFS (Depth-First Search)
• BFS (Breadth-First Search)
• Connected Components
• Dijkstra's Algorithm (One Way Shortest Path)
• Prim's Algorithm (Minimum Spanning Tree)
• Kruskal's Algorithm (Minimum Spanning Tree)
• Floyd-Warshall (All Way Shortest Path)
• Toposort (Topological Sort)
• ArticFind (Find all Articulation Points), O(E)
• Ford-Fulkerson's Algorithm with Capacity Scaling (Maxflow/Mincut)
• Dinic's Algorithm (Maxflow/Mincut)
• Edmonds-Karp's Algorithm (Maxflow/Mincut)
• Hierholzer's Algorithm (Euler Cycle detection)
• Bellman-Ford (for negative weights)
• Bipartite Matching

Greedy Algorithm:

• Activity selection/Task scheduling problem
• Huffman coding
• Knapsack problem

Computational Geometry:

• Graham's Scan Algorithm (Convex Hull)
• Closest Pair of Points (Sweep Line)
• Line-Line Intersection
• Segment-Segment Intersection
• Area of Polygon
• Line-Point Distance
• Point-Segment Distance
• Circle from Three Points
• Reflection
• Rotation
• Area of a Triangle (three points)
• Bentley-Ottman's Algorithm (Sweep Line, finding all intersections of multiple line segments)
• Shamos-Hoey Algorithm (checking if there is an intersection given multiple line segments)
• Crossing Number (resp. Winding Number, the method to check whether a point is inside a simple polygon (resp. non-simple polygon))

Data Structures:

• Queue
• Stack
• Singly Linked List
• Binary Indexed Tree (BIT)
• 2D Binary Indexed Tree (2D BIT)
• Binary Search Tree (BST)
• Priority-Queue
• Heap
• Segment Tree
• Dictionary (STL Map)
• Set (STL Set)
• Suffix Array (resp. Suffix Sorting, determine if string is a subseq. of another string)
• Union-Find (Disjoint-Set Data Structure)
• Doubly Linked List
• STL Vector
• Trie
• Hash Table
• Suffix Tree

Dynamic Programming:

A selection of solutions to fairly standard DP problems.

• Edit Distance
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS), O(nlogn)
• Matrix Chain Multiplication (MCM)
• Maximum Empty Rectangle (MER)
• Range Minimum Query, Sparse Table (RMQ)
• Stable Marriage Problem
• Binomial Coefficient Solver

String Manipulation:

• String Handling (in general)
• Knuth Morris Pratt (String Search)

Sorting:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort
• Heap Sort

Searching:

• Linear Search
• Binary Search
• Ternary Search