Past exam of the computer science course of the University of Oxford / 2019

Source paper: released Oxford examination archive, member 2018/T/a16156w1.pdf. The actual cover identifies the Second Public Examination, Trinity Term 2019, Friday 28 June, 09:30–11:30; the archive directory predates that cover year. All three questions are covered below, including every printed Roman part.

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

Sum net outflow over all vertices in the source side $S$. An internal directed edge occurs once positively and once negatively, so it cancels. All internal vertices have zero net outflow by flow conservation, and the sink is outside $S$. ThereforeThe second sum is nonnegative, while every term in the first satisfies its capacity constraint. Consequently,This is direct accounting from flow conservation; it does not invoke the max-flow min-cut theorem.

A path-cycle matching is exactly an edge subset whose resulting subgraph has maximum degree at most two: every nontrivial connected component of a graph of this form is a graph path or a cycle in a graph. Thus the task is a bipartite b-matching problem with bound two at every vertex.

Find a bipartition $L,R$, orient every original edge from $L$ to $R$, and add a source $s$ and sink $t$. Give each arc $s\to u$, for $u\in L$, flow network edge capacity two; each original arc $u\to v$ flow network edge capacity one; and each arc $v\to t$, for $v\in R$, flow network edge capacity two. Compute an integral maximum flow and select the original edges whose flow is one. The integral max-flow theorem guarantees such an integral optimum.

By flow conservation, at most two selected edges touch each vertex, so they decompose into the required vertex-disjoint paths and cycles in a graph. Conversely, any permissible path-cycle matching gives a feasible flow: send one unit through its middle arc for each selected edge, with the outside arc amounts equal to the endpoint degrees. In both directions, the flow value equals the number of selected edges. Maximizing either quantity therefore maximizes the other.

The blue edges in this example form a four-cycle in a graph and a one-edge graph path; the dashed edge is unused. Their five units of flow are optimal: the two left vertices $a,b$ can each contribute at most two selected edges, and $c$ has only one incident edge.

The constructed flow network has $|V|+2$ vertices and $|E|+|V|$ arcs. A polynomial-time algorithm for maximum flow, such as the Edmonds–Karp algorithm, followed by a traversal of the selected subgraph, gives an efficient solution.

Separate the forced integer portion from the choice of rounding direction. Put $p_{ij}=\lfloor a_{ij}\rfloor$ and $q_{ij}=a_{ij}-p_{ij}$. Define residual demandsThese are nonnegative integers, since the original row and column sums are integers. Also ${\sum }_i{r}_i={\sum }_j{c}_j=:T$. Each fractional part satisfies $0\le q_{ij}<1$.

Construct a flow network with a vertex for each row and column, source-to-row arcs of flow network edge capacity $r_i$, row-to-column arcs of flow network edge capacity one exactly where $q_{ij}>0$, and column-to-sink arcs of flow network edge capacity $c_j$. The amounts $q_{ij}$ themselves define a fractional feasible flow of flow value $T$. No flow can exceed $T$, the total source flow network edge capacity. Because all constructed flow network edge capacities are integers, an integral maximum flow also has flow value $T$ and saturates every source and sink arc.

Let $h_{ij}$ be its middle-arc flow, taking $h_{ij}=0$ when that arc is absent. Then $h_{ij}\in \{0,1\}$, and the required answer isAt an already integral entry no middle arc exists, so that entry stays fixed. At a nonintegral entry the two possibilities are precisely its floor and ceiling. Flow conservation gives ${\sum }_j{h}_{ij}=r_i$ and ${\sum }_i{h}_{ij}=c_j$, preserving every original row and column sum.

This is matrix rounding with fixed margins. There are $m+n+2$ vertices and at most $mn+m+n$ arcs. Exact rational arithmetic computes the floors and residual demands in polynomial time in the encoded input length; the resulting flow network edge capacities are small integers, so there is no need to scale by a potentially large common denominator.

First give $w$ the vote of every voter whose allowed set contains $w$. Let their number be $K$. This loses no possible strict victory: starting with any winning assignment, changing such a ballot to $w$ increases $w$'s score and weakly decreases an opponent's score. Thus a winning assignment exists exactly when one exists with these $K$ ballots fixed.

