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

\pagestyle{fancy}

\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 3}
\rfoot{Due: 4:00pm, Friday, February 10}
\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}

\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.
\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 and $m$ edges, 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
  $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}

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

\begin{question} \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). \]

Give an $O(n+m)$-time algorithm to find the
diameter of an (undirected) \textbf{tree} $T=(V,E)$.  Prove that your
algorithm is correct.
\end{question}

\begin{question}
  Does your algorithm from Question~\ref{q:diameter} work for
  \textbf{all} undirected graphs?  If so, prove it.  If not, provide a
  counterexample.
\end{question}

\begin{question} \mbox{}
  \begin{itemize}
  \item On a scale of 1 to 10, how difficult was this assignment?
  \item How many hours would you estimate that you spent on it?
  \item Which was your favorite question?  Your least favorite?
  \end{itemize}
\end{question}

\subsection*{Extra credit: Approximating the diameter of a graph}

\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}




