Skip to main content

Module Quiz

Complete this quiz after finishing all concept and practice pages.

Current Module Questions​

Question 1: Graph Model Discipline​

A "follows" relationship on a microblog is being modeled. Which graph model is correct: directed simple, undirected simple, directed multigraph, or undirected multigraph? Why?

Answer: Directed simple graph. "Alice follows Bob" does not imply "Bob follows Alice," so edges must be directed. A user follows another user at most once, so parallel edges are not needed. Self-follows are usually disallowed, so no self-loops.

Question 2: Representation Choice​

A graph has |V| = 10^6 and |E| = 2 x 10^7. Which representation should you use, and why does the alternative fail?

Answer: Adjacency list. Density is |E| / |V|^2 = 2 x 10^{-8}, extremely sparse. A matrix would need 10^{12} cells, which does not fit in memory. The list costs Theta(|V| + |E|) = 2.1 x 10^7 cells.

Question 3: BFS vs Dijkstra​

On an unweighted directed graph with 10^5 vertices and 10^6 edges, is there any benefit to using Dijkstra instead of BFS for single-source shortest paths?

Answer: No. BFS runs in O(|V| + |E|) = O(1.1 x 10^6). Dijkstra with a binary heap runs in O((|V| + |E|) log |V|) - worse by a factor of log |V| ~ 17. BFS is strictly faster and simpler on unit weights.

Question 4: DFS Edge Classification​

During DFS on a directed graph, you encounter an edge (u, v) where color[v] = GRAY. What kind of edge is this, and what does its existence imply?

Answer: A back edge. It points from a descendant to an ancestor in the DFS tree, because v is on the current recursion stack. Its existence proves the directed graph has a cycle through v.

Question 5: Topological Sort​

Given a DAG and Kahn's algorithm, you observe that the output length is |V| - 2. What does this tell you?

Answer: The graph is not actually a DAG. A cycle exists involving at least two vertices whose in-degree never reached zero because they are part of the cycle. Kahn's algorithm uses this as its cycle-detection rule.

Question 6: Dijkstra Running Time​

State Dijkstra's running time with a binary heap and with a Fibonacci heap. Derive each bound.

Answer:

  • Binary heap: O((|V| + |E|) log |V|). Each extract-min is O(log |V|), done |V| times; each relaxation can do a decrease-key (or equivalent push with lazy deletion) at O(log |V|), done at most |E| times.
  • Fibonacci heap: O(|E| + |V| log |V|). extract-min is O(log |V|) amortized, |V| times, giving O(|V| log |V|). decrease-key is O(1) amortized, |E| times, giving O(|E|).

Question 7: Why Not Dijkstra for Negative Edges​

Construct a small graph with a single negative edge and no negative cycle where Dijkstra produces an incorrect answer.

Answer:

s -(1)-> a
s -(4)-> t
a -(-3)-> t

Dijkstra extracts s, relaxes a (dist 1) and t (dist 4). It then extracts a (dist 1) and relaxes t to 1 + (-3) = -2. Actually with lazy pops, it may still extract t at dist 4 first and finalize, missing the improvement to -2. This is exactly where the invariant breaks: when t was finalized at 4, the algorithm assumed no future vertex could improve it, because weights were "assumed" nonnegative.

Question 8: Bellman-Ford Pass Count​

Why are exactly |V| - 1 passes sufficient for Bellman-Ford in the absence of a negative cycle?

Answer: Any shortest simple path visits each vertex at most once and therefore has at most |V| - 1 edges. After pass k, dist[v] reflects the shortest path using at most k edges. So after |V| - 1 passes, all shortest simple paths are covered.

Question 9: Floyd-Warshall Loop Order​

Why must Floyd-Warshall's outer loop iterate over k (the intermediate vertex), not over rows or columns?

Answer: The DP recurrence d^{(k)}[i][j] = min(d^{(k-1)}[i][j], d^{(k-1)}[i][k] + d^{(k-1)}[k][j]) requires all entries of the previous layer to be fully computed. Only by iterating k outermost and updating in place is it safe: the entries dist[i][k] and dist[k][j] that appear on the right-hand side match either the updated or non-updated values, both of which satisfy the invariant.

Question 10: MST Cut-Property Application​

State the cut property, and apply it in one sentence to justify Kruskal's next edge choice.

Answer: Cut property: for any non-trivial cut (S, V - S), the minimum-weight edge crossing it is safe to include in some MST. When Kruskal is about to add edge (u, v) of minimum remaining weight with find(u) != find(v), it crosses the cut between u's and v's current components; by the cut property, it is safe.

Question 11: Kruskal Running Time​

Why is Kruskal's running time O(|E| log |V|) rather than O(|E| log |E|)?

Answer: For simple graphs, |E| <= |V|^2, so log |E| <= 2 log |V| = O(log |V|). The sort is O(|E| log |E|) = O(|E| log |V|). The union-find operations add O(|E| alpha(|V|)), dominated by the sort. Total: O(|E| log |V|).

Question 12: Prim vs Dijkstra​

