Decision 1

Joseph McAuliffe
Mind Map by , created almost 4 years ago

Decision 1 Mind Map

14
2
0
Tags
Joseph McAuliffe
Created by Joseph McAuliffe almost 4 years ago
Controversy: How Popular was the Nazi Regime?
shann.w
Decision 1
Lucy Denver
The bones in the body
Thomas Marshall
CHEMISTRY C1 3
x_clairey_x
Core HR Knowledge
jkim05
Democracy
Dan Easterbrook
AS Psychology Unit 1 - Memory
Asterisked
OCR AS Biology
joshbrown3397
The Muscles in the body
Thomas Marshall
Decision 1
1 Chapter 1 ~ Algorithms
1.1 Following instructions
1.2 Flow chart
1.2.1 Start/End
1.2.2 Instruction
1.2.3 Decision
1.3 Sorts
1.3.1 Bubble
1.3.1.1 Compare adjacent items
1.3.1.2 "Passes"
1.3.2 Quick
1.3.2.1 Pivots to create sub-lists
1.3.2.1.1 (n+1)/2 and round up if necessary to find pivots
1.4 Binary Search
1.4.1 Search an ordered list
1.4.2 Select middle item using (n+1)/2 and round up if necessary
1.4.2.1 Consider it compared to value searching for
1.5 Bin Packing
1.5.1 First-fit
1.5.1.1 In order given
1.5.1.2 Quick but not likely to lead to a good solution
1.5.2 First-fit decreasing
1.5.2.1 With a list in descending order
1.5.2.2 Fairly good solution but not always optimal
1.5.3 Full-bin
1.5.3.1 Uses observation to fill bins
1.5.3.2 Good solution but difficult, especially with lots of numbers
2 Chapter 2 ~ Graphs and Networks
2.1 Points - Nodes/Vertices
2.1.1 List is called the vertex set
2.2 Lines - Arcs/Edges
2.2.1 If numbers associated, it is a weighted graph or network
2.2.2 List is called the edge set
2.3 Terms: Subgraph, Degree/Valency/Order, Path, Walk, Cycle/Circuit
2.4 Connected, Loop, Simple Graph, Directed Edges, Digraph
2.5 Trees/Spanning Tree
2.6 (Complete) Bipartite and Complete graphs
2.7 Isomorphic graphs
2.8 Adjacency and distance matrices
3 Chapter 3 ~ Algorithms on Networks
3.1 Minimum Spanning Tree (no cycles)
3.1.1 Kruskal's
3.1.1.1 Using ascending weights
3.1.2 Prim's
3.1.2.1 Least weight from chosen vertex
3.1.2.1.1 Easily done with a distance matrix
3.2 Dijkstra's Alorithm
3.2.1 Shortest path between two vertices
3.2.2 Select smallest working value
3.2.3 Work backwards to find path
3.2.4
4 Chapter 4 ~ Route Inspection (Chinese Postman)
4.1 Is a graph traversable?
4.1.1 If all of the valencies in a graph are even, the that graph is Eulerian and therefore traversable
4.1.2 If the graph has just two valencies that are odd, then the graph is semi-Eulerian. In this case, the start and finish points will be the two vertices with odd valencies
4.1.3 A graph is not traversable if it has more than two odd valencies
4.2 Finding the shortest route in a network
4.2.1 For semi-Eulerian graph, the shortest path between the two odd vertices will have to be repeated
4.2.2 Algorithm
4.2.2.1 1 ~ Identify any vertices with odd valency
4.2.2.1.1 2 ~ Consider all possible pairings of these vertices
4.2.2.1.1.1 3 ~ Select the complete pairing that has the least sum
4.2.2.1.1.1.1 4 ~ Add a repeat of the arcs indicated by this pairing to the network
4.3 Traversable ~ sum of each arc's weight will be the weight of the network
5 Chapter 5 ~ Critical Path Analysis
5.1 Precedence Table/Dependence Table
5.1.1 Shows what must be completed for an activity to start
5.1.2 Used to create activity network
5.1.2.1 0 node ~ source node
5.1.2.2 Last node ~ sink node
5.1.2.3 Often can take a couple of times to get layout correct
5.2 Dummies
5.2.1 Each activity must be uniquely represented
5.2.2 C depends on A but D depends on A and B
5.3 Early and Late event times
5.3.1 Early ~ use largest number
5.3.1.1 From a forward pass/forward scan
5.3.2 Late ~ use smallest number
5.3.2.1 From a backward pass/backward scan
5.3.3 Total float = latest finish time - duration - earliest start time
5.3.4 Cascade (Gantt) Charts
5.3.4.1 Shows time leeway
5.3.4.2 Dotted box represents float
5.3.4.3 Look halfway before to see how many activities
5.3.4.3.1 Consider float
5.4 Critical activities
5.4.1 Change to time would impact overall time
5.4.1.1 At each node, early event time = late event time
5.4.2 Critical path
6 Chapter 6 ~ Linear Programming
7 Chapter 7 ~ Matchings