# Mathematics: Decision 1 (Notes 1 of 1)

### Description

OCR AS-Level / A-Level Contains all major spec points. COMPLETED
Note by declanlarkins, updated more than 1 year ago More Less
 Created by declanlarkins over 10 years ago Copied by declanlarkins over 10 years ago Copied by declanlarkins over 10 years ago
433
13

## Resource summary

### Page 1

An algorithm is a set of instructions for solving a problem. The order of an algorithm tells you how 'efficient' an algorithm is. It tells you how the time the algorithm takes to run changes as the number of input values changes.Most algorithms are general which means they work for loads of different input values, but this means that for simple cases it might not be the best method to use.Algorithms are largely used in computer programming, and setting computers working on problems which it would take too much time for people to work out by hand.An algorithm may be given in the form of a flow chart or set of instructions... (it is important to follow and take a note of EVERY step!)All algorithms must have a stopping condition otherwise they could keep repeating and repeating forever.There are two algorithms for sorting numbers into ascending, or descending order: bubble sort and shuttle sort.Instructions for the shuttle sort:1) Compare the first two numbers 2) Are they... in the right order? leave them be; ...in the wrong order? swap them. This is the first pass.3) Compare the second and third numbers4) Repeat step two5) If you make a swap compare the swapped number to the number before it and go through step 2 again. Stop comparing numbers when you reach a number that won't be swapped or you work your way back to the front of the list. This is pass two. 6) Continue comparing the next pair of numbers and swapping if necessary until you get to the last pair of numbers in the list.Instructions for the bubble sort:1) Compare the first two numbers, if they're in the right order move on, if they're in the wrong order swap them. 2) Compare the next pair of numbers (2nd and 3rd) and swap if necessary, then move on to the next pair and swap if necessary and repeat until you reach the end of the list. This is the first pass.3) If you made swaps on the last pass then go back to the beginning of the list and start again.Remember to record the number of comparisons and swaps on each pass.For both algorithms the maximum number of passes is n-1 (when n is the number of numbers being sorted). The bubble sort may finish in fewer passes than this but the shuttle sort will always need the maximum number of passes.The shuttle sort and bubble sort will both need the same number of swaps but the bubble sort is LESS efficient because you may have to do many more comparisons then necessary.There are also 2 'bin-packing' algorithms to know about - to aim of these is to pack a set of items into the minimum number of bins while not exceeding the maximum height or weight criteria in each of the bins.Instructions for first-fit:1) Put the first item in the list into the first bin.2) Put the next item in the list into the first bin it will fit into.3) Repeat step 2 until all the items are packed.This algorithm is quick and easy but is unlikely to give the right answer.Instructions for first-fit decreasing:1) Put the list of items into descending order.2) Follow the instructions for first-fit.This algorithm usually gives a better solution, but a better solution yet may be gained by working out the optimum solution yourself. If you add up the space wasted and it is more than the value one 'bin' can hold there may be a better solution..

