RTMNU · Third Year B.Tech Computer Science & Engineering (Data Science) · NEP 2020
Design & Analysis of Algorithm
BDS6T20 · Semester VI · 3 credits · College 30 + university 70
Unit 1: Introduction to Algorithms, Asymptotic Analysis, and Sorting Techniques
7 hoursProperties of algorithms; recurrence relations solved by the characteristic equation and the master theorem; asymptotic notation and worst-, average- and best-case analysis of insertion, selection and bubble sort; amortised analysis and its applications; the bitonic sorting network.
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 Strategies and Greedy Approach
7 hoursBinary search, quick sort, merge sort, heap sort, Strassen's matrix multiplication and the min–max algorithm; greedy job sequencing with deadlines, knapsack, optimal merge patterns and Huffman codes.
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 and its Strategies
8 hoursThe basic strategy; multistage graphs, forward and backward; longest common subsequence, matrix-chain multiplication and optimal binary search trees; 0/1 knapsack; the travelling salesperson problem; Bellman–Ford single-source and Floyd–Warshall all-pairs shortest paths.
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: Basic Traversal and Search Techniques and Backtracking
8 hoursBreadth-first and depth-first search and connected components; backtracking, the N-queens problem (4 and 8 queens) and its analysis, 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
7 hoursBasic concepts, non-deterministic algorithms, NP-hard and NP-complete problems, Cook's theorem, decision and optimisation problems and NP-hard graph problems.
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).