Unit D1: Decision Mathematics AS 1

An algorithm is a precise, finite sequence of instructions that transforms permitted inputs into outputs. To implement an algorithm written as text or a flow chart, follow its arrows and decisions exactly, updating variables in the stated order until its stopping condition is reached.

Make a trace table with one row for each completed pass through the process. Record every variable after the assignments, the result of the decision test, and any output. Use the updated value in the next row; do not reuse the previous value or stop merely because successive values look close.

For the text algorithm 'input $x$; while $x<20$, replace $x$ by $x+3$; output $x$', input 8 gives successive values 8, 11, 14, 17, 20. The test is then false, so the output is 20.

Positions are counted from 1. Thus a list of 9 items uses the 5th item, while a list of 6 uses the 4th: the right-hand one of the two central items. Apply the same rule whenever a middle item is required.

These four list algorithms have different jobs: bin packing allocates, bubble and quick sort order, and binary search locates. Preserve the given order unless the method explicitly changes it.

For every quick-sort sublist and binary-search candidate list, use $(N+1)/2$ when $N$ is odd and $(N+2)/2$ when $N$ is even, so an even list uses its right-hand middle item.

Quick-sorting $[7,2,5,3,6]$ starts with pivot 5: $[2,3]\mid5\mid[7,6]$. To binary-search sorted $[2,3,5,6,7]$ for 6, compare with 5 and search $[6,7]$; its right-middle item is 7, then 6 is found.

A spanning tree connects every vertex of a connected weighted graph without cycles. With $n$ vertices it has exactly $n-1$ edges. A minimum spanning tree (MST), or minimum connector, is a spanning tree whose total edge weight is as small as possible.

For Prim on a symmetric adjacency matrix, activate the start vertex's column and remove its row from future selection. Choose the least available entry in active columns; it identifies an edge to the vertex in that row. Activate the new vertex's column, remove its row, and repeat. Rows and columns represent vertices, symmetric entries represent undirected edge weights, and a blank or dash means no edge.

If $AB=2$, $AC=5$, $BC=1$, $BD=4$ and $CD=3$, Kruskal selects $BC$, $AB$, $CD$, with total 6. Prim from $A$ selects $AB$, $BC$, $CD$: the order differs, but the MST is the same.

Dijkstra's algorithm finds shortest distances from one start vertex in a weighted network with non-negative edge weights. A temporary label is the best distance found so far; once it is the smallest temporary label and becomes permanent, its value cannot improve.

Give the start vertex permanent label 0 and every other vertex a temporary label $\infty$. From the newest permanent vertex $u$, calculate a candidate for each adjacent non-permanent vertex $v$. Replace $v$'s label and predecessor only when the candidate is smaller. Then make the smallest temporary label permanent and repeat until the destination is permanent.

Let $AB=4$, $AC=2$, $CB=1$, $BD=5$, $CD=8$, $BE=9$ and $DE=2$. From $A$, make $C$ permanent at 2, improve $B$ to 3 via $C$, make $B$ permanent, improve $D$ to 8, then reach $E$ at 10 via $D$. Backtracking predecessors gives $A-C-B-D-E$, length 10.

The permanent destination label gives the shortest distance, but the route comes from predecessor labels: start at the destination and follow predecessors backwards to the start, then reverse the sequence. If a journey must pass through a specified vertex, find and join the required shortest-path segments.

A route-inspection, or Chinese postman, problem asks for the shortest closed walk that traverses every edge of a connected weighted network at least once and returns to its start. First add every edge weight to obtain the unavoidable base total $S$; extra distance comes only from edges that must be repeated.

A closed walk enters and leaves each vertex in pairs, so every vertex must have even degree after repeated edges are included. If the network already has no odd vertices, an Eulerian closed walk exists and the minimum length is $S$. Odd vertices always occur in an even number.

When there are two odd vertices, duplicate a shortest path between them. With four odd vertices $A,B,C,D$, inspect all three pairings: $AB+CD$, $AC+BD$ and $AD+BC$, using shortest-path distances rather than necessarily direct edges. Choose the pairing with the least total, duplicate the edges on those paths, then trace a closed walk using every original edge and every required repeat.

Suppose $S=120$ and the shortest-path pairing totals for four odd vertices are 13, 18 and 15. Duplicate the paths belonging to the total 13, so the minimum route length is $120+13=133$. The written route must show those repeated edges and finish where it started.

If a question explicitly allows different start and finish vertices, those two vertices may remain odd; make every other vertex even with the least additional shortest paths. This is a stated-endpoints extension: the core D1.3.1 task is the closed route that returns to its start.

A travelling-salesperson problem (TSP) seeks a minimum-length tour that visits every required vertex and returns to its start. A tour is a closed walk; unlike route inspection, the goal is to visit vertices, not to traverse every edge.

The triangle inequality says that a direct classical edge from $A$ to $C$ is no longer than travelling from $A$ to $C$ through another vertex $B$: $w(A,C)\leq w(A,B)+w(B,C)$. This is why a repeated intermediate vertex in a closed walk can be shortcut without increasing its length.

