Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms (A10399W1)

Solutions to the paper dated 5 June 2015.^[ref] All thirteen numbered subparts are treated. The original cover and both question pages have been checked, including the directions and labels of the flow network diagram. The binary counter and decimal counter analyses use the conventional all-zero initial state; the effect of allowing a different initial state is stated explicitly.

The accounting method assigns each operation a charge, its amortized cost, that can differ from its actual cost. Cheap operations save the excess charge as credits associated with the data structure or its entries. An expensive operation spends these previously saved credits. The essential invariant is that the credit balance never becomes negative.

If the initial balance is zero, operation $i$ has actual cost $c_i$, charge ${\hat{c}}_i$, and leaves balance $B_i$, thenThus a nonnegative credit balance makes the total charge an upper bound on the total actual cost for every operation sequence. In particular, a constant time charge proves a linear time total. The argument is a deterministic amortized analysis; it requires no probability distribution on the operations. A nonzero initial balance must be included as an additive term in the bound.

Yes: starting from zero, $n$ increments of the decimal counter cost $\Theta (n)$ digit changes, uniformly in the number $k$ of digits. An increment changes the trailing digits equal to $9$ into $0$ and increases the next digit. Number digits from $0$ at the least significant end. Digit $i$ changes once every $10^i$ increments, so the exact number of changes isHere the floor function counts carries reaching each position, and the last equality sums a geometric series. Since digit $0$ changes on every increment, $C_{10}(n,k)\ge n$ for $k\ge 1$. The loop tests and carry handling add only a constant amount per changed digit and per operation, giving the same time complexity.

An accounting method explanation is also possible. Charge two credits for each change of digit $0$: one pays for that change and one joins a common bank. For $n$ increments the higher digits change at most $n/9$ times, so their costs can be covered from that bank; the displayed prefix bound ensures that it never goes negative.

The formula allows wraparound modulo $10^k$; alternatively, restrict to increments before overflow. Initializing the array itself costs $\Theta (k)$ if that is counted separately. If the initial digits are arbitrary, the number of changes at position $i$ is at most $\lceil n/10^i\rceil$, giving $O(n+k)$ in Big O notation. Starting with all digits equal to $9$ makes the first increment cost $k$, so the initial-state convention matters.

For an initially zero binary counter, bit $i$ changes precisely on increments whose indices are divisible by $2^i$. Weighting each such change by $2^i$ gives the exact totalFor $n\ge 1$ and $k\ge 1$, put $r=\min \{k,1+\lfloor {\log }_{2}n\rfloor \}$. All summands with $i\ge r$ vanish; each of the other summands is at most $n$. ThereforeThis is sharper than simply charging $n$ for each of all $k$ positions when $n$ is small. To show that the order is best possible, use $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. For every $0\le i<r$,Thus the asymptotic analysis gives a tight bound. If wraparound is excluded, $n<2^k$, and this becomes $\Theta (n(1+{\log }_{2}n))$, often written $\Theta (n\log n)$ for $n\ge 2$. If wraparound is allowed and $n\ge 2^k$, it becomes $\Theta (nk)$. For $n=0$, the cost is zero.

For completeness, the same conclusion cannot be asserted uniformly over arbitrary initial binary counter states. An initial value $2^k-1$ makes the first increment change every bit, costing $2^k-1$. A general upper bound follows by replacing each floor function in the count by a ceiling function:To see the second inequality, split at $r$: for $i<r$, use $\lceil n/2^i\rceil \le n/2^i+1$, and for $i\ge r$, use $\lceil n/2^i\rceil =1$. For $n\ge 1$ the worst initial-state cost is consequently $\Theta (nr+2^k)$. This qualification separates initialization from the usual amortized analysis starting at zero.

Use two permanent stacks, $F$ and $B$, and one temporary stack, $T$. At operation boundaries $T$ is empty. Maintain the representation invariant that the deque, read from front to back, is the top-to-bottom contents of $F$ followed by the bottom-to-top contents of $B$. Thus the tops of $F$ and $B$ are the two accessible ends. Maintain their sizes using two counters, requiring only $O(1)$ additional storage in Big O notation.

