RTMNU SY AI syllabus

RTMNU · Second Year B.Tech Artificial Intelligence · NEP 2020

Design and Analysis of Algorithms

BAI4T13 · Semester IV · 3 credits · College 30 + university 70

All notes for this subject
  1. Unit 1: Mathematical Foundations

    8 hours

    Bounding summations by integration, analysing control structures, worst- and average-case analysis, asymptotic notations, insertion sort, recursion and recurrence relations solved by the characteristic equation, and amortised analysis.

    Examined in the 70-mark end-semester paper

    • Best, worst and average-case analysis
    • Asymptotic notations: big-O, omega and theta
    • Analysing non-recursive algorithms
    • Recurrences: substitution and recursion-tree methods
    • Solving recurrences by the characteristic equation
    • Amortised analysis
  2. Unit 2: Divide and Conquer; Greedy Method

    8 hours

    Binary search, quick sort, merge sort and heap sort by divide and conquer; the greedy method for the fractional knapsack, job sequencing with deadlines, minimum-cost spanning trees and single-source shortest paths.

    Examined in the 70-mark end-semester paper

    • Merge sort and quick sort analysis
    • Greedy method: fractional knapsack and Huffman coding
    • Job sequencing with deadlines
    • Minimum spanning trees: Prim's and Kruskal's
    • Dijkstra's algorithm with priority queues
  3. Unit 3: Dynamic Programming

    8 hours

    Multistage graphs, all-pairs and single-source shortest paths, the travelling salesman problem, longest common subsequence, the 0/1 knapsack and matrix-chain multiplication.

    Examined in the 70-mark end-semester paper

    • Multistage graphs
    • Shortest paths: Bellman-Ford and Floyd-Warshall
    • Travelling salesperson by dynamic programming
    • Dynamic programming: 0/1 knapsack and LCS
    • Matrix chain multiplication and optimal BSTs
  4. Unit 4: Traversal, Search and Backtracking

    6 hours

    Breadth- and depth-first search; the backtracking strategy for the N-queens problem, graph colouring and Hamiltonian cycles.

    Examined in the 70-mark end-semester paper

    • BFS, DFS and topological sorting
    • Backtracking and state-space trees
    • N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
  5. Unit 5: NP-Hard and NP-Complete Problems

    6 hours

    Non-deterministic algorithms, NP-hard and NP-complete problems, Cook's theorem, decision and optimisation problems and polynomial reduction.

    Examined in the 70-mark end-semester paper

    • P, NP and NP-complete problems
    • Cook's theorem and polynomial-time reduction

Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).