RTMNU · Second Year B.Tech Artificial Intelligence · NEP 2020
Design and Analysis of Algorithms
BAI4T13 · Semester IV · 3 credits · College 30 + university 70
Unit 1: Mathematical Foundations
8 hoursBounding summations by integration, analysing control structures, worst- and average-case analysis, asymptotic notations, insertion sort, recursion and recurrence relations solved by the characteristic equation, and amortised analysis.
Examined in the 70-mark end-semester paper
- Best, worst and average-case analysis
- Asymptotic notations: big-O, omega and theta
- Analysing non-recursive algorithms
- Recurrences: substitution and recursion-tree methods
- Solving recurrences by the characteristic equation
- Amortised analysis
Unit 2: Divide and Conquer; Greedy Method
8 hoursBinary search, quick sort, merge sort and heap sort by divide and conquer; the greedy method for the fractional knapsack, job sequencing with deadlines, minimum-cost spanning trees and single-source shortest paths.
Examined in the 70-mark end-semester paper
- Merge sort and quick sort analysis
- Greedy method: fractional knapsack and Huffman coding
- Job sequencing with deadlines
- Minimum spanning trees: Prim's and Kruskal's
- Dijkstra's algorithm with priority queues
Unit 3: Dynamic Programming
8 hoursMultistage graphs, all-pairs and single-source shortest paths, the travelling salesman problem, longest common subsequence, the 0/1 knapsack and matrix-chain multiplication.
Examined in the 70-mark end-semester paper
- Multistage graphs
- Shortest paths: Bellman-Ford and Floyd-Warshall
- Travelling salesperson by dynamic programming
- Dynamic programming: 0/1 knapsack and LCS
- Matrix chain multiplication and optimal BSTs
Unit 4: Traversal, Search and Backtracking
6 hoursBreadth- and depth-first search; the backtracking strategy for the N-queens problem, 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
6 hoursNon-deterministic algorithms, NP-hard and NP-complete 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
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).