D1 Flashcards
Bubble Sort
Purpose
Sorts a list into ascending or descending order
[n]
The integer value of
Round to the nearest whole number
Bubble Sort
Algorithm
- 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
Quick Sort
Purpose
Sorts a list into ascending or descending order
Quick Sort
Algorithm
- 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
Binary Search
Purpose
To find an item in an ordered list
Binary Search
Algorithm
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
Bin Packing
Purpose
Fitting items into a space
Bin Packing
First Fit Algorithm
- 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
Bin Packing
First Fit Decreasing Algorithm
- Reorder the items so that they are in descending order, biggest first
- Apply the first fit algorithm to the new list
Bin Packing
Full Bin Packing Algorithm
- 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
Graph
Definition
A graph consists of vertices/nodes connected by edges/arcs
Simple Graph
Definition
Contains no loops
No more than one edge between each pair of vertices
Weighted Graph
Definition
A graph that has a number or distance associated with each edge
Su graph
Definition
A part of a bigger graph
Degree / Valency / Order
Definition
The degree/valency/order of a vertex is the number of edges incident to it
Connected
Definition
Two vertices are connected if there is a path between them
Path
Definition
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
Walk
Definition
A path in which you are permitted to repeat vertices
Cycle / Circuit
Definition
A closed path, the end vertex of the last edge is the start vertex of the first edge
Loop
Definition
An edge that starts and finishes at the same vertex
Digraph
Definition
A graph that has directions associated with its edges
Tree
Definition
A connected graph with no cycles
Spanning Tree
Definition
A spanning tree of a graph, G, is a su graph which includes all of the vertices in G and is also a tree
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
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
Isomorphic Graphs
Definition
Two graphs are isomorphic if they show the same information but drawn differently
Adjacency Matrix
Definition
A table that records the number of direct links between vertices
Distance Matrix
Definition
A table that records the weights of the direct links between vertices
Complete Graph
Definition
n vertices directly connected by an edge to every other vertex
Notation kn
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
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
Kruskal’s Algorithm
Algorithm
- Write out all the edges in ascending order of weight
- Select the arc of least weight to start the tree
- Consider the next arc of least weight
- if it would form a cycle reject it
- if not add it to the tree
- Repeat step 4 until the tree is complete
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
Prim’s Algorithm - Graph
Algorithm
- Choose any edge to start the tree
- Select the edge of least weight that joins a vertex in the tree to one not in the tree
- Repeat step two until the tree is complete
Prim’s Algorithm - Distance Matrix
Algorithm
- Choose any vertex to start the tree
- Delete the row in the matrix for the chosen vertex
- Number the column of the chosen vertex
- Circle the lowest undeleted entry in any of the numbered columns
- The ringed entry is the next vertex to be considered
- Repeat steps 2 to 5 until all rows are deleted
Dijkstra’s Algorithm
Purpose
Finds the shortest, cheapest or fastest route between two vertices
Dijkstra’s Algorithm
Algorithm
- Number the first vertex and enter working values for all vertices connected to it
- Number the next vertex of shortest distance come the start and enter a final value
- Use this final value to enter working values for all vertices connected to it
- Repeat steps 2 to 3 until you reach the end vertex
- The final value for the end vertex is the shortest distance to it from the start
- To find the route work backwards for the end vertex
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
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
Eulerian
Definition
A graph is eulerian if all the valences are even
A eulerian graph is always traversable
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
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
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
Dummy Activity
Purpose
Shows reliance
There can never be more than one activity between a pair of events
Critical Activity
Definition
Any activity on the critical path
Increasing the duration of a critical activity will increase the duration of the whole project
Critical Path
Definition
A path from the source to the sink node only following critical activities
Source Node
Definition
The first event in a project
Sink Node
Definition
The final event in a project
Early Event Time
Definition
The earliest time an event can start
The biggest value, working from the source to the sink node
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
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
Total Float
Formula
TotalFloat = LateEventTime - Duration - EarlyEventTime
Minimum Number of Workers
Formula
TotalDurationOfAllActivities / DurationOfTheProject
Objective Function
Definition
The aim of the problem
To maximise or minimise an algebraic expression
Constraints
Definition
Things that will prevent you from having an infinite number of each variable
Each constraint can be written as an inequality
Feasible Region
Definition
The region that contains all of the combinations of variables that are possible after applying the constraints
Optimal Solution
Definition
The feasible solution that meets the objective function
Solving a Linear Programming Problem
Steps
- Define the variables
- State the objective functions
- Write the constraints as inequalities
- Plot the inequalities on a graph and label the feasible region
- Find the optimal solution
Finding the Optimal Solution
Objective Line Method
- Set the objective function equal to any number
- Plot this line on the graph
- Move the line across the graph keeping the gradient the same
- 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 - Out the coordinates into the objective function to find the maximum/minimum value
Finding the Optimal Solution
Vertex Testing Method
- Consider each vertex of the feasible region
2 substitute the coordinates of each vertex into the objective function - Identify the vertex that gives the maximum/minimum value
Plotting Inequalities
≤ and ≥
Use a solid line _____________
Plotting Inequalities
< and >
Use a dashed line —————
