\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{fullpage}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{latexsym}              % Additional LaTeX Symbols
\usepackage{amssymb}               % AMS Fonts
\usepackage{enumitem}
\usepackage{pseudocode}
\newcommand{\nats}{\ensuremath{\mathbb N}}
\newcommand{\Real}{\ensuremath{\mathbb R}}
\newcommand{\ind}[1]{\hspace*{#1em}}
\newcommand{\Algorithm}{{\bf Algorithm\ }}
\newcommand{\Subroutine}{{\bf Subroutine\ }}
\newcommand{\Comment}{{\bf Comment\ }}
\newcommand{\Note}{{\bf Note:\ }}
\newcommand{\Assert}{{\bf assert:\ }}
\newcommand{\Input}{{\bf Input:\ }}
\newcommand{\Output}{{\bf Output:\ }}
\newcommand{\Caveat}{{\bf Caveat:\ }}
\newcommand{\Condition}{{\bf Condition:\ }}
\newcommand{\For}{{\bf for\ }}
\newcommand{\From}{{\bf from\ }}
\newcommand{\Downto}{{\bf downto\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\By}{{\bf by\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Od}{{\bf od}}
\newcommand{\While}{{\bf while\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\Elif}{{\bf elif\ }}
\newcommand{\Fi}{{\bf fi}}
\newcommand{\myAnd}{{\bf and\ }}
\newcommand{\Or}{{\bf or\ }}
\newcommand{\Break}{{\bf break}}
\newcommand{\Next}{{\bf next}}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\bigO}{{O\tilde{\phantom{\imath}}}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\Q}{\ensuremath{\mathbb Q\mskip1mu}}
\newcommand{\K}{{\mathsf{K}}}
\newcommand{\F}{{\mathsf{F}}}
\newcommand{\R}{{\mathsf{R}}}
\newcommand{\B}{{\mathsf{B}}}
\newcommand{\M}{{\mathsf{M}}}
\newcommand{\MM}{{\mathsf{MM}}}
\newcommand{\remove}[1]{{}}
\newcommand{\ignore}[1]{{}}
\newcommand{\rednote}[1]{{\color{red} #1}}
\newcommand{\bluenote}[1]{{\color{blue} #1}}

\newif\ifmarking
\markingfalse
\markingtrue
\newcommand{\markscheme}[1]{\ifmarking{\tcbset{colframe=red,colback=white,colupper=red}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

\newif\ifsoln
\solnfalse

\newcommand{\solution}[1]{\ifsoln{\tcbset{colframe=blue,colback=white,colupper=blue}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

\markingtrue

% for typesetting code
\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

\begin{document}

\noindent
{CS 341, Fall 2025 \hfill  T. Brown, É. Schost}

\begin{center}
\ifsoln{\large\bf ASSIGNMENT 4 SOLUTIONS}
\else{\large\bf ASSIGNMENT 4}
\fi
\end{center}

\ifsoln{\noindent\bf 
These solutions are for students currently enrolled in the Fall 2025 offering of CS 341 only.  You may not share or distribute them with anyone outside the course without explicit written permission from the instructors. (To do so is a violation of academic conduct.)}
\fi

\bigskip
\noindent
DUE: Mon Nov 17, 11:59 PM.
DO NOT COPY.  ACKNOWLEDGE YOUR SOURCES.

\medskip
\noindent
Please read \verb|http://www.student.cs.uwaterloo.ca/~cs341| for
general instructions and policies.

{\bf Note:} All logarithms default to base 2 (i.e.,  $\log x$ is defined as $\log_2 x$).
{\bf Note:}  ``Giving'' an algorithm means doing the four parts (i)--(iv) as described on the course web page. \textbf{Proofs are required unless we explicitly state otherwise.} If you think we made a mistake and a proof is not required, feel free to ask. 
You may use the \textbf{unit cost model unless otherwise stated}.

\bigskip
\noindent



\begin{enumerate}

\item{[15 marks]} \textbf{Solving a System of Linear Inequalities.}
You are given a system $\Sigma$ of $m$ linear inequalities over $n$ unknowns $x_1,\dots,x_n$. Each inequality is of the form:
\[ x_i - x_j \le a_{i,j}\]
where $a_{i,j}$ is an integer constant.
Note that $a_{i,j}$ is not necessarily defined for all $(i,j)$.
Thus, the $a_{i,j}$ integers that \textit{are} defined are given to you in an array $A[1..n]$ where \textit{each entry} $A[i]$ is itself an array.
More specifically, $A[i]$ is an array of entries of the form $[j, a_{i,j}]$.
In other words, $A[i]$ contains $a_{i,j}$ for all $j$ such that $a_{i,j}$ is actually defined in $\Sigma$.

Give an algorithm that decides if there is a solution to these
inequalities, and if so, finds one.
The output is thus: NULL if there is no solution, and an array of $n$ integers containing the (solved) values of $x_1 ... x_n$ otherwise.

Hint: build a weighted directed graph $G$ such that $G$ has no negative weight cycle if and only if there is a solution to the system $\Sigma$.



\item{[15 marks]} \textbf{Verifying Treeness, Spanning and Minimality.}
You are given a connected weighted undirected graph $G=(V,E)$, with
vertices $V=\{1,\dots,n\}$, and $m$ edges. As input, you can assume an adjacency list representation $A[1..n]$.
Each $A[i]$ is itself an array, with all entries of the form $[j,w_{i,j}]$, with $w_{i,j}$ the weight of edge $\{i,j\}$.
You can assume that all $w_{i,j}$ are distinct, and that the entries of $A[i]$ are sorted in increasing order of $j$.

You are also given an array $T[1..n-1]$, whose entries are in principle \textit{meant to} represent some edges of $G$, but you \textbf{may not} assume its entries actually represent edges of $G$.
All you may assume is that each entry of $T$ is of the form $(u,v)$, with $u \ne v$ integers in $1,\dots,n$.
The goal of this problem is to verify whether $T$ is the
minimum spanning tree of $G$.\footnote{Warning: we will not obtain a better worst-case bound than Kruskal's algorithm (in any part). Still, we hope to design an algorithm that would be able, in practice, to detect \textit{early on} that $T$ is not an MST.}

\begin{enumerate}
\item Prove the following general property: for any cycle $C$ in $G$,
  the edge $e$ with maximum weight on $C$ does not belong to the
  minimal spanning tree of $G$.

\item Give an algorithm that determines whether $T$ is a
  \textbf{spanning tree} (not necessarily minimal). If so, return an array $P[1..n]$ where for all
  $i$, $P[i]=[j,w_{i,j}]$, with $j$ the parent of $i$ in $T$.
  For this to make sense, assume that \textit{if $T$ is a spanning tree}, then we choose the vertex $1$ as root (and set $P[1]=[1,\bullet]$).
  If $T$ is not a spanning tree, you can return NULL.
  For full credit, this should be done in time $O(n \log n)$.

\item (bonus question, +4 marks) Assume $T$ is a \textbf{spanning tree}. For any vertices $u\ne v$ in $G$, there is a unique path
  $P_{u,v}$ connecting $u$ to $v$ in $T$; we are interested in
  accessing efficiently the maximum weight $w^T_{u,v}$ of the edges along this
  path, that is, $w^T_{u,v}=\max_{e \in P_{u,v}} w_e$. Describe a data structure $S$ such that
  \begin{itemize}
  \item given $P$ from the previous question, $S$ can be created in time $O(n \log n)$
  \item given $S$, $u$ and $v$, you can obtain $w^T_{u,v}$ in time $O(\log n)$.

  \end{itemize}

  Note that $S$ should contain information about \textit{all pairs} of $u, v$ so that you can answer queries about \textit{any} $u,v$ pair in $O(\log n)$ time.

\item For this part, assume that you already have a complete solution to part (c), meaning you have access to a data structure that lets you find $w_{u,v}^T$ in $O(\log n)$ time for any $u, v$.
  Assume that $T$ is a spanning tree. Give a simple
  criterion involving the weights $w_{u,v}$ and $w^T_{u,v}$ to test if
  $T$ is minimal.
  Give an algorithm that decides if $T$ is minimal,
  and give a big-O on the worst-case runtime.

\end{enumerate}

\item{[10 marks]} \textbf{Squid-like game.}
Input: a 2D array $A[1..k, 1..k]$ of positive integers, a start location $s = (s_i, s_j)$ and a finish location $f = (f_i, f_j)$.

The array represents a $k \times k$ grid of breakable floor tiles that you can stand on.
You start on tile $s$ at time 0, and it takes 1 unit of time to jump to a neighbouring tile (up, down, left, right).\footnote{It doesn't \textit{really} matter which direction you consider +/- i or +/- j to be, but let's say -i is up, +i is down, -j is left and +j is right. I.e., the same as: \texttt{for (i = 1..k) \{ for (j = 1..k) print $A[i, j]$ \} print newline}.}
You want to travel to tile $f$.

Unfortunately, as time ticks forward, the floor tiles are being smashed!
Fortunately, you know, for each tile, the exact time when it will be smashed.
Those times are exactly the contents of the array $A$.
That is, tile $i,j$ is smashed at time $A[i, j]$.
The tile you are trying to move to, $f$, is a safe tile (smashed at time $\infty$).

You cannot occupy a smashed tile, but you can leave a tile at the same time as it is being smashed.
More specifically, if you are on tile $i,j$ at time $t = A[i, j] - 1$ (meaning the tile will be smashed in the next time step), then you can safely move to a neighbouring tile, arriving at time $t+1$, as long as that neighbouring tile will be smashed at time $t+2$ or later.

\textbf{Output: True/false. Can you travel safely from $s$ to $f$?}

Runtime $O(k^2)$ for full marks.

\end{enumerate}

\end{document}
