Algorithms

\(T\) is a subgraph of \(G\), so every path between \(u\) and \(v\) in \(T\) is also a path in \(G\). Hence the shortest path in \(G\) can never be longer than the one in \(T\): \(d_1(u, v) \le d_2(u, v)\).

Equality is not guaranteed. Take a triangle \(x, y, z\) with \(w(x, y) = w(y, z) = 1\) and \(w(x, z) = 1.5\); the MST keeps the two edges of weight 1. Then \(d_1(x, z) = 1.5\) but \(d_2(x, z) = 2\), which rules out (A) and (C), while \(d_1(x, y) = d_2(x, y) = 1\) rules out (D).

Answer: B

Divide both sides by \(2^{n}\) and put \(S(n) = T(n)/2^{n}\). The recurrence becomes \(S(n) = S(n - 1) + n\) with \(S(0) = 1\).

So \(S(n) = 1 + (1 + 2 + \dots + n) = 1 + \frac{n(n+1)}{2}\), and \(T(n) = 2^{n}\left(1 + \frac{n(n+1)}{2}\right) = \Theta(n^{2}2^{n})\).

Answer: A

fun() is bubble sort. Each swap exchanges one adjacent out-of-order pair, so it removes exactly one inversion, and the total number of swaps equals the number of inversions in the input.

In a descending array of 30 distinct values every pair is an inversion, so the count is \(\binom{30}{2} = \frac{30 \times 29}{2} = 435\). Pass by pass gives the same total: pass \(i\) makes \(29 - i\) comparisons and every one of them swaps, so \(29 + 28 + \cdots + 1 = 435\).

Answer: 435

The diagonals BD and AC (weights 1 and 3) are in every MST: BD is the unique lightest edge at D (DA = 6, DC = 8) and AC is the unique lightest edge at A (AD = 6, AB = 7). Together they form two pieces, {A, C} and {B, D}.

A spanning tree on 4 vertices has 3 edges, so exactly one more edge must join the two pieces. The candidates are BC = \(x\), AD = 6, AB = 7 and CD = 8. BC is in every MST only if it is strictly the lightest of these, i.e. \(x \lt 6\).

At \(x = 6\), BC ties with AD and {BD, AC, AD} is an MST without BC. So the largest integer value is 5.

Answer: 5

Pick any two elements and compare them once. Because the integers are distinct, one of them is strictly smaller, and that smaller element cannot be the largest in the list: the other element beats it. So one comparison always suffices.

Zero comparisons cannot work, since without any comparison every element we might pick could still be the maximum. Hence the minimum is 1.

\(N - 1\) comparisons are what it takes to find the largest element itself, which is a different task; the question only asks for some element that is not the largest.

Answer: A

• (A) False. In a triangle on \(s, a, b\), DFS from \(s\) may go \(s \to a \to b\), placing \(b\) at depth 2 although the edge \(sb\) puts it at distance 1.
• (B) True. If \(u\) is discovered before its neighbour \(v\), then \(v\) is discovered before \(u\) finishes, so \(v\) becomes a descendant of \(u\). Every non-tree edge therefore joins a vertex to one of its ancestors; undirected DFS has no cross edges.
• (C) True. BFS depths are shortest distances from \(s\), and an edge \((u, v)\) gives \(d(v) \le d(u) + 1\) and \(d(u) \le d(v) + 1\).
• (D) True. Restarting the search (BFS or DFS) from each unvisited vertex visits exactly one connected component per start.

Answer: B, C, D

MSTs stay. Every spanning tree of a connected graph with \(n\) vertices has exactly \(n - 1\) edges, so every spanning tree gets heavier by the same amount, \((n - 1)\alpha\). Their order by weight does not change, so every MST remains an MST.

SPs can change. A path with \(k\) edges gets heavier by \(k\alpha\), so paths with more edges are penalised more. Take edges \(uv\) and \(vw\) of weight 1 and an edge \(uw\) of weight 3. The shortest path from \(u\) to \(w\) is \(u, v, w\) with weight 2. After adding \(\alpha = 2\) it weighs 6, while the single edge \(uw\) weighs 5, so the old SP is no longer shortest.

Answer: C

• P: link the tail of one list to the head of the other and update the tail pointer. That is a fixed number of pointer changes: \(\Theta(1)\).
• Q: copy both arrays into one array of size \(2n\) and run bottom-up build-heap, which takes linear time: \(\Theta(n)\). Inserting the \(n\) keys one at a time would cost \(\Theta(n \log n)\), so that bound (B, C) is not the best.
• R: an in-order traversal of each tree gives two sorted lists in \(\Theta(n)\). Merge them in \(\Theta(n)\), then build a BST from the merged list (middle element as root, recursively) in \(\Theta(n)\). Inserting one tree’s keys into the other would give the slower \(\Theta(n \log n)\) or \(\Theta(n^{2})\) of D and C.

Answer: A

Search in three binary-search phases:

1. Find the peak: compare \(A[m]\) with \(A[m+1]\). If \(A[m] < A[m+1]\) the peak is to the right, otherwise at \(m\) or to its left. Each comparison halves the range: \(O(\log n)\).
2. Binary search the increasing part \(A[1..i]\).
3. Binary search the decreasing part \(A[i+1..n]\).

That is \(O(\log n)\) comparisons in all, and no algorithm can do better: a sorted array is itself bitonic (take \(i = n\)), and searching a sorted array needs \(\Omega(\log n)\) comparisons. So the bound is \(\Theta(\log n)\); \(\Theta(\log^{2} n)\) is achievable but not the best, and \(\Theta(1)\) is impossible.

Answer: D

On a tree, a vertex farthest from any start vertex is always an end of a longest path, so the second BFS measures the tree's diameter: the largest distance, in edges, between two vertices.

In the figure, a longest path starts at the lowest leaf on the far left, goes up to its neighbour and the left branching vertex, crosses to the central branching vertex, and follows the right branch through two more vertices to the rightmost leaf: 6 edges. The topmost leaf also reaches the rightmost leaf in 6 edges, and no two vertices are farther apart.

So the output is 6 whichever start vertex \(v\) is chosen.

Answer: 6