D1 Flashcards
How do you solve a problem containing Kruskals Algorithm?
- List all arcs in size order
- Fill in in order
- Do not form loops
How do you solve a problem containing Prims Algorithm?
- Select a node
- Find smallest connecting
- Keep going until all nodes have been joined
- No loops
How do you solve a problem containing Dijkstras Algorithm?
- Pick a node
- Give nodes connecting a temporary label
- Make smallest permanent
- Repeat
How do you solve a problem containing Chinese Postman Algorithm?
- Find all odd nodes
- Connect two smallest connections and connect if Eularian
- If semi-eulerian is required leave two odd
When would you need to use the Chinese Postman algorithm?
When you need to go along every arc
How do you solve a problem containing Travelling Salesperson Algorithm?
- Find upper bound by nearest neighbour
- Find lower bound
- Put in an inequality
How do you find the upper bound for travelling salesperson?
Use nearest neighbour:
- Pick node
- Find smallest connecter
- Join all smallest until back to first node
- Algorithm fails if cannot return to first
- To find best do for all nodes
How do you find the lower bound for travelling salesperson?
- Choose a node
- Find MST
- Add node back in by drawing back the two connecting arcs with the lowest weights
What are the 8 rules of graphs?
- Total order of nodes is twice the number of arcs (so total order must be even)
- There cannot be an odd number of odd nodes
- For a connected graph, the order of each node must be at least 1
- For a simple graph with n nodes, the order of each node must not be bigger than n-1
- An Eulerian graph has all even nodes
- A semi-Eulerian graph has exactly 2 odd nodes
- Any tree with n nodes must have exactly n-1 arcs
- Kn with n nodes will have a total of 1/2n(n-1) arcs.
How do you solve a problem containing the first fit Algorithm?
- Put into first available bin in order given
How do you solve a problem containing the first fit decreasing Algorithm?
- Sort into decreasing order
- Apply first fit
How do you solve a problem containing the shuttle sort Algorithm?
- Compare first 2 numbers and swap is necessary
- Underline first number
- Compare first two numbers not underlined
- Swap with underlined if necessary
- Repeat 2-3
How do you solve a problem containing the bubble sort Algorithm?
- Compare first 2 numbers
- Take top number to end swapping if necessary
- Highest number now in place
- Underline last number
- Repeat 1-3
- Do not compare underlined numbers
How do you solve order of algorithm questions if the algorithm is of quadratic order?
- Write info given
- Work out scaling factor
- x unknown link by scaling factor squared
How do you solve order of algorithm questions if the algorithm is of cubic order?
- Write info given
- Work out scaling factor
- x unknown link by scaling factor cubed
