Problem 2: Minimum spanning trees Grading criteria: correctness of code. Note: you will need to reference your answer to problem 1, but this problem will be graded independently .e., as if your answer to problem 1 is correct, whether it is or not). William Stein announces the formation of CoCalc Fiber, a new broadband network which will connect the capital cities of the 48 continental United States (excluding Alaska and Hawai) with a series of underground cables joining certain pairs of cities. Naturally, William wants to minimize the cost of building this network; he assumes that the cost of building a network link between some pairs of cities is proportional to the distance between those two cities. 2a. Define a function that implements the haversine formula: given two latitude-longitude pairs, compute the distance between those two points on Earth. Use kilometers instead of miles, because the US was supposed to convert to the metric system in 1975. Check your formula by computing the distance between New York City and San Diego, as reported by the Great Circle Mapper web site. In t 1: 2b. Construct a complete graph in which each vertex is labeled by the name of a state, and each edge is labeled by the distance between the capital cities. In 2c. Construct the minimal spanning tree corresponding to the optimal CoCalc Fiber network. In 2d. William decides to scale back his plans and connect only the Western states (meaning Montana, Wyoming, Colorado, New Mexico, and all continental states west of these). Furthermore, he is now only going to build links between states which are adjacent (meaning that they share a land border, not just a corner); and all city pairs will now be treated as costing the same amount. Construct the minimal spanning tree corresponding to the optimal network. Problem 2: Minimum spanning trees Grading criteria: correctness of code. Note: you will need to reference your answer to problem 1, but this problem will be graded independently .e., as if your answer to problem 1 is correct, whether it is or not). William Stein announces the formation of CoCalc Fiber, a new broadband network which will connect the capital cities of the 48 continental United States (excluding Alaska and Hawai) with a series of underground cables joining certain pairs of cities. Naturally, William wants to minimize the cost of building this network; he assumes that the cost of building a network link between some pairs of cities is proportional to the distance between those two cities. 2a. Define a function that implements the haversine formula: given two latitude-longitude pairs, compute the distance between those two points on Earth. Use kilometers instead of miles, because the US was supposed to convert to the metric system in 1975. Check your formula by computing the distance between New York City and San Diego, as reported by the Great Circle Mapper web site. In t 1: 2b. Construct a complete graph in which each vertex is labeled by the name of a state, and each edge is labeled by the distance between the capital cities. In 2c. Construct the minimal spanning tree corresponding to the optimal CoCalc Fiber network. In 2d. William decides to scale back his plans and connect only the Western states (meaning Montana, Wyoming, Colorado, New Mexico, and all continental states west of these). Furthermore, he is now only going to build links between states which are adjacent (meaning that they share a land border, not just a corner); and all city pairs will now be treated as costing the same amount. Construct the minimal spanning tree corresponding to the optimal network
