RTMNU TY CSE (DS) syllabus

RTMNU · Third Year B.Tech Computer Science & Engineering (Data Science) · NEP 2020

Design & Analysis of Algorithm

BDS6T20 · Semester VI · 3 credits · College 30 + university 70

  1. Unit 1: Introduction to Algorithms, Asymptotic Analysis, and Sorting Techniques

    7 hours

    Properties of algorithms; recurrence relations solved by the characteristic equation and the master theorem; asymptotic notation and worst-, average- and best-case analysis of insertion, selection and bubble sort; amortised analysis and its applications; the bitonic sorting network.

    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 Strategies and Greedy Approach

    7 hours

    Binary search, quick sort, merge sort, heap sort, Strassen's matrix multiplication and the min–max algorithm; greedy job sequencing with deadlines, knapsack, optimal merge patterns and Huffman codes.

    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 and its Strategies

    8 hours

    The basic strategy; multistage graphs, forward and backward; longest common subsequence, matrix-chain multiplication and optimal binary search trees; 0/1 knapsack; the travelling salesperson problem; Bellman–Ford single-source and Floyd–Warshall all-pairs shortest paths.

    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: Basic Traversal and Search Techniques and Backtracking

    8 hours

    Breadth-first and depth-first search and connected components; backtracking, the N-queens problem (4 and 8 queens) and its analysis, 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

    7 hours

    Basic concepts, non-deterministic algorithms, NP-hard and NP-complete problems, Cook's theorem, decision and optimisation problems and NP-hard graph problems.

    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).