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

Foundations of Algorithm Design and Machine Learning (CS60020)

Instructor: Sourangshu Bhattacharya

Class Schedule: Mon(10:10:55) , Wed(8:00-09:55) , Thurs(10:00-10:55)

Classroom: CSE-119

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, 3rd January 2018, at 9:00 am in CSE-119.

Assignments:

Lecture Notes:

Introduction: slides
Algorithms track:

  • Lecture 1: Insertion sort (slides)
  • Lecture 2: Merge sort, Analysis (slides)
  • Lecture 3: Divide and Conquer, Fibonacci numbers, Strassen's Algorithm (slides)
  • Lecture 4: Strassen's algorithm (slides)
  • Lecture 5: Proof of Master's Theorem (slides)
  • Lecture 6: Quicksort, Analysis (slides)
  • Lecture 7,8: Randomized analysis of quicksort, Heap and Heap sort (slides)
  • Lecture 9,10: Lower bound on comparison sort, Radix sort (slides)
  • Lecture 11,12: Hashing (slides)
  • Lecture 13,14: Balanced binary search trees (slides)
  • Lecture 15: Dynamic programming (slides)
  • Lecture 16,17: Greedy and Graph algorithms (slides)
  • Lecture 18: Shortest path - Dijkstra'a Algorithm (slides)
  • Lecture 19: Shortest path - Bellman and Ford (slides)
  • Lecture 20: All pair shortest path (slides)
Machine Learning track:
  • Lecture 1: Concept learning, Non-noisy finite hypothesis class, candidate elimination. (slides)
  • Lecture 2: VC-dimension, Regression, Overfitting and regularisation. (slides)
  • Lecture 3, 4, 5, 6: Bias-variance decomposition, Model selection, Least-squares classification, Fisher's Linear Discriminant, Logistic Regression, Multi-class linear classification, Naive Bayes, k-NN, Decision-tree. (slides)
  • Lecture 7,8: Bagging, Random forests, Boosting. (slides)
  • Lecture 9,10: Support vector Machines, Kernel methods (slides)
  • Lecture 11,12,13: Neural Networks, Backpropagation, CNN, RNN. (slides)
  • Lecture 14: Autoencoders, Attention models. (slides)

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

Textbooks:

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