Thu Feb 27

• Questions about anything?

minimum spanning tree

• Define the problem
• Discuss Prim's algorithm .
  • greedy, growing a tree
  • need to keep track of closest vertex to (growing) tree
  • ... appropriate data structure is a min-heap with an extra "update" feature
  • O(E log(V)) with the special min-heap
• Discuss Kruskal's algorithm
  • greedy, growing a forest of min-edges
  • need to keep track of which vertices are in which trees
  • ... appropriate data structure is "disjoint set"
  • O(E log(E) ) ~ O(E log(V))

maze generation !

(depending on time ....)

shortest path

• define the problem
• Discuss Dijkstra's algorithm
  • greedy, growing a tree with tentative best-to-node
  • same min-heap-plus-modify give best result
• Discuss Floyd-Warshall algorithm
  • ... tricky recursive idea O(V**3) that finds all shortest distance paths ...
  • ... simplest version finds distance but not paths(!)