Graph

Accessible graph list

• Graph Basics - draft

  contrasts: Deterministic Finite Automata. Both use circles and arrows, but graph basics models relationships among objects while a DFA diagram models finite memory states and labeled input transitions.

  prerequisite: Breadth-First Search. BFS repeatedly asks for each node's immediate neighbors, so it depends on nodes, edges, and adjacency.

• Breadth-First Search - draft

  generalizes: Dijkstra's Algorithm. Dijkstra keeps BFS's frontier-and-distance idea, but chooses the next node by smallest tentative total cost instead of FIFO queue order.

• Dijkstra's Algorithm - draft
• Closest Pair D&C - draft

  contrasts: Graham Scan. Both are geometric algorithms, but closest pair uses divide and conquer while Graham Scan uses ordering plus a stack invariant.

  contrasts: Bentley-Ottmann Sweep Line. Both avoid naive pair checking in geometry, but closest pair uses recursive spatial filtering while Bentley-Ottmann uses a dynamic sweep line.

• Graham Scan - draft

  motivates: Bentley-Ottmann Sweep Line. Graham Scan introduces geometric ordering and local turn tests; Bentley-Ottmann extends that idea to an order maintained by changing events.

• Bentley-Ottmann Sweep Line - draft
• P vs NP - draft

  prerequisite: Polynomial-Time Reductions. Reductions compare decision problems using polynomial time, so learners first need the P vs NP vocabulary of decision problems and polynomial-time algorithms.

  uses: Circuit-SAT. Circuit-SAT uses the P vs NP idea that a proposed assignment can serve as a polynomial-time checkable certificate.

• Polynomial-Time Reductions - draft

  prerequisite: NP-Hardness. NP-hardness is defined by polynomial-time reductions from every NP problem to a target.

  prerequisite: Circuit-SAT to SAT. This reduction is the first concrete SAT-facing use of polynomial-time reductions.

• NP-Hardness - draft

  prerequisite: Circuit-SAT. Circuit-SAT is the first concrete source problem after the general NP-hardness definition.

• Circuit-SAT - draft

  prerequisite: Circuit-SAT to SAT. The reduction starts from a concrete circuit-SAT source instance and emits a SAT formula.

  motivates: Boolean Satisfiability (SAT). SAT asks the same search-for-an-assignment question as Circuit-SAT, but the object is a Boolean formula instead of a gate circuit.

• Circuit-SAT to SAT - draft
• Boolean Satisfiability (SAT) - draft

  prerequisite: Circuit-SAT to SAT. The target language and satisfiability structure are fixed by SAT before introducing this concrete reduction.

• Confusion Matrix - draft

  uses: Precision. Precision uses the predicted-positive part of the confusion matrix to ask how many positive predictions were correct.

  uses: Recall. Recall uses the actual-positive row of the confusion matrix to ask how many real positives were found.

  uses: Rand Index. Rand Index reuses the confusion-matrix idea, but the counted objects are item pairs instead of individual classifier examples.

• Precision - draft

  contrasts: Recall. Precision judges positive predictions, while recall judges real positives covered.

  uses: F1 Score. F1 uses precision as one input in its harmonic balance formula.

• Recall - draft

  uses: F1 Score. F1 uses recall as the other input in its harmonic balance formula.

• F1 Score - draft
• Purity - draft

  contrasts: Rand Index. Purity scores each cluster by a majority reference label, while Rand Index checks pairwise together/apart decisions.

• Rand Index - draft

  generalizes: Adjusted Rand Index. Adjusted Rand Index keeps Rand-style pair agreement, then subtracts the agreement expected from the cluster and class margins.

  contrasts: Fowlkes-Mallows Index. Both use clustering pair counts, but Fowlkes-Mallows ignores true negatives and balances pair precision with pair recall.

• Adjusted Rand Index - draft

  contrasts: Fowlkes-Mallows Index. ARI adjusts for chance agreement from margins, while FMI focuses on positive co-clustering decisions without chance adjustment.

• Fowlkes-Mallows Index - draft

  contrasts: Silhouette Score. Fowlkes-Mallows is external because it needs reference labels; Silhouette is internal because it judges distances and cluster assignments only.

• Silhouette Score - draft

  contrasts: Calinski-Harabasz Index. Silhouette compares each point with its nearest rival cluster, while Calinski-Harabasz summarizes centroid scatter globally.

  motivates: Davies-Bouldin Index. After seeing cohesion versus separation point by point, Davies-Bouldin asks the same kind of question at the cluster-centroid level.

  motivates: Dunn Index. Silhouette averages point-level contrast; Dunn turns the same separation idea into an extreme-gap test.

  applied-in: K-Means Clustering. Internal metrics such as silhouette are often used after K-Means proposes a hard clustering.

