Computer Science 6901, Fall '26
Potential Exam Questions

---

Copyright 2026 by H.T. Wareham
All rights reserved

---

Topic 1, Topic 2, Topic 3, Topic 4

Questions prefixed by "(*)" involving executing one or more of the algorithms discussed in class.

Topic #1 (Problems and Algorithms; Lecture #1)

• Name three types of problems based on the type of problem output.
• Name two types of problems based on the entities encoded in the I/O relations.
• Name three types of algorithms based on the type of computer model.

Topic #2 (Time Complexity; Lectures #2-3)

• Name in order the four necessary lies discussed in class on the road from actual running tome to a useful and usable measure of algorithm runtime efficiency.
• Give the mathematical definition of "T(n) is O(f(n))" ("T(n) is OMEGA(f(n))").
• Given an algorithm, give an asymptotic worst-case time-complexity expression for this algorithm.
• Given an algorithm with calls to procedures of unknown time complexity, give an asymptotic worst-case parameterized time-complexity expression for this algorithm.
• Given an algorithm with calls to procedures with specified time complexities, give an asymptotic worst-case time-complexity expression for this algorithm.
• Given a multiple choice question "Which of the following is true of the function X?", circle the letters associated with the appropriate answers. Note that some questions may have more than one answer whose letter needs to be circled.

Topic #3 (Combinatorial Solution-space Trees; Lectures #3-4)

• What are the three types of solutions for combinatorial optimization problems discussed in class?
• What is the name given to implicit combinatorial solution-space tree (CST) generation by depth (breadth) first search when combined with dynamic pruning?
• What are the two types of CST dynamic pruning discussed in class?
• (*) Given a variant of a combinatorial optimization problem discussed in class, an algorithm A for implicitly generating CSTs for that problem, and an instance I of that problem, sketch the CST generated for I by A, indicating printed (pruned) solution nodes by solid (dotted) circles.

Topic #4 (Divide & Conquer / Dynamic Programming; Lectures #4-8)

• What property of problem solution spaces is shared by problems with divide & conquer, dynamic programming, and greedy algorithms?
• What property of problem solution spaces separates problems with divide & conquer algorithms from problems with dynamic programming algorithms?
• What are two divide & conquer algorithms that were discussed in class?
• What are the five steps of the Dynamic Programming Cookbook?
• Describe a linear space algorithm for computing the length of the longest commmon subsequence of two given character strings.
• (*) Given the recurrence for (a variant of) the Longest Common Subsequence problem and an instance I of that problem, fill in all entries of a provided dynamic programming table for I relative to that recurrence (including backpointer arrows), indicate by circling the appropriate arrows encoding an optimal solution, and give the optimal solution encoded in the traceback path.
• (*) Given the recurrence for the 0/1 Knapsack problem and an instance I of that problem, fill in all entries of a provided dynamic programming table for I relative to that recurrence (including backpointer arrows), indicate by circling the appropriate arrows encoding an optimal solution, and give the optimal solution encoded in the traceback path.