CS6741 - Algorithmic Foundations of Data Science

Course Data :


  • Mathematical Basics: Probability theory including random variables, conditional probability, Bayes law, concentration of measure, martingales; graph theory including basic definitions, spanning trees, connectivity, cuts; linear algebra including eigenvalues, norms, elementary spectral graph theory.
  • Traditional and Data Centric Models of Computations Turing machine model, RAM model, streaming, sublinear algorithms, distributed data centric models based on MapReduce and Pregel.
  • High Dimensional Space High dimensional sphere, volumes of high dimensional solids, gaussians in high dimension, high dimensional point sets, Johnson-Lindenstrauss theorem.
  • Sampling and VC-dimension Random walks and graph sampling, MCMC algorithms, learning, linear and non-linear separators, VC-dimension and connection to sampling, PAC learning.
  • Sketching and Sparsification Locality sensitive hashing, min-wise hashing, Bloom filters, count-min sketches, compressed sensing, graph sparsification techniques, pseudo-random generators with application to approximating norms.
  • Communication Complexity Model, fooling sets, equality, disjointness, hardness reductions for problems in streaming, distributed verification, and property testing.




Credits Type Date of Introduction
4-0-0-0-8-12 Elective Jul 2014

Previous Instances of the Course

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits