PRG 211 Algorithms & Logic for
Computer Programming
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
Consider an algorithm with the following recurrence:
T(n) = 3T(n/2) + n.
Using the Master Theorem, what is the time complexity of the algorithm?
- A. Θ(n)
- B. Θ(n log n)
- C. Θ(n^log_2(3))
- D. Θ(n^2)
ANS: C. Θ(n^log_2(3))
Rationale: Here, a = 3 and b = 2. We compute exponent log_b(a) =
log_2(3) ≈ 1.585. Since f(n) = n is O(n^(log_2(3)-ε)) (for ε ≈ 0.585), by
Master Theorem (Case 1) the time complexity is Θ(n^log_2(3)).
---
Question 2:
Which algorithmic paradigm is best described by solving a problem
recursively by breaking it into two or more independent subproblems
and then combining their solutions?
- A. Greedy algorithms
- B. Dynamic programming
- C. Divide-and-conquer
- D. Backtracking
ANS: C. Divide-and-conquer
Rationale: Divide‐and‐conquer splits the problem into independent
subproblems, solves each recursively, and merges the solutions. It is
distinct from dynamic programming, where overlapping subproblems are
stored to avoid re-computation.
---
©2025
, Question 3:
A Turing machine is considered the gold standard for a computational
model because it can simulate any algorithm. This concept is captured by
which property?
- A. Turing Completeness
- B. Decidability
- C. Determinism
- D. Finite state operation
ANS: A. Turing Completeness
Rationale: Turing completeness means that a computational model
(like a Turing machine) can simulate any other Turing complete system. It
is the benchmark for what is computable.
---
Question 4:
The Boolean Satisfiability Problem (SAT) is important in computational
complexity because it was the first problem to be proven NP-complete.
Which theorem established this result?
- A. Cook’s Theorem
- B. Gödel’s Incompleteness Theorem
- C. Rice’s Theorem
- D. Bellman’s Principle
ANS: A. Cook’s Theorem
Rationale: Cook’s Theorem (1971) established that SAT is NP-complete,
meaning that any problem in NP can be reduced to SAT in polynomial
time, forming the basis of NP-completeness.
---
Question 5:
Which complexity class contains decision problems that can be solved in
©2025
Computer Programming
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
Consider an algorithm with the following recurrence:
T(n) = 3T(n/2) + n.
Using the Master Theorem, what is the time complexity of the algorithm?
- A. Θ(n)
- B. Θ(n log n)
- C. Θ(n^log_2(3))
- D. Θ(n^2)
ANS: C. Θ(n^log_2(3))
Rationale: Here, a = 3 and b = 2. We compute exponent log_b(a) =
log_2(3) ≈ 1.585. Since f(n) = n is O(n^(log_2(3)-ε)) (for ε ≈ 0.585), by
Master Theorem (Case 1) the time complexity is Θ(n^log_2(3)).
---
Question 2:
Which algorithmic paradigm is best described by solving a problem
recursively by breaking it into two or more independent subproblems
and then combining their solutions?
- A. Greedy algorithms
- B. Dynamic programming
- C. Divide-and-conquer
- D. Backtracking
ANS: C. Divide-and-conquer
Rationale: Divide‐and‐conquer splits the problem into independent
subproblems, solves each recursively, and merges the solutions. It is
distinct from dynamic programming, where overlapping subproblems are
stored to avoid re-computation.
---
©2025
, Question 3:
A Turing machine is considered the gold standard for a computational
model because it can simulate any algorithm. This concept is captured by
which property?
- A. Turing Completeness
- B. Decidability
- C. Determinism
- D. Finite state operation
ANS: A. Turing Completeness
Rationale: Turing completeness means that a computational model
(like a Turing machine) can simulate any other Turing complete system. It
is the benchmark for what is computable.
---
Question 4:
The Boolean Satisfiability Problem (SAT) is important in computational
complexity because it was the first problem to be proven NP-complete.
Which theorem established this result?
- A. Cook’s Theorem
- B. Gödel’s Incompleteness Theorem
- C. Rice’s Theorem
- D. Bellman’s Principle
ANS: A. Cook’s Theorem
Rationale: Cook’s Theorem (1971) established that SAT is NP-complete,
meaning that any problem in NP can be reduced to SAT in polynomial
time, forming the basis of NP-completeness.
---
Question 5:
Which complexity class contains decision problems that can be solved in
©2025
