Question 4 [12 Marks]
A relative of yours is a curator at a botanical garden. She would like to launch an olfactory outdoor
exhibition in which visitors walk through a path where n fragrant plants are carefully lined up so that
the transition and progression of scents along the path are an enjoyable experience. The problem is
that the aroma of some plants should not come after that of some other plants, or the quality of the
olfactory orchestration is compromised. After manually trying many arrangements, a garden worker
exclaimed that the task is so wicked that only a computer scientist can find an optimal arrangement!
Remembering that you took computer science courses in university, your relative immediately calls
to ask if you can help with finding an arrangement. You proudly respond that while your education
has nothing to do with fragrant plants, CSC263 has equipped you with some tools that could help.
Rejoiced, your relative sends you a list of the n plants that she wants to use, as well as a list of m tuples
where any given tuple (a, b) indicates that plant a should not come after plant b in the arrangement.
She notes that not all of the n plants necessarily appear in the tuples list, and only plants that have
issues with others appear as tuples (so do not assume anything about the value of m relative to n).
Now you can get to work:
(a) Similar to Question 1, model the provided input (the two lists) as a graph that you can use to
answer the subsequent parts. You do not need more than one graph.
(b) To the dismay of your relative, you find when testing out different inputs (beyond what she
provided you) and their equivalent graphs that there are scenarios when no scent-compatible
arrangement is possible. Characterize the graphs in which no arrangement is possible.
(c) Now describe in plain English an efficient algorithm that returns True if a compatible arrangement
exists among the n plants, and False otherwise. The algorithm should only check and not actually
produce an arrangement. The algorithm takes as input the graph you designed in part (a)
represented as an adjacency list.
(d) What is the worst-case run time of your algorithm from part(c)? Express your answer in terms
of n and m and justify it.
(e) If your algorithm from part (c) indicates that an arrangement is possible, how do you compute
an actual arrangement? Explain your algorithm in plain English and provide all necessary
implementation details.
(f) What is the worst-case run time of your algorithm from part (e)? Express your answer in terms
of n and m and justify it.
1