1 Bad Coin Proof Redo the proof from last week with a different coin set. Use f1; 6; 10g. Simple counterproof: 12: A*=6; 6, A=10; 1; 1 2 Minimum Spanning Tree - Prim’s Algorithm Remember that the graph implementation affects the runtime. Start with AdjacencyMatrix then try AdjacencyList. Using AL: 1. If we were to run Prims algorithm on a DAG (directed acyclic graph), where the first selected node (source) is the root of the DAG (connected to every other node), would the runtime change? 2. What if the source can be reached by every other node? If we ran Prims, and only considered adding edges that enter a discovered node, would the runtime change? (In other words, this is the same as above but all the directed edges are reversed and Prim’s searches backwards from the same source.) 3. What if we used a different graph implementation? 1
