首页 >
> 详细

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.

(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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Comp 250 Assignment 3 2020-05-24
- Macm 316 – Computing Assignment 7 2020-05-24
- Sta457 Assignment 2020-05-24
- Homework 10 2020-05-24
- Lab 2 Msc: Time Series Prediction With... 2020-05-24
- Comp2011作业代做、Data Analysis作业代写、C++编程语言 2020-05-24
- 代做compsys201作业、Python，Java，C/C++编程语言作业 2020-05-24
- Program留学生作业代做、Python编程设计作业调试、Data作业代写 2020-05-24
- 代写 Practical 3 Covid-19程序作业，代写... 2020-05-23
- 代写comp3059作业、代做programming作业、Java语言作业代 2020-05-23
- Coit12206作业代写、Program课程作业代做、Java、Pytho 2020-05-23
- Data2001作业代做、Data Science作业代做、Sql语言作业代 2020-05-23
- 代写comp2017作业、代写c/C++语言作业、代写data作业、C/C+ 2020-05-23
- Data留学生作业代做、Python编程设计作业调试、代写program课程 2020-05-22
- Mkan1-Uc 5103作业代写、代做analytics作业、Java，P 2020-05-22
- Pols 512作业代写、R编程设计作业调试、Data留学生作业代做、代写r 2020-05-21
- Econ 6070作业代做、Data课程作业代写、代做java，Python 2020-05-21
- Pstat 170 2020-05-20
- Comp 250 Assignment 3 2020-05-20
- Data留学生作业代做、代写r程序语言作业、代做r实验作业、代写progra 2020-05-20