CMPUT 675: Algorithms for
Streaming and Big Data
Fall 2019, MW 12:00-13:20, Location: CSC
B41.
Instructor: Mohammad
R. Salavatipour
Course description and
objectives
The focus of the course is in design and analysis
of algorithms dealing with massive data, typically so large that
it cannot fit into storage and hence the algorithm might have
access to a stream of data. The constraints we typically have to
work with is limited memory size compared to the massive data
size. We will discuss algorithms for sampling and sketching,
dimensionality reduction, sparsification, approximate query
processing, etc. We will see several techniques along they way and
the focus is on the design and analysis of the algorithms, rather
than particular applications and how they will be used in
practice.
Prerequisites
CMPUT 304 or strong undergraduate background in
theoretical computer science, mathematics, and statistics.
Grading Scheme
This is a theory course (no programming involved).
Each student is expected to take notes for one or two lectures
(depending on the number of participants). The notes should be
typeset using the template provided below and submitted within 5
days after the lecture. In doing so you have to complete the steps
in the proofs and provided details for parts that are sketched in
the lecture. You submit your .tex files and all supporting files.
This will be worth 10% of your grades.
There will be 3-4 sets of assignments (worth 60%).
The remaining 30% is for a course project. The project can be a
survey on a topic related to the course (to be agreed upon
mutually) or can be a presentation. See details of project below.
Homework assignments, scribe notes, as well as written
projects must be prepared using LaTeX.
Lecture notes
As a template for course notes, here is a source
file for lecture 1.
Here is the algorithms.sty and picins.sty
Assignments
Course Project
For your course project you have two options. One option could be
a written survey (up to 10 pages) of a few papers (one or two or
three) related to the topics of the course, or it could be a
presentation in one of the lectures again on a topic related to
the course. The written projects are due Dec 4 and this is
a firm deadline.
Presentations will be in the last 3 weeks of Nov. So if you pick
to do a presentation you must select the topic
early on. In order to pick your project you must submit a proposal
to me by Oct 23, stating what you plan to do, list of
papers/topics you propose to work on and whether it will be a
presentation or a survey. This can be a simple e-mail. We have to
come to a mutual agreement on the project by Nov 4.
Here is more information about project
topics.
Course Policies
Please refer to the Department
Course Policies for general information about course
policies.
Assignments are due before the start of the lecture on the due
dates. Late assignments up to 24 hours will be deducted 20% of
full grade. After 24 hours no assignment will be accepted.
Scribed Lecture notes are due 5 days after the lecture. You need
to send all source files (.tex and images if any).
There is no text book for this course. Here are some useful links
to similar courses and other resources:
Questions? Send email to me ...