\documentclass[11pt]{article}


\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 181b} \\ Advanced Topics in Algorithms \\ Spring 2002 \\
Problem Set 6b \\ Due Tuesday in class
\end{center}

First a note about the synchronous distributed model:
Each node is assumed to have a unique ID (UID) between 1 and $n$, where
$n$ is the number of nodes in the network.
We assume that each node can store some
\emph{constant} number of variables.  These variables include the node's
UID among other information.  The specific values stored in these
variables constitute the state of the node.  The values in these variables
can be no larger than $n$.
Notice that a node is prohibited under this model from attempting to store
$n$ distinct variables.

At each synchronous clock pulse, each node sends some of its values to
its neighboring nodes.  It then collects the incoming values sent by its
neighbors and then changes some of the values of its variables
(effectively changing its state).

\begin{enumerate}

\item \textbf{[15 Points] Distributed Leader Election in a Ring.}
Consider a graph which is simply a ring of $n$ vertices.  Describe a
simple algorithm such that after $O(n)$ rounds, one node declares itself
the leader and all the remaining nodes say ``not it!''  (they declare
themselves non-leaders).

Explain why your algorithm runs in $O(n)$ rounds.  What is the
communication complexity of your algorithm?  (Recall that the
communication complexity is the total number of messages sent over all
edges during the algorithm.)


\item \textbf{[25 Points] Now for a More Efficient Algorithm!}
Now, solve the previous problem using $O(n)$ rounds and only $O(n \log
n)$ communication complexity. 

Here's an approach that you may wish to consider.  During phase 1, each
node sends its UID one hop to the left and right and the UID is then
reflected back to the sender unless a neighboring node had a larger UID.
Thus, the UID returns to the sender from both directions iff the sender
had a UID larger than both neighboring nodes.  In the next phase, some
nodes will send their UIDs twice as far as in the previous phase.
You fill in the details!

Explain why your algorithm has $O(n)$ time complexity and $O(n \log n)$
communication complexity.

\item \textbf{[10 Points] Matroids Revisited.}
Let $M=(E, \mathcal{I})$ be a matroid.  Analogous to the definition in a
vector space, the \emph{rank} of a set $X \subseteq E$, denoted $r(X)$,
is the size of the a largest independent set of $X$. Let $B$ be a basis
of $M$. Show that $r(B) = r(E) = |B|$.

\item \textbf{[10 Points] Matroids Rerevisited.}
  Recall that if $V$ is a vector space and $X \subseteq V$, the 
  \emph{span} of $X$, denoted $\mbox{span}(X)$, is defined to be the
subspace of all vectors that can be expressed as a linear combination of
vectors in
$X$.  One property of vector spaces is that for any basis $B$ in vector
space $V$, $\mbox{span}(B)= V$.

If $M = (E, \mathcal{I})$ is a matroid and $X \subseteq E$, the
span of $X$, denoted $\mbox{span}(X)$, is defined to be a maximal
superset $Y$ of $X$ such that $r(Y) = r(X)$.
Let $M=(E,\mathcal{I})$ be a matroid and let $B$ be a basis in the
matroid.  Show that $\mbox{span}(B) = E$.
\end{enumerate}
\end{document}