Examples: Traveling Salesperson Problem (TSP), Knapsack Problem.

V. Graph Algorithms

Graph Representations:
- Adjacency List: $O(V+E)$ space. Good for sparse graphs.
- Adjacency Matrix: $O(V^2)$ space. Good for dense graphs.
Breadth-First Search (BFS):
- Explores layer by layer. $O(V+E)$.
- Finds shortest paths in unweighted graphs. Uses a queue.
Depth-First Search (DFS):
- Explores as far as possible along each branch before backtracking. $O(V+E)$.
- Used for finding connected components, topological sort, strongly connected components. Uses a stack or recursion.
Topological Sort: Linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $u \to v$, $u$ comes before $v$ in the ordering. $O(V+E)$.
Minimum Spanning Trees (MST):
- Kruskal's Algorithm: $O(E \log E)$ or $O(E \log V)$. Sort edges by weight, use Union-Find to add edges if they don't form a cycle.
- Prim's Algorithm: $O(E \log V)$ (binary heap) or $O(E + V \log V)$ (Fibonacci heap). Grows a single MST from a starting vertex.
Single-Source Shortest Paths:
- Bellman-Ford Algorithm: $O(VE)$. Handles negative edge weights, detects negative cycles.
- Dijkstra's Algorithm: $O(E \log V)$ (binary heap) or $O(E + V \log V)$ (Fibonacci heap). Does NOT handle negative edge weights.
All-Pairs Shortest Paths:
- Floyd-Warshall Algorithm: $O(V^3)$. Dynamic programming approach. Handles negative edge weights, detects negative cycles.
- Johnson's Algorithm: $O(VE + V^2 \log V)$. Reweights edges to be non-negative, then runs Dijkstra from each vertex. Good for sparse graphs.
Maximum Flow:
- Ford-Fulkerson Method: Repeatedly finds augmenting paths in the residual graph and pushes flow. $O(E \cdot f^*)$ where $f^*$ is max flow.
- Edmonds-Karp Algorithm: Ford-Fulkerson with BFS to find augmenting paths. $O(VE^2)$.

VI. Advanced Topics

String Matching:
- Naive Algorithm: $O((n-m+1)m)$. Simple, but can be slow.
- Rabin-Karp Algorithm: $O(nm)$ worst case, $O(n+m)$ average case. Uses hashing to quickly check for matches.
- Knuth-Morris-Pratt (KMP) Algorithm: $O(n+m)$. Uses a precomputed "prefix function" (LPS array) to avoid redundant comparisons when a mismatch occurs.
Computational Geometry:
- Algorithms for geometric problems (e.g., convex hull, closest pair of points, line segment intersection).
- Convex Hull: Smallest convex polygon enclosing a set of points. Algorithms like Graham scan ($O(n \log n)$) or Jarvis march ($O(nh)$).
Number Theoretic Algorithms:
- Greatest Common Divisor (GCD): Euclidean Algorithm $O(\log n)$.
- Modular Arithmetic: Operations on integers modulo $n$.
- Primality Testing: Miller-Rabin (probabilistic), AKS (deterministic polynomial time).
P and NP Complexity Classes:
- P (Polynomial time): Problems solvable in polynomial time.
- NP (Nondeterministic Polynomial time): Problems whose solutions can be *verified* in polynomial ti