B.E. (Artificial Intelligence and Data Science) Advanced Algorithms Syllabus - Mumbai University
This is the TY BE AI and DS syllabus under CBCS REV-2019 'C' Scheme, in force from the academic year 2022-23. The University has published no NEP 2020 syllabus for Semesters V to VIII of any engineering branch, so this is the scheme you are examined on — exam form 1T01815 and 1T01816. The first and second years of the degree are on NEP 2020.
Loading syllabus...
Syllabus for Advanced Algorithms
The University heads this subject CSDL05012, with a digit zero where the series takes the letter O. Her own Department Optional Course table prints it CSDLO5012.
Module 1 8 hours
- 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 9 hours
- Approximation Algorithms
- 2.1 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 9 hours
- 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 5 hours
- 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 4 hours
- 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 4 hours
- Combinatorial Analysis
- 6.1 Introduction, Next subset of n-Set problems, Random Subset of n-Setproblems, Sequencing, Ranking and selection algorithms for general combinatorial families.
Text Books
- 1 Jon Kleinberg, Eva Tardos, "Algorithm Design", Cornell University, Pearson Publications
- 2 Robert Sedgewick, Kevin Wayne, "Algorithms", Princeton, FOURTH EDITION, AddisonWessely.
- 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.
References
- 1 Anany Levitin, Introduction to The design and analysis of algorithms, 3rd Edition, Pearson publication.
- 2 Peter J. Cameron, "Combinatorics: Topics, Techniques, Algorithms", Cambridge University Press
Useful Links
- 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 Data Science), item 6.42 (R), under CBCS REV-2019 'C' Scheme, in force from the academic year 2022-23. Wording, module numbering and hours are as printed in that syllabus.
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.