# D1 - algorithms

D1 algorithm list and ways to solve (brief)

HideShow resource information
• 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
• 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
• 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
• 2. move other options to correct side (keep the order)
• 3. circle pivot and square used pivots