Homework 5

Details

You should work alone on this assignment.

1. Find an optimal binary search tree for keys with probabilities 0.4, 0.05, 0.10, 0.05, 0.20, 0.15, 0.05. Show all of your work and draw the tree with numbers in the nodes to clearly indicate which one is where.
2. Use Floyd's algorithm on the Traveling Salesman problem Triforce Floyd in Algoraph to compute the all-pairs shortests paths. (Ignore the fact this this is a Traveling Salesman problem). Make sure to click Show node indices to get the vertex indices to display (Otherwise your matrix will probably be wrong).
   Show all of your work. In particular, show the matrix at each of the 6 steps and any scratch work you need along the way.
   Based on your solution, give the vertcies in the shortest path from 3 to 5 and specify the weight of the path. Make sure you look back at the graph and verify that the solution makes sense.