CSE 101 Homework 1
Winter 2021
This homework is due on gradescope Friday January 15th at 11:59pm pacific time. Remember to justify
your work even if the problem does not explicitly say so. Writing your solutions in LATEXis recommend
though not required.
Question 1 (Clone Maze, 35 points). Steven’s body has been split into two clones and he needs to reach the
recombiner to fix it. Unfortunately, the clones still have only one mind between them and will always move
in the same direction as each other. What is worse is that the laboratory that the clones are in is filled with
traps!
The laboratory is given as an n× n grid of squares. Some of these squares are marked as walls and are
impassible. Some are marked as traps and will kill Steven if a clone enters one. Two squares are marked
as the two pads for the recombiner, and two squares are marked as the current locations of Steven’s clones.
When moving, Steven selects one of the four directions (up, down, left, right) and both clones move one
square in that direction if possible (a clone does not move if there is a wall of the edge of the laboratory
one square in that direction). If a clone moves into a trap square, Steven will die. Give an algorithm to
determine if it is possible for Steven to get both of his clones to both of the recombiner pads. For full credit
your algorithm should run in time polynomial in n.
Question 2 (Proportional Connectivity, 35 points). The nation of Graphania exists on a small chain of
islands. Recently, they have begun building (two-way) bridges connecting some of the islands. The government
of Graphania wants to measure the progress of this new bridge system and to do so, they want to measure the
probability that given two random Graphanian citizens, A and B that A will be able to reach B by travelling
along the newly built bridges.
You are given a list of Graphania’s islands along with the fraction of the population living on each island,
and which other islands each island has bridges to. Your goal is to compute the probability that a randomly
selected pair of citizens can reach each other using these bridges. You can assume that once on an island, a
citizen can reach anywhere else on that island.
(a) Give a linear time algorithm to solve this problem. [30 points]
(b) Does this algorithm work if some of the bridges are one-way instead of two way? If not, what goes wrong?
[5 points]
Question 3 (DFS Tree from Pre- and Post- Orders, 30 points). Given the pre- and post- order numbers of
each vertex of a graph G in a particular execution of DFS, give a polynomial time algorithm that computes
the DFS tree for that execution.
Question 4 (Extra credit, 1 point). Approximately how much time did you spend working on this homework?
1