Algorithms

The algorithm walks once through the array, comparing each adjacent pair \((a_{i}, a_{i+1})\), and stops as soon as a pair breaks the order. The worst case is an array that really is sorted (or breaks the order only at the very end): all \(N-1\) pairs must then be compared before the algorithm can answer.

So the worst-case time grows linearly with \(N\). It is \(\Theta(N)\), which means it is both \(O(N)\) and \(\Omega(N)\).

B fails because no method can do better: an element that is never examined could break the order, so the time is also \(\Omega(N)\). C and D fail because a single pass is \(O(N)\).

Answer: A

Divide both sides by \(n\): \(\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1\). Writing \(S(n) = T(n)/n\), this is \(S(n) = S(\sqrt{n}) + 1\): each step takes a square root and adds 1.

For \(n = 2^{2^{k}}\), taking the square root \(k\) times brings \(n\) down to a constant, so \(S(n) = \Theta(k) = \Theta(\log \log n)\) and \(T(n) = n\,S(n) = \Theta(n \log \log n)\).

In the recursion tree, every level does exactly \(n\) work in total (for example \(\sqrt{n}\) subproblems of size \(\sqrt{n}\) cost \(\sqrt{n} \cdot \sqrt{n}\)), and there are \(\log \log n\) levels.

Answer: A

In a BFS tree the depth of every vertex equals its shortest distance from \(v\), and any edge \((u, w)\) forces \(\text{dist}(w) \le \text{dist}(u) + 1\).

• C is true. A forward edge \((u, w)\) leads to a descendant \(w\) of \(u\) that is not its child, so \(w\) is at least two levels below \(u\) in \(T\). The edge itself gives \(\text{dist}(w) \le \text{dist}(u) + 1\), a contradiction.
• A and D are false: with the edges \(v \to u\) and \(u \to v\), both searches give the tree \(v \to u\), and \(u \to v\) is a back edge.
• B is false: with the edges \(v \to a\), \(v \to b\) and \(b \to a\), a DFS that visits \(a\) first builds the tree \(v \to a\), \(v \to b\), which is also the BFS tree, and \(b \to a\) is a cross edge.

Answer: C

A DFS of an undirected graph grows one tree for each connected component: a new tree starts only when no unvisited vertex is reachable from the earlier ones. So the number of trees in the DFS forest equals the number of components.

A tree on \(t\) vertices has \(t - 1\) edges, so a forest with \(n\) vertices and \(c\) trees has \(n - c\) edges:

\[100 - c = 40 \quad\Rightarrow\quad c = 60\]

Edges of \(G\) that are not in the forest (back edges) do not change this, so \(G\) has 60 connected components.

Answer: 60

The elements that are not replaced keep their values and positions, so they must already form a non-decreasing subsequence. Conversely, any kept non-decreasing subsequence works: every other element can be replaced by a value between its kept neighbours, since equal values are allowed. So the distance is the array length minus the length of the longest non-decreasing subsequence.

In \([2, 5, 3, 1, 4, 2, 6]\) the longest one is \(2, 3, 4, 6\), of length 4; no subsequence of length 5 is non-decreasing. Replacing the other three elements (5, 1 and 2) by, say, 3, 4 and 5 gives \([2, 3, 3, 4, 4, 5, 6]\).

Distance \(= 7 - 4 = 3\).

Answer: 3

Think of Kruskal’s algorithm, which takes the cheapest edges first.

• The four weight-1 edges \(ab, af, cd, de\) form no cycle, so every minimum spanning tree contains them. They leave three components: \(\{a, b, f\}\), \(\{c, d, e\}\) and \(\{g\}\).
• Two more edges are needed, and all weight-2 edges meet \(g\): \(ga, gb, gf\) reach the first component and \(gc, gd, ge\) the second. A tree takes exactly one from each group, since two from the same group would close a cycle.
• The weight-3 edges are never used.

So there are \(3 \times 3 = 9\) minimum spanning trees, each of weight 8.

Answer: 9