\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning,arrows.meta}
\usepackage[pdftitle={CS 341 Assignment 2},%
pdfsubject={University of Waterloo, CS 341, Winter 2026},%
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 2026}\\
\vspace{2mm}
{\Large\bf Written Assignment 2}\\
%\vspace{3mm}
\textbf{Elena Grigorescu, Mark Petrick, Luke Schaeffer \\Copyright $\copyright$ 2026 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Friday, February 6 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{[10 Marks] Completion time with priorities}
In class we saw a greedy algorithm, where, given $n$ jobs with their processing times, we designed a greedy algorithm that minimized the sum of completion times $\sum_{i\in [n]} C(i)$. Here, assume further that each job $i$ also has an importance, given by a value $p_i>0.$ The new goal is to minimize the sum $\sum_{i\in [n]}p_i C(i)$, where $C(i)$ represents the completion time of job $i$. Design and analyze an efficient algorithm to solve this problem.



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

\subsection{[10 Marks] Rich and greedy}
Bank manager Jezos wants to ensure that his gold bullion are monitored using an advanced surveillance system. Nevertheless, he is cost-conscious, and would not use more cameras than strictly necessary to monitor his gold locations. 
However, he does enlist the help of CS 341 student Kate to help him minimize the number of surveillance cameras that need to be installed, and figure out where they should be installed. 

Assume that the piles of gold are spaced out along a long corridor, and the surveillance cameras can only cover unit-length closed intervals of its length. Then Kate's algorithm must compute the smallest set of unit-length closed intervals that contains all of the gold piles. For example, given the set of points $\{2.5, 3, 3.2, 6, 6.5\}$, representing the locations on the corridor of the gold piles, one of the smallest set of unit-length closed intervals covering the points could be $[2.5,3.5]$ and $[6,7]$.   

\begin{enumerate}
    \part{a} Describe an efficient algorithm that, given a set of locations $\{x_1, x_2, \ldots, x_n\}$ outputs the smallest set of intervals at which surveillance cameras must be installed, i.e., the smallest set of unit-length closed intervals that contains all of the gold.
    \part{b} Argue that your algorithm is correct, and analyze the running time of your algorithm.
\end{enumerate}




\subsection{[15 Marks] No neighboring items }

 Given an array $S$ of integers in arbitrary order and an integer $d$, $1\leq d \leq n/2$, find a way to select entries in $S$ so that the sum of the selected entries is maximum among all selections where  
any two selected entries are at least $d$ locations apart in $S$ (i.e., if indices $p$ and $q$ are chosen, we have $|p-q| > d$). 
\begin{itemize}
\part{a} Define a recurrence relation relevant to the solution and briefly justify its correctness.
\part{b} Describe the table used in this dynamic programming algorithm as follows:

\begin{itemize}
\item State the dimension of the table.
\item State the meaning (in English) of what an entry in the table represents
\item State the table initialization.
\item State the order in which the table will be filled in.
\end{itemize}

\part{c} Write out the algorithm (in pseudocode) to solve this dynamic programming problem and state how to obtain the final value.

\part{d} Write out the algorithm (in pseudocode) with brief description to determine the optimal sequence.

\part{e} Analyze the running time of the algorithm that determines the optimal sequence.
\end{itemize}




\subsection{[15 Marks] A thief with two knapsacks}

 A thief is faced with $n$ valuable items, each with weight $w_i$ and profit $p_i$, $1 \leq i \leq n$, and  he is prepared with two knapsacks of capacity $W_1$ and $W_2$, respectively. 
 He may only hide the stolen items in his knapsacks,  the items are indivisible and unique, and of course, he cannot exceed the capacity of each knapsack. He will quickly have to figure out how to maximize his profit. Design and analyze the solution of a smart thief, by giving precise answers to each subproblem a)-e) from Question 3 above.
 

\end{document}