# Maths: Decision 1

**A1** Representing algorithms:

**Pseudo-code**is a mix of English and computer programming syntax- Another way of expressing an algorithm is with a
**flowchart** **Heuristic algorithms**don't always find the best solution, but are much quicker than trying every possible solution to find the correct one (known as brute-force algorithms)

**A2** Bin packing algorithms:

- The following algorithms are heuristic and are to find the most efficient way to fit multiple objects of varying sizes onto multiple "bins"/boxes/shelves etc
**The first-fit algorithm**: iterate through the list of items and place each in the first bin that has space for it**The first-fit decreasing algorithm**: first sort the items into decreasing order (see sorting algorithms below), then apply the first-fit algorithm. This will generally output a better solution at the cost of higher complexity (items must first be sorted)**The full bin algorithm**: this has an even higher complexity: first find combinations of items which will fill a bin, then apply a first-fit algorithm to the remaining items. This algorithm is much harder to program a computer to do, as it must check not just for pairs of items to fill bins, but also sets of 3, 4, 5 etc, and possibly try different combinations to find the best if many groups will fill a bin

## Sorting algorithms:

**Bubble**: The list is cycled through, comparing each pair and swapping if necessary. This is repeated until a pass is made where no swaps are made**Shuttle**: In the first pass, the first and second items are compared and swapped if required. In the second pass, the second and third are compared, and if swapped, the first and second are compared again and swapped if necessary. This is continued until the end of the list is reached**Insertion**: The first element is placed in a new list (which will eventually contain the sorted one). The second is then moved into the new list and swaps are made until it is in the correct position. This is repeated until all elements have been moved into the new list**Quick sort**: The median is selected as a pivot () and all elements larger than it are moved above it. All elements smaller than the pivot are moved below it and equal values can be moved either way. This is then repeated recursively for all sub-lists

**A3** Algorithm complexity:

**Efficiency**is the measure of how long an algorithm would take to run compared to the increase in problem size,*n*- The
**order**of an algorithm is the approximate run time

- Some algorithms have**linear complexity**(input size is linearly proportional to computation time), shown as O(n) and some have**quadratic complexity**, shown as . Therefore, a doubling of the data set would quadruple the complexity

- Unless stated otherwise, 'big O' notation describes worst-case scenario performance

## Sorting algorithm complexities:

- All of these algorithms generally have quadratic complexity
- The number of comparisons and swaps can often be calculated. For example, with bubble sort: comparisons and swaps. This is because if n = 5, the number of comparisons would equal 4 + 3 + 2 + 1

**g1** Graphs:

- A
**graph**is a set of vertices (nodes), connected by arcs - A
**loop**is an arc with the same vertex at each end - A
**tree**is a connected graph with no cycles - The
**degree**(or order) is the number of edges of a node **Simple graphs**have no loops, only one edge connecting each set of vertices- A
**walk**is a sequence of edges where the end of each is the beginning of the next, except from the last vertex **Trails**are walks where edges are not repeated**Paths**are trails where vertices are not repeated- A
**cycle**is a closed path.**A Hamiltonian cycle**visits every vertex (but only once) - A graph is connected if there is a path between every pair of vertices
- A
**complete graph**has every pair of vertices connected by an edge - A
**digraph**is a graph where at least one edge has a specific direction (represented by an arrow) - A
**planar**graph can be drawn with no crossing edges. A**bipartite**graph's vertices can be split into two groups where each edge has one vertex in each group - Two graphs can be
**isomorphic**if one can be manipulated (e.g. stretched) to become identical to the other - A graph can be represented by an
**incidence matrix**, by labeling the points and listing the number of edges on each

**N1** Networks:

- A
**network**is a graph with weighted arcs (e.g. with distances)

**N3/A4** Kruskal's algorithm:

- This is a
**minimal spanning tree algorithm**- finding the shortest route connecting all points in a network - First, select the shortest arc, then find the next shortest arc and use that, provided that it does not create a cycle. If there is a choice of shortest arcs (both the same size), any can be chosen. Repeat until n - 1 arcs have been chosen
- This algorithm is harder to program for a computer because it requires sorting of arcs first using a sorting algorithm, and it needs to be able to check for cycles, which is not very efficient

