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.
Unit 1: Introduction to Algorithms, Asymptotic Analysis and Sorting Techniques
7 hoursWhat 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
Unit 2: Divide and Conquer Strategies and Greedy Approach
7 hoursDivide 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
Unit 3: Dynamic Programming and its Strategies
8 hoursThe 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
Unit 4: Basic Traversal and Search Techniques and Backtracking
8 hoursBreadth-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
Unit 5: NP-Hard and NP-Complete Problems
7 hoursBasic 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).