Computer Science 3600, Winter '25
Potential Exam Questions

---

Copyright 2025 by H.T. Wareham
All rights reserved

---

Topic 1, Topic 2, Topic 3, Topic 4, Topic 5, Topic 6, Topic 7

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 Matrix Chain Parenthesization 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.

Topic #5 (Greedy Algorithms; Lectures #9-11)

• What property of problem solution spaces separates problems with divide & conquer algorithms from problems with greedy algorithms?
• What are the combinations of presence / absence of solution space properties discussed in class that characterize problems solvable by each of the dynamic programming, divide and conquer, greedy, and/or combinatorial solution-space tree algorithms?
• What is required for a greedy choice to be called safe?
• (*) Given a set of activities sharing a common resource and the start and finish times of each of these activities, give the optimal solution for this set created by the greedy Activity Selectiion algorithm discussed in class.
• (*) Given an undirected edge-weighted graph, show how Kruskal's minimum spanning tree algorithm works on this graph. Give the graph at the end of the execution of the algorithm, with all tree-edges and the order in which each tree-edge was added clearly marked.
• (*) Given an undirected edge-weighted graph, show how Prim's minimum spanning tree algorithm works on this graph relatuive to a specified root-vertex. Give the graph at the end of the execution of the algorithm, with all tree-edges and the order in which each tree-edge was added clearly marked.

Topic #6 (Graph Algorithms; Lectures #12-14)

• What are the two types of data structures for representing graphs that were discussed in class?
• Give the names of two types of graph traversal algorithms discussed in class.
• (*) Given a directed graph, show this graph at the end of the execution of the Breadth-First Search (BFS) algorithm when the search is started at vertex X, with the d- and pi-values for all vertices as well as all BFS-search tree edges clearly marked. Assume that the algorithm considers vertices in alphabetical order and that each adjacency list is ordered alphabetically.
• (*) Given a directed edge-weighted graph, run Dijkstra's algorithm on this graph using vertex X as the source vertex. Show the d and pi values and the vertices in set S after each iteration of the WHILE loop by filling in the appropriate values on the spare copies of the graph given in this table.
• (*) Given a directed edge-weighted graph and an ordering of the edges in this graph, run the Bellman-Ford algorithm on this graph relative to source vertex X when the edges are relaxed in the specified order in each relaxation-phase. Show the d and pi values after each relaxation-phase by filling in the appropriate values on the spare copies of the graph given in this table.

Topic #7 (Polynomial-time Intractability; Lectures #14-19)

• What is a reduction? Polynomial-time reduction? Many-one polynomial time reduction?
• What are two of the three (very) useful properties of polynomial-time reductions that were discussed in class?
• Given a problem X and a problem class C, define what it means for X to be C-hard (C-complete).
• Given a reduction web and a multiple choice question "Which of the following statements is true if the one or more specified complexity results are known for problems in the web?", circle the letters associated with the appropriate answers. Note that some questions may have more than one answer whose letter needs to be circled.
• What are three of the six types of polynomial-time algorithms discussed in class that are used to deal with polynomial-time intractability?