% Created 2017-09-17 Sun 10:08
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\usepackage{csquotes}
\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}
\usepackage{nopageno}
\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}
\newcommand{\marksamt}[1]{\textbf{[#1~marks]}}
\newcommand{\markamt}[1]{\textbf{[#1~mark]}}
\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}
\date{\today}
\title{CPSC 320 2017W1: Assignment 1}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs 25.2.1 (Org mode 8.2.10)}}
\begin{document}

\maketitle
Please submit this assignment via \href{https://gradescope.com/}{GradeScope} at
\url{https://gradescope.com}. Be sure to identify everyone in your group if
you're making a group submission (which we encourage!).

Submit by the deadline \textbf{Friday 22 Sep at 10PM}. For credit, your group
must make a \textbf{single} submission via one group member's account,
marking all other group members in that submission \textbf{using GradeScope's
interface}. Your group's submission \textbf{must}:
\begin{itemize}
\item Be on time.
\item Consist of a single, clearly legible file uploadable to GradeScope
with clearly indicated solutions to the problems. (PDFs produced via
\LaTeX{}, Word, Google Docs, or other editing software work
well. Scanned documents will likely work well. \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 quizzes). Put
these \textbf{in order} starting each problem on a new page, ideally. If
not, \textbf{very clearly} and prominently indicate which problem is
answered where!
\item Include at the start of the document the \textbf{ugrad.cs.ubc.ca e-mail
addresses} of each member of your team. (No names are necessary.)
\item Include at the start of the document the statement: "All group
members have read and followed the \href{http://blogs.ubc.ca/cpsc3202017W1/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 (and GradeScope information) 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 your outside-group
collaborators' ugrad.cs.ubc.ca e-mail addresses. (Be sure to get
those when you collaborate!)
\end{itemize}
\section{Looping Back to Asymptotic Analysis}
\label{sec-1}

\textbf{NOTE:} There are 8 blanks plus one \textbf{YES} or \textbf{NO} question to answer.

Each row of the table below lists a problem posed for an array of $n$
numbers. You are determining \textbf{good big-O bounds for the worst-case
performance} of efficient algorithms for each problem. In the \textbf{left
blank}, give a bound for an efficient algorithm if the \textbf{input array is
not known to be sorted}. In the \textbf{right blank}, give a bound for an
efficient algorithm if the \textbf{input array is known to be already
sorted}.

Each bound is one of: $O(1), O(\lg n), O(n), O(n \lg n), O(n^2)$.

Note: throughout this problem, assume basic operations on numbers take
constant time.


\begin{center}
\begin{tabular}{l|l|l|}
Problem & big-O bound (unordered) & big-O bound (known to be sorted)\\
\hline
 &  & \\
a. Find a given target value &  & \\
 &  & \\
\hline
 &  & \\
b. Find the maximum &  & \\
 &  & \\
\hline
 &  & \\
c. Find the largest absolute difference &  & \\
between any two values &  & \\
\hline
 &  & \\
d. Find the total of the absolute differences &  & \\
between each pair of values &  & \\
\hline
\end{tabular}
\end{center}

Finally, note that for some algorithms over arrays, even if the input
is not \textbf{known} to be sorted, sorted arrays are a common case worth
optimizing for.

A friend suggests that this is the case for finding the maximum of an
array of $n$ numbers. Is there a correct and efficient algorithm for
this problem that has an asymptotically better runtime in the case
where the input happens to be sorted than in the worst case? (Circle
the \textbf{best} answer.)

\medskip

Answer: \hfill \textbf{YES} \hfill \textbf{NO} \hfill \strut

\medskip
\subsection{For the assignment}
\label{sec-1-1}
In addition, for each of the 8 blanks, justify your answer by giving
(1) \textbf{brief, high-level pseudocode for an efficient algorithm for the
problem}, (2) \textbf{a brief description of the type of input that generates
the algorithm's worst case}, and (3) \textbf{a brief justification of why
your bound is appropriate for your algorithm/case}.

For the final \textbf{YES} or \textbf{NO} question, \textbf{briefly justify your answer}.

If you need to work with indexes, assume 0-based indexing, i.e., the
first element of an array $A$ of length $n$ is $A[0]$ while the last
is $A[n-1]$.
\section{Structural Engineering}
\label{sec-2}
\subsection{Choosing Your Structures}
\label{sec-2-1}
For each of the following, choose the data structure that
most efficiently supports a solution of: \textbf{stack}, \textbf{queue}, \textbf{pri q}
(priority queue implemented as a binary heap), and \textbf{dict}
(dictionary/map implemented as a hash table). Choose the \textbf{best} answer
in each case. If there are multiple best answers, just pick one.



\begin{enumerate}
\item Given a string $s$ containing only characters from the set \texttt{[},
\texttt{]}, \texttt{(}, \texttt{)}, \texttt{\{}, and \texttt{\}}, determine if $s$ is balanced. (If A is
balanced, then (A), \{A\}, and [A] are balanced. If A and B are
balanced, then AB is balanced. The empty string is balanced.)
$\underline{\phantom{XXXXXXXXXXXXX}}$

\item Given a string $s$, build a data structure that can be used to
rapidly find the number of times any character $c$ appears in $s$.
$\underline{\phantom{XXXXXXXXXXXXX}}$

\item Given a map of a cave (represented as a graph), a starting
location (a vertex), and a set of exits (vertices), find a path from
the start to an exit. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Given the same cave map inputs as above, find the path containing
the least number of passages (edges) from the start to an
exit. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Given the same cave map inputs as above plus a landmark (another
vertex), find the path containing the least number of passages
(edges) from the start to an exit and passing through the
landmark. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Given an array of integers and value k, find the kth largest
element of the array. $\underline{\phantom{XXXXXXXXXXXXX}}$
\end{enumerate}
\subsubsection{For the assignment}
\label{sec-2-1-1}
In addition, for each of the problems above, go back and justify your
answer briefly, including briefly describing the algorithm you would
implement using your chosen data structure.
\subsection{Knowing Your Structures}
\label{sec-2-2}
Each item below describes an operation on a tree data structure.
Choose the tightest worst-case running time for a good implementation
of the operation among: $O(1), O(\lg n), O(n), O(n \lg n), O(n^2)$.
$n$ represents the number of items (keys or key/data pairs) in the
structure. Note: BST is binary search tree.



\begin{enumerate}
\item Find the minimum key in an AVL tree. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Insert a key into a BST (not necessarily balanced). $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Find the largest key less than a given key in a balanced
BST. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Determine if a given BST satisfies the AVL balance
property. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Perform a level order traversal of a BST. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Build a minHeap from a given array of integers. $\underline{\phantom{XXXXXXXXXXXXX}}$

\item Sort the elements of an array in place using the heap sort algorithm. $\underline{\phantom{XXXXXXXXXXXXX}}$
\end{enumerate}
\subsubsection{For the assignment}
\label{sec-2-2-1}
In addition, for each problem above, please justify your bound by
giving (1) \textbf{brief, high-level pseudocode for an efficient algorithm
for the problem}, (2) \textbf{a brief description of the type of input that
generates the algorithm's worst case}, and (3) \textbf{a brief justification
of why your bound is appropriate for your algorithm/case}.

Note: If you feel the algorithm you'd use is a widely known, common
algorithm (like merge sort), just cite the algorithm in (1), but
you'll still need enough detail about how it works for the
justification in (3).
\section{Marriage Rites}
\label{sec-3}

Each of the following problems presents a SMP scenario (for the classic
stable marriage problem with $n$ men, $n$ women, and complete
preference lists) and a statement about that scenario. For each one,
indicate by writing the \textbf{bolded} word whether:
\begin{enumerate}
\item The statement is \textbf{ALWAYS} true, i.e., true in \emph{every} SMP instance
matching the scenario.
\item The statement is \textbf{SOMETIMES} true, i.e., true in some SMP instance
matching the scenario but also false in some such instance.
\item The statement is \textbf{NEVER} true, i.e., true in \emph{none} of the SMP instances
matching the scenario.
\end{enumerate}

Here are the problems:
\begin{enumerate}
\item \textbf{Scenario:} Any  SMP instance solved using Gale-Shapley
with women proposing. \textbf{Statement:} A man is unmarried in the
solution.

\medskip
Circle the \textbf{best} answer: \hfill \textbf{ALWAYS} \hfill \textbf{SOMETIMES} \hfill \textbf{NEVER} \hfill \strut
\medskip
\item \textbf{Scenario:} Any SMP instance with $n \geq 1$ solved using
Gale-Shapley with men proposing. \textbf{Statement:} A woman and man marry
each other, although each prefers someone else.

\medskip
Circle the \textbf{best} answer: \hfill \textbf{ALWAYS} \hfill \textbf{SOMETIMES} \hfill \textbf{NEVER} \hfill \strut
\medskip
\item \textbf{Scenario:} An SMP instance with $n \geq 2$. \textbf{Statement:} A stable
solution exists in which everyone gets their second choice partner.

\medskip
Circle the \textbf{best} answer: \hfill \textbf{ALWAYS} \hfill \textbf{SOMETIMES} \hfill \textbf{NEVER} \hfill \strut
\medskip
\item \textbf{Scenario:} Any SMP instance with $n \geq 1$ in which all the men
share the same preference list, solved using Gale-Shapley with women
proposing. \textbf{Statement:} At least one man gets his first choice in
the solution.

\medskip
Circle the \textbf{best} answer: \hfill \textbf{ALWAYS} \hfill \textbf{SOMETIMES} \hfill \textbf{NEVER} \hfill \strut
\medskip
\item \textbf{Scenario:} Any SMP instance solved using
Gale-Shapley. \textbf{Statement:} The loop in Gale-Shapley runs at least
$n$ times.

\medskip
Circle the \textbf{best} answer: \hfill \textbf{ALWAYS} \hfill \textbf{SOMETIMES} \hfill \textbf{NEVER} \hfill \strut
\medskip
\end{enumerate}
\subsection{For the assignment}
\label{sec-3-1}
In addition, for each of the problems above, please \textbf{briefly} justify your answer.

Justify an \textbf{ALWAYS} answer by giving a small instance that fits the
scenario for which the statement is true and then briefly sketching
the key points in a proof that the statement is true for all instances
that fit the scenario.

Justify a \textbf{NEVER} answer by giving a small instance that fits the
scenario for which the statement is \textbf{false} and then briefly sketching
the key points in a proof that the statement is \textbf{false} for all
instances that fit the scenario.

Justify a \textbf{SOMETIMES} answer by giving \textbf{two} small instances that fit
the scenario: one for which the statement is true and one for which
the statement is false.
\section{Jus de Pokemon a la Mariage}
\label{sec-4}

In a new Pokemon Go challenge, trainers (i.e., players) working as a
team want to catch Pokemon as rapidly as possible. We define the PGP
(Pokemon Go Proximity) problem as: Given $n$ trainers (and their
locations) and $n$ Pokemon (and their locations), assign each trainer
a Pokemon to catch such that the trainers are nearby their target
Pokemon.

\begin{enumerate}
\item Complete the following to make a sensible---if \textbf{not} necessarily optimal---reduction from PGP to SMP.

Note: (1) Assume that SMP allows ties in preference lists. (2) A
reduction from problem A to problem B (of the type that uses the
solver for B exactly once) is a way to transform any instance of A
into an instance of B such that the solution to the B instance can
be transformed into a solution to the original A instance
(including both "directions" of transformation but not including a
solver for B).

\textbf{Reduction:} Given an instance of PGP, produce an instance of SMP
as follows:

Each of the $n$ men is $\underline{\rule{0em}{1.5em}\phantom{MMMMMMMMMMM}}$.

Each of the $n$ women is $\underline{\rule{0em}{1.5em}\phantom{MMMMMMMMMMM}}$.

Construct the men's preference lists using the observation that a
man $m_i$ prefers woman $w_j$ to woman $w_k$ exactly when
$\underline{\rule{0em}{1.5em}\phantom{MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM}}$.

Generate women's preference lists similarly.

Then, given a solution to SMP, produce a solution to PGP by
$\underline{\rule{0em}{1.5em}\phantom{MMMMMMMMMMMMMMM}}$
$\underline{\rule{0em}{1.5em}\phantom{MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM}}$.

\item Sketch a \textbf{small, clear instance of PGP} for which
this reduction generates an optimal solution.

For this problem and the next: (1) Optimal means the total distance
travelled by trainers to their paired Pokemon is the minimum
possible for any pairing. (2) Use \textbf{X} for trainers and \textbf{O} for
Pokemon. (3) Your answer should be close in size to the
minimum-size correct answer. Significantly larger instances will
receive no credit. (4) There's plenty of room here for correct
solutions.

\bigskip
\vfill
\item Sketch a \textbf{small, clear instance of PGP} where this
reduction does \textbf{not} generate an optimal solution. (Read the notes
for the previous problem.)

\emph{Hint:} All trainers and Pokemon can sit on a single line. If you
feel your reduction is optimal, be aware we're dubious and then
sketch a proof of its optimality.

\bigskip
\vfill
\end{enumerate}
\subsection{For the assignment}
\label{sec-4-1}
In addition, briefly sketch a brute force approach to implementing the
reduction (not including the solution to the SMP instance, which can
just use G-S or some other SMP solver) and give/briefly justify a big-O
bound on the worst-case for this implementation.

Also, give the solution to your second instance found by the reduction
(briefly explaining how and why this is reached), give the solution to
that second instance that is optimal, and show that the optimal
solution has lower total distance than the reduction's solution.
% Emacs 25.2.1 (Org mode 8.2.10)
\end{document}