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.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme