CS180 Homework 3

CS180 Homework 3

1. (10 pt) Give an example where Dijkstra’s algorithm fails when there are edges of negative weight even if
there are no negative cycle. (A negative cycle means a cycle v1
, . . . , vr where v1 = vr and the total weights
Pr−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
0
, 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 problem is to find the lowest weight tour of the graph, where a tour is a path v1
, v2
, . . . , vr
such that v1 = 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 Pr−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).
4. (20 pt) Derive the order of T(n) for the following recurrence:
T(n) = 2T(
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.
5. (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 can’t 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.