Algorithms for Data Science (COMP 5112)

Assignments

Instructor: Anil Maheshwari
Office: Herzberg Building 5125B (None of us can access it for time being!)
E-mail: anil@scs.carleton.ca

Lectures: Online lectures twice a week (may change). I am planning to hold lectures on Wednesdays and Fridays at 2:30PM. First one will be on Friday September 11th, and the link will be provided via cuLearn. The schedule may change once I know your time zones. The recorded videos will likely be posted in cuLearn. The recordings are not to be shared with anybody.

Office hours: During the breaks and immediately after the online lectures.

Course objectives:

To learn some of the algorithmic techniques to handle data science problems.
Topics may include:

Randomized Algorithms in Linear Algebra
Data Streaming
Dimensionality Reduction
Online Algorithms (including the role of Primal-Dual LPs in their analysis)
Finding Similar Items using Hashing
Nearest Neighbor Searching
Random Graphs and Second Moment Method
Algorithmic Aspects of Social Networks (Graph Partitioning, Searching various substructures)

These topics may be adjusted based on the background and interest of the students in the class.

Required Background:

We will cover a spectrum of techniques from the design and analysis of algorithms. It is assumed that you have a very good grasp on:

Analysis of algorithms (O-notation, recurrences, and complexity analysis)
Elementary probability theory including expectation, indicator random variables, Variance, Markov's Inequality (contents of COMP 2804)
Basic data structures (lists, trees, hashing, BST)
Discrete mathematics (counting, permutations and combinations, graph theory, proof techniques: induction, contradiction, ..)
Algorithmic techniques (divide and conquer, greedy, dynamic programming, BFS, DFS, Connectivity, Shortest Paths, and what is NP-Compleness)
Linear Algebra (Eigenvalues/vectors, Rank-Nullity, Vector Spaces, Norms).

Note that there will not be sufficient time to review the background material to a satisfactory level during the course. (In nutshell you must have a background that is equivalent to the following Carleton Courses: COMP 1805, COMP 2402, COMP 3804, and a course in Linear Algebra.)

Reference Material:

Foundations of Data Science by Blum, Hopcroft and Kanan.
My Notes on Topics in Algorithm Design
Mining of Massive Data Sets: mmds.org
Several Research Articles that will be mentioned during the course.

Useful References related to various topics. This will get modified as we go along the course.

Linear Algebra:

Eigenvalues (1 2)
Video Lectures and the book of Gilbert Strang
Chapter on Matrices for CS in My Notes on Topics in Algorithm Design

PageRank:

Probability:

Locality Sensitive Hashing

Chapter 3 in Mining of Massive Data Sets by Stanford Group (mmds.org)
Chapter on LSH in My Notes on Topics in Algorithm Design
Useful references on LSH
STOC98 paper of Indyk-Motwani

Data Streaming

Mining Data Streams chapter of MMDS
Wikipedia Article
DGIM Article
Count-Min Sketch Article
AMS Article (Approximating frequency moments)
Flajolet and Martin's Article on number of distinct elements in a stream
Some parts are covered in the Chapter in My Notes on Algorithm Design
My talk on Bloom Filters and Count-Min-Sketch

Adwords

Chapter on Advertisement on the Web from the MMDS Book.

SVD/Dimensionality Reduction:

Chapter in the MMDS book on Dimensionality Reduction
Try a few SVDs using Wolfram Alpha.

Randomized Load Balancing & Perfect Hashing

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec7.pdf

Kleinberg&Tardos Algorithm Design Book, Chapter 13.

Grading Scheme: (Tentative)

- Assignments/Exercises: 30% (including a Take Home Exam)
- Scribe Notes: 15% (you will be responsible to type in content of (part of) one of the lectures in a LaTeX template and add some relevant exercises),
- Project: 55% (initial proposal 10% + short report 30% + presentation 15%). Outline is as follows:

Pick a topic. (Look at references under "Reference Material" and conferences in related areas and also use Google Scholar) to see who refers to those papers etc.)
Initial Proposal: Submit a 1-2 page draft. What is the topic you chose? Why? What problem(s) you will look at? What you plan to do? Outline of sections of your report? Main References. Due (in pdf format) by October 2nd.
Report (Initial Draft): Due by November 9. The report format will likely be a research article. Its best to use LaTeX (e.g. see Overleaf). The sections will include:

