% -*- compile-command: "latexmk -pdf hw-03-graphs.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=3,date=September\ 20,topic=Graphs]{algorithms-hw}

\begin{document}

\coversheet

\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(V+E)$ 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} \label{q:BFSQ}
  On the website you will find a file called \texttt{graph.txt} which
  describes a large undirected graph.  The first line of the file
  contains a single integer which is the number of edges in the graph.
  Each subsequent line of the file describes one edge, and contains
  two space-separated strings which are the names of the two vertices
  at the endpoints of the edge.

  Write a program (in a programming language of your choice) to find
  the shortest path from the vertex labelled with your first
  name\footnote{Collisions are resolved by appending the first letter
    of your last name.} to the vertex labelled \texttt{END} (if there
  are multiple shortest paths you can find any one of them).  You
  should submit a text file containing the list of vertices along this
  shortest path, starting with your name and ending with \texttt{END}.
  Each vertex should be on a separate line.  For example, my solution
  looks like this:
\begin{verbatim}
Brent
ClTxyl
LPlAQf
fM4ZaY
hweBqP
qKykFp
VwZSvh
END
\end{verbatim}
  You should also turn in the code you used to find your path.\marginnote[-5em]{Note
  that you must submit your solution to this problem (including your
  code and the text file with your shortest path)
  \textbf{electronically}, even if you turn in the rest of the
  assignment on paper.}
\end{question}

\end{document}




