... somewhere something incredible is waiting to be known.

Foundations of Algorithm Design and Machine Learning (CS60020)

Instructor: Sourangshu Bhattacharya

TAs: Nikhil Kumar Singh, Paramita Koley and Soumi Das

Class Schedule: Monday (12 - 12:55 pm) , Tuesday (10:00 - 11:55 am) , Thurs(8:00 - 8:55 am)

Classroom: NC-231

Website: http://cse.iitkgp.ac.in/~sourangshu/coursefiles/cs60050_19S.html

Past course website: http://cse.iitkgp.ac.in/~sourangshu/coursefiles/cs60050_18S.html

Moodle: https://10.5.18.110/moodle/ (accessible only from inside institute network)

First Meeting: Thursday, 7th January 2019, at 12:00 am in NC-231.


Lecture schedule and Notes:

Introduction: Introductory class on 7th Jan. slides

Algorithms track:

Lecture

Date

Topic

1

10/1

Insertion sort slides

2

14/1

Guest lecture by Prof. Saurabh Bagchi

3

17/1

Order Notation slides

4

21/1

Divide and Conquer - Mergesort slides

5

24/1

Divide and Conquer - Powering, Binary Search, Master Theorem slides

6

28/1

Divide and Conquer - Fibonacci numbers, Strassen's algorithm, Subarray sum slides

7

31/1

Divide and Conquer - Strassen', Proof of Master Theorem. slides

8

4/2

Same as above

9

7/2

Quicksort and Analysis slides

10

11/2

Same as above.

11

14/2

 

12

28/2

 

13

4/3

 

14

7/3

 

15

11/3

 

16

14/3

 

17

18/3

 

18

21/3

 

19

25/3

 

20

28/3

 

21

1 / 4

 

22

4/4

 

23

8/4

 

24

11/4

 

Machine Learning track:

Lecture

Date

Topic

1

8/1

Regression, overfitting and regularisation. slides

2

15/1

Guest lecture by Prof. Saurabh Bagchi

3

22/1

Fisher's linear discriminant, Logistic Regression, Naive Bayes. slides

4

29/1

Non-parametric classifier, k-NN, Decision trees slides

5

5/2

Bagging, Random forests. slides

6

12/2

Boosting, Support vector machines. slides

7

5/3

RNNs, LSTM – applications.

8

12/3

CNNs – applications.

9

19/3

Attention models, Auto encoders.

10

26/3

Probabilistic models – Naïve bayes, CRFs, HMMs, etc.

11

2/4

Clustering – latent variable models.

12

9/4

Online learning, Stochastic gradient descent.

13

16/4

Multi-task and transfer learning.

 

 

 


Syllabus:
Algorithms for data Science:
Introduction to the design and analysis of efficient algorithms, with an emphasis on data science
Notion of time and space complexity and order notation.
Lists. Hashing.
Graph and Basic graph algorithms: Definitions and representation, Reachability, Shortest path.
A brief exposure to Divide and Conquer and Dynamic programming
Introducing the concept of NP-completeness- basic notions
Introduction to randomized algorithms and approximation algorithms.
Notion of sub-linear algorithms, streaming algorithms, sampling
Foundations of Machine Learning:
Introduction. Concept learning. Hypothesis space. Inductive Bias. Learnability. Underfitting and overfitting.
Feature Selection, Dimension Reduction
SVM and introduction to kernel methods.
Unsupervised and semi-supervised learning. Expectation maximization. Mixture of Gaussians.
Active learning, Learning with Imbalanced Data. Anomaly detection.
Ensemble methods.
A brief introduction to graphical models
Introduction to Deep Learning


Assignments:


Textbooks:

  • Introduction to Algorithms by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein
  • Introduction to Machine Learning by Ethem Alpaydin