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.

Bi-partite graphs.

Write down or interpret a matrix to represent a given graph.


For storage of graphs.

 


 

 

Draw all essentially different trees with 5 vertices.

Kn and Km,n
Conditions for planarity.
 

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 two-variable 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.