Decision

Preparing to Revise/not forget

• 6 Algorithms
• 6 revision cards
• 6 questions

Decision 1

• Kruskal
• Prims
• Traveling Salesman
• (Upper bound - Nearest Neighbour)
• (Lowerbound - delete and Prims)

Kruskal

• List everything smallest to largest
• Select - No cycles
• Total
• Tree (Lable)

Prim's

• Start at....
• Choose smallest that connects. (LIST)
• No cycles
• Tree

Traveling Salesman

• Upper Bound - Nearest Neighbour
• Lower Bound (Delete and Prim's)
• Lower

UB - Nearest Neighbour

• Start at...
• What is nearest? (not already vistied)
• Go everywhere
• Go home - Tour

LB - Del & Prim's

• Start @...
• Delete row and column
• Pick smallest two
• Prim's on the rest

Prim's on Table

• Start at...
• cross out row
• highlight column
• circle smallest in highlighted
• write down and repeat

Decision 2

• Dijkstra
• Chinese Postman
• Critical Path

Chinese Postman Problem

• Odd nodes (Always 4)
• Pairs of odds (3sets of 2 pairs)
• Shortest
• Total
• CPP = Total + Shortest
• (Start and finish same place)

Chinese Postman

• (Different start & finish)
• Start(node) Finish(node) Repeat(2nodes-pair)
• CPP = Total + repeat

Untitled Slide