RTMNU · Second Year B.Tech Computer Engineering · NEP 2020
Design & Analysis of Algorithm
BCME4T13 · Semester IV · 3 credits · College 30 + university 70
Unit 1: Introduction
7 hoursAlgorithms 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
Unit 2: Divide & Conquer and Greedy Approaches
8 hoursThe 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
Unit 3: Dynamic Programming Approaches
8 hoursDynamic 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
Unit 4: Amortization
7 hoursRandomised 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
Unit 5: NP Problems
6 hoursNP-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).