To improve an upper bound, identify a repeated vertex in the walk and replace the surrounding detour by the corresponding direct edge in the complete graph, while still visiting every required vertex and returning to the start. Continue only while the result remains a valid tour. In a practical network, a classical edge represents the shortest route between its endpoints and must later be expanded back into real network edges.

If a closed walk contains $A-B-C-B-D-A$, then $B$ is revisited. In its complete metric graph, the section $C-B-D$ may be replaced by $C-D$. The resulting tour $A-B-C-D-A$ is no longer than the original walk and is therefore at least as good an upper bound.

For a classical TSP, a lower bound is a value the optimal tour cannot be below, while an upper bound is the length of an actual valid tour. Minimum spanning tree (MST) methods produce both kinds of information without claiming the exact optimum.

For a lower bound, delete one vertex $v$ and all its incident edges. Find an MST on the remaining vertices, then add the two least edge weights incident to $v$ in the complete graph. Every tour must connect $v$ twice, and removing $v$ from a tour leaves a connected spanning structure, so its length cannot be less than this total. Trying different deleted vertices can give different lower bounds; retain the largest valid one.

For an MST upper bound, double every MST edge to form a closed walk that reaches every vertex. Its length is twice the MST weight. Shortcut repeated vertices using the triangle inequality until a tour remains; the resulting tour length $U$ is an upper bound and may be smaller than the doubled-tree length.

For a practical network, first form a complete network or table whose entry for each vertex pair is their shortest-path distance in the original network. Apply the classical bound methods to that complete network. When reporting a practical route, expand each selected complete-network edge back to its corresponding shortest path.

If deleting $A$ leaves an MST of weight 22 and the two least edges incident to $A$ have weights 5 and 7, then $L_A=22+5+7=34$. If doubling and shortcutting an MST gives a valid tour of length 38, then the optimum $T$ satisfies $34\leq T\leq38$.

The nearest-neighbour algorithm constructs a travelling-salesperson tour from a specified start vertex. It is a greedy method: at each step it uses the nearest vertex not yet visited, rather than comparing complete future tours.

Start at the stated vertex. Move to the nearest unvisited vertex, record that edge and mark the new vertex visited. Repeat until every vertex has been visited exactly once, then include the closing edge back to the start. Add every selected edge, including the closing edge, to obtain an upper bound.

If two nearest unvisited vertices tie, branch at the tie and complete each possible route; the branches can produce different tour lengths. Apply the same tie rule again if another tie occurs. For one start vertex, retain the shortest valid tour generated by its branches.

In a complete graph let $AB=2$, $AC=5$, $AD=6$, $BC=4$, $BD=3$ and $CD=1$. Starting at $A$, choose $B$ (2), then $D$ (3), then $C$ (1), and finally return to $A$ (5). The nearest-neighbour tour is $A-B-D-C-A$ with length 11.

Different starting vertices can give different tours. If several starts are requested, run the algorithm independently from each and take the smallest resulting tour length as the best nearest-neighbour upper bound. On a practical network, work from its complete shortest-distance table and then expand the selected edges into actual paths.

An activity network models which project activities must finish before others can start. In the activity-on-arc convention, each labelled arrow is an activity and its duration; each vertex is an event marking the completion of all activities that enter it. Arrow direction therefore records precedence, not physical movement.

Begin with every activity that has no predecessor at a start event. Add each remaining activity only when all of its immediate predecessors have reached its start event. Merge arrows when several activities must all finish before the next one starts, and continue until all final activities reach one finish event. Number events so every arrow points from a lower to a higher event number.

A dummy is a zero-duration arrow that preserves a dependency without adding work or resources. Use one when the real arrows alone would make an activity depend on too many predecessors, or would give two activities the same start and finish events. It is part of the network logic but not a project activity.

One valid construction is $A:1 o2$, $B:1 o3$, a dummy $2 o3$, $C:2 o4$, $D:3 o4$ and $E:4 o5$. The dummy makes $D$ wait for both $A$ and $B$, while $C$ still depends on $A$ only; the common event 4 makes $E$ wait for both $C$ and $D$.

A precedence table reverses the modelling step: for each real activity in an activity-on-arc network, it lists only the activities that must finish immediately before that activity can start.

Take one activity at a time and inspect its tail event. Record the real activities whose arrows feed that event. If an incoming arrow is a dummy, do not list the dummy; trace backwards through it to the real activity or activities whose completion it carries. Activities leaving the initial event have no predecessors.

Although $A$ and $B$ must occur before $E$, they are not immediate predecessors of $E$: once $C$ and $D$ are complete, their earlier requirements are already satisfied. Listing only $C,D$ keeps the table equivalent to the network without redundant transitive dependencies.

The critical path is a start-to-finish path whose activities determine the minimum project duration. A delay to any activity on that path delays the project unless the plan changes. Find it by a forward pass for earliest event times and a backward pass for latest event times.

Set the start event's earliest time to 0. Moving with the arrows, an event can occur only after every incoming activity finishes, so take the maximum incoming finish time. At the finish event, set the latest time equal to its earliest time. Moving against the arrows, take the minimum latest permitted start supplied by the outgoing activities.

