Molly is planning a roadtrip to visit her grandfather. The road system she is travelling on...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Molly is planning a roadtrip to visit her grandfather. The road system she is travelling on is given by a directed graph G with her initial location at a vertex s and final destination a vertex t. Each edge e of G has associated to it a positive integer r(e), which is the number of days that it will take Molly to travel along this edge. Molly wants to do some sightseeing on this trip and so also associates another value V(e) to each edge proportional to the value to her of traversing this edge. (a) Suppose that Molly needs to arrive at her grandfather's after exactly k days. Provide an algorithm to determine the greatest total value of any path with this traversal time. For full credit, your algorithm should run in time O(k(|V|+|E|)) or better. [20 points0 (b) Suppose instead that Molly is allowed to spend as much time as she wants travelling, but instead wants to optimize the average value per day of travel. For any real number x, give an algorithm to determine whether or not there is a path that allows Molly to reach her grandfather with an average value per day of travel of at least x. For full credit, your algorithm should run in time O(|V||E|). [20 points] (c) As in part (b), assume that Molly is trying to optimize her average value. Suppose that all edge values are between 0 and 1. Give an algorithm that given an > 0 approximates the best average value Molly can achieve to within error at most e in time O(|V||E| log(2/e)). [10 points] [Note: For all of these algorithms we will need to make the slightly unrealistic assumption that Molly is allowed to traverse the same edge multiple times, getting the same value from it each time.] Molly is planning a roadtrip to visit her grandfather. The road system she is travelling on is given by a directed graph G with her initial location at a vertex s and final destination a vertex t. Each edge e of G has associated to it a positive integer r(e), which is the number of days that it will take Molly to travel along this edge. Molly wants to do some sightseeing on this trip and so also associates another value V(e) to each edge proportional to the value to her of traversing this edge. (a) Suppose that Molly needs to arrive at her grandfather's after exactly k days. Provide an algorithm to determine the greatest total value of any path with this traversal time. For full credit, your algorithm should run in time O(k(|V|+|E|)) or better. [20 points0 (b) Suppose instead that Molly is allowed to spend as much time as she wants travelling, but instead wants to optimize the average value per day of travel. For any real number x, give an algorithm to determine whether or not there is a path that allows Molly to reach her grandfather with an average value per day of travel of at least x. For full credit, your algorithm should run in time O(|V||E|). [20 points] (c) As in part (b), assume that Molly is trying to optimize her average value. Suppose that all edge values are between 0 and 1. Give an algorithm that given an > 0 approximates the best average value Molly can achieve to within error at most e in time O(|V||E| log(2/e)). [10 points] [Note: For all of these algorithms we will need to make the slightly unrealistic assumption that Molly is allowed to traverse the same edge multiple times, getting the same value from it each time.]
Expert Answer:
Answer rating: 100% (QA)
a To find the greatest total value of any path that allows Molly to reach her grandfather in exactly ... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
Please solve all the letters, and please show all work indetail. If you use excel please show other excel box showing whatyou inputted in the excel boxes.. Thanks!!! 5. Growth opportunities. The firm...
-
Assume that you qualify for a $25,000 loan from the Canada Student Loans Program to help finance your education. You are considering whether to repay this loan on graduation with a fixed interest...
-
Daniel receives 400 shares of A&M Corporation stock from his aunt on May 20, 2017, as a gift when the stock has a $60,000 FMV. His aunt purchased the stock in 2007 for $42,000. The taxable gift is...
-
True or False: If \(E R R>M A R R\), then \(I R R>E R R>M A R R\).
-
MicroProducts, Incorporated (MPI) manufactures printed circuit boards for a major PC manufacturer. Before a board is sent to the customer, three key components must be tested. These components can be...
-
Airport Passenger Processing: As an IT Manager you were tasked to improve the performance of the local Airport Passenger Processing system . This is to make the Airport more efficient and more...
-
How would the Highest interest rate to the Lowest credit card payment method apply a $1200 payment to a card with an outstanding balance of $2000 broken down as follows: Transaction Rate Balance...
-
How can Human Capital be enhanced?
-
The CEO of Hillton is considering splitting the firm into two separate firms, "Nicole Corp" and "Paris Corp", in a spin-off. After reading the debt covenants carefully, the CEO has discovered that...
-
What will be printed out as a result of the following code? int x = 4, y = 5; System.out.println(++x); x + = y++; System.out.println(x +","+y);
-
Tesla exports cars to many countries, including China. The company expects to receive 16 million yuan () in one year from its exports. The firm expects the following exchange rate scenarios and...
-
Design an ER diagram for a Hotel Reservation System described below: Very important notes: 1- Make sure to suggest the necessary attributes for each entity and relationship if any. 2- Make sure to...
-
HillCom Corp stock was $75.00 per share at the end of last year. Since then, it paid a $2.50 per share dividend last year. The stock price is currently $78.00. If you owned 100 shares of HillCom,...
-
(5 points) Let S be the cube with side length 2, faces parallel to the coordinate planes, and centered at the origin, with outward orientation. (a) Calculate the total flux of the constant vector...
-
A survey of 70 college freshmen asked whether students planned to take biology, chemistry, or physics during their first year. Use the diagram to answer each question. How many of the surveyed...
-
Find a real general solution. Show the details of your work. (x 2 D 2 - 0.2xD + 0.36I)y = 0
-
What form does a 3 X 3 matrix have if it is symmetric as well as skew-symmetric?
-
Orthogonality is particularly important, mainly because of orthogonal coordinates, such as Cartesian coordinates, whose natural basis consists of three orthogonal unit vectors. When will the...
-
Cumulative Normal distribution \(\Phi_{(\mu, \sigma)}\) and probability (a) \(X \sim \phi_{(0,1)}\); what is \(P(X \leq 1.43)\) ? (b) \(X \sim \phi_{(0,1)}\); what is \(P(X>1.43)\) ? (c) \(X \sim...
-
Inverse cumulative Normal distribution \(z\) (a) Find \(z_{0.05}\). (b) Find \(z_{0.95}\). (c) Let \(X \sim \phi_{(2,1)}\). Find \(a\) such that \(P(X \leq a)=0.05\). (d) Let \(X \sim \phi_{(2,1)}\)....
-
The Normal approximation (a) A discrete stochastic variable \(X\) has expected value \(\mu_{X}=3\) and \(\sigma_{X}=1.2\). Use the Normal approximation to find \(P(X \leq 4)\). (b) A continuous...
Study smarter with the SolutionInn App