Adding at the front pushes onto $F$; adding at the back pushes onto $B$. Removing at an end whose permanent stack is nonempty simply pops that stack. If both permanent stacks are empty, report an empty deque.

Suppose a front removal finds $F$ empty and $B$ contains $m>0$ elements. Rebalance as follows:

The parked elements are the back half of the deque; the unparked elements are the front half. Moving the front half onto $F$ reverses their stack order and exposes the correct front element. Parking and restoring the back half reverses it twice, preserving its original order in $B$. The temporary stack is empty again. For a back removal with $B$ empty, exchange the roles of $F$ and $B$ throughout. Rebalance approximately half the elements, so both ends retain accessible elements after a large transfer.

For the amortized analysis, count each push or pop as one unit and use the potential method withInitially the deque is empty, so $\Phi =0$, and $\Phi$ is always nonnegative. An ordinary insertion or removal costs one unit and changes the size difference by at most one, giving amortized cost at most $4$.

For a rebalancing removal, let $h=\lfloor m/2\rfloor$. The parked half makes two transfers per element and the other half makes one; each transfer is a pop and a push. Including the final removal, the actual cost isBefore rebalancing the absolute size difference is $m$. Immediately after the split it is at most $1$, and after the removal it is at most $2$. HenceSize tests and counter updates change only these constants. Summing the amortized costs and using nonnegative final potential proves $O(1)$ amortized running time for all four operations, with three stacks and $O(1)$ additional storage. An individual rebalancing operation can still take linear time in the current size.

A flow network is a finite directed graph $G=(V,E)$ with nonnegative flow network edge capacities $c_e$, together with distinct source and sink vertices $s,t$. A feasible flow in the nonnegative directed-edge convention is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints and flow conservation:Its flow value is the net outflow at the source,which equals the net inflow at the sink by flow conservation.

A 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 counts only directed edges leaving $S$:The net flow across the cut of a flow network subtracts flow on edges returning into $S$, and equals $|f|$.

For the following parts, a circulation with vertex demands has no exceptional source or sink in the original directed graph. Instead it satisfies net inflow minus net outflow equal to $d_v$ at every vertex. Thus positive demands consume flow, and negative demands supply flow.

Write flow balance using the positive-inflow conventionRemove the lower bounds on network flow by writing $f_{uv}={\ell }_{uv}+x_{uv}$, where only ${\ell }_{BC}=4$ is nonzero. Then $0\le x_{uv}\le c_{uv}-{\ell }_{uv}$, and its required flow balance isIn the order $A,B,C,D$, the lower-bound contribution is $(0,-4,4,0)$, soThe resulting flow network edge capacities areAdd a new source $s$ with an edge $s\to A$ of flow network edge capacity $6$, and a new sink $t$ with edges $B\to t$ and $D\to t$ of flow network edge capacities $1$ and $5$. A feasible flow saturating these new edges is equivalent to a solution for $x$: ordinary flow conservation in the enlarged flow network produces exactly the residual supplies and demands above. All source and sink edges must be saturated, requiring flow value $6$.

Start the Edmonds–Karp algorithm at zero flow. Repeated breadth-first search in the residual network permits the following shortest augmenting paths; when paths tie, choose the one through $B$ first.

The first augmenting path has three edges. Once $B\to t$ is saturated, the next shortest possibilities have four edges, so steps $2$ and $3$ respect the breadth-first search rule. Each augmentation adds the usual backward edges to the residual network, though these particular augmentations need only forward edges. Now $s\to A$ is saturated, so no further augmenting path exists. The cut of a flow network with source side $\{s\}$ has cut capacity $6$, proving that the obtained flow is a maximum flow.

The original-edge values for $x$ are $(4,2,0,3,2)$ in the order $AB,AC,BC,BD,CD$. Restore the lower bound to obtainAll original capacity constraints hold, and $f_{BC}=4$ meets its lower bound. The net inflows at $A,B,C,D$ are respectivelyThe original network therefore admits a feasible circulation with vertex demands.

