Algorithmic strategies
Math Algorithms
Graph Algorithms
 BFS – DFS traversals
 Topological sort
 Euler path/cycle
 Shortestpath algorithms (Dijkstra, BellmanFord, FloydWarshall)
 Minimum spanning tree (Prim, Kruskal algorithms)
 Finding connected components and transitive closures
 Strongly connected components, bridges and articulation points
 O(V E) time algorithm for computing maximum bipartite matching
 Ford Fulkerson's/Edmonds Karp's (Max Flow, Min Cut)
 Counting paths in DAG
DP Algorithms
 Max Sum 1D/2D
 Kadane's Algorithm
 Longest Increasing Subsequence (LIS)
 Longest Common Subsequence (LCS)
 Knapsack/Subset Sum
 Memoization
 DP with DAG
 DP on Tree
 DP Optimization Techniques
Data Structures
 Binary heap data structures
 Representation of disjoint sets: the UnionFind data structure
 Binary index trees and Segment trees
 Balanced binary search trees
 Augmented binary search trees
 Lowest common ancestor
 Creating persistent data structures by path copying or using fat nodes
 Composition of data structures (2D statically balanced binary trees)
 Heavylight decomposition and separator structures for static trees
 Data structures for dynamically changing trees and their use in graph algorithms
String Algorithms
 KnuthMorrisPratt (KMP)
 RabinKarp hashing
 Suffix arrays/tree
 Suffix automaton
 AhoCorasick
Computational Geometry
 Geometry Basics (area, perimeter, Euclidean distance, Trigonometry)
 Line Segment Intersection
 Testing if a Polygon is Convex
 Testing if a Point is Inside a Polygon
 Cutting a (Convex) Polygon with a Straight Line
 Graham Scan (Convex Hull)
 Triangulation

