Instructor: Anil
Maheshwari Office: HP 5125b E-mail: anil@scs.carleton.ca
Lectures: Lectures are Wednesday
and Fridays at 08:35 to 09:55 AM. See public class schedule
for the location. Office hours: Mondays 08:30-09:45 AM
(HP 5125b)
Please feel free to send me email at anil@scs.carleton.ca
Teaching Assistant:
Details will be posted here.
Course objectives: Algorithmic
design techniques for modern data sets arising in, for example,
data mining, web analytics, epidemic spreads, search engines and
social networks. Topics may include data mining, hashing,
streaming, clustering, recommendation systems, link analysis,
dimensionality reduction, online, social networking, game
theoretic and probabilistic algorithms.
Caution: Note that you need a minimum of B+ in COMP 2804 to
register in this course. The contents of this course are fairly
broad, and will cover a spectrum of techniques from the design and
analysis of algorithms. It is assumed that you have a very good
grasp on the analysis of algorithms (O-notation, recurrences, and
complexity analysis), elementary probability theory including
expectation and indicator random variables (contents of COMP
2804), the knowledge of basic data structures (lists, trees,
hashing), and the knowledge of discrete mathematics (counting,
permutations and combinations, proof techniques:
induction, contradiction, ..). Note that there will not be time to
review these material, and to appreciate the contents of this
course, you must have a very good grasp on these topics.
Arora, Hazan and Kale, The
multiplicative weights update method: a meta-algorithm and
applications, Theory of Computing 8(1): 121-164, 2012.
Chapter 11 in Notes.
Topics
We will likely cover parts of MMDS Chapters 3, 4, 5, 7, 8, 9,
11, and possibly 10 and 6. In addition to this there will
be more material on Data Streaming from some research articles.
In broad terms, some combination of the following topics:
Link Analysis
Mining Data Streams - Frequency and Moment Estimates
Finding Similar Items - Locality Sensitive Hashing
Advertising on the web - Adwords & Online matching
Recommendation Systems - Collaborative Filtering
Dimensionality Reduction - Eigenvalues, PCA, SVD
Clustering - K-Means
Mining Social Networks - Community Detection, Partitioning of
Graphs, Dynamic Graph Algorithms
Frequent Itemset
Online Learning
+ some probability
+ linear algebra as and when required.
Grading Scheme (Tentative):
- 2 Tests: 2 x 15%: Scheduled during the class time slots on October
10 and November 14.
- Final Exam: 25% Scheduled by the Exam Services
- Project: 45%
Written Project Proposal (10%): Due by Oct 1
3-Minute Project Proposal Presentation (5%):
Friday, Oct 3rd Class
End-of-Term presentation on projects (15%):
Scheduled within the last 3-4 weeks of classes.
Project Report (15%): A couple of days before
your end-of-term project presentation.
Outline is as follows:
Pick a topic.
You may look for
papers/citations in recent
proceedings of the conferences
ACM-SIAM Symposium on Discrete
Algorithms conference (SODA),
SIGKDD,
WWW, KDD, Data
Minining and Knowledge
Discovery, WSDM, ICLR, ICML.
Initial Proposal:Submit
one page draft by October 1st.
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. Prepare a 3
minute presentation which will
be heldduring
the class time slot on
October 3rd.
Final
Project Presentation:Presentation is for
approximately 10 minutes duration.
It will be held during last 3-4 weeks of
the course.
Project
Report: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.
Experiments
(in case you performed any simulation etc.)
Conclusions
(Summary + What did you learn? + What do you
think can be done in future?)
References
Report will be
approximately 4 pages long and
will be posted on the course
web-page.
You may
use a double
column format -
for example the
style file from
Canadian
Conference in
Computational
Geometry Style
File from
here:
http://vga.usask.ca/cccg2020/CCCG2020-tex-template.zip
Schedule
of FALL 2025 Term
Sept 03: Introduction +
Online
Learning
Course Logistics
Introduction to
Multiplicative-Weight Update Method
Arora, Hazan and Kale, The
multiplicative weights update method: a meta-algorithm and
applications, Theory of Computing 8(1): 121-164, 2012.
Sep 11: Bloom
Filters (contd.) + Probability Basics
Probability Basics (Sample Space, Random
Variable, Linearity of Expectation, Markov's Inequality) -
Section 2.1+2.2 in Notes and/or COMP 2804 Textbook.
Final Exam: See the Exam
Schedule for Room Location.
Important Considerations:
Late assignments are not accepted. Assignments submissions are
handled electronically 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 your 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.
Undergraduate Academic Advisor:
The Undergraduate Advisor for the School of Computer Science is
available in Room 5302 HP; or by email at
scs.ug.advisor@scs.carleton.ca. The undergraduate advisor can
assist with information about prerequisites and preclusions, course
substitutions/equivalencies, understanding your academic audit and
the remaining requirements for graduation. The undergraduate advisor
will also refer students to appropriate resources such as the
Science Student Success Centre, Learning Support Services and
Writing Tutorial Services.
University Policies
Carleton is committed to providing academic
accessibility for all individuals. Please review the academic
accommodation available to students here: https://students.carleton.ca/course-outline/.
We follow all the rules and regulations set by Carleton
University, Faculty 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.More information and standard sanction guidelines can be
found here: https://science.carleton.ca/students/academic-integrity/.Please note that content generated by an
unauthorized A.I.-based tool *is* considered plagiarized
material.
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.