<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 341 Assignment 4},%
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}}

\begin{document}

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

\noindent For all dynamic programming questions, clearly state the following:
\begin{itemize}
\item[i)] A definition of the subproblems.
\item[ii)] The recurrence relation used to solve the problem in terms of the optimal solution to subproblems.  Briefly explain what each case covers, in English.
\item[iii)] State the base cases and give an algorithm (in pseudocode) that solves the subproblems in an appropriate order to compute the optimal value.
\item[iv)] An algorithm to recover the actual items (the actual cities visited, actual items chosen, etc) in the optimal solution.
\item[v)] A brief explanation on how the actual items could be recovered if more storage space could be used; i.e., what should be stored and how the actual items would be retrieved.
\item[vi)] Runtime and space complexity for parts iii), iv), and v) above.
\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{[8 marks] }

Consider communication networks consisting of a set of one-way links, over which one node (the source of the link) can send messages to another node (the target of the link).  Since each link is one-way, a direct message in reply may not be possible -- unless the reverse link also exists.

In such a network, a sequence of nodes $p_1,p_2,\dots,p_k$ is a {communication} route from $p_1$ to~$p_k$ (of length $k-1$) iff for each $i$ with $1\leq i&lt;k$, node $p_i$ has a link to~$p_{i+1}$.
A \emph{conversation} route between two nodes $p$ and $q$ consists of a communication route from~$p$ to~$q$ and a communication route from~$q$ to~$p$.
The length of a conversation route is the sum of the lengths of the two communication routes.

Design an efficient algorithm that computes, for each pair~$p$ and~$q$ ($p\neq q$), the length of a shortest conversation route between the two or determines that no such route exists.
The input to the algorithm is a list, for each node, of the nodes to which it has a link.




%%%%%%%%%%   Q1

\subsection{[14 marks] }

You are planning a round-the-world trip which will involve visiting $n$ cities:
$0 \rightarrow 1 \rightarrow 2 \rightarrow \cdots \rightarrow n$.
For traveling between city $i$ and $i+1$ ($0\leq i &lt; n$) you need to choose between two modes of transportation: train or plane.  
You are starting at the train station of city 0 and want to end up at the airport of city $n$. 
The goal is to minimize the cost of the trip.
The cost of transferring between the train station and the airport of city $i$, either direction, is given by $b_i$, $0\leq i \leq n$.
The cost of traveling from city $i$ to city $i+1$ via train is $t_i$ and by plane $p_i$, $0\leq i &lt; n$. 

You prefer taking the train but your traveling companion prefers flying.
As a result of a compromise, an additional constraint to the optimization
problem is that you want to {\bf use the plane exactly $n/2$ times}.
Assume that $n$ is divisible by $2$.

Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.

%%%%%%%%%%   Q2

\subsection{[14 marks]}

Given $n$ items, where item $i$ has value $v_i$ and weight $w_i$ such that $v_i$ and $w_i$ are positive integers.
Suppose we have two knapsacks, each can store up to a weight of $W$ and want to select items to store in the two knapsacks, maximizing the total value of the selected items.

\medskip
\noindent Equivalently, we want to select disjoint subsets $A,B \in \{1, \ldots, n\}$ to maximize:

\begin{center}
$\sum_{k\in A} v_k + \sum_{k\in B} v_k$
\end{center}
subject to the constraints
\begin{itemize}
    \item $\sum_{k\in A} w_k \leq W$  and
    \item $\sum_{k\in B} w_k \leq W$.
\end{itemize}

\noindent Design a dynamic programming algorithm that solves the problem in $O(nW^2)$ time.



%%%%%%%%%%   Q3

\subsection{[14 marks] }

A \emph{histogram rectangle} is a rectangle whose bottom edge lies on the $x$-axis.


\noindent Given $n$ points $p_1=(x_1,y_1),\ldots,p_n=(x_n,y_n)$ (with $y_i&gt;0$ for all $i$) and an integer $k$, we want to find $k$ nonoverlapping histogram rectangles that contain all $n$ points, while minimizing the total area of the rectangles.

See the following example for $k=4$ (the solution below for is not necessarily optimal).  
Note that we allow ``thin'' rectangles with area 0 (like the third one from the left).

\begin{center}
\includegraphics{Images/a4rect.pdf}
\end{center}

\noindent Design a dynamic programming algorithm that solves the problem in $O(kn^2)$ time.

\noindent Hint: First sort the points $p_1,\ldots,p_n$ by $x$-coordinates.
For each $i=0,\ldots,n$ and $j=0,\ldots,k$ or $j=1,\ldots,k$, consider the subproblem of finding $j$ nonoverlapping histogram rectangles that contain $p_1,\ldots,p_i$.
\end{document}
</pre></body></html>