Question 1 [12 marks]
One of the changes the Covid-19 pandemic brought about was the introduction of one-way aisle rules in
stores. Welmart, a supermarket chain with over 400 stores in Canada, has received a lot of complaints
since the introduction of this rule from customers who found themselves unable to go from some store
sections to others as no paths existed between them. Welmart investigated the complaints and deemed
it a quality control issue: stores differ greatly in their size and layout and each store manager manually
designates the one-way paths for their stores. The complex nature of path designation has inevitably
left certain sections in some stores unreachable from others. The supermarket giant has therefore hired
you to design an efficient algorithm that takes the path layouts of all stores, and for each, return True
if it has a problem and False otherwise. Store managers have provided you with the section and path
layouts – an example is shown below for the Eden Hills (left) and Hyde Park (right) stores. Directed
arrows indicate one-way paths between sections. The dual paths (between Dairy and Fresh Produce
for example in Eden Hills) indicate in reality a wide aisle that was split in half. But they are shown
as two separate paths and you should treat them as such in your solution.
(a) Phrase the task you were hired to do as a graph problem using terminologies we learned in class.
(b) Represent each of the two store layouts as an adjacency list. Order sections and paths
alphabetically.
(c) If each store has n sections and e paths,1 describe an algorithm for performing the task from part
(a) in O(n + e) worst-case time. This asymptotic bound is for performing the check on a single
store – not all of them. Include as many implementation details as possible. You can assume that
the layout information (as shown in the figure above) has already been converted to adjacency
lists. The total number of stores your algorithm will be run on is variable, e.g. m, rather than a
constant, e.g. 400. You do not need this info (since you are conducting the runtime analysis at a
store level), but some of you will surely ask about the number of stores. For legibility, it would
be a good idea to use a numeric list to indicate the algorithm steps.
(d) Apply the algorithm you described in part (c) to determine if the Eden Hills and Hyde Park
stores have a path problem or not. Draw any additional or intermediate representations/graphs
that you use. Explain your work.
(e) Justify the worst-case runtime of your algorithm.
1the actual value of n and e could differ across stores but you do not need to worry about that
1