CSS 200 Foundations of CS - Finals Mock Exam Review - UOPX 2025

CSS 200 Foundations of Computer
Science

Finals Mock Exam Review

(Questions & Solutions)

2025




©2025

, Question 1:
A sorting algorithm selects the smallest element from an unsorted array
and swaps it with the first unsorted element in each iteration. In the
worst-case scenario, what is the time complexity of this algorithm?
- A. O(n)
- B. O(n log n)
- C. O(n²)
- D. O(2ⁿ)

ANS: C. O(n²)
Rationale: This description characterizes the selection sort algorithm,
whose worst-case (and best-case) time complexity is O(n²) because it
performs roughly n(n–1)/2 comparisons as the array is processed.

---

Question 2:
Which of the following computational models is considered the most
powerful among those discussed in the theory of computation?
- A. Finite automata
- B. Pushdown automata
- C. Turing machines
- D. Linear bounded automata

ANS: C. Turing machines
Rationale: Turing machines are the most powerful model of
computation, capable of simulating any algorithm, and serve as the
standard theoretical basis for defining what is computable.

---

Question 3:
The decision version of the Boolean satisfiability problem (SAT) is
©2025

,significant because it was the first problem to be proven NP-complete.
Which theorem does this result relate to?
- A. Rice’s Theorem
- B. Cook’s Theorem
- C. Gödel’s Incompleteness Theorem
- D. Bellman’s Principle of Optimality

ANS: B. Cook’s Theorem
Rationale: Cook’s Theorem established that the Boolean satisfiability
problem (SAT) is NP-complete, forming the foundation of NP-
completeness theory and its implications for P vs NP.

---

Question 4:
A computer scientist is analyzing an algorithm that solves a problem by
recursively dividing it into two subproblems of equal size. Which
recurrence relation best models the time complexity of this algorithm,
assuming linear time is spent on dividing and combining?
- A. T(n) = 2T(n/2) + O(n)
- B. T(n) = T(n - 1) + O(1)
- C. T(n) = T(n/2) + O(n²)
- D. T(n) = 2T(n/2) + O(1)

ANS: A. T(n) = 2T(n/2) + O(n)
Rationale: This recurrence models divide-and-conquer algorithms (e.g.,
merge sort) where the problem is divided into two equal parts, with O(n)
work required to combine them, resulting in an overall time complexity
of O(n log n).

---

Question 5:
Which of the following is an example of a problem that is proven to be
NP-complete?
©2025

, - A. Sorting a list of numbers
- B. The Traveling Salesman Problem (decision version)
- C. Computing the greatest common divisor (GCD)
- D. Finding the shortest path in a weighted graph

ANS: B. The Traveling Salesman Problem (decision version)
Rationale: The decision version of the Traveling Salesman Problem
(TSP) is NP-complete because it is both in NP and NP-hard. While the
optimization version is NP-hard, the decision version fits the NP-
complete classification.

---

Question 6:
Which algorithm employs dynamic programming to efficiently solve the
problem of finding the longest common subsequence between two
sequences?
- A. Quick sort
- B. Dijkstra’s algorithm
- C. Floyd-Warshall algorithm
- D. LCS (Longest Common Subsequence) algorithm

ANS: D. LCS (Longest Common Subsequence) algorithm
Rationale: The LCS algorithm uses dynamic programming to solve the
problem by breaking the problem into overlapping subproblems and
storing intermediate results, thereby reducing overall computation.

---

Question 7:
Regular languages are defined by regular expressions and can be
recognized by finite automata. Which of the following properties is true
for regular languages?
- A. They are closed under union and concatenation.
- B. They are not closed under complementation.
©2025