This document is a B.Tech (Semester IV) Theory Examination Question Paper for the subject BCS409 – Design and Analysis of Algorithm, from the academic session 2023–2024.
It is a 70-mark, 3-hour examination designed to evaluate a student’s understanding of algorithmic techniques, complexities, data structures, optimization strategies, backtracking, graph algorithms, and computational theory.
The paper is divided into three sections—A, B, and C—covering short theory, intermediate descriptive problems, and advanced analytical questions.
SECTION A – Short Questions (14 Marks)
Seven short questions (2 marks each), asked in both English and Hindi. Topics include:
Why Quick Sort is preferred for arrays
Best-case time complexity of Heap Sort
Difference between merging in Binomial Heap vs Binary Heap
Advantages of Tries over hash tables
Applications of Convex Hull in computer graphics
Comparing Floyd–Warshall DP approach with Bellman–Ford
Practical uses of string matching in search engines
This section checks conceptual clarity and quick reasoning.
SECTION B – Intermediate Descriptive Problems (21 Marks)
Students must attempt any three, covering detailed algorithm design and analysis topics:
Growth of functions and explanation of Big-O, Ω, Θ notations
Skip Lists: structure, insertion, deletion, search, and comparison with AVL & Red-Black Trees
Divide & Conquer matrix multiplication, implementation, and time analysis
Sum of Subsets problem using backtracking
Detailed explanation, implementation, and applications of the Fast Fourier Transform (FFT)
This section assesses problem-solving depth and algorithmic reasoning.
SECTION C – Advanced Analytical Questions (28 Marks)
Each question contains two options; students choose one from each.
3. Sorting Algorithms
Compare Bubble, Insertion, Selection sorts
Explain Linear Time Sorting (Counting Sort & Radix Sort)
4. Heap & Advanced Data Structures
Implementation and time analysis of Binomial Heap operations
Structure and operations of Fibonacci Heap and comparisons with Dijkstra’s algorithm
5. Greedy vs DP Algorithms
Knapsack problem using Greedy approach, why greedy fails for 0/1 knapsack, and comparison with DP
Prim’s Algorithm with implementation and applications
6. Graph Algorithms & Backtracking
Detailed explanation of Floyd’s Algorithm, comparison with Warshall’s
Hamiltonian Cycle using backtracking, comparison with other approaches
7. Computational Complexity & Randomization
Theory of NP-Completeness, examples, implications
Randomized algorithms, including implementation and analysis of randomized Quick Sort
This section assesses high-level algorithmic thinking, optimization, and computational theory understanding.
Overall Purpose of the Document
This exam paper evaluates a student's:
Mastery of algorithm design techniques (Greedy, DP, Divide & Conquer)
Understanding of time/space complexity and asymptotic analysis
Ability to work with advanced data structures (Heaps, Tries, Skip Lists, Fibonacci Heaps)
Problem-solving approach for backtracking and graph algorithms
Knowledge of NP-Completeness and randomized algorithms
The paper combines short conceptual questions, medium-depth explanations, and highly analytical long-answer problems, ensuring complete assessment of the Design & Analysis of Algorithms subject.
