Fall 2017

Regular (Weekly) Office Hours: Monday 11:45 AM to 12:45PM

Bi-Weekly Office Hours (Only for Project Meetings): Tuesday & Friday 10:00-11:30 AM

TA will be located in Room HP 4125

- 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
- Chapter on Matrices for CS in My Notes on Topics in Algorithm Design

- 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

(We will likely cover parts of MMDS Chapters 3, 4, 5, 7, 8, 9, 11,
and possibly 10 and 6.)

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

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

Frequent Itemset

and

some probability+linear algebra as and when required.

Grading Scheme: (Tentative)

- 3 Assignments: 15% (Assignment 1: PDF-File TeX-File)

- Mid-Term: 10%

- Final Exam: 20%

- Quiz (during the class on several occasions): 9%

- Project: 46% (Breakdown: Bi-weekly Progress Meetings with the TA (6%); Summary Presentation (5%); Report (18%); Seminar(17%))

A typical project will involve - some theoretical work and some prototype implementation. First, the students will submit a project proposal (1-2 page) 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. It should have the breakdown of the whole project in terms of bi-weekly goals. Your proposal is due on October 4th. On October 11th, you will give a 4 minute talk to the class on what is your project about, what you have done so far, and what remains to be done. For this you will provide at most three slides (pdf file) 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 4-6 pages)). The Seminar will be approximately for 15-18 minutes, where you will describe the class your project in some 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 4-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.

To ensure and to guide you with respect to all aspects of the project, you will be setting mandatory bi-weekly meetings with the TA. He will monitor your progress as well as assist you with your conceptual/technical questions. Note that he is not there for fixing bugs in your code. Also the instructor is there to help you with the theoretical content, as sometimes they may be daunting on the first sight!

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 20:

Sept 25:

Oct 02: A1 Due

Oct 09: Thanksgiving

Oct 30:

Nov 01: Mid-Term

Dec 04:

Dec 06:

Dec 08:

Final Exam: Date will be announced by Examination Office.

Project Schedule:

Title |
Group |
Bi-weekly Meeting Schedule |
Report Due Date |
Presentation Date |

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

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.

Sep 07:

Sep 14:

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. 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.

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

**Project meeting dates are:**1st Meeting: Week of Sept 18-22

2nd Meeting: Week of Sept 25-28

3rd Meeting: Week of Oct 16-20

4th Meeting: Week of Oct 30-Nov 3

5th Meeting: Week of Nov 13-18

6th Meeting: Week of Nov 20-25

- Assignment 1 is posted.