Further Decision - Algorithms Flashcards
Bubble Sort (C1)
Comparison of adjacent items in a list, if they are out of order, you swap them.
Once a pass is completed without any swaps, the list is in order.
ALWAYS SORT BACK TO FRONT
‘Ascending’ (Rising value) => Start with organising biggest values at the end.
‘Descending’ (Decreasing value) => Start with organising smallest values at end.
Quick Sort (C1)
- Select pivot item (midpoint, round up for even number)
- Split items into 2 sub-lists
- Order greater items onto one side and smaller items on other side
- Select new pivot (midpoint of new set) and repeat until all numbers are ordered
First-Fit Algorithm (C1)
[Bin-packing]
- Take items in order given
- Fit into first bin possible
First-Fit DECREASING Algorithm (C1)
[Bin-packing]
Same as FF but first sort items into descending value before applying the algorithm.
(Fit into first bin possible)
Planarity Algorithm (C2)
- Identify Hamiltonian cycle
- Draw polygon with vertices in order of Hamiltonian cycle
- Draw all edges
- List edges inside polygon
- Label an edge (I)
- If any cross: NON-PLANAR; if none cross: label (O)
- Repeat until found to be planar or not
What does the Planarity Algorithm do?
Identify whether or not a graph is PLANAR or not by redrawing to identify whether the edges cross.
Prim’s Algorithm (C3)
- Choose any vertex to start
- Select an adjoining arc of least weight that connects to a vertex not yet in the tree
- Repeat until all vertices are connected
Kruskal’s Algorithm (C3)
- Sort edges into ascending weights
- Select arc of least weight to start the tree
- Select next arc of least weight which DOESN’T form a cycle.
- Repeat until all vertices are connected
What does Kruskal’s Algorithm do?
Find a Minimum Spanning Tree
Prim’s vs Kruskal’s? (C3)
Prim’s = Vertices
Kruskal’s = Edges
Prim’s => Distance Matrix Method (C3)
- Choose any vertex to start
- Delete the row of the vertex
- Number the vertex’s column
- Circle the lowest undeleted entry in the column
- Move to the corresponding column of the circled no.
- Repeat the process for each circled number
What does Prim’s Algorithm do? (C3)
Find a Minimum Spanning Tree.
Dijkstra’s Algorithm Method (C3)
_______________________________
|Vertex|Label Ord|Final Label|
Working Values
- Label start vertex S with FL 0
- Record working values at each connecting vertex.
- Look at all vertices and write smallest value as FL on relevant vertex
- Repeat until destination vertex (T) has a FL
- Shortest path = ST
What does Dijkstra’s Algorithm do? (C3)
Finds the shortest path between two vertices in a network.
Floyd’s Algorithm Method (C3)
Complete initial distance (two-way) table by recording distances between vertices (if path is not direct, i.e. must pass via another vertex, label with infinity symbol)
What does Floyd’s Algorithm do? (C3)
Find the shortest path between every pair of vertices in a network.
Route Inspection Algorithm (C4)
WHY? = Find shortest route in network which traverses every arc at least once and returns to its starting point.
- If graph is Eulerian cycle, shortest route = total weight
- Identify vertices with odd degree
- Consider all possible pairings
- Select complete pairing with least sum
- Add pairing sum to weight of network
With 6 odd nodes, 2 of these will usually be the first and last vertex
Weight of arc XY (C3)
[Dijkstra’s algorithm]
= FL of Y - FL of X
Working Value (at Y) (C3)
[Dijkstra’s algorithm]
= Final Label at X + Weight of arc XY
Travelling Salesman Problem Aim (C5)
Find a good (not optimal) tour of minimum total weight.
Practical Travelling Salesman Problem (C5)
WHY? = Find an upper bound
Each vertex must be visited AT LEAST ONCE before returning to the start.
- Use Prim’s or Kruskal’s to find MST for network (guarantees each vertex is included)
- Double the weight of the MST so that completing the cycle is guaranteed
(= INITIAL UB) - Seek ‘shortcuts’) make use of some non-included arcs enabling a bypass of a repeat
Triangle Inequality (reminder) (C5)
Longest side of any triangle </= sum of two shorter sides
Classical Traveling Salesman Problem (C5)
WHY? = Find a lower bound
Each vertex must be visited EXACTLY ONCE before returning to the start
- Remove each vertex in turn, together with arcs
- Find RESIDUAL MST & its length
- Add RSMT to ‘cost of reconnecting deleted vertex by two shortest, distinct arcs and note the totals.
- Greatest total = lower bound
- If LB = Hamiltonian cycle or = UB, solution is optimal.
Nearest Neighbour Algorithm (C5)
Same as Prim’s algorithm, EXCEPT you look for the nearest vertex to the last vertex chosen, rather than any vertex in the tree.
Prim’s vs Nearest Neighbour
What does the Nearest Neighbour Algorithm do?
Finds an upper bound for the TSP.
Formulating a LP problem (C6)
- Define decision variables (e.g. x, y, z)
- State objective (min/max)
- Write constraints as inequalities
- Find min/max point on graph by looking for first/last point covered by objective line
Solving a LP problem (C6)
Vertex testing method:
- Find coordinates of each vertex of feasible region
- Evaluate obj. function at each point
- Select optimal vertex
[for integer values, make a BOX of integer coordinates around and test each one, making sure its in the feasible region.]
Formulating LP problems using Simplex Method (C7)
- Formulate LP problem
- Transform inequalities into equations via slack & artificial variables
- Put into a tableau
(e.g. b.v.|x|s1|value)
Slack & Artificial Variables (C7)
Slack: Represent difference between actual quantity & maximum possible value of quantity. Used for: >/=
Artificial: Used for: </=
Solving LP problem using Simplex Method (C7)
- Create tableau
- Find column of most -ve value in obj. row
- Find smallest theta value (value column entry/pivot column entry)
- Make new table by swapping b.v. of pivot with old constraint
- Make pivot value 1 and all other values in column 0 and state operations used
- Repeat until all P values are +ve
- Solution = Value Column
‘Integer Solution Needed’??? (SM) (C7)
Use LP BOX method:
Test 4 points around optimal solution forming a square. Find set of points which fit constrains & give a maximum for obj. function.
‘MINIMISE’ Simplex Method (C7)
Same steps as maximise except…
- Define new obj. function (P) as negative of original obj. function (Q)
- After maximising P, write solution as negative of P to minimise Q
What does the Simplex Method do? (C7)
Determine if a vertex, on the edge of a feasible region, is optimal.
AND
Decide which adjacent vertex to move to to increase the obj. function’s value.
Solving LP problem using TWO STAGE Simplex Method
Scheduling Diagrams vs Gant Charts vs Resource Histograms
