\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{fullpage}
%\usepackage[]{algorithm2e}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{latexsym}              % Additional LaTeX Symbols
\usepackage{amssymb}               % AMS Fonts
\usepackage{enumitem}
\usepackage{pseudocode}

\usepackage{tikz}
\usetikzlibrary{shapes,chains,positioning}
\usetikzlibrary {graphs,quotes}



\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
\solntrue
\newcommand{\solution}[1]{\ifsoln{\tcbset{colframe=blue,colback=white,colupper=blue}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

\solntrue
% \markingfalse

% 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}
\large\bf ASSIGNMENT 2
\end{center}

\bigskip
\noindent
DUE: Wed Oct 8, 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.

\bigskip
\noindent

\begin{enumerate}

    \item{[10 marks]} \textbf{Greedy / Divide \& Conquer.}
        \begin{enumerate}
            Suppose there are $n$ valuable gemstones embedded in the ground, arranged in a line.
            The gemstones have positive integer values $v_1, v_2, ..., v_n$.
            You can \textit{extract} gemstones from the ground using your pickaxe, but in the process of extracting gemstone $v_i$, you will \textit{destroy} gemstones $v_{i-1}$ and $v_{i+1}$.
            The exceptions are $v_1$ and $v_n$.
            Extracting $v_1$ will only destroy one gemstone, $v_2$, and extracting $v_n$ will only destroy $v_{n-1}$.
            The goal is to extract gemstones in such a way as to \textbf{maximize the total value} you obtain.
            
            Prove that the following greedy algorithms for this problem are \textbf{incorrect}.
        
            \item{[1 mark]}
                Consider gems in the input order, and take every gemstone that you can.
                (In other words, at each step, if the gemstone being considered is not already destroyed, take it, destroying its neighbours.)

            \item{[1 mark]}
                Sort from most valuable to least valuable (i.e., such that $v_1 \ge v_2 \ge ... \ge v_n$) then take every gemstone you can in that order.
                (Assume we also keep track of where the gems were in the input order, i.e., before the sort, so we know which gems are destroyed when we extract a gem.)

            \item{[1 mark]}
                Do preprocessing to determine the sums $S_{odd}$ of all odd $v_i$, i.e., $v_1, v_3, ...$, and $S_{even}$ of all even $v_i$, i.e., $v_2, v_4, ...$.
                If $S_{odd}$ is larger, extract all of the odd gems.
                Otherwise extract the even ones.

            \item{[1 mark]}
                For each gem $v_i$, $1 < i < n$, let $f_i = \frac{v_i}{v_{i-1}+v_{i+1}}$, and let $f_1 = \frac{v_1}{v_2}$ and $f_n = \frac{v_n}{v_{n-1}}$.
                Sort from largest to smallest $f_i$ (breaking ties arbitrarily), remembering where each gem was in the input order.
                Then, take every gem you can (i.e., that is not destroyed) in that order.
                
            \item{[1 mark]}
                For each gemstone $v_i$, $1 < i < n$, let $f_i = v_i - v_{i-1} - v_{i+1}$ (i.e., the value you would get from the gem, minus the values of the gems that would be destroyed).
                For $v_1$ and $v_n$, let $f_1 = v_1 - v_2$ and $f_n = v_n - v_{n-1}$, respectively.
                Sort from largest to smallest $f_i$ (breaking ties arbitrarily), then take every gemstone you can (i.e., that is not destroyed by another gem you extract) in that order.

            \item{[5 marks]}
                Design a divide \& conquer algorithm that returns the maximum value that can be achieved by extracting gems.
                Briefly justify correctness.
                Give a $\Theta$ bound for your algorithm's runtime in the unit cost model.
                To make the analysis a easier, you can ignore floors/ceilings, or differences of +/- 1 or 2 between subproblem sizes.
        
        \end{enumerate}



\medskip

\item{[10 marks]} \textbf{Greedy.}

We are given $n$ jobs (we'll just refer to them by their indices, from
$1$ to $n$); each one takes one unit of time to complete. We are also
given deadlines $d_1,\dots,d_n$ (positive integers) and rewards
$r_1,\dots,r_n$.  We'll say that a set of jobs $F \subseteq
\{1,\dots,n\}$ is satisfiable if we can find an ordering of it for
which all its jobs are done before, or at the time of, their
respective deadlines. If that's the case, the total reward of $F$ is
$R(F)=\sum_{j \in F} r_j$.

Your task will be to design a greedy algorithm that finds a
satisfiable set $F$ that maximizes $R(F)$; the first questions will
possibly help you prove correctness.
\begin{enumerate}
\item {[1 mark]} For a set of jobs $F \subseteq \{1,\dots,n\}$, and $t \in
  \{0,\dots,n\}$, we define the counting function $c(F,t)$ as the number
  of jobs in $F$ with deadline at most $t$. Prove that $F$ is
  satisfiable if and only if $c(F,t) \le t$ for $t=0,\dots,n$.

\item {[3 marks]} Let $G$ and $F$ be satisfiable sets,
  with $F$ not included in $G$, and suppose that $j$ is a job in $G$,
  but not of $F$. Prove that there is a job $i$ in $F$, but not in
  $G$, such that $F \cup \{j\} -\{i\}$ is satisfiable. Suggestion: use
  the previous question.
  
\item {[3 marks]} Give a greedy algorithm that finds a satisfiable set $G$
  that maximizes the total reward. For this question, a description in
  words and a correctness proof are sufficient; don't worry about
  implementation details yet.

  Suggestion: prove that if $G$ is the greedy output and $F$ any other
  satisfiable set, you can build $F'$ satisfiable with $R(F) \le
  R(F')$ and $|G \cap F'| > |G \cap F|$. First, though: assuming that
  this suggested claim is valid, make sure that you can explain why
  this would prove that the greedy output is optimal (if you do this
  last step correctly, even without proving the suggested claim, you
  will get partial credit).

\item {[3 marks]} Explain how to implement the strategy from (c): tell us
  what data structure(s) you use and how you will use them to perform
  the required operations. Give a big-O bound for the resulting
  runtime; $O(n^2)$ is enough for full marks on this question.
\end{enumerate}


\medskip

\item{[10 marks]} \textbf{Dynamic Programming.}

We consider a directed graph $G=(V,E)$, where edges $e$ are labeled by both a {\em probability} $p[e]$ and a character $c[e]$. For any vertex $v$, the sum of all $p[e]$, for $e=(v,w)$, is equal to $1$.

We can build a string $S$ by starting from an arbitrary vertex $s$, and repeating $L$ times the following: from the current vertex $v$, choose an edge $e=(v,w)$ at random (using the probability distribution given by the probabilities $p[e]$, for $e$ outgoing edge at $v$), append its character $c[e]$ to $S$, and repeat from $w$.

The goal here is to somehow reverse the process: you are given the string $S$, and your task is to determine what was the likeliest walk we followed to produce this string: you should return the probability of this walk (which is the product of the probabilities of its edges) and the walk itself. For example, consider the following graph, with edges labeled with their probabilities and characters $T$ or $F$ (at $v=1$, both outgoing edges have the same label; this is fine).
\begin{center}
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw}]
    \node (S) at (0,0) {$1$};
    \node (A) at (1.5,1.5) {$2$};
    \node (B) at (1.5,-1.5) {$3$};
    \node (C) at (4.5,1.5) {$4$};
    \node (D) at (4.5,-1.5) {$5$};
