%Do not change
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}}
\newif\iftemplate
%\templatefalse
\templatetrue
\begin{document}
% Do not modify
%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\begin{textblock*}{30cm}(-1.7cm,-2.3cm)
\noindent {\large CS 381-Fall 2019} \\
\iftemplate
\noindent {\large Name: } \\
\noindent {\large Purdue ID: } \\
\noindent {\large Date: \today}
\fi
\end{textblock*}
\vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 5} \\
\textbf{Due Date: October 26, 2019 at 11:59PM on Gradescope.} \\
\textbf{Instructor: Jeremiah Blocki}\\
\end{center}
\subsection*{Homework Guideline Reminders}
\begin{itemize}
\item Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures.
\item Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed {\em entirely} in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded.
\end{itemize}
\subsection*{Question 1: Button Mash (25 points)}
Jane is playing a game called \emph{Button Mash} with her boyfriend Charles and her sister Elizabeth. In Button Mash, all players are trying to cooperatively achieve the highest total score after $n$ rounds. Each round, one of the players (or no players possibly), can choose to push a button to earn points. Jane, Elizabeth, and Charles are each given an array ($J$, $E$, and $C$ respectively) of length $n$ containing integers (positive or negative) where the $i$th element denotes the amount of points they would earn if that person pushed the button on the $i$th round. For example, $J[5]$ would be the amount of points that the team would earn on the 5th round if Jane pushed the button. There are two restrictions to the button pushing:
\begin{itemize}
\item At most one player can push the button each round.
\item No player can push the button in two consecutive rounds.
\end{itemize}
Design an algorithm that returns the maximum amount of points that the team can earn along with an array of length $n$ denoting who pushed the button each round to obtain that score. Prove the correctness of your algorithm, and analyze its time and space complexity.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 2: War-Torn Country (25 points)}
You are in a war torn country with $n$ cities $C = \{C_1, C_2, \dots, C_n\}$, fully-connected by a set of $m$ (bidirectional) highways $H$ such that $h_{i, j}$ connects cities $C_i$ and $C_j$. You are in city $C_S$ and would like to get out by traversing highways to reach a city with an airport. There are exactly two cities with airports out of the country, $C_{E_1}$ and $C_{E_2}$. However, since there are terrorists in the city, they naturally would like to take control over some highways. A local news station informs you that each highway $h_{i, j}$ has probability $p_{i,j}$ that the highway is safe from terrorists.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Design an efficient algorithm to find the most optimal way (the safest path) that allows you to escape the country. Analyze the time and space complexity of your algorithm.
\item While figuring out the path, you realize you have completely forgotten about your friends and family! You need to pick them up from the cities $C_A$ and $C_B$ respectively. Modify your algorithm to find the most optimal path again that goes through these cities (in any order).
\end{enumerate}
\textbf{Hint:} When you travel on subsequent highways, you don't \textit{add} their probabilities, but you \textit{multiply} them e.g., the probability that a path $P=v_i,v_j,v_k$ is safe is $p_{i,j} \times p_{j,k}$.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 3: Dark Knight Network (25 points)}
Gotham is being terrorized by Joker, specially in night. Batman has to stop him, but he can only do so if he catches Joker on a well-lit street. Gotham has $n$ junctions fully-connected by $m$ streets, but Batman only has $n-1$ street lights. Lights are placed on streets, and a street with a light is considered \textbf{well-lit}. At most one light can be placed on each street.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Let $L(e)$ denote the length of road $e$. Batman senses that Joker is more likely to end up on longer roads, so he wants to prioritize lighting longer roads. Additionally, he wants to make sure that there is a well-lit path (a sequence of connected well-lit edges) from every junction to every other junction to make sure that all of Gotham is covered. Design an efficient algorithm for Batman to choose which roads to light, maximizing the total length of well-lit roads under the above constraint.
\item Batman showed your algorithm to Alfred, and Alfred said, ``Know your algorithms, Master Wayne. This doesn't have proof of correctness.'' Address the concern raised by Alfred.
\item Call the lit-up road network obtained in part \textbf{(a)} DKN (Dark Knight Network). One of Gotham's roads $e'$ has now been placed under maintenance, increasing the length of that road --- the length of other roads $e\neq e'$ remains the same. Should Batman update the placement of the $n-1$ street lights for his DKN? If `no', justify your answer, otherwise design an efficient algorithm to compute an updated placement incorporating the road length increase.
\end{enumerate}
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 4: Optimal Mario Game (25 points)}
Jane is playing the latest Super Mario game, and she is determined to beat the game before leaving for lunch. The game is defined as follows:
\begin{itemize}
\item Mario begins the game at level $L_1$ with integer amount of lives $E_0$.
\item The objective is to reach the final level $L_n$ with as many lives remaining as possible. Jane needs as many lives as possible to defeat the final boss, Bowser.
\item After entering a level, Mario can proceed to any level that is connected to the current level given that he has enough lives. $C_{u, v}$ represents the change in lives required for Mario to move from level $L_u$ to $L_v$. Mario cannot move from $L_u$ to $L_v$ if they are not connected or if $C_{u, v}$ would penalize Mario down to 0 or less lives.
\end{itemize}
We can represent the Mario world as a directed graph, where the levels are the nodes and directed edges represent connections between the levels. The weights on the directed edges represent the life cost of moving from one level to another. For example, if Mario is in level $L_u$ with 50 lives, and $C_{u, v}=-10$, then Mario will have 40 lives if he chooses to move to level $L_v$. We are also guaranteed that there will be no directed cycles in the graph. To answer the following questions, you may use algorithms learned in class (such as BFS or DFS) without explaining how they work.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Jane is really good at the game, so Mario only has to spend 1 life to go between any two levels (i.e. $C_{u, v} = -1$ for all $u$ and $v$ with an edge from $u$ to $v$). Briefly describe an efficient algorithm that returns the optimal (maximal) number of lives that Mario will have when reaching level $L_n$. Give the time and space complexity of your algorithm.
\item The game has been updated so that it is now more difficult. Now, Mario spends different amounts of lives to go from one level to another, but Mario will never gain lives (i.e. $C_{u, v} \leq 0$). Briefly describe an efficient algorithm that returns the optimal (maximal) number of lives that Mario will have when reaching level $L_n$. Give the time and space complexity of your algorithm.
\item The game developers realized that the previous version was too hard, so they made it more fair. Now, Mario will pick up some extra lives at each level he visits. Specifically, each level $L_i$ is associated with a positive life count $E_i$ such that if Mario enters $L_i$, he will gain $E_i$ lives. Note that Mario collects the lives \emph{after} he enters the level, so he must first have enough lives to traverse to that level before taking the new lives. Describe an efficient algorithm that returns the optimal (maximal) number of lives that Mario will have when reaching level $L_n$. Give the time and space complexity of your algorithm.
\\ \\
\textbf{Hint:} Maybe there is a way to define the problem in terms of subproblems.
\item \textbf{Bonus (5 points):} This time, the game is exactly the same as the previous version except Mario begins the game with a single skip powerup. He can use the powerup at any time to jump to any level he wants (including levels already traversed) except for the final level $L_n$. Modify your previous algorithm to account for this case. Give the time and space complexity of your algorithm.
\end{enumerate}
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\end{document}