IT 415 Algorithm Design & Analysis
Comprehensive Final Exam (Qns & Ans)
2025
Question 1 (Multiple Choice)
Question:
Dynamic programming exploits overlapping subproblems and
optimal substructure. Which technique builds up solutions using a
bottom‐up approach by iteratively tabulating results?
A) Recursion with memoization
B) Divide and Conquer
C) Tabulation
D) Greedy algorithms
Correct ANS:
©2025
,C) Tabulation
Rationale:
Tabulation is a dynamic programming technique that solves
subproblems iteratively from the smallest up. Unlike memoization
(a top‐down approach), tabulation avoids recursion entirely by
filling out a table of solutions, thereby reducing the overhead of
recursive calls.
---
Question 2 (Fill in the Blank)
Question:
For the recurrence relation
T(n) = 2T(n/2) + n,
the asymptotic solution using the Master Theorem is
Θ(________).
Correct ANS:
n log n
Rationale:
©2025
,In the recurrence T(n) = 2T(n/2) + n, we have a = 2, b = 2, and
f(n) = n. Since f(n) = Θ(n) and n^(log₂2) = n, the Master Theorem
(Case 2) tells us that T(n) = Θ(n log n).
---
Question 3 (True/False)
Question:
True/False: Greedy algorithms always yield an optimal solution
for the 0/1 Knapsack Problem.
Correct ANS:
False
Rationale:
While greedy strategies find the optimal solution for the
Fractional Knapsack Problem, they do not guarantee an optimal
solution for the 0/1 Knapsack Problem due to the inherent
combinatorial nature of item selection where items are either
entirely taken or left.
---
©2025
, Question 4 (Multiple Response)
Question:
Select all properties that a problem must exhibit in order for
dynamic programming to be an effective solution method:
A) Overlapping subproblems
B) Optimal substructure
C) Greedy-choice property
D) A well-defined state space
Correct ANS:
A) Overlapping subproblems, B) Optimal substructure, D) A
well-defined state space
Rationale:
Dynamic programming is applicable when a problem has
overlapping subproblems, meaning the same computations occur
repeatedly, and an optimal substructure, where the optimal
solution can be constructed from optimal solutions of its
subproblems. A clear state-space formulation is also essential.
The greedy-choice property is not required for DP and generally
pertains to algorithms solved by greedy methods.
©2025
Comprehensive Final Exam (Qns & Ans)
2025
Question 1 (Multiple Choice)
Question:
Dynamic programming exploits overlapping subproblems and
optimal substructure. Which technique builds up solutions using a
bottom‐up approach by iteratively tabulating results?
A) Recursion with memoization
B) Divide and Conquer
C) Tabulation
D) Greedy algorithms
Correct ANS:
©2025
,C) Tabulation
Rationale:
Tabulation is a dynamic programming technique that solves
subproblems iteratively from the smallest up. Unlike memoization
(a top‐down approach), tabulation avoids recursion entirely by
filling out a table of solutions, thereby reducing the overhead of
recursive calls.
---
Question 2 (Fill in the Blank)
Question:
For the recurrence relation
T(n) = 2T(n/2) + n,
the asymptotic solution using the Master Theorem is
Θ(________).
Correct ANS:
n log n
Rationale:
©2025
,In the recurrence T(n) = 2T(n/2) + n, we have a = 2, b = 2, and
f(n) = n. Since f(n) = Θ(n) and n^(log₂2) = n, the Master Theorem
(Case 2) tells us that T(n) = Θ(n log n).
---
Question 3 (True/False)
Question:
True/False: Greedy algorithms always yield an optimal solution
for the 0/1 Knapsack Problem.
Correct ANS:
False
Rationale:
While greedy strategies find the optimal solution for the
Fractional Knapsack Problem, they do not guarantee an optimal
solution for the 0/1 Knapsack Problem due to the inherent
combinatorial nature of item selection where items are either
entirely taken or left.
---
©2025
, Question 4 (Multiple Response)
Question:
Select all properties that a problem must exhibit in order for
dynamic programming to be an effective solution method:
A) Overlapping subproblems
B) Optimal substructure
C) Greedy-choice property
D) A well-defined state space
Correct ANS:
A) Overlapping subproblems, B) Optimal substructure, D) A
well-defined state space
Rationale:
Dynamic programming is applicable when a problem has
overlapping subproblems, meaning the same computations occur
repeatedly, and an optimal substructure, where the optimal
solution can be constructed from optimal solutions of its
subproblems. A clear state-space formulation is also essential.
The greedy-choice property is not required for DP and generally
pertains to algorithms solved by greedy methods.
©2025