Introduction (Motivation, Problem Statement, Related Work, Short Summary of what you did).
Preliminaries (In case you need to discuss some notation, definitions, etc. as background
Main Section - How did you solve the problem; State Algorithm; State its Analysis; State its Correctness. (NOTE: This will be expressed in terms of multiple questions and answers, and I will explain this further. )
Experiments (in case you performed any simulation etc.)
Conclusion (Summary + What did you learn? + What do you think can be done in future?)
References

Recorded Presentation and Final Report: Due on November 30. Presentation is a pre-recorded Video of approximately 10 minute duration describing your project (this will be posted on cuLearn under course web-page). Report will be approximately 6 page long and will also be posted on cuLearn. (Take Home Exam will have questions from these reports/presentations).

Weekly Schedule (Tentative):

Week #	Topics	References
Week 1	Introduction. What is this course about? Course Logistics Probability Basics Balls and Bins Experiments Hashing
Week 2	Data Streaming Count Min Sketch and its Applications Sliding Window
Week 3	Estimating Frequency Moments in a Data Stream
Week 4	Locality-Sensitive Hashing LSH Families Applications
Week 5	Geometric Algorithms - Approximate Nearest Neighbors - Clustering - Core Sets
Week 6	Online Algorithms - Classical Examples - Matching - Analysis via Primal-Dual LP
Week 7	Regret Minimization - Multiplicative Weights Algorithm
Week 8	Linear Algebra Review Graph Partitioning Applications in Social Networks
Week 9	Dimensionality Reduction
Week 10	Second Moment Method Random Graphs
Week 11	Randomized Linear Algebra
Week 12	Project Presentations

Important Considerations:

Late assignments/reports/projects are not accepted. All submissions are handled electronically (i.e., through cuLearn) and there is no "grace period" with respect to a deadline. Technical problems do not exempt you from this requirement. You are advised to:

periodically upload you progress (e.g. upload your progress at least daily)
attempt to submit your final submission at least one hour in advance of the due date and time.

University Policies

We follow all the rules and regulations set by Carleton University, Dean of Science, and the School of Computer Science regarding accommodating students with any kind of need(s). Please consult with the appropriate authorities to see how you can be accommodated and please follow their procedures. For information about Carleton's academic year, including registration and withdrawal dates, see Carleton's Academic Calendar. Following is a standard list of recommendations that we have been advised to provide you with respect to whom to contact for the appropriate action(s):

Pregnancy Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit Equity Services.

Religious Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit Equity Services.

Academic Accommodations for Students with Disabilities If you have a documented disability requiring academic accommodations in this course, please contact the Paul Menton Centre for Students with Disabilities (PMC) at 613-520-6608 or pmc@carleton.ca for a formal evaluation or contact your PMC coordinator to send your instructor your Letter of Accommodation at the beginning of the term. You must also contact the PMC no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with your instructor as soon as possible to ensure accommodation arrangements are made. For more details, visit the Paul Menton Centre website.

Survivors of Sexual Violence. As a community, Carleton University is committed to maintaining a positive learning, working and living environment where sexual violence will not be tolerated, and survivors are supported through academic accommodations as per Carleton's Sexual Violence Policy. For more information about the services available at the university and to obtain information about sexual violence and/or support, visit: carleton.ca/sexual-violence-support.

Accommodation for Student Activities. Carleton University recognizes the substantial benefits, both to the individual student and for the university, that result from a student participating in activities beyond the classroom experience. Reasonable accommodation must be provided to students who compete or perform at the national or international level. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, see the policy.

Student Academic Integrity Policy. Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Examples of punishable offences include: plagiarism and unauthorized co-operation or collaboration.

Plagiarism. As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean of Science.

Unauthorized Co-operation or Collaboration. Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis". For this course, the following holds:

Students are NOT allowed to collaborate on assignments. Please avoid using search engines to look for answers etc. Just a word of caution - in theoretically oriented courses, it is important to come up with your own ideas for the proof/an algorithm/a contradiction/etc. Sometimes these are like logical puzzles - if somebody tells you a solution then they are trivial and hard part is to come up with a solution. What we want to learn is how to solve them ourselves.
Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams/tests.
Penalties for academic offences can be found on the ODS webpage: https://science.carleton.ca/academic-integrity/.

Announcements:

This is the very first offering of this course! I will seek your advise in terms of any particular algorithms that you will like to see in this course.
All communications will be done via cuLearn forums. If you have a question that may benefit the whole class, please post it in the forum or ask during the class/office hour. (The discussion that are of private nature can be done by sending me an e-mail.)
I am planning to take online lectures twice a week. Once I know the time zones of all the students, we will draw up a lecture schedule. Online lectures will be recorded (subject to all the technological issues involved). I am planning to make the recordings available on cuLearn. They won't be made available on any other outlets. You need a cuLearn account to access them. Please do not post or resend the links to the recorded video to anybody (thanks).
During the online lectures we will post quizzes. You are expected to answer them in the allocated time limit. If we are not able to find a suitable time to hold the lectures, we will find some alternative mechanism to host the quizzes.
I am planning to hold my office hours immediately after the online lectures.
I am new to online lectures and there will be several bumps! I am still hoping that you will appreciate the beautiful algorithmic techniques.
For uOttawa students: Please try to figure out how to obtain the cuLearn account. (I can't help you with the administrative aspect - please contact graduate and departmental administrators.)
For your benefit I will be posting some of the videos from COMP 3801 class. Those are gentle introduction to a subset of the topics in this course. The reason for posting them is that you may review them beforehand to get somewhat familiar with the contents and the style of this course. This course will be at a much faster pace. We will cover significantly more and advanced material. Think of the COMP 3801 videos as the background preparation.
Learn (La)TeX as soon as possible - will help you to write your thesis later!