## Prim's algorithm:

- This algorithm achieves the same as Kruskal's, but a different method is used
- A node is first selected as a starting point, then the shortest arc is selected which is connected to the existing network. This is repeated until all nodes have been connected
- This algorithm is much better for computer implementation; here is the method in matrix form:
- The starting node is selected and its row is deleted and column highlighted. The smallest entry in the highlighted column is found and selected. Then this row is deleted and column highlighted, and the process is continued until there are no rows remaining

## Complexity:

- Both of these algorithms have
**cubic complexity**

**N4** Dijkstra's algorithm:

- This algorithm is to find the shortest route between any two points on a network. It has
**quadratic complexity** - A box is drawn above each node, containing two small squares at the top and a wide rectangle at the bottom. The top left box is the order, top right box is the distance from the start point and the bottom is the
*temporary label* - A start node is chosen and labelled with a permanent label, 0, which is the distance from the start point. The order is then recorded, 1 for the start node (so the top left box reads 1 and the top right reads 0)
- Then, the distance to each connected node is calculated and recorded in the temporary box. If one path is shorter than another, cross out the old one and use the shortest one. Once paths from that node have been calculated, the shortest becomes the next permanent node. Set its order to one more than the previous box and the distance to the shortest distance. This is repeated until each node has been labelled

**X1** Precedance networks:

- An
**activity network**uses nodes to represent**events**(the start/end of an activity) and arcs for**activities** - Events must be numbered to ensure that each activity can be uniquely identified by its start and end node.
**Dummy activities**can be used to solve any issues here and are represented by a dotted line with 0 time - There should be one start node (1) and one finish node
- The
**critical path**is the longest path through the network - any delay on this path will increase the duration of the entire operation

## Critical path analysis:

- A double box should be drawn above/below each node. The left represents the
**early event time**- the earliest time the event can be left, and the right is the**latest event time**- the latest the event can be left for the operation to complete within the minimum completion time. This can be easily calculated by working backwards through the network once early event time has been calculated for all nodes

## Floats:

- The
**total float**is the time a task can be delayed for without delaying completion of the project - The
**independent float**is the time a task can be delayed for without delaying the start of its successors - The following formulas could be used or they could be determined from the activity network:

## Resource histograms:

- These plot resources against time (e.g. people on the y axis, time on the x)
**TO DO: more detail, check spec. Cascade chart???**

**L1 - 5** Linear programming:

- Step 1:
**Formulation**:

- Identify variables, use**Let**to describe each in terms of x and y

- The**objective function**describes the aim - what needs to be maximised. For example, if selling product A (x) for £1 and product B (y) for £2, the objective function would be x + 2y - Step 2: finding the
**solution**

- The**feasible region**is the area on the graph which meets all of the inequalities. Non-feasible areas are shaded to indicate this

- To find the**optimal solution**, the intersections (vertices) should be checked; and the objective function can be used to find the best solution

- Therefore, simultaneous equations could be used to find these vertices accurately

## Integer programming:

- Sometimes the solutions must be integers (whole numbers), for example the number of items
- If the LP (linear) solution is already integer, then this will be the optimal solution
- However, if this is not a whole number, all integer points around the LP solutions should be checked with the objective function

## Minimisation:

- In these problems, the optimal solution is the solution with the lowest value

**Z1** Simulation:

- When problems are too complex to be solved using probability, simulation can be used by generating random numbers
- In the exam, random numbers will be given between 0 and another (e.g. 99). Therefore, rules must be formulated. For example, to simulate a coin flip using numbers from 0 to 99, the following rule could be used:

- 0 - 49 → heads

- 50 - 99 → tails - In some cases, there will be numbers which need to be rejected. These should be minimised to increase efficiency
**TO DO: Know how to generate realisations of a discrete uniformly distributed random variable. 2 Be able to use random variables to model discrete non-uniform random variables**