% Created 2016-10-30 Sun 14:03
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{soul}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\usepackage{amsmath}
\usepackage{algpseudocode}
\usepackage[margin=0.75in]{geometry}
\usepackage{nth}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,calc}
\usepackage{ccicons}
\usepackage{fancyhdr}
\usepackage{hyperref}
\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International License. \ccby}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
%\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by-nc/4.0/}{Creative Commons Attribution-NonCommercial 4.0 International License. \ccbync}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
\providecommand{\alert}[1]{\textbf{#1}}

\title{CPSC 320 2016W1: Assignment 4}
\author{}
\date{2016-10-20 Thu}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs Org-mode version 7.9.3f}}

\begin{document}

\maketitle

Submit this assignment via handin (see the \href{http://blogs.ubc.ca/cpsc320/syllabus/#assignments}{syllabus} for more
information) to the target \texttt{assn4} by the deadline \textbf{Thursday 10 Nov at 10PM}. For credit, your group must make a \textbf{single} submission via one
group member's account. Your group's submission \textbf{must}:
\begin{itemize}
\item Be on time.
\item Consist of a single, clearly legible PDF file named \texttt{solution.pdf}
  with clearly indicated solutions to the problems. (Directly produced
  via \LaTeX{}, Word, Google Docs, or other editing software is
  best. Scanned is fine. \textbf{High-quality} photographs are OK if we agree
  they're legible.)
\item Include prominent numbering that corresponds to the numbering used
  in this assignment handout (not the individual quiz postings). Put
  these \textbf{in order}, ideally. If not, \textbf{very clearly} and prominently
  indicate which problem is answered where!
\item Include at the start of the document the names and ugrad.cs.ubc.ca
  account IDs of each member of your team.
\item Include at the start of the document the statement: ``All group
  members have read and followed the \href{http://blogs.ubc.ca/cpsc320/syllabus/#conduct}{guidelines for academic conduct in CPSC 320}. As part of those rules, when collaborating with anyone
  outside my group, (1) I and my collaborators took no record but
  names away, and (2) after a suitable break, my group created the
  assignment I am submitting without help from anyone other than the
  course staff.'' (Go read those guidelines!)
\item Include at the start of the document acknowledgment of collaborators
  and references (with the exceptions listed in the conduct
  guidelines).
\end{itemize}
\section{The Price Isn't Always Right}
\label{sec-1}

Aconcagua.com sells storage on both an auction and fixed-price
basis. They want to use historical auction data to investigate their
fixed price choices.

For $n$ seconds, they have the price point reached in each second in
their auctions. They want to find the largest price-over-time stretch
in their data. That is, given an array $A$ of $n$ price points, they
want to find the largest possible value of $f(i,d) =
d*\min(A[i],A[i+1],\ldots,A[i+d-1],A[i+d])$ where $i$ is the index of
the left end of a stretch of seconds, $d$ is the duration in seconds
of that stretch, and the function $f$ computes the duration times the
minimum price over that period. (Prices are positive, $d \geq 0$, and
for all values of $i$, $f(i,0) = 0$ and $f(i,1) = A[i]$.)

For example, the best stretch is underlined in the following price
array: $[8, 2, \underline{9, 5, 6, 5}, 3, 1]$. Using 1-based indexing,
the value for this optimal stretch starting at index 3 and running for
4 seconds is $f(3,4) = 4*\min(9, 5, 6, 5) = 4*5 = 20$.

\begin{enumerate}
\item Give a \textbf{brute force} algorithm to solve this problem. Your algorithm
   must run in polynomial time.
   %\vfill
   %\vfill
   %\vfill
\item Give and briefly justify a good asymptotic bound on the runtime of
   your algorithm.
   %\vfill
\end{enumerate}
%\clearpage
\subsection{Divide-and-Conqaguar}
\label{sec-1-1}

In this part, you will give a divide-and-conquer approach that is more
efficient than the brute force approach.
\begin{enumerate}
\item Consider again the example array from the previous part: $[8, 2, 9,
   5, 6, 5, 3, 1]$. Imagine that you are told that the solution \textbf{must}
   use the elements at indexes 4 and 5 (i.e., elements 5 and 6). You
   want to expand the stretch either to the left or right one step at
   a time while maintaining the invariant that the stretch you have
   chosen is the best that includes indexes 4 and 5 until the stretch
   includes the entire array.
   
   Finish the following table describing this expansion, thinking
   carefully about why you make the choice you do at each point:

\begin{center}
\begin{tabular}{rrrr}
    $i$  &     $d$  &  minimum  &  $f(i,d)$  \\
      4  &       2  &        5  &        10  \\
      3  &       3  &        5  &        15  \\
      3  &       4  &        5  &        20  \\
 \ldots  &  \ldots  &   \ldots  &    \ldots  \\
      1  &       8  &        1  &         8  \\
\end{tabular}
\end{center}


\item Give an efficient algorithm for finding the optimal price stretch.
\item Give and briefly justify a good asymptotic bound on the runtime of
   your algorithm.
\end{enumerate}
%\clearpage
\section{CS CSI}
\label{sec-2}

The major credit card company DoctorCard can either check a
transaction to see if it's fraudulent or skip it. Each transaction
comes with an estimated value for fraud checking (based on the size
and suspiciousness of the transaction). Skipping a transaction
provides no value. Checking if it's fraudulent provides the estimated
value. However, because of computational costs, DoctorCard \textbf{must} skip
checking the next two transactions if they check the current
one.

We're interested in maximizing the total fraud value checked given
such an array of estimated values $A$.

So, for example, the optimal transactions to check are underlined in
the following transaction record: $[4, \underline{9}, 1, 10, 1,
\underline{7}, 2, 2]$. Note that each checked (underlined) transaction
must be followed by at least two unchecked transactions and that
therefore the last two entries must always be unchecked.

Design an efficient algorithm to find the maximum total fraud
value. Your algorithm need not find the actual transactions to check,
just the value.\footnote{If you want a justification of that: DoctorCard is
comparing the value achieved by their online algorithm---i.e.,
algorithm that makes choices as transactions arrive---against the
optimal total achievable.
 } Your algorithm may use linear memory and
time.

\textbf{HINT:} Start by designing a recurrence $F(n)$ that describes the
optimal fraud value achievable for transactions $1,\ldots,n$ in terms
of the optimal value(s) for smaller stretches of the array. Then,
either convert that into a recursive solution and memoize it or
convert that into a dynamic programming solution.
%\clearpage
\subsection{CSI Finds the Culprit}
\label{sec-2-1}

Adapt your original algorithm so that it produces the optimal set of indexes to
check for fraud rather than the maximum total value.
\subsection{Forgetful CSI}
\label{sec-2-2}

Instead adapt your original algorithm so that it produces only the
maximum total value but does it using constant memory.
%\clearpage
\section{Hitting Rock Bottom}
\label{sec-3}

Finding the global minimum---the single smallest element---in an
unsorted array of numbers requires $\Omega(n)$ time.  A \textbf{local}
minimum is a number that is smaller than its neighbour(s). (For $n>1$,
the first and last elements have only one neighbour each and so it's
``easier'' for them to be local minima.) A local minimum can be found
more quickly.

For example, the three local minima in the following array are
underlined: $[8, \underline{2}, 3, 7, 9, \underline{5}, 6, 12,
\underline{10}]$.

\begin{enumerate}
\item Give an efficient algorithm to find a \textbf{local} minimum of an array
   of $n$ distinct numbers. (You may assume $n > 1$ if
   needed.) \textbf{HINT:} try to quickly find a portion of the larger array
   in which there's guaranteed to be at least one local minimum.
   %\vfill
   %\vfill
   %\vfill
\item Give and briefly justify a good asymptotic bound on the runtime of
   your algorithm.
   %\vfill
\item Sketch the key points in a proof that your algorithm is
   correct. (You may find it useful to establish and take advantage of
   this condition: ``the leftmost and rightmost elements of the portion
   of $A$ under consideration are smaller than any neighbours they
   have outside the portion of $A$ under consideration'' or to put it
   another way ``I can check if the leftmost and rightmost elements are
   local minima without having to consider anything outside the
   portion of $A$ under consideration''.)
   %\vfill
   %\vfill
\end{enumerate}
%\clearpage
\subsection{Rock Bottom Tiles}
\label{sec-3-1}

Now, consider an $n\times n$ 2-dimensional array of distinct
numbers. A local minimum is still a number smaller than its
neighbour(s); however, an element now neighbours the four elements
above, below, to the left, and to the right. (On the edges and
corners, an element has fewer neighbours and so it's ``easier'' for it
to be a local minimum.)

\begin{enumerate}
\item Give an example of such a 2-dimensional array with $n=5$ and circle
   all the local minima.
\item Give an efficient algorithm to find a \textbf{local} minimum in such a
   2-dimensional array. (You may assume $n > 1$ if needed.)
   
   \textbf{HINT:} Consider the set of array elements down the two middle
   lines of the array, in this shape:
   
     \begin{tikzpicture}[thick]
       \draw [thin] (0,0) rectangle (2,2);
       \draw [ultra thick] (1,0) -- (1,2);
       \draw [ultra thick] (0,1) -- (2,1);
     \end{tikzpicture}   
   
   The smallest of these elements tells you something about where a
   local minimum might be. It will likely help to compare against your
   example!
\item Give and briefly justify a good asymptotic bound on the runtime of
   your algorithm.
\item Sketch the key points in a proof that your algorithm is
   correct. (It may help to note that in the inital array of $n$
   distinct numbers, there is always at least one local minumum
   because the global minimum is also guaranteed to be a local
   minimum.)
\end{enumerate}
%\clearpage
\section{No Chutes, Just Ladders}
\label{sec-4}

A children's game has $n$ spaces numbered $1, \ldots, n$. A game piece
can progress from one space to the next or---in certain spaces marked
with ladders---it can ``jump'' forward a fixed number of spaces.

You are given an array $A$ of the spaces on the board, where each
entry of $A$ is the set of spaces from which a piece can arrive at
that space. So, using 1-based indexing, $A[1] = \{\}$ because pieces
start at space 1 but cannot move to there from anywhere. For every
other index $i$ of a space, $i-1 \in A[i]$ because we can always
arrive at $i$ from space $i-1$. To illustrate ladders, if space $j$
had a ladder of length 3 and a ladder of length 7 leading to it, its
set would be $A[j] = \{j-1, j-3, j-7\}$.

Your goal is to count how many different ways there are to arrive at
the final space.

For example, consider this gameboard first as a graph:

\includegraphics[width=0.5\textwidth]{figures/ladders-dag.png}

and then as an array: $[\{\}, \{1\}, \{1,2\}, \{2,3\}, \{1,3,4\}]$.

There is only 1 way to reach node 2 (from node 1). There are 2 ways to
reach node 3 (via 2 or directly from 1). There are 3 ways to reach
node 4 (via nodes 2 and 3, via just node 2, or via just node 3). There
are 6 ways to reach the final space, node 5.

Design an efficient algorithm to count how many different ways there
are to arrive at the final space. Your algorithm may use linear time
and ``linear'' memory, where we assume that the count of ways to reach a
node can be stored in constant space.

\textbf{HINT:} Start by designing a recurrence $C(n)$ that describes the
number of ways to reach space $n$ in terms of the number of ways to
reach previous spaces on the board and in terms of $A[n]$ (the set of
spaces from which space $n$ is reachable). Then, either convert that
into a recursive solution and memoize it or convert that into a
dynamic programming solution.
%\clearpage

\end{document}