B.E Artificial Intelligence and Machine Learning Advanced Algorithms Syllabus - Mumbai University

This is the Third Year AI-ML syllabus under REV-2019 'C' Scheme, in force from the academic year 2022-23. The University has not yet published an NEP 2020 syllabus for this year of the degree, and this is the scheme its examinations are set on.

Loading syllabus...

Syllabus for Advanced Algorithms

Semester 5 · Third Year AI-ML

Module 1: NP and Computational Intractability

1.1 Polynomial-Time Reductions, NP Completeness: Overview, Class P– Class NP NP Hardness, NP Completeness, Cook Levine Theorem, Characteristics of NP Complete Problems, The Satisfiability Problem, NP-Complete Problems, Sequencing Problems Partitioning Problems, Graph Coloring, Numerical Problems, Co-NP and the Asymmetry of NP, A Partial Taxonomy of Hard Problems. Reduction of standard NP Complete Problems: SAT, 3SAT, Clique, Vertex Cover, Set Cover, Hamiltonian Cycle.

Module 2: Approximation Algorithms

Approximation algorithms for known NP hard problems, Inapproximability, Approximation algorithms with small additive error: Edge Coloring, Bin Packing, Randomized rounding and linear programming, Problems having polynomial approximation schemes, Optimization problems with constant factor approximations, Hard-to-approximate problems, Analysis of Approximation Algorithms.

Module 3: Randomized Algorithms

3.1 Introduction to randomized algorithm, Finding the Global Minimum Cut, Random Variables and Their Expectations, A Randomized Approximation Algorithm for MAX 3-SAT, Randomized Divide and Conquer: Median Finding and Quicksort, Hashing: A Randomized Implementation of Dictionaries, Finding the Closest Pair of Points: A Randomized Approach, Randomized Caching, Chernoff Bounds, Load Balancing, Packet Routing, Las Vegas Algorithm, Monte Carlo Algorithm.

Module 4: Local Search

4.1 The Landscape of an Optimization Problem, The Metropolis Algorithm and Simulated Annealing, An Application of Local Search to Hopfield Neural Networks, Maximum-Cut Approximation via Local Search, Choosing a Neighbour Relation, Classification via Local Search, Best-Response Dynamics and Nash Equilibria.

Module 5: String and Amortized Analysis

5.1 String Sort, Tries, Substring Search, Regular Expressions, Data Compression, String Matching Algorithms: Introduction to String matching, The Knuth Morris-Pratt algorithm, Aho- Korasik algorithm, Z-algorithm, Amortized Analysis: Aggregate analysis, The accounting method, The potential method Dynamic tables.

Module 6: Combinatorial Analysis

6.1 Introduction, Next subset of n-Set problems, Random Subset of n Set problems, Sequencing, Ranking and selection algorithms for general combinatorial families.

Useful Links

1 Jon Kleinberg, Eva Tardos, ―Algorithm Design‖, Cornell University, Pearson Publications
2 Robert Sedgewick, Kevin Wayne, ―Algorithms‖, Princeton, FOURTH EDITION, Addison Wessely.
3 Thomas H. Cormen , Charles E., Ronald l., Clifford Stein, ―Introduction to Algorithms‖, Third Edition, The MIT Press Cambridge.
4 Albert Nijenhuis, Herbert Wilf, ―Combinatorial Algorithms for computers and calculators‖, Second edition, Academic Press
5 George Heineman, Gary Pollice, Stanley Selkow, ―Algorithms in a Nutshell‖, Oreilly Press. rd
1 Anany Levitin, Introduction to The design and analysis of algorithms, 3 Edition, Pearson publication.
2 Peter J. Cameron, ―Combinatorics: Topics, Techniques, Algorithms‖, Cambridge University Press
1 https://www.binghamton.edu/watson/continuing-education/data-science/advanced-algorithms .html 2 https://nptel.ac.in/courses/106104019 3 https://www.coursera.org/learn/advanced-algorithms-and-complexity 4 https://onlinecourses.swayam2.ac.in/cec20_cs03/preview *Suggestion: Laboratory work based on the above syllabus can be incorporated as a mini project in CSM501: Mini-Project.

Reproduced from the University of Mumbai syllabus for B.E. (Artificial Intelligence and Machine Learning) under REV-2019 'C' Scheme, in force from the academic year 2022-23. Wording is as printed in that syllabus. Module numbering is as printed there too.

The complete syllabus

This subject is cut from the University circular for its year. Open a document here if you want the whole thing rather than a single subject.

PDF 7.8 (R-A) B.E. (Artificial Intelligence and Machine Learning) Sem I & II (Revised, NEP 2020) NEP 2020 syllabus Read full PDF Read

PDF 6.21 (N) B.E. (Artificial Intelligence and Machine Learning) Sem III & IV (NEP 2020) NEP 2020 syllabus Read full PDF Read

PDF 6.42 (R) B.E. (Artificial Intelligence and Machine Learning) Third Year, Sem V & VI (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read

PDF B.E. (Artificial Intelligence and Machine Learning) Fourth Year, Sem VII & VIII (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read

Report or request