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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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 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 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 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. Ex- press 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 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

 

• What bound do we get if we use the same strategy on groups of seven instead of groups of five?
• 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 .

 

• Give an O(n log n) algorithm for solving the
• Describe an O(n) algorithm that uses our ability to find the median key in O(n) time. Describe the steps of the Be precise in your description of the steps, which can include recursive calls and must address the base case.
• Give a recurrence for your algorithm and derive the O(n) bound for
• Write pseudocode for the algorithm, similar to pseudocode you have seen in our You may make calls to algorithms that are already defined in the text.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of