M.E.I. STRUCTURED MATHEMATICSUNIT D1
Unit D1: Scheme of Work
Unit Title
Decision Mathematics 1 (4771) is an AS unit.
Objectives
To give students experience of modelling and of the use of algorithms in a variety of situations.
To develop modelling skills.
The problems presented are diverse and require flexibility of approach. Students are expected to consider the success of their modelling, and to appreciate the limitations of their solutions.
Examination(72 marks) in June
1 hour 30 minutes.
The examination paper has two sections:
Section A:three questions, each worth 8 marks.
Section Total: 24 marks.
Section B:three questions, each worth 16 marks.
Section Total: 48 marks.
Teaching Structure - It is very important that you adhere to the teaching schedule.
(TeachingSchedule is available which gives an idea how many weeks you need for each topic. Please discuss in details with the staff with whom you share the group.) C4 unit is taught by one member of staff, whilst the other member teaches D1. The AS/A2 specification and D1 programme of study is available for reference purposes. There is a series of lessons DBBs lessons that can be used to teach the whole of D1.
Chapter Assessments
Every topic has a chapter assessment that must be completed for homework and assessed by the teacher. Chapter assessments should be handed in with the correct front sheet. Copies of these are available for students on DBBs support page and in the sixth form area of the pupil shared drive. They are also available with mark schemes in the department area. Marks are to be entered in the spreadsheet in the department area. It is vital this gets done on time for monitoring purposes, especially the borderline/under-achieving students.
Past examinationpapers are available on the network in the pupil shared resources for students/staff to access.
ICT
Power points to aid teaching/learning are available for D1.Autograph is also available on the network. Please keep yourself updated by logging onto
MEI Online resources: Username and password available for staff only.
Scheme of Work
This scheme of work is a “working document” and comments and alterations are very welcome, especially if you have a new or exciting way to teach a topic.
Topic and learning objectives / References / Teaching pointsD1/1 ALGORITHMS
1.1. Introduction
Be able to interpret and apply algorithms presented in a variety of formats: flow charts, written English, pseudo-code (A1) / Ch.1 p.1-5 / What is an algorithm? Definition: a sequence of precise instructions to solve a problem. Properties: (a) each step must be defined precisely; (b) it must work for any set of inputs; (c) the answer to a problem must depend only on the inputs; (d) it must produce an output and stop after a finite number of steps.
What examples can we think of? (a) the techniques taught in junior school for +, –, ×, ÷; (b) cake recipes, knitting patterns, etc. (c) see for something defined by a flow chart: what is it doing? (d) Zeller’s algorithm (text p.1).
How can we communicate an algorithm? (a) flow chart; (b) written English (recipe book); (c) computer programming language such as BBC Basic (ancient, but comprehensible) or more modern versions such as VBA; (d) pseudo-code which is independent of a particular programming language: read e.g. on p.2. Some BBC Basic programs are available, e.g. one to find the HCF of two numbers.
Understand the basic ideas of algorithmic complexity: worst case; size of problem; idea that for quadratic complexity doubling the size of a large problem can quadruple the solution time; order notation O(n2) (A3)
Be able to analyse the complexity of some of the algorithms covered in this specification (A4) / Ch.1 p.6-9
Ex.1A (leads into 1.2 below) / How efficient is an algorithm? Efficiency = fewer operations, less storage capacity.
The example on p.6/7 re. nested multiplications is a good one. How would you write these as algorithms? Stress that the complexity refers to the worst case.
In the case of non-nested multiplication, the expression for complexity contains n2 terms, so the algorithm has quadratic complexity: mention the order notation O(n2). Doubling the size of the problem (n) quadruples the complexity, and hence the length of time the algorithm takes to run. For the nested multiplication, the algorithm has linear complexity. What happens in this case? What would happen in a case of cubic complexity?
Read about the bin-packing problem on p.7/8 and try Ex.1A.
1.2. Packing algorithms
Be able to develop and adapt simple algorithms: full-bin; first-fit; first-fit decreasing packing algorithms (candidates expected to know these) (A2)
Be happy with the concept of a 'for...next loop' in an algorithm / Ch.1 p.9-11
Ex.1B Q3 (for...next loop)
Investigations 4 & 5 (Internet research recommended) / A heuristic algorithm is an algorithm which usually finds a good, if not the best, solution. Exhaustive algorithms look at all possibilities and can guarantee to produce the best solution, but there are often very many possibilities! Here we look at three heuristic algorithms for bin-packing problems: First-Fit; First-Fit decreasing; Full bin (definitions p.9). These must be learned.
What are the advantages and disadvantages of each? Full-bin requires lots of combinations to be checked to see if they make full bins. First-fit decreasing requires a sort first.
The minimum number of “bins” required can be calculated by finding the total “length”, dividing by the size of the bin and rounding up.
Investigation 4 is the knapsack problem: algorithms to solve this are “greedy” (maximising immediate gain at the possible expense of future consequences). More examples of such algorithms in ch.3.
1.3. Sorting algorithms
Be able to develop and adapt simple algorithms for sorting: bubble, shuttle, insertion, quick sort (candidates not expected to memorise these) (A2) / Ch.1 p.15-21
Ex.1C (optional)
Ex.1E Q14
Ex.1D / Start with brief notes on the five different sorting algorithms. Then MEI have an excellent spreadsheet called Allsorts, which candidates should be encouraged to download from the Distance Learning site. This can be used to gain familiarity with the algorithms and to count comparisons and swaps. Ex.1E Q14, although tedious, could be tackled here as it encourages candidates to find lists which lead to the greatest number of comparisons for shuttle sort and insertion sort.All have quadratic complexity.
Although the specification states “candidates will not be required to memorise sorting algorithms” they were asked to carry out a bubble sort, with no instructions given, in N03. In other questions, they have been given slightly different sets of instructions to carry out, and count comparisons and swaps. It is very important that candidates carry out the instructions given, not those memorised!
1.4. Searching algorithms
Not explicitly in specification / Ch.1 p.22-24
Ex.1E Q1,2,4,10-13, 15-17 (some) / Read through p.22-24 briefly.
The questions in Ex.1E are often long, but it is probably worth doing some of them.
Completion of above / Chapter Assessment 1
D1/2 GRAPHS
Understand notation and terminology: nodes/vertices; arcs/edges; trees; node order; simple; complete; connected and bipartite graphs; walks; trails; cycles and Hamilton cycles; digraphs; planarity (g1) / Ch.2 p.43-50
Ex.2A Q2,3,8 / What is a graph? A graph in this context is just a set of points, some or all of which are joined by lines. The same idea applies to e.g. y = x2, but we join plotted points by a smooth curve because we are dealing with the continuous.
The origin of graph theory lies in recreational mathematics, such as the Bridges of Königsberg. The development of computer power led to widespread applications to industrial and commercial problems, e.g. transport planning, scheduling, circuit design, etc.
There is a great deal of language in this chapter: the MEI DL site has a useful glossary which could be photocopied. To add to the confusion, many ideas have two names! Start with arc/edge and node/vertex.
Example 1: a graph G has 10 vertices labelled 1-10. Join 2 vertices if they have a factor larger than 1 in common. (i) Draw G. (ii) How many edges? (iii) Introduce degree, and tabulate the degree of each vertex. (iv) Sum of degrees? Notice anything? 2E = ∑d, the “handshaking lemma”. Why? (v) More language: G is simple (no loops) and not connected. (vi) Draw subgraphs consisting of {2,4,6,8,10} and {3,6,9}. What do you notice? These are complete. Investigate the complete graph Kn: degree of each vertex? how many edges? Let’s all shake hands, or play chess against each other: remove edges to see games still to be played.
Continuation of above / Ex.2A Q1,10,12,14 / Example 2: draw a probability tree diagram, e.g. for tossing two coins. A tree is a simple, connected graph with no cycles. A tree has the smallest number of edges possible if the graph is to remain connected: in general, a tree with n vertices has n – 1 edges. Other applications: family trees?
Example 3: draw two sets of four points. Four MPs W, X, Y and Z are being considered for four cabinet posts F, H, C and E. W could be F or H, etc. A bipartite graph illustrates the problem: solve it. The complete bipartite graph Km,n has m vertices in one row and n in another. (i) How many edges are there? (ii) What are the degrees of the vertices? (iii) Verify that 2E = ∑d. (iv) Consider K2,3: show that this graph can be drawn without edges crossing (planar). Repeat for K2,4. Can you conclude anything about K2,n? What about K3,3? Other applications: printed circuit boards?
Example 4: to cover incidence matrices, isomorphism, traversability, Eulerian, semi-Eulerian and non-Eulerian graphs, we can do little better than to use the notes from the MEI DL site (d1g1n.pdf). Why is it impossible for a graph to have one vertex of odd degree?
Example 5: a digraph is a graph where at least one edge has a direction associated with it, e.g. one-way systems, ferries visiting different ports. Try to discover the condition for a digraph to be Eulerian (at each vertex, no. edges in = no. edges out).
Completion of above
Be able to model appropriate problems by using graphs, e.g. Königsberg bridges; various river crossing problems; the tower of cubes problem; filing systems (g2) / Ex.2A Q13,16
Ex.2B Q3 (optional) / The examples cover most of the language: we haven’t mentioned walks and trails, and a Hamilton cycle is a cycle which visits each vertex (only) once. E.g. a salesman starts and finishes at home, and needs to visit a number of different towns once each.
Applications are dealt with pretty well in the above examples, and there are some other good ones in the text (e.g. the “showman” puzzle). A possible field for research is Schlegel diagrams, which relate solids to networks (and hence prove Euler’s formula). The Bridges of Königsberg problem is the famous application of traversability (and is Ex.2A Q13). Kaliningrad is now in Russia! The “tower of cubes” puzzle is “Build the tallest possible tower of cubes such that touching face colours match and lighter cubes are always on top of heavier cubes” which should lead to a digraph: you could try looking at but it is unlikely to be illuminating!
Completion of above / Chapter Assessment 2
D1/3 NETWORKS
3.1. Minimum connector problems
Understand that a network is a graph with weighted arcs (N1)
Know and be able to use Kruskal’s and Prim’s algorithms (N3) / Ch.3 p.60-65
Ex.3A Q1-3 / A network is a graph with weighted arcs. The weights might be lengths, times etc.
Recall the idea of a tree: removing any edge would disconnect the graph. E.g. to link computers into a network, there is no point in having cycles: with three computers, C could be connected to A via B. Now add lengths of cables and find the minimum spanning tree. With three, it’s easy, but we need a method to apply to more complicated problems. Provide a fairly simple exampleand work through Kruskal’s and Prim’s algorithms using it (see text for descriptions). Kruskal works with arcs, Prim with nodes. These processes are greedy (they need no forward planning) and always lead to the optimal solution.
Know and be able to use the matrix form of Prim’s algorithm (N3) / Ch.3 p.68-69
Ex.3B Q1,2
(photocopies help) / For large networks, we would need to be able to supply details of the network to a computer. How can we do this? Via a table: if two nodes are not directly linked, enter ∞. Work through the algorithm as applied to the table. Other applications: translation problems.
Ch.3 p.86-87 / Mention here that Kruskal and Prim both have cubic complexity, so if T is the time taken to solve a problem and n is the number of vertices, Tn3.
3.2. Finding a shortest path
Know and be able to apply Dijkstra’s algorithm (N4) / Ch.3 p.73-79
(A worksheet exists)
Ex.3C (introductory)
Ex.3D Q1,2,4 / p.73 has a very good introduction (Autoroute). Dijkstra’s algorithm enables you to find the shortest route between a chosen starting point and any other point in a network. Start with a simple example where all the paths between two points in a network can be listed and the shortest one selected: a well-chosen example can show that the required algorithm cannot be greedy. Work through Dijkstra’s algorithm with a slightly harder example: it is essential it is followed exactly!
Ch.3 p.87 / Dijkstra has quadratic complexity. Doubling the size of the problem needs four times the effort.
Be able to model appropriate problems by using networks, e.g. “geographical” problems (N2) / Investigations 2 & 6
Ex.3E Q1,3,9,12,14 / Examination questions often ask for slight adaptations of the algorithms, e.g. a road in a network is blocked, or a new road is built. The investigations and the questions in Ex.3E provide suitable examples.
Completion of above / Chapter Assessment 3
D1/4 CRITICAL PATH ANALYSIS
4.1. Activity networks
Be able to construct a precedence network (X1 part) / Ch.4 p.101-103
(A worksheet exists) / CPA was developed in the 1950s by the CEGB. It is widely used to plan complex projects. Such projects require a number of processes or activities, some of which require others to be completed before they can start.
Work through the problem on the worksheet, which covers precedence tables, constructing the network (nodes represent events which are the start/finish of one or more activities: arcs represent activities, and the weight of the arc gives the duration) and dummy activities which arise in two situations: (i) if Y has predecessors W and X, but Z has predecessor W alone; (ii) if two activities would otherwise join the same start and end nodes (activities would be identified to a computer by giving the numbers of their start and end nodes).
It is always a good idea to draw the network on a piece of scrap paper first!
Be able to use a precedence network, including forward and backward passes, the identification of critical activities and the calculation of float (total and independent) (X1 part) / Ex.4A Q1-5 / Having created the network, we now find the critical path. Any delay in the activities on this path (the critical activities) will increase the duration of the whole process. Show how to move from left to right through the network to find the earliest event times, and then from right to left to find the latest event times. Critical activities are those for which LET at end – EET at beginning = duration. Do this for some of the networks drawn above.
Non-critical activities have spare time, or float, associated with them. There are two kinds of float: (i) independent float is spare time associated with one particular activity; (ii) interfering float is associated with two or more activities. If an activity is delayed by an amount up to its interfering float, it may delay other activities, but will not delay the overall completion time.
Completion of above
4.2. Resource allocation
Be able to construct and interpret a cascade chart (X2)
Be able to construct and interpret a resource histogram (X3)
Understand the use of alternative criteria in project optimisation: time, cost, use of resources (X4) / Ch.4 p.111-118 / Resource usage can be examined by constructing a cascade chart and an associated resource histogram.
The cascade chart shows the information in the completed activity network in the form of bars drawn against a time scale. It is useful to show dependencies by marking in vertical dotted lines to show the latest times by which activities can be completed. Do not worry about the flow chart on p.113: it doesn’t work anyway!
The resource histogram shows the number of people employed at a given time, against time. The total area under a resource histogram gives the total number of, say, person-minutes for the project (the total time the project would take if carried out by one person).
We might be able to use the float to help us use resources better, e.g. the number of workers needed. This is called resource levelling. Read p.115 in the text for some ideas about alternative criteria.
Be able to crash a network: checking critical activities and for activities becoming critical (X5) / Ex.4B Q3
Ex.4C Q8,9,11,13,14 / Suppose we carry out a critical path analysis on a project and find that the minimum completion time is 24 weeks. But it is absolutely essential to complete the project in 23 weeks.We must reduce the length of one of the activities on the critical path. This is called “crashing” the network. There will usually be costs associated with this, as more workers might have to be employed. A question may offer us a number of possibilities, from which we have to select the cheapest alternative.
This topic is referred to in the specification, but has never been tested.
Completion of above / Chapter Assessment 4
D1/5 LINEAR PROGRAMMING
5.1. Formulation and solution
Be able to manipulate inequalities algebraically (L1)
Be able to illustrate linear inequalities in two variables graphically (L2)
Be able to formulate simple maximisation of profit and minimisation of cost problems (L3)
Be able to use graphs to solve 2D problems: show alternative feasible points and their associated costs/profits (L4 part) / Ch.5 p.138-145
Ex.5A Q1,3,4,6 / Decision Maths! Usually there is a particular aim in making one decision rather than another. This aim might be to maximise profit or minimise cost. LP produces a mathematical model of a situation in which requirements, constraints and objectives are expressed as algebraic equations. Dates from WW2.
To formulate a LP problem, we (i) decide what we must decide, hence identifying the decision variables. In exams, these must be written as e.g. “Let x be the number of Type A sheds produced per day”. Then (ii) set up the constraints, which will probably include x ≥ 0, y ≥ 0 (non-negativity). Then (iii) set up the objective function, which will be what we want to maximise or minimise. All this results in a LP “expression”, which might have the form “Maximise P = ... subject to 2x + 3y ≤ 30...”