Computer Science Theory for the Information Age covers the computer science theory likely to be useful in the next 40 years， including high- dimensional space， random graphs， singular value decomposition. random walks， Markov chains， learning algorithms， VC-dimension， algorithms for massive date problems， clustering. The book also covers graphical models and belief propagation， ranking and voting， sparse vectors， and compressed sensing. The book is intended for either an undergraduate or a graduate theory course in computer science. Prof. John Hopcroft is a world-renowned scientist and an expert on education in computer science. He was awarded the A. M. Turing Award in 1986 for his contributions in theoretical computing and data structure design. Dr. Ravindran Kannan is a principal researcher with Microsoft Research Labs located in India.

Description Contents Resources Courses About the Authors This book provides an introduction to the mathematical and algorithmic foundations of data science, including machine learning, high-dimensional geometry, and analysis of large networks. Topics include the counterintuitive nature of data in high dimensions, important linear algebraic techniques such as singular value decomposition, the theory of random walks and Markov chains, the fundamentals of and important algorithms for machine learning, algorithms and analysis for clustering, probabilistic models for large networks, representation learning including topic modelling and non-negative matrix factorization, wavelets and compressed sensing. Important probabilistic techniques are developed including the law of large numbers, tail inequalities, analysis of random projections, generalization guarantees in machine learning, and moment methods for analysis of phase transitions in large random graphs. Additionally, important structural and complexity measures are discussed such as matrix norms and VC-dimension. This book is suitable for both undergraduate and graduate courses in the design and analysis of algorithms for data.