RTMNU TY AI & DS syllabus

RTMNU · Third Year B.Tech Artificial Intelligence & Data Science · NEP 2020

Design and Analysis of Algorithms

BAD5T17 · Semester V · 3 credits · College 30 + university 70

  1. Unit 1: Mathematical Foundations and Analysis

    Summations, finding complexity from code, worst and average cases, asymptotic notations, analysis of searching and sorting, recurrences solved by the characteristic equation, and amortised analysis.

    Examined in the 70-mark end-semester paper

    • What makes a good algorithm
    • Solving recurrences by the characteristic equation
    • Divide and conquer and the master theorem
    • Asymptotic notations: big-O, omega and theta
    • Best, worst and average-case analysis
    • Amortised analysis
    • Bitonic sorting networks
  2. Unit 2: Divide and Conquer and the Greedy Method

    Binary search, quick, merge and heap sort and Strassen's multiplication; the greedy method for fractional knapsack, job sequencing with deadlines, minimum spanning trees and single-source shortest paths.

    Examined in the 70-mark end-semester paper

    • Sequential and binary search
    • Merge sort and quick sort analysis
    • Heaps
    • Strassen's matrix multiplication
    • Job sequencing with deadlines
    • Greedy method: fractional knapsack and Huffman coding
    • Optimal merge patterns
  3. Unit 3: Dynamic Programming

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

    Examined in the 70-mark end-semester paper

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

    Breadth-first and depth-first search; backtracking for N-queens, 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

    Non-deterministic algorithms, NP-hard and NP-complete problems, graph 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
    • Non-deterministic algorithms and NP-hard graph problems

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