Drew is a ballpark chaser, meaning his goal is to attend games at all 30 Major...

Transcribed Image Text:

Drew is a ballpark chaser, meaning his goal is to attend games at all 30 Major League Baseball stadiums (this is true). However, after the labor disputes during the 2020 pandemic, he has become disgusted and swears off attending any more games (this is dramatic and not true, but makes for good motivation to this problem!). Now he needs a new hobby and decides to drive from Portland, Maine to Portland, Oregon. He would like to make the drive as interesting as possible, but can't stand the thought of driving through more than k cities with professional baseball teams. You are given a simple, directed graph G = (V,E) with weights on edges w: E → R, which represents a map of the United States; cities are nodes, edges are roads between two cities, and the weight of an edge is how boring driving on this road is (looking at you I-71 in Ohio). A subset B of the vertices in V are marked as having a professional baseball team, aka "ballclub nodes". We will denote the node representing Portland, ME as s (the start) and the node representing Portland, OR as t (the terminus). (a) [15 points] Describe and provide pseudocode for an algorithm that takes as input G, w, BC V, s, t, and a positive integer k, and returns a path from s to t that contains at most k ballclub nodes and has smallest weight (i.e. is most interesting/least boring) among all such paths, if such a path exists, and outputs "No Solution" otherwise. You may assume that there are no negative cycles and that s and t are not in B, as neither Portland has an MLB team. In your submission, you need not prove the correctness of your algorithm; but please note that you need to be able to prove it if asked. (b) [5 points] State and justify the asymptotic running time of your algorithm. Drew is a ballpark chaser, meaning his goal is to attend games at all 30 Major League Baseball stadiums (this is true). However, after the labor disputes during the 2020 pandemic, he has become disgusted and swears off attending any more games (this is dramatic and not true, but makes for good motivation to this problem!). Now he needs a new hobby and decides to drive from Portland, Maine to Portland, Oregon. He would like to make the drive as interesting as possible, but can't stand the thought of driving through more than k cities with professional baseball teams. You are given a simple, directed graph G = (V,E) with weights on edges w: E → R, which represents a map of the United States; cities are nodes, edges are roads between two cities, and the weight of an edge is how boring driving on this road is (looking at you I-71 in Ohio). A subset B of the vertices in V are marked as having a professional baseball team, aka "ballclub nodes". We will denote the node representing Portland, ME as s (the start) and the node representing Portland, OR as t (the terminus). (a) [15 points] Describe and provide pseudocode for an algorithm that takes as input G, w, BC V, s, t, and a positive integer k, and returns a path from s to t that contains at most k ballclub nodes and has smallest weight (i.e. is most interesting/least boring) among all such paths, if such a path exists, and outputs "No Solution" otherwise. You may assume that there are no negative cycles and that s and t are not in B, as neither Portland has an MLB team. In your submission, you need not prove the correctness of your algorithm; but please note that you need to be able to prove it if asked. (b) [5 points] State and justify the asymptotic running time of your algorithm.

Answer rating: 100% (QA)

a Algorithm for Finding Path with Fewest Ballclub Nodes and Sma... View the full answer