For any feasible circulation with vertex demands, sum its defining flow balance over all vertices:Every directed edge $ab\in E$ contributes $+f_{ab}$ exactly once to the first sum, at its head $b$, and $-f_{ab}$ exactly once to the second, at its tail $a$. The two sums therefore contain exactly the same terms. They cancel, givingThis is global flow conservation: internal transport cannot create or destroy the total amount. Lower bounds on network flow and capacity constraints restrict which flows are feasible but do not affect the cancellation. The condition is necessary, not sufficient: insufficient flow network edge capacities can still prevent satisfying balanced demands.

For each user define its set of eligible ads byThis uses the intersection of demographic-group memberships: belonging to one advertised group suffices, because the eligibility condition is a set union. A user in several groups still receives at most one ad.

A direct algorithm is to process users independently. For user $u_i$, scan ads $a_j$ until finding one for which some group $S_{\ell }$ belongs to both ${\mathcal{S}}^i$ and ${\mathcal{S}}_j$. Assign that ad and stop processing this user. If no such ad exists, leave the user unassigned. There is no upper bound on the number of different users who can receive the same ad, so these decisions do not compete for an ad resource.

For correctness, every produced impression has a shared permitted group, and the stopping rule assigns at most one ad to each user. Conversely, a user with $E_i=\varnothing$ cannot receive an ad in any feasible solution. Since every other user can contribute at most one impression, every feasible solution has value at mostThe algorithm attains this bound, provingRepresent each membership set by a length-$k$ array of Boolean variables. Testing one user-ad pair costs $O(k)$, so all tests and input setup take $O(nmk+(n+m)k+n+m+k)$ time in Big O notation, which is polynomial time in all three parameters. For positive $n,m,k$, this simplifies to $O(nmk)$.

A maximum flow formulation gives the same result if desired: add edges $s\to u_i$ with flow network edge capacity $1$, $u_i\to a_j$ with flow network edge capacity $1$ exactly when $j\in E_i$, and $a_j\to t$ with flow network edge capacity $n$. By the integral max-flow theorem, an integral maximum flow selects valid impressions. Setting the last flow network edge capacity to $1$ would impose an extra restriction absent from this paper.

Using the standard maximum form of a linear program, writewhere $x\in {\mathbb{R}}^n$, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The inequalities are coordinatewise, and $c^{T}x$ is the objective function. General linear programs can be put in this form: reverse the sign of a minimization objective function, reverse lower-bound linear inequalities, replace an equality by two opposite linear inequalities, and replace each unrestricted variable by the difference of two nonnegative variables. Some conventions instead call the equality-constraint version standard form; the convention here is the maximum-with-upper-bounds convention.

Introduce nonnegative slack variables $x_{n+i}=b_i-{\sum }_{j=1}^n{a}_{ij}{x}_j$. The equivalent slack form of a linear program isThe original variables are initially nonbasic and the slack variables basic. More generally, a slack form of a linear program specifies disjoint index sets $N,B$ and writesThus each basic variable and the objective function are expressed using only nonbasic variables. Setting all nonbasic variables to zero gives the associated basic solution, which is a feasible solution exactly when the resulting basic values are nonnegative. The slack form of a linear program does not itself require that initial basic solution to be feasible.

A vertex cover of an undirected graph $G=(V,E)$ is a subset $C\subseteq V$ containing at least one endpoint of every edge. The optimization version of the vertex cover problem minimizes $|C|$; the vertex cover decision problem asks whether a cover of size at most a given bound exists.

Let $x_v=1$ mean that vertex $v$ is selected. An integer program for minimum-size vertex cover isThe linear programming relaxation replaces $x_v\in \{0,1\}$ by $0\le x_v\le 1$. The edge inequalities enforce coverage, and the objective function counts selected vertices in the integer program.

For a graph triangle with vertices $1,2,3$, the three covering constraints areAdding them gives $2(x_1+x_2+x_3)\ge 3$. Therefore the relaxed objective function is at least $3/2$. The feasible solution $x_1=x_2=x_3=1/2$ attains that lower bound, soIn contrast, one vertex leaves the opposite edge uncovered and any two vertices cover all three edges, giving integer optimum $2$. The example exhibits a genuinely non-integer optimal value, rather than merely a fractional feasible solution.

