Problem 1. [30 points] Three Lotus Tiles
Three Lotus Tiles is a solitaire game, played on a connected undirected graph G = (V, E). Initially,
three tiles are placed on distinct start vertices a, b, c. In each turn, the player must move all three
tiles, by moving each tile along an edge from its current vertex to an adjacent vertex. At the end of
each turn, the three tiles must lie on three different vertices.
Your goal is to move the tiles onto three goal vertices «, y, 2; it does not matter which tile ends up
on which vertex. Your solution may run in O(V|3 + (El3).
Problem 2. [30 points] The Adventures of Avatar Aang
Avatar Ang is trying to get to the North Pole to learn waterbending, but the fire nation has blocked
off specific routes on his way. Now, the only routes his trusty flying bison, Appa, can take are
between m specific pairs of islands (known as island hops). As a result, in order for Ang to reach
the North Pole, he must travel via a series of island hops. Each island hop is denoted by the pair
(i1, i2) of islands it connects, and he can hop in either direction.
(a) [15 points]
Appa the flying bison has only so much strength to carry Ang to his destination
(known as energy units). Each island hop (vi, ¿;) requires a given positive integer
amount of energy units denoted by hij. Describe an O(km) worst-case algorithm to
determine whether there exists a sequence of island hops that Ang can take from the
South Pole to the North Pole that costs a total of less than k energy units. Assume that
(b) [15 points] Before leaving the South Pole, Aang discovers lili, a magical plant that
allows Appa to make an island hop using only one energy unit (called an ultra-hop).
However, after making one ultra hop, Appa cannot consume lili again until he makes
a normal island hop. Describe an O(km) worst-case algorithm to determine whether
there exists a sequence of island hops (both normal and ultra-hops) that Aang can take
to reach the North Pole using less than k energy units.
Problem 3. [40 points] Node Way Home
We have a directed graph G
= E, V. We’ll define a meeting point as any node that is reachable
from all other nodes in the graph. In the graph below there are two meeting points: O and 1.
(a) [5 points] Say we reverse the edges to get graph G’. If node a was a meeting point in
graph G, which of the following must be true. Please provide brief justification with
a counterexample or a couple sentences (pictures of graphs are fine for examples).
1. a is still a meeting point in G’
2. a can reach every other node in G’
3. G’ is strongly connected
4. G’ is connected
5. There must exist at least one meeting point in G
(b) [7 points] We’ll define an origin node as any node that can reach every other node in
the graph. Prove that if at least one origin node exists in graph G, then the final node
in the finishing order of Full DFS on G must be an origin node.
(c) [8 points] Describe a linear time algorithm that can take in a graph G and either return
a meeting point or None if no meeting points exist. You should justify your runtime,
but do not have to prove correctness. You may use other parts of this problem in your
write-up, but you are not required to. Multiple solutions exist. You may assume that
VI> 1 and that the graph is simple.
(d) [20 points] Implement the algorithm for find_meeting_point, and submit your