CS Homework 3 Solution

    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 ‘v ,v   is negative).
i    1    i    i+1

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) 2 T ) is changed from w to w0, 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 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
P
r  1
. We aim to


i=1 ‘vi ,vi+1

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 ( 2n ) + 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.