Further Decision - Algorithms Flashcards

(48 cards)

1
Q

Bubble Sort (C1)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Quick Sort (C1)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

First-Fit Algorithm (C1)

A

[Bin-packing]
- Take items in order given
- Fit into first bin possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

First-Fit DECREASING Algorithm (C1)

A

[Bin-packing]
Same as FF but first sort items into descending value before applying the algorithm.

(Fit into first bin possible)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Planarity Algorithm (C2)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does the Planarity Algorithm do? (C2)

A

Identify whether or not a graph is PLANAR or not by redrawing to identify whether the edges cross.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Euler’s Handshaking Lemma (C2)

A

Σ Degrees = 2 x no. of arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Prim’s Algorithm (C3)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Kruskal’s Algorithm (C3)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does Kruskal’s Algorithm do?

A

Find a Minimum Spanning Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Prim’s vs Kruskal’s? (C3)

A

Prim’s = Vertices
Kruskal’s = Edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Prim’s => Distance Matrix Method (C3)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does Prim’s Algorithm do? (C3)

A

Find a Minimum Spanning Tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Dijkstra’s Algorithm Method (C3)

A

_______________________________
|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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does Dijkstra’s Algorithm do? (C3)

A

Finds the shortest path between two vertices in a network.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Floyd’s Algorithm Method (C3)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does Floyd’s Algorithm do? (C3)

A

Find the shortest path between every pair of vertices in a network.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Route Inspection Algorithm (C4)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Weight of arc XY (C3)

A

[Dijkstra’s algorithm]
= FL of Y - FL of X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Working Value (at Y) (C3)

A

[Dijkstra’s algorithm]
= Final Label at X + Weight of arc XY

21
Q

Travelling Salesman Problem Aim (C5)

A

Find a good (not optimal) tour of minimum total weight.

22
Q

Practical Travelling Salesman Problem (C5)

A

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
23
Q

Triangle Inequality (reminder) (C5)

A

Longest side of any triangle </= sum of two shorter sides

24
Q

Classical Traveling Salesman Problem (C5)

A

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.
25
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.
26
What does the Nearest Neighbour Algorithm do?
Finds an upper bound for the TSP.
27
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
28
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.]
29
Formulating LP problems using Simplex Method (C7)
- Formulate LP problem - Transform inequalities into equations via variables: Slack (≤) and/or Artificial (≥) - Put into a tableau (e.g. b.v.|x|s1|value)
30
Slack & Artificial Variables (C7)
Slack: Represent difference between actual quantity & maximum possible value of quantity. Used for: >/= Artificial: Used for:
31
Solving LP problem using Simplex Method (C7)
- Formulate (see other FC) - 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
32
'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.
33
'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
34
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.
35
Solving LP problem using TWO STAGE Simplex Method (C7)
- Formulate - Use I = -(a1 + a2), sub in a1 & a2 and rearrange to = value - Use SM to make a1 & a2 = 1 & everything else = 0 → Basic feasible solution is found. - Remove artificial columns & I row to make new table - Use SM to solve new table - Solution = Value Column
36
Solving LP problem using BIG M Simplex Method (C7)
AIM: Drive artificial Vs to 0 M = arbitrarily large number - Formulate - Subtract M(a1 + a2 + ...) from obj. function - Sub. in a1, rearrange as in 2S method (= value) - Use SM to solve tableau - Solution = Value column Big M method can be used instead of 2S when there is ≥ constraints.
37
Gantt (Cascade) Charts vs Resource Histograms vs Scheduling Diagrams (C8)
Gantt → Highlights range of time in which each activity can be completed Resource → Identifies how many workers are needed each day, and whether this can be reduced using floats Scheduling → Identifies minimum no. of workers needed for project by maximising each workers' potential
38
Gantt/Cascade Chart (C8)
Provides a graphical way to represent the range of possible start & finish time for all activities on a single diagram.
39
Worker Rules (C8)
- No worker can carry out more than one activity at any time. - Once a worker(s) has started an activity, they must finish it - Once a worker(s) has finished an activity they are immediately available to start another
40
Resource Histogram (C8)
Shows the number of workers active at any given time. It is constructed assuming each activity starts at the earliest time possible, then it can be used to identify which activities may be delayed to minimise the no. of workers required → Resource Levelling
41
Scheduling Diagrams (C8)
Scheduling = Assigning workers to activities. - Use first available worker - Assign lowest value activity (if there is a choice)
42
Lower Bound (no. of workers needed to complete project within critical time) (C8)
Sum of all activity times / Critical time of project
43
COMMON COMBINATION: Nearest Neighbour
Floyd's/Prim's
44
Prim's vs NN
45
Floyd's vs NN
46
Pros cons of algorithms and speed of algorithm, what algorithm questions may look like, link precedence tables and dijjstras?
Link pros cons to order - links to speed;
47
48
- Make FCs on when to use each algorithm in decision? (using chapter summaries?) o + What questions for each may look like o + what algorithms might be used together o + Link precedence tables and dijkstras for part c