Linear programming is a way of solving problems to find the 'optimal solution'. For example, how many of each type of cupcake should be made to give maximum profit, given a limit on the amount of flour, eggs and cooking time available. Vocabulary to know:-Decision variable - x,y,z The amount of each thing being produced.-Objective function - The thing you're trying to maximise (or minimise)-Constraints - The factors that limit the problem (non-negativity constraints are often appropriate).-Feasible solution - A solution that satisfies all the constraints.You may be asked to formulate constraints from a wordy problem - just ensure you separate out the information you're given and then work out which way around the inequality sign should go.When drawing a graph to find the feasible region (ie. if there are only two variables)  shade the area you don't want, which will leave you with an unshaded area which satisfies all the constraints.To find the optimal solution write out all the co-ordinates of the vertices of the feasible region - you may be able to see these by eye or have to solve the equations of each line that intersects simultaneously. Substitute all the co-ordinates into the objective function to get the value of the objective function at each point. Depending on if you're maximising or minimising the value the optimum value will be at the biggest or smallest number. Remember to write a statement giving x= and y=, don't just leave co-ordinates. If the optimal solution requires that x and y be integer values, calculate the function for all the vertices as above but then look for points with integer values of x and y near to the optimum vertex. Another way of calculating the optimum solution is to use the simplex method.To do this use slack variables - these are just a way of turning inequalities into equations (if you know x+y+z is less than or equal to 20 then x+y+z+some variable (s) will equal 20 - even if the variable turns out to be 0). You use a different slack variable for each inequality. The simplex method works as follows: (see example)1) Turn the inequalities into equations using slack variables. Move the variables in the objective function onto the other side of the equation to get it equal to 0.2) Set up a tableau with columns for P, x, y, z and the slack variables and a right-hand-side (RHS) column.3) Choose a pivot column - this will either be given in the question or should be the a negative value in the top row (the most negative value will tend to solve the problem quicker).4) Perform a ratio test by dividing each of the values in the RHS column by the corresponding value in the chosen pivot column. Choose the value in the pivot column which gives the smallest number in the ratio test. This is the 'pivot element'.5) Divide the whole of the pivot row by the pivot element to make the new value of the pivot one - write this new row in a new tableau below the initial tableau.6) Make all the other values in the pivot column 0 by adding or subtracting multiples of the new pivot row to each of the rows and write these in the new tableau.7) Keep repeating these steps (4,5,6) until there are no more negative values in the top row.The optimum value of P will be the RHS value in the top row.To read off the values of the variables look down the column to find the 1 and across to the RHS value (if all the values in the column are 0s). If the values in the column are all random and jumbled then that variable equals 0.This method works for the slack variables aswell - to interpret the slack variables in terms of the question look back to what that inequality represented, for example the time or the cost - if the slack variables aren't 0 it means there is spare capacity.

A graph is made up of dots (nodes/vertices) joined together by lines (arcs/edges), There are special types of graph:Connected graphs - every node is connected, directly or indirectly, to every other node.Simple graph - no node is connected to another node by more than one arc, or has an arc connecting it to itself.Directed graph - arcs may be given a direction arrow meaning that arc can only be 'travelled down' in one direction.Planar graphs - these can be arranged (on a single plane) in such a way that the arcs do not cross each other.A path is is a route in a graph which flows from the end of one arc to the start of the next and doesn't repeat any vertices.A cycle is a closed path - it ends in the same place as it starts.A tree is a graph that connects every node to every other node, directly or indirectly (ie. it is a connected graph), and has no cycles. A spanning tree is a tree which includes all the vertices.The order of a node is how many arcs are connected to it. If a node as an arc connecting it to itself this counts as two, because it is in contact with the node in two places. Nodes can be of odd or even order but the total of all the orders is always even - this is because it is double the number of arcs. In a simply connected graph with n nodes the maximum order of any node is n-1. The total orders of all the nodes is twice the number of arcs, and so is even. In any graph there are an even number of odd nodes. A graph is traversable if you can start at any point, go along every arc exactly once(without taking your pen of the paper) and end up back where you started.Eulerian graphs have this property because all the nodes have even order.A graph is semi-traversable if there is a route where you can go along every arc exactly once but only if you start and end at particular vertices.Semi-Eulerian graphs have this property because they have exactly two vertices with an odd order and the rest are even - the route must start at one of the odd vertices and end up at the other one.

Algorithms

Graph Theory

Networks

Linear Programming

### Similar

Fractions and percentages
GCSE Maths Symbols, Equations & Formulae
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
HISTOGRAMS
CUMULATIVE FREQUENCY DIAGRAMS
GCSE Maths: Geometry & Measures
GCSE Maths: Understanding Pythagoras' Theorem
Using GoConqr to study Maths
New GCSE Maths
Maths GCSE - What to revise!
GCSE Maths Symbols, Equations & Formulae