## Info

#### Instructor

**When**: Tue, Thu 5pm-6.30pm**Where**: CAS-B18**Prof**: Babis Tsourakakis**Email**: ctsourak@bu.edu**Office hours**: Tu 9.30-10.30am (MCS102) and R 9.30-10.30am (Zoom)

#### Teaching Fellow

**TF**: Mr. Ryan Yu**Email**: ryu1@bu.edu- Teaching Labs on each Monday (Attendance mandatory, attend your session!)
**Office hours**: M (PSY B53): 12:20 – 2.15 , W (via zoom): 5:30 – 7 PM

Zoom Links and passcodes are available on Piazza

## Piazza website

CS365 Github

Prerequisites

Students taking this class must have taken:

- CS 112
- CS 131 (MA293)
- CS 132 (MA242)
- and CS 237 (MA581) or equivalent.

The consent of the instructor is necessary to take the class. Otherwise, you will not get a final grade. CS 330 is *highly *recommended but not mandatory requirements as the previous.

## Syllabus

Topics will include probability, information theory, linear algebra, calculus, Fourier analysis, graph theory with a strong focus on their applicability for analyzing datasets. Finally, two lectures will be devoted to data management, and more specifically the classic relational model, SQL and Datalog. A detailed syllabus is available on Piazza, with the code to sign up on Gradescope.

## Textbooks

No need to buy a textbook. There will be assigned readings from the following books that are available online (click for the pdf)

- Foundations of Data Science by Avrim Blum, John Hopcroft, Ravi Kannan
- Understanding Machine Learning: From theory to algorithms by Shai Shalev-Shwartz and Shai Ben-David
- Introduction to Probability for Data Science by Stanley Chan
- Mathematics for Machine Learning by Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong.

## Programming

The class assumes familiarity with programming. The recommended languages for this class are Python3 and Julia. R and Matlab are also recommended. Other languages are welcome (C, C++, Java, etc), but are not recommended for this class.

## Lectures

**Note**: at the end of each lecture, you will find the assigned readings. The readings associated with a magnifying glass are mandatory. The rest is material if you are further interested, and have the time to devote.

**Lecture 1 (1/20)**: data visualization – introduction, class logistics, types of data, basics of data visualization

Slides available here**Lecture 2 (1/25)**: probability I – review of prerequisite material, and other basic concepts through problem solving

Slides available here.**Lecture 3 (1/27)**: probability II – convergence of random variables, probability inequalities, Weak law of large numbers, confidence intervals

Slide available here.**Lecture 4 (2/1)**: probability III – π estimation randomized algorithm Central Limit theorem, moment generating functions, Chernoff bounds

Slides available here.**Lecture 5 (2/3)**: probability IV, statistical inference I , machine learning I– Bayes’ rule, Naive Bayes classifier

Slides available here.**Lecture 6 (2/8)**: probability V, statistical inference II, machine learning II– denoising images using Bayes’ rule

Slides available here.**Lecture 7 (2/10)**: probability VI, statistical inference III– concentration of measure (cont.), sampling theorem

Slides available here.**Lecture 8 (2/15)**: statistical inference IV – method of moments, MLE, Bayesian inference, MAP

Slides available here.**Lecture 9 (2/17)**: statistical inference V – EM algorithm for parametric inference

Slides available here.**Midterm 2/24****Lecture 10 (3/1)**: streaming algorithms I – streaming model, missing number puzzle, reservoir sampling, moment estimation problem

Slides available here.**Lecture 11 (3/3)**: streaming algorithms II – F1 estimation using Morris counters

Slides available here.**Lecture 12 (3/15)**: streaming algorithms III -k-wise independence, F0, F2 estimation

Slides available here and here.**Lecture 13 (3/17):**dimensionality reduction I, machine learning III – distance functions, k-nearest neighbors classifier, Johnson-Lindenstrauss lemma

Slides available here.**Lecture 14 (3/22)**: linear algebra I – vector space, subspace, linear mapping, linear independence, basis, basics of matrices (whiteboard lecture)

Prerequisite CS132 material here.**Lecture 15 (3/24)**: linear algebra II – projections on subspaces, least squares, eigenvalue decomposition, real symmetric matrices’ spectral properties (whiteboard lecture)

Prerequisite CS132 material here.**Lecture 16 (3/29)**: dimensionality reduction II, matrix decompositions I – singular value decomposition (SVD)

Slides available here.**Lecture 17 (3/31)**: dimensionality reduction III, matrix decompositions II – math of singular value decomposition (SVD), and principal component analysis (PCA) (whiteboard lecture)**Lecture 18 (4/5)**: dimensionality reduction IV, matrix decompositions III – PCA for dimensionality reduction

Python code here and a demo here.**Lecture 19 (4/7)**: graphs I – G(n,p) model, community detection using spectral clustering

Python code here and notes for the emergence of K4s here.**Lecture 20 (4/12)**: graphs II – community detection using spectral clustering, Markov Chains (intro)

Python code here.**Lecture 21 (4/14)**: graphs III – Markov Chains (cont.), Pagerank

Python code here.**Lecture 22 (4/19)**: vector calculus I – level curves, gradient, directional derivative, Hessian, chain rule

Slides available here.**Lecture 23 (4/21)**: vector calculus II – matrix calculus

Slides available here.**Lecture 24 (4/26)**: vector calculus III optimization I – Taylor series, formulating problems, minimization, Weierstrass theorem

Slides available here.**Lecture 25 (4/28)**:vector calculus IV optimization II – 1st and 2nd order necessary conditions, gradient descent

Slides available here.**Lecture 26 (5/3)**:vector calculus V optimization III – gradient descent, convexity, Lagrange multipliers, duality

Slides available here.