Every remaining voter must now be assigned to an allowed opponent, and each opponent may receive at most $K-1$ votes. If any allowed set is empty, there is no valid election assignment. With at least two candidates, $K=0$ immediately makes a unique victory impossible. With only the candidate $w$, every nonempty ballot set forces that candidate, so the answer is yes under the question's strict-comparison definition.

For the remaining case $K\ge 1$, make a flow network with a vertex for each remaining voter and each opponent. Add source-to-voter arcs of flow network edge capacity one, voter-to-opponent arcs of flow network edge capacity one for the allowed choices, and opponent-to-sink arcs of flow network edge capacity $K-1$. Compute an integral maximum flow. ThenA flow saturating all voter arcs assigns each remaining voter to exactly one allowed opponent, by integrality and flow conservation. The sink-arc capacity constraints give every opponent strictly fewer than $K$ votes. Conversely, any winning assignment with the fixed $K$ votes defines just such a saturating feasible flow. The flow network has at most $n+m+2$ vertices and $O(n+m+{\sum }_i|C_i|)$ arcs, hence the decision takes polynomial time.

Take $u,v\in P$ and $0\le \lambda \le 1$. Their convex combination satisfiesThus every such convex combination remains in $P$, so $P$ is a convex set. The assertion also holds when $P$ is empty.

An extreme point $p\in P$ cannot be written as a nontrivial convex combination of two distinct points of $P$: if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, then $u=v=p$.

A vertex of a linear polyhedron is a feasible point at which the active constraints include $n$ linearly independent row normals. Equivalently, some $n$ independent bounding hyperplanes intersect uniquely at that point. This definition does not require $P$ to be bounded or full-dimensional. For a linear polyhedron, it is also equivalent to the point uniquely maximizing a suitable linear function: sum the selected active inequalities to construct one such linear function.

Let $p$ be a vertex of a linear polyhedron and choose $n$ independent active constraints, written $Bp=d$, with $B$ invertible. Suppose $p=\lambda u+(1-\lambda )v$, where $u,v\in P$ and $0<\lambda <1$. Each selected inequality has $B_{i}u\le d_i$ and $B_{i}v\le d_i$, whileSince both weights are positive, equality in this weighted upper bound forces $B_{i}u=B_{i}v=d_i$ for every selected row. Hence $Bu=Bv=d$, and invertibility gives $u=v=p$. Therefore every vertex of a linear polyhedron is an extreme point.

No. For the linear polyhedron $P=[0,1{]}^2$, take $c=(1,0{)}^T$ and $x^{\ast }=(1,1/2{)}^T$. The maximum of $c^{T}x$ is one, attained at $x^{\ast }$. Yetso $x^{\ast }$ is not an extreme point, hence not a vertex of a linear polyhedron. An optimal face can contain many points; an arbitrary maximizer need not be one of its vertices of a linear polyhedron.

Only $z,w$ have printed nonnegativity restrictions; $x,y$ are unrestricted. In four-dimensional space, a vertex of a linear polyhedron needs four independent active constraints. There are exactly four available constraints, so all must be active. Solving them givesand therefore the only possible vertex of a linear polyhedron is $(x,y,z,w)=(2,3,0,0)$. It is feasible, and its four active normals are independent, so it is indeed a vertex of a linear polyhedron.

One can also see uniqueness geometrically from the slack variables $s_1=1-2x+y-5w$ and $s_2=3-y-z-w$. The feasible region is in affine bijection with the nonnegative orthant in $(s_1,s_2,z,w)$:That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.

Use the standard maximum form of a linear program convention $\max c^{T}u$ subject to $Mu\le b$ and $u\ge 0$. Split the unrestricted variables as $x=x^{+}-x^{-}$ and $y=y^{+}-y^{-}$, with all four new variables nonnegative. The resulting linear program isIf equality-constraint standard form is preferred, add a nonnegative slack variable to each inequality.

