Decision Mathematics 1

Worked examples (5)

• 1Identify graph features (4 marks, D1)
• 2Minimum spanning tree by Kruskal's algorithm (6 marks, D1)
• 3MST by Prim's algorithm (list form) (5 marks, D1)
• 4Prim's algorithm on a distance matrix (7 marks, D1)
• 5Compare Kruskal's and Prim's (3 marks, D1)

Worked examples (6)

• 1Bubble sort: sort into ascending order (5 marks, D1)
• 2Quick sort with middle pivot (6 marks, D1)
• 3First-fit bin packing (4 marks, D1)
• 4First-fit decreasing bin packing (5 marks, D1)
• 5Full-bin packing heuristic (3 marks, D1)
• 6Tracing a flowchart algorithm (4 marks, D1)

Worked examples (5)

• 1Dijkstra's shortest path (8 marks, D1)
• 2Route inspection: 2 odd vertices (6 marks, D1)
• 3Route inspection: 4 odd vertices (8 marks, D1)
• 4TSP upper bound by nearest neighbour (5 marks, D1)
• 5TSP lower bound via MST (6 marks, D1)

Worked examples (6)

• 1Formulate a linear programming problem (5 marks, D1)
• 2Graph the feasible region (5 marks, D1)
• 3Objective line / ruler method (5 marks, D1)
• 4Vertex testing (4 marks, D1)
• 5Integer-valued solution (5 marks, D1)
• 6Minimisation LP problem (6 marks, D1)

Worked examples (5)

• 1Construct an activity-on-arc network from a precedence table (6 marks, D1)
• 2Forward and backward pass — event times (8 marks, D1)
• 3Identify the critical path and total floats (5 marks, D1)
• 4Construct a Gantt (cascade) chart (5 marks, D1)
• 5Scheduling diagram: minimum number of workers (6 marks, D1)