← Exam 2 home

Mock Exam 2

Fall 2026, A-I 305

Time yourself: 2 hours. Problems first (≈12 min each), then MCQs (≈1 min each). Write answers on paper.

Closed book and closed notes, no calculators or cheat sheets allowed. Please don’t use cell phones during the exam.

Questions 1–7 carry 2–3 points each (15 points total); questions 8–22 carry 1/3 point each (5 points total). Total: 20 points.

Whenever an algorithm has a choice of vertices or edges, pick the one that is alphabetically first unless the question says otherwise.

Question 1 (2 points)

Consider the directed graph \(G\) below, with vertices A–I and edges A→B, B→C, C→A, C→D, D→E, E→F, F→D, G→H, H→G, H→E, I→A, A→E, B→H.

ABCIDEFGH
The graph for Question 1.
  1. Run depth-first search on \(G\). Whenever you have a choice of vertices to explore (in the outer loop and among neighbors), always pick the one that is alphabetically first. Give the pre and post numbers of every vertex, and classify every edge as a tree, forward, back, or cross edge.
  2. Run the strongly connected components algorithm: run DFS on the reverse graph \(G^R\) (alphabetical choices), then explore \(G\), processing vertices in decreasing order of their post numbers from \(G^R\). In what order are the SCCs found?
  3. Which SCCs are sources and which are sinks? Draw the metagraph (the DAG of SCCs).
  4. What is the minimum number of edges you must add to \(G\) to make it strongly connected? Give an example of such edge(s) and justify your answer.

Question 2 (2 points)

Consider the directed graph below with edge lengths S→A 4, S→B 1, B→A 2, B→C 5, A→C 1, A→D 6, C→D 2, C→E 7, D→E 1, D→F 5, E→F 2, B→E 9.

412516271529SABCDEF
The graph for Question 2.
  1. Run Dijkstra’s algorithm starting at S (break ties alphabetically). Show a table of the dist values of every vertex after each deleteMin, and give the order in which vertices are removed from the priority queue.
  2. Draw the final shortest-path tree.
  3. Give an example of a directed graph with 3 vertices and no negative cycle on which Dijkstra’s algorithm gives a wrong answer. Say what Dijkstra outputs and what the true distance is.

Question 3 (2 points)

  1. Given a directed graph \(G = (V, E)\) with positive edge lengths and a source vertex \(s\), give an \(O((|V| + |E|) \log |V|)\) algorithm that computes, for every vertex \(u\), the number of distinct shortest paths from \(s\) to \(u\). Justify correctness.
  2. Professor F. Lake suggests the following algorithm for finding the shortest path from \(s\) to \(t\) in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstra’s algorithm starting at \(s\), and return the shortest path found to \(t\). Is this a valid method? Either prove that it works correctly, or give a counterexample.

Question 4 (3 points)

Consider the undirected graph below with edge weights A–B 3, A–C 1, B–C 3, B–D 2, C–D 4, C–E 5, D–E 2, D–F 6, E–F 3, E–G 4, F–G 1, B–F 7.

313245263417ABCDEFG
The graph for Question 4.
  1. What is the cost of a minimum spanning tree?
  2. How many minimum spanning trees does the graph have? Explain why.
  3. Run Kruskal’s algorithm (break ties between equal-weight edges alphabetically by edge name, e.g. AB before BC). List the edges in the order they are added. For each edge, give a cut that justifies adding it (by the cut property).
  4. Run Prim’s algorithm starting at A. Give the order in which vertices are added, and a table of the cost array after each iteration.

Question 5 (2 points)

  1. A file uses the six symbols below, with frequencies given per 100 characters:
    symbolabcdef
    frequency3225201085
    Construct a Huffman code. Show each merge, draw the tree, and give the codeword for each symbol. How many bits does the encoding use per 100 characters, and how does that compare with a fixed-length code?
  2. True or false? Give a one-line justification (or a counterexample) for each. Assume \(G\) is a connected undirected graph with edge weights.
    1. If \(G\) has a cycle with a unique heaviest edge \(e\), then \(e\) cannot be part of any MST.
    2. The shortest path between two nodes is necessarily part of some MST.
    3. Let \(e\) be any edge of minimum weight in \(G\). Then \(e\) must be part of some MST.

Question 6 (2 points)

0/1 knapsack with capacity \(W = 8\) and the following items (each item can be used at most once):

item1234
weight3612
value71323
  1. Let \(B[k, w]\) be the maximum total value of a subset of items \(1, \ldots, k\) with total weight at most \(w\). Write the recurrence for \(B[k, w]\), including the base case.
  2. Fill in the table \(B[k][w]\) for \(k = 1, \ldots, 4\) and \(w = 0, \ldots, 8\).
  3. What is the optimal value, and which items achieve it?
  4. What does the greedy algorithm that takes items in decreasing order of value/weight (skipping any item that does not fit) return? Is it optimal?
  5. If unlimited copies of each item are allowed (knapsack with repetition), what is the optimal value \(K(8)\)?

Question 7 (2 points)

