RTMNU TY IT syllabus

RTMNU · Third Year B.Tech Information Technology · NEP 2020

Design and Analysis of Algorithm

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

Unit 5 is headed "Blockchain Applications and Challenges" on the course page, but its content is NP-hard and NP-complete problems; it is titled by its content here.

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

    7 hours

    What an algorithm is and its properties; recurrence relations solved by the characteristic equation and the master theorem; asymptotic notation and best-, average- and worst-case analysis of insertion, selection and bubble sort; amortised analysis and the bitonic sorting network.

    Examined in the 70-mark end-semester paper

    • Algorithms and design strategies
    • Recurrence relations and the master theorem
    • Time and space complexity, asymptotic notation
    • Bubble, selection and insertion sort
    • 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 approach applied to job sequencing with deadlines, the knapsack problem, optimal merge patterns and Huffman coding.

    Examined in the 70-mark end-semester paper

    • Linear and binary search
    • Divide and conquer: merge sort and quick sort
    • Heaps and heap sort
    • Divide and conquer matrix multiplication
    • Finding maximum and minimum by divide and conquer
    • Job sequencing with deadlines
    • Greedy: activity selection and fractional knapsack
    • Optimal merge patterns
    • 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 and the travelling salesman problem; single-source shortest paths by Bellman–Ford and all-pairs shortest paths by Floyd–Warshall.

    Examined in the 70-mark end-semester paper

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

    8 hours

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

    Examined in the 70-mark end-semester paper

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

    7 hours

    Basic concepts and non-deterministic algorithms; the classes NP-hard and NP-complete; Cook's theorem; decision and optimisation problems; graph-based NP problems.

    Examined in the 70-mark end-semester paper

    • P, NP, NP-hard and NP-complete problems
    • NP-complete problems, SAT and Cook's theorem

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