Traversal:

BFS (Breadth-First Search): Uses Queue. Finds shortest path in unweighted graphs.
DFS (Depth-First Search): Uses Stack/Recursion. Detects cycles, topological sort.

Topological Sort: Linear ordering of vertices for DAGs (Directed Acyclic Graphs). (Kahn's algorithm, DFS-based).

Connected Components: Set of nodes where any two nodes are connected.

Strongly Connected Components (SCC): For directed graphs (Kosaraju's, Tarjan's).

Comparison Sorts:
- Bubble Sort: $O(n^2)$ worst, $O(n^2)$ avg.
- Selection Sort: $O(n^2)$ worst, $O(n^2)$ avg.
- Insertion Sort: $O(n^2)$ worst, $O(n)$ best. Good for nearly sorted.
- Merge Sort: $O(n \log n)$ worst, $O(n \log n)$ avg. Stable. $O(n)$ space. Divide & Conquer.
- Quick Sort: $O(n^2)$ worst, $O(n \log n)$ avg. In-place (avg). Divide & Conquer.
- Heap Sort: $O(n \log n)$ worst, $O(n \log n)$ avg. In-place.
Non-Comparison Sorts:
- Counting Sort: $O(n+k)$ for integers in range $[0, k]$. Stable.
- Radix Sort: $O(nk)$ for $n$ numbers with $k$ digits. Stable.
- Bucket Sort: $O(n^2)$ worst, $O(n+k)$ avg. (depends on distribution).

Linear Search: $O(n)$ worst.
Binary Search: $O(\log n)$ on sorted arrays.
Ternary Search: $O(\log_3 n)$ for unimodal functions.
Hashing: $O(1)$ average for search/insert/delete using hash tables. Worst case $O(n)$ (collisions).

Shortest Path:
- Dijkstra's Algorithm: Single source, non-negative weights. $O(E \log V)$ with min-priority queue.
- Bellman-Ford Algorithm: Single source, handles negative weights. Detects negative cycles. $O(VE)$.
- Floyd-Warshall Algorithm: All-pairs shortest path. $O(V^3)$.
Minimum Spanning Tree (MST):
- Prim's Algorithm: $O(E \log V)$ with min-priority queue.
- Kruskal's Algorithm: $O(E \log E)$ with Disjoint Set Union.
Cycle Detection: DFS for directed/undirected. BFS for undirected.
Bipartite Check: BFS/DFS with 2-coloring.
Flow Networks: Ford-Fulkerson, Edmonds-Karp.

Recursion: Function calls itself. Base case and recursive step.
- Tail Recursion: Optimization possible.
Backtracking: Explores all potential solutions. If a path doesn't work, backtrack.
- Examples: N-Queens, Sudoku Solver, Permutations, Combinations, Subset Sum.
Master Theorem: Solves recurrences of form $T(n) = aT(n/b) + f(n)$.

Principle: Overlapping subproblems and Optimal substructure.
Techniques:
- Memoization (Top-down): Store results of expensive function calls.
- Tabulation (Bottom-up): Fill a table iteratively.
Examples: Fibonacci, Longest Common Subsequence (LCS), Knapsack Problem, Coin Change, Edit Distance.