% Created 2017-10-18 Wed 15:43
\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{algpseudocode}
\usepackage[margin=0.75in]{geometry}
\usepackage{nth}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,calc,arrows}
\usepackage{ccicons}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{nopageno}
\usepackage{enumitem}
\usepackage{multicol}
\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{\fillinMCAll}[1]{\fillinMCAllmath{\mbox{#1}}}
\newcommand{\fillinMCAllmath}[1]{\begin{tikzpicture}\draw (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{\answerbox}[1][3\baselineskip]{%
\noindent\setlength{\fboxrule}{2pt}\framebox[0.7\linewidth]{%
\raisebox{2pt}[0pt][#1]{}%
}\par\medskip%
}
\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 3}
\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 27 Oct 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}
\clearpage
\section{eXtreme True And/Or False}
\label{sec-1}
\textbf{Pre-Reading: The Very Busy 3-D Printer}

The CS department buys a single 3-D printer and wants to develop a
scheduling algorithm for it. We'll call their problem the Very Busy
3-D Printer Problem or VB3.

The input for a particular week is a list of $n$ jobs for the
printer. Each job is a pair of a positive integer duration $t$ of the
job and non-negative integer deadline $d$ for the job. Once started, a
job must be run to completion, which takes $t$ minutes. To be useful,
the job must be complete by the deadline $d$ (also in minutes from the
start of the week).

The output is a schedule: a list of $k \leq n$ of the jobs along with
a non-negative integer start time $s$ for each one, sorted in
increasing order of start time. A valid schedule must ensure that no
two jobs overlap (i.e., no jobs $i$ and $j$ exist in the schedule such
that $s_i \leq s_j$ and $s_i + t_i > s_j$) and all jobs finish on time
($s_i + t_i \leq d_i$). Note that it is OK for a job's end time to
match the next job's start time. The goal is to schedule as many of
the jobs as possible.

For example, the input $(2, 5), (1, 3), (3, 4), (5, 15)$ represents
four jobs. The first is of length 2 minutes with a deadline 5 minutes
from the "zero" time. The second job is only 1 minute long and has a
deadline 3 minutes after the zero time. Etc.

The optimal solution to this instance includes three of the four
jobs. One option---represented with tuples of $(s, t, d)$ start time,
duration, and deadline---would be $(0, 2, 5), (2, 1, 3), (8, 5,
15)$. That runs the 2 minute job right away, followed by the one
minute job. Then, at minute 8, it runs the 5 minute job. This would
also be an optimal schedule with different jobs and timing: $(0, 1,
3), (1, 3, 4), (4, 5, 15)$.

\clearpage

\textbf{FILL IN YOUR UGRAD ID} and read the problem statement on the previous
page (relevant for all but the first part). Then, follow the
directions on this page.

Each of the following problems presents a scenario and a statement
about that scenario. For each one, indicate by filling in the
appropriate circle whether:
\begin{itemize}
\item The statement is \textbf{ALWAYS} true, i.e., true in \emph{every} instance
matching the scenario.
\item The statement is \textbf{SOMETIMES} true, i.e., true in some 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
instances matching the scenario.
\end{itemize}
Problems:
\begin{enumerate}
\item \textbf{Scenario:} A simple graph with $n \geq 3$. \textbf{Statement:} Any simple
path that starts at an arbitrary vertex $v$ and ends at an
arbitrary vertex $u \neq v$ can be extended into a simple cycle by
adding vertices after $u$.

$\fillinMC{ALWAYS}$

$\fillinMC{SOMETIMES}$

$\fillinMC{NEVER}$

\item \textbf{Scenario:} An instance of VB3 with $n \geq 2$. \textbf{Statement:} An
optimal schedule $((s_1, t_1, d_1), \ldots)$ exists in which $s_1 =
   0$ and for each subsequent pair of jobs in the schedule $i$ and
$i+1$, $s_i + t_i = s_{i+1}$.

$\fillinMC{ALWAYS}$

$\fillinMC{SOMETIMES}$

$\fillinMC{NEVER}$

\item \textbf{Scenario:} An instance of VB3 with $n \geq 1$. \textbf{Statement:} The
job $i$ with the maximum value of $d_i - t_i$ is in some optimal
solution to the instance.

$\fillinMC{ALWAYS}$

$\fillinMC{SOMETIMES}$

$\fillinMC{NEVER}$

\item \textbf{Scenario:} An instance of VB3 with $n \geq 1$. \textbf{Statement:} This
greedy algorithm produces an optimal solution to the instance:
Begin with an empty schedule and time marker $m = 0$. In increasing
order of job duration: if the next job $i$ can be finished in time
($m + t_i \leq d_i$), add it to the schedule with start time $m$
and then increase $m$ by $t_i$.

$\fillinMC{ALWAYS}$

$\fillinMC{SOMETIMES}$

$\fillinMC{NEVER}$

\item \textbf{Scenario:} An instance of VB3 with $n \geq 1$ and with an optimal
solution containing at least one job. \textbf{Statement:} This greedy
algorithm produces an optimal solution to the instance: Begin with
an empty schedule and time marker $m = 0$. In increasing order of
job deadline: if the next job $i$ can be finished in time ($m + t_i
   \leq d_i$), add it to the schedule with start time $m$ and then
increase $m$ by $t_i$.

$\fillinMC{ALWAYS}$

$\fillinMC{SOMETIMES}$

$\fillinMC{NEVER}$
\end{enumerate}

\clearpage
\subsection{Quiz Solution}
\label{sec-1-1}
\begin{enumerate}
\item \textbf{SOMETIMES}
\item \textbf{ALWAYS}
\item \textbf{ALWAYS}
\item \textbf{SOMETIMES}
\item \textbf{SOMETIMES}
\end{enumerate}
\subsection{Assignment}
\label{sec-1-2}
On the assignment, for each of the problems above, please \textbf{briefly}
justify the 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.

\textbf{IMPORTANT CAUTION:} None of your example instances should critically
rely on tie-breaking behaviour to illustrate what they are meant to
show. \textbf{Ensure} that you briefly explain why each instance fits the
scenario and makes the statement true or false, as needed.
\section{Bestride the BST}
\label{sec-2}
We define a size-weighted BST (wBST) to be a binary search tree in
which each node also has a weight: a count of the number of nodes in
the subtree rooted at that node. A leaf (a single node with empty
subtrees) has weight 1, a node with only one subtree which is itself a
leaf has weight 2, a node with two leaves as subtrees has weight 3,
etc.

The following binary tree is labelled with its weights (but omits the
keys and values that would be in each node of a full wBST):

\includegraphics[width=0.6\textwidth]{figures/2017W1-a3-wBT.png}

\clearpage

\textbf{FILL IN YOUR UGRAD ID} and read the definition on the previous
page. Then, consider the following pseudocode for correcting a wBST's
weights:
\begin{verbatim}
// A node has four fields: key, value, weight, and subtrees left and right.
// The only field of the special value EMPTY representing empty trees is EMPTY.weight = 0.
// (So, for a wBST b, b.weight will not produce an error, even if b is an empty tree.)
function WeightBST(root):
    if root != EMPTY:
        WeightBST(root.left)
        WeightBST(root.right)
        root.weight = root.left.weight + root.right.weight
\end{verbatim}
\begin{enumerate}
\item There is a single, small error in the code above; fix it.

\item After you have corrected it, a proof of correctness of this
algorithm would proceed by induction. This problem and the next two ask about such a proof.

Which of these would be the type of tree to use for the base case
in the proof? Fill in the circle next to the \textbf{best} answer.

\begin{tabular}{l}
$\fillinMC{an incorrectly weighted tree}$\\
$\fillinMC{a correctly weighted tree}$\\
$\fillinMC{an empty tree}$\\
$\fillinMC{a single leaf node}$\\
$\fillinMC{a tree one node smaller than the current one}$\\
$\fillinMC{the two subtrees of the current tree}$\\
\end{tabular}
\vfill
\item Your induction hypothesis will assume a property applies to a
particular type of tree. Which of these best describes the \emph{type of
tree} on which you make the induction hypothesis?  Fill in the
circle next to the \textbf{best} answer.

\begin{tabular}{l}
$\fillinMC{an incorrectly weighted tree}$\\
$\fillinMC{a correctly weighted tree}$\\
$\fillinMC{an empty tree}$\\
$\fillinMC{a single leaf node}$\\
$\fillinMC{a tree one node smaller than the current one}$\\
$\fillinMC{the two subtrees of the current tree}$\\
\end{tabular}
\vfill
\item Your induction hypothesis will assume a property applies to a
particular type of tree. Which of these best describes the
\emph{property} you will assume true for the type of tree you chose in
the previous part?  Fill in the circle next to the \textbf{best} answer.

\begin{tabular}{l}
$\fillinMC{it is weighted correctly}$\\
$\fillinMC{it is weighted incorrectly}$\\
$\fillinMC{it is an empty tree}$\\
$\fillinMC{it has a single leaf node}$\\
$\fillinMC{it has one fewer nodes than the current tree}$\\
$\fillinMC{it is a subtree of the current tree}$\\
\end{tabular}
\clearpage
\item Fill in the circle next to the best asymptotic bound on the
runtime of this algorithm in terms of the number of nodes in the
tree $n$.

\begin{tabular}{l}
$\fillinMCmath{O(1)}$\\
$\fillinMCmath{O(\lg n)}$\\
$\fillinMCmath{O(n)}$\\
$\fillinMCmath{O(n \lg n)}$\\
$\fillinMCmath{O(n^2)}$\\
\end{tabular}

\item Fill in the blanks to correctly and efficiently complete the
following code to count the number of keys in a (correctly
weighted) wBST \texttt{root} that are strictly larger than the target
value \texttt{lo}. (As is usual, no duplicate keys appear in the tree.)

\begin{algorithmic}
\Procedure{CountLarger}{root, lo}
  \If {root is EMPTY}
    \State \Return 0
  \ElsIf {root.key $<$ lo}
    \State \Return \fillinblankmath{MMMMMMMMMMMMMMMMMMMMMMMMM}
  \ElsIf {root.key $=$ lo}
    \State \Return \fillinblankmath{MMMMMMMMMMMMMMMMMMMMMMMMM}
  \Else % \Comment{root.key $>$ lo}
    \State \Return \fillinblankmath{MMMMMMMMMMMMMMMMMMMMMMMMM}
  \EndIf
\EndProcedure
\end{algorithmic}
\end{enumerate}
\subsection{Quiz Solution}
\label{sec-2-1}
\begin{enumerate}
\item Change the root weight calculation to \texttt{root.weight =
   root.left.weight + root.right.weight + 1}.
\item an empty tree
\item the two subtrees of the current tree
\item it is weighted correctly
\item $O(n)$
\item No solution provided at this time.
\end{enumerate}
\subsection{Assignment}
\label{sec-2-2}
Note: For the proofs in this section, we will grade based on:
\begin{itemize}
\item A clear, correct, easily readable proof structure, which allows us
to put our attention on individual parts of the proof. The structure
must reflect both an understanding of induction and of the key
features of the algorithms, recurrences, and properties being
proven.
\item Clear, concise, correct, and easily readable arguments in each
section of the proof.
\end{itemize}
Now, solve the following:
\begin{enumerate}
\item Prove the correctness of the algorithm after the correction from
the quiz solution.

Specifically, prove that after the call to \texttt{WeightBST} on \texttt{root}
completes, for each node and empty tree \texttt{v} in the subtree rooted
at \texttt{root} the number of nodes in the subtree rooted at \texttt{v} is
exactly \texttt{v.weight}.
\item Create a recurrence relation $T_W(n)$ describing the time taken by
the \texttt{WeightBST} algorithm called on a wBST with $n$ nodes. (You
don't know the structure of the wBST; so, assume for the recursive
case that the left subtree has $k$ nodes.)
\item Prove inductively that $T_W(n) \leq cn + d$ for appropriate
constants $c$ and $d$.
\item Complete the \texttt{CountLarger} function so that it runs in $O(h)$ time
on a tree with height $h$.
\item Prove the correctness of \texttt{CountLarger} by induction.
\item Write pseudocode for a short, clear, and efficient function
\texttt{CountRange(root, lo, hi)} that counts the number of nodes in the
correctly-weighted wBST \texttt{root} with keys $k$ such that $lo < k \leq
   hi$. Make use of \texttt{WeightBST} or \texttt{CountLarger} as needed.
\end{enumerate}
\section{Preparing for Sasquatch (Part 1)}
\label{sec-3}
Every year, on Memorial Day weekend, the Gorge Amphitheater in
Washington hosts the \href{https://www.sasquatchfestival.com}{Sasquatch! Music Festival}. Tickets are expensive,
so if you go it's imperative to maximize your musical pleasure by
attending as many performances as you can. Luckily, you're enrolled in
cpsc320, which makes you an expert in festival planning!

A \emph{performance} is represented by a pair $(s,f)$ where $s$ is its
start time and $f$ is its finish time (relative to the start of the
festival). There are $n$ performances over the three days, hosted
across many stages. Your goal is to maximize the number of
non-overlapping performances in your festival itinerary.

In each of the following greedy algorithms, answer "Yes" if the
algorithm \emph{always} constructs an optimal schedule, and answer "No"
otherwise.

\begin{tabular}{rlll}
 & Yes & No & Algorithm:\\
\hline
1 & $\fillinMC{}$ & $\fillinMC{}$ & Choose the performance $p$ that ends last, discard all performances that conflict with $p$,\\
 &  &  & and recurse on the remaining performances.\\
2 & $\fillinMC{}$ & $\fillinMC{}$ & Choose the performance $p$ that starts last, discard all performances that conflict with $p$,\\
 &  &  & and recurse on the remaining performances.\\
3 & $\fillinMC{}$ & $\fillinMC{}$ & Choose the performance $p$ with shortest duration $(f - s)$, discard all performances that\\
 &  &  & conflict with $p$, and recurse on the remaining performances.\\
4 & $\fillinMC{}$ & $\fillinMC{}$ & Choose a performance $p$ that conflicts with the fewest other performances, discard all\\
 &  &  & performances that conflict with $p$, and recurse on the remaining performances.\\
5 & $\fillinMC{}$ & $\fillinMC{}$ & If no performances conflict, choose them all. Otherwise, discard a performance that\\
 &  &  & conflicts with the most other performances and recurse on the remaining performances.\\
6 & $\fillinMC{}$ & $\fillinMC{}$ & If any performance $p$ completely contains another performance, discard $p$ and recurse.\\
 &  &  & Otherwise, choose the performance $q$ that ends first, discard all performances that canflict\\
 &  &  & with $q$, and recurse on the remaining performances.\\
\end{tabular}
\subsection{Quiz Solution}
\label{sec-3-1}
\begin{enumerate}
\item NO
\item YES
\item NO
\item NO
\item NO
\item YES
\end{enumerate}
\subsection{Assignment}
\label{sec-3-2}
\begin{enumerate}
\item Prove that each of the answers above is correct.

For a "No" answer: give a small instance (counterexample to the
algorithm's correctness) where the greedy algorithm described fails
to achieve an optimal solution. Be sure to briefly explain the
optimal solution and the lower-valued solution found by the greedy
algorithm. Your counterexample should \textbf{not} critically rely on
tie-breaking behaviour of the algorithm to illustrate what it is
meant to show.

For a "Yes", prove your result. (Neither proof requires an exchange
argument if you can think of a useful reduction.)

Reminder, you are giving in order:
\begin{enumerate}
\item Counterexample
\item Proof
\item Counterexample
\item Counterexample
\item Counterexample
\item Proof
\end{enumerate}
\item Suppose the organizers of the festival would like to schedule a set
of times where things like raffle winners, camping rules, and
merchandise tent hours could be announced to all the festival
attendees. To do this, a broadcast is made simultaneously to every
performance occurring at the time of the announcement. Describe and
analyze a greedy algorithm to find the smallest set of broadcast
times required to assure that every performance has at least one
announcement.
\begin{enumerate}
\item Give 3 different trivial instances.
\item Give all of the meaningfully distinct instances for $n=2$ performances.
\item Write pseudocode for a greedy algorithm to solve this
problem. (As a simplifying hint, it's ok for announcements to be
made exactly when a performance begins or ends.)
\item Prove that your greedy algorithm finds an optimal solution.
\end{enumerate}
\end{enumerate}

(Thanks to \url{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf} for the great problems.)
\section{Preparing for Sasquatch (Part 2)}
\label{sec-4}
Suppose there are $n$ candidates running for a public office, and that
voting has provided a tally that indicates, between any pair of
candidates, which one is preferred. This is very naturally modeled as
a directed graph with $n$ vertices, and exactly one directed edge
between every pair of vertices: $G=(V,E)$, with $V = {c_1, \ldots,
c_n}$ and $\forall u,v\in V$ either $(u,v)\in E$, or $(v,u)\in E$, but
not both. Such a graph is called a \emph{tournament}.

A \emph{ranking} is a permutation of candidates $c_{(1)}\ldots c_{(n)}$ so
that edge $(c_{(i)},c_{(i+1)})\in E$ for all $1\leq i < n$. In this
problem we will show that a ranking always exists, \emph{even if there are
cycles in the original graph}. (An alternative way of representing the
solution is a simple directed path through all the vertices.)

Here's an example of a tournament of size $n=4$ with a ranking in bold:
\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (1) {$c_{(1)}$};
    \node[main node] (4) [right of =1] {$c_{(2)}$};
    \node[main node] (2) [right of=4] {$c_{(3)}$};

    \node[main node] (3) [right of =2] {$c_{(4)}$};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge [line width=2.8pt] node {} (4)
          edge [bend left] node  {} (2)
    (2) edge[line width=2.8pt] node  {} (3)
    (3) edge[bend left] node  {} (1)
    (4) edge [bend left]node  {} (3)
         edge[line width=2.8pt] node  {} (2);
    
\end{tikzpicture}\]

The actual names of the candidates (or the labels on the vertices), do
not matter in this problem.

A proof that a ranking is always possible in a tournament would
proceed by induction. These questions are designed to help you gather
your thoughts for completing that proof.

\begin{enumerate}
\item (We're doing this one for you!) There is only one instance for
$n=2$, drawn here:
\[\begin{tikzpicture}[every path/.style={>=latex},every node/.style={draw,circle}]
  \node            (a) at (0,0)  { $c_{(1)}$ };
  \node            (b) at (2,0)  { $c_{(2)}$ };
  \draw[->] (a) edge (b);
\end{tikzpicture}\]
\vspace{0.25in}
\item Draw \emph{all} instances for $n=3$: \answerbox[5\baselineskip]

\vspace{0.25in}
\item In each of the size $3$ instances in the previous part, clearly
indicate a ranking by drawing a dotted line along the directed path
through all the vertices.

\vspace{0.25in}
\item Consider an arbitrary tournament of size $n$. An appropriate
inductive hypothesis would apply to
$\underline{\phantom{~~~~~~~~~~~~~~~~~~}}$.

\begin{tabular}{l}
$\fillinMCmath{\mbox{a tournament of size } \frac{n}{2}}$\\
$\fillinMCmath{\mbox{a directed, acyclic graph of size } n}$\\
$\fillinMCmath{\mbox{a tournament of size } n-1}$\\
$\fillinMCmath{\mbox{a DFS tree of } n-1 \mbox{ edges}}$\\
$\fillinMCmath{\mbox{a directed acyclic graph of size } \frac{n}{2}}$\\
$\fillinMC{a partition of the tournament into 3 subgraphs}$\\
\end{tabular}
\vspace{0.25in}
\item The inductive hypothesis would conclude by saying the structure you
specified in the previous part has a
$\underline{\phantom{~~~~~~~~~~~~~~~~~~}}$.

\begin{tabular}{l}
$\fillinMC{tournament}$\\
$\fillinMC{ranking}$\\
$\fillinMC{champion}$\\
$\fillinMC{tree of shortest paths}$\\
$\fillinMC{vertex whose out degree is 0}$\\
$\fillinMCmath{\mbox{directed acyclic graph of size } \frac{n}{2}}$\\
\end{tabular}

\vspace{0.25in}
\item Suppose you have a tournament of size $m$ and you add a new vertex
$v$, together with edges from $v$ \emph{to} each of the vertices in the
tournament. Can you add the new vertex to the ranking? If so,
where? If not, why not? (Choose the best answer to these
questions.)

\begin{tabular}{l}
$\fillinMC{Yes, anywhere!}$\\
$\fillinMC{Yes, in position 1.}$\\
$\fillinMCmath{\mbox{Yes, in position } m+1.}$\\
$\fillinMC{Maybe, depending on the structure of the existing tournament.}$\\
$\fillinMC{No, because the new vertex must have both an incoming and an outgoing edge.}$\\
\end{tabular}

\vspace{0.25in}
\item Suppose you have a tournament of size $m$ and you add a new vertex
$v$, together with edges \emph{from} each of the vertices in the
tournament to $v$. Can you add the new vertex to the ranking? If
so, where? If not, why not? (Choose the best answer to these
questions.)

\begin{tabular}{l}
$\fillinMC{Yes, anywhere!}$\\
$\fillinMC{Yes, in position 1.}$\\
$\fillinMCmath{\mbox{Yes, in position } m+1.}$\\
$\fillinMC{Maybe, depending on the structure of the existing tournament.}$\\
$\fillinMC{No, because the new vertex must have both an incoming and an outgoing edge.}$\\
\end{tabular}
\end{enumerate}
\subsection{Quiz Solution}
\label{sec-4-1}
\begin{enumerate}
\item Given above.
\item Here are the only two meaningfully different instances. Any other
instance is just a renaming of these (and remember that the vertex
labels don't matter).

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (1) {$c_{(1)}$};
    \node[main node] (4) [right of =1] {$c_{(2)}$};
    \node[main node] (2) [right of=4] {$c_{(3)}$};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge [line width=2.8pt] node {} (4)
          edge [bend left] node  {} (2)
    (4) edge[line width=2.8pt] node  {} (2);
\end{tikzpicture}

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (1) {$c_{(1)}$};
    \node[main node] (4) [right of =1] {$c_{(2)}$};
    \node[main node] (2) [right of=4] {$c_{(3)}$};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge [line width=2.8pt] node {} (4)
    (2) edge [bend left] node  {} (1)
    (4) edge[line width=2.8pt] node  {} (2);
\end{tikzpicture}
\item See above.
\item a tournament of size $n-1$
\item ranking
\item yes in position $1$
\item yes in position $m+1$
\end{enumerate}
\subsection{Assignment}
\label{sec-4-2}
\begin{enumerate}
\item To further prepare for your inductive argument, make a sketch
representing the ranking for a tournament of size $n-1$, and
consider an $n^{th}$ vertex. Under what condition can it be
inserted into position 1? Under what condition can it be inserted
into the middle of the existing chain? Under what condition can it
be inserted into position $n$? Must one of those conditions exist?
\item Assemble the answers from the quiz and the exploration in the
previous part into a complete proof that, for any $n$, a tournament
of size $n$ always has a ranking.
\item Use the insights from your proof to design (and give in
pseudocode!)  an algorithm for finding a ranking, given a
tournament.
\item Give and briefly justify a good big-$O$ bound on the running time
of the algorithm in the previous part in terms of the number of
vertices $n$ in the graph.
\end{enumerate}
% Emacs 25.2.1 (Org mode 8.2.10)
\end{document}