computer science 3110

1. Suppose your class is on a field trip to an island with n towns on it, connected by m townto-town buses (which run in both directions), run by c companies. Each company’s buses
are a different colour, and there can be buses from two or more companies running between
two towns. You have a map showing which companies run buses between which towns. The
drivers have a relaxed attitude to schedules and the buses run often, so there’s no telling
which buses will be arriving and leaving next.
Your classmate Ryan has wandered off and got lost and you’re (somewhat reluctantly) trying
to find him. You’d told him which buses the class was supposed to take during the day, and
given him tickets from the appropriate companies, the same colours as the buses and stapled
together in the right order. Ryan didn’t remember which towns the class was going to visit,
however, so he always took the first bus he saw of the colour of the next ticket, tearing off
that ticket and giving it to the driver.
Design a polynomial-time dynamic-programming algorithm that, given the map of the bus
routes, Ryan’s starting point and the colours of the buses he took, calculates the probability
Ryan is in each of the n towns.
For example, if the map is as shown below and Ryan started in town A and took a red bus,
a green bus, a blue bus and another green bus, then he could have gone
A-B-C-D-B,
A-B-D-A-C,
A-B-D-C-A,
A-B-D-C-B,
A-C-A-B-C,
A-C-A-B-D,
A-C-A-D-B,
A-C-B-A-C .
The probability Ryan went first from A to B is 0.5, and the probability he went first from A
to C is 0.5. Therefore, after one trip, the probability he was in B is 0.5 and the probability
he was in C is 0.5.
The probability Ryan’s second trip took him from B to C is 0.5 times the probability he was
in B, or 0.25. The probability it took him from B to D is also 0.5 times the probability he
was in B, or 0.25. The probability it took him from C to A is 0.5 times the probability he
was in C, or 0.25. The probability it took him from C to B is 0.5 times the probability he
1was in C, or 0.25. Therefore, after two trips, the probability is 0.25 he was in any particular
town.
The probability Ryan’s third trip took him from A to B is 0.5 times the probability he was
in A, or 0.125. The probability it took him from A to D is 0.5 times the probability he was
in A, or 0.125. The probability it took him from B to A is the probability he was in A, or
0.25. The probability it took him from C to D is the probability he was in C, or 0.25. The
probability it took him from D to A is 0.5 times the probability he was in D, or 0.125. The
probability it took him from D to C is 0.5 times the probability he was in D, or 0.125.
Therefore, after three trips, the probabilities Ryan was in A, B, C, D are, respectively, 0.25 +
0.125 = 0.375 (the probability his third trip took him from B to A plus the probability it
took him from D to A), 0.125, 0.125 and 0.125 + 0.25 = 0.375 (the probability his third trip
took him from A to D plus the probability it took him from C to D).
You can compute the probability of Ryan being in a particular town after four trips and five
trips similarly.
Isn’t it lucky you’re on an island, so you can’t accidentally lose Ryan forever