Compare Prim and Dijkstra as algorithms. What is identical, and what single change in the update rule distinguishes them?

Answer: Both maintain a priority queue keyed on a key[v] array, extract min, and relax outgoing edges. The difference is the update rule:

  • Dijkstra: key[v] := min(key[v], key[u] + w(u, v))
  • Prim: key[v] := min(key[v], w(u, v))

Dijkstra accumulates distance from s; Prim only considers the single-edge cost. That one-line change converts shortest-path to minimum-spanning-tree.

Question 13: Max-Flow Min-Cut​

State the max-flow min-cut theorem and explain how to recover a minimum cut from a maximum flow.

Answer: The max flow value equals the minimum cut capacity. Given a max flow f, let S be the set of vertices reachable from s in the residual graph G_f (using only residual edges with positive capacity). Then (S, V - S) is a minimum cut, and every edge from S to V - S in E is saturated.

Question 14: Ford-Fulkerson Backward Edges​

Why does Ford-Fulkerson need backward residual edges?

Answer: They enable the algorithm to undo earlier suboptimal routing decisions. Without them, a bad choice of augmenting path could saturate an edge in the wrong direction, and no future path could improve the flow. The backward edge lets a new augmenting path "cancel" previously pushed flow by pushing negative flow on the original edge, restoring optimality.

Question 15: Bipartite Matching Reduction​

Describe the reduction from unweighted bipartite matching to max flow, and explain why the max-flow value equals the matching size.

Answer: Add source s with unit-capacity edges to every vertex in L, orient every L-R edge left-to-right with unit capacity, add sink t with unit-capacity edges from every vertex in R. Each unit of flow traces a path s -> l -> r -> t, which picks edge (l, r). Unit capacities on s -> l and r -> t guarantee each L and R vertex is used by at most one unit, so saturated L -> R edges form a valid matching. Conversely, any matching of size k gives k edge-disjoint s-to-t paths.

Interleaved Review Questions​

Prior Module Question 1 (S2M2: Priority Queues)​

What is the running time of extract-min and decrease-key in a binary heap versus a Fibonacci heap?

Answer:

  • Binary heap: extract-min O(log n), decrease-key O(log n).
  • Fibonacci heap: extract-min O(log n) amortized, decrease-key O(1) amortized.

This is why Fibonacci heaps theoretically speed up Dijkstra and Prim: they turn O(|E| log |V|) into O(|E|) for decrease-key work.

Prior Module Question 2 (S2M2: Hashing)​

Why does a hash-set representation of neighbors in an adjacency structure support O(1) expected has_edge(u, v) queries?

Answer: A hash set supports O(1) expected lookup. Storing each vertex's neighbors in a hash set keeps edge-existence fast while retaining the Theta(|V| + |E|) total space of an adjacency list.

Prior Module Question 3 (S2M1: Divide-and-Conquer Analysis)​

Write the Master Theorem-style analysis of T(n) = 8 T(n/2) + O(n^2).

Answer: a = 8, b = 2, f(n) = n^2, so n^{log_b a} = n^3. Since f(n) = O(n^{3 - epsilon}) for epsilon = 1, case 1 applies: T(n) = Theta(n^3).

Prior Module Question 4 (S1 Probability: Linearity of Expectation)​

Why is the expected number of edges in a random graph G(n, p) equal to p C(n, 2)?

Answer: Let X_{ij} be the indicator that edge (i, j) is present. E[X_{ij}] = p. E[|E|] = E[sum X_{ij}] = sum E[X_{ij}] = p C(n, 2) by linearity of expectation. Independence is not needed.

Prior Module Question 5 (S1 Proofs: Induction)​

Why does |E| = |V| - 1 characterize trees among connected graphs?

Answer: Prove by induction on |V|: a tree on 1 vertex has 0 edges. Removing a leaf of a tree on n vertices gives a tree on n - 1 vertices, which has n - 2 edges by IH; restoring the leaf adds one edge, so n - 1. Conversely, a connected graph with |V| - 1 edges has no room for cycles (adding a cycle edge while preserving connectivity would require |V| edges), so it is a tree.

Self-Assessment and Remediation​

Mastery Level (90-100% correct):

  • Ready to advance with confidence. Proceed to Module 4 (Dynamic Programming).

Proficient Level (75-89% correct):

  • Review only the missed concept pages and redo two problems of each missed type. Most common remediation needs here are the running-time derivations (Q6, Q11) and the flow problem (Q13-Q15).

Developing Level (60-74% correct):

  • Rework Practice pages 2 (shortest paths and MST) and 3 (flow and matching), plus Code Katas 3, 4, 5, and 7.
  • Write the cut-property and cycle-property arguments by hand until they are automatic.

Insufficient Level (<60% correct):

  • Return to the concept sequence and rebuild the model-first habits before advancing.
  • Reimplement BFS, DFS, Dijkstra, and Kruskal from scratch until each fits in one uninterrupted session.
  • Rework the modeling drills in Practice page 3 until you can state (V, E, s, t, c) for each problem without hesitation.