\end{scope}
\begin{scope}[ 
    every edge/.style={draw=red,very thick}]
     \path [->] (S) edge node [left]{$0.6$, $T$} (A);
     \path [->] (S) edge node [left=1mm]{$0.4$, $T$} (B);
     \path [->] (A) edge node [above]{$0.1$, $T$} (C);
     \path [->] (A) edge node [left=2mm, pos=0.2] {$0.9$, $F$} (D);
     \path [bend right,->] (B) edge node [very near end,right]{$1$, $T$} (C);
     \path [->] (C) edge node [left,very near end]{$1$, $F$} (B);
     \path [bend right, ->] (D) edge node [right,very near start] {$0.3$, $T$} (A);
     \path [->] (D) edge node [below]{$0.7$, $F$} (B);
\end{scope}
\end{tikzpicture}
\end{center}
Starting from $v=1$, there are two ways we can obtain the string $S=TT$, through the walks $124$ and $134$. The former has probability $0.6 \times 0.1 = 0.06$, the latter $0.4 \times 1 = 0.4$. There is only one other walk labeled $S=TT$, namely $524$, with probability $0.3 \times 0.1=0.03$. So in this case, the output of the algorithm should be the walk $134$, with its probability $0.4$.

Describe an algorithm that performs this task and analyze its runtime in terms of $n$ (number of vertices), $m$ (number of edges) and $L$ (length of the string $S$). You can assume that all operations you do use arguments that fit in a word (this includes floating-point arithmetic, to manipulate the probabilities) and you can do the analysis in the unit cost model. You can also assume that the vertex set is $V=\{1,\dots,n\}$, and that you are given the graph as an array $A=A[1..n]$, with each $A[i]$ being the list of all $j$ such that $(i,j)$ is an edge.


\end{enumerate}

\end{document}
