Advanced Data Structures and Algorithms examination paper by the University of Oxford (2015) 2026-10-31
Examination dated 5 June 2015, Trinity term, University of Oxford. The public archive contains the paper as the member
2015-adsa.pdf of Lawrence Attachment.zip. The three original pages contain the cover and thirteen numbered subparts on amortized analysis, flow networks, and linear programming. CLIME precision-matrix estimator Created 2026-10-03 Updated 2026-11-05
The CLIME precision-matrix estimator estimates a sparse matrix representing the precision matrix from a sample covariance matrix . An initial estimate solvesThese are the entrywise matrix L1 norm and entrywise maximum norm, not the induced column-sum and row-sum norms. Writing for column and for the corresponding basis vector gives separate problems subject to , each a linear programming problem.[ref]
A Constrained L1 Minimization Approach to Sparse Precision Matrix Estimation by Tony Cai and others. Section 2, equations 1–3: norm definitions, constrained estimator and column decomposition
The column solutions need not form a symmetric matrix. The original construction selects the smaller-magnitude entry from each pair and copies it to both positions, using a common tie rule. Error analysis requires that the true precision matrix be feasible for the chosen tolerance.[ref]
A Constrained L1 Minimization Approach to Sparse Precision Matrix Estimation by Tony Cai and others. Section 2, symmetrization after equation 1 and feasibility-based analysis
Positive definiteness is not an optimization constraint here. For example, with and , the zero matrix is feasible and minimizes the objective. A positive-definite conclusion therefore needs further assumptions and a statistical theorem, rather than following from the program alone.
Complementary slackness Created 2026-09-24 Updated 2026-11-05
For the primal maximization , and dual minimization , , a feasible pair has the nonnegative objective-gap decompositionThus equal objective values are equivalent toThese are complementary slackness. Combined with primal and dual feasibility they certify optimality by weak duality. Conversely, primal and dual optima satisfy them by strong duality.
A positive dual multiplier forces its primal constraint to be tight, and a positive primal variable forces its dual constraint to be tight. A tight constraint need not have a positive multiplier: both factors in a complementary product may be zero. This distinguishes ordinary complementary slackness from a stronger strict-complementarity assertion. In the example under linear programming, the third primal inequality is slack and its multiplier is zero.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.5.2, complementary slackness; inequalities and equality of optimal objectives
Contact time of translating line segments 2026-10-14
For segments with initial direction vectors , initial endpoint displacement , and translation velocities , contact is feasibility of the displayed linear equation with and . Minimizing is a small linear programming problem. A nonsingular three-column coefficient matrix gives at most one candidate; singular, parallel and degenerate cases require the constrained feasibility problem rather than division by a vanishing determinant.
Critical path method Created 2026-10-14 Updated 2026-11-05
The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration .
Add a zero-duration source before every initial activity and a zero-duration sink after every terminal activity. Give each edge weight , including zero weight on edges leaving . This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.
Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from to ; hence the feasible finish matches the lower bound. This is dynamic programming on a directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.
For our project scheduling example, , , and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.
Now fix the project start at zero and the finish at . The latest starts come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives , , , , , and . These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.
Earliest solid and latest hollow activity bars for the critical path method, with task floats of 2 for B and 6 for E
. Details. Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.
Daniel Dadush Created 2026-10-14 Updated 2026-11-05
Daniel Dadush studies mathematical optimization, including linear programming, integer programming, geometry of numbers and discrepancy theory. His work connects the geometry of high-dimensional convex sets with algorithms for mathematical optimization.[ref]
Homepage: homepages.cwi.nl/~dadush/
Portrait of Daniel Dadush
. Photograph linked on the CWI personal homepage.A polynomial-time algorithm for integer linear feasibility gives exact rational linear programming optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality localizes the finite optimum to an interval containing a unique rational of bounded denominator; continued fractions recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.
Fractional knapsack problem 2026-10-06
This linear programming relaxation allows a fraction of each item. With positive weights, sort decreasing profit-to-weight ratios and fill capacity in that order, using at most one fractional item. An exchange argument proves optimality. Negative-profit items are omitted and positive-profit zero-weight items are included for free.
Karmarkar standard form Created 2026-10-14 Updated 2026-10-24
This form of linear programming additionally has the uniform vector as a strictly positive feasible point and known optimum zero. A homogeneous self-dual embedding of a linear program, followed by elimination of unrestricted Lagrange multipliers and normalization by the sum of nonnegative coordinates, yields this form without presupposing feasibility of the original program. The known start and optimum support projective interior-point methods. Polynomial bit-complexity statements additionally require finite rational input encoding; bounded arbitrary real coefficients alone do not provide it.
Linear optimization on a convex hull Created 2026-10-18 Updated 2026-10-20
A linear functional cannot exceed its best original value by mixing. For a finite nonempty set and in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.
For the eight samples above, use the linear functional . Its largest sample value is , and is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at . The line is a supporting line: every point of the convex hull lies in the half-space , and touches its boundary.
The point passes the coordinate-wise bounds , , but . This single inequality certifies that is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.
This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function , the new point instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.
Linear programming Created 2026-09-24 Updated 2026-11-05
Linear programming optimizes a linear function over finitely many linear equalities and inequalities. A common convention isThe feasible region is a linear polyhedron, so the problem has convex geometry even when it represents a discrete-looking allocation. A linear programming relaxation drops integrality requirements and supplies bounds for an integer program.
For a concrete example, maximize subject to , , , and . The point is feasible and has value ten. Multiplying the first inequality by two and adding the second givesThus this point is globally optimal. The multipliers form a dual linear program certificate; the unused third constraint has zero multiplier. This small calculation captures the purpose of linear programming duality: a feasible solution gives a value, while a feasible dual combination proves that no better value is possible.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §4.3.1, linear programs; §5.1, Lagrange dual lower bounds
A model can instead be infeasible or unbounded. The simplex method uses changing bases, while interior-point methods approach the optimum through the feasible interior when suitable initialization or embedding is supplied. A chosen numerical algorithm must report which case occurred and respect the input's sign and standard-form conventions.
Linear programming duality Created 2026-09-24 Updated 2026-11-05
Linear programming duality pairs the standard maximization problemwith the minimization problemThe dual variables form nonnegative combinations of primal inequalities. If and are feasible, thenThis is weak duality, giving independently checkable bounds before any algorithm reaches an optimum.
For a feasible primal with finite optimal value, strong duality for finite-dimensional linear programs ensures attained primal and dual optima with equal values. Their objective difference decomposes into nonnegative products of variables and opposite slacks, yielding complementary slackness. The worked allocation in linear programming has primal point and dual multipliers , both with value ten. Sign conventions change for minimization, equality rows and unrestricted variables; a dual formula belongs to its declared primal form.
Nimrod Megiddo Created 2026-10-14 Updated 2026-11-05
Nimrod Megiddo is a mathematician known for research on optimization and the computational complexity theory of algorithms. His fixed-dimensional linear programming algorithm solves a problem with constraints in time when the dimension is fixed. The dependence on is absorbed into the constant, so this statement does not give a uniformly linear algorithm when the number of variables also grows.[ref]
https://theory.stanford.edu/~megiddo/pdf/lplin.pdf. Linear Programming in Linear Time When the Dimension Is Fixed, JACM 31 (1984), abstract and introduction, pp. 114–115
This result illustrates a useful distinction in computational complexity theory: a geometric optimization problem can become much easier when its ambient dimension is a fixed parameter.Homepage: theory.stanford.edu/~megiddo/
Nonbasic variable 2026-10-14
A nonbasic variable corresponds to a column outside the current simplex basis. In standard nonnegative linear programming, it is set to zero at the basic solution. With explicit finite bounds, it is normally fixed at one of its bounds.
// Target: mathematical-optimization.bigb
Past exam of the integer programming course of the University of Oxford 2011 3 a Solution 2026-10-31
The assignment constraint matrix has one row for each outgoing sum and one for each incoming sum. The column for has a one in outgoing row and incoming row . Negate all incoming rows. Each column now has exactly one and one , the node-arc incidence matrix of the directed bipartite graph from row vertices to column vertices.
Here is a direct proof that this signed matrix is totally unimodular. Consider any square submatrix and induct on its size. If a column has no nonzero entry, its determinant is zero. If a column has one nonzero entry, expansion along it reduces the determinant to plus or minus a smaller subdeterminant, hence to or . If every column has two nonzero entries, they have opposite signs, so each column sum is zero. The rows are then dependent and the determinant is zero. The size-one case is immediate, completing the induction.
Negating rows only changes signs of square subdeterminants. Thus the original assignment matrix is also a totally unimodular matrix. This proves the total unimodularity of directed incidence matrices argument directly in the required setting.
The integrality theorem for totally unimodular systems says that has integral vertices when is totally unimodular and is integral. Redundant equalities cause no problem. Here the row sums also force , so every integral feasible vertex is a binary assignment. The bounded nonempty LP relaxation has an optimal vertex, and therefore an optimal assignment. Hence the assignment problem can be solved by linear programming without a binary search; dedicated methods such as the Hungarian algorithm also exploit its polynomial-time structure. Multiple optimal assignments can have fractional convex combinations, so the conclusion concerns an optimal integral vertex, not every optimal LP point.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 34 1 Solution Created 2026-10-03 Updated 2026-10-14
Introduce the nonnegative integer surplus variables and . Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of must be , rather than . The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.
The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity is an integer, while is nonnegative. Thus the integer is at most , and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic .
Apply this to the row . Since , and , the resulting valid inequality isMultiply by five and add an integer slack . Its row is . At the old relaxed optimum, is negative, while the minimization objective coefficients remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.
The cut row permits either or to enter. The dual ratio test givesThus enters and leaves. Solving the cut row and substituting givesSetting the nonbasic variables gives nonnegative basic values . The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.
Past exam of the mathematics course of the University of Cambridge 2004 ib Paper 3 12G Solution Created 2026-09-24 Updated 2026-10-14
Let be player two's mixed strategy in Rock paper scissors. The respective expected payoffs from choosing rock, scissors and paper are , and . Thus player two solves the linear programming problemA linear objective on this probability simplex is maximized by a largest-payoff pure response, or by any mixture of tied maximizers. Scissors is never a maximizing response: rock exceeds it by one. Comparing the other two gives according as . ThereforeThe optimal expected payoff is below the tie and above it, with value at the tie.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 66 2 i Solution Created 2026-10-03 Updated 2026-10-14
Put , , and . A point on each moving segment has the form and , with . Contact is therefore equivalent toThe contact time of translating line segments is the minimum feasible . This reduces the entire continuous-motion problem to three linear equations and linear inequalities.
In three-dimensional space form the matrix . If it is nonsingular, solveusing a stable linear solver. A candidate with in the unit interval and is the only contact event and hence the earliest one; otherwise no contact occurs. Check initial intersection explicitly, so an already touching pair returns time zero.
If is singular, use a rank-revealing factorization to test consistency. Write every solution as , with columns of spanning the null space, and minimize its time coordinate subject to the box and nonnegative-time constraints. This is a small linear programming problem. It handles parallel segments, collinear overlap, a continuum of contact times and segments degenerated to points. Infeasibility means no future contact. When , the relative geometry is stationary: initially disjoint segments never meet. The first contact is the least feasible nonnegative time, not just an intersection of the two supporting lines.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 38 1 Solution Created 2026-10-03 Updated 2026-10-14
Introduce slack variables . The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.
The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has , and . Although increasing improves the objective at rate four, reaches zero first at , giving pivot three. After pivot four, and ; the upper bound gives pivot five.
In the final objective row every reduced cost is nonpositive. Since , it also directly certifies the upper bound , attained only when all three vanish. Thus
A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements , and . It therefore brings into the simplex basis first, with leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.
This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, for constraints and original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 38 2 Solution Created 2026-10-03 Updated 2026-11-05
In a minimum-cost flow problem, every directed arc has a per-unit cost and lower and upper capacities . Each vertex has a prescribed net supply , with . We seek flows minimizing subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has and, here, .
For project scheduling, augment the precedence graph with a source , of duration , and a sink . Join to every task with no predecessor, and every task with no successor to . Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed matrix by itself contains no start or finish vertex. Assuming the precedence graph is a directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix . These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is , the recursion of the critical path method.
To derive project scheduling duality, associate a nonnegative multiplier with . The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all vanish. This gives one unit of net outflow at , one unit of net inflow at , and zero net flow at other vertices. Hence the dual isEquivalently, minimize with . The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.
The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials making the network reduced costzero on the tree. An arc at its lower bound is improving if ; an arc at its upper bound is improving in reverse if . Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.
For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is . The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is , so this is a degenerate but feasible network simplex tree basis. Normalizing , the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring into the tree. The resulting cycle increases the flows on and decreases those on . The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing . The resulting unit flow follows and has cost .
For the new tree, normalized potentials areThe only nonbasic arcs now have and , both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path has duration , so it and the timetable furnish a unit-flow certificate for project duration.


