# Algorithm Question in relation to Graphs

Dhruv needs help with Computer Science as soon as possible. Dhruv wrote:

Topic: Computer Science | No Language / I don't know

Hi,

Would you be able to help me with the following:

You are hired as a cyclist for the Giggle Highway View project, which will provide street-level

images along the entire US national highway system. As a pilot project, you are asked to ride

the Giggle Highway-View Fixed-Gear Carbon-Fiber Bicycle from the Giggleplex in Mountain

View to Gigglesburgh in Cambridge.

You are a hopeless caffeine addict, but like most Giggle employees you are also a coffee

single-origin espresso. After each espresso shot, you can bike up to H miles before suffering a

caffeine-withdrawal migraine.

Giggle helpfully provides you with a map of the United States, in the form of an undirected

graph G, whose vertices represent coffee shops that sell independently roasted, hand-pulled,

connections between them. Each edge e is labeled with the length `(e) of the corresponding

stretch of highway. Naturally, there are acceptable espresso stands at both Giggle offices,

represented by two specific vertices s and t in the graph G.

(a) Describe and analyze an algorithm to determine whether it is possible to bike from the

Giggleplex to Gigglesburgh without suffering a caffeine-withdrawal migraine.

(i) Describe precisely what your algorithm is given as input and what it needs to output.2

Solution:

(ii) Describe your algorithm in pseudocode.

Solution:

(iii) Justify correctness of your algorithm. Your justification does not need to be long or

formal, just convincing.

Solution:

(iv) Analyze the running time of your algorithm.

Solution:

You discover that by using a drag-reducing moustache wax, you can increase the distance H that you can bike between espresso shots. Describe and analyze an algorithm to find the minimum value of H that allows you to bike from the Giggleplex to Gigglesburgh without suffering a caffeine-withdrawal migraine.3

(i) Describe precisely what your algorithm is given as input and what it needs to output.2

(ii) Describe your algorithm in pseudocode. 1The cultural tropes used in this problem might date me slightly. 2Hint: Make sure you have this right before you move on to designing the algorithm. 3Hint: Use dynamic programming! Think about how to modify the Bellman-Ford Algorithm. 2

(iii) Justify correctness of your algorithm. Your justification does not need to be long or formal, just convincing.

(iv) Analyze the running time of your algorithm.

When you report to your supervisor that the ride is impossible given the existing layout of coffee shops, she responds âWell canât you get your caffeine fix at Starbucks?â and hands you an updated graph G0 that includes an additional vertex for every Starbucks location in the US. Describe and analyze an algorithm to find the minimum number of Starbucks locations you have to visit to bike from the Giggleplex to Gigglesburgh without suffering a caffeine-withdrawal headache.3

(i) Describe precisely what your algorithm is given as input and what it needs to output.2 Solution:

(ii) Describe your algorithm in pseudocode. Solution:

(iii) Justify correctness of your algorithm. Your justification does not need to be long or formal, just convincing. Solution:

(iv) Analyze the running time of your algorithm. Solution:

## Related Questions

Similar orders to Algorithm Question in relation to Graphs
21
Views
0
Nested imbalanced design of expriment using Box-Adjusted wald-type test
I need to provide statistical analysis of a nested non-balanced design of an experiment. I am would like to have the implementation R. I will need the answers to be provided as shown in the attached file (Project.pdf), and also would like to have access to...
34
Views
0
CMPT 200 Coding Homework
Write a class called Fraction that can store a rational number (reminder: those numbers that can be expressed in the form a/b, where a and b are integers are rational numbers). For example, a variable with a value of Â½ would be created using oneHalf ...
15
Views
0