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.