% -*- compile-command: "rubber -d hw.9.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace}
\usepackage[linesnumbered,ruled]{algorithm2e}
% \usepackage[left=.75in,top=.75in,right=.75in,bottom=.75in]{geometry}

\usepackage{qrcode, enumitem}

\pagestyle{fancy}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 9}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, April 14}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\section{A potpourri of pleasing problems}

\begin{question}
  Let $f : \mathbb{N} \to \mathrm{Bool}$ be a function that takes
  natural numbers as inputs and yields Boolean values as output.  We
  say $f$ is \emph{monotone} if there is some $k \in \mathbb{N}$ such
  that $f(n) = \mathrm{False}$ for all $n < k$ and $f(n) = \mathrm{True}$
  for all $n \geq k$.  In other words, $f$ starts out returning False, but as $n$
  gets bigger there comes some point when $f$ switches to returning
  True (and never switches back).  For example, the function $g(n) = n
  > 100$, which reports whether its input is greater than $100$, is
  monotone: it outputs False for all $n < 101$ and then switches to
  True for all $n \geq 101$.  As another example, consider the
  function $h(n)$ which reports whether or not $n \log_2 n > 3.6\times
  10^{13}$.  Clearly $h$ is monotone, since if some $n$ satisfies this
  inequality then everything larger than $n$ will also satisfy it; but
  unlike $g$, the critical value of $n$ where $h$ will switch from
  False to True is not \emph{a priori} obvious.

  Using pseudocode, describe an efficient algorithm which, given a
  monotone function $f$, returns the critical value $k \in \mathbb{N}$
  at which $f$ switches from False to True.  What is the running time
  of your algorithm in terms of $k$?
\end{question}

% \begin{question} \label{q:euler} An \emph{Euler tour} or \emph{Euler
%     circuit} of a graph $G$ is a cycle that visits every edge of $G$
%   exactly once. (An Euler tour is allowed to visit vertices multiple
%   times.)
% \begin{enumerate}[label=(\alph*)]
% \item Prove that a connected, undirected graph $G$ has an Euler
%   tour if and only if every vertex has even degree.
% \item \marginnote{\emph{\ref{q:euler}}\quad\qrcode{Take\ a\ walk.}}
%   Describe and analyze a linear time algorithm to compute an Euler
%   tour in a given graph, or correctly report that no such tour exists.
% \end{enumerate}
% \end{question}

\begin{question}
  Consider the problem of making change for $C$ cents using the fewest
  possible number of coins.  Assume that each coin's value is an
  integer.
\begin{enumerate}[label=(\alph*)]
\item Describe a greedy algorithm to make change for $C$ cents
  using US quarters, dimes, nickels, and pennies.  Prove that your
  algorithm yields an optimal solution.
\item Give a set of coin denominations for which the greedy
  algorithm does not yield an optimal solution.  Your set should
  include a penny so that there is a solution for every value of $C$.
\item Design and analyze an algorithm to make change using the fewest
  number of coins that works for any set of coins.  That is, as input
  your algorithm should take
  \begin{itemize}
  \item $n$, the number of different coin types;
  \item a list $c_1$, $c_2$, \dots, $c_n$ giving the values of the
    different coins (if you like, you may assume they are already
    sorted from smallest to largest); and
  \item the number of cents $C$ we would like to make change for.
  \end{itemize}
  As output your algorithm should either report that it is not
  possible to make the required amount $C$ using the given coins, or
  give a set of coins which add up to $C$ such that the number of
  coins in the set is as small as possible. For example, if given as
  input $c_1 = 1$, $c_2 = 5$, $c_3 = 20$ and the target value
  $C = 47$, your algorithm should output the set $\{20, 20, 5, 1, 1\}$.
  Note that we assume there is an unlimited supply of coins of each
  type.  Be sure to justify your algorithm's correctness and analyze
  its time complexity.
\end{enumerate}
\end{question}

\begin{question}
  Describe how to implement a queue using two stacks and $\Theta(1)$
  additional memory, so that the amortized time for any enqueue or
  dequeue operation is $\Theta(1)$. The \emph{only} access you have to
  the stacks is through the standard methods \textsc{Push} and
  \textsc{Pop}.  You may assume that \textsc{Push} and \textsc{Pop}
  take $\Theta(1)$ time in the worst case.
\end{question}

\begin{question} \label{q:longest}
  \marginnote[0.2in]{\emph{\ref{q:longest}}\quad\qrcode{Careful:\
      just\ because\ a\ cycle\ exists\ doesn't\ mean\ there\ are\
      arbitrarily\ long\ paths\ from\ s\ to\ t.}}  Let $G = (V,E)$ be
  a directed, weighted graph with positive edge weights, and let
  $s, t \in V$. Design and analyze an efficient algorithm to either
  find the length of the \textbf{longest} path from $s$ to $t$ in $G$,
  or report that paths from $s$ to $t$ can be arbitrarily long
  (because there is a cycle somewhere in the middle).
\end{question}

\end{document}



% \begin{question}
%   Suppose we can insert or delete an element into a hash table in
%   $O(1)$ time.  In order to ensure that our hash table is always big
%   enough, without wasting a lot of memory, we will use the following
%   global rebuilding rules:
%   \begin{itemize}
%   \item After an insertion, if the table is more than $3/4$ full, we
%     allocate a new table twice as big as our current table, insert
%     everything into the new table, and then free the old table.
%   \item After a deletion, if the table is less than $1/4$ full, we
%     allocate a new table half as big as our current table, insert
%     everything into the new table, and then free the old table.
%   \end{itemize}
%   Show that for any sequence of insertions and deletions, the
%   amortized time per operation is still
%   $O(1)$.\marginnote{\emph{Hint}: Do not use potential functions.}
% \end{question}
