Fall 2017

- Mining of Massive Datasets (MMDS) by Leskovec, Rajaraman, Ullman (2nd Edition, Cambridge University Press, 2014)
- Discrete Structures for Computer Science: Counting, Recursion, and Probability by Michiel Smid
- My Notes on Topics in Algorithm Design

General References:

- Algorithm Design: Kleinberg and Tardos, Addison-Wesley.
- Networks, Crowds, and Markets: Reasoning About a Highly Connected World, By David Easley and Jon Kleinberg
- Networks, An Introduction: Newman.

- Web-page of the text
book: http://www.mmds.org/

- Statistics 110:Probability Video Lectures from Harvard
- 18.06 Introduction to Linear Algebra by Gilbert Strang
- Networked Life: 20 Q & A by Mung Chiang, Cambridge
- LaTeX
- IPE

Useful References related to various topics:

- Linear Algebra:

- Eigenvalues (1 2)
- Video
Lectures and the book of
Gilbert Strang

- PageRank:
- Page Rank
- Original paper by Brin and Page on PageRank: The anatomy of a large-scale hypertextual web search engine (1998).
- What
can you do with a web in your pocket by Brin, Motwani,
Page and Winograd.

- Link to the TED talk of Cedric Villani on "What's so sexy about Math" and the description of PageRank.

- Probability:

Topics

Some combination of the following topics:

Link Analysis

Finding Similar Items - Locality Sensitive Hashing

Mining Data Streams - Frequency and Moment Estimates

Advertising on the web - Adwords & Online matching.

Mining Social Networks - Community Detection, Partitioning of
Graphs, Dynamic Graph Algorithms, ...

Recommendation Systems - Collaborative Filtering

Dimensionality Reduction - Eigenvalues, PCA, SVD

......

Grading Scheme: TBD

Will involve some combination of Scribing, Assignments, In class tests and quiz(s), Seminar/Presentation/Project.

Sept 06:

Introductory remarks. What to expect. A quick summary of some of the topics that we will cover.

A bit of Linear Algebra and Probability.

Sept 11:

Sept 18:

Sept 25:

Oct 02:

Oct 09: Thanksgiving

Oct 30:

Nov 01:

Dec 04:

Dec 06:

Dec 08:

Some of the projects from the past offering of
this course:

Fall 17: Music Collaboration
Graph; Counting Distinct
Elements in Streams; Finding Regions
of Interest in Images; Predicting
controversy of a Wikipedia Article

What follows below are the
contents from the 1st offering of this course from Fall 2016.
The format will likely change this term as we have over 20
students registered in the course:

- It may change a bit during the term.

- Tentatively: Assignments (7.5(A1)+7.5(A2)+10(A3)=25%), Participation (10%), Project (50% = 7.5% Proposal; 7.5% Interim Presentation; 20% Report; 15% Seminar), Quiz (15%)

Assignment 1 (PDF FILE LaTeX File)

Assignment 2 (PDF-File LaTeX-File)

Assignment 3 There are two parts to this assignment.

Part 1: Take any four topics from the course - list what was the main idea and what were the main techniques used in your opinion for each of these topics.

Part 2: Do the same thing as Part 1 for the seminar/projects. Pick any two seminars (except your own) and highlight what was the main idea and what were the main techniques used.

The whole assignment should not exceed 3 pages. Think of writing two paragraphs for each topic - one paragraph highlighting the main idea and the other one highlighting the main technique.

- Information on Project: The major
component of this course is an individual project on one of
the topics/themes related to this course. For getting some
project ideas look into http://www.mmds.org/ and specifically
in CS 246 and CS 341 course web-pages. Also the three
books on Networks listed in Useful References are good source
for project ideas. A typical project will involve - some
theoretical work and some prototype implementation. First, the
students will submit a project proposal (2 pages) consisting
of well-defined problem statement, appropriate references,
some idea on what kind of theoretical research/analysis is
required, what will likely be implemented, some idea on how
testing data will be collected, what kind of results are
expected, and a time line. Your proposal is due on September
30th. On November 2nd, you will give a 5-7 minute talk to the
class about what is your project about, what you have done so
far, and what remains to be done. For this you will provide a
few slides and the presentation will be done in the class.
This will be followed by a Project report and a seminar in
late November/Early December. Project Report will
provide details on all aspect of the project (Problem
Statement, Background Work, Theoretical Analysis, Experimental
Design and Analysis, Conclusions, and References (about 8-10
pages)). The Seminar will be approximately for
20-25 minutes, where you will describe the class your project
in detail. It is expected that you will make a formal
presentation about your project in this seminar. Also, you
will be asked to prepare a set of 5-6 quiz problems based on
your seminar. Your formal presentation is due one week before
your seminar date including the quiz problems. Your project
report is due a couple of days before your seminar date.
All these deadlines are fairly strict due to the nature of
this course.

Sep 07:

Sep 14:

- Page Rank
- Link to the paper by Brin and Page: The anatomy of a large-scale hypertextual web search engine (1998).
- What
can you do with a web in your pocket by Brin, Motwani, Page
and Winograd.

- Link to the TED talk of Cedric Villani on "What's so sexy about Math" and the description of PageRank.

Sep 23:

Sep 28:

Oct 05:

Oct 07:

Oct 12:

Oct 14:

Oct 19:

Advertising on the web - online algorithms for matching.

Oct 21:

Nov 02:

Nov 04:

Nov 09:

Nov 11:

Nov 16:

Due Date for Assignment 2

Nov 18:

Nov 23:

Nov 25:

Nov 30:

Dec 02:

Dec 07:

The undergraduate advisor for the School of Computer Science is available in Room 5302C HP, by telephone at 520-2600, ext. 4364 or by email at undergraduate_advisor@scs.carleton.ca. The 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 the Writing Tutorial Services.

- Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, they must do so in their own words.
- 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.

You may need special arrangements to meet your academic obligations during the term. For an accommodation request the processes are as follows: