% -*- compile-command: "rubber -d hw-03-graphs.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace,algorithm,algorithmic,enumitem,qrcode}

\pagestyle{fancy}

\lhead{CSCI 382: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 3}
\rfoot{Due: 3:00pm, Friday, September 15}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
%\renewcommand{\footwidth}{\textwidth}
%\addtolength{\headwidth}{\marginparwidth}
%\addtolength{\headwidth}{\marginparsep}
\renewcommand{\footrulewidth}{0.4pt}

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

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

\begin{document}

\mbox{}
\vspace{\fill}

\textbf{The first page of your homework submission must be a cover
  sheet answering the following questions.}  Do not leave it until the
last minute; it's fine to fill out the cover sheet before you have
completely finished the assignment. Assignments submitted without a
cover sheet, or with a cover sheet obviously dashed off without much
thought at the last minute, will not be graded.  \vspace{1in}

\begin{itemize}
\item How many hours would you estimate that you spent on this
  assignment?
  \vspace{1in}
\item Explain (in one or two sentences) one thing you learned through
  doing this assignment.
  \vspace{1in}
\item What is one thing you think you need to review or study more?
  What do you plan to do about it?
\end{itemize}

\vspace{\fill}

\newpage

\begin{question} \label{q:handshake}
  \marginnote{\emph{\ref{q:handshake}}\quad\qrcode{Start\ by\ proving\
      the\ handshake\ lemma:\ the\ sum\ of\ all\ vertex\ degrees\ is\
      twice\ the\ number\ of\ edges.}}
  Prove: for all $n \geq 1$, if $G$ is a connected graph with $n$
  vertices and $n-1$ edges, then $G$ has no cycles. (This is the third
  part of the proof from class, characterizing trees as having any two
  out of three properties.)
\end{question}

\begin{question} \label{q:connected-deg} Let $G=(V,E)$ be an
  \marginnote[0.5in]{\emph{\ref{q:connected-deg}}\quad\qrcode{Think\
      about\ cuts\ in\ the\ graph.\ A\ cut\ (S,T)\ is\ a\ partition\
      of\ the\ vertices\ into\ two\ sets\ S\ and\ T\ such\ that\
      every\ vertex\ is\ in\ either\ S\ or\ T\ but\ not\ both.}}
  undirected graph with $n$ vertices, with no self-loops (that is, no
  edges of the form $(v,v)$ from a vertex to itself).  Show that if
  every vertex has degree at least $n/2$, the graph is connected.  If
  it makes your proof easier, you may assume that $n$ is even.
\end{question}

% \begin{question}[K\&T 3.9] \label{q:bridge}
%   There's a natural intuition that two nodes that are far apart in a
%   communication network---separated by many hops---have a more tenuous
%   connection than two nodes that are close together.  There are a
%   number of algorithmic results that are based to some extent on
%   different ways of making this notion precise.  Here's one that
%   involves the susceptibility of paths to the deletion of nodes.

%   \marginnote{\emph{\ref{q:bridge}}\quad\qrcode{Imagine\ performing\
%       a\ breadth-first\ search\ starting\ from\ s.\ How\ large\ is\
%       each\ layer\ along\ the\ way\ to\ t?}}
%   Suppose that an undirected graph $G=(V,E)$ with $n$ vertices
%   contains two nodes $s$ and $t$ such that the distance between $s$
%   and $t$ is strictly greater than $n/2$.  Show that there must exist
%   some node $v$, not equal to either $s$ or $t$, such that deleting
%   $v$ from $G$ destroys all $s-t$ paths.  (In other words, the graph
%   obtained from $G$ by deleting $v$ contains no path from $s$ to $t$.)
%   Give an algorithm with running time $\Theta(m+n)$ to find such a node
%   $v$.  Describe your algorithm in prose and prove that it works
%   correctly.  Make sure your algorithmic description is clear and
%   concise.
% \end{question}

\begin{question}
  Consider the family of undirected graphs $\mathcal{H}_k$ defined as
  follows.  $\mathcal{H}_k$ has $2^k$ vertices labelled with the
  integers $0$ through $2^k - 1$.  Vertices $u$ and $v$ are connected
  by an edge if and only if the binary representations of $u$ and $v$
  differ in exactly one bit position.  For example, in $\mathcal{H}_4$, the
  vertices $5$ and $13$ are connected by an edge since $5 = 0101_2$
  and $13 = 1101_2$ differ in the first bit position, but the rest of
  the bits are the same.

  Consider doing a BFS in $\mathcal{H}_{10}$ starting at node $0$.
  How many vertices are in $L_6$, that is, the sixth layer generated
  by the BFS?  Give your answer together with either a proof, or the
  program you used to calculate the answer. Either approach will
  receive full credit. (\emph{Hint} if you choose to write a program:
  to flip the \verb|j|th bit of an integer \verb|n|, you can use
  \verb|n ^ (1 << j)|, that is, the bitwise XOR of \verb|n| with the
  result of shifting $1$ left $j$ times, that is, $2^j$.  These
  operators are valid syntax in many languages such as Java, Python,
  and C.)

  % (\emph{Hint:} to test whether \verb|x| and \verb|y| differ
  % in a single bit, you can compute
  % %
  % \[ \verb|(x != y) && ((x^y) & ((x^y) - 1) == 0)| \]
  % where \verb|&| is bitwise AND and \verb|^| is bitwise XOR.\footnote{\url{https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2}})
