Memory tricks that make search, optimization and classic AI click

BFS (queue, level-by-level): complete and optimal for unweighted graphs. DFS (stack, goes deep first): memory efficient but not optimal. Uniform Cost Search: optimal for weighted graphs. A* Search: f(n) = g(n) + h(n). g(n) = actual cost from start. h(n) = heuristic estimate to goal. Optimal if heuristic is admissible (never overestimates). Used in GPS navigation and game pathfinding.

Minimax for two-player zero-sum games (chess, tic-tac-toe). MAX player (you) chooses action maximizing score. MIN player (opponent) minimizes your score. Alternate MAX and MIN levels. Alpha-Beta Pruning: prune branches where alpha is >= beta -- same result, dramatically fewer nodes. Reduces from O(b^d) to O(b^(d/2)) in best case. AlphaZero: minimax plus deep learning plus self-play -- beat world champions.

Variables (cells, regions), Domains (digits 1-9, colors), Constraints (no repeats, adjacent regions differ). Backtracking: assign one variable at a time, backtrack when constraint violated. MRV (Minimum Remaining Values): assign most constrained variable first. AC-3 Arc Consistency: preprocessing that removes domain values with no compatible assignment.

Population: candidate solutions. Fitness function: evaluate solution quality. Selection: fitter solutions more likely to reproduce. Crossover: combine two parents to produce offspring. Mutation: randomly alter part of a solution -- maintains diversity, avoids local optima. Repeat for many generations. Used when search space is huge or gradient is unavailable.

Directed Acyclic Graph (DAG). Nodes = random variables. Edges = direct probabilistic influence (X to Y means X directly influences Y). Each node stores a Conditional Probability Table (CPT) given its parents. Applications: medical diagnosis, spam filtering, fault diagnosis. Inference: given evidence, compute probability of query variable. Inference is NP-hard in general.

Batch GD: gradient on entire dataset -- stable, slow. SGD: gradient on one example -- fast, very noisy. Mini-batch (32-256 samples): standard in deep learning -- best of both worlds. Adam: adaptive per-parameter learning rate -- most popular optimizer, works with defaults (lr=0.001). Momentum: adds inertia, avoids oscillation, escapes saddle points.

Bagging: parallel independent models on random subsets, average predictions -- reduces variance. Random Forest = bagging of decision trees. Boosting: sequential, each model corrects previous errors -- reduces bias. XGBoost and LightGBM = gradient boosting. Stacking: meta-model learns to combine base model outputs. No Free Lunch: try ensembles before complex single models.

PCA finds orthogonal directions (principal components) of maximum variance. PC1: greatest variance direction. Project data onto top k components. Scree plot: variance explained vs k -- choose where curve elbows (~95% variance kept). Always standardize first. t-SNE and UMAP: nonlinear alternatives for visualization only.

Run many random simulations, average results -- converges to true value as samples increase. Monte Carlo Tree Search (MCTS): simulate random game playouts from each position to guide search -- used in AlphaGo. MCMC (Markov Chain Monte Carlo): sample from complex probability distributions -- used in Bayesian inference.

Support: how often do X and Y appear together? Confidence (A to B): P(B given A). Lift: is the relationship stronger than chance? Lift greater than 1 = positive association beyond chance. Apriori: uses anti-monotonicity to prune itemset search efficiently. Applications: recommendations, fraud detection, drug interactions.

DP solves complex problems by breaking into overlapping subproblems, solving each once, storing results (memoization). Two conditions: optimal substructure and overlapping subproblems. Top-down (memoization): recursive with caching. Bottom-up (tabulation): iterative. Viterbi algorithm: DP for finding most likely sequence in a Hidden Markov Model -- used in speech recognition and POS tagging.

K-NN is beautifully simple: to classify a new point, find the K training examples closest to it (by distance) and let them vote. Majority wins. K=1 means one nearest neighbor decides. K=5 means the 5 closest points vote. Large K = smoother boundary (less overfit). Small K = jagged boundary (more overfit). No training phase — just store all data and compute distances at prediction time. Lazy learning at its finest.

SVM finds the boundary line (hyperplane) that separates two classes with the maximum margin — the widest possible street between the two neighborhoods. The data points closest to the boundary are called support vectors (the houses on the edge of the street). Wider street = more confident separation = better generalization. The kernel trick lets SVM handle data that can't be separated by a straight line by projecting it into higher dimensions.

The output type determines which algorithm you need. Classification: output is a discrete category — spam/not spam, cat/dog, disease/healthy. Regression: output is a continuous number — house price, temperature tomorrow, patient age. Same input data, completely different question. Logistic regression (confusingly named) is a classifier. Linear regression predicts numbers. Always ask: am I predicting a category or a value?

A decision tree asks a series of yes/no questions about features, splitting the data at each step. Each split is chosen to maximize information gain — making the resulting groups as pure as possible. Terminal nodes (leaves) contain the final prediction. It's exactly like 20 Questions: "Is it alive? Does it have legs? Does it bark?" The tree stops when leaves are pure or a depth limit is reached. Interpretable but prone to overfitting without pruning.

K-means finds K clusters in unlabeled data: Step 1 — randomly place K centroids. Step 2 — assign every point to its nearest centroid. Step 3 — move each centroid to the average position of its assigned points. Repeat steps 2–3 until centroids stop moving. The algorithm converges to stable clusters. You must choose K in advance (a weakness). Great for customer segmentation, document grouping, and image compression.

Before choosing any algorithm, identify the task type. Classification: predict a discrete category (spam/not spam). Regression: predict a continuous number (house price). Clustering: group unlabeled data by similarity (K-means). Dimensionality Reduction: compress features while keeping structure (PCA). Getting this wrong means applying the wrong family of algorithms entirely. Always ask: What type of output do I need?

PCA finds the directions (principal components) along which the data varies the most, then projects the data onto those axes. PC1 captures the most variance, PC2 the next most (perpendicular to PC1), and so on. You then keep only the top K components, discarding the rest. Use case: 500 features → 10 principal components that capture 95% of variance. Speeds up training, reduces overfitting, enables visualization in 2D/3D.

K-means assumes clusters are roughly spherical and requires you to specify K upfront. DBSCAN (Density-Based Spatial Clustering) finds clusters of any shape — it groups points that are densely packed and labels sparse outliers as noise. No need to specify K. Perfect for: geographic data (cities form irregular shapes), anomaly detection (outliers labeled automatically), real-world messy clusters. Weakness: sensitive to the epsilon (neighborhood radius) hyperparameter.

Naive Bayes classifies by applying Bayes theorem, assuming all features are conditionally independent given the class. This assumption is almost never true — hence "naive." Yet it works remarkably well for text classification (spam filtering, sentiment analysis) because word frequencies are approximately independent. Training is instant — just count frequencies. Prediction is a few multiplications. Accuracy often rivals far more complex models on text data. Always try it as a baseline.