RTMNU TY CSE syllabus

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

Design & Analysis of Algorithm

BCSE6T21 · Semester VI · 2 credits · College 30 + university 70

2 credits in the scheme table (2 lecture hours a week; the course page lists 3), with its own 2-hour lab.

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

    7 hours

    Algorithms and their properties; 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

    • Asymptotic notation: Big-O, Omega and Theta
    • Recurrences: substitution, iteration and recursion tree
    • Recurrence relations and their solution
    • The master method
    • Analysis of selection and insertion sort
    • Amortised analysis
    • Parallel sorting
  2. Unit 2: Divide and Conquer Strategies and Greedy Approach

    7 hours

    Divide and conquer: binary search, quick sort, merge sort, heap sort, Strassen's matrix multiplication and the min–max algorithm; the greedy method applied to job sequencing with deadlines, the knapsack problem, optimal merge patterns and Huffman codes.

    Examined in the 70-mark end-semester paper

    • Analysis of binary search
    • Quick sort
    • Merge sort
    • Heap sort
    • Strassen's matrix multiplication
    • Finding maximum and minimum by divide and conquer
    • Activity selection and job sequencing
    • Optimal merge patterns and Huffman coding
  3. Unit 3: Dynamic Programming and its Strategies

    8 hours

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

    Examined in the 70-mark end-semester paper

    • Multistage graphs
    • Longest common subsequence
    • Matrix chain multiplication
    • Optimal binary search trees
    • 0/1 knapsack
    • Travelling salesperson by dynamic programming
    • Bellman-Ford algorithm
    • Floyd-Warshall all-pairs shortest paths
  4. Unit 4: Basic Traversal and Search Techniques and Backtracking

    8 hours

    Breadth-first and depth-first search and connected components; backtracking — the basic strategy, the N-queens problem (4 and 8 queens) and its analysis, graph colouring and Hamiltonian cycles.

    Examined in the 70-mark end-semester paper

    • Graph traversal: DFS and BFS
    • Connected components with BFS and DFS
    • Backtracking
    • N-queens problem
    • Graph colouring by backtracking
    • Hamiltonian cycles by backtracking

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