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

\usepackage{qrcode}

\pagestyle{fancy}

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

\begin{document}


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

\textbf{Note}: when asked to ``describe and analyze'' an algorithm,
you should describe the algorithm using pseudocode, prove its
correctness, and analyze its worst-case running time.

\marginnote{\qrcode{This\ is\ a\ hint.}}  Hints are provided in QR
codes in the margin, numbered by their corresponding question.  Some
questions have multiple hints; generally the hints are in order of
hintiness.  If you do not have a device capable of reading QR codes,
you can find the hints in the \verb|.tex| source for this document.

% \subsection*{Algorithms in the Wild:  Making Change}

% \begin{question}
% Our recent focus in class has been {\em greedy} algorithms.  Here we will examine a very practical problem that affords a greedy solution in some cases, but doesn't in others.  Consider the problem of making change for $n$ cents using the fewest number of coins.  Assume that each coin's value is an integer.
% \begin{description}
% 	\item [(a)] Describe a greedy algorithm to make change for $n$ cents using US quarters, dimes, nickels, and pennies.  Prove that your algorithm yields an optimal solution.	
% 	\item [(b)] 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 $n$.
% \end{description}
% \end{question}

\subsection*{Dijkstra's Algorithm}

\begin{question} Recall \emph{Dijkstra's Algorithm} for finding
  shortest paths in a directed, weighted graph.
  \begin{enumerate}
  \item Why doesn't Dijkstra's algorithm work if edges in the graph
    can have negative weights?  Give an example of a graph where
    Dijkstra's algorithm fails to find the shortest path between a
    pair of vertices.
  \item What happens if we replace ``smallest'' in Dijkstra's
    algorithm with ``biggest''---that is, we use a max priority queue
    so we pull out the \emph{biggest} edge on each iteration, and when
    we add a vertex $u$ to the set $S$, for each edge $(u,v)$ we
    update $\pi[v]$ with the \emph{maximum} of $\pi[v]$ and the sum
    $d[u] + l_{uv}$.  Can we use Dijkstra's algorithm to find
    \emph{longest} paths bewteen nodes in a graph?
  \end{enumerate}
\end{question}

\subsection*{Some Problems from Jeff Erickson}

\begin{question} \label{q:fes} A {\em feedback edge set} of an
  \marginnote{\emph{\ref{q:fes}\quad\qrcode{Think\ about\ maximum\
        weight\ spanning\ trees.}}}  undirected, connected graph $G$
  is a subset $F$ of the edges such that every cycle in $G$ contains
  at least one edge in $F$. In other words, removing every edge in $F$
  makes the graph $G$ acyclic.  Describe and analyze a fast algorithm
  to compute the minimum weight feedback edge set of a given
  edge-weighted graph.
\end{question}

\begin{question} \label{q:mst-update}
\marginnote{\emph{\ref{q:mst-update}a}\quad\qrcode{Consider\
    separately\ the\ cases\ when\ e\ is\ in\ T\ and\ is\ not\ in\ T.}}
  Suppose you are given a graph $G$ with weighted edges and a minimum
  spanning tree $T$ of $G$.
\begin{description}
\item [(a)] Describe and analyze an algorithm to update the minimum
  spanning tree when the weight of a single edge $e$ is decreased.
\item [(b)] Describe and analyze an algorithm to update the minimum
  spanning tree when the weight of a single edge $e$ is increased.
\end{description}
\marginnote[-0.3in]{\emph{\ref{q:mst-update}b}\quad\qrcode{Think\ about\ the\ cut\ and\ cycle\ properties\
    from\ lecture.}}
In both cases, the input to your algorithm is the edge $e$ and its new
weight; your algorithms should modify $T$ so that it is still a
minimum spanning tree.
\end{question}

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

% \begin{question}[checkers]
% Draughts/checkers is a game played on an $m \times m$ grid of squares, alternately colored light and dark.  The game is usually played on an $8 \times 8$ or $10 \times 10$ board, but the rules easily generalize to any board size. Each dark square is occupied by at most one game piece (called a checker in the U.S.), which is either black or white; light squares are always empty. One player (ÔWhiteÕ)  moves the white pieces; the other (ÔBlackÕ) moves the black pieces. 

% Consider the following simple version of the game, essentially American checkers or British draughts, but where every piece is a king.  Pieces can be moved in any of the four diagonal  directions, either one or two steps at a time. On each turn, a player either moves one of her pieces one step diagonally into an empty square, or makes a series of jumps with one of her checkers. In a single jump, a piece moves to an empty square two steps away in any diagonal direction, but only if the intermediate square is occupied by a piece of the opposite color; this enemy piece is captured 
% and immediately removed from the board. Multiple jumps are allowed in a single turn as long as they are made by the same piece. A player wins if her opponent has no pieces left on the board.  See Figure~\ref{fig:checkers} for an example. 

% Describe an algorithm that correctly determines whether White can capture every black piece, 
% thereby winning the game, in a single turn. The input consists of the width of the board ($m$), a list 
% of positions of white pieces, and a list of positions of black pieces. For full credit, your algorithm should run in $O(n)$ time, where $n$ is the total number of pieces. 

% \begin{figure}[h]

% % \centering\includegraphics[scale=0.5]{figures/checkers}
% \caption{\label{fig:checkers} (a) White can win in one turn using the jumps given in (b).  Both (c) and (d) have no one-turn wins.}
% \end{figure}

% \end{question}

\subsection*{Extra Credit}

\begin{question}
  (\textbf{Extra credit}.) One can use MST algorithms to generate
  mazes.  There's a nice Wikipedia entry on the topic:
\[
\text{\url{http://en.wikipedia.org/wiki/Maze_generation_algorithm}} \]
Read the sections about randomized Kruskal's and randomized Prim's
algorithms and implement a maze generation program using one of the
algorithms.  Your program should take three parameters, an integer
width, an integer height, and a filename, and output a maze in {\tt
  PNG} format.  For example,
\begin{verbatim}
genmaze 30 40 mymaze.png
\end{verbatim}
should generate a $30 \times 40$ maze in the file {\tt mymaze.png}.
Hand in a printout of a sample maze generated from your program, along
with a printout of your source code.
\end{question}

% \begin{question}[this question is very hard]
% In Question~\ref{q:fes} we considered feedback edge sets (FES).  Similarly, a {\em feedback vertex set} (FVS) in an undirected graph $G = (V, E)$ is a set $F \subseteq V$ of vertices such that every cycle in the graph $G$ contains some vertex in $F$. The {\em minimum feedback vertex set} problem is as follows: Given an undirected graph $G = (V, E)$ with a non-negative cost function on its vertices, $c : V \rightarrow \mathbb{R}^{+}$, find a minimum cost subset of vertices that is an FVS in $G$.  While FES is easy to solve in undirected graphs, FVS appears to be difficult in undirected graphs.  In fact, there is no known polynomial time algorithm to solve the problem.  However, it is possible to approximate the minimum FSV in polynomial time.  Develop and analyze an algorithm that finds a FSV that is always within a factor of 3 of the optimal FSV.
% \end{question}


\end{document}




