Introduction to Data Analytics/Science
June-July 2018

General References:

• 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
• AMs Notes on Topics in Algorithm Design

• 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:
  
• STAT110 on Youtube
  
• Introduction to Probability book by Blitzstein and Hwang
• Discrete Structures for Computer Science: Counting, Recursion, and Probability by Michiel Smid
• Chapter on Probability in AMs Notes on Topics in Algorithm Design
• Locality Sensitive Hashing
• Chapter 3 in TextBook
• Chapter on LSH in AMs 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
• Adwords
• Chapter on Advertisement on the Web from the Book.
• SVD/Dimensionality Reduction:
• Chapter in the book on Dimensionality Reduction
• Try a few SVDs using Wolfram Alpha.
  

Tentative Topics

Some combination of the following topics:
(Instructors are Listed in [ ] )

Week 0: June  21/22: [AM + AD]

• Introductions, Logistics, What to expect, What is expected.  Review of basic probability/stat theory with applications to finding similar items.
• Software Tools: R & Python and some simple exercises
• Exercise 1:
  

  R Introduction Quiz

  Set seed to 100 using set.seed(100) command. 

  
  

1. Randomly generate 100 numbers with a mean 0 and standard deviation 1 and store these numbers in a vector called `two'
2. What is the expected value of the generated numbers and the actual mean
3. Write a function which takes in a number x and seed y and returns x randomly generated numbers with seed y
4. Write a function which returns the mean median and mode in a vector given a vector inputs
5. Generate 1000 numbers with a mean 0 and stdev 1, and find how many of them are greater than 0.2 with a single command. Store these as a vector called `six'
6. Multiply the vectors `six' by `two' and store results in `tricky' - what is the result and why is there a warning?
7. Install the `housingData' package and store the `fipsCounty' data into a data frame
8. Which state appears the most times?
9. Load the housing data into a dataframe. Which state has the most houses sold, which state has the highest average difference between list and selling price
10. Plot a graph of list and selling price and find the outliers in the data. Does there appear to be a relation and is there a similarity between the outliers

Week 1: June 25-29 [AM + AD]

• Finding Similar Items
• Fingerprint Matching
• Similarity of Sets using Jaccard Distance
  
• Similarity of Bit Strings using Hamming Distance
  
• Exposure to basic probability/stat computations in R/Python + Selecting a Data Set for playing with the tools.
• Probabiliy: Random Variables, Indicator Random Variables, and Linearity of Expectation.
• Balls and Bins
• Birthday Problem
• Coupon Collector Problem
• Introduction to Data Streams
• Finding the Majority Element
• Finding Elements that occur frequently - Count Min Sketch
• Problem Set
• Mid-Term Quiz
  

• Counting Distinct Elements in Data Streams
• Page Rank via Eigenvalue/Eigenvector of Markov Matrix and the concept of Teleportation.
  
• Mid-Term Evaluation - Take Home Probability Exam! 
  
• Solution to the Mid-Term.
  

Week 3: July 9-13 [AD]

         R-Introduction

• R-Studio
• R-Markdown
• Math Operations
• Functions
• Basic Data Structures
• Statistical Features

         Tables and Graphs

• Reading and Cleaning Data
• Plotting Data
• Operations on Tables (Select, Filter, Mutate, Sumarize)
  
• Functions on Vectors and Lists
  

        Linear Regression

• Introduction
  
• Measuring Error
• Gradient Descent
  
• Regression Package in R
• Correlation
• Linear Model
• Multiple Linear Regression
  
• Splitting into training testing sets
• Different regression models, generating features, choosing features
• Different types of regressions and measuring error
• Problems and Drawbacks with Regression

           Classification

Logistic Regression

Decision Trees

Neural Nets

Measuring Error

• Multiple Regression
• Splitting
• Cross Validation
  
• Overfitting                 

Assignment-1

Assignment-2         

Functional Programming in R

Week 4: July 16-19 [SM + AD]

• Processing Spatial Data
• Binary Search Tree
• K-D Trees
  
• Range Searching 
  
• Finding yourself on the map, i.e. Point Location
• July 19: Presentations + Short Report
  

• Using methods discovered/learned during the course, present some interesting findings on small/big datasets.   (Datasets may include  stock prices, house data, DGA strings, etc.) Summarize your findings/observations in a short report. Ensure that the report is not longer than 2-pages: Should consist of a clear problem statement; methodology; findings; your conclusions and observations. Present your findings in a formal seminar (10-12 minutes) during the last lecture. Please form a team of two/three and discuss your project ideas with Aditya/Anil starting in Week 1 so that you can make some substantial progress during your stay at Carleton. Enjoy!
• Please submit a pdf file of your report (Max 2 pages) and of your presentation by July 17th. Only one report per group please.
  
• Note that your presentation is about 10-12 minutes long. One of the members of your group will be picked at random to make the presentation.
  
• All presentations are on July 19th morning.
  

1. Classes from June 21-July 6th will be offered by Anil/Aditya, July 9-13 by Aditya, and July 16-19 by Saeed/Aditya. 
   
2. Exercise 1 is posted
3. Problem Set is posted (Due on 3rd July)
4. Short presentation related to your seminar topic is on Friday June 29th.
5. Mid-Term Quiz - Please email your answers to anil@scs.carleton.ca by 4PM today