\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{CSE 101 Homework 1}
\date{Winter 2021}
\begin{document}
\maketitle
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 \LaTeX is recommend though not required.
\begin{ques}[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\times n$ grid of squares. Some of these squares are marked as \emph{walls} and are impassible. Some are marked as \emph{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 \emph{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$.
\end{ques}
\begin{ques}[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.
\begin{enumerate}[(a)]
\item Give a linear time algorithm to solve this problem. [30 points]
\item Does this algorithm work if some of the bridges are one-way instead of two way? If not, what goes wrong? [5 points]
\end{enumerate}
\end{ques}
\begin{ques}[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.
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}