\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,float}
% \usepackage{enumitem}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 341 Assignment 1},%
pdfsubject={University of Waterloo, CS 341, Winter 2025},%
pdfauthor={MP}]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\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}}


\graphicspath{ {./figures/} }
\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS 341 Winter 2025}\\
\vspace{2mm}
{\Large\bf Written Assignment 3}\\
%\vspace{3mm}
\textbf{Armin Jamshidpey, Mark Petrick, Collin Roberts \\Copyright $\copyright$ 2025 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Friday, March 7 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}

\item Space complexity is not required for this assignment.

\item Assume all graphs are stored using adjacency list 
representation.
\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 {[10 marks]} Prove or disprove each of the following statements, where in each case $G = (V,E)$ is a connected undirected weighted graph with $n$ vertices and $m$ edges.

\begin{enumerate}
\part{a} If $G$ has $m \ge n$ edges and a unique heaviest edge $e$, then $e$ is not part of any minimum spanning tree of $G$.

\part{b} If $G$ has $m \ge n$ edges and a unique lightest edge $e$, then $e$ is  part of every minimum spanning tree of $G$.


\part{c} If $e$ is a maximal weight edge of a cycle of $G$, then there is a minimum spanning tree of $G$ that does not include $e$.



\end{enumerate}






%%%%%%%%%%%%%%%%%% Q2

\subsection{[10 marks]} A \emph{vertex-and-edge-weighted graph} is a directed graph $G = (V,E)$ where each vertex $v \in V$ has a \emph{cost} $c(v)$ and every edge $e \in E$ has a \emph{weight} $w(e)$. The \emph{length} of a path in $G$ is the sum of the weights of the edges in the path \emph{and} the cost of the vertices in the path. 
In the Single-Source Shortest Path (SSSP) problem on vertex-and-edge-weighted graphs, we are given $G$ and a source vertex $s$ and we want to determine the minimum length of a path from $s$ to $v$ for every $v \in V$. (Note that the minimum length of a path from $s$ to $s$ is $c(s)$.)

Solve the SSSP problem on vertex-and-edge-weighted graphs in the special case where all the weights and the costs are positive integers.








%%%%%%%%%%%%%%%%%% Q3

\subsection {[10 marks]} {}
In the {\sc JobSelection} problem, the input is a positive integer $t$ and a sequence
of $n$ pairs of positive integers $(r_1,p_1), (r_2,p_2), \ldots, (r_n, p_n)$ that correspond to
the \emph{reward} $r_i$ you earn if you complete job $i$ and the \emph{penalty} $p_i$ that you must
pay if you do not complete job $i$. You can only complete $t$ jobs; a valid solution to the problem is
a subset $S \subseteq \{1,2,\ldots,n\}$ of $|S| = t$ jobs that maximizes the profit
\[
{\rm profit}(S) = \sum_{i \in S} r_i - \sum_{j \notin S} p_j
\]
earned by completing the set $S$ of jobs.

Design a greedy algorithm to solve this optimization problem. Prove that it always returns an optimal solution.






%%%%%%%%%%%%%%%%%% Q4

\subsection {[10 marks]}
There are $n$ houses to be connected to the internet in a very sparse forest
neighbourhood.
There are two options for every household $i$:\\
1) to put an ethernet link to a neighbour $j$, which costs $c_{ij}$ dollars, or\\
2) to get a router, which costs $r_i$ dollars (price for the routers can be different depending on the location).

A house will be connected to the internet if either (1) there is some path from it along ethernet links
that leads to a house with the router or (2) there is a router in the house.

Design an efficient algorithm that, given the array $r[1..n]$ and the array $c[1..n, 1..n]$ as input, finds the minimum cost to connect every house to the internet.
Note that not every two houses can be connected by a link, in which case the entry $c_{ij} = \infty$. You may not use dynamic programming.



























\end{document}