CS180 Homework 3
代写homework | 代做Algorithm | R代做 | 统计代写 – 这道题目是统计代写任务, 是比较有代表性的R语言等代写方向, 这个项目是homework代写的代写题目
- (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).
- (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.
- (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).
- (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.
- (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:
https://www.youtube.com/watch?v=-wemznvGPfg
– 2. Follow the instructions to generate a PDF scan of the assignments:
http://gradescope-static-assets.s3-us-west-2.amazonaws.com/help/submitting_
hw_guide.pdf
– 3. Make sure you start each problem on a new page.
We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is not a requirement but it helps us to grade the homework and give feedback. For grading, we will take into account both the correctness and the clarity. Your answer are supposed to be in a simple and understandable manner. Sloppy answers are expected to receiver fewer points.
Unless specified, you should justify your algorithm with proof of correctness and time complexity.