RTMNU SY Computer Engg syllabus

RTMNU · Second Year B.Tech Computer Engineering · NEP 2020

Design & Analysis of Algorithm

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

All notes for this subject
  1. Unit 1: Introduction

    7 hours

    Algorithms and examples; the tournament method; evaluating polynomial functions and pre-processing of coefficients; solving recurrence equations; asymptotic notation and complexity.

    Examined in the 70-mark end-semester paper

    • Asymptotic notation: Big-O, Omega and Theta
    • Growth of functions
    • Recurrences: substitution, iteration and recursion tree
    • Tournament method for the largest and second-largest element
    • Polynomial evaluation: Horner's rule and preprocessing of coefficients
  2. Unit 2: Divide & Conquer and Greedy Approaches

    8 hours

    The divide-and-conquer method and Strassen's matrix multiplication; the greedy method, Huffman codes, minimum spanning trees, Dijkstra's algorithm, the knapsack problem and job sequencing with deadlines.

    Examined in the 70-mark end-semester paper

    • Divide and conquer
    • Strassen's matrix multiplication
    • The greedy method
    • Optimal merge patterns and Huffman coding
    • Kruskal's and Prim's minimum spanning trees
    • Dijkstra's single-source shortest paths
    • Fractional knapsack
    • Activity selection and job sequencing
  3. Unit 3: Dynamic Programming Approaches

    8 hours

    Dynamic programming: the knapsack problem, matrix-chain multiplication, longest common subsequence, multistage graphs, all-pairs shortest paths, optimal binary search trees and the travelling salesman problem.

    Examined in the 70-mark end-semester paper

    • Dynamic programming
    • 0/1 knapsack
    • Matrix chain multiplication
    • Longest common subsequence
    • Multistage graphs
    • Floyd-Warshall all-pairs shortest paths
    • Optimal binary search trees
    • Travelling salesperson by dynamic programming
  4. Unit 4: Amortization

    7 hours

    Randomised algorithms of the Las Vegas and Monte Carlo types; randomised quick sort and its analysis; the min-cut algorithm; amortised analysis.

    Examined in the 70-mark end-semester paper

    • Randomised algorithms: Las Vegas and Monte Carlo
    • Randomised quick sort and its analysis
    • Karger's min-cut algorithm
    • Amortised analysis
  5. Unit 5: NP Problems

    6 hours

    NP-hard and NP-complete problems and reducibility, with vertex cover, 3-CNF satisfiability, clique, Hamiltonian cycle and TSP; approximation algorithms for vertex cover and TSP.

    Examined in the 70-mark end-semester paper

    • P, NP and NP-complete problems
    • NP-completeness reductions: vertex cover, 3-CNF SAT, clique and Hamiltonian cycle
    • Approximation algorithms: vertex cover and TSP

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