Adversarial & Game-Tree 3

Alpha-Beta Pruning track alpha (best for MAX) and beta (best for MIN); prune when alpha >= beta

Minimax MAX nodes take the max of children; MIN nodes take the min; values propagate to the root

Monte Carlo Tree Search (MCTS) repeat: Select (UCB1) -> Expand -> Simulate (random rollout) -> Backpropagate wins

Approximate Nearest Neighbour 1

HNSW (Vector / Semantic Search) multi-layer navigable small-world graph; greedy descent layer by layer.

Approximate Nearest Neighbour (ANN) 1

FAISS (IVF + Product Quantization) IVF: assign vectors to nearest centroid; search only the closest few cells. PQ: compress each vector into small codes.

Graph Traversal 3

Bidirectional Search run two BFS frontiers (from start, from goal); stop when they intersect

Breadth-First Search (BFS) queue = [start]; pop front, visit, enqueue unvisited neighbours; repeat

Depth-First Search (DFS) stack = [start]; pop top, visit, push unvisited neighbours; repeat

Hash-Based 3

Bloom Filter set k bits at hash1(x), hash2(x), ... hashk(x); query: all those bits set => maybe, any unset => definitely no

Hash Table Lookup index = hash(key) mod table_size

LSH (Locality-Sensitive Hashing) choose hashes where Pr[h(a)=h(b)] grows with similarity(a,b); group items by bucket

Information Retrieval 3

Inverted Index for each word, store the list of documents containing it; query = intersect those lists

PageRank PR(p) = (1-d)/N + d * sum(PR(q)/outlinks(q)) for all q linking to p

TF-IDF & BM25 (Relevance Ranking) tf-idf = term_frequency * log(N / docs_containing_term); BM25 refines this with saturation + length

Informed & Heuristic 4

A* (A-Star) Search expand the node with smallest f = g (cost so far) + h (estimated cost to goal)

Dijkstra's Algorithm repeatedly pick the unvisited node with the smallest known distance; relax its edges

Greedy Best-First Search expand the node with the smallest h (estimated distance to goal); ignore g

IDA* (Iterative Deepening A*) repeat: depth-first search bounded by f <= threshold; raise threshold to the smallest f that exceeded it

Interval & Divide-and-Conquer 6

Binary Search sort the data; then mid = (low + high) // 2; keep the half that can hold the target.

Exponential Search bound = 1; while arr[bound] < target: bound *= 2; binary_search(arr, bound/2, min(bound,n-1))

Fibonacci Search use consecutive Fibonacci numbers to pick the probe index; no division needed

Interpolation Search pos = lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo])

Jump Search step = floor(sqrt(n)); jump while arr[min(step,n)-1] < target; then scan the block

Ternary Search m1 = lo + (hi-lo)/3; m2 = hi - (hi-lo)/3; compare target with arr[m1], arr[m2]

Linear & Sequential 2

Linear Search for i in 0..n-1: if arr[i] == target: return i

Sentinel Linear Search arr[n] = target; i = 0; while arr[i] != target: i += 1

Probabilistic & Sequence 1

Beam Search at each step, expand all kept sequences, score them, keep the top-k (the beam width)

String & Pattern Matching 5

Aho-Corasick build a trie of all patterns + failure links; scan the text once, following links on mismatch

Boyer-Moore on mismatch, shift the pattern so the text's bad character aligns with its last occurrence in the pattern

Knuth-Morris-Pratt (KMP) build failure[] (longest proper prefix that is also a suffix); on mismatch jump by it

Rabin-Karp hash each text window with a rolling hash; if it equals the pattern hash, verify directly

Suffix Trees & Suffix Arrays sort all suffixes (suffix array); binary-search the sorted suffixes for the pattern

Tree-Based 6

AVL / Red-Black Trees (Self-Balancing) after each insert/delete, rotate subtrees to keep height ~ log n

B-Tree / B+ Tree each node holds up to m-1 keys and m children; one node read narrows to one child

Binary Search Tree (BST) at each node: go left if target < node, right if target > node, stop if equal

LSM Tree (Log-Structured Merge Tree) writes -> in-memory memtable; flush to sorted disk files; reads check memtable then files (newest first)

Skip List start top-left; move right while next <= target, else drop down a level; repeat

Trie (Prefix Tree) follow one edge per character; a word exists if the path ends at a marked node

⌨ Computers

Data Structures and Algorithms (DSA)