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) — extracted question text · 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. Check the original PDF for equations, diagrams and complete wording. Extracted: 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