Problems Base course RU

Built on

matrix

Articles

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 Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Hungarian algorithm Which job for whom at the least total cost: potentials, tight pairs and augmenting paths in O(n³). O(n³) 2 problems STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems DP Technique Interval DP The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing. O(n³) 2 problems 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 TEC Technique Cache-friendly data The same algorithm, a different order of memory accesses: tiling, padded rows and laying data out by field. the same big O 1 problem

Problems

Airports opening Dark islands Fibonacci modulo m Sequencer errors The resistance of a circuit A floor with a pillar All the derivatives of a network All the spanning trees Cache misses Couriers and orders Lights out The shortest loop

Often together

classic 7 graph 4 maps and navigation 3 interviews 3 dynamic programming 3 in production 3 linear algebra 3 array 2 cache-friendly 2 weighted graph 2 contests 2 optimization 2