# 代写homework | 代做Algorithm | R | 统计代写- CS180 Homework 3

### CS180 Homework 3 1. (10 pt) Give an example where Dijkstras Algorithm fails when there are edges of negative weight even if there are no negative cycle. (A negative cycle means a cycle v 1 ,… , vr where v 1 = vr and the total weights r 1 i = 1 `vi , vi + 1 is negative).
2. (25 pt) Given an undirected weighted graph G with n nodes and m edges, and we have used Prim algorithm to construct a minimum spanning tree T. Suppose the weight of one of the tree edge (( u , v ) T ) is changed from w to w , design an algorithm to verify whether T is still a minimum spanning tree. Your algorithm should run in O ( m )time, and explain why your algorithm is correct. You can assume all the weights are distinct.
3. (20 pt) Given an undirected graph with nonegative edge weights, the goal of the traveling saleseman prob- lem is to find the lowest weight tour of the graph, where a tour is a path v 1 , v 2 ,… , vr such that v 1 = vr and every node in the graph is visited at least once. Note that edges or nodes can appear more than once in the tour. The cost of the tour is the sum of the edge weights in this path, defined as
``````  R  1
i = 1 `vi , vi + 1. We aim to
develop an approximation algorithm for solving this problem via MST.
``````
• Prove the weight of the optimal tour is at least the weight of the MST
• Describe an algorithm to find a tour that visits every node with the cost at most twice the cost of the MST (so this will be a two-approximation algorithm for traveling salesman problem).
1. (20 pt) Derive the order of T ( n )for the following recurrence:
``````T ( n )= 2 T (
``````
``````n
2
``````
``````)+ n log n
``````
``````This one cannot be derived from the Master Theorem, so you will need to compute the sum of costs at each
level directly, like what we did in the class.
``````
1. (25 pt) An array with n objects, has a majority element if more than half of its entries are the same. Given an array, design an algorithm to tell whether there is a majority element, and if so, find that element. Your algorithm should run in O ( n log n )time. Note that the elements of the array may not be ordered numbers so you cant make any query in the form of A [ i ] >A [ j ]. However, you can answer questions of the form A [ i ]= A [ j ] in constant time.

homework assignments are due on the exact time indicated. Please submit your homework using the Gradescope system. Email attachments or other electronic delivery methods are not acceptable. To learn how to use Gradescope, you can:

1. Watch the one-minute video with complete instructions from here: