CS60020 : Foundations of Algorithm Design and Machine Learning Spring 2025

Schedule

Instructor     Aritra Hazra
Timings [Slot: D4]     Monday (12:00-13:00), Tuesday (10:00-12:00), Thursday (08:00-09:00)
Venue     NC-231 (Nalanda Complex)
Teaching Assistants     To be Decided

Notices and Announcements

December 19, 2024

This course is primarily designed as a CORE course for PGDBA students. I do not encourage CSE students (both UG and PG) to take this course. However, research scholars (MS and PhD students) are allowed to participate in this course. Moreover, I may allow (cannot guarantee though!) a few interested non-CSE students to take part in this course, provided that I have capacity to accept and they have not done any Algorithms or any Machine Learning related course earlier. For those non-CSE students, I shall consider requests only through ERP portal till 29-December-2024 and shortlist them (immediately after that) based on their CGPA only (and possibly preferring the final year students).

Tentative Coverage

Module I : Algorithms for Data Science

Topic Details Duration Dates Student-Scribes
(Unedited)
Introduction

Problems, Representation and Solution

1 hour

Algorithm Design and Analysis

Recursive Formulation and Data Structuring
Correctness and Optimality (Problem Lower Bounds)
Efficiency (Time and Space Complexity)

5 hours

Divide and Conquer Paradigm

Searching and Sorting
More Example Problems and Analysis
Master Theorem and Complexity Analysis

5 hours

Dynamic Programming

Classical Example Problems and Analysis
String Matching Algorithms
Memo(r)ization and Complexity Analysis

4 hours

Graph Algorithms

Representation and Traversals
Shortest Paths and Spanning Trees

5 hours

Intractable (Hard) Problems

P, NP and NP-Complete Problems
Problem Reduction and Hardness

3 hours

Solving Hard Problems
(Combinatorial Optimization)

Approximation and Randomized Algorithms
Heuristic Search and Branch-and-Bound Approach
Constraint Satisfaction and Local Search
Simulated Annealing and Genetic Algorithms

4 hours



Module II : Foundations of Machine Learning

Topic Details Duration Dates Student-Scribes
(Unedited)
Introduction

The Learning Problem
Feasibility of Learning

2 hours

Decision Tree Learning

Boolean Concept Learning and Version Space
Entropy Measures and Gains, Gini Index and Impurity
Hypotheses Space and Inductive Bias, Occam's Razor

2 hours

Linear Models

Classification and Regression
Non-linear Transformation
Logistic Regression

2 hours

Artificial Neural Networks

Perceptrons and Multi-Layer Neural Networks
Back-propagation and Gradient Descent
Deep Learning Architectures

2 hours

Support Vector Machines

Primal-Dual Optimization and Soft Margin
Kernels and Radial Basis Function
Dimensionality Reduction (Principal Component Analysis)

3 hours

Performance Evaluation

Accuracy, Precision, Recall, F-Score and ROC
Sampling and Bootstraping
Hypotheses Testing and Cross-Validation

1 hour

Learning Theory

Error and Noise, Training vs. Testing and Validation
Generalization, PAC Learnability and VC Dimensions
Bias and Variance, Overfitting and Regularization

5 hours

Bayesian Learning

MLE and MAP, Naive Bayes and Gaussian Naive Bayes
Expectation-Maximization Algorithm
Bayesian Network and Graphical Models

4 hours

Ensemble Learning

Bagging and Boosting
AdaBoost and Random Forest

1 hour

Unsupervised Learning

Clustering, Semi-Supervised and Active Learning

2 hours

Conclusion

Core Learning Principles

1 hour

Books and References

Module I : Algorithms for Data Science
  1. Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Fourth Edition, MIT Press/McGraw-Hill, 2022.
  2. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
  3. Muhammad Hamad Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific Publishers, 2016.
  4. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms, Universities Press, 2008.
  5. Mark Allen Weiss, Data Structures and Algorithm Analysis in C, Pearson Education, 1997.
Module II : Foundations of Machine Learning
  1. Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th Global Edition, Pearson, 2022.
  2. Tom Mitchell; Machine Learning, First Edition, McGraw Hill, 1997.
  3. Yaser S. Abu-Mostafa, Malik Magdon-Ismail, Hsuan-Tien Lin; Learning From Data, First Edition, AML Book, 2012.
  4. Ethem Alpaydin; Introduction to Machine Learning, Fourth Edition, The MIT Press, March 2020.
  5. Christopher Bishop; Pattern Recognition and Machine Learning, First Edition, Springer-Verlag New York, 2006.    [ Open-Access ]

Scribes (Class-Notes by Students)

Projects / Assignments

Examinations

Marks Distribution:   10% Class-Test + 10% Project + 30% Mid-Sem + 45% End-Sem + 5% Scribes