D1 Flashcards
(63 cards)
0
Q
Bubble Sort
Purpose
A
Sorts a list into ascending or descending order
1
Q
[n]
A
The integer value of
Round to the nearest whole number
2
Q
Bubble Sort
Algorithm
A
- Starting at the beginning of the list compare adjacent values
- if they are in order leave them
- if not swap them - When you get to the end of the list repeat step one, each repetition of step one is called a pass
- When a pass has been completed without any swaps the list is in order
3
Q
Quick Sort
Purpose
A
Sorts a list into ascending or descending order
4
Q
Quick Sort
Algorithm
A
- Select the middle value as a pivot by circling it
- Write out the items that are lower than the pivot in the order they appear in the list before the pivot
- Write down the pivot in a square as a fixed value
- Write down the remaining items that would come after the pivot in the order that they appear in the list
- Each side of the pivot(s) is now treated as a separate sub lists
- For each sub list repeat steps 1-5
- Stop when all items are fixed values, in a square
5
Q
Binary Search
Purpose
A
To find an item in an ordered list
6
Q
Binary Search
Algorithm
A
T is the value you are looking for
m is the value from the list
n is the number of items left in the list
- m = [n+1 / 2]th value
- -if m=T item is found, end
- if mT discard m and all items before it
- Repeat steps 1 to 2 until T is found or the list is exhausted
7
Q
Bin Packing
Purpose
A
Fitting items into a space
8
Q
Bin Packing
First Fit Algorithm
A
- Take the items in the order given
2. Place each item in the first bin that it will fit in starting from bin 1 each time
9
Q
Bin Packing
First Fit Decreasing Algorithm
A
- Reorder the items so that they are in descending order, biggest first
- Apply the first fit algorithm to the new list
10
Q
Bin Packing
Full Bin Packing Algorithm
A
- Pack the first bins with any combinations of items that will completely fill a bin
- Pack any remaining items using the first fit algorithm (not decreasing) using the original order given
11
Q
Graph
Definition
A
A graph consists of vertices/nodes connected by edges/arcs
12
Q
Simple Graph
Definition
A
Contains no loops
No more than one edge between each pair of vertices
13
Q
Weighted Graph
Definition
A
A graph that has a number or distance associated with each edge
14
Q
Su graph
Definition
A
A part of a bigger graph
15
Q
Degree / Valency / Order
Definition
A
The degree/valency/order of a vertex is the number of edges incident to it
16
Q
Connected
Definition
A
Two vertices are connected if there is a path between them
17
Q
Path
Definition
A
A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex if the next edge in the sequence
No vertex is repeated
18
Q
Walk
Definition
A
A path in which you are permitted to repeat vertices
19
Q
Cycle / Circuit
Definition
A
A closed path, the end vertex of the last edge is the start vertex of the first edge
20
Q
Loop
Definition
A
An edge that starts and finishes at the same vertex
21
Q
Digraph
Definition
A
A graph that has directions associated with its edges
22
Q
Tree
Definition
A
A connected graph with no cycles
23
Q
Spanning Tree
Definition
A
A spanning tree of a graph, G, is a su graph which includes all of the vertices in G and is also a tree
24
Minimum Spanning Tree
| Definition
The minimum spanning tree of a graph, G, is the spanning tree of smallest weight that includes all of the vertices in G
25
Bipartite Graph
| Definition
A graph which consists of two superset sets of vertices set X and set Y
Edges can only connect vertices between the two sets not within them
26
Isomorphic Graphs
| Definition
Two graphs are isomorphic if they show the same information but drawn differently
27
Adjacency Matrix
| Definition
A table that records the number of direct links between vertices
28
Distance Matrix
| Definition
A table that records the weights of the direct links between vertices
29
Complete Graph
| Definition
n vertices directly connected by an edge to every other vertex
Notation kn
30
Complete Bipartite Graph
| Definition
Every vertex in set x is connected by an edge to every vertex in set y
Notation kx,y where x is the number of vertices in set X and y is the number of vertices in set Y
31
Kruskal's Algorithm
| Purpose
Finds the shortest/cheapest/fastest way of linking all the nodes into one system
Finds the minimum spanning tree of a graph
It considers edges
32
Kruskal's Algorithm
| Algorithm
1. Write out all the edges in ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least weight
- if it would form a cycle reject it
- if not add it to the tree
4. Repeat step 4 until the tree is complete
33
Prim's Algorithm
| Purpose
Finds the shortest/cheapest/fastest way of linking all the modes into one system
Finds the minimum spanning tree if a graph
Considers vertices
Can be applied to a graph or a distance matrix
34
Prim's Algorithm - Graph
| Algorithm
1. Choose any edge to start the tree
2. Select the edge of least weight that joins a vertex in the tree to one not in the tree
3. Repeat step two until the tree is complete
35
Prim's Algorithm - Distance Matrix
| Algorithm
1. Choose any vertex to start the tree
2. Delete the row in the matrix for the chosen vertex
3. Number the column of the chosen vertex
4. Circle the lowest undeleted entry in any of the numbered columns
5. The ringed entry is the next vertex to be considered
6. Repeat steps 2 to 5 until all rows are deleted
36
Dijkstra's Algorithm
| Purpose
Finds the shortest, cheapest or fastest route between two vertices
37
Dijkstra's Algorithm
| Algorithm
1. Number the first vertex and enter working values for all vertices connected to it
2. Number the next vertex of shortest distance come the start and enter a final value
3. Use this final value to enter working values for all vertices connected to it
4. Repeat steps 2 to 3 until you reach the end vertex
5. The final value for the end vertex is the shortest distance to it from the start
6. To find the route work backwards for the end vertex
38
Traversable
| Definition
A graph is traversable if it can be drawn I one go without removing the pen from the paper, starting and finishing in the same place
39
Semi-Traversable
| Definition
A graph is semi-traversable if it can be drawn in one go without revving the pen from the paper, starting and finishing at different vertices
40
Eulerian
| Definition
A graph is eulerian if all the valences are even
| A eulerian graph is always traversable
41
Semi-Eulerian
| Definition
A graph is semi-eulerian if exactly two of its vertices have and odd valency and all of the others are even
A semi-eulerian graph is semi-traversable
42
Route Inspection / Chinese Postman Algorithm
| Purpose
Finds the weight of the shortest route which traverses every arc at least once and returns to the starting point
43
Route Inspection / Chinese Postman Algorithm
| Algorithm
- If a graph is eulerian the shortest route that traverse each edge and returns to the starting point is equal to the weight of the network
- If a graph is semi-eulerian, repeat the shortest route between the two odd vertices and add to the total weight of the network
- if there are more than two odd vertices:
1. Consider the possible pairings of the odd vertices
2. Select the combination of pairings which gives the smallest total weight
3. Add the weight to the total weight of the network
44
Dummy Activity
| Purpose
Shows reliance
| There can never be more than one activity between a pair of events
45
Critical Activity
| Definition
Any activity on the critical path
| Increasing the duration of a critical activity will increase the duration of the whole project
46
Critical Path
| Definition
A path from the source to the sink node only following critical activities
47
Source Node
| Definition
The first event in a project
48
Sink Node
| Definition
The final event in a project
49
Early Event Time
| Definition
The earliest time an event can start
| The biggest value, working from the source to the sink node
50
Late Event a Time
| Definition
The latest an event can start without delaying the project
| The smallest number working from the sink node to the source node
51
Total Float
| Definition
The total float of an activity is the amount of time that it can be delayed by without affecting the duration of the project
52
Total Float
| Formula
TotalFloat = LateEventTime - Duration - EarlyEventTime
53
Minimum Number of Workers
| Formula
TotalDurationOfAllActivities / DurationOfTheProject
54
Objective Function
| Definition
The aim of the problem
| To maximise or minimise an algebraic expression
55
Constraints
| Definition
Things that will prevent you from having an infinite number of each variable
Each constraint can be written as an inequality
56
Feasible Region
| Definition
The region that contains all of the combinations of variables that are possible after applying the constraints
57
Optimal Solution
| Definition
The feasible solution that meets the objective function
58
Solving a Linear Programming Problem
| Steps
1. Define the variables
2. State the objective functions
3. Write the constraints as inequalities
4. Plot the inequalities on a graph and label the feasible region
5. Find the optimal solution
59
Finding the Optimal Solution
| Objective Line Method
1. Set the objective function equal to any number
2. Plot this line on the graph
3. Move the line across the graph keeping the gradient the same
4. To maximise take the vertex of the feasible region that the line crosses last
To minimise take the vertex of the feasible region that the line crosses first
5. Out the coordinates into the objective function to find the maximum/minimum value
60
Finding the Optimal Solution
| Vertex Testing Method
1. Consider each vertex of the feasible region
2 substitute the coordinates of each vertex into the objective function
3. Identify the vertex that gives the maximum/minimum value
61
Plotting Inequalities
| ≤ and ≥
Use a solid line _____________
62
Plotting Inequalities
| < and >
Use a dashed line ---------------
