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


\pagestyle{fancy}

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

\subsection*{Some practice counting}

\begin{question}
  Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$
  edges.  Show that if every vertex has degree at least $n/2$, the
  graph is connected.  You may assume that $n$ is even.  As a hint,
  think about cuts in the graph.  A cut $(S,T)$ is a partition of the
  vertices into two sets $S$ and $T$ such that $S \cup T = V$ and $S
  \cap T = \emptyset$.
\end{question}

\begin{question}[K\&T 3.9]
  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.

  Suppose that an $n$-node undirected graph $G=(V,E)$ 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 $O(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.  As a
  hint, imagine performing a breadth-first search from $s$.  How large
  is each layer $L_{i}$ along the way to $t$?
\end{question}

\subsection*{BFS, again}

\begin{question}
Consider the following algorithm:

\newcommand{\unv}{\textsc{Unvisited}\xspace}
\newcommand{\vis}{\textsc{Visited}\xspace}
\newcommand{\parent}{\textit{parent}\xspace}

\begin{algorithm*}[h]
\caption{BFSQ} \label{alg:BFSQ}
\begin{algorithmic}[1]
\REQUIRE An undirected graph $G = (V,E)$ and a starting node $s \in V$.
\medskip
\STATE Initialize $Q$ to be a queue with a single element $s$
\STATE Initialize $T$ to an empty tree
\STATE Initialize all nodes to \unv
\WHILE{$Q$ is not empty}
  \STATE Remove the first node $u$ from $Q$
  \STATE Mark $u$ as \vis
  \FORALL{edges $(u,v) \in E$ adjacent to $u$}
    \IF{$v$ is \unv}
      \STATE Add $v$ to the end of $Q$
      \STATE Add $(u,v)$ to $T$
    \ENDIF
  \ENDFOR
\ENDWHILE
\RETURN $T$
\end{algorithmic}
\end{algorithm*}

  \begin{enumerate}[label=(\alph*)]
  \item Prove that algorithm BFSQ produces a tree whose levels are the
    same as the $L_i$ produced by the BFS algorithm from
    class. (\emph{Hint}: show that if $u \in L_i$ and $v \in L_j$ with
    $i < j$, then $u$ is added to $Q$ before $v$.)
  \item Describe a representation for $T$ which allows an arbitrary
    edge $(u,v)$ to be added to $T$ in $O(1)$ time.
  \end{enumerate}
\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.  For example, in $H_4$, the vertices $5$
  and $13$ are connected by an edge since $5 = 0101_2$ and
  $13 = 1101_2$ differ in exactly one bit.

  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|, use
  \verb|n ^ (1 << j)|, that is, the bitwise XOR of \verb|n| with
  $2^j$.)

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

\subsection*{Graph diameters}

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

\begin{question} \label{q:diameter} As in the text, we say that the
  {\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 a
  \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 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}




