D1 - algorithms
D1 algorithm list and ways to solve (brief)
- Created by: ben mackett
- Created on: 11-05-14 19:44
View mindmap
- D1 - algorithms
- Prim
- 1. start at selected vertex
- 2. select ac of last weight that join the vertex
- 3. repeat for all selected arcs
- Dijkstra
- 1. label the start and end vertex
- 2. record a working value at any vertex that touches a closed vertex
- 3. select the smallest value to get to end
- 4. retrace the steps to return to start
- 5. write the order that you travelled stating each arc
- Kruskal
- 1. list all arcs in weight order
- 2. select the arc of least weight
- 3. consider the next lowest arc
- 4. if it forms a cycle reject otherwise accept
- 5. repeat until all arcs have been considered and all vertices have been added
- bubble sort
- 1. circle first 2 numbers
- 2. switch to be in order
- 3. repeat with all numbers
- 4. repeat on new line until no change occurs
- Bin Packing
- 1st fit
- 1. take ist number and place it in first available bin
- 2. repeat for all numbers
- 1st it decreasing
- 1. order all numbers from large to small
- 2. repeat as done for 1st fit
- full bin
- 1. match numbers that add to full bin size
- 2. for unmatched numbers place in 1st available bin
- 1st fit
- Matchings
- 1.to gain initial matching pair 1st option
- 2. to gain improved matching change unmatched people to vertex knocking people off
- 3. for full matching ensure all x's are touching a y
- Quick Sort
- 1. locate pivot
- 4. repeat until all squares
- 2. move other options to correct side (keep the order)
- 3. circle pivot and square used pivots
- Route inspection
- 1. if all vertex are even the network is traversable
- 2. identify all odd valencies
- 3. consider pairings for these vertex
- 4. select the smallest pairing
- 5. double this pairing. it is now traversable
- Prim
- 2. move other options to correct side (keep the order)
- 3. circle pivot and square used pivots
Comments
No comments have yet been made