Stationary distributions

Property-preserving lossy compression

Nearest Neighbor

k-d tree

Regularization (mathematics)

L1 regularization

Matrix compression

Laplacian of a graph

Reservoir sampling

Markov chain Monte Carlo (MCMC)

Majority elements

Distance-preserving compression

PAC Guarantees

Linear-Algebraic Techniques

De-noising

Eigenvectors/eigenvalues

Markov's inequality

The Fourier Perspective

Linear programming

Dimensionality Reduction

Approximate heavy hitters

Locality-Sensitive Hashing (LSH)

MinHash

Principal Component Analysis (PCA)

Matrix completion

Spectral embeddings

Chebyshev‘s inequality

Convolution

Convex optimization

Empirical risk minimization

Bloom filters

Jaccard Similarity

Polynomial embedding

Maximizing variance

Uniqueness of low-rank tensor factorizations

Graph coloring

Importance Sampling

Sparse Vector/Matrix Recovery

Privacy Preserving Computation

Count-min sketch

Euclidean Distance

Johnson-Lindenstrauss Transform

Random projection

Power iteration algorithm

Jenrich's algorithm

Spectral clustering

Markov Chains

Compressed Sensing

Differential privacy

Similarity Search

Lp distance

Generalization

L2 regularization

Singular Value Decomposition (SVD)

Spectral Graph Theory

Interpretations of the second eigenvalue

Mathematical Programming

CS 168: The Modern Algorithmic Toolbox Stanford University Spring 2022 CS 168 provides a comprehensive introduction to modern algorithm concepts, covering hashing, dimension reduction, programming, gradient descent, and regression. It emphasizes both theoretical understanding and practical application, with each topic complemented by a mini-project. It's suitable for those who have taken CS107 and CS161.  This course will provide a rigorous and hands-on introduction to the central ideas and algorithms that constitute the core of the modern algorithms toolkit. Emphasis will be on understanding the high-level theoretical intuitions and principles underlying the algorithms we discuss, as well as developing a concrete understanding of when and how to implement and apply the algorithms. The course will be structured as a sequence of one-week investigations; each week will introduce one algorithmic idea, and discuss the motivation, theoretical underpinning, and practical applications of that algorithmic idea. Each topic will be accompanied by a mini-project in which students will be guided through a practical application of the ideas of the week. Topics include modern techniques in hashing, dimension reduction, linear and convex programming, gradient descent and regression, sampling and estimation, compressive sensing, and linear-algebraic techniques (principal components analysis, singular value decomposition, spectral techniques).  CS107 and CS161, or permission from the instructor. 

CS 168: The Modern Algorithmic Toolbox

Theoretical Computer Science

Polynomial Identity Testing

Karger's algorithm

Karger-Stein algorithm

Primality Testing

Sampling-based median algorithm

Moment generating functions

Chernoff bound

Randomized routing on the hypercube

Balls and Bins

"Poissonization"

The power of 2 choices

Metric Embeddings

Bourgain's embedding

Johnson-Lindestrauss Transform

Dimension reduction and sparsity

Restricted Isometry Property (RIP)

Ramsey's theorem

Independent Sets

De-randomization via Conditional Expectations

Second-moment method

Algorithmic Lovász local lemma

Randomized algorithm for 2SAT

Fundamental Theorem of Markov Chains

Mixing times

Strong stationary times

Coupling

Martingales

the Doob Martingale

Azuma-Hoeffding tail bounds

The martingale stopping theorem

Pseudorandomness: expanders and extractors

CS 265 / CME 309 Randomized Algorithms and Probabilistic Analysis Stanford University Fall 2022 This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required. Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms.  CS 161 and STAT 116, or equivalents and instructor consent. 

CS 265 / CME 309 Randomized Algorithms and Probabilistic Analysis