Graphs and paths - Data Structures and Problem Solving Using Java - page 568

d. Write a program that checks whether a graph is strongly con-

nected. What is the running time of your algorithm?

Explain how each of the following problems can be solved by applying a
shortest-path algorithm. Then design a mechanism for representing an input
and write a program that solves the problem .

The input is a list of league game scores (and there are no ties). If all
teams have at least one win and a loss, we can generally “prove,” by a
silly transitivity argument, that any team is better than any other. For
instance, in the six-team league where everyone plays three games,
suppose that we have the following results: A beat B and C ; B beat C
and F ; C beat D ; D beat E ; E beat A ; and F beat D and E . Then we can
prove that A is better than F because A beat B who in turn beat F . Sim-
ilarly, we can prove that F is better than A because F beat E and E
beat A . Given a list of game scores and two teams X and Y , either find
a proof (if one exists) that X is better than Y or indicate that no proof
of this form can be found.

14.21

A word can be changed to another word by a one-character substitu-
tion. Assume that a dictionary of five-letter words exists. Give an
algorithm to determine whether a word A can be transformed to a
word B by a series of one-character substitutions, and if so, outputs
the corresponding sequence of words. For example, bleed converts to
blood by the sequence bleed , blend , blond , blood .

14.22

Modify Exercise 14.22 to allow words of arbitrary length and to allow
transformations in which we add or delete one character. The cost of
adding or deleting a character equals the length of the longer string in
the transformation while a single-character substitution only costs 1.
Thus ark , ask , as , was is a valid transformation from ark to was and the
cost is 7 (1+3+3).

14.23

The input is a collection of currencies and their exchange rates. Is
there a sequence of exchanges that makes money instantly? For
instance, if the currencies are X , Y , and Z and the exchange rate is 1 X
equals 2 Y s, 1 Y equals 2 Z s , and 1 X equals 3 Z s, then 300 Z s will buy
100 X s, which in turn will buy 200 Y s, which in turn will buy 400 Z s.
We have thus made a profit of 33 percent.

14.24

A student needs to take a certain number of courses to graduate, and these
courses have prerequisites that must be followed. Assume that all courses
are offered every semester and that the student can take an unlimited

14.25