====================================================================
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 running time E V log V
- return matching as a set of edges
(Weighted) nonbipartite matching
- quite tricky to implement
Global mincut for undirected graphs
- Stoer-Wagner O(EV + V^2 log V) with an index priority queue
(use union-find to simplify dealing with contracting edges)
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/loomis-scribe.ps
[ simple and probably faster in practice than Karger's randomized algorithm ]
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]