\end{question}

\begin{question} \mbox{}
  \begin{itemize}
  \item Visit \url{http://open.kattis.com/} and make an account if you don't
    already have one.
  \item Solve \url{http://open.kattis.com/problems/torn2pieces} using
    any programming language you want.  I have provided starter code
    in Python and Java on the course website.
  \item Submit a printout of your code, along with a link to your user
    profile on Kattis.
  \end{itemize}

  I am well aware that there are many solutions to this problem that
  can be found on the Internet.  Please \textbf{do not look at them}.
  You will learn far less if you look at someone else's solution,
  not to mention that it is an academic integrity
  violation---\emph{even} if you only intend to ``get a few ideas''
  and then write your own solution.

  A few hints:
  \begin{itemize}
  \item If you want to use a BFS, you don't need to keep track of the
    layers as in the pseudocode given in class.  Instead, you can just
    keep a queue of vertices to be processed.  That is, instead of
    putting a node in $L_{i+1}$, just put it in the queue.  Keep
    taking vertices out of the queue and processing them until the
    queue is empty.  Using a queue ensures that we finish processing
    each layer completely before moving on to any vertices in the next
    layer.
  \item Note that there may be stations which are not connected to
    \emph{any} other stations (although this would be quite strange in
    real life)!
  \item Be sure to process each connection as a \emph{two-way}
    (undirected) connection.  Some stations may not be listed
    separately if all their connections have already been listed under
    other stations.  For example, the input
\begin{verbatim}
  2
  A C
  B C
  A B
\end{verbatim}
    should yield the output \texttt{A C B}.  Station \texttt{C} is not
    listed on its own line, but it shows up as being connected to both
    \texttt{A} and \texttt{B}.
  \item You may or may not find it helpful to make a separate
    \texttt{Graph} class.  When submitting code to Kattis you cannot
    submit multiple files, but you can put multiple classes in the
    same file (even in Java!---just make sure that only one of the
    classes is marked \texttt{public}).
  \end{itemize}
\end{question}

\subsection*{Extra credit: Tree diameter}

\newcommand{\dist}{\mathit{dist}}
\newcommand{\diam}{\mathit{diam}}

\begin{question}[Optional extra credit] \label{q:diameter} As in the text, we say that the
  \marginnote{\emph{\ref{q:diameter}}\quad\qrcode{Pick\ an\ arbitrary\
      starting\ vertex\ u\ and\ find\ the\ vertex\ s\ which\ is\
      farthest\ from\ u.\ Then\ prove\ that\ the\ distance\ from\ s\
      to\ the\ vertex\ farthest\ from\ it\ is\ the\ diameter.}}  {\em
    distance} between two nodes $u$ and $v$ in a graph $G=(V,E)$ is
  the minimum number of edges in a path joining them; we'll denote
  this by $\dist(u,v)$.  We say that the {\em diameter} of $G$ is the
  maximum distance between any pair of nodes, that is,
  \[ \diam(G) = \max_{u,v \in V} \dist(u,v). \] \marginnote{Be careful that you
  understand what this definition says---the diameter is \emph{not}
  the length of the longest possible path!  It is the maximum length
  of a \emph{shortest} path.  These sorts of maximum-of-minimum
  definitions can be tricky to think about, but they come up all the
  time---as another example, for a given problem we typically want to
  come up with the algorithm with the \emph{best} \emph{worst}-case
  behavior.}

  Give a $\Theta(|V|+|E|)$-time algorithm to find the diameter of an
  (undirected) \textbf{tree} $T=(V,E)$.  Prove that your algorithm is
  correct for trees, and give a counterexample showing that your
  algorithm does not correctly find the diameter of all graphs.
\end{question}

% \begin{question}
%   There's a good chance your linear-time algorithm in
%   Question~\ref{q:diameter} doesn't extend to arbitrary undirected
%   graphs.  (If it does, you almost certainly have a STOC publication.
%   Congratulations!)  It turns out that, until very recently, we didn't
%   have any method for computing the diameter of a graph that didn't
%   first compute the shortest path between all pairs of nodes.  When
%   graphs are dense, all-pairs shortest paths is fairly expensive, so
%   some people have explored quicker algorithms which {\em estimate}
%   the diameter of the graph.  Develop a linear-time algorithm that,
%   given a graph $G$, returns a diameter estimate that is always within
%   a factor of 1/2 of the true diameter.  That is, if the true diameter
%   is $\diam(G)$ then you should return a value $k$ where $\diam(G)/2
%   \leq k \leq diam(G)$.
% \end{question}

\end{document}




