程序代写代做代考 graph C algorithm go 1

1
1.
CSCI 570 – Fall 2020 HW 4 Solution
Graded Problems
Suppose you were to drive from USC to Santa Monica along I-10. Your gas tank, when full, holds enough gas to go p miles, and you have a map that contains the information on the distances between gas stations along the route. Let d1 < d2 < ... < dn be the locations of all the gas stations along the route where di is the distance from USC to the gas station. We assume that the distance between neighboring gas stations is at most p miles. Your goal is to make as few gas stops as possible along the way. Give the most efficient algorithm to determine at which gas stations you should stop and prove that your strategy yields an optimal solution. Give the time complexity of your algorithm as a function of n. Solution: The greedy strategy we adopt is to go as far as possible before stopping for gas. That is when you are at the ith gas station, if you have enough gas to go the i + 1th gas station, then skip the ith gas station. Otherwise stop at the ith station and fill up the tank. Let {g1,g2,...,gm} be the set of gas stations at which our algorithm made us refuel. We next prove that our choice is optimal. Let {h1, h2, . . . , hk} be an optimal solution. Since it is not possible to get to the g1 + 1th gas station without stop- ping, any solution should stop at either g1 or a gas station before g1, thus h1 ≤ g1. If h1 < g1, then we can swap its first stop with g1 without chang- ing the number of stops. The new solution we obtain {g1,h2,...,hk} is legal since when leaving g1 we have at least as much fuel now as we had before swapping. Hence {g1, h2, . . . , hk} is an optimal solution. Assume that {g1, g2, . . . , gc−1, hc, . . . , hk} is an optimal solution (induction hypothesis). From the greedy strategy taken by our algorithm, hc ≤ gc. If hc kc−1 ≥ ic−1, the cth step of the algorithm ran successfully and found sic such that sic = skc . Further since ic is the smallest index greater than ic−1 such that sic = ric , it is true that kc ≥ ic and the claim follows.
The running time of the algorithm is O(n+m) as we examine each element in the sequences at most once.
2. Solve Kleinberg and Tardos, Chapter 4, Exercise 22.
4

Solution: Consider the following counterexample. Let G = (V,E) be a weighted graph with vertex set V = {v1, v2, v3, v4} and edges (v1, v2), (v2, v3), (v3, v4), (v4, v1) of cost 2 each and an edge (v1, v3) of cost 1. Then every edge belongs to some minimum spanning tree, but a spanning tree consisting of three edges of cost 2 would not be minimum.
5