Give the two inequalities nonnegative dual variables $\alpha ,\beta$. The dual linear program isThe paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the dual linear program has $2\alpha =2$, $-\alpha +\beta =3$, $\beta \ge 4$, $5\alpha +\beta \ge 7$ and $\alpha ,\beta \ge 0$. Thus its only feasible point is $(\alpha ,\beta )=(1,4)$, of objective function value $13$.

The point $(1,4)$ satisfies dual feasibility and supplies an upper bound of $13$ by weak duality. Directly, take one copy of the first constraint and four copies of the second:Since $w\ge 0$, the original objective function is at most $13-2w\le 13$. The feasible point $(2,3,0,0)$ attains $13$. HenceThere are also nonvertex optima. In terms of the slack variables, the exact objective function identity isEquality requires $s_1=s_2=w=0$, leaving the entire optimal faceNegative $x$ or $y$ on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.

First suppose the stated nonnegative vectors $y,z$ exist. If $x\in P\cap Q$, multiply $Ax\le b$ by $y^T$ and $Cx\le d$ by $z^T$. Since $x\ge 0$ and $y^{T}A+z^{T}C\ge 0$, this gives the contradictionThus the certificate implies $P\cap Q=\varnothing$.

For the converse, putA common feasible point exists exactly when $Mx\le h$, $x\ge 0$. Introducing a nonnegative vector of slack variables $s$ makes this equivalent toIf this system is infeasible, the nonnegative-equations version of Farkas' lemma supplies an unrestricted vector $u$ such thatSplit $u=(y,z{)}^T$ according to the original two blocks of inequalities. The three conditions become $y,z\ge 0$, $y^{T}A+z^{T}C\ge 0$ and $y^{T}b+z^{T}d<0$, exactly the desired certificate. Both directions are proved. The role of $x\ge 0$ is essential: it is why the combined normal need only be nonnegative rather than zero.^[ref]

Let $B=A^T$ and choose any column probability vector $q$, for example the first coordinate unit vector. Because $A$ has nonnegative entries and each row sums to one, $B$ maps the probability simplexinto itself: $Bv\ge 0$ and $1^{T}Bv=(A1{)}^{T}v=1^{T}v=1$.

The iterates $B^{j}q$ need not converge, so take their arithmetic averages,A telescoping sum givesBoth vectors on the right before subtraction have L1 norm one, so $\Vert B{x}_N-x_N{\Vert }_1\le 2/N\to 0$.

The probability simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by the Heine-Borel theorem. It follows that a subsequence $x_{N_j}$ converges to some $x\in \Delta$. Passing to the limit in the displayed identity, using continuity of the linear map $B$, gives $A^{T}x=Bx=x$, with $x\ge 0$ and ${\sum }_i{x}_i=1$.

This proves stationary distribution existence for a finite Markov chain without any Markov chain irreducibility or aperiodicity assumption. Those stronger hypotheses concern uniqueness and convergence, not the existence required here.

A parameterized decision problem is fixed-parameter tractable if there is an algorithm deciding inputs of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, where $f$ is a computable function and $c$ is a constant independent of $k$. Arbitrarily expensive dependence on the parameter is permitted; putting $k$ in the exponent of $N$ does not by itself establish fixed-parameter tractability.

For a minimization problem with nonnegative costs, a factor-two approximation algorithm runs in polynomial time, always returns a feasible solution, and satisfies $\mathrm{cost}(\mathrm{ALG})\le 2\mathrm{OPT}$ on every feasible input. A feasible solution also satisfies $\mathrm{OPT}\le \mathrm{cost}(\mathrm{ALG})$. If the optimum is zero, the guarantee requires an answer of zero cost.

The vertex cover decision problem takes a finite simple graph $G$ and a nonnegative integer $k$, and asks whether there is a vertex cover of cardinality at most $k$. The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.

For the decision problem, if there are no edges, accept; if there is an edge but $k=0$, reject. Otherwise choose an edge $uv$ and branch: either include $u$ and recurse on $G-u$ with budget $k-1$, or include $v$ and recurse on $G-v$ with budget $k-1$. Accept if either branch accepts. Every vertex cover contains at least one endpoint of $uv$, so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.

