RTMNU · Second Year B.Tech Artificial Intelligence & Machine Learning · NEP 2020
Design and Analysis of Algorithms
BAM4T13 · Semester IV · 3 credits · College 30 + university 70
Unit 1: Introduction to Algorithms
7 hoursGrowth of functions, asymptotic notations, recurrence relations and the master theorem.
Examined in the 70-mark end-semester paper
- Space and time complexity
- Asymptotic notations: big-O, omega and theta
- Recurrences: substitution and recursion-tree methods
- Divide and conquer and the master theorem
Unit 2: Divide and Conquer
7 hoursMerge sort, quick sort, binary search and Strassen's matrix multiplication.
Examined in the 70-mark end-semester paper
- Merge sort and quick sort analysis
- Sequential and binary search
- Strassen's matrix multiplication
Unit 3: Greedy Algorithms
7 hoursHuffman coding, Kruskal's and Prim's algorithms and Dijkstra's algorithm.
Examined in the 70-mark end-semester paper
- Greedy method: fractional knapsack and Huffman coding
- Minimum spanning trees: Prim's and Kruskal's
- Dijkstra's algorithm with priority queues
Unit 4: Dynamic Programming
8 hoursThe Fibonacci series, longest common subsequence, matrix-chain multiplication and the Floyd–Warshall algorithm.
Examined in the 70-mark end-semester paper
- Dynamic programming
- Dynamic programming: 0/1 knapsack and LCS
- Matrix chain multiplication and optimal BSTs
- Shortest paths: Bellman-Ford and Floyd-Warshall
Unit 5: NP-Completeness
7 hoursP and NP problems, NP-completeness and approximation algorithms.
Examined in the 70-mark end-semester paper
- P, NP and NP-complete problems
- Approximation algorithms
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).