Question 1 (Shortest Paths, 30 points). Find the lengths of the shortest path from s to each other vertex
in the graph below:
1
Question 2 (Crossing Close Pair, 35 points). Give an algorithm that given two sets A and B each consist-
ing of n real numbers finds the minimum distance between a point of A and a point of B. In particular,
it computes the minimum possible value of |a − b| over all pairs a ∈ A and b ∈ B. For full credit, your
algorithm should run in time O(n log(n)).
For example, if A = {0, 1, 8} and B = {11, 3, 5}, then the closest pair would be 1 and 3 with distance 2.
2
Question 3 (Concert Tour, 35 points). Sadie and her band are looking for gigs. There are k different
venues willing to offer to let them play. Each venue has a schedule of performance openings for them, and
each opening takes place at a specific time and will pay Sadie’s band a specific amount of money. However,
travelling between venues takes time and Sadie’s band will not be able to play two different performances
unless there is enough time to get from one venue to the other (they can play multiple performances at the
same venue without any gap between them).
Give an algorithm that given the schedule of n possible performances (along with times, payments and
which venue it takes place in) along with the transit times between each pair of venues, computes the most
amount of money that Sadie’s band can make by performing. For full credit, your algorithm should run in
time O(kn log(n)).
For example, if venue A has performances at 9am (paying $100), 10am (paying $200) and 12pm (paying
$100) and venue B has performances at 11am (paying $200), and 4pm (paying $300) and the two venues are
5 hours apart from each other, Sadie could play at 9am and 10am at venue A and at 4pm at venue B for a
total of $600.
3