# 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

snobâyou only drink independently roasted, hand-pulled, direct-trade, organic, shade-grown,

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,

direct-trade, organic, shade-grown single-origin espresso, and whose edges represent highway

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:

## Get Help With a similar task to - Algorithm Question in relation to Graphs

## Related Questions

Tutlance Experts offer help in a wide range of topics. Here are some of our top services:

- Math homework help
- Nursing homework help
- Statistics homework help
- Nursing coursework help
- Capstone project writing services
- Essay writers for hire
- Case study writing help
- Buy college papers online
- Buy college research papers
- College homework help
- Professional resume writing services
- Programming homework help
- Coursework writing help
- Term paper writing help
- Biology homework help
- Do my physics homework
- Dissertation data analysis help
- PhD Dissertation writing services
- Chemistry homework help

Post your project now for free and watch professional experts outbid each other in just a few minutes.