The search tree has depth at most $k$ and at most $2^k$ leaves. Processing each node in $O(|V|+|E|)$ time gives $O(2^k(|V|+|E|))$ running time, establishing fixed-parameter tractability.

For optimization, greedily build a maximal matching $M$: repeatedly select an edge and discard every edge touching either endpoint. Return the set $C$ of all endpoints of $M$. Any edge with neither endpoint in $C$ could be added to $M$, contradicting maximality; thus $C$ is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. ThereforeThe greedy construction takes polynomial time, and can be implemented in $O(|V|+|E|)$ with adjacency lists. It needs only a maximal matching, not a maximum matching.

If the basis has $r\le k$ members, it has $2^r$ subsets, each specifying a possible union. Different subsets can produce the same union, so the number of distinct generated sets is at most $2^r$. Consequently,Here $\mathcal{F}$ is a set family of distinct sets. If a representation lists duplicate input sets, discard those duplicates before applying this bound. The empty union is included.

Write $U^{\prime }=U\setminus \{y\}$ and ${\mathcal{F}}^{\prime }=\{B\setminus \{y\}:B\in \mathcal{F}\}$. If $\mathcal{A}$ is a basis for the original instance, replace each member $A$ by $A\setminus \{y\}$. Deletion commutes with unions, so the resulting family generates every member of ${\mathcal{F}}^{\prime }$ and has at most $|\mathcal{A}|$ members.

Conversely, take a basis ${\mathcal{A}}^{\prime }$ for the reduced instance. Lift each of its members byIf $B\setminus \{y\}$ is represented as a union of reduced basis sets, the same union of their lifts agrees with $B$ on $U^{\prime }$. It contains $y$ exactly when one of the selected reduced basis sets contains $x$, namely exactly when $x\in B$. By the assumed incidence equivalence in a set family, this occurs exactly when $y\in B$. Thus the lifted union is precisely $B$, and the lifted basis has no more members.

Therefore deleting $y$ preserves the yes/no answer with the same parameter $k$. The reverse construction does not require a reduced basis set to be an input set.

First discard duplicate input sets, and let $m=|\mathcal{F}|$. If $m>2^k$, reject by part (i); this rejection can be encoded as the fixed no-instance $U=\{u\}$, $\mathcal{F}=\{\{u\}\}$, $k=0$ of the set basis problem. Otherwise, represent each ground element $x$ by its incidence columnKeep one element from each class of equal columns. By repeatedly applying part (ii), this preserves the answer. The reduced number of elements $q$ satisfiesRelabel these representatives and store their reduced incidence matrix. Its $mq$ membership bits, the dimensions and $k$ have encoded length bounded solely by a computable function of $k$; the leading incidence bound is $2^{k+2^k}$. Thus this is a kernelization, even though it is not a polynomial kernel. Forming columns and grouping identical ones takes polynomial time in the original explicit input length. To test $m>2^k$, compare bit lengths or truncate exponentiation at $m+1$; never construct an enormous $2^k$ merely to perform this preprocessing comparison.

For completeness, the bounded instance can be solved explicitly. Enumerate all ordered lists of $k$ subsets of the $q$-element ground set, allowing empty members to pad shorter bases. There are at most $2^{kq}$ such lists. For a candidate basis and each reduced input set $B$, form the union of every candidate basis set contained in $B$. If this union equals $B$, a representation exists; if it does not, no union of that candidate's members can represent $B$, because any member not contained in $B$ would add a forbidden element. Testing every $B$ therefore verifies a candidate in time polynomial in $m,q,k$.

The preprocessing is polynomial in the original input length, and the remaining search depends only on $k$. Hence the set basis problem is fixed-parameter tractable with respect to $k$. Empty input families and $k=0$ are covered by the same empty-union convention.

Assume the standard nonempty instance convention $1\le k\le n$, and set $d(v,v)=0$. Start with no centers. Pick any city still farther than $2r^{\ast }$ from every selected center, add it as a center, and mark every city within distance $2r^{\ast }$ of it as covered. Stop when all cities are covered.

