Decision 1
Chapter 1  Simple Ideas of Algorithms


Correctness, finiteness and
generality. Stopping conditions.
Bubble, shuttle, shell, quicksort algorithms.

Candidates should appreciate
that for a given input an algorithm produces a unique output. Candidates
will not be required to write algorithms in examinations, but may be
required to trace, correct, complete or amend a given algorithm, and
compare or comment on the number of iterations required. Candidates should appreciate the relative advantages of the different algorithms in terms of the number of iterations required. Comment on number of comparisons and swaps. Find an expression for the maximum number of comparisons when the shuttle sort algorithm is applied to a list of length of n.

Chapter 2  Graphs and Networks 

Vertices, edges, edge weights, paths, cycles. Adjacency/distance matrices Connectedness. Directed and undirected graphs. Degree of a vertex, odd and even vertices, Eulerian trails and Hamiltonian cycles. Trees. Bipartite graphs. 
Write down or interpret a matrix to represent a given graph.
Draw all essentially different trees with 5 vertices.
Kn and Km,n 
Chapter 3  Spanning Tree Problems


Prim’s and Kruskal’s algorithms to find minimum spanning trees. Relative advantage of the two algorithms. Greediness.

Minimum length spanning trees are also called minimum connectors. Candidates will be expected to apply these algorithms in graphical, and for Prim’s algorithm also in tabular forms. Essential that method and order of working is shown clearly on both graphical and tabular forms. Candidates may be required to comment on the appropriateness of their solution in its context. 
Chapter 4  Matchings


Use of bipartite graphs. Improvement of matching using an algorithm. 
Use of an alternating path Clear demonstration of method of working is required. 
Chapter 5  Shortest Paths in Networks


Dijkstra’s algorithm. 
Problems involving shortest and quickest routes and paths of minimum cost. Including a labelling technique to identify the shortest path. Networks may be given in graph or tabular form. To include finding bounds of an individual edge to ensure a particular path is minimal. Candidates may be required to comment on the appropriateness of their solution in its context. 
Chapter 6  Route Inspection Problem 

Chinese Postman Problem. 
Candidates should appreciate the significance of the odd vertices They must show that they have considered all possible pairings of the odd vertices. Problems with more than four odd vertices will not be set.
Candidates may be required to comment on the appropriateness of their solution in its context. 
Chapter 7  Travelling Salesman Problem


Conversion of a practical problem into the classical problem of finding a Hamiltonian cycle. Determination of upper bounds by nearest neighbour algorithm. Determination of lower bounds on route lengths using minimum spanning trees. Modelling scheduling and other problems as TSPs.

By deleting a node then adding twice the shortest distance to the node or the sum of the two shortest edges and the length of the minimum spanning tree for the remaining graph. Candidates may be required to comment on the appropriateness of their solution in its context. 
Chapter 8  Linear Programming 

Graphical solution of twovariable problems. 
Candidates will be expected to formulate a variety of problems as linear programmes. They may be required to use up to a maximum of 3 decision variables. In the case of two decision variables candidates may be expected to plot a feasible region. The significance of the objective line must be appreciated. To include finding integer solutions Candidates may be required to comment on the appropriateness of their solution in its context. 
Chapter 9  Mathematical Modelling


The application of mathematical modelling to situations that relate to the topics covered in this module  Including the interpretation of results in context. 