Assignment:
Problem: Minimum Spanning Tree-
a. Using the MST algorithm (section 8.6 in text or the one taught in class), provide the minimum spanning tree for the above graph (not drawn to scale). What is the length of your spanning tree?
b. The MST algorithm is a "greedy algorithm" because at each step it chooses the shortest arc that can be used to expand the connected network. For the minimum spanning tree problem, such a greedy approach produces an optimal solution. For other optimization problems, a greedy algorithm will NOT always produce an optimal solution. Describe in words an optimization problem where a greedy algorithm will NOT produce an optimal solution. Also describe why using a greedy approach can lead you astray (i.e. not towards the optimal solution). Note, you are encouraged to use other resources (e.g., the internet, your textbook, your friend), just cite your sources and make sure your answer is written in your own words.