% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.

\documentclass[12pt,addpoints,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CSCE629 Analysis of Algorithms}
\def\term{Texas A\&M U, Fall 2019}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { \hfill \large{\course} \hfill }
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill \textbf{#5}  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { \term \hfill \emph{#2}}
       \hbox to 5.78in { {#3 \hfill \emph{#4}}}
      }
   }
   \end{center}
   \vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}

%-----defs and commands-----%
%\def\mG{[\textbf{G}]\xspace}
\def\veps{\varepsilon}
\newcommand{\bit}{\{0,1\}}
\newcommand{\negl}{\text{negl}}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
\newcommand{\alg}[1]{\textsf{#1}}
%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
\studenttrue 
% \studentfalse

\def\hwnum{7}
\def\issuedate{10/19/19}
\def\duedate{10am, 10/25/19} % 
\def\yourname{your name} % put your name here
%------------------------------%

\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi

\noindent \textbf{Instructions.}

\begin{itemize} 
\item Typeset your submission by \LaTeX, and submit in PDF
  format. Your solutions will be graded on \emph{correctness} and
  \emph{clarity}. You should only submit work that you believe to be
  correct, and you will get significantly more partial credit if you
  clearly identify the gap(s) in your solution. You may opt for the
  ``I’ll take 15\%'' option.
\item You may collaborate with others on this problem set.  However,
  you must \textbf{{write up your own solutions}} and \textbf{{list
      your collaborators and any external sources}} for each
  problem. Be ready to explain your solutions orally to a course staff
  if asked.
\item For problems that require you to provide an algorithm, you must
  give a precise description of the algorithm, together with a proof
  of correctness and an analysis of its running time. You may use
  algorithms from class as subroutines. You may also use any facts
  that we proved in class or from the book.
\item \textbf{If you describe a Greedy algorithm, you will get no
    credit without a formal proof of correctness, even if your
    algorithm is correct.}
\end{itemize}

\noindent This assignment contains \numquestions\ questions,
\numpages\ pages for the total of \numpoints \ points and
\numbonuspoints\ bonus points. A random subset of the problems will be
graded. \medskip

\newpage
\begin{questions}
  \question (Burrito-Delivery) You’ve just accepted a job from Elon
  Musk, delivering burritos from San Francisco to Houston. You get to
  drive a Burrito-Delivery Vehicle through Elon’s new
  \emph{Transcontinental Underground Burrito-Delivery Tube}, which
  runs in a direct line between these two cities. Your
  Burrito-Delivery Vehicle runs on single-use batteries, which must be
  replaced after at most 100 miles. The actual fuel is virtually free,
  but the batteries are expensive and fragile, and therefore must be
  installed only by official members of the Transcontinental
  Underground Burrito-Delivery Vehicle Battery-Replacement
  Technicians’ Union. Thus, even if you replace your battery early,
  you must still pay full price for each new battery to be
  installed. Moreover, your Vehicle is too small to carry more than
  one battery at a time.

  There are several fueling stations along the Tube; each station
  charges a different price for installing a new battery. Before you
  start your trip, you carefully print the Wikipedia page listing the
  locations and prices of every fueling station along the Tube. Given
  this information, how do you decide the best places to stop for
  fuel?

  More formally, suppose you are given two arrays $D[1,\ldots,n]$ and
  $C[1,\ldots,n]$, where $D[i]$ is the distance from the start of the
  Tube to the $i$th station, and $C[i]$ is the cost to replace your
  battery at the $i$th station. Assume that your trip starts and ends
  at fueling stations (so $D[1] = 0$ and $D[n]$ is the total length of
  your trip), and that your car starts with an empty battery (so you
  must install a new battery at station 1).
  \begin{parts}
    \part[10] Describe and analyze a greedy algorithm to find the
    \emph{minimum number} of refueling stops needed to complete your
    trip. Don’t forget to prove that your algorithm is correct.

    \part[10] But what you really want to minimize is the \emph{total
      cost} of travel. Show that your greedy algorithm in part (a)
    does not produce an optimal solution when extended to this
    setting.
    
    \bonuspart[5] Sketch an efficient algorithm to compute the
    locations of the fuel stations you should stop at to minimize the
    total cost of travel. You can use any algorithm we've discussed so
    far.
  \end{parts}
  

\newpage 
\question (Minimum spanning tree) This question explores the
uniqueness of MST.

  \begin{parts}
  \part[10] Prove \corr{or disprove (both directions)} that an
    edge-weighted graph $G$ has a unique minimum spanning tree
    \emph{if and only if} the following conditions hold:
    \begin{itemize}
    \item For any partition of the vertices of $G$ into two subsets,
      the minimum weight edge with one endpoint in each subset is
      unique.
    \item The maximum-weight edge in any cycle of $G$ is unique.
    \end{itemize}
    \part[10] Describe and analyze an algorithm to determine whether or
    not a graph has a unique minimum spanning tree.
  \end{parts}

\newpage 
\question Suppose we are maintaining a data structure under a
series of $n$ operations. Let $f(i)$ denote the actual running time of
the $i$th operation. For each of the following functions $f$,
determine the resulting amortized cost of a single operation.

\begin{parts}
  \part[10] $f(i)$ is the largest integer $k$ such that $2^k$ divides
  $i$.
  \part[10] $f(i)$ is $i$ if $i$ is an exact power of $2$, and $1$
  otherwise.
\end{parts}

\end{questions}
\end{document}
