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.

Stochastic Optimization
Metric Embedding
Fourier Analysis

For the later, we will emphasize on the following two areas.

Biological Applications
Network Analysis

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
Paper1
Paper2
Paper3

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

Chapter 15 of the book Lectures on Discrete Geometry, by Jiri Matousek.
A handbook chapter by Piotr Indyk and Jiri Matousek.
A survey paper and talk from FOCS 2001 by Piotr Indyk.

Mar 6th Embeddings into l_infinity
Lecture 3

Mar 13th Embeddings into l_p spaces.
Lecture 4

Mar 20th No Class--Spring Recess

Mar 27th Embedding into tree distribution
Lecture 5
Lecture 6

Apr 3rd Applications
Reading-1
Reading-2 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
Reading-1
Reading-2 Large Scale Optimization Course at UTexas
Non-linear Programming Course at MIT, Lecture 1 to 4

Apr 24th Gradient Descent Continued
Reading-3

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 Paper1 Paper2 Paper3
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 Chapter 15 of the book Lectures on Discrete Geometry, by Jiri Matousek. A handbook chapter by Piotr Indyk and Jiri Matousek. A survey paper and talk from FOCS 2001 by Piotr Indyk.
Mar 6th	Embeddings into l_infinity Lecture 3
Mar 13th	Embeddings into l_p spaces. Lecture 4
Mar 20th	No Class--Spring Recess
Mar 27th	Embedding into tree distribution Lecture 5 Lecture 6
Apr 3rd	Applications Reading-1 Reading-2	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 Reading-1 Reading-2	Large Scale Optimization Course at UTexas Non-linear Programming Course at MIT, Lecture 1 to 4
Apr 24th	Gradient Descent Continued Reading-3