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     Aritra Hota   |   Subhash Agrawal

Notices and Announcements

January 01, 2025

There will be an extra 2-hour class on 08-January-2025 (Wednesday) at 5:30pm in CSE-119 (CSE Dept., Ground Floor). An announcement for the same will also be made in the first class (tomorrow).

December 31, 2024

Wish you a very happy new year and semester ahead. Our first class will be on 02-January-2025 (Thursday) at 8:00am. An email with all relevant details will be sent to the registered/admitted students very soon.

December 19, 2024

This course is primarily designed as a CORE course for PGDBA students. However, research scholars (MS and PhD students) are allowed to participate in this course. Except these students, I am unable to admit any other UG or PG student to take part in this course. Hence, all requests from students sent via ERP will remain pending without being approved (and thereby those students are requested to switch into other courses before the subject registration deadline expires).

Tentative Coverage

Module I : Algorithms for Data Science

Topic Details Duration Dates Class-Scribes*
(Daily)		 Additional-Scribes*
(Weekly and Appendix)
Introduction

Problems, Representation, Solution and Landscape

1 hour

02-Jan-2025



23BM6JP06_2025-01-06~10 (Week-1 Summary)





23CS91P01_2025-01-14 (BST and Heap)

24CS72P04_2025-01-16 (Matrix Multiplication)
Algorithm Design and Analysis

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

6 hours

06-Jan-2025
07-Jan-2025
08-Jan-2025
09-Jan-2025
13-Jan-2025

23BM6JP01_2025-01-06
23BM6JP45_2025-01-07
23BM6JP03_2025-01-08
23BM6JP04_2025-01-08
23BM6JP05_2025-01-09
23BM6JP07_2025-01-13
Divide and Conquer Paradigm

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

4 hours

14-Jan-2025
16-Jan-2025
20-Jan-2025

23BM6JP09_2025-01-14
Dynamic Programming

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

3 hours

21-Jan-2025
23-Jan-2025

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 Class-Scribes*
(Daily)		 Additional-Scribes*
(Weekly and Appendix)
Introduction

The Learning Problem
Feasibility of Learning

2 hours

27-Feb-2025
03-Mar-2025

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

2 hour

Unsupervised Learning

Clustering, Semi-Supervised and Active Learning

2 hours

Conclusion

Core Learning Principles

1 hour

* Scribes are unedited class-notes documented by students (and uploaded as it is) based on the class teaching; and hence may contain errors!

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