WDM11 Decision Mathematics 1

Lessons in WDM11

1. Algorithms, flow charts and trace tables
   Follow every instruction exactly, record every change in a trace table, then describe in general terms what the output means.
2. Bubble sort
   Compare neighbours, swap if out of order, repeat passes until a pass makes no swaps.
3. Bubble sort: full traces and counting
   Pass k makes n - k comparisons; stop only after a pass with no swaps; at most n(n - 1)/2 comparisons and swaps.
4. Quick sort
   Pivot = middle item ((N + 1)/2 or (N + 2)/2); smaller items before, larger after, original order kept; pivot every sub-list each pass.
5. Binary search
   List must be ordered; middle = (first + last)/2 rounded up; discard the middle item and the half that cannot contain the target.
6. Bin packing
   Lower bound = total ÷ capacity rounded up. First fit uses the given order; first fit decreasing sorts first. Equal to the lower bound means optimal.
7. Graphs and networks: the language
   Sum of degrees = 2 × edges; trees on n vertices have n - 1 edges; K_n has n(n - 1)/2 edges.
8. Eulerian and semi-Eulerian graphs
   All degrees even: Eulerian (closed route). Exactly two odd: semi-Eulerian (start and end at the odd vertices). More odd vertices: not traversable.
9. Minimum spanning trees: Kruskal's algorithm
   Smallest edge first; reject any edge that makes a cycle; stop at n - 1 edges; show every accept and reject.
10. Minimum spanning trees: Prim's algorithm
    Grow one tree: add the shortest edge from the tree to a new vertex; no cycles can form; list edges in the order chosen.
11. Prim's algorithm on a distance matrix
    Cross out the row, number the column, choose the smallest entry in the numbered columns, repeat. Read edges as column to row.
12. Dijkstra's algorithm
    Smallest working value becomes final next; update neighbours only if smaller; trace back using final(Y) - final(X) = weight.
13. Dijkstra: directed networks and multiple routes
    Follow arrow directions; check every arc when tracing back, as there may be several shortest routes; split 'via' problems into two parts.
14. Route inspection: two odd vertices
    Total weight + shortest path between the two odd vertices; the repeated path may go through other vertices.
15. Route inspection: four odd vertices
    List all three pairings of the four odd vertices, add shortest paths for each, repeat the smallest; total weight + that amount.
16. The travelling salesman problem
    Classical TSP: every vertex exactly once on a complete network with the triangle inequality. Practical problems are converted with a table of shortest distances
17. TSP upper bound: doubling the minimum spanning tree
    Upper bound = 2 × MST weight; improve it with short cuts that skip visited vertices; smaller upper bounds are better.
18. TSP upper bound: nearest neighbour
    Always go to the nearest unvisited vertex, then return to the start; try several starts and keep the shortest tour.
19. TSP lower bound: residual minimum spanning tree
    Delete a vertex, residual MST of the rest, add the two shortest edges at the deleted vertex; keep the largest lower bound.
20. Activity networks and precedence tables
    Activity on arc: arcs are activities, nodes are events; one source, one sink; list only immediate predecessors.
21. Dummy activities
    Dummies have zero duration, are dashed, and carry dependence. Use them when activities share some but not all predecessors, or to keep each activity uniquely na
22. Early and late event times, critical path
    Forward pass takes the largest, backward pass the smallest. Critical: both ends critical and the duration fills the gap exactly.
23. Total float and Gantt charts
    Float = latest finish - duration - earliest start. Critical activities go along the top of a Gantt chart; bars slide within their float.
24. Scheduling workers
    Workers ≥ total duration ÷ critical time, rounded up. When a worker is free, give them the available activity with the lowest latest finish time.
25. Linear programming: formulating problems
    Define variables in words, write every constraint (including non-negativity), and state maximise or minimise with the objective.
26. Linear programming: graphical solution
    Shade out, leave R clear. Optimum at a vertex: slide an objective line or test every vertex. Answer in context.
27. Linear programming: integer solutions
    Solve exactly first, then test whole number points near the optimal vertex against every constraint; the best one may not be the nearest.

Next exams for WDM11

• January 2027: Tue 19 Jan 2027, afternoon, 1h 30m
• Summer 2027: Tue 1 Jun 2027, afternoon, 1h 30m

From Pearson's final timetables. All exam dates. Always confirm your entries with your exams officer.