% -*- 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}