Useful References related to various topics:
Topics
We will likely cover parts of MMDS Chapters 3, 4, 5, 7, 8, 9,
11, and possibly 10 and 6. In addition to this there will
be more material on Data Streaming from some research articles.
In broad terms, some combination of the following topics:
Link Analysis
Mining Data Streams  Frequency and Moment Estimates
Finding Similar Items  Locality Sensitive Hashing
Advertising on the web  Adwords & Online matching
Recommendation Systems  Collaborative Filtering
Dimensionality Reduction  Eigenvalues, PCA, SVD
Clustering  KMeans
Mining Social Networks  Community Detection, Partitioning of
Graphs, Dynamic Graph Algorithms
Frequent Itemset
+ some probability+linear algebra as and when required.
Assignment # 
Posted On (Tentative) 
Due Date 
I 
September 19th (see Brightspace) 
Oct 13th 
II 

III 
Week
# 
Topic 
Remarks 
Week
0 
What
is this course about? Introduction + Course Logistics 

Week
0/1 
Majority,
Heavy Hitters, and Introduction to CountMin Sketch. Linear Algebra  Symmetric Matrices 
Read
Section 10.1 of Notes Section 4.1 of Notes 
Week
2 
Bloom
Filters Linear Algebra  Eigenvalues 
Section 10.2 of Notes Section 4.2  4.4 of Notes 
Week
3 
Estimating
Frequency Moments F_0 and F_2 + Markov Chains 
Section 10.3 of Notes + Chapter 4 of MMDS Section 4.7 of Notes 
Weeks
3/4 
Estimating
Frequency Moments F_0 and F_2 + Pagerank Algorithm 
Section 4.7 of Notes 
Weeks 4/5  Balls
and Bins +
Assignment 1 Solutions 
Exercises of Chapter 4 of Notes and COMP 2804
Textbook 
Week 6  Stream
Statistics over Sliding
Window Locality Sensitive Hashing 
Section 10.4 of Notes Chapter 9 of Notes Sections: 9.19.3 Section: 9.6.5 
Study Break (Oct 2529) 

Week
7 
LSH 
Metric Spaces, Hamming and
Near Neighbors, Matching
Fingerprints Adwords Problem 
Chapter in mmds.org on Advertising on the Web Section 11.1 (My notes have proofs using the Linear Programming formulation) 
Week
8 
Balance Algorithm  
Week 9  Collaborative Filtering 
Chapter 9 of MMDS 
Week
10 
Collaborative
Filtering Contd. Dimensionality Reduction SVD 
Section 4.5 of my notes + Chapter 11.3 and 11.4 of MMDS 
Week
1011 
CUR+
Assignment 3 Problems 

Week 12  Clustering MWUMethod (How to become an expert) 
kmeans (Llyod's algorithm,
MMDS Section 7.3) and kmeans++ paper (Arthur and Vassilvitskii, 8th ACMSIAM Symposium
on Discrete algorithms, 2007) Section 11.5.1, 11.5.2 of my notes. Randomized MWU (without proofs)  see Section 11.5.3 and 11.5.4 of my notes. 
Week 12/13 
MWUMethod MWIS 
Maximum Weight Independent Sets (Recoverable Values) 
Final Exam 
Important Dates: For important academic dates and deadlines, refer to https://calendar.carleton.ca/academicyear/