SnippetList

From FeitWiki

Here is a list of stuff which might be useful to bring code for. Please just anything you think is useful.

Stuff is graded 1-3, where 1 is often useful, and 3 is seldom useful.

• Graph problems
  • Single-source shortest path
    • Dijkstra with neighbour matrix, O(V²) (1)
    • Dijkstra with heap, O(ElogV) (3)
    • Bellmann-Ford, O(VE), handles negative edges (3)
  • All-pairs shortest path: Floyd-Warshall, O(V³) (1)
  • Flow
    • Maximum flow: Edmonds-Karp, O(VE²) (1)
    • Minimum cost flow: Ford-Fulkerson with Bellmann-Ford or Floyd-Warshall instead of BFS (3)
    • Special code for bipartite matching (edge lists, no super source/sink) (3)
  • Minimum spanning tree
    • Prims with neighbour matrix, O(V²) (1)
    • Prims with heap, O(ElogV) (3)
• Numbers
  • Generating primes (1)
  • GCD and LCM (2)
  • Euler's Phi function (2)
• Geometry
  • Skalar product (2)
  • Vector product (2)
  • Where do two vectors cross (2)
  • 2D convex hull (2)
  • On which side of a vector is a point (3)
• Data structures
  • Union set/find (2)
• Brute force^*
  • Generating all n! permutations (1)
  • Generating all selections k out of n, unordered and ordered (2)
  • Generating all 2ⁿ selections (3)
  • Genarating all matchings (2)

^* For the brute force problems, there are in general two cases: The subproblems are independent, or they are not. When they are independent, you can often use memoisation or DP to speed up the search for the best solution.