==================================================================== 1. FUNDAMENTALS ==================================================================== ==================================================================== 2. SORTING ==================================================================== Three-pivot quicksort [ see http://algs4.cs.princeton.edu/23quicksort/QuickDualPivot.java.html for our dual-pivot ] Timsort Smoothsort (heapsort variant invented by Dijkstra) For a good description, see http://www.keithschwarz.com/smoothsort/ Binary heap (optimized) - replace full exchanges with half exchanges - use shifting instead of integer division? - consider trick of sinking all the way to a leaf (only 1 compare per level down), then swimming up (1 compare per level up). If the key sinks down most of the way (as is likely), this will be an improvement Pairing heap - among fastest in practice [in progress] B-heap - to exploit caching with large priority queues ==================================================================== 3. SEARCHING / SYMBOL TABLES ==================================================================== Splay tree - see http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html - not yet throughly tested Cuckoo hashing (but how to get two hash functions in Java?) Tabulation hashing (but how to get two hash functions in Java?) Universal hashing (but how to get a parameterized hash function in Java?) ==================================================================== 4. GRAPHS ==================================================================== Nonrecursive depth-first search algorithms (to avoid excesive stack sizes) http://algs4.cs.princeton.edu/41undirected/NonrecursiveDFS.java.html http://algs4.cs.princeton.edu/41undirected/BipartiteX.java.html http://algs4.cs.princeton.edu/42digraph/NonrecursiveDirectedDFS.java.html http://algs4.cs.princeton.edu/42digraph/TopologicalX.java.html http://algs4.cs.princeton.edu/42digraph/DirectedCycleX.java.html - cycle (can be done with BFS) - strong components (Kosaraju-Sharir should be easy since second DFS can be replaced by BFS) All cycles in a graph or all directed cycles in a digraph - Paton's algoriths for graphs - Tiernan, Johnson, Tarjan, Szwarcfiter-Lauer - see http://code.google.com/p/niographs/ Planarity testing (and embedding) - very tricky algorithm and code Biconnected components and bridges - design API - see http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html - see http://algs4.cs.princeton.edu/41undirected/Bridge.java.html GraphGenerator - for some families, see http://en.wikipedia.org/wiki/Gallery_of_named_graphs - see also http://algs4.cs.princeton.edu/42directed/DigraphGenerator.java.html ==================================================================== 5. STRINGS ==================================================================== Optimized two-array radix sort - use explicit stack instead of recursion (so that you don't need to save the count[] array in each recursive call and you don't need to reallocate the count[] array but can reset to 0) - See McIlroy-Bostic-McIlroy paper In-place MSD radix sort - http://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html - See McIlroy-Bostic-McIlroy paper Radix trie DAWG - directed acyclic word graph ==================================================================== 6. CONTEXT ==================================================================== Dynamic trees (aka link-cut trees) Faster maxflow Network simplex - for min cost flow or transportation problem - see Algorithms, 3rd edition in Java Weighted bipartite matching - see http://algs4.cs.princeton.edu/65reductions/AssignmentProblem.java.html but modify so that it takes an EdgeWeightedGraph as an argument. - the natural variant will have running time E V log V - return matching as a set of edges (Weighted) nonbipartite matching - quite tricky to implement - see https://github.com/simlu/EdmondsBlossom for an MIT license version Directed Chinese postman problem - A = set of vertices with indegree > outdegree - B = set of vertices with outdegree > indegree - solve transportation problem, where weight of edge from v in A to w in B is length of shortest (fewest number of edges) path and supply/demand = |indegree - outdegree| - add these edges to G - find directed Eulerian cycle in resulting digraph Undirected Chinese postman - let A = set of vertices with odd degree - compute all-pairs shortest path between vertices in A - find min weight perfect matching in A, where weight of edge is length of shortest path (number of edges) between the two vertices - add these edges to G - find Eulerian cycle in resulting graph Delaunay triangulation / Voronoi - tricky to implement in N log N time All simple cycles / paths in a graph/digraph via backtracking Range minimum query (RMQ) / lowest common ancestor (LCA) / Cartesian tree http://courses.csail.mit.edu/6.851/spring12/scribe/L15.pdf [in progress] PADS public domain algorithms (in Python) by David Eppstein http://www.ics.uci.edu/~eppstein/PADS/ [includes implementation of Edmonds nonbipartite matching algorithm]