Distinct chosen centers have pairwise distance greater than $2r^{\ast }$. Fix an optimal set of $k$ centers and assign each city to one optimal center within distance $r^{\ast }$. Two cities assigned to the same center have distance at most $2r^{\ast }$ by the triangle inequality. Thus no two chosen centers can be assigned to that same optimal center. The pigeonhole principle shows that the greedy procedure selects at most $k$ centers and has radius at most $2r^{\ast }$. If fewer than $k$ are selected, add arbitrary distinct cities; this cannot worsen the radius.

With the supplied radius, a straightforward implementation updates coverage in $O(n)$ time per selected center, hence takes $O(nk)$ distance tests. The argument also handles $r^{\ast }=0$. It is the packing bound underlying the metric k-center problem.

The optimum radius is a distance from some city to a selected city, so it belongs toSort the distinct values of $D$, try them in increasing order, and run part (i)'s greedy procedure with each trial value $r$. Declare a trial successful when all cities are covered using at most $k$ centers; stop a failed trial as soon as a $(k+1)$st center would be selected. The trial $r=r^{\ast }$ must succeed by part (i), so the first successful value $\hat{r}$ satisfies $\hat{r}\le r^{\ast }$. Its output hasThere are $O(n^2)$ candidate distances and $O(n^2)$ work per trial, giving a polynomial-time algorithm with running time $O(n^4)$, plus sorting. Success at $r$ need not mean that radius $r$ itself is feasible; only the radius-$2r$ guarantee is used.

A faster alternative is the farthest-first traversal. Choose any first center, then repeatedly choose a city farthest from its nearest current center until $k$ have been chosen. Let $R$ be the resulting radius. If $R>0$, adjoin a city attaining that distance. At every earlier selection, the maximum distance to the then-current center set was at least $R$, so all pairs among these $k+1$ cities are at distance at least $R$. Two belong to the same optimal radius-$r^{\ast }$ closed ball, giving $R\le 2r^{\ast }$ by the triangle inequality. If $R=0$, the guarantee is immediate. Maintaining nearest-center distances gives $O(nk)$ distance evaluations without knowing $r^{\ast }$.

Source paper: released Oxford examination archive, member 2018/T/a16607w1.pdf. Its native cover identifies the Second Public Examination, Trinity Term 2019, Monday 3 June, 14:30–16:30. The archive directory predates the actual cover year. All three questions and every unnumbered requirement within their printed parts are addressed. The blocks-world figure is intact.

The first assertion is false. Give the root a first child that is a goal state of cost ten and another child leading to many cheaper non-goal search nodes. Depth-first search can take the first child and stop immediately. A-star search with the admissible heuristic $h=0$ behaves as uniform-cost search and expands the cheaper non-goal search nodes before selecting that goal. Thus an admissible heuristic does not make A-star search expand fewer nodes than every possible depth-first search ordering. The latter need not return an optimal solution.

The second assertion is true under the usual finite-branching factor assumption. Breadth-first search orders by search depth, not path cost. Every finite depth contains finitely many search nodes, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite branching factor would invalidate the argument irrespective of step costs.

The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed. If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost cycle in a graph that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.

Iterative deepening depth-first search increases a bound on the number of actions, usually through $0,1,2,\dots$. Iterative lengthening search instead bounds accumulated path cost; after an unsuccessful pass, its next bound is the least path cost among the rejected search nodes. Thus it can distinguish shallow expensive paths from deeper cheap ones.

Both repeatedly perform depth-first search and retain its small active-path storage, trading repeated work for avoiding a large search frontier. With unit step costs their bounds coincide. With unequal positive step costs, iterative deepening depth-first search finds a solution with the fewest actions, while iterative lengthening search, under the termination conditions discussed next, finds one of least total cost. Real-valued path costs can make iterative lengthening search perform many more passes than the depth-bounded method.

Start the threshold at zero and let $C^{\ast }$ be the least solution cost. Suppose an unsuccessful pass has threshold $L<C^{\ast }$. Along an optimal action sequence, take the first prefix whose path cost exceeds $L$. Its preceding prefix is explored, so that rejected prefix contributes to the next-threshold calculation. Positive step costs imply that its cost is at most $C^{\ast }$. Therefore the next threshold is also at most $C^{\ast }$.