Let $A:1 o2$ take 4, $B:1 o3$ take 3, $C:2 o4$ take 5 and $D:3 o4$ take 2. The forward pass gives $e_1=0$, $e_2=4$, $e_3=3$ and $e_4=\max(4+5,3+2)=9$. The backward pass gives $l_4=9$, $l_2=4$, $l_3=7$ and $l_1=0$. Thus $A,C$ form the critical path and the minimum completion time is 9.

An activity $(i,j)$ is critical when it uses all available time: $e_i+d_{ij}=l_j$. Join critical activities continuously from the start event to the finish event; more than one critical path can exist.

Total float is the amount by which an activity can be delayed without delaying the project's minimum completion time. For activity $(i,j)$, compare its earliest possible start with the latest start allowed by its finish event.

If $e_i=6$, $l_j=15$ and the duration is 4 hours, then $F=15-6-4=5$ hours. A critical activity has total float 0; a non-critical activity may be moved within its float only while all precedence constraints remain satisfied.

Place critical activities first because they cannot move. Then fit non-critical activities into their allowed float, shifting them only when predecessors have finished and the assigned worker is free. A cascade chart displays flexibility; a finished scheduling diagram displays the chosen start times and worker allocation, not the unused float. When every activity requires one worker, total activity duration is the total worker-time used in the lower bound.

For example, 68 worker-hours in a 24-hour project gives the lower bound $\lceil68/24 ceil=3$ workers. This average-work bound may be unattainable: precedence can force several activities to overlap. To prove that at least $k$ workers are needed, identify a time strictly inside an interval when $k$ named activities must all be running; then construct a valid $k$-worker schedule if the exact minimum is required.

A linear program turns a decision into variables, one linear objective to maximise or minimise, and linear constraints that describe every permitted choice. Define each variable and its unit first so every coefficient has a clear meaning.

Choose decision variables for the quantities controlled. Write the objective, such as profit, cost or output, and state maximise or minimise. Translate each independent limit, minimum, ratio or total into an equality or inequality. Clear fractions or decimals to give simplified integer coefficients when requested, then include non-negativity and any required integer condition.

If a relation fixes a third variable, substitute it into both the objective and every constraint before presenting a two-variable model. Equivalent positive rescalings of an objective have the same optimum, but changing its sign reverses maximise and minimise.

Let $x$ and $y$ be numbers of products A and B. A earns 5 and B earns 8, each A uses 2 machine-hours and 4 kg of material, each B uses 3 machine-hours and 2 kg, with 60 hours, 64 kg and at least 6 units of A required. The model is: maximise $P=5x+8y$, subject to $2x+3y\leq60$, $4x+2y\leq64$, $x\geq6$, $x,y\geq0$. If products are indivisible, also require $x,y\in\mathbb Z$.

For two variables, each linear inequality defines a half-plane. Their common intersection is the feasible region $R$; only points in $R$, including permitted boundary points, can be candidates for the optimum.

Draw each boundary by replacing its inequality with equality, using accurate intercepts or two calculated points and a ruler. Test a point not on the line to select the correct side. Apply every constraint, including non-negativity, and label the intersection that remains as $R$. Find exact vertex coordinates by solving the pairs of boundary equations that meet there.

A linear objective changes at a constant rate, so on a bounded polygonal feasible region its maximum and minimum occur at a vertex, or along a whole boundary edge when the objective line is parallel to that edge. The ruler and vertex methods therefore describe the same geometry.

For $x,y\geq0$, $x+y\leq8$, $x+2y\leq10$, maximise $P=3x+4y$. The vertices are $(0,0)$, $(8,0)$, $(6,2)$ and $(0,5)$. Their objective values are 0, 24, 26 and 20, so the maximum is $P=26$ at $(6,2)$. Sliding a line $3x+4y=k$ towards larger $k$ gives the same final contact.

After choosing the optimal point, translate its coordinates and objective value back into the problem's quantities and units. Substitute into resource expressions when the unused amount or slack is required.

When decision variables count indivisible items, only integer-coordinate points in the feasible region are allowed. The continuous graphical optimum can be fractional, so it may be a bound or guide rather than a feasible answer.

Mark or list the lattice points that satisfy every constraint. A point on a non-strict boundary is allowed, while a strict inequality excludes its boundary. Evaluate the objective at all relevant feasible integer candidates; for a small region, enumerate them all. A fixed integer variable can instead be substituted into the constraints to obtain the complete integer range of the other variable.

Never round a fractional optimum automatically. Rounding one coordinate can violate a constraint, and rounding down can miss a better feasible lattice point. Check feasibility first, then compare objective values.

Consider integer $x,y\geq0$ with $2x+y\leq9$ and $x+3y\leq10$, maximising $P=5x+4y$. The continuous boundary intersection is $(17/5,11/5)$, which is not an allowed integer point. Because both objective coefficients are positive, for each possible integer $x$ it is enough here to retain the greatest feasible $y$.

The integer optimum is therefore $(4,1)$ with $P=24$. Simply rounding the continuous point to $(3,2)$ gives only 23, while $(4,2)$ is infeasible because $2x+y=10>9$.