This question paper is designed after analysis of 2024, 2023, 2022
question papers
📘 MCA – III Semester
MCA-302 : Analysis and Design of Algorithm
Time: 3 Hours Maximum Marks: 70
🟢 PART – A (10 × 2 = 20 Marks)
(Answer up to 25 words only)
Q1. What is an algorithm?
Answer:
An algorithm is a finite sequence of well-defined steps used to solve a computational problem and
produce a correct output in finite time.
Q2. Define asymptotic notation.
Answer:
Asymptotic notation is a mathematical tool used to describe the growth rate of an algorithm’s time
or space complexity for large input sizes.
Q3. What do you mean by time complexity?
Answer:
Time complexity measures how the execution time of an algorithm increases with respect to the size
of the input.
Q4. Define space complexity.
Answer:
Space complexity refers to the total memory required by an algorithm during execution, including
input storage and auxiliary space.
Q5. What is divide and conquer technique?
Answer:
Divide and conquer is an algorithm design technique that divides a problem into smaller
subproblems, solves them recursively, and combines the results.
Q6. Define greedy algorithm.
Answer:
A greedy algorithm makes locally optimal choices at each step with the aim of finding a global
optimal solution.
Q7. What is dynamic programming?
Answer:
Dynamic programming is an algorithmic technique that solves problems by breaking them into
overlapping subproblems and storing intermediate results.
Q8. What is a minimum spanning tree?
Answer:
A minimum spanning tree is a subset of edges of a connected graph that connects all vertices with
minimum total edge weight.
Q9. Define NP-complete problem.
Answer:
An NP-complete problem is a problem that is both in NP and as hard as any problem in NP.
Q10. What is the time complexity of binary search?
Answer:
The time complexity of binary search is O(log n).
🟡 PART – B (5 × 4 = 20 Marks)
(~100 words each)
Q1. Explain different asymptotic notations.
Answer:
Asymptotic notations are used to analyze algorithm efficiency. Big-O (O) represents the upper bound
or worst-case performance. Omega (Ω) represents the lower bound or best-case performance. Theta
(Θ) represents the exact bound when upper and lower bounds are the same. These notations ignore
constants and lower-order terms, focusing on growth rates. They allow comparison of algorithms
independent of hardware or programming language.
Q2. Explain time complexity estimation, space complexity estimation, and trade-off.
Answer:
Time complexity estimation determines how execution time grows with input size, while space
complexity estimation measures memory usage. Often, reducing time complexity increases space
usage and vice versa. This is called a time-space trade-off. For example, using extra memory for
lookup tables can reduce computation time. Efficient algorithm design balances both based on
application requirements.
Q3. Explain Divide and Conquer strategy.
Answer:
Divide and conquer solves a problem by dividing it into smaller subproblems, solving each
recursively, and combining the solutions. This strategy reduces complexity and improves efficiency.
Common examples include binary search, merge sort, and quick sort. It is effective for large problems
because it simplifies problem structure and reduces redundant computation.
Q4. Explain Dynamic Programming method.
Answer:
Dynamic programming is used when problems have overlapping subproblems and optimal
substructure. It stores intermediate results to avoid recomputation. Problems like knapsack, shortest
path, and matrix chain multiplication are solved using dynamic programming. This approach
significantly reduces time complexity compared to naive recursive solutions.
Q5. Explain P, NP and NP-Complete problems.
Answer:
Class P contains problems solvable in polynomial time. NP contains problems whose solutions can be
verified in polynomial time. NP-Complete problems are the hardest problems in NP. If any NP-
Complete problem is solved in polynomial time, then P = NP.
🔴 PART – C (3 × 10 = 30 Marks)
(~200–250 words each, complete answers)
Q1. Explain Merge Sort algorithm. Derive its time complexity and sort the list:
415, 213, 700, 515, 712, 715
Answer:
Merge sort is a divide and conquer sorting algorithm. It divides the array into two halves, recursively
sorts each half, and then merges the sorted halves.
Algorithm Steps:
1. Divide the array into two halves.
2. Recursively apply merge sort on each half.
3. Merge the two sorted halves into one sorted array.
Diagram:
Divide → Sort → Merge
Sorting:
Original: 415, 213, 700, 515, 712, 715
Sorted: 213, 415, 515, 700, 712, 715
Time Complexity:
Best, Average, Worst Case: O(n log n)
Space Complexity:
O(n)
Merge sort is stable and efficient for large datasets.
Q2. Explain Quick Sort algorithm and sort the list:
100, 800, 320, 910, 430, 500, 750
Answer:
Quick sort is a divide and conquer algorithm that selects a pivot element and partitions the array into
elements smaller and greater than the pivot.
Steps:
1. Choose a pivot.
2. Partition array around pivot.
3. Recursively sort subarrays.
Diagram:
Pivot
/ \
< >
Sorted List:
100, 320, 430, 500, 750, 800, 910
Time Complexity:
Average Case: O(n log n)
Worst Case: O(n²)
Space Complexity:
O(log n) (recursive stack)
Quick sort is very fast in practice.
Q3. Explain Backtracking technique and 8-Queens problem.
Answer:
Backtracking is a problem-solving technique that builds solutions incrementally and abandons
solutions that violate constraints. It is used when all possibilities must be explored.
8-Queens Problem:
The goal is to place 8 queens on a chessboard such that no two queens attack each other.
Approach:
Place one queen per row.
Check column and diagonal conflicts.
Backtrack if placement is unsafe.
State Space Tree:
Row 1 → Row 2 → Row 3 → ... → Row 8
Backtracking systematically explores all valid configurations and guarantees correct solutions.