D1 - algorithms

D1 algorithm list and ways to solve (brief)

HideShow resource information
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
    • 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

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Decision resources »