Design And Analysis Of Algorithm (BCS409) - AKTU Question Paper 2025-26
B.Tech · Semester 4 · Free PDF Download
This is the official AKTU Design And Analysis Of Algorithm Previous Year Question Paper for B.Tech Semester 4, academic session 2025-26. Published by Dr. A.P.J. Abdul Kalam Technical University (AKTU/UPTU), Lucknow. Free PDF download — no login required.
Course:B.Tech
Semester:Semester 4
Session:2025-26
University:AKTU / UPTU
Rate this paper
Questions Asked in 2025-26
Design And Analysis Of Algorithm (BCS409) — complete question paper · 70 marks · 3 Hours
Section AAttempt all questions in brief. 02 x 7 = 14
- aFind Big-O of:f(n) = n³ + 4n log n + 6
- bWhat is the difference between time and space trade-off?
- cWhat is probabilistic balancing in Skip List?
- dWhy is extract-min costly in Fibonacci Heap?
- eDefine Convex Hull in computational geometry
- fDifferentiate between Greedy and Dynamic Programming
- gWhat is Algebraic Computation?
Section BAttempt any three of the following: 07 x 3 = 21
- aExplain the concept of recurrence relations. Solve the recurrence relation using Master Theorem:T(n)=2T(n/2)+n. Also interpret its significance in algorithm efficiency
- bDefine B-Tree. Construct a B-Tree of order 5 by inserting:20, 10, 30, 5, 15, 25, 35, 40, 45. Show all node splits clearly
- cBy considering vertex ‘1’ as source vertex, find the shortest paths to all other vertices in the following graph using Dijkstra’s algorithms. Show all the steps
- dWhat is the Hamiltonian Cycle problem? Describe a backtracking algorithm to solve it and demonstrate its application with a step-by- step example
- eExplain the concept of approximation ratio. Analyze the performance of an approximation algorithm for Vertex Cover problem
Section CAttempt any one part of the following: 07 x 1 = 07
- aWhat is Max Heap property?. Construct a Max Heap from the following elements:[20, 15, 30, 5, 10, 25]. Explain each step clearly
- bCompare comparison-based and non-comparison-based sorting algorithms. Give advantages and limitations of each
- aExplain the structure of Binomial Trees. Prove that a Binomial Tree of degree k has 2^k nodes
- bDefine Red-Black Tree.Prove that a Red-Black Tree with n-internal nodes has height at most (2lg(n+1)). (SEM. IV) THEORY EXAMINATION 2025-26 DESIGN AND ANALYSIS OF ALGORITHM
- aDiscuss Prim’s and Kruskal’s algorithm. Construct minimum spanning tree for the below given graph using Prim’s algorithm (Source node = a)
- bExplain the Divide and Conquer approach with Merge Sort. Analyze its time complexity
- aDefine the Traveling Salesman Problem (TSP) and explain how the Branch and Bound (B&B) technique provides an optimal solution. Using the cost matrix given below, find the minimum-cost Hamiltonian circuit step-by-step, including matrix reduction, lower bound calculation, and construction of the state-space tree. Given distance/cost matrix
- bFind all valid configurations for placing 4 queens on a board using the backtracking algorithm. Start by placing the first queen in the first row and proceed row-by-row
- aExplain why NP-Complete problems are considered intractable. Can all NP problems be solved in polynomial time? Justify
- bCompare Fast Fourier Transform (FFT) and Dynamic Programming approaches for solving computational problems
Question text is extracted from the official AKTU question paper PDF above. Hindi translations are omitted — every question is printed in English in the original paper. Last verified: 2026-08-23.
Design And Analysis Of Algorithm — Other Year Papers
AKTU Design And Analysis Of Algorithm PYQs from other sessions
More B.Tech Semester 4 (2025-26) Papers
Other subjects from same semester and session
Technical Communication2025-26Mathematics Iii2025-26Mathematics Iv2025-26Mathematics V2025-26Cyber Security2025-26Python Programming2025-26Operating System2025-26Theory Of Automata And Formal Languages2025-26
View all B.Tech Semester 4 2025-26 papers →Syllabus & More PYQs
Paper solve karne se pehle unit-wise syllabus dekh lo