By induction, no threshold used before the first solution exceeds $C^{\ast }$. A returned goal state therefore has cost at most $C^{\ast }$; by the definition of $C^{\ast }$ it cannot cost less. The first returned solution is optimal.

The termination qualification matters. In a finitely branching problem with step costs at least $ϵ>0$, a threshold $L$ admits only depths up to $\lfloor L/ϵ\rfloor$, so each pass is finite and only finitely many path costs precede $C^{\ast }$. These conditions establish completeness as well. Strict positivity alone on an arbitrary infinite tree is insufficient: an infinite branch with costs $1/2,1/4,1/8,\dots$ can remain below a finite threshold and trap depth-first search. The optimality argument above is valid whenever the required passes terminate; a finite graph with finitely many strictly positive action costs supplies a uniform positive lower bound.

With initial threshold zero and unit step costs, the thresholds are $0,1,\dots ,d$, so there are $d+1$ passes. Starting the first pass at one instead omits the zero-threshold pass when the root is not a goal.

At depth $i$, at most $b^i$ search nodes are admitted in each pass with threshold at least $i$. Across all passes, the full-to-cutoff visit bound isThis is attained when the only depth-$d$ goal is visited last. If a goal test occurs before expansion, the goal is visited but not expanded, giving the corresponding worst-case expansion countFor $b\ne 1$, the visit bound is $V(b,d)=[b^{d+2}-(d+2)b+d+1]/(b-1{)}^2$, hence the worst-case number expanded is $\Theta (b^d)$ for fixed $b>1$. For $b=1$, it is $\Theta (d^2)$. An earlier goal reduces the final pass, so its exact count cannot be inferred from $b,d$ alone. Children generated and immediately rejected above a threshold are not counted as expanded; counting those generated nodes adds the corresponding branching overhead.

A lower bound on individual step costs does not bound the difference between consecutive path cost thresholds. Two different paths can have costs differing by an arbitrarily small amount, even though every edge costs at least $ϵ$.

Let $C^{\ast }$ be the optimal solution cost. Every unsuccessful threshold is the path cost of some search node below $C^{\ast }$. Such a node has depth strictly less than $C^{\ast }/ϵ$. For a uniform branching factor $b>1$, the number of passes is therefore bounded byIf a solution of depth $d$ exists, each of its edges costs at most one, so $C^{\ast }\le d$ and an associated bound is $O(b^{\lceil d/ϵ\rceil })$ passes. If $d$ denotes the optimal solution's depth, the same inequality applies. With no solution-cost or solution-depth bound, $b$ and $ϵ$ alone give no finite uniform iteration bound.

The exponential behavior is possible. Put a depth-$d$ goal on a branch with unit costs and let a large competing subtree use costs just above $ϵ$. Choose tiny distinct perturbations so that its many search nodes below cost $d$ have distinct path costs. The threshold can advance through those costs one at a time. Thus a bound such as $\lceil d/ϵ\rceil$ on the number of passes is unjustified: it bounds admitted depth, not the number of distinct costs. For $b=1$ there is only one path, so the corresponding count is linear in the admitted depth rather than exponential.

For the three-colourability problem, represent a candidate by a complete colour assignment $c:V\to \{r,g,b\}$, initially chosen at random. Give it the conflict objective functionA neighbor changes the colour of one vertex to either other colour. For hill climbing, maximize $-H$, or equivalently repeatedly choose a recolouring that reduces $H$. One can inspect all $2|V|$ neighbors, or focus on conflicted vertices and evaluate their alternative colours using only incident edges. Stop successfully as soon as $H=0$, which is exactly a proper graph colouring with three colours.

If no improving move exists at positive $H$, the method is stuck in a local minimum. Random restarts, limited sideways moves or other exploratory local search choices can reduce this failure mode, but do not turn a finite unsuccessful run into a proof of impossibility. On a graph with no proper graph colouring using three colours, every complete colouring has $H>0$, so this procedure cannot return a valid colouring. Conversely, a positive-conflict stopping point also occurs on some graphs admitting a proper graph colouring with three colours. Failure of hill climbing alone does not certify non-colourability. For a concrete trap, use a bipartite graph with three vertices on each side and every cross-edge, and give each side one vertex of each colour. There are three conflicts. Recolouring any single vertex leaves it with exactly one same-colour neighbor, so no single change improves $H$, even though colouring each whole side differently solves the instance.

