Decision Flashcards
Algorithm
A finite sequence of step-by-step instructions carried out to solve a problem
Bubble Sort
Compare Adjacent items in the list:
· If in order, then leave them
· If out of order, then swap terms.
Compare all pairs in the list
Sort is complete when a full pass with no swaps is complete.
Quick Sort
Select midpoint as pivot, write all terms smaller than pivot on the left and all the terms bigger than the pivot on the right hand side.
Repeat this for the sublists produced.
Sort complete when all terms have been a pivot.
What are the 3 bin packing algorithms?
First-fit - considering items in the order they are given in.
First-Fit decreasing - order items in decreasing order and apply first fit algorithm.
Full-Bin - by inspection select items that will combine to fill bins, then apply first fit to remaining terms.
Order of an algorithm
A measure of the run time of the algorithm.
Increasing the size from m to n, increases the algorithm by a factor of f(m)/f(n)
Increasing the size of a problem by k
· An algorithm of linear order will take k times longer.
· An algorithm of quadratic order will take k² times longer.
· An algorithm of cubic order will take k³ times longer.
A graph
A graph consists of nodes which are connected by edges.
A Weighted Graph
Edges have a number associated with them, denoted there size.
A subgraph
A subgraph is a section of an original graph, showing only select nodes and edges.
Degree, Valency, or Order of a node
The number of edges going into a node.
Odd and Even Nodes
Denoted is the order of a node is odd or even.
Walk
Path
Trail
Cycle
A walk is a route through a graph from one node to the next.
A path is a walk in which no node is visited more than once.
A trail is a walk in which no edge is visited more than once.
A cycle is a walk where the start and end node are the same and no other node is visited more than once.
Hamiltonian Cycle
A cycle that includes every vertex.
Connected Graph
A graph where every vertex is connected. There is a path to any vertex from any vertex.
A Loop
An edge which starts and finished at the same vertex.
Simple graph
No Loops and there is a single edge from every vertex to every vertex.
Directed Graph
Edges have a direction and can only be commuted in that direction.
Euler’s Handshaking Lemma
In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges. Number of odd nodes must be even.
A tree
A connected graph with no cycles
A Spanning Tree
A subgraph which includes all the vertices of the original graph and is also a tree.
A Complete Graph
A graph in which every vertex is directly connected by a single edge to each other vertex.
An Isomorphic Graph
Graphs which show the same information but may be drawn differently
Adjacency Matrix
A matrix describing the number of arcs joining the corresponding vertices.
Distance Matrix
A matrix describing the weight of arcs connecting vertices.
Minimum Spanning Tree
A spanning tree such that the total length of its arcs are as small as possible.
Kruskal’s Algorithm
1) sort edges into ascending order of weight
2) select the edge of least weight
3) select from edges not previously selected, the edge of least weight that does not form a cycle
4) repeat step 3 until selected edges form a spanning tree
Prim’s Algorithm
1) choose starting vertex
2) choose vertex nearest to starting vertex, add that vertex and add its associated edge to the tree
3) connect to the tree of connected vertices that vertex that is nearest to any vertex in the connected set, but to a vertex not already in the tree
4) repeat step 3 till all vertices are connected to the tree
Prim’s Algorithm with a distance matrix
1) start with the matrix representing the network and choose a starting vertex. Delete the row corresponding to to that vertex
2) label with ‘1’ the column corresponding to the start vertex, ring the smallest undeleted entry in that column
3) delete the row corresponding to the entry you just ringed
4) label with the next number the column corresponding to the vertex you just ringed
5) ring the lowest undeleted entry in all labelled columns
6) repeat steps 3, 4 and 5 till all rows are deleted. The ringed entries represent the edges in the minimum connector
Dijkstra’s Algorithm
1) give start vertex label 0
2) give each vertex connected to start vertex a working value
3) find smallest working value and give it its permanent label
4) update working values at any unlabelled vertex that can be reached from V
5) repeat steps 3 and 4 till destination vertex given permanent label
Eulerian Graph
Contains a trail that includes every edge but starts and finishes at the same vertex. Graph must be connected and have all even vertices.
Semi-Eulerian Graph
Contains a trail that includes every edge but starts and finishes at different vertices. Graph must be connected and have exactly 2 odd vertices.
Route Inspection Algorithm
1) list all odd vertices
2) form all possible pairings of odd vertices
3) for each pairing find the edges that are best to repeat and find the sum of the lengths of these edges
4) choose the pairing with the smallest sum, construct a route that repeats these edges
Vertex Method to find the Optimal Point
Find the Feasible Region
Find the co-ordinates of the vertices of the feasible region
Trial each vertex to see which gives the optimal solution
Precedence Table
A table that shows which activities must be completed before others are started.
Dummy Activity
No time or cost. Shows the dependancy between activities.
Early Event Time
The earliest time an activity can start allowing all preceding activities to occur, These can be found on the forward pass.
Late Event Time
The latest time that an event can be left without exceeding the time needed for the project. These can be found on the backwards pass.
Critical Activity and Path
Critical activities are any activities with equal Early and Late Event Times. Critical activities form the critical path.
Float
Total Float = Latest finish time - Duration - Earliest start time
Gantt Charts
A visual showing the critical path, and the earliest start and latest finish time of each activity.
