Problems Base course RU

Built on

graph

Articles

DS Data structure Cuckoo hashing Two nests per key, a lookup in at most two probes; insertion evicts tenants. Works up to a load of 1/2, with buckets up to 98 %. lookup at most d probes in the worst case; insertion O(1) on average below the threshold 1 problem GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.

neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists

2 problems GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem GRA Algorithm Dinic's algorithm Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks. O(V² E) 2 problems GRA Algorithm Graph colouring Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables. O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 problems GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem PAR Technique Branch and bound 38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242. exponential in the worst case 1 problem NUM Algorithm Chinese remainder theorem A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes. O(k²) operations on machine numbers 2 problems NUM Algorithm Gaussian elimination A linear system by elimination: the pivot, LU, conditioning, sparse matrices and fill-in. O(n³): about n³/3 multiplications for the forward pass 2 problems

Problems

Is there such a street piece A domino mosaic An import cycle Carroll's doublets Night closures Routes with no step back The resistance of a circuit A crossing under repair A profitable round of exchanges A ring from its pieces All the spanning trees An avalanche of retries Calls and repairers Changes of plane Channels without interference Cuckoo nests Frequencies for the towers Street closures The forgotten code Town codes Triangles of imports A described relative A table between stations Direct flights Exam days Flood watch Shortest itineraries with no change in common The snowplough

Often together

classic 16 interviews 10 maps and navigation 9 contests 8 shortest path 7 weighted graph 6 networks 5 matrix 4 traversal 4 heap 4 heuristic 4 connectivity 3