COP 4533
Algorithm Abstraction & Design
4.0 Credits
Final Exam Review (Qns & Ans)
2025
©2025
, Multiple Choice Questions
1. Question:
Which algorithm design paradigm solves problems by recursively
dividing the input into smaller subproblems, solving each
independently, and then combining the results?
a. Greedy Algorithms
b. Divide and Conquer
c. Dynamic Programming
d. Backtracking
ANS:
b. Divide and Conquer
Rationale:
Divide and conquer explicitly splits the problem into smaller
subproblems, solves them recursively, and then merges the
solutions, making it ideal for algorithms like merge sort and quick
sort.
2. Question:
What is the worst-case time complexity of the QuickSort
algorithm when a poor pivot is consistently chosen?
a. O(n log n)
b. O(n²)
c. O(n)
d. O(log n)
ANS:
b. O(n²)
Rationale:
In the worst case (for example, when the smallest or largest
element is chosen repeatedly as the pivot), QuickSort degrades to
O(n²) due to highly unbalanced partitions.
3. Question:
©2025
, Which design technique is best suited for problems that exhibit
both optimal substructure and overlapping subproblems?
a. Greedy Strategy
b. Divide and Conquer
c. Dynamic Programming
d. Backtracking
ANS:
c. Dynamic Programming
Rationale:
Dynamic programming leverages the overlapping subproblems
and recomputes solutions only once by storing intermediate results,
as seen in the Fibonacci sequence or the knapsack problem.
4. Question:
The success of a greedy algorithm hinges on which key property?
a. Overlapping subproblems
b. Recursive structure
c. Greedy-choice property
d. Tail recursion
ANS:
c. Greedy-choice property
Rationale:
The greedy-choice property ensures that locally optimal choices
also lead to a global optimum, which is crucial for the correctness
of greedy algorithms.
5. Question:
Which of the following algorithm techniques systematically
explores all potential candidates and abandons paths that cannot
possibly lead to a valid solution?
a. Backtracking
b. Dynamic Programming
c. Divide and Conquer
d. Greedy Algorithms
©2025
Algorithm Abstraction & Design
4.0 Credits
Final Exam Review (Qns & Ans)
2025
©2025
, Multiple Choice Questions
1. Question:
Which algorithm design paradigm solves problems by recursively
dividing the input into smaller subproblems, solving each
independently, and then combining the results?
a. Greedy Algorithms
b. Divide and Conquer
c. Dynamic Programming
d. Backtracking
ANS:
b. Divide and Conquer
Rationale:
Divide and conquer explicitly splits the problem into smaller
subproblems, solves them recursively, and then merges the
solutions, making it ideal for algorithms like merge sort and quick
sort.
2. Question:
What is the worst-case time complexity of the QuickSort
algorithm when a poor pivot is consistently chosen?
a. O(n log n)
b. O(n²)
c. O(n)
d. O(log n)
ANS:
b. O(n²)
Rationale:
In the worst case (for example, when the smallest or largest
element is chosen repeatedly as the pivot), QuickSort degrades to
O(n²) due to highly unbalanced partitions.
3. Question:
©2025
, Which design technique is best suited for problems that exhibit
both optimal substructure and overlapping subproblems?
a. Greedy Strategy
b. Divide and Conquer
c. Dynamic Programming
d. Backtracking
ANS:
c. Dynamic Programming
Rationale:
Dynamic programming leverages the overlapping subproblems
and recomputes solutions only once by storing intermediate results,
as seen in the Fibonacci sequence or the knapsack problem.
4. Question:
The success of a greedy algorithm hinges on which key property?
a. Overlapping subproblems
b. Recursive structure
c. Greedy-choice property
d. Tail recursion
ANS:
c. Greedy-choice property
Rationale:
The greedy-choice property ensures that locally optimal choices
also lead to a global optimum, which is crucial for the correctness
of greedy algorithms.
5. Question:
Which of the following algorithm techniques systematically
explores all potential candidates and abandons paths that cannot
possibly lead to a valid solution?
a. Backtracking
b. Dynamic Programming
c. Divide and Conquer
d. Greedy Algorithms
©2025
