We will perform the same operations as when solving the system or finding its determinant. You can search for the rank using Gaussian elimination. Generally, the rank of a matrix does not exceed \(\min (N, M)\). Note that if the matrix is square and its determinant is non-zero, then the rank is \(N\) ( \(=M\)) otherwise it will be less. Let the matrix be rectangular and have size \(N \times M\). The rank of a matrix can also be defined as the largest order of any non-zero minor in the matrix. The rank is not only defined for square matrices. The rank of a matrix is the largest number of linearly independent rows/columns of the matrix. The Stern-Brocot Tree and Farey Sequences Optimal schedule of jobs given their deadlines and durationsġ5 Puzzle Game: Existence Of The Solution MEX task (Minimal Excluded element in an array) Search the subsegment with the maximum/minimum sum RMQ task (Range Minimum Query - the smallest element in an interval)
Kuhn's Algorithm - Maximum Bipartite Matching Maximum flow - Push-relabel algorithm improved Maximum flow - Ford-Fulkerson and Edmonds-Karp Lowest Common Ancestor - Tarjan's off-line algorithm Lowest Common Ancestor - Farach-Colton and Bender algorithm Second best Minimum Spanning Tree - Using Kruskal and Lowest Common AncestorĬhecking a graph for acyclicity and finding a cycle in O(M) Minimum Spanning Tree - Kruskal with Disjoint Set Union Number of paths of fixed length / Shortest paths of fixed length Strongly Connected Components and Condensation Graphĭijkstra - finding shortest paths from given vertexīellman-Ford - finding shortest paths with negative weightsįloyd-Warshall - finding all shortest paths Half-plane intersection - S&I Algorithm in O(N log N)Ĭonnected components, bridges, articulations points Search for a pair of intersecting segmentsĭelaunay triangulation and Voronoi diagram Pick's Theorem - area of lattice polygons Manacher's Algorithm - Finding all sub-palindromes in O(N)īurnside's lemma / Pólya enumeration theoremįinding the equation of a line for a segmentĬheck if points belong to the convex polygon in O(log N) Euclidean algorithm for computing the greatest common divisorĭeleting from a data structure in O(T(n) log n)ĭynamic Programming on Broken Profile.
0 kommentar(er)
