BAMU TY AI & ML syllabus

BAMU · Third Year B.E./B.Tech Artificial Intelligence and Machine Learning · NEP 2020

Design and Analysis of Algorithms

PCCT-3 · Semester V · 3 credits · CIA 40 + SEE 60

All notes for this subject
  1. Module 1: Introduction; Analysis Framework

    15 hours

    What makes a good algorithm, space and time complexity, big-O, omega and theta, best, worst and average cases; analysing loops and conditionals; setting up recurrences and solving them by substitution and recursion trees.

    Examined in the 60-mark end-semester paper

    • What makes a good algorithm
    • Space and time complexity
    • Asymptotic notations: big-O, omega and theta
    • Best, worst and average-case analysis
    • Analysing non-recursive algorithms
    • Recurrences: substitution and recursion-tree methods
  2. Module 2: Divide and Conquer and Greedy Techniques; Dynamic Programming

    15 hours

    Divide and conquer and its master recurrence, merge sort, quick sort and Strassen's multiplication; the greedy method, fractional knapsack, Huffman coding and minimum spanning trees; dynamic programming — 0/1 knapsack, LCS, matrix chain multiplication, Bellman–Ford, Floyd–Warshall and optimal BSTs — compared with greedy.

    Examined in the 60-mark end-semester paper

    • Divide and conquer and the master theorem
    • Merge sort and quick sort analysis
    • Strassen's matrix multiplication
    • Greedy method: fractional knapsack and Huffman coding
    • Minimum spanning trees: Prim's and Kruskal's
    • Dynamic programming: 0/1 knapsack and LCS
    • Matrix chain multiplication and optimal BSTs
    • Shortest paths: Bellman-Ford and Floyd-Warshall
  3. Module 3: Graph Algorithms and Advanced Search Techniques

    15 hours

    BFS, DFS and topological sorting; Dijkstra's algorithm with priority queues; backtracking and state-space trees for N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO and least-cost search, and the travelling salesperson problem.

    Examined in the 60-mark end-semester paper

    • BFS, DFS and topological sorting
    • Dijkstra's algorithm with priority queues
    • Backtracking and state-space trees
    • N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
    • Branch and bound: FIFO and least-cost search
    • Travelling salesperson by branch and bound

Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).