RTMNU · Third Year B.Tech Computer Science & Engineering · NEP 2020
Design & Analysis of Algorithm
BCSE6T21 · Semester VI · 2 credits · College 30 + university 70
2 credits in the scheme table (2 lecture hours a week; the course page lists 3), with its own 2-hour lab.
Unit 1: Introduction to Algorithms, Asymptotic Analysis and Sorting Techniques
7 hoursAlgorithms and their properties; 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
- Asymptotic notation: Big-O, Omega and Theta
- Recurrences: substitution, iteration and recursion tree
- Recurrence relations and their solution
- The master method
- Analysis of selection and insertion sort
- Amortised analysis
- 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 method applied to job sequencing with deadlines, the knapsack problem, optimal merge patterns and Huffman codes.
Examined in the 70-mark end-semester paper
- Analysis of binary search
- Quick sort
- Merge sort
- Heap sort
- Strassen's matrix multiplication
- Finding maximum and minimum by divide and conquer
- Activity selection and job sequencing
- Optimal merge patterns and 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, the travelling-salesman problem, Bellman–Ford single-source and Floyd–Warshall all-pairs shortest paths.
Examined in the 70-mark end-semester paper
- Multistage graphs
- Longest common subsequence
- Matrix chain multiplication
- Optimal binary search trees
- 0/1 knapsack
- Travelling salesperson by dynamic programming
- Bellman-Ford algorithm
- Floyd-Warshall all-pairs shortest paths
Unit 4: Basic Traversal and Search Techniques and Backtracking
8 hoursBreadth-first and depth-first search and connected components; backtracking — the basic strategy, the N-queens problem (4 and 8 queens) and its analysis, graph colouring and Hamiltonian cycles.
Examined in the 70-mark end-semester paper
- Graph traversal: DFS and BFS
- Connected components with BFS and DFS
- Backtracking
- N-queens problem
- Graph colouring by backtracking
- Hamiltonian cycles by backtracking
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).