For an action sequence $\pi$, let $T_{\pi }(B)$ be the set of all physical states obtainable by applying it to the initial belief state $B$. Under a deterministic model this is an image; for nondeterministic outcomes it is the union of all permitted images. For $B^{\prime }\subseteq B$,If each action is applicable to every current possibility from $B$, it is also applicable to every possibility from $B^{\prime }$. If the final belief state for $B$ is contained in the physical goal set $G$, then $T_{\pi }(B^{\prime })\subseteq G$. Thus the same plan solves every subset of $B$.

Nothing comparable follows for an arbitrary superset. For example, let an action take $s_1$ to a goal and leave $s_2$ at a non-goal. It solves $\{s_1\}$ but not $\{s_1,s_2\}$. A larger belief state is solved by this particular sequence exactly when all added states also permit it and end in $G$. It may succeed on some supersets and fail on others; it cannot be guaranteed merely from success on $B$.

Use incremental belief-state search to find only the initial possibilities needed to constrain a successful plan. Choose one possible initial state, or a small subset $B_0$ of the full initial belief state $B$. Find an action sequence solving this restricted problem, then simulate it from every state in $B$.

If validation succeeds, return the candidate. Otherwise choose a state that makes some action inapplicable or ends outside the goal, add it to $B_0$, and search again for a plan that works for every selected state. Replanning can revise the earlier sequence; merely appending a repair to one arbitrary candidate can miss solutions. For a finite initial belief state, there are at most $|B|$ additions before every initial possibility has been included. If a complete restricted solver proves that even the selected subset is unsolvable, part (g) shows that the full problem is unsolvable.

The benefits are smaller intermediate belief states, fewer states propagated through candidate actions, and avoidance of unnecessary portions of the full power set search space. One physical-state counterexample can eliminate many invalid candidates. The worst case can still require all initial states; the method exploits instances where a few representative possibilities already force a plan that passes universal validation.

Let $Q=\{1,\dots ,n{\}}^2$ be the board squares and let $\mathrm{Attack}(p,q)$ mean that the absolute coordinate differences are $(1,2)$ or $(2,1)$.

One variable per knight. Use $X_1,\dots ,X_k$, with each constraint domain equal to $Q$. For every pair $i<j$, requireEvery satisfying assignment places $k$ distinct nonattacking knights, and any such placement gives an assignment after labelling its knights. This has only $k$ variables and $O(k^2)$ binary constraints, but domains of size $n^2$. Relabelling the knights gives $k!$ assignments for the same unlabelled board, so the representation contains considerable redundancy.

One Boolean variable per square. Use $Y_q\in \{0,1\}$ for every $q\in Q$. Impose the cardinality constraintand for every knight-attack pair $p,q$ impose $Y_p+Y_q\le 1$. There are $n^2$ variables, each with a two-element constraint domain, and only $O(n^2)$ local attack restrictions, because each square attacks at most eight others. The single counting constraint is a global constraint, not a binary constraint.

The square encoding avoids knight-label redundancy and has sparse local attack relations; the knight encoding uses fewer variables when $k$ is small and makes single-knight moves natural. Both are exact representations of the nonattacking knights problem. Neither may impose one knight per row: several knights can legally share a row.

Use the knight-variable representation and build a placement one knight at a time. The initial state is the empty placement. An action places the next knight on an empty square attacking no previously placed knight; the search transition model appends that square. The goal test is that $k$ knights have been placed. Each action adds exactly one, so any solution has depth $k$.

Put $N=n^2$. At depth $j$, there are at most $N-j$ choices, hence branching factor at most $N$. A coarse search tree size bound is $1+N+\cdots +N^k$. Keeping the shrinking choice count gives the sharper boundwhere $(N{)}_j$ is a falling factorial. This counts ordered placements before attack pruning.

