(SEM IV) THEORY EXAMINATION 2023-24 DESIGN AND ANALYSIS OF ALGORITHM

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.