Home Page for CMPSCI 691DA (Big Data Algorithms & Applications)

Instructor: Barna Saha Office: CS 322. Office phone: (413) 577-2510. E-mail: barna@cs.umass.edu.

Office Hours: By appointment.

Class Time: Currently Scheduled for Fri 2:30--3:30pm. CS 140.

Course Overview: Big Data brings us to interesting times and promises to revolutionize our society from business to government, from healthcare to academia. As we walk through this digitized age of exploded data, there is an increasing demand to develop unified toolkits for data processing and analysis. In this course our goal is two fold, (i) to study a subset of topics that build the mathematical foundation of big data processing, and (ii) to learn about applications of big data in important domains of interest. For the former, our plan is to concentrate on the following three topics.

For the later, we will emphasize on the following two areas. I will post relevant papers on the topics that we will cover in the course before the Spring semester starts. So stay tuned!

Course Work: This is a one credit seminar course covering several papers and course notes on the topics listed above. Each student will be assigned 1 paper/lecture note before the beginning of the semester which they will present in the class.
The presentation of theory paper needs to be in-depth (preferably board presentation) covering the detailed proofs of main theorems and lemmas. Assignment of presentation topic to students will be based on first-come-first-served basis.

Prerequisites: The students are expected to have strong mathematical foundations, must have basic knowledge of algorithms and probability, and should be able to read and understand papers appearing in top theoretical computer science conferences. Senior undergraduate students meeting these requirements are encouraged to take this course.

Class Paper to be presented References
Jan 23rd Introduction to Fourier Sampling, k-Sparse Fourier Sampling
Lecture 1 MIT 6.893
Lecture 2 MIT 6.893
Survey on Sparse Fourier Transofrm
Jan 30th Average case O(klog(n)) algorithm for Sparse Fourier Transform
Lecture 3 MIT 6.893
Feb 6th O(k log n) algorithm for worst case k-sparse signals.
Lecture 4 MIT 6.893
Lecture 5 MIT 6.893
Feb 13th Applications: Network Evolution via Spectral Analysis
Reading 1-a
Reading 1-b
Time-Frequency Analysis of Biomedical Signal
Reading 2-a
Presentation 2-b
Feb 20th Recap: buffer class
Feb 27th Intro to Embedding, Metric Methods in Algorithms
Lecture 1
Lecture 2
Lecture Notes from Algorithmic Applications of Metric Embeddings class at CMU
Mar 6th Embeddings into linfinity
Lecture 3
Mar 13th Embeddings into lp spaces.
Lecture 4
Mar 20th No Class--Spring Recess
Mar 27th Embedding into tree distribution
Lecture 5
Lecture 6
Apr 3rd Applications
Complex Networks and Hidden Metric Space
Apr 10th No Class due to travel, Substitute class date will be declared later.
Substitute Class, Date TBD Recap: buffer class
Apr 17th Intro to Convex Optimization, Gradient Descent
Large Scale Optimization Course at UTexas
Non-linear Programming Course at MIT, Lecture 1 to 4
Apr 24th Gradient Descent Continued