• Calinski-Harabasz Index - draft

  contrasts: Davies-Bouldin Index. CH is a higher-better global scatter ratio, while DB is a lower-better average of each cluster's worst rival.

  contrasts: Dunn Index. CH uses squared centroid scatter; Dunn uses pairwise distance extremes and is more sensitive to bridge points or outliers.

• Davies-Bouldin Index - draft

  contrasts: Dunn Index. DB averages worst centroid similarities, while Dunn uses the single closest cross-cluster gap and widest within-cluster diameter.

• Dunn Index - draft
• K-Means Clustering - draft

  contrasts: K-Medoids Clustering. K-Means uses averaged centroids; K-Medoids repairs that assumption by requiring centers to be actual data points.

  contrasts: DBSCAN. K-Means searches for center-shaped partitions, while DBSCAN grows connected dense regions and can mark noise.

  generalizes: EM for GMM. EM for GMM keeps the alternating update flavor of K-Means but replaces hard nearest-centroid assignment with probabilistic responsibilities.

• K-Medoids Clustering - draft
• DBSCAN - draft

  generalizes: OPTICS. OPTICS keeps DBSCAN's density-reachability idea but records an ordering across distance scales instead of committing to one epsilon.

  generalizes: HDBSCAN. HDBSCAN extends density clustering by selecting stable branches from a hierarchy rather than one fixed density cut.

• OPTICS - draft

  motivates: HDBSCAN. OPTICS exposes multi-scale density structure; HDBSCAN turns a related hierarchy into selected stable clusters.

• HDBSCAN - draft
• EM for GMM - draft
• Feature Map - draft

  motivates: Kernel Function. Kernels answer the mapped-inner-product question that feature maps make concrete.

  uses: Polynomial Kernel. Polynomial kernels are easiest to understand by first seeing explicit polynomial feature maps.

  motivates: Principal Component Analysis. Feature maps show that a representation can rewrite inputs; PCA learns a linear representation from the data itself.

• Kernel Function - draft

  prerequisite: Linear Kernel. The linear kernel is the simplest named example after the general kernel definition.

  prerequisite: RBF Kernel. RBF is a named kernel whose similarity comes from distance decay rather than raw dot-product alignment.

  prerequisite: Sigmoid Kernel. The sigmoid kernel needs the general kernel-validity idea because it is not valid for every parameter setting.

• Linear Kernel - draft

  generalizes: Polynomial Kernel. The polynomial kernel starts from the linear dot product and adds powers and interaction features.

  contrasts: RBF Kernel. Linear similarity rewards origin-based alignment; RBF similarity rewards local nearness.

  uses: Sigmoid Kernel. The sigmoid kernel squashes an affine transformation of the same dot product used by the linear kernel.

• Polynomial Kernel - draft

  contrasts: RBF Kernel. Polynomial kernels add finite-degree interactions, while RBF behaves like a much richer local feature space.

• RBF Kernel - draft
• Sigmoid Kernel - draft
• Principal Component Analysis - draft

  contrasts: Multidimensional Scaling. PCA preserves coordinate variance after rotation, while MDS starts from pairwise distances and tries to preserve those distances.

  contrasts: Linear Discriminant Analysis. PCA ignores labels and keeps high-variance directions; LDA uses labels to keep directions that separate classes.

• Multidimensional Scaling - draft

  generalizes: Isomap. Isomap keeps MDS's distance-table layout step but replaces raw distances with neighbor-graph shortest-path distances.

• Isomap - draft

  contrasts: Stochastic Neighbor Embedding. Isomap preserves graph geodesic distances, while SNE preserves local neighbor probabilities.

  contrasts: UMAP. Both build neighbor graphs, but Isomap uses shortest-path distances while UMAP matches fuzzy local memberships.

• Linear Discriminant Analysis - draft

  generalizes: Quadratic Discriminant Analysis. QDA relaxes LDA's shared-covariance assumption by letting each class keep its own covariance shape.

• Quadratic Discriminant Analysis - draft

  contrasts: Stochastic Neighbor Embedding. QDA is supervised classification geometry; SNE returns to unsupervised local-neighborhood visualization.

• Stochastic Neighbor Embedding - draft

  generalizes: t-SNE. t-SNE keeps SNE's neighbor-probability matching and repairs crowding with a heavy-tailed low-dimensional similarity.

• t-SNE - draft

  contrasts: UMAP. Both are local-neighbor embeddings for visualization, but UMAP frames the problem as fuzzy graph matching with attraction and repulsion.

• UMAP - draft
• B-Tree - draft

  motivates: B+-Tree. B+-trees keep B-tree's shallow page-based search shape, then move records to linked leaves to make range scans efficient.

• B+-Tree - draft
• Deterministic Finite Automata - draft

  prerequisite: Nondeterministic Finite Automata. NFA is easiest to learn after DFA: a DFA keeps one current state, while an NFA generalizes the transition idea to a set of possible current states.

• Nondeterministic Finite Automata - draft