Yuckdonald’s is considering opening a series of restaurants along Quaint Valley Highway (QVH). The \(n\) possible locations are along a straight line, and their distances from the start of QVH are, in miles and in increasing order, \(m_1 < m_2 < \cdots < m_n\). The constraints are:

  1. Give a dynamic programming algorithm to compute the maximum expected total profit subject to the constraints. State the subproblem, the recurrence, the base case, the order in which you solve the subproblems, where the final answer is, and the running time.
  2. Run your algorithm on \(m = (1, 3, 4, 7, 9, 10)\), \(p = (5, 6, 4, 9, 3, 7)\), \(k = 3\). Show the table, the maximum profit, and which locations are used.

Questions 8–22 (1/3 point each)

Choose one answer for each question.

Question 8 (1/3 point)

Dijkstra’s algorithm implemented with a binary heap runs in time

  1. \(O(|V|^2)\)
  2. \(O((|V| + |E|) \log |V|)\)
  3. \(O(|V| \cdot |E|)\)
  4. \(O(|V| + |E|)\)

Question 9 (1/3 point)

A model has three Boolean variables and two variables with domain {low, mid, high}. How many possible worlds are there?

  1. 17
  2. 12
  3. 36
  4. 72

Question 10 (1/3 point)

Generalized arc consistency (GAC) finishes, and every variable’s domain has exactly one value left. What can you conclude?

  1. That assignment is the unique solution of the CSP
  2. The CSP has no solution
  3. You still need domain splitting to know whether a solution exists
  4. The CSP has several solutions and GAC picked one of them

Question 11 (1/3 point)

A sound and complete proof procedure for definite clauses answers “no” to the query ask g. This means

  1. \(g\) is false in every model of the KB
  2. \(\neg g\) is a logical consequence of the KB
  3. \(g\) is not a logical consequence of the KB
  4. the KB is inconsistent

Question 12 (1/3 point)

What is the truth value of \(p \rightarrow q\) when \(p\) is false and \(q\) is true?

  1. true
  2. false
  3. undefined
  4. it depends on the knowledge base

Question 13 (1/3 point)

Which of the following is true of Huffman coding?

  1. The two most frequent symbols are always the two children of the root
  2. Every symbol gets a codeword of length \(\lceil \log_2 n \rceil\)
  3. The least frequent symbol always has a strictly longer codeword than every other symbol
  4. There is an optimal tree in which the two least frequent symbols are siblings at the deepest level

Question 14 (1/3 point)

What is the purpose of path compression in a union-find (disjoint sets) data structure?

  1. To make union take \(O(1)\) time by always linking the shorter tree under the taller one
  2. To make later find operations faster by pointing each node on the find path directly at the root
  3. To reduce the memory used by the parent array
  4. To guarantee that every tree has height exactly 1 after each union

Question 15 (1/3 point)

A hash table with chaining stores \(n\) keys in \(m\) slots. Under simple uniform hashing, the expected time for a search is

  1. \(O(1)\) in the worst case
  2. \(O(\log n)\)
  3. \(O(1 + \alpha)\), where \(\alpha = n/m\)
  4. \(O(n)\)

Question 16 (1/3 point)

The \(O(nW)\) dynamic programming algorithm for 0/1 knapsack (\(n\) items, capacity \(W\)) is called

  1. polynomial, because \(n\) and \(W\) are both part of the input
  2. pseudo-polynomial
  3. exponential in \(n\)
  4. linear

Question 17 (1/3 point)

A directed graph has a cycle if and only if depth-first search finds

  1. a back edge
  2. a cross edge
  3. a forward edge
  4. more than one DFS tree

Question 18 (1/3 point)

In the edit distance dynamic program, the entry \(E(i, j)\) is computed directly from

  1. \(E(i-1, j-1)\) only
  2. \(E(i-1, j)\) and \(E(i, j-1)\) only
  3. \(E(i-1, j-1)\) and \(E(i-2, j-2)\)
  4. \(E(i-1, j)\), \(E(i, j-1)\) and \(E(i-1, j-1)\)

Question 19 (1/3 point)

Why does the Bellman-Ford algorithm need only \(|V| - 1\) rounds of updating all edges (when there is no negative cycle)?

  1. Each round finalizes one more vertex, as in Dijkstra’s algorithm
  2. The edges are relaxed in sorted order of length
  3. Some shortest path to each vertex is simple, so it has at most \(|V| - 1\) edges
  4. A negative edge can appear on at most \(|V| - 1\) shortest paths

Question 20 (1/3 point)

The cut property says: suppose edges \(X\) are part of an MST of \(G\). Pick any subset of nodes \(S\) for which \(X\) does not cross between \(S\) and \(V - S\), and let \(e\) be

  1. the heaviest edge on any cycle; then \(e\) is in every MST
  2. the lightest edge across this partition; then \(X \cup \{e\}\) is part of some MST
  3. the lightest edge in the whole graph; then \(e\) is in every MST
  4. any edge across this partition; then \(X \cup \{e\}\) is part of some MST

Question 21 (1/3 point)

You run local search on a large CSP for a long time and it never finds an assignment that satisfies all constraints. What can you conclude?

  1. The CSP has no solution
  2. The CSP has exactly one solution, which is hard to find
  3. Arc consistency would also fail to find a solution
  4. Nothing definite: local search cannot prove that no solution exists

Question 22 (1/3 point)

You have a knowledge base of a million definite clauses and need to answer one query. Which proof procedure is the better choice?

  1. Bottom-up, because it is complete
  2. Bottom-up, because only it is sound
  3. Top-down, because it only explores clauses relevant to the query
  4. A truth table, because it is exact

Answer key and worked solutions →