Algorithm Design Patterns and Anti-Patterns Algorithm design patterns. Ex. Greedy. O(n log n)interval scheduling. Divide-and-conquer. O(n log n)FFT. Dynamic programming. O(n2)edit distance. Duality. O(n3)bipartite matching. Reductions. Algorithm design anti-patterns. NP-completeness. O(nc)algorithm unlikely. PSPACE-completeness. O(nc)certification algorithm unlikely. Undecidability. No algorithm possible. 32 Algorithm Design Patterns and Anti-Patterns Algorithm design patterns. Ex.  Greedy. O(n log n) interval scheduling.  Divide-and-conquer. O(n log n) FFT.  Dynamic programming. O(n2) edit distance.  Duality. O(n3) bipartite matching.  Reductions. Algorithm design anti-patterns.  NP-completeness. O(nc ) algorithm unlikely.  PSPACE-completeness. O(nc ) certification algorithm unlikely.  Undecidability. No algorithm possible