% Created 2018-01-13 Sat 09:25
\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{graphicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{algpseudocode}
\usepackage[margin=0.75in]{geometry}
\usepackage{nth}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,shapes.misc,calc,arrows,patterns,decorations.pathreplacing}
\usepackage{ccicons}
\usepackage{calc}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{nopageno}
\usepackage{enumitem}
\usepackage{multicol}
\usepackage{braket}
\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}
\setlength{\columnseprule}{1pt}
\newcommand{\bonusmarksamt}[1]{\textbf{[#1~BONUS~marks]}}
\newcommand{\bonusmarkamt}[0]{\textbf{[1~BONUS~mark]}}
\newcommand{\marksamt}[1]{\textbf{[#1~marks]}}
\newcommand{\markamt}[0]{\textbf{[1~mark]}}
\newcommand{\fillinMC}[1]{\fillinMCmath{\mbox{#1}}}
\newcommand{\fillinMCmath}[1]{\begin{tikzpicture}\draw circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCsoln}[1]{\fillinMCmathsoln{\mbox{#1}}}
\newcommand{\fillinMCmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCAll}[1]{\fillinMCAllmath{\mbox{#1}}}
\newcommand{\fillinMCAllmath}[1]{\begin{tikzpicture}\draw (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinMCAllsoln}[1]{\fillinMCAllmathsoln{\mbox{#1}}}
\newcommand{\fillinMCAllmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinblank}[1]{\fillinblankmath{\mbox{#1}}}
\newcommand{\fillinblankmath}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{\LARGE\phantom{#1}}\endgroup}
\newcommand{\fillinblanksoln}[1]{\fillinblankmathsoln{\mbox{#1}}}
\newcommand{\fillinblankmathsoln}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{{#1}}\endgroup}
\newcommand{\answerbox}[1][3\baselineskip]{%
\noindent\setlength{\fboxrule}{2pt}\framebox[0.7\linewidth]{%
\raisebox{2pt}[0pt][#1]{}%
}\par\medskip%
}
\usepackage{collcell,array}
\newcommand{\shiftdown}[1]{\smash{\raisebox{-.5\normalbaselineskip}{#1}}}
\newcolumntype{C}{>{\collectcell\shiftdown}c<{\endcollectcell}}
\newcommand{\shiftup}[1]{\smash{\raisebox{.5\normalbaselineskip}{#1}}}
\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 2017W2: 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. (Reminder: groups can include a
maximum of three students; we strongly encourage groups of two.)

Submit by the deadline \textbf{Monday 22 Jan 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. (Please do \textbf{NOT} include
your name on the assignment, however.\footnote{If you don't mind private
  information being stored outside Canada and want an extra
  double-check on your identity, include your student number rather
  than your name.})
\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 IDs, but \textbf{not} their names. (Be sure
to get those IDs when you collaborate!)
\end{itemize}
\section{Looping Back to Asymptotic Analysis}
\label{sec-1}
Before we begin, a few notes on pseudocode throughout CPSC 320: Your
pseudocode need not compile in any language, but it must communicate
your algorithm clearly, concisely, correctly, and without irrelevant
detail. Reasonable use of plain English is fine in such
pseudocode. You should envision your audience as a capable CPSC 320
student unfamiliar with the problem you are solving. If you choose to
use actual code, note that you may \textbf{neither} include what we consider
to be irrelevant detail \textbf{nor} assume that we understand the particular
language you chose. (So, for example, do not write \texttt{\#include
<iostream>} at the start of your pseudocode, and avoid idiosyncratic
features of your language like Java's ternary (question-mark-colon)
operator.)

\medskip

In this problem, 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]$.

\medskip

Answer each of the following:
\begin{enumerate}
\item What common algorithm would you use to find "a given target value"
in an unordered array?
\item What common algorithm would you use to find "a given target value"
in a sorted array?
\item \textbf{NOT GRADED} (just for practice): Assume we are totalling the
values in the array (to find the average) and that the values are
integers. Assume that it takes $\Theta(\lg x)$ bits to represent an
integer $x$ and that the largest value in the array $m$ is big,
i.e., $n \leq m$. Give a good asymptotic big-O bound on the number
of bits needed to represent the total. \emph{Show your work.}
\item Complete the pseudocode function below for an algorithm that runs
in worst-case linear time and finds "a pair of values summing to a
given target value" in a sorted array. You may assume as a
precondition that such a pair must exist in the array.

\textbf{READ THE NEXT TWO PARTS} and ensure your algorithm will work
correctly with them.

\begin{verbatim}
// Given a sorted array A containing at least one pair of values
// v1 and v2 such that v1 + v2 = target, returns such a pair (v1, v2).
FindPair(A, target):
\end{verbatim}
\item Describe how if given a length $n$, you could produce an input
array \texttt{A} of that length and a target value \texttt{target} such that your
\texttt{FindPair} algorithm will run in constant time, independent of $n$.
\item \textbf{NOT GRADED} (just for practice): Describe how if given a length $n$, you could produce an input
array \texttt{A} of that length and a target value \texttt{target} such that your
\texttt{FindPair} algorithm will run $\Theta(n)$ time, i.e., describe
worst-case input to your algorithm.
\item Complete the pseudocode function below for an algorithm that runs
in worst-case linear time and finds "the three smallest values" in
an unordered array (of length $\ge$ 3). Your code \textbf{must} be trivial
to modify to find the 4, 5, 6, or any other constant number $c$
smallest values in the array.

\begin{verbatim}
// Return the three smallest values in A as (v1, v2, v3), where v1 
// is the smallest, v2 the 2nd smallest, and v3 the 3rd smallest.
FindSmallestThree(A):
\end{verbatim}
\item \textbf{NOT GRADED} (just for practice): Describe briefly in English a worst-case linear-time algorithm to
determine whether any value is repeated in a sorted array.
\item Briefly justify why no algorithm for finding the smallest three
elements in an unordered array can perform better in the case where
the input happens to be (but is not known to be) sorted.
\end{enumerate}
\section{All Tied Up}
\label{sec-2}
\textbf{Reminders:} STP is SMP except where ties are allowed in preference
lists.

A \emph{strong instability} in a perfect matching consists of a woman $w$
and a man $m$ such that $w$ and $m$ both (strictly) prefer each other
to their current partner.

A \emph{weak instability} in STP is one of:
\begin{itemize}
\item a strong instability (i.e., every strong instability is also a
weak instability),
\item a woman $w$ and man $m$ such that $w$ prefers $m$ to her partner
and $m$ is indifferent between $w$ and his partner, or
\item a man $m$ and woman $w$ such that $m$ prefers $w$ to his partner
and $w$ is indifferent between $m$ and her partner.
\end{itemize}

Now, solve these problems:
\begin{enumerate}
\item Give a good reduction from STP to SMP.

In particular, you should identify an algorithm \texttt{TransformInstance}
that takes an instance of SMP and transforms it into an instance of
SMP, an algorithm \texttt{TransformSolution} that transforms the solution
of such an SMP instance back into a solution to the original STP
instance. (You may assume \texttt{TransformSolution} has access to the
original STP instance and any data it needs from
\texttt{TransformInstance}.)

You're not supplying an algorithm to solve SMP. That's not part of
a reduction from STP to SMP!

\textbf{BE SURE} that your solution works for the next part.
\item Prove that your reduction (combined with an arbitrary
algorithm---which is \textbf{not} necessarily Gale-Shapley---that produces
stable SMP solutions) produces STP solutions with no strong
instabilities.

As is often the case, you will likely want to approach the proof
via the contrapositive: a strong instability in the STP solution
implies an instability in the SMP solution.
\item \textbf{NOT GRADED} (just for practice): Describe a way to create an STP instance of an arbitrary size $n$
   that has $n!$ solutions without strong instabilities.
\item \textbf{NOT GRADED} (just for practice): Give a \textbf{small} instance $I$ of STP and a solution $P$ to $I$ in
which: every woman is indifferent between $m_1$ and $m_2$; $m_1$
ranks $w_1$ first (tied with no one); $m_2$ ranks $w_1$ last (tied
with no one); $P$ has no strong instabilities; and $m_2$ marries
$w_1$ in $P$.
\item Give a \textbf{small} instance $I$ of STP for which every valid solution
has a weak instability. \textbf{Briefly} explain why every valid solution
has a weak instability.
\item We might try to modify the Gale-Shapley algorithm to alternate
proposals between men and women. Give a \textbf{small} instance $I$ of SMP
(\textbf{not} STP), trace a run of this modified Gale-Shapley algorithm on
it up to its solution, and identify an instability in that
solution.
\end{enumerate}
\section{To Re Mi Pa So Ti La Do!}
\label{sec-3}
Recall that a solution to a problem is \textbf{not} "strong Pareto optimal"
if a single step change to that solution can make at least one person
better off while making \emph{no one} worse off.

A solution to a problem is \textbf{not} "weak Pareto optimal" if a single
step change to that solution can make \textbf{everyone} better off.

We decided that a "single step" in SMP is to take any two married
pairs $(m, w)$ and $(m', w')$ and swap them to get the two married
pairs $(m, w')$ and $(m', w)$. "Better off" and "worse off" are
defined naturally in terms of the preference lists.

You may find it useful to say that a "good" step that makes a solution
not Pareto optimal is a "Pareto inefficiency". A "strong Pareto
inefficiency" is a single step that shows that the solution is not
"strong Pareto optimal". A "weak Pareto inefficiency" is such a step
for "weak Pareto optimality".

(Reminder: we're talking in this problem about standard SMP, not SMP
with ties, unequal numbers of men and women, or any other previously
discussed variant.)

Solve these problems under those definitions:
\begin{enumerate}
\item Consider the following scenario and statement. Indicate whether the
statement is \textbf{always}, \textbf{sometimes}, or \textbf{never} true in any
situation matching the scenario. Then, justify your answer as follows:
\begin{itemize}
\item 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.
\item 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.
\item 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.
\end{itemize}
\textbf{Scenario:} $P$ is a valid solution to SMP instance $I$ in which
four (different) people are in two married couples as follows $(m,
   w), (m', w')$.

\textbf{Statement:} A single step that swaps $(m, w)$ and $(m', w')$ makes
some but not all of the four people better off while making none of
the four worse off.
\item Prove that any solution to SMP that is stable is also strong Pareto
optimal. (You may want to use the contrapositive!)
\item \textbf{NOT GRADED} (just for practice): Give a \textbf{small} instance of SMP and a valid (but not necessarily
stable) solution to that instance that is \textbf{not} weak Pareto
optimal.
\item Briefly explain why for every instance of SMP with $n \geq 3$, any
valid solution is also weak Pareto optimal.
\end{enumerate}
\section{Knowing Your Structures}
\label{sec-4}
\begin{enumerate}
\item Complete the following algorithm with pseudocode to efficiently
find the successor key value of a key value present in a BST (not
necessarily an AVL) that does have a successor in the tree, given
the key value of the node and the root of the tree.

\begin{verbatim}
// precondition: key is present in the tree rooted at root,
//               and key has a successor also present in the tree
FindSuccessor(key, root):
\end{verbatim}

It will likely be helpful to also complete the following algorithm:

\begin{verbatim}
// precondition: the tree rooted at root is non-empty
// postcondition: produces the key with minimum value in the tree
FindMin(root):
\end{verbatim}
\item \textbf{NOT GRADED} (just for practice): The same code runs correctly on both a BST and an AVL to find the
successor. Briefly explain why it takes $O(\lg n)$ time in the
worst case on an AVL tree but not on a general BST.
\item \textbf{NOT GRADED} (just for practice): What key values present in the tree could you use for $k_1$ and
$k_2$ to get worst-case performance from an efficient algorithm
that counts the number of keys between $k_1$ and $k_2$ in a
balanced BST?
\item \textbf{NOT GRADED} (just for practice): Propose an additional variable (beyond the tree's size) that would
be useful to characterize the asymptotic performance of an
efficient algorithm that counts the number of keys between $k_1$
and $k_2$ in a balanced BST. \textbf{Briefly justify} your proposal.
\item Here is pseudocode to check if a binary tree is a maxHeap. (That
is, it has the heap order property. It need not have the heap shape
property.) The pseudocode only compares a given node's key against
its direct children's keys, not against all descendents'
keys. Either (a) clearly but concisely prove this pseudocode is
correct or (b) give and explain a counterexample to its
correctness.

\begin{verbatim}
// root is the root of a binary tree that may be empty
IsMaxHeap(root):
    if root is empty:
        return TRUE
    else:
        if root.left is not empty and root.left.key > root.key:
            return FALSE
        if root.right is not empty and root.right.key > root.key:
            return FALSE
        return IsMaxHeap(root.left) and IsMaxHeap(root.right)
\end{verbatim}
\item Give the runtime of an asymptotically efficient algorithm to find
the first 150 keys in an AVL tree (i.e., the 150 smallest keys) and
\textbf{briefly justify} your answer.
\end{enumerate}
\section{Choosing Your Structures}
\label{sec-5}
\textbf{Reminder:} We state below the data structure that most efficiently
supports a solution to several problems of the options: \textbf{array},
\textbf{stack}, \textbf{queue}, \textbf{priority queue} (implemented as a binary heap),
\textbf{balanced BST} (balanced binary search tree implemented as an AVL
tree) and \textbf{dictionary} (dictionary/map implemented as a hash
table).

\begin{enumerate}
\item \textbf{NOT GRADED} (just for practice): Determine the next collision that will happen in a game where balls are bouncing around
on a pool table. You may assume that a function to determine when two balls will collide
(assuming they do not change direction beforehand) has already been written.

\textbf{Priority queue}
\item Given a map of a cave (represented as a graph), a starting location (a vertex), and a
magic spell that will affect all locations within a given distance from the starting
location, determine which locations will be affected by the spell. Note that spells
do not penetrate walls.

\textbf{Queue}
\item Given the same cave map inputs as above, and a set of exits (vertices), 
find the path containing the least number of dangerous creatures from the start 
to an exit.

\textbf{Priority queue}
\item \textbf{NOT GRADED} (just for practice): You are building an interpreter for a version of the C language
that does not have pointers, and you need to keep track (by name)
of the current value of each global and local variable.

\textbf{Dictionary}
\item \textbf{NOT GRADED} (just for practice): You are a teaching assistant who is maintaining the current
projected final grades of the students in the course. The
projections are updated every time a new assigment, quiz or exam
grades becomes known (whether a single updated or a group of
simultaneous ones), and you want to be able to return efficiently a
list of all students whose projected final grade lies within a
given range (this range is not fixed, but varies with every query).

\textbf{Balanced binary search tree}
\item Given a string containing only lowercase alphabetic characters
(a--z), determine which character occurs the most often in the
string.

\textbf{Array}
\item \textbf{NOT GRADED} ("spoiled" below): Given a mathematical expression, determine if it is parenthesized properly. For
example, ``(((2+3)*5))'' is parenthesized properly, but ``(2+4)) + (5'' is not.

\textbf{Stack}
\end{enumerate}

Now, justify the answers briefly. Specifically: Give a high-level
description of an algorithm to solve the problem (pseudocode is
unnecessary for the level of detail we want) that includes an
explanation of how and why the correct data structure fits into the
algorithm.

For example, on the seventh problem (which you should not submit), we
might say:

\begin{quote}
Scan the string, pushing opening parentheses onto the stack. At each
closing parenthesis, ensure the stack is non-empty (or the string was
unbalanced) and pop. If the stack is empty at the end, the string was
balanced. The stack ensures we always compare the most recently
encountered, unbalanced opening parenthesis against the next closing
parenthesis.
\end{quote}

Side note: you could solve this problem with just a counter (increment
on open, decrement on close, fail if the counter is ever negative,
fail if the counter ends up positive\ldots{} essentially tracking only the
size of the stack). However, a wide variety of slight variations on
the problem (e.g., having two different types of brackets) makes a
stack appropriate.
\section{Tangling the Knot}
\label{sec-6}
Reminder: In the mentor/mentee problem (MMP), an instance is a set of
(at least two) people, each with two preference lists over everyone
but themselves: one ranking others as potential mentors, one ranking
them as potential mentees. A solution should make mentor/mentee pairs
so that each person has exactly one mentor and exactly one mentee.

\begin{enumerate}
\item A friend proposes solving MMP via the following reduction, assuming
each employee has a unique employee ID:
\begin{quote}
Create an SMP instance as follows: Let the set of men $M$ be the
first half of the employees by ID. Let the set of women $W$ be the
second half of the employees by ID. Let the preference lists of men
match the first half of employees' mentee preferences over the
second half of employees. Let the preference lists of women match
the second half of employees' mentor preferences over the first
half of employees.

Given a solution to the SMP instance, create the solution to MMP as
follows: For a pair $(m, w)$, let the "first-half" employee
corresponding to $m$ be a mentor to the "second-half" employee
corresponding to $w$ (the mentee).
\end{quote}

Give a small, \textbf{complete} instance of MMP such that this reduction
fails, and briefly explain how and why it fails.
\item \textbf{NOT GRADED} (just for practice): Follow these steps to establish that this reduction can produce an MMP solution in which some employee has no mentor:
\begin{enumerate}
\item Give a small, \textbf{complete} instance of MMP such that this reduction
succeeds.
\item Write out the SMP instance produced by the reduction.
\item Write out a stable solution to this SMP instance (arrived it however you like).
\item Write out the MMP solution produced by the reduction given this
stable solution to the SMP instance.
\item Identifiy an employee who received no mentor in the MMP
solution.
\end{enumerate}
\item \textbf{NOT GRADED} (just for practice): Prove that in any valid solution to an instance of MMP, there is a
path going from mentor to mentee in $P$ (i.e., from a person to the
person who is their mentee and then optionally continuing from that
person to their mentee and so on) that is a cycle (starts and ends
on the same person). (Hint: the Pigeonhole Principle can help you
make short work of this proof, but be sure you establish
specifically that some path starts and ends at the same person, not
just that the path \emph{contains} a cycle.)
\item A friend proposes solving MMP via this alternate reduction,
slightly different from the one you saw on the quiz:
\begin{quote}
Create an SMP instance as follows: Let the set of men $M$ be the
set of employees. Let the set of women $W$ be a second copy of the
set of employees. Let the preference list of each man $m_e$ (a copy
of employee $e$) match the \textbf{mentee} preference list of $e$ but with
$e$ themselves (as the copy $w_e$ of $e$) added to the end of the
list. Similarly let the preference lists of women match the
employees' \textbf{mentor} preferences but with each employee added to the
end of their own preference list.

Given a solution to the SMP instance, create the solution to MMP as
follows: For a pair $(m, w)$, let the employee corresponding to $m$
be a mentor to the employee corresponding to $w$ (the mentee).
\end{quote}

Now, follow these steps to establish that this reduction can
produce an MMP solution in which some employee is their own mentor:
\begin{enumerate}
\item Give a small, \textbf{complete} instance of MMP such that this reduction
succeeds.
\item Write out the SMP instance produced by the reduction.
\item Write out a stable solution to this SMP instance (arrived it
however you like).
\item Write out the MMP solution produced by the reduction given this
stable solution to the SMP instance.
\item Identifiy an employee who received themselves as mentor in the
MMP solution.
\end{enumerate}
\item Prove that using the reduction from the previous problem, no two
employees can both be assigned themselves as mentors. (You may not
\textbf{assume} that in SMP no two people can both receive their last
choices on their preference lists, although this is true. You can
prove it and then use the fact if you like, but there's an easier
and shorter proof!)
\item For one \textbf{COURSE BONUS POINT}, write a \textbf{short}, \textbf{clear}, \textbf{correct}
proof that no two women can both receive their least-preferred
partner in any stable solution to any SMP instance.

\textbf{WARNING:} We'll be rapid and harsh in grading these (e.g., if an
answer is too long for our liking, we won't read it; if an answer
makes an irrelevant or false statement, we won't read further), and
it doesn't affect your assignment grade. So, skip it unless you
have time and motivation on your hands.
\end{enumerate}
% Emacs 25.2.1 (Org mode 8.2.10)
\end{document}