CS420留学生代做、algorithm代写、Python，Java，c++程序语言代做

日期：2020-04-03 11:07

Homework 4, CS420, Spring 2020

Submit as a PDF scan. Make sure your name and I.D. number appear at

the top of it. Arrange your solutions so that they appear in order in the

PDF file. Check what you have submitted to make sure it is all legible

and nothing is missing.

1. Suppose Johnson’s algorithm doesn’t change the weight of any edge by more than

plus or minus r. Give a tight exact bound on how much it can change the total

weight of a cycle that has k vertices in it. I am looking for an exact bound, not an

asymptotic (big-Θ) bound. Explain your answer by showing algebraically how much

the reweighting label w of a vertex on the cycle can contributed to the reweighted

weight of the cycle.

2. Suppose you add a constant to all the reweighting labels at the vertices. What does

this do to the reweighted values. Justify your answer with algebra.

3. Suppose Johnson’s algorithm operates on a class of graphs that have no negative

cycle but that do have a zero-weight directed cycle that contains all the vertices. The

application in which these graphs arise make it obvious which are the edges of the

cycle; assume the edges of this cycle are given.

Give an algorithm to perform the reweighting that is faster than Bellman-Ford. Express

your bound as a function of n and/or m. Do not count the cost of performing

the n calls to Dijkstra’s algorithm once you have reweighted it.

You can express the steps of your algorithm in English, but you must do it in a way

that leaves no question about what the step does. Explain why it works.

To be safe, you may want to supplement your English description with pseudocode

to resolve any ambiguity that you could lose points for.

4. There is a long, straight beach several miles long with n houses along it. You want to

open up a bar-and-grill on the beach. Give an O(n) algorithm for finding a location

that minimizes the sum of distances to the n houses. The distances of all the houses

from the first house in the sequence are known precisely.

5. When we got an O(n) algorithm for selection, we divided the elements into groups of

five.

(a) What bound do we get if we use the same strategy on groups of seven instead of

groups of five?

(b) What about groups of three?

6. Suppose an array contains a set of ordered pairs (k, w), where k is the key of the pair

and w, a positive number, is the weight. The weighted rank of a key k is the total sum

of weights of pairs whose key is less than or equal to k.

Problem: Given a weight W between 0 and the sum of weights of all pairs in the

array, find the smallest key k whose weighted rank is greater than or equal to W.

(a) Give an O(n log n) algorithm for solving the problem.

1

(b) Describe an O(n) algorithm that uses our ability to find the median key in O(n)

time. Describe the steps of the algorithm. Be precise in your description of the

steps, which can include recursive calls and must address the base case.

(c) Give a recurrence for your algorithm and derive the O(n) bound for it.

(d) Write pseudocode for the algorithm, similar to pseudocode you have seen in our

readings. You may make calls to algorithms that are already defined in the text.

2