Assume job sizes $t_i\ge 0$ and machine speeds $s_j>0$, with at least one machine. Let $y_{ij}\ge 0$ be the amount of job $T_i$ assigned to machine $M_j$, and let $T\ge 0$ be the proposed makespan. Use the linear programThe first family of constraints assigns every job completely. The second bounds each machine's completion time by $T$, since $L_j/s_j\le T$ is equivalent to $L_j\le s_{j}T$. It is a linear inequality because $s_j$ is an input constant. There is no integrality restriction: jobs are divisible as specified in this scheduling model.

To verify the formulation, any actual allocation defines the variables above, with $T$ equal to its largest completion time, and satisfies every constraint. Conversely, from a feasible solution, assign amount $y_{ij}$ to machine $M_j$ and process its assigned pieces consecutively. Its total time is at most $T$, so the linear program realizes the claimed makespan.

There is also a useful exact check. Put $W={\sum }_i{t}_i$ and $S={\sum }_j{s}_j$. Summing machine constraints gives $W\le ST$, so $T\ge W/S$. Assigningmakes every machine's completion time $W/S$, provingThis relies on the paper's divisible-work model, in which machine completion times depend only on total assigned size. If $W=0$, the optimum is $0$.

A feasible point $x$ is an extreme point solution of a linear program if it cannot be written as a nontrivial convex combination of two distinct feasible points. Explicitly, ifthen $y=z=x$. Equivalently, $x$ lies in no open line segment joining two distinct feasible points. Being an extreme point concerns the feasible region; it does not by itself mean that $x$ optimizes the objective function.

Let $G=(L\cup R,E)$ be the given bipartite graph. A matching in a graph selects edges with no shared endpoint. For each edge $e$, introduce an indicator $x_e$ for selection. The integer program for a maximum cardinality matching isIts linear programming relaxation iswith the same objective function. Explicit upper bounds $x_e\le 1$ may be included, but they already follow from a constraint at either endpoint.

We prove that every extreme point of $P$ is integral by showing that any feasible point with a fractional coordinate admits a two-sided perturbation. Given such an $x$, form the fractional support graph $H$ with exactly those edges for which $0<x_e<1$. This is a nonempty bipartite graph. A vertex incident to one of these edges cannot also meet an edge with value $1$, because its incident sum would exceed $1$.

First suppose $H$ contains a graph cycle. Choose a simple one, $e_1,\dots ,e_q$. Its length $q$ is even since $H$ is a bipartite graph. Define a nonzero vector $h$ by alternating $+1,-1$ along the graph cycle and putting $0$ on other edges. At each vertex on the graph cycle, the two changed coordinates have opposite signs, so its incident sum is unchanged. ChooseThen $x^{+}=x+\epsilon h$ and $x^{-}=x-\epsilon h$ are distinct feasible points: no coordinate leaves $[0,1]$ and all incident sums are unchanged. Since $x=(x^{+}+x^{-})/2$, it is not an extreme point.

Otherwise $H$ is a forest. Choose a connected component of a graph containing an edge, and a simple graph path in it between two tree leaves. Alternate $+1,-1$ along the graph path to define $h$. Every internal vertex of the graph path still has unchanged incident sum, including any additional edges branching from it. At either endpoint, exactly one incident edge has fractional value; all other incident coordinates are $0$, since a coordinate $1$ is impossible there. Thus each endpoint has strictly positive slack $1-{\sum }_{e\ni v}{x}_e$ in its degree constraint. Choose $\epsilon >0$ smaller than these two slacks and smaller than every $x_e$ and $1-x_e$ along the graph path. Both $x+\epsilon h$ and $x-\epsilon h$ remain feasible: the endpoint sums can increase or decrease by $\epsilon$, and the internal sums do not change. Again $x$ is the midpoint of distinct feasible points, contradicting extremality.

Both cases exclude fractional coordinates at an extreme point. ThereforeThe nonempty bounded linear polyhedron $P$ has an optimal extreme point for the stated linear function, so the relaxation yields a maximum cardinality matching. This is stronger than the existence of one integral optimum: it proves integrality of every extreme point. It does not claim that every optimal feasible point is integral; convex mixtures of distinct optimal matchings in a graph can be fractional.