Big Data Algorithms and Data Structures
- Instructor:
- Hu Fu
fuhu@mail.shufe.edu.cn
Office: 504 School of Information Management and Engineering
- Lectures:
- Friday 8:55-11:45am, 301 Lecture Hall No 3
- Syllabus:
-
This course is a theoretical introduction to basic data structures and algorithms used to deal with data of large scales.
Randomization plays a crucial role in these techniques, and a large of part of this course focuses on randomized algorithms and data structures.
Topics include a review of discrete probability theory, hashing, concentration inequalities, examples of randomized data structures, dimensionality reduction, streaming algorithms, and selected other topics.
- Prerequisites:
-
Familiarity with basic data structures and algorithms will be assumed.
Discrete probability theory will be used throughout the course; a quick review will be provided at the beginning of the course.
- Texts:
-
There is no required textbook.
Supplementary readings are occasionally provided here. Optional readings will be marked as such.
- Course Work:
-
Grades are determined by Problem sets/written assignments (30%) + Project (30%) + Final (40%). The final is a take-home exam.
For the course project, students will form groups of up to 4 people and survey a topic related to big data data structures or algorithms.
The instructor will suggest candidate topics, but students are encouraged to explore topics of their own interests.
Each group will make an in-class presentation in the last lecture, and submit a survey.
A survey can be in either Chinese or English, with an expected length of two pages.
The projects will be evaluated based on the quality of presentation and the written survey.
- Homework Policies:
-
- We will have 3-4 written assignments. Students are encouraged to form groups of up to three people for each assignment. Each group needs to turn in only one solution, but every group member must be able to explain everything turned in.
- No late solutions will be accepted.
- Typesetting solutions using LaTex is encouraged.
Here is a LaTeX template for your reference.
-
For assignments and exams, unless it is stated otherwise, for all questions that ask to design an algorithm, you need to provide justification for (i.e., to prove) the correctness of your algorithm. When the question asks for a certain running time (e.g. polynomial time, or O(n^2)), you should analyze the running time of your algorithm.
-
Assignments and their solutions will be posted on the Canvas system.
You should turn in your solutions there or hand them in at the start of the lecture. Please make sure that your submission has all the names of your group members.
-
Some problems in the assignments are more challenging than the others. You are encouraged to discuss problems among yourselves or come to office hours. You should start thinking about the problems early and not wait till the last day or two. Allow yourself time to think and to seek help.
-
If you do work with someone outside your group or use some outside source, you must acknowledge them in your write-up.
- Schedule:
-
-
Sept 12: Introduction and review of probabilities
-
Sept 19: Universal hashing, Bloom filters, Markov inequality
-
Sept 26: Chebyshev inequality, Chernoff bounds, Quicksort
-
Oct 10: Fisnishing quicksort; Balls and bins, skip lists, Johnson-Lindenstrauss transform
-
Oct 17: Streaming model, AMS, k-wise independent hash
-
Oct 24 Finishing AMS. Count-min, Count-sketch, distinct elements
-
Oct 31: Distinct elements, Fast JL Transform,
-
Nov 7: Sparse Recovery, Compressed Sensing
-
Nov 14: Finish Compressed Sensing, proof of RIP, similarity estimation
-
Nov 21: Project presentations. Nearest neighbor search with JL-transform. Locality sensitive hashing for Hamming distance.