Official practice exam 2

• Run DFS. Color each newly visited vertex the opposite color of its parent (blue/green). Restart with any color in each new tree.
• Then scan every edge. If some edge has both ends the same color, the graph is not bipartite. Otherwise it is.

Answer: DFS 2-coloring plus an edge check, \(O(|V|+|E|)\).

• (⇒) Every edge switches sides, so a cycle gets back to its start only after an even number of steps.
• (⇐) Prove the contrapositive: not bipartite ⇒ odd cycle.
• Run the DFS coloring. Not bipartite, so some edge \(\{u,v\}\) has both ends the same color.
• In an undirected DFS every non-tree edge is a back edge, so say u is an ancestor of v.
• Same color means depth(v) − depth(u) is even, so the tree path from u to v has an even number of edges.
• That path plus the edge \(\{u,v\}\) is a cycle with an odd number of edges.

• At least 3: an odd cycle can't be 2-colored.
• 3 is enough. Delete one edge \(\{u,v\}\) of the odd cycle. Now there's no odd cycle, so 2-color it by (b).
• If u and v ended up the same color, recolor v with the third color.

Answer: 3.

• Vertex = state \((a,b,c)\) = pints in the (10, 7, 4) containers, with \(a+b+c=11\), \(0\le a\le10\), \(0\le b\le7\), \(0\le c\le4\).
• Directed edge \(x\to y\) if one pour turns state x into state y.
• Question: is some vertex with \(b=2\) or \(c=2\) reachable from \((0,7,4)\)?
• Algorithm: explore (DFS) or BFS from \((0,7,4)\), linear in the size of the graph.
• It is reachable: (0,7,4) → (4,7,0) → (10,1,0) → (6,1,4) → (6,5,0) → (2,5,4) → (2,7,2).

Answer: reachability in the state graph, solved with DFS or BFS. Yes, 2 pints is possible.

• As stated, yes: there could be a negative cycle through s (an edge into s plus a very negative edge out of s).
• Say that first, then assume no negative cycle. Now Dijkstra works.
• Dijkstra's proof needs one fact: when v has the smallest estimate outside the finished set S, the path through S to v is shortest.
• Suppose some other path to v were shorter. With no negative cycles it can be taken simple, so it never returns to s.
• It leaves S at some edge \((i,j)\). Its length up to j is at least j's estimate, which is at least v's estimate (v had the smallest).
• Every edge after j is positive, because only edges out of s are negative. So the path to v is no shorter than v's estimate. Contradiction.

Answer: it can fail only if there's a negative cycle through s. With no negative cycle, Dijkstra is correct.

• Bellman–Ford, but stop after k rounds instead of \(|V|-1\).
• Set dist(u) = 0, everything else ∞. Repeat k times: update every edge \((x,y)\): \(\text{dist}(y)=\min(\text{dist}(y),\ \text{dist}(x)+\ell(x,y))\), and record prev.
• Invariant: after round i, dist is correct for every vertex whose shortest path has at most i edges. So k rounds are enough.
• Follow prev back from v to get the path.

Answer: k rounds of Bellman–Ford, \(O(k|E|)\).

• The heaviest edge can be a bridge, and every spanning tree must use a bridge.
• Triangle a, b, c with weights 1, 2, 3, plus edge (c, d) of weight 10. \(|E| = 4 > |V|-1 = 3\), and (c, d) is in every MST.

Answer: false.

• Suppose e = (u, v) is in an MST T. Removing e splits T into two parts.
• The rest of the cycle goes from u to v, so it has another edge e′ crossing between the parts, and \(w(e') < w(e)\).
• T − e + e′ is a lighter spanning tree. Contradiction.

Answer: true.

• Run Kruskal and break ties so e comes first. The first edge Kruskal looks at is always added.
• Or: cut property with a cut that separates e's endpoints. e is a lightest edge across it.

Answer: true.

• Suppose an MST T doesn't contain e. T + e has a cycle.
• Every other edge on that cycle is strictly heavier than e. Remove one: the result is a lighter spanning tree. Contradiction.

Answer: true.

• Let \(F = T\cap H\).
• Take any \(e\in F\). Removing e from T splits V into a cut \((S, V-S)\). Among T's edges, only e crosses it.
• e is a lightest edge of G across this cut. If a crossing edge f had \(w(f) < w(e)\), then T − e + f would be lighter.
• H's edges are a subset of G's, so e is still a lightest edge of H across the cut, and no other edge of F crosses it.
• Add F's edges one at a time. Each step is the cut property in H: X ⊆ some MST of H, e lightest across a cut X doesn't cross ⇒ X ∪ {e} ⊆ some MST of H.

Answer: by induction with the cut property, F is in some MST of H.

• Subproblem: \(P(x,y)\) = best return from an x × y piece, for \(1\le x\le X\), \(1\le y\le Y\).
• Recurrence: \(P(x,y)\) is the best of three options (an empty max counts as 0):
  • Sell it whole: \(\max c_i\) over products with \(a_i\le x,\ b_i\le y\).
  • Cut the x side at h: \(\max_{1\le h<x} P(h,y)+P(x-h,y)\).
  • Cut the y side at w: \(\max_{1\le w<y} P(x,w)+P(x,y-w)\).
• If products can be rotated, also allow \(b_i\le x,\ a_i\le y\).
• Fill in increasing x, then y. Answer is \(P(X,Y)\).
• XY subproblems, each \(O(X+Y+n)\) work.

Answer: \(O(XY(X+Y+n))\), pseudo-polynomial.

• Subproblem: for \(S\subseteq\{1..n\}\) and \(j\in S\), \(C(S,j)\) = best (value − cost) of a path that starts at home, visits exactly the sales in S, and ends at \(g_j\).
• Base: \(C(\{j\},j)=v_j-d_{0j}\).
• Recurrence: \(C(S,j)=v_j+\max_{i\in S-\{j\}}\big[C(S-\{j\},i)-d_{ij}\big]\). Fill in order of increasing \(|S|\).
• Answer: \(\max\{0,\ \max_{S,\,j\in S} C(S,j)-d_{j0}\}\). The 0 is staying home.
• \(n2^n\) subproblems × \(O(n)\) each.

Answer: subset DP, \(O(n^2 2^n)\).