Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 6

Dynamic programming describes a problem by reusable subproblem states and a recurrence, computing each required state once through memoization or a bottom-up order. Its benefit comes from sharing answers to overlapping subproblems.

The principle of optimality says that, after the information needed by a state has been fixed, the remaining part of an optimal solution is optimal for that state. Otherwise replacing it by a better subsolution would improve the whole solution. A correct state must retain every constraint that can affect later choices.

Both divide-and-conquer algorithms and dynamic programming derive answers from smaller problems. A typical divide-and-conquer algorithm, such as merge sort, splits an instance into separate parts and combines their answers. Dynamic programming additionally identifies repeated states across different decompositions and reuses their answers; matrix-chain multiplication is a standard example.

Thus a recursion tree may repeatedly solve the same state, whereas a dynamic programming table or memoization stores it once. The resulting recurrence and dependency order determine the running time. The principle of optimality supports combining optimal state answers; it does not by itself justify a greedy algorithm.

Three examples of independent sets are $\{A,C\}$, $\{B,D\}$ and $\{C,E\}$: none contains both endpoints of an edge. The maximum independent sets areThe triangle on $\{A,D,E\}$ contributes at most one vertex, and the path on $\{B,C,F\}$ contributes at most two, giving the upper bound three. Both displayed sets attain it. A three-element choice cannot use $A$, since that excludes $B$ and leaves at most one of the adjacent vertices $C,F$. Consequently it must use $D$ or $E$, together with both $B,F$; these are the only two choices. In particular, the maximum independent set is not unique.

Highlighted vertices give the two possible optimal choices. The third side of the left triangle rules out choosing both $D$ and $E$.

No. A tree consisting of a single edge $uv$ has the two maximum independent sets $\{u\}$ and $\{v\}$. Each has size one, and neither can be enlarged because $u,v$ are adjacent. Thus even a two-vertex tree gives a counterexample to uniqueness.

Choose a root. For each vertex $v$, define $I(v)$ as the maximum size in its descendant subtree when $v$ is included, and $O(v)$ as that size when $v$ is excluded. For its children $w$,A leaf has $I=1,O=0$. If $v$ is included, all its children must be excluded. If $v$ is excluded, either child state is allowed. Different child subtrees have no edges between them because the graph is a tree, so their contributions can be optimized independently. This proves the recurrence by structural induction.

Evaluate the two states in postorder traversal. At root $r$, the answer is $\max \{I(r),O(r)\}$. For reconstruction, pick an attaining root state; an included vertex forces every child to its excluded state, while an excluded vertex permits each child to choose its larger state. Record the included vertices during this second traversal, breaking ties consistently.

With adjacency lists, rooting, state evaluation and reconstruction each take $O(|V|+|E|)=O(n)$ time, with $O(n)$ stored states and output. This is maximum independent set in a tree.

The source describes an independent set as a proper subset. For a tree with at least one edge, every independent set is automatically proper, so the algorithm meets that convention. If it is enforced literally for the single-vertex tree, return the empty set of size zero there; the usual non-strict subset convention would instead return its one vertex.