Complexity and Algorithms

• For notes on algorithms in general, see algorithm.

Divide and Conquer

• Recurrence relations and their solutions
  • Asymptotic notation, primarily the $O$-notation.
  • Master Theorem
  • Fibonacci sequence and generating function method.
• Problems
  • Binary multiplication and
  • Strassen’s matrix multiplication

Prune and Search

• Persistent Data Structure
• Selection problem, which mimics the ideas in quicksort.
• 2D minimal problem

Computational Geometry

• plane sweep technique
• Visibility problem
• Segment intersection
• Convex hull
• Triangulation
• Linear programming
• Longest increasing sub-sequence problem (equivalent to longest northeast path problem)

Dynamic Programming

• Longest common sequence problem
• Matrix chain multiplication
• k-Link shortest path
• Maximum independent sets
• Bitonic traveling salesman problem

Graph

• Depth-first search
• Biconnected component
• Topological sort
• Strongly connected components
• Single source and all-pair shortest paths problems.

Complexity