For a full expansion down to depth $k$, the number of depth-$k$ leaves is at most $(N{)}_k$, or approximately $n^{2k}$ when $k$ is small relative to $N$. If $I_k$ denotes the number of legal unlabelled $k$-knight placements, the exact number of legal depth-$k$ leaves is $k!I_k$. There can also be earlier dead-end leaves: a legal placement may leave no further nonattacking square. Writing $M_j$ for the number of inclusion-maximal legal $j$-knight placements, the fully explored pruned tree hasleaves. Its leaf count is still at most the unpruned $(N{)}_k$, since each early leaf replaces a disjoint nonempty subtree of the unpruned tree. Breadth-first search that stops at its first goal can construct less of the last layer; if no solution exists, it exhausts the reachable partial placements.

Identifying different insertion orders changes the representation. With a state that is an unlabelled set of occupied squares and repeated-state elimination, the corresponding depth-$k$ state bound is $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$, with $I_k$ legal goal states. The factorial and binomial bounds refer to these different representations, not competing counts of the same tree.

Backtracking assigns one variable at a time and abandons a partial assignment as soon as it cannot extend to a solution. With forward checking, placing a knight deletes its occupied and attacked squares from every remaining knight's constraint domain. An empty constraint domain rejects the branch immediately; stronger constraint propagation, such as arc consistency, can detect additional incompatibilities among future choices.

This combines early rejection with depth-first storage. It retains the current assignment and domain changes rather than the entire breadth-first layer of partial placements. A direct knight-variable implementation uses $O(k{n}^2)$ space for explicit domains, plus its assignment and restoration trail, instead of an exponentially large breadth-first search search frontier. Propagation has a computational cost and does not guarantee improvement on every input, but often prevents exploration of vast inconsistent subtrees.

The minimum remaining values heuristic selects an unassigned variable with the fewest currently legal values, exposing the likeliest failure first. The degree heuristic selects a variable constrained to the largest number of other unassigned variables, often breaking minimum remaining values heuristic ties. Degree is measured in the remaining constraint graph, not by counting assigned neighbors. In the symmetric knight-variable encoding the remaining degrees can all tie, so the heuristic need not discriminate there.^[ref]

A useful local search state is any occupied-square subset $S\subseteq Q$, allowing temporary attacks. Let $C(S)$ count unordered attacking pairs and $N=n^2$. MaximizeACTIONS can offer insertion at an empty square, deletion of an occupied square, and relocation of one knight to an empty square. RESULT is respectively $S\cup \{q\}$, $S\setminus \{p\}$, and $(S\setminus \{p\})\cup \{q\}$. Insertions and deletions alone connect the whole state space; relocation is a useful additional proposal.

Every conflicting state has $F(S)\le N-(N+1)<0$, whereas the empty board has score zero. Every conflict-free state has score exactly its knight count. Hence every global maximizer is a maximum-size nonattacking placement. If a knight participates in $r\ge 1$ conflicts, deleting it changes the score by $-1+(N+1)r>0$, so a positive-conflict local stopping point cannot persist when improving deletions are considered.

From a random board, choose score-improving moves, with random restarts or occasional non-improving proposals to escape poor conflict-free local optima. A maximal placement is not necessarily a maximum placement: accepting only legal insertions can get stuck too early. This objective function defines the intended optimization precisely; a finite heuristic run still gives no general global-optimality certificate.

The depth assertion is false. Each move occupies one new square, so the general bound is $n^2$, not $n$. On a $2\times 2$ board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length $\lceil n^2/2\rceil$, since knight moves always change colour.

The opponent-independent “best possible move” assertion is false. Minimax search maximizes the guaranteed utility against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning strategy is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax strategy guarantees its minimax value, not that its root choice is best for every possible opponent behavior.^[ref]

The $O(n)$ storage assertion is false for the usual minimax implementation. Here the maximum branching factor is $O(n^2)$ and maximum depth is $O(n^2)$. A conventional depth-first search retaining pending successors uses the usual $O(bm)=O(n^4)$ search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to $O(n^2)$ stack frames plus board storage; neither accounting should confuse the board side length $n$ with its $n^2$ squares.