# Complexity and Algorithms - For notes on algorithms in general, see [[algorithm]]. ## [[divide-and-conquer|Divide and Conquer]] - [[recurrence|Recurrence relations]] and their solutions - [[asymptotic-notation|Asymptotic notation]], primarily the $O$-notation. - [[master-theorem|Master Theorem]] - [[fibonacci|Fibonacci sequence]] and generating function method. - Problems - [[binary-multiplication|Binary multiplication]] and [[hypercube|]] - [[strassen|Strassen's matrix multiplication]] ## [[prune-and-search|Prune and Search]] - [[persistent-data-structure|Persistent Data Structure]] - [[selection-problem|Selection problem]], which mimics the ideas in [[quicksort]]. - [[2d-minimal|2D minimal problem]] ## [[computational-geometry|Computational Geometry]] - [[sweeping|Sweeping/sweep line/plane sweep technique]] - [[visibility-problem|Visibility problem]] - [[segment-intersection|Segment intersection]] - [[convex-hull|Convex hull]] - [[triangulation|Triangulation]] - [[linear-programming|Linear programming]] - [[lis|Longest increasing sub-sequence problem]] (equivalent to longest northeast path problem) ## [[dp|Dynamic Programming]] - [[lcs|Longest common sequence problem]] - [[matrix-chain|Matrix chain multiplication]] - [[k-link-shortest-path|k-Link shortest path]] - [[max-independent-set|Maximum independent sets]] - [[bitonic-tsp|Bitonic traveling salesman problem]] ## [[graph|Graph]] - [[dfs|Depth-first search]] - [[biconnected-component|Biconnected component]] - [[topological-sort|Topological sort]] - [[scc|Strongly connected components]] - [[shortest-path|Single source]] and [[all-pair-shortest-path|all-pair]] shortest paths problems. ## Complexity