Big Data Algorithms and Data Structures
- Instructor:
- Hu Fu
fuhu@mail.shufe.edu.cn
Office: 504 School of Information Management and Engineering
- Lectures:
- Monday 8:55-11:45am, 803 Third Lecture Hall
- 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 (40%) + Project (20%) + 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 5: Introduction and review of probabilities
-
Sept 12: Universal hashing, Bloom filters, Markov inequality
-
Sept 19: Perfect hashing, Chebyshev inequality, Chernoff bounds, Quicksort
-
Sept 26: Balls and bins, skip lists, Johnson-Lindenstrauss transform
-
Oct 9: Streaming model, AMS, k-wise independent hash
-
Oct 16: Count-min, Count-sketch, sparse recovery, distinct elements
-
Oct 23: Distinct elements, Fast JL Transform
-
Oct 30: Similarity estimation, Compressed Sensing
-
Nov 6: Finish compressed sensing. Project presentations
-
Nov 13: Project presentations