Big Data Algorithms

Course Summary

To introduce data acquisition, structure of bigdata, map reduce algorithms, stream algorithms and applications: search, social network, machine learning, computational advertising, blockchain database.

Final Exam


Project


Midterm Exam


Administrative Information

Lectures: Mon 10:00-11:40am & Wed 10:00-11:40am, Chen Rui Qiu Building, Room 309

Instructor: Xiaotie Deng - SEIEE 3-428 Email: deng-xt@cs.sjtu.edu.cn
Office hours: by appointment via email or ask after class

Teaching Assistant:
Juntao Wang - SEIEE 3-524, Email: wjtcute@126.com Phone: 18801906372
Rucha Kulkarni - SEIEE 3-524, Email: ruchak@cse.iitb.ac.in Phone: 13020151236
Wenhan Huang -SEIEE 3-524, Email: wenhanhuang1993@gmail.com


Assessment Information

Please submit any required materials in pdf, ppt, or word(not recommanded) to wjtcute@126.com



Handout

  • If the slides are not presented in proper format, please download them and open in a pdf reader.
  • The student who reports to any TA a new error in any formula or notation or misleading typo will be announced in this page and get a bonus in final grade.
  • The deadline of each assignment will be automatically set at one week after the corresponding lecture. You do not need to do all the assignments but any four of them.
  • Please submit your assignment to email: wjtcute@126.com
Lecture Assignment Reference Supplements
0. Introduction updated at Sep. 28
1. Median Algorithm Selection and Sorting With Limited Storage
1D Random Walk
Photos of the lecture
2. Shortest Path Query Spanner Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
3. Convex Hall & Tangent Algorithms Assignment1 ddl: Sep. 30 Photos of the lecture
4. Kolmogorov Complexity Updated at Sep. 28 Wiki Lecture notes on descriptional complexity and randomness
Lecture 2. Randomness
5. Sketch of Big Data
6. Fix parameter algorithms
7. Yao's Principle and Randomness Wiki
8. Martingale, Azuma Inequality and Random Graph Coloring
9. Paradox in Games Assignment2 ddl: Nov. 4
10. Google's Big Table and Replacement Algorithms Google's Big Table
Paging Algorithms
11. Probabilistic Data Structure I Bloom_filter , Random_oracle , Related work
12. Probabilistic Data Structure II
13. Selfish Mining Blockchain
14. Second Memory Sorting new
15. Project Instructions new Assignment 3 ddl: Nov. 28
16. MapReduce new