CSS 430 Algorithmic Theory & Practice
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
Consider an algorithm whose running time is described by the recurrence
relation
T(n) = 4T(n/2) + n.
Using the Master Theorem, what is the asymptotic time complexity?
- A. Θ(n)
- B. Θ(n log n)
- C. Θ(n²)
- D. Θ(n² log n)
ANS: C. Θ(n²)
Rationale: Here a = 4, b = 2, and f(n) = n. We compute n^(log_b a) =
n^(log₂4) = n². Since f(n) = O(n) is polynomially smaller than n², by Master
Theorem (Case 1) the complexity is Θ(n²).
---
Question 2:
Which algorithm design paradigm involves breaking a problem into
independent subproblems, solving each recursively, and combining their
results?
- A. Greedy algorithms
- B. Dynamic programming
- C. Divide-and-conquer
- D. Backtracking
ANS: C. Divide-and-conquer
Rationale: Divide-and-conquer splits a problem into independent
subproblems, solves them recursively, and then combines their solutions.
Unlike dynamic programming, its subproblems are typically non-
overlapping.
---
©2025
, Question 3:
Which of the following is the most powerful computational model that
serves as the abstract basis for algorithmic computation?
- A. Finite automata
- B. Pushdown automata
- C. Turing machine
- D. Linear bounded automata
ANS: C. Turing machine
Rationale: Turing machines are the most general model of
computation; they can simulate any algorithm and define decidability
and computational complexity.
---
Question 4:
The Boolean satisfiability problem (SAT) is historically significant as the
first problem proven NP-complete. Which theorem established this
result?
- A. Cook’s Theorem
- B. Rice’s Theorem
- C. Gödel’s Incompleteness Theorem
- D. Bellman’s Principle of Optimality
ANS: A. Cook’s Theorem
Rationale: Cook’s Theorem demonstrated that SAT is NP-complete,
meaning any problem in NP can be reduced to it in polynomial time,
establishing the foundation for NP-completeness theory.
---
Question 5:
Which complexity class contains all decision problems for which a
solution, once provided, can be verified in polynomial time?
- A. P
©2025
, - B. NP
- C. NP-hard
- D. NP-complete
ANS: B. NP
Rationale: NP is the set of decision problems for which a given solution
can be verified in polynomial time, irrespective of whether the problem
can also be solved in polynomial time.
---
Question 6:
A recursive algorithm must have a _______ case to ensure termination.
- A. Recursive
- B. Inductive
- C. Base
- D. Infinite
ANS: C. Base
Rationale: A base case provides the condition under which the
recursion stops, ensuring that the algorithm terminates rather than
recursing indefinitely.
---
Question 7:
Which type of reduction is used to prove that a problem is NP-complete
by showing that every problem in NP can be reduced to it in polynomial
time?
- A. Polynomial-time reduction
- B. Exponential reduction
- C. Logarithmic reduction
- D. Constant-time reduction
ANS: A. Polynomial-time reduction
©2025
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
Consider an algorithm whose running time is described by the recurrence
relation
T(n) = 4T(n/2) + n.
Using the Master Theorem, what is the asymptotic time complexity?
- A. Θ(n)
- B. Θ(n log n)
- C. Θ(n²)
- D. Θ(n² log n)
ANS: C. Θ(n²)
Rationale: Here a = 4, b = 2, and f(n) = n. We compute n^(log_b a) =
n^(log₂4) = n². Since f(n) = O(n) is polynomially smaller than n², by Master
Theorem (Case 1) the complexity is Θ(n²).
---
Question 2:
Which algorithm design paradigm involves breaking a problem into
independent subproblems, solving each recursively, and combining their
results?
- A. Greedy algorithms
- B. Dynamic programming
- C. Divide-and-conquer
- D. Backtracking
ANS: C. Divide-and-conquer
Rationale: Divide-and-conquer splits a problem into independent
subproblems, solves them recursively, and then combines their solutions.
Unlike dynamic programming, its subproblems are typically non-
overlapping.
---
©2025
, Question 3:
Which of the following is the most powerful computational model that
serves as the abstract basis for algorithmic computation?
- A. Finite automata
- B. Pushdown automata
- C. Turing machine
- D. Linear bounded automata
ANS: C. Turing machine
Rationale: Turing machines are the most general model of
computation; they can simulate any algorithm and define decidability
and computational complexity.
---
Question 4:
The Boolean satisfiability problem (SAT) is historically significant as the
first problem proven NP-complete. Which theorem established this
result?
- A. Cook’s Theorem
- B. Rice’s Theorem
- C. Gödel’s Incompleteness Theorem
- D. Bellman’s Principle of Optimality
ANS: A. Cook’s Theorem
Rationale: Cook’s Theorem demonstrated that SAT is NP-complete,
meaning any problem in NP can be reduced to it in polynomial time,
establishing the foundation for NP-completeness theory.
---
Question 5:
Which complexity class contains all decision problems for which a
solution, once provided, can be verified in polynomial time?
- A. P
©2025
, - B. NP
- C. NP-hard
- D. NP-complete
ANS: B. NP
Rationale: NP is the set of decision problems for which a given solution
can be verified in polynomial time, irrespective of whether the problem
can also be solved in polynomial time.
---
Question 6:
A recursive algorithm must have a _______ case to ensure termination.
- A. Recursive
- B. Inductive
- C. Base
- D. Infinite
ANS: C. Base
Rationale: A base case provides the condition under which the
recursion stops, ensuring that the algorithm terminates rather than
recursing indefinitely.
---
Question 7:
Which type of reduction is used to prove that a problem is NP-complete
by showing that every problem in NP can be reduced to it in polynomial
time?
- A. Polynomial-time reduction
- B. Exponential reduction
- C. Logarithmic reduction
- D. Constant-time reduction
ANS: A. Polynomial-time reduction
©2025
