Title

Topics

Time

Notes

Algorithms

Definition of algorithm

Examples of algorithms

Sorting algorithms

Bin packing algorithms

Double lesson

Double lesson

Double lesson

Double lesson

Total : 2 weeks

Using flowcharts

Bubble sort. Ex1A

Quick sort.  Ex 1B Finish HW

Full bin combinations

First fit algorithm

First fit decreasing algorithm

Ex 1C Finish HW

Test on all the above

Algorithms on graphs

Modelling using graphs

Definition of terms used in graph theory.

Other ways of representing graphs.

Trees

Networks

The minimum spanning tree (or minimum connector).

Prim’s algorithm: finding a minimum spanning tree from a graph

Kruskal’s algorithm for finding a minimum spanning tree.

Finding the shortest path through a network.

Dijkstra’algorithm

Double lesson

Double lesson

1 week

Double lesson

Double lesson

Total : 3 weeks

Learn

e.g. Underground maps

Ex 2A HW

Ex2B HW

Prim’s algorithm to the computer network.

Applying Prim’s algorithm to a matrix.

Applying the matrix form of Prim’s algorithm to the computer network.

How this method works.

What is a greedy algorithm, why is Kruskal greedy?

A complex network problem

Algorithmic complexity.

End of chapter test

Decision making in graphs

The travelling salesman problem (TSP).

The difficulty with the TSP.

An upper bound to the practical problem.

A lower bound for the classical problem.

The route inspection problem.

1 week

1 week

Total: 2 weeks

Alternative ways of pairing

The route inspection algorithm. (Chinese Postman Problem).

End of Chapter test

Critical path analysis

Precedence tables.

Activity networks

Analysing the project(the critical path algorithm)

Critical events and critical activities

Time analysis of a network

Using the float

Double lesson

Double lesson

1 week

2 weeks

Total: 3 weeks

Drawing an activity network

Using dummies

Earliest event time e_i (forward scan)

Latest event time l_i (backward scan)

Meaning of the total float

Scheduling

Resource levelling

End of Chapter test

Flows in networks

Flow networks

Capacities and flows

The maximum flow-minimum cut theorem

Finding the maximum flow using augmentation-a labelling algorithm

Flows in undirected edges

Spotting flow augmenting paths

1 week

How is the max flow-min cut theorem useful?

Linear programming

Formulating linear programming problems

Graphical solutions for two-variable problems

Feasible solutions of a linear programming problem

Finding the optimum solution of a linear programming problem

Extreme points and optimality

Integer valued solutions

The algebraic method for solving linear programming problems

Basic solutions

Simplex method

Total: 3 weeks

Set of points defined by a linear inequality

Set of points defined by a collection of inequalities

Slack variables

WS prepared: In D1on computer

Matchings

Modelling using a bipartite graph

Matchings

Improving a matching using an alternating path: the matching improvement algorithm

Total: 2 weeks

Changing the status

Topic

Key Words/ Notes

Time

Key Skills/Links

1. Transportation problems

Sources, destinations, capacity, availability, requirement.

Formulation as a linear programming problem (linear programming not required). What is a balanced problem?

Setting up of transportation tableau.

Finding an initial solution, use of North West corner method for a ‘feasible solution.’

Testing solution for optimality and calculation of improvement indices. NB. Improvement indices use cost values.  Use of unused cells in final calculation, non-negativity indicates optimal solution. I_ij = Cij – R_i – K_j

Obtaining an improved solution-use of ‘stepping stone’ method.  Rules for stepping stone, best method is to check totals in rows and columns are unaltered.  Idea of more than one optimal solution.

Unbalanced transportation problems, use of dummy to make ‘balanced’.

Degeneracy (number of occupied cells is not m+n-1).  Creation of artificially occupied cell.

Define closed path

Resource: Heinemann Decision Maths (D2)  Chapter 1

1 week

1 week

Problem Solving

Improving learning.

Transportation Problems and link to Business Studies, minimizing costs, maximizing profits

2.  Allocation

(assignment)                             problem

One agent is assigned to one and only one task.  Balanced problems.

Formulation of problem as a linear programme.

Solution of the assignment problem using the ‘Hungarian algorithm’, finding the opportunity cost matrix.  Testing for an optimal assignment.

Revising the opportunity cost matrix, making the final assignment.  Possibility of multiple optimal solutions.

Unbalanced assignment problems, introduction of either dummy row or column (Value to be zero).

Maximisation assignment problems-the optimal assignment obtained is the optimal assignment for the original maximizing problem.

Resource: Heinemann Decision Maths (D2)  Chapter 2

                  Discrete Mathematics 2 (OCR) p9-17

1 week

1 week

Problem Solving.

Allocation Problems: Business Studies applications, minimizing costs, maximizing profits

3. The Travelling Salesman Problem

Establish the difference to the ‘Route Inspection’ problem.  Define TSP, walk, tour, tour of minimum weight.  Find tour of minimum weight that visits each vertex once only. The difficulty with the TSP, i.e. practicality when number of vertices is large. 

Calculation of upper bounds by 2 x minimum spanning tree (Prim/Krushkal’s algorithm).  Finding shortcuts to improve upper bound.

 Finding lower bounds by deleting vertices.  Note: Solution found is not always optimal.   The ‘Nearest Neighbour’ algorithm. (Note: Nearest unvisited neighbour to current vertex.  The Practical TSP.

Resource: Heinemann Decision Maths (D2) Chapter 3

                  Decision Mathematics-de Pomerai/Berry Section 3.2,3.3

                  Discrete Mathematics 1 (OCR)Chp 6

1 week

1 week

Problem solving

4.  Game Theory

Types of Games:  Two person game, zero-sum game.  Payoff matrix, strategy, gain, loss and value of game.  Optimal strategy, single strategy, pure strategy, mixed strategy, different strategies.

Pure strategy games-minimax strategy, saddle points(equilibrium point).  Mixed strategies for 2 x 2 games.  Use of graphical inequalities for solutions.

Mixed strategies for 2 x 3 and 3 x 2 games.  Solution by graphical inequalities.

Formulation of a game as a linear programme.  (Note: minimize v means maximizing 1/v)  Use of Simplex method for solution.  Revision and emphasis on increased care as all numbers in Objective row have relevance to full solution. I.e. we can find the strategy A should use from the final tableau of the calculation for B’s strategy.

Dominance-elimination of a strategy if all game outcomes are the same or worse than the corresponding game outcomes of another strategy.

Resource: Heinemann Decision Maths (D2) Chapter 4

                 Decision Mathematics-de Pomerai/Berry Section 13.2

                                                                       + Simplex Method Chapter 9

                  Discrete Mathematics 2 ( OCR) Chp 5

1 week

2 weeks

1 week

Business Studies application: maximum gain, minimum loss, optimization.

Complexity with increased variables, use of IT Omnigraph, possibly Excel

5.  Dynamic Programming

Definition-technique for solving multi-stage decision making problems enabling optimal solutions to be found.  The principal of optimality-any part of the shortest route from S to T is itself a shortest path.

Dynamic programming applied to shortest route problem.  Terminology-Stage,initial state, action, destination, value. Re-apply to find longest route.

Minimax route- route on which all the maximum length of the edges used is as small as possible.  The maximin route-route on which all the minimum length of edges used is as large as possible.

Other applications of dynamic programming.

Resource: Heinemann Decision Maths (D2) Chapter 5

                 Discrete Mathematics 2 Chp 6

1 week

Problem Solving

Possible IT with Visio time line