Algorithms for Big Data (Fall 2019)
General Information
Instructor:
Chihao Zhang
Time:
Friday
12:55 - 15:40
Location:
DongShangYuan (东上院) 107
Office Hour:
Monday
6:00pm - 8:00pm
School of Software (软件学院) 1402-2
References
The main references of this course are lecture notes from following courses:
Data Stream Algorithms
Algorithms for Big Data
Algorithmic Techniques for Big Data
Algorithms for Massive Data
Sketching Algorithms for Big Data
News
[Nov 10]
Assignment 2 is out, due on Nov. 29.
[Oct 11]
Assignment 1 is out, due on Oct. 25. SJTU students can find the assignment on
Canvas
.
Lecture Notes
[Nov 29][
slides
][
handout
]
Graph Laplacian, Courant-Fischer theorem, Random walk
[Nov 22][
slides
][
handout
]
Approximate matrix multiplication; Graph spectrum
[Nov 15][
slides
][
handout
]
Yao's lemma; Lower bound for connectivity; Lower bound for 0-norm
[Nov 08][
slides
][
handout
]
Communication complexity; Disjointness; Lower bound for streaming algorithms
[Nov 01][
slides
][
handout
]
Shortest path; Maximum matchings; Counting triangles
[Oct 25][
slides
][
handout
]
Johnson-Lindenstrauss lemma; p-stable distribution; Graph stream
[Oct 18][
slides
][
handout
]
Count-Min; AMS estimator for frequency moments; Tug-of-War estimator
[Oct 11][
slides
][
handout
]
BJKST algorithm; Frequency estimation; Misra-Gries; Count Sketch
[Sep 29][
slides
][
handout
]
Strongly 2-universal family of Hash functions; AMS algorithm for counting distinct elements
[Sep 27][
slides
][
handout
]
Concentration inequalities; Universal Hash function family
[Sep 20][
slides
][
handout
]
Streaming model, Morris algorithm