\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning,arrows.meta}
\usepackage[pdftitle={CS 341 Assignment 4},%
pdfsubject={University of Waterloo, CS 341, Winter 2026},%
pdfauthor={MP}]{hyperref}
\usepackage{cleveref}
\usepackage{enumerate}
\usepackage{sepfootnotes}
\usepackage{tcolorbox}
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}

\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\newtheorem{claim}{Claim}
\Crefname{claim}{Claim}{Claims}

\usepackage{algorithmic}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

\newcommand{\pts}[1]{%
  \ifnum\pdfstrcmp{#1}{1}=0
    \textbf{#1~mark}%
  \else
    \textbf{#1~marks}%
  \fi
}
\newcommand{\pt}{{\textbf{1 mark}}}
\newcommand{\opt}{\mathsf{OPT}}


\usepackage{tikz}
\usepackage{wrapfig}
\usepackage{pgfplots}

\tikzstyle{vertex}=[circle, draw, inner sep=1pt, minimum size=15pt]

\usetikzlibrary{arrows.meta}
\tikzset{>={Latex[width=2mm,length=2mm]}}

\tikzset{
  dot/.style={circle, draw, fill=black, inner sep=0pt, minimum width=4pt},
}
\usepackage{graphicx}
\graphicspath{ {images/} }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS 341 Winter 2026}\\
\vspace{2mm}
{\Large\bf Written Assignment 4}\\
%\vspace{3mm}
\textbf{Elena Grigorescu, Mark Petrick, Luke Schaeffer \\Copyright $\copyright$ 2026 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Monday, March 16 at 11:59pm to Crowdmark \\
All work submitted must be the student's own.}
\end{center}
\begin{itemize}
\item Make sure to read the Assignments section on the course webpage for instructions on submission and question expectations (``Instructions for Assignments"):  \\ \url{https://student.cs.uwaterloo.ca/~cs341/#Assignments}
\end{itemize}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

%%%%%%%%%%%% Q1


\subsection{[17 marks] Ski Consultant}

The Loowater Downhill Ski Resort (LDSR) has hired you as a consultant. For those not familiar with downhill skiing (and snowboarding), a ski resort consists of 
\begin{itemize}
	\item a network of \emph{trails} that visitors can ski/snowboard \emph{down},
	\item a system of powered \emph{lifts} to transport people \emph{up} the mountain, 
	\item a number of \emph{base lodges}, with access to parking and shuttle buses.
\end{itemize}
We model this as a directed graph $G = (V,E)$ (given by an adjacency list), where the edges are partitioned $E = T \cup L$ into trails $T$ and lifts $L$. Additionally, $B \subseteq V$ is the set of base lodges at Loowater. 

Note that trails go down hill, and lifts go up hill, so the two sets are (separately) topologically ordered by elevation. That is, $(V,T)$ is a DAG and $(V,L)$ is a DAG. You may assume there are no isolated vertices in $(V,T)$.  

Your job is to help LDSR answer a few questions about their resort. For each one, you should design an algorithm using the ideas from class, and briefly justify it. 

\begin{enumerate}
	\part{a} Is every trail accessible from some base lodge? For all $v \in V$, does there exist a base lodge $b_v \in B$ such that there is a walk from $b_v$ to $v$? 
	\part{b} Assume the answer to part (a) is yes. Is there is a \emph{candidate main lodge} $b^{*} \in B$ from which every trail is accessible? If so, identify all such lodges because LSDR are interested in expanding one of them with a better rental shop, food and drink, etc., and want to know their options. 
\end{enumerate}
LDSR also wants to know what happens at the end of the day when the lifts shut down. Without lifts, the skiers can only ski down trails, and the graph collapses to $G = (V,T)$.
\begin{enumerate}
	\part{c} Can all skiers get back to some base lodge? For all $v \in V$, does there exists a $b_v \in B$ such that there is a walk $v \leadsto b_v$? 
	\part{d} For safety reasons, it is important that the ski patrol be able to evacuate wounded skiers to some lodge on a stretcher, without assuming that the lifts are working. Given weights $w(t) > 0$ for all trails $t \in T$, representing the time required to ski a trail in a medical situation, find the vertex farthest from a lodge. 
\end{enumerate}

\subsection{[9 Marks] MinMax spanning trees}
Consider an undirected positively-weighted connected graph $G = (V, E)$. A tree $T = (V, E')$ is a \textit{MinMax Spanning Tree} (MMST), if it is a spanning tree of $G$ in which cost of the edge with maximum weight is minimized. In other words, $T$ is an MMST if there is no other spanning tree of $G$ in which the edge weights are all smaller than the weight of the maximum weight edge in $T$. Prove or disprove each of the following statements:
\begin{enumerate}
    \part{a} Every MinMax Spanning Tree of $G$ is a Minimum Spanning Tree of $G$.
    %
    \part{b} Every Minimum Spanning Tree of $G$ is a MinMax Spanning Tree of $G$.
\end{enumerate}

\subsection{[9 marks] Self-Storage Scheme}

Dolly Boxley needs to store some priceless family heirlooms in a rental self-storage facility for a few years. The problem is that all $n$ self-storage facilities near her offer great introductory deals on the first month, and then the second month onward is at a dramatically higher rate. So, Dolly has devised a scheme to \emph{cycle} through the facilities: she'll rent for one month at one facility, then move everything to another facility and rent one month there, then move again and so on, such that she perpetually gets the first month rate. 

However, there is a cost to moving each month. Dolly has done her research and prepared a table $C$ where $C[i,j]$ is the cost to move from facility $i$ to facility $j$, factoring in her own time, the cost of gas, the fees at both facilities, etc. Note that due to some very annoying one-way streets, the cost of moving is not symmetric, i.e., $C[i,j] \neq C[j,i]$. $C[i,i]$ represents the cost of leaving the items at facility $i$ and paying the higher monthly rate. We also interpret $C$ as a weighted graph $G = (V, E)$. 

Dolly is looking for the best long-term solution, i.e., a cycle of facilities $f_0, f_1, \ldots, f_k = f_0$ such that the average monthly cost 
\[
c^{*} = \frac{1}{k} \sum_{j=0}^{k-1} C[f_j, f_{j+1}],
\]
is as low as possible. We'll call this cycle the \emph{optimal cycle}.
\begin{enumerate}
    \part{a} Suppose we knew $c^{*}$ in advance, and constructed a graph $G(c^{*})$ by subtracting $c^{*}$ from every edge. Show that $G(c^{*})$ contains a zero weight cycle and no negative weight cycles. 
    \part{b} Suppose all costs in the table $C$ are integers between $0$ and $W$. Briefly describe how to use binary search to find $c^{*}$ and an optimal cycle in $O(mn(\log(W) + \log(n))$ time. 
    %\part{c} Dolly is currently storing her items in facility $s$. 
\end{enumerate}

\subsection{[5 Marks] Course assignment}
 A high school principal is trying to finalize the assignment of teachers to courses for scheduling the upcoming semester. The school has $n$ teachers (namely: $t_1, t_2, \ldots, t_n$) and there is a maximum of $m$ courses (namely: $c_1, c_2, \ldots, c_m$) to be offered. Each teacher can be in charge of two courses per semester, and each course must have exactly one teacher during the semester. For each teacher $t_i$, there is a subset $S_i \subset \{c_1, c_2, \ldots, c_m\}$ of courses s/he can teach. The principal is trying to come up with an assignment such that the number of offered courses is maximized and he has been advised that he can use Ford-Fulkerson max-flow algorithm to obtain such a schedule. Your task is to design an efficient construction to help the principal for finding an assignment as desired. Notice that it may or may not be possible to offer all $m$ courses. Also, there might be more than one assignment with the desired property, it is enough for your solution to return one  of them. Analyze the running time and briefly justify your answer.

\end{document}