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