RTMNU · Third Year B.Tech Artificial Intelligence & Data Science · NEP 2020
Design and Analysis of Algorithms
BAD5T17 · Semester V · 3 credits · College 30 + university 70
Unit 1: Mathematical Foundations and Analysis
Summations, finding complexity from code, worst and average cases, asymptotic notations, analysis of searching and sorting, recurrences solved by the characteristic equation, and amortised analysis.
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
Unit 2: Divide and Conquer and the Greedy Method
Binary search, quick, merge and heap sort and Strassen's multiplication; the greedy method for fractional knapsack, job sequencing with deadlines, minimum spanning trees and single-source shortest paths.
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
Unit 3: Dynamic Programming
Multistage graphs, all-pairs and single-source shortest paths, the travelling salesperson problem, longest common subsequence, 0/1 knapsack and chain matrix multiplication.
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
Unit 4: Traversal, Search and Backtracking
Breadth-first and depth-first search; backtracking for N-queens, 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
Unit 5: NP-Hard and NP-Complete Problems
Non-deterministic algorithms, NP-hard and NP-complete problems, graph problems, Cook's theorem, decision and optimisation problems and polynomial reduction.
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).