Spring 2022

Stanford University

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.

No data.

No data

Lecture notese available at Proposed Lecture Schedule

No videos available

Mini-projects available at Announcements

Supplementary materials available at Proposed Lecture Schedule

Approximate heavy hittersBloom filtersChebyshev‘s inequalityCompressed SensingConvex optimizationConvolutionCount-min sketchDe-noisingDifferential privacyDimensionality ReductionDistance-preserving compressionEigenvectors/eigenvaluesEmpirical risk minimizationEuclidean DistanceGeneralizationGraph coloringImportance SamplingInterpretations of the second eigenvalueJaccard SimilarityJenrich's algorithmJohnson-Lindenstrauss TransformL1 regularizationL2 regularizationLaplacian of a graphLinear programmingLinear-Algebraic TechniquesLocality-Sensitive Hashing (LSH)Lp distanceMajority elementsMarkov ChainsMarkov chain Monte Carlo (MCMC)Markov's inequalityMathematical ProgrammingMatrix completionMatrix compressionMaximizing varianceMinHashNearest NeighborPAC GuaranteesPolynomial embeddingPower iteration algorithmPrincipal Component Analysis (PCA)Privacy Preserving ComputationProperty-preserving lossy compressionRandom projectionRegularization (mathematics)Reservoir samplingSimilarity SearchSingular Value Decomposition (SVD)Sparse Vector/Matrix RecoverySpectral Graph TheorySpectral clusteringSpectral embeddingsStationary distributionsThe Fourier PerspectiveUniqueness